---
abstract: |
    We explore upper bounds on the covering radius of non-hollow lattice polytopes.  In particular, we conjecture a general upper bound of $d/2$ in dimension $d$, achieved by the “standard terminal simplices” and direct sums of them.  We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino & Schymura (2017) that the $d$-th covering minimum of the standard terminal $n$-simplex equals $d/2$, for every $n>d$.

    We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger’s formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume.  To this end, we introduce a new notion of discrete surface area of non-hollow simplices.  We prove our discrete analog in dimension two and we give strong evidence for its validity in arbitrary dimension. 
address:
- 'Institut für Mathematik, Freie Universität Berlin, Arnimallee 2, 14195 Berlin, Germany'
- 'Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, Av.  de Los Castros 48, 39005 Santander, Spain'
- 'Institute for Mathematics, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland'
author:
- Giulia Codenotti
- Francisco Santos
- Matthias Schymura
bibliography:
- 'mybib.bib'
date: 'March 7, 2019'
title: 'The covering radius and a discrete surface area for non-hollow simplices'
---

[^1]

Introduction
============

The *covering radius* of a convex body $K$ in $\R^d$ with respect to a lattice $\Lambda$ is defined as $$\mu(K,\Lambda) = \min\left\{\mu \geq 0 : \mu K + \Lambda = \R^d\right\}.$$ Unless stated otherwise, we consider $\Lambda=\Z^d$ and just write $\mu(K)$. A convex body $K$ is called *hollow* or *lattice-free* (with respect to $\Lambda$) if $\operatorname{int}(K) \cap \Lambda = \emptyset$, where $\operatorname{int}(K)$ denotes the interior of $K$. With this notion, the covering radius $\mu(K,\Lambda)$ can be equivalently described as the greatest $\mu \geq 0$ such that the dilation $\mu K$ admits a hollow translate.  We are interested in upper bounds on the covering radius of non-hollow *lattice polytopes*, that is, polytopes all of whose vertices are lattice points.  If we drop the non-hollow condition it is easy to show that the maximum covering radius of a lattice $d$-polytope equals $d$, with equality if and only if the polytope is a *unimodular simplex*; that is, one of the form $\operatorname{conv}(\{{\mathbf{0}},b_1,\ldots,b_d\})$ where $\{b_1,\ldots,b_d\}$ is a lattice basis for $\Lambda$, or a lattice translate of that. ( See \[coro:corner\] for a proof of a more general statement). 

The existence of interior lattice points makes the problem more difficult and interesting.  The natural candidate to play the role of the unimodular simplex is $$S({\mathbf{1}}_{d+1}) := \operatorname{conv}(\left\{-{\mathbf{1}}_d,e_1,\ldots,e_d \right\}),$$ since it is the unique non-hollow $d$-polytope of minimum volume (see [@beyhenkwills2007notes Thm.  1.2]).  Here ${\mathbf{1}}_d = (1,\ldots,1)$ denotes the all-one vector in dimension $d$, and $e_i$ denotes the $i$th coordinate unit vector.[^2]

The covering radius of $S({\mathbf{1}}_{d+1})$ was computed in [@gonzalezschymura2017ondensities Prop.  4.9]: $$\begin{aligned}
\mu(S({\mathbf{1}}_{d+1}),\Z^d) = \frac{d}{2}.\label{eqn:covradSone}\end{aligned}$$ Since the covering radius is additive with respect to direct sums (see ), direct sums of simplices of the form $S({\mathbf{1}}_l)$ or lattice translates thereof also have covering radius equal to $d/2$. We conjecture that this procedure gives *all* the non-hollow lattice polytopes of maximum covering radius in a given dimension:

\[conj:one\] Let $P \subseteq \R^d$ be a non-hollow lattice $d$-polytope.  Then $$\mu(P) \le \frac{d}{2},$$ with equality if and only if $P$ is obtained by direct sums and/or translations of simplices of the form $S({\mathbf{1}}_l)$.

In dimension two, $S({\mathbf{1}}_3)$ has covering radius $1$, and so do the following triangle and square: $$\begin{aligned}
S({\mathbf{1}}_{2})\oplus ((1+ S({\mathbf{1}}_{2})) &= \operatorname{conv}(\{(1,0), (-1,0), (0,2)\}),
\\
S({\mathbf{1}}_{2})\oplus S({\mathbf{1}}_{2}) &= \operatorname{conv}(\{(1,0), (-1.0), (0,1), (0, -1)\}).\end{aligned}$$ In dimension three, translations and/or direct sums of the $S({\mathbf{1}}_l)$s produce nine pairwise non-equivalent non-hollow $3$-polytopes of covering radius $3/2$, that we describe in . 

One motivation for \[conj:one\] is as follows.  The *$d$-th covering minimum* of a convex body $K \subseteq \R^n$ with respect to a lattice $\Lambda \subseteq \R^n$ is defined as $$\mu_d(K, \Lambda) := \max_{\pi} \mu(\pi(K),\pi(\Lambda)),$$ where $\pi$ runs over all linear projections $\pi: \R^n \to \R^d$ such that $\pi(\Lambda)$ is a lattice.  Covering minima were introduced by Kannan & Lovász [@kannanlovasz1988covering] and interpolate between $\mu_n(K) = \mu(K)$ and $\mu_1(K)$, the reciprocal of the *lattice width* of $K$.

Since $S({\mathbf{1}}_{n+1})$ projects to $S({\mathbf{1}}_{d+1})$ for every $d < n$, we use  and get $$\begin{aligned}
\label{eq:mud_one}
\mu_d(S({\mathbf{1}}_{n+1})) \ge
\mu_d(S({\mathbf{1}}_{d+1})) = \frac{d}2.\end{aligned}$$ The converse inequality was conjectured in [@gonzalezschymura2017ondensities]:

\[conj:minima\] For every $n \in \N$ and $d \le n$, $$\begin{aligned}
\label{eq:minima}
\mu_d(S({\mathbf{1}}_{n+1}))= \frac{d}2.\end{aligned}$$

In \[sec:one-minima\] we prove:

\[thm:one\] For each $d\in \N$, the following are equivalent:

(i) $\mu(P) \leq \frac{\ell}{2}$ for every non-hollow lattice $\ell$-polytope $P$ and for every $\ell\le d$.

(ii) \[conj:minima\] holds for every $\ell\le d$. That is, $\mu_\ell(S({\mathbf{1}}_{n+1}))=\frac{\ell}{2}$, for every $\ell, n \in \N$ with $\ell\le d\le n$.

\[thm:one\_smalldim\] \[conj:one\], hence also \[conj:minima\], holds in dimension up to three. 

The computation of the covering radius for $S({\mathbf{1}}_{d+1})$ can be generalized to the following class of simplices: For each ${\omega}=({\omega}_0,\dots,{\omega}_d) \in \R_{> 0}^{d+1}$, we define $$S({\omega}) := \operatorname{conv}(\left\{ -{\omega}_0 {\mathbf{1}}_d, {\omega}_1 e_1, \ldots, {\omega}_d e_d\right\}).$$ In \[sec:lambda\] we derive the following closed formula for $\mu(S({\omega}))$. Therein and in the rest of the paper we denote by $\operatorname{Vol}_\Lambda(K)$ the *normalized volume* of a convex body $K$ with respect to a lattice $\Lambda$, which equals the Euclidean volume $\operatorname{vol}(K)$ of $K$ normalized such that a unimodular simplex of $\Lambda$ has volume one. 

\[thm:lambda\] For every ${\omega}\in \R^{d+1}_{>0}$, we have $$\mu(S({\omega})) 
= 
\frac{\sum_{0 \leq i < j \leq d} \frac{1}{{\omega}_i {\omega}_j}} {\sum_{i=0}^d \frac{1}{{\omega}_i}}
=
\frac12 \frac{\sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S({\omega})))} {\operatorname{Vol}_{\Z^d}(S({\omega}))},$$ where $\pi_i: \R^d \to \R^{d-1}$ is the linear projection vanishing at the $i$th vertex of $S({\omega})$.

In [@gonzalezschymura2017ondensities], the authors conjecture an optimal lower bound on the *covering product* $\mu_1(K) \cdot \ldots \cdot \mu_d(K) \cdot \operatorname{Vol}_{\Z^d}(K)$ for any convex body $K \subseteq \R^d$. As a consequence of the explicit formula for $\mu(S({\omega}))$, we confirm this conjecture for the simplices $S({\omega})$ (see \[cor:lambda\_cov\_prod\]). 

Observe that the volume expression on the right in \[thm:lambda\] can be defined for every simplex with the origin in its interior as follows:

\[def:discretesurfarea\] Let $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a $d$-simplex with the origin in its interior.  We say that $S$ has *rational vertex directions* if the line through the origin and the vertex $v_i$ has rational direction, for every $0 \leq i \leq d$.

Writing $\pi_i: \R^d \to \R^{d-1}$ for the linear projection vanishing at $v_i$, we define the *discrete surface area* of such a simplex $S$ as $$\operatorname{Surf}_{\Z^d}(S) := \sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S)).$$

Note that $\operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S)) = \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(F_i))$, with $F_i$ being the facet of $S$ opposite to the vertex $v_i$. In this sense, the sum of these numbers is indeed a version of the “surface area” of $S$, except that the volume of each facet is computed with respect to its projection from the opposite vertex. 

Motivated by this definition and \[thm:lambda\] we propose the following conjecture, which is the main object of study in this paper:

\[conj:volume\] Let $S$ be a $d$-simplex with the origin in its interior and with rational vertex directions.  Then $$\begin{aligned}
\mu(S) \leq \frac12 \frac{\operatorname{Surf}_{\Z^d}(S)}{\operatorname{Vol}_{\Z^d}(S)}. 
\label{eq:volume}\end{aligned}$$

In we give additional motivation for this conjecture.  We show that it implies \[conj:one\] (\[coro:vol\_one\]), that it holds in dimension two (\[thm:volume\_dim2\]), and that in arbitrary dimension it holds up to a factor of two (\[prop:volume\_factor\_2\]). 

Covering criteria such as the one in are rare in the literature, but very useful as they reduce the question of covering to computing less complex geometric functionals such as volume or (variants of the) surface area (cf.  [@gruber2007convex Sect.  31]).  A classical inequality of this type is the following result of Hadwiger.  We regard \[conj:volume\] as a discrete analog thereof. 

\[thm:hadwiger\] For every convex body $K$ in $\R^d$ $$\mu(K) \leq \frac12 \frac{\operatorname{surf}(K)}{\operatorname{vol}(K)},$$ where $\operatorname{vol}(K)$ and $\operatorname{surf}(K)$ are the Euclidean volume and surface area of $K$.

Observe that the statement of \[conj:volume\] is more intrinsic than Hadwiger’s inequality.  This is because the Euclidean surface area is not invariant under unimodular transformations, so that the bound in \[thm:hadwiger\] depends on the particular representative of $K$ in its unimodular class.  Moreover the inequality only holds for the standard lattice $\Z^d$ and cannot easily be transfered to other lattices (cf.  [@schnell1992minimal] for partial results for arbitrary lattices).  In constrast, our proposed relation in \[conj:volume\] *is* unimodularly invariant and there is no loss of generality in restricting to the standard lattice as we do (see \[cor:discrsurfarea\_invariance\] for details on these claims).  Moreover, our proposed inequality in \[conj:volume\] is tight for the large class of simplices $S({\omega})$.

In \[sec:0inboundary\], we complement our investigations on \[conj:volume\] by extending it to the case where the origin lies in the boundary of the simplex $S$, rather than in the interior.  Another way to extend \[conj:one\] is to ask for the maximal covering radius among lattice polytopes with at least $k \geq 1$ interior lattice points.  The natural conjecture is:

\[conj:k\] Let $k,d\in \N$ be nonnegative integers with $k \geq 2$. Then, for every lattice $d$-polytope $P$ with $k$ interior lattice points we have $$\mu(P) \le \frac{d-1}2 + \frac1{k+1},$$ with equality if and only if $P$ is obtained by direct sums and/or translations of a segment $[0,k+1]$ and one or more standard terminal simplices $S({\mathbf{1}}_l)$.

In \[sec:k\_points\] we prove this conjecture in dimension two (see \[thm:dim2-k\]).  Observe that no analog of \[conj:k\] makes sense for other covering minima.  Indeed, the maximum $d$th covering minimum $\mu_d$ among non-hollow lattice $n$-polytopes with $k$ interior lattice points does not depend on $k$ or $n$, for $d < n$: It equals the maximum covering radius among non-hollow lattice $d$-polytopes, since every non-hollow lattice $d$-polytope can be obtained as the projection of a $(d+1)$-polytope with arbitrarily many interior lattice points.  In fact, assuming \[conj:one\] this maximum is given by $$\mu_d(S(k,1,\ldots,1)) = \mu_d(S({\mathbf{1}}_{d+1})) = \frac{d}2, \quad \textrm{for all } n>d \textrm{ and } k \in \N.$$ Summing up, the relationship between our conjectures is as follows: $$\begin{matrix}
&&\cref{conj:volume}\\
&&\Downarrow\\
\cref{conj:k} & \Rightarrow & \cref{conj:one} & \\
&&\Downarrow\\
&&\cref{conj:one}&\text{without equality case}\\
&&\Updownarrow\\
&&\cref{conj:minima}\\
\end{matrix}$$ A summary of our results is that all these conjectures hold in dimension two, that \[conj:one\] holds in dimension three and that \[conj:volume\] holds for the simplices of the form $S({\omega})$.

Preliminaries {#sec:tools}
=============

This section develops some tools that will be essential for our analyses.  We first describe how the covering radius behaves with respect to projections, and more importantly, that it is an additive functional on direct sums of convex bodies and lattices.  Afterwards we introduce and study the concept of *tight covering* that facilitates our equality characterizations, for example the one in \[thm:one\_smalldim\]. 

Projection and direct sum {#sec:direct_sum}
-------------------------

\[lem:projection\] Let $K \subseteq \R^d$ be a convex body containing the origin, and let $\pi: \R^d \to \R^l$ be a rational linear projection, so that $\pi(\Z^d)$ is a lattice.  Let $Q=K \cap \pi^{-1}({\mathbf{0}})$ and let $L= \pi^{-1}({\mathbf{0}})$ be the linear subspace spanned by $Q$. Then, we have $$\mu(K,\Z^d) \leq \mu(Q,\Z^d \cap L) + \mu(\pi(K),\pi(\Z^d)).$$

Let us abbreviate $\mu_{Q} = \mu(Q,\Z^d \cap L)$ and $\mu_{\pi} = \mu(\pi(K),\pi(\Z^d))$. Let $x \in \R^d$ be arbitrary.  Then, $\pi(x)$ is covered by $\mu_{\pi} \cdot \pi(K) + \pi(\Z^d) = \pi \left(\mu_{\pi} K + \Z^d \right)$. Hence, there exists a point $x' \in \R^d$ such that the segment $[x,x']$ is parallel to $L$ and such that $x'$ is covered by $\mu_{\pi} K + \Z^d$. On the other hand, $y = x - x' \in L$ is covered by $\mu_Q Q + (\Z^d \cap L)$. Since $Q \subseteq K$, this implies that $x = y + x'$ is covered by $(\mu_Q + \mu_{\pi}) K + \Z^d$, as claimed. 

A particularly interesting case of the above result is when $K$ decomposes as a direct sum.  Let $\R^d = V \oplus W$ be a decomposition into complementary linear subspaces with $\dim(V) = \ell$ and $\dim(W) = d-\ell$. The *direct sum* of two convex bodies $K \subseteq V, L \subseteq W$ both containing the origin is defined as $$K \oplus L := \left\{ \lambda x +  (1 - \lambda) y : 
x \in K, y \in L, \lambda \in [0,1] \right\} \subseteq \R^d.$$ The direct sum of two lattices $\Lambda \subseteq V$, $\Gamma \subseteq W$ is defined as $$\Lambda \oplus \Gamma := \left\{ x + y : x \in \Lambda, y \in \Gamma \right\} \subseteq \R^d.$$ With these definitions we can now formulate:

\[cor:directsum\] Let $\R^d = V \oplus W$ be a decomposition as above, let $K \subseteq V$, $L \subseteq W$ be convex bodies containing the origin, and let $\Lambda \subseteq V$, $\Gamma \subseteq W$ be lattices.  Then, $$\mu_d(K \oplus L, \Lambda \oplus \Gamma) = \mu_\ell(K, \Lambda) + \mu_{d-\ell}(L, \Gamma).$$

The inequality $\mu_d(K \oplus L, \Lambda \oplus \Gamma) \leq \mu_\ell(K, \Lambda) + \mu_{d-\ell}(L, \Gamma)$ is a special case of , via the natural projection $\R^d = V \oplus W \to V$.

For the other inequality, let $x \in V$ be a point not covered by $c K + \Lambda$ for some $c < \mu_\ell(K,\Lambda)$ and let $y \in W$ be a point not covered by $\bar c L + \Gamma$ for some $\bar c < \mu_{d-\ell}(L,\Gamma)$. We claim that $x + y \in V \oplus W = \R^d$ is not covered by $(c + \bar c) (K \oplus L) + \Lambda \oplus \Gamma$, and thus $c + \bar c \leq \mu_d(K \oplus L, \Lambda \oplus \Gamma)$. Since, $c$ and $\bar c$ were taken arbitrarily, this implies $\mu_\ell(K, \Lambda) + \mu_{d-\ell}(L, \Gamma) \leq \mu_d(K \oplus L, \Lambda \oplus \Gamma)$.

Assume to the contrary, that $x + y \in (c + \bar c)(K \oplus L) + \Lambda \oplus \Gamma$, that is, $x + y = (c + \bar c)(\lambda p + (1 - \lambda) q) + w + z$, for some $\lambda \in [0,1]$, $p \in K$, $q \in L$, $w \in \Lambda$, and $z \in \Gamma$. Since the sums are direct, we get $x = (c + \bar c) \lambda p + w$ and $y = (c + \bar c)(1 - \lambda) q + z$, which by assumption implies $(c + \bar c) \lambda > c$ and $(c + \bar c) (1 - \lambda) > \bar c$. These two inequalities cannot hold at the same time, and we arrive at a contradiction. 

Tight covering
--------------

\[defi:tight\] Let $K \subseteq \R^d$ be a convex body and let $\Lambda$ be a lattice.  Then, $K$ is called *tight for $\Lambda$* if for every convex body $K' \supsetneq K$, we have $$\mu(K',\Lambda) < \mu(K,\Lambda).$$

\[defi:last\_covered\] Let $K \subseteq \R^d$ be a convex body of covering radius $\mu$ with respect to a lattice $\Lambda$. A point $p \in \R^d$ is *last covered by $K$* if $$p \notin \operatorname{int}(\mu\cdot K) + \Lambda.$$ Let $P$ be a $d$-polytope, let $F$ be a facet of $P$, and let $p$ be a point that is last covered by $P$. We say that $p$ *needs $F$* if $p \in \operatorname{relint}(\mu\cdot F) + \Lambda$.

\[lemma:tight\_vs\_facets\] Let $K \subseteq \R^d$ be a convex body of covering radius $\mu$ with respect to a lattice $\Lambda$. Then, the following properties are equivalent:

i)  $K$ is tight for $\Lambda$.

ii) $K$ is a polytope and for every facet $F$ of $K$ and for every last covered point $p$, $p$ needs $F$.

iii) $K$ is a polytope and every facet of every hollow translate of $\mu\cdot K$ is non-hollow. 

iv) Every hollow translate of $\mu\cdot K$ is a maximal hollow convex body with respect to inclusion. 

