Schreier's lemma explained

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

Suppose

H is a subgroup of G , which is finitely generated with generating set S , that is, G = \langle S\rangle .

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 \to H\backslash G , where H\backslash G denotes the set of right cosets of H in G .

The definition is made given that

g\in G , \overline{g} is the chosen representative in the transversal R of the coset Hg , that is, g\in H\overline{g}.

Then

H is generated by the set\{rs(\overline{rs}) ^{-1} |r\in R, s\in S\}.

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

Example

The group Z₃ = Z/3Z is cyclic. Via Cayley's theorem, Z₃ is a subgroup of the symmetric group S₃. 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 S₃ = \scriptstyle\langle \scriptstyle\rangle .

Z₃ has just two cosets, Z₃ and S₃ \ Z₃, so we select the transversal, and we have

\begin{matrix} t _{1s} _{1} = ( 1 2 ),& so &\overline{t _{1s} _{1}} = ( 1 2 )\\ t _{1s} _{2} = ( 1 2 3 ) ,& so & \overline{t _{1s} _{2}} = e\\ t _{2s} _{1} = e ,& so & \overline{t _{2s} _{1}} = e\\ t _{2s} _{2} = ( 2 3 ) ,& so & \overline{t _{2s} _{2}} = ( 1 2 ). \\ \end{matrix}

Finally,

t _{1s} _{1\overline{t} _{1s} ^{-1} ^{1 }} = e t _{1s} _{2\overline{t} _{1s} ^{-1} ^{2 }} = ( 1 2 3 ) t _{2s} _{1\overline{t} _{2s} ^{-1} ^{1 }} = e t _{2s} _{2\overline{t} _{2s} ^{-1} ^{2 }} = ( 1 2 3 ).

Thus, by Schreier's subgroup lemma, generates Z₃, but having the identity in the generating set is redundant, so it can be removed to obtain another generating set for Z₃, (as expected).

References

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