Counting the subgroups of a free group

A covering is a permutation set up a dictionary. A covering of a figure-eight — the wedge of two circles, whose loops are the free group on two letters $a$ and $b$ — is described completely by saying where each loop sends each sheet: a pair of permutations of the sheets. A connected covering with a marked sheet is a subgroup, the words that bring the marked sheet back to itself, and the number of sheets is the subgroup’s index. That essay counted the connected coverings up to relabelling, three of two sheets and seven of three, and left the subgroups themselves for later.

This essay counts them, and the count is worth doing because it is exact, because it has a one-line recursion behind it, and because what it measures is startling: a group with two generators has more than thirty million subgroups of index ten.

From subgroups to pairs of permutations #

The translation needs one adjustment to count subgroups rather than coverings. A subgroup of index $n$ is a covering with $n$ sheets and a marked sheet: the subgroup is the set of words whose path from the marked sheet ends where it started. Two coverings give the same subgroup exactly when one can be relabelled into the other by a relabelling that keeps the mark where it is. So, writing the sheets as $1, \dots, n$ with sheet 1 marked:

A subgroup of index $n$ is then a pair of permutations $(\alpha, \beta)$ of $\{1, \dots, n\}$ that between them can take sheet 1 to every other sheet. Such a pair is called transitive, and transitivity is exactly what makes the covering connected: a covering in which some sheet cannot be reached from the marked one falls into pieces, and the words returning to the marked sheet only see the piece it lies in, which has fewer sheets.

Two transitive pairs give the same subgroup when they differ by a relabelling of sheets $2, \dots, n$, and there are $(n - 1)!$ such relabellings. None of them, apart from the identity, leaves a transitive pair unchanged: a relabelling that fixes sheet 1 and commutes with both permutations must fix every sheet that sheet 1 can reach, and in a transitive pair that is every sheet. So each subgroup is counted exactly $(n - 1)!$ times among the transitive pairs.

So the number of subgroups of index $n$ is $a_n = t_n / (n - 1)!$, where $t_n$ is the number of transitive pairs of permutations. Everything comes down to counting $t_n$.

For three sheets the figure shows the answer drawn. There are $3!^2 = 36$ pairs of permutations of three sheets; 26 of them are transitive; and $26 / 2! = 13$. The thirteen pictures are the thirteen subgroups. Ignoring which sheet is marked merges them into seven classes, which are the subgroups up to conjugacy, because moving the mark from one sheet to another changes the subgroup to a conjugate one — the words that return to the new sheet are the old ones read from a different starting point.

Hall’s recursion: sort every pair by how far one sheet travels #

Counting transitive pairs directly is a search through $(n!)^2$ pairs, which is 14,400 for five sheets and 13 billion for ten. Marshall Hall found in 1949 a way to count them by counting the pairs that are not.

Take any pair of permutations of $n$ sheets and ask which sheets sheet 1 can reach by applying $\alpha$, $\beta$ and their inverses: its orbit. Suppose the orbit has $k$ sheets. Then the pair, restricted to those $k$ sheets, is a transitive pair on them; restricted to the other $n - k$, it is any pair at all, because those sheets never interact with sheet 1. And the $k$ sheets can be any $k$ that include sheet 1. So the pairs whose orbit has exactly $k$ sheets number

$$\binom{n-1}{k-1}\, t_k\, \big((n-k)!\big)^2,$$

and since every pair has some orbit,

$$(n!)^2 = \sum_{k=1}^{n} \binom{n-1}{k-1}\, t_k\, \big((n-k)!\big)^2.$$

The last term, $k = n$, is $t_n$ itself, and everything else is known from smaller $n$. Subtract, and $t_n$ is found.

The figure carries it out for five sheets. Of the 14,400 pairs, 576 leave sheet 1 where it is — both permutations fix it, and the other four sheets are a free choice — 432 let it reach exactly one other sheet, 624 reach two others, and 1,704 reach three. The remaining 11,064 are transitive, and $11{,}064 / 4! = 461$.

This is the counting-two-ways habit applied to a classification: the total $(n!)^2$ is known, the parts are expressed through smaller cases, and the unknown part is the remainder. It turns a search through billions of pairs into a dozen multiplications.

The count, checked #

The recursion gives the sequence

$$a_n = 1,\ 3,\ 13,\ 71,\ 461,\ 3447,\ 29093,\ 273343,\ 2829325,\ 31998903,\ \dots$$

