# Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields

Manuel Bodirsky  Technische Universität, Dresden, Germany  manuel.bodirsky@tu-
dresden.de ,  Mario Kummer  Technische Universität, Dresden, Germany
<EMAIL_ADDRESS>and  Andreas Thom  Technische Universität, Dresden,
Germany<EMAIL_ADDRESS>
###### Abstract.

In this article we develop new methods for exhibiting convex semialgebraic
sets that are not spectrahedral shadows. We characterize when the set of
nonnegative polynomials with a given support is a spectrahedral shadow in
terms of sums of squares. As an application of this result we prove that the
cone of copositive matrices of size $n\geq 5$ is not a spectrahedral shadow,
answering a question of Scheiderer. Our arguments are based on the model
theoretic observation that any formula defining a spectrahedral shadow must be
preserved by every unital ${\mathbb{R}}$-linear completely positive map $R\to
R$ on a real closed field extension $R$ of ${\mathbb{R}}$.

###### 2010 Mathematics Subject Classification:

Primary: 14P10, 90C22

Manuel Bodirsky received funding from the ERC under the European Community’s
Seventh Framework Programme (Grant Agreement no. 681988, CSP-Infinity). Mario
Kummer was partially supported by DFG grant 421473641. Andreas Thom was
partially supported by ERC Consolidator Grant 681207 and DFG SPP 2026.

##  1\. Introduction

A set $S\subseteq{\mathbb{R}}^{n}$ is called a _spectrahedron_ if

$S=\\{(x_{1},\dots,x_{n})\mid A_{0}+A_{1}x_{1}+\dots+A_{n}x_{n}\succeq 0\\}$

for some $k\times k$ real symmetric matrices $A_{0},A_{1},\dots,A_{n}$. Here
$A\succeq 0$ says that the real symmetric matrix $A$ is positive semidefinite,
and the expression $A_{0}+A_{1}x_{1}+\cdots+A_{n}x_{n}\succeq 0$ is called a
_linear matrix inequality (LMI) of size $k$_. Note that spectrahedra are
convex and _semialgebraic_ , i.e., definable over ${\mathbb{R}}$ by a first-
order formula in the language of real-closed fields (i.e., the language of
ordered rings).

There has been ample interest in representing convex semialgebraic sets
$K\subseteq{\mathbb{R}}^{n}$ as a _spectrahedral shadow_. This amounts to
finding real symmetric matrices $A_{0},\ldots,A_{n},B_{1},\ldots,B_{m}$ of the
same size such that

$K=\\{x\in{\mathbb{R}}^{n}\mid\exists y\in{\mathbb{R}}^{m}\colon
A_{0}+x_{1}A_{1}+\cdots+x_{n}A_{n}+y_{1}B_{1}+\cdots{+}y_{m}B_{m}\succeq
0\\}.$

The interest stems primarily from the fact that there are efficient methods
for approximately optimizing a linear function over such a set. It was shown
by Helton and Nie [11] that every convex semialgebraic set satisfying certain
smoothness and curvature conditions is a spectrahedral shadow. Moreover,
Scheiderer proved that every convex semialgebraic set in the plane is a
spectrahedral shadow [30]. On the other hand, not every convex semialgebraic
set is a spectrahedral shadow. The first counterexamples were constructed by
Scheiderer [31]. Further examples were found in [8, 4], both using similar
techniques as Scheiderer in his seminal work.

Recent efforts also focus on finding a representation as spectrahedral shadow
with several LMIs of a bounded size. For instance Averkov [2] showed that the
cone of $k\times k$ real symmetric positive semidefinite matrices has no
semidefinite extended representation with LMIs of size less than $k$ (for a
formal definition, see Section 2). A generalization of this result in terms of
convex geometry was given by Saunderson [29]. On the positive side, Scheiderer
[32] proved that for every closed convex semialgebraic set
$K\subseteq{\mathbb{R}}^{2}$ LMIs of size two are sufficient.

Our approach to these questions is based on an easy consequence of the Tarski
principle for real closed fields. The question whether a given semialgebraic
set $K\subseteq{\mathbb{R}}^{n}$ is a spectrahedral shadow is equivalent to
the question whether $K$ has a primitive positive definition over the
structure $\mathfrak{A}$ with domain $\mathbb{R}$ and with a relation
$S\subseteq{\mathbb{R}}^{n}$ for every spectrahedron $S$. By the Tarski
principle for real closed fields, we may equivalently study this question over
real-closed field extensions $R$ of $\mathbb{R}$ instead of $\mathbb{R}$. More
precisely, if $\phi$ is a formula in the language of real closed fields that
defines $K$, let $K^{*}$ be the set defined by $\phi$ over $R$. Likewise, let
${\mathfrak{A}}^{*}$ denote the structure with domain $R$ which contains for
every formula $\psi$ that defines a spectrahedron over ${\mathbb{R}}$ the
relation defined by $\psi$ over $R$. Then $K$ has a primitive positive
definition in ${\mathfrak{A}}$ if and only if $K^{*}$ has a primitive positive
definition in $\mathfrak{A}^{*}$. A map $h\colon R\to R$ _preserves_ a
relation $K\subseteq R^{n}$ if $(h(a_{1}),\dots,h(a_{n}))\in K$ whenever
$(a_{1},\dots,a_{n})\in K$. We use the easy fact that $K^{*}$ does not have an
existential positive definition in ${\mathfrak{A}}^{*}$ (and hence in
particular no primitive positive definition) if there exists a map $h\colon
R\to R$ that preserves all the relations of ${\mathfrak{A}}^{*}$ but not
$K^{*}$. In Appendix B we discuss this approach in more detail and prove a
converse of the last statement.

We show that a map $L\colon R\to R$ preserves ${\mathfrak{A}}^{*}$ if and only
if it is unital, ${\mathbb{R}}$-linear, and completely positive in the sense
of Operator theory. Thus, in order to prove that $K$ is not a spectrahedral
shadow, it suffices to exhibit a unital, ${\mathbb{R}}$-linear, and completely
positive map $L\colon R\to R$ on a real closed field extension
${\mathbb{R}}\subseteq R$ that does not preserve the set defined by $\phi$. In
this way we prove that the set of copositive matrices of size $n$ is not a
spectrahedral shadow whenever $n\geq 5$, a family of convex semialgebraic sets
that resisted Scheiderer’s efforts, see [31, Question 5.2]. A real symmetric
matrix $A$ is _copositive_ if $x^{\top}Ax\geq 0$ for every non-negative real
vector $x$. Note that for $n\leq 4$ it follows from the main result in [7]
that this set is a spectrahedral shadow.

Note that convexity is not only preserved by conjunction (i.e., intersection)
and existential quantification (i.e., projections), but also by universal
quantification. In the light of the results mentioned above one may ask
whether every convex semi-algebraic set has a definition using a formula from
_positive first-order logic_ over the structure formed by all spectrahedra.
Positive first-order logic is the extension of existential positive logic by
universal quantification (so only negation from first-order logic is
prohibited). Our proof shows that the considered convex semialgebraic sets are
not definable from spectrahedra even in this more expressive logic. The reason
is that the map $L\colon R\to R$ that we construct is _surjective_. Hence, we
may combine the Tarski principle with the easy direction of Lyndon’s
preservation theorem (see, e.g., Corollary 10.3.5 in [13]) to conclude that
for example the set of copositive matrices does not have a definition from
spectrahedra in positive first-order logic.

Apart from the Tarski principle the only ingredient to our proof is a
separation theorem (3.7) that follows from the results in [21]. We will give a
self-contained proof in Appendix A. In particular, we do not make use of the
theory developed in [31]. Our result on copositive matrices is a consequence
of the following more general result:

######  Theorem (see 3.15 below).

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ a finite set and let
$\operatorname{P}_{+}(S)$ the set of all nonnegative polynomials with
coefficients from ${\mathbb{R}}$ whose support is contained in $S$. Then the
following are equivalent:

  1. (1)

$\operatorname{P}_{+}(S)$ is a spectrahedral shadow.

  2. (2)

There exists an integer $d>0$ such that $p(x_{1}^{d},\ldots,x_{n}^{d})$ is a
sum of squares for all $p\in\operatorname{P}_{+}(S)$.

Finally, in Section 4 we reprove Averkov’s above mentioned result in a similar
fashion. Here we use results about positive definite maps [15].

We now give a brief outline of our proof strategy. We first observe in Section
2 that a map $L\colon R\to R$ for some real closed field extension $R$ of
${\mathbb{R}}$ preserves ${\mathfrak{A}}^{*}$ if and only if $L$ is unital,
${\mathbb{R}}$-linear, and completely positive in the sense that applying $L$
entry-wise to a positive semidefinite symmetric matrix over $R$ gives a
positive semidefinite matrix. When $R=R^{\prime}[[\epsilon^{\Lambda}]]$ is the
field of Hahn series with value group $\Lambda$ and coefficients in another
real closed field $R^{\prime}$, we consider maps $L_{f}\colon R\to R$ of the
form
$L_{f}\left(\sum_{a\in\Lambda}c_{a}\epsilon^{a}\right)=\sum_{a\in\Lambda}f(a)c_{a}\epsilon^{a}$
for functions $f\colon\Lambda\to R^{\prime}$. On the other hand, extending $f$
linearly, we obtain a linear functional $T_{f}\colon R^{\prime}[\Lambda]\to
R^{\prime}$ on the group ring of $\Lambda$. The crucial insight of Section 2
is that $L_{f}$ is completely positive whenever $T_{f}$ is positive on every
nonzero square in $R^{\prime}[\Lambda]$. In Section 3 we focus on the case
$\Lambda={\mathbb{Q}}^{n}$. Elements of the group ring
$R^{\prime}[{\mathbb{Q}}^{n}]$ can be regarded as functions on
$(R^{\prime}_{>0})^{n}$. If such a function takes only nonnegative values but
is not a sum of squares in $R^{\prime}[{\mathbb{Q}}^{n}]$, then it can be
separated by a linear functional $T_{f}$ from the cone of sums of squares
after a base change to a larger real closed field by 3.7. The corresponding
map $L_{f}$ is then completely positive but does not preserve a certain convex
cone of nonnegative polynomials. Applying this construction to the so-called
Horn polynomial proves that the cone of copositive matrices of size $n\geq 5$
is not a spectrahedral shadow.

Acknowledgements. We would like to thank Claus Scheiderer for helpful comments
on a previous version of the manuscript.

##  2\. $k$-positive maps

In this section let $R$ always be a real closed field extension of
${\mathbb{R}}$. Let $\Gamma_{k}$ be the set of all first-order formulas in the
language of real closed fields with parameters from ${\mathbb{R}}$ that
express a linear matrix inequality of size $k$ with coefficients from
${\mathbb{R}}$, and let $\Gamma=\cup_{k=1}^{\infty}\Gamma_{k}$. Let
${\mathfrak{A}}_{k}$ be the relational structure with domain ${\mathbb{R}}$
whose relations consist of the sets defined by the formulas in $\Gamma_{k}$.
We follow standard terminology in model theory, see, e.g., [13, 33]. For the
convenience of the reader, we have collected the relevant concepts in Appendix
B.1. The signature of $\mathfrak{A}_{k}$ should not be confused with the
signature of real closed fields. If a set $K$ has a primitive positive
definition over ${\mathfrak{A}}_{k}$ then we say that $K$ has a _semidefinite
extended formulation with LMIs of size $k$_, following the terminology of
Averkov [2].

We say that a map $h\colon R\to R$ _preserves_ a formula in the language of
real closed fields if it preserves the relation defined by the formula over
$R$. The map $h$ is called _unital_ if it preserves the formula $x=1$, and for
$R^{\prime}\subseteq R$ it is called _$R^{\prime}$ -linear_ if it preserves
the formula $z=\lambda\cdot x+\mu\cdot y$ for all $\lambda,\mu\in R^{\prime}$.

######  Definition 2.1.

Let $k\in{\mathbb{Z}}_{>0}$. A map $L\colon R\to R$ is called _$k$ -positive_
if for every $k\times k$ symmetric positive semidefinite matrix
$A=(a_{ij})_{i,j}$ with $a_{ij}\in R$ the matrix $L(A):=(L(a_{ij}))_{i,j}$ is
positive semidefinite as well. For technical reasons, we declare every map
$L\colon R\to R$ to be $0$-positive. If $L$ is $k$-positive for every $k$,
then, following the nomenclature of operator theory (see, e.g., [6, §1.5]), we
say that $L$ is _completely positive_.

######  Remark 2.2.

Note that if $L\colon R\to R$ is $k$-positive, then it is also
$k^{\prime}$-positive for all $k^{\prime}\in\\{0,\ldots,k\\}$ since principal
submatrices of positive semidefinite matrices are again positive semidefinite.

######  Lemma 2.3.

Let $k\in{\mathbb{Z}}_{>0}$. A map $L\colon R\to R$ preserves all formulas in
$\Gamma_{k}$ (respectively $\Gamma$) if and only if $L$ is unital,
${\mathbb{R}}$-linear, and $k$-positive (respectively completely positive).

###### Proof.

Assume that $L$ preserves all formulas in $\Gamma_{k}$. The formula $x=1$ is
equivalent to

${\begin{pmatrix}x-1\end{pmatrix}\succeq
0\wedge\begin{pmatrix}1-x\end{pmatrix}\succeq 0.}$

