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”

Pingback: Sums of Squares – Part 1: Optimization – Maths to Share

The Motzkin Polynomial

Newton Polytopes

Not a sum of squares

References

Share this:

Like this:

Related

One thought on “Sums of Squares – Part 2: Motzkin”

Leave a Reply Cancel reply