# New Bounds for the Integer Carathéodory Rank

Iskander Aliev  Cardiff University, United Kingdom  Martin Henk  Technische
Universität Berlin, Germany  Mark Hogan  Cardiff University, United Kingdom
Stefan Kuhlmann  Technische Universität Berlin, Germany  Timm Oertel
Friedrich-Alexander-Universität Erlangen-Nünrberg, Germany

Abstract. Given a rational pointed $n$-dimensional cone $C$, we study the
integer Carathéodory rank $\operatorname{CR}(C)$ and its asymptotic form
$\operatorname{CR^{\rm a}}(C)$, where we consider “most” integer vectors in
the cone. The main result significantly improves the previously known upper
bound for $\operatorname{CR^{\rm a}}(C)$. We also study bounds on
$\operatorname{CR}(C)$ in terms of $\Delta$, the maximal absolute $n\times n$
minor of the matrix given in an integral polyhedral representation of $C$. If
$\Delta\in\\{1,2\\}$, we show $\operatorname{CR}(C)=n$, and prove upper bounds
for simplicial cones, improving the best known upper bound on
$\operatorname{CR}(C)$ for $\Delta\leq n$.

##  1 Introduction

A cone $C$ in $\mathbb{R}^{n}$ is rational if there exists an integer
${m\times n}$ matrix $\bm{A}$ such that

$\displaystyle C=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}\bm{x}\geq\bm{0}\\},$ (1)

where ${\bm{0}}$ is the zero vector and the inequality is componentwise. The
cone $C$ is pointed  if $C\cap(-C)=\\{{\bm{0}}\\}$, that is the origin is the
vertex of $C$, or equivalently, $\bm{A}$ has full column rank. The dimension
of the cone $C$ is the cardinality of a maximal set of linearly independent
vectors in $C$.

Given a finite set
$G=\\{{\bm{g}}_{1},\ldots,{\bm{g}}_{t}\\}\subset\mathbb{Z}^{n}$, the
_semigroup_ $S$ with generating set $G$ is defined as

$S=\\{\lambda_{1}{\bm{g}}_{1}+\cdots+\lambda_{t}{\bm{g}}_{t}:\lambda_{1},\ldots,\lambda_{t}\in\mathbb{Z}_{\geq
0}\\}.$ (2)

Let $C\subset\mathbb{R}^{n}$ be a rational pointed $n$-dimensional cone. The
integer points in the cone $C$ form a semigroup $S=C\cap\mathbb{Z}^{n}$. Due
to a result of van der Corput [27] (see also [22] and [24]), the semigroup $S$
has a uniquely determined inclusion–minimal finite generating set $H=H(C)$.
The set $H$ has been traditionally referred to as the _Hilbert basis_ of $C$.
In the theory of mathematical optimisation, Hilbert bases are strongly related
to Totally Dual Integral (TDI)-systems [25, Chapter 22.3], and Graver bases
[1, 18].

A classical theorem by Carathéodory states that each point of the cone $C$ is
a non-negative combination of at most $n$ vectors which lie on extreme rays of
$C$. Cook, Fonlupt, and Schrijver posed in [13] the following question,
analogous to the one answered by Carathéodory’s theorem:

– What is the smallest $k$ such that every integer point of the cone $C$ can
be expressed as a non-negative integer combination of at most $k$ vectors in
the Hilbert basis $H$?

We will refer to $k$ as the _integer Carathéodory rank_ of $C$, and denote it
by $\operatorname{CR}(C)$. To formally define this quantity, we consider for
any element ${\bm{x}}$ of the semigroup $C\cap\mathbb{Z}^{n}$ its
representation length

$\sigma({\bm{x}})=\min\\{l:{\bm{x}}=\lambda_{1}{\bm{h}}_{1}+\cdots+\lambda_{l}{\bm{h}}_{l},\lambda_{i}\in\mathbb{Z}_{\geq
0},{\bm{h}}_{i}\in H(C)\\}\,.$

Then

$\operatorname{CR}(C)=\max\\{\sigma({\bm{x}}):{\bm{x}}\in
C\cap\mathbb{Z}^{n}\\}\,.$

The paper [13] gave the upper bound $\operatorname{CR}(C)\leq 2n-1$ which was,
subsequently, applied in the context of TDI-systems, integer rounding property
of integer programs, independent sets of _matroids_ , and coverings of perfect
graphs. The current best known upper bound

$\operatorname{CR}(C)\leq 2n-2$ (3)

was obtained by Sebő in [26]. We also remark that the notion of the integer
Carathéodory rank was extended by Eisenbrand and Shmonin [15] to general
semigroups $S$ of the form (2). See also [2, 3] and references within.

Following the work of Bruns and Gubeladze [8], we say that a pointed rational
$n$-dimensional cone $C\subset\mathbb{R}^{n}$ satisfies the _Integral
Carathéodory Property_ (ICP) if $\operatorname{CR}(C)=n$. It was conjectured
in [26] that the ICP holds for every $n$-dimensional cone $C$. This conjecture
was disproved by Bruns et al. in [9]. Specifically, it was shown in [9] that
in every dimension $n\geq 6$ there exists an $n$-dimensional cone $C$ with
$\operatorname{CR}(C)\geq\left\lfloor 7n/6\right\rfloor$.

To study the “typical” maximal representation length, Bruns and Gubeladze
introduced in [8] the _asymptotic integer Carathéodory rank
$\operatorname{CR^{\rm a}}(C)$_ of the cone $C$, which is defined as the
smallest positive integer $k$ such that the following limit exists and
satisfies the equality

$\lim_{\delta\rightarrow\infty}\frac{|\\{{\bm{x}}\in S:\sigma({\bm{x}})\leq
k\\}\cap[-\delta,\delta]^{n}|}{|S\cap[-\delta,\delta]^{n}|}=1\,.$

That is “most” vectors in $C\cap\mathbb{Z}^{n}$ can be represented by at most
$k$ Hilbert basis elements.

Clearly, $\operatorname{CR^{\rm a}}(C)\leq\operatorname{CR}(C)$. It was shown
in [8] that

$\operatorname{CR^{\rm a}}(C)\leq 2n-3\,$ (4)

and that in every dimension $n\geq 6$ there exists an $n$-dimensional cone $C$
with $\operatorname{CR^{\rm a}}(C)>n$.

Known results on the integer Carathéodory rank lead to two interesting and
long–standing open questions:

