How many roots can there be of a polynomial $f \in K[x_1, x_2, \dots , x_n]$ where $K$ is a finite field and the maximum exponent of $x_i$ in any term is $m$ for all $i$, assuming not all coefficients are zero?

I found this related question, but I'm really interested in the worst case; I won't have any "singularity condition", necessarily.

Here's an idea:

View $f$ as a polynomial over $(K(x_2, \dots , x_n))[x_1]$, where $K(x_2, \dots , x_n)$ is the field of fractions of $K[x_2, \dots , x_n]$. At least one coefficient of $f$ when viewed this way is non-zero. Now $f$ has at most $m$ roots, since its single indeterminate, $x_1$, has exponent at most $m$. For each of these $m$ roots $y_{1,1}, y_{1,2}, \dots, y_{1,m}$ and any $x_2, \dots, x_n$, $f(y_{1,j}, x_2, \dots, x_n) = 0$. There are $m k^{n-1}$ tuples of this form, where $k$ is the size of $K$.

Additionally, for each $v \in K$, $f(v, x_2, \dots, x_n)$ is a polynomial in $n-1$ variables. For the $v$s that are not roots of $f$ when viewed as above, $f(v, x_2, \dots, x_n)$ has at least one non-zero coefficient. This sets up an inductive equation:

$$ c(n) \leq \begin{cases} m & n = 1\\ m k^{n-1} + k c(n-1) & n > 1 \end{cases} $$

With solution

$$ c(n) \leq n m k^{n-1} $$

On the other hand, let $f_i$ be a polynomial of degree $m$ in $K[x_i]$ with $m$ distinct roots. Then $\prod f_i$ has at least $n m (k-m)^{n-1}$ distinct roots.

Is this right? Can we get tighter bounds?

  • 2
    $\begingroup$ Of course you should sprinkle the phrase "not identically zero" liberally throughout. $\endgroup$ Apr 20, 2013 at 7:59
  • 1
    $\begingroup$ I thought that it might be reasonable to let you know that your question and answer have been discussed on meta recently. $\endgroup$ Aug 26, 2016 at 17:52

1 Answer 1


It turns out that the upper bound is just a special case of the Schwartz-Zippel lemma.

  • 1
    $\begingroup$ A user has asked for a more detailed explanation in this case. $\endgroup$
    – hardmath
    Aug 26, 2016 at 19:45
  • $\begingroup$ can you add some more details or references? $\endgroup$
    – glS
    Sep 17, 2019 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.