Schreier's subgroup lemma

From Free net encyclopedia

---

Current revision

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 <math>H</math> is a subgroup of <math>G</math>, which is finitely generated with generating set <math>S</math>, that is, G = <S>. Let <math>R</math> be a right transversal of <math>H</math> in <math>G</math>.

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

<math>g\in H\overline{g}</math>

Then <math>H</math> is generated by the set

<math>\{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>\Bbb{Z}_3=\{ e, (1\ 2\ 3), (1\ 3\ 2) \}</math>

<math>S_3=\{ e, (1\ 2), (1\ 3), (2\ 3), (1\ 2\ 3), (1\ 3\ 2) \}</math>

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

Calculating the cosets of Z₃ in S₃, we have

<math>(1\ 2)\Bbb{Z}_3 = S_3\setminus\Bbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3) \}</math>

<math>(1\ 3)\Bbb{Z}_3 = S_3\setminus\Bbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3) \}</math>

<math>(2\ 3)\Bbb{Z}_3 = S_3\setminus\Bbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3) \}</math>

<math>e\Bbb{Z}_3 = \Bbb{Z}_3</math>

<math>(1\ 2\ 3)\Bbb{Z}_3 = \Bbb{Z}_3</math>

<math>(1\ 3\ 2)\Bbb{Z}_3 = \Bbb{Z}_3</math>

So, we can select a transversal { t₁=e, t₂=(1 2) }, and we have

<math>\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 = (1\ 3\ 2) ,&\quad\mathrm{so}\quad& \overline{t_2s_2} = (1\ 2) \\ \end{matrix}</math>

Finally,

<math>t_1s_1\overline{t_1s_1} = e</math>

<math>t_1s_2\overline{t_1s_2} = (1\ 3\ 2)</math>

<math>t_2s_1\overline{t_2s_1} = e </math>

<math>t_2s_2\overline{t_2s_2} = (1\ 3\ 2)</math>

Thus, by Schrier'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).

References

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