Two moves reach every basis

Reduction is the procedure a crystallographic database runs before it will say whether two reported cells are the same crystal. Two moves, applied until neither applies, and out comes a triple of integers that depends on the lattice and on nothing anybody chose.

Two things about it are usually stated and rarely argued. The first is that it terminates. The second is that the two moves are enough — that no third move is needed, that every one of a lattice’s infinitely many bases is reachable from every other by those two alone. Both are facts about a group with two generators, and both become visible the moment the space of lattice shapes is drawn.

What a change of basis is allowed to be #

A basis of a lattice is a pair of vectors whose integer combinations are exactly the lattice points and nothing else. Passing from one basis to another means writing each new vector as an integer combination of the old ones — an integer matrix — and being able to write the old ones in terms of the new, which is a second integer matrix inverse to the first. Two integer matrices whose product is the identity have determinants that are integers multiplying to one, so each determinant is ±1.

That is the whole constraint. A change of basis is an integer matrix of determinant ±1, and there are infinitely many of them.

A matrix of determinant two is not among them, and the reason is worth stating because the failure is silent. Such a matrix sends the lattice to a sublattice — a genuinely different, coarser lattice keeping one point in two — and every subsequent computation is about that other object. The check is one line and the site’s own machinery refuses the input rather than proceeding.

Two moves, and a word for every matrix #

The two moves of the reduction are particular matrices — $T = \begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$, which sends v to v + u, and $S = \begin{pmatrix}0 & -1\\ 1 & 0\end{pmatrix}$, which sends u to v and v to −u.

Every integer matrix of determinant one is a product of these. That is not an observation about small cases; it is a construction, and the construction is the Euclidean algorithm. Take any such matrix and look at its first column. T added to the top entry a multiple of the bottom one; S exchanges them with a sign. Alternating those two is precisely the division-with-remainder that computes a greatest common divisor, and because the two entries of the column are coprime — their determinant relation forces it — the algorithm ends with a zero. A matrix with a zero in the lower left and determinant one is ±T to some power, and the word is finished.

The relations are as informative as the generation. $S^2$ and $(ST)^3$ are both the inversion $-\mathbf{1}$, and the inversion does nothing to a lattice at all: it sends both basis vectors to their negatives, which is the same basis with both arrows reversed. So on lattices S behaves as an element of order two, ST as an element of order three, and T has no order — repeating it shears the cell further and further and never comes back.

A group generated by an element of order two and an element of order three, with no relation between them beyond those, is as free as such a group can be. That is why the words above have no shortcuts in them: two different words in S and ST really are two different changes of basis, unless one can be turned into the other by using $S^2 = 1$ or $(ST)^3 = 1$. It is the same kind of fact a plane group’s presentation records, about a group that is not a plane group at all.

The consequence worth having is a normal form. Every element can be written as an alternating product — an S, then one or two copies of ST, then an S, and so on — and two such products name the same change of basis only when they are the same product. That is a solution to the word problem for this group, obtained the same way it was obtained for the seventeen: not by comparing matrices, which would be easy here, but by having a canonical spelling that two equal elements are forced to share. It matters because it is the reason the Euclidean walk above cannot be improved on by cleverness. There is no shorter word hiding behind a relation, because there are no relations left to hide behind.

And it says which changes of basis are far apart. Two cells whose words differ by one letter describe lattices whose descriptions are one shear or one swap apart; two whose words share no prefix are as unrelated as two descriptions of one lattice can be. A published cell is a word, and the reduction is the observation that all of those words name the same thing.

The third move, and why it is not a third generator #

Gauss’s reduction as it is actually written has a move the two above do not include: when b comes out negative, change the sign of v and make it positive. That is the matrix $\begin{pmatrix}1 & 0\\ 0 & -1\end{pmatrix}$, its determinant is −1, and neither S nor T nor any product of them can produce it — the determinant of a product is the product of the determinants, and a product of ones is one.

So the changes of basis are not one group but two halves. The determinant-one half is generated by S and T and is what the tiling below is built from. The other half is that half again, each element multiplied by the sign change, and it is the mirror.

Whether the sign change counts as a change of basis at all is a question about what is being classified rather than about arithmetic, and this collection has answered it: a lattice and its mirror image are one lattice, because a grid of points has no handedness — handedness belongs to what is placed on the grid. So the sign change is admitted, and its effect on the picture is to fold the usual fundamental domain in half. The region used here runs from Re τ = 0 to ½ rather than from −½ to ½ for exactly that reason, and the 1,140 spurious isospectral pairs an earlier search produced are what admitting it prevents.

