# Is every virtually free group residually finite?

Question: Is every (finitely generated) virtually free group residually finite?

A well-known question asks whether every hyperbolic group is residually finite (Mladen Bestvina. Questions in geometric group theory. http://www.math.utah.edu/ ~bestvina/eprints/questions- updated.pdf.). My question is a very speciall case, and I wonder if it has been done.

It is known that residual finiteness is not a quasi isometry invariant (Is residual finiteness a quasi isometry invariant for f.g. groups?).

• Yes, every virtually (residually finite) group is residually finite (clear), and every free group is residually finite (O. Schreier). They are also linear, by the way.
– YCor
Apr 27 at 7:55
• A virtually residually finite group is always residually finite. Apr 27 at 11:39
• Eventually this seems to become a big-list question, namely "provide proofs that free groups are residually finite".
– YCor
Apr 29 at 13:20
• There is already a big list question on that Apr 29 at 21:51
• mathoverflow.net/questions/20471/… Apr 29 at 21:52

As already mentioned, it is an easy exercise to show that a group containing a residually finite subgroup of finite index is itself residually finite. But proving that free groups are residually finite is (standard but) not so easy. There exist several possible arguments. Here are two of my favourites.

First proof. As motivated in Stallings' excellent article Topology of finite graphs, one can prove many properties of free groups of finite ranks by doing some elementary algebraic topology on finite graphs.

Let $$g$$ be a non-trivial element of a free group $$F$$ of finite rank. Let $$B$$ be a bouquet of $$\mathrm{rk}(F)$$ oriented circles, each one labelled by a generator of $$F$$. Write $$g$$ as a reduced word and let $$X$$ be a (subdivided) path whose oriented edges are labelled by generators in such that the reading $$X$$ yields $$g$$. There is a map $$X \to B$$ that sends each edge of $$X$$ to the edge of $$B$$ having the same label. Because our word is reduced, the map $$X \to B$$ is locally injective. Now, add edges to $$X$$ to get a covering $$X' \to B$$. This is possible because, in order to get a covering of $$B$$, it suffices to have, for each vertex $$v$$ and for each generator $$s$$, one (half-)edge labelled $$s$$ leaving $$v$$ and one (half-)edge labelled $$s$$ arriving at $$v$$. Then the image of $$\pi_1(X')$$ in $$\pi_1(B)$$ yields a finite-index subgroup $$H$$ in $$F$$ that does not contain $$g$$ (because $$g$$, thought of as a loop in $$B$$, lifts to a path in $$X'$$ that is not a loop).

Second proof. Instead of proving that free groups are residually finite, we can prove that the Coxeter group $$W_n:= \underset{n \text{ free factors}}{\underbrace{\mathbb{Z}/2\mathbb{Z} \ast \cdots \ast \mathbb{Z}/2 \mathbb{Z}}}.$$ is residually finite (since it is virtually free). The key observation is that the Cayley graph of $$W_n$$ with respect to its canonical generating set is a tree $$T_n$$, that vertex-stabilisers are trivial, and that $$W_n$$ acts on $$T_n$$ by reflections: each edge is flipped by an element of order two. Now, let $$g \in W_n$$ be a non-trivial element. Fix a path $$P$$ between the vertices $$1$$ and $$g$$ in $$T_n$$, and let $$E$$ denote the collection of all the edges of $$T_n \backslash P$$ with one endpoints in $$P$$. By an easy ping-pong argument, we can prove that $$H:= \langle \text{reflection along } e, e \in E \rangle$$ acts on $$T_n$$ with $$P$$ as a fundamental domain. It follows that $$H$$ has finite-index (since $$P$$ is finite) and that $$g$$ does not belong to $$H$$ (since $$h P \cap P= \emptyset$$ for every non-trivial $$h \in H$$).

Remark. Observe that, in the two arguments, the construction of the finite-index subgroup $$H$$ is explicit once $$g$$ is given. In particular, its index is controlled by the length of $$g$$.

• +1, I for one am all for hijacking this question for a big-list of favorite proofs of Schreier's result, if one is missing... Apr 29 at 6:09

Here is a different, purely group-theoretical proof that free groups are residually finite, following [J. Rotman, Advanced Modern Algebra (Second Edition), Proposition 4.80 p. 279].

Proposition. Given a free group $$F$$ and a non-trivial element $$g \in F$$, there exists a finite permutation group $$S$$ and a homomorphism $$\varphi \colon F \to S$$ such that $$\varphi(g) \neq 1$$.

Proof. Let $$X$$ a basis of $$F$$, and write $$g$$ as a reduced word $$g=x^{e_n}_{i_n}\ldots x^{e_1}_{i_1},$$ where $$x_{i_k} \in X$$ and $$e_k \in \{\pm 1\}$$. There are $$m \leq n$$ distinct base elements occurring in this word, say $$x_1, \ldots, x_m$$. For each of these basis elements $$x_j$$ we are now going to construct a permutation $$\alpha_j \in S_{n+1}$$.

Consider the set of all positions $$k$$ where $$x_j$$ or $$x_j^{-1}$$ occurs. If $$x_j$$ occurs, define $$\alpha_j(k)=k+1$$; if $$x_j^{-1}$$ occurs define $$\alpha_j(k+1)=k$$, namely, $$\alpha_j^{-1}(k)=k+1$$. This specifies $$\alpha_j$$ on a subset of $$\{1, \ldots, n+1\}$$, and we can complete it to a permutation of $$S_{n+1}$$, that we denote again by $$\alpha_j$$.

Finally, let us define a group homomorphism $$\varphi \colon F \to S_{n+1}$$. Since $$X$$ is a basis for $$F$$, by the universal property of free groups it suffices to define $$\varphi$$ on the elements of $$X$$. If $$x \in X$$ is an $$x_j$$ occurring in the spelling of $$g$$, define $$\varphi(x)=\alpha_j$$; if $$x$$ is not involved in the expression of $$g$$, define $$\varphi(x)=1$$. With such a definition, we have $$\varphi(g)= \alpha^{e_n}_{i_n}\ldots \alpha^{e_1}_{i_1}.$$ This is not the trivial permutation, since it sends $$1$$ to $$n+1$$. $$\square$$

• That's nice! It needs virtually nothing beyond the universal property of the free group, which is often used as the definition. Apr 29 at 13:34
• @DerekHolt: On the contrary, it uses that non-trivial elements of free groups are represented by reduced words, which is equivalent to the topological description as the fundamental group of a rose.
– HJRW
Apr 29 at 14:06
• I think this is essentially O. Schreier's original proof (in the 1920s).
– YCor
Apr 29 at 16:05
• (By the way it doesn't really use any group theory result, I'd rather view it as combinatorial or "permutation-theoretic" if it makes any sense. Of course this point of view is subjective. This proof is, by the way, used in some quantitative versions of residual finiteness since for a given nontrivial group word it gives a finite set of reasonable size for which this word acts nontrivially.)
– YCor
Apr 29 at 16:16
• @YCor It is Schreier's proof indeed, with the caveat that "residually finite" would not be coined for another 20 years after Schreier's paper (this paper is the same as the one containing the famous subgroup theorem). All that Schreier was out to prove is that a non-empty reduced word is not equal to $1$ in a free group, and his method of doing so is the one in the answer. Apr 29 at 23:50

Continuing the suggested hijacking, here is another proof that free groups are residually finite. It suffices to prove $$F_2$$ is residually finite. As in Francesco's answer, given a nontrivial word $$g \in F_2$$ we need to find a finite group $$G$$ and a homomorphism $$f : F_2 \to G$$ such that $$f(g) \neq 1$$.

Take $$G = \mathrm{SL}_2(p)$$ for prime $$p$$ larger than the length of $$g$$. If the generators are $$x, y$$, define $$f$$ by $$f(x) = \begin{pmatrix} 1 & X \\ 0 & 1 \end{pmatrix},\qquad f(y) = \begin{pmatrix} 1 & 0 \\ Y & 1\end{pmatrix}$$ for $$X, Y \in \mathbf{F}_p$$ to be determined. Suppose without loss of generality that $$g = x^{a_1} y^{b_1} \cdots x^{a_k} y^{b_k}$$ where $$a_1 b_1 \cdots a_k b_k \neq 0$$. Then $$f(g) = \begin{pmatrix} a_1 b_1 \cdots a_k b_k X^k Y^k + \cdots & a_1 b_1 \cdots a_k X^k Y^{k-1} + \cdots \\ a_2 \cdots a_k b_k X^{k-1} Y^k + \cdots & b_1 a_2 b_2 \cdots a_k X^{k-1} Y^{k-1} + \cdots \end{pmatrix},$$ where lower-order terms are hidden. Now put $$Y = 1$$ and note that we have polynomials in one variable with nonzero leading coefficient and degree less than $$p$$, so we can choose $$X$$ so that any one of them is nonzero, which is what we wanted.

• On reflection, I guess this is the same as my answer, except that you check the non-triviality in the quotient without first checking it in what I have hear Alex Lubotzky call “the mother group”. So you simultaneously prove the more non-trivial of my two “standard facts”.
– HJRW
Apr 29 at 15:04

To add to the list, here's a proof that is probably actually longer than the others, but is immediate "modulo standard facts".

Standard fact 1: All finitely generated free groups embed into $$SL_2(\mathbb{Z})$$. Indeed, famously the congruence subgroup $$\Gamma(2)$$ of $$PSL_2(\mathbb{Z})$$ is free of rank 2, all finitely generated free groups embed in $$F_2$$, and by the universal property we can embed into $$SL_2(\mathbb{Z})$$.

Standard fact 2: $$SL_2(\mathbb{Z})$$ is residually finite. Indeed, given a non-identity matrix, map to $$SL_2(\mathbb{Z}/n)$$ for large enough $$n$$.