Telling two words apart

A plane group written as letters and relations is a small object: two to four generators, and a handful of relators saying that the translations commute and that the point operation moves them in a stated way. Multiplying two words in those letters is trivial — write one after the other. Deciding whether two words are the same element is not.

For general finitely presented groups it is not merely hard. It is undecidable: Novikov and Boone showed in the 1950s that there are finitely presented groups for which no algorithm whatever can answer the question. So the fact that these seventeen have a short answer is a fact about them and not about presentations.

The normal form #

Every element of a plane group is a translation followed by a point-group operation, and that decomposition is unique — a plane group is a semidirect product of its lattice by its point group, which is what an extension says in the symmorphic case and what the general case says with a twist.

So a word has a normal form: evaluate it, and record the translation and which point operation is left. The evaluation runs in the group’s own realisation — integer matrices, and translations carried as twelfths so that a three-fold rotation and a half translation are both exact — and two words name the same element exactly when the six integers agree. No tolerance, no search, no bound on the word length.

That the procedure is correct is two statements, and both are checked rather than assumed. The realisation is a homomorphism because every relator evaluates to the identity in it. It is injective because coset enumeration on the translation subgroup returns exactly the order of the point group — the presentation has no more elements than the matrix group, so nothing can have collapsed.

Why a normal form is the whole of it #

It is worth being explicit about what makes this easy, because the ease is not typical and the reason is structural.

A normal form is a rule that picks one word out of every set of words naming the same element, computably. If a group has one, its word problem is solved: reduce both words and compare. Most of the difficulty in combinatorial group theory is that a presentation gives no hint whether a normal form exists.

For a plane group the normal form comes from the structure rather than from the presentation. The group has a normal subgroup of translations with a finite quotient, so every element is t·p with t a translation and p one of finitely many point operations, and the pair (t, p) is unique. Reducing a word means pushing all the point operations to the right past the translations, which is possible because the relators say exactly how a point operation moves a translation — that is what the relators are.

The realisation does that pushing arithmetically. Instead of rewriting the word symbolically, each letter is multiplied in as a matrix and a translation, and the accumulated pair is the normal form. Same computation, no bookkeeping, and it is exact because the translations are carried as twelfths: a three-fold rotation moves a lattice vector to another lattice vector, a glide contributes a half, and twelve is the least common multiple of everything that occurs.

What the abelianisation cannot do #

There is a much simpler-looking procedure, and it is wrong.

Send each word to its exponent sums — how many times each letter appears, counting inverses negatively. That is the map to the abelianisation, it is easy to compute, and if two words differ there then they differ in the group.

The trouble is the other direction. Take the rotation r and a translation x in p4 and form the commutator r x r⁻¹ x⁻¹. Every letter appears once with its inverse, so every exponent sum is zero. In the abelianisation this word is the identity. In p4 it is a translation — the difference between x and its image under a quarter turn, which is a lattice vector and not zero.

That single example is why the abelianisation is a shadow rather than a description, and it is worth holding onto: the information the abelianisation throws away is exactly the information that makes a plane group a plane group rather than a lattice with a decoration.

And the shadow is not even a faithful one. Compute the abelianisation of all seventeen and only twelve different groups come back. p2, pmg, cmm and p4m all abelianise to ℤ₂ ⊕ ℤ₂ ⊕ ℤ₂; pgg, p4 and p4g all give ℤ₂ ⊕ ℤ₄; pg and cm both give ℤ ⊕ ℤ₂, and p31m and p6 both give ℤ₆. Four groups of order twelve in the point group and four with none in common arrive at one answer, because everything that distinguishes them lies in how a point operation moves a translation, and that is exactly what abelianising forgets. So the exponent sums cannot tell two groups apart either, let alone two words in one of them.

What the abelianisation is still good for is the opposite question, and it is worth the paragraph because it is used a few rungs along. It answers what quotients does this group have that are commutative, and those decide which colourings and which two-domain descents exist. p3’s is ℤ₃ ⊕ ℤ₃, of order nine; a group whose every commutative quotient has odd order has no homomorphism onto a group of order two, so p3 has no subgroup of index two — which is the one empty row in the subgroup table. A shadow is a poor likeness and a perfectly good silhouette.

A second procedure, with nothing in common #

A plane group is residually finite: for any element that is not the identity there is a finite quotient in which it is still not the identity. Reducing the translations modulo N gives such a quotient — the group becomes finite, of order |P|·N² — and two words that differ eventually differ there too.

