Why are free groups residually finite?

Question

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?

Answer 1

Here is a direct proof for free groups.

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$.

Answer 2

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$.

Answer 3

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}$.

Answer 4

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.

Answer 5

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.

Answer 6

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 Link 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.

Answer 7

A proof based on algebraic topology can also be found in Thomas Koberda's lecture notes, RAAGS and their subgroups; in fact, he proves more generally that a finitely generated free group is residually $p$ for any prime. The proof is rather laconic, so I gives some details below.

A finitely generated free group $F$ is the fundamental group of a finite bouquet of circles $X_0$. By induction, we build a sequence of regular coverings $$\cdots \to X_2 \to X_1 \to X_0,$$ where $\mathrm{Aut}(X_{i+1} \to X_i) \simeq H_1(X_i, \mathbb{Z}_p)$; in order to construct $X_{i+1}$, it is sufficient to take the covering of $X_i$ associated to the subgroup of $\pi_1(X_i)$ consisting of the kernel of $$\pi_1(X_i) \twoheadrightarrow \pi_1(X_i)^{\mathrm{ab}} \simeq H_1(X_i,\mathbb{Z}) \twoheadrightarrow H_1(X_i, \mathbb{Z}_p).$$

In particular, notice that $H_1(X_i,\mathbb{Z}_p)$ is a finitely generated abelian torsion group, so it is a finite $p$-group. Therefore, any covering $X_{i+1} \to X_i$ of our sequence has a degree a power of $p$. To conclude, it is sufficient to notice that any loop in $X_0$ does not lift into $X_i$ as a loop for some large enough $i$.

Because the action $\mathrm{Aut}(X_{i+1} \to X_i) \curvearrowright X_{i+1}$ is free, we deduce

Claim 1: A loop $\gamma \subset X_i$ lifts into $X_{i+1}$ as a loop iff $\gamma=1$ in $H_1(X_0, \mathbb{Z}_p)$.

Claim 2: A loop minimising the length among the homotopically nontrivial loops of a graph $Y$ defines a nontrivial element of $H_1(Y,\mathbb{Z})$.

Now let $l(X_i)$ denote the minimal length of a homotopically nontrivial loop in $X_i$. Of course, we have $l(X_0)=1$.

Claim 3: $l(X_{i}) \geq i+1$ for all $i \geq 0$.

Let $\gamma$ be a loop in $X_{i+1}$ and let $p$ denote the covering map $X_{i+1} \to X_i$. Then $p(\gamma)$ is a loop in $X_i$ that lifts into $X_{i+1}$ as a loop, so $\mathrm{lg}(p(\gamma)) \geq l(X_i)+1$ according to claims 1 and 2 (if $p$ is large enough). Hence $$\mathrm{lg}(\gamma) \geq \mathrm{lg}(p(\gamma)) \geq l(X_i)+1,$$ and finally $l(X_{i+1}) \geq l(X_i)+1$. Now, claim 3 follows easily.

We deduce from claim 3 that, if a homotopically nontrivial loop $\gamma \subset X_0$ loops into $X_i$ as a loop $\gamma'$, then $$\mathrm{lg}(\gamma)=\mathrm{lg}(\gamma') \geq l(X_i) \geq i+1;$$ therefore, for large enough $j$, $\gamma$ cannot lifts into $X_j$ as a loop.