Schreier's lemma

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 [math]\displaystyle{ H }[/math] is a subgroup of [math]\displaystyle{ G }[/math], which is finitely generated with generating set [math]\displaystyle{ S }[/math], that is, G = [math]\displaystyle{ \scriptstyle \langle S\rangle }[/math].

Let [math]\displaystyle{ R }[/math] be a right transversal of [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math]. In other words, [math]\displaystyle{ R }[/math] is (the image of) a section of the quotient map [math]\displaystyle{ G \to H\backslash G }[/math], where [math]\displaystyle{ H\backslash G }[/math] denotes the set of right cosets of [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math].

We make the definition that given [math]\displaystyle{ g }[/math]∈[math]\displaystyle{ G }[/math], [math]\displaystyle{ \overline{g} }[/math] is the chosen representative in the transversal [math]\displaystyle{ R }[/math] of the coset [math]\displaystyle{ Hg }[/math], that is,

[math]\displaystyle{ g\in H\overline{g}. }[/math]

Then [math]\displaystyle{ H }[/math] is generated by the set

[math]\displaystyle{ \{rs(\overline{rs})^{-1}|r\in R, s\in S\} }[/math]

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,

[math]\displaystyle{ \mathbb{Z}_3=\{ e, (1\ 2\ 3), (1\ 3\ 2) \} }[/math]

[math]\displaystyle{ S_3= \{ e, (1\ 2), (1\ 3), (2\ 3), (1\ 2\ 3), (1\ 3\ 2) \} }[/math]

where [math]\displaystyle{ e }[/math] is the identity permutation. Note S₃ = [math]\displaystyle{ \scriptstyle\langle }[/math]{ s₁=(1 2), s₂ = (1 2 3) }[math]\displaystyle{ \scriptstyle\rangle }[/math].

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

[math]\displaystyle{ \begin{matrix} t_1s_1 = (1\ 2),&\quad\text{so}\quad&\overline{t_1s_1} = (1\ 2)\\ t_1s_2 = (1\ 2\ 3) ,&\quad\text{so}\quad& \overline{t_1s_2} = e\\ t_2s_1 = e ,&\quad\text{so}\quad& \overline{t_2s_1} = e\\ t_2s_2 = (2\ 3) ,&\quad\text{so}\quad& \overline{t_2s_2} = (1\ 2). \\ \end{matrix} }[/math]

Finally,

[math]\displaystyle{ t_1s_1\overline{t_1s_1}^{-1} = e }[/math]

[math]\displaystyle{ t_1s_2\overline{t_1s_2}^{-1} = (1\ 2\ 3) }[/math]

[math]\displaystyle{ t_2s_1\overline{t_2s_1}^{-1} = e }[/math]

[math]\displaystyle{ t_2s_2\overline{t_2s_2}^{-1} = (1\ 2\ 3). }[/math]

Thus, by Schreier's subgroup lemma, { e, (1 2 3) } 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 2 3) } (as expected).

References

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