when is the power of a nonnegative polynomial a sum of squares? - MathOverflow

when is the power of a nonnegative polynomial a sum of squares?

2011-01-24T12:04:33Z

There are polynomials that are not sum of squares. For example Motzkin gave the example $x^4y^2+x^2y^4+z^6-3x^2y^2z^2$ in 1967.

Is there a real polynomial $f\in{\mathbb{R}}[x_1,\ldots,x_n]$ in several indeterminates that is not a sum of squares but $f^N$ is a sum of squares for some odd integer $N>0$?

This question is interesting in the following sense. The notion of writing nonnegative polynomials $f$ as a sum of squares is to give an algebraic proof of the inequality $f\ge 0$. As per Motzkin's example, we know that this is not always possible. One way to resolve this is to follow Artin and use denominators. Another way (which I learnt from D'Angelo) is to show that $f^{N}$ is a sum of squares for some odd $N$.

This question is me wondering whether such a technique of consider the radical of sum of squares is vacuous.

Answer by Gjergji Zaimi for when is the power of a nonnegative polynomial a sum of squares?

2011-01-27T06:18:31Z

This doesn't answer your question but it's more of a comment. In the paper "Integral solution of Hilbert's seventeenth problem", Gilbert Stengle gives an example of a positive semidefinite form no odd power of which is a sum of squares. His examples are of the form $$x^{2k+1}z^{2k+1}+(z^{2k-1}y^2-xz^{2k}-x^{2k+1})^2$$ In the same paper it is proven that for ever positive semidefinite form $F$ there is a polynomial $\phi$ of odd degree, with coefficients which are sums of squares, that satisfies $\phi(-F)=0$. Now to every $F$ one can assign a number $\nu(F)$ which is the lowest possible degree of such a $\phi$. It is then calculated that $$\nu(x^2y^4+y^2z^4+z^2x^4-3x^2y^2z^2)=\nu(x^4y^2+x^2y^4+z^6-3x^2y^2z^2)=3.$$ In the end he poses the problem of whether one can have $\phi (u)=u^{\nu(F)}+\sigma$ (which coincides with the question you ask), or for example, if there can exist a form which is not a sum of squares but the cube of it is. Judging by the papers citing the one above, it seems like the question is still open.

Answer by Bruce Reznick for when is the power of a nonnegative polynomial a sum of squares?

2011-01-28T21:45:15Z

Motzkin's original proof shows that $x^4y^2 + x^2y^4 + z^6 - a x^2y^2z^2$ is psd and not sos for any $a$ in the interval $(0,3]$. If you take $a = .02$ say, it is reasonably simple, though messy, to show that $(x^4y^2 + x^2y^4 + z^6 - .02x^2y^2z^2)^3$ is a sum of squares; in fact, it's a sum of binomial squares $(x^b y^c z^d - x^e y^f z^g)^2$, where $b+c+d=e+f+g=9$. The idea is to look at any monomial with a negative coefficient and make it into the middle term of this square, in a way that the other two terms are still in the Newton polytope. For example, one term in the given cube is $-.06x^10y^6z^2$, which is "handled" by $.03(x^6y^3 - x^4y^3z^2)^2$. It's sort of messy to work out, but I've convinced myself (at least) that it's true.

Answer by J.C. Ottem for when is the power of a nonnegative polynomial a sum of squares?

2011-01-31T15:04:39Z

Here's an explicit example. The polynomial $f=x^{4} y^{2}+x^{2} y^{4}-x^{2} y^{2}+1$ is not a sum of squares (as one can check using Motzkin's original proof or by computer). On the other hand, the polynomial $f^3$ can be written as a sum of squares, $$f^3=c_1F_1^2+c_2F_2^2+\ldots+c_{19}F_{19}^2$$ where the coefficients $c_i$ and polynomials $F_i$ are listed below.

I guess I should mention the software I used for computing this, namely the package "SOS.m2" for Macaulay2. This package has a function 'getSOS' which spits out a sum of squares representation of a given polynomial. See this link for details. The point is that the problem of finding such a representation can be viewed as a problem of semi-definite programming, and can be solved in reasonable time if the degree is small. In particular, this gives the algorithm you mention for checking whether a polynomial is non-negative.

EDIT: If anyone is interested, I have uploaded the Macaulay2 code here.

Now for the coefficients $c_i$:

(c1..c19)=(146/17,146/17,146/17,4036391/1186250,4036391/1186250,4036391/1186250,
       74/25,1847624417319/1971413728310,431999528319079/461906104329750,
       1847624417319/1971413728310,1847624417319/1971413728310,431999528319079/
       461906104329750,431999528319079/461906104329750,8243/10693,1032024/
       1393067,16675964223443/35265267617884,16675964223443/35265267617884,
       389070/559013,16675964223443/35265267617884)

And the polynomials $F_i$:

(F_1,...,F_19)=(-459/3650 x^4 y^4-1071/3796 x^4 y^2-1071/3796 x^2
   y^4+x^2 y^2-17/73,-17/73 x^6 y^3-1071/3796 x^4 y^5+x^4
   y^3-459/3650 x^2 y^3-1071/3796 x^2 y,-1071/3796 x^5 y^4-17/73
   x^3 y^6+x^3 y^4-459/3650 x^3 y^2-1071/3796 x
   y^2,-65670975/137237294 x^5 y^4+8569925/68618647 x^3 y^6+x^3
   y^2-65670975/137237294 x y^2,8569925/68618647 x^6
   y^3-65670975/137237294 x^4 y^5+x^2 y^3-65670975/137237294 x^2
   y,x^4 y^4-65670975/137237294 x^4 y^2-65670975/137237294 x^2
   y^4+8569925/68618647,-175/629 x^5 y^3-175/629 x^3 y^5+x^3
   y^3-175/629 x y,x^4 y^2-421805182124/9238122086595 x^2
   y^4-80070895463/1231749611546,x^2
   y^4-1201063431945/17632633808942,-80070895463/1231749611546 x^6
   y^3-421805182124/9238122086595 x^4 y^5+x^2
   y,-421805182124/9238122086595 x^5 y^4-80070895463/1231749611546 x^3
   y^6+x y^2,x^5 y^4-1201063431945/17632633808942 x^3
   y^6,-1201063431945/17632633808942 x^6 y^3+x^4 y^5,-21157/107159
   x^5 y^3-21157/107159 x^3 y^5+x y,-21157/86002 x^5 y^3+x^3
   y^5,x^6 y^3,1,x^5 y^3,x^3 y^6)