Nonnegative Polynomials and Circuit Polynomials
The concept of sums of nonnegative circuit polynomials (SONC) was recently introduced as a new certificate of nonnegativity especially for sparse polynomials. In this paper, we explore the relationship between nonnegative polynomials and SONC polynomials. As a first result, we provide sufficient conditions for nonnegative polynomials with general Newton polytopes to be SONC polynomials, which generalizes the previous result on nonnegative polynomials with simplex Newton polytopes. Secondly, we prove that every SONC polynomial admits a SONC decomposition without cancellation. In other words, SONC decompositions can exactly preserve the sparsity of nonnegative polynomials, which is dramatically different from the classical sum of squares (SOS) decompositions and is a key property to design efficient algorithms for sparse polynomial optimization based on SONC decompositions.
\section{Introduction}
A real polynomial $f\in{\mathbb{R}}[{\mathbf{x}}]={\mathbb{R}}[x_1,\ldots,x_n]$ is called a {\em nonnegative polynomial} if its evaluation on every real point is nonnegative. All of nonnegative polynomials form a convex cone, denoted by PSD. Certifying nonnegativity of polynomials is a central problem of real algebraic geometry and has a deep connection with polynomial optimization. A classical approach for handling this problem is sum of squares (SOS) decompositions. From the perspective of computation, checking whether a polynomial is a sum of squares boils down to a semidefinite programming (SDP) problem involving a positive semidefinite matrix of size $\binom{n+d}{d}$, where $n$ is the number of variables and $2d$ is the degree of the polynomial \cite{pa,pa1}. Hence, the size of the corresponding SDP problem grows rapidly with $n,d$ increasing, which greatly limits the scalability of this approach. 

The concept of sums of nonnegative circuit polynomials recently introduced by Iliman and Wolff in \cite{iw} is a substitute of sums of squares of polynomials to represent nonnegative polynomials. A polynomial $f$ is called a {\em circuit polynomial} if it is of the form
\begin{equation}
f({\mathbf{x}})=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}},
\end{equation}
where $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}\subseteq(2{\mathbb{N}})^n$ comprises the vertices of a simplex, ${\boldsymbol{\beta}}$ is an interior point of the convex hull of $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}$ and $c_i>0$ for $i=1,\ldots,m$. For every circuit polynomial $f$, we associate it with the {\em circuit number} defined as $\Theta_f:=\prod_{i=1}^m(c_i/\lambda_i)^{\lambda_i}$, where the $\lambda_i$'s are uniquely given by the convex combination ${\boldsymbol{\beta}}=\sum_{i=1}^m\lambda_i{\boldsymbol{\alpha}}_i \textrm{ with } \lambda_i>0 \textrm{ and } \sum_{i=1}^m\lambda_i=1$. Then the nonnegativity of $f$ is easy to decide: $f$ is nonnegative if and only if either ${\boldsymbol{\beta}}\in(2{\mathbb{N}})^n$ and $d\le\Theta_f$ or ${\boldsymbol{\beta}}\notin(2{\mathbb{N}})^n$ and $-\Theta_f\le d\le\Theta_f$.

We say that a polynomial is a {\em sum of nonnegative circuit polynomials (SONC)}, if it can be written as a sum of nonnegative circuit polynomials. The set of SONC polynomials also forms a convex cone. Clearly, an explicit representation of a SONC polynomial as a sum of nonnegative circuit polynomials provides a certificate of its nonnegativity, which is called a {\em SONC decomposition}. By virtue of SONC decompositions, algorithms were proposed for polynomial optimization problems (see \cite{lw} for the unconstrained case and see \cite{dlw,diw,dkw} for the constrained case). Numerical experiments for unconstrained polynomial optimization problems in \cite{pap,se} have demonstrated the advantage of the SONC-based methods compared to the SOS-based methods especially in the high-degree but fairly sparse case. A comparison with details between SONC and SOS can be found in \cite{se}.

From the perspective of theory, it is natural to ask which types of nonnegative polynomials admit SONC decompositions and how big the gap between the PSD cone and the SONC cone is. In \cite{iw}, it was proved that if the Newton polytope of a polynomial $f$ is a simplex and there exists a point such that all terms of $f$ except for those corresponding to the vertices of the Newton polytope have the negative sign on this point, then $f$ is nonnegative if and only if $f$ is a SONC polynomial (see Theorem \ref{nc-thm2}). The first contribution of this paper is that we generalize this conclusion to polynomials with general Newton polytopes. Specifically, we provide sufficient conditions for nonnegative polynomials with general Newton polytopes to be SONC polynomials in terms of combinatorial structure of the supports (Theorem \ref{npgp-thm7} and Theorem \ref{npmt-thm1}). Moreover, we give a counter example that a nonnegative polynomial does not admit a SONC decomposition if one of these conditions fails.

As the second contribution of this paper, we clarify an important fact that every SONC polynomial can decompose into a sum of nonnegative circuit polynomials by just using the support of the original polynomial (Theorem \ref{sec3-thm2}). In other words, SONC decompositions can exactly preserve the sparsity of polynomials. It is dramatically different from the SOS decompositions of nonnegative polynomials, where extra monomials are needed in general. This key property of SONC decompositions explains the advantage of SONC decompositions for certifying nonnegativity of sparse polynomials compared to the classical SOS decompositions and is crucial to design efficient algorithms for sparse polynomial optimization based on SONC decompositions. 

The rest of this paper is organized as follows. In Section 2, we recall some basic facts on SONC polynomials. After that we consider the problem which types of nonnegative polynomials admit SONC decompositions. We deal with the case of nonnegative polynomials with one negative term in Section 3 and deal with the case of nonnegative polynomials with multiple negative terms in Section 4. In Section 5, we prove that every SONC polynomial decomposes into a sum of nonnegative circuit polynomials with the same support. What's more, we prove that no cancellation is needed in this decomposition.

\section{Preliminaries}
\subsection{Notation and Nonnegative Polynomials}
Let ${\mathbb{R}}[{\mathbf{x}}]={\mathbb{R}}[x_1,\ldots,x_n]$ be the ring of real $n$-variate polynomial, ${\mathbb{R}}^*={\mathbb{R}}\backslash\{0\}$, and ${\mathbb{N}}^*={\mathbb{N}}\backslash\{0\}$. Let ${\mathbb{R}}_+$ be the set of positive real numbers and ${\mathbb{R}}_{\ge0}$ the set of nonnegative real numbers. For a finite set ${\mathscr{A}}\subseteq{\mathbb{N}}^n$, we denote by $\hbox{\rm{cone}}({\mathscr{A}})$ the conic hull of ${\mathscr{A}}$, by $\hbox{\rm{conv}}({\mathscr{A}})$ the convex hull of ${\mathscr{A}}$, and by $V({\mathscr{A}})$ the vertices of the convex hull of ${\mathscr{A}}$. We also denote by $V(P)$ the vertex set of a polytope $P$. We consider polynomials $f\in{\mathbb{R}}[{\mathbf{x}}]$ supported on the finite set ${\mathscr{A}}\subseteq{\mathbb{N}}^n$, i.e. $f$ is of the form $f({\mathbf{x}})=\sum_{{\boldsymbol{\alpha}}\in{\mathscr{A}}}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}$ with $c_{{\boldsymbol{\alpha}}}\in{\mathbb{R}}, {\mathbf{x}}^{{\boldsymbol{\alpha}}}=x_1^{\alpha_1}\cdots x_n^{\alpha_n}$. The {\em support} of $f$ is $\hbox{\rm{supp}}(f):=\{{\boldsymbol{\alpha}}\in {\mathscr{A}}\mid c_{{\boldsymbol{\alpha}}}\ne0\}$ and the {\em Newton polytope} of $f$ is defined as $\hbox{\rm{New}}(f):=\hbox{\rm{conv}}(\hbox{\rm{supp}}(f))$. For a polytope $P$, we use $P^{\circ}$ to denote the interior of $P$. For $m\in{\mathbb{N}}$, let $[m]:=\{1,\ldots,m\}$.

A polynomial $f\in{\mathbb{R}}[{\mathbf{x}}]$ which is nonnegative over ${\mathbb{R}}^n$ is called a {\em nonnegative polynomial}. The class of nonnegative polynomials is denoted by PSD.

A nonnegative polynomial must satisfy the following necessary conditions.
\begin{proposition}(\cite[Theorem 3.6]{re1})\label{nc-prop2}
Let ${\mathscr{A}}\subseteq{\mathbb{N}}^n$ and $f=\sum_{{\boldsymbol{\alpha}}\in {\mathscr{A}}}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with $\hbox{\rm{supp}}(f)={\mathscr{A}}$. Then $f$ is nonnegative only if the followings hold:
\begin{enumerate}
  \item $V({\mathscr{A}})\subseteq(2{\mathbb{N}})^n$;
  \item If ${\boldsymbol{\alpha}}\in V({\mathscr{A}})$, then the corresponding coefficient $c_{{\boldsymbol{\alpha}}}$ is positive.
\end{enumerate}
\end{proposition}

