Only 12 polynomials exist with given properties

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 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)$$