A subgroup becomes a machine

A subgroup given by words can be hard to inspect. A small labelled graph changes the task: membership becomes following a path. The important step is proving that the graph remembers exactly the subgroup we started with.

This is the purpose of Stallings folding. We work through one example, then use the same graph operations to find a basis and compute an intersection.

Words that hide a simple question

Work in the free group F(a, b). Its elements are words in a, b and their inverses, reduced by cancelling adjacent inverse pairs. Multiplication concatenates words and reduces. Let H be the subgroup generated by a² and ab. Is a given reduced word in H?

One approach searches through products of the two generators and their inverses. The search hides useful information in repeated cancellations. We will instead build an object that incorporates those cancellations into its local rules.

Build the loops, then fold

Start at a vertex called 0. Draw one loop reading aa and another reading ab, giving each an intermediate vertex. Every arrow may also be followed backwards, with its label inverted. The closed walks at 0 represent exactly products of our generators and their inverses.

We want to read an input word one letter at a time without searching among several possible continuations. At present, the first letter a offers two choices. Make that choice unique by identifying the two a-arrows and their endpoints. This operation is called a fold. It gives the required deterministic reading rule, but we must still check that the identification has not changed the represented subgroup.

Why the fold preserves the answer

Every old closed walk remains a closed walk after folding, with the same label. The converse needs an argument: identifying vertices might otherwise create unwanted words.

Here a new walk may switch between what used to be vertices u and v. Before folding, connect them by travelling backwards along the first a-edge and forwards along the second. That detour reads a⁻¹a, which cancels. Insert this detour whenever a lifted walk needs to switch sides. The result is an old closed walk representing the same free-group element. Thus the fold preserves the represented subgroup.

The general Stallings folding procedure repeatedly identifies equally labelled arrows with the same starting vertex, including inverse arrows. Each fold reduces the finite graph, so the process terminates. The same cancellation argument justifies each step. In the resulting graph there is at most one outgoing arrow for each signed letter at each vertex.

We may then discard every edge that lies in no reduced closed walk based at 0, keeping the base vertex itself. Here reduced means that an edge is never immediately followed by its reverse. The remaining pointed graph is the core. This pruning removes no accepted group element; in our example there is nothing to prune.

Membership becomes a walk

Why is it enough to read the reduced word? In a folded graph, two successive inverse labels must traverse an edge and then its reverse: that reverse is the unique outgoing edge with the required label. Cancelling the letters therefore cancels a backtracking detour, without changing the endpoints. A closed walk representing a group element reduces to a closed walk reading its reduced word.

Reduce the input word, start at 0, and follow its letters. A missing arrow or a different final vertex means rejection; returning to 0 means membership. For this graph:

The third answer can be checked in the original generators: a⁻¹b = (a²)⁻¹(ab). The graph has made this cancellation available without a search through products.

Once the finite graph has been constructed, testing a word takes one transition per letter. Free reduction can also be done in linear time with a stack: append the next letter unless it cancels the last one already stored. These bounds concern a membership query after preprocessing; they do not identify the cost of building the graph with the length of that query.

A basis from a spanning tree

Choose the outgoing a-edge as a spanning tree. Each remaining edge gives a closed walk: reach its start along the tree, cross the edge, and return along the tree.

These walks generate every closed walk. Insert the tree path from 0 to each intermediate vertex and its reverse between successive edges. The inserted paths cancel in pairs, expressing the original walk as a product of the displayed loops and their inverses; tree edges contribute only backtracking. They are independent as well. Contract the tree and record each remaining edge by its own letter. Removing backtracking deletes inverse pairs of these letters, so a nonempty freely reduced product of the proposed generators cannot reduce to the empty walk.

To transfer this basis to the subgroup, use the foldedness argument from the membership test: a nonempty reduced edge path has a nonempty reduced label word. The label map therefore introduces no additional relation, and the closed walks above give a free basis of the represented subgroup.

Here they read a² and ab. In a connected finite graph the count is E − V + 1, counting each edge together with its reverse once. We have 3 − 2 + 1 = 2 generators.

Intersection becomes synchronisation

Now suppose finite folded graphs represent subgroups H and K. Membership in their intersection asks for the same word to be accepted by both graphs. While reading that word, the information we need is the current vertex in each graph. Use that pair as a new state. A letter can be followed from a pair exactly when it can be followed in both coordinates. Start at the pair of starting vertices.

A reduced word returns to that pair exactly when it returns in both original graphs: exactly when it lies in H ∩ K. Keep the starting component and remove edges that occur in no reduced closed walk based there. This gives the subgroup graph for the intersection. It is finite, and a spanning tree supplies a finite basis. We have both an algorithm and a proof of Howson’s theorem: the intersection of two finitely generated subgroups of a free group is finitely generated.

For a concrete calculation, keep H = ⟨a², ab⟩ and take K = ⟨a⟩. The graph for K has one vertex and one a-loop. In the product, the two a-edges of the graph for H remain, while its b-edge disappears because the second coordinate has no such edge. The resulting two-edge circuit reads a². Thus

The product has at most the product of the two vertex counts. Its size can therefore exceed either input graph, even though reading a single word in it remains deterministic.

Completing a graph changes the subgroup

A subgroup has finite index precisely when its folded core graph is finite and complete: every signed letter can be followed from every vertex. Its index is then the number of vertices. Our graph is incomplete, so H has infinite index. Adding a b-arrow from 0 to 1 would complete it, but would enlarge the subgroup: b² would now be accepted. The completed graph has two vertices, and each letter switches between them, so it accepts exactly the words of even reduced length. Completion can construct a finite-index overgroup; it does not preserve the original membership problem.

The free-group hypothesis matters throughout. Additional relations change which words are equal, so this finite machine does not automatically solve subgroup membership in an arbitrary group.

Sources and another graph construction

John R. Stallings developed the method in Topology of finite graphs, Inventiones Mathematicae 71 (1983), 551–565. For the detailed combinatorial treatment used here, see Ilya Kapovich and Alexei Myasnikov, Stallings foldings and subgroups of free groups: §§2–3 for folds and subgroup preservation, Lemma 6.1 for a spanning-tree basis, Proposition 8.3 for finite index, and Proposition 9.4 and Corollary 9.6 for intersections. The examples above illustrate these established constructions.

For finite groups, the transporter graph keeps two witness words while searching by left and right multiplication. Its closed comparisons recover subgroup intersections attached to different components.