# On lattice width of lattice-free polyhedra and height of Hilbert bases

Martin Henk Institut für Mathematik, Technische Universität Berlin, Germany,
<EMAIL_ADDRESS>Stefan Kuhlmann Institut für Mathematik, Technische
Universität Berlin, Germany<EMAIL_ADDRESS>Robert Weismantel
Department of Mathematics, Institute for Operations Research, ETH Zürich,
Switzerland<EMAIL_ADDRESS>
The last two authors have received funding from the third authors Einstein
Visiting Fellowship (project 1-4001022) issued by the Einstein Foundation

Abstract. We study the lattice width of lattice-free polyhedra given by
$\bm{A}\bm{x}\leq\bm{b}$ in terms of $\Delta(\bm{A})$, the maximal $n\times n$
minor in absolute value of $\bm{A}\in\mathbb{Z}^{m\times n}$. Our main
contribution is to link the lattice width of lattice-free polyhedra to the
height of Hilbert bases and to the diameter of finite abelian groups. This
leads to a bound on the lattice width of lattice-free pyramids which solely
depends on $\Delta(\bm{A})$ provided a conjecture regarding the height of
Hilbert bases holds. Further, we exploit a combination of techniques to obtain
novel bounds on the lattice width of simplices.
A second part of the paper is devoted to a study of the above mentioned
Hilbert basis conjecture. We give a complete characterization of the Hilbert
basis if $\Delta(\bm{A})=2$ which implies the conjecture in that case and
prove its validity for simplicial cones.

##  1 Introduction

Given a polyhedron

$\displaystyle
P(\bm{A},\bm{b}):=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}\bm{x}\leq\bm{b}\\}$

defined by $\bm{A}\in\mathbb{Z}^{m\times n}$ with full column rank, $m\geq n$
and $\bm{b}\in\mathbb{Z}^{m}$. The polyhedron is lattice-free if
$P(\bm{A},\bm{b})\cap\mathbb{Z}^{n}=\emptyset$ and the lattice width of
$P(\bm{A},\bm{b})$ is defined as

$\displaystyle
w(P(\bm{A},\bm{b})):=\min_{\bm{z}\in\mathbb{Z}^{n}\backslash\\{\bm{0}\\}}(\max_{\bm{x}\in
P(\bm{A},\bm{b})}\bm{z}^{T}\bm{x}-\min_{\bm{y}\in
P(\bm{A},\bm{b})}\bm{z}^{T}\bm{y}).$

More generally, given a set $X\subseteq\mathbb{Z}^{n}\backslash\\{\bm{0}\\}$
the lattice width of $P(\bm{A},\bm{b})$ in directions $X$ is

$\displaystyle w^{X}(P(\bm{A},\bm{b})):=\min_{\bm{z}\in X}(\max_{\bm{x}\in
P(\bm{A},\bm{b})}\bm{z}^{T}\bm{x}-\min_{\bm{y}\in
P(\bm{A},\bm{b})}\bm{z}^{T}\bm{y}).$

Let $\mathcal{F}$ be the set of facet normals of $P(\bm{A},\bm{b})$, which are
a subset of the rows of $\bm{A}$. Then $w^{\mathcal{F}}(P(\bm{A},\bm{b}))$
denotes the facet width of $P(\bm{A},\bm{b})$. In Subsection 1.2 we present an
upper bound on the facet width in terms of the lattice width, see Proposition
1.9.
There are various upper bounds on the lattice width of lattice-free polyhedra
which depend on the dimension $n$, e.g., the lattice width is
$\mathcal{O}(n\log(n))$ if the number of vertices or facets of
$P(\bm{A},\bm{b})$ can be bounded by a polynomial in $n$, see [5]. The current
best upper bound on the lattice width of the more general class of convex
bodies is $\mathcal{O}^{*}(n^{\frac{4}{3}})$ where $\mathcal{O}^{*}$ denotes
that a polynomial in $\log n$ is omitted, see [17].
The lattice width plays a key role for a variety of algorithms related to
integer programs. One famous example is Lenstras approach to solve the
feasibility question of integer linear programs [12].
Our aim is to bound the lattice/facet width of lattice-free polyhedra solely
in terms of $\Delta(\bm{A})$ where

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

For $\Delta(\bm{A})=1$ it is well-known that each vertex of $P(\bm{A},\bm{b})$
is integral. Further, each full-dimensional polyhedron contains an integer
point if $\Delta(\bm{A})=2$, see [21, Theorem 1]. Hence, lattice-free
polyhedra with $\Delta(\bm{A})=2$ are contained in a hyperplane. That already
implies $w(P(\bm{A},\bm{b}))=0=\Delta(\bm{A})-2$.
Simplices are so far the only class of polytopes that are known to be bounded
solely by $\Delta(\bm{A})$, as proven by Gribanov and Veselov [9]. More
precisely, they show

$\displaystyle w^{\mathcal{F}}(P(\bm{A},\bm{b}))<\delta(\bm{A})-1,$ (1)

where $\bm{A}\in\mathbb{Z}^{(n+1)\times n}$ defines the simplex and

$\displaystyle\delta(\bm{A}):=\min\\{|\det\bm{B}|:\bm{B}\text{ is an }n\times
n\text{ invertible submatrix of }\bm{A}\\}.$

Furthermore, they present a bound on the lattice width of lattice-free
polyhedra that depends among other things on $\Delta(\bm{A})$, the dimension
and the lowest common multiple of all $n\times n$ minors, which can get
exponentially large in $\Delta(\bm{A})$.
In a recent result, Basu and Jiang use the facet width of certain polytopes
with bounded minors to construct an algorithm which efficiently enumerates
special integer points inside those polytopes [6]. The latter result is one
recent example among many research studies that try to establish a refined
theory of integer optimization in which answers to questions do not only
depend on the dimension and the number of rows of an underlying constraint
matrix, but also involve the data parameter defined as the maximum absolute
value among all subdeterminants of the constraint matrix. Besides the lattice
width and facet width there are many other prominent functions of this kind:
the diameter of a polyhedron, the support of optimal solutions to standard-
form integer programs, the proximity of optimal integer and continuous
solutions and the running time function for integer optimization problems. See
[1, 2, 3, 4, 7, 8, 14, 15, 16] for some references about this development.
A core of our analysis is a new link between lattice-freeness, the height of a
Hilbert basis and the diameter of finite abelian groups. This leads among
others to a bound on the facet width of lattice-free pyramids, see Theorem
1.2.
The diameter of a finite abelian group is defined as follows. Let $G$ be a
finite (additive) abelian group and $H\subseteq G$ a set which generates $G$.
Then the diameter of $G$ with respect to $H$ denotes the minimal
$k\in\mathbb{N}$ such that $H$ generates $G$ with at most $k$ sums, i.e.,

$\displaystyle\operatorname{diam}_{H}(G):=\min\\{k\in\mathbb{N}:\\{h^{1}+...+h^{l}:h^{i}\in
H\text{ and }l\leq k\\}=G\\}.$

Further, the diameter of $G$ is given by

$\displaystyle\operatorname{diam}(G):=\max\\{\operatorname{diam}_{H}(G):H\subseteq
G\text{ generates }G\\}$

and therefore it is independent of the generating set.
As it turns out, the Hilbert basis of a specific cone forms a generating set
of an appropriate finite abelian group that we will investigate in Section 2.
Given a matrix $\bm{A}\in\mathbb{Z}^{m\times n}$ with full column rank and
$m\geq n$ we define the polyhedral cone

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

So $C(\bm{A})$ is rational and pointed. The Hilbert basis elements of such a
cone $C(\bm{A})$ with respect to a lattice $\Lambda$ are the irreducible
elements, i.e., $\bm{h}\in C(\bm{A})\cap\Lambda$ is a Hilbert basis element if
and only if for all $\bm{z}^{1},\bm{z}^{2}\in C(\bm{A})\cap\Lambda$ with
$\bm{h}=\bm{z}^{1}+\bm{z}^{2}$ we have either $\bm{z}^{1}=\bm{0}$ or
$\bm{z}^{2}=\bm{0}$. All elements in $C(\bm{A})\cap\Lambda$ can be described
as a non-negative integral combination of the respective Hilbert basis
elements. The set of all Hilbert basis elements is called the Hilbert basis.
In order to bound the facet width, we use a bound on each Hilbert basis
element. This relates directly to the height of Hilbert bases.
Each Hilbert basis element $\bm{h}$ with respect to a lattice $\Lambda$ is a
positive combination of the vectors which lie on the extreme rays of
$C(\bm{A})$. If we denote the set of those vectors by $R$, then the height of
a Hilbert basis element equals

$\displaystyle\mathcal{H}_{R,\Lambda}(\bm{h}):=\min\left\\{\sum_{\bm{r}\in
R}\lambda_{\bm{r}}:\sum_{\bm{r}\in
R}\lambda_{\bm{r}}\bm{r}=\bm{h},\lambda_{\bm{r}}\geq 0\text{ for all
}\bm{r}\in R\right\\}$

and the height of a Hilbert basis is

$\displaystyle\mathcal{H}_{R,\Lambda}(C(\bm{A})):=\max\\{\mathcal{H}_{R,\Lambda}(\bm{h}):\bm{h}\in
C(\bm{A})\cap\Lambda\text{ is a Hilbert basis element}\\}.$

Commonly, the vectors $R$ are scaled to be primitive lattice vectors. In that
case, the height is strictly bounded by $n-1$, see [13]. Some improvements of
this bound with respect to determinants of these primitive vectors are given
in [10]. However, for our approach we need another scaling of the vectors
which we define below.
Let $\bm{r}\in C(\bm{A})$ lie on an extreme ray with

$\displaystyle\bm{A}_{I,\cdot}\bm{r}=\bm{0}$

for $I\subseteq[m]$ and $|I|=n-1$ such that
$\operatorname{rank}(\bm{A}_{I,\cdot})=n-1$, see beginning of Subsection 1.1
for a definition of the matrices $\bm{A}_{I,\cdot}$ and
$\bm{A}_{I,[n]\backslash\\{i\\}}$. Then by Cramer’s rule we work with the
following scaling (up to a sign)

$\displaystyle r_{i}:=(-1)^{i}\det\bm{A}_{I,[n]\backslash\\{i\\}}$

for $i=1,...,n$. This scaling could vary if there are other $n-1$ linearly
independent rows of $\bm{A}$ indexed by $\bar{I}\subseteq[m]$ with

$\displaystyle\bm{A}_{\bar{I},\cdot}\bm{r}=\bm{0}$

and $\gcd(\bm{A}_{\bar{I},\cdot})\neq\gcd(\bm{A}_{I,\cdot})$, see (6) for a
definition of this quantity. We scale as large as possible:

$\displaystyle\max_{I\subseteq[m]}\\{\gcd(\bm{A}_{I,\cdot}):I\subseteq[m],\text{
}|I|=n-1,\text{ }\operatorname{rank}(\bm{A}_{I,\cdot})=n-1,\text{
}\bm{A}_{I,\cdot}\bm{r}=\bm{0}\\}.$ (2)

Throughout this paper we refer to these scaled vectors as normalized
generators and denote by $R(\bm{A})$ the set of normalized generators of
$C(\bm{A})$. If the vectors are scaled to be primitive, we refer to them as
primitive generators and denote the set by $\tilde{R}(\bm{A})$.
The scaling allows us to deduce the following fundamental property of the
right-hand side $\bm{A}\bm{r}$. Pick $k\in[m]$ and $\bm{r}\in R(\bm{A})$, we
observe

$\displaystyle\bm{A}_{k,\cdot}\bm{r}=|\det\bm{A}_{I\cup\\{k\\},\cdot}|\leq\Delta(\bm{A})$

by Laplace expansion. In particular, we get

$\displaystyle\|\bm{A}\bm{r}\|_{\infty}\leq\Delta(\bm{A}).$ (3)

Note that $\bm{r}$ is not necessarily primitive. Therefore, the height of a
Hilbert basis with respect to the normalized generators might be significantly
smaller than $n-1$ and might not even depend on the dimension at all. A recent
result by Sissokho [19] shows that the height of a Hilbert basis with respect
to the normalized generators is bounded by 1 if $m=n+1$. Due to this and our
following collection of results (Theorem 1.1), we conjecture the following:

Strong Hilbert basis conjecture (SHC). Let $C(\bm{A})$ be a cone, $\bm{h}\in
C(\bm{A})$ a Hilbert basis element of $C(\bm{A})$ with respect to
$\mathbb{Z}^{n}$ and $R(\bm{A})=\\{\bm{r}^{1},...,\bm{r}^{t}\\}$. Then

$\displaystyle\bm{h}\in\operatorname{conv}\\{\bm{0},\bm{r}^{1},...,\bm{r}^{t}\\}$

or equivalently $\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C(\bm{A}))\leq 1$.

