# Schreier’s lemma

Let $G$ be a group, $H$ a subgroup   and $T$ transversal of $H$ in $G$. For every $g\in G$, we denote by $\bar{g}$ the unique element $t\in T$ such that $Hg=Ht$. We also insist that $1\in T$. Under these conditions we can state Schreier’s lemma.

###### Lemma 1 (Schreier).

Given a group $G=\langle S\rangle$, a subgroup $H$, and transversal $T$ for $G/H$, then the set

 $U=H\cap\{ts(\overline{ts})^{-1}~{}:~{}s\in S,t\in T\}$

generates $H$.

###### Proof.

 We show that $H$ is generated by $U\cup U^{-1}$. We already know $U$ is contained in $H$ and we know every element $h\in H$ is expressible as a word over $S$, as $S$ generates $G$. So $h=s_{1}\cdots s_{k}$ where $s_{i}\in S\cup S^{-1}$. Note that $h=1s_{1}\cdots s_{k}$ which is of the form $u_{1}\cdots u_{i}t_{i+1}s_{i+1}\cdots s_{k}$ for $u_{j}\in U\cup U^{-1}$, $t_{i+1}\in T$ and $s_{j}\in S\cup S^{-1}$, where $i=0$. We assume for induction that $h$ has this form for some $i$. Now we perform the sleight-of-hand.

 $\displaystyle h$ $\displaystyle=$ $\displaystyle u_{1}\cdots u_{i}t_{i+1}s_{i+1}\cdots s_{k}$ $\displaystyle=$ $\displaystyle u_{1}\cdots u_{i}t_{i+1}s_{i+1}(\overline{t_{i+1}s_{i+1}})^{-1}(% \overline{t_{i+1}s_{i+1}})s_{i+2}\cdots s_{k}$ $\displaystyle=$ $\displaystyle u_{1}\cdots u_{i}(t_{i+1}s_{i+1}(\overline{t_{i+1}s_{i+1}})^{-1}% )\overline{t_{i+1}s_{i+1}}s_{i+2}\cdots s_{k}$ $\displaystyle=$ $\displaystyle u_{1}\cdots u_{i}u_{i+1}t_{i+2}s_{i+2}\cdots s_{k}$

by letting $u_{i+1}=t_{i+1}s_{i+1}(\overline{t_{i+1}s_{i+1}})^{-1}$ which is in $U\cup U^{-1}$, and $t_{i+2}=\overline{t_{i+1}s_{i+1}}\in T$. At the end of the iteration we have replaced all the $s_{i}$’s with elements of $U\cup U^{-1}$ and the last element $t_{k}\in T$. However, $U$ lies in $H$ so the product $u_{1}\cdots u_{k}\in H$ and as $h\in H$ and $h=u_{1}\cdots u_{k}t_{k}$ we know $t_{k}\in H$. As $Ht_{k}=H$, and $t_{k}\in T$ we now use the fact that $1\in T$ to assert that $t_{k}=1$. So $h$ is a word in $U\cup U^{-1}$ and thus $U$ generates $H$. ∎

The lemma lead to an unexpected use in the 1970’s where it was rediscovered by various authors to solve certain problems in computational group theory. Sims used the result to find generators of the stabilizer  of a point in a permutation group  . This method could then be repeated to find generators for each stabilizer in a stabilizer chain of a base of the group. A naive approach can result in exponentially many generators, so Sims’ algorithm  additionally removes unnecessary generators along the way. This is now called the Schreier-Sims algorithm.

Independently a version of this algorithm was developed by Frust, Hopcroft, and Luks as a means to prove the polynomial-time complexity of various problems in finite group  theory and graph theory  . Many improvements followed including versions by Knuth, Jerum, and even a probabilistic nearly linear time method by Seress.

The lemma still finds use in non-finite groups as Schreier had intended. The associated algorithms have been repeatedly improved principally by the work of George Havas and Colin Ramsay.

## References

• 1 Seress, Ákos Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003.
Title Schreier’s lemma SchreiersLemma 2013-03-22 15:53:55 2013-03-22 15:53:55 Algeboy (12884) Algeboy (12884) 17 Algeboy (12884) Theorem msc 20K27 Schreier-Sims LiftsTransversals FindingTheOrderOfAGroup