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 .

## Newton Polytopes

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.

## References

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”