How many ways there are to thin a lattice

Take the square lattice and keep half of its points — not any half, but a half that is itself a lattice. There are exactly three ways to do it.

Keep every second column, and the result is a lattice with a cell twice as wide. Keep every second row, and it is twice as tall. Or keep the points whose coordinates add to an even number, and the result is the square lattice turned through forty-five degrees and shrunk: the same shape as the original, at a different size and orientation.

Three, and no more. That is a small enough number to check by hand and it is the first case of a count that runs a long way: the number of sublattices of index n in the plane is the sum of the divisors of n, and the number in space is a longer sum over the same kind of data. Both are theorems with finite proofs, and both are enumerated here rather than quoted.

What a sublattice is, exactly #

A sublattice is a subset of a lattice that is a lattice in its own right: closed under addition and subtraction, and discrete. Every one of them is the set of integer combinations of some basis, and writing that basis as the columns of a matrix H turns a geometric object into an integer matrix.

The index is then the determinant of H, up to sign. It is simultaneously three things: the number of parent points per sublattice point, the ratio of the two cells’ areas, and the number of cosets the sublattice has in the parent. That those three coincide is the content of the word, and the same three-way identity turns up wherever an index does.

The trouble with H is that it is not unique. Multiplying it on the right by any integer matrix of determinant ±1 gives a different basis for the same sublattice, and there are infinitely many such matrices — which is exactly the ambiguity a cell always has, one level down.

Hermite normal form: one name each #

The ambiguity has a standard resolution and it is the reason a count is possible at all. Every class of matrices under right multiplication by GL(2, ℤ) contains exactly one matrix that is upper triangular, with positive diagonal entries, and with each off-diagonal entry reduced to lie between zero and the diagonal entry below it. That is the Hermite normal form, and it is a canonical name: one form per sublattice, no duplicates and nothing missed.

So enumerating the sublattices of index n is enumerating the Hermite forms of determinant n, and in the plane that is a short loop. Pick a divisor a of n, set d = n/a, and let the off-diagonal entry b run from 0 to a − 1. Each choice is one sublattice.

Counting the choices gives the answer immediately: for each divisor a there are a of them, so the total is the sum of the divisors of n.

Why one index has several sublattices #

The count is not one, and the reason is worth sitting with, because a great deal of crystallography turns on it.

A sublattice of index n is a way of throwing away all but one point in n, and the choice is which points. Doubling along a and doubling along b are different choices; so is the centred one. They agree on how many points survive and disagree on which, and nothing about the index distinguishes them.

That is why a superstructure has to be specified rather than named. A crystal whose cell has doubled has not said which doubling it did, and the diffraction pattern is what says: the new reflections appear at half-integer positions along whichever direction the doubling was along. A single number — the multiplication of the cell volume — is not a description.

One point in n, counted rather than believed #

There is a check available on every one of these pictures and it is worth making, because the failure it guards against is the one this site keeps meeting: a well-formed drawing of the wrong thing.

A sublattice of index n keeps one lattice point in n. That is a statement about density, and it can be tested by counting: draw a window, count the parent’s points inside it, count the sublattice’s, and the ratio must be n to within the boundary. The index as a determinant and the index as a density are different calculations on different objects, and every figure here makes both.

Neither test is expensive and neither is decorative. The first would catch a basis written down wrongly; the second would catch a drawing loop that marked the wrong points. Between them there is nothing left for a picture to get wrong except which sublattice was intended, and that is written in the caption.

The same question in space, with a longer answer #

Three dimensions changes the loop and not the method. A Hermite form is upper triangular with three diagonal entries whose product is n and three off-diagonal entries each reduced against the one below it, so the count for a given diagonal (a, d, f) is d·f², and the total is the sum of d·f² over all factorisations n = a·d·f.

That sum has a name in analytic number theory: it is the coefficient of n⁻ˢ in the product ζ(s)·ζ(s−1)·ζ(s−2), and the plane’s answer is the coefficient in ζ(s)·ζ(s−1). The pattern continues — one more zeta factor per dimension — which is the kind of fact that makes the counting look inevitable in retrospect and was not obvious in advance.

Where this site has already used a sublattice, three times, without counting them #