Thus $L(1)=1$. A similar argument shows that $z=\lambda\cdot x+\mu\cdot y$ is
in $\Gamma_{k}$ for all $\lambda,\mu\in{\mathbb{R}}$. To prove that $L$ is
$k$-positive, note that a symmetric matrix $A=(a_{ij})_{1\leq i,j\leq k}$ is
positive semidefinite if and only if
$(a_{11},a_{12},\dots,a_{1k},a_{22},a_{23},\dots,a_{{kk}})$ satisfies the
linear matrix inequality $\sum_{1\leq i\leq j\leq k}x_{ij}E_{ij}\succeq 0$
where $E_{ij}$ has entry $1$ at position $i,j$ and at position $j,i$ and entry
$0$ at all other positions. Since $L$ preserves this formula, we have that
$L(A)\succeq 0$ whenever $A\succeq 0$.

Conversely, assume that $L$ is unital, ${\mathbb{R}}$-linear, and
$k$-positive. Consider $k\times k$ real symmetric matrices
$A_{0},A_{1},\ldots,A_{n}$. Let

$K=\\{x\in R^{n}\mid A_{0}+x_{1}A_{1}+\cdots+x_{n}A_{n}\succeq 0\\}$

and let $x=(x_{1},\ldots,x_{n})\in K$. Then $L(x)=(L(x_{1}),\ldots,L(x_{n}))$
is also in $K$. Indeed, by the properties of $L$ we have

$\displaystyle A_{0}+L(x_{1})A_{1}+\cdots+L(x_{n})A_{n}$
$\displaystyle=L(A_{0}+x_{1}A_{1}+\cdots+x_{n}A_{n})\succeq 0.$

######  Lemma 2.4.

Let $R\subset R^{\prime}$ a field extension and $L\colon R^{\prime}\to
R^{\prime}$ be an $R$-linear map. Let $A$ be an $m\times n$ matrix with
entries in $R^{\prime}$. Let $M$ and $N$ be $a\times m$ and $n\times b$
matrices with entries in $R$. Then we have $L(MAN)=ML(A)N$.

###### Proof.

This follows directly from $R$-linearity. ∎

Now let $\Lambda$ a divisible ordered abelian group. We consider
$H=R[[\epsilon^{\Lambda}]]$, the field of Hahn series over $R$ with value
group $\Lambda$ and the valuation $v\colon H\to\Lambda\cup\\{\infty\\}$ given
by $v\left(\sum_{e\in\Lambda}c_{e}\epsilon^{e}\right)=\min\\{e\in\Lambda\mid
c_{e}\neq 0\\}$. Since $H$ is real closed [1, page 218, (2)], it is equipped
with an order $\leq$ defined by $x\leq y\Leftrightarrow\exists z(z^{2}+x=y)$.
Further, let ${\mathfrak{o}}$ the valuation ring of $H$, namely all elements
of $H$ with nonnegative valuation. Then ${\mathfrak{o}}$ is a local ring with
residue field $R$, the maximal ideal consisting of all elements with positive
valuation. We denote by $\pi\colon{\mathfrak{o}}\to R$ the natural projection.

######  Lemma 2.5.

Let $L\colon H\to H$ be $R$-linear and $(k-1)$-positive and suppose that for
all $a_{1},\ldots,a_{k}\in H_{>0}$ with $v(a_{1})<\cdots<v(a_{k})$ the matrix
$L(a\cdot a^{\top})$, where $a=(a_{1},\ldots,a_{k})^{\top}$, is positive
semidefinite. Then $L$ is $k$-positive.

###### Proof.

Let $B$ be a $k\times k$ symmetric positive semidefinite matrix over $H$. Then

$B=\sum_{i=1}^{k}b_{i}\cdot b_{i}^{\top}$

for some column vectors $b_{1},\ldots,b_{k}\in H^{k}$. Since $L$ is
$R$-linear, we have

$L(B)=\sum_{j=1}^{k}L(b_{i}\cdot b_{i}^{\top}).$

Since the sum of positive semidefinite matrices is positive semidefinite, it
therefore suffices to show that $L(a\cdot a^{\top})$ is positive semidefinite
for all $a=(a_{1},\ldots,a_{k})^{\top}$ with $a_{1},\dots,a_{k}\in H$. Since
$L$ is $(k-1)$-positive, we may assume that $a_{i}\neq 0$ for all $i$. Let
$M\in\operatorname{{\mathbf{GL}}}_{n}(R)$. The matrix $L(a\cdot a^{\top})$ is
positive semidefinite if and only if $ML(a\cdot a^{\top})M^{\top}$ is positive
semidefinite, which equals $L((Ma)\cdot(Ma)^{\top})$ by 2.4. Thus, after
choosing $M$ to be a suitably signed permutation matrix, we may assume that
$a_{1}\geq a_{2}\geq\cdots\geq a_{k}>0$. This implies that
$v(a_{1})\leq\cdots\leq v(a_{k})$. Now, after choosing $M$ to be a product of
suitable elementary matrices, we can make each inequality strict. ∎

######  Lemma 2.6.

Let $A$ be a symmetric $n\times n$ matrix with entries in ${\mathfrak{o}}$.
Then the following holds:

  1. (1)

If $A=(a_{ij})_{1\leq i,j\leq n}$ is positive semidefinite, then
$\pi(A)=(\pi(a_{ij}))_{1\leq i,j\leq n}$ is positive semidefinite.

  2. (2)

If $\pi(A)$ is positive definite, then $A$ is positive definite.

###### Proof.

We use the well-known fact that a symmetric matrix is positive semidefinite
(positive definite) if and only if all its principal minors are nonnegative
(positive, respectively); see, e.g., [14, Theorem 7.2.5]). Let
$x\in{\mathfrak{o}}$ with $x\geq 0$. Since every nonnegative element in
${\mathfrak{o}}$ has a square root in ${\mathfrak{o}}$, we have that
$\pi(x)\in R$ has a square root as well and hence $\pi(x)\geq 0$. If $B$ is a
principal submatrix of $A$, then $\det(\pi(B))=\pi(\det(B))$. Therefore, if
every principal minor of $A$ is nonnegative, the same is true for every
principal minor of $\pi(A)$. This shows (1). For proving (2) assume that $A$
is not positive definite. Then there is a principal minor of $A$ which is
nonpositive. The same minor of $\pi(A)$ will also be nonpositive showing that
$\pi(A)$ is not positive definite. ∎

######  Remark 2.7.

Note that the converse of neither $(1)$ nor $(2)$ in 2.6 is true, as witnessed
by the $1\times 1$ matrices $(-\epsilon)$ and $(\epsilon)$.

For any function $f\colon\Lambda\to R$ we define the function $L_{f}\colon
H\to H$ via

$L_{f}\left(\sum_{e\in\Lambda}c_{e}\epsilon^{e}\right)=\sum_{e\in\Lambda}f(e)c_{e}\epsilon^{e}.$

We want to derive a criterion on $f$ for $L_{f}$ to be $k$-positive. We start
with the following refinement of 2.5.

######  Lemma 2.8.

Let $L\colon H\to H$ be $R$-linear and $(k-1)$-positive and suppose that for
all $a_{1},\ldots,a_{k}\in H_{>0}$ with $v(a_{1})<\cdots<v(a_{k})$ and
$\pi(\frac{a_{i}}{\epsilon^{v(a_{i})}})=1$ the matrix $L(a\cdot a^{\top})$ is
positive semidefinite, where $a=(a_{1},\ldots,a_{k})^{\top}$. Then $L$ is
$k$-positive.

###### Proof.

This follows in the same way as 2.5 by another multiplication with a suitable
diagonal matrix. ∎

######  Corollary 2.9.

Let $L\colon H\to H$ be $R$-linear and suppose that for all
$a_{1},\ldots,a_{k}\in H_{>0}$ with $v(a_{1})<\cdots<v(a_{k})$ and
$\pi(\frac{a_{i}}{\epsilon^{v(a_{i})}})=1$ the matrix $L(a\cdot a^{\top})$ is
positive semidefinite, where $a=(a_{1},\ldots,a_{k})^{\top}$. Then $L$ is
$k$-positive.

###### Proof.

For every $i\in\\{0,\ldots,k\\}$ we prove that $L$ is $i$-positive by
induction on $i$. The case $i=0$ is trivial. Let $i\in\\{1,\ldots,k\\}$ and
assume that $L$ is $(i-1)$-positive. Let $a_{1},\ldots,a_{k}\in H_{>0}$ with
$v(a_{1})<\cdots<v(a_{k})$ and $\pi(\frac{a_{i}}{\epsilon^{v(a_{i})}})=1$. By
assumption $L(a\cdot a^{\top})$ is positive semidefinite. This implies in
particular that the top left $i\times i$ submatrix of $L(a\cdot a^{\top})$ is
positive semidefinite as well. Thus, we can apply 2.8 which proves that $L$ is
$i$-positive. ∎

For later reference we also note the following condition for $L_{f}$ being a
bijection.

######  Lemma 2.10.

Let $f\colon\Lambda\to R$ be such that $L_{f}\colon H\to H$ is unital and
$2$-positive. Then $L_{f}$ is bijective.

###### Proof.

Let $a\in\Lambda$ and consider the positive semidefinite matrix

$A=\begin{pmatrix}\epsilon^{a}&1\\\ 1&\epsilon^{-a}\end{pmatrix}.$

Since $L_{f}$ is unital, we have

$L_{f}(A)=\begin{pmatrix}f(a)\epsilon^{a}&1\\\
1&f(-a)\epsilon^{-a}\end{pmatrix}.$

Since $L_{f}$ is $2$-positive, this shows that $f(a)f(-a)\geq 1$, so in
particular $f(a)\neq 0$. Now one can define

$g:\Lambda\to R,\,a\mapsto\frac{1}{f(a)}$

and one has $L_{f}\circ L_{g}=L_{g}\circ L_{f}=\textrm{id}_{H}$. ∎

######  Definition 2.11.

A function $f\colon\Lambda\to R$ is called _$k$ -positive semidefinite_ if for
all $x_{1},\ldots,x_{k}\in\Lambda$ the matrix $(f(x_{i}+x_{j}))_{i,j}$ is
positive semidefinite. It is called _$k$ -positive definite_ if for all
pairwise different $x_{1},\ldots,x_{k}\in\Lambda$ the matrix
$(f(x_{i}+x_{j}))_{i,j}$ is positive definite. Finally, the function
$f\colon\Lambda\to R$ is called _positive semidefinite_ (_positive definite_
111In [3, page 88], positive definite functions are called _positive definite
in the semigroup sense_ ; we use the shorter form since no confusion can arise
in our context.) if $f$ is $k$-positive semidefinite ($k$-positive definite)
for all $k\in{\mathbb{Z}}_{\geq 0}$.

######  Remark 2.12.

If $f_{1},f_{2}\colon\Lambda\to R$ are $k$-positive (semi-)definite and
$\lambda,\mu\in R_{>0}$, then $\lambda f_{1}$, $\mu f_{2}$ and $\lambda
f_{1}+\mu f_{2}$ are $k$-positive (semi-)definite as well. Indeed, this
follows from the fact that the cone of positive (semi-)definite matrices is
convex.

The motivation for considering 2.11 is the following result.

######  Theorem 2.13.

Let $f\colon\Lambda\to R$ and consider $L_{f}\colon H\to H$ as defined above.

  1. (1)

If $f$ is $k$-positive definite, then $L_{f}$ is $k$-positive.

  2. (2)

If $L_{f}$ is $k$-positive, then $f$ is $k$-positive semidefinite.

###### Proof.

In order to prove $(2)$ let $v_{1},\ldots,v_{k}\in\Lambda$. We have to prove
that $(f(v_{i}+v_{j}))_{i,j}$ is positive semidefinite. Let
$a=(\epsilon^{v_{1}},\ldots,\epsilon^{v_{k}})^{\top}$. By assumption
$L_{f}(a\cdot a^{\top})$ is positive semidefinite. Let
$b=(\epsilon^{-v_{1}},\ldots,\epsilon^{-v_{k}})^{\top}$ and let $B=b\cdot
b^{\top}$ which is positive semidefinite. Then the Hadamard product $C$ of
$L_{f}(a\cdot a^{\top})$ with $B$ is positive semidefinite as well by the
Schur product theorem. Hence, 2.6(1) implies that $\pi(C)$ is positive
semidefinite. One calculates that $\pi(C)$ is the matrix
$(f(v_{i}+v_{j}))_{1\leq i,j\leq k}$, which proves $(2)$.

We will prove $(1)$ by applying 2.9. To that end let $a_{1},\ldots,a_{k}\in
H_{>0}$ be such that $v(a_{1})<\cdots<v(a_{k})$ and
$\pi(\frac{a_{i}}{\epsilon^{v(a_{i})}})=1$. We have to show that the matrix
$L_{f}(a\cdot a^{\top})$ is positive semidefinite, where
$a=(a_{1},\ldots,a_{k})^{\top}$. Let
$b=(\epsilon^{-v(a_{1})},\ldots,\epsilon^{-v(a_{k})})^{\top}$ and $B=b\cdot
b^{\top}$. Since $B$ is positive semidefinite of rank one with nonzero
entries, the matrix $L_{f}(a\cdot a^{\top})$ is positive semidefinite if and
only if its Hadamard product $C$ with $B$ is positive semidefinite. As above
one calculates that $\pi(C)$ is the matrix $(f(v(a_{i})+v(a_{j})))_{1\leq
i,j\leq k}$ which is positive definite since $f$ is $k$-positive definite and
$v(a_{1}),\dots,v(a_{k})$ are pairwise different. Thus, $C$ is positive
definite by 2.6(2). Therefore, $L_{f}(a\cdot a^{\top})$ is positive
semidefinite and $(1)$ follows from 2.9. ∎

######  Remark 2.14.

