# Dense packings via lifts of codes to division rings

Nihar Gargava and Vlad Serban

###### Abstract.

We obtain algorithmically effective versions of the dense lattice sphere
packings constructed from orders in $\mathbb{Q}$-division rings by the first
author. The lattices in question are lifts of suitable codes from prime
characteristic to orders $\mathcal{O}$ in $\mathbb{Q}$-division rings and we
prove a Minkowski–Hlawka type result for such lifts. Exploiting the additional
symmetries under finite subgroups of units in $\mathcal{O}$, we show this
leads to effective constructions of lattices approaching the best known lower
bounds on the packing density $\Delta_{n}$ in a variety of new dimensions $n$.
This unifies and extends a number of previous constructions.

This work was partially funded by the Swiss National Science Foundation (SNSF)

##  1\. Introduction

The sphere packing problem in $\mathbb{R}^{n}$ is concerned with maximizing
the proportion of Euclidean space covered by a set of balls of equal radius
and disjoint interiors. We will mostly be concerned with the _lattice_ sphere
packing problem, where the balls are required to be centered at points on an
$n$-dimensional lattice $\Lambda$. The proportion achieved by a particular
lattice, called the packing density of $\Lambda$, is then given by

$\Delta(\Lambda):=\frac{\mathrm{Vol}(\mathbb{B}_{n}(\lambda_{1}(\Lambda)))}{2^{n}\mathrm{Vol}(\Lambda)},$

where $\lambda_{1}(\Lambda)$ denotes the shortest vector length in $\Lambda$,
$\mathbb{B}_{n}(r)$ a ball of radius $r$ and $\mathrm{Vol}(\Lambda)$ denotes
the covolume of the lattice. We also denote by $\Delta_{n}$ the supremum of
lattice packing densities that can be achieved in $n$ dimensions. Its value is
only known in a handful of dimensions, see for instance the summary [CS88,
1.5.] as well as [CK04]. The density is achieved by highly symmetric lattices
such as root lattices or the Leech lattice. Owing to highly celebrated results
[Hal05, Via17, CKM+17], some of these are even known to solve the general
sphere packing problem. For arbitrary dimensions, the best known upper and
lower bounds on $\Delta_{n}$ are however exponentially far apart as $n$
increases (see e.g., the survey article [Coh16] for more background). In this
article we shall be concerned with lower bounds as $n$ increases and with
giving effective constructions of lattices approaching these bounds.

The classical Minkowski–Hlawka theorem [Hla43] states that $\Delta_{n}\geq
2\frac{\zeta(n)}{2^{n}}$, a bound which Rogers [Rog47] later improved by a
linear factor to $\Delta_{n}\geq\frac{cn}{2^{n}}$ for $c=2/e\approx 0.74$. The
constant was subsequently sharpened to $c=1.68$ by Davenport-Rogers [DR47] and
$c=2$ by Ball [Bal92] for all $n$. More recently, Vance [Van11] showed using
lattices which are modules over the Hurwitz integers that one may take
$c=24/e\approx 8.83$ and Venkatesh [Ven12] showed that for $n$ large enough
one may take $c=65963$. Moreover, by considering lattices from maximal orders
in cyclotomic fields, Venkatesh was able to achieve for infinitely many
dimensions the improvement $\Delta_{n}\geq\frac{n\log\log n}{2^{n+1}}$. The
first author [Gar21] then extended such results to lattices coming from orders
$\mathcal{O}$ in arbitrary $\mathbb{Q}$-division algebras. This was achieved
by proving a Siegel mean value theorem (see [Sie45, Gar21]) in this setting
and exploiting the additional symmetries of the lattices under the group of
finite order units in $\mathcal{O}^{\times}$ to obtain dense packings. In
particular, new sequences of dimensions such that
$\Delta_{n}\geq\frac{c_{1}\cdot n\log\log(n)^{c_{2}}}{2^{n}}$ for constant
$c_{1},c_{2}>0$ are uncovered.

Lattices provide an important tool for coding, for instance for the Additive
White Gaussian Noise (AWGN) model. For such applications it is often desirable
to have lattices that are “good” in the sense of achieving high packing
densities (see e.g., [Loe97]). The sphere packing problem is moreover
crucially connected to optimizing parameters of codes and energy optimization
(see e.g.,[CS88, UniversalOpt]). However, despite having Minkowski’s lower
bound for over a century, producing explicit families of lattices that achieve
these asymptotic bounds in less than astronomical running time has proved
elusive. Currently known polynomial time algorithms produce lattices whose
densities are exponentially worse than these bounds [litsyn1987constructive].
In this paper, we make the currently best known existential results for
$\mathbb{Q}$-division algebras effective by exhibiting finite sets of lattices
which for large enough dimension must contain a lattice approaching the non-
constructive lower bounds stated above.

Indeed, for orders $\mathcal{O}$ in a $\mathbb{Q}$-division algebra, we
consider for suitable primes $p$ and for $t\geq 2$ the reduction map
$\phi_{p}:\mathcal{O}^{t}\to(\mathcal{O}/p\mathcal{O})^{t}$ and may identify
the quotient with a product of matrix rings over a finite field
$\mathbb{F}_{q}$. The sets of lattices $\mathbb{L}_{p}$ we consider are then
re-scaled pre-images via $\phi_{p}$ of codes in
$(\mathcal{O}/p\mathcal{O})^{t}$ of a certain fixed
$\mathbb{F}_{q}$-dimension. Our first main result, Theorem 3.7, is in effect a
Siegel mean value theorem for these sets of lifts of codes valid for general
finite dimensional $\mathbb{Q}$-division algebras. We refer the reader to
Section 3 for detailed statements, whereas some useful preliminary results on
lattices from division algebras are established in Section 2.

In Section 4, the extra symmetries of these lattices under finite subgroups of
$\mathcal{O}^{\times}$ is exploited to obtain (see Theorem 4.4):

######  Theorem 1.1.

Let $A$ be a central simple division algebra over a number field $K$ with ring
of integers $\mathcal{O}_{K}$. Let $\mathcal{O}$ be an $\mathcal{O}_{K}$-order
in $A$. Let $n^{2}=[A:K]$, $m=[K:\mathbb{Q}]$ and let $t\geq 2$ be a positive
integer. Let $G_{0}$ be a fixed finite subgroup of $\mathcal{O}^{\times}$.
Then there exists a lattice $\Lambda$ in dimension $n^{2}mt$ achieving

$\Delta(\Lambda)\geq\frac{|G_{0}|\zeta(mn^{2}t)\cdot t}{2^{mn^{2}t}\cdot
e(1-e^{-t})}.$

Moreover, there exists for any $\varepsilon>0$ an $\mathcal{O}$-lattice
$\Lambda_{\varepsilon}$ in dimension $n^{2}mt$ of packing density

$\Delta(\Lambda_{\varepsilon})\geq(1-\varepsilon)\cdot\frac{|G_{0}|\zeta(mn^{2}t)\cdot
t}{2^{mn^{2}t}\cdot e(1-e^{-t})}$

which can be constructed. Indeed, $\Lambda_{\varepsilon}$ is obtained by
applying Proposition 4.1 to a suitable sublattice of $\mathcal{O}^{t}$
obtained as a pre-image via reduction modulo primes $\mathfrak{p}$ of
$\mathcal{O}_{K}$ of large enough norm of a code. The code in question is
isomorphic to $k$ copies of simple left
$\mathcal{O}/\mathfrak{p}\mathcal{O}$-modules for some $nt-t<k<nt$.

Note that Proposition 4.1 mentioned in the theorem is a version of a lemma of
Minkowski extended to the division algebra setting. The theorem above is
derived from Theorem 3.7 by mimicking an approach of Rogers [Rog47], later
used by Vance [Van11] and Campello [Cam18]. In this way, we combine nearly all
of these existence results and generalize them in one theorem.

In order to obtain the densest packings asymptotically, one therefore seeks
families of orders $\mathcal{O}$ with large finite unit groups
$G_{0}\subset\mathcal{O}^{*}$. Building on Amitsur’s classification [Ami55]
and following [Gar21], we give examples of such families. For instance, one
may consider quaternion algebras over cyclotomic fields and hope to combine
the improvements over the Minkowski-Hlawka bounds obtained by Vance and
Venkatesh. However, due to a parity condition on the dimension, this is not
quite the case and one obtains asymptotic lower bounds

$\Delta_{n}\geq\frac{3\cdot(\log\log n)^{7/24}n\cdot(1+o(1))}{2^{n}}.$

Still, the lower bound obtained exceeds the lower bound from cyclotomic fields
$n\log\log n\cdot 2^{-(n+1)}$ in less than astronomical dimensions due to the
improved constant. Moreover, one can exhibit lattices from non-commutative
rings that achieve the same asymptotic density as the cyclotomic lattices (see
Proposition 4.9).

Finally, in Section 5 we establish effectivity by giving lower bounds on the
norm of the prime $\mathfrak{p}$ so that packing densities such as in Theorem
1.1 can be achieved, both by varying the division algebra and its dimension
(Theorem 5.1) and by varying the rank of the $\mathcal{O}$-lattices to obtain
an effective version of Vance’s results (Proposition 5.6). As an application,
we obtain in Proposition 5.4:

######  Proposition 1.2.

Let $m_{k}=\prod_{\begin{subarray}{c}p\leq k\text{ prime}\\\
2\nmid\operatorname{ord}_{2}p\end{subarray}}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}}}$.

We ought to stress that such effective lower bounds on the density are not the
first of their kind but that there is a rather rich history of such results.
Rush [Rus89], building on work with Sloane [RS87], recovered the Minkowski-
Hlawka bound via coding-theoretic results such as the Varshamov-Gilbert bound
and by lifting codes via the Leech-Sloane Construction A (see [CS88, Chapter
5]). The connection between random coding and such averaging results was
further explicited by Loeliger [Loe97]. This leads to families of approximate
size $e^{n^{2}\log n}$ in which to search for lattices achieving the
Minkowski-Hlawka bound. Gaborit and Zémor [GZ07] exploited additional
structures to reduce the family size to $e^{n\log n}$. Finally, Moustrou
[Mou16] used a similar approach for cyclotomic lattices to obtain an effective
version of Venkatesh’s result. This approach was further formalized by
Campello [Cam18], where an example of such results for quaternion algebras is
also mentioned. Our work thus owes a lot to these existing constructions. In
particular, our approach is chiefly based on Moustrou’s and Campello’s work
[Mou16, Cam18] and extends the scope of their results to division algebras,
allowing symmetries from arbitrarily large non-commutative finite groups. We
also note that the utility of codes from division rings is well-studied by
coding theorists, see for example [BO13, DO16, VL21].

We hope that this article provides a useful addition to both the coding-
theoretic and mathematical literature. The effective results we arrive at in
Section 5 typically have a complexity of $e^{C\cdot n\log n(1+o(1))}$, which
is similar to [Mou16, Theorem 1]. However, the effective version of Vance’s
result (see Corollary 5.7) has complexity $e^{1/4\cdot n^{2}\log n(1+o(1))}$
and it should be similar for other constructions obtained by increasing the
$\mathcal{O}$-rank of the lattices.

The running times correspond to an exhaustive search through all the finitely
many lattice candidates and it would be interesting to examine if one can
further reduce the complexity of this search. It should be remarked that our
results can still be used to quickly generate one of these random lattices in
high dimensions that have prescribed symmetries and are expected to have large
minimal vectors. Furthermore, our results hint towards the algebraic
structures that one might look for in order to construct explicit families of
lattices that are asymptotically “good”.

##  2\. Preliminaries on division rings

In this section, we recall some definitions and results on central simple
algebras and in particular division rings. The primary reference is Reiner’s
book [Rei03]. Let $\mathcal{O}_{K}$ denote a Dedekind ring with quotient field
$K$ and let $A$ denote a separable $K$-algebra.

######  Definition 2.1.

An $\mathcal{O}_{K}$-order in $A$ is a subring $\mathcal{O}$ of $A$ having the
same identity element and such that $\mathcal{O}$ is a _full_
$\mathcal{O}_{K}$-lattice in $K$, i.e. $\mathcal{O}$ is a finitely generated
$\mathcal{O}_{K}$-submodule of $A$ such that $K\cdot\mathcal{O}=A$.

The existence of $\mathcal{O}_{K}$-orders and maximal orders is easily shown.
From now on let $\mathcal{O}$ denote such an order. We first review some
results about ideals in $\mathcal{O}$. Note that we shall typically state
results for general $\mathcal{O}_{K}$-orders, although simply dealing with
maximal orders suffices for our applications.

###  2.1. Prime ideals

######  Definition 2.2.

A prime ideal of $\mathcal{O}$ is a proper two-sided ideal $\mathfrak{p}$ in
$\mathcal{O}$ such that $K\cdot\mathfrak{p}=A$ and such that for every pair of
two sided ideals $S,T$ in $\Lambda$, we have that $S\cdot
T\subset\mathfrak{p}$ implies $S\subset\mathfrak{p}$ or
$T\subset\mathfrak{p}$.

For a prime $p$ of $\mathcal{O}_{K}$ we shall denote by
$\mathcal{O}_{p},A_{p}$ the localizations at $p$ of the
$\mathcal{O}_{K}$-order $\mathcal{O}$ and of $A$ and by
$\hat{\mathcal{O}}_{p},\hat{A_{p}}$ the respective completions. Finally let
$\mathrm{rad}(R)$ denote the Jacobson radical of a ring $R$. It is easy to
obtain (see [Rei03, Thm 22.3,22.4]) the characterization:

######  Theorem 2.3.

The prime ideals of an $\mathcal{O}_{K}$-order $\mathcal{O}$ coincide with the
maximal two-sided ideals of $\mathcal{O}$. If $\mathfrak{p}$ is a prime ideal
of $\Lambda$, then $p=\mathfrak{p}\cap\mathcal{O}_{K}$ is a non-zero prime of
$\mathcal{O}_{K}$, and $\overline{\mathcal{O}}:=\mathcal{O}/\mathfrak{p}$ is a
finite dimensional simple algebra over the residue field $\mathcal{O}_{K}/p$.
Moreover, when $A$ is a central simple $K$-algebra, there is a bijection
$\mathfrak{p}\leftrightarrow p$ between the set of primes of $\mathcal{O}$ and
of $\mathcal{O}_{K}$, given by

$p=R\cap\mathfrak{p}\text{ and
}\mathfrak{p}=\mathcal{O}\cap\mathrm{rad}(\mathcal{O}_{p}).$

We note that when $A$ is a central simple $K$-algebra, the quotient
$\mathcal{O}/\mathfrak{p}$ is a simple Artin ring and hence a ring of matrices
over a division ring. In particular, when $\mathcal{O}_{K}/p$ is a finite
field the quotient $\mathcal{O}/\mathfrak{p}$ is isomorphic to a ring of
matrices over a finite field.

We now summarize the behavior of $\mathcal{O}$ and $A$ under localization as
well as the splitting behavior for central simple algebras:

######  Theorem 2.4.

Let $\mathcal{O}$ be a maximal order in a central simple $K$-algebra $A$. Let
$p$ denote a prime of $\mathcal{O}_{K}$. Then the completion $\hat{A_{p}}$ is
a central simple $\hat{K}_{p}$-algebra and $\hat{\mathcal{O}}_{p}$ is a
maximal order. Moreover:

  1. (1)

For almost every prime $p$ of $\mathcal{O}_{K}$, we have that

$\hat{A_{p}}\cong M_{n}(\hat{K}_{p})$

with $n^{2}=[A:K]$ (_split_ or _unramified_ case). Moreover $p$ is split if
and only if the corresponding prime ideal $\mathfrak{p}$ of $\mathcal{O}$ as
in Theorem 2.3 is just $p\mathcal{O}$.

  2. (2)

The order $\Lambda=M_{n}(\hat{\mathcal{O}}_{p})$ is a maximal
$\hat{\mathcal{O}}_{K_{p}}$-order in $M_{n}(\hat{K}_{p})$ having a unique
maximal two-sided ideal $\pi_{\hat{K}_{p}}\Lambda$, where $\pi_{\hat{K}_{p}}$
is a prime element of the discrete valuation ring $\hat{\mathcal{O}}_{K_{p}}$.
The powers

$(\pi_{\hat{K}_{p}}\Lambda)^{t}=\pi_{\hat{K}_{p}}^{t}\cdot\Lambda\text{ for
}t=0,1,2,\ldots$

exhaust all the non-zero two-sided ideals of $\Lambda$ and any maximal
$\hat{\mathcal{O}}_{K_{p}}$-order is of the form $u\Lambda u^{-1}$ for
$u\in\mathrm{GL}_{n}(\hat{K}_{p})$.

###### Proof.

These are well-known results, see e.g. [Rei03, Theorems 17.3, 32.1]. ∎

In what follows, we will thus use the same notation $\mathfrak{p}$ for the
primes of $\mathcal{O}_{K}$ and the corresponding prime in $\mathcal{O}$ in
the split case.

We can now establish the following lemma which will provide the necessary
reduction maps in order to lift codes from characteristic $p$ to division
rings:

######  Lemma 2.5.

Let $K$ be a number field and $A$ a division algebra with center $K$ so that
$[A:K]=n^{2}$. Let $\mathcal{O}$ be an $\mathcal{O}_{K}$-order in $A$. Then
for all but finitely many primes $\mathfrak{p}$ of $\mathcal{O}_{K}$, the
quotient $\mathcal{O}/\mathfrak{p}\mathcal{O}$ is isomorphic to
$M_{n}(\mathbb{F}_{q})$, where
$\mathcal{O}_{K}/\mathfrak{p}\mathcal{O}_{K}\cong\mathbb{F}_{q}$.

###### Proof.

This follows from our previous considerations and in particular the fact that
only finitely many primes of $A$ are ramified. Indeed, first assume that
$\mathcal{O}$ is a maximal order. Then we know that the completion satisfies

$\hat{A}_{\mathfrak{p}}=A\otimes_{K}\hat{K}_{\mathfrak{p}}\cong
M_{n}(\hat{K}_{\mathfrak{p}})$

and moreover that the order $\hat{\mathcal{O}}_{\mathfrak{p}}$ in the local
case is maximal and conjugate to
$M_{n}(\hat{\mathcal{O}}_{K_{\mathfrak{p}}})$. In particular, we then have

$\mathcal{O}/\mathfrak{p}\mathcal{O}\cong
M_{n}(\hat{\mathcal{O}}_{K_{\mathfrak{p}}})/\mathrm{rad}(M_{n}(\hat{\mathcal{O}}_{K_{\mathfrak{p}}}))\cong
M_{n}(\hat{\mathcal{O}}_{K_{\mathfrak{p}}}/\mathfrak{p}\hat{\mathcal{O}}_{K_{\mathfrak{p}}})\cong
M_{n}(\mathbb{F}_{q}).$

When the order is not maximal, the same holds if one additionally avoids
primes dividing the index of $\mathcal{O}$ in a maximal order since their
localizations will coincide at those primes. ∎

If in the above one wishes to ensure $q=p$ is prime this can also typically be
achieved for infinitely many primes by imposing that $p$ splits in
$\mathcal{O}_{K}$ and by the Čebotarev density theorem.

###  2.2. Lattices from orders

The central simple algebras $A$ are equipped with natural embeddings
$A\hookrightarrow A\otimes_{\mathbb{Q}}\mathbb{R}$. The latter space being a
semisimple $\mathbb{R}$-algebra, it can be identified with a product of matrix
rings over $\mathbb{R},\mathbb{C}$ and $\mathbb{H}$ respectively, depending on
the signature of $K$ and the splitting behavior of $A$ at infinity. An
$\mathcal{O}_{K}$-order then embeds as a lattice into this space. We establish
some properties of these lattices in the next two subsections.

######  Lemma 2.6.

Any semisimple $\mathbb{R}$-algebra $A$ admits an involution $(\
)^{*}:A\rightarrow A$ such that the following conditions are satisfied.

  * •

For any $a,b\in A$, we have $(ab)^{*}=b^{*}a^{*}$.

  * •

The trace yields a positive definite quadratic form
$a\mapsto\operatorname{T}(a^{*}a)$ on $A$, meaning that
$\operatorname{T}(a^{*}a)$ is always non-negative and is zero only when $a=0$.
Moreover, this quadratic form induces the inner product $\langle
x,y\rangle=\operatorname{T}(x^{*}y)$ on $A$.

In particular, when $A$ is a division algebra over $\mathbb{Q}$, such an
involution exists on $A\otimes_{\mathbb{Q}}\mathbb{R}$.

###### Proof.

See e.g. [Gar21, Corollary 35] ∎

We will denote $A\otimes_{\mathbb{Q}}\mathbb{R}$ by $A_{\mathbb{R}}$.
Involutions with the properties as described in Lemma 2.6 will henceforth be
called “positive involutions”. An element $a\in A_{\mathbb{R}}$ such that
$a^{*}=a$ and $x\mapsto\operatorname{T}(x^{*}ax)$ is a positive definite real
quadratic form on $A_{\mathbb{R}}$ is called symmetric and positive definite.
For instance, for any unit $a$ the element $a^{*}a$ is symmetric positive
definite.

In practice, we will be considering $t\geq 2$ copies of orders $\mathcal{O}$
in division algebras $A$ with center a number field $K$ and our lattices will
be $\mathcal{O}^{t}\subseteq A^{t}\hookrightarrow(A_{\mathbb{R}})^{t}$. We
will endow the space $A_{\mathbb{R}}^{t}$ with the norm induced by the
following quadratic form:

$\displaystyle A_{\mathbb{R}}^{t}$ $\displaystyle\rightarrow\mathbb{R}$ (2.1)
$\displaystyle(x_{1},x_{2},\dots,x_{t})$
$\displaystyle\mapsto\sum_{i=1}^{t}\operatorname{T}(x_{i}^{*}ax_{i}),$ (2.2)

where $(-)^{*}$ is a positive involution as defined above and $a\in
A_{\mathbb{R}}$ is a symmetric positive definite element to be fixed later.
This makes $A_{\mathbb{R}}^{t}$ into an Euclidean space of real dimension
$mn^{2}t$ and $\mathcal{O}^{t}$ embeds as a lattice into that space.

###  2.3. Norm-trace inequality

Recall that for a finite dimensional algebra $A$ over any field $k$ we have
norm and trace functions $N_{A/k},T_{A/k}:A\rightarrow k$ given by the
determinant and trace of the left multiplication maps respectively. It will be
useful to establish some of their properties; for instance we later use the
norm-trace inequality to give lower bounds on the Euclidean norm of certain
lattice points via Lemma 2.12.

######  Lemma 2.7.

Consider a finite dimensional semisimple $\mathbb{R}$-algebra $A_{\mathbb{R}}$
together with a positive involution $(\ )^{*}$. Let $a\in A_{\mathbb{R}}$ be a
symmetric positive definite element and let
$d=\dim_{\mathbb{R}}A_{\mathbb{R}}$. Then $\operatorname{N}(a)>0$,
$\operatorname{T}(a)>0$ and

$\displaystyle\frac{1}{d}\operatorname{T}(a)\geq\operatorname{N}(a)^{\frac{1}{d}}.$
(2.3)

###### Proof.

See [Gar21, Lemma 40]. ∎

######  Corollary 2.8.

In the same setting as above, we have for any $x\in A_{\mathbb{R}}$ and for
$a\in A_{\mathbb{R}}$ symmetric positive definite that

$\frac{1}{d}\operatorname{T}(x^{*}ax)\geq\operatorname{N}(x)^{\frac{2}{d}}\operatorname{N}(a)^{\frac{1}{d}}.$
(2.4)

###### Proof.

Note that $x^{*}ax$ is symmetric and positive definite when $x$ is a unit in
$A_{\mathbb{R}}$. If $x$ is not a unit, then the right-hand side is trivial. ∎

We remark that the inequalities above are sharp, equality being achieved by
appropriate scalar matrices. For central simple $K$-algebras $A$, one can
furthermore define the “reduced norm” and the “reduced trace” which we denote
by $\operatorname{nr}_{A/K},\operatorname{tr}_{A/K}:A\rightarrow K$.
Definitions and properties can be found in [Rei03, Section 9].

The following definition and ensuing lemma can also be found in [Rei03,
9.13-14].

######  Definition 2.9.

Suppose $A$ is a central simple $L$-algebra and $K\subseteq L$ is a subfield
such that $[L:K]<\infty$. Then for each $a\in A$, we define the “relative
reduced trace” $\operatorname{tr}_{A/K}:A\rightarrow K$ and “relative reduced
norm” $\operatorname{nr}_{A/K}:A\rightarrow K$ as

$\displaystyle\operatorname{tr}_{A/K}=\operatorname{T}_{L/K}\circ\operatorname{tr}_{A/L},$
(2.5)
$\displaystyle\operatorname{nr}_{A/K}=\operatorname{N}_{L/K}\circ\operatorname{nr}_{A/L}.$
(2.6)

######  Lemma 2.10.

The following holds for a central simple $L$-algebra $A$ and a subfield
$K\subseteq L$ with $[L:K]<\infty$ for any $a\in A$:

$\displaystyle\operatorname{T}_{A/K}(a)=\sqrt{[A:L]}\operatorname{tr}_{A/K},$
(2.7)
$\displaystyle\operatorname{N}_{A/K}(a)=\operatorname{nr}_{A/K}(a)^{\sqrt{[A:L]}}.$
(2.8)

We may now establish the following lemmas:

######  Lemma 2.11.

Let $A$ be a division algebra over $\mathbb{Q}$ whose center is $K$ and
$[A:K]=n^{2}$. Let $\mathcal{O}\subseteq A$ be a maximal order in the division
algebra. Let $\mathfrak{p}$ be a prime ideal of $\mathcal{O}_{K}$ for which
$A$ splits and let $\mathbb{F}_{q}=\mathcal{O}_{K}/\mathfrak{p}$ denote the
residue field. Then the following diagram commutes:

${\mathcal{O}}$${\mathcal{O}_{K}}$${\mathcal{O}/\mathfrak{p}\mathcal{O}\cong
M_{n}(\mathbb{F}_{q})}$${\mathbb{F}_{q},}$$\scriptstyle{\phi_{p}}$$\scriptstyle{\operatorname{nr}_{A/K}}$$\scriptstyle{\pi_{\mathfrak{p}}}$$\scriptstyle{\det}$
(2.9)

where the vertical maps designate reduction modulo $\mathfrak{p}$.

###### Proof.

First note that $\operatorname{nr}_{A/K}(a)\in\mathcal{O}_{K}$ for each
$a\in\mathcal{O}$ since $\operatorname{nr}_{A/K}(a)\in K$ and
$\mathcal{O}_{K}$ is integrally closed (see also [Rei03, (10.1)]). The reduced
norm $\operatorname{nr}_{A/K}(a)$ may be computed as the determinant of the
corresponding matrix in $M_{n}(E)$, where $E$ is a splitting field for $A$
(and is easily seen to be independent of that choice). We may in particular
choose $E$ to be the $\mathfrak{p}$-adic completion $\hat{K}_{\mathfrak{p}}$
since by our assumption we have $A\otimes_{K}\hat{K}_{\mathfrak{p}}\cong
M_{n}(\hat{K}_{\mathfrak{p}})$. Therefore, in this case commutativity of the
following diagram follows immediately:

${M_{n}(\mathcal{O}_{\hat{K}_{\mathfrak{p}}})}$${\mathcal{O}_{\hat{K}_{\mathfrak{p}}}}$${\mathcal{O}_{\mathfrak{p}}/\mathfrak{p}\mathcal{O}_{\mathfrak{p}}\cong
M_{n}(\mathbb{F}_{q})}$${\mathbb{F}_{q},}$$\scriptstyle{\tilde{\phi_{p}}}$$\scriptstyle{\det}$$\scriptstyle{\pi_{\mathfrak{p}}}$$\scriptstyle{\det}$
(2.10)

where $\mathcal{O}_{p}$ is the image of $\mathcal{O}$ in
$A\otimes_{K}K_{\mathfrak{p}}$. Now it is not necessarily the case that
$\mathcal{O}_{\mathfrak{p}}=M_{n}(\mathcal{O}_{\hat{K}_{\mathfrak{p}}})$.
However, in the complete local case
$M_{n}(\mathcal{O}_{\hat{K}_{\mathfrak{p}}})$ is a maximal
$\mathcal{O}_{\hat{K}_{\mathfrak{p}}}$-order and moreover all the maximal
orders are conjugate (see [Rei03, Theorem 17.3]). Since the reduced norm is
invariant under conjugation we may assume $\operatorname{nr}_{A/K}$ on
$\mathcal{O}$ factors through $M_{n}(\mathcal{O}_{\hat{K}_{\mathfrak{p}}})$.
Similarly, we can assume $\phi_{p}$ factors through
$M_{n}(\mathcal{O}_{\hat{K}_{\mathfrak{p}}})$. The commutativity of diagram
(2.9) thus follows from that of (2.10).

∎

######  Lemma 2.12.

Let $A$ be a $\mathbb{Q}$-division algebra with center $K$, let $\mathcal{O}$
denote a maximal order and let $\mathfrak{p}$ be a prime of $\mathcal{O}_{K}$
at which $A$ is split, so that we have a reduction map

$\phi_{p}:\mathcal{O}\to\mathcal{O}/\mathfrak{p}\mathcal{O}\cong
M_{n}(\mathbb{F}_{q}),$

