Antisymmetry and the 2x2x2 Cube

Basically, I had used the <U,L,F,D,R,B> model of 40320*2187 = 88179840 positions to do my calculations. I wrote my program to generate lookup tables to convert from those 88179840 positions to 77802*1152 sym-coordinates or 40296*2304 "antisym-coordinates," while also building a reverse-mapping lookup table to map the 77802*1152 sym-coordinates or 40296*2304 antisym-coordinates back to the 88179840 positions. These tables required a whopping 724,087,296 bytes.

The antisymmetry version of the code would take each position x in <U,L,F,D,R,B> and calculate (m^-1xm)c and (m^-1x^-1m)c for all cube rotations c and all cube symmetries m. An alternate version calculated (m^-1xm)c and ((m^-1xm)c)^-1, which also also seemed to work.

After Jerry's response, I went back to look at using <U,R,F> (essentially equivalent to using <U,L,F> as suggested by Jerry). Instead of generating mapping tables in both directions, I simply created a mapping table from the 3674160 positions to the 40296 classes. So for a position x in <U,R,F>, the program would compute (in <U,L,F,D,R,B>-space) all positions of the form (m^-1(xc)m)q and (m^-1(xc)^-1m)q for all cube rotations c and all cube symmetries m, and where q represents the cube rotation required to put the resulting cube back into a <U,R,F> position. All the resulting <U,R,F> positions were mapped to the same class index as x. This process continued with all <U,R,F> positions not yet assigned to a class. So the mapping table in this case was only 14,696,640 bytes. This reduces the storage required, but in applying every cube rotation to the positions in <U,R,F>, it is still essentially reducing from <U,L,F,D,R,B>-space.

Later, I reran the program, except without applying the "q" cube rotation, essentially ignoring all resulting positions not in the <U,R,F>-space. This still produced the same 40296 classes. This reduces execution time, but is still essentially based on reducing from the <U,L,F,D,R,B>-space. It may be possible to simplify this further, but I haven't investigated any further.

Order of the corners of the 3x3x3   88179840
Order of the 2x2x2                   3674160  (24 times reduction)
2x2x2 reduced by symmetry              77802  (47.22 times reduction, about 48 times)

I've been thinking about this a lot and I think I was wrong in my previous post when I implied using cubic symmetry to reduce the 2x2x2 group was invalid. I believe I see how to use full cubic symmetry to reduce the 2x2x2 group in the context of the fixed cubelet model.

One must have a representation which represents all eight cubelets, one of which is designated as the reference cubelet. Let G be the group of all corner permutations using the full set of face turns and H be the subgroup of G generated using only the R,U,F face turns. H then contains all elements of G in which the reference cubelet, the ( l , d , b ) cubelet, is in the unrotated or E state.

An equivalence class may be generated for each element h in H by applying similarity transforms using the elements of the cubic symmetry group:

e_i = c_i^-1 h c_i for all elements, c_i, of the cubic symmetry group.

Now as I pointed out in the previous post the set of elements generated above is not a valid equivalence class because in general the elements generated are not members of H. This is because the similarity transform may move and/or rotate the reference cubelet from the E state. However, since G has cubic symmetry and h is a member of G, the transformed elements will be members of G. Any element of G may be converted to an element of H by applying a whole cube rotation, i.e. the whole cube rotation which will place the reference cubelet in the E state. So, for each element e_i a whole cube rotation must be applied to generate its corresponding element in H. The set of elements thus generated would then constitute the equivalence class--I think.

In order for the above to be valid, the procedure must uniquely define each class. For this to be true it must not matter which element of the class one uses as the basis of the class--submit any member of the class to the above procedure and one will generate the same list of elements. Now I have been confusing myself with left cosets, right cosets, normal subgroups, etc. trying to convince myself this is the case, but I haven't yet. Perhaps someone with more facility with the abstract concepts of group theory than I could look at the above with a critical eye and help me out?

The first cube rotation can be seen as a recolouring, the last cube rotation determines the orientation of the puzzle as a whole. All elements in C g C are deemed equivalent to g itself.

These are easily shown to be equivalence classes.

