Date: 24 Jun 1987 08:54:48 EDT (Wed)
From: Dan Hoey <hoey@nrl-aic.ARPA>
Subject: Lower bounds for the 3^N cubes
To: Cube-Lovers@AI.AI.MIT.EDU
Message-Id: <551537688/hoey@nrl-aic>

The ability to calculate the sizes of large cube groups prompts me to
generalize the lower-bound machinery we have for magic cubes, to see
how it behaves asymptotically.  The machinery we have uses the three
isomorphic Abelian groups A(N) generated by the three sets of parallel
generators for the N^3 cube.  Since the group of the N^3 cube is a
quotient of the free product of three copies of A(N), we can
upper-bound the number of positions close to SOLVED in the cube group
by the number of positions close to SOLVED in the free product.  This
implies a lower bound for the diameter of the cube group.

One useful tool for group diameter work is the Poincare series.  The
Poincare series of a finitely generated group is the power series p(z)
in which the coefficient of z^d is the number of group elements of
length d.  When the group is finite, the power series is a polynomial.
For our analysis, we will need the Poincare polynomial of A(N).

When N is odd, the analysis is straightforward, since A(N) is the
direct product of (N-1) cyclic groups of order 4.  Let S be the set of
generators for A(N), |S| = 2(N-1) including inverses.  Now suppose we
take a subset T of S.  We can construct a group element F(T) by
multiplying the elements of T together, *except* that when both a
generator G and its inverse G' appear in T we replace them with G^2.
It is easy to see that F is a bijection between the power set of S and
the group A(N).  The interesting thing about F is that the length of
F(T) is |T|.  So the number of length-d elements of A(N) is the number
of d-element subsets of S, and the binomial theorem gives us the
Poincare polynomial of A(N):  p(z) = (z+1)^(2(N-1)).

When N is even, we are in considerably murkier waters.  It's easy
enough in the Cutist analysis I presented on 1 June 1982:  There are
N-1 ways of cutting the cube into two pieces perpendicular to each
axis, and so 2(N-1) generators of A(N), and the analysis proceeds as
above.  But a year later I converted to Eccentric Slabism, and I
suppose I should present that analysis here.  In the Slabist
interpretation, the generators of A(N) are the 2N quarter-turns of
unit-thickness slabs.  But to avoid charging for whole-cube moves, we
must single out a particular slab S0 for which a turn is equivalent to
turning each of the other slabs {S1,S2,...,SN} in the opposite
direction.  The Poincare polynomial for A(N) is
        p(z) = ((z+1) (SUM[0<=i<N/2] C(N-1,i) z^i))^2
where C(N,r) is the binomial coefficient.  This can be shown by
constraining T to include fewer than N/2 of {S1,...,SN} and fewer than
N/2 of {S1',...,SN'} in the previous analysis.  Showing that this is a
length-preserving bijection is tricky, and I will spare you the gory
details, barring pleas to the contrary.  Does anyone know of a closed
form for that sum?

In general, the free product of three copies of A(N) has Poincare
series
    q(z) = p(z)/(3 - 2p(z))
where p(z) is the Poincare series of A(N).  The series q(z) can be
expanded term by term using the technique I sent in on 9 January 1981.
As in that message, we add up every other coefficient through that of
z^d to produce an upper bound on the number of positions of the
move-parity of d reachable in d qtw or fewer, and if this is less than
half the size of the group of the cube we have a lower-bound of d+2 qtw
to solve the cube.  I've done this for the cubes up to 10^3, and I get
the following lower bounds.  The traits are as given in my previous
message.

          LOWER BOUNDS ON GOD'S NUMBER FOR N^3 PUZZLES
      Traits
 N     {}     {m}     {i}   {m,i}     {s}   {s,m}   {s,i} {s,m,i}
 2     11
 3     21                              25
 4     37      44      43      50
 5     59      72      74      87      62      74      79      92
 6     81     102     118     145
 7    111     143     174     218     113     146     181     225
 8    138     183     246     316
 9    175     236     334     435     178     238     343     443
10    208     284     439     580

Asymptotically, the coefficients of q(z) grow by a factor approaching
R, where p(1/R) = 3/2.  This allows us to calculate the rate at which
the free product grows.  Here's a table of the smaller values.

    N    R (exact)                   R (approx)

    2    1/((3/2)^(1/2) - 1)          4.449
    3    1/((3/2)^(1/4) - 1)          9.371
    4    6/((4 + 6^(3/2))^(1/2) - 4) 18.519
    5    1/((3/2)^(1/8) - 1)         19.235
    6                                29.047
    7    1/((3/2)^(1/12) - 1)        29.098
    8                                38.960
    9    1/((3/2)^(1/16) - 1)        38.963
   11    1/((3/2)^(1/20) - 1)        48.828 (for even N>=10, use
   13    1/((3/2)^(1/24) - 1)        58.693  approximation for N+1).
   15    1/((3/2)^(1/28) - 1)        68.558
   17    1/((3/2)^(1/32) - 1)        78.423
   19    1/((3/2)^(1/36) - 1)        88.288
   21    1/((3/2)^(1/40) - 1)        98.153

Clearly R grows proportionally to N, so our asymptotic lower bound will
be somewhere around Log[N](G[t](n)), which is O(N^3/log(n)) for the
theoretical invisible groups (trait i) and O(N^2/log(n)) for the
surface groups.  This is as opposed to Eidswick's upper bounds, which
are O(N^3) and O(N^2), respectively.  So the gap increases, but not
terribly quickly.

It is interesting to compare this with the sort of behavior we see in
the 8-puzzle, 15-puzzle, ..., N^2-1-puzzles, as Jim Saxe suggested to
me many years ago.  The N^2-1-puzzle has (N^2)!/2 positions and 2 to 4
possible moves, so the lower bound based on this sort of counting
argument is O(log((N^2)!)) = O(N^2 log N).  Yet we know that we can put
O(N^2) pieces at a distance of O(N) from their home, so God's number
for the puzzle is O(N^3).  It is pleasant to see that our bounds on the
cubes are tight to within a log factor.

Dan