Newton Polytopes And Sums Of Squares

For a polynomial $p$ define its Newton Polytope $\mathcal{N}(p)$ to be the convex hull of the vectors of exponents of monomials that occur in $p$. For example, if $p=x_1x_2^2+x_2^2+x_1x_2x_3$ then $\mathcal{N}(p)=\operatorname{conv} \left(\left\{(1,2,0),(0,2,0),(1,1,1)\right\}\right)$, which is a triangle in $\mathbb{R}^3$.

Show that if $p=\sum q_i^2$ then $$\mathcal{N}({q_i}) \subseteq \frac{1}{2}\mathcal{N}(p).$$


Solution:

Thanks for the hint:
Let $v$ be a vertex of conv$(\bigcup \mathcal{N}(q_i))= K$ and suppose, seeking a contradiction, that $2v \notin \text{supp}(p)$. This means that $x^{2v}$ must occur as a ''cross term" in some $q_i^2$ (lest all coefficients of $x^{2v}$ be squares). That is, $2v=u+w$ for $u,w$ different from $v$. But then $v=\frac{1}{2}(u+w)$ is not a vertex of $K$.

So the double of every vertex of $K$ is a member of $\text{supp}(p) \subset \mathcal{N}(p)$. Since $2K$ is a polytope, it is the convex hull of its vertices. Since all vertices of $2K$ are contained in the convex set $\mathcal{N}(p)$, we have $2K \subset \mathcal{N}(p)$. Therefore $2\mathcal{N}(q_i) \subset \mathcal{N}(p)$. -MH

Attempted Soluton: We can show that $2\mathcal{N}({q_i}) \subseteq \mathcal{N}(p)$. Now, fix $i$. $2\mathcal{N}(q_i)$ is the convex hull of twice the exponents of the monomials of $q_i$. Suppose $x^a$ is a monomial in $q_i$. Then $x^{2a}$ is a monomial in $q_i^2$, so $2a$ is one of the points determining $\mathcal{N}(p)$. But it's also one of the points determining $2\mathcal{N}(q_i)$. Since this is true for all $i$, one has $2\mathcal{N}({q_i}) \subseteq \mathcal{N}(p)$.

spb says: this doesn't work. Consider the example $q_1=\sqrt{2}x-\sqrt{2}y, q_2=x^2-1$ so that we have
$$q_1^2=(\sqrt{2}x-\sqrt{2}y)^2=2x^2-4xy+y^2 $$
$$q_2^2=(x^2-1)^2=x^4-2x^2+1,$$
and note that for $a=(1,0)$ we have that $x$ is a monomial of $q_1$ and $x^{2}$ is a monomial of $q_1^2$ but $2a$ is NOT in the support of $p=q_1^2+q_2^2$ (i.e., $x^2$ is NOT a monomial of $p$, so it isn't one of the points determining $\mathcal{N}(p)$). The problem is that a 'square term' of $q_i^2$ might be a 'cross term' of $q_j^2$ and so square terms might not show up in $p$. In yet another way, $\operatorname{supp}(q_i)\nsubseteq \frac{1}{2} \operatorname{supp}(p)$ in general. I should mention I've been obsessing about this problem since 3 AM last night and if anyone knows a solution to this problem please tell me. I should also mention that this is the same 'solution' that I had originally on the day when these problems were assigned and it was only last night when I started TeXing that I realized the mistake.

Indeed, this problem is a bit more delicate than it looks. Reznick gives a short but nontrivial proof in "EXTREMAL PSD FORMS WITH FEW TERMS" using limits. See Theorem 1. I have seen this result dismissed as a trivial observation several times (in lectures and papers). Unfortunately, I think most of us manage to convince ourselves with something like the above argument. -MH

I agree that this problem is harder than it looks but there is a simple proof. As a hint consider the convex hull of all the Newton polytopes of the $q_i$. Prove that twice this big convex hull is contained in $P$. Greg B.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License