|
|
A note on mediated simplices | Arxiv
Abstract. Many homogeneous polynomials that arise in the study of sums of
squares and Hilbert’s 17th problem are those formed by monomial substitutions into
the arithmetic-geometric inequality. In 1989, Reznick [Math. Ann. 283, 431–464]
gave a necessary and sufficient condition for such a form to have a representation
as a sum of squares of forms, involving the arrangement of lattice points in the
simplex whose vertices were the $n$-tuples of the exponents used in the substitution.
Further, a claim was made, and not proven, that sufficiently large dilations of any
such simplex will also satisfy this condition. The aim of this short note is to prove
the claim, and provide further context for the result, both in the study of Hilbert’s
17th Problem and the study of lattice point simplices.
1. Introduction
In 1989, the second author considered [14] a class of homogeneous polynomials
(forms) which had arisen in the study of Hilbert’s 17th Problem as monomial substitutions into the arithmetic-geometric inequality. The goal was to determine when
such a form, which must be positive semidefinite, had a representation as a sum
of squares of forms. The answer was a necessary and sufficient condition involving
the arrangement of lattice points in the simplex whose vertices were the $n$-tuples of
the exponents used in the substitution. Further, a claim was made in [14], and not
proven, that sufficiently large dilations of any such simplex will also satisfy this condition. The aim of this short note is to prove the claim, and provide further context
for the result, both in the study of Hilbert’s 17th Problem and the study of lattice
point simplices. The second author is happy to acknowledge that the return to this
claim was triggered by two nearly simultaneous events: an invitation to speak at the
2019 SIAM Conference on Applied Algebraic Geometry, and a request from Jie Wang
for a copy of [15], which was announced in [14] but never written.
2. Preliminaries
We work with homogeneous polynomials (forms) in $\mathbb{R}[x]=\mathbb{R}\left[x_{1}, \ldots, x_{n}\right]$, the ring of real polynomials in $n$ variables. Write the monomial $x_{1}^{\alpha_{1}} \cdots x_{n}^{\alpha_{n}}$ as $x^{\alpha}$, for $\alpha=$ $\left(\alpha_{1}, \ldots, \alpha_{n}\right) \in \mathbb{Z}^{n}$. For $S \subset \mathbb{Z}^{n},\operatorname{cvx}(S)$ denotes the convex hull of $S$. For $p(x)=\sum_{\alpha} c(\alpha) x^{\alpha} \in \mathbb{R}[x]$, let $\operatorname{supp}(p)=\{\alpha \mid c(\alpha) \neq 0\}$, write $\operatorname{New}(p)$ for the Newton polytope of $p$, that is, $\operatorname{New}(p)=\operatorname{cvx}(\operatorname{supp}(p))$, and let $C(p)=\operatorname{New}(p) \cap \mathbb{Z}^{n}$.
A form $p \in \mathbb{R}[x]$ is positive semidefinite or psd if $p(x) \geq 0$ for all $x \in \mathbb{R}^{n}$. It is a sum of squares or sos if $p=\sum_{j} h_{j}^{2}$ for forms $h_{j} \in \mathbb{R}[x]$. Clearly, every sos form is psd. In 1888, D. Hilbert [8] proved that there exist psd forms which are not sos.
The arithmetic-geometric inequality (or AGI) states that if $t_{i} \geq 0, \lambda_{i} \geq 0$ and $\sum_{i=1}^{n} \lambda_{i}=1$, then
\[
\lambda_{1} t_{1}+\cdots+\lambda_{n} t_{n} \geq t_{1}^{\lambda_{1}} \cdots t_{n}^{\lambda_{n}},
\]
with equality only if the $t_{i}$ 's are equal. In 1891, A. Hurwitz [9] gave a proof of the AGI, in which the key step was setting $\lambda_{i}=a_{i} / N$ where $a_{i} \in \mathbb{Z}^{n}$ with $\sum a_{i}=N$ for even $N$, and $t_{i}=x_{i}^{N}$. Under this substitution and a scaling, one obtains the form
\[
a_{1} x_{1}^{N}+\cdots+a_{n} x_{n}^{N}-N x_{1}^{a_{1}} \cdots x_{n}^{a_{n}} .
\]
Hurwitz then proves that each such form is sos (in fact, a sum of squares of binomials), and hence psd. (He cites [8] to observe that this is not automatic.) For example, after a scaling and relabeling of the $x_{i}$ 's as $x, y, z$, we have
\[
\begin{gathered}
H(x, y, z):=x^{6}+y^{6}+z^{6}-3 x^{2} y^{2} z^{2} \\
=\frac{3}{2}\left(x^{2} y-y z^{2}\right)^{2}+\left(x^{3}-x y^{2}\right)^{2}+\frac{1}{2}\left(x^{2} y-y^{3}\right)^{2}+\left(z^{3}-y^{2} z\right)^{2}+\frac{1}{2}\left(y z^{2}-y^{3}\right)^{2} .
\end{gathered}
\]
For more on Hurwitz' proof, see [13], where Eq. (3.5) gives a representation of $H$ as a sum of four squares, one of which is the square of a trinomial.
The first explicit example of a psd form which is not sos was presented in 1967 by T. Motzkin [11]. It, too, arises as a substitution into the AGI: let $t_{1}=x^{4} y^{2}, t_{2}=$ $x^{2} y^{4}, t_{3}=z^{6}, \lambda_{i}=\frac{1}{3}$ and scale:
\[
M(x, y, z):=x^{4} y^{2}+x^{2} y^{4}+z^{6}-3 x^{2} y^{2} z^{2}
\]
The proof that $M$ is not sos was based on a preliminary argument that if $M=\sum h_{j}^{2}$, then $h_{j}(x, y, z)=c_{1 j} x^{2} y+c_{2 j} x y^{2}+c_{3 j} z^{3}+c_{4 j} x y z$ : the coefficient of $x^{2} y^{2} z^{2}$ in $\sum h_{j}^{2}$ is then $\sum c_{4 j}^{2} \neq-3$. The argument of Motzkin's proof was formalized in [12], where it is shown that, in general, $p=\sum h_{j}^{2}$ implies that $C\left(h_{j}\right) \subseteq \frac{1}{2} C(p)$.
The following machinery was developed in [12,14] to analyze such forms. Consider a set $\mathcal{U}=\left\{u_{1}, \ldots, u_{m}\right\}$ with $u_{i} \in\left(2 \mathbb{Z}_{\geq 0}\right)^{n}$ and $\sum_{j=1}^{m} u_{i j}=2 d$. We further assume that $\operatorname{cvx}(\mathcal{U})$ is a simplex, and $w \in \operatorname{cvx}(\mathcal{U}) \cap \mathbb{Z}^{n}$ has the barycentric representation $w=\sum \lambda_{i} u_{i}, \lambda_{i} \geq 0$ and $\sum_{i=1}^{m} \lambda_{i}=1$. In this way, the substitution $\left\{t_{i}=x^{u_{i}}\right\}$ into the AGI yields a psd form of degree $2 d$
\[
p(x)=\lambda_{1} x^{u_{1}}+\cdots+\lambda_{m} x^{u_{m}}-x^{w} .
\]
This was called an agiform in [14] and the set $\mathcal{U}$ was called a trellis. Observe that $C(p)=\operatorname{cvx}(\mathcal{U}) \cap \mathbb{Z}^{n}$. More generally, a polynomial $p(x)=\sum_{i=1}^{m} a_{i} x^{u_{i}}-b x^{w}$ with $a_{i}>0$ for $i=1, \ldots, m$ is called a circuit polynomial. Circuit polynomials have recently been studied by M. Dressler, J. Forsgård, S. Iliman, T. de Wolff, and J. Wang; see for example $[10],[2],[3],[16]$. Interest in circuit polynomials is in part due to their use in finding efficiently-computable certificates of positivity based on the AGI, which are then independent of sos representations.
There is a geometric criterion which determines whether an agiform is sos.
Definition. Suppose $\mathcal{U}$ is given as above, and let $S \subset \operatorname{cvx}(\mathcal{U}) \cap \mathbb{Z}^{n}$ be a set of lattice points containing the $u_{i}$ 's. Then $S$ is $\mathcal{U}$-mediated if for every $y \in S$, either $y=u_{i}$ for some $i$, or there exist $z_{1} \neq z_{2} \in S \cap(2 \mathbb{Z})^{n}$ so that $y=\frac{1}{2}\left(z_{1}+z_{2}\right)$. In other words, $S$ is $\mathcal{U}$-mediated if every point in $S$ is either a vertex of $\mathcal{U}$ or an average of two different even points in $S$.
Theorem 2.1. [14, Cor. 4.9] With $\mathcal{U}, \lambda_{i}$ as above, the agiform $\lambda_{1} x^{u_{1}}+\cdots+\lambda_{m} x^{u_{m}}-x^{w}$ is sos if and only if there is a $\mathcal{U}$-mediated set containing $w$.
Let $\mathcal{U}_{1}=\{(4,2,0),(2,4,0),(0,0,6)\}$ and $\mathcal{U}_{2}=(\{(6,0,0),(0,6,0),(0,0,6)\} .$ Up to scaling, both $H$ and $M$ are agiforms, since $w=(2,2,2)$ is the centroid to both $\operatorname{cvx}\left(\mathcal{U}_{1}\right)$ and $\operatorname{cvx}\left(\mathcal{U}_{2}\right)$. By Theorem 2.1, $M$ is not sos because $\operatorname{cvx}\left(\mathcal{U}_{1}\right) \cap(2 \mathbb{Z})^{3}=\left\{u_{1}, u_{2}, u_{3}, w\right\}$ and it is impossible to write $w$ as an average of two different members of this set. However, it is easy to check that the set
\[
S=\{(6,0,0),(0,6,0),(0,0,6),(2,2,2),(4,2,0),(2,4,0),(0,2,4),(0,4,2)\}
\]
is $\mathcal{U}_{2}$-mediated, providing an independent proof that $H$ is sos.
We refer the reader to [14] for the separate proofs of the necessity and sufficiency in Theorem 2.1.
3. MAIN THEOREM
The following theorem was asserted in [14, Prop.2.7].
Theorem 3.1. For every integer $k \geq \max \{2, m-2\}, \operatorname{cvx}(k \mathcal{U}) \cap \mathbb{Z}^{n}$ is $(k \mathcal{U})$-mediated.
Corollary 3.2. Any agiform $p \in \mathbb{R}\left[x_{1}, \ldots, x_{n}\right]$ can be written as a sum of squares of forms in the variables $x_{i}^{1 / k}$ for $k \geq \max \{2, m-2\}$.
To prove Theorem 3.1, we show that any non-vertex $w \in \operatorname{cvx}(k \mathcal{U}) \cap \mathbb{Z}^{n}$ is the average of two different points in $\operatorname{cvx}(k \mathcal{U}) \cap(2 \mathbb{Z})^{n}$. The proof for $k \geq m-1$ is easy, while the proof for the remaining case $(m \geq 4$ and $k=m-2)$ is more delicate. We defer the discussion of Corollary $3.2$ to the next section.
We start with some notation and lemmas. First, recall that $t \in \mathbb{R}$ may be written as $t=\lfloor t\rfloor+\{t\}$, where $\lfloor t\rfloor \in \mathbb{Z}$ and $\{t\} \in[0,1)$. If $v=\sum a_{i} u_{i} \in \operatorname{cvx}(k \mathcal{U})$ with $a_{i} \in \mathbb{Z}_{\geq 0}, \sum a_{i}=k$, then we say that $v$ is a bead. Observe that beads are always even.
Lemma 3.3. Suppose $k>1$ and $v \in \operatorname{cvx}(k \mathcal{U})$ is a non-vertex bead. Then $v$ is an average of two different beads in $\operatorname{cvx}(k \mathcal{U})$.
Proof. Suppose that $v=\sum a_{i} u_{i}$ is a non-vertex bead. At least two of the $a_{i}$ 's must be positive; without loss of generality, suppose $a_{1}, a_{2} \geq 1$. Then $v$ is the average of the beads $v \pm\left(u_{1}-u_{2}\right)$ in $\operatorname{cvx}(k \mathcal{U})$ |
|
