# Message #1817

From: schuma <mananself@gmail.com>

Subject: [MC4D] Re: God’s Number for n^3 cubes.

Date: Sun, 03 Jul 2011 06:34:41 -0000

Hi Roice,

Today I computed a lower bound for the god’s number of 3^n, using a simple counting argument. And the lower bound is in the order of 3^n. It’s much much lower than our heuristic upper bound 5^n. Currently I don’t know any way to improve the lower bound. So if I have to guess the asymptotics of the god’s number, I have to change my mind to believe that the upper bound 5^n is very loose.

If the god’s number is really ~ 3^n, then the best solution uses only sub-exponential moves per piece to solve all the pieces. It means there’s a huge room for improvement. Maybe the way to go is like in 3^3, Kociemba’s algorithm has nothing to do with 3-cycles but is related to subgroups and cosets.

Nan

— In 4D_Cubing@yahoogroups.com, Roice Nelson <roice3@…> wrote:

>

> I’d like to see results here as well, though it is a very different kind of

> problem than the one Nan proposed.

>

> Since I can’t seem to help myself from making predictions, mine here is that

> things will follow what happened for the 3^3. That is, the lower/upper

> bounds will get squeezed together over an extended time (the upper bound

> requiring more effort) using group theory arguments, but that the group

> theory arguments will run out of steam. cube20.org has a tabular history of

> the 20 year saga to find God’s Number for Rubik’s Cube. Since they had to

> finish off the final gap with computers, which will be impossible for the

> 3^4, the exact answer may literally never be known. Maybe the 2^4 will be

> tractable though.

>

> I don’t recall specific bounds being mathematically defended here before,

> but I may very well have missed them or may be forgetting. Perhaps some

> wiki pages for God’s Algorithm are in order to begin collating what we know.

> We could have separate pages for the asymptotic and low-dimensional

> problems.

>

> Take Care,

> Roice

>

>

> On Fri, Jul 1, 2011 at 4:41 AM, PAUL TIMMONS <paul.timmons@…>wrote:

>

> >

> >

> > How about restricting oneself to God’s algorithm for the 3^4 case? I

> > wanted to get an

> > idea for the likely length of God’s algorithm (both in the QTM and the

> > FTM). There must

> > be some some heuristic results available now that the MC4D has been in use

> > for some years now. Even more so I am interested in any results for the 2^4

> > case in both metrics

> > but in particular the quarter-turn one. Sorry if this information is in

> > circulation elsewhere - too much information to sift through and too little

> > time!

> >

> >

>