Five where four were promised

What the signs allow proved Descartes’ rule by removing one term at a time, and its sharpest consequence is that the number of positive roots of a polynomial in one unknown is bounded by the number of its terms, not its degree. A polynomial with three terms — a trinomial — has at most two positive roots, whether its degree is three or three thousand.

The question for systems is the obvious one. Take two polynomial equations in two unknowns $x$ and $y$, and ask how many solutions they can have with both $x$ and $y$ positive. The classical answer, Bézout’s theorem, counts by degree: two curves of degrees $d_1$ and $d_2$ meet in at most $d_1 d_2$ points. For sparse equations that is hopeless, since a trinomial of degree 108 would be allowed thousands of solutions. What was wanted was a count by terms, as Descartes gave in one variable.

Anatoli Kushnirenko proposed one in the 1970s. For $n$ equations in $n$ unknowns, with the $i$-th equation having $m_i$ terms, the number of isolated solutions with every coordinate positive should be at most $(m_1 - 1)(m_2 - 1)\cdots(m_n - 1)$ — Descartes’ bound in each equation, multiplied. For two trinomials, that is four. It is not true, and the smallest case already fails: two trinomials can have five positive solutions.

Counting by degree, and why it overcounts #

Bézout’s theorem is the right count for the problem it answers. Two plane curves of degrees $d_1$ and $d_2$ with no common component meet in exactly $d_1 d_2$ points, if the points are counted with multiplicity, in the complex numbers, and including points at infinity — the two-variable version of the fact that a polynomial of degree $n$ has exactly $n$ complex roots. For Haas’s two curves of degree 108 that is 11,664 intersection points.

Almost none of them are real, and of the real ones almost none are positive. The situation is the one what the coefficients already know found in one variable: the complex count is fixed by the degree and says nothing about the real one. In one variable Descartes’ rule bridges the gap for positive roots by reading terms instead of degree. Kushnirenko’s proposal was that the same bridge could be built for systems simply by multiplying, and the multiplication would have been natural if the equations were independent of each other in the way that a product suggests. They are not, and the five crossings are what the interaction adds.

The complex count by terms does exist. The BKK theorem — after David Bernstein, Kushnirenko himself and Khovanskii — counts solutions with every coordinate non-zero in the complex numbers by the mixed volume of the shapes the exponents make, and for sparse systems it is far smaller than Bézout’s number. But it counts complex solutions, and the real and positive ones are a subset it cannot locate.

Two curves that cross five times #

The system in the figure is

$$x^6 + \tfrac{44}{31}\,y^3 - y = 0, \qquad y^6 + \tfrac{44}{31}\,x^3 - x = 0.$$

Each equation has three terms, so Kushnirenko’s bound is $(3-1)(3-1) = 4$. The two curves cross five times in the positive quadrant, once on the diagonal and twice on each side of it, in mirror-image pairs, since exchanging $x$ and $y$ exchanges the two equations.

Each curve is easy to draw. The first equation says $x^6 = y - \tfrac{44}{31}y^3$, which is positive for $y$ between nought and $\sqrt{31/44} \approx 0.84$, so for each such $y$ there is exactly one positive $x$. The curve runs from the origin up along the $y$-axis, bulges out to about $x = 0.83$, and returns to the $y$-axis at $y = 0.84$. Its mirror image does the same with the axes swapped. Two bulging arcs, one hugging each axis, cross where their outer edges meet, and the arithmetic arranges for their outer edges to weave across each other five times.

This system is due to Alicia Dickenstein, Maurice Rojas, Korben Rusek and Justin Shih, in 2007, and its degree of six is not where the story started.

The first counterexample hid in a corner #

Bertrand Haas published the first counterexample in 2002, in a paper titled simply A simple counterexample to Kouchnirenko’s conjecture. His equations had the same shape and much higher degree:

$$x^{108} + 1.1\,y^{54} - 1.1\,y = 0, \qquad y^{108} + 1.1\,x^{54} - 1.1\,x = 0.$$

In ordinary coordinates there is nothing to see. With exponents that large, $x^{108}$ is negligible unless $x$ is very close to 1, so the first curve lies almost exactly along the line $x = 1$ except where $y$ is near nought or near 1, and all the action is squeezed into the corner $(1,1)$.

Magnified logarithmically out of the corner, the five crossings separate. One is on the diagonal, at about $0.9915$ in both coordinates. The other four are pairs in which one coordinate is about $0.92$ or $0.94$ and the other is within a few millionths of 1. A plot with pixels of a thousandth would put all five in the same pixel, and a numerical solver started at random would find the diagonal one and perhaps one other. That the conjecture stood for more than two decades is less surprising in this light: the counterexample had to be looked for in a corner no one would draw.

