Lattices: The Geometry of Discrete Point Sets

Two Sources of a Simple Idea

Take the integer points of the plane: all pairs \((a, b)\) with \(a, b \in \mathbb{Z}\). This is among the most familiar infinite patterns in mathematics, a regular grid repeating identically in every direction. Replace the two unit steps that generate it, \((1,0)\) and \((0,1)\), with any two other vectors that do not lie on a common line, and take all their integer combinations. The result is again an evenly spaced array of points, sheared or stretched but still perfectly periodic. Such a point set is a lattice, and this page studies its geometry in \(\mathbb{R}^n\).

The definition that follows will look almost too plain to repay attention. A lattice is the set of integer combinations of some independent vectors. Two independent historical currents explain why this plain object rewards close study, and both feed the questions this page goes on to raise.

The geometry of numbers

The first current is the study of whole numbers through geometry. A question in arithmetic can be recast as a question about how the integer points of the plane or of a higher-dimensional space are arranged relative to a region. Two questions of this kind are which integers can be written as a sum of two squares and how well an irrational number can be approximated by fractions. Minkowski's insight, late in the nineteenth century, was that a sufficiently large symmetric convex region must swallow a lattice point other than the origin, purely for reasons of volume. This turns arithmetic statements into statements about area and volume, and it is the reason a lattice carries a genuine geometry rather than a mere combinatorial pattern. We take up this circle of ideas, and the notion of the shortest lattice vector it controls, in a companion page.

The reduction of quadratic forms

The second current is the search for a good set of generating vectors. The same lattice can be produced by many different pairs of vectors. Some are nearly orthogonal and short, others are long and skewed almost onto a single line. Lagrange and Gauss, studying binary quadratic forms, developed a procedure to replace a skewed pair by a short and nearly orthogonal one generating the same lattice. This basis-reduction idea was later extended to arbitrary dimension, and in the twentieth century an efficient form of it became one of the most widely used algorithms in computational mathematics. The non-uniqueness of the generating set, which we make precise below, is exactly what gives this search room to operate.

Beyond these two currents, a further face of the lattice belongs to the physical sciences. A crystal repeats a fixed arrangement of atoms at the points of a lattice, and in three dimensions a lattice arrangement achieves the greatest possible density for stacking equal spheres. We note this only to set it aside. The thread we follow is the mathematical one, the geometry of numbers and the reduction of bases, because it is this thread that leads, much later, to the hard computational problems on which a new generation of cryptography is built. That destination is still several steps away. The immediate task is to fix the definitions with care.

Lattices and Their Bases

Fix a collection of \(k\) vectors \(\mathbf{b}_1, \dots, \mathbf{b}_k \in \mathbb{R}^n\) that are linearly independent. The lattice they generate is the set of all their integer combinations.

Two integer parameters record the shape of the lattice and its ambient space. The number \(k\) of basis vectors is the rank of the lattice, and the dimension \(n\) of the surrounding space is its dimension. When \(k = n\), so that the basis vectors span all of \(\mathbb{R}^n\), the lattice is called full-rank. The integer grid \(\mathbb{Z}^n\), generated by the standard basis, is the prototypical full-rank lattice. The single line of points \(\mathcal{L}\big((2,1)^\top\big) \subset \mathbb{R}^2\) is a rank-\(1\) lattice that sits inside a two-dimensional space and is therefore not full-rank. Unless stated otherwise, the lattices we treat are full-rank, so that \(\mathbf{B}\) is a square invertible matrix. The general case differs in bookkeeping rather than in substance.

An intrinsic description

The definition above builds a lattice from a chosen basis. There is a second, coordinate-free way to say what a lattice is, one that names no generators at all and instead describes the point set by two structural properties it possesses.

The first property is algebraic. A lattice is closed under the vector-space operations that keep it inside itself. The origin belongs to it, and if \(\mathbf{x}\) and \(\mathbf{y}\) are lattice points then so are \(-\mathbf{x}\) and \(\mathbf{x} + \mathbf{y}\). In the language of the algebra track, a lattice is an additive subgroup of \(\mathbb{R}^n\). The second property is topological, and it is what separates a lattice from a dense set of points such as \(\mathbb{Q}^n\). A lattice is discrete. Every lattice point has a surrounding ball of some positive radius that contains no other lattice point. The two properties reinforce each other. If the only lattice point within distance \(r\) of the origin is \(\mathbf{0}\) itself, then any two distinct lattice points \(\mathbf{x}\) and \(\mathbf{y}\) satisfy \(\|\mathbf{x} - \mathbf{y}\| \ge r\), because \(\mathbf{x} - \mathbf{y}\) is itself a nonzero lattice point. The points do not merely fail to fill space. They stay apart by one and the same gap everywhere.

These two properties characterize lattices exactly. A subset of \(\mathbb{R}^n\) arises as \(\mathcal{L}(\mathbf{B})\) for some independent basis if and only if it is a discrete additive subgroup of \(\mathbb{R}^n\). The forward direction is immediate. Integer combinations of independent vectors form an additive subgroup, and since \(\mathbf{B}\) is injective with a continuous inverse on its image, the separation of the integer points of \(\mathbb{Z}^k\) carries over to \(\mathcal{L}(\mathbf{B})\), so the set is discrete. The reverse direction, that every discrete additive subgroup admits a finite independent generating set, is a standard fact in the geometry of numbers, which we take as known rather than prove here. The two descriptions may be used interchangeably in what follows.

Change of Basis

The integer grid \(\mathbb{Z}^2\) is generated by the standard basis \((1,0)^\top, (0,1)^\top\). It is equally generated by \((1,1)^\top, (2,1)^\top\). Every integer point is an integer combination of the second pair, and conversely. A single lattice therefore carries many bases, and the freedom to pass between them is what basis reduction exploits. We now make this freedom exact by determining which changes of basis preserve the lattice and which do not.