Another point of view on positive semidefinite functions can be taken by
looking at the group ring $R[\Lambda]$. The group ring $R[\Lambda]$ can be
identified with the subring of $H=R[[\epsilon^{\Lambda}]]$ consisting of
series with finite support. Now any function $f\colon\Lambda\to R$ can be
extended linearly to an $R$-linear functional $T_{f}\colon R[\Lambda]\to R$.
An element of $R[\Lambda]$ is of the form
$a=\sum_{i=1}^{k}c_{i}\epsilon^{a_{i}}$ for $k\in{\mathbb{N}}$,
$(c_{1},\dots,c_{k})\in R^{k}$, and $(a_{1},\dots,a_{k})\in\Lambda^{k}$. Then
we have

$\displaystyle T_{f}(a^{2})$
$\displaystyle=T_{f}\left(\sum_{i,j=1}^{k}c_{i}c_{j}\epsilon^{a_{i}+a_{j}}\right)=\sum_{i,j}^{k}c_{i}c_{j}f(a_{i}+a_{j})$
$\displaystyle=\begin{pmatrix}c_{1}&\ldots&c_{k}\end{pmatrix}\cdot(f(a_{i}+a_{j}))_{1\leq
i,j\leq k}\cdot\begin{pmatrix}c_{1}\\\ \vdots\\\ c_{k}\end{pmatrix}.$

From this we see that $f$ is positive semidefinite (positive definite) if and
only if $T_{f}(a^{2})\geq 0$ ($T_{f}(a^{2})>0$, respectively) for all $a\in
R[\Lambda]\setminus\\{0\\}$.

For the rest of this section we focus on the case $\Lambda={\mathbb{R}}$. Let
${\mathcal{H}}({\mathbb{C}})$ be the ring of holomorphic functions on
${\mathbb{C}}$. We have a homomorphism of ${\mathbb{R}}$-algebras
$\Psi\colon{\mathbb{R}}[\Lambda]\to{\mathcal{H}}({\mathbb{C}})$ defined as
follows. For $a\in{\mathbb{R}}$, set $\Psi(\epsilon^{a})$ to be the
holomorphic function $z\mapsto\exp(az)$ and extend linearly to all of
${\mathbb{R}}[\Lambda]$.

######  Lemma 2.15.

Let $g\in{\mathbb{R}}[\Lambda]$. If $\Psi(g)$ vanishes on $[a,b]$ for $a<b$,
then $g=0$ as element of ${\mathbb{R}}[\Lambda]$. In particular, the
homomorphism $\Psi$ is injective.

###### Proof.

Let $g=\sum_{i=1}^{n}c_{i}\epsilon^{a_{i}}$ for some
$c_{i},a_{i}\in{\mathbb{R}}$, $i=1,\ldots,n$, with $a_{1}<\cdots<a_{n}$. The
identity theorem from complex analysis implies that $\Psi(g)$ vanishes on all
of ${\mathbb{C}}$. Thus we have $\sum_{i=1}^{n}c_{i}\exp(a_{i}z)=0$ for all
$z\in{\mathbb{C}}$. Linear independence of characters now implies that
$c_{i}=0$ for $i\in\\{1,\ldots,n\\}$ because the functions
${\mathbb{R}}\to{\mathbb{R}},\,t\mapsto\exp(a_{i}t)$ for
$i\in\\{1,\ldots,n\\}$ are pairwise different characters. ∎

This enables us to construct positive definite functions
${\mathbb{R}}\to{\mathbb{R}}$.

######  Example 2.16.

Let $\Lambda={\mathbb{R}}$ and $\mu$ a measure on ${\mathbb{R}}$ with
$\int\exp(ax)d\mu(x)<\infty$ for all $a\in{\mathbb{R}}$. Then the functional

$T\colon{\mathbb{R}}[\Lambda]\to{\mathbb{R}},\,g\mapsto\int\Psi(g)(x)d\mu(x)$

clearly satisfies $T(g^{2})\geq 0$ for all $g\in{\mathbb{R}}[\Lambda]$. If we
choose for instance $\mu$ to be the pushforward to ${\mathbb{R}}$ of the
Lebesgue measure on some compact interval $[a,b]$ with $a<b$, then we even
have $T(g^{2})>0$ for every $g\in{\mathbb{R}}[\Lambda]\setminus\\{0\\}$.
Indeed, for any $g\in{\mathbb{R}}[\Lambda]$ with $T(g^{2})=0$ the function
$\Psi(g)$ must vanish on $[a,b]$, which implies $g=0$ by 2.15. Let
$f\colon{\mathbb{R}}\to{\mathbb{R}}$ defined by $f(a)=T(\epsilon^{a})$ for
$a\in{\mathbb{R}}$. Since $T$ is ${\mathbb{R}}$-linear, we have $T=T_{f}$ and
thus $f$ is positive definite by 2.14.

######  Corollary 2.17.

Let $\Lambda$ be a divisible ordered abelian group whose dimension as a
${\mathbb{Q}}$-vector space is at most $2^{\aleph_{0}}$. Further, let $R$ be a
real closed field extension of ${\mathbb{R}}$. Then there exists an $R$-linear
map $T\colon R[\Lambda]\to R$ which satisfies $T(g^{2})>0$ for every $g\in
R[\Lambda]\setminus\\{0\\}$.

###### Proof.

By 2.16 there exists a positive definite map
$f\colon{\mathbb{R}}\to{\mathbb{R}}$. By our assumptions on $\Lambda$ there is
an injective group homomorphism $\iota_{1}\colon\Lambda\to{\mathbb{R}}$. Let
$\iota_{2}\colon{\mathbb{R}}\to R$ be the inclusion map. Then the map
$\bar{f}=\iota_{2}\circ f\circ\iota_{1}\colon\Lambda\to R$ is also positive
definite. By 2.14 the map $T_{\bar{f}}\colon R[\Lambda]\to R$ has the desired
properties. ∎

##  3\. The group ring $R[{\mathbb{Q}}^{n}]$

From now on let $R$ be a real closed field (not necessarily an extension of
${\mathbb{R}}$). We fix a total order on ${\mathbb{Q}}^{n}$ that is
translation-invariant, for instance the lexicographical ordering. As in 2.14
we consider the group ring $R[{\mathbb{Q}}^{n}]$ as the subring of
$R[[\epsilon^{{\mathbb{Q}}^{n}}]]$ of series with finite support. For
$a=(a_{1},\ldots,a_{n})\in{\mathbb{Q}}^{n}$ we write

$\epsilon^{a}=\epsilon_{1}^{a_{1}}\cdots\epsilon_{n}^{a_{n}}.$

By plugging in positive elements from $R$ for $\epsilon_{i}$ we can regard
elements from $R[{\mathbb{Q}}^{n}]$ as functions on the positive orthant
$R_{>0}^{n}$. Clearly, every element of $R[{\mathbb{Q}}^{n}]$ that can be
written as a sum of squares of elements of $R[{\mathbb{Q}}^{n}]$ is
nonnegative on $R_{>0}^{n}$. We will see in 3.4 that the converse to this is
not true. We will consider the polynomial ring
$R[\underline{x}]=R[x_{1},\ldots,x_{n}]$ as subring of $R[{\mathbb{Q}}^{n}]$
by replacing $x_{i}$ by $\epsilon_{i}$.

######  Remark 3.1.

Evaluating elements $f\in R[{\mathbb{Q}}^{n}]$ at negative numbers is in
general not well defined since the exponents can have even denominator.
Similarly, a polynomial can be a sum of squares of elements from the group
ring $R[{\mathbb{Q}}^{n}]$ without being nonnegative on all of $R^{n}$. For
example, $\epsilon\in R[\epsilon]$ takes negative values on $R$, but equals
$(\epsilon^{\frac{1}{2}})^{2}$.

######  Remark 3.2.

A polynomial $p\in R[\underline{x}]$ is a sum of squares of elements in
$R[{\mathbb{Q}}^{n}]$ if and only if $p(x_{1}^{m},\dots,x_{n}^{m})$ is a sum
of squares of polynomials from $R[\underline{x}]$ for some
$m\in{\mathbb{Z}}_{>0}$. Indeed, negative exponents cannot appear in the sum
of squares decomposition since lowest degree terms cannot cancel out.

######  Example 3.3.

Consider the Motzkin polynomial

$M=x_{3}^{6}-3x_{1}^{2}x_{2}^{2}x_{3}^{2}+x_{1}^{2}x_{2}^{4}+x_{1}^{4}x_{2}^{2}\in
R[x_{1},x_{2},x_{3}].$

It follows from the inequality of arithmetic and geometric means that $M$ is
nonnegative on $R^{3}$ (since
$\frac{1}{3}x_{1}^{4}x_{2}^{2}+\frac{1}{3}x_{1}^{2}x_{2}^{4}+\frac{1}{3}x_{3}^{6}\geq
x_{1}^{4/3}x_{2}^{2/3}x_{1}^{2/3}x_{2}^{4/3}x_{3}^{6/3}$) but it is not a sum
of squares of polynomials from $R[\underline{x}]$ [18]. However,
$M(x_{1}^{2},x_{2}^{2},x_{3}^{2})$ is a sum of squares of polynomials [28,
Example 5.3]:

$M(x_{1}^{2},x_{2}^{2},x_{3}^{2})=2\cdot(x_{1}^{3}x_{2}^{3}-x_{1}x_{2}x_{3}^{4})^{2}+(x_{1}^{4}x_{2}^{2}-x_{1}^{2}x_{2}^{4})^{2}+(x_{3}^{6}-x_{1}^{2}x_{2}^{2}x_{3}^{2})^{2}.$

This shows that $M$ is a sum of squares of elements of $R[{\mathbb{Q}}^{3}]$.

######  Example 3.4.

Consider the _Horn polynomial_

$h=(x_{1}+x_{2}+x_{3}+x_{4}+x_{5})^{2}-4(x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{4}+x_{4}x_{5}+x_{5}x_{1}).$

It was proven in [10, p. 335] that $h$ is nonnegative on the positive orthant.
However, for any integer $k>0$ the polynomial $h(x_{1}^{k},\ldots,x_{5}^{k})$
is not a sum of squares of elements of $R[{\underline{x}}]$. This was shown in
[26, §4] by adapting the proof from [10] for the case $k=2$. This shows that
$h$ is not a sum of squares of elements of $R[{\mathbb{Q}}^{5}]$.

For the sake of completeness, we repeat the argument here. Assume $h$ is a sum
of squares in $R[{\mathbb{Q}}^{5}]$. Then for some integer $d>0$ the
polynomial

$H_{d}=h(x_{1}^{{d}},\ldots,x_{5}^{{d}})=g_{1}^{2}+\dots+g_{m}^{2}$

is a sum of squares of homogeneous polynomials $g_{j}$ of degree $d$ (since
highest and lowest degree terms cannot cancel out). Restricting $H_{d}$ to
$x_{i}=x_{i+1}=0$ we obtain

$(x_{i+2}^{d}-x_{i+3}^{d}+x_{i+4}^{d})^{2}$

for $i\in\\{1,\dots,5\\}$ where the indices are taken modulo $5$. Thus, for
$j\in\\{1,\dots,m\\}$ the restriction of $g_{j}$ to $x_{i}=x_{i+1}=0$ must be
a scalar multiple of $x_{i+2}^{d}-x_{i+3}^{d}+x_{i+4}^{d}$. Indeed, if

$(x_{i+2}^{d}-x_{i+3}^{d}+x_{i+4}^{d})^{2}=g_{1}^{\prime
2}+\dots+g_{m}^{\prime 2}$

for $g_{j}^{\prime}\in{\mathbb{R}}[x_{i+2},x_{i+3},x_{i+4}]$, then each
$g_{j}^{\prime}$ must vanish on the real zero set of
$x_{i+2}^{d}-x_{i+3}^{d}+x_{i+4}^{d}$. The latter is Zariski dense in the
complex zero set which implies by Hilbert’s Nullstellensatz that
$g_{j}^{\prime}$ is divisible by the irreducible polynomial
$x_{i+2}^{d}-x_{i+3}^{d}+x_{i+4}^{d}$. Letting $c_{i}$ be the coefficient of
$x_{i}^{d}$ in $g_{j}$, this shows that $c_{i}=-c_{i+1}$. Since $5$ is an odd
number, this actually implies that $c_{1}=\cdots=c_{5}=0$. In particular, we
have that $g_{j}(1,0,\ldots,0)=0$ for $j\in\\{1,\ldots,m\\}$. However, since
$H_{d}(1,0,\ldots,0)\neq 0$, this is a contradiction.

######  Example 3.5.

The Horn polynomial considered in 3.4 is a special case of the following more
general construction. Recall that a _stable set_ of a graph $G=(V,E)$ is a
subset of elements of $V$ that are pairwise not adjacent to each other. The
_stability number_ $\alpha(G)$ of $G$ is the largest size of a stable set of
$G$. By a theorem of Motzkin–Straus [19] the quadratic form associated to the
symmetric matrix

$Q(G)=\alpha(G)(I+A)-J$

is nonnegative on the positive orthant [23, Example 3.163], i.e., the matrix
$Q(G)$ is _copositive_. Here, $A$ is the adjacency matrix of $G$ and $J$ is
the all-ones matrix. The Horn polynomial corresponds to the matrix $Q(C_{5})$
where $C_{5}$ is the five-cycle. The argument from 3.4 can in fact be applied
to any odd cycle of size at least five.

We also note that nonnegative elements in ${\mathbb{R}}[{\mathbb{Q}}^{n}]$
cannot be distinguished from sums of squares by an ${\mathbb{R}}$-linear
functional ${\mathbb{R}}[{\mathbb{Q}}^{n}]\to{\mathbb{R}}$.

######  Proposition 3.6.