The equivalence of iii) and iv) is the characterization of maximal hollow convex bodies by Lovász [@lovasz1989geometryofnumbers].  For the equivalence of i) and iv) observe that, by definition, $\mu$ is the largest constant such that (a) $\mu \cdot K$ has a hollow lattice translate and (b) the inequality $\mu(K',\Lambda) < \mu(K,\Lambda)$ in the definition of tightness is nothing but maximality of all such hollow translates. 

We now show the equivalence of i) and ii).  Suppose there is a facet $F$ of $K$ that is not needed by some last covered point $p$. Let $K'=\operatorname{conv}(K \cup \{x\})$, where $x \notin K$ is a point *beyond $F$*, meaning that $x$ violates the inequality that defines $F$, but satisfies all other facet-inducing inequalities of $K$. Then $$\mu(K',\Lambda) = \mu(K,\Lambda),$$ because $p$ is still a last covered point of $K'$ (for the same dilate $\mu$). 

Conversely, if $K$ is not tight let $K'$ be a convex body strictly containing $K$ and that has the same covering radius.  Let $F$ be a facet of $K$ with $\operatorname{relint}(F) \subseteq \operatorname{int}(K')$. Let $p$ be a point that is last covered by $K'$. Since the covering radii are equal and $K \subsetneq K'$, $p$ must also be last covered by $K$. Since we chose $F$ so that $\operatorname{relint}(F)$ is in the interior of $K'$, $p$ does not need $F$.

\[ex:tightness\_char\] It is not sufficient for tightness that “every facet is needed by *some* last covered point.”  An example showing this is the hexagon $P=\operatorname{conv}(\{\pm(1,0), \pm(0,1), \pm(1,1)\})$ with respect to the integer lattice.  $P$ has covering radius $2/3$, the same as the triangle $\operatorname{conv}(\{(-1,1), (2,1), (-1,-2)\})$ that properly contains it, so it is not tight.  It has two orbits of last covered points, with representatives $\pm\left(2/3,1/3\right)$, each of which needs three of the six edges of $P$.

\[lemma:simplex\_monotone\] Every simplex is tight for every lattice. 

We use .  Let $\Delta$ be a simplex of covering radius $\mu$ with respect to a lattice $\Lambda$, and let $p$ be a point last covered by $\Delta$. That is, $p \notin \operatorname{int}(\mu\Delta) + \Lambda$. Let $F_0,F_1,\ldots,F_d$ be the facets of $\Delta$, with interior facet normals $v_0,\dots,v_d$.

Every neighborhood of $p$ is covered by $\mu \Delta + \Lambda$, and $p$ can only lie in lattice translates of the boundary of $\mu \Delta$. Suppose, in order to get a contradiction, that a certain facet $F_i$ is not needed by $p$. This implies that for every $\mu \Delta + z$ ($z\in \Lambda$) containing $p$ there is a facet $F_j\ne F_i$ such that $
\mu \Delta + z \subset H_j^p$, where $$H_j^p:=\{x \in \R^d : v_j^\intercal x \le v_j^\intercal p\}$$ is the translation to $p$ of the $j$-th facet-defining half-space of $\Delta$. This implies that we have a neighborhood of $p$ covered by the $d$ affine half-spaces with $p$ in the boundary corresponding to the indices $j\ne i$. This is impossible since the corresponding $d$ normals are linearly independent. 

\[lemma:sum\_monotone\] Let $K_1$ and $K_2$ be convex bodies containing the origin and let $\Lambda_1$ and $\Lambda_2$ be lattices.  Then, $K_1$ and $K_2$ are tight for $\Lambda_1$ and $\Lambda_2$, respectively, if and only if $K_1 \oplus K_2$ is tight for $\Lambda_1 \oplus \Lambda_2$.

First of all, let $K' \supsetneq K_1 \oplus K_2$ be a convex body and let $K'_1$ and $K'_2$ be the projection of $K'$ onto the linear span of $K_1$ and $K_2$, respectively.  Clearly, either $K'_1 \supsetneq K_1$ or $K'_2 \supsetneq K_2$, so that by and the tightness of $K_1$ and $K_2$, we have $$\begin{aligned}
\mu(K_1 \oplus K_2, \Lambda_1 \oplus \Lambda_2) &= \mu(K_1,\Lambda_1) + \mu(K_2,\Lambda_2) > \mu(K'_1,\Lambda_1) + \mu(K'_2,\Lambda_2) \\
&= \mu(K'_1 \oplus K'_2, \Lambda_1 \oplus \Lambda_2) \geq \mu(K', \Lambda_1 \oplus \Lambda_2),\end{aligned}$$ since $K'_1 \oplus K'_2 \subseteq K'$. Therefore, $K_1 \oplus K_2$ is tight for $\Lambda_1 \oplus \Lambda_2$.

Conversely, if say $K_1$ is not tight for $\Lambda_1$, then there exists $K'_1 \supsetneq K_1$ such that $\mu(K_1,\Lambda_1) = \mu(K'_1,\Lambda_1)$. Then, $K'_1 \oplus K_2 \supsetneq K_1 \oplus K_2$ and by $$\begin{aligned}
\mu(K'_1 \oplus K_2,\Lambda_1 \oplus \Lambda_2) &= \mu(K'_1,\Lambda_1) + \mu(K_2,\Lambda_2) = \mu(K_1,\Lambda_1) + \mu(K_2,\Lambda_2) \\
&= \mu(K_1 \oplus K_2,\Lambda_1 \oplus \Lambda_2),\end{aligned}$$ so $K_1 \oplus K_2$ is not tight for $\Lambda_1 \oplus \Lambda_2$.

\[lemma:lattice\_monotone\] Let $\Lambda' \subsetneq \Lambda$ be two lattices in $\R^d$, and let $K \subseteq \R^d$ be a convex body.  Then, $$\mu(K, \Lambda) \le \mu(K, \Lambda').$$

Let $\mu = \mu(K, \Lambda)$ and $\mu' = \mu(K, \Lambda')$. Then, $\mu' K + \Lambda' \subseteq \mu' K + \Lambda$, so $\mu \leq \mu'$. An example where equality holds is the following: Let $K= [-1,1]^d$ and let $\Lambda$ be an arbitrary refinement of $\Z^d$ contained in $\R^{d-1} \times \Z$. Then, $\mu(K,\Z^d) = \mu(K,\Lambda)=1/2$.

