You are currently browsing the monthly archive for January 2009.

Ping-Pong Lemma

Question. Let G be a group and $a, b \in G$.  When is $\langle a, b \rangle \cong F_2$?

Ping-Pong Lemma: Let G be a group acting on a set X and $a, b \in G$. Assume:

1. a and b have infinite orders.
2. There exist $X_1, X_2 \subseteq X$ such that $X_2 \nsubseteq X_1$ and $a^m X_2\subseteq X_1$, $b^m X_1 \subseteq X_2$ for all $m \neq 0$.

Then $\langle a, b \rangle \cong F_2$.

Proof. Consider $\varphi : F_2 = \langle x, y \rangle \twoheadrightarrow \langle a,b \rangle \leq G$ such that $\varphi (x) = a$ and $\varphi (y) = b$.  Choose a reduced word w for a nontrivial element in $F_2$, i.e., either $w = x^{m_1} y^{n_1} x^{m_2} \cdots$ or $w = y^{m_1} x^{n_1} y^{m_2} \cdots$ and $m_i, n_i \neq 0$.

Case 1: $w = x^{m_1} y^{n_1} \cdots x^{m_k}$.  Then $\varphi (w) X_2 = a^{m_1} b^{n_1} \cdots a^{m_k} X_2$ and $a^{m_k} X_2 \subseteq X_1$, so $\varphi (w) X_2 \subseteq a^{m_1} b^{n_1} \cdots b^{n_{k-1}} X_1$ and $b^{n_{k-1}} X_1 \subseteq X_2$, and so on until $\varphi (w) X_2 \subseteq a^{m_1} X_2 \subseteq X_1$, so $\varphi (w) X_2 \neq X_2$.  Therefore $\varphi (w) \neq 1$.

Case 2: $w = y^{m_1} x^{n_1} \cdots y^{m_k}$.  Then, by Case 1, $\varphi (xwx^{-1}) \neq 1$, so $\varphi (x) \varphi (w) \varphi (x^{-1}) \neq 1$.  Therefore $\varphi (w) \neq 1$.

Case 3: $w = x^{m_1} y^{n_1} \cdots y^{n_k}$.  (similar to above)

Case 4: $w = y^{m_1} x^{n_1} \cdots x^{n_k}$.  (similar to above)

Free Groups Are Linear

Theorem 3. $F_2$ is linear.

Proof. $\mathrm{SL}_2\mathbb{R}$ acts on $\mathbb{R}^2$ by linear transformations.  Let $a = \left(\begin{array}{cc} 1&2 \\ 0&1 \\ \end{array}\right)$ and $b = \left(\begin{array}{cc} 1&0 \\ 2&1 \\ \end{array}\right)$.  Then $a^m = \left(\begin{array}{cc} 1&2m \\ 0&1 \\ \end{array}\right)$ and $b^m = \left(\begin{array}{cc} 1&0 \\ 2m&1 \\ \end{array}\right)$. Let $X_1 = \left\{\left(\begin{array}{c} x \\ y \\ \end{array}\right) \mid |x| > |y|\right\}$ and $X_2 = \left\{\left(\begin{array}{c} x \\ y \\ \end{array}\right) \mid |x| < |y|\right\}$.  Then $a^m X_2 \subseteq X_1, b^m X_1 \subseteq X_2$ for all $m \neq 0$, so $\langle a, b \rangle \cong F_2$ by the Ping-Pong Lemma.

Corollary 1. Finitely generated free groups are linear, hence residually finite.

Proof. The case of $\mathbb{Z}$ is obvious; otherwise, this follows from $F_n \hookrightarrow F_2$ as proved in Exercise 1.

Separability

Definition. Let G be a group.  The profinite topology on G is the coarsest topology such that every homomorphism from G to a finite group (equipped with the discrete topology) is continuous.

Definition. A subgroup H is separable in G if H is closed in the profinite topology of G.