That gives a second decision procedure, and it is a genuinely different one: it never computes a normal form, it works entirely inside finite groups, and it can be run by anyone who can multiply permutations. It is also much slower — the modulus needed grows with the size of the difference — which is the usual trade between a procedure that decides and one that merely searches.

The check that matters here is the negative one. A pair of words that are equal must be separated by no modulus, however far the search runs. If the two procedures disagreed, one of them would be wrong; running the second one on equal words is what makes that a test rather than a hope.

How many spellings an element has #

The other side of a decision procedure is that it makes the ambiguity visible. An element of a plane group has infinitely many spellings — append a letter and its inverse as often as one likes — and among them there is a shortest, its length in the word metric.

That shortest length is what the breadth-first search below computes, and it is not a property of the element alone: it depends on which letters are allowed. In p4, the translation x has length one; in p1 with the same lattice and the generators x and y, so does it. But the translation x·y⁻¹ has length two in p1 and length two in p4 as well, while a translation two steps along a diagonal is shorter in a group whose rotation can be used to reach it.

The rotation is a shortcut. In p6, three of the six short lattice vectors are reachable in one step and the other three in two, because the six-fold rotation produces them from the first — which is precisely why p6’s ball is a hexagon and p2’s is a diamond, and why the growth coefficients differ by a factor of three halves rather than by the ratio of the point-group orders.

Measuring the group #

Once two words can be told apart, the group can be counted. Multiply the identity by generators repeatedly, keep only the elements that are genuinely new, and the number reachable in n steps is a measurement.

Every dot in that picture required the word problem to be solved, because a breadth-first search has to know when two products are the same element. And what comes out is a sequence — 1, 7, 29, 78, 160, … for p6 — which is eventually a quadratic.

The four sequences worth putting side by side are p1’s, p2’s, p4’s and p6’s, because they share a construction and differ only in the point group. p1 gives 1, 5, 13, 25, 41; p2 gives 1, 6, 18, 38, 66; p4 gives 1, 7, 24, 56, 104. The counts are not multiples of each other term by term — a rotation reaches some elements sooner than the extra elements arrive — but the second differences settle at 4, 8, 16 and 36, which are twice the point-group orders for the first three and three times it for p6. How long they take to settle is the other reading: p1 is quadratic from radius two, p2 from three, p4 from four and p6 from five, and the delay is the number of steps it takes for the rotation’s shortcuts to stop being an edge effect.

Eventually quadratic is testable without fitting anything: a sequence is eventually quadratic exactly when its second difference is eventually constant. So the second differences are computed, the radius at which they settle is recorded, and half the constant is the leading coefficient.

The answer is exact and it is the same for all seventeen: the leading coefficient is

$$a = |P| \times \begin{cases} 3 & \text{hexagonal lattice} \\ 2 & \text{otherwise.}\end{cases}$$

Two factors, and both are interpretable. The point group’s order appears because each lattice point carries a whole coset of the translation subgroup, so the ball contains |P| elements for every lattice point it reaches. The two or three is the area of the unit ball of the word metric on ℤ²: with two generating translations the ball is a diamond of area 2n², and on a hexagonal lattice a third short translation is available cheaply, so the ball is a hexagon of area 3n².

That growth is quadratic at all is Gromov’s theorem in miniature. A group of polynomial growth is virtually nilpotent, and a plane group is virtually ℤ² — which is the strongest possible statement of the fact this collection uses everywhere: a plane group is a lattice with a finite decoration, and its growth cannot tell the decoration from the lattice except through the constant.

The Cayley graph is the pattern, nearly #

The picture the ball is drawn in deserves a word, because it is almost — and not quite — one of this collection’s pattern plates.

A Cayley graph has one vertex per group element and an edge for each generator. Drawing it in the plane by putting each element at its translation part is a projection: the |P| elements sharing a lattice point land on top of one another, so the picture shows the orbit of a point under the group rather than the group itself, with the multiplicities hidden.

That projection is exactly the map from a plane group to its lattice, and the fibres are the point group. So the drawing is the pattern the group generates from a single point — which is the orbit — with a distance written on each point saying how many letters it takes to reach it. The geometry and the algebra are the same picture at two levels of detail, and the word metric is the algebra’s contribution: nothing about the pattern says that one lattice point is two steps away and another is three.

Drawing the Cayley graph faithfully would need the fibres separated, which is what a fundamental domain does — one copy of the domain per group element, tiling the plane. The Cayley graph of a plane group is the adjacency graph of those copies, and the ball of radius n is the set of copies reachable in n steps.

What the round trip checked, and how #

