example of Schreier’s Lemma

Let G be a permutation groupMathworldPlanetmath, that is, a subgroupMathworldPlanetmathPlanetmath of the symmetric groupMathworldPlanetmathPlanetmath Sym(Ω) on the set Ω. Fix ωΩ. Then


is a subgroup of G, and furthermore, the orbit ωG canonically parameterizes a transversalPlanetmathPlanetmath of G/Gω. That is, to every coset Gωg there corresponds precisely one image ωg and visa-versa. This leads to one of the most significant applications of Schreier’s lemma.

Example. Let G=s1=(1,2,3,4),s2=(1,3), which is a copy of D8 actings the symmetriesMathworldPlanetmathPlanetmathPlanetmath of the four corners of a square. If we let ω=1 then we know that the stabilizerMathworldPlanetmath G1 has index 4 in G and is therefore of order 2.

Geometrically it is not too difficult to understand that the stabilizer G1 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:


This translates to the following simple transversal


Notice that we have used the generatorsPlanetmathPlanetmathPlanetmath 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=G1. Here U is the set:


We need to perform several multiplicationPlanetmathPlanetmath to reduce this set of generators, for instance, 1s13s2=4s2=4 so s13s2¯=s13 while 1s12s2=3s2=1 so s12s2¯=1. Proceeding like this we find


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


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


This agrees with our graphical intuition.

Of course the value of Schreier’s lemma is for sets Ω 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 sequenceMathworldPlanetmath 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 timeMathworldPlanetmath algorithmMathworldPlanetmath for establishing generators of a stabilizer chain.

Title example of Schreier’s Lemma
Canonical name ExampleOfSchreiersLemma
Date of creation 2013-03-22 15:54:02
Last modified on 2013-03-22 15:54:02
Owner Algeboy (12884)
Last modified by Algeboy (12884)
Numerical id 5
Author Algeboy (12884)
Entry type Example
Classification msc 20K27
Related topic LiftsTransversals