|
5
|
|
edited Feb 1 2011 at 9:22 |
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
|
|
edited Jan 31 2011 at 21:43 |
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
|
|
edited Jan 31 2011 at 19:33 |
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
|
|
edited Jan 31 2011 at 16:07 |
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). But On the other hand, the polynomial $f^3$ can be written as a sum of squares,
ahem$c_1F_1^2+c_2F_2^2+\ldots+c_{19}F_{19}^2$ $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" 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}
|
|
|
|
|
1
|
|
answered Jan 31 2011 at 15:04 |
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. But $f^3$ can be written as, ahem $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" 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.
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}
|
|
|
