Introduction

Ask someone to find the roots of x5−x−1x^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, 11 and 22? 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)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.

The Chain in Action

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

<p class="hint">The polynomial is fixed at p(x) = x^3 - 4x, with roots at -2, 0 and 2. Slide the two handles to pick an interval [a, b] and watch the Sturm chain count the sign changes at each end.</p>
<div class="controls">
  <label for="a">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">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Fixed demo polynomial p(x) = x^3 - 4x = x(x-2)(x+2), real roots at -2, 0, 2.
const P = [0, -4, 0, 1]; // x^3 - 4x, roots at -2, 0, 2

function degree(p) {
  for (let i = p.length - 1; i >= 0; i--) if (Math.abs(p[i]) > 1e-9) return i;
  return -1;
}
function trim(p) {
  const d = degree(p);
  return d < 0 ? [0] : p.slice(0, d + 1);
}
function deriv(p) {
  const d = degree(p);
  if (d <= 0) return [0];
  const out = [];
  for (let i = 1; i <= d; i++) out.push(p[i] * i);
  return out;
}
// Polynomial long division a / b, returns only the remainder.
function divmod(a, b) {
  a = trim(a.slice());
  b = trim(b.slice());
  const db = degree(b);
  let rem = a.slice();
  while (degree(rem) >= db && degree(rem) >= 0) {
    const dr = degree(rem);
    const coeff = rem[dr] / b[db];
    const shift = dr - db;
    for (let i = 0; i <= db; i++) rem[i + shift] -= coeff * b[i];
    rem = trim(rem);
  }
  return rem;
}
// Build the Sturm chain -- p0=p, p1=p', p_(i+1) = -rem(p_(i-1), p_i) -- until it hits a nonzero constant.
function buildChain(p) {
  const chain = [trim(p.slice()), trim(deriv(p))];
  let i = 1;
  while (degree(chain[i]) >= 0) {
    const r = divmod(chain[i - 1], chain[i]).map((c) => -c);
    if (degree(r) < 0) break;
    chain.push(trim(r));
    i++;
    if (i > 10) break;
  }
  return chain;
}
function evalP(p, x) {
  let r = 0;
  for (let i = p.length - 1; i >= 0; i--) r = r * x + p[i];
  return r;
}
// Count sign changes in the chain values at x, skipping exact zeros.
function signVariations(chain, x) {
  const vals = chain.map((p) => evalP(p, x));
  const signs = [];
  for (const v of vals) { if (Math.abs(v) > 1e-9) signs.push(v > 0 ? 1 : -1); }
  let changes = 0;
  for (let i = 1; i < signs.length; i++) if (signs[i] !== signs[i - 1]) changes++;
  return { changes, vals };
}

function fmtPoly(p) {
  const d = degree(p);
  if (d < 0) return '0';
  const parts = [];
  for (let i = d; i >= 0; i--) {
    const c = p[i];
    if (Math.abs(c) < 1e-9) continue;
    const coeff = Math.abs(c - Math.round(c)) < 1e-6 ? Math.round(c) : c.toFixed(2);
    let term;
    if (i === 0) term = `${coeff}`;
    else if (i === 1) term = `${coeff}x`;
    else term = `${coeff}x^${i}`;
    parts.push((parts.length === 0 ? '' : (c < 0 ? '- ' : '+ ')) + term.replace('-', ''));
  }
  return parts.join(' ') || '0';
}

const CHAIN = buildChain(P);

function render() {
  const a = parseFloat(document.getElementById('a').value);
  const b = parseFloat(document.getElementById('b').value);
  document.getElementById('a-val').textContent = a.toFixed(1);
  document.getElementById('b-val').textContent = b.toFixed(1);

  const lo = Math.min(a, b);
  const hi = Math.max(a, b);

  const va = signVariations(CHAIN, lo);
  const vb = signVariations(CHAIN, hi);
  const count = va.changes - vb.changes;

  const chainDiv = document.getElementById('chain');
  chainDiv.innerHTML = '';
  CHAIN.forEach((p, idx) => {
    const row = document.createElement('div');
    row.className = 'chain-row';
    const sA = va.vals[idx], sB = vb.vals[idx];
    const cls = (v) => Math.abs(v) < 1e-9 ? 'zero' : (v > 0 ? 'pos' : 'neg');
    const lbl = (v) => Math.abs(v) < 1e-9 ? '0' : (v > 0 ? '+' : '−');
    row.innerHTML =
      '<span class="poly">p' + idx + '(x) = ' + fmtPoly(p) + '</span>' +
      '<span class="sign ' + cls(sA) + '">' + i18nFmt('at %x%:', { x: lo.toFixed(1) }) + ' ' + lbl(sA) + '</span>' +
      '<span class="sign ' + cls(sB) + '">' + i18nFmt('at %x%:', { x: hi.toFixed(1) }) + ' ' + lbl(sB) + '</span>';
    chainDiv.appendChild(row);
  });

  // Draw the number line, mark the three real roots, and highlight the chosen interval.
  const svg = document.getElementById('line');
  const W = 400, H = 60, margin = 20;
  const X0 = -4.2, X1 = 4.2;
  const toPx = (x) => margin + ((x - X0) / (X1 - X0)) * (W - 2 * margin);
  const roots = [-2, 0, 2];
  let html = '<line x1="' + margin + '" y1="30" x2="' + (W - margin) + '" y2="30" stroke="#c8ced4" stroke-width="2"/>';
  roots.forEach((r) => {
    const inside = r > lo + 1e-9 && r < hi - 1e-9;
    html += '<circle cx="' + toPx(r) + '" cy="30" r="5" fill="' + (inside ? '#0a7d33' : '#c8ced4') + '"/>';
    html += '<text x="' + toPx(r) + '" y="48" font-size="11" text-anchor="middle" fill="#555">' + r + '</text>';
  });
  html += '<rect x="' + toPx(lo) + '" y="26" width="' + (toPx(hi) - toPx(lo)) + '" height="8" fill="#1d3557" opacity="0.18" rx="3"/>';
  html += '<circle cx="' + toPx(lo) + '" cy="30" r="4" fill="#1d3557"/>';
  html += '<circle cx="' + toPx(hi) + '" cy="30" r="4" fill="#1d3557"/>';
  svg.innerHTML = html;

  document.getElementById('status').textContent =
    i18nFmt('V(a) = %va%, V(b) = %vb%  ->  exact root count in the interval = %n%', { va: va.changes, vb: vb.changes, n: count });
}

document.getElementById('a').addEventListener('input', render);
document.getElementById('b').addEventListener('input', render);
render();
Result
Console

Watch the two sign-change tallies: the count at aa minus the count at bb is always exactly the number of roots inside (a,b)(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 Real Complexity

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

  • Start the chain. Set p0=pp_0 = p and p1=p′p_1 = p', the derivative.
  • Keep dividing. For each next term, divide pi−1p_{i-1} by pip_i and take the negative of the remainder: pi+1=−rem⁡(pi−1,pi)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 xx that is not a root of any chain polynomial, let V(x)V(x) be the number of sign changes when you read p0(x),p1(x),…,pk(x)p_0(x), p_1(x), \dots, p_k(x) in order (zeros are simply skipped).
  • The theorem. For a<ba < b neither a root of pp, the number of distinct real roots of pp in (a,b)(a, b) equals exactly V(a)−V(b)V(a) - V(b).

Because polynomial division of degree-nn polynomials costs only polynomial time, and the chain has at most nn terms, the whole procedure runs in polynomial time in nn — 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sturm-theorem/Content licensed under CC BY-NC 4.0.