PROVED
This has been solved in the affirmative.
Let $f(k)$ be the minimum number of terms in $P(x)^2$, where $P\in \mathbb{Q}[x]$ ranges over all polynomials with exactly $k$ non-zero terms. Is it true that $f(k)\to\infty$ as $k\to \infty$?
This is Problem 4.4 in
[Ha74], where it is attributed to Erdős.
First investigated by Rényi and Rédei
[Re47]. Erdős
[Er49b] proved that $f(k)<k^{1-c}$ for some $c>0$. The conjecture that $f(k)\to \infty$ is due to Erdős and Rényi.
This was solved by Schinzel
[Sc87], who proved that\[f(k) > \frac{\log\log k}{\log 2}.\]In fact Schinzel proves lower bounds for the corresponding problem with $P(x)^n$ for any integer $n\geq 1$, where the coefficients of the polynomial can be from any field with zero or sufficiently large positive characteristic.
Schinzel and Zannier
[ScZa09] have improved this to\[f(k) \gg \log k.\]
View the LaTeX source
This page was last edited 29 December 2025.
Additional thanks to: Stefan Steinerberger
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #485, https://www.erdosproblems.com/485, accessed 2026-01-16
