Roots of sparse polynomials over a finite field
Zander Kelley · LMS Journal of Computation and Mathematics · 2016
For a $t$ -nomial $f(x)=\sum _{i=1}^{t}c_{i}x^{a_{i}}\in \mathbb{F}_{q}[x]$ , we show that the number of distinct, nonzero roots of $f$ is bounded above by $2(q-1)^{1-\unicode[STIX]{x1D700}}C^{\unicode[STIX]{x1D700}}$ , where $\unicode[STIX]{x1D700}=1/(t-1)$ and $C$ is the size of the largest coset in $\mathbb{F}_{q}^{\ast }$ on which $f$ vanishes completely. Additionally, we describe a number-theoretic parameter depending only on $q$ and the exponents $a_{i}$ which provides a general and easily computable upper bound for $C$ . We thus obtain a strict improvement over an earlier bound of Canettiet al. which is related to the uniformity of the Diffie–Hellman distribution. Finally, we conjecture that $t$ -nomials over prime fields have only $O(t\log p)$ roots in $\mathbb{F}_{p}^{\ast }$ when $C=1$ .