# 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.

• Look up "real root isolation". Mar 7, 2021 at 7:20
• Look up Sturm sequences. Mar 8, 2021 at 14:49
• There are cases where the structure of the coefficients implies that all the roots are real. Do you need a general case or would a more specialized one work? Jul 23, 2021 at 16:17

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

1. 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: 1. 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{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{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)

• I moved my check into the answer, feel free to roll back. Incidentally, the quadratic discriminant found by this method correlates with the standard cubic discriminant and thus this method is a derivation of the cubic discriminant. Jul 23, 2021 at 13:13
• You might want to add information on a bound, such as the Cauchy bound, which can be used to the points to evaluate to find all roots. Jul 23, 2021 at 15:54
• @MichaelBurr I am not the most experienced individual in that field. If you have information that you believe would be worthwhile to add, I recommend that you edit the answer above, I would be more than happy to credit you!
– user905694
Jul 23, 2021 at 16:01
• I created an edit, please feel free to incorporate into the text elsewhere (or to revert). Jul 23, 2021 at 16:12