Let $T\colon{\mathbb{R}}[{\mathbb{Q}}^{n}]\to{\mathbb{R}}$ be an
${\mathbb{R}}$-linear functional with $T(a^{2})\geq 0$ for all
$a\in{\mathbb{R}}[{\mathbb{Q}}^{n}]$ and let
$p\in{\mathbb{R}}[{\mathbb{Q}}^{n}]$ be nonnegative on $R_{>0}^{n}$. Then
$T(p)\geq 0$.

###### Proof.

In the case $n=1$ the statement of [3, Proposition 5.10, page 211] says that
for every such $T$ there is a measure $\mu$ on $[0,\infty)$ such that
$T(g)=\int gd\mu$. This shows in particular that $T(p)\geq 0$. The case $n>1$
then follows from [3, Theorem 5.4, page 204]. ∎

However, if we replace the target field by some real closed extension field,
then separation by a linear functional is always possible. The following
theorem follows from the results of [21]. We will give self-contained proofs
in Appendix A.

######  Theorem 3.7.

Let $p\in R[{\mathbb{Q}}^{n}]$ not be a sum of squares of elements of
$R[{\mathbb{Q}}^{n}]$. Then there exists a real closed field extension
$R^{\prime}\supset R$ and an $R^{\prime}$-linear functional $T\colon
R^{\prime}[{\mathbb{Q}}^{n}]\to R^{\prime}$ such that for every $a\in
R^{\prime}[{\mathbb{Q}}^{n}]\setminus\\{0\\}$ we have $T(a^{2})>0$ and
$T(p)<0$.

###### Proof.

By A.3 there exists a real closed field extension $R^{\prime}\supset R$ and an
$R^{\prime}$-linear functional $T^{\prime}\colon
R^{\prime}[{\mathbb{Q}}^{n}]\to R^{\prime}$ such that for every $a\in
R^{\prime}[{\mathbb{Q}}^{n}]$ we have $T^{\prime}(a^{2})\geq 0$ and
$T^{\prime}(p)<0$. Further, by 2.17 there exists an $R^{\prime}$-linear map
$T_{0}\colon R^{\prime}[{\mathbb{Q}}^{n}]\to R^{\prime}$ that satisfies
$T_{0}(a^{2})>0$ for all $0\neq a\in R^{\prime}[{\mathbb{Q}}^{n}]$. Let
$\lambda\in R^{\prime}$ be such that $\lambda>0$ and
$\lambda|T_{0}(p)|<|T^{\prime}(p)|$. Then $T=\lambda T_{0}+T^{\prime}$ has the
desired properties. ∎

Now we are ready to formulate and prove our main result.

######  Definition 3.8.

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ be a finite set and $R$ a real closed
field. We denote by $\operatorname{P}(S,R)$ the (finite dimensional)
$R$-vector space of all polynomials in $n$ variables and coefficients in $R$
whose support is contained in $S$. We further denote by
$\operatorname{P}_{+}(S,R)$ the convex cone of all $p\in\operatorname{P}(S,R)$
such that $p(x)\geq 0$ for all $x\in R^{n}$. Finally, we denote by
$\Sigma(S,R)$ the convex cone of all $P\in\operatorname{P}(S,R)$ that are a
sum of squares of polynomials (with coefficients in $R$). If we do not specify
the real closed field, then we work over the real numbers, i.e., we write
$\operatorname{P}(S)=\operatorname{P}(S,{\mathbb{R}})$,
$\operatorname{P}_{+}(S)=\operatorname{P}_{+}(S,{\mathbb{R}})$, and
$\Sigma(S)=\Sigma(S,{\mathbb{R}})$.

######  Remark 3.9.

Note that $\operatorname{P}_{+}(S,R)$ is the set of all tuples $(c_{s})_{s\in
S}\subset R^{S}$ such that

$\forall x_{1}\cdots\forall x_{n}\colon\,\sum_{s\in
S}c_{s}\cdot\prod_{i=1}^{n}x_{i}^{s_{i}}\geq 0$

holds true over $R$. This is a formula in the language of real closed fields
without parameters. Such a formula also exists for $\Sigma(S,R)$. Indeed, let
$T_{1}={\mathbb{Z}}_{\geq 0}^{n}\cap\operatorname{conv}(S)$ and
$T_{2}={\mathbb{Z}}_{\geq 0}^{n}\cap(\frac{1}{2}\operatorname{conv}(S))$.
Every element of $\Sigma(S,R)$ is a sum of squares of elements of
$\operatorname{P}(T_{2},R)$, i.e., lies in the conical hull of the set

$\\{q^{2}\mid
q\in\operatorname{P}(T_{2},R)\\}\subset\operatorname{P}(T_{1},R).$

Then by Carathéodory’s theorem for the conical hull every such element can be
written as a sum of $|T_{1}|=\dim(\operatorname{P}(T_{1},R))$ many squares.
Therefore, we have that $\Sigma(S,R)$ is the set of all
$p\in\operatorname{P}(S,R)$ for which there exist $c_{i,t}\in R$, for
$i\in\\{1,\dots,|T_{1}|\\}$ and $t\in T_{2}$, such that

$p=\sum_{i=1}^{|T_{1}|}\left(\sum_{t\in
T_{2}}c_{i,t}\prod_{j=1}^{n}x_{j}^{t_{j}}\right)^{2}.$

This shows that $\Sigma(S,R)$ is defined by a formula in the language of real
closed fields without parameters.

######  Remark 3.10.

For all finite sets $S$ the set $\Sigma(S)$ is a spectrahedral shadow [22,
§6.3.1, page 263].

######  Proposition 3.11.

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ be a finite set. Assume that there
exists a real closed field $R$ and $p\in\operatorname{P}_{+}(S,R)$ such that
$p$ is not a sum of squares of elements from $R[{\mathbb{Q}}^{n}]$. Then
$\operatorname{P}_{+}(S)$ is not a spectrahedral shadow.

###### Proof.

Without loss of generality we may assume that $R$ contains ${\mathbb{R}}$. By
3.7 there exists a real closed field extension $R^{\prime}\supset R$ and an
$R^{\prime}$-linear functional $T\colon R^{\prime}[{\mathbb{Q}}^{n}]\to
R^{\prime}$ such that $T(a^{2})>0$ for all $a\in
R^{\prime}[{\mathbb{Q}}^{n}]\setminus\\{0\\}$ and $T(p)<0$. Let
$f\colon{\mathbb{Q}}^{n}\to R^{\prime}$ defined by
$f(w)=T(\epsilon_{1}^{w_{1}}\cdots\epsilon_{n}^{w_{n}})\in R^{\prime}$ for
$w\in{\mathbb{Q}}^{n}$. By the $R^{\prime}$-linearity of $T$ we then have
$T=T_{f}$ as in 2.14. As $T(a^{2})>0$ we have that $f$ is positive definite
(see 2.14). After replacing $T$ by $\frac{1}{T(1)}\cdot T$, we can further
assume that $f(0)=1$. Therefore, we have that $L_{f}\colon
R^{\prime}[[\epsilon^{{\mathbb{Q}}^{n}}]]\to
R^{\prime}[[\epsilon^{{\mathbb{Q}}^{n}}]]$ is completely positive by 2.13,
${\mathbb{R}}$-linear by construction, and unital because $f(0)=1$. The
polynomial $q=p(\epsilon_{1}x_{1},\ldots,\epsilon_{n}x_{n})$ with coefficients
in $R[[\epsilon^{{\mathbb{Q}}^{n}}]]$ is nonnegative on
$R^{\prime}[[\epsilon^{{\mathbb{Q}}^{n}}]]^{n}$. By construction we have

$L_{f}(q)(\epsilon_{1}^{-1},\ldots,\epsilon_{n}^{-1})=T_{f}(p)<0.$

Thus, $L_{f}$ preserves all formulas in $\Gamma$ by 2.3 but not the formula
defining $\operatorname{P}_{+}(S,R^{\prime}[[\epsilon^{{\mathbb{Q}}^{n}}]])$.
This shows that $\operatorname{P}_{+}(S)$ is not a spectrahedral shadow. ∎

A first-order formula is called _positive_ if it is built from atomic formulas
by existential and universal quantification, conjunction, and disjunction.
That is, only negation from first-order logic is forbidden.

######  Proposition 3.12.

Let $S\subset{\mathbb{Z}}^{n}_{\geq 0}$ and $p\in\operatorname{P}_{+}(S,R)$ be
as in 3.11. Then $\operatorname{P}_{+}(S)$ does not have a positive definition
over the relational structure whose relations consist of all spectrahedra and
the inequality relation $\neq$.

###### Proof.

Note that by 2.10 the map $L_{f}\colon
R^{\prime}[[\epsilon^{{\mathbb{Q}}^{n}}]]\to
R^{\prime}[[\epsilon^{{\mathbb{Q}}^{n}}]]$ constructed in the proof of 3.11 is
surjective. It follows from the easy direction of the Lyndon preservation
theorem for positive first-order logic (see, e.g., Corollary 10.3.5 in [13])
and the Tarski principle for real-closed fields (similarly as outlined for
existential positive logic in the introduction) that the convex semi-algebraic
set $\operatorname{P}_{+}(S)$ does not have a definition by a positive formula
over spectrahedra. In fact, the map $L_{f}$ is also injective and hence
preserves $\neq$, and so $\operatorname{P}_{+}(S)$ is inexpressible even if we
additionally allow the use of $\neq$. ∎

######  Remark 3.13.

If full first-order logic is permitted, then the graph of multiplication can
already be defined from fairly restricted sets of relations over the reals
[24, 17] (and in combination with the graph of addition we then obtain all
semialgebraic relations). In particular, it is easy to see that all
semialgebraic relations can be defined with first-order formulas and
parameters from the graph of addition and the spectrahedron defined by $y\geq
x^{2}$.

Let $R$ be a real closed field, $d>0$ an integer, $S\subset{\mathbb{Z}}_{\geq
0}^{n}$ a finite set and $s\in\\{\pm 1\\}^{n}$. We consider the following
isomorphisms of $R$-vector spaces:

$\displaystyle\psi_{d}\colon$
$\displaystyle\operatorname{P}(S,R)\to\operatorname{P}(d\cdot S,R),$
$\displaystyle p(x_{1},\ldots,x_{n})\mapsto p(x_{1}^{d},\ldots,x_{n}^{d}),$
$\displaystyle\varphi_{s}\colon$
$\displaystyle\operatorname{P}(S,R)\to\operatorname{P}(S,R),$ $\displaystyle
p(x_{1},\ldots,x_{n})\mapsto p(s_{1}x_{1},\ldots,s_{n}x_{n}).$

Further, we define

$\Sigma_{d}(S,R)=\bigcap_{s\in\\{\pm
1\\}^{n}}\varphi_{s}(\psi_{d}^{-1}(\Sigma(d\cdot S,R))).$

Again we write $\Sigma_{d}(S)=\Sigma_{d}(S,{\mathbb{R}})$.

######  Lemma 3.14.

The following hold true for all integers $d>0$:

  1. (1)

$\Sigma_{d}(S,R)$ can be defined by a formula in the language of real closed
fields without parameters.

  2. (2)

$\Sigma_{d}(S,R)\subseteq\Sigma_{i\cdot d}(S,R)$ for all integers $i>0$.

  3. (3)

$\Sigma_{d}(S,R)\subseteq\operatorname{P}_{+}(S,R)$.

  4. (4)

$\Sigma_{d}(S)$ is a spectrahedral shadow.

###### Proof.

Part $(1)$ follows from 3.9 and the fact that $\psi_{d}$ and $\varphi_{s}$ are
first-order definable without parameters in the language of real closed
fields. If a polynomial $p$ is a sum of squares, then
$p(x_{1}^{i},\ldots,x_{n}^{i})$ is also a sum of squares. This shows $(2)$.
Let $p\in\Sigma_{d}(S,R)$ and $x_{1},\ldots,x_{n}\in R$. To show $(3)$, we
have to show that $p(x_{1},\ldots,x_{n})\geq 0$. For $i\in\\{1,\dots,n\\}$,
let $s_{i}\in\\{\pm 1\\}$ be such that $s_{i}x_{i}\geq 0$. Then we let
$y_{i}=\sqrt[d]{s_{i}x_{i}}$. We have
$q=\psi_{d}(\varphi_{s}^{{-1}}(p))\in\Sigma(d\cdot
S,R)\subseteq\operatorname{P}_{+}(d\cdot S,R)$. Therefore,

$0\leq
q(y_{1},\ldots,y_{n})=(\varphi_{s}^{{-1}}(p))(s_{1}x_{1},\ldots,s_{n}x_{n})=p(x_{1},\ldots,x_{n}).$

This shows $(3)$. We finally have that $\Sigma_{d}(S)$ is a spectrahedral
shadow as the intersection of finitely many spectrahedral shadows. ∎

######  Theorem 3.15.

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ be a finite set. The following are
equivalent:

  1. (1)

$\operatorname{P}_{+}(S)$ is a spectrahedral shadow.

  2. (2)

For every real closed field $R$ and every polynomial
$p\in\operatorname{P}_{+}(S,R)$, there exists $d>0$ such that
$p(x_{1}^{d},\ldots,x_{n}^{d})$ is a sum of squares.

  3. (3)

There exists $d>0$ such that for every real closed field $R$ and every
polynomial $p\in\operatorname{P}_{+}(S,R)$ the polynomial
$p(x_{1}^{d},\ldots,x_{n}^{d})$ is a sum of squares.

  4. (4)

There exists $d>0$ such that for every polynomial
$p\in\operatorname{P}_{+}(S)$ the polynomial $p(x_{1}^{d},\ldots,x_{n}^{d})$
is a sum of squares.

  5. (5)

$\operatorname{P}_{+}(S)$ has a positive definition over the relational
structure whose relations consist of all spectrahedra and the inequality
relation $\neq$.

