Polynomials and Newton Polygons

(Guest author Andrew here!)

A good exercise for Olympiad students is to prove the following:

A real polynomial $f(x)\in \R[x]$ which is everywhere non-negative (psd, short for positive semi-definite) must be a sum of squares (sos). 

This is in some sense an algebraic witness to the analytic property of being non-negative, and is an example of what is known as a Positivstellensatz. One might reasonably ask whether this extends to the case of multiple variables, and it turns out the answer is no. 

Consider the two variable polynomial $g(x,y)=x^4y^2+x^2y^4-3x^2y^2+1$ (the Motzkin polynomial). Non-negativity follows from the AM-GM inequality. But how can we show that it isn't a sum of squares?

We now introduce an object known as the Newton polytope. Given a polynomial $f$, 

• To every monomial with non-zero coefficient, assign a point whose $i^{th}$ coordinate is the degree of the $i^{th}$ variable in that monomial, e.g. assign to $x_1^n$ the point $(n, 0)$.
• The Newton polytope $N(f)$ of a polynomial is the convex hull of the points assigned to each monomial.

Note this is independent of the actual coefficients. And if $p_1,p_2$ are monomials which are assigned points $a_1,a_2$ respectively, then $p_1p_2$ is assigned the point $a_1+a_2$.

Claim: if $f= \sum_i g_i^2$, then the Newton polytope of $f$ is $2A$ where $A$ is the convex hull of all the points corresponding to the monomials contained in the $g_i$. 

Proof: We show that $2A \subseteq N(f)$ and leave the other direction to the reader.

Note that if $p_1, p_2, p_3$ are monomials assigned points $a_1, a_2,a_3$ respectively and $p_1p_2=p_3$ then $a_1+a_2=2a_3$. So if $a_3$ is a vertex in $A$ corresponding to the term $r$ in some $g_i$, and $p_1,p_2$ are terms in a polynomial $h_j$ such that $p_1p_2=r^2$, then $p_1=p_2=r$. If $r$ weren't equal to either $p_i$ then $a_3$ wouldn't be a vertex and would be on the line between $a_1$ and $a_2$.

Hence if $a_3$ is a vertex of $A$ corresponding to $p_3$, then $p_3^2$ appears with a positive coefficient in $f$. $\blacksquare$

Proof that the Motzkin polynomial is not sos: Now we can draw the Newton polytope $N(g)$ of the Motzkin polynomial. If it were a sum of squares $g= \sum_ih_i^2$, then the Newton polytope of each $h_i$ would have to be contained in $\frac{1}{2} N(g)$, which upon inspection, forces each $h_i$ to be of the form $h_i(x_1,x_2)=a_ix_1^2x_2+b_ix_1x_2^2+c_ix_1x_2+d_i$. In particular, in any such expression the coefficient of $(x_1x_2)^2$ must be positive as a sum of squares, but in the Motzkin polynomial the coefficient is $-3$, a contradiction. $\blacksquare$

One could also attempt to bash this out by hand since the degree is so low, but that isn't the correct solution in my opinion, since the Newton polytope is useful for many other things as well (apart from systematizing bashes). We have defined it for two variable polynomials, but the reader can figure out how this extends readily to any number of variables by considering the corresponding $\mathbb{Z}$-lattice in $\mathbb{R}^n$.

Remarks:

• There are many other polynomials which are psd but not sos, for example the $n=5$ case of IMO 1971 Q1. See here for a longer discussion.
• Hilbert's 17th problem, solved in 1920 by Artin in the affirmative, asks whether it's possible to write any psd polynomial as a sum of squares of rational functions. This is part of a broader philosophy of deciding to what extent positivity comes from the most trivial inequality that sums of squares are non-negative. Another way in which this is much more subtle is that cubes of Motzkin-like polynomials are in fact sums of squares, so there is a polynomial 'witness' to their positivity after all.
• It's interesting that AM-GM suffices to show that the Motzkin polynomial is psd even though it isn't a sum of squares since one proof of the AM-GM inequality goes by showing it for 2 variables using that $(x-y)^2 \geq 0$, then repeatedly doubling to get it for $2^n$ variables, before finally substituting special values in to reduce the number of variables. 
• There are a number of reasonable things which break when the polynomial is allowed to have multiple variables. Here's another: for which $n$ does an $n$-variable polynomial necessarily attain its bounds (if finite)?
• Denote by $F_{d,n}$ the set of (even) degree $d$ homogeneous polynomials in $n$ variables, $P_{d,n}$ the subset of $F_{d,n}$ of all psd polynomaials, and $\Sigma_{d,n}$ the subset of $F_{d,n}$ consisting of the sums of squares. Hilbert proved (nonexplicitly) that these are equal if and only if $n\leq 2$ or $d=2$ or $(n,d)=(3,4)$. One can homogenise the Motzkin polynomial and multiply by even powers of say $x_1$ to exhibit explicit examples. The other psd but not sos polynomials cover the cases not covered by this technique.

Here's another example of how one might show things are irreducible by using Newton polytopes (again one could in theory bash some of the cases covered, but it's extremely painful and may simply not work).

If the Newton polytope of $f$ can not be written as a Minkowski sum of two smaller polytopes, then $f$ is irreducible. It is surprisingly easy to test whether a lattice polygon in $\mathbb{R}^2$ can be written as a Minkowski sum of a smaller lattice polygon. Let $A$ be a lattice polytope. Travel around $\partial A$ and write down the vectors pointing from each lattice point to the next lattice point; call this sequence of vectors $v(A)$.

For example, if our polynomial is $ay^2+by+cxy+d+ex+fx^2+gx^3$ with $adg\neq0$, then the lattice points on the boundary are $(0,2), (0,1), (0,0), (1,0), (2,0), (3,0)$. So $v(A)=( (0,-1), (0,-1), (1,0), (1,0), (1,0), (-3,2) )$. (Note that (1,1) is not on the boundary of the triangle.)

It turns out that $v(A+B)$ is simply the sequences $v(A)$ and $v(B)$, interleaved by sorting their slopes. So, if $A$ can be written as the Minkowski sum $A_1+A_2$, we must be able to partition $v(A)$ into two disjoint sub-sequences, each of which sums to zero. In the above example, this can't be done, so any polynomial of the above form must be irreducible.

Exercise in applying this method: fix $k$ a field (e.g. $\mathbb Q$, $\mathbb R$, $\mathbb C$) and $f = X_1^{a_1} \cdots X_n^{a_n}-1$ a $n$-variable polynomial. When is this polynomial irreducible in $k[X_1,\dots,X_n]$?