The inequality in may not be strict, even for simplices.  An example is the simplex $(I\oplus I')' \oplus I$ of below.  It has the same covering radius as $S({\mathbf{1}}_4)$ (equal to $3/2$), yet it is isomorphic to $S({\mathbf{1}}_4)$ when regarded with respect to the sublattice of index two generated by its vertices and its interior lattice point.  This can easily be derived from its depiction in the bottom-center of , or from its coordinates in (in these coordinates the sublattice is $\{(x,y,z)\in \Z^3: x\in 2\Z\}$). 

\[conj:one\] and \[conj:minima\]: Equivalence and small dimensions {#sec:one-minima}
==================================================================

Equivalence of Conjectures \[conj:one\] and \[conj:minima\] {#sec:one}
-----------------------------------------------------------

As an auxiliary result we first reduce \[conj:one\] to lattice simplices. 

\[lemSimplexInside\] Every non-hollow lattice polytope contains a non-hollow lattice simplex of possibly smaller dimension. 

Consider a triangulation $T$ of the given lattice polytope $P$ whose only vertices are the vertices of $P$. Since $P$ is non-hollow it contains an interior lattice point, say $p \in \operatorname{int}(P)\cap\Z^d$. Let $S$ be the unique, possibly lower-dimensional, simplex in $T$ that contains $p$ in its relative interior.  By definition, $S$ is non-hollow and contained in $P$.

\[cor:ReduToSimpls\] \[conj:one\] reduces to lattice simplices.  More precisely, \[conj:one\] holds in every dimension $\leq d$, if and only if it holds for lattice simplices in every dimension $\leq d$.

One direction is trivially true.  We prove the other one by induction on $d$. Let $P \subseteq \R^d$ be a non-hollow lattice polytope.  In view of \[lemSimplexInside\], we find an $\ell$-dimensional non-hollow lattice simplex $S \subseteq P$. If $\ell=d$, then we simply have $\mu(P) \leq \mu(S)$. So, let us assume that $\ell < d$ and assume that \[conj:one\] is proven for any dimension $<d$. Assume also that $S$ contains the origin in its interior and write $L_S$ for the linear hull of $S$. We now apply \[lem:projection\] to the projection $\pi$ onto $L_S^\perp$. Observe that $S \subseteq P \cap \pi^{-1}({\mathbf{0}}) = P \cap L_S$, and that $S$ is non-hollow with respect to $\Z^d \cap L_S$ and $\pi(P)$ is non-hollow with respect to the lattice $\pi(\Z^d)$. We get that $$\mu(P) \leq \mu(S,\Z^d \cap L_S) + \mu(\pi(P),\pi(\Z^d)) \leq \frac{\ell}{2} + \frac{d-\ell}{2} = \frac{d}{2}.\qedhere$$

Suppose first that for $\ell \le d$ every lattice $\ell$-polytope $P$ has $\mu(P) \le \ell/2$. Since $S({\mathbf{1}}_{n+1})$ projects to $S({\mathbf{1}}_{\ell+1})$, we have by  $$\mu_\ell(S({\mathbf{1}}_{n+1}),\Z^n) \geq \mu_\ell(S({\mathbf{1}}_{\ell+1}),\Z^\ell) = \frac{\ell}2.$$ For the converse inequality, let $\pi : \R^n \to \R^\ell$ be an integer projection along which the value of $\mu_\ell(S({\mathbf{1}}_{n+1}))$ is attained.  Then, $\pi(S({\mathbf{1}}_{n+1}))$ is non-hollow with respect to the lattice $\pi(\Z^n)$, and thus $$\mu_\ell(S({\mathbf{1}}_{n+1}),\Z^n) = \mu_\ell(\pi(S({\mathbf{1}}_{n+1})), \pi(\Z^n)) \leq \frac{\ell}2.$$ For the reverse implication (ii) $\Rightarrow$ (i), suppose \[conj:minima\] holds in every dimension $\ell \leq d$. Let $P$ be a lattice $\ell$-polytope with at least one interior lattice point, which without loss of generality we assume to be the origin ${\mathbf{0}}$. By \[cor:ReduToSimpls\] we can assume $P$ to be a simplex, and we let $v_0,\dots,v_\ell$ be its vertices.  Let $(b_0,\ldots,b_\ell) \in \N^{\ell+1}$ be a multiple of the barycentric coordinates of ${\mathbf{0}}$ in $P$; that is, assume that $$\label{eqn:barycentric}
{\mathbf{0}}= \frac{1}{N} \sum_{i=0}^\ell b_i v_i,$$ where $N = \sum_{i=0}^\ell b_i \geq \ell+1$. Consider the $(N-1)$-dimensional simplex $S({\mathbf{1}}_{N})$, and the affine projection $\pi : \R^{N-1} \to \R^\ell$ that sends exactly $b_i$ vertices of $S({\mathbf{1}}_{N})$ to $v_i$, $i=0,\ldots,\ell$. Expression  implies that $\pi$ sends the origin to the origin, which in turn implies $\pi$ to be an integer projection.  In particular, $$\mu(P,\Z^\ell) \leq \mu_\ell(\pi(S({\mathbf{1}}_{N})),\pi(\Z^{N-1})) \leq \mu_\ell(S({\mathbf{1}}_{N}),\Z^{N-1}) = \frac{\ell}2,$$ since $\pi(\Z^{N-1}) \subseteq \Z^\ell$.

Conjecture \[conj:one\] in dimensions 2 and 3 {#sec:smalldim}
---------------------------------------------

We here prove \[conj:one\] in dimensions two and three, including the case of equality. 

### Conjecture \[conj:one\] in dimension two {#conjecture-conjone-in-dimension-two .unnumbered}

Let $I=[-1,1]$ and $I'=[0,2]$ be intervals of length two centered at $0$ and $1$, respectively. 

\[lemma:dimtwo-a\] The three polygons $S({\mathbf{1}}_3)$, $I \oplus I$, and $I \oplus I'$ have covering radius equal to one. 

For $S({\mathbf{1}}_3)$ this is just \[eqn:covradSone\].  For the other two polygons it follows from , since they are unimodularly equivalent to direct sums of segments of length two. 

![ The non-hollow lattice polygons $S({\mathbf{1}}_3)$, $I \oplus I$ and $I\oplus I'$ of covering radius equal to one.[]{data-label="fig:3cov1polys"}](3cov1polys.pdf)

We now show that every other non-hollow lattice polygon contains a (unimodularly equivalent) copy of one of these three, which implies .  For this let us consider the following auxiliary family of lattice triangles with $k$ interior lattice points: For each $k \in \N$, and $\alpha\in \{0,1\}$ let $$M_k(\alpha)=\operatorname{conv}(\{(-1,0), (1,\alpha), (0, k+1)\}).$$ Observe that $$M_1(0) = I\oplus I',
\quad
M_1(1) \cong S({\mathbf{1}}_3),
$$ k2,   M\_[k-1]{}() M\_[k]{}(). 

\[lemma:dimtwo-b\] Every non-hollow lattice polygon $P$ contains a unimodular copy of either $M_1(0)= I\oplus I'$, $M_1(1)\cong S({\mathbf{1}}_3)$ or $I\oplus I$.

Without loss of generality, assume the origin is in the interior of $P$. Consider the complete fan whose rays go through all non-zero lattice points in $P$. We call this the *lattice fan* associated to $P$, and it is a complete unimodular fan.  Since a 2-dimensional fan is uniquely determined by its rays, we denote $\F\{v_1,\dots,v_m\}$ the fan with rays through $v_1,\dots, v_m \in \R^2$. In particular, the lattice fan of $P$ is denoted $\F\{P\cap \Z^2\}$.

By the classification of complete unimodular fans, see [@ewald1996combinatorial Thm.  V.6.6], $\F\{P\cap \Z^2\}$ can be (modulo unimodular equivalence) obtained by successively refining the lattice fan of either $S({\mathbf{1}}_3)$ or $$\F_l:= \F\{(0,-1), (0,1), (-1,0), (1,l)\},$$ for some $l\in \Z_{\ge0}$. Observe that $\F_0$ is the lattice fan of $I\oplus I$, $\F_1$ refines the lattice fan of $S({\mathbf{1}}_3)\cong M_1(1)$ and, for every $l\ge 2$ we have that $\F_l$ is unimodularly equivalent to the fan of $$\begin{cases}
M_k(0)& \text{ if $l=2k$ is even, and}\\
M_k(1)& \text{ if $l=2k-1$ is odd.} 
\end{cases}$$ This, together with the fact that $M_1(\alpha) \subseteq M_k(\alpha)$ for every $k\ge 1$, implies that $P$ contains one of $M_1(0)$, $M_1(1)$ or $I\oplus I$.

\[coro:ConjA\_dim2\] Let $P$ be a non-hollow lattice polygon.  Then $$\mu(P)\le 1,$$ with equality if and only if $P$ is unimodularly equivalent to one of $S({\mathbf{1}}_3)$, $I \oplus I$, or $I \oplus I'$.

By , unless $P$ is one of $S({\mathbf{1}}_3)$, $I \oplus I$ or $I \oplus I'$ it strictly contains one of them.  If the latter happens then its covering radius is strictly smaller than $1$, since the three of them are tight by and . 

\[rem:M\_k-dim2\] The covering radius of $M_k(\alpha)$ can be computed explicitly via $$M_k(0) \cong I \oplus [0,k+1], \quad
\text{and}
\quad
M_k(1) \cong S(k,1,1).$$ Indeed, this implies $$\mu(M_k(0)) = \frac12 + \frac1{k+1} = \frac{k+3}{2k+2} 
, \quad
\text{and}
\quad
\mu(M_k(1)) = \frac{1 + \frac2k}{2+\frac1k} = \frac{k+2}{2k+1},$$ by and , respectively.  We see that, indeed, their covering radius equals $1$ for $k=1$ and is strictly smaller for greater $k$.

### Conjecture \[conj:one\] in dimension three {#conjecture-conjone-in-dimension-three .unnumbered}

For the three-dimensional case we introduce the following concept:

\[defi:minimal\] A *minimal $d$-polytope* is a non-hollow lattice $d$-polytope not properly containing any other non-hollow lattice $d$-polytope. 

In this language, our results in dimension 2 can be restated as: There are exactly three minimal $2$-polytopes, they have covering radius $1$, and every other non-hollow lattice $2$-polytope has strictly smaller covering radius. 

In dimension three things are a bit more complicated.  To start with, instead of three direct sums of (perhaps translated) simplices of the form $S({\mathbf{1}}_i)$ there are nine, that we now describe.  As in the previous section, let $I=[-1,1] = S({\mathbf{1}}_2)$ and $I'=[0,2]$. In a similar way we define: $$\begin{aligned}
S'({\mathbf{1}}_3) &= (1,1) + S({\mathbf{1}}_3) = \operatorname{conv}(\{(0,0), (2,1), (1,2)\}),\\
(I \oplus I')^\circ &= (0,-1) + (I \oplus I') = \operatorname{conv}(\{(0,1), (\pm1,-1)\}),\\
(I \oplus I')' &= (0, -2) + (I \oplus I') = \operatorname{conv}(\{(0,0), (\pm1,-2)\}).\end{aligned}$$ Put differently, $S'({\mathbf{1}}_3)$ is $S({\mathbf{1}}_3)$ translated to have the origin as a vertex; the other two are $I \oplus I'$ translated to have the origin in the interior and at the “apex”, respectively. 

\[lemma:minimum\_3d\] There are the following nine non-equivalent lattice $3$-polytopes of covering radius $3/2$, obtained as direct sums of (perhaps translated) simplices of the form $S({\mathbf{1}}_d)$: $$\begin{array}{c}
S({\mathbf{1}}_4), 
\\
S({\mathbf{1}}_3) \oplus I, \qquad
S'({\mathbf{1}}_3) \oplus I, \qquad
S({\mathbf{1}}_3) \oplus I',
\\
I\oplus I\oplus I,  \qquad
I\oplus I\oplus I',
\\
(I \oplus I')^\circ \oplus I, \qquad
(I \oplus I')'\oplus I , \qquad
(I \oplus I')^\circ \oplus I'. 
\end{array}$$

The last five polytopes are illustrated in , which is borrowed from [@blancosantos2019nonspanning p. 123].  Observe that the last three can equally be written as $$\begin{array}{ccc}
I \oplus (I \oplus I)' , \qquad
I \oplus (I' \oplus I)'  , \qquad
I \oplus (I \oplus I')'' ,
\end{array}$$ where $(I \oplus I)'$ denotes $I \oplus I$ translated to have the origin as a vertex and $(I \oplus I')''$ is $I \oplus I'$ translated to have the origin at an endpoint of its edge of length two. 

![ The five non-hollow lattice $3$-polytopes that can be obtained by translations and direct sums of $I=[-1,1]$.[]{data-label="fig:sums_of_I"}](sums_of_I.pdf)

That all the described direct sums are non-hollow follows from the following more general fact: The direct sum of two or more non-hollow lattice polytopes containing the origin is non-hollow if (and only if) all but at most one of the summands has the origin in its interior.  Indeed, if the summand exists then its interior point(s) are interior in the sum; if it doesn’t then the origin is an interior point in the sum. 

With this in mind, we only need to check that the nine described polytopes are pairwise unimodularly non-equivalent, which is left to the reader. 

A second difference with dimension two is that these nine non-hollow lattice $3$-polytopes are no longer the only minimal ones.  Minimal non-hollow $3$-polytopes have been classified and there are 26 with a single interior lattice point (see [@kasprzyk2010threefolds Thm.  3.1] and Tables 2 & 4 therein) plus the infinite family described in below. 

To prove \[conj:one\] in dimension three we show that, on the one hand, the covering radii of the 26 with a single interior lattice point can be explicitly computed and/or bounded, giving the following result, the proof of which we postpone to . 

\[thm:26minimal\] Among the 26 minimal non-hollow $3$-polytopes with a single interior lattice point, all except the nine in have covering radius strictly smaller than $3/2$.

On the other hand, all the (infinitely many) minimal non-hollow $3$-polytopes with more than one interior lattice point have covering radius strictly smaller than $3/2$, as we now prove.  For any $k \in \N$ and $\alpha, \beta \in\{0,1\}$, we define $M_k(\alpha, \beta)$ to be the following lattice tetrahedron: $$M_k(\alpha,\beta)= \operatorname{conv}(\{(1,0,0), (-1,0,\alpha), (0,1,k+1), (0,-1, k+1-\beta)\}).$$

\[thm:M\_k-3d\] Every minimal $3$-polytope with $k\ge2$ interior lattice points is equivalent by unimodular equivalence or refinement of the lattice to $M_k(\alpha,\beta)$ for some $\alpha,\beta \in \{0,1\}$.

is a version of [@ballettikasprzyk2016twopoints Prop.  4.2], although more explicit than the original one.  An example where refinement is needed in the statement is $M_k(0,0)$ considered with respect to the lattice $\Lambda$ generated by $\Z^3$ and $(1/q, 1-1/q,0)$, with $q$ and $k+1$ coprime.  $M_k(0,0)$ is still minimal with respect to $\Lambda$ because it contains no point of $\Lambda \setminus \Z^3$.

Let $P$ be a minimal lattice $3$-polytope with more than one interior lattice point, and let $L$ be a line containing two of them.  Without loss of generality we assume that $L = \{(0,0,z) : z\in \R\}$ and $L\cap P$ is the segment between $(0,0,z_1)$ and $(0,0,z_2)$, with $z_1 \in [0,1)$ and $z_2\in (r,r+1]$ for some $r \in \{2,\ldots,k\}$, so that $L$ contains $r$ interior lattice points of $P$.

[**Claim 1:**]{} *The minimal faces of $P$ containing respectively $(0,0,z_1)$ and $(0,0,z_2)$ are non-coplanar edges.*  Let $F_1$ and $F_2$ be those faces.  If one of them, say $F_1$, had dimension two, then $\operatorname{conv}(F_1 \cup \{(0,0,r)\})$ would be a non-hollow lattice polytope strictly contained in $P$. If one of them, say $F_1$, had dimension zero then necessarily $F_1 = \{(0,0,z_1)\}=\{(0,0,0)\}$. This would imply $\operatorname{conv}(P \cap \Z^3 \setminus\{{\mathbf{0}}\})$ to be a non-hollow lattice polytope strictly contained in $P$. Thus, $F_1$ and $F_2$ are both edges of $P$. They cannot be coplanar, since otherwise there would be vertices $p$ and $q$ of $P$, one on either side of the hyperplane $\operatorname{aff}(F_1 \cup F_2)$, and the polytope $\operatorname{conv}(F_1 \cup \{(0,0,r),p,q\})$ would be non-hollow and strictly contained in $P$.

Hence, $\operatorname{conv}(F_1 \cup F_2)$ is a non-hollow lattice tetrahedron and by minimality, $P=\operatorname{conv}(F_1 \cup F_2)$. We denote $v_i$ and $w_i$ the vertices of $F_i$, for $i=1,2$.

[**Claim 2:**]{} *All the lattice points in the tetrahedron $P$ other than the four vertices are on the line $L$.* Let $H_i$ be the plane containing the line $L$ and the edge $F_i$, for $i=1,2$. The polytope $Q= \operatorname{conv}(L\cap P \cup\{v_1, w_1, v_2\}) \subset P$ is contained in $H_1^+$, one of the two halfspaces defined by $H_1$; furthermore, the facet of $Q$ lying on $H_1$ is non-hollow, since $(0,0,1)$ is in its relative interior.  Therefore, if $P$ contained any lattice point $u$ other than the vertex $w_2$ in the open halfspace $(H_1^-)^o$ then $\operatorname{conv}(Q \cup \{u\})$ would be a non-hollow lattice polytope strictly contained in $P$. Thus there are no lattice points in the open halfspace $(H_1^-)^o$. Since the same can be said for the other halfspaces, $H_1^+$ and $H_2^\pm$, all lattice points of $P$ except its four vertices must lie on $L$.

In particular, we have $r=k$.

[**Claim 3:**]{} *The endpoint $(0,0,z_i)$ equals the mid-point of the edge $F_i=\operatorname{conv}(\{v_i,w_i\})$*.  Let us only look at $i=1$, the other case being symmetric.  Let $u_1=(0,0,1)$ and $u_2=(0,0,2)$ be the first two interior lattice points of $P$ along $L$. The triangles $\operatorname{conv}(\{u_1,u_2,v_1\})$ and $\operatorname{conv}(\{u_1,u_2,w_1\})$ are empty lattice triangles in the plane $H_1$, hence they have the same area.  Thus, $v_1$ and $w_1$ are at the same distance from (and on opposite sides of) the line $L$, which implies the statement. 

In particular, $z_1\in [0,1)$ and $z_2\in (k,k+1]$ are either integers or half-integers, so they can be written as $z_1=\alpha/2$ and $z_2=k+1-\beta/2$ for some $\alpha,\beta \in \{0,1\}$. It is now clear that the affine transformation that fixes $L$ and sends $v_1 \mapsto (1,0,0)$ and $v_2 \mapsto (0,1,k+1)$, sends $P$ to $M_k(\alpha, \beta)$. The map may send $\Z^3$ to a different lattice $\Lambda$, but $\Lambda$ refines $\Z^3$ since $(1,0,0)$, $(0,1,k+1)$, $(0,0,1)$ and $(0,0,2)$ are in $\Lambda$ and they generate $\Z^3$.

\[coro:M\_k-3d\] Every minimal $3$-polytope with $k\ge2$ interior lattice points has covering radius strictly smaller than $3/2$.

The projection of $M_k(\alpha,\beta)$ along the $z$ direction is $I\oplus I$ and the fiber over the origin is the segment $\{0\}\times \{0\} \times [\alpha/2, k+1 - \beta/2]$, of length $k+1 - (\alpha + \beta)/2$. Thus, by , $$\mu(M_k(\alpha,\beta)) \le \mu(I\oplus I) + \mu([\alpha/2, k+1 - \beta/2]) = 1 + \frac1{k+1 -\frac{\alpha + \beta}2} \le \frac32.$$ Moreover, the last inequality is met with equality only in the case $k=2$, $\alpha=\beta=1$. But for $M_2(1,1)$ we can consider the projection $(x,y,z) \mapsto x$, whose image is $I$ and whose fiber is $$\operatorname{conv}(\{(0,1/2), (1,3), (-1,2)\}) \cong S(3/2,1,1).$$ Thus, by and , we have $$\mu(M_2(1,1)) \le \mu(I) + \mu(S(3/2,1,1)) = \frac12 + \frac{7/3}{8/3} = \frac{11}8<\frac32.\qedhere$$

In fact we can be more explicit:

\[rem:M\_k-dim3\] The covering radius of $M_k(\alpha,\beta)$ admits a closed expression: $$\begin{aligned}
\mu(M_k(0,0)) &= \mu (I \oplus [0,k+1] \oplus I) = 1 + \frac1{k+1}. 
\\
\mu(M_k(1,0)) &= \mu(M_k(0,1)) = \mu (I \oplus M_k(1)) = 1 + \frac{3}{4k+2},
\\
\mu(M_k(1,1)) &= 1+ \frac{1}{2k}.\end{aligned}$$ The first formula directly follows from \[lem:projection\].  The second one also does, using .  For the third one, see \[lem:Mk11\].  For $k=1$ the three expressions reduce to $3/2$, which is consistent with the descriptions $M_1(0,0) \cong I\oplus (I\oplus I')'$, $M_1(0,1) \cong I \oplus S({\mathbf{1}}_3)$, and $M_1(1,1) \cong S({\mathbf{1}}_4)$.

We are now ready to prove \[conj:one\] in dimension three:

\[thm:ConjA\_dim3\] Let $P$ be a non-hollow lattice $3$-polytope.  Then $$\mu(P)\le \frac32,$$ with equality if and only if $P$ is unimodularly equivalent to one of the nine polytopes in . 

Let $P$ be a non-hollow lattice $3$-polytope, and let $T$ be a minimal one contained in it.  If $T$ is not one of the nine in then $T$, and hence $P$, has covering radius strictly smaller than $3/2$ by either or .  If $T$ is one of the nine and $P\ne T$ then $$\mu(P) < \mu(T) = \frac32,$$ since these nine are tight by and . 

Another proof of Conjecture \[conj:one\] in dimension two {#sec:v}
---------------------------------------------------------

Let $v \in \R_{\ge 1}^d$ and let $\Delta_v := \operatorname{conv}(\{-v,e_1,\ldots,e_d\})$. The following result says that bounds for the covering radii of this class of simplices translate to bounds for all non-hollow lattice polytopes (cf.  \[cor:ReduToSimpls\]). 

\[lemma:delta\_v\] Let $\Delta$ be a non-hollow lattice $d$-simplex.  Then, there is a vector $v \in \Q_{\ge1}^d$ such that $$\mu(\Delta) \le \mu(\Delta_v).$$

Write $\Delta = \operatorname{conv}(\{w_0,w_1,\ldots,w_d\})$ and assume without loss of generality that ${\mathbf{0}}\in \operatorname{int}(\Delta) \cap \Z^d$. Let $(\beta_0,\beta_1,\ldots,\beta_d)$ be the barycentric coordinates of the origin with respect to $\Delta$. That is, $\beta_i \geq 0$, $\sum_{i=0}^d \beta_i = 1$, and ${\mathbf{0}}=\sum_{i=0}^d \beta_i w_i$. We may assume without loss of generality that $0 < \beta_0 \leq \beta_i$, for all $i \in \{1,\ldots,d\}$. Now, let $W=(w_1,\ldots,w_d) \in \Z^{d \times d}$ and let $v\in\R^d$ be such that $W\Delta_v = \Delta$. Clearly, $\beta_0 v = W^{-1} \left(\sum_{i=1}^d \beta_i w_i\right)=\sum_{i=1}^d \beta_i e_i$, and hence $v=(\frac{\beta_1}{\beta_0},\ldots,\frac{\beta_d}{\beta_0}) \in \Q_{\geq1}^d$.

With these observations, we get $$\mu(\Delta) \leq \mu(\Delta,W\Z^d) = \mu(W\Delta_v,W\Z^d) = \mu(\Delta_v),$$ as desired. 

In dimension two, this approach leads to another proof of \[conj:one\]:

\[prop:conj:v\_plane\] For every $v \in  \R_{\ge1}^2$, we have $$\mu(\Delta_v) \le 1.$$ Equality holds if and only if $v \in \{(a,1),(1,a)\}$, for some $1 \leq a \leq 2$.

Due to symmetry, we can assume $v = (v_1,v_2)$ with $v_1 \geq v_2$. If $v_2 > 1$, then $\Delta_v$ strictly contains the triangle $\Delta_w$, for some $w = (w_1,1) \in \R^2_{\geq 1}$. By \[lemma:simplex\_monotone\] triangles are tight for every lattice, so that $\mu(\Delta_v) < \mu(\Delta_w)$ and it thus suffices to consider $v = (a,1)$, for $a \geq 1$.

Let $F_0$ be the edge of $\Delta_v$ not containing $v$, and let $F_1$ and $F_2$ be the edges of $\Delta_v$ not containing $e_1$ and $e_2$, respectively.  Further, let $\ell = \{(x,y) : x+y=1\}$ be the line containing $F_0$. An elementary calculation provides us with the following intersection points: $$\begin{aligned}
\ell \cap (F_1 + e_1) &= \left\{\left(\tfrac{2}{a+2},\tfrac{a}{a+2}\right)\right\}, & \ell \cap (F_2 + e_2) &= \left\{\left(\tfrac{1}{a+2},\tfrac{a+1}{a+2}\right)\right\}, \\
\ell \cap (F_1 + (1,1)) &= \left\{\left(\tfrac{2-a}{a+2},\tfrac{2a}{a+2}\right)\right\}, & \ell \cap (F_2 + (1,1)) &= \left\{\left(\tfrac{2}{a+2},\tfrac{a}{a+2}\right)\right\}.\end{aligned}$$ This already shows that the translates $\{0,1\}^2 + \Delta_v$ cover the unit cube $[0,1]^2$, for every $a \geq 1$, so that $\mu(\Delta_v) \leq 1$ as claimed. 

In order to decide the equality case, observe that in the covering of $[0,1]^2$ by these four translates, the point $\left(\tfrac{2}{a+2},\tfrac{a}{a+2}\right)$ is covered last, and is not contained in the interior of any of the four triangles.  However, the translate $(2,1) + \Delta_v$ may contain this point in the interior.  Noting that $$\ell \cap (F_1 + (2,1)) = \left\{\left(\tfrac{4-a}{a+2},\tfrac{2a-2}{a+2}\right)\right\},$$ this happens if and only if $4-a < 2$, that is, $a > 2$.

Unfortunately, the analogous result fails in higher dimensions:

\[exm:conj:v\_counterex\] The method described in \[sec:26computations\] can be used to compute that $$\mu(\Delta_{(3/2,1,1)}) = \frac{14}{9} > \frac32.$$ Counterexamples in higher dimensions can be constructed from this example as follows: Let $v \in \R^d_{\geq1}$ be such that $\mu(\Delta_v) > \frac{d}{2}$, and let $S$ be the non-hollow lattice $(d+1)$-simplex arising as the direct sum of $\Delta_v$ and $I' = [0,2]$. In view of \[lemma:delta\_v\], there exists $w \in \R^{d+1}_{\geq 1}$ such that $$\mu(\Delta_w) \geq \mu(S) = \mu(\Delta_v) + \mu(I') > \frac{d}{2} + \frac12 = \frac{d+1}{2},$$ where we also used \[cor:directsum\]. 

Conjecture \[conj:volume\] {#sec:volume}
==========================

We here focus on \[conj:volume\].  We show that it implies \[conj:one\], we prove it up to a factor of two in arbitrary dimension, and we prove it in dimension two.  Finally, in \[sec:0inboundary\], we investigate how the proposed bound changes if we allow the origin to be contained in the boundary of the given simplex. 

As a preparation, let us first reinterpret \[conj:volume\] in terms of (reciprocals of) certain lengths.  To this end, let $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a $d$-simplex with the origin in its interior, and assume that it has *rational vertex directions*, that is, the line through the origin and the vertex $v_i$ has rational direction, for every $0\leq i \leq d$.

As in \[conj:volume\], let $\pi_i$ be the linear projection to dimension $d-1$ vanishing at $v_i$. Finally, let $\ell_i$ be the lattice length of $S \cap \pi_i^{-1}({\mathbf{0}})$. Put differently, let $u_i$ be the point where the ray from $v_i$ through ${\mathbf{0}}$ hits the opposite facet of $S$ and let $\ell_i$ be the ratio between the length of $[u_i,v_i]$ and the length of the primitive lattice vector in the same direction.  In formula: $$\ell_i :=  \operatorname{Vol}_{\Z^d \cap \R v_i}([u_i, v_i]).$$

\[lemma:ell\] For every $i \in \{0,1,\ldots,d\}$, we have $$\frac1{\ell_i} = \frac { \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S))}{\operatorname{Vol}_{\Z^d}(S)}.$$ In particular, is equivalent to the inequality $$\begin{aligned}
\label{eq:ell}
\mu(S) \leq \frac12 \sum_{i=0}^d \frac1{\ell_i}.\end{aligned}$$

By construction, we have $\pi_i(S) = \pi_i(F_i)$, where $F_i$ is the facet of $S$ opposite to the vertex $v_i$. Therefore, $\operatorname{vol}(S) = \frac{1}{d} \operatorname{vol}(\pi_i(S)) \operatorname{vol}([u_i,v_i])$. The determinants of the involved lattices are related by $1=\det(\Z^d)=\det(\pi_i(\Z^d))\det(\Z^d \cap \R v_i)$ (cf.  [@martinet2003perfect Prop.  1.2.9]).  Hence, $$\begin{aligned}
\operatorname{Vol}_{\Z^d}(S) &= \frac{d!  \operatorname{vol}(S)}{\det(\Z^d)} = \frac{(d-1)!  \operatorname{vol}(\pi_i(S))}{\det(\pi_i(\Z^d))} \frac{\operatorname{vol}([u_i,v_i])}{\det(\Z^d \cap \R v_i)} \\
&= \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S)) \operatorname{Vol}_{\Z^d \cap \R v_i}([u_i, v_i]),\end{aligned}$$ as desired. 

We now also detail the claim in the introduction, that the discrete surface area defined in \[def:discretesurfarea\] is invariant under unimodular transformations. 

\[cor:discrsurfarea\_invariance\] Let $S$ be a $d$-simplex with the origin in its interior and with rational vertex directions.  Let $A$ be an invertible linear transformation.  Then $$\operatorname{Surf}_{A\Z^d}(AS) = \operatorname{Surf}_{\Z^d}(S).$$ In particular, if $A$ is unimodular, we have $\operatorname{Surf}_{\Z^d}(AS) = \operatorname{Surf}_{\Z^d}(S)$.

As before we write $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ and we let $\pi_i$ be the projection vanishing at $v_i$, for $0 \leq i \leq d$. Clearly, $AS = \operatorname{conv}(\{Av_0,\ldots,Av_d\})$ and the corresponding projection $\bar \pi_i$ vanishing at $Av_i$ can be written as $\bar \pi_i = \pi_i A^{-1}$. Therefore, we get $$\operatorname{Surf}_{A\Z^d}(AS) = \sum_{i=0}^d \operatorname{Vol}_{\bar \pi_i(A\Z^d)}(\bar \pi_i(AS)) = \sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S)) = \operatorname{Surf}_{\Z^d}(S),$$ as claimed. 

Conjecture \[conj:volume\] implies Conjecture \[conj:one\] {#sec:volume_implies_one}
----------------------------------------------------------

\[coro:vol\_one\] \[conj:volume\]  $\Longrightarrow$ \[conj:one\]. 

In view of , it suffices to consider lattice simplices.  Therefore, let $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a lattice $d$-simplex containing the origin in its interior.  Furthermore, let ${\omega}_i$ be the lattice length of the segment $[{\mathbf{0}},v_i]$. Then, $1- {\omega}_i/\ell_i$ is the $i$-th barycentric coordinate of the origin with respect to the vertices of $S$, so that $$\sum_{i=0}^d \left(1- \frac{{\omega}_i}{\ell_i}\right) = 1$$ and, hence, $\sum_{i=0}^d {\omega}_i/\ell_i = d$. On the other hand, for a lattice simplex we have ${\omega}_i\ge 1$. Thus, assuming holds for $S$, we have $$\mu(S) \leq \frac12 \sum_{i=0}^d \frac1{\ell_i} 
\le
\frac12 \sum_{i=0}^d \frac{{\omega}_i}{\ell_i} 
=\frac{d}2.  \qedhere$$

Conjecture \[conj:volume\] holds up to a factor of two
------------------------------------------------------

In the formulation of \[lemma:ell\], \[conj:volume\] is easily proved inductively up to a factor of two. 

\[prop:volume\_factor\_2\] Let $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a $d$-simplex with the origin in its interior and with rational vertex directions.  Then $$\mu(S)\leq 
\sum_{i=0}^d \frac{1}{\ell_i},$$ with the lattice lengths $\ell_i$ defined as above. 

As above, let $u_i$ be the intersection of the line $\R v_i$ with the facet $F$ of $S$ opposite to $v_i$, so that $\ell_i$ is the lattice length of $Q := [u_i,v_i] \subseteq S$. Note, that $u_i$ lies in the relative interior of $F$. Also, let $\pi_i$ be the linear projection vanishing at $v_i$. By the assumptions on $S$, the projection $\pi_i$ is rational and thus $\pi_i(S)$ is a $(d-1)$-dimensional simplex having the origin in its interior and with rational vertex directions with respect to $\pi_i(\Z^d)$.

Using \[lem:projection\] and the induction hypothesis for $\pi_i(S)$, we get $$\begin{aligned}
\mu(S,\Z^d) &\leq \mu(Q,\Z^d \cap L_Q) + \mu(\pi_i(S),\pi_i(\Z^d))
\leq \frac{1}{\ell_i} + \sum_{j \neq i} \frac{1}{\ell_j'},\label{eq:induct_conj:volume}\end{aligned}$$ where the $\ell_j'$ are the corresponding lattice-lengths in $\pi_i(S)$. Thus, to prove the proposition we only need to show that $\ell_j' \geq \ell_j$, for all $j \neq i$. In fact, since the one-dimensional lattice $\pi_i(\Z^d) \cap \pi_i(\R v_j)$ refines $\pi_i(\Z^d \cap \R v_j)$, we have $$\begin{aligned}
\ell_j = \operatorname{Vol}_{\Z^d \cap \R v_j}([u_j, v_j])
&=  \operatorname{Vol}_{\pi_i(\Z^d \cap \R v_j)} ([\pi_i(u_j), \pi_i(v_j)]) \\
&\le  \operatorname{Vol}_{\pi_i(\Z^d) \cap \pi_i(\R v_j)} ([\pi_i(u_j), \pi_i(v_j)]) \leq \ell_j'.  \end{aligned}$$ Here, the last inequality comes from the fact that $[\pi_i(u_j), \pi_i(v_j)] \subseteq \pi_i(S)$ is contained in the ray from the vertex $\pi_i(v_j)$ of $\pi_i(S)$ through the origin. 

\[coro:volume\_dim2\] in the next section proves \[conj:volume\] in the plane.  So we can base the inductive proof above on the stronger assumption that $\mu(S') \leq c_{d-1} \sum_{i=0}^{d-1} \frac{1}{\ell_i'}$, where $S'$ is a $(d-1)$-dimensional simplex and $c_{d-1}$ is a suitable constant with $c_2 = 1/2$. Summing the thus modified inequality  for all indices $0 \leq i \leq d$, yields the recursion $(d+1)c_d = 1+d c_{d-1}$. Solving it shows that $$\mu(S) \leq \frac{2d-1}{2d+2} \sum_{i=0}^d \frac{1}{\ell_i},$$ for all $d$-simplices $S$ with the origin in its interior and with rational vertex directions.  This is a good bound in $\R^3$ since $c_3 = 5/8$.

Conjecture \[conj:volume\] in dimension two {#sec:conj:volume_dim2}
-------------------------------------------

In this section we prove in dimension two.  Our first remarks are valid in arbitrary dimension. 

Throughout, let $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a simplex with the origin in its interior and with rational vertex directions.  For each $i=0,\ldots,d$, let $p_i$ be the primitive positive multiple of $v_i$. Let $\alpha = (\alpha_0,\dots,\alpha_d)\in \N^{d+1}$ be the primitive integer linear dependence among the $p_i$’s.  That is, $$\sum_{i=0}^d \alpha_i p_i = {\mathbf{0}}\qquad \text{and} \qquad \gcd(\alpha_0,\dots,\alpha_d) = 1.$$ Also, for each $i$, let $\beta_i = \alpha_i \|p_i\| / \|v_i\| \in \R_{>0}$, so that $$\sum_{i=0}^d \beta_i v_i = \sum_{i=0}^d \alpha_i p_i  = {\mathbf{0}}.$$

\[rem:coprime\] The fact that the $p_i$’s are primitive imposes some condition on the vector $\alpha \in \N^{d+1}$. Namely, for each $i\in \{0,\ldots,d\}$, we have $$\gcd(\alpha_j : j\ne i) = 1.$$ Indeed, let $\Lambda$ be the lattice generated by $\{p_0,p_1,\ldots,p_d\}$, and let $\Lambda_i$ be the sublattice generated by $\{p_j : j \ne i\}$. Then, the primitive vector of $\Lambda_i$ in the direction of $p_i$ is $$\frac{\sum_{j\ne i} \alpha_j p_j}{\gcd(\alpha_j : j\ne i)}=
\frac{- \alpha_i p_i}{\gcd(\alpha_j : j\ne i)},$$ which is an integer multiple of $p_i$ if, and only if, $\gcd(\alpha_j : j\ne i)= 1$.

As in the previous sections, for each $i$ let $\ell_i$ be the lattice length of $S \cap \R v_i$. The following lemma says that the vectors $\alpha$ and $\beta = (\beta_0,\beta_1,\ldots,\beta_d)$ contain all the information about $S$ needed to compute the right-hand side in . 

\[lemma:barycentric\] The lattice length of $S \cap \R v_i$ equals $$\ell_i = \frac{\alpha_i}{\beta_i} + \frac{\alpha_i}{\sum_{j\ne i} \beta_j}=
\frac{\alpha_i}{\beta_i} \cdot  \frac{\sum_{j=0}^d \beta_j}{\sum_{j\ne i} \beta_j}.$$

To slightly simplify notation, we do the computations for $i=0$. For this, let us use the vectors $p_1,\dots,p_d$ as the basis for a linear coordinate system in $\R^d$. In these coordinates, $p_0$ becomes $$p_0 = - \frac{1}{\alpha_0} \left( \alpha_1,\dots,\alpha_d \right).$$ On the other hand, the equation of the facet of $S$ opposite to $v_0$ is $$\sum_{j=1}^d \frac{\beta_j}{\alpha_j} x_j = 1,$$ so that this facet intersects the line spanned by $p_0$ in the point $$\frac{\left({\alpha_1}, \dots, {\alpha_d}\right)}{ \sum_{j=1}^d \beta_j}
=
\frac{- \alpha_0} {\sum_{j=1}^d \beta_j} \, p_0.$$ Thus, the segment $S \cap \R v_0$ has endpoints $\frac{\alpha_0}{\beta_0} p_0$ and $ \frac{-\alpha_0}{\sum_{j=1}^d \beta_j} p_0$, which implies the statement. 

Observe that the quantity ${\omega}_i$ in the proof of \[coro:vol\_one\] equals $\alpha_i/\beta_i$. With this in mind, one easily recovers the equality $\sum_i \frac{{\omega}_i}{\ell_i}=d$ used in that proof, from \[lemma:barycentric\]. 

### Specializing to dimension two {#specializing-to-dimension-two .unnumbered}

Our proof of in two dimensions is based on applying to the projection $\pi: \R^2 \to \R$ along the direction of $v_i$, for some fixed $i \in \{0,1,2\}$. Then, with the notation above,

(i) $\alpha_0$, $\alpha_1$ and $\alpha_2$ are pairwise coprime, by . 

(ii) The lattice length of $S\cap \pi^{-1}({\mathbf{0}})$ is $\ell_i$.

(iii) The lattice length of $\pi(S)$ equals $$\frac{\alpha_j\alpha_k}{\beta_j}+ \frac{\alpha_j\alpha_k}{\beta_k} =
    \frac{\alpha_j\alpha_k}{\beta_j\beta_k}(\beta_j + \beta_k),$$ where $\{j,k\} = \{0,1,2\} \setminus \{i\}$. Here we use that the projection of the segment $[{\mathbf{0}},v_j]= \frac{\alpha_j}{\beta_j} [{\mathbf{0}},p_j]$ has length $\alpha_k \frac{\alpha_j}{\beta_j}$, since $\gcd(\alpha_j,\alpha_k)=1$ implies that $\pi(\frac{p_j}{\alpha_k})$ is a primitive lattice point in the projection. 

Writing $L=\pi^{-1}({\mathbf{0}})$, gives us $$\mu(S) \le \mu(S\cap L,\Z^2 \cap L) + \mu(\pi(S),\pi(\Z^2)).$$ Hence, the inequality  would follow from: $$\label{eq:volume_dim2}
\frac1{\ell_j} + \frac1{\ell_k} - \frac1{\ell_i} \ge \frac{2\beta_j\beta_k}{\alpha_j\alpha_k(\beta_j + \beta_k)} .$$ We prove this inequality under mild assumptions. 

\[thm:volume\_dim2\] Let $S = \operatorname{conv}(\{v_0,v_1,v_2\}) \subseteq \R^2$ be a triangle with the origin in its interior and with rational vertex directions.  Let the vectors $\alpha$ and $\beta$, and the lengths $\ell_i$ be defined as above, and let $p_0$, $p_1$ and $p_2$ be primitive in the directions of $v_0$, $v_1$ and $v_2$. Assume that $(\alpha_0,\alpha_1,\alpha_2) \ne (1,1,1)$. Then, the inequality  holds for some choice of $i\in \{0,1,2\}$.

Moreover, the inequality is strict unless $(\alpha_0,\alpha_1,\alpha_2) = (2,1,1)$ and $\beta_1=\beta_2$, up to reordering the indices. 

 

(i) \[exm:equal\_alphas\] The necessity of $(\alpha_0,\alpha_1,\alpha_2) \ne (1,1,1)$ is shown by the following example.  If $S=S(1,1,1)$ (so that $\alpha_i = \beta_i = 1$ for all $i$), then $$\frac1{\ell_j} + \frac1{\ell_k} - \frac1{\ell_i}  = \frac23
    \qquad \text{and} \qquad
    \frac{2\beta_j \beta_k}{\alpha_j \alpha_k(\beta_k + \beta_k)} =1,$$ so the inequality fails. 

(ii) \[exm:small\_ell\] Even if $(\alpha_0,\alpha_1,\alpha_2) \ne (1,1,1)$, it is not true that  holds *for every* $i\in \{0,1,2\}$. For ${\omega}>0$, consider the simplex $$S = \operatorname{conv}(\{(0,{\omega}), (-1,-1), (1,-1)\}).$$ It has parameters $(\alpha_0, \alpha_1, \alpha_2) = (2,1,1)$, $(\beta_0, \beta_1, \beta_2) = \left(\frac2{\omega}, 1,1\right)$, $\ell_0={\omega}+1$, and $\ell_1 = \ell_2 = \frac{2{\omega}+2}{{\omega}+2}$. For $i=0$, we indeed have $$\frac1{\ell_1} + \frac1{\ell_2} - \frac1{\ell_0} = 1 
    =
    \frac{2\beta_1\beta_2}{\alpha_1\alpha_2(\beta_1 + \beta_2)}.$$ But for $i \in \{1,2\}$, we get $$\frac1{\ell_j} + \frac1{\ell_k} - \frac1{\ell_i} = \frac1{\ell_0} = \frac1{{\omega}+1}
    <
    \frac2{{\omega}+2}
    =
    \frac{2\beta_j\beta_k}{\alpha_j\alpha_k(\beta_j + \beta_k)}.$$

*Case 1: At most one of the $\alpha_i$s equals 1.*  Say $\alpha_1\ne 1\ne \alpha_2$. With no loss of generality assume $\ell_2\ge \ell_1$. Then, by , $$\begin{aligned}
\frac1{\ell_0} + \frac1{\ell_1} - \frac1{\ell_2} 
& \ge \frac1{\ell_0} 
= \frac{\beta_0}{\alpha_0} \cdot \frac{\beta_1 + \beta_2}{\beta_0+\beta_1+\beta_2} 
 > \frac{\beta_0}{\alpha_0} \cdot \frac{\beta_1}{\beta_0 + \beta_1}
  \ge \frac{2\beta_0\beta_1}{\alpha_0\alpha_1(\beta_0 + \beta_1)}.     \end{aligned}$$

*Case 2: Two of the $\alpha_i$s equal 1.*  Assume that $\alpha_1=\alpha_2=1$. The condition $(\alpha_0,\alpha_1,\alpha_2) \ne (1,1,1)$ then implies $\alpha_0\ge 2$, so that gives $$\begin{aligned}
\frac1{\ell_1} + \frac1{\ell_2} - \frac1{\ell_0} 
& = \frac{\beta_1(\beta_0 + \beta_2)}{\beta_0+\beta_1+\beta_2} 
     + \frac{\beta_2(\beta_0 + \beta_1)}{\beta_0+\beta_1+\beta_2} 
     - \frac{\beta_0}{ \alpha_0} \cdot \frac{\beta_1 + \beta_2}{\beta_0+\beta_1+\beta_2} \\
& = \frac{
          2 \beta_1\beta_2
          +  \left(1-\frac1{\alpha_0}\right) \beta_0 (\beta_1 +\beta_2) 
          }
     {\beta_0+\beta_1+\beta_2} 
\overset{*}{\ge} \frac{
          2 \beta_1\beta_2
          + \frac12 \beta_0 (\beta_1 +\beta_2)
          }
     {\beta_0+\beta_1+\beta_2}. 
$$ Thus, the inequality we want to prove is $$\begin{aligned}
\frac{
          2 \beta_1\beta_2
          + \frac12 \beta_0 (\beta_1 +\beta_2)
          }
     {\beta_0+\beta_1+\beta_2} \ge
 \frac{2\beta_1\beta_2}{\beta_1 + \beta_2}\end{aligned}$$ or, equivalently, $$\begin{aligned}
          2 \beta_1\beta_2 (\beta_1 +\beta_2)
          + \frac12 \beta_0 (\beta_1 +\beta_2)^2 \ge
    2\beta_1\beta_2 (\beta_0+\beta_1+\beta_2).\end{aligned}$$ This is equivalent to $(\beta_1 +\beta_2)^2 \overset{*}{\ge} 4 \beta_1\beta_2$, which clearly holds. 

The two inequalities we used, marked with “$\overset{*}{\ge}$”, are equalities if and only if $\alpha_0 =2$ and $\beta_1=\beta_2$, respectively. 

We now prove for $d=2$, which together with \[coro:ConjA\_dim2\] and \[prop:conj:v\_plane\], gives the third proof of \[conj:one\] in the plane. 

\[coro:volume\_dim2\] holds in dimension two. 

Let $S = \operatorname{conv}(\{v_0,v_1,v_2\}) \subseteq \R^2$ be a triangle with the origin in its interior and with rational vertex directions.  Let the vectors $\alpha$ and $\beta$, and the lengths $\ell_i$ be defined as above, taking $p_0$, $p_1$ and $p_2$ primitive.  In view of we need to show that $$\mu(S) \le \frac12\left( \frac1{\ell_0} + \frac1{\ell_1} + \frac1{\ell_2} \right).$$ If $(\alpha_0,\alpha_1,\alpha_2) = (1,1,1)$, then consider the lattice $\Lambda$ generated by $p_0,p_1,p_2$. Let $A$ be the linear transformation sending $e_i$ to $p_i$, for $i=1,2$. Then, $\Lambda = A\Z^2$ and $S=A S({\omega})$ for a suitable ${\omega}\in \R^3_{>0}$. Moreover, since the $p_i$s are primitive, the lattice lengths $\ell_i$ are the same for every pair $(S,\Z^2)$, $(S,\Lambda)$, and $(S({\omega}),\Z^2)$. Observing that $\Lambda \subseteq \Z^2$ is a sublattice, we may therefore apply and get $$\mu(S) \leq \mu(S,\Lambda) = \mu(S({\omega}),\Z^2) = \frac12\left( \frac1{\ell_0} + \frac1{\ell_1} + \frac1{\ell_2} \right).$$ So, we assume that $(\alpha_0,\alpha_1,\alpha_2) \neq (1,1,1)$ and thus we can apply , which provides us with an index $i \in \{0,1,2\}$ such that the inequality  holds.  As we saw above, this implies the desired bound. 

Analogs to Conjecture \[conj:volume\] with the origin in the boundary {#sec:0inboundary}
---------------------------------------------------------------------

As we said in the introduction, the question analogous to for general lattice polytopes has an easy answer: the maximum covering radius among all $d$-dimensional lattice polytopes equals $d$ and is attained by, and only by, unimodular simplices.  This phenomenon generalizes to analogs of \[thm:lambda\] and \[conj:volume\], which admit easy proofs.  The generalization concerns the simplices $S({\omega})$, except we now allow one of the entries of ${\omega}$ (typically the first one) to be zero so that the origin becomes a vertex:

\[prop:corner\] For an ${\omega}\in \R^{d}_{>0}$ let $$S(0,{\omega}):=\operatorname{conv}(\left\{{\mathbf{0}}, {\omega}_1 e_1, \ldots, {\omega}_d e_d\right\}).$$ Then $$\mu(S(0,{\omega}) )
=
 {\sum_{i=1}^d \frac{1}{{\omega}_i}}
=
 \frac{\sum_{i=1}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S({\omega})))} {\operatorname{Vol}_{\Z^d}(S({\omega}))},$$ where $\pi_i: \R^d \to \R^{d-1}$ is the linear projection that forgets the $i$-th coordinate. 

$S(0,{\omega}) $ can be redescribed as $$\left\{x\in \R_{\ge0}^d : \sum_{i=1}^d \frac{x_i}{{\omega}_i} \le 1\right\}.$$ In this form it is clear that $\mu(S(0,{\omega}))$ equals the unique $\mu\in [0,\infty)$ such that ${\mathbf{1}}_d$ lies in the boundary of $\mu\cdot S(0,{\omega})$, which equals $\sum_i \frac1{{\omega}_i}$, as stated. 

\[coro:corner\] Let $S = \operatorname{conv}(\{{\mathbf{0}},v_1,\ldots,v_d\}) \subseteq \R^d$ be a $d$-simplex with rational vertex directions.  For each $i=1,\ldots,d$, let $\pi_i : \R^d \to \R^{d-1}$ be the linear projection vanishing at $v_i$. Then, $$\mu(S) \leq \frac{\sum_{i=1}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S))}
{\operatorname{Vol}_{\Z^d}(S)},$$ with equality if and only if $S$ is unimodularly equivalent (by a transformation fixing the origin) to $S(0,{\omega})$ for some ${\omega}\in \R_{> 0}^d$.

Let $p_1,\ldots,p_d \in \Z^d$ be the primitive vertex directions of $S$, so that $v_i = {\omega}_i p_i$, where ${\omega}_i$ is the lattice length of the segment $[{\mathbf{0}},v_i]$, for each $i=1,\ldots,d$. Then, the linear map sending $p_i \mapsto e_i$, $i=1,\ldots,d$, sends $S$ to $S(0,{\omega})$ and $\Z^d$ to a lattice $\Lambda$ containing $\Z^d$. This implies $$\mu(S, \Z^d)= \mu(S(0,{\omega}), \Lambda) \leq \mu(S(0,{\omega}),\Z^d) = \frac{\sum_{i=1}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S))}
{\operatorname{Vol}_{\Z^d}(S)},$$ by . 

The ‘if’ in the equality case is obvious: in this case $\Lambda = \Z^d$. For the ‘only if’ suppose that $\Lambda$ is a proper superlattice of $\Z^d$ and let $p \in \Lambda \cap [0,1)^d\setminus\{{\mathbf{0}}\}$ be a non-zero lattice point in the half-open unit cube.  Let $\mu=\mu(S(0,{\omega}), \Z^d) = \frac{\sum_{i=1}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S))} {\operatorname{Vol}_{\Z^d}(S)}$. Then, the point ${\mathbf{1}}$ is the only point in the unit cube $[0,1]^d$ that is last covered by $\Z^d + \mu \cdot S(0,{\omega})$. Since ${\mathbf{1}}$ lies in the interior of $p + \mu \cdot S(0,{\omega})$, the covering radius of $S(0,{\omega})$ is strictly smaller with respect to $\Lambda$ than it is with respect to $\Z^d$.

Our next results say that \[prop:corner\] and \[coro:corner\] are not only analogs (without the factor of two) of \[thm:lambda\] and \[conj:volume\], but also a limit of them when we make one of the vertices tend to zero.  We consider this as additional evidence for .  Formally:

\[thm:limit\] Let $S= \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a $d$-simplex with the origin in its interior and with rational vertex directions.  For each $i \in \{0,\ldots,d\}$ consider the one-parameter family of simplices $$S^{(i)}_t:= \operatorname{conv}(\{v_0,\ldots,tv_i,\ldots,v_d\}), \quad t \in [0,1],$$ so that $S^{(i)}_1=S$ and $S^{(i)}_0 = \operatorname{conv}(\{v_1,\ldots,{\mathbf{0}},\ldots,v_d\})$. For each $i=0,\dots,d$ let $\pi_i : \R^d \to \R^{d-1}$ be the linear projection vanishing at $v_i$.

Then, there is an index $j \in \{0,\ldots,d\}$ such that $$\label{eq:limit}
\lim_{t\to 0} \frac12 \frac{\sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S^{(j)}_t))} {\operatorname{Vol}_{\Z^d}(S^{(j)}_t)}
\ge
\frac{\sum_{i=0, i \neq j}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S^{(j)}_0))} {\operatorname{Vol}_{\Z^d}(S^{(j)}_0)},$$ with equality if and only if the primitive lattice vectors parallel to $v_0,\ldots,v_d$ add up to zero. 

