# Gracious Living

Subgroups of Free Groups are Free
December 28, 2010, 07:32
Filed under: Algebra, Math | Tags: , , , , ,

Okay, first post for a while.  As I promised quite a while back, let’s prove together that subgroups of free groups are free.  It’s surprising that this is nontrivial to prove: just try to come up with some subgroups of $F_2$ and you’ll see what I mean.  In fact, using only basic algebraic topology and a bit of graph theory, we can come up with a really simple argument that replaces this one.  Perhaps that’s an argument in favor of algebraic topology.  But I think this angle is sort of interesting, and it should be a fresh experience for me, at least.

The proof is due to Jean-Pierre “Duh Bear” Serre in his book Trees.  A heads up if you track this down — Serre has a really weird way of defining graphs.  Fortunately, for this proof at least, a little bit of work translates things into the same language of graphs and digraphs that we saw when talking about Cayley graphs.  I review that below the fold.  It takes a while to set up the machinery, though the proof itself isn’t too long.  To recompense, I’ve left out a couple minor details, which you’re probably able to fill in.  If some step doesn’t make sense, work it out — or try to disprove it!

A graph is a set of “vertices” and a set of “edges,” with each edge connected to two vertices.  A digraph or oriented or directed graph is the same thing, but the edges “point” in one direction: we can then talk about the beginning and end of a certain edge, the vertex it’s going to and the vertex it’s leaving respectively.  Note that we can make one into the other: given a digraph, if you forget which of the two vertices connected to each edge is its beginning and which its end, you’ve got yourself a graph, and given a graph, you can “orient” it by picking a beginning and end of each edge.  In addition, a graph can be made into a topological space: orient it, start with the space $V\sqcup (E\times[0,1])$, and use quotients to glue $(y,0)$ to the beginning of $y$ and $(y,1)$ to its end, for each edge $y$.  Ordinarily, we draw graphs as points for the vertices with little lines going between them for the edges, with arrows if the graph is oriented.  For our purposes, we will allow multiple edges between the same two vertices, and “loops” from one vertex to itself.

Graph theory is the study of these things.  Sometimes it asks topological questions, like whether all graphs can be embedded in the plane (the gas-water-electricity puzzle being a well-known counterexample).  More often, though, the questions are combinatorial — how many graphs are there with a certain  number of vertices, or how can you get from one vertex to another, and so on.  Serre’s idea was to use graphs to study groups, leading to what’s apparrently called “Bass-Serre Theory”.

The next couple of definitions should be pretty easy to think about by now.  A subgraph of a graph has a subset of its vertices and a subset of the edges connecting those vertices.  A graph map between two graphs sends the vertices of the first to the vertices of the second, the edges of the first to the edges of the second, and ensures that the image of an edge is attached to the images of the vertices the original edge was attached to.  It’s basically a continuous map that sends vertices to vertices and edges to edge, if we think of a graph as topological.  A graph isomorphism is a graph map with an inverse.  Obviously, graph isomorphisms are just graph maps that are bijective on vertices and edges.  We can also talk about paths, which are, well, paths from one vertex to another using edges; a path of length $n$ is the image of the graph with $n$ vertices attached in a row under a graph map.  We require all paths to be of finite length. A graph is connected if there’s a path between any two of its vertices: equivalently, if it’s path-connected as a topological space.  A cycle is just a path from a vertex to itself.  The most important kind of graph, for us, is a tree — a connected graph that has no cycles.  They’re called trees because they look like trees, which is in turn because tree branches don’t grow in circles, for the most part.

Now, we’ve already seen one kind of graph — the Cayley graph of a group.  To be a bit more precise, let $G$ be a group and $S$ a subset.  The Cayley graph $\Gamma(G,S)$ is the oriented graph with a vertex for each element of $G$ and an edge from $g$ to $sg$ for each $s\in S,g\in G$.  One easy thing to prove is that $\Gamma(G,S)$ is connected iff $S$ generates $G$.  Relations between elements of $S$, meanwhile, correspond to cycles in the graph: how exactly?  What does it look like if $e\in S$?