It is a genuinely different decision in three dimensions. There a lattice’s mirror image is again the same lattice, but the space group built on it need not be: eleven pairs of space groups are mirror images that no motion relates, and a convention that folds mirror images together loses exactly those eleven. The same fold, applied one level up, deletes a real distinction. Which is why the fold is stated here rather than assumed, and stated about lattices only.

The region, copied #

Here is the picture the two relations were always describing.

Each change of basis carries the region somewhere else, and the images tile the half-plane exactly. Two copies coincide only when the two matrices differ by −I, which is the one element that does nothing — so the copies are in one-to-one correspondence with the changes of basis, up to that sign.

This is the geometric content of the claim that a fundamental region is a fundamental region. Every lattice has a basis whose point is in the shaded copy, because the copies cover; no lattice has two such bases, because they do not overlap. Reduction is not a convention that happens to work. It is the statement that this tiling exists, carried out one lattice at a time.

Look at where copies meet. Three of them meet at ρ and two at i — which is exactly the order-three element ST and the order-two element S, seen as rotations of the tiling about those two points. The corners of the region are corners because something turns there, and what turns is the extra symmetry those two lattices have. The hexagonal lattice’s twelve symmetries and the square lattice’s eight are the same two numbers again, doubled by the inversion that the picture cannot see.

And the third kind of special point is the one that is not there. Going upwards in the region the cell grows longer and thinner without limit and never arrives anywhere. That missing point is a cusp, and it is T’s doing: T has infinite order, so nothing at the top ever closes up. A lattice near the top is one whose two shortest vectors are wildly different lengths — a chain of points with the neighbouring chains far away — and the region records the fact that there is no limiting shape by having a hole where the limit would be.

There is a family resemblance here to Conway’s accounting for the seventeen. A folded-up wallpaper pattern is a small surface with marked points costing exactly two dollars, and past two the list does not stop — spend more and the answer is hyperbolic and the list is infinite. The region above is such an object: two cone points, of orders two and three, and a cusp. It is hyperbolic, which is why the copies in the picture shrink towards the real axis rather than staying the same size.

How far a lattice has to walk #

Termination now has a short answer and a sharp one.

The claim is not that a lattice’s point starts near the region. It can start anywhere: a badly chosen basis puts it far out along the real axis, in a copy of the region so flattened that it is invisible at any scale where the shaded copy is legible. What is bounded is not the distance but the number of copies crossed, and those two are different quantities in a hyperbolic tiling — which is the whole reason the tiling is drawn.

Each S strictly decreases a, the smaller of the two squared lengths, which is a positive integer and cannot decrease forever. Between two consecutive S moves there is at most one block of T’s, and that block is a single division: the number of copies of u to subtract from v is the quotient. So the reduction’s length is the number of steps in a division chain — a continued fraction — and continued fractions are short. It is the same reason Euclid’s algorithm on two ordinary integers finishes quickly, applied to a pair of vectors.

The short answer, then: reduction terminates because the tiling above is locally finite. Only finitely many copies of the region come near any point, so a lattice’s point can only be finitely far from the shaded copy in the number of moves it takes to get there, however extreme the basis it arrived in.

Two generators in three dimensions, and no normal form #

The claim that the plane’s situation does not carry upwards needs sharpening, because the part that fails is not the part a reader expects.

Two generators are enough in three dimensions as well. The integer matrices of determinant one in three variables are generated by a permutation matrix and a single elementary shear, and the same is true in every dimension — so the generation statement transfers unchanged.

What does not transfer is the relations. In the plane the group is a free product of a group of order two and a group of order three, so a word in the generators has a normal form — an alternating sequence, unique — and every question about a change of basis becomes a question about a string. In three dimensions there is no such decomposition: the relations are numerous, no normal form of that kind exists, and two words can be equal for reasons a rewriting rule does not see.

The tiling picture goes with it. The plane’s fundamental region has copies that tile the half-plane, one per change of basis, meeting three at a corner and two along an edge — a picture whose combinatorics is the presentation. The three-dimensional space of lattice shapes is five-dimensional, its fundamental region is bounded by many more walls, and the pattern of how the copies meet has no short description.

So the honest statement is that three dimensions keeps the generation, loses the presentation, and therefore loses the termination proof. Reduction in three dimensions terminates for a different reason — a strictly decreasing integer quantity, as the plane’s does — and not because a word can be shortened.