– What are the optimal upper bounds for $\operatorname{CR}(C)$ and
$\operatorname{CR^{\rm a}}(C)$ in terms of $n$? In the case of
$\operatorname{CR}(C)$, Sebő’s bound (3) remains the best known upper estimate
for over three decades. Further, the work of Gubeladze [20] indicates that
reducing (3) to a bound of the form $\operatorname{CR}(C)\leq(2-\epsilon)n$
with $\epsilon>0$ for all sufficiently large $n$ is a challenging problem. In
particular, it would disprove a conjecture ([20, Conjecture 2.1]) on the
integer Carathéodory rank of normal polytopes.

In this paper, we study the above question in the case of the asymptotic
integer Carathéodory rank. Theorem 1 reduces the bound (4) to
$\operatorname{CR^{\rm a}}(C)\leq\lfloor 3n/2\rfloor$. On the other hand,
Theorem 2 shows that in every dimension $n\geq 6$ there exists an
$n$-dimensional cone $C$ with $\operatorname{CR^{\rm a}}(C)\geq\lfloor
7n/6\rfloor$.

– What cones have the integer Carathéodory property? Cook, Fonlupt, and
Schrijver [13] observed that the ICP holds for two-dimensional cones.
Subsequently, Sebő [26] proved the ICP for cones of dimension three. On the
other hand, due to the result of Bruns et al. [9], there exist cones that do
not satisfy the ICP for every $n\geq 6$. Despite this, it remains an active
line of research to classify which cones admit the ICP; see [14, 17] for some
results concerning cones related to matroids. We continue this line of
research by investigating the integer Carathéodory rank in terms of the
parameter

$\displaystyle\Delta(\bm{A})=\max\left\\{\left|\det\bm{B}\right|:\bm{B}\text{
is an }n\times n\text{ submatrix of }\bm{A}\right\\},$

where $\bm{A}\in\mathbb{Z}^{m\times n}$ has full column rank. We refer to
$\bm{A}$ as $\Delta$-modular if $\Delta(\bm{A})=\Delta$.

Recently, significant effort has been made to understand the computational
complexity of integer programming problems defined by $\Delta$-modular
matrices. Three key results in this area are given in [4, 16, 23]. This task
motivated the study of polyhedral geometry depending on the parameter
$\Delta(\bm{A})$; see [6, 10, 11, 21] for an incomplete collection of results
concerning the distance of optimal integral solutions of an integer linear
program and optimal vertex solutions of the corresponding relaxation, the
lattice width of lattice-free polyhedra, and the diameter of polyhedra. In
some of the recent advancements, in particular [11, 21], Hilbert bases play a
central role when proving novel upper bounds which solely depend on
$\Delta(\bm{A})$.

An intriguing special case are _simplicial cones_ , that means cones, where
$\bm{A}\in\mathbb{Z}^{n\times n}$ in (1) satisfies $\det\bm{A}\neq 0$. Even
for simplicial cones it is open whether they admit the ICP. An affirmative
answer to this has, combined with some extra effort, the following strong
implication: the integer vectors contained in the zonotope spanned by the
primitive generators of a non-simplicial cone have the ICP. In addition to
this, the study of simplicial cones and the ICP relates to various other
concepts in mathematics such as simplices with the integer decomposition
property which themselves are connected to weighted projective spaces; see for
instance [7, 12].

In this paper, we consider the above question of which cones admit the ICP
independently from the dimension of the cone. Theorem 3 shows that the ICP
holds in arbitrary dimension for cones with $\Delta(\bm{A})\in\\{1,2\\}$. We
further strengthen this for simplicial cones and obtain an improvement on the
bound (3) if $\Delta(\bm{A})\leq n$; see Theorem 4.

In what follows, by $\operatorname{int}X$ we denote the interior of a set $X$,
$\operatorname{lin}X$ is the linear hull of $X$, $\operatorname{pos}X$ is the
positive hull of $X$, and $\operatorname{aff}X$ is the affine hull of $X$. We
use the notation $[m]$ for the set $\\{1,\ldots,m\\}$. Given
$\bm{A}\in\mathbb{Z}^{m\times n}$, $I\subseteq[m]$, and $J\subseteq[n]$, we
denote by $\bm{A}_{I,J}$ the submatrix of $\bm{A}$ with rows indexed by $I$
and columns indexed by $J$. If $J=[n]$, we write $\bm{A}_{I,\cdot}$ and
similarly $\bm{A}_{\cdot,J}$ when $I=[m]$. In the same manner, given a vector
$\bm{x}\in\mathbb{R}^{n}$ and a set $I\subseteq[n]$, we denote by
$\bm{x}_{I}\in\mathbb{R}^{|I|}$ the vector with coordinates indexed by $I$.
The support of $\bm{x}$ is defined as
$\operatorname{supp}(\bm{x})=\\{i\in[n]:\bm{x}_{\\{i\\}}\neq 0\\}.$ We denote
by $\operatorname{GL}(n,\mathbb{Z})$ the group of all $n\times n$ unimodular
matrices, that is $\bm{A}\in\mathbb{Z}^{n\times n}$ and
$\left|\det\bm{A}\right|=1$. The standard unit vectors in $\mathbb{R}^{n}$ are
denoted by $\bm{e}_{1},\ldots,\bm{e}_{n}$.

##  2 Statement of results

Our main result strengthens the bound (4) obtained by Bruns and Gubeladze [8].

######  Theorem 1.

Let $C$ be a rational pointed $n$-dimensional cone. Then

$\operatorname{CR^{\rm a}}(C)\leq\left\lfloor\tfrac{3}{2}n\right\rfloor.$

The second result gives a new lower bound for the maximal value of the
asymptotic integer Carathéodory rank of an $n$-dimensional cone.

######  Theorem 2.

For every integer $n\geq 6$ there exists a rational pointed $n$-dimensional
cone $C_{n}$ such that

$\operatorname{CR^{\rm a}}(C_{n})\geq\left\lfloor\tfrac{7}{6}n\right\rfloor.$
(5)

To state our parameterized results, we consider a rational pointed cone

$\displaystyle
C(\bm{A})=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}\bm{x}\geq\bm{0}\\}\,$

and estimate its integer Carathéodory rank in terms of the parameter
$\Delta(\bm{A})$.

Firstly, we show that the ICP holds for the cone $C(\bm{A})$ if all $n\times
n$ subdeterminants of $\bm{A}$ are bounded by two.

######  Theorem 3.

Let $\bm{A}\in\mathbb{Z}^{m\times n}$ be a matrix of full column rank with
$\Delta(\bm{A})\leq 2$. Then $\operatorname{CR}(C(\bm{A}))=n$.

Note that a counterexample for Sebő’s conjecture obtained in [9] has a
polyhedral representation with $\Delta(\bm{A})=144$. The smallest
$2<\Delta(\bm{A})\leq 144$ for which the ICP fails is not known.