A change of basis is a matrix acting on the right of \(\mathbf{B}\). Replacing \(\mathbf{B}\) by \(\mathbf{B}\mathbf{U}\) produces new columns that are combinations of the old ones. For the new columns to be integer combinations of the old, and vice versa, both \(\mathbf{U}\) and its inverse must have integer entries. Such matrices have a clean characterization.

The connection between the two notions is that unimodular matrices are exactly the integer matrices with an integer inverse. Suppose \(\det(\mathbf{U}) = \pm 1\), so that \(\mathbf{U}\) is invertible. The adjugate formula for the inverse writes \(\mathbf{U}^{-1} = \det(\mathbf{U})^{-1} \operatorname{adj}(\mathbf{U})\), where the adjugate \(\operatorname{adj}(\mathbf{U})\) is built from determinants of integer submatrices of \(\mathbf{U}\) and therefore has integer entries. Dividing integer entries by \(\det(\mathbf{U}) = \pm 1\) leaves them integers, so \(\mathbf{U}^{-1}\) is again an integer matrix, and indeed itself unimodular.

Conversely, if both \(\mathbf{U}\) and \(\mathbf{U}^{-1}\) have integer entries, then \(\det(\mathbf{U})\) and \(\det(\mathbf{U}^{-1})\) are both integers, and by the multiplicativity of the determinant their product is \(\det(\mathbf{U}\mathbf{U}^{-1}) = \det(\mathbf{I}) = 1\). The only integers whose product is \(1\) are \(\pm 1\), so \(\det(\mathbf{U}) = \pm 1\). The unimodular matrices thus form a group under multiplication.

A point left open earlier can now be settled. The rank of a lattice was defined as the number of vectors in a basis, and this is well-defined only if every basis has the same size. Any two bases of a lattice are linearly independent sets with the same span, namely the real span of the lattice, so the invariance of dimension gives them the same size, and the rank is an invariant of the lattice and not of the basis. The theorem will return in a sharper form once a volume is attached to a basis.

The fundamental parallelepiped

A basis carries with it a natural tile, the region swept out by combinations of the basis vectors with coefficients in the half-open unit interval.

The tile depends on the basis. A skewed basis produces a long, slanted parallelepiped, while a nearly orthogonal one produces a nearly rectangular tile. What does not depend on the basis is the way the tile fills space. Placing one copy of \(\mathcal{P}(\mathbf{B})\) at each lattice point covers all of \(\mathbb{R}^n\) exactly once.

To see this, write any point as \(\mathbf{p} = \mathbf{B}\mathbf{y}\) with \(\mathbf{y} \in \mathbb{R}^n\), and split each coordinate into its integer and fractional parts, \(y_i = \lfloor y_i \rfloor + \{y_i\}\) with \(\lfloor y_i \rfloor \in \mathbb{Z}\) and \(\{y_i\} \in [0, 1)\). Then \(\mathbf{p} = \mathbf{B}\lfloor \mathbf{y} \rfloor + \mathbf{B}\{\mathbf{y}\}\), where the first term is a lattice point and the second lies in \(\mathcal{P}(\mathbf{B})\). This decomposition is unique because the integer and fractional parts of a real number are, so every point of space lies in exactly one translate, with no gaps and no overlaps.

Together with a single tile, the lattice thus tiles the whole space by translation, and that is the geometric content of the basis being a set of generators. The volume of the tile is the quantity the companion page takes up first. There it is shown to be identical across all bases of the lattice, and it becomes the lattice's determinant.

The Shortest Vector

A lattice has a feature the integer grid hides from view. In \(\mathbb{Z}^n\) the nonzero points nearest the origin are the standard basis vectors and their negatives, all of length one. In a skewed lattice the shortest nonzero vector may be far from any basis vector we happened to write down, and finding it is not obvious from the basis at all. This shortest length is a central geometric invariant of a lattice, and it is the quantity the rest of the lattice story circles back to.

Throughout, \(\|\cdot\|\) denotes the Euclidean norm \(\|\mathbf{x}\| = \big(\sum_i x_i^2\big)^{1/2}\), unless another norm is named. The definitions below adapt to any norm by substituting its unit ball for the Euclidean one.

Setting \(i = 1\) recovers the minimum distance, so the successive minima are a graded refinement of a single idea. The first minimum \(\lambda_1\) measures the shortest vector, \(\lambda_2\) the shortest vector in a new direction, and so on up to \(\lambda_n\), which measures how far one must reach to capture a full set of \(n\) independent short vectors.

The insistence on linear independence is what keeps \(\lambda_2\) from collapsing back onto \(\lambda_1\). The vector \(-\mathbf{v}\) has the same length as a shortest vector \(\mathbf{v}\), but it spans the same line, so it adds no new direction and does not count toward \(\lambda_2\). Only a vector spanning a new direction advances the dimension in the definition. The successive minima increase weakly, \(\lambda_1 \le \lambda_2 \le \dots \le \lambda_n\), directly from the definition, since a ball large enough to hold \(i\) independent vectors also holds \(i - 1\) of them.

Two facts make these quantities well-posed rather than formal. First, the minimum in the definition is attained. Lattice points are separated by a fixed gap, so the balls of half that radius centred at them are disjoint, and only finitely many disjoint balls of a fixed radius fit inside a bounded region. Only finitely many lattice points therefore lie within any fixed radius, and a shortest nonzero vector exists rather than being merely approached. Second, the same gap bounds \(\lambda_1(\mathcal{L})\) below by a positive number, which is the geometric expression of the discreteness we built into the definition of a lattice.