13
$\begingroup$

If $P$ is a polynomial over the field $\mathbb F_q$ of degree at most $q-2$ with $k$ nonzero coefficients, then $P$ has at most $(1-1/k)(q-1)$ distinct nonzero roots.

Does this fact have any standard name / reference / proof / refinements / extensions?

$\endgroup$
1
  • 5
    $\begingroup$ What is $p$? Do you mean $(q-1)$ instead of $(p-1)$? $\endgroup$ Aug 17, 2018 at 14:43

2 Answers 2

14
$\begingroup$

Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $\mathbb{F}_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^{q-1}-1$. This is why the following argument looks natural and I expect something similar to appear in other extensions of this result.

Denote $P(x)=\sum_{i=1}^k c_i x^{a_i}$, $0=a_1<a_2<a_3<\dots<a_k\leqslant q-2<a_{k+1}:=q-1$. Choose $i\in \{1,2,\dots,k\}$ such that $a_{i+1}-a_i\geqslant (q-1)/k$ and reduce the polynomial $Q(x)=x^{q-1-a_{i+1}}P(x)$ modulo $x^{q-1}-1$. The remainder $R(x)$ has the same non-zero roots as $P$, but $\deg R(x)\leqslant \max (q-1+a_i-a_{i+1},a_k-a_{i+1})=q-1+a_i-a_{i+1}\leqslant (q-1)(1-\frac1k)$.

This method allows to get something for the polynomials in many variables. Say, if a non-zero polynomial $P(x_1,\dots,x_n)$ has degree at most $q-2$ in each variable and has at most $M$ non-zero-coefficients, we may estimate the number of points $a=(a_1,\dots,a_n)\in (\mathbb{F}_q^*)^n$ for which $P(a)=0$. Namely, choose some ``forbidden'' set $\Omega\in \{0,1,\dots,q-2\}^n$ and look for a monomial $x_1^{c_1}\dots x_n^{c_n}$ for which all monomials of the reduced polynomial $x_1^{c_1}\dots x_n^{c_n}P(x_1,\dots,x_n)$ (reduced modulo the ideal $\langle x_1^{q-1}-1,\dots,x_n^{q-1}-1\rangle$, that does not change the zeroes in $(\mathbb{F}_q^*)^n$) do not belong to $\Omega$. If we choose random exponents $c_1,\dots,c_n$, each specific monomial belongs to $\Omega$ after multiplying by $x_1^{c_1}\dots x_n^{c_n}$ and reduction with probability $|\Omega|/(q-1)^n$. Thus if $M\cdot |\Omega|<(q-1)^n$, we may avoid $\Omega$ by suitable multiplication and reduction. For certain choices of $\Omega$ this gives some upper bounds on the number of zeroes by De Millo -- Lipton -- Schwartz -- Zippel -- Alon -- Füredi -- $\dots$ theory.

$\endgroup$
0
5
$\begingroup$

This is just an uncertainty principle for the cyclic group $\mathbb F_q^*$; see, e.g. this paper by Tao.

$\endgroup$
1
  • $\begingroup$ Right, this is, essentially, what motivated me to ask this question. However, this is a sort of "non-standard uncertainty" since the functions in question are not complex-valued, but $\mathbb F_q$-valued. Anyway, I wonder whether this result about the polynomials has appeared somewhere, or has a "standard" name / reference. $\endgroup$
    – Seva
    Nov 20, 2018 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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