Wall and Vinson Revisited

Huseyin Aydin  Ramazan Dikici^{∗}

Geoff C. Smith

School of Mathematical Sciences, University of Bath, Bath BA2 7AY, England

1 Introduction

Let G be a finite group. We define a family of recurrences, parameterized by natural numbers n, via equations

(R_{n})  x_{i} = x_{i−1}x_{i−2} ⋯ x_{i−n}.

We fix n > 1. We may ‘start’ the recurrence with any initial data g_{0}, g_{1}, …, g_{n−1} and then the recurrence will define a periodic bi-infinite sequence (g_{i}) indexed by the integers. We use the term loop to describe a bi-infinite sequence satisfying the recurrence. Notice that if α ∈ Z, then putting h_{i} = g_{i+α} for 0 ≤ 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 α steps. We say that (h_{i}) is a rotation of (g_{i}).

The fundamental period of a loop is clearly a significant number, and we call it Wall’s number after a pioneer in this area. Following Wall [17] 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 Lucas Number is already in use. The reader’s attention is drawn to [9],[11] and [12].

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 [1, 2, 3] 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 [16], who was particularly interested in ranks of apparition, a mistranslation from the French. More interest has come in the form of [4, 6, 13, 15] and [18].

∗The work of the first two authors was supported by Ataturk University, Erzurum, Turkey

There have been exciting recent developments in this area. Pinch [10] 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.

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.

Theorem 1.1 (D.D. Wall[17]) The number k(s, p^{n}) divides k(s, p)p^{n−1}, and the two quantities are equal provided k(s, p) ≠ k(s, p^{2}).

Wall goes on to conjecture that for all primes p, we always have k(s, p) ≠ 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 1.1 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 [3]. The rôle 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}} ⋯ x_{i−n}^{a_{n}}

or additively as

(A_{n}).  x_{i} = ∑_{r=1}^{n} a_{r}x_{n−r}

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} ∈ {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 caveat should be noted, since we do not intend to adjoin non-singularity conditions repeatedly to our results.

2 Two Step Recurrences

The theory of general two-step recurrences is very well understood. See [9], and chapter 2 of [11]. The following results of this section are well-known [16, 17].

Theorem 2.1 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,

3 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.

Theorem 3.1 Short loops must be geometric for the 3-step Fibonacci recurrence in H, the additive group of the finite field GF (p^{n}).

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, α for some α ∈ H.

Let the roots of X^{3} − X^{2} − X − 1 be τ_{1}, τ_{2} and τ_{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 τ_{1}, τ_{2} and τ_{3} are distinct and τ_{1}τ_{2}τ_{3} = 1. We distinguish six special loops (j ∈ {1, 2, 3})

r(j) = (1, τ_{j}, τ_{j}^{2}, …)

and

h(j) = (0, 1, 1 − τ_{j}, …).

Lemma 3.2 If i ≠ j then lcm(k(h_{i}), k(h_{j})) = k.

Proof h_{i} − h_{j} = (t_{j} − t_{i}) · s where s is the standard loop. Thus k(h_{i} − h_{j}) = k so lcm(k(h_{i}), k(h_{j})) = k.

Lemma 3.3 If i, j and m are distinct then k(h_{m}) | lcm(k(r(i)), k(r(j))).

Proof To see this, notice that r(i) − r(j) = (τ_{i} − τ_{j})h_{m} – here we are using the fact that τ_{1} + τ_{2} + τ_{3} = 1. Thus k(h_{m}) | lcm(k(r(i), k(r(j)).

Lemma 3.4 If i ≠ j then lcm(k(r_{1}), k(r_{2}), k(r_{3})) = lcm(k(r(i), k(r(j)))).

Proof Let

z = lcm(o(τ_{1}), o(τ_{2})) = lcm(k(r(1)), k(r(2))).

Now raising the equation τ_{1}τ_{2}τ_{3} = 1 to a power we obtain τ_{1}^{z}τ_{2}^{z}τ_{3}^{z} = 1. Thus o(τ_{3}) | z so

lcm(o(τ_{1}), o(τ_{2}), o(τ_{3})) = z.

The choice of τ_{1} and τ_{2} was arbitrary so our claim is justified.

Lemma 3.5 If i ≠ j then lcm(k(r(i)), k(r(j))) = k.

Proof By 3.2 we have k = lcm(k(h_{1}), k(h_{2})). Now we deploy 3.3 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 3.4 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.

Lemma 3.6 If i, j, m are distinct then lcm(k(r(i)), k(r(j))) | k(h_{m}).

Proof To see this, notice that r(i) − r(j) = (τ_{i} − τ_{j})(0, 1, 1 − τ_{m}….) and so has length k(h_{m}). Now τ_{i}^{k(h_{m})} − τ_{j}^{k(h_{m})} = 0 and τ_{i}^{k(h_{m})+1} − τ_{j}^{k(h_{m})+1} = τ_{i} − τ_{j}. Subtracting we obtain τ_{i}^{k(h_{m})} = 1. Thus k(r(i)) | k(h_{3}) whenever i and m are distinct as required.

Piecing together 3.3 and 3.6 we have established that k(h_{i}) = k for all i ∈ {1, 2, 3}. It remains to address loops of the form (0, 1, 1 − α, …) where α is not a root of X^{3} − X^{2} − X − 1. Consider the matrix

A = ( \begin{matrix}0 & 1 & 1 − α \\ 1 & 1 − α & 2 − α \\ 1 − α & 2 − α & 4 − 2α \end{matrix} ) .

More matrices are useful. We define them as

F = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix} ) ,

B = ( \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 2 \\ 1 & 2 & 4 \end{matrix} )

and finally

C = ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{matrix} ) .

Notice that A = B − αC = (F − αI)C so det(A) = det(F − αI)(−1)^{3} = det(αI − F) = α^{3} − α^{2} − α − 1. However, the choice of α forces det(a) ≠ 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 − α, …). Thus such a loop (0, 1, 1 − α, …) 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 3.1.

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 golden loops. The first few instances of this phenomenon we outline here.

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

