Ping-pong lemma

In mathematics, the ping-pong lemma, or table-tennis lemma, is any of several mathematical statements that ensure that several elements in a group acting on a set freely generates a free subgroup of that group.

The ping-pong argument goes back to the late 19th century and is commonly attributed^[1] to Felix Klein who used it to study subgroups of Kleinian groups, that is, of discrete groups of isometries of the hyperbolic 3-space or, equivalently Möbius transformations of the Riemann sphere. The ping-pong lemma was a key tool used by Jacques Tits in his 1972 paper^[2] containing the proof of a famous result now known as the Tits alternative. The result states that a finitely generated linear group is either virtually solvable or contains a free subgroup of rank two. The ping-pong lemma and its variations are widely used in geometric topology and geometric group theory.

Modern versions of the ping-pong lemma can be found in many books such as Lyndon & Schupp,^[3] de la Harpe,^[1] Bridson & Haefliger^[4] and others.

This version of the ping-pong lemma ensures that several subgroups of a group acting on a set generate a free product. The following statement appears in Olijnyk and Suchchansky (2004),^[5] and the proof is from de la Harpe (2000).^[1]

Let G be a group acting on a set X and let H₁, H₂, ..., H_k be subgroups of G where k ≥ 2, such that at least one of these subgroups has order greater than 2. Suppose there exist pairwise disjoint nonempty subsets X₁, X₂, ...,X_k of X such that the following holds:

• For any i ≠ s and for any h in H_i, h ≠ 1 we have h(X_s) ⊆ X_i.

Then $${\displaystyle \langle H_{1},\dots ,H_{k}\rangle =H_{1}\ast \dots \ast H_{k}.}$$

By the definition of free product, it suffices to check that a given (nonempty) reduced word represents a nontrivial element of ${\displaystyle G}$. Let ${\displaystyle w}$ be such a word of length ${\displaystyle m\geq 2}$, and let $${\displaystyle w=\prod _{i=1}^{m}w_{i},}$$ where ${\textstyle w_{i}\in H_{\alpha _{i}}}$ for some ${\textstyle \alpha _{i}\in \{1,\dots ,k\}}$. Since ${\textstyle w}$ is reduced, we have ${\displaystyle \alpha _{i}\neq \alpha _{i+1}}$ for any ${\displaystyle i=1,\dots ,m-1}$ and each ${\displaystyle w_{i}}$ is distinct from the identity element of ${\displaystyle H_{\alpha _{i}}}$. We then let ${\displaystyle w}$ act on an element of one of the sets ${\textstyle X_{i}}$. As we assume that at least one subgroup ${\displaystyle H_{i}}$ has order at least 3, without loss of generality we may assume that ${\displaystyle H_{1}}$ has order at least 3. We first make the assumption that ${\displaystyle \alpha _{1}}$and ${\displaystyle \alpha _{m}}$ are both 1 (which implies ${\displaystyle m\geq 3}$). From here we consider ${\displaystyle w}$ acting on ${\displaystyle X_{2}}$. We get the following chain of containments: $${\displaystyle w(X_{2})\subseteq \prod _{i=1}^{m-1}w_{i}(X_{1})\subseteq \prod _{i=1}^{m-2}w_{i}(X_{\alpha _{m-1}})\subseteq \dots \subseteq w_{1}(X_{\alpha _{2}})\subseteq X_{1}.}$$

By the assumption that different ${\displaystyle X_{i}}$'s are disjoint, we conclude that ${\displaystyle w}$ acts nontrivially on some element of ${\displaystyle X_{2}}$, thus ${\displaystyle w}$ represents a nontrivial element of ${\displaystyle G}$.

To finish the proof we must consider the three cases:

• if ${\displaystyle \alpha _{1}=1,\,\alpha _{m}\neq 1}$, then let ${\displaystyle h\in H_{1}\setminus \{w_{1}^{-1},1\}}$ (such an ${\displaystyle h}$ exists since by assumption ${\displaystyle H_{1}}$ has order at least 3);
• if ${\displaystyle \alpha _{1}\neq 1,\,\alpha _{m}=1}$, then let ${\displaystyle h\in H_{1}\setminus \{w_{m},1\}}$;
• and if ${\displaystyle \alpha _{1}\neq 1,\,\alpha _{m}\neq 1}$, then let ${\displaystyle h\in H_{1}\setminus \{1\}}$.

In each case, ${\displaystyle hwh^{-1}}$ after reduction becomes a reduced word with its first and last letter in ${\displaystyle H_{1}}$. Finally, ${\displaystyle hwh^{-1}}$ represents a nontrivial element of ${\displaystyle G}$, and so does ${\displaystyle w}$. This proves the claim.

Let G be a group acting on a set X. Let a₁, ...,a_k be elements of G of infinite order, where k ≥ 2. Suppose there exist disjoint nonempty subsets

of X with the following properties:

• a_i(X − X_i^–) ⊆ X_i⁺ for i = 1, ..., k;
• a_i⁻¹(X − X_i⁺) ⊆ X_i^– for i = 1, ..., k.

