Message #1818

From: Andrew Gould <agould@uwm.edu>
Subject: RE: God’s Number for n^4 cubes.
Date: Sun, 03 Jul 2011 09:33:54 -0500

I have emails I’ve been wanting to catch up on starting back with
goldilocks.. Anyhoo, as it turns out, I had already been working on finding
lower bounds using counting arguments WHEN the twist metric is extremely
well defined.

(I’m only considering face twists in this email–i.e. (N-1)D face twists.)
For example,

QFTM = "90 degree twists of faces are allowed and that’s it";

QSTM = "90 degree twists of slices" (MC5D)

AAFTM (atomic angle face.) = if it’s possible to do a 90-degree face twist,
the equivalent 180 counts as 2 twists;

AASTM (atomic angle slice.) = MC4D’s counting method.

Surprisingly enough, QFTM on the 3^4 is the one that took the most work.
Here’s the lower bounds for God’s number that I calculate:

table: QFTM FTM

2^4 22 16

3^4 75 56

Although this counting method yields a lower bound of 18 for the 3^3 FTM
(where we now know it’s 20), the same method for the 2^3 QTM yields a lower
bound of 10 where God’s number is known to be 14. So it’s difficult to say
how decent these bounds are–especially when we don’t know (and can’t
compare) God’s number for any 4D (or higher) cube with twist metrics that
yield the full number of attainable states via face twists. Nonetheless,
lower bounds have historically been closer to the actual God’s number than
the upper bounds, so if you wanted to take a guess at the actual number I’d
say, go slightly greater than these.

–

Andy

From: 4D_Cubing@yahoogroups.com [mailto:4D_Cubing@yahoogroups.com] On Behalf
Of Roice Nelson
Sent: Friday, July 01, 2011 19:54
To: 4D_Cubing@yahoogroups.com
Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.

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@btinternet.com>
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!