Sums of Squares – Part 2: Motzkin

In the previous blog post we observed that if a polynomial g could be written as a sum \sum_{i=1}^n h_i^2 where each h_i is a polynomial, then g must be non-negative. We then asked if the converse was true. That is, if g is a non-negative polynomial, can g 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 f by looking at the values of \lambda such that g = f - \lambda 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

g(x,y) = x^4y^2 +x^2y^4-3x^2y^2+1.

We wish to prove two things about this polynomial. The first claim is that g(x,y) \ge 0 for all x,y \in \mathbb{R} and the second claim is that g 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 n \in \mathbb{N} and all a_1,a_2,\ldots, a_n \ge 0, we have that

\left(a_1a_2\ldots a_n\right)^{1/n} \le \frac{a_1+a_2+\ldots+a_n}{n}.

We will apply this inequality with n = 3, a_1 = x^4 y^2, a_2 = x^2 y^4 and a_3 = 1. This gives that

\left(x^4 y^2 x^2 y^4 1\right)^\frac{1}{3} \le \frac{x^4 y^2 + y^2 x^4 +1 }{3}.

Simplifying the left hand side and multiplying both sides by 3 gives that

3x^2 y^2 \le x^4 y^2 + y^2 x^4 + 1.

Since our Motzkin polynomial g is given by g(x,y) = x^4 y^2 + y^2 x^2 - 3x^2 y^2 +1, the above inequality is equivalent to g(x,y) \ge 0.

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 f has n variables, then the Newton polytope of f, denoted N(f) is a convex subset of \mathbb{R}^n. To define N(f) we associate a point in \mathbb{R}^n to each term of the polynomial f based on the degree of each variable. For instance the term 3x^2y^4 is assigned the point (2,4) \in \mathbb{R}^2 and the term 4xyz^3 is assigned the point (1,1,3) \in \mathbb{R}^2. Note that the coefficients of the term don’t affect this assignment.

We then define N(f) to be the convex hull of all points assigned to terms of the polynomial f. For instance if f(x,y) = x^4y^3+5x^3y - 7y^3+8, then the Newton polytope of f is the following subset of \mathbb{R}^2.

Note again that changing the non-zero coefficients of the polynomial f does not change N(f).

Now suppose that our polynomial is a sum of squares, that is f = \sum_{i=1}^n h_i^2. It turns out the the Newton polytope of f can be defined in terms of the Newton polytopes of h_i. In particular we have that N(f) =2X where X is the convex hull of the union of N(h_i) for i = 1,\ldots, n.

To see why this is true, note that if a and b are the points corresponding to two terms p and q, then a+b corresponds to pq. Thus we can see that every term of f corresponds to a point that can be written as a+b for some a,b \in N(h_i). It follows that N(f) \subseteq 2X.

Conversely note that if we have terms p, q, r corresponding to points a,b, c and pq = r^2, then a+b = 2c. It follows that if c is a vertex in X corresponding to the term r in some polynomial h_i and p,q are two terms in a polynomial h_j such that pq = r^2, then p=q=r. This is because if r was not equal to either p or q, then the point c would not be a vertex and would instead lie on the line between the points assigned to p and q.

It follows that if c is a vertex of X with corresponding term r, then r^2 appears with a positive coefficient in f = \sum_{i=1}^n h_i. It follows that 2X \subseteq N(f) and so 2X = N(f).

Not a sum of squares

Let’s now take another look at the Motzkin polynomial which is defined to be

g(x,y) = x^4y^2 + x^2 y^4 - 3x^2y^2 + 1.

Thus the Newton polytope of g has corners (4,2), (2,4), (0,0) and looks like this

Thus if the Motzkin polynomial was a sum of squares g = \sum_{i=1}^n h_i^2, then the Newton polytope of each h_i must be contained in \frac{1}{2}N(g). Now \frac{1}{2}N(g) looks like this

The only integer points contained in \frac{1}{2}N(g) are (0,0), (1,1), (1,2) and (2,1). Thus each h_i must be equal to h_i(x,y) = a_i x^2 y+b_i xy^2 + c_i xy + d_i. If we square this polynomial we see that the coefficient of x^2 y^2 is c_i^2. Thus the coefficient of x^2y^2 in \sum_{i=1}^n h_i^2 must be c_1^2+c_2^2+\ldots +c_n^2 \ge 0. But in the Motzkin polynomial, x^2y^2 has coefficient -3.

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”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s