The construction is not new here. It has appeared under three different names, in three different fields, and the arithmetic was the same in each.

Centring. A centred cell is a lattice containing a sublattice: the primitive description and the conventional one differ by an index of two for a C-centred or body-centred cell and four for a face-centred one. The letter on the front of a space-group symbol is the name of a sublattice relation.

Coincidence. The coincidence site lattice of two grains is the intersection of a lattice with a rotated copy of itself, and Σ is its index. There the sublattice arises from an intersection rather than from a construction, but it is the same object and its index is the same quantity.

Klassengleiche subgroups. A plane group can lose symmetry by thinning its lattice, and the choice of which sublattice to thin to is a choice from exactly the list enumerated above. Counting those subgroups means counting sublattices first.

The coincidence case is worth following, because it is the one that arrives from the opposite direction and lands in the same list. Rotate a square lattice by 22.62° against a copy of itself and the two grids share one point in thirteen; those shared points are the coincidence site lattice, and they are a sublattice of index thirteen in each grain. Nothing about that construction writes down a matrix — it intersects two point sets — and yet what comes out is one of the fourteen sublattices of index thirteen this page enumerates. Which one it is can be said exactly: the shared lattice is carried onto itself by the parent’s own quarter-turn, so it is one of the two that are still square.

The last of the three is the one where the counting is load-bearing rather than descriptive, and it is worth being precise about why the two numbers differ. Forty-five of the seventy-four index-two subgroups among the seventeen plane groups are klassengleiche, and there are three sublattices of index two — so the two counts are not the same count. A klassengleiche subgroup is a pair: a sublattice from the list above, together with a decision about which coset representatives of the parent’s operations to keep on it. Neither half constrains the other, so the subgroup count is a product rather than a copy of the sublattice count, and counting sublattices is the first of the two factors rather than the whole answer.

What the count is good for #

The number itself is a bound, and a bound is exactly what a structural problem needs.

A crystal that orders — two atom types on one site sorting themselves into a pattern — produces a superstructure whose cell is some multiple of the parent’s. The multiple comes off the diffraction pattern easily. Which sublattice it is does not, and the list of candidates is finite and short: seven at index four in the plane, thirty-five in space. That list can be tested one at a time against the observed reflections, and a search over a finite list is a different kind of problem from a search over a family.

The same bound limits how many superstructures a given ordering can produce, which is a count of antiphase domains: a structure whose cell has doubled has two ways of being in step with itself, and the number of translational domain states is the index. Sublattice arithmetic supplies the count and the physics supplies which one happens.

There is a reciprocal-space reading of the same fact, and it is the one an experiment meets first. Thinning a lattice in real space thickens it in reciprocal space by the same index: a sublattice of index n has a reciprocal lattice n times as dense, so its diffraction pattern has n times as many reflections. The extra ones are the superlattice reflections, they are usually weak — their intensity comes from the difference between the atoms that ordered rather than from the atoms themselves — and their positions say which of the sublattices on the list was taken. That is the whole of superstructure determination in three sentences, and every one of them is a statement about an index.

The weakness matters more than it sounds. Superlattice reflections can be a hundredth of the intensity of the main ones, and what a powder pattern loses is exactly the sort of information that distinguishes one candidate sublattice from another — so ordering is routinely missed in a powder measurement and found in a single-crystal one. The list of candidates is finite either way; what varies is whether the measurement can choose between them.

Who worked this out, and what for #

Charles Hermite introduced the normal form in 1851, for a question about quadratic forms rather than about lattices — the point of it was to give integer matrices a canonical representative so that two could be compared.

The counting function is older in spirit and younger in statement: the identity that the number of sublattices of index n in ℤᵈ is the coefficient in a product of zeta functions is a piece of nineteenth-century arithmetic that became crystallographically useful only when superstructures needed enumerating in the twentieth. Both halves — the canonical form and the count — arrived long before anybody had a diffraction pattern to apply them to.

There is a lesson about conventions in that history. Crystallography’s own name for a sublattice relation is a centring letter, and its own name for the choice is which cell to draw — both of which make the relation sound like a matter of description rather than of arithmetic. The bigger cell wins by convention and the smaller one is still there underneath, and calling the relation by its mathematical name makes the count available where the crystallographic name does not.

