26f now claimed proven sufficient

As Herbert mentioned, there was an error in our original ISSAC '07 publication announcing our proof that 26f suffice for the cube. Specifically, we reduced both levels 12 and 13 of the square subgroup and the level 3 cosets by symmetry, when in fact only one can be reduced for a correct result.

We have since gone back and re-done the computation, this time using the full subgroup (without symmetry reduction). Unfortunately, a few configurations were found that required 15 moves, hence allowing only a reduction of 1 move at coset level 3. Through further analysis, we have performed the same computation at further levels. We finally removed all cases at coset level 9. This required significant additional computation, and the use of the "brute-forcing" method we mention at the end of the paper.

This fix was presented this week at ISSAC '07, and will appear in a later journal version of the paper. We will likely also provide a fixed version of the paper online in the mean time.

Thanks very much to Herbert for his careful reading of our paper, and for bringing this mistake to our attention (among his other very useful comments). Also, thanks to all of the other researchers in this area (some of which Herbert mentioned). Our result would not have been possible without the methods and results that came before.

Best,

-Dan

Congrats for successful proof!
I would love to read the final paper.
(Unfortunately, I'm not a member of ACM)

Good news that you were able to fix the problem! How many additional CPU-time did you need for the necessary new computations?

I thought I would remark that the Kunkle/Cooperman paper has established what I believe is a new "record" for the largest coset space of the cube for which a full God's algorithm calculation has been carried out.

On October 1, 2005, I published on this forum a summary of my God's Algorithm calculation of the permutations of the corners and edges (with respect to fixed centers) in the quarter-turn metric. I believe this is the largest subgroup of the cube for which a God's algorithm calculation has been completed, with 9,656,672,256,000 positions.

The coset space analyzed by Kunkle/Cooperman has 65,182,537,728,000 positions, and thus is 6.75 times larger than the subgroup in my analysis. Interestingly, the paper by Kunkle/Cooperman only lists the number of equivalence classes (symmetrized cosets) at each distance from the trivial coset, but doesn't give a distribution in terms of the actual number of cosets of the squares subgroup.

So to my knowledge, the largest God's algorithm calculations of Rubik's cube sub-spaces in terms of the number of elements are given below. This table does not include analyses of coset spaces that are not closed under a set of basic cube moves, such as done by Rokicki, Radu, and Kociemba. In the table, the numbers under "Symmetries" in parentheses are for symmetry and antisymmetry, regardless of whether or not antisymmetry was used in the calculation.

Sub-space                    Size        Symmetries   Type     Metric   Person(s)   Year
-------------------  ------------------  ----------   ----     ------   ---------   ----
Cosets of squares    65,182,537,728,000    48      coset space   FTM    Kunkle/     2007
subgroup                                                                Cooperman

Permutations of the   9,656,672,256,000    48 (96)  subgroup     QTM    Norskog     2005
corners and edges

Permutations of the   9,656,672,256,000    48 (96)  subgroup     FTM    Norskog     2006
corners and edges

Edges (with centers)    980,995,276,800    48 (96)  subgroup     QTM    Rokicki     2004
subgroup

Edges (with centers)    980,995,276,800    48 (96)  subgroup     FTM    Rokicki     2004
subgroup

My congratulations to Kunkle/Cooperman for achieving this new "record."

I also congratulate Silviu Radu for his 34q upper bound proof.

- Bruce Norskog

In my previous post, I called the permutations of the corners and edges a subgroup of the cube group. The definition of a subgroup (call it H) of another group (call it G) more or less says that H must consist of a subset of elements of G, and that H itself is a group under the group operation of G. However, I view the permutations of the corners and edges "subgroup" as partitioning the elements of the cube group into a set of equivalence classes of size 2048*2187 as opposed to a subset of elements of the cube group. With that viewpoint, it seems to me that it isn't technically a subgroup.

However, I can define the following subgroup of the cube group:
H = < U, D, U' L² U L² U² B' R' U' F U² F' R B L' U', U' R² U R² U² F' L' U' B U² B' L F R' U', L B² R' F² D' R B² L' U' F² R' F² R U', R F² L' B² D' L F² R' U' B² L' B² L U' >
The set of generators for H are equivalent to U, D, L, R, F, and B except that the orientation of all the corners and edges are preserved (using a particular commonly-used convention for corner orientation as well as edge orientation). Thus, each of my equivalence classes contains one of the elements of the above subgroup, and that element can be considered a representative element of the equivalence class. Thus, what I am calling a subgroup of the cube group is at least isomorphic to a subgroup of the cube group. So I think it is reasonable to talk of that "subgroup" as a subgroup. Similar logic can be applied to the edges (with centers) "subgroup."

One of Herbert's comments that I find most interesting has to do with whether or not items (permutations or cosets) that have been reduced by symmetry have to be expanded at any point in the calculations. I have a similar situation in the program I have used to calculate God's algorithm out to 13q and to 11f. Let's take the 13q case as an example, although the 11f case is essentially the same.

In my case, I'm not dealing with cosets. To calculate out to 13q, I store the set of all permutations out to 7q (call it T₇) and the set of all the permutations out to 6q (call it T₆). Then, I form the product T₇T₆, with the products being produced in lexicographical order so as to detect duplicate permutations. (I have posted all this before.)

What I really wanted to do was to deal with T₇ reduced by symmetry and T₆ reduced by symmetry, and I tried mightily to find a way to get it to work. But it just doesn't work, and I think for the same reasons that Herbert cited in the last paragraph of his message.

What I ended up doing was storing T₇ and T₆ reduced by symmetry, and then dynamically exanding each of them roughly 48 times as I was forming the products. (And of course, I really don't have to store T₆ separately from T₇ because T₆ is a subset of T₇.)

I wondered if maybe I could expand T₇ but not T₆ or vice versa. Perhaps I could have done it that way. But what I did instead was to expand both. Then, I found a way to create cutoff points so that not all products are really produced. In fact, the only products that are produced out to 13q are those known to be reduced by symmetry. So I do get a 48 times speedup.

Here is another example of the same principle. Consider the way breadth first searches are usually done. Let's let V_n be the set of permutations that are exactly n moves from Start. In this terminology, T_n is the union of V_i for i from 0 to n. The basic breadth first algorithm that anybody would use is V_i+1=V_iQ in the quarter turn metric, or V_i+1=V_i(Q union H) in the face turn metric. There's some bookkeeping you have to do to avoid counting duplicate positions, but that's the basic algorithm.

Well, what I have all ways done instead is W_i+1=W_iQ or W_i+1=W_i(Q union H), where W_i is V_i reduced by symmetry. Working with W in this fashion, it doesn't have to be re-expanded back to V. It can be used as it. But you can't reduce Q or H by symmetry. They are already expanded, and you just leave them expanded. And with this algorithm also, you get about a 48 times speedup.

The difference in my two algorithms is that in the W_i+1=W_iQ case, nothing has to be expanded, but the products have to be reduced by symmetry after they are formed. And when you reduce the products by symmetry after they are formed, I can't figure out a way to make the products come out in lexicographic order. So this algorithm is only suitable for problems that are small enough to allow storing all results in a table in memory. In the T₇T₆ case, both T₇ and T₆ have to be expanded. But the products are produced in lexicographic order, and hence do not have to be stored at all. Cutoff points are used so that the only products that are produced are the ones that are already reduced by symmetry (about 1/48 of the total, which is why you get about a 48 times speedup).

The bottom line is that if you are forming the product of two sets of items (permutations or cosets) X and Y, then you can reduce X by symmetry or you can reduce Y by symmetry, but you cannot reduce both of them by symmetry.