###### Proof.

The implication $(1)\Rightarrow(2)$ follows from 3.11 and 3.2. Now assume
$(2)$. We first claim that

$\operatorname{P}_{+}(S,R)=\bigcup_{k=1}^{\infty}\Sigma_{k}(S,R).$

The inclusion $\supseteq$ is 3.14(3). Let $p\in\operatorname{P}_{+}(S,R)$. By
assumption, for all $s\in\\{\pm 1\\}^{n}$ there is $k_{s}>0$ such that
$\psi_{k_{s}}(\varphi_{s}(p))\in\Sigma(k_{s}\cdot S,R)$. Therefore, letting
$k=\prod_{s\in\\{\pm 1\\}^{n}}k_{s}$ we have
$\psi_{k}(\varphi_{s}(p))\in\Sigma(k\cdot S,R)$ and thus
$p\in\Sigma_{k}(S,R)$.

Both $\operatorname{P}_{+}(S,R)$ and each $\Sigma_{k}(S,R)$ can be defined by
a formula without parameters. Thus, letting ${\mathbb{R}}^{*}$ be an
$\aleph_{1}$-saturation of ${\mathbb{R}}$, we have
$\operatorname{P}_{+}(S,{\mathbb{R}}^{*})=\Sigma_{d}(S,{\mathbb{R}}^{*})$ for
some $d>0$ by [27, Theorem 2.2.11]. By the Tarski principle we thus have
$\operatorname{P}_{+}(S,R)=\Sigma_{d}(S,R)$ for every real closed field $R$.
This shows $(3)$.

The direction $(3)\Rightarrow(4)$ is trivial. Finally, assume $(4)$ which
implies $\operatorname{P}_{+}(S)=\Sigma_{d}(S)$. This shows $(1)$ by 3.14(4)
and we have that $(1)$—$(4)$ are equivalent.

It is clear that $(1)$ implies $(5)$ and 3.12 shows that $(5)$ implies $(2)$.
∎

######  Remark 3.16.

3.15 also gives a characterization of when the set of all
$p\in\operatorname{P}(S)$ which are nonnegative on the nonnegative orthant is
a spectrahedral shadow. Indeed, a polynomial $p\in\operatorname{P}(S)$ is
nonnegative on the nonnegative orthant if and only if
$p(x_{1}^{2},\ldots,x_{n}^{2})\in\operatorname{P}_{+}(2S)$.

######  Remark 3.17.

A closed convex cone $K\subseteq{\mathbb{R}}^{n}$ is a spectrahedral shadow if
and only if its dual cone is a spectrahedral shadow (Exercise 6.23 in [22]).
The dual cone of $\operatorname{P}_{+}(S)$ is the closed conical hull of the
image of ${\mathbb{R}}^{n}$ under the monomial map given by the monomials from
$S$.

The following answers Question 5.2 in [31]. For $s\in{\mathbb{Z}}^{n}_{\geq
0}$, we write $|s|$ for $s_{1}+\dots+s_{n}$.

######  Corollary 3.18.

The set of copositive matrices of size $n\geq 5$ is not a spectrahedral
shadow. Moreover, it does not have a positive definition in the relational
structure over the reals whose relations consist of all spectrahedra and the
inequality relation.

###### Proof.

By 3.16 the set of copositive matrices of size $n$ can be identified with the
set of all polynomials $q\in{\mathbb{R}}[x_{1},\ldots,x_{n}]$ that are
homogeneous of degree two such that $q(x_{1}^{2},\ldots,x_{n}^{2})$ is
nonnegative on ${\mathbb{R}}^{n}$. Thus, the set of copositive matrices of
size $n$ is identified with $\operatorname{P}_{+}(2S)$ where
$S=\\{s\in{\mathbb{Z}}_{\geq 0}^{n}\mid|s|=2\\}$. We have seen in 3.4 that the
Horn polynomial $h$ satisfies
$p=h(x_{1}^{2},\ldots,x_{n}^{2})\in\operatorname{P}_{+}(2S)$ but
$p(x_{1}^{d},\ldots,x_{n}^{d})$ is not a sum of squares for every $d>0$. Thus
3.15 implies the claim. ∎

For the rest of this section we summarize the current knowledge on whether
$\operatorname{P}_{+}(S)$ is a spectrahedral shadow for a given finite set
$S\subset{\mathbb{Z}}_{\geq 0}^{n}$.

######  Example 3.19 (Hilbert).

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ a finite set and $\Delta_{\leq d}$ the
set of all $s\in{\mathbb{Z}}_{\geq 0}^{n}$ such that $|s|\leq d$. Hilbert [12]
proved that every element of $\operatorname{P}_{+}(S)$ is a sum of squares if
we are in one of the following cases:

  1. (1)

$S\subseteq\Delta_{\leq 2}$;

  2. (2)

$n=1$;

  3. (3)

$n=2$ and $S\subseteq\Delta_{\leq 4}$.

Thus, in all these cases $\operatorname{P}_{+}(S)$ is a spectrahedral shadow.

######  Example 3.20 (Fawzi, Scheiderer).

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ a finite set which is _downward
closed_ in the sense that if $s^{\prime}\leq s$ (coordinate-wise) and $s\in
S$, then $s^{\prime}\in S$. Then by [8, Theorem 3] the set
$\operatorname{P}_{+}(S)$ is a spectrahedral shadow if and only if
$\operatorname{P}_{+}(S)=\Sigma(S)$. Thus, for every nonnegative polynomial
which is not a sum of squares, letting $S$ be the downward closure of its
support, we obtain an instance where $\operatorname{P}_{+}(S)$ is not a
spectrahedral shadow. Scheiderer [31] used a related criterion in several
examples. A generalization of [8, Theorem 3] to finite dimensional spaces of
polynomials not necessarily spanned by monomials is given in [4, Theorem
2.14].

######  Example 3.21 (SONC).

A finite subset $A\subset{\mathbb{Z}}_{\geq 0}^{n}$ is called _circuit set_ if
its convex hull $\operatorname{conv}(A)\subset{\mathbb{R}}^{n}$ is a
$k$-dimensional simplex whose vertices $v_{0},\ldots,v_{k}$ are in
$2{\mathbb{Z}}_{\geq 0}^{n}$ and
$A\setminus\\{v_{0},\ldots,v_{k}\\}\subseteq\\{w\\}$ for some $w$ in the
relative interior of $\operatorname{conv}(A)$. For any finite
$S\subset{\mathbb{Z}}_{\geq 0}^{n}$ the cone of _sums of nonnegative circuit
polynomials_ is defined as

$\textrm{SONC}(S)=\sum_{A\subseteq S\textrm{ a circuit
set}}\operatorname{P}_{+}(A).$

Averkov [2, §6] showed that $\textrm{SONC}(S)$ has a semidefinite extended
representation with LMIs of size at most two. Without the bound on the LMI
sizes this also follows from a result by Reznick [28, 26] which implies that
for every $p\in\textrm{SONC}(S)$ the polynomial
$p(x_{1}^{d},\ldots,x_{n}^{d})$ is a sum of squares for $d=\max(2,n-1)$. In
particular, we have that $\operatorname{P}_{+}(S)$ is a spectrahedral shadow
whenever $\operatorname{P}_{+}(S)=\textrm{SONC}(S)$. By definition this is the
case if $S$ is a circuit set. Equality is also straightforward to see if every
element of $S$ is a vertex of $\operatorname{conv}(S)$. More cases of equality
can be deduced from [20, Theorem 11] and [9, Theorem 8.1].

The proof of 3.18 shows the existence of a set $S\subset{\mathbb{Z}}^{n}_{\geq
0}$ of size $\frac{1}{2}n(n+1)$, for $n\geq 5$, such that
$\operatorname{P}_{+}(S)$ is not a spectrahedral shadow. For $n=5$ this means
$|S|=15$. Moreover, Scheiderer [31, Remark 4.21] constructs such an
$S\subset{\mathbb{Z}}^{2}_{\geq 0}$ with $|S|=14$. We do not know the smallest
size of a set $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ such that
$\operatorname{P}_{+}(S)$ is not a spectrahedral shadow. The following shows
that any such set must satisfy $|S|>5$.

######  Corollary 3.22.

Let $S\subset{\mathbb{Z}}_{\geq 0}^{n}$ with $|S|\leq 5$. Then
$\operatorname{P}_{+}(S)$ is a spectrahedral shadow.

###### Proof.

Consider the convex hull $K=\operatorname{conv}(S)\subset{\mathbb{R}}^{n}$ and
let $N$ be the number of vertices of $K$. First suppose that $N\leq 2$. Then
there is a finite subset $T\subset{\mathbb{Z}}_{\geq 0}$ and
$v\in{\mathbb{Z}}_{\geq 0}^{n}$, $w\in{\mathbb{Z}}^{n}\setminus\\{0\\}$ such
that $S=\\{v+k\cdot w\mid k\in T\\}$ and such that the entries of $w$ do not
have a nontrivial common divisor. If $\operatorname{P}_{+}(S)\neq\\{0\\}$ we
can further assume that $v\in 2{\mathbb{Z}}_{\geq 0}^{n}$. Then the vector
space isomorphism

$\operatorname{P}(T)\to\operatorname{P}(S),\,p\mapsto\underline{x}^{v}\cdot
p(\underline{x}^{w})$

identifies $\operatorname{P}_{+}(T)$ with $\operatorname{P}_{+}(S)$. Since
every univariate nonnegative polynomial is a sum of squares, the set
$\operatorname{P}_{+}(T)$, and hence $\operatorname{P}_{+}(S)$, is a
spectrahedral shadow.

In the case $N\geq 3$ we claim that
$\operatorname{P}_{+}(S)=\textrm{SONC}(S)$. This implies the claim since
$\textrm{SONC}(S)$ is a spectrahedral shadow by [2, §6], see also 3.21. First
assume that $K$ is a simplex. Since $|S|\leq 5$, there are at most two
elements of $S$ that are not vertices of $K$. Hence
$\operatorname{P}_{+}(S)=\textrm{SONC}(S)$ follows from [20, Theorem 11(1)]
(applied to the trivial partition of $S$). Now assume that $K$ is not a
simplex. We first note that $N\geq 3$ implies that $\dim(K)\geq 2$. Therefore,
since $K$ is not a simplex, we even have $N\geq 4$. Thus there is at most one
element of $S$ that is not a vertex of $K$ and we can apply [20, Theorem
11(2)] (again to the trivial partition). ∎

##  4\. Separating $\Gamma_{k}$ from $\Gamma_{k+1}$

The following criteria for a function $f\colon{\mathbb{R}}\to{\mathbb{R}}$ to
be $k$-positive definite or semidefinite are due to Karlin [15].

######  Lemma 4.1.

For $k\in{\mathbb{Z}}_{>0}$ let $f\in C^{2k-2}({\mathbb{R}})$ and for all
$x\in{\mathbb{R}}$ consider the Hankel matrix
$H_{f}(x)=(f^{(i+j-2)}(x))_{1\leq i,j\leq k}$ of order $k$.

  1. (1)

If $f$ is $k$-positive semidefinite, then $H_{f}(x)$ is positive semidefinite
for every $x\in{\mathbb{R}}$.

  2. (2)

If $H_{f}(x)$ is positive definite for every $x\in{\mathbb{R}}$, then $f$ is
$k$-positive definite.

###### Proof.

Part (1) follows from applying suitable transformations to the matrix

$(f(x_{i}+x_{j}))_{i,j}$

for $x_{1}<\cdots<x_{k}$ and then letting all $x_{i}$ converge to the same
value $x$ as it is done in [15, §2.1]. Part (2) follows from [15, Thm. 2.6]
applied to the kernel $K(x,y)=f(x+y)$. ∎

This criterion allows us to exhibit a function ${\mathbb{R}}\to{\mathbb{R}}$
that is $k$-positive definite, but not $k+1$-positive semidefinite. First we
make some observations on the Hankel matrices $H_{f}(x)$.

######  Remark 4.2.

By definition the Hankel matrix $H_{f}(x)$ is linear in $f$.

For the rest of the section let $0<a_{1}<\cdots<a_{k}$ and
$g(x)=\sum_{m=1}^{k}\exp(a_{m}x)$. Let $\bar{g}(x)=g(-x)$. For any
$\epsilon>0$ consider the function
$f_{\epsilon}\colon{\mathbb{R}}\to{\mathbb{R}}$ given by
$f_{\epsilon}(x)=g(x)+\bar{g}(x)-\epsilon$.

######  Lemma 4.3.

For any $\epsilon>0$ the function $f_{\epsilon}$ is not $(k+1)$-positive
semidefinite.

###### Proof.

Let ${p}_{m}(x)=\exp(a_{m}x)$ for $m\in\\{1,\ldots,k\\}$. The Hankel matrix
$H_{{p}_{m}}(x)$ of order $k+1$ equals the rank one matrix

$\exp(a_{m}x)\cdot v_{m}^{\top}\cdot v_{m}$

where $v_{m}=(1,a_{m},\ldots,a_{m}^{k})$ for $m\in\\{1,\ldots,k\\}$. Let
$w\in{\mathbb{R}}^{k+1}$ be a nonzero vector in the orthogonal complement of
the subspace spanned by $v_{1},\ldots,v_{k}$. We claim that $w^{\top}$ is in
the kernel of $H_{g}(x)$ for all $x\in{\mathbb{R}}$. Indeed, we have for all
$x\in{\mathbb{R}}$ that

$H_{g}(x)\cdot w^{\top}=\sum_{m=1}^{k}H_{{p}_{m}}(x)\cdot
w^{\top}=\sum_{m=1}^{k}\exp(a_{m}x)\cdot
v_{m}^{\top}\cdot\underbrace{v_{m}\cdot w^{\top}}_{=0}=0.$

