Every way down, and no way round

How many sublattices of a given index a plane lattice has is a counting question with a tidy answer — the sum of the divisors of the index — and counting is where that essay stopped. There is a further question, and it is the one that turns a list into an object.

What are the sublattices to each other?

Two of them can contain a third; one can be a scaled copy of another; a chain of them can descend step by step. Those relations are not arbitrary, and the shape they make is not one anybody would guess from a divisor sum.

The two conditions that make it a tree #

Fix a prime p and restrict attention to sublattices whose index is a power of it. Two conventions turn the collection into a graph.

Two sublattices are the same vertex when one is a rational multiple of the other. The lattice L, its double 2L and its third L/3 are one thing here, because they differ by a change of scale and nothing else. That is the identification called homothety, and it is the step that makes the object finite at each level rather than infinite.

Two vertices are joined when one contains the other with index p. Nothing else counts as an edge.

With those conventions the graph has two properties, and the whole of the interest is in the second.

p + 1 neighbours, and why #

From the whole lattice there are exactly p + 1 sublattices of index p, and the reason is a change of subject that is worth making explicitly.

A sublattice of index p contains pℤ², so it corresponds to a subgroup of ℤ²/pℤ², which is a two-dimensional vector space over the field of p elements. A subgroup of index p in that is a line through the origin, and a two-dimensional space over a field of p elements has exactly p + 1 lines: p of them with a definite slope and one vertical.

So the branching number is the number of points on a projective line, and it is p + 1 for the same reason projective lines have that many points. Arithmetic that looked like divisor-counting has turned into linear algebra over a finite field.

The same count applies at every vertex, because every vertex is a lattice and every lattice looks like ℤ² from its own point of view. Hence: p + 1 neighbours everywhere.

No cycles, and why #

From a vertex at distance k from the whole lattice, one of its p + 1 neighbours is nearer the root and p are further. That is what makes the graph a tree, and it is checked here on every vertex whose whole neighbourhood was grown rather than argued from the general theory.

The counts follow: one vertex at distance zero, p + 1 at distance one, and (p + 1)p^(k−1) at distance k. For p = 2 that is 1, 3, 6, 12, 24; for p = 3 it is 1, 4, 12, 36; for p = 5 it is 1, 6, 30, 150.

The absence of cycles is the surprise. A collection of sublattices ordered by containment is a partially ordered set, and partial orders usually have plenty of diamonds — two things both containing a third and both contained in a fourth. Here there are none, once scale is divided out, and a walk that leaves the root can never come back to it except by retracing.

Hermite normal form is what makes it computable #

A lattice has infinitely many bases, so “is this the same sublattice?” is not a question about matrices until a canonical form is chosen. The Hermite normal form is that form: for a rank-two lattice it is the unique upper-triangular integer matrix with positive diagonal and its off-diagonal entry reduced modulo the one below it.

Two bases span the same sublattice exactly when their Hermite forms are equal, so the comparison is three integers rather than a search. The enumeration of index-n sublattices is then a double loop — over divisors d of n, and over the d values the off-diagonal entry can take — and it produces σ(n) of them, which is required to equal the divisor sum rather than being replaced by it.

The homothety class is one further step: divide the Hermite form by the greatest common divisor of its entries. Every homothety class of sublattice contains exactly one such primitive form, so vertices of the tree and primitive Hermite forms are the same thing, and equality of vertices is again a comparison of three integers.

Why scale has to be divided out #

The homothety identification is the one convention in the construction, and it is worth defending, because without it the object is not a tree and the whole picture disappears.

Keep scale and the sublattices of index a power of p form a partially ordered set with pℤ² ⊂ ℤ² at index p², and now there are diamonds everywhere: pℤ² is contained in three different index-p sublattices, each of which contains it, so four vertices close a cycle. The graph is dense with four-cycles and nothing about it is tree-like.

Dividing by scale removes exactly those cycles, and the reason is that they were never really cycles. Two lattices differing by a factor of p are the same lattice measured in different units; a crystallographer would call them the same lattice on a cell of a different size, which is the cell being a choice again. The identification is not a trick to make the picture nicer — it is the removal of a distinction that was not there.

What it costs is the index. Once scale is gone, a vertex has no index: only pairs of vertices have a distance, and asking how far a vertex is from the root is asking a question about the pair. That is why the two counts in the table differ, and it is the only real price the convention exacts.

What the tree is #

The object has a name, and it belongs to a subject that looks nothing like crystallography.

It is the Bruhat–Tits tree of the group PGL₂ over the p-adic numbers, and it is to that group what the hyperbolic plane is to PGL₂ over the reals: the space the group acts on, from which its structure can be read. Vertices are homothety classes of lattices; the group permutes them; distance in the tree measures how far two lattices are from being scaled copies.

