18
$\begingroup$

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.

3 Answers 3

25

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.

  • 2
    A nice superset of my answer.2010-11-10
  • 1
    I'm surprised you don't mention your blog/class at http://392c.wordpress.com/2009/01/01/ , where I first was able to understand this and many other geometric approaches to combinatorial group theory. :-)2010-11-10
  • 0
    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.2010-11-10
10

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.

8

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.

  • 0
    In general, you also need to count base points. (This doesn't arise in index two because all the covers are regular.)2010-11-10
  • 0
    Of course. Thanks for the clarification!2010-11-10
  • 0
    Henry, would you mind explaining the issue with base points? How do one for example count them when there are infinitely many of them (every edge/circle contains infinitely many points)? Actually I know, from reading your post, that you seem to only consider the (finitely many) vertices as base points, but why only them?2010-11-10
  • 0
    The basepoint of $G$ has to be a vertex because it has to be a preimage of the basepoint of $R_2$ which is its unique vertex.2010-11-10
  • 0
    Sorry, I meant to ask why a basepoint of $R_2$ must be a vertex. $R_2$ is the wedge of two circles so why cant any point on either of the circles be used as the base point?2010-11-10
  • 1
    You get to choose the basepoint. You could choose it elsewhere in $R_2$, but this makes things very convenient.2010-11-10
  • 0
    But then how does Henry's comment on needing to count the base points fit in to this all? If any point can be taken as the base point, then there are infinitely many base points to count. What if we looked at index 3 subgroups, what problems would we get if we don't "count" the base points?2010-11-10
  • 1
    You need to look at the possible preimages in $G$ of the chosen basepoint of $R_2$. (The covering map preserves basepoints.)2010-11-10
  • 1
    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?2010-11-10
  • 0
    @CheerfulParsnip Hi, could you better explain why a two-sheet covering space on $\mathbb{S}^1\vee\mathbb{S}^1$ corresponds to a graph with two vertices?2018-05-03