Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

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

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