Reduction modulo three

The previous rung computed a bound: the order of a finite group of integer matrices divides 24 in the plane and 48 in space, so the classification cannot run away. The bound is exact, it is short to compute, and it presupposes the theorem it comes from.

There is a second argument for the same finiteness, and it is stranger. It computes no bound, it uses no geometry, and it takes one line.

Reduce every matrix modulo three.

Integer matrices modulo three form a finite group — 48 elements in two dimensions, 11,232 in three — and if reduction carries a finite group of integer matrices into it without collapsing anything, then that group has at most 48 elements. Finiteness, from nothing but counting the residues.

Why the collapse cannot happen #

The claim is that the kernel is torsion-free: a matrix congruent to the identity modulo three, other than the identity itself, has infinite order. If that holds, no two distinct operations of a finite group can have the same reduction — their quotient would be a non-identity kernel element of finite order — and injectivity follows.

The argument is a computation with a leading term. Write such a matrix as

A = I + 3ᵏ B, with B an integer matrix not divisible by three,

where k is as large as it can be, so B carries whatever is left. Raise A to the power p and expand: the first two terms are the identity and p·3ᵏB, and every later term carries at least 3²ᵏ. If A has order p then the sum must be exactly the identity, so p·3ᵏB has to be cancelled by terms of higher order in three — and it cannot be, because it is not divisible by 3^(k+1) unless p is. When p is three, the next term is examined and the same obstruction appears one level up.

The whole argument is that the leading correction cannot vanish. Nothing about lattices enters, and the same proof works for any modulus of at least three.

Modulo two, and the matrix that refutes it #

The hypothesis m ≥ 3 looks like the kind of technical condition that could be an artefact of a proof. It is not, and the counterexample is the most familiar matrix in crystallography.

Minus the identity is congruent to the identity modulo two, and it has order two. It is the inversion centre — the operation eleven of the thirty-two classes contain, the operation Friedel’s law forces onto every diffraction pattern, and a symmetry of every lattice that exists. So the kernel of reduction modulo two contains an element of order two, the argument collapses immediately, and any conclusion drawn from it would have been drawn about every centrosymmetric crystal there is.

Eight of the thirteen arithmetic classes collapse modulo two, and which eight is not arbitrary.

That is the reason the figure has two columns rather than one. A check that reports “no collisions” is worth nothing until it has been shown capable of reporting a collision, and the mod-two column is that demonstration on the same thirteen groups with the same code.

Which classes survive, and what the kernel is made of #

The matrices congruent to the identity modulo two are those whose off-diagonal entries are even and whose diagonal entries are odd. Among the finite groups here, that comes to a very short list: the identity, minus the identity, and the two matrices with one sign flipped — the diagonal sign matrices, and nothing else.

So the amount a class loses modulo two is exactly how much of it is diagonal signs.

2mmp is the extreme case: its four operations are precisely the four diagonal sign matrices, so all four reduce to the identity and the whole group becomes trivial modulo two. A finiteness argument built on the modulus two would, in that case, be deducing a property of a group of order four from a group of order one.

The five survivors are the classes with no diagonal sign but the identity. They are the trivial class, the centred mirror — whose reflection is the off-diagonal matrix that swaps the two axes rather than negating one — and the three classes built on a three-fold rotation, whose matrices have odd off-diagonal entries and are nowhere near the identity modulo anything.

That is a neat illustration of what makes the modulus matter. Modulo two, the sign of an entry is invisible, and half of crystallography is about signs: an inversion, a reflection, a two-fold axis. Modulo three a sign is perfectly visible — 1 and −1 are 1 and 2 — and nothing is lost.

A search, beside a proof #

The lemma is a theorem and does not need checking. An implementation of it does, and a proof does not catch a program that is looking in the wrong place.

The mod-two column is again what makes the mod-three column mean anything. And the result is stated as what it is: evidence about a box, not a proof about GL(2,ℤ), which is what the lemma is for. A search over a finite box cannot establish a statement about infinitely many matrices, and reporting it as though it could would be exactly the kind of overclaiming this site’s figure rules forbid.

