Counting Real Roots Without Solving: Sturm's Theorem

How many real roots does the polynomial $x^5 - 3x^2 + 1$ have? Not how many complex roots — the Fundamental Theorem of Algebra already answers that (five, with multiplicity). The real question is subtler: of those five, how many live on the real line?

Remarkably, there is an algorithm from 1829 that answers this exactly — without finding a single root, without graphing, and without any approximation. It is Sturm's Theorem, and it remains one of the most elegant results in classical algebra.

The Problem

The Fundamental Theorem of Algebra tells us a degree-$n$ polynomial has exactly $n$ roots in $\mathbb{C}$. But it gives no procedure to determine how many of them are real, or where they lie. Sturm's theorem fills exactly this gap:

Given a real polynomial $p$, it counts the number of distinct real roots in any interval $(a, b]$ — and can isolate each root in an arbitrarily small interval.

The Sturm Sequence

Start with a square-free polynomial $p$ (if $p$ has repeated roots, just divide by $\gcd(p, p')$ first). Build a chain of polynomials using a sign-flipped version of the Euclidean algorithm:

$p_0 = p, \qquad p_1 = p', \qquad p_{i+1} = -\operatorname{rem}(p_{i-1}, p_i).$

In words: each new term is the negative of the remainder when you divide the previous two. Keep going until you reach a nonzero constant.

The Counting Rule

For a real number $t$, let $V(t)$ be the number of sign changes in the list

$p_0(t),\; p_1(t),\; p_2(t),\; \dots$

(skipping any zeros). Then the number of distinct real roots in $(a, b]$ is:

$\#\{\text{real roots in } (a,b]\} = V(a) - V(b).$

Taking $a = -\infty$ and $b = +\infty$ counts all real roots. At infinity, the sign of each $p_i$ is just the sign of its leading term.

Why does it work?

As $t$ increases past a root of $p$, the leading pair $(p, p')$ loses exactly one sign change. The construction guarantees that passing a root of any inner term $p_i$ produces in . So decreases by exactly each time crosses a real root — counting them precisely.

A Worked Example

Let's count the real roots of $p(x) = x^3 - 3x + 1.$

Step 1 — Build the Sturm sequence.

$p_0 = x^3 - 3x + 1, \qquad p_1 = p_0' = 3x^2 - 3.$

Dividing $p_0$ by $p_1$ leaves remainder $-2x + 1$, so $p_2=-(-2x+1)$

Dividing $p_1$ by $p_2$ leaves remainder $-\tfrac{9}{4}$, so (a positive constant).

Step 2 — Count all real roots (signs at $\pm\infty$).

$\#\text{real roots} = V(-\infty) - V(+\infty) = 3 - 0 = 3.$

So all three roots are real! (Confirmed by the discriminant $\Delta = 81 > 0$.)

Step 3 — Locate them. How many lie in $(0, 1]$?

$\#\text{roots in } (0,1] = V(0) - V(1) = 2 - 1 = 1.$

Exactly one root lies in $(0, 1]$. Indeed, the three roots are approximately $-1.879,\; 0.347,\; 1.532$ — and only $0.347$ falls in that interval. ✓

What Sturm Misses: Multiplicity

There is one subtlety that trips up everyone the first time:

Sturm's theorem counts each real root only once, regardless of its multiplicity.

For $p(x) = (x-1)^2(x+2)$, Sturm reports 2 real roots (the values $x=1$ and $x=-$), not 3. To count real roots , two classical tools complete the picture.

Tool 1 — Square-free decomposition (separating roots by multiplicity)

All repeated-root information lives in $\gcd(p, p')$: a root of multiplicity $m$ in $p$ has multiplicity $m-1$ in $p^{\mathrm{\prime }}$, so it survives in the gcd. Writing

$p(x) = a_1(x)^1 \cdot a_2(x)^2 \cdot a_3(x)^3 \cdots$

with each $a_k$ square-free (e.g. via Yun's algorithm, just repeated gcd's), the factor $a_k$ collects exactly the roots of multiplicity $k$. Then:

$\#\{\text{real roots with multiplicity}\} = \sum_{k\ge 1} k \cdot \big(\text{distinct real roots of } a_k\big),$

and each "distinct real roots of $a_k$" is found by ordinary Sturm (each $a_k$ is square-free).

Tool 2 — The Budan–Fourier theorem (counts with multiplicity directly)

Instead of Sturm's special chain, use the successive derivatives $p,\,p',\,p'',\,\dots,\,p^{(n)}$. If is the number of sign changes in that list, then the number of real roots in , , is

$V(a) - V(b) - (\text{a non-negative even number}).$

The parity is always correct, so it pins the count down up to an even slack.

Worked example: $p(x) = x^3 - 3x + 2 = (x-1)^2(x+2)$

Square-free decomposition. $\gcd(p,p') = x-1$, and $p/(x-1) = (x-1)(x+2)$ is the square-free part. Sturm on it gives real roots.

Total with multiplicity $= 1 + 2 = 3.$

Budan–Fourier cross-check. $p=x^3-3x+2,\ p'=3x^2-3,\ p''=6x,\ p'''=6$. Signs give and , so the count with multiplicity is . ✓ The double root is counted — exactly what Sturm does not do.

Complete Classification of a Cubic

A real cubic $p(x) = ax^3 + bx^2 + cx + d$ (with $a\neq0$) admits a remarkably clean classification, because its single

$x_0 = -\dfrac{b}{3a}, \qquad p''(x_0) = 0,$

is also its center of symmetry — and any triple root must sit exactly there.

Two facts drive everything:

1. A real cubic always has at least one real root (odd degree), so the "0 real roots" case is impossible.
2. The discriminant $\Delta = 18abcd - 4b^3d + b^2c^2 - 4ac^3 - 27a^2d^2$ detects multiple roots: iff has a repeated root.

Notes.

• When Sturm gives 2, degree 3 forces the pattern $2+1$ — no extra test needed.
• The triple-root test only truly needs $p(x_0)=0$ and $p'(x_0)=0$; the condition is automatic at the inflection point.

Examples. Triple root: $(x-1)^3 = x^3 - 3x^2 + 3x - 1$ with and . Double+simple: . Three distinct: . One real + two complex: (here , but ).

Quartics: Degree 4

For $p(x) = ax^4 + bx^3 + cx^2 + dx + e$, two things change.

• Parity. Degree 4 is even, and complex roots come in conjugate pairs, so the number of real roots counted with multiplicity is always even: $0$, $2$, or $4$.
• No single-point trick. Unlike the cubic, a quartic has (in general) two inflection points and no single center of symmetry, so the elegant "inflection-point" shortcut does not generalize. Instead, use the full toolkit: Sturm for the distinct count, square-free decomposition / Budan–Fourier for multiplicities, and the discriminant for a quick nature-of-roots check.

Sturm still works — worked example $p(x) = x^4 - 5x^2 + 4$

This factors as $(x-1)(x+1)(x-2)(x+2)$, so we expect 4 distinct real roots.

$p_0 = x^4 - 5x^2 + 4,\quad p_1 = 4x^3 - 10x,\quad p_2 = \tfrac52 x^2 - 4,\quad p_3 = \tfrac{18}{5}x,\quad p_4 = 4.$

$\#\text{real roots} = 4 - 0 = 4.$ ✓ All four roots are real and distinct.

Quick classification by discriminant

Define the discriminant $\Delta$ together with the auxiliary quantities

$P = 8ac - 3b^2,\qquad D = 64a^3e - 16a^2c^2 + 16ab^2c - 16a^2bd - 3b^4,$

$\Delta_0 = c^2 - 3bd + 12ae,\qquad R = b^3 + 8a^2d - 4abc.$

For the example above, $P = 8(1)(-5) - 0 = -40 < 0$ and $D = 64(4) - 16(25) = -144 < 0$ with → , matching Sturm. ✓

Multiplicities for quartics

As with the cubic, recover multiplicities by combining Sturm with square-free decomposition (or Budan–Fourier). The possible real-root multiplicity patterns are the partitions of the real part of the root multiset:

Sturm alone cannot separate these — the discriminant table above (or a square-free decomposition) resolves which pattern actually occurs.

Why It Still Matters

For everyday computation, methods based on Descartes' Rule of Signs are faster. But Sturm's theorem has a unique virtue: it works over any real closed field, which makes it foundational for the theory of quantifier elimination and decidability in the first-order theory of the reals. It is also the oldest real-root isolation algorithm — the ancestor of the root-finders inside modern computer algebra systems.

Not bad for an idea from 1829.

References

• J. C. F. Sturm, Mémoire sur la résolution des équations numériques (1835).
• S. Basu, R. Pollack, M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer (2006).
• H. Cohen, A Course in Computational Algebraic Number Theory, Springer.
• Sturm's theorem — Wikipedia
• Quartic function (nature of the roots) — Wikipedia