For the remainder of this paper, we assume for simplicity that the monomial factor of any polynomial $f$ is $1$, that is, if $f={\mathbf{x}}^{{\boldsymbol{\alpha}}'}(\sum c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}})$ such that $\sum c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\in{\mathbb{R}}[{\mathbf{x}}]$ and ${\boldsymbol{\alpha}}'\in{\mathbb{N}}^n$, then ${\mathbf{x}}^{{\boldsymbol{\alpha}}'}=1$. Otherwise, we can always factor out the monomial factor.

\subsection{Nonnegative Polynomials Supported on Circuits}
A subset ${\mathscr{A}}\subseteq(2{\mathbb{N}})^n$ is called a {\em trellis} if ${\mathscr{A}}$ comprises the vertices of a simplex.
\begin{definition}
Let ${\mathscr{A}}$ be a trellis and $f\in{\mathbb{R}}[{\mathbf{x}}]$. Then $f$ is called a {\em circuit polynomial} if it is of the form
\begin{equation}\label{nc-eq}
f({\mathbf{x}})=\sum_{{\boldsymbol{\alpha}}\in{\mathscr{A}}}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d{\mathbf{x}}^{{\boldsymbol{\beta}}},
\end{equation}
with $c_{{\boldsymbol{\alpha}}}>0$ and ${\boldsymbol{\beta}}\in\hbox{\rm{conv}}({\mathscr{A}})^{\circ}$. Assume
\begin{equation}
{\boldsymbol{\beta}}=\sum_{{\boldsymbol{\alpha}}\in{\mathscr{A}}}\lambda_{{\boldsymbol{\alpha}}}{\boldsymbol{\alpha}}\textrm{ with } \lambda_{{\boldsymbol{\alpha}}}>0 \textrm{ and } \sum_{{\boldsymbol{\alpha}}\in{\mathscr{A}}}\lambda_{{\boldsymbol{\alpha}}}=1.
\end{equation}
For every circuit polynomial $f$, we define the corresponding {\em circuit number} as $\Theta_f:=\prod_{{\boldsymbol{\alpha}}\in{\mathscr{A}}}(c_{{\boldsymbol{\alpha}}}/\lambda_{{\boldsymbol{\alpha}}})^{\lambda_{{\boldsymbol{\alpha}}}}$.
\end{definition}

The nonnegativity of a circuit polynomial $f$ is decided by its circuit number alone.
\begin{theorem}(\cite[Theorem 3.8]{iw})\label{nc-thm1}
Let $f=\sum_{{\boldsymbol{\alpha}}\in{\mathscr{A}}}c_{{\boldsymbol{\alpha}}} {\mathbf{x}}^{{\boldsymbol{\alpha}}}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ be a circuit polynomial and $\Theta_f$ its circuit number. Then $f$ is nonnegative if and only if either ${\boldsymbol{\beta}}\in(2{\mathbb{N}})^n$ and $d\le\Theta_f$ or ${\boldsymbol{\beta}}\notin(2{\mathbb{N}})^n$ and $|d|\le\Theta_f$.
\end{theorem}

\begin{remark}
For the concise of narrative, we also view a monomial square as a nonnegaive circuit polynomial.
\end{remark}

The following proposition characterizes the zeros of a circuit polynomial when the Newton polytope is full-dimensional.
\begin{proposition}(\cite[Proposition 3.4 and Corollary 3.9]{iw})\label{nc-prop1}
Let $f=\sum_{i=0}^nc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\Theta_f{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ be a circuit polynomial, $\Theta_f$ the circuit number and ${\boldsymbol{\beta}}=\sum_{i=0}^n\lambda_i{\boldsymbol{\alpha}}_i$ with $\lambda_i>0$ and $\sum_{i=0}^n\lambda_i=1$. Then $f$ has exactly one zero ${\mathbf{x}}_*$ in ${\mathbb{R}}_+^{n}$ which satisfies:
\begin{equation}
\frac{c_0{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_0}}{\lambda_0}=\cdots=\frac{c_n{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_n}}{\lambda_n}=\Theta_f{\mathbf{x}}_*^{{\boldsymbol{\beta}}}.
\end{equation}
Moreover, if ${\mathbf{x}}$ is any zero of $f$, then $|{\mathbf{x}}|={\mathbf{x}}_*$, i.e. $|x_i|=(x_*)_{i}$ for $i=1,\ldots,n$.
\end{proposition}

We shall say that a polynomial is a {\em sum of nonnegative circuit polynomials (SONC)}, if it can be written as a sum of nonnegative circuit polynomials. Clearly, an explicit representation of a SONC polynomial as a sum of nonnegative circuit polynomials provides a certificate of its nonnegativity, which is called a {\em SONC decomposition}. We denote by SONC the class of SONC polynomials.

The following theorem gives a characterization for a nonnegative polynomial to be a SONC polynomial when the Newton polytope is a simplex.
\begin{theorem}(\cite[Corollary 7.5]{iw})\label{nc-thm2}
Let $f=\sum_{i=0}^n c_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\sum_{j=1}^l d_j{\mathbf{x}}^{{\boldsymbol{\beta}}_j}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n, c_i>0, i=0,\ldots,n$ such that $\hbox{\rm{New}}(f)$ is a simplex and ${\boldsymbol{\beta}}_j\in\hbox{\rm{New}}(f)^{\circ}\cap{\mathbb{N}}^n$ for $j=1,\ldots,l$. If there exists a point ${\boldsymbol{v}}=(v_j)\in({\mathbb{R}}^*)^n$ such that $d_j{\boldsymbol{v}}^{{\boldsymbol{\beta}}_j}>0$ for all $j$, then $f\in\hbox{\rm{PSD}}$ if and only if $f\in\hbox{\rm{SONC}}$.
\end{theorem}

\section{Nonnegative Polynomials with One Negative Term}
Now we study which types of nonnegative polynomials with general Newton polytopes admit SONC decompositions. The well-known Hilbert's classification on the coincidence of nonnegative polynomials and SOS polynomials is according to the number of variables and the degree of polynomials. As to the SONC case, it depends on the combinatorical structure of the support of polynomials. In this section, we deal with the case of nonnegative polynomials with one negative term, i.e., we assume that the polynomial is of the form $f_d=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$ and ${\boldsymbol{\beta}}\notin V(\hbox{\rm{New}}(f_d))$. Let $\partial\hbox{\rm{New}}(f_d)$ denote the boundary of $\hbox{\rm{New}}(f_d)$. We first reduce the case of ${\boldsymbol{\beta}}\in\partial\hbox{\rm{New}}(f_d)$ to the case ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f_d)^{\circ}$ by the following lemma.

\begin{lemma}\label{sec3-lm}
Let $f_d=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$ and ${\boldsymbol{\beta}}\in\partial\hbox{\rm{New}}(f_d)$. Furthermore, let $F$ be the face of $\hbox{\rm{New}}(f_d)$ containing ${\boldsymbol{\beta}}$. Then $f_d$ is nonnegative if and only if the restriction of $f_d$ to the face $F$ is nonnegative.
\end{lemma}
\begin{proof}
The necessity follows from \cite[Theorem 3.6]{re1}. For the sufficiency, note that the restriction to the face $F$ contains the term $-d{\mathbf{x}}^{{\boldsymbol{\beta}}}$ and this restriction is nonnegative. Moreover, all other terms in $f_d$ are monomial squares. Hence $f_d$ is nonnegative.
\end{proof}

Now we assume ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f_d)^{\circ}$. Without loss of generality, we further make the assumption that $\dim(\hbox{\rm{New}}(f_d))=n$. Otherwise, we can reduce to this case by applying an appropriate monomial transformation to $f_d$. It is easy to see that the set $\{d\in{\mathbb{R}}\mid f_d\in\hbox{\rm{PSD}}\}$ is nonempty and has upper bounds. So the supremum exists. Let
\begin{equation}\label{npgp-eq1}
d^*\triangleq\sup\{d\in{\mathbb{R}}\mid f_d\in\hbox{\rm{PSD}}\}.
\end{equation}

We need the following theorem.
\begin{theorem}(\cite[Theorem 1.5]{mu})\label{sec1-thm2}
Consider the following system of polynomial equations
\begin{equation}\label{sec1-eq2}
\sum_{i=1}^m c_i{\boldsymbol{\alpha}}_i{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}={\mathbf{b}},
\end{equation}
where ${\boldsymbol{\alpha}}_i\in{\mathbb{R}}^n,c_i>0,i=1,\ldots,m$. Moreover, assume $\dim(\hbox{\rm{conv}}(\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}))=n$. Then for any ${\mathbf{b}}\in\hbox{\rm{cone}}(\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\})^{\circ}$, (\ref{sec1-eq2}) has exactly one zero in ${\mathbb{R}}_+^{n}$.
\end{theorem}

\begin{lemma}\label{sec1-lm}
Consider the following system of polynomial equations on variables $({\mathbf{x}},d)$
\begin{equation}\label{sec1-eq1}
\begin{cases}
\sum_{i=1}^m c_i{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}=0\\
\sum_{i=1}^m c_i{\boldsymbol{\alpha}}_i{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\boldsymbol{\beta}}{\mathbf{x}}^{{\boldsymbol{\beta}}}=\mathbf{0}
\end{cases},
\end{equation}
where ${\boldsymbol{\alpha}}_i\in{\mathbb{R}}^n, c_i>0,i=1,\ldots,m$, ${\boldsymbol{\beta}}\in\hbox{\rm{conv}}(\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\})^{\circ}$. Moreover, assume $\dim(\hbox{\rm{conv}}(\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}))=n$. Then \eqref{sec1-eq1} has exactly one zero in ${\mathbb{R}}_+^{n+1}$.
\end{lemma}
\begin{proof}
Eliminate $d$ from (\ref{sec1-eq1}) and we obtain
\begin{equation}\label{sec1-eq3}
\sum_{i=1}^m c_i({\boldsymbol{\alpha}}_i-{\boldsymbol{\beta}}){\mathbf{x}}^{{\boldsymbol{\alpha}}_i}=\mathbf{0}.
\end{equation}
Divide (\ref{sec1-eq3}) by ${\mathbf{x}}^{{\boldsymbol{\beta}}}$, and we have
\begin{equation}\label{sec1-eq4}
\sum_{i=1}^m c_i({\boldsymbol{\alpha}}_i-{\boldsymbol{\beta}}){\mathbf{x}}^{{\boldsymbol{\alpha}}_i-{\boldsymbol{\beta}}}=\mathbf{0}.
\end{equation}
Since ${\boldsymbol{\beta}}\in\hbox{\rm{conv}}(\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\})^{\circ}$, we have $\mathbf{0}\in\hbox{\rm{cone}}(\{{\boldsymbol{\alpha}}_1-{\boldsymbol{\beta}},\ldots,{\boldsymbol{\alpha}}_m-{\boldsymbol{\beta}}\})^{\circ}$. Thus by Theorem \ref{sec1-thm2}, (\ref{sec1-eq4}) and hence (\ref{sec1-eq3}) have exactly one zero in ${\mathbb{R}}_+^{n}$, say ${\mathbf{x}}_*$. Substitute ${\mathbf{x}}_*$ into the first equation of (\ref{sec1-eq1}), and we obtain $d=\sum_{i=1}^m c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i-{\boldsymbol{\beta}}}>0$.
\end{proof}

