Fourier Analysis in Finite Nilpotent

Groups

Huseyin Aydin ^{∗}

Geoff C. Smith

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

1 Introduction

Let s denote the ordinary Fibonacci sequence taken modulo a natural number m. This is a bi-infinite periodic sequence (or 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 Wall’s Number[15]. 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, ∑_{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

∑_{r=0}^{k−1} ∑_{j=0}^{r−1} ∑_{i=0}^{j−1} s_{r}^{2}s_{j}s_{i}^{2}s_{r−j−1}s_{j−i−1}(−1)^{r+1} + ∑_{j=0}^{k−1} ∑_{i=0}^{j−1} s_{j}(_{2}^{s_{j}})s_{j−i−1}s_{i}^{2}(−1)^{j+1}

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

+ ∑_{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 [1] or [2]. The group theoretic implications of these calculations are summarized in [3]. 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 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 [10], [14] and [15] 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 [11] 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 CAY-LEY [4] 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 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 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 [9], and Zelmanov [17] has recently finished the proof. For background material in this area, the reader may wish to consult [13]. The proof relies upon an argument of P. Hall and G. Higman [6] 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 [12], and the papers of Johnson and his co-workers [5, 7, 8]. 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.

Theorem 1.1 The following equations all hold. They are

(A)  ∑ s_{i} = 0,

(B)  ∑ s_{i}^{2} = 0,

(C)  ∑ s_{i}^{3} = 0,

and, providing p ≠ 3,

(D)  ∑ s_{i}^{4}(−1)^{i} = 0.

If p ≠ 11 then

(E)  ∑ s_{i}^{5} = 0.

Theorem 1.2 The following equations also hold. They are

(A′)  ∑ s_{i}(−1)^{i} = 0,
(C′)  ∑ s_{i}^{3}(−1)^{i} = 0,

and if p ≠ 11 then

(E′)  ∑ s_{i}^{5}(−1)^{i} = 0.

2 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

∑ s_{i}^{19} = ∑ s_{i−42}^{19} = ∑ s_{k−i}^{19}.

This proves to be a fruitful observation.

We announce that

∑ s_{i}^{6} = 0.

Moreover, it is also true that

∑ s_{i}^{7} = 0

and

∑(−1)^{i}s_{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 [1].

The sums which are mysteriously absent from 1.1 and 1.2 are not missing through oversight. The following results may be found in [1]. For obvious reasons, the prime 5 is excluded.

∑(−1)^{i}s_{i}^{2} = −\frac{2}{5}k

∑ s_{i}^{4} = \frac{6}{25}k

∑(−1)^{i}s_{i}^{6} = −\frac{4}{25}k

∑ s_{i}^{8} = \frac{14}{125}k.

We conjecture that, if n = 4l + 2, then ∑(−1)^{i}s_{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 ∑ 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.

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

4 Proofs

We make the blanket assumption that p ≠ 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.

Proof of (A).

∑ s_{i} = ∑(s_{i−1} + s_{i−2}) = 2 ∑ s_{i}

so ∑ s_{i} = 0.

Proof of (B).

∑ s_{i}^{2} = ∑(s_{i−1} + s_{i−2})^{2}

so

(1)  ∑ s_{i}^{2} = 2 ∑ s_{i}^{2} + 2 ∑ s_{i}s_{i−1}.

Similarly, we express s_{i−2} as s_{i} − s_{i−1} to obtain

(2)  ∑ s_{i}^{2} = ∑ s_{i−2}^{2} = 2 ∑ s_{i}^{2} − 2 ∑ s_{i}s_{i−1}.

Adding (1) and (2) we obtain

2 ∑ s_{i}^{2} = 4 ∑ s_{i}^{2}

from which the equation (B) follows.

Proof of (C).

∑ s_{i}^{3} = ∑ s_{i+1}^{3} = ∑(s_{i} + s_{i−1})^{3}

so

(3)  ∑ s_{i}^{3} = 2 ∑ s_{i}^{3} + 3 ∑ s_{i}^{2}s_{i−1} + 3 ∑ s_{i}s_{i−1}^{2}.

Similarly we may write

∑ s_{i}^{3} = ∑ s_{i−2}^{3} = ∑(s_{i} − s_{i−1})^{3}

and so

(4)  ∑ s_{i}^{3} = −3 ∑ s_{i}^{2}s_{i−1} + 3 ∑ s_{i}s_{i−1}^{2}.

Add (3) and (4) to obtain

2 ∑ s_{i}^{3} = 2 ∑ s_{i}^{3} + 6 ∑ s_{i}s_{i−1}^{2}

from which it follows that

(5)  3 ∑ s_{i}s_{i−1}^{2} = 0.

Now we adjust (5) using s_{i} = s_{i−1} + s_{i−2} to obtain

(6)  3 ∑ s_{i}^{3} + 3 ∑ s_{i}^{2}s_{i−1} = 0.

From (3) and (5) we know

(7)  ∑ s_{i}^{3} + 3 ∑ s_{i}^{2}s_{i−1} = 0.

Subtract (7) from (6) to obtain the result. Wall’s number k is even [15], and of course the Cassini identity holds modulo p,

(8)  s_{i}^{2} = s_{i−1}s_{i+1} + (−1)^{i+1} for all integers i.

Moreover we have

(9)  s_{k−i} = s_{−i} = s_{i}(−1)^{i+1} for all integers i

Proof of (A′) and (C′). Apply (9) to (A) and (C). Notice that one may always deduce ∑ s_{i}^{2t+1}(−1)^{i} = 0 from ∑ s_{i}^{2t+1} = 0. Proof of (D).

(10)  ∑ s_{i}^{4}(−1)^{i} = 0.

We introduce some temporary shorthand to clarify the proof. Let

α = ∑ s_{i}^{4}(−1)^{i},
β = ∑ s_{i+1}^{3}s_{i−1}(−1)^{i},
γ = ∑ s_{i+1}s_{i−1}^{3}(−1)^{i},
δ = ∑ s_{i+1}^{2}s_{i−1}^{2}(−1)^{i},
ϵ = ∑ s_{i}^{3}s_{i−1}(−1)^{i},
ζ = ∑ s_{i}s_{i−1}^{3}(−1)^{i}

and finally

η = ∑ s_{i}^{2}s_{i−1}^{2}(−1)^{i}.

Our ambition is to demonstrate that α = 0. First we show that β = γ.

β = ∑ s_{i+1}^{3}s_{i−1}(−1)^{i} = ∑ s_{k−i−1}^{3}s_{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

β = ∑_{i=1}^{k} s_{i−1}^{3}s_{i+1}(−1)^{i} = ∑_{i=1}^{k−1} s_{i−1}^{3}s_{i+1}(−1)^{i} = γ,

the final equality being obtained by translation of the range. Our next ambition is to show that α = δ. We deploy (8) to good effect.

δ = ∑(s_{i+1}s_{i−1})^{2}(−1)^{i} = ∑(s_{i}^{2} + (−1)^{i})^{2}(−1)^{i} so

δ = ∑ s_{i}^{4}(−1)^{i} + 2 ∑ s_{i}^{2} + ∑(−1)^{i}.

Now ∑ s_{i}^{2} = 0 by (B) and ∑(−1)^{i} = 0 since k is even, so α = δ.

Our next target is to show that ϵ = ζ. We have

ϵ = ∑ s_{i}^{3}s_{i−1}(−1)^{i} = ∑ s_{k−i}^{3}s_{k−i+1}(−1)^{k−i+1}.

Note that i and i − 1 have opposite parity. We reverse the range of summation to obtain

ϵ = ∑_{i=1}^{k} s_{i}^{3}s_{i+1}(−1)^{i+1} = ∑ s_{i}s_{i−1}^{3}(−1)^{i} = ζ.

Now for something a little different; we show that α + β = ϵ (= ζ). Notice that

α + β = ∑ s_{i}^{4}(−1)^{i} + ∑ s_{i}^{3}s_{i−2}(−1)^{i+1}
= ∑ s_{i}^{3}(−1)^{i}(s_{i} − s_{i−2}) = ∑ s_{i}^{3}s_{i−1}(−1)^{i} = ϵ.

As a final preliminary, we show that η = 0. We have

η = ∑ s_{i}^{2}s_{i−1}^{2}(−1)^{i} = ∑ s_{k−i}^{2}s_{k−i+1}^{2}(−1)^{k−i}.

Once again we have used (9), and have prepared to reverse the range of summation. Thus

η = ∑_{i=1}^{k} s_{i}^{2}s_{i+1}^{2}(−1)^{i} = ∑ s_{i}^{2}s_{i+1}^{2}(−1)^{i}.

Now translate the range of summation to yield

η = ∑ s_{i−1}^{2}s_{i}^{2}(−1)^{i+1} = −η.

Let us summarize the results of our labour:

β = γ, δ = α, ϵ = ζ, α + β = ϵ, η = 0.

We now embark on calculations to obtain linear relations between α and β, using the binomial theorem as our vehicle.

α = ∑(s_{i+1} − s_{i−1})^{4}(−1)^{i} = −α − 4β + 6δ − 4γ − α

so

α = −2α − 8β + 6α

and therefore

(11).  3α − 8β = 0

Now we express α in a different way.

α = ∑ s_{i+1}^{4}(−1)^{i+1} = ∑(s_{i} + s_{i−1})^{4}(−1)^{i+1},

so

α = −α − 4ϵ − 6η − 4ζ + α.

This simplifies to

α = −4(α + β) − 0 − 4(α + β)

and so

(12)  9α + 8β = 0.

Adding (11) and (12) we obtain 12α = 0 from which the result follows unless p = 3. When p = 3 the result is true by inspection.

Corollary 4.1

β = ∑ s_{i+1}^{3}s_{i−1}(−1)^{i} = 0
γ = ∑ s_{i+1}s_{i−1}^{3}(−1)^{i} = 0
δ = ∑ s_{i+1}^{2}s_{i−1}^{2}(−1)^{i} = 0
ϵ = ∑ s_{i}^{3}s_{i−1}(−1)^{i} = 0
ζ = ∑ s_{i}s_{i−1}^{3}(−1)^{i} = 0
η = ∑ s_{i}^{2}s_{i−1}^{2}(−1)^{i} = 0

Proof of (E) and (E′). Let θ = ∑ s_{i}^{5} then

θ = ∑(s_{i+1} − s_{i−1})^{5}

so

θ = −5 ∑ s_{i+1}^{4}s_{i−1} + 10 ∑ s_{i+1}^{3}s_{i−1}^{2} − 10 ∑ s_{i+1}^{2}s_{i−1}^{3} + 5 ∑ s_{i+1}s_{i−1}^{4}

and therefore

θ = −5 ∑ s_{i+1}s_{i−1}(s_{i+1}^{3} − s_{i−1}^{3}) + 10 ∑ s_{i+1}^{2}s_{i−1}^{2}(s_{i+1} − s_{i−1}).

We now deploy equation (8) to obtain

θ = −5 ∑(s_{i}^{2} + (−1)^{i})(s_{i+1}^{3} − s_{i−1}^{3}) + 10 ∑(s_{i}^{2} + (−1)^{i})^{2}s_{i}.

This expression admits of considerable simplification. In fact one can simply suppress the occurrences of (−1)^{i} because the following equations hold:

∑ s_{i+1}^{3}(−1)^{i+1} = 0 from (C′)
∑ s_{i−1}^{3}(−1)^{i+1} = 0 from (C′)
∑ s_{i}^{3}(−1)^{i+1} = 0 also from (C′)

and

∑ s_{i} = 0 from (A).

Thus

θ = −5 ∑ s_{i}^{2}(s_{i+1}^{3} − s_{i−1}^{3}) + 10θ,

and so

−9θ = −5 ∑ s_{i}^{2}(s_{i+1}^{3} − (s_{i+1} − s_{i})^{3}).

Expanding we obtain

−9θ = −5 ∑ s_{i}^{2}(3s_{i+1}^{2}s_{i} − 3s_{i+1}s_{i}^{2} + s_{i}^{3}).

Thus we have

−9θ = −5 ∑ s_{i}^{2}(3s_{i+1}s_{i}(s_{i+1} − s_{i}) + s_{i}^{3})

and therefore

−9θ = −5 ∑ s_{i}^{2}(3s_{i+1}s_{i}s_{i−1} + s_{i}^{3}).

We now close on our quarry using (8) again. We have

−9θ = −5 ∑ 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θ = −5 ∑ 4s_{i}^{5} = −20θ.

We conclude that 11θ = 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 ∑ s_{i}^{5} = 1 and ∑ s_{i}^{5}(−1)^{i} = −1.

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

[5] C.P. Chalk and D.L. Johnson. “The Fibonacci Groups II”, Proc. Royal Soc. Edinburgh 77A, (1977), 79-86.

[6] P. Hall and G. Higman. “On the p−length of p−soluble Groups and Reduction Theorems for Burnside’s Problem”, Proc. London Math. Soc., 6 (1956), 1-42.

[7] D.L. Johnson. “A Note on the Fibonacci Groups”, Israel J. Math. 17 (1974), 277-282.

[8] D.L. Johnson, J.W. Wamsley and D. Wright. “The Fibonacci Groups”, Proc. Lond. Math. Soc. (3) 29, (1974), 577-592.

[9] A.I. Kostrikin. “The Burnside Problem”, Izv. Akad. Nauk SSSR, Ser. Mat. 23 (1959), 3-34.

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

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

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

[13] M. Vaughan-Lee. The Restricted Burnside Problem, Oxford University Press (1990).

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

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

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

[17] E. I. Zelmanov. “ Solution of the Restricted Burnside Problem for groups of odd exponent”, Izv. Akad. Nauk SSSR Ser. Mat. 54 (1990), 42-59, 221 (Russian). English translation (J. Wiegold) Math. USSR-Izv. 36 (1991) no. 1, 41-60. The even exponent case will appear in Mat. Sbornik.

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