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”