Ever heard of the Fibonacci sequence?
This is a well-known sequence of numbers that turns up now and again in various domains of mathematics. It is related to subjects as diverse as the golden ratio, logarithmic spirals, huge prime numbers, sunflowers and rabbits. There is even a whole mathematical journal devoted to its properties (`The Fibonacci Quarterly'). No surprise that we also encounter it in these pages.
The sequence starts as follows:
0 1 1 2 3 5 8 13 21 34 55 89 ...
It can easily be generated: each number is the sum of the two numbers
immediately in front of it. (55=21+34, 89=55+34, ...)
We are interested in a modular version of this sequence, where we take some fixed modulus q (say 3) and take the remainder of each number in the Fibonacci sequence after division by q:
0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 ...
In other words, each element in the sequence is the sum of the two
previous ones, where the sum is now computed with modular
arithmetic.
In the `true' Fibonacci sequence, numbers always grow larger and larger. In our modular version, we have a pattern of small numbers (in the range 0..q-1) that repeats eventually. In the example above, the pattern reiterates every 8 entries. The number 8 is called the period of the repeating sequence.
(0,1) (1,1) (1,2) (2,0) (0,2) (2,2) (2,1) (1,0) (0,1) (1,1) ...(This sequence of coordinate pairs also has period 8.)
But now we may map the pairs of coordinates to actual names of
points (as on the previous page):
(0,1) (1,1) (1,2) (2,0) (0,2) (2,2) (2,1) (1,0) a e f d b h g cand this again suggests a way of numbering points:
a=0 e=1 f=2 d=3 b=4 h=5 g=6 c=7
The pictures on the right give you an idea of what this means for the semi-affine plane. We ended up with a numbering of the points which is such that the lines form the shifts of a CDS (in this case, the CDS {0,1,6} of size 3 and modulus 8). (Note that this is a different CDS to the one we had before. The semi-affine plane however is the same, but the numbering is different.)
[ At this point it is probably worth mentioning that the word `modulus' is used here in two different meanings. We are doing modular arithmetic with modulus 3, but the modulus of the resulting CDS is 8. If this confuses you, you are not alone, but you will still have to learn to live with it. ]
To my knowledge the only primes for which the Fibonacci series works are q=2 and q=3. (You might try q=2, but it results in a boring CDS.) I am not absolutely certain that there are no other primes for which this `Fibonacci method' works, but if so, they will be big.
Let us have a look at what happens when q is five. The Fibonacci sequence `modulo 5' reads
0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 ....or written as pairs of coordinates:
(0,1) (1,1) (1,2) (2,3) (3,0) (0,3) (3,3) (3,1) (1,4) (4,0)
(0,4) (4,4) (4,3) (3,2) (2,0) (0,2) (2,2) (2,4) (4,1) (1,0) ...
This gives us a cycle of period twenty. Unfortunately,
the semi-affine plane of order 5 contains as many
as 24 points, hence this cycle is a little too short.
In general, for a modulus q to work, the period of the Fibonacci cycle
must be q^2-1. Yesterday I spent a sleepless night trying to find another prime
number q for which the period is large enough. If you find one,
let me
know.
Of course I would not have gone to such great lengths to explain you the relation between the semi-affine plane of order 3 and the Fibonacci sequence if this were of no use for higher orders. On the next page we shall see that we can use other sequences instead.
Fibonacci's nephews
97/01/02 - Kris Coolsaet