# A Reverse Minkowski Theorem

Oded Regev
Courant Institute of Mathematical Sciences, New York University.Supported by
the Simons Collaboration on Algorithms and Geometry and by the National
Science Foundation (NSF) under Grant No. CCF-1320188. Any opinions, findings,
and conclusions or recommendations expressed in this material are those of the
authors and do not necessarily reflect the views of the NSF. Noah Stephens-
Davidowitz11footnotemark: 1
<EMAIL_ADDRESS>Supported by the National Science Foundation (NSF) under
Grant No. CCF-1320188, and the Defense Advanced Research Projects Agency
(DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236.
Part of this work was done while visiting Chris Peikert at the University of
Michigan.

###### Abstract

We prove a conjecture due to Dadush, showing that if
$\mathcal{L}\subset\mathbb{R}^{n}$ is a lattice such that
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$, then

$\sum_{\boldsymbol{y}\in\mathcal{L}}e^{-t^{2}\|\boldsymbol{y}\|^{2}}\leq
3/2\;,$

where $t:=10(\log n+2)$. From this we also derive bounds on the number of
short lattice vectors and on the covering radius.

##  1 Introduction

A lattice $\mathcal{L}\subset\mathbb{R}^{n}$ is the set of integer linear
combinations of linearly independent basis vectors
$\mathbf{B}=(\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n})$. The determinant
of the lattice, $\det(\mathcal{L})=|\det(\mathbf{B})|$, is a measure of its
global density in the sense that

$\det(\mathcal{L})=\lim_{r\rightarrow\infty}\frac{\operatorname{vol}(rB_{2}^{n})}{|\mathcal{L}\cap
rB_{2}^{n}|}\;,$

where $rB_{2}^{n}$ denotes the closed Euclidean ball of radius $r>0$, whose
volume is $(\pi n)^{-1/2}(2\pi er^{2}/n)^{n/2}(1+o(1))$. (Here and elsewhere,
we write $o(1)$ for an arbitrary function that approaches zero as the
dimension $n$ approaches infinity.)

Minkowski’s celebrated first theorem shows that a lattice with small
determinant must have short non-zero vectors [Min10]. This is one of the
foundational results in the study of lattices and the geometry of numbers, and
it has innumerable applications. We consider the following point-counting form
of this theorem due to Blichfeldt and van der Corput,111They actually showed
the slightly stronger bound $|\mathcal{L}\cap rB_{2}^{n}|\geq 2\lfloor
2^{-n}\cdot\operatorname{vol}(rB_{2}^{n})\rfloor+1$ and considered arbitrary
norms, not just $\ell_{2}$. (See, e.g., [GL87, Thm. 1 of Ch. 2, Sec. 7].)
which says that a lattice with small determinant must have _many_ short
points, or informally, that “global density implies local density.”

######  Theorem 1.1 ([vdC36]).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with $\det(\mathcal{L})\leq
1$ and $r>0$,

$|\mathcal{L}\cap rB_{2}^{n}|\geq
2^{-n}\cdot\operatorname{vol}(rB_{2}^{n})=\frac{1}{\sqrt{\pi
n}}\Big{(}\frac{\pi er^{2}}{2n}\Big{)}^{n/2}(1+o(1))\;.$

It is quite natural to ask whether a converse of Theorem 1.1 holds. In
particular, if a lattice has sufficiently many short points, does it
necessarily have small determinant? Does local density imply global density?

It is easy to see that the answer is actually no. Consider, for example, the
lattice generated by the vectors $(1/t,0)$ and $(0,t^{2})$ for some
arbitrarily large $t$. This lattice has at least $2\lfloor tr\rfloor+1$ points
of norm at most $r$, but it has arbitrarily large determinant $t$. Notice,
however, that this lattice contains a _sublattice_ generated by $(1/t,0)$ that
does have small determinant. This leads us to a more refined question:

> If a lattice has sufficiently many short points, does it necessarily have a
> small-determinant _sublattice_? Does local density imply global density over
> a subspace?

Equivalently, in the contrapositive, the question asks for an upper bound on
the number of lattice points in a ball given that there is no sublattice of
small determinant.

Dadush conjectured a suitably precise answer to these questions [Dad12a]. He
later studied this conjecture in depth in joint work with the first named
author [DR16]. Among other things, they showed a number of applications of the
conjecture (from computational complexity of lattice problems to Brownian
motion on flat tori) and gave some evidence for it. We refer the reader to
[DR16] for a full list of their results.

Our main result is a proof of the conjecture of Dadush, which in particular
implies the applications mentioned above.

######  Theorem 1.2 (Reverse Minkowski Theorem).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$,

$\rho_{1/t}(\mathcal{L})\leq\frac{3}{2}\;,$

where $t:=10(\log n+2)$.

Here, for a lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and $s>0$,

$\rho_{s}(\mathcal{L}):=\sum_{\boldsymbol{y}\in\mathcal{L}}e^{-\pi\|\boldsymbol{y}\|^{2}/s^{2}}\;$

is the _Gaussian mass_ of the lattice with _parameter_ $s$. This can be seen
as a smooth version of the point-counting function $r\mapsto|\mathcal{L}\cap
rB_{2}^{n}|$, with the parameter $s$ playing the role of the radius $r$, and
it arises naturally in a number of contexts (often in the form of the theta
function, $\Theta_{\mathcal{L}}(iy):=\rho_{1/\sqrt{y}}(\mathcal{L})$). In
particular, Theorem 1.2 immediately implies that $|\mathcal{L}\cap
rB_{2}^{n}|\leq 3e^{\pi t^{2}r^{2}}/2$ for any radius $r>0$.

We can equivalently formulate Theorem 1.2 in terms of the parameter

$\eta^{*}(\mathcal{L}):=\inf\\{t\ :\ \rho_{1/t}(\mathcal{L})\leq 3/2\\}\;$

(known as the smoothing parameter of the dual lattice [MR07]). Namely, by
scaling $\mathcal{L}$ so that

$\eta_{\det}(\mathcal{L}):=\max_{\mathcal{L}^{\prime}\subseteq\mathcal{L}}\det(\mathcal{L}^{\prime})^{-1/\operatorname{rank}(\mathcal{L}^{\prime})}\;$

is equal to one, Theorem 1.2 shows that

$\frac{2}{3}\cdot\eta_{\det}(\mathcal{L})\leq\eta^{*}(\mathcal{L})\leq 10(\log
n+2)\cdot\eta_{\det}(\mathcal{L})\;,$ (1)

where the lower bound is an immediate consequence of the Poisson Summation
Formula (Eq. (3)). For example, $\eta^{*}(\mathbb{Z}^{n})=\sqrt{\log
n/\pi}+o(1)$ and $\eta_{\det}(\mathbb{Z}^{n})=1$.

In Section 5, we extend Theorem 1.2 to obtain a bound on the Gaussian mass for
all parameters, as follows.

######  Theorem 1.3.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$,

  1. 1.

$\rho_{s}(\mathcal{L})\leq 1+e^{-\pi(1/s^{2}-t^{2})}/2$ for any $s\leq 1/t$;

  2. 2.

$\rho_{s}(\mathcal{L})\leq(Cst)^{n/2}$ for any $1/t<s<t$ and some universal
constant $C>1$; and

  3. 3.

$\rho_{s}(\mathcal{L})\leq 2s^{n}$ for any $s\geq t$,

where $t:=10(\log n+2)$.

Theorem 1.3 implies the following point-counting bounds. (See Section 5 for
the proof.)

######  Corollary 1.4.

For every lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$, and every shift vector
$\boldsymbol{u}\in\mathbb{R}^{n}$,

  1. 1.

for any $r\geq 1$, $|\mathcal{L}\cap(rB_{2}^{n}+\boldsymbol{u})|\leq 3e^{\pi
t^{2}r^{2}}/2$;

  2. 2.

for any $\sqrt{n/(2\pi)}\cdot t^{-1}\leq r\leq\sqrt{n/(2\pi)}\cdot t$,
$|\mathcal{L}\cap(rB_{2}^{n}+\boldsymbol{u})|\leq(Ctr/\sqrt{n})^{n/2}$ for
some universal constant $C>0$; and

  3. 3.

for any $r\geq\sqrt{n/(2\pi)}\cdot t$,
$|\mathcal{L}\cap(rB_{2}^{n}+\boldsymbol{u})|\leq 2(2\pi er^{2}/n)^{n/2}$,

where $t:=10(\log n+2)$.

In Section 8, we discuss the tightness of Theorem 1.3 and Corollary 1.4.

###  1.1 Approximation to the covering radius

The _covering radius_ $\mu(\mathcal{L})$ of a lattice
$\mathcal{L}\subset\mathbb{R}^{n}$ is the maximal distance from any point in
$\mathbb{R}^{n}$ to the lattice, or equivalently, the minimum radius $r$ such
that $\mathcal{L}+rB_{2}^{n}=\mathbb{R}^{n}$. It follows from the definition
that $\mu(\mathcal{L})$ must be at least the radius of a ball of volume
$\det(\mathcal{L})$, which is at least $\sqrt{n/(2\pi
e)}\det(\mathcal{L})^{1/n}$. By considering projections, Kannan and Lovász
[KL88] improved this lower bound, as follows. Let
$\pi_{W^{\perp}}(\mathcal{L})$ be the projection of the lattice onto the space
$W^{\perp}$ orthogonal to some _lattice subspace_ $W\subset\mathbb{R}^{n}$—a
subspace spanned by $k<n$ linearly independent lattice vectors.222The
projection $\pi_{W^{\perp}}(\mathcal{L})$ is a lattice if and only if $W$ is a
lattice subspace. Then clearly
$\mu(\mathcal{L})\geq\mu(\pi_{W^{\perp}}(\mathcal{L}))$, and the latter is at
least $(\dim(W^{\perp})/(2\pi
e))^{1/2}\cdot\det(\pi_{W^{\perp}}(\mathcal{L}))^{1/\dim(W^{\perp})}$. So, we
obtain the lower bound

$\mu(\mathcal{L})\geq\frac{1}{\sqrt{2\pi e}}\cdot\mu_{\det}(\mathcal{L})\;,$

where

$\displaystyle\mu_{\det}(\mathcal{L})$
$\displaystyle:=\max_{W\subset\mathbb{R}^{n}}\sqrt{\dim(W^{\perp})}\cdot\det(\pi_{W^{\perp}}(\mathcal{L}))^{\frac{1}{\dim(W^{\perp})}}$
$\displaystyle=\max_{\mathcal{M}\subseteq\mathcal{L}^{*}}\sqrt{\operatorname{rank}(\mathcal{M})}\cdot\det(\mathcal{M})^{-\frac{1}{\operatorname{rank}(\mathcal{M})}}\;,$

with the first maximum taken over lattice subspaces $W\subset\mathbb{R}^{n}$
and $\mathcal{L}^{*}$ being the dual lattice. Kannan and Lovász also observed
the upper bound

$\mu(\mathcal{L})\leq C\sqrt{n}\cdot\mu_{\det}(\mathcal{L})\;$

(see [DR16, Theorem 11.1] for a proof), and asked whether a better upper bound
could be found.333They also proved similar bounds for arbitrary norms [KL88,
Corollary 3.11]. In Section 6, we use Theorem 1.2 to derive the following
improved bound.

######  Theorem 1.5 (Covering-radius approximation).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\frac{1}{\sqrt{2\pi e}}\cdot\mu_{\det}(\mathcal{L})\leq\mu(\mathcal{L})\leq
10(\log n+10)^{3/2}\cdot\mu_{\det}(\mathcal{L})\;.$ (2)

We emphasize that Dadush and Regev [DR16] already proved that Theorem 1.5
(with slightly weaker parameters) would follow from a proof of Theorem 1.2.
Although our proof is shorter and achieves slightly better parameters, it is
conceptually similar to the one in [DR16].

We note that the specific polylogarithmic factor that we obtain is likely not
optimal. In fact, in Theorem 6.8 we prove a bound similar to that in Eq. (2)
that replaces the factor $10(\log n+10)^{3/2}$ by $C\sqrt{\log n}$, assuming
the celebrated Slicing Conjecture [Bou91, Kla06]. However, it is not difficult
to show that this factor cannot be smaller than $\sqrt{\log
n/(4e)}+o(1)$.444Consider the lattice $\mathcal{L}$ generated by
$(\boldsymbol{e}_{1},\boldsymbol{e}_{2}/2,2\boldsymbol{e}_{3}/3^{3/2},\ldots,(n-1)^{(n-1)/2}\boldsymbol{e}_{n}/n^{n/2})$.
It is not difficult to verify that $\mu_{\det}(\mathcal{L})=1$, but
$\displaystyle\mu(\mathcal{L})^{2}=1/4+\sum_{k=2}^{n}\frac{(k-1)^{k-1}}{4k^{k}}=1/4+\sum_{k=2}^{n}\frac{(1-1/k)^{k}}{4(k-1)}=\sum_{k=2}^{n}\frac{1}{4e(k-1)}+O(1)=\frac{\log
n}{4e}+O(1)\;.$ Therefore, $\mu(\mathcal{L})=\sqrt{\log n/(4e)}+o(1)$.

#### Covering radius of stable lattices and Minkowski’s Conjecture.

We say that a lattice $\mathcal{L}\subset\mathbb{R}^{n}$ is _stable_ if
$\det(\mathcal{L})=1$ and $\det(\mathcal{L}^{\prime})\geq 1$ for all
sublattices $\mathcal{L}^{\prime}\subseteq\mathcal{L}$. Stable lattices arise
in a number of contexts [HN75, Stu76, Gra84] and they play an important role
in the sequel. Shapira and Weiss showed that a tight bound of
$\mu(\mathcal{L})\leq\mu(\mathbb{Z}^{n})=\sqrt{n}/2$ on the covering radius of
stable lattices would imply a well-known conjecture attributed to Minkowski
[SW16]. (See also [Sol16].) We do not manage to prove such a tight bound, but
en route to proving Theorem 1.5 we do show that $\mu(\mathcal{L})\leq
4\sqrt{n}(\log n+10)$ for all stable lattices. (See Theorem 6.2.) We also
observe that a very strong resolution to the Slicing Conjecture would yield
the desired tight bound, when combined with a recent result due to Magazinov
[Mag17]. (See Theorem 6.7 and the discussion afterwards.)

###  1.2 An optimal bound on the Gaussian mass for “extreme” parameters

It is tempting to ask whether
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$ for any lattice
$\mathcal{L}\subset\mathbb{R}^{n}$ such that $\det(\mathcal{L}^{\prime})\geq
1$ for all sublattices $\mathcal{L}^{\prime}\subseteq\mathcal{L}$ and any
parameter $s>0$. (See Section 1.5.) The next theorem shows that indeed
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$ for such lattices, but
only for “extremely low” or “extremely high” parameters $s$. (See Section 7
for the proof.)

######  Theorem 1.6.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ such that
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$ and parameter $s>0$ such that
either $s\leq\sqrt{2\pi/(n+2)}$ or $s\geq\sqrt{(n+2)/(2\pi)}$, we have
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$.

We hope that the proof of Theorem 1.6 might provide some hints as to how to
extend it to all parameters $s$.

###  1.3 Proof overview

In this section, we give a high-level overview of the proof of Theorem 1.2.

#### Bounding the mass of stable lattices.

Recall that a lattice $\mathcal{L}$ is _stable_ if $\det(\mathcal{L})=1$ and
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$. I.e., stable lattices are
determinant-one lattices that satisfy the assumption in Theorem 1.2. In this
proof overview, we focus on bounding the Gaussian mass $\rho_{s}(\mathcal{L})$
of stable lattices $\mathcal{L}$. As it turns out, the general case then
follows easily.

Crucially, the stable lattices form a compact subset of the set of
determinant-one lattices, so that the continuous function
$\rho_{s}(\mathcal{L})$ must attain a global maximum over the set of stable
lattices. We may therefore restrict our attention to a lattice that
corresponds to this global maximum. If this lattice is on the _boundary_ of
the set of stable lattices, then it has a strict sublattice
$\mathcal{L}^{\prime}$ with determinant one. We can then “split the lattice”
at $\mathcal{L}^{\prime}$. Namely, we can replace the original lattice
$\mathcal{L}$ by the direct sum
$\mathcal{L}^{\prime}\oplus\mathcal{L}/\mathcal{L}^{\prime}$. It is not
difficult to prove that

$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathcal{L}^{\prime}\oplus\mathcal{L}/\mathcal{L}^{\prime})=\rho_{s}(\mathcal{L}^{\prime})\rho_{s}(\mathcal{L}/\mathcal{L}^{\prime})$

and that $\mathcal{L}^{\prime}$ and $\mathcal{L}/\mathcal{L}^{\prime}$ are
stable. So, we have reduced the question to a lower-dimensional one.
Therefore, if we could show that for any dimension, the global maximizer is on
the boundary, then we could use induction to show that the global maximizer of
the Gaussian mass is simply the integer lattice
$\mathbb{Z}^{n}=\mathbb{Z}\oplus\cdots\oplus\mathbb{Z}$.

Indeed, this is how we prove Theorem 1.6 (in Section 7), which shows that
$\mathbb{Z}^{n}$ has maximal Gaussian mass for certain “extreme” parameters
$s$. For such parameters, by taking the second derivative, we show that a
stable lattice cannot be a local maximum over the set of determinant-one
lattices. Therefore, the global maximizer of $\rho_{s}(\mathcal{L})$ over the
compact subset of stable lattices must be on the boundary, and we can perform
the “splitting” procedure described above to show by induction that
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$.

However, we do not know if $\rho_{s}(\mathcal{L})$ can have such stable local
maxima for other parameters. As a potential way around this issue, we could
use a natural and very elegant idea due to Shapira and Weiss [SW16]—We could
try to directly bound the value of $\rho_{s}(\mathcal{L})$ at any hypothetical
local maximum. Then, either the global maximum of $\rho_{s}(\mathcal{L})$ over
the set of stable lattices is one of these local maxima, in which case we can
apply this bound; or it is on the boundary, in which case we can “split the
lattice” as above. (Shapira and Weiss suggested using this approach to bound
the covering radius of stable lattices to resolve Minkowski’s Conjecture
[SW16]. Interestingly, local maxima of the covering radius do exist [DSV12].)

#### Enter the Voronoi cell.

Unfortunately, even bounding the value of $\rho_{s}(\mathcal{L})$ at local
maxima seems to be beyond our grasp. So, instead of working with
$\rho_{s}(\mathcal{L})$ directly, we work with a proxy for it: the Gaussian
mass of the Voronoi cell of the lattice

$\gamma_{s}(\mathcal{V}(\mathcal{L})):=\int_{\mathcal{V}(\mathcal{L})/s}e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm
d}\boldsymbol{x}\;,$

where the Voronoi cell is the set of all points that are closer to the origin
than to any other lattice vector

$\mathcal{V}(\mathcal{L}):=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\
\forall\boldsymbol{y}\in\mathcal{L},\
\|\boldsymbol{x}\|\leq\|\boldsymbol{y}-\boldsymbol{x}\|\\}\;.$

An elegant proof due to Chung, Dadush, Liu, and Peikert [CDLP13] shows that
$\rho_{s}(\mathcal{L})$ is at most $1/\gamma_{s}(\mathcal{V}(\mathcal{L}))$.
(See Lemma 4.1.) So, in order to prove an upper bound on
$\rho_{s}(\mathcal{L})$, it suffices to prove a lower bound on
$\gamma_{s}(\mathcal{V}(\mathcal{L}))$.

We accomplish this via the approach described above. I.e., we reduce the
problem to bounding the value of $\gamma_{s}(\mathcal{V}(\mathcal{L}))$ at
local minima. (Here too, we do not know whether these local minima exist.) By
comparing gradients, we then show (in Section 3) that any lattice
corresponding to a local minimum must have a Voronoi cell
$\mathcal{V}(\mathcal{L})$ such that the function
$A\mapsto\gamma_{s}(A\mathcal{V}(\mathcal{L}))$ has a critical point at
$A=I_{n}$, where $A\in\mathrm{SL}_{n}(\mathbb{R})$ ranges over all
determinant-one matrices. Using a result due to Bobkov [Bob11], which itself
follows from a deep theorem due to Cordero-Erausquin, Fradelizi, and Maurey
[CFM04],555We note in passing that one can prove Theorem 1.2 (at least up to
constants) without using this rather heavy hammer by considering local maxima
of the _$\ell$ -norm_ of the Voronoi cell instead of local minima of the
Gaussian mass of the Voronoi cell. we can show that any such critical point
must actually be a global _maximum_ of the function
$A\mapsto\gamma_{s}(A\mathcal{V}(\mathcal{L}))$. I.e., in the language of
convex geometry, the Voronoi cell is in a position that maximizes the Gaussian
mass. (Note the rather surprising jump from a presumed local minimum over the
set of determinant-one lattices to a global _maximum_ over the set of
positions of the Voronoi cell.)

