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

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

How do I solve it?

• 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)$ – Dan Uznanski Mar 16 at 9:00
• 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. – John Omielan Mar 16 at 9:09
• Have you tried solving the problems explicitly for low degrees and looking for patterns that you can try to prove? – Henning Makholm Mar 16 at 9:48
• 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? – John Omielan Mar 16 at 10:30

## 1 Answer

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.