# Message #1813

From: schuma <mananself@gmail.com>

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

Date: Fri, 01 Jul 2011 23:20:01 -0000

Yes the ability of parallelization is hard to specify. It’s also the key contribution of Demaine’s paper.

An interesting interpretation of my calculation is as follows. The (2/3)n-color pieces are the most, but the number of moves per piece is not the greatest. The n-color pieces requires the most number of moves per piece, but there’re not too many of them. So there’s a balancing point between them, in terms of the total number of moves. That balancing point is (4/5)n-color pieces. Those are the hardest part.

If one is using macro to solve it and has recorded a 3-cycle macro for each type of pieces, the solving time is proportional to the number of pieces rather than the total number of moves. In that case (2/3)n-color pieces are the major difficulty.

Nan

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

>

> Great stuff Nan!

>

> I experimentally observed last night that there was a maximum at

> (2/3*n)-color pieces, but my intuition was still telling me it wouldn’t

> dominate (that a smearing of pieces would continue to contribute). Love it

> when my intuition gets put in it’s place :D

>

> Here are piece count graphs I had made for

> 250<http://www.gravitation3d.com/mc4d/god/250-d_piece_counts.png>and

> 500 <http://www.gravitation3d.com/mc4d/god/500-d_piece_counts.png>dimensional

> Rubik’s Cubes (I started overflowing double precision in the

> 600s). The cubie-count peak you calculated at 2/3rds is easy to see. The

> curve is wider on the latter in an absolute sense, spanning some 70

> significant piece types rather than 50. But as a proportion of the total

> number of piece types, I see now it is still getting thinner. So as

> dimension -> infinity, one can think about how this smooth peak approaches a

> spike!

>

> I love that you threw a conjecture out there too. All your reasoning looks

> great, and the only biggish question for me right now is the

> parallelization, and whether that could be leveraged to lower the base of

> the exponent. I’m going to go out on a limb and say it’s possible. After

> your analysis, it feels more tractable to investigate too, because we only

> need to parallelize one piece type.

>

> One thought on that is not using 3-cycles. Say you could generate a

> sequence that cycles a much larger number of pieces. You do preliminary

> moves to put a bunch of pieces in the correct place in this cycle, run it,

> then undo the preliminaries. I used this tactic with a 7-cycle of 3C pieces

> on MC4D (in my glory days, when I used to still be in the running for

> shortest solutions). Maybe cycles of exponential length are even possible

> to take advantage of, since there are an exponential number of pieces to be

> solved. I’ll think on this stuff more.

>

> seeya,

> Roice

>

> On Fri, Jul 1, 2011 at 3:31 PM, schuma <mananself@…> wrote:

>

> > Hi Roice,

> >

> > Here’s my calculation based on your suggestion:

> >

> > (1) The number of k-color pieces on a 3^n is 2^k*(n choose k). [footnote 1]

> > In terms of the number, (2/3*n)-color pieces are dominating. [footnote 2]

> >

> > (2) I think your proposal of using 2^k moves to solve a k-color piece is

> > good, because it basically means one can use a nested commutator with k

> > layers to

> >

> > construct a pure 3-cycle for a kC piece. This coincide with my intuition. I

> > wonder if the MC7D solvers have more insights. Andrey and Charlie, how do

> > you

> >

> > guys solve the 7D pieces?

> >

> > (3) Let’s assume we solve one piece at a time, with no parallelization.

> > Actually, if one can do parallelization, but cannot achieve an exponential

> > gain

> >

> > (solve a^n pieces at the same time for some constant a), it still cannot

> > affect the big picture.

> >

> > Combine all these points, an estimate of the move count for solving a 3^n

> > is about:

> >

> > summation_{k=0…n} 2^k * 2^k * (n choose k) = 5^n

> >

> > In this summation, there’s actually a dominating term: k = 0.8n [footnote

> > 3]. Solving the (0.8n)C pieces takes the most moves, which is about 5^n

> > divided by

> >

> > a polynomial of n, which is essentially 5^n (note that I only care about

> > the base of the exponential function). This estimate is tighter than a quick

> > upper

> >

> > bound of 6^n, which can be obtained by noticing there are no more than 3^n

> > pieces, each can be solved by no more than 2^n moves.

> >

> > My conjecture is that one cannot improve the base of the exponential

> > function, e.g., reduce 5^n to 4.9^n. A rigorous statement would be:

> >

> > Conjecture: For any epsilon>0, there exists N>0, so that for all n>N, the

> > god’s number of 3^n is between (5-epsilon)^n and (5+epsilon)^n.

> >

> > Nan

> >

> >

> > Footnote:

> > [1]: ref: <http://en.wikipedia.org/wiki/Hypercube#Elements>. Note that the

> > m-dimensional boundary has (n-m) colors.

> > [2]: Use the same method as in [3].

> > [3]: Why k=0.8n dominates the number of moves:

> > Take the estimate (n choose k) is approximately 2^(n* h(k/n)), where h() is

> > the binary entropy function

> >

> > <http://en.wikipedia.org/wiki/Binary_entropy_function>. The summation

> > becomes:

> >

> > summation_{k=0…n} 2^(n* (2k/n + h(k/n)) )

> >

> > When n is large, what’s important is the exponent. There’s a dominating

> > term in the summation, that is exponentially greater than all other terms.

> > Since the

> >

> > function (2k/n + h(k/n) reaches it’s maximum log5/log2 at k/n = 0.8, the

> > (0.8n)-color pieces take most of the moves. The single term of k=0.8n

> >

> > One can use the same technique to see why (2/3*n) pieces dominate the

> > number of pieces.

>