MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Why are free groups residually finite?

Why is it that every nontrivial word in a free group (it's easy to reduce to the case of, say, two generators) has a nontrivial image in some finite group? Equivalently, why is the natural map from a group to its profinite completion injective if the group is free?

Apparently, this follows from a result of Malcev's that finitely generated matrix groups over an arbitrary commutative ring are residually finite, but is there a more easily accessible proof if we only want the result for free groups?

-
Meta-proof: if this weren't true, there would be some word in two letters that vanished identically on every finite group (sometimes called a group law). Wouldn't you have heard of that word? :) – Tom Church Apr 6 2010 at 4:46
After assigning your question as an exercise, Bergman's "An Invitation to General Algebra and Universal Constructions" asks the harder question: If X is a set, F is the free group on X, H is a finitely generated subgroup of F, and $s\in F\setminus H$, is there a homomorphism to a finite group where H is trivial but s is not? [If H is not finitely generated, we get examples like s=x and H=conjugates of x by positive powers of y.] – Pace Nielsen Apr 6 2010 at 15:32
Pace - the answer to Bergman's harder question is no! (For instance, suppose s lies in the normal closure of H.) Perhaps you mean or Bergman means: 'If X is a set, F is the free group on X, H is a finitely generated subgroup of F, and $s\in F\smallsetminus H$ , is there a homomorphism to a finite group where the image of s does not lie in the image of H?' This property is called LERF. There's a beautiful proof due to Stallings. (See my comments on Andy's answer.) – HW Apr 6 2010 at 17:24
Yes Henry, I meant the latter question. Thanks for the reference. – Pace Nielsen Apr 6 2010 at 18:56

Let $x_1,\dots,x_m$ be the generators of our group. Consider a word $x_{i_n}^{e_n}\dots x_{i_2}^{e_2}x_{i_1}^{e_1}$ where $e_i\in\{\pm 1\}$ and there are no cancellations (that is, $e_k=e_{k+1}$ if $i_k=i_{k+1}$).

I'm going to map this word to a nontrivial element of $S_{n+1}$, the group of permutations of $M:=\{1,\dots,n+1\}$. It suffices to construct permutations $f_1,\dots,f_m\in S_{n+1}$ such that $f_{i_n}^{e_n}\dots f_{i_2}^{e_2}f_{i_1}^{e_1}\ne id_M$. For each $k=1,\dots,n$, assign $f_{i_k}(k)=k+1$ if $e_k=1$, or $f_{i_k}(k+1)=k$ if $e_k=-1$. This gives us injective maps $f_1,\dots,f_m$ defined on subsets of $M$. Assign yet unassigned values of $f_i$'s arbitrarily (the only requirement is that they are bijections). The resulting permutations satisfy $f_{i_n}^{e_n}\dots f_{i_2}^{e_2}f_{i_1}^{e_1}(1)=n+1$.

Edit: As pointed out by Steve D in comments, this proof can be found in a book by Daniel E. Cohen, "Combinatorial group theory: a topological approach" (1989). The book can be found on the net if you are determined; the proof in on page 7 and in Proposition 5 on page 11.

Edit [DZ]: I have a hard time reading multiple subscripts, so here is an example of Sergei Ivanov's construction.

Take the word $cca^{-1}bc^{-1}a$. This has length $6$, so we will find a homomorphism to $S_7$ whose image of this word is nontrivial because it sends $1$ to $7$. We'll choose values of permutations so that the $k$th suffix sends $1$ to $k+1$:

Suffix 1: $a$

$\alpha=\bigg(\begin{array}{} 1&2 &3 &4& 5& 6& 7 \\ 2&?&?&?&?&?&? \end{array} \bigg)$

Suffix 2: $c^{-1}a$

$\gamma=\bigg(\begin{array}{} 1&2 &3 &4& 5& 6& 7 \\ ?&?&2&?&?&?&? \end{array} \bigg)$

Suffix 3: $bc^{-1}a$

$\beta=\bigg(\begin{array}{} 1&2 &3 &4& 5& 6& 7 \\ ?&?&4&?&?&?&? \end{array} \bigg)$

Suffix 4: $a^{-1}bc^{-1}a$

$\alpha=\bigg(\begin{array}{} 1&2 &3 &4& 5& 6& 7 \\ 2&?&?&?&4&?&? \end{array} \bigg)$

Suffix 5: $ca^{-1}bc^{-1}a$

$\gamma=\bigg(\begin{array}{} 1&2 &3 &4& 5& 6& 7 \\ ?&?&2&?&6&?&? \end{array} \bigg)$

Suffix 6: $cca^{-1}bc^{-1}a$

$\gamma=\bigg(\begin{array}{} 1&2 &3 &4& 5& 6& 7 \\ ?&?&2&?&6&7&? \end{array} \bigg)$

These conditions on $\alpha, \beta,$ and $\gamma$ don't conflict, they can be extended to permutations, and then $\gamma\gamma\alpha^{-1}\beta\gamma^{-1}\alpha(1) = 7$.

-
You are assuming all the generators in the word are different, but this is not really the case in a free group. What about the word ababababab? – Adam Gal Apr 6 2010 at 9:42
No I don't assume that the $i_k$'s are different, only that there are no cancellations in the word. In your example, you define two permutations $f_a$ and $f_b$. You assign $f_b(1)=2$, $f_b(3)=4$ and so on, $f_a(2)=3$, $f_a(4)=5$ and so on, and extend these partially defined maps. – Sergei Ivanov Apr 6 2010 at 10:01
Nice argument! Would you mind if I added an example? – Douglas Zare Apr 6 2010 at 15:43
Feel free to improve it any way you like. – Sergei Ivanov Apr 6 2010 at 16:27
This is essentially the argument given in Cohen's "Combinatorial Group Theory". – Steve D Apr 8 2010 at 21:27
show 1 more comment

Karl Auinger and I came up with the following proof which proves residually p and even stronger properties (e.g., residually finite of square-free exponent). Let me first introduce the main construction which we use in http://www.springerlink.com/content/9nmr9hhl5guvwyjf/ for stronger separability results.

Fix a finite generating set X. All groups are assumed to be X-generated. If G is an X-generated group and p a prime, let G(p) be the quotient of the free group $F_X$ by the normal subgroup consisting of all words $w$ which are trivial in G and which label a loop in the Cayley graph of G at 1 that is trivial in homology with mod-p coefficients. G(p) is an extension of an elementary abelian p-group by G.

Now let C be a class of finite groups such that for each $G\in C$ there is a prime p with $G(p)\in C$ and which is closed under finite direct products, subgroups and quotient groups. For example, C could be all finite p-groups or all finite groups of square-free exponent. We claim free groups are residually C.

Let N be the intersection of all normal subgroups of $F_X$ with quotient in C. We must show N is trivial. Suppose not. Let $H=F_X/N$. Since H is not free on the image of X, there is a word w labeling a vertex simple loop (no repeated vertices) at 1 in the Cayley graph of H. Since H is residually C, there is a finite X-generated group G in C such that w labels a vertex simple loop at 1 in the Cayley graph of G. Let p be a prime with G(p) in C. Clearly a vertex simple loop is non-trivial in mod-p homology. Thus w is non-trivial in G(p) contradicting that G(p) is a quotient of H. This proves N is trivial so free groups are residually C.

-
 There is a short proof of the fact that the free group is residually $p$. Let $\psi_n:SL_2(\mathbb{Z})\rightarrow SL_2(\mathbb{Z}/p^n\mathbb{Z})$ denote reduction mod. $p^n$. Observe that, for $n\geq 2$ and $S\in Ker(\psi_n)\backslash Ker(\psi_{n+1})$, then $S^p$ is in $Ker(\psi_{n+1})\backslash Ker(\psi_{n+2})$. Realize $F_2$ as the subgroup of $SL_2(\mathbb{Z})$ generated by $(1,p^2,0,1)$ and $(1,0,p^2,1)$. The above observation shows that $\psi_n(F_2)$ is a $p$-group, for every $n\geq 2$. If $g$ is a non-trivial element in $F_2$, then $\psi_n(g)\neq 1$ for $n$ large enough. – Alain Valette Apr 9 2012 at 11:48 @Alain, Of course I know this proof but the kinds of classes the above proof gives are more general. For instance if one takes any infinite supernatural number $\mu$, then the free group is residually a finite group of order dividing $\mu$. I don't see how to get that immediately from linear over Z. – Benjamin Steinberg Apr 12 2012 at 20:24

Actually there is a simple reasoning showing residual finiteness of free groups using coverings. Indeed, consider the free group $F(n)$ as a fundamental group of a wedge $X$ of $n$ circles. Take any nontrivial element $w$ of $F(n)$. It is sufficient to exhibit a finite cover $X_0 \to X$ such that the path $w$ is not covered by a loop in the graph $X_0$. The graph $X_0$ can be built as follows: take a universal cover $\tilde X$ of $X$. It is a Cayley graph of $F(n)$, a regular tree, every vertex of which has in-degree $n$ and out-degree $n$ with edges labeled by generators of $F(n)$. Consider the path W (starting at a fixed origin) in $\tilde X$ corresponding to the word $w$. In order to obtain $X_0$, we declare Vertices($X_0$) = Vertices($W$) and Edges($X_0$) = Edges($W$) plus additional edges added in such a way that $X_0$ becomes an $n$-regular graph: every vertex should have $n$ in-coming and $n$ out-going edges. This is always possible since $W$ was originally taken from an $n$-regular graph.

Thus we get a finite $n$-regular graph $X_0$, hence a finite sheeted covering $X_0\to X$ in which the path $w$ is not a loop. Therefore, element $w$ lies outside of a finite index subgroup of $F(n)$, hence it lies outside some finite index normal subgroup, hence it maps nontrivially into some finite group.

-
This is precisely Stallings' proof. See my comment on Andy's answer. – HW Apr 12 2010 at 19:14

You can also use the fact that free groups are linear. For instance if $$a=\begin{pmatrix} 1 & 2 \\ 0 & 1 \ \end{pmatrix}$$ and $b$ is the transpose of $a$, a simple ping-pong argument shows that $a$ and $b$ generate a free subgroup of $SL(2,Z)$. Now any element of $SL(2,Z)$ will be non-trivial in reduction mod $p>>1$.

-
The questioner explicitly said he didn't want this answer! – HW Apr 6 2010 at 17:26
Henry, the questioner did not want to use Malcev's theorem, which the argument above does not use. – Igor Belegradek Apr 6 2010 at 19:03
Doesn't this proof generalize to give Malcev's theorem? The proof I know for finitely generated linear groups over fields goes along these same lines. I'm not sure about finitely generated linear groups over arbitrary commutative rings. – Nick Hildebrand Apr 6 2010 at 19:15
@Keivan: I gave a proof of Malcev's theorem, along similar lines, on this question: mathoverflow.net/questions/9628/… – Steve D Apr 7 2010 at 16:37
I recommend Roger Alperin's account in his paper "An elementary account of Selberg's lemma". – HW Apr 7 2010 at 17:11

You can use Magnus series to prove this. I believe this argument is, at most, a slight variant of one in a paper of his (but it's been a number of years).

If your free group has n generators, take the noncommutative power series ring $R = \mathbb{F}_2\langle\langle x_1,\ldots,x_n\rangle \rangle$, with 2-sided ideal of definition $I = (x_1,\ldots,x_n)$. (Then $R/I^s$ is a finite ring.) We define a homomorphism $\phi$ from the free group to $R^\times$ that sends the i'th generator $g_i$ to $1 + x_i$. It suffices to show that every word in the free group has nonzero image in some $(R/I^s)^\times$.

Suppose $w = g_{m_1}^{e_1} \cdots g_{m_k}^{e_k}$ is a word in the free group where $e_i \neq 0$, ${m_i} \neq {m_{i+1}}$. Write $e_i = 2^{r_i} f_i$ where $f_i$ is odd. Then the first nonzero coefficient in $(1 + x_i)^{e_i}$ is that of $(x_i)^{2^{r_i}}$. Thus if you expand out $\phi(w)$ into a monomial product, the monomial $x_1^{2^{r_1}} \cdots x_k^{2^{r_k}}$ appears exactly once. Therefore, $\phi(w)$ has nonzero image in $R/I^s$ for $s > \sum 2^{r_i}$.

-
 The result is due to Magnus and this is basically his original proof. The standard source for it is the final chapter of Magnus-Karass-Solitar, though I can't say that I find that book very inspiring. A related proof uses the Fox free differential calculus (if you think of the Magnus expansion as the Taylor series of the free group, then the Fox free derivatives give the coefficients). See Fox's first paper on the free differential calculus for the details. – Andy Putman Apr 6 2010 at 4:59 Now I'm confused - I actually came back here to say that I think I misattributed and I believe Zassenhaus was the one who first used the mod-p Magnus transform. But Springerlink is fighting me tonight and so I am having difficulty actually verifying things. – Tyler Lawson Apr 6 2010 at 5:15 Actually, I was going too quick and I misread things. The references I gave are for the stronger result that free groups are residually nilpotent (though I guess this is only stronger once you've convinced yourself that nilpotent groups are residually finite, but that's not too hard). – Andy Putman Apr 6 2010 at 5:19

There is a beautiful and very short proof due to Hempel of the residual finiteness of both free groups and fundamental groups of closed surfaces. See his paper

J. Hempel, Residual finiteness of surface groups, Proc. Amer. Math. Soc. 32 (1972), 323.

-
Another classic reference is Stallings's paper "Topology of finite graphs". It contains a very nice proof of the stronger fact that free groups are LERF. I imagine the proof is similar to Hempel's proof (though I don't have online access to Hempel's). Stallings, John R. Topology of finite graphs. Invent. Math. 71 (1983), no. 3, 551--565. – HW Apr 6 2010 at 5:06
Hempel's proof is actually completely different! The basic idea is that a free group is \pi_1 of a compact surface w/ bdry. You take a loop that you want to separate by a fi subgroup, and you keep passing to finite covers to "resolve" the self-intersections of the curve. By the way, is there a nice analogue of Stallings's techniques for surface groups? – Andy Putman Apr 6 2010 at 5:09
... but the surface with boundary retracts onto a graph, so aren't the proofs coarsely equivalent? – Matthew Stover Apr 6 2010 at 12:56
The two proofs are very similar - imagine doing Hempel's proof on a graph, instead of a surface. Perhaps Hempel's proof gives slightly more, like residual nilpotence? (Are the covers he uses always cyclic?) Stallings's techniques work identically for surfaces with boundary, if you translate as follows: graph vertex -> fundamental polygon; graph edge -> 'dual' glued edge of fundamental polygon. In a sense, Scott's argument using Coxeter groups in 'Surface groups are virtually geometric' is the 'right' way to generalise Stallings's ideas to the closed case. – HW Apr 6 2010 at 17:19
I'll have to go back and reread Stallings's article -- I last read it when I was in graduate school. Hempel's argument doesn't give residual nilpotence, but it can be jazzed up a bit to give residual nilpotence plus a few other interesting conclusions. See my paper "On the self-intersections of curves deep in the lower central series of a surface group" with Justin Malestein. – Andy Putman Apr 6 2010 at 18:06