Counting crossings along one curve #

The way to count them without drawing is to reduce two unknowns to one. The first equation can be solved for $x$ as a function of $y$, as above, and substituting that $x$ into the second equation’s left side gives a function of $y$ alone, whose sign changes are exactly the points where the first curve crosses the second.

The function changes sign five times, and each change is a crossing. Every figure here was computed this way: walk the first curve with its parameter in logarithmic steps fine enough to resolve points within $10^{-15}$ of the corner — everything done with logarithms so that $x^{108}$ never underflows — find the sign changes, and then check each solution in both original equations.

The reduction does not bring Descartes’ rule back. The function of $y$ involves $(y - \tfrac{44}{31}y^3)^{1/6}$ raised to powers, and it is not a polynomial with few terms; the rule has nothing to say about it. Eliminating $x$ algebraically instead, with the resultant, gives an honest polynomial in $y$, but one of high degree with many terms, and Descartes’ bound for it is far above five. The sparsity that made the question interesting is exactly what elimination destroys.

Where in the family five appear #

Haas’s equations belong to a family, $x^{2d} + c\,y^d - c\,y = 0$ with its mirror, and the family can be surveyed. For each exponent and each value of $c$ on a grid, the figure counts the positive solutions. At $c$ just above one there is a single solution on the diagonal. Further right, every row has a band where the count is five, followed by a long stretch of three. The band is wide at high degree — from about $1.10$ to $1.37$ at degree 108 — and narrows as the degree comes down, until at degree six it is a sliver.

Why the band widens with the degree can be read off the corner picture. Each curve is made of two nearly straight pieces — one hugging an edge of the square, one running across near the other edge — joined by a sharp bend, and the higher the exponents, the straighter the pieces and the sharper the bend. Five crossings need the two bends to pass through each other at a shallow angle, so that the curves weave rather than cross once; sharp bends and straight pieces give that weaving room to happen over a wider range of $c$. At low degree the curves are rounder, the weave is tighter, and the coefficient must be tuned more finely to produce it.

The degree-6 system of the first figure is this family at its smallest exponent, rescaled. Replacing $x$ and $y$ by $s x$ and $s y$ multiplies the three terms by different powers of $s$, and choosing $s$ to make the last coefficient one turns $c$ into $c^{2/5}$ on the middle term; the sliver of five at degree six lies at $c \approx 2.40$, and $2.40^{2/5}$ is $1.42$, which is $\tfrac{44}{31}$ to two decimals.

Along one row the count moves in jumps. It goes from one to five at once, because by the mirror symmetry two tangencies happen at the same moment, one on each side of the diagonal, and each creates a pair of solutions. It falls from five to three when a mirror-image pair merges with the diagonal solution and leaves it alone. At degree six the whole window of five is half a hundredth wide, and a survey on a coarser grid would miss it. Neither transition ever leaves more than five, at any degree or any $c$ in the survey.

Five is the most #

That ceiling is a theorem. Tien-Yien Li, Maurice Rojas and Xiaoshen Wang proved in 2003 that two trinomials in two unknowns have at most five isolated solutions with both coordinates positive. Haas’s example is therefore sharp, and the correct form of Kushnirenko’s bound in the smallest case is five, not four.

Their argument, like the trace figure, reduces the system to counting the zeros of one function of one variable, which is possible because a trinomial curve can be parametrised explicitly — the first equation was solved for $x$ above by taking a single root. The difficulty is that the function obtained is not a polynomial, so neither Descartes’ rule nor Sturm’s chain applies to it, and controlling its zeros is where the work lies. The theorem is short to state and the proof is not.

For more terms or more unknowns, exact maxima are not known. The best general theorem is Askold Khovanskii’s, from 1980, and it is a bound of a very different size.

Khovanskii’s bound and the truth #

Khovanskii’s fewnomial theorem says that a system of $n$ polynomial equations in $n$ unknowns, involving $n + k + 1$ distinct monomials in all, has at most $2^{\binom{n+k}{2}}(n+1)^{n+k}$ isolated positive solutions. The degree does not appear, which is the point: it is the first theorem to count solutions of a system by its terms, as Descartes counted roots of one polynomial. His method, now called the Khovanskii–Rolle theorem, extends Rolle’s argument from functions on a line to curves in higher dimensions, and it is one of the few tools that can count real solutions of equations without reference to complex ones.

