Every word driven to a normal form

Every surface is a sphere with handles computes two numbers from a gluing word, reads the surface’s name off them, and says in as many words that this is not the theorem: “nothing here proves the theorem. The figures compute the two numbers for particular gluings and check them against the names. That the numbers determine the surface is a claim about all surfaces, its proof is the reduction of words to normal forms, and no drawing of four squares establishes it.”

The reduction is a procedure, it is short, and it can be watched.

What the moves are allowed to be #

A gluing word describes a polygon with its edges paired. The reduction rewrites the word, and every rewrite must be a cut-and-reglue: cut the polygon along a straight line between two corners, and glue the two pieces back along a pair of edges that were going to be identified anyway. The result is a different polygon with a different word and the same surface, because nothing was added or removed — only the order of the assembly changed.

That is the only licence the proof has, and it is what makes the derivation trustworthy. Three moves suffice, plus rotating the word, which is only a choice of where the polygon starts.

Cancel. If a letter sits beside its own inverse, the two edges are glued to each other directly and the pair can be deleted — the polygon folds shut along them. The one exception is a word of length two, which is already a sphere and has nothing left to cancel into.

Bring a flip pair together. If a letter appears twice the same way round, the gluing has a flip in it. One cut and one reglue brings the two occurrences adjacent, producing $yy$ followed by the rest of the word reversed and inverted. That is a cross-cap, isolated.

Bring an interleaved pair together. If two letters alternate round the polygon — $a \ldots b \ldots a^{-1} \ldots b^{-1}$ — two cuts bring them adjacent as $aba^{-1}b^{-1}$. That is a handle, isolated.

Collapse a handle beside a cross-cap. Once both a handle block and a cross-cap block are present, the identity replaces them with three cross-caps. That is the fourth move, it is Dyck’s identity applied as a rewrite, and it is what stops the reduction ending at a mixed form.

Each move takes a word to a word and each is a cut-and-reglue. Four is the complete list, and the argument that four suffice is the whole content of the proof.

Why those three exhaust the cases #

Take a word in which no letter sits beside its inverse — otherwise cancel. Pick any letter. Its two occurrences either run the same way round or they do not.

If they run the same way, the second move applies. If they run opposite ways, look at what sits between them. Either some letter has one occurrence inside and one outside — the letters are interleaved, and the third move applies — or every letter inside is entirely inside. In that case the part between the two occurrences of $a$ is a word in its own right, glued to itself, and $a \ldots a^{-1}$ wraps a smaller surface in a way the first move can cancel after the inner part has been reduced.

So the first three moves cover every word, and applying them repeatedly separates it into cross-caps and handles with nothing else left. The fourth then finishes the job: a handle beside a cross-cap is three cross-caps, which is the identity the gluing diagrams state as Dyck’s theorem, so a word containing both collapses to cross-caps alone. That is why the answer is two lists rather than a grid.

The fourth move is genuinely needed and is the one easiest to leave out. Without it the reduction stops at forms like $bcb^{-1}c^{-1}dd$ — one handle and one cross-cap, which is a perfectly good surface and is not one of the three standard shapes. That omission is how this figure came to have a fourth move: the derivation ran to a word it could not name.

Why the procedure stops #

A procedure that rewrites words needs an argument that it terminates, and the argument is a quantity that cannot rise for ever.

The cancel move shortens the word by two. The other two moves do not shorten it — they rearrange — so length alone is not enough. What falls is a compound measure, and it has to be compound because the four moves pull in different directions. The first part counts the letters not yet sitting inside a finished block — an isolated $xx$ or a commutator — and the cancel, cross-cap and pair moves all lower it. The collapse leaves that part at nought and lowers the second: the number of handle blocks still standing beside a cross-cap, which is one before the collapse and nought after.

Written as one number, the measure is four times the first part plus the second, so that lowering the first always beats anything the second does. A single obvious count does not work: the word’s length with flip pairs doubled falls for three of the moves and rises for the collapse, since six edges with one flip pair become six edges with three.

The figures compute that measure at every line and require that no move raises it. That requirement is what the derivation is evidence for — an argument that a procedure stops is exactly the kind that is easy to state and easy to get wrong, and a measure that provably never rises is the checkable version of it.

