ping-pong lemma

Theorem (Ping Pong Lemma).

Let $k\mathrm{\ge }\mathrm{2}$ and let $G$ be a group acting on a space $X$. Suppose we are given a class $\mathrm{M}\mathrm{=}\mathrm{\{}{A}_{\mathrm{1}}\mathrm{,}{A}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathrm{,}{A}_k\mathrm{,}{B}_{\mathrm{1}}\mathrm{,}{B}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathrm{,}{B}_k\mathrm{\}}$ of $\mathrm{2}\mathit{}k$ pairwise disjoint subsets of $X$ and suppose $y_{\mathrm{1}}\mathrm{,}{y}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathrm{,}{y}_k$ are elements of $G$ such that

$$B_i^c\subseteq y_i(A_i)\mathit{\hspace{1em}}i=1,2,\mathrm{\dots },k$$

($B_i^c$ is the complement of $B_i$ in $X$). Then, the subgroup of $G$ generated by $y_{\mathrm{1}}\mathrm{,}{y}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathrm{,}{y}_k$ is free.

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

Fact 1.

For all $i\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{\dots }\mathrm{,}k$ we have $y_i\mathit{}\mathrm{(}{A}_i^c\mathrm{)}\mathrm{\subseteq }{B}_i$ and $y_i^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}{B}_i^c\mathrm{)}\mathrm{\subseteq }{A}_i$

Proof.

$B_i^c\subseteq y_i(A_i)⟹B_i\supseteq y_i{(A_i)}^c=y_i(A_i^c)$ ∎

Fact 2.

If $i\mathrm{\ne }j$ then $A_j\mathrm{\cup }{B}_j\mathrm{\subseteq }{A}_i^c\mathrm{\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\mathrm{,}S\mathrm{\in }\mathrm{M}$ then $R^c\mathrm{⊈}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^{{ϵ}_n}\mathrm{\cdots }{z}_2^{{ϵ}_2}{z}_1^{{ϵ}_1}$ such that $z_{\mathrm{\ell }}\in \{y_1,y_2,\mathrm{\dots },y_k\}$ and ${ϵ}_{\mathrm{\ell }}\in \{-1,+1\}$. and suppose further that $w$ is freely reduced, namely, if $z_i=z_{i+1}$ then ${ϵ}_i={ϵ}_{i+1}$. We want to show that $w\ne 1$ in $G$. Assume by contradiction that $w=1$. We get a contradiction by giving $R,S\in ℳ$ 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:

Define the following subsets $P_0,P_1,\mathrm{\dots },P_n$ of $X$:

$$P_0=S^c;P_1=z_1^{{ϵ}_1}(P_0),\mathrm{\dots },P_n=z_n^{{ϵ}_n}(P_{n-1})=w(S^c)$$

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

1. if ${ϵ}_{\mathrm{\ell }}=1$ then $P_{\mathrm{\ell }}\subseteq B_i$.

2. if ${ϵ}_{\mathrm{\ell }}=-1$ then $P_{\mathrm{\ell }}\subseteq A_i$.

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

1. $z_{\mathrm{\ell }-1}\ne z_{\mathrm{\ell }}$: by the induction hypothesis $P_{\mathrm{\ell }-1}$ is a subset of $A_j\cup B_j$ for some $j\ne i$. Therefore, by Fact 2 we get that $P_{\mathrm{\ell }-1}$ is a subset of $A_i^c\cap B_i^c$. Consequently, we get the following:

   $$P_{\mathrm{\ell }}=z_{\mathrm{\ell }}^{{ϵ}_{\mathrm{\ell }}}(P_{\mathrm{\ell }-1})=y_i^{{ϵ}_{\mathrm{\ell }}}(P_{\mathrm{\ell }-1})\subseteq y_i^{{ϵ}_{\mathrm{\ell }}}(A_i^c\cap B_i^c)$$

   Hence, if ${ϵ}_{\mathrm{\ell }}=1$ then:

   $$P_{\mathrm{\ell }}\subseteq y_i(A_i^c\cap B_i^c)\subseteq y_i(A_i^c)\subseteq B_i$$

   And if ${ϵ}_{\mathrm{\ell }}=-1$ then:

   $$P_{\mathrm{\ell }}\subseteq y_i^{-1}(A_i^c\cap B_i^c)\subseteq y_i^{-1}(B_i^c)\subseteq A_i$$

2. $z_{\mathrm{\ell }-1}=z_{\mathrm{\ell }}$: by the fact that $w$ is freely reduced we get an equality between ${ϵ}_{\mathrm{\ell }-1}$ and ${ϵ}_{\mathrm{\ell }}$. Hence, if ${ϵ}_{\mathrm{\ell }}=1$ then $P_{\mathrm{\ell }-1}\subseteq B_i\subseteq A_i^c$ and therefore:

   $$P_{\mathrm{\ell }}=z_{\mathrm{\ell }}^{{ϵ}_{\mathrm{\ell }}}(P_{\mathrm{\ell }-1})=y_i(P_{\mathrm{\ell }-1})\subseteq y_i(A_i^c)\subseteq B_i$$

   Similiarly, if ${ϵ}_{\mathrm{\ell }}=-1$ then $P_{\mathrm{\ell }-1}\subseteq A_i\subseteq B_i^c$ and therefore:

   $$P_{\mathrm{\ell }}=z_{\mathrm{\ell }}^{{ϵ}_{\mathrm{\ell }}}(P_{\mathrm{\ell }-1})=y_i^{-1}(P_{\mathrm{\ell }-1})\subseteq y_i^{-1}(B_i^c)\subseteq A_i$$

∎

Title	ping-pong lemma
Canonical name	PingpongLemma
Date of creation	2013-03-22 17:11:21
Last modified on	2013-03-22 17:11:21
Owner	uriw (288)
Last modified by	uriw (288)
Numerical id	8
Author	uriw (288)
Entry type	Theorem
Classification	msc 20F65
Synonym	table-tennis lemma