# Lower bound for Megaminx in htm and qtm



## Herbert Kociemba (Mar 1, 2012)

I analyzed the number of generic move sequences to get lower bounds for God's number of Megaminx, taking into account the commutativity of moves. There are a lot of commutating moves because of the many disjoint faces of Megaminx. In htm, I found a lower bound of 45 moves and in qtm a lower bound of 55 moves. 

I posted the details here:

http://cubezzz.dyndns.org/drupal/?q=node/view/328


----------



## qqwref (Mar 1, 2012)

I made a somewhat similar recursion a while back and ended up with, I think, 43 moves for the Megaminx. I'm not sure exactly where our techniques differ, but I do like this technique in general, as you can get some pretty nice results without a huge amount of work.


----------



## Herbert Kociemba (Mar 1, 2012)

qqwref said:


> I made a somewhat similar recursion a while back and ended up with, I think, 43 moves for the Megaminx. I'm not sure exactly where our techniques differ, but I do like this technique in general, as you can get some pretty nice results without a huge amount of work.


 
I assume, the techniques differ somehow, because the difference between 43 und 45 means that you have more than 1000 times the number of move sequences with 45 moves.
I would be really pleased, if 
1. Someone could double check, that there are 25 unordered pairs of faces (X,Y), which have no pieces in common and either X or Y (or both) have pieces in common with some arbitrary different fixed face,e.g. U.
2. The same for 15 unordered triples (X,Y,Z), which have no pieces in common and either X or Y or Z have pieces in common with another different face, for example the U face.
3. Compute the true number of positions of Megaminx out to some depth in htm and qtm to check if the numbers are the same for the first ??? depths. This depends on the length of the shortest nontrivial identity. Btw, What is the shortest nontrivial identity on Megaminx?


----------



## Lucas Garron (Mar 1, 2012)

Herbert Kociemba said:


> What is the shortest nontrivial identity on Megaminx?



At most 10 moves. FRU'R'U2F'L'ULU2' works on Megaminx.


----------



## TMOY (Mar 1, 2012)

The niklas done the wrong way (L' U R U' L U R' U') is a 8-move identity.


----------



## Herbert Kociemba (Aug 18, 2016)

In a private communication Tomas Rokicki pointed out recently that my argumentation concerning the commutating moves is too weak. Indeed not all commutative moves are taken into account in my argumentation and the lower bound 45 can be improved to 48 moves.
http://twistypuzzles.com/~sandy/forum/viewtopic.php?f=1&t=26168
shows an algorithm which gives the correct numbers.

Using the key idea given here - keeping track of the "recently used moves" - I found a pencil and paper method to compute the number of canonical sequences for each depth. If there is more than one recently used move these moves have to commute pairwise.
There are only 5 different types of "recently used moves":
0. No recently used move (this happens only at depth 0)
1. One recently used move
2. Two recently used moves. There are 2 types for this case. The two moves are opposite to each other or they are not opposite and do not share any cubies (else they would not commute).
3. Three recently used moves. Essentially there is only one case for three axes such that the moves commute pairwise.

Let us name the number of maneuvers of depth n which end with 0, 1, 2 or three recently used moves with a0(n), a1(n), a2a(n), a2b(n) and a3(n).
For depth 0 we have
a0(0) = 1, a1(0) = 0, a2a(0) = 0, a2b(0) = 0, a3(0) = 0

Analysing what happens when you append one move you find for n>=0:

a0(n+1) = 0
a1(n+1) = 4*(12*a0(n) + 5*a1(n) + 2*a2a(n))
a2a(n+1) = 4*(5*a1(n) + 4*a2a(n) + 10*a2b(n) + 3*a3(n))/2
a2b(n+1) = 4*(1*a1(n) + 2*a2a(n) + 3*a3(n))/2
a3(n+1) = 4*(2*a2a(n) + 3*a3(n))/3

The factor 4 takes into account that there are 4 possible moves for each axis, dividing by 2 or 3 takes into account that for commutative moves we only count a fraction of the possibilites.

The total number total (n) of canonical sequences of depth n then is given by

total(n) = a0(n)+a1(n)+a2a(n)+a2b(n)+a3(n) which gives

1, 48, 1536, 43520, 1182720, 31641600, 841318400, 22315008000, 591298560000, 15661924352000,....

Tom also gave me the number of true positions for each depth which is

1, 48, 1536, 43520, 1180800, 31471080,.....
which shows that all canonical sequences up to depth 3 give different positions.

I also found a simple linear recurrence for the number of canonical sequences for the megaminx which I think is really surprising

total(n+1) = 36 total(n) -240 total(n-1) -320 total(n-2), n>=3 and total(1)= 48, total(2) = 1536 and total(3) =43520.

This easily gives the lower bound of 48 moves. That this is the same number as the number of depth 1 maneuvers is coincidence. The same coicidence happens btw. for Rubik's cube, where the number of depth 1 maneuvers and the lower bound are both 18...

The asymtotic branching factor is the greatest zero of the corresponding characteristic polynomial x^3-(36 x^2-240x-320) which is about 26.4803 .

The above holds for HTM. I do not see how to give an easy similar argumentation for QTM.


----------