Finally, we complete the proof by applying the celebrated $\ell\ell^{*}$
theorem [FT79, Lew79, Pis82]. In particular, this theorem tells us that every
convex body $K$ with $\operatorname{vol}(K)=1$ has a position
$A\in\mathrm{SL}_{n}(\mathbb{R})$ such that $\gamma_{1/t}(AK)\geq 2/3$, with
$t:=10(\log n+2)$ as in Theorem 1.2. (See Theorem 4.6.) Since the Voronoi cell
is already in a position that maximizes the mass, we must have
$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq\gamma_{1/t}(A\mathcal{V}(\mathcal{L}))\geq
2/3$. We then obtain the desired bound on $\rho_{1/t}(\mathcal{L})$ by
applying the result of [CDLP13].

###  1.4 Related work

Our main theorem was originally conjectured by Dadush [Dad12a]. Dadush
together with the first named author described several applications of the
conjecture [DR16]. In particular, they showed the connection between this
conjecture and the Kannan-Lovász-style covering-radius approximation given in
Theorem 1.5. They also used a result from convex geometry (specifically the
Milman-Pisier Theorem) as evidence for the conjecture. That theorem is related
to the $\ell\ell^{*}$ theorem that we use in our proof.

The high-level outline of our proof (in which we obtain a bound on a lattice
parameter by reducing the question to stable local extrema) is due to Shapira
and Weiss [SW16]. They showed that an important conjecture attributed to
Minkowski would follow if we could prove that $\mathbb{Z}^{n}$ has maximal
covering radius amongst all stable lattices (i.e., that the covering radius of
an $n$-dimensional stable lattice is at most $\sqrt{n}/2$). They then observed
that it would suffice to bound the covering radius of the lattices
corresponding to local maxima of the covering radius function over the set of
determinant-one lattices.

Stable lattices were introduced (in a more general context) by Harder and
Narasimhan [HN75] and by Stuhler [Stu76]. Our presentation more-or-less
follows that of Grayson [Gra84].

Counting the number of lattice points in a ball is a classical question, and a
summary of all that is known is far beyond the scope of this paper. (See,
e.g., [CS98].) In particular, much research has gone into studying the
relationship between the number of points in a ball of radius $r$ and the
determinant of the densest _one-dimensional_ sublattice, written
$\lambda_{1}(\mathcal{L})$. (I.e., $\lambda_{1}(\mathcal{L})$ is the length of
the shortest non-zero vector in the lattice.) It is easy to see that the
number of lattice points in a ball of radius $r\geq\lambda_{1}(\mathcal{L})$
is at most $(Cr/\lambda_{1}(\mathcal{L}))^{n}$, which is essentially the best
possible bound based on $\lambda_{1}(\mathcal{L})$.666Finding the exact best
possible bounds on $|\mathcal{L}\cap s\lambda_{1}(\mathcal{L})B_{2}^{n}|$ in
various regimes is a fascinating classical problem that is still an active
area of research. For example, when $s=1$, this is known as the lattice
“kissing number” problem, and the limit as $s\to\infty$ is the lattice sphere-
packing problem. See, e.g., [KL78, CS98, CK09]. We consider the densest
sublattice of any dimension (not just the densest one-dimensional sublattice)
to obtain bounds that are much stronger in many cases. (Other authors have
considered other generalizations of $\lambda_{1}(\mathcal{L})$ to derive
incomparable bounds. E.g., [Hen02].)

Many authors have considered the extrema of various lattice parameters over
the set of determinant-one lattices. Voronoi famously characterized the local
maxima of the length of the shortest non-zero vector [Vor08], and a long line
of work has gone into finding the specific global maxima in various
dimensions. (See, e.g., [CS98, CK09].) Similarly, Montgomery [Mon88] and
Sarnak and Strömbergsson [SS06] considered the minima of the Gaussian mass
$\rho_{s}(\mathcal{L})$ and closely related functions.

Informally, the results mentioned above (and almost all literature on this
topic since Minkowski) were concerned with the “best” lattices. E.g., the
largest minimum distance, the smallest covering radius, the minimal Gaussian
mass, etc. We are in some sense interested in the “worst” lattices. Thus, we
consider _maxima_ of the Gaussian mass, maxima of the covering radius (as in
[DSV12]), etc. (These questions only makes sense over a bounded subset of the
determinant-one lattices, such as the stable lattices.) Note that, while the
“best” lattices tend to have fascinating properties (see, e.g., [CS98]), in
our setting the “worst” lattice that we know of is $\mathbb{Z}^{n}$.

In recent follow-up work, Lovett and the first named author used Theorem 1.2
to give a counterexample to a very strong variant of the polynomial Frieman-
Ruzsa conjecture over the integers [LR17]. This variant was introduced by
Green (who suggested that it was likely to be false) [Gre07].

###  1.5 Directions for future work

The most obvious direction for future work is to try to obtain a better value
for $t$ in Theorem 1.2. As far as we know, the correct value could be as small
as $t=\eta^{*}(\mathbb{Z}^{n})=\sqrt{\log(n)/\pi}+o(1)$. Our proof seems to be
loose in two places: (1) Theorem 4.6, which bounds the maximal Gaussian mass
of convex bodies; and (2) the induction argument in the proof of Proposition
4.14. It seems that one would need to improve both parts of the proof to
obtain a significantly better bound.

A more ambitious goal would be to prove that $\mathbb{Z}^{n}$ is the exact
maximizer in Theorem 1.3 for all parameters $s>0$. One might try to prove this
by showing that $\rho_{s}(\mathcal{L})$ has no local maxima over the set of
determinant-one lattices for any parameter $s>0$. Alternatively, one can try
using the technique of “characterizing the local extrema” that we use to prove
Theorem 1.2. For this, we note that any local maximum of
$\rho_{s}(\mathcal{L})$ must correspond to an “isotropic” lattice
$\mathcal{L}$ in the sense that

$\sum_{\boldsymbol{y}\in\mathcal{L}}\rho_{s}(\boldsymbol{y})\boldsymbol{y}\boldsymbol{y}^{T}=\alpha\cdot
I_{n}$

for some scalar $\alpha>0$. So, it would suffice to show that
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$ for (stable) “isotropic”
lattices. Unfortunately, we do not know how to make use of this.

Recall from Eq. (1) that Theorem 1.2 gives quite a tight approximation to the
smoothing parameter $\eta^{*}(\mathcal{L})$. However, an analogous tightness
result does not hold for Theorem 1.3 and Corollary 1.4. Dadush and Regev
therefore suggested a potential refinement that depends on “the full spectrum
of dense sublattices,” $\min_{\mathcal{L}^{\prime}\subseteq\mathcal{L},\
\operatorname{rank}(\mathcal{L}^{\prime})=k}\det(\mathcal{L}^{\prime})^{1/k}$
for $k=1,\ldots,n$, rather than just
$\min_{\mathcal{L}^{\prime}\subseteq\mathcal{L}}\det(\mathcal{L}^{\prime})^{1/\operatorname{rank}(\mathcal{L}^{\prime})}$
[DR16, Section 9]. This could potentially give a tight characterization of
$|\mathcal{L}\cap rB_{2}^{n}|$ for all radii $r$ and all lattices
$\mathcal{L}\subset\mathbb{R}^{n}$.

One can also consider generalizations of Theorems 1.5 and 1.2 to arbitrary
norms, as discussed in [KL88] and [DR16, Section 9] respectively. Extending
Theorem 1.5 to arbitrary norms could potentially yield faster algorithms for
Integer Programming [Dad12b]. Unfortunately, a natural generalization of
Theorem 1.2 actually fails. (See [DR16, Section 9].)

### Acknowledgments

We are extremely grateful to Daniel Dadush for sharing his conjecture with us
and for many helpful discussions. We are also indebted to Barak Weiss for
introducing us to stable lattices and their salient properties and for telling
us about the technique of “handling the stable local maxima separately” from
his paper with Uri Shapira [SW16]. We also thank him for his help with the
proof of Proposition 6.4. We thank Bo’az Klartag for referring us to [Bob11]
and for other useful comments. The first named author thanks Prof. Volker
Kempe for his help with the two rascals.

##  2 Preliminaries

We use $c,C,C^{\prime}$ to denote arbitrary positive universal constants,
whose value might change from one occurrence to the next. Logarithms are base
$e$ unless otherwise specified. Vectors $\boldsymbol{x}\in\mathbb{R}^{n}$ are
column vectors. We write $\|\boldsymbol{x}\|$ to represent the Euclidean norm
of $\boldsymbol{x}$, and we write $I_{n}$ for the identity matrix in $n$
dimensions. For a matrix $A\in\mathbb{R}^{n\times n}$, we write $A^{T}$ for
the transpose of $A$. We write $B_{2}^{n}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}\
:\ \|\boldsymbol{x}\|\leq 1\\}$ for the Euclidean ball in $\mathbb{R}^{n}$. We
write $\pi_{S}(\boldsymbol{x})$ for the orthogonal projection of
$\boldsymbol{x}$ onto $\operatorname{span}(S)$ for some
$S\subseteq\mathbb{R}^{n}$. (E.g.,
$\pi_{\boldsymbol{y}}(\boldsymbol{x})=\langle\boldsymbol{y},\boldsymbol{x}\rangle\boldsymbol{y}/\|\boldsymbol{y}\|^{2}$.)
We write $S^{\perp}$ for the subspace of vectors orthogonal to $S$. For two
additive subgroups $S_{1}\subseteq\mathbb{R}^{n}$ and
$S_{2}\subseteq\mathbb{R}^{m}$, their direct sum $S_{1}\oplus
S_{2}\subseteq\mathbb{R}^{n+m}$ is $\\{(\boldsymbol{x},\boldsymbol{y})\
:\boldsymbol{x}\in S_{1},\boldsymbol{y}\in S_{2}\\}$.

A _convex body_ $K\subset\mathbb{R}^{n}$ is a convex compact subset of
$\mathbb{R}^{n}$ with non-empty interior. It is _symmetric_ if $-K=K$. A
_position_ of a convex body is simply $AK$ for a determinant-one matrix $A$.

###  2.1 Lattices

A _lattice_ $\mathcal{L}\subset\mathbb{R}^{n}$ of rank $d$ is the set of
integer linear combinations of linearly independent basis vectors
$\mathbf{B}:=(\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{d})$,

$\mathcal{L}=\mathcal{L}(\mathbf{B}):=\Big{\\{}\sum_{i=1}^{d}a_{i}\boldsymbol{b}_{i}\
:\ a_{i}\in\mathbb{Z}\Big{\\}}\;.$

We typically treat lattices as though they are full rank (i.e., $d=n$) by
implicitly identifying $\operatorname{span}(\mathcal{L})$ with
$\mathbb{R}^{d}$. The _dual lattice_

$\mathcal{L}^{*}:=\\{\boldsymbol{w}\in\operatorname{span}(\mathcal{L})\ :\
\forall\boldsymbol{y}\in\mathcal{L},\
\langle\boldsymbol{w},\boldsymbol{y}\rangle\in\mathbb{Z}\\}$

is the set of all vectors in the span of $\mathcal{L}$ that have integer
linear products with all lattice vectors. One can check that
$\mathcal{L}^{**}=\mathcal{L}$ and that $\mathcal{L}^{*}$ is generated by
$\mathbf{B}^{*}:=\mathbf{B}(\mathbf{B}^{T}\mathbf{B})^{-1}$.

We write

$\lambda_{1}(\mathcal{L}):=\min_{\boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}}\|\boldsymbol{y}\|$

for the length of the shortest non-zero lattice vector. The _covering radius_
is

$\mu(\mathcal{L}):=\max_{\boldsymbol{t}\in\operatorname{span}(\mathcal{L})}\min_{\boldsymbol{y}\in\mathcal{L}}\|\boldsymbol{t}-\boldsymbol{y}\|\;.$

The _determinant_ of the lattice is given by
$\det(\mathcal{L}):=\sqrt{\det(\mathbf{B}^{T}\mathbf{B})}$, or simply
$|\det(\mathbf{B})|$ in the full-rank case. One can show that the determinant
is well defined (i.e., it does not depend on the choice of basis
$\mathbf{B}$). It follows that, if $\mathcal{L}\subset\mathbb{R}^{n}$ and
$A\in\mathbb{R}^{n\times n}$ is non-singular, then
$\det(A\mathcal{L})=|\det(A)|\det(\mathcal{L})$, and that
$\det(\mathcal{L}^{*})=1/\det(\mathcal{L})$.

A _sublattice_ $\mathcal{L}^{\prime}\subseteq\mathcal{L}$ is an additive
subgroup of $\mathcal{L}$. We say that $\mathcal{L}^{\prime}$ is _primitive_
if
$\mathcal{L}^{\prime}=\mathcal{L}\cap\operatorname{span}(\mathcal{L}^{\prime})$.
For a primitive sublattice $\mathcal{L}^{\prime}\subseteq\mathcal{L}$, we
define the quotient lattice
$\mathcal{L}/\mathcal{L}^{\prime}:=\pi_{\mathcal{L}^{\prime\perp}}(\mathcal{L})$
to be the projection of $\mathcal{L}$ onto the space orthogonal to
$\mathcal{L}^{\prime}$. In particular, $\mathcal{L}/\mathcal{L}^{\prime}$ is a
lattice, and we have the identities
$(\mathcal{L}/\mathcal{L}^{\prime})^{*}=\mathcal{L}^{*}\cap\operatorname{span}(\mathcal{L}^{\prime})^{\perp}$
and
$\det(\mathcal{L}/\mathcal{L}^{\prime})=\det(\mathcal{L})/\det(\mathcal{L}^{\prime})$.

For a parameter $s>0$ and $\boldsymbol{x}\in\mathbb{R}^{n}$, we define
$\rho_{s}(\boldsymbol{x})=e^{-\pi\|\boldsymbol{x}\|^{2}/s^{2}}$. Then, for any
discrete set $A$, we define its Gaussian mass as
$\rho_{s}(A)=\sum_{\boldsymbol{x}\in A}\rho_{s}(\boldsymbol{x})$. When $s=1$,
we omit the subscript.

We recall the Poisson Summation Formula for the Gaussian mass of a lattice,
which says that

$\rho_{s}(\mathcal{L})=\frac{s^{n}}{\det(\mathcal{L})}\cdot\rho_{1/s}(\mathcal{L}^{*})$
(3)

for any $s>0$ and (full-rank) lattice $\mathcal{L}\subset\mathbb{R}^{n}$.

######  Lemma 2.1 ([Ban93, Lemma 1.5]).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, shift vector
$\boldsymbol{u}\in\mathbb{R}^{n}$, and any $r\geq 1/\sqrt{2\pi}$,

$\rho((\mathcal{L}-\boldsymbol{u})\setminus
r\sqrt{n}B_{2}^{n})\leq\big{(}\sqrt{2\pi er^{2}}e^{-\pi
r^{2}}\big{)}^{n}\cdot\rho(\mathcal{L})\;.$

The following claim is an immediate consequence of the Poisson Summation
Formula.

######  Claim 2.2.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, shift vector
$\boldsymbol{u}\in\mathbb{R}^{n}$, and parameter $s>0$,
$\rho_{s}(\mathcal{L}-\boldsymbol{u})\leq\rho_{s}(\mathcal{L})$ with equality
if and only if $\boldsymbol{u}\in\mathcal{L}$.

######  Lemma 2.3.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, primitive sublattice
$\mathcal{L}^{\prime}\subset\mathcal{L}$, and $s>0$,

$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathcal{L}^{\prime}\oplus\mathcal{L}/\mathcal{L}^{\prime})=\rho_{s}(\mathcal{L}^{\prime})\rho_{s}(\mathcal{L}/\mathcal{L}^{\prime})\;,$

with equality if and only if
$\mathcal{L}=\mathcal{L}^{\prime}\oplus\mathcal{L}/\mathcal{L}^{\prime}$.

###### Proof.

Let $\widehat{C}:=\\{\mathcal{L}^{\prime}+\boldsymbol{y}\ :\
\boldsymbol{y}\in\mathcal{L}\\}$ be the set of distinct cosets of
$\mathcal{L}^{\prime}$ over $\mathcal{L}$,
$\pi:=\pi_{\operatorname{span}(\mathcal{L}^{\prime})}$, and
$\pi^{\perp}:=\pi_{\operatorname{span}(\mathcal{L}^{\prime})^{\perp}}$. Then,

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{L}}\rho_{s}(\boldsymbol{y})$
$\displaystyle=\sum_{\boldsymbol{c}\in\widehat{C}}\rho_{s}(\boldsymbol{c})=\sum_{\boldsymbol{c}\in\widehat{C}}\rho_{s}(\pi(\boldsymbol{c}))\rho_{s}(\pi^{\perp}(\boldsymbol{c}))\leq\rho_{s}(\mathcal{L}^{\prime})\sum_{\boldsymbol{c}\in\widehat{C}}\rho_{s}(\pi^{\perp}(\boldsymbol{c}))=\rho_{s}(\mathcal{L}^{\prime})\rho_{s}(\mathcal{L}/\mathcal{L}^{\prime})\;,$

where the inequality follows from Claim 2.2. ∎

###  2.2 Linear algebra

We write $\mathrm{GL}_{n}(\mathbb{R})$ for the set of all $n\times n$
invertible real matrices, and $\mathrm{SL}_{n}(\mathbb{R})$ for the set of all
$n\times n$ determinant-one real matrices. A matrix
$U\in\mathrm{SL}_{n}(\mathbb{R})$ is _orthogonal_ if $U^{T}U=I_{n}$.
Equivalently, a matrix is orthogonal if its associated liner transformation is
an isometry. (I.e., $\|U\boldsymbol{x}\|=\|\boldsymbol{x}\|$ for all
$\boldsymbol{x}\in\mathbb{R}^{n}$.) We write
$\|A\|:=\sup_{\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}}\|A\boldsymbol{x}\|/\|\boldsymbol{x}\|$
for the _operator norm_ of $A$.

We recall the definition of the _matrix exponential_ ,

$e^{A}:=I_{n}+A+A^{2}/2+A^{3}/6+\cdots\;,$

for any matrix $A\in\mathbb{R}^{n\times n}$. Every positive-definite matrix
$A$ has a matrix logarithm $M$ such that $e^{M}=A$. In the main part of the
paper, we will only need this definition in the special case of diagonal
matrices, in which case the matrix exponential simply “applies the scalar
exponential function to each entry of the matrix.”

###  2.3 A note on the topology of the space of determinant-one lattices

Throughout this paper, we consider various topological notions over the space
of determinant-one (full-rank) lattices in $\mathbb{R}^{n}$ (e.g., local
maxima, compactness, etc.). Formally, the space of determinant-one lattices is
$\mathrm{SL}_{n}(\mathbb{R})/\mathrm{SL}_{n}(\mathbb{Z})$ (i.e., the set of
determinant-one real matrices modulo the unimodular matrices, which are
transformations between bases of the same lattice), and the topology is the
quotient topology. (See [Ter16, Section 1.4].) The reader may prefer to think
of the space of determinant-one lattice _bases_ with the standard topology on
$\mathrm{SL}_{n}(\mathbb{R})$.

###  2.4 Stability

We say that a lattice $\mathcal{L}\subset\mathbb{R}^{n}$ is _stable_ if
$\det(\mathcal{L})=1$ and $\det(\mathcal{L}^{\prime})\geq 1$ for all
sublattices $\mathcal{L}^{\prime}\subseteq\mathcal{L}$. (Some authors call
such lattices “semistable.”) Note the obvious relationship between this notion
and Theorem 1.2. Here, we describe the properties of stable lattices that we
will need in the sequel, and include proofs for completeness. This theory was
developed by [HN75, Stu76, Gra84]. See, e.g., [Gra84, Cas04] for a more
thorough treatment.

Figure 1:  The canonical polygon of a (hypothetical) lattice $\mathcal{L}$.

We can in some sense “decompose” any lattice into stable lattices. To see
this, we consider the two-dimensional scatter plot with points

$\\{(\operatorname{rank}(\mathcal{L}^{\prime}),\
\log\det(\mathcal{L}^{\prime}))\ :\
\mathcal{L}^{\prime}\subseteq\mathcal{L}\\}\;,$

for some lattice $\mathcal{L}\subset\mathbb{R}^{n}$, where we explicitly
include the trivial sublattice $\\{\boldsymbol{0}\\}$ and define
$\log\det(\\{\boldsymbol{0}\\}):=0$. We call this the _canonical plot_ of
$\mathcal{L}$. Note that these points are bounded from below and that the
minimum $\log\det$ for each fixed rank is achieved. The convex hull of these
points is therefore a degenerate polygon (bounded from below, but unbounded
from above), called the _canonical polygon_ of $\mathcal{L}$. See Figure 1.

