Ping-pong lemma

Last updated March 21, 2023

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

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 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 1, X 2, ..., X k$ of $X$ such that the following holds:

For any $i \neq s$ and for any $h$ in $H i$ , $h \neq 1$ we have $h (X s) \subseteq 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 (nonempty) reduced word represents a nontrivial element of $G$ . Let $w$ be such a word of length $m\geq 2$ , and let

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 $\alpha _{i}\neq \alpha _{i+1}$ for any $i=1,\dots ,m-1$ and each $w_{i}$ is distinct from the identity element of $H_{\alpha _{i}}$ . We then let $w$ act on an element of one of the sets ${\textstyle X_{i}}$ . As we assume that at least one subgroup $H_{i}$ has order at least 3, without loss of generality we may assume that $H_{1}$ has order at least 3. We first make the assumption that $\alpha _{1}$ and $\alpha _{m}$ are both 1 (which implies $m\geq 3$ ). From here we consider $w$ acting on $X_{2}$ . We get the following chain of containments:

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 $X_{i}$ 's are disjoint, we conclude that $w$ acts nontrivially on some element of $X_{2}$ , thus $w$ represents a nontrivial element of $G$ .

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

In each case, $hwh^{-1}$ after reduction becomes a reduced word with its first and last letter in $H_{1}$ . Finally, $hwh^{-1}$ represents a nontrivial element of $G$ , and so does $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 of infinite order, where k ≥ 2. Suppose there exist disjoint nonempty subsets

X 1 +, ..., X k + and X 1 -, ..., X k -

of $X$ with the following properties:

$a i (X - X i -) \subseteq X i +$ for $i = 1, ..., k$ ;
$a i -1 (X - X i +) \subseteq X i -$ for $i = 1, ..., k$ .

Then the subgroup $H = ⟨ a 1, ..., a k ⟩ \leq G$ generated by a₁, ..., a_k is free with free basis ${a 1, ..., a k}$ .

Proof

This statement follows as a corollary of the version for general subgroups if we let $X i = X i + \cup 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 ⟩ \leq SL 2 (Z)$ , generated by the matrices

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

and

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

is free of rank two.

Proof

Indeed, let $H 1 = ⟨ A ⟩$ and $H 2 = ⟨ 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}\mid n\in \mathbb {Z} \}=\left\{{\begin{pmatrix}1&2n\\0&1\end{pmatrix}}:n\in \mathbb {Z} \right\}

and

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 2 (Z)$ on $R 2$ 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 explicit descriptions of H₁ and H₂, that for every nontrivial $g \in H 1$ we have $g (X 2) \subseteq X 1$ and that for every nontrivial $g \in H 2$ we have $g (X 1) \subseteq X 2$ . Using the alternative form of the ping-pong lemma, for two subgroups, given above, we conclude that $H = H 1 * H 2$ . Since the groups $H 1$ and $H 2$ 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 nonidentity elements of finite order. Let $g, h \in G$ be two non-commuting elements, that is such that $gh \neq hg$ . Then there exists M ≥ 1 such that for any integers $n \geq M$ , $m \geq M$ the subgroup $H = ⟨ g n, h m ⟩ \leq 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 in G is a nonidentity element then a has exactly two distinct fixed points, $a \infty$ and $a -\infty$ in $\partial G$ and that $a \infty$ is an attracting fixed point while $a -\infty$ is a repelling fixed point.

Since $g$ and $h$ do not commute, basic facts about word-hyperbolic groups imply that $g \infty$ , $g -\infty$ , $h \infty$ and $h -\infty$ are four distinct points in $\partial G$ . Take disjoint neighborhoods $U +$ , $U -$ , $V +$ , and $V -$ of $g \infty$ , $g -\infty$ , $h \infty$ and $h -\infty$ in $\partial G$ respectively. Then the attracting/repelling properties of the fixed points of g and h imply that there exists $M \geq 1$ such that for any integers $n \geq M$ , $m \geq M$ we have:

$g n (\partial G - U -) \subseteq U +$
$g - n (\partial G - U +) \subseteq U -$
$h m (\partial G - V -) \subseteq V +$
$h - m (\partial G - V +) \subseteq V -$

The ping-pong lemma now implies that $H = ⟨ g n, h m ⟩ \leq 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]
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]

Related Research Articles

In mathematics, the indefinite orthogonal group, O(p, q) is the Lie group of all linear transformations of an n-dimensional real vector space that leave invariant a nondegenerate, symmetric bilinear form of signature (p, q), where n = p + q. It is also called the pseudo-orthogonal group or generalized orthogonal group. The dimension of the group is n(n − 1)/2.

In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form

In mathematics, the modular group is the projective special linear group $of 2 × 2 matrices with integer coefficients and determinant 1. The matrices A and −A are identified. The modular group acts on the upper-half of the complex plane by fractional linear transformations, and the name "modular group" comes from the relation to moduli spaces and not from modular arithmetic.$

In mathematics, a Fuchsian group is a discrete subgroup of PSL(2,R). The group PSL(2,R) can be regarded equivalently as a group of isometries of the hyperbolic plane, or conformal transformations of the unit disc, or conformal transformations of the upper half plane, so a Fuchsian group can be regarded as a group acting on any of these spaces. There are some variations of the definition: sometimes the Fuchsian group is assumed to be finitely generated, sometimes it is allowed to be a subgroup of PGL(2,R), and sometimes it is allowed to be a Kleinian group which is conjugate to a subgroup of PSL(2,R).