Both of those were found by the derivation rather than by thinking about it. The first version demanded a strict fall at every step and the octagon refused to draw, because a commutator move can rearrange without lowering anything; the second version’s measure rose at the collapse. A drawn derivation checks the termination argument at every step it takes, and an argument that only sounds right does not survive that.

The invariants as a guard, not as the answer #

The figures recompute the characteristic and the sidedness after every move and require both to be unchanged. That is worth being precise about, because it is not how the proof uses them.

The proof does not need the invariants at all. It rewrites words by moves that manifestly preserve the surface, reaches a standard form, and reads the answer off the form. The invariants are what makes the converse work — that two surfaces with the same pair are the same surface — and they enter only at the end, to say which standard form was reached.

What the figures use them for is a check on the implementation. A move implemented wrongly would produce a word describing a different surface, and the characteristic or the sidedness would move. So the invariants are the test harness rather than the argument, and that is the right division: the moves are what the proof is made of and the invariants are what catches a mistake in them.

Both are computed from the word by the counting an earlier essay sets up — corners pooled by the identifications, one edge per letter, one face — and the alternating sum’s independence of the cutting is what makes that computation meaningful across a rewrite — without it a rewrite could change the number without changing the surface, and the guard would be worthless.

A word with three flip pairs, and what the identity does #

The tidying identity is the step that looks like a trick and is the reason the answer is a list rather than a table, so it is worth watching it act.

Dyck’s identity says a handle in the presence of a cross-cap is worth two more cross-caps. In word terms, $aba^{-1}b^{-1}cc$ reduces to $ddeeff$ — the handle’s four edges and the cross-cap’s two become three cross-caps. The reduction above applies it as a named move, and the order matters: the collapse is tried before the commutator move, because otherwise the commutator move rebuilds the handle the collapse would have removed and the two alternate for ever. That loop is what the step budget would have reported, and reordering the moves is the fix.

That is why the two lists cannot mix. A word containing any flip is driven all the way to cross-caps; a word containing none is driven to handles; and the collapse is what carries the first case past the mixed forms it would otherwise stop at.

It is also where the asymmetry between the two lists comes from. A handle costs two from the characteristic and a cross-cap costs one, so a surface with $k$ cross-caps has $\chi = 2 - k$ and the odd and even $k$ are both available; the two-sided list only reaches even values. The two lists overlap in their values and not in their surfaces, which is why the sidedness cannot be dropped and is visible in the arithmetic rather than in any picture.

What the normal forms are #

The reduction ends at one of three shapes and the list is short enough to write out.

$$aa^{-1} \quad\text{the sphere}$$

$$a_1b_1a_1^{-1}b_1^{-1}\cdots a_gb_ga_g^{-1}b_g^{-1} \quad\text{the surface with } g \text{ handles}$$

$$c_1c_1c_2c_2\cdots c_kc_k \quad\text{the sphere with } k \text{ cross-caps}$$

Reading the invariants off each takes a line. The handle form has $4g$ edges in $2g$ pairs and all its corners in one class, so $\chi = 1 - 2g + 1 = 2 - 2g$. The cross-cap form has $2k$ edges in $k$ pairs and all its corners in one class, so $\chi = 1 - k + 1 = 2 - k$. The handle form has every letter appearing once each way, so it is two-sided; the cross-cap form has every letter twice the same way, so it is not.

So the forms are indexed by one number each and the invariants recover it. That is the classification, and the reduction is what says every word is one of them.

The same reduction on the Klein bottle #

The word $abab^{-1}$ is the case an earlier essay uses to argue that both invariants are needed, and it is worth following through the procedure because the derivation says something the invariants do not.

No letter sits beside its inverse, so cancel does not apply. The letter $a$ appears twice the same way round, so the cross-cap move does: one cut brings the pair together and the rest of the word is reversed and inverted. The result is a word with two cross-caps, which is $\chi = 0$ and one-sided.

So the derivation says the Klein bottle is two cross-caps — which is the statement a disc sewn to a Möbius band makes from the other direction, by building it out of two Möbius bands. Two constructions, one surface, and the reduction is what identifies them without anybody having to see either object.

That is the practical value of a normal form. Two descriptions of the same thing look unrelated until both are reduced, at which point they are the same string of letters — and the reduction is a procedure, so the comparison needs no insight. A normal form turns “are these the same?” into “are these strings equal?”, which is the whole reason normal forms are worth having in any subject.