We are interested in the vertices of this polygon (i.e., the extremal points),
which correspond to certain primitive sublattices of $\mathcal{L}$ with low
determinants. (E.g., $\mathcal{L}_{0},\ldots,\mathcal{L}_{5}$ in Figure 1.)
Each vertex corresponds to a unique sublattice, and a lattice
$\mathcal{L}_{1}$ corresponding to a low-rank extremal point is a sublattice
of any lattice $\mathcal{L}_{2}$ corresponding to a higher-rank extremal
point, $\mathcal{L}_{1}\subset\mathcal{L}_{2}$. Therefore, the extremal points
define a _canonical filtration_ of $\mathcal{L}$,

$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\mathcal{L}_{1}\subset\cdots\subset\mathcal{L}_{k}=\mathcal{L}\;.$

(E.g., the canonical filtration of $\mathbb{Z}^{n}$ is trivial:
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\mathcal{L}_{1}=\mathbb{Z}^{n}$.
Note in particular we only include lattices that correspond to _vertices_ in
the canonical filtration, not any lattice on the boundary.) All of the
quotients $\mathcal{L}_{i}/\mathcal{L}_{i-1}$ of adjacent sublattices in the
canonical filtration are scalings of stable lattices. This is what we mean
when we say that we can “decompose” a lattice into a sequence of stable
lattices. Following [Gra84, Cas04], we make these facts (and more) precise in
Proposition 2.5, which lists basic properties of the canonical filtration and
stable lattices. We first need the following lemma, due to Stuhler [Stu76].

######  Lemma 2.4.

For any $\mathcal{L}\subset\mathbb{R}^{n}$ and any two primitive sublattices
$\mathcal{L}_{1},\mathcal{L}_{2}\subseteq\mathcal{L}$,

$\operatorname{rank}(\mathcal{L}_{1})+\operatorname{rank}(\mathcal{L}_{2})=\operatorname{rank}(\mathcal{L}_{1}\cap\mathcal{L}_{2})+\operatorname{rank}(\mathcal{L}_{1}+\mathcal{L}_{2})\;,$

and

$\det(\mathcal{L}_{1}\cap\mathcal{L}_{2})\det(\mathcal{L}_{1}+\mathcal{L}_{2})\leq\det(\mathcal{L}_{1})\det(\mathcal{L}_{2})\;,$

where we define $\det(\\{\boldsymbol{0}\\})=1$.

###### Proof.

The equality of ranks follows by considering the dimensions of the subspaces
spanned by $\mathcal{L}_{1}$, $\mathcal{L}_{2}$,
$\mathcal{L}_{1}\cap\mathcal{L}_{2}$, and $\mathcal{L}_{1}+\mathcal{L}_{2}$.
For the inequality, suppose that
$\mathcal{M}_{1},\mathcal{M}_{2}\subseteq\mathcal{M}$ are sublattices such
that $\mathcal{M}_{1}\cap\mathcal{M}_{2}=\\{\boldsymbol{0}\\}$ and
$\mathcal{M}_{1}+\mathcal{M}_{2}=\mathcal{M}$. Then, we have

$\det(\mathcal{M})=\det(\mathcal{M}_{1})\cdot\det(\pi_{\operatorname{span}(\mathcal{M}_{1})^{\perp}}(\mathcal{M}_{2}))\leq\det(\mathcal{M}_{1})\det(\mathcal{M}_{2})\;.$

Plugging in
$\mathcal{M}:=(\mathcal{L}_{1}+\mathcal{L}_{2})/(\mathcal{L}_{1}\cap\mathcal{L}_{2})$,
$\mathcal{M}_{1}:=\mathcal{L}_{1}/(\mathcal{L}_{1}\cap\mathcal{L}_{2})$ and
$\mathcal{M}_{2}:=\mathcal{L}_{2}/(\mathcal{L}_{1}\cap\mathcal{L}_{2})$ gives

$\displaystyle\det(\mathcal{L}_{1}+\mathcal{L}_{2})/\det(\mathcal{L}_{1}\cap\mathcal{L}_{2})$
$\displaystyle=\det((\mathcal{L}_{1}+\mathcal{L}_{2})/(\mathcal{L}_{1}\cap\mathcal{L}_{2}))$
$\displaystyle\leq\det(\mathcal{L}_{1}/(\mathcal{L}_{1}\cap\mathcal{L}_{2}))\det(\mathcal{L}_{2}/(\mathcal{L}_{1}\cap\mathcal{L}_{2}))$
$\displaystyle=\det(\mathcal{L}_{1})\det(\mathcal{L}_{2})/\det(\mathcal{L}_{1}\cap\mathcal{L}_{2})^{2}\;.$

The result follows by rearranging. ∎

######  Proposition 2.5.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, let
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0},\mathcal{L}_{1},\ldots,\mathcal{L}_{k}=\mathcal{L}$
be all sublattices corresponding to vertices of the canonical polytope,
ordered by their rank. (See Figure 1.) Then,

  1. 1.

the $\mathcal{L}_{i}$ define a filtration
$\mathcal{L}_{0}\subset\mathcal{L}_{1}\subset\cdots\subset\mathcal{L}_{k}$;

  2. 2.

the quotient lattice $\mathcal{L}_{i}/\mathcal{L}_{i-1}$ is a scaling of a
stable lattice for $1\leq i\leq k$ (i.e.,
$\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{-1/\operatorname{rank}(\mathcal{L}_{i}/\mathcal{L}_{i-1})}\cdot\mathcal{L}_{i}/\mathcal{L}_{i-1}$
is stable); and

  3. 3.

for all $1\leq i\leq k-1$,
$\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{1/\operatorname{rank}(\mathcal{L}_{i}/\mathcal{L}_{i-1})}<\det(\mathcal{L}_{i+1}/\mathcal{L}_{i})^{1/\operatorname{rank}(\mathcal{L}_{i+1}/\mathcal{L}_{i})}$.

Furthermore,

  1. (i)

the dual of a stable lattice is stable;

  2. (ii)

the set of all stable lattices is compact;

  3. (iii)

the direct sum of stable lattices is stable; and

  4. (iv)

a lattice $\mathcal{L}\subset\mathbb{R}^{n}$ is on the boundary of the set of
stable lattices if and only if $\mathcal{L}$ is stable and there is a
primitive sublattice $\mathcal{L}^{\prime}\subset\mathcal{L}$ with
$0<\operatorname{rank}(\mathcal{L}^{\prime})<n$ such that
$\mathcal{L}^{\prime}$ and $\mathcal{L}/\mathcal{L}^{\prime}$ are both stable.

###### Proof.

To prove Item 1, we first note that for any two indices $i\leq j$, we can
interpret Lemma 2.4 in terms of the canonical plot as follows. Consider the
parallelogram with the three vertices
$(\operatorname{rank}(\mathcal{L}_{i}),\log\det(\mathcal{L}_{i}))$,
$(\operatorname{rank}(\mathcal{L}_{i}+\mathcal{L}_{j}),\log\det(\mathcal{L}_{i}+\mathcal{L}_{j}))$,
and
$(\operatorname{rank}(\mathcal{L}_{i}\cap\mathcal{L}_{j}),\log\det(\mathcal{L}_{i}\cap\mathcal{L}_{j}))$.
Lemma 2.4 tells us that the point
$(\operatorname{rank}(\mathcal{L}_{j}),\log\det(\mathcal{L}_{j}))$ lies on or
above the fourth point in this parallelogram. This contradicts the assumption
that $\mathcal{L}_{i}$ and $\mathcal{L}_{j}$ are extremal points of the convex
hull of the canonical plot _unless_ the parallelogram is degenerate—i.e.,
unless $\mathcal{L}_{i}+\mathcal{L}_{j}=\mathcal{L}_{j}$ or
$\mathcal{L}_{i}\cap\mathcal{L}_{j}=\mathcal{L}_{i}$. This happens if and only
if $\mathcal{L}_{i}\subseteq\mathcal{L}_{j}$, as needed.

To prove Item 2, let
$\mathcal{L}^{\prime}\subseteq\mathcal{L}_{i}/\mathcal{L}_{i-1}$. Let
$\widehat{\mathcal{L}}\subseteq\mathcal{L}_{i}$ be a “lift” of
$\mathcal{L}^{\prime}$ so that
$\mathcal{L}_{i-1}\subseteq\widehat{\mathcal{L}}$ and
$\mathcal{L}^{\prime}=\widehat{\mathcal{L}}/\mathcal{L}_{i-1}$. Since
$\mathcal{L}_{i-1}$ and $\mathcal{L}_{i}$ are vertices of the canonical
polygon, the point
$(\operatorname{rank}(\widehat{\mathcal{L}}),\log\det(\widehat{\mathcal{L}}))$
must lie on or above the line between
$(\operatorname{rank}(\mathcal{L}_{i-1}),\log\det(\mathcal{L}_{i-1}))$ and
$(\operatorname{rank}(\mathcal{L}_{i}),\log\det(\mathcal{L}_{i}))$. Therefore,

$\displaystyle\det(\mathcal{L}^{\prime})$
$\displaystyle=\det(\widehat{\mathcal{L}})/\det(\mathcal{L}_{i-1})$
$\displaystyle\geq\Big{(}\frac{\det(\mathcal{L}_{i})}{\det(\mathcal{L}_{i-1})}\Big{)}^{\frac{\operatorname{rank}(\widehat{\mathcal{L}})-\operatorname{rank}(\mathcal{L}_{i-1})}{\operatorname{rank}(\mathcal{L}_{i})-\operatorname{rank}(\mathcal{L}_{i-1})}}$
$\displaystyle=\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{\frac{\operatorname{rank}(\mathcal{L}^{\prime})}{\operatorname{rank}(\mathcal{L}_{i}/\mathcal{L}_{i-1})}}\;.$

I.e., if we set
$\alpha_{i}:=\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{-1/\operatorname{rank}(\mathcal{L}_{i}/\mathcal{L}_{i-1})}$,
then $\det(\alpha_{i}\mathcal{L}^{\prime})\geq 1$. It follows that
$\alpha_{i}\mathcal{L}_{i}/\mathcal{L}_{i-1}$ is stable, as claimed.

Item 3 simply says that the slopes of the lines between vertices on the
canonical polytope are strictly increasing. This is essentially just the
definition of a vertex. (See Figure 1.)

To prove Item (i), let $\mathcal{M}\subset\mathbb{R}^{n}$ be a stable lattice
and let $\mathcal{M}^{\prime}\subseteq\mathcal{M}^{*}$ be a primitive
sublattice of the dual. We have

$\det(\mathcal{M}^{\prime})=\frac{1}{\det(\mathcal{M}^{*}/\mathcal{M}^{\prime})}=\det((\mathcal{M}^{*}/\mathcal{M}^{\prime})^{*})=\det(\mathcal{M}\cap\operatorname{span}(\mathcal{M}^{\prime}))\geq
1\;.$

Therefore, $\mathcal{M}^{*}$ is stable.

To prove Item (ii), it suffices to find a bounded set in $\mathbb{R}^{n\times
n}$ that contains a basis for every stable lattice. Indeed, for any stable
lattice $\mathcal{M}\subset\mathbb{R}^{n}$, by Item (i), we know that its dual
$\mathcal{M}^{*}$ is also stable. Therefore, $\lambda_{1}(\mathcal{M}^{*})\geq
1$. It then follows from [LLS90] that there exists a basis
$(\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n})$ of $\mathcal{M}$ with
$1\leq\|\boldsymbol{b}_{i}\|\leq Cn^{2.5}$ for all $i$, as needed.

To prove Item (iii), let $\mathcal{M}_{1},\mathcal{M}_{2}$ be two stable
lattices, and let
$\mathcal{M}^{\prime}\subset\mathcal{M}_{1}\oplus\mathcal{M}_{2}$ be a
sublattice. Then, applying Lemma 2.4, we have

$\det(\mathcal{M}^{\prime})\geq\frac{\det(\mathcal{M}^{\prime}\cap\mathcal{M}_{1})\det(\mathcal{M}^{\prime}+\mathcal{M}_{1})}{\det(\mathcal{M}_{1})}=\det(\mathcal{M}^{\prime}\cap\mathcal{M}_{1})\det(\mathcal{M}^{\prime}+\mathcal{M}_{1})\;.$

Note that $\mathcal{M}^{\prime}\cap\mathcal{M}_{1}$ is a sublattice of
$\mathcal{M}_{1}$, so that $\det(\mathcal{M}^{\prime}\cap\mathcal{M}_{1})\geq
1$. And
$\mathcal{M}^{\prime}+\mathcal{M}_{1}=\mathcal{M}_{1}\oplus\pi_{\operatorname{span}(\mathcal{M}_{2})}(\mathcal{M}^{\prime})$
is the direct sum of $\mathcal{M}_{1}$ with a sublattice of $\mathcal{M}_{2}$,
so that
$\det(\mathcal{M}^{\prime}+\mathcal{M}_{1})=\det(\pi_{\operatorname{span}(\mathcal{M}_{2})}(\mathcal{M}^{\prime}))\geq
1$ as well. The result follows.

Finally, Item (iv) follows by first noting that a stable lattice $\mathcal{M}$
is on the boundary if and only if there is some strict primitive non-zero
sublattice $\mathcal{M}^{\prime}\subset\mathcal{M}$ with
$\det(\mathcal{M}^{\prime})=1$. Clearly, $\mathcal{M}^{\prime}$ is stable,
since it has determinant one and all of its sublattices are also sublattices
of $\mathcal{M}$, so that they must have determinant at least one. The proof
that $\mathcal{M}/\mathcal{M}^{\prime}$ is stable is essentially identical to
the proof of Item 2. ∎

###  2.5 The Voronoi cell and fundamental bodies

The _Voronoi cell_ of a lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\mathcal{V}(\mathcal{L}):=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\
\langle\boldsymbol{x},\boldsymbol{y}\rangle\leq\|\boldsymbol{y}\|^{2}/2,\
\forall\boldsymbol{y}\in\mathcal{L}\\}\;,$

is the set of vectors in $\mathbb{R}^{n}$ that are closer to $\boldsymbol{0}$
than to any other lattice vector. In fact, it is a symmetric polytope.

A _fundamental body_ of a lattice $\mathcal{L}\subset\mathbb{R}^{n}$ is any
convex body $K\subset\mathbb{R}^{n}$ such that $K+\mathcal{L}$ is a tiling of
space. Equivalently, $\operatorname{vol}(K)=\det(\mathcal{L})$ and
$\mathrm{Int}(K)\cap(K+\boldsymbol{y})=\emptyset$ for any non-zero lattice
point $\boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}$. In
particular, the Voronoi cell is a fundamental body.

######  Claim 2.6.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, primitive sublattice
$\mathcal{L}^{\prime}\subset\mathbb{R}^{n}$, fundamental body $K_{1}$ of
$\mathcal{L}^{\prime}$, and fundamental body $K_{2}$ of
$\mathcal{L}/\mathcal{L}^{\prime}$, $K:=K_{1}\times K_{2}$ is a fundamental
body of $\mathcal{L}$. In particular, if
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\mathcal{L}_{1}\subset\cdots\subset\mathcal{L}_{k}$
is a filtration of primitive sublattices, then

$\mathcal{V}\Big{(}\bigoplus_{i}\mathcal{L}_{i}/\mathcal{L}_{i-1}\Big{)}=\mathcal{V}(\mathcal{L}_{1}/\mathcal{L}_{0})\times\cdots\times\mathcal{V}(\mathcal{L}_{k}/\mathcal{L}_{k-1})$

is a fundamental body of $\mathcal{L}$.

###### Proof.

Notice that

$\operatorname{vol}(K)=\operatorname{vol}(K_{1})\cdot\operatorname{vol}(K_{2})=\det(\mathcal{L}^{\prime})\cdot\det(\mathcal{L}/\mathcal{L}^{\prime})=\det(\mathcal{L})\;.$

It therefore suffices to show that
$\mathrm{Int}(K)\cap(K+\boldsymbol{y})=\emptyset$ for any
$\boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}$. So suppose
$\boldsymbol{y}\in\mathcal{L}$ such that
$\mathrm{Int}(K)\cap(K+\boldsymbol{y})\neq\emptyset$. Then, by projecting
orthogonally to $\mathcal{L}^{\prime}$, we see that
$\mathrm{Int}(K_{2})\cap(K_{2}+\pi_{\operatorname{span}(\mathcal{L}^{\prime})^{\perp}}(\boldsymbol{y}))\neq\emptyset$.
Since $K_{2}$ is a fundamental body of $\mathcal{L}/\mathcal{L}^{\prime}$ and
$\pi_{\operatorname{span}(\mathcal{L}^{\prime})^{\perp}}(\boldsymbol{y})\in\mathcal{L}/\mathcal{L}^{\prime}$,
it follows that
$\pi_{\operatorname{span}(\mathcal{L}^{\prime})^{\perp}}(\boldsymbol{y})=\boldsymbol{0}$,
i.e., $\boldsymbol{y}\in\mathcal{L}^{\prime}$. Intersecting with
$\operatorname{span}(\mathcal{L}^{\prime})$, this implies that
$\mathrm{Int}(K_{1})\cap(K_{1}+\boldsymbol{y})\neq\emptyset$. Since
$\boldsymbol{y}\in\mathcal{L}^{\prime}$ and $K_{1}$ is a fundamental body of
$\mathcal{L}^{\prime}$, we obtain that $\boldsymbol{y}=\boldsymbol{0}$. The
result follows. ∎

The next lemma and its corollary show that the Voronoi cell is in some sense
the “optimal fundamental body.” They are very similar to some results due to
Dadush [Dad12b, Lemma 6.3.6, Corollary 6.3.7].

######  Lemma 2.7.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, there is a map
$\psi_{\mathcal{L}}:\mathbb{R}^{n}\to\mathcal{V}(\mathcal{L})$ such that
$\|\psi_{\mathcal{L}}(\boldsymbol{x})\|\leq\|\boldsymbol{x}\|$, and for every
fundamental body $K$ of $\mathcal{L}$, $\psi_{\mathcal{L}}$ restricted to
$\mathrm{Int}(K)$ is injective and volume-preserving.

###### Proof.

The function $\psi_{\mathcal{L}}$ just maps $\boldsymbol{x}$ to the unique
representative of $\boldsymbol{x}\bmod\mathcal{L}$ that is in the Voronoi
cell. Specifically, let
$\mathsf{CVP}_{\mathcal{L}}(\boldsymbol{x}):=\operatorname*{argmin}_{\boldsymbol{y}\in\mathcal{L}}\|\boldsymbol{y}-\boldsymbol{x}\|$
be the closest lattice vector to $\boldsymbol{x}$, and let
$\psi_{\mathcal{L}}(\boldsymbol{x}):=\boldsymbol{x}-\mathsf{CVP}_{\mathcal{L}}(\boldsymbol{x})$.
By the definition of $\mathsf{CVP}$, it is immediate that
$\|\psi_{\mathcal{L}}(\boldsymbol{x})\|=\min_{\boldsymbol{y}\in\mathcal{L}}\|\boldsymbol{y}-\boldsymbol{x}\|\leq\|\boldsymbol{x}\|$.

Suppose
$\psi_{\mathcal{L}}(\boldsymbol{x})=\psi_{\mathcal{L}}(\boldsymbol{x}^{\prime})$
for some $\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathrm{Int}(K)$. I.e.,
$\boldsymbol{x}-\mathsf{CVP}_{\mathcal{L}}(\boldsymbol{x})=\boldsymbol{x}^{\prime}-\mathsf{CVP}_{\mathcal{L}}(\boldsymbol{x}^{\prime})$.
Rearranging, we see that
$\boldsymbol{y}:=\boldsymbol{x}-\boldsymbol{x}^{\prime}=\mathsf{CVP}_{\mathcal{L}}(\boldsymbol{x})-\mathsf{CVP}_{\mathcal{L}}(\boldsymbol{x}^{\prime})$
is a lattice point. But,
$\boldsymbol{x}\in\mathrm{Int}(K)\cap(K+\boldsymbol{y})$. Since $K$ is a
fundamental body, it follows that $\boldsymbol{y}=\boldsymbol{0}$. I.e.,
$\boldsymbol{x}=\boldsymbol{x}^{\prime}$, and $\psi_{\mathcal{L}}$ is
injective over $\mathrm{Int}(K)$.

The fact that $\psi_{\mathcal{L}}$ is volume-preserving over $\mathrm{Int}(K)$
follows from the fact that it is an injective piecewise combination of
translations. ∎

######  Corollary 2.8.

For any non-decreasing measurable function $f:\mathbb{R}\to\mathbb{R}$,
lattice $\mathcal{L}\subset\mathbb{R}^{n}$, and fundamental body $K$ of
$\mathcal{L}$,

$\int_{\mathcal{V}(\mathcal{L})}f(\|\boldsymbol{x}\|){\rm
d}\boldsymbol{x}\leq\int_{K}f(\|\boldsymbol{x}\|){\rm d}\boldsymbol{x}\;.$

