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

distance positions mod 48 0 1 1 18 2 3 3 24 4 39 5 12 6 22 7 12 8 40 9 3 10 4 11 20 12 24 13 36 14 46 15 41 16 39 17 10 18 33 19 11 20 42 >=21 0

## Comment viewing options

### mod 96?

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.

### mod 96

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

### I think it can(not) be done

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:

- 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).
- 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.

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.

### number of self-inverse positions

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

### M p = M p' can be understood

- 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.

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.

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

### Mike Godfrey and I did a comp

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.

### single anti-symmetries only

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

- A is also the set of anti-symmetries of p' and S is also the set of symmetries of p',
- If p = p', then A = S is a subgroup of the 48 symmetries,
- 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.

- 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. - 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.
- 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.

### New kind of symmetry

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

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.

### mirror image

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?!

### Mirror Symmetry

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.

### Your mapping above is the map

_{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' ⇒ FThere 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.

### Conjugate 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'

### Symmetry, Maneuvers, and Syllables

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^{m}L^{m}U^{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.

x^{m}(FLU)^{m}m'(FLU)m m'(F)(L)(U)m m'(F)mm'(L)mm'(U)m (m'Fm)(m'Lm)(m'Um) F^{m}L^{m}U^{m}

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_{1}s_{2}...s_{k}. is a minimal maneuver for the non-syllable x that has been uniquely decomposed into syllables s_{1}, s_{2}, ...s_{k}. Then Symm(x)= Symm(s_{1}) ∩ Symm(s_{2}) ∩ ...Symm(s_{k}) . So non-syllables tend not to have very much symmetry.

## Very nice!

This helps confirm my earlier results for FTM through 13f*, in that at least the modulos are correct.

Now we need to find an eager hand who is willing to calculate the distances for all symmetric positions in the QTM. This will have the side benefit, probably, of finding any "hard" positions in the QTM (only a very few positions are known that take 25 or more moves).

My current count of difficult positions in the QTM is:

26: 1

25: 2

24: 219

If anyone knows of any distance 24 or greater QTM positions, I'd love to hear of them to add them to this database.