Exercise 3. Let G be a group. $X \subseteq G$ is separable if and only if for all $g \in G \smallsetminus X$, there exists a homomorphism to a  finite group $q : G \rightarrow Q$ such that $q(g) \not \in q(X)$.  Note that if X = {1}, this is equivalent to: G is RF if and only if {1} is separable.

Hint. For the “if” direction, let $g \in G$ and consider $q^{-1} \circ q(g)$.  For the other direction, use the definition of subbase and that $p : G \rightarrow P, q: G \rightarrow Q \Rightarrow \text{ker}(p \times q) = \text{ker}(p) \cap \text{ker}(q)$.

Definition. Let G be a group.

1. G is Extended RF (ERF) if any subgroup of G is separable.
2. G is Locally ERF (LERF, subgroup separable) if any finitely generated subgroup is separable.

Lemma 3. Let G be a group. A subgroup H of G is separable if and only if for all $g \in G \smallsetminus H$, there exists a finite-index subgroup $K \leq G$ such that $H \leq K \leq G$ and $g \not \in K$.

Proof. In the “only if” direction, by the previous exercise, for all $g \in G \smallsetminus H$, there exists a homomorphism to a  finite group $q : G \rightarrow Q$ such that $q(g) \not \in q(H)$. Then $g \not \in q^{-1} \circ q(H) = K$.  Conversely, let $g \in G \smallsetminus H$. By hypothesis, there exists a finite-index subgroup $K \leq G$ such that $H \leq K \leq G$ and $g \not \in K$.  Let $L = \cap_{h \in G} K^h$. Note that this is a finite number of intersections ($|G/N_G (K)|$, to be precise). There exists a finite quotient $q : G \rightarrow G/L$.  Then  $q^{-1} \circ q(H) = H \cdot L$.  Therefore, $g \not \in q^{-1} \circ q(H)$, i.e., $q(g) \not \in q(H)$, and the lemma follows by the previous exercise.

Scott’s Criterion (1978). Let X be a Hausdorff topological space and $G = \pi_1 (X,x)$.  Let $X' \rightarrow X$ be a covering and $H = \pi_1 (X',x')$. Then H is separable in G if and only if for any compact $\Delta \subseteq X'$, there exists and intermediate finite-sheeted cover $\hat{X} \rightarrow X$ such that $X' \rightarrow \hat{X}$ embeds $\Delta$ into $\hat{X}$.

Exercise 4. Let $H \leq G$ be a separable subgroup.

1. If $G' \leq G$, then $G' \cap H$ is separable in G’.
2. If $G \leq G'$ has finite index, then $H$ is separable in G’.

Residual finiteness

Let $G$ be a group and $g\in G$ with $g\neq 1$. Then we call $G$ residually finite (hereafter RF) if there exists a subgroup $K\subset G$ of finite index such that $g\notin K$. In other words, for every nontrivial element of $G$, there exists a finite index subgroup that does not contain that particular element.

Example. Finite groups are RF, since the trivial subgroup has finite index and does not contain any of the nontrivial elements of $G$.

Metaquestion. How general is the class of RF groups? In particular, which finitely generated/finitely presented groups are RF?

Remarks. Assume that $G$ is finitely generated.

(i) The definition can be strengthened so that we may assume that our finite index subgroup $K\subset G$ is normal in $G$. Indeed, if $G$ is finitely generated, then there are only finitely many subgroups of a given fixed index $k$. (See the exercise from the second lecture.) If $g_0\neq 1$, and $K\subset G$ is a subgroup of finite index that does not contain $g_0$, then

$\textrm{core}(K)=\bigcap_{g\in G}gKg^{-1}$

is a subgroup of finite index in $G$ which excludes $g_0$, since $gKg^{-1}$ and $K$ have the same index in $G$ for all $g\in G$, so this intersection is really the intersection of finitely many subgroups of finite index. Thus $\textrm{core}(K)$ also has finite index in $G$.

