# Lattice packings through division algebras

Presentation by

### Nihar P. Gargava

Doctoral student,
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$, choose $r > 0$ and consider the open balls $\{ B_{r}\left( v \right)\}_{v \in \Lambda}$ such for any $v_1, v_2 \in \Lambda$, $B_{r}(v_1) \cap B_{r}(v_2) \neq \emptyset \Rightarrow v_1 = v_2$.

Then $(\Lambda,r)$ is called a lattice sphere packing, or simply lattice packing inside $(\R^d, \langle \ , \ \rangle)$.

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

#### Visualizing in $\R^2$

However, note that $2r$ can be at most $$m(\Lambda) = \min_{v \in \Lambda \setminus \{0\}} ||v|| ,$$ otherwise some balls will begin to intersect.

The goal is to maximize packing density. So take $r = \frac{1}{2}m(\Lambda)$. In that case packing density will be equal to $$\frac{\mu( B_{m(\Lambda)/2}(0) )}{ \mu(\R^d / \Lambda)},$$ and is independent of scaling.

To maximize this over all $\Lambda$, it is sufficient to maximize over unit covolume lattices (i.e. $$\mu(\R^d/\Lambda)$$ = 1)

#### Visualizing in $\R^2$

So we somehow find $\sup_{\substack{\Lambda \subseteq \R^d \\ \mu(\R^d/\Lambda)=1}} \mu\left(B_{m(\Lambda)/2}(0) \right)$

$= \sup_{ g \in SL_d(\R)} \frac{1}{2^d} \mu\left(B_{m(g \Z^d)}(0) \right)$

which we use to define our dimensional constant $c_d$ $\colon= \frac{1}{2^d} c_d$

Putting it together, we have $c_{d} = \sup\left\{ \mu\left( B_{r}(0)\right) \ | \ r> 0,\exists~g \in SL_d(\R) \text{ and } B_{r}(0) \cap g\Z^d = \{ 0\}\right\}.$

Clearly, $$~c_d \in~[0,2^d]$$, so supremum exists!

## What is known about $~c_d$?

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.

#### Some asymptotic lower bounds for large dimensions

Lower bound Contribution of Dimensions covered
$c_d \ge 1$ Minkowksi (1896) $\forall ~d \ge 1$
$c_d \ge 2(d-1)$ Ball (1992) $\forall ~d \ge 1$
$c_{4n} \ge 8.8n$ Vance (2011) $d=4n , n \ge 1$
$c_{2\varphi(n)} \ge n$ Venkatesh (2013) $d=2\varphi(k)$ for some $k$

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

Explicit lattice constructions can help us only upto $d \le 300$.

(Ball, 1992) , the lower bound is as indicated.

(Vance, 2011) , using a probabilistic argument on lattices that lie in vector-space over quaternion division algebra. Works only when $4 \mid d$.

(Venkatesh, 2013) , using a probabilistic argument on lattices that lie in $(K \otimes_\mathbb{Q} \mathbb{R})^2$, $K$ is a cyclotomic field.

(G., 2021) , using a probabilistic argument on lattices that lie in $(D \otimes_\mathbb{Q} \mathbb{R})^2$, $D$ is a division algebra over $\mathbb{Q}$.

#### Theorem

(G. 2021)
Let $D$ be a finite-dimensional division algebra over $\mathbb{Q}$. Let $\mathcal{O} \subseteq D$ be an order in $D$ and $G_{0} \subseteq \mathcal{O}$ be a finite group embedded in the multiplicative group of $D$. Then if $d=2\dim_{\mathbb{Q}}D$, then \begin{align} c_{d} \ge \# G_{0}. \end{align}

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.

## The probabilistic method

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

#### Proposition

There exists a unique (upto scaling) natural measure on $SL_d(\R)/SL_d(\Z)$, left-invariant under $SL_d(\R)$ action on cosets.
Furthermore, $SL_d(\mathbb{R})/SL_d(\mathbb{Z})$ under this has a bounded total measure.

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

## Lattice-sum function

Consider a bounded measurable function with compact support $f:\R^d \rightarrow \R$.
e.g. the indicator function of a ball.

With this, we can now construct the lattice-sum function $\Phi_f(\Lambda): X_d \rightarrow \R$, given as $\Phi_f(\Lambda) = \sum_{v \in \Lambda \setminus \{ 0\}}^{} f(v).$

