A group in four letters

A symmetry group on this site is a set of matrices with translations attached, acting on fractional coordinates. That description has carried every argument here: the detector rediscovers it from a point set, the classification sorts it, and every figure is drawn by applying it to a motif. It is concrete, it is checkable, and it brings the plane along with it wherever it goes.

There is a second description, and it has no plane in it at all.

A presentation is a list of letters and a list of words that must equal the identity. Everything else about the group is a consequence. Whether two words name the same operation, how many operations there are, whether one subgroup sits inside another — all of it is decided by the words, and none of it needs a lattice, a matrix, or a picture.

That is worth having for a reason this site keeps running into. A statement about the drawing of a group is a statement that a change of convention can move. A statement about the group itself cannot be moved by anything, and the presentation is where such statements come from.

Where the letters come from #

Quoting a presentation would be a table, and this site does not run on tables. So the presentation is derived from the group’s own operations, by the standard construction for a group extension, and it takes four steps.

The translations. Every plane group contains a lattice, and the lattice has two generators. Call them x and y. They commute, which is the first relator: x y x⁻¹ y⁻¹.

One letter per generator of the point group. The point group of a plane group is cyclic or dihedral — there are ten of them and no others is the three-dimensional version of the same fact — so it needs at most two letters, r for a rotation and s for a reflection. Each is realised as an actual operation of the group, translation part included, taken from the coset representatives the closure produces.

Conjugation, read off the matrix. A translation conjugated by an operation is the translation by the rotated vector: g x g⁻¹ is the translation by the first column of g’s matrix. Nothing is chosen here. The matrix says what the word is, and there is one such relation for each letter and each translation.

The point group’s own relations, corrected. This is the step that carries the content. In the point group, r⁴ is the identity. In the plane group it need not be — the operation may come back translated — so each relation of the point group is evaluated where the group actually lives, and whatever pure translation comes out is written as a word in x and y and subtracted off.

pg is the smallest case and the whole of it fits in a sentence. Its point group is a single reflection, so in the point group s² is the identity; in pg the operation is a glide, and a glide applied twice is a translation by a whole cell. So the relator is s s x⁻¹ rather than s s, and that one character is the entire difference between pg and pm — two groups with the same point group, the same lattice and the same number of letters, told apart by where one relator comes back to.

The correction is the extension, and it is visible in four groups. Thirteen of the seventeen need no correction at all: every point relation comes back as the identity, the group is a semidirect product of its lattice by its point group, and the presentation says so on its face. The other four — pg, pmg, pgg and p4g — carry a correction, and they are exactly the four non-symmorphic plane groups that the arithmetic classes and the symmorphic count arrive at from two other directions entirely.

Three routes to the number thirteen, sharing no code: a search over finite subgroups of the integer matrices, a test on each group’s translation parts, and a count of relators that come back translated. That is the kind of agreement this site is built to notice.

Counting without counting anything #

The presentation is now a self-contained object: four letters, eight words. It can be handed to a procedure that has never heard of the plane.

Todd–Coxeter coset enumeration is that procedure, and what it does is worth stating plainly. Given generators, relators, and a list of words generating a subgroup, it builds a table whose rows are cosets of that subgroup and whose columns are the generators and their inverses. It fills entries by scanning relators at each row — a relator must carry a coset back to itself, so following it around the table forces entries — and it defines a new row only when a scan runs out of table. When two rows are proved to be the same coset, they are merged.

Run it on a plane group’s presentation with the subgroup generated by x and y, and the number of rows is the number of cosets of the translation subgroup. Which is the order of the point group.

Four is the order of the point group of p4. Nothing in the computation knew that, or knew what a rotation is.

Seventeen groups, seventeen agreements. For every plane group, the index returned by the enumeration equals the order of the point group computed from the matrices. The two numbers have nothing in common but the group: one is the size of a set of matrices, the other is the number of rows a table settled down to.

And the agreement is one-way. Two groups can return the same index and be different groups: p3m1 and p31m both settle at six, from presentations with the same number of letters and the same number of relators, and no amount of scanning separates them. The index certifies that a presentation presents a group of the right size; it does not certify which.

The refusal, which is the whole reason to trust the number #

An enumeration that always returns a number is not counting anything. Coset enumeration is guaranteed to terminate when the index is finite and is guaranteed nothing whatever otherwise, and that asymmetry has to be visible, or the method is a random number generator with good manners.