Prior to this paper, the conjecture was known to be true for $m=n+1$. It is
also true if we fix $\Delta(\bm{A})=1$, see e.g., [20, Proposition 8.1]. More
specifically, the Hilbert basis elements are the primitive vectors on each
extreme ray in that case. These results combined with our upcoming analysis
(Theorem 1.5, Proposition 1.6 and Corollary 1.7) yield the following cases
where (SHC) holds.

######  Theorem 1.1.

(SHC) holds if at least one of the following conditions is satisfied:

  1. 1.

$m\leq n+1$

  2. 2.

all $n\times n$ minors of $\bm{A}$ are contained in $\\{0,\pm k,\pm 2k\\}$ for
some $k\in\mathbb{N}_{\geq 1}$.

The proof of Theorem 1.1 is presented in Subsection 3.4.
We emphasize that the scaling in (2) is important. There are counterexamples
to the conjecture if we use a different scaling, see Appendix A.1 for an
example.
Throughout the paper we work with cones defined by $\bm{A}\bm{x}\geq\bm{0}$.
Nevertheless, we can reformulate the setting of (SHC) in terms of the
orthogonal subspace of the image of $\bm{A}$. For that purpose let
$\bm{W}\in\mathbb{Z}^{(m-n)\times m}$ be a full row rank matrix with
$\bm{W}\bm{A}=\bm{0}$. Then in the orthogonal formulation we work with the
cone defined by $\bm{W}\bm{x}=\bm{0}$ and $\bm{x}\geq\bm{0}$. Further, the
normalized generators correspond to suitably scaled circuits. This orthogonal
setting is equivalent to ours and builds the foundation of [19].
In order to state our facet width, let us make precise what a pyramid means.
Let $\bm{v}$ satisfy $\bm{A}\bm{v}=\bm{b}$ for a full column rank matrix
$\bm{A}\in\mathbb{Z}^{m\times n}$ with $m\geq n$ and
$\bm{b}\in\mathbb{Z}^{m}$. One might think of $\bm{v}$ as the apex. We
investigate the translated cone

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

and some $-\bm{a}\in\operatorname{int}(C(\bm{A})^{*})\cap\mathbb{Z}^{n}$,
where $C(\bm{A})^{*}$ is the dual cone of $C(\bm{A})$, see (7) for a precise
definition. The pyramid is then defined by

$\displaystyle
P(\bm{A},\bm{a},\bm{b},b_{a}):=\left\\{\bm{x}\in\mathbb{R}^{n}:\begin{pmatrix}\bm{A}\\\
\bm{a}^{T}\end{pmatrix}\bm{x}\leq\begin{pmatrix}\bm{b}\\\
b_{a}\end{pmatrix}\right\\}$

where $b_{a}$ is an integer greater than $\bm{a}^{T}\bm{v}$. Observe that
$-\bm{a}\in\operatorname{int}(C^{*})$ guarantees the boundedness of
$P(\bm{A},\bm{a},\bm{b},b_{a})$. We remark that the arguments in this paper
stay valid if $-\bm{a}$ lies on the boundary of
$C(\bm{A})^{*}\cap\mathbb{Z}^{n}\backslash\\{\bm{0}\\}$. In that case,
$P(\bm{A},\bm{a},\bm{b},b_{a})$ is unbounded.
Furthermore, we refer to a polyhedron $P(\bm{A},\bm{b})$ as $\Delta$-modular
if $\Delta(\bm{A})=\Delta$. Finally, in order to state our facet width bound,
we denote by $\Gamma^{*}$ the dual lattice of $\Gamma$, see (8) for a
definition and more about lattices and their bases.

######  Theorem 1.2.

Let $P=P(\bm{A},\bm{a},\bm{b},b_{a})$ be a lattice-free $\Delta$-modular
pyramid. Further, let $\Lambda=(\bm{A}^{T}\mathbb{Z}^{m})^{*}$ and
$\bm{B}\in\mathbb{Q}^{n\times n}$ be a basis of $\Lambda$. Then

$\displaystyle
w^{\bm{a}}(P)\leq\frac{\Delta}{\gcd(\bm{A})}\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\operatorname{diam}(\Lambda/\mathbb{Z}^{n})-1$
(4)

and if (SHC) is true, then

$\displaystyle w^{\bm{a}}(P)\leq\Delta-2.$ (5)

The second inequality is based on a result of Klopsch and Lev [11] about the
diameter of finite abelian groups. Furthermore, we present examples where the
first bound in (4) is tight for arbitrary finite abelian groups.
We emphasize that proving any constant upper bound on
$\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))$ implies
directly an upper bound in (4) which depends linearly on $\Delta$.
Moreover, recall that $\tilde{R}(\bm{A}\bm{B})$ denotes the set of primitive
generators of $C(\bm{A}\bm{B})$. We obtain

$\displaystyle\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\leq\mathcal{H}_{\tilde{R}(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))<n-1$

using the bound in [13]. This leads to

$\displaystyle w^{\bm{a}}(P)<(n-1)(\Delta-1)-1.$

As a consequence of Theorem 1.2, we are able to generalize (1) by exploiting
the underlying group structure. We abbreviate

$\displaystyle\delta:=\delta\left(\begin{pmatrix}\bm{A}\\\
\bm{a}^{T}\end{pmatrix}\right).$

######  Corollary 1.3.

Let $P=P(\bm{A},\bm{a},\bm{b},b_{a})$ be a lattice-free simplex with
$|\det\bm{A}|=\delta$. Then

$\displaystyle
w^{\mathcal{F}}(P)<\operatorname{diam}(\Lambda/\mathbb{Z}^{n})\leq\delta-1.$

This is not a direct improvement of (1), but the first inequality solely
depends on the group structure of $\Lambda/\mathbb{Z}^{n}$ and is usually
significantly smaller than $\delta-1$. Hence, this bound is more accurate.
We apply Corollary 1.3 to improve (1) in terms of the lattice width.

######  Theorem 1.4.

Let $P=P(\bm{A},\bm{a},\bm{b},b_{a})$ be a lattice-free simplex with
$|\det\bm{A}|=\delta$. Then

$\displaystyle w(P)<\left\lfloor\frac{\delta}{2}\right\rfloor.$

This is the current best upper bound on the lattice width of simplices with
respect to their minors. We prove all the lattice/facet width results in
Section 2.
As mentioned earlier, the lattice width of lattice-free pyramids is closely
tied to (SHC). Therefore, we study in Section 3 the conjecture and prove its
validity for some classes of cones. In particular, we characterize the Hilbert
basis if $\Delta(\bm{A})=2$. Throughout the paper we refer to $2$-modular
polyhedra as bimodular. Furthermore, if $\bm{h}$ lies on an extreme ray, we
say that $\bm{h}$ is trivial. Otherwise we call $\bm{h}$ non-trivial.

######  Theorem 1.5.

Let $C(\bm{A})$ be a bimodular cone and $\bm{h}$ a non-trivial Hilbert basis
element of $C(\bm{A})$ with respect to $\mathbb{Z}^{n}$. Then, there exist
$\bm{r}^{i},\bm{r}^{j}\in R(\bm{A})$ with

$\displaystyle\bm{h}=\frac{1}{2}\bm{r}^{i}+\frac{1}{2}\bm{r}^{j}$

for $i\neq j$.

Theorem 1.5 implies that (SHC) holds in the bimodular case. While proving this
result we rediscover that all Hilbert basis elements of $C(\bm{A})$ are
trivial for $\Delta(\bm{A})=1$.
We also show that (SHC) behaves well under certain linear transformations.

######  Proposition 1.6.

Let $C(\bm{A})$ be a cone and $\bm{B}\in\mathbb{Z}^{n\times n}$ be an
invertible matrix. If (SHC) holds for $C(\bm{A})$, then it is true for
$C(\bm{A}\bm{B})$. Furthermore, it suffices to prove (SHC) when
$\gcd(\bm{A})=1$.

As a result, we are able to give an affirmative answer to (SHC) in the
simplicial case and locate the Hilbert basis elements in terms of lower-
dimensional faces. More specifically, we prove the following.

######  Corollary 1.7.

Let $C(\bm{A})$ be a simplicial cone and $\bm{h}$ a Hilbert basis element of
$C(\bm{A})$ with respect to $\mathbb{Z}^{n}$. Then,
$\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C(\bm{A}))\leq 1$. Furthermore,
$\bm{h}$ lies in the interior of a $k$-face of $C(\bm{A})$ with $k\leq\Delta$.

Combining this with [19] implies that (SHC) holds if $m\leq n+1$. Moreover,
Corollary 1.7 shows (SHC) for $n=2$ as every cone in dimension two is
simplicial. Already for simplicial cones there are examples where the height
of a Hilbert basis with respect to the primitive generators asymptotically
attains $n-1$, compare with [10] and [13]. This and Corollary 1.7 highlight
the discrepancy between primitive and normalized generators. We prove
Proposition 1.6 and Corollary 1.7 in Subsection 3.3.
Theorem 1.5 enables us to identify classes of pyramids where our bound (5)
holds.

######  Corollary 1.8.

The bound (5) holds if at least one of the following is satisfied:

  1. 1.

$\Delta(\bm{A})$ is prime.

  2. 2.

All $n\times n$ minors of $\bm{A}$ are in
$\\{0,\pm\frac{\Delta(\bm{A})}{2},\pm\Delta(\bm{A})\\}$.

We prove this statement in Section 2.
We remark that the lattice width cannot lead to bounds which solely depend on
$\Delta(\bm{A})$ if
$\operatorname{int}(P(\bm{A},\bm{b}))\cap\mathbb{Z}^{n}=\emptyset$. A detailed
example for that is given in (10).

###  1.1 Notation and definitions

Here, we introduce the notation and definitions which are used throughout the
paper. We abbreviate $[m]:=\\{1,...,m\\}$. Given $\bm{A}\in\mathbb{Z}^{m\times
n}$, $I\subseteq[m]$ and $J\subseteq[n]$ then $\bm{A}_{I,J}$ denotes the
submatrix of $\bm{A}$ with rows indexed by $I$ and columns indexed by $J$.
When $J=[n]$, we use $\bm{A}_{I,\cdot}$ and vice versa. In case of $|I|=|J|$,
we write $\bm{A}_{I,J}^{-1}$ for $(\bm{A}_{I,J})^{-1}$. Further,
$\operatorname{adj}(\bm{A}_{I,J})$ denotes the adjugate matrix of
$\bm{A}_{I,J}$. If $m\geq n$, we use

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

and set $\gcd(\bm{A}^{T}):=\gcd(\bm{A})$. Additionally,
$\operatorname{rank}(\bm{A})$ denotes the (column) rank of $\bm{A}$. For
$\bm{x}\in\mathbb{R}^{n}$ we represent the support of $\bm{x}$ as

$\displaystyle\operatorname{supp}(\bm{x}):=\\{i\in[n]:x_{i}\neq 0\\}.$

An $\bm{x}\in\mathbb{Z}^{n}$ is called primitive if $\gcd(\bm{x})=1$. If not
defined otherwise, we denote by $C(\bm{A})$ the cone

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

with $\bm{A}\in\mathbb{Z}^{m\times n}$ and $\operatorname{rank}(\bm{A})=n$.
The cone $C(\bm{A})$ is simplicial if $m=n$. We denote by

$\displaystyle C(\bm{A})^{*}:=\\{\bm{x}\in\mathbb{R}^{n}:\bm{y}^{T}\bm{x}\geq
0\text{ for all }\bm{y}\in C(\bm{A})\\}$ (7)

the dual cone of $C(\bm{A})$. An extreme ray is a 1-dimensional face of
$C(\bm{A})$. Let

$\displaystyle
P(\bm{A},\bm{b}):=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}\bm{x}\leq\bm{b}\\}$

be a polytope with $\bm{A}\in\mathbb{Z}^{m\times n}$ for $m\geq n$ and
$\operatorname{rank}(\bm{A})=n$ and $\bm{v}\in P(\bm{A},\bm{b})$ a vertex of
$P(\bm{A},\bm{b})$. Further, let $I\subseteq[m]$ be the maximal index set with
$\bm{A}_{I,\cdot}\bm{v}=\bm{b}_{I}$. Then

$\displaystyle
C^{\bm{v}}:=P(\bm{A}_{I,\cdot},\bm{b}_{I})=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}_{I,\cdot}\bm{x}\leq\bm{b}_{I}\\}$

is the vertex cone of $\bm{v}$.
A lattice $\Lambda$ is a discrete subgroup of $\mathbb{R}^{n}$. A basis of
$\Lambda$ are $k$ linearly independent vectors
$\bm{b}^{1},...,\bm{b}^{k}\in\Lambda$ such that
$\Lambda:=(\bm{b}^{1},...,\bm{b}^{k})\mathbb{Z}^{k}$. If $k=n$, the lattice is
full-dimensional. The dual lattice $\Lambda^{*}$ of a full-dimensional lattice
$\Lambda$ is defined by

