Test to determine if a polynomial has only real roots?

Given a polynomial $p(x)=x^n + c_{n-1} x^{n-1} + \cdots + c_0$ with real coefficients $c_{n-1}, \ldots, c_0$, is there an efficient method to determine whether all roots to the polynomial are real and not complex? If it helps, you may assume all of its $n$ roots are distinct.

I know, for the quadratic case, the discriminant $c_1^2 - 4c_0>0$ is necessary and sufficient to determine if all roots are real.

Solution 1:

Let's start with a trivial fact: A polynomial of degree $n$ has a total of $n$ roots. Furthermore, let's assume that all the roots are distinct and that the total number of real roots of the polynomial of degree $n$ is $X$. Hence, if $X = n$, all the roots of the polynomial are real. The challenge, however, is to find $X$. We can do so using Sturm's Theorem!

The theorem is as follows:

Take any squarefree polynomial $p(x)$, and any interval $(a, b)$ such that $p_i(a), p_i(b) \neq 0$, for any $i$. Let $p_0(x), . . . p_m(x)$ denote the Sturm chain corresponding to $p(x$). For any constant $c$, let $\sigma(c)$ denote the number of changes in sign in the sequence $p_0(c), . . . p_m(c)$. Then $p(x)$ has $\sigma(a) − \sigma(b)$ distinct roots in the interval $(a, b)$.

(Taken from here)

Let's try to understand the above italicized terms:

1. A squarefree polynomial refers to one which has only distinct roots.
2. We can understand a Sturm chain to continue in the following way till $p_i(x) = 0$: $$p_0(x) = p(x)$$ $$p_1(x) = p^\prime(x)$$ $$p_2(x) = -1 \times \text{remainder of} \: (p_0 \div p_1)$$ $$p_3(x) = -1 \times \text{remainder of} \: (p_1 \div p_2)$$ $$\text{...}$$ $$p_m(x) = -1 \times \text{remainder of} \: (p_{m-2} \div p_{m−1})$$
3. Changes in sign refer to going from $+$ to $-$ and vice-versa.

Hopefully, the theorem now makes sense. Simply, it is telling us that $X = \sigma(a) − \sigma(b)$ in the interval $(a,b)$.

If there is still some confusion, the following example may help:

1. Consider the polynomial $p(x) = x^3 - 7x + 7$. Our aim is to find whether it has all real roots.
2. We start by finding its Sturm chain: $$p_0(x) = x^3 - 7x + 7$$ $$p_1(x) = \frac{d}{dx}(x^3 - 7x + 7) = 3x^2 - 7$$ $$p_2(x) = -1 \times \text{remainder of} \: \frac{x^3 - 7x + 7}{3x^2 - 7} = \frac{14x}{3} - 7$$ $$p_3(x) = -1 \times \text{remainder of} \: \frac{3x^2 - 7}{\frac{14x}{3} - 7} = \frac{1}{4}$$ We can stop here because $p_4(x) = 0$.

Note: The remainders that are found can be multiplied by any positive constant to aid calculation. For example $\frac{14x}{3} - 7$ could be multiplied by $3$ to give $14x - 21$. This could now be used as $p_{2}(x)$.

3. Within the interval $(-\infty, \infty)$, we now find the signs of $p_i(a)$ and $p_i(b)$ for $i = \{0, 1, 2, 3 \}$ which is represented in the table below:

4. Hence $X = \sigma(a) − \sigma(b) = 3 - 0 = 3$. Since $X = n$, all the roots are real.

We can check the above result using a more conventional method. Descartes' Rule of Signs guarantees exactly one negative root, which we can call $a$. Consequently, the sum of the remaining roots is $−a$ and their product is $\frac{-7}{a}$, so the remaining roots satisfy the equation

$$x^{2}+ax−\frac{7}{a}=0 \quad (1)$$

This has a positive discriminant if $a<-\sqrt[3]{28}$, giving us $2$ more real roots. However, we also have $x^3−7x+7\to-\infty$ as $x$ decreases without bound. Hence, the negative root is $< -\sqrt[3]{28}$. As a result, the quadratic equation $(1)$ will provide $2$ more real roots matching the result found via the Sturm chain.

(Credit: Oscar Lanzi)

For the purposes of this question, the above answer should suffice. However, I highly recommend that you look up the proof for this theorem without which none of the above may make sense. Cheers!

Edit $1$: $b = \infty \neq -\infty$ in the table above.

Edit $2$: To make this method more effective, we may need to evaluate the sign changes at specific points instead of $(-\infty,\infty)$. The Cauchy or Lagrange upper bounds give explicit limits on the maximum size of all roots (real or complex). By choosing $a$ and $b$ outside of this range, we have $\sigma(a)-\sigma(b)=\sigma(-\infty)-\sigma(\infty)$ i.e. the total number of real roots. (Credit: Michael Burr)