11institutetext: University of California, Davis, Davis CA 95616, USA
11email<EMAIL_ADDRESS>22institutetext: Texas A&M
University, College Station TX 77843, USA
22email<EMAIL_ADDRESS>
# Integer Points in Arbitrary Convex Cones:
The Case of the PSD and SOC Cones ††thanks: Due to space limitations, we omit
several proofs. These can be found at
https://www.math.ucdavis.edu/d̃eloera/IPCO2024.pdf.
This research is partially based upon work supported by the National Science
Foundation under Grant No. DMS-1929284 while the first, third, and fourth
authors were in residence at the Institute for Computational and Experimental
Research in Mathematics in Providence, RI, during the Discrete Optimization
program. We thank Kurt Anstreicher, Renata Sotirov, Pablo Parrilo, Chiara
Meroni, and Bento Natura for relevant comments.

Jesús A. De Loera 11 0000-0002-9556-1112 Brittney Marsters 11
0009-0000-5656-0670 Luze Xu 11 0000-0001-5705-4403 Shixuan Zhang 22
0000-0002-0606-4756

###### Abstract

We investigate the semigroup of integer points inside a convex cone. We extend
classical results in integer linear programming to integer conic programming.
We show that the semigroup associated with nonpolyhedral cones can sometimes
have a notion of finite generating set. We show this is true for the cone of
positive semidefinite matrices (PSD) and the second-order cone (SOC). Both
cones have a finite generating set of integer points, similar in spirit to
Hilbert bases, under the action of a finitely generated group. We also extend
notions of total dual integrality, Gomory-Chvátal closure, and Carathéodory
rank to integer points in arbitrary cones.

###### Keywords:

Integer Points Convex Cones Semigroups Hilbert bases Conic Programming
Positive Semidefinite Cone Second-Order Cone

##  1 Introduction

A semigroup $S$ is a subset of $\mathbb{Z}^{N}$ that contains $\mathbf{0}$ and
is closed under addition. Given a convex cone $C\subseteq\mathbb{R}^{N}$, the
integer points $S_{C}\mathrel{\mathop{\ordinarycolon}}=C\cap\mathbb{Z}^{N}$
form a semigroup which we will call the _conical semigroup_ of $C$. In
particular, given any compact convex body $K\subseteq\mathbb{R}^{n}$, the
integer points $\text{cone}(K\times\\{1\\})\cap\mathbb{Z}^{n+1}$ form a
conical semigroup. Conical semigroups appear not just in optimization [1, 6],
but also in algebra and number theory [2, 3]. Given a convex cone
$C\subseteq\mathbb{R}^{N}$ for $N\geq 1$, we say a subset $B\subseteq S_{C}$
is an _integral generating set_ of $S_{C}$ if for any $s\in S_{C}$ there exist
$b_{1},\dots,b_{m}\in B$ and $c_{1},\dots,c_{m}\in\mathbb{Z}_{\geq 0}$ such
that $s=\sum_{i=1}^{m}c_{i}b_{i}$, for some $m\geq 1$. Furthermore, we call
$B$ a _conical Hilbert basis_ if $B$ is an inclusion-minimal integral
generating set.

When the defining cone $C$ is rational, polyhedral and pointed, there is
abundant literature on the topic. It is well-known that we have a unique
finite Hilbert basis in this case [11, 20]. Historically, Hilbert bases have
been fundamental in the theory and algorithms of combinatorial optimization.
For example, determining if a rational system $A\mathbf{x}\leq\mathbf{b}$ is
totally dual integral (TDI) is equivalent to checking if, for every face $F$
of the polyhedron
$P\mathrel{\mathop{\ordinarycolon}}=\\{\mathbf{x}\mathrel{\mathop{\ordinarycolon}}A\mathbf{x}\leq\mathbf{b}\\}$,
the rows of $A$ which are active in a face $F$ form a Hilbert basis for
cone($F$)[20].

It is natural to ask, what properties transfer from rational polyhedral cones
to arbitrary convex cones? For instance, _do we preserve any notion of
finiteness in generating sets for semigroups when we relax the polyhedral
condition and instead consider general conical semigroups? Are there Hilbert
bases for general cones?_ This paper discusses finite generation for conical
semigroups and extends the polyhedral cone theory of Hilbert bases to
nonpolyhedral convex cones. Our main results will pertain to the semigroups
arising from the cone of positive semidefinite matrices and the second-order
cone. Both cones play a key role in modern optimization [4, 5]. We also
discuss some applications of our nonpolyhedral point of view.

In what follows, we denote
$\mathrm{GL}(N,\mathbb{Z})\mathrel{\mathop{\ordinarycolon}}=\\{U\in\mathbb{Z}^{N\times
N}\mathrel{\mathop{\ordinarycolon}}~{}|\det(U)|=1\\}$. Here is a new notion of
finite generation for conical semigroups.

###### Definition 1

Given a conical semigroup $S_{C}\subset\mathbb{Z}^{N}$, we call it
$(R,G)$-finitely generated if there is a finite subset $R\subseteq S_{C}$ and
a finitely generated subgroup $G\subseteq\mathrm{GL}(N,\mathbb{Z})$ acting on
$C$ linearly such that

  1. 1.

both the cone $C$ and the semigroup $S_{C}$ are invariant under the group
action, i.e., $G\cdot C=C$ and $G\cdot S_{C}=S_{C}$, and

  2. 2.

every element $s\in S_{C}$ can be represented as

$s=\displaystyle\sum_{i\in K}\lambda_{i}g_{i}\cdot r_{i}$

for $r_{i}\in R$, $g_{i}\in G$, and $\lambda_{i}\in\mathbb{Z}_{\geq 0}$, and
where $K$ is a finite index set.

Note that when $C$ is a (pointed) rational polyhedral cone, then the conical
semigroup $S_{C}=C\cap\mathbb{Z}^{N}$ is $(R,G)$-finitely generated by $R$,
its Hilbert basis, and $G$, the trivial group $\\{I_{N}\\}$. Similarly, note
that if $S_{C}$ is an $(R,G)$-finitely generated semigroup, then $\cup_{r\in
R}G\cdot r$ is an integral generating set of $S_{C}$, which is a superset of a
conical Hilbert basis. We call $R$ the set of _roots_ of $S_{C}$, and
$\cup_{r\in R}G\cdot r$ the set of generators for $S_{C}$.

