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.