Factors of Sparse Polynomials are Sparse

2014/04/18 by Zeev Dvir, Rafael Oliveira, Dvir, Zeev +1
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1404.4834

openalex publication_date 2014/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample to this paper's main result in positive characteristic: If F is a field with prime characteristic p, then the polynomial x₁^p + x₂^p + … + x^np has the following factor: (x₁+x₂+ … + x_n)^p-1, which has sparsity n^p.

Citations

• Approximate formulas for some functions of prime numbers

Related

• The 3-sparsity of Xⁿ-1 over finite fields, II
• Computing sparse multiples of polynomials
• Sparse Univariate Polynomials with Many Roots Over Finite Fields
• The 3-sparsity of Xⁿ-1 over finite fields
• Root structures of polynomials with sparse exponents