Further, we claim that the first component of $w$ is nonzero. Indeed, assume
otherwise and let $w^{\prime}\in{\mathbb{R}}^{k}$ be such that
$w=(0,w^{\prime})$. Then $w^{\prime}$ is in the orthogonal complement of the
vectors

$(a_{1},\ldots,a_{1}^{k}),\ldots,(a_{k},\ldots,a_{k}^{k}).$

However, these vectors are linearly independent because $a_{1},\dots,a_{k}$
are pairwise different and nonzero. This is a contradiction to our assumption
that $w$ and thus $w^{\prime}$ is nonzero. Therefore, we have shown that the
first component of $w$ is nonzero. Without loss of generality, we may assume
that it equals $1$. For $m\in\\{1,\ldots,k\\}$ let $b_{m}=-a_{m}$ and
$u_{m}=(1,b_{m},\ldots,b_{m}^{k})$. Then, as above, we compute

$wH_{\bar{g}}(x)w^{\top}=\sum_{m=1}^{k}\exp(-a_{m}x)\cdot\langle
u_{m},w\rangle^{2}$

which tends to zero for $x\to\infty$ because $a_{1},\dots,a_{k}$ are positive.
Let $x_{0}\in{\mathbb{R}}$ be such that $wH_{\bar{g}}(x)w^{\top}<\epsilon$ for
all $x>x_{0}$. Then we have for all $x>x_{0}$ that

$wH_{f_{\epsilon}}w^{\top}=wH_{\bar{g}}w^{\top}-\epsilon<0.$

By 4.1 this proves the claim. ∎

######  Lemma 4.4.

For sufficiently small $\epsilon>0$ the function $f_{\epsilon}$ is
$k$-positive definite.

###### Proof.

Let $H_{g}(x)$ and $H_{\bar{g}}(x)$ be Hankel matrices of order $k$. They are
positive linear combinations of positive semidefinite rank one matrices so
they are positive semidefinite for all $x\in{\mathbb{R}}$. We can write
$H_{g}(x)=A+B(x)$ where $A=\sum_{m=1}^{k}v_{m}^{\top}\cdot v_{m}$,
$B(x)=\sum_{m=1}^{k}(\exp(a_{m}x)-1)\cdot v_{m}^{\top}\cdot v_{m}$ and
$v_{m}=(1,a_{m},\ldots,a_{m}^{k-1})$. Similarly, we can write
$H_{\bar{g}}(x)=A^{\prime}+B^{\prime}(-x)$ where
$A^{\prime}=\sum_{m=1}^{k}u_{m}^{\top}\cdot u_{m}$,
$B^{\prime}(x)=\sum_{m=1}^{k}(\exp(-a_{m}x)-1)\cdot u_{m}^{\top}\cdot u_{m}$
and $u_{m}=(1,-a_{m},\ldots,(-a_{m})^{k-1})$. We note that when $x\geq 0$ we
have that $B(x)$ is positive semidefinite because $\exp(a_{m}x)\geq 1$ for
$x\geq 0$ and similarly $B^{\prime}(-x)$ is positive semidefinite when $x\leq
0$. In any case, $A$ and $A^{\prime}$ are positive definite since the vectors
$v_{1},\ldots,v_{k}$ resp. $u_{1},\ldots,u_{k}$ are linearly independent.
Thus, it suffices to choose $\epsilon>0$ in such a way that both
$A-\epsilon\cdot\delta_{1}\cdot\delta_{1}^{\top}$ and
$A^{\prime}-\epsilon\cdot\delta_{1}\cdot\delta_{1}^{\top}$ are positive
definite, where $\delta_{1}$ is the first unit vector, since
$\epsilon\cdot\delta_{1}\cdot\delta_{1}^{\top}$ is the Hankel matrix of the
constant function $\epsilon$. Indeed, for $x\geq 0$ we have that

$H_{f_{\epsilon}}(x)=(A-\epsilon\cdot\delta_{1}\cdot\delta_{1}^{\top})+B(x)+H_{\bar{g}}(x)$

is positive semidefinite. Similarly, for $x\leq 0$, we have that

$H_{f_{\epsilon}}(x)=(A^{\prime}-\epsilon\cdot\delta_{1}\cdot\delta_{1}^{\top})+B^{\prime}(-x)+H_{{g}}(x)$

is positive semidefinite. ∎

######  Corollary 4.5.

For every $k\in{\mathbb{Z}}_{\geq 0}$ there is a function
${\mathbb{R}}\to{\mathbb{R}}$ that is $k$-positive definite but not
$k+1$-positive semidefinite.

###### Proof.

For sufficiently small $\epsilon>0$ the function $f_{\epsilon}$ has the
desired properties. ∎

######  Example 4.6.

Let $k=2$ and $0<a_{1}<a_{2}$. Then

$f_{\epsilon}(x)=\exp(a_{1}x)+\exp(a_{2}x)+\exp(-a_{1}x)+\exp(-a_{2}x)-\epsilon.$

For $x\geq 0$ resp. $x\leq 0$ the Hankel matrix $H_{f}(x)$ is of the form

${\underbrace{\begin{pmatrix}2&\pm(a_{1}+a_{2})\\\
\pm(a_{1}+a_{2})&a_{1}^{2}+a_{2}^{2}\end{pmatrix}}_{=A\textnormal{ resp.
}A^{\prime}\textnormal{ in the proof of \ref{lem:exh2}
}}+\begin{pmatrix}-\epsilon&0\\\ 0&0\end{pmatrix}+C}(x)$

where ${C}(x)$ is positive semidefinite. For instance letting $a_{1}=\ln(2)$,
$a_{2}=\ln(3)$, and $\epsilon=\frac{1}{11}$ makes $H_{f_{\frac{1}{11}}}(x)$
positive definite for all $x\in{\mathbb{R}}$. Indeed, in this case we have

$\det\begin{pmatrix}2-\epsilon&\pm(a_{1}+a_{2})\\\
\pm(a_{1}+a_{2})&a_{1}^{2}+a_{2}^{2}\end{pmatrix}=\frac{21}{11}\cdot(\ln(2)^{2}+\ln(3)^{2})-(\ln(2)+\ln(3))^{2}\approx
0.011>0.$

Thus, $f_{\frac{1}{11}}$ is $2$-positive definite. However, the matrix
$(f_{\frac{1}{11}}(x_{i}+x_{j}))_{1\leq i,j\leq 3}$ for
$x_{1}=5,x_{2}=6,x_{3}=7$ equals

$\begin{pmatrix}\frac{39956170693955}{665127936}&\frac{715125242123209}{3990767616}&\frac{12823220129727323}{23944605696}\\\
&&&\\\
\frac{715125242123209}{3990767616}&\frac{12823220129727323}{23944605696}&\frac{230229525738486289}{143667634176}\\\
&&&\\\
\frac{12823220129727323}{23944605696}&\frac{230229525738486289}{143667634176}&\frac{4137070068201557555}{862005805056}\end{pmatrix}.$

Its determinant is

$-\frac{2277541160576348197}{107750725632}<0$

and thus the matrix is not positive semidefinite. Therefore,
$f_{\frac{1}{11}}$ is not 3-positive semidefinite.

In order to apply 2.13 consider the real closed field
$H={\mathbb{R}}[[\epsilon^{\mathbb{R}}]]$ of Hahn series over ${\mathbb{R}}$
in the (infinitesimal) indeterminate $\epsilon$ and with value group
${\mathbb{R}}$.

######  Corollary 4.7 (Cor. 2.5 in [2]).

The cone $K$ of $k\times k$ real symmetric positive semidefinite matrices has
no semidefinite extended formulation with LMIs of size less than $k$.

###### Proof.

By 4.5 there exists a function $f\colon{\mathbb{R}}\to{\mathbb{R}}$ that is
$(k-1)$-positive definite but not $k$-positive semidefinite. By 2.12 we can
assume without loss of generality that $f(0)=1$. Then $L_{f}\colon H\to H$
does not preserve $K$ by 2.13(2). But $L_{f}$ preserves all spectrahedra of
size $k-1$ by 2.3, and hence it preserves all sets that have an semidefinite
extended formulation with LMIs of size at most $k-1$. This shows that $K$ does
not have such a formulation. ∎

In the same way as in the proof of 3.12 we even obtain the following stronger
statement.

######  Corollary 4.8.

The cone K of $k\times k$ real symmetric positive semidefinite matrices does
not have a positive definition over the relational structure whose relations
consist of all sets that can be described by an LMI of size less than $k$ and
the inequality relation $\neq$.

##  Appendix A Real closed separation

We follow the line of arguments from [21]. We start with a lemma that is well-
known which we include for the sake of completeness.

######  Lemma A.1.

Let $R$ be a real closed field and $I$ some finite index set. Let
$V_{1},V_{2}$ be finite-dimensional $R$-vector spaces. Let $\alpha_{i}\colon
V_{1}\to V_{2}$, $i\in I$, be some homogeneous polynomial maps with the
property that no non-trivial positive linear combination of images of the
$\alpha_{i}$ is trivial, meaning that

$\sum_{j=1}^{r}\lambda_{j}\alpha_{i_{j}}(v_{j})=0$

for $r\in{\mathbb{N}}$, $i_{j}\in I$ and $\lambda_{j}>0$ implies that all
$v_{j}\in V_{i_{j}}$ are zero. Then

$C:={\rm conv}({\cup_{i\in I}\alpha_{i}(V_{1})})$

is a closed convex cone. Moreover, if $b\not\in C$, then there exists an
$R$-linear map $\phi\colon V_{2}\to R$, such that $\phi(c)\geq 0$ for $c\in C$
and $\phi(b)<0$.

###### Proof.

After choosing bases we can assume that $V_{1}=R^{d}$ and $V_{2}=R^{n}$. Let

$S=\\{v\in R^{d}\mid||v||_{2}=1\\}$

the unit sphere with respect to the euclidean norm. Since each $\alpha_{i}$ is
homogeneous, we have that $C$ is the conical hull of $\cup_{i\in
I}\alpha_{i}(S)$. In particular, it is a convex cone. Thus it remains to prove
that $C$ is closed. Let $m=|I|$. We consider the map

$\Phi:S^{m\cdot n}\times\Delta_{m\cdot n}\to
R^{n},\,(v_{11},\ldots,v_{mn},\lambda_{11},\ldots,\lambda_{mn})\mapsto\sum_{j=1}^{n}\sum_{i=1}^{m}\lambda_{ij}\alpha_{i}(v_{ij})$

where $\Delta_{mn}\subset R^{mn}$ is the standard simplex. The image $B\subset
R^{n}$ of $\Phi$ is semialgebraically compact as the image of a
semialgebraically compact set under a continuous semialgebraic map. We claim
that

$\Sigma=\\{(v,b)\in R^{n}\times B\mid\exists\lambda\geq 0:v=\lambda\cdot b\\}$

is a closed subset of $R^{n}\times B$. Indeed, it can be written as

$\Sigma=\\{(v,b)\in R^{n}\times B\mid\forall
i,j:(v_{i}b_{j}=v_{j}b_{i})\wedge(v_{i}b_{i}\geq 0)\\}$

since $0\not\in B$ by assumption. Since $B$ is semialgebraically compact, the
projection of $\Sigma$ onto the first coordinate, which equals to $C$ by
Carathéodory’s theorem for the conical hull, is closed as well. Now the
conical separation theorem implies the additional statement. ∎

Let $R$ be a real closed field and $A$ a commutative $R$-algebra. For
$g_{1},\ldots,g_{r}\in A$ we denote

${\rm U}_{A}(g_{1},\ldots,g_{r})=\\{\alpha\in\operatorname{Sper}(A)\mid
g_{1}(\alpha)>0,\ldots,g_{r}(\alpha)>0\\}$

where $\operatorname{Sper}(A)$ is the _real spectrum_ of $A$, see for example
[5, §7]. We further consider the _quadratic module_ ${\rm
QM}_{A}(g_{1},\ldots,g_{r})$, i.e., the set of all

$s_{0}+s_{1}g_{1}+\cdots+s_{r}g_{r}\in A$

where the $s_{i}\in A$ are sum of squares. We say that $A$ is _real reduced_
if $\sum_{i=1}^{k}a_{i}^{2}=0$ implies $a_{1}=\cdots=a_{k}=0$ for all
$k\in\mathbb{N}$.

######  Theorem A.2.

Let $R$ be a real closed field and let $A$ a real reduced commutative
$R$-algebra. Let $b,g_{1},\ldots,g_{r}\in A$ be such that the following holds:

  1. (1)

$b\not\in{\rm QM}_{A}(g_{1},\ldots,g_{r})$,

  2. (2)

${\rm U}_{A}(g_{1},\ldots,g_{r})$ is Zariski dense in
$\operatorname{Sper}(A)$.

Then there exists a real closed field $R^{\prime}$ containing $R$ and an
$R^{\prime}$-linear map

$\phi\colon A^{\prime}=R^{\prime}\otimes_{R}A\to R^{\prime}$

such that $\phi(1\otimes b)<0$ and $\phi(c)\geq 0$ for all $c\in{\rm
QM}_{A^{\prime}}(g_{1},\ldots,g_{r})$.

###### Proof.

Since $A$ is real reduced, we have that $\operatorname{Sper}(A)\neq\emptyset$.
If $g_{i}=0$ for some $i\in\\{1,\dots,r\\}$, then ${\rm
U}_{A}(g_{1},\ldots,g_{r})=\emptyset$ contradicting our second assumption.
Therefore, all the $g_{i}$ are nonzero. In order to simplify notation we
further let $g_{0}=1$. Let $H$ be a finite-dimensional $R$-subspace of $A$
containing $b,g_{0},\ldots,g_{r}$. Consider the set