Observe that the condition for equality includes, but is more general than, the case when $S$ is of the form $S({\omega})$.

For each $i$, let $u_i$ be the primitive lattice vector parallel to $v_i$, and let $U=\{u_0,\ldots,u_d\}$. We choose $j$ to be an index minimizing the (absolute value of the) determinant of $U \setminus \{u_i\}$ among all $i$. Observe that $S$ is of the form $S({\omega})$ if and only if all those determinants are equal to $1$.

To simplify notation, in the rest of the proof we assume $j=0$ and we drop the superindex from the notation $S^{(j)}_t$.

Since the volume functional is continuous, we have $$\lim_{t\to 0}  {\operatorname{Vol}_{\Z^d}(S_t)} = {\operatorname{Vol}_{\Z^d}(S_0)},$$ and, for each $i=1,\dots,d$, $$\lim_{t\to 0}  \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S_t)) = \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S_0)).$$ Thus, the only thing to prove is that $$\lim_{t\to 0} \operatorname{Vol}_{\pi_0(\Z^d)}(\pi_0(S_t))
\ge
 \sum_{i=1}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S_0)).$$ The volume on the left-hand side does not depend on $t$ because the vertex of $S_t$ that depends on $t$ is projected out by $\pi_0$. Moreover, this volume equals $\sum_{i=1}^d\operatorname{Vol}_{\pi_0(\Z^d)}(\pi_0(F_i))$, where $F_i$ is the facet of $S_0$ opposite to $v_i$. Similarly, $\operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S_0)) = \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(F_i))$. Hence, the inequality follows from $$\label{eq:two_projections}
