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.

  • 1
    $\begingroup$ Look up "real root isolation". $\endgroup$
    – KReiser
    Mar 7, 2021 at 7:20
  • 2
    $\begingroup$ Look up Sturm sequences. $\endgroup$ Mar 8, 2021 at 14:49
  • 1
    $\begingroup$ 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? $\endgroup$ Jul 23, 2021 at 16:17

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

  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:

enter image description here

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

  • 1
    $\begingroup$ 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. $\endgroup$ Jul 23, 2021 at 13:13
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 23, 2021 at 15:54
  • $\begingroup$ @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! $\endgroup$
    – user905694
    Jul 23, 2021 at 16:01
  • 1
    $\begingroup$ I created an edit, please feel free to incorporate into the text elsewhere (or to revert). $\endgroup$ Jul 23, 2021 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .