Geometry of Numbers: Minkowski's Theorems Explained

What Is Geometry of Numbers?

Geometry of numbers is the study of number-theoretic questions using geometric objects such as lattices and convex bodies. Its central question is: when does a shape become large enough that it must contain a nonzero lattice point? Minkowski's theorem gives the exact volume threshold, turning a picture about points and shapes into a rigorous bound.

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 must cooperate — it cannot avoid the shape. This leads directly to bounds on how short a lattice’s shortest vector can be.

Minkowski's Theorem: A Visual Explanation

Minkowski in two dimensions. For Λ = ℤ², det(Λ) = 1, so the threshold is 4. The smaller shape can miss every nonzero point; a symmetric convex shape with area above 4 cannot.

Read the diagram from left to right. A small symmetric convex body may avoid every nonzero lattice point. In two dimensions, once its area exceeds $4\det(\Lambda)$ , avoidance becomes impossible: at least one point other than the origin lies inside. In $n$ dimensions, the same threshold is $2^n\det(\Lambda)$ .

Intuition

Draw a grid of dots on paper (a 2D lattice) and put the centre of a plate on one of the dots. A small plate may cover no other dot. A large enough plate always covers another one, wherever the grid is shifted or skewed.

The geometry of numbers says exactly how large is large enough. For any shape that is convex and symmetric about its centre, Minkowski’s theorem guarantees another dot as soon as the shape’s area is more than four times the area of one grid cell. The same argument shows that every lattice has a nonzero point fairly close to the origin, which gives an upper bound on 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

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 Convex Body Theorem (1896)

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

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

Applying this to the Euclidean ball $\mathcal{K} = \{ x : \|x\| \leq r \}$ of volume $V_n r^n$ (where $V_n = \pi^{n/2}/\Gamma(n/2+1)$ is the volume of the unit ball), and setting $V_n r^n = 2^n \det(\Lambda)$ , yields the Minkowski bound on the shortest vector:

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

The bound on $\lambda_1$ is tight up to a constant factor: random lattices have $\lambda_1 \approx \sqrt{n/(2\pi e)} \cdot \det(\Lambda)^{1/n}$ . A standalone walkthrough of the theorem, with the proof, counterexamples and a worked example, is in 6.5 Minkowski’s convex body theorem.

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 — Successive Minima and Minkowski’s Second Theorem

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

$\lambda_k(\Lambda) = \min\{ r > 0 : \dim\,\mathrm{span}(\Lambda \cap B(0,r)) \geq k \}$
where $B(0,r)$ is the closed ball of radius $r$ . This gives a sequence $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ .

Minkowski’s Second Theorem bounds their product:

$\frac{2^n}{n!} \cdot \frac{\det(\Lambda)}{V_n} \leq \prod_{k=1}^n \lambda_k(\Lambda) \leq 2^n \cdot \frac{\det(\Lambda)}{V_n}$
where $V_n = \pi^{n/2}/\Gamma(n/2+1)$ is the volume of the unit ball in $\mathbb{R}^n$ (with the Euclidean norm). 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 $\lambda_2, \dots, \lambda_n$ is at least as hard as SVP.

Minkowski also proved the sharper upper bound $\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). Both bounds are worked through on a checked example in 6.6 Minkowski’s second theorem.

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. Note that $\mu \geq \lambda_1/2$ , and noise below $\mu$ is not enough for decryption: a target can sit almost equally close to two lattice points. Unique decoding needs the noise below the packing radius $\lambda_1/2$ .

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^*$ :

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

In particular, $\lambda_1(\Lambda) \cdot \mu(\Lambda^*) \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.

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 $\gamma_n$ , named after Charles Hermite who proved the first bounds in 1850.

Hermite’s Constant — Definition and Known Values

$\gamma_n = \sup_{\Lambda \subset \mathbb{R}^n} \frac{\lambda_1(\Lambda)^2}{\det(\Lambda)^{2/n}}$
Equivalently, every lattice satisfies $\lambda_1(\Lambda) \leq \sqrt{\gamma_n} \cdot \det(\Lambda)^{1/n}$ , with equality achieved by the densest lattice in dimension $n$ .

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

$\gamma_1 = 1, \quad \gamma_2 = \tfrac{2}{\sqrt{3}} \approx 1.155, \quad \gamma_3 = \sqrt[3]{2} \approx 1.260$
$\gamma_4 = \sqrt{2} \approx 1.414, \quad \gamma_8 = 2, \quad \gamma_{24} = 4$
The value $\gamma_2 = 2/\sqrt{3}$ is achieved by the hexagonal lattice $A_2$ ; $\gamma_8 = 2$ by the $E_8$ lattice; $\gamma_{24} = 4$ by the Leech lattice $\Lambda_{24}$ . The values for $n = 5, 6, 7$ are also known; for every other dimension, $\gamma_n$ is not known exactly.

Asymptotically, Minkowski’s convex body theorem gives $\gamma_n \lesssim 2n/(\pi e)$ , Blichfeldt improves this to $\gamma_n \lesssim n/(\pi e)$ , and Kabatiansky–Levenshtein to about $1.744 \cdot n/(2\pi e)$ . From below, the Minkowski–Hlawka theorem gives $\gamma_n \gtrsim n/(2\pi e)$ . So $\gamma_n$ grows linearly in $n$ , but its exact asymptotic constant is unknown.

Check Your Understanding

Q1. Minkowski’s theorem requires the shape to be symmetric about the origin. Why does that condition matter?
Q2. You double the lattice determinant (spread the points out) in 2D. What happens to the area a centered convex shape needs to be guaranteed to catch a nonzero lattice point?
Q3. What does Minkowski’s bound λ₁ ≤ √n · $\det(\Lambda)^{1/n}$ actually give a cryptanalyst?
Q4. In LWE decryption the error is kept below half the shortest vector length (λ₁/2). What does that buy?

← Previous1.2Vectors & Bases Next →1.4Lattice MetricsMeasuring how "good" a lattice basis really is.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.