From:

Subject:

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 cubeM 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