with $n={\sqrt{[A:K]}}$. Let $(\ )^{*}:A_{\mathbb{R}}\rightarrow
A_{\mathbb{R}}$ be a positive involution. If $x\in\mathcal{O}\setminus\\{0\\}$
(which we may identify with its image in $A_{\mathbb{R}}$) is such that
$\phi_{p}(x)$ is a non-invertible matrix, then

$\|x\|\geq\left(\sqrt{[A:\mathbb{Q}]}\operatorname{N}(a)^{\frac{1}{2[A:\mathbb{Q}]}}\right)q^{\frac{1}{\sqrt{[A:K]}[K:\mathbb{Q}]}}.$
(2.11)

where $a\in A_{\mathbb{R}}$ is symmetric positive definite and
$\|x\|^{2}:=\operatorname{T}(x^{*}ax)$ on $A_{\mathbb{R}}$.

###### Proof.

We know from the norm-trace inequality that

$\displaystyle\tfrac{1}{[A:\mathbb{Q}]}\operatorname{T}(x^{*}x)\geq\operatorname{N}(x)^{\frac{2}{{[A:\mathbb{Q}]}}}\operatorname{N}(a)^{\frac{1}{[A:\mathbb{Q}]}}.$
(2.12)

Since $\det\circ\phi_{p}(x)=0$, we get by Lemma 2.11 that
$\mathfrak{p}\mid\operatorname{nr}_{A/K}(x)$ and hence

$\displaystyle\operatorname{N}_{K/\mathbb{Q}}(\mathfrak{p})\mid\operatorname{N}_{K/\mathbb{Q}}\circ\operatorname{nr}_{A/K}(x)$
$\displaystyle\Rightarrow$ $\displaystyle
N_{K/\mathbb{Q}}(\mathfrak{p})\mid\operatorname{nr}_{A/\mathbb{Q}}(x)$
$\displaystyle\Rightarrow$ $\displaystyle
N_{K/\mathbb{Q}}(\mathfrak{p})^{\sqrt{[A:K]}}\mid\operatorname{N}_{A/\mathbb{Q}}(x)$

Since $\operatorname{N}_{A/\mathbb{Q}}(x)^{2}\in\mathbb{Z}_{\geq 0}$ and
$x\neq 0$, this gives us a lower bound on
$\operatorname{N}_{A/\mathbb{Q}}(x)^{2}$. Thus we have that

$\displaystyle\tfrac{1}{[A:\mathbb{Q}]}\operatorname{T}(x^{*}ax)\geq\operatorname{N}_{K/\mathbb{Q}}(\mathfrak{p})^{\frac{2\sqrt{[A:K]}}{{[A:\mathbb{Q}]}}}\operatorname{N}(a)^{\frac{1}{[A:\mathbb{Q}]}}.$
(2.13)

which proves the claim given that
$\operatorname{N}_{K/\mathbb{Q}}(\mathfrak{p})=|\mathcal{O}_{K}/\mathfrak{p}|=q$.
∎

We also record the following result:

######  Lemma 2.13.

Let $A$ be a central simple division $K$-algebra for $K$ a number field and
let $\mathcal{O}$ be a maximal $\mathcal{O}_{K}$-order which we identify with
the corresponding lattice in $A_{\mathbb{R}}=A\otimes_{\mathbb{Q}}\mathbb{R}$.
Then, with respect to any quadratic form $q_{a}(x)=\operatorname{T}(x^{*}ax)$
for a symmetric positive definite element $a\in A_{\mathbb{R}}$, one may
define the shortest vector length $\lambda_{1,q_{a}}$, Hermite parameter
$\gamma_{q_{a}}$ and covering radius $\tau_{q_{a}}$, and they are subject to
the following:

  1. (1)

The shortest vector length satisfies
$\lambda_{1,q_{a}}(\mathcal{O})\geq\sqrt{[A:\mathbb{Q}]}\cdot\operatorname{N}(a)^{1/(2[A:\mathbb{Q}])}$.

  2. (2)

For any two-sided $\mathcal{O}$-ideal I (by which we mean a full
$\mathcal{O}_{K}$-lattice in $\mathcal{O}$), the Hermite parameter satisfies

$\gamma_{q_{a}}(I)\geq\frac{[A:\mathbb{Q}]}{d(\mathcal{O}/\mathbb{Z})^{1/[A:\mathbb{Q}]}}$

  3. (3)

The covering radius satisfies

$\tau_{q_{a}}(\mathcal{O})\leq
d(\mathcal{O}/\mathbb{Z})^{1/[A:\mathbb{Q}]}\cdot\left(\frac{\sqrt{[A:\mathbb{Q}]}}{2\pi}+\frac{3}{\pi}\right)\cdot\operatorname{N}(a)^{-1/(2[A:\mathbb{Q}])},$

where $d(\mathcal{O}/\mathbb{Z})$ denotes the discriminant of $\mathcal{O}$
computed with respect to a $\mathbb{Z}$-basis.

###### Proof.

The first part follows trivially from the norm-trace inequality. For the
second statement, we know $I$ also yields a lattice in $A_{\mathbb{R}}$ and,
following [Bay06, Section 4], we set
$\beta_{I,q_{a}}(x):=\frac{q_{a}(x)}{\det_{q_{a}}(I)^{1/[A:\mathbb{Q}]}}$,
where by definition $\det_{q_{a}}(I)$ is the determinant of a matrix of
$q_{a}$ in a $\mathbb{Z}$-basis of the ideal lattice $I$. Note that by
definition $\gamma_{q_{a}}(I)=\min_{x\in I}\beta_{I,q_{a}}(x)$. By the norm-
trace inequality, we have that
$\operatorname{N}_{A/\mathbb{Q}}(x)^{2}\leq(q_{a}(x)/[A:\mathbb{Q}])^{[A:\mathbb{Q}]}\cdot\operatorname{N}(a)^{-1}$.
Therefore, since the discriminant of $\mathcal{O}$ satisfies
$d(\mathcal{O}/\mathbb{Z})=\det_{q_{1}}(\mathcal{O})=\operatorname{N}(a)^{-1}\cdot\det_{q_{a}}(\mathcal{O})$,
we obtain the inequality:

$\operatorname{N}_{A/\mathbb{Q}}(x)^{2}\leq\left(\frac{\beta_{\mathcal{O},q_{a}}(x)}{[A:\mathbb{Q}]}\right)^{[A:\mathbb{Q}]}\cdot
d(\mathcal{O}/\mathbb{Z})^{2}.$

Moreover, letting $\mathcal{N}(I)$ denote the norm of an $\mathcal{O}$-ideal
as in [Rei03, Section 24] and $\mathcal{N}_{\mathbb{Q}}(I)$ the number
representing the fractional $\mathbb{Z}$-ideal generated by
$\operatorname{N}_{A/\mathbb{Q}}(x)$ for $x\in I$ (see [Rei03, Theorem 24.9]),
we have that
$\det_{q_{a}}(I)=\det_{q_{a}}(\mathcal{O})\cdot\mathcal{N}_{\mathbb{Q}}(I)^{2}$.
Putting these together we deduce:

$\beta_{I,q_{a}}(x)=\beta_{\mathcal{O},q_{a}}(x)\cdot\mathcal{N}_{\mathbb{Q}}(I)^{-2/[A:\mathbb{Q}]}\geq\frac{[A:\mathbb{Q}]}{d(\mathcal{O}/\mathbb{Z})^{1/[A:\mathbb{Q}]}}\cdot\left(\frac{\operatorname{N}_{A/\mathbb{Q}}(x)}{\mathcal{N}_{\mathbb{Q}}(I)}\right)^{2/[A:\mathbb{Q}]}$
(2.14)

Taking the minimum over $x\in I$ of equation (2.14) yields the result, since
for any $x\in I$ we have that
$\operatorname{N}_{A/\mathbb{Q}}(x)/\mathcal{N}_{\mathbb{Q}}(I)\geq 1$.

For the third statement, we use a transference theorem: indeed, denoting by
$\mathcal{O}^{\sharp}$ the dual lattice, we have that

$\lambda_{1,q_{a}}(\mathcal{O}^{\sharp})\cdot\tau_{q_{a}}(\mathcal{O})\leq\frac{[A:\mathbb{Q}]}{2\pi}+\frac{3\sqrt{[A:\mathbb{Q}]}}{\pi}$

by a refinement [MSD19, (1.9)] of a result of Banaszczyk [Ban93]. But under
the choice of inner product $\langle x,y\rangle=\operatorname{T}(x^{*}ay)$
corresponding to $q_{a}$, the dual lattice $\mathcal{O}^{\sharp}$ is just
$a^{-1}$ times the image under the involution $(-)^{*}$ of the inverse
different $\mathfrak{D}(\mathcal{O}/\mathbb{Z})^{-1}=\\{x\in
A:\operatorname{tr}_{A/\mathbb{Q}}(x\cdot\mathcal{O})\subset\mathbb{Z}\\}$ and
therefore has the same parameters. Given that
$a^{-1}\mathfrak{D}(\mathcal{O}/\mathbb{Z})^{-1}$ is a two sided (non-
integral) $\mathcal{O}$-ideal, by the second statement we deduce

$\lambda_{1,q_{a}}(\mathcal{O}^{\sharp})=\lambda_{1,q_{a}}(a^{-1}\mathfrak{D}(\mathcal{O}/\mathbb{Z})^{-1})\geq\sqrt{[A:\mathbb{Q}]}\left(\frac{\det_{q_{a}}(a^{-1}\mathfrak{D}(\mathcal{O}/\mathbb{Z})^{-1})}{d(\mathcal{O}/\mathbb{Z})}\right)^{1/(2[A:\mathbb{Q}])}.$

Since
$\det_{q_{a}}(a^{-1}\mathfrak{D}(\mathcal{O}/\mathbb{Z})^{-1})=\det_{q_{a}}(\mathcal{O}^{\sharp})=\det_{q_{a}}(\mathcal{O})^{-1}$,
we obtain that

$\lambda_{1,q_{a}}(\mathcal{O}^{\sharp})\geq\sqrt{[A:\mathbb{Q}]}\cdot
d(\mathcal{O}/\mathbb{Z})^{-1/[A:\mathbb{Q}]}\cdot\operatorname{N}(a)^{1/(2[A:\mathbb{Q}])}.$

The result follows by the transference theorem. ∎

We now have the tools to tackle in the next section the first main result of
this paper.

##  3\. A general averaging result for lifts

Again, let $A$ denote a central simple $K$-algebra for $K$ a number field and
assume $A$ is a division ring. We set $n^{2}=[A:K]$ and $m=[K:\mathbb{Q}]$.
Let $\mathcal{O}$ denote an order in $A$. The purpose of this section is to
prove a discrete version of a Siegel mean value theorem (see [Sie45, Ven12,
Gar21]) for $\mathcal{O}$-lattices obtained via lifts of codes in
characteristic $p$ for increasingly large primes $p$. In order to facilitate
discussion and comparison with previous results, we will state a more abstract
and flexible version of the main averaging result and later explain the most
convenient choices of parameters.

Assume we are given for a fixed integer $t\geq 2$ a family of surjective
homomorphisms

$\phi_{p}:\mathcal{O}^{t}\to\mathcal{R}_{p}^{t},$

indexed by primes $p$, where $\mathcal{R}_{p}$ is a finite
$\mathbb{F}_{p}$-algebra of fixed $\mathbb{F}_{p}$-rank $d_{\mathcal{R}}$ and
where the sizes of $p,\mathcal{R}_{p}$ are unbounded in the family. We also
fix an embedding $i:A\hookrightarrow\mathbb{R}^{n^{2}m}$ which identifies
$\mathcal{O}^{t}$ with a lattice in $\mathbb{R}^{n^{2}mt}$. Assume we are
given subsets $U_{p}\subset\mathcal{R}_{p}^{t}$ and sets of
$\mathcal{R}_{p}$\- submodules $\mathcal{C}_{k}$ of $\mathcal{R}_{p}^{t}$ of
fixed $\mathbb{F}_{p}$-dimension $d(k)<t\cdot d_{\mathcal{R}}$ (which we refer
to as generalized $k$-dimensional codes) such that the following two
conditions hold:

  1. (1)

($U$-balancedness): For any fixed $p$ in the family and $x\in U_{p}$, the
number of $k$-dimensional codes in $\mathcal{C}_{k}$ containing $x$ is
constant (we denote this constant $L_{U_{p}}$).

  2. (2)

(non-degeneracy): There exists a constant $c_{U}>0$ and
$s>\frac{d_{\mathcal{R}}\cdot t-\max_{k}d(k)}{mn^{2}t}$ such that

$\|i(x)\|\geq c_{U}\cdot p^{s}\text{ for any nonzero
}x\in\phi_{p}^{-1}(\mathcal{R}_{p}^{t}\setminus U_{p}).$

We also require the mild condition that
$\lim_{p\to\infty}\frac{|U_{p}|}{|R_{p}|^{t}}=1$.

We can then prove an averaging result for lifts in this general setup. Denote
within this setup the set of scaled lattices

$\mathbb{L}_{p}=\\{\beta\phi_{p}^{-1}(C):C\in\mathcal{C}_{k}\\},$

where $\beta$ is chosen such that all the lattices in $\mathbb{L}_{p}$ have
volume $V:=\mathrm{Vol}(\mathcal{O}^{t})$, ergo
$\beta=(\frac{p^{d(k)}}{|R_{p}|^{t}})^{1/n^{2}mt}$. Finally, we define
following [Cam18, Def 2]:

######  Definition 3.1.

A function $f:\mathbb{R}^{d}\to\mathbb{R}$ is called semi-admissible if $f$ is
Riemann-integrable and there exist positive constants $b,\delta>0$ such that

$|f(\mathbf{x})|\leq\frac{b}{(1+\|\mathbf{x}\|)^{d+\delta}}\text{ for all
}\mathbf{x}\in\mathbb{R}^{d}.$

We then have the following:

######  Theorem 3.2.

Let $\mathcal{C}_{k}$ be the set of codes of fixed $\mathbb{F}_{p}$-dimension
$d(k)$ and let $f:\mathbb{R}^{n^{2}mt}\to\mathbb{R}$ be a semi-admissible
function for $t\geq 2$. Under the setup and notations above, assume the
$U$-balancedness and non-degeneracy conditions are satisfied. Then, provided
$d_{\mathcal{R}}\cdot t>d(k)>t\cdot(d_{\mathcal{R}}-s(n^{2}m))$, we have:

$\lim_{p\to\infty}\mathbb{E}_{\mathbb{L}_{p}}\left(\sum_{x\in(\beta\phi_{p}^{-1}(C))^{\prime}}f(i(x))\right)\leq(\zeta(n^{2}mt)\cdot
V)^{-1}\cdot\int_{\mathbb{R}^{n^{2}mt}}f(x)dx,$

