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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.