Message #1819
From: PAUL TIMMONS <paul.timmons@btinternet.com>
Subject: Re: [MC4D] RE: God’s Number for n^4 cubes.
Date: Mon, 04 Jul 2011 10:37:19 +0100
This leads me to the very idle speculation that in big O notation that it may take roughly
O(n^r) moves to reach every possible position in the QTM where n=2 or 3 and r is the exponent or number of dimensions. Can anyone corroborate this?
Do you have any details re. your methods to derive the lower bounds? Are these definitve - you will excuse me if I do not take these results at face (no pun intended) value. This will I am sure be of interest to many people on this forum. As Roice has remarked it would be useful to start Wiki’ing up what is known for small r and r->00.
P.S. Perhaps it is just me but the two images attached seemed to be blank. What message were they supposed to convey?
On Sun, 3/7/11, Andrew Gould <agould@uwm.edu> wrote:
From: Andrew Gould <agould@uwm.edu>
Subject: [MC4D] RE: God’s Number for n^4 cubes.
To: 4D_Cubing@yahoogroups.com
Date: Sunday, 3 July, 2011, 15:33
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!