Skip to main content
2 of 2
Typos fixed, tag added
Seva
  • 23k
  • 2
  • 59
  • 141

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

Seva
  • 23k
  • 2
  • 59
  • 141