Dan Hoey writes in his e-mail message of 1994/11/04

In January of this year, Jerry Bryan and I wrote of counting the
number of M-conjugacy classes of Rubik's cube. In the sense that (for
instance) there is really only one position 1 QT from start, even
though that QT may be applied in twelve different ways, this task
amounts to counting the true number of positions of the cube. The
earlier discussion centered on calculations involving computer
analysis of large numbers of positions. However, a look in Paul B.
Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside
theorem is a tool that allows us to perform this calculation by hand.

...a very nice application of the Polya-Burnside theorem,
to compute the number of M-conjugacy classes in G...

Yes, a little bit of group theory can answer many questions arising from
the cube. In fact I have noticed that quite a few of well known results
in group theory have been rediscovered in this forum. Note that I don't
think this is a bad thing. At least for me results that I ``knew'' are
now, that they have been demonstrated for the cube, much easier to grasp
than they were before (grasp is certainly an appropriate term in
connection with the cube).

Dan continues

For our purpose, we take the group J to be M, the 48-element group of
symmetries of the cube. X will be the set of all cube positions,
which we usually call Gx (for GE, GC, or G, depending on whether we
consider edges, corners, or both; we are considering the positions
relative to fixed face centers in all three cases). And the repre-
sentation R is the operation of M-conjugation: (R(m))(g) = m' g m.
Verifying that R is a homomorphism is an exercise in associativity
that Jim Saxe and I carried out in the Symmetry and Local Maxima
paper, in the archives [cube-mail-1, 14 December 1980].

The way I view this is as follows. The entire cube group C is a
permutation group group on 6*9 points, generated by the six face turns U,
D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the
reflection S. This group has a subgroup M of symmetries of the cube (of
order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another
subgroup is G, generated by the six face turns, which has index 48 in G.
G is a normal divisor of C, G is the semidirect product of M and G. The
same is true for GE and GC.

Obviously M operates by conjugation on G, and this implies that the
mapping R is a homomorphisms.

Another way to say this is that M is a subgroup of the outer autmorphism
group of G (which in this case can be easily represented as a supplement
of G). Note that the elements of M are also a autmorphisms of the Cayley
graph. That means that elements of M respects the length of operations.
That is if g_1 and g_2 are elements of G that are in one conjugacy class
under M, then the lenght of the shortest process effecting them is equal.
This follows from the fact that M fixes the set of the generators of G
and their inverses. M is fact the largest subgroup of the outer
autmorphism group with this property, which makes it rather important.

Dan continues

R has been so chosen because we wish to calculate the number of
M-conjugacy classes of Gx, |Gx\Conj(M)|, which is be the number of
orbits of R(M). To apply the Polya-Burnside theorem for this, we need
to calculate, for each element of m of M, the number of fixed points
of R(m). That is the number of elements g of Gx for which m' g m = g.
Multiplying by m, this becomes g m = m g: the fixed points we wish to
count are just those elements g of Gx that commute with m.

This set is called the *centralizer* of m in Gx. Usually the centralizer
in a group X is only defined for elements in X, but it is obvious how to
extend this definition.

Dan continues

The fundamental principle we use in finding whether g commutes with m
can be found by examining the cycles of m. Suppose m permutes a cycle
(c1,c2,...,ck), so that c2=m(c1), c3=m(c2),...,ck=m(c[k-1]),c1=m(ck).
...nice discussion of what must happen to cycles if two
permutations commute...

This can be used directly to compute the centralizer of an element in the
full symmetric group. Since G's structure is very similar to a symmetric
group (or more accurately the direct product of two symmetric groups), it
allows to describe the centralizer of an element in G. The more a group
differs from a symmetric group the less this analysis helps (for those
that know what I'm talking about: the more a group differs from the
symmetric group, the worse a backtrack computation using cycle structure
analysis is).

Dan continues

Counting M-conjugacy classes of the entire Rubik's cube

M class             Edge         Corner       Corner times edge
  (class size)      F.P.          F.P.             / (96*class size)
===============  ==========     =========    =======================

Minor typo. You don't mean ``Corner times edge / (96 * class size)'' but
``Corner times edge / 96 * class size'', which is in fact what you
computed for the following table.

Dan continues

| G\Conj(M) | = 901,083,404,981,813,616

Here is how you compute this value in GAP (excuse me the plug).

gap-3.4 -b -g 4m 
gap> Sum( ConjugacyClasses( M ),
>         c -> Size( Centralizer(G,Representative(c)) ) / 48 * Size(c) );
901083404981813616

Have a nice day.

Martin.

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