When is a power of a nonnegative polynomial a sum of squares?

Question

There are nonnegative polynomials that are not sums 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,\dotsc,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 1

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 2

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 (Wayback Machine). 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 (Wayback Machine).

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)

Answer 3

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.