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$ with generating set $S$ , that is, $G=\langle S\rangle$ .

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

.^[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 $\mathbb {Z} _{3}=\mathbb {Z} \,/\,3\mathbb {Z}$ 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, Ákos (2002). "Bases and Strong Generating Sets, §4.2 The Schreier—Sims Algorithm". Permutation group algorithms. Cambridge Tracts in Mathematics. Vol. 152. New York: Cambridge University Press. p. 57.
↑ Johnson, David Lawrence (1980). "Free groups and free presentations, §2 The Nielsen–Schreier theorem". Topics in the Theory of Group Presentations. London Mathematical Society Lecture Note Series. Vol. 42. New York: Cambridge University Press. p. 13, Lemma 3.
↑ Holt, Derek (April 2013), Presentation of Groups (Notes by F. Bouyer) (PDF), The University of Warwick, p. 8, Corollary 3.8 Erratum: "|Z| = |X|·|U|" should read "|Z| ≤ |X|·|U|"

[Seress-1] Seress, Ákos (2002). "Bases and Strong Generating Sets, §4.2 The Schreier—Sims Algorithm". Permutation group algorithms. Cambridge Tracts in Mathematics. Vol. 152. New York: Cambridge University Press. p. 57.

[Johnson-2] Johnson, David Lawrence (1980). "Free groups and free presentations, §2 The Nielsen–Schreier theorem". Topics in the Theory of Group Presentations. London Mathematical Society Lecture Note Series. Vol. 42. New York: Cambridge University Press. p. 13, Lemma 3.

[Holt-3] Holt, Derek (April 2013), Presentation of Groups (Notes by F. Bouyer) (PDF), The University of Warwick, p. 8, Corollary 3.8 Erratum: "|Z| = |X|·|U|" should read "|Z| ≤ |X|·|U|"

[1]

[2]

[3]