In mathematics, Schreier's lemma is a theorem in group theory used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup.

Statement

edit

Suppose   is a subgroup of  , which is finitely generated with generating set  , that is,  .

Let   be a right transversal of   in  . In other words,   is (the image of) a section of the quotient map  , where   denotes the set of right cosets of   in  .

The definition is made given that  ,   is the chosen representative in the transversal   of the coset  , that is,

 

Then   is generated by the set

 

Hence, in particular, Schreier's lemma implies that every subgroup of finite index of a finitely generated group is again finitely generated.

Example

edit

The group Z3 = Z/3Z is cyclic. Via Cayley's theorem, Z3 is a subgroup of the symmetric group S3. Now,

 
 

where   is the identity permutation. Note S3 =  { s1=(1 2), s2 = (1 2 3) } .

Z3 has just two cosets, Z3 and S3 \ Z3, so we select the transversal { t1 = e, t2=(1 2) }, and we have

 

Finally,

 
 
 
 

Thus, by Schreier's subgroup lemma, { e, (1 2 3) } generates Z3, but having the identity in the generating set is redundant, so it can be removed to obtain another generating set for Z3, { (1 2 3) } (as expected).

References

edit
  • Seress, A. Permutation Group Algorithms. Cambridge University Press, 2002.