Lattice packings through division algebras

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

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

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.

Recall:
To show $c_d \ge M$, we must prove the existence of $g \in SL_d(\R)$ such that the origin centered ball $B$ with $\mu(B) = M$ 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$!

Here we used a symmetry of $\{\pm 1\}$ under which the ball and the lattice are invariant. Both Venkatesh and the new result use this idea.

Venkatesh's approach was to work with larger a larger group, namely $\Z/n\Z$. For the new result, the symmetries are even bigger and 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). $$

Again, with this bijection, we will make $Y_d$ a topological space. With a bit of work, we can also show that $Y_d$ has a finite measure with respect to the natural left $SL_2(K_{\R})$-invariant measure.

$Y_d$ can be give 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 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 on similar lines. 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}$. Choose $f$ to be the indicator function of a ball invariant under the right action of $G_0$. Then $\Phi_f(\Lambda) \in \{0, |G_0|, 2|G_0|, \dots\}$ for all $\Lambda \in Y_d$.

Conclusion: We get the bounds $$c_{2 \dim_{\mathbb{Q}} D} \ge \# G_0.$$

Let $(G_{0},\mathcal{O}, D ) $ be as finite subgroup inside an order inside a $\mathbb{Q}$-division algebra respectively. Then there exists a lattice packing in dimensions $d= 2\dim_{\mathbb{Q}} D$ whose packing efficiency is at least $\frac{1}{2^{d}} ( \#G_{0} )$.

Note that the following tightening can be done once we have a tuple $(G_{0},\mathcal{O},D)$. When $D$ is a $\mathbb{Q}$-division algebra, the $\mathbb{Q}$-span of $G_{0}$ in $D$ is also a division algebera. Let $\mathbb{Z}\langle G_{0}\rangle \subseteq \mathcal{O}$ be the $\mathbb{Z}$-span of $G_{0}$, then we get that $(G_{0},\mathbb{Z}\langle G_{0}\rangle ,\mathbb{Q}\langle G_{0}\rangle )$ is another tuple that gives us a lower bound.

So we only need to find finite subgroups $G_0$ that live in some $\mathbb{Q}$-division algebra $D$ and we can get the rest.

Fortunately, there exists a complete classification of such finite subgroups due to Amitsur, 1955.

The following construction $D=(E/F,\sigma,\gamma)$ is called a cyclic division algebra.

• $\DeclareMathOperator{\Gal}{Gal}$ $\DeclareMathOperator{\N}{N}$ $F$ is a number field over $\mathbb{Q}$,
• $E/F$ is a cyclic extension of degree $n$, i.e. the field extension $E/F$ is Galois and the Galois group is cyclic,
• $\sigma$ is a generator of the cyclic group $\Gal(E/F)$ and
• $\gamma \in F^{*}$, with the property that the multiplicative order of $\gamma$ in the group $K^{*}/ N_{F}^{E}(E^{*})$ is exactly $n$. That is, $\gamma^{k} \notin N_{F}^{E}(E^{*})$ for any $k \in \{ 1,2,\dots,n-1\}$ and $\gamma^{n} = N_{F}^{E}(x)$ for some $x\in E^{*}$.
  When this happens we say that $\gamma \in F^{*}$ is a non-norm element.

Consider a formal element $b$ that does not commute with $E$ and satisfies $b^{n} = \gamma$. $D$ is now defined as per the isomorphism \begin{align} \label{eq:iDentify} D \simeq E \oplus E b \oplus E b^{2} \oplus \dots \oplus E b^{n-1},\end{align} with the rule that \begin{align} bl = \sigma(l)b \text{ for all }l \in E.\label{eq:ruleofD} \end{align}

If $\gamma$ does not satisfy the non-norm condition, then we call $(E/F,\sigma,\gamma)$ just a cyclic algebra.

All division algebras over $\mathbb{Q}$ are cyclic division algebras!

The dimension of $D=(E/F,\sigma,\gamma)$ over $\mathbb{Q}$ is $\dim_{\mathbb{Q}}D = [F:\mathbb{Q}]n^2 = [E:\mathbb{Q}]n$.

For $1 \le r \le m $ and $(m,r)=1$, consider the integers

• $\DeclareMathOperator{\ord}{ord} n = \ord_{m} r$ is the multiplicative order or $r$ modulo $m$, that is the smallest postive integer $k$ such that $m \mid r^{k}-1$,
• $s = \gcd(r-1,m)$,
• $t = m/s$.

When $r=1$, we will assume $n=s=1$. In these definitions, we will think of $m$ and $r$ as two parameters and $n,s,t$ will automatically be set as defined above.

With this, consider the cyclic algebra $\mathfrak{U}_{m,r} = (\mathbb{Q}(\mu_{m}), F , \sigma_{r}, \mu_{m}^{t} )$, where $F$ is the subfield of $\mathbb{Q}(\mu_{m})$ fixed by $\sigma_{r}$, and $\sigma_{r}$ is the field automorphism of $\mathbb{Q}(\mu_{m})$ given by $\mu_{m} \mapsto \mu_{m}^{r}$.

A priori, $\mathfrak{U}_{m,r}$ is just a $\mathbb{Q}$-algebra which may not be a division algebra. For this to be a division algebra, we want that $\mu_{m}^{t}$ is a non-norm element of $F$.

The division algebra $\mathfrak{U}_{m,r}$ contains the following group.

\begin{align} G_{m,r}:= \langle A,B \ | \ A^{m} = 1, B^{n} = A^{t}, BAB^{-1} = A^{r}\rangle. \end{align} We get that $|G_{m,r}|= mn = m \ord_{m}r$. When $r=1$, $G_{m,r}$ is a cyclic group of order $m$.

It embeds as per $i:G_{m,r} \rightarrow \mathfrak{U}_{m,r}^{*}$ defined sending $A \mapsto \mu_{m}$ and $B \mapsto b$.

When $\ord_m 2$ is odd, one can get a slightly better group of size $24 |G_{m,r}|$ embedded in the division algebra $\left(\tfrac{-1,-1}{\mathbb{Q}}\right) \otimes_{\mathbb{Q}} \mathfrak{U}_{m,r}$.

Amitsur then proves that apart from two more sporadic examples, these two are the only families of examples.

Note that in the two families, $ \# G_0 / \dim_{\mathbb{Q}} \mathbb{Q} \langle G_0 \rangle = m/\varphi(m) $ or $6 m / \varphi(m)$. Looking at this, we can conclude that along no sequence of new constructions will we get $c_d > O(d \log \log d)$.

We can leverage the second family to get a sequence that shows that $c_d \ge O(d (\log \log d)^{7/24})$

$\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 picturized previously.

The following is also an interesting sequence made of new examples.

Let $\{ p_1,p_2,\dots\}$ be the sequence of all primes and suppose $q= 1+\prod_{i=1}^{N}p_{i} $ is a prime for some $N$. Then we can choose an integer $r$ such that $r \equiv 1 \pmod{p_i}$ for each $i$ but has $\ord_{q} r = q-1$, i.e. $r$ is a generator of $\mathbb{F}_{q}^{*}$.

Set $m=q(q-1) = q \prod_{i=1}^{N} p_i$. Then, one can check that $\mathfrak{U}_{m,r}$ is a division algebra so we can have $$ 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)$.

Summary: Amitsur's work allows us to conclude that there are no asymptotic improvements possible when we allow some non-commutative symmetries.

These results prove existence of a lattice with a high packing density. Can we actually construct such lattices algorithmically?

The approach is based on methods of Moustrou (2017). The idea is that $\int_{Y_d} \Phi_f$ can be approximated by averaging $\Phi_f$ over a growing family of finitely many lattices.