for $n = 1$ to 10. The figure checks the first five terms against brute force: every one of the $(n!)^2$ pairs is tested for transitivity directly, and the counts agree with the recursion exactly.

Brute force also finds what the recursion does not: the subgroups up to conjugacy, by putting every transitive pair into a canonical form under all relabellings and counting the forms. That gives 1, 3, 7, 26, 97 for $n = 1$ to 5 — the coverings without a mark, and the numbers the essay on coverings as permutations quoted. The two sequences are related but not by a simple division: a conjugacy class of index-$n$ subgroups has $n$ members unless the subgroup is conjugate to itself in more than one way, which is exactly the case where the covering has symmetries of its own, the deck transformations. Thirteen subgroups in seven classes means some classes are small: the four regular coverings with three sheets, whose subgroups are normal, are classes of one, and the other nine subgroups fall into three classes of three.

The index-two count can be checked a third way, without permutations. A subgroup of index two is the kernel of a map from the group onto the two-element group, and such a map is fixed by where it sends $a$ and $b$: four choices, one of them trivial, three subgroups. The index-three count has a similar check in the normal ones — kernels of maps onto the cyclic group of order three, of which there are $(9 - 1)/2 = 4$ — but the other nine are not kernels, and only the permutations see them.

Each of these subgroups is itself free. The subgroup that is freer than the group proved that a subgroup of index $n$ in the free group on two letters is free on $n + 1$ letters, by counting the edges and vertices of the covering graph. So the thirteen subgroups of index three are thirteen different copies of the free group on four letters sitting inside the free group on two, and the 461 of index five are copies of the free group on six.

Reading one subgroup off its picture #

Each drawing in the hero figure can be read back into a subgroup, and doing it once shows what the count is counting. Take the covering in which $a$ moves the sheets round in a cycle, $1 \to 2 \to 3 \to 1$, and $b$ leaves every sheet where it is. A word returns sheet 1 to itself exactly when its $a$’s, counted with sign, add to a multiple of three; the $b$’s do nothing. So the subgroup is the set of words whose exponent sum in $a$ is divisible by three, a normal subgroup, the kernel of the map to the integers modulo three that counts $a$’s.

Its free basis can be read off the picture too. Choose a tree in the covering graph — the $a$-edges from sheet 1 to 2 and from 2 to 3 — and every edge outside the tree gives one generator, the loop that runs out along the tree, across the edge and back. The edges outside the tree are the $a$-edge from 3 back to 1 and the three $b$-loops, so the generators are $a^3$, $b$, $a b a^{-1}$ and $a^2 b a^{-2}$: four of them, as the folding of graphs and the rank formula $1 + n(r - 1)$ both say they must be.

Every one of the thirteen pictures yields four generators the same way, and every one of the 461 subgroups of index five yields six. The count is therefore also a count of ways to sit a copy of a larger free group inside a smaller one with a given index, and the recursion is the only practical way to know how many there are.

Almost every pair is connected #

The recursion also says how much of the $(n!)^2$ the transitive pairs take up, and the answer is nearly all of it. For five sheets the share is 76.8 per cent; by forty sheets it is 97.4 per cent. The chance of failing is close to $1/n$, and the figure shows the exact values settling onto that line.

The reason is that one kind of failure dominates. If both permutations happen to fix the same sheet, that sheet is cut off from the rest; each permutation fixes a given sheet with chance $1/n$, so both do with chance $1/n^2$, and there are $n$ sheets to choose. Every other way of failing — two sheets swapped by both, a block of three closed under both — costs at least another factor of $n$. Two random shuffles reach every shuffle measured the same failures by sampling and found the same order: a shared fixed letter first, everything else much rarer. Here the share is exact, from a recursion, and at forty sheets it is $0.02570$ against $0.02569$ from the first three terms of the series $1/n + 1/n^2 + 4/n^3$.

That has a striking consequence for the count. Since almost all $(n!)^2$ pairs are transitive,

$$a_n = \frac{t_n}{(n-1)!} \approx \frac{(n!)^2}{(n-1)!} = n \cdot n!,$$

with a relative error of about $1/n$. The free group on two letters has about $n \cdot n!$ subgroups of index $n$, which for $n = 10$ is 36 million against the true 32 million. The count grows faster than any exponential, because the group, for all its two generators, has as many subgroups of a given index as there are ways to arrange the sheets.

