# Only 12 polynomials exist with given properties

Prove that there are only 12 polynomials that have

• all real roots, and
• whose coefficients are all $$-1$$ or $$1$$.

(zero coefficients are not allowed, and constant polynomials do not count.)

Two of them are obviously $$x-1$$ and $$x+1$$.

I tried applying Viete's theorems, but could not get anything useful.

• Well also $-x-1$, $-x+1$, $x^2-1$, and $-x^2+1$... Apr 18, 2015 at 2:59
• In that case, $x^2-1$ doesn't work, and neither does $x$, but the constant polynomials $1$ and $-1$ work (they each have zero roots, all real vacuously). Apr 18, 2015 at 3:05
• $b^2 - 4ac > 0$ for the combinations $b = \pm 1, a = \pm1, c = \mp 1$. Then we can account for: $x^2 + x - 1$, $x^2 -x - 1$, $-x^2 + x + 1$, $-x^2 - x + 1$ Apr 18, 2015 at 3:07
• $x^3-x^2-x+1=(x-1)^2(x+1)$. This and its negative brings us up to 12 polynomials so far (the original 2, their negatives, kmeis's four quadratics, and the two constant polynomials). Apr 18, 2015 at 3:12
• Im not sure if the constants count as $(x-1)(x+1)^2$ and its negative produces a satisfactory polynomial. This can be seen from looking at the cubic equation that these are the only 4 cubics. Apr 18, 2015 at 3:16

I will assume that the reader is capable of finding that there are exactly 12 such polynomials in degree $3$ or less, by brute force if necessary.

Assume the degree of such a polynomial $f(x)$ is at least 4 for the sake of contradiction. Let the leading coefficients be $f(x) = x^n - Ax^{n-1} + Bx^{n-2} - C x^{n-3} + Dx^{n-4} + \ldots$. This convention is adopted so that the values $A,B,C,D\in \{\pm 1\}$ are the first four elementary symmetric polynomials in the roots. That is, if $\alpha_1, \alpha_n$ are the $n$ real roots of $f(x)$, we have

• $A = \sum_{i=1}^n \alpha_i =\alpha_1 + \alpha_2 + \ldots + \alpha_n$
• $B = \sum_{1 \le i<j\le n} \alpha_i\alpha_j = \alpha_1\alpha_2 + \alpha_1\alpha_3 + \ldots + \alpha_{n-1}\alpha_n$
• $C = \sum_{1 \le i<j<k\le n}\alpha_i\alpha_j\alpha_k$
• $D = \sum_{1 \le i<j<k<l\le n}\alpha_i\alpha_j\alpha_k\alpha_l$

Remember that $\alpha_i^2 > 0$ holds for all $i$ (nonzero constant term) and all of $A,B,C,D$ square to $1$. We will now use Newton's identities to compute some values that must be positive. \begin{align*} 0 < \sum_{i=1}^n \alpha_i^2 & = A^2-2B = 1-2B\\ 0 < \sum_{i=1}^n \alpha_i^4 & = A^4-4A^2B + 2B^2 + 4AC - 4D\\ & = 3 - 4B + 4AC - 4D \end{align*} In particular, from $0 < 1-2B$ we conclude $B = -1$ and the first sum must be 3. The second sum is thus simplified to $7+4AC-4D$. Next we note the identity $$9 = \left( \sum_{i=1}^n \alpha_i^2 \right)^2 = \sum_{i=1}^n \alpha_i^4 + 2\sum_{1 \le i<j\le n} \alpha_i^2\alpha_j^2$$ then implies $$0 <\sum_{1 \le i<j\le n} \alpha_i^2\alpha_j^2 = \frac{1}{2}\left(9 - \sum_{i=1}^n \alpha_i^4 \right) = \frac{1}{2}\left(9 - (7+4AC-4D)\right) = 1 -2AC + 2D$$ Now, we note that $AC-D \in \{-2, 0, 2\}$, but $0 < 7+4AC-4D$ tells us it cannot be $-2$, and $0< 1 - 2AC+2D$ tells us it cannot be $2$. Thus, it must be $0$, and in particular the above sum simplifies to $1-2AC+2D = 1$. We now perform one final calculation and rearrangement \begin{align*} 3 = 3\cdot 1 & = \left( \sum_{i=1}^n \alpha_i^2 \right) \left(\sum_{1 \le i<j\le n} \alpha_i^2\alpha_j^2\right) = \sum_{1 \le i<j\le n} \alpha_i^4\alpha_j^2 + 3 \sum_{1 \le i<j<k\le n} \alpha_i^2\alpha_j^2\alpha_k^2\\ 0 < \sum_{1 \le i<j\le n} \alpha_i^4\alpha_j^2 & = 3 \left( 1 - \sum_{1 \le i<j<k\le n} \alpha_i^2\alpha_j^2\alpha_k^2\right) \end{align*} This last line is a contradiction, because $\sum_{1 \le i<j<k\le n} \alpha_i^2\alpha_j^2\alpha_k^2$ is (by the fundamental theorem of symmetric polynomials) a polynomial in the coefficients of $f$, and is therefore at least $1$.

• I believe "but 0 < 7+4AC-D" should be "but 0 < 7+4AC-4D" Apr 18, 2015 at 8:24
• What do you think about my simplification? :) Apr 20, 2015 at 5:56

