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?