The two presentations differ by four characters. One presents a group of order six; the other presents an infinite group, and no amount of patience turns the second into a number. So the enumerator here reports an unfinished run as unfinished — it does not return the count it had reached, which would be an arbitrary function of the cap.

That refusal is also the reason the seventeen agreements mean something. A procedure that returns twelve for p6m and would also have returned twelve for a presentation that did not present p6m is not evidence. This one either finishes or says so.

The asymmetry has a name and a reason worth carrying, because it is not a defect of this implementation. Coset enumeration is a semi-decision procedure: if the index is finite it will find it, given enough table, and if the index is infinite it will run for ever without ever being able to say so. There is no version of the algorithm that terminates in both cases, and there cannot be, because deciding whether a finitely presented group is finite is undecidable — a theorem, not a gap in anybody’s implementation. The cap here is therefore not a tuning parameter with a right value; it is the point at which a machine that would otherwise never stop is stopped, and the only honest thing to do with the result is to report that it did not finish.

That is the same discipline the law of rational indices used as a decision procedure is under, and the same one a tolerance-based near-symmetry is under: a procedure that can only say yes must say nothing rather than no, and a number that came from running out of room is not a number.

What the checks establish, and what they do not #

Three things are checked here, and the third is easy to skip past.

Every relator holds where the group lives. Each relator is evaluated as a product of actual operations and must be the identity — not the identity modulo the lattice, which is a weaker statement, but the identity with a zero translation. That rules out a relation asserted too strongly: a false relator would present a smaller group and nothing downstream would notice.

The index is right. Coset enumeration on the letters alone returns the order of the point group. That rules out the commonest way of being too weak, which is a missing relation.

The generators generate. A set of letters that presents the right relations but names operations generating only a subgroup would produce a table with the right number of rows for the wrong group. So the operations chosen as r and s are handed to the Schreier construction along with x and y, and the subgroup they generate must be everything — the whole point group and the whole lattice.

What none of that amounts to is a proof of isomorphism. The three checks establish that the presented group maps onto the plane group, that the translation subgroup has the right index, and that no relation was invented. They do not exclude the possibility that the presented group is some proper extension agreeing on both counts. Proving that requires a different argument — a Reidemeister–Schreier rewriting, or an appeal to the general theorem that an extension is presented by exactly these relations — and neither is computed here. The claim made is the one that was checked.

This is the same discipline the site applies to the six-dimensional icosahedral construction, where a stated group is verified to preserve a point set and nothing verifies that no other group does. Stating which direction was checked costs one sentence and is the difference between a result and a decoration.

Why a presentation is worth the trouble #

The obvious objection is that the matrices were already there, and everything the presentation says can be read off them. For counting operations, that is true.

It stops being true the moment the question is about the group rather than about the plane.

p3m1 and p31m are the site’s standing example. They have the same point group, the same lattice, the same number of operations, and every plate here draws them side by side to show the difference: the mirrors of one run through the lattice points, the mirrors of the other run between them. That is a statement about where things sit in the plane. It is completely convincing and it is not, on its face, a proof that the two groups are not isomorphic — an isomorphism is not required to respect anybody’s drawing.

From the presentations, the two groups have different abelianisations, and that settles it in a way no picture can. The next rung is about that computation.

A second use is negative and worth as much. Presentations make it possible to state clearly what a group is not determined by. Two of the seventeen have identical presentations up to renaming letters, and are the same group; several have different presentations that a rewriting shows to be equivalent. Which words were chosen is a convention, exactly like a choice of origin or of cell. What survives every choice is what the presentation is for.

The word problem, which is not solvable in general #

A presentation raises a question it does not obviously answer: given two words in the letters, do they name the same element?

For a general finitely presented group the answer is that there is no procedure at all. Novikov proved it in 1955 and Boone independently in 1958: presentations exist for which no algorithm decides whether a word equals the identity, and the obstruction is not that the problem is hard but that it is unsolvable in the sense of computability. A presentation is a complete description of a group and it is not, in general, a usable one.

For a plane group the answer is that it is trivial, and the reason is the description this essay set out to do without. Every element is a matrix with a translation; multiplying the matrices out and comparing the results settles any two words in time proportional to their length. So the concrete description is not merely a picture of the abstract one — it is a solution to a problem that has none in general, which is what a faithful representation by matrices always is.