At right is $\Gamma(F_2,\{a,b\})$, and it should give you an idea of how other Cayley graphs of free groups look.  It’s a fractal, which means that as you zoom in on any other vertex, you get a picture that looks just like the one we see here centered on $e$.  In particular, though it’s drawn here in a small space, it’s not actually compact; the sequence $a,a^2,a^3,\dotsc$ shoots infinitely far out to the right.

Now, we want to talk about groups acting on graphs.  By this we mean that the action of each group element is a graph map from the graph to itself: equivalently, there is a group action on the set of vertices and on the set of edges such that if we act on both by the same element, edges stay attached to the right vertices.  There are two important properties of these actions that we want.  First, an action is free if group elements other than the identity don’t fix any vertex.  (This is a term used for group actions without a fixed point on any sort of set, actually.)  Second, an action is without inversions if, when we orient the graph, we don’t end up sending an edge to the same edge backwards with any group element.  This is important because if this does happen, then we’ll end up fixing a point in the topological version of the graph: namely, the midpoint of that edge.  So to ensure that our actions really don’t fix anything, we require them to be free and without inversions.  As an exercise, prove that an action is without inversions iff there’s a way of orienting the graph so that the action keeps the arrows pointing the same direction.

Now, each group acts on its Cayley graph by right multiplication.  The element $h$ sends the vertex $g$ to $gh$, and the edge from $g$ to $sg$ to the edge from $gh$ to $sgh$.  This is clearly free because $gh=g$ only when $h=e$; likewise, it’s without inversions because if $gh=sg,sgh=g$, then $g=sgh=s^2g$ so $s^2=e$.  But then the Cayley graph has two edges between $g$ and $sg$, one going each direction, and acting with $h$ just switches them, rather than sending an edge to its reverse.  Likewise, subgroups act on the same Cayley graph, and this is still free and without inversions.

But the Cayley graph of a free group is a tree, because the group has no nontrivial relations.  So subgroups of free groups act freely and without inversions on trees.  So all we need to prove is that any group that acts freely and without inversions on a tree is free!

Given an action without inversions of $G$ on a graph $X$, we can define its “quotient tree,” $X/G$.  This has a vertex for every orbit of the vertices $X$ (the set of vertices you can get to by acting on a single vertex with all the elements of $G$), and an edge for every orbit of the edges, connected to the corresponding orbits of the vertices.  I leave it to you to prove this is well-defined.  Obviously sending each (vertex, edge) to its orbit gives you a surjective graph map from $X$ to $X/G$.  We say that a subgraph $Y$ of $X/G$ lifts to $X$ if there is a subgraph of $X$, isomorphic to $Y$, whose image is also $Y$ under the projection.  At right is an example from Serre of a graph surjection that doesn’t allow a lifting. Then we have the following:

• Proposition.  Let $G$ act without inversion on a connected graph $X$. Then every subtree of $X/G$ (a subgraph that’s also a tree) lifts to a subtree of $X$.

Proof. A high-level application of Zorn’s Lemma! Let $T^\prime$ be a subtree of $X/G$, and let $\Omega$ be the set of subtrees of $X$ whose images under the projection are in $T^\prime$ and isomorphic to themselves. Inclusion is a partial order on this set, and given a totally ordered subset, its union is an upper bound of that set (you can’t make a non-tree out of a union of infinitely many trees because that would require a cycle of infinite length, which we don’t allow).  So there’s a maximal element of $\Omega$, say $T_0$.  I claim $T_0$ is a lift of $T^\prime$.  Suppose not; then there’s an edge in $T^\prime$ not belonging to the image of $T$.  By connectedness, at least one such edge has one endpoint in the image $T_0^\prime$ of $T_0$, and the other endpoint can’t be in $T_0^\prime$, because if so, we would have a cycle in $T^\prime$ given by going along this edge and then going back to the beginning along edges of $T_0^\prime$.  Let $y^\prime$ be such an edge and $y$ a lift of this edge.  Obviously, $gy$ for $g\in G$ is also a lift of $y^\prime$, so we can “translate” $y$ so that it’s attached to $T_0$ again.  By the above reasoning, its other end can’t be in $T_0$, but then adding it to $T_0$ gives a bigger tree that still projects to a tree in $T^\prime$.  This is a contradiction, so $T_0^\prime=T^\prime.$ $\square$