\begin{theorem}\label{npgp-thm3}
Let $f_d=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$ such that ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f_d)^{\circ}\cap{\mathbb{N}}^n$, $\dim(\hbox{\rm{New}}(f_d))=n$, and let $d^*$ be defined as (\ref{npgp-eq1}). Then $f_d\in\hbox{\rm{PSD}}$ if and only if either ${\boldsymbol{\beta}}\in(2{\mathbb{N}})^n$ and $d\le d^*$ or ${\boldsymbol{\beta}}\notin(2{\mathbb{N}})^n$ and $|d|\le d^*$. Moreover, $f_{d^*}$ has exactly one zero in ${\mathbb{R}}_+^{n}$.
\end{theorem}
\begin{proof}
First, if ${\boldsymbol{\beta}}\in(2{\mathbb{N}})^n$ and $d\le0$, then obviously $f_d$ is nonnegative since it is a sum of monomial squares. If ${\boldsymbol{\beta}}\notin(2{\mathbb{N}})^n$ and $d\le0$, then $f_d$ is nonnegative if and only if $f_{-d}$ is nonnegative. Thus without loss of generality, we can only consider the case of $d>0$. Since the only negative term in $f_d$ is $-d{\mathbf{x}}^{{\boldsymbol{\beta}}}$, $f_d$ is nonnegative over ${\mathbb{R}}^n$ if and only if $f_d$ is nonnegative over ${\mathbb{R}}_+^n$. Therefore, by the definition of $d^*$, $f_d\in\hbox{\rm{PSD}}$ if and only if $d\le d^*$. The zeros of $f_{d^*}$ are also the minimums of $f_{d^*}$. Then they coincide with the zeros of the system of equations $\{f_{d^*}({\mathbf{x}})=0,\nabla(f_{d^*}({\mathbf{x}}))=\mathbf{0}\}$ ($\nabla$ denotes the gradient) which is equivalent to
\begin{equation}\label{sec1-eq5}
\begin{cases}
\sum_{i=1}^m c_i{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d^*{\mathbf{x}}^{{\boldsymbol{\beta}}}=0\\
\sum_{i=1}^m c_i{\boldsymbol{\alpha}}_i{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d^*{\boldsymbol{\beta}}{\mathbf{x}}^{{\boldsymbol{\beta}}}=\mathbf{0}
\end{cases}.
\end{equation}
By Lemma \ref{sec1-lm}, (\ref{sec1-eq5}) has exactly one zero in ${\mathbb{R}}_+^{n}$, and so does $f_{d^*}$.
\end{proof}

We need the following theorem from discrete geometry.
\begin{theorem}[Helly, \cite{dgk}]\label{npgp-thm5}
Let $X_1,\ldots,X_r$ be a finite collection of convex subsets of ${\mathbb{R}}^n$ with $r>n$. If the intersection of every $n+1$ of these sets is nonempty, then the whole collection has a nonempty intersection.
\end{theorem}

\begin{corollary}\label{npgp-cor1}
Let $X_1,\ldots,X_r$ be a finite collection of convex subsets of ${\mathbb{R}}^n$ with $r>n+1$. If the intersection of every $r-1$ of these sets is nonempty, then the whole collection has a nonempty intersection.
\end{corollary}
\begin{proof}
Since $r>n+1$, the condition that the intersection of every $r-1$ of these sets is nonempty implies that the intersection of every $n+1$ of these sets is nonempty. So the corollary is immediate from Theorem \ref{npgp-thm5}.
\end{proof}

\begin{lemma}\label{npgp-lm1}
Let $A=(a_{ij})\in{\mathbb{R}}^{m\times r}$, ${\mathbf{b}}=(b_j)\in{\mathbb{R}}^r$ and ${\mathbf{z}}=(z_1,\ldots,z_r)^T$ a set of variables. For each $j$, let $A_j$ be the submatrix by deleting all of the $i$-th rows with $a_{ij}\ne0$ and the $j$-th column from $A$. Assume that $A{\mathbf{z}}={\mathbf{b}}$ has a solution, $\hbox{\rm{rank}}(A)>1$ and $\hbox{\rm{rank}}(A_j)=\hbox{\rm{rank}}(A)-1$ for all $j$. Then $A{\mathbf{z}}={\mathbf{b}}$ has a nonnegative solution if and only if $A_j\bar{{\mathbf{z}}}_j=\bar{{\mathbf{b}}}_j$ has a nonnegative solution for $j=1,\ldots,r$, where $\bar{{\mathbf{z}}}_j={\mathbf{z}}\backslash z_j$, $\bar{{\mathbf{b}}}_j={\mathbf{b}}\backslash b_j$.
\end{lemma}
\begin{proof}
Let $t=\hbox{\rm{rank}}(A)>1$. Then the system of linear equations $A{\mathbf{z}}={\mathbf{b}}$ has $r-t$ free variables. Without loss of generality, let the $r-t$ free variables be $\{z_1,\ldots,z_{r-t}\}$. We can figure out $\{z_{r-t+1},\ldots,z_r\}$ from $A{\mathbf{z}}={\mathbf{b}}$ and assume $z_{j}=f_{j-r+t}(z_1,\ldots,z_{r-t})$ for $j=r-t+1,\ldots,r$. Then $A{\mathbf{z}}={\mathbf{b}}$ has a nonnegative solution if and only if
\begin{equation}\label{npgp-eq6}
\{(z_1,\ldots,z_{r-t})\mid z_1\ge0,\ldots,z_{r-t}\ge0,z_{r-t+1}=f_{1}\ge0,\ldots,z_{r}=f_{t}\ge0\}
\end{equation}
is nonempty. Since both $z_j\ge0$ for $1\le j\le r-t$ and $f_j\ge0$ for $1\le j\le t$ define convex subsets of ${\mathbb{R}}^{r-t}$, then by Corollary \ref{npgp-cor1}, (\ref{npgp-eq6}) is nonempty if and only if
\begin{align}\label{npgp-eq7}
\begin{split}
\{(z_1,\ldots,z_{r-t})\mid &z_1\ge0,\ldots,z_{j-1}\ge0,z_{j+1}\ge0,\ldots,z_{r-t}\ge0,\\
&z_{r-t+1}=f_{1}\ge0,\ldots,z_{r}=f_{t}\ge0\}
\end{split}
\end{align}
is nonempty for $j=1,\ldots,r-t$ and
\begin{align}\label{npgp-eq8}
\begin{split}
\{(z_1,\ldots,z_{r-t})\mid &z_1\ge0,\ldots,z_{r-t}\ge0,z_{r-t+1}=f_{1}\ge0,\ldots,z_{j-1+r-t}=f_{j-1}\ge0,\\
&z_{j+1+r-t}=f_{j+1}\ge0,\ldots,z_{r}=f_{t}\ge0\}
\end{split}
\end{align}
is nonempty for $j=1,\ldots,t$.

For $j\in[r-t]$, (\ref{npgp-eq7}) is nonempty if and only if $A{\mathbf{z}}={\mathbf{b}}$ has a solution with $\bar{{\mathbf{z}}}_j\in{\mathbb{R}}_{\ge0}^{r-1}$ and $z_j\in{\mathbb{R}}$, which is equivalent to the condition that $A_j\bar{{\mathbf{z}}}_j=\bar{{\mathbf{b}}}_j$ has a nonnegative solution since $\hbox{\rm{rank}}(A_j)=\hbox{\rm{rank}}(A)-1$. For $j\in[t]$, (\ref{npgp-eq8}) is nonempty if and only if $\{f_{1}\ge0,\ldots,f_{j-1}\ge0,f_{j+1}\ge0,\ldots,f_{t}\ge0\}$ has a nonnegative solution, which is also equivalent to the condition that $A_{j+r-t}\bar{{\mathbf{z}}}_{j+r-t}=\bar{{\mathbf{b}}}_{j+r-t}$ has a nonnegative solution since $\hbox{\rm{rank}}(A_{j+r-t})=\hbox{\rm{rank}}(A)-1$. Put all above together and we have that $A{\mathbf{z}}={\mathbf{b}}$ has a nonnegative solution if and only if $A_j\bar{{\mathbf{z}}}_j=\bar{{\mathbf{b}}}_j$ has a nonnegative solution for $j=1,\ldots,r$ as desired.
\end{proof}

Lemma \ref{npgp-lm1} needs the assumption that the solution set of $A{\mathbf{z}}={\mathbf{b}}$ is nonempty. We know that the system of linear equations $A{\mathbf{z}}={\mathbf{b}}$ has a solution if and only if ${\mathbf{b}}$ belongs to the image of $A$. For the later use, we give a more concrete description for the condition that $A{\mathbf{z}}={\mathbf{b}}$ has a solution here.
\begin{lemma}\label{npgp-lm2}
Let $A=(a_{ij})\in{\mathbb{R}}^{m\times r}$, ${\mathbf{b}}=(b_j)\in{\mathbb{R}}^r$, and ${\mathbf{z}}=(z_1,\ldots,z_r)^T$, ${\mathbf{y}}=(y_1,\ldots,y_r)^T$ be sets of variables. Let $\{\mathbf{a}_1,\ldots,\mathbf{a}_m\}$ be the set of row vectors of $A$ and let $I=(\mathbf{a}_1{\mathbf{z}}-y_1,\ldots,\mathbf{a}_m{\mathbf{z}}-y_m)\cap{\mathbb{R}}[y_1,\ldots,y_m]$. Assume that $\{\mathbf{c}_1{\mathbf{y}},\ldots,\mathbf{c}_l{\mathbf{y}}\}$ is a set of generators of $I$ and let $C$ be the matrix whose row vectors are $\{\mathbf{c}_1,\ldots,\mathbf{c}_l\}$. Then $\hbox{\rm{rank}}(C)=m-\hbox{\rm{rank}}(A)$ and $A{\mathbf{z}}={\mathbf{b}}$ has a solution if and only if $C{\mathbf{b}}=\mathbf{0}$.
\end{lemma}
\begin{proof}
Observe that $\{\mathbf{c}_1,\ldots,\mathbf{c}_l\}$ generates the linear space of all linear relationships among $\{\mathbf{a}_1,\ldots,\mathbf{a}_m\}$. In other words, $\{\mathbf{c}_1^T,\ldots,\mathbf{c}_l^T\}$ generates the kernel space of $A^T$. Thus $\hbox{\rm{rank}}(C)=\hbox{\rm{rank}}(\ker(A^T))=m-\hbox{\rm{rank}}(A)$.

If $C{\mathbf{b}}=\mathbf{0}$, i.e. ${\mathbf{b}}$ is a zero of the elimination ideal $I$, then by the Extension Theorem on p.125 of \cite{cls}, we can extend ${\mathbf{b}}$ to a zero of the ideal $(\mathbf{a}_1{\mathbf{z}}-y_1,\ldots,\mathbf{a}_m{\mathbf{z}}-y_m)$. Therefore, $A{\mathbf{z}}={\mathbf{b}}$ has a solution. The converse is easy.
\end{proof}

\begin{lemma}\label{npgp-thm4}
Let $f_d=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$ such that ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f_d)^{\circ}\cap{\mathbb{N}}^n$, $\dim(\hbox{\rm{New}}(f_d))=n$, and let $d^*$ be defined as (\ref{npgp-eq1}). Then $f_{d^*}\in\hbox{\rm{SONC}}$.
\end{lemma}
\begin{proof}
Without loss of generality, assume $m>n+1$. By Theorem \ref{npgp-thm3}, $f_{d^*}$ has exactly one zero in ${\mathbb{R}}_+^{n}$, which is denoted by ${\mathbf{x}}_*$. Let
$$\{\Delta_1,\ldots,\Delta_r\}:=\{\Delta\mid\Delta\textrm{ is a simplex }, {\boldsymbol{\beta}}\in\Delta^{\circ}, V(\Delta)\subseteq\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}\}$$
and $I_k:=\{i\in[m]\mid{\boldsymbol{\alpha}}_i\in V(\Delta_k)\}$ for $k=1,\ldots,r$. Firstly, we assume $\dim(\Delta_k)=n$ for all $k$. Hence $|I_k|=n+1$ for all $k$. For each $\Delta_k$, since ${\boldsymbol{\beta}}\in\Delta_k^{\circ}$, we can write ${\boldsymbol{\beta}}=\sum_{i\in I_k}\lambda_{ik}{\boldsymbol{\alpha}}_i$, where $\sum_{i\in I_k}\lambda_{ik}=1, \lambda_{ik}>0, i\in I_k$. Let us consider the following system of linear equations on variables $\{c_{ik}\}$ and $\{s_k\}$:
\begin{equation}\label{npgp-eq2}
\begin{cases}
\frac{c_{ik}{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}}{\lambda_{ik}}=s_k, &\textrm{for }i\in I_k,k=1,\ldots,r\\
\sum_{i\in I_k} c_{ik}=c_i, &\textrm{for }i=1,\ldots,m
\end{cases}.
\end{equation}
Eliminate $\{c_{ik}\}$ from (\ref{npgp-eq2}) and we obtain:
\begin{equation}\label{npgp-eq3}
\sum_{i\in I_k}\lambda_{ik}s_k=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}, \quad \textrm{for }i=1,\ldots,m.
\end{equation}

