Sparse univariate polynomials with many roots over finite fields

DOI10.1016/J.FFA.2017.03.006MaRDI QIDQ2363328zbMATH OpenOpenAlexFDO

Authors Qi Cheng, Shuhong Gao, J. Maurice Rojas, Daqing Wan

Publication date 13 July 2017

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6346

zbMATH Keywords

torsionfinite fieldChebotarev densitysparse polynomialFrobeniuscosetDescartes\(t\)-nomialleast prime

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Abstract: Suppose $q$ is a prime power and $finmathbb{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{)}^{fract-2t-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^{fract-2t-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 $Omegaleft(fraclogploglogpight)$ distinct roots in $mathbb{F}_p$.

Recommendations

• Roots of sparse polynomials over a finite field
• Estimating the number of roots of trinomials over finite fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• On the number of distinct roots of a lacunary polynomial over finite fields

Cites work

• scientific article; zbMATH DE number 3539473 (Why is no real title available?)
• scientific article; zbMATH DE number 3563269 (Why is no real title available?)
• scientific article; zbMATH DE number 1305294 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 5019718 (Why is no real title available?)
• scientific article; zbMATH DE number 3091842 (Why is no real title available?)
• A bound for the least prime ideal in the Chebotarev density theorem
• A note on the different of the composed field
• Estimates on exponential sums related to the Diffie-Hellman distributions
• Estimating the number of roots of trinomials over finite fields
• Explicit zero density theorems for Dedekind zeta functions
• Factorization of polynomials over finite fields
• Norms of roots of trinomials
• Numbers of solutions of equations in finite fields
• On some approximation problems concerning sparse polynomials over finite fields
• On the irreducibility of certain trinomials
• On the statistical properties of Diffie-Hellman distributions
• Roots of Polynomials in Subgroups of and Applications to Congruences
• Roots of sparse polynomials over a finite field
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• The distribution of polynomials over finite fields
• The smallest prime that splits completely in an abelian number field
• Uniform Distribution of Polynomials Over Finite Fields
• Zeros of sparse polynomials over local fields of characteristic \(p\)

Cited in

(12)

• Sparse shifts for univariate polynomials
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Roots of sparse polynomials over a finite field
• Counting roots for polynomials modulo prime powers
• Sparse squares of polynomials
• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Estimating the number of roots of trinomials over finite fields
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Sparse polynomial equations and other enumerative problems whose Galois groups are wreath products
• Value sets of sparse polynomials
• Polynomials whose powers are sparse
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

This page was built for publication: Sparse univariate polynomials with many roots over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363328)