Sturm's Theorem

Ask someone to find the roots of $x^5 - x - 1$ and they will reach for a calculator, a graph, or Newton's method — and still not be sure they found every real root. Ask a different question instead: how many real roots does it have between, say, $1$ and $2$? That question has an exact, computable answer, and you never have to solve the equation to get it.

In 1829 the French mathematician Jacques Charles François Sturm found a way to answer exactly that. Build a short chain of polynomials from $p(x)$ and its derivative, evaluate them at the two endpoints of an interval, and simply count how many times the signs change. The difference between the two counts is the exact number of distinct real roots inside — not an estimate, not a probability, a hard guarantee.

It is one of the cleanest examples in mathematics of turning a "search" problem (find the root) into a "counting" problem (how many are there) that a machine can answer with nothing but arithmetic and sign comparisons.

Below is the fixed polynomial $p(x) = x^3 - 4x$, which factors as $x(x-2)(x+2)$ — so its real roots are exactly $-2$, $0$ and $2$. Pick an interval $[a, b]$ and the demo builds the full Sturm chain for $p$, evaluates every polynomial in the chain at $a$ and $b$, and counts sign changes on each side.

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label for="a">{{label_a}}</label>
  <input type="range" id="a" min="-4" max="4" step="0.1" value="-3">
  <span class="val" id="a-val">-3.0</span>
  <label for="b">{{label_b}}</label>
  <input type="range" id="b" min="-4" max="4" step="0.1" value="3">
  <span class="val" id="b-val">3.0</span>
</div>
<div class="line-wrap">
  <svg id="line" viewBox="0 0 400 60" preserveAspectRatio="none"></svg>
</div>
<div class="chain" id="chain"></div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: grid; grid-template-columns: auto 1fr auto; gap: .4rem .6rem; align-items: center; margin-bottom: .6rem; }
.controls label { font: 600 13px system-ui, sans-serif; color: #1d3557; }
.controls input[type="range"] { width: 100%; }
.controls .val { font: 700 13px ui-monospace, monospace; color: #1d3557; min-width: 2.6em; text-align: right; }
.line-wrap { margin: .3rem 0 .8rem; }
#line { width: 100%; height: 56px; display: block; }
.chain { display: flex; flex-direction: column; gap: .3rem; margin-bottom: .6rem; font: 13px ui-monospace, monospace; }
.chain-row { display: grid; grid-template-columns: 1fr auto auto; gap: .5rem; align-items: center;
             padding: .3rem .5rem; background: #f4f6f8; border-radius: 6px; }
.chain-row .poly { color: #1d3557; }
.chain-row .sign { font-weight: 700; padding: .05rem .4rem; border-radius: 4px; }
.sign.pos { background: #d7f5df; color: #0a7d33; }
.sign.neg { background: #fde3e3; color: #c92f3c; }
.sign.zero { background: #eee; color: #888; }
.status { font-size: 1rem; font-weight: 700; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }

// Code not found

Watch the two sign-change tallies: the count at $a$ minus the count at $b$ is always exactly the number of roots inside $(a, b)$, no matter how you slide the interval. Move the boundary across a root and the tally jumps by exactly one — the chain "feels" every root it crosses, and only the ones it crosses.

The construction behind the chain is almost embarrassingly simple, once you see it:

• Start the chain. Set $p_0 = p$ and $p_1 = p'$, the derivative.
• Keep dividing. For each next term, divide $p_{i-1}$ by $p_i$ and take the negative of the remainder: $p_{i+1} = -\operatorname{rem}(p_{i-1}, p_i)$. This is exactly the Euclidean algorithm for polynomials — the same idea used to find the greatest common divisor of two integers, just with polynomial long division instead.
• Stop at a constant. The chain shrinks in degree every step (division by a lower-degree polynomial guarantees it) and ends when a term becomes a nonzero constant, or the whole process reveals a repeated-root factor to remove first.
• Count sign changes. For a point $x$ that is not a root of any chain polynomial, let $V(x)$ be the number of sign changes when you read $p_0(x), p_1(x), \dots, p_k(x)$ in order (zeros are simply skipped).
• The theorem. For $a < b$ neither a root of $p$, the number of distinct real roots of $p$ in $(a, b)$ equals exactly $V(a) - V(b)$.

Because polynomial division of degree-$n$ polynomials costs only polynomial time, and the chain has at most $n$ terms, the whole procedure runs in polynomial time in $n$ — no factoring, no floating-point root-finding, no risk of missing a root or double-counting one. It gives a certificate: a small number of arithmetic sign checks that prove the exact count.

Turning "find a root" into "count the roots exactly" is more useful than it sounds, because counting is the first step to isolating and certifying:

• Real root isolation: computer algebra systems repeatedly bisect an interval and re-run Sturm's count on each half, shrinking down to intervals that are guaranteed to contain exactly one root — a rigorous starting point for any numerical solver.
• Exact symbolic computation: because every step is polynomial arithmetic with no rounding, Sturm sequences give computer algebra systems a way to reason about real roots with mathematical certainty rather than floating-point approximation.
• Control theory and stability: closely related sign-counting arguments (the Routh–Hurwitz criterion) test whether all roots of a characteristic polynomial lie in the stable half of the plane, without ever solving for them.
• Quantifier elimination: deciding true/false statements about real polynomial inequalities is a core task of cylindrical algebraic decomposition, and it leans on exactly this kind of root-counting machinery.

Anywhere a system needs to know "how many solutions exist here" before it commits to searching for one — the way Newton's method commits to a single starting guess — Sturm's idea of counting through signs is a recurring, certainty-giving tool.

Sturm's theorem is nearly two hundred years old, yet it still captures something computer science keeps rediscovering: sometimes the fastest way to answer "how many" is not to search for each one, but to build a structure — here, a short chain of polynomial remainders — whose signs already know the answer.

The next time you're tempted to hunt for a root numerically and hope you didn't miss one, remember there is an exact, certified count waiting for you first, built from nothing more than division and sign changes — the same quiet arithmetic that powers Euclid's algorithm.