The subgroups of a surface group

Counting the subgroups of a free group found that the free group on two letters has 1, 3, 13, 71, 461 subgroups of index 1 to 5, by a recursion of Marshall Hall’s that sorts every pair of permutations by how far one sheet travels. The free group is the fundamental group of a figure eight, and its coverings are pairs of permutations with no condition at all. That essay ended on the question for closed surfaces, where the generators must satisfy a relation: the group of the genus-$g$ surface is generated by $a_1, b_1, \ldots, a_g, b_g$ subject to

$$[a_1, b_1][a_2, b_2]\cdots[a_g, b_g] = 1,$$

the boundary of the single face that every surface is a sphere with handles glued from a polygon. A relation makes Hall’s recursion useless, because the permutations can no longer be chosen independently. The count becomes a question about how often a product of commutators is the identity — and that is a question the characters of the symmetric group answer exactly.

From subgroups to permutations #

Covering a surface multiplies its count built the coverings explicitly. Number the sheets $1, \ldots, n$; walking once round each handle’s loop moves a point on one sheet to a point on another, so each generator becomes a permutation of the sheets; and since the boundary of the face can be shrunk to a point, the product of the commutators of those permutations must leave every sheet where it was. Conversely, any $2g$ permutations whose commutators multiply to the identity build an $n$-sheeted covering. So the coverings with numbered sheets are exactly the homomorphisms from the surface group to the symmetric group $S_n$.

Subgroups come from the connected ones. A covering is connected when the permutations can carry every sheet to every other — when they generate a transitive group — and a connected covering with a marked sheet over a marked point corresponds to exactly one subgroup of index $n$, the loops that lift to closed loops on the marked sheet. Each subgroup arises from $(n - 1)!$ transitive homomorphisms, one for each way of numbering the other sheets. So the number of subgroups of index $n$ is the number of transitive solutions of the commutator equation, divided by $(n - 1)!$, and the whole problem is to count solutions.

Counting all solutions is the hard part and the elegant one; separating the transitive ones is bookkeeping. If $h_n$ is the number of solutions divided by $n!$, then

$$\sum_{n \ge 0} h_n x^n = \exp\Big(\sum_{k \ge 1} \frac{a_k}{k} x^k\Big),$$

where $a_k$ is the number of subgroups of index $k$, because an arbitrary covering is a disjoint union of connected ones and the exponential generating function of a set of pieces is the exponential of the generating function of a piece. Differentiating gives the recursion $n h_n = \sum_k a_k h_{n-k}$, and the hero’s table is that recursion run on the counts below.

Characters count the solutions #

In 1896 Georg Frobenius found how many ways a product of commutators can equal a given element of a finite group. For the identity in the symmetric group the answer is

$$\#\{(a_1, b_1, \ldots, a_g, b_g) : [a_1, b_1]\cdots[a_g, b_g] = 1\} = n!\sum_{\lambda} \left(\frac{n!}{f_\lambda}\right)^{2g-2},$$

the sum running over the partitions $\lambda$ of $n$, with $f_\lambda$ the dimension of the corresponding irreducible character of $S_n$. Alexander Mednykh used this in 1979 to count the coverings of surfaces, and the number $n!/f_\lambda$ is a product of hook lengths: draw the Young diagram of $\lambda$, and for each box count the boxes to its right and below it, plus one; the product of these is $n!/f_\lambda$, the formula of Frame, Robinson and Thrall. So the whole count needs nothing but the shapes of the partitions of $n$, each contributing the product of its hook lengths raised to the power $2g - 2$.

Two consequences are visible at once. For the torus, $g = 1$, the exponent is nought, every term is 1, and the number of solutions is $n!$ times the number of partitions of $n$. For the sphere, $g = 0$, the exponent is $-2$, the terms are $f_\lambda^2/(n!)^2$, and their sum is $1/n!$ by the classical identity $\sum f_\lambda^2 = n!$ — one solution, the empty one, as there should be for a sphere, which has no coverings but trivial ones.

The formula against every quadruple #

A formula drawn from representation theory deserves a direct check, and for small symmetric groups every quadruple of permutations can be tried. The figure does it for genus two, where the equation is $[a, b][c, d] = 1$. In $S_3$, whose characters have dimensions 1, 2 and 1 for the partitions 3, 21 and 111, the formula predicts $6 \cdot (6^2 + 3^2 + 6^2) = 486$ solutions among the $6^4 = 1{,}296$ quadruples; trying them all finds 486. In $S_4$, with dimensions 1, 3, 2, 3, 1, it predicts 34,176 of the 331,776 quadruples, and the search agrees.

The check also explains how the formula works. Tabulate, for each permutation $c$, how many pairs $(a, b)$ have commutator $c$; a solution of $[a, b][c, d] = 1$ is a pair of pairs whose commutators are inverse to each other, so the count is a sum of products of those tallies. Frobenius’s insight was that the tally of commutators is a combination of characters with coefficients $1/f_\lambda$, and that combinations of characters multiply by multiplying coefficients — which is why each handle contributes another factor of $(n!/f_\lambda)^2$ and the exponent is $2g - 2$.

The torus and the partitions #

The torus case is old and pretty, and the figure checks it from scratch. Its group is $\mathbb{Z}^2$, generated by two commuting loops, so a covering is a pair of commuting permutations. For $n$ from 1 to 6, the figure tries every pair in $S_n$ and counts the commuting ones: 1, 4, 18, 120, 840, 7,920, which are $1 \cdot 1$, $2 \cdot 2$, $6 \cdot 3$, $24 \cdot 5$, $120 \cdot 7$, $720 \cdot 11$ — $n!$ times the number of partitions of $n$. The count has a direct reason as well: the number of commuting pairs in any finite group is the group’s order times its number of conjugacy classes, and the classes of $S_n$ are the cycle types, one for each partition.

Running the exponential bookkeeping on $n!\,p(n)$ leaves the subgroups, and they are counted by $\sigma(n)$, the sum of the divisors of $n$: 1, 3, 4, 7, 6, 12. That is a theorem about lattices — every subgroup of index $n$ in $\mathbb{Z}^2$ has a basis $(a, 0), (b, d)$ with $ad = n$ and $0 \le b < a$, so there are $\sum_{a \mid n} a = \sigma(n)$ of them — and the formula recovers it from the partitions without knowing anything about lattices. The partitions of $n$, which a diagram turned on its side studied as Ferrers diagrams, and the divisors of $n$ are tied together by the covering spaces of the torus, through the identity $\sum p(n)x^n = \exp\big(\sum \sigma(n)x^n/n\big)$ that Euler would have recognised.

Handles multiply the count #

The first figure’s table shows how fast the counts grow. The genus-two surface has 15 subgroups of index 2, 220 of index 3, 5,275 of index 4 and 26,370,058,035 of index 8; genus three has 63, 7,924, 2,757,307 and, at index 8, $42{,}295{,}362{,}888{,}015{,}649{,}395$. The free group on two letters, whose figure eight has the same Euler characteristic $-1$ as a torus with a puncture, has far fewer: 273,343 at index 8. A relation would seem to cut the count down, since it forbids most choices of permutations; but a surface of genus two has four generators to the free group’s two, and the relation removes only one generator’s worth of freedom. The genus-two count is like a free group on three letters, not two.

Index-$n$ subgroups of the genus-$g$ group are the fundamental groups of the connected $n$-sheeted coverings, which are themselves surfaces, of genus $n(g - 1) + 1$ by the multiplicativity of the Euler characteristic. So the counts in the table are also counts of surfaces: the 220 subgroups of index 3 in the genus-two group are the 220 ways, up to marking, that a surface of genus four can wrap three times around a surface of genus two without branching.

Almost every covering is connected, almost all from two characters #

Two facts make the counts simple for large $n$, and the figure watches both arrive. The first is that almost every solution is transitive: the share of homomorphisms to $S_n$ that give a connected covering is 0.94 at two sheets, dips, and then climbs to 0.9989 at thirty. That is the surface-group version of John Dixon’s theorem of 1969 that two random permutations almost surely generate a transitive group, and in fact all of $S_n$ or $A_n$; four permutations constrained by one relation are still random enough.

The second is that almost all of Frobenius’s sum comes from two terms. The characters of dimension one, for the partitions $(n)$ and $(1^n)$ — the trivial character and the sign — have $f_\lambda = 1$, so they contribute $(n!)^{2g-2}$ each, the largest possible terms. Every other partition has $f_\lambda \ge n - 1$ and contributes at most $(n!/(n - 1))^{2g-2}$, smaller by a power of $n$. At thirty sheets the two largest terms account for 0.9988 of the whole. So the number of solutions is close to $2(n!)^{2g-1}$, and since almost all are transitive, the number of subgroups is close to

$$2n\,(n!)^{2g-2}.$$

Against the asymptotic formula #

Thomas Müller and Jan-Christoph Puchta proved in 2002 that the number of subgroups of index $n$ in the genus-$g$ surface group is asymptotic to $2n(n!)^{2g-2}$, and the figure divides the exact counts by it. For genus two the ratio overshoots to about 1.13 at index 4, settles, and is $1.00008$ at index 30; for genus three and four it is $1.00000$ to five places well before that. More handles make the convergence faster, because the exponent $2g - 2$ magnifies the gap between the two dominant terms and the rest.

The asymptotic has a clean reading. The Euler characteristic of the genus-$g$ surface is $2 - 2g$, and the count grows like $(n!)^{-\chi}$ up to the factor $2n$: the number of ways to cover a surface with $n$ sheets is controlled by how negative its Euler characteristic is, exactly as the Euler characteristic of the cover is $n$ times the base’s. The free group, with $\chi = -1$, grows like $n \cdot n!$, which Hall’s numbers confirm; the torus, with $\chi = 0$, grows like $\sigma(n)$, only polynomially; and each further handle multiplies the growth by another $(n!)^2$.

