Schreier's subgroup lemma

From Wikipedia, the free encyclopedia

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

Suppose H is a subgroup of G, which is finitely generated with generating set S, that is, G = <S>. Let R be a right transversal of H in G.

We make the definition that given g∈G, is the chosen representative in the transversal R of the coset Hg, that is,

Then H is generated by the set

[edit] Example

Let us establish the evident fact that the group Z₃=Z/3Z is indeed cyclic. Via Cayley's theorem, Z₃ is a subgroup of the symmetric group S₃. Now,

where e is the identity permutation. Note S₃ = < { s₁=(1 2), s₂=(1 2 3) } >.

Z₃ has just two cosets, Z₃ and S₃ \ Z₃, so we select the transversal { t₁=e, t₂=(1 2) }, and we have

Finally,

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

[edit] References

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