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, \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\}

[edit] 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,

\Bbb{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) } >.

Calculating the cosets of Z3 in S3, we have

(1\ 2)\Bbb{Z}_3 = S_3\setminus\Bbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3) \}
(1\ 3)\Bbb{Z}_3 = S_3\setminus\Bbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3) \}
(2\ 3)\Bbb{Z}_3 = S_3\setminus\Bbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3) \}
e\Bbb{Z}_3 = \Bbb{Z}_3
(1\ 2\ 3)\Bbb{Z}_3 = \Bbb{Z}_3
(1\ 3\ 2)\Bbb{Z}_3 = \Bbb{Z}_3

So, we can select a transversal { t1=e, t2=(1 2) }, and we have

\begin{matrix} t_1s_1 = (1\ 2),&\quad\mathrm{so}\quad&\overline{t_1s_1} = (1\ 2)\\ t_1s_2 = (1\ 2\ 3) ,&\quad\mathrm{so}\quad& \overline{t_1s_2} = e\\ t_2s_1 = e ,&\quad\mathrm{so}\quad& \overline{t_2s_1} = e\\ t_2s_2 = (2\ 3) ,&\quad\mathrm{so}\quad& \overline{t_2s_2} = (1\ 2) \\ \end{matrix}

Finally,

t_1s_1\overline{t_1s_1}^{-1} = e
t_1s_2\overline{t_1s_2}^{-1} = (1\ 3\ 2)
t_2s_1\overline{t_2s_1}^{-1} = e
t_2s_2\overline{t_2s_2}^{-1} = (1\ 3\ 2)

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

[edit] References

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