Geometry of Numbers — Minkowski's Theorem and Successive Minima

Here is a simple question: if you blow up a balloon inside a lattice, how big does it have to get before it is forced to touch a lattice point? The answer — which depends on both the size of the balloon and the density of the lattice — tells you something deep about the structure of the lattice. This kind of reasoning is the geometry of numbers, pioneered by Hermann Minkowski in 1896 at age 26. His two celebrated convex body theorems are the mathematical ancestor of every lattice reduction and shortest vector algorithm developed over the following century.

The central insight is that there is a precise relationship between the volume of a convex shape and the number of lattice points it must contain. Get your shape big enough, and the lattice mustcooperate — it cannot avoid the shape. This leads directly to bounds on how short a lattice's shortest vector can be.

Beginner's Intuition 💡

Imagine you have a grid of dots on a piece of paper (a 2D lattice). Now, take a coin (a shape) and try to place it on the paper without covering any dots. If your coin is small like a dime, this is easy. But if your coin is huge, like a dinner plate, it's impossible—no matter where you put it, it will cover at least one dot.

The Geometry of Numbers mathematically proves exactly how big that "plate" has to be before it is guaranteed to hit a dot. By knowing this, we can guarantee that every lattice has points that are relatively close to the center, which gives us the "Shortest Vector".

The Fundamental Cell

Before we can talk about volume and lattice density, we need one key concept: the fundamental cell (also called the fundamental parallelepiped). Think of it like the "unit tile" of the lattice (see vectors and bases) — the smallest region that tiles all of space perfectly when you place a copy at every lattice point.

Definition 6 — Fundamental Parallelepiped

Given a basis matrix $$B$$ , the fundamental parallelepiped is all the points you can reach with fractional (not just integer) steps along the basis vectors, using fractions in $$[0, 1)$$ :

$\mathcal{P}(B) = \{ t_1 b_1 + t_2 b_2 + \cdots + t_n b_n \mid 0 \leq t_i < 1 \}$

Its volume is $|\det(B)|$ , which we write as $\det(\Lambda)$ — the determinant of the lattice. This number is the same no matter which basis you choose, making it an intrinsic property of the lattice (not just of the basis).

The determinant measures how "densely packed" the lattice is. A small determinant means the fundamental cell is small, which means lattice points are close together — a dense lattice. A large determinant means a sparse lattice with widely spaced points.

Minkowski's Theorem

Now for the main event. Minkowski's theorem says: if your symmetric convex body (like a ball or a cube centered at the origin) has volume greater than $$2^n$$ times the lattice determinant, then it must contain a nonzero lattice point. You cannot build a lattice that evades arbitrarily large bodies forever.

Theorem 1 — Minkowski's First Theorem (1896)

Let $\mathcal{K}$ be any shape that is:
— convex (no dents), and
— symmetric about the origin (if $x \in \mathcal{K}$ then $-x \in \mathcal{K}$ )

If the volume of $\mathcal{K}$ is greater than $2^n \cdot \det(\Lambda)$ , then $\mathcal{K}$ contains at least one nonzero lattice point.

Intuition: once your shape is big enough relative to the lattice tile size, it overlaps too many translated copies of the fundamental cell and — by a pigeonhole argument — must catch a lattice point.

Applying this to a Euclidean ball (a sphere) immediately gives a bound on how short the shortest lattice vector can be. The sphere must eventually contain a lattice point; that gives an upper bound on $\lambda_1$ , the shortest vector length.

Corollary — Minkowski's Bound on the Shortest Vector

Every lattice in $$n$$ dimensions has a nonzero vector of length at most:

$\lambda_1(\Lambda) \leq \sqrt{n} \cdot \det(\Lambda)^{1/n}$

This is sometimes called the Minkowski bound. It says: no matter how you choose your lattice, the shortest vector cannot be longer than $\sqrt{n}$ times the "average lattice spacing" $\det(\Lambda)^{1/n}$ . The bound is nearly tight — there exist lattices where $\lambda_1$ is very close to this value.

Successive Minima: Beyond the Shortest Vector

The shortest vector is just one data point. To fully understand the shape of a lattice, we want to know how many short, linearly independent vectors exist. The successive minima capture this.

Think of it as follows: shrink a ball around the origin. The first time it touches a nonzero lattice point, the radius is $\lambda_1$ . Keep expanding. The second time the ball contains a lattice point that points in a genuinely new direction (not a multiple of the first), the radius is $\lambda_2$ . Continue until you have $$n$$ independent vectors — that gives $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ .

Theorem 2 — Minkowski's Second Theorem

The product of all successive minima is controlled by the lattice determinant. Specifically:

$\prod_{k=1}^n \lambda_k(\Lambda) \leq \gamma_n^{n/2} \cdot \det(\Lambda)$

where $\gamma_n$ is Hermite's constant (see §1.4). Intuitively: you cannot have all successive minima be simultaneously large — a denser lattice forces at least some short vectors to exist.

Packing and Covering: Two Views of the Same Lattice

Place a ball of radius $$r$$ at every lattice point. If $$r$$ is small enough, the balls don't overlap — you have a sphere packing. If $$r$$ is large enough, the balls cover every point in space — you have a sphere covering. These two radii have names and deep connections to hard computational problems.

Packing radius

The largest $$r$$ such that balls centered at lattice points don't overlap is $\rho = \lambda_1 / 2$ — half the shortest vector length. This is the "safe distance" between lattice points: any two distinct points are at least $2\rho$ apart. Maximizing this over all lattices is the classical sphere packing problem.

Covering radius

