\documentstyle{article}
\title{\huge Fourier Analysis in Finite Nilpotent Groups } 
\author{Huseyin Aydin
\thanks{The work of the first author was supported
by Ataturk University, Erzurum, Turkey
}\\
\and
Geoff C. Smith\\
School of Mathematical Sciences, University of Bath, Bath BA2 7AY, England
}
\date{}
\pagestyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\def\empty {\emptyset}\let\bold=\bf
\def\Z{{\bf Z}}
\def\Q{{\bf Q}}
\def\lr{\longrightarrow}
\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}
\parindent=0cm
\parskip=0.2cm
\renewcommand{\baselinestretch}{1.5}
\begin{document}
\maketitle
\section{Introduction}
Let $s$ denote the ordinary {\em Fibonacci sequence} taken modulo a natural
number $m.$ This is a bi-infinite periodic sequence (or {\em loop})
indexed by the integers.
Thus $s = (s_i)$ and $s_0 = 0, s_1 =1.$ The shortest period of this sequence
is called the fundamental period, and it will be denoted by
$k.$ We sometimes refer to this quantity as {\em Wall's Number}\cite{Wa}.
In the course of investigating recurrences in finite 
nilpotent groups, the authors have been drawn into investigating
the sums of monomials (manufactured from $s$) where the range of summation
is a fundamental period. As is well-known, $\sum_0^{k-1} s_i = 0.$
The fundamental periods of loops associated with 
recurrence relations in finite nilpotent groups can be governed by sums
far more complex than this. Indeed, the authors have been driven to
show that sums such as
$$ \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} $$
actually vanish. The reader wishing for the full and intricate details
should consult \cite{APhD} or \cite{ASTe}. The group theoretic implications
of these calculations are summarized in \cite{ASLMS}. The techniques
for handling multiple sums are similar in spirit to those demonstrated
here, but the manipulations are considerably longer.

In the course of this note, we shall concentrate on the evaluation of certain
single sums, chosen for simplicity rather than because
of their particular importance. We lose nothing
by insisting that we work modulo a rational prime power $q$
rather than an arbitrary natural number $m.$ In what follows, we shall
actually assume that $q = p$ is prime -- the arguments are the same
but the discussion of bad cases is marginally easier. We propose the name 
{\em Fourier Sums} for sums of this general type, by analogy with
Fourier Integrals. In conventional Fourier analysis, one does at least
know the length of a fundamental period; in our case this is not available.
Whilst \cite{Lu}, \cite{Vi} and \cite{Wa} provide us with bounds on $k,$
as far as the authors are aware there is no known closed formula for $k.$
We draw the reader's attention to \cite{Ri} which, in chapter 2, gives
an admirable summary of the properties of Lucas sequences modulo a prime.
 
The authors acknowledge the assistance of the Computer Algebra
system CAYLEY \cite{Ca} which enabled them to discover empirical 
evidence for the results in this note, though the proofs here are
not machine aided. Indeed, it was a discovery using CAYLEY which really
led to our pursuit of this subject; this was the fact that
there is a connection between the Burnside problem and
Fibonacci Groups. Let $B(r,n)$ denote the group on $r$ generators
subject to the infinite collection of relators $w^n$ where $w$ ranges
over all words in the generators and their inverses. This is called
the {\em Burnside} group on $r$ generators of exponent $n.$ The group
$B(r,n)$ may be finite or infinite, but in any event it will have
a unique largest finite quotient group, denoted $R(r,n).$ The latter
group is termed the {\em Restricted Burnside} group with the relevant 
parameters. The existence $R(r,n)$ is a highly non-trivial matter.
The history of the proof of its existence is long and complicated,
and we cannot do it justice here.

Partial results were obtained by Kostrikin \cite{Ko}, and 
Zelmanov \cite{Ze} has recently finished the proof. 
For background material in this area,
the reader may wish to consult \cite{VL}. The proof relies upon an
argument of P. Hall and G. Higman \cite{HH} and on the
classification of finite simple groups.

Consider the particular group $R(2,5),$ the restricted
Burnside group on two generators of exponent 5 (of order $5^{34}$); this
is a quotient of the two step Fibonacci group on 20 generators. The Fibonacci
groups are a class of finitely presented groups with presentations
manufactured from Fibonacci-type recurrences. The interested reader
should consult the excellent survey of Thomas \cite{Th}, and the papers of
Johnson and his co-workers \cite{CJ,J74,JWW}. We acknowledge helpful
conversations with Dave Johnson and Rick Thomas. 

