Multiply until every sign is positive

Is $x^2 - 1.8xy + y^2$ positive whenever $x$ and $y$ are positive? The middle coefficient is negative and larger than either of the others, so the question is not settled by looking. Completing the square settles it: the form is $(x - 0.9y)^2 + 0.19y^2$, a sum of squares, positive except at the origin. That is the classical kind of certificate, and the essay before this one showed both how far it reaches and where it fails: Motzkin’s polynomial is never negative and is not a sum of squares, and Artin’s theorem rescues it only after multiplying by a suitable square.

There is a different kind of certificate, older in spirit and cruder in method, which asks for nothing to be completed. Multiply the form by $x + y$, and again, and again. If after some number of multiplications every coefficient of the product is positive, then the product is obviously positive for positive $x$ and $y$, since every one of its terms is; and since $x + y$ is positive there too, so is the original form. George Pólya proved in 1928 that this always works for a form that is strictly positive on the region in question — some power of $x + y$, or of $x_1 + \cdots + x_n$ in more variables, always turns every coefficient positive. This essay computes how high the power has to go.

The region and the segment #

A form is a polynomial whose terms all have the same degree, and it is enough to know its values on the segment where $x + y = 1$, since every other point with positive coordinates is a multiple of one there and a form of degree $d$ just scales by the $d$-th power. So the question “is the form positive on the positive quadrant?” is the question “is it positive on the segment from $(0, 1)$ to $(1, 0)$?”. In three variables the segment becomes a triangle, the simplex $x + y + z = 1$ with all three coordinates non-negative, and so on in higher dimensions.

On the segment the hero’s form is the curve drawn in black: 1 at each end, dipping to 0.05 in the middle, where $x = y = \tfrac12$. It is positive everywhere, but only just. Its coefficients, read as they are, say the opposite: two of them are $+1$ and the middle one is $-1.8$.

Each multiplication averages #

Multiplying by $x + y$ does something simple to the coefficients. If the form is $\sum a_k x^k y^{d-k}$, the product’s coefficient of $x^k y^{d+1-k}$ is $a_{k-1} + a_k$: each new coefficient is the sum of two neighbours. Repeating $N$ times gives coefficients that are sums of the old ones weighted by binomial coefficients, a row of Pascal’s triangle spread across the old row.

The raw numbers grow like $2^N$ and hide what is happening. Divide each coefficient of the product by the binomial coefficient $\binom{N+d}{k}$ that sits in the same place, and the result is the Bernstein coefficient, the number that, plotted at the point $k/(N + d)$ of the segment, approximates the form’s value there. That is what the hero draws. At $N = 0$ the three Bernstein coefficients are $1$, $-0.9$ and $1$, far from the curve in the middle. At $N = 6$ they have closed in, and only three are still below zero. At $N = 19$ all twenty-two lie close to the curve, and all are positive.

The reason they approach the curve is the reason Bernstein’s polynomials approximate any continuous function: the binomial weights that produce the coefficient at position $k/n$ are the probabilities of a binomial count, and a binomial count with many trials concentrates around its mean. So each Bernstein coefficient is an average of the form over a small, shrinking neighbourhood of its own position, with an error that falls like $1/N$. Once that error is smaller than the form’s least value on the segment, every coefficient is positive.

That argument is the whole proof of Pólya’s theorem. It also says why the form must be strictly positive: if it reached zero somewhere, the coefficients near that place would approach zero, and nothing would force them to approach it from above.

The signs, power by power #

Watching the signs alone shows how indirect the certificate is. The negative coefficients start as the single middle one. As the product grows they number two, then one, then two or three, rising and falling by one as the middle of the row alternates between one coefficient and two, and they disappear only at the nineteenth power. At no earlier power does a row prove anything: a single negative coefficient leaves the question open, because a polynomial with a negative coefficient can be positive or not. The certificate, when it comes, comes all at once.

The count of sign changes in a row of coefficients is also the quantity in Descartes’ rule of signs, which bounds the number of positive roots of a polynomial by the number of times its coefficients change sign. Set $y = 1$ and the form becomes the quadratic $t^2 - 1.8t + 1$ in $t = x/y$, with two sign changes and no positive roots, so Descartes’ bound is not attained. Multiplying by $(t + 1)^N$ adds no positive roots and, by Pólya’s theorem, eventually removes every sign change. In one variable this is a converse to Descartes’ rule: a polynomial with no positive roots, and positive at both ends of the half-line, can be multiplied into one whose signs say so.

How high the power must go #

For a form that comes close to zero the certificate must be long, because the Bernstein coefficients have to approximate the form more closely than its least value. The question is how long.

