Forgetting a group in three dimensions

The argument this site rests on has four steps and none of them mentions a dimension. A symmetry of a lattice is a matrix that maps the lattice to itself; written in the lattice’s own basis that matrix has integer entries; a translation compatible with it has a rational one with a small denominator; and so deciding whether a point set has a given symmetry is integer arithmetic rather than a comparison against a tolerance.

Every one of those sentences is as true of a 3×3 matrix as of a 2×2 one.

So the round trip runs in space, and this essay is about what had to be built to make it run and what it cost. Three things were genuinely harder than translating the two-dimensional code, and the first is the one worth the most attention.

The holohedries are not typed in #

In the plane there are five lattice types and each has a point group small enough to write out: two operations for the oblique lattice, four for the rectangular and the rhombic, eight for the square, twelve for the hexagonal. The plane’s were written out here for a long time — a table of thirty-one matrices, checked by eye.

In space there are seven, the largest has forty-eight elements, and typing out a hundred and thirty-four 3×3 integer matrices correctly is not a thing anybody should attempt. More to the point, a table is the wrong object. What a holohedry is is the answer to a question — which integer matrices preserve this lattice’s metric? — and asking the question is both shorter than the table and worth more.

The metric of a lattice is the matrix of dot products of its basis vectors. A symmetry sends each basis vector to a lattice vector of the same length, with the same angles to the others, so finding the symmetries means finding every integer vector of the right squared length and then every triple of them with the right inner products. That is a finite search, and the bound on it can be made exact rather than generous: if a vector has squared length N under the form, then its i-th coordinate satisfies x² ≤ N·(G⁻¹)ᵢᵢ, which is Cauchy–Schwarz applied to the form itself.

Two things follow immediately from doing it this way, and both are worth more than the tidiness.

The first is that the fourteen Bravais lattices become countable rather than quotable. If the machinery reports that a C-centred cubic lattice has sixteen automorphisms rather than forty-eight, then the sentence “there is no C-centred cubic lattice” stops being a fact to memorise.

The second is a check that cannot be faked. A bounded search fails silently: it returns a group that is correct as far as it went. So every holohedry here is required to come out at the order its system is defined by — two for triclinic, forty-eight for cubic — and the requirement is checked every time the figure is drawn. If the bound were wrong, the cubic answer would be some divisor of forty-eight and the figure would refuse rather than appear. A gate that only checks the answers it can already predict is a gate that checks nothing, but this one is checking the search, which is exactly the thing that could quietly be wrong.

The metrics themselves need one piece of care. They are chosen generic, meaning no accidental equality holds among their entries, and the reason is that an accident produces a lattice with more symmetry than its system has. A tetragonal metric with c equal to a is a cubic lattice; a monoclinic one with β at ninety degrees is orthorhombic. One accident of that kind was in fact written into an early version of this code and caught by the assertion: with a² = 9, b² = 16 and c² = 25, two of the primitive vectors of the body-centred orthorhombic cell come out orthogonal, because 9 + 16 = 25. The lattice was still orthorhombic and the count still came out at eight, so nothing failed — but the relation is a property of those three numbers rather than of an orthorhombic lattice, and it would have made a later figure drawn from that metric wrong in a way nothing measured. The c² is now 36.

A metric is a small object with a lot in it #

It is worth pausing on the metric, because it carries more than it looks and this field will lean on it repeatedly.

The metric is six numbers: three squared lengths and three dot products, arranged as a symmetric 3×3 matrix. That is all the geometry a lattice has. Every length, every angle, every distance between lattice points and every volume is recoverable from those six numbers, and two lattices with the same metric in some basis are the same lattice.

What makes it usable here is that the six numbers can be integers. A cubic cell of side three has the metric with nines on the diagonal and zeros elsewhere. A hexagonal one with a² = 8 has −4 in the a·b position, because the angle is 120° and the cosine is exactly −1/2. Rational cosines are what keep the arithmetic exact — a cell with a 100° angle would have an irrational entry and every comparison would become a tolerance, which is precisely the situation this site exists to avoid.