$\displaystyle\Lambda^{*}:=\\{\bm{x}\in\mathbb{R}^{n}:\bm{y}^{T}\bm{x}\in\mathbb{Z}\text{
for all }\bm{y}\in\Lambda\\}.$ (8)

The canonical unit vectors of $\mathbb{R}^{n}$ are denoted by
$\bm{e}_{1},...,\bm{e}_{n}$. The vector $\bm{1}\in\mathbb{R}^{n}$ represents
the all-ones vector in $\mathbb{R}^{n}$ and $\bm{I}_{n}$ is the $n\times n$
unit matrix.
We abbreviate $\Delta(\bm{A})$ by $\Delta$ and $\delta(\bm{A})$ by $\delta$ if
the underlying constraint matrix is clear from the context.
$GL(n,\mathbb{Z})$ denotes the group of all $n\times n$ unimodular matrices,
i.e., $\bm{A}\in\mathbb{Z}^{n\times n}$ and $|\det\bm{A}|=1$,
$\operatorname{int}(X)$ for $X\subseteq\mathbb{R}^{n}$ is the interior of $X$
and $\mathbb{N}=\\{0,1,2,...\\}$.

###  1.2 Relation between lattice and facet width

In this subsection we show that there is a natural relation between lattice
and facet width in terms of the $n\times n$ minors of the given constraint
matrix.
Let $P=P(\bm{A},\bm{b})$ be a polytope defined by a full column rank matrix
$\bm{A}\in\mathbb{Z}^{m\times n}$ for $m\geq n$. In contrast to the rest of
the paper, we allow the right-hand side to be real, i.e.,
$\bm{b}\in\mathbb{R}^{m}$. Further, we assume that all rows of $\bm{A}$ define
a facet of $P$. Therefore, the set of facet normals $\mathcal{F}$ corresponds
to the rows of $\bm{A}$.
Given any $\bm{a}\in\mathcal{F}$ we get by definition the following trivial
bounds

$\displaystyle w(P)\leq w^{\mathcal{F}}(P)\leq w^{\bm{a}}(P).$

A converse relationship is presented next.

######  Proposition 1.9.

Let $P=P(\bm{A},\bm{b})$ be a $\Delta$-modular polytope. Then

$\displaystyle w^{\mathcal{F}}(P)\leq\Delta w(P).$

###### Proof.

Let $\bm{a}\in\mathbb{Z}^{n}\backslash\\{\bm{0}\\}$ be a flat direction
attaining $w(P)$. Since $P$ is bounded, we can pick vertices $\bm{v},\bm{w}\in
P$ that maximize/minimize $\bm{a}^{T}\bm{x}$ over $P$. Thus,

$\displaystyle w(P)=\bm{a}^{T}(\bm{v}-\bm{w}).$

By Carathéodory’s theorem there exist $n$ linearly independent rows of
$\bm{A}$ which define the vertex cone $C^{\bm{v}}$, say
$\bm{A}_{1,\cdot},...,\bm{A}_{n,\cdot}$, with

$\displaystyle\bm{a}^{T}=\sum_{i=1}^{n}\lambda_{i}\bm{A}_{i,\cdot}$ (9)

where we assume that $\lambda_{1},...,\lambda_{k}$ are positive for $k\leq n$
and $\lambda_{i}=0$ if $i\in[n]\backslash[k]$. We select a vertex
$\tilde{\bm{w}}$ which maximizes $-\bm{A}_{1,\cdot}\bm{x}$. Then

$\displaystyle w(P)$ $\displaystyle=\bm{a}^{T}\bm{v}-\bm{a}^{T}\bm{w}$
$\displaystyle\geq\bm{a}^{T}\bm{v}-\bm{a}^{T}\tilde{\bm{w}}$
$\displaystyle=\sum_{i=1}^{k}\lambda_{i}(\bm{A}_{i,\cdot}\bm{v}-\bm{A}_{i,\cdot}\tilde{\bm{w}})$
$\displaystyle=\sum_{i=1}^{k}\lambda_{i}(b_{i}-\bm{A}_{i,\cdot}\tilde{\bm{w}})$
$\displaystyle=\lambda_{1}w^{\bm{A}_{1,\cdot}^{T}}(P)+\sum_{i=2}^{k}\lambda_{i}(b_{i}-\bm{A}_{i,\cdot}\tilde{\bm{w}})$
$\displaystyle\geq\lambda_{1}w^{\bm{A}_{1,\cdot}^{T}}(P).$

As $\lambda_{1}$ is positive and $\bm{a}\in\mathbb{Z}^{n}$, we get
$\lambda_{1}\geq\Delta^{-1}$ by Cramer’s rule applied to (9). The claim
follows from $w^{\mathcal{F}}(P)\leq w^{\bm{A}_{1,\cdot}^{T}}(P)$. ∎

Suppose there is a function $f$ where $f$ solely depends on $\Delta$ such that
$w(P)\leq f(\Delta)$. Then the proof of Proposition 1.9 shows us that
$w^{\mathcal{F}}(P)\leq\Delta f(\Delta)$.
If we focus on the case $\Delta=1$, we obtain the following interesting
corollary.

######  Corollary 1.10.

Let $P=P(\bm{A},\bm{b})$ be a polytope with $\Delta=1$. Then

$\displaystyle w(P)=w^{\mathcal{F}}(P).$

We close this subsection by providing an example $P(\bm{A},\bm{b})$ where
$\operatorname{int}(P(\bm{A},\bm{b}))\cap\mathbb{Z}^{n}=\emptyset$ and the
lattice width depends on the dimension.
Let

$\displaystyle
S=\left\\{\bm{x}\in\mathbb{R}^{n}:\begin{pmatrix}-1&0&\ldots&0\\\ 0&-1&&\\\
\vdots&&\ddots&\\\ 0&&&-1\\\
1&1&\ldots&1\end{pmatrix}\bm{x}\leq\begin{pmatrix}0\\\ 0\\\ \vdots\\\ 0\\\
n\end{pmatrix}\right\\}$ (10)

be a simplex scaled with the dimension $n$. It is easy to see that
$\operatorname{int}(S)\cap\mathbb{Z}^{n}=\emptyset$ and $\Delta=1$. So
Corollary 1.10 tells us that it suffices to calculate $w^{\mathcal{F}}(S)$ in
order to obtain $w(S)$. Doing so yields $n=w^{\mathcal{F}}(S)=w(S)$.

##  2 Facet width of lattice-free pyramids

In this section we present a link between (SHC), the diameter of finite
abelian groups and the lattice width of lattice-free pyramids in facet
direction.
We want to understand the lattice-freeness of the pyramid
$P(\bm{A},\bm{a},\bm{b},b_{a})$. As a first step, we fix the vertex cone
$C^{\bm{v}}=\bm{v}-C(\bm{A})$ at the apex $\bm{v}$. Our aim is to determine
how far we can push out the facet defined by $\bm{a}$ until we are guaranteed
to hit an integer point. In other words, how big does $b_{a}$ need to be such
that we can guarantee
$P(\bm{A},\bm{a},\bm{b},b_{a})\cap\mathbb{Z}^{n}\neq\emptyset$.
In order to tackle this question, we utilize some group structure coming from
the integrality of the constraint matrix and the right-hand side of
$P(\bm{A},\bm{a},\bm{b},b_{a})$. Let

$\displaystyle\Lambda=\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}\bm{x}\in\mathbb{Z}^{m}\\}$

be the lattice of integral right-hand sides for $\bm{A}$. Note that

$\displaystyle\Lambda=(\bm{A}^{T}\mathbb{Z}^{m})^{*}$ (11)

as each element $\bm{x}\in(\bm{A}^{T}\mathbb{Z}^{m})^{*}$ satisfies by our
definition of the dual lattice $\bm{e}_{i}^{T}\bm{A}\bm{x}\in\mathbb{Z}$ for
all $i\in[m]$ and every element in $\bm{y}\in\Lambda$ satisfies
$\bm{z}^{T}\bm{A}\bm{y}\in\mathbb{Z}$ for all $\bm{z}\in\mathbb{Z}^{m}$.
Observe that $\bm{v}\in\Lambda$ and $\mathbb{Z}^{n}\subseteq\Lambda$. Let
$\bm{h}^{1},...,\bm{h}^{t}\in C(\bm{A})\cap\Lambda$ denote the Hilbert basis
elements of $C(\bm{A})$ with respect to $\Lambda$. Then every element in
$(\bm{v}-C(\bm{A}))\cap\Lambda$ can be written as

$\displaystyle\bm{v}-\sum_{i=1}^{t}\lambda_{i}\bm{h}^{i}\in\Lambda$ (12)

for integral non-negative $\lambda_{1},...,\lambda_{t}$. Specifically, all
elements in $(\bm{v}-C(\bm{A}))\cap\mathbb{Z}^{n}$ are of the form above. Let
an integral point of the form (12) be given. Since $b_{a}\in\mathbb{Z}$, the
lattice-freeness of $P(\bm{A},\bm{a},\bm{b},b_{a})$ yields

$\displaystyle\bm{a}^{T}(\bm{v}-\sum_{i=1}^{t}\lambda_{i}\bm{h}^{i})\geq
b_{a}+1.$

Hence, we obtain

$\displaystyle
w^{\bm{a}}(P(\bm{A},\bm{a},\bm{b},b_{a}))=b_{a}-\bm{a}^{T}\bm{v}\leq\sum_{i=1}^{t}\lambda_{i}(-\bm{a}^{T}\bm{h}^{i})-1.$

We proceed by constructing an upper bound on $\lambda_{1}+...+\lambda_{t}$ via
the diameter of finite abelian groups. A second step is then to bound
$-\bm{a}^{T}\bm{h}^{i}$ using (SHC).
First, we pass to the finite abelian group $\Lambda/\mathbb{Z}^{n}$. Here, an
integer point of the form (12) corresponds an additive inverse of the coset
$\bm{v}+\mathbb{Z}^{n}$ in $\Lambda/\mathbb{Z}^{n}$. Let
$H=\\{\bm{h}^{1}...,\bm{h}^{t}\\}/\mathbb{Z}^{n}$ be the set of Hilbert basis
elements modulo $\mathbb{Z}^{n}$. As the Hilbert basis generates the lattice
$\Lambda$, the set $H$ is a generating set of $\Lambda/\mathbb{Z}^{n}$. Thus,
we need at most $\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})$ sums to
generate all elements, including an additive inverse of
$\bm{v}+\mathbb{Z}^{n}$ in $\Lambda/\mathbb{Z}^{n}$.
We want to bound $\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})$ from above.
The definitions already yield
$\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})\leq\operatorname{diam}(\Lambda/\mathbb{Z}^{n})$.
By the fundamental theorem of finite abelian groups every finite abelian group
can be decomposed into the direct sum of cyclic groups, i.e., let $G$ be a
finite abelian group then there exist $s_{1},...,s_{N}\in\mathbb{N}_{\geq 2}$
for $N\in\mathbb{N}_{\geq 1}$ such that

$\displaystyle
G\cong\mathbb{Z}/s_{1}\mathbb{Z}\oplus...\oplus\mathbb{Z}/s_{N}\mathbb{Z}$

and $s_{1}|s_{2}|...|s_{N}$. We refer to this as the invariant decomposition
and the $s_{i}$ as the invariant factors. In dependence of this decomposition
there exists an exact formula for the diameter of a finite abelian group by
Klopsch and Lev.

######  Theorem 2.1 ([11], Theorem 2.1).

Let $G$ be a finite abelian group with invariant decomposition
$G\cong\mathbb{Z}/s_{1}\mathbb{Z}\oplus...\oplus\mathbb{Z}/s_{N}\mathbb{Z}$.
Then

$\displaystyle\operatorname{diam}(G)=\sum_{i=1}^{N}s_{i}-1.$

It is not hard to see that

$\displaystyle\sum_{i=1}^{N}s_{i}-1\leq\left(\prod_{i=1}^{N}s_{i}\right)-1.$
(13)

The product of the invariant factors equals the order of $G$. In our case the
order of $G$ is the index of $\Lambda/\mathbb{Z}^{n}$. The following lemma
quantifies this index which is given by $(\det\Lambda)^{-1}$.

######  Lemma 2.2.

Let $\bm{A}\in\mathbb{Z}^{m\times n}$ with full column rank, $m\geq n$ and
$\Lambda=(\bm{A}^{T}\mathbb{Z}^{m})^{*}$. Then

$\displaystyle\det\Lambda=\frac{1}{\gcd(\bm{A})}.$

###### Proof.

We prove $\det\bm{A}^{T}\mathbb{Z}^{m}=\gcd(\bm{A})$. Then the claim follows
from