The computation here is a small one and it is worth saying how small: enumerating every sublattice of index twelve in three dimensions is 455 matrices, each of six entries. The whole census up to index twelve, in both dimensions, is under a millisecond. What makes it useful is not that it is hard but that it is complete — a list with nothing missing is a different object from a handful of examples.

Where the exactness stops #

Two limits, both real.

The sublattices counted here are not classified. Two of the three at index two — doubling along a and doubling along b — are the same object as far as the square lattice’s symmetry is concerned, since a quarter-turn carries one onto the other. The list above counts them separately, because it counts sublattices and not classes of them. Counting classes means quotienting by the parent’s point group, which is a smaller number and a different question, and the essays that need it say which they mean.

And nothing here says which sublattices are worth having. Of the three at index two, one is square and two are not; of the seven at index four, only some keep any symmetry at all. A sublattice with no symmetry is a perfectly good sublattice and a poor description of a crystal, and separating the two is the next rung.

What kind of quotient, not merely how large #

A sublattice of index n is counted here by its Hermite form, which is a canonical name. There is a second canonical form carrying different information, and it answers a question the count does not: what shape the thinning has.

Reduce the same integer matrix on both sides — row operations and column operations, both of determinant ±1 — and it becomes diagonal, with each diagonal entry dividing the next. That is the Smith normal form, and its diagonal entries describe the quotient group of the parent lattice by the sublattice: index four can come out as ℤ/4 or as ℤ/2 × ℤ/2, and the two are genuinely different objects with the same index.

The difference is visible in the pictures. A sublattice with quotient ℤ/4 is reached by four steps in one direction — a cell four times as long and the same width. One with quotient ℤ/2 × ℤ/2 doubles both axes, and the parent’s points fall into four classes no single translation cycles through. Same index, same number of discarded points, different structure.

Where it matters is in counting domains. A superstructure that orders on a sublattice can nucleate in several places at once, and two regions ordering on the same sublattice but offset by a parent translation meet at an antiphase boundary. How many distinct offsets there are is the order of the quotient group, and how they compose — whether two boundaries can annihilate, and which pairs — is the group’s structure. ℤ/4 gives a cyclic ladder of four domains; ℤ/2 × ℤ/2 gives four domains no two steps of which are the same step.

So the index counts the domains and the Smith form says how they are related, and only the second predicts what happens when two of them meet.

The same count, in reciprocal space #

There is a symmetry in this arithmetic worth naming, because it means the enumeration is doing double duty.

A sublattice of a lattice corresponds, under duality, to a superlattice of its dual: thinning a lattice by a factor of n makes its dual n times denser, since the two are related by inversion. So the sublattices of index n of L are in one-to-one correspondence with the lattices containing L* at index n, by the same Hermite forms transposed.

That is why the count appears in two places in a diffraction experiment that look unconnected. In real space it bounds how many superstructures a given ordering can produce. In reciprocal space it counts the ways the extra reflections can be arranged — because a superstructure whose real-space cell is a sublattice of index n has a reciprocal lattice n times denser, and the possible arrangements of superlattice reflections are the possible superlattices of the dual.

Neither reading needs the other, and having both is the check. A superstructure proposed from real-space reasoning and a set of extra reflections observed in a pattern must name the same Hermite form, and a disagreement is a statement that one of the two was misread — most often the reflections, since a weak superlattice peak is easy to miss and a missing peak makes the observed arrangement look like a different sublattice of larger index.

Both readings share one property worth naming: the enumeration is a list, not a formula with a list attached. Every statement above was checked by writing the sublattices down and testing them, and the closed-form count is what the list is compared against rather than what produced it. That is the arrangement this collection prefers wherever a count has a closed form, and it is the only arrangement in which a wrong closed form can be caught.

Where the ladder goes next #

The question the count leaves open is which of the sublattices at a given index have the same symmetry as their parent, and the answer turns out to have nothing to do with crystallography: a sublattice of the square lattice is itself square exactly when its index is a sum of two squares, which is Fermat’s theorem arriving in a question about patterns.