The angles being rational rather than realistic is a genuine departure from any real crystal and it costs nothing, because the classification does not depend on the values. A monoclinic lattice with β = arccos(−1/8) has the same symmetry as one with β = 100.3°, and the point of the generic choice is only that no additional symmetry sneaks in. That is checked rather than assumed, which is the assertion above.

There is a converse worth noticing while the metric is in view. Because symmetry here is decided against a stated metric, a crystal whose metric is accidentally more symmetric than its structure — a monoclinic cell that happens to measure β = 90.00° — will present a lattice with more symmetry than the crystal has. That gap between the metric symmetry and the actual symmetry is a real and common difficulty in structure determination, and it is the three-dimensional version of what this site’s near-symmetry essay is about. The machinery here has nothing to say about it, because it is a question about measurement error and this machinery has none.

The detector, and the size of the problem #

The second half of the round trip is the detector, and its structure is the plane’s: for each linear part the lattice allows, and for each candidate translation, test whether the operation maps the point set to itself. What makes it complete rather than heuristic is that a symmetry must send some point to some point, so the differences between points exhaust the candidate translations.

What changes in space is the size. The largest group here has 192 operations in its conventional cell, and its orbit of a three-point motif is 576 points; forty-eight linear parts against 576 candidate translations each is nearly twenty-eight thousand operations to test, and each test walks the whole point set.

The fix is to find the pure translations first. They form a subgroup, and any operation that works can be composed with any of them to give another that works — so candidates need only be tested one per coset, and a face-centred lattice has four translations in the cell, which divides the work by four for free.

That number matters more than it looks. A check that takes a minute gets run when somebody remembers; a check that takes an eighth of a second runs inside the figure that is being drawn, every time, and a figure that fails it is never seen. The whole value of this site’s habit rests on the check being cheap enough to be unavoidable.

What it refuses, and the oldest finding on this site #

The interesting direction of the round trip is not the missing one. A pattern that lacks a symmetry it was supposed to have tends to look wrong, and a reader would catch it. A pattern with symmetries it was never given looks perfect, and it is a picture of a different group from the one in the caption.

This collection found that in the plane first, and gave it an essay: the motif must be a comma, because the orbit of a single dot under p1 acquires an inversion centre at the midpoint between the dot and each of its own lattice translates. A single point is too symmetric to illustrate the group with no symmetry at all.

The same argument holds in space, for the same reason, and it was rediscovered here by the machinery refusing to draw something.

There is a second and cruder way to spoil a motif, and the detector catches it too.

Every diagram in this field therefore verifies with a three-point asymmetric motif, whatever it goes on to draw. Some of the plan diagrams then plot the orbit of one point, because that is what the Tables print and because three points times forty-eight operations is an unreadable thicket — but the verification uses the comma, the figure’s description says which was used for what, and the two numbers both appear.

The commoner failure in space is worse than in the plane, and it is worth saying why. In the plane, a determined reader can trace a wallpaper pattern’s operations and satisfy themselves that the caption is right. Here nobody can. A space-group diagram is a projection with heights printed as numbers, and checking that a set of twenty-four points really has exactly eight symmetries and not sixteen is not something a person does by looking. The picture and its caption are separated by an argument that cannot be made visually, in either direction — which is the strongest case this site has yet had for computing what its figures claim.

Where the exactness stops #

Four limits, stated plainly, because the value of an exact method is entirely in knowing its edge.

The point sets are finite and periodic. What the detector examines is the contents of one cell, modulo the lattice. That is the right object — a space group modulo its translations is finite and everything else is not — but it means the machinery decides nothing about anything aperiodic. A quasicrystal has no lattice and there is nothing here that applies to it. The aperiodic essays say so where they use a measurement rather than a decision, and they are measurements.

The lattice type is an input, not an output. The detector is told which of the seven metrics it is working against and searches the matrices that preserve it. Handed a point set on a cubic lattice but told it is orthorhombic, it will return the eight operations an orthorhombic lattice permits and miss the other forty. That is not a bug — it is what “the symmetries compatible with this lattice” means — but it does mean the answer is conditional on a stated holohedry, and every figure states its own.

Nothing here derives the 230. Six arithmetic classes are enumerated completely, which is a real computation and a small fraction of the classification. The step from those to the full list is a question about equivalence rather than about search, and this field does not take it.

The three-dimensional round trip is about the geometry, not the chemistry. It decides whether a set of points has a symmetry. It says nothing about whether atoms would sit there, what holds them there, or what the structure would do. A crystal that a space group permits may be impossible for a dozen reasons this machinery cannot see.

The input that could be removed #

Of the four limits above, the second is the one that separates this machinery from what an experiment does, and it is worth saying what removing it would take, because the pieces are all in this collection already.

The detector is told which lattice type it is working against. An experiment is not: it measures a set of positions and has to decide the lattice from them. The two steps of doing that are both here. Take the differences between points and find the ones that recur — a lattice, if the set is periodic. Then reduce that lattice’s basis and read its type off the reduced metric, which is what the reduced cell is for.

Chaining them would make the round trip fully self-contained: point set in, lattice out, holohedry out, operations out, group out, and no input but the points. What stops it is not the arithmetic but the tolerance, and it stops in exactly one place. Deciding which differences recur is exact for a generated point set and a judgement for a measured one, so the chained version would be exact here and would not transfer — which is the same boundary the tolerance essay draws, arriving one step earlier than usual.

That is why the input stays an input. Supplying the lattice type keeps the whole detector exact; deriving it would make one step a threshold and leave the rest exact, which is a worse arrangement than it sounds, because a single threshold in a chain makes every downstream claim conditional on it.

Nothing in it mentions three either #

The essay opens by observing that the argument’s four steps mention no dimension, and the observation runs further than the plane and space.

The round trip needs three things: a lattice, a finite list of integer matrices preserving it, and a way to solve for translation parts. All three exist in any dimension. So the machinery would run in four, and the aperiodic essays are where it would be wanted — a modulated structure is periodic in four dimensions and an icosahedral quasicrystal in six, and neither has a detector, which those essays record as their honest gap.

What would have to be built is the holohedry search, and its cost is the reason it has not been. The search here tests integer matrices preserving a metric, bounded by the requirement that each column have the right length — cheap in three dimensions, where the answer is at most forty-eight matrices. In four dimensions the Bravais classes number sixty-four rather than fourteen and the largest holohedry is far larger, so the same search is a different computation rather than the same one with an index changed.

That is a limit worth stating as a cost rather than as a principle. Nothing about the argument fails above three dimensions; what fails is the assumption that the finite list at the heart of it is small enough to enumerate without thinking about it.

What it made possible #

Set against those limits, the thing that changed is concrete. Until the detector reached three dimensions, every claim made here about space groups was a claim about arithmetic that happened in some other dimension — the restriction in three dimensions is a fact about cyclotomic polynomials and matrix orders, exact and dimension-free, and it was as far as the machinery reached.

Now a space-group diagram is checked the same way a wallpaper diagram has always been. The symmetry elements drawn on a plan are computed by solving for each operation’s fixed set rather than placed by hand. The extinction conditions come out of a sum over the group’s operations and agree with the International Tables on every group tested, which is a second route to the same symmetry sharing nothing with the first but the operations.

And the enumeration of a class is only possible because the closure can be run and tested: an assignment of translations that does not correspond to a real group produces a closure that never terminates, and detecting that is how the invalid assignments are filtered out. That is the next essay, and the one after it does it in full for a class with ten answers.