$C(H):=\left\\{\sum_{i=0}^{r}g_{i}\cdot\sum_{j=1}^{k_{i}}a_{ij}^{2}\mid
k_{i}\in\mathbb{N},a_{ij}\in H\right\\}.$

Note that $C(H)$ is a convex cone inside the finite-dimensional subspace
$H^{(2)}:={\rm span}_{R}\\{g_{i}a_{1}a_{2}\in A\mid a_{1},a_{2}\in H,\,0\leq
i\leq r\\}$ and $b\in H^{(2)}$ but $b\not\in C(H).$ Since $A$ is real-reduced
and by condition $(2)$, we can apply A.1 to the maps

$\alpha_{i}:H\to H^{(2)},\,a\mapsto a^{2}\cdot g_{i}.$

Therefore, there exists an $R$-linear map $\phi_{H}\colon H^{(2)}\to R$ such
that $\phi_{H}(c)\geq 0$ for all $c\in C(H)$ and $\phi_{H}(b)<0$. Let
$\phi^{\prime}_{H}\colon A\to R$ be an arbitrary linear extension of
$\phi_{H}$ to $A$. Consider an ultrafilter $\mathcal{U}$ on the set of finite-
dimensional subspaces of $A$, containing the filter generated by sets of the
form $S_{H}:=\\{H^{\prime}\mid H\subset H^{\prime}\\}$ for $H$ a finite-
dimensional subspace, and consider the ultra-product
$R^{\prime}:=\prod{}^{\mathcal{U}}R$ which is again a real closed field. There
is a natural $R$-linear map $\phi^{\prime}\colon A\to R^{\prime}$ induced by
all $\phi^{\prime}_{H}$ for $H$ as above. Consider the $R^{\prime}$-linear map

$\phi:=1_{R^{\prime}}\otimes_{R}\phi^{\prime}\colon R^{\prime}\otimes_{R}A\to
R^{\prime}.$

It is clear by construction that $\phi(1\otimes b)<0$. We claim that $\phi$ is
nonnegative on ${\rm QM}_{A^{\prime}}(g_{1},\ldots,g_{r})$. It suffices to
show that $\phi$ is nonnegative on elements of the form $a^{2}g_{k}$ for $a\in
R^{\prime}\otimes_{R}A$ and $0\leq k\leq r$. We write
$a=\sum_{j=1}^{l}x_{j}\otimes y_{j}$ with $x_{j}\in R^{\prime}$ and $y_{j}\in
A.$ Let $H$ be a finite-dimensional subspace of $A$ containing
$b,g_{0},\ldots,g_{r}$ and $y_{1},\dots,y_{l}$. Consider the matrix

$(\phi(1\otimes
g_{k}y_{i}y_{j}))_{i,j=1}^{{l}}=(\phi^{\prime}(g_{k}y_{i}y_{j}))_{i,j=1}^{{l}}\in
M_{{l}}(R^{\prime}).$

For $x=(x_{1},\dots,x_{l})\in R^{\prime l}$ and
$y:=(g_{k}y_{i}y_{j})_{i,j=1}^{l}$ we get
$\phi(a^{2}g_{k})=x\phi^{\prime}(y)x^{\top}$, so that it is sufficient to show
that $\phi_{H}(y)\in M_{{l}}(R)$ is positive semi-definite for all such $H$.
However, this is clear since for $x^{\prime}\in R^{l}$, we have

$x^{\prime}\phi_{H}(y)x^{\prime\top}=\phi_{H}((x^{\prime}_{1}y_{1}+\cdots+x^{\prime}_{l}y_{l})^{2}\cdot
g_{k})\geq 0$

by construction. This finishes the proof. ∎

######  Corollary A.3.

Let $R$ be a real closed field and let $A$ a real reduced commutative
$R$-algebra. Let $b\in A$ not a sum of squares. Then there exists a real
closed field $R^{\prime}$ containing $R$ and an $R^{\prime}$-linear map

$\phi\colon R^{\prime}\otimes_{R}A\to R^{\prime}$

which is nonnegative on sums of squares such that $\phi(1\otimes b)<0$.

######  Remark A.4.

Let $X\subset R^{n}$ be some algebraic set and $A=R[X]$ its coordinate ring,
i.e., the ring of all polynomial functions $X\to R$. Then $A$ is real reduced
and the second condition of A.2 is equivalent to the geometric condition that

$\\{a\in X\mid g_{1}(a)>0,\ldots,g_{r}(a)>0\\}$

is Zariski dense in $X$.

##  Appendix B Preservation Theorems

The approach to study definable sets via structure-preserving maps can be used
to obtain exact characterisations of existential positive, positive, and
first-order definability. There are various formulations of such preservation
theorems. Our formulation in Theorem B.1 (in Section B.2) is closest to the
setting of this article and we have been unable to find it in the literature,
but it should be considered to be known.

###  B.1. Basic Terminology

A _signature_ $\tau$ is a set of _function symbols_ and _relation symbols_.
Each symbol is equipped with an arity $k\in{\mathbb{N}}$. A _$\tau$
-structure_ $\mathfrak{A}$ consists of a set $A$ (the _domain_) and

  * •

for each function symbol $f\in\tau$ of arity $k$ an operation
$f^{\mathfrak{A}}\colon A^{k}\to A$, and

  * •

for each relation symbol $R\in\tau$ of arity $k$ a relation $R\subseteq
A^{k}$.

Note that the arity might in particular be $0$; function symbols of arity $0$
are also called _constants_. We denote structures by $\mathfrak{A}$,
$\mathfrak{B}$, $\mathfrak{C}$, and so on, and the corresponding underlying
sets by the corresponding roman letters $A$, $B$, $C$, and so on. If
$\mathfrak{A}$ and $\mathfrak{B}$ are structures with the same domain and
$\mathfrak{A}$ is obtained from $\mathfrak{B}$ by dropping some of the
relations and operations, then $\mathfrak{A}$ is called a _reduct_ of
$\mathfrak{B}$, and $\mathfrak{B}$ is called an _expansion_ of $\mathfrak{A}$.

In the usual way we define _$\tau$ -terms_ inductively; constant symbols from
$\tau$ are $\tau$-terms, variables are $\tau$-terms, and a function symbol of
arity $k$ applied to a sequence of $\tau$-terms of length $k$ is a
$\tau$-term. If $t$ is a $\tau$-term, we write $t(x_{1},\dots,x_{n})$ if all
the variables that appear in $t$ are from $x_{1},\dots,x_{n}$. An _atomic
$\tau$-formula_ is an expression of the form

  * •

$\bot$ (which stands for _false_), or

  * •

$t_{1}=t_{2}$ where $t_{1}$ and $t_{2}$ are $\tau$-terms, or

  * •

$R(t_{1},\dots,t_{k})$ where $R\in\tau$ is a relation symbol of arity $k$ and
$t_{1},\dots,t_{k}$ are $\tau$-terms.

A _first-order $\tau$-formula_ is built from atomic $\tau$-formulas in the
usual inductive manner, using conjunction $\wedge$, disjunction $\vee$,
negation $\neg$, universal quantification $\forall$, and existential
quantification $\exists$. If $\phi$ is a first-order formula, we write
$\phi(x_{1},\dots,x_{n})$ if all the variables that appear _free_ in $\phi$
(i.e., that are not bound by a universal or existential quantifier; for formal
details, see [13]) are from $x_{1},\dots,x_{n}$. Formulas without free
variables are called _sentences_. If $\phi(x_{1},\dots,x_{k})$ is a
$\tau$-formula and $a_{1},\dots,a_{k}\in A$ we define
$\mathfrak{A}\models\phi(a_{1},\dots,a_{n})$ if $(a_{1},\dots,a_{k})$
_satisfies_ $\phi$ in $\mathfrak{A}$ (see [13] for a precise definition). A
$\tau$-formula $\phi(x_{1},\dots,x_{k})$ defines over $\mathfrak{A}$ a
relation $R\subseteq A^{k}$, namely

$\big{\\{}(a_{1},\dots,a_{k})\in
A^{k}\mid\mathfrak{A}\models\phi(a_{1},\dots,a_{k})\big{\\}}.$

An $\tau$-formula $\phi(x_{1},\dots,x_{k})$ defines over $\mathfrak{A}$ an
operation $f\colon A^{k-1}\to A$ if $\phi$ defines over $\mathfrak{A}$ the
_graph_ of $f$, i.e., the relation

$\\{(a_{1},\dots,a_{k})\in A^{k}\mid f(a_{1},\dots,a_{k-1})=a_{k}\\}.$

We say that $\mathfrak{A}$ is a _first-order reduct_ of $\mathfrak{B}$ if
$\mathfrak{A}$ is a reduct of an expansion of $\mathfrak{B}$ by relations and
operations that are first-order definable in $\mathfrak{B}$.

###  B.2. Preservation Theorems

A first-order formula is called _existential positive_ if it is built without
negation and universal quantification. Note that every existential positive
formula is equivalent to a disjunction of _primitive positive formulas_ ,
i.e., formulas of the form

$\exists x_{1},\dots,x_{k}(\psi_{1}\wedge\dots\wedge\psi_{m})$

where $\psi_{1},\dots,\psi_{m}$ are atomic formulas.

######  Theorem B.1.

Let $\mathfrak{A}$ be a structure. Then $\mathfrak{A}$ has an elementary
extension $\mathfrak{A}^{*}$ such that the following holds. If $\mathfrak{B}$
is a first-order reduct of $\mathfrak{A}$ and $K\subseteq A^{k}$ is first-
order definable over $\mathfrak{A}$, then

  * •

$K$ has an existential positive definition in $\mathfrak{B}$ if and only if
$K^{*}$ is preserved by all endomorphisms of $\mathfrak{B}^{*}$;

  * •

$K$ has a positive definition in $\mathfrak{B}$ if and only if $K^{*}$ is
preserved by all surjective endomorphisms of $\mathfrak{B}^{*}$;

  * •

$K$ has a first-order definition in $\mathfrak{B}$ if and only if $K^{*}$ is
preserved by all automorphisms of $\mathfrak{B}^{*}$.

Here, $\mathfrak{B}^{*}$ is the first-order reduct of $\mathfrak{A}^{*}$
defined by the same formulas as the first-order reduct $\mathfrak{B}$ of
$\mathfrak{A}$, and $K^{*}$ is the relation defined over $\mathfrak{A}^{*}$ by
the same first-order formula that defines $K$ over $\mathfrak{A}$.

We prove Theorem B.1 in Section B.4.

######  Remark B.2.

In our setting, the real-closed field ${\mathbb{R}}$ plays the role of
$\mathfrak{A}$. For the results in Section 3 we then work with the first-order
reduct $\mathfrak{B}$ of $\mathfrak{A}$ that contains all spectrahedra as
relations, to show that specific relations $K$ with a first-order definition
in $\mathfrak{A}$ do not have a positive definition in $\mathfrak{B}$. In
Section 4 we work with the first-order reduct $\mathfrak{B}$ of $\mathfrak{A}$
that contains all relations that are defined by LMIs of size $k$ to show that
some specific relations $K$ with a first-order definition in $\mathfrak{A}$ do
not have a positive definition in $\mathfrak{B}$. In both settings, Lemma 2.3
is a statement about the endomorphisms of $\mathfrak{B}^{*}$.

The elementary extension $\mathfrak{A}^{*}$ of $\mathfrak{A}$ in B.1 will be a
so-called _special model_ (see, e.g., [13]). In the context of preservation
theorems often _saturated structures_ are used. Special structures are more
technical to define than saturated structures. However, the existence of
saturated structures requires the generalised continuum hypothesis which we
would like to avoid.

###  B.3. Saturated and Special Structures

For $n\geq 0$, an _$n$ -type_ of a theory $T$ is a set $p$ of formulas with
free variables $x_{1},\dots,x_{n}$ such that $p\cup T$ is satisfiable. An _$n$
-type over a structure $\mathfrak{A}$_ is an $n$-type of the first-order
theory of ${\mathfrak{A}}$; note that we do not admit parameters in these
formulas (i.e., we allow constants to appear in the formulas of the type only
if they belong to the signature). An $n$-type $p$ of $\mathfrak{A}$ is
_realised_ in $\mathfrak{A}$ if there exist $a_{1},\ldots,a_{n}\in A$ such
that $\mathfrak{A}\models\phi(a_{1},\ldots,a_{n})$ for each $\phi\in p$. For
an infinite cardinal $\kappa$, a structure $\mathfrak{A}$ is _$\kappa$
-saturated_ if, for all $\beta<\kappa$ and expansions $\mathfrak{A}^{\prime}$
of $\mathfrak{A}$ by at most $\beta$ constants, every $1$-type of
$\mathfrak{A}^{\prime}$ is realised in $\mathfrak{A}^{\prime}$. We say that an
infinite structure $\mathfrak{A}$ is _saturated_ if it is $|A|$-saturated. If
$\lambda$ is a cardinal, then $\lambda^{+}$ denotes the successor cardinal of
$\lambda$.

######  Theorem B.3 (Theorem 4.3.12 in [16]).

Let $\tau$ be a signature and $\lambda\geq|\tau|$. Then every $\tau$-structure
$\mathfrak{B}$ has a $\lambda^{+}$-saturated elementary extension of
cardinality $\leq|B|^{\lambda}$.

So if we assume the Generalised Continuum Hypothesis, then there are saturated
models of size $\kappa^{+}$ for all cardinals $\kappa$ (Corollary 10.2.4 in
[13]).

######  Definition B.4.

