MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 added 100 characters in body

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,
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)

4 deleted 53 characters in body

Here is

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 computing a sum of squares representation the problem of finding such a polynomial $f\ge 0$ representation can be transferred to viewed as a problem of semidefinite semi-definite programming, and can be computed 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.

Now for the coefficients $c_i$:

{c_1,...,c_19}={146/17,146/17,146/17,4036391/1186250,4036391/1186250,4036391/1186250,

(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

(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}
)


 
 
 
3 added 4 characters in body

Here is 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, $$c_1F_1^2+c_2F_2^2+\ldots+c_{19}F_{19}^2$$ $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 computing a sum of squares representation of a polynomial$f\ge 0$can be transferred to a problem of semidefinite programming, and can be computed in reasonable time if the degree is small. In particular, this gives the algorithm you mention for checking whether a polynomial is non-negative. Now for the coefficients$c_i$: {c_1,...,c_19}={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}

2 added 215 characters in body
1