I already accepted @Rolf Hoyer s excellent answer, this is just its simplification, too large for comment, but using the same notation, for the sake of clarity.

• $A = \sum_{i=1}^n \alpha_i =\alpha_1 + \alpha_2 + \ldots + \alpha_n$
• $B = \sum_{1 \le i<j\le n} \alpha_i\alpha_j = \alpha_1\alpha_2 + \alpha_1\alpha_3 + \ldots + \alpha_{n-1}\alpha_n$
• $Z = \prod_{i=1}^n \alpha_i =\alpha_1\alpha_2\ldots\alpha_n$

Since polynomials have coefficients are $-1$ or $1$, than $A$, $B$, and $Z$ must be $-1$ or $1$.

The idea is to express $\sum_{i=1}^n \alpha_i^2$ in terms of $A$ and $B$:

$$\sum_{i=1}^n \alpha_i^2 =\alpha_1^2 + \alpha_2^2 + \ldots + \alpha_n^2 = (\sum_{i=1}^n \alpha_i)^2 - 2*\sum_{1 \le i<j\le n} \alpha_i\alpha_j$$ $$= A^2 - 2B = 1 - 2B = 3$$

Last two steps are based on $A^2 = 1$, and $B$ must be $-1$ since otherwise $\sum_{i=1}^n \alpha_i^2 =1 - 2B$ is negative.

Now, let us apply AM-GM inequality on $\alpha_1^2, \alpha_2^2, \ldots, \alpha_n^2$:

$$3=\sum_{i=1}^n \alpha_i^2 =\alpha_1^2 + \alpha_2^2 + \ldots + \alpha_n^2 \ge n \sqrt[n]{\prod_{i=1}^n \alpha_i^2} = n \sqrt[n] {Z^2} = n \sqrt[n] 1 = n$$

This means $n \le 3$, in other words, polynomials must be of degree 1, 2, or 3, and those were 12 already found by others in the comments to the original question above. They 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$$

$$-(x+1)$$ $$-(x-1)$$ $$-(x^2+x-1)$$ $$-(x^2-x-1)$$ $$-(x^3-x^2-x+1)$$ $$-(x^3+x^2-x-1)$$

• ohoh, i clumsily wrote that, but the intention was to apply arithmetic geometric mean inequality.. i corrected @RolfHoyer Apr 20, 2015 at 6:31
• It's the $n$-th root instead of the square root, that's a nice simplification Apr 20, 2015 at 7:03
• Such a very nice simplification! Apr 22, 2015 at 2:56