# Rubik's Cube antisymmetry and the shrinking of Cube Space

In this posting we introduce the concept of antisymmetry of Cube positions: antisymmetric positions include self-inverse positions as a special case. We show that the size of Cube Space is reduced by approximately a factor of 2 after taking account of positions that are related to one another by antisymmetry. The "new" real size of Cube Space is found to be 450541810590509978.

[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

## Comment viewing options

### Letter L pattern on all the six faces

About 20 minutes ago I hit upon a posting in news:sci.math by Herbert Kociemba (June 15th 2005 22:19) on antisymmetric Cube positions. So I am an absolute beginner in this forum.

The subject awakened memories from bygone times! In the 1980s I spent many hours with the Cube. I bought two copies; on one of them I studied what special positions arise when one systematically turns opposite faces thru a quarter-turn, both of them in the same screw sense with respect to the centre.
At a certain time I obtained a letter L (5 squares) in four of the faces and a mirrored letter L in the remaining two. Unfortunately I did not record the exact sequence of turns. I darenot restore the start position, afraid to lose this elegant six Ls position.

Is this subject of sequences of special turns an existing specialism?

I was much pleased to find that Rubik's Cube is after 25 years still alive and kicking.

### First of all, congrats to Mik

First of all, congrats to Mike and Herbert for the excellent work.

Joher,
Yes, a lot of research has already been done on such special sequences. In particular, what you describe are anti-slice moves, and the group of positions you can get with just those moves (the anti-slice group) is well known.

If you take a look at my web site (link below), you will find a Java applet that allows you to restrict yourself to just those moves, as well as a built-in solver for it. Similarly, the group of positions reached with only half turns (the square group) is also represented there.

Cubie applet:
http://www.geocities.com/jaapsch/puzzles/cubie.htm

I would also recommend that you try to find a copy of David Singmaster's Notes on the Magic Cube, which sets out much of the groundwork of the theory of the cube, including a calculation of how many positions there are in the anti-slice group, or the square group.

Singmaster's Cubic Circular magazine came out after his Notes, and can be found on my site.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

### I also would like to congratu

I also would like to congratulate Mike and Herbert for their excellent work.

The possibility of using inverses to reduce the size of the "real" cube space by approximately another factor of 2 was mentioned in Cube-Lovers. But nobody ever posted the detailed calcululations to Cube-Lovers. This certainly seems like the first time anybody has performed the calculations.

Also, the possibility of implementing this reduction in the size of the search space in a search program was mentioned in Cube Lovers. But to the best of my knowledge, nobody has ever implemented such a reduction. I am working on a new set of programs as we speak that will include this feature, but I am a long way from having the new programs in production. I'm curious if Herbert has implemented this feature in any of his programs, or is planning to.

Finally, some time after Dan Hoey posted his Polya-Burnside results to Cube-Lovers, Martin Schoenert performed the same calculations with about two lines of GAP code. Well, there were some GAP libraries behind the scenes that defined the Rubik's Cube group and also that defined the group of symmetries for the Cube. So those group definitions did not count against the "two lines of code". What I always meant to do and never did was to chase down what GAP was doing behind the scenes to implement its "two lines of code". It might have been doing something similar to Dan's Polya-Burnside calculations, or it may have been doing something entirely different. I don't know.

See
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Martin_Schoenert__Re__The_real_size_of_cube_space.html

for Martin's GAP calculation of the "real" size of cube space.

Jerry Bryan

### Reduction of cube space with GAP

First, I am very new to this, so bear with me while I attempt this:

I have written the class of symmetries for GAP that can replicate Martin's results and the idea can further be applied to other permutation puzzles. (Given the class of symmetries, M) This is merely what Martin wrote in the article http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Martin_Schoenert__Re__The_real_size_of_cube_space.html with one minor change:

gap> Sum( ConjugacyClasses( M ),
> c -> Size( Centralizer(G,Representative(c)) ) / Size( M ) * Size(c) );

If you would like to see the definitions of M I used I will post them here.

I may have an explanation to the question of what GAP did.

What Martin was using is what www.mathworld.com refers to as the Cauchy-Frobenius Lemma.

It states this: Let J be a finite group and the image R(J) be a representation which is a homomorphism of J into a permutation group S(X), where S(X) is the group of all permutations of a set X. Define the orbits of R(J) as the equivalence classes under x~y, which is true if there is some permutation p in R(J) such that p(x)=y. Define the fixed points of p as the elements x of X for which p(x). Then the average number of fixed points of permutations R(J) in is equal to the number of orbits of R(J).

Using this to enumerate the equivalence classes in GAP would be averaging the sum of the size of the centralizers of each permutation.

This lemma was later rediscovered by Burnside as a coloring theorem and is a an application of the Cauchy-Frobenius Lemma.

It accounts for all N-colorings by averaging the number of colorings left fixed by each permutation. (N^(number of cycles in permutation))

I hope I didn't confuse anyone with my lack of experience...
Questions/comments/corrections welcome!

Thank you for your time,
-Joe

### Using antisymmetry in Cube Explorer search

The coordinates I use in Cube Explorer are incompatible to inversion, so I cannot use this feature. Take for example the orientations of the edges, which are described by a number from 0 to 2047. There is no possibility to map a coordinate x to a coordinate x' which describes the "inverse" of x because the coordinate x gives no information about the permutation. Only edge-coordinates, which store the complete information about the permutation of all 12 edges can be "inverted".

### Reduction of search space?

> The possibility of using inverses to reduce the size of the
> "real" cube space by approximately another factor of 2 was
> mentioned in Cube-Lovers.

Interesting -- I hadn't noticed this. The calculation seemed a natural thing to do after we'd completed a scheme for classifying Cube positions by their "magnetic symmetry". (In Cube Explorer, Herbert has provided a tool to search for positions in a specified magnetic symmetry class).

> Also, the possibility of implementing this reduction in the size
> of the search space in a search program was mentioned in Cube
> Lovers.

I hadn't noticed this either. Do you remember when it was discussed?

Mike

### After diligent searching, I c

After diligent searching, I can't find a mention of a further reduction by a factor of two in the Cube Lovers archives. Either my searching has not been diligent enough, or (more likely) there was private E-mail about the subject that did not make it to Cube-Lovers. So my apologies.

I will use the old Cube-Lovers convention that the group of 48 symmetries of the cube is called M. The normal way that symmetry can be used in a search of a large cube space space is simply to calculate for each position x the set of M-conjugates x^M, and to define a representative for each set of M-conjugates as

y=Rep(x)=min(x^M)

(x^M means {x'mx | m in M} )

Then, it is only the representatives that are stored and manipulated. The representatives are not very well behaved (they are not amenable to being stored in a Sims table, for instance), so managing and indexing large numbers of them is non-trivial. That is, there is some extra cost associated with gaining the approximately 48 times reduction in the search space.

To gain the additional 2 times reduction in the search space in a computer program, representatives have to be defined as

y=Rep(x)=min(x^M union z^M) where z=x'

When searching cube space, given a representative y it is necessary to calculate all its neighbors -- those positions one move away. With representives in a search space reduced by 48 times, the neighbors of y are of the form Rep(yk), where k is a member of the set of allowable moves. With representatives in a search space reduced by 96 times, the neighbors of y are all the positions of the form Rep(yk) plus the all positions of the form Rep(y'k), where k is defined as before. As an alternative, you could calculate all positions of the form Rep(yk) plus all the positions of the form Rep(ky).

Jerry