Never negative and no sum of squares

A quadratic that never goes below nought has a certificate for that fact, and the certificate is a finished piece of algebra. Complete the square in $x^2 + 2xy + 3y^2$ and it becomes $(x + y)^2 + 2y^2$. Nobody has to check a single point: a square of a real number is not negative, a sum of such squares is not negative, and the expression has been rewritten as one. The signs no completion can change showed that this always works in degree two. Whatever order the variables are taken in, a quadratic form that is never negative comes apart into squares with positive coefficients, and one that goes negative at some point cannot.

So there is a tempting general belief: never negative means a sum of squares. It is true for a polynomial in one variable of any degree, by pairing up its complex roots. It is true for a quadratic in any number of variables. It feels like the kind of thing that should simply be true, since it is hard to imagine what else could hold a polynomial above nought everywhere, across a whole plane, if not squares.

The belief is false, and the smallest witness anybody found is remarkably small. It has two variables, degree six, four terms and small integer coefficients.

$$M(x, y) = x^4y^2 + x^2y^4 - 3x^2y^2 + 1.$$

Theodore Motzkin wrote it down in 1967. It takes a line to show that this is never negative and a table with sixteen cells to show that no squares add up to it. And the failure is not the end of the story, because multiplying it by the harmless-looking factor $1 + x^2 + y^2$ turns it into a sum of five squares after all.

A proof of positivity that uses no squares #

The reason $M$ is never negative is the inequality between the arithmetic and geometric means. Its three positive terms $x^4y^2$, $x^2y^4$ and $1$ have a geometric mean that collapses, because the powers add up to a perfect cube:

$$\frac{x^4y^2 + x^2y^4 + 1}{3} \ge \sqrt[3]{x^4y^2 \cdot x^2y^4 \cdot 1} = x^2y^2.$$

Multiply through by three and subtract, and that is the statement $M \ge 0$. Equality in the means needs all three terms equal, so $x^4y^2 = x^2y^4 = 1$, which forces $x^2 = y^2 = 1$. The polynomial touches nought at exactly the four points $(\pm 1, \pm 1)$ and nowhere else, and that is why Motzkin’s paper was called The arithmetic–geometric inequality: the example fell out of asking whether that inequality could be proved by squares.

For two terms it can. The inequality $a^2 + b^2 \ge 2ab$ is the square $(a - b)^2 \ge 0$ with its terms moved about, and that one line is the same arithmetic as making a square out of it: a corner is missing, and paying for it is the proof. Hurwitz showed in 1891 that the means inequality for $n$ positive variables, written with each variable raised to the power $n$, is always a sum of squares. The catch is the substitution. Motzkin’s $M$ puts monomials in place of those variables, and substituting monomials into a sum of squares only yields a sum of squares when each monomial is itself a perfect $n$-th power. Here $x^4y^2$ is not a perfect cube. So the means inequality still holds and the squares that proved it are lost in transit.

What a square is allowed to contain #

The proof that no squares work begins by limiting what could possibly go inside one. Suppose $M = q_1^2 + q_2^2 + \cdots + q_r^2$ for some polynomials $q_i$. There is no bound assumed on $r$, nor on the size of the coefficients. The first question is which monomials those $q_i$ can contain.

Draw every monomial $x^iy^j$ of $M$ as the point $(i, j)$ on a grid. The convex hull of those points is called the Newton polygon of $M$, and for this polynomial it is a triangle with corners at $(0, 0)$, $(4, 2)$ and $(2, 4)$, since those are the exponents of $1$, $x^4y^2$ and $x^2y^4$. The fourth monomial, $x^2y^2$, sits at $(2, 2)$, strictly inside.

Now push in any direction across the grid, say by giving $x$ and $y$ weights and asking for the heaviest monomial. The heaviest part of each $q_i$, squared, is the heaviest part of $q_i^2$, and it carries positive coefficients on its extreme terms. Squares that are added cannot cancel each other’s extreme terms, because a sum of positive numbers is not nought. So the heaviest part of the whole sum is exactly as heavy as twice the heaviest part of the heaviest $q_i$. This is true in every direction, and that is the statement that the Newton polygon of each $q_i$ lies inside half the Newton polygon of $M$.

