From:

~~~ ~~~ Subject:

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