{\bf Claim}: The linear system (\ref{npgp-eq3}) on variables $\{s_1,\ldots,s_r\}$ has a nonnegative solution.

Denote the coefficient matrix of (\ref{npgp-eq3}) by $A$. Add up all of the equations of (\ref{npgp-eq3}) and we obtain:
\begin{equation}\label{npgp-eq9}
\sum_{k=1}^rs_k=\sum_{i=1}^m\sum_{i\in I_k}\lambda_{ik}s_k=\sum_{i=1}^mc_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}.
\end{equation}
Multiply the $i$-th equation of (\ref{npgp-eq3}) by ${\boldsymbol{\alpha}}_i$ and then add up all of them. We obtain:
\begin{equation}\label{npgp-eq10}
{\boldsymbol{\beta}}\sum_{k=1}^rs_k=\sum_{i=1}^m\sum_{i\in I_k}\lambda_{ik}{\boldsymbol{\alpha}}_is_k=\sum_{i=1}^mc_i{\boldsymbol{\alpha}}_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}.
\end{equation}
$(\ref{npgp-eq10})-(\ref{npgp-eq9})\times{\boldsymbol{\beta}}$ gives
\begin{equation}\label{npgp-eq11}
\sum_{i=1}^mc_i({\boldsymbol{\alpha}}_i-{\boldsymbol{\beta}}){\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}=\mathbf{0}.
\end{equation}
By (\ref{sec1-eq5}) in the proof of Theorem \ref{npgp-thm3}, $\{c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}\}_{i=1}^m$ satisfies (\ref{npgp-eq11}). Thus by Lemma \ref{npgp-lm2}, (\ref{npgp-eq3}) has a solution. Moreover, since ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f_d)^{\circ}$ and $\dim(\hbox{\rm{New}}(f_d))=n$, then $\hbox{\rm{rank}}(\{{\boldsymbol{\alpha}}_i-{\boldsymbol{\beta}}\}_{i=1}^m)=n$. Thus $\hbox{\rm{rank}}(A)=m-n>1$.

For each $j$, denote the coefficient matrix of
\begin{equation}\label{npgp-eq4}
\{\sum_{i\in I_k}\lambda_{ik}s_k=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}\mid i\notin I_j\}
\end{equation}
by $A_j$. Note that \eqref{npgp-eq4} is obtained from \eqref{npgp-eq3} by removing the equations involving the variable $s_j$. For every $i\notin I_j$, since ${\boldsymbol{\beta}}\in\Delta_j^{\circ}$, there exists a facet $F$ of $\Delta_j$ such that ${\boldsymbol{\beta}}\in\hbox{\rm{conv}}(V(F)\cup\{{\boldsymbol{\alpha}}_i\})^{\circ}$. Assume $\hbox{\rm{conv}}(V(F)\cup\{{\boldsymbol{\alpha}}_i\})=\Delta_{p_i}$. For every $k\notin\{j\}\cup\bigcup_{i\notin I_j}\{p_i\}$, let $s_k=0$ in (\ref{npgp-eq4}) and we obtain:
\begin{equation}\label{npgp-eq5}
\{\lambda_{ip_i}s_{p_i}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}\mid i\notin I_j\}.
\end{equation}
Thus $\hbox{\rm{rank}}(A_j)=m-|I_j|=m-(n+1)=\hbox{\rm{rank}}(A)-1$. Therefore by Lemma \ref{npgp-lm1}, in order to prove the claim, we only need to show that the linear system (\ref{npgp-eq4}) on variables $\{s_1,\ldots,s_r\}\backslash\{s_j\}$ has a nonnegative solution for $j=1,\ldots,r$.

Given $j\in[r]$, from (\ref{npgp-eq5}) we have $s_{p_i}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}/\lambda_{ip_i}$ for $i\notin I_j$ and hence
\begin{equation}
\begin{cases}
s_k=0, &\textrm{for }k\notin\{j\}\cup\bigcup_{i\notin I_j}\{p_i\}\\
s_{p_i}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}/\lambda_{ip_i}, &\textrm{for }i\notin I_j
\end{cases}
\end{equation}
is a nonnegative solution for (\ref{npgp-eq4}). Thus the claim is proved.

Assume that $\{s_1^*,\ldots,s_r^*\}$ is a nonnegative solution for the system of equations (\ref{npgp-eq3}). Substitute $\{s_1^*,\ldots,s_r^*\}$ into the system of equations (\ref{npgp-eq2}), and we have $c_{ik}=\lambda_{ik}s_k^*/{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}$ for $i\in I_k,k=1,\ldots,r$. Let $d_k=s_k^*/{\mathbf{x}}_*^{{\boldsymbol{\beta}}}$ and $f_k=\sum_{i\in I_k}c_{ik}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d_k{\mathbf{x}}^{{\boldsymbol{\beta}}}$ for $k=1,\ldots,r$. Then by (\ref{npgp-eq2}) and by Proposition \ref{nc-prop1}, $d_{k}$ is the circuit number of $f_{k}$ and hence $f_k$ is a nonnegative circuit polynomial for all $k$. By (\ref{npgp-eq2}), $\sum_{k=1}^rd_k{\mathbf{x}}_*^{{\boldsymbol{\beta}}}=\sum_{k=1}^r\sum_{i\in I_k}c_{ik}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}_*=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}_*=d^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}}$. So we have $\sum_{k=1}^rd_k=d^*$. It follows $f_{d^*}=\sum_{k=1}^rf_k$ as desired.

For the case that $\dim(\Delta_k)=n$ does not hold for all $k$, note that all results above remain valid for ${\boldsymbol{\beta}}\in{\mathbb{R}}^n$. We then give ${\boldsymbol{\beta}}$ a small perturbation, say ${\boldsymbol{\delta}}$, such that $\dim(\Delta_k)=n$ holds for all $k$. Then the new linear system (\ref{npgp-eq3}) for ${\boldsymbol{\beta}}+{\boldsymbol{\delta}}$ has a nonnegative solution. Let ${\boldsymbol{\delta}}\to\mathbf{0}$, we obtain that (\ref{npgp-eq3}) also has a nonnegative solution for ${\boldsymbol{\beta}}$. Thus the theorem remains true in this case.
\end{proof}

\begin{theorem}\label{npgp-thm7}
Let $f_d=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$ such that ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f_d)^{\circ}\cap{\mathbb{N}}^n$, $\dim(\hbox{\rm{New}}(f_d))=n$. Then $f_d\in\hbox{\rm{PSD}}$ if and only if $f_d\in\hbox{\rm{SONC}}$.
\end{theorem}
\begin{proof}
The sufficiency is obvious. Assume that $f_d$ is nonnegative. If ${\boldsymbol{\beta}}\in(2{\mathbb{N}})^n$ and $d<0$, or $d=0$, then $f_d$ is a sum of monomial squares and obviously $f_d\in\hbox{\rm{SONC}}$. If ${\boldsymbol{\beta}}\notin(2{\mathbb{N}})^n$ and $d<0$, through a variable transformation $x_j\mapsto -x_j$ for some odd number $\beta_j$, we can always assume $d>0$. Let $d^*$ be defined as (\ref{npgp-eq1}). By Lemma \ref{npgp-thm4}, $f_{d^*}\in\hbox{\rm{SONC}}$. Suppose $f_{d^*}=\sum_{k=1}^r(\sum_{i\in I_k}c_{ik}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d_k{\mathbf{x}}^{{\boldsymbol{\beta}}})$, where $\sum_{i\in I_k}c_{ik}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d_k{\mathbf{x}}^{{\boldsymbol{\beta}}}$ is a circuit polynomial with $d_k$ the corresponding circuit number for all $k$. Since $f_d$ is nonnegative, then $d\le d^{*}$ by Theorem \ref{npgp-thm3}. We have $f_d=\sum_{k=1}^r(\sum_{i\in I_k}c_{ik}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\frac{d}{d^*}d_k{\mathbf{x}}^{{\boldsymbol{\beta}}})$, where $\sum_{i\in I_k}c_{ik}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\frac{d}{d^*}d_k{\mathbf{x}}^{{\boldsymbol{\beta}}}$ is a nonnegative circuit polynomial for all $k$ by Theorem \ref{nc-thm1}. Thus $f_d\in\hbox{\rm{SONC}}$.
\end{proof}

