God's algorithm for FTM mod 48, 2. Try

With 2 hard positions of 25 moves, this means that only the positions that are one move apart from 4-dots superflip have 25 moves. Weird!

Can you compute mod 96 as well? Then you must compute positions for which the inverse is a symmetric variant of the original as well.

This one is self-inverse:
U2 L U' F2 U2 F2 U2 F2 U' L' U2 (11f*)
But this one is not:
L' U2 L R' F2 R' (6f*)

But that computation is maybe too huge.

Yeah, there are many more positions that are congruent to their inverse mod M (that is, M p = M p') than there are positions that have some form of symmetry, and so far no one has come up with a good way to solve them all. I still think Silviu's solution of all symmetrical positions is one of the most amazing and startling developments in computer cubing.

So without some significant further insight, mod 96 is probably not in immediate reach.

Let m be an anti-symmetry of p. If m has order > 2, then there is also a symmetry of p, and we can look up in tables for symmetric cubes what the optimal generator of p is.

So assume m has order <= 2. Then m = m'. Since m'pm = p' be definition of m, we have mpm = p'. Applying m' from the left gives pm = m'p' = (pm)'. So the object is to search for positions p such that pm is self-inverse for some symmetry m of order <= 2.

We first make the positional cube group of 12!*8!/2 positions a factor 48 smaller (the result will be an action of the original cube group). For that purpose, we take a real Hungarian cube and a fake cube. The clean fake cube is the mirror image of the clean Hungarian cube. We preserve that property when we apply face turns on the real cube, so we apply the mirrored face turns on the fake cube. Before starting to turn, we remove the centers of both cubes. Next, we define a position as the set of our two cubes.

Notice that symmetries have no longer an effect when applied from the right. Furthermore, 24 symmetries can be done with face moves (dot interchanges for 12 of the symmetries and F2U2B2L'R'B2D2F2U2LRDB2F2L2R2U' for RL mirroring). A position on our reduced positional cube is called self-inverse if one can make a self-inverse Hungarian positional cube by coloring the centers of one of both cubes (which means that the fake cube will always get another coloring of the centers as what it had before removing the centers).

Take for instance the position L'U2LR'F2R'. This will be RU2R'LF2L on the fake cube. Next, interchanges the front center with the up center and the back center with the down center on the fake cube to get a positional self-inverse Hungarian cube of screwdriver type: the corner and edge parities do not match. More generally, assume that pm is self-inverse. Then pmn is self-inverse as well, where n is the manuever of changing the centers according to m', thus restoring the centers. This means by definition that the reduced positional cube of p is self-inverse as such.

Here follows a strategy:

1. Compute, for all 12!*8!/2/48 reduced positional cube positions, the distance & 2 (QTM) or % 3 (FTM) towards a self-inverse reduced positional cube, and store them in a table. Assuming perfect symmetry reduction, the table will have size 523.908.000 bytes (QTM) or 838.252.800 bytes (FTM).
2. Solve the clean cube, using the above table as prune table. Indeed, if m'pm = p' for an m of order <= 2, then pm is self-inverse, and we find generators g of p with our prune table. Test whether g is anti-symmetric of order <= 2 on the whole cube with orientations.

Lemma. Getting on the bottom of our pruning system, the probability is 0.03 % that we have a generator g that is anti-symmetric of order <= 2 on the whole cube with orientations.

Proof: Assume we find g on the bottom of our prune system. Then by definition of self-inverse for reduced positional cubes, gmn is self-inverse for the positional cube, where m is a symmetry and n is the manuever of changing the centers according to m'. Hence gm is self-inverse for the positional cube. The probability that m has order <= 2 is 5/12. The probability that m flips the corners is 1/2.

For the edges, the probability that they are correct is 1/2 to the power the number of pairs that are interchanged. But with all edges interchanged, the last pair is automatically correct. So the probability is more than 1/32. For the corners, the probability that they are correct is 1/3 to the power the number of cycles in case the symmetry does not flip the corners. But the last cycle is automatically correct. This is (1/3)^7 with 8 cycles. But it is not very likely that there are 8 cycles. No, let us say that there are 6 cycles. Then the probability is 1/243. Actually, the number is larger than 1/137: about 171/867 times smaller than the number below that is estimated by 1/27.

If the symmetry does flip the corners, then the probability that the corner orientation is correct is 1/3 to the power the number of pairs that are interchanged. But the last pair is automatically correct. So the probability is more than 1/27. And 5/12*(1/2*1/32*1/27+1/2*1/32*1/137) = 0.00029.

Edit: L2B'U'BL2F'DF'D'F2 is odd and selfinverse. So let us forget everything about binary prune tables for QTM. It must be always ternary (% 3).

Or one byte per entry: 2 bits for ternary distance and 6 bits for indicating faces that lead to a closer position.

The total number of self-inverse positions (not including the identity) is 170911549183, just a little larger value than the number of symmetric positions, which this thread gave as 164604041664. Of course, these positions and the symmetric positions overlap, and of the self-inverse positions, we would only need to optimally solve 1/48 of the remaining (non-symmetric) positions. But this still does not include the positions such as L' U2 L R' F2 R' that are not self-inverse. I don't know how many of those type of positions there are. But clearly it's a substantial calculation to get to the mod 96 numbers.

The number of self-inverse positions (excluding the identity) or order 2 positions is given at these links.
http://www.jaapsch.net/puzzles/cubic3.htm#p34
http://home.comcast.net/~wdjoyner/agt/cubebook_errata.html

The number of positions such that p = p' is 170911549183, but what about positions that are a self inverse of anyone of their symmetric positions, in other words M p = M p'?

For positions p that are symmetric, just count those that are also anti-symmetric. The non-symmetric anti-symmetric positions is 8A + 12B, of which A are self-inverse, where

• A is the number of self-inverse positions of the cube without a symmetry,
• B is the number of self-inverse positions of the screwdriver cube with even edge flip and non-matching corner and edge position parity, again without symmetry.

See my above post about computing them for some explanation.

EDIT: this cannot be right. It would predict the same number of anti-symmetries for the identity as for central reflection. The problem is corner flip. Yes, you read it right, not corner twist, but corner flip. The central reflection flips all corners. With that, the corners have the right orientation far more often for self-inverse, namely > 1/27 instead of about 1/243. Ouch!

No, the non-symmetric anti-symmetric positions is 4A + 6B + 4C + 6D, of which A are self-inverse, where

• A is the number of self-inverse positions of the cube without a symmetry,
• B is the number of self-inverse positions of the screwdriver cube with even edge flip and also a total corner orientation of zero (modulo the dihedral group of the triangle), non-matching corner and edge position parity, and again without symmetry,
• C is the number of self-inverse positions of the corner-flipped cube without a symmetry,
• D is the number of self-inverse positions of the corner-flipped screwdriver cube with even edge flip and also a total corner orientation of zero (modulo the dihedral group of the triangle), non-matching corner and edge position parity, and again without symmetry.

Apply for instance U'L2UR2D2F2L2R2BRUR'U2B'DR2D2B2. Forget the edges. Notice that this is an anti-symmetric corner tri-swap. Now let the majority of edges decide the color of the faces. Then we have a self-inverse position. If we do count symmetric positions, then we obtain by the below-mentioned thread:

• A < 170.911.549.184
• B < 171.397.817.856
• C < 867.012.574.464
• D < 866.246.275.584

Since it is hard to exclude symmetry in a checklist (and also hardly of use), we need a check table of 10.377.561.055.232 entries. With 48 symmetries and 8 bits per byte, this becomes about 27.024.898.582 bytes (perfect symmetry reduction). So say 32G of RAM. There exist computers with that much of RAM.

Mike Godfrey and I did a complete analysis of all antisymmetric cases here. Especially the number of positions for each possible case is supplied.
But to get a distance table mod 96 it does not suffice to have distance table for these 10 cases. You need the know the distance tables for the number of cubes which *exactly* have a given symmetry/antisymmetry which means we must analyze all possible subgroups. Only for symmetry there are already 32 types of subgroups, including antisymmetry there are much more. If you want to play a bit with the subgroups which do not include the selfinverse antisymmetry, you can check the antisymmetrybox radiobutton on the Symmetry Editor tab in Cube Explorer.

The above thread investigates single anti-symmetries only. One should investigate the whole system of anti-symmetries and symmetries of positions, I think.

First one remark. When you apply a symmetry m with cube explorer, the program rearrange colors to restore the centers. Hence mp = p for positions p. This is however not what you want. For that purpose, I will not rearrange colors after symmetries. But then, the centers get screwed up. Therefore, I will only consider compositions of symmetries and faces turns such that the symmetries add up to the identity. If this is not the case, then I assume a missing symmetry on the left, ok? For compositions without faces turns (thus only symmetries), this will only give the identity, so in this exceptional case, I will not assume a missing symmetry on the left.

Now assume that cpa = dqb for symmetries a,b,c,d and positions p and q. This means by definition that a'pa = b'qb. Applying b' on the right, we obtain a'pab'= b'qbb', which by definition means ba'pab'= q, i.e. p(ab') = q. So if m = ab' and q = p', then pm = p'. This is the identity we are going to investigate.

Lemma 1. Let p be a position, A be the set of anti-symmetries of p (i.e. the set of symmetries m such that pm = p'), and S be the set of symmetries of m (i.e. the set of symmetries m such that pm = p). Then

1. A is also the set of anti-symmetries of p' and S is also the set of symmetries of p',
2. If p = p', then A = S is a subgroup of the 48 symmetries,
3. If p <> p' and A is non-empty, then S is a normal subgroup of index 2 of the subgroup A |_| S (the union of A and S) of the 48 symmetries.

Proof:

1. Assume first that m is a symmetry of p. Then by inverting both sides of m'pm = p', we obtain m'p'm'' = p''. So m is a symmetry of p'. The converse follows by taking p = p', as desired.
   Assume next that m is an anti-symmetry of p. Let k be the order of p. Then k is also the order of p', and m'p'm = m'p(k-1)m = (m'pm)(k-1) = (p')(k-1) = p. So m is an anti-symmetry of p'. The converse follows by taking p = p', as desired.
2. Since p = p', it follows that symmetries and anti-symmetries are the same. Furthermore, it is clear that S is a subgroup of all 48 symmetries.
3. Again, S a subgroup of all 48 symmetries. Let m be any anti-symmetry of p. Then by conjugating m'pm = p' with m, we obtain p = mp'm'. So m' is an anti-symmetry of p as well. It follows that A |_| S is closed under taking inverse. One can easily show that A |_| S is closed under composition, so A |_| S is a subgroup of all 48 symmetries of the cube.
   Let a be another anti-symmetry of p. Then am' is a symmetry of p, so a = am'm is contained in Sm. It follows that A is contained in Sm. On the other hand, let s be a symmetry of p. Then sm is an anti-symmetry of p, so s = smm' is contained in Am'. It follows that S is contained in Am'. By multiplication from the right by m, we obtain that Sm is contained in A. So A = Sm. In particular the sizes of A and S are equal.
   Since S is a subgroup of A |_| S, and A and S are disjoint of the same size, it follows that the index of S as such equals 2. Now subgroups of index two are automagically normal, which completes the proof.

Edit: this lemma has already been implemented in cube explorer.

Thanks!

Conventional symmetry was able to reduce the size of the cube by a factor of almost 48 and your study of antisymmetry reduced it by another factor of almost 2, giving a total of a factor of almost 96...

One might ask if they are any other ways to reduce the real size of the cube? The most important property in my opinion that symmetry and antisymmetry conserve is the depth of a position... Are there any other permutations that conserve the depth of a position? if they do exist, such permutations might be considered as another form of symmetry that can be used to further reduce the real size of the cube...

As an example, if we take a position of depth 8 with an optimal sequence as:

ABCDEFGH

then when we talk about antisymmetry we are talking about the position:

H'G'F'E'D'C'B'A' which we know for sure it has a depth 8 as well.

What about the position A'B'C'D'E'F'G'H'? is it already covered by some symmetry? if yes which one? if no then can this permutation be used to further reduce the real size of the group?

Symmetry reduction is possible because the set of cube face turns is invariant under conjugation by the cubic group symmetry elements:

	m' < F > m = < F >	

where < F > is the set of cube face turns and m is an element of the cubic symmetry group. Conjugate each element of the face turn set with a particular cubic group element and one regenerates the face turn set.

So if one has a product of face turns equal to a cube state

	f1 * f2  . . . * fn = state

conjugation of that state with a symmetry element gives:

	m' ( f1 * f2 . . . * fn. ) m = m' (state) m = state2

	m'( f1 )m * m'( f2 )m . . . * m'( fn )m = state2

Since all the transformed face turns are face turns one generates a second sequence of turns of equal length which gives the transformed cube state, state2. It is simply proved that if the first sequence is of minimum length then the conjugate sequence must be of minimum length.

So if one could think up another transform, say z, such that:

	z' < F > z = < F >

then one could use this to further reduce the Rubik's cube group. If such a transform exists, I cannot imagine what it would be. Your proposed transform doesn't fit the bill. There is no similarity transform which will transform each face turn into its inverse. And appropriately, if one inverts the sense but not the order of the turns one does not necessarily get a minimum length solution for the resulting state. Apply the transform to a solution to the 26 turn state ( superflip composed with C2 dots ):

U U R U U F B' R R U R' L' F B U U B U D' F' B D F' B' D D

and one gets a state soluble in 22 turns:

cube state 1:  U' U' R' U' U' F' B R' R' U' R L F' B' U' U' B' U' D F B' D' F B D' D'
Singmaster: FU LD BU LB FD LF BD RU RB RD RF LU UFR URB UBL ULF DRF DFL DLB DBR
Cube has no symmetry.
Computing optimal solution.
depth 12 completed,             38 nodes,              0 tests
depth 14 completed,          10372 nodes,           1520 tests
depth 16 completed,         590753 nodes,          46700 tests
depth 18 completed,       34604400 nodes,        1331504 tests
depth 20 completed,     2317615217 nodes,       39790136 tests
U U R F' B R L' F U D L U U F' B L L U F' B' R L  (22q*)

Now antisymmetry is different. It is not based on a similarity transform. Antisymmetry reduction is based on a theorem of group theory that states:

	if	A * B = C	then	B' * A' = C'

which is simply proved using the properties of inverses. If one finds a minimum solution to a state, using the above theorem one may derive a minimum solution for the state's inverse.

Thank you for the counterexample.

I am however puzzled as to why that is the case because it seems to me that if I am solving the cube while watching myself in a mirror, then each move I do, my mirror image will do its inverse... So if I reach a state ABCD, my mirror image will reach the state A'B'C'D', how is it possible then that these two states might have two different depths?!

It is not what your mirror image does, but rather what you would do to the mirror image cube. Orient the cube such that you are looking at the front face. On the cube in the mirror the face facing front is the back face. If normally one turns the front face clockwise, one must turn the back face such that it appears to turn clockwise in the mirror image. This maps to a clockwise turn of the back face. Carry this through consistently and one achieves a mirror conjugate of your cube state.

If you watch yourself performing a sequence of turns in a mirror, your mirror image achieves a mirror image of your cube state. This mirror image is not achievable on a real cube.

I think the mirror conjugate can be achieved by the following permutation then:

U<->D'
D<->U'
L<->R'
R<->L'
F<->B'
B<->F'

Is this permutation already covered by some symmetry?

Your mapping above is the mapping produced by conjugating with the inversion operation (rotate the left face to the right position leaving the front to the front. Now perform the turns on the mirror image to form the inversion conjugate). The mapping I describe above produced by a mirror is generated by conjugating with a &sigma_h element:

     U ⇒ U'
     D ⇒ D'
     R ⇒ R'
     L ⇒ L'
     F ⇒ B'
     B ⇒ F'

     U' ⇒ U
     D' ⇒ D
     R' ⇒ R
     L' ⇒ L
     F' ⇒ B
     B' ⇒ F

There are twenty four mirrored cubic group elements: inversion, 3 &sigma_h, 6 &sigma_d, 6 four-fold improper rotations and 8 six-fold improper rotations. Each of these produce a different mapping of the cube turns.

Here are the forty-eight mappings of the cube turns produced by conjugation by the cubic group elements. I have expressed the symmetry elements as a remapping of the coordinate axes. If one has a set of points with cubic symmetry such as the vertexes of a cube ( or the center points of the Rubik cube facelets ) applying any of these geometric transforms to each point will regenerate the set of points: m < cube points > = < cube points > . In reference to the cube, place the origin at the center of the cube with the x axis pointing right, the y axis pointing up and the z axis pointing front. The first entry is the identity element, elements 1 through 12 are the tetrahedral rotation elements, 1 through 24 are the cubic rotational elements and 25 through 48 comprise the mirrored coset of the rotation elements.

 1 { x, y, z} R  R' U  U' F  F' L' L  D' D  B' B 
 2 { x,-y,-z} R  R' D  D' B  B' L' L  U' U  F' F 
 3 {-x, y,-z} L  L' U  U' B  B' R' R  D' D  F' F 
 4 {-x,-y, z} L  L' D  D' F  F' R' R  U' U  B' B 
 5 { y, z, x} U  U' F  F' R  R' D' D  B' B  L' L 
 6 { y,-z,-x} U  U' B  B' L  L' D' D  F' F  R' R 
 7 {-y, z,-x} D  D' F  F' L  L' U' U  B' B  R' R 
 8 {-y,-z, x} D  D' B  B' R  R' U' U  F' F  L' L 
 9 { z, x, y} F  F' R  R' U  U' B' B  L' L  D' D 
10 { z,-x,-y} F  F' L  L' D  D' B' B  R' R  U' U 
11 {-z, x,-y} B  B' R  R' D  D' F' F  L' L  U' U 
12 {-z,-x, y} B  B' L  L' U  U' F' F  R' R  D' D 
13 { x, z,-y} R  R' F  F' D  D' L' L  B' B  U' U 
14 { x,-z, y} R  R' B  B' U  U' L' L  F' F  D' D 
15 {-x, z, y} L  L' F  F' U  U' R' R  B' B  D' D 
16 {-x,-z,-y} L  L' B  B' D  D' R' R  F' F  U' U 
17 { y, x,-z} U  U' R  R' B  B' D' D  L' L  F' F 
18 { y,-x, z} U  U' L  L' F  F' D' D  R' R  B' B 
19 {-y, x, z} D  D' R  R' F  F' U' U  L' L  B' B 
20 {-y,-x,-z} D  D' L  L' B  B' U' U  R' R  F' F 
21 { z, y,-x} F  F' U  U' L  L' B' B  D' D  R' R 
22 { z,-y, x} F  F' D  D' R  R' B' B  U' U  L' L 
23 {-z, y, x} B  B' U  U' R  R' F' F  D' D  L' L 
24 {-z,-y,-x} B  B' D  D' L  L' F' F  U' U  R' R 
25 { x, z, y} R' R  F' F  U' U  L  L' B  B' D  D'
26 { x,-z,-y} R' R  B' B  D' D  L  L' F  F' U  U'
27 {-x, z,-y} L' L  F' F  D' D  R  R' B  B' U  U'
28 {-x,-z, y} L' L  B' B  U' U  R  R' F  F' D  D'
29 { y, x, z} U' U  R' R  F' F  D  D' L  L' B  B'
30 { y,-x,-z} U' U  L' L  B' B  D  D' R  R' F  F'
31 {-y, x,-z} D' D  R' R  B' B  U  U' L  L' F  F'
32 {-y,-x, z} D' D  L' L  F' F  U  U' R  R' B  B'
33 { z, y, x} F' F  U' U  R' R  B  B' D  D' L  L'
34 { z,-y,-x} F' F  D' D  L' L  B  B' U  U' R  R'
35 {-z, y,-x} B' B  U' U  L' L  F  F' D  D' R  R'
36 {-z,-y, x} B' B  D' D  R' R  F  F' U  U' L  L'
37 { x, y,-z} R' R  U' U  B' B  L  L' D  D' F  F'
38 { x,-y, z} R' R  D' D  F' F  L  L' U  U' B  B'
39 {-x, y, z} L' L  U' U  F' F  R  R' D  D' B  B'
40 {-x,-y,-z} L' L  D' D  B' B  R  R' U  U' F  F'
41 { y, z,-x} U' U  F' F  L' L  D  D' B  B' R  R'
42 { y,-z, x} U' U  B' B  R' R  D  D' F  F' L  L'
43 {-y, z, x} D' D  F' F  R' R  U  U' B  B' L  L'
44 {-y,-z,-x} D' D  B' B  L' L  U  U' F  F' R  R'
45 { z, x,-y} F' F  R' R  D' D  B  B' L  L' U  U'
46 { z,-x, y} F' F  L' L  U' U  B  B' R  R' D  D'
47 {-z, x, y} B' B  R' R  U' U  F  F' L  L' D  D'
48 {-z,-x,-y} B' B  L' L  D' D  F  F' R  R' U  U'

Nice table. I'm going to piggy-back some comments about symmetry, maneuvers, and syllables. Some of this information has been posted recently by others, but some of it is new.

As an example, suppose x=FLU and let m be a symmetry of the cube.  Then, x^m=F^mL^mU^m.  The proof is as follows.  Note that each step is reversible so the proof can be read top to bottom or bottom to top.  Also, the proof can be thought of as a template for a completely general proof.  That is, replace FLU by q_{i_1}q_{i_2}...q_{i_n}, and the proof holds for any maneuver whatsoever.  The maneuver does not even have to be minimal.  I'm thinking of q_{i_k} as being an arbitrary quarter turn, but the same concept applies equally well to the face turn metric.

     xm
     (FLU)m
     m'(FLU)m
     m'(F)(L)(U)m
     m'(F)mm'(L)mm'(U)m
     (m'Fm)(m'Lm)(m'Um)
     FmLmUm

As usual, we define Symm(x) to be the set of all symmetries m in M such that x^m=x.  Now, suppose that maneuver for x is minimal and unique.  In this case, conjugation by an element m of Symm(x) must preserve each individual move.  FLU is a maneuver that is minimal and unique, so any m in Symm(FLU) must preserve each of F, L, and U.  Another way to say the same thing is that Symm(FLU) = Symm(F) ∩ Symm(L) ∩ Symm(U) .  As a result, positions that have unique minimal maneuvers tend not to have very much symmetry, and positions with a lot of symmetry tend to have many minimal maneuvers.

Let's look at a couple of positions that do not have unique minimal maneuvers - namely RR=R'R' and RL'=L'R.  In the case of Symm(RR=R'R'), any m in Symm(RR=R'R') may either preserve R and R', or it may exchange them.  Using the numbering system in Bruce's table, we have Symm(R)=Symm(R')={#1,#2,#13,#14}.  But we have Symm(RR=R'R')={#1,#2,#13,#14,#25,#26,#37,#38}.  Which is to say, R and R' are preserved by {#1,#2,#13,#14) and they are exchanged by {#25,#26,#37,#38}.  Similarly, Symm(RL'=L'R)={#1,#2,#13,#14,#27,#28,#39,#40}.  Which is to say, R and L' are preserved by {#1,#2,#13,#14} and they are exchanged by {#27,#28,#39,#40}.

In general, when a position has many, many minimal maneuvers, the symmetry of the maneuvers may not be subject to such a facile analysis.  But what we can say in general is that for any m for which conjugation preserves x, conjugation of the set of minimal maneuvers by m in Symm(x) must preserve the set of minimal maneuvers.

Finally, we consider symmetry as it applies to maneuvers for syllables and non-syllables.  Syllables tend to have many minimal maneuvers and they tend to have a good bit of symmetry.  About the best we can say about the symmetry of maneuvers for syllables in general is the aforementioned statement that for any m for which conjugation preserves x, conjugation of the set of minimal maneuvers by m in Symm(x) must preserve the set of minimal maneuvers.  Of course, the same general statement applies to non-syllables as well.  But for non-syllables we can go one step further.  A non-syllable x may or may not have a unique minimal maneuver in terms of individual moves, but by definition a non-syllable x does have a unique minimal maneuver in terms of syllables that are each shorter than x.  Suppose that x=s₁s₂...s_k.  is a minimal maneuver for the non-syllable x that has been uniquely decomposed into syllables s₁, s₂, ...s_k.  Then Symm(x)= Symm(s₁) ∩ Symm(s₂) ∩ ...Symm(s_k) .  So non-syllables tend not to have very much symmetry.