when is the power of a nonnegative polynomial a sum of squares? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:26:23Z http://mathoverflow.net/feeds/question/53047 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/53047/when-is-the-power-of-a-nonnegative-polynomial-a-sum-of-squares when is the power of a nonnegative polynomial a sum of squares? Colin Tan 2011-01-24T12:04:33Z 2011-03-09T05:30:12Z <p>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.</p> <p>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$?</p> <p>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$. </p> <p>This question is me wondering whether such a technique of consider the radical of sum of squares is vacuous.</p> http://mathoverflow.net/questions/53047/when-is-the-power-of-a-nonnegative-polynomial-a-sum-of-squares/53458#53458 Answer by Gjergji Zaimi for when is the power of a nonnegative polynomial a sum of squares? Gjergji Zaimi 2011-01-27T06:18:31Z 2011-01-27T06:18:31Z <p>This doesn't answer your question but it's more of a comment. In the paper <a href="http://www.springerlink.com/content/u41867l6173450j6/" rel="nofollow">"Integral solution of Hilbert's seventeenth problem"</a>, 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.</p> http://mathoverflow.net/questions/53047/when-is-the-power-of-a-nonnegative-polynomial-a-sum-of-squares/53653#53653 Answer by Bruce Reznick for when is the power of a nonnegative polynomial a sum of squares? Bruce Reznick 2011-01-28T21:45:15Z 2011-01-29T05:15:24Z <p>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. </p> http://mathoverflow.net/questions/53047/when-is-the-power-of-a-nonnegative-polynomial-a-sum-of-squares/53892#53892 Answer by J.C. Ottem for when is the power of a nonnegative polynomial a sum of squares? J.C. Ottem 2011-01-31T15:04:39Z 2011-02-01T09:22:41Z <p>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.</p> <p>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 <a href="http://control.ee.ethz.ch/~hpeyrl/Projects/SOS/rational_sos.php" rel="nofollow">link</a> 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.</p> <p>EDIT: If anyone is interested, I have uploaded the Macaulay2 code <a href="http://folk.uio.no/johnco/SOSrun.txt" rel="nofollow">here</a>.</p> <p>Now for the coefficients $c_i$:</p> <pre><code>(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) </code></pre> <p>And the polynomials $F_i$:</p> <pre><code>(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) </code></pre>