Lower bound using the Edges antipode

I just found out that Tom has already proved that X=22 here:
http://cubezzz.homelinux.org/drupal/?q=node/view/44

It is the fourth calculation.

This means that each cube position can either choose to go to the edges identity or to the edges antipode then add 22 to go to the cube identity.

Each cube position has to find out which is the closest to it, the edges identity or the edges antipode. That way we avoid adding 18 but only add a number Y between 9 and 17.

This gives an upper bound of 39 but I hope that Y is less than 13 to break the 35q limit...

I have done a test run of a preliminary version of my program for generating the two-dimensional table for the edges group, giving distance from solved vs. distance from the antipode. This program only looked at even permutation positions, and obtained results for about 730,000 positions (unique with respect to M-symmetry). Assuming it was working correctly, it found many positions that are at least distance 14 from both the solved position and the antipode. In fact it was a little over 32% of the positions.

This should not be surprising. If you look at the distance table for the edges group (QTM), you see that about 56.6% of the even permutation positions are depth 14. Since that is a majority of even permutation positions, at least some of them must also be a distance of 14 from the antipode. You could estimate that 56.6% of the distance-14 positions would also be a distance of 14 from the antipode. In fact, 56.6% of 56.6% is about 32%, in close agreement with my sample.

For odd permutation positions, over 90% are depth 13. Therefore, it would be expected that about 81% of the positions are a distance of 13 from both the solved position and the antipode.

To get a smaller upper bound for Rubik's cube in QTM, it was hoped that every position of the edges group would be within 12 quarter turns from either the solved position or the antipode. However, it is clear to me that there are a very large number of positions for which this is not the case.

- Bruce Norskog

Hi Bruce,

Thank you for your calculation.

Well, I am disapointed at the result but all hope is not lost after reading this from Jerry Brayn and the reply from Dan Hoey here:
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Jerry_Bryan__Some_Additional_Distances_in_the_Edge_Group.html

It gave me the idea of looking for a 4D distribution instead of the 2D distribution you calculated. The 4D distribution would be the distance from the identity (I), the pons asinorum (P), the superflip (E) and the pons asinorum+superflip (PE). So that each cube position would have a choice of 4 routes whichever is closest to it...

The cosets corresponding to this 4 positions have all been calculated by Tom Rokiki here:
http://cubezzz.homelinux.org/drupal/?q=node/view/44

and they can all be solved in 22 moves except 5 positions [up to symmetry] in the superflip coset which need 24 moves. However those 5 positions might be searched exhaustively to prove that they can be avoided all the time.

With 4 routes to choose from for each cube position we might have a better chance to have a distance < 13.

Thinking however about your argument about the 90% at depth 13 and how that would make you expect about 81% at distance of 13 from both the solved edges and the antipode edges, I came to realize that even with 4 routes to choose from I would still expect 65% to be at distance of 13 from all of the 4 starting points...

If 4 routes are not enough then let's add more. The H-symmetric positions at Mike's website http://www.math.ucf.edu/~reid/Rubik/h_symmetric.html seem to be good condidates for such an attempt.

So instead of 4 routes I would have 24 routes to choose from... If this does not lower Y to under 13 I do not know what else does!;)

One thing is sure is that the more "independent" [Do not ask me what I mean by independent because I do not know] routes we add, the more better chance we have of lowering Y...


To conduct such a culculation, I need to create 20 [actually only 8 thanks to symmetry] more tables, similar to what Tom Rokiki did for the 4 points [I,E,P,EP]. If Tom Rokiki is reading this, I would be very grateful if you can share your code with which you did the 44millions calculation.

I would also need to produce a 24D distribution similar to what you did for the 2D distribution. If you can share with me your code I will also be very garteful.

Jerry Brayn says here
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Jerry_Bryan__Some_Additional_Distances_in_the_Edge_Group.html

that if you already know the 1D distribution from Start then you can find the distance of any position to a different position that has some symmetry relation to Start thanks to conjugacy... I did not fully understand his argument but it sounds like the 24D distribution I am looking for can be deducted from the 1D distribution somehow...

Thanks a lot!

I was using that idea to calculate my distance table.

Let x be a position in the edge group. Let Z be the antipode. Then x'*Z takes x to the antipode Z. So you just look up the position x'*Z in the edge group distance table to get the distance from x to Z.

I generated the distance table for the edge group in December 2005, to provide independent verification of Rokicki's result. I used that data to do my calculation. Since my data table is over to 18GB (with 1GB defined as 1000^3 bytes), I only loaded a small portion of it into memory. My data consists of 76 files for even permutations and 76 files for odd permutations. So I loaded 6 of the even permutation files into memory. Then I looked for positions from a subset of this space for which x'*Z was also in the space. This avoided the need to perform a random-access disk file lookup to get the distance of x'*Z. By limiting the amount of positions it tried, it only took a few minutes to run and get results for over 700,000 positions.

I figured this idea could be extended to generate the whole 2-dimensional table. This would not extend well to looking up distances to a set of 24 positions, since it is very unlikely to have all 24 computed positions to be within the subset of the table loaded into memory. Perhaps performing random access disk file lookup would be what you would have to do, but that might be very slow because of the total number of positions being so large.

Of course, an actual 24-dimensional table would not be practical to generate. For each position, you would probably want to just find the distance to the closest of the 24 positions. Or even simpler, just get the distance to each of the 24 positions until you find one that's less than or equal to 12, if you're satisfied with merely getting that result.

I further note that the 24 H-symmetric positions (which include the four M-symmetric positions) on Reid's site are cube group positions, not edge group positions. I believe these correspond to only 8 different positions within the edge group (two 6H positions and two 6H+Superflip positions, in addition to the four M-symmetric positions). I think it is rather questionable if 8 edge group positions would be enough. I also note that just over one-fourth of the edge group positions are 12q or less from the solved position, so it would take a minimum of four fixed positions to have any chance of having every edge group position to be within 12q of at least one of the fixed positions, assuming very little overlap in "coverage" by each of the four fixed positions. I believe generally you will have rather significant overlap in the positions "covered" by any pair of the fixed positions.

Hi Bruce,

Thank you for your reply.

Let me know if I can help generating this 2D QTM distribution. I do have time and computer resources unfortunatly I am lacking a good code that will not take ages to produce this full distribution.

If we prove that X is equal to 22 (I am working on this using Mike's optimal solver) and if turns out that Y is less than 13 then a new lower bound can be reached hopefully.

Thanks