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