Lattices, The Point Lattice Theorem

The Point Lattice Theorem

Consider an integer lattice in Rⁿ, with covolume v. If a compact set S is convex, and symmetric about 0, with volume ≥ 2ⁿv, then S contains a nonzero lattice point. This is the point lattice theorem, by Minkowski. (biography)

Strict Inequality

It is enough to demonstrate the point lattice theorem for volumes > 2ⁿv. Suppose the theorem holds for strict inequality, but not for equality. Find a convex shape, symmetric about 0, with volume equal to 2ⁿv, that contains no other lattice points beyond 0. Magnify this shape by 1+ε, expanding it away from 0. For every ε, the resulting shape holds a nonzero lattice point. Let ε approach 0 and find infinitely many points in a bounded region. This is a contradiction. Hence we will prove the result for any shape whose volume exceeds 2ⁿv, and that will suffice.

What Kind of Shape is S?

Start at 0 and select any direction, indicated by the unit vector u. If +3u is in S, then so is -3u. That's what we mean by symmetric about 0. Also, the entire segment from -3u to +3u is in S. That's what we mean by convex.

A line drawn through the origin intersects S in a closed line segment. The segment is closed and bounded because S is compact.

Let r(u) be the radius of S, as a function of direction. This defines the surface of S. As you walk about, there are no valleys or craters, because S is convex. There may be a mountain, or even a sharp corner, e.g. when S is a cube, but you can't fall into a hole.

Walk in a particular direction, all the way around S, and the vector u traces out a circle. Along this path, r(u) is continuous. Suppose it is not continuous at r(u₀) = h. Near u₀, r remains above or below h±ε infinitely often. If the elevation remains low, then h looks like a step up on the surface. Draw a line from h to a nearby point at h-ε, and this line passes through empty space. Since S is convex, this is impossible. Therefore r remains above h+ε, on at least one side of u₀. Draw a line from a high point near h to a point on the other side. Whether the other side is high or low, or level with h, the line still sails over the top of h at u₀. Once again S fails to be convex. Therefore the path along S is continuous in any direction.

It may be possible to parlay this into a proof that the surface of S is continuous, but I can't seem to fill in the details. Fortunately this theorem is usually applied to simple shapes such as polyhedra, where the surface is piecewise smooth. Volume is calculated by traditional integration, and there is no trouble.

The Volume Argument

Contract S towards the origin by cutting r(v) in half. Thus the volume of S is reduced by 2ⁿ, but it is still larger than v.

Cut S into pieces, by using the hyperplanes of the lattice. In other words, build the base cell of the lattice and let it tile space. Each cell that intersects S cuts out a piece of S. Translate this piece back to the base cell at the origin. Thus S may be cut into many pieces, and all those pieces are carried back to their corresponding locations in the base cell.

Although there might be a lot of pieces, the number of pieces is finite. This is because S is bounded. It is contained in a large bounded region in Rⁿ, and the number of cells in such a region is finite.

If S were cut into infinitely many pieces, with volumes approaching 0, it might be possible to put those pieces back together to make something smaller than S. It's counterintuitive, but you can reduce the volume of a shape just by cutting it up and reassembling the pieces. However, nothing like that can happen here, because the number of pieces is finite. The volume of S is indeed the sum of its pieces.

Suppose these pieces do not overlap in the base cell. They may share a border, but they don't overlap. The volume consumed by these pieces exceeds v, even though they live in a cell of size v. This is a contradiction, hence at least two pieces overlap.

There are points x and y in S that map to the same point in the base cell. Thus y-x is w, a vector in our lattice. Since S is symmetric it also contains -x. Let z = -x and write y+z = w. The midpoint of y and z, which is (y+z)/2, equals ½w. By convexity, this midpoint lies in S. Finally, expand S by 2, resurrecting the original shape. Now S contains y+z, or w, which is a nonzero lattice point.

Lesser Volume

If the volume is any smaller, the theorem fails. Consider the integers within the reals. A closed segment of length less than 2, symmetric about the origin, contains no other lattice points.