12
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ Interesting! Can you cite a proof that no polynomial exists with degree less than $12$ and having the desired property? $\endgroup$ – Tom Lynd Jul 21 '15 at 16:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Jul 21 '15 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.