The family $x^2 - (2 - \varepsilon)xy + y^2$ has least value $\varepsilon/4$ on the segment, at its midpoint. As $\varepsilon$ shrinks it approaches $(x - y)^2$, which touches zero there. The least power was computed exactly for thirteen values of $\varepsilon$, by tracking the sign of each Bernstein coefficient as a product of short ratios, so that no binomial coefficient is ever formed and nothing overflows even at a power of several thousand. It runs 3, 7, 11, 19, 37 and so on, to 3,999 at $\varepsilon = 0.001$. The product $N\varepsilon$ settles at 4.

In 2001 Victoria Powers and Bruce Reznick gave a bound valid for every form: if a form of degree $d$ has least value $\lambda$ on the simplex, and $L$ is the largest of its coefficients each divided by its multinomial coefficient, then any power $N > d(d-1)L/(2\lambda) - d$ works. For this family $d = 2$, $L = 1$ and $\lambda = \varepsilon/4$, so the bound is $4/\varepsilon - 2$. The computed least powers never exceed it by more than the one that the strict inequality allows: at $\varepsilon = 0.001$ the bound is 3,998, it guarantees 3,999, and 3,999 is the least power that works. The bound is attained. Its dependence on the least value cannot be improved; a form that comes within $\lambda$ of zero needs, in the worst case, a certificate of length proportional to $1/\lambda$.

The middle coefficient, exactly #

For this family the whole computation can be done by hand, and it explains both the factor of 4 and why the bound is met. The product’s coefficients divided by binomial coefficients are combinations of three ratios, $\binom{N}{k-2}$, $\binom{N}{k-1}$ and $\binom{N}{k}$ each divided by $\binom{n}{k}$ with $n = N + 2$, and those ratios are $k(k-1)$, $k(n-k)$ and $(n-k)(n-k-1)$, all over $n(n-1)$. When $n$ is even the middle coefficient, at $k = n/2$, comes out as

$$\frac{\varepsilon n/4 - 1}{n - 1},$$

so it is positive exactly when $n > 4/\varepsilon$, that is when $N > 4/\varepsilon - 2$ — the Powers–Reznick bound, reached from the other side. At $N = 4/\varepsilon - 2$ the middle coefficient is exactly zero, which is what the computation found to within rounding at $\varepsilon = 0.001$ and $N = 3{,}998$. When $n$ is odd the middle falls between two coefficients, each a little better off, which is why the least power is sometimes one or two below the bound, as at $\varepsilon = 0.1$, where it is 37 rather than 39.

At $\varepsilon = 0$ the same expression is $-1/(n - 1)$: the values $-1/9$, $-1/33$ and $-1/129$ that the next figure measures. It is the quadratic of where two roots run into each other seen from the inside. As the middle coefficient $-(2 - \varepsilon)$ approaches $-2$, the two complex roots of $t^2 - (2 - \varepsilon)t + 1$ run together onto the positive real axis, and the length of the certificate is the price of their approach: a root at distance about $\sqrt{\varepsilon}$ from the positive axis costs a power of about $4/\varepsilon$.

A zero in the middle #

At $\varepsilon = 0$ the form is $(x - y)^2$, never negative and zero at the midpoint. Its Bernstein coefficients approach the curve as before, but the curve is zero there and they approach it from below. The least coefficient, always the middle one, is $-0.11111$ at $N = 8$, $-0.03030$ at $N = 32$ and $-0.00775$ at $N = 128$, shrinking roughly like $1/N$ and never reaching zero. No power certifies the form, though it is a perfect square and as non-negative as a form can be.

So the two kinds of certificate fail in different places. Sums of squares certify $(x - y)^2$ trivially and fail for Motzkin’s polynomial; Pólya’s method certifies anything strictly positive, however awkward, and fails at the simplest square. A zero at an end of the segment can be harmless, since the coefficients there need only be non-negative and a form like $x^2$ has them from the start, but a zero inside defeats every power. Which forms with zeros on the boundary of the simplex can still be certified this way has been studied by Castle, Powers and Reznick, and the answer depends on how the form behaves near each zero.

Three variables #

In three variables the coefficients of the product sit naturally on a triangle, one for each monomial $x^i y^j z^k$, with the pure powers at the corners. The form $x^2 + y^2 + z^2 - 0.9(xy + yz + zx)$ has its least value on the simplex at the centre, where it is $1/30$; on the triangle $x + y + z = 1$ it equals $1 - 2.9(xy + yz + zx)$, and the bracket is largest at the centre. At $N = 0$ three of its six coefficients are negative, the mixed ones. By $N = 9$ the negatives are a patch of 12 out of 78 around the centre, by $N = 19$ seven of 253, and at $N = 29$ there are none among 528.

The Powers–Reznick bound for this form is $2 \cdot 1/(2 \cdot \tfrac{1}{30}) - 2 = 28$, so it guarantees the power 29, and 29 is the least power that works. The bound is exact again, and for the same reason: the form’s minimum sits at the centre of the simplex, where the averaging that Bernstein coefficients perform is slowest to settle.

