Jerry Bryan wrote in his message of 1995/06/28

I guess I am going to have to break down and get a copy of GAP. It
is truly impressive how much GAP can do so easily.

Hah, great, another user for GAP.
Now maybe I can get a raise from my boss ;-)

Jerry continued

My interpretation of Martin's GAP program is that it implements the
general outline of the algorithm I described, except that GAP was
able to calculate the number of K-symmetric permutations in a very
simple and direct way, whereas I was going to have to puzzle each one
out by hand.

Let me rephrase that a little bit. My GAP prgram implements the general
outline of the algorithm you described, except that I am able to tell GAP
to calculate the number of K-symmetric permutations in a very simple and
direct way (but GAP is going to puzzle each one out using an non-simple
and non-direct algorithm I shall outlined in another message).

Jerry continued

The heart of Martin's program appears to be the following, and I have
a couple of questions.

# compute how many elements have at least this symmetry group
number := Size( Centralizer( G, rep ) );

The first question is: how does the Size function work? As a simpler
example than the one above, what if you simply say Size(G)? I am
naively assuming that G is specified to GAP in terms of generators
only, and that it makes no attempt to actually represent each element
of G (too big!). And I have seen snippets of GAP libraries for G
posted by Mark Longridge, and they look like generators. I have been
in several group theory books lately, and I don't recall seeing
a general algorithm presented for determining the size of a finite
group based on its generators.

For this particular case (asking for the size of a centralizer in a
permutation group), the answer is trivial. The algorithm that computes
(generators for) the centralizer computes the size of the centralizer as
a byproduct. I will try to outline this algorithm in another message.

But when you say 'Size(G)', then GAP will indeed use an algorithm that
computes the size of a permutation group given by a set of generators.
The algorithm is called the ``Schreier--Sims'' algorithm. It was
developed by C.Sims for his investigations of sporadic simple groups, and
is mostly based on a lemma by N.Schreier. Unfortunately it is *not*
described in any of the generally available textbooks on group theory.

The funny thing is, that this algorithm works very much like the
algorithm puzzlers use to find a method to solve the cube. Of course it
is lacking the cleverness many puzzlers use to prove that their method is
complete (i.e., solves all possible states), but then the algorithm
(resp. the computer running the algorithm) is a lot more patient.

The first step (for puzzlers and the algorithm) is to find a method to
bring the first facelet to its home place.

The algorithm does this by finding all (24) places to which this facelet
can be moved. This is done by applying the (6) generators to all the
places found so far, and repeating until no new places are found. For
each place it also remembers a process that moves the choosen facelet
from its home place to this place, called a representative for the place.

The second step (for puzzlers and the algorithm) is to find enough
processes that leave the first facelet in its home place. If one has
enough such processes, one can simply start another round of the
algorithm. I.e., one uses those processes to bring the second facelet to
its home place, finds enough processes that leave the first and the
second facelet in their respective home places, and so on.

In group theoretic terms the set of elements that leave the first facelet
is in its home place is a subgroup (called the stabilizer of that point),
and the problem is to find a set of generators for this subgroup.

So how does the algorithm find such a set of generators? This is where
Schreier's lemma kicks in.

Let us first take a representative <r1> of a place <p1> (so <r1> moves
the first facelet to the place <p1>). Then we multiply this by a
generator <g> of the original group. Say <g> moves the first facelet
from the place <p1> to the place <p2>. Finally we multiply the product
<r1> * <g> by the inverse of the representative <r2> of the place <p2>.
This obviously moves the first facelet back to its home place, so the
product <r1> * <g> * <r2>^-1 is a process that leaves the first facelet
in its home place, i.e., it is an element of the subgroup.

Now Schreier's lemma says that if we take all 24 times 6 such elements,
then the resulting set is a set of generators for the subgroup. In fact
Schreier's lemma says that if you select the representatives carefully,
then 24 * (6 - 1) + 1 generators will suffice, and for certain subgroups
(subgroups of free groups) no smaller set of generators will do.

So we now start another round of the algorithm with this (smaller)
subgroup. How much smaller is this subgroup? The size of the whole
group is the size of the subgroup times 24 (we get each element of the
whole group exactely once by multiplying each subgroup element by each of
the 24 representatives). So the subgroup is smaller by a factor of 24.

After at most 48 rounds (for the 48 facelets) we are done.

We can now easily compute the size of the entire group. It is the size
of the subgroup of those elements that leave the first facelet in its
home place times 24 (the number of possible places for the first
facelet). The size of this subgroup is the size of the subgroup that
leaves the first and the second facelet in their respective home places
times the number of possible places for the second facelet. And so on.

We also have a method to solve any state as follows. We first find the
place <p1> of the first facelet and multiply by the inverse of the
representative of <p1>, to move that facelet back to its home place.
Then we find the place <p2> of the second facelet and multiply by the
inverse of the representative found in the second round of the algorithm,
to move that facelet back to its home place. Since that representative
was found in the second round it doesn't move the first facelet, so now
the first and the second facelet are in their respective home places.
After at most 48 rounds, we have moved all facelets to their home places.

As has been pointed out before, such a method to solve any state gives us
a membership test for <G>. Suppose we are given an arbitrary permutation
<x> of the facelets. Then we simply try to solve <x>. If we can solve
it, then <x> is an element of <G>. If we cannot solve it, then <x> is
not an element of <G>.

Now the algorithm as described above has a fatal flaw. The number of
generators increases with each round. In the first round we have 6
generators, in the second round we have about 24 * 6 generators, in the
third round we have about 24^2 * 6 generators, and so on. Most of these
generators will be redundant, i.e., they will lie in the subgroup
generated by the other generators.

The solution is as follows. Instead of taking all 24 * 6 generators for
the second round, we randomly select some (say 6) of them. Those will
generate a subgroup <S> of the whole stabilizer (and our hope is that
this subgroup will be equal to the whole stabilizer). Then we apply the
algorithm to <S>, and compute a method to solve any element of <S>. As
described above, this gives us a way to test membership in <S>. We now
compute all 24 * 6 generators for the stabilizer, and for each one test
whether it is an element of <S>. If they are all elements of <S>, then
<S> is indeed the whole stabilizer, and we are done. If not, then we
have found a new non-redundant generator for the stabilizer, and we start
anew, this time with 7 generators instead of the originally choosen 6.

The first algorithm is sometimes called the iterative Schreier--Sims,
because it iterates over the stabilizers. The second algorithm is called
the recursive Schreier--Sims, because it assumes that we have solved the
problem for <S> recursively. This is the algorithm currently implemented
in GAP. There is a third variant called Schreier--Todd--Coxeter--Sims,
that uses a Todd--Coxeter algorithm to prove that <S> is the whole
stabilizer without computing all Schreier generators, which is important
when there are many (say 1000000) possible places for the first facelet.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany