example of Schreier’s Lemma
is a subgroup of , and furthermore, the orbit canonically parameterizes a transversal of . That is, to every coset there corresponds precisely one image and visa-versa. This leads to one of the most significant applications of Schreier’s lemma.
Geometrically it is not too difficult to understand that the stabilizer is the subgroup ; 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 is but in order to make use of Schreier’s lemma we encode the orbit together with a representative of which transports to the corresponding orbit element. For example:
This translates to the following simple transversal
Notice that we have used the generators of to create the orbit so that the transversal is created as words over the generators of 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 . Here is the set:
Remembering these words are permutations we further find the set reduces to
Finally, we must intersect with . At first glance this feels impossible as we do not yet know ; however, we do know that if and only if . So we test this for each element of and find that indeed each element in this case lies in . 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 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.
|Title||example of Schreier’s Lemma|
|Date of creation||2013-03-22 15:54:02|
|Last modified on||2013-03-22 15:54:02|
|Last modified by||Algeboy (12884)|