What the signs allow

The remainders that count the roots ran Euclid’s algorithm on a polynomial and its derivative and got an exact count of the real roots in any interval. On its way it mentioned an older and cheaper rule, the one René Descartes stated in La Géométrie in 1637: write down the signs of the coefficients in order, count how often they change, and that number bounds the positive roots. It differs from the true count by an even number.

Sturm’s chain needs a long division for every member. Descartes’ rule needs only the signs, and it says something the chain cannot say at all: the bound depends on how many terms the polynomial has, not on its degree. $x^{100} - 3x^{57} + 1$ has three terms and two sign changes, so at most two positive roots, and the hundred in the exponent is irrelevant. The rule reads a polynomial as a short list of signs, and a short list of signs can govern a polynomial of any degree.

This essay proves the rule, measures how far it overshoots, and then asks the question it leaves hanging. The rule gives one bound for the positive roots, from the signs of $p(x)$, and another for the negative roots, from the signs of $p(-x)$. Every count each bound allows can be realised by some polynomial with the given signs. Not every pair of counts the two bounds allow together can be realised together, and the first failure comes at degree four.

The proof removes one term at a time #

The proof is an induction on the number of terms, and the figure is its four steps written out for one polynomial. Take $p(x) = x^9 - 5x^5 + 5x^2 - 1$, with four terms and signs $+ - + -$: three changes. Differentiating gives $9x^8 - 25x^4 + 10x$, and the constant term has disappeared. Dividing out the power $x$, which changes no positive root because $x$ is positive, leaves $9x^7 - 25x^3 + 10$: three terms, signs $+ - +$, two changes. Differentiate and divide by $x^2$ and the result is $63x^4 - 75$, with one change; once more and it is a single term, $252$, which never vanishes.

Two facts make each step do its work. Rolle’s theorem: between two roots of a smooth function there is a root of its derivative, so a function with $r$ positive roots has a derivative with at least $r - 1$. Dividing by a positive power of $x$ does not change where the positive roots are, so the member below has at least $r - 1$ positive roots too. And the sign changes can only go down by one or stay the same: differentiating a polynomial whose constant term is not nought multiplies every other coefficient by a positive exponent and deletes the constant term, so the list of signs loses its last entry and nothing else. It loses a change if the last two signs differed, and keeps every change otherwise.

Put together, each member has at most one more positive root than the member below it and at most one more sign change, and the last member, a single term, has neither. Counting upward, $p$ has at most as many positive roots as sign changes. The same induction proves the sharper statement that the number of terms minus one is a bound, since every step removes a term; that is the form in which the degree never enters.

Where the slack goes #

Changing one coefficient from $-5$ to $-2$ keeps every sign, so the bound stays at three. The polynomial now has a single positive root. The chain shows where the missing two went: the first derivative, divided by $x$, has no positive roots, although the member below it has one and Rolle’s theorem would have allowed two. The argument bounds each member by the one below, and a bound is all it can give; where a member happens to have fewer roots than it could, the slack is carried all the way up.

The deficit is always even, and the reason is a comparison of two ends. The number of positive roots, counted with multiplicity, is even or odd according to whether $p$ has the same sign near $x = 0$ as at large $x$ — the first set by the lowest nonzero coefficient, the second by the highest — because the graph crosses the axis an even number of times between two points of the same sign and an odd number between two of opposite signs, as the intermediate value property guarantees. The number of sign changes is even or odd for exactly the same reason: a list of signs that starts and ends with the same sign changes an even number of times. The two counts share a parity, so they differ by an even number.

How far it overshoots #

On a polynomial chosen at random the rule is loose. Sixteen random coefficients have about eight sign changes, since each neighbouring pair disagrees half the time; the polynomial itself has about one positive root, since almost none of the roots of a random polynomial are real — about $\tfrac{2}{\pi}\ln 16 \approx 1.8$ real roots, split between the two sides. So the typical overshoot is six or eight, and the figure’s three hundred polynomials bear that out, with an excess from two to twelve and never an odd number.

On a polynomial whose roots are all real, the rule is exact, and the proof is a count. Write $V_+$ for the sign changes of $p(x)$ and $V_-$ for those of $p(-x)$. Replacing $x$ by $-x$ flips the sign of every odd-power coefficient, which turns every place where two neighbouring coefficients agree into a place where they disagree, and the reverse; for a polynomial of degree $n$ with no zero coefficient, $V_+ + V_- = n$ exactly. If every root is real and none is nought, the positive and negative roots also add to $n$, since a polynomial of degree $n$ has exactly $n$ roots counted with multiplicity. Each count is at most its bound, the two counts add to $n$, and the two bounds add to $n$: every inequality must be an equality.

