Rubik's Cube antisymmetry and the shrinking of Cube Space

[Contribution also posted on sci.math]

In the old Cube Lovers mailing list around 1993-4, there was active interest in the problem of counting the essentially distinct positions of the Cube, up to whole-cube symmetries. Work by Dan Hoey and Jerry Bryan led to the "Real Size of Cube Space" being calculated as

RealSize = 901083404981813616

[Dan Hoey, "The Real Size of Cube Space", Cube Lovers 4 Nov 1994]. This number is approximately 1/48 of the order of the Cube group,

NaiveSize = 43252003274489856000,

because the vast majority of positions lack symmetry, and each of these unsymmetrical positions is equivalent to 47 others after rotation or reflection. The exact calculation is non-trivial, precisely because some Cube positions are invariant under certain rotations or reflections: simple division by 48 undercounts these symmetrical positions.

In those earlier discussions, positions x and y are regarded as equivalent if y=g[x], where the mapping g[x]=gxg' describes the action of an element g of the full cubic symmetry group of order 48. [Although it is an abuse of notation to use g for both the symmetry element and its action on Cube positions, we trust that no confusion will arise here: in most of the following discussion, g will denote one of the 48 mappings just defined and G will denote the corresponding group of 48 mappings.]

We remark at this point that the idea of symmetry may be extended to include invariance under inversion, which we call "time reversal" here, mainly to avoid confusion with "inversion" in the sense of "central reflection". Accordingly, we say that a self-inverse Cube position is invariant under the operation of time reversal T, defined by the mapping T[x]=x'. Less trivially, there are positions that are invariant under the combined action of time-reversal and a spatial symmetry operation; for example, the 3-cycle (UF,UR,UL) is invariant under left-right reflection followed by time-reversal. Generalized symmetries of this kind have been extensively discussed in the crystallographic literature, particularly for the classification of magnetic solids by their symmetry. In that context, invariance under the combined action of time reversal and a spatial symmetry element is often called an "antisymmetry": we shall borrow this terminology here.

It appears natural to generalize the idea of equivalence of Cube positions to include both symmetry and antisymmetry. In addition to the usual equivalence under symmetry, we shall also regard two Cube positions x and y as equivalent if one is the inverse of the other, x=T[y]; or, more generally, if x=T[g[y]], where the mapping g corresponds to an ordinary spatial symmetry element. We can then ask: What is the Real Size of Cube Space, after taking antisymmetry into account?

As discussed in Dan Hoey's message, the Polya-Burnside lemma was a very helpful tool in his calculations, as it reduced the problem to that of enumerating the relatively small numbers of positions that are invariant under each of the spatial symmetry operations. Fortunately, the same method can also be applied when the antisymmetries are included.

To see why this is possible, we augment the transformation group G by including all the antisymmetry transformations to obtain an enlarged set of transformations A = G + TG. Here we note (1) that T is self-inverse, T[T[x]]=x, and (2) that T commutes with any spatial symmetry transformation g, T[g[x]]=g[T[x]]. [When applied to any Cube position, g rotates (or reflects) the facelet cycles in space, while T simply reverses the directions of the cycles: the order of these operations is immaterial.]

From (1) and (2) it follows at once that the enlarged set of transformations, A, is a group (of order 96) whose multiplication rule is the usual composition of mappings of the set of Cube positions onto itself: if a and b are elements of A, ab is defined such that (ab)[x] = a[b[x]] for every position x; of course, the identity element e has the property e[x]=x. These conditions are sufficient for the Polya-Burnside lemma to be applied to the set of Cube positions under the action of the group of mappings A.

By use of the Polya-Burnside lemma, the "new" Real Size of Cube Space (by which we mean the number of orbits of A) can be found as the "average" Sum_a N(a)/96 taken over all mappings a from A, where N(a) is the number of fixed points of a; i.e., the number of solutions of a[x]=x. Of course, N(e) = NaiveSize, and the quantities N(g), for spatial symmetry transformations g, were previously given in Dan Hoey's message.

We independently wrote programs to search for positions with each kind of (anti)symmetry. The computations were broken up into much the smaller ones needed for odd and even permutations of corners and edges taken separately: our results agree in all cases. Although it was strictly necessary to calculate N(a) only for the cases of antisymmetry, we calculated the known N(g) as a further check.