Half the triangle has corners at $(0, 0)$, $(2, 1)$ and $(1, 2)$. It contains four grid points, and the figure marks them: $1$, $xy$, $x^2y$ and $xy^2$. So every $q_i$ has the form

$$q_i = a_i + b_i\,xy + c_i\,x^2y + d_i\,xy^2,$$

and the whole infinite search for a sum of squares has shrunk to a question about four coefficients per square. Nothing else can appear, however many squares are used and however large their coefficients are.

The one cell #

Expand those squares and collect terms. Sixteen products of the four monomials appear, and they can be laid out as a table in which the row and column name the two factors.

The table’s power is that $x^2y^2$ appears in exactly one cell. It would take $xy \cdot xy$, or $x^2y$ times something with $y$ to the first power and no $x$, or $xy^2$ times something with $x$ alone, and those last two monomials are not among the four. So the coefficient of $x^2y^2$ in the sum of squares is exactly $\sum_i b_i^2$. A sum of squares of real numbers cannot be $-3$. That is the whole proof.

It is a remarkably thin obstruction. All the other cells can be matched: the terms in $x^4y^2$ and $x^2y^4$ come from the diagonal cells for $x^2y$ and $xy^2$, the constant from the cell for $1$. Everything is fine except that one entry, and that entry is on the diagonal of a table that ought to be positive. The table is what is now called a Gram matrix: a polynomial is a sum of squares exactly when it can be written with a positive semidefinite matrix sandwiched between two copies of its list of allowed monomials. Motzkin’s polynomial has, in effect, a $-3$ on that diagonal which no choice of the other entries can move, and a positive semidefinite matrix can have no negative diagonal entry.

The reasoning connects directly to the signs no completion can change. There the question was whether a quadratic form on the variables themselves was positive, and Sylvester’s law said that the answer does not depend on how it is completed. Here the same quadratic-form question is being asked about a list of monomials rather than variables, and the same answer returns: the polynomial is secretly a quadratic form in $1, xy, x^2y, xy^2$, and that form has a negative direction even though, once the monomials are tied to actual values of $x$ and $y$, the negative direction can never be reached. The relations among monomials are what make the polynomial positive. Those relations are invisible to squares.

No constant can rescue it #

The proof above never used the constant term. It used only the $-3$. So raising the polynomial changes nothing: $M + 1$, $M + 10$ and $M + 1{,}000{,}000$ all have the same four allowed monomials and the same fatal cell, and none is a sum of squares. Those polynomials are strictly positive by a wide margin. The obstruction has nothing to do with $M$ being tight at its zeros, which is what one would first suspect. A polynomial may stand a million above nought everywhere and still not be expressible as squares, because being a sum of squares is about the arrangement of coefficients and not about height.

That is what the opening figure draws. Replace the $3$ by a free coefficient $c$, giving

$$M_c = x^4y^2 + x^2y^4 - c\,x^2y^2 + 1.$$

The least value on the plane comes on the diagonals. Setting $x^2 = y^2 = t$ gives $2t^3 - ct^2 + 1$, whose minimum for positive $c$ is at $t = c/3$ with value $1 - c^3/27$. That reaches nought at exactly $c = 3$, where it is Motzkin’s polynomial, and beyond $c = 3$ the polynomial goes negative.

The cell argument gives the other edge. For $c \le 0$ the polynomial is plainly a sum of squares, four of them, since every term has a non-negative coefficient and every monomial is a perfect square. For any $c > 0$ at all, however small, the coefficient of $x^2y^2$ is negative and no squares can produce it. So the whole interval $0 < c \le 3$ consists of polynomials that are never negative and are not sums of squares, and most of that interval is strictly positive. At $c = \tfrac{1}{100}$ the polynomial is within a hair of a sum of four squares, and its least value is 0.99999996, and it is still not one. Motzkin’s value $c = 3$ is not an isolated freak. It is the far end of a whole family, chosen because that is the end where the polynomial touches nought and makes the example look as sharp as it can.

What the eye gets from the surface #

The obstruction is completely invisible in the values of the function. The next figure shows $M$ from above, colour-coded by height. It has four pits at $(\pm 1, \pm 1)$, a plateau at height 1 along both axes, and rapid growth outside. Nothing distinguishes that shape from the shape of a sum of squares with the same zeros.