\begin{theorem}\label{npgp-thm8}
Let $f=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$. Then $f\in\hbox{\rm{PSD}}$ if and only if $f\in\hbox{\rm{SONC}}$. Moreover, let
$$\mathscr{F}:=\{\Delta\mid\Delta\textrm{ is a simplex }, {\boldsymbol{\beta}}\in\Delta^{\circ}, V(\Delta)\subseteq\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}\}.$$
If $f\in\hbox{\rm{PSD}}$, then $f$ admits a SONC decomposition as follows:
\begin{equation}
    f=\sum_{\Delta\in\mathscr{F}}f_{\Delta}+\sum_{i\in I}c_i{\mathbf{x}}^{{\boldsymbol{\alpha}}_i},
\end{equation}
where $f_{\Delta}$ is a nonnegative circuit polynomial supported on $V(\Delta)\cup\{{\boldsymbol{\beta}}\}$ for each $\Delta$ and $I=\{i\in[m]\mid{\boldsymbol{\alpha}}_i\notin\cup_{\Delta\in\mathscr{F}}V(\Delta)\}$.
\end{theorem}
\begin{proof}
It follows easily from Lemma \ref{sec3-lm} and Theorem \ref{npgp-thm8}.
\end{proof}

\section{Nonnegative Polynomials with Multiple Negative Terms}
In this section, we deal with the case of nonnegative polynomials with multiple negative terms. Let $\Delta$ be a polytope of dimension $d$. For a vertex ${\boldsymbol{\alpha}}$ of $\Delta$, we say that $\Delta$ is {\em simple} at ${\boldsymbol{\alpha}}$ if ${\boldsymbol{\alpha}}$ is the intersection of precisely $d$ edges.
\begin{theorem}\label{npmt-thm1}
Let $f=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\sum_{j=1}^ld_j{\mathbf{x}}^{{\boldsymbol{\beta}}_j}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$, ${\boldsymbol{\beta}}_j\in\hbox{\rm{New}}(f)^{\circ}\cap{\mathbb{N}}^n,j=1,\ldots,l$. Assume that $\hbox{\rm{New}}(f)$ is simple at some vertex, all of the ${\boldsymbol{\beta}}_j$'s lie in the same side of every hyperplane determined by points among $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}$ and there exists a point ${\boldsymbol{v}}=(v_k)\in({\mathbb{R}}^*)^n$ such that $d_j{\boldsymbol{v}}^{{\boldsymbol{\beta}}_j}>0$ for all $j$. Then $f\in\hbox{\rm{PSD}}$ if and only if $f\in\hbox{\rm{SONC}}$.
\end{theorem}
\begin{proof}
Without loss of generality, assume $\dim(\hbox{\rm{New}}(f))=n$ and $m>n+1$. The sufficiency is obvious. Suppose $f$ is nonnegative. After a variable transformation $x_k\mapsto -x_k$ for all $k$ with $v_k<0$, we can assume $d_j>0$ for all $j$. Let
\begin{equation}\label{npmt-eq9}
d_l^*\triangleq\sup\{\tilde{d}_l\in{\mathbb{R}}\mid \tilde{f}=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\sum_{j=1}^{l-1}d_j{\mathbf{x}}^{{\boldsymbol{\beta}}_j}-\tilde{d}_l{\mathbf{x}}^{{\boldsymbol{\beta}}_l}\in\hbox{\rm{PSD}}\}.
\end{equation}
Note that $d_l^*$ is well-defined since the set in (\ref{npmt-eq9}) is nonempty and has upper bounds. Let $f^*=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\sum_{j=1}^{l-1}d_j{\mathbf{x}}^{{\boldsymbol{\beta}}_j}-d_l^*{\mathbf{x}}^{{\boldsymbol{\beta}}_l}$. Then $f^*=0$ has a zero in ${\mathbb{R}}_+^{n}$ (\cite[Lemma 4.6]{wang}), which is denoted by ${\mathbf{x}}_*$. The condition that all of the ${\boldsymbol{\beta}}_j$'s lie in the same side of every hyperplane determined by points among $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}$ implies if a simplex $\Delta$ with vertices coming from $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}$ contains some ${\boldsymbol{\beta}}_j$, then $\dim(\Delta)=n$ and it contains all ${\boldsymbol{\beta}}_j,j=1,\ldots,l$. Let
$$\{\Delta_1,\ldots,\Delta_r\}:=\{\Delta\mid\Delta\textrm{ is a simplex }, {\boldsymbol{\beta}}_j\in\Delta^{\circ}, j\in[l], V(\Delta)\subseteq\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}\}$$
and $I_k:=\{i\in[m]\mid{\boldsymbol{\alpha}}_i\in V(\Delta_k)\}$ for $k=1,\ldots,r$. Then $\dim(\Delta_k)=n$ for all $k$. For every ${\boldsymbol{\beta}}_j$ and every $\Delta_k$, since ${\boldsymbol{\beta}}_j\in\Delta_k^{\circ}$, we can write ${\boldsymbol{\beta}}_j=\sum_{i\in I_k}\lambda_{ijk}{\boldsymbol{\alpha}}_i$, where $\sum_{i\in I_k}\lambda_{ijk}=1, \lambda_{ijk}>0, i\in I_k$. Let us consider the following system of linear equations on variables $\{c_{ijk}\}$, $\{d_{jk}\}$ and $\{s_{jk}\}$:
\begin{equation}\label{npmt-eq1}
\begin{cases}
\frac{c_{ijk}{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}}{\lambda_{ijk}}=d_{jk}{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}=s_{jk}, &\textrm{for }i\in I_k,k=1,\ldots,r,j=1,\ldots,l\\
\sum_{k=1}^rd_{jk}=d_j, &\textrm{for }j=1,\ldots,l-1\\
\sum_{k=1}^rd_{lk}=d_l^*, \\
\sum_{j=1}^l\sum_{i\in I_k} c_{ijk}=c_i, &\textrm{for }i=1,\ldots,m
\end{cases}.
\end{equation}
Eliminate $\{c_{ijk}\}$ and $\{d_{jk}\}$ from (\ref{npmt-eq1}) and we obtain:
\begin{equation}\label{npmt-eq2}
\begin{cases}
\sum_{j=1}^l\sum_{i\in I_k}\lambda_{ijk}s_{jk}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}, &\textrm{for }i=1,\ldots,m\\
\sum_{k=1}^rs_{jk}=d_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}, &\textrm{for }j=1,\ldots,l-1\\
\sum_{k=1}^rs_{lk}=d_l^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l},
\end{cases}.
\end{equation}
{\bf Claim}: The linear system (\ref{npmt-eq2}) on variables $\{s_{jk}\}$ has a nonnegative solution.

Denote the coefficient matrix of (\ref{npmt-eq2}) by $A$. Add up all of the equations of the first part of (\ref{npmt-eq2}), and we obtain:
\begin{equation}\label{npmt-eq6}
\sum_{j=1}^l\sum_{k=1}^rs_{jk}=\sum_{i=1}^m\sum_{j=1}^l\sum_{i\in I_k}\lambda_{ijk}s_{jk}=\sum_{i=1}^mc_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}.
\end{equation}
Multiply the $i$-th equation of the first part of (\ref{npmt-eq2}) by ${\boldsymbol{\alpha}}_i$ and then add up all of them. We obtain:
\begin{equation}\label{npmt-eq7}
\sum_{j=1}^l{\boldsymbol{\beta}}_j\sum_{k=1}^rs_{jk}=\sum_{i=1}^m\sum_{j=1}^l\sum_{i\in I_k}\lambda_{ijk}{\boldsymbol{\alpha}}_is_{jk}=\sum_{i=1}^mc_i{\boldsymbol{\alpha}}_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}.
\end{equation}
Substitute the second and the third part of (\ref{npmt-eq2}) into (\ref{npmt-eq6}) and (\ref{npmt-eq7}), and we obtain:
\begin{equation}\label{npmt-eq8}
\begin{cases}
\sum_{j=1}^{l-1}d_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}+d_l^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l}=\sum_{i=1}^mc_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}\\
\sum_{j=1}^{l-1}d_j{\boldsymbol{\beta}}_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}+d_l^*{\boldsymbol{\beta}}_l{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l}=\sum_{i=1}^mc_i{\boldsymbol{\alpha}}_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}
\end{cases}.
\end{equation}
The zero ${\mathbf{x}}_*$ of $f^*$ is also a minimizer of $f^*$. Then it must satisfy the equations $\{f^*({\mathbf{x}}_*)=0,\nabla(f^*({\mathbf{x}}_*))=\mathbf{0}\}$ which is actually equivalent to (\ref{npmt-eq8}). Thus by Lemma \ref{npgp-lm2}, (\ref{npmt-eq2}) has a solution on variables $\{s_{jk}\}$. Moreover, since $\dim(\Delta_1)=n$, the volume of $\Delta_1$, which equals $\frac{1}{n!}|\det(\{\begin{pmatrix}1\\ {\boldsymbol{\alpha}}_i\end{pmatrix}\}_{i\in I_1})|$, is nonzero. It follows $$\hbox{\rm{rank}}(\{\begin{pmatrix}1\\ {\boldsymbol{\alpha}}_1\end{pmatrix},\ldots,\begin{pmatrix}1\\ {\boldsymbol{\alpha}}_m\end{pmatrix},\begin{pmatrix}-1\\ -{\boldsymbol{\beta}}_1\end{pmatrix},\ldots,\begin{pmatrix}-1\\ -{\boldsymbol{\beta}}_l\end{pmatrix}\})=n+1$$ and hence by Lemma \ref{npgp-lm2}, $\hbox{\rm{rank}}(A)=m+l-(n+1)>1$.

