Schreier's lemma

Template:Short description 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=⟨S⟩$.

Let $R$ be a right transversal of $H$ in $G$ with the neutral element $e$ in $R$. 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 $\bar{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{\mathbb{Z}}}_3=\mathbb{\mathbb{Z}}/3\mathbb{\mathbb{Z}}$ is cyclic. Via Cayley's theorem, ${\mathbb{\mathbb{Z}}}_3$ is isomorphic to a subgroup of the symmetric group $S_3$. Now,

${\mathbb{\mathbb{Z}}}_3=\{e,(123),(132)\}$

$S_3=\{e,(12),(13),(23),(123),(132)\}$

where $e$ is the identity permutation. Note that $S_3$ is generated by $S=\{s_1=(12),s_2=(123)\}$.

${\mathbb{\mathbb{Z}}}_3$ has just two right cosets in $S_3$, namely ${\mathbb{\mathbb{Z}}}_3$ and $S_3\setminus {\mathbb{\mathbb{Z}}}_3=\{(12),(13),(23)\}$, so we select the right transversal $R=\{r_1=e,r_2=(12)\}$, and we have

$\begin{array}{rlrlrl}{r}_1{s}_1& =(12),& \text{so}& & \overline{r_1{s}_1}& =(12)\\ r_1{s}_2& =(123),& \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& =(23),& \text{so}& & \overline{r_2{s}_2}& =(12).\\ \end{array}$

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}=(123)$

$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}=(123).$

Thus, by Schreier's lemma, $\{e,(123)\}$ generates ${\mathbb{\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{\mathbb{Z}}}_3$, $\{(123)\}$.