(ii) Equivalently, $G$ is RF if and only if for each $g\in G$ not the identity, there exists a homomorphism $\phi:G\to A$, where $A$ is a finite group, for which $\phi(g)$ is not the identity in $A$. Indeed, if $G$ is RF and $K_0$ is normal subgroup provided by (i), then $g$ does not die under the natural homomorphism from $G$ to $G/K_0$. Conversely, given such a homomorphism, the kernel of $\phi$ is a subgroup of finite index that does not contain $g$.

(iii) Also, $G$ is RF if and only if

$\bigcap_{K\subset G,\ [G:K]<\infty}K=\{1\}.$

That is, the intersection of all the subgroups of finite index in $G$ is the trivial subgroup. Were some nonidentity element $g$ to be contained in this intersection, then it would be contained in each subgroup of finite index in $G$, so this element prevents $G$ from being RF. Conversely, if this intersection is trivial, each nonidentity element of $G$ must be excluded from some finite index subgroup, so $G$ is RF.

(iv) If $G$ is RF and $g_1,\dots,g_n\in G$, then there exists a finite index subgroup $K\subset G$ with $g_j\notin K$ for all $1\leq j\leq n$. Here, just take the intersection of the finite index subgroup associated with each $g_j$. This is again a finite index subgroup of $G$.

Lemma 2: Let $G$ be a finitely generated group.

(i) If $G$ is RF and $H\subset G$ is a subgroup, then $H$ is RF.

(ii) If $H$ is RF and $H\subset G$ with $H$ finite index in $G$, then $G$ is RF.

That is, RF passes to all subgroups and also to supergroups of finite index.

Proof. For (i), choose $h\in H$. Considered as an element of $G$, there exists a homomorphism $\phi$ to a finite group $A$ for which $\phi(h)$ is not the identity. The restriction of $\phi$ to $H$ is also a homomorphism to a finite group for which the image of $h$ is nontrivial. The kernel of this restricted homomorphism is a subgroup of finite index in $H$ that does not contain $h$. (Note that we did not assume that $H$ is finitely generated.)

For (ii), choose $g\in G$. If $g\notin H$, then $H$ is a finite index subgroup not containing $g$, and we are done. If $g\in H$, then there exists a finite index subgroup $K\subset H$ that does not contain $g$. However, $K$ is also a finite index subgroup of $G$, so we are done. $\square$

Topological reformulation of RF

Now, we would like to connect RF with a topological property of a space with fundamental group $G$. Let $M$ be a compact manifold with universal covering $\widetilde{M}$ and $G=\pi_1(M)$. Accordingly, we assume throughout that $G$ is finitely generated. (We will see later that the manifold condition can be relaxed.)

Theorem 2: The group $G$ is RF if and only if the following condition holds: for every compact subset $C\subset\widetilde{M}$ there exists a finite sheeted covering $M_C\to M$ for which $C$ embeds homeomorphically in $M_C$.

Proof. Assume the topological condition holds and choose any $g\in G$ not the identity. This corresponds to a loop (based at a point dependent only upon our choice of universal covering) in $M$ which we also denote by $g$. To this loop, there also is a corresponding lift to a connected arc $a$ in $\widetilde{M}$ with distinct endpoints $x$ and $y$.

Let $C$ be the compact set $\{x,y\}$. Then, there exists a finite sheeted covering $M_C\to M$ for which $x$ and $y$ are distinct points of $M_C$. By the lifting property of covering spaces, this implies that if $K_C\subset G$ is the subgroup of finite index corresponding to the covering $M_C\to M$, then $g\notin K_C$. Therefore $G$ is RF.

Conversely, suppose that $G$ is RF and choose any subset $C\subset\widetilde{M}$. Then, since $G$ acts freely and properly discontinuous on $\widetilde{M}$, the set $T_C$ of those $g\in G$ (not the identity) for which $g C$ intersects $C$ nontrivially is finite. Now, choose $K_C\subset G$ of finite index containing none of the elements of $T_C$. If $M_C$ is the corresponding finite sheeted covering, we have that $hC\cap C=\emptyset$ for all $h\in\pi_1(M_C)$. That is, $C$ embeds homeomorphically in $M_C$. $\square$

