# n-th order polynomial with all roots where all coefficients are 1 or -1, highest order of n?

I have polynomial $$f(x） = \sum_{i=0}^n a_i x^i$$, where $$a_i = \pm 1$$. All roots of $$f(x)$$ are real. What's the highest order of $$n$$? Note that the roots are real but can be irrational. Even if there are duplicate roots, that's fine

• I assume you are not counting multiplicity of the roots (i.e. the n roots are all distinct).
– D.B.
Dec 25, 2018 at 4:02
• @D.B. yes, even if there are duplicate roots, that's fine Dec 25, 2018 at 4:04
• An example with $n=3$ is $x^3-x^2-x+1 = (x-1)^2(x+1)$. There don't seem to be any for $n=4, 5$, $6$ or $7$. Dec 25, 2018 at 4:15
• @RobertIsrael that's right. We can prove all roots have abs value between (0.5,2) as well. Dec 25, 2018 at 4:40
• Descartes’ Rule of Signs might be helpful here. Dec 25, 2018 at 4:49

Vieta's Formulas are the key to this problem. Let $$r_1, \cdots, r_n$$ be the roots. Then define \begin{align} A &= \sum_{i=1}^n r_i \\ B &= \sum_{1 \le i_2 < i_2 \le n} r_{i_1}r_{i_2} \\ C &= \prod_{i=1}^n r_i . \end{align} By Vieta's Formulas, we know that $$A, B, C \in \{\pm 1\}.$$ Now $$\sum_{i=1}^n r_i^2 = A^2 - 2B = 1-2B \ge 0 \implies B = -1.$$ But then by AM-GM, we have $$\frac{3}n = \frac{1}n \sum_{i=1}^n r_i^2 \ge \left(C^2 \right)^{1/n} = 1$$ which cannot happen for $$n \ge 4$$.