where $p$ ranges over the primes in the family and where for
$\Lambda\in\mathbb{L}_{p}$ we denote by $\Lambda^{\prime}$ the primitive
vectors in $\Lambda$ (=shortest vectors of the lattice on the real line they
span).

We note that we set up the non-degeneracy condition so that in the very least
the largest dimension $d(k)$ possible for the appropriate notion of
$k$-dimensional code which is strictly contained in $\mathcal{R}_{p}^{t}$
satisfies the condition $d_{\mathcal{R}}\cdot
t>d(k)>t\cdot(d_{\mathcal{R}}-s(n^{2}m))$ and so the result is not vacuous.

###### Proof.

We split the expected value of the lattice sum into two parts: First, we show
that the expected value of the term

$\sum_{x\in(\beta\phi_{p}^{-1}(C))^{\prime},\phi_{p}(x/\beta)\in(\mathcal{R}_{p}^{t}\setminus
U_{p})}f(i(x))=\sum_{x\in(\phi_{p}^{-1}(C))^{\prime},\phi_{p}(x)\in(\mathcal{R}_{p}^{t}\setminus
U_{p})}f(\beta i(x))$

tends to zero in absolute value as $p\to\infty$. By the non-degeneracy
condition, we can bound

$\|\beta i(x)\|\geq\beta\cdot c_{u}\cdot p^{s}=c_{u}\cdot
p^{(d(k)-d_{\mathcal{R}}\cdot t)/(mn^{2}t)}p^{s}$ (3.1)

which under our assumption on $d(k)$ becomes arbitrarily large as
$p\to\infty$. Since $f$ decays rapidly at infinity we get for each individual
lattice in $\mathbb{L}_{p}$ that the sum converges to $0$ as $p\to\infty$ by
dominated convergence, and therefore idem for the average.

The remaining terms can be bounded on average via $U$-balancedness. Indeed,
let $g:R_{p}^{t}\to\mathbb{R}^{+}$ denote any function. We have that

$\displaystyle\mathbb{E}_{\mathcal{C}}[\sum_{c\in\mathcal{C}\cap U_{p}}g(c)]$
$\displaystyle=\sum_{x\in
U_{p}}\mathbb{E}_{\mathcal{C}}[g(x)\mathbf{1}_{C}(x)]$
$\displaystyle=\sum_{x\in U_{p}}g(x)\frac{L_{U_{p}}}{|\mathcal{C}|}$
$\displaystyle\leq\sum_{x\in U_{p}}g(x)\frac{p^{d(k)}}{|U_{p}|},$

where we use $U$-balancedness as well as a counting argument for the
inequality and where the expected value is taken as average over all codes in
$\mathcal{C}$. We deduce the inequality

$\mathbb{E}[\sum_{x\in(\phi_{p}^{-1}(C))^{\prime},\phi_{p}(x)\in U_{p}}f(\beta
i(x))]\leq\frac{p^{d(k)}}{|U_{p}|}\sum_{x\in(\mathcal{O}^{t})^{\prime}}f(\beta
i(x)).$

By the Möbius inversion formula (and exchanging summation and limits by
dominated convergence when $f$ does not have bounded support), the latter
equals

$\sum_{r=1}^{\infty}\frac{\mu(r)}{r^{n^{2}mt}}\sum_{x\in\mathcal{O}^{t}\setminus\\{0\\}}\frac{p^{d(k)}}{|U_{p}|}r^{n^{2}mt}f(r\beta
i(x)).$

The result now follows: first, note that we have for fixed $r\in\mathbb{N}$ by
approximation of the Riemann integral of $f$ that

$\lim_{p\to\infty}\sum_{x\in\mathcal{O}^{t}\setminus\\{0\\}}(r\beta)^{n^{2}mt}f(r\beta
i(x))=V^{-1}\int_{\mathbb{R}^{n^{2}mt}}f(x)dx$

since $\beta\to 0^{+}$ as $p$ becomes large. Moreover, by the second part of
the non-degeneracy assumption the ratio $\frac{|U_{p}|}{|R_{p}|^{t}}\to 1$, so
that $\frac{p^{d(k)}}{|U_{p}|}$ approaches $\beta^{n^{2}mt}$ as $p\to\infty$.
Finally, switching the limit in $p$ and summation in $r$ is allowed by
dominated convergence, as $f$ decays rapidly. ∎

We now turn to examples of such a setup.

######  Example 3.3.

In the case where $n=1$ and $\mathcal{O}$ is just the ring of integers
$\mathcal{O}_{K}$ of a number field $K$, we can for example take $\phi_{p}$ to
be the reduction map modulo a prime $\mathfrak{p}|p$ of $\mathcal{O}_{K}$ for
(the infinitely many) primes $p$ that split completely in $\mathcal{O}_{K}$.
In this case, we get $\mathcal{R}_{p}=\mathbb{F}_{p}$ and take $U_{p}$ to be
the complement in $\mathcal{R}^{t}$ of
$(\mathbb{F}_{p}\setminus\mathbb{F}_{p}^{\times})^{t}$. With the usual
definition of $k$-dimensional codes as free rank $k$
$\mathbb{F}_{p}$-submodules of $\mathbb{F}_{p}^{t}$, the balancedness
condition is satisfied (see e.g., [Loe97, Lemma 1]), and moreover the non-
degeneracy result is straightforward in this case: nonzero elements
$x\in\mathfrak{p}\mathcal{O}_{K}$ have algebraic norm

$N_{K/\mathbb{Q}}(x)\in p\mathbb{Z}\setminus\\{0\\},$

but the norm is just the product of the $n$ embedded coordinates of $i(x)$, so
by the geometric/arithmetic mean inequality we obtain

$\|i(x)\|\gg p^{1/n}$

and non-degeneracy is satisfied. The condition on $k$ in Theorem 3.2 simply
becomes $k>0$ and this recovers the construction of [Cam18] in the number
field case.

######  Example 3.4.

Let now $n>1$ so that we are in the non-commutative situation. The most
straightforward generalization to division algebras $A$ with center $K$ of the
number field results is the following: consider primes $\mathfrak{p}|p$ of
$\mathcal{O}_{K}$ that split $A$. Let
$\mathbb{F}_{q}\cong\mathcal{O}_{K}/\mathfrak{p}$ denote the residue field. We
then have an infinite family of ring isomorphisms

$\phi_{p}:\mathcal{O}/\mathfrak{p}\mathcal{O}\to M_{n}(\mathbb{F}_{q})$

for a maximal order $\mathcal{O}$ in $A$. We take $t$ copies of these to build
our reduction map. In order to make sure the multiplicative structure is
preserved as well, it makes sense to set
$\mathcal{R}_{p}:=M_{n}(\mathbb{F}_{q})$ and to consider codes which are free
$\mathcal{R}_{p}$-submodules of $\mathcal{R}_{p}^{t}$ of rank $k$. It also
seems natural to define $U_{p}$ to be the complement in $\mathcal{R}_{p}^{t}$
of