14281                    595                    4760
                         680
                         952

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.

4 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 [5] 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).

Added after the conference:

Dr Dresel of Reading, England was kind enough to point out some references which we had missed. Specifically, his letter [7] and the paper of Heed [8]. 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 lnlnP. Thus, using Heed’s argument, Dresel should have found about 2.6 violators, and we should have found about 2.9. Notice that lnln10^{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.

References

[1] H. Aydin “Recurrence Relations in Finite Nilpotent Groups”, Ph.D. thesis, Bath (1991).

[2] 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.

[3] H. Aydin and G. C. Smith, “Finite p-Quotients of Some Cyclically Presented Groups” J. London Math. Soc. to appear.

[4] 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.

[5] 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.

[6] H. Doostie, “Fibonacci-type Sequences and Classes of Groups”, Ph.D. thesis, St Andrews (1988).

[7] L. A. G. Dresel “Letter to the Editor”, The Fibonacci Quarterly, 15 (1977), 346.

[8] J. J. Heed “Wieferichs and the Problem z(p^{2}) = z(p)”, The Fibonacci Quarterly 22 (1964), 116-118.

[9] E. Lucas “Théorie des fonctions numériques simplement périodiques”, Amer. J. Math., 1, (1878) 184-240 and 289-321

[10] R. G. E. Pinch “Linear Recurrent Sequences modulo prime powers”, to appear Proc. 3^{rd} IMA Conference on Coding and Cryptography, Cirencester, England. December 1991.

[11] P. Ribenboim “The Little Book of Big Primes”, Springer-Verlag (1991).

[12] J. A. Reeds and N. J. A. Sloane, “Shift Register synthesis (modulo m)”, SIAM J. Comput. 14 (1985) 505-513.

[13] L. Somer, “The Divisibility Properties of Primary Lucas Recurrences with Respect to Primes”, The Fibonacci Quarterly 18 No 4 (1980), 316-334.

[14] R. S. Sutor (ed.), “AXIOM user guide”, NAG Ltd, (1991)

[15] 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.

[16] 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.

[17] D. D. Wall, “Fibonacci Series Modulo m”, Amer. Math. Monthly 67 (1960), 525-532.

[18] H. J. Wilcox, “Fibonacci Sequences of Period n in Groups”, The Fibonacci Quarterly 24 (1986), 356-361.

Present address of the first author: Ataturk University Fen-Ed Faculty Department of Mathematics Erzurum, Turkey