9
$\begingroup$

Given $n,d\in \mathbb{Z}^+$, how many subgroups of index $d$ does the free group of rank $n$ have?

In case $n=1$ the question is trivial, and in case $n=2, d=2$ there are 3 such subgroups. I think I have got a algorithm to solve case $d=2$ for arbitrary $n$. But the general case seems very difficult. For example in case $n=2$ and $d$ a prime number, I don't know how to proceed.

That's my question. Any suggestions will be appreciated. Thanks

$\endgroup$
15
$\begingroup$

This calculation was performed by Marshall Hall Jr. Let $N(d,n)$ be the number of subgroups of index $d$ in the free group of rank $n$. Then

$N(d,n)=d(d!)^{n-1}-\sum_{i=1}^{d-1}((d-i)!)^{n-1}N(i,n)$.

One can prove this inductively by analysing permutation groups as in abx's answer, or alternatively by thinking about covering spaces of graphs---see the answers to this question on MSE for a few more details.

$\endgroup$
  • 2
    $\begingroup$ A more elegant way of stating Hall's result is $\log\sum_{d\geq 0} d!^{n-1} x^d= \sum_{d\geq 1}N(d,n)\frac{x^d}{d}$. See Enumerative Combinatorics, vol. 2, Exercise 5.13 for this and related results. $\endgroup$ – Richard Stanley Feb 25 '14 at 21:33
  • $\begingroup$ That's very nice! $\endgroup$ – HJRW Feb 26 '14 at 10:14
7
$\begingroup$

This is a very incomplete answer. The case $d=2$ is particular because a subgroup of index 2 is normal. In this case subgroups of order 2 of $F_n$ correspond bijectively to surjective homomorphisms $F_n\rightarrow \mathbb{Z}/2$. Such a map factors through the abelian quotient $\mathbb{Z}^n$, thus there are $2^n-1$ subgroups of index 2 of $F_n$.

In general subgroups of index $d$ of $F_n$ correspond to $n$-uples of permutations $(\sigma _1,\ldots ,\sigma _n)$ in $\mathfrak{S}_d$ such that the subgroup they generate acts transitively on $[1,d]$, up to conjugacy by $\mathfrak{S}_{d-1}$. They also correspond to $d$-sheeted covering of the sphere branched along $\{1,\ldots ,d\} $. This is reminiscent of Hurwitz numbers though it does not seem to be directly related.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.