For two trinomials, with six monomials, $n = 2$ and $k = 3$, and the bound is $2^{10} \cdot 3^5 = 248{,}832$. Bihan and Sottile brought the general bound down in 2007 to $\tfrac{e^2 + 3}{4}\, 2^{\binom{k}{2}} n^k$, which here is 166. The truth is five. The bounds were built to hold for every system of every shape, and their size is the price of that generality; they are not attempts to be sharp in the smallest case.

Why the positive quadrant #

The restriction to positive solutions is not a convenience. In logarithmic coordinates, $x = e^u$ and $y = e^v$, a monomial $x^a y^b$ becomes $e^{au + bv}$, an exponential of a linear function. A polynomial with $m$ terms becomes a sum of $m$ exponentials, and its positive solutions become all the real solutions of that sum, with no constraint of sign. The count by terms is really a theorem about exponential sums, where the exponents need not even be whole numbers.

In one variable this is exactly where Descartes’ rule lives: dividing by the lowest power and differentiating, in logarithmic coordinates, is dividing by an exponential and differentiating, and it removes one exponential at each step. Rolle’s theorem does the counting, as it does when the roots of the slope stay inside the roots of the function, and Rolle’s theorem is a statement about one real variable. Negative solutions are handled by changing signs of variables, which permutes the signs of the terms, so the positive quadrant loses nothing — any orthant can be moved onto it.

The logarithmic coordinates are also why Haas’s corner could be magnified at all. The corner figure uses $-\log_{10}(1 - x)$ rather than $\log x$, which is a different magnification for a different place, but the lesson is the same: the geometry of sparse equations is multiplicative, and a picture in the wrong coordinates hides it.

Where the solutions come from in practice #

The question is not only a curiosity about counterexamples. A chemical reaction network under mass-action kinetics has steady states that are the positive solutions of a polynomial system whose terms correspond to the reactions — few terms, high degree, and only positive concentrations meaningful. Whether a network can have several steady states, and so can switch between them, is a question about how many positive solutions such a system can have. The same holds for the configurations of a linkage, the equilibria of an economic model and the rest points of many biological models.

In each case Bézout’s count by degree is far too large and the count by terms is what matters, and in each case the honest general bound is Khovanskii-type — far above the truth. The remainders that count the roots gave an exact count in one variable by Euclid’s algorithm; for systems no such count exists, and the positive solutions are found by the numerical route of finding every complex solution and checking which are real and positive, as a random polynomial’s roots were found.

What the figures cannot show #

Every solution drawn is computed in floating-point arithmetic and checked by substituting it into both equations, where each residual is below $10^{-9}$. That makes each solution drawn a solution, but it does not by itself prove there are no others. The count of five at each drawn system is complete for the reason given by Li, Rojas and Wang, not by the search: once five are exhibited, there cannot be a sixth.

The survey of the family is on a grid of $c$ with steps of $0.005$ and a parameter sweep of a few thousand points along each curve. A window of five narrower than the grid, or two solutions closer than the sweep’s resolution, would be missed; the degree-6 row shows that the first danger is real, since its window is less than two grid steps wide. What the survey establishes is where five certainly occur, not where they certainly do not.

And a figure of two curves in the plane shows the crossings but not their multiplicity or their stability. The theorems count isolated solutions; a tangency, where two curves touch without crossing, is a solution that a small change of coefficients can remove or split in two, and it is exactly at such tangencies that the count jumps.

Still open: how the truth grows #

For two trinomials the answer is five. For $n$ equations in $n$ unknowns with $n + k + 1$ monomials, the true maximum is not known beyond a handful of small cases, and the gap between the best constructions and the best bounds is enormous. Constructions give systems whose number of positive solutions grows polynomially in $k$ for fixed $n$; the bounds grow like $2^{k^2/2}$. Whether the truth is polynomial or exponential in the number of monomials is one of the central open questions of real algebraic geometry, and Kushnirenko’s conjecture in a weakened form — some bound polynomial in the number of terms — is still open.

Even for two equations in two unknowns, the exact maximum is known when both are trinomials and in only a few other special shapes. Two equations with four terms each already have no settled answer, and no one knows whether Kushnirenko’s product fails there by one, as it does for trinomials, or by more.

Counting by terms, again #

Descartes’ rule was a statement that a short list of signs controls a polynomial of any degree. Khovanskii’s theorem is the same statement for systems, true in principle and absurd in size, and Haas’s example is the first sign of why the size is hard to bring down: the simplest guess, multiply the one-variable bounds, fails on the smallest system it could be tested on, and it fails in a corner of the plane that ordinary pictures cannot see.

The answer for the smallest case turned out to be five, and the proof that five is the most took a year after the counterexample. For every case larger, the count by terms exists and is unknown.