To reduce the size of the table below, we omit the known results for the ordinary symmetries, so that an entry such as "diagonal mirror plane (6)" refers only to the 6 antisymmetries related to the mirror planes of that kind. The "Total" in that particular case would be

6*(7607424*56052 + 8080448*54432) = 5197477653504.

It will be noticed, especially among the order-2 antisymmetries, that certain of the numbers are repeated. We indicate the reasons for this later.

identity (1)
Edges even:   8080448   Edges odd:   7607424
Corners even:   10396   Corners odd:   11424
Total: 170911549184

central reflection (1)
Edges even:   8080448   Edges odd:   7607424
Corners even:   56052   Corners odd:   54432
Total: 867012574464

2-fold rotation about face normal (3)
Edges even:   8080448   Edges odd:   7607424
Corners even:   10396   Corners odd:   11424
Total: 512734647552

2-fold rotation about diagonal (6)
Edges even:   7607424   Edges odd:   8080448
Corners even:   10396   Corners odd:   11424
Total: 1028386907136

mirror plane parallel to face (3)
Edges even:   8080448   Edges odd:   7607424
Corners even:   56052   Corners odd:   54432
Total: 2601037723392

diagonal mirror plane (6)
Edges even:   7607424   Edges odd:   8080448
Corners even:   56052   Corners odd:   54432
Total: 5197477653504

3-fold rotation about body diagonal (8)
Edges even:       116   Edges odd:        72
Corners even:       1   Corners odd:       9
Total: 6112

6-fold rotation-reflection about body diagonal (8)
Edges even:       116   Edges odd:        72
Corners even:       9   Corners odd:       9
Total: 13536

4-fold rotation about face normal (6)
Edges even:       960   Edges odd:         0
Corners even:     108   Corners odd:       0
Total: 622080

4-fold rotation-reflection about face normal (6)
Edges even:       960   Edges odd:         0
Corners even:      36   Corners odd:       0
Total: 207360

The sum of the Totals taken over all antisymmetries is

TotalAnti = 10377561904320.

From this we obtain

NewRealSize = (48*RealSize + TotalAnti)/96 = 450541810590509978.

***************************
We turn now to the "coincidences" noticed in the above table, and, for the order-2 antisymmetries, we re-derive the computed results via combinatorial arguments. (Actually, we have verified all of the table entries by separate calculations by hand: the sample calculations provided below should give an indication of the kinds of considerations involved.)

As a preamble to the arguments, we observe that for any order-2 spatial symmetry element g of the cubic symmetry group we have, for the fixed points of the mapping Tg,

x=Tg[x] <=> x= gx'g' <=> gx = x'g' <=> gx = (gx)',

so that x is a fixed point of Tg if and only if gx is self-inverse. This means that the number of fixed points of Tg in the set of all cube positions X is the same as the number of self-inverse positions in the mapped space gX.

Let us denote by XE (XC) the set of all edge (corner) configurations, respectively.

First we consider the edge configurations. For any order-2 spatial symmetry element g we have gXE = XE, so the numbers of fixed points of Tg are the same as the numbers of self-inverse edge positions in XE: these are given as 8080448 and 7607424 in the first entry of our table above. The diagonal mirror-plane reflection is the only odd permutation here: the numbers 8080448 and 7607424 are swapped in this case because even permutations in gXE are mapped to odd permutations in XE, and vice versa. This explains all of the instances of the numbers 8080448 and 7607424 in the table.

The same argument applies to the corners in case of 2-fold rotations (this explains the various appearances of 10396 and 11424), but cannot be used in the case of 2-fold reflections. The reason is that the space gXC is not identical with XC here: corners have a "handedness" which changes under reflection. Nevertheless, it is possible and interesting to understand why there are many more self-inverse corner positions in gXC than there are in XC. The precise origin of this difference will emerge only towards the end of the detailed calculations below, because we prefer to present the simpler calculations for the edges first.

The first entry in the table corresponds to self-inverse positions: these consist only of products of 1-cycles and 2-cycles of cubies. We consider the edge permutations.

If C(n,k) denotes the binomial coefficient, we have, for example,
C(12,2)C(10,2)C(8,2)/3! for the number of edge permutations with exactly three 2-cycles, ignoring the possible orientations.