From now on we shall assume that all sums are taken over a fundamental period.

\begin{theorem}
\label{main} The following equations all hold. They are 
$$\sum s_i = 0,\leqno (A)$$

$$\sum s_i^2 = 0,\leqno (B)$$

$$\sum s_i^3 = 0, \leqno (C)$$
and, providing $p \not = 3,$
$$\sum s_i^4(-1)^i = 0. \leqno (D)$$
If $p \not = 11$ then $$\sum s_i^5 = 0. \leqno (E)$$
\end{theorem}
\begin{theorem}
\label{subsid}
The following equations also hold. They are
$$\sum s_i(-1)^i = 0,\leqno (A')$$
$$\sum s_i^3(-1)^i = 0, \leqno (C')$$
and if $p \not = 11$ then $$\sum s_i^5(-1)^i = 0. \leqno (E')$$
\end{theorem}
\section{ Results and Conjectures }
We point out that summing (integrating) a periodic function over a fundamental
period is both translation invariant and reflection invariant. 
Thus, for example, we have 
$$\sum s_i^{19} = \sum s_{i-42}^{19}= \sum s_{k-i}^{19}.$$ This proves
to be a fruitful observation.

We announce that $$\sum s_{i}^{6} = 0. $$
Moreover, it is also true that
$$\sum s_{i}^7 = 0 $$
and
$$\sum (-1)^is_{i}^7 = 0$$
unless $p=11$ or $29.$ These results may be proved using the techniques
which are developed in section 4, and are available in \cite{APhD}.

The sums which are mysteriously absent from \ref{main} and
\ref{subsid} are not missing through oversight.
The following results may be found in \cite{APhD}. For obvious reasons,
the prime 5 is excluded.

$$\sum (-1)^is_{i}^2=-{2\over 5}{k}$$ 
$$\sum s_{i}^4={6\over 25}{k}$$ 
$$\sum (-1)^is_{i}^6=-{4\over 25}{k}$$ 
$$\sum s_{i}^8={14\over {125}}{k}.$$

We conjecture that, if $n=4l+2,$ then
$\sum (-1)^is_{i}^n$ is a rational multiple of $k$ and only powers
of 5 can occur in the denominator of the rational multiplier.
Also we conjecture that, if $n=4l,$ then $\sum s_{i}^n$ can be similarly
described. Otherwise we conjecture that the corresponding sums vanish,
save, for fixed exponent, for at most finitely many bad primes.
\section{ New Directions }

These results are clearly only of limited interest in their own right.
They take on deeper significance when interpreted in terms of the
behaviour of recurrences in other algebraic structures. Similar
summations must be performed using arbitrary recurrences, rather than
the Fibonacci two-step. The special identities which render the Fibonacci
problem tractable are not available in general, or, put another way,
new identities would have to be constructed using the coefficients
of the general $n$-step recurrence. This {\em ad hoc} procedure is all
very well for the Fibonacci case, but there is no hope of developing
a general theory out of raw algebraic manipulation. 

To address this problem, Smith and Dikici are developing methods
which turn the problem of evaluating the sums into linear algebra
(of countable dimensional space). They can often solve the resulting systems
of equations by looking at sufficiently large finite subproblems.
They end up calculating row echelon forms of fairly substantial
integer matrices (typically several hundred rows and columns) using
Computer Algebra systems. These calculations will form the basis of 
Dikici's thesis, and will be available for publication shortly. Traces
of this method begin to appear in the proofs of $(D)$ and $(E)$ in section 4.
\section{ Proofs }
 
We make the blanket assumption that $p \not =2,$ since our 
results all hold (trivially) in that case, but the proofs in the sequel
do not. An awkward feature of $2$ is that $k = 3$ is odd. 

{\em Proof} of $(A).$
$$\sum s_i = \sum (s_{i-1} + s_{i-2}) = 2\sum s_i$$
so $\sum s_i = 0.$

{\em Proof} of $(B).$
$$\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}. \leqno (1)$$

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}. \leqno (2)$$

Adding (1) and (2) we obtain
$$\ 2\sum s_i^2 = 4\sum s_i^2$$
from which the equation $(B)$ follows.
 
{\em Proof}  of $(C).$
$$ \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. \leqno
(3)$$
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. \leqno (4)$$
Add $(3)$ and $(4)$ 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.\leqno (5)$$
Now we adjust $(5)$ 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. \leqno (6)$$
From $(3)$ and $(5)$ we know
$$ \sum s_i^3 + 3\sum s_i^2 s_{i-1} = 0. \leqno (7)$$
Subtract $(7)$ from $(6)$ to obtain the result.\\
Wall's number $k$ is even \cite{Wa}, 
and of course the {\em Cassini }
identity holds modulo $p,$ 
$$s_i^2 = s_{i-1}s_{i+1} + (-1)^{i+1}\hbox{ for all integers } i .\leqno (8)$$ 
Moreover we have
$$s_{k-i} = s_{-i} = s_i(-1)^{i+1}\hbox{ for all integers } i \leqno(9)$$

{\em Proof} of $(A')$ and $(C').$ Apply (9) to $(A)$ and $(C).$ Notice that
one may always deduce $\sum s_i^{2t+1}(-1)^i=0$ from $\sum s_i^{2t+1}
=0.$

{\em Proof} of $(D).$
$$\sum s_i^4 (-1)^i = 0.\leqno (10)$$

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 being obtained using $(9)$ and the fact that $k$ is even.
Now reverse the direction of summation to obtain
$$\beta = \sum_{i=1}^k s_{i-1}^3s_{i+1}(-1)^i 
= \sum_{i=1}^{k-1} s_{i-1}^3s_{i+1}(-1)^i= \gamma,$$
the final equality being obtained by translation of the range.

Our next ambition is to show that $\alpha = \delta.$ We deploy
(8) 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 (B)  and $\sum (-1)^i = 0$ since $k$ is even, so
$\alpha = \delta.$

Our next target is to show that $\epsilon = \zeta.$ We have
$$\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).$ Notice that
$$\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.$ We have 
$$\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 $(9),$ 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.$$
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 \leqno(11).$$

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. \leqno (12)$$