$\displaystyle\det\bm{A}^{T}\mathbb{Z}^{m}=\det\Lambda^{*}=(\det\Lambda)^{-1}.$

We transform $\bm{A}^{T}$ into Smith normal form, see e.g., [18, Chapter 4.4]
for a treatment of Smith normal forms. In order to do so, there are $\bm{U}\in
GL(n,\mathbb{Z})$ and $\bm{V}\in GL(m,\mathbb{Z})$ such that

$\displaystyle\bm{U}\bm{A}^{T}\bm{V}=\begin{pmatrix}\begin{matrix}\alpha_{1}&&\\\
&\ddots&\\\ &&\alpha_{n}\end{matrix}\quad\bm{0}\end{pmatrix}$

with $\alpha_{1}\cdot...\cdot\alpha_{n}=\gcd(\bm{A})$. In the following, we
apply $\bm{V}\mathbb{Z}^{m}=\mathbb{Z}^{m}$,
$\det\bm{U}\Lambda^{*}=\det\Lambda^{*}$ and obtain

$\displaystyle\det\bm{A}^{T}\mathbb{Z}^{m}=\det\bm{U}\bm{A}^{T}\mathbb{Z}^{m}=\det\bm{U}\bm{A}^{T}\bm{V}\mathbb{Z}^{m}=\alpha_{1}\cdot...\cdot\alpha_{n}=\gcd(\bm{A}).$

∎

Lemma 2.2 allows us to bound
$\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})$. It remains to bound the
scalar product $-\bm{a}^{T}\bm{h}^{i}$. Here we make use of (SHC). For sake of
readability, we set

$\displaystyle\Delta(\bm{a}):=\Delta\left(\begin{pmatrix}\bm{A}\\\
\bm{a}^{T}\end{pmatrix}\right).$

In the following lemma, we allow $\bm{a}$ to be rational. Note that the
definition of $\Delta(\bm{A})$ extends naturally to rational matrices.

######  Lemma 2.3.

Given a cone $C=C(\bm{A})$ and $-\bm{a}\in C^{*}\cap\mathbb{Q}^{n}$. Let
$\bm{h}\in C$ be a Hilbert basis element of $C$ with respect to
$\mathbb{Z}^{n}$. Then

$\displaystyle-\bm{a}^{T}\bm{h}\leq\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C)\Delta(\bm{a}).$

###### Proof.

Define

$\displaystyle Q:=\bigcap_{-\bm{a}\in
C^{*}\cap\mathbb{Q}^{n}}\\{\bm{x}\in\mathbb{R}^{n}:-\bm{a}^{T}\bm{x}\leq\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C)\Delta(\bm{a})\\}\cap
C$

the infinite intersection of all polyhedra which arise by intersecting the
cone $C$ with one of the half-spaces defined by $-\bm{a}\in
C^{*}\cap\mathbb{Q}^{n}$. We show $\bm{h}\in Q$.
Let $R(\bm{A})=\\{\bm{r}^{1},...,\bm{r}^{t}\\}$. Boundedness of the right-hand
side, cf. (3), yields

$\displaystyle-\bm{a}^{T}\bm{r}^{i}\leq\Delta(\bm{a})$

for all $-\bm{a}\in C^{*}\cap\mathbb{Q}^{n}$ and $i=1,...,t$. Thus,
$\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C)\bm{r}^{i}\in Q$. Since the
intersection of infinitely many convex sets is convex, we conclude

$\displaystyle\operatorname{conv}\\{\bm{0},\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C)\bm{r}^{1},...,\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C)\bm{r}^{t}\\}\subseteq
Q.$ (14)

∎

###### Proof of Theorem 1.2.

Recall that $P=P(\bm{A},\bm{a},\bm{b},b_{a})$. By definition we have
$\bm{v}\in\Lambda$, cf. (11). Note that $\bm{v}-C(\bm{A})$ is the vertex cone
of $P$ at $\bm{v}$. Let $\bm{h}^{1},...,\bm{h}^{t}$ denote the Hilbert basis
of $C(\bm{A})$ with respect to $\Lambda$.
Assume

$\displaystyle\bm{v}-\sum_{i=1}^{t}\lambda_{i}\bm{h}^{i}\in\mathbb{Z}^{n}$

for $\lambda_{1},...,\lambda_{t}\in\mathbb{Z}_{\geq 0}$. Then the coset

$\displaystyle-\sum_{i=1}^{t}\lambda_{i}\bm{h}^{i}+\mathbb{Z}^{n}$

is an additive inverse of $\bm{v}+\mathbb{Z}^{n}$ in $\Lambda/\mathbb{Z}^{n}$.
So we can choose the coefficients to satisfy

$\displaystyle\lambda_{1}+...+\lambda_{t}\leq\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})\leq\operatorname{diam}(\Lambda/\mathbb{Z}^{n})$
(15)

where $H=\\{\bm{h}^{1},...,\bm{h}^{t}\\}/\mathbb{Z}^{n}$. Since $P$ is
lattice-free, we have

$\displaystyle
b_{a}+1\leq\bm{a}^{T}(\bm{v}-\sum_{i=1}^{t}\lambda_{i}\bm{h}^{i}).$ (16)

Recall that $\bm{B}\in\mathbb{Q}^{n\times n}$ is a basis of $\Lambda$. Then
$\bm{B}^{-1}C(\bm{A})=C(\bm{A}\bm{B})$ and
$\bm{B}^{-1}\bm{h}^{1},...,\bm{B}^{-1}\bm{h}^{t}$ are Hilbert basis elements
of $C(\bm{A}\bm{B})$ with respect to $\mathbb{Z}^{n}$. Specifically, we get
$\bm{A}\bm{B}\in\mathbb{Z}^{m\times n}$ by definition of $\Lambda$. Lemma 2.2
implies

$\displaystyle\Delta\left(\begin{pmatrix}\bm{A}\\\
\bm{a}^{T}\end{pmatrix}\bm{B}\right)=\frac{\Delta(\bm{a})}{\gcd(\bm{A})}$

where $\Delta(\bm{a})=\Delta$. Combining this with Lemma 2.3 and
$-\bm{B}^{T}\bm{a}\in\operatorname{int}(C(\bm{A}\bm{B})^{*})\cap\mathbb{Q}^{n}$
results in

$\displaystyle-\bm{a}^{T}\bm{h}^{i}=-\bm{a}^{T}\bm{B}\bm{B}^{-1}\bm{h}^{i}\leq\frac{\Delta}{\gcd(\bm{A})}\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B})).$
(17)

As a consequence of (16), (17) and (15), we obtain

$\displaystyle w^{\bm{a}}(P)$ $\displaystyle=b_{a}-\bm{a}^{T}\bm{v}$
$\displaystyle\leq\bm{a}^{T}(\bm{v}-\sum_{i=1}^{t}\lambda_{i}\bm{h}^{i})-1-\bm{a}^{T}\bm{v}$
$\displaystyle=-\sum_{i=1}^{t}\lambda_{i}\bm{a}^{T}\bm{h}^{i}-1$
$\displaystyle\leq\frac{\Delta}{\gcd(\bm{A})}\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\sum_{i=1}^{t}\lambda_{i}-1$
$\displaystyle\leq\frac{\Delta}{\gcd(\bm{A})}\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\operatorname{diam}(\Lambda/\mathbb{Z}^{n})-1.$

For the second inequality in Theorem 1.2, we get
$\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\leq 1$ from the
validity of (SHC). Further, we note that

$\displaystyle\operatorname{diam}(\Lambda/\mathbb{Z}^{n})\leq\gcd(\bm{A})-1$

from (13) and Lemma 2.2. As a result, we obtain

$\displaystyle
w^{\bm{a}}(P)\leq\frac{\Delta}{\gcd(\bm{A})}\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})-1\leq\Delta\frac{\gcd(\bm{A})-1}{\gcd(\bm{A})}-1\leq\Delta-2.$

∎

###### Proof of Corollary 1.8.

We need (SHC) to be true for the cone $C(\bm{A}\bm{B})$ in the proof above.
Applying Theorem 1.5 and the result for $\Delta(\bm{A}\bm{B})=1$ this is the
case when

$\displaystyle\frac{\Delta(\bm{A})}{\gcd(\bm{A})}\in\\{1,2\\}$

which holds if the second statement from the claim is satisfied. Additionally,
the first statement, $\Delta(\bm{A})$ being prime, implies
$\gcd(\bm{A})=\Delta(\bm{A})$. That is why, the existence of a $n\times n$
minor of $\bm{A}$ with determinant smaller than $\Delta(\bm{A})$ yields
$\gcd(\bm{A})=1$ which is equivalent to $\Lambda=\mathbb{Z}^{n}$. Hence,
$\bm{v}\in\Lambda$ contradicts the lattice-freeness of $P$. ∎

The second part of Theorem 1.2 is true if (SHC) holds. A more detailed
analysis reveals that (SHC) is required to be true for Lemma 2.3 with
$\mathcal{H}_{R(\bm{A}\bm{B}),\mathbb{Z}^{n}}(C(\bm{A}\bm{B}))\leq 1$. This
still holds under the following Weak Hilbert basis conjecture.

Weak Hilbert basis conjecture. Given a cone $C(\bm{A})$ and $-\bm{a}\in
C(\bm{A})^{*}\cap\mathbb{Z}^{n}$. Let $\bm{h}\in C(\bm{A})$ be a Hilbert basis
element with respect to $\mathbb{Z}^{n}$. Then

$\displaystyle-\bm{a}^{T}\bm{h}\leq\Delta(\bm{a}).$

Since the rational case $\bm{a}\in\mathbb{Q}^{n}$ follows directly from the
integral case, we can restrict ourselves in the Weak conjecture to
$\bm{a}\in\mathbb{Z}^{n}$. Lemma 2.3 shows that the Strong version implies the
Weak version, hence the name. However, both conjectures are equivalent if $C$
is simplicial. That is why,
$\operatorname{conv}\\{\bm{0},\bm{r}^{1},...,\bm{r}^{n}\\}$ from (14) is a
simplex and the facet containing $\bm{r}^{1},...,\bm{r}^{n}$ is defined by a
facet normal in $C(\bm{A})^{*}\cap\mathbb{Q}^{n}$. Hence, we have equality in
(14).
A special case of the pyramid where all vertex cones are simplicial is the
simplex. In that case, we are able to show more. Theorem 1.2 applied to the
simplex case gives us the following quantities. We have
$\Lambda=\bm{A}^{-1}\mathbb{Z}^{n}$ and the Hilbert basis elements of
$C(\bm{A})$ with respect to $\Lambda$ are the columns of $\bm{A}^{-1}$. In
particular, all Hilbert basis elements of $C(\bm{A})$ are trivial. Further,
$\gcd(\bm{A})=\Delta(\bm{A})$ and the fact that $\bm{A}^{-1}$ is a basis of
$\Lambda$ imply that (SHC) needs to hold for the cone $C(\bm{I}_{n})$. This is
true by Corollary 1.8.

###### Proof of Corollary 1.3.

Recall that $P=P(\bm{A},\bm{a},\bm{b},b_{a})$ is a simplex with
$|\det\bm{A}|=\delta$. Let $\bm{h}^{1},...,\bm{h}^{n}$ be the Hilbert basis
elements of $C(\bm{A})$ with respect to $\Lambda$. We denote by

$\displaystyle\bm{v},\bm{v}-\lambda_{1}\bm{h}^{1},...,\bm{v}-\lambda_{n}\bm{h}^{n}$

the vertices of $P$ for some positive scalars $\lambda_{1},...,\lambda_{n}$.
We prove the corollary by contradiction. Assume that
$w^{\mathcal{F}}(P)\geq\operatorname{diam}(\Lambda/\mathbb{Z}^{n})$. This
yields

$\displaystyle\operatorname{diam}(\Lambda/\mathbb{Z}^{n})$ $\displaystyle\leq
w^{\bm{A}_{i,\cdot}^{T}}(P)=\bm{A}_{i,\cdot}\bm{v}-\bm{A}_{i,\cdot}(\bm{v}-\lambda_{i}\bm{h}^{i})=\lambda_{i}$

for all $i=1,...,n$ since the Hilbert basis elements are columns of
$\bm{A}^{-1}$. The lower bound on the scalars implies

$\displaystyle\bm{v}-\underbrace{\operatorname{conv}\\{\bm{0},\operatorname{diam}(\Lambda/\mathbb{Z}^{n})\bm{h}^{1},...,\operatorname{diam}(\Lambda/\mathbb{Z}^{n})\bm{h}^{n}\\}}_{=:M}\subseteq
P.$ (18)

We observe that

$\displaystyle M=\left\\{\bm{x}\in\mathbb{R}^{n}:\begin{pmatrix}\bm{A}\\\
-\bm{1}^{T}\bm{A}\end{pmatrix}\bm{x}\leq\begin{pmatrix}\bm{0}\\\
\operatorname{diam}(\Lambda/\mathbb{Z}^{n})\end{pmatrix}\right\\},$

