# Does there exist a polynomial $f(x)$ with real coefficients such that $f(x)^2$ has fewer nonzero coefficients than $f(x)$?

I saw this problem on a problem set and I have absolutely no idea how to proceed in a feasible way.

Does there exist a polynomial $f(x)$ with real coefficients such that $f(x)^2$ has fewer nonzero coefficients than $f(x)$?

Any help would be appreciated.

• For examples, please see this. Not simple! – André Nicolas Jul 21 '15 at 15:52
• @AndréNicolas , Thank you but is there an elegant way to find those polynomials? I – Tom Lynd Jul 21 '15 at 15:55
• You are welcome. Quick I do not know. – André Nicolas Jul 21 '15 at 16:02
• The reason for my quest is that this problem is taken from a problem set which is aimed at undergraduates. – Tom Lynd Jul 21 '15 at 16:07
• Degree 12 is smallest, per reference given by André Nicolas. Might be tough for undergraduates. – jbuddenh Jul 21 '15 at 16:28

Hint: What happens if you consider a truncated Taylor series for $\sqrt{1-x}$ ? For instance:

$$\left(1-\frac{x}{2}-\frac{x^2}{8}-\frac{x^3}{16}-\frac{5 x^4}{128}\right)^2 = 1-x+\frac{7 x^5}{128}+\frac{7 x^6}{512}+\frac{5 x^7}{1024}+\frac{25 x^8}{16384}$$ with about the same number of non-zero coefficients. Are you able to adjust a couple of coefficients in the LHS in order to prove your claim? For instance: $$\left(1-\frac{x}{2}-\frac{x^2}{8}-\frac{x^3}{16}+ \frac{x^4}{64}\right)^2=1-x+\frac{7 x^4}{64}-\frac{x^7}{512}+\frac{x^8}{4096}.$$ However, in order to find a polynomial whose square has fewer non-zero terms than the original polynomial, you have to consider polynomials with degree at least $12$.

• Interesting! Can you cite a proof that no polynomial exists with degree less than $12$ and having the desired property? – Tom Lynd Jul 21 '15 at 16:02
• @TomLynd: to be honest, I never read the proof, but Wikipedia gives it is due to Abbott (2002) and it is more or less an extensive computation through Groebner basis. – Jack D'Aurizio Jul 21 '15 at 16:16