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 $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, let $R$ be a set containing exactly one element from each right coset of $H$ in $G$.

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

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

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

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

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

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

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

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

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

References

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