Let $p$ be a prime, and $n\ge 1$ an integer number. Suppose that the (not necessarily distinct) vectors $v_1,\dotsc,v_N \in{\mathbb F}_p^n$ satisfy the following condition:

\begin{gather} \text{For any $f_1,\dotsc,f_N\in\mathbb F_p$, there exists $z\in\mathbb F_p^n$ such that} \\ \langle v_1,z\rangle\ne f_1,\dotsc,\langle v_N,z\rangle\ne f_N. \tag{$\ast$} \end{gather}

How large can $N$ be under this assumption?

Denoting the largest possible value of $N$ by $N(p,n)$, one has $N(p,1)=p-1$. In general, $N(p,n)\ge(p-1)n$, as follows by taking $(v_j)$ to be the sequence containing $p-1$ instances of every basis vector; how sharp is this bound?

Incidentally, ($\ast$) implies that for any subspace $L\le\mathbb F_p^n$ there are at most $|L|-1$ indices $j\in[1,N]$ with $v_j\in L$, but this does not lead to any reasonable upper bound for $N(p,n)$.

  • 3
    $\begingroup$ The obvious upper bound is $np\log p$ (every next choice of $f_j$ can be made to reduce the available set of $z$ by $1/p$ of its size). I'm not sure which of the two trivial bounds is closer to the truth though... $\endgroup$ – fedja Nov 22 '18 at 19:21
  • 1
    $\begingroup$ $b_j$ and $v_j$ denote the same thing, right? $\endgroup$ – Fedor Petrov Nov 24 '18 at 11:30
  • $\begingroup$ @FedorPetrov: Right, fixed! $\endgroup$ – Seva Nov 24 '18 at 14:38
  • $\begingroup$ I would say, for any $d$-dimensional subspace $L$ there are at most $N(p,d)$ indices $j$ with $v_j\in L$... $\endgroup$ – Ilya Bogdanov Nov 24 '18 at 15:54
  • $\begingroup$ @IlyaBogdanov: I would expect something of this sort, but this does not seem immediate to me: inside $L$, you are limited with the choice of $z$. $\endgroup$ – Seva Nov 24 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.