Problem #485: Let $f(k)$ be the minimum number of terms in $P(x)^2$,...

---

Progress

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.\]