Suppose now that $\bm{A}\in\mathbb{Z}^{n\times n}$ is a nonsingular matrix.
Then $C(\bm{A})$ is a simplicial cone and
$\Delta(\bm{A})=\left|\det\bm{A}\right|$. In this setting, we obtain an upper
bound for $\operatorname{CR}(C(\bm{A}))$ which combines the parameter
$\Delta(\bm{A})$ with the dimension $n$. This results in an improvement on the
bound (3) for $\Delta(\bm{A})\leq n$.

######  Theorem 4.

Let $\bm{A}\in\mathbb{Z}^{n\times n}$ be a nonsingular matrix.

  * (i)

If $1\leq\Delta(\bm{A})\leq 4$, then $\operatorname{CR}(C(\bm{A}))=n$.

  * (ii)

If $\Delta(\bm{A})\geq 5$, then $\operatorname{CR}(C(\bm{A}))\leq
n+\Delta(\bm{A})-3$.

##  3 Proofs of Theorem 1 and 2

###  3.1 Proof of Theorem 1

To prove the upper bound for the asymptotic integer Carathéodory rank
$\operatorname{CR^{\rm a}}(C)$, it is sufficient to construct a set
$D\subseteq C\cap\mathbb{Z}^{n}$ that satisfies the following two properties.

  1. (i)

For any point ${\bm{b}}\in D$ we have $\sigma({\bm{b}})\leq 3n/2$.

  2. (ii)

We have

$\lim_{\delta\to\infty}\frac{\left|D\cap[-\delta,\delta]^{n}\right|}{\left|C\cap\mathbb{Z}^{n}\cap[-\delta,\delta]^{n}\right|}=1\,.$

Let us take the Hilbert basis $H(C)=\\{\bm{h}_{1},\ldots,\bm{h}_{t}\\}$ of the
cone $C$ and consider the matrix $\bm{H}\in\mathbb{Z}^{n\times t}$ with
columns $\bm{h}_{1},\ldots,\bm{h}_{t}$. Let further

$\Delta=\max\left\\{\left|\det\bm{H}_{\cdot,I}\right|\;:\;I\subseteq[t],\;|I|=n\right\\}.$

We consider the set

$D=C\cap\mathbb{Z}^{n}\setminus\bigcup_{\tau\in{[t]\choose
n-1}}\left\\{\sum_{i=1}^{t}\lambda_{i}\bm{h}_{i}\;:\;\begin{array}[]{l}0\leq\lambda_{i}\,\quad\quad\text{
for all }i\in\tau,\\\ 0\leq\lambda_{i}<\Delta\text{ for all
}i\in[t]\setminus\tau\end{array}\right\\}.$

Note that for each $\tau\in{[t]\choose n-1}$ we can write

$\left\\{\sum_{i=1}^{t}\lambda_{i}\bm{h}_{i}\;:\;\begin{array}[]{l}0\leq\lambda_{i}\,\quad\quad\text{
for all }i\in\tau,\\\ 0\leq\lambda_{i}<\Delta\text{ for all
}i\in[t]\setminus\tau\end{array}\right\\}=P+C_{\tau},$

where

$P=\bm{H}\cdot[0,\Delta)^{t}=\\{\bm{H}{\bm{x}}:{\bm{x}}\in[0,\Delta)^{t}\\}$

and

$C_{\tau}=\left\\{\sum_{i\in\tau}\lambda_{i}\bm{h}_{i}\;:\;\lambda_{i}\geq
0\right\\}\,.$

Observe that
$\left|C\cap\mathbb{Z}^{n}\cap[-\delta,\delta]^{n}\right|\in\Theta(\delta^{n})$.
Similarly, for any $\tau\in{[t]\choose n-1}$ it holds that
$\left|(P+C_{\tau})\cap\mathbb{Z}^{n}\cap[-\delta,\delta]^{n}\right|\in\Theta(\delta^{k})$,
where $k=\operatorname{rank}\bm{H}_{\cdot,\tau}\leq|\tau|<n$. It holds

$\frac{\left|D\cap[-\delta,\delta]^{n}\right|}{\left|C\cap\mathbb{Z}^{n}\cap[-\delta,\delta]^{n}\right|}\geq
1-\frac{\sum_{\tau\in{[t]\choose
n-1}}\left|(P+C_{\tau})\cap\mathbb{Z}^{n}\cap[-\delta,\delta]^{n}\right|}{\left|C\cap\mathbb{Z}^{n}\cap[-\delta,\delta]^{n}\right|}.$

The latter ratio tends to zero, as $\delta$ tends to infinity. Hence, $D$
satisfies (ii).

Given $\bm{b}\in\mathbb{Z}^{n}$, we will use the notation $Q(\bm{H},{\bm{b}})$
for the polyhedron

$Q(\bm{H},{\bm{b}})=\\{{\bm{x}}\in\mathbb{R}^{t}_{\geq
0}:\bm{H}{\bm{x}}={\bm{b}}\\}.$

To show that $D$ satisfies (i), it is sufficient to prove that for any
$\bm{b}\in D$, there exists a $\bm{x}\in Q(\bm{H},{\bm{b}})\cap\mathbb{Z}^{t}$
with $|\operatorname{supp}(\bm{x})|\leq 3n/2$. Let us consider the following
linear optimisation problem:

$\max\left\\{x_{1}+\cdots+x_{t}:\bm{x}=(x_{1},\ldots,x_{t})^{\top}\in
Q(\bm{H},\bm{b})\right\\}\,.$ (6)

Since $C$ is pointed and $\bm{b}\in C$, it is clear that (6) is feasible and
bounded. Let ${\bm{\lambda}}$ be an optimal vertex solution for (6). Hence,
${\bm{\lambda}}$ has at most $n$ non-zero entries and, renumbering the
coordinates, we may assume that $\lambda_{n+1}=\ldots=\lambda_{t}=0$.
Furthermore, the condition $\bm{b}\in D$ implies that
$\lambda_{1},\ldots,\lambda_{n}\geq\Delta$.

Note that $\bm{H}_{\cdot,[n]}$ is an optimal basis for (6). A classical result
from the theory of linear programming implies that any vector
$\bm{\alpha}=(\alpha_{1},\ldots,\alpha_{n},0,\ldots,0)^{\top}\in\mathbb{R}^{t}_{\geq
0}$ with $\bm{H}\bm{\alpha}\in\mathbb{Z}^{n}$ is an optimal solution to the
linear optimisation problem $\max_{\bm{x}\in
Q(\bm{H},\bm{H}\bm{\alpha})}(x_{1}+\cdots+x_{t})$, see for example [5, Section
5.1].

