Dense packings via lifts of codes to division rings

Presentation of work done by

Nihar Gargava, Vlad Serban

Chair of Number Theory,
Section of Mathematics,
École Polytechnique Fédérale de Lausanne

What is a lattice packing?

\(\DeclareMathOperator{\R}{\mathbb{R}}\)\(\DeclareMathOperator{\Z}{\mathbb{Z}}\)\(\DeclareMathOperator{\C}{\mathbb{C}}\)\( \DeclareMathOperator{\F}{\mathbb{F}}\)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$, we define the packing radius $r_{\text{pack}}$ to be the largest possibt radius $r$ such that the open balls $\{ B_{r}\left( v \right)\}_{v \in \Lambda}$ satisfy $v_1, v_2 \in \Lambda$, $B_{r}(v_1) \cap B_{r}(v_2) \neq \emptyset \Rightarrow v_1 = v_2$.

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_{\text{pack}}}(0) )}{ \mu(\R^d / \Lambda)} \] It is always in the interval $[0,1]$ and is scaling independent.

In $2$ dimensions, the densest lattice packing is the hexagonal lattice.

Visualizing in $\R^2$

For a lattice $\Lambda$, we denote it's packing density as $\Delta(\Lambda)$

Lattices have lots of applications in coding theory. In particular, they form good candidates for Euclidean codes under an Additive White Gaussian Noise (AWGN) model.

Be careful!
Coding theoretic packing density is defined slightly differently. For $\Lambda \subseteq \mathbb{R}^{d}$ \begin{align} \frac{r_{\text{pack}(\Lambda)}}{r_{\text{eff}(\Lambda)}} = \Delta(\Lambda)^{\frac{1}{d}}, \end{align}


(Minkowski, ~1896)
It is possible to have a sequence of lattices $\Lambda^{(d)} \subseteq \mathbb{R}^{d}$ as $d \rightarrow \infty$ such that \begin{align} \Delta(\Lambda^{(d)}) \ge 2^{-d}. \end{align}

Improvements have been made on this by Rogers, Vance, Venkatesh. The current best bound is by Venkatesh: \begin{align} \limsup\Delta(\Lambda^{(d)}) \ge 2^{-d} \cdot \frac{d}{2} \log \log d. \end{align}

Open problem:

What are explicit descriptions of lattices that prove these lower bounds as $d \to \infty$? That is, what are the lattices that have the most optimal packing density in large dimensions?

In terms of coding theory, this problem is to find explicitly lattices that achieve "goodness" \begin{align} \Delta(\Lambda^{(d)})^{\frac{1}{d}} = \frac{r_{\text{pack}}(\Lambda^{(d)})}{r_{\text{eff}}(\Lambda^{(d)})} \ge \frac{1}{2}, \end{align} for a subsequence of lattices $\Lambda^{(d)} \subseteq \mathbb{R}^{d}$ as $d \to \infty$.

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

Finite (exponential) time algorithms to generate such lattices exist. The basic idea is to use some variant of Leech-Sloane Construction A on codes and use a probabilistic argument like Gilbert-Varshamov.

Some important work in this direction is due to Rush, Sloane, Loeliger, Gaborit, Zémor.

The latest in the line of such works is Moustrou (2016) and Campello (2018). They considered variants of Construction A over residue algebras of number fields and Hurwitz integers respectively. This narrows the class of lattices to look for in order to achieve Minkowski's lower bound.

This joint work is the latest in this series. It seems to be the most general such result so far. We encompasses all the previous constructions and the best lower bounds on $\limsup \Delta(\Lambda^{(d)})$.

How do effective results work?

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

Denote $X_d$ to be the set of all unit covolume lattices in $\mathbb{R}^{d}$. 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 let $f:\R^d \to \R$ be a compactly supported Riemann integrable function. Let $\Phi_f:X_d \to \R$ be the lattice-sums of $f$, i.e. $\Phi_f(\Lambda): X_d \rightarrow \R$, given as \[ \Phi_f(\Lambda) = \sum_{v \in \Lambda \setminus \{ 0\}}^{} f(v).\]

So let us try to average $\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


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

