From BRYAN@wvnvm.wvnet.edu Sun Aug 21 09:08:01 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03765; Sun, 21 Aug 94 09:08:01 EDT Message-Id: <9408211308.AA03765@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1039; Sun, 21 Aug 94 08:18:30 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5568; Sun, 21 Aug 1994 08:18:30 -0400 X-Acknowledge-To: Date: Sun, 21 Aug 1994 08:18:29 EDT From: "Jerry Bryan" To: "der Mouse" , "Cube Lovers List" Subject: Re: Updated Upper Limits, Q-turns In-Reply-To: Message of 08/21/94 at 06:33:02 from , mouse@collatz.mcrcim.mcgill.edu 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?