Let
$\bm{\mu}=(\lambda_{1}-\lfloor\lambda_{1}\rfloor,\ldots,\lambda_{n}-\lfloor\lambda_{n}\rfloor)^{\top}$.
Consider the vector ${\bm{r}}=\bm{H}_{\cdot,[n]}\bm{\mu}\in
C\cap\mathbb{Z}^{n}$. We can write
${\bm{r}}=\sum_{i=1}^{t}\beta_{i}\bm{h}_{i}$ with
$\beta_{i}\in\mathbb{Z}_{\geq 0}$. Hence,

$\bm{b}=\sum_{i=1}^{n}\lfloor\lambda_{i}\rfloor\bm{h}_{i}+\sum_{i=1}^{t}\beta_{i}\bm{h}_{i}.$

Observe that ${\bm{\beta}}=(\beta_{1},\ldots,\beta_{t})^{\top}\in
Q(\bm{H},\bm{r})$ by construction and that the linear optimisation problem

$\max\\{x_{1}+\cdots+x_{t}:\bm{x}=(x_{1},\ldots,x_{t})^{\top}\in
Q(\bm{H},\bm{r})\\}$

has an optimal vertex solution $(\mu_{1},\ldots,\mu_{n},0,\ldots,0)^{\top}$.
Hence, $\sum_{i=1}^{t}\beta_{i}\leq\sum_{i=1}^{n}\mu_{i}$.

If $\sum_{i=1}^{n}\mu_{i}\leq n/2$, then at most $\lfloor n/2\rfloor$ of the
numbers $\beta_{i}$ can be non-zero and the result follows. To settle the case
$\sum_{i=1}^{n}\mu_{i}>n/2$, we consider the vector
${\bm{\gamma}}=(\lceil\lambda_{1}\rceil-\lambda_{1},\ldots,\lceil\lambda_{n}\rceil-\lambda_{n})^{\top}$.
We have ${\bm{s}}=\bm{H}_{\cdot,[n]}{\bm{\gamma}}\in C\cap\mathbb{Z}^{n}$ and,
consequently, ${\bm{s}}=\sum_{i=1}^{t}\delta_{i}\bm{h}_{i}$ with
$\delta_{i}\in\mathbb{Z}_{\geq 0}$. Observe that
${\bm{\delta}}=(\delta_{1},\ldots,\delta_{t})^{\top}\in Q(\bm{H},{\bm{s}})$
and that the linear optimisation problem

$\max\\{x_{1}+\cdots+x_{t}:\bm{x}=(x_{1},\ldots,x_{t})^{\top}\in
Q(\bm{H},{\bm{s}})\\}$

has an optimal vertex solution
$(\gamma_{1},\ldots,\gamma_{n},0,\ldots,0)^{\top}$. Hence,

$\sum_{i=1}^{t}\delta_{i}\leq\sum_{i=1}^{n}\gamma_{i}<n/2\,$

and, consequently, ${\bm{s}}$ can be expressed as non-negative integer
combination of strictly less than $n/2$ Hilbert basis elements.

Let $q=\left|\det\bm{H}_{\cdot,[n]}\right|\leq\Delta$. Then $q{\bm{\gamma}}$
is integral by Cramer’s rule. Recall that we have $\bm{b}\in D$ and, in
particular, $\lambda_{i}\geq\Delta$ for all $i\in[n]$. Thus, we obtain that

$\eta_{i}=\lambda_{i}-(q-1)\gamma_{i}=(\lambda_{i}+\gamma_{i})-q\gamma_{i}$

are non-negative integers for all $i\in[n]$. Finally, we can express $\bm{b}$
as

$\displaystyle{\bm{b}}$
$\displaystyle=\sum_{i=1}^{n}\lambda_{i}\bm{h}_{i}=\sum_{i=1}^{n}(\eta_{i}+(q-1)\gamma_{i})\bm{h}_{i}$
$\displaystyle=\sum_{i=1}^{n}\eta_{i}\bm{h}_{i}+(q-1){\bm{s}}\,.$

This completes the proof since ${\bm{s}}$ is the non-negative integral
combination of strictly less than $n/2$ Hilbert basis elements. ∎

###  3.2 Proof of Theorem 2

Let $C$ be a pointed rational $n$-dimensional cone in $\mathbb{R}^{n}$.
Theorem 6.1 in [8] implies that if $\operatorname{CR^{\rm a}}(C)=n$, then
$\operatorname{CR}(C)=n$. The counterexample to the integer Carathéodory
conjecture, shown in [9], provides a 6-dimensional cone $C_{6}$ with
$\operatorname{CR}(C_{6})=7$. Hence, by Theorem 6.1, we get the lower bound
$\operatorname{CR^{\rm a}}(C_{6})>6$. Furthermore, the inequality
$\operatorname{CR^{\rm a}}(C_{6})\leq\operatorname{CR}(C_{6})$ implies
$\operatorname{CR^{\rm a}}(C_{6})=7$.

Lemma 4.4 in [8] shows that $\operatorname{CR^{\rm a}}(C\times
C^{\prime})=\operatorname{CR^{\rm a}}(C)+\operatorname{CR^{\rm
a}}(C^{\prime})$. Following the construction in [9] and setting
$C_{n}=\left(\mathop{\mathchoice{\raise-2.20001pt\hbox{\huge$\times$}}{\raise-0.50003pt\hbox{\Large$\times$}}{\hbox{\large$\times$}}{\times}}_{i=1}^{\lfloor
n/6\rfloor}C_{6}\right)\times C^{\prime},$ where $C^{\prime}$ is any pointed,
full-dimensional, rational cone in $\mathbb{R}^{n\bmod 6}$, we obtain a cone
that satisfies (5).∎

##  4 Proofs of Theorems 3 and 4

Throughout this section, we work with the polytope

$\displaystyle
P_{\bm{1}}(\bm{A})=\\{\bm{x}\in\mathbb{R}^{n}:\bm{0}\leq\bm{A}\bm{x}\leq\bm{1}\\},$

where $\bm{1}$ denotes the all-ones vector. Note that $P_{\bm{1}}(\bm{A})$ is
full-dimensional if and only if $C(\bm{A})$ is full-dimensional. Further,
$P_{\bm{1}}(\bm{A})$ is bounded as $\bm{A}$ has full column rank.