Random forms sit far below the bound #

The symmetric examples are the hard cases, built with the minimum in the middle. For random forms the bound is generous. Of 400 random quartics in $x$ and $y$, the 318 that stay above 0.01 on the segment were each certified at the least possible power and compared with the bound. None needs more than the bound allows; 83 need no multiplication at all, their coefficients already positive; and the median ratio of least power to bound, both shifted by one, is 0.09. The bound sees only the least value and the largest coefficient, and a form whose minimum lies near an end of the segment, or whose negative coefficients are small, is certified long before the bound says it must be.

What a certificate of this kind is for #

A certificate made of positive coefficients is checked by reading signs, and searching for one is a linear programme: asking whether some combination of products of $x_1 + \cdots + x_n$ with the form, plus an unknown constant, has non-negative coefficients is a system of linear inequalities. That makes Pólya’s theorem the basis of a hierarchy of linear programmes for optimising a polynomial over the simplex — find the largest $c$ such that $(x_1 + \cdots + x_n)^N(p - c(x_1 + \cdots + x_n)^d)$ has non-negative coefficients — whose values approach the true minimum as $N$ grows. Each step is a linear programme rather than the semidefinite programme that sums of squares require, cheaper to solve and weaker per step. The cost is in the number of coefficients. A product of degree $N + d$ in $n$ variables has $\binom{N+d+n-1}{n-1}$ of them: the three-variable form above, certified at $N = 29$, has 528, but the same power and degree in ten variables would have $\binom{40}{9} = 273{,}438{,}880$, one linear inequality each. A certificate whose length grows like $1/\lambda$ in the power grows like a power of $1/\lambda$ in its size, and that, rather than any failure of the theorem, is what limits its use.

The trade is the same for every certificate of positivity met so far. Sylvester’s law certified a quadratic form by its signs after completion; squares certified more and missed Motzkin’s polynomial; Pólya’s products certify every strictly positive form on the simplex and miss every form with an interior zero. Each kind of certificate is exact somewhere and silent somewhere else.

What the pictures cannot show #

The least powers are computed exactly in the sense that the sign of each Bernstein coefficient is evaluated in floating point as a sum of a few products of ratios, which is accurate to many digits but not exact arithmetic. At the least power for $\varepsilon = 0.001$ the deciding coefficient is $1.25 \times 10^{-7}$, far above the rounding; one power lower it is zero to within $10^{-16}$, which the computation counts as not positive, and which the formula for the middle coefficient shows is exactly zero. The random quartics are a single sample of 400, the least value of each found by a fine scan and refinement. Only binary forms and one ternary family are computed; the bound holds in any number of variables, and how tight it is there is not tested.

What was computed and what was quoted #

Computed here: the Bernstein coefficients of every product drawn, by products of ratios; the least power for $x^2 - 1.8xy + y^2$ (19), for $x^2 - (2 - \varepsilon)xy + y^2$ at thirteen values of $\varepsilon$ down to 0.001 (3,999), and for the ternary form with $a = 0.9$ (29), each found by doubling and bisection and checked against the Powers–Reznick bound; the negative middle coefficients of $(x - y)^2$ at powers 8, 32 and 128; and 318 random quartics against their bounds.

Quoted: Pólya’s theorem of 1928; the bound of Powers and Reznick from 2001; the work of Castle, Powers and Reznick on boundary zeros; the use of Pólya’s theorem in linear-programming hierarchies for optimisation over the simplex.

Still open: zeros, and the size in many variables #

Forms that touch zero on the boundary of the simplex sometimes have Pólya certificates and sometimes do not, and a complete description of which do, in any number of variables, is not available: the known criteria look at the form’s behaviour near each zero, and they are clean in few variables and incomplete beyond. The size of the certificate raises a second question. The Powers–Reznick bound grows like $d^2 L/\lambda$, and the symmetric examples here show it cannot be improved in $\lambda$; how it must depend on the number of variables and the degree, for the forms that arise in practice, is studied but not settled, and it decides how far the linear-programming hierarchies can be pushed before they become larger than the problems they solve.

A power for every positive form #

A form that is strictly positive on the simplex becomes a polynomial with every coefficient positive after multiplication by a high enough power of the sum of the variables, because the divided coefficients are averages that close in on the form’s values. The power needed grows like the reciprocal of the form’s least value: $x^2 - (2 - \varepsilon)xy + y^2$ needs 3,999 at $\varepsilon = 0.001$, exactly what the Powers–Reznick bound guarantees, a three-variable form with least value $1/30$ needs 29, again exactly the bound, and random quartics need a tenth of it. A form that touches zero inside, even $(x - y)^2$, is certified by no power at all.