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

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.

-
Does Motzkin's proof that his f is not a sum of squares also show that f^N is not a sum of squares for odd N? Or could his polynomial itself already a potential positive answer to your question? –  JSE Jan 27 '11 at 4:39
Hi JSE. The proof of that Motzkin's polynomial is not a sum of squares that I know is given by Reznick. This proof is almost brute force. Since the given polynomial is of low degree (deg 6) so the brute force method works. However, raising to high power makes such brute force method difficult. –  Colin Tan Jan 27 '11 at 4:43
this still leaves open as to whether a high power of Motzkin's power is a potential answer to my question. –  Colin Tan Jan 27 '11 at 4:58
In the first sentence of your question you forgot the attribute "non-negative". –  Andrei Moroianu Jan 27 '11 at 8:55
I've changed the title. thanks andrei –  Colin Tan Jan 28 '11 at 3:27

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.

-
thanks Bruce for your answer! –  Colin Tan Jan 29 '11 at 6:56

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)

-
thanks JC for your explicit example. I really should learn to use scientific computing. –  Colin Tan Feb 1 '11 at 12:24
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.