# Finding subgroups of a free group with a specific index

How many subgroups with index two are there of a free group on two generators? What are their generators?

All I know is that the subgroups should have $(2 \times 2) + 1 - 2 = 3$ generators.

Mariano's answer is quite right, but relies on the 'accident' that all subgroups of index two are normal. If you wanted to find all the subgroups of index three, say, you would need to try another approach. Here's one idea.

The free group of rank two, $F$, is the fundamental group of the figure-eight graph $\Gamma$, which has one vertex and two edges. Fix the vertex as the base point. The subgroups of index $k$ correspond, via covering-space theory, to connected covering spaces $\widehat{\Gamma}\to\Gamma$ of degree $k$, with a choice of base vertex $\hat{v}\in\widehat{\Gamma}$. (If, on the other hand, you only wanted to count conjugacy classes of subgroups, you could forget about $\hat{v}$.) Because the covering map $p:\widehat{\Gamma}\to\Gamma$ has degree $k$, the graph $\widehat{\Gamma}$ has exactly $k$ vertices.

Let's decorate the graph $\Gamma$ so that we can see $F=\langle a,b\rangle$ more clearly. Label each edge with the corresponding generator $a$ or $b$. Furthermore, orient each edge to indicate in which direction the generator goes around it.

You can use the covering map $p$ to pull the labels and orientations back from $\Gamma$ to $\widehat{\Gamma}$. That is, if $\hat{e}$ is an edge of $\widehat{\Gamma}$ and $p(\hat{e})=e$ is labelled $a$, then you should label $\hat{e}$ with $a$ also, and orient $\hat{e}$ so that $p$ sends the orientation on $\hat{e}$ to the orientation on $e$.

With a little thought, it's not too hard to see that this decoration on $\widehat{\Gamma}$---the labels and orientation---are enough to reconstruct the map $p$: they tell you where to send each edge, and there's only one choice of where to send each vertex. The statement that $p$ is a covering map translates into a nice condition on the decoration of $\widehat{\Gamma}$: for each vertex $\hat{u}$, you see exactly one edge with label going into $\hat{u}$, and exactly one edge with each label going out of $\hat{u}$. I'll call this condition 'the covering condition'.

This discussion turns counting the subgroups of index $k$ into the combinatorial problem of counting the connected, decorated, based graphs $\widehat{\Gamma}$ with $k$ vertices that satisfy the covering condition. With a little thought, one can write down a formula for this. Marshall Hall Jr did just this (though I don't think he thought in terms of the covering spaces of graphs) and came up with the following formula. Let $N(k,r)$ be the number of subgroups of index $k$ in the free group of rank $r$. Then

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

For some related things, I wrote a blog post about proving theorems about free groups by thinking about covering spaces of graphs here.

Alternatively, if you don't like covering spaces, an equivalent point of view is to count transitive actions by permutation groups with $r$ generators on based sets of size $k$. This turns out to be the same combinatorial problem.

• A nice superset of my answer. – Cheerful Parsnip Nov 10 '10 at 15:18
• I'm surprised you don't mention your blog/class at 392c.wordpress.com/2009/01/01 , where I first was able to understand this and many other geometric approaches to combinatorial group theory. :-) – user641 Nov 10 '10 at 15:56
• Aw, shucks. That blog was entirely written by my class, so I tend to forget what was in it. Thanks for the props, though! I'm very proud of them. – HJRW Nov 10 '10 at 18:30

Let $F$ be free on $a$ and $b$, and let $N$ be a subgroup of index $2$. Then $N$ is normal, and there is a map $\phi:F\to\mathbb Z/2\mathbb Z$ with kernel precisely $N$. What are the possible images of $a$ and $b$? For each possible choice you can describe the corresponding generators of $N$ as a normal subgroup, and with a little extra work, generators as subgroup.

I like to approach this sort of problem using graphs. The free group on two generators is the fundamental group of a wedge of two circles $R_2$, which I picture as a red oriented circle and a black oriented circle. A subgroup of index $k$ corresponds to a covering map $G\to R_2$ of index $k$. $G$ can be pictured as a (Edit: basepointed) $k$-vertex connected graph with red and black oriented edges such that at every vertex there is one incoming and one outgoing edge of each color. In the case $k=2$, it's not hard to write down all such graphs. I count three myself.

• In general, you also need to count base points. (This doesn't arise in index two because all the covers are regular.) – HJRW Nov 10 '10 at 14:59
• Of course. Thanks for the clarification! – Cheerful Parsnip Nov 10 '10 at 15:15
• You get to choose the basepoint. You could choose it elsewhere in $R_2$, but this makes things very convenient. – Cheerful Parsnip Nov 10 '10 at 16:17
• You need to look at the possible preimages in $G$ of the chosen basepoint of $R_2$. (The covering map preserves basepoints.) – Cheerful Parsnip Nov 10 '10 at 16:32
• letiitbe: Jim has it. You fix a base point $v\in R_2$ - it's convenient to choose the vertex, but it could be anything. For a covering space $G$ you need to choose a base point $\hat{v}$ to talk about $\pi_1(G,\hat{v})$, and for the covering map to induce a well-defined map on $\pi_1$ you need to choose $\hat{v}$ in the preimage of $v$. So in any case, the number of choices you have is precisely equal to the degree of the covering. If you chose $v$ to be the vertex of $R_2$ then the valid choices for $\hat{v}$ are precisely the vertices of $G$. Does that make sense? – HJRW Nov 10 '10 at 18:27