10
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Of course you should sprinkle the phrase "not identically zero" liberally throughout. $\endgroup$ Commented 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$ Commented Aug 26, 2016 at 17:52

1 Answer 1

4
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .