Search problems in vector spaces

Abstract: We consider the following

q

-analog of the basic combinatorial search problem: let

q

be a prime power and

G F (q)

the finite field of

q

elements. Let

V

denote an

n

-dimensional vector space over

G F (q)

and let

m a t h b f v

be an unknown 1-dimensional subspace of

V

. We will be interested in determining the minimum number of queries that is needed to find

m a t h b f v

provided all queries are subspaces of

V

and the answer to a query

U

is YES if

m a t h b f v l e q s l a n t U

and NO if

m a t h b f v o t l e q s l a n t 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) and

M (n, q)

in the non-adaptive case (when all queries must be made in advance). In the case

n = 3

we prove

2 q - 1 = A (3, q) < M (3, q)

if

q

is large enough. While for general values of

n

and

q

we establish the bounds [ nlog q le A(n,q) le (1+o(1))nq ] and [ (1-o(1))nq le M(n,q) le 2nq, ] provided

q

tends to infinity.

Recommendations

Cites Work

Cited In (8)

This page was built for publication: Search problems in vector spaces