From:

~~~ Subject:

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.

The Polya-Burnside theorem describes a relation between a finite group

J and a _representation_ of the group. For our purposes, a represen-

tation is a homomorphism of J into a permutation group, R: J -> S[X].

Here, S[X] refers to the group of all permutations of a set X; the

image of J, called R(J), need not be the whole of S[X], but R(J) will

be a subgroup of S[X]. The _orbits_ of R(J) are the equivalence

classes of X under the relation x~y, said to be true if there is some

permutation p in R(J) for which p(x)=y. The _fixed points_ of a

permutation p in R(J) are the elements x of X for which p(x)=x. The

Polya-Burnside theorem states that the average number of fixed points

of permutations in R(J) is equal to the number of orbits of R(J).

That is,

|R(J)| |Orbits(R(J))| = Sum[p in R(J)] |FixedPoints(p)|.

The average may also be taken over J:

|J| |Orbits(R(J))| = Sum[j in J] |FixedPoints(R(j))|,

a nontrivial distinction, since R may not be one-to-one (though it is

for our application). The Polya-Burnside theorem is not very

inaccessible nor hard to prove, but I will not prove it here.

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].

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.

There are several tools to make the counting easier. First, I'll note

that just as there are M-conjugacy classes of Gx, there are

M-conjugacy classes of M itself. The number of fixed points of R(m)

is the same for any m in a given conjugacy class. So to calculate the

total number of fixed points over R(M), we need only calculate the

number of g in Gx commuting with each of the ten classes of cube

symmetry and multiply by the size of the class.

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).

For g to commute with m, we have g(c2)=m(g(c1)), g(c3)=m(g(c2)), ...,

