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