###### Proof.

$\int_{K}f(\|\boldsymbol{x}\|){\rm
d}\boldsymbol{x}=\int_{\mathrm{Int}(K)}f(\|\boldsymbol{x}\|){\rm
d}\boldsymbol{x}\geq\int_{\mathrm{Int}(K)}f(\|\psi_{\mathcal{L}}(\boldsymbol{x})\|){\rm
d}\boldsymbol{x}=\int_{\psi_{\mathcal{L}}(\mathrm{Int}(K))}f(\|\boldsymbol{x}\|){\rm
d}\boldsymbol{x}=\int_{\mathcal{V}(\mathcal{L})}f(\|\boldsymbol{x}\|){\rm
d}\boldsymbol{x}\;,$

where the last equality follows from the fact that $\psi_{\mathcal{L}}$
preserves volume and
$\operatorname{vol}(\mathrm{Int}(K))=\operatorname{vol}(\mathcal{V}(\mathcal{L}))$,
so it must be the case that
$\psi_{\mathcal{L}}(\mathrm{Int}(K))\subset\mathcal{V}(\mathcal{L})$ differs
from $\mathcal{V}(\mathcal{L})$ on a set of measure zero. ∎

###  2.6 Matrix calculus

For a function $g:\mathbb{R}^{n\times n}\to\mathbb{R}$, if for some
$Q\in\mathbb{R}^{n\times n}$ there exists an $B\in\mathbb{R}^{n\times n}$ such
that

$\lim_{M\to 0}\frac{g(Q+M)-g(Q)-\mbox{\rm Tr}(B^{T}M)}{\|M\|}=0\;,$

then we say that $g$ is _differentiable_ at $Q$, and we call $B$ the
_gradient_ of $g$ at $Q$,

$\nabla_{A}g(A)|_{A=Q}:=B\;.$

(Some authors prefer to define $\nabla g(A)|_{A=Q}$ as $B^{T}$.)

##  3 Gradients over lattices and over positions of the Voronoi cell

The purpose of this section is to prove the following theorem. (Note that the
gradient is actually symmetric, so that the transpose in the definition of the
function $g$ is simply a matter of convention.) The proof we give here is
elementary but somewhat lengthy. For the reader’s benefit, we include in
Appendix A a much shorter proof that assumes, however, that one already knows
that the functions $g$ and $h$ are differentiable.

######  Theorem 3.1.

For any continuously differentiable function $f:\mathbb{R}^{\geq
0}\to\mathbb{R}$ and lattice $\mathcal{L}\subset\mathbb{R}^{n}$, let

$g(A):=\frac{1}{|\det(A)|}\cdot\int_{\mathcal{V}(A^{T}\mathcal{L})}f(\|\boldsymbol{x}\|^{2}){\rm
d}\boldsymbol{x}\text{, \ and \
}h(A):=\frac{1}{|\det(A)|}\cdot\int_{A\mathcal{V}(\mathcal{L})}f(\|\boldsymbol{x}\|^{2}){\rm
d}\boldsymbol{x}\;,$

where $A\in\mathrm{GL}_{n}(\mathbb{R})$ ranges over the set of all non-
singular matrices. Then, $g$ and $h$ are differentiable at $A=I_{n}$, with

$\nabla_{A}g(A)|_{A=I_{n}}=\nabla_{A}h(A)|_{A=I_{n}}=2\int_{\mathcal{V}(\mathcal{L})}f^{\prime}(\|\boldsymbol{x}\|^{2})\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}\;,$

where $f^{\prime}(x):=\frac{{\rm d}}{{\rm d}x}f(x)$.

We first compute the gradient of $h$, which is straightforward.

######  Claim 3.2.

For any continuously differentiable function $f:\mathbb{R}^{\geq
0}\to\mathbb{R}$ and measurable set $U$, let

$h(A):=\frac{1}{|\det(A)|}\cdot\int_{AU}f(\|\boldsymbol{x}\|^{2}){\rm
d}\boldsymbol{x}\;,$

where $A\in\mathrm{GL}_{n}(\mathbb{R})$ ranges over the set of all non-
singular matrices. Then, $h$ is differentiable with

$\nabla_{A}h(A)|_{A=I_{n}}=2\int_{U}f^{\prime}(\|\boldsymbol{x}\|^{2})\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}\;,$

where $f^{\prime}(x):=\frac{{\rm d}}{{\rm d}x}f(x)$, provided that this
integral and $h(I_{n})$ are well-defined and finite.

###### Proof.

By a change of variables, we have

$h(A)=\int_{U}f(\|A\boldsymbol{x}\|^{2}){\rm d}\boldsymbol{x}\;.$

Then, by applying an appropriate high-dimensional form of Leibniz’s integral
rule (see, e.g., [Kam16]), we may swap the gradient and the integral and write

$\displaystyle\nabla_{A}h(A)$
$\displaystyle=\int_{U}\big{(}\nabla_{A}f(\|A\boldsymbol{x}\|^{2})\big{)}{\rm
d}\boldsymbol{x}$
$\displaystyle=2\int_{U}f^{\prime}(\|A\boldsymbol{x}\|^{2})A\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}$ $\displaystyle\text{(Chain rule)}\;.$

###  3.1 Polytopes and “protected cones”

We define

$H_{\boldsymbol{w}}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\
\langle\boldsymbol{w},\boldsymbol{x}\rangle\leq 1\\}\;.$

Any convex body with $\boldsymbol{0}$ in its interior can be written as

$K(W):=\bigcap_{\boldsymbol{w}\in W}H_{\boldsymbol{w}}$

for some (possibly infinite) set $W\subset\mathbb{R}^{n}$. We call $K(W)$ a
_polytope_ if the set $W$ can be taken to be finite. I.e., a polytope is a
bounded finite intersection of half-spaces.

The _facets_ of a polytope $K(W)$ are the points in the polytope for which at
least one inequality is tight,

$\mathcal{F}_{W,\boldsymbol{w}}:=\\{\boldsymbol{x}\in K(W)\ :\
\langle\boldsymbol{w},\boldsymbol{x}\rangle=1\\}\;,$

for $\boldsymbol{w}\in W$.

A polytope has _normally symmetric facets_ if for every $\boldsymbol{w}\in
W\setminus\\{\boldsymbol{0}\\}$,
$\boldsymbol{x}\in\mathcal{F}_{W,\boldsymbol{w}}$ if and only if the
“reflection of $\boldsymbol{x}$ through
$\operatorname{span}(\boldsymbol{w})$,”
$2\pi_{\boldsymbol{w}}(\boldsymbol{x})-\boldsymbol{x}$, is in
$\mathcal{F}_{W,\boldsymbol{w}}$. In other words, a polytope has normally
symmetric facets if each facet is symmetric about the line normal to the
facet. Equivalently, if we define

$R_{W,\boldsymbol{w}}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\ \text{for all
$\boldsymbol{w}^{\prime}\in W$,
}\langle\boldsymbol{w}^{\prime},\boldsymbol{x}\rangle\leq\langle\boldsymbol{w},\boldsymbol{x}\rangle\\}\;$
(4)

to be the minimal cone containing $\mathcal{F}_{W,\boldsymbol{w}}$ (or
$\\{\boldsymbol{0}\\}$ if the facet is empty), then a polytope has normally
symmetric facets if and only if
$\phi_{\boldsymbol{w}}(R_{W,\boldsymbol{w}})=R_{W,\boldsymbol{w}}$ for all
$\boldsymbol{w}\in W\setminus\\{\boldsymbol{0}\\}$, where

$\phi_{\boldsymbol{w}}(\boldsymbol{x}):=2\pi_{\boldsymbol{w}}(\boldsymbol{x})-\boldsymbol{x}=2\langle\boldsymbol{w},\boldsymbol{x}\rangle\boldsymbol{w}/\|\boldsymbol{w}\|^{2}-\boldsymbol{x}\;.$
(5)

We will be interested in perturbations of polytopes. When we analyze these
objects, we will have some trouble with points $\boldsymbol{x}$ that “change
cones $R_{W,\boldsymbol{w}}$.” The next lemma shows how to find slightly
smaller “protected cones” $\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}$
inside the $R_{W,\boldsymbol{w}_{i}}$ so that the vectors inside these
“protected cones” do not leave the larger cone $R_{W,\boldsymbol{w}_{i}}$
after a small perturbation $W\to W^{\prime}$. See Figure 2.

(a) A polytope $K(W)\subset\mathbb{R}^{2}$ with the corresponding cones
$R_{W,\boldsymbol{w}_{1}},\ldots,R_{W,\boldsymbol{w}_{6}}$.

(b) The “protected cone” $\overline{R}_{W,\boldsymbol{w}_{1},\varepsilon}$,
“bad” set $B_{1}$, and the symmetric difference
$K(W)\mathbin{\triangle}K(W^{\prime})$ between the original polytope $K(W)$
and its perturbation $K(W^{\prime})$.

Figure 2:  An illustration of Lemma 3.3.

######  Lemma 3.3.

For any finite set
$W:=\\{\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{k}\\}\subset\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}$
of distinct vectors such that $K(W)$ is a polytope and sufficiently small
$\varepsilon>0$, there exist “protected cones”
$\overline{R}_{W,\boldsymbol{w}_{1},\varepsilon},\ldots,\overline{R}_{W,\boldsymbol{w}_{k},\varepsilon}$
such that for any
$W^{\prime}:=\\{\boldsymbol{w}_{1}^{\prime},\ldots,\boldsymbol{w}_{k}^{\prime}\\}\subset\mathbb{R}^{n}$
with $\|\boldsymbol{w}_{i}^{\prime}-\boldsymbol{w}_{i}\|\leq\varepsilon$ for
all $i$, we have

  1. 1.

$\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\subseteq
R_{W^{\prime},\boldsymbol{w}_{i}^{\prime}}$ for all $i$ (i.e., vectors in the
protected cones “keep the same relevant vector” after any $\varepsilon$
perturbation of the $\boldsymbol{w}_{i}$);

  2. 2.

for all $i$, the “bad” set $B_{i}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\
\boldsymbol{x}\in
R_{W,\boldsymbol{w}_{i}}\setminus\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\\}$
of points not in the protected cone satisfies
$\operatorname{vol}(B_{i}\cap(K(W)\mathbin{\triangle}K(W^{\prime}))\leq
O(\varepsilon^{2})$, where the $O(\varepsilon^{2})$ term hides dependence on
$W$ (i.e., the dark red region in Figure 2(b) has volume at most
$O(\varepsilon^{2})$); and

  3. 3.

if
$\phi_{\boldsymbol{w}_{i}}(R_{W,\boldsymbol{w}_{i}})=R_{W,\boldsymbol{w}_{i}}$,
then
$\phi_{\boldsymbol{w}_{i}}(\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon})=\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}$.

###### Proof.

Let

$\alpha_{\varepsilon}:=\max_{i\neq
j}\frac{2\varepsilon}{\|\boldsymbol{w}_{i}-\boldsymbol{w}_{j}\|}\;.$

We take

$\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}\
:\ \boldsymbol{x}+\alpha_{\varepsilon}\|\boldsymbol{x}\|B_{2}^{n}\subseteq
R_{W,\boldsymbol{w}_{i}}\\}\;.$

Item 3 then follows from the fact that $\phi_{\boldsymbol{w}_{i}}$ is an
isometry. In particular,
$\phi_{\boldsymbol{w}_{i}}(\boldsymbol{x}+\alpha_{\varepsilon}\|\boldsymbol{x}\|B_{2}^{n})=\phi_{\boldsymbol{w}_{i}}(\boldsymbol{x})+\alpha_{\varepsilon}\|\phi_{\boldsymbol{w}_{i}}(\boldsymbol{x})\|B_{2}^{n}$.

Turning to Item 1, suppose that
$\boldsymbol{x}\in\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}$, and let
$j\neq i$. Let
$\widehat{\boldsymbol{w}}:=(\boldsymbol{w}_{i}-\boldsymbol{w}_{j})/\|\boldsymbol{w}_{i}-\boldsymbol{w}_{j}\|$.
By the definition of the protected cone, we have

$\langle\boldsymbol{w}_{i},\boldsymbol{x}-\alpha_{\varepsilon}\|\boldsymbol{x}\|\widehat{\boldsymbol{w}}\rangle\geq\langle\boldsymbol{w}_{j},\boldsymbol{x}-\alpha_{\varepsilon}\|\boldsymbol{x}\|\widehat{\boldsymbol{w}}\rangle\;.$

Rearranging, we see that

$\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle\geq\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle+\alpha_{\varepsilon}\|\boldsymbol{x}\|\langle\boldsymbol{w}_{i}-\boldsymbol{w}_{j},\widehat{\boldsymbol{w}}\rangle=\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle+\alpha_{\varepsilon}\|\boldsymbol{x}\|\|\boldsymbol{w}_{i}-\boldsymbol{w}_{j}\|\geq\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle+2\varepsilon\|\boldsymbol{x}\|\;.$

Therefore, by Cauchy-Schwarz, we have

$\langle\boldsymbol{w}_{i}^{\prime},\boldsymbol{x}\rangle\geq\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle-\varepsilon\|\boldsymbol{x}\|\geq\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle+\varepsilon\|\boldsymbol{x}\|\geq\langle\boldsymbol{w}_{j}^{\prime},\boldsymbol{x}\rangle\;.$

I.e., $\boldsymbol{x}\in R_{W^{\prime},\boldsymbol{w}_{i}^{\prime}}$, as
needed.

Finally, suppose that $\boldsymbol{x}\in
B_{i}\cap(K(W)\mathbin{\triangle}K(W^{\prime}))$. We assume that
$\boldsymbol{x}\in K(W)\setminus K(W^{\prime})$, since the case where
$\boldsymbol{x}\in K(W^{\prime})\setminus K(W)$ is nearly identical. Since
$\boldsymbol{x}\in K(W)$, we have

$\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle\leq 1\;.$

Since $\boldsymbol{x}\notin K(W^{\prime})$, there exists a $j$ such that

$1<\langle\boldsymbol{w}_{j}^{\prime},\boldsymbol{x}\rangle=\langle\boldsymbol{w}_{j},\boldsymbol{x}\rangle+\langle\boldsymbol{w}_{j}^{\prime}-\boldsymbol{w}_{j},\boldsymbol{x}\rangle\leq\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle+\varepsilon\|\boldsymbol{x}\|\;,$

where we used that $\boldsymbol{x}\in R_{W,\boldsymbol{w}_{i}}$. It follows
that

$|\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle-1|\leq\varepsilon\|\boldsymbol{x}\|=O(\varepsilon)\;.$
(6)

And, since $\boldsymbol{x}\in B_{i}$, there must also be some $j\neq i$ such
that

$|\langle\boldsymbol{w}_{i}-\boldsymbol{w}_{j},\boldsymbol{x}\rangle|\leq
O(\varepsilon)\|\boldsymbol{x}\|\leq O(\varepsilon)\;.$ (7)

In other words, $\boldsymbol{x}$ lies in one of finitely many intersections
between a slab of width $O(\varepsilon)$ bounded away from $\boldsymbol{0}$
(defined by Eq. (6)), a slab of width $O(\varepsilon)$ around $\boldsymbol{0}$
(defined by Eq. (7)), and the bounded set $K(W)\cup K(W^{\prime})$. Item 2
then follows from the fact that any such set has volume $O(\varepsilon^{2})$.
∎

The next rather technical and specific corollary shows that these protected
cones in some sense “do not distinguish between perturbations to
$\boldsymbol{w}_{i}^{\prime}$ and perturbations to
$\phi_{\boldsymbol{w}_{i}}(\boldsymbol{w}_{i}^{\prime})$,” when $K(W)$ has
normally symmetric facets.

######  Corollary 3.4.

For any finite set
$W:=\\{\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{k}\\}\subset\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}$
such that $K(W)$ is a polytope with normally symmetric facets, sufficiently
small $\varepsilon>0$, and
$W^{\prime}:=\\{\boldsymbol{w}_{1}^{\prime},\ldots,\boldsymbol{w}_{k}^{\prime}\\}\subset\mathbb{R}^{n}$
with $\|\boldsymbol{w}_{i}^{\prime}-\boldsymbol{w}_{i}\|\leq\varepsilon$ for
all $i$, let
$W^{\prime\prime}:=\\{\phi_{\boldsymbol{w}_{1}}(\boldsymbol{w}_{1}^{\prime}),\ldots,\phi_{\boldsymbol{w}_{k}}(\boldsymbol{w}_{k}^{\prime})\\}$.
Then,

$\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
K(W^{\prime})=\phi_{\boldsymbol{w}_{i}}(\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
K(W^{\prime\prime}))$

for all $i$, where $\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}$ is the
“protected cone” from Lemma 3.3.

###### Proof.

By Item 1 of Lemma 3.3, we have that
$\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\subseteq
R_{W^{\prime},\boldsymbol{w}_{i}^{\prime}}\cap
R_{W^{\prime\prime},\phi_{\boldsymbol{w}_{i}}(\boldsymbol{w}_{i}^{\prime})}$.
It follows that $\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
K(W^{\prime})=\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
H_{\boldsymbol{w}_{i}^{\prime}}$, and similarly
$\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
K(W^{\prime\prime})=\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
H_{\phi_{\boldsymbol{w}_{i}}(\boldsymbol{w}_{i}^{\prime})}$. Noting that for
any $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{n}$,
$\langle\phi_{\boldsymbol{w}_{i}}(\boldsymbol{y}),\boldsymbol{x}\rangle=\langle\boldsymbol{y},\phi_{\boldsymbol{w}_{i}}(\boldsymbol{x})\rangle=\langle\boldsymbol{y},\phi_{\boldsymbol{w}_{i}}^{-1}(\boldsymbol{x})\rangle$,
we see that for any $\boldsymbol{y}\in\mathbb{R}^{n}$,

$H_{\phi_{\boldsymbol{w}_{i}}(\boldsymbol{y})}=\\{\boldsymbol{x}\in\mathbb{R}^{n}:\langle\phi_{\boldsymbol{w}_{i}}(\boldsymbol{y}),\boldsymbol{x}\rangle\leq
1\\}=\\{\boldsymbol{x}\in\mathbb{R}^{n}:\langle\boldsymbol{y},\phi_{\boldsymbol{w}_{i}}^{-1}(\boldsymbol{x})\rangle\leq
1\\}=\phi_{\boldsymbol{w}_{i}}(H_{\boldsymbol{y}})\;.$

We therefore have

$\phi_{\boldsymbol{w}_{i}}(\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap
H_{\phi_{\boldsymbol{w}_{i}}(\boldsymbol{w}_{i}^{\prime})})=\phi_{\boldsymbol{w}_{i}}(\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}\cap\phi_{\boldsymbol{w}_{i}}(H_{\boldsymbol{w}_{i}^{\prime}}))=\phi_{\boldsymbol{w}_{i}}(\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon})\cap
H_{\boldsymbol{w}_{i}^{\prime}}\;,$

where the last equality follows from the fact that
$\phi_{\boldsymbol{w}_{i}}=\phi_{\boldsymbol{w}_{i}}^{-1}$. The result follows
by recalling from Item 3 of Lemma 3.3 that
$\phi_{\boldsymbol{w}_{i}}(\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon})=\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}$.
∎

###  3.2 Perturbations of polytopes

The purpose of this subsection is to prove Lemma 3.8. The next claim shows
that a small change to $W$ corresponds to a small change to $K(W)$.

######  Claim 3.5.

For any finite set
$W=\\{\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{k}\\}\subset\mathbb{R}^{n}$
such that $K(W)$ is a polytope, sufficiently small $\varepsilon>0$, and any
$W^{\prime}:=\\{\boldsymbol{w}_{1}^{\prime},\ldots,\boldsymbol{w}_{k}^{\prime}\\}\subset\mathbb{R}^{n}$
such that $\|\boldsymbol{w}_{i}-\boldsymbol{w}_{i}^{\prime}\|\leq\varepsilon$,

$\operatorname{vol}(K(W)\mathbin{\triangle}K(W^{\prime}))\leq
O(\varepsilon)\;,$

where the $O(\varepsilon)$ term hides factors that depend on $W$.

###### Proof.

Suppose that $\boldsymbol{x}\in K(W)\setminus K(W^{\prime})$. (The case when
$\boldsymbol{x}\in K(W^{\prime})\setminus K(W)$ is essentially identical.)
Then, there exists some index $i$ such that

$\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle\leq
1<\langle\boldsymbol{w}_{i}^{\prime},\boldsymbol{x}\rangle\;.$

Using
$\langle\boldsymbol{w}_{i}^{\prime}-\boldsymbol{w}_{i},\boldsymbol{x}\rangle\leq\varepsilon\|\boldsymbol{x}\|\leq
O(\varepsilon)$, we see that