\operatorname{Vol}_{\pi_0(\Z^d)}(\pi_0(F_i)) \ge \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(F_i)).$$ Both sides of \[eq:two\_projections\] are integer multiples of $\operatorname{Vol}_{\Z^d \cap \operatorname{aff}(F_i)}(F_i)$, with the proportionality factors being the lattice distances from $F_i$ to $u_0$ and to $u_i$, respectively.  These distances are proportional to the determinants of $U\setminus \{u_i\}$ and $U\setminus \{u_0\}$, so our assumption on $u_0$ minimizing this implies the statement.  Moreover, we have equality if, and only if, all the determinants of $U\setminus \{u_i\}$ are equal to that of $U\setminus \{u_0\}$. This in turn is equivalent to $\sum_{i=0}^d u_i={\mathbf{0}}$.

\[coro:limit\] In the conditions of \[thm:limit\] and for the index $j$ mentioned therein, we have $$\lim_{t\to 0} \mu(S^{(j)}_t) \le
\lim_{t\to 0} \frac12 \frac{\sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S^{(j)}_t))} {\operatorname{Vol}_{\Z^d}(S^{(j)}_t)},$$ with equality if and only if the primitive lattice vectors parallel to $v_0,\dots,v_d$ add up to zero. 

This follows from \[thm:limit\] since $$\lim_{t\to 0} \mu(S^{(j)}_t) = \mu(S^{(j)}_0) \le \frac{\sum_{i=0,i \neq j}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S^{(j)}_0))} {\operatorname{Vol}_{\Z^d}(S^{(j)}_0)},$$ where the last inequality is \[coro:corner\]. 

\[rem:limit\] \[eq:limit\] is not true for all choices of $j$. Without any assumption on $j$ the proof of \[thm:limit\] carries through up to the point where we say that \[eq:limit\] would follow from \[eq:two\_projections\], but the latter inequality is not true in general.  For a specific example, let $S=\operatorname{conv}(\{(0,-1), (1,1), (-1,1)\})$ and consider $j=0$. Then, for $i=1,2$, $$\operatorname{Vol}_{\pi_0(\Z^d)}(\pi_0(F_i)) = 1 < 2 =  \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(F_i)).$$ This gives $$\lim_{t\to 0} \frac12 \frac{\sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S^{(0)}_t))} {\operatorname{Vol}_{\Z^d}(S^{(0)}_t)} = \frac12\cdot\frac{2+2+2}{2} = \frac32,$$ and $$\frac{\sum_{i=1}^d \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S^{(0)}_0))} {\operatorname{Vol}_{\Z^d}(S^{(0)}_0)} = \frac{2+2}{2} = 2.$$

We finally look at the intermediate case where ${\mathbf{0}}$ is in the boundary of $S= \operatorname{conv}(\{v_0,\ldots,v_d\})$ but not a vertex.  We can generalize \[conj:volume\] to

\[conj:volume2\] Let $S = \operatorname{conv}(\{v_0,\ldots,v_d\})$ be a $d$-simplex with ${\mathbf{0}}\in S\setminus \{v_0,\ldots,v_d\}$, and with rational vertex directions.  Let $\pi_i:\R^d \to \R^{d-1}$ be the linear projection vanishing at $v_i$. Let $I\subset\{0,\dots,d\}$ be the set of labels of facets of $S$ containing ${\mathbf{0}}$. Then $$\begin{aligned}
\mu(S) \leq \frac12 \frac{\sum_{i=0}^d \operatorname{Vol}_{\pi_i(\Z^d)} (\pi_i(S)) + \sum_{i\in I} \operatorname{Vol}_{\pi_i(\Z^d)} (\pi_i(S))}
{\operatorname{Vol}_{\Z^d}(S)}. 
\label{eq:volume2}\end{aligned}$$

\[prop:volume2\] \[conj:volume2\] $\Longleftrightarrow$ \[conj:volume\]. 

The implication \[conj:volume2\] $\Longrightarrow$ \[conj:volume\] is obvious, since the latter is the case $I=\emptyset$ of the former. 

For the other implication, for each $i=0,\ldots,d$, let $$\ell_i  =\frac{\operatorname{Vol}_{\Z^d}(S)}{\operatorname{Vol}_{\pi_i(\Z^d)} (\pi_i(S))},$$ which equals the lattice length of the segment $S \cap \operatorname{lin}(\{v_i\})$. The inequality in \[conj:volume2\] we want to prove becomes $$\mu(S) \leq \frac12 \sum_{i\not\in I} \frac1{\ell_i} + \sum_{i\in I} \frac1{\ell_i}.$$ Let $S_I= \operatorname{conv}(\{v_i : i \not\in I\})$, and $S_{\overline I}=\operatorname{conv}(\{{\mathbf{0}}\} \cup \{v_i: i \in I\})$. Observe that $S_I$ equals the intersection of the facets of $S$ containing ${\mathbf{0}}$, hence it is a $(d-|I|)$-simplex with ${\mathbf{0}}$ in its relative interior.  $S_{\overline I}$ is an $|I|$-simplex with ${\mathbf{0}}$ as a vertex.  Hence, \[conj:volume\] and \[prop:corner\] respectively say: $$\mu(S_I) \le \frac12 \sum_{i \not\in I} \frac1{\ell_i} \qquad\text{and}\qquad
\mu(S_{\overline I}) \le \sum_{i \in I} \frac1{\ell_i}.$$ Consider the linear projection $\pi_I: \R^d \to \R^{I}$ vanishing on $S_I$. By \[lem:projection\] $$\mu(S) \le \mu(S_I) + \mu (\pi_I(S)),$$ so it only remains to show that $$\mu (\pi_I(S)) \le \mu(S_{\overline I}).$$ This holds because $\pi_I$ is an affine bijection from $S_{\overline I}$ to $\pi_I(S)$, so that $\pi_I(S)$ can be considered to be the same as $S_{\overline I}$ except regarded with respect to a (perhaps) finer lattice. 

Covering minima of the simplex S(w) {#sec:lambda}
===================================

The covering radius of S(w) {#sec:lambda_proof}
---------------------------

We here prove \[thm:lambda\] and thus compute the covering radius of $S({\omega})=\operatorname{conv}(\left\{-{\omega}_0 {\mathbf{1}}_d,{\omega}_1 e_1,\ldots,{\omega}_d e_d\right\})$.

The simplex $S({\omega})$ can be triangulated into the $d+1$ simplices $$S_i = \operatorname{conv}(\left\{{\mathbf{0}},{\omega}_0 e_0, {\omega}_1 e_1, \ldots, {\omega}_d e_d\right\} \setminus \{{\omega}_i e_i\}), \quad 0 \leq i \leq d,$$ where $e_0 = -{\mathbf{1}}_d$. Writing $[d]_0 := \{0,1,\ldots,d\}$, we define $$\mathring{P}_i = \bigg\{ \sum_{j \in [d]_0 \setminus \{i\}} \alpha_j e_j : 0 \leq \alpha_j < 1 \bigg\}$$ the half-open parallelotope spanned by the primitive edge directions of $S_i$ incident to the origin.  Let $i \in [d]_0$ be fixed.  Then, for any $x \in \R^d$ there is a lattice point $v_i \in \Z^d$ such that $x \in v_i + \lambda S_i$ and the dilation factor $\lambda \geq 0$ is the smallest possible.  Let $L_i(x)$ be the set of all such lattice points $v_i$. For a fixed $v \in \Z^d$, we define $$R_i(v) = \left\{x \in \R^d : v \in L_i(x)\right\}$$ to be the region of points that are associated to $v$ in this way. 

Explicitly these regions are translates of the $\mathring{P}_i$, more precisely we claim that $R_i(v)=v + \mathring{P}_i$, for all $i \in [d_0]$.

Indeed, let $x \in R_i(v)$, and let $\lambda \geq 0$ be smallest possible such that $x \in v + \lambda S_i$. By the definition of $S_i$, we can write $x-v = \sum_{j \in [d]_0 \setminus \{i\}} \alpha_j e_j$, for some $\alpha_j \geq 0$. If there would be an index $j$ such that $\alpha_j \geq 1$, then $x \in v + e_j + \lambda S_i$ and the intersection of this simplex and $v + \lambda S_i$ is a smaller homothetic copy of $S_i$ containing $x$. Thus, $\lambda$ is not minimal and this contradiction implies that $x \in v + \mathring{P}_i$. Conversely, if $x-v = \sum_{j \in [d]_0 \setminus \{i\}} \alpha_j e_j \in \mathring{P}_i$, and $\lambda \geq 0$ is minimal such that $x \in v + \lambda S_i$, then $x-v$ lies in the facet of $\lambda S_i$ not containing the origin.  Since $0 \leq \alpha_j < 1$, for all $j \in [d]_0 \setminus \{i\}$, the scalar $\lambda$ is not only minimal for $v$, but for any lattice point.  Hence, $v \in L_i(x)$.

With this observation, the regions $R_i(v)$ are seen to be induced by the arrangement of the hyperplanes $\{x_i = a \}, \{x_i -x_j = a\}$ for all $j \in [d]_0 \setminus \{i\}$ and $a \in \Z$, where we define $x_0 = 0$. We call this arrangement $A_d^i$. Moreover, for a point $x$ in the interior of $R_i(v)$, the associated lattice point is unique, and we call it $v_i(x)$.

The smallest common refinement $\A_d$ of the arrangements $\A_d^0,\ldots,\A_d^d$ is known as the *alcoved arrangement* (see [@becksanyal2018combinatorial Ch.  7] for a detailed description).  The full-dimensional cells of $\A_d$, also called its *chambers*, are lattice translations of the simplices $$C_\pi =\operatorname{conv}\left(\left\{{\mathbf{0}}, e_{\pi(1)}, e_{\pi(1)}+e_{\pi(2)}, \ldots, e_{\pi(1)}+\ldots+e_{\pi(d)}\right\}\right),$$ where $\pi$ is a permutation of $\{1,\ldots,d\}$.

Each chamber of $A_d$ is the intersection of regions $R_i(v)$. More precisely, $$\begin{aligned}
\operatorname{int}(C_\pi) &= R_0({\mathbf{0}}) \cap R_{\pi(1)}(e_{\pi(1)}) \cap  \ldots \cap R_{\pi(d)}(e_{\pi(1)} +\ldots+e_{\pi(d)}) \\
&= \mathring{P}_0 \cap (e_{\pi(1)} + \mathring{P}_{\pi(1)} )\cap  \ldots \cap (e_{\pi(1)} +\ldots+e_{\pi(d)} + \mathring{P}_{\pi(d)}).\end{aligned}$$ Therefore, the chambers $C_\pi$ are exactly those regions of points in $\R^d$ that, for each $i \in [d]_0$, are associated to the same lattice point, that is, $v_i(x)=v_i(y)$ for all $x, y \in \operatorname{int}(C_\pi)$.

After these preparations, we are ready to compute the covering radius of $S({\omega})$. Note that, since $[0,1]^d$ is a fundamental cell of $\Z^d$, we only need to find the smallest dilation factor $\mu$ so that the lattice translates of $\mu S({\omega})$ cover the unit cube.  Moreover, we may focus on what happens within one chamber $C_\pi$, and by symmetry we assume that $\pi = {\text{Id}}$. Among all points in $C_{\text{Id}}= \operatorname{conv}\left(\left\{{\mathbf{0}}, e_1, e_1+e_2, \ldots, e_1+\ldots+e_d\right\}\right)$, we are looking for a point $y$ which is last covered by dilations of $S_i + e_{[i]}$, for some $i \in [d]_0$, and the factor of dilation needed.  Here, we write $e_{[i]} = e_1+\ldots+e_i$. If we let $\ell_i : \R^d \to \R$ be the linear functional which takes value $1$ on the facet $F_i$ of $S({\omega})$ that is opposite to ${\omega}_i e_i$, this is equivalent to $$y = \operatorname*{argmax}_{x \in C_{\text{Id}}} \min_{i \in [d]_0} |\ell_i(x-e_{[i]})|.$$ The key observation is that $y$ is the point where all the values $|\ell_i(y-e_{[i]})|$, $0 \leq i \leq d$, are equal.  This is because $\ell_i(x-e_{[i]})$ is nonnegative for $x \in C_{\text{Id}}$ and because there is a positive linear dependence among the functionals $\ell_i$, so there cannot be a point $y'$ where they all achieve a larger value than at a point where they all achieve the same value.  Therefore,  $y$ satisfies the conditions $$\begin{aligned}
\ell_0(y) = \ell_i(y-e_{[i]}), \quad \text{for every }1 \leq i \leq d.\end{aligned}$$ The explicit expression of the functionals $\ell_i$ is $$\begin{aligned}
\ell_0(x) = \sum_{j=1}^d {\omega}_j^{-1} x_j \quad \text{and} \quad \ell_i(x) = \sum_{j \in [d] \setminus \{i\}} {\omega}_j^{-1}x_j -\left(\sum_{j \in [d]_0 \setminus \{i\}}{\omega}_j^{-1} \right) x_i.\end{aligned}$$ Thus we need to solve the system of the following equations: $$\sum_{j=1}^d {\omega}_j^{-1} y_j  = \sum_{j \in [d] \setminus \{i\}} {\omega}_j^{-1}y_j -\left(\sum_{j \in [d]_0 \setminus \{i\}}{\omega}_j^{-1} \right) y_i + {\omega}_0^{-1} + \sum_{j>i} {\omega}_j^{-1}, \quad 1 \leq i \leq d.$$ This system is solved by $y=(y_1,\ldots,y_d)$ with $$y_i = \frac{{\omega}_0^{-1} + {\omega}_{i+1}^{-1} + \ldots +{\omega}_d^{-1}}{{\omega}_0^{-1} + {\omega}_1^{-1} + \ldots +{\omega}_d^{-1}}.$$ The value that the functionals take at $y$ is by what we said above the covering radius of $S({\omega})$, and it is given by $$\mu(S({\omega})) = \ell_0(y) =  \frac{\sum_{0 \leq i < j \leq d} {\omega}_i^{-1}{\omega}_j^{-1}}{\sum_{i=0}^d {\omega}_i^{-1}},$$ as desired. 

\[cor:conjC\_primitiveSimplices\] Let $S \subseteq \R^d$ be a simplex with the origin it its interior and with rational vertex directions.  If the primitive vertex directions $p_0,p_1,\ldots,p_d$ of $S$ satisfy $p_0+p_1+\ldots+p_d={\mathbf{0}}$, then holds for $S$.

The proof is basically given already in .  Consider the lattice $\Lambda$ generated by $p_0,p_1,\ldots,p_d$, and let $A$ be the linear transformation sending $e_i$ to $p_i$, for $i=1,\ldots,d$. Then, $\Lambda = A\Z^d$ and $S=A S({\omega})$ for a suitable ${\omega}\in \R^{d+1}_{>0}$. Since the $p_i$s are primitive, the lattice lengths $\ell_i=\frac{\operatorname{Vol}_{\Z^d}(S)}{ \operatorname{Vol}_{\pi_i(\Z^d)}(\pi_i(S))}$ are the same for every pair $(S,\Z^d)$, $(S,\Lambda)$, and $(S({\omega}),\Z^d)$. Using that $\Lambda \subseteq \Z^d$ is a sublattice, we therefore apply and get $$\mu(S) \leq \mu(S,\Lambda) = \mu(S({\omega}),\Z^d) = \frac12 \sum_{i=0}^d \frac{1}{\ell_i}.  \qedhere$$

Observe that \[thm:lambda\] says that \[eq:volume\] in \[conj:volume\] is an equality for simplices of the form $S({\omega})$. Other simplices may also produce an equality, as the triangle $T = S({\mathbf{1}}_2) \oplus S'({\mathbf{1}}_2)$ shows: $$\frac12 \frac{\sum_{i=0}^2 \operatorname{Vol}_{\pi_i(\Z^2)} (\pi_i(T))} {\operatorname{Vol}_{\Z^2}(T)} = 
\frac12 \cdot \frac{3 + 3 + 2}{4} = 1 = \mu(T).$$

The covering product conjecture {#sec:covprod}
-------------------------------

The following conjecture was proposed in [@gonzalezschymura2017ondensities], which was the initial motivation to compute the covering minima of the simplex $S({\mathbf{1}}_{d+1})$.

\[conj:cov\_prod\] For every convex body $K \subseteq \R^d$, $$\mu_1(K)\cdot\ldots\cdot\mu_d(K)\cdot\operatorname{vol}(K) \geq \frac{d+1}{2^d}.$$ Equality is attained for the simplex $S({\mathbf{1}}_{d+1})$.

\[conj:cov\_prod\] is known to hold for $d=2$ [@schnell1995a].  We show it in arbitrary dimension for the simplices $S({\omega})$.

\[cor:lambda\_cov\_prod\] For every ${\omega}\in \R^{d+1}_{>0}$, we have $$\mu_1(S({\omega})) \cdot \ldots \cdot \mu_d(S({\omega})) \cdot \operatorname{Vol}_{\Z^d}(S({\omega})) \geq \frac{(d+1)!}{2^d}.$$ Equality can hold only if ${\omega}_0 = {\omega}_1 = \ldots = {\omega}_d$.

Since every permutation of the vertices of $S({\mathbf{1}})$ is a unimodular transformation, and since the considered product functional is invariant under unimodular transformations, we can assume that ${\omega}_0 \leq {\omega}_1 \leq \ldots \leq {\omega}_d$. By , the covering radius of $S({\omega})$ is given by $$\mu(S({\omega})) = \frac{\sigma_{d-1}({\omega}_0,{\omega}_1,\ldots,{\omega}_d)}{\sigma_d({\omega}_0,{\omega}_1,\ldots,{\omega}_d)},$$ where $\sigma_j({\omega}_0,{\omega}_1,\ldots,{\omega}_d) = \sum_{0\leq i_1 < \ldots < i_j \leq d} \prod_{\ell=1}^j {\omega}_{i_\ell}$ is the *$j$-th elementary symmetric function* in the ${\omega}_i$’s.  Writing ${\omega}_I = ({\omega}_0,{\omega}_{i_1},\ldots,{\omega}_{i_j})$, for every index set $I = \{i_1,\ldots,i_j\} \subseteq \{1,\ldots,d\}$, $|I|=j$, we project onto the $j$-dimensional coordinate plane indexed by $I$ and obtain $\mu_j(S({\omega})) \geq \mu_j(S({\omega}_I))$. In particular, choosing $I=\{1,\ldots,j\}$, we have $$\begin{aligned}
\mu_j(S({\omega})) \geq \frac{\sigma_{j-1}({\omega}_0,{\omega}_1,\ldots,{\omega}_j)}{\sigma_j({\omega}_0,{\omega}_1,\ldots,{\omega}_j)}.\label{eqn:covmins_lambda}\end{aligned}$$ Next, in view of ${\omega}_j \geq {\omega}_{j-1} \geq \ldots \geq {\omega}_0$, we get $$\begin{aligned}
\frac{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_j)}{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_{j-1})} &= \frac{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_{j-1}) + {\omega}_j \, \sigma_{j-2}({\omega}_0,\ldots,{\omega}_{j-1})}{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_{j-1})} \nonumber \\
  &= 1 + \frac{{\omega}_j \, \sigma_{j-2}({\omega}_0,\ldots,{\omega}_{j-1})}{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_{j-1})} \geq 1+\frac{\binom{j}{2}}{j} = \frac{j+1}{2}, \label{eqn:covmins_lambda_2}\end{aligned}$$ with strict inequality unless ${\omega}_j = {\omega}_{j-1} = \ldots = {\omega}_0$.

