Measuring a Lattice: Determinant and Minkowski's Theorem

The previous note showed that a lattice has many bases and that they differ enormously in usefulness. This note finds a number that does not depend on which basis you picked, and then uses it to prove that a short vector must exist.

01.Tiling

Take the parallelogram spanned by $b_1$ and $b_2$, and place one copy at every lattice point. The copies cover the plane exactly. No gaps anywhere, and no two copies overlapping.

This tile is called the fundamental parallelepiped of the basis, or the fundamental domain, and formally it is

$$\mathcal{P}(B) \;=\; \Bigl\{\, t_1 b_1 + t_2 b_2 + \cdots + t_n b_n \;:\; t_i \in [0, 1) \,\Bigr\}.$$

The half-open interval $[0,1)$ is what makes the tiling exact rather than approximate: each edge belongs to one tile and not to its neighbour, so nothing is double-counted.

Different bases give differently shaped tiles. The good basis from the previous note gives a fat rhombus. The bad basis gives a long thin sliver. Draw both and they look nothing alike.

They have the same area.

That is not a coincidence, and it is the fact this note is built on.

02.The determinant

For a full-rank lattice with basis matrix $B$, define

$$\det(\mathcal{L}) \;=\; |\det B|.$$

The vertical bars are absolute value, since a determinant can come out negative depending on the order of the columns and an area cannot.

For the running example,

$$B = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}, \qquad \det B = 3 \cdot 2 - 1 \cdot 1 = 6 - 1 = 5.$$

Check it against the bad basis, which describes the same lattice:

$$B' = \begin{pmatrix} 7 & 11 \\ 4 & 7 \end{pmatrix}, \qquad \det B' = 7 \cdot 7 - 11 \cdot 4 = 49 - 44 = 5.$$

Same number.

This is guaranteed rather than lucky. From Good and Bad Bases, any two bases of one lattice are related by $B' = BU$ with $U$ unimodular, and determinants multiply, so

$$\det B' \;=\; \det B \cdot \det U \;=\; \det B \cdot (\pm 1).$$

Taking absolute values, the sign disappears and the two agree. So $\det(\mathcal{L})$ is a property of the lattice, not of any description of it.

03.What the number means

The determinant measures how spread out the lattice is. Concretely, it is the area of the plane per lattice point.

For our lattice, $\det(\mathcal{L}) = 5$, so on average there is one lattice point in every region of area $5$. Compare $\mathbb{Z}^2$, where the basis is the identity matrix, the determinant is $1$, and there is one point per unit square. Our lattice is five times sparser.

The intuition to carry forward is a trade-off:

Small determinant means tightly packed, which means points are close together, which means there is a short vector.

Large determinant means spread out, which means points are far apart, which means the shortest vector is long.

That intuition can be made exact, and it was, in 1889.

04.Minkowski's first theorem

Theorem (Minkowski, 1889). For any full-rank lattice $\mathcal{L}$ in $\mathbb{R}^n$, the shortest non-zero vector has Euclidean length at most

$$\sqrt{n} \cdot \det(\mathcal{L})^{1/n}.$$

Check it against the running example. Here $n = 2$ and $\det(\mathcal{L}) = 5$, so the bound is

$$\sqrt{2} \cdot 5^{1/2} \;=\; \sqrt{10} \;\approx\; 3.162 .$$

The theorem promises a non-zero lattice vector no longer than $3.162$. Look at the table from What a Lattice Is: the point $(-2, 1)$ is on the lattice, and its length is

$$\sqrt{(-2)^2 + 1^2} \;=\; \sqrt{5} \;\approx\; 2.236 .$$

Comfortably under the bound, so the theorem holds here. It is worth noticing that the theorem gives an upper bound on the shortest length and not the length itself. The actual shortest vector can be much shorter than the bound, and here it is.

The proof is a pigeonhole argument about boxes, and it uses no number theory at all. This book does not reproduce it.

05.Why the theorem matters here

The content is subtler than "short vectors exist", so it is worth stating carefully.

Minkowski says that the determinant alone constrains the shortest vector. You do not need to know the basis, the shape, or anything else about the lattice. One number forces the existence of a vector below a certain length.

That has two consequences for cryptography, pulling in opposite directions.

It tells a designer that a short vector is always there to be found, so the security of a lattice scheme can never rest on a short vector being absent. It is present. The security rests entirely on it being hard to locate.

And it gives a designer a calibration tool. Given a target dimension and a modulus, Minkowski says roughly how short the shortest vector is, which says how much noise a scheme can add before the noise itself starts looking like a lattice vector and decryption breaks. Chapter 5 uses exactly this when it explains ML-KEM's decryption failure probability.

The next note turns "locate the short vector" into the two problems that are actually assumed hard.