Sparse univariate polynomials with many roots over finite fields

DOI10.1016/J.FFA.2017.03.006zbMATH Open1406.11121arXiv1411.6346OpenAlexW2964149052MaRDI QIDQ2363328FDOQ2363328

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)

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$.

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

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

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)

Cites Work

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

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
• Value sets of sparse polynomials
• Sparse polynomial equations and other enumerative problems whose Galois groups are wreath products
• 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)