Sparse univariate polynomials with many roots over finite fields

Abstract Suppose q is a prime power and f ∈ 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 ) t − 2 t − 1 on the number of cosets in F q ⁎ needed to cover the roots of f in F q ⁎ . Here, we give explicit f with root structure approaching this bound: When q is a perfect ( t − 1 ) -st power we give an explicit t -nomial vanishing on q t − 2 t − 1 distinct cosets of F q ⁎ . Over prime fields 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 Ω ( log ⁡ p log ⁡ log ⁡ p ) distinct roots in F p .