i.e., $M$ is a simplex with all $n\times n$ minors being $\pm\det\bm{A}$. This
results in

$\displaystyle
w^{-\bm{A}^{T}\bm{1}}(\bm{v}-M)=\operatorname{diam}(\Lambda/\mathbb{Z}^{n}).$

From Theorem 1.2 it follows that there is an integer point in $\bm{v}-M$.
Further, the inclusion (18) implies that $P$ contains an integer point, a
contradiction to the lattice-freeness. ∎

We finish this section by providing examples where the inequality (4) of
Theorem 1.2 is tight for arbitrary finite abelian groups.
Let

$\displaystyle\mathbb{Z}/s_{1}\mathbb{Z}\oplus...\oplus\mathbb{Z}/s_{N}\mathbb{Z}=G$

be an invariant decomposition. In dependence of $G$ we define the
$N$-dimensional simplex

$\displaystyle
S^{G}=\left\\{\bm{x}\in\mathbb{R}^{N}:\begin{pmatrix}s_{1}&0&\ldots&0\\\
0&s_{2}&&\\\ \vdots&&\ddots&\\\ 0&&&s_{N}\\\
-s_{1}&-s_{2}&\ldots&-s_{N}\end{pmatrix}\bm{x}\leq\begin{pmatrix}-1\\\ -1\\\
\vdots\\\ -1\\\ (\sum_{i=1}^{N}s_{i})-1\end{pmatrix}\right\\}.$

Here the $N\times N$ diagonal matrix corresponds to $\bm{A}$ and the last row
to $\bm{a}^{T}$ from Theorem 1.2. In particular, we have

$\displaystyle\gcd(\bm{A})=\prod_{i=1}^{N}s_{i}=\Delta.$

Further, our vertex and Hilbert basis elements of $C$ with respect to
$\Lambda$ have the following form

$\displaystyle\bm{v}=\begin{pmatrix}-\frac{1}{s_{1}}\\\ -\frac{1}{s_{2}}\\\
\vdots\\\
-\frac{1}{s_{N}}\end{pmatrix},\bm{h}^{1}=\begin{pmatrix}\frac{1}{s_{1}}\\\
0\\\ \vdots\\\ 0\end{pmatrix},...,\bm{h}^{N}=\begin{pmatrix}0\\\ \vdots\\\
0\\\ \frac{1}{s_{N}}\end{pmatrix}.$

By construction

$\displaystyle\bm{v}-(s_{1}-1)\bm{h}^{1}-...-(s_{N}-1)\bm{h}^{N}\in\mathbb{Z}^{N}$

is the integer point which minimizes the coefficient sum. Note that

$\displaystyle(\sum_{i=1}^{N}s_{i})-1=\bm{a}^{T}(\bm{v}-(s_{1}-1)\bm{h}^{1}-...-(s_{N}-1)\bm{h}^{N})-1.$

Hence, $S^{G}$ is lattice-free. The facet width in the direction of the last
row is

$\displaystyle
w^{\bm{a}}(S^{G})=(\sum_{i=1}^{N}s_{i})-1-\bm{a}^{T}\bm{v}=\operatorname{diam}(G)-1.$

This follows from Theorem 2.1.

###  2.1 Lattice width of lattice-free simplices

The diameter $\operatorname{diam}(\Lambda/\mathbb{Z}^{n})$ in Corollary 1.3 is
usually significantly smaller than $\delta-1$. We strengthen (13) by
incorporating the number of cyclic groups in the invariant decomposition.

######  Lemma 2.4.

Let $G=\mathbb{Z}/s_{1}\mathbb{Z}\oplus...\oplus\mathbb{Z}/s_{N}\mathbb{Z}$ be
an invariant decomposition with $N\in\mathbb{N}_{\geq 1}$ and
$\prod_{i=1}^{N}s_{i}=\delta$. We have

$\displaystyle\operatorname{diam}(G)\leq\left\lfloor\frac{\delta}{2^{N-1}}+N-2\right\rfloor.$

###### Proof.

Theorem 2.1 states

$\displaystyle\operatorname{diam}(G)=\sum_{i=1}^{N}s_{i}-1.$ (19)

We prove the claim by induction on $N$. The group $G$ is cyclic if $N=1$ and
therefore $\operatorname{diam}(G)=\delta-1$.
Let $N\geq 2$ and $s_{1},...,s_{N}$ be the invariant factors which attain
(19). Set

$\displaystyle\tilde{G}=\mathbb{Z}/s_{1}\mathbb{Z}\oplus...\oplus\mathbb{Z}/s_{N-1}\mathbb{Z}.$

This is another invariant decomposition with

$\displaystyle\operatorname{diam}(\tilde{G})\leq\left\lfloor\frac{\delta}{2^{N-2}s_{N}}+N-3\right\rfloor$

by induction hypothesis. We get

$\displaystyle\operatorname{diam}(G)=\sum_{i=1}^{N}s_{i}-1\leq\frac{\delta}{2^{N-2}s_{N}}+N-3+s_{N}-1=:f(s_{N})$

By calculating first and second derivatives of the function
$f:\left[2,\frac{\delta}{2^{N-1}}\right]\to\mathbb{R}$, which is defined
above, we observe that $f$ attains its maxima on the boundary. The claim
follows from the integrality of $\operatorname{diam}(G)$. ∎

This bound is sharp if $\delta=2^{N}$. However, in other cases it is still far
away from being optimal. Nevertheless, it serves our purposes as we see in the
proof of Theorem 1.4.
Furthermore, we analyze the relationship between the cardinality of the
generating set and its diameter for cyclic groups. Another theorem from
Klopsch and Lev [11] helps us again. They define

$\displaystyle\phi_{j}(G)=\max\\{|H|:H\subseteq G,H\text{ generates
}G,j\leq\operatorname{diam}_{H}(G)\\}$

for a finite abelian group $G$ and $j\in\mathbb{N}$. This quantity measures
the maximal cardinality among all generating sets of $G$ which need at least
$j$ sums to generate $G$. Moreover, the definition immediately implies
$\phi_{1}(G)\geq\phi_{2}(G)\geq...\geq\phi_{\operatorname{diam}(G)}(G)$. We
have the following exact formula if $G$ is cyclic.

######  Theorem 2.5 ([11], Theorem 2.5).

Let $\delta\in\mathbb{N}_{\geq 3}$ and $j\in[2,\delta-1]$. Then

$\displaystyle\phi_{j}(\mathbb{Z}/\delta\mathbb{Z})=\max\left\\{\frac{\delta}{d}\left(\left\lfloor\frac{d-2}{j-1}\right\rfloor+1\right):d\textnormal{
divides }\delta,d\geq j+1\right\\}.$

This is all we need for the proof.

###### Proof of Theorem 1.4.

Recall that $P=P(\bm{A},\bm{a},\bm{b},b_{a})$ is a simplex with
$|\det\bm{A}|=\delta$. If $\delta=1$, one of the vertices is integral by
Cramer’s rule. Further, if $\delta=2$, the claim follows from Corollary 1.3.
Thus, we assume $\delta\geq 3$.
We set $\Lambda=\bm{A}^{-1}\mathbb{Z}^{n}$ and denote by
$\bm{h}^{1},...,\bm{h}^{n}$ the columns of $\bm{A}^{-1}$. Further, we write
$H=\\{\bm{h}^{1},...,\bm{h}^{n}\\}/\mathbb{Z}^{n}$. Note, Lemma 2.4 and
Corollary 1.3 imply that we may assume that $\Lambda/\mathbb{Z}^{n}$ is a
cyclic group, i.e.,

$\displaystyle\Lambda/\mathbb{Z}^{n}\cong\mathbb{Z}/\delta\mathbb{Z}.$

Further, let $k$ denote the number of different cosets in $H$. We want to
identify the maximal $k$ such that we need strictly more than
$\lfloor\frac{\delta}{2}\rfloor$ sums to generate the group. This can be done
by the exact formula in Theorem 2.5 which yields

$\displaystyle\phi_{\lfloor\frac{\delta}{2}\rfloor+1}(\mathbb{Z}/\delta\mathbb{Z})=\left(\left\lfloor\frac{\delta-2}{\left\lfloor\frac{\delta}{2}\right\rfloor}\right\rfloor+1\right)=2.$
(20)

Hence, for $k\geq 3$ we know that $\lfloor\frac{\delta}{2}\rfloor$ sums
suffice to generate the group, i.e.,
$\operatorname{diam}_{H}(\Lambda/\mathbb{Z}^{n})\leq\lfloor\frac{\delta}{2}\rfloor$.
Therefore, assume that $k\leq 2$. Observe that $k=2$ already implies that one
of the two cosets is trivial. Otherwise we would be able to add the trivial
coset to our generating set and obtain a set with cardinality three which
contradicts the maximality in (20).
So we can assume that without loss of generality

$\displaystyle\bm{h}^{1}+\mathbb{Z}^{n}=...=\bm{h}^{l}+\mathbb{Z}^{n}$

belong to the non-trivial coset for $l=2,...,n$. Hence,
$\bm{h}^{l+1}+\mathbb{Z}^{n},...,\bm{h}^{n}+\mathbb{Z}^{n}$ are trivial, i.e.,
$\bm{h}^{l+1},...,\bm{h}^{n}$ are integral. If $l=n$, then $H$ contains only
one coset. We exploit this structure to construct a flat direction for these
special simplices.
Define the matrix

$\displaystyle\tilde{\bm{A}}^{-1}=(\bm{h}^{1},\bm{h}^{2}-\bm{h}^{1},...,\bm{h}^{l}-\bm{h}^{1},\bm{h}^{l+1},...,\bm{h}^{n}).$

Every column apart from the first one is integral. Furthermore, the
construction guarantees $|\det\bm{A}^{-1}|=|\det\tilde{\bm{A}}^{-1}|$. Let
$\bm{T}$ be the transformation matrix which scales the first column of
$\tilde{\bm{A}}^{-1}$ by $\delta$ and leaves the rest unchanged. Thus,
$\tilde{\bm{A}}^{-1}\bm{T}\in\mathbb{Z}^{n\times n}$ and

$\displaystyle|\det\tilde{\bm{A}}^{-1}\bm{T}|=1,$

so $\tilde{\bm{A}}^{-1}\bm{T}\in GL(n,\mathbb{Z})$. Therefore, the inverse is
unimodular, too, and we get

$\displaystyle\bm{d}=\frac{1}{\delta}(\bm{A}_{1,\cdot}+...+\bm{A}_{l,\cdot})=\bm{e}_{1}^{T}\bm{T}^{-1}\tilde{\bm{A}}$

is integral. We show that $\bm{d}$ is a flat direction. For this purpose, let

$\displaystyle\bm{v},\bm{v}-\lambda_{1}\bm{h}^{1},...,\bm{v}-\lambda_{n}\bm{h}^{n}$

be the vertices of $P$ with $\bm{v}$ being the vertex tight at the
inequalities defined by $\bm{A}$ and $\lambda_{1},...,\lambda_{n}$ positive
scalars. By construction we have

$\displaystyle\bm{d}\bm{h}^{i}=0$

for $i=l+1,...,n$. Without loss of generality let
$\bm{v}-\lambda_{1}\bm{h}^{1}$ be the vertex which minimizes
$\bm{d}^{T}\bm{x}$. Recall, that we have

$\displaystyle\lambda_{1}=\bm{A}_{1,\cdot}\bm{v}-\bm{A}_{1,\cdot}(\bm{v}-\lambda_{1}\bm{h}^{1})=w^{\bm{A}_{1,\cdot}^{T}}(P)<\delta-1$

by Corollary 1.3. This yields

$\displaystyle
w^{\bm{d}^{T}}(P)=\bm{d}\bm{v}-\bm{d}(\bm{v}-\lambda_{1}\bm{h}^{1})=\frac{\lambda_{1}}{\delta}<1-\frac{1}{\delta}.$

In summary, all simplices with

$\displaystyle\operatorname{diam}(\Lambda/\mathbb{Z}^{n})>\left\lfloor\frac{\delta}{2}\right\rfloor$

attain a flat direction with $w(P)<1$. Thus, the claim follows. ∎

##  3 Towards a proof of (SHC)

We begin our discussions by showing that it is possible to impose more
structure on (SHC) without loss of generality.

###  3.1 Reduction to full-dimensional version

Let us introduce the following geometric object which plays a key role in
proving Theorem 1.5. For $\bm{y}\in C(\bm{A})$ the spindle is defined by

$\displaystyle
S(\bm{y}):=\\{\bm{x}\in\mathbb{R}^{n}:\bm{0}\leq\bm{A}\bm{x}\leq\bm{A}\bm{y}\\}.$

