Roots of Sparse Polynomials over a Finite Field

Abstract

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-\epsilon }{C}^{\epsilon }$, where $\epsilon =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 Canetti et 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$.

References in corpus (1)

• Sparse Univariate Polynomials with Many Roots Over Finite Fields

Cited by in corpus (4)

• On the clique number of Paley graphs of prime power order
• Distribution of integral values for the ratio of two linear recurrences
• Value sets of sparse polynomials
• On the number of distinct roots of a lacunary polynomial over finite fields