Since we can generate random lattices, we can talk about the expected value of $\Phi_f(\Lambda)$.

Let us try to do this experimentally! Let us sample over a set $S \subseteq X_d$ of lattices.

So we see that it is almost the integral.

#### Visualizing in $\R^2$

What we are empirically confirming is the following.

#### Theorem

(Siegel, 1945)
Suppose $f:\mathbb{R}^{d} \rightarrow \mathbb{R}$ is a compactly supported bounded measurable function. Then, the following holds. \begin{align} \int_{X_d} \Phi_f = \int_{SL_d(\mathbb{R})/SL_d(\mathbb{Z})}^{} \left( \sum_{v \in g \mathbb{Z}^{d} \setminus \{ 0\}}^{}f(v) \right) dg = \int_{\mathbb{R}^{d}}^{} f(x) dx, \end{align} where the $dx$ on the right-hand side is the usual Lebesgue measure on $\mathbb{R}^{d}$ and $dg$ is the unique $SL_d(\mathbb{R})$-invariant probability measure on $SL_d(\mathbb{R})/SL_d(\mathbb{Z})$.

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.

## Venkatesh's lower bound

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.

#### Theorem

(Venkatesh 2013)
Let $d = 2\varphi(n)$ Suppose $f:K_{\mathbb{R}}^2 \rightarrow \mathbb{R}$ is a compactly supported bounded measurable function. Then, the following holds. \begin{align} \int_{Y_d} \Phi_f = \int_{SL_2(K_\mathbb{R})/SL_2(\mathcal{O}_K)}^{} \left( \sum_{v \in g \mathcal{O}_K^{\oplus 2} \setminus \{ 0\}}^{}f(v) \right) dg = \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}_K^{\oplus 2}$ of unit covolume and $dg$ is the unique $SL_2(K_\mathbb{R})$-invariant probability measure on $Y_d$.

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

## Towards division algebra

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

#### Theorem

(G. 2021)
Let $d = 2 [D:\mathbb{Q}]$. Suppose $f:D_{\mathbb{R}}^2 \rightarrow \mathbb{R}$ is a compactly supported bounded measurable function. Then, the following holds. \begin{align} \int_{Y_d} \Phi_f = \int_{SL_2(D_\mathbb{R})/SL_2(\mathcal{O})}^{} \left( \sum_{v \in g \mathcal{O}^{\oplus 2} \setminus \{ 0\}}^{}f(v) \right) dg = \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}^{\oplus 2}$ of unit covolume and $dg$ is the unique $SL_2(D_\mathbb{R})$-invariant probability measure on $Y_d$.

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.

## Controlled randomness

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

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}

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

#### Theorem

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

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

#### Theorem

(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}^{t} \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^{-1/nmt} \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 therefore prove the following from above.

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

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!

## Thank you for your attention!

Email:
nihar.gargava@epfl.ch

Based on arXiv preprints:
2107.04844, 2111.03684

Slides:
nihargargava.com/effective_seminar

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.

## Appendix: How to generate random 2-dimensional lattices

To the map $\psi:[\pi/3,2\pi/3]\times ]0,1] \rightarrow \mathbb{H}$ given by $\psi(a,b) = \cos(a) + i \sin(a)/b$ is a measure preserving map!

It maps the rectangle bijectively to a fundamental domain of $\mathbb{H}/SL_2(\mathbb{Z})$.

Using this, the following map randomly generates a lattice. $\psi_1: [0,2\pi]\times [\pi/3,2\pi/3] \times ] 0,1] \to SL_2(\mathbb{R})\\ \psi_1(x,y,z) = \left[ \begin{smallmatrix} 1 & \cos(y) \\ 0 & 1 \end{smallmatrix} \right] \left[ \begin{smallmatrix} \left(\frac{\sin(y)}{z}\right)^{\frac{1}{2}} & 0 \\ 0 & \left({\frac{\sin(y)}{z}}\right)^{-\frac{1}{2}} \end{smallmatrix} \right] \left[ \begin{smallmatrix} \cos(x) & \sin(x) \\ -\sin(x) & \cos(x) \end{smallmatrix} \right]$

This only works for $d=2$. It is not known how to generalize this to higher dimensions!