← Back to arXiv
arXivNumber TheoryarXiv:2609.22286

Superpolynomially Large Support in Every Irreducible Factor of Lacunary Polynomials

The paper is about a basic question in algebra: if you start with a "sparse" polynomial (one where most coefficients are zero, with only a handful of nonzero terms), must its factors also be sparse? Sparse polynomials, sometimes called lacunary polynomials, are convenient to work with precisely because they can have very high degree while still being described compactly. Researchers have long wondered whether sparsity is "inherited" when you factor such polynomials, similar to how other algebraic operations like taking powers or composing polynomials do tend to preserve sparsity in a predictable way.

The main result of the paper is a definitive "no" to that question, in a strong quantitative sense. The authors construct infinitely many polynomials over the rational numbers that have exactly m nonzero terms, yet every irreducible piece (factor that cannot be broken down further) of each such polynomial has a superpolynomially large number of nonzero terms, meaning the number of terms grows faster than any fixed power of m. This is a striking gap: you start with something compact and sparse, and every building block hiding inside it is unavoidably dense with nonzero coefficients.

The result matters because it separates multiplication from other algebraic operations in a fundamental way. For operations like exponentiation or composition, there are known "reverse sparsity" principles guaranteeing that if the output is sparse, the inputs must be too. Multiplication has no such guarantee, and this paper makes that precise without any extra assumptions on the size of the coefficients, the positions of the exponents, or the degree of the polynomial. This provides a clean, unconditional obstruction to sparse factorization, filling a gap in our understanding of how complexity behaves under polynomial arithmetic.

Read original →