From hoey@aic.nrl.navy.mil Fri Nov 4 11:46:53 1994 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24797; Fri, 4 Nov 94 11:46:53 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA10296; Fri, 4 Nov 94 11:46:51 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Fri, 4 Nov 94 11:46:50 EST Date: Fri, 4 Nov 94 11:46:50 EST From: hoey@aic.nrl.navy.mil Message-Id: <9411041646.AA21659@sun13.aic.nrl.navy.mil> To: Cube-Lovers@life.ai.mit.edu Subject: The real size of cube space 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