Owing to the self-inverse property, there are only two possibilities for the flips in any one of the 2-cycles: namely, those cases where the total number of flips in the 2-cycle is even, i.e., 0/0 and 1/1. In contrast, all orientations are permitted for the six 1-cycles, subject to the constraint that the total number of flips be even. After taking into account these possibilities for the orientations, we find

[C(12,2)C(10,2)C(8,2) / 3!] * 2^3 * 2^5

for the number of edge positions with exactly three 2-cycles. Analogous expressions can, of course, be written down for any number of 2-cycles. If we use Pe(n) = C(12,2) ... C(12-2(n-1),2)/n! to denote the number of edge permutations with n 2-cycles (ignoring the orientations), we then have for the number of self-inverse odd permutations of edges

Pe(1)*2^1*2^9 + Pe(3)*2^3*2^5 + Pe(5)*2^5*2^1 = 7607424.

Similarly, for the self-inverse even permutations of edges we find

2^11 + Pe(2)*2^2*2^7 + Pe(4)*2^4*2^3 + Pe(6)*2^6 = 8080448.

In the case of self-inverse corner positions, the twist of each fixed corner must be 0. For each 2-cycle, the total twist over the cycle is 0 (mod 3), giving 3 possibilities for the orientations: namely, 0/0, 1/2 and 2/1. There are no further restrictions on the twists, so that, with Pc(n) defined analogously to Pe(n) by

Pc(n) = C(8,2) ... C(8-2(n-1),2)/n!,

we get for the number of self-inverse odd permutations of corners

Pc(1)*3^1 + Pc(3)*3^3 = 11424,

while for the even self-inverse corner permutations we find

1 + Pc(2)*3^2 + Pc(4)*3^4 = 10396.

Finally, we show how to calculate the numbers of fixed points of XC for a 2-fold antisymmetry involving a reflection, such as the central reflection m. Although the number of fixed points of Tm in XC can be obtained by direct, combinatorial arguments, the calculation can be shortened considerably by recalling that (as explained above) this is equivalent to finding the number of self-inverse corner positions in mXC. First, however, we must briefly indicate how the twist of a corner may be generalized to include the possibility of reflection.

When no reflection is made (so, for positions in XC), the twists of the corners are combined by addition (mod 3), which is isomorphic to multiplication in the cyclic group C3. On the other hand, when the processes of twisting are generalized to include reflection (as is necessary when we consider mXC), these actions must be combined via multiplication in the dihedral group D3. We define three new, reflected orientations 3, 4 and 5 as follows: the central reflection m applied to a corner with orientation o = 0, 1 or 2 sends the corner to the diagonally opposite location with the orientation o+3. From the preceding definition of the orientations it is clear that 3, 4 and 5 may also be used to denote the three operations of reflection in D3; naturally, these operations are self-inverse, so that we have 3+3 = 4+4 = 5+5 = 0.

Now, the difference between positions in mXC and XC is simply that all corner orientations are 3, 4 or 5 in mXC and 0, 1 or 2 in XC. We have the same constraint on the corner orientations in mXC as in XC, in the sense that the sum of all corner orientations (regarded here purely as integers) has to be 0 (mod 3). This gives additional possibilities for the twists of self-inverse corner 1-cycles in mXC, which may have any of the three values 3, 4 or 5, in contrast to the single value 0 in XC. The 2-cycles again have three possibilities in mXC (namely 3/3, 4/4 and 5/5), but with an additional difference compared with XC that the integer sum of the twists over a 2-cycle is not 0, except for the case 3/3. Then we have, for example, 3^1*3^5 possible orientations for a self-inverse permutation with exactly one 2-cycle: this may be understood as a factor 3^1 for the possible orientations of the 2-cycle and a factor 3^5 for the orientations of the remaining six corners.

Accordingly, for the self-inverse corner positions in mXC we find totals

Pc(1)*3^1*3^5 + Pc(3)*3^3*3^1 = 54432

for the odd permutations and

3^7 + Pc(2)*3^2*3^3 + Pc(4)*3^3 = 56052

for the even permutations. Note, in particular, that the factor 3^3 appears in the coefficient of Pc(4) in this expression, in contrast to the corresponding factor 3^4 in the unreflected case. The reason for this difference is that the total twist over each self-inverse 2-cycle need not be 0 in mXC, so there is only one choice for the fourth 2-cycle.

***************************
Mike Godfrey and Herbert Kociemba