For every $u\in[l]$ and every $v\in[r]$, denote the coefficient matrix of
\begin{equation}\label{npmt-eq3}
\begin{cases}
\sum_{i\in I_k}\lambda_{ijk}s_{jk}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}, &\textrm{for }i\notin I_v\\
\sum_{k=1}^rs_{jk}=d_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j},&\textrm{for }j\ne u,l\\
\sum_{k=1}^rs_{lk}=d_l^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l},&\textrm{if }u\ne l
\end{cases}
\end{equation}
by $A_{uv}$. Note that \eqref{npmt-eq3} is obtained from \eqref{npmt-eq2} by removing the equations involving the variable $s_{uv}$. For every $i\notin I_v$, since ${\boldsymbol{\beta}}_u\in\Delta_v^{\circ}$, there exists a facet $F$ of $\Delta_v$ such that ${\boldsymbol{\beta}}_u\in\hbox{\rm{conv}}(V(F)\cup\{{\boldsymbol{\alpha}}_i\})^{\circ}$. Assume $\hbox{\rm{conv}}(V(F)\cup\{{\boldsymbol{\alpha}}_i\})=\Delta_{p_i}$. For $j=u,k\notin\cup_{i\notin I_v}\{p_i\}$ or $j\ne u,k\ne v$, let $s_{jk}=0$ in (\ref{npmt-eq3}), and we obtain:
\begin{equation}\label{npmt-eq4}
\begin{cases}
\lambda_{iup_i}s_{up_i}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}, &\textrm{for }i\notin I_v\\
s_{jv}=d_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}, &\textrm{for }j\ne u,l\\
s_{lv}=d_l^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l},&\textrm{if }u\ne l
\end{cases}.
\end{equation}
Thus $\hbox{\rm{rank}}(A_{uv})=m-|I_v|+l-1=m-(n+1)+l-1=\hbox{\rm{rank}}(A)-1$. Therefore by Lemma \ref{npgp-lm1}, in order to prove the claim, we only need to show that the linear system (\ref{npmt-eq3}) on variables $\{s_{jk}\}_{j,k}\backslash\{s_{uv}\}$ has a nonnegative solution for all $u\in[l]$ and all $v\in[r]$.

Given $v\in[r]$, from (\ref{npmt-eq4}) we have $s_{up_i}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}/\lambda_{iup_i}$ for $i\notin I_v$, $s_{jv}=d_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}$ for $j\ne u,l$, and $s_{lv}=d_l^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l}$. Hence
\begin{equation}
\begin{cases}
s_{jk}=0, &\textrm{for }j=u,k\notin\cup_{i\notin I_v}\{p_i\} \textrm{ or }j\ne u,k\ne v\\
s_{up_i}=c_i{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}/\lambda_{iup_i}, &\textrm{for }i\notin I_v\\
s_{jv}=d_j{\mathbf{x}}_*^{{\boldsymbol{\beta}}_j}, &\textrm{for }j\ne u,l\\
s_{lv}=d_l^*{\mathbf{x}}_*^{{\boldsymbol{\beta}}_l},&\textrm{if }u\ne l
\end{cases}
\end{equation}
is a nonnegative solution for (\ref{npmt-eq3}). So the claim is proved.

Assume that $\{s_{jk}^*\}_{j,k}$ is a nonnegative solution for the system of equations (\ref{npmt-eq2}). Substitute $\{s_{jk}^*\}_{j,k}$ into the system of equations (\ref{npmt-eq1}), and we have $c_{ijk}=\lambda_{ijk}s_{jk}^*/{\mathbf{x}}_*^{{\boldsymbol{\alpha}}_i}$ for $i\in I_k, k=1,\ldots,r,j=1,\ldots,l$. Let $f_{jk}=\sum_{i\in I_k}c_{ijk}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-d_{jk}{\mathbf{x}}^{{\boldsymbol{\beta}}_j}$ for $k=1,\ldots,r,j=1,\ldots,l$. Then by (\ref{npmt-eq1}) and by Proposition \ref{nc-prop1}, $d_{jk}$ is the circuit number of $f_{jk}$ and $f_{jk}$ is a nonnegative circuit polynomial for all $j,k$. By (\ref{npmt-eq1}), we have $f=\sum_{j=1}^{l-1}\sum_{k=1}^rf_{jk}+\sum_{k=1}^r(\sum_{i\in I_k}c_{ilk}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\frac{d_l}{d_l^*}d_{lk}{\mathbf{x}}^{{\boldsymbol{\beta}}_l})$. Since $d_l\le d_l^*$, $\sum_{i\in I_k}c_{ilk}{\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\frac{d_l}{d_l^*}d_{lk}{\mathbf{x}}^{{\boldsymbol{\beta}}_l}$ is a nonnegative circuit polynomial for all $k$ by Theorem \ref{nc-thm1}. Thus $f\in\hbox{\rm{SONC}}$.
\end{proof}

\begin{example}
Let $d^*=\sup\{d\in{\mathbb{R}}_+\mid 1+x^6+y^6+x^6y^6-x^2y-dx^4y\in\hbox{\rm{PSD}}\}$ and $f=1+x^6+y^6+x^6y^6-x^2y-d^*x^4y$. We have $(2,1)=\frac{1}{6}(6,6)+\frac{1}{6}(6,0)+\frac{2}{3}(0,0)=\frac{1}{3}(6,0)+\frac{1}{6}(0,6)+\frac{1}{2}(0,0)$, and $(4,1)=\frac{1}{6}(6,6)+\frac{1}{2}(6,0)+\frac{1}{3}(0,0)=\frac{2}{3}(6,0)+\frac{1}{6}(0,6)+\frac{1}{6}(0,0)$.
\begin{center}
\begin{tikzpicture}
\draw (0,0)--(0,3);
\draw (0,0)--(3,0);
\draw (3,0)--(3,3);
\draw (0,3)--(3,3);
\draw (0,0)--(3,3);
\draw (0,3)--(3,0);
\fill (0,0) circle (2pt);
\node[below left] (1) at (0,0) {$1$};
\fill (3,0) circle (2pt);
\node[below right] (2) at (3,0) {$x^6$};
\fill (0,3) circle (2pt);
\node[above left] (3) at (0,3) {$y^6$};
\fill (3,3) circle (2pt);
\node[above right] (4) at (3,3) {$x^6y^6$};
\fill (1,1/2) circle (2pt);
\node[below] (5) at (1,1/2) {$x^2y$};
\fill (2,1/2) circle (2pt);
\node[below] (6) at (2,1/2) {$x^4y$};
\end{tikzpicture}
\end{center}
The system of equations $\{f=0,\nabla(f)=\mathbf{0}\}$ has exactly one zero $(x_*\approx1.04521,y_*\approx0.764724,d^*\approx2.11373)$ in ${\mathbb{R}}_+^{n}$. The following linear system
\begin{equation}\label{npmt-eq12}
\begin{cases}
1=\frac{2}{3}s_{11}+\frac{1}{2}s_{12}+\frac{1}{3}s_{21}+\frac{1}{6}s_{22}\\
x_*^6=\frac{1}{6}s_{11}+\frac{1}{3}s_{12}+\frac{1}{2}s_{21}+\frac{2}{3}s_{22}\\
y_*^6=\frac{1}{6}s_{12}+\frac{1}{6}s_{22}\\
x_*^6y_*^6=\frac{1}{6}s_{11}+\frac{1}{6}s_{21}\\
x_*^2y_*=s_{11}+s_{12}\\
d^*x_*^4y_*=s_{21}+s_{22}
\end{cases}
\end{equation}
on variables $\{s_{11},s_{12},s_{21},s_{22}\}$ has a nonnegative solution $(s_{11}\approx0.835429,s_{12}=0,s_{21}\approx0.729142,s_{22}=1.2)$. Thus from the proof of Theorem \ref{npmt-thm1}, we obtain a SONC decomposition of $f$ which is $f\approx(0.556953+0.106793x^6+0.533967x^6y^6-x^2y)+(0.243047+0.27962x^6+0.466033x^6y^6-0.798909x^4y)+(0.2+0.613587x^6+y^6-1.31482x^4y)$.
\end{example}





\begin{corollary}\label{npmt-cor1}
Let $f=\sum_{i=1}^mc_i {\mathbf{x}}^{{\boldsymbol{\alpha}}_i}-\sum_{j=1}^ld_j{\mathbf{x}}^{{\boldsymbol{\beta}}_j}\in{\mathbb{R}}[{\mathbf{x}}]$ with ${\boldsymbol{\alpha}}_i\in(2{\mathbb{N}})^n,c_i>0,i=1,\ldots,m$, ${\boldsymbol{\beta}}_j\in\hbox{\rm{New}}(f)^{\circ}\cap{\mathbb{N}}^n,d_j>0,j=1,\ldots,l$ and $\dim(\hbox{\rm{New}}(f))=n$. Assume that $f$ is nonnegative and has a zero, $\hbox{\rm{New}}(f)$ is simple at some vertex, and all of the ${\boldsymbol{\beta}}_j$'s lie in the same side of every hyperplane determined by points among $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}$. Then $f$ has exactly one zero in ${\mathbb{R}}_+^{n}$.
\end{corollary}
\begin{proof}
By Theorem \ref{npmt-thm1}, $f\in\hbox{\rm{SONC}}$. Suppose $f=\sum_{k=1}^rf_k$, where $f_k$ is a nonnegative circuit polynomial for all $k$. Let ${\mathbf{x}}$ be a zero of $f$. Then we have $f_k({\mathbf{x}})=0$ for all $k$. By Proposition \ref{nc-prop1}, $f_k(|{\mathbf{x}}|)=0$ and $|{\mathbf{x}}|$ is the only zero of $f_k$ in ${\mathbb{R}}_+^{n}$ for all $k$. Hence $|{\mathbf{x}}|$ is the only zero of $f$ in ${\mathbb{R}}_+^{n}$.
\end{proof}


\section{SONC Decompositions Preserve Sparsity}
For a polynomial $f\in{\mathbb{R}}[{\mathbf{x}}]$, let $\Lambda(f):=\{{\boldsymbol{\alpha}}\in\hbox{\rm{supp}}(f)\mid{\boldsymbol{\alpha}}\in(2{\mathbb{N}})^n\textrm{ and }c_{{\boldsymbol{\alpha}}}>0\}$ and $\Gamma(f):=\hbox{\rm{supp}}(f)\backslash\Lambda(f)$. Then we can write $f=\sum_{{\boldsymbol{\alpha}}\in\Lambda(f)}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-\sum_{{\boldsymbol{\beta}}\in\Gamma(f)}d_{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}$ with $c_{{\boldsymbol{\alpha}}}>0$. Assume $V(\hbox{\rm{New}}(f))\subseteq\Lambda(f)$. For every ${\boldsymbol{\beta}}\in\Gamma(f)$, let
\begin{equation}
\mathscr{F}({\boldsymbol{\beta}}):=\{\Delta\mid\Delta\textrm{ is a simplex, } {\boldsymbol{\beta}}\in\Delta^{\circ}, V(\Delta)\subseteq\Lambda(f)\}.
\end{equation}
Consider the following SONC decomposition for a nonnegative polynomial $f$:
\begin{equation}\label{sec5-eq}
f=\sum_{{\boldsymbol{\beta}}\in\Gamma(f)}\sum_{\Delta\in\mathscr{F}({\boldsymbol{\beta}})}f_{{\boldsymbol{\beta}}\Delta}+\sum_{{\boldsymbol{\alpha}}\in\tilde{{\mathscr{A}}}}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}},
\end{equation}
where $f_{{\boldsymbol{\beta}}\Delta}$ is a nonnegative circuit polynomial supported on $V(\Delta)\cup\{{\boldsymbol{\beta}}\}$ for each $\Delta$ and $\tilde{{\mathscr{A}}}=\{{\boldsymbol{\alpha}}\in\Lambda(f)\mid{\boldsymbol{\alpha}}\notin\cup_{{\boldsymbol{\beta}}\in\Gamma(f)}\cup_{\Delta\in\mathscr{F}({\boldsymbol{\beta}})}V(\Delta)\}$. If $f$ admits a SONC decomposition of the form \eqref{sec5-eq}, then we say that $f$ decomposes into a {\em sum of nonnegative circuit polynomials with the same support}.

