Ping-pong lemma

Ping-pong lemma

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

History

The ping-pong argument goes back to late 19th century and is commonly attributed 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 containg the proof of a famous result now known as the Tits alternative.J. Tits. "Free subgroups in linear groups." Journal of Algebra, vol. 20 (1972), pp. 250–270 ] 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&SchuppRoger C. Lyndon and Paul E. Schupp. "Combinatorial Group Theory." Springer-Verlag, New York, 2001. "Classics in Mathematics" series, reprint of the 1977 edition. ISBN-13: 9783540411581; Ch II, Section 12, pp. 167–169] , de la HarpePierre de la Harpe. [http://books.google.com/books?id=cRT01C5ADroC&pg=PA25&dq=ping+pong+lemma+group+theory&sig=_1EZ9oSfAdljZFH1g7uvFiHuI-w#PPA25,M1 "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.] , Bridson&HaefligerMartin 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] and others.

Formal statement

Let "G" be a group acting on a set "X". Let "a"1,...,"a""k" be elements of "G", where "k" ≥ 1. 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"–) ⊆ "X""i"+ for "i" = 1, ..., "k";

*"a""i"−1("X" − "X""i"+) ⊆ "X""i"– for "i" = 1, ..., "k".

Then the subgroup "H" = <"a"1, ..., "a""k"> ≤ "G" generated by "a"1, ..., "a""k" is free with free basis {"a"1, ..., "a""k"}.

Proof

To simplify the argument, we will prove the statement under the following mild additional assumption:
*X e igcup_{i=1}^k (X_i^+cup X_i^-).The argument for the general case is similar to the one given below but requires more careful analysis.

Choose a point "x" in "X" such that

:x otin igcup_{i=1}^k (X_i^+cup X_i^-).

To show that "H" is free with free basis "a"1,...,"a""k" it suffices to prove that every nontrivial freely reduced word in the alphabet

: "A" = {"a"1, ..., "a""k", "a"1−1, ..., "a""k"−1}

represents a nontrivial element of "G".

Let "w" be such a freely reduced word, that is, "w" = "b""n""b""n"−1..."b"1, where "n" ≥ 1, where each "bj" belongs to "A" and where "w" does not contain subwords of the form "a""i""a""i"−1 or "a""i"−1"a""i".

Induction on "j" shows that for every "j" = 1, ..., "n" we have

:b_jdots b_2b_1 xin igcup_{i=1}^k (X_i^+cup X_i^-).

Thus

:wxin igcup_{i=1}^k (X_i^+cup X_i^-).

Therefore "wx" ≠ "x" and hence "w" ≠ 1 in "G", as required.

The name "ping-pong lemma" is motivated by the fact that, in the above argument, the point "b""j""b""j"−1..."b"1"x" bounces like a ping-pong between the sets "X"1+, ..., "X""k"+, "X"1&ndash;,...,"X""k"&ndash; as "j" varies over "j" = 1, ..., "n".

Ping-pong lemma for several subgroups

There is also a version of the ping-pong lemma which ensures that several subgroups of a group acting on a set generate a free product.


=A version for two subgroups=

Let "G" be a group acting on a set "X" and let "H"1, "H"2 be two subgroups of "G" such that |"H"1| ≥ 3 and |"H"2| ≥ 2. Suppose there exist two non-empty subsets "X"1 and "X"2 of "X" such that the following hold:

*"X"1 is not contained in "X"2;
*for every "h"1 ∈ "H"1, "h"1 ≠ 1 we have "h"1("X"2) ⊆ "X"1;
*for every "h"2 ∈ "H"2, "h"2 ≠ 1 we have "h"2("X"1) ⊆ "X"2.

Then the subgroup "H"=<"H"1, "H"2>≤"G" of "G" generated by "H"1 and "H"2 is equal to the free product of "H"1 and "H"2::"H" = "H"1∗"H"2.

A version for an arbitrary finite number of subgroups

The following version of the ping-pong lemma for several subgroups appears in [Andrij Olijnyk and Vitaly Suchchansky. [http://www.worldscinet.com/cgi-bin/details.cgi?id=pii:S0218196704001931&type=html Representations of free products by infinite unitriangular matrices over finite fields.] International Journal of Algebra and Computation. Vol. 14 (2004), no. 5&ndash;6, pp. 741&ndash;749; Lemma 2.1] .

Let "G" be a group acting on a set "X" and let "H"1, "H"2,...., "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 disjoint nonempty subsets "X"1, "X"2,....,"X""k" of "X" such that the following holds:

*For any "i"≠"j" and for any "h"∈"H""i", "h"≠1 we have "h"("X""j")⊆"X""i".

Then:langle H_1,dots, H_k angle=H_1astdots ast H_k.

Examples

Special linear group example

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

:scriptstyle A=egin{pmatrix}1 & 2\ 0 &1 end{pmatrix} and scriptstyle B=egin{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|nin mathbb Z}={egin{pmatrix}1 & 2n\ 0 & 1 end{pmatrix} : ninmathbb Z}

and

:H_2={B^n|nin mathbb Z}={egin{pmatrix}1 & 0\ 2n & 1 end{pmatrix} : ninmathbb Z}.

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

:X_1={egin{pmatrix}x \ y end{pmatrix}in mathbb R^2 : |x|>|y|}

and

:X_2={egin{pmatrix}x \ y end{pmatrix}in mathbb R^2 : |x|<|y|}.

It is not hard to check, using the above explicitly descriptions of "H"1 and "H"2 that for every nontrivial "g" ∈ "H"1 we have "g"("X"2) ⊆ "X"1 and that for every nontrivial "g" ∈ "H"2 we have "g"("X"1) ⊆ "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 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""n", "h""m"> ≤ "G" is free of rank two.


=Sketch of the proofM. Gromov. "Hyperbolic groups." Essays in group theory, pp. 75&ndash;263,Mathematical Sciiences Research Institute Publications, 8, Springer, New York, 1987; ISBN: 0-387-96618-8; Ch. 8.2, pp. 211&ndash;219.] =

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"&ndash;, "V"+ and "V"&ndash; 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""n"(∂"G" &ndash; "U"&ndash;) ⊆ "U"+
*"g"−"n"(∂"G" &ndash; "U"+) ⊆ "U"&ndash;
*"h""m"(∂"G" &ndash; "V"&ndash;) ⊆ "V"+
*"h"−"m"(∂"G" &ndash; "V"+) ⊆ "V"&ndash;

The ping-pong lemma now implies that "H" = <"g""n", "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 Shottki 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 Schottki-type arguments are widely used in geometric group theory, particularly for subgroups of word-hyperbolic groups and for automorphism groups of trees. [Alexander Lubotzky. "Lattices in rank one Lie groups over local fields." Geometric and Functional Analysis, vol. 1 (1991), no. 4, pp. 406&ndash;431 ]
*ping-pong lemma is also used for studying Schottki-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 Teichmuller space. [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&ndash;141,Contemporary Mathematics series, 432, American Mathematical Society, Providence, RI, 2007; ISBN: 978-0-8218-4227-0; 0-8218-4227-7] A similar argument is also utilized in the study of subgroups of the outer automorphism group of a free group. [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&ndash;244. ]
*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. (see also [Pierre de la Harpe. "Free groups in linear groups." L'Enseignement Mathématique (2), vol. 29 (1983), no. 1-2, pp. 129&ndash;144 ] 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. These generalizations are used, in particular, in the proof of Maskit's Combination Theorem for Kleinian groups [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&ndash;156 and pp. 160&ndash;167] .
*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 setPierre de la Harpe. [http://books.google.com/books?id=cRT01C5ADroC&pg=PA188&vq=semi-group&dq=ping+pong+lemma+group+theory&source=gbs_search_s&sig=ACfU3U2oMEeKTE_pB7Gt_MqNjOaUNZL8yw "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&ndash;188. ] , and for specific types of actions, e.g. in the context of linear groups [Alex Eskin, Shahar Mozes and Hee Oh. [http://www.springerlink.com/content/3ybuud1bpkkkcxn0/ On uniform exponential growth for linear groups.] Inventiones Mathematicae. vol. 60 (2005), no. 1, pp.1432&ndash;1297; Lemma 2.2] , groups acting on trees [Roger C. Alperin and Guennadi A. Noskov. [http://books.google.com/books?id=w7LO6AkB8Y8C&pg=PA2&lpg=PA2&dq=%22ping-pong+lemma%22+semigroup&source=web&ots=aBPNu6adQ2&sig=7mZjESpp-6Bkekw68RCPEDYJSTM&hl=en&sa=X&oi=book_result&resnum=4&ct=result#PPA2,M1 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-13: 9780821831588; page 2, Lemma 3.1] and others. [Yves de Cornulier and Romain Tessera. [http://msp.warwick.ac.uk/gt/2008/12-01/p011.xhtml Quasi-isometrically embedded free sub-semigroups.] Geometry & Topology, vol. 12 (2008), pp. 461&ndash;473; Lemma 2.1]

References

ee also

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Geometric group theory — is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act (that is, when the… …   Wikipedia

  • Vietnam — Socialist Republic of Vietnam Cộng hòa Xã hội chủ nghĩa Việt Nam …   Wikipedia

  • Hardware random number generator — This SSL Accelerator computer card uses a hardware random number generator to generate cryptographic keys to encrypt data sent over computer networks. In computing, a hardware random number generator is an apparatus that generates random numbers… …   Wikipedia

  • Pipapo — ist ein Wort (eine Triplikation) der Umgangssprache und wird hauptsächlich in Verbindungen wie „mit allem Pipapo“ in der Bedeutung „mit allem, was dazugehört“, „mit allem Drum und Dran“ als ein zusammenfassender Platzhalter verwendet, wenn man… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”