For a reader who has met a lattice only as a grid of dots, that is a considerable widening. The same object — a discrete subgroup of full rank in a plane — supports a geometry in which the natural picture is not a grid at all but an infinitely branching tree, and the branching number is a prime.

Distance, and what it measures #

A pair of vertices in a tree has a distance, and here it has a meaning in terms of the lattices.

If M ⊆ L with L/M cyclic of order p^k — a single elementary divisor — the two vertices are at distance k. If the quotient has two elementary divisors p^a and p^b with a ≤ b, then dividing out the common factor p^a gives a cyclic quotient of order p^(b−a), and the distance is b − a.

Distance in the tree is the gap between the elementary divisors, which is a purely arithmetic quantity, and it is zero exactly when the two lattices are scaled copies. That is the sense in which the tree metrises the difference between two lattices that this collection has otherwise treated as a yes-or-no matter.

It also explains the mismatch of the two counts. A sublattice of index p^k whose elementary divisors are p^a and p^(k−a) sits at distance |k − 2a| from the root, not at distance k; only the ones with a trivial first divisor — the primitive ones — are as far away as their index suggests.

Where it touches the rest of the subject #

Three connections, of increasing distance from crystallography.

Centring. A centred cell is a sublattice of index two of a lattice, or equivalently a lattice of index two in the centred one, and the three index-two sublattices of a plane lattice are exactly the three neighbours of the root at p = 2. The bookkeeping the fourteen Bravais lattices require is a walk of one step in this tree.

Superstructures. An ordered alloy on a superlattice is a sublattice of the parent, and the reflections it adds are indexed by the quotient. The same relation decides which sublattices keep the parent’s own symmetry, which is a question about the vertex and not about its index. The tree organises the possible superlattices by how far they are from the parent, which is the natural way to enumerate the small ones.

And the arithmetic itself. The reason there are p + 1 neighbours is the reason a projective line over a field of p elements has p + 1 points, and that fact is doing the same work here that it does in the classification of finite simple groups and in the theory of modular forms. Nothing about crystals is being used; the lattice is doing the work.

Growing it, and checking it #

The tree is not drawn from the formula. It is grown breadth-first from the whole lattice: at each step every current vertex’s p + 1 neighbours are computed, canonicalised and looked up, and the ones not already seen become the next level.

That order of operations is deliberate, because it makes the two claims of this essay into measurements rather than restatements. Regularity is checked by computing every neighbourhood and requiring it to have p + 1 distinct members. Acyclicity is checked by requiring every vertex except the root to have exactly one neighbour nearer the root — which is what having no cycles amounts to in a connected graph grown this way. And the level sizes are counted and required to equal (p + 1)p^(k−1).

All three hold at every prime measured. Had the canonicalisation been wrong — had the division by the content been forgotten, say — the level sizes would have come out too large and the acyclicity check would have failed in the same run, which is the kind of double failure that makes a bug easy to find.

The negative tests matter as much. A sublattice and a scaled copy of it must be one vertex, and two sublattices of the same index differing by no scale must be two; both are asserted, because a canonicalisation that collapsed everything would satisfy the first perfectly.

The edge of the tree #

A tree with no cycles and infinite branching has a boundary — the set of ways of walking away from the root and never coming back — and that boundary has a description worth having, because it is where the analogy with the hyperbolic plane becomes exact.

An end of the tree is an infinite path leading away from the root without repeating a vertex, taken up to agreeing eventually. At every step there are p ways to continue, so the ends are the sequences of choices, one from p options at each step, after the first choice from p + 1.

Those sequences are exactly the points of a projective line over the p-adic numbers, which is what the tree’s branching number already suggested: at each finite level the neighbours are the points of a projective line over the field of p elements, and taking the limit assembles them into a projective line over the completion.

That gives the tree its place in the family. The hyperbolic plane is the symmetric space of the real linear group, and its boundary is a circle — the real projective line. The tree is the same construction over the p-adic numbers, its boundary is the p-adic projective line, and the two are the same object in two arithmetics.

For a reader who came for sublattices, the concrete reading is this: an end of the tree is a coherent way of shrinking a lattice for ever, choosing at each stage a sublattice of index p inside the last, and two such sequences are the same end when they eventually agree. Nothing in the plane corresponds to it, which is the sense in which the object is arithmetic rather than geometric.

What acts on it #

The last piece of the analogy is the group, and naming it says why the tree is canonical rather than a convenient drawing.

Changes of basis of the lattice act on the whole picture: an invertible rational matrix carries sublattices to sublattices and preserves containment and index, so it acts on the tree by graph automorphisms. The group acting is PGL₂ over the p-adic numbers, and the tree is its natural home in exactly the way the hyperbolic plane is the natural home of the real group.

The stabiliser of a vertex is the set of transformations carrying that lattice to a scalar multiple of itself — the integer matrices of the lattice, up to scale — so the tree’s vertices correspond to the conjugates of that stabiliser, which is what a symmetric space is.

The crystallographic reading is smaller and worth having. A lattice’s own automorphism group fixes the root, since it carries the lattice to itself, and it therefore permutes the p + 1 neighbours. Which permutation it gives is a fact about the lattice type: the square lattice’s eight automorphisms act on the three sublattices of index two with two fixed and two exchanged, and the hexagonal lattice’s twelve act on the four of index three with one fixed and three permuted — which is the same factorisation argument that decided which colourings each lattice admits.

Three limits #

It is one prime at a time. Sublattices of index six are not in any of these trees; the general picture is a product over primes, and the object that handles all of them at once is a building rather than a tree. Nothing here computes that.

That restriction is milder than it sounds, because the count factorises exactly as the trees do. The number of sublattices of index n is the sum of the divisors of n, and that function is multiplicative: σ(12) = σ(4)·σ(3) = 7 × 4 = 28, which is the number the enumeration returns at index twelve. The reason is the same one that makes the product of trees the right object. A sublattice of index twelve is the intersection of a sublattice of index four with one of index three, and that pair is unique, because the quotient of a lattice by a sublattice is a finite abelian group and a finite abelian group splits into its prime parts with nothing left over. So there is no interaction between primes to lose. Choosing a sublattice of index twelve is choosing a vertex in the two-tree and a vertex in the three-tree, independently, and the tidy divisor sum of the previous rung is that independence written as arithmetic.

It is rank two. In rank three the analogous object is a two-dimensional complex rather than a graph, its vertices have far more neighbours, and the tidy statement one neighbour nearer the root fails. The tree is a rank-two phenomenon in the same way that the neatness of the Euler relation for plane nets is a two-dimensional phenomenon.

It says nothing about the metric. Two sublattices at the same tree distance can be a square lattice and a very oblique one, since containment is an arithmetic relation and the lattice types are metric ones.

And it is not a picture of a crystal. A vertex is a whole lattice, not a point of one, and adjacency is containment rather than proximity. Reading the tree as though it were a structure is the one mistake it invites.

What a tree buys that a list does not #

It is fair to ask what the extra structure is for, given that the count was already known.

A tree supports questions a list cannot be asked. Which sublattices lie between two given ones — the answer is the path, and there is exactly one. How far apart are two superlattices of a structure — a distance, rather than a pair of unrelated indices. Which sublattices of index p^k are “generic” and which are scaled copies of shallower ones — the levels answer it directly, where the divisor sum cannot.

There is also a practical version. Enumerating the small superlattices of a structure, which is what a search for an ordered phase or a modulated one has to do, is a walk outward in this tree; doing it as a loop over indices with a Hermite enumeration inside re-derives the same lattices many times over, once for each way their index factorises. The tree visits each exactly once, because each is a vertex.

And it changes what a sublattice is. A list makes a sublattice an item; a tree makes it a place, with neighbours and a distance and a direction away from the root. That reframing is what the essays around this one are about — an object treated as a set of points, asked a question that ignores where the points are, and answering with more structure than the geometric question had.

No vertex is really the root. The whole lattice sits at the left of the drawing because a drawing has to start somewhere, and dividing out scale is what makes that a matter of presentation rather than of substance. Take any vertex, redraw the tree with that one on the left, and the result is the same picture: every vertex has p + 1 neighbours whatever its distance from wherever the root was put, and exactly one of those neighbours lies back along the path. A vertex therefore carries no information about itself at all — no index, no shape, no distinguishing feature — and everything a vertex has is a relation to other vertices. That is why the two columns of the level table differ at all: one counts sublattices of a given index, which is a property a lattice has on its own, and the other counts vertices at a given distance, which is a relation to a root the tree does not really have. It is the sharpest form of the reframing above: a sublattice is not an item measured against a fixed parent, it is a place, and every place looks like every other.

Where this goes #

The companion essay in this field counts points in a growing region and finds a polynomial; this one counts ways down and finds a tree. Both are answers to how much lattice is there, asked in different directions, and neither is derivable from the other.

The thread these two share runs wider than either: an object that looked like a set of points is being asked questions that have nothing to do with where the points are, and the answers keep being sharper than the geometric ones.