We’ll call a lift of a maximal subtree of $G/X$ (one to which you can’t add an edge without creating a cycle) a tree of representatives of $X$ with respect to $G$.

• Theorem.  Let $G$ act freely and without inversions on a tree $X$, and let $T$ be a tree of representatives of this action.  Give $X$ an orientation that’s preserved by $G$.  Let $S$ be the set of elements $g\ne e$ in $G$ such that there is an oriented edge from $T$ to $gT$ in $X$.  Then $X$ is free and $S$ is a minimal generating set.

Proof.  First see that $T$ has at most one point from each orbit.  So all the “translates” of $T$ by elements of $G$ are disjoint.  We can make a new graph, $X^\prime$, by quotienting out each translate: this graph has a vertex for every translate $gT$ and an edge for each edge between two translates.  You can check that this new graph is still a tree and that $G$ still acts on it freely and without inversions, preserving the induced orientation.  In addition, its vertices are in bijection with the elements of $G$, and acting by $h$ will send the vertex corresponding to $gT$ to that corresponding to $ghT$.  Basically, what we’re going to show is that this graph is isomorphic to $\Gamma(G,S)$, where $S$ is as above.  We have a bijection on vertices, so we just need to make sure that it works on edges.

But by definition, if we have an edge $y^\prime$ between $(gT)$ and $(hT)$ in $X^\prime$, then there’s an edge $y$ between the corresponding subtrees in $X$, and acting by $g^{-1}$ gives us an edge $yg^{-1}$ between $T$ and $hg^{-1}T$.  So $hg^{-1}\in S$.  Then we can extend the map of vertices by sending the edge $y^\prime$ of $X^\prime$ to the edge from $g$ to $h$ in $\Gamma(G,S)$.  Do this for every edge of $X^\prime$, and we’ve got our graph map.  Conversely, any edge in $\Gamma(G,S)$ is between some $g$ and $sg$ where $g\in G,s\in S$, and so $s$ corresponds to an edge from $T$ to some $hT$, and then we can send this edge to the one between $(gT)$ and $(hgT)$ in $X^\prime$.  So $X^\prime$ is isomorphic to $\Gamma(G,S)$!

But this means that $\Gamma(G,S)$ is a tree!  And as we know, this is only possible if there are no nontrivial relations between elements of $S$.  Since it’s connected, $S$ generates $G$.  Thus, $G$ is free, and $S$ is a minimal generating set.  $\square$

So this is what we’ve done.  We know how to talk about Cayley graphs in terms of generators and relations: in particular, generators give connectedness, and relations give cycles.  Cayley graphs are trees iff they’re graphs of free groups, and in this case, the free groups (and thus their subgroups) act on them freely and without inversions.  The important thing about actions without inversions is that we can lift every subtree of the quotient graph to a tree of representatives.  But then given a free action without inversions on a tree, we can lift its entire quotient graph to a tree of representatives, and create a new graph whose vertices are the translates of this tree of representatives.  This is still a tree, and it turns out to be the Cayley graph of the group we started with.  So this group is free, and thus any group that can act freely without inversions on a tree is also free.  Subgroups of free groups are one example.

Serre actually goes on at this point to prove some more combinatorial results, including giving an explicit basis for a subgroup of a free group and the “Schreier index formula” expressing the “dimension” of a subgroup of a free group in terms of the “dimension” of its father and its index.  But these aren’t particularly important to us, right now.  It is important, though, to know that subgroups of free groups are free: the generators-and-relations theorem shows that you can express every group as a quotient of a free group, and now we know that this is a quotient by a free group.  We’ll start seeing more advanced structures than groups as we foray deeper into algebra, and while there are “free objects” in all of them, it’ll become clear that this “free over free” presentation is unique to groups.  This is important, for example, in homological algebra, where you sometimes want to build a chain of free objects called a “free resolution” of a certain object.  For groups, this chain is only two objects long, but for other structures, it can be infinitely long!

In fact, I hope to get deeper into algebra soon.  I’d like to show you the Sylow theorems, the collective Death Star of combinatorial group theory, a few things about abelian groups, and then rings, the next interesting algebraic structure.