The examples the mod-two search turns up are worth a look on their own. Matrices like [−7, −8; 6, 7] have order two, entries far from the identity, and are congruent to the identity modulo two — so the failure of the mod-two argument is not a single exceptional matrix but a whole family, growing with the box.

The residue group permits one order too many #

There is a second thing the target group can be asked, and the answer is a small surprise.

Every operation of a finite group of integer matrices lands in GL(2, ℤ/3) with its order intact, so every rotation order a plane lattice permits must occur as an element order in that group of forty-eight matrices. Enumerating them: 1, 2, 3, 4, 6 — and 8.

The first five are exactly the orders a lattice permits. The sixth is not, and it is the same eight that divides Minkowski’s bound and occurs nowhere: twelve of the forty-eight matrices over the integers modulo three have order eight, and no integer matrix of order eight exists at all.

That is the residue argument’s honest limit, in one number. It carries a faithful copy of the group into a finite target, which proves finiteness; the target then has room for one order the original never had, so nothing about which orders occur can be read back out of it. The order-eight elements over the residues are not shadows of anything — they are genuine elements of a genuine group, and the map runs one way.

The trace argument is what settles the orders, and it is unrelated: an integer matrix has an integer trace, a rotation through 2π/n has trace 2cos(2π/n), and the only integers in that range are −2, −1, 0, 1 and 2. Residues never enter. Two arguments, two questions, and the temptation to expect one tool to answer both is exactly what the eight is here to spoil.

What the lemma bounds, and how badly #

Injectivity into a finite group gives a bound for free: the order of a finite group of integer matrices divides the order of the group it embeds into. In two dimensions that is |GL(2, ℤ/3)| = (9 − 1)(9 − 3) = 48.

The lemma’s bound is worse than the formula’s, and in three dimensions it is far worse. |GL(3, ℤ/3)| is 11,232, which factors as 2⁵ · 3³ · 13. The 13 in there is the giveaway: no crystallographic point group has an order divisible by thirteen, and no argument that produces a bound with such a factor is paying attention to the objects it bounds. What the lemma is good at is proving that the answer is finite in the first place, in any dimension, in a line.

A larger modulus does not help and a different one does not hurt. The lemma holds for any m ≥ 3, so the reduction could equally be done modulo four, where the target group has 96 elements in the plane; modulo five, where it has 480. Bigger targets give worse bounds and the same finiteness. Four is sometimes preferred in the literature because it makes the target a group of order a power of two, which is convenient for a different argument; three is the smallest that works, and being the smallest is the whole content of the previous section.

So the two halves have a clean division of labour. The lemma answers why finite: because a faithful copy of the group sits inside a finite group of residues. The formula answers how large: because the order divides an explicit product over primes. Neither is a substitute for the other, and the classification needs both — the first to know the search terminates, the second to know how short the answer will be.

What is checked here, and over what #

The injectivity check is exhaustive in two dimensions. It runs over the thirteen arithmetic classes, which is every finite subgroup of GL(2,ℤ) up to conjugacy — and conjugacy is the right equivalence, since reduction commutes with conjugation by a matrix that is invertible modulo three, which every unimodular matrix is. So the check is not a sample: it is the whole statement in that dimension.

In three dimensions it is not run at all. This site enumerates fourteen Bravais lattices, thirty-two crystal classes and forty-five space groups, and does not enumerate the seventy-three arithmetic classes; the check that would correspond to the one above is therefore not available and is not claimed.

The box search is about the box. Nine in each entry, unimodular, congruent to the identity. Thirty-seven matrices in the mod-three case and two hundred and ninety-two in the mod-two case, which is the honest count of what was looked at.

Nothing here is about the rotation orders. The lemma bounds group orders and says nothing about whether a five-fold rotation exists — that is the crystallographic restriction, and it comes from a trace being an integer rather than from any residue argument. The two are frequently confused because both begin “integer matrices cannot…”.

Who found it, and when #

Minkowski proved both halves in the 1880s, and the reduction argument is the one that carries his name as a lemma. It appears in Zur Theorie der positiven quadratischen Formen (1887), where the subject is quadratic forms and the matrix groups are again the tool rather than the object.

