From:

Subject:

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,011Ummm. 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?