PingPongLemma 2007-06-03 10:23:11 2007-06-03 21:46:17 Theorem % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amsthm} \newtheorem*{theorem}{Theorem} \newtheorem{fact}{Fact} \begin{theorem}[Ping Pong Lemma] Let $k\geq2$ 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. \end{theorem} \PMlinkescapeword{simple} \noindent Before turning to prove the lemma let's state three simple facts: \begin{fact} \label{fct1} 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$ \end{fact} \begin{proof} $B_i^c \subseteq y_i(A_i) \implies B_i \supseteq y_i(A_i)^c = y_i(A_i^c)$ \end{proof} \begin{fact} \label{fct2} If $i\neq j$ then $A_j\cup B_j \subseteq A_i^c\cap B_i^c$. \end{fact} \begin{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$. \end{proof} \begin{fact} \label{fct3} If $R,S\in\mathcal{M}$ then $R^c\not\subseteq S$ \end{fact} \begin{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. \end{proof} \bigskip Using the above 3 facts, we now turn to the proof of the Ping Pong Lemma: \begin{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\neq1$ 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 \ref{fct3} 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) \] \PMlinkescapeword{complete} To complete the proof we show by induction that for $\ell=1,2,\ldots,n$ if $z_\ell=y_i$ then: \begin{enumerate} \item if $\epsilon_\ell=1$ then $P_\ell\subseteq B_i$. \item if $\epsilon_\ell=-1$ then $P_\ell\subseteq A_i$. \end{enumerate} For $\ell=1$ the above follows from Fact \ref{fct1} 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: \begin{enumerate} \item $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 \ref{fct2} 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 \] \item $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 \] \end{enumerate} \end{proof}