ping-pong lemma


Theorem (Ping Pong Lemma).

Let k2 and let G be a group acting on a space X. Suppose we are given a class M={A1,A2,,Ak,B1,B2,,Bk} of 2k pairwise disjoint subsets of X and suppose y1,y2,,yk are elements of G such that

Bicyi(Ai)i=1,2,,k

(Bic is the complement of Bi in X). Then, the subgroupMathworldPlanetmathPlanetmath of G generated by y1,y2,,yk is free.

Before turning to prove the lemma let’s state three simple facts:

Fact 1.

For all i=1,,k we have yi(Aic)Bi and yi-1(Bic)Ai

Proof.

Bicyi(Ai)Biyi(Ai)c=yi(Aic)

Fact 2.

If ij then AjBjAicBic.

Proof.

Ai and Aj are disjoint therefore AjAic. Similarly, AjBic so AjAicBic. In the same way, BjAicBic so AjBjAicBic. ∎

Fact 3.

If R,SM then RcS

Proof.

Assume by contradictionMathworldPlanetmathPlanetmath that RcS. Then, X=RS and therefore any element of M intersects with either R or S. However, the elements of M are pairwise disjoint and there are at least 4 elements in M so this is a contradiction. ∎


Using the above 3 facts, we now turn to the proof of the Ping Pong Lemma:

Proof.

Suppose we are given w=znϵnz2ϵ2z1ϵ1 such that z{y1,y2,,yk} and ϵ{-1,+1}. and suppose further that w is freely reduced, namely, if zi=zi+1 then ϵi=ϵi+1. We want to show that w1 in G. Assume by contradiction that w=1. We get a contradiction by giving R,S such that w(Sc)R and therefore contradicting Fact 3 above since Sc=w(Sc)R.

The set S is chosen as follows. Assume that z1=yi then:

S={Aiif ϵ1=1Biif ϵ1=-1

Define the following subsets P0,P1,,Pn of X:

P0=Sc;P1=z1ϵ1(P0),,Pn=znϵn(Pn-1)=w(Sc)

To completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof we show by inductionMathworldPlanetmath that for =1,2,,n if z=yi then:

  1. 1.

    if ϵ=1 then PBi.

  2. 2.

    if ϵ=-1 then PAi.

For =1 the above follows from Fact 1 and the specific choice of P0. Assume it is true for -1 and assume that z=yi. We have two cases to check:

  1. 1.

    z-1z: by the induction hypothesis P-1 is a subset of AjBj for some ji. Therefore, by Fact 2 we get that P-1 is a subset of AicBic. Consequently, we get the following:

    P=zϵ(P-1)=yiϵ(P-1)yiϵ(AicBic)

    Hence, if ϵ=1 then:

    Pyi(AicBic)yi(Aic)Bi

    And if ϵ=-1 then:

    Pyi-1(AicBic)yi-1(Bic)Ai
  2. 2.

    z-1=z: by the fact that w is freely reduced we get an equality between ϵ-1 and ϵ. Hence, if ϵ=1 then P-1BiAic and therefore:

    P=zϵ(P-1)=yi(P-1)yi(Aic)Bi

    Similiarly, if ϵ=-1 then P-1AiBic and therefore:

    P=zϵ(P-1)=yi-1(P-1)yi-1(Bic)Ai

Title ping-pong lemma
Canonical name PingpongLemma
Date of creation 2013-03-22 17:11:21
Last modified on 2013-03-22 17:11:21
Owner uriw (288)
Last modified by uriw (288)
Numerical id 8
Author uriw (288)
Entry type TheoremMathworldPlanetmath
Classification msc 20F65
Synonym table-tennis lemma