While a nonpolyhedral cone cannot be finitely generated in the usual sense,
using a possibly infinite (finitely generated) group $G$ allows us to extend
our understanding beyond the polyhedral case. Because the possibly infinite
generators for $S_{C}$ can be obtained by group action $G$ on a finite set $R$
and $G$ is finitely generated, this allows for the possibility of algorithmic
methods. The well-known Krein-Milman theorem states that any point in a closed
pointed cone $C$ can be generated by extreme rays, denoted by
$\operatorname{ext}(C)$ [4]. When we restrict to the conical semigroup $S_{C}$
and nonnegative integer combinations, the primitive integer points on the
extreme rays of $C$ must be contained in the set of generators of $S_{C}$,
where an integer point $x=(x_{1},\dots,x_{N})\in\mathbb{Z}^{N}$ is _primitive_
if $\mathrm{gcd}(x_{1},\dots,x_{N})=1$. We call the integer points of $S_{C}$
on the extreme rays of $C$ _extreme points_ , denoted by
$\operatorname{ext}(S_{C})\mathrel{\mathop{\ordinarycolon}}=\\{y\in
S_{C}\mathrel{\mathop{\ordinarycolon}}y\in\operatorname{ext}(C)\cap\mathbb{Z}^{N}\\}$.
However, as in the polyhedral case, the generators will often include extra
nonextreme boundary points or even interior points. We provide the following
definition of _sporadic points_ that cannot have an extreme point subtracted
from them and still remain within the cone.

###### Definition 2

We say a point $x\in S_{C}=C\cap\mathbb{Z}^{N}$ is sporadic if there does not
exist $y\in\operatorname{ext}(S_{C})$ such that $x-y\in S_{C}$.

If $x\in S_{C}$ is sporadic, then $x$ cannot be written as an integer conical
combination of extreme points (even though it can be written as a real
combination of them). From the definition of sporadic points, we know that all
points $x\in S_{C}$ can be written as an integer conical combination of
primitive extreme points and one sporadic point. To show that a semigroup is
$(R,G)$-finitely generated, it is sufficient to show that the set of primitive
extreme points and sporadic points are finite or can be obtained from a
finitely generated group $G$ that acts on a finite set of roots, $R$.

The two convex cones of interest in this work are positive semidefinite cone
(PSD) and second-order cone (SOC). In Sections 2 and 3 of this paper, we will
present the following two main results pertaining to integer points in the PSD
cone $\mathcal{S}^{n}_{+}(\mathbb{Z})$, and those in the SOC
$\mathrm{SOC}(n)\cap\mathbb{Z}^{n}$.

###### Theorem 1.1

The conical semigroup of the cone of $n\times n$ positive semidefinite
matrices, $\mathcal{S}^{n}_{+}(\mathbb{Z})$, is $(R,G)$-finitely generated by
$G\cong\mathrm{GL}(n,\mathbb{Z})$ where $G$ acts on
$X\in\mathcal{S}^{n}_{+}(\mathbb{Z})$ by $X\mapsto UXU^{\mathsf{T}}$ for each
$U\in\mathrm{GL}(n,\mathbb{Z})$, and by $R$, the union of any single rank-one
matrix and a finite subset of the sporadic points. Moreover,

  1. 1.

If $n\leq 5$, then there are no sporadic points. Thus,
$R=\\{\mathbf{e}_{1}\mathbf{e}_{1}^{\mathsf{T}}\\}$, where $\mathbf{e}_{1}$ is
the first unit vector.

  2. 2.

If $n=6$, then $R=\\{\mathbf{e}_{1}\mathbf{e}_{1}^{\mathsf{T}},M\\}$, where
$M$ is a single sporadic point defined in Section 2 Proposition 5.

###### Theorem 1.2

For dimension $3\leq n\leq 10$, the conical semigroup
$\mathrm{SOC}(n)\cap\mathbb{Z}^{n}$ is $(R,G)$-finitely generated with $G$ and
$R$ defined in Section 3.

We say that two matrices $X_{1},X_{2}$ are unimodularly equivalent if
$X_{2}=U\cdot X_{1}=UX_{1}U^{\mathsf{T}}$ for some
$U\in\mathrm{GL}(n,\mathbb{Z})$. It is easy to see that it defines an
equivalence relation for all integer PSD matrices. Note that the equivalence
class of $\mathbf{e}_{1}\mathbf{e}_{1}^{\mathsf{T}}$ are all rank-1 integer
matrix $\mathbf{x}\mathbf{x}^{\mathsf{T}}$ for some primitive integer vector
$\mathbf{x}\in\mathbb{Z}^{n}$. An interpretation of Theorem 1.1 is that for
dimension $n\leq 5$, every integer PSD matrix can be represented as the sum of
rank-$1$ matrices $\mathbf{x}\mathbf{x}^{\mathsf{T}}$ for some primitive
integer vector $\mathbf{x}\in\mathbb{Z}^{n}$. However, the same result fails
for dimension $n=6$. In this case, we will have that every integer PSD matrix
can be represented as the sum of rank-$1$ matrices and one sporadic matrix
$Y$, which is unimodularly equivalent to $M$ (this matrix was first found by
[19]). In general, every integer PSD matrix can be represented as the sum of
rank-$1$ matrices and one sporadic matrix, which is unimodularly equivalent to
a matrix in the finite set $R$. Regarding prior work that inspired us, we
mention [16] that contains a similar rank-1 decomposition structure for PSD
$\\{0,1\\}$ matrices: a PSD $\\{0,1\\}$ matrix
$X\in\mathcal{S}^{n}_{+}(\mathbb{Z})\cap\\{0,1\\}^{n\times n}$ satisfies
$X=\sum_{i\in K}\mathbf{x}_{i}\mathbf{x}_{i}^{\mathsf{T}}$ for
$\mathbf{x}_{i}\in\\{0,1\\}^{n}$, where $K$ is a finite index set. Similarly,
[18] extended the results to PSD $\\{0,\pm 1\\}$ matrices: a PSD $\\{0,\pm
1\\}$ matrix $X\in\mathcal{S}^{n}_{+}(\mathbb{Z})\cap\\{0,\pm 1\\}^{n\times
n}$ satisfies $X=\sum_{i\in K}\mathbf{x}_{i}\mathbf{x}_{i}^{\mathsf{T}}$ for
$\mathbf{x}_{i}\in\\{0,\pm 1\\}^{n}$, where $K$ is a finite index set. Our
results extend to all integer positive semidefinite matrices. For the second-
order cone, we extended the construction of the Barning-Hall tree in [8] for
the primitive extreme points (or Pythagorean tuples) to classify the sporadic
points.

While it might be tempting to believe that these results hint that all conical
semigroups are $(R,G)$-finitely generated for some finite set $R$ and some
subgroup $G\subseteq\mathrm{GL}(N,\mathbb{Z})$, we conjecture the contrary:

###### Conjecture 1

There exists a conical semigroup $S_{C}$ that is not $(R,G)$-finitely
generated for any choice of $R$ and $G$.

What is the significance of these results beyond their connections to
classical geometry of numbers, lattices, and number theory? (See e.g., [14]).
We motivate our interest about conical semigroups with two applications in
optimization. In what follows, we assume that our cone
$C\subset\mathbb{R}^{N}$ is full-dimensional.

The first application regards the notion of _Chvátal-Gomory cuts_ which is
useful in the branch-and-cut methods for integer programming. How much of this
can be extended to conic integer programming? Given a linear map
$\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{m}\to\mathbb{R}^{N}$
and $\mathbf{c}\in\mathbb{R}^{N}$, we define a _linear conical inequality_
(LCI) system as