$1-O(\varepsilon)<\langle\boldsymbol{w}_{i},\boldsymbol{x}\rangle\leq 1\;.$

I.e., $\boldsymbol{x}$ lies in one of $k$ slabs with width proportional to
$\varepsilon$. The result follows by noting that the intersection of any such
slab with the bounded body $K(W)$ has volume $O(\varepsilon)$. ∎

######  Claim 3.6.

For any non-singular matrix $A\in\mathrm{GL}_{n}(\mathbb{R})$ and any
$W\subset\mathbb{R}^{n}$, $AK(W)=K(A^{-T}W)$.

###### Proof.

It suffices to note that $\boldsymbol{x}\in AK(W)$ if and only if
$\langle\boldsymbol{w},A^{-1}\boldsymbol{x}\rangle=\langle
A^{-T}\boldsymbol{w},\boldsymbol{x}\rangle\leq 1$ for all $\boldsymbol{w}\in
W$. ∎

Recall that the Voronoi cell of a lattice $\mathcal{L}$ is given by
$\mathcal{V}(\mathcal{L}):=K(W)$, where
$W:=\\{2\boldsymbol{y}/\|\boldsymbol{y}\|^{2}\ :\
\boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}\\}$. We therefore
define $\psi(\boldsymbol{y}):=2\boldsymbol{y}/\|\boldsymbol{y}\|^{2}$. We will
need the following technical claim, which shows how $\psi$ behaves under small
linear perturbations.

######  Claim 3.7.

For any $\boldsymbol{y}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}$, matrix
$M\in\mathbb{R}^{n\times n}$, and sufficiently small $\varepsilon>0$, we have

$\|M_{\varepsilon}^{-1}\psi(\boldsymbol{y})-\psi(\phi_{\boldsymbol{y}}(M_{\varepsilon}\boldsymbol{y}))\|\leq
O(\varepsilon^{2})\;,$

where $M_{\varepsilon}:=I_{n}+\varepsilon M$ and the $O(\varepsilon^{2})$
notation hides dependence on $\boldsymbol{y}$ and $\|M\|$.

###### Proof.

We have

$M_{\varepsilon}^{-1}\psi(\boldsymbol{y})=(I_{n}-\varepsilon
M)\psi(\boldsymbol{y})+O(\varepsilon^{2})\cdot\boldsymbol{u}=2\cdot\frac{\boldsymbol{y}-\varepsilon
M\boldsymbol{y}}{\|\boldsymbol{y}\|^{2}}+O(\varepsilon^{2})\cdot\boldsymbol{u}\;,$

where $\boldsymbol{u}\in\mathbb{R}^{n}$ is some unit vector that depends on
$\boldsymbol{y}$ and $M$. Similarly, we have

$\displaystyle\psi(\phi_{\boldsymbol{y}}(M_{\varepsilon}\boldsymbol{y}))$
$\displaystyle=2\cdot\frac{\phi_{\boldsymbol{y}}(M_{\varepsilon}\boldsymbol{y})}{\|M_{\varepsilon}\boldsymbol{y}\|^{2}}$
$\displaystyle=2\cdot\frac{\boldsymbol{y}+2\varepsilon\langle\boldsymbol{y},M\boldsymbol{y}\rangle\boldsymbol{y}/\|\boldsymbol{y}\|^{2}-\varepsilon
M\boldsymbol{y}}{\|\boldsymbol{y}\|^{2}+2\varepsilon\langle\boldsymbol{y},M\boldsymbol{y}\rangle+\varepsilon^{2}\|M\boldsymbol{y}\|^{2}}$
$\displaystyle=2\cdot\frac{(\boldsymbol{y}-\varepsilon
M\boldsymbol{y})\cdot(1+2\varepsilon\langle\boldsymbol{y},M\boldsymbol{y}\rangle/\|\boldsymbol{y}\|^{2})}{\|\boldsymbol{y}\|^{2}\cdot(1+2\varepsilon\langle\boldsymbol{y},M\boldsymbol{y}\rangle/\|\boldsymbol{y}\|^{2})}+O(\varepsilon^{2})\cdot\boldsymbol{u}^{\prime}$
$\displaystyle=2\cdot\frac{\boldsymbol{y}-\varepsilon
M\boldsymbol{y}}{\|\boldsymbol{y}\|^{2}}+O(\varepsilon^{2})\cdot\boldsymbol{u}^{\prime}\;,$

where $\boldsymbol{u}^{\prime}$ is some unit vector that depends on
$\boldsymbol{y}$ and $M$. The result follows. ∎

With this, we can prove the analogue of Claim 3.6 for $K(\psi(Y))$ instead of
$K(W)$. (Note the similarity between the set $Y^{\prime}$ here and the set
$W^{\prime\prime}$ in Corollary 3.4.)

######  Lemma 3.8.

For any finite set
$Y:=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{k}\\}\subset\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}$
such that $K(\psi(Y))$ is a polytope, linear transformation
$M\in\mathbb{R}^{n\times n}$, and sufficiently small $\varepsilon>0$,

$\operatorname{vol}\big{(}(M_{\varepsilon}K(\psi(Y)))\mathbin{\triangle}K(\psi(Y^{\prime}))\big{)}\leq
O(\varepsilon^{2})\;,$

where $M_{\varepsilon}:=I_{n}+\varepsilon M$,
$Y^{\prime}:=\\{\phi_{\boldsymbol{y}_{1}}(M_{\varepsilon}^{T}\boldsymbol{y}_{1}),\ldots,\phi_{\boldsymbol{y}_{k}}(M_{\varepsilon}^{T}\boldsymbol{y}_{k})\\}$,
and the $O(\varepsilon^{2})$ term hides dependence on $Y$ and $\|M\|$.

###### Proof.

By Claim 3.6, $M_{\varepsilon}K(\psi(Y))=K(M_{\varepsilon}^{-T}\psi(Y))$. And,
by Claim 3.7, the vectors in $\psi(Y^{\prime})$ differ from the vectors in
$M_{\varepsilon}^{-T}\psi(Y)$ by vectors of length $O(\varepsilon^{2})$. The
result then follows from Claim 3.5. ∎

###  3.3 Gradient equivalence for polytopes with normally symmetric facets

We can now prove a more general variant of Theorem 3.1.

######  Theorem 3.9.

For any continuously differentiable function $f:\mathbb{R}^{\geq
0}\to\mathbb{R}$ and finite set
$Y:=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{k}\\}\subset\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}$
such that $K(\psi(Y))$ is a polytope with normally symmetric facets, let

$g(A):=\frac{1}{|\det(A)|}\cdot\int_{K(\psi(A^{T}Y))}f(\|\boldsymbol{x}\|^{2}){\rm
d}\boldsymbol{x}\text{, \ and \
}h(A):=\frac{1}{|\det(A)|}\cdot\int_{AK(\psi(Y))}f(\|\boldsymbol{x}\|^{2}){\rm
d}\boldsymbol{x}\;.$

Then, $g$ and $h$ are differentiable at $A=I_{n}$, with

$\nabla_{A}g(A)|_{A=I_{n}}=\nabla_{A}h(A)|_{A=I_{n}}=2\int_{K(\psi(Y))}f^{\prime}(\|\boldsymbol{x}\|^{2})\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}\;,$

where $f^{\prime}(x):=\frac{{\rm d}}{{\rm d}x}f(x)$.

###### Proof.

Since $f$ is continuous and we are only interested in its value over a bounded
region, we may assume without loss of generality that $f$ is bounded. I.e.,
$|f(x)|\leq C_{f}$ for some finite $C_{f}>0$. We have already computed the
gradient of $h$ in Claim 3.2, so we only need to show that
$\nabla_{A}g(A)|_{A=I_{n}}=\nabla_{A}h(A)|_{A=I_{n}}$. For a convex body
$K\subset\mathbb{R}^{n}$, let
$F(K):=\int_{K}f(\|x\|)^{2}{\rm}d\boldsymbol{x}$. (E.g.,
$g(A)=F(K(\psi(A^{T}Y)))/|\det(A)|$ and $h(A)=F(AK(\psi(Y)))/|\det(A)|$.)

Let $\varepsilon>0$ be sufficiently small, and let $M\in\mathbb{R}^{n\times
n}$ such that $\|M^{T}\boldsymbol{y}_{i}\|\leq 1$ and
$\|\psi(\boldsymbol{y}_{i}+\varepsilon
M^{T}\boldsymbol{y}_{i})-\psi(\boldsymbol{y}_{i})\|\leq\varepsilon$ for all
$i$. Let $M_{\varepsilon}:=I_{n}+\varepsilon M$. It suffices to show that

$\big{|}\det(M_{\varepsilon})g(M_{\varepsilon})-\det(M_{\varepsilon})h(M_{\varepsilon})\big{|}=\big{|}F(K(\psi(M_{\varepsilon}^{T}Y)))-F(M_{\varepsilon}K(\psi(Y)))\big{|}\leq
O(\varepsilon^{2})\;.$

We first move from $M_{\varepsilon}K(\psi(Y))$ to $K(\psi(Y^{\prime}))$, where
$Y^{\prime}:=\\{\phi_{\boldsymbol{y}_{1}}(M_{\varepsilon}^{T}\boldsymbol{y}_{1}),\ldots,\phi_{\boldsymbol{y}_{k}}(M_{\varepsilon}^{T}\boldsymbol{y}_{k})\\}$:

$\big{|}F(M_{\varepsilon}K(\psi(Y)))-F(K(\psi(Y^{\prime})))\big{|}\leq
C_{f}\cdot\operatorname{vol}((M_{\varepsilon}K(\psi(Y)))\mathbin{\triangle}K(\psi(Y^{\prime})))\leq
O(\varepsilon^{2})\;,$

where the last inequality follows from Lemma 3.8.

Let $\boldsymbol{w}_{i}:=\psi(\boldsymbol{y}_{i})$ and
$W:=\\{\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{k}\\}$. Since the cones
$R_{W,\boldsymbol{w}_{i}}$ cover space, we have

$\displaystyle\big{|}F(K(\psi(Y^{\prime})))-F(K(\psi(M_{\varepsilon}^{T}Y)))\big{|}\leq\sum_{i}\big{|}F(R_{W,\boldsymbol{w}_{i}}\cap
K(\psi(Y^{\prime})))-F(R_{W,\boldsymbol{w}_{i}}\cap
K(\psi(M_{\varepsilon}^{T}Y)))\big{|}\;.$

Let $\overline{R}_{i}:=\overline{R}_{W,\boldsymbol{w}_{i},\varepsilon}$ be the
“protected cones” from Lemma 3.3. Then,

$\displaystyle\big{|}F(R_{W,\boldsymbol{w}_{i}}\cap
K(\psi(Y^{\prime})))-F(R_{W,\boldsymbol{w}_{i}}\cap
K(\psi(M_{\varepsilon}^{T}Y)))\big{|}$
$\displaystyle\leq\big{|}F(\overline{R}_{i}\cap
K(\psi(Y^{\prime})))-F(\overline{R}_{i}\cap
K(\psi(M_{\varepsilon}^{T}Y)))\big{|}+C_{f}\cdot\operatorname{vol}\big{(}(R_{W,\boldsymbol{w}_{i}}\setminus\overline{R}_{i})\cap(K(\psi(Y^{\prime}))\mathbin{\triangle}K(\psi(M_{\varepsilon}^{T}Y))\big{)}$
$\displaystyle\leq\big{|}F(\overline{R}_{i}\cap
K(\psi(Y^{\prime})))-F(\overline{R}_{i}\cap
K(\psi(M_{\varepsilon}^{T}Y)))\big{|}+O(\varepsilon^{2})\;,$

where we have applied Item 2 of Lemma 3.3 by noting that

$\displaystyle\operatorname{vol}\big{(}(R_{W,\boldsymbol{w}_{i}}\setminus\overline{R}_{i})\cap(K(\psi(Y^{\prime}))\mathbin{\triangle}K(\psi(M_{\varepsilon}^{T}Y))\big{)}$
$\displaystyle\leq\operatorname{vol}\big{(}(R_{W,\boldsymbol{w}_{i}}\setminus\overline{R}_{i})\cap(K(\psi(M_{\varepsilon}^{T}Y))\mathbin{\triangle}K(\psi(Y)))\big{)}$
$\displaystyle\qquad+\operatorname{vol}\big{(}(R_{W,\boldsymbol{w}_{i}}\setminus\overline{R}_{i})\cap(K(\psi(Y^{\prime}))\mathbin{\triangle}K(\psi(Y)))\big{)}$
$\displaystyle\leq O(\varepsilon^{2})\;.$

Finally, we claim that

$F(\overline{R}_{i}\cap K(\psi(Y^{\prime})))=F(\overline{R}_{i}\cap
K(\psi(M_{\varepsilon}^{T}Y)))\;.$

Indeed, by Corollary 3.4, we have that $\overline{R}_{i}\cap
K(\psi(M_{\varepsilon}^{T}Y))=\phi_{\boldsymbol{w}_{i}}(\overline{R}_{i}\cap
K(\psi(Y^{\prime})))$. (Here, we have used the fact that
$\phi_{\boldsymbol{y}_{i}}=\phi_{\boldsymbol{w}_{i}}$ together with the fact
that $\phi_{\boldsymbol{w}_{i}}$ commutes with $\psi$.) Recalling that
$\phi_{\boldsymbol{w}_{i}}$ is an isometry (and that it therefore preserves
volume), we have

$F(\overline{R}_{i}\cap K(\psi(Y^{\prime})))=\int_{\overline{R}_{i}\cap
K(\psi(Y^{\prime}))}f(\|\phi_{\boldsymbol{w}_{i}}(\boldsymbol{x})\|^{2}){\rm
d}\boldsymbol{x}=F(\phi_{\boldsymbol{w}_{i}}(\overline{R}_{i}\cap
K(\psi(Y^{\prime}))))=F(\overline{R}_{i}\cap
K(\psi(M_{\varepsilon}^{T}Y)))\;,$

as claimed. Combining everything together gives the result. ∎

###  3.4 Proof of Theorem 3.1

We now prove Theorem 3.1 as a relatively straightforward corollary of Theorem
3.9. To do this, we first recall the following well known fact.

######  Lemma 3.10.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$, the Voronoi cell
$\mathcal{V}(\mathcal{L})$ has normally symmetric facets.

###### Proof.

Let
$W:=\psi(\mathcal{L}\setminus\\{\boldsymbol{0}\\})=\\{2\boldsymbol{y}/\|\boldsymbol{y}\|^{2}\
:\ \boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}\\}$ so that
$\mathcal{V}(\mathcal{L})=K(W)$, and let
$\boldsymbol{y},\boldsymbol{y}^{\prime}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}$
be distinct. Let $\boldsymbol{w}:=2\boldsymbol{y}/\|\boldsymbol{y}\|^{2}\in
W$, and
$\boldsymbol{w}^{\prime}:=2\boldsymbol{y}^{\prime}/\|\boldsymbol{y}^{\prime}\|^{2}\in
W$ be the corresponding points in $\boldsymbol{w}$. Suppose $\boldsymbol{x}\in
R_{W,\boldsymbol{w}}$. It suffices to show that
$\langle\boldsymbol{w}^{\prime},\phi_{\boldsymbol{w}}(\boldsymbol{x})\rangle\leq\langle\boldsymbol{w},\phi_{\boldsymbol{w}}(\boldsymbol{x})\rangle$.
Equivalently, it suffices to show that

$\frac{\langle\boldsymbol{y}^{\prime},\phi_{\boldsymbol{y}}(\boldsymbol{x})\rangle}{\|\boldsymbol{y}^{\prime}\|^{2}}\leq\frac{\langle\boldsymbol{y},\phi_{\boldsymbol{y}}(\boldsymbol{x})\rangle}{\|\boldsymbol{y}\|^{2}}\;.$

We consider the inner product of $\boldsymbol{y}-\boldsymbol{y}^{\prime}$ with
$\boldsymbol{x}$. In particular, since
$\boldsymbol{y}-\boldsymbol{y}^{\prime}$ is a non-zero lattice vector and
$\boldsymbol{x}\in R_{W,\boldsymbol{w}}$, we have

$\langle\boldsymbol{y}-\boldsymbol{y}^{\prime},\boldsymbol{x}\rangle\leq\|\boldsymbol{y}-\boldsymbol{y}^{\prime}\|^{2}\cdot\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle}{\|\boldsymbol{y}\|^{2}}=\Big{(}1-\frac{2\langle\boldsymbol{y},\boldsymbol{y}^{\prime}\rangle}{\|\boldsymbol{y}\|^{2}}+\frac{\|\boldsymbol{y}^{\prime}\|^{2}}{\|\boldsymbol{y}\|^{2}}\Big{)}\cdot\langle\boldsymbol{y},\boldsymbol{x}\rangle\;.$

Rearranging, we have

$2\cdot\frac{\langle\boldsymbol{y},\boldsymbol{y}^{\prime}\rangle\langle\boldsymbol{y},\boldsymbol{x}\rangle}{\|\boldsymbol{y}\|^{2}\|\boldsymbol{y}^{\prime}\|^{2}}-\frac{\langle\boldsymbol{y}^{\prime},\boldsymbol{x}\rangle}{\|\boldsymbol{y}^{\prime}\|^{2}}\leq\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle}{\|\boldsymbol{y}\|^{2}}\;.$

The result follows by noting that the right-hand side is equal to
$\frac{\langle\boldsymbol{y},\phi_{\boldsymbol{y}}(\boldsymbol{x})\rangle}{\|\boldsymbol{y}\|^{2}}$
and the left-hand side is equal to
$\frac{\langle\boldsymbol{y}^{\prime},\phi_{\boldsymbol{y}}(\boldsymbol{x})\rangle}{\|\boldsymbol{y}^{\prime}\|^{2}}$.
∎

With this, we can prove the theorem.

###### Proof of Theorem 3.1.

Let $U\subset\mathrm{GL}_{n}(\mathbb{R})$ be some bounded open neighborhood
around $I_{n}$. It suffices to show that there exists a _finite_ set $Y$
satisfying that for all $A\in U$, the Voronoi cell
$\mathcal{V}(A^{T}\mathcal{L})$ is equal to $K(\psi(A^{T}Y))$. (Without the
finiteness assumption, we could simply take
$Y=\mathcal{L}\setminus\\{\boldsymbol{0}\\}$.) The result then follows from
Theorem 3.9 applied to $Y$ together with Lemma 3.10.

Note that we only need to take $\boldsymbol{y}\in Y$ if
$\|A^{T}\boldsymbol{y}\|\leq 2\mu(A^{T}\mathcal{L})$ for some $A\in U$. Let
$s:=\sup_{A\in U}\mu(A^{T}\mathcal{L})$, and notice that $s<\infty$ since $U$
is bounded and the covering radius function $\mu$ is continuous. Let
$\alpha:=\inf_{A\in
U,\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{0}\\}}\|A^{T}\boldsymbol{x}\|/\|\boldsymbol{x}\|$.
We may take $U$ small enough that $\alpha>0$. Then, let
$Y:=(\mathcal{L}\setminus\\{\boldsymbol{0}\\})\cap(2s/\alpha)B_{2}^{n}$ and
notice that it is a finite set. If $\|A^{T}\boldsymbol{y}\|\leq
2\mu(A^{T}\mathcal{L})\leq 2s$ for some $A\in U$, then
$\|\boldsymbol{y}\|\leq\|A^{T}\boldsymbol{y}\|/\alpha\leq 2s/\alpha$. So,
$K(\psi(A^{T}Y))=\mathcal{V}(A^{T}\mathcal{L})$, as needed. ∎

##  4 Proof of the Reverse Minkowski Theorem

In this section, we prove our main theorem, Theorem 1.2. Recall that the
Voronoi cell $\mathcal{V}(\mathcal{L})$ of a lattice
$\mathcal{L}\subset\mathbb{R}^{n}$ is the symmetric polytope of all vectors in
$\mathbb{R}^{n}$ that are closer to $\boldsymbol{0}$ than to any other lattice
vector,

$\mathcal{V}(\mathcal{L}):=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\
\forall\boldsymbol{y}\in\mathcal{L},\
\langle\boldsymbol{y},\boldsymbol{x}\rangle\leq\|\boldsymbol{y}\|^{2}/2\\}\;.$

Also recall that for parameter $s>0$, $\gamma_{s}(\cdot)$ is the Gaussian
measure on $\mathbb{R}^{n}$ given by

$\gamma_{s}(S):=\int_{S/s}e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm d}\boldsymbol{x}$

for any measurable set $S\subseteq\mathbb{R}^{n}$. (Some authors prefer to
parametrize $\gamma$ in terms of the standard deviation
$\sigma:=s/\sqrt{2\pi}$.) We are interested in the Gaussian mass
$\gamma_{s}(\mathcal{V}(\mathcal{L}))$ of the Voronoi cell because, as the
following lemma due to Chung, Dadush, Liu, and Peikert shows, this can be used
to obtain an upper bound on the mass $\rho_{s}(\mathcal{L})$ of the lattice
itself [CDLP13]. We include a proof for completeness.

