1
$\begingroup$

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$?

$\endgroup$
1
  • $\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, 2011 at 14:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.