1 Introduction and statement of results
1.1 The Lonely Runner Conjectures
Let
$ \left \lVert {x} \right \rVert = \min \{x - {\lfloor {x}\rfloor }, {\lceil {x}\rceil } - x\}$
denote the distance from a real number
$x \in \mathbb {R}$
to a nearest integer. Dirichlet’s approximation theorem states that for every
$t\in \mathbb {R}$
and
$n\in \mathbb {N}$
, there is some
$v\in {\left \{{1,2,\dotsc ,n}\right \}}$
such that
$ \left \lVert {vt} \right \rVert \leq \frac {1}{n+1}$
. A natural question is whether the set
${\left \{{1,2,\dotsc ,n}\right \}}$
can be replaced by any other set of n distinct natural numbers, such that we obtain a better bound than
$\frac {1}{n+1}$
. The claim that this question has a negative answer is the content of the following famous problem:
Conjecture A (Lonely Runner Conjecture)
Let
$v_1,\dotsc ,v_n$
be nonzero real numbers. Then, there is some
$t\in \mathbb {R}$
such that
$ \left \lVert {v_it} \right \rVert \geq \frac {1}{n+1}$
for every i with
$1\leq i\leq n$
.
This was initially formulated by Wills in ’68 [Reference Wills26], and then an equivalent formulation as a geometric view-obstruction problem was given by Cusick in ’73 [Reference Cusick13]. The name of the conjecture was given by Goddyn [Reference Bienia, Goddyn, Gvozdjak, Sebő and Tarsi9], who reinterpreted the problem in the following fashion: Suppose that
$n+1$
runners are running indefinitely on a circular track of length
$1$
with constant, pairwise distinct, velocities and a common starting point; then the conjecture that each runner becomes ‘lonely’ at some point in time, meaning that their distance to every other runner is at least
$\frac {1}{n+1}$
, is equivalent to Conjecture A, by letting
$v_1,\dots ,v_n$
be the velocities of the other n runners relative to the one we are looking at.
For a recent and comprehensive survey on the Lonely Runner Conjecture, we refer the reader to [Reference Perarnau and Serra22]. Following this survey and other sources on the problem, we refer to Conjecture A as ‘LRC for
$n+1$
runners’, since in Goddyn’s interpretation there is an extra runner, which can be assumed to have velocity zero with no loss of generality. LRC has been proven to hold for up to
$7$
runners [Reference Barajas and Serra4].
Weaker versions of LRC have also been considered, where
$\frac {1}{n+1}$
is replaced by a smaller fraction; the problem is trivially true if we use
$\frac {1}{2n}$
, but it is still open if
$\frac {1}{n+1}$
is replaced by
$\frac {c}{n}$
, for any
$c>\frac {1}{2}$
. The best effort in this direction is by Tao in ’18 [Reference Tao25], who showed that there is a time t such that
$$\begin{align*}\left\lVert {v_it} \right\rVert \geq\frac{1}{2n}+\frac{c\log n}{n^2(\log\log n)^2}, \;\;\;\text{ for all }i \text{ with }1\leq i\leq n, \end{align*}$$
for some explicit absolute constant
$c> 0$
.
Usually the LRC is stated for distinct velocities; this is no loss of generality, in the sense that if a counter-example to Conjecture A has a repeated velocity, then removing such a velocity provides a counter-example for smaller n. Distinctness of the velocities becomes crucial in certain variants of the conjecture, as we shall see further below. We may also assume that all velocities
$v_i$
are positive integers. This reduction appeared first in German language as a combination of the arguments in the proofs of Wills [Reference Wills26, Lemma 5] and Betke & Wills [Reference Betke and Wills8, Lemma 1)]. Alternative proofs were given in [Reference Bohman, Holzman and Kleitman10] and [Reference Henze and Malikiosis19].
Excitingly, a much stronger reduction than to integer velocities was achieved by Tao [Reference Tao25]. In order to confirm the veracity of the LRC for up to
$\leq n$
runners for a fixed integer
$n \in \mathbb {N}$
, it suffices to check finitely many velocity vectors
$(v_1,\dots ,v_n) \in \mathbb {Z}_{>0}^n$
.
Theorem 1.1 [Reference Tao25, Theorem 1.4]
There exists an absolute and explicitly computable constant
$C> 0$
, such that the following assertions are equivalent for every natural number
$n \geq 1$
:
Our first main result is an improvement of this bound from Tao’s
$n^{O(n^2)}$
to roughly
$n^{2n}$
. To state our bound, for each subset
$S \subseteq [n]:=\{1,\dots ,n\}$
let us denote
$v_S:=\gcd (v_i: i \in S)$
.
Theorem A. Suppose that LRC is true for n runners. Then, LRC is true for
$n+1$
runners with integral positive velocities
$0,v_1,\ldots ,v_n$
satisfying
$\gcd (v_1,\dotsc ,v_n)=1$
and
$$\begin{align*}\sum_{S \subseteq [n]} v_S> \binom{n+1}{2}^{n-1}. \end{align*}$$
We note that, independently of our paper, a similar result has been proved by Giri & Kravitz [Reference Giri and Kravitz16] with a bound of the order of
$O(n^{\frac {5}{2}n})$
. The condition
$\gcd (v_1,\dotsc ,v_n)=1$
in Theorem A is needed for our proof but is not relevant in practice: every minimal (with respect, e.g., to the sum of velocities) counter-example to LRC must automatically satisfy it, because simultaneously scaling a given set of velocities does not change the problem instance.
We are also interested in the shifted variant of the Lonely Runner Conjecture, which allows each runner to have an individual starting point [Reference Beck, Hoşten and Schymura5].
Conjecture B (Shifted Lonely Runner Conjecture)
Let
$v_1,\dotsc ,v_n$
be distinct nonzero real numbers. Then, for every
$s_1,\dotsc ,s_n\in \mathbb {R}$
there is some
$t\in \mathbb {R}$
such that for every i with
$1\leq i\leq n$
it holds
$ \left \lVert {v_it+s_i} \right \rVert \geq \frac {1}{n+1}$
.
This has been proved up to
$n=3$
in [Reference Cslovjecsek, Malikiosis, Naszódi and Schymura12] and again in [Reference Fan and Sun15, Section 4.2]. As happened with Conjecture A, Conjecture B has also been reduced to the case where the velocities are positive integers (see [Reference Cslovjecsek, Malikiosis, Naszódi and Schymura12, Section 4.1]). However, in this conjecture one has to insist that all velocities be distinct because otherwise n runners with the same velocity v and with equally spaced starting points (that is,
$s_i = i/n$
for each i) would provide a counter-example: at every time t there is a runner i with
$ \left \lVert {vt+i/n} \right \rVert \leq \frac {1}{2n}$
. That the bound
$\frac {1}{2n}$
is optimal for sLRC when equal velocities are allowed was proven by Schoenberg in an interpretation of the problem as billiard ball motions inside the unit cube [Reference Schoenberg23] (see [Reference Beck, Hoşten and Schymura5, Theorem 4] for an alternative proof).
In our attempt to prove a result similar to Theorem A for sLRC we encountered an obstruction in the form of a two-dimensional problem, which we dub the ‘Lonely Vector Problem’. Let
${\mathbf {P}={\left \{{\mathbf {p}_1,\dotsc ,\mathbf {p}_n}\right \}}\subseteq \mathbb {R}^2}$
be a collection of n nonzero vectors, not all parallel and no two being equal or opposite to one another. Let
$S_{\mathbf {P}}$
be the following associated multiset of cardinality
$n^2$
:
$$\begin{align*}S_{\mathbf{P}} = \mathbf{P} \cup {\left\{{\mathbf{p}_i+\mathbf{p}_j : 1\leq i<j\leq n}\right\}} \cup {\left\{{\mathbf{p}_i-\mathbf{p}_j : 1\leq i<j\leq n}\right\}}. \end{align*}$$
Definition 1.2. We say that a set
$\mathbf {P}$
as above satisfies the Lonely Vector Property (LVP) if the multiset
$S_{\mathbf {P}}$
contains a vector that is not parallel to any other vector in
$S_{\mathbf {P}}$
. We say that the Lonely Vector Property holds for a certain
$n\in \mathbb {N}$
if every such set of n rational vectors, not all parallel and no two of them equal or opposite to one another, satisfies the Lonely Vector Property.
With this language our version of Theorem A for the sLRC is as follows:
Theorem B. Suppose that sLRC is true for n runners and that the LVP holds for every natural number
$\leq n$
. Then, sLRC is true for
$n+1$
runners with integral positive distinct velocities
$0,v_1,\ldots ,v_n$
satisfying
$\gcd (v_1,\dotsc ,v_n)=1$
and
$$\begin{align*}\sum_{S \subseteq [n]} v_S> \binom{n+1}{2}^{n-1}. \end{align*}$$
Remark 1.3. Consider the set
$\mathbf {P}$
consisting of vertices of a regular m-gon centred at the origin (taking only one from each pair of opposite vertices if
$m=2n$
is even). These vectors are not all parallel and no two equal or opposite, so we can ask ourselves whether they satisfy the LVP. It turns out that they do not, unless the polygon is a triangle, square, or hexagon. The fact that these three regular polygons are precisely the ones that can be linearly transformed to have rational coordinates shows the importance of rationality in the LVP, and illustrates the difficulty of proving it; see Section 4 for details.
In Section 4, we prove the LVP for up to
$n=4$
points. With this, Theorem B implies that the sLRC holds for
$n=4$
if it holds for all integer velocities with
$v_1 + v_2 + v_3 + v_4 < 1000$
. But we also improve this bound to
$195$
(see Theorem E below).
1.2 Zonotopal restatements of LRC and sLRC
We here recall the reformulation of Conjectures A and B in terms of zonotopes, developed in [Reference Henze and Malikiosis19]. We start with the following definition:
Definition 1.4. Let
$Z = \sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]} \subseteq \mathbb {R}^{n-1}$
be a lattice zonotope in
$\mathbb {R}^{n-1}$
with n generators. If the generators
$\{\mathbf {u}_i : 1\leq i\leq n\}$
are in linear general position, that is, every
$n-1$
of them are linearly independent, we say that Z is a Lonely Runner Zonotope (LRZ).
Conjecture A’ (Equivalent to Conjecture A)
For every Lonely Runner Zonotope
$Z = \sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]}$
of dimension
$n-1$
we have
$$ \begin{align} \frac{n-1}{n+1}(Z-\mathbf{x})\cap(\mathbf{x}+\mathbb{Z}^{n-1}) \neq \varnothing, \end{align} $$
where
$\mathbf {x}=\frac {1}{2}(\mathbf {u}_1+\dotsb +\mathbf {u}_n)$
is the centre of Z.
Let us describe in short how this equivalence works. As mentioned in the previous section, there is no loss of generality in assuming that the velocities
$v_1,\dotsc ,v_n$
are integers and that
$\gcd (v_1,\dots ,v_n)=1$
. We associate with such velocities a set of vectors
$$\begin{align*}\mathbf{u}_1,\dotsc,\mathbf{u}_n\in\mathbb{Z}^{n-1},\end{align*}$$
that span
$\mathbb {Z}^{n-1}$
as a lattice and satisfy
$$ \begin{align} \begin{pmatrix} | & \ldots & |\\ \mathbf{u}_1 & \ldots & \mathbf{u}_n\\ | & \ldots & | \end{pmatrix} \begin{pmatrix} v_1\\ v_2\\ \vdots\\ v_n \end{pmatrix}=\mathbf{0}. \end{align} $$
We will denote by
$$\begin{align*}Z_{\mathbf{v}}:=\sum_{i=1}^n{\left[{\mathbf{0},\mathbf{u}_i}\right]} \subseteq \mathbb{R}^{n-1} \end{align*}$$
the lonely runner zonotope associated in this way with the velocity vector
$$\begin{align*}\mathbf{v} = (v_1,\dotsc,v_n) \in \mathbb{Z}_{>0}^n. \end{align*}$$
$Z_{\mathbf {v}}$
is unique modulo unimodular equivalence. One way to construct it is to start with
$\mathbf {u}^{\prime }_i=-v_n \mathbf {e}_i$
for
$i=1,\dots ,n-1$
and
$\mathbf {u}^{\prime }_n=(v_1,\dots ,v_{n-1})$
, and then let
$\mathbf {u}_i= T(\mathbf {u}^{\prime }_i)$
where
$T:\mathbb {R}^{n-1}\to \mathbb {R}^{n-1}$
is an arbitrary linear transformation sending a lattice basis of
$\mathbb {Z}\mathbf {u}^{\prime }_1 + \dotsc + \mathbb {Z} \mathbf {u}^{\prime }_n$
to the standard basis.
Conversely, starting with a zonotope
$Z = \sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]}$
with vectors
$\mathbf {u}_1, \dots , \mathbf {u}_n\in \mathbb {Z}^{n-1}$
in linear general position that generate the lattice
$\mathbb {Z}^{n-1}$
, let
$v_1,\dots ,v_n$
be the coefficients of the unique linear dependence among them, suitably scaled so that the
$v_i$
’s are integers and have no trivial common factor. These coefficients satisfy (1.2) and are nonzero by general position of the
$\mathbf {u}_i$
’s. In fact, they are the minors of size
$n-1$
of the matrix
$\begin {pmatrix} \mathbf {u}_1 & \ldots & \mathbf {u}_n\\ \end {pmatrix}$
; this implies that
$$ \begin{align} \operatorname{\mathrm{vol}}(Z_{\mathbf{v}}) = v_1 + \dotsc + v_n. \end{align} $$
For this reason we call
$\mathbf {v}$
the volume vector of
$Z_{\mathbf {v}}$
. See Section 2.1 for more details.
The equivalence of Conjectures A and A’ follows then from the following more precise statement:
Proposition 1.5 [Reference Henze and Malikiosis19]
For each
$\mathbf {v}=(v_1,\dots ,v_n) \in \mathbb {Z}_{> 0}^n$
with
$\gcd (v_1,\dots ,v_n)=1$
, a time t as required in Conjecture A exists for
${\mathbf {v}}$
if and only if
$Z_{\mathbf {v}}$
satisfies (1.1).
Sketch of proof.
For a given velocity vector
$\mathbf {v}$
, Conjecture A holds if and only if the line
$\mathbb {R}\mathbf {v}$
spanned by
$\mathbf {v}$
in
$\mathbb {R}^n$
intersects the lattice arrangement of cubes
$\mathbb {Z}^n+[\frac {1}{n+1},\frac {n}{n+1}]^n$
or, equivalently, if the cube
$[\frac {1}{n+1},\frac {n}{n+1}]^n$
intersects the lattice arrangement of lines
$\mathbb {Z}^n+\mathbb {R}\mathbf {v}$
. Projecting orthogonally onto
$H=\mathbf {v}^{\perp }$
, the lattice arrangement
$\mathbb {Z}^n+\mathbb {R}\mathbf {v}$
collapses into a lattice
$\Gamma $
, whereas the cube
$[\frac {1}{n+1},\frac {n}{n+1}]^n$
becomes a zonotope, generated by n vectors of H in linear general position. Then, there exists a linear isomorphism between H and
$\mathbb {R}^{n-1}$
, which transforms said zonotope to
$Z_{\mathbf {v}}$
and
$\Gamma $
to
$\mathbb {Z}^{n-1}$
. Hence, if Conjecture A holds for
$\mathbf {v}$
, then
$Z_{\mathbf {v}}$
satisfies (1.1).
It is not hard to show the converse as well. Suppose that
$Z_{\mathbf {v}}$
satisfies (1.1);
$Z_{\mathbf {v}}$
is paved by n parallelepipeds whose volumes are exactly the coordinates of
$\mathbf {v}$
. This fact implies that there is a linear isomorphism between
$\mathbb {R}^{n-1}$
and the hyperplane
$H=\mathbf {v}^{\perp }$
in
$\mathbb {R}^n$
, such that the above arguments may be reversed. See more details in [Reference Henze and Malikiosis19].
The sum
$\sum _{S \subseteq [n]} v_S$
in our Theorems A and B is nothing but the number of lattice points in the lattice zonotope
$Z_{\mathbf {v}}$
(see Corollary 2.3).Footnote 1 Hence, Theorem A is equivalent to the following:
Theorem A’. Let
$n\in \mathbb {N}$
. If Conjecture A’ holds for
$n-1$
, then no counter-example to Conjecture A’ for n can contain more than
$\binom {n+1}{2}^{n-1}$
lattice points.
Remark 1.6. Our arguments in Section 3 leading to Theorem A’ are not dependent on the precise value
$\frac {n-1}{n+1}$
in Conjecture A’. In fact,
$$ \begin{align} (1-2\eta)(Z-\mathbf{x})\cap(\mathbf{x}+\mathbb{Z}^{n-1}) \neq \varnothing \end{align} $$
holds for every Lonely Runner Zonotope
$Z = \sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]}$
of dimension
$n-1$
for some
$\eta>0$
, if and only if the version of Conjecture A for n where the bound
$\frac {1}{n+1}$
is replaced by
$\eta $
holds. Hence, assuming Conjecture A’ to hold in dimension
$n-1$
with a constant
$\frac {n-1}{n+1} + \varepsilon $
, for some small
$\varepsilon> 0$
, results in a finite checking result (depending on
$\varepsilon $
) for a weakened version of the LRC in dimension n.
We now look at the sLRC. Since it assumes different velocities, it involves the following class of zonotopes:
Definition 1.7. Let
$Z_{\mathbf {v}} \subseteq \mathbb {R}^{n-1}$
be an LRZ associated with the velocity vector
$\mathbf {v} = (v_1,\dots ,v_n) \in \mathbb {Z}_{>0}^n$
. When the entries of
$\mathbf {v} $
are pairwise distinct we say that
$Z_{\mathbf {v}}$
is a Strong Lonely Runner Zonotope (sLRZ).
Recall that the covering radius
$\mu (M)$
of a convex body
$M \subseteq \mathbb {R}^d$
, is the smallest dilation factor
$\rho>0$
, such that
$\rho M+\mathbb {Z}^d = \bigcup _{\mathbf {z} \in \mathbb {Z}^d} (\rho M + \mathbf {z})$
covers the entire space
$\mathbb {R}^d$
(see more details about it in Section 2). The reformulation of sLRC is as follows:
Conjecture B’ (Equivalent to Conjecture B)
Every Strong Lonely Runner Zonotope
$Z_{\mathbf {v}}$
of dimension
$n-1$
satisfies
$$ \begin{align} \mu(Z_{\mathbf{v}}) \leq \frac{n-1}{n+1}. \end{align} $$
Again the equivalence follows from the following more precise statement:
Proposition 1.8 [Reference Henze and Malikiosis19]
Fix
$\mathbf {v}=(v_1,\dots ,v_n) \in \mathbb {Z}_{>0}^n$
with pairwise distinct entries and
$\gcd (v_1,\dots ,v_n)=1$
. A time t as required in Conjecture B exists for every choice of
$(s_1,\dots ,s_n)$
if and only if
$\mu (Z_{\mathbf {v}}) \leq \frac {n-1}{n+1}$
.
For the sake of comparison, we note that for each LRZ
$Z \subseteq \mathbb {R}^{n-1}$
with centre
$\mathbf {x}$
, Equation (1.1) is equivalent to
$$\begin{align*}\frac{2n}{n+1}\mathbf{x} \in \frac{n-1}{n+1}Z + \mathbb{Z}^{n-1}, \end{align*}$$
while Equation (1.5) is equivalent to the obviously stronger assertion
$$\begin{align*}\mathbb{R}^{n-1} \subseteq \frac{n-1}{n+1}Z + \mathbb{Z}^{n-1}. \end{align*}$$
In view of Proposition 1.8, the following is equivalent to Theorem B.
Theorem B’. Let
$n\in \mathbb {N}$
. If Conjecture B’ holds for
$n-1$
and the LVP holds for every natural number at most n, then no counter-example to Conjecture B’ for n can contain more than
$\binom {n+1}{2}^{n-1}$
lattice points.
The reason why we need the Lonely Vector Property to prove Theorem B’ can be traced down to the fact that the projection of an sLRZ is, in general, not an sLRZ. To circumvent this we introduce the following definition.
Definition 1.9. A finite collection of lattice vectors spanning
$\mathbb {R}^d$
is called cosimple, if there is a linear dependence involving them and having coefficients that are all nonzero and with pairwise different absolute values. A lattice zonotope that is generated by a cosimple collection of vectors is called a cosimple zonotope.
In this definition, and in what follows, we switch to represent dimension by d (instead of
$n-1$
) in order to reserve n for the number of generators of our zonotopes. Since every sLRZ with n generators is a cosimple
$(n-1)$
-zonotope, the following conjecture that we introduce in this paper generalizes the sLRC:
Conjecture C. Every cosimple zonotope with generators in
$\mathbb {Z}^d$
has covering radius upper bounded by
$d/(d+2)$
.
The advantage of this generalization is that, using that every projection of a cosimple zonotope is cosimple, in this generalized setting we can prove a finite checking result that does not need the LVP. In fact, the proof of the following statement is much simpler than that of Theorems A’ and B’:
Theorem C. If Conjecture C holds in dimension
$d-1$
for all cosimple zonotopes, then no counter-example to Conjecture C in dimension d can contain more than
$\binom {d+2}{2}^d$
lattice points.
Since Conjecture C is stronger than Conjectures A’ and B’, this implies the following:
Corollary 1.10. If Conjecture C holds in dimension
$d-1$
for all cosimple zonotopes, then no counter-example to Conjectures B’ or A’ in dimension d can have more than
$\binom {d+2}{2}^d$
lattice points.
Theorems A’ (hence Theorem A), Theorem B’ (hence Theorem B), and Theorem C are proved, respectively, in Sections 3, 4 and 5, after introducing in Section 2 some concepts and results from zonotope theory and from the geometry of numbers that we need for the proofs.
In Section 4 we additionally prove the LVP for
$n\leq 4$
, and in Section 5 we give some properties of cosimple zonotopes. For instance, we show that every cosimple zonotope has lattice-width at least three and that the converse almost holds (Corollary 5.6). Here, the lattice-width of a convex body
$C \subseteq \mathbb {R}^d$
is the minimum length of a segment of the form
$f(C)$
, the minimum being taken over all integer linear functionals f, that is, linear functionals
$f : \mathbb {R}^d \to \mathbb {R}$
with
$f(\mathbb {Z}^d) \subseteq \mathbb {Z}$
(see Section 2 for more details).
Small dimension
In the final two Sections 6 and 7 we look at Conjectures B’ and C in low dimension, proving them for
$d=2$
and providing a volume bound for
$d=3$
. In fact, both results are proved for lattice zonotopes of lattice-width at least three, a setting more general than that of sLR or even cosimple zonotopes.
Theorem D (See more precise Theorem 6.3)
Every lattice
$2$
-zonotope Z of lattice-width at least three has
$\mu (Z)\le \frac 12$
, except for a certain parallelogram
$P_{2,5}$
of area
$5$
and with
$\mu (P_{2,5})=\frac 35$
.
Theorem E (See more precise Theorem 7.1)
Every lattice
$3$
-zonotope Z of lattice-width at least three and volume at least
$196$
has
$\mu (Z) < \frac 35$
, except for parallelepipeds projecting onto
$P_{2,5}$
.
In both statements the proof starts by using known bounds relating the lattice-width, volume and covering radius of convex bodies in dimensions two and three (Lemmas 2.10 and 2.11). In dimension two the general bound reduces our problem to zonotopes of lattice-width at most two or volume at most eight, which are relatively easy to classify. In dimension three the general bound easily proves Theorem E for zonotopes of lattice-width at least four (Section 7.1), but some additional work and a careful case-study are required for those of lattice-width three (Section 7.2).
We believe these low-dimensional results are interesting for several reasons:
On the one hand, even if Conjecture B’ is already known for dimension two [Reference Cslovjecsek, Malikiosis, Naszódi and Schymura12], our much more detailed Theorem D allows us to prove part (2) of the following statement in arbitrary dimension.
Theorem F. Suppose that sLRC holds for
$n-1$
. Then it also holds for velocity vectors
$(v_1,\dots ,v_n)$
with
$\gcd (v_1,\dots ,v_n)=1$
that satisfy one of the following conditions:
On the other hand, Theorem E shows that all potential counter-examples to Conjecture C for
$d=3$
, hence also those to Conjecture B for
$n=4$
, have volume at most 195:
Corollary 1.11. sLRC holds for
$n=4$
for all velocity vectors
$(v_1,v_2,v_3,v_4) \in \mathbb {Z}_{>0}^4$
satisfying
$$\begin{align*}\sum_i v_1 + v_2 + v_3 + v_4 \geq 196. \end{align*}$$
This result opens the door for a computational proof of the sLRC for five runners.
Remark 1.12. After a preprint of this manuscript appeared, such a computational proof was carried out successfully in [Reference Alcántara, Criado and Santos1], so that we now know that sLRC holds for
$n=4$
. Certifying that the covering radius of the
$2\, 133\, 561$
relevant sLR
$3$
-zonotopes is bounded by
$\frac 35$
required the authors of [Reference Alcántara, Criado and Santos1] to devise a new (and compared with [Reference Cslovjecsek, Malikiosis, Naszódi and Schymura12], more efficient) algorithm for bounding covering radii of rational polytopes in general.
As a by-product of their computations, [Reference Alcántara, Criado and Santos1] also shows that there are only three velocity vectors
$(v_1,v_2,v_3,v_4)$
that are tight for the sLRC, meaning that for them no bound larger than
$\tfrac 1{5}$
works in Conjecture B (equivalently, their associated sLR zonotopes have covering radius exactly
$\frac 35$
). These are the vectors
$(1,2,3,4)$
,
$(1,3,4,7)$
, and
$(1,3,4,6)$
. The first two were known to be tight for the original LRC (which obviously implies tightness for sLRC) but
$(1,3,4,6)$
is tight only for sLRC.
2 Preliminaries
2.1 Volume and lattice points in lattice zonotopes
We here recall some known facts about zonotopes in general and lonely runner zonotopes in particular.
Let
$Z = \sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]}\subseteq \mathbb {R}^d$
be a zonotope of dimension d with n generators. For each subset
$S\subseteq [n]$
let us denote
$Z_S:= \sum _{i\in S} {\left [{\mathbf {0},\mathbf {u}_i}\right ]}$
. If
$|S|=d$
, then
$Z_S$
is a parallelepiped of volume
$ \left \lvert {\det (\mathbf {u}_i: i \in S)} \right \rvert $
(degenerating to volume zero if
$\{\mathbf {u}_i: i \in S\}$
is linearly dependent). It is well-known (see, e.g., [Reference Shephard24, Eq. (57)]) that
$$ \begin{align} \operatorname{\mathrm{vol}}(Z) = \sum_{S \subseteq [n], |S|=d} \operatorname{\mathrm{vol}}(Z_S). \end{align} $$
Suppose now that
$\mathbf {u}_i \in \mathbb {Z}^d$
for every i. Then it still makes sense to define
$\operatorname {\mathrm {vol}}(Z_S)$
for a subset
$S \subseteq [n]$
of size other than d, as the relative
$|S|$
-dimensional volume of
$Z_S$
, normalized to the lattice
$\mathbb {Z}^d \cap (\sum _{i\in S} \mathbb {R} \mathbf {u}_i)$
. Observe that we insist on
$\operatorname {\mathrm {vol}}(Z_S)$
to denote an
$|S|$
-dimensional volume, so again
$\operatorname {\mathrm {vol}}(Z_S)=0$
if
$\{\mathbf {u}_i: i \in S\}$
is linearly dependent; for example, if
$|S|> d$
. With this convention,
$\operatorname {\mathrm {vol}}(Z_S)$
coincides with the
$\gcd $
of all the
$(|S|\times |S|)$
-minors of the
$d \times |S|$
matrix with columns
$\{\mathbf {u}_i : i \in S\}$
. It turns out that the sum of all these volumes for parallelepipeds of dimensions from 0 to d equals the number of lattice points in Z.
Theorem 2.1 (see [Reference Beck and Robins6, Corollary 9.3 & Theorem 9.9])
Let
$Z=\sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]}\subseteq \mathbb {R}^d$
be a lattice zonotope. Then
$$ \begin{align} |Z \cap \mathbb{Z}^d| &=\sum_{S \subseteq [n]} \operatorname{\mathrm{vol}}(Z_S). \end{align} $$
Comparing (2.1) and (2.2) one observes that every lattice zonotope contains more lattice points than its volume.
We now specialize to lonely runner zonotopes; that is, we assume
$d=n-1$
. Then,
$(\operatorname {\mathrm {vol}}(Z_{S}))_{|S|= n-1}$
equals the volume vector
$(v_1,\dots , v_n)$
of Z, and Equation (2.1) specializes to (1.3). The assumption
$\gcd (v_1,\dots ,v_n)=1$
is equivalent to the lattice
$\mathbb {Z}^{n-1}$
being generated by the vectors
$\mathbf {u}_1,\dotsc ,\mathbf {u}_n$
.
We can also give a zonotopal interpretation of the greatest common divisor of subsets of the velocities. As we did in the Introduction, for a subset
$S\subseteq [n]$
we denote
$v_S:= \gcd (v_i : i \in S)$
.
Lemma 2.2. Let
$(v_1,\dots ,v_n)$
with
$\gcd (v_1,\dots ,v_n)=1$
be the volume vector of an LRZ. Then, for each
$S \subseteq [n]$
, we have
$$\begin{align*}v_{ [n] \setminus S} = \operatorname{\mathrm{vol}}(Z_S). \end{align*}$$
Note the special case
$v_\emptyset = \operatorname {\mathrm {vol}}(Z_{[n]})=0$
of this equality.
Proof. One direction is easy: the volume of
$Z_S$
divides the volume of all the full-dimensional parallelepipeds of which
$Z_S$
is a face, and those are precisely the ones of volumes
$v_i$
,
$i\not \in S$
. Thus,
$\operatorname {\mathrm {vol}}(Z_S)$
divides
$v_{ [n] \setminus S} =\gcd (v_i : i \not \in S)$
.
For the other direction, suppose that we do not have equality. That is, there is a nontrivial factor
$r \geq 2$
such that
$ \gcd (v_i : i \not \in S) = r \operatorname {\mathrm {vol}}(Z_S)$
. Let
$k= |S|$
. Without loss of generality suppose that the generators of
$Z_S$
are
$\mathbf {u}_1,\dotsc ,\mathbf {u}_k$
and that they span the linear subspace of the first k coordinates (the latter is no loss of generality since it can be achieved by a unimodular transformation). That is, writing
$\mathbf {u}_i = (\mathbf {x}_i, \mathbf {y}_i)$
with
$\mathbf {x}_i\in \mathbb {Z}^k$
and
$\mathbf {y}_i \in \mathbb {Z}^{n-k}$
, the matrix of the vectors
$\mathbf {u}_i$
has the following block structure:
$$\begin{align*}\mathbf{U}:= \begin{pmatrix} | & \ldots & |\\ \mathbf{u}_1 & \ldots & \mathbf{u}_n\\ | & \ldots & | \end{pmatrix} = \begin{pmatrix} \mathbf{x}_1 \ \ldots \ \mathbf{x}_k &|& \mathbf{x}_{k+1} \ \ldots \ \mathbf{x}_n\\ \hline \mathbf{0} \ \ \ldots \ \ \mathbf{0} &|& \mathbf{y}_{k+1} \ \ldots \ \mathbf{y}_n\\ \end{pmatrix} = \begin{pmatrix} \mathbf{S} &|& \mathbf{X} \\ \hline \mathbf{0} &|& \mathbf{Y} \\ \end{pmatrix}, \end{align*}$$
where
$\mathbf {S}$
is a square
$k\times k$
matrix of determinant
$\operatorname {\mathrm {vol}}(Z_S)$
and
$\mathbf {Y}$
is an
$(n-k)\times (n-k)$
matrix whose maximal minors are all divisible by r. The contradiction is that then all the maximal minors of
$\mathbf {U}$
are divisible by r. For those obtained by removing one of the last
$n-k$
columns this is obvious (in fact, those minors are the
$v_i$
, for
$i \not \in S$
); for those obtained by removing one of the first k columns it follows by Laplace multirow expansion along the first k rows.
Corollary 2.3. Let
$Z\subseteq \mathbb {R}^{n-1}$
be an LRZ with volume vector
$(v_1,\dots ,v_n)$
and for each
$S\subseteq [n]$
let
$v_S:= \gcd (v_i \in S)$
. Then,
$$\begin{align*}|Z \cap \mathbb{Z}^{n-1}| = \sum_{S\subseteq [n]} v_S. \end{align*}$$
2.2 Concepts from the Geometry of Numbers
The geometric ideas in our proofs rest on some fundamental principles in the Geometry of Numbers describing how the volume of a convex body
$C \subseteq \mathbb {R}^d$
relates to whether C contains lattice points, that is, points from
$\mathbb {Z}^d$
, or whether it can be translated to avoid containing them. Specific variants of such principles can be conveniently formulated by three well-studied parameters that we now introduce.
The first parameter is the first successive minimum and concerns
$\mathbf {0}$
-symmetric convex bodies C, that is, those that satisfy
$C = -C$
. It is defined as
$$\begin{align*}\lambda_1(C) := \min\left\{ \lambda> 0 : \lambda C \cap \mathbb{Z}^d \neq \left\{\mathbf{0}\right\} \right\}, \end{align*}$$
and the lattice points in
$\mathbb {Z}^d \cap \lambda _1(C) C) \setminus \{\mathbf {0}\}$
are said to attain the first successive minimum of C. This parameter was introduced in the seminal works of Minkowski, whose first fundamental theorem says:
Theorem 2.4 (See [Reference Gruber17, Section 22])
Let
$C \subseteq \mathbb {R}^d$
be a
$\mathbf {0}$
-symmetric convex body. If C does not contain a nonzero point of
$\mathbb {Z}^d$
in its interior, then
$\operatorname {\mathrm {vol}}(C) \leq 2^d$
.
Equivalently, for every convex body C one has
$$\begin{align*}\lambda_1(C)^d \operatorname{\mathrm{vol}}(C) \leq 2^d. \end{align*}$$
The following related result is a version of [Reference Betke, Henk and Wills7, Theorem 2.1]. Observe that we no longer assume C to be
$\mathbf {0}$
-symmetric, but
$C-C$
always is. The parameter
$\lambda _1(C-C)^{-1}$
equals the greatest lattice length of a segment contained in C:
Lemma 2.5. Let
$C \subseteq \mathbb {R}^d$
be a convex body and
$\ell \in \mathbb {N}$
. If
$|C\cap \mathbb {Z}^d|>\ell ^d$
, then
$$\begin{align*}\lambda_1(C-C) \leq \frac{1}{\ell}. \end{align*}$$
Proof. By the pigeon-hole principle.
$|C\cap \mathbb {Z}^d|>\ell ^d$
implies that there are two distinct lattice points
$\mathbf {x},\mathbf {y}\in C\cap \mathbb {Z}^d$
in the same class modulo
$\ell \mathbb {Z}^d$
. Then,
$\frac 1\ell (\mathbf {x}-\mathbf {y}) \in \mathbb {Z}^d \cap \frac 1\ell (C-C)$
implies
$\lambda _1(C-C) \leq 1/\ell $
.
Remark 2.6. Suppose that C itself is centrally symmetric, that is,
$C - \mathbf {x} = \mathbf {x} - C$
, for some point
$\mathbf {x}$
, not necessarily the origin. Then,
$\operatorname {\mathrm {vol}}(C-C) = 2^d \operatorname {\mathrm {vol}}(C)$
, so Minkowski’s theorem (Theorem 2.4) gives
$$\begin{align*}\lambda_1(C-C) \leq 1 / \sqrt[d]{\operatorname{\mathrm{vol}}(C)}. \end{align*}$$
Since ‘number of lattice points’ can be considered a discrete analogue of ‘volume’, Lemma 2.5, restricted to centrally symmetric bodies, is a discrete version of Theorem 2.4. In fact, in the case of interest to us, C will be a lattice zonotope so, as noted right after Theorem 2.1, its number of lattice points is larger than its volume.
The second parameter important for us is the covering radius of a convex body
$C \subseteq \mathbb {R}^d$
, which appeared already in the zonotopal reformulation of the sLRC (Conjecture B’). For convenience, we define it with respect to an arbitrary lattice
$\Lambda \subseteq \mathbb {R}^d$
as
$$\begin{align*}\mu(C,\Lambda) := \min\left\{ \mu> 0 : \mu C + \Lambda = \mathbb{R}^d \right\}. \end{align*}$$
That is, the covering radius is the minimal positive dilation factor
$\mu $
such that every point in
$\mathbb {R}^d$
is contained in some lattice translation of
$\mu C$
. When
$\Lambda = \mathbb {Z}^d$
and then we write
$\mu (C)$
instead of
$\mu (C, \mathbb {Z}^d)$
for brevity.
It is easy to prove (cf. [Reference Gruber and Lekkerkerker18, Chapter 2, §13]) that
$\mu (C,\Lambda )$
coincides with the maximum dilation factor
$\rho> 0$
such that
$\rho C$
has a hollow translate, where we say that a convex body
$C'$
is hollow if its interior contains no lattice points. For example,
$\mu (C,\Lambda ) \geq 1$
is equivalent to C admitting a hollow translate.
The following result is fundamental in our proofs, since it allows us to induct on the dimension when
$\lambda _1$
is sufficiently small (which will be guaranteed by Lemma 2.5).
Proposition 2.7. Let
$C \subseteq \mathbb {R}^d$
be a convex body containing the origin, and let
$\pi : \mathbb {R}^d \to \mathbb {R}^{d-1}$
be the projection along a direction that attains the first successive minimum of
$C-C$
. Then,
$$\begin{align*}\mu(C) \leq \lambda_1(C-C) + \mu\left(\pi(C),\pi(\mathbb{Z}^d)\right). \end{align*}$$
Proof. This is a special case of [Reference Codenotti, Santos and Schymura11, Lemma 2.1], which reads as follows: Let
$\pi : \mathbb {R}^d \to \mathbb {R}^l$
be a rational linear projection, so that
$\pi (\mathbb {Z}^d)$
is a lattice. Let
$Q = C \cap \pi ^{-1}(\mathbf {0})$
and let
$L = \pi ^{-1}(\mathbf {0})$
be the linear subspace spanned by Q. Then,
$$\begin{align*}\mu(C) \leq \mu(Q,\mathbb{Z}^d \cap L) + \mu(\pi(C),\pi(\mathbb{Z}^d)). \end{align*}$$
Now, specializing the dimension to
$l = d-1$
, and the direction of the projection
$\pi $
to be along some
$\mathbf {w} \in \lambda _1(C-C)(C-C) \cap \mathbb {Z}^d \setminus \{ \mathbf {0}\}$
, we find that
$Q = [\mathbf {x},\mathbf {y}]$
, for some
$\mathbf {x},\mathbf {y} \in C$
, and
$\mathbf {w} = \lambda _1(C-C) (\mathbf {x} - \mathbf {y})$
. Since we further have
$\mathbb {Z}^d \cap \pi ^{-1}(\mathbf {0}) = \mathbb {Z} \mathbf {w}$
, this implies
$$\begin{align*}\lambda_1(C-C) = \mu\left(\lambda_1(C-C)^{-1} [\mathbf{0},\mathbf{w}],\mathbb{Z} \mathbf{w}\right) = \mu(Q,\mathbb{Z}^d \cap \pi^{-1}(\mathbf{0})), \end{align*}$$
and the statement follows.
The second bound for
$\mu $
that we need is apparently new and formulates as follows:
Proposition 2.8. Let
$C \subseteq \mathbb {R}^d$
be a convex body and let
$\pi : \mathbb {R}^d \to \mathbb {R}^{d-s}$
be a rational linear projection. Then,
$$\begin{align*}\mu(C) \leq \max\left\{\mu(\pi(C),\pi(\mathbb{Z}^d)) , \max_{\mathbf{y} \in \pi(C)}\mu(C \cap \pi^{-1}(\mathbf{y})) \right\}, \end{align*}$$
where
$\mu (C \cap \pi ^{-1}(\mathbf {y}))$
is considered with respect to the lattice
$\mathbb {Z}^d \cap \pi ^{-1}(\mathbf {0})$
translated to the affine subspace
$\pi ^{-1}(\mathbf {y})$
.
Proof. For the sake of brevity we write
$$\begin{align*}\mu_{\mathbf{y}} = \mu(C \cap \pi^{-1}(\mathbf{y})) \quad\textrm{ and }\quad \mu_\pi = \mu(\pi(C),\pi(\mathbb{Z}^d)). \end{align*}$$
Let
$L= \pi ^{-1}(\mathbf {0})$
, so that
$s=\dim L$
. After we dilate C by the factor
$\mu _\pi $
, every s-dimensional affine plane H parallel to L intersects some integer translation of
$\mu _\pi C$
. Hence, H contains an integer translation of
$ \mu _\pi C \cap \pi ^{-1}(\mathbf {y}) $
for some
$\mathbf {y} \in \pi (C)$
.
If
$\mu _\pi \geq \mu _{\mathbf {y}}$
, then, by
$\mathbb {R}^d = L + \pi (\mathbb {R}^d)$
, we get
$\mu (C) \leq \mu _\pi $
. So, now we assume that
$\mu _\pi < \mu _{\mathbf {y}}$
. The argument above implies that adding to
$\mu _\pi C$
a dilation of C by a factor
$\mu _{\mathbf {y}} - \mu _\pi $
will guarantee a complete covering of H. This implies that
$\mu (C) \leq \mu _\pi + \max _{\mathbf {y}}\{\mu _{\mathbf {y}} - \mu _\pi \} = \max _{\mathbf {y}} \mu _{\mathbf {y}}$
, finishing the proof.
Proposition 2.9. Let
$n \geq 3$
and suppose that Conjecture B’ (hence Conjecture B) holds for
$n-1$
velocities. Then, it holds for n velocities that satisfy
$\gcd (v_1,\dots , v_{n})=1$
if
$n-1$
of them have a common nontrivial factor. Equivalently, if the corresponding sLRC zonotope has a nonprimitive generator.
Proof. That a generator being not primitive is equivalent to all but one of the
$v_i$
’s having a common factor is the special case of Lemma 2.2, where the set S consists just of a single element.
So, let
$Z = \sum _{i=1}^n{\left [{\mathbf {0},\mathbf {u}_i}\right ]}\subseteq \mathbb {R}^{n-1}$
be an sLRZ and suppose that one generator is not primitive, say
$\mathbf {u}_{n}=k \mathbf {e}_d$
, for some
$k\in \mathbb {Z}_{\ge 2}$
. Let
$\pi :\mathbb {R}^{n-1}\to \mathbb {R}^{n-2}$
be the projection along
$\mathbf {u}_n$
. Then, Proposition 2.8 combined with the inductive hypothesis gives
$$\begin{align*}\mu(Z) \le \max\left\{\mu(\pi(Z)), \mu([\mathbf{0},\mathbf{u}_n]) \right\} \le \max\left\{\frac{n-2}{n}, \frac1k \right\} < \frac{n-1}{n+1}, \end{align*}$$
since
$k \geq 2$
and
$n \geq 3$
.
For our study of the low-dimensional cases of Conjecture C in Sections 6 and 7, we need some results relating
$\mu (C)$
with a third parameter, the lattice-width of a convex body C, defined as follows. For each
$\mathbf {z} \in \mathbb {R}^d$
define
$$\begin{align*}w(C, \mathbf{z}) = \max_{\mathbf{x} \in C} {\mathbf{z}}^\intercal \mathbf{x} - \min_{\mathbf{x} \in C} {\mathbf{z}}^\intercal \mathbf{x}, \end{align*}$$
and
$$\begin{align*}w(C) = \min_{\mathbf{z} \in \mathbb{Z}^d \setminus \{\mathbf{0}\}} w(C, \mathbf{z}). \end{align*}$$
That is,
$w(C)$
is the minimal width of C in a lattice direction, where width in each direction
$\mathbf {z} \in \mathbb {Z}^d$
is normalized to the distance between lattice hyperplanes orthogonal to
$\mathbf {z}$
. An observation that we frequently use below is that if C is a lattice polytope, that is, C is the convex hull of finitely many points of
$\mathbb {Z}^d$
, then the lattice-width
$w(C)$
is an integer.
The following results bound the volume of wide hollow bodies. Equivalently, they bound the volume of an arbitrary convex body C in terms of the product
$w(C)\mu (C)$
(see Corollary 6.1 for the latter perspective). The versions we need, for dimensions two and three, are due to Averkov & Wagner [Reference Averkov and Wagner3] and to Iglesias & Santos [Reference Iglesias-Valiño and Santos20], respectively.
Lemma 2.10 [Reference Averkov and Wagner3, Theorem 2.2]
Let
$w> 1$
and let
$C \subseteq \mathbb {R}^2$
be a hollow convex body of lattice-width at least w. Then,
$\operatorname {\mathrm {vol}}(C) \le \frac {w^2}{2(w-1)}$
.
Lemma 2.11 [Reference Iglesias-Valiño and Santos20, Theorem 2.1]
Let
$C \subseteq \mathbb {R}^3$
be a hollow convex body of lattice-width
$w\ge 2+2/\sqrt 3$
. Then,
$\operatorname {\mathrm {vol}}(C) $
is bounded from above by
$$ \begin{align*} &\frac{8w^3}{(w-1)^3}, && \text{ if } w\ge \frac2{\sqrt3}(\sqrt{5}-1) + 1 \approx 2.427, \text{ and}\\ &\frac{3w^3}{4(w - (1+2/\sqrt3))}, && \text{ otherwise}. \end{align*} $$
3 Projections of Lonely Runner Zonotopes, and a finite checking result for LRC
In this section, we prove Theorem A’ (and thus Theorem A). First, we prove an independent result that will allow us to apply induction on the dimension.
3.1 Projections of Lonely Runner Zonotopes
Let
$Z_{\mathbf {v}}\subseteq \mathbb {R}^{n-1}$
be an LRZ, with generators
$\mathbf {u}_1, \dots , \mathbf {u}_n$
and centre
$\mathbf {x}_{\mathbf {v}}:=\frac {1}{2}\sum _{i=1}^n\mathbf {u}_i$
. Consider a linear projection
$$ \begin{align*} T: \ \mathbb{R}^{n-1} &\to \mathbb{R}^{n-2} \\ \mathbf{u}_i &\mapsto \mathbf{y}_i \end{align*} $$
satisfying
$T(\mathbb {Z}^{n-1}) = \mathbb {Z}^{n-2}$
. Let
$Z=T(Z_{\mathbf {v}})$
, which is itself a lattice zonotope,
$$\begin{align*}Z = \sum_{i=1}^n{\left[{\mathbf{0},\mathbf{y}_i}\right]}, \end{align*}$$
with its centre given by
$\mathbf {y}_{\mathbf {v}}:=T(\mathbf {x}_{\mathbf {v}}) = \frac 12\left (\mathbf {y}_1 + \dotsc + \mathbf {y}_n\right )$
.
What we want to show is that
Theorem 3.1. The zonotope Z contains a lattice translation of a lonely runner zonotope
$Z' \subseteq \mathbb {R}^{n-2}$
with centre
$\mathbf {z}\equiv \mathbf {y}_{\mathbf {v}}\bmod \mathbb {Z}^{n-2}$
.
For the proof, let
$\mathbf {w}$
be a primitive vector in the kernel of T, which means that its coordinates have no nontrivial common factor. We need to know how the volumes of parallelepipeds spanned by
$n-2$
vectors among
$\mathbf {y}_1,\dotsc ,\mathbf {y}_n$
compare to those spanned by
$n-2$
vectors among
$\mathbf {w},\mathbf {u}_1,\dotsc ,\mathbf {u}_n$
. To this end, let
$\mathbf {u}_1',\dotsc ,\mathbf {u}_{n}'$
denote a relabelling of the n vectors
$\mathbf {u}_1,\dotsc ,\mathbf {u}_n$
and let
$\mathbf {y}_1',\dotsc ,\mathbf {y}_{n}'$
be the corresponding relabelling of
$\mathbf {y}_1,\dotsc ,\mathbf {y}_n$
.
Lemma 3.2.
$$ \begin{align} \operatorname{\mathrm{vol}}{\left({[\mathbf{0},\mathbf{w}]+\sum_{i=1}^{n-2}[\mathbf{0},\mathbf{u}^{\prime}_i]}\right)} &= \left\lvert {\det(\mathbf{w},\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{n-2})} \right\rvert = \left\lvert {\det(\mathbf{y}^{\prime}_1,\dotsc,\mathbf{y}^{\prime}_{n-2})} \right\rvert. \end{align} $$
Proof. By a unimodular transformation sending the primitive vector
$\mathbf {w}$
to the last coordinate vector
$\mathbf {e}_{n-1}$
, there is no loss of generality in assuming the
$\mathbf {w} = \mathbf {e}_{n-1}$
. In this case the equality of the determinants is clear.
Since Z is a zonotope with n generators
$\mathbf {y}_1,\dotsc ,\mathbf {y}_{n}$
and dimension
$n-2$
, there are the following
$n^2$
natural choices of zonotopes
$Z'$
in Theorem 3.1. First, we consider the n zonotopes generated by all but one of the generators of Z. That is, taking
$Z'$
to be
$$ \begin{align} \mathbf{y}^{\prime}_n + \sum_{i=1}^{n-1}[\mathbf{0},\mathbf{y}^{\prime}_i]. \end{align} $$
The other
$n(n-1)$
options for
$Z'$
correspond to combining two of the generators of Z into a single one, and taking the rest of the generators individually, that is, taking
$Z'$
to be of the form
$$ \begin{align} \sum_{i=1}^{n-2}[\mathbf{0},\mathbf{y}^{\prime}_i]+[\mathbf{0},\mathbf{y}^{\prime}_{n-1}+\mathbf{y}^{\prime}_n] \end{align} $$
or
$$ \begin{align} \mathbf{y}^{\prime}_n+\sum_{i=1}^{n-2}[\mathbf{0},\mathbf{y}^{\prime}_i]+[\mathbf{0},\mathbf{y}^{\prime}_{n-1}-\mathbf{y}^{\prime}_n]. \end{align} $$
Each of these
$n^2$
zonotopes has
$n-1$
generators and is contained in Z. The only missing property in order for one of them to be an LRZ (respectively, an sLRZ, which we need in Section 4) is that the corresponding volume vector contains no zero entry (respectively, contains no zero entry and no two equal or opposite entries).
Some zonotope of type (3.2) is an LRZ if and only if the volumes of the parallelepipeds spanned by
$\mathbf {w}$
and some
$n-2$
vectors among the
$\mathbf {u}^{\prime }_i$
are nonzero; if, in addition, such volumes are all distinct, then it is even an sLRZ. From now on, we will express
$\mathbf {w} \in \mathbb {Z}^{n-1}$
in terms of the
$\mathbf {u}_i$
, namely,
$$ \begin{align} \mathbf{w}=\sum_{i=1}^n\rho_i\mathbf{u}_i, \end{align} $$
where
$\rho _i\in \mathbb {Q}$
,
$1\leq i\leq n$
. Observe that the vector
$(\rho _1,\dots ,\rho _n)$
is not unique, but any choice will work in what follows. Below, the numbers
$\rho _i'$
and
$v_j'$
correspond to the induced relabelling of the coefficients
$\rho _i$
in (3.5) and the velocities
$v_j$
in (1.2).
Proposition 3.3. Suppose
$P=\sum _{i=1}^{n-1}[\mathbf {0},\mathbf {u}^{\prime }_i]$
, that is, P is the parallelepiped whose projection is (3.2) (translated by a lattice vector). Then, the volume of the parallelepiped spanned by
$\mathbf {w}$
and all the vectors
$\mathbf {u}^{\prime }_i$
except from
$\mathbf {u}^{\prime }_j$
equals the absolute value of
$$ \begin{align*} {\begin{vmatrix} \rho^{\prime}_j & \rho^{\prime}_n\\ v^{\prime}_j & v^{\prime}_n \end{vmatrix}}, \;\;\; 1\leq j\leq n-1. \end{align*} $$
Proof. Using (1.2) and (3.5), the volume spanned by
$\mathbf {w}$
and all
$\mathbf {u}^{\prime }_i$
except from
$\mathbf {u}^{\prime }_j$
, is
$$ \begin{align*} & \left\lvert {\det(\mathbf{w},\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_{n-1})} \right\rvert \\ &\hspace{1cm}= \left\lvert {\det(\mathbf{w}-\tfrac{\rho^{\prime}_n}{v^{\prime}_n}\sum_{i=1}^nv^{\prime}_i\mathbf{u}^{\prime}_i,\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_{n-1})} \right\rvert \\ &\hspace{1cm}= \left\lvert {\det((\rho^{\prime}_j-\tfrac{\rho^{\prime}_n}{v^{\prime}_n}v^{\prime}_j)\mathbf{u}^{\prime}_j,\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_{n-1})} \right\rvert \\ &\hspace{1cm}= \left\lvert {\rho^{\prime}_jv^{\prime}_n-\rho^{\prime}_nv^{\prime}_j} \right\rvert , \end{align*} $$
as claimed.
Proposition 3.4. Suppose
$P=\sum _{i=1}^{n-2}[\mathbf {0},\mathbf {u}^{\prime }_i]+[\mathbf {0},\mathbf {u}^{\prime }_{n-1}\pm \mathbf {u}^{\prime }_n]$
, that is, P is the parallelepiped whose projection is (3.3) or (3.4) (translated by a lattice vector). Then, the volume of the parallelepiped spanned by
$\mathbf {w}$
and
$n-2$
vectors among the generators of P equals the absolute value of
$$ \begin{align*} {\begin{vmatrix} \rho^{\prime}_j & \rho^{\prime}_{n-1}\mp\rho^{\prime}_n\\ v^{\prime}_j & v^{\prime}_{n-1}\mp v^{\prime}_n \end{vmatrix}}, \;\;\; 1\leq j\leq n-1. \end{align*} $$
Proof. Using (1.2) and (3.5), the volume spanned by
$\mathbf {w}$
and all generators except from
$\mathbf {u}^{\prime }_j$
,
$1\leq j\leq n-2$
, is given by
$$ \begin{align*} & \left\lvert {\det(\mathbf{w},\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_{n-2},\mathbf{u}^{\prime}_{n-1}\pm\mathbf{u}^{\prime}_n)} \right\rvert \\& \quad = \left\lvert {\det(\mathbf{w}-\tfrac{\rho^{\prime}_j}{v^{\prime}_j}\sum_{i=1}^nv^{\prime}_i\mathbf{u}^{\prime}_i,\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_{n-2},\mathbf{u}^{\prime}_{n-1}\pm\mathbf{u}^{\prime}_n)} \right\rvert \\& \quad = \left\lvert {\det((\rho^{\prime}_{n-1}-\tfrac{\rho^{\prime}_j}{v^{\prime}_j}v^{\prime}_{n-1})\mathbf{u}^{\prime}_{n-1}+(\rho^{\prime}_n-\tfrac{\rho^{\prime}_j}{v^{\prime}_j}v^{\prime}_n)\mathbf{u}^{\prime}_n,\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_{n-2},\mathbf{u}^{\prime}_{n-1}\pm\mathbf{u}^{\prime}_n)} \right\rvert \\& \quad = \left\lvert {\begin{vmatrix} \rho^{\prime}_{n-1}-\tfrac{\rho^{\prime}_j}{v^{\prime}_j}v^{\prime}_{n-1} & 1\\ \rho^{\prime}_n-\tfrac{\rho^{\prime}_j}{v^{\prime}_j}v^{\prime}_n & \pm 1\\ \end{vmatrix} \det(\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{j-1},\mathbf{u}^{\prime}_{j+1},\dotsc,\mathbf{u}^{\prime}_n) } \right\rvert \\& \quad = \left\lvert {\begin{vmatrix} \rho^{\prime}_{n-1}v^{\prime}_j-{\rho^{\prime}_j}{}v^{\prime}_{n-1} & 1\\ \rho^{\prime}_nv^{\prime}_j-{\rho^{\prime}_j}{}v^{\prime}_n & \pm 1\\ \end{vmatrix} } \right\rvert \\& \quad = \left\lvert {\begin{vmatrix} \rho^{\prime}_j & \rho^{\prime}_{n-1}\mp\rho^{\prime}_n\\ v^{\prime}_j & v^{\prime}_{n-1}\mp v^{\prime}_n \end{vmatrix} } \right\rvert. \end{align*} $$
The volume spanned by
$\mathbf {w}$
and
$\mathbf {u}^{\prime }_1,\dotsc ,\mathbf {u}^{\prime }_{n-2}$
is, by Proposition 3.3,
$$ \begin{align*} \left\lvert {\det(\mathbf{w},\mathbf{u}^{\prime}_1,\dotsc,\mathbf{u}^{\prime}_{n-2})} \right\rvert &= \left\lvert {\begin{vmatrix} \rho^{\prime}_{n-1} & \rho^{\prime}_n\\ v^{\prime}_{n-1} & v^{\prime}_n \end{vmatrix}} \right\rvert = \left\lvert {\begin{vmatrix} \rho^{\prime}_{n-1} & \rho^{\prime}_{n-1}\mp\rho^{\prime}_n\\ v^{\prime}_{n-1} & v^{\prime}_{n-1}\mp v^{\prime}_n \end{vmatrix}} \right\rvert.\\[-49pt] \end{align*} $$
Remark 3.5. Calling
$\mathbf {p}_i =(\rho _i, v_i)$
and
$\mathbf {e}_1=(1,0)$
we have that the configurations
$$\begin{align*}\{\mathbf{u}_1, \dots, \mathbf{u}_n, \mathbf{w}\} \subseteq \mathbb{R}^{n-1} \qquad{ \text{and} }\qquad \{\mathbf{p}_1, \dots, \mathbf{p}_n, -\mathbf{e}_1\} \subseteq \mathbb{R}^{2} \end{align*}$$
are Gale dual to one another. Indeed, as explained in Remark 5.4, this amounts to saying that the row-spaces of
$ \begin {pmatrix} \mathbf {u}_1 &\dots & \mathbf {u}_n & \mathbf {w} \end {pmatrix} $
and
$ \begin {pmatrix} \rho _1 &\dots & \rho _n & - 1\\ v_1 &\dots & v_n & 0\\ \end {pmatrix} $
are orthogonal complements of one another. That they are orthogonal follows from Eqs. (1.2) and (3.5), and complementarity from adding up the ranks of the matrices,
$n-1$
and
$2$
respectively.
Now, Gale duality implies that each maximal minor in one of the matrices equals the complementary minor in the other (modulo a multiplicative constant, the same for all minors, and a sign depending on the indices of columns used in each minor). This provides an alternative proof of Proposition 3.3: the minor obtained in the first matrix forgetting
$\mathbf {u}_i$
and
$\mathbf {u}_j$
equals (modulo sign; the constant happens to be
$\pm 1$
for our particular ‘choice of Gale transform’) the determinant of
$\mathbf {p}_i$
and
$\mathbf {p}_j$
.
Proof of Theorem 3.1
It suffices to show that a zonotope of type (3.3) or (3.4) is a lonely runner zonotope. The centre
$\mathbf {z}$
of such a zonotope obviously satisfies the desired condition. Consider now the vectors
$\mathbf {p}_i=(\rho _i,v_i)\in \mathbb {Q}\times \mathbb {Z}$
,
$1\leq i\leq n$
. By Proposition 3.4 and Eq. (3.1), it suffices to show that there are two of them, say
$\mathbf {p}_i$
and
$\mathbf {p}_j$
, such that
$\mathbf {p}_i\pm \mathbf {p}_j$
, with an appropriate choice of sign, is not parallel to any vector
$\mathbf {p}_k$
,
$1\leq k\leq n$
.
Without loss of generality, assume that
$$\begin{align*}\frac{\rho_{n-1}}{v_{n-1}}=\max{\left\{{\frac{\rho_i}{v_i}:1\leq i\leq n}\right\}} \quad\textrm{ and }\quad \frac{\rho_n}{v_n}=\min{\left\{{\frac{\rho_i}{v_i}:1\leq i\leq n}\right\}}. \end{align*}$$
We note that not all
$\mathbf {p}_k$
are parallel, otherwise
$\mathbf {w}$
would be the zero vector. Hence, the inequality
$\frac {\rho _{n-1}}{v_{n-1}}> \frac {\rho _n}{v_n}$
is indeed strict.
If
$v_{n-1}=v_n$
, then
$\mathbf {p}_{n-1}-\mathbf {p}_n=(\rho _{n-1}-\rho _n,0)$
is obviously not parallel to any of the
$\mathbf {p}_i$
, as their y-coordinates are nonzero. If
$v_{n-1}>v_n$
, then
$\mathbf {p}_{n-1}-\mathbf {p}_n$
is on the upper half plane, as all
$\mathbf {p}_i$
are, and it holds
$$\begin{align*}\frac{\rho_{n-1}-\rho_n}{v_{n-1}-v_n}>\frac{\rho_{n-1}}{v_{n-1}}, \end{align*}$$
whence by definition of
$\mathbf {p}_{n-1}$
it follows that
$\mathbf {p}_{n-1}-\mathbf {p}_n$
is not parallel to any
$\mathbf {p}_k$
,
$1\leq k\leq n$
. A similar argument with
$\mathbf {p}_n - \mathbf {p}_{n-1}$
applies if
$v_{n-1}<v_n$
.
3.2 Proof of Theorem A’
To have a more symmetric description, from a given LRZ
$Z_{\mathbf {v}} \subseteq \mathbb {R}^{n-1}$
with centre
$\mathbf {x}_{\mathbf {v}}$
, we define the
$\mathbf {0}$
-symmetric scaled-down zonotope
$$\begin{align*}K_{\mathbf{v}}=\frac{n-1}{n+1}(Z_{\mathbf{v}}-\mathbf{x}_{\mathbf{v}}). \end{align*}$$
Conjecture A’ is then equivalent to the statement that
$$ \begin{align} K_{\mathbf{v}}\cap(\mathbf{x}_{\mathbf{v}}+\mathbb{Z}^{n-1})\neq\varnothing. \end{align} $$
Observe that, by Lemma 2.5 plus the hypothesis that
$Z_{\mathbf {v}}$
has more than
$\binom {n+1}{2}^{n-1}$
lattice points, we have that
$$ \begin{align} \lambda_1(K_{\mathbf{v}}) = 2 \lambda_1(K_{\mathbf{v}}-K_{\mathbf{v}}) = \frac{2(n+1)}{n-1} \lambda_1(Z_{\mathbf{v}}-Z_{\mathbf{v}}) \le \frac{4}{(n-1)n}. \end{align} $$
Now, let
$\mathbf {w}\in \mathbb {Z}^{n-1}$
be a vector attaining the first successive minimum of
$K_{\mathbf {v}}$
, that is,
$$\begin{align*}\mathbf{w}\in \lambda_1(K_{\mathbf{v}})K_{\mathbf{v}}\cap(\mathbb{Z}^{n-1}\setminus{\left\{{\mathbf{0}}\right\}}). \end{align*}$$
The vector
$\mathbf {w}$
is necessarily primitive; hence, if we consider a projection
$T:\mathbb {R}^{n-1} \to \mathbb {R}^{n-2}$
with
$T(\mathbb {Z}^{n-1}) = \mathbb {Z}^{n-2}$
and with
$T(\mathbf {w})=\mathbf {0}$
, Theorem 3.1 tells us that the image
$Z=T(Z_{\mathbf {v}})$
contains an LRZ with the same centre as Z.
We keep the notation
$\mathbf {y}_i:=T(\mathbf {u}_i)$
, so that
$$\begin{align*}Z = \sum_{i=1}^n{\left[{\mathbf{0},\mathbf{y}_i}\right]} \end{align*}$$
and the centre of Z is given by
$\mathbf {y}_{\mathbf {v}}:=T(\mathbf {x}_{\mathbf {v}}) = \frac 12\left (\mathbf {y}_1 + \dotsc + \mathbf {y}_n\right )$
. Then, the assumption that Conjecture A’ holds in dimension
$n-2$
and that Z contains an LRZ imply that
$$\begin{align*}\frac{n-2}{n}(Z-\mathbf{y}_{\mathbf{v}})\cap(\mathbf{y}_{\mathbf{v}}+\mathbb{Z}^{n-2})\neq \varnothing. \end{align*}$$
Let
$\mathbf {b}$
be a vector in the above intersection, and let
$\mathbf {a}\in \frac {n-2}{n}(Z_{\mathbf {v}}-\mathbf {x}_{\mathbf {v}})$
be such that
$T(\mathbf {a})=\mathbf {b}$
. Since
$\mathbf {b} - \mathbf {y}_{\mathbf {v}} \in \mathbb {Z}^{n-2} =T(\mathbb {Z}^{n-1})$
, we have that
$\mathbf {a} - \mathbf {x}_{\mathbf {v}} \in T^{-1}(\mathbb {Z}^{n-2})$
. That, is, the line
$\mathbf {a} + \mathbb {R} \mathbf {w}=T^{-1}(\mathbf {b})$
contains infinitely many points of
$\mathbf {x}_{\mathbf {v}}+\mathbb {Z}^{n-1}$
, forming an affine one-dimensional lattice. Every segment between two consecutive lattice points on this line has lattice length equal to
$1$
. Hence, in order to ensure that the intersection
$K_{\mathbf {v}}\cap (\mathbf {x}_{\mathbf {v}}+\mathbb {Z}^{n-1})$
is nonempty, it suffices to show:
Lemma 3.6. The lattice length of the segment
$K_{\mathbf {v}}\cap (\mathbf {a}+\mathbb {R}\mathbf {w})$
is at least
$1$
.
Proof. We abbreviate
$\lambda _1(K_{\mathbf {v}})$
as
$\lambda _1$
. If
$\mathbf {a}\in \mathbb {R}\mathbf {w}$
, then
$K_{\mathbf {v}}\cap (\mathbf {a}+\mathbb {R}\mathbf {w}) = K_{\mathbf {v}}\cap \mathbb {R}\mathbf {w}$
, which has lattice length
$2/\lambda _1$
. Equation (3.7) shows that this is at least
$n(n-1)/2 \ge 1$
, since
$n\ge 2$
.
If, on the contrary,
$\mathbf {a}\notin \mathbb {R}\mathbf {w}$
, then
$\mathbf {w}$
and
$\mathbf {a}$
generate a two-dimensional linear subspace. Consider the point
$$\begin{align*}\mathbf{a}':=\frac{(n-1)n}{(n-2)(n+1)}\mathbf{a}\in\frac{n-1}{n+1}(Z_{\mathbf{v}}-\mathbf{x}_{\mathbf{v}})=K_{\mathbf{v}}. \end{align*}$$
The triangle S with vertices
$\mathbf {a}'$
,
$\frac {1}{\lambda _1}\mathbf {w}$
, and
$-\frac {1}{\lambda _1}\mathbf {w}$
is contained in
$K_{\mathbf {v}}$
, so we have
$$\begin{align*}\ell(K_{\mathbf{v}}\cap(\mathbf{a}+\mathbb{R}\mathbf{w}))\geq \ell(S\cap(\mathbf{a}+\mathbb{R}\mathbf{w})).\end{align*}$$
Now,
$$\begin{align*}{\left({\frac{(n-2)(n+1)}{(n-1)n}}\right)} + {\left({\frac{2}{(n-1)n}}\right)}= 1, \end{align*}$$
and
$$\begin{align*}{\left({\frac{(n-2)(n+1)}{(n-1)n}}\right)} \mathbf{a}' \pm {\left({\frac{2}{(n-1)n}}\right)} \frac{1}{\lambda_1}\mathbf{w}= \mathbf{a} \pm \frac{2}{(n-1)n\lambda_1}\mathbf{w}, \end{align*}$$
imply that this intersection
$S\cap (\mathbf {a}+\mathbb {R}\mathbf {w})$
is precisely the segment
$$\begin{align*}{\left[{\mathbf{a}-\frac{2}{(n-1)n\lambda_1}\mathbf{w},\mathbf{a}+\frac{2}{(n-1)n\lambda_1}\mathbf{w}}\right]},\end{align*}$$
whose lattice length is precisely
$$\begin{align*}\frac{4}{(n-1)n\lambda_1}.\end{align*}$$
This is at least
$1$
by Eq. (3.7).
4 The Lonely Vector Problem, and a finite checking result for sLRC
4.1 Proof of Theorem B’
In this section, we prove Theorem B’ (and thus Theorem B). We keep the notation from the previous section and, in particular, we consider the set of vectors
$$\begin{align*}\mathbf{P}={\left\{{\mathbf{p}_i=(\rho_i,v_i):1\le i\le n}\right\}} \subseteq \mathbb{Q}\times\mathbb{Z} \end{align*}$$
from the proof of Theorem 3.1. They are not all parallel to each other since that would imply the vectors
$(v_1,\dots ,v_n)$
and
$(\rho _1,\dotsc ,\rho _n)$
to be parallel, which cannot happen because
$$\begin{align*}\sum_{i=1}^n v_i \mathbf{u}_i = \mathbf{0}, \qquad \sum_{i=1}^n\rho_i \mathbf{u}_i = \mathbf{w} \ne \mathbf{0}. \end{align*}$$
Since we deal with Conjecture B, or its equivalent geometric formulation, Conjecture B’, we may further assume that the
$v_i$
are positive and pairwise distinct. In particular, no two vectors from
$\mathbf {P}$
are equal or opposite.
Our goal is to prove that the zonotope
$Z_{\mathbf {v}}$
contains an sLRZ of type (3.2), (3.3) or (3.4), but we are only able to do this assuming that
$\mathbf {P}$
has the Lonely Vector Property (LVP) introduced in Definition 1.2.
Proposition 4.1. Suppose that
-
1.
$Z=\sum _{i=1}^n[\mathbf {0},\mathbf {u}_i]\subseteq \mathbb {R}^{n-1}$
is an sLRZ, and that -
2. the set of vectors
$\mathbf {P}={\left \{{\mathbf {p}_i=(\rho _i,v_i):1\le i\le n}\right \}}$
satisfies the Lonely Vector Property, where
$(v_1,\dots ,v_n)$
is the volume vector of Z and
$\mathbf {w}=\sum _{i=1}^n\rho _i\mathbf {u}_i\in \mathbb {Z}^{n-1}$
is a lattice vector attaining the first successive minimum of
$Z-Z$
.
Then,
$T(Z)$
contains an sLRZ of type (3.2), (3.3) or (3.4).
Proof. We distinguish two cases: assume first that one of the vectors, without loss of generality
$\mathbf {p}_n$
, is not parallel to any nonzero vector of the form
$\mathbf {p}_k\pm \mathbf {p}_\ell $
, where
$(k,\ell )\neq (n,n)$
. Then, the zonotope
$$\begin{align*}Z'=\sum_{i=1}^{n-1}[\mathbf{0},\mathbf{y}_i],\end{align*}$$
where
$T(\mathbf {u}_i)=\mathbf {y}_i$
is an sLRZ. Indeed, if two volumes of parallelepipeds of
$Z'$
were equal, then by Lemma 3.2 and Proposition 3.3 we would have
$$\begin{align*}\begin{vmatrix} \rho_i & \rho_n\\ v_i & v_n \end{vmatrix}=\pm\begin{vmatrix} \rho_j & \rho_n\\ v_j & v_n \end{vmatrix}, \end{align*}$$
for some
$1\leq i<j\leq n-1$
, or equivalently,
$\mathbf {p}_n$
would be parallel to
$\mathbf {p}_i\pm \mathbf {p}_j$
, contradicting the assumption on
$\mathbf {p}_n$
. If one volume were zero, then
$\mathbf {p}_n$
would be parallel to some
$\mathbf {p}_i$
,
$1\leq i\leq n-1$
, again a contradiction.
For the second case, we assume that
$\mathbf {p}_{n-1}\pm \mathbf {p}_n$
is not parallel to any nonzero vector of the form
$\mathbf {p}_k\pm \mathbf {p}_\ell $
, where
$(k,\ell )\neq (n-1,n)$
. Then, the zonotope
$$\begin{align*}Z'=\sum_{i=1}^{n-2}[\mathbf{0},\mathbf{y}_i]+[\mathbf{0},\mathbf{y}_{n-1}\mp\mathbf{y}_n],\end{align*}$$
is an sLRZ. Indeed, if two volumes of parallelepipeds of
$Z'$
were equal, then by Lemma 3.2 and Proposition 3.4 we would have
$$\begin{align*}\begin{vmatrix} \rho_i & \rho_{n-1}\pm\rho_n\\ v_i & v_{n-1}\pm v_n \end{vmatrix}=\pm\begin{vmatrix} \rho_j & \rho_{n-1}\pm\rho_n\\ v_j & v_{n-1}\pm v_n \end{vmatrix}, \end{align*}$$
for some
$1\leq i<j\leq n-1$
, or equivalently,
$\mathbf {p}_{n-1}\pm \mathbf {p}_n$
would be parallel to
$\mathbf {p}_i\pm \mathbf {p}_j$
, contradicting the assumption on
$\mathbf {p}_n$
. If one volume were zero, then
$\mathbf {p}_{n-1}\pm \mathbf {p}_n$
would be parallel to some
$\mathbf {p}_i$
,
$1\leq i\leq n-1$
, again a contradiction, completing the proof.
Proof of Theorem B’
We suppose that Conjecture B’ holds for
$n-1$
, so in particular it holds for the sLRZ
$Z' \subseteq T(Z)$
, which exists by Proposition 4.1. On the other hand, by Lemma 2.5,
$\lambda _1(Z-Z) \le \frac {2}{n(n+1)}$
. Thus, Proposition 2.7 gives
$$ \begin{align*} \mu(Z) &\leq \lambda_1(Z-Z)+\mu(T(Z),\mathbb{Z}^{n-2}) \\ &\le \ \lambda_1(Z-Z)+\mu(Z',\mathbb{Z}^{n-2})\\ &\leq \frac{2}{n(n+1)}+\frac{n-2}{n} \ = \ \frac{n-1}{n+1}.\\[-43pt] \end{align*} $$
4.2 Small cases of the LVP
We now tackle a couple of special cases for which the LVP holds. To this end, recall from the introduction that for a point set
$\mathbf {P}={\left \{{\mathbf {p}_1,\dotsc ,\mathbf {p}_n}\right \}}\subseteq \mathbb {R}^2$
we associate the multiset
$$\begin{align*}S_{\mathbf{P}} = \mathbf{P} \cup {\left\{{\mathbf{p}_i+\mathbf{p}_j : 1\leq i<j\leq n}\right\}} \cup {\left\{{\mathbf{p}_i-\mathbf{p}_j : 1\leq i<j\leq n}\right\}}. \end{align*}$$
In the first case, we do not require the vectors to be rational.
Proposition 4.2. Suppose that
$\mathbf {P}={\left \{{\mathbf {p}_1,\dotsc ,\mathbf {p}_n}\right \}}$
linearly spans
$\mathbb {R}^2$
, contains no two equal or opposite elements and
$\mathbf {p}_3,\dotsc ,\mathbf {p}_n$
are parallel. Then,
$\mathbf {P}$
has the LVP.
Proof. If all but one vector were parallel, say
$\mathbf {p}_2$
is also parallel to
$\mathbf {p}_3,\dotsc ,\mathbf {p}_n$
, then all vectors of the form
$\mathbf {p}_j\pm \mathbf {p}_k$
are parallel to
$\mathbf {p}_2$
as well, for
$2\leq j,k\leq n$
. Then, obviously each vector
$\mathbf {p}_1\pm \mathbf {p}_j$
is not parallel to any other vector in
$S_{\mathbf {P}}$
, for
$2\leq j\leq n$
.
If
$\mathbf {p}_1$
and
$\mathbf {p}_2$
were parallel, then we write every vector in
$S_{\mathbf {P}}$
as a linear combination of
$\mathbf {p}_1$
and
$\mathbf {p}_3$
. We may further assume that
$\mathbf {p}_2=\lambda _2\mathbf {p}_1$
, with
$\lambda _2>\lambda _1=1$
, and
$\mathbf {p}_j=\mu _j\mathbf {p}_3$
for
$4\leq j\leq n$
, with
$1=\mu _3<\mu _4<\mu _5<\dotsb <\mu _n$
. Then, it is clear that
$\mathbf {p}_2+\mathbf {p}_3=\lambda _2\mathbf {p}_1+\mathbf {p}_3$
is not parallel to any other vector of
$S_{\mathbf {P}}$
; indeed, if there were such a vector in
$S_{\mathbf {P}}$
, it should have both coordinates positive, with respect to
$\mathbf {p}_1$
and
$\mathbf {p}_3$
, so, it would be of the form
$\mathbf {p}_i+\mathbf {p}_j=\lambda _i\mathbf {p}_1+\mu _j\mathbf {p}_3$
, with
$1\leq i\leq 2$
,
$3\leq j\leq n$
. However, if
$(i,j)\neq (2,3)$
, then these vectors cannot be parallel, as
$\lambda _i-\mu _j\lambda _2<0$
.
So, we reduce to the case where
$\mathbf {p}_1$
,
$\mathbf {p}_2$
and
$\mathbf {p}_3$
are pairwise not parallel. We first note that changing a
$\mathbf {p}_i$
to its opposite or applying a linear transformation to
$\mathbf {P}$
does not affect the LVP. So, without loss of generality, we may assume that all
$\mathbf {p}_j$
with
$3\leq j\leq n$
lie on the positive y-axis, and
$\mathbf {p}_1$
,
$\mathbf {p}_2$
in the first quadrant, such that
$\mathbf {p}_1$
has smaller slope than
$\mathbf {p}_2$
; We also assume that
$$\begin{align*}v_3<v_4<\dotsb<v_n. \end{align*}$$
With this convention, the slopes of the vectors
$\mathbf {p}_2+\mathbf {p}_j$
,
$3\leq j\leq n$
, form a strictly increasing sequence of numbers strictly between the slope of
$\mathbf {p}_2$
and the slope of
$\mathbf {p}_3$
, while those of
$\mathbf {p}_1-\mathbf {p}_j$
,
$3\leq j\leq n$
, form a strictly decreasing sequence of numbers strictly between the slope of
$\mathbf {p}_1$
and the slope of
$-\mathbf {p}_3$
. Therefore, these
$2(n-2)$
vectors along with
$\mathbf {p}_1$
,
$\mathbf {p}_1+\mathbf {p}_2$
,
$\mathbf {p}_2$
, define
$2n-1$
distinct lines through the origin, none of them the y-axis. There are a total of
$(n-2)^2$
vectors of
$S_{\mathbf {P}}$
lying on the y-axis, so failure of the LVP and the pigeonhole principle would imply them to lie in at most
$2n-2$
lines, completing the proof that
$\mathbf {P}$
indeed satisfies the LVP.
Corollary 4.3. Any set of three vectors spanning
$\mathbb {R}^2$
, with no two equal or opposite, has the LVP.
We now deal with the case of four vectors, for which we need them to be rational.
Proposition 4.4. Let
$\mathbf {P} = {\left \{{\mathbf {p}_1,\mathbf {p}_2,\mathbf {p}_3,\mathbf {p}_4}\right \}}\subseteq \mathbb {Q}^2$
, with not all parallel and no two equal or opposite. Then,
$\mathbf {P}$
has the LVP.
Proof. If two of the vectors are parallel then
$\mathbf {P}$
has the LVP, by Proposition 4.2. So, we may assume that no two of them are parallel.
Since the LVP is invariant under linear transformation and under changing one or more vectors to their opposites, we can also assume that
$$\begin{align*}\mathbf{p}_1=(1,0), \ \mathbf{p}_2=(x_2,y_2), \ \mathbf{p}_3=(x_3,y_3), \ \mathbf{p}_4=(0,1), \end{align*}$$
with
$x_2, x_3, y_2, y_3>0$
and the slope of
$\mathbf {p}_2$
smaller than that of
$\mathbf {p}_3$
. Indeed, first perform a rational linear transformation sending
$\mathbf {p}_4$
to
$(0,1)$
; then assume without loss of generality that
$\mathbf {p}_1, \mathbf {p}_2, \mathbf {p}_3$
have positive x-coordinate (changing them to their opposite if needed) and are ordered according to slope (relabelling them if needed); finally, send
$\mathbf {p}_1$
to
$(1,0)$
with a second rational linear transformation that fixes
$\mathbf {p}_4$
.
The vectors
$\mathbf {p}_i$
(
$i=1,2,3,4$
),
$\mathbf {p}_i + \mathbf {p}_{i+1}$
(
$i=1,2,3$
) and
$\mathbf {p}_4 - \mathbf {p}_{1}$
define eight distinct lines through the origin; the first seven have non-negative distinct slopes (including
$0$
and
$\infty $
) since
$$\begin{align*}0 \le \frac{x_i}{y_i}<\frac{x_i+x_{i+1}}{y_i+y_{i+1}}<\frac{x_{i+1}}{y_{i+1}} \le \infty, \;\;\; 1\leq i\leq3,\end{align*}$$
and the last one has negative slope, equal to
$-1$
.
Since
$S_{\mathbf {P}}$
has
$16$
elements, the only possibility for
$\mathbf {P}$
not to satisfy the LVP would be if each of these eight lines contains exactly two of the vectors; below we show that this possibility leads to a contradiction.
If one of
$x_i$
(
$i\in \{2,3\}$
) is smaller than
$1$
then
$\mathbf {p}_i - \mathbf {p}_1$
has negative slope, hence it must have the slope of
$\mathbf {p}_4 - \mathbf {p}_1$
, which gives a contradiction since then the three vectors
$\mathbf {p}_4 - \mathbf {p}_i$
,
$\mathbf {p}_4 - \mathbf {p}_1$
and
$\mathbf {p}_i - \mathbf {p}_1$
are parallel. So,
$x_2,x_3\ge 1$
. The same argument with
$\mathbf {p}_4 - \mathbf {p}_i$
instead of
$\mathbf {p}_i - \mathbf {p}_1$
implies
$y_2,y_3\ge 1$
. This now implies that
-
• The only vector of
$S_{\mathbf {P}}$
that can have negative slope (in particular, the only one that can be parallel to
$\mathbf {p}_4-\mathbf {p}_1$
) is
$\mathbf {p}_3-\mathbf {p}_2$
; hence we assume
$x_2+x_3 = y_2+y_3$
. -
• The only vector that can be parallel to
$\mathbf {p}_1$
is
$\mathbf {p}_4-\mathbf {p}_2$
; hence
$y_2=1$
. -
• The only one that can be parallel to
$\mathbf {p}_4$
is
$\mathbf {p}_3-\mathbf {p}_1$
; hence
$x_3=1$
.
So, we have that
$$ \begin{align} \mathbf{p}_2=(\lambda,1), \;\;\; \mathbf{p}_3=(1,\lambda), \end{align} $$
for some rational
$\lambda>1$
(
$\lambda =1$
would give
$\mathbf {p}_2=\mathbf {p}_3)$
.
So far we have four pairs of parallel vectors: the three pairs mentioned above (with slopes
$0$
,
$\infty $
and
$-1$
), plus
$\mathbf {p}_1+\mathbf {p}_4=(1,1)$
and
$\mathbf {p}_2+\mathbf {p}_3=(1+\lambda , 1+\lambda )$
(with slope
$1$
). The eight unpaired vectors are the following:
$$\begin{align*}\begin{array}{llll} \mathbf{p}_1 + \mathbf{p}_2, & \mathbf{p}_2, & \mathbf{p}_3, & \mathbf{p}_3 + \mathbf{p}_4, \\ \mathbf{p}_1 + \mathbf{p}_3, & \mathbf{p}_2 + \mathbf{p}_4, & \mathbf{p}_2 - \mathbf{p}_1, & \mathbf{p}_4 - \mathbf{p}_3. \end{array} \end{align*}$$
The first four have different (and increasing) slopes, so we would need to pair the last four to them.
The vector
$\mathbf {p}_1+\mathbf {p}_3=(2,\lambda )$
has slope strictly between those of
$\mathbf {p}_1$
and
$\mathbf {p}_3$
. Hence, it must be parallel either to
$\mathbf {p}_2 =(\lambda ,1)$
or to
$\mathbf {p}_1+\mathbf {p}_2=(\lambda +1,1)$
. The first case yields
$\lambda =\sqrt {2}$
, a contradiction, since
$\lambda \in \mathbb {Q}$
. The second case yields
$\lambda ^2+\lambda -2=0$
, a contradiction, since the two solutions are
$\lambda \in \{1,-2\}$
and we had
$\lambda>1$
. Thus, we establish a contradiction if we assume that
$\mathbf {P}$
does not have the LVP, concluding the proof.
Remark 4.5. As we said in the introduction, if we remove the restriction that the given vectors are rational then the vertices of any regular n-gon other than the triangle, hexagon, and square provide a counter-example to the LVP. In fact, our proof of the LVP for four vectors shows that the only sets of four vectors, no two parallel or opposite, failing to have the LVP are those of the form expressed in (4.1) with
$\lambda = \sqrt {2}$
, which are (linearly isomorphic) to four consecutive vertices of the regular octagon.
5 Cosimple configurations and a generalization of sLRC, with a finite checking result
Recall Definition 1.9: A lattice zonotope spanning
$\mathbb {R}^d$
is called cosimple if there is a linear dependence among its generators having coefficients that are all nonzero and with pairwise different absolute values. In particular, a cosimple zonotope in
$\mathbb {R}^d$
with
$d+1$
generators has its generators in linear general position, so that the class of cosimple zonotopes with
$d+1$
generators coincides with the class of sLRZs.
5.1 Proof of Theorem C
The advantage of allowing for more than
$d+1$
generators is that now any projection of a cosimple zonotope is cosimple. Observe that the projection along one of the generators will make that generator be zero. We can still consider it part of the vector set although this is irrelevant both for the definition of cosimplicity (we can give the zero vector an arbitrary coefficient in a linear dependence) and for Conjecture C (the zero vector as a generator does not affect the covering radius).
Invariance under projection makes the analogue of Theorems A’ and B’ much easier to prove and allows us to remove the ‘Lonely Vector Problem’ from the latter:
Proof of Theorem C
Let Z be our cosimple zonotope with more than
${\binom {d+2}2}^d$
lattice points. By Lemma 2.5 we have
$\lambda _1(Z-Z) \le 1/ \binom {d+2}2$
and by Proposition 2.7 and the induction hypothesis (using that the projection of a cosimple zonotope is cosimple)
$$\begin{align*}\mu(Z) \leq \lambda_1(Z-Z) + \mu\left(\pi(Z),\pi(\mathbb{Z}^d)\right) \le \frac{1}{{\binom{d+2}2}} + \frac{d-1}{d+1} =\frac{d}{d+2}.\\[-47pt] \end{align*}$$
5.2 Remarks on cosimple zonotopes
We first show that in Conjecture C there is no loss of generality in assuming the generators to be primitive, generalizing Proposition 2.9:
Lemma 5.1. Let
$d\ge 2$
. If Conjecture C holds in dimension
$d-1$
for every cosimple zonotope with
$n-1$
generators, then it holds in dimension d for all cosimple zonotopes with n generators one of which is not primitive or two of which agree or are opposite to one another.
Proof. If two generators agree or are opposite to one another, then we can substitute their sum for the two of them, so we are in the case of a nonprimitive generator.
Hence, let Z be a cosimple d-zonotope with n generators
$\mathbf {u}_1, \dotsc , \mathbf {u}_n \in \mathbb {Z}^d$
and suppose without loss of generality that
$\mathbf {u}_{n}=k \mathbf {e}_d$
, for some
$k\in \mathbb {Z}_{\ge 2}$
. Let
$\pi :\mathbb {R}^d\to \mathbb {R}^{d-1}$
be the projection that forgets the last coordinate. Then
$Z=Z_1+ Z_2$
, where
$Z_1$
is the segment of length k in the last coordinate direction and
$\pi (Z_2)$
is a cosimple
$(d-1)$
-zonotope with
$n-1$
generators. Hence, Proposition 2.8 plus the inductive hypothesis gives
$$\begin{align*}\mu(Z) \le \max\left\{\mu(Z_1), \mu(\pi(Z_2)) \right\} \le \max\left\{\frac1k, \frac{d-1}{d+1}\right\} \le \frac{d}{d+2}, \end{align*}$$
since
$d \geq 2$
.
Corollary 5.2. Let
$d\ge 2$
. If Conjecture C holds in dimension
$d-1$
for every cosimple zonotope with
$n-1$
generators, then it holds in dimension d for all cosimple zonotopes with n generators one of which is not primitive or two of which agree or are opposite to one another.
We now characterize cosimple configurations:
Lemma 5.3. Let
$\mathbf {A}$
be a finite collection of vectors spanning
$\mathbb {R}^d$
. Then,
$\mathbf {A}$
is cosimple if and only if neither of the following conditions hold:
-
(i) There is a hyperplane H containing all but one of the elements of
$\mathbf {A}$
. -
(ii) There is a hyperplane H containing all but two of the elements of
$\mathbf {A}$
, and the two elements are at the same distance from H.
Proof. The ‘only if’ is easy: if (i) happens then the element in question has coefficient zero in every linear dependence. If (ii) happens then the coefficients of the two elements in question have the same absolute value in every linear dependence.
For the converse, suppose that none of (i) and (ii) happens. Let
$L \subseteq \mathbb {R}^{\mathbf {A}}$
be the linear space of linear dependence vectors in
$\mathbf {A}$
. The fact that (i) and (ii) do not hold means that L is not contained in any of the hyperplanes where a coordinate is zero or where two coordinates have the same absolute value (this arrangement of hyperplanes happens to be the Coxeter arrangement of type
$B_n$
, although we do not need this). Then, a generic vector
$\lambda $
from L does not belong to any of those hyperplanes, and certifies that
$\mathbf {A}$
is cosimple.
Remark 5.4. Let us call a vector configuration simple if no element is zero or equal or opposite to another one.Footnote 2 The characterization in Lemma 5.3 then says that
$\mathbf {A}$
is cosimple if and only if its Gale transform is simple, which explains the name.
To understand this connection, let us briefly review Gale duality; see, for example, [Reference De Loera, Rambau and Santos14, Section 4.1] for more details. If
$\mathbf {A} = \{\mathbf {u}_1, \dots , \mathbf {u}_n\} $
is a finite set of n vectors in
$\mathbb {R}^d$
, we call linear evaluations and linear dependences of
$\mathbf {A}$
the following two linear subspaces of
$\mathbb {R}^n\cong \mathbb {R}^{\mathbf {A}}$
:
$$ \begin{align*} \operatorname{\mathrm{eval}}(\mathbf{A})&:=\left\{\left(f(\mathbf{u}_1), \dots, f(\mathbf{u}_n)\right) : f \in ({\mathbb{R}^d})^*\right\}, \\ \operatorname{\mathrm{dep}}(\mathbf{A})&:=\left\{\left(\lambda_1,\dots,\lambda_n\right) \in \mathbb{R}^n: \lambda_1 \mathbf{u}_1 + \dots + \lambda_n \mathbf{u}_n = \mathbf{0} \right\}. \end{align*} $$
These two subspaces are orthogonal complements of one another, and have ranks equal to k and
$n-k$
, where k is the rank of
$\mathbf {A}$
. (In what follows we assume
$k=d$
). A subset
$\mathbf {B}\subseteq \mathbb {R}^{n-d}$
of size n is called a Gale transform or a Gale dual of
$\mathbf {A}$
if it has the following two equivalent propertiesFootnote 3:
$$\begin{align*}\operatorname{\mathrm{eval}}(\mathbf{A}) = \operatorname{\mathrm{dep}}(\mathbf{B}), \qquad \operatorname{\mathrm{eval}}(\mathbf{B}) = \operatorname{\mathrm{dep}}(\mathbf{A}). \end{align*}$$
In this language, Lemma 5.3 says that
$\mathbf {A}$
is cosimple if and only if none of
$\mathbf {e}_i$
or
$\mathbf {e}_i \pm \mathbf {e}_j$
lie in
$\operatorname {\mathrm {eval}}(\mathbf {A})$
, where
$\mathbf {e}_i$
denotes the i-th standard basis vector. The same conditions for
$\operatorname {\mathrm {dep}}(\mathbf {B})$
are equivalent to
$\mathbf {B}$
being simple.
Corollary 5.5. Any set of integer vectors in linear general position with at least two more vectors than its dimension is cosimple.
Proof. Assuming, for contradiction, that the vectors are not cosimple, the obstructions in Lemma 5.3 imply that all but (at most) two of them lie in a hyperplane, hence they are not in linear general position.
Corollary 5.6. Every cosimple zonotope has lattice-width three or more. Conversely, if Z is a lattice d-zonotope of width three or more, not a parallelepiped, and its generators span the lattice, then Z is cosimple.
Proof. For the first part we argue by contradiction. If f is an integer linear functional giving width
$w\in \{1,2\}$
to a lattice zonotope Z there are two possibilities: either f is zero in all but one of the generators, or it has value
$\pm 1$
in two of them and is zero in the rest. Both cases imply Z not to be cosimple, by Lemma 5.3.
For the second part, suppose that Z is not cosimple and that the generators of Z integrally span
$\mathbb {Z}^d$
. By Lemma 5.3 one of the following happens:
-
1. All but one of the generators lie in a hyperplane. Then the condition that the generators span the lattice implies that Z has width one with respect to that hyperplane.
-
2. All but two generators lie in a hyperplane, and the functional f vanishing on that hyperplane has the same value on the other two generators. Again, the condition that generators span the lattice implies that f has value
$\pm 1$
on those two generators, hence Z has width two.
Lemma 5.3 implies that being cosimple is closed under extending the set. Since the covering radius is nonincreasing with respect to inclusion, minimal counter-examples to Conjecture C must be also minimal cosimple configurations; that is, cosimple configurations with the property that removing an element produces a noncosimple one. To this end, in the following result we characterize minimal cosimple configurations, except that the characterization is easier to express in terms of Gale duality:
Corollary 5.7. Let
$\mathbf {A}$
be a cosimple configuration and let
$\mathbf {B}$
be its Gale transform. Then,
$\mathbf {A}$
is minimal cosimple if and only if in
$\mathbf {B}$
every element is parallel to either another element or to the sum or difference of some other two elements.
Proof. Via Gale duality, deleting an element
$\mathbf {u}$
in a configuration
$\mathbf {A}$
is equivalent to contracting the corresponding element
$\mathbf {v}$
in its Gale dual
$\mathbf {B}$
, which geometrically amounts to projecting
$\mathbf {B}$
along the direction of
$\mathbf {v}$
(see [Reference De Loera, Rambau and Santos14, Section 4.2]). Hence, we want to characterize the simple configurations
$\mathbf {B}$
with the property that the projection of
$\mathbf {B} \setminus \mathbf {v}$
along the direction of
$\mathbf {v}$
fails to be simple for every
$\mathbf {v} \in \mathbf {B}$
.
The failure may happen in two ways: either
$\mathbf {B}$
has two parallel elements, so that projecting along one of them makes the other one zero, or
$\mathbf {B}$
has two elements with sum or difference parallel to a third element, so that projecting along the latter makes the first two equal or opposite.
This characterization of minimal cosimple configurations shows that the zonotopes of type (3.2), (3.3) and (3.4) are the natural ones to consider in Sections 3 and 4.
6 Dimension two: proof of sLRC and its cosimple generalization
That Conjecture B’ holds in dimension two (equivalently, that the shifted LRC holds for four runners) has been proved in [Reference Cslovjecsek, Malikiosis, Naszódi and Schymura12]. Here, we give a proof of the stronger Conjecture C in dimension two and for an arbitrary number n of generators. The idea is to show that we only need to look at zonotopes of very small volume. For this, we use two immediate consequences of Lemma 2.10:
Corollary 6.1.
-
(i) Let
$C \subseteq \mathbb {R}^2$
be a convex body of lattice-width at least w and covering radius greater than
$\mu $
, with
$\mu w>1$
. Then,
$$\begin{align*}\operatorname{\mathrm{vol}}(C) < \frac{w^2}{2\mu w - 2}. \end{align*}$$
-
(ii) Let Z be a lattice
$2$
-zonotope of lattice-width
$w \ge 3$
and covering radius
$\mu> 1/2$
. Then,
$$\begin{align*}w = 3 \quad , \quad \mu \leq \frac23 \quad \textrm{and} \quad \operatorname{\mathrm{vol}}(Z) \leq 8. \end{align*}$$
Proof. (i): This is basically a rephrasing of Lemma 2.10. Let
$\mu '>\mu $
be the covering radius of C and let
$C'=\mu ' C$
, which has a hollow translate and lattice-width at least
$\mu ' w> 1$
. Then, Lemma 2.10 gives
$$\begin{align*}\operatorname{\mathrm{vol}}(C) = \frac{\operatorname{\mathrm{vol}}(C')}{{\mu'}^2} \le \frac{{\mu'}^2 w^2}{{\mu'}^2 2({\mu'} w-1)} = \frac{w^2}{ 2\mu' w-2} < \frac{w^2}{ 2\mu w-2}. \end{align*}$$
(ii): As before, the zonotope
$Z' = \mu Z$
has a hollow translate, and by the assumptions, its lattice-width equals
$\mu w$
and is strictly greater than
$3/2$
. Moreover, we also have
$\mu w \leq 2$
by the two-dimensional ‘flatness theorem’ for
$\mathbf {0}$
-symmetric convex bodies due to [Reference Averkov and Wagner3, Corollary 2.7]. In combination, the inequalities
$3/2 < \mu w \leq 2$
and
$\mu> 1/2$
give
$w=3$
and
$\mu \leq 2/3$
, because the lattice-width of any lattice zonotope is an integer.
Regarding the volume, Lemma 2.10 together with
$1/\mu < 2$
gives
$$\begin{align*}\operatorname{\mathrm{vol}}(Z) = \frac{\operatorname{\mathrm{vol}}(Z')}{\mu^2} < \frac{4(\mu w)^2}{2(\mu w - 1)} \leq 9. \end{align*}$$
The last inequality holds, since the function
$x \mapsto \frac {x^2}{x-1}$
has maximum value equal to
$9/2$
in the interval
$x \in [\frac 32,2]$
. Finally, the volume of any lattice zonotope is an integer, so that
$\operatorname {\mathrm {vol}}(Z) \leq 8$
as claimed.
For the proof of our main two-dimensional result we need the following classification of lattice parallelograms with primitive generators. The classification is up to affine transformations that do not change the lattice
$\mathbb {Z}^d$
. More precisely, two lattice polytopes
$P,Q \subseteq \mathbb {R}^d$
are called unimodularly equivalent if there is a unimodular matrix
$U \in \mathbb {Z}^{d \times d}$
, that is,
$|\det (U)|=1$
, and a translation vector
$\mathbf {t} \in \mathbb {Z}^d$
such that
$P = UQ + \mathbf {t}$
; in symbols
$P \cong Q$
.
Lemma 6.2. Let P be a lattice parallelogram of area q with primitive generators. Then, P is unimodularly equivalent to
$$\begin{align*}P_{p,q}:=[\mathbf{0}, \mathbf{e}_1] + [\mathbf{0}, (p,q)] , \end{align*}$$
for some
$p\in \mathbb {Z}$
with
$\gcd (p,q)=1$
. Moreover,
$P_{p,q}$
and
$P_{p',q}$
are unimodularly equivalent if
$p'=\pm p^{\pm 1} \bmod q$
.
Hence, if
$q\le 8$
, then P is equivalent to either
$P_{1,q}$
or to one of
$P_{2,5}$
,
$P_{2,7}$
,
$P_{3,8}$
.
Proof. Since our generators are primitive, there is no loss of generality in assuming that the first one is
$\mathbf {e}_1$
, which already implies that our parallelogram is a lattice translation of
$P_{p,q}$
for some p. The condition
$\gcd (p,q)$
is neccessary (and sufficient) for the generator
$(p,q)$
to be primitive.
The unimodular transformation
$\binom {1\ 1}{0 \ 1}$
shows that
$P_{p,q} \cong P_{p+q,q}$
; hence p is only important modulo q. That
$P_{p,q} \cong P_{-p,q}$
follows by reflection on the y-axis (followed by the translation by the vector
$\mathbf {e}_1$
) and that
$P_{p,q} \cong P_{p',q}$
when
$p'=p^{-1} \bmod q$
follows from the fact that if
$p'p =1 +aq$
for some integer a, then the unimodular transformation
$\binom {p'\ -a}{q\ \ -p}$
sends
$\{\mathbf {e}_1, (p,q)\}$
to
$\{(p',q), \mathbf {e}_1\}$
.
Theorem 6.3. All lattice
$2$
-zonotopes of covering radius greater than 1/2 are unimodularly equivalent to one of the following:
-
1. Parallelograms of lattice-width one, generated by
$\{(1,0), (0,k)\}$
for some
$k\ge 1$
. -
2. Parallelograms
$P_{1,k}$
of lattice-width two and area k,
$k\ge 2$
. -
3. Hexagons of lattice-width two, with volume vector
$(1,1,k)$
for some
$k\ge 1$
. -
4. The parallelogram
$P_{2,5}$
of lattice-width three and volume
$5$
.
In particular, Conjecture C holds in dimension two for any number of generators.
Proof. Let Z be a lattice
$2$
-zonotope. We argue depending on the lattice-width of Z. Lattice-width one implies that Z is (up to unimodular equivalence) a parallelogram of the type in part (1).
Parallelograms of lattice-width two must attain their width either with respect to a diagonal direction or with respect to an edge e. The former are the parallelograms in part (2), and the latter have
$\mu (Z) = 1/2$
unless the edge e is primitive, in which case they have area two and are either in part (1) or part (2), with
$k=2$
.
The nonparallelograms of lattice-width two necessarily have three generators which can be assumed to be
$(a,0), (b,1), (c,1)$
, as we may apply a unimodular transformation so that the lattice-width is attained in the direction of the second coordinate. Such a hexagon contains the parallelogram with generators
$(a,0)$
and
$(b+c,2)$
, whose covering radius is
$\max \{\frac 12,\frac 1a\}$
, so
$\mu (Z)> 1/2$
implies
$a=1$
and the volume vector is
$(1,1,k)$
, with
$k=|b-c|$
.
Hence, for the rest of the proof we assume that Z has lattice-width at least three and covering radius
$\mu = \mu (Z)> 1/2$
, which implies by Corollary 6.1 (ii) that
$\operatorname {\mathrm {vol}}(Z) \le 8$
.
We now argue depending on the number of generators in Z. This number must be less than five, since the volume of a lattice zonotope with n generators (in linear general position) is at least
$\binom {n}{2}$
, and
$\binom 52> 8$
. So, we have three cases:
-
• Suppose that Z has two generators, that is, it is a parallelogram. If one of the generators is not primitive, then the fact that this edge has length at least two and that the width of Z with respect to the functional constant on this edge is more than two implies
$\mu (Z)\le 1/2$
. (This is a particular case of Proposition 2.8, where we project Z along the functional f).If Z is a parallelogram with both edges primitive, Lemma 6.2 implies that Z is either in part (2) or it is equivalent to one of
$P_{2,5}$
,
$P_{2,7}$
,
$P_{3,8}$
. Since
$P_{2,5}$
is in part (4), we only need to check that
$P_{2,7}$
and
$P_{3,8}$
have
$\mu \le 1/2$
. For this:-
–
$P_{2,7}$
contains the parallelogram
$P'$
generated by
$\mathbf {u}_1=(2,6)$
and
$\mathbf {u}_2=(1,1)$
;
$\mathbf {u}_1$
is not primitive and
$P'$
has lattice-width two with respect to the functional
$f(x,y) = 3x-y$
vanishing on it, so
$\mu (P_{2,7}) \le \mu (P') \le 1/2$
. -
–
$P_{3,8}$
is equivalent to
$P_{5,8}$
, which contains the parallelogram
$P'$
generated by
$(2,2)$
and
$(4,6)$
; since none of them is primitive,
$\mu (P_{5,8}) \le \mu (P') \le 1/2$
.
-
-
• Suppose that Z has three generators. The volume vector cannot be
$(2,2,2)$
or of the form
$(a,a,b)$
with
$\gcd (a,b)=1$
since that implies lattice-width two. Indeed, without loss of generality assume that the generator separating the two a’s (with
$a=b=2$
in the first case) is of the form
$(p,0)$
. Then the other two generators are
$(q,h)$
and
$(r,h)$
with
$a = ph$
, so that
$b=(q-r)h$
. Then,
$\gcd (a,b)=1$
implies
$h=1$
, hence width two. The case
$a=b=2$
, using
$b=(q-r)h$
leads to either
$h=1$
(hence width two) or
$q-r=1$
, implying that one of q or r is even and the corresponding generator is not primitive.This leaves only the following possible volume vectors
$(v_1,v_2,v_3)$
satisfying
$v_1+v_2+v_3\le 8$
: That these five zonotopes have
$$\begin{align*}(v_1,v_2,v_3) \in \{ (1,2,3), (1,2,4), (1,2,5), (1,3,4), (2,2,4) \}. \end{align*}$$
$\mu \le \frac 12$
is illustrated in Figure 1, where they are shown to contain a parallelepiped with horizontal base of length two and height two. That parallelepiped has
$\mu =\frac 12$
, so a polygon containing it has
$\mu $
bounded by that. (For
$(1,2,3)$
we show that such a parallelpiped is contained in
$Z_1\cup Z_2$
where
$Z_1$
and
$Z_2$
are translated to one another by the vector
$(2,2)\in 2\mathbb {Z}^2$
, which is enough for the implication.) In fact, their exact covering radii are
$\frac 12$
,
$\frac 37$
,
$\frac 37$
,
$\frac 37$
, and
$\frac 12$
(see [Reference Cslovjecsek, Malikiosis, Naszódi and Schymura12, Table 2] for the first four).Figure 1 The five hexagons in the proof of Theorem 6.3, with their volume vectors. In each of them a parallelepiped with base and height equal to 2 is shown, to illustrate that the hexagons have
$\mu \le \frac 12$
.Figure 2 The octagon in the proof of Theorem 6.3, with an inscribed square implying
$\mu \le \frac 12$
. -
• If Z has four pairwise nonproportional generators, then the volume of Z equals the sum of the six volumes of the parallelograms generated by the
$2$
-element subsets of the generators (cf. [Reference Shephard24, Eq. (57)]). The only possibilities for the volume
$6$
-tuples adding up to eight or less are These numbers, modulo sign and reordering, are the six
$$\begin{align*}\{(1,1,1,1,1,1) ,(1,1,1,1,1,2) , (1,1,1,1,1,3), (1,1,1,1,2,2)\}. \end{align*}$$
$2\times 2$
minors
$(p_{ij})_{1 \le i < j \le 4}$
of a
$2\times 4$
matrix, hence they have to satisfy the following Plücker relation (see, e.g., [Reference Miller and Sturmfels21, Section 4.2]): The only one where this is possible is
$$\begin{align*}p_{14}p_{23} - p_{13}p_{24} + p_{12}p_{34} = 0. \end{align*}$$
$(1,1,1,1,1,2)$
, corresponding uniquely (modulo unimodular transformation) to the zonotope generated by
$(1,0)$
,
$(0,1)$
,
$(1,1)$
, and
$(1,-1)$
. This has covering radius exactly
$1/2$
(see Figure 2).
Remark 6.4. The covering radii of the zonotopes in Theorem 6.3 can be computed to be as follows:
-
1.
$\mu =1$
; -
2.
$\mu = 1/2 + 1/k$
, if k is even, and
$\mu = 1/2 + 1/(2k)$
, if k is odd; -
3.
$\mu = 1/2 + 1/(2k+2)$
, if k is even, and
$\mu = 1/2 + 1/(4k+2)$
, if k is odd; -
4.
$\mu = 3/5$
.
In our calculations below (proof of Proposition 7.4) we need the last one of them, so let us prove it. Using Lemma 6.2 it is easy to see that
$P_{2,5}$
is isomorphic to the parallelogram Q generated by
$(2,-1)$
and
$(1,2)$
, depicted in the left picture of Figure 3. The caption of the figure explains why, indeed,
$\mu (P_{2,5}) = \mu (Q) = 3/5$
.
Figure 3 The covering radius of the parallelogram
$Q \cong P_{2,5}$
equals
$3/5$
: The left picture shows that Q contains a translation of the square
$[0,5/3]^2$
; hence
$\mu (P_{2,5}) \le 3/5$
. For the equality, consider the right picture, where we scale down Q by
$3/5$
about its centre, so that the axes-parallel square in it becomes a lattice unit square with its vertices in the boundary of
$(3/5)Q$
. Since any smaller dilation will fail to contain points from
$\mathbb {Z}^2$
, we have that
$\mu \cdot P_{2,5} + \mathbb {Z}^{2}$
does not cover
$\mathbb {R}^2$
for any
$\mu < 3/5$
.
Proposition 6.5. Let
$n \geq 4$
. Suppose that Conjecture B holds for
$n-1$
velocities and that we have an instance with n velocities satisfying
$\gcd (v_1,\dots , v_{n})=1$
. If
$\delta = \gcd (v_3,\dots , v_{n})$
satisfies
$$ \begin{align*} \delta \ge 2 + \frac8{n-3} & \quad\text{and } \delta \text{ is even, or} \\ \delta \ge 1 + \frac4{n-3} & \quad\text{and } \delta \text{ is odd,} \end{align*} $$
then Conjecture B holds for
$v_1,\dotsc ,v_n$
.
Proof. In the light of Lemma 2.2, the condition
$\delta =\gcd (v_3,\dots , v_{n})$
is equivalent to saying that the parallelogram
$Z_{\{1,2\}}$
spanned by
$\mathbf {u}_1$
and
$\mathbf {u}_2$
has area
$\delta $
.
If
$\mu (Z_{\{1,2\}}) \le \tfrac {n-1}{n+1}$
then sLRZ holds for
$(v_1,\dots ,v_n)$
by Proposition 2.8 applied to the projection along the plane
$\operatorname {\mathrm {lin}}(\{\mathbf {u}_1, \mathbf {u}_2\})$
. Indeed, every fibre of the projection contains a translated copy of
$Z_{\{1,2\}}$
, and the image of the projection is an sLRZ with two less generators.
Hence, we have to consider only the parallelograms with
$\mu (Z_{\{1,2\}})>\tfrac {n-1}{n+1} \geq \tfrac 35$
, listed in Theorem 6.3 and whose covering radii are given in Remark 6.4. Those of part (1) are discarded by Lemma 5.1, since they have a nonprimitive generator amd the one in part (3) has covering radius
$\tfrac 35 \leq \tfrac {n-1}{n+1}$
, so only those in part (2) need to be considered. These have covering radius
$1/2 +1/\delta $
if their area
$\delta $
is even, and
$1/2+1/2\delta $
, if it is odd. The inequalities
$$\begin{align*}\frac12 + \frac1\delta \leq \frac{n-1}{n+1} \quad\text{ and }\quad \frac12 + \frac1{2\delta} \leq \frac{n-1}{n+1} \end{align*}$$
are, respectively, equivalent to the ones in the statement.
The values of
$\delta $
not covered by Proposition 6.5 quickly decrease with n. In fact, since Conjecture B holds for
$n \leq 4$
(see Remark 1.12), the proposition implies the following:
Corollary 6.6. Suppose that Conjecture B holds for
$n-1$
velocities but fails for some vector with n velocities and satisfying
$\gcd (v_1,\dots , v_{n})=1$
. Then either:
-
1.
$n\in \{5,6\}$
and
$\gcd (v_3,\dots , v_{n}) \in \{1,2,4\}$
, or -
2.
$n\ge 7$
and
$\gcd (v_3,\dots , v_{n}) \in \{1,2\}$
.
7 Dimension three: volume bound for potential counterexamples
We here prove that any potential counter-example to Conjecture C for dimension
$3$
(and hence any potential counterexample to Conjectures B and B’ for
$n=4$
) has volume bounded by 195. Independently of the zonotope to be cosimple, we show the following stronger result:
Theorem 7.1. Let Z be a lattice
$3$
-zonotope with
$\mu (Z) \geq 3/5$
and let w be its lattice-width. Then,
$w \leq 6$
and if
$w \ge 3$
, then either:
-
1.
$w=3$
and either
$\operatorname {\mathrm {vol}}(Z) \le 120$
or Z is a parallelepiped projecting to the parallelogram
$P_{2,5}$
of Theorem 6.3. If Z is an sLRZ then
$\operatorname {\mathrm {vol}}(Z) \le 80$
. -
2.
$w=4$
and
$\operatorname {\mathrm {vol}}(Z) \le 195$
. -
3.
$w=5$
and
$\operatorname {\mathrm {vol}}(Z) \le 125$
. -
4.
$w=6$
and
$\operatorname {\mathrm {vol}}(Z) \le 98$
.
That all cosimple zonotopes (hence all sLRZ) have lattice-width at least three follows from Corollary 5.6. In what follows, we treat separately the cases of lattice-width at least four and equal to three.
7.1 Zonotopes of lattice-width at least four
To deal with zonotopes of lattice-width at least four, we argue similarly as we did in Corollary 6.1 and make use of Lemma 2.11, which is the corresponding three-dimensional volume bound for hollow convex bodies.
Corollary 7.2. Let Z be a lattice
$3$
-zonotope of lattice-width
$w \ge 4$
and covering radius
$\mu \ge 3/5$
. Then,
$w \le 6$
and the volume of Z is upper bounded by
-
(i)
$195$
if
$w=4$
, -
(ii)
$125$
if
$w=5$
, -
(iii)
$98$
if
$w=6$
.
Proof. It is proven in [Reference Averkov, Codenotti, Macchia and Santos2, Theorem 5.2] that a hollow convex 3-body has lattice-width bounded by
$3.972$
. Hence, for a convex body of covering radius
$\mu \ge 3/5$
we have
$$\begin{align*}w\le 3.972 \mu^{-1} \le 3.972 \cdot \frac{5}{3} = 6.62. \end{align*}$$
This shows
$w \le 6$
, since the lattice-width of the lattice zonotope Z is an integer.
For the volume, let
$Z'=\mu Z$
, which has a hollow translate and lattice-width
$\mu w$
. For
$w \ge 5$
, we have
$\mu w \ge 3$
so we can apply the first bound in Lemma 2.11, which gives
$$\begin{align*}\operatorname{\mathrm{vol}}(Z) = \mu^{-3} \operatorname{\mathrm{vol}}(Z') \le 8 \mu^{-3} \frac{\mu^{3}w^3}{(\mu w-1)^3} = \left(\frac{2w}{\mu w-1}\right)^3 \le \left(\frac{10w}{3w-5}\right)^3. \end{align*}$$
Plugging in
$w=5$
and
$w=6$
gives bounds of
$(50/10)^3=125$
and
$(60/13)^3 = 98.32$
, respectively. The observation that
$\operatorname {\mathrm {vol}}(Z)$
is an integer gives the bound for cases (ii) and (iii).
For
$w=4$
, we may need to use the first bound of Lemma 2.11 or the second one, depending on
$\mu $
, since for
$\mu \approx 3/5$
we have that
$\mu w \approx 12/5 = 2.4$
. Thus, we use the maximum of the two bounds. Using
$\mu \ge 3/5$
, the first bound gives
$$\begin{align*}\operatorname{\mathrm{vol}}(Z) = \mu^{-3} \operatorname{\mathrm{vol}}(Z') \le \mu^{-3} \frac{8 \mu^3w^3}{(\mu w - 1)^3} = \frac{8 \cdot 4^3}{(4\mu - 1)^3} \le \frac{40^3}{7^3} = 186.59, \end{align*}$$
and the second one gives
$$\begin{align*}\operatorname{\mathrm{vol}}(Z) = \mu^{-3} \operatorname{\mathrm{vol}}(Z') \le \frac{3 w^3}{4(\mu w - (1+2/\sqrt3))} \le \frac{48}{12/5 - (1+2/\sqrt3)} = 195.68, \end{align*}$$
finishing the proof.
Remark 7.3. The same ideas from the proof of [Reference Iglesias-Valiño and Santos20, Theorem 2.1], but assuming C to be
$\mathbf {0}$
-symmetric, imply that the first bound in Lemma 2.11 applies for
$w\ge \sqrt {5} \approx 2.236$
. Using this extended bound in the proof of Corollary 7.2 would reduce the volume bound for lattice-width
$w=4$
to
$186$
, instead of
$195$
.
7.2 Zonotopes of lattice-width three
For the rest of the section, let Z be a lattice
$3$
-zonotope of lattice-width three. We first treat the case where the lattice-width is attained with respect to (at least) two different integer linear functionals, and then we see how the case of a single one splits into two subcases.
7.2.1 Zonotopes of lattice-width three for two different functionals
We here assume that Z is a lattice 3-zonotope of lattice-width three with respect to two (linearly independent) functionals
$f_1,f_2$
. Let us first see that there is no loss of generality in assuming that these are the first two coordinates. Think of
$f_1$
and
$f_2$
as elements of the dual lattice
$(\mathbb {Z}^3)^*$
. Since
$$\begin{align*}w(Z, \lambda_1 f_1+ \lambda_2 f_2) \le \lambda_1 w(Z, f_1) + \lambda_2 w(Z, f_2), \end{align*}$$
there is no loss of generality in assuming that the triangle formed by
$f_1$
,
$f_2$
and the origin contains no other lattice points. Equivalently, this triangle is unimodular, hence part of a lattice basis (see, for instance, [Reference Gruber and Lekkerkerker18, Chapter 1]). Then, a change of basis sends
$f_1$
and
$f_2$
to the first two coordinates.
Then, if we let
$\pi :\mathbb {R}^3\to \mathbb {R}^2$
be the projection forgetting the third coordinate, we have that
$Z':=\pi (Z)$
is a two-dimensional lattice zonotope of lattice-width three that fits in the square
$[0,3]^2$
.
Proposition 7.4. Let Z be a lattice
$3$
-zonotope of width three attaining its width w.r.t. two linearly independent functionals, and with
$\mu (Z) \ge \frac 35$
. Assume that the projection
$Z'=\pi (Z)$
is contained in the square
$[0,3]^2$
but is different from the parallelogram
$P_{2,5}$
of Theorem 6.3.
Then
$$\begin{align*}\operatorname{\mathrm{vol}}(Z) \le \frac{5\operatorname{\mathrm{vol}}(Z')}{3-5\mu(Z')} \le 10\operatorname{\mathrm{vol}}(Z'). \end{align*}$$
Proof. The width of
$Z'$
is also at least three, since a functional giving a certain width to
$Z'$
lifts to a functional with the same width on Z. Hence, the fact that
$Z'$
does not equal
$P_{2,5}$
implies, by Theorem 6.3, that
$\mu (Z') \le 1/2$
.
Let h denote the maximum length among the fibres
$\{\pi ^{-1}( \mathbf {x}) \cap Z :\mathbf {x}\in Z'\}$
, and let
$\mathbf {x} \in Z'$
be a point attaining this maximum h. Then, for each
$k \in (0,1]$
, we find that the zonotope
$Z^{\prime }_k:=\mathbf {x}+ k (Z'-\mathbf {x})\subseteq Z'$
has
$\mu (Z^{\prime }_k) = \mu (Z')/k$
and for every
$\mathbf {y} \in Z^{\prime }_k$
the length of
$\pi ^{-1}( \mathbf {y})$
is at least
$(1-k) h$
.
Taking
$k= 5\mu (Z')/3 \leq 5/6$
, we have that
$\mu (Z^{\prime }_k) = 3/5$
and that every fibre over a point
$\mathbf {y} \in Z^{\prime }_k$
has length at least
$\frac {3-5\mu (Z')}{3}h$
. By Proposition 2.8,
$\mu (Z) \ge 3/5$
and
$\mu (Z') < 3/5$
implies that some
$\mathbf {y}\in Z^{\prime }_k$
must have length bounded by
$5/3$
, that is,
$$\begin{align*}\frac{3-5\mu(Z')}{3}h \le 5/3 \quad\Rightarrow \quad h \le \frac{5}{3-5\mu(Z')} \leq 10 \,, \end{align*}$$
also using
$\mu (Z') \leq 1/2$
. Since, obviously,
$\operatorname {\mathrm {vol}}(Z) \le h \operatorname {\mathrm {vol}}(Z')$
, the result follows.
Corollary 7.5. Let Z be a lattice
$3$
-zonotope that has lattice-width three w.r.t. two linearly independent functionals. If
$\mu (Z) \ge \frac 35$
, then
$ \operatorname {\mathrm {vol}}(Z) \le 80, $
unless Z is a parallelepiped projecting to
$P_{2,5}$
.
Proof. If Z projects to
$P_{2,5}$
, the fact that
$P_{2,5}$
is a parallelogram with primitive generators implies that Z is a parallelepiped. Since we assume this does not happen, we can apply the bound of Proposition 7.4. Let
$Z'=\pi (Z)$
, as in that statement. If
$Z'=[0,3]^2$
, then
$\operatorname {\mathrm {vol}}(Z')=9$
and
$\mu (Z')=1/3$
, so Proposition 7.4 gives
$\operatorname {\mathrm {vol}}(Z) \le \frac {45}{3-\frac 53} = 33.75$
. If
$Z' \ne [0,3]^2$
, then
$\operatorname {\mathrm {vol}}(Z') \le 8$
and the same result gives
$\operatorname {\mathrm {vol}}(Z) \le 10 \operatorname {\mathrm {vol}}(Z') \leq 80$
.
7.2.2 Zonotopes of lattice-width three for a unique functional
We first prove some technical lemmas. In the first one, we say that a polytope P is centrally symmetric if there is a point
$\mathbf {x} \in P$
such that
$P - \mathbf {x} = \mathbf {x} - P$
. For example, all zonotopes are centrally symmetric, but the lemma holds without the zonotopal assumption.
Lemma 7.6. Let P be a centrally symmetric lattice
$3$
-polytope of lattice-width three with respect to a unique lattice functional f. We assume
$f(P)=[0,3]$
and denote
$P_k:= P \cap f^{-1}(k)$
, for each
$k\in [0,3]$
.
-
1.
$\mu (P_k) \le 2 \mu (P_1)$
, for every
$k\in [2/3,7/3]$
. -
2. If
$P_1$
is a lattice polytope, then where
$$\begin{align*}w_{f}(P) = w(P_1), \end{align*}$$
$w_{f}(P)$
denotes the minimum width of P with respect to lattice functionals not proportional to f.
-
3. Assume that P is a zonotope. Then,
-
(a)
$\operatorname {\mathrm {vol}}(P) \le 3 \operatorname {\mathrm {vol}}(P_1)$
, and -
(b) if, moreover, P has at most one generator
$\mathbf {u}$
orthogonal to f, that is, with
$f(\mathbf {u})=0$
, then
$\operatorname {\mathrm {vol}}(P) = 2 \operatorname {\mathrm {vol}}(P_1)$
.
-
Proof. Let us start with part (1):
-
• If
$k\in [2/3,1]$
, then
$$\begin{align*}k P_1 \subseteq (1-k)P_0 + k P_1 \subseteq P_k \quad \Rightarrow \quad \mu(P_k) \le \frac1{k}\mu(P_1) \le \frac32 \mu(P_1) < 2 \mu(P_1). \end{align*}$$
-
• If
$k\in [1, 3/2]$
, then where equality can possibly hold only for
$$\begin{align*}(2-k) P_1 \subseteq (2-k)P_1 + (k-1) P_2 \subseteq P_k \quad \Rightarrow \quad \mu(P_k) \le \frac1{2-k}\mu(P_1) \le 2 \mu(P_1), \end{align*}$$
$k = 3/2$
.
-
• If
$k \in [3/2,7/3]$
, then by central symmetry of P around a point
$\mathbf {x} \in P$
with
$f(\mathbf {x}) = 3/2$
, we get
$\mu (P_k) = \mu (P_{3-k}) \leq 2 \mu (P_1)$
.
Let us now prove part (2). That
$w_{f}(P) \ge w(P_1)$
is clear: every lattice functional
$f'$
not proportional to f restricts to a nonzero lattice functional on
$P_1$
, so the width of
$P_1$
is smaller than or equal to the width of P with respect to
$f'$
.
For the converse, let us assume without loss of generality that f equals the third coordinate, so that we identify each
$P_k\subseteq \mathbb {R}^2\times \{k\}$
with its projection along that coordinate.
Let
$g: \mathbb {R}^2 \to \mathbb {R}$
be a lattice functional attaining the lattice-width of
$P_1$
. By central symmetry of P and the hypothesis on
$P_1$
being a lattice polytope,
$g(P_1)$
and
$g(P_2)$
are integer segments of the same length, equal to
$w := w(P_1)$
. Let m be the integer with
$$\begin{align*}g(P_2) = m + g(P_1) \end{align*}$$
and consider the functional
$$\begin{align*}f'(x_1,x_2,x_3) := g(x_1,x_2) - m x_3. \end{align*}$$
Let S be the segment
$S:=g(P_1) - m$
. By construction,
$f'(P_1)= f'(P_2)=S$
; and we only need to prove
$f'(P)\subseteq S$
and get
$w_{f}(P) \le \operatorname {\mathrm {length}}(f'(P)) \le \operatorname {\mathrm {length}}(S) = w(P_1)$
.
Claim.
$f'(P_1)= f'(P_2)=S$
implies
$f'(P)\subseteq S$
.
Consider the 2-dimensional image
$Q:= F(P)$
under the map
$$\begin{align*}F: \mathbb{R}^3 \to \mathbb{R}^2 \quad \textrm{ with } \quad \mathbf{p} \mapsto (f'(\mathbf{p}), f(\mathbf{p})). \end{align*}$$
Q is a 2-dimensional lattice polytope contained in
$\mathbb {R}\times [0,3]$
and with
$Q_1= Q_2 =S$
, where we define
$Q_k := Q \cap f^{-1}(k)$
analogously to
$P_k$
. This implies
$Q \subseteq S \times [0,3]$
, that is,
$f'(P) \subseteq S$
, as desired.
To prove part (3) we first claim a similar result in dimension two:
Claim. Let
$P'$
be a lattice
$2$
-zonotope of lattice-width three with respect to a lattice functional
$\bar f$
, with
$\bar f(P')=[0,3]$
and denote
$P^{\prime }_k:= P' \cap {\bar f}^{-1}(k)$
. Then,
$\operatorname {\mathrm {vol}}(P') \le 3 \operatorname {\mathrm {vol}}(P^{\prime }_1)$
, and if, moreover,
$P^{\prime }_0$
is a single point, then
$\operatorname {\mathrm {vol}}(P') = 2 \operatorname {\mathrm {vol}}(P^{\prime }_1)$
.
To prove it, consider the parallelogram
$P":=P'\cap {\bar f}^{-1}([1,2])$
.
$P'$
is contained in the parallelogram obtained by extending
$P"$
along the edges not orthogonal to
$f'$
, so
$\operatorname {\mathrm {vol}}(P') \le 3 \operatorname {\mathrm {vol}}(P") = 3\operatorname {\mathrm {vol}}(P^{\prime }_1)$
. If
$P^{\prime }_0$
(and hence
$P^{\prime }_3$
) is a single point, then
$P' \setminus P"$
is the union of two triangles of area
$\frac 12\operatorname {\mathrm {vol}}(P")$
, thus
$\operatorname {\mathrm {vol}}(P') = 2 \operatorname {\mathrm {vol}}(P") = 2\operatorname {\mathrm {vol}}(P^{\prime }_1)$
.
We now use induction on the number m of generators of the zonotope P orthogonal to f, with base case
$m=0$
. Since the (absolute) values of f on generators not orthogonal to f add up to three,
$m=0$
implies that P has only three generators and f takes value
$1$
in each of them. The volume of P is then the determinant of the three generators and the area of the triangle
$P_1$
is half the determinant, so statement (b) holds in this case.
For the induction step, let
$\mathbf {u}$
be a generator orthogonal to f. Let Q be the (perhaps two-dimensional) zonotope generated by the remaining generators of P, and let
$P'$
be the projection of P along the direction of
$\mathbf {u}$
. Then,
$$ \begin{align} \operatorname{\mathrm{vol}}(P) &= \operatorname{\mathrm{vol}}(Q) + \ell(\mathbf{u}) \operatorname{\mathrm{vol}}(P'), \end{align} $$
where
$\ell (\mathbf {u})$
denotes lattice length (see Section 3.1). Similarly, with the obvious notations,
$$ \begin{align} \operatorname{\mathrm{vol}}(P_1) &= \operatorname{\mathrm{vol}}(Q_1) + \ell(\mathbf{u}) \operatorname{\mathrm{vol}}(P^{\prime}_1). \end{align} $$
Notice that, if Q is two-dimensional, then
$\operatorname {\mathrm {vol}}(Q)=\operatorname {\mathrm {vol}}(Q_1)=0$
. Now, if
$\mathbf {u}$
is the only generator orthogonal to f, then
$P^{\prime }_0$
is a single point, so that
$\operatorname {\mathrm {vol}}(P') = 2 \operatorname {\mathrm {vol}}(P^{\prime }_1)$
by the claim, and the induction hypothesis is the case
$m=0$
implying
$\operatorname {\mathrm {vol}}(Q) = 2 \operatorname {\mathrm {vol}}(Q_1)$
. Combining this with the identities (7.1) and (7.2) proves statement (b). If
$m \geq 2$
, we have
$\operatorname {\mathrm {vol}}(P') \le 3 \operatorname {\mathrm {vol}}(P^{\prime }_1)$
by the claim and
$\operatorname {\mathrm {vol}}(Q) \leq 3 \operatorname {\mathrm {vol}}(Q_1)$
by induction hypothesis. Again combining this with (7.1) and (7.2) then proves statement (a).
Now, let Z be a lattice
$3$
-zonotope of lattice-width three attained by a unique functional f. As before, we denote
$Z_k = Z \cap f^{-1}(k)$
below, for
$k \in \mathbb {R}$
. Since the width of Z for the functional f equals the sum of the (absolute) values of f on the generators, lattice-width three implies one of the following possibilities for the generators of Z that are not orthogonal to f:
-
1. There are three of them, and f takes value
$1$
on each of the three. -
2. There are two of them, and f takes values
$1$
and
$2$
on them, respectively. -
3. There is a single one, and f takes value
$3$
on it.
The last case is easy to discard:
Proposition 7.7 (Case (3) for f)
If Z is a lattice 3-zonotope of lattice-width three with respect to a unique functional f and has exactly one generator not orthogonal to f, then
$\mu (Z) < 3/5$
.
Proof. Assume that the linear functional f is the third coordinate and hence the nonorthogonal generator is of the form
$\mathbf {u}=(p,q,3)$
. By applying the unimodular transformation
$$\begin{align*}\begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix} \mapsto \begin{pmatrix} x_1-{\lfloor{{p}/3}\rfloor} x_3 \\ x_2-{\lfloor{{q}/3}\rfloor} x_3 \\ x_3 \end{pmatrix} \end{align*}$$
there is no loss of generality in assuming that
$p,q\in \{0,1,2\}$
.
To seek a contradiction suppose that
$\mu (Z) \ge 3/5$
. Since
$Z=Z_0 + {\left [{\mathbf {0},\mathbf {u}}\right ]}$
, Proposition 2.8 gives
$$\begin{align*}\frac35 \le \mu(Z) \le \max\left\{\mu(Z_0),\frac13\right\}, \end{align*}$$
implying that
$\mu (Z_0)>3/5$
. Then, Theorem 6.3 implies that
$Z_0$
has lattice-width one or two, since
$Z_0 =P_{2,5}$
would imply Z to have width two with respect to two different functionals.
We can assume the lattice-width
$w\le 2$
of
$Z_0$
to be attained with respect to the first coordinate, that is,
$Z_0 \subseteq [0,w]\times \mathbb {R}\times \{0\}$
. Then, the lattice-width of Z with respect to the first coordinate is
$w+p$
, which is at most
$3$
except if
$w=p=2$
. But in that case Z has width three with respect to
$f'(\mathbf {x}) = x_1-x_3$
, since
$f'(Z_0)=[0,2]$
and
$f'(Z) = f'(Z_0 + [\mathbf {0},\mathbf {u}]) =[-1,2]$
. The contradiction is that in both cases we have a second functional giving Z width three.
Case (1) is also easy, since in this case
$Z_1$
is a lattice polytope and we can readily apply to Z the three parts of Lemma 7.6.
Proposition 7.8 (Case (1) for f)
Let Z be a lattice
$3$
-zonotope of lattice-width three with respect to a single functional f and with
$\mu (Z) \ge 3/5$
. If Z has three generators not orthogonal to f, then
$$\begin{align*}\operatorname{\mathrm{vol}}(Z_1) \le 40. \end{align*}$$
Proof. By Proposition 2.8,
$\mu (Z) \ge 3/5$
implies that there is a
$k\in [2/3, 7/3]$
with
$\mu (Z_k) \ge 3/5$
. Part (1) of Lemma 7.6 then gives
$\mu (Z_1) \ge 3/10$
.
Since f is the only functional giving width three to Z and
$Z_1$
is a lattice polytope, part (2) of Lemma 7.6 says that
$Z_1$
has lattice-width at least four, so Corollary 6.1 with
$\mu w \ge 6/5$
implies
$$\begin{align*}\operatorname{\mathrm{vol}}\left(Z_1\right) \le \frac{16}{2/5} = 40, \end{align*}$$
as claimed.
Corollary 7.9 (Case (1) for f)
Let Z be a lattice
$3$
-zonotope of lattice-width three attained by a unique functional f and with
$\mu (Z)\ge 3/5$
. If Z has three generators not orthogonal to f, then
$ \operatorname {\mathrm {vol}}(Z) \le 120$
. If, moreover, Z is an sLRZ, then
$\operatorname {\mathrm {vol}}(Z) \le 80$
.
Proof. The bounds follow from Proposition 7.8 and part (3) of Lemma 7.6. In the second bound we use that an sLRZ of dimension three has four generators. Since three of them are not orthogonal to f only one can be orthogonal.
For Case (2) we have a stronger form of part (1) and a variation of part (2) of Lemma 7.6, since
$Z_1$
may not be a lattice polytope.
Lemma 7.10. Let P be a lattice
$3$
-zonotope of lattice-width three with respect to a unique functional f, and suppose that it has two generators
$\mathbf {u}_1$
and
$\mathbf {u}_2$
with
$f(\mathbf {u}_1)=1$
and
$f(\mathbf {u}_2)=2$
. Assume further that
$f(P) = [0,3]$
. Then, with the notations of Lemma 7.6, it holds
-
1.
$\mu (P_k) \le \frac 32 \mu (P_1)$
, for every
$k\in [2/3,7/3]$
, and -
2.
$$\begin{align*}w_{f}(P) = \lceil w(P_1)\rceil \le w(P_1) + \frac12. \end{align*}$$
Proof. To make things concrete, assume without loss of generality that f equals the third coordinate and let
$$\begin{align*}\mathbf{u}_1=(\mathbf{p},1), \quad \mathbf{u}_2=(\mathbf{q},2), \end{align*}$$
for some
$\mathbf {p}, \mathbf {q} \in \mathbb {Z}^2$
. Calling
$T\subseteq \mathbb {R}^2$
the segment with endpoints
$\mathbf {p}$
and
$\frac 12\mathbf {q}$
, we have that
$$\begin{align*}P_1 = P_0 + (T \times \{1\}) \quad \text{ and }\quad P_2 = \frac12 \mathbf{q} + P_1, \end{align*}$$
where the last equality uses that
$P_1$
is a (perhaps nonlattice) zonotope, hence centrally symmetric. In fact, for all
$k\in [1,2]$
, we now have that
$P_k$
is a translation of
$P_1$
by the vector
$\frac {k-1}2 \mathbf {q}$
. This implies that
$\mu (P_k) = \mu (P_1)$
for
$k\in [1,2]$
, and the argument in the proof of Lemma 7.6 gave
$\mu (P_k) \le \frac 32 \mu (P_1)$
for
$k\in [2/3, 1) \cup (2,7/3]$
. This proves part (1).
For part (2), as in the proof of part (2) of Lemma 7.6 we have that
$w_{f}(P) \ge w(P_1)$
is obvious, and for the converse we let
$g: \mathbb {R}^2 \to \mathbb {R}$
be a lattice functional attaining the lattice-width of
$P_1$
. If
$g(P_1)$
(hence
$g(P_2)$
, by central symmetry) are lattice segments then all we said in the proof of Lemma 7.6 remains valid, and we get
$$\begin{align*}w_{f}(P) = w(P_1). \end{align*}$$
So, suppose that
$g(P_1)$
is not a lattice segment. Since one endpoint of T is a lattice point and the other is half-integral, we have that one endpoint of
$g(P_1)$
is an integer and the other a half-integer. Without loss of generality assume
$g(P_1)=[a,b-1/2]$
, with
$a < b$
. Let
$\mathbf {p}_1, \mathbf {p}_2 \in \mathbb {Z}^2$
be lattice points with
$g(\mathbf {p}_1) = g(\mathbf {p}_2) =b$
and that lie sufficiently far from each other in opposite directions on the line
$f^{-1}(1) \cap (g^{-1}(b) \times \{1\})$
. This implies that
$$\begin{align*}P^{\prime}_1:= \operatorname{\mathrm{conv}}\left(P_1 \cup \{(\mathbf{p}_1,1), (\mathbf{p}_2,1)\}\right) \end{align*}$$
is a lattice polytope containing
$P_1$
, and
$$\begin{align*}P':= \operatorname{\mathrm{conv}}(P \cup \{(\mathbf{p}_1,1), (\mathbf{p}_2,1) , (\mathbf{x}- \mathbf{p}_1,2), (\mathbf{x} - \mathbf{p}_2,2) \}), \end{align*}$$
where
$\frac 12\mathbf {x}$
is the (half-integral) centre of P, is a centrally symmetric lattice polytope containing P and with
$P'\cap f^{-1}(1) = P^{\prime }_1$
. Also, by construction,
$g(P^{\prime }_1)= [a,b]$
so its width equals
$$\begin{align*}b-a =\lceil w(P_1)\rceil = w(P_1) + \frac12. \end{align*}$$
The result follows from applying part (2) of Lemma 7.6 to
$P'$
.
Corollary 7.11 (Case (2) for f)
Let Z be a lattice
$3$
-zonotope of lattice-width three with respect to a single functional f and with
$\mu (Z) \geq 3/5$
. If Z has exactly two generators not orthogonal to f, then
$$\begin{align*}\operatorname{\mathrm{vol}}(Z_1) \le \frac{245}{16} , \end{align*}$$
hence
$$\begin{align*}\operatorname{\mathrm{vol}}(Z) \le 3\cdot \frac{245}{16} < 46. \end{align*}$$
Proof. The second inequality follows from the first one by part (3) of Lemma 7.6.
For the first inequality we simply modify the proof of Proposition 7.8 as indicated by Lemma 7.10:
By Proposition 2.8,
$\mu (Z) \ge 3/5$
implies that there is a
$k\in [2/3, 7/3]$
with
$\mu (Z_k) \ge 3/5$
. Part (1) of Lemma 7.10 then gives
$\mu (Z_1) \ge 2/5$
.
Since f is the only functional giving width three to Z, part (2) of Lemma 7.10 says that
$Z_1$
has width at least
$7/2$
, so Corollary 6.1 with
$\mu w \ge 7/5$
implies
$$\begin{align*}\operatorname{\mathrm{vol}}\left(Z_1\right) \le \frac{49/4}{4/5} = \frac{245}{16}, \end{align*}$$
as claimed.
Acknowledgments
The authors would like to thank the two referees, whose valuable remarks helped improve the appearance of the paper.
Competing interest
The authors have no competing interests to declare.
Financial support
R. D. Malikiosis was granted a renewed research stay by the Alexander von Humboldt Foundation for the completion of this project; R. D. Malikiosis also acknowledges that this project is carried out within the framework of the National Recovery and Resilience Plan Greece 2.0, funded by the European Union, NextGenerationEU (Implementation body: HFRI, Project Name: HANTADS, No. 14770).
Work of F. Santos is partially supported by grant PID2022-137283NB-C21 funded by MCIN/AEI/10.13039/501100011033.
Open access
