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

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

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

${\displaystyle g\in H{\overline {g}}.}$

Then ${\displaystyle H}$ is generated by the set

${\displaystyle \{rs({\overline {rs}})^{-1}|r\in R,s\in 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,

${\displaystyle \mathbb {Z} _{3}=\{e,(1\ 2\ 3),(1\ 3\ 2)\}}$

${\displaystyle S_{3}=\{e,(1\ 2),(1\ 3),(2\ 3),(1\ 2\ 3),(1\ 3\ 2)\}}$

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

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

${\displaystyle {\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,

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

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

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

${\displaystyle 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 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.