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