In Theorem \ref{npgp-thm7} and Theorem \ref{npmt-thm1}, we have seen that nonnegative polynomials satisfying certain conditions decompose into sums of nonnegative circuit polynomials with the same support. We shall prove that actually every SONC polynomial decomposes into a sum of nonnegative circuit polynomials with the same support. For the proof, we first recall a connection between nonnegative circuit polynomials and sums of binomial squares (SBS).

\subsection{Nonnegative Circuit Polynomials and Sums of Binomial Squares}
We call a lattice point is {\em even} if it is in $(2{\mathbb{N}})^n$. For a subset $M\subseteq{\mathbb{N}}^n$, define $\overline{A}(M):=\{\frac{1}{2}({\boldsymbol{u}}+{\boldsymbol{v}})\mid{\boldsymbol{u}}\ne{\boldsymbol{v}},{\boldsymbol{u}},{\boldsymbol{v}}\in M\cap(2{\mathbb{N}})^n\}$ as the set of averages of distinct even points in $M$. For a trellis ${\mathscr{A}}$, we say that $M$ is an {\em ${\mathscr{A}}$-mediated set} if ${\mathscr{A}}\subseteq M\subseteq\overline{A}(M)\cup{\mathscr{A}}$ \cite{re1}. It turns out that the problem whether a nonnegative circuit polynomial is an SOS polynomial is closely related to ${\mathscr{A}}$-mediated sets.
\begin{theorem}\label{sec3-thm1}
Let $f=\sum_{{\boldsymbol{\alpha}}\in{\mathscr{A}}} c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}], d\ne0$ be a nonnegative circuit polynomial with ${\boldsymbol{\beta}}\in\hbox{\rm{New}}(f)^{\circ}$. If ${\boldsymbol{\beta}}$ belongs to an ${\mathscr{A}}$-mediated set $M$, then $f$ is a sum of binomial squares, i.e., $f=\sum_{2{\boldsymbol{u}},2{\boldsymbol{v}}\in M}(a_{{\boldsymbol{u}}}{\mathbf{x}}^{{\boldsymbol{u}}}-b_{{\boldsymbol{v}}}{\mathbf{x}}^{{\boldsymbol{v}}})^2$ for $a_{{\boldsymbol{u}}},b_{{\boldsymbol{v}}}\in{\mathbb{R}}$.
\end{theorem}
\begin{proof}
The proof can be easily derived from Theorem 5.2 in \cite{iw} and Theorem 4.4 in \cite{re1}.
\end{proof}

Mediated sets were firstly studied by Reznick in \cite{re1}. For a trellis ${\mathscr{A}}$, there is a maximal ${\mathscr{A}}$-mediated set ${\mathscr{A}}^*$ satisfying $A({\mathscr{A}})\subseteq{\mathscr{A}}^*\subseteq\hbox{\rm{conv}}({\mathscr{A}})\cap{\mathbb{N}}^n$ which contains every ${\mathscr{A}}$-mediated set. Following \cite{re1}, a trellis ${\mathscr{A}}$ is called an {\em $H$-trellis} if ${\mathscr{A}}^*=\hbox{\rm{conv}}({\mathscr{A}})\cap{\mathbb{N}}^n$. The following theorem states that every trellis is an $H$-trellis after multiplied by a sufficiently large number.
\begin{theorem}(\cite[Theorem 3.5]{po})\label{sec3-prop}
Let ${\mathscr{A}}\subseteq{\mathbb{N}}^n$ be a trellis. Then $k{\mathscr{A}}$ is an $H$-trellis for any integer $k\ge n$.
\end{theorem}

From Theorem \ref{sec3-prop} together with Theorem \ref{sec3-thm1}, we know that every $n$-variate nonnegative circuit polynomial supported on $k{\mathscr{A}}$ and a lattice point in the interior of $\hbox{\rm{conv}}(k{\mathscr{A}})$ is a sum of binomial squares for any trellis ${\mathscr{A}}$ and an integer $k\ge n$.
\begin{lemma}\label{sec4-lm1}
Suppose that $f(x_1,\ldots,x_n)\in{\mathbb{R}}[{\mathbf{x}}]$ is a SONC polynomial. Then $f(x_1^k,\ldots,x_n^k)$ is a sum of binomial squares for any integer $k\ge n$.
\end{lemma}
\begin{proof}
Assume $f=\sum f_i$, where $f_i$'s are nonnegative circuit polynomials. For any integer $k\ge n$, since every $f_i(x_1^k,\ldots,x_n^k)$ is a sum of binomial squares, so is $f(x_1^k,\ldots,x_n^k)$.
\end{proof}

\subsection{Supports of Sums of Nonnegative Circuit Polynomials}
Now we can prove: every SONC polynomial decomposes into a sum of nonnegative circuit polynomials with the same support. The proof will take use of the SBS decompositions for SONC polynomials. Hence we first apply the map $x_i\mapsto x_i^k$ to $f\in{\mathbb{R}}[{\mathbf{x}}]$.
\begin{lemma}\label{sec4-lm}
Let $f(x_1,\ldots,x_n)\in{\mathbb{R}}[{\mathbf{x}}]$ and $k$ an odd number. Then $f(x_1,\ldots,x_n)$ decomposes into a sum of nonnegative circuit polynomials with the same support if and only if $f(x_1^k,\ldots,x_n^k)$ decomposes into a sum of nonnegative circuit polynomials with the same support.
\end{lemma}
\begin{proof}
It is immediate from the fact that a polynomial $g(x_1,\ldots,x_n)$ is a nonnegative circuit polynomial if and only if $g(x_1^k,\ldots,x_n^k)$ is a nonnegative circuit polynomial for an odd number $k$.
\end{proof}

If a polynomial $f\in{\mathbb{R}}[{\mathbf{x}}]$ has the form $\sum_{{\boldsymbol{\alpha}}\in\Lambda(f)}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d{\mathbf{x}}^{{\boldsymbol{\beta}}}$, where either ${\boldsymbol{\beta}}\in(2{\mathbb{N}})^n$ and $d>0$, or ${\boldsymbol{\beta}}\notin(2{\mathbb{N}})^n$, then we call $f$ a {\em banana polynomial}. By Theorem \ref{npgp-thm8}, a nonnegative banana polynomial decomposes into a sum of nonnegative circuit polynomials with the same support. If a polynomial $f$ can be written as $f=\sum_{{\boldsymbol{\beta}}\in\Gamma(f)}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(f)}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\beta}}})$ such that every $\sum_{{\boldsymbol{\alpha}}\in\Lambda(f)}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}$ is a nonnegative banana polynomial, then we say that $f$ decomposes into a {\em sum of nonnegative banana polynomials with the same support}.
\begin{theorem}\label{sec3-thm2}
Let $f=\sum_{{\boldsymbol{\alpha}}\in\Lambda(f)}c_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-\sum_{{\boldsymbol{\beta}}\in\Gamma(f)}d_{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\in{\mathbb{R}}[{\mathbf{x}}]$. If $f\in\hbox{\rm{SONC}}$, then $f$ decomposes into a sum of nonnegative circuit polynomials with the same support, i.e. $f$ admits a SONC decomposition of the form \eqref{sec5-eq}.
\end{theorem}
\begin{proof}
By Lemma \ref{sec4-lm}, we only need to prove the theorem for $f(x_1^{2n+1},\ldots,x_n^{2n+1})$. By Theorem \ref{npgp-thm7}, we finish the proof by showing that $f(x_1^{2n+1},\ldots,x_n^{2n+1})$ is a sum of nonnegative banana polynomials with the same support.

For simplicity, let $h=f(x_1^{2n+1},\ldots,x_n^{2n+1})$. By Theorem \ref{sec4-lm1}, we can write $h$ as a sum of binomial squares, i.e. $h=\sum_{i=1}^m(a_i{\mathbf{x}}^{{\boldsymbol{u}}_i}-b_i{\mathbf{x}}^{{\boldsymbol{v}}_i})^2$. Let us do induction on $m$. When $m=1$, $h=(a_1{\mathbf{x}}^{{\boldsymbol{u}}_1}-b_1{\mathbf{x}}^{{\boldsymbol{v}}_1})^2=a_1^2{\mathbf{x}}^{2{\boldsymbol{u}}_1}+b_1^2{\mathbf{x}}^{2{\boldsymbol{v}}_1}-2a_1b_1{\mathbf{x}}^{{\boldsymbol{u}}_1+{\boldsymbol{v}}_1}$ and the conclusion is obvious. Assume that the conclusion is correct for $m-1$. Now consider the case of $m$. Without loss of generality, assume ${\boldsymbol{u}}_m+{\boldsymbol{v}}_m\in\Gamma(h)$. Let $h'=\sum_{i=1}^{m-1}(a_i{\mathbf{x}}^{{\boldsymbol{u}}_i}-b_i{\mathbf{x}}^{{\boldsymbol{v}}_i})^2=\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-\sum_{{\boldsymbol{\beta}}\in\Gamma(h')}d_{{\boldsymbol{\beta}}}'{\mathbf{x}}^{{\boldsymbol{\beta}}}$. By the induction hypothesis, we can write $h'=\sum_{{\boldsymbol{\beta}}\in\Gamma(h')}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}'{\mathbf{x}}^{{\boldsymbol{\beta}}})$ as a sum of nonnegative banana polynomials with the same support. Then
\begin{equation}\label{sec3-eq10}
h=\sum_{{\boldsymbol{\beta}}\in\Gamma(h')}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}'{\mathbf{x}}^{{\boldsymbol{\beta}}})+(a_m{\mathbf{x}}^{{\boldsymbol{u}}_m}-b_m{\mathbf{x}}^{{\boldsymbol{v}}_m})^2.
\end{equation}
From $h=h'+(a_m{\mathbf{x}}^{{\boldsymbol{u}}_m}-b_m{\mathbf{x}}^{{\boldsymbol{v}}_m})^2$, it follows that $\hbox{\rm{supp}}(h)$ and $\hbox{\rm{supp}}(h')$ differ among three elements: $2{\boldsymbol{u}}_m,2{\boldsymbol{v}}_m,{\boldsymbol{u}}_m+{\boldsymbol{v}}_m$. We will obtain the expression $h=\sum_{{\boldsymbol{\beta}}\in\Gamma(h)}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h)}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\beta}}})$ of $h$ as a sum of nonnegative banana polynomials with the same support from (\ref{sec3-eq10}) by adjusting the terms involving $2{\boldsymbol{u}}_m,2{\boldsymbol{v}}_m,{\boldsymbol{u}}_m+{\boldsymbol{v}}_m$ in (\ref{sec3-eq10}).