The one-sided surfaces, and a count of involutions #

The non-orientable surfaces have their own version of the formula, and its first case is a small surprise. The projective plane, which a disc sewn to a Möbius band built from a disc and a band, has a fundamental group with one generator $x$ and the relation $x^2 = 1$; the surface made from $k$ cross-caps has generators $x_1, \ldots, x_k$ and the relation $x_1^2 x_2^2 \cdots x_k^2 = 1$. Frobenius and Issai Schur counted the solutions of that equation too. In a group whose characters are all real, as those of $S_n$ are, the number of solutions is

$$n!\sum_\lambda \left(\frac{n!}{f_\lambda}\right)^{k-2},$$

the same shape as before with $2g$ replaced by $k$ — the Euler characteristic of the $k$-cross-cap surface is $2 - k$, so the exponent is again minus the Euler characteristic. At $k = 2$, the Klein bottle, every term is 1 and the count is $n!\,p(n)$, exactly as for the torus: the two surfaces with Euler characteristic nought have the same number of coverings with numbered sheets, though not the same coverings, and their subgroups of each index are therefore equal in number too. At $k = 1$ the exponent is $-1$, each term is $f_\lambda/n!$, and the formula becomes simply $\sum_\lambda f_\lambda$.

That case counts the permutations with $x^2 = 1$, the involutions of $S_n$ together with the identity, and says their number is $\sum_\lambda f_\lambda$, the total number of standard Young tableaux with $n$ boxes. For $n = 4$ that is $1 + 3 + 2 + 3 + 1 = 10$, and $S_4$ has exactly ten elements whose square is the identity: the identity, six transpositions and three products of two disjoint transpositions. The identity is one of the classical consequences of the Robinson–Schensted correspondence, which pairs each permutation with two tableaux of the same shape and each involution with one; here it falls out of counting the coverings of the projective plane. The coverings of a one-sided surface are counted by tableaux, and the coverings of a two-sided one by tableaux squared, raised to a power set by the number of handles.

Counted, never listed #

The counts are exact integers: the hook products are exact, their powers and sums are computed in whole-number arithmetic, and the exponential bookkeeping divides only where the result is known to be whole. The formula is checked against an exhaustive search in $S_1$ to $S_4$ for genus two and $S_1$ to $S_6$ for the torus, and the torus counts are checked against $\sigma(n)$ and the free-group counts against Hall’s. The share and growth figures go to index 30, where the partitions number 5,604 and the integers have hundreds of digits.

Nothing here describes the subgroups themselves. The formula counts them without listing any; it does not say how many are normal, which coverings are regular, or how the coverings’ own symmetry groups are distributed. Nor does it extend directly to surfaces with boundary or punctures, whose groups are free, or to non-orientable surfaces, whose relation is a product of squares and whose count uses a different sum — Frobenius and Schur’s, with signs from the real or quaternionic type of each character.

Still open: the shape of a typical covering #

For the free group, the free-group essay noted that random pairs of permutations describe a typical covering well, and that the coverings’ finer statistics follow from that model. For surface groups the analogous statement is harder: a typical index-$n$ subgroup comes from a random solution of the commutator equation, and how the cycle structures of its permutations, the symmetries of its covering, or the lengths of its shortest closed curves are distributed is known only in part. Results of Doron Puder, Michael Magee and others in the last decade have shown that random coverings of a hyperbolic surface have spectral gaps close to optimal — that their Laplacian’s smallest non-zero eigenvalue approaches the largest value the base allows — through the same character sums that count them here; but the full distribution of that eigenvalue, and of most other geometric invariants of a random covering, is still being worked out.

There is also a counting question closer to the formula. Mednykh’s sum, and Frobenius’s behind it, extend to branched coverings, where a count that can say zero found the Hurwitz existence problem lurking: for some branch data the count is nought, and deciding which is subtle. For unbranched coverings the count is never nought, since the trivial covering always exists, but a refined count — of coverings whose monodromy group is all of $S_n$, or of regular coverings with a given group — has no closed form, and computing it needs the full character table of the group, not just its dimensions, as when the label may be a matrix built it for $S_n$.

A relation counted by characters #

A connected $n$-sheeted covering of the genus-$g$ surface is a transitive choice of $2g$ permutations whose commutators multiply to the identity, and Frobenius’s formula counts all choices as $n!\sum_\lambda (n!/f_\lambda)^{2g-2}$, which needs only the hook lengths of the partitions of $n$. It gives the torus $n!$ times the partitions of $n$ and so $\sigma(n)$ subgroups of index $n$; it gives the genus-two surface 15, 220, 5,275, 151,086, and it agrees with every quadruple of permutations tried in $S_4$. As $n$ grows, almost every covering is connected and almost the whole sum comes from the two characters of dimension one, so the count approaches $2n(n!)^{2g-2}$ — a growth set by the surface’s Euler characteristic, which each handle makes another factor of $(n!)^2$ steeper.