Folding a graph until it decides

A subgroup of a free group is nearly always given by a list of words: the subgroup generated by $abaB$, $bb$ and $aa$. Almost nothing is readable from that list. Its rank is not the number of words, since they may be dependent. Its index is not visible at all. Whether a fourth word belongs to it is not obvious in any case where it is not obvious.

The two rungs below turn subgroups into graphs and into permutations, and both start from a covering that is already given. Stallings’ construction starts from the words.

The construction #

Draw the words. Make one loop at a base vertex for each generator word, with one edge per letter and a fresh vertex between consecutive letters. The result is a bouquet of loops meeting only at the base, and its loops are exactly the given generators.

Fold. Wherever two edges with the same label leave the same vertex, merge their far endpoints into one. Wherever two edges with the same label arrive at the same vertex, do the same.

Stop when nothing folds. What is left is a graph in which every vertex has at most one edge of each label leaving it and at most one arriving.

Folding is the right operation because it does exactly one thing to the subgroup: nothing. Merging the far ends of two like-labelled edges from one vertex identifies two paths that read the same word, and two paths reading the same word from the same start already represent the same element — so the identification adds no new elements and loses none. Every fold is a change to the picture and not to the group, which is why the folded graph can replace the bouquet.

That last property is the whole point. It makes the graph deterministic: reading a word from the base vertex, each letter has at most one edge to follow, so the walk is forced. A word is in the subgroup exactly when the walk exists and returns to the base.

Why it stops #

Every fold merges two vertices into one, so the vertex count strictly decreases. A count of vertices is a whole number, it starts finite, and it cannot decrease forever — so the folding terminates, in at most as many steps as there were vertices to begin with.

That is a termination argument by decreasing measure, the same shape a tableau’s is and the same shape a congestion game’s potential provides. Find a quantity the operation reduces, and note that it cannot be reduced without limit.

The bound is good as well as finite. The starting graph has one vertex per letter of the input, so folding costs at most that many merges, and each merge is cheap. The whole construction is linear in the total length of the words, up to the bookkeeping of finding which edges to fold.

What the folded graph says #

Once the graph is folded, everything about the subgroup is a property of it and every question is a walk.

Membership. Read the word. If the walk exists and comes back, the word is in the subgroup; otherwise it is not. That is one step per letter, and the figures test it on the generators, which must be accepted, and on words that must be refused.

Rank. The subgroup is free — Nielsen–Schreier — of rank $E - V + 1$, read off the folded graph exactly as the rung below reads it off a covering. A list of three words that folds to a graph of rank two has produced a dependent generating set, and the folding is what found the dependence.

Index. The subgroup has finite index exactly when every vertex of the folded graph has an edge of every label both leaving and entering — when the graph is a genuine covering rather than a fragment of one. The index is then the number of vertices.

And a basis. Growing a spanning tree and taking the edges outside it gives a free basis for the subgroup, written as words in the original generators. So the construction produces not only the rank but the generators achieving it.

The basis deserves a sentence about its shape, since it is the same shape the rung below produced from a covering. Each edge outside the tree gives one generator: the path down the tree to that edge’s start, the edge itself, and the path back up the tree from its end. So a generator is a word of length at most twice the tree’s depth plus one, and the whole basis is written down in one pass.

A basis found this way is not the list that was handed in. The input words may be dependent, may be longer than necessary, or may be a redundant description of a small subgroup, and the folded graph reports the truth about all three. That is the practical value of the construction: handed a list, it returns the subgroup’s actual size and an efficient description of it.

Why the folded graph is the right object #

The construction is not an ad-hoc trick and the reason is the ladder’s dictionary.

The folded graph is a subgraph of the covering corresponding to the subgroup — specifically the core of it, the part reachable by the subgroup’s own loops. Folding is the operation that turns an arbitrary graph mapping to the wedge into an immersion, and the immersion is the core of a covering.

