Misplaced Pages

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2023) (Learn how and when to remove this message)

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, ${\displaystyle G=\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}$.

The definition is made given that ${\displaystyle g\in 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\}.}$

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,

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

• Lemmas in group theory