Dense polynomials whose squares are sparse

Squaring a polynomial usually makes it messier, but cancellation can make the square surprisingly sparse. How few terms can the square of a polynomial with many terms have? The best construction has stood since 1949; the task is to find a polynomial of degree $n$ with every coefficient nonzero whose square has fewer than $\sqrt{n}$ terms.

Problem

For $k \ge 1$ let $f(k)$ be the minimum number of nonzero coefficients of $p(x)^2$, over polynomials $p$ with exactly $k$ nonzero coefficients.

Task. Find $p(x) = a_0 + a_1 x + \cdots + a_n x^n$ with every $a_i$ a nonzero integer (so $p$ has $n + 1$ terms) such that $p(x)^2$ has fewer than $\sqrt{n}$ nonzero coefficients.

Such a $p$ shows $f(k) < k^{1/2}$ for $k = n + 1$. Products $p(x)\,p(x^N)$ with $N$ large, and their iterates, then give infinitely many $k$ with the same exponent.

Background

Rényi and Rédei first studied $f(k)$, and Erdős proved in 1949 that $f(k) < k^{1-c}$ for some $c > 0$; Erdős and Rényi conjectured that $f(k) \to \infty$, which Schinzel proved in 1987 [1, 4]. Even $f(k) < k$ is not obvious: Rényi found a polynomial with 29 terms whose square has 28, and Coppersmith and Davenport found one with 13 terms whose square has 12; Abbott showed that nothing of degree below 12 has a square with fewer terms than itself [3] (see also MathWorld). The present question is about the other end: how small $f(k)$ can be.

What is known

• Lower bound: $f(k) \gg \log k$ (Schinzel and Zannier, 2009) [2], improving Schinzel's $\log \log k / \log 2$ [1].
• Upper bound: Verdenius's 1949 construction gives $f(k) \ll k^{\log 8/\log 13} \approx k^{0.811}$ for real coefficients and $f(k) \ll k^{\log 6/\log 9} \approx k^{0.815}$ for integer coefficients, which is the case here. Per Epoch and the discussion of Erdős problem 485, neither has been improved since [4].
• So a dense polynomial with fewer than $\sqrt{n}$ terms in its square would cut the integer exponent from about $0.815$ to below $\tfrac{1}{2}$. Any exponent below the 1949 one would already be new.
• Erdős problem 485 (whether $f(k) \to \infty$) is solved; this upper-bound question is a different, open one.

What would count as progress

• An integer coefficient list $[a_0, \dots, a_n]$ with all entries nonzero; squaring and counting nonzero coefficients is immediate.
• Epoch scores submissions with its own verifier on a JSON array of the coefficients, constant term first.
• A construction with any exponent below that of Verdenius, even if it falls short of $\sqrt{n}$, would be the first improvement in more than 75 years.

References

1. A. Schinzel, On the number of terms of a power of a polynomial, Acta Arith. 49 (1987), 55–70. doi:10.4064/aa-49-1-55-70
2. A. Schinzel and U. Zannier, On the number of terms of a power of a polynomial, Rend. Lincei Mat. Appl. 20 (2009), 95–98. doi:10.4171/RLM/534
3. J. Abbott, Sparse squares of polynomials, Math. Comp. 71 (2002), 407–414. doi:10.1090/S0025-5718-00-01294-1
4. T. F. Bloom, Erdős Problem #485, with its discussion thread. erdosproblems.com/485

Source

Imported from FrontierMath: Open Problems, polynomial-square-few-coefficients, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.