Remark. We never really used here that $M$ was a manifold, only that its fundamental group acted properly discontinuous on the universal covering. (The action need not be free either, since this would only add another finite number of elements to our set $T_C$.) Thus, it suffices to assume that $M$ is Hausdorff and locally compact.

Examples.

(1) Finitely generated abelian groups are RF. (Exercise.)

(2) Selberg’s Lemma (Malcev-Selberg): If $G$ is a finitely generated linear group, that is, $G\subset\mathrm{GL}_N(\mathbb{C})$ for some $N$, then $G$ is RF.

Proof. We begin with the case $G\subset\mathrm{GL}_N(\mathbb{Z})$. Since RF passes to arbitrary subgroups, it suffices to prove that $\mathrm{GL}_N(\mathbb{Z})$ is RF.

Choose any $g\neq 1$. This means that the matrix $g-1$ has some nonzero entry, say $x$. Since $x$ is an integer, we can find some large prime $p$ that does not divide $x$. Now, consider the homomorphism

$\phi_p:\mathrm{GL}_N(\mathbb{Z})\to\mathrm{GL}_N(\mathbb{Z}/p\mathbb{Z})$

given by reducing the entries of a given matrix modulo $p$. This is a homomorphism because matrix multiplication is linear in the entries. (Exercise – make this precise.) Since $\mathbb{Z}/p\mathbb{Z}$ is a finite field, its general linear group is a finite group, i.e. the kernel $K_p$ of $\phi_p$ is a finite index subgroup of $\mathrm{GL}_N(\mathbb{Z})$, and it does not contain $g$ by construction. Thus $\mathrm{GL}_N(\mathbb{Z})$ is RF, and thus any subgroup thereof is also RF.

More generally, if $G\subset\mathrm{GL}_N(\mathbb{C})$ is finitely generated, we can arrange that $G\subset\mathrm{GL}_N(R)$, where $R\subset\mathbb{C}$ is the subring generated by the entries of a finite collection of generators for $G$. In particular, this is an integral domain, since it is a finitely generated subring of $\mathbb{C}$. Thus, given $x$ a nonzero element of $g-1$ as above, we can find a prime ideal $\mathcal{P}$ of $R$ that does not divide $x$, i.e. $x\notin\mathcal{P}$.

Now, $R/\mathcal{P}$ is a finite integral domain, that is, a finite field, and we can build a reduction homomorphism $\phi_{\mathcal{P}}$ analogous to the situation over the integers. The the image of the reduction homomorphism is the general linear group of a finite field, so it is a finite group. We now proceed exactly as above.  $\square$

This theorem is often referred to as Selberg’s Lemma, even though Malcev supposedly proved it first.

(3) Free groups $F_r$ of finite rank are linear, so they are RF. Notice that we have seen, in the exercise from the first lecture, that $F_r$ is a subgroup of $F_2$ for all $r\geq 0$, so it suffices to prove that $F_2$ is linear. One such representation the subgroup of $\mathrm{SL}_2(\mathbb{Z})$ generated by the two matrices

$a=\left(\begin{matrix} 1 & 2 \\ 0 & 1\end{matrix}\right)$

$b=\left(\begin{matrix} 1 & 0 \\ 2 & 1\end{matrix}\right).$

There are several ways to prove that this group is free of rank two. First, one use a bit of hyperbolic geometry and the action of $\mathrm{SL}_2(\mathbb{R})$ on the hyperbolic plane to prove that this group is the fundamental group of a hyperbolic manifold that is deformation equivalent to the rose with two petals. Also, one can use the so-called Ping-Pong Lemma, which says that a finite collection of homeomorphisms of a space that satisfy a certain set of conditions necessarily generate a free subgroup of the homeomorphism group.

We begin with a lemma that among other things demonstrates that most free groups are non-trivial

Lemma 1: If $T\subset S$ are sets then the map $\iota: F_T\to F_S$, induced by inclusion has a left inverse. Consequently, $\iota$ is injective.

