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.
Best Answer
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.