# Symmetry Reduction of Coset Spaces

Having repeatedly shot myself in the foot by mishandling the symmetry reduction of coset spaces, I finally sat down, laid out the math and put together a set of notes on the matter. These notes follow.

**Coset Spaces**

Solving Rubik's cube either manually or by computer usually involves dealing with coset spaces. A group may be partitioned into cosets of a subgroup of the group:

g * SUB where g is an element of the parent group and SUB is a subgroup of the parent group

Corners first solvers take a scrambled cube to the subgroup of the cube group with solved corner cubies. This subgroup is comprised of all the even parity edge arrangements composed with the identity corner arrangement. A coset of this subgroup is characterized by a particular arrangement of the corner cubies. All members of the coset have the same corner cubie arrangement. Obviously, a turn sequence which will take one coset member to a member of the parent subgroup will take any coset member to a member of the subgroup. One could use this coset space as the basis for an IDA solver pruning table. The table would list the depth of each coset of the solved corners group—that is, the minimum number of turns needed to take a member of the coset to a member of the subgroup.

The effectiveness of such a pruning table increases with the depth of the coset space. The deeper the average depth of the cosets the more effective is the pruning of the search tree. This equates to larger coset spaces based on smaller subgroups. In order fit larger pruning tables into physical memory one eventually must resort to symmetry reduction of the coset space.

For the purposes of this discussion two parent subgroups are considered. The first is the subgroup of the Rubik's cube group with solved edge cubies. This coset space consists of
12! * 2^{11} = 980,995,276,800 cosets, one for each arrangement of the edge cubies. The second is the subgroup of the Rubik's cube group with the Up layer solved. This coset space consists of
(24 * 21 * 18 * 15) * (24 * 22 * 20 * 18) = 25,866,086,400 cosets, one for each arrangement of the Up face cubies. Either of these coset spaces is too large to map into the physical memory of
a personal computer and is a candidate for symmetry reduction.

**Symmetry reduction**

The elements of a symmetry equivalence class, m' g m (where m ranges over the cubic symmetry group and g is an element of the Rubik's cube group), are all at the same depth in the Cayley graph. Find the depth of one and one has found the depth of them all. The conjugates of the elements of a coset are given by:

m' * g * SUB * m

A coset space may be reduced by symmetry only for those symmetry elements for which m' * SUB * m = SUB

m' * g * SUB * m = m' * g * (m * SUB * m') * m = m' * g * m * SUB

The symmetry conjugates of the coset, g * SUB, are contained in the coset, m' * g * m * SUB only if SUB is invariant under conjugation by m.

The fixed edge cubie subgroup described above shows full cubic symmetry and the coset space may be reduced about 48 fold. The fixed Up cubie subgroup on the other hand only shows C4v symmetry. All other symmetries swap Up layer cubies with lower layer cubies and are not useable. Thus this coset space may only be reduced about eight fold.

**Anti-symmetry reduction**

Find the depth of a group element and you have also found the depth its inverse. The inverse of a left coset, g * SUB, is the right coset, SUB * g'. The second coset is composed of the inverses of the elements of the first coset. A coset space may be reduced with anti-symmetry only if the subgroup is a normal subgroup, i.e.

g * SUB = SUB * g

The subgroup of the cube group with all edge cubies solved is a normal subgroup. One may reduce this coset space using anti-symmetry. On the other hand, the subgroup of the cube group with the Up layer solved is not an normal subgroup and anti-symmetry reduction is not valid for this coset space.

To elaborate:

The subgroup of the cube group with solved edge cubies consists of all even parity corner positions composed with the identity edge position. Since a conjugate of an even parity corner position is always an even parity corner position:

g' SUB g = SUB

and thus:

g * SUB = g * g' * SUB * g = SUB * gFor a cube group element g, the left coset is:

g * SUB = < g * s0 , g * s1 , g * s2 … >

For the inverse of g:

g' * SUB = SUB * g' = < s0' * g' , s1' * g' , s2' * g' … > (SUB, being a group, includes the inverses)

Each element of a coset may thus be mapped to its inverse in the antisymmetric coset. So if one solves the coset containing g one knows the results one would obtain for the coset with edge position g'.

On the other hand, the fixed Up cubie subgroup is not a normal subgroup. Since g in general swaps Up layer cubies with lower layer cubies, a conjugate of a lower layer permutation is not always a lower layer permutation.

g' SUB g ≠ SUB

In general the inverses of g * SUB are not contained in the coset g' * SUB and this coset space may not be reduced by antisymmetry.

**In Summary**

Mapping each coset to a byte in memory, the cosets of the fixed edge cubie subgroup may be reduced by the full 96 M+ symmetries to about 10GB, while the cosets of the fixed Up layer subgroup may be reduced by the eight C4v symmetries to about 3.2 GB.