4 Search Problems in Vector Spaces
2014
We consider the following q-analog of the basic combinatorial search problem: let q be a prime power and GF(q) the nite eld of q elements. Let V denote an n-dimensional vector space over GF(q) and let v be an unknown 1-dimensional subspace of V. We will be interested in determining the minimum number of queries that is needed to nd v provided all queries are subspaces of V and the answer to a query U is YES if v 6 U and NO if v ̸6 U. This number will be denoted by A(n; q) in the adaptive case (when for each queries answers are obtained immediately and later queries might depend on previous answers) andM(n; q) in the non-adaptive case (when all queries must be made in advance). In the case n = 3 we prove 2q − 1 = A(3; q) < M(3; q) if q is large enough. While for general values of n and q we establish the bounds n log q ≤ A(n; q) ≤ (1 + o(1))nq and (1 − o(1))nq ≤M(n; q) ≤ 2nq; provided q tends to innity.