$(\mathcal{R}_{p}^{t}\setminus
U_{p}):=((M_{n}(\mathbb{F}_{q})\setminus\mathrm{GL}_{n}(\mathbb{F}_{q}))^{t}.$

It then follows that the $U$-balancedness condition is again satisfied (see
the proof of [Cam18, Lemma 2]). We get a non-degeneracy result from Lemma
2.12: indeed we obtain for a nonzero vector $a\in\mathcal{O}^{t}$ that maps to
$\mathcal{R}_{p}^{t}\setminus U_{p}$ the lower bound

$\|i(a)\|\gg q^{\frac{1}{nm}}$ (3.2)

Moreover, as
$|\mathrm{GL}_{n}(\mathbb{F}_{q})|=\prod_{i=0}^{n-1}(q^{n}-q^{i})$ we also
have that $\frac{|U_{p}|}{|\mathcal{R}_{p}|^{t}}\to 1$ as $p\to\infty$. Since
the largest possible $\mathbb{F}_{q}$-dimension of a code is $n^{2}(t-1)$,
tracing through the definitions we have non-degeneracy exactly when $t>n$, in
which case via Theorem 3.2 we obtain the averaging result by pulling back
codes which are free $M_{n}(\mathbb{F}_{q})$-modules of rank $k$ for
$t>k>t-t/n$. In particular, when $n=2$ we recover in the special case of the
quaternion algebra $A=\left(\frac{-1,-1}{\mathbb{Q}}\right)$ the results of
[Cam18, Theorem 3] for the Lipschitz integers as well as for the maximal order
of Hurwitz integers. We note that we recover the condition $k>t/2$ appearing
in [Cam18, Theorem 3]. So this does give a generalization to arbitrary
$\mathbb{Q}$-division algebras when $t>n$, however it would be more convenient
to obtain results that work for arbitrary $t\geq 2$.

In order to obtain averaging results that do not require the condition $t>n$,
one would have to obtain a stronger non-degeneracy lower bound on the norm or
relax the condition that the codes be free
$\mathcal{R}_{p}=M_{n}(\mathbb{F}_{q})$-modules. Since the norm-trace
inequality and the lower bound are sharp, we focus on the latter. However,
when relaxing the definition of codes, one has to be careful to preserve the
$U$-balancedness condition and to preserve enough multiplicative structure so
that the units $\mathcal{O}^{\times}$ act on the lattices and we obtain
improved bounds on the packing density. This is achieved by taking as
$k$-dimensional codes $k$ copies of the simple left
$M_{n}(\mathbb{F}_{q})$-module $V=\mathbb{F}_{q}^{n}$ for $n\leq k<tn$. This
carries enough structure through to the lattices in $\mathbb{L}_{p}$ for the
intended applications. Moreover, the $U$-balancedness result is a special case
of the following, which we formulate in representation-theoretic terms:

######  Lemma 3.5.

Let $k$ be a field. Let $R$ be a f.d. semisimple $k$-algebra and $V$ be a
simple (left) $R$-module of finite dimension over $k$. Fix integers $n_{1}\leq
n_{2}\leq n_{3}$. Consider $V^{\oplus n_{3}}$ as an $R$-module and consider
the sets

$\displaystyle U$ $\displaystyle=\\{v\in V^{\oplus n_{3}}\ |\ Rv\simeq
V^{\oplus n_{1}}\\},$ $\displaystyle\mathcal{C}_{n_{2},n_{3}}$
$\displaystyle=\\{C\subseteq V^{\oplus n_{3}}\ |\ C\text{ is an $R$-submodule,
}C\simeq V^{\oplus n_{2}}\\}.$

Assuming that $U$ is non-empty, for each $u\in U$ there is a bijection

$\displaystyle\\{C\in\mathcal{C}_{n_{2},n_{3}}\ |\ u\in
C\\}\leftrightarrow\mathcal{C}_{n_{2}-n_{1},n_{3}-n_{1}}$

###### Proof.

Observe that for any $u\in U$

$\displaystyle u\in C\Leftrightarrow$ $\displaystyle\ Ru\subseteq C\subseteq
V^{\oplus n_{3}}$ $\displaystyle\Leftrightarrow$ $\displaystyle\
\frac{C}{Ru}\subseteq\frac{V^{\oplus n_{3}}}{Ru}\simeq
V^{\oplus(n_{3}-n_{1})}.$

Hence, if we identify $V^{\oplus n_{3}}/Ru$ with $V^{\oplus(n_{3}-n_{1})}$,
the proposed bijection is simply $C\mapsto C/Ru$. ∎

######  Corollary 3.6.

In the previous lemma, if $k$ is a finite field, then the number
$\\#\\{C\in\mathcal{C}_{n_{2},n_{3}}\ |\ u\in C\\}$ is independent of $u$.

Setting $R=M_{n}(\mathbb{F}_{q})$, $V=\mathbb{F}_{q}^{n}$, $n_{3}=nt$,
$n_{2}=k$ and $n_{1}=n$, we deduce our $U$-balancedness condition. We
summarize our results in this case as a consequence of Theorem 3.2 in easily
accessible form:

######  Theorem 3.7.

Let $A$ be a $\mathbb{Q}$-division algebra whose center is a number field $K$.
Let $n=\sqrt{[A:K]}$ and $m=[K:\mathbb{Q}]$. Let $\mathcal{O}$ be an order in
$A$ and for an integer $t\geq 2$ we consider an infinite family of surjective
reduction maps

$\phi_{p}:\mathcal{O}^{t}\to M_{n}(\mathbb{F}_{q})^{t}$

as given in each coordinate by Lemma 2.5. Let
$i:A^{t}\to(A\otimes_{\mathbb{Q}}\mathbb{R})^{t}$ denote the coordinate-wise
embedding and let $f:\mathbb{R}^{n^{2}mt}\to\mathbb{R}$ be a semi-admissible
function. For a fixed $n\leq k<nt$, set

$\displaystyle\mathcal{C}_{k,p}$ $\displaystyle=\\{C\subseteq
M_{n}(\mathbb{F}_{q})^{\oplus t}\ |\ C\text{ is a
$M_{n}(\mathbb{F}_{q})$-submodule isomorphic to }(\mathbb{F}_{q}^{n})^{\oplus
k}\\}$ $\displaystyle\mathbb{L}_{k,p}$
$\displaystyle=\\{\beta_{p}\phi_{p}^{-1}(C)\ |\ C\in\mathcal{C}_{k,p}\\},$

where the constant $\beta_{p}$ normalizing the covolume of lattices in
$\mathbb{L}_{k,p}$ to $V:=\mathrm{Vol}(\mathcal{O}^{t})$ is given by
$\beta_{p}=q^{\frac{nk-n^{2}t}{n^{2}mt}}$. Then if $(n-1)t<k<nt$, we have that

$\lim_{p\to\infty}\mathbb{E}_{\mathbb{L}_{k,p}}\left(\sum_{x\in(\beta_{p}\phi_{p}^{-1}(C))^{\prime}}f(i(x))\right)\leq(\zeta(n^{2}mt)\cdot
V)^{-1}\cdot\int_{\mathbb{R}^{n^{2}mt}}f(x)dx,$

where the limit is taken over primes in the family and
$(\beta_{p}\phi_{p}^{-1}(C))^{\prime}$ denotes the primitive vectors in
$\beta_{p}\phi_{p}^{-1}(C)$.

###### Proof.

This readily follows from our discussions above as a special case of Theorem
3.2: indeed we set

$U_{p}=\\{v\in M_{n}(\mathbb{F}_{q})^{\oplus t}\ |\
\dim_{\mathbb{F}_{q}}\left(M_{n}(\mathbb{F}_{q})v\right)=n^{2}\\}.$

Moreover, we take $R_{p}=M_{n}(\mathbb{F}_{q})$ and the U-balancedness
condition is satisfied by Corollary 3.6. Finally, the non-degeneracy condition
is again satisfied as in Example 3.4, since if $a\in\mathcal{O}^{\oplus
t}\setminus\\{0\\}$ is such that $\phi_{p}(a)\notin U_{p}$, then $a$ has to
have one coordinate which is non-trivial and is a non-invertible matrix modulo
$p$. Thus we obtain the bound in equation (3.2) and obtain non-degeneracy as
before. Finally, the condition on $d(k)$ in Theorem 3.2 then just becomes
$tn-t<k<tn$. ∎

In particular, we obtain in this way a valid result as soon as $t\geq 2$.

##  4\. Improved bounds

Keeping the notation from the previous section, we now show how to leverage
the extra symmetries under finite groups $G_{0}\subset\mathcal{O}^{\times}$ of
the lattices obtained in $\mathbb{L}_{p}$ in order to obtain sphere packings
of density exceeding the Minkowski–Hlawka bound. We first present a result
based on the approach in [Cam18, Corollary 1] which in turn is inspired by
Vance [Van11] and Rogers’ [Rog47] work.

For a central $K$-division algebra $A$, we recall that $A_{\mathbb{R}}$
denotes the real vector space $A\otimes_{\mathbb{Q}}\mathbb{R}$ of dimension
$n^{2}m$. We also recall that the space $A_{\mathbb{R}}^{t}$ is endowed with a
norm coming from the quadratic form as defined in Equation 2.2 for some
positive definite and symmetric $a\in A_{\mathbb{R}}$. Such a norm will be
chosen and fixed permanently in Lemma 4.3.

Given a lattice $\Lambda\subset A_{\mathbb{R}}^{t}$ which is an
$\mathcal{O}$-module and such a choice of norm we however first define the _k-
th $A$-minimum_ $\min_{k}(\Lambda)$ to be the smallest $r$ such that the
closed ball $\mathbb{B}_{A_{\mathbb{R}}}(r)$ of radius $r$ contains $k$
$A_{\mathbb{R}}$-linearly independent lattice vectors (under the left
$A_{\mathbb{R}}$-action on $A_{\mathbb{R}}^{t}$).

In particular, $\min_{1}(\Lambda)$ is the shortest vector length
$\lambda_{1}(\Lambda)$ in $\Lambda$. We begin by remarking that a lemma of
Minkowski [Min10] which was extended by Vance [Van11, Theorem 2.2] holds even
more generally:

######  Proposition 4.1.

Let $t\geq 2$ and $\Lambda$ denote an $\mathcal{O}$-lattice in
$A_{\mathbb{R}}^{t}$. Then $\Lambda$ contains a left $A_{\mathbb{R}}$-module
basis $\\{v_{1},\ldots,v_{t}\\}$ such that $\|v_{i}\|=\min_{i}(\Lambda)$.
Moreover, if $\mathrm{Vol}(\Lambda)=1$, there exists an $\mathcal{O}$-lattice
${\Lambda^{\prime}}$ of covolume one in $A_{\mathbb{R}}^{t}$ such that

$\lambda_{1}({\Lambda^{\prime}})=\left(\prod_{i=1}^{t}\operatorname{min}_{i}(\Lambda)\right)^{1/t}.$

###### Proof.

Essentially the same proof goes through as in [Van11, Theorem 2.2] (replacing
$4$ by the appropriate dimension $mn^{2}$).

To proceed, we select

$\displaystyle v_{1}$
$\displaystyle=\operatorname{argmin}_{v\in\Lambda\setminus\\{0\\}}\ \|i(v)\|$
$\displaystyle v_{2}$
$\displaystyle=\operatorname{argmin}_{v\in\Lambda\setminus Av_{1}}\|i(v)\|$
$\displaystyle v_{3}$
$\displaystyle=\operatorname{argmin}_{v\in\Lambda\setminus(Av_{1}+Av_{2})}\|i(v)\|$
$\displaystyle v_{4}$
$\displaystyle=\operatorname{argmin}_{v\in\Lambda\setminus(Av_{1}+Av_{2}+Av_{3})}\|i(v)\|$
$\displaystyle\vdots$

and we can argue inductively that they are linearly independent with respect
to $A_{\mathbb{R}}$-action and satisfy $\|i(v_{i})\|=\min_{i}(\Lambda)$.

We now generate vectors $x_{1},x_{2},\cdots,x_{k}$ using a Gram-Schmidt
process (see Appendix A) on $v_{1},v_{2},\cdots,v_{k}$. Since
$\\{v_{i}\\}_{i=1}^{k}$ is free with respect to left-$A_{\mathbb{R}}$ action,
we get that $x_{1},x_{2},\cdots,x_{k}$ freely generate $A_{\mathbb{R}}^{k}$ as
a left-$A_{\mathbb{R}}$ module.

Now consider the $\mathbb{R}$-linear map given by

$\displaystyle
T:y\mapsto\frac{y_{i}}{\lambda_{i}}x_{1}+\frac{y_{2}}{\lambda_{2}}x_{2}+\cdots\frac{y_{k}}{\lambda_{k}}x_{k},$
$\displaystyle\text{ for }y=y_{1}x_{1}+y_{2}x_{2}+\cdots+y_{k}x_{k}\in
A_{\mathbb{R}}^{k}.$

Define a lattice $\Lambda^{\prime}$ by:

$\displaystyle\Lambda^{\prime}=(\lambda_{1}\lambda_{2}\ldots\lambda_{k})^{{1}/{k}}T(\Lambda).$

We observe that $\det(\Lambda^{\prime})=\det(\Lambda)$. For any
$y^{\prime}\in\Lambda^{\prime}\setminus\\{0\\}$, we can now find
$y=y_{1}x_{1}+\cdots+y_{k}x_{k}\in\Lambda$ such that
$y^{\prime}=(\lambda_{1}\cdots\lambda_{k})^{1/k}T(y)$. Furthermore, there must
be a smallest $i_{0}\geq 1$ such that $y_{i_{0}}\neq 0$ and
$y_{i_{0}+1}=y_{i_{0}+2}=\cdots=y_{k}=0$. Then
$y\in\Lambda\cap(A_{\mathbb{R}}v_{1}+A_{\mathbb{R}}v_{2}+\cdots+A_{\mathbb{R}}v_{i_{0}})$
and
$y\not\in\Lambda\cap(A_{\mathbb{R}}v_{1}+\cdots+A_{\mathbb{R}}v_{i_{0}-1})$.
Therefore $\|i(y)\|\geq\lambda_{i_{0}}$. This implies that

$\displaystyle\|i(y^{\prime})\|^{2}=\left(\lambda_{1}\lambda_{2}\ldots\lambda_{k}\right)^{2/k}\sum_{i=1}^{i_{0}}\left|\frac{i(y_{i})}{\lambda_{i}}\right|^{2}\geq\left(\lambda_{1}\lambda_{2}\ldots\lambda_{k}\right)^{2/k}\frac{1}{\lambda_{i_{0}}^{2}}\sum_{i=1}^{k}\left|{i(y_{1})}\right|^{2}\geq(\lambda_{1}\ldots\lambda_{k})^{2/k},$

using orthogonality as in Appendix A. This lower bound is tight, since we can
set $y_{1}=1_{A_{\mathbb{R}}}$ and $y_{i}=0$ for $i\geq 2$. ∎

######  Remark 4.2.

This version of Minkowski’s lemma given above is effective in the sense that
for an explicit lattice $\Lambda$, the lattice $\Lambda^{\prime}$ can also be
computed algorithmically. The only important step here is to find the
successive minima vectors $v_{i}$, and then $\Lambda^{\prime}$ is easily seen
to be computable.

When $A=\mathbb{Q}$ (so $A_{\mathbb{R}}=\mathbb{R}$), finding the $v_{i}$ can
be achieved by the so-called SMP algorithm, which will have an exponential
running time of $O(2^{2t})$. Details can be found in [MG12]. The division
algebra case requires only slight modifications of the algorithm and should
have a running time of $O(2^{2mn^{2}t})$.

We also record the lemma:

######  Lemma 4.3.

Let $\mathcal{O}$ denote an order in a $K$-division algebra $A$ and let
$G_{0}\subset\mathcal{O}^{*}$ denote a finite group. Then $G_{0}$ acts on
vectors in any $\mathcal{O}$-lattice $\Lambda\in\mathbb{L}_{p}$ obtained as in
the construction of Theorem 3.2. Furthermore, we may choose a symmetric
positive definite element $a\in A_{\mathbb{R}}$ such that for all such
$\Lambda$ the induced norm satisfies

$\|i(x)\|^{2}=\sum_{i=1}^{t}\operatorname{T}(x_{i}^{*}ax_{i})=\|i(g\cdot
x)\|^{2}\text{ }\forall g\in G_{0},x\in\Lambda.$

###### Proof.

The lattices obtained in $\mathbb{L}_{p}$ via our construction are easily seen
to be preserved under the $\mathcal{O}$-action when the morphisms $\phi_{p}$
preserve the multiplicative structure and the codes in $\mathcal{C}$ we are
pulling back are $\phi_{p}(\mathcal{O})$-modules. Therefore the units act as
well.

For the second part, we may set

$a=\sum_{g\in G_{0}}g^{*}g.$

One can easily check that the induced quadratic form then has the required
$G_{0}$-invariance.

∎

From now on, we may and will assume a norm as in Lemma 4.3 has been chosen on
$A_{\mathbb{R}}$. Using the methods from [Rog47, Van11, Cam18] we apply
Theorem 3.2 to a specific function $f:\mathbb{R}^{mn^{2}t}\to\mathbb{R}$ in
order to obtain improved bounds.

######  Theorem 4.4.

Let $A$ be a central simple division algebra over a number field $K$. Let
$\mathcal{O}$ be an $\mathcal{O}_{K}$-order in $A$. Let $n^{2}=[A:K]$,
$m=[K:\mathbb{Q}]$ and let $t\geq 2$ be a positive integer. Let $G_{0}$ be a
fixed finite subgroup of $\mathcal{O}^{\times}$. Then there exists a lattice
$\Lambda$ in dimension $n^{2}mt$ achieving

$\Delta(\Lambda)\geq\frac{|G_{0}|\zeta(mn^{2}t)\cdot t}{2^{mn^{2}t}\cdot
e(1-e^{-t})}.$

Moreover, there exists for any $\varepsilon>0$ an $\mathcal{O}$-lattice
$\Lambda_{\varepsilon}$ in dimension $n^{2}mt$ achieving

$\Delta(\tilde{\Lambda}_{\varepsilon})\geq(1-\varepsilon)\cdot\frac{|G_{0}|\zeta(mn^{2}t)\cdot
t}{2^{mn^{2}t}\cdot e(1-e^{-t})}$

which can be constructed. Indeed, $\tilde{\Lambda}_{\varepsilon}$ is obtained
by applying Proposition 4.1 to a suitable sublattice of $\mathcal{O}^{t}$
obtained as a pre-image via reduction modulo primes $\mathfrak{p}$ of
$\mathcal{O}_{K}$ of large enough norm of a code isomorphic to $k$ copies of
simple left $\mathcal{O}/\mathfrak{p}\mathcal{O}$-modules for $nt-t<k<nt$ as
in Theorem 3.7.

###### Proof.

We define $f$ to be the radial function $f_{r}$ of bounded support given by

$f_{r}(y)=\begin{cases}\frac{1}{mn^{2}}&\text{ if
}0\leq\|y\|<re^{(1-t)/mn^{2}t}\\\
\frac{1}{mn^{2}t}-\log(\frac{\|y\|}{r})&\text{ if
}re^{(1-t)/mn^{2}t}\leq\|y\|\leq re^{1/mn^{2}t}\\\ 0&\text{ else }\end{cases}$

This function is indeed semi-admissible and we have that

$\int_{\mathbb{R}^{mn^{2}t}}f_{r}(y)dy=V_{mn^{2}t}\cdot
r^{mn^{2}t}\cdot\frac{e(1-e^{-t})}{mn^{2}t},$

where $V_{mn^{2}t}$ denotes the volume of the unit ball in
$mn^{2}t$-dimensional Euclidean space. For a small $0<\varepsilon<1$ we may
find $r\geq 0$ so that

$V_{mn^{2}t}\cdot
r^{mn^{2}t}\cdot\frac{e(1-e^{-t})}{mn^{2}t}=(1-\varepsilon)\cdot\frac{|G_{0}||\mathrm{Vol}(\mathcal{O}^{t})|\zeta(mn^{2}t)}{mn^{2}}.$

Taking $\mathbb{L}_{p}$ and $k$ satisfying the assumptions of Theorem 3.2, we
may therefore for $p$ large enough find a lattice $\Lambda=\beta\cdot
i(\Lambda_{0})\in\mathbb{L}_{p}$ of volume $\mathrm{Vol}(\mathcal{O}^{t})$
such that

$\sum_{y\in\Lambda^{\prime}}f_{r}(y)\leq(1-\varepsilon)\frac{|G_{0}|}{mn^{2}}<\frac{|G_{0}|}{mn^{2}}.$

We now use the fact that the units of finite order
$G_{0}<\mathcal{O}^{\times}$ act freely on primitive vectors of $\Lambda$ and
that $\|i(gv)\|=\|i(v)\|$ for $g\in G_{0}$ for our choice of norm (see Lemma
4.3). Indeed, letting $\\{v_{1},\ldots,v_{t}\\}$ be linearly independent
vectors achieving the $A$-minima $\|\beta\cdot i(v_{j})\|=\min_{j}(\Lambda)$
as guaranteed by Proposition 4.1, we then have that

$\sum_{y\in\Lambda^{\prime}}f_{r}(y)\geq\sum_{j=1}^{t}\sum_{g\in
G_{0}}f_{r}(\beta\cdot i(gv_{j}))=|G_{0}|\sum_{j=1}^{t}f_{r}(\beta\cdot
i(v_{j})).$

In other words, $\sum_{j=1}^{t}f_{r}(\beta\cdot i(v_{j}))<1/(mn^{2})$ so that
by definition of $f_{r}$ we must have

$\min_{j}(\Lambda)\geq re^{(1-t)/(mn^{2}t)}\text{ for all }j.$ (4.1)

Moreover, it must then be by definition of $f_{r}$ that

$\sum_{j=1}^{t}\log\left(\frac{\min_{j}(\Lambda)}{r}\right)>0$ (4.2)

and hence

$\left(\prod_{j=1}^{t}\min_{j}(\Lambda)\right)^{1/t}>r.$

From proposition 4.1 we deduce the (constructive) existence of a lattice
$\tilde{\Lambda}$ with volume equal to $\mathrm{Vol}(\Lambda)$ and shortest
vector length $\lambda_{1}(\tilde{\Lambda})>r$. We thus obtain for all such
$\varepsilon$ the existence of a lattice $\tilde{\Lambda}_{\varepsilon}$ of
volume $\mathrm{Vol}(\mathcal{O}^{t})$ and packing density

$\Delta(\tilde{\Lambda}_{\varepsilon})\geq(1-\varepsilon)\cdot\frac{|G_{0}|\zeta(mn^{2}t)\cdot
t}{2^{mn^{2}t}\cdot e(1-e^{-t})}.$

Letting $\varepsilon\to 0$, it thus also follows by Mahler compactness that
the sequence $\tilde{\Lambda}_{\varepsilon}$ has a converging subsequence (in
the quotient topology on
$\mathrm{GL}_{mn^{2}t}(\mathbb{R})/\mathrm{GL}_{mn^{2}t}(\mathbb{Z})$). Since
the packing density is a continuous function with respect to this topology, we
also get the existence of a lattice with density
$\Delta_{t}\geq\frac{|G_{0}|\zeta(mn^{2}t)\cdot t}{2^{mn^{2}t}\cdot
e(1-e^{-t})}$. ∎

######  Remarks 4.5.

  1. (1)

First note that the zeta factor quickly approaches one as $n^{2}mt$ increases
and thus can be ignored for the purpose of giving asymptotic bounds for large
dimensions.

  2. (2)

The lower bounds on the density in Theorem 4.4 have the advantage of producing
a factor $t$ in the numerator for lattices constructed from $\mathcal{O}^{t}$.
Via a simpler approach, taking $f$ to be the indicator function of a ball one
finds an $\mathcal{O}$\- lattice $\Lambda$ which outperforms the bound above
(slightly) only when $t=2$. We record this below.

######  Proposition 4.6.

With the notations of Theorem 4.4, there exists a $n^{2}mt$-dimensional sub-
lattice $\Lambda_{\varepsilon}\subset\mathcal{O}^{t}$ with packing density

$\Delta(\Lambda_{\varepsilon})\geq(1-\varepsilon)\cdot\frac{|G_{0}|\zeta(mn^{2}t)}{2^{mn^{2}t}}$

in the set of scaled pre-images of codes $\mathbb{L}_{p}$ for $p$ large
enough. Moreover, there exists a $n^{2}mt$-dimensional lattice $\Lambda$ with
density $\Delta(\Lambda)\geq\frac{|G_{0}|\zeta(mn^{2}t)}{2^{mn^{2}t}}$ for all
$t\geq 2$.

###### Proof.

Take $f$ to be the indicator function of a ball of radius $r$ and let $r$ be
chosen so that
$\mathrm{Vol}(\mathbb{B}(r))=(1-\varepsilon)|G_{0}|\zeta(mn^{2}t)\mathrm{Vol}(\mathcal{O}^{t})$.
Applying Theorem 3.7, there must be for large enough $p$ a lattice
$\Lambda_{\varepsilon}$ in $\mathbb{L}_{p}$ (with the notations of the
theorem) such that

$|\mathbb{B}(r)\cap\Lambda_{\varepsilon}^{\prime}|\leq(1-\varepsilon)|G_{0}|.$
(4.3)

Having arranged for $f$ to be $G_{0}$-invariant, the left hand side of (4.3)
must be a multiple of $|G_{0}|$ and thus is forced to equal $0$. This gives a
lower bound on the shortest vector leading to the desired packing density for
$\Lambda_{\varepsilon}$, while the second statement follows again by Mahler
compactness. ∎

Taking $t=2$ is often the most advantageous in view of optimizing the packing
density in relation to the dimension of the lattice. Nevertheless, having
improved bounds for arbitrary $t\geq 2$ should be useful.

###  4.1. Classification of finite subgroups of $\mathcal{O}^{\times}$ and
bounds.

In order to examine the density of lattice packings that can be achieved via
this method, it is necessary to understand which finite groups
$G_{0}<\mathcal{O}^{\times}$ can occur for $\mathbb{Q}$-division algebras.
This classification was completely carried through by Amitsur [Ami55]. As
outlined in more detail in [Gar21, 2.2–3], we summarize some cases that lead
to new, dense packings.

To that end, we recall that recently dense packings were found in special
cases of our construction by Venkatesh [Ven12] when
$A=K=\mathbb{Q}(\zeta_{m})$ and by Vance [Van11] when
$A=\left(\frac{-1,-1}{\mathbb{Q}}\right)$ by exploiting that the respective
$\mathcal{O}$-lattices are invariant under $\mathbb{Z}/m\mathbb{Z}$ and the
binary tetrahedral group
$\mathfrak{T}^{*}\cong\mathrm{SL}_{2}(\mathbb{F}_{3})$ of order $24$,
respectively. The most spectacular lattice packing densities in the cyclotomic
case then occur when maximizing the ratio
$\frac{|\mathbb{Z}/m\mathbb{Z}|}{[\mathbb{Q}(\zeta_{m}):\mathbb{Q}]}=\frac{m}{\varphi(m)}$
whereas in the Hurwitz lattice case the improved bounds are obtained in
dimensions $4t$. The first result is that in the more general context of
division algebras we may in some sense combine these two improvements:

######  Proposition 4.7.

Assume $m$ is a positive integer such that $2$ has odd order modulo $m$. Then
the algebra
$\mathbb{Q}(\zeta_{m})\otimes_{\mathbb{Q}}\left(\frac{-1,-1}{\mathbb{Q}}\right)$
is a division algebra with center $\mathbb{Q}(\zeta_{m})$ and has a maximal
$\mathbb{Z}[\zeta_{m}]$-order $\mathcal{O}$ with subgroup
$\mathfrak{T}^{*}\times\mathbb{Z}/m\mathbb{Z}\subset\mathcal{O}^{\times}$.

###### Proof.

See [Ami55, Theorems 6a, 7]. ∎

In particular, we obtain for $m$ satisfying the parity condition above the
existence of lattices $\Lambda_{m}$ in dimension $8\varphi(m)$ satisfying:

$\Delta(\Lambda)\geq\frac{24m\zeta(8\varphi(m))}{2^{8\varphi(m)}}>\frac{24m}{2^{8\varphi(m)}}.$

via lifting codes as in Theorem 3.7 and Proposition 4.6. By maximizing the
ratio $m/\varphi(m)$ under the additional parity condition, we arrive at:

######  Proposition 4.8.

Using the construction above and letting

$m_{k}=\prod_{\begin{subarray}{c}p\leq k\text{ prime}\\\
2\nmid\operatorname{ord}_{2}p\end{subarray}}p,$

we obtain lattice packings in dimension $8\varphi(m_{k})$ of density

$\Delta\geq
C(\log\log\varphi(m_{k}))^{7/24}\cdot\frac{24\cdot\varphi(m_{k})}{2^{8\varphi(m_{k})}}$
(4.4)

for some fixed constant $C>0$. Moreover, for any $C<1$ the bound in (4.4) is
valid for $m_{k}$ large enough.

###### Proof.

This is [Gar21, Theorem 30]. ∎

Moreover, there are several other ways to obtain dense packings in new
dimensions via the division algebra approach. We refer the reader to the
discussion in [Gar21] but simply restate [Gar21, Prop 64]:

######  Proposition 4.9.

There exists an infinite sequence of dimensions $\\{d_{n}\\}$ in which a
packing density

$\Delta_{d_{n}}\geq\frac{1}{2}\log\log d_{n}\frac{d_{n}}{2^{d_{n}}}$

is achieved and the lattice achieving this packing density is invariant under
the action of a non-commutative group.

###### Proof.

See [Gar21, Prop 31]. The division algebras in question are
$\left(\frac{-1,-1}{\mathbb{Q}[\zeta_{m}+\zeta_{m}^{-1}]}\right)$ for $m$ a
product of primes maximizing $m/\varphi(m)$ under suitable conditions. The
extra symmetries here come from the action of the dihedral group with $2m$
elements on lattices in dimension $4\varphi(m)$. ∎

One of the main advantages in obtaining such lattices via lifts of codes is
that, at least in theory, such lattices can be explicitly found by searching a
finite set of parameters as opposed to, say, the averaging results in [Gar21].
We conclude by a discussion of such effectivity questions.

##  5\. Notes on effectivity

Our results such as Theorem 3.7 imply that dense lattices in dimension
$mn^{2}t$ can be found among pre-images of codes in characteristic $p$ as
$p\to\infty$. In this last section we show how large it suffices to take $p$
in order to guarantee a lattice of packing density greater than
$(1-\varepsilon)\frac{|G_{0}|}{2^{mn^{2}t}}$ is found, with
$G_{0}<\mathcal{O}^{*}$ designating the units of finite order in
$\mathcal{O}$.

###  5.1. Varying the division ring

We first focus on the case of $t=2$ in Theorem 4.4 when in fact the better
bounds are obtained by taking the simpler indicator function
$f=\mathds{1}_{\mathbb{B}(r)}$ of a ball of appropriate radius as in
Proposition 4.6.

######  Theorem 5.1.

Let $A$ denote central simple division $K$-algebras for number fields $K$ and
denote $[A:K]=n^{2}$ and $[K:\mathbb{Q}]=m$. Let $\mathcal{O}$ denote a
maximal order in such $A$. Fix $0<\varepsilon<1$. Assume the prime
$\mathfrak{p}|p$ in $\mathcal{O}_{K}$ is chosen large enough with respect to
$m,n$ so that the size of the residue field $|\mathcal{O}_{K}/\mathfrak{p}|=q$
satisfies:

  1. (1)

we have as $m,n$ increase the relation:

$(n^{2}m)^{2}\mathrm{Vol}(\mathcal{O})^{2/(mn^{2})}|G_{0}|^{-1/(mn^{2})}=o(q^{1/mn}),$

  2. (2)

the ratio
$\frac{|M_{n}(\mathbb{F}_{q})|^{2}}{|M_{n}(\mathbb{F}_{q})|^{2}-|M_{n}(\mathbb{F}_{q})\setminus\mathrm{GL}_{n}(\mathbb{F}_{q})|^{2}}<(1+\varepsilon/3)$.

Then there exists an effective constant $C_{\varepsilon}>0$ such that in
dimension $2n^{2}m>C_{\varepsilon}$ there exists a lattice
$\Lambda\in\mathbb{L}_{p}$ with packing density

$\Delta(\Lambda)\geq(1-\varepsilon)\frac{|G_{0}|}{2^{2n^{2}m}}.$

Here $\mathbb{L}_{p}$ denotes the set of scaled preimages of generalized codes
of $\mathbb{F}_{q}$-dimension $2n^{2}-n$ via the reduction map
$\phi_{p}:\mathcal{O}^{2}\to(\mathcal{O}/\mathfrak{p}\mathcal{O})^{2}$ as in
Theorem 3.7.

###### Proof.

Tracing through the proof of Theorem 3.7 for $t=2$ and $k=2n-1$ (the only
sensible choice), we find that the term

$\sum_{x\in(\phi_{p}^{-1}(C))^{\prime},\phi_{p}(x)\in(\mathcal{R}_{p}^{2}\setminus
U_{p})}f(\beta i(x))$

is trivial for $f=\mathds{1}_{\mathbb{B}(r)}$ and some $C\in\mathcal{C}_{k,p}$
as soon as

$r<\left(\operatorname{N}(a)^{1/2n^{2}m}\cdot
n\sqrt{m}\right)q^{\frac{1}{2nm}},$ (5.1)

via Lemma 2.12 and (3.1), where $a=\sum_{g\in G_{0}}g^{*}g$. Since
$\operatorname{N}(g^{*}g)=1$ for $g\in G_{0}$, it is easy to give a uniform
lower bound $\operatorname{N}(a)^{1/2n^{2}m}\geq 1$ or even
$\operatorname{N}(a)^{1/2n^{2}m}\geq\sqrt{|G_{0}|}$ by the Minkowski
determinant inequality. In particular, it suffices to ensure the parameter $r$
satisfies

$r<\left(n\sqrt{m}\right)q^{\frac{1}{2nm}}.$ (5.2)

The expected value for the remaining terms for fixed characteristic $p$ can
then be seen by balancedness to be bounded by:

$\mathbb{E}\leq\frac{q^{n(2n-1)}}{q^{2n^{2}}-(q^{n^{2}}-\prod_{i=0}^{n-1}(q^{n}-q^{i}))^{2}}\cdot\sum_{x\in(\mathcal{O}^{2})^{\prime}}\mathds{1}_{\mathbb{B}(r)}(\beta_{p}i(x))$
(5.3)

Now by a classical geometry of numbers result (see [Cam18, Lemma 4] or [Mou16,
Lemma 3 (2)]) we can bound

$\sum_{x\in(\mathcal{O}^{2})^{\prime}}\mathds{1}_{\mathbb{B}(r)}(\beta_{p}i(x))\leq(r+\beta_{p}\tau(\mathcal{O}^{2}))^{2n^{2}m}\cdot\frac{V_{2n^{2}m}}{\beta_{p}^{2n^{2}m}\mathrm{Vol}(\mathcal{O}^{2})},$
(5.4)

where $\tau(\mathcal{O}^{2})$ denotes the packing radius of $\mathcal{O}^{2}$
and $V_{d}$ denotes the volume of the $d$-dimensional unit ball. Writing
$S_{n}(q):=\frac{q^{n(2n-1)}}{q^{2n^{2}}-(q^{n^{2}}-\prod_{i=0}^{n-1}(q^{n}-q^{i}))^{2}}\geq\beta_{p}^{2n^{2}m}$
we arrive at:

$\mathbb{E}\leq\frac{S_{n}(q)}{\beta_{p}^{2n^{2}m}}r^{2n^{2}m}\frac{V_{2n^{2}m}}{\mathrm{Vol}(\mathcal{O}^{2})}\cdot\left(1+\frac{\tau(\mathcal{O}^{2})\beta_{p}}{r}\right)^{2n^{2}m}$
(5.5)

Observe now that
$\frac{S_{n}(q)}{\beta_{p}^{2n^{2}m}}=\frac{|M_{n}(\mathbb{F}_{q})|^{2}}{|M_{n}(\mathbb{F}_{q})|^{2}-|M_{n}(\mathbb{F}_{q})\setminus\mathrm{GL}_{n}(\mathbb{F}_{q})|^{2}}$,
so that we can assume $q$ is large enough so that
$\frac{S_{n}(q)}{\beta_{p}^{2n^{2}m}}<(1+\varepsilon/3)$.

Moreover, for a radius $r$ that yields the density bound, we should have that
the volume of the ball of radius $r$ is around
$|G_{0}|(1-\varepsilon)\mathrm{Vol}(\mathcal{O}^{2})$. By the Stirling
formula, we may estimate as the dimension grows

$r\sim\frac{n\sqrt{m}}{\sqrt{\pi
e}}(|G_{0}|\mathrm{Vol}(\mathcal{O}^{2}))^{1/2n^{2}m},$

which under our assumptions on $q$ satisfies the inequality (5.2) using a
trivial bound like $|G_{0}|=o((n^{2}m)^{nm})$. It now suffices to show that
under the parameters above, we can bound
$\left(1+\frac{\tau(\mathcal{O}^{2})\beta_{p}}{r}\right)^{2n^{2}m}<(1+\varepsilon/3)$
for large enough dimension, since then we get from the inequality (5.5) the
existence of a lattice in $\mathbb{L}_{p}$ with the desired lower bound on the
pac king density. Recall that $\beta_{p}=q^{-1/2nm}$ with our parameters and
we have from Lemma 2.13 that

$\tau(\mathcal{O}^{2})=\sqrt{2}\cdot\tau(\mathcal{O})\leq\mathrm{Vol}(\mathcal{O})^{2/n^{2}m}\cdot(n\sqrt{m}+6)/(\sqrt{2}\pi).$

We thus have

$\frac{\tau(\mathcal{O}^{2})\beta_{p}}{r}\lesssim\mathrm{Vol}(\mathcal{O})^{1/(mn^{2})}|G_{0}|^{-1/(2mn^{2})}q^{-1/(2mn)}$

But under the assumptions of the theorem on $q$, the result now follows since
as $mn^{2}$ goes to infinity the term
$2mn^{2}\cdot\frac{\tau(\mathcal{O}^{2})\beta_{p}}{r}$ becomes arbitrarily
small. Assuming $p$ and $q$ chosen large enough for each $n,m$ as in the
assumptions of the theorem, we may thus view
$\left(1+\frac{\tau(\mathcal{O}^{2})\beta_{p}}{r}\right)^{2n^{2}m}$ as a
function in $n,m$ which approaches $1$ for large enough dimension $n^{2}m$.
This easily yields an effective constant $C_{\varepsilon}$ guaranteeing
$\left(1+\frac{\tau(\mathcal{O}^{2})\beta_{p}}{r}\right)^{2n^{2}m}<(1+\varepsilon/3)$
for $n^{2}m>C_{\varepsilon}$. ∎

We may then for instance apply this result to specific families of maximal
orders in division rings of increasing $\mathbb{Q}$-dimension. One may arrange
for the size of the finite units $G_{0}$ to be known in this family via
Amitsur’s results ([Ami55]). Moreover, the computation of the volume
$\mathrm{Vol}(\mathcal{O})$ reduces to a computation of
$\sqrt{d(\mathcal{O}/\mathbb{Z})}$, since the $\mathbb{Z}$-discriminant
$d(\mathcal{O}/\mathbb{Z})$ can be defined as the ideal generated by
$\\{\det(\operatorname{tr}_{A/\mathbb{Q}}x_{i}x_{j})_{1\leq
i,j\leq[A:\mathbb{Q}]}\\}$ for $x_{i}\in\mathcal{O}$ a $\mathbb{Z}$-basis.
Equivalently it is the norm of the $\mathbb{Q}$-algebra different
$\operatorname{N}_{A/\mathbb{Q}}(\mathfrak{D}(\mathcal{O}/\mathbb{Z}))$. We
may then write ([Rei03, Ex 25.1]):

$d(\mathcal{O}/\mathbb{Z})=\operatorname{N}_{K/\mathbb{Q}}(d(\mathcal{O}/\mathcal{O}_{K}))\cdot
d(\mathcal{O}_{K}/\mathbb{Z})^{n^{2}},$

where $d(\mathcal{O}/\mathcal{O}_{K})$ is just the regular discriminant of the
central simple $K$-algebra $A$ and $d(\mathcal{O}_{K}/\mathbb{Z})$ is the
discriminant of the central number field. In particular, when there is some
control of the ramification behavior of $A/K$ and we have some upper bounds
for the discriminant of $K$, the conditions of Theorem 5.1 become entirely
explicit.

######  Example 5.2.

When $K=\mathbb{Q}(\zeta_{m})$ is a cyclotomic field, one has that

$d(\mathcal{O}_{K}/\mathbb{Z})=\frac{m^{\varphi(m)}}{\prod_{l\in\mathbb{P},l\mid
m}l^{\varphi(m)/(l-1)}}.$ (5.6)

When $n=1$, by considering cyclotomic fields $\mathbb{Q}(\zeta_{m})$ Moustrou
thus finds via a version of Theorem 5.1 in this case effective dense lattices
in dimensions $2\varphi(m)$ for large enough $m$ and shows a suitable $q$ can
be found in time $O(m^{3}\log(m))^{\varphi(m)}$, see [Mou16, Theorem 1, Prop
3.1].

######  Example 5.3.

Similarly, fixing $n=2$, varying $K=\mathbb{Q}(\zeta_{m})$ and considering the
quaternion algebra over $K$

$A=\left(\frac{-1,-1}{\mathbb{Q}(\zeta_{m})}\right)$

when $2$ has odd order modulo $m$, we can use that
$d(\mathcal{O}_{K}/\mathbb{Z})\leq m^{\varphi(m)}$ and that the discriminant
of the Hurwitz integers $d(\mathcal{H}/\mathbb{Z})=2$ to obtain an effective
version of Proposition 4.8 via Theorem 5.1. We record this below.

######  Proposition 5.4.

Let $m_{k}=\prod_{\begin{subarray}{c}p\leq k\text{ prime}\\\
2\nmid\operatorname{ord}_{2}p\end{subarray}}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}}}$