The lemma generalises further than it is usually stated. Reduction modulo any m ≥ 3 works, and the modulus 4 is sometimes preferred because it makes the two-dimensional target group a 2-group. Serre’s Cours d’arithmétique gives the clean modern proof in a paragraph, and it is the version the argument above follows.

The crystallographic reading came later and from a different direction. Fedorov, Schoenflies and Barlow enumerated the two hundred and thirty space groups in the 1890s by exhaustion, before anybody had a theorem saying such an exhaustion must terminate — three people, working independently, checking a list against a bound that did not yet exist in the literature they were reading. That the three answers agreed is the reason anyone believed the count, and the theoretical guarantee arrived afterwards.

The lemma has no physical content, and that is worth saying plainly. Nothing about a crystal is congruent to anything modulo three. What the argument is about is the description — the integer matrices that a lattice basis turns the symmetries into — and it works because that description is arithmetic. A reader looking for the crystallographic meaning of the modulus will not find one, in the same way that there is no physical meaning to the choice of cell or of origin. The theorem is about the representation, and the representation is exact, so the theorem is about the crystal only in the sense that an exact description can be reasoned about instead of the thing.

That is, in miniature, the argument the whole site runs on. A pattern’s symmetry is decidable because the description is integral; the description is integral because the lattice makes it so; and once it is, questions about symmetry become questions about integers, where a residue argument, a trace argument or a divisibility can settle in one line what no amount of looking at the pattern will.

The pattern is not unusual in this subject. The seventeen were enumerated by Fedorov before the classification proof was written down; the thirty-two classes were arrived at by Hessel in 1830 and ignored for decades before Gadolin rediscovered them. A finished list precedes the argument that it is finished, usually by a generation.

The lemma’s proof, which is a paragraph #

The essay treats the lemma as a theorem to be used rather than shown, and the argument is short enough to give — and giving it is what makes the failure at two something to be seen rather than reported.

Suppose M is an integer matrix of finite order, congruent to the identity modulo m, and not the identity. Write

$$M = I + m^{k}A,$$

with k chosen as large as possible, so A is an integer matrix not divisible by m. Let p be a prime dividing the order of M, and replace M by a power of itself so that its order is exactly p. Then M^p = I, and expanding the binomial gives

$$I = I + p\,m^{k}A + \binom{p}{2} m^{2k}A^{2} + \cdots$$

so that p m^k A is divisible by m²ᵏ together with every later term. Divide through by m^k and look at the result modulo m. Every term after the first carries at least mᵏ and vanishes, leaving pA ≡ 0.

If p does not divide m this says A ≡ 0 (mod m), contradicting the choice of k. If p does divide m, the second term needs closer attention, and for m ≥ 3 the extra powers of m in m²ᵏ beat the single factor of p in the binomial coefficient. Either way there is no such M, and the reduction is injective.

Where the argument breaks at two #

The failure at m = 2 is visible in the same expansion, at the one place the inequality was needed.

Take p = 2 and m = 2. The second term of the binomial is $\binom{2}{2} m^{2k}A^{2} = m^{2k}A^{2}$, and the first is $2\,m^{k}A = m^{k+1}A$. Those two carry the same power of m when k = 1, so they can cancel each other instead of the first dominating — and that is exactly what the counterexample does.

−I is congruent to I modulo two, since −I = I + 2(−I). It has order two. And the two terms of the expansion are 2·2·(−I) = −4I and 4I, which sum to zero: (−I)² = I, with no contradiction anywhere.

So the inversion is not an unlucky example that happens to break a good argument. It is the case the argument’s inequality was written to exclude, appearing at the smallest modulus where the inequality fails, and it is why the lemma is stated for m ≥ 3 rather than for every modulus with the case m = 2 left as an exercise.

Where this ladder goes #

This anchor has two rungs and they are the same theorem taken from opposite ends: a bound that is sharp and needs the theory, and a residue argument that is crude and needs nothing.

What they secure is not one of the site’s counts but all of them, and the place to see what that buys is any essay here that ends in a number. Five lattices, thirteen ways to hold one, seventeen groups, thirty-two classes, fourteen Bravais lattices — every one of those enumerations is a search that was allowed to stop, and this is the permission.