\documentstyle{article}
\title{\huge Wall and Vinson Revisited} 
\author{Huseyin Aydin\\ 
\and
Ramazan Dikici\thanks{The work of the first two authors 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}
\begin{document}
\maketitle

\section{Introduction}
Let $G$ be a finite group. 
We define a family of recurrences, parameterized
by natural numbers $n,$ 
via equations
$$ x_i = x_{i-1}x_{i-2}\cdots x_{i-n}. \leqno (R_n)$$

We fix $n > 1.$
We may `start' the recurrence with any initial data $g_0,g_1,\ldots,g_{n-1}$
and then the recurrence will define a periodic bi-infinite sequence
$(g_i)$ indexed by the integers. We use the term {\em loop} to describe
a bi-infinite sequence satisfying the recurrence. Notice that if 
$\alpha \in \Z,$ then putting $h_i = g_{i+\alpha}$ for $0 \le i < n$
we obtain a another set of initial data. The recurrence $R_n$ then gives
us another loop $(h_i)$ of $G.$ Notice that $(h_i)$ is just $(g_i)$ shifted
through $\alpha$ steps. We say that $(h_i)$ is a {\em rotation} of $(g_i).$\par 

The fundamental period of a loop is clearly a significant number, and
we call it {\em Wall's number} after a pioneer in this area. Following
Wall \cite{Wa} we shall use the letter $k$ (suitably adorned) to describe
this period. We shall clarify this point later. In all fairness, we should
really cite Lucas rather than Wall, but the term {\em Lucas Number}
is already in 
use. The reader's attention is drawn to \cite{Lu},\cite{Ri} and 
\cite{RS}.\par 

Wall investigated the recurrence $R_2$ in finite cyclic groups. This subject
immediately reduces to the study of cyclic groups of prime power order.
This paradigm is exploited elsewhere \cite{APhD,ASTe,ASLMS} 
to study recurrences
in finite nilpotent groups, since they are the cartesian product of their
Sylow $p-$subgroups. Another early contributor to this field was 
Vinson \cite{Vi}, who was particularly interested in ranks of apparition,
a mistranslation from the French. More interest has come in the 
form of \cite{CDR,Do,So,Th} and \cite{Wi}.\par 

There have been exciting recent developments in this area. Pinch \cite{Pi}
has studied the relationship between the period of a general linear 
recurrence modulo a rational prime $p,$ and the period modulo a power of
that prime. He does this via examining the algebraic number theory
of certain finite extensions of the $p-$adic numbers.\par

Wall distinguishes the special loop $s = (s_i)$ with initial data
$s_0 = 0$ and $s_1 = 1$ in $\Z/p^n\Z.$ Let $k(s,p^n)$ denote the
fundamental period of $s.$

\begin{theorem} (D.D. Wall\cite{Wa}) 
\label{big}
The number $k(s,p^n)$ divides $k(s,p)p^{n-1},$ and the two
quantities are equal provided $k(s,p) \not = k(s,p^2).$
\end{theorem}
Wall goes on to conjecture that for all primes $p,$ we always have
$k(s,p) \not = k(s,p^2).$ He announced that he had verified this
result for all primes $p < 10^4.$ We have tested the conjecture on more
modern computers, and can confirm that the result holds for all primes
less than $10^8.$ We include the code in Appendix A, in case the reader
is interested in chasing still further.

The theorem \ref{big} has recently been generalized. A slightly weaker
version of it
is now known to hold in any finite $p-$group $P$ for arbitrary
$t-$step linear recurrences  \cite{ASLMS}. The r\^ole of $n$ in this context is
the minimum length of an exponent $p$ central series of $P.$

In Appendix B we include some mysticism; 
an unjustifiable probabilistic argument 
to persuade the gullible that Wall's conjecture is true.

Let us consider the more general recurrences written multiplicatively as
$$ x_i = x_{i-1}^{a_1}x_{i-2}^{a_2}\cdots x_{i-n}^{a_n}$$
or additively as
$$ x_i = \sum_{r=1}^n a_rx_{n-r} \leqno (A_n).$$
The exponents/coefficients are deemed to be integers.
Such a recurrence may not be so well behaved as $R_n,$ for it may be
singular in a particular group. This means that initial data may
not define a unique bi-infinite periodic sequence; the problem
arises when attempting to extend the sequence through negative
integer subscripts. Certainly all is well if $a_n \in \{1,-1\}.$
Equally well, if we are working in a $p-$group all is well provided
$gcd(p,a_n) = 1.$ We shall assume, from now on, that all our sequences
are non-singular in the groups to which we apply them. This
important {\em caveat} should be noted, since we do not intend
to adjoin non-singularity conditions repeatedly to our results.
\section{ Two Step Recurrences}

The theory of general two-step recurrences is very well understood.
See \cite{Lu}, and chapter 2 of \cite{Ri}. The following
results of this section are well-known \cite{Vi,Wa}. 
\begin{theorem}
\label{temp}
Let $H$ be the additive group of a finite field $K = GF(p^t).$ 
Consider the standard sequence $s = (s_i)$ for the recurrence $A_2.$ Let
$k(s)$ denote the Wall number of $s.$ Suppose $b = (b_i)$ is any loop
satisfying $A_2$ in $H,$ then $k(b)$ divides $k(s).$ If $k(b) < k(s)$
then $b$ must either be the trivial loop (all entries 0) or must be a geometric
sequence,
\end{theorem} 

\section{ Higher Step Recurrences}
Here we believe that our results may be new.
We now press on to discuss the recurrences $R_3$ and $R_4.$ We concentrate
initially on the cases where each $a_i$ is 1, the Fibonacci case.
We work in the additive group $H$ of a finite
field as before. We will find that the analysis of this case is remarkably 
similar to the case $R_2,$ but that moving up to $R_4$ the situation
becomes more complex.

Let the standard loop $s$ begin (0,0,1), and let its period be $k_3(p),$
written as $k$ in this section. As before, the period of any loop must
divide $k$ for the usual reasons.

\begin{theorem}
\label{te}
Short loops must be geometric for the 3-step Fibonacci recurrence
in $H,$ the additive group of the finite field $GF(p^n).$
\end{theorem}
{\em Proof\ } We tackle this proof via a sequence of lemmas.
Let $f$ be any non-trivial loop containing two consecutive
zeros. It must be a non-zero scalar multiple of a rotation of the
standard loop and so has period $k.$
Now suppose that $g$ is a non-trivial loop containing
at most one consecutive zero. By rotation and scaling we may assume
that $f$ begins $0,1,\alpha$ for some 
$\alpha \in H.$

Let the roots of $X^3 - X^2 - X - 1$ be $\tau_1,\tau_2$ and $\tau_3.$
The discriminant of $X^3 - X^2 - X - 1$ is 44, so in what follows, we ban the
primes 2 and 11 as being bad, and analyze them separately. Thus
$\tau_1,\tau_2$ and $\tau_3$ are distinct and $\tau_1\tau_2\tau_3 = 1.$
We distinguish six special loops $(j \in \{1,2,3\})$
$$r(j) = (1,\tau_j,\tau_j^2,\ldots)$$
and
$$h(j) = (0,1,1-\tau_j, \ldots).$$
\begin{lemma}
\label{fred}
If $i \not = j$ then $lcm(k(h_i),k(h_j)) = k.$
\end{lemma}

{\em Proof}
 $h_i - h_j = (t_j - t_i) \cdot s$ where $s$ is the standard loop. Thus
$k(h_i - h_j) = k$ so $lcm(k(h_i), k(h_j)) = k.$\bigskip
\begin{lemma}
\label{john}
If $i,j$ and $m$ are distinct then
$k(h_m)\ |\ lcm( k(r(i)),k(r(j))).$
\end{lemma}
{\em Proof}
To see this, notice that $r(i) - r(j) = (\tau_i - \tau_j) h_m$ --
here we are using the fact that $\tau_1 + \tau_2 + \tau_3 = 1.$
Thus $k(h_m)\ |\ lcm( k(r(i),k(r(j)).$\bigskip

\begin{lemma}
\label{mary}
If $i \not = j$ then $lcm(k(r_1),k(r_2),k(r_3)) =
lcm(k(r(i),k(r(j)))).$
\end{lemma}
{\em Proof}
Let 
$$z = lcm(o(\tau_1),o(\tau_2)) = lcm(k(r(1)),k(r(2))).$$ 
Now raising the equation
$\tau_1\tau_2\tau_3 = 1$ to a power we obtain $\tau_1^z\tau_2^z\tau_3^z = 1.$
Thus $o(\tau_3)\ |\ z$ so $$lcm(o(\tau_1),o(\tau_2),o(\tau_3))= z.$$ 
The choice of $\tau_1$ and $\tau_2$ was arbitrary so our claim
is justified.\bigskip
\begin{lemma}
\label{ kate}
If $i \not = j$ then $lcm(k(r(i)),k(r(j))) = k.$
\end{lemma}
{\em Proof}
By \ref{fred} we have $k = lcm(k(h_1),k(h_2)).$ 
Now we
deploy \ref{john} to deduce that $k$ must divide
$$lcm(lcm(k(h_2),k(h_3)),lcm(k(h_1),k(h_3))) = lcm(k(r(1)),k(r(2)),k(r(3))).$$
Finally we deploy \ref{mary} to obtain that 
$k$ divides $lcm(k(r(i)),k(r(j)))$ whenever $i$ and $j$ are distinct. 
However $k(r(i))$ and $k(r(j))$ must be divisors of $k$ and so
we are done.

\begin{lemma}
\label{harry}
 
If $i,j,m$ are distinct then 
$lcm(k(r(i)),k(r(j)))\ |\ k(h_m).$
\end{lemma}
{\em Proof}
To see this, notice that 
$r(i) - r(j) = (\tau_i-\tau_j)(0,1,1-\tau_m.\ldots)$
and so has length $k(h_m).$ Now \mbox{$\tau_i^{k(h_m)} - \tau_j^{k(h_m)} = 0$}
and $\tau_i^{k(h_m)+1} - \tau_j^{k(h_m)+1}= \tau_i - \tau_j.$
Subtracting we obtain $\tau_i^{k(h_m)} = 1.$
Thus $k(r(i))\ |\ k(h_3)$ whenever $i$ and $m$ are distinct
as required.

Piecing together \ref{john} and \ref{harry} we have established that
$k(h_i) = k$ for all $i \in \{1,2,3\}.$
It remains to address loops of the form $(0,1,1-\alpha,\ldots)$ where
$\alpha$ is {\em not} a root of $X^3 - X^2 - X - 1.$
Consider the matrix 
$$A = \pmatrix{0 & 1 & 1-\alpha \cr 1 & 1-\alpha & 2-\alpha
	       \cr1-\alpha & 2-\alpha & 4 - 2\alpha}.$$	


More matrices are useful. We define them as
$$F = \pmatrix{0 & 1 & 0 \cr 0 & 0 & 1 \cr 1 & 1 & 1},$$
$$B = \pmatrix{0 & 1 & 1 \cr 1 & 1 & 2 \cr 1 & 2 & 4} $$ and finally
$$C = \pmatrix{0 & 0 & 1 \cr 0 & 1 & 1 \cr 1 & 1 & 2}.$$
Notice that $A = B - \alpha C = (F - \alpha I)C$
so $det(A) = det(F-\alpha I)(-1)^3 = det(\alpha I - F) = 
\alpha^3 - \alpha^2 - \alpha -1.$ However,
the choice of $\alpha$ forces $det(a) \not = 0.$ The fact that
$A$ is non-singular enables us to write  the standard
loop $s$ as a linear combination of rotations of 
$(0,1,1-\alpha,\ldots).$ Thus such a loop $(0,1,1-\alpha,\ldots)$
must have period $k.$

We conclude that any non-trivial short loop must contain no entry which
is 0. By the same argument used in the two step case it follows
that any candidate short loops must be geometric progressions with
common ratio a root of $X^3 - X^2 - X - 1$ and we have proved
\ref{te}. 

The situation here is more complex than in the two step case; it is 
possible for all three roots to give rise to genuine short loops.
We shall call these loops {\em golden loops}. The first few instances
of this phenomenon we outline here.
\begin{verbatim}
Prime               Golden Loop Length         Wall Number 

 4481                   2240                    4480
                         640			 
                         896

 4621                     84                    4620
                         660			
                        2310

 6007                    182                    2002
                         154
                        1001

 6917                    364                    6916
                         532
                        3458

14281                    595                    4760
                         680
                         952

\end{verbatim}
Passing to the Fibonacci 4-step recurrence the situation gets less pleasant.
It is possible for non-trivial short loops to have entries which vanish.
The prime 7 is a case in point. Walls number is 342 in $GF(7)$ but
there is a short loop containing a 0 of length 171.
   
\section{ Appendix A:  Computer Search}
We sought a counterexample to Wall's conjecture, and failed to find one
less than $10^8.$
We ran programs 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 \cite{Ca} 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).

{\em Added after the conference:}\\

Dr Dresel of Reading, England was kind enough to point out some 
references which we
had missed. Specifically, his letter \cite{Dr} and the paper of Heed \cite{He}.
There is no substantial difference between the zero-entry problem (studied
by Heed) and Wall's conjecture as we call it. Dresel performed a
search for a prime violating Wall's conjecture and had dealt with those
less than $10^6$ by 1977. Dresel's calculations used a different method
from ours, but the complexity is about the same.

The paper of Heed contains a `calculation' that the expected number of 
violations of Wall's conjecture
is infinite. In the course of the argument he makes certain 
plausible probabilistic assumptions.
However, he finds that the expected number of violations less than $P$ is
approximately $ln ln P.$ Thus, using Heed's argument, Dresel should have 
found about $2.6$ violators, and we should have found about $2.9.$
Notice that $ln ln 10^{8.7}$ is close to 3. We could push the 2.9 to 3
by doing about 5 times more work than has been done already.


\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''
J. London Math. Soc. {\em to appear}.
\bibitem{CDR} C. M. Campbell, H. Doostie and E. F. Robertson,
``Fibonacci Length of Generating Pairs in Groups'', Applications of
Fibonacci Numbers, ed. G.E. Bergum, A.N. Philippou and A.F. Horadam,
Kluwer vol.3 (1990), 27-35.
\bibitem{Ca}J.J. Cannon, An introduction to the group theory 
language Cayley, in
Computational Group Theory, edited by M.D. Atkinson, Academic Press, London,
1984, 145--183.
\bibitem{Do} H. Doostie, ``Fibonacci-type Sequences and Classes of
Groups'', Ph.D. thesis, St Andrews (1988).
\bibitem{Dr} L. A. G. Dresel ``Letter to the Editor'',  
The Fibonacci Quarterly,
15 (1977), 346.
\bibitem{He} J. J. Heed ``Wieferichs and the Problem $z(p^2) = z(p)$'',
The Fibonacci Quarterly 22 (1964), 116-118. 
\bibitem{Lu} E. Lucas ``Th\'eorie des fonctions num\'eriques simplement
p\'eriodiques'', Amer. J. Math., 1, (1878) 184-240 and 289-321
\bibitem{Pi} R. G. E. Pinch ``Linear Recurrent Sequences modulo
prime powers'', {\em to appear } Proc. $3^{rd}$ IMA Conference on Coding
and Cryptography, Cirencester, England. December 1991.
\bibitem{Ri} P. Ribenboim ``The Little Book of Big Primes'', Springer-Verlag
(1991).
\bibitem{RS} J. A. Reeds and N. J. A. Sloane, ``Shift Register synthesis
(modulo m)'', SIAM J. Comput. 14 (1985) 505-513.
\bibitem{So} L. Somer, ``The Divisibility Properties of Primary
Lucas Recurrences with Respect to Primes'', The Fibonacci Quarterly
18 No 4 (1980), 316-334.
\bibitem{AX} R. S. Sutor (ed.), ``AXIOM user guide'', NAG Ltd, (1991)
\bibitem{Th} R. M. Thomas, ``The Fibonacci Groups Revisited'',
in C. M. Campbell and E. F. Robertson
(eds.), Proceedings of Groups St. Andrews 1989 vol. 2 LMS Lecture
Note Series 160, CUP, (1991) pp 445 -454.
\bibitem{Vi} J. Vinson,`` The Relations of the Period
Modulo $m$ to the Rank of Apparition of $m$ in the Fibonacci Sequence'',
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'', The Fibonacci Quarterly 24 (1986), 356-361.


\end{thebibliography} 
{\em Present address of the first author:}\\
Ataturk University\\
Fen-Ed Faculty\\
Department of Mathematics\\
Erzurum, Turkey
\end{document}
\end