in dimension $n_{k}$.

###### Proof.

We consider the quaternion algebras
$A_{k}=\left(\frac{-1,-1}{\mathbb{Q}(\zeta_{m_{k}})}\right)$ and exhibit a
large enough residue field size $q$ so that the conditions of Theorem 5.1 are
satisfied. From the discriminant relation (5.6) we obtain that the first
condition amounts to

$(m_{k}\varphi(m_{k})^{2})^{2\varphi(m_{k})}=o(q).$

It is convenient to as in [Mou16, Prop 3.1.] search for large primes which
split completely in $\mathbb{Q}(\zeta_{m_{k}})$, and this happens when
$p\equiv 1\mod m_{k}$. Using an effective version of the Čebotarev density
theorem (see e.g., [TZ18]), one sees that an interval of size, say,
$(1/m_{k})(m_{k})^{6\varphi(m_{k})}$ around $m_{k}^{6\varphi(m_{k})}$ must
contain such a prime for large enough $m_{k}$. Such a prime then satisfies
$(m_{k}\varphi(m_{k})^{2})^{2\varphi(m_{k})}=o(p)$ for our choice of $m_{k}$.
Finding a suitable prime $p$ can thus be done in at most around $e^{3/4n\log
n}$ steps. Moreover, for such primes, we have that