When proving Theorem 3 and Theorem 4, we employ the following strategy:
Firstly, we argue that
$P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}\backslash\\{\bm{0}\\}\neq\emptyset$.
Then, given $\bm{z}\in\operatorname{int}C(\bm{A})\cap\mathbb{Z}^{n}$, this
implies the existence of some Hilbert basis element $\bm{h}\in H(C(\bm{A}))$
such that the point $\bm{z}-\lambda\bm{h}$ for some
$\lambda\in\mathbb{Z}_{>0}$ is contained in the boundary of $C(\bm{A})$; see
Lemma 5. Next, we work with our new integer vector $\bm{z}-\lambda\bm{h}$ and
iterate this procedure using Lemma 6 below. Hence, we use at every step
exactly one Hilbert basis element and the dimension of the face of $C(\bm{A})$
which contains the current integer vector in the relative interior decreases
by at least one. Consequently, our strategy results in expressing $\bm{z}$ as
an integer combination of at most $n$ Hilbert basis elements.

We begin by proving the first step, that is, the existence of a Hilbert basis
element $\bm{h}$ from above. By doing so, we exploit a crucial property of
Hilbert basis elements: given $\bm{h}\in H(C)$ and $\bm{y}_{1},\bm{y}_{2}\in
C\cap\mathbb{Z}^{n}$ such that $\bm{h}=\bm{y}_{1}+\bm{y}_{2}$, then either
$\bm{y}_{1}=\bm{0}$ or $\bm{y}_{2}=\bm{0}$; see, e.g., [25, Chapter 16.4] for
some details.

######  Lemma 5.

Let $\bm{A}\in\mathbb{Z}^{m\times n}$ be a full column rank matrix with rows
${\bm{a}}_{1},\ldots,{\bm{a}}_{m}$ such that
$P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}\backslash\\{\bm{0}\\}\neq\emptyset$.
Given $\bm{z}\in\operatorname{int}C(\bm{A})\cap\mathbb{Z}^{n}$, there exists a
Hilbert basis element $\bm{h}\in H(C(\bm{A}))$ and $\lambda\in\mathbb{Z}_{>0}$
such that $\bm{z}-\lambda\bm{h}\in C(\bm{A})$ and
$\bm{a}_{i}^{\top}(\bm{z}-\lambda\bm{h})=0$ for some $i\in[m]$.

###### Proof.

Let $\bm{h}\in P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}\backslash\\{\bm{0}\\}$ be
chosen such that $\left|\operatorname{supp}(\bm{A}\bm{h})\right|$ is minimal
among all vectors in
$P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}\backslash\\{\bm{0}\\}$. We observe that

$\displaystyle\lambda=\min_{i\in\operatorname{supp}(\bm{A}\bm{h})}\bm{a}_{i}^{\top}\bm{z}$

already yields the claim for $\bm{h}$ as $\bm{A}\bm{h}\in\\{0,1\\}^{m}$. So it
suffices to argue that $\bm{h}$ is a Hilbert basis element.

Let $\bm{y}_{1},\bm{y}_{2}\in C(\bm{A})\cap\mathbb{Z}^{n}$ be such that
$\bm{h}=\bm{y}_{1}+\bm{y}_{2}$. It is sufficient to show that one of the
vectors $\bm{y}_{1}$, $\bm{y}_{2}$ is zero. Since
$\bm{A}\bm{h}\in\\{0,1\\}^{m}$, we have $\bm{A}\bm{y}_{i}\in\\{0,1\\}^{m}$ for
$i=1,2$ as well. However, this implies that
$\operatorname{supp}(\bm{A}\bm{y}_{i})\subseteq\operatorname{supp}(\bm{A}\bm{h})$
for $i=1,2$. The minimality of
$\left|\operatorname{supp}(\bm{A}\bm{h})\right|$ implies that either
$\bm{y}_{1}=\bm{0}$ or $\bm{y}_{2}=\bm{0}$. ∎∎

Lemma 5 enables us to argue inductively over the dimension $n$. To make this
precise, we establish in the next result a representation for lower-
dimensional faces and their minors. Let $\bm{A}\in\mathbb{Z}^{m\times n}$ be a
matrix with full column rank and let $\bm{b}\in\mathbb{Z}^{m}$. In what
follows, we consider the polyhedron
$P(\bm{A},\bm{b})=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}\bm{x}\leq\bm{b}\\}$ and
define

$\displaystyle\gcd(\bm{A})=\gcd(\det\bm{A}_{I,\cdot}:I\subseteq[m]\text{ with
}|I|=n)\,.$

For $\bm{A}\in\mathbb{Z}^{m\times n}$ with full row rank, we set
$\gcd(\bm{A})=\gcd(\bm{A}^{\top})$.

######  Lemma 6.

Let $\bm{A}\in\mathbb{Z}^{m\times n}$ be a matrix with full column rank and
$\bm{b}\in\mathbb{Z}^{m}$. Further, let
$F_{I}=P(\bm{A},\bm{b})\cap\left(\bm{v}+\ker\bm{A}_{I,\cdot}\right)$ be a
$(n-k)$-dimensional face of $P(\bm{A},\bm{b})$ with
$\operatorname{aff}F_{I}\cap\mathbb{Z}^{n}\neq\emptyset$, where
$I\subseteq[m]$ with $\left|I\right|=k$ and
$\bm{A}_{I,\cdot}\bm{v}=\bm{b}_{I}$ hold. Then, there exists a unimodular
transformation $\bm{U}\in\operatorname{GL}(n,\mathbb{Z})$ and orthogonal
projection $\pi:\mathbb{R}^{n}\to\mathbb{R}^{n-k}$ with the following
properties:

  * (i)

$\pi\left(\bm{U}\cdot F_{I}\right)$ is a $(n-k)$-dimensional polyhedron that
admits a representation of the form $\pi\left(\bm{U}\cdot
F_{I}\right)=P(\tilde{\bm{A}},\tilde{\bm{b}})$ with an integer vector
$\tilde{\bm{b}}$ and integer matrix $\tilde{\bm{A}}$ which is at most
$\left\lfloor\frac{\Delta(\bm{A})}{\gcd(\bm{A}_{I,\cdot})}\right\rfloor$-modular.

  * (ii)

There exists a one-to-one mapping between $F_{I}\cap\mathbb{Z}^{n}$ and
$\pi\left(\bm{U}\cdot F_{I}\right)\cap\mathbb{Z}^{n-k}$.

###### Proof.

We assume without loss of generality that $I=\\{1,\ldots,k\\}$. There exists a
unimodular transformation $\bm{U}\in\operatorname{GL}(n,\mathbb{Z})$, such
that

$\displaystyle\bm{A}_{I,\cdot}\bm{U}^{-1}=(\bm{H},\bm{0})$

for some invertible matrix $\bm{H}\in\mathbb{Z}^{k\times k}$ that can be
obtained, for instance, by transforming $\bm{A}_{I,\cdot}$ into Hermite normal
form; see [25, Chapter 4] for more information on the Hermite normal form.
Moreover, we have

