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.

History

The ping-pong argument goes back to 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.

Formal statements

Ping-pong lemma for several subgroups

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,^[5] and the proof is from.^[1]

Let G be a group acting on a set X and let H₁, H₂,...., H_k be nontrivial 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∈H_i, h≠1 we have h(X_s)⊆X_i.

Then

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

Proof

By the definition of free product, it suffices to check that a given reduced word is nontrivial. Let w be such a word, and let

w=\prod _{{i=1}}^{m}w_{{\alpha _{i},\beta _{i}}}.

Where w_{s,β_k}∈ H_s for all such β_k, and since w is fully reduced α_i≠ α_i+1 for any i. We then let w act on an element of one of the sets X_i. As we assume for at least one subgroup H_i has order at least 3, without loss we may assume that H₁ is at least 3. We first make the assumption that α₁ and α_m are both 1. From here we consider w acting on X₂. We get the following chain of containments and note that since the X_i are disjoint that w acts nontrivially and is thus not the identity element.

w(X_{2})\subseteq \prod _{{i=1}}^{{m-1}}w_{{\alpha _{i},\beta _{i}}}(X_{1})\subseteq \prod _{{i=1}}^{{m-2}}w_{{\alpha _{i},\beta _{i}}}(X_{{\alpha _{{m-1}}}})\subseteq \dots \subseteq w_{{1,\beta _{1}}}w_{{\alpha _{2},\beta _{2}}}(X_{{\alpha _{3}}})\subseteq

\subseteq w_{{1,\beta _{1}}}(X_{{\alpha _{2}}})\subseteq X_{1}

To finish the proof we must consider the three cases:

If $\alpha _{1}=1;\alpha _{m}\neq 1$ , then let $h\in H_{1}\setminus \{w_{{1,\beta _{1}}}^{{-1}},1\}$
If $\alpha _{1}\neq 1;\alpha _{m}=1$ , then let $h\in H_{1}\setminus \{w_{{1,\beta _{m}}},1\}$
And if $\alpha _{1}\neq 1;\alpha _{m}\neq 1$ , then let $h\in H_{1}\setminus \{1\}$

In each case, hwh⁻¹ is a reduced word with α₁' and α_{m '}' both 1, and thus is nontrivial. Finally, hwh⁻¹ is not 1, and so neither is w. This proves the claim.

The Ping-pong lemma for cyclic subgroups

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

X₁⁺,...,X_k⁺ and X₁^–,...,X_k^–

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

Proof

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⟩.

Examples

Special linear group example

One can use the ping-pong lemma to prove^[1] that the subgroup H = <A,B>≤SL(2,Z), generated by the matrices

\scriptstyle A={\begin{pmatrix}1&2\\0&1\end{pmatrix}}

and

\scriptstyle B={\begin{pmatrix}1&0\\2&1\end{pmatrix}}

is free of rank two.

Proof

Indeed, let H₁ = <A> and H₂ = <B> be cyclic subgroups of SL(2,Z) generated by A and B accordingly. It is not hard to check that A and B are elements of infinite order in SL(2,Z) and that

H_{1}=\{A^{n}|n\in {\mathbb Z}\}=\left\{{\begin{pmatrix}1&2n\\0&1\end{pmatrix}}:n\in {\mathbb Z}\right\}

and

H_{2}=\{B^{n}|n\in {\mathbb Z}\}=\left\{{\begin{pmatrix}1&0\\2n&1\end{pmatrix}}:n\in {\mathbb Z}\right\}.

Consider the standard action of SL(2,Z) on R² by linear transformations. Put

X_{1}=\left\{{\begin{pmatrix}x\\y\end{pmatrix}}\in {\mathbb R}^{2}:|x|>|y|\right\}

and

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 explicitly 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.

Word-hyperbolic group example

Let G be a word-hyperbolic group which is torsion-free, that is, with no nontrivial 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.

Sketch of the proof^[6]

The group G acts on its hyperbolic boundary ∂G by homeomorphisms. It is known that if a ∈ G is a nontrivial 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, the 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.

Applications of the ping-pong lemma

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]
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]

References

1 2 3 4 Pierre de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago. ISBN 0-226-31719-6; Ch. II.B "The table-Tennis Lemma (Klein's criterion) and examples of free products"; pp. 25–41.
1 2 J. Tits. Free subgroups in linear groups. Journal of Algebra, vol. 20 (1972), pp. 250–270
1 2 Roger C. Lyndon and Paul E. Schupp. Combinatorial Group Theory. Springer-Verlag, New York, 2001. "Classics in Mathematics" series, reprint of the 1977 edition. ISBN 978-3-540-41158-1; Ch II, Section 12, pp. 167–169
↑ Martin R. Bridson, and André Haefliger. Metric spaces of non-positive curvature. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 319. Springer-Verlag, Berlin, 1999. ISBN 3-540-64324-9; Ch.III.Γ, pp. 467–468
↑ Andrij Olijnyk and Vitaly Suchchansky. Representations of free products by infinite unitriangular matrices over finite fields. International Journal of Algebra and Computation. Vol. 14 (2004), no. 5–6, pp. 741–749; Lemma 2.1
1 2 M. Gromov. Hyperbolic groups. Essays in group theory, pp. 75–263, Mathematical Sciences Research Institute Publications, 8, Springer, New York, 1987; ISBN 0-387-96618-8; Ch. 8.2, pp. 211–219.
↑ Alexander Lubotzky. Lattices in rank one Lie groups over local fields. Geometric and Functional Analysis, vol. 1 (1991), no. 4, pp. 406–431
↑ Richard P. Kent, and Christopher J. Leininger. Subgroups of mapping class groups from the geometrical viewpoint. In the tradition of Ahlfors-Bers. IV, pp. 119–141, Contemporary Mathematics series, 432, American Mathematical Society, Providence, RI, 2007; ISBN 978-0-8218-4227-0; 0-8218-4227-7
↑ M. Bestvina, M. Feighn, and M. Handel. Laminations, trees, and irreducible automorphisms of free groups. Geometric and Functional Analysis, vol. 7 (1997), no. 2, pp. 215–244.
↑ Pierre de la Harpe. Free groups in linear groups. L'Enseignement Mathématique (2), vol. 29 (1983), no. 1-2, pp. 129–144
↑ Bernard Maskit. Kleinian groups. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 287. Springer-Verlag, Berlin, 1988. ISBN 3-540-17746-9; Ch. VII.C and Ch. VII.E pp.149–156 and pp. 160–167
↑ Pierre de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago. ISBN 0-226-31719-6; Ch. II.B "The table-Tennis Lemma (Klein's criterion) and examples of free products"; pp. 187–188.
↑ Alex Eskin, Shahar Mozes and Hee Oh. On uniform exponential growth for linear groups. Inventiones Mathematicae. vol. 60 (2005), no. 1, pp.1432–1297; Lemma 2.2
↑ Roger C. Alperin and Guennadi A. Noskov. Uniform growth, actions on trees and GL₂. Computational and Statistical Group Theory:AMS Special Session Geometric Group Theory, April 21–22, 2001, Las Vegas, Nevada, AMS Special Session Computational Group Theory, April 28–29, 2001, Hoboken, New Jersey. (Robert H. Gilman, Vladimir Shpilrain, Alexei G. Myasnikov, editors). American Mathematical Society, 2002. ISBN 978-0-8218-3158-8; page 2, Lemma 3.1
↑ Yves de Cornulier and Romain Tessera. Quasi-isometrically embedded free sub-semigroups. Geometry & Topology, vol. 12 (2008), pp. 461–473; Lemma 2.1

Ping-pong lemma

History

Formal statements

Ping-pong lemma for several subgroups

Proof

The Ping-pong lemma for cyclic subgroups

Proof

Examples

Special linear group example

Proof

Word-hyperbolic group example

Sketch of the proof[6]

Applications of the ping-pong lemma

References

See also

Sketch of the proof^[6]