# Counting roots of a multivariate polynomial over a finite field

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?

-
Of course you should sprinkle the phrase "not identically zero" liberally throughout. –  Greg Martin Apr 20 '13 at 7:59
Thanks, Martin! –  jbapple Apr 20 '13 at 15:21

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

-