# Asymptotic Lower Bounds on Sphere Packing Efficiency of Lattices

Presentation by

Affliation:

### École Polytechnique Fédérale de Lausanne, Switzerland

Chair of Number Theory

## Introduction

$$\DeclareMathOperator{\R}{\mathbb{R}}$$$$\DeclareMathOperator{\Z}{\mathbb{Z}}$$$$\DeclareMathOperator{\C}{\mathbb{C}}$$$$\DeclareMathOperator{\F}{\mathbb{F}}$$ Suppose we have $\{a_1, a_2, ... , a_n \} \in m \Z$ with $a_i \ge 0$ and suppose that $$\frac{1}{n}\sum_{i=1}^{n} a_i < m.$$

What can we conclude about the numbers $a_i$?

Answer: At least one of them is $0$.

#### Lemma

(Integrality gap)
Let $X$ be a probability space and $\Phi: X\to \R^{\ge 0}$ be a random variable that takes values only in $m \Z$ for some integer $m$.
If $\int_X \Phi < m$, then there exists some $x \in X$ such that $\Phi(x) = 0$.

For our application, we will set $X$ to be a set of lattices.

## What is a lattice packing?

Consider $\R^d$ with the standard inner product. A lattice $\Lambda\subseteq \R^d$ is a discrete subgroup such that the quotient space $\R^d / \Lambda$ has a finite induced volume.

Given a lattice $\Lambda$, choose $r > 0$ and consider the open balls $\{ B_{r}\left( v \right)\}_{v \in \Lambda}$ such for any $v_1, v_2 \in \Lambda$, $B_{r}(v_1) \cap B_{r}(v_2) \neq \emptyset \Rightarrow v_1 = v_2$.

Then $(\Lambda,r)$ is called a lattice sphere packing, or simply lattice packing inside $(\R^d, \langle \ , \ \rangle)$.