In fact any compact part of the picture is no evidence at all. A theorem of Weierstrass says that on a bounded region $\sqrt{M}$ can be approximated to any accuracy by a polynomial, and the square of that polynomial then approximates $M$. So on any square the eye can examine, there are sums of squares that a printed picture could not tell apart from $M$. The polynomials that approximate it have enormous degree and enormous coefficients, and they behave wildly outside the square; the distinction between the two kinds of polynomial lives in the exact coefficients and the behaviour far away. The figure is reliable as a picture of a function and silent about the arithmetic that this essay is about. Being a sum of squares is not a property of a shape.

A factor that restores the squares #

So what does certify the non-negativity of $M$, if squares cannot? The answer is that squares can, as long as a denominator is allowed. Multiply by $1 + x^2 + y^2$, and something strange happens.

The identity is

$$\begin{aligned}(1 + x^2 + y^2)\,M = {} &(x^2y - y)^2 + (xy^2 - x)^2 + (x^2y^2 - 1)^2 \\ &+ \tfrac14(xy^3 - x^3y)^2 + \tfrac34(xy^3 + x^3y - 2xy)^2,\end{aligned}$$

and it was checked here by expanding both sides as exact polynomials, coefficient by coefficient. The factor on the left is positive, so the identity is a new proof that $M \ge 0$, and it is a proof by squares. The multiplier has increased the degree from six to eight, which enlarges the Newton polygon and opens up new monomials such as $xy^3$. The table now has room to put something positive in the cell that was stuck at $-3$. Dividing by $(1 + x^2 + y^2)^2$ writes $M$ as a sum of squares of rational functions.

There is a second identity, with a different multiplier:

$$(x^2 + y^2)^2\,M = \big(x^2y(x^2 + y^2 - 2)\big)^2 + \big(xy^2(x^2 + y^2 - 2)\big)^2 + \big(xy(x^2 + y^2 - 2)\big)^2 + (x^2 - y^2)^2.$$

That one has only four squares, and it was also verified by expansion. Four is exactly what the polynomial needs, the same number that appears in Euler’s identity for products of four squares though for different reasons. J. W. S. Cassels, W. S. Ellison and Albrecht Pfister showed in 1971 that $M$ is not a sum of three squares of rational functions, by a route through elliptic curves over function fields that looks nothing like the table above.

This is the shape of the answer to Hilbert’s seventeenth problem. In 1900 Hilbert asked whether every polynomial that is never negative is a sum of squares of rational functions, and in 1927 Emil Artin proved that it is. Artin’s proof is not a construction. It goes through the theory of ordered fields, and shows that if no such expression existed, one could build a field in which the polynomial is negative, contradicting its non-negativity when the theorem is transferred back to the real numbers. Pfister added in 1967, the same year as Motzkin’s example, that $2^n$ squares always suffice for a polynomial in $n$ variables. For two variables that is the four found above.

Hilbert’s table #

Hilbert’s own contribution in 1888 was the complete answer to a tidier question: for which combinations of number of variables and degree does never negative always mean a sum of squares of polynomials?

There are exactly three safe families. One variable of any degree: pair up complex roots. Degree two in any number of variables: complete the square. And the sporadic third, two variables of degree four, which is the surprising one and the only hard case in his paper, a fact about curves in the projective plane. Every other combination has a counterexample, and it suffices to find them in two variables of degree six and three variables of degree four, since from there the failure spreads by adding variables and multiplying by squares.

Hilbert’s argument for those counterexamples was indirect. It compared the number of conditions needed for a polynomial to vanish on a set of points with the number of squares of cubics available, and showed by a dimension count that some non-negative polynomial must escape. It exhibited nothing, and it was so hard to turn into an example that none appeared in print for almost eight decades. When Motzkin’s did appear it turned out to be nothing more than the means inequality in disguise, available to anyone who had thought of asking. The story has a moral about existence proofs that is the opposite of the usual one. The usual moral is that a counting proof hides an object too complicated to write down. Here it hid an object of four terms.

Squares as a method #