$\mathrm{LCI}_{C}(\mathbf{c},\mathcal{A})\mathrel{\mathop{\ordinarycolon}}=\\{\mathbf{x}\in\mathbb{R}^{m}\mathrel{\mathop{\ordinarycolon}}\mathbf{c}-\mathcal{A}(\mathbf{x})\in
C\\}$

where $\mathbf{c}\in\mathbb{Z}^{N}$ and
$\mathcal{A}(\mathbb{Z}^{m})\subseteq\mathbb{Z}^{N}$. When $C$ is the cone of
positive semidefinite matrices in $\mathcal{S}^{n}(\mathbb{R})$, then
$N=\binom{n+1}{2}$ and $\mathcal{A}(\mathbf{x})=\sum_{i=1}^{m}x_{i}A_{i}$ for
some matrices $A_{1},\dots,A_{m}\in\mathcal{S}^{n}(\mathbb{Z})$. This is known
as a _linear matrix inequality_ and defines a _spectrahedron_. An important
concept for LCI is called total dual integrality (TDI), which has been well-
known for polyhedral cones $C$ [13, 12] and recently extended to spectrahedral
cones [7, 17]. We use $C^{*}$ to denote the dual cone of $C$,
$\mathcal{A}^{*}$ to denote the adjoint linear map of $\mathcal{A}$, and give
a definition for general cones here.

###### Definition 3

An LCI system $\mathbf{c}-\mathcal{A}(\mathbf{x})\in C$ is totally dual
integral, if for any $\mathbf{b}\in\mathbb{Z}^{m}$, the dual optimization
problem

$\displaystyle\min\quad$ $\displaystyle
y(\mathbf{c})\quad\mathrm{s.t.}\quad\mathcal{A}^{*}(y)=\mathbf{b},\ y\in
C^{*},$

whenever feasible, has an integer optimal solution $y^{*}\in
C^{*}\cap\mathbb{Z}^{N}$.

To approximate the convex hull of
$Z\mathrel{\mathop{\ordinarycolon}}=\mathrm{LCI}_{C}(\mathbf{c},\mathcal{A})\cap\mathbb{Z}^{m}$,
a commonly used approach (quite similar to its polyhedral version) is to add
_Chvátal-Gomory_ (CG) cuts, which are defined as follows [17]. If
$\mathbf{u}\in\mathbb{Z}^{m}$ is an integral vector and $v\in\mathbb{R}$ a
real number such that the linear inequality
$\mathbf{u}^{\mathsf{T}}\mathbf{x}\leq v$ is _valid_ for all
$x\in\mathrm{LCI}_{C}(c,\mathcal{A})$, then the inequality
$\mathbf{u}^{\mathsf{T}}\mathbf{x}\leq\lfloor v\rfloor$ is valid for all
$\mathbf{x}\in Z$ and called a CG cut. There are possibly infinitely many CG
cuts so we define the (elementary) CG closure as

$\mathrm{CG}\text{-}\mathrm{cl}(Z)\mathrel{\mathop{\ordinarycolon}}=\bigcap_{\begin{subarray}{c}(\mathbf{u},v)\in\mathbb{Z}^{m}\times\mathbb{R}\mathrel{\mathop{\ordinarycolon}}\\\
S\subseteq\\{\mathbf{x}\mathrel{\mathop{\ordinarycolon}}\mathbf{u}^{\mathsf{T}}\mathbf{x}\leq
v\\}\end{subarray}}\left\\{\mathbf{x}\in\mathbb{R}^{m}\mathrel{\mathop{\ordinarycolon}}\mathbf{u}^{\mathsf{T}}\mathbf{x}\leq\lfloor
v\rfloor\right\\}.$ (1)

Now take any linear function $w\in C^{*}$ such that
$w(\mathbb{Z}^{N})\subseteq\mathbb{Z}$. Then, a CG cut can be generated by

$w\circ\mathcal{A}(\mathbf{x})\leq\lfloor w(\mathbf{c})\rfloor,$

as, by definition, $w\circ\mathcal{A}(\mathbb{Z}^{m})\in\mathbb{Z}$.
Conversely, if the conical semigroup
$S_{C^{*}}\mathrel{\mathop{\ordinarycolon}}=C^{*}\cap\mathbb{Z}^{N}$ is
$(R,G)$-finitely generated, then we can get all CG cuts through $R$ and $G$
for our TDI LCI system. This is one of the nice consequences of this property.

###### Theorem 1.3

Suppose $C\subset\mathbb{R}^{N}$ is a full-dimensional convex cone such that
$S_{C^{*}}\mathrel{\mathop{\ordinarycolon}}=C^{*}\cap\mathbb{Z}^{N}$ is
$(R,G)$-finitely generated, and $\mathrm{LCI}_{C}(\mathbf{c},\mathcal{A})$ is
TDI. Then the CG closure for
$Z\mathrel{\mathop{\ordinarycolon}}=\mathrm{LCI}_{C}(\mathbf{c},\mathcal{A})\cap\mathbb{Z}^{m}$
can be described by

$\mathrm{CG}\text{-}\mathrm{cl}(Z)=\left\\{\mathbf{x}\in\mathbb{R}^{m}\mathrel{\mathop{\ordinarycolon}}(g\cdot
r)^{\mathsf{T}}\mathcal{A}(\mathbf{x})\leq\lfloor(g\cdot
r)^{\mathsf{T}}\mathbf{c}\rfloor,\quad\forall\,r\in R,g\in G\right\\}.$

The final application has to do with classical notions of integer rank [10].
Just like the notion of (real) rank of a linear system allows us to bound the
number of nonzero entries in a solution of a linear system, we want to know
how many elements are needed to decompose any element of a conical semigroup
as a linear combination of generators with nonnegative integer coefficients.
Suppose that our conical semigroup $S_{C}=C\cap\mathbb{Z}^{N}$ has an integer
generating set $B$. For any element $s\in S_{C}$, there exist integer
generators $b_{1},\dots,b_{m}\in B$ and
$\lambda_{1},\dots,\lambda_{m}\in\mathbb{Z}_{\geq 1}$ such that
$s=\sum_{i=1}^{m}\lambda_{i}b_{i}$, for some $m\geq 1$. The minimum number $m$
needed in the sum is called the _integer Carathéodory rank_ (ICR) of $s$, and
the maximum number over all $s\in S_{C}$ is the ICR of the conical semigroup
$S_{C}$ or the cone $C$. We show an upper bound on the ICR that depends only
on the dimension $N$. The proof is almost identical to the popular polyhedral
result in [10, 22] but we must use the extreme point characterization of semi-
infinite linear optimization [9] to allow infinite generating sets.

###### Theorem 1.4

Let $C\subset\mathbb{R}^{N}$ be an arbitrary pointed convex cone and
$S_{C}\mathrel{\mathop{\ordinarycolon}}=C\cap\mathbb{Z}^{N}$. Then
$\mathrm{ICR}(S_{C})\leq 2N-2$.

