4
$\begingroup$

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)$.

$\endgroup$
10
  • 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
    Commented Nov 22, 2018 at 19:21
  • 1
    $\begingroup$ $b_j$ and $v_j$ denote the same thing, right? $\endgroup$ Commented Nov 24, 2018 at 11:30
  • $\begingroup$ @FedorPetrov: Right, fixed! $\endgroup$
    – Seva
    Commented Nov 24, 2018 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$ Commented Nov 24, 2018 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
    Commented Nov 24, 2018 at 15:57

0

You must log in to answer this question.

Browse other questions tagged .