We can reformulate the irreducibility of Hilbert basis elements in terms of a
spindle property. By definition we have $\bm{h}\in C(\bm{A})$ is a Hilbert
basis element with respect to a lattice $\Lambda$ if and only if

$\displaystyle S(\bm{h})\cap\Lambda=\\{\bm{0},\bm{h}\\}.$ (21)

We refer to our problem as full-dimensional for a given Hilbert basis element
$\bm{h}\in C(\bm{A})$ if $\dim(S(\bm{h}))=n$ where $\dim(S(\bm{h}))$ denotes
the dimension of the linear space spanned by the elements in $S(\bm{h})$. This
holds if and only if $\bm{h}\in\operatorname{int}(C(\bm{A}))$.

Full-dimensional Strong Hilbert basis conjecture. Let $C(\bm{A})$ be a (full-
dimensional) cone, $\bm{h}\in\operatorname{int}(C(\bm{A}))$ a Hilbert basis
element of $C(\bm{A})$ with respect to $\mathbb{Z}^{n}$. Then

$\displaystyle\mathcal{H}_{R(\bm{A}),\mathbb{Z}^{n}}(C(\bm{A}))\leq 1.$

Furthermore, we can rewrite $\bm{r}\in R(\bm{A})$ with
$\bm{A}_{I,\cdot}\bm{r}=\bm{0}$ in terms of the adjugate matrix. Let
$\bm{A}_{j,\cdot}$ be a row with $\bm{A}_{j,\cdot}\bm{r}>0$. Then

$\displaystyle\bm{r}=|\det\bm{A}_{J,\cdot}|\bm{A}_{J,\cdot}^{-1}\bm{e}_{n}=\operatorname{sign}(\det\bm{A}_{J,\cdot})\operatorname{adj}(\bm{A}_{J,\cdot})\bm{e}_{n}$
(22)

for $J=I\cup\\{j\\}$ where without loss of generality the last row of
$\bm{A}_{J,\cdot}$ corresponds to the row indexed by $j$. Note that the
representation does not depend on the choice of $\bm{A}_{j,\cdot}$.
Next, we reduce the general version to the full-dimensional one.

######  Proposition 3.1.

The full-dimensional conjecture implies the (SHC).

###### Proof of Proposition 3.1.

Given a cone $C(\bm{A})$, which is not necessarily full-dimensional. Let
$\bm{h}\in C(\bm{A})$ be in the (relative) interior of a $k$-dimensional face
of $C(\bm{A})$ with $1\leq k\leq n-1$, i.e., there exists $I\subseteq[m]$ with
$|I|=n-k$, $\bm{A}_{I,\cdot}\bm{h}=\bm{0}$,
$\operatorname{rank}(\bm{A}_{I,\cdot})=n-k$ and $\gcd(\bm{A}_{I,\cdot})$
maximal among all rows describing the $k$-dimensional face. We define by

$\displaystyle
F=C(\bm{A})\cap\\{\bm{x}\in\mathbb{R}^{n}:\bm{A}_{I,\cdot}\bm{x}=\bm{0}\\}$

this $k$-face. Surely, $\bm{h}$ is a Hilbert basis element of $F$ with respect
to $\mathbb{Z}^{n}$ if and only if the same holds for the cone $C(\bm{A})$.
In the following, we transform $F$ into coordinate hyperplanes, project $F$
onto the non-zero coordinates and check that the scaling works out.
There exists a unimodular transformation $\bm{U}\in GL(n,\mathbb{Z})$, such
that

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

for some invertible matrix $\bm{H}\in\mathbb{Z}^{(n-k)\times(n-k)}$, e.g., by
transforming $\bm{A}_{I,\cdot}$ into Hermite normal form. Moreover, one can
show

$\displaystyle|\det\bm{H}|=\gcd(\bm{A}_{I,\cdot})$ (23)

via the Smith normal form, compare with the proof of Lemma 2.2. Since (SHC) is
invariant under unimodular transformations, we can work with the face

$\displaystyle\bm{U}^{-1}F\subseteq\\{\bm{x}\in\mathbb{R}^{n}:x_{1}=...=x_{n-k}=0\\}.$

From now on, we assume that our face $F$ has the form from above, i.e., lies
in the first $n-k$ coordinate hyperplanes.
Let $\tilde{F}$ be the projection of $F$ onto the last $k$ coordinates. So
$\tilde{F}$ is $k$-dimensional. As a result, we have

$\displaystyle\tilde{F}=\\{\bm{x}\in\mathbb{R}^{k}:\bm{A}_{\cdot,[n]\backslash[n-k]}\bm{x}\geq\bm{0}\\}=C(\bm{A}_{\cdot,[n]\backslash[n-k]}).$

The cone $\tilde{F}$ is defined by the last $k$ columns of $\bm{A}$. Further,
each point $\bm{x}\in F$ with $\bm{x}^{T}=(\bm{0},\tilde{\bm{x}}^{T})$
corresponds one-to-one to $\tilde{\bm{x}}\in\tilde{F}$. Hence, $\bm{h}$ is a
Hilbert basis element of $F$ with respect to $\mathbb{Z}^{n}$ if and only if
$\tilde{\bm{h}}$ is a Hilbert basis element of $\tilde{F}$ with respect to
$\mathbb{Z}^{k}$. Furthermore,
$\tilde{\bm{h}}\in\operatorname{int}(\tilde{F})$.
It is left to check the scaling of our new normalized generators. Each
normalized generator $\bm{r}$ of $F$ corresponds to a normalized generator
$\tilde{\bm{r}}$ of $\tilde{F}$. Let

$\displaystyle\bm{r}=|\det\bm{A}_{J,\cdot}|\bm{A}_{J,\cdot}^{-1}\bm{e}_{n}=\operatorname{sign}(\det\bm{A}_{J,\cdot})\operatorname{adj}(\bm{A}_{J,\cdot})\bm{e}_{n}$

for some $J\subseteq[m]$.
Suppose $I\subseteq J$ and let $\tilde{I}=J\backslash I$. This implies that
the matrix $\bm{A}_{J,\cdot}$ is up to row permutations of the following form

$\displaystyle\bm{A}_{J,\cdot}=\begin{pmatrix}\bm{H}&\bm{0}\\\
\star&\bm{A}_{\tilde{I},[n]\backslash[n-k]}\end{pmatrix}.$

So we get

$\displaystyle\operatorname{adj}(\bm{A}_{J,\cdot})\bm{e}_{n}=\det\bm{H}\begin{pmatrix}\bm{0}\\\
\operatorname{adj}(\bm{A}_{\tilde{I},[n]\backslash[n-k]})\bm{e}_{k}\end{pmatrix}$

by using the generalized Laplace expansion along the first $n-k$ rows.
Together with the definition of $\bm{r}$ this yields

$\displaystyle\bm{r}$
$\displaystyle=\operatorname{sign}(\det\bm{A}_{J,\cdot})\operatorname{adj}(\bm{A}_{J,\cdot})\bm{e}_{n}$
$\displaystyle=\operatorname{sign}(\det\bm{A}_{J,\cdot})\det\bm{H}\begin{pmatrix}\bm{0}\\\
\operatorname{adj}(\bm{A}_{\tilde{I},[n]\backslash[n-k]})\bm{e}_{k}\end{pmatrix}$
$\displaystyle=\operatorname{sign}(\bm{A}_{\tilde{I},[n]\backslash[n-k]})|\det\bm{H}|\begin{pmatrix}\bm{0}\\\
\operatorname{adj}(\bm{A}_{\tilde{I},[n]\backslash[n-k]})\bm{e}_{k}\end{pmatrix}.$

The normalized generator which corresponds to $\bm{r}$ is defined by

$\displaystyle\tilde{\bm{r}}=\operatorname{sign}(\bm{A}_{\tilde{I},[n]\backslash[n-k]})\operatorname{adj}(\bm{A}_{\tilde{I},[n]\backslash[n-k]})\bm{e}_{k}.$

Hence, the last $k$ coordinates of $\bm{r}$ are $|\det\bm{H}|\tilde{\bm{r}}$.
Solving the full-dimensional version yields non-negative coefficients
$\lambda_{1},...,\lambda_{t}$ which sum up to at most one and generate
$\tilde{\bm{h}}$ with the respective normalized generators of $\tilde{F}$. We
obtain

$\displaystyle\bm{h}=\frac{1}{|\det\bm{H}|}\sum_{i=1}^{t}\lambda_{i}\bm{r}^{i}\quad\text{with}\quad\frac{1}{|\det\bm{H}|}\sum_{i=1}^{t}\lambda_{i}\leq\frac{1}{|\det\bm{H}|}\leq
1.$

It is left to show that we can choose $I\subseteq J$. For each $n-1$ linearly
independent rows which define $\bm{r}$ and are indexed by $K$ we can partition
$K$ into sets $K_{1}$ and $K_{2}$ where the rows of $\bm{A}$ indexed by
$K_{1}$ define $F$. The rows of $\bm{A}_{K_{1},\cdot}$ are a linear
combination of the rows of $(\bm{H},\bm{0})$. Hence, there exists a matrix
$\bm{Q}\in\mathbb{Q}^{(n-k)\times(n-k)}$ with

$\displaystyle\bm{A}_{K_{1},\cdot}=\bm{Q}(\bm{H},\bm{0}).$

Recall that $\gcd(\bm{A}_{I,\cdot})=|\det\bm{H}|$, see (23). Since
$\gcd(\bm{A}_{I,\cdot})$ is by choice maximal among all representations of $F$
with the rows of $\bm{A}$, we have $|\det\bm{Q}|\leq 1$. Applying the
generalized Laplace expansion along the rows indexed by $K_{1}$ yields

$\displaystyle\gcd(\bm{A}_{K,\cdot})=|\det\bm{Q}||\det\bm{H}|\gcd(\bm{A}_{K_{2},[n]\backslash[n-k]})=|\det\bm{Q}|\gcd(\bm{A}_{I,\cdot})\gcd(\bm{A}_{K_{2},[n]\backslash[n-k]}).$

As $|\det\bm{Q}|\leq 1$ and $|\det\bm{Q}|=1$ if $K_{1}=I$, we can choose
$K_{1}=I$ to maximize the expression above. This yields $I\subseteq J$.

∎

###  3.2 Proof for bimodular cones

In this subsection we prove Theorem 1.5. In order to do so, we need three
lemmas which are valid for the more general class of $\Delta$-modular cones.
Let $\bm{h}\in C(\bm{A})$ be a Hilbert basis element with respect to
$\mathbb{Z}^{n}$. In the following, we assume

$\displaystyle\bm{h}=\sum_{i=1}^{t}\lambda_{i}\bm{r}^{i}$

for non-negative scalars $\lambda_{1},...,\lambda_{t}$ and
$\bm{r}^{1},...,\bm{r}^{t}\in R(\bm{A})$. If $\bm{h}$ is non-trivial, we
already know that $\lambda_{i}<\frac{1}{\gcd(\bm{r}^{i})}$ for all
$i=1,...,t$, as otherwise we can subtract
$\frac{1}{\gcd(\bm{r}^{i})}\bm{r}^{i}$ from $\bm{h}$ and stay in the cone. The
next lemma strengthens this bound by incorporating boundedness of the right-
hand side.

######  Lemma 3.2.

Let $C(\bm{A})$ be a $\Delta$-modular cone and $\bm{h}$ a non-trivial Hilbert
basis element of $C(\bm{A})$ with respect to $\mathbb{Z}^{n}$ such that
$\bm{h}=\sum_{i=1}^{t}\lambda_{i}\bm{r}^{i}$ for non-negative scalars
$\lambda_{1},...,\lambda_{t}$ and $\bm{r}^{1},...,\bm{r}^{t}\in R(\bm{A})$.
Then

$\displaystyle\lambda_{i}\leq\frac{1}{\gcd(\bm{r}^{i})}-\frac{1}{\|\bm{A}\bm{r}^{i}\|_{\infty}}\leq\frac{1}{\gcd(\bm{r}^{i})}-\frac{1}{\Delta}$

for $i=1,...,t$.

###### Proof.

Fix some index $i\in[t]$ and denote

$\displaystyle\tilde{\bm{r}}^{i}=\frac{1}{\gcd(\bm{r}^{i})}\bm{r}^{i}\in\mathbb{Z}^{n}.$

We have

$\displaystyle\bm{A}\bm{h}=\sum_{j=1}^{t}\lambda_{j}\bm{A}\bm{r}^{j}\geq\lambda_{i}\bm{A}\bm{r}^{i}=\underbrace{\gcd(\bm{r}^{i})\lambda_{i}}_{=:\tilde{\lambda}_{i}}\bm{A}\tilde{\bm{r}}^{i}.$

Since the left side of the inequality is integral, we conclude

$\displaystyle\bm{A}\bm{h}\geq\left\lceil\tilde{\lambda}_{i}\bm{A}\tilde{\bm{r}}^{i}\right\rceil,$