So the algorithm computes the covering from the words, which is the direction the correspondence does not obviously give: the rung below’s dictionary says a subgroup determines a covering, and folding is how that covering is built when the subgroup arrives as a list.

The finite-index case is where the core is the whole covering. When the folded graph is already a covering — every label present at every vertex, both ways — nothing is missing and the number of vertices is the index. When it is not, the subgroup has infinite index and the core is a finite object describing an infinite covering, which is why the algorithm terminates on a case the covering itself does not.

The missing part is easy to describe and worth describing, because it explains what the core leaves out. A vertex of the folded graph lacking an $a$ leaving it would, in the full covering, have one — leading out into a piece of the covering that no loop of the subgroup ever visits. Attaching an infinite tree at each such gap recovers the whole covering, and every one of those trees is invisible to every question the algorithm answers.

So the core is exactly the part a subgroup can see, and the infinite remainder is the part it cannot. That is why an infinite-index subgroup has a finite description at all: the subgroup is finitely generated, its loops are finitely many, and everything they touch is a finite graph.

What it settles that was open #

The construction dates from 1983 and it turned a number of questions from hard into routine, which is worth listing because it says what an algorithm is worth.

Membership was decidable before by Nielsen’s method, and folding is faster and much simpler to state. Nielsen’s reduction repeatedly replaces a pair of generators by a shorter product, which terminates and takes work quadratic in the total length; folding is linear, and the folded graph then answers each subsequent membership question in time proportional to the word rather than to the subgroup.

Whether two lists generate the same subgroup is decided by folding both and comparing the graphs, since the folded graph is unique.

Whether a subgroup has finite index, and what it is, is read off the graph.

Intersection is the product construction of the rung below: fold both, take the graph of pairs, and the component containing the base pair is the intersection’s core. Howson’s theorem — that two finite-rank subgroups of a free group intersect in one of finite rank — falls out with an explicit bound, where the original proof gave none.

And Nielsen–Schreier itself. The folded graph is a graph, its fundamental group is free, and the subgroup is its fundamental group, so the subgroup is free. That is the rung below’s proof with the covering constructed rather than assumed.

Reading the graph as an automaton #

The folded graph is a machine and it is worth naming which kind, because the vocabulary supplies several free theorems.

A deterministic finite automaton has states, a starting state, a set of accepting states, and one transition per state and letter. The folded graph has all four: the vertices are states, the base vertex is both the start and the only accepting state, and determinism is exactly what folding achieved.

So membership in the subgroup is acceptance by an automaton, and the language it accepts is the set of words representing subgroup elements. That is a regular language, which is a strong statement about the subgroup: every finitely generated subgroup of a free group is a regular set of words, and regular sets are closed under intersection, union and complement.

The closure properties are where the free theorems are. Intersecting two subgroups is intersecting two automata, which is the product construction; deciding whether one contains another is deciding language inclusion; and deciding whether two lists give the same subgroup is deciding language equality, which for deterministic automata is minimisation and comparison.

Every one of those was a theorem in group theory before it was an exercise in automata, and the translation is what makes the second description the practical one.

Uniqueness, and why the order does not matter #

The construction has a choice in it — which pair of edges to fold next — and the result does not depend on it, which is a property that needs proof and is what makes the graph an invariant.

The argument is a confluence statement: two different folds available at once can be performed in either order and reach the same graph, so any two folding sequences converge. That is the same shape of argument as cut elimination’s and as the confluence of any rewriting system.

The two-step version of it is the standard lemma. If a graph admits two different folds, performing either one leaves the other still available — possibly in a slightly changed form — and doing both in either order gives the same result. Combined with termination, that local statement upgrades to the global one: every sequence of folds ends, and all of them end in the same place.

Termination plus local confluence gives uniqueness, and that pair is the standard way any rewriting system is shown to have normal forms. It is the same argument that makes a reduced word in a free group well defined, which is the fact this whole construction was built on.

