example of Schreier’s Lemma

Let $G$ be a permutation group, that is, a subgroup of the symmetric group $Sym(\mathrm{\Omega })$ on the set $\mathrm{\Omega }$. Fix $\omega \in \mathrm{\Omega }$. Then

$$G_{\omega }=\{g\in G:{\omega }^g=\omega \}$$

is a subgroup of $G$, and furthermore, the orbit ${\omega }^G$ canonically parameterizes a transversal of $G/G_{\omega }$. That is, to every coset $G_{\omega }g$ there corresponds precisely one image ${\omega }^g$ and visa-versa. This leads to one of the most significant applications of Schreier’s lemma.

Example.Let $G=⟨s_1=(1,2,3,4),s_2=(1,3)⟩$, which is a copy of $D_8$ actings the symmetries of the four corners of a square. If we let $\omega =1$ then we know that the stabilizer $G_1$ has index 4 in $G$ and is therefore of order 2.

Geometrically it is not too difficult to understand that the stabilizer $G_1$ is the subgroup $⟨(2,4)⟩$; however, computers are not generally geometrically inclined, and so we use Schreier’s lemma to conclude the same in a completely computational method.

The orbit of $1$ is $\{1,2,3,4\}$ but in order to make use of Schreier’s lemma we encode the orbit together with a representative of $G$ which transports $1$ to the corresponding orbit element. For example:

$$1^G=\{1=1^1,2=1^{s_1},3=2^{s_1},4=3^{s_1}\}.$$

This translates to the following simple transversal

$$T=\{1,s_1,s_1^2,s_1^3\}.$$

Notice that we have used the generators of $G$ to create the orbit so that the transversal is created as words over the generators of $G$ as given. (This process is not unique in general, but always possible.)

So we now have the ingrediants of Schreier’s lemma so we use them to create a generating set for $H=G_1$. Here $U$ is the set:

$$U=\{1s_1{(\overline{1s_1})}^{-1},1s_2{(\overline{1s_2})}^{-1},s_1{s}_1{(\overline{s_1{s}_1})}^{-1},s_1{s}_2{(\overline{s_1{s}_2})}^{-1},s_1^2{s}_1{(\overline{s_1^2{s}_1})}^{-1},s_1^2{s}_2{(\overline{s_1^2{s}_2})}^{-1},s_1^3{s}_1{(\overline{s_1^3{s}_1})}^{-1},s_1^3{s}_2{(\overline{s_1^3{s}_2})}^{-1}\}.$$

We need to perform several multiplication to reduce this set of generators, forinstance, $1^{s_1^3{s}_2}=4^{s_2}=4$ so $\overline{s_1^3{s}_2}=s_1^3$ while$1^{s_1^2{s}_2}=3^{s_2}=1$ so $\overline{s_1^2{s}_2}=1$. Proceeding like thiswe find

$$U=\{1,s_2{s}_1^2,1,s_1{s}_2{s}_1^{-1},1,s_1^2{s}_2,1,s_1^3{s}_2{s}_1\}=\{1,s_2{s}_1^2,s_1{s}_2{s}_1^{-1},s_1^2{s}_2,s_1^3{s}_2{s}_1\}.$$

Remembering these words are permutations we further find the set reduces to

$$U=\{(),(2,4)\}.$$

Finally, we must intersect $U$ with $G_1$. At first glance this feels impossible as we do not yet know $G_1$; however, we do know that $g\in G_1$ if and only if $1^g=1$. So we test this for each element of $U$ and find thatindeed each element in this case lies in $G_1$. Therefore by Schreier’s lemma,

$$G_1=⟨(),(2,4)⟩.$$

This agrees with our graphical intuition.

Of course the value of Schreier’s lemma is for sets $\mathrm{\Omega }$ of hundreds and thousands of points, well beyond human intuition in most cases. Recursive applications of the result allow one to build a set of generators for an entire stabilizer sequence and thus reveal the order of a permutation group – without having to list all the elements which is an impossibly large task.

A naive recursion is not generally sufficient as the number of generators returned at each level grows multiplicatively. However, applying some suitible filters and organizing the process (the main insight of Sims) leads to a polynomial time algorithm for establishing generators of a stabilizer chain.