Some 3-color cube results

Good work coming up with God's number (and distance distributions) for these tricolor cube metrics, Tom!

I note that I have verified that the 162 maneuvers you listed for the face turn metric do in fact generate 15f* positions according to my optimal solver.

"Positions" that differ only in the way the cube is oriented are generally not counted as distinct positions. With the tricolor cube, you can perform x², y², and z² cube rotations without appearing to affect the centers. This means that each "actual" position has four different "looks" depending upon how the cube is oriented (without changing the 3 axes). So you have provided distance distributions in terms of the 10,863,756,288,000 configurations I mentioned, but you did not get a distribution in terms of the "actual" positions. (Well, I didn't either for my tricolor 4x4x4 centers analysis, so don't feel you have to.)

Also, I'm guessing you got a distribution in terms of the equivalence classes, but I don't see those figures.

You can get 192 "symmetries" similar to how you can get 1152 "symmetries" for the 2x2x2 cube. Just use h = m'*g*m*c where m is an element of M, and c is an element of { identity, x², y², z² }. But as has been pointed out, you still only get at most 48 elements per equivalence class, and conjugating by the elements of M will suffice to find all elements of a symmetry class. The tricolor 4x4x4 centers puzzle has more "symmetries" because there are no pieces tied to a particular axis.

My point is that we can generally talk about as many as 1152 "symmetries" for cubic puzzles. (I may very well be abusing the term symmetry here, hence I've used quotation marks.) These 1152 "symmetries" have been used to perform God's Algorithm calculations for such puzzles as the 2x2x2 cube and the edges-only (no centers) 3x3x3 cube, for example. So they are useful "symmetries." The 1152 symmetries allow us to classify "states" as equivalent if they differ by a rotation of the whole cube (and hence, intrinsically the same state), by a symmetrical equivalence (conjugating by elements of the symmmetry group of the cube), or a combination of both.

What you (Tom) have shown is that some of these symmetries are redundant with the usual 48 symmetries when dealing specifically with the tricolor 3x3x3 cube. And I never claimed in this thread that these "symmetries" weren't redundant with respect to the tricolor 3x3x3 cube. (5/6 of the 1152 "symmetries" always have a visible effect on the centers, so can quickly be deemed irrelevant. This leaves 192 potential symmetries, but as your argument shows, the extra 144 are redundant with the usual 48.)

In the centers-only 4x4x4 tricolor cube, however, we find that the usual 48 symmetries alone are not sufficient, at least if we want states (within the state space of the specified 9,465,511,770 states) that correspond to the same instrinsic state to be in the same equivalence class.

For example, consider the maneuver R' b' u F2 u' b u F2 u' R (with lower case representing inner layer turns) applied to a 4x4x4 supercube. This maneuver has the effect of performing a pure 3-cycle of center pieces. If we conjugate this by the elements of M, we find that this has 3-fold symmetry. Now rotate the whole cube 90 degrees in the same direction as a U move. We now conjugate by the elements of M and produce 48 different states (in the full state space). Without changing the intrinsic state of the cube (only applying a rotation to the whole cube), we have changed it from being 3-fold symmetrical to being asymmetrical! The same holds if we only assume the centers have stickers, and if we assume 3 colors for the centers as well. Clearly, we want a symmetry scheme that provides consistent amount of symmetry for states that correspond to the same intrinsic state of the cube. So simple M-conjugation will not work here.

Your use of the term "symmetry" for ( m' q m c) is entirely appropriate. For the G = < R , U , F , D , B , L > representation of the 2 x 2 x 2 cube:

m' G m c = G for all m ∈ M and c ∈ C

Thus the group is invariant under this transformation and it is a symmetry of the group. It may be productive rather to consider this symmetry as two different symmetries:

c G = G for all c ∈ C

and

m' G m = G for all m ∈ M

If one reduces the group by the rotation symmetries by picking the element with the Down-Left-Back cubie properly oriented in the Down-Left-Back cubical to represent the class the generators reduce to <R , U , F> and you end up with the fixed cubie representation of the puzzle. Thus by using a fixed cubie representation one may reduce the size of the group 24 fold from the get-go. Moreover, now there is a one to one correspondence between the distinct states of the cube and the representation. On the other hand when one proceeds to reduce the group by M conjugation one must apply a rotation to get the conjugates back in the group. So, perhaps it's six of one and half a dozen of the other.

Let me add my two cents to the discussion of the extra symmetry shown by the tri-color cube. The way I look at it there is no extra symmetry beyond the familiar 48 cubic group symmetries. Rather the D2 subgroup (the two fold rotations about the principal axes of the cube) of the cubic group is different in kind, giving by conjugation degenerate cube states rather than merely symmetry equivalent cube states.

Conjugations of a tri-color cube state by the D2 symmetries give states indistinguishable from the original (after a 180° whole cube rotation in most cases). Now the 48 members of the cubic symmetry group may be partitioned into cosets of the D2 symmetry group. Conjugation of a cube state by the elements of each of these cosets likewise give four states indistinguishable from each other. Thus a 48 member equivalence class is composed of only 12 distinct states since it will partition into 12 sets of 4 indistinguishable cubes. Smaller equivalence classes may reduce by a factor of 4, 3 or not at all depending on the symmetry shown by the elements of the class. Classes with elements showing D2 symmetry will not be degenerate, classes showing only one C2 symmetry will have three fold degeneracy and classes showing none of the D2 symmetries will have four fold degeneracy.

I finally got off my duff and did a symmetry analysis of the tri-color cube in line with my earlier comments:

Class Size Degeneracy    Class Count           Cosets       D2 Reduced Cosets
    48         4       226,325,259,954  10,863,612,477,792  2,715,903,119,448
    24         4             5,868,914         140,853,936         35,213,484
    24         2               113,248           2,717,952          1,358,976
    16         4                 8,566             137,056             34,264
    12         4                 1,466              17,592              4,398
    12         2                 6,620              79,440             39,720
     8         4                   352               2,816                704
     6         2                   184               1,104                552
     6         1                    38                 228                228
     4         4                     6                  24                  6
     3         1                    14                  42                 42
     2         1                     8                  16                 16
     1         1                     2                   2                  2
Total                  226,331,259,372  10,863,756,288,000  2,715,939,771,840

So the 43,252,003,274,489,856,000 elements of the six color cube partition into 10,863,756,288,000 cosets by the permutations of the indistinguishable cubies of the tri-color cube. Since the center facelets of opposite faces on the tricolor are indistinguishable this count includes positions which differ only by a 180° whole cube rotation. These duplicates may be eliminated by reduction by D2 symmetry to give 2,715,939,771,840 distinct positions. Reduction by the full 48 member cubic symmetry group gives 226,331,259,372 symmetry distinct positions.

Note that my previous post is in error when it states that a cubic group equivalence class showing only one C2 symmetry is three fold degenerate. Rather the degeneracy is two. Since C2x * C2y = C2z, if a element shows C2x symmetry then the C2y and C2z conjugates are exactly the same rather than needing a 180° whole cube rotation to be the same. Such exact duplicates are eliminated already in forming the equivalence class. Thus my supposed three fold degeneracy collapses into two fold degeneracy.

When the counts for classes of the same size but different D2 degeneracy are combined they agree with those found by Bruce Norskog above. Thus Bruce's counts are confirmed.

Here's how I would transpose the turn sequences:

24 MU R' F' MU2 B L MU' B L MF' R' D B' L'
24 U B L MF R' U D2 R B' F2 MR F' U' R' 
8 L' B D' U' L MF U R MU' R F2 D R'
6 F' L' U' MF U MR2 U' F2 L MU' F' U' L' B'
4 MR B' R' MU' L2 D' MF MR U2 L' D F2 R' B'

And here's the routine I use for the transposition. The trick is to keep a running account of the rotation of the reference frame produced by the replacement of face turns with middle slice turns and transpose the turns accordingly. The code is in MacOS objective c which you would have to port. In my enumeration of the turns r is a clockwise turn and s is a counterclockwise turn.

-(NSData *)transposeToSingmasterPath: (NSData *)path
{
    NSMutableData    *result;
    const RM_Turn    *source;
    RM_Turn            op, op2,  *destination;
    unsigned            n, max, symTag1, symTag2;
    
    result = [NSMutableData dataWithLength: [path length]];
    
    source = [path bytes];
    destination = [result mutableBytes];
    max = [path length] / sizeof(RM_Turn);
    
    symTag1 = [cubicGroup identityTag];
    for( n = 0 ; n < max ; n++ )
    {
        op = [self conjugateOfTurn: source[n] bySymTag: symTag1];
        
        switch (op) 
        {
            case RLr:
                op2 = MRs;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4x3];    //90° cw rotation about the x axis
                break;
                
            case RLs:
                op2 = MRr;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4x];
                break;
                
            case RL2:
                op2 = MR2;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4x2];
                break;
                           
            case UDr:
                op2 = MUs;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4y3];
                break;
                
            case UDs:
                op2 = MUr;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4y];
                break;
                
            case UD2:
                op2 = MU2;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4y2];
                break;
                
            case FBr:
                op2 = MFs;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4z3];
                break;
                
            case FBs:
                op2 = MFr;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4z];
                break;
                
            case FB2:
                op2 = MF2;
                symTag2 =  [cubicGroup tagForElementNamed: CS_C4z2];
                break;
                
            default:
                op2 = op;
                symTag2 = [cubicGroup identityTag];
                break;
        }
        destination[n] = op2;
        // sym1 = sym1 * sym2  i.e. the right product with the last frame rotation
        symTag1 = [cubicGroup productOfOperatorTag: symTag1
                                          stateTag: symTag2 ];
    }
    return result;
}

I've been musing about this all afternoon and I believe I can answer my own question. The four fold degeneracy Bruce Norskog referred to arising from the center facelets of opposite faces being indistinguishable is not subsumed by the 3,981,312 fold degeneracy outlined above. If it were then d * q (where d is one of the three four spot permutations and q is an element of the standard cube group) would be in the same coset as q. This is not in general the case. However, in certain cases d * q is in the same coset. This is exemplified by the identity base set | E |. Since the four spot permutations are members of the base set, d * | E | = | E |. Thus the further reduction of the coset space is something less than 4.

What one can say is that the product d * q will be in same coset as the symmetry conjugate d * q * d since d is an element of |E|.

d * q * | E | = d * q * d * | E |

Thus the nearly four fold degeneracy Bruce mentioned is subsumed by the reduction by symmetry equivalence class performed by Tom Rokicki.