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 $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,

$\mathbb {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${ s₁=(1 2), s₂ = (1 2 3) }$\scriptstyle \rangle$.

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

${\begin{matrix}t_{1}s_{1}=(1\ 2),&\quad {\text{so}}\quad &{\overline {t_{1}s_{1}}}=(1\ 2)\\t_{1}s_{2}=(1\ 2\ 3),&\quad {\text{so}}\quad &{\overline {t_{1}s_{2}}}=e\\t_{2}s_{1}=e,&\quad {\text{so}}\quad &{\overline {t_{2}s_{1}}}=e\\t_{2}s_{2}=(2\ 3),&\quad {\text{so}}\quad &{\overline {t_{2}s_{2}}}=(1\ 2).\\\end{matrix}}$

Finally,

$t_{1}s_{1}{\overline {t_{1}s_{1}}}^{-1}=e$

$t_{1}s_{2}{\overline {t_{1}s_{2}}}^{-1}=(1\ 2\ 3)$

$t_{2}s_{1}{\overline {t_{2}s_{1}}}^{-1}=e$

$t_{2}s_{2}{\overline {t_{2}s_{2}}}^{-1}=(1\ 2\ 3).$

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

References

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