Proof: Let $X_T$ and $X_S$ be the roses with petals indexed by $T$ and $S$ respectively. In particular we have that $F_T=\pi_1(X_T)$ and $F_S=\pi(X_S)$. If we view $X_T$ as a subspace of $X_S$ in the obvious way then there exists $p:X_S\to X_T$ such that $p|_{X_T}=Id$ (One such map is obtained by crushing the petals in $X_S\smallsetminus X_T$). This map $p$ induces a function $p_\ast :\pi_1(X_S)\to \pi_1(X_T)$ and this map can easily be seen to be the desired left inverse. QED

The next thing that we would like to do is examine exactly what do elements of free groups “look like.” Informally, elements look like words in the elements of $S$ where only the obvious cancellations by inverses are allowed. More formally, we will identify the elements of $S$ with their images under the map $\iota: S\to F_S$ (This is not the same $\iota$ from Lemma 1). Next we consider products of the form $w=s_1^{\epsilon_1}s_2^{\epsilon_2}\ldots s_k^{\epsilon_k}$, where $s_i\in S$ and $\epsilon_i=\pm 1$. Next, we prove a theorem that formalizes the previous intuition about free groups

Normal Form Theorem: Given a free group $F_S$ the following 2 statements are true

1. Every element of $F_S$ is of the form $w$.
2. If $w=1$ then $w$ is either the empty word or there exists $1\leq j\leq k-1$ such that $s_j=s_{j+1}$ and $\epsilon_j=-\epsilon_{j+1}$

Proof: We will prove the theorem when $S=\{a,b\}$, but the proof generalizes to sets of all cardinality. Let $X_S$ be the rose with 2 petals and wedge point $v$ and so we have that $F_S=\pi_1(X_S,v)$. Next, let $T_S$ be the universal cover of $X_S$ based at $t_0$. Because $F_S$ acts freely on $T_S$ and $X_S$ has only one vertex we see that the vertices of $T_S$ are in bijection with the elements of $F_S$. We next observe 2 facts. First, from lemma 1 we see that since $T_S$ is simply connected that it must be a tree. Second, since each vertex of $T_S$ looks locally like $v$ we see that every vertex of $T_S$ is 4-valent. From covering space theory we know that if $g\in \pi_1(X_S,v)$ and $t$ is a vertex of $T_S$ then the lift of $g$ to $T_S$ that starts at $t$ ends at $g\cdot t$.

We proceed by induction on $d(t_0,g\cdot t_0)$, which is the minimum number of edges between $t_0$ and $g\cdot t_0$.  Suppose that $d(t_0,g\cdot t_0)=k$. Since $T_S$ is a tree with all 4-valent vertices we see that there exists $h\in \pi_1(X_S,v)$ such that $d(t_0,h\cdot t_0) and $d(h\cdot t_0, g\cdot t_0)=1$. Next, observe that there exists $c\in \{a,b,a^{-1},b^{-1}\}$ such that when $c$ is lifted at $g\cdot t_0$ ends at $h\cdot t_0$. Therefore we see that $cg\cdot t_0=h\cdot t_0$ and since the group action is free this implies that $h=ag$ which proves 1.

For the second proposition, suppose that $w=1$ and that the second proposition is not true. From covering space theory we know that the lift of $w$ at $v$ is a loop based at $v$. First, since $w$ is not the empty word we see that it will not lift to the constant path. Finally, since $w$ contains no obvious cancellations we see that $T_S$ must contain a loop based at $v$ that is not the constant loop, which contradicts the fact that $T_S$ is a tree. Thus 2 must hold. QED

As a consequence of the previous theorem we see that it is possible to solve the word problem of whether it is algorithmically possible to decide if a group element is the identity.

Definition: A group $G$ is finitely generated if and only if there exists a surjection from $F_k$ to $G$ for some finite $k$.

Exercise 2:

1. Show that if $r<\infty$ then $F_r$ has finitely many subgroups of index $d<\infty$.
2. Deduce that the same holds for any finitely generated group $G$.