Message #1811

From: schuma <mananself@gmail.com>
Subject: Re: God’s Number for n^3 cubes.
Date: Fri, 01 Jul 2011 20:31:09 -0000

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.

— In 4D_Cubing@yahoogroups.com, Roice Nelson <roice3@…> wrote:
>
> Small typo correction in the second to last bullet about parallelizing… I
> meant to write *O(3^n)* pieces will move during a twist. I seem to have
> trouble with accidentally reversing this notation some times :S
>
> Roice