$\displaystyle\bm{A}\bm{U}^{-1}=\begin{pmatrix}\bm{H}&\bm{0}\\\
\star&\tilde{\bm{A}}\end{pmatrix}$

for some $\tilde{\bm{A}}\in\mathbb{Z}^{(m-k)\times(n-k)}$ with full column
rank.

Let $\pi:\mathbb{R}^{n}\to\mathbb{R}^{n-k}$ denote the orthogonal projection
onto the last $n-k$ coordinates and let $\tilde{\bm{z}}\in\mathbb{R}^{k}$ be
the unique solution of $\bm{H}\bm{x}=\bm{b}_{I}$. Then,

$\displaystyle\pi\left(\bm{U}\cdot
F_{I}\right)=\left\\{\bm{x}\in\mathbb{R}^{n-k}:\tilde{\bm{A}}\bm{x}\leq\bm{b}_{[m]\backslash
I}-\bm{A}_{[m]\backslash I,[k]}\tilde{\bm{z}}\right\\}$ (7)

which is a $(n-k)$-dimensional polyhedron defined by the integral constraint
matrix $\tilde{\bm{A}}$. Let us show that $\tilde{\bm{A}}$ is at most
$\left\lfloor\frac{\Delta(\bm{A})}{\gcd\bm{A}_{I,\cdot}}\right\rfloor$-modular.
For that purpose, let $\bm{B}$ be a $(n-k)\times(n-k)$ submatrix of
$\tilde{\bm{A}}$. We can extend the matrix to

$\displaystyle\begin{pmatrix}\bm{H}&\bm{0}\\\ \star&\bm{B}\end{pmatrix}$

which is an $n\times n$ submatrix of $\bm{A}\bm{U}^{-1}$ with determinant
$\left|\det\bm{B}\right|\left|\det\bm{H}\right|\leq\Delta(\bm{A})$. We have
$\left|\det\bm{H}\right|=\gcd\bm{A}_{I,\cdot}$ which follows, e.g., from the
Smith normal form; see for instance [25, Chapter 4.4] for a treatment of Smith
normal forms. The latter equality and the integrality of $\tilde{\bm{A}}$
imply that $\tilde{\bm{A}}$ is at most
$\left\lfloor\frac{\Delta(\bm{A})}{\gcd\bm{A}_{I,\cdot}}\right\rfloor$-modular.
Further, the right-hand side of the system in (7) defining $\pi(\bm{U}\cdot
F_{I})$ is given by $\bm{b}_{[m]\backslash I}-\bm{A}_{[m]\backslash
I,[k]}\tilde{\bm{z}}$. To settle property (i), it remains to prove the
integrality of the right-hand side. We claim that $\tilde{\bm{z}}$ has to be
integral. The integrality follows then from the previous mentioned description
of the right-hand side.

Since $\bm{U}$ is unimodular,
$\operatorname{aff}F_{I}\cap\mathbb{Z}^{n}\neq\emptyset$ implies
$\operatorname{aff}(\bm{U}\cdot F_{I})\cap\mathbb{Z}^{n}\neq\emptyset$. Recall
that $\tilde{\bm{z}}\in\mathbb{R}^{k}$ denotes the unique solution of
$\bm{H}\bm{x}=\bm{b}_{I}$. Let $\bm{z}\in\mathbb{R}^{n}$ be the vector
$\tilde{\bm{z}}$ with $n-k$ zeros appended. We have

$\displaystyle\operatorname{aff}(\bm{U}\cdot F_{I})$
$\displaystyle=\bm{z}+\ker\bm{A}_{I,\cdot}\bm{U}^{-1}=\bm{z}+\left\\{\bm{x}\in\mathbb{R}^{n}:\bm{x}_{[k]}=\bm{0}\right\\}$
$\displaystyle=\left\\{\bm{x}\in\mathbb{R}^{n}:\bm{x}_{[k]}=\tilde{\bm{z}}\right\\}.$

Thus, $\operatorname{aff}(\bm{U}\cdot F_{I})\cap\mathbb{Z}^{n}\neq\emptyset$
implies $\tilde{\bm{z}}\in\mathbb{Z}^{k}$. Hence, property (i) follows by the
discussion above. Moreover, we obtain $\bm{y}\in\bm{U}\cdot
F_{I}\cap\mathbb{Z}^{n}$ if and only if $\pi(\bm{y})\in\pi(\bm{U}\cdot
F_{I})\cap\mathbb{Z}^{n-k}$, which settles property (ii). ∎∎

###  4.1 Proof of Theorem 3

In this proof, we refer to $\bm{A}$ as unimodular and bimodular if
$\Delta(\bm{A})=1$ and $\Delta(\bm{A})=2$, respectively.

Suppose first that $\Delta(\bm{A})=1$. We argue inductively on $n$. For $n=1$,
the cone is a ray and, thus, the statement immediately holds. Let $n>1$ and
$\bm{z}\in C(\bm{A})\cap\mathbb{Z}^{n}$. If $\bm{z}$ lies on the boundary of
$C(\bm{A})$, we restrict to the face which contains $\bm{z}$ in the relative
interior and apply Lemma 6 with respect to that face. This results in a lower-
dimensional cone with unimodular constraint matrix and the statement of the
theorem follows by induction.

We may now assume $\bm{z}\in\operatorname{int}C(\bm{A})\cap\mathbb{Z}^{n}$,
which implies that $C(\bm{A})$ is a full-dimensional cone. Since
$P_{\bm{1}}(\bm{A})$ is defined by a unimodular matrix with integral right-
hand side, every vertex of $P_{\bm{1}}(\bm{A})$ is integral. There are at
least two vertices as $n\geq 2$. Hence, the polytope $P_{\bm{1}}(\bm{A})$
contains a non-zero integral vector. Using Lemmas 5 and 6, the statement of
the theorem follows by induction.

Suppose now that $\Delta(\bm{A})=2$. In this case, our proof crucially relies
on an integer feasibility result due to Veselov and Chirkov:

######  Theorem 7.

[28, Theorem 1] Let $\bm{A}\in\mathbb{Z}^{m\times n}$ be bimodular and
$\bm{b}\in\mathbb{Z}^{m}$ such that $P(\bm{A},\bm{b})$ is full-dimensional.
Then $P(\bm{A},\bm{b})\cap\mathbb{Z}^{n}\neq\emptyset$.

We argue again inductively over $n$. Similarly to the $\Delta(\bm{A})=1$ case,
we may assume that $n>1$ and
$\bm{z}\in\operatorname{int}C(\bm{A})\cap\mathbb{Z}^{n}$. Furthermore, we
assume that every row of $\bm{A}$ defines a facet of $C(\bm{A})$. If this is
not the case, we remove rows of $\bm{A}$ which do not correspond to a facet of
$C(\bm{A})$. This operation does not increase $\Delta(\bm{A})$.

