Notable Lattices — Z^n, A_n, D_n, E_8, Leech Lattice

Not all lattices are created equal. Certain lattices appear repeatedly in mathematics, physics, and cryptography because they have exceptional properties: maximum packing density, deep algebraic symmetry, or computational structures that make them useful. This section surveys the most important lattice families — concrete examples that ground the abstract theory.

Beginner's Intuition 💡

Imagine stacking oranges at a grocery store. You naturally arrange them in a repeating, interlocking grid to fit as many as possible into a small space. That arrangement is a lattice!

Mathematicians have searched for years to find the absolute most efficient way to "stack oranges" not just in 3D space, but in 8-dimensional and 24-dimensional space. These perfectly optimized, impossibly dense arrangements have specific names (like the E₈ lattice or the Leech lattice). These are the "celebrities" of the lattice world.

The Integer Lattice ℤⁿ

The simplest lattice of all is the standard integer lattice $\mathbb{Z}^n$ : all points in $$n$$ -dimensional space with integer coordinates. Its basis is the identity matrix $$I_n$$ , its determinant is 1, and its shortest vector has length 1. Every other lattice can be thought of as a "deformation" of $\mathbb{Z}^n$ by an invertible linear map.

Properties of ℤⁿ

$\det(\mathbb{Z}^n) = 1$ (unit fundamental cell)
$\lambda_1 = 1$ (all coordinate unit vectors have length 1)
$\lambda_1 = \lambda_2 = \cdots = \lambda_n = 1$ (all successive minima equal)
$\mu = \sqrt{n}/2$ (covering radius: the corner of the unit cube)

Self-dual: $(\mathbb{Z}^n)^\vee = \mathbb{Z}^n$ . The integer lattice is its own dual. This makes it the natural setting for modular arithmetic over integers — the foundation of LWE.

The Hexagonal Lattice A₂ — Densest Packing in 2D

The hexagonal lattice $A_{2}$ is the two-dimensional root lattice and the solution to the oldest sphere packing problem: how do you arrange circles in the plane to cover the most area? The answer — proven by Thue in 1910 and rigorously confirmed by Fejes Tóth in 1940 — is the hexagonal arrangement, familiar from honeycombs and citrus displays.

The A₂ Lattice — Properties

$A_{2}$ is spanned by the vectors $b_{1} = (1, 0)$ and $b_{2} = (1/2, 3 /2)$ , or equivalently defined as:

$A_{2} = {(x_{0}, x_{1}, x_{2}) \in Z^{3} : x_{0} + x_{1} + x_{2} = 0}$
embedded into $R^{2}$ by projecting onto the plane $x_{0} + x_{1} + x_{2} = 0$ .

Key properties:
$det (A_{2}) = 3, λ_{1} = 2, kissing number = 6$
Packing density: $Δ (A_{2}) = π / 12 \approx 0.9069$ — the maximum possible in 2D, achieving Hermite's constant $γ_{2} = 2/ 3$ (see SVP).

$A_{2}$ is self-dual up to rotation and scaling: $A_{2}^{\lor}$ is a rotated copy of $A_{2}$ scaled by $1/ 3$ . Its Voronoi cells are regular hexagons, making it the most efficient 2D covering lattice as well.

The Root Lattices: Aₙ, Dₙ, and the Exceptional D₄

Root lattices arise from the classification of semisimple Lie algebras. They are the "next simplest" lattices after $Z^{n}$ and have important applications in sphere packing, error-correcting codes, and algebraic number theory.

The Aₙ lattice family

$A_{n} \subset Z^{n + 1}$ : the set of integer vectors $(x_{0}, \dots, x_{n})$ summing to zero.

$det (A_{n}) = n + 1, λ_{1} (A_{n}) = 2$ Kissing number of $A_{n}$ : $n (n + 1)$ .

$A_{1} = Z$ (the integers), $A_{2}$ is the hexagonal lattice (optimal 2D packing), $A_{3}$ is the face-centered cubic lattice (the familiar cannonball stacking).

The Dₙ lattice and D₄

$D_{n} \subset Z^{n}$ : integer vectors whose coordinate sum is even.

