Let $F$ be a finite field, $n, k, m$ be natural numbers. I give you $m$ vectors $c^{(1)},\ldots,c^{(m)}\in F^n$. I ask for polynomials $p_1,\ldots,p_n$ on $k$ variables over $F$ such that the system of polynomial equations $p_i(t_1,\ldots,t_k)=c^{(j)}_i$ for $i=1,\ldots,n$ is satisfiable for every $1\leq j\leq m$.

Such polynomials can be found with degree $1$ if $k=n$: just take $p_i^{(j)}(t_1,\ldots,t_{k}) = t_i$. Can one find such polynomials when $k=n^{\epsilon}$ for a small $\epsilon>0$ and with degree depending only on $1/\epsilon$?

  • $\begingroup$ A simple observation: If $k = 1$ and $m > |F|$, then there are no solutions, because for all $p_1, \ldots, p_n \in F[t]$, $|\lbrace (p_1(t), \ldots, p_n(t)): t \in F \rbrace| \leq |F| < m$. By the same argument, in general there can be no solution if $m > |F|^k$. $\endgroup$
    – pinaki
    May 17 '11 at 14:34

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.