So the folded graph depends only on the subgroup, not on the generating list or the folding order — which is what lets two subgroups be compared by comparing their graphs.

Where it needs its hypotheses #

The group must be free. Folding uses that a word has a unique reduced form and that a graph’s fundamental group is free. In a group with relations there are extra identifications the graph cannot see, and the construction does not apply.

Labels must be distinguishable and directed. An edge carries a generator and a direction, and the folding rule is about edges with the same label and the same direction relative to the vertex. Ignoring direction folds too much and produces a graph that accepts words outside the subgroup.

The base vertex is part of the data. The folded graph without a marked base decides the subgroup only up to conjugacy — which is the same ambiguity the covering correspondence has, and for the same reason.

Folding can only ever shrink the graph. Every merge identifies two vertices and never separates any, so the folded graph is a quotient of the bouquet and the subgroup it describes contains everything the bouquet’s loops did. The construction cannot lose a generator, which is the direction the correctness proof needs first.

And the refusals are the check with teeth. A graph that accepted everything would pass every test made of the generators and would be useless. The figures list words that must be refused and require them to be, which is this collection’s standing habit and is the only way to know a decision procedure decides.

Stallings, and a paper about something else #

John Stallings published the folding construction in 1983, in a paper called Topology of finite graphs, and the immediate purpose was a new proof of Grushko’s theorem — about how a free product decomposes — rather than an algorithm for subgroups.

The algorithm is the paper’s method rather than its result, and it is now the more used of the two. That is the same shape as several results on this site: the Lagrange remainder inside a failed programme, Kummer’s carry theorem inside work on Fermat’s last theorem, and here an algorithm inside a proof.

The method’s ancestry is older. Nielsen’s 1921 argument reduces a generating set by replacing pairs with shorter products, and it is essentially folding done on words rather than on a graph; Stallings’ contribution was to see that the same reduction is a geometric operation with a geometric invariant at the end.

Moving a combinatorial procedure onto a graph made its output an object rather than a normal form, and that is why the folded graph answers questions the word-based version could only answer one at a time.

What the pictures cannot show #

The figures draw the folded graph and not the folding. The merges happen in some order, the intermediate graphs are not shown, and the confluence — that any order reaches the same place — is asserted rather than drawn.

The covering the folded graph is the core of is generally infinite, and only the core is drawable. So the picture is complete as a decision machine and incomplete as a picture of the covering, and which of the two is being looked at matters for reading the vertex count as an index.

And the acceptance and refusal are computed rather than visible. A reader can trace a word through the graph and check one case; that the machine is correct on every word is a theorem about the construction, and the figures test a handful in each direction.

The ladder from here #

Rungs above: Grushko’s theorem and the folding proof it was written for. The Kurosh subgroup theorem for free products, where the same technique classifies subgroups of a more complicated object. Folding for graphs of groups, which extends the whole apparatus to groups built from pieces. The algorithmic questions the construction opens — deciding whether a subgroup is normal, computing its normaliser, finding a basis — each of which becomes a property of the graph. And the connection to automata, where a folded graph is a deterministic finite automaton and membership is exactly acceptance.

An object instead of a normal form #

The habit is the one the history above names, and it is worth stating because the improvement is easy to underestimate.

Nielsen’s method takes a list of words and returns a better list. Two subgroups given by different better-lists still have to be compared word by word, and every question about the subgroup is a new computation on the list.

Stallings’ method takes a list of words and returns a graph, and the graph does not depend on the list. Two subgroups are equal exactly when their graphs are isomorphic; the rank is a subtraction; membership is a walk; the index is a count of vertices.

The gain is that a canonical object answers every question, and a normal form answers the question it was normalised for. That is the general reason to prefer a construction returning an object to one returning a representation, and the test of whether the object is the right one is exactly the uniqueness proof — without it, the graph would be one more representation and the whole advantage would be gone.