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 <math>H</math> is a subgroup of <math>G</math>, which is finitely generated with generating set <math>S</math>, that is, <math>G = \langle S\rangle</math>.

Let <math>R</math> be a right transversal of <math>H</math> in <math>G</math> with the neutral element <math>e</math> in <math>R</math>. In other words, let <math>R</math> be a set containing exactly one element from each right coset of <math>H</math> in <math>G</math>.

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

Then <math>H</math> is generated by the set

<math>\{rs(\overline{rs})^{-1}|r\in R, s\in S\}</math>.<ref name= Seress >Template:Cite book</ref><ref name= Johnson >Template:Cite book</ref>

Hence, in particular, Schreier's lemma implies that every subgroup of finite index of a finitely generated group is again finitely generated.<ref name= Holt >Template:Citation  Erratum: "|Z| Template:Font |X|·|U|" should read "|Z| Template:Font |X|·|U|"</ref>

Example

The group <math>\mathbb{Z}_3 = \mathbb{Z}\,/\,3 \mathbb{Z}</math> is cyclic. Via Cayley's theorem, <math>\mathbb{Z}_3</math> is isomorphic to a subgroup of the symmetric group <math>S_3</math>. Now,

<math>\mathbb{Z}_3 = \{ e, (1\ 2\ 3), (1\ 3\ 2) \}</math>

<math>S_3 = \{ e, (1\ 2), (1\ 3), (2\ 3), (1\ 2\ 3), (1\ 3\ 2) \}</math>

where <math>e</math> is the identity permutation. Note that <math>S_3</math> is generated by <math>S = \{ s_1 = (1\ 2),\, s_2 = (1\ 2\ 3) \}</math>.

<math>\mathbb{Z}_3</math> has just two right cosets in <math>S_3</math>, namely <math>\mathbb{Z}_3</math> and <math>S_3 \setminus \mathbb{Z}_3 = \{ (1\ 2), (1\ 3), (2\ 3)\}</math>, so we select the right transversal <math>R = \{ r_1 = e,\, r_2 = (1\ 2) \}</math>, and we have

<math>\begin{align}

r_1s_1 &= (1\ 2), & \text{so} && \overline{r_1s_1} &= (1\ 2) \\ r_1s_2 &= (1\ 2\ 3), & \text{so} && \overline{r_1s_2} &= e \\ r_2s_1 &= e , & \text{so} && \overline{r_2s_1} &= e \\ r_2s_2 &= (2\ 3), & \text{so} && \overline{r_2s_2} &= (1\ 2). \\ \end{align}</math>

Finally,

<math>r_1s_1\left(\overline{r_1s_1}\right)^{-1} = e</math>

<math>r_1s_2\left(\overline{r_1s_2}\right)^{-1} = (1\ 2\ 3)</math>

<math>r_2s_1\left(\overline{r_2s_1}\right)^{-1} = e</math>

<math>r_2s_2\left(\overline{r_2s_2}\right)^{-1} = (1\ 2\ 3).</math>

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