On 08/21/94 at 06:33:02 der Mouse said:
>> 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[1]  =          12
P[2]  =         114
P[3]  =       1,068
P[4]  =      10,011

Ummm.  4*2*P[4-1] + 6*2*P[4-2] + 4*2*P[4-3] + 1*2*P[4-4] =
       4*2*1068 + 6*2*114 + 4*2*12 + 1*2*1 = 10010 < P[4].

What have I missed? Is Dan's formula not valid until n=5 or something?

der Mouse

I had just noticed the same thing, and intended to investigate. I don't
know what happens to Dan's formula for n=4.

At the time Dan's chart was first published, P[n] was only known
for sure for n = 0..4. Dan showed strict equality for these
levels, and I assume P[4] came from the known values rather than
from the formula. It still does not explain why the formula
yields a value which is too low for P[4] -- I could easier
understand why it yielded a value which is too high, but it seems
to me that it ought to yield the exact value that close to Start.

For P[5], Dan's original chart showed "=<". Subsequent computer
search changed this to strict equality, which is a great victory
for Dans' formula. The first term for which
Dan's chart is too high is P[6]. I had therefore intended to
start my investigations at that point until I discovered the
discrepancy at P[4].

Just as a reality check, let me mention some trivial points. Suppose
it is discovered that (X1 X2 ... Xn) = (Y1 Y2 ... Ym). Define
X = (X1 X2 ... Xn) and Y = (Y1 Y2 ... Ym). Since X = Y, it is
immediate that XY' = Y'X = X'Y = YX' = I. Conversely, a sequence
(X1 X2 ... Xn) = I can be decomposed into X = (X1 X2 ... Xk) and
Y = (X[k+1] ... Xn). Then, XY = I and hence X and Y' (and also
X' and Y) are what I have called "duplicate sequences", that is
different sequences which yield the same cube. This is why
identities are so important for bounding P[n].

I seem to do everything backwards, so I would just look for the duplicate
sequences. However, it is probably more elegant to look for the identities.
Dan's original note said that computer
search has shown that there are not any identities other than the ones we
already know about up through length 10. It looks to me like Dan's
formula takes care of the identities we already know about. So
as usual, I am probably missing something obvious.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
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?