g(ck)=m(g(c[k-1]), and g(c1)=m(g(ck)). So (g(c1),g(c2),...,g(ck)) is

also a cycle of m. Thus g must map each k-cycle of m to another

k-cycle of m, and in the same order. Conversely, if g acts thus on

cycles, then g will commute with m, and so g is a fixed point of R(m).

Suppose that m has j different k-cycles of cubies. There are j! k^j

possibilities for g's action on the cubies in those k-cycles: j!

permutations of cycles, and for each g:(c1,c2,...,ck)->(d1,d2,...,dk),

k choices for g(c1) among {d1,...,dk}. It turns out to be a fairly

easy exercise to show that half of those possibilities are even

permutations and half odd, though the partition by parity is

surprisingly different depending on whether k is even or odd. This

will allow us to combine the results for GE and GC simply by

multiplying together and dividing by two.

Now consider orientation of cubies. This is similar to the case of

permutation, in that the orientation that g imposes on a cubie is a

constant for all cubies in a cycle. I will first discuss the edge

orientation, which is fairly straightforward, and continue to corner

orientation, which has some surprising features.

For edge orientation, if all the cycles have even length, then g's

orientation parity is zero over each cycle, and so zero over the

entire cube. So we can choose the orientation of imposed by c1->g(c1)

for each cycle (c1,...,ck) in 2^j ways. If there are odd-length

cycles, then half of the orientations will have nonzero orientation

parity, and only 2^(j-1) possible orientations can be achieved.

For corners, we might expect there to be 3^(j-1) orientations, except

3^j for cycles of length a multiple of three, and this is often so.

But there are two important exceptions. First, if m is a reflection

(i.e., not a proper rotation in C) then alternate cubies in each cycle

must be given the opposite orientation by g. If the cycle has even

length, this conserves orientation, so there will be 3^j possibili-

ties. If the cycle has odd length, this implies that the orientation

of each cubie must be its own opposite (i.e., zero twist). Thus,

there there is only one possible orientation of the 1-cycles in the

diagonal reflections. The second exception, an even bigger surprise,

occurs when m is either the 120-degree rotation or the 60-degree in-

verted rotation. It turns out that the orientation constraint forbids

any permutation that exchanges the two 1-cycles in these positions.

(This constraint on permutations would throw off the equality between

even and odd permutations, except that these classes of m have other

corner cycles that restore the balance.) The impossibility of m

commuting with an exchange of the two corners can be verified by

examining the possible orientations, but I haven't got any good way of

characterizing when it would be be a problem in general. In fact, I

did not notice it until I investigated discrepancies with the

exhaustive computer analysis.

Using the above analysis, we may carry out the calculation as in the

three tables below. The first two tables count the number of fixed

points of R(m) for an element m of each class, multiply by the class

size, and divide by |J|=48 to get the number of orbits as in the

Polya-Burnside theorem. The third table calculates the number of

fixed points by combining the results of the first two tables, divided

by the class size (which was multiplied in both for edges and for

corners), and divided by 2 (because only half the combined positions

have matching permutation parity).

Counting M-conjugacy classes of the edges of Rubik's cube.

M class Cycles Total F.P. Numeric (class size) of m Perms Oris in class Total/48 ============== =========== ====== ====== ========== =========== Identity (1) 12 1-cycles 12! 2^12/2 12! 2^11 20437401600 Axis Rot/2 (3) 6 2-cycles 6! 2^6 2^6 6! 3 2^12 184320 Rot/3 (8) 4 3-cycles 4! 3^4 2^4/2 4! 3^4 2^6 2592 Diag Rot/2 (6) 5 2-cycles 5! 2^5 2^5 2 1-cycles 2 2^2/2 5! 3 2^13 61440 Rot/4 (6) 3 4-cycles 3! 4^3 2^3 3! 3 2^10 384 Inv Rot/4 (6) 3 4-cycles 3! 4^3 2^3 3! 3 2^10 384 Diag Ref (6) 5 2-cycles 5! 2^5 2^5 2 1-cycles 2 2^2/2 5! 3 2^13 61440 Inv Rot/6 (8) 2 6-cycles 2! 6^2 2^2 2! 3^2 2^7 48 Axis Ref (3) 4 2-cycles 4! 2^4 2^4 4 1-cycles 4! 2^4/2 4! 3^2 2^14 73728 Inversion (1) 6 2-cycles 6! 2^6 2^6 6! 2^12 61440 ----------- | GE\Conj(M) | = 20437847376

Counting M-conjugacy classes of the corners of Rubik's cube.

M class Cycles Total F.P. Numeric (class size) of m Perms Oris in class Total/48 =============== ========== ====== ===== =========== ======= Identity (1) 8 1-cycles 8! 3^8/3 8! 3^7 1837080 Axis Rot/2 (3) 4 2-cycles 4! 2^4 3^4/3 4! 3^4 2^4 648 Rot/3 (8) 2 3-cycles 2! 3^2 3^2 2 1-cycles 1 3^2/3 3^5 2^4 81 Diag Rot/2 (6) 4 2-cycles 4! 2^4 3^4/3 4! 3^4 2^5 1296 Rot/4 (6) 2 4-cycles 2! 4^2 3^2/3 3^2 2^6 12 Inv Rot/4 (6) 2 4-cycles 2! 4^2 3^2 3^3 2^6 36 Diag Ref (6) 2 2-cycles 2! 2^2 3^2 4 1-cycles 4! 1 4! 3^3 2^4 216 Inv Rot/6 (8) 1 6-cycle 6 3 1 2-cycle 1 3 3^3 2^4 9 Axis Ref (3) 4 2-cycles 4! 2^4 3^4 4! 3^5 2^4 1944 Inversion (1) 4 2-cycles 4! 2^4 3^4 4! 3^4 2^4 648 ------- | GC\Conj(M) | = 1841970

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) =============== ========== ========= ======================= Identity (1) 12! 2^11 8! 3^7 901,083,401,551,872,000 Axis Rot/2 (3) 6! 3 2^12 4! 3^4 2^4 955,514,880 Rot/3 (8) 4! 3^4 2^6 3^5 2^4 629,856 Diag Rot/2 (6) 5! 3 2^13 4! 3^4 2^5 318,504,960 Rot/4 (6) 3! 3 2^10 3^2 2^6 18,432 Inv Rot/4 (6) 3! 3 2^10 3^3 2^6 55,296 Diag Ref (6) 5! 3 2^13 4! 3^3 2^4 53,084,160 Inv Rot/6 (8) 2! 3^2 2^7 3^3 2^4 1,296 Axis Ref (3) 4! 3^2 2^14 4! 3^5 2^4 1,146,617,856 Inversion (1) 6! 2^12 4! 3^4 2^4 955,514,880 ----------------------- | G\Conj(M) | = 901,083,404,981,813,616

These results have been corroborated and expanded by use of

combinatorial computer programs, to be described in a later message.

Dan Hoey

Hoey@AIC.NRL.Navy.Mil