Then the subgroup H = ⟨a₁, ..., a_k⟩ ≤ G generated by a₁, ..., a_k is free with free basis {a₁, ..., a_k}.

This statement follows as a corollary of the version for general subgroups if we let X_i = X_i⁺ ∪ X_i⁻ and let H_i = ⟨a_i⟩.

One can use the ping-pong lemma to prove^[1] that the subgroup H = ⟨A,B⟩ ≤ SL₂(Z), generated by the matrices $${\displaystyle A={\begin{pmatrix}1&2\\0&1\end{pmatrix}}}$$ and $${\displaystyle B={\begin{pmatrix}1&0\\2&1\end{pmatrix}}}$$ is free of rank two.

Indeed, let H₁ = ⟨A⟩ and H₂ = ⟨B⟩ be cyclic subgroups of SL₂(Z) generated by A and B accordingly. It is not hard to check that A and B are elements of infinite order in SL₂(Z) and that $${\displaystyle H_{1}=\{A^{n}\mid n\in \mathbb {Z} \}=\left\{{\begin{pmatrix}1&2n\\0&1\end{pmatrix}}:n\in \mathbb {Z} \right\}}$$ and $${\displaystyle H_{2}=\{B^{n}\mid n\in \mathbb {Z} \}=\left\{{\begin{pmatrix}1&0\\2n&1\end{pmatrix}}:n\in \mathbb {Z} \right\}.}$$

Consider the standard action of SL₂(Z) on R² by linear transformations. Put $${\displaystyle X_{1}=\left\{{\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}:|x|>|y|\right\}}$$ and $${\displaystyle X_{2}=\left\{{\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}:|x|<|y|\right\}.}$$

It is not hard to check, using the above explicit descriptions of H₁ and H₂, that for every nontrivial g ∈ H₁ we have g(X₂) ⊆ X₁ and that for every nontrivial g ∈ H₂ we have g(X₁) ⊆ X₂. Using the alternative form of the ping-pong lemma, for two subgroups, given above, we conclude that H = H₁ ∗ H₂. Since the groups H₁ and H₂ are infinite cyclic, it follows that H is a free group of rank two.

Let G be a word-hyperbolic group which is torsion-free, that is, with no nonidentity elements of finite order. Let g, h ∈ G be two non-commuting elements, that is such that gh ≠ hg. Then there exists M ≥ 1 such that for any integers n ≥ M, m ≥ M the subgroup H = ⟨gⁿ, h^m⟩ ≤ G is free of rank two.

The group G acts on its hyperbolic boundary ∂G by homeomorphisms. It is known that if a in G is a nonidentity element then a has exactly two distinct fixed points, a^∞ and a^−∞ in ∂G and that a^∞ is an attracting fixed point while a^−∞ is a repelling fixed point.

Since g and h do not commute, basic facts about word-hyperbolic groups imply that g^∞, g^−∞, h^∞ and h^−∞ are four distinct points in ∂G. Take disjoint neighborhoods U₊, U_–, V₊, and V_– of g^∞, g^−∞, h^∞ and h^−∞ in ∂G respectively. Then the attracting/repelling properties of the fixed points of g and h imply that there exists M ≥ 1 such that for any integers n ≥ M, m ≥ M we have:

• gⁿ(∂G – U_–) ⊆ U₊
• g⁻ⁿ(∂G – U₊) ⊆ U_–
• h^m(∂G – V_–) ⊆ V₊
• h^−m(∂G – V₊) ⊆ V_–

The ping-pong lemma now implies that H = ⟨gⁿ, h^m⟩ ≤ G is free of rank two.

• The ping-pong lemma is used in Kleinian groups to study their so-called Schottky subgroups. In the Kleinian groups context the ping-pong lemma can be used to show that a particular group of isometries of the hyperbolic 3-space is not just free but also properly discontinuous and geometrically finite.
• Similar Schottky-type arguments are widely used in geometric group theory, particularly for subgroups of word-hyperbolic groups^[6] and for automorphism groups of trees.^[7]
• The ping-pong lemma is also used for studying Schottky-type subgroups of mapping class groups of Riemann surfaces, where the set on which the mapping class group acts is the Thurston boundary of the Teichmüller space.^[8] A similar argument is also utilized in the study of subgroups of the outer automorphism group of a free group.^[9]
• One of the most famous applications of the ping-pong lemma is in the proof of Jacques Tits of the so-called Tits alternative for linear groups.^[2] (see also ^[10] for an overview of Tits' proof and an explanation of the ideas involved, including the use of the ping-pong lemma).
• There are generalizations of the ping-pong lemma that produce not just free products but also amalgamated free products and HNN extensions.^[3] These generalizations are used, in particular, in the proof of Maskit's Combination Theorem for Kleinian groups.^[11]
• There are also versions of the ping-pong lemma which guarantee that several elements in a group generate a free semigroup. Such versions are available both in the general context of a group action on a set,^[12] and for specific types of actions, e.g. in the context of linear groups,^[13] groups acting on trees^[14] and others.^[15]

• Free group
• Free product
• Kleinian group
• Tits alternative
• Word-hyperbolic group
• Schottky group