The smallest $$r$$ such that every point in space is within distance $$r$$ of some lattice point is the covering radius $\mu(\Lambda)$ . It is the "worst case distance" from any point to its nearest lattice point. This number is crucial for LWE decryption: as long as the noise is smaller than $\mu$ , decryption can recover the correct answer.

Connection to cryptography

Decrypting an LWE ciphertext is a special case of finding the nearest lattice point (CVP). Because the error is deliberately kept below $\lambda_1/2$ , there is a unique closest lattice point — and finding it requires knowing the secret key. Without the key, finding the nearest lattice point in high dimension is believed computationally infeasible.

Banaszczyk's Transference Theorem

One of the deepest results in the geometry of numbers connects a lattice to its dual: if one has a very short vector, the other must have a relatively long one, and vice versa. This "transference" principle is used in the security proofs of LWE.

Theorem 3 — Transference (Banaszczyk 1993)

For any full-rank lattice $\Lambda$ and its dual $\Lambda^\vee$ :

$1 \leq \lambda_k(\Lambda) \cdot \lambda_{n-k+1}(\Lambda^\vee) \leq n$

In particular, $\lambda_1(\Lambda) \cdot \mu(\Lambda^\vee) \leq n$ .

What this means: if you can find a short vector in the lattice, you can bound how large the covering radius of the dual lattice is — and vice versa. The two lattices are in a quantifiable geometric tension.

Minkowski's Convex Body Theorem — Precise Statement

Minkowski's theorem is often stated informally, but its precise form is worth knowing carefully. The key condition is that the convex body must be symmetric about the origin and have volume strictly greater than $2^{n} det (Λ)$ . At exactly $2^{n} det (Λ)$ , the theorem still holds if $K$ is also compact (closed and bounded), giving the tight version.

Minkowski's Convex Body Theorem — Full Statement

Let $Λ \subset R^{n}$ be a full-rank lattice with determinant $det (Λ)$ , and let $K \subset R^{n}$ be a convex, origin-symmetric set. Then:

$vol (K) > 2^{n} \cdot det (Λ) ⟹ K contains a nonzero point of Λ$
If additionally $K$ is compact (closed and bounded), the strict inequality can be replaced with $\geq$ .

Applying this to the Euclidean ball $K = {x : ∥ x ∥ \leq r}$ of volume $V_{n} r^{n}$ (where $V_{n} = π^{n /2} /Γ (n /2 + 1)$ is the volume of the unit ball), and setting $V_{n} r^{n} = 2^{n} det (Λ)$ , yields the Minkowski bound on the shortest vector:

$λ_{1} (Λ) \leq n \cdot det (Λ)^{1/ n}$
The proof uses a pigeonhole argument over translates of the fundamental domain: shrink $K$ by half, tile space by $Λ$ , and observe that distinct translates must overlap by volume considerations.

Successive Minima and Minkowski's Second Theorem

The first minimum $λ_{1}$ tells us the length of the shortest nonzero lattice vector. The successive minima extend this to a full sequence capturing the shortest linearly independent set of lattice vectors.

Successive Minima — Formal Definition

The $k$ -th successive minimum of a lattice $Λ$ is:

$λ_{k} (Λ) = min {r > 0 : dim span (Λ \cap B (0, r)) \geq k}$
where $B (0, r)$ is the closed ball of radius $r$ . This gives a sequence $λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}$ .

Minkowski's Second Theorem bounds their product:

$\frac{2 ^{n}}{V _{n}} \cdot det (Λ) \leq k = 1 \prod n λ_{k} (Λ) \leq 2^{n} \cdot det (Λ)$
where $V_{n} = π^{n /2} /Γ (n /2 + 1)$ is the volume of the unit ball in $R^{n}$ . The upper bound says you cannot have all successive minima be simultaneously large in a dense lattice. The lower bound says you cannot have them all be simultaneously small either — a constraint that limits how well-packed any lattice can be.

Note: unlike the first theorem, computing the successive minima is hard in general. The problem of finding $λ_{2}, \dots, λ_{n}$ is at least as hard as SVP.

Hermite's Constant γₙ

Among all lattices of the same determinant, which one has the longest shortest vector? The answer is quantified by Hermite's constant $γ_{n}$ , named after Charles Hermite who proved the first bounds in 1850.

Hermite's Constant — Definition and Known Values

$γ_{n} = Λ \subset R^{n} sup \frac{λ _{1} ( Λ ) ^{2}}{det ( Λ ) ^{2/ n}}$
Equivalently, every lattice satisfies $λ_{1} (Λ) \leq γ_{n} \cdot det (Λ)^{1/ n}$ , with equality achieved by the densest lattice in dimension $n$ .

Known exact values (these correspond to the densest sphere packings):

$γ_{1} = 1, γ_{2} = \frac{2}{3} \approx 1.155, γ_{3} = 32 \approx 1.260$
$γ_{4} = 2 \approx 1.414, γ_{8} = 2, γ_{24} = 4$
The value $γ_{2} = 2/ 3$ is achieved by the hexagonal lattice $A_{2}$ ; $γ_{8} = 2$ by the $E_{8}$ lattice; $γ_{24} = 4$ by the Leech lattice $Λ_{24}$ . For all other dimensions, $γ_{n}$ is not known exactly.

Asymptotically, Minkowski's theorem gives $γ_{n} \leq n / (π e) + O (lo g n)$ , while the Blichfeldt bound gives $γ_{n} \leq 2 n / (π e) + O (1)$ . The true growth rate is $γ_{n} \sim n / (2 π e)$ as $n \to \infty$ .