As before, our first goal is to show that $P_{\bm{1}}(\bm{A})$ contains a non-
zero integer vector. Let $F_{\bm{a}}=\\{\bm{x}\in
P_{\bm{1}}(\bm{A}):\bm{a}^{\top}\bm{x}=1\\}$ define a facet of
$P_{\bm{1}}(\bm{A})$ for some row $\bm{a}$ of $\bm{A}$. In what follows, we
distinguish between the cases $\gcd(\bm{a})=1$ and $\gcd(\bm{a})=2$. Note that
$\gcd(\bm{a})\geq 3$ is not possible as it violates the assumption that
$\bm{A}$ is bimodular.

Let $\gcd(\bm{a})=1$. This implies that the affine hull of the facet
$F_{\bm{a}}$ contains integer vectors. Applying Lemma 6, we receive a full-
dimensional polytope in $(n-1)$-dimensional ambient space which is bimodular.
Hence, it contains an integer vector by Theorem 7. Since the right-hand side
equals one, this vector cannot be $\bm{0}$.

Let $\gcd(\bm{a})=2$. Every row of $\bm{A}$ is facet defining for $C(\bm{A})$
as we assumed in the beginning of the proof. Therefore, there exists a facet
of $P_{\bm{1}}(\bm{A})$ defined by $\bm{a}^{\top}\bm{x}=0$. By Lemma 6, the
facet defined by $\bm{a}$ corresponds to a polytope with unimodular constraint
matrix and integral right-hand side. As the linear hull of the facet contains
integral vectors, every non-zero vertex is integral. There are at least two
vertices since $n\geq 2$. So there exists a non-zero integer vector in the
facet.

Using Lemmas 5 and 6, the statement of the theorem follows by induction. ∎

###  4.2 Proof of Theorem 4

Recall that $\bm{A}\in\mathbb{Z}^{n\times n}$ is a nonsingular matrix and,
thus, $\Delta(\bm{A})=\left|\det\bm{A}\right|$. In this manner, we write
$\left|\det\bm{A}\right|$ instead of $\Delta(\bm{A})$ throughout the proof. We
will need the auxiliary result below. The proof is based on the theory of
lattices; see [19] for an introduction to lattices.

######  Lemma 8.

Suppose that $n\geq\left|\det\bm{A}\right|$. Then the parallelepiped
$P_{\bm{1}}(\bm{A})=\\{\bm{x}\in\mathbb{R}^{n}:\bm{0}\leq\bm{A}\bm{x}\leq\bm{1}\\}$
contains a non-zero integer vector.

###### Proof.

Suppose that the matrix $\bm{A}^{-1}$ has columns
$\bm{w}_{1},\ldots,\bm{w}_{n}$ and let $\Lambda=\bm{A}^{-1}\mathbb{Z}^{n}$.
Then $\bm{w}_{i}\in\Lambda$ for each $i\in[n]$. Note that
$\bm{A}\bm{w}_{i}=\bm{e}_{i}$ and hence
$\bm{w}_{1},\bm{w}_{1}+\bm{w}_{2},\ldots,\bm{w}_{1}+\cdots+\bm{w}_{n}\in
P_{\bm{1}}(\bm{A})\cap\Lambda$. We analyse these sums with respect to the
cosets of the finite abelian group $\Lambda/\mathbb{Z}^{n}$. Note that
$\left|\Lambda/\mathbb{Z}^{n}\right|=\left|\det\bm{A}\right|$ since
$\det\Lambda=\left|\det\bm{A}\right|^{-1}$. As $n\geq\left|\det\bm{A}\right|$,
either one of the sums is integral or two sums, say
$\bm{w}_{1}+\cdots+\bm{w}_{p}$ and $\bm{w}_{1}+\cdots+\bm{w}_{q}$ for $p<q$,
are contained in the same coset of $\Lambda/\mathbb{Z}^{n}$ by the pigeonhole
principle. This implies that $\bm{w}_{p+1}+\cdots+\bm{w}_{q}\in
P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}$. ∎∎

Suppose first that $1\leq\left|\det\bm{A}\right|\leq 4$ and take any integer
point ${\bm{z}}$ in $C(\bm{A})$. By Lemma 6, we may assume that $C(\bm{A})$ is
full-dimensional and that
$\bm{z}\in\operatorname{int}C(\bm{A})\cap\mathbb{Z}^{n}$. Since every cone of
dimension at most three has the ICP [26, Theorem 2.2], we suppose that $n\geq
4$. Thus, we get $n\geq 4\geq\left|\det\bm{A}\right|$. As
$n\geq\left|\det\bm{A}\right|$, Lemma 8 gives
$P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}\backslash\\{\bm{0}\\}\neq\emptyset$.
Applying Lemmas 5 and 6 we replace ${\bm{z}}$ with an integer point in a
lower-dimensional cone whose constraint matrix is at most
$\left|\det\bm{A}\right|$-modular. We repeat this procedure until the
dimension is at most $\left|\det\bm{A}\right|-1$. For each iteration, we use
exactly one Hilbert basis element and the number of iterations is at most
$n-(\left|\det\bm{A}\right|-1)$. Next, we apply again the result of [26]
stating that the ICP holds for cones in dimension
$3\geq\left|\det\bm{A}\right|-1$. Thus, we obtain an expression of ${\bm{z}}$
as an integer combination of at most $n$ elements of $H(C(\bm{A}))$.

Suppose now that $\left|\det\bm{A}\right|\geq 5$ and take any integer point
${\bm{z}}$ in $C(\bm{A})$. Observe that the case
$n-1\leq\left|\det\bm{A}\right|$ follows from (3). Hence, we may assume
$n\geq\left|\det\bm{A}\right|$. Therefore, using Lemma 8 and then Lemmas 5 and
6 as above, we can replace ${\bm{z}}$ with an integer point in a lower-
dimensional cone which is at most $\left|\det\bm{A}\right|$-modular. We repeat
this procedure until the dimension is at most $\left|\det\bm{A}\right|-1$. As
$\left|\det\bm{A}\right|-1\geq 2$, we can apply Sebő’s bound, (3), and get at
most $2\left(\left|\det\bm{A}\right|-1\right)-2$ Hilbert basis elements in an
integral combination. Together with our previous steps, which give us at most
$n-(\left|\det\bm{A}\right|-1)$ Hilbert basis elements in an integral
combination, we obtain an expression of ${\bm{z}}$ as a non-negative integer
combination of at most