######  Lemma 4.1 ([CDLP13, Lemma 3.4]).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and $s>0$,

$\rho_{s}(\mathcal{L})\cdot\gamma_{s}(\mathcal{V}(\mathcal{L}))\leq 1\;.$

###### Proof.

By scaling appropriately, we may assume without loss of generality that $s=1$.
Note that the Voronoi cell tiles space with respect to $\mathcal{L}$. I.e.,
$\bigcup_{\boldsymbol{y}\in\mathcal{L}}(\mathcal{V}(\mathcal{L})+\boldsymbol{y})=\mathbb{R}^{n}$,
where the union is disjoint except on a measure-zero set. So,

$\displaystyle 1$
$\displaystyle=\int_{\mathbb{R}^{n}}e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm
d}\boldsymbol{x}$
$\displaystyle=\sum_{\boldsymbol{y}\in\mathcal{L}}\int_{\mathcal{V}(\mathcal{L})}e^{-\pi\|\boldsymbol{y}+\boldsymbol{t}\|^{2}}{\rm
d}\boldsymbol{t}$
$\displaystyle=\sum_{\boldsymbol{y}\in\mathcal{L}}e^{-\pi\|\boldsymbol{y}\|^{2}}\int_{\mathcal{V}(\mathcal{L})}e^{-\pi\|\boldsymbol{t}\|^{2}}e^{2\pi\langle\boldsymbol{y},\boldsymbol{t}\rangle}{\rm
d}\boldsymbol{t}$
$\displaystyle=\sum_{\boldsymbol{y}\in\mathcal{L}}\rho(\boldsymbol{y})\int_{\mathcal{V}(\mathcal{L})}e^{-\pi\|\boldsymbol{t}\|^{2}}\cosh(2\pi\langle\boldsymbol{y},\boldsymbol{t}\rangle){\rm
d}\boldsymbol{t}$
$\displaystyle\geq\sum_{\boldsymbol{y}\in\mathcal{L}}\rho(\boldsymbol{y})\int_{\mathcal{V}(\mathcal{L})}e^{-\pi\|\boldsymbol{t}\|^{2}}{\rm
d}\boldsymbol{t}$
$\displaystyle=\rho(\mathcal{L})\gamma(\mathcal{V}(\mathcal{L}))\;,$

where the fourth line follows from the fact that the Voronoi cell is
symmetric. ∎

Therefore, in order to prove Theorem 1.2, it suffices to show that
$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq 2/3$ for every lattice
$\mathcal{L}\subset\mathbb{R}^{n}$ with $\det(\mathcal{L}^{\prime})\geq 1$ for
all sublattices $\mathcal{L}^{\prime}\subseteq\mathcal{L}$, where $t:=10(\log
n+2)$. As we explained in the introduction, we will reduce this to studying
local minima of the function
$\mathcal{L}\mapsto\gamma_{1/t}(\mathcal{V}(\mathcal{L}))$ over the set of
determinant-one lattices. (We do not know whether such local minima actually
exist.)

In Section 4.1, we collect some facts about the Gaussian mass of convex
bodies. In Section 4.2, we apply these facts to the Voronoi cell to prove
Theorem 1.2.

###  4.1 Gaussian mass of convex bodies

We say that a measurable set $U\subset\mathbb{R}^{n}$ is in _isotropic
Gaussian position for parameter $s$_ if

$\int_{U/s}e^{-\pi\|\boldsymbol{x}\|^{2}}\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}=\alpha\cdot I_{n}$

for some scalar $\alpha>0$. If $s=1$, we simply say that $U$ is in _isotropic
Gaussian position_. Such a position has been considered elsewhere (e.g.,
[Bob11]), but as far as we know, it did not previously have a name.

The main goal of this section is to prove the following theorem. We will also
include a standard fact in Lemma 4.11 towards the end of this section.

######  Theorem 4.2.

For any symmetric convex body $K\subset\mathbb{R}^{n}$ with
$\operatorname{vol}(K)\geq 1$, if $K$ is in isotropic Gaussian position for
some parameter $0<s\leq 1/t$, then $\gamma_{s}(K)\geq 2/3$ where $t:=10(\log
n+2)$.

Our proof of Theorem 4.2 proceeds in two parts. The first part is a result due
to Bobkov [Bob11] (Proposition 4.3 below), showing that an isotropic Gaussian
position of a convex body has maximal Gaussian mass. We include a proof for
completeness. In the second part (Theorem 4.6 below), we show that any volume-
one convex body $K\subset\mathbb{R}^{n}$ has a position such that
$\gamma_{s}(K)\geq 2/3$.

######  Proposition 4.3 ([Bob11, Proposition 3.1]).

For any symmetric convex body $K\subset\mathbb{R}^{n}$, if $K$ is in isotropic
Gaussian position for some parameter $s>0$, then
$\gamma_{s}(K)\geq\gamma_{s}(AK)$ for any determinant-one matrix
$A\in\mathrm{SL}_{n}(\mathbb{R})$.

We start by observing that isotropic Gaussian positions correspond to critical
points of the Gaussian mass function over positions.

######  Fact 4.4.

For any measurable set $U\subset\mathbb{R}^{n}$, let

$h(A):=\frac{\gamma(AU)}{|\det(A)|}\;,$

where $A\in\mathrm{GL}_{n}(\mathbb{R})$ ranges over the non-singular matrices.
Then,

$\nabla_{A}h(A)|_{A=I_{n}}=-2\pi\int_{U}e^{-\pi\|\boldsymbol{x}\|^{2}}\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}\;.$

In particular, $A\mapsto\gamma(AU)$ has a critical point at $I_{n}$ when
restricted to determinant-one matrices if and only if $U$ is in isotropic
Gaussian position.

###### Proof.

Simply apply Fact 3.2 with $f(x)=e^{-\pi x}$ and recall that a scalar-valued
differentiable function over matrices has a critical point at $I_{n}$ when
restricted to the set of determinant-one matrices if and only if its gradient
is proportional to the identity. ∎

We will also need the following result due to Cordero-Erausquin, Fradelizi,
and Maurey [CFM04], which is related to the so-called (B) conjecture due to
Banaszczyk (see [Lat02]).

######  Theorem 4.5 ([CFM04]).

For any symmetric convex body $K\subset\mathbb{R}^{n}$, the function
$\gamma(e^{D}K)$, where $D\in\mathbb{R}^{n\times n}$ ranges over all diagonal
matrices, is log-concave.

###### Proof of Proposition 4.3.

By scaling $K$, we may assume that $s=1$. Let $A=UDV$ be the singular-value
decomposition of $A$. (I.e., $D$ is a diagonal matrix and $U$ and $V$ are
orthogonal matrices.) Note that the Gaussian measure is invariant under
orthogonal transformations, so that $\gamma(AK)=\gamma(UDVK)=\gamma(DVK)$. Let
$K^{\prime}:=VK$, and note that $\gamma(K^{\prime})=\gamma(K)$ and that
$K^{\prime}$ is in isotropic Gaussian position, since $V$ is an orthogonal
transformation.

Let $\widehat{h}(M):=\gamma(e^{M}K^{\prime})/|\det(e^{M})|$. By Fact 4.4 and
the chain rule, we have

$\nabla_{M}\widehat{h}(M)|_{M=0}=-2\pi\int_{K^{\prime}}e^{-\pi\|\boldsymbol{x}\|^{2}}\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}=-\alpha\cdot I_{n}\;$

for some scalar $\alpha\in\mathbb{R}$, where the second equality is simply the
fact that $K^{\prime}$ is in isotropic Gaussian position. Let
$X\subset\mathbb{R}^{n\times n}$ be the set of trace-zero diagonal matrices.
Then, the function $\widehat{h}_{X}$ obtained by restricting $\widehat{h}$ to
$X$ has a critical point at zero, since $\mbox{\rm Tr}(I_{n}M)=0$ for any
$M\in X$. By Theorem 4.5, $\widehat{h}_{X}$ is log-concave, so that this
critical point must be a global maximum. Therefore,
$\gamma(AK)=\gamma(DK^{\prime})\leq\gamma(K^{\prime})=\gamma(K)$, as needed. ∎

We now proceed to the second part of the proof of Theorem 4.2.

######  Theorem 4.6.

For any symmetric convex body $K\subset\mathbb{R}^{n}$ with volume one, there
is a determinant-one matrix $A\in\mathrm{SL}_{n}(\mathbb{R})$ such that
$\gamma_{1/t}(AK)\geq 2/3$, where $t:=2\sqrt{3e}(\log_{2}n+2)<10(\log n+2)$.

The proof is based on an important theorem that follows from the work of
Figiel and Tomczak-Jaegermann [FT79], Lewis [Lew79], and Pisier [Pis82]. We
first need some definitions. Recall that any symmetric convex body
$K\subset\mathbb{R}^{n}$ defines a norm $\|\cdot\|_{K}$ given by

$\|\boldsymbol{x}\|_{K}:=\inf\\{s\geq 0\ :\ \boldsymbol{x}\in sK\\}\;.$

We then define the $\ell$-norm on $\mathbb{R}^{n\times n}$ by

$\ell_{K}(A):=\Big{(}\int_{\mathbb{R}^{n}}\|A\boldsymbol{x}\|_{K}^{2}{\rm
d}\gamma(\boldsymbol{x})\Big{)}^{1/2}\;,$

where ${\rm d}\gamma(\boldsymbol{x}):=e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm
d}\boldsymbol{x}$. Finally, we recall that a convex body $K$ has a _polar_
given by

$K^{\circ}:=\\{\boldsymbol{x}\in\mathbb{R}^{n}\ :\ \forall\boldsymbol{y}\in
K,\ \langle\boldsymbol{y},\boldsymbol{x}\rangle\leq 1\\}\;,$

which is itself a convex body.

######  Theorem 4.7 ([FT79, Lew79, Pis82]; see [Dad12b, Theorem 4.4.3]).

For any symmetric convex body $K\subset\mathbb{R}^{n}$, there exists a
determinant-one matrix $A\in\mathrm{SL}_{n}(\mathbb{R})$ such that

$\ell_{K}(A)\ell_{K^{\circ}}(A^{-T})\leq n(\log_{2}n+2)/\pi\;.$

######  Lemma 4.8.

For any symmetric convex body $K\subset\mathbb{R}^{n}$ with volume one and any
determinant-one matrix $A\in\mathrm{SL}_{n}(\mathbb{R})$, we have

$\ell_{K^{\circ}}(A^{-T})\geq\sqrt{n/(2\pi)}\cdot r_{n}>n/(2\pi\sqrt{e})\;.$

where $r_{n}:=\operatorname{vol}(B_{2}^{n})^{-1/n}>\sqrt{n/(2\pi e)}$ is the
radius such that $\operatorname{vol}(r_{n}B_{2}^{n})=1$.

###### Proof.

By replacing $K$ with $AK$, we may assume without loss of generality that
$A=I_{n}$. Unpacking the definitions, we see that

$\displaystyle\ell_{K^{\circ}}(I_{n})^{2}$
$\displaystyle=\int_{\mathbb{R}^{n}}\|\boldsymbol{x}\|_{K^{\circ}}^{2}{\rm
d}\gamma(\boldsymbol{x})$
$\displaystyle=\int_{\mathbb{R}^{n}}\sup_{\boldsymbol{y}\in
K}\langle\boldsymbol{y},\boldsymbol{x}\rangle^{2}{\rm
d}\gamma(\boldsymbol{x})$
$\displaystyle=\Big{(}\int_{\mathbb{R}^{n}}\|\boldsymbol{x}\|^{2}{\rm
d}\gamma(\boldsymbol{x})\Big{)}\cdot\Big{(}\int_{\mathbb{R}^{n}}\sup_{\boldsymbol{y}\in
K}\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle^{2}}{\|\boldsymbol{x}\|^{2}}{\rm
d}\gamma(\boldsymbol{x})\Big{)}$
$\displaystyle=\frac{n}{2\pi}\cdot\int_{\mathbb{R}^{n}}\sup_{\boldsymbol{y}\in
K}\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle^{2}}{\|\boldsymbol{x}\|^{2}}{\rm
d}\gamma(\boldsymbol{x})\;,$

where we have used the fact that the Gaussian is spherically symmetric. By
Jensen’s inequality, we have

$\int_{\mathbb{R}^{n}}\sup_{\boldsymbol{y}\in
K}\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle^{2}}{\|\boldsymbol{x}\|^{2}}{\rm
d}\gamma(\boldsymbol{x})\geq\Big{(}\int_{\mathbb{R}^{n}}\sup_{\boldsymbol{y}\in
K}\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle}{\|\boldsymbol{x}\|}{\rm
d}\gamma(\boldsymbol{x})\Big{)}^{2}\;,$

and by Urysohn’s inequality (see [AGM15, Theorem 1.5.11]), we have

$\int_{\mathbb{R}^{n}}\sup_{\boldsymbol{y}\in
K}\frac{\langle\boldsymbol{y},\boldsymbol{x}\rangle}{\|\boldsymbol{x}\|}{\rm
d}\gamma(\boldsymbol{x})\geq r_{n}\;.$

The result follows by combining everything together. ∎

The following corollary is an immediate consequence of the previous two
results.

######  Corollary 4.9.

For any symmetric convex body $K\subset\mathbb{R}^{n}$ with volume one, there
exists a determinant-one matrix $A\in\mathrm{SL}_{n}(\mathbb{R})$ such that
$\ell_{K}(A)\leq 2\sqrt{e}(\log_{2}n+2)$.

###### Proof of Theorem 4.6.

By Corollary 4.9, there exists an $A\in\mathrm{SL}_{n}(\mathbb{R})$ such that

$\ell_{K}(A)^{2}=\int_{\mathbb{R}^{n}}\|A\boldsymbol{x}\|_{K}^{2}{\rm
d}\gamma(\boldsymbol{x})\leq(2\sqrt{e}(\log_{2}n+2))^{2}\;.$

We will use $A^{-1}$ as our matrix. Note that

$\gamma_{1/t}(A^{-1}K)=\int_{\mathbb{R}^{n}}1_{\|\boldsymbol{x}\|_{A^{-1}K}\leq
t}{\rm
d}\gamma(\boldsymbol{x})=\int_{\mathbb{R}^{n}}1_{\|A\boldsymbol{x}\|_{K}\leq
t}{\rm
d}\gamma(\boldsymbol{x})=1-\int_{\mathbb{R}^{n}}1_{\|A\boldsymbol{x}\|_{K}>t}{\rm
d}\gamma(\boldsymbol{x})\;.$

The result then follows by Markov’s inequality, which tells us that

$\int_{\mathbb{R}^{n}}1_{\|A\boldsymbol{x}\|_{K}>t}{\rm
d}\gamma(\boldsymbol{x})\leq\frac{1}{t^{2}}\cdot\int_{\mathbb{R}^{n}}\|A\boldsymbol{x}\|_{K}^{2}{\rm
d}\gamma(\boldsymbol{x})\leq\frac{1}{t^{2}}\cdot(2\sqrt{e}(\log_{2}n+2))^{2}=\frac{1}{3}\;.\qed$

We now obtain Theorem 4.2 as an immediate corollary of Proposition 4.3 and
Theorem 4.6.

###### Proof of Theorem 4.2.

By Theorem 4.6, there is some $A\in\mathrm{SL}_{n}(\mathbb{R})$ such that
$\gamma_{s}(AK)\geq 2/3$, and by Proposition 4.3,
$\gamma_{s}(K)\geq\gamma_{s}(AK)\geq 2/3$, as needed. ∎

#### Concentration of measure.

We will also need a standard lemma about the concentration of Gaussian
measure. We first recall the Gaussian isoperimetric inequality [SC74, Bor75]
(see also [AGM15, Theroem 3.1.9]).

######  Theorem 4.10 (Gaussian isoperimetric inequality).

For any measurable set $U\subset\mathbb{R}^{n}$ and any $\tau>0$,

$\gamma(U+\tau B_{2}^{n})\geq\int_{-\infty}^{\sigma+\tau}e^{-\pi x^{2}}{\rm
d}x\;,$

where $\sigma\in[-\infty,\infty]$ is such that $\int_{-\infty}^{\sigma}e^{-\pi
x^{2}}{\rm d}x=\gamma(U)$.

Recall that the _inradius_ of a convex body $K$ is defined as $\max\\{r\geq 0\
:\ rB_{2}^{n}\subseteq K\\}$, i.e., the radius of the largest ball contained
in the body.

######  Lemma 4.11.

If $K\subset\mathbb{R}^{n}$ is a convex body with $\gamma_{1/t}(K)\geq 2/3$
for some $t>0$, then

$\gamma_{1/(t+\tau)}(K)\geq 1-e^{-\pi r^{2}\tau^{2}}/3\;,$

for any $\tau\geq 0$, where $r\geq 0$ is the inradius of $K$.

###### Proof.

Note that

$\gamma_{1/(t+\tau)}(K)=\gamma((t+\tau)K)\geq\gamma(tK+r\tau B_{2}^{n})\;,$

since by definition $rB_{2}^{n}\subseteq K$. Applying Theorem 4.10, we have

$\gamma_{1/(t+\tau)}(K)\geq\int_{-\infty}^{\sigma+r\tau}e^{-\pi x^{2}}{\rm
d}x\;,$

where $\sigma>0$ is such that $\int_{-\infty}^{\sigma}e^{-\pi x^{2}}{\rm
d}x=2/3$. Finally, we note that

$\int_{-\infty}^{\sigma+r\tau}e^{-\pi r^{2}}{\rm
d}x=1-\int_{\sigma+r\tau}^{\infty}e^{-\pi x^{2}}{\rm d}x\geq 1-e^{-\pi
r^{2}\tau^{2}}\int_{\sigma}^{\infty}e^{-\pi x^{2}}{\rm d}x=1-e^{-\pi
r^{2}\tau^{2}}/3\;,$

where the inequality follows from the fact that $\sigma$, $\tau$, and $r$ are
non-negative, so that $(x+r\tau)^{2}\geq x^{2}+r^{2}\tau^{2}$ for all
$x\geq\sigma$. The result follows. ∎

###  4.2 Proof of Theorem 1.2

We now use Theorem 3.1 and Theorem 4.2 to characterize local minima of
$\gamma_{s}(\mathcal{V}(\mathcal{L}))$.

######  Theorem 4.12.

If $\mathcal{L}\subset\mathbb{R}^{n}$ corresponds to a local minimum (or
maximum) of $\gamma_{1/t}(\mathcal{V}(\mathcal{L}))$ over the set of
determinant-one lattices, then $\mathcal{V}(\mathcal{L})$ is in isotropic
Gaussian position with parameter $1/t$, and

$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq 2/3\;,$

where $t:=10(\log n+2)$.

###### Proof.

By Theorem 3.1 with $f(x)=t^{n}\cdot e^{-\pi t^{2}x}$, we have

$\displaystyle\nabla_{A}\big{(}\gamma_{1/t}(\mathcal{V}(A^{T}\mathcal{L}))/|\det(A)|\big{)}|_{A=I_{n}}$
$\displaystyle=2\int_{\mathcal{V}(\mathcal{L})}f^{\prime}(\|\boldsymbol{x}\|^{2})\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}$ $\displaystyle=-2\pi
t^{n+2}\cdot\int_{\mathcal{V}(\mathcal{L})}e^{-\pi
t^{2}\|\boldsymbol{x}\|^{2}}\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}\;.$

Recall that $I_{n}$ corresponds to a local extremum of a differentiable
function $g(A)$ restricted to the manifold of determinant-one matrices only if
$\nabla_{A}g(A)|_{A=I_{n}}$ is a scalar multiple of the identity. So, the
above expression must be a multiple of the identity. I.e.,
$\mathcal{V}(\mathcal{L})$ is in isotropic Gaussian position. The result then
follows from Theorem 4.2. ∎

Before moving to the proof of our main theorem, we need the following claim.

######  Claim 4.13.

For any $x>1$,

$e^{-2\log^{2}x}+e^{-2\log^{2}(x/(x-1))}<1\;.$

###### Proof.

By symmetry, we may assume that $x\geq 2$. (Otherwise, we can replace $x$ with
$x/(x-1)$.) If $2\leq x\leq 2.5$, then

$e^{-2\log^{2}x}+e^{-2\log^{2}(x/(x-1))}<e^{-2\log^{2}2}+e^{-2\log^{2}(5/3)}<1\;.$

A similar computation works if $2.5\leq x\leq e$. Finally, using the fact that
$\log(x/(x-1))=-\log(1-1/x)>1/x$ for $x>1$, we have for any $x\geq e$ that

