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 $\overline{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\mathrm{=}\mathrm{⟨}S\mathrm{⟩}$, a subgroup $H$, and transversal$T$ for $G\mathrm{/}H$, then the set

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

generates $H$.

Proof.

[1]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 asa word over $S$, as $S$ generates $G$. So $h=s_1\mathrm{\cdots }{s}_k$ where$s_i\in S\cup S^{-1}$. Note that $h=1s_1\mathrm{\cdots }{s}_k$ which is ofthe form $u_1\mathrm{\cdots }{u}_i{t}_{i+1}{s}_{i+1}\mathrm{\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 forinduction that $h$ has this form for some $i$. Now we perform thesleight-of-hand.

$h$$=$$u_1\mathrm{\cdots }{u}_i{t}_{i+1}{s}_{i+1}\mathrm{\cdots }{s}_k$

$=$$u_1\mathrm{\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}\mathrm{\cdots }{s}_k$

$=$$u_1\mathrm{\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}\mathrm{\cdots }{s}_k$

$=$$u_1\mathrm{\cdots }{u}_i{u}_{i+1}{t}_{i+2}{s}_{i+2}\mathrm{\cdots }{s}_k$

by letting $u_{i+1}=t_{i+1}{s}_{i+1}{(\overline{t_{i+1}{s}_{i+1}})}^{-1}$ which isin $U\cup U^{-1}$, and $t_{i+2}=\overline{t_{i+1}{s}_{i+1}}\in T$. At theend 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\mathrm{\cdots }{u}_k\in H$ and as $h\in H$ and $h=u_1\mathrm{\cdots }{u}_k{t}_k$we know $t_k\in H$. As $H{t}_k=H$, and $t_k\in T$ we now use the factthat $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 was discovered in the course of studying free groups as a way to produce generatorsfor a subgroup of a free group. The Reidemeister-Schreiertheorem strengthened this result to produce a presentation for $H$ given onefor $G$ and a transversal of $G/H$.

The lemma lead to an unexpected use in the 1970’s where it was rediscovered by various authorsto solve certain problems in computational group theory. Sims used the result to findgenerators of the stabilizer of a point in a permutation group. This method could then berepeated 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 additionallyremoves 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 toprove the polynomial-time complexity of various problems in finite group theory and graphtheory. Many improvements followed including versions by Knuth, Jerum, and even a probabilisticnearly linear time method by Seress.

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