Finally, computing the volumes of the pyramids over the $d+1$ facets of $S({\omega})$ with apex at the origin, we obtain $\operatorname{Vol}_{\Z^d}(S({\omega})) = \sigma_d({\omega}_0,{\omega}_1,\ldots,{\omega}_d)$. Combining this with  and  yields $$\begin{aligned}
\mu_1(S({\omega})) \cdot \ldots \cdot \mu_d(S({\omega})) \cdot \operatorname{Vol}_{\Z^d}(S({\omega})) &\geq \prod_{j=1}^d \frac{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_j)}{\sigma_j({\omega}_0,\ldots,{\omega}_j)} \sigma_d({\omega}_0,\ldots,{\omega}_d) \\
&= \prod_{j=1}^{d} \frac{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_{j})}{\sigma_{j-1}({\omega}_0,\ldots,{\omega}_{j-1})} \geq \frac{(d+1)!}{2^d}.\end{aligned}$$ Furthermore, equality can only hold if ${\omega}_0 = {\omega}_1 = \ldots = {\omega}_d$ as otherwise  would be strict for $j=d$.

Note that if holds, then the simplex $S({\mathbf{1}}_{d+1})$ attains equality in (this was the original motivation in [@gonzalezschymura2017ondensities] to state ). 

With the notation of the proof above, for each $I \subseteq\{1,\ldots,d\}$, $|I| = j$, we have $\mu_j(S({\omega}_I)) \leq \mu_j(S({\omega}_0,{\omega}_1,\ldots,{\omega}_j))$, just because $S({\omega}) \subseteq S(\bar{\omega})$, whenever ${\omega}_i \leq \bar{\omega}_i$, for all $i$. Therefore, the bound in  is maximal among coordinate projections of $S({\omega})$. This suggests the following common generalization of and . 

\[conj:mu\_j\_lambda\] For every ${\omega}\in \R^{d+1}_{>0}$ with ${\omega}_0 \leq {\omega}_1 \leq \ldots \leq {\omega}_d$, and every $j \in \{1,\ldots,d\}$, the $j$-th covering minimum of the simplex $S({\omega})$ is attained by the projection to the first $j$ coordinates.  That is: $$\mu_j(S({\omega})) = \mu_j(S({\omega}_0,\dots, {\omega}_j)) = \frac{\sigma_{j-1}({\omega}_0,{\omega}_1,\ldots,{\omega}_j)}{\sigma_j({\omega}_0,{\omega}_1,\ldots,{\omega}_j)}.$$

Besides the case $j=d$ () also the case $j=1$ of \[conj:mu\_j\_lambda\] holds.  Assuming that ${\omega}_0 \leq {\omega}_1 \leq \ldots \leq {\omega}_d$, it states that $\mu_1(S({\omega}))=\frac{1}{{\omega}_0+{\omega}_1}$. Since  provides the lower bound, this is equivalent to $$\det(\Z^d | L_z) \leq \frac{\| S({\omega}) | L_z \|}{{\omega}_0+{\omega}_1},$$ for all primitive $z \in \Z^d\setminus\{{\mathbf{0}}\}$, where $L_z = \operatorname{lin}\{z\}$. In view of $\det(\Z^d | L_z) = \|z\|^{-1}$ and $e_i | L_z = \frac{z_i}{\|z\|^2} z$, it follows from an elementary computation. 

Conjecture \[conj:k\]: Lattice polytopes with k interior lattice points {#sec:k_points}
=======================================================================

We now look at , that is, we investigate the maximum covering radius among lattice $d$-polytopes with at least $k \geq 2$ interior lattice points.  The conjectured maximum covering radius $\frac{d-1}2+\frac1{k+1}$ is attained by the polytopes of the form $$[0,k+1] \oplus T_1\oplus \dots \oplus T_m,$$ where each $T_i$ is a non-hollow lattice $d_i$-polytope of covering radius $d_i/2$, with $\sum_{i=1}^m d_i=d-1$. The different $T_i$ can be translated to have their (unique) interior lattice point at different positions along the segment $[0,k+1]$ in much the same way as in the examples of .  In the following we analyze the possibilities in dimensions two and three:

\[exm:dim2-k\] In dimension two we have a single $T_i$, the segment $[-1,1]$, but we can place it at different heights with respect to $[0,k+1]$. For each $k$ we can construct $\lfloor (k+3)/2 \rfloor$ non-isomorphic lattice polygons with $k$ interior lattice points and of covering radius $\frac12 + \frac1{k+1}$, namely: $$\operatorname{conv}(\{(0,0), (0,k), (-1,i), (1,i)\}), \quad i=0,\dots, \lfloor (k+1)/2 \rfloor.$$ The case $i=0$ coincides with the triangle $M_k(0)$; the cases $i>0$ produce kite-shaped quadrilaterals. 

Observe that the triangle $M_k(1)\cong S(k,1,1)$ is very similar to but has smaller area than $M_k(0)$. One could expect it to achieve a larger covering radius but it does not, as computed in \[rem:M\_k-dim2\]: $$\mu(M_k(1)) = \frac{k+2}{2k+1} = \frac12 + \frac3{4k+2} <  \frac12 + \frac1{k+1}, \ \ \text{ if } k \geq 2.$$

\[exm:dim3-k\] In dimension three we can have $[0,k+1]\oplus T$ with $\dim(T)=2$ or $[0,k+1]\oplus T_1\oplus T_2$ with $\dim(T_1)=\dim(T_2)=1$.

If the latter happens then $T_1=T_2=[-1,1]=I$ and, again, they can be placed at different heights along the segment $[0,k+1]$. This gives quadratically many non-isomorphic octahedra (when both $T_1$ and $T_2$ intersect $[0,k+1]$ in the interior), linearly many triangular bipyramids (when one intersects in the interior and the other at an end-point), plus the square pyramid $[0,k+1] \oplus I \oplus I$ and the tetrahedron $M_k(0,0)$ (when both intersect at end-points). 

In the case $[0,k+1]\oplus T$, $T$ can be either $S({\mathbf{1}}_3)$ or $I\oplus I'$; the case $T=I \oplus I$ being already covered above.  This produces two tetrahedra $[0,k+1] \oplus S({\mathbf{1}}_3)$ and $[0,k+1] \oplus I \oplus I'$, plus linearly many triangular bipyramids. 

As happened in dimension two, the computations of \[rem:M\_k-dim3\] show that $M_k(1,0)$ and $M_k(1,1)$ have covering radius strictly smaller than $1+\frac1{k+1}$, even if their volume is smaller than that of $M_k(0,0)$.

The rest of this section is devoted to prove \[conj:k\] in dimension two.  More precisely, we show:

\[thm:dim2-k\] Let $P$ be a non-hollow lattice polygon with $k \geq 2$ interior lattice points.  Then $\mu(P)\le \frac12+\frac1{k+1}$, with equality if and only if $P$ is the direct sum of two lattice segments of lengths $2$ and $k+1$.

Our proof is split up into five steps distinguishing cases with respect to the following parameters: A lattice polytope $P$ has *(lattice) width* $\omega \in \N$ if there is an affine integer projection from $P$ to the segment $[0,\omega]$ but not to $[0,\omega-1]$. Remember that the width is the reciprocal of the first covering minimum.  The numbers $m$, $m'$, and $k$ will denote the maximum number of collinear lattice points, maximum number of collinear *interior* lattice points, and the number of interior lattice points of $P$, respectively.  We proceed as follows:

-   $(\omega = 2)$ in \[lemma:width2\]

-   $(\omega \geq 3, m \geq 4)$ except for $(\omega=3, m=4, k\geq5)$ in \[lem:bigm\]

-   $(\omega=3, m=4, k\geq5)$ in \[lem:34\]

-   $(\omega \geq 3, m' \geq 3)$ in \[lem:3collinear\]

-   $(\omega \geq 3, m' \leq 2)$

It will turn out that equality in the bound of \[thm:dim2-k\] can only occur in the first case, that is, when $P$ has width two. 

\[lemma:width2\] Let $P$ be a lattice polygon with $k \geq 2$ interior lattice points.  Then, the following are equivalent:

(i) $P$ has width equal to two. 

(ii) All the interior lattice points of $P$ are collinear. 

Moreover, if this happens then $P$ satisfies \[conj:k\], with equality if and only if $P$ is the direct sum of two lattice segments of lengths $2$ and $k+1$.

The fact that width two implies that all interior lattice points are collinear is obvious.  For the converse, without loss of generality assume that the $k$ interior lattice points of $P$ are $(0,1), \dots, (0,k)$. We claim that $P\subset[-1,1]\times \R$. Suppose to the contrary that $P$ has a lattice point $(x,y)$ with $|x|\ge 2$. Then the triangle $T$ with vertices $(0,1)$, $(0,2)$ and $(x,y)$ is fully contained in $\operatorname{int}(P)$ except perhaps for the vertex $(x,y)$ which may be in the boundary of $P$. Now, since $T$ is a non-unimodular triangle it contains at least one lattice point other than its vertices.  That point is in $\operatorname{int}(P)$, which contradicts the collinearity assumption. 

This finishes the proof of the stated equivalence.  Let us now show \[conj:k\] for a lattice polygon $P$ satisfying (i) and (ii).  We keep the convention that the interior lattice points in $P$ are $(0,1), \dots, (0,k)$. Let $S$ be the segment $P\cap(\{0\}\times \R)$. We distinguish three cases, depending on whether none, one, or both of the end-points of $S$ are lattice points:

-   If exactly one is a lattice point, then $P$ contains a copy of $M_k(1)$, whose covering radius is strictly smaller than $\frac12+\frac1{k+1}$ (see \[exm:dim2-k\]). 

-   If none is a lattice point then $S=\{0\} \times [1/2, k+1/2]$. Without loss of generality we have $$P= \operatorname{conv}(\{(-1,0), (-1,a), (1,1), (1, 1+b)\}),$$ where $a$ and $b$ are nonnegative integers with $a+b=2k$. There are two possibilities: If $a=b=k$ then $P$ is a parallelogram of covering radius at most $1/2$, because $\frac12 P$ contains a fundamental domain of $\Z^2$. If $a\ne b$ then one of them, say $a$, is at least $k+1$. In this case, $P$ contains the triangle $\operatorname{conv}(\{(-1,0), (-1,a), (1,1)\})$ whose covering radius is bounded by $1/2 + 1/a \le 1/2 + 1/(k+1)$. Since triangles are tight, equality can only hold when $P$ coincides with this triangle, implying $b=0$. But in that case $a=2k$ and $1/2 + 1/a < 1/2 + 1/(k+1)$, since $k\geq2$.

-   If both end-points of $S$ are lattice points, then they are given by $(0,0)$ and $(0,k+1)$. Applying \[lem:projection\] to the projection that forgets the second coordinate gives the upper bound: the fiber $S$ has length $k+1$ and the projection has length $2$. For the case of equality, observe that if $P$ has lattice points $u\in \{-1\}\times \R$ and $v\in \{1\}\times \R$ such that the mid-point of $uv$ is integral then $P$ contains (an affine image of) the direct sum of $[-1,1]$ and a segment of length $k+1$. Since that direct sum is tight (\[lemma:sum\_monotone\]), $P$ either equals the direct sum or it has strictly smaller covering radius. 

    Thus, we can assume that $P$ does not have such points $u$ and $v$. Put differently, $P$ has a single lattice point on each side of $S$ and the height of these points have different parity.  Without loss of generality we can assume $$P= \operatorname{conv}(\{(0,0), (0,k+1), (-1,0), (1,a)\}),$$ for an odd $a \in [1, 2k+1]$. We claim that the *proof* of \[lem:projection\] implies that $\mu(P)$ is *strictly smaller* than $\lambda:=1/2 + 1/(k+1)$. Indeed, that proof is based on the fact that $\lambda P$ contains the following parallelogram $Q$, which is a fundamental domain for $\Z^2$: $$Q=\operatorname{conv}\left(\left\{
          \left(-\frac12,0\right),
          \left(-\frac12,1\right),
          \left(\frac12,\frac{a}2\right),
          \left(\frac12,1+\frac{a}2\right)
          \right\}\right).$$ But we can argue that, moreover, the vertices of $Q$ are its only points not contained in the interior of $\lambda P$, and that each of these vertices is in the interior of some lattice translation of $\lambda P$ because the vertical offset of the left and right edges of $Q$ is not an integer.  This implies $\lambda$ to be strictly larger than $\mu(P)$.

For the rest of the proof of \[thm:dim2-k\], we can now assume that the width $\omega$ of $P$ is at least three.  Let $L$ be the line containing the maximum number $m$ of collinear lattice points in $P$. We will frequently use the following upper bound, obtained from \[lem:projection\] applied to the projection along the direction of $L$: $$\begin{aligned}
\mu(P) \le \frac1\omega + \frac1{m-1}.\label{eq:m_omega}\end{aligned}$$

\[lem:bigm\] If $P$ is a non-hollow lattice polygon with $(\omega \geq 3, m \geq 4, k\geq2)$, except for $(\omega=3, m=4, k\geq5)$, then $P$ satisfies \[conj:k\] with strict inequality. 

We look separately at the possibilitites for maximum number $m$ of collinear interior lattice points of $P$:

If $m\ge 7$ then \[eq:m\_omega\] gives $$\mu(P) \le \frac1\omega + \frac1{m-1} \le \frac13+\frac16 =\frac12,$$ and there is nothing to prove. 

If $m\in \{5,6\}$ then the same argument works as long as $\omega\ge 4$. If $\omega=3$, then we have $k \le 2m$, because all interior lattice points lie in two parallel lines orthogonal to the direction in which the width is attained.  Thus, we get the following, depending on the value of $m$: $$\begin{aligned}
\mu(P) \le  \frac13 + \frac1{5} = \frac{8}{15} \quad < \quad \frac{15}{26} = \frac12 +\frac1{13} \le \frac12+\frac1{k+1}, \quad \text { if $m=6$}.\\
\mu(P) \le \frac13 + \frac1{4} = \frac{7}{12} \quad<\quad \frac{13}{22} = \frac12 +\frac1{11} \le \frac12+\frac1{k+1},  \quad \text { if $m=5$}. 
$$

So, for the rest of the proof we assume $m=4$. If $\omega\ge 6$ then \[eq:m\_omega\] again gives $\mu(P) \le \frac16 + \frac13$. Thus, assume $\omega\in \{3,4,5\}$ and suppose without loss of generality that $P\subset [0,\omega] \times \R$. The observation that $k\le 4(\omega-1)$ (because there are $\omega-1$ intermediate lines $\{i\}\times \R$, each with at most $m=4$ lattice points) discards the case $\omega=5$: $$\mu(P) \le \frac15+\frac13 = \frac8{15} \quad < \quad \frac{19}{34} \le \frac12 + \frac1{k+1} .$$

In the case $\omega=4$ we could a priori have up to $3\times 4=12$ interior lattice points.  But more than $10$ would imply at least three in each of the three lines $\{i\}\times \R$, $i=1,2,3$. This would make $P$ contain a parallelogram $Q$ with vertical edge of length two and horizontal width two.  Such a $Q$ has $\mu(Q)\le \frac12$, since $\frac12Q$ contains a fundamental domain of $\Z^2$. Thus, we can assume $k\le 10$ and we get $$\mu(P) \le \frac14+\frac13 = \frac7{12} \quad < \quad \frac12 + \frac1{11} \le \frac12 + \frac1{k+1}.$$ In the final case, $m=4$, $\omega=3$, and $k\le 4$, we get $$\mu(P) \le \frac13+\frac13 = \frac23 \quad < \quad \frac12 + \frac1{5} \le \frac12 + \frac1{k+1}.\qedhere$$

\[rem:castryck\] Lattice polytopes with $m \leq 3$ contain at most nine lattice points in total, since they cannot have two points in the same residue class modulo $(3\Z)^2$. In particular, they have $k\le 6$. On the other hand, the polytopes with $(\omega=3,m=4)$ have $k \leq 8$ because they have at most four points in each of the two intermediate lines along the direction where $\omega=3$ is attained.  Thus, the cases not covered by \[lemma:width2\] and \[lem:bigm\] have between $3$ and $8$ interior lattice points.  Castryck [@castryck2012movingout] enumerated all lattice polygons with $k\le 30$ up to unimodular equivalence, and showed that there are $120 + 211 + 403 + 714 + 1023 + 1830$ of them with $k$ equal to $3$, $4$, $5$, $6$, $7$, and $8$. The rest of the section could be replaced by a computer-aided computation of the covering radius of these $4301$ polygons. 

The missing case ($\omega=3$, $m=4$, $k\ge 5$) in \[lem:bigm\] is dealt with separately, since it needs some ad-hoc arguments. 

\[lem:34\] Suppose $P$ has width $3$ (assume it is contained in $[0,3]\times \R$), its maximum number of collinear points is $4$, and it has $k \geq 5$ interior lattice points.  Then at least one of the following conditions holds:

(i) $P$ has four collinear lattice points along one of the intermediate vertical lines $\{1\}\times \R$ or $\{2\}\times \R$ and (at least) three of them are interior to $P$,

(ii) $P$ contains a parallelogram with one vertical edge of length two and horizontal width two. 

In both cases we have $$\mu(P) < \frac12 + \frac1{k+1}.$$

We first prove the conclusion.  If $P$ contains a parallelogram $Q$ as stated in (ii) then $\mu(P) \le \mu(Q) =\frac12$ and we are done.  Suppose, then, that $P$ contains the four collinear points $(1,i)$, $i=1,2,3,4$ and that the first three are interior.  Then the segment $P\cap \{x=1\}$ has length at least $3+\frac13=\frac{10}3$, because its bottom end-point cannot be above $(1, \frac23)$. Thus $$\mu(P) \le \frac13 + \frac3{10} = \frac{19}{30} \quad < \quad \frac{9}{14} =\frac12 + \frac17 \le \frac12 +\frac1{k+1},$$ if $k \in \{5,6\}$. In the case $k \geq 7$, we can assume the four collinear lattice points $(1,i)$, $i=1,2,3,4$ are actually interior to $P$. Therefore, the segment $P\cap \{x=1\}$ has length at least $3+\frac23=\frac{11}3$, because its bottom end-point cannot be above $(1, \frac23)$ and its top end-point cannot be below $(1,4+\frac13)$. Thus $$\mu(P) \le \frac13 + \frac3{11} = \frac{20}{33} \quad < \quad \frac{11}{18} =\frac12 + \frac19 \le \frac12 +\frac1{k+1}.$$

Let us now assume that $P$ is neither in the conditions of (i) or (ii) and let us derive a contradiction.  By (the negation of) (i), $P$ has at most three interior lattice points along each of the two vertical lines.  Since it has at least five in total, we assume without loss of generality that $$(1,1), (1,2), (1,3), (2,1), (2,2) \in \operatorname{int}(P).$$ The proof is based on arguing that certain additional points must or cannot be in $P$. This is illustrated in \[fig:34\] where the points that *must* be in $P$ are drawn as black dots and the ones that *cannot* as crosses.  The initial points that we assume in $\operatorname{int}(P)$ are drawn as white dots.  The labels of the points indicate the order in which they appear in the proof:

![ Illustration of the proof of \[lem:34\].[]{data-label="fig:34"}](34.pdf)

1)  None of the points $(1,0)$, $(1,4)$, $(2,-1)$, or $(2,4)$ can be in $P$, since their presence would give condition (i). 

2)  The left end-point of the top (respectively, bottom) edge of $P$ meeting the line $\{x=1\}$ must then be of the form $(0,a)$ with $a\ge 3$ (respectively, with $a\le 2$).  Hence, $(0,2)$ and $(0,3)$ are in $P$.

3)  One of $(0,1)$ or $(0,4)$ must be in $P$, for otherwise the edges going from $(0,2)$ and $(0,3)$ to the right must go strictly below and above $(2,0)$ and $(2,3)$ respectively, giving four interior points along $\{x=2\}$. Assume without loss of generality that $(0,1) \in P$.

4)  Since we already have an intersection of length two with $\{x=0\}$, the intersection with $\{x=2\}$ must have length strictly smaller than $2$, in order for $P$ not to be in the conditions of part (ii).  Thus, $(2,0), (2,3)\not\in P$.

5)  Now the top edge of $P$ crossing $\{x=1\}$ must have its left end-point above $(0,3)$, because $(2,3) \notin P$, which implies $(0,4) \in P$. Since we already have four collinear points in $\{x=0\}$, neither $(0,0)$ nor $(0,5)$ is in $P$.

6)  Now the only possibility for the right end-points of the top and bottom edges of $P$ are $(3,0)$ and $(3,2)$ (remember that the white dots in the figure are meant to be in the interior of $P$). 

This gives a contradiction, since $P$ is now as described in part (ii). 

\[lem:3collinear\] Suppose $P$ has width at least three and three interior collinear lattice points.  Then, $P$ has four collinear lattice points. 

![ Illustration of the proof of \[lem:3collinear\].[]{data-label="fig:3collinear"}](3collinear.pdf)

Suppose $P$ contains $(1,1)$, $(1,2)$ and $(1,3)$ in its interior and moreover that $P$ does not contain four collinear lattice points.  We are going to arrive to a contradiction.  Similarly to the proof of \[lem:34\], we illustrate our reasoning in \[fig:3collinear\]:

1)  $(1,0)$ and $(1,4)$ are exterior to $P$, and the length of $P\cap\{x=1\}$ is greater than two. 

2)  Since $P$ does not have a vertex in $\{x=1\}$, one of the intersections $P\cap \{x=0\}$ or $P\cap \{x=2\}$ has at least the same length as $P\cap \{x=1\}$. Suppose it is $P\cap \{x=0\}$. If $P$ does not have a vertex in $\{x=0\}$ then it has at least three lattice points in $\{x=-1\}$ and at least one in $\{x\geq2\}$. That would make at least ten lattice points in total, which would imply $m\ge 4$ as we observed in .  So, without loss of generality we assume that the top edge crossing $\{x=1\}$ has a vertex at $(0,3)$.

3)  Then $(0,0)$ and $(0,4)$ are exterior to $P$, in order not to have four collinear points, and $(0,2)$ and $(0,1)$ are interior to $P$, since $P\cap \{x=0\}$ has length larger than two. 

4)  The edges crossing $\{x=1\}$ must cross $\{x=2\}$ above $(2,3)$ and below $(2,2)$ respectively, so these two points are also in the interior of $P$.

So, we have identified eight lattice points in $P$. But none of them can be an end-point of the bottom edge of $P$ crossing $\{x = 1\}$. Thus, $P$ has at least ten lattice points, which implies $m\ge 4$.

After Lemmas \[lemma:width2\]–\[lem:3collinear\], the only case left to consider is when $P$ has at least three interior lattice points (since otherwise it has width two), but no three of them collinear.  Moreover, we can assume $P$ does not contain four collinear points. 

Let $Q$ be the convex hull of all the interior lattice points in $P$. $Q$ has at most four lattice points, because if there were five then two of them would be in the same residue class modulo $(2\Z)^2$, giving three collinear ones.  This gives only three possibilities for $Q$: it is equivalent to either a unimodular triangle, a unit parallelogram, or $S({\mathbf{1}}_3)$.

No boundary lattice point $p$ of $P$ can be at lattice distance more than one from $Q$, because otherwise the triangle with vertices $p$ and two of the lattice points in $Q$ would contain additional lattice points, which would necessarily be in the interior of $P$. Thus, $P$ is fully contained in one of the three polygons drawn in \[fig:kpoints-final\].  In each case, let $R$ denote the polygon in the figure; we want to show that every subpolygon of $R$ containing all the white dots (the polygon $Q$) in its interior has covering radius strictly smaller than $\frac12+\frac1{k+1}$, where $k=3$ in cases (A) and (B), and $k=4$ in case (C):

![ The three cases in the proof of \[thm:dim2-k\].[]{data-label="fig:kpoints-final"}](kpoints-final)

(A) If $Q=S({\mathbf{1}}_3)$, then $R=2Q=S(2,2,2)$. The only lattice subpolygon of $R$ containing $Q$ in its interior is $R$ itself, whose covering radius is $1/2$ by \[thm:lambda\] (or by the fact that it coincides with $2S({\mathbf{1}}_3)$). 

(B) If $Q$ is a unit parallelogram, without loss of generality we assume that $Q = [1,2]^2$ and $R=[0,3]^2$. We distinguish cases:

    1)  $P$ contains at least one lattice point from the relative interior of each edge of $R$. The only possibility for $R$ not to contain four collinear points is that $P$ equals $S := \operatorname{conv}(\{(1,0), (3,1), (2,3), (0,2)\})$ (or its mirror reflection).  It is easy to calculate that $\mu(S)=\frac35 <\frac12 + \frac15$, since $Q$, which is a fundamental domain, is inscribed in the dilation of $S$ of factor $\frac35$ centered at $(\frac32,\frac32)$.

    2)  Along some edge, $P$ does not contain any relative interior point of $R$. Say $P$ contains neither $(1,0)$ nor $(2,0)$. Then, it must contain the edge from $(0,0)$ to $(3,1)$ (or its mirror reflection, which gives an analogous case).  If $P$ contains $(0,1)$ then we have four collinear points.  If it does not, then it contains the edge from $(0,0)$ to $(1,3)$. In particular, $P$ contains the triangle with vertices $(0,0)$, $(3,1)$ and $(1,3)$. This triangle is a translate of $S(1,2,2)$, hence its covering radius equals $\frac58 < \frac12+\frac15$ by \[thm:lambda\]. 

(C) If $Q$ is a unimodular triangle, then without loss of generality we can assume that $Q = \operatorname{conv}(\{(1,1), (1,2), (2,1)\})$, so that $P$ is contained in $R = \operatorname{conv}(\{(0,0), (4,0), (0,4)\})$. There are two possibilities:

    1)  $P$ contains a vertex of $R$, say $(0,0)$. It must also contain (at least) one lattice point on the opposite edge $\{x+y=4\}$. But:

        i)  If $(2,2)\in P$ then $\mu(P) \le \mu([0,2]^2)=\frac12$.

        ii) If $(4,0)$ or $(0,4)$ is in $P$ then $P$ contains five collinear points. 

        iii) If $(3,1)$ is in $P$ then $P\cap\{y=1\}$ has length at least $8/3$. for the projection along this line gives $\mu(P) \le \frac13 + \frac38= \frac{17}{24} < \frac34$. The case $(1,3)\in P$ is symmetric to this one. 

    2)  $P$ does not contain a vertex of $R$. Then, in order for $(1,1)$ to be in the interior of $P$, $P$ must contain (at least) one of the points $(1,0)$ or $(0,1)$. The same reasoning for the other two interior points gives that $P$ contains one of $(3,0)$ and $(3,1)$, and one of $(0,3)$ and $(1,3)$. Out of the eight combinations of one point from each pair the only ones that do not produce four collinear points in $P$ are the triangle $\operatorname{conv}(\{(0,1), (3,0), (1,3)\})$ and its reflection along the diagonal $\{x=y\}$. In \[lem:2triangles\] we compute the covering radius of this triangle to be $5/7$, which is smaller than $3/4$.

