The remainders that count the roots

How many real solutions does $x^5 - 5x^3 + x^2 + 3x - 1 = 0$ have? A graph suggests an answer, and the answer a graph suggests is exactly what cannot be trusted: a curve that dips to touch the axis and a curve that dips just past it look the same at any resolution coarse enough to see the whole curve. What the coefficients already know found one exact answer for cubics, the sign of the discriminant, and no such single number works beyond degree three.

In 1829 Charles Sturm found a procedure that works for every degree and every interval, and it is Euclid’s algorithm. Divide the polynomial by its derivative, keep the remainder with its sign reversed, divide the derivative by that, and so on down to a constant. Evaluate the signs of the whole chain at a point and count how often they change. That count drops by one exactly when the point crosses a real root, and at no other time, so the difference between the counts at two ends of an interval is the number of real roots inside it.

The chain, built like a tiling #

The construction is the one the oldest algorithm performs on two lengths, applied to two polynomials. Write $p_0 = p$ and $p_1 = p'$. Divide $p_0$ by $p_1$, getting a quotient and a remainder of lower degree; call the negative of the remainder $p_2$. Divide $p_1$ by $p_2$ and call the negative of that remainder $p_3$. Continue until the remainder is zero. Each step lowers the degree by at least one, so for a polynomial of degree 5 the chain has at most six members.

The only change from Euclid’s own algorithm is the sign. The remainders are the same polynomials, up to that reversal, and the last non-zero one is the greatest common divisor of $p$ and $p'$, exactly as the last non-zero remainder of two whole numbers is theirs. Dividing each member by a positive number changes no signs, so the chain can be kept in whole numbers:

$$p_2 \propto 10x^3 - 3x^2 - 12x + 5, \quad p_3 \propto 171x^2 - 26x - 45, \quad p_4 \propto 14{,}026x - 6{,}741, \quad p_5 \propto 1.$$

The coefficients grow as the degree falls — 14,026 from a polynomial whose largest coefficient was 5 — because each division by a fraction multiplies out its denominators. That growth is the practical cost of the method, and it is why computer algebra systems use a refinement, the subresultant chain, that keeps them in check. The idea is unchanged.

The table is the whole method. At $-\infty$ each polynomial has the sign of its leading term times $(-1)$ to its degree, and the column reads $-, +, -, +, -, +$ — five changes. At $+\infty$ every leading coefficient is positive and the column is all $+$, no changes. So the quintic has exactly five real roots: it has no complex ones at all. The columns in between say where they are: the count drops from 5 to 4 between $-3$ and $-2$, from 4 to 3 between $-1$ and 0, from 3 to 1 between 0 and 1 — two roots there — and from 1 to 0 between 1 and 2.

One entry in the table is 0: $p_2$ vanishes at $x = 1$, since $10 - 3 - 12 + 5 = 0$. A zero is simply skipped when counting changes, and the next section explains why that is always safe for the members after the first.

Why the count moves only at roots #

There are two things to show: the count does not change when $x$ crosses a root of one of the later members, and it drops by exactly one when $x$ crosses a root of $p$ itself.

The first comes from the division that defined the chain. Each step says $p_{k-1} = q_k\,p_k - p_{k+1}$. At a root of $p_k$ this reads $p_{k-1} = -p_{k+1}$: the two neighbours of the vanishing member have opposite signs. Just before the root and just after it, the triple $(p_{k-1}, p_k, p_{k+1})$ reads $(+, ?, -)$ or $(-, ?, +)$, and whatever $p_k$’s sign, the triple contains exactly one change. So crossing a root of a middle member leaves the count where it was. That is why the sign reversal is there: with Euclid’s plain remainders the neighbours would have the same sign at such a point, and the count would jump.

The second is a fact about derivatives. Near a simple root of $p$, the function is increasing if $p' > 0$ and decreasing if $p' < 0$. Either way $p$ and $p'$ have opposite signs just before the root and the same sign just after it. The first pair in the chain loses a sign change as $x$ crosses the root, and nothing else changes, so the count drops by exactly one.

Two consecutive members never vanish at the same point, because a common root of $p_k$ and $p_{k+1}$ would, by the same division identity, be a root of every member back to $p$ and $p'$, and so of their greatest common divisor. When the gcd is a constant that cannot happen. The count is therefore a staircase that steps down by one at each real root of $p$, flat everywhere else — the blue line under the graph above, which the figure evaluated exactly, in whole-number arithmetic, at four hundred points.

Two roots the graph cannot separate #

The polynomial $10{,}000x^4 - 40{,}001x^2 + 40{,}002$ factors as $(x^2 - 2)(10{,}000x^2 - 20{,}001)$, so its positive roots are $\sqrt 2 \approx 1.414214$ and $\sqrt{2.0001} \approx 1.414249$. On the interval from 1.3 to 1.5 its graph looks like a parabola resting on the axis at one point. It is not. It crosses the axis, dips below it by 0.000025, and crosses back, all within a stretch of 0.000035.

No plot at a sensible scale can show that, and a program that looks for sign changes of $p$ on a grid of four hundred points misses it too, because both crossings fall between the same two grid points, where $p$ is positive at each. The Sturm count at the two ends of the interval says 2 and 0, two roots, not one and not none — and it says so from the signs of five polynomials at two points, with no resolution involved at all.

That is the sense in which the count is exact and the graph is not. A tangency, a pair of close crossings and a near miss look the same from a distance, and they are three different answers to the question of how many roots there are. Sturm’s chain tells them apart at any distance.

The third case is the near miss, and $x^4 - 2x^2 + x + 3$ is a mild one: its graph sags towards the axis near $x = -1$ but stays about 0.94 above it. The chain’s count is 2 at both ends of the interval, and indeed at $-\infty$ and $+\infty$, so there is no real root anywhere. The two sign changes that never go away are the two conjugate pairs of complex roots, which the chain counts as nothing: Sturm’s theorem sees only the real line, and says nothing about where the complex roots are, only that they are not real.

When the chain stops early #

Euclid’s algorithm on $x^3 - 3x + 2$ and its derivative $3x^2 - 3$ stops after one division. The derivative, scaled, is $x^2 - 1$; the remainder of $x^3 - 3x + 2$ on division by it is $-2x + 2$, which reversed and scaled is $x - 1$; and $x - 1$ divides $x^2 - 1$ exactly. The chain ends on a polynomial of degree one, not a constant.

That ending is information. The last member is the greatest common divisor of $p$ and $p'$, and a polynomial shares a factor with its derivative exactly when it has a repeated root: here $x^3 - 3x + 2 = (x - 1)^2(x + 2)$, and 1 is a double root. So the first thing Sturm’s chain reports is whether any root repeats, and it reports it by the same test that tells two whole numbers whether they share a factor.

The count still works, with one change in what it counts. Every member of the chain is divisible by the gcd, and dividing it out produces a chain for $(x - 1)(x + 2)$, whose roots are the distinct roots of $p$; dividing by the gcd flips all the signs together on one side of 1, which leaves the number of changes unchanged. So the drop from 2 to 0 says two distinct real roots, $-2$ and 1, with the double one counted once.

Finding them by counting them #

A count in any interval is enough to find every root. Start with an interval guaranteed to contain all of them — Cauchy’s bound says no root of $x^5 - 5x^3 + \cdots$ is larger in size than 1 plus the largest coefficient after the first, which is 6, so $[-8, 8]$ will do. Count; halve any interval whose count is two or more; count the halves; repeat. After five rounds each root is alone in an interval with rational endpoints, and the two close roots near 0.4 and 0.7 were the last to be separated.

From there any method will do. Bisection on a sign change of $p$ is now safe, because each interval contains exactly one simple root; Newton’s method, which can wander into another root’s basin when started carelessly, has nowhere else to go once its starting interval holds one root and $p'$ keeps a sign on it. This is how computer algebra systems isolate real roots with certainty, and the certainty is the point: no root was computed to do the isolating, only counted, so the result does not depend on how accurately anything was computed.

A continued fraction of polynomials #

The chain has a second reading that ties it back to the rectangle. Euclid’s algorithm on two whole numbers is the continued fraction of their ratio, as a fraction that never closes showed. On two polynomials it is the continued fraction of their ratio too:

$$\frac{p}{p'} = q_1 - \cfrac{1}{q_2 - \cfrac{1}{q_3 - \cdots}},$$

with the minus signs coming from the reversed remainders. The quotients $q_k$ are polynomials, usually of degree one, and the sign changes in the chain count how often the rational function $p'/p$ jumps from $-\infty$ to $+\infty$ as $x$ increases — which is once at each real root of $p$, because near a root $p'/p$ behaves like $1/(x - r)$. Cauchy called that number the index of the function over the interval.

The same index, computed for a different pair of polynomials, answers a question engineers ask every day: does a system described by a polynomial have all its roots in the left half of the complex plane, so that it settles rather than blowing up? Routh’s criterion of 1876 and Hurwitz’s of 1895 decide it by exactly this kind of chain, built from the polynomial’s even and odd parts, and a sign-change count along it. A test for the stability of a feedback loop is Euclid’s algorithm with its signs reversed, and it is taught to control engineers under Routh’s name without mention of Sturm or Euclid.

The coarser count that came first #

Sturm’s count has an older, cheaper cousin that reads signs too, but the signs of the coefficients rather than of a chain. Descartes’ rule of signs, from 1637, says that the number of positive roots is at most the number of sign changes in the list of coefficients, and differs from it by an even number. For $x^5 - 5x^3 + x^2 + 3x - 1$ the coefficients run $+, -, +, +, -$ once the zero is dropped: three changes, so three positive roots or one. Replacing $x$ by $-x$ gives $-x^5 + 5x^3 + x^2 - 3x - 1$, with two changes, so two negative roots or none.

On this quintic Descartes happens to be exact — three positive roots and two negative — but only because every root is real. On $x^2 - x + 1$ the rule allows two positive roots, and there are none; it can only ever offer an upper bound and a parity. The difference between the two methods is the difference between a count of changes in a fixed list and a count that moves as $x$ moves: Descartes reads one column, at the point where every power of $x$ is compared, and Sturm reads a column at every point, with a chain designed so that the columns can only differ at roots.

The derivative is in the chain for the reason Rolle’s theorem gives. Between two real roots of $p$ there is always a root of $p'$, so the real roots of the derivative interleave with those of the polynomial; the roots of the slope stay inside proves the complex version, where the derivative’s roots lie in the convex hull of the polynomial’s. Sturm’s chain is built so that only that first relationship can ever move the count: wherever the later members’ roots fall, the neighbours of a vanishing member disagree in sign, and the bookkeeping of the whole chain reduces to what $p$ and $p'$ do at a root of $p$.

What the steps and the table cannot show #

The step function is sampled. The blue staircases are evaluated exactly, in whole numbers, but at four hundred points, and between two samples the count could in principle do anything. The theorem says it does not — it steps down only at roots — and the figures were checked against every root found by an independent method, but a picture of a staircase is still a picture of four hundred values.

The chain says nothing about complex roots. The two sign changes that persist for $x^4 - 2x^2 + x + 3$ at every point are not a count of anything; its four complex roots are simply absent from the difference the theorem takes, and the chain does not say where they are. Locating complex roots needs a different argument, the argument principle, which counts how often a closed curve winds round zero.

And the whole-number coefficients grow. The chain for a quintic with coefficients below 6 ends in a member with coefficients over fourteen thousand, and for polynomials of degree 50 the plain chain is hopeless in practice. The refinements that tame it are not drawn here, and the method’s success on the examples is a statement about small degree.

Still open: how many real roots a system with few terms can have #

Descartes’ rule of signs, the older and coarser count, says that a polynomial with $k$ non-zero terms has at most $k - 1$ positive roots, whatever its degree — $x^{100} - 3x^{57} + 1$ has at most two, however high the powers. The bound depends on the number of terms, not on the degree, and it is sharp.

For systems of polynomial equations in several unknowns, the analogous question is open. Kushnirenko conjectured in the 1970s that the number of positive solutions of $n$ equations in $n$ unknowns is bounded by a product of term counts, as in one variable; the conjecture was disproved in 2003 by Haas, with a pair of equations in two unknowns having more solutions than it allowed. Khovanskii’s theorem gives an upper bound that depends only on the number of terms, but it is astronomically large, and nobody knows whether the true bound grows polynomially or exponentially in the number of terms. The one-variable case has an exact count and a sharp bound; the several-variable case has neither.

The gap matters in practice. Problems in robotics, chemistry and the design of mechanisms reduce to systems whose equations have few terms and high degree, and the number of real solutions is the number of physically possible configurations. Sturm’s chain has no counterpart that counts them exactly, and the bounds available are too large to be useful — so those problems are solved by numerical homotopy methods that find every complex solution and then check which are real, the method this essay’s figures used as their independent check.

Counting where locating was expected #

Sturm’s theorem answers “how many” by never asking “where”. It evaluates signs of polynomials at a handful of points and reads off a count that no plot could guarantee. The method is Euclid’s, run on polynomials instead of lengths, with one sign changed so that the middle of the chain can never move the count.

The same division that decides who wins Euclid’s game by the parity of its runs decides here how many times a curve crosses a line, and where two roots run into each other is the moment the chain’s last member stops being a constant.

When the objects are hard to find, count them first — and look for an invariant that changes by exactly one each time one of them is passed. Here the invariant is a number of sign changes, the objects are real roots, and the counting turns into finding by halving intervals until each holds one. The same move counts the lattice points on a circle by a formula that never lists them, and it counts crossings in the linking of two loops by adding signs; Sturm’s version is the one where the sum is taken down a chain of remainders.