%\input verbatim
\parindent = 0 pt
\parskip = 6pt
\outer\def\heading#1\endheading{\vskip0pt plus.2vsize\penalty-100
\vskip0pt plus-.2\vsize\bigskip\vskip\parskip
\message{#1}\leftline{\bf#1}\nobreak\smallskip\noindent}
\outer\def\title#1\endtitle{\centerline{\titling #1}}
\magnification=1200
\font\titling=cmr17\font\proclaiming=cmr12
\def\comment #1{\sevenbf\par\noindent\hrule\smallskip #1
\smallskip\hrule\medskip}
\def\empty {\emptyset}\let\bold=\bf
\def\Z{{\bf Z}}
\def\Q{{\bf Q}}
\def\R{{\bf R}}
\def\N{{\bf N}}
\def\C{{\bf C}}
\def\m{{\bf m}}
\def\a{\beta_1}
\def\b{\beta_2}
\def\h{{\bf h}}
\def\s{{\bf s}}
\def\f{{\bf f}}
\def\g{{\bf g}} 
\def\t{\thinspace}
\def\v{\vskip .5cm} 
\def\sqr#1#2{{\vcenter{\vbox{\hrule height.#2pt
         \hbox{\vrule width.#2pt height#1pt \kern#1pt
              \vrule width.#2pt}
         \hrule height.#2pt}}}}
\outer\def\proclaim#1#2\endproclaim
{\medbreak\noindent{\proclaiming#1.}
\enspace{\sl#2}\par\ifdim\lastskip<\medskipamount
\removelastskip\penalty55\medskip\fi}
\outer\def\demo#1{{\proclaiming#1}}
\def\enddemo{}
\def\square{\mathchoice\sqr68\sqr68\sqr{4.2}6\sqr{3.0}6}

\centerline{ \bf Remarks on Fibonacci Sequences in Groups 1}\v
\centerline{ Huseyin Aydin and Geoff C Smith }\v
\centerline{ \bf Section 1}\v
\centerline{ Introduction }\v \v

We shall prove two major theorems in the course of this document.
They are as follows.\v

Theorem A.\v

Suppose that $G$ is a $p-$group for some prime $p,$ and that
$G$ has exponent $p$ central length $n,$ then if any two elements
of $G$ are used to initiate a Fibonacci sequence in $G,$ then that sequence
must have minimum period dividing $kp^{n-1}$ where $k$ is the minimum
period of the ordinary Fibonacci sequence modulo $p.$\v\v
Recall the definition of a Fibonacci group;
The Fibonacci Group $F(r,n)$ is the group with the following presentation:
$$<\ x_1,\ldots,x_n\ |\ x_1x_2\ldots x_r=x_{r+1},\ x_2x_3\ldots x_{r+1} =
x_{r+2}, \ldots ,\ x_nx_1\ldots x_{r-1} = x_r\ >$$
where all subscripts are taken modulo $n.$\v\v
Theorem B.\v
Suppose that the Fibonacci Group $F(2,n)$ has the two generator relatively free 
group in the variety of exponent $p$ groups of class 1 as a homomorphic
image, then $F(2,n)$ has the two generator relatively free group $G$
in the variety of exponent $p$ groups of class 4 as a homomorphic
image.\v

Put less cleanly but perhaps more clearly, Theorem B says that if
$C_p \times C_p$ is a quotient of $F(2,n),$ then a larger quotient
can be described (unless the prime $p$ is even). Johnson
and Odoni have characterized the circumstances under which
$F(2,n)$ made Abelian is cyclic [JO], in turn, they have
therefore characterized the circumstances under which the Abelian
quotient is non-cyclic, and so Theorem B applies. Computer experiments
indicate that Theorem B is best possible, in the sense that it cannot be 
extended to class 5.
\v 
We also make announcements of two  computer generated results -- using
the system CAYLEY.\v
Announcement C.\v
Any Fibonacci sequence constructed by starting off with two
elements from the restricted Burnside group $R(2,5)$ must have
minimum period dividing 20. This is the least number with this property.
Indeed, the number 20 is also the minimum period of a Fibonacci
sequence in $C_5 \times C_5.$\v

Announcement D.\v

Wall's conjecture that for each prime $p$, the minimum period of the 
ordinary Fibonacci sequence
modulo $p^2$ is greater than the minimum period of the Fibonacci sequence
modulo $p$ has been verified to hold for all primes
less than $10^8$ by computer search.\v
Theorem A is proved in Section 2, and Theorem B is proved in Section 4,
using results on Fourier sums established in the lengthy and technical 
Section 3. The results of Section 3 may be of some interest in their own
right. Announcement C is a calculation which may be performed quite
easily via CAYLEY, in particular using the nilpotent quotient algorithm.
The background to Announcement D is explained in Section 5.

\vfill \eject

\centerline{ \bf Section 2}\v
\centerline{ D.D. Wall revisited, and a proof of Theorem A.}\v
The notion of a Fibonacci Group $F(r,n)$ followed on the heels of
Conway's Advanced Problem 5327 in the American Mathematical Monthly [Co].
Since then considerable effort has been expended in attempting to understand 
Fibonacci groups
(the reader not familiar with this notation should see Section 1).
This enterprise has met with considerable success. For example we now know
exactly when $F(2,n)$ is finite. Roger Lyndon's [Ly] application of
small cancellation theory almost finished the problem, though some corrections
(or perhaps amplifications)
to the arguments were needed, and were, according to a personal communication
from D. L. Johnson, supplied in Chalk's thesis [Ch]. The authors of this
document have not yet had the opportunity to read Chalk's thesis, and
rely on the evidence of D.L. Johnson for the accuracy of this information. 
The  `hard' cases not covered by Lyndon's
work were $F(2,8)$ and $F(2,10)$  -- these were covered by Brunner [Br],
and $F(2,9)$ by Newman [Ne].\v
 
In general, we know
quite a lot about Abelianized Fibonacci Groups, thanks to the 
work of Johnson and others in a sequence of papers in the mid-seventies, for
example in [CJ], [Jo] and [JWW]. Recent developments include work on
structure of  Abelianized Fibonacci groups (and more generally cyclically
presented groups). Papers are in preparation in this area, see (when
they exist) [BJK] and [JO]. This is a most felicitous and timely development
since [JO] will, among other things,  describe exactly when $F(2,n)$
can be the subject of Theorem B of this document.

The co-operation between Thomas, Robertson and Campbell has proved very
fruitful, and has given us 
some insight into groups which have presentations closely related to those 
of Fibonacci Groups. Thomas has an excellent survey article in the form
of a technical report [Th89] which appears more widely in abbreviated form
in [Th91]. This article is also a good source of references.
One possibility for future work by the 
authors of this document will be generalization of the results contained
here to Fibonacci-like groups and, if possible, cyclically presented
groups in general. The methods in the sequel do not admit of ready 
generalization, but Dikici and Smith are in the process of developing
alternative
methods to cover more general cases. 

What we will do in this work is to investigate which groups $F(2,n)$
have a given finite quotient $G$ of a particular form.
This problem has already been the
subject of investigation. It seems to have first been addressed by
Wall [Wa] and then Vinson [Vi] for cyclic groups. This case amounts
to the study of the instance where the image group is 
cyclic of prime-power order -- thanks to the Chinese remainder theorem.
We are able to generalize the Wall-Vinson theory to address the case where 
the image
group is an arbitrary finite $p-$group. This is the content of Theorem A.
We shall reprove some of the early
results for two reasons. Firstly we wish to make this paper self-contained,
but secondly we have a slightly different perspective from these
earlier workers -- and we contend that our viewpoint is better lit.

Campbell, Robertson and Doostie have, in an excellent preprint [CDR], addressed
the similar questions where the image group is simple. This work overlaps
in some degree with Doostie's thesis [D].

We must gratefully acknowledge the use of the Computer Algebra system
CAYLEY [Ca], which enabled us to guess some truths via 
computational experiments, and to effect calculations with specific groups 
where appropriate.

In {\it Remarks on Fibonacci Loops 2} (to appear) the authors will summarize
computational results on various relatively free nilpotent finite
$p-$groups. Work is also in progress (Dikici and Smith) concerning
similar questions about $F(r,n)$ where $r \ge 3.$ We expect this to
appear in {\it Remarks on Fibonacci loops 3 }. Dikici and Smith
claim to be able to generalize both Theorem A and Theorem B of this document.

Let $G$ be a finite group. We define a Fibonacci loop or {\it loop} 
$\g$ of $G$ a follows.
Suppose $g_0,g_1 \in G,$ then for $i \ge 2$ define $g_i = g_{i-2}g_{i-1}$
recursively. For $i \le 0$ define $g_i = g_{i+2}g_{i+1}^{-1}$ also
recursively. We obtain a {\it loop},
a ``bi-infinite sequence'' $\g = (g_i)_{ i \in \Z}$, for which both recurrence
equations hold for every integer $i.$\v

Such a loop must be periodic, since $G$ is finite. We will use the
term {\it length} to describe the minimum period of a loop $\f$, and write
it as $l(\f).$ Thus
if a loop $\f$ is known to be periodic with period $t, $ then
we may deduce that $l(\f)$ divides $t.$ There 
will be exactly $|G|^2$ distinct loops, since that is the number
of distinct ordered pairs of group elements. The r\^ole of the
indexing is not particularly significant, and we can eliminate it
easily. We define an equivalence relation $\sim$ on loops
by writing $(g_i) \sim (h_i)$ if and only if there exists an integer
$s$ such that $g_{i+s} = h_i$ for each integer $i.$ We introduce the term
{\it eloop} for the equivalence classes of loops. The period
of a loop is constant on equivalence classes, so the notion of the
length of an eloop makes sense. We deliberately blur the distinction
between $\f$ and the eloop containing $\f$ in order to avoid
notational explosion. If $\f$ is a loop or an eloop,
we write $l(\f)$ for its length.\v

Notice that $Aut(G)$ acts naturally on both the loops and 
the eloops; moreover, group homomorphisms send loops
to loops and eloops to eloops, though length may drop.\v

The set of loops of $G$ will be denoted $L(G).$
The set of all periodic bi-infinite sequences
of elements of $G$ form a group under componentwise composition, and
if $G$ is Abelian then $L(G)$ is a finite subgroup isomorphic
to the Cartesian square of $G.$\v

Notation:\v If $\f$ is a loop of length $l$ then we may elect to write it as
$$ \f= (f_0,f_1,\ldots f_{l-1})$$
and we may, by abuse, refer to the associated eloop in the same way.
This gives us a unique representation for loops, but, in general,
non-unique representations for eloops. We refer to the process of selecting
a loop in the same eloop class as $\f \in L(G)$ as {\it rotating} $\f.$\v

The case when $G$ is cyclic of prime order has been
studied by Wall [Wa] , Vinson [Vi] and Wilcox [Wi]. We reprove some 
of their 
results from our perspective, and throw a little light on some of their 
results.\v

We may assume that $G$ is the additive group of a field $GF(p)$ 
with $p$ elements.
The automorphism group of $G$ will then be handily realized as multiplication
by units.\v

Having chosen this particular representation of $G,$ there is an obvious
distinguished loop $\s$ with $s_0 = 0$ and $s_1 = 1.$ We call
this the {\it standard} loop, and refer to its associated
eloop as the standard eloop. The appellation {\it trivial} would seem appropriate
for the loop ${\bf 0} = (0,0,\ldots)$ and its associated eloop.\v

Following Wall [Wa] we let $k(p^n)$ denote the length of the standard eloop
of the cyclic group of order $p^n,$ thought of as the additive group of
$\Z/p^n\Z.$\v 

Lemma  2.1.\v
(i) Let $H$ be the additive group of the 
finite field $GF(p^t).$
If $\f \in L(H)$ then $l(\f)$ divides 
$k(p).$ A non-trivial short loop ${\bf h}\ (l({\bf h})< k(p))$
must have all its entries non-zero and be a geometric sequence 
(i.e. $h_i^{-1}h_{i+1}$ must be independent of $i$).\v 
(ii) For non-trivial loops $\f$ in $C_p$ we have $l(\f) = k(p)$
unless $p \cong 0,1$ or $4$ mod $5.$ 
\v

Proof.\v 
(i) Let $\s = (0,1,1, \ldots)$ be the standard loop of length $k(p),$
so $\s$ is a loop in $GF(p),$ a subfield of $GF(p^t).$
We can rotate this loop to obtain other loops of length $k(p)$ in
the same equivalence class. We can also multiply each element of the
loop by an element of $GF(p^t)$ to obtain another loop. Suppose $\f \in L(H)$ is
an arbitrary loop. In the obvious notation,
$$ \f = (f_0,f_1,\ldots) = f_0 \cdot(1,0,\ldots) + f_1\cdot(0,1,\ldots).$$
Notice that $(1,0,\dots)$ is a rotation of the standard loop so the
loop $\f$ has period $k(p)$ and 
$l(\f)$ must divide  $k(p).$\v

Suppose $\f$ has 0 as an entry, but is not the trivial loop. By rotation
we may assume that $\f = (0,x,\ldots)$ where $x \not = 0.$ Now
$\f = x\cdot \s$ (and $\s = x^{-1}\cdot \f$) so $l(\f) = k(p).$ \v

We may now assume that $\f$ has only non-zero entries, and we shall suppose that
$l(\f) < k(p).$ Suppose
$ \f = (w,wx,\ldots)$ and that $\g$ is any rotation of $\f.$ 
Thus $\g = (y, yz, \ldots)$ 
and then $\f - wy^{-1}\cdot \g
= (0,w(x - z),\ldots)$ is a loop of length less than $k(p)$ containing
an entry which is $0.$ It must be the trivial loop and so $x = z.$ Thus there
exists at most one $\beta \in GF(p^t)$ which can occur as a ratio of consecutive
elements in any given short loop. Thus a non-trivial short loop
must have non-zero entries. This completes the proof of part (i).\v

(ii) The recurrence equation forces
such a $\beta$ to satisfy $\beta^2 = \beta + 1.$ 
If $t = 1$ such a $\beta$ will exist in $GF(p)$ exactly when 
$5$ is a square in $GF(p).$ The condition for this special case
is that  either $p = 5$
or, by quadratic reciprocity, $p \cong 1$ or $4$ mod $5.$ 
$$\eqno \square$$
Thus non-trivial short loops of $C_p$ can only exist when a {\it golden ratio}
occurs in $GF(p).$ The polynomial $X^2 - X - 1$ has coincident roots
in $GF(5),$ and otherwise it has distinct roots. Thus for
$p \cong 1$ or $4$ mod $5$ there are two rival golden ratios in play,
either of which might be the common ratio of a non-trivial short loop.
The length of a loop with common ratio $\beta,$ a golden ratio,
is simply the multiplicative order of $\beta.$
In fact at most one of the golden ratios can cause a loop to be short.\v

Lemma 2.2.
Let $H$ be the additive group of a finite field $GF(p^t)$ where
$p \not = 5.$
Suppose $\f \in L(H)$ is a 
non-trivial short loop with common ratio $\beta_1.$ Let
$ \beta_2 \ (\not = \beta_1)$ be the other root of $X^2 - X -1$ in 
$GF(p^t).$ There are no non-trivial short loops in $L(H)$ with common ratio
$\beta_2.$\v
Proof.\v We may multiply $\f$ by $f_0^{-1}$ to obtain a loop 
${\bf a}  = (1, \beta_1, \ldots)$ of the same length as $\f.$
Let
${\bf b } = (1, \beta_2, \ldots).$ Put $n = l({\bf a}) = o(\beta_1)$
and observe that $\beta_1 \beta_2 = -1.$
Thus $\beta_2^{2n} = (-1)^{2n} = 1.$ We can exchange the r\^oles
of $\beta_2$ and $\beta_1$ to obtain that the multiplicative orders
of $\beta_1$ and $\beta_2$ either coincide or differ by a factor of
2.\v  
Thus $l({\bf a} - {\bf b})$ divides $m = max\{o(\a),\ o(\b)\}.$
Now ${\bf a} - {\bf b}$ commences with 0 
and so must either be ${\bf 0}$ or of length
$k(p).$ It cannot be ${\bf 0}$ else $\a = \b$ and then $p = 5.$\v
It follows that $k(p)$ divides $m.$\v
On the other hand, $m$ is the length of a loop of $H$ and so, by Lemma 2.1,
we know that $m$ divides $k(p).$ Thus $m = k(p)$ as required.  
$$\eqno \square$$ 

In the case $p = 5$ the polynomial $X^2 - X -1$ has the double root 3.
This gives rise to short loops of length 4 of the form
$(a, 3a, 4a, 2a)$ where $a \not = 0.$ In fact $k(5) = 20$ by direct calculation:
$$ \s = (0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1).$$\vfill \eject
Lemma 2.3 (Wall) Suppose $p$ is an odd prime.\v
(i) If $p \cong 1 \hbox{ or } 4 \hbox{ mod } 5$ then
$k(p)$ divides $p-1.$\v 
(ii) If $p \cong 2 \hbox{ or } 3 \hbox { mod } 5$ then $k(p)$ divides 2p+2. \v 

Proof.\v
Choose $\beta \in GF(p^2)$ a root of $X^2 - X - 1$ giving 
rise to a loop $(1, \beta, \ldots)$ of length $k(p).$ 
Such a $\beta$ exists by lemma 2.2.  
Thus $k(p)$ is the multiplicative order of $\beta.$ Now part (i)
is immediate since then $\beta \in GF(p)^\circ,$ the group of units
of $GF(p).$
For part (ii), put $\beta_1 = \beta  \in GF(p^2) \setminus GF(p).$ Let
the other root of $X^2 - X -1$ in $GF(p^2)$ be $\beta_2.$ By Galois Theory
there in a $GF(p)-$ automorphism of $GF(p^2)$ exchanging $\beta_1$ and 
$\beta_2,$ so the multiplicative orders of $\beta_1$ and $\beta_2$ must
coincide and be $k(p)$ by Proposition 3.2. 
Let $t$ be the smallest positive integer such that $\beta_1^t \in GF(p).$
By considering the group $GF(p^2)^\circ/GF(p)^\circ$ we see
that $t$ divides $p+1.$ It is important to note that if $t$ happens to
be odd, then $t$ actually divides $(p+1)/2.$
Put $\gamma = \beta_1/\beta_2.$ By Galois Theory
$\beta_1^u \in GF(p)$ if and only if $\beta_1^u = \beta_2^u,$ so
then $\gamma^t = 1.$
Recall
that $\beta_1\beta_2 = -1$ and so $$\gamma^t = 
\beta_1^t/\beta_2^t = (-1)^t\beta_1^{2t} = 1.$$
If $t$ is even $k(p)$ must divide $2t,$ and if $t$ is odd, $k(p)$ must
divide $4t.$ We remarked earlier that $t$ divides $p+1,$ and also divides
$(p+1)/2$ in the event that $t$ is odd. Either way, we have proved that 
$k(p)$ must divide $2p+2.$
$$ \eqno \square$$ 
Definition.\v
Suppose $G$ is (temporarily) any Abelian group 
written additively, and that $\g \in L(G).$ In the event that
there exists $g_i$ in the sequence such that $g_i = 0,$ we let
the rank of apparition of the sequence be $r$ where $r$ is the
smallest positive integer such that there exist $m,n \in \Z$ with
$g_m = g_n = 0$ and $m-n = r.$\v
Lemma 2.4 Suppose that $x$ appears immediately before the second 0 in the 
standard loop $\s \in L(C_p)$, and that $o(x) = t.$ 
We may conclude that $k(p) = rt$
when $r$ is the rank of apparition for $p.$\v 

Proof.\v
$ f = (0,1,\ldots 0,x \ldots)$ so multiplication by $x$ rotates $f$ through
$r.$ Thus $x^t = 1$ and $x^u \not = 1$ for positive integers $u$ smaller than
$t,$ and so $rt = k(p).$
$$\eqno \square$$

Lemma 2.5 (Vinson) \v
Suppose $p \not =2 \hbox{ or }  5,$ then
the rank of apparition $r$ of $\s \in L(C_p)$ is the multiplicative order of 
$\gamma = \beta_1/\beta_2.$ 
If $r$ is odd then $k(p) = 4r.$
If $r$ is even then either $l = r$ or $l = 2r.$\v
Proof\v Let $\gamma = \beta_1/\beta_2$ and suppose that $o(\gamma) = u.$
Notice that $$s = d(1,\beta_1,\ldots) - d(1,\beta_2,\ldots)$$ where
$d = (\beta_1 - \beta_2)^{-1}.$ The rank of apparition $r$ is the
smallest positive integer such that $\beta_1^r = \beta_2^r,$ and so
must coincide with the multiplicative order of $\gamma.$\v
Our argument proceeds along the lines of part of the proof of 
lemma 2.4, though on this occasion we are studying $\gamma
= \beta_1/\beta_2$ even when $\beta_1,\beta_2 \in GF(p).$ We may assume
that the multiplicative order of $\beta_1$ is $k(p),$ else we just
interchange the r\^oles of $\beta_1$ and $\beta_2.$ At any rate,
it is still true that $1 = \gamma^r = \beta_1^r/\beta_2^r$ and so
$\beta_1^{2r} = (-1)^r.$ If $r$ is even this forces $k(p)$ to divide $2r.$ 
Next
we are use the fact that $p$ is odd so that $-1 \not = 1.$
If $r$ is odd we have $k(p)$ divides $4r$
but not $2r.$\v
We also know that $r$ divides $k(p)$ irrespective of the parity
of $r$ by lemma 2.4. Now we are done. 
$$\eqno \square$$
When $p =2$ the proof of lemma 2.5  goes through almost to the end.
It only fails at the point where the distinction is made between $-1$ and
$1.$ It is true that the rank of apparition is $o(\gamma) = 2.$ 
Thus the Proposition all holds when $p = 2$ save that we must allow
$k(2)$ divides $2r.$ 
There is no way round this point, since
in fact $k(2) = 3 = r$ so $k(2) \not = 4r.$\v
Notice that when $p = 5,$ we have $\beta_1 = \beta_2 = 0.$ In
fact the standard loop 
$$ (0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1)$$ 
has length $20$, and the rank of apparition is $5.$\v
Having tidied the awkward primes, we obtain a clean result.\v
Corollary.\v If $p$ is an odd prime then $k$ is even.
$$\eqno \square$$
We now turn our attention to more general circumstances. In a group
of prime order, only the trivial loop ${\bf 0}$ has the property that two
adjacent elements fail to generate the whole group. In general
this is not the case. The interesting case is when a pair, and therefore
all pairs, of adjacent elements of the loop generate the group --
otherwise you simply study a smaller group. We will call
a loop (or eloop) a {\it generating loop} of a finite group $G$
if and only if a pair, and so all pairs, of adjacent elements
generate the group. We pursue the theme of $p-$groups. From this point
of view, we may restrict ourselves to $p$-groups where $G/\phi(G),$
the Frattini quotient,
is either cyclic of order $p$ (so $G$ itself is cyclic) or the 
Cartesian square of the cyclic
group of order $p.$ The Abelian case was investigated by Wall. As we
observed before, the product of loops is not in general a loop, but
we can squeeze out something.\v 
 
Lemma 2.6\v
 Let $G$ be  a finite group with $\f \in L(G)$
a loop. Suppose that $\h \in L(Z(G))$ is a loop of the 
centre of $G,$ then $\f\cdot \h,$ the componentwise product
of these loops is a loop of $G.$\v

Proof.\v For each integer $i$ we have
$$f_ih_i = f_{i-2}f_{i-1}h_{i-2}h_{i-1} = f_{i-2}h_{i-2}f_{i-1}h_{i-1}.$$
$$\eqno \square$$

Theorem A.\v
Suppose $G$ is a  
$p$-group for some prime $p,$ and that
$G$ has exponent $p$ central length $n,$
then if $\f$ is loop of $G$ then the length of $\f$ must
divide $k(p)p^{n-1}.$ \v
Proof\v We induct on the exponent $p$ central length
of $G,$ and disposing of the trivial group
and the Abelian groups by inspection, we may assume that 
$G$ has exponent $p$ central length at least 2.
We consider the elements $f_0,f_1$ of $G.$ 
The group $G$ must have a central 
subgroup $N$ of exponent $p$ with $G/N$ having exponent $p$ central length 
$n-1.$ 
Choose a transversal $T$ for $N$ in $G$ and
put $f_i = t_i n_i$ where $t_i \in T,\ n_i \in N$ for $i \in \Z.$
The length of the loop $(t_0N,t_1N,\ldots)$ in $G/N$ 
must divide $\lambda = k(p)p^{n-2}$ by the inductive hypothesis.
Thus $f_{\lambda} = t_0 n_{\lambda }$ and $f_{\lambda +1} = t_1 n_
{\lambda + 1}.$ It is not necessarily true that the bi-infinite
sequence $(n_i)$ is a loop of $N.$ 


The ``ratios'' $f_{\lambda}f_0^{-1}$ and $f_{\lambda + 1}f_1^{-1}$
only depend on $t_0$ and $t_1.$ To see this we tinker with $n_0$ and
$n_1$ in an arbitrary fashion, and observe that the relevant ratios are left
undisturbed. Suppose that $\m$
is any loop of $N.$ Notice that $l(\m)$ must divide $k(p)$ by lemma 2.1, and 
so $l(\m)$ must
therefore divide $\lambda.$ Thus
$$ \m   = (m_\lambda,m_{\lambda + 1},\ldots) = (m_0,m_1,\dots).$$
Now consider $ {\bf a}= \f \cdot \m.$ By lemma 2.6 this is a loop of $G,$
and by selecting $\m$ appropriately we may force $a_0 = t_0n$ and
$a_1 = t_1n'$ where $n,n'$ are any chosen pair of elements of $N.$
Now
$$ a_\lambda a_0^{-1} = f_\lambda m_\lambda (f_0 m_0)^{-1} = 
f_\lambda f_0^{-1} = u$$
and 
$$ a_{\lambda + 1} a_1^{-1} = f_{\lambda +1}m_{\lambda + 1}(f_1m_1)^{-1} =
f_{\lambda + 1}f_1^{-1} = v.$$ 
We have shown that $u$ and $v$ depend only on 
$t_0$ and $t_1,$ and do not depend
on $n_0$ or $n_1.$ Thus $f_{j\lambda} = f_{(j-1)\lambda} u$ and 
$f_{j\lambda + 1} = f_{(j-1)\lambda + 1} v$ for all positive
integers $j.$ We conclude that $f_{p\lambda} = f_0u^p = f_0$ and
$f_{p\lambda +1} = f_1 v^p = f_1$ and we are done. 
$$\eqno \square$$

In [Wa] Wall raises the question as to whether or not it can happen
that $k(p) = k(C_p)$ can be equal to $k(C_{p^2}).$ He did a computer search
and found that $k(p) \not = k(p^2)$ for all primes less than $10^4.$ It is
amusing to note that, with the passage of time, Wall's heroic
calculation of 1960 can now be performed in about 1 second
on a SUN 4 workstation. We have
extended the range of the search, and can announce that equality does not
hold for any prime less than $10^8.$ See Section 5 of this document.
\v



Let us focus on the prime 5 for a moment,
let $G$ be
the Restricted Burnside Group $R(2,5)$ -- so $|G| = 5^{34}$ and $G$ is nilpotent
of class 12. A computer calculation shows that $k(G) = 20 = k(5).$
In other words, $R(2,5)$ is a homomorphic image of $F(2,20).$ This is
the content of Announcement C.\v 

\vfill \eject

\centerline{\bf Section 3} 
\centerline{ Fourier Sums }
We now embark on a large number of calculations concerning
{\it Fourier Sums}. We call them Fourier sums by analogy with
the process of integrating a periodic function over its fundamental
range, widely studied in other contexts. 
We will work modulo a prime $p,$ though
we could always choose to work modulo an arbitrary natural
number. In the cases where we exclude certain primes, we would
have had to impose non-divisibility conditions on the modulus
should we have worked modulo a composite number.

We will make the blanket assumption that the prime is at least 5. This
simplifies matters considerably. In particular, for odd primes
$k$ is even, whereas $k$ is 3 when $p$ is 2. That would lead
to all sorts of extra complications. Another prime which causes trouble
is the prime 11. This does not start to become awkward until Lemma 3.7,
so we will not ban it from the outset. Group theoretically, the cases
$p = 2$ or $3$ are degenerate in our applications, so we lose little.
Some of the congruences hold good when $p = 2$ or $3,$ a fact which may be
verified by direct calculation.
Where the range of summation is not stated, it is supposed to be
clear. In particular, we begin with sums over the range 
$0 \le i \le k-1,$ exactly over a fundamental period. The key
observation to make is that we may translate the range of summation
to any other fundamental period without changing the value of the sum.
Another useful ruse is to reverse the range of summation.\v

The philosophy of our (admittedly technical) manipulations is that
in order to prove results about finite $p-$groups, we need to establish that
certain sums of monomials manufactured from the Fibonacci sequence
modulo $p$ must vanish. These sums can get quite complicated, for example
it turns out to be necessary to show that
$$ \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=0}^{j-1}
            s_r^2s_js_i^2s_{r-j-1}s_{j-i-1}(-1)^{r+1}
+ \sum_{j=0}^{k-1}\sum_{i=0}^{j-1}s_j(_2^{s_j})s_{j-i-1}s_i^2(-1)^{j+1}$$
$$ + \sum_{i=0}^{k-1} s_i^2(_3^{s_i})(-1)^{i+1} = 0.$$

This is a somewhat daunting sum of sums. We will build
an armoury of equations and techniques which will eventually render
the above sum tractable. In case the reader might think that any
sum (over the fundamental range) of monomials must vanish, we draw
his or her attention to $\sum_{i=0}^{k-1} s_i^2(-1)^{i+1}.$  We can 
show that this sum never vanishes for the relevant primes save when
the prime is 5. 

Another point worth making is that the network of logical dependencies
between the equations in the sequel is somewhat complex. We have found a 
route through to the equations which we need. It is hardly likely
that we have found the ``shortest path''. Some of the equations we study
are very friendly, in the sense that almost any sensible attempt to
demonstrate their truth will succeed. Others were far more resistant,
and required the application of considerable ingenuity before they 
yielded. There
may, of course, be fast tracks to those results, but if so, we have been
unable to find them.
\vfill \eject 
Lemma 3.1\v

The following equations concerning sums of powers of Fibonacci numbers
over a fundamental range all hold good.

$$\sum s_i = 0.\eqno (1)$$

$$\sum s_i^2 = 0.\eqno (2)$$

$$\sum s_i^3 = 0. \eqno (3)$$

Proof. 
$$\sum s_i = \sum s_{i-1} + \sum s_{i-2} = \sum s_i + \sum s_i.$$
Equation (1) now follows. Note how we have exploited the periodicity
of the loop $(s_i).$
$$\sum s_i^2 = \sum (s_{i-1} + s_{i-2})^2$$
so

$$\ \sum s_i^2 = 2\sum s_i^2 + 2\sum s_is_{i-1}. \eqno (4)$$

Similarly, we express $s_{i-2}$ as $s_i - s_{i-1}$ to obtain

$$\ \sum s_i^2 = \sum s_{i-2}^2 = 2\sum s_i^2 - 2\sum s_is_{i-1}. \eqno (5)$$

Adding (4) and (5) we obtain
$$\ 2\sum s_i^2 = 4\sum s_i^2$$
from which the equation (2) follows. 
$$ \sum s_i^3 = \sum s_{i+1}^3 =  \sum (s_i + s_{i-1})^3 $$
so
$$ \sum s_i^3 = 2\sum s_i^3 + 3\sum s_i^2s_{i-1} + 3\sum s_is_{i-1}^2. \eqno
(6)$$ 
Similarly we may write
$$ \sum s_i^3 = \sum s_{i-2}^3 = \sum (s_i - s_{i-1})^3$$
and so
$$ \sum s_i^3 = -3\sum s_i^2s_{i-1} + 3\sum s_is_{i-1}^2. \eqno (7)$$
Add $(6)$ and $(7)$ to obtain

$$ 2\sum s_i^3 = 2\sum s_i^3 + 6\sum s_is_{i-1}^2$$

from which it follows that

$$ 3\sum s_is_{i-1}^2 = 0.\eqno (8)$$

Now we adjust $(8)$ using $s_i = s_{i-1} + s_{i-2}$ to obtain

$$ 3\sum s_i^3 + 3\sum s_i^2 s_{i-1} = 0. \eqno (9)$$

From $(6)$ and $(8)$ we know

$$ \sum s_i^3 + 3\sum s_i^2 s_{i-1} = 0. \eqno (10)$$

Subtract $(10)$ from $(9)$ to obtain the result.
$$\eqno \square$$

Corollary.

$$\sum s_is_{i-1} = 0 \eqno(11)$$

$$\sum s_i^2s_{i-1} = \sum s_is_{i-1}^2 = 0.\eqno(12)$$

$$\sum s_i^2s_{i+a} = 0 \ \forall \ a \in \Z.\eqno (13 ) $$

Equation (13) is obtained from equations (3) and (12) using the
Fibonacci recurrence and finite induction.

$$\eqno \square$$
Lemma 3.2. 
$$ s_{k-i} = s_{-i} = s_i(-1)^{i+1}\ \forall i \in \Z \eqno (14)$$
$$\sum s_i(-1)^{i+1} = 0.\eqno (15)$$
$$\sum s_i^3(-1)^{i+1} = 0.\eqno (16)$$

Special Note: Equation $(14)$ is of such crucial importance in the sequel
that we will often omit to give future mention to it, else this document would
be overwhelmed with such references. The reader is urged to take
note of this result. The result is, of course, well-known, as are
equations (1) and (15).\v
Proof.\v

First notice that $s_i = s_{i-1} + s_{i-2}\ \forall i \in \Z$ forces
$$ s_{i-2}(-1)^{i-1} = s_{i-1}(-1)^i + s_i(-1)^{i+1}\ \forall i \in \Z .$$ 
Put $t_{-i} = s_i(-1)^{i+1}$ to obtain $t_i = t_{i-1} + t_{i-2}\ 
\forall i \in \Z.$
Notice also that $t_0 = 0$ and $t_1 = 1.$ Thus $(t_i) = (s_i),$
and equation $(14)$ follows. Note that it follows that $k$ is even (for odd
primes), because 
$$1 = s_1 = s_{k-(k-1)} = s_{k-1}(-1)^k = (-1)^k.$$  

$(15):$ Now $$\sum s_i(-1)^{i+1} = \sum_{i=0}^{k-1} t_{-i} 
  = \sum_{i=0}^{k-1} t_{k-i}.$$
We now reverse the direction of the range of summation, replacing
$i$ by $k-i.$ We have
$$\sum s_i(-1)^{i+1}  = \sum_{i= 1}^k s_{-i} = \sum s_{-i} = \sum s_i = 0$$
by $(1).$\v
We tackle the proof of equation (16) in the same spirit.
$$ \sum s_i^3 = \sum s_{k-i}^3 (-1)^{3(i+1)} 
   = \sum s_{k-i}^3 (-1)^{k-i+1}$$ 
since $k$ is even. Now reverse the direction of summation to obtain
$$\sum s_i^3 = \sum_{i = 1}^k s_i^3 (-1)^{i+1} = \sum s_i^3(-1)^{i+1}.$$
Recall that $\sum s_i^3 = 0$ by equation (3) and so we are done.
$$\eqno \square$$

Corollary.\v For odd primes $p,$\ Wall's number $k$ is even.\v
$$\eqno \square$$
Lemma 3.3\v

The following equations hold good.
$$\sum s_{i+1}^2 s_i = 0 \eqno (17)$$
$$\sum s_{i+1}s_i^2 = 0 \eqno (18)$$
$$\sum s_{i+1}^2s_i(-1)^i = 0 \eqno (19)$$
$$\sum s_{i+1}s_i^2(-1)^i = 0 \eqno(20)$$
Proof.\v
We first exploit equation $(3),$
$$ 0 = \sum s_{i+2}^3 = \sum ( s_{i+1} + s_i)^3 = 2\sum s_i^3
+ 3\sum s_{i+1}^2s_i + 3\sum s_{i+1}s_i^2 .$$
Thus 
$$3\sum s_{i+1}^2s_i + 3\sum s_{i+1}s_i^2 = 0.$$  
Similarly we have
$$ 0 = \sum s_{i-1}^3 = \sum (s_{i+1}-s_i)^3 = - 3\sum s_{i+1}^2s_i 
+ 3\sum s_{i+1}s_i^2.$$
Adding and subtracting these last two equations
we obtain $(18)$ and $(17).$
If we repeat this argument, but exploit equation $(16)$
rather than equation $(3),$ we obtain equations
$(19)$ and $(20).$ 
$$\eqno \square$$
Corollary.
$$\sum s_i^2s_{i+a}(-1)^i = 0 \ \forall \ a \in \Z.\eqno (21)$$

This follows from equations (16) and (20), the Fibonacci recurrence,
and finite induction.
$$\eqno \square$$
The next lemma is well-known. We include a proof for completeness.\v

Lemma 3.4\v This is a well-known Fibonacci identity.
 $$s_{i+1}s_{i-1} = s_i^2 + (-1)^i\ \forall i \in \Z \eqno (22)$$
Proof.\v
To see this, one may simply
observe that
$$ \pmatrix{ s_{i+1} & s_i \cr s_i & s_{i-1}} = \pmatrix{ 1 & 1 \cr
1 & 0}^i$$
in $GL(2,\Z)$ by induction on $i.$ Taking determinants yields the result.
$$\eqno \square$$ 

The next lemma needs a little work. The corresponding non-alternating
sum $\sum s_i^4$ is not 0 in general. It is when $p$ is 2 or 3, but
a computer search yields no other prime smaller than 900 for which
the value of this sum is 0. Happily it is the alternating sum which we
need to control.\v 

Lemma 3.5\v

$$\sum s_i^4 (-1)^i = 0.\eqno (23)$$

Proof.\v

We introduce some temporary shorthand to clarify the proof.

Let 
$$\alpha = \sum s_i^4(-1)^i,$$ 
$$\beta = \sum s_{i+1}^3s_{i-1}(-1)^i,$$
$$\gamma = \sum s_{i+1}s_{i-1}^3(-1)^i,$$
$$\delta = \sum s_{i+1}^2s_{i-1}^2(-1)^i,$$
$$\epsilon = \sum s_i^3 s_{i-1}(-1)^i,$$
$$\zeta = \sum s_is_{i-1}^3(-1)^i$$
and finally
$$\eta = \sum s_i^2 s_{i-1}^2(-1)^i.$$
Our ambition is to demonstrate that $\alpha = 0.$ First we show that
$\beta = \gamma.$
$$\beta = \sum s_{i+1}^3s_{i-1}(-1)^i = \sum s_{k-i-1}^3s_{k-i+1}(-1)^{k-i}.$$
The final equality is obtained using $(14)$ and the fact that $k$ is even
-- the corollary to lemma 3.2.
Now reverse the direction of summation to obtain
$$\beta = \sum_{i=1}^k s_{i-1}^3s_{i+1}(-1)^i = \gamma.$$
The final equality is obtained by translating the range.\par

Our next ambition is to show that $\alpha = \delta.$ We deploy
the result of lemma 3.4 (equation (22)) to good effect.
$$\delta = \sum (s_{i+1}s_{i-1})^2(-1)^i = \sum (s_i^2 + (-1)^i)^2(-1)^i$$
so $$\delta = \sum s_i^4(-1)^i + 2\sum s_i^2 + \sum (-1)^i.$$
Now $\sum s_i^2 = 0$ by (2)  and $\sum (-1)^i = 0$ since $k$ is even. Thus
$\alpha = \delta.$

Our next target is to show that $\epsilon = \zeta.$
$$\epsilon = \sum s_i^3s_{i-1}(-1)^i = \sum s_{k-i}^3s_{k-i+1}(-1)^{k-i+1}.$$
Note that $i$ and $i-1$ have opposite parity. We reverse the range of
summation to obtain
$$\epsilon = \sum_{i=1}^k s_i^3s_{i+1}(-1)^{i+1} = \sum s_is_{i-1}^3(-1)^i 
= \zeta.$$

Now for something a little different; we show that $\alpha + \beta = \epsilon
\ (= \zeta).$
$$\alpha + \beta =  \sum s_i^4(-1)^i + \sum s_i^3s_{i-2}(-1)^{i+1}$$ 
$$ = \sum s_i^3(-1)^i(s_i - s_{i-2}) = \sum s_i^3s_{i-1}(-1)^i
= \epsilon.$$
As a final preliminary, we show that $\eta = 0.$ Notice that
$$\eta = \sum s_i^2 s_{i-1}^2(-1)^i = \sum s_{k-i}^2s_{k-i+1}^2(-1)^{k-i}.$$
Once again we have used $(14),$ and have prepared to reverse the range
of summation. Thus
$$\eta = \sum_{i=1}^k s_i^2s_{i+1}^2(-1)^i = \sum s_i^2 s_{i+1}^2 (-1)^i.$$
Now translate the range of summation to yield
$$\eta = \sum s_{i-1}^2 s_i^2 (-1)^{i+1} = -\eta,$$
and we are done.

Let us summarize the results of our labour.
$$\beta = \gamma,\ \delta = \alpha,\ \epsilon = \zeta,\ 
\alpha + \beta  = \epsilon,\ \eta = 0.$$

We now embark on calculations to obtain linear relations between $\alpha$
and $\beta,$ using the binomial theorem as our vehicle.

$$\alpha = \sum (s_{i+1} - s_{i-1})^4(-1)^i = -\alpha - 4\beta + 
6\delta -4\gamma - \alpha$$ so
$$\alpha = -2\alpha -8\beta + 6\alpha$$ and therefore
$$3\alpha - 8\beta = 0 \eqno(*).$$

Now we express $\alpha$ in a different way.
$$\alpha = \sum s_{i+1}^4(-1)^{i+1} = \sum (s_i + s_{i-1})^4(-1)^{i+1},$$
so
$$\alpha = -\alpha -4\epsilon - 6\eta -4\zeta + \alpha.$$
This simplifies to
$$\alpha =  - 4(\alpha + \beta) - 0 - 4(\alpha + \beta) $$
and so
$$9\alpha + 8\beta = 0. \eqno (**)$$

Adding the starred equations we obtain $12\alpha = 0$ from which
the result follows. 
$$\eqno \square$$
Corollary.

$$\beta = \sum s_{i+1}^3s_{i-1}(-1)^i = 0. \eqno (24 )$$
$$\gamma = \sum s_{i+1}s_{i-1}^3(-1)^i = 0. \eqno (25 )$$
$$\delta = \sum s_{i+1}^2s_{i-1}^2(-1)^i = 0. \eqno (26)$$
$$\epsilon = \sum s_i^3 s_{i-1}(-1)^i = 0.\eqno (27 )$$
$$\zeta = \sum s_is_{i-1}^3(-1)^i = 0. \eqno (28)$$
$$\eta = \sum s_{i}^2s_{i-1}^2 (-1)^i = 0.\eqno (29)$$

$$\eqno \square$$
We now discard the assigned meanings of these Greek letters, since we
will wish to use them locally again in the future.\v

Lemma 3.6\v

If $p \not = 11$ then $$\sum s_i^5 = 0 \eqno (30)$$
and $$\sum s_i^5(-1)^i = 0 \eqno (31)$$

Proof.\v
Equation $(31)$ will follow easily from $(30),$ and we address ourselves
to $(30).$ Lemma 3.4 (equation  (22)) will be our main weapon.

Let $\alpha = \sum s_i^5$ then
$$\alpha = \sum (s_{i+1} - s_{i-1})^5$$  so
$$\alpha = -5\sum s_{i+1}^4s_{i-1} + 10\sum s_{i+1}^3s_{i-1}^2 
- 10\sum s_{i+1}^2s_{i-1}^3 + 5\sum s_{i+1}s_{i-1}^4$$ and therefore
$$ \alpha = -5\sum s_{i+1}s_{i-1}(s_{i+1}^3 - s_{i-1}^3)
+ 10\sum s_{i+1}^2s_{i-1}^2(s_{i+1} - s_{i-1}).$$
We now deploy equation (22) to obtain
$$\alpha = -5\sum (s_i^2 + (-1)^i)(s_{i+1}^3 - s_{i-1}^3)
+10\sum (s_i^2 + (-1)^i)^2s_i.$$  
This expression admits of considerable simplification. In fact one can
simply suppress the occurrences of $(-1)^i$ because the following
equations hold:
$$\hbox{ } \sum s_{i+1}^3(-1)^{i+1} = 0 \hbox{ from (16) }$$
$$\hbox{ } \sum s_{i-1}^3(-1)^{i+1} = 0 \hbox{ from (16) }$$
$$\hbox{ } \sum s_i^3(-1)^{i+1} = 0 \hbox{ from (16) }$$
and
$$\hbox{ } \sum s_i = 0 \hbox{ from (1). }$$
Thus $$\alpha = -5\sum s_i^2(s_{i+1}^3 - s_{i-1}^3) + 10\alpha,$$
and so $$ -9\alpha = -5\sum s_i^2 (s_{i+1}^3 - (s_{i+1} - s_i)^3).$$
Expanding we obtain
$$-9\alpha = -5\sum s_i^2(3s_{i+1}^2s_i -3s_{i+1}s_i^2 +s_i^3)$$
so
$$-9\alpha = -5\sum s_i^2 (3s_{i+1}s_i(s_{i+1} - s_i) + s_i^3)$$
and therefore 
$$-9\alpha = -5\sum s_i^2 (3s_{i+1}s_is_{i-1} + s_i^3).$$
We now close on our quarry using lemma 3.4 again. We have
$$-9\alpha = -5\sum s_i^2 (3s_i(s_i^2 + (-1)^i) + s_i^3).$$
Once again we may suppress $(-1)^i$ because of equation $(16).$ Thus
$$-9\alpha = -5\sum 4s_i^5 = -20\alpha.$$
We conclude that $11\alpha = 0.$ Since we have excluded the
prime 11, we have demonstrated the truth of equation $(30).$

To prove the second part of the lemma is now an easy task.
We have
$$\sum s_i^5(-1)^i = \sum s_{k-i}^5(-1)^{i+1}(-1)^i = -\sum s_{k-i}^5 =
- \sum s_i^5 = 0,$$
and by appeal to equation (30), equation (31) is justified.
$$\eqno \square$$

As a matter of interest, the exclusion of the prime 11 in lemma 3.6
is necessary. When $p = 11$ a direct calculation yields
$\sum s_i^5 = 1$ and
$\sum s_i^5(-1)^i = -1.$\v
 

Lemma 3.7

Assuming $p \not = 11,$ we have
$$ \sum s_i^2s_{i-1}^3 = 0 \eqno (32)$$
$$ \sum s_i^3s_{i-1}^2(-1)^i = 0 \eqno (33)$$
Proof.\v
Put
$\alpha =  \sum s_i^2s_{i-1}^3,$ so
$$\alpha  = \sum (s_{i+1} - s_{i-1})^2s_{i-1}^3 
          = \sum (s_{i+1}^2 - 2s_{i+1}s_{i-1} + s_{i-1}^2)s_{i-1}^3.$$
Thus
$$\alpha = \sum s_{i+1}^2s_{i-1}^3 - 2\sum s_{i+1}s_{i-1}^4 + \sum s_{i-1}^5,$$
but by equation (30) this simplifies to
$$\alpha = \sum s_{i+1}^2s_{i-1}^3 - 2 \sum s_{i+1}s_{i-1}^4.\eqno (34)$$
Now deploy equation (22) in conjunction with equation (34)
to deduce that
$$\alpha = \sum (s_i^2 + (-1)^i)^2 s_{i-1} - 2 \sum (s_i^2 + (-1)^i)s_{i-1}^3,$$
and so
$$\alpha = \sum (s_i^4 + 2s_i^2(-1)^i + 1)s_{i-1} -2\sum s_i^2s_{i-1}^3 - 
2\sum s_{i-1}^3(-1)^i.$$
Now equations (19),(1) and (16) come to aid, giving
$$\alpha = \sum s_i^4s_{i-1} -2\sum s_i^2 s_{i-1}^3,$$
and so
$$3\alpha = \sum s_i^4s_{i-1}.\eqno (35)$$

We now embark on another tack. This time we exploit equation (30). We have
$$\sum s_{i+1}^5 = \sum (s_i+s_{i-1})^5 = 0$$
so
$$\sum (s_i^5 + 5s_i^4s_{i-1} + 10s_i^3s_{i-1}^2 + 10 s_i^2s_{i-1}^3
   + 5s_is_{i-1}^4 + s_{i-1}^5)  = 0,$$
which simplifies to
$$5\sum s_i^4s_{i-1}+10\sum s_i^3s_{i-1}^2+
10\sum s_i^2s_{i-1}^3+5\sum s_is_{i-1}^4 = 0,
\eqno (36)$$
thanks to equation (30).

We now repeat this argument, this time observing that equation (30) yields
$$\sum s_{i-2}^5 = \sum (s_i - s_{i-1})^5 = 0.$$

After mimicking our previous calculation, we find
$$-5\sum s_i^4s_{i-1} + 10\sum s_i^3s_{i-1}^2 - 
10 \sum s_i^2s_{i-1}^3 + 5\sum s_is_{i-1}^4
= 0.\eqno (37)$$

Subtracting (37) from (36) we obtain
$$ 10\sum s_i^4s_{i-1} + 20\sum s_i^2s_{i-1}^3 = 0,$$ or rather
$$20\alpha = -10\sum s_i^4s_{i-1}.\eqno (38)$$
From equations $(35)$ and $(38)$ we deduce
$50\alpha = 0,$ which really asserts that 
$25\alpha = 0.$
When $p = 5$ the result is true by direct calculation 
and so equation (32) is established. Now for equation (33).\v
$$ \sum s_i^2s_{i-1}^3 
= \sum s_{k-i}^2s_{k-i+1}^3(-1)^i = 0$$
by (32). Now reverse the direct of summation -- replacing $k-i$ by $i$
to obtain
$$\sum_{i = 1}^k s_i^2s_{i+1}^3(-1)^i = \sum s_i^3s_{i-1}^2(-1)^{i+1} = 0.$$
Thus (33) is also established and we are done.
$$\eqno \square$$
The proviso that $p \not = 11$ is necessary, since a direct calculation yields
that, in that instance, the sums described in (32) and (33) are, respectively,
5 and 6. 

Corollary\v

Unless the prime $p$ is 11, we have
$$ \sum s_i^4s_{i-1} = 0.\eqno (39) $$
In the event that $p = 11,$ the sum is actually 3.
$$\eqno \square$$

From now on, we will ban the prime 11 from our considerations, since whenever
we have recourse to one of the preceding equations (37),(38) or (39), we would
have to make an exception for that prime.\v
Lemma 3.8 
$$ \sum s_i^3s_{i-1}^2 = 0 \eqno (40)$$
$$ \sum s_i^2s_{i-1}^3(-1)^i = 0 \eqno (41)$$
Proof.\v
We exploit equation (32). We have
$$ \sum s_i^2s_{i-1}^3 = \sum s_{i-1}^3(s_{i-1}+s_{i-2})^2 = 0$$
so
$$\sum s_{i-1}^5 + 2\sum s_{i-1}^4s_{i-2} + \sum s_{i-1}^3s_{i-2}^2 = 0.$$
The first sum vanishes by equation (30) and the second by equation (39).
Thus
$$\sum s_{i-1}^3s_{i-2}^2=\sum s_i^3s_{i-1}^2 = 0$$
and so equation (40) is established.
Now we obtain equation (41) by reversing the direction of summation
in equation (40). We have
$$\sum s_i^3s_{i-1}^2 = \sum s_{k-i}^3s_{k-i+1}^2(-1)^{i+1} = 0.$$

Replacing $k-i$ by $i$ we obtain
$$\sum_{i =1}^k s_i^3s_{i+1}^2(-1)^{i+1} = 0$$
Now replace $i+1$ by $i$ and then slide the range of summation to yield
$$\sum s_i^2s_{i-1}^3(-1)^i = 0$$ as required.
$$\eqno \square$$

Lemma 3.9
$$ \sum s_{i+1} s_i^4 = 0 \eqno (42)$$
$$ \sum s_i^4s_{i-1}(-1)^i = 0 \eqno (43)$$
$$ \sum s_{i+1}s_i^4(-1)^i = 0 \eqno (44)$$

Proof.\v
From equations (39) and (30) we have
$$\sum s_{i+1} s_i^4 = \sum (s_i + s_{i-1})s_i^4 = \sum s_i^5
+\sum s_i^4 s_{i-1} =0.$$
Thus equation (42) is established. 
We have
$$ \sum s_{i+1} s_i^4 = \sum s_{k-i-1}s_{k-i}^4 (-1)^i = 0.$$
Now reverse the direction of summation in the usual way, replacing
$k-i$ by $i$. This yields
$$\sum_{i=1}^k s_{i-1}s_i^4(-1)^i = \sum s_i^4s_{i-1}(-1)^i = 0$$ and
equation (43) is established.
Finally we turn to equation (43) as our route to proving equation (44).
Thus we see that
$$ \sum s_i^4s_{i-1}(-1)^i = \sum s_i^4(s_{i+1} - s_i)(-1)^i = 0.$$ 
Now deploy equations (43) and (31) and we are home.
$$\eqno \square$$

Lemma 3.10 
$$\alpha = \sum s_i^2s_{i-2}^3(-1)^{i+1} = 0. \eqno (45)$$
Proof.\v
$$\alpha = \sum (s_{i-1} + s_{i-2})^2s_{i-2}^3(-1)^{i+1}$$
so
$$\alpha = \sum s_{i-1}^2s_{i-2}^3(-1)^{i+1}
          + 2\sum s_{i-1}s_{i-2}^4(-1)^{i+1}
          +\sum s_{i-2}^5(-1)^{i+1}$$ so
$$\alpha =\sum s_i^2s_{i-1}^3(-1)^i-2\sum s_{i+1}s_i^4(-1)^i-\sum s_i^5(-1)^i
$$
These sums vanish by equations (41), (44) and (31) respectively.
Thus $\alpha = 0$ and we are done.
$$\eqno \square$$

Lemma 3.11 \v This is presumably well-known. For each integer $n$ we have
        $$3s_n^2 = s_{n+1}^2 + s_{n-1}^2 + 2(-1)^{n+1}.\eqno (46)$$ 
Proof.\v This result actually holds in the ordinary Fibonnaci sequence,
and not just modulo a prime $p.$
$$ s_n^2 = (s_{n+1} - s_{n-1})^2 = s_{n+1}^2 + s_{n-1}^2 - 2s_{n+1}s_{n-1}$$
but $s_{n+1}s_{n-1} = s_n^2 + (-1)^n$ by equation (22) so
$$s_n^2 = s_{n+1}^2 + s_{n-1}^2 - 2s_n^2 + 2(-1)^{n+1}$$
and the result follows.
$$\eqno \square$$


On the basis of computational experiments, we propose the following
conjectures.\v

Conjecture 1: If $q$ is prime then $\sum s_i^q = 0$ for all but finitely
many prime moduli $p.$ The evidence for this conjecture is as follows.
We know it holds for primes $q$ less than 7 that the conjecture holds.
For primes $q$ larger than 7 we have computed all values of the
prime modulus $p < 200$ for which the sum $\sum s_i^q$ fails to vanish.
This conjecture looks rather dodgy and we will discard it in published
documents unless we find more compelling arguments. \v

Conjecture 2: The prime moduli causing the sum $\sum s_i^q$ to fail to
vanish must be congruent to $1$ or $-1$ mod 10. 
The data is as follows. NB This need to be more comprehensive.
The data below only includes values of $p$ less than 100.\v
\vfill \eject


$q \ \ \ \  p$\v
$5 \ \ \ \          11$\v
$7 \ \ \ \    11, 29$\v
$11  \ \ \        19, 29$\v
$13  \ \ \       19, 29$\v
$17  \ \ \        11, 19, 29, 31$\v
$19  \ \ \        11, 29, 31$\v
$23  \ \ \        29, 31$\v
$29  \ \ \       11, 19, 31, 59$\v
$31  \ \ \       19, 59$\v
$37  \ \ \       11, 29, 59, 71$\v
$41  \ \ \       29, 59, 71, 79$\v
$43  \ \ \       29, 59, 71, 79$\v 
$47  \ \ \       11, 19, 29, 31, 59, 71 ,79$\v
$53  \ \ \        19, 29, 31, 59, 71, 79$\v 
$59  \ \ \         11, 31, 71, 79$\v
$61  \ \ \       71, 79$\v
$67  \ \ \        11, 19, 29, 71, 79$\v
$71 \ \ \        19, 29, 79$\v
$73 $  \v
\vfill
\eject
We now embark on the study of Fibonacci double sums, and remind the reader that
the primes 2,3 and 11 are barred from our discussions. A typical sum 
is of the form $\sum_{j=0}^{k-1}\sum_{i = 0}^{j-1} f(i,j).$ We
abbreviate the notation for this sum to $\sum_{i<j} f(i,j).$ In the event
that we wish to consider $\sum_{j = 0}^{k-1} \sum_{i=0}^{k-1} f(i,j)$
we will write $\sum_{all} f(i,j).$ As in the case of single sums, we 
will heavily exploit the periodicity of $(s_i),$ and tinker with
ranges of summation. A variety of other tricks is needed too, and we
will introduce such ruses on an {\it ad hoc} basis as the need arises.\v
Lemma 3.12 $$\nu = \sum_{i<j}s_j^2s_{j-i} = 0 \eqno (47)$$
$$ \mu = \sum_{i<j} s_j^2 s_{j-i-1} = 0\eqno (48)$$
Proof.
$$\nu = \sum_{i<j} s_j^2s_{j-i+1} - \sum_{i<j} s_j^2s_{j-i-1}$$
$$ = \sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_{j-i+1}
   - \sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_{j-i-1}$$
$$ = \sum_{j=0}^{k-1}\sum_{i= -1}^{j-2} s_j^2s_{j-i}
   - \sum_{j=0}^{k-1}\sum_{i= 1}^j s_j^2s_{j-i}.$$
We can tinker with the ranges of summation providing we only add or
subtract terms which vanish, or compensate by inserting new sums. Thus 
$$ \nu = (\sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_{j-i}
         +\sum_{j=0}^{k-1} s_j^2 s_{j+1} 
         -\sum_{j=0}^{k-1} s_j^2 s_1)
         - (\sum_{j=0}^{k-1}\sum_{i=0}^{j-1}s_j^2s_{j-i}
           -\sum_{j=0}^{k-1}s_j^3
           +\sum_{j=0}^{k-1} s_j^2s_0).$$ 
In this expression for $\nu,$ the first and fourth terms cancel,
the sixth vanishes since $s_0 = 0,$ and the remaining terms --
the second, third and fifth, 
vanish by equations (12), (2) and (3) respectively. Thus $\nu = 0$
and (47) is established.

We now address $\mu.$
$$\mu = 
\sum_{i<j} s_j^2 s_{j-i-1} = \sum_{j=0}^{k-1}\sum_{i=1}^j s_j^2 s_{j-i}.$$
We slide down the range for $i$ by 1. The case $i = j$ is
harmless since $s_0 = 0.$ Thus
$$\mu = \sum_{i<j}s_j^2s_{j-i} - \sum s_j^3.$$
We deploy equation $(3)$ and equation $(47)$ to deduce
$\mu = \nu = 0,$
and equation (48) is established.
$$\eqno \square$$
Corollary.
$$ \sum_{i<j}  s_j^2 s_{j-i+a} = 0 \ \forall a \in \Z.\eqno (49)$$
This follows from equations (47),(48), the Fibonacci recurrence and 
finite induction.
$$\eqno \square$$
Lemma 3.13 $$\sum_{i<j} s_j^2 s_i^2 s_{j-i-1}(-1)^{j+1} = 0.\eqno (50)$$
Proof.\v  Put $$\psi = \sum_{i<j} s_j^2s_i^2s_{j-i-1}(-1)^{j+1}.$$
Recall equation $(46)$
$$ 3s_n^2 = s_{n+1}^2 + s_{n-1}^2 + 2(-1)^{n+1}\ \ \forall n \in \Z,$$
which will play a central r\^ole in our manipulations.
We introduce some temporary names for various expressions.
$$\alpha = \sum_{i<j} s_{j+1}^2s_i^2s_{j-i-1}(-1)^{j+1},$$
$$\beta = \sum_{i<j} s_{j-1}^2s_i^2s_{j-i-1}(-1)^{j+1}$$
and $$\gamma = \sum_{i<j}s_i^2s_{j-i-1}.$$ 
Let $\theta = 3\psi$ then
$$\theta = \alpha + \beta + 2\gamma,$$
by recasting $3s_j^2$ using equation $(46).$ The previous lemma (equation (48))
shows that $\gamma = 0$ so $\theta = \alpha + \beta.$
Now
$$\alpha = \sum_{i<j}s_{j+1}^2s_i^2s_{j-i-1}(-1)^{j+1}
= \sum_{j=1}^k\sum_{i=0}^{j-2}s_j^2s_i^2s_{j-i-2}(-1)^j.$$
There is no problem in adjusting the range for $j$ since $s_0 = s_k = 0.$
Thus
$$ \alpha = \sum_{j=0}^{k-1}\sum_{i=0}^{j-2}s_j^2s_i^2s_{j-i-2}(-1)^j.
$$
Now we wish to add $j-1$ to the range of $i;$ this too is fine
since it involves the creation of the extra term
$$\sum_{j=0}^{k-1}s_j^2s_{j-1}^2s_{-1}(-1)^j.$$
This vanishes by equation (29).
Thus $$\alpha = \sum_{i<j} s_j^2s_i^2s_{j-i-2}(-1)^j. \eqno (51)$$

We now give $\beta$ similar treatment.
$$\beta = \sum_{i<j}s_{j-1}^2s_i^2s_{j-i-1}(-1)^{j+1}
= \sum_{j=-1}^{k-2} \sum_{i=0}^j s_j^2s_i^2s_{j-i}(-1)^j  .$$ 
We can remove $-1$ from the range of $j$ since there are no
legal values of $i$ less than $0.$ We wish to introduce $k-1$
into the range of $j.$ This creates an extra term
$$ \sum_{i=0}^{k-1} s_{k-1}^2s_i^2s_{k-i-1}(-1)
 = \sum s_i^2s_{i+1}(-1)^{i+1}. $$
This last sum vanishes by equation (20). The removal of $j$ from the range
of $i$ is harmless since $s_0 = 0.$
Thus we may write $$\beta = \sum_{i<j} s_j^2s_i^2s_{j-i}(-1)^j.\eqno (52)$$

We are roughly half way through this proof. Now, in the spirit of justice,
we start again, this time giving $i$ the treatment previously meted
out to $j.$
$$ \theta = \delta + \epsilon +2 \zeta$$
where
$$ \delta = \sum_{i<j} s_j^2s_{i+1}^2s_{j-i-1}(-1)^{j+1},$$
$$ \epsilon = \sum_{i<j} s_j^2s_{i-1}^2s_{j-i-1}(-1)^{j+1}$$
and 
$$ \zeta = \sum_{i<j} s_j^2s_{j-i-1}(-1)^{i+j}.$$
As might be expected, $\zeta$ is the easiest term to deal with, and so we
tackle it first. We are introducing a new type of ruse here, so the
reader may wish to be especially alert. Of course we could prove
that $\zeta = 0$ by a direct method, but the following technique
illustrates a new weapon at our disposal.
$$\zeta = \sum_{i<j} s_j^2s_{j-i-1}(-1)^{i+j}
= \sum_{i<j} s_j^2s_{i-j+1}$$ so
$$\zeta = \sum_{j=0}^k\sum_{i=0}^{j-1}s_j^2s_{i-j+1}$$
since $s_k = 0.$ Now prepare to reverse direction of summation. We have
$$\zeta = \sum_{j=0}^k\sum_{i=0}^{j-1} s_{k-j}^2s_{(k-j)-(k-i)+1}.$$
We replace $k-j$ by $j$ and $k-i$ by $i$ to yield
$$\zeta = \sum_{i=0}^k\sum_{j=0}^{i-1} s_j^2 s_{j-i+1}.$$
The clean way to see that this ruse is legitimate is to
realize that we were summing over all pairs $(i,j)$ in the range
$0 \le i < j \le k.$ This is the same as the range
$0 \le k-j < k-i \le k.$
Thus $$\zeta = \sum_{j<i}s_j^2 s_{j-i+1} + \sum s_j^2s_{j-k+1}.$$
The final sum in this last equation is really 
$\sum s_j^2s_{j+1}$ which vanishes by equation (12). We can shave of
the top of the range of $i$ by equation (18). We conclude that
$$\zeta = \sum_{j<i} s_j^2 s_{j-i+1} = \sum_{all} s_j^2 s_{j-i+1}
- \sum_{i<j}  s_j^2 s_{j-i+1} - \sum s_j^2s_1.$$
The second and third terms on the right vanish by equations
(49) and (2) respectively. Thus  we deduce that
$$\zeta = \sum_{j=0}^{k-1} s_j^2 (\sum_{i=0}^{k-1} s_{j-i+1}).$$
The inner sum is really just $\sum s_i$ which vanishes by equation (1).
Thus we have shown that $\zeta = 0.$
 
We conclude that $\theta = \delta + \epsilon.$ Now we work on $\delta.$
Notice that
$$\delta = \sum_{i<j}s_j^2s_{i+1}^2s_{j-i-1}(-1)^{j+1}
= \sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_{i+1}^2s_{j-i-1}(-1)^{j+1}.$$
Now change variable $i$ in the sum to obtain
$$\delta = \sum_{j=0}^{k-1}\sum_{i=1}^js_j^2s_i^2s_{j-i}(-1)^{j+1}.$$
Now we can slide the range of $i$ down by 1 at both ends
since  $s_0 = 0.$
Thus $$\delta = \sum_{i<j}s_j^2s_i^2s_{j-i}(-1)^{j+1} = -\beta.\eqno (53)$$ 
by equation (52).
Thus $\delta = -\beta.$ On this bright note, we set off in pursuit of
$\epsilon.$
$$\epsilon = \sum_{i<j}s_j^2s_{i-1}^2s_{j-i-1}(-1)^{j+1}
= \sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_{i-1}^2s_{j-i-1}(-1)^{j+1}.$$
Changing variable as before, we obtain
$$\epsilon = \sum_{j=0}^{k-1} \sum_{i=-1}^{j-2}
 s_j^2s_i^2s_{j-i-2}(-1)^{j+1}.$$
Once again we would like to slide the range of $i$ by 1, but this time
upwards. When we fix $i = -1$ the contribution to the sum is
$$\sum s_j^2 s_{-1}^2s_{j-1}(-1)^{j+1}$$
which vanishes by equation (19). When we put $i=j-1$ the contribution
is
$$\sum s_j^2s_{j-1}^2s_{-1}(-1)^{j+1}.$$
This vanishes by equation (29).
We conclude that
$$\epsilon = \sum_{i<j} s_j^2s_i^2s_{j-i-2}(-1)^{j+1} = -\alpha,$$
by equation (51).
Pulling things together, we obtain
$$\theta = \alpha + \beta = -(\delta + \epsilon) = -\theta.$$
Thus $\theta = 0,$ and so $\psi = 0$ and we are done.
$$\eqno \square$$

Corollary.\v
$$ \zeta = \sum_{i<j} s_j^2s_{j-i-1}(-1)^{i+j} = 0. \eqno (54)$$

Lemma 3.14 \v Using the notation of the previous lemma
$$\alpha = \sum_{i<j} s_{j+1}^2 s_i^2 s_{j-i-1} (-1)^{j+1} = 0.\eqno (55)$$
$$\beta = \sum_{i<j} s_{j-1}^2 s_i^2 s_{j-i-1} (-1)^{j+1} = 0.\eqno (56)$$ 
Proof.\v In the proof of the previous lemma we obtained
$\alpha + \beta = 0.$ Also, using equations (52) and (53) we have
$$\beta - \alpha = \sum_{i<j}s_j^2s_i^2s_{j-i}(-1)^j 
-\sum_{i<j}s_j^2s_i^2s_{j-i-2}(-1)^j = \sum_{i<j} s_j^2s_i^2s_{j-i-1}(-1)^j
= -\psi = 0.$$
Thus $\alpha = \beta = 0.$
$$\eqno \square$$
Corollary:
$$\sum_{i<j} s_j^2s_i^2s_{j-i+a}(-1)^{j+1} = 0 \ \ \forall a \in \Z.\eqno (57)$$
This follows from equations (50),(51) and (55), the Fibonacci 
recurrence and finite induction.
$$\eqno \square$$ 
Lemma 3.15 
$$\sum_{i<j} s_js_{j+1}s_i^2s_{j-i-1}(-1)^{j+1} = 0.\eqno (58)$$
Proof.\v Temporarily put
$$\lambda = \lambda(i,j) = s_i^2s_{j-i-1}(-1)^{j+1}.$$
The previous two lemmas tell us (via equations (56),(50) and (54)) that
$$\sum_{i<j} s_{j-1}^2\lambda = \sum_{i<j} s_j^2\lambda = 
\sum_{i<j} s_{j+1}^2\lambda = 0.$$
Now $$2\sum_{i<j} s_js_{j+1}\lambda = -\sum_{i<j} (s_{j+1} - s_j)^2\lambda
= - \sum_{i<j} s_{j-1}^2 \lambda = 0.$$
The final equality is simply equation (56), and we are done.
$$\eqno \square$$

Corollary:\v

$$\sum_{i<j} s_js_{j+a}s_i^2s_{j-i-1}(-1)^{j+1} = 0 \ \ \forall a \in \Z.
\eqno (59)$$ 
$$\eqno \square$$
Lemma 3.16 
$$\sum_{i<j} s_js_i^2s_{j-i+a} = 0\ \ \forall \ a \in \Z. \eqno (60)$$
Proof.\v
Put
$$\alpha = \sum_{i<j} s_js_i^2s_{j-i+a} = \sum_{i<j}s_{j+1}s_i^2s_{j-i+a}
- \sum_{i<j} s_{j-1}s_i^2s_{j-i+a}.$$
Thus
$$\alpha = \sum_{j=1}^k\sum_{i=0}^{j-2}s_js_i^2s_{j-i+a-1}
-\sum_{j=-1}^{k-2}\sum_{i=0}^j s_js_i^2s_{j-i+a+1},$$
by adjusting the ranges of $i$ and $j.$ Now we immediately
deduce
$$\alpha = \sum_{j=0}^{k-1}\sum_{i=0}^{j-2} s_js_i^2s_{j-i+a-1}
         - \sum_{j=0}^{k-2}\sum_{i=0}^j s_js_i^2s_{j-i + a+ 1}$$
by removing and introducing vanishing terms.
Now
$$\sum_{j=0}^{k-1}\sum_{i=0}^{j-2}s_js_i^2s_{j-i+a-1}
= \sum_{i<j}s_js_i^2s_{j-i+a-1} - \sum_{j=0}^{k-1} s_js_{j-1}^2s_a.$$
The last term vanishes by equation (12) so
$$\sum_{j=0}^{k-1}\sum_{i=0}^{j-2}s_js_i^2s_{j-i+a-1} =
\sum_{i<j} s_js_i^2s_{j-i+a-1}.$$
We now attack the second sum in our expression for $\alpha.$ We see that
$$\sum_{j=0}^{k-2}\sum_{i=0}^j s_js_i^2s_{j-i+a+1}
= \sum_{j= 0}^{k-1} \sum_{i=0}^j s_js_i^2s_{j-i+a+1} - \sum_{i=0}^{k-1} s_{k-1}s_i^2s_{k-i+a}.$$
The final sum being subtracted is tractable. It is simply
$$\sum_{i=0}^{k-1}s_{k-1}s_i^2s_{i-a}(-1)^{i-a+1},$$
and this vanishes by
equation $(21).$
We deduce that
$$ \alpha =\sum_{j= 0}^{k-1}  \sum_{i=0}^j s_js_i^2s_{j-i+a+1}
= \sum_{i<j}s_js_i^2s_{j-i+a+1} + \sum s_j^3s_{a+1}.$$
The last term vanishes by equation (3), and so we have
$$\alpha = \sum_{i<j} s_js_i^2s_{j-i+a-1} - \sum_{i<j}s_js_i^2s_{j-i+a+1}.$$
Now $s_{j-i+a-1} - s_{j-i+a+1} = -s_{j-i+a}$ so
$$\alpha = - \sum_{i<j} s_js_i^2 s_{j-i+a} = -\alpha.$$
Thus $\alpha = 0$ as required.
$$\eqno \square$$

Lemma 3.17 $$\sum_{i<j} s_j^2s_{j-i-1}s_i(-1)^{i+j} = 0.\eqno (61)$$
Proof.\v Let $$\alpha = \sum_{i<j} s_j^2s_{j-i-1}s_i(-1)^{i+j},$$
so $$\alpha = \sum_{i<j} s_j^2s_is_{i-j+1}.$$
Now $$\sum_{all} s_j^2s_is_{i-j+1} = 
\sum_{all}s_j^2s_is_{j-i-1}(-1)^{i+j}= 
\sum_{i=0}^{k-1} s_i(-1)^i(\sum_{j=0}^{k-1} s_j^2s_{j-i-1}(-1)^j),$$ 
but the inner sum vanishes thanks to equation (21). Thus we have
$$\sum_{all} s_j^2s_is_{i-j+1} = 0.$$
Our intention is to use the following trick -- the meaning of which
should be self evident --
$$ \sum_{all} = \sum_{i<j} + \sum_{j<i} + \sum_{i=j}.$$
We must investigate the sum when $i = j.$ This is just
$$ \sum s_i^2 s_i s_1 = \sum s_i^3 = 0,$$
which vanishes because of equation (3).
We conclude that
$$ \alpha = - \sum_{j<i} s_j^2s_is_{i-j+1} = -\sum_{i<j} s_js_i^2s_{j-i+1}.$$
The final equality is obtained by permuting notation. 
Thus $$\alpha = -\sum_{i<j} s_js_i^2s_{j-i+1}$$
which vanishes by equation (60).
$$\eqno \square$$

Lemma 3.18 $$\sum_{i<j} s_j^2s_is_{i-1}s_{j-i-1}(-1)^{j+1} \eqno (62)$$
Proof.\v

Let $$\alpha = \sum_{i<j} s_j^2s_is_{i-1} s_{j-i-1}(-1)^{j+1}.$$
Using $s_{i-1} = s_i - s_{i-2}$ and the equation (50) we obtain
$$\alpha = \sum_{i<j} s_j^2 s_i s_{i-2}s_{j-i-1}(-1)^j.$$
Now use equation (22) so
$$\alpha = \sum_{i<j} s_j^2 s_{i-1}^2 s_{j-i-1}(-1)^j -
\sum s_j^2s_{j-i-1}(-1)^{i+j}.$$
The last term vanishes by equation (54).
Now 
$$ \alpha = \sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_{i-1}^2s_{j-i-1}(-1)^j$$
so$$\alpha = \sum_{j=1}^k\sum_{i=1}^{j-1}s_{j+1}^2s_i^2s_{j-i-1}(-1)^{j+1}.$$
Adjusting the ranges we have
$$\alpha = \sum_{i<j} s_{j+1}^2s_i^2s_{j-i-1}(-1)^{j+1}
+ \sum s_{k+1}^2s_i^2s_{k-i-1},$$
so $$\alpha = \sum_{i<j} s_{j+1}^2s_i^2s_{j-i-1}(-1)^{j+1}
+ \sum s_{i+1}s_i^2(-1)^i.$$
These last two terms vanish by (55) and (20) so  $\alpha = 0$ and we are done.
$$\eqno \square$$

Lemma 3.19 

$$6s_js_{j-1}^2 = s_{j+1}^3 + s_{j-2}^3 - 2s_j^3\ \ \forall j \in \Z.
\eqno (63)$$

Proof.\v
For each integer $j$ we have
$$s_{j+1}^3 + s_{j-2}^3 - 2s_j^3 
= (s_j + s_{j-1})^3 + (s_j - s_{j-1})^3 - 2s_j^3
= 6s_js_{j-1}^2.$$
$$\eqno \square$$ 

Lemma 3.20

$$6s_j^2s_{j-1} = s_{j+1}^3 - s_{j-2}^3 - 2s_{j-1}^3\ \ \forall j \in \Z.
\eqno (64)$$

Proof.
For each integer $j$ we have
$$s_{j+1}^3 - s_{j-2}^3 - 2s_{j-1}^3
= (s_j + s_{j-1})^3 - (s_j - s_{j-1})^3 - 2s_{j-1}^3 = 6s_j^2s_{j-1}.$$
$$\eqno \square$$

Lemma 3.21
$$\sum_{i<j} s_j^2s_{j-i+a}s_is_{i-1}^2(-1)^{j+1} = 0
\ \ \forall a \in \Z. \eqno (65)$$

Proof.\v
Put
$$\alpha = 6\sum_{i<j} s_j^2s_{j-i+a}s_is_{i-1}^2(-1)^{j+1} $$
$$ = \sum_{i<j} s_j^2s_{j-i+a}s_{i+1}^3 (-1)^{j+1}+ 
\sum_{i<j}s_j^2s_{j-i+a}s_{i-2}^3(-1)^{j+1}
-2 \sum_{i<j} s_j^2s_{j-i+a}s_i^3(-1)^{j+1}.$$
Now fiddle with the range of summation for $i.$
$$\alpha = \sum_{j=0}^{k-1}\sum_{i=1}^js_j^2s_{j-i+a+1}s_i^3(-1)^{j+1}
+\sum_{j=0}^{k-1}\sum_{i= -2}^{j-3} s_j^2s_{j-i+a-2}s_i^3(-1)^{j+1}$$ $$
- 2\sum_{i<j} s_j^2s_{j-i+a}s_i^3(-1)^{j+1}.
\eqno (66)$$

We deal with these three double sums in equation (66) 
individually. The first one is
$$\sum_{j=0}^{k-1}\sum_{i=1}^j s_j^2s_{j-i+a+1}s_i^3(-1)^{j+1}
= \sum_{i<j} s_j^2s_{j-i+a+1}s_i^3(-1)^{j+1}
+ \sum_{j=0}^{k-1} s_{a+1}s_j^5(-1)^{j+1}.$$
The last term vanishes by (31) so
$$\sum_{j=0}^{k-1}\sum_{i=1}^j s_j^2s_{j-i+a+1}s_i^3(-1)^{j+1}
= \sum_{i<j} s_j^2s_{j-i+a+1}s_i^3(-1)^{j+1}.\eqno (67)$$
Now for the second term in equation (66). We have
$$\sum_{j=0}^{k-1}\sum_{i=-2}^{j-3} s_j^2s_{j-i+a-2}s_i^3(-1)^{j+1}
= \sum_{i<j} s_j^2s_{j-i+a-2}s_i^3(-1)^{j+1}
-\sum s_j^2s_as_{j-2}^3(-1)^{j+1}$$ $$
- \sum s_j^2s_{a-1}s_{j-1}^3(-1)^{j+1}
+ \sum \sum s_j^2s_{j+a}s_{-2}^3(-1)^{j+1}
+ \sum s_j^2s_{j+a+1}s_{-1}^3(-1)^{j+1}.$$ 
The last four terms vanish by equations (45),
(41),(21),and (21) respectively, so
$$\sum_{j=0}^{k-1}\sum_{i=-2}^{j-3} s_j^2s_{j-i+a-2}s_i^3(-1)^{j+1}
= \sum_{i<j} s_j^2s_{j-i+a-2}s_i^3(-1)^{j+1}. \eqno (68)$$

Thus from equations (66),(67) and (68) we have 
$$\alpha = \sum_{i<j} s_j^2s_i^3(-1)^{j+1}(s_{j-i+a+1} + s_{j-i+a-2}
- 2s_{j-i+a}).$$

However,
$$s_{j-i+a+1} + s_{j-i+a-2} - 2s_{j-i+a} =
  (s_{j-i+a+1} - s_{j-i+a}) -(s_{j-i+a} - s_{j-i+a-2})$$
$$ = s_{j-i+a-1} - s_{j-i+a-1} = 0.$$
Thus $\alpha = 0$ and we are done.
$$\eqno \square$$

Lemma 3.22\v
NB There are  sign errors in this proof. They require correction...
$$\sum_{i<j} s_j^2 s_{j-1} s_i^2 s_{j-i+a} (-1)^{j+1} = 0
\ \ \forall a \in \Z. \eqno (69)$$ 
Proof.\v The proof is similar to that of lemma 3.21, but 
this time we exploit lemma 3.20 rather than lemma 3.19. 
Put $$\alpha = 6\sum_{i<j}s_j^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1},$$ 
$$\beta  = \sum_{i<j}s_j^3s_i^2s_{j-i+a-1}(-1)^j,$$
$$\gamma = \sum_{i<j}s_j^3s_i^2s_{j-i+a+2}(-1)^j$$
$$\delta = \sum_{i<j}s_j^3s_i^2s_{j-i+a+1}(-1)^j.$$
Now we introduce more notation. 
Put $$\beta_1 = \sum_{j=1}^k\sum_{i=0}^{j-2}s_j^3s_i^2s_{j-i+a-1}(-1)^j,$$
$$\gamma_1 = \sum_{j=-2}^{k-3}\sum_{i=0}^{j+1}s_j^3s_i^2s_{j-i+a+2}(-1)^j$$ 
and 
$$\delta_1 = \sum_{j=-1}^{k-2}\sum_{i=0}^js_j^3s_i^2s_{j-i+a+1}(-1)^j.$$ 
Equation (64) yields that
$$\alpha = \sum_{i<j}s_{j+1}^3s_i^2s_{j-i+a}(-1)^{j+1}
          -\sum_{i<j}s_{j-2}^3s_i^2s_{j-i+a}(-1)^{j+1}$$ $$
          -2\sum_{i<j}s_{j-1}^3s_i^2s_{j-i+a}(-1)^{j+1}.$$
Recasting the ranges of summation for $j$ we obtain
$$\alpha =  \sum_{j=1}^k\sum_{i=0}^{j-2}s_j^3s_i^2s_{j-i+a-1}(-1)^j
+  \sum_{j=-2}^{k-3}\sum_{i=0}^{j+1}s_j^3s_i^2s_{j-i+a+2}(-1)^j$$
$$ -  2\sum_{j=-1}^{k-2}\sum_{i=0}^js_j^3s_i^2s_{j-i+a+1}(-1)^j \eqno (70)$$
or rather
$$\alpha = \beta_1 + \gamma_1 -2 \delta_1.$$
We must simplify each sum on the right. We 
take them in sequence. First
we have
$$\beta_1 = \beta - \sum s_j^3s_{j-1}^2s_a(-1)^j.$$
The last expression vanishes by (33) so $\beta_1 = \beta.$
We now approach $\gamma_1.$ We have
$$\gamma_1 = \sum_{j=0}^{k-3}\sum_{i=0}^{j+1} s_j^3s_i^2s_{j-i+a+2}(-1)^j$$
so
$$\gamma_1 = \sum_{j=0}^{k-1}\sum_{i=0}^{j+1} s_j^3s_i^2s_{j-i+a+2}(-1)^j 
- \sum s_{k-2}^3s_i^2s_{k-i+a} + \sum_{i=0}^k s_{k-1}^3s_i^2s_{k-i+a+1}.$$
$$ = \sum_{j=0}^{k-1}\sum_{i=0}^{j+1} s_j^3s_i^2s_{j-i+a+2}(-1)^j
  +\sum s_i^2s_{i-a}(-1)^{i-a+1} + \sum s_i^2 s_{i-a-1}(-1)^{i-a}.$$
The last two sums vanish by (21) so
$$\gamma_1 = \sum_{j=0}^{k-1}\sum_{i=0}^{j+1} s_j^3s_i^2s_{j-i+a+2}(-1)^j.$$
We need to attenuate the range of $j.$ We accomplish this task thus --
$$\gamma_1 = \gamma + \sum s_j^5s_{a+2}(-1)^j 
+ \sum s_j^3s_{j+1}^2 s_{a+3}(-1)^j.$$ 
Once again the last two sums vanish, this time because of (31) and (41).
We may conclude that $\gamma_1 = \gamma.$
Next we tackle $\delta_1.$ We have
$$\delta_1 =  \sum_{j=-1}^{k-2}\sum_{i=0}^js_j^3s_i^2s_{j-i+a+1}(-1)^j$$ so
$$\delta_1 = \sum_{j=0}^{k-1}\sum_{i=0}^j s_j^3s_i^2 s_{j-i+a+1}(-1)^j
 - \sum_{i=0}^{k-1} s_{k-1}^3s_i^2s_{k-i+a}(-1)^{k-1}$$
$$ =\sum_{j=0}^{k-1}\sum_{i=0}^j s_j^3s_i^2 s_{j-i+a+1}(-1)^j
+ \sum s_i^2s_{i-a}(-1)^{i-a+1}.$$

The last term vanishes by (21) again.
Thus we have
$$\delta_1 = \sum_{j=0}^{k-1}\sum_{i=0}^j s_j^3s_i^2 s_{j-i+a+1}(-1)^j.$$
We now shrink the range of $i$ and so 
$$\delta_1 = \delta - \sum s_j^5s_{a+1}(-1)^j.$$
The last term vanishes by (31) so $\delta_1 = \delta.$
Thus $$\alpha = \beta_1 + \gamma_1 - 2\delta_1 = \beta + 
\gamma - 2\delta. $$
Now we can deduce that
$$\alpha = \sum_{i<j<r} s_j^3s_i^2(s_{j-i+a-1}
+s_{j-i+a+2} - 2s_{j-i+a+1})(-1)^j.$$
The expression in brackets vanishes by the Fibonacci recurrence because
$$ (s_{j-i+a-1}
+s_{j-i+a+2} - 2s_{j-i+a+1})
=(s_{j-i+a-1} - s_{j-i+a+1}) + (s_{j-i+a+2} - s_{j-i+a+1})$$
$$ = -s_{j-i+a} +s_{j-i+a} = 0.$$
Now we are
done.
$$\eqno \square$$

Lemma 3.23\v
For every integer $a$ we have
$$ \sum_{i<j} s_j^3s_i^2s_{j-i+a}(-1)^{j+1} = 0. \eqno (71)$$

Proof.\v
 Let
$$\alpha =\sum_{i<j} s_j^3s_i^2s_{j-i+a}(-1)^{j+1} $$
then
$$\alpha = \sum_{i<j}(s_{j+1}-s_{j-1})^3s_i^2s_{j-i+a}(-1)^{j+1}$$
so
$$\alpha = \sum_{i<j}s_{j+1}^3s_i^2s_{j-i+a}(-1)^{j+1}
          -3\sum_{i<j}s_{j+1}^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1}$$ $$
          +3\sum_{i<j}s_{j+1}s_{j-1}^2s_i^2s_{j-i+a}(-1)^{j+1}
	  -\sum_{i<j}s_{j-1}^3s_i^2s_{j-i+a}(-1)^{j+1}.$$
We now adjust ranges of summation. We have
$$\alpha  = \sum_{j=1}^k\sum_{i=0}^{j-2} s_j^3s_i^2s_{j-i+a-1}(-1)^j
	-3\sum_{i<j} (s_j^2 + (-1)^j)s_{j+1}s_i^2s_{j-i+a}(-1)^{j+1}$$ $$
        +3\sum_{i<j} (s_j^2 + (-1)^j)s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1}
         - \sum_{j=-1}^{k-2}\sum_{i=0}^j s_j^3s_i^2s_{j-i+a+1}(-1)^j. \eqno (*)$$
We examine the four sums in (*) separately.
We have $$\alpha = \beta - 3\gamma + 3\delta - \epsilon$$
in the obvious notation. We have 
$$\beta = \sum_{j=1}^k\sum_{i=0}^{j-2} s_j^3s_i^2s_{j-i+a-1}(-1)^j$$
so $$\beta = \sum_{j=0}^{k-1}\sum_{i=0}^{j-2}s_j^3s_i^2s_{j-i+a-1}(-1)^j$$
since $s_0 = 0.$ Now adjust the range of $i,$
so $$\beta = \sum_{i<j}s_j^3s_i^2s_{j-i+a-1}(-1)^j 
	-\sum s_j^3s_{j-1}^2s_a(-1)^j.$$
The final term in the last equation vanishes by equation (33) so
$$\beta  = \sum_{i<j}s_j^3s_i^2s_{j-i+a-1}(-1)^j.$$
Next we approach $\epsilon.$ We have
$$\epsilon =\sum_{j=-1}^{k-2}\sum_{i=0}^j s_j^3s_i^2s_{j-i+a+1}(-1)^j$$
so $$\epsilon = \sum_{j=0}^{k-1}\sum_{i=0}^j s_j^3s_i^2s_{j-i+a+1}(-1)^j
- \sum s_{k-1}^3s_i^2s_{k-i+a}(-1)^{k-1}.$$
The final term is, up to sign,

$$\sum s_i^2s_{i-a}(-1)^i$$ which vanishes by equation (21). 
Thus $$\epsilon =  \sum_{j=0}^{k-1}\sum_{i=0}^j s_j^3s_i^2s_{j-i+a+1}(-1)^j,$$
so adjusting the range of $i$ we obtain
$$\epsilon = \sum_{i<j} s_j^3s_i^2s_{j-i+a+1}(-1)^j + \sum s_j^5s_{a+1}(-1)^j.$$
The last sum vanishes by equation (31).
It is now clear that
$$\beta - \epsilon = \sum_{i<j}s_j^3s_i^2s_{j-i+a-1}(-1)^j
-  \sum_{i<j} s_j^3s_i^2s_{j-i+a+1}(-1)^j$$
so 
$$\beta - \epsilon = \sum_{i<j}s_j^3s_i^2s_{j-i+a}(-1)^{j+1} = \alpha.$$
We now approach $\gamma$ and $\delta.$
$$\gamma = \sum_{i<j} (s_j^2 + (-1)^j)s_{j+1}s_i^2s_{j-i+a}(-1)^{j+1}$$
so $$\gamma = \sum_{i<j} s_j^2s_{j+1}s_i^2s_{j-i+a}(-1)^{j+1}
+ \sum_{i<j} s_{j+1}s_i^2s_{j-i+a}(-1).$$

Similarly
$$\delta = \sum_{i<j} s_j^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1}
+ \sum_{i<j} s_{j-1}s_i^2s_{j-i+a}(-1).$$
Thus
$$\gamma - \delta = \sum_{i<j}s_j^3s_i^2s_{j-i+a}(-1)^{j+1} 
 - \sum_{i<j} s_js_i^2s_{j-i+a}.$$
The final term of the last equation vanishes by
equation (60).
Thus $$\gamma  - \delta= \sum_{i<j}s_j^3s_i^2s_{j-i+a}(-1)^{j+1} = \alpha.$$
From equation (*) we deduce that
$$\alpha = \beta - \epsilon - 3(\gamma - \delta)$$
so
$$\alpha = \alpha - 3\alpha  = -2\alpha.$$
It follows that $3\alpha = 0$ and we are done.
$$\eqno \square$$


Lemma 3.24\v

$$\sum_{i<j} s_{j+b}s_js_{j-i+a}s_i^3(-1)^{j+1}. \eqno (72)$$

Proof.\v

We establish this by showing

$$\sum_{i<j} s_j^2s_{j-i+a}s_i^3(-1)^{j+1}=0\eqno (*)$$

and

$$\sum_{i<j} s_{j+1}s_js_{j-i+a}s_i^3(-1)^{j+1}=0\eqno (**)$$

for all integers $a$ and $b.$ From now on , in the course of this proof
we will omit to mention that in all equations involving $a$ and $b,$
the values of $a$ and $b$ are arbitrary integers.

The result follows from  (*) and (**), the 
Fibonacci recurrence and finite induction.
Recall equation (65) which asserts that

$$ \sum_{i<j} s_j^2s_{j-i+a}s_is_{i-1}^2(-1)^{j+1} = 0.$$

Reverting to detailed notation, this asserts that

$$ \sum_{j=0}^{k-1}\sum_{i=0}^{j-1}  s_j^2s_{j-i+a}s_is_{i-1}^2(-1)^{j+1} = 0 
,$$
and changing a variable this means that
$$ \sum_{j=0}^{k-1}\sum_{i=-1}^{j-2} 
 s_j^2s_{j-i+a-1}s_{i+1}s_i^2(-1)^{j+1} = 0.$$
Now remove the edge effects from this last sum. We have
$$\sum_{j=0}^{k-1}\sum_{i=-1}^{j-2}
 s_j^2s_{j-i+a-1}s_{i+1}s_i^2(-1)^{j+1}
= \sum_{i<j} s_j^2s_{j-i+a-1}s_{i+1}s_i^2(-1)^{j+1}
$$ $$ + \sum s_j^2s_{j+a}s_0s_{-1}^2(-1)^{j+1}
 - \sum s_j^2s_as_js_{j-1}^2(-1)^{j+1}.$$
The final two sums vanish because $s_0 = 0,$
and equation (33) applies (respectively).
We may add 1 to $a$ since it is arbitrary, and deduce that

$$\sum_{i<j} s_j^2s_{j-i+a}s_{i+1}s_i^2(-1)^{j+1}=0 \eqno (73).$$

Now recall equation (69) which asserts that

$$\sum_{i<j} s_j^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1} = 0.$$

We use the $\sum_{all} = \sum_{i<j} + \sum_{j<i} - \sum_{i=j}$ trick.
Now we have
$$\sum_{all}s_j^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1} =
\sum_{j=0}^{k-1}s_j^2s_{j-1}(-1)^{j+1}(\sum_{i=0}^{k-1}
s_i^2s_{i-j-a}(-1)^{i-j-a+1}).$$
The inner sum vanishes by equation (21) so
$$\sum_{all}s_j^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1} =0.$$
Now consider the contribution when $i=j$. This is
$$\sum s_i^4s_{i-1}s_a(-1)^{i+1}$$
which vanishes by equation (43).
We may conclude that
$$\sum_{j<i} s_j^2s_{j-1}s_i^2s_{j-i+a}(-1)^{j+1} = 0.$$
Now change the r\^oles of $i$ and $j$ in this equation to obtain
$$\sum_{i<j}s_j^2s_{i-j+a}s_i^2s_{i-1}(-1)^{i+1} = 0$$
which equally well asserts that
$$\sum_{i<j}s_j^2s_{j-i+a}s_i^2s_{i-1}(-1)^{j+1} = 0 \eqno (74). $$
We have spun the term $s_{i-j+a}$ to $s_{j-i-a},$ replaced $a$ by $-a$,
and mulitiplied by $-1$ if necessary. 

Subtracting equation (74) from equation (73) we obtain equation (*).
We now address equation (**) using our new found faith in equation (*).
We know from equation (*) that
$$ \sum_{i<j} s_j^2s_{j-i+a}s_i^3(-1)^{j+1}=0,$$
so we may change the variable $j$ to deduce that
$$ \sum_{j=-1}^{k-2}\sum_{i=0}^j s_{j+1}^2s_{j-i+a+1} s_i^3(-1)^j =0.$$
Now the range of summation for $j$ can be slipped up by 1 without
damage,
so
$$\sum_{j=0}^{k-1}\sum_{i=0}^j s_{j+1}^2s_{j-i+a+1} s_i^3(-1)^j =0.$$
iNow eliminate the edge effect. Our latest equation can be written
$$\sum_{i<j}s_{j+1}^2s_{j-i+a+1} s_i^3(-1)^j
- \sum s_{j+1}^2s_{a+1}s_j^3(-1)^j = 0.$$ The final term vanishes by
equation (41) so
$$\sum_{i<j}s_{j+1}^2s_{j-i+a+1} s_i^3(-1)^{j+1} = 0. \eqno (75)$$
We have subtracted 1 from $a$ and multiplied by $-1$.

Now repeat this last enterprise, this time changing the variable $j$ in
the opposite direction. We have
$$ \sum_{i<j} s_j^2s_{j-i+a}s_i^3(-1)^{j+1}=0,$$
so replacing $j$ by $j-1$ we see that
$$\sum_{j=1}^k\sum_{i=0}^{j-2}s_{j-1}^2s_{j-i+a-1}s_i^3(-1)^j = 0.$$
Thus
$$\sum_{j=1}^k\sum_{i=0}^{j-1}s_{j-1}^2s_{j-i+a-1}s_i^3(-1)^j
- \sum s_{j-1}^2s_as_{j-1}^3(-1)^j = 0$$
The final term vanishes by equation (31). Knocking 0 off the range
of $j$ is harmless since there are no legal values of $i$ when
$j = 0,$ so we only have to worry about what happens when $j =k.$ Thus
$$\sum_{i<j}s_{j-1}^2s_{j-i+a-1}s_i^3(-1)^j
+ \sum s_{k-1}^2s_{k-i+a-1}s_i^3 = 0.$$
Now $$\sum s_{k-1}^2s_{k-i+a-1}s_i^3 = \sum s_{i-a+1}s_i^3(-1)^{i+a}$$
which vanishes by equations (23) and (28), and a finite induction.
We deduce that
$$\sum_{i<j}s_{j-1}^2s_{j-i+a}s_i^3(-1)^{j+1} = 0 \eqno (76).$$
We have added 1 to $a$ and multiplied by $-1$. 
Now $$2s_{j+1}s_j = -(s_{j+1} - s_j)^2 + s_{j+1}^2 + s_j^2
= s_{j+1}^2 + s_j^2 - s_{j-1}^2.$$
Thus 
adding equations (75) and (*), then subtracting equation (76)
we obtain
$$2\sum_{i<j}s_{j+1}s_js_{j-i+a}s_i^3(-1)^{j+1}=0$$
and we are done.
$$\eqno \square$$ 

Lemma 3.25

$$\sum_{i<j<r} s_{r-j-1}s_js_i^2s_{j-i-1} = 0.\eqno (77)$$

Proof.\v
We put
$$\alpha = \sum_{i<j<r} s_{r-j-1}s_js_i^2s_{j-i-1} 
= \sum_{i<j<r} s_{r-j}s_js_i^2s_{j-i-1} 
- \sum_{i<j<r} s_{r-j-2}s_js_i^2s_{j-i-1}.$$
Now adjust the ranges of summation, to obtain
$$\alpha = \sum_{r=1}^k\sum_{j=0}^{r-2}\sum_{i=0}^{j-1}
           s_{r-j-1}s_js_i^2s_{j-i-1} -
	\sum_{r=-1}^{k-2}\sum_{j=0}^r\sum_{i=0}^{j-1}
           s_{r-j-1}s_js_i^2s_{j-i-1}.\eqno (*)$$
We study these last two sums separately. Initially we address the
first sum.
$$\sum_{r=1}^k\sum_{j=0}^{r-2}\sum_{i=0}^{j-1}
 s_{r-j-1}s_js_i^2s_{j-i-1} = \sum_{r=0}^k\sum_{j=0}^{r-1}\sum_{i=0}^{j-1}
 s_{r-j-1}s_js_i^2s_{j-i-1}$$
by inserting vanishing terms.
Now we must work a little harder.
$$\sum_{r=0}^k\sum_{j=0}^{r-1}\sum_{i=0}^{j-1}
s_{r-j-1}s_js_i^2s_{j-i-1} = \sum_{i<j<r} s_{r-j-1}s_js_i^2s_{j-i-1}
- \sum_{i<j}s_{k-j-1}s_js_i^2s_{j-i-1}.$$
The final term here is just
$$\sum_{i<j} s_js_{j+1}s_i^2s_{j-i-1}(-1)^j$$
which vanishes by (58).
Thus the first sum in our equation (*) for $\alpha$ can be replaced by
$$\sum_{i<j<r} s_{r-j-1}s_js_i^2s_{j-i-1},$$
which happens to be $\alpha.$
Thus (*) becomes
$$\alpha = \alpha - \sum_{r=-1}^{k-2}\sum_{j=0}^r\sum_{i=0}^{j-1}
           s_{r-j-1}s_js_i^2s_{j-i-1}. \eqno (**)$$
Now for the remaining unsimplified term in (**). We have
$$\sum_{r=0}^{k-2}\sum_{j=0}^r\sum_{i=0}^{j-1}
s_{r-j-1}s_js_i^2s_{j-i-1}
= \sum_{r=0}^{k-1}\sum_{j=0}^r\sum_{i=0}^{j-1}
s_{r-j-1}s_js_i^2s_{j-i-1} 
- \sum_{j=0}^{k-1}\sum_{i=0}^{j-1}
s_{k-j-2}s_js_i^2s_{j-i-1}.$$

Once again, the second term 

$$\sum_{j=0}^{k-1}\sum_{i=0}^{j-1}
s_{k-j-2}s_js_i^2s_{j-i-1}= \sum s_js_{j+2}s_i^2s_{j-i-1} (-1)^{j+1}$$
vanishes, this time because of 
 equation (59). Thus we have
$$\sum_{r=0}^{k-2}\sum_{j=0}^r\sum_{i=0}^{j-1} s_{r-j-1}s_js_i^2s_{j-i-1}
=\sum_{r=0}^{k-1}\sum_{j=0}^r\sum_{i=0}^{j-1}
s_{r-j-1}s_js_i^2s_{j-i-1}$$
$$ = \sum_{i<j<r}s_{r-j-1}s_js_i^2s_{j-i-1} 
+ \sum_{r=0}^{k-1} \sum_{i=0}^{r-1} s_{-1} s_rs_i^2s_{r-i-1}.$$
The final term here is simply another way of writing
$$\sum_{i<j} s_{-1}s_js_i^2s_{j-i-1}$$ which vanishes by equation (60).
Thus
$$\sum_{r=0}^{k-2}\sum_{j=0}^r\sum_{i=0}^{j-1} s_{r-j-1}s_js_i^2s_{j-i-1}
= \sum_{i<j<r}s_{r-j-1}s_js_i^2s_{j-i-1}= \alpha.$$


Putting all the pieces together by substituting into (**), we obtain
$$\alpha = \alpha - \alpha = 0.$$
$$\eqno \square$$

Lemma 3.26 
$$\sum_{i<j<r} s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i} = 0.\eqno (78)$$
Proof.\v
Let $$\alpha = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i}
= \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{j-i}(-1)^{r+i}
$$ $$- \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{j-i-2}(-1)^{r+i}.$$
Now adjust the ranges of summation for $i$ to obtain
$$\alpha = \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=-1}^{j-2}
s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}
- \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=1}^j
s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}.\eqno (*)$$

We consider the two sums in (*) separately, First we have
$$\sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=-1}^{j-2}
s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}
= \sum_{i<j<r}s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}
$$ $$ + \sum_{j<r} s_r^2s_{r-j-1}s_j^2(-1)^r
- \sum_{j<r} 0.$$
The argument of the the third sum vanishes since $s_0 = 0.$ The second
expression is simply another way of writing
$$\sum_{i<j} s_j^2s_i^2s_{j-i-1}( -1)^j$$ which vanishes by equation (50).
Thus (*) becomes
$$ \alpha = \sum_{i<j<r}s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}
- \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=1}^j
s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}. \eqno (**)$$
We now tackle the second expression in (**). We have
$$ \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=1}^j
s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}
= \sum_{i<j<r}s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}$$ $$
- \sum_{j<r} s_r^2s_{r-j-1}s_js_{j-1}(-1)^{r+1}
+ \sum_{j<r} s_r^2s_{r-j-1}s_js_{-1}(-1)^{r+j+1}.$$
The second sum here is really just
$$ \sum_{i<j} s_j^2s_is_{i-1}s_{j-i-1}(-1)^{j+1}$$ which vanishes by 
equation (62).
The third sum is really
$$ \sum_{i<j} s_j^2s_{j-i-1}s_i(-1)^{i+j+1}$$ which vanishes by 
equation (61). Thus (**) becomes
$$\alpha =  \sum_{i<j<r}s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}
-  \sum_{i<j<r}s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i+1}$$
$$ = - \alpha + \alpha = 0,$$ 
and we are done.

$$\eqno \square$$


Lemma 3.27

$$\theta = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1} = 0.
\eqno (79)$$
Proof.\v
Let $$\alpha = \sum_{i<j<r} s_{r+1}^2s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1},$$
$$\beta = \sum_{i<j<r} s_{r-1}^2s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1},$$
and
$$\lambda = \sum_{i<j<r} s_{r-j-1}s_js_i^2s_{j-i-1}.$$

Recall from equation (46) that
$$3s_n^2 = s_{n+1}^2 + s_{n-1}^2 - 2(-1)^n\ \ \forall n \in \Z$$
We deploy this, focusing on the variable $r$, to obtain
$$3\theta = \alpha + \beta + 2\lambda.$$
The equation (73) shows that $\lambda = 0$ so
$$3\theta = \alpha + \beta.$$
We now attempt to find a different linear relation between $\alpha$ and 
$\beta.$ We have

$$\alpha = \sum_{r=1}^k \sum_{j=0}^{r-2}\sum_{i=0}^{j-1}
s_r^2s_{r-j-2}s_js_i^2s_{j-i-1}(-1)^r.$$

Sliding the range of $r$ down by 1
is harmless since $s_0 = 0.$ We have
$$\alpha = 
\sum_{i<j<r}s_r^2s_{r-j-2}s_js_i^2s_{j-i-1}(-1)^r
-\sum_{r=0}^{k-1}\sum_{i=0}^{r-2}s_r^2s_{-1}s_{r-1}s_i^2s_{r-i-2}(-1)^r.$$
The second sum is the edge effect, and we need to show it vanishes. We change 
the dummy variable $r$ to $j$ to render the appearance of the sum more 
familiar. We have
$$\sum_{j=0}^{k-1}\sum_{i=0}^{j-2} s_j^2s_{j-1}s_i^2s_{j-i-2}(-1)^j
= \sum_{i<j} s_j^2s_{j-1}s_i^2s_{j-i-2}(-1)^j 
- \sum s_j^2s_{j-1}^3s_{-1}(-1)^j.$$
The first sum vanishes by (69) and the second because of equation (41).
Thus $$\alpha =\sum_{i<j<r} s_r^2s_{r-j-2}s_js_i^2s_{r-i-1}(-1)^r.\eqno (*)$$


We now address $\beta$ in the same spirit. We have 
$$\beta = \sum_{i<j<r} s_{r-1}^2 s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1}$$

$$ = \sum_{r=-1}^{k-2}\sum_{j=0}^r\sum_{i=0}^{j-1}
s_r^2s_{r-j}s_js_i^2s_{j-i-1}(-1)^r.$$

When $j = r$ we get no contribution, so

$$\beta = \sum_{i<j<r} s_r^2s_{r-j}s_js_i^2s_{j-i-1}(-1)^r
- \sum_{i<j} s_{k-1}^2s_{k-1-j}s_js_i^2s_{j-i-1}(-1)^{k-1}.$$
The last term, up to sign,  is just
$$ \sum_{i<j} s_js_{j+1}s_i^2s_{j-i-1}(-1)^{j+1}$$ which vanishes
by equation (59).
Thus
$$\beta = \sum_{i<j<r} s_r^2s_{r-j}s_js_i^2s_{j-i-1}(-1)^r$$ 

Thus $$\alpha - \beta = \sum_{i<j<r} 
s_r^2(s_{r-j-2}-s_{r-j})s_js_i^2s_{j-i-1}(-1)^r
= \theta.$$
Putting this information together, we have
$$3\theta = \alpha + \beta \hbox{ and } \theta = \alpha - \beta.$$ 

We are nearly half way home. Put
$$\epsilon = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{i+1}^2 s_{j-i-1}(-1)^{r+1}$$
and
$$\gamma = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{i-1}^2s_{j-i-1}(-1)^{r+1}.$$

$$\zeta = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{j-i-1}(-1)^{r+i}.$$
Equation (46) forces
$$\theta = \epsilon + \gamma + 2\zeta.$$ However, $\zeta$ vanishes by 
equation (78)
so $\theta = \epsilon + \gamma.$ We address $\epsilon.$

$$\epsilon = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{i+1}^2s_{j-i-1}(-1)^{r+1}
= \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=1}^j
s_r^2s_{r-j-1}s_js_i^2s_{j-i}(-1)^{r+1}$$
so
$$\epsilon = \sum_{i<j<r} s_r^2s_{r-j-1}s_is_j^2s_{j-i}(-1)^{r+1}.$$
We now turn our attention to $\gamma.$ We have
$$\gamma = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_{i-1}^2s_{j-i-1}(-1)^{r+1}
= \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=-1}^{j-2}
s_r^2s_{r-j-1}s_js_i^2s_{j-i-2}(-1)^{r+1}.$$ 
This gives us
$$\gamma = \sum_{i<j<r}s_r^2s_{r-j-1}s_js_i^2s_{j-i-2}(-1)^{r+1}
+ \sum_{j<r} s_r^2s_{r-j-1}s_js_{j-1}(-1)^{r+1}$$
$$- \sum_{j<r} s_r^2s_{r-j-1}s_js_{j-1}^2(-1)^{r+1},$$
and changing variable names we see that
$$\gamma = \sum_{i<j<r}s_r^2s_{r-j-1}s_js_i^2s_{j-i-2}(-1)^{r+1}
+ \sum_{i<j} s_j^2 s_is_{i-1}s_{j-i-1}(-1)^{j+1}$$ $$
- \sum_{i<j} s_j^2s_{j-i-1}s_is_{i-1}^2(-1)^{j+1}.$$
The final two sums vanish by equations (62) and (65). 
$$\gamma = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_i^2s_{j-i-2}(-1)^{r+1}.\eqno (**)$$

Notice that the expressions for $\epsilon$ and $\gamma$
yield
$\theta = \epsilon - \gamma.$ 

Summarizing we have
$$\alpha + \beta = 3\theta = \epsilon + \gamma $$
and
$$\alpha - \beta = \theta = \epsilon - \gamma.$$
Thus $\alpha = \epsilon = 2\theta $ and $\beta = \gamma = \theta.$

Now consider
$$\theta = \sum_{i<j<r} s_r^2s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1}.$$
We put
$$\mu  = \sum_{i<j<r} s_r^2s_{r-j-1}s_{j+1}s_i^2s_{j-i-1}(-1)^{r+1}$$
and $$\nu =
 \sum_{i<j<r} s_r^2s_{r-j-1}s_{j-1}s_i^2s_{j-i-1}(-1)^{r+1}$$
so
$$\theta = \mu - \nu.$$ Adjusting ranges of summation we see that 
$$\mu = \sum_{r=0}^{k-1}\sum_{j=1}^r\sum_{i=0}^{j-2} 
s_r^2s_{r-j}s_js_i^2s_{j-i-2}(-1)^{r+1}$$
and 
$$\nu = \sum_{r=0}^{k-1}\sum_{j=-1}^{r-2}\sum_{i=0}^j 
s_r^2s_{r-j-2}s_js_i^2s_{j-i}(-1)^{r+1}.$$

Now $$\mu = \sum_{r=0}^{k-1}\sum_{j=0}^{r-1}\sum_{i=0}^{j-2}
s_r^2s_{r-j}s_js_i^2s_{j-i-2}(-1)^{r+1}$$
since we have added and removed vanishing terms. We now extend
the range of $i$ so
$$\mu = \sum_{i<j<r} s_r^2s_{r-j}s_js_i^2s_{j-i-2}(-1)^{r+1}
+ \sum_{j<r} s_r^2s_{r-j}s_js_{j-1}^2s_{-1}(-1)^{r+1}.$$ 
 Changing variable names we see that
$$\mu = \sum_{i<j<r} s_r^2s_{r-j}s_js_i^2s_{j-i-2}(-1)^{r+1}
+ \sum_{i<j} s_j^2s_{j-i}s_is_{i-1}^2(-1)^{j+1}.$$
The final sum vanishes by (66) and so
$$\mu = \sum_{i<j<r} s_r^2s_{r-j}s_js_i^2s_{j-i-2}(-1)^{r+1}.$$

We now attack $\nu.$
We have
$$\nu= \sum_{r=0}^{k-1}\sum_{j=-1}^{r-2}\sum_{i=0}^j
s_r^2s_{r-j-2}s_js_i^2s_{j-i}(-1)^{r+1} 
=\sum_{r=0}^{k-1}\sum_{j=0}^{r-2}\sum_{i=0}^j
s_r^2s_{r-j-2}s_js_i^2s_{j-i}(-1)^{r+1}$$
since there are no legal values of $i$ less than $-1.$
We increment the top range of $j$ introducing the term
$$\sum_{r=0}^{k-1}\sum_{i=0}^{r-1}
s_r^2s_{-1}s_{r-1}s_i^2s_{r-i-1}(-1)^{r+1} = \sum_{i<j}s_j^2s_{j-1}
s_i^2s_{j-i-1}(-1)^{j+1}.$$
which vanishes by (69). We now contract the upper range of $i$ by 1,
which is inconsequential since $s_0 = 0.$
Thus

$$\nu = \sum_{i<j<r} s_r^2s_{r-j-2}s_js_i^2s_{j-i}(-1)^{r+1}.$$ 

The expressions for $\mu$ and  $\nu$ differ in two places.

Notice that
$$s_{r-j}s_{j-i-2} - s_{r-j-2}s_{j-i}
= (s_{r-j-1}+s_{r-j-2})s_{j-i-2} - s_{r-j-2}(s_{j-i-1} + s_{j-i-2})$$
$$ =  s_{r-j-1}s_{j-i-2} - s_{r-j-2}s_{j-i-1}$$
so $$\theta = \mu - \nu = \sum_{i<j<r}
s_r^2s_{r-j-1}s_js_i^2s_{j-i-2}(-1)^{r+1}
-\sum_{i<j<r} s_r^2s_{r-j-2}s_js_i^2s_{j-i-1}(-1)^{r+1}.$$
Now, examination of the equations in the proof marked (*) and (**) 
yields that
$$\theta = \gamma + \alpha.$$ 
However, we know that $\gamma = \theta$ and $\alpha = 2\theta,$
so $\theta = 3\theta.$
Thus $\theta = 0$ and we are done.
$$\eqno \square$$

Corollary.\v
In the notation of the lemma, it follows that $\alpha = 0$ and so
$$\sum_{i<j<r} s_{r+1}^2s_js_i^2s_{r-j-1}s_{j-i-1}(-1)^{r+1}= 0.
\eqno (80)$$
$$\eqno \square$$


Lemma 3.28
$$\tau = \sum_{i<j<r} s_rs_{r+1}s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1} = 0.
\eqno (81)$$

Proof.\v

Put $\kappa = \kappa(i,j)=  s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1} $ so
$$\tau = \sum_{i<j<r}s_rs_{r+1}\kappa.$$
Now exploit the previous corollary (equation (80))
in conjunction with $s_r = s_{r+1} - s_{r-1}$
to obtain
$$ \tau = \sum_{i<j<r} s_{r+1}^2\kappa - \sum_{i<j<r}s_{r+1}s_{r-1}\kappa.$$
The first term vanishes by (79), and $s_{r+1}s_{r-1} = s_r^2 + (-1)^r$
for each $r$ by (22).
Thus
$$\tau =-\sum_{i<j<r} s_r^2s_{r-j-1}s_js_i^2s_{j-i-1}(-1)^{r+1}  
+ \sum_{i<j<r} s_{r-j-1}s_js_i^2s_{j-i-1} .$$
The first term vanishes by equation (79) and the second term vanishes
by equation (77). Thus $\tau = 0$ and we are done.
$$\eqno \square$$

\vfill \eject

\centerline{\bf  Section 4 }\v
\centerline{ A Proof of Theorem B }\v

Consider a group $H= H^{\Z} $ with the following presentation:

 $$H^{\Z} = < x,y,z,t,u\ :\ [y,x] = z,\ [z,x] = t,\ [t,x] = u\ >$$
where those pairs of generators with unspecified commutators
are implicitly deemed to commute. This is a torsion-free
nilpotent group of nilpotency class 4. In fact this
group is generated by just $x$ and $y.$ Each element of the group
will have a unique representation as $x^ay^bz^ct^du^e$ where
$a,b,c,d,e \in \Z.$ In fact, we may as well think of this
group as being a rather strange group structure on $\Z^5.$ 
The group multiplication law will be given by rational
polynomials in 10 variables, and inversion by rational
polynomials in 5 variables. These polynomials must, of course, have the
property that, regarded as maps, they assume integral
values when supplied with integral arguments. We shall use the somewhat
sloppy term {\it integer valued rational polynomials} to
describe such polynomials.  

Let $p$ be a prime, and  work in 
$(\Z/p\Z)^5$ instead. There are no difficulties associated with this reduction
modulo $p,$ because the polynomials involved do not have primes other
than 2 or 3 involved in denominators of co-efficients.
We regard the variables a,b,c,d,e as being in $\Z/p\Z$ and obtain
a group structure on $(\Z/p\Z)^5.$ We call this group $H^{\Z/p\Z}$ and for
$p$ larger than 3
this will be a group of exponent $p.$ We shall demonstrate this shortly.
The natural ring epimorphism 
$ \Z \longrightarrow \Z/p\Z$ induces a natural
epimorphism of groups $\psi: H^{\Z}\longrightarrow H^{\Z/p\Z}.$ We abuse the
letters $x,y,z,t,u$ to denote the images of the corresponding elements
of $H^{\Z}$ under $\psi$. 

The relatively
free two generator nilpotent groups of 
class 4 with exponent laws 2 and 3 are, respectively,
$C_2 \times C_2$ and the (class 2) extra-special group of order 27. These
are, in a sense, degenerate, since for all other primes $p,$ the relatively
free two-generator exponent p class 4 groups are all of genuine class 4, 
and have order $p^8.$ It is these primes $p >3$ on which we shall focus.

We examine the details of the multiplication law
of the groups $H^{\Z/p\Z}.$ The element $u$ is central,
and the group $V = <y,z,t,u>$ is Abelian. A concrete representation of this
group is to think of $V$ as a four dimensional $GF(p)-$vector space. This
space admits an automorphism $\alpha$ (really $x$) given by the matrix
  $$\pmatrix{ 1 & 1 & 0 & 0 \cr 0 & 1 & 1 & 0 \cr 0 & 0 & 1 & 1 \cr
            0 & 0 & 0 & 1 }.$$
The group $H^{\Z/p\Z}$ is then realized as the semi-direct product of $V$ with
$<\alpha>.$ 

Notice that the matrix of $\alpha^n$ is

  $$\pmatrix{ 1 & (_1^n)  & (_2^n) & (_3^n)  \cr 
0 & 1 &  (_1^n) &  (_2^n) \cr 
0 & 0 & 1 &  (_1^n) \cr
0 & 0 & 0 & 1 },$$
so for primes $p$ other than $2$ and $3$ we have $\alpha^p = 1.$ We wish to
show that for primes $p>3,$ the group $H^{\Z/p\Z}$ has exponent $p.$ 

Suppose $v \in V$ and that $n \in \N,$ then 
$$(\alpha^n \cdot v)^p = \alpha^{pn} \cdot v(1 + \alpha^n + \ldots + 
\alpha^{n(p-1)})$$
by the definition of semi-direct products. Assuming that $p$ is a prime
other than 2 or 3, we have that $\alpha^p =1,$ so $\alpha^{np} = 1.$
It remains to show that
$$ \beta = 1 + \alpha^n + \ldots +
\alpha^{n(p-1)} = 0.$$ Let $m_n \in GF(p)[X]$ denote the minimum
polynomial of $\alpha^n,$ so $m_n$ is irreducible and divides
$$1-X^p = (1-X)(1 + X + X^2 + \ldots + X^{p-1}).$$
The ring $GF(p)[X]$ is a unique factorization domain. If $m_n$ divides
$(1-X)$ then $\alpha^n=1$ so $\beta = 0.$ Conversely, if $m_n$ fails to
divide $(1-X)$ then it must divide $1 + X + X^2 + \ldots + X^{p-1}$
so $\beta = 0.$

Thus for primes $p$
greater than $3$ the group $H^{\Z/p\Z}$ has exponent $p.$ 

We now investigate the group law of $H^{\Z/p\Z}$
in some detail, reverting to
the description of $H^{\Z/p\Z}$ as being $(\Z/p\Z)^5$ with a peculiar group law.
In the obvious notation
$$(a,b,c,d,e) \cdot (a',b',c',d',e') = (a'',b'',c'',d'',e'')$$  
represents the group law.
A straightforward induction argument yields the following:
$$ a'' = a + a'$$
$$ b'' = b + b'$$
$$ c'' = c + c' + a'b$$
$$ d'' = d + d' + a'c + (_2^{a'})b$$
$$ e'' = e + e' + a'd +(_2^{a'})c + (_3^{a'})b$$

We now use these formulas to calculate the Fibonacci loop
${\bf l}(x,y,\ldots).$

The first few terms are as follows (reduce modulo $p$ of your choice):\v \v


    $( 1, 0, 0, 0, 0 )$\v
    $( 0, 1, 0, 0, 0 )$\v
    $( 1, 1, 0, 0, 0 )$\v
    $( 1, 2, 1, 0, 0 )$\v
    $( 2, 3, 2, 0, 0 )$\v
    $( 3, 5, 7, 4, 1 )$\v
    $( 5, 8, 18, 19, 10 )$\v
    $( 8, 13, 50, 108, 151 )$\v
    $( 13, 21, 132, 495, 1265 )$\v
    $( 21, 34, 351, 2267, 10438 )$\v
    $( 34, 55, 924, 9944, 77748 )$\v

In particular, choosing the prime 7, we obtain the loop\v


    $( 1, 0, 0, 0, 0 )$\v
    $( 0, 1, 0, 0, 0 )$\v
    $( 1, 1, 0, 0, 0 )$\v
    $( 1, 2, 1, 0, 0 )$\v
    $( 2, 3, 2, 0, 0 )$\v
    $( 3, 5, 0, 4, 1 )$\v
    $( 5, 1, 4, 5, 3 )$\v
    $( 1, 6, 1, 3, 4 )$\v
    $( 6, 0, 6, 5, 5 )$\v
    $( 0, 6, 1, 6, 1 )$\v
    $( 6, 6, 0, 4, 6 )$\v
    $( 6, 5, 2, 1, 3 )$\v
    $( 5, 4, 3, 4, 6 )$\v
    $( 4, 2, 2, 2, 0 )$\v
    $( 2, 6, 0, 0, 0 )$\v
    $( 6, 1, 6, 1, 6 )$\v
    $( 1, 0, 0, 0, 0 )$\v
    $( 0, 1, 0, 0, 0 )$\v

of length 16.\v

Let the $i^{th}$ entry of ${\bf l}$ be $(s_{i-1},s_i,z_i,t_i,u_i).$\v

From now on we will make the benign assumption that the prime $p$ is
not 2,3,5 or 11, so all the results of Section 3 may be freely used.\v
Lemma 4.1

$$z_k = z_{k+1} = 0.$$\v
Proof.\v

Using the formula for multiplication, a simple induction shows that
for positive $n,$ we have
$$ z_n = \sum_{i= 0}^{n-1} s_{n-i-1}s_i^2. $$

Thus

$$ z_{k} = \sum_{i=0}^k s_{k-i-1}s_i^2 = \sum s_{k-i-1}s_i^2.$$
By lemma 2.2  (equation (14) we have
$$z_k = \sum s_{i+1}s_i^2(-1)^i$$
lemma 3.3 (equation (20)) we have  $z_k = 0.$ \v
Similarly
$$z_{k+1} = \sum_{i=0}^k s_{k-i}s_i^2 = \sum s_{k-i}s_i^2 
= \sum s_i^3(-1)^{i+1}.$$
This last expression vanishes by lemma 3.2 (equation (16))
so $z_{k+1} = 0$ and we are done. 
$$\eqno \square$$

Lemma 4.2\v

$$ t_k = t_{k+1} = 0 .$$

Proof.\v

We use a similar method as in the proof of lemma 4.1, but the argument
is a little more complicated. Once again, we use induction to
obtain a formula for $t_n$ for positive $n.$ It is
$$ t_n = \sum_{j= 0}^{n-1} s_{n-1-j}s_jz_j 
 + \sum_{i=0}^{n-1} (_2^{s_i})s_is_{n-i-1}.$$

In particular,
$$ t_{k+1} = \sum_{j= 0}^k s_{k-j}s_j \sum_{i=0}^{j-1} s_i^2 s_{j-i-1}
+ \sum_{i=0}^k (_2^{s_i})s_is_{k-i}$$
which, after cosmetic treatment, becomes
$$ t_{k+1} = \sum_{j=0}^{k-1}\sum_{i=0}^{j-1} s_j^2s_i^2s_{j-i-i}(-1)^{j+1}
+ \sum (_2^{s_i})s_i^2(-1)^{i+1}.$$

This expression vanishes by appeal to three section 3 equations,
those numbered (50), (23) and (16) will do the trick.\v 

We address the second problem.
$$t_k = \sum_{j=0}^{k-1}s_{k-1-j}s_j\sum_{i=0}^{j-1} s_i^2s_{j-i-1}
+ \sum (_2^{s_i})s_is_{i+1}(-1)^i.$$
The second sum vanishes by equations (20) and (28), and so
$$t_k = \sum_{i<j} s_js_{j+1} s_i^2 s_{j-i-1}(-1)^j.$$
This vanishes by equation (55) and so $t_k = 0$ and we are done.
$$\eqno \square$$

Lemma 4.3\v
$$ u_k = u_{k+1} = 0.$$
Proof.\v
The argument is in the same style as the previous two proofs. For
positive $n,$ an inductive argument shows that for positive $n$ we have

$$u_n = \sum_{r = 0}^{n-1} s_{n-r-1}s_rt_r
       + \sum_{j=0}^{n-1} s_{n-j-1}(_2^{s_j})z_j 
       + \sum_{i = 0}^{n-1} s_{n-i-1} (_3^{s_i}) s_i,$$

which expands to

$$u_n = \sum_{r=0}^{n-1}\sum_{j=0}^{r-1}\sum_{i=0}^{j-1}
        s_{n-r-1}s_rs_{r-j-1}s_js_{j-i-1}s_i^2
+ \sum_{j=0}^{n-1}\sum_{i=0}^{j-1}
	s_{n-j-1}s_j(_2^{s_i})s_is_{j-i-1}$$
$$+\sum_{j=0}^{n-1}\sum_{i=0}^{j-1}s_{n-j-1}(_2^{s_j})
        s_{j-1-i}s_i^2
       +\sum_{i=0}^{n-1} s_{n-i-1}(_3^{s_i})s_i.$$
$$u_{k+1} = \sum_{r=0}^k\sum_{j=0}^{r-1}\sum_{i=0}^{j-1}
            s_r^2s_js_i^2s_{r-j-1}s_{j-i-1}(-1)^{r+1}
+\sum_{j=0}^{k}\sum_{i=0}^{j-1}
        s_{k-j}s_j(_2^{s_i})s_is_{j-i-1} $$
$$+ \sum_{j=0}^k\sum_{i=0}^{j-1}s_j(_2^{s_j})s_{j-i-1}s_i^2(-1)^{j+1}
+ \sum_{i=0}^k s_i^2(_3^{s_i})(-1)^{i+1}.$$
The last of the three sums is quite straightforward; it vanishes because
of equations $(16)$, $(23)$ and $(31).$ Thus we have
$$u_{k+1} = \sum_{r=0}^k\sum_{j=0}^{r-1}\sum_{i=0}^{j-1}
            s_r^2s_js_i^2s_{r-j-1}s_{j-i-1}(-1)^{r+1}
+\sum_{j=0}^{k}\sum_{i=0}^{j-1}
        s_j^2(_2^{s_i})s_is_{j-i-1}(-1)^{j+1}$$
$$+ \sum_{j=0}^k\sum_{i=0}^{j-1}s_j(_2^{s_j})s_{j-i-1}s_i^2(-1)^{j+1}.$$
The first sum vanishes by equation (78), the second by equations (5) and (72), 
and the last by equations (50) and (70). 
$$u_k = \sum_{i<j<r}
s_{k-1-r}s_rs_{r-j-1}s_js_{j-i-1}s_i^2
+ \sum_{j=0}^{k-1}\sum_{i=0}^{j-1}
        s_{k-j-1}s_j(_2^{s_i})s_is_{j-i-1}$$ 
$$+ \sum_{i<j} s_{k-j-1}(_2^{s_j})s_{j-i-1}s_i^2
+ \sum s_{k-i-1}(_3^{s_i})s_i.$$
These three sums vanish for the following reasons. The first sum is really
$$\sum s_{r+1}s_rs_{r-j-1}s_js_{j-i-1}s_i^2(-1)^r.$$
This vanishes by (81). The second sum is actually
$$ \sum_{j=0}^{k-1}\sum_{i=0}^{j-1}
        s_{j+1}s_j(_2^{s_i})s_is_{j-i-1}(-1)^j$$
which vanishes by equations (58) and (72).

The next sum is
$$\sum s_{j+1}(_2^{s_j})s_{j-i-1}s_i^2(-1)^j.$$
This vanishes by equations (72) and (58).
Finally we consider the fourth sum which is 
$$\sum s_{i+1}(_3^{s_i})s_i(-1)^i.$$ This vanishes by equations (44),
 (28) and (20).  $$\eqno \square$$ 

Lemma 4.4\v 
Let $$H = < x,y,z,t,u\ :\ [y,x] = z,\ [z,x] = t,\ [t,x] = u\ >$$
where those pairs of generators with unspecified commutators
are implicitly deemed to commute, and the $p-$th power of
every group element is 1. The Fibonacci loop $(x,y,\ldots)$ 
in $H$ has length $k = k(p).$\v
Proof.\v
This is simply the upshot of lemmas 4.1,4.2 and 4.3. 
$$\eqno \square$$

We use implicit left bracket notation for commutators,
so $$(a,b,c) = ((a,b),c).$$ Recall the identity of Witt,
$$ (a,b^{-1},c)^b(b,c^{-1},a)^c(c,a^{-1},b)^a = 1\eqno (Witt)$$
and Philip Hall's formulas
$$(ab,c) = (a,c)^b(b,c) \hbox{ and } (a,bc) = (a,c)(a,b)^c \eqno (Hall).$$
These equations hold for all $a,b,c$ elements of an arbitrary
group $G.$ See [Ha].\v

Lemma 4.5\v
Suppose that $x,y \in G,$ where $G$ has nilpotency class 4.
Let $\alpha = (x,y),$ then $(\alpha,x,y) = (\alpha,y,x).$\v

Proof\v
The Witt identity forces
$$(\alpha,x,y)^{x^{-1}}(x^{-1},y^{-1},\alpha)^y(y,
\alpha^{-1},x^{-1})^{\alpha} = 1.$$
The commutators have weight 4 and so each one is central. Our equation
can thus be written
$$(\alpha,x,y)(x^{-1},y^{-1},\alpha)(y,\alpha^{-1},x^{-1}) = 1.$$


Now $$(x^{-1},y^{-1})= (x,y)^{x^{-1}y^{-1}} = (x,y)z$$
where $z \in \gamma_3(G).$
Now using $Hall$ we see that
$$(x^{-1},y^{-1},\alpha) = ((x,y)z,\alpha) = ((x,y),\alpha)^z(z,\alpha).$$
Thus we obtain
$$(x^{-1},y^{-1},\alpha) = (\alpha,\alpha)^z(z,\alpha).$$
Now clearly $(\alpha,\alpha) = 1,$ and since $z \in \gamma_3(G)$
and
$\alpha \in \gamma_2(G)$ then $(z,\alpha) \in \gamma_5(G).$ However,
$G$ has class 4 so $\gamma_5(G)$ is trivial. Thus our
main equation becomes
$$(\alpha,x,y)(y,\alpha^{-1},x^{-1}) = 1.$$

Now we work on the final commutator in this expression. We have
$$(y,\alpha^{-1},x^{-1})= ((y,(y,x)),x^{-1})
= (((x,y),y)^{y^{-1}},x^{-1}).$$
Now $$((x,y),y)^{y^{-1}} = ((x,y),y)t$$ for some
$t \in \gamma_4(G),$ and so
$$(((x,y),y)^{y^{-1}},x^{-1})= (((x,y),y)t,x^{-1})
= (((x,y),y),x^{-1})^t(t,x^{-1}).$$
Now $t$ is central so we may deduce that
$$(y,\alpha^{-1},x^{-1})= (\alpha,y,x^{-1}).$$

Now Hall's formulas
force $$(\alpha,y,x)(\alpha,y, x^{-1})^x= 1.$$
As usual we may omit the final conjugation by $x$ since $(\alpha,y, x^{-1})$
is central. Thus $$(\alpha,y, x^{-1}) = (\alpha,y,x)^{-1}.$$
We deduce that
$$(\alpha,x,y) = (\alpha, y, x).$$
$$\eqno \square$$

Theorem B.\v

Proof.\v

The theorem holds for the primes 2,3,5 and 11 by direct computer aided
calculation. In principle a diligent human could perform the task.
We may therefore assume that our prime is not 2,3,5 or 11, 
so all the results of Section 3 and 4 may be freely used.
Let $T$ be the two generator relatively free class 4 group,
and suppose that $T$ is relatively free on $x$ and $y.$ 
We assume the reader has a passing familiarity with the theory
of torsion-free finitely generated nilpotent groups, and refer him
or her to $[Ba]$, $[Ha]$ or $[Se]$ in the event that our presumption is 
unjustified.

The group $T$
has Hirsch length 8, and a Mal'cev basis may be easily described.
It is
$$ x, y, [y,x], [[y,x],x], [[y,x],y], [[[y,x],x],x], 
[[[y,x],y],x] = [[[y,x],x],y], [[[y,x],y],y].$$
The equality in this list is justified by Lemma 4.5,
and we may regard $T = T^{\Z}$ as being the group structure
on $\Z^8$ induced by this Mal'cev basis. See [Ha].

Thanks to [MKS] page 349 exercise 9, and to Eamonn O'Brien for pointing
out this reference, we know that $\bar T = T/T^p$ has order $p^8.$ It follows
that the Mal'cev basis we have described induces a central series
in $\bar T$ where adjacent terms of the series have quotients which
are cyclic of order $p.$  We abusively denote the images of $x$ and $y$
in $\bar T$ by the same letters.
The group $\bar T$ is relatively free, so we have a {\it Fibonacci
automorphism } $\phi : \bar T \longrightarrow \bar T$ defined
by $x\phi = y$ and $y\phi = xy.$ Let $M = <(y,x,y)>^{\bar T},$ a normal
subgroup of order $p^3.$ A routine calculation shows that
$M\phi  \cap M \cap M\phi^{-1} = 1.$ 

The details we now explain -- using vector notation to express group
elements in $\bar T$ with respect to the image of the Mal'cev basis
of $T;$ we also freely use easy consequences of $(Hall)$ to be found on page
9 of $[Ha].$ We have
$$ M\phi = <(xy,y,xy)>^{\bar T}  = <(y,x,x)(y,x,y)(y,x,y,x)>^{\bar T} $$

so

$$ M\phi = \{(0,0,0,a,a,b,a+b+c,c)\ | \ a,b,c \in \Z/p/Z\}.$$
Also we find that
$$ M = <(y,x,y)>^{\bar T} = \{(0,0,0,0,a,0,b,c)\ | \ a,b,c \in \Z/p\Z\}.$$
Finally
$$ M\phi^{-1} = <(x,yx^{-1},x)>^{\bar T} = <(y,x,x)>^{\bar T}$$
so
$$ M\phi^{-1} = \{(0,0,0,a,0,b,c,0)\ | \ a,b,c \in \Z/p\Z\}.$$
Notice that 
$$ M \cap M\phi^{-1} = <(y,x,x,y)> = <(y,x,y,x)>, $$
a cyclic group of order $p.$ In vector notation this is

$$ M \cap M\phi^{-1} = \{ (0,0,0,0,0,0,a,0)\ |  \ a \in \Z/p\Z\}.$$
Finally we deduce that
$$M\phi \cap M \cap M\phi^{-1} = 1$$ as required. Note that the appeal
to [MKS] is only present to give us a way of showing that the intersection
$M\phi  \cap M \cap M\phi^{-1}$ is trivial.

We have natural maps $\bar T
\longrightarrow {\bar T}/M\phi^i$ for each $i,$ and these induce
an embedding
$$\theta : \bar T \longrightarrow {\bar T}/M\phi \times {\bar T}/M
\times {\bar T}/M\phi^{-1}.$$
Now $Im(\bar T)$  is a subcartesian product in 
${\bar T}/M\phi \times {\bar T}/M
\times {\bar T}/M\phi^{-1}.$
Each group $\bar T/M\phi^i$ is a copy
of the group $H$ studied in this section.

When we compute the Fibonacci sequence in 
$\bar T$ the images in ${\bar T}/M\phi \times {\bar T}/M
\times {\bar T}/M\phi^{-1}$
of the first four terms are as follows.

$$ (x(M\phi) , xM, x(M\phi^{-1})) \eqno (a)$$
$$ (y(M\phi)
 , yM, y(M\phi^{-1})) \eqno (b)$$
$$ (xy(M\phi), xyM, xy(M\phi^{-1})) \eqno (c)$$
$$ (yxy(M\phi),yxyM,yxy(M\phi^{-1})) \eqno (d)$$

In the second co-ordinate, we are simply calculating the Fibonacci
loop which as been the central object of study of this section. This
is not quite true of the first and third co-ordinates. The groups
are the same (up to isomorphism), but the starting values are different.
However, in these co-ordinates we are actually dealing with rotations
of the series in the second co-ordinate. This is because
$(xM)\phi = y(M\phi)$ and $(yM)\phi = xy(M\phi)$ 
yielding a rotation by 1 place in the loop of the first co-ordinate. 
Similarly $\phi^{-1}$ 
induces a rotation through 1 place
in the opposite direction in the third co-ordinate. 
Thus the loop beginning $(x,y,\ldots)$
in $\bar T$ has length $k = k(p)$ as required.
$$\eqno \square$$

Observations\v

The final ruse in the proof of Theorem B was used because we did not
know that {\it  all } loops in $H$ had length dividing $k,$ we only
knew it for the specific loop with which worked throughout Section
3 and  Section 4. Now, however, we are suddenly liberated. From Theorem
B it follows that any loop in any class 4 $p-$group 
of exponent $p$ has length dividing
$k,$ since any such group is a quotient of the relatively free group
$\bar T.$
\vfill \eject
\centerline{\bf Section 5 }\v
\centerline{ \bf On a Conjecture of D D Wall}\v

Let $n$ be a positive integer and suppose $(s_i)$ denotes the standard
Fibonacci bi-infinite sequence modulo $n.$ Thus $s_0 = 0$ and $s_1 = 1.$
The minimum period of this sequence we call Wall's number $k(n),$ or
just $k$ if the modulus is clear. Wall conjectured that for any
prime $p$ that $k(p) \not = k(p^2).$ He verified this conjecture
for all primes less than $10^4.$ We have been unable to prove Wall's
conjecture, but can announce that we have searched all primes less than
$10^8$ and Wall's conjecture holds in all cases. In this document,
$p$ will always denote an odd prime. Recall Lemma 2.3;

Lemma (Wall)\v
For all primes $p,$ $$\hbox{ if } p \cong 1 \hbox{ or } 4 \hbox{ mod } 5
\hbox{ then } k(p) \hbox{ divides } p-1,$$
and
$$\hbox{ if } p \cong 2 \hbox{ or } 3 \hbox{ mod } 5
\hbox{ then } k(p) \hbox{ divides } 2p+2.$$
$$\eqno \square$$ 

For a substantial prime (of order say $10^8$) a naive attempt to calculate
$k(p),$ let alone $k(p^2)$ is extremely computationally expensive.
By naive we mean that one simply calculates the Fibonacci sequence until it 
repeats. A better way to calculate $k(p)$ is  
to test divisors of $p-1$ or $2p+2$ (as appropriate). One can calculate
a specified term of the Fibonacci sequence (mod $p$ or $p^2$)
relatively cheaply using the Fibonacci matrix equation
$$ \pmatrix{ s_{i+1} & s_i \cr s_i & s_{i-1}} = \pmatrix{ 1 & 1 \cr
1 & 0}^i$$ in $GL(2,R)$
where $R$ is $\Z/p\Z$ or $\Z/p^2\Z$ as appropriate. The method of repeated
squaring is, of course, {\it de rigeur}. Even so, the explicit 
calculation of $k(p)$ has drawbacks,
since multiple calculations are needed to determine the true value of
$k(p)$.

The algorithm we used relies on another theorem of Wall, in our terms this
is a corollary of Theorem A.\v

Theorem (Wall)\v

If $k(p) \not = k(p^2)$ then $k(p^2) = pk(p).$

$$\eqno \square$$

We introduce the notation $w(p) = p-1$ or $w(p)$ = $2p+2$
as $p \cong 1,4$ or $p \cong 2,3$ mod 5. \v
Proposition\v
Let $p$ be an odd prime which is not 5,
and suppose that $(s_i)$ denotes the Fibonacci sequence modulo $p^2$. We have
$s_{w(p)} = 0$ and  $s_{w(p) + 1}  = 1$ if and only if
$k(p)  = k(p^2).$\v
Proof.\v
If $k(p^2)= k(p)$ then $k(p^2)$ divides $w(p).$ Conversly if $k(p^2)
= pk(p)$ then $pk(p)$ cannot divide either $p-1$ or $2p+2$ unless $p$
is $2$.
$$\eqno \square$$

This proposition can be readily turned into algorithm for testing
Wall's conjecture. We ran this program for several weeks in the
background on a variety of SUN 3, SUN 4 and Orion machines. Each
machine examined a congruence class or congruence classes of primes
modulo 30, depending on the machines relative speed. For almost
all of the calculation, the arbitrary precision arithmetic feature
of CAYLEY was used to perform the computation, though as an experiment
J P ffitch coded the algorithm in LISP and eliminated a small part of the 
range (circa 5 million).

Note that the repeated squaring of the Fibonacci matrix can be performed
more easily than squaring an arbitrary matrix, since all powers of
the matrix are symmetric.\v

The code follows: \v
\beginverbatim
x = 1;
``Initialize the Fibonacci Matrix''
a11 = 1;
a12 = 1;
a22 = 0;

a = seq(a11,a12,a22);
`` Procedure for multiplying matrices of our special form mod q''
procedure mult(a,b,q;c);
        c11 = (a[1]*b[1] + a[2]*b[2]) mod q;
        c12 = (a[1]*b[2] + a[2]*b[3]) mod q;
        c22 = (a[2]*b[2] + a[3]*b[3]) mod q;
        c = seq(c11,c12,c22);
end;

``Procedure writes the integer q into a reverse binary sequence''
procedure decomp(q;bin);
        bin = empty;
        while q ne 0 do
                r = q mod 2;
                q = (q-r)/2; 
                bin = append(bin,r);
        end;
end;

``Main Program''
zz = 50000000 mod 30;
for i = (50000000 - zz + x) to 100000000 by 30 do
        if i mod 1000000 lt 30 then 
                print ' done up to ',i;
        end;
        if not prime(i) then
                loop;
        end;
        y = i\^2;
        ``Split into two cases; determine the appropriate multiple
          of Walls Number.''
        if ((i mod 5) eq 1) or ((i mod 5) eq 4) then
                k = i-1;
        else k = 2*i+2;
        end;
        decomp(k;bin);
        u= seq(1,0,1);
        ustore = u;
        m = conseq(u,length(bin));
        m[1] = a;
        b = a;
        ``Compute the appropriate power of the Fibonacci matrix mod y
          using the method of repeated squaring.'';
        for j = 2 to length(m) do
                mult(b,b,y;b);
                m[j] = b;
        end;
        for j = 1 to length(m) do
                if bin[j] eq 1 then
                        mult(u,m[j],y;u);
                end;
        end;
        if u eq ustore then
                print '*****violator*****',i;
        end;
end;
print ' done ';
show time;
\endverbatim
\vfill \eject

\centerline{\bf Acknowledgements}\v

We wish to acknowledge the contribution of various people in making this
work possible.\v

Rick Thomas' survey [Th] and other preprints first stimulated our interest
in this problem. The Computational Group Theory system CAYLEY developed
in Sydney by John Cannon and many others enabled us to discover ``experimental
truths'' which we then had to try to prove.\v

Converstaions and correspondence with several people has been most useful.
Dave Johnson has been most helpful in pointing out slips in early drafts
of this document, and in suggesting further lines of research. We are also
grateful to seminar audiences who have watched this theory develop, and
have given us considerable encouragement. It would not be possible to
mention all the names, and so we mention none.\v

The first author acknowledges with gratitude the financial support of
Ataturk University in Erzurum, Turkey, during his stay at Bath University
in the United Kingdom.

\vfill \eject
\end
