Schreier's lemma

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

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\mathrm{\setminus }G$, where $H\mathrm{\setminus }G$ denotes the set of right cosets of $H$ in $G$.

The definition is made given that $g\in G$, $\bar{g}$ is the chosen representative in the transversal $R$ of the coset $Hg$, that is,

$g\in H\bar{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,(123),(132)\}$

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

where $e$ is the identity permutation. Note S₃ = $⟨${ s₁=(1 2), s₂ = (1 2 3) }$⟩$.

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

$\begin{array}{ccc}{t}_1{s}_1=(12),& \text{so}& \overline{t_1{s}_1}=(12)\\ t_1{s}_2=(123),& \text{so}& \overline{t_1{s}_2}=e\\ t_2{s}_1=e,& \text{so}& \overline{t_2{s}_1}=e\\ t_2{s}_2=(23),& \text{so}& \overline{t_2{s}_2}=(12).\end{array}$

Finally,

$t_1{s}_1\stackrel{-1}{\overline{t_1{s}_1}}=e$

$t_1{s}_2\stackrel{-1}{\overline{t_1{s}_2}}=(123)$

$t_2{s}_1\stackrel{-1}{\overline{t_2{s}_1}}=e$

$t_2{s}_2\stackrel{-1}{\overline{t_2{s}_2}}=(123).$

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.