Lattice packings through division algebras

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 new result provides 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 new result 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 Venkaesh, 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. 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 \{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}^{*} $$

And if $x,y \in \mathcal{O}$ and if $ \mu \in \mathcal{O}^{*} \setminus \{ 1_{D}\}$, we have that $$\left[ \begin{matrix} x \\ y \end{matrix}\right] \left[ \begin{matrix} \mu & 0 \\ 0 & \mu \end{matrix}\right]=\left[ \begin{matrix} x \\ y \end{matrix}\right] \Rightarrow x=y=0.$$

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.

The following sequence of lower bounds can be constructed purely from the new points. The merit is that these sequences produce lattices with non-commutative symmetries.

$\DeclareMathOperator{\ord}{ord}$ We pick $$m = \prod_{ \substack{ p \text{ is prime} \\ p \le x \\ 2 \nmid \ord_{p} 2} }^{} p$$ and $r=1$. Then observe that with this, we get that $m$ is odd and $\ord_{m}2$ is also odd. Using the classification just given before, we get that $c_{8\varphi(m)} \ge 24m$. This sequence was the one shown previously. It shows that $c_d \ge O(d (\log \log d)^{7/24})$

Suppose $q= 1+\prod_{i=1}^{N}p_{i} $ is a prime for some $N$. These number can be used to show $$ c_{2 (q-1)^{2}\varphi(q-1) } \ge q(q-1)^{2}.$$ If there are infinitely many such primes, then this sequence asymptotically approaches $O(d\log \log d)$.

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

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}

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

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!