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.

  • $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Oct 13 '16 at 23:27
  • 1
    $\begingroup$ Anyway, $1-x-x^2+x^3 = (x+1)(x-1)^2$, so the maximum degree is at least $3$. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.