$D_{n} = {x \in Z^{n} : x_{1} + \dots + x_{n} \equiv 0 (mod 2)}$ $det (D_{n}) = 4, λ_{1} (D_{n}) = 2$ Kissing number of $D_{n}$ : $2 n (n - 1)$ .

$D_{4}$ is exceptional: it has kissing number 24 and extraordinary symmetry — its automorphism group has order 1152, three times larger than expected. $D_{4}$ is related to the quaternions and is the densest known 4D lattice packing.

D₄ and E₈ — Exceptional Lattices and Their Kissing Numbers

$E_{8}$ is arguably the most remarkable mathematical object in this field. It is the unique densest lattice packing in 8 dimensions, proven optimal by Maryna Viazovska in 2016 (Fields Medal, 2022). It has extraordinary symmetry: 240 minimal vectors (the "roots"), a kissing number of 240, and deep connections to modular forms, string theory, and the Monster group.

The E₈ Lattice — Definition and Properties

$E_{8}$ can be defined as the set of vectors $(x_{1}, \dots, x_{8}) \in R^{8}$ such that either:

— All $x_{i} \in Z$ and $\sum x_{i} \equiv 0 (mod 2)$ , or
— All $x_{i} \in Z + 1/2$ and $\sum x_{i} \equiv 0 (mod 2)$ .

Key properties:
$det (E_{8}) = 1 (self-dual: E_{8}^{\lor} = E_{8})$ $λ_{1} (E_{8}) = 2, kissing number = 240$ $Δ (E_{8}) = π^{4} /384 \approx 0.2537 (optimal in 8D)$ Hermite ratio: $λ_{1}^{2} / det (E_{8})^{2/8} = 2$ , achieving $γ_{8} = 2$ .

The 240 minimal vectors of $E_{8}$ form the root system of the exceptional Lie algebra, which appears in heterotic string theory. The automorphism group has order $696, 729, 600$ . $E_{8}$ is the unique even unimodular lattice in dimension 8.

Kissing number comparison: $D_{4}$ has kissing number 24; $E_{8}$ has 240; the Leech lattice has 196,560. These are the largest known kissing numbers in their respective dimensions, and in dimensions 4 and 8 they are provably optimal.

The Leech Lattice Λ₂₄ — 196560 Kissing Number and the Monster Group

In dimension 24, the Leech lattice $Λ_{24}$ plays the role $E_{8}$ plays in dimension 8 — and then some. Discovered by John Leech in 1965, it is the densest known 24-dimensional packing (proven optimal by Viazovska et al. 2016), has a kissing number of $196, 560$ , and its automorphism group is directly related to the Monster group — the largest sporadic finite simple group.

The Leech Lattice — Properties and Monster Group Connection

$det (Λ_{24}) = 1 (even unimodular in dimension 24)$ $λ_{1} (Λ_{24}) = 2, kissing number = 196, 560$ $Δ (Λ_{24}) = π^{12} /479001600 \approx 1.93 \times 1 0^{- 3} (optimal in 24D)$ Hermite ratio: $λ_{1}^{2} / det (Λ_{24})^{2/24} = 4$ , achieving $γ_{24} = 4$ .

The Leech lattice is the unique even unimodular lattice in dimension 24 with no vectors of squared length 2 (no "roots"). It can be constructed from the $[24, 12, 8]$ Golay code: arrange codewords as the coordinates of lattice vectors, apply appropriate scaling, and impose an integrality condition.

Connection to the Monster group: The automorphism group of $Λ_{24}$ is Conway's group $Co_{0}$ , of order:

$∣ Co_{0} ∣ = 8, 315, 553, 613, 086, 720, 000$
The Monster group $M$ — the largest sporadic simple group, of order roughly $8 \times 1 0^{53}$ — acts on a 196,884-dimensional space that decomposes into representations whose dimensions are directly related to the coefficients of the $j$ -function in number theory. This connection, called Monstrous Moonshine (proved by Borcherds, Fields Medal 1998), passes through the Leech lattice and its associated vertex operator algebra. The lattice is thus a bridge between combinatorics, number theory, and the deepest structure in finite group theory.

NTRU Lattices

The NTRU lattice is the algebraic lattice underlying the NTRU cryptosystem (1996) — the oldest lattice-based cryptosystem that remains secure. Unlike the geometric lattices above, NTRU lattices have a specific structure derived from polynomial rings.

