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!