Packing density of a lattice packing is: $\lim_{R \rightarrow \infty} \frac{\mu\left( B_{R}(0) \cap \left( \bigsqcup_{v \in \Lambda} B_{r}(v) \right) \right)}{\mu\left( B_{R}(0) \right)} = \frac{\mu( B_{r}(0) )}{ \mu(\R^d / \Lambda)}$ It is always in the interval $]0,1[$.

#### Visualizing in $\R^2$

However, note that $2r$ can be at most $$m(\Lambda) = \min_{v \in \Lambda \setminus \{0\}} ||v|| ,$$ otherwise some balls will begin to intersect.

The goal is to maximize packing density. So take $r = \frac{1}{2}m(\Lambda)$. In that case packing density will be equal to $$\frac{\mu( B_{m(\Lambda)/2}(0) )}{ \mu(\R^d / \Lambda)},$$ and is independent of scaling.

To maximize this over all $\Lambda$, it is sufficient to maximize over unit covolume lattices (i.e. $$\mu(\R^d/\Lambda)$$ = 1)

#### Visualizing in $\R^2$

So we somehow find $\sup_{\substack{\Lambda \subseteq \R^d \\ \mu(\R^d/\Lambda)=1}} \mu\left(B_{m(\Lambda)/2}(0) \right)$

$= \sup_{ g \in SL_d(\R)} \frac{1}{2^d} \mu\left(B_{m(g \Z^d)}(0) \right)$

which we use to define our dimensional constant $c_d$ $\colon= \frac{1}{2^d} c_d$

Putting it together, we have $c_{d} = \sup\left\{ \mu\left( B_{r}(0)\right) \ | \ r> 0,~g \in SL_d(\R) \text{ and } B_{r}(0) \cap g\Z^d = \{ 0\}\right\}.$

Clearly, $$~c_d \in~]0,2^d[$$, so supremum exists!

## The space of lattices

Finding $c_d$ is very difficult for a general $d$. To show $c_d \ge K$, we must prove the existence of $g \in SL_d(\R)$ such that the origin centered ball $B$ with $\mu(B) = K$ has $g \Z^d \cap B = \{0\}$

This is an optimization problem on the space $X_d:= \{ \Lambda \subset \mathbb{R}^{d} | \ \mu(\mathbb{R}^{d} / \Lambda) = 1 \} = \{ g\Z^d \ | \ g \in SL_d(\R) \}$

$\simeq SL_d(\mathbb{R})/SL_d(\mathbb{Z}).$

A priori, this is a bijection of sets. But now we can pull back the topology and the measure from $SL_d(\R)/SL_d(\Z)$.

$SL_d(\R)$ has the topology of a locally compact group.

$SL_d(\R)$ is unimodular. $SL_d(\Z)$ is a discrete subgroup inside $SL_d(\R)$ and therefore there is a unique left $SL_d(\R)$-invariant measure on $SL_d(\R)/SL_d(\Z)$.

#### Proposition

There exists a unique (upto scaling) natural measure on $SL_d(\R)/SL_d(\Z)$, left-invariant under $SL_d(\R)$ action on cosets.
Furthermore, $SL_d(\mathbb{R})/SL_d(\mathbb{Z})$ under this has a bounded total measure.

One can show this by constructing a "coarse" fundamental domain of the quotient space.

This gives us the probability space on which we want to use the integrality gap argument. Let us now introduce the random variable.

## Lattice-sum function

Consider a bounded measurable function with compact support $f:\R^d \rightarrow \R$.
e.g. the indicator function of a ball.

With this, we can now construct the lattice-sum function $\Phi_f(\Lambda): X_d \rightarrow \R$, given as $\Phi_f(\Lambda) = \sum_{v \in \Lambda \setminus \{ 0\}}^{} f(v).$

Since we can generate random lattices, we can talk about the expected value of $\Phi_f(\Lambda)$.

Let us try to do this experimentally! Let us sample over a set $S \subseteq X_d$ of lattices.

So we see that it is almost the integral.

#### Visualizing in $\R^2$

What we are empirically confirming is the following.

#### Theorem

(Siegel, 1945)
Suppose $f:\mathbb{R}^{d} \rightarrow \mathbb{R}$ is a compactly supported bounded measurable function. Then, the following holds. \begin{align} \int_{X_d} \Phi_f = \int_{SL_d(\mathbb{R})/SL_d(\mathbb{Z})}^{} \left( \sum_{v \in g \mathbb{Z}^{d} \setminus \{ 0\}}^{}f(v) \right) dg = \int_{\mathbb{R}^{d}}^{} f(x) dx, \end{align} where the $dx$ on the right-hand side is the usual Lebesgue measure on $\mathbb{R}^{d}$ and $dg$ is the unique $SL_d(\mathbb{R})$-invariant probability measure on $SL_d(\mathbb{R})/SL_d(\mathbb{Z})$.

But as you saw that for any $\Lambda \in X_d$, when $f$ is the indicator of a ball, we must have $\Phi_f(\Lambda) \in \{0,2,4,6,...\}$. That's because balls are symmetric. $$v \in \text{supp}(f) \cap ( \Lambda \setminus \{0 \}) \Rightarrow -v \in \text{supp}(f) \cap ( \Lambda \setminus \{0 \}).$$

If $f$ is the indicator function of a ball of volume $2- \varepsilon$, then this tells us that for any dimension $d$ $$\int_{X_d} \Phi_f = 2 - \varepsilon$$

Conclusion: There exists some lattice $\Lambda \in X_d$ such that $\Phi_f(\Lambda) = 0$. That is, there is some lattice of unit covolume that intersects trivially with an origin centered ball of volume $2 - \varepsilon$.

Another conclusion: $c_d \ge 2$ for all dimensions $d$!

The details of the Siegel's theorem are too lengthy for this talk. But there is another proof of $c_d \ge 2$ that can be proven within the next 15 minutes!

## Controlled randomness

Choose a prime number $p$. Consider the map $\pi_p:\Z^d \to \F_p^d$.

$\F_p^d \setminus \{0\}$ is a disjoint union of lines. $$\F_p^d \setminus \{0\}= \bigsqcup_{v \in (\F_p^d\setminus\{0\} )/\F_p^* }(\F_p v \setminus \{0\})$$

This implies that $$\Z^d \setminus p \Z^d = \bigsqcup_{v \in (\F_p^d\setminus\{0\} )/\F_p^* } \pi_p^{-1}(\F_p v \setminus \{0\})$$

Let us put all these sub-lattices in one set $$\mathcal{L}_p'= \{ \pi_p^{-1}(\F_p v) \ | \ v \in \F_p^d \setminus \{ 0 \} \}.$$

#### Visualizing in $\R^2$

However the lattices in $\mathcal{L}_p'$ are not unit covolume. But each one of them has a covolume of $p^{d-1}$.

So appropriately normalizing, elements of this set become unit covolume lattices. $$\mathcal{L}_p= \{ C_p \pi_p^{-1}(\F_p v) \ | \ v \in \F_p^d \setminus \{ 0 \} \},$$ when $C_p = p^{-\left( 1- \frac{1}{d} \right)}$.

So $\mathcal{L_p} \subseteq X_d$ is a set of unit covolume lattices, with $\#\mathcal{L}_p \to \infty$ as $p \to \infty$.

Now as before let $f:\R^d \to \R$ be a compactly supported Riemann integrable function. Let $\Phi_f:X_d \to \R$ again be the lattice-sums of $f$.

So let us try to find $\Phi_f$ on $\mathcal{L}_p$. We will assume that the prime $p$ is very large. \begin{align} \frac{1}{\#\mathcal{L}_p}\sum_{\Lambda \in \mathcal{L}_p} \Phi_f(\Lambda) \end{align}

By construction, we have that $$C_p\Z^d \setminus p C_p \Z^d = \bigsqcup_{ \Lambda \in \mathcal{L}_p } \Lambda \setminus(p C_p \Z^d)$$

Using this and some manipulation gives us \begin{align} & \frac{1}{\#\mathcal{L}_p}\sum_{\Lambda \in \mathcal{L}_p} \Phi_f(\Lambda) \\ & = \sum_{v \in (pC_p\Z^d) \setminus \{0\} } f(v) + \frac{1}{\#\mathcal{L}_p} \sum_{v \in C_p \Z^d \setminus ( pC_p \Z^d )} f(v) . \end{align}

Since $pC_p = p^{\frac{1}{d}} \to \infty$ as $p \to \infty$, the non-zero points of $pC_p \Z^d$ are pushed away from the support of $f$.

#### Visualizing in $\R^2$

So for large $p$, we can ignore the first term. Or, we can assume that the coeffecient behind the first term was $(\# \mathcal{L}_p)^{-1}$. So we get that \begin{align} \frac{1}{\#\mathcal{L}_p}\sum_{\Lambda \in \mathcal{L}_p} \Phi_f(\Lambda) & = \frac{1}{\#\mathcal{L}_p} \sum_{v \in C_p \Z^d \setminus ( pC_p \Z^d )} f(v) +\frac{1}{\#\mathcal{L}_p} \sum_{v \in (pC_p\Z^d) \setminus \{0\} } f(v) \\ & = \frac{1}{\#\mathcal{L}_p} \sum_{v \in C_p \Z^d \setminus \{0\} } f(v) . \end{align}

And now, shocking fact!
$( C_p^d \# \mathcal{L_p} )\to 1$ as $p \to \infty$ (Easy combinatorics exercise.)

So in fact, as $p \to \infty$, the sum on the right converges to the Riemann integral of $f$ on $\R^d$. $$\frac{1}{\#\mathcal{L}_p} \left( \sum_{v \in (\# \mathcal{L}_p)^{\frac{1}{d}} \Z^d \setminus \{0\} } f(v) \right) \to \int_{\R^d} f(x) dx .$$

What we have managed to show (with proof!) is

#### Theorem

(Rogers, 1947)
Let $p$ be an arbitrary prime, $\mathbb{F}_p$ be the field with $p$ elements and let $\pi_p:\mathbb{Z}^{d} \rightarrow \mathbb{F}_p^{d}$ be the natural coordinate-wise projection map. Let $\mathcal{L}_p$ be the set of sub-lattices of $\mathbb{Z}^{d}$ that are pre-images of one-dimensional subspaces in this projection map scaled to become unit covolume, i.e. $$\mathcal{L}_p = \{ C_p \pi_p^{-1}( \mathbb{F}_p v) \ | \ v \in \mathbb{F}_p^d \setminus \{ 0\} \}, C_p = p^{-\left(1-\frac{1}{d}\right)} .$$ Consider a compactly supported continuous function $f:\mathbb{R}^{d} \rightarrow \mathbb{R}$ and the lattice-sum function $\Phi_f:X_d \rightarrow \mathbb{R}$ as defined above. Then the following holds. \begin{align} \lim_{ p \rightarrow \infty}\left[ \frac{1}{\# {\mathcal{L}}_p}\sum_{ \Lambda \in {\mathcal{L}}_p} \Phi_{f}\left( \Lambda\right) \right] = \int_{\mathbb{R}^{d}} f(x) dx. \end{align}

After using the integrality gap lemma, this is a constructive proof of $c_d \ge 2$.

## What is known about $~c_d$?

The exact value of the constant $c_d$ is known only for $d = \{ 1,2,3,4,5,6,7,8,24\}$. For other $d$, we want to understand the asymptotic behaviour.

#### Some asymptotic lower bounds for large dimensions

Lower bound Contribution of Dimensions covered
$c_d \ge 1$ Minkowksi (1896) $\forall ~d \ge 1$
$c_d \ge 2(d-1)$ Ball (1992) $\forall ~d \ge 1$
$c_{4n} \ge 8.8n$ Vance (2011) $d=4n , n \ge 1$
$c_{2\varphi(n)} \ge n$ Venkatesh (2013) $d=2\varphi(k)$ for some $k$

Since $\lim \inf \left( \frac{\varphi(n)}{n} \log \log n\right) = e^{- \gamma}$, the last bound is the best lower bound (among these, and overall) on $c_d$ in infinitely many dimensions. The first dimension where it outperforms all others in this list is $d=960$.

These bounds don't perform well in low dimensions!

#### Table of comparison of these lower bounds

 Dimension $d$ Lower bound from lattice constructions Lower bound from the table before 2 3 4 8 12 16 24 48 72 $3.628$ $5.925$ $9.867$ $64.94$ $202.6$ $963.9$ $1.618$ $\times 10^4$ $6.524$ $\times 10^6$ $8.881$ $\times 10^8$ $2$ $3$ $8.8$ $17.6$ $28.4$ $35.2$ $52.8$ $105.6$ $158$

However, efforts of constructing explicit lattice have not been so fruitful and already in dimensions $d > 1000$, one of the mentioned asymptotic bounds is the best possible known lower bound.

## Venkatesh's lower bound

Thanks to all the background that we have built, we can actually show Venkatesh's bound.
The idea is to take a nice enough subcollection $Y_d \subseteq X_d$ of lattices and average the lattice-sum function $\Phi_f$ over them.

## Lattices with a cyclic group symmetry

The following is Venkatesh's construction.

Start with $K = \mathbb{Q}[\mu_n]$ , is the $n$th cyclotomic number field. Then $K_{\R}= K\otimes_{\mathbb{Q}}\R$ is a $\varphi(n)$-dimensional real vector space. Set $d = 2 \varphi(n)$

Take $\R^{d} \simeq K_{\R}^{\oplus 2}$. Identify $\Z^{2\varphi(n)}$ with $\mathcal{O}_K^{\oplus 2}$, two copies of the ring of integers in this vector space. Take $G = \Z/n\Z$ acting on this lattice via $\langle \mu_n \rangle$, multiplication by the $n$th roots of unity.

Define now the set $Y_d$ as mentioned before to be $$Y_d = \left\{ \left[ \begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right] \mathcal{O}_K^2 \ | \ a,b,c,d \in K\otimes \R , ad-bc =1_{K_{\R}} \right\}.$$

In conventional notation, this is just $$\{ g ( \mathcal{O}_K^{\oplus 2} ) \ | \ g \in SL_2(K_{\R}) \} \simeq SL_2(K_\mathbb{R} ) /SL_2(\mathcal{O}_K).$$

Again, with this bijection, we will make $Y_d$ a topological space. But does there exists a probability measure on $Y_d$?

Fortunately, the following theorem exists.

#### Theorem

(Borel, Harish-Chandra, 1962)
Let $\mathcal{G}\subseteq SL_n(\C)$ be an algebraic group defined over $\mathbb{Q}$. Then $\mathcal{G}_{\mathbb{R}}/\mathcal{G}_{\mathbb{Z}}$ has a finite invariant measure if any only if $X_{\mathbb{Q}}(\mathcal{G}^{0}) = \{ e\}$, where $\mathcal{G}^{0} \subseteq \mathcal{G}$ is the connected component of identity in the Zariski topology. That is to say, there are no non-trivial $\mathbb{Q}$-characters of $\mathcal{G}^{0}$.

So $Y_d$ now has probability measure. But why make such a $Y_d$?

Note that whenever $a,b,c,d \in {K}_{\R}$, we have that $$\left[ \begin{matrix} a & b \\ c & d \end{matrix}\right]\left[ \begin{matrix} \mu_n & 0 \\ 0 & \mu_n \end{matrix}\right]=\left[ \begin{matrix} \mu_n & 0 \\ 0 & \mu_n \end{matrix}\right]\left[ \begin{matrix} a & b \\ c & d \end{matrix}\right]$$

And if $x,y \in \mathcal{O}_K$ and if $r \notin n \Z$, we have that $$\left[ \begin{matrix} \mu_n^r & 0 \\ 0 & \mu_n^r \end{matrix}\right]\left[ \begin{matrix} x \\ y \end{matrix}\right]=\left[ \begin{matrix} x \\ y \end{matrix}\right] \Rightarrow x=y=0.$$

Putting the two together implies that for each $g\in SL_2(K_{\mathbb{R}})$, $g(\mathcal{O}_K^{\oplus 2})$ is invariant under the cyclic group action of $\langle \mu_n \rangle$, and the action has full orbits on the non-zero points of the lattice.

So if $f$ is the indicator function of an origin-centered ball with respect to a quadratic form that is invariant under $\langle \mu_n \rangle$, we have that $\Phi_f(\Lambda) \in n \Z$ for $\Lambda \in Y_d$. Such a quadratic form always exists by averaging!

Venkatesh, then proves the following analogue of Siegel's theorem.

#### Proposition

Let $d = 2\varphi(n)$ Suppose $f:K_{\mathbb{R}}^2 \rightarrow \mathbb{R}$ is a compactly supported bounded measurable function. Then, the following holds. \begin{align} \int_{Y_d} \Phi_f = \int_{SL_2(K_\mathbb{R})/SL_2(\mathcal{O}_K)}^{} \left( \sum_{v \in g \mathcal{O}_K^{\oplus 2} \setminus \{ 0\}}^{}f(v) \right) dg = \int_{\mathbb{R}^{d}}^{} f(x) dx, \end{align} where the $dx$ on the right-hand side is that Lebesgue measure on $\mathbb{R}^{d}$ that makes $\mathcal{O}_K^{\oplus 2}$ of unit covolume and $dg$ is the unique $SL_2(K_\mathbb{R})$-invariant probability measure on $Y_d$.

This along with the integrality lemma gives $c_{2\varphi(n)} \ge n$.

But what if I told you there is a much more elegant constructive proof?

This approach was developed by Moustrou (2017). It is perfect analogue to Rogers (1947).

#### Theorem

Let $K$ be a number field and $r \in \mathbb{N}$. Let $\mathcal{P} \subseteq \mathcal{O}_K$ be a prime ideal with $N(\mathcal{P})>>1$, $k_\mathcal{P}$ be the residual field with $N(\mathcal{P})$ elements and let $\pi_\mathcal{P}:\mathcal{O}_K^{r} \rightarrow k_{\mathcal{P}}^{r}$ be the natural coordinate-wise projection map. Let $\mathcal{L}_\mathcal{P}$ be the set of sub-lattices of $\mathcal{O}^{r}_K$ that are pre-images of one-dimensional subspaces in this projection map scaled to become unit covolume, i.e. $$\mathcal{L}_\mathcal{P} = \{ C_\mathcal{P} \pi_{\mathcal{P}}^{-1}( {k}_\mathcal{P} v) \ | \ v \in \mathcal{k}_\mathcal{P}^r \setminus \{ 0\} \}, C_\mathcal{P} = N(\mathcal{P})^{-\left(1-\frac{1}{d}\right)} .$$ Consider a compactly supported continuous function $f:K_\mathbb{R}^{r} \rightarrow \mathbb{R}$ and the lattice-sum function $\Phi_f$. \begin{align} \lim_{ N(\mathcal{P}) \rightarrow \infty}\left[ \frac{1}{\# {\mathcal{L}}_p}\sum_{ \Lambda \in {\mathcal{L}}_p} \Phi_{f}\left( \Lambda\right) \right] = \int_{K_\mathbb{R}^r } f(x) dx, \end{align} where the measure on the right hand side is one which makes $\mathcal{O}_K^r \subseteq K_\mathbb{R}^r$ unit covolume.

The proof of this theorem is exactly the same as Rogers ('47) with very little changes.

Set $r=2$, $K=\mathbb{Q}[\mu_n]$ and one can have a growing collection of finitely many lattices $\mathcal{L}_\mathcal{P}$ such that one of them will have packing efficiency $\ge n$, in space of dimension $2\varphi(n)$.

Questions?

## Appendix: How to generate random 2-dimensional lattices

To the map $\psi:[\pi/3,2\pi/3]\times ]0,1] \rightarrow \mathbb{H}$ given by $\psi(a,b) = \cos(a) + i \sin(a)/b$ is a measure preserving map!

It maps the rectangle bijectively to a fundamental domain of $\mathbb{H}/SL_2(\mathbb{Z})$.

Using this, the following map randomly generates a lattice. $\psi_1: [0,2\pi]\times [\pi/3,2\pi/3] \times ] 0,1] \to SL_2(\mathbb{R})\\ \psi_1(x,y,z) = \left[ \begin{smallmatrix} 1 & \cos(y) \\ 0 & 1 \end{smallmatrix} \right] \left[ \begin{smallmatrix} \left(\frac{\sin(y)}{z}\right)^{\frac{1}{2}} & 0 \\ 0 & \left({\frac{\sin(y)}{z}}\right)^{-\frac{1}{2}} \end{smallmatrix} \right] \left[ \begin{smallmatrix} \cos(x) & \sin(x) \\ -\sin(x) & \cos(x) \end{smallmatrix} \right]$

This only works for $d=2$. It is not known how to generalize this to higher dimensions!