First let us consider the terms involving $2{\boldsymbol{u}}_m$. If $2{\boldsymbol{u}}_m\notin\Gamma(h')$, then we have nothing to do. If $2{\boldsymbol{u}}_m\in\Gamma(h')$ and $2{\boldsymbol{u}}_m\in\Gamma(h)$, then we must have $d_{2{\boldsymbol{u}}_m}'>a_m^2$. By the equality $\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{2{\boldsymbol{u}}_m}'{\mathbf{x}}^{2{\boldsymbol{u}}_m}+a_m^2{\mathbf{x}}^{2{\boldsymbol{u}}_m}+b_m^2{\mathbf{x}}^{2{\boldsymbol{v}}_m}-2a_mb_m{\mathbf{x}}^{{\boldsymbol{u}}_m+{\boldsymbol{v}}_m}=(1-\frac{a_m^2}{d_{2{\boldsymbol{u}}_m}'})(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}
-d_{2{\boldsymbol{u}}_m}'{\mathbf{x}}^{2{\boldsymbol{u}}_m})+\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}\frac{c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'a_m^2}{d_{2{\boldsymbol{u}}_m}'}{\mathbf{x}}^{{\boldsymbol{\alpha}}}+b_m^2{\mathbf{x}}^{2{\boldsymbol{v}}_m}-2a_mb_m{\mathbf{x}}^{{\boldsymbol{u}}_m+{\boldsymbol{v}}_m}$, we obtain the expression $h=\sum_{{\boldsymbol{\beta}}\in\Gamma(h')\backslash\{2{\boldsymbol{u}}_m\}}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}'{\mathbf{x}}^{{\boldsymbol{\beta}}})+(1-\frac{a_m^2}{d_{2{\boldsymbol{u}}_m}'})(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}
-d_{2{\boldsymbol{u}}_m}'{\mathbf{x}}^{2{\boldsymbol{u}}_m})+\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}\frac{c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'a_m^2}{d_{2{\boldsymbol{u}}_m}'}{\mathbf{x}}^{{\boldsymbol{\alpha}}}+b_m^2{\mathbf{x}}^{2{\boldsymbol{v}}_m}-2a_mb_m{\mathbf{x}}^{{\boldsymbol{u}}_m+{\boldsymbol{v}}_m}$ which is still a sum of nonnegative banana polynomials. If $2{\boldsymbol{u}}_m\in\Gamma(h')$ and $2{\boldsymbol{u}}_m\in\Lambda(h)$, then we must have $a_m^2>d_{2{\boldsymbol{u}}_m}'$ and we can write $h$ as $h=\sum_{{\boldsymbol{\beta}}\in\Gamma(h')\backslash\{2{\boldsymbol{u}}_m\}}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}'{\mathbf{x}}^{{\boldsymbol{\beta}}})+\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}
+(a_m^2-d_{2{\boldsymbol{u}}_m}'){\mathbf{x}}^{2{\boldsymbol{u}}_m}+b_m^2{\mathbf{x}}^{2{\boldsymbol{v}}_m}-2a_mb_m{\mathbf{x}}^{{\boldsymbol{u}}_m+{\boldsymbol{v}}_m}$ which is still a sum of nonnegative banana polynomials. If $2{\boldsymbol{u}}_m\in\Gamma(h')$ and $2{\boldsymbol{u}}_m\notin\hbox{\rm{supp}}(h)$, then the terms $-d_{2{\boldsymbol{u}}_m}'{\mathbf{x}}^{2{\boldsymbol{u}}_m}$ and $a_m^2{\mathbf{x}}^{2{\boldsymbol{u}}_m}$ must be cancelled in (\ref{sec3-eq10}). Hence we obtain the expression of $h$ as $h=\sum_{{\boldsymbol{\beta}}\in\Gamma(h')\backslash\{2{\boldsymbol{u}}_m\}}(\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{{\boldsymbol{\beta}}{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}-d_{{\boldsymbol{\beta}}}'{\mathbf{x}}^{{\boldsymbol{\beta}}})+\sum_{{\boldsymbol{\alpha}}\in\Lambda(h')}c_{2{\boldsymbol{u}}_m{\boldsymbol{\alpha}}}'{\mathbf{x}}^{{\boldsymbol{\alpha}}}
+b_m^2{\mathbf{x}}^{2{\boldsymbol{v}}_m}-2a_mb_m{\mathbf{x}}^{{\boldsymbol{u}}_m+{\boldsymbol{v}}_m}$ which is still a sum of nonnegative banana polynomials.

Continue adjusting the terms involving $2{\boldsymbol{v}}_m$ and ${\boldsymbol{u}}_m+{\boldsymbol{v}}_m$ in the expression of $h$ in a similar way. Eventually we can write $h$ as a sum of nonnegative banana polynomials with the same support as desired.
\end{proof}

\begin{remark}
Theorem \ref{sec3-thm2} ensures that every SONC polynomial admits a SONC decomposition by only using the support from the original polynomial and with no cancellation. This is a very desired property (sparsity-preservation) to design efficient algorithms for sparse polynomial optimization based on SONC decompositions and is a distinguished difference from SOS decompositions.
\end{remark}

\begin{remark}
Although in the proof of Theorem \ref{sec3-thm2}, we use all simplices containing ${\boldsymbol{\beta}}$ as an interior point for each ${\boldsymbol{\beta}}\in\Gamma(f)$, it is possible to obtain a SONC decomposition for $f$ by using less simplices. Actually, by Theorem \ref{sec3-thm2} together with Carath\'eodory's theorem (\cite[Corollary 17.1.2]{ro}), we can write a SONC polynomial $f$ as a sum of at most $|\hbox{\rm{supp}}(f)|$ nonnegative circuit polynomials.
\end{remark}

Finally, we give an example to illustrate that the condition that all of the ${\boldsymbol{\beta}}_j$'s lie in the same side of every hyperplane determined by points among $\{{\boldsymbol{\alpha}}_1,\ldots,{\boldsymbol{\alpha}}_m\}$ in Theorem \ref{npmt-thm1} cannot be dropped. 
\begin{example}
Let $f=1+4x^2+x^4-3x-3x^3$. Then $f\in\hbox{\rm{PSD}}$, but $f\notin\hbox{\rm{SONC}}$.
\end{example}
\begin{proof}
It is easy to verify that the minimum of $f$ is $0$ with the only minimizer $x_*=1$. We have $1=\frac{1}{2}\cdot0+\frac{1}{2}\cdot2=\frac{3}{4}\cdot0+\frac{1}{4}\cdot4$, and $3=\frac{1}{2}\cdot2+\frac{1}{2}\cdot4=\frac{1}{4}\cdot0+\frac{3}{4}\cdot4$.

\begin{center}
\begin{tikzpicture}
\draw (0,0)--(4,0);
\fill (0,0) circle (2pt);
\node[above] (1) at (0,0) {$1$};
\fill (1,0) circle (2pt);
\node[above] (2) at (1,0) {$x$};
\fill (2,0) circle (2pt);
\node[above] (3) at (2,0) {$x^2$};
\fill (3,0) circle (2pt);
\node[above] (4) at (3,0) {$x^3$};
\fill (4,0) circle (2pt);
\node[above] (5) at (4,0) {$x^4$};
\end{tikzpicture}
\end{center}

By Theorem \ref{sec3-thm2} and from the proof of Theorem \ref{npmt-thm1}, we have that if $f\in\hbox{\rm{SONC}}$, then the following linear system
\begin{equation}\label{npmt-eq5}
\begin{cases}
1=\frac{1}{2}s_1+\frac{3}{4}s_3+\frac{1}{4}s_4\\
4x_*^2=\frac{1}{2}s_1+\frac{1}{2}s_3\\
x_*^4=\frac{1}{4}s_2+\frac{1}{2}s_3+\frac{3}{4}s_4\\
3x_*=s_1+s_2\\
3x_*^3=s_3+s_4
\end{cases}
\end{equation}
on variables $\{s_1,s_2,s_3,s_4\}$ should have a nonnegative solution. However, (\ref{npmt-eq5}) has no nonnegative solutions. This contradictory implies $f\notin\hbox{\rm{SONC}}$.
\end{proof}








\bibliographystyle{amsplain}

2020-01-08T02:16:44.000
1804
1804.09455
en
https://arxiv.org/abs/1804.09455
The concept of sums of nonnegative circuit polynomials (SONC) was recently introduced as a new certificate of nonnegativity especially for sparse polynomials. In this paper, we explore the relationship between nonnegative polynomials and SONC polynomials. As a first result, we provide sufficient conditions for nonnegative polynomials with general Newton polytopes to be SONC polynomials, which generalizes the previous result on nonnegative polynomials with simplex Newton polytopes. Secondly, we prove that every SONC polynomial admits a SONC decomposition without cancellation. In other words, SONC decompositions can exactly preserve the sparsity of nonnegative polynomials, which is dramatically different from the classical sum of squares (SOS) decompositions and is a key property to design efficient algorithms for sparse polynomial optimization based on SONC decompositions.
Combinatorics (math.CO); Algebraic Geometry (math.AG)
Nonnegative Polynomials and Circuit Polynomials
Qwen/Qwen-72B
1. YES
2. YES