In the previous blog post we observed that if a polynomial could be written as a sum where each is a polynomial, then must be non-negative. We then asked if the converse was true. That is, if is a non-negative polynomial, can be written a sum of squares of polynomials? As we saw, a positive answer to this question would allow us to optimize a polynomial function by looking at the values of such that can be written as a sum of squares.
Unfortunately, as we shall see, not all non-negative polynomials can be written as sums of squares.
The Motzkin Polynomial
The Motzkin polynomial is a two variable polynomial defined by
We wish to prove two things about this polynomial. The first claim is that for all and the second claim is that cannot be written as a sum of squares of polynomials. To prove the first claim we will use the arithmetic mean geometric mean inequality. This inequality states that for all and all , we have that
We will apply this inequality with , , and . This gives that
Simplifying the left hand side and multiplying both sides by gives that
Since our Motzkin polynomial is given by , the above inequality is equivalent to .
Thus we have shown that the Motzkin polynomial is non-negative. We now wish to show that it is not a sum of squares. To do this we will first have to define the Newton polytope of a polynomial. If our polynomial has variables, then the Newton polytope of , denoted is a convex subset of . To define we associate a point in to each term of the polynomial based on the degree of each variable. For instance the term is assigned the point and the term is assigned the point . Note that the coefficients of the term don’t affect this assignment.
We then define to be the convex hull of all points assigned to terms of the polynomial . For instance if , then the Newton polytope of is the following subset of .
Note again that changing the non-zero coefficients of the polynomial does not change .
Now suppose that our polynomial is a sum of squares, that is . It turns out the the Newton polytope of can be defined in terms of the Newton polytopes of . In particular we have that where is the convex hull of the union of for .
To see why this is true, note that if and are the points corresponding to two terms and , then corresponds to . Thus we can see that every term of corresponds to a point that can be written as for some . It follows that .
Conversely note that if we have terms corresponding to points and , then . It follows that if is a vertex in corresponding to the term in some polynomial and are two terms in a polynomial such that , then . This is because if was not equal to either or , then the point would not be a vertex and would instead lie on the line between the points assigned to and .
It follows that if is a vertex of with corresponding term , then appears with a positive coefficient in . It follows that and so .
Not a sum of squares
Let’s now take another look at the Motzkin polynomial which is defined to be
Thus the Newton polytope of has corners and looks like this
Thus if the Motzkin polynomial was a sum of squares , then the Newton polytope of each must be contained in . Now looks like this
The only integer points contained in are and . Thus each must be equal to . If we square this polynomial we see that the coefficient of is . Thus the coefficient of in must be . But in the Motzkin polynomial, has coefficient .
Thus the Motzkin polynomial is a concrete example of a non-negative polynomial that is not a sum of squares.
As stated in the first part of this series, these two blog posts are based off conversations I had with Abhishek Bhardwaj last year. I also used these slides to remind myself why the Motzkin polynomial is not a sum of squares.
One thought on “Sums of Squares – Part 2: Motzkin”