Find all polynomials with coefficients from set $\{-1,1\}$ and which have all their roots real.

What I have tried:

Assume polynomial is $a_{n}x^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots +a_{0}=0$ and $a_{i}\in \{-1,1\}$ for $i=0,1,2,3,4,\cdots ,n$. Let its roots be $x=r_{i}$ for $i=1,2,3,\cdots n$. Then

$\begin{aligned}\sum r_{i}=-\frac{a_{n-1}}{a_{n}}=\pm 1\\\\ \mathop{\sum}_{i<j}r_{i}r_{j}=+\frac{a_{n-2}}{a_{n}}=\pm 1\\\\ \mathop{\sum}_{i<j<k}r_{i}r_{j}r_{k}=+\frac{a_{n-2}}{a_{n}}=\pm 1\\\\ \prod r_{i}=(-1)^n\frac{a_{0}}{a_{n}}\end{aligned}$

How do I solve it?

  • $\begingroup$ Are you actually required to use that form? It'd be a lot easier - to the point of triviality - to use the roots form $a\product_k(x-x_k)$ $\endgroup$ – Dan Uznanski Mar 16 at 9:00
  • $\begingroup$ Note if $a_n = -1$, you can multiply the equation by $-1$ and still get the same roots. Thus, WLOG, you can set $a_n = 1$, with this at least simplifying your equations slightly. Also, your triple product formula should have $-\frac{a_{n-3}}{a_n}$ in the middle part. $\endgroup$ – John Omielan Mar 16 at 9:09
  • 2
    $\begingroup$ Have you tried solving the problems explicitly for low degrees and looking for patterns that you can try to prove? $\endgroup$ – Henning Makholm Mar 16 at 9:48
  • $\begingroup$ I haven't solved it, but for $n \ge 2$, I have determined so far that, if you let $a_n = 1$, then $a_{n-2} = -1$, plus that $\sum r_i^2 = 3$. Are you able to see why this is so? $\endgroup$ – John Omielan Mar 16 at 10:30

WLOG, let $a_n = 1$. Also, let $r_1,\ldots,r_n$ be the roots of the polynomial.

As you noted, $\displaystyle\sum_{k = 1}^{n}r_k = -a_{n-1}$, $\displaystyle\sum_{1 \le k < \ell \le n}r_kr_{\ell} = a_{n-2}$, and $\displaystyle\prod_{k = 1}^{n}r_k = (-1)^na_0$. Hence,

$$\displaystyle\sum_{k = 1}^{n}r_k^2 = \left(\sum_{k = 1}^{n}r_k\right)^2-2\left(\sum_{1 \le k < \ell \le n}r_kr_{\ell}\right) = a_{n-1}^2-2a_{n-2} = 1-2a_{n-2} = \begin{cases}3 & \text{if} \ a_{n-2} = -1 \\ -1 & \text{if} \ a_{n-2} = 1 \end{cases}.$$

Since all the roots are real, $\displaystyle\sum_{k = 1}^{n}r_k^2 \ge 0$. Hence, we must have $a_{n-2} = -1$ and thus $\displaystyle\sum_{k = 1}^{n}r_k^2 = 3$.

Trivially, we then have $\displaystyle\sum_{k = 1}^{n}|r_k|^2 = \sum_{k = 1}^{n}r_k^2= 3$, as well as $\displaystyle\prod_{k = 1}^{n}|r_k| = \left|\prod_{k = 1}^{n}r_k\right| = \left|(-1)^na_0\right| = 1$.

So by the RMS-GM inequality, we have $$\displaystyle 1 = \left(\prod_{k = 1}^{n}|r_k|\right)^{1/n} \le \left(\dfrac{1}{n}\sum_{k = 1}^{n}|r_k|^2\right)^{1/2} = \sqrt{\dfrac{3}{n}}.$$

Therefore, we must have $n \le 3$. It is easy to check that the only solutions are:

$x-1$, $x+1$, $x^2-x-1$, $x^2+x-1$, $x^3-x^2-x+1$, $x^3+x^2-x-1$, and their negatives.


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.