# Forcing scalar products to avoid prescribed values

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

• 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... – fedja Nov 22 '18 at 19:21
• $b_j$ and $v_j$ denote the same thing, right? – Fedor Petrov Nov 24 '18 at 11:30
• @FedorPetrov: Right, fixed! – Seva Nov 24 '18 at 14:38
• I would say, for any $d$-dimensional subspace $L$ there are at most $N(p,d)$ indices $j$ with $v_j\in L$... – Ilya Bogdanov Nov 24 '18 at 15:54
• @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$. – Seva Nov 24 '18 at 15:57