Sparse univariate polynomials with many roots over finite fields

作者：Cheng, Qi^*; Gao, Shuhong; Rojas, J. Maurice; Wan, Daqing

来源：Finite Fields and Their Applications, 2017, 46: 235-246.

DOI：10.1016/j.ffa.2017.03.006

• Sparse polynomial
• t-nomial
• Finite field
• Descartes
• Coset
• Torsion
• Chebotarev density
• Frobenius
• Least prime

Suppose q is a prime power and f is an element of 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 Omega (log p/log log p) distinct roots in F-p.

• 出版日期2017-7