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
  • 5
    $\begingroup$ For examples, please see this. Not simple! $\endgroup$ Jul 21, 2015 at 15:52
  • $\begingroup$ @AndréNicolas , Thank you but is there an elegant way to find those polynomials? I $\endgroup$
    – Tom Lynd
    Jul 21, 2015 at 15:55
  • $\begingroup$ You are welcome. Quick I do not know. $\endgroup$ Jul 21, 2015 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, 2015 at 16:07
  • $\begingroup$ Degree 12 is smallest, per reference given by André Nicolas. Might be tough for undergraduates. $\endgroup$
    – jbuddenh
    Jul 21, 2015 at 16:28

1 Answer 1

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$
2
  • $\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, 2015 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$ Jul 21, 2015 at 16:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .