Sparse Univariate Polynomials with Many Roots Over Finite Fields

Abstract

Suppose $q$ is a prime power and $f\in {\mathbb{F}}_q[x]$ is a univariate polynomial with exactly $t$ monomial terms and degree $<q-1$. To establish a finite field analogue of Descartes' Rule, Bi, Cheng, and Rojas (2013) proved an upper bound of $2(q-1{)}^{\frac{t-2}{t-1}}$ on the number of cosets in ${\mathbb{F}}_q^{\ast }$ needed to cover the roots of $f$ in ${\mathbb{F}}_q^{\ast }$. Here, we give explicit $f$ with root structure approaching this bound: For $q$ a $(t-1)$-st power of a prime we give an explicit $t$-nomial vanishing on $q^{\frac{t-2}{t-1}}$ distinct cosets of ${\mathbb{F}}_q^{\ast }$. Over prime fields ${\mathbb{F}}_p$, computational data we provide suggests that it is harder to construct explicit sparse polynomials with many roots. Nevertheless, assuming the Generalized Riemann Hypothesis, we find explicit trinomials having $\Omega \left(\frac{\log p}{\log \log p}\right)$ distinct roots in ${\mathbb{F}}_p$.

9 pages, 1 figure, presented at MEGA 2015. This is the journal version, and includes new extremal examples and additional references, including pointers to recent advances by Kelley and Owen. Comments and questions welcome

Cited by in corpus (1)

• Roots of Sparse Polynomials over a Finite Field