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

Question

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

Answer 1

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