The subgroup that is freer than the group

A subgroup is smaller than the group it sits in. It has fewer elements, or at any rate no more; it satisfies every relation the group satisfies and possibly others besides. Nothing about that suggests a subgroup could need more generators than the whole group — and yet inside the free group on two letters sits a subgroup of index three which is free on four.

The statement is Nielsen’s, from 1921 for the finitely generated case and Schreier’s in general four years later, and both original proofs are combinatorial: take a subgroup, choose representatives for its cosets, grind out a generating set, prove it has no relations. The proof below is not that. It replaces the group with a space and the subgroup with a covering of that space, and then the theorem is a count of edges.

The space whose loops are a free group #

Take a point and attach a circle to it. A loop that goes round once is not the same as a loop that stands still, and going round n times is not the same as going round m times, so the loops of this space are the integers — a free group on one generator.

Attach two circles instead and the loops become words in two letters, a and b, with the only permitted simplification being the cancellation of a letter against its own inverse. That the group is free — that no other relation holds — is not obvious from the picture and is exactly what a covering argument establishes: the universal cover of the wedge of two circles is an infinite tree in which every vertex meets four edges, a tree has no loops, and a word that returned to its starting point upstairs would have to be a word that cancelled.

So a wedge of circles is a space whose fundamental group is free, with one generator per circle. The word rank means the number of circles, and it means the number of generators, and the whole argument works by keeping those two meanings glued together.

Every covering of a graph is a graph #

Now the second ingredient, and it is where the topology earns its place. A covering space of a graph is a graph. Above each vertex sits a set of vertices, above each edge a set of edges, and the local picture is a stack of copies — which for a one-dimensional space means the thing upstairs is again one-dimensional, with vertices and edges and nothing else.

The way to build one is to say, for each generator, how it permutes the sheets. Send a to the permutation that swaps the two sheets and b to the one that does nothing, and the covering is drawn above: two vertices, two a-edges running between them, and a b-loop at each vertex. Every vertex has exactly one edge of each label leaving it and one arriving, which is precisely the condition that makes the map down to the figure eight a covering rather than merely a map.

By the correspondence between coverings and subgroups, a connected covering with n sheets corresponds to a subgroup of index n: the subgroup of those loops downstairs whose lifts close up. So a subgroup of the free group on two letters, of index three, has been drawn. It is a graph.

The rank of a graph is a count #

The last ingredient is the easiest and does all the work. Take a connected graph and grow a spanning tree — start anywhere, keep adding edges that reach a new vertex, stop when every vertex is in. A tree on V vertices has V − 1 edges, and a tree has no loops at all, so it can be contracted to a point without changing anything about the loops of the graph.

Contract it. What remains is a wedge of circles, one for each edge that was not in the tree, so the fundamental group of a connected graph is free of rank E − V + 1. It is free because the contracted space is a wedge of circles, and its rank is a subtraction.

Put the three together. A subgroup of index n in the free group of rank k is the fundamental group of an n-sheeted cover of the wedge of k circles. That cover has n vertices and nk edges. So its rank is

$$nk - n + 1 = 1 + n(k-1),$$

and every subgroup of a free group, of finite index, is free of exactly that rank. The theorem for infinite index is the same argument with the word “finite” deleted: every covering of a graph is a graph, and every graph has a free fundamental group, whether or not the number of sheets is finite.

Reading the formula #

The formula is worth staring at, because it says three things at once.

A subgroup of index one is the group. Put n = 1 and the rank comes back as k.

A subgroup of finite index in a rank-one free group has rank one. Put k = 1 and the rank is 1 for every n, which is the statement that every subgroup of the integers is a copy of the integers — the fact the classification of covers of the circle already gave, arriving from the other side.

Above rank one, the rank grows without bound. Put k = 2 and the rank is n + 1, so the free group on two letters contains free subgroups of every finite rank, and by taking an infinite cover, one of infinite rank as well. A group with two generators contains a subgroup needing a million, and the subgroup satisfies no relation the group does not.

That is the part that reads as impossible until the picture is there. In a finite group nothing like it can happen — Lagrange’s theorem says a subgroup’s order divides the group’s, so a subgroup is smaller in the plainest sense. Freeness runs the other way: fewer relations means more room, and a subgroup of a free group has at least as few relations as the group, which is none. Nothing is left to stop the generators multiplying.

A subgroup written out #

The formula is a count, and a count can feel like a trick until the objects it counts are on the table. So here is the index-two subgroup of the free group on a and b, read off the two-sheeted cover drawn above.

Number the sheets one and two, and put the base point on sheet one. A loop downstairs lifts to a path upstairs starting at sheet one, and it belongs to the subgroup exactly when that path ends at sheet one as well. Since a swaps the sheets and b does not, a word ends where it started precisely when it contains an even number of as. That is the subgroup: all words of even a-length.

It is free of rank three, and the three generators can be read off the picture. The spanning tree is one of the two a-edges; the edges outside it are the other a-edge and the two b-loops, and each of those, closed up through the tree, is a word:

$$b, \quad aba^{-1}, \quad a^2.$$