##  2 The Positive Semidefinite (PSD) Cone

Let $\mathcal{S}^{n}(\mathbb{Z})$ (resp. $\mathcal{S}^{n}(\mathbb{R})$) denote
the set of $n\times n$ symmetric matrices of integer (resp. real) entries. For
a matrix $X\in\mathcal{S}^{n}(\mathbb{Z})$, we say that $X$ is PSD (denoted as
$X\succeq 0$) if and only if it is so when regarded as a real matrix
$X\in\mathcal{S}^{n}(\mathbb{R})$. We denote $\mathcal{S}^{n}_{+}(\mathbb{Z})$
as the set of integer PSD matrices.

The group $\mathrm{GL}(n,\mathbb{Z})$ embeds into $\mathrm{GL}(N,\mathbb{Z})$
as follows. Given a matrix $U\in\mathrm{GL}(n,\mathbb{Z})$ and any
$X\in\mathcal{S}^{n}(\mathbb{Z})$, we define the action $U\cdot
X\mathrel{\mathop{\ordinarycolon}}=UXU^{\mathsf{T}}$. This action is a linear
map and takes integer points in $\mathbb{Z}^{N}$ to integer points, and thus
can be represented by the multiplication with a matrix in
$\mathrm{GL}(N,\mathbb{Z})$. It is well-known that this group
$\mathrm{GL}(n,\mathbb{Z})$ is finitely generated [23]. For the convenience of
discussion, we still use the matrix $U\in\mathrm{GL}(n,\mathbb{Z})$ to denote
this matrix multiplication in the subgroup of $\mathrm{GL}(N,\mathbb{Z})$.

###  2.1 Lemmas for $n\leq 5$ and $n=6$

The following _integer rank-1 decomposition_ for PSD integer matrices is
studied in [19]. We recast their arguments with a modern geometric
perspective, and use it to extend the notion of $(R,G)$-finite generation to
the PSD cone.

###### Lemma 1

If $n\leq 5$, then for any $X\in\mathcal{S}_{+}^{n}(\mathbb{Z})$, we can find
a finite index set $K$ and vectors $\mathbf{x}_{i}\in\mathbb{Z}^{n}$, $i\in K$
such that

$X=\sum_{i\in K}\mathbf{x}_{i}\mathbf{x}_{i}^{\mathsf{T}}.$ (2)

To restate Definition 2 in the PSD case, we say an integer matrix
$X\in\mathcal{S}^{n}(\mathbb{Z})$ is _sporadic_ if there does not exist
$\mathbf{x}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}$ such that
$X-\mathbf{x}\mathbf{x}^{\mathsf{T}}\succeq 0$. Lemma 1 is equivalent to the
fact that there is no sporadic point in $\mathcal{S}_{+}^{n}(\mathbb{Z})$ when
$n\leq 5$.

###### Proposition 1

There is no sporadic point in $\mathcal{S}_{+}^{n}(\mathbb{Z})$ if and only if
every positive semidefinite integer matrix in
$\mathcal{S}_{+}^{n}(\mathbb{Z})$ has an integer rank-1 decomposition.

For any matrix $X\in\mathcal{S}^{n}(\mathbb{R})$, we can define a convex set
$C(X)\mathrel{\mathop{\ordinarycolon}}=\\{\mathbf{x}\in\mathbb{R}^{n}\mathrel{\mathop{\ordinarycolon}}X-\mathbf{x}\mathbf{x}^{\mathsf{T}}\succeq
0\\}$. Since $X-\mathbf{x}\mathbf{x}^{\mathsf{T}}\succeq 0$ if and only if,
for any $\mathbf{v}\in\mathbb{R}^{n}$,
$|\mathbf{v}^{\mathsf{T}}\mathbf{x}|^{2}\leq\mathbf{v}^{\mathsf{T}}X\mathbf{v}$,
we see that $C(X)$ is a compact convex set that is symmetric about the origin.
This provides another equivalent formulation of the integer rank-1
decomposition.

###### Proposition 2

For $X\in\mathcal{S}_{+}^{n}(\mathbb{Z})$, $X$ is sporadic if and only if
$C(X)\cap\mathbb{Z}^{n}=\\{\mathbf{0}\\}$.

This provides a geometric perspective to our problem. Note that the set $C(X)$
is a (possibly degenerate) ellipsoid because

$X\succeq\mathbf{x}\mathbf{x}^{\mathsf{T}}\iff\begin{bmatrix}1&\mathbf{x}^{\mathsf{T}}\\\
\mathbf{x}&X\end{bmatrix}\succeq
0\iff\mathbf{x}^{\mathsf{T}}X^{\dagger}\mathbf{x}\leq
1,(I-XX^{\dagger})\mathbf{x}=0,$

by the positive semidefiniteness of Schur complements, where $X^{\dagger}$
denotes the pseudoinverse of $X$. In the case where $\det(X)>0$,

$C(X)=\\{\mathbf{x}\in\mathbb{R}^{n}\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{\mathsf{T}}\mathrm{adj}(X)\mathbf{x}\leq\det(X)\\}\text{
with }\mathrm{vol}(C(X))=V_{n}\sqrt{\det(X)}$

where $\mathrm{adj}(X)$ is the adjugate of $X$ satisfying
$\mathrm{adj}(X)=\det(X)X^{-1}$ and
$V_{n}\mathrel{\mathop{\ordinarycolon}}=\pi^{n/2}/\Gamma(\frac{n}{2}+1)$ is
the volume of the unit $n$-ball. Note that $C(X)$ is not necessarily full-
dimensional if $X$ is rank deficient. The degenerate case for rank 1 is
characterized by the following proposition.

###### Proposition 3

Suppose $X\in\mathcal{S}_{+}^{n}(\mathbb{Z})$, and $\mathrm{rank}(X)=1$, then
$X=\lambda\mathbf{x}\mathbf{x}^{\mathsf{T}}$, where
$\mathbf{x}\in\mathbb{Z}^{n}$ and $\lambda\in\mathbb{Z}_{\geq 1}$.

From Proposition 3, we can directly prove the case for $n=2$ using Minkowski’s
first Theorem (for example, see [11]): if $\mathrm{vol}(C(X))>4$, then there
is a nonzero integral point.

###### Proposition 4

Lemma 1 holds for $n=2$.

In the general degenerate case, we can reduce the problem to one involving
full-rank matrices of some lower dimension.

###### Lemma 2

Let $X\in\mathcal{S}^{n}(\mathbb{Z})$. If $r=\mathrm{rank}(X)<n$, then $X$ is
unimodularly equivalent to

$\begin{bmatrix}\mathbf{0}&\mathbf{0}\\\ \mathbf{0}&\hat{X}\end{bmatrix},$

for some $\hat{X}\in\mathbb{Z}^{r\times r}$, $\mathrm{rank}(\hat{X})=r$.

