Maximum degree of a polynomial $\sum\limits_{i=0}^n a_i x^{n-i}$ such that $a_i = \pm 1$ for every $i$, with only real zeroes

What is the maximum degree of a polynomial of the form $\sum\limits_{i=0}^n a_i x^{n-i}$ with $a_i = \pm 1$ for $0 \leq i \leq n$, such that all the zeros are real?

How would I manipulate that scary sigma? I'm stuck. Solutions are greatly appreciated.

• I think that Newton's and MacLaurin's inequalities play a major role here. That scary sigma is just a notation shortcut for writing the involved polynomial. – Jack D'Aurizio Oct 13 '16 at 23:27
• Anyway, $1-x-x^2+x^3 = (x+1)(x-1)^2$, so the maximum degree is at least $3$. – Jack D'Aurizio Oct 13 '16 at 23:29

The maximum degree is $3$.

Let $\mathcal{E} = \{ +1, -1 \}$. Let's say for some $n \ge 3$, there is a polynomial $p(z) = \sum_{k=0}^n a_k z^k \in \mathcal{E}[x]$ and all its roots are real. Let $\lambda_1, \ldots,\lambda_n$ be the roots. By Vieta's formula, we have

$$\sum_{k=1}^n \lambda_k = -\frac{a_{n-1}}{a_n} \in \mathcal{E} \quad\text{ and }\quad \sum_{1 \le j \le k \le n} \lambda_j \lambda_k = \frac{a_{n-2}}{a_n} \in \mathcal{E}$$ This implies $$\sum_{k=1}^n\lambda_k^2 = \left(\sum_{k=1}^n\lambda_k\right)^2 - 2\sum_{1\le j \le k \le n}\lambda_j\lambda_k = \left(\frac{a_{n-1}}{a_n}\right)^2 - 2\frac{a_{n-2}}{a_n} = 3 \text{ or } - 1$$ Since $\lambda_k$ are all real, we can rule out the second case. As a result, $\sum\limits_{k=1}^n \lambda_k^2 = 3$.

Apply a similar argument to $z^n p\left(\frac1z\right)$, we find $\sum\limits_{k=1}^n \lambda_k^{-2} = 3$.

Combine these two results and notice $\lambda^2 + \lambda^{-2} \ge 2$ for all real number $\lambda$, we have

$$6 = 3 + 3 = \sum_{k=1}^n \lambda_k^2 + \lambda_k^{-2} \ge \sum_{k=1}^n 2 = 2n\quad\implies\quad 3 \ge n$$

This implies the maximum degree is at most $3$.

As pointed by Jack D'Aurizio in comment more than a year ago, there is a polynomial with degree $3$ in $\mathcal{E}[x]$

$$1 - x - x^2 + x^3 = (x+1)(x-1)^2$$ whose roots are all real. This means the maximum degree is indeed $3$.