From:

~~~ Subject:

On 9 January 1981, Dan Hoey provided a recursive procedure which

gives the best known upper bound on the number of

cubes at each distance from Start. With Dan's recursive procedure,

the upper bound for any level is a function of the known value or

upper bound for the immediately preceding four levels. Dan's procedure

takes into account identities of the form XX'=I and RL=LR.

At the time Dan performed his calculations, only level 0 through level 4

were known for sure. We now have 8 levels, so Dan's calculations can be

updated. I am going to give the new calculations, and I am also

going to include Dan's original calculations for comparison purposes.

In both tables, P[n] is the number of cubes which are n moves from

Start.

Dan's recursion formula is:

P[n] <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*2*P[n-4]

Dan's calculations:

P[0] = 1 P[9] < 724,477,008 P[18] < 4.048*10^17 P[1] = 12 P[10] < 6.792*10^9 P[19] < 3.795*10^18 P[2] = 114 P[11] < 6.366*10^10 P[20] < 3.557*10^19 P[3] = 1,068 P[12] < 5.967*10^11 P[21] < 3.334*10^20 P[4] = 10,011 P[13] < 5.594*10^12 P[22] < 3.125*10^21 P[5] <= 93,840 P[14] < 5.243*10^13 P[23] < 2.930*10^22 P[6] < 879,624 P[15] < 4.915*10^14 P[24] < 2.746*10^23 P[7] < 8,245,296 P[16] < 4.607*10^15 P[25] < 2.574*10^24 P[8] < 77,288,598 P[17] < 4.319*10^16

New Calculations:

P[0] = 1 P[9] <= 720,627,064 P[18] <= 4.026*10^17 P[1] = 12 P[10] <= 6.755*10^09 P[19] <= 3.774*10^18 P[2] = 114 P[11] <= 6.332*10^10 P[20] <= 3.538*10^19 P[3] = 1,068 P[12] <= 5.935*10^11 P[21] <= 3.316*10^20 P[4] = 10,011 P[13] <= 5.563*10^12 P[22] <= 3.108*10^21 P[5] = 93,840 P[14] <= 5.215*10^13 P[23] <= 2.914*10^22 P[6] = 878,880 P[15] <= 4.888*10^14 P[24] <= 2.731*10^23 P[7] = 8,221,632 P[16] <= 4.582*10^15 P[25] <= 2.560*10^24 P[8] = 76,843,595 P[17] <= 4.295*10^16

I think that the two most interesting things about the new calculations

are: 1) they are nearly the same as the old calculations, and 2) they

are not exactly the same as the old calculations. In both cases, the

question is "why?".

My interpretation is that Dan's analysis not only puts an upper

bound on the number cubes at each level, it also puts an upper bound

on the branching factor. We trivially have an absolute upper limit

on the branching factor of 12. After level 1, we trivially have an

upper limit on the branching factor of 11 (i.e., "don't undo the move

you just made", or "don't have a sequence of the form XX'"). As before,

moves of opposite faces commute. Taking commutations of opposite faces

into account, the branching factor is reduced (empirically ) to an upper

limit of about 9.37.

This empirical analysis is starting with a high branching factor and

subtracting out the cubes we should not count, so that we are

dealing with identities of the form XX' and commutations of the form

RL=LR separately. Dan's analysis deals with cubes we *should* count,

and he thereby deals with identities of the form XX' and commutations

of the form RL=LR in one fell swoop.

But Dan's analysis does not yield exact figures, only limits. It seems

therefore that there must be other cases our empirical approach must

choose not to count. What might those other cases be? It seems that

there must be cases where a sequence X1 X2 ... Xn

is equal to a sequence Y1 Y2 ... Ym, but where there is no obvious

way to characterize the relationship between two sequences (e.g., they

are not simple commutations of each other), and where we cannot even

find the sequences without some sort of exhaustive search.

I would interpret that fact that the new upper limits do not equal the

old upper limits as meaning that such "duplicate" sequences do exist

close to Start. I would interpret the fact that the new upper limits

are close to the old upper limits as meaning that there are not very

many such "duplicate" sequences close to Start.

But consider another quote from Dan in the same article:

The recurrence on which this bound relies is due to the

relations F^4 = FBF'B' = I (and their M-conjugates.) It may be

possible to improve the recurrence by recognizing other short

relations. Exhaustive search has shown that there are none of

length less than 10.

I am afraid I need Dan to explain this further. Dan's logic seems

impeccable. But on the other hand

there must be cases where X1 X2 ... Xn = Y1 Y2 ... Ym, where

the sum of the length of the sequences is less than 10, and where

the equality is not explained by the relations F^4 = FBF'B' = I.

Otherwise, Dan's calculations would yield exact values rather than

upper limits close to Start, and the "new calculations" for upper

limits would equal the "old calculations".

Let me think out loud just for a second. Consider relations such as

LRLRLRLR = I or RR'RR'RR'RR' = I. These are *sequences* of length 8

but *cubes* of length 0. Is it possible that such sequences are being

counted too many or not enough times when the recursion is four

levels deep?

Finally, I have argued on purely empirical grounds that the branching

factor will remain relatively constant from about level 3 to some

unknown level (maybe about level 18 or 19 or 20?), where the branching

factor will decay rapidly because you run out of cubes. Well, I think

I want to argue further that during this "relatively constant" portion

of the distribution the branching factor *will* decay. It might not

decay very much, and I don't see any easy way to calculate how much

it will decay. The argument is very simple. Any time a "duplicate

sequence" occurs, it reduces the branching factor at that level, but

also at subsequent levels. That is, longer sequences can contain the

"duplicate sequence" as a sub-sequence. Hence, any decay in the branching

factor at one level is propagated to all subsequent levels.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU

If you don't have time to do it right today, what makes you think you are

going to have time to do it over again tomorrow?