Jump to content

Schreier's lemma

From Wikipedia, the free encyclopedia

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.