Kalpana Kalpana (Editor)

Schreier's lemma

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Definition

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 . In other words, R is (the image of) a section of the quotient map G → H ∖ G , where H ∖ G denotes the set of right cosets of H in G .

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

g ∈ H g ¯ .

Then H is generated by the set

{ r s ( r s ¯ ) − 1 | r ∈ R , s ∈ S }

Example

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

Z 3 = { e , ( 1   2   3 ) , ( 1   3   2 ) } S 3 = { e , ( 1   2 ) , ( 1   3 ) , ( 2   3 ) , ( 1   2   3 ) , ( 1   3   2 ) }

where e 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

t 1 s 1 = ( 1   2 ) , so t 1 s 1 ¯ = ( 1   2 ) t 1 s 2 = ( 1   2   3 ) , so t 1 s 2 ¯ = e t 2 s 1 = e , so t 2 s 1 ¯ = e t 2 s 2 = ( 2   3 ) , so t 2 s 2 ¯ = ( 1   2 ) .

Finally,

t 1 s 1 t 1 s 1 ¯ − 1 = e t 1 s 2 t 1 s 2 ¯ − 1 = ( 1   2   3 ) t 2 s 1 t 2 s 1 ¯ − 1 = e t 2 s 2 t 2 s 2 ¯ − 1 = ( 1   2   3 ) .

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

References

Schreier's lemma Wikipedia
(Text) CC BY-SA