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.
