From:

~~~ Subject:

Jerry Bryan was looking at some formulas I had in the archives:

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]...

I just rechecked Dan's original note of 9 January 1981. He

specifically says the formula is good for n > 4. Mea culpa.

However, I still do not fully understand *why* this should be the

case.

I thought I put the bound in.... I've been meaning to look that up

and explain it, but time's been short.

The analysis is done by breaking up the minimal processes into

"syllables", where a syllable is a maximal sequence of commuting turns.

So for each pair (x,y) in {(F,B),(T,D),(L,R)} there are

four syllables of length 1: x, x', y, and y';

six syllables of length 2: xx, xy, xy', x'y, x'y', and yy;

four syllables of length 3: xxy, xxy', xyy, and x'yy;

one syllable of length 4: xxyy.

(It's not really a coincidence that this is most of the fifth line of

Pascal's triangle.)

Now for the first syllable, we can pick any of the three pairs for

(x,y). But for succeeding syllables, we must pick a pair that is not

equal to the preceding pair. So each term in the recurrence refers to

the length of the last syllable:

Length of last syllable=1 2 3 4

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

The second part of each coefficient is 2, except that when the length

of the last syllable is equal to n (so that we are counting the first

syllable), the second part of the coefficient is 3.

In response to my description:

> >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.

Jerry continues:

> ... 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".

No. The bounds fail to be exact when we have a relation r=s with

|r|=|s|=n. This corresponds to a relation r s'=I of length 2n. The

shortest relations of length >4 are the ones of length 12 (as I

reported on 22 March 1981) so my bounds become inexact at length 6.

Chris Worrell listed the length-12 relations on 08/02/81, and I

reported that his list was complete on 14 August 1981 0111-EDT. The

12-qtw identities (up to M-conjugacy) are:

I12-1 FR' F'R UF' U'F RU' R'U I12-2 FR' F'R UF' F'L FL' U'F I12-3 FR' F'R UF' UL' U'L FU'

As Allan C. Wechsler noted on 17 August 1981, any two of them can be

combined to form the third.

Consider relations such as LRLRLRLR = I or RR'RR'RR'RR' = I.

The first is a consequence of the relations L^4=R^4=LRL'R'=I. The

second is a consequence of group theory; no relations are needed. The

recurrence deals with these: it models the freeest group specified by

the given relations.

I have tried unsuccessfully to create a recurrence that will deal with

the 12-qtw identities, but it's complicated. For instance, repeatedly

putting I12-1 in the center of another I12-1 yields identities of the

form:

F (R'F' RU)^n F'U' (FR U'R')^n U

There are a bunch of other cases, too.

Dan

Hoey@AIC.NRL.Navy.Mil