A polynomial has only real roots and all coefficients $\pm 1$. Prove the degree $<4$.

Let $P(x)$ be a polynomial with only real roots and all coefficients equal to $\pm 1$. Prove that the degree of the polynomial is less than 4.

This is practice for Putnam, but I am not certain where to begin. I know I need to use inequalities. Could this be a roots of unity problem?

• Well $x^4+1$ has no real roots, so there's a start. – Ian Coley Sep 18 '13 at 4:44
• I think it's supposed to say "A polynomial has ONLY real roots". – Glen O Sep 18 '13 at 4:45
• Yes allow me to correct that. The source for the problem also made that mistake. – Alex Sep 18 '13 at 4:49
• There's also the fact that primitive $n$th roots of unity are not real after $n=2$ and they are roots of cyclotomic polynomials, which tend to have only coefficients $\pm1$. – Ian Coley Sep 18 '13 at 4:50
• Just to state the obvious, all coefficients are supposed to be in $\{-1,0,1\}$. – Marc van Leeuwen Sep 18 '13 at 5:04

Let $P(x)=x^n+a_1x^{n-1}+...+a_n$ where all $a_i'$ s are $1$ or $-1$ and $x_1,x_2...x_n$ are all real roots of $P.$ By Viet's formulas $|x_1+x_2+...+x_n|=1$ and $x_1^2+x_2^2+...+x_n^2=(x_1+x_2+...x_n)^2-2\sum_{i<j}x_ix_j=1-2a_{2}=3.$ Now we can estimate $3=x_1^2+x_2^2+...x_n^2\ge n\sqrt[n]{x_1^2x_2^2...x_n^2}=n$ so, $n\le 3$ and the result follows.