Adding (11) and (12) we obtain $12\alpha = 0$ from which
the result follows unless $p=3.$  When $p=3$ the result is true
by inspection.
\begin{cor}

$$\beta = \sum s_{i+1}^3s_{i-1}(-1)^i = 0$$
$$\gamma = \sum s_{i+1}s_{i-1}^3(-1)^i = 0$$
$$\delta = \sum s_{i+1}^2s_{i-1}^2(-1)^i = 0$$
$$\epsilon = \sum s_i^3 s_{i-1}(-1)^i = 0$$
$$\zeta = \sum s_is_{i-1}^3(-1)^i = 0$$
$$\eta = \sum s_{i}^2s_{i-1}^2 (-1)^i = 0$$
\end{cor}

{\em Proof} of $(E)$ and $(E').$
Let $\theta = \sum s_i^5$ then

$$\theta = \sum (s_{i+1} - s_{i-1})^5$$  so
$$\theta = -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
$$ \theta = -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 (8) to obtain
$$\theta = -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 }(C') $$
$$\hbox{ } \sum s_{i-1}^3(-1)^{i+1} = 0 \hbox{ from }(C') $$
$$\hbox{ } \sum s_i^3(-1)^{i+1} = 0 \hbox{ also from }(C')$$
and
$$\hbox{ } \sum s_i = 0 \hbox{ from }(A).$$
Thus $$\theta = -5\sum s_i^2(s_{i+1}^3 - s_{i-1}^3) + 10\theta,$$
and so $$ -9\theta = -5\sum s_i^2 (s_{i+1}^3 - (s_{i+1} - s_i)^3).$$
Expanding we obtain
$$-9\theta = -5\sum s_i^2(3s_{i+1}^2s_i -3s_{i+1}s_i^2 +s_i^3).$$
Thus we have
$$-9\theta = -5\sum s_i^2 (3s_{i+1}s_i(s_{i+1} - s_i) + s_i^3)$$
and therefore
$$-9\theta = -5\sum s_i^2 (3s_{i+1}s_is_{i-1} + s_i^3).$$
We now close on our quarry using (8)  again. We have
$$-9\theta = -5\sum s_i^2 (3s_i(s_i^2 + (-1)^i) + s_i^3).$$
Once again we may suppress $(-1)^i$ because of $(C').$ Thus
$$-9\theta = -5\sum 4s_i^5 = -20\theta.$$
We conclude that $11\theta = 0.$ Since we have excluded the
prime 11, we have demonstrated the truth of $(E).$ Now $(E')$ follows
in the usual way.

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

\begin{thebibliography}{99}
\bibitem{APhD} H. Aydin. ``Recurrence Relations in Finite Nilpotent Groups'',
Ph.D. thesis, Bath (1991).
\bibitem{ASTe} H. Aydin and G. C. Smith. 
``Remarks on Fibonacci Sequences in Groups 1'',
Bath Mathematics and Computer Science Technical Report 91-50,
University of Bath 1991.
\bibitem{ASLMS} H. Aydin and G. C. Smith. 
``Finite p-Quotients of Some Cyclically Presented Groups'', {\em J. London Math. Soc.} to appear.
\bibitem{Ca} J.J. Cannon. ``An introduction to the group theory language 
Cayley'', in
{\em Computational Group Theory}, edited by M.D. Atkinson, Academic Press, London,
1984, 145--183.
\bibitem{CJ} C.P. Chalk and D.L. Johnson. ``The Fibonacci Groups II'',
{\em Proc. Royal Soc. Edinburgh}  77A, (1977), 79-86.
\bibitem{HH} P. Hall and G. Higman. ``On the $p-$length of $p-$soluble
Groups and Reduction Theorems for Burnside's Problem'', {\em Proc. London Math. 
Soc.,} 6 (1956), 1-42.
\bibitem{J74} D.L. Johnson. ``A Note  on the Fibonacci Groups'',
{\em Israel J. Math.} 17 (1974), 277-282.
\bibitem{JWW} D.L. Johnson, J.W. Wamsley and D. Wright.
``The Fibonacci Groups'', {\em Proc. Lond. Math. Soc.} (3) 29, (1974), 577-592.
\bibitem{Ko} A.I. Kostrikin. ``The Burnside Problem'', {\em Izv. Akad. 
Nauk SSSR,
Ser. Mat.} 23 (1959), 3-34.
\bibitem{Lu} E. Lucas. ``Th\'eorie des fonctions num\'eriques simplement
p\'eriodiques'', {\em Amer. J. Math.} 1, (1878), 184-240 and 289-321. 
\bibitem{Ri} P. Ribenboim. {\em The Little Book of Big Primes}, Springer-Verlag
(1991).
\bibitem{Th} R. M. Thomas. ``The Fibonacci Groups Revisited'',
in C. M. Campbell and E. F. Robertson
(eds.), {\em Proceedings of Groups St. Andrews 1989} vol. 2 LMS Lecture
Note Series 160, CUP, (1991) pp 445-454.
\bibitem{VL} M. Vaughan-Lee. {\em The Restricted Burnside Problem}, Oxford
University Press (1990). 
\bibitem{Vi} J. Vinson.`` The Relations of the Period
Modulo $m$ to the Rank of Apparition of $m$ in the Fibonacci Sequence'',
{\em The Fibonacci Quarterly} 1 (1963), 37-45.
\bibitem{Wa} D. D. Wall. ``Fibonacci Series Modulo $m$'',
Amer. Math. Monthly 67 (1960), 525-532.
\bibitem{Wi} H. J. Wilcox. ``Fibonacci Sequences of Period
$n$ in Groups'', {\em The Fibonacci Quarterly} 24 (1986), 356-361.
\bibitem{Ze} E. I. Zelmanov. `` Solution of the Restricted Burnside
Problem for groups of odd exponent'', {\em Izv. Akad. Nauk SSSR Ser. Mat.} 
54 (1990), 42-59, 221 (Russian). English translation (J. Wiegold) {\em Math.
USSR-Izv.} 36 (1991) no. 1, 41-60. The even exponent case will appear in
{\em Mat. Sbornik}.
\end{thebibliography} 
{\em Present address of the first author:}\\
Ataturk University\\
Fen-Ed Faculty\\
Department of Mathematics\\
Erzurum, Turkey

\end{document}
\end