To prove Lemma 1, we need to use a more sophisticated method based on the
_Hermite constant_ [21]

$\gamma_{n}\mathrel{\mathop{\ordinarycolon}}=\left(\max_{A\succ
0}\frac{\lambda_{1}(A)}{(\det(A))^{\frac{1}{n}}}\right)^{n},\text{ where
}\lambda_{1}(A)=\min_{\mathbf{x}\in\mathbb{Z}^{n}\setminus\\{\bf
0\\}}(\mathbf{x}^{\mathsf{T}}A\mathbf{x}).$

###### Remark 1

Hermite gives a bound $\gamma_{n}\leq(\frac{4}{3})^{\frac{n(n-1)}{2}}$. The
exact value of $\gamma_{n}$ is only known for $n\leq 8$ and $n=24$.

$n$ |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  24
---|---|---|---|---|---|---|---|---
$\gamma_{n}$ |  $\frac{4}{3}$ |  2 |  2 |  8 |  $\frac{64}{3}$ |  64 |  256 |  $4^{24}$

######  Proof (for Lemma 1)

The case $n=1$ follows from Proposition 3. We will show that
$C(X)\cap\mathbb{Z}^{n}\neq\\{\mathbf{0}\\}$ for $2\leq n\leq 5$, where
$C(X)=\\{\mathbf{x}\in\mathbb{R}^{n}\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{\mathsf{T}}\mathrm{adj}(X)\mathbf{x}\leq\det(X)\\}$.
By the definition of the Hermite constant, we have

$\min_{\mathbf{x}\in\mathbb{Z}^{n}\setminus\\{\bf
0\\}}(\mathbf{x}^{\mathsf{T}}\mathrm{adj}(X)\mathbf{x})\leq(\gamma_{n}\det(\mathrm{adj}(X)))^{\frac{1}{n}}=(\gamma_{n}(\det(X))^{n-1})^{\frac{1}{n}}.$

For $n=2,3,4,5$, we have $\frac{n^{n}}{(n-1)^{n-1}}>\gamma_{n}$. By taking the
derivative with respect to $\det(X)$, we know that
$\frac{(\det(X)+1)^{n}}{(\det(X))^{n-1}}\geq\frac{n^{n}}{(n-1)^{n-1}}$. Thus,
$\gamma_{n}<\frac{(\det(X)+1)^{n}}{\det(X)^{n-1}}$. Therefore,

$\min_{\mathbf{x}\in\mathbb{Z}^{n}\setminus\\{\bf
0\\}}(\mathbf{x}^{\mathsf{T}}\mathrm{adj}(X)\mathbf{x})\leq(\gamma_{n}\det(\mathrm{adj}(X)))^{\frac{1}{n}}=(\gamma_{n}\det(X)^{n-1})^{\frac{1}{n}}<\det(X)+1.$

Because $x^{\mathsf{T}}\mathrm{adj}(X)x,\det(X)\in\mathbb{Z}$ for any
$x\in\mathbb{Z}^{n}$, we have

$\min_{\mathbf{x}\in\mathbb{Z}^{n}\setminus\\{\bf
0\\}}(\mathbf{x}^{\mathsf{T}}\mathrm{adj}(X)\mathbf{x})\leq\det(X),$

which implies that
$C(X)\cap(\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\})\neq\emptyset$. Lemma 1 now
follows from Propositions 2 and 1, and Lemma 2. ∎

The argument used to prove Lemma 1 fails for $n\geq 6$, but it implies that
the determinant of the sporadic matrices is bounded by a constant only
dependant on $n$. For example, in the case of $n=6$, the argument only fails
when $3\leq\det(X)\leq 14$; for $n=7$, it only fails when $2\leq\det(X)\leq
56$, and for $n=8$, it only fails when $1\leq\det(X)\leq 247$. We summarize
this observation in the following corollary.

###### Corollary 1

If $X\in\mathcal{S}_{+}^{n}(\mathbb{Z})$ is sporadic, then
$\det(X)<\gamma_{n}$.

A sporadic matrix for $n=6$ was initially found in [19].

###### Proposition 5

In $n=6$, the matrix $M$ is sporadic, i.e.,
$C(M)\cap\mathbb{Z}^{n}=\\{\mathbf{0}\\}$.

$M=\left[\begin{array}[]{c@{\hskip 1em}c@{\hskip 1em}c@{\hskip 1em}c@{\hskip
1em}c@{\hskip 1em}c}2\hfil\hskip 10.00002pt&0\hfil\hskip
10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\\\\[-5.0pt] 0\hfil\hskip 10.00002pt&2\hfil\hskip
10.00002pt&0\hfil\hskip 10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\\\\[-5.0pt] 1\hfil\hskip 10.00002pt&0\hfil\hskip
10.00002pt&2\hfil\hskip 10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\\\\[-5.0pt] 1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\hfil\hskip 10.00002pt&2\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\\\\[-5.0pt] 1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip 10.00002pt&2\hfil\hskip
10.00002pt&1\\\\[-5.0pt] 1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip 10.00002pt&1\hfil\hskip
10.00002pt&2\end{array}\right]\text{ with }\det(M)=3.$

Moreover, in [15], it is shown that for $n=6$, $M$ is the unique sporadic
matrix under unimodular equivalence. Using this fact, we have the following
Lemma.

###### Lemma 3

If $n=6$, then for any $X\in\mathcal{S}_{+}^{n}(\mathbb{Z})$,

$X=\sum_{i\in K}\mathbf{x}_{i}\mathbf{x}_{i}^{\mathsf{T}}+Y$

for $\mathbf{x}_{i}\in\mathbb{Z}^{n}$ and $Y$ unimodularly equivalent to $M$,
where $K$ is a finite index set.

###  2.2 Proof of Theorem 1.1

###### Proof

We know that the primitive extreme points are generated from the group
$\mathrm{GL}(n,\mathbb{Z})$ that acts on
$\\{\mathbf{e}_{1}\mathbf{e}_{1}^{\mathsf{T}}\\}$. The finiteness of the index
set $K$ follows from similar argument in Proposition 1. We only need to prove
that the sporadic points are generated from the group
$\mathrm{GL}(n,\mathbb{Z})$ on a finite set $R$.

Corollary 1 shows that for any sporadic matrix $X$, $\det(X)<\gamma_{n}$. By
[21, Theorem 2.4], there exists a constant $\alpha_{n}>0$ depending only on
$n$, such that for any positive definite matrix
$X\in\mathcal{S}^{n}(\mathbb{Z})$, there is a unimodularly equivalent matrix
$X^{\prime}$ of $X$ with diagonal entries satisfy

$\prod_{i=1}^{n}X^{\prime}_{ii}\leq\alpha_{n}\det(X^{\prime})=\alpha_{n}\det(X)<\alpha_{n}\gamma_{n}.$