$e^{-2\log^{2}x}+e^{-2\log^{2}(x/(x-1))}<\frac{1}{x^{2}}+e^{-2/x^{2}}<\frac{1}{x^{2}}+1-\frac{1}{x^{2}}=1\;.\qed$

We now prove our main theorem in the special case when $\mathcal{L}$ is a
stable lattice. The full result will follow as a relatively straightforward
corollary.

######  Proposition 4.14.

For any stable lattice $\mathcal{L}\subset\mathbb{R}^{n}$,
$\rho_{1/t}(\mathcal{L})\leq\frac{3}{2}$, where $t:=10(\log n+2)$.

###### Proof.

By Lemma 4.1, it suffices to show that
$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq 2/3$. We assume for induction that
$\gamma_{1/(10(\log d+2))}(\mathcal{V}(\mathcal{L}^{\prime}))\geq 2/3$ for any
stable lattice $\mathcal{L}^{\prime}$ of rank $d<n$. (A quick check shows that
this is true for $d=1$.) Since the set of stable lattices is compact by Item
(ii) of Proposition 2.5 and the function
$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))$ is continuous, we may assume without
loss of generality that $\mathcal{L}$ corresponds to a global minimum of
$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))$ over the set of stable lattices. If
this global minimum is also a _local_ minimum over the set of determinant-one
lattices, then by Theorem 4.12, $\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq
2/3$, and we are done.

Otherwise, $\mathcal{L}$ lies on the boundary of the set of stable lattices.
I.e., there is some primitive sublattice
$\mathcal{L}^{\prime}\subset\mathcal{L}$ of rank $d<n$ such that
$\mathcal{L}^{\prime}$ and $\mathcal{L}/\mathcal{L}^{\prime}$ are stable. (See
Item (iv) of Proposition 2.5.) By Corollary 2.8 together with Claim 2.6, we
have

$\displaystyle\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq\gamma_{1/t}(\mathcal{V}(\mathcal{L}/\mathcal{L}^{\prime}\oplus\mathcal{L}^{\prime}))=\gamma_{1/t}(\mathcal{V}(\mathcal{L}/\mathcal{L}^{\prime}))\cdot\gamma_{1/t}(\mathcal{V}(\mathcal{L}^{\prime}))\;.$
(8)

Let $t_{1}:=10(\log d+2)$ and $t_{2}:=10(\log(n-d)+2)$. By the induction
hypothesis, we see that
$\gamma_{1/t_{1}}(\mathcal{V}(\mathcal{L}^{\prime}))\geq 2/3$ and
$\gamma_{1/t_{2}}(\mathcal{V}(\mathcal{L}/\mathcal{L}^{\prime}))\geq 2/3$. By
Lemma 4.11, we therefore have

$\gamma_{1/t}(\mathcal{V}(\mathcal{L}^{\prime}))\geq 1-\frac{1}{3}\cdot
e^{-2\log^{2}(n/d)}\text{, and
}\gamma_{1/t}(\mathcal{V}(\mathcal{L}/\mathcal{L}^{\prime}))\geq
1-\frac{1}{3}\cdot e^{-2\log^{2}(n/(n-d))}\;,$

where we have used the fact that the inradius of the Voronoi cell is
$\lambda_{1}(\mathcal{L})/2$, which is at least $1/2$ for a stable lattice
(and the constant in the exponent is very loose). Therefore, using (8),

$\displaystyle\gamma_{1/t}(\mathcal{V}(\mathcal{L}))$
$\displaystyle\geq\Big{(}1-\frac{1}{3}\cdot
e^{-2\log^{2}(n/d)}\Big{)}\cdot\Big{(}1-\frac{1}{3}\cdot
e^{-2\log^{2}(n/(n-d))}\Big{)}$
$\displaystyle>1-\frac{1}{3}\cdot\big{(}e^{-2\log^{2}(n/d)}+e^{-2\log^{2}(n/(n-d))}\big{)}$
$\displaystyle>\frac{2}{3}\;,$

where the last inequality follows from Claim 4.13 with $x:=n/d$.

So, for every stable lattice $\mathcal{L}$, we have
$\gamma_{1/t}(\mathcal{V}(\mathcal{L}))\geq 2/3$, and the result then follows
from Lemma 4.1. ∎

We now derive our main theorem as a corollary.

###### Proof of Theorem 1.2.

Let
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\cdots\subset\mathcal{L}_{k}=\mathcal{L}$
be the canonical filtration of $\mathcal{L}$. Recall from Item 2 of
Proposition 2.5 that $\alpha_{i}\cdot(\mathcal{L}_{i}/\mathcal{L}_{i-1})$ is a
stable lattice, where
$\alpha_{i}:=\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{-1/\operatorname{rank}(\mathcal{L}_{i}/\mathcal{L}_{i-1})}\leq
1$. Therefore, by Lemma 2.3,

$\rho_{1/t}(\mathcal{L})\leq\rho_{1/t}\Big{(}\bigoplus_{i=1}^{k}\mathcal{L}_{i}/\mathcal{L}_{i-1}\Big{)}\leq\rho_{1/t}\Big{(}\bigoplus_{i=1}^{k}\alpha_{i}(\mathcal{L}_{i}/\mathcal{L}_{i-1})\Big{)}\;.$

By Item (iii) of Proposition 2.5, this direct sum of stable lattices is itself
a stable lattice. The result then follows from Proposition 4.14. ∎

##  5 Bounds on $\rho_{s}(\mathcal{L})$ for all parameters and point-counting
bounds

We first give the proof of Corollary 1.4, which follows immediately from
Theorem 1.3.

###### Proof of Corollary 1.4.

For any $r>0$

$|\mathcal{L}\cap(rB_{2}^{n}+\boldsymbol{u})|\leq e^{\pi
r^{2}/s^{2}}\rho_{s}(\mathcal{L}-\boldsymbol{u})\leq e^{\pi
r^{2}/s^{2}}\rho_{s}(\mathcal{L})\;,$

where the last inequality is Claim 2.2. Item 1 then follows by plugging in
$s=1/t$ and applying Item 1 of Theorem 1.3. Item 2 follows by taking
$s=r\sqrt{2\pi/n}$ and applying Item 2 of Theorem 1.3. Finally, Item 3 follows
by taking $s=r\sqrt{2\pi/n}$ and applying Item 3 of Theorem 1.3. ∎

We now prove Theorem 1.3, which gives bounds on the Gaussian mass for all
parameters. We start with Item 1, addressing parameters $s\leq 1/t$.

######  Theorem 5.1 (Slight strengthening of Item 1 of Theorem 1.3).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$,

$\rho_{s}(\mathcal{L})\leq
1+e^{-\pi\lambda_{1}(\mathcal{L})^{2}(1/s^{2}-t^{2})}/2\leq
1+e^{-\pi(1/s^{2}-t^{2})}/2$

for any $s\leq 1/t$, where $t:=10(\log n+2)$.

###### Proof.

Note that for any $\boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}$,

$\rho_{s}(\boldsymbol{y})=\rho_{1/t}(\boldsymbol{y})\cdot
e^{-\pi\|\boldsymbol{y}\|^{2}(1/s^{2}-t^{2})}\leq\rho_{1/t}(\boldsymbol{y})e^{-\pi\lambda_{1}(\mathcal{L})^{2}(1/s^{2}-t^{2})}\;.$

The result follows by summing over all
$\boldsymbol{y}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}$ and applying
Theorem 1.2. The second inequality uses the fact that
$\lambda_{1}(\mathcal{L})\geq 1$. ∎

We now prove the “high-parameter analogue” of Theorem 1.2. The proof uses
Theorem 1.2 and duality.

######  Theorem 5.2 (Item 3 of Theorem 1.3).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$ and any parameter $s\geq t$,
$\rho_{s}(\mathcal{L})\leq 2s^{n}$ where $t:=10(\log n+2)$.

###### Proof.

Recall the Poisson Summation Formula applied to the Gaussian mass (Eq. (3)):

$\rho_{s}(\mathcal{L})=\frac{s^{n}}{\det(\mathcal{L})}\cdot\rho_{1/s}(\mathcal{L}^{*})\;.$

Assume first that $\mathcal{L}$ is stable. Then, by Theorem 1.2 and the fact
that the dual of a stable lattice is stable (Item (i) of Proposition 2.5),

$\rho_{s}(\mathcal{L})=s^{n}\cdot\rho_{1/s}(\mathcal{L}^{*})\leq
s^{n}\cdot\rho_{1/t}(\mathcal{L}^{*})\leq 2s^{n}\;.$

For a general lattice $\mathcal{L}\subset\mathbb{R}^{n}$, let
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\mathcal{L}_{1}\subset\cdots\subset\mathcal{L}_{k}=\mathcal{L}$
be the canonical filtration of $\mathcal{L}$. Recall that
$\alpha_{i}(\mathcal{L}_{i}/\mathcal{L}_{i-1})$ is stable for some
$\alpha_{i}\leq 1$. (See Item 2 of Proposition 2.5.) Then, by Lemma 2.3,

$\rho_{s}(\mathcal{L})\leq\rho_{s}\Big{(}\bigoplus\mathcal{L}_{i}/\mathcal{L}_{i-1}\Big{)}\leq\rho_{s}\Big{(}\bigoplus\alpha_{i}\cdot\mathcal{L}_{i}/\mathcal{L}_{i-1}\Big{)}\leq
2s^{n}\;,$

where the last inequality follows from the fact that the direct sum of stable
lattices is stable together with the bound proven above for stable lattices.
(See Item (iii) of Proposition 2.5.) ∎

The rest of this section is dedicated to the proof of Item 2 of Theorem 1.3.
Note that we already have a bound on $\rho_{s}(\mathcal{L})$ for $s\leq 1/t$
and for $s\geq t$, but we currently have no non-trivial bound for intermediate
parameters $1/t<s<t$. To remedy this, we show in Theorem 5.5 below that
$\rho_{e^{\sigma}}(\mathcal{L})$ is “approximately log-convex,” which allows
us to interpolate between these two bounds. In the proof of Theorem 5.5, we
are unable to work with $\rho_{e^{\sigma}}(\mathcal{L})$ directly, so we
instead show that it can be approximated by
$\gamma_{e^{\sigma}}(\mathcal{V}(\mathcal{L}))$ (Lemma 5.4). We then notice
that the latter function is log-concave by Theorem 4.5.

######  Claim 5.3.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$,
$\boldsymbol{y}\in\mathcal{L}$, and $s>0$,

$\rho_{s}(\boldsymbol{y})\gamma_{s}(\mathcal{V}(\mathcal{L}))\leq\gamma_{s}(\mathcal{V}(\mathcal{L})+\boldsymbol{y})\leq\gamma_{s}(\mathcal{V}(\mathcal{L}))$

###### Proof.

By scaling appropriately, we may assume that $s=1$. We have

$\displaystyle\gamma(\mathcal{V}(\mathcal{L})+\boldsymbol{y})$
$\displaystyle=\int_{\mathcal{V}(\mathcal{L})}e^{-\pi\|\boldsymbol{x}+\boldsymbol{y}\|^{2}}{\rm
d}\boldsymbol{x}$
$\displaystyle=\rho(\boldsymbol{y})\int_{\mathcal{V}(\mathcal{L})}\rho(\boldsymbol{x})e^{-2\pi\langle\boldsymbol{y},\boldsymbol{x}\rangle}{\rm
d}\boldsymbol{x}$
$\displaystyle=\rho(\boldsymbol{y})\int_{\mathcal{V}(\mathcal{L})}\rho(\boldsymbol{x})\cosh(2\pi\langle\boldsymbol{y},\boldsymbol{x}\rangle){\rm
d}\boldsymbol{x}\;,$

where we have used the symmetry of the Voronoi cell in the last line. The
lower bound now follows from noting that
$\cosh(2\pi\langle\boldsymbol{x},\boldsymbol{y}\rangle)\geq 1$. For the upper
bound, we recall that, by definition, any vector in the Voronoi cell
$\boldsymbol{x}\in\mathcal{V}(\mathcal{L})$ satisfies
$\langle\boldsymbol{y},\boldsymbol{x}\rangle\leq\|\boldsymbol{y}\|^{2}/2$ for
any lattice vector $\boldsymbol{y}\in\mathcal{L}$. Therefore,
$\cosh(2\pi\langle\boldsymbol{y},\boldsymbol{x}\rangle)\leq\cosh(\pi\|\boldsymbol{y}\|^{2})\leq
1/\rho(\boldsymbol{y})$, as needed. ∎

######  Lemma 5.4.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and any $s>0$,

$e^{-4n}/2\leq\gamma_{s}(\mathcal{V}(\mathcal{L}))\rho_{s}(\mathcal{L})\leq
1\;.$

###### Proof.

The upper bound is Lemma 4.1, repeated for comparison. By scaling
appropriately, we may assume that $s=1$. Recall that
$\int_{\mathbb{R}^{n}}\|\boldsymbol{x}\|^{2}e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm
d}\boldsymbol{x}=n/(2\pi)$. It follows from Markov’s inequality that
$\int_{\sqrt{n/\pi}B_{2}^{n}}e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm
d}\boldsymbol{x}\geq 1/2$. Let

$Y:=\\{\boldsymbol{y}\in\mathcal{L}\ :\
(\mathcal{V}(\mathcal{L})+\boldsymbol{y})\cap\sqrt{n/\pi}B_{2}^{n}\neq\emptyset\\}\;.$

I.e., $Y$ is the set of vectors $\boldsymbol{y}\in\mathcal{L}$ such that there
exists some $\boldsymbol{x}\in\sqrt{n/\pi}B_{2}^{n}$ with
$\|\boldsymbol{y}-\boldsymbol{x}\|\leq\|\boldsymbol{y}^{\prime}-\boldsymbol{x}\|$
for every $\boldsymbol{y}^{\prime}\in\mathcal{L}$. By taking
$\boldsymbol{y}^{\prime}=\boldsymbol{0}$, we immediately see that
$Y\subseteq\mathcal{L}\cap 2\sqrt{n/\pi}B_{2}^{n}$. Recalling that the Voronoi
cell tiles space, we have

$\displaystyle 1/2$
$\displaystyle\leq\int_{\sqrt{n/\pi}B_{2}^{n}}e^{-\pi\|\boldsymbol{x}\|^{2}}{\rm
d}\boldsymbol{x}$ $\displaystyle\leq\sum_{\boldsymbol{y}\in
Y}\gamma(\mathcal{V}(\mathcal{L})+\boldsymbol{y})$
$\displaystyle\leq|Y|\cdot\gamma(\mathcal{V}(\mathcal{L}))$ (Claim 5.3)
$\displaystyle\leq|\mathcal{L}\cap
2\sqrt{n/\pi}B_{2}^{n}|\cdot\gamma(\mathcal{V}(\mathcal{L}))$
$\displaystyle\leq e^{4n}\rho(\mathcal{L})\gamma(\mathcal{V}(\mathcal{L}))\;,$

as needed. ∎

We now prove the “approximate log-convexity” of
$\rho_{e^{\sigma}}(\mathcal{L})$.

######  Theorem 5.5.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and any $t_{1}>s>t_{2}>0$,

$\rho_{s}(\mathcal{L})\leq
2e^{4n}\rho_{t_{1}}(\mathcal{L})^{\tau}\rho_{t_{2}}(\mathcal{L})^{1-\tau}\;,$

where $\tau:=\log(s/t_{2})/\log(t_{1}/t_{2})$.

###### Proof.

We have

$\displaystyle\rho_{s}(\mathcal{L})$
$\displaystyle\leq\frac{1}{\gamma_{s}(\mathcal{V}(\mathcal{L}))}$ (Lemma 4.1)
$\displaystyle\leq\frac{1}{\gamma_{t_{1}}(\mathcal{V}(\mathcal{L}))^{\tau}\gamma_{t_{2}}(\mathcal{V}(\mathcal{L}))^{1-\tau}}$
(Theorem 4.5) $\displaystyle\leq
2e^{4n}\rho_{t_{1}}(\mathcal{L})^{\tau}\rho_{t_{2}}(\mathcal{L})^{1-\tau}$
$\displaystyle\text{(Lemma~{}\ref{lem:rho_gamma_2})}\;,$

as needed. ∎

######  Corollary 5.6 (Item 2 of Theorem 1.3).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$ and any parameter $1/t<s<t$, we
have

$\rho_{s}(\mathcal{L})\leq 4(e^{8}st)^{n/2}\;,$

where $t:=10(\log n+2)$.

###### Proof.

Let $\tau:=(1-\log s/\log t)/2$. Then,

$\displaystyle\rho_{s}(\mathcal{L})$ $\displaystyle\leq
2e^{4n}\rho_{1/t}(\mathcal{L})^{\tau}\cdot\rho_{t}(\mathcal{L})^{1-\tau}$
(Theorem 5.5) $\displaystyle\leq
2^{1+\tau}e^{4n}\rho_{t}(\mathcal{L})^{1-\tau}$ (Theorem 1.2)
$\displaystyle\leq 4e^{4n}t^{(1-\tau)n}$ (Corollary 5.2)
$\displaystyle=4(e^{8}st)^{n/2}\;,$

as needed. ∎

##  6 Proof of the covering radius approximation

We will need the following lemma, which is implicit in [Ban93].

######  Lemma 6.1.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and $t>0$ such that
$\rho_{1/t}(\mathcal{L}^{*})\leq 3/2$,

$\mu(\mathcal{L})<\Big{(}\sqrt{\frac{n}{2\pi}}+1\Big{)}\cdot t\;.$

###### Proof.

By scaling the lattice, we may assume without loss of generality that $t=1$.
Let $r:=((1+4/\sqrt{n})/(2\pi))^{1/2}$. By Lemma 2.1, for any
$\boldsymbol{t}\in\mathbb{R}^{n}$, we have

$\rho((\mathcal{L}-\boldsymbol{t})\setminus
r\sqrt{n}B_{2}^{n})\leq\big{(}\sqrt{2\pi er^{2}}e^{-\pi
r^{2}}\big{)}^{n}\cdot\rho(\mathcal{L})=e^{-2\sqrt{n}}(1+4/\sqrt{n})^{n/2}\cdot\rho(\mathcal{L})<\rho(\mathcal{L})/3\;,$

where the last inequality follows by noting that it holds for $n=1$ and that
$e^{-2x}\cdot(1+4/x)^{x^{2}/2}$ is a decreasing function in $x$ for $x>0$ (a
fact that can be proven using a tedious but straightforward computation). On
the other hand, it is an easy consequence of the Poisson Summation Formula
(see, e.g., [MR07]) that for any $\boldsymbol{t}\in\mathbb{R}^{n}$,

$\rho(\mathcal{L}-\boldsymbol{t})\geq\frac{2-\rho(\mathcal{L}^{*})}{\rho(\mathcal{L}^{*})}\cdot\rho(\mathcal{L})\geq\rho(\mathcal{L})/3\;.$

Therefore, $(\mathcal{L}-\boldsymbol{t})\cap r\sqrt{n}B_{2}^{n}$ is nonempty,
and in particular, $\operatorname{dist}(\boldsymbol{t},\mathcal{L})\leq
r\sqrt{n}<\sqrt{n/(2\pi)}+1$. Since this holds for arbitrary $\boldsymbol{t}$,
we have $\mu(\mathcal{L})<\sqrt{n/(2\pi)}+1$, as needed. ∎

We now note that Theorem 1.2 (together with Lemma 6.1) immediately implies a
bound on the covering radius of stable lattices.

######  Theorem 6.2.

For any stable lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\mu(\mathcal{L})\leq 4\sqrt{n}(\log n+10)\;.$

###### Proof.

Let $t:=10(\log n+2)$. Since $\mathcal{L}^{*}$ is also stable (by Item (i) of
Proposition 2.5), Theorem 1.2 implies that $\rho_{1/t}(\mathcal{L}^{*})\leq
3/2$. Applying Lemma 6.1, we have

$\mu(\mathcal{L})\leq(\sqrt{n/(2\pi)}+1)\cdot t<4\sqrt{n}(\log n+10)\;,$

as needed. ∎

Next, we show (Proposition 6.4) how to reduce the case of general lattices to
the stable case. We will need the following technical lemma, which is a slight
modification of [DR16, Lemma 4.9] (with an essentially identical proof).

######  Lemma 6.3 (Reverse AM-GM).

Let $0<a_{1}<\cdots<a_{k}$ and $d_{1},\dots,d_{k}\in\mathbb{N}$, and for
$j=1,\ldots,k$, define $m_{j}:=\sum_{i\geq j}d_{i}$. Then,

$\displaystyle\sum_{i=1}^{k}d_{i}a_{i}$ $\displaystyle\leq
2e\cdot\lceil\log(2m_{1})\rceil\cdot\max_{j}m_{j}\Big{(}\prod_{i\geq
j}a_{i}^{d_{i}}\Big{)}^{1/m_{j}}\;.$

###### Proof.

