GAP cannot solve Rubik's cube 4x4x4 and higher ? (Practical limits of Schreier–Sims algorithm)

Question

According to our practical experiments and literature search - computer algebra system GAP cannot "solve" Rubik's cube 4x4x4 and higher. That means cannot decompose given random element of the permutation group into the product of generators, if the group is large enough - like 10ˆ45 elements - Rubik's cube 4x4x4. (Assuming standard CPU machine with say RAM 32G).

Question 1: Is that correct ? (Or there are some tricks to make it work known to experts) ?

GAP is based on Schreier–Sims algorithm which description of complexity might be sort of confusing - see previous MO discussions collected here: on the one hand it is kind of polynomial complexity, but according to the cited discussions it can produce exponentially long decomposition lengths (it is also explicitly stated in the paper "Planning and learning in permutation groups": "are usually exponentially long").

Question 2: What can be said more precisely about complexity of Schreier–Sims algorithms - not using "O" notation, but giving some precise constant which would correspond to practical implementations in systems like GAP ?

Question 3: How does the polynomial complexity coexist with exponentially long outputs ?

Is it due to the fact that algorithm first creates strong generating set which contains elements of the form like $sˆk$, for very large "k" ? I.e. to compute "k" one needs polynomial, but we should take value of polynomial at $|G|$, not $log|G|$ ? Or there is some other mechanism ?

PS

Here is an example from GAP tutorial to handle the standard 3x3x3 Rubik's cube: https://www.math.rwth-aachen.de/homes/GAP/WWW2/Doc/Examples/rubik.html

Answer 1

No, that is not at all correct. GAP easily can solve $n\times n\times n$ cubes for say $n\leq 50$ (and probably quite a bit beyond).

For $n=4$, the naive permutation degree is $6\cdot4^2=96$. There are no special tricks to make it work. My guess would be that you made a mistake somewhere, but it is hard to say without seeing your code.

The group order is usually not the limiting factor at all. We routinely work with groups much larger than $10^{45}$. The permutation degree and the minimal size of a basis are much more important.

The diameter of the Rubik's cube group for $n=4$ won't be high. My guesstimate would be that a typical random element would have an expression with $<100$, or at least in the order of magnitude. So no problem with any "exponential output size" here.

Maybe what you are thinking about is finding guaranteed shortest decompositions. That is indeed much harder, and not something Schreier-Sims is made for. But that's not at all needed to solve the cube, which is what you are asking about.