MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$. – auniket May 17 '11 at 14:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.