Schreier's lemma

In group theory, Schreier's lemma is a theorem 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, ${\displaystyle G=\langle S\rangle }$.

Let ${\displaystyle R}$ be a right transversal of ${\displaystyle H}$ in ${\displaystyle G}$ with the neutral element ${\displaystyle e}$ in ${\displaystyle R}$. In other words, let ${\displaystyle R}$ be a set containing exactly one element from each right coset of ${\displaystyle H}$ in ${\displaystyle G}$.

For each ${\displaystyle g\in G}$, we define ${\displaystyle {\overline {g}}}$ as the chosen representative of the coset ${\displaystyle Hg}$ in the transversal ${\displaystyle R}$.

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

${\displaystyle \{rs({\overline {rs}})^{-1}|r\in R,s\in S\}}$.^[1][2]

Hence, in particular, Schreier's lemma implies that every subgroup of finite index of a finitely generated group is again finitely generated.^[3]

Example

The group ${\displaystyle \mathbb {Z} _{3}=\mathbb {Z} \,/\,3\mathbb {Z} }$ is cyclic. Via Cayley's theorem, ${\displaystyle \mathbb {Z} _{3}}$ is isomorphic to a subgroup of the symmetric group ${\displaystyle S_{3}}$. 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 that ${\displaystyle S_{3}}$ is generated by ${\displaystyle S=\{s_{1}=(1\ 2),\,s_{2}=(1\ 2\ 3)\}}$.

${\displaystyle \mathbb {Z} _{3}}$ has just two right cosets in ${\displaystyle S_{3}}$, namely ${\displaystyle \mathbb {Z} _{3}}$ and ${\displaystyle S_{3}\setminus \mathbb {Z} _{3}=\{(1\ 2),(1\ 3),(2\ 3)\}}$, so we select the right transversal ${\displaystyle R=\{r_{1}=e,\,r_{2}=(1\ 2)\}}$, and we have

${\displaystyle {\begin{aligned}r_{1}s_{1}&=(1\ 2),&{\text{so}}&&{\overline {r_{1}s_{1}}}&=(1\ 2)\\r_{1}s_{2}&=(1\ 2\ 3),&{\text{so}}&&{\overline {r_{1}s_{2}}}&=e\\r_{2}s_{1}&=e,&{\text{so}}&&{\overline {r_{2}s_{1}}}&=e\\r_{2}s_{2}&=(2\ 3),&{\text{so}}&&{\overline {r_{2}s_{2}}}&=(1\ 2).\\\end{aligned}}}$

Finally,

${\displaystyle r_{1}s_{1}\left({\overline {r_{1}s_{1}}}\right)^{-1}=e}$

${\displaystyle r_{1}s_{2}\left({\overline {r_{1}s_{2}}}\right)^{-1}=(1\ 2\ 3)}$

${\displaystyle r_{2}s_{1}\left({\overline {r_{2}s_{1}}}\right)^{-1}=e}$

${\displaystyle r_{2}s_{2}\left({\overline {r_{2}s_{2}}}\right)^{-1}=(1\ 2\ 3).}$

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