The subgroups the moduli region hides #

There is one more piece of structure in the same group, this collection uses it elsewhere, and naming it here connects two essays that look unrelated.

Take the matrices congruent to the identity modulo some N. They form a subgroup — a congruence subgroup — of finite index in the whole group, and the index is computable from N by a product over its prime factors.

That subgroup is precisely what the reduction-modulo-three argument is about. The lemma there says a finite group of integer matrices meets the congruence subgroup only in the identity, for N ≥ 3 — which in this essay’s vocabulary says that no non-trivial finite subgroup fixes a vertex of the tiling in a particular way, and the finiteness of the classification follows.

The two essays therefore describe one object from opposite ends. This one uses the group’s generators and relations to prove that reduction terminates; that one uses its congruence subgroups to prove that the classification is finite. The generators, the relations, the region, the tiling and the congruence subgroups are five descriptions of the same group, and each of this collection’s arguments reaches for whichever is shortest.

What this does not settle #

It is a proof about shapes, not about a search. Nothing above finds the shortest vector of a lattice by looking for it. The reduction arrives at a form with 0 ≤ b ≤ a ≤ c, and then a is the shortest squared length, because any other lattice vector is a combination whose value the inequalities bound from below. The order matters: reduction is not a search that has been proved to succeed, it is a normalisation whose output happens to answer the question. In higher dimensions the two come apart, and the shortest vector becomes genuinely hard while a reduced basis stays cheap.

It is a proof about the plane, and not for the reason usually given. The thing that fails one dimension up is not the count of generators — the section above measures that and finds two enough there as well — but the relations, and with them the normal form that made the plane’s termination a statement about strings. The shape of a three-dimensional lattice needs five numbers rather than one, its fundamental region is bounded by many more walls than three, and no picture of the copies is available to argue from. Niggli’s reduction is the procedure that replaces Gauss’s there, and its termination is proved by exhibiting a quantity that decreases rather than by drawing anything. It is checked in this collection the only way it can be: scramble a lattice’s basis by a random change of basis, reduce, and require the same six numbers back.

That difference is worth holding on to, because “the argument does not generalise” is usually said about the wrong half. Generation is cheap and survives: an elementary shear and a permutation generate the determinant-one matrices in any number of variables, so a change of basis is still a word in two letters however many axes there are. What does not survive is that the word can be brought to a canonical form by a local rule. In the plane a reduction is a rewriting: read the word, cancel what cancels, and what is left is the unique alternating sequence. In space a word can be equal to a much shorter one for a reason no rewriting rule sees, so the length of the word says nothing about how far the basis has to travel, and the proof has to fall back on a decreasing integer.

And the two moves are a claim about a group, not about an algorithm. Nothing above says that the shortest word is the one a reduction finds, or that a reduction finds a short word at all. It says that every change of basis is a word in S and T, and that the reduction’s own sequence of moves is one such word — which is enough for termination and not enough for efficiency. The two questions come apart badly in higher dimensions, where a reduced basis is cheap and a shortest one is not, and they come apart even here for a lattice whose two axes differ by a factor of a million: the walk is short in copies of the region crossed and long in the arithmetic each step costs.

It says nothing about lattices with contents. Everything here is about the grid. A crystal is a grid with atoms on it, and the atoms are what the symmetry statements in this collection are ultimately about; two lattices with the same reduced form may carry structures with nothing in common. What reduction settles is whether two cells describe one lattice, which is the first of the two questions a database has to answer and not the second.

And it settles nothing about how hard reduction is in general. Finding a short basis in a high-dimensional lattice is a computation whose cost is the subject of a different field entirely; this collection names it and does not derive it. In two dimensions the answer is a continued fraction and the question does not arise.

One consequence is practical enough to be worth stating plainly. A structure reported in a badly chosen cell — a long thin cell, a cell whose vectors are nearly parallel, a cell that some diffractometer’s indexing routine produced and nobody looked at — is not a problem to be dealt with by judgement. It is a point somewhere in the tiling, and the number of moves back is the length of a continued fraction. The worst case among all the bases with entries up to three is five moves. There is no cell so eccentric that the walk home is long.

What is left is a fact worth carrying back to every essay here that reduces a cell. The reduced form is not the tidiest of a lattice’s descriptions or the conventional one. It is the lattice’s own address in a space that exists, whose copies tile the plane, and which a lattice reaches in a handful of steps whatever basis it arrived wearing.