PlanetMath: ping-pong lemma

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

ping-pong lemma

(Theorem)

Theorem 1 (Ping Pong Lemma) Let $k\geq2$ and let be a group acting on a space . Suppose we are given a class $\mathcal{M}=\{A_1,A_2,\ldots,A_k,B_1,B_2,\ldots,B_k\}$ of pairwise disjoint subsets of and suppose $y_1,y_2,\ldots,y_k$ are elements of such that

$\displaystyle B_i^c \subseteq y_i(A_i)\quad i=1,2,\ldots,k$

( is the complement of in ). Then, the subgroup of generated by $y_1,y_2,\ldots,y_k$ is free.

Before turning to prove the lemma let's state three simple facts:

Fact 1 For all $i=1,\ldots,k$ we have $y_i(A_i^c)\subseteq B_i$ and $y_i^{-1}(B_i^c)\subseteq A_i$

Proof. $B_i^c \subseteq y_i(A_i) \implies B_i \supseteq y_i(A_i)^c = y_i(A_i^c)$ $\qedsymbol$

Fact 2 If $i\neq j$ then $A_j\cup B_j \subseteq A_i^c\cap B_i^c$ .

Proof.

and

are disjoint therefore $A_j\subseteq A_i^c$ . Similarly, $A_j\subseteq B_i^c$ so $A_j\subseteq A_i^c\cap B_i^c$ . In the same way, $B_j\subseteq A_i^c\cap B_i^c$ so $A_j\cup B_j \subseteq A_i^c\cap B_i^c$ . $\qedsymbol$

Fact 3 If $R,S\in\mathcal{M}$ then $R^c\not\subseteq S$

Proof. Assume by contradiction that $R^c\subseteq S$ . Then, $X=R\cup S$ and therefore any element of

intersects with either

. However, the elements of

are pairwise disjoint and there are at least 4 elements in

so this is a contradiction. $\qedsymbol$

Using the above 3 facts, we now turn to the proof of the Ping Pong Lemma:

Proof. Suppose we are given $w=z_n^{\epsilon_n}\cdots z_2^{\epsilon_2}z_1^{\epsilon_1}$ such that $z_\ell\in\{y_1,y_2,\ldots,y_k\}$ and $\epsilon_\ell\in\{-1,+1\}$ . and suppose further that

is freely reduced, namely, if $z_i=z_{i+1}$ then $\epsilon_i=\epsilon_{i+1}$ . We want to show that $w\neq1$ in

. Assume by contradiction that

. We get a contradiction by giving $R,S\in\mathcal{M}$ such that $w(S^c)\subseteq R$ and therefore contradicting Fact 3 above since $S^c=w(S^c)\subseteq R$ .

The set is chosen as follows. Assume that then:

$\displaystyle S=\left\{\begin{array}{ll} A_i & \text{if } \epsilon_1=1 \ B_i & \text{if } \epsilon_1=-1 \end{array} \right.$

Define the following subsets $P_0,P_1,\ldots,P_n$ of

$\displaystyle P_0 = S^c; \quad P_1=z_1^{\epsilon_1}(P_0), \ldots ,\; P_n=z_n^{\epsilon_n}(P_{n-1})=w(S^c)$

To complete the proof we show by induction that for $\ell=1,2,\ldots,n$ if $z_\ell=y_i$ then:

if $\epsilon_\ell=1$ then $P_\ell\subseteq B_i$ .
if $\epsilon_\ell=-1$ then $P_\ell\subseteq A_i$ .

For $\ell=1$ the above follows from Fact 1 and the specific choice of

. Assume it is true for $\ell-1$ and assume that $z_\ell=y_i$ . We have two cases to check:

$z_{\ell-1}\neq z_\ell$ : by the induction hypothesis $P_{\ell-1}$ is a subset of $A_j\cup B_j$ for some $j\neq i$ . Therefore, by Fact 2 we get that $P_{\ell-1}$ is a subset of $A_i^c\cap B_i^c$ . Consequently, we get the following:
$\displaystyle P_\ell = z_\ell^{\epsilon_\ell}(P_{\ell-1}) = y_i^{\epsilon_\ell}(P_{\ell-1}) \subseteq y_i^{\epsilon_\ell}(A_i^c\cap B_i^c)$
Hence, if $\epsilon_\ell=1$ then:
$\displaystyle P_\ell \subseteq y_i(A_i^c\cap B_i^c) \subseteq y_i(A_i^c) \subseteq B_i$
And if $\epsilon_\ell=-1$ then:
$\displaystyle P_\ell \subseteq y_i^{-1}(A_i^c\cap B_i^c) \subseteq y_i^{-1}(B_i^c) \subseteq A_i$
$z_{\ell-1}=z_\ell$ : by the fact that is freely reduced we get an equality between $\epsilon_{\ell-1}$ and $\epsilon_\ell$ . Hence, if $\epsilon_\ell=1$ then $P_{\ell-1}\subseteq B_i\subseteq A_i^c$ and therefore:
$\displaystyle P_\ell = z_\ell^{\epsilon_\ell}(P_{\ell-1}) = y_i(P_{\ell-1}) \subseteq y_i(A_i^c) \subseteq B_i$
Similiarly, if $\epsilon_\ell=-1$ then $P_{\ell-1}\subseteq A_i\subseteq B_i^c$ and therefore:
$\displaystyle P_\ell = z_\ell^{\epsilon_\ell}(P_{\ell-1}) = y_i^{-1}(P_{\ell-1}) \subseteq y_i^{-1}(B_i^c) \subseteq A_i$