$\left|\frac{|M_{2}(\mathbb{F}_{p})|^{2}}{|M_{2}(\mathbb{F}_{p})|^{2}-|M_{2}(\mathbb{F}_{p})\setminus\mathrm{GL}_{2}(\mathbb{F}_{p})|^{2}}-1\right|=o(e^{-n_{k}}),$

which deals with the second condition of Theorem 5.1. The time estimate for
enumerating the lattice family is then of $e^{4.5\cdot
n_{k}\log(n_{k})(1+o(1))}$ binary operations since the number of codes we
consider in Theorem 5.1 here amounts to $O(p^{6})$. The costs of the remaining
computations, such as computing the packing density of lattices, are also
exponential in the dimension, but being of cost $2^{O(n_{k})}$ do not
contribute to the main term of the estimate. We thus obtain an effective
version of the bounds in Proposition 4.8, as claimed. ∎

The density lower bounds above outperform the best known effective lower
bounds on the density from cyclotomic fields up to dimensions around
$1.98\cdot 10^{46}$ because of the improved constant coming from the size of
the binary tetrahedral group ( see also [Gar21, Fig. 1]).

######  Example 5.5.

Consider the case when $k=2$ and $m_{k}=7\cdot 23=161$. A suitable prime $p$
is then for instance

$p=(161\cdot\varphi(161)^{2})^{2\varphi(161)}+223147$

of size about $10^{1072}$ and satisfying $p\equiv 1\mod 161$. Using this prime
in Theorem 5.1 yields a lattice $\Lambda$ in $8\cdot\varphi(161)=1056$
dimensions such that

$\Delta(\Lambda)\geq(1-\varepsilon)\frac{3864}{2^{1056}},$

for $\varepsilon\leq 10^{-1000}$ in about $10^{10^{4}}$ bit-operations. Even
with the best computers, it is currently far out of reach to enumerate a basis
for such a lattice. Nevertheless, this gives a very explicit construction of
such a random lattice that achieves a good packing.

Finally, we note that similarly an effective version of Proposition 4.9 can be
obtained. It seems plausible for such results that as long as only the degree
of the center of the division algebras over $\mathbb{Q}$ is unbounded as in
Proposition 5.4, the family size of $n$-dimensional lattices to be searched
should be $e^{C\cdot n\log(n)(1+o(1))}$ for some constant $C>0$.

###  5.2. Varying the rank $t$

Finally, we remark that one also obtains effective good asymptotic lattices
from our constructions by fixing the division ring $A$ and maximal order
$\mathcal{O}$ and instead varying the rank of the $\mathcal{O}$-lattices as in
Vance’s construction [Van11]. In particular, one obtains an effective version
of Vance’s construction which we record here. The general case is handled in
the same way and is left to the reader.

######  Proposition 5.6.

For any $0<\varepsilon<1$, there exists a lattice in $\mathbb{H}^{t}$ which is
a free rank $t$ module over the ring of Hurwitz integers $\mathcal{H}$, whose
geometric mean of the quaternionic minima satisfy

$\left(\prod_{j=1}^{t}\min_{j}(\Lambda)\right)^{1/t}>r$

where $r$ is defined by
$\mathrm{Vol}(\mathbb{B}(r))=(1-\varepsilon)\frac{24t\mathrm{Vol}(\mathcal{H}^{t})\cdot\zeta(4t)}{e(1-e^{-t})}$,
and which, provided the odd prime $p$ satisfies $t^{2}=o(p)$ and $t$ is large
enough, lies in the set of (rescaled) lifts

$\mathbb{L}_{p}=\\{p^{\frac{1-t}{2t}}\phi_{p}^{-1}(C):C\in\mathcal{C}_{t+1}\\},$

where $\phi_{p}:\mathcal{H}^{t}\to(\mathcal{H}/p\mathcal{H})^{t}\cong
M_{2}(\mathbb{F}_{p})^{t}$ is the reduction map and $\mathcal{C}_{t+1}$ is the
set of left $M_{2}(\mathbb{F}_{p})$-submodules of $M_{2}(\mathbb{F}_{p})^{t}$
isomorphic to $t+1$ copies of the simple left module $\mathbb{F}_{p}^{2}$.

###### Proof.

Consider the proof of Theorem 4.4. Then for any $t\geq 2$ the support of the
radial function $f_{r}(y)$ is contained in the ball of radius
$re^{1/mn^{2}t}=re^{1/4t}$. Choose $r$ such that

$\mathrm{Vol}(\mathbb{B}(r))=(1-\varepsilon)\frac{24t\mathrm{Vol}(\mathcal{H}^{t})\cdot\zeta(4t)}{e(1-e^{-t})}$
(5.7)

Via Stirling’s formula, we get from (5.7) and the discriminant
$d(\mathcal{H})=2$ the asymptotic

$r\sim t^{1/(4t)+1/2}\cdot\frac{2^{5/8}}{\sqrt{\pi e}}.$ (5.8)

First consider any $t<k<2t$. Pulling back codes of $\mathbb{F}_{p}$-dimension
$2k$ as in Theorem 3.7, in order to lift the averaging result we see that the
support of $f$ has to be contained in the ball of radius $2p^{1/4}$, so that
we arrive at the condition

$e^{(1+\ln(t)-2t)/(4t)}\cdot\frac{2^{-3/8}}{\sqrt{\pi}}\sqrt{t}<p^{1/4}.$

Thus for $t\geq 2$ it in particular suffices to take $p\geq t^{2}$. Note that
here any odd prime $p$ is unramified and can be used in the construction.
Inspecting the proof of Theorem 3.2 (and ignoring for simplicity the Möbius
inversion step since the zeta factor quicly approaches $1$ for large $t$), we
have that

$\displaystyle\mathbb{E}$
$\displaystyle\leq\frac{p^{d(k)}}{|U_{p}|\cdot\beta_{p}^{4t}}\cdot\sum_{x\in\mathcal{O}^{t}\setminus\\{0\\}}\beta_{p}^{4t}f_{r}(\beta_{p}i(x))$
$\displaystyle=\frac{p^{4t}}{p^{4t}-(p^{3}+p^{2}-p)^{t}}\cdot\sum_{x\in\mathcal{O}^{t}\setminus\\{0\\}}\beta_{p}^{4t}f_{r}(\beta_{p}i(x))$

as $\beta_{p}=p^{k/2t-1}$, and it therefore remains to bound the difference

$\Delta(p,t)=\left|\beta_{p}^{4t}\cdot\sum_{x\in\mathcal{O}^{t}\setminus\\{0\\}}f_{r}(\beta_{p}i(x))-V^{-1}\int_{\mathbb{R}^{4t}}f_{r}(x)dx\right|$
(5.9)

recalling here that $f_{r}$ is the radial function given by

$f_{r}(y)=\begin{cases}\frac{1}{4}&\text{ if }0\leq\|y\|<re^{(1-t)/4t}\\\
\frac{1}{4t}-\log(\frac{\|y\|}{r})&\text{ if }re^{(1-t)/4t}\leq\|y\|\leq
re^{1/4t}\\\ 0&\text{ else. }\end{cases}$

We note that in particular $f_{r}$ has derivative bounded by
$C_{r}=e^{1/4}/r$. Tiling the support of $f_{r}$ by Voronoï cells of diameter
the packing radius $\tau(\beta\mathcal{O}^{t})$, we can bound the error in
approximating the Riemann integral via the lattice sum on each individual cell
by $\mathrm{Vol}(\mathcal{O}^{t})\beta_{p}^{4t}\cdot C_{r}\cdot
2\tau(\beta\mathcal{O}^{t})$. For large enough $p,t$, we may estimate that the
support of $f_{r}$ is covered by
$\beta^{-4t}e\cdot\frac{Vol(\mathbb{B}(r))}{\mathrm{Vol}(\mathcal{O}^{t})}$
cells (with an error that is $o(\mathrm{Vol}(\mathcal{O}^{t}))$ as
$t\to\infty$), so that we arrive at the total error estimate

$\Delta(p,t)\lesssim
2eC_{r}\cdot\beta_{p}\frac{\mathrm{Vol}(\mathbb{B}(r))}{\mathrm{Vol}(\mathcal{O}^{t})}\cdot\sqrt{t}\cdot\tau(\mathcal{O})$
(5.10)

We therefore obtain for $r$ satisfying (5.7) the bound as $p,t$ become large
of