At degree four the rule is exact about half the time, and the figure’s second population shows that exactness is not a coincidence of small degree: whenever all four roots are real, the count matches the signs. The rule is a sharp instrument on the polynomials whose roots are all real and a coarse one on typical polynomials, and the difference between the two is the number of roots that have left the real line in complex pairs — each pair taking two from the count and leaving the signs unchanged.

Every count alone can be had #

A bound is sharp if something meets it, and for Descartes’ rule the question can be asked of every sign pattern separately. Given a list of signs with $c$ changes, is there a polynomial with exactly those signs and exactly $c$ positive roots? And one with $c - 2$, and $c - 4$, down to one or nought?

David Anderson, Julian Jackson and Meera Sitharam proved in 1998 that the answer is always yes. Every sign pattern and every count of positive roots that the rule allows for it can be realised together. The construction multiplies factors: a factor $(x - a)$ with $a$ positive contributes a positive root and a sign change, and factors can be chosen so that the product has exactly the prescribed signs while the roots are wherever they are wanted. The first figure’s polynomial is an instance, with three positive roots and three changes, and its perturbation with one root is an instance of the next count down.

So the rule for positive roots, taken alone, is as good as a rule reading only the signs could be. The same holds for negative roots, since they are the positive roots of $p(-x)$. What the 1998 result does not settle is what happens when both are asked at once.

Two counts at once #

A sign pattern for a polynomial of degree $n$ with no zero coefficient fixes both bounds: $V_+$ changes allow $V_+, V_+ - 2, \ldots$ positive roots, $V_-$ changes allow $V_-, V_- - 2, \ldots$ negative ones, and the two counts cannot add to more than $n$. Every pair satisfying those conditions is allowed. Whether each allowed pair occurs is a finite question for each pattern, and at degree four it can be settled by looking.

The table was filled by drawing random quartics for each sign pattern, with coefficients spread over many orders of magnitude, and counting their positive and negative roots exactly with the Sturm chain of the remainders that count the roots — a polynomial with a repeated root is skipped, because the rule counts a double root twice and the chain counts it once. For fourteen of the sixteen patterns, every allowed pair turned up. For the pattern $+ + - + +$ the pair (two positive, no negative) never did, and for its mirror image $+ - - - +$ the pair (no positive, two negative) never did.

A search that fails to find something proves nothing on its own. These two failures are theorems: Jack Grabiner showed in 1999 that the pattern $+ + - + +$ cannot be realised with two positive roots and no negative ones, and his argument fits in a picture.

Why two positive roots force two negative ones #

Write the quartic as $p(x) = x^4 + ax^3 - bx^2 + cx + d$ with $a, b, c, d$ all positive, which is what the pattern $+ + - + +$ says. Then

$$p(-x) = x^4 - ax^3 - bx^2 - cx + d = p(x) - 2ax^3 - 2cx.$$

For positive $x$ the subtracted amount $2ax^3 + 2cx$ is positive, so $p(-x) < p(x)$ at every positive $x$. Now suppose $p$ has two positive roots. Between them $p$ is negative, because $p$ is positive at $x = 0$ and positive for large $x$ and changes sign only at those two roots. At any point $x$ between them, $p(-x) < p(x) < 0$. But at $x = 0$ it equals $d$, which is positive. So $p(-x)$, as a function of positive $x$, is positive at nought and negative somewhere to the right, and it crosses the axis: $p$ has a negative root. The rule then forces a second, since the negative roots of this pattern must be even in number.

Two positive roots force two negative ones, although the rule, looking at each side separately, allows either without the other. The mirror image follows by replacing $x$ with $-x$. What the argument uses is more than the signs — it uses that the odd-power coefficients are both positive and the even-power ones, apart from the middle, are too, so that flipping the sign of $x$ drags the whole graph down. Information of that kind is present in the pattern taken as a whole and absent from each count taken alone.

What the signs leave out #

The rule works with the signs because the signs survive the operations the proof uses: differentiation multiplies coefficients by positive whole numbers, and division by $x$ shifts them. What the signs cannot see is the sizes, and the sizes decide everything else — whether $x^9 - 5x^5 + 5x^2 - 1$ has three roots or, with $-2$ in place of $-5$, one.