In mathematics, a Kleinian group is a discrete subgroup of the group of orientation-preserving isometries of hyperbolic 3-space $H 3$ . The latter, identifiable with $PSL(2, C)$ , is the quotient group of the 2 by 2 complex matrices of determinant 1 by their center, which consists of the identity matrix and its product by $-1$ . $PSL(2, C)$ has a natural representation as orientation-preserving conformal transformations of the Riemann sphere, and as orientation-preserving conformal transformations of the open unit ball $B 3$ in $R 3$ . The group of Möbius transformations is also related as the non-orientation-preserving isometry group of $H 3$ , $PGL(2, C)$ . So, a Kleinian group can be regarded as a discrete subgroup acting on one of these spaces.

In mathematics, the HNN extension is an important construction of combinatorial group theory.

In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a word hyperbolic group or Gromov hyperbolic group, is a finitely generated group equipped with a word metric satisfying certain properties abstracted from classical hyperbolic geometry. The notion of a hyperbolic group was introduced and developed by Mikhail Gromov (1987). The inspiration came from various existing mathematical theories: hyperbolic geometry but also low-dimensional topology, and combinatorial group theory. In a very influential chapter from 1987, Gromov proposed a wide-ranging research program. Ideas and foundational material in the theory of hyperbolic groups also stem from the work of George Mostow, William Thurston, James W. Cannon, Eliyahu Rips, and many others.

<span class="mw-page-title-main">Hermitian symmetric space</span> Manifold with inversion symmetry

In mathematics, a Hermitian symmetric space is a Hermitian manifold which at every point has an inversion symmetry preserving the Hermitian structure. First studied by Élie Cartan, they form a natural generalization of the notion of Riemannian symmetric space from real manifolds to complex manifolds.

<span class="mw-page-title-main">Hyperboloid model</span> Model of n-dimensional hyperbolic geometry

In geometry, the hyperboloid model, also known as the Minkowski model after Hermann Minkowski, is a model of n-dimensional hyperbolic geometry in which points are represented by points on the forward sheet S⁺ of a two-sheeted hyperboloid in (n+1)-dimensional Minkowski space or by the displacement vectors from the origin to those points, and m-planes are represented by the intersections of (m+1)-planes passing through the origin in Minkowski space with S⁺ or by wedge products of m vectors. Hyperbolic space is embedded isometrically in Minkowski space; that is, the hyperbolic distance function is inherited from Minkowski space, analogous to the way spherical distance is inherited from Euclidean distance when the n-sphere is embedded in (n+1)-dimensional Euclidean space.

In mathematics, the Weyl character formula in representation theory describes the characters of irreducible representations of compact Lie groups in terms of their highest weights. It was proved by Hermann Weyl. There is a closely related formula for the character of an irreducible representation of a semisimple Lie algebra. In Weyl's approach to the representation theory of connected compact Lie groups, the proof of the character formula is a key step in proving that every dominant integral element actually arises as the highest weight of some irreducible representation. Important consequences of the character formula are the Weyl dimension formula and the Kostant multiplicity formula.

In mathematics, the Tits alternative, named for Jacques Tits, is an important theorem about the structure of finitely generated linear groups.

In mathematics, a group is called boundedly generated if it can be expressed as a finite product of cyclic subgroups. The property of bounded generation is also closely related with the congruence subgroup problem.

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.

In the mathematical subject of group theory, the rank of a groupG, denoted rank(G), can refer to the smallest cardinality of a generating set for G, that is

In the mathematical subject of group theory, the Stallings theorem about ends of groups states that a finitely generated group $has more than one end if and only if the group admits a nontrivial decomposition as an amalgamated free product or an HNN extension over a finite subgroup. In the modern language of Bass-Serre theory the theorem says that a finitely generated group has more than one end if and only if admits a nontrivial action on a simplicial tree with finite edge-stabilizers and without edge-inversions.$

In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm. Small cancellation methods are also used for constructing Tarski monsters, and for solutions of Burnside's problem.

In mathematics, and more precisely in topology, the mapping class group of a surface, sometimes called the modular group or Teichmüller modular group, is the group of homeomorphisms of the surface viewed up to continuous deformation. It is of fundamental importance for the study of 3-manifolds via their embedded surfaces and is also studied in algebraic geometry in relation to moduli problems for curves.

In mathematics, the curve complex is a simplicial complex C(S) associated to a finite-type surface S, which encodes the combinatorics of simple closed curves on S. The curve complex turned out to be a fundamental tool in the study of the geometry of the Teichmüller space, of mapping class groups and of Kleinian groups. It was introduced by W.J.Harvey in 1978.

In mathematics, a convergence group or a discrete convergence group is a group $acting by homeomorphisms on a compact metrizable space in a way that generalizes the properties of the action of Kleinian group by Möbius transformations on the ideal boundary of the hyperbolic 3-space . The notion of a convergence group was introduced by Gehring and Martin (1987) and has since found wide applications in geometric topology, quasiconformal analysis, and geometric group theory.$

In mathematics, a Cannon–Thurston map is any of a number of continuous group-equivariant maps between the boundaries of two hyperbolic metric spaces extending a discrete isometric actions of the group on those spaces.

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

Contents

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

Related Research Articles

References

See also

Ping-pong lemma

Contents

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

Related Research Articles

References

See also

Sketch of the proof^[6]