That leaves the two descriptions with a clean division of labour, and it is worth stating because the rest of this ladder depends on it. The matrices answer questions about elements: which operation is this, where does it sit, what does it do to that point. The letters answer questions about the group: how many cosets, what is the abelianisation, how few generators are needed. Each is bad at the other’s questions. The matrices cannot see that p3m1 and p31m are non-isomorphic, because non-isomorphism is not a property of any particular pair of matrices; the letters cannot draw anything.

And the traffic goes both ways. The presentation here was derived from the operations, so the abstract description was obtained from the concrete one. The next rung computes an invariant from the abstract description that decides a question the concrete one cannot answer. Neither description is prior; what matters is that the passage between them is a computation rather than an assertion.

Where the exactness stops #

The derivation is exact and the arithmetic is integral. Translations are carried as exact multiples of a twelfth of a cell, which clears every halving and thirding a plane group can produce, and a relator’s translation must be an integer number of cells or the derivation throws rather than rounding.

The enumeration is exact and bounded. The table is integer entries and merges; there is no tolerance anywhere. It is bounded by a cap, and hitting the cap is reported rather than answered.

The construction is two-dimensional here, and not by necessity. The same four steps derive a presentation of a space group in three dimensions from its operations, and the same enumeration counts its cosets — the point group’s presentation is the only part that would need extending past cyclic and dihedral. That is not done in these essays, and no claim here depends on it.

“Derived, not quoted” applies to the relations and not to the algorithm. Todd–Coxeter is implemented here, from its published description, in the form the standard reference calls HLT with coincidences. What is derived is the input; what is checked is the output.

Who found it, and when #

Walther von Dyck put presentations on a footing in 1882, and the free group modulo a normal closure of relators is still called a Dyck group in some quarters. The idea that a group could be specified by relations rather than exhibited as transformations was, at the time, a genuinely strange one.

J. A. Todd and H. S. M. Coxeter published the enumeration in 1936, as a systematic version of hand calculations people had been doing for decades. It was designed for pencil and paper — the paper’s worked examples were done by hand — and it became the first serious algorithm of computational group theory when machines arrived. It has the awkward distinction of being an algorithm that provably works and provably cannot be given a running-time bound, since the index it is looking for may be infinite.

Coxeter and Moser’s Generators and Relations for Discrete Groups (1957) collected presentations for the seventeen plane groups, among a great deal else, and is where a reader will find them tabulated. The presentations here agree with those, which is reassuring and is not the check: the check is that they hold in the group and enumerate to the right index.

Where this ladder goes #

Two rungs follow, and both are computations that the matrices cannot do.

The first is the abelianisation — what is left of a group when the order of its letters is thrown away. It is an invariant, it is computed by a Smith normal form on a small integer matrix, and it separates p3m1 from p31m without mentioning a mirror line.

The second is how few operations a group needs, which turns out to be a question with a floor and a ceiling that usually meet: the abelianisation says no group can be generated by fewer than a certain number, an exhaustive search says a set of that size exists, and for fourteen of the seventeen the two numbers agree and the answer is settled exactly.

A presentation is not unique, and the moves that change it #

The essay derives one presentation per group, and it is worth saying plainly that a group has many — because the non-uniqueness is where the whole difficulty of the subject lives.

Four elementary moves change a presentation without changing the group. Add a relator that is a consequence of the others, or remove one. Add a new letter together with a relation defining it in terms of the old ones, or remove such a pair. Those are the Tietze transformations, and Tietze’s theorem says that any two presentations of one group are connected by a finite sequence of them.

That is an existence statement and not a procedure. The theorem promises a sequence exists; it gives no bound on how long, no rule for finding it, and no way of telling — when a search has run a long time without success — whether to keep going. Deciding whether two presentations name the same group is Dehn’s isomorphism problem, and in general it is undecidable.

So a presentation is a description in exactly the sense this collection uses the word everywhere else: complete, and not canonical. Two people deriving one for p4g by the recipe above will get the same one because the recipe is fixed; two people deriving one by any means at all will not.

What rescues the plane groups is Bieberbach. For crystallographic groups the isomorphism problem is decidable, because an isomorphism must carry translations to translations and the search is finite — so the seventeen can be told apart by a procedure, which no general list of presentations could be.

That is the reason the checks in this essay stop where they do. They establish that the presented group maps onto the plane group with the right index, and the step from there to isomorphism is supplied by a theorem about crystallographic groups rather than by anything about presentations.