$\displaystyle
2\left(\left|\det\bm{A}\right|-1\right)-2+\left(n-\left(\left|\det\bm{A}\right|-1\right)\right)=n+\left|\det\bm{A}\right|-3$

elements of $H(C(\bm{A}))$.∎

Remark: We highlight the limitation of our approach: Given an integer vector
${\bm{z}}\in C(\bm{A})$, the strategy of searching for an element $\bm{h}\in
H(C(\bm{A}))$ such that for some integer $\lambda$ the vector
${\bm{z}}-\lambda\bm{h}$ reaches a lower-dimensional face of the cone
$C(\bm{A})$ is limited to the case $\Delta(\bm{A})\leq{2}$. This already fails
for the well-understood case when $\Delta(\bm{A})=3$ and $n=2$, which, in
light of our previous discussion, could be considered the natural next step
towards a possible extension of the method. An instance illustrating this
deficiency is given by $C(\bm{A})$ with

$\displaystyle\bm{A}=\begin{pmatrix}1&0\\\ 2&3\end{pmatrix}$

and ${\bm{z}}=(7,-3)^{\top}\in C(\bm{A})\cap\mathbb{Z}^{n}$. Then
$\Delta(\bm{A})=\det\bm{A}=3$ and the Hilbert basis elements of $C(\bm{A})$ is
given by the vectors $\bm{e}_{1},\bm{e}_{2}$, $(2,-1)^{\top}$, and
$(3,-2)^{\top}$. One can check that
$P_{\bm{1}}(\bm{A})\cap\mathbb{Z}^{n}=\\{\bm{0}\\}$ and no Hilbert basis
element has the desired property. So already in this comparably simple case
the method of reducing to lower-dimensional faces of the cone fails.

## References

  * [1] K. Aardal, R. Weismantel, and L.A. Wolsey.  Non-standard approaches to integer programming.  volume 123, pages 5–74. 2002.  Workshop on Discrete Optimization, DO’99 (Piscataway, NJ).
  * [2] I. Aliev, G. Averkov, J. de Loera, and T. Oertel.  Sparse representation of vectors in lattices and semigroups.  Mathematical Programming, 192, 05 2021.
  * [3] I. Aliev, J. De Loera, T. Oertel, and C. O’Neill.  Sparse solutions of linear diophantine equations.  SIAM Journal on Applied Algebra and Geometry, 1:239–253, 2017.
  * [4] S. Artmann, R. Weismantel, and R. Zenklusen.  A strongly polynomial algorithm for bimodular integer linear programming.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206–1219, 2017.
  * [5] D. Bertsimas and J.N. Tsitsiklis.  Introduction to linear optimization.  Athena Scientific, 1997.
  * [6] N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier.  On sub-determinants and the diameter of polyhedra.  Discrete and Computational Geometry, 52:102–115, 2014.
  * [7] B. Braun, R. Davis, and L. Solus.  Detecting the integer decomposition property and ehrhart unimodality in reflexive simplices.  Advances in Applied Mathematics, 100:122–142, 2018.
  * [8] W. Bruns and J. Gubeladze.  Normality and covering properties of affine semigroups.  J. Reine Angew. Mathematik, 510:151–178, 1999.
  * [9] W. Bruns, J. Gubeladze, M. Henk, A. Martin, and R. Weismantel.  A counterexample to an integer analogue of Carathéodory’s theorem.  Journal für reine und angewandte Mathematik, 510:179–185, 1999\.
  * [10] M. Celaya, S. Kuhlmann, J. Paat, and R. Weismantel.  Improving the Cook et al. proximity bound given integral valued constraints.  In Integer Programming Combinatorial Optimization: 23rd International Conference, pages 84–97, 2022.
  * [11] M. Celaya, S. Kuhlmann, J. Paat, and R. Weismantel.  Proximity and flatness bounds for integer linear optimization.  http://arxiv.org/abs/2211.14941, 2022.
  * [12] H. Conrads.  Weighted projective spaces and reflexive simplices.  manuscripta mathematica, 107(2):215–227, 2002.
  * [13] W. Cook, J. Fonlupt, and A. Schrijver.  An integer analogue of Carathéodory’s theorem.  Journal of Combinatorial Theory, Series B, 40(1):63–70, 1986.
  * [14] J.C. de Pina and J. Soares.  Improved bound for the Carathéodory rank of the bases of a matroid.  Journal of Combinatorial Theory, Series B, 88:323–327, 2003.
  * [15] F. Eisenbrand and G. Shmonin.  Carathéodory bounds for integer cones.  Operations Research Letters, 34:564, 568:2006, 2006.
  * [16] S. Fiorini, G. Joret, S. Weltge, and Y. Yuditsky.  Integer programs with bounded subdeterminants and two nonzeros per row.  2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 13–24, 2022.
  * [17] D.C. Gijswijt and G. Regts.  Polyhedra with the Integer Carathéodory property.  Journal of Combinatorial Theory, Series B, 102:62–70, 2012.
  * [18] J. E. Graver.  On the foundations of linear and integer linear programming. I.  Math. Programming, 9(2):207–226, 1975.
  * [19] P. M. Gruber and C. G. Lekkerkerker.  Geometry of numbers, volume 37 of North-Holland Mathematical Library.  North-Holland Publishing Co., Amsterdam, second edition, 1987.
  * [20] J. Gubeladze.  Normal polytopes: between discrete, continuous, and random.  Journal of Pure and Applied Algebra, 227, 2023.
  * [21] M. Henk, S. Kuhlmann, and R. Weismantel.  On lattice width of lattice-free polyhedra and height of Hilbert bases.  SIAM Journal on Discrete Mathematics, 36(3):1918–1942, 2022.
  * [22] R. G. Jeroslow.  Some basis theorems for integral monoids.  Math. Oper. Res., 3(2):145–154, 1978.
  * [23] M. Nägele, R. Santiago, and R. Zenklusen.  Congruency-constrained TU problems beyond the bimodular case.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2743–2790. SIAM, 2022.
  * [24] A. Schrijver.  On total dual integrality.  Linear Algebra Appl., 38:27–32, 1981.
  * [25] A. Schrijver.  Theory of Linear and Integer Programming.  Wiley, 1986.
  * [26] A Sebő.  Hilbert bases, Carathéodory’s theorem and combinatorial optimization.  Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990.
  * [27] J. van der Corput.  Konstruktion der Minimalbasis für spezielle Diophantische Systeme von linear-homogenen Gleichungen und Ungleichungen.  Proc. Roy. Acad., 34:515–523, 1931.
  * [28] S.I. Veselov and A.J. Chirkov.  Integer program with bimodular matrix.  Discrete Optimization, 6:220–222, 2009.