Message #1812

From: Roice Nelson <roice3@gmail.com>
Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.
Date: Fri, 01 Jul 2011 17:45:12 -0500

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@gmail.com> 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.