Presentation of work done by
\(\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.
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}
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}
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)})$.
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 \} \}.$$
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$.
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
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)$.
We can now, for example, prove the following theorem.
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!