Thread: "God's Number for n^4 cubes."

=C2=A0=20





I have emails I've been wanting to catch up on starting back with goldilock=
s=E2=80=A6.=C2=A0 Anyhoo, as it turns out, I had already been working on fi=
nding lower bounds using counting arguments WHEN the twist metric is extrem=
ely well defined.=C2=A0=20
(I'm only considering face twists in this email--i.e. (N-1)D face twists.)=
=C2=A0 For example,=20
=C2=A0
QFTM =3D "90 degree twists of faces are allowed and that's it"; =C2=A0
QSTM =3D "90 degree twists of slices" (MC5D)
AAFTM (atomic angle face=E2=80=A6) =3D if it's possible to do a 90-degree f=
ace twist, the equivalent 180 counts as 2 twists;=C2=A0=20
AASTM (atomic angle slice=E2=80=A6) =C2=A0=3D MC4D's counting method. =C2=
=A0
=C2=A0
Surprisingly enough, QFTM on the 3^4 is the one that took the most work.=C2=
=A0 Here's the lower bounds for God's number that I calculate:
=C2=A0
table:=C2=A0=C2=A0=C2=A0 QFTM=C2=A0=C2=A0=C2=A0 FTM
2^4=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 22=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 16
3^4=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 75=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 56
=C2=A0
Although this counting method yields a lower bound of 18 for the 3^3 FTM (w=
here we now know it's 20), the same method for the 2^3 QTM yields a lower b=
ound of 10 where God's number is known to be 14. =C2=A0So 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 y=
ield the full number of attainable states via face twists.=C2=A0 Nonetheles=
s, lower bounds have historically been closer to the actual God's number th=
an the upper bounds, so if you wanted to take a guess at the actual number =
I'd say, go slightly greater than these.=C2=A0=20
=C2=A0
--
Andy
=C2=A0
=C2=A0


From: 4D_Cubing@yahoogroups.com [mailto:4D_Cubing@yahoogroups.com] On Behal=
f 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.
=C2=A0
=C2=A0=20




I'd like to see results here as well, though it is a very different kind of=
problem than the one Nan proposed.

=C2=A0

Since I can't seem to help myself from making=C2=A0predictions, mine here i=
s that things will follow what happened for the 3^3. =C2=A0That is, the low=
er/upper bounds will get squeezed together over an extended time (the upper=
bound requiring more effort) using group theory arguments, but that the gr=
oup theory arguments will run out of steam.=C2=A0 cube20.org has a tabular =
history of the 20 year saga to find God's Number for Rubik's Cube.=C2=A0 Si=
nce they had to finish off the final gap with computers, which will be impo=
ssible for the 3^4, the exact answer may literally never be known. =C2=A0Ma=
ybe the 2^4 will be tractable though.

=C2=A0

I don't recall specific bounds being mathematically defended here before, b=
ut I may very well have missed them or may be forgetting. =C2=A0Perhaps som=
e wiki pages for God's Algorithm are in order to begin collating what we kn=
ow. =C2=A0We could have separate pages for the asymptotic and low-dimension=
al problems.

=C2=A0

Take Care,

Roice


=C2=A0

On Fri, Jul 1, 2011 at 4:41 AM, PAUL TIMMONS =
wrote:

=C2=A0





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 cir=
culation elsewhere - too much information to sift through and too little ti=
me!

=C2=A0







--0-2094008194-1309772239=:17943
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;"> This leads me to the very idle speculati= on that in big O notation that it may take roughly O(n^r) moves to reach every possible position in the QTM where n=3D2 o= r 3 and r is the exponent or number of dimensions. Can anyone corroborate t= his?   Do you have any details re. your methods to derive the lower bounds? A= re these definitve - you will excuse me if I do not take these results at f= ace (no pun intended) value. This will  I am sure be of interest&= nbsp;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:R> px; MARGIN-LEFT: 5px"> From: Andrew Gould <agould@uwm.edu> Subj= ect: [MC4D] RE: God's Number for n^4 cubes. To: 4D_Cubing@yahoogroups.co= m Date: Sunday, 3 July, 2011, 15:33  =20 11pt">I have emails I've been wanting to catch up on starting back with gol= dilocks=E2=80=A6.  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.  11pt">(I'm only considering face twists in this email--i.e. (N-1)D face twi= sts.)  For example, 11pt">  11pt">QFTM =3D "90 degree twists of faces are allowed and that's it";  = ; 11pt">QSTM =3D "90 degree twists of slices" (MC5D) 11pt">AAFTM (atomic angle face=E2=80=A6) =3D if it's possible to do a 90-de= gree face twist, the equivalent 180 counts as 2 twists;  11pt">AASTM (atomic angle slice=E2=80=A6)  =3D MC4D's counting method.=   11pt">  11pt">Surprisingly enough, QFTM on the 3^4 is the one that took the most wo= rk.  Here's the lower bounds for God's number that I calculate:= 11pt">  11pt">table:    QFTM    FTM 11pt">2^4         22  &nb= sp;        16 11pt">3^4         75  &nb= sp;        56 11pt">  11pt">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 l= ower bound of 10 where God's number is known to be 14.  So it's diffic= ult 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.  None= theless, lower bounds have historically been closer to the actual God's num= ber than the upper bounds, so if you wanted to take a guess at the actual n= umber I'd say, go slightly greater than these.  11pt">  11pt">-- 11pt">Andy 11pt">  11pt">  From:SPAN> 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, thou= gh it is a very different kind of problem than the one Nan proposed. <= /DIV>   Since I can't seem to help myself from mak= ing predictions, mine here is that things will follow what happened fo= r 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= .  cube2= 0.org has a tabular history of the 20 year saga to find God's Number fo= r Rubik's Cube.  Since they had to finish off the final gap with compu= ters, 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 mathe= matically 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 or= der 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 TIMMO= NS <ns@btinternet.com" rel=3Dnofollow target=3D_blank ymailto=3D"mailto:paul.ti= mmons@btinternet.com">paul.timmons@btinternet.com> wrote:   dding=3D0> How about restricting oneself to God's alg= orithm for the 3^4 case? I wanted to get an idea for the likely length of God's algori= thm (both in the QTM and the FTM). There must be some some heuristic results available n= ow that the MC4D has been in use for some years now. Even more so I am inte= rested in any results for the 2^4 case in both metrics but in particular the quarter-turn one. So= rry if this information is in circulation elsewhere - too much information = to sift through and too little time!  = =

--0-2094008194-1309772239=:17943--

=20
On Fri, Jul 1, 2011 at 4:41 AM, PAUL TIMMONS =
wrote:
=20
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 cir=
culation elsewhere - too much information to sift through and too little ti=
me!

=20
On Fri, Jul 1, 2011 at 4:41 AM, PAUL TIMMONS =
wrote:
=20
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 cir=
culation elsewhere - too much information to sift through and too little ti=
me!