For $\ell=1,2,\ldots$, let $S_{\ell}:=\\{j\ :\ e^{-\ell}a_{k}<a_{j}\leq
e^{1-\ell}a_{k}\\}$, and let $j_{\ell}:=\min\\{j\in S_{\ell}\\}$. For non-
empty $S_{\ell}$, we have

$\sum_{i\in S_{\ell}}d_{i}a_{i}\leq m_{j_{\ell}}e^{1-\ell}a_{k}\leq
em_{j_{\ell}}a_{j_{\ell}}\leq em_{j_{\ell}}\cdot\Big{(}\prod_{i\geq
j_{\ell}}a_{i}^{d_{i}}\Big{)}^{1/m_{j_{\ell}}}\;.$

Let $\ell^{*}:=\lceil\log(2m_{1})\rceil$. By the above inequality, it suffices
to argue that there exists an $\ell$ such that
$2\ell^{*}\cdot\sum_{S_{\ell}}d_{i}a_{i}\geq\sum_{i=1}^{k}d_{i}a_{i}$. Indeed,

$\sum_{\ell=1}^{\ell^{*}}\sum_{i\in
S_{\ell}}d_{i}a_{i}=\sum_{i=1}^{k}d_{i}a_{i}-\sum_{\ell>\ell^{*}}\sum_{i\in
S_{\ell}}d_{i}a_{i}>\sum_{i=1}^{k}d_{i}a_{i}-m_{1}\cdot\frac{a_{k}}{2m_{1}}\geq\frac{1}{2}\cdot\sum_{i=1}^{k}d_{i}a_{i}\;,$

where in the last inequality we have used that $d_{k}\geq 1$. Therefore, there
exists an $\ell$ such that

$\sum_{i\in
S_{\ell}}d_{i}a_{i}\geq\frac{1}{2\ell^{*}}\cdot\sum_{i=1}^{k}d_{i}a_{i}\;,$

as needed. ∎

Recall that

$\mu_{\det}(\mathcal{L}):=\max_{W\subset\mathbb{R}^{n}}\sqrt{\dim(W^{\perp})}\cdot\det(\pi_{W^{\perp}}(\mathcal{L}))^{\frac{1}{\dim(W^{\perp})}}\;,$

where the maximum is over lattice subspaces $W\subset\mathbb{R}^{n}$ of
$\mathcal{L}$ (i.e., subspaces $W$ spanned by up to $n-1$ lattice vectors).

######  Proposition 6.4.

Let

$C_{\mu}(n):=\max_{d\leq n}\sup\mu(\mathcal{L})/\sqrt{d}\;,$

where the supremum is over stable lattices $\mathcal{L}\subset\mathbb{R}^{d}$.
Then, for any lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\mu(\mathcal{L})\leq\sqrt{2e\lceil\log(2n)\rceil}\cdot
C_{\mu}(n)\cdot\mu_{\det}(\mathcal{L})\;.$

###### Proof.

Let
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\mathcal{L}_{1}\subset\cdots\subset\mathcal{L}_{k}=\mathcal{L}$
be the canonical filtration of some lattice
$\mathcal{L}\subset\mathbb{R}^{n}$. Let
$d_{i}:=\operatorname{rank}(\mathcal{L}_{i}/\mathcal{L}_{i-1})$. Note that
$\mathcal{L}_{i}/\mathcal{L}_{i-1}$ is a scaling of a stable lattice, i.e.,
$\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{-1/d_{i}}\cdot(\mathcal{L}_{i}/\mathcal{L}_{i-1})$
is stable. (See Item 2 of Proposition 2.5.) We therefore have by Claim 2.6 and
Lemma 2.7 that

$\displaystyle\mu(\mathcal{L})^{2}$
$\displaystyle\leq\mu\Big{(}\bigoplus_{i}\mathcal{L}_{i}/\mathcal{L}_{i-1}\Big{)}^{2}$
$\displaystyle=\sum_{i}\mu(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{2}$
$\displaystyle\leq
C_{\mu}(n)^{2}\cdot\sum_{i}d_{i}\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{2/d_{i}}\;.$
(9)

Next, we recall from Item 3 of Proposition 2.5 that
$a_{i}:=\det(\mathcal{L}_{i}/\mathcal{L}_{i-1})^{2/d_{i}}$ is an increasing
sequence, and we note that $\sum_{i\geq
j}d_{i}=\operatorname{rank}(\mathcal{L}/\mathcal{L}_{j-1})$. We may therefore
use Lemma 6.3 to bound Eq. (9) from above by

$\displaystyle 2e\lceil\log(2n)\rceil\cdot
C_{\mu}(n)^{2}\cdot\max_{i}\operatorname{rank}(\mathcal{L}/\mathcal{L}_{i})\cdot\det(\mathcal{L}/\mathcal{L}_{i})^{\frac{2}{\operatorname{rank}(\mathcal{L}/\mathcal{L}_{i})}}$
$\displaystyle\quad\leq 2e\lceil\log(2n)\rceil\cdot
C_{\mu}(n)^{2}\max_{W\subset\mathbb{R}^{n}}\dim(W^{\perp})\cdot\det(\pi_{W^{\perp}}(\mathcal{L}))^{\frac{2}{\dim(W^{\perp})}}\;,$

as needed. ∎

Theorem 1.5 now follows as an immediate corollary of the above results. In
particular, we have $C_{\mu}(n)\leq 4(\log n+10)$ and therefore
$\sqrt{2e\lceil\log(2n)\rceil}\cdot C_{\mu}(n)\leq 10(\log n+10)^{3/2}$. The
result then follows from Proposition 6.4.

###  6.1 Connection with the Slicing Conjecture

In this section, we prove Theorem 6.8. The structure of the proof is based on
the one suggested in [SW16], as was the case for the proof of our main theorem
in Section 4.

As in Section 4, we are unable to work with the lattice parameter
$\mu(\mathcal{L})$ that interests us directly.777 While [DSV12] give a
characterization of lattices corresponding to local maxima of $\mu$, we are
unable to obtain a sufficiently strong bound on the covering radius of these
lattices. See [SW16] for more about this question. Instead, we work with the
lattice parameter

$\overline{\mu}(\mathcal{L}):=\sqrt{\frac{1}{\det(\mathcal{L})}\int_{\mathcal{V}(\mathcal{L})}\|\boldsymbol{x}\|^{2}{\rm
d}\boldsymbol{x}}\;,$

which gives a good approximation to $\mu$. The following tight result due to
Magazinov [Mag17] (and conjectured in [HLR09]) makes this precise. (See
[HLR09, Claim 3.1] for a slightly weaker result with a simple proof. See,
e.g., [ZF96, CS98, GMR05, HLR09, Mag17] for more about $\overline{\mu}$.)

######  Theorem 6.5 ([Mag17]).

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\overline{\mu}(\mathcal{L})\leq\mu(\mathcal{L})\leq\sqrt{3}\overline{\mu}(\mathcal{L})\;.$

We now observe that Theorem 3.1 is applicable to the function
$\overline{\mu}(\mathcal{L})^{2}$. Recall that a symmetric convex body
$K\subset\mathbb{R}^{n}$ is said to be _isotropic_ if
$\int_{K}\boldsymbol{x}\boldsymbol{x}^{T}{\rm d}\boldsymbol{x}=\alpha\cdot
I_{n}$ for some scalar $\alpha>0$.

######  Proposition 6.6.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\nabla_{A}\overline{\mu}(A^{T}\mathcal{L})^{2}|_{A=I_{n}}=\frac{2}{\det(\mathcal{L})}\int_{\mathcal{V}(\mathcal{L})}\boldsymbol{x}\boldsymbol{x}^{T}{\rm
d}\boldsymbol{x}\;,$

where $A\in\mathrm{GL}_{n}(\mathbb{R})$ ranges over non-singular matrices. In
particular, if $\mathcal{L}$ corresponds to a local maximum (or local minimum)
of $\overline{\mu}(\mathcal{L})$ over the set of determinant-one lattices,
then $\mathcal{V}(\mathcal{L})$ is isotropic.

###### Proof.

To compute the gradient, we simply apply Theorem 3.1 with $f(x):=x$, and
recall that

$\overline{\mu}(A^{T}\mathcal{L})^{2}=\frac{1}{\det(\mathcal{L})}\cdot\frac{1}{|\det(A)|}\int_{\mathcal{V}(A^{T}\mathcal{L})}f(\|\boldsymbol{x}\|^{2}){\rm
d}\boldsymbol{x}\;.$

The “in particular” follows from the fact that a differentiable function
$g(A)$ restricted to the set of determinant-one matrices has a critical point
at $A=I_{n}$ if and only if $\nabla_{A}g(A)|_{A=I_{n}}$ is a scalar multiple
of the identity. ∎

We define the (symmetric) isotropic constant

$L_{n}^{2}:=\max_{d\leq
n}\frac{1}{d}\cdot\sup_{K}\int_{K}\|\boldsymbol{x}\|^{2}{\rm
d}\boldsymbol{x}\;,$

where the supremum is taken over all isotropic symmetric convex bodies
$K\subset\mathbb{R}^{d}$ of volume one. It is known to satisfy
$1/(2\sqrt{3})\leq L_{n}\leq Cn^{1/4}$, and the Slicing Conjecture implies
that $L_{n}$ is bounded by a universal constant [Bou91, Kla06]. (The lower
bound is due to the hypercube, $[-1/2,1/2]^{n}$.) We note in passing that we
are only concerned with the isotropic constant for Voronoi cells, which could
conceivably be easier to bound than the isotropic constant for arbitrary
convex bodies.

######  Theorem 6.7.

For any stable lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\mu(\mathcal{L})\leq\sqrt{3}\overline{\mu}(\mathcal{L})\leq\sqrt{3n}L_{n}\;.$

###### Proof.

By Theorem 6.5, it suffices to prove that
$\overline{\mu}(\mathcal{L})\leq\sqrt{n}L_{n}$. Note that this is trivially
true for $n=1$. We assume for induction that
$\overline{\mu}(\mathcal{L}^{\prime})\leq\sqrt{d}L_{d}\leq\sqrt{d}L_{n}$ for
all stable lattices $\mathcal{L}^{\prime}$ of rank $d<n$. Recall that the set
of stable lattices is compact (Item (ii) of Proposition 2.5), so that we may
assume without loss of generality that $\mathcal{L}$ corresponds to a global
maximum of the function $\overline{\mu}$ over this set. If this is also a
_local_ maximum over the set of determinant-one lattices, then by Proposition
6.6, the Voronoi cell is isotropic, and we have
$\overline{\mu}(\mathcal{L})\leq\sqrt{n}L_{n}$ by the definition of
$\overline{\mu}$ and $L_{n}$. Otherwise, $\mathcal{L}$ must lie on the
boundary of the set of stable lattices. I.e., there is some primitive
sublattice $\mathcal{L}^{\prime}\subset\mathcal{L}$ of rank $0<d<n$ such that
$\mathcal{L}^{\prime}$ and $\mathcal{L}/\mathcal{L}^{\prime}$ are both stable.
(See Item (iv) of Proposition 2.5.) Applying the induction hypothesis and
Corollary 2.8 (together with Claim 2.6), we have

$\overline{\mu}(\mathcal{L})^{2}\leq\overline{\mu}(\mathcal{L}^{\prime}\oplus\mathcal{L}/\mathcal{L}^{\prime})^{2}=\overline{\mu}(\mathcal{L}^{\prime})^{2}+\overline{\mu}(\mathcal{L}/\mathcal{L}^{\prime})^{2}\leq
dL_{n}^{2}+(n-d)L_{n}^{2}=nL_{n}^{2}\;,$

as needed. ∎

As far as we know, it is entirely possible that $L_{n}=1/(2\sqrt{3})$, i.e.,
that the hypercube $[-1/2,1/2]^{n}$ is the worst symmetric body for the
Slicing Conjecture. If this is true, then we get that for any stable lattice
$\mathcal{L}\subset\mathbb{R}^{n}$, $\mu(\mathcal{L})\leq\sqrt{n}/2$, which is
tight for $\mathbb{Z}^{n}$. Apart from being an interesting statement in its
own right, it was shown by Shapira and Weiss [SW16] that such a result would
imply the so-called Minkowski conjecture (see there for more information).

We can now use Proposition 6.4 to extend Theorem 6.7 to all lattices
$\mathcal{L}\subset\mathbb{R}^{n}$.

######  Theorem 6.8.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$,

$\mu(\mathcal{L})\leq 5\sqrt{\log n+1}\cdot
L_{n}\cdot\mu_{\det}(\mathcal{L})\;.$

As we observed in Footnote 4, there are lattices with $\mu(\mathcal{L})\geq
C\sqrt{\log n}\cdot\mu_{\det}(\mathcal{L})$. So, Theorem 6.8 is tight up to a
constant, assuming the Slicing Conjecture. (We made no attempt to optimize the
constant in Theorem 6.8.)

##  7 An optimal bound for extreme parameters

We now prove Theorem 1.6, which says that $\mathbb{Z}^{n}$ has maximal
Gaussian mass amongst all lattices $\mathcal{L}$ with
$\det(\mathcal{L}^{\prime})\geq 1$ for all sublattices
$\mathcal{L}^{\prime}\subseteq\mathcal{L}$, for very small parameters
$s\leq\sqrt{2\pi/(n+2)}$ _and_ for very large parameters
$s\geq\sqrt{(n+2)/(2\pi)}$. The proof is similar to that of Theorem 1.2,
except here we work directly with $\rho_{s}(\mathcal{L})$ (instead of the
proxy $\gamma_{s}(\mathcal{V}(\mathcal{L}))$). Moreover, we show that
$\rho_{s}(\mathcal{L})$ has _no local maxima_ for those values of $s$, which
leads to a simpler proof and the clearly tight result. In order to show that
local maxima do not exist, we will show that the Laplacian of
$\rho_{s}(\mathcal{L})$ is always positive when $\mathcal{L}$ is stable.

In more detail, for a lattice $\mathcal{L}$ and $s>0$ let
$f_{\mathcal{L},s}:X\to\mathbb{R}$ be given by

$f_{\mathcal{L},s}(A):=\rho_{s}(e^{A/2}\mathcal{L})=\sum_{\boldsymbol{y}\in\mathcal{L}}e^{-\pi\boldsymbol{y}^{T}e^{A}\boldsymbol{y}/s^{2}}\;,$

where $X\subset\mathbb{R}^{n\times n}$ is the linear space of all symmetric
matrices with zero trace. Notice that as $A$ ranges over $X$,
$e^{A}:=I_{n}+\sum_{i=1}^{\infty}A^{i}/i!$ ranges over all determinant-one
positive-definite matrices. (In particular, $e^{A/2}\mathcal{L}$ ranges over
all lattices of fixed determinant, up to orthogonal transformations.) See
[Ter16, Section 1.1.3] for a more in-depth treatment of the space of
determinant-one matrices.

Recall that the _Laplacian_ of a twice differentiable function
$g:X\to\mathbb{R}$ is given by

$\Delta_{X}g(A):=\sum_{i}\frac{\partial^{2}}{\partial E_{i}^{2}}g(A)\;,$

where the $E_{i}$ form an orthonormal basis of $X$, and

$\frac{\partial^{2}}{\partial M^{2}}g(A):=\frac{\partial^{2}}{\partial
r^{2}}g(A+rM)|_{r=0}$

is the directional second derivative of $g$ in the $M$ direction. One can show
that the Laplacian does not depend on the choice of basis. Clearly, if the
Laplacian is positive at $A$, then $A$ cannot correspond to a local maximum of
$g$, since there must be at least one direction in which the second derivative
is positive.

The Laplacian of $f_{\mathcal{L},s}$ is straightforward to calculate. It can
be found, e.g., in the work by Sarnak and Strömbergsson [SS06] who used it to
study local minima of $\rho_{s}(\mathcal{L})$.

######  Claim 7.1 ([SS06, Eq. (46)]).

Let $X\subset\mathbb{R}^{n\times n}$ be the space of trace-zero symmetric
matrices. Then, for any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and any
parameter $s>0$,

$\Delta_{X}f_{\mathcal{L},s}(0)=\frac{\pi}{s^{2}}\cdot\frac{n-1}{n}\cdot\sum_{\boldsymbol{y}\in\mathcal{L}}\rho_{s}(\boldsymbol{y})\|\boldsymbol{y}\|^{2}\Big{(}\frac{\pi}{s^{2}}\cdot\|\boldsymbol{y}\|^{2}-\frac{n+2}{2}\Big{)}\;.$

######  Proposition 7.2.

For any lattice $\mathcal{L}\subset\mathbb{R}^{n}$ and

$0<s\leq\sqrt{\frac{2\pi}{n+2}}\cdot\lambda_{1}(\mathcal{L})\;,$

$\mathcal{L}$ cannot correspond to a local maximum of $\rho_{s}(\mathcal{L})$
over the set of determinant-one lattices. In particular, since stable lattices
have $\lambda_{1}(\mathcal{L})\geq 1$, a stable lattice cannot correspond to a
local maximum for $s\leq\sqrt{2\pi/(n+2)}$.

###### Proof.

It suffices to show that the Laplacian given in Claim 7.1 is positive for such
$\mathcal{L}$. Indeed, the summand is zero for
$\boldsymbol{y}=\boldsymbol{0}$, and since

$\frac{\pi}{s^{2}}\cdot\lambda_{1}(\mathcal{L})^{2}\geq\frac{n+2}{2}\;,$

the summand is non-negative for all non-zero $\boldsymbol{y}\in\mathcal{L}$.
Finally, since any lattice contains vectors of arbitrarily large length, there
must be some strictly positive terms in the sum. Therefore, the full sum is
strictly positive, as needed. ∎

From this, we derive our main result for the special case of stable lattices.

######  Proposition 7.3.

For any $0<s\leq\sqrt{2\pi/(n+2)}$ and stable lattice
$\mathcal{L}\subset\mathbb{R}^{n}$,
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$.

###### Proof.

Note that the result is trivial for $n=1$. We assume for induction that the
result holds for all dimensions less than $n$. Since the set of stable
lattices is compact and $\rho_{s}(\mathcal{L})$ is a continuous function, we
may assume that $\mathcal{L}$ corresponds to a global maximum of
$\rho_{s}(\mathcal{L})$ over the set of stable lattices. By Proposition 7.2,
this cannot be a local maximum over the set of determinant-one lattices. So,
$\mathcal{L}$ must be on the boundary of the set of stable lattices. I.e.,
there is a non-trivial primitive sublattice
$\mathcal{L}^{\prime}\subset\mathcal{L}$ with
$d:=\operatorname{rank}(\mathcal{L}^{\prime})$ such that
$\mathcal{L}^{\prime}$ and $\mathcal{L}/\mathcal{L}^{\prime}$ are themselves
stable lattices of rank strictly less than $n$. (See Item (iv) of Proposition
2.5.) Applying the induction hypothesis, we have by Lemma 2.3 that

$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathcal{L}^{\prime})\cdot\rho_{s}(\mathcal{L}/\mathcal{L}^{\prime})\leq\rho_{s}(\mathbb{Z}^{d})\cdot\rho_{s}(\mathbb{Z}^{n-d})=\rho_{s}(\mathbb{Z}^{n})\;,$

where we have used the fact that
$s\leq\sqrt{2\pi/(n+2)}\leq\min\\{\sqrt{2\pi/(d+2)},\ \sqrt{2\pi/(n-d+2)}\\}$
in order to apply the induction hypothesis. ∎

We now “invert the parameter” using duality.

######  Corollary 7.4.

For any $s\geq\sqrt{(n+2)/(2\pi)}$ and stable lattice
$\mathcal{L}\subset\mathbb{R}^{n}$,
$\rho_{s}(\mathcal{L})\leq\rho_{s}(\mathbb{Z}^{n})$.

###### Proof.

Recall that the dual $\mathcal{L}^{*}$ of a stable lattice is itself stable.
(See Item (i) of Proposition 2.5.) Furthermore, by the Poisson Summation
Formula for the discrete Gaussian (Eq. (3)),

$\rho_{s}(\mathcal{L})=\frac{s^{n}}{\det(\mathcal{L})}\cdot\rho_{1/s}(\mathcal{L}^{*})\leq\frac{s^{n}}{\det(\mathcal{L})}\cdot\rho_{1/s}(\mathbb{Z}^{n})=\rho_{s}(\mathbb{Z}^{n})\;,$

as needed, where the inequality follows from Proposition 7.3, and the last
equality follows from the Poisson Summation Formula applied to
$\mathbb{Z}^{n}$. ∎

We can now prove Theorem 1.6.

###### Proof of Theorem 1.6.

Let
$\\{\boldsymbol{0}\\}=\mathcal{L}_{0}\subset\mathcal{L}_{1}\subset\cdots\subset\mathcal{L}_{k}=\mathcal{L}$
be the canonical filtration of $\mathcal{L}$, and let