What the procedure does not settle #

It does not give the shortest derivation. The moves are applied in a fixed order — cancel first, then flip pairs, then interleavings — and a different order gives a different sequence and the same end. How short a derivation can be is a question about words rather than about surfaces, and nothing here answers it.

It does not extend to three dimensions. An earlier essay says the classification in three dimensions “is not a list but a decomposition”, and the reason the method fails is visible here: the whole procedure depends on a surface being cuttable into a polygon, a single disc with its edges paired — the shape the gluing diagrams start from. The analogous statement in three dimensions — every three-manifold is a ball with its faces glued — is true, and the moves on the resulting words do not reduce to a short list.

And it assumes the surface is triangulable. Every surface is, which is a theorem of Radó’s from 1925 and is not obvious; without it there is no polygon to start from, and the surfaces that cannot be drawn at all are handled by the words exactly because the words never leave the plane. That hypothesis is invisible in the procedure and is doing real work, and it is the one step of the classification that two dimensions gets for free and four does not get at all.

Why a polygon is the right starting point #

One assumption runs under the whole procedure and is worth making visible, because it is where the two-dimensional case gets its ease.

A closed surface, cut along enough curves, opens out into a single disc — a polygon with its edges paired. That is the statement the procedure starts from, and it is not obvious: it says the surface has no essential complexity beyond how the disc’s edges are matched. The cutting is done by taking a triangulation and removing a spanning tree’s worth of edges, which leaves a disc, and every surface has a triangulation.

Once the surface is a polygon, everything is combinatorics. The word is a finite string, the moves are string rewrites, the invariants are counts, and the whole classification is a theorem about strings that happens to be about surfaces. The geometry is spent entirely in the first step, and the reason three dimensions is hard is that the corresponding first step gives an object whose rewriting rules do not reduce.

That division is worth carrying. A classification proof of this shape has two halves: a normalisation of the object into combinatorial data, and a normal-form theorem about the data. The first half is geometry and is usually the deep part; the second is bookkeeping and is what a figure can carry. Here the first half is Radó’s theorem and is invisible on this page, and the second half is the table.

What the pictures cannot show #

The derivations are tables of words, which is the honest picture of a procedure on words and a poor picture of a surface. What the moves are — a cut along a diagonal, a regluing along an edge — is a pair of pictures the figures do not draw, and a reader who wants them has to hold the polygon in mind while reading the table.

The step budget is finite and stated. A word needing more moves than the budget allows would stop short of a normal form, and the figure requires that a normal form is reached — so a word too long for the budget refuses to draw rather than reporting an unfinished reduction.

And a word already in normal form has no derivation. The figures require that at least one move applies, so pointing the procedure at $aabbcc$ refuses: there is nothing to do, which is the correct answer and not a picture.

Still open: how long a reduction has to be #

The reduction terminates and how quickly is a different question. The measure that never rises gives a bound of roughly the word’s length squared, since each move either shortens the word or removes one flip pair or interleaving, and there are at most a linear number of those.

Whether that is the truth is not known to be sharp. There are words for which the obvious strategies take a quadratic number of moves and no word is known to need more, but a matching lower bound would need a way of certifying that a given word is far from every normal form — and the natural candidate for such a certificate, the invariants, are computed in linear time and say nothing about distance.

The related question with more at stake concerns the analogous problem one dimension up. Deciding whether two three-manifolds given by gluing words are the same is algorithmically hard in a way the two-dimensional case is not — the two-dimensional decision is two numbers and a comparison — and locating the boundary between the easy and the hard case is a subject rather than a result.

What the list of moves was worth #

A classification theorem can be stated in one sentence and believed on authority. What the procedure adds is that the sentence is a consequence of three rewrites, each of which is a picture anybody can check, and that the whole of the theorem’s content is the claim that those three cover every case.

The exhaustion is where the work is. Proving that a word with no cancellable pair, no repeated-same-way letter and no interleaving does not exist is the argument, and once it is made the rest is bookkeeping. That shape — a short list of moves, an argument that the list is complete, and a measure that makes the rewriting stop — is what a normal-form theorem always looks like, whether the objects are surfaces, matrices or fractions.

And the measure is the part most often left out. A procedure that plainly makes progress usually does, and the cases where it does not are the interesting ones; writing down what falls is cheap, and it is the difference between a method and a hope.