The abelianisation must fail. The commutator above must be non-trivial in the group and trivial in the abelianisation, or the essay’s central example is not an example.

Equal words must not be separated. By any modulus, at any size.

Unequal words must be separated, and the modulus that does it is reported rather than merely existing.

The ball must keep growing. A breadth-first search that stopped finding new elements would mean the group had been mistaken for a finite one, and the sizes are required to be strictly increasing at every radius.

And every realisation must be faithful, which is the two-part check above, run for all seventeen.

Who asked the question, and when #

Max Dehn posed it in 1911, along with two companions — the conjugacy problem (are two elements conjugate?) and the isomorphism problem (are two presentations of the same group?) — and he posed all three in a paper about surfaces, because the fundamental group of a surface is exactly the sort of object that arrives as a presentation and needs to be recognised.

Dehn solved the word problem for surface groups with an algorithm that still bears his name, and it works by a very different principle from the one here: in a surface group, any word representing the identity contains more than half of some relator, so a word can be shortened by substitution until it vanishes. That is a rewriting procedure, and it is the ancestor of every modern normal-form algorithm.

Novikov in 1955 and Boone in 1958 independently produced finitely presented groups with unsolvable word problem, by encoding a Turing machine into a presentation. The construction is not delicate — once the encoding exists, the halting problem does the rest — and it settled that Dehn’s question has no general answer.

Between those two poles the plane groups sit at the easy end. They are virtually abelian, which is about as far from a Turing machine as a group can be, and the presentations this collection derives come with a faithful matrix representation attached because they were derived from one. The word problem is easy here precisely because the group was never given as an abstract presentation in the first place — which is worth saying plainly, since an essay that produced a normal form without saying where the group came from would be claiming more than it had done.

What it costs, which is the other half of decidable #

Decidability says an answer exists; it says nothing about how long it takes, and the two are worth separating because the gap between them is where most of the interesting mathematics on this question lives.

The procedure here is linear in the length of the word. Each letter is one multiplication of a matrix and a translation, the accumulated pair has bounded size, and the comparison at the end is exact integer equality. A word of a thousand letters costs a thousand small multiplications, and nothing about the group’s size or its relations enters the cost.

That is unusually good, and it is a consequence of the normal form being computed rather than searched for. Dehn’s algorithm for surface groups, by contrast, works by repeatedly finding a subword that more than half a relator, and its cost depends on the presentation as well as on the word. Coset enumeration — the method the figure above uses to check the index of the translation subgroup — is worse still: it is guaranteed to terminate only when the index is finite, and even then no bound on its running time can be computed in advance from the presentation.

And in the general case there is no cost at all to speak of, because there is no procedure. That is the shape of the whole subject: the plane groups are decidable, cheaply, for a structural reason, and one step outside them the question stops having an answer rather than becoming expensive. The same distinction runs through this collection’s tiling essays — a bounded search that always terminates is a different kind of object from one that terminates when it is lucky, and the difference is not one of degree.

Where the exactness stops #

Solvability here is not solvability in general. These groups have a normal form because they are virtually abelian. A general finitely presented group has no such structure and, by Novikov and Boone, may have no algorithm at all. Nothing about the procedure here extends; what extends is the observation that a faithful representation by matrices with computable entries always solves the word problem, and finding one is the hard part.

The growth coefficient is a fact about the group and its generators. Change the generating set and the ball changes shape and the coefficient changes with it. What does not change is that the growth is quadratic, which is why the degree is a group invariant and the coefficient is not. The table’s numbers are for the generators this collection’s presentations use, and they would be different for others.

The second differences settle, and where they settle is measured. For p1 it is immediate; for p6m it takes six steps, because the point group has twelve elements and the ball has to grow past them before the lattice dominates. That number is reported so that a reader can see the claim is asymptotic rather than exact at small radius.

Nothing here decides conjugacy or isomorphism. Dehn’s other two problems are separate, and the second is the one this collection answers elsewhere by other means: deciding whether two of the seventeen are the same group is done by comparing operations rather than presentations, and two presentations that describe the same group can look very different.

The finite quotients are a semi-decision procedure made complete by a theorem. Residual finiteness is what guarantees a separating modulus exists; the search would run forever on a group without it, and nothing in the search would announce that.

Where the ladder goes next #

The presentations thread has now derived a group from its own operations, forgotten its order, found how few operations rebuild it, and decided when two of its words agree. What has not been asked is which of its subgroups are the same group again — a plane group sitting inside itself with a bigger cell, which turns out to be possible only at certain indices, and those indices are the values of a quadratic form.