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!
> >
> >
>