The reason this is now a subject with a large literature is computational. Deciding whether a polynomial of degree six is non-negative everywhere is, in general, a hard problem: it contains problems known to be NP-hard. Deciding whether it is a sum of squares is much easier, since it is the feasibility of a Gram matrix, a question about a positive semidefinite matrix with linear constraints, and that is a semidefinite programme of size controlled by the monomials in half the Newton polygon. Pablo Parrilo’s thesis of 2000 and Jean Lasserre’s paper of 2001 turned this into a working method for optimisation: to find the least value of a polynomial, ask for the largest constant whose subtraction leaves a sum of squares.

That method is a relaxation, of the same kind as the one that answers in halves, and Motzkin’s polynomial is its standard warning. The true minimum of $M$ is nought. The largest $\gamma$ for which $M - \gamma$ is a sum of squares does not exist, because $M - \gamma$ never is one for any real $\gamma$, as the section on constants showed. So the relaxation does not merely give a weak bound on this polynomial; the bound is $-\infty$. Multiply by $1 + x^2 + y^2$ before asking and the method recovers. This is the general recipe, a hierarchy of larger and larger multipliers, and it is a statement that the same duality that makes two numbers meet operates on an enlarged space of certificates.

It is also unclear how often the relaxation should be expected to fail. For small numbers of variables and low degree, sums of squares fill most of the cone of non-negative polynomials, and most polynomials that appear in practice have a certificate. Grigoriy Blekherman showed in 2006 that this cannot last: for a fixed degree above two, as the number of variables grows, the sums of squares become a vanishing proportion of the non-negative polynomials, measured by volume in a natural normalisation. So the counterexamples that took 79 years to find are, in high dimensions, nearly everything.

What the expansions do not establish #

The computations behind these figures are of two different kinds and should not be confused. The identities are exact: both sides were expanded with integer coefficients, scaled by four to clear the fractions, and compared term by term. They would fail if a single coefficient were wrong, and the sample table is only a visual reassurance. The classification of the family $M_c$ is also proved outright, by the means inequality and by the cell.

The grid in the surface figure proves nothing. Evaluating $M$ at many points can suggest non-negativity and can refute it, but it cannot establish it, and the fact that the least grid value is positive only reflects that the grid misses the exact zeros. Non-negativity comes from the inequality. Hilbert’s table is quoted, not derived: the figure states his theorem and neither the third safe family nor the dimension count is reproduced here. And Artin’s theorem has only been illustrated, on one polynomial, by a multiplier found by hand. For a general polynomial neither the figures nor the method here produce a denominator.

Still open: how much of a multiplier is enough #

Artin’s theorem says a multiplier exists and is silent on its size. The two found here have degree two and four. For a general non-negative polynomial, how large must the denominator be? The best general upper bounds, descended from effective versions of Artin’s argument, are towers of exponentials in the number of variables and the degree, and the lower bounds known are far smaller. Nobody knows the true growth.

For strictly positive forms there is a far gentler story: Pólya showed in 1928 and Bruce Reznick extended in 1995 that multiplying a positive definite form by a large enough power of $x_1^2 + \cdots + x_n^2$ yields a sum of squares, with the power bounded by how nearly the form approaches nought. A uniform denominator cannot work for every non-negative polynomial, since the form at the boundary of the cone can resist every power. Reznick’s examples show the failure happening exactly where zeros of the form lie. How the required power blows up on the way to the boundary is known only in terms of bounds with a wide gap.

A proof that the squares could not see #

The two arguments in this essay use completely different information. Non-negativity comes from relations among monomials: $x^4y^2$, $x^2y^4$ and $x^2y^2$ cannot be chosen independently, because they are all built from the same $x$ and $y$, and the means inequality is exactly such a relation. Sums of squares ignore those relations, treating each allowed monomial as an independent coordinate, and for $M$ that blindness leaves a negative direction that is never actually reachable. One cell of a table shows it, and no constant can repair it.

Completing the square was never a method of evaluating polynomials. It is a way of reading a polynomial’s coefficients as a quadratic form, and the theorem at the bottom of the method says when that reading tells the truth. For quadratics it always does. For sextics in two variables it can miss the point by an unbounded margin, and the repair, a multiplier that enlarges the table, is what the whole modern practice of proving inequalities by squares consists of.