where we apply the ceiling function componentwise. If

$\displaystyle\left\lceil\tilde{\lambda}_{i}\bm{A}\tilde{\bm{r}}^{i}\right\rceil=\bm{A}\tilde{\bm{r}}^{i},$

we get $\bm{h}-\tilde{\bm{r}}^{i}\in C(\bm{A})\cap\mathbb{Z}^{n}$. This yields
$\bm{h}=\tilde{\bm{r}}^{i}$, since $\bm{h}$ is a Hilbert basis element and
$\tilde{\bm{r}}^{i}\neq\bm{0}$, which contradicts the requirement that
$\bm{h}$ is non-trivial. Hence, there exists an index $k\in[m]$ such that

$\displaystyle\tilde{\lambda}_{i}\left(\bm{A}\tilde{\bm{r}}^{i}\right)_{k}\leq\left(\bm{A}\tilde{\bm{r}}^{i}\right)_{k}-1.$

After rearranging we get

$\displaystyle\lambda_{i}=\frac{\tilde{\lambda}_{i}}{\gcd(\bm{r}^{i})}\leq\frac{\|\bm{A}\tilde{\bm{r}}^{i}\|_{\infty}-1}{\|\bm{A}\tilde{\bm{r}}^{i}\|_{\infty}\gcd(\bm{r}^{i})}=\frac{1}{\gcd(\bm{r}^{i})}-\frac{1}{\|\bm{A}\bm{r}^{i}\|_{\infty}}.$

Applying (3) proves the second inequality. ∎

An immediate implication of Lemma 3.2 is that $\bm{r}\in R(\bm{A})$ with
$\gcd(\bm{r})=\Delta$ does not contribute to the positive combination if
$\bm{h}$ is non-trivial. Specifically, each Hilbert basis element is trivial
if $\Delta=1$, which reproves the statement in that case. Furthermore, all
normalized generators which contribute to the positive combination are
primitive if $\Delta\in\\{2,3\\}$. That is why, $\gcd(\bm{r})$ divides
$\|\bm{A}\bm{r}\|_{\infty}$ which implies
$\gcd(\bm{r})=\|\bm{A}\bm{r}\|_{\infty}$ if $\Delta\in\\{2,3\\}$. Hence, we do
not run into the subtlety which occurred when we defined the normalized
generators in the bimodular case.
In the next lemma we investigate the case when $\bm{h}$ is generated by two
normalized generators.

######  Lemma 3.3.

Let $C(\bm{A})$ be a $\Delta$-modular cone and $\bm{h}$ a Hilbert basis
element of $C(\bm{A})$ with respect to $\mathbb{Z}^{n}$ which is given by
$\bm{h}=\lambda_{1}\bm{r}^{1}+\lambda_{2}\bm{r}^{2}$ with
$\lambda_{1},\lambda_{2}>0$ and $\bm{r}^{1},\bm{r}^{2}\in R(\bm{A})$. Then

$\displaystyle\lambda_{i}\geq\frac{1}{\|\bm{A}\bm{r}^{i}\|_{\infty}}\geq\frac{1}{\Delta}$

for $i=1,2$.

###### Proof.

Choose without loss of generality $i=1$. Assume, for sake of a contradiction,
that $\lambda_{1}<\frac{1}{\|\bm{A}\bm{r}^{1}\|_{\infty}}$. This implies
$\left(\lambda_{1}\bm{A}\bm{r}^{1}\right)_{k}\notin\mathbb{Z}$ for all
$k\in[m]$. Hence,

$\displaystyle\operatorname{supp}(\bm{A}\bm{r}^{1})\subseteq\operatorname{supp}(\bm{A}\bm{r}^{2}).$

Since $\bm{A}\bm{r}^{2}$ is (inclusionwise) minimal, we have equality above
which implies $\bm{r}^{1}=\bm{r}^{2}$, a contradiction. Again, the second
inequality follows from (3). ∎

Lastly, we prove a statement about cones with special integer hull.

######  Lemma 3.4.

Let $C=C(\bm{A})$ be a cone, $\bm{v}\in\mathbb{Q}^{n}$ and $\bm{z}\in\bm{v}+C$
the only vertex of the integer hull
$\operatorname{conv}((\bm{v}+C)\cap\mathbb{Z}^{n})$. Then

$\displaystyle\operatorname{conv}((\bm{v}+C)\cap\mathbb{Z}^{n})=\bm{z}+C.$

###### Proof.

After translation we can assume that $\bm{z}=\bm{0}$.
Since $C$ is defined by an integral matrix, all extreme rays contain integer
points. This implies already
$\operatorname{conv}((\bm{v}+C)\cap\mathbb{Z}^{n})\supseteq C$. Assume there
exists

$\displaystyle\bm{v}+\bm{x}\in\operatorname{conv}((\bm{v}+C)\cap\mathbb{Z}^{n})\backslash
C.$

Let $\bm{a}$ be some row of $\bm{A}$ with $\bm{a}^{T}(\bm{v}+\bm{x})<0$.
Consider the following linear optimization problem and note that

$\displaystyle\bm{a}^{T}\bm{v}\leq\min_{\bm{y}\in\operatorname{conv}((\bm{v}+C)\cap\mathbb{Z}^{n})}\bm{a}^{T}\bm{y}\leq\bm{a}^{T}(\bm{v}+\bm{x})<0.$

This problem is bounded and $\bm{0}$ cannot be a solution. So the optimum is
attained at a vertex of $\operatorname{conv}((\bm{v}+C)\cap\mathbb{Z}^{n})$
different from $\bm{z}=\bm{0}$. This contradicts our assumption. ∎

In the following proof of Theorem 1.5 we exploit a result regarding the
integer hull of bimodular polytopes proven by Veselov and Chirkov [21].
Here $P$ is a polytope defined by an integral constraint matrix and integral
right-hand side and for a vertex $\bm{v}\in P$ we denote by $C^{\bm{v}}$ the
vertex cone of $\bm{v}$. Furthermore, an edge is called incident to a vertex
if this edge contains the vertex. Below we denote two vertices of a polytope
which share an edge as adjacent vertices.

######  Theorem 3.5 ([21], Theorem 2).

Let $P(\bm{A},\bm{b})$ be a full-dimensional bimodular polytope and $\bm{v}$ a
vertex of $P(\bm{A},\bm{b})$. Then each vertex of
$\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ lies on an edge of
$P(\bm{A},\bm{b})$ incident to $\bm{v}$.

We are now in the position to prove our main result.

###### Proof of Theorem 1.5.

Firstly, we assume that $\bm{h}$ is a positive combination of precisely two
normalized generators. By Lemma 3.2 and Lemma 3.3 the two coefficients need to
be $\frac{1}{2}$. It is left to show that every $\bm{h}$ can be generated by
at most two normalized generators.
Recall from (21) that the spindle $S(\bm{h})$ satisfies
$S(\bm{h})\cap\mathbb{Z}^{n}=\\{\bm{0},\bm{h}\\}$. Further, we can assume

$\displaystyle\bm{h}\in\operatorname{int}(C(\bm{A}))$ (24)

by Proposition 3.1. As $\bm{h}$ is non-trivial and lies in the interior of
$C(\bm{A})$, the spindle $S(\bm{h})$ is a full-dimensional bimodular polytope
with $\dim(S(\bm{h}))=n\geq 2$. Therefore, there exists a vertex $\bm{v}\in
S(\bm{h})$ which is neither $\bm{0}$ nor $\bm{h}$. We claim that $\bm{v}$ is
adjacent to $\bm{0}$ and $\bm{h}$. This implies that $\bm{v}$ and
$\bm{h}-\bm{v}$ lie both on extreme rays of $C(\bm{A})$ by symmetry of
$S(\bm{h})$. So we have $\bm{h}=(\bm{h}-\bm{v})+\bm{v}$, i.e., $\bm{h}$ is the
$\frac{1}{2}$ combination of precisely two normalized generators,
$2(\bm{h}-\bm{v})$ and $2\bm{v}$. This completes the proof.
It remains to show that $\bm{v}$ has to be adjacent to $\bm{0}$ and $\bm{h}$.
Assume this is not the case. Let $C^{\bm{v}}$ be the vertex cone at $\bm{v}$.
The integer hull $\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ contains
$\bm{0}$ and $\bm{h}$. From Theorem 3.5 it follows that the vertices of
$\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ are contained in
$S(\bm{h})\cap\mathbb{Z}^{n}=\\{\bm{0},\bm{h}\\}$. Hence,
$\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ has at most two vertices,
$\bm{0}$ and $\bm{h}$. Further, the vertices of
$\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ lie on edges of
$S(\bm{h})$ incident to $\bm{v}$ by Theorem 3.5. This combined with our
assumption that $\bm{v}$ is not adjacent to $\bm{0}$ and $\bm{h}$ implies that
$\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ contains exactly one
vertex. Without loss of generality let this be $\bm{0}$. Using Lemma 3.4 we
observe

$\displaystyle\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})=C^{\bm{v}}-\bm{v}.$
(25)

Since $\bm{v}\neq\bm{0}$, there exists a row $\bm{a}$ of $\bm{A}$ with
$\bm{a}^{T}\bm{v}=\bm{a}^{T}\bm{h}>0$, where we use (24) for the strict
inequality. Combining this with (25) we get that $\bm{a}^{T}\bm{x}\leq 0$ is
an inequality of the integer hull
$\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$. However,
$\bm{h}\in\operatorname{conv}(C^{\bm{v}}\cap\mathbb{Z}^{n})$ implies that

$\displaystyle 0\geq\bm{a}^{T}\bm{h}>0.$

This is a contradiction. Hence, every non-integral vertex of $S(\bm{h})$ is
adjacent to $\bm{0}$ and $\bm{h}$. ∎

Note that the proof of Theorem 1.5 shows us that the diameter from $\bm{0}$ to
$\bm{h}$ of the vertex-edge graph induced by $S(\bm{h})$ is equal to two.
Moreover, let $V$ be the number of vertices of $S(\bm{h})$. Then there are
$\frac{V-2}{2}$ possibilities to express $\bm{h}$ as a positive combination of
two normalized generators.

###  3.3 Proof for simplicial cones

###### Proof of Proposition 1.6.

We start by proving the first claim. Integrality of the matrices implies
$\bm{A}\bm{B}\in\mathbb{Z}^{m\times n}$. We set
$\Lambda=\bm{B}\mathbb{Z}^{n}$. Let $\bm{B}^{-1}\bm{h}\in
C(\bm{A}\bm{B})\cap\mathbb{Z}^{n}$ be a Hilbert basis element of
$C(\bm{A}\bm{B})$ with respect to $\mathbb{Z}^{n}$. Then $\bm{h}\in
C(\bm{A})\cap\Lambda$ is a Hilbert basis element of $C(\bm{A})$ with respect
to $\Lambda$.
Since $\Lambda\subseteq\mathbb{Z}^{n}$, we have $\bm{h}\in\mathbb{Z}^{n}$.
Hence, we can express $\bm{h}$ as a non-negative integral sum of Hilbert basis
elements $\tilde{\bm{h}}^{1},...,\tilde{\bm{h}}^{s}$ with respect to
$\mathbb{Z}^{n}$. So there are $\lambda_{1},...,\lambda_{t}\in\mathbb{Z}_{\geq
0}$ with

$\displaystyle\bm{h}=\sum_{i=1}^{s}\lambda_{i}\tilde{\bm{h}}^{i}=\underbrace{\tilde{\bm{h}}^{1}+...+\tilde{\bm{h}}^{1}}_{\lambda_{1}\text{-times}}+...+\underbrace{\tilde{\bm{h}}^{s}+...+\tilde{\bm{h}}^{s}}_{\lambda_{s}\text{-times}}.$
(26)

First, we aim to bound $\lambda_{1}+...+\lambda_{s}=:\lambda$. For that
purpose, we denote by $\bm{y}^{1},...,\bm{y}^{\lambda}$ the terms in (26). We
observe that

$\displaystyle\bm{y}^{1},\bm{y}^{1}+\bm{y}^{2},...,\bm{y}^{1}+...+\bm{y}^{\lambda-1}\in(S(\bm{h})\cap\mathbb{Z}^{n})\backslash\\{\bm{0},\bm{h}\\}$

as each subsum of $\bm{y}^{1}+...+\bm{y}^{\lambda}$ satisfies
$\bm{0}\leq\bm{A}\bm{x}\leq\bm{A}\bm{h}$.
Since $\bm{h}$ is Hilbert basis element of $C(\bm{A})$ with respect to
$\Lambda$, we get $S(\bm{h})\cap\Lambda=\\{\bm{0},\bm{h}\\}$ from (21).
Therefore, none of the sums above can be in $\Lambda$. So they are non-trivial
elements in the quotient group $\mathbb{Z}^{n}/\Lambda$. The index of
$\mathbb{Z}^{n}/\Lambda$ is $|\det\bm{B}|$. If $\lambda\geq|\det\bm{B}|+1$, we
have two sums, say $\bm{y}^{1}+...+\bm{y}^{q}$ and $\bm{y}^{1}+...+\bm{y}^{p}$
with $1\leq q<p\leq\lambda-1$, which lie in the same coset. This implies