That is also why the rule is a statement about positive roots and nothing finer. The roots of the slope stay inside gave the derivative’s roots a location, inside the convex hull of the polynomial’s; Descartes’ rule gives the positive roots only a number. What the coefficients already know found that the sum and product of the roots are fixed by two coefficients; the rule finds that the signs of all of them fix an upper bound and a parity, and that, by the 1998 construction, nothing more can be concluded about either side alone.

And the rule’s bound for $x^{100} - 3x^{57} + 1$ still stands. Two positive roots at most, and it has both: one near $0.984$, where $3x^{57}$ overtakes the constant, and one near $1.024$, where $x^{100}$ overtakes $3x^{57}$ in turn. The degree tells almost nothing, and three terms tell almost everything.

Between the two rules #

There is a rule halfway between Descartes’ and Sturm’s, and it shows that the two are ends of one family. François Budan in 1807 and Joseph Fourier in 1820 took the list of a polynomial and all its derivatives, $p, p', p'', \ldots, p^{(n)}$, evaluated it at a point $a$, and counted its sign changes, $V(a)$. The number of roots between $a$ and $b$ is at most $V(a) - V(b)$, and differs from it by an even number.

At $a = 0$ the $k$-th derivative is $k!$ times the $k$-th coefficient, so the list of derivatives at nought has the same signs as the list of coefficients, read from the constant term up. At $b$ very large every derivative has the sign of its leading term, which is positive, so the list has no changes at all. The Budan–Fourier count between nought and a large $b$ is therefore exactly Descartes’ count: the rule of 1637 is the special case at the two ends of the positive axis.

Moving $a$ and $b$ inward gives a bound for any interval, as Sturm’s chain does. What the derivatives lack is the property Sturm arranged by building his chain from Euclid’s remainders: that the count changes only at roots of $p$. The derivative list can also lose sign changes in pairs at points where some derivative vanishes and $p$ does not, and those losses are what the even excess measures. Sturm’s chain was designed to have no such points, which is why its count is exact and the others are bounds.

What the table cannot show #

The table’s forty-four realised pairs are witnessed: for each, a specific quartic with whole coefficients was found and its roots were counted in exact arithmetic, so each entry is a proof by example. The two missing pairs are missing from a search, and it is Grabiner’s argument — drawn in the last figure — that makes their absence a fact rather than an observation.

At higher degree the same search becomes less reliable, because the polynomials that realise a rare pair can occupy a very small region of coefficient space, and random sampling can miss them while they exist. That is the difficulty in the problem: showing a pair occurs needs one example, and showing it never occurs needs an argument, and the arguments at higher degree are not as short as Grabiner’s.

And the table covers only patterns with no zero coefficient. A missing term changes the counting — a zero coefficient contributes no sign — and the realisability question for patterns with gaps is a separate and larger one.

Still open: which pairs occur #

For each degree the question is finite — finitely many sign patterns, finitely many allowed pairs — and it has been settled degree by degree. Alain Albouy and Yiyang Fu completed the classification through degree six in 2014; Jens Forsgård, Vladimir Kostov and Boris Shapiro dealt with degree seven, and Kostov and collaborators have pushed further. At each degree a list of impossible pairs is found, each needing its own proof, and a pattern like Grabiner’s recurs among them.

What is not known is a rule: a criterion that reads a sign pattern and a pair of counts and says, without a search and a case-by-case argument, whether the pair occurs. The impossible pairs found so far share features — they tend to ask for roots on one side while forbidding them on the other, in patterns whose shape drags one side’s graph below the other’s — but no general statement is known to capture them all. A rule of 1637 that fits in a line has a sharpened form, asked about both sides at once, whose answer is still a table.

Counting from the outside #

Descartes’ rule and Sturm’s theorem sit at two ends of the same idea. Both count roots by counting sign changes in a list. Sturm’s list is a chain of polynomials evaluated at a point, built by Euclid’s algorithm run on polynomials instead of whole numbers, and it gives an exact count at the cost of computing the chain. Descartes’ list is the coefficients themselves, and it gives a bound at no cost at all.

Between them is a surprisingly rich question. The bound is sharp for each side alone, exact when every root is real, and off by an even number in general — and when both sides are asked together, the signs carry information that neither bound uses, enough to forbid some combinations outright. A list of pluses and minuses turns out to be a finer invariant than its two counts, and how much finer is still being measured.