A structure $\mathfrak{A}$ of cardinality $\kappa\geq\omega$ is _special_ if
$\mathfrak{A}$ is the union of an elementary chain
$(\mathfrak{B}_{\lambda})_{\lambda<\kappa}$ and each $\mathfrak{B}_{\lambda}$
is $\lambda^{+}$-saturated.

Saturated structures are special, because we can write a saturated structure
$\mathfrak{A}$ of cardinality $\kappa$ as
$(\mathfrak{B}_{\lambda})_{\lambda<\kappa}$ where
$\mathfrak{B}_{\lambda}=\mathfrak{A}$; since $\mathfrak{A}$ is
$\lambda^{+}$-saturated for all $\lambda<\kappa$, this proves that
$\mathfrak{A}$ is special. The converse is not true; see [13, Exercises 6 to 8
on page 514]. The advantage of special structures is that they always exist,
independently from set-theoretic assumptions.

######  Theorem B.5 (Theorem 10.4.2. in [13]).

Every infinite structure has a special elementary extension.

###  B.4. Proof of the Preservation Theorems

The following is at the heart of the proof of B.1.

######  Theorem B.6.

Let $\mathfrak{A}$ and $\mathfrak{B}$ be special structures of the same
signature and cardinality.

  * •

If every first-order sentence that is true in $\mathfrak{A}$ is true in
$\mathfrak{B}$, then there exists an isomorphism between $\mathfrak{A}$ and
$\mathfrak{B}$.

  * •

If every positive sentence that is true in $\mathfrak{A}$ is true in
$\mathfrak{B}$, then there exists a surjective homomorphism from
$\mathfrak{A}$ to $\mathfrak{B}$.

  * •

If every existential positive sentence that is true in $\mathfrak{A}$ is true
in $\mathfrak{B}$, then there exists a homomorphism from $\mathfrak{A}$ to
$\mathfrak{B}$.

###### Proof.

The first statement can be shown by a back and forth argument, and is Theorem
10.4.4. in [13]. The other two statements can be shown analogously. ∎

######  Lemma B.7 (see Theorem 10.4.5. in [13]).

First-order reducts of special structures are special.

###### Proof of B.1.

In each of the three statements, the forward direction is immediate, since
homomorphisms preserve existential positive formulas, surjective homomorphisms
preserve positive formulas, and automorphisms preserve first-order formulas.
Moreover, if $K$ has a certain definition in $\mathfrak{B}$, then $K^{*}$ has
the corresponding definition in $\mathfrak{B}^{*}$ since all the involved
structures and sets are first-order definable in $\mathfrak{A}$ and
$\mathfrak{A}^{*}$, respectively, and $\mathfrak{A}$ and $\mathfrak{A}^{*}$
have the same first-order theory.

The three statements are well-known if $\mathfrak{A}$ is finite (see, e.g.,
[25]) so let us assume that $\mathfrak{A}$ is infinite. Let $\mathfrak{A}^{*}$
be a special elementary extension of $\mathfrak{A}$ which exists by B.5, and
let $S$ be the first-order theory of $\mathfrak{A}$ (and $\mathfrak{A}^{*}$).
Let $\mathfrak{B}$ be a first-order reduct of $\mathfrak{A}$ with signature
$\tau$ and let $K\subseteq A^{k}$ be first-order definable over
$\mathfrak{A}$. Let $\mathfrak{B}^{*}$ be the reduct of $\mathfrak{A}^{*}$ and
$K^{*}\subseteq(A^{*})^{k}$ be as in the statement of the theorem. By B.7 we
have that $\mathfrak{B}^{*}$ is special as well.

To show the converse of the first statement, suppose that $K^{*}$ is preserved
by all endomorphisms of $\mathfrak{B}^{*}$. Let $\Psi$ be the set of all
existential positive $\tau$-formulas $\psi(x_{1},\dots,x_{k})$ that hold on
all tuples from $K^{*}$ in $\mathfrak{B}^{*}$. Let $\underline{a}$ be a tuple
satisfying $\Psi$ in $\mathfrak{B}^{*}$. Note that if there is no such tuple,
then $\phi$ must be unsatisfiable in $\mathfrak{B}$. In this case, $\phi$ is
equivalent to the existential positive formula $\bot$ and we are done.

Let $U$ be the set of all primitive positive $\tau$-formulas
$\theta(\underline{x})$ such that
$\mathfrak{B}^{*}\models\neg\theta(\bar{a})$. For any first-order
$\tau$-formula $\eta$ let $T(\eta)$ be the first-order formula obtained from
$\eta$ by replacing each atomic subformula of $\eta$ by its first-order
definition over $\mathfrak{A}^{*}$. We claim that

$S\cup\\{T(\neg\theta)\mid\theta\in U\\}\cup\\{\phi\\}$

is satisfiable. Otherwise, by the compactness theorem of first-order logic
there would be a finite subset $V$ of $U$ such that
$S\cup\\{T(\neg\theta)\mid\theta\in V\\}\cup\\{\phi\\}$ is unsatisfiable.
Since $\neg T(\theta)=T(\neg\theta)$ we get that $S\cup\\{\phi\\}$ implies
$\bigvee_{\theta\in V}T(\theta)$. Thus, $\psi:=\bigvee_{\theta\in V}\theta$ is
an existential positive formula such that $S\cup\\{\phi\\}\models T(\psi)$.
But then $\psi\in\Psi$ and $\mathfrak{B}^{*}\models\psi(\underline{a})$. This
is in contradiction to the assumption that
$\mathfrak{B}^{*}\models\neg\theta(\underline{a})$ for all $\theta\in U$.

Since $\mathfrak{A}^{*}$ is a special model of $S$, the $n$-type
$\\{T(\neg\theta(\bar{x}))\mid\theta\in U\\}\cup\\{\phi(\bar{x})\\}$ is
realised by some $b\in(A^{*})^{k}$ in $\mathfrak{A}^{*}$. Let
$c_{1},\dots,c_{k}$ be new constant symbols and let $\mathfrak{C}$ be the
$\tau\cup\\{c_{1},\dots,c_{k}\\}$-expansion of $\mathfrak{B}^{*}$ where
$\underline{c}^{\mathfrak{C}}=\underline{b}$. Let $\mathfrak{D}$ be the
$\tau\cup\\{c_{1},\dots,c_{k}\\}$-expansion of $\mathfrak{B}^{*}$ where
$\underline{c}^{\mathfrak{C}}=\underline{a}$. Clearly, $\mathfrak{C}$ and
$\mathfrak{D}$ are special as well. Every primitive positive
$(\tau\cup\\{c_{1},\dots,c_{k}\\})$-sentence $\theta$ that is true in
$\mathfrak{D}$ is also true in $\mathfrak{C}$: otherwise, if $\theta$ were
false in $\mathfrak{C}$, then write $\theta$ as $\theta(\underline{c})$ for
$\theta\in U$, in contradiction to the assumption that
$\mathfrak{D}\models\\{\neg\theta(\underline{c})\;|\;\theta\in U\\}$. Hence,
since $\mathfrak{C}$ is special and by B.6, there exists a homomorphism from
$\mathfrak{D}$ to $\mathfrak{C}$. This homomorphism maps $\underline{b}$ to
$\underline{a}$. Since $\underline{b}$ satisfies $\phi$ in $\mathfrak{A}^{*}$
we have that $\underline{b}\in K^{*}$, and since $K^{*}$ is preserved by
endomorphisms of $\mathfrak{B}^{*}$, we have $\underline{a}\in K^{*}$. We
conclude that $S\cup\\{T(\theta)\mid\theta\in\Psi\\}\cup\\{\neg\phi\\}$ is
unsatisfiable, and again by compactness there exists a finite subset
$\Psi^{\prime}$ of $\Psi$ such that
$S\cup\\{T(\theta)\mid\theta\in\Psi^{\prime}\\}\cup\\{\neg\phi\\}$ is
unsatisfiable. Note that $\psi:=\bigwedge\Psi^{\prime}$ is an existential
positive formula and
$S\models\forall\underline{x}(T(\psi)\Leftrightarrow\phi)$ which is what we
wanted to show.

The converse directions for statement two and three of the theorem can be
shown analogously. ∎

## References

  * [1] Norman L. Alling.  Foundations of Analysis over Surreal Number Fields.  Mathematics Studies. Vol. 141. North-Holland, 1987.
  * [2] Gennadiy Averkov.  Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization.  SIAM J. Appl. Algebra Geom., 3(1):128–151, 2019.
  * [3] Christian Berg, Jens Peter Reus Christensen, and Paul Ressel.  Harmonic analysis on semigroups. Theory of positive definite and related functions, volume 100.  Springer, Cham, 1984.
  * [4] Renato G. Bettiol, Mario Kummer, and Ricardo A. E. Mendes.  Convex algebraic geometry of curvature operators.  SIAM J. Appl. Algebra Geom., 5(2):200–228, 2021.
  * [5] Jacek Bochnak, Michel Coste, and Marie-Françoise Roy.  Real algebraic geometry, volume 36 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)].  Springer-Verlag, Berlin, 1998.  Translated from the 1987 French original, Revised by the authors.
  * [6] Nathanial P. Brown and Narutaka Ozawa.  $C^{*}$-algebras and finite-dimensional approximations, volume 88 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2008.
  * [7] Palahenedi Hewage Diananda.  On non-negative forms in real variables some or all of which are non-negative.  Proc. Cambridge Philos. Soc., 58:17–25, 1962.
  * [8] Hamza Fawzi.  The set of separable states has no finite semidefinite representation except in dimension $3\times 2$.  Comm. Math. Phys., 386(3):1319–1335, 2021.
  * [9] Jens Forsgård and Timo de Wolff.  The Algebraic Boundary of the Sonc-Cone.  SIAM J. Appl. Algebra Geom., 6(3):468–502, 2022.
  * [10] Marshall Hall, Jr. and Morris Newman.  Copositive and completely positive quadratic forms.  Proc. Camb. Philos. Soc., 59:329–339, 1963.
  * [11] J. William Helton and Jiawang Nie.  Sufficient and necessary conditions for semidefinite representability of convex hulls and sets.  SIAM J. Optim., 20(2):759–791, 2009.
  * [12] David Hilbert.  über die Darstellung definiter Formen als Summe von Formen- quadraten.  Math. Ann., 32(3):342–350, 1888.
  * [13] Wilfrid Hodges.  Model theory.  Cambridge University Press, Cambridge, 1993.
  * [14] Roger A. Horn and Charles R. Johnson.  Matrix Analysis.  Cambridge University Press, 1985.
  * [15] Samuel Karlin.  Total positivity. Volume I.  Stanford, California: Stanford University Press. XIV, 576 pages, 1968\.
  * [16] David Marker.  Model Theory: An Introduction.  Springer, New York, 2002.
  * [17] David Marker, Ya’acov Peterzil, and Anand Pillay.  Additive reducts of real closed fields.  Journal of Symbolic Logic, 57(1):109–117, 1992.
  * [18] Theodore S. Motzkin.  The arithmetic-geometric inequality.  In Inequalities (Proc. Sympos. Wright-Patterson Air Force Base, Ohio, 1965), pages 205–224. Academic Press, New York, 1967\.
  * [19] Theodore S. Motzkin and Ernst Gabor Straus.  Maxima for graphs and a new proof of a theorem of Turán.  Canadian J. Math., 17:533–540, 1965.
  * [20] Riley Murray, Venkat Chandrasekaran, and Adam Wierman.  Newton polytopes and relative entropy optimization.  Found. Comput. Math., 21(6):1703–1737, 2021.
  * [21] Tim Netzer and Andreas Thom.  Real closed separation theorems and applications to group algebras.  Pac. J. Math., 263(2):435–452, 2013.
  * [22] Jiawang Nie.  Semidefinite representability.  In Semidefinite optimization and convex algebraic geometry, volume 13 of MOS-SIAM Ser. Optim., pages 251–291. SIAM, Philadelphia, PA, 2013.
  * [23] Pablo A. Parrilo.  Polynomial optimization, sums of squares, and applications.  In Semidefinite optimization and convex algebraic geometry, volume 13 of MOS-SIAM Ser. Optim., pages 47–157. SIAM, Philadelphia, PA, 2013.
  * [24] Ya’acov Peterzil.  Reducts of some structures over the reals.  J. Symb. Log., 58(3):955–966, 1993.
  * [25] Reinhard Pöschel and Lev A. Kalužnin.  Funktionen- und Relationenalgebren.  Deutscher Verlag der Wissenschaften, Berlin, 1979.
  * [26] Victoria Powers and Bruce Reznick.  A note on mediated simplices.  J. Pure Appl. Algebra, 225(7), 2021.
  * [27] Alexander Prestel and Charles N. Delzell.  Positive polynomials.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2001.  From Hilbert’s 17th problem to real algebra.
  * [28] Bruce Reznick.  Forms derived from the arithmetic-geometric inequality.  Math. Ann., 283(3):431–464, 1989.
  * [29] James Saunderson.  Limitations on the expressive power of convex cones without long chains of faces.  SIAM J. Optim., 30(1):1033–1047, 2020.
  * [30] Claus Scheiderer.  Semidefinite representation for convex hulls of real algebraic curves.  SIAM J. Appl. Algebra Geom., 2(1):1–25, 2018.
  * [31] Claus Scheiderer.  Spectrahedral shadows.  SIAM J. Appl. Algebra Geom., 2(1):26–44, 2018.
  * [32] Claus Scheiderer.  Second-order cone representation for convex sets in the plane.  SIAM J. Appl. Algebra Geom., 5(1):114–139, 2021.
  * [33] Katrin Tent and Martin Ziegler.  A course in model theory.  Lecture Notes in Logic. Cambridge University Press, 2012.