Schreier's subgroup lemma

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$&isin;$G$, $overline\{g\}$ is the chosen representative in the transversal $R$ of the coset $Hg$, that is, :$gin\; Hoverline\{g\}$

Then $H$ is generated by the set:$\{rs(overline\{rs\})^\{-1\}|rin\; R,\; sin\; S\}$

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,: $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 "S"₃ = < { "s"₁=(1 2), "s"₂=(1 2 3) } >.

Calculating the cosets of Z₃ in "S"₃, we have: $(1\; 2)Bbb\{Z\}\_3\; =\; S\_3setminusBbb\{Z\}\_3\; =\; \{\; (1\; 2),\; (1\; 3),\; (2\; 3)\; \}$: $(1\; 3)Bbb\{Z\}\_3\; =\; S\_3setminusBbb\{Z\}\_3\; =\; \{\; (1\; 2),\; (1\; 3),\; (2\; 3)\; \}$: $(2\; 3)Bbb\{Z\}\_3\; =\; S\_3setminusBbb\{Z\}\_3\; =\; \{\; (1\; 2),\; (1\; 3),\; (2\; 3)\; \}$

: $eBbb\{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 { "t"₁="e", "t"₂=(1 2) }, and we have :

Finally, : $t\_1s\_1overline\{t\_1s\_1\}^\{-1\}\; =\; e$: $t\_1s\_2overline\{t\_1s\_2\}^\{-1\}\; =\; (1\; 3\; 2)$: $t\_2s\_1overline\{t\_2s\_1\}^\{-1\}\; =\; e$: $t\_2s\_2overline\{t\_2s\_2\}^\{-1\}\; =\; (1\; 3\; 2)$

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