More letters, more subgroups #

Nothing in the argument depended on there being two letters. A covering of a wedge of $r$ circles is $r$ permutations, the orbit of sheet 1 sorts them the same way, and Hall’s recursion runs with $(n!)^r$ in place of $(n!)^2$. The count is then about $n \cdot (n!)^{r-1}$.

With one letter the group is the integers, the recursion gives exactly one subgroup of each index — the multiples of $n$ — and a single permutation is transitive exactly when it is one cycle through all $n$ sheets, of which there are $(n - 1)!$. With three letters the counts start 1, 7, 97, 2,143, 68,641, and with four, 1, 15, 625, 54,335. Each extra letter multiplies the count by roughly another $n!$, which is the figure’s fan of lines.

The contrast with the free abelian group is instructive. The integers squared, $\mathbb{Z}^2$, also has two generators, and its subgroups of index $n$ number $\sigma(n)$, the sum of the divisors of $n$ — at most a small multiple of $n$, growing like $n \log \log n$. Two generators that commute leave room for almost nothing; two that do not leave room for $n \cdot n!$. The count of finite-index subgroups is a measure of how free a group is, and the free group sits at the top of that measure, since every two-generator group is a quotient of it and has at most as many subgroups of each index.

Where the free group sits among groups #

Counting subgroups of each index, for a group with finitely many generators, gives a sequence called its subgroup growth, and the sequence turns out to say a great deal about the group. The two ends are the ones measured here. A free group has the fastest growth any group with that many generators can have, about $n \cdot (n!)^{r-1}$, because every other group on $r$ generators is a quotient of it. The integers and the lattices $\mathbb{Z}^d$ have the slowest kind, polynomial in $n$, because their subgroups are cut out by integer matrices and there are only polynomially many of each determinant.

Between those ends the growth sorts groups into families. Alexander Lubotzky, Avinoam Mann and Dan Segal proved in 1993 that a finitely generated group whose subgroups can separate its elements has polynomial subgroup growth exactly when it is, up to a subgroup of finite index, built from abelian pieces in a controlled way — so a count of subgroups, read only for its rate, detects an algebraic property the count never mentions. Groups like the modular group, which contains a free group with finite index, inherit factorial growth from it; groups of matrices over the integers in higher dimensions grow at intermediate rates that depend on their arithmetic.

The free group is the reference point for all of this, and Hall’s recursion is why it is a usable one: for no other group with factorial growth is the count this easy to compute exactly. Most groups have to be approached through their quotients and the structure of their finite images, where for the free group the finite images are simply pairs of permutations, all of them allowed.

That is also the honest reason the topological picture matters here. The algebra of a free group gives no direct handle on its subgroups of index five. The covering picture turns each one into a finite object — five sheets, two permutations — and the count into a question about finite objects, which a recursion can answer. It is the same move covering spaces have made from the start, unrolling a loop into a path, carried to the point where it produces a number.

What the computation does and does not see #

The recursion is exact for every $n$ and needs only whole-number arithmetic, which the figures do without rounding to forty sheets. Its derivation rests on one fact — that a pair restricted to an orbit is transitive there, and restricted to the complement is arbitrary — and the brute-force check to five sheets tests that fact on every pair rather than taking it on trust.

The conjugacy classes are counted only to five sheets, because the canonical form needs every relabelling of every transitive pair, about $n!$ times the work of the recursion’s whole table. Beyond that they can be counted by Burnside’s lemma over the symmetric group, and the figures do not attempt it.

The drawings of the thirteen subgroups are the coverings themselves, not a schematic; each is checked to be connected and to differ from the others under every relabelling that keeps the mark.

Still open: subgroups of a surface group #

The same question can be asked of the fundamental group of a closed surface, the group covering a surface multiplies its count worked with, where the generators must satisfy one relation. The count of index-$n$ subgroups is then known exactly through a formula of Alexander Mednykh, a sum over the characters of the symmetric group of the kind a count that can say zero used for branched coverings, and its growth is again factorial, with the exponent set by the surface’s Euler characteristic.

What is not well understood is the finer statistics: how the subgroups of a given index are distributed by the shape of their coverings, how many are normal, and how these change as the index grows. For the free group the random-pair picture answers such questions, since almost every pair is a typical covering; for surface groups, where the pairs are constrained by the relation, the corresponding random model is harder to sample and its typical behaviour is a subject of current work.