# Polynomials that are sums of squares

Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials?

By way of background, if we one replaces "polynomial" by "rational function" then there is such an algorithm, because a rational function is a sum of squares iff it is positive definite. But this equivalence fails for polynomials.

-

Yes, the group of Parillo developed an algorithm and a matlab toolbox they called SOSTOOLS

There is a degree of complexity though, I am not an expert in their algorithm so I don't know how efficient their algorithm is. I remember reading that the sum of squares polynomials are dense in the space of positive semidefinite polynomials by some norm.. I think it was L1 norm. And if you know that your polynomial is positive and convex, then its "more likely" that its a sum of squares (as far as I know, no one has yet shown that there are convex (multivariate) polynomials that are positive but not sum of squares).

-

Jose writes: "if you have a polynomial that is positive semidefinite, more likely than not it is a sum of squares"

This sort of statement is very sensitive to what probability distribution you use on the space of all polynomials. I am sure there are formulations in which it is true; here is one in which it is false.

Fix d greater than 1. Let Poly(2d,n) be the vector space of homogenous*, degree 2d polynomials in n variables. Let's choose polynomials uniformly at random from unit sphere in this space. Blekherman has computed that the probability that a polynomial is positive is ~ n^{-1/2}, while the probability that it is a sum of squares is ~ n^{-d/2}. So, for n large, almost all positive polynomials are not sums of squares.

Blekherman also has a recent preprint showing that, in the same sense, almost all positive convex polynomials are not sums of squares.

* If you don't like working with homogenous polynomials, notice that Poly(2d,n) is also the vector space of inhomogenous polynomials in n-1 variables with degree at most d. Just plug in 1 for the last variable. Under this correspondence, a polynomial is nonnegative on R^n if and only if it is nonnegative on R^{n-1} x {1}. The property of being strictly positive is not preserved by this transformation, but the polynomials which are nonnegative and not strictly positive form a set of measure 0.

-
I agree, to say "more unlikely" might need a bit more explanation. I will have to find my source and post it. Thanks for pointing out the papers of Blekherman. What I found a bit disturbing was that he used space of homogenous polynomials and made a conclusion over them,but the title and the work seems to confuse me. Is it known that if you use the density computed by Blekhherman for HOMOGENOUS positive polynomials one gets something of the same range for ANY positive polynomial? Also his paper on convex poly, does admit that there are no known non SOS polynomials that are convex – Jose Capco Nov 1 '09 at 6:36
Here is a paper by Netzer and Lassere: tinyurl.com/y8unahb Could anyone teach me how to add hyperlinks when commenting? Anyway, in the paper they used l1-norm on the coefficient.. and from SOS being dense in PSD using that norm i concluded my remark. But to say "it is dense" is definitely not the same as "it is more", sorry for that. – Jose Capco Nov 1 '09 at 7:21
Nothing to apologize for. It looks to me like the difference can be summarized in this way up in this way: If you hold n fixed and send d to infinity, then "most" positive polynomials are sums of squares. If you hold d fixed and send n to infinity then "most" are not. Of course, in both cases, you also have to specify the norm being used on the vector space of polynomials. – David Speyer Nov 1 '09 at 12:59