The 26 minimal 1-point lattice 3-polytopes {#sec:26minimal}
==========================================

The $26$ minimal non-hollow lattice $3$-polytopes with a single interior lattice point were classified by Kasprzyk [@kasprzyk2010threefolds].  We describe them in Tables \[tbl:minimal\_tetrahedra\] and \[tbl:minimal\_non-tetrahedra\], in the same order as they appear in Kasprzyk’s Tables 2 and 4.  contains the 16 that are tetrahedra and the 10 that are not.  For each of them we list its vertices as the columns of a matrix and include a description that is explained in \[sec:26bounds\].  For the tetrahedral examples in we also include the *volume vector* $(a,b,c,d)$ consisting of the normalized volumes of the pyramids from the origin over the facets.  The given descriptions allow us to bound the covering radius away from $3/2$ for each of the $17$ polytopes that are not equivalent to one in \[lemma:minimum\_3d\], thus obtaining a first proof of .  A second proof is by explicitly computing their covering radius via solving a suitable mixed-integer linear program as explained in \[sec:26computations\].  The covering radius obtained for each is also shown in the tables, and is highlighted in bold-face for the nine of , which are the ones with $\mu=3/2$.

[-.4cm]{}[-.4cm]{}

  ----------------------------------- ----------------------------------- ---------------------------- ---------------------------------
      $\left(\begin{array}{cccc}          $\left(\begin{array}{cccc}       $\left(\begin{array}{cccc}     $\left(\begin{array}{cccc}
           -1 & 1 & 0 & 0 \\                   -2 & 2 & 0 & 0 \\               -5 & 5 & 0 & 0 \\               -1 & 1 & 0 & 0 \\
           -1 & 0 & 1 & 0 \\                   -2 & 1 & 1 & 0 \\               -3 & 2 & 1 & 0 \\               -1 & 0 & 1 & 0 \\
            -1 & 0 & 0 & 1                      -1 & 0 & 0 & 1                   -2 & 1 & 0 & 1                 -2 & 0 & 0 & 1
          \end{array}\right)$                 \end{array}\right)$             \end{array}\right)$             \end{array}\right)$

              $(1,1,1,1)$                         $(2,2,2,2)$                     $(5,5,5,5)$                     $(1,1,1,2)$

    $S({\mathbf{1}}_4)=T(1,1,1,1)$         $(I \oplus I')'\oplus I$               $T(5,5,5,5)$                   $T(1,1,1,2)$

                                                                                   $\mu=9/10$                      $\mu=7/5$

      $\left(\begin{array}{cccc}          $\left(\begin{array}{cccc}       $\left(\begin{array}{cccc}     $\left(\begin{array}{cccc}
           -1 & 1 & 0 & 0 \\                   -1 & 1 & 0 & 0 \\               -1 & 1 & 0 & 0 \\               -1 & 1 & 0 & 0 \\
           -1 & 0 & 1 & 0 \\                   -2 & 0 & 1 & 0 \\               -2 & 0 & 1 & 0 \\               -2 & 0 & 1 & 0 \\
            -3 & 0 & 0 & 1                      -2 & 0 & 0 & 1                   -3 & 0 & 0 & 1                 -4 & 0 & 0 & 1
          \end{array}\right)$                 \end{array}\right)$             \end{array}\right)$             \end{array}\right)$

              $(1,1,1,3)$                         $(1,1,2,2)$                     $(1,1,2,3)$                     $(1,1,2,4)$

     $S({\mathbf{1}}_3) \oplus I'$       $S({\mathbf{1}}_3)' \oplus I$            $T(1,1,2,3)$          $(I \oplus I')^\circ \oplus I'$

                                                                                   $\mu=9/7$           

      $\left(\begin{array}{cccc}          $\left(\begin{array}{cccc}       $\left(\begin{array}{cccc}     $\left(\begin{array}{cccc}
           -1 & 1 & 0 & 0 \\                   -1 & 1 & 0 & 0 \\               -1 & 1 & 0 & 0 \\               -2 & 1 & 0 & 0 \\
           -3 & 0 & 1 & 0 \\                   -3 & 0 & 1 & 0 \\               -4 & 0 & 1 & 0 \\               -3 & 0 & 1 & 0 \\
            -4 & 0 & 0 & 1                      -5 & 0 & 0 & 1                   -6 & 0 & 0 & 1                 -5 & 0 & 0 & 1
          \end{array}\right)$                 \end{array}\right)$             \end{array}\right)$             \end{array}\right)$

              $(1,1,3,4)$                         $(1,1,3,5)$                     $(1,1,4,6)$                     $(1,2,3,5)$

   $\text{Pyr}_3(S({\mathbf{1}}_3))$           $I'\oplus M_2(1)$               $I'\oplus M_2(0)$                 $T(1,2,3,5)$

              $\mu=11/9$                          $\mu=13/10$                      $\mu=4/3$                      $\mu=12/11$

      $\left(\begin{array}{cccc}          $\left(\begin{array}{cccc}       $\left(\begin{array}{cccc}     $\left(\begin{array}{cccc}
           -3 & 1 & 0 & 0 \\                   -1 & 1 & 0 & 0 \\               -3 & 2 & 0 & 0 \\               -4 & 3 & 0 & 0 \\
           -4 & 0 & 1 & 0 \\                   -3 & 0 & 2 & 0 \\               -4 & 1 & 1 & 0 \\               -3 & 1 & 1 & 0 \\
            -5 & 0 & 0 & 1                      -4 & 0 & 1 & 1                   -5 & 1 & 0 & 1                 -5 & 2 & 0 & 1
          \end{array}\right)$                 \end{array}\right)$             \end{array}\right)$             \end{array}\right)$

              $(1,3,4,5)$                         $(2,2,3,5)$                     $(2,3,5,7) $                    $(3,4,5,7)$

             $T(1,3,4,5)$              $\text{Pyr}_4(S({\mathbf{1}}_3))$         $T(2,3,5,7) $                   $T(3,4,5,7)$

              $\mu=14/13$                          $\mu=7/6$                        $\mu=1$                       $\mu=18/19$
  ----------------------------------- ----------------------------------- ---------------------------- ---------------------------------

  : The covering radius of the minimal non-hollow tetrahedra with exactly one interior lattice point.[]{data-label="tbl:minimal_tetrahedra"}

  ------------------------------------------------ --------------------------------------
            $\left(\begin{array}{rrrrr}                 $\left(\begin{array}{rrrrr}
               1 & 0 & 0 &  0 & -1 \\                     1 & 0 & 0 & -2  & -1 \\
               0 & 1 & 0 &  0 & -1 \\                     0 & 1 & 0 & -1  &  0 \\
                0 & 0 & 1 & -1 &  0                         0 & 0 & 1 &  0  & -1
                \end{array}\right)$                         \end{array}\right)$

            $S({\mathbf{1}}_3) \oplus I$                       $I\oplus Q_4$

                                                                $\mu = 4/3$

            $\left(\begin{array}{rrrrr}                 $\left(\begin{array}{rrrrr}
               1 & 0 & -1 & 1 & -1 \\                     1 & 0 & 0 & -2  & -2 \\
               0 & 1 & -1 & 2 & -2 \\                     0 & 1 & 0 & -1  &  0 \\
                0 & 0 &  0 & 3 & -3                         0 & 0 & 1 &  0  & -1
                \end{array}\right)$                         \end{array}\right)$

    $\text{Bipyr}_3(S({\mathbf{1}}_3) \oplus I)$            $I\oplus I\oplus I'$

                   $\mu = 17/18$                   

            $\left(\begin{array}{rrrrr}                 $\left(\begin{array}{rrrrr}
               1 & 0 & 0 &  0 & -2 \\                     1 & 0 & -2 & 1  & -3 \\
               0 & 1 & 0 &  0 & -1 \\                     0 & 1 & -1 & 1  & -1 \\
                0 & 0 & 1 & -1 &  0                         0 & 0 &  0 & 2  & -2
                \end{array}\right)$                         \end{array}\right)$

           $(I \oplus I')^\circ \oplus I$           $\text{Bipyr}_2(I\oplus I\oplus I')$

                                                                 $\mu=7/8$

            $\left(\begin{array}{rrrrr}                 $\left(\begin{array}{rrrrrr}
              1 & 0 & -2 & 1  & -1 \\                   1 & 0 & 0 & -1 &  0 &  0 \\
              0 & 1 & -1 & 1  & -1 \\                    0 & 1 & 0 &  0 & -1 &  0\\
                0 & 0 &  0 & 2  & -2                      0 & 0 & 1 &  0 &  0 & -1
                \end{array}\right)$                         \end{array}\right)$

   $\text{Bipyr}_2((I \oplus I')^\circ \oplus I)$           $I\oplus I\oplus I$

                     $\mu = 1$                     

            $\left(\begin{array}{rrrrr}                 $\left(\begin{array}{rrrrrr}
               1 & 0 & 0 & -1 &  1 \\                   1 & 0 & -1 &  0 & 1 & -1 \\
               0 & 1 & 0 & -1 &  1 \\                   0 & 1 &  0 & -1 & 1 & -1 \\
                0 & 0 & 1 &  0 & -1                       0 & 0 &  0 &  0 & 2 & -2
                \end{array}\right)$                         \end{array}\right)$

              $ \text{Pyr}_3([0,1]^2)$              $\text{Bipyr}_2(I\oplus I\oplus I)$

                    $\mu = 4/3$                                 $\mu = 3/4$
  ------------------------------------------------ --------------------------------------

  : The covering radius of the minimal non-hollow non-tetrahedra with exactly one interior lattice point.[]{data-label="tbl:minimal_non-tetrahedra"}

First proof of Theorem \[thm:26minimal\]: theoretical bounds {#sec:26bounds}
------------------------------------------------------------

The $26$ polytopes of and are as follows.  In some cases the description allows us to compute the covering radius exactly, and in other cases to show that it is strictly smaller than 3/2:

-   The nine from , of covering radius $3/2$.

-   There are three more in that decompose as direct sums, namely (translations of) $I'\oplus M_2(1)$, $I'\oplus M_2(0)$, and $I\oplus Q_4$. Here $M_k(\alpha)= M_k(2,1;\alpha,0)$ is the triangle defined in and $$Q_4=
    \left(\begin{array}{rrrrr}
    2 & 1 & 0  & 0 \\
    0 & 1 &  0  & -1
    \end{array}\right).$$ For the first two the decomposition is enough to compute their covering radius, via : $$\begin{aligned}
    \mu(I'\oplus M_2(1)) &= \mu(I')+ \mu(M_2(1)) =\frac12 + \frac45 = \frac{13}{10} ,\\
    \mu(I'\oplus M_2(0)) &= \mu(I')+ \mu(M_2(0)) =\frac12 + \frac56 = \frac{4}{3}.\end{aligned}$$ For the third one we use that $Q_4$ strictly contains $S({\mathbf{1}}_3)$ and that $S({\mathbf{1}}_3)$ is tight (\[lemma:simplex\_monotone\]) to obtain: $$\mu(I\oplus Q_4) = \mu(I)+ \mu(Q_4) < \mu(I)+ \mu(S({\mathbf{1}}_3)) = \frac{3}{2}.$$

-   There are four in that are the same as the four of covering radius $3/2$ except considered with respect to a finer lattice.  Since they are also (skew) bipyramids, they are marked as $\text{Bipyr}_i($–$)$, where $i$ is the index of the superlattice.  Let $P$ be one of them.  In each case the intersection of $P$ with the plane $z=0$ is a non-hollow lattice polygon (in fact, it is one of the three of covering radius equal to one).  Applying to the projection $\pi$ onto the $z$-coordinate we get: $$\mu(P) \le \mu(P\cap\{z=0\}) + \mu(\pi(P)) \le 1 + \frac14 =\frac54,$$ since $\pi(P)$ has length at least four in all cases. 

-   The three marked as $\text{Pyr}_i(Q)$ are (skew) pyramids of height $i$ over a polygon $Q$. More precisely: $\text{Pyr}_3(S({\mathbf{1}}_3))$ and $\text{Pyr}_4(S({\mathbf{1}}_3))$ are both tetrahedra with a facet isomorphic to $S({\mathbf{1}}_3)$ in the plane $x-2y+z=2$ and the opposite vertex at distance three and four, respectively, from that facet.  $\text{Pyr}_3([0,1]^2)$ is a pyramid with base a unimodular parallelogram in the plane $x+y+z=1$ and the apex at distance three.  In the three cases, $\mu(Q)=1$ so that applied to the projection that has the base of the pyramid as fiber gives $$\mu(\text{Pyr}_i(Q)) \le \mu(Q) + \frac1i = 1 + \frac{1}i \le \frac43.$$

-   The eight described as $T(a,b,c,d)$ in are the *terminal tetrahedra*, that is, the lattice tetrahedra with only five lattice points, their four vertices plus the origin.  These have previously been classified by Kasprzyk [@Kasprzyk2006terminal] and Reznick [@Reznick2006clean Thm.  7], and appear also as the last eight rows in [@blancosantos2016lattice3 Table 1].  The parameters $a$, $b$, $c$, and $d$ are the normalized volumes of the pyramids from the origin over the facets.  One of them coincides with $S({\mathbf{1}}_4) = T(1,1,1,1)$. The rest of this section describes a way to bound their covering radius when $a+b+c+d$ is relatively big.  In we compute it exactly when it is small. 

Let $A$, $B$, $C$, $D$ be the vertices of $T(a,b,c,d)$ labeled in the natural way (so that $a$ is the determinant of $BCD$, $b$ is the determinant of $ACD$, etc.).  Since $T(a,b,c,d)$ is terminal, the triangle formed by the origin and any two vertices is unimodular, and so there is no loss of generality in taking $C$ and $D$ to be the points $(1,0,0)$ and $(0,1,0)$, respectively.  Once this is done, $A$ and $B$ must have $z$ coordinate equal to $b$ and $-a$ (or vice versa), in order for the determinants of $BCD$ and $ACD$ to be $a$ and $b$, respectively.  Then, in order for the determinants of $ABD$ and $ACD$ to be $c$ and $d$, the segment $AB$ must intersect the plane $z=0$ at $(-c/(a+b), -d/(a+b))$. That is, $T(a,b,c,d)\cap \{z=0\}$ is the triangle $\Delta_{(c/(a+b), d/(a+b))}$ of .  Then, applied to the $z$ coordinate gives: $$\mu(T(a, b,c,d)) \le \mu\left(\Delta_{\left(\frac{c}{a+b}, \frac{d}{a+b}\right)}\right) + \frac1{a+b}.$$ Now, says that whenever $c,d \ge a+b$ the first summand is $\le 1$. Thus: $$\mu(T(1,2,3,5)) \le \frac{4}{3}, \quad
\mu(T(1,3,4,5)) \le \frac{5}{4}, \quad
\mu(T(2,3,5,7)) \le \frac{6}{5}.$$ For the simplex $T(5,5,5,5)$ we can use that the triangle $\Delta_{(1/2,1/2)}$ coincides with $S(1,1,1/2)$, so gives us its exact covering radius $5/4$. Thus: $$\mu(T(5,5,5,5)) \le \frac54 + \frac1{10} < \frac32.$$ The same applies to $T(3,4,5,7)$ since $\Delta_{(5/7, 1)}$ contains the point $(1/2, 1/2)$ and hence the triangle $\Delta_{(1/2, 1/2)}$: $$\mu(T(3,4,5,7)) \le
 \mu\left(\Delta_{\left(\frac{5}{7}, 1\right)}\right) + \frac17 \le
 \mu\left(\Delta_{\left(\frac12, \frac12\right)}\right) + \frac17 = \frac54 + \frac17 <\frac32.$$ This shows the desired inequality for all the tetrahedra $T(a,b,c,d)$ except the two smallest ones, $T(1,1,1,2)$ and $T(1,1,2,3)$. For these two, \[coro:T1112\] below shows $\mu(T(1,1,1,2))=\frac75$ and $\mu(T(1,1,2,3))=\frac97$.

Computing the covering radius of a lattice simplex {#sec:graph-method}
--------------------------------------------------

Let $T=\operatorname{conv}(\{v_0,v_1,\ldots,v_d\})$ be a lattice simplex of normalized volume $V=\operatorname{Vol}_\Lambda(T)$ with respect to a certain lattice $\Lambda$. The affine map defined by $v_0 \mapsto {\mathbf{0}}$ and $v_i \mapsto V \cdot e_i$, $i=1,\dots,d$, sends $T$ to the dilated standard simplex $V \cdot\operatorname{conv}(\{{\mathbf{0}},e_1,\dots,e_d\})$ and $\Lambda$ to an intermediate lattice between $\Z^d$ and $V\Z^d$, which we still denote by $\Lambda$. Observe that $\Lambda_T:= \Lambda/ V\Z^d$ is a subgroup of $\Z^d/ V\Z^d = (\Z_V)^d$ of order $V$ and that $$\Z^d / \Lambda = (\Z_V)^d / (\Lambda/ V\Z^d)$$ is, hence, a finite abelian group of order $V^{d-1}$. The *Cayley graph* $G$ associated with the quotient group $\Z^d / \Lambda$ is the directed graph with vertex set $\Z^d / \Lambda$ and edges $(x+\Lambda,x+e_i+\Lambda)$, for $x \in \Z^d$ and $1 \leq i \leq d$. The following is a particular case of [@marklofstrom2013diameters Lem.  3 & 4] (cf.  also [@gonzalezschymura2017ondensities Thm.  4.11]):

\[lem:graph\_method\_general\] In the above conditions, let $G$ be the Cayley graph of the quotient group $\Z^d / \Lambda$ and let $\delta = \delta(G)$ be the (directed) diameter of $G$. Equivalently, $\delta$ is the maximum distance from ${\mathbf{0}}$ to any other node of $G$. Then, $$\mu(T) = \frac{\delta+d}V.$$

The covering radius of the standard $d$-simplex $\operatorname{conv}(\{{\mathbf{0}},e_1,\dots,e_d\})$ with respect to a sublattice $\Lambda$ of $\Z^d$ equals $\delta+d$. (This is the case $v=(1,\ldots,1)$ of [@gonzalezschymura2017ondensities Thm.  4.11]).  We divide this by $V$ since we are looking at the $V$th dilation of the standard simplex. 

In all cases of interest for us the group $\Lambda_T$ is cyclic; that is, there is a lattice point $p\in \Lambda$ such that $\Lambda$ equals the lattice generated by the vertices of $T$ together with $p$. We say that $T$ is a *cyclic simplex* when this happens.  In these conditions, let $\frac1V(a_0,\dots,a_d)$ be the barycentric coordinates of $p$, so that $a_0,\dots, a_d$ are integers which add up to $V$. Then, $$\Z^d / \Lambda \cong (\Z_V)^d / \langle(a_1,\dots,a_d)\rangle.$$ In particular:

\[coro:graph\_method\] Let $T$ be a cyclic simplex of normalized volume $V$ with generator $\frac1V(a_0,\dots,a_d)$ and let $G(V; a_1,\dots,a_d)$ be the Cayley graph of $\Z^d / \Lambda \cong (\Z_V)^d / \langle(a_1,\dots,a_d)\rangle$ with respect to the standard generators.  Then $$\mu(T) = \frac{\delta+d}V,$$ where $\delta$ is the diameter of $G(V; a_1,\dots,a_d)$.

Let us now look at an arbitrary lattice tetrahedron with an interior lattice point $p$ and let $a, b, c, d \in \N$ be the normalized volumes of the pyramids with apex at $p$ over the facets of $T$. When $\gcd(a,b,c,d)=1$ we have that $\Lambda_T$ is cyclic of order $V=a+b+c+d$ and with generator $\frac1V(a,b,c)$. Thus, \[coro:graph\_method\] gives an easy way to compute the covering radius of $T$. The case $a=1$ is particularly simple, since then $G(V;a,b,c)$ coincides with the Cayley graph of $(\Z_V)^2$ with respect to the generators $(1,0)$, $(0,1)$ and $(-b,-c)$. That is, $G(V; a,b,c)$ has $(\Z_V)^2$ as vertex set and from each vertex $(i,j)$ we have the following three arcs: $$(i,j) \to (i,j+1), \quad
(i,j) \to (i+1,j), \quad
(i,j) \to (i-b,j-c).$$

With this in mind, \[fig:grids\] shows the computation of $\delta(G(5;1,1,1))$ and $\delta(G(7;1,1,2))$ in the following way: a grid with $V^2$ cells represents the nodes of $G(V; 1, b,c)$ with the origin at the south-west corner.  In each cell we have written its distance from the origin.  The grid has to be regarded as a torus, so that every cell has an east, west, north and south neighbor.  Moving to the north or east increases the distance from the origin by at most one unit, and when it does not increase the corresponding wall is highlighted in bold to signify that the corresponding arc of $G(V; a,b,c)$ is not used in any shortest path from the origin.  Observe that, by commutativity, most of the arcs of the form $(i,j) \to (i-b,j-c)$ are irrelevant for the diameter: only those arriving to cells with bold south and west are needed in order to verify that the diagrams are correct.  Such cells have their distances also in bold.  For example, the cell $(V-b, V-c)$ is the one labeled $\bf 1$ and with south and west edges in bold. 

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![ Graphical computation of $\delta(G(5;1,1,1))=4$ and $\delta(G(7;1,1,2))=6$, which imply $\mu(T(1,1,1,2))=\frac75$ and $\mu(T(1,1,2,3))=\frac97$. []{data-label="fig:grids"}](G511.pdf "fig:")   ![ Graphical computation of $\delta(G(5;1,1,1))=4$ and $\delta(G(7;1,1,2))=6$, which imply $\mu(T(1,1,1,2))=\frac75$ and $\mu(T(1,1,2,3))=\frac97$. []{data-label="fig:grids"}](G712.pdf "fig:")
                                                                                            $G(5;1,1,1)$                                                                                                                                                                                      $G(7;1,1,2)$
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

\[coro:T1112\] $\mu(T(1,1,1,2))=\frac75$  and  $\mu(T(1,1,2,3))=\frac97$.

The condition $a=1$ used in the computations can be weakened to $\gcd(a,V)=1$, since in this case $G(V;a,b,c)=G(V;1,ba^{-1}, ca^{-1})$, where $a^{-1}$ denotes the inverse of $a$ modulo $V$. Although we only show the computations for $T(1,1,1,2)$  and  $T(1,1,2,3)$, fourteen of the sixteen simplices in satisfy this; all but $(I\oplus I')'\oplus I$ and $T(5,5,5,5)$.

This method can also be applied to the minimal tetrahedra $M_k(1,1)$ of \[sec:smalldim\]:

\[lem:Mk11\] For every $k\in \N$ we have $$\mu(M_k(1,1)) = 1+ \frac{1}{2k}.$$

$M_k(1,1)$ has normalized volume $4k$ and the point $p=(0,0,1)$ has barycentric coordinates $\frac1{4k}(1,1,2k-1,2k-1)$. Thus, $\mu(M_k(1,1))$ equals $(\delta +3)/4k$ where $\delta$ is the diameter of the graph $G(4k;1,2k-1,2k-1)$. This diameter equals $4k-1$, as derived from \[fig:Gk11\]. 

![ Computation of $\mu(M_k(1,1))=1+1/2k$ via $\delta(G(4k;1,2k-1,2k-1))=4k-1$. Only the distance to some cells is shown.  The ones achieving the diameter are highlighted in yellow.[]{data-label="fig:Gk11"}](Gk11.pdf)

Also, we can easily compute the covering radius of the triangle needed at the end of the proof of \[thm:dim2-k\]. 

\[lem:2triangles\] $$\mu(\operatorname{conv}(\{(0,1),(3,0),(1,3)\})) = \frac57.$$

The triangle has normalized area $7$ and the point $(1,1)$ has barycentric coordinates $\frac17(1,2,4)$. Thus, $$\begin{aligned}
\mu(\operatorname{conv}(\{(0,1),(3,0),(1,3)\})) &= \frac{\delta(G(7;1,2))+2}7 = \frac{3+2}7.\end{aligned}$$ The (easy) computation $\delta(G(7;1,2)) = 3$ is left to the reader. 

Second proof of Theorem \[thm:26minimal\]: computer calculations {#sec:26computations}
----------------------------------------------------------------

Here we describe an algorithmic computation of covering radii based on a formulation of $\mu(P)$ as the optimal value of a mixed-integer program.  This formulation is already implicit in Kannan’s paper [@kannan1992latticetranslates Sect.  5]. 

Let $P = \{x \in \R^d : a_i^\intercal x \leq b_i, 1 \leq i \leq m\}$ be a polytope with outer facet normals $a_i \in \R^d$ and right hand sides $b_i \in \R$. Without loss of generality, we assume that $b_i > 0$, that is, $P$ contains the origin in its interior.  Since $P$ is bounded, there exists a finite subset $N_P \subseteq \Z^d$ such that $\mu(P) P + N_P$ contains the unit cube $[0,1]^d$.

\[prop:MIP\] The covering radius $\mu(P)$ is equal to the optimal value of the following linear mixed-integer program: $$\begin{array}{rrcll}
\displaystyle \mathrm{maximize}  & \mu \\
\mathrm{s.t.} &  a_i^\intercal x & \geq & \mu b_i + a_i^\intercal \ell - M(1-y_i^\ell), & \forall i=1,\ldots,m, \, \forall \ell \in N_P \\
& \sum_{i=1}^{m} y_i^\ell & \geq & 1, & \forall \ell \in N_P \\
& y_i^\ell & \in & \{0,1\}, & \forall i=1,\ldots,m, \, \forall \ell \in N_P \\
& x & \in & [0,1]^d . & \\ 
\end{array}$$ The constant $M > 0$ is chosen large enough such that every non-active inequality involving $M$ is redundant. 

By the periodicity of the arrangement $\mu P + \Z^d$, we get that $$\mu(P) = \min\{\mu \geq 0 : [0,1]^d \subseteq \mu P + N_P\}.$$ Hence, the covering radius equals the minimal $\mu \geq 0$ such that for all $x \in [0,1]^d$ there exists an $\ell \in N_P$ such that $x \in \mu P + \ell$. This gives a mixed-integer program with infinitely many constraints.  In order to turn it into a finite program, we may also interpret the covering radius as the supremum among $\mu \geq 0$ such that there exists an $x \in [0,1]^d$ such that $x \notin \mu P + N_P$.

Modeling this non-containment condition can be done as follows: For a fixed $\ell \in N_P$, we have $x \notin \mu P + \ell$ if and only if there exists a defining inequality of $P$ that is violated, that is, there exists an $i \in \{1,\ldots,m\}$ such that $a_i^\intercal x > \mu b_i + a_i^\intercal \ell$. Introducing the binary variable $y_i^\ell$ for each $1 \leq i \leq m$ and each $\ell \in N_P$, and using a large enough constant $M > 0$, this is modeled by the first two lines in the program, as the condition $\sum_{i=1}^{m} y_i^\ell \geq 1$ ensures that at least one inequality is violated for $\ell$.

We can replace the supremum by a maximum and the strict inequality $a_i^\intercal x > \mu b_i + a_i^\intercal \ell$ by a non-strict one, since $P$ is compact and the covering radius is in fact an attained maximum. 

In order to make this formulation effective, we need to find a suitable finite subset $N_P \subseteq \Z^d$: A point $x \in [0,1]^d$ is contained in $z + \mu(P)P$, for some $z \in \Z^d$, if and only if $z \in [0,1]^d - \mu(P)P$. Hence, for any theoretically proven upper bound $\mu(P) \leq \mu$, we can solve the mixed-integer program in with respect to $N_P = ([0,1]^d - \mu P) \cap \Z^d$ and obtain the covering radius of $P$.

Based on these considerations, we employed the SCIP solver in exact solving mode [@exact-scip] and computed the covering radius of the $26$ minimal lattice $3$-polytopes with the results given in Tables \[tbl:minimal\_tetrahedra\] and \[tbl:minimal\_non-tetrahedra\]. 

Acknowledgements {#acknowledgements .unnumbered}
----------------

We thank Ambros Gleixner for useful discussions and guidance with the exact computer calculations presented in \[sec:26computations\], and Gabrielle Balletti for helpful indications regarding [@ballettikasprzyk2016twopoints Prop.  4.2]. 

[^1]: G. Codenotti and F. Santos were supported by the Einstein Foundation Berlin under grant EVF-2015-230.  F. Santos is also supported by project MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE).  M. Schymura was supported by the Swiss National Science Foundation (SNSF) within the project *Convexity, geometry of numbers, and the complexity of integer programming (Nr.  163071)*. 

[^2]: The notation $S({\mathbf{1}}_{d+1})$ comes from the fact that this is a particular case of the simplices $S({\omega})$, ${\omega}\in \R_{>0}^{d+1}$ introduced below.  We call $S({\mathbf{1}}_{d+1})$ the *standard terminal simplex* since *terminal* is used in the literature for lattice simplices with the origin in the interior and no lattice points other than the origin and the vertices.