Because $X^{\prime}\in\mathcal{S}^{n}(\mathbb{Z})$ is positive definite,
$X^{\prime}_{ii}\geq 1$ and thus is bounded from above. From this we see that
there are only finitely many possibilities for such $X^{\prime}$ because each
off-diagonal entry must satisfy $|X^{\prime}_{ij}|^{2}\leq
X^{\prime}_{ii}X^{\prime}_{jj}$ for any $1\leq i,j\leq n$.

The two special cases $n\leq 5$ and $n=6$ follow from Lemma 1 and 3. ∎

##  3 The Second-Order Cone (SOC)

In this section, we will let $T_{n}$ be the conical semigroup
$\text{SOC}(n)\cap\mathbb{Z}^{n}$ where

${\small\text{SOC}(n)\mathrel{\mathop{\ordinarycolon}}=\left\\{\mathbf{x}\in\mathbb{R}^{n}\mathrel{\mathop{\ordinarycolon}}0\leq\sqrt{x_{1}^{2}+\dots+x_{n-1}^{2}}\leq
x_{n}\right\\}.}$

Additionally, for $\mathbf{a},\mathbf{b}\in\mathbb{R}^{n}$, consider the
bilinear form

$\displaystyle\langle\mathbf{a},\mathbf{b}\rangle\mathrel{\mathop{\ordinarycolon}}=a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n-1}b_{n-1}-a_{n}b_{n}.$

In this quadratic space, the reflection in vector $\mathbf{w}$ is defined as
$\mathbf{x}\rightarrow\mathbf{x}-2\frac{\langle\mathbf{x},\mathbf{w}\rangle}{\langle\mathbf{w},\mathbf{w}\rangle}\mathbf{w}$.

###### Definition 4

Let $P_{i,j}$ be the permutation matrix that swaps the $i$-th and $j$-th
columns and define $Q_{k}$ be the matrix determined by

$(Q_{k})_{i,j}=\begin{cases}-1&\text{ if }i=j=k\\\ 1&\text{ if }i=j\neq k\\\
0&\text{ if }i\neq j.\end{cases}$

For $n=3$, let $A_{3}$ denote the matrix associated with the reflection in the
vector $(1,1,1)$. For $4\leq n\leq 10$, let $A_{n}$ denote the matrix
associated with the reflection in the vector $(1,1,1,0,\dots,0,1)$ also
associated to this bilinear form:

$A_{3}=\begin{pmatrix}-1&-2&2\\\ -2&-1&2\\\ -2&-2&3\\\ \end{pmatrix},\hskip
8.53581ptA_{n}=\begin{pmatrix}\begin{matrix}0&-1&-1\\\ -1&0&-1\\\
-1&-1&0\end{matrix}&\vline&\mbox{\Large 0}&\vline&\begin{matrix}1\\\ 1\\\
1\end{matrix}\\\ \hline\cr\mbox{\Large
0}&\vline&\text{I}_{n-4}&\vline&\mbox{\Large 0}\\\
\hline\cr\begin{matrix}-1&-1&-1\end{matrix}&\vline&\mbox{\Large
0}&\vline&2\end{pmatrix}$

We define the matrix $A_{n}^{+}=Q_{1}Q_{2}\dots Q_{n-1}A_{n}$. Note that
$A_{n}$ is unimodular.

Elements $\mathbf{s}\in T_{n}$ such that
$\langle\mathbf{s},\mathbf{s}\rangle=\bf 0$ belong to the boundary of $T_{n}$,
and we will denote the set of these points as $\partial T_{n}$. In number
theory, these points are called Pythagorean tuples. In [8], they proved that
the set of primitive Pythagorean tuples, denoted as
$\operatorname{ext}^{p}(T_{n})$, is generated by finitely many matrices acting
on a finite set $R$ for $3\leq n\leq 10$.

######  Lemma 4 (Theorem 1 in [8])

For $3\leq n\leq 10$, $\operatorname{ext}^{p}(T_{n})=\cup_{r\in R}G\cdot r$,
where the group

$G=\left\langle A_{n},Q_{1},\dots,Q_{n-1},P_{1,2},P_{1,3},\dots
P_{1,n-1}\right\rangle$

and the sets

  1. 1.

$R=\left\\{(1,0,\dots,0,1)^{\mathsf{T}}\right\\}$ for $3\leq n<10$,

  2. 2.

$R=\left\\{(1,0,0,0,0,0,0,0,0,1)^{\mathsf{T}},(1,1,1,1,1,1,1,1,1,3)^{\mathsf{T}}\right\\}$
for $n=10$,

where $G$ acts on $R$ by left multiplication.

Note that $G$ maps $\partial T_{n}$ to $\partial T_{n}$.

We will begin this section by discussing the structural properties of the
sporadic points of $T_{n}$. Then we use the structural properties of
Pythagorean tuples and sporadic points to prove Theorem 1.2.

###  3.1 Sporadic Points of $\text{SOC}(n)\cap\mathbb{Z}^{n}$

In this section, we will begin by restating the definition of sporadic points
in the case of $\text{SOC}(n)$ and offer two partial characterizations of
sporadic elements of $\text{SOC}(n)$.

###### Definition 5

We call a point $\mathbf{s}\in T_{n}$ sporadic if there is no integral point
$\mathbf{p}$ such that $\langle\mathbf{p},\mathbf{p}\rangle=0$ and
$\mathbf{s}-\mathbf{p}\in T_{n}$.

Just as the group $G$ takes elements of $\partial T_{n}$ to $\partial T_{n}$,
the group $G$ will take sporadic elements to sporadic elements. This closure
ensures that our action by $G$ on the semigroup $T_{n}$ is well-defined.

###### Lemma 5

Let $\mathbf{s}\in T_{n}$.

  1. 1.

Then, $A_{n}^{+}\mathbf{s}$ and $(A_{n}^{+})^{-1}\mathbf{s}$ are both in
$T_{n}$.

  2. 2.

If $\mathbf{s}$ is sporadic, then $A_{n}^{+}\mathbf{s}$ and
$(A_{n}^{+})^{-1}\mathbf{s}$ are both sporadic.

Next, we will provide some Lemmas about the properties of sporadic points
necessary to prove Theorem 1.2. For a detailed exposition of the technical
proofs, please refer to the extended version. Lemmas 6 and 7 show that
sporadic points are close to the boundary, $\partial T_{n}$.

###### Lemma 6

Suppose $\mathbf{s}\in T_{n}$ is a primitive sporadic with nonnegative entries
such that $s_{n}>1$ and $s_{i}\neq 0$ for some $i\in[n-1]$. Then,

$s_{n}=\left\lceil\sqrt{s_{1}^{2}+s_{2}^{2}+\dots+s_{n-1}^{2}}\right\rceil$

###### Lemma 7

Let $\mathbf{s}\in T_{n}$. If $\langle\mathbf{s},\mathbf{s}\rangle=-1$, then
$\mathbf{s}$ is sporadic. When $3\leq n<7$, we also have the converse: if
$\mathbf{s}$ is sporadic, then $\langle\mathbf{s},\mathbf{s}\rangle=-1$.