$\displaystyle\bm{y}^{q+1}+...+\bm{y}^{p}=(\bm{y}^{1}+...+\bm{y}^{p})-(\bm{y}^{1}+...+\bm{y}^{q})\in
S(\bm{h})\cap\Lambda$

and thus contradicts $S(\bm{h})\cap\Lambda=\\{\bm{0},\bm{h}\\}$. Hence,

$\displaystyle\lambda_{1}+...+\lambda_{s}=\lambda\leq|\det\bm{B}|.$ (27)

Second, we apply our assumption that (SHC) holds for $C(\bm{A})$. Therefore,
each Hilbert basis element in (26) is a convex combination of the normalized
generators of $C(\bm{A})$. Let $R(\bm{A})=\\{\bm{r}^{1},...,\bm{r}^{t}\\}$. As
(SHC) holds for $C(\bm{A})$ and with (26) and (27), we obtain

$\displaystyle\bm{h}\in|\det\bm{B}|\operatorname{conv}\\{\bm{0},\bm{r}^{1},...,\bm{r}^{t}\\}.$

Transforming back with $\bm{B}^{-1}$ results in

$\displaystyle\bm{B}^{-1}\bm{h}\in\operatorname{conv}\\{\bm{0},|\det\bm{B}|\bm{B}^{-1}\bm{r}^{1},...,|\det\bm{B}|\bm{B}^{-1}\bm{r}^{t}\\}.$
(28)

By Cramer’s rule we have
$|\det\bm{B}|\bm{B}^{-1}\bm{r}^{1},...,|\det\bm{B}|\bm{B}^{-1}\bm{r}^{t}\in\mathbb{Z}^{n}$.
It suffices to check that these vectors are the normalized generators of
$C(\bm{A}\bm{B})$ or equivalently
$R(\bm{A}\bm{B})=|\det\bm{B}|\bm{B}^{-1}R(\bm{A})$. Let $I\subseteq[m]$ denote
the indices which correspond to the $(n-1)\times n$ submatrix
$\bm{A}_{I,\cdot}$ of $\bm{A}$ in the definition of the generator
$\bm{r}^{1}$. Then we have

$\displaystyle\bm{0}=\bm{A}_{I,\cdot}\bm{r}^{1}=\bm{A}_{I,\cdot}\bm{B}(\bm{B}^{-1}\bm{r}^{1})=(\bm{A}\bm{B})_{I,\cdot}(\bm{B}^{-1}\bm{r}^{1}).$

Assume $\bm{r}^{1}$ is given as in (22). Thus,

$\displaystyle|\det\bm{B}|\bm{B}^{-1}\bm{r}^{1}=|\det\bm{A}_{I\cup\\{j\\},\cdot}\bm{B}|(\bm{A}_{I\cup\\{j\\},\cdot}\bm{B})^{-1}\bm{e}_{n}.$

Hence, $|\det\bm{B}|\bm{B}^{-1}\bm{r}^{1}$ is potentially a normalized
generator. We still need to verify that the scaling is correct. Let the index
set $K\subseteq[m]$ denote another matrix with
$\bm{0}=\bm{A}_{K,\cdot}\bm{r}^{1}$ and
$\operatorname{rank}(\bm{A}_{K,\cdot})=n-1$. Since the kernels of
$\bm{A}_{I,\cdot}$ and $\bm{A}_{K,\cdot}$ are equal, there exists
$\bm{Q}\in\mathbb{Q}^{(n-1)\times(n-1)}$ with

$\displaystyle\bm{Q}\bm{A}_{I,\cdot}=\bm{A}_{K,\cdot}$

and $|\det\bm{Q}|\leq 1$ by maximality of $\gcd(\bm{A}_{I,\cdot})$. Therefore,

$\displaystyle\gcd((\bm{A}\bm{B})_{K,\cdot})=|\det\bm{Q}|\gcd((\bm{A}\bm{B})_{I,\cdot})\leq\gcd((\bm{A}\bm{B})_{I,\cdot})$

shows that $|\det\bm{B}|\bm{B}^{-1}\bm{r}^{1}\in R(\bm{A}\bm{B})$ and in
general $R(\bm{A}\bm{B})=|\det\bm{B}|\bm{B}^{-1}R(\bm{A})$.
For the second claim we assume that $\bm{B}^{T}$ is a basis of the lattice
$\bm{A}^{T}\mathbb{Z}^{m}$. Thus, we can decompose
$\bm{A}=\tilde{\bm{A}}\bm{B}$ where $\tilde{\bm{A}}\in\mathbb{Z}^{m\times n}$
since each row of $\bm{A}$ is in $\bm{B}^{T}\mathbb{Z}^{n}$. As a result, we
obtain $C(\bm{A})=C(\tilde{\bm{A}}\bm{B})$. From the first claim it suffices
to show (SHC) for $C(\tilde{\bm{A}})$ which proves the statement since
$\gcd(\tilde{\bm{A}})=1$, see Lemma 2.2. ∎

###### Proof of Corollary 1.7.

The simplicial cone $C(\bm{A})$ is given by an invertible matrix
$\bm{A}\in\mathbb{Z}^{n\times n}$. Proposition 1.6 implies that we can assume
$1=\gcd(\bm{A})=|\det\bm{A}|$. Hence, the first claim follows immediately from
the case $\Delta(\bm{A})=1$, e.g., compare with [20, Proposition 8.1].
In order to prove the second claim, we look closer into the proof of
Proposition 1.6. Note that $\bm{h}$ lies in the relative interior of a
$k$-face of $C(\bm{A})$ if and only if $\bm{A}\bm{h}$ lies in the relative
interior of a $k$-face of $C(\bm{I}_{n})$. So we are in the special case where
the constraint matrix is the $n\times n$ unit matrix. Further, the Hilbert
basis elements of $C(\bm{I}_{n})$ are the unit vectors
$\bm{e}_{1},...,\bm{e}_{n}$. That and (26) imply

$\displaystyle\bm{A}\bm{h}=\sum_{i=1}^{n}\lambda_{i}\bm{e}_{i}.$

Moreover, the number of non-zero entries of $\bm{A}\bm{h}$ corresponds to the
dimension of the face which contains $\bm{A}\bm{h}$ in its interior as
$C(\bm{I}_{n})$ is simplicial. In other words,
$|\operatorname{supp}(\bm{A}\bm{h})|$ is the dimension we are trying to bound.
Putting everything together yields

$\displaystyle|\operatorname{supp}(\bm{A}\bm{h})|\leq\lambda_{1}+...+\lambda_{n}\leq|\det\bm{A}|=\Delta$

where we used (27) for the second inequality. ∎

###  3.4 Proof of Theorem 1.1

###### Proof of Theorem 1.1.

The first statement is a consequence of Corollary 1.7 and [19]. The case $k=1$
for the second statement follows directly from the result for
$\Delta(\bm{A})=1$ and Theorem 1.5. For arbitrary $k\in\mathbb{N}_{\geq 2}$
observe that $\gcd(\bm{A})\geq k$. We can modify the cone such that $k=1$ as
in the proof of Proposition 1.6. ∎

## References

  * [1] I Aliev, De Loera, J., F. Eisenbrand, T. Oertel, and R. Weismantel.  The support of integer optimal solutions.  SIAM Journal on Optimization, 28:2152–2157, 2018.
  * [2] I Aliev, De Loera, J., T. Oertel, and C. O’Neil.  Sparse solutions of linear diophantine equations.  SIAM Journal on Applied Algebra and Geometry, 1:239–253, 2017.
  * [3] S. Artmann, F. Eisenbrand, C. Glanzer, T. Oertel, S. Vempala, and R. Weismantel.  A note on non-degenerate integer programs with small sub-determinants.  Operations Research Letters, 44(5):635–639, 2016.
  * [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] W. Banaszczyk, A.E. Litvak, A. Pajor, and S.S. Szarek.  The flatness theorem for nonsymmetric convex bodies via the local theory of banach spaces.  Mathematics of Operations Research, 24(3):728 – 750, 1999.
  * [6] A. Basu and H. Jiang.  Enumerating integer points in polytopes with bounded subdeterminants.  https://arxiv.org/abs/2102.09994, 2021.
  * [7] 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.
  * [8] F. Eisenbrand and R. Weismantel.  Proximity results and faster algorithms for integer programming using the Steinitz lemma.  2018\.
  * [9] D.V. Gribanov and S.I. Veselov.  On integer programming with bounded determinants.  Optimization Letters, 10:1169–1177, 2016.
  * [10] M. Henk and R. Weismantel.  The height of minimal Hilbert bases.  Results in Mathematics, 32:298 – 303, 1997.
  * [11] B. Klopsch and V.F. Lev.  Generating abelian groups by addition only.  Forum Mathematicum, 21.1:23–41, 2009.
  * [12] H.W. Lenstra.  Integer programming with a fixed number of variables.  Mathematics of Operations Research, 8(4):538 – 548, 1983.
  * [13] J. Liu, L.E. Trotter Jr., and G.M. Ziegler.  On the height of the minimal Hilbert basis.  Results in Mathematics, 23:374 – 376, 1993.
  * [14] M. Nägele, R. Santiago, and R. Zenklusen.  Congruency-constrained TU problems beyond the bimodular case.  https://arxiv.org/pdf/2109.03148.pdf, 2021.
  * [15] M. Nägele, B. Sudakov, and R. Zenklusen.  Submodular minimization under congruency constraints.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, pages 849–866, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics.
  * [16] J. Paat, R. Weismantel, and S. Weltge.  Distances between optimal solutions of mixed-integer programs.  Mathematical Programming, 179:455 – 468, 2018.
  * [17] M. Rudelson.  Distances between nonsymmetric convex bodies and the MM*-estimate.  Positivity, 4:2:161–178, 2000.
  * [18] A. Schrijver.  Theory of Linear and Integer Programming.  Wiley, 1986.
  * [19] P.A. Sissokho.  Geometry of the minimal solutions of a linear diophantine equation.  SIAM Journal on Discrete Mathematics, 35(3):1952 – 1963, 2021.
  * [20] B. Sturmfels.  Gröbner bases and convex polytopes.  University Lecture Series, Volume 8, 162 pp., 1996.
  * [21] S.I. Veselov and A.J. Chirkov.  Integer program with bimodular matrix.  Discrete Optimization, 6:220–222, 2009.

##  Appendix A Appendix

###  A.1 Example: Maximal scaling is necessary

This explicit example is a product of computational experiments on a computer.
Given the following constraint matrix

$\displaystyle\bm{A}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 1&8&4&11\\\
1&4&3&6\\\ -1&-7&-3&-10\\\ -1&-7&-2&-9\end{pmatrix}$

and the respective cone $C(\bm{A})$. The normalized generators of $C(\bm{A})$
are the columns of the matrix below

$\displaystyle\begin{pmatrix}14&0&0&0&0&1&0\\\ 0&7&0&15&9&8&0\\\
2&7&10&6&4&3&11\\\
-2&-7&-3&-13&-8&-7&-4\end{pmatrix}=(\bm{r}^{1},...,\bm{r}^{7}).$

We have

$\displaystyle\begin{pmatrix}0&1&0&0\\\ 1&8&4&11\\\ -1&-7&-3&-10\\\
-1&-7&-2&-9\end{pmatrix}\bm{r}^{1}=\bm{0}.$

Note that $I\subseteq\\{2,3,5,6\\}$ with $I=\\{2,3,6\\}$ gives us
$\gcd(\bm{A}_{I,\cdot})=2$ whereas all other three element subsets of
$\\{2,3,5,6\\}$ yield a gcd of 1. If we would pick one of those, we get the
vector $\frac{1}{2}\bm{r}^{1}$. However, the Hilbert basis element

$\displaystyle\bm{h}=\begin{pmatrix}6\\\ 1\\\ 2\\\ -2\end{pmatrix}$

of $C(\bm{A})$ with respect to $\mathbb{Z}^{4}$ can be expressed by

$\displaystyle\bm{h}=\frac{3}{7}\bm{r}^{1}+\frac{1}{9}\bm{r}^{5}+\frac{4}{63}\bm{r}^{7}=\frac{47}{112}\bm{r}^{1}+\frac{1}{8}\bm{r}^{6}+\frac{1}{14}\bm{r}^{7}$

which yields coordinate sums greater than 1 if we replace $\bm{r}^{1}$ with
$\frac{1}{2}\bm{r}^{1}$.