A polynomial $a_0x^n+a_1x^{n-1}+…+a_{n-1}x+a_n$,$a_i\in\{-1,1\}$ has all its roots real, find maximum degree possible and number of such polynomials.

algebra-precalculusnumber theorypolynomials

For polynomials of the form $$a_0x^n+a_1x^{n-1}+…+a_{n-1}x+a_n$$ where $a_i\in\{-1,1\}$ for $i=0,1…n$ having all its roots real, find the maximum degree possible as well as number of such polynomials.

$4$ linear polynomials are possible and $4$ quadratic polynomials are possible but how to comment on cubic and higher degree polynomials? Still I tried as follows:

Let $f(x)=ax^3+bx^2+cx+d$, so discriminant of $f’(x)$ comes out to be $b^2-3ac$ and since it must be positive(otherwise only one root will be there for the cubic) I got $a=1,c=-1$ or $a=-1,c=1$ where $b$ can be $1$ as well as $-1$. So roots of $f’(x)$ are $\frac{-b\pm1}{3a}$. Now checking the sign of $f(x)$ on these values seems to be a very tedious task. Also how to check higher degree polynomials. Is there a better way out?

Best Answer

For low degrees, you can easily check this by brute force (there are only $2^{d+1}$ possible choices of $a$, where $d$ is the degree). So I did, and for cubic polynomials, you get the following four polynomials: $$ \begin{bmatrix} -1& -1& 1& 1\\ -1& 1 &1& -1\\ 1& -1 &-1& 1\\ 1& 1 &-1& -1 \end{bmatrix} $$ Here, each row corresponds to a choice of $[a_0, a_1,a_2,a_3]$, such that the corresponding polynomial has only real roots. I also checked quartic and quintic polynomials, and there no such polynomials that satisfy your condition. See my (rudimentary) matlab code below.

Edit: In fact, for each degree, there are only 2 possible polynomials you have to evaluate. Equation (1) in

A Sufficient Condition for All the Roots of a Polynomial To Be Real David C. Kurtz

States a necessary condition for a polynomial to have real roots (note the differing notation in this paper). When all coefficients are $\{ \pm 1\}$, this equation states that $a_{i-1}$ and $a_{i+1}$ should have different signs. Thus, we may search for a polynomial with constant term $a_n = 1$ (problem is invariant under real unit scaling). Then the paper provides the signs of $a_{n-2} = -1$, $a_{n-4} = 1$, $a_{n-6} = -1$ etc. This determines half of the coefficients. For the remaining half, you can choose one of them, which fixes then all of the coefficients via the same equation in the paper. Then it remains to investigate the roots of those two polynomials.

polyDegree = 5;
P = [ones(1,polyDegree+1), -ones(1,polyDegree+1)];
P = perms(P); P = P(:,1:polyDegree+1);
P = int32(unique(P,"rows"));

validPolyCoeffs = [];
for j = 1:size(P,1)
    currentPerm = P(j,:);
    R = roots(double(currentPerm'));
    imagParts = imag(R);
    if sum(abs(imagParts)) < 10^-6
        validPolyCoeffs = [validPolyCoeffs; currentPerm];
    end
end
Related Question