The Subgroup Q and its cosets

If we solve all 138,639,780 essentially different H-cosets, we still solve almost all possible cube positions three times. This is because we are able to reduce the number of H-cosets only by D4h symmetries (recall that there are 16 of them), while the symmetry group Oh of the cube has 48 elements. Let's observe what happens if for example we rotate the coset H*R, about the long diagonal containing the corners URF and DLB, by 120 degrees.

H*R =

Rotating this color pattern about the URF-DLB axis we get

and the result after exchanging the colors again so that the colors for the centers are restored is

This does not look like a coset of H any more and indeed it is not! Look at the corners first. Because the white facelets have vanished, the orientations of the corners are now undefined. The positions of the red-green edges have also vanished.

We need to relabel the cube in a different way to be able to retrieve information about H-coset properties when doing some symmetry operations which involve rotations along the long diagonal.

We accomplish this by coloring additional facelets in the H-subgroup color scheme. We let Q be the subgroup corresponding to this new color scheme, and we also denote the corresponding color pattern by Q.

Pattern Q =


Obviously subgroup Q is a proper subgroup of H. The moves U2, D2, R2, F2, L2, B2 do not change the Q-wise relabeled cube. In analogy to the subgroup H one could argue that <U2, D2, R2, F2, L2, B2> generates Q, but this is not true. In this way way you only get a subgroup of index 6 in Q.

Observe that there a two different types of corners, one with the colors white, green and red in clockwise orientation and one with these colors anticlockwise. The positions of each of these types build a tetrahedron, so there are 4!*4! possibilities to exchange the corners without changing the relabeled cube. Analogously there are 4! ways to exchange the red-green edges, 4! ways to exchange the white-green edges, and 4! ways to exchange the white-red edges. Because we can generate only even permutations without disassembling the cube, the subgroup Q has (4!)^5 / 2 = 3,981,312 elements. The index of Q in H is 19,508,428,800 / 3,981,312 = 4900.

It is easy to spot if a cube position is an element of Q. All faces only have only two colors, the center facelet color or the color of the opposite center facelet. Here is an example:

The subgroup Q has all 48 symmetries of the cube. This is why we usually find 48 cosets which are equivalent to each other.

Q*R = , Q*F = , Q*L=,
Q*B = , Q*U = and Q*D =

for example are all equivalent to each other. In this case there are only 6 equivalent cases, because this coset has 8 self-symmetries.

The number of cosets of Q is
|G|/|Q| = 43,252,003,274,489,856,000 / 3,981,312 = 10,863,756,288,000, but we can get a better understanding if we compute this number directly by counting the number of possible color patterns of the relabeled cube.

There are C(12,4) possibilities to set the red-green edges and C(8,4) possibilities to set the white-green edges, and then the white-red edges are forced. There are C(8,4) ways to set the 4 white-green-red anticlockwise oriented corners, and the 4 white-green-red clockwise oriented corners are forced. The corners may be oriented in 3^7 ways and the edges in 2^11 ways. So the total number of cosets of Q is C(12,4) * C(8,4)^2 * 3^7 * 2^11 = 10,863,756,288,000.

When we reduce the number 10,863,756,288,000 of Q-cosets by the 48 symmetries of Oh it can be shown that there are 226,331,259,372 essentially different equivalence classes. This is about 10,863,756,288,000 / 48, but not exactly. It is a bit more because some equivalence classes have less than 48 elements as explained before.

Because Q is a subgroup with index 4900 in H, each H-coset splits into 4900 Q-cosets.
Take for example the H-coset

H*R =

 

If we complete the Q color scheme there are C(8,4) = 70 ways to set the 4 anticlockwise white-green-red corners, for example:

Now there are C(8,4) = 70 ways to set the white-green edges for example:

At this point the 4 white-red edges and the 4 white-green-red clockwise corners are forced. The result is an example of one of the 70*70 Q-cosets which build the H*R-coset.

If we were able to select a subset of the 138,639,780 essentially different H-cosets containing 4900 Q-cosets each so that each of the 226,331,259,372 essentially different Q-cosets (or a coset equivalent with reference to Oh-symmetry) is contained in at least one element of the selected H-cosets, the entire cube space could be essentially solved by solving only this subset of the H-cosets.

This is a typical set cover problem, aside from the fact that the number 138,639,780 of involved sets is too large to find a good solution using available techniques and hardware. We can get around this obstacle if we build unions of H-cosets and deal with a significantly smaller number of sets.

<previous>     <next>