Date: Thu, 04 Mar 1999 08:37:14 -0800

[...]  Here is a proof that indeed there is no
b>2, such that (b,2b) contains a complete prime pattern:

Assume you have a complete prime pattern. Then
consider the shift cycle containing the state (x-)^b
(see remark at the end). It consists of two states, the other 
one being (-x)^b. Thus, the only possible entry (exit) point 
of this shift cycle is (x-)^b.

First you can show that the predecessor of (x-)^b is
x-(-x)^{b-1}: It has to be of the form 
x-A. Now the only possibility to reach a state starting 
with x from x-A is to throw a 1. Hence A=(-x)^{b-1}.

Similarly, the only successor of (x-)^b is (-x)^{b-1}x-:
It has to be of the form Bx-. Hence you have to throw a
h-1 implying B=(-x)^{b-1}. 

Hence we showed that you enter the shift cycle in question
from x-(-x)^{b-1} and the following shift cycle contains
(-x)^{b-1}x-. But these two states belong to the same
shift cycle. Hence, the graph (b,2b) contains two 
shift cycles, only. But the only cases where this holds
are b=1 and b=2. qed

Remark: The term (x-)^b means (mathematically) the b-th power
of the word x- in the free monoid generated by the set
consisting of x and -. Non-mathetically, it is simply the state
you obtain repeating b-times the sequence x-. The notion
(x-)^{b-1} then means that you take only b-1 repetitions.


  Dietrich

--
   Dr. Dietrich Kuske
   Institut f"ur Algebra
   TU Dresden
   D-01062 Dresden