Three words, no relation between them, and every even-a word is a product of these three and their inverses. A reader can check the last claim on any example — abab is $(aba^{-1}) \cdot a^2 \cdot b$, and $ab^{-1}a^{-1}b$ is $(aba^{-1})^{-1} \cdot b$ — and the check is the graph being walked, one letter at a time, with the current sheet deciding which generator the letter contributes.

Notice what happened to the rank: two generators went in and three came out, and the extra one is a², which exists only because a itself is not in the subgroup. The subgroup is smaller and its alphabet is larger, and both statements are about the same edge.

What the argument bought, and what it cost #

The combinatorial proofs of this theorem are not long, but they are fiddly in a specific way: they choose a set of coset representatives, they define a generating set from those choices, and they then have to show the result is independent of the choices. The covering proof has no choices in it at all until the very last step, where a spanning tree is grown — and the rank does not depend on which tree, because E − V + 1 does not mention the tree.

What was paid for that is a translation. The subgroup has to be recognised as a covering, which means the correspondence between subgroups and coverings has to be in place, and that correspondence is a substantial theorem in its own right. The economics are the usual ones for a good abstraction: an expensive construction once, then a series of cheap answers, and this is one of the cheap answers.

There is a second thing bought, and it is the reason the proof is remembered rather than merely correct. The construction is effective. Given a subgroup by its permutation action on cosets, the graph can be drawn, the tree grown, and the free generators read off as the edges outside it — each one a specific word in the original letters. The proof does not merely say a free basis exists; it hands one over.

Where it fails, and what it needs #

The theorem is about free groups and nothing else. A subgroup of a group given by generators and relations is not generally describable this way, and the corresponding covering space is not a graph. The statement “every subgroup of a group is a group of the same kind” is false for almost every kind of group anybody names.

The rank formula needs the cover connected. A covering by a disconnected graph is a covering by several graphs, and the index argument does not apply to it; the figures above check connectedness by walking the graph rather than assuming it. A disconnected cover corresponds not to one subgroup but to a family.

The finite-index formula needs finite index. For an infinite-index subgroup the theorem still says free, and says nothing about the rank, because E − V + 1 is a subtraction of infinities. The infinite cyclic cover of the figure eight is a free group of infinite rank, and there is no formula to check it against.

A basis is not unique, and the theorem does not pretend otherwise. A free group of rank three has infinitely many free bases, and different spanning trees of the same cover produce different ones. What the formula pins down is the number of generators, which is an invariant of the group; the generators themselves are a choice, in the same way that a basis of a vector space is.

And the correspondence itself has hypotheses. The classification of coverings by subgroups needs the base space to be connected, locally path-connected and semi-locally simply connected. A graph is all three, comfortably, which is why the proof runs so smoothly here and why the same manoeuvre elsewhere needs care.

Where it came from #

Nielsen proved the finitely generated case in 1921 by a length-reducing argument on words — take a generating set, replace a pair by a shorter product wherever possible, and show the process stops. It is an algorithm rather than a picture, and it is still the basis of the algorithms used today.

Schreier generalised it in 1927 by the coset-representative method, which is the one that appears in algebra courses. The topological proof came later still, and is usually credited to Reidemeister in the 1930s: it is the moment the fundamental group stopped being a tool for studying spaces and started being a thing spaces were used to study.

The reversal is worth noticing, because the whole subject has since gone that way. Groups given by generators and relations are hard to reason about directly; the same groups presented as the loops of a space are reasoned about by drawing. Geometric group theory is that observation taken seriously for eighty years, and Nielsen–Schreier is its founding example.

What the pictures cannot show #

The covers drawn here are finite, and every one of them is a choice of a subgroup rather than all of them. Two different permutation actions on the same number of sheets give different subgroups of the same index, and the figures draw one apiece.

The spanning tree is drawn solid and the remaining edges dashed, which suggests the free generators are the dashed edges. Strictly they are loops built from a dashed edge and the tree path back to the base point — the edge is the part that is not forced, and the tree path is bookkeeping. A reader who takes the dashed edges to be the generators has the count right and the objects slightly wrong.

And no figure here shows that the group downstairs is free. That was asserted, and the argument for it needs the universal cover, which is an infinite tree and cannot be drawn. Everything on this page is conditional on the fundamental group of a wedge of k circles being free of rank k, which is the one thing the pictures take on trust.

The ladder from here #

Below: the same loop, unrolled, where the correspondence between coverings and subgroups is set up, and the group drawn as a map, whose Cayley graph is the universal cover of the wedge when the group is free. Sideways: the blocks a subgroup cuts out, where index is counted in the finite world and behaves in the opposite way, and two trees, and every edge in exactly one of them, which is the same spanning-tree count doing different work. Above: the Kurosh subgroup theorem for free products, Stallings foldings, and the algorithmic questions the effective version opens.

What is worth carrying away #

The move is to stop asking what a subgroup is and start asking what space it is the loops of. Once the subgroup is a covering graph, every question about it becomes a question about vertices and edges, and vertices and edges can be counted.

The surprise the theorem produces — a subgroup with more generators than its group — survives the proof rather than being explained away by it, and that is a good sign. It says the intuition it violates was about the wrong kind of group. Size arguments work where there is size; freeness is an absence of relations, and absence does not divide.