Erdős Problem #485

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\)? A conjecture of Erdős and Rényi (this is Problem 4.4 in [Ha74], attributed to Erdős); the function was first investigated by Rényi and Rédei [Re47], and Erdős [Er49b] proved that \(f(k) < k^{1-c}\) for some \(c > 0\). The answer is yes: Schinzel [Sc87] proved \(f(k) > \log \log k / \log 2\), and Schinzel and Zannier [ScZa09] improved this to \(f(k) \gg \log k\).