$\Delta(p,t)=O(t)\cdot p^{\frac{k-2t}{2t}}.$

It now seems most convenient to take $k=t+1$ and we see that in particular the
condition $t^{2}=o(p)$ suffices to guarantee for any given $\varepsilon>0$
that $\Delta(p,t)<\varepsilon$ for large enough rank $t$. We have thus shown
that for any $\varepsilon$ we can find $t$ large enough so that under our
assumptions on $p$ there exists $\Lambda\in\mathbb{L}_{p}$ with
$\sum_{y\in\Lambda^{\prime}}f_{r}(y)\leq(1-\varepsilon)\cdot 6$. The result
now follows as in the proof of Theorem 4.4. ∎

We therefore conclude:

######  Corollary 5.7.

Given any $0<\varepsilon<1$, for large enough $t$ a lattice $\tilde{\Lambda}$
in dimension $4t$ whose packing density satisfies

$\Delta(\tilde{\Lambda})\geq(1-\varepsilon)\cdot\frac{24t\zeta(4t)}{2^{4t}\cdot
e(1-e^{-t})}$

can be constructed with $e^{4t^{2}\log(t)(1+o(1))}$ bit operations.

###### Proof.

Given $\varepsilon$ and large enough $t$, it is easy to find a large enough
prime $p$ so that the construction of Proposition 5.6 applies. The
corresponding family of lattices has $|\mathcal{C}_{t+1}|$ elements in
Proposition 5.6’s notation. They are generated by vectors with coefficients
polynomial in $t$. The cost of computing their density or shortest vector as
well as of computing their successive quaternionic minima (see remark 4.2) is
thus small compared to the cost of enumerating the family and we find by
applying the effective version of 4.1 the desired lattice. ∎

## Acknowledgements

We would like to thank Gauthier Leterrier, Martin Stoller and Maryna Viazovska
for helpful conversations on the topics of this paper. We thank Matthew De
Courcy-Ireland for insightful comments on a previous version of this
manuscript.

Nihar Gargava got funded by the Swiss National Science Foundation (SNSF),
Project funding (Div. I-III), “Optimal configurations in multidimensional
spaces”, 184927.

##  Appendix A Gram-Schmidt process for real semisimple algebras with positive
involutions

Let $A$ be a real semisimple algebra and let $(\ )^{*}:A\rightarrow A$ be a
positive involution.

###  A.1. Orthogonality in $A^{k}$

Let $k\geq 1$. Fix a positive definite symmetric element $a\in A$. Let us
define

$\displaystyle\langle\ ,\ \rangle_{A}:A^{k}\times A^{k}$ $\displaystyle\mapsto
A$ $\displaystyle\langle x,y\rangle_{A}$
$\displaystyle=\sum_{i=1}^{k}x_{i}ay_{i}^{*}.$

This form is $\mathbb{R}$-bilinear but not necessarily $A$-bilinear, since $A$
may not be commutative. We can however define a real positive definite
symmetric bilinear form on $A^{k}$ given by

$\displaystyle\langle x,y\rangle_{\mathbb{R}}=\operatorname{T}\left(\langle
x,y\rangle_{A}\right).$

We assume that $A^{k}$ carries this real inner product.

######  Lemma A.1.

The following properties are satisfied by $\langle\ ,\ \rangle_{A}$.

  1. (1)

For $x,y\in A^{k}$, we have

$\displaystyle\langle x,y\rangle^{*}_{A}=\langle y,x\rangle_{A}.$

  2. (2)

For $x\in A^{k}\setminus\\{0\\}$, $\langle x,x\rangle_{A}$ is a symmetric and
positive definite in $A$, and hence is a unit in $A$.

  3. (3)

For $x,y\in A^{k}$ and $\alpha\in A$, we have

$\displaystyle\langle\alpha x,y\rangle_{A}$ $\displaystyle=\alpha\langle
x,y\rangle_{A},$ $\displaystyle\langle x,\alpha y\rangle_{A}$
$\displaystyle=\langle x,y\rangle_{A}\alpha^{*}.$

  4. (4)

Suppose $x\in A^{k}\setminus\\{0\\}$. Then there exists some $b\in A$ such
that $\langle bx,bx\rangle=1_{A}$.

###### Proof.

All of them are trivial verifications. For the last one, we must find a $b\in
A$ such that $\langle x,x\rangle_{A}^{-1}=b^{*}b$. See [Gar21, Corollary 46].

∎

######  Definition A.2.

We say two vectors in $A^{k}$ are orthogonal if the above given product
between them is $0$. We call a set of vectors
$\\{x_{1},x_{2},\cdots,x_{m}\\}\in A^{k}$ orthonormal if $\langle
x_{i},x_{j}\rangle_{A}=\delta_{ij}1_{A}$.

Note that if $\langle x,y\rangle=0$, then
$\langle\alpha_{1}x,\alpha_{2}y\rangle=0$ for each $\alpha_{1},\alpha_{2}\in
A$ and $x,y\in A^{k}$.

######  Proposition A.3.

Suppose $x_{1},x_{2},\cdots,x_{m}\in A^{k}$ is an orthonormal set of vectors.
Then $m\leq k$ and $x_{1},x_{2},\cdots,x_{m}$ are free under the left action
of $A$. If $m=k$, then the vectors $x_{1},\cdots,x_{k}$ freely generate
$A^{k}$ as a left $A$-module.

###### Proof.

Observe that if $a_{1},a_{2},\cdots,a_{m}\in A$ are such that

$\displaystyle a_{1}x_{1}+a_{2}x_{2}+\dots+a_{m}x_{m}=0,$

then we can just evaluate

$\displaystyle\langle
a_{1}x_{1}+a_{2}x_{2}+\dots+a_{m}x_{m},x_{i}\rangle=a_{i}\langle
x_{i},x_{i}\rangle=a_{i}1_{A}=0.$

Hence, we have that each $a_{i}=0$. Using this, we get that

$\displaystyle A^{m}$ $\displaystyle\rightarrow A^{k}$
$\displaystyle(a_{1},a_{2},\ldots,a_{m})$ $\displaystyle\mapsto
a_{1}x_{1}+\cdots+a_{m}x_{m}.$

is an injective $\mathbb{R}$-linear map. Hence, for dimensional constraints,
$m\leq k$ and $m=k$ will imply that it is an isomorphism. ∎

######  Remark A.4.

If we were to define

$\displaystyle\langle\ ,\ \rangle_{A}:A^{k}\times A^{k}$ $\displaystyle\mapsto
A$ $\displaystyle\langle x,y\rangle$
$\displaystyle=\sum_{i=1}^{k}x_{i}^{*}y_{i},$

we would reach the same proposition above, but for right actions instead of
left.

######  Corollary A.5.

Suppose $x_{1},x_{2},\cdots,x_{k}\in A^{k}$ is an orthonormal set of vectors.
Then for any $v=a_{1}x_{1}+a_{2}x_{2}+\dots+a_{k}x_{k}$ for
$\\{a_{i}\\}_{i=1}^{k}\subseteq A$, we have

$\displaystyle\langle v,v\rangle_{\mathbb{R}}=\operatorname{T}(\langle
v,v\rangle_{A})=\sum_{i=1}^{k}\operatorname{T}(a_{i}^{*}aa_{i}).$

###  A.2. Gram-Schmidt algorithm

The following algorithm is an analogue of Gram-Schmidt.

Suppose $v_{1},v_{2},\cdots,v_{k}\in A^{k}$ are some vectors that freely
generate $A^{k}$ as a left $A$-module. We claim that using these vectors, it
is possible to create a set of orthonormalized basis vectors
$x_{1},x_{2},\cdots,x_{k}$.

First, we do the following. Define for $u,v\in A^{k}$,

$\displaystyle\operatorname{proj}(u,v)=\begin{cases}{\langle
u,v\rangle_{A}}\langle u,u\rangle_{A}^{-1}u&\text{ if }u\neq 0\\\ 0&\text{if
}u=0\end{cases}.$

This has the property that
$\langle\operatorname{proj}(u,v),u\rangle_{A}=\langle u,v\rangle_{A}$.

Generate vectors $x_{1}^{\prime},x_{2}^{\prime},\cdots,x_{k}^{\prime}$ as
follows.

$\displaystyle x_{1}^{\prime}$ $\displaystyle={v_{1}},$ $\displaystyle
x_{2}^{\prime}$
$\displaystyle=v_{2}-\operatorname{proj}(x_{1}^{\prime},v_{2})$ $\displaystyle
x_{3}^{\prime}$
$\displaystyle=v_{3}-\operatorname{proj}(x_{1}^{\prime},v_{3})-\operatorname{proj}(x_{2}^{\prime},v_{3})$
$\displaystyle x_{4}^{\prime}$
$\displaystyle=v_{4}-\operatorname{proj}(x_{1}^{\prime},v_{4})-\operatorname{proj}(x_{2}^{\prime},v_{4})-\operatorname{proj}(x_{3}^{\prime},v_{4})$
$\displaystyle\vdots$

We can prove that $\langle x_{i}^{\prime},x_{j}^{\prime}\rangle=0$ for $i>j$
by first induction via ordering $(i,j)$ as $(2,1),(3,1),\cdots$,
$(k,1),(3,2),(4,2),\cdots$, $(k,2),(4,3),\cdots$. Now choose $b_{i}$ such that
$x_{i}=b_{i}x^{\prime}_{i}$ has $\langle x_{i},x_{i}\rangle=1_{A}$. Hence, we
are done.

######  Definition A.6.

Given a real semisimple algebra $A$ with a positive involution $(\ )^{*}$, we
call the above method of generating $x_{1},x_{2},\cdots,x_{m}$ from vectors
$v_{1},v_{2},\cdots,v_{m}$ the Gram-Schmidt algorithm. If
$\\{v_{i}\\}_{i=1}^{m}$ are free under left $A$ multiplication, then so are
$\\{x_{i}\\}_{i=1}^{m}$.

## References

  * [Ami55] Shimshon A. Amitsur.  Finite subgroups of division rings.  Trans. Amer. Math. Soc., 80:361–386, 1955.
  * [Bal92] Keith Ball.  A lower bound for the optimal density of lattice packings.  Int. Math. Res. Not. IMRN, 1992(10):217–221, 05 1992.
  * [Ban93] W. Banaszczyk.  New bounds in some transference theorems in the geometry of numbers.  Math. Ann., 296(4):625–636, 1993.
  * [Bay06] Eva Bayer Fluckiger.  Upper bounds for Euclidean minima of algebraic number fields.  J. Number Theory, 121(2):305–323, 2006.
  * [BO13] Grégory Berhuy and Fréderique Oggier.  An introduction to central simple algebras and their applications to wireless communication.  Amer. Math. Soc., 2013.
  * [Cam18] Antonio Campello.  Random ensembles of lattices from generalized reductions.  IEEE Trans. Inform. Theory, 64(7):5231–5239, 2018.
  * [CK04] Henry Cohn and Abhinav Kumar.  Optimality and uniqueness of the Leech lattice among lattices.  Ann. of Math., 170, 03 2004.
  * [CKM+17] Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska.  The sphere packing problem in dimension 24.  Ann. of Math., 185(3):1017–1033, 2017.
  * [Coh16] Henry Cohn.  A conceptual breakthrough in sphere packing.  Notices Amer. Math. Soc., 64, 11 2016.
  * [CS88] John Conway and N. Sloane.  Sphere Packings, Lattices and Groups, volume 290 of Grundlehren Math. Wiss. Springer, 01 1988.
  * [DO16] Jérôme Ducoat and Frédérique Oggier.  On skew polynomial codes and lattices from quotients of cyclic division algebras.  Adv. Math. Commun., 10(1):79–94, 2016.
  * [DR47] Harold Davenport and Carl A. Rogers.  Hlawka’s theorem in the geometry of numbers.  Duke Math. J., 14(2):367 – 375, 1947.
  * [Gar21] Nihar Prakash Gargava.  Lattice packings through division algebras.  arXiv, abs/2107.04844, 2021.
  * [GZ07] Philippe Gaborit and Gilles Zémor.  On the construction of dense lattices with a given automorphisms group.  Ann. Inst. Fourier, 57(4):1051–1062, 2007.
  * [Hal05] Thomas C. Hales.  A proof of the Kepler conjecture.  Ann. of Math., 162:1063–1183, 2005.
  * [Hla43] Edmund Hlawka.  Zur Geometrie der Zahlen.  Math. Z., 49:285–312, 1943.
  * [Loe97] Hans-Andrea Loeliger.  Averaging bounds for lattices and linear codes.  IEEE Trans. Inform. Theory, pages 1767–1773, 1997.
  * [MG12] Daniele Micciancio and Shafi Goldwasser.  Complexity of lattice problems: a cryptographic perspective, volume 671.  Springer Sci. & Bus. Media, 2012.
  * [Min10] Hermann Minkowski.  Geometrie der Zahlen.  B.G. Teubner, 1910.
  * [Mou16] Philippe Moustrou.  On the density of cyclotomic lattices constructed from codes.  Int. J. Number Theory, 13, 03 2016.
  * [MSD19] Stephen D. Miller and Noah Stephens-Davidowitz.  Kissing numbers and transference theorems from generalized tail bounds.  SIAM J. Discret. Math., 33:1313–1325, 2019.
  * [Rei03] Irving Reiner.  Maximal Orders.  Lond. Math. Soc. Monogr. Ser. Clarendon Press, 2003.
  * [Rog47] Carl A. Rogers.  Existence theorems in the geometry of numbers.  Ann. of Math., 48(4):994–1002, 1947.
  * [RS87] Jason Rush and Neil Sloane.  An improvement to the Minkowski-Hlawka bound for packing superballs.  Mathematika, 34:8 – 18, 06 1987.
  * [Rus89] Jason A. Rush.  A lower bound on packing density.  Invent. Math., 98(3):499–510, 1989.
  * [Sie45] Carl L. Siegel.  A mean value theorem in geometry of numbers.  Ann. of Math., 46:340, 1945.
  * [TZ18] Jesse Thorner and Asif Zaman.  A unified and improved Chebotarev density theorem.  Algebra Number Theory, 13, 03 2018.
  * [Van11] Stephanie Vance.  Improved sphere packing lower bounds from Hurwitz lattices.  Advan. Math., 227, 05 2011.
  * [Ven12] Akshay Venkatesh.  A note on sphere packings in high dimension.  Int. Math. Res. Not. IMRN, 2013(7):1628–1642, 03 2012.
  * [Via17] Maryna S. Viazovska.  The sphere packing problem in dimension 8.  Ann. of Math., 185(3):991–1015, 2017.
  * [VL21] Roope Vehkalahti and Laura Luzzi.  The DMT of real and quaternionic lattice codes and DMT classification of division algebra codes.  ArXiv, abs/2102.09910, 2021.