# ping-pong lemma

###### Theorem (Ping Pong Lemma).

Let $k\geq 2$ and let $G$ be a group acting on a space $X$. Suppose we are given a class $\mathcal{M}=\{A_{1},A_{2},\ldots,A_{k},B_{1},B_{2},\ldots,B_{k}\}$ of $2k$ pairwise disjoint subsets of $X$ and suppose $y_{1},y_{2},\ldots,y_{k}$ are elements of $G$ such that

 $B_{i}^{c}\subseteq y_{i}(A_{i})\quad i=1,2,\ldots,k$

($B_{i}^{c}$ is the complement of $B_{i}$ in $X$). Then, the subgroup   of $G$ 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})$

###### Fact 2.

If $i\neq j$ then $A_{j}\cup B_{j}\subseteq A_{i}^{c}\cap B_{i}^{c}$.

###### Proof.

$A_{i}$ and $A_{j}$ 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}$. ∎

###### 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 $M$ intersects with either $R$ or $S$. However, the elements of $M$ are pairwise disjoint and there are at least 4 elements in $M$ so this is a contradiction. ∎

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 $w$ is freely reduced, namely, if $z_{i}=z_{i+1}$ then $\epsilon_{i}=\epsilon_{i+1}$. We want to show that $w\neq 1$ in $G$. Assume by contradiction that $w=1$. 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 $S$ is chosen as follows. Assume that $z_{1}=y_{i}$ then:

 $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 $X$:

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

if $\epsilon_{\ell}=1$ then $P_{\ell}\subseteq B_{i}$.

2. 2.

if $\epsilon_{\ell}=-1$ then $P_{\ell}\subseteq A_{i}$.

For $\ell=1$ the above follows from Fact 1 and the specific choice of $P_{0}$. Assume it is true for $\ell-1$ and assume that $z_{\ell}=y_{i}$. We have two cases to check:

1. 1.

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

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

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

 $P_{\ell}\subseteq y_{i}^{-1}(A_{i}^{c}\cap B_{i}^{c})\subseteq y_{i}^{-1}(B_{i% }^{c})\subseteq A_{i}$
2. 2.

$z_{\ell-1}=z_{\ell}$: by the fact that $w$ 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:

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

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

Title ping-pong lemma PingpongLemma 2013-03-22 17:11:21 2013-03-22 17:11:21 uriw (288) uriw (288) 8 uriw (288) Theorem  msc 20F65 table-tennis lemma