Definition 24 — NTRU Lattice

In NTRU with ring $R = \mathbb{Z}[x]/(x^n - 1)$ and modulus $$q$$ , the public key is a polynomial $h = g \cdot f^{-1} \pmod{q}$ where $$f, g$$ are small polynomials. The NTRU lattice is:

$\Lambda_h = \{ (u, v) \in R^2 : u \equiv hv \pmod{q} \}$

Its basis matrix is a $2n \times 2n$ circulant block matrix. The short vector $$(f, g)$$ is hidden in this lattice; recovering it is the NTRU problem. The Falcon signature scheme (FIPS 206) is built on NTRU lattices.

Cyclotomic Lattices and Ring-LWE

Ring-LWE and Module-LWE operate over rings of integers in cyclotomic number fields. The ring $\mathbb{Z}[x]/(x^n + 1)$ (with $$n$$ a power of 2) is the ring of integers in the cyclotomic field $\mathbb{Q}(\zeta_{2n})$ , where $\zeta_{2n}$ is a primitive $$2n$$ -th root of unity.

Elements of this ring correspond to lattice points in $\mathbb{R}^n$ via the canonical embedding, and the ring structure induces a rich algebraic symmetry on the resulting lattice — called an ideal lattice. Every ideal in the ring corresponds to a sublattice, and the structure enables efficient arithmetic via NTT.

Ideal lattices

A lattice $\Lambda$ is an ideal lattice if it corresponds to an ideal in a number ring. It is closed under the ring's multiplication action: if $v \in \Lambda$ , then all cyclic rotations of $$v$$ are also in $\Lambda$ . This structure makes ideal lattices more efficient (NTT multiplication) but potentially more vulnerable to algebraic attacks than general lattices.

Module lattices

A module lattice is a direct sum of ideal lattices. Kyber and Dilithium use module lattices of rank $$k$$ — $$k$$ copies of an ideal lattice arranged as a vector. This interpolates between general LWE lattices (rank 1 is Ring-LWE; rank $$n$$ is close to plain LWE) and provides a more conservative hardness assumption than Ring-LWE alone.

q-ary Lattices Used in LWE-Based Cryptography

The lattices that actually appear in LWE and SIS hardness are called q-ary lattices. They are the most practically important family for post-quantum cryptography. Unlike the geometric lattices above (which are studied for their own properties), q-ary lattices are defined to encode a specific computational problem.

q-ary Lattices Λ_q^⊥(A) and Λ_q(A) — Definitions

For a uniformly random matrix $A \in Z_{q}^{m \times n}$ and prime modulus $q$ , define the two complementary q-ary lattices:

$Λ_{q}^{⊥} (A) = {y \in Z^{m} : A y \equiv 0 (mod q)}$
$Λ_{q} (A) = {y \in Z^{m} : \exists x \in Z^{n}, y \equiv A x (mod q)}$
Both are lattices in $Z^{m}$ containing $q Z^{m}$ as a sublattice. Their determinants are:

$det (Λ_{q}^{⊥} (A)) = q^{m - n}, det (Λ_{q} (A)) = q^{n}$
The two lattices are dual up to scaling: $Λ_{q} (A)^{\lor} = (1/ q) Λ_{q}^{⊥} (A^{⊤})$ . This duality is why SIS and LWE are dual problems: solving SIS means finding a short vector in $Λ_{q}^{⊥} (A)$ , while LWE decryption amounts to finding the nearest point in $Λ_{q} (A)$ to a given target.

Why these lattices are hard to attack: The matrix $A$ is public and random, so the lattice is not structured — an attacker sees a random-looking $m \times m$ integer lattice and must find a short vector (SIS) or solve CVP (LWE). By a worst-case to average-case reduction (Regev 2005, Peikert 2009), breaking random q-ary lattices is at least as hard as solving GapSVP in the worst case over all lattices of similar dimension.

In ML-KEM (Kyber), the modulus is $q = 3329$ and the dimension is $n = 256$ per module slot. In ML-DSA (Dilithium), $q = 8380417$ . These choices are carefully calibrated so that the smallest BKZ block size capable of finding a short vector in $Λ_{q}^{⊥} (A)$ requires at least $2^{128}$ operations.