Random Lattices as Sphere Packings

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. In this talk, we will only focus on lower bounds.

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$.

To recover Venkatesh's result, set $D=\mathbb{Q}(\mu_n)$, $\mathcal{O} = \mathbb{Z}[\mu_n]$ and $G_0 = \langle \mu_n \rangle$. Hence, this gives \begin{align} c_{2 \varphi(n)} \ge n \end{align}

The cherrypicked sequence of Venkatesh achieves an asymptotic growth of $O( d \log \log d )$. This is achieved by setting $K$ as the $n$th cyclotomic field where $n=\prod_{p < N} p$.

The division algbera construction gives more freedom to cherrypick sequences. Instead of choosing a sequence of cyclotomic fields, we can now choose sequences of $\mathbb{Q}$-divison algebras. However, no such sequence will be able to give an asymptotic result strictly better than $O( d \log \log d )$. Improvements in individual dimensions is still possible, as shown before.

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)$.

This gives us a probability space. Hence we can talk about random unit covolume lattices.

What we are empirically confirming is the following.

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$!

Both Venkatesh and the division algebra lattices use this idea. What we want is to find expectation of the lattice sum over a smaller subset of lattices that have a larger group of symmetries.

For Venkatesh, the group of symmetries is always a cyclic group. For the new result, the symmetries are non-commutative.

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.

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

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

$Y_d$ can be given probability measure.

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 \{0,n,2n,3n,4n,\ldots\}$ for $\Lambda \in Y_d$. Such a quadratic form always exists by averaging!

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

Conclusion: By setting $f$ as the indicator function of a ball in a suitable quadratic form, we conclude that there exists some lattice $\Lambda \in Y_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 $ n - \varepsilon$.

Another conclusion: $c_{2 \varphi(n)} \ge n$ for all $n$!

The division algebra case is also very similar. Let $D$ be a finite-dimensional division algebra over $\mathbb{Q}$. Let $\mathcal{O} \subseteq D$ be an order in $D$. We work in $d = 2 \dim_{\mathbb{Q}} D$ dimensions. Define $D_{\R}= D \otimes_\mathbb{Q} \R$. $$Y_d = \{ g ( \mathcal{O}^{\oplus 2} ) \ | \ g \in SL_2(D_{\R}) \} \simeq SL_2(D_\mathbb{R} ) /SL_2(\mathcal{O}). $$
Here $$ SL_2(D_{\R}) = \left\{ \left[ \begin{matrix} a & b \\ c & d \end{matrix}\right] \ | \ \left[ \begin{matrix} x \\ y \end{matrix}\right] \mapsto \left[ \begin{matrix} ax + by \\ cx + dy \end{matrix}\right] \text{ is a measure preserving map on } D_{\R}^{\oplus 2} \right\}$$

$Y_d$ consists of lattices that are invariant under diagonal right-multiplication by units in $\mathcal{O}$ $$ g ( \mathcal{O}^{\oplus 2} ) = g ( \mathcal{O}^{\oplus 2} ) \left[ \begin{matrix} \mu & 0 \\ 0 & \mu \end{matrix}\right] , \text{ for any } \mu \in \mathcal{O}^{*} $$

To get packing bounds, fix a finite subgroup $G_0 \subseteq \mathcal{O}^*$ to act diagonally on the right of $\mathcal{O}^{\oplus 2}$. We get the bounds $$c_{2 \dim_{\mathbb{Q}} D} \ge \# G_0.$$

In fact we only need to find finite subgroups that live in $\mathbb{Q}$-division algebras. The order $\mathcal{O}$ can be aligned according to the finite group. Fortunately, there exists a complete classification of such finite subgroups due to Amitsur, 1955.

For brewity, we will not discuss classification of of finite subgroups ofdivision rings. Instead, let us talk about effectiveness of these results.

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$.

What do you expect this quantity to be as $p \to \infty$? \begin{align} \frac{1}{\#\mathcal{L}_p}\sum_{\Lambda \in \mathcal{L}_p} \Phi_f(\Lambda) = \frac{1}{\#\mathcal{L}_p}\sum_{\Lambda \in \mathcal{L}_p} \left( \sum_{v \in \Lambda \setminus \{0\} } f(v) \right) \end{align}

The answer to this question is very classical.

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

Since we are working with finitely many lattices, we can use this procedure to obtain a probabilistic algorithm that randomly generates lattices with good packing efficiency

This idea can be generalized to number fields, as was shown by (Moustrou, 2016).

We can also generalize the proof for division rings. But what are analogue of prime ideals for division rings?

Suppose $D$ is a $\mathbb{Q}$-division ring, $K$ be the center of the ring and $\mathcal{O}$ be an $\mathcal{O}_K$-order in $D$. Let $[D:K]=n^2$.

A prime ideal of an $\mathcal{O}$ is a proper two-sided ideal $\mathfrak{p}$ in $\mathcal{O}$ such that $K\cdot \mathfrak{p} =D$ and such that for every pair of two sided ideals $S,T$ in $\mathcal{O}$, we have that $S\cdot T\subset \mathfrak{p}$ implies $S\subset \mathfrak{p}$ or $T\subset \mathfrak{p}$.

Important property: For all but finitely many primes $\mathfrak{p}$ of $\mathcal{O}$, the quotient $\mathcal{O}/\mathfrak{p}\mathcal{O}$ is isomorphic to $M_n(\mathbb{F}_q)$, where $\mathcal{O}_K/\mathcal{O}_K \cap \mathfrak{p} \cong \mathbb{F}_q$.

Hence we get countably many projection maps $\pi_\mathfrak{p}: \mathcal{O} \rightarrow M_n(\mathbb{F}_q)$.

We can therefore prove the following from above.

The sequence above is actually the sequence of green points mentioned before. This theorem shows that the construction is also effective.

The condition of $ 2 \nmid \mathrm{ord}_p 2 $ has to do with division ring contructions. Details can be given on request!

This is like the problem of finding hay in a haystack!

Need to decrease the search space to get smaller running times! This is ongoing work...

For the $SL_d(\mathbb{R})/SL_d(\mathbb{Z})$ case, we have (Rogers, 1955-56) papers. This created a lower bound of $c_d \ge \tfrac{1}{3}\sqrt{d}$, which was the best back then.

Such work has not been satisfactorily generalized to $SL_t(K)/SL_t(\mathcal{O}_K)$. This is an ongoing project jointly with V. Serban and M. Viazovska.

For $SL_d(\mathbb{R})/SL_d(\mathbb{Z})$ and $SL_d(K)/SL_d(\mathcal{O}_K)$, this is known due to the work of Eskin, Oh, Ullmo.

For division rings, this is still open.