C c₁ g c₂ C = C g C for any c₁, c₂ in C, and so it doesn't matter which element in the class is used to represent it.

You said:

Let H be the subgroup of G generated using only the R,U,F face turns. An equivalence class may be generated for each element h in H by applying similarity transforms using the elements of the cubic symmetry group:

e_i = c_i^-1 h c_i for all elements, c_i, of the cubic symmetry group.

[...], for each element e_i a whole cube rotation must be applied to generate its corresponding element in H. The set of elements thus generated would then constitute the equivalence class--I think.

You said:

In order for the above to be valid, the procedure must uniquely define each class. For this to be true it must not matter which element of the class one uses as the basis of the class--submit any member of the class to the above procedure and one will generate the same list of elements.

The only remaining question now is, will the number of equivalence classes be the same in these two different formulations.

Given an equivalence class of the second type, C h C intersected with H, it is easy to uniquely construct an eq. class of the first type, namely C h C.

The other direction is only slightly trickier. Given an eq. class of the first type, C g C for some g in G. The reference piece is moved somewhere, but since C is transitive, we can follow it by a cube rotation c such that c g lies in H. From this we can of course construct C (cg) C intersect H, an eq. class of the second type.

So these two formulations of sets of equivalent permutations are themselves equivalent. It is just that in the second formulation you use a smaller group of permutations, resulting in just as many smaller equivalence classes.

Things are not so different if we use use M instead of C, i.e. include the reflections as well. The only difference is that an equivalence class of the first type now becomes M g M intersect G. This is because reflection is not an operation that lies in G itself, just like the cube rotations in C were not in the group H. For M g M intersect G to make sense, we must of course work in a supergroup containing both G and M, for example the group S₂₄.

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

Your analysis is very interesting. I'm trying to get my mind around what you're saying. I think visually. Symbols on paper lose their meaning unless I can visualize it, so bear with me.

You said:
"Let C be the group of rotations of the cube. When reducing the whole group G by cube rotations, we split G into sets C g C, g in G."

Ok, CgC are sets generated by: c_i g c_j for all elements c_i, c_j in C. This is equivalent to c_i (c_j^-1 g c_j). The similarity transform, (c_j^-1 g c_j), generates all the unique ways pattern g may be applied to the cube and c_i are all the whole cube rotations which may be applied to each pattern ( or the different angles from which that pattern may be viewed ).

Now we've been talking about reducing G using the full 48 element cubic symmetry group, what you refer to as M. So we want to look at equivalence classes as MgM intersect G. Restating MgM as I did above for CgC, the constructions of the sets follows:

m_i(m_j^-1 g m_j) for all elements m_i, m_j of M.

The similarity transform: (m_j^-1 g m_j) always generates an element of G--parity rules require that the product of a rotation and a reflection is always a reflection and the product of two reflections is always a rotation. Thus you don't have to worry about the transform producing inside-out cubelets. Reflection preserves twist parity so everything is OK. In order for the whole product to be a member of G, m_i can't be a reflection. That is m_i must be a rotation, an element of C. Thus the sets may be constructed as:

c_i(m_j^-1 g m_j) for all elements c_i of C and m_j of M

So MgM intersect G generates sets containing all the ways a pattern ( and its mirror image ) may be applied to the cube and all the different angles from which each may be viewed. So one may organize the elements of each equivalence set in G into subsets, each subset containing all the ways of viewing a particular result of (m_j^-1 g m_j). Now the procedure I propose for generating equivalence sets in H starts by generating a set by:

(m_j^-1 h m_j) for all elements m_j of M

This is precisely the same as the first part of the procedure for generating the equivalence sets in G. Thus the initially generated set contains one element from each subset of the set in G defined above. By applying a whole cube rotation the element in each subset which is a member of H is determined ( and there must be one since all orientations are included ) and thus becomes an element of the equivalence set in H. OK, good. I've convinced myself that what you say is true. The equivalence sets generated are indeed (MgM intersect G) intersect H.

All your other arguments for completeness etc. seem good. So I think the proposed procedure is sound and will give well formed equivalence sets in the fixed cubelet model.

Thank you. After working through what you said, I think I understand things much better.