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
-
$\begingroup$ I assume you are not counting multiplicity of the roots (i.e. the n roots are all distinct). $\endgroup$– D.B.Commented Dec 25, 2018 at 4:02
-
$\begingroup$ @D.B. yes, even if there are duplicate roots, that's fine $\endgroup$– CuriousMindCommented Dec 25, 2018 at 4:04
-
1$\begingroup$ 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$. $\endgroup$– Robert IsraelCommented Dec 25, 2018 at 4:15
-
$\begingroup$ @RobertIsrael that's right. We can prove all roots have abs value between (0.5,2) as well. $\endgroup$– CuriousMindCommented Dec 25, 2018 at 4:40
-
$\begingroup$ Descartes’ Rule of Signs might be helpful here. $\endgroup$– ClaytonCommented Dec 25, 2018 at 4:49
1 Answer
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$.