Inspired by the structure of Pythagorean tuples, we analyze the set of
sporadic points that remain at the same height in $T_{n}$ after multiplication
by $(A_{n}^{+})^{-1}$. Let $(p)_{n}$ denotes the $n^{\text{th}}$ coordinate of
$p$,

###### Lemma 8

Let $n\leq 10$. Suppose $\mathbf{s}\in T_{n}$ is a primitive sporadic such
that $s_{1}\geq\dots\geq s_{n-1}\geq 0$ and $s_{n}>1$. The following list of
tuples are the only such $\mathbf{s}$ where
$((A_{n}^{+})^{-1}\mathbf{s})_{n}=s_{n}$.

  * •

For $n=7$, we have the following tuple: $(1,1,1,1,1,1,3)$.

  * •

For $n=8$, we have the following tuples: $(1,1,1,1,1,1,1,3)$,
$(1,1,1,1,1,1,0,3)$.

  * •

For $n=9$, we have the following tuples:

$\displaystyle(1,1,1,1,1,1,1,1,3),(1,1,1,1,1,1,1,0,3),(1,1,1,1,1,1,0,0,3),(2,2,2,2,2,2,2,1,6).$

  * •

For $n=10$, we have the following tuples:

$\displaystyle(1,1,1,1,1,1,1,1,0,3),$ $\displaystyle\hskip
8.53581pt(1,1,1,1,1,1,1,0,0,3),$ $\displaystyle\hskip
8.53581pt(1,1,1,1,1,1,0,0,0,3),$ $\displaystyle(2,2,2,2,2,2,2,2,1,6),$
$\displaystyle\hskip 8.53581pt(2,2,2,2,2,2,2,1,0,6).$

Then we show that besides the points listed in Lemma 8, every other sporadic
points will reduce to a strictly lower height after multiplication by
$(A_{n}^{+})^{-1}$.

###### Lemma 9

Let $\mathbf{s}\in T_{n}$ be sporadic with nonnegative entries such that
$s_{1}\geq s_{2}\geq\dots\geq s_{n-1}$, $s_{1}\geq 1$ and $3\leq n\leq 10$.
For $s$ not listed in Lemma 8,

$((A_{n}^{+})^{-1}\mathbf{s})_{n}<(\mathbf{s})_{n}.$

###### Proof

This is equivalent to showing that $-s_{1}-s_{2}-s_{3}+2s_{n}<s_{n}$, or
rather $s_{n}<s_{1}+s_{2}+s_{3}.$ The case of $n=3$ reduces to the inequality
$s_{3}<s_{1}+s_{2}$. By Lemma 6, we have that

$\displaystyle s_{n}$
$\displaystyle=\bigg{\lceil}\sqrt{s_{1}^{2}+s_{2}^{2}+\dots+s_{n-1}^{2}}\bigg{\rceil}$
$\displaystyle\leq\bigg{\lceil}\sqrt{s_{1}^{2}+s_{2}^{2}+s_{3}^{2}+2s_{1}s_{2}+2s_{1}s_{3}+2s_{2}s_{3}}\bigg{\rceil}$
(3)
$\displaystyle=\bigg{\lceil}\sqrt{(s_{1}+s_{2}+s_{3})^{2}}\bigg{\rceil}=s_{1}+s_{2}+s_{3},$

where the inequality follows from the order $s_{1}s_{2}\geq s_{1}s_{3}\geq
s_{2}s_{3}\geq s_{4}^{2}\geq...\geq s_{n-1}^{2}$ and $n\leq 10$. As $s$ is not
one of the tuples listed in Lemma 8, the inequality (3) can be made strict.
Therefore, $s_{n}<s_{1}+s_{2}+s_{3}$, which implies that
$(A_{n}^{+})^{-1}\mathbf{s}$ sits at a strictly lower height in the cone than
$\mathbf{s}$. ∎

###  3.2 Proof of Theorem 1.2

We now present a complete formulation of Theorem 1.2 followed by its proof.

###### Theorem 3.1

For dimension $3\leq n\leq 10$, the conical semigroup
$\mathrm{SOC}(n)\cap\mathbb{Z}^{n}$ is $(R,G)$-finitely generated by

$G=\left\langle A_{n}^{+},Q_{1},\dots,Q_{n-1},P_{1,2},P_{1,3},\dots
P_{1,n-1}\right\rangle$

and a finite set $R$. More specifically,

  1. 1.

If $3\leq n\leq 6$, then
$R=\left\\{(1,0,\dots,0,1)^{\mathsf{T}},(0,\dots,0,1)^{\mathsf{T}}\right\\}$.

  2. 2.

If $n=7$, then

$R=\left\\{(1,0,0,0,0,0,1)^{\mathsf{T}},(0,0,0,0,0,0,1)^{\mathsf{T}},(1,1,1,1,1,1,3)^{\mathsf{T}}\right\\}.$

  3. 3.

If $n=8$, then

$\displaystyle
R=\Big{\\{}(1,0,0,0,0,0,0,1)^{\mathsf{T}},(0,0,0,0,0,0,0,1)^{\mathsf{T}},(1,1,1,1,1,1,1,3)^{\mathsf{T}},(1,1,1,1,1,1,0,3)^{\mathsf{T}}\Big{\\}}.$

  4. 4.

If $n=9$, then

$\displaystyle R=\Big{\\{}$
$\displaystyle(1,0,0,0,0,0,0,0,1)^{\mathsf{T}},(0,0,0,0,0,0,0,0,1)^{\mathsf{T}},(1,1,1,1,1,1,1,1,3)^{\mathsf{T}},$
$\displaystyle(1,1,1,1,1,1,1,0,3)^{\mathsf{T}},(1,1,1,1,1,1,0,0,3)^{\mathsf{T}},(2,2,2,2,2,2,2,1,6)^{\mathsf{T}}\Big{\\}}.$

  5. 5.

If $n=10$, then

$\displaystyle
R=\Big{\\{}(1,0,0,0,0,0,0,0,0,1)^{\mathsf{T}},(1,1,1,1,1,1,1,1,1,3)^{\mathsf{T}},(0,0,0,0,0,0,0,0,0,1)^{\mathsf{T}},$
$\displaystyle(1,1,1,1,1,1,1,1,0,3)^{\mathsf{T}},(1,1,1,1,1,1,1,0,0,3)^{\mathsf{T}},(1,1,1,1,1,1,0,0,0,3)^{\mathsf{T}},$
$\displaystyle(2,2,2,2,2,2,2,2,1,6)^{\mathsf{T}},(2,2,2,2,2,2,2,1,0,6)^{\mathsf{T}}\Big{\\}}.$

###### Proof

This follows directly from Lemma 9 and that fact that $(0,0,\dots,0,1)$ is the
sporadic of minimal height in this cone. Let $\mathbf{s}\in T_{n}$. If
$\mathbf{s}$ is not sporadic, we can represent it as

