Are all polynomial inequalities deducible from the trivial inequality? - MathOverflow

Are all polynomial inequalities deducible from the trivial inequality?

2009-12-11T17:25:31Z

I remember learning some years ago of a theorem to the effect that if a polynomial $p(x_1, ... x_n)$ with real coefficients is non-negative on $\mathbb{R}^n$, then it is a sum of squares of polynomials in the variables $x_i$. Unfortunately, I'm not sure if I'm remembering correctly. (The context in which I saw this theorem was someone asking whether there was a sum-of-squares proof of the AM-GM inequality in $n$ variables, so I'm not 100% certain if the quoted theorem was specific to that case.)

So: does anyone know a reference for the correct statement of this theorem, if in fact something like it is true? (Feel free to retag if you don't think it's appropriate, by the way.)

Answer by Alon Amit for Are all polynomial inequalities deducible from the trivial inequality?

2009-12-11T17:36:21Z

Not exactly - you may need to allow squares of rational functions, not just polynomials. This is Hilbert's 17th Problem.

Answer by Anton Petrunin for Are all polynomial inequalities deducible from the trivial inequality?

2009-12-11T17:37:33Z

In short: it IS true in three cases:

for polynomial of degree 2
for polynomial of degree 4 in two variables
for polynomial in one variable.

The answer is here:

Hilbert, D. Ueber die Darstellung deniter Formen als Summe von Formenquadraten. Mathem. Annalen Bd 32, S. 342-350 (1888)

Answer by Greg Kuperberg for Are all polynomial inequalities deducible from the trivial inequality?

2009-12-11T17:38:39Z

One interpretation of the question is Hilbert's 17th problem, to characterize the polynomials on $\mathbb{R}^n$ that take non-negative values. The problem is motivated by the nice result, which is not very hard, that a non-negative polynomial in $\mathbb{R}[x]$ (one variable) is a sum of two squares. What is fun about this result is that it establishes an analogy between $\mathbb{C}[x]$, viewed as a quadratic extension by $i$ of the Euclidean domain $\mathbb{R}[x]$; and $\mathbb{Z}[i]$ (the Gaussian integers), viewed as a quadratic extension by $i$ of the Euclidean domain $\mathbb{Z}$. In this analogy, a real linear polynomial is like a prime that is 3 mod 4 that remains a Gaussian prime, while a quadratic irreducible polynomial is like a prime that is not 3 mod 4, which is then not a Gaussian prime. A non-zero integer $n \in \mathbb{Z}$ is a sum of two squares if and only if it is positive and each prime that is 3 mod 4 occurs evenly. Analogously, a polynomial $p \in \mathbb{R}[x]$ is a sum of two squares if and only if some value is positive and each real linear factor occurs evenly. And that is a way of saying that $p$ takes non-negative values.

In dimension 2 and higher, the result does not hold for sums of squares of polynomials. But as the Wikipedia page says, Artin showed that a non-negative polynomial (or rational function) in any number of variables is at least a sum of squares of rational functions.

In general, if $R[i]$ and $R$ are both unique factorization domains, then some of the primes in $R$ have two conjugate (or conjugate and associate) factors in $R[i]$, while other primes in $R$ are still primes in $R[i]$. This always leads to a characterization of elements of $R$ that are sums of two squares. This part actually does apply to the multivariate polynomial ring $R = \mathbb{R}[\vec{x}]$. What no longer holds is the inference that if $p \in R$ has non-negative values, then the non-splitting factors occur evenly. For instance, $x^2+y^2+1$ is a positive polynomial that remains irreducible over $\mathbb{C}$. It is a sum of 3 squares rather than 2 squares; of course you have to work harder to find a polynomial that is not a sum of squares at all.

Answer by Sonat Suer for Are all polynomial inequalities deducible from the trivial inequality?

2009-12-11T19:43:42Z

Considering the word deduce, I think a possible way to address this question is to use logic, more precisely model theory. Here is a model theoretic restatement of your question: What is a good axiomatization of the quantifier free theory of reals as an ordered ring? The answer is a classical theorem of Tarski, which also solves Hilbert's 17th problem with some algebra. Tarski's theorem says that the theory of real closed fields has quantifier elimination. This implies that the theorey of real closed fields is complete as there is an algebraicaly prime model, namely the rationals. So a valid system of polynomial inequalities in any real closed field is deducible from the axioms of real cosed fields.

Answer by FG for Are all polynomial inequalities deducible from the trivial inequality?

2009-12-11T20:14:26Z

There is a Wikipedia page on polynomial sums of squares. Hilbert showed in the article quoted by Anton that all nonnegative polynomials are sums of squares in the following three situations:

univariate polynomials of any degree (and only two squares are needed)
quadratic polynomials in any number of variables $n$ (and at most $n$ squares are needed, which can be obtained from the Cholesky decomposition of the associated positive semidefinite matrix)
polynomials of degree four in two variables

One of the simplest examples of nonnegative polynomial that is not a sum of squares is the Motzkin polynomial, given by $p(x,y)=1 + x^2 y^4 + x^4 y^2 - 3x^2 y^2$. Interestingly enough, one can easily show that it is nonnegative using the arithmetic-geometric mean (on the first three terms), while a careful reasoning on the zeros of a potential decomposition into squares shows that it is not sum of squares (see e.g. Some concrete aspects of Hilbert's 17th problem by Bruce Reznick).

Finally, note that sum-of-squares decompositions of a given polynomial can be computed numerically using semidefinite programming.

Answer by Gil Kalai for Are all polynomial inequalities deducible from the trivial inequality?

2009-12-12T16:11:57Z

Let me draw your attention to the paper "There are significantly more nonegative polynomials than sums of squares" by Grigoriy Blekherman. Here are slides of a related talk by Grigory

The abstract reads: "We study the quantitative relationship between the cones of nonnegative polynomials, cones of sums of squares and cones of sums of even powers of linear forms. We derive bounds on the volumes (raised to the power reciprocal to the ambient dimension) of compact sections of the three cones. We show that the bounds are asymptotically exact if the degree is fixed and number of variables tends to infinity. When the degree is larger than two, it follows that there are significantly more nonnegative polynomials than sums of squares and there are significantly more sums of squares than sums of even powers of linear forms. Moreover, we quantify the exact discrepancy between the cones; from our bounds it follows that the discrepancy grows as the number of variables increases."