We combine this knowledge with an integrality gap argument as follows.

Set $f$ as the indicator function of a ball. Let the radius vary. The left hand side is an average over positive integers. Let $p$ be a very large prime number. \begin{align} \left[ \frac{1}{\# {\mathcal{L}}_p}\sum_{ \Lambda \in {\mathcal{L}}_p} \Phi_{f}\left( \Lambda\right) \right] \simeq \int_{\mathbb{R}^{d}} f(x) dx. \end{align}

For any $\Lambda \in \mathcal{L}_p$, 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$ and a large enough prime number $p$, $$\left[ \frac{1}{\# {\mathcal{L}}_p}\sum_{ \Lambda \in {\mathcal{L}}_p} \Phi_{f}\left( \Lambda\right) \right] \le 2 - \varepsilon$$

Hence one of the finitely many lattices in $\mathcal{L}_p$ is the lattice that we need!

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), and hence narrowing down the class of lattices to consider. The packing bounds attained by Moustrou reach those by Venkatesh.

We can also generalize the proof for division rings. But what are analogues 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)$.


(G., Serban, 2021)
Let $d = 2 [D:\mathbb{Q}]$. Let $\mathfrak{p} \subseteq \mathcal{O}$ be a prime as above and let $\pi_\mathfrak{p}:\mathcal{O}^{2} \rightarrow M_n(\mathbb{F}_q)^{2}$ be the projection map as above (on two copies of $\mathcal{O}$). Consider the set of sub-lattices of $\mathcal{O}^{2}$ that are pre-images of $M_n(\mathbb{F}_q)$-submodules of $\mathbb{F}_q$-dimension $n(2n-1)$, i.e. \begin{align*} \mathcal{C}_{\mathfrak{p}} & = \{ C \subseteq M_n(\mathbb{F}_q)^{ 2 } \ | \ C \text{ is a $M_n(\mathbb{F}_q)$-submodule }\simeq (\mathbb{F}_q^{n})^{\oplus (2n-1)}\} , \\ \mathcal{L}_{\mathfrak{p} } & = \{ \beta_{\mathfrak{p}} \pi_{\mathfrak{p}}^{-1}(C) \ | \ C \in \mathcal{C}_{\mathfrak{p}}\} , \ \ \beta_{\mathfrak{p}} = q^{-\frac{n}{d}} \end{align*} 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}$. Then the following holds. \begin{align} \lim_{ \#\mathbb{F}_q \rightarrow \infty} \left[ \frac{1}{\#{\mathcal{L}}_{\mathfrak{p}}} \sum_{ \Lambda \in {\mathcal{L}}_{\mathfrak{p}} } \Phi_{f}\left( \Lambda\right) \right] = \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}^{2} \subseteq (D \otimes \mathbb{R})^2 \simeq \mathbb{R}^d$ of unit covolume.

We can now, for example, prove the following theorem.


(G., Serban, 2021)
Let $m_k=\prod_{\substack{p\leq k \text{ prime}\\2\nmid\mathrm{ord}_2p}}p$ and set $n_k:=8\varphi(m_k)$. Then for any $\varepsilon>0$ there is an effective constant $c_\varepsilon$ such that for $k>c_\varepsilon$ a lattice $\Lambda$ in dimension $n_k$ with density $$\Delta(\Lambda)\geq (1-\varepsilon)\frac{24\cdot m_k}{2^{n_k}}$$ can be constructed in $e^{4.5\cdot n_k\log(n_k)(1+o(1))}$ binary operations. This construction leads to the asymptotic density of $\Delta(\Lambda)\geq (1-e^{-n_k})\frac{3\cdot n_k(\log\log n_k)^{7/24}}{2^{n_k}}$.

This is one example of theorems that can be produced using the our division ring construction by choosing the sequence of division rings to work with. By varying this sequence of division rings, almost all previously known results can be recovered.

This leads us to hints over what algebraic structures to look for in our haystack!

Thank you for your attention!


Based on arXiv preprints:
2107.04844, 2111.03684


How does it work?:
This presentation and all the animations are written in html and javascript using reveal.js and d3.js.

Feel free to contact for questions/comments.