$\displaystyle\mathbf{s}=\lambda_{1}\mathbf{p}_{1}+\lambda_{2}\mathbf{p}_{2}+\dots+\lambda_{k}\mathbf{p}_{k}+\lambda\mathbf{p}$
(4)

where $\lambda,\lambda_{i}\in\mathbb{Z}_{\geq 0}$, each $\mathbf{p}_{i}$ is a
primitive Pythagorean tuple and $\mathbf{p}$ is sporadic. By Lemma 4, each
$\mathbf{p}_{i}$ can be decomposed as
$\mathbf{p}_{i}=G_{i}(1,0,\dots,0,1)^{\mathsf{T}}$ when $3\leq n<10$ or
$\mathbf{p}_{i}=G_{i}(1,0,\dots,0,1)^{\mathsf{T}}+\tilde{G_{i}}(1,1,\dots,1,3)^{\mathsf{T}}$
when $n=10$ where each $G_{i},\tilde{G_{i}}\in G$. It remains to consider the
sporadic $\mathbf{p}$. Given any primitive sporadic tuple $\mathbf{s}$, we can
recover an element of $R$ as follows:

  1. 1.

Multiply $\mathbf{p}$ by the appropriate permutation matrices $P_{i,j}$ and
sign changing matrices $Q_{j}$ so that $\mathbf{p}$ has nonnegative entries
and $p_{1}\geq\dots\geq p_{n-1}$. Call this resulting vector
$\mathbf{p}^{\prime}$.

  2. 2.

Multiply $\mathbf{p}^{\prime}$ by $(A_{n}^{+})^{-1}$ and repeat step 1 as
necessary. By Lemma 9, the height of the resulting vector will be strictly
lower then that of the vector we started with or the resulting vector will
belong to $R$.

  3. 3.

Repeat step 2 until the resulting vector $\mathbf{r}$ belongs to $R$. By Lemma
8, the only possibilities for the resulting vector belong to $R$.

This process gives the equality $\mathbf{r}=G_{1}\dots G_{k}\mathbf{p}$. If we
let $G^{\prime}=G_{1}\dots G_{k}$, then we have
$(G^{\prime})^{-1}\mathbf{r}=\mathbf{p}$. Therefore, for $3\leq n\leq 10$, the
conical semigroup $\text{SOC}(n)$ is $(R,G)$-finitely generated by the claimed
$R$ and $G$. ∎

When $n=9$, the primitive sporadic point $(2,2,2,2,2,2,2,1,6)$ can be written
as the sum of two sporadic points with smaller heights:

$(2,2,2,2,2,2,2,1,6)=(1,1,1,1,1,1,1,0,3)+(1,1,1,1,1,1,0,0,3).$

We can similarly decompose $(2,2,2,2,2,2,2,2,1,6)$ and $(2,2,2,2,2,2,2,1,0,6)$
for $n=10$. In this sense, these sporadic points fail to be minimal. Thus, if
we remove them from the set of roots $R$, our semigroup $S$ remains
$(R,G)$-finitely generated. However, when we remove these point from our root
sets, our decomposition in equality (4) requires modification and we must
allow for multiple sporadic points in the expression.

###### Remark 2

Lastly, it is worth noting that inequality (3) would fail in dimensions larger
than 10. Thus, this line of argumentation would fail to produce results for
$n>10$.

## References

  * [1] Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Weismantel, R.: The support of integer optimal solutions. SIAM J. Optim. 28(3), 2152–2157 (2018)
  * [2] Aliev, I., Averkov, G., De Loera, J.A., Oertel, T.: Sparse representation of vectors in lattices and semigroups. Math. Program. 192(1-2), 519–546 (2022)
  * [3] Aliev, I., De Loera, J.A., Oertel, T., O’Neill, C.: Sparse solutions of linear Diophantine equations. SIAM J. Appl. Algebra Geom. 1(1), 239–253 (2017)
  * [4] Barvinok, A.: A course in convexity, vol. 54. American Mathematical Soc. (2002)
  * [5] Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM (2001)
  * [6] Berndt, S., Brinkop, H., Jansen, K., Mnich, M., Stamm, T.: New support size bounds for integer programming, applied to makespan minimization on uniformly related machines. ArXiv:2305.08432 (2023)
  * [7] de Carli Silva, M.K., Tuncel, L.: A notion of total dual integrality for convex, semidefinite, and extended formulations. SIAM Journal on Discrete Mathematics 34(1), 470–496 (2020)
  * [8] Cass, D., Arpaia, P.J.: Matrix generation of Pythagorean n-tuples. Proceedings of the American Mathematical Society 109(1), 1–7 (1990)
  * [9] Charnes, A., Cooper, W.W., Kortanek, K.: Duality in semi-infinite programs and some works of Haar and Carathéodory. Management Science 9(2), 209–228 (1963)
  * [10] Cook, W., Fonlupt, J., Schrijver, A.: An integer analogue of Caratheodory’s theorem. Journal of Combinatorial Theory, Series B 40(1), 63–70 (1986)
  * [11] De Loera, J., Hemmecke, R., Köppe, M.: Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics (2013)
  * [12] Edmonds, J., Giles, R.: Total dual integrality of linear inequality systems. In: Progress in combinatorial optimization, pp. 117–129. Elsevier (1984)
  * [13] Giles, F.R., Pulleyblank, W.R.: Total dual integrality and integer polyhedra. Linear algebra and its applications 25, 191–196 (1979)
  * [14] Kaveh, K., Khovanskii, A.G.: Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory. Ann. of Math. (2) 176(2), 925–978 (2012)
  * [15] Ko, C.: On the decomposition of quadratic forms in six variables (dedicated to professor LJ Mordell on his fiftieth birthday). Acta Arithmetica 3(1), 64–78 (1939)
  * [16] Letchford, A.N., Sørensen, M.M.: Binary positive semidefinite matrices and associated integer polytopes. Mathematical Programming 131(1-2), 253–271 (Feb 2012)
  * [17] de Meijer, F., Sotirov, R.: The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization. ArXiv:2201.10224 (2022)
  * [18] de Meijer, F., Sotirov, R.: On integrality in semidefinite programming for discrete optimization. ArXiv:2306.09865 (2023)
  * [19] Mordell, L.J.: The representation of a definite quadratic form as a sum of two others. The Annals of Mathematics 38(4), 751 (Oct 1937)
  * [20] Schrijver, A.: Theory of Linear and Integer Programming. Wiley Series in Discrete Mathematics & Optimization, Wiley (1998)
  * [21] Schürmann, A.: Computational geometry of positive definite quadratic forms: polyhedral reduction theories, algorithms, and applications, vol. 48. American Mathematical Soc. (2009)
  * [22] Sebö, A.: Hilbert bases, Caratheodory’s theorem and combinatorial optimization. In: Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference. pp. 431–455 (1990)
  * [23] Trott, S.M.: A pair of generators for the unimodular group. Canadian Mathematical Bulletin 5(3), 245–252 (1962)