In mathematics, the ping-pong lemma, or table-tennis lemma, is any of several mathematical statements that ensure that several elements in a groupacting on a set freely generates a freesubgroup of that group.
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 statementsedit
Ping-pong lemma for several subgroupsedit
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 H1, H2, ..., Hk be subgroups of G where k ≥ 2, such that at least one of these subgroups has order greater than 2.
Suppose there exist pairwise disjointnonempty subsets X1, X2, ...,Xk of X such that the following holds:
For any i ≠ s and for any h in Hi, h ≠ 1 we have h(Xs) ⊆ Xi.
Then
Proofedit
By the definition of free product, it suffices to check that a given (nonempty) reduced word represents a nontrivial element of . Let be such a word of length , and let
where for some . Since is reduced, we have for any and each is distinct from the identity element of . We then let act on an element of one of the sets . As we assume that at least one subgroup has order at least 3, without loss of generality we may assume that has order at least 3. We first make the assumption that and are both 1 (which implies ). From here we consider acting on . We get the following chain of containments:
By the assumption that different 's are disjoint, we conclude that acts nontrivially on some element of , thus represents a nontrivial element of .
To finish the proof we must consider the three cases:
if , then let (such an exists since by assumption has order at least 3);
if , then let ;
and if , then let .
In each case, after reduction becomes a reduced word with its first and last letter in . Finally, represents a nontrivial element of , and so does . This proves the claim.
The Ping-pong lemma for cyclic subgroupsedit
Let G be a group acting on a set X. Let a1, ...,ak be elements of G of infinite order, where k ≥ 2. Suppose there exist disjoint nonempty subsets
X1+, ..., Xk+ and X1–, ..., Xk–
of X with the following properties:
ai(X − Xi–) ⊆ Xi+ for i = 1, ..., k;
ai−1(X − Xi+) ⊆ Xi– for i = 1, ..., k.
Then the subgroup H = ⟨a1, ..., ak⟩ ≤ Ggenerated by a1, ..., ak is free with free basis {a1, ..., ak}.
Proofedit
This statement follows as a corollary of the version for general subgroups if we let Xi = Xi+ ∪ Xi− and let Hi = ⟨ai⟩.
Examplesedit
Special linear group exampleedit
One can use the ping-pong lemma to prove[1] that the subgroup H = ⟨A,B⟩ ≤ SL2(Z), generated by the matrices
Indeed, let H1 = ⟨A⟩ and H2 = ⟨B⟩ be cyclic subgroups of SL2(Z) generated by A and B accordingly. It is not hard to check that A and B are elements of infinite order in SL2(Z) and that
It is not hard to check, using the above explicit descriptions of H1 and H2, that for every nontrivial g ∈ H1 we have g(X2) ⊆ X1 and that for every nontrivial g ∈ H2 we have g(X1) ⊆ X2. Using the alternative form of the ping-pong lemma, for two subgroups, given above, we conclude that H = H1 ∗ H2. Since the groups H1 and H2 are infinite cyclic, it follows that H is a free group of rank two.
Word-hyperbolic group exampleedit
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 integersn ≥ M, m ≥ M the subgroup H = ⟨gn, hm⟩ ≤ 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 neighborhoodsU+, 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:
gn(∂G – U–) ⊆ U+
g−n(∂G – U+) ⊆ U–
hm(∂G – V–) ⊆ V+
h−m(∂G – V+) ⊆ V–
The ping-pong lemma now implies that H = ⟨gn, hm⟩ ≤ G is free of rank two.
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]
Referencesedit
^ abcdPierre 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.
^ abJ. Tits. Free subgroups in linear groups.Journal of Algebra, vol. 20 (1972), pp. 250–270
^ abRoger 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
^ abM. 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.
^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
^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 GL2. 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