In the course of writing about Fibonacci's famous sequence, I stumbled into an exploration of what factors show up in any given sequence conforming to the recurrence rule. I can summarise the basic conclusions with:
In this page I'll assume the latter case and use sequence
with
the tacit presumption that it follows Fibonacci's rule – each entry is the
sum of the two before it – and has coprime entries.
This inevitably leads to every third entry in the sequence being even, with a pair of odd entries in the gaps between them. That equally inevitably lead me to wonder about other factors. Naturally, the place to start that enquiry is with the odd primes. I began by going through simply finding out by experiment what sequences to arise modulo each given prime; once I spotted some patterns, I realised there was some analysis that could clarify the situation; then I ran into 13 doing something beyond what I first thought of. Later it crossed my mind that this exploration is worth describing in the order in which I conducted it, rather than tidying it up and making it seem like I noticed the clever bits right away, so I've done my best to reconstruct the actual sequence of exploration up to modulo 13, so that I can then continue this as an exploration. Perhaps that will give some insight into how a mathematician discovers truth, rather than giving an elegant summary of the final conclusions.
Since two successive terms in a sequence determine the whole – subtract the first from the second to get the previous; and the sum of the two we have is the next; inductively extend those process indefinitely in both directions – and, modulo any given prime, the number of distinct values is that prime, so there are only finitely many pairs of values that can be found adjacent to one another. The order of the pair matters, but we're working with coprime sequences so no two adjacent entries share any common factor, notably including our prime, so we rule out the pair 0, 0 and, for prime p, are left with p.p −1 = (p −1).(p +1) possible pairs.
So every pair implies a sequence; each consecutive pair that appears in that sequence implies the same sequence, just shifted along a bit. As there are finitely many pairs available, the sequence modulo any given prime must eventually repeat itself. Since we can wind backwards from the repeated pair to discover the earlier sequence, the two repeat instances of the pair must actually have the same sequences of values before them so, in fact, the pair we start with will necessarily be the first to be repeated; and the sequence will be cyclic modulo every prime. In particular, any sequence with a multiple of a prime in it will have further multiples of that prime at regular intervals. All this leads to the available sequences, modulo any given prime, partitioning the set of allowes pairs; the sums of the orders of the sequences, modulo p, must be (p −1).(p +1).
The arithmetic modulo each prime forms a field – we can add, subtract, multiply and divide, always getting whole values modulo the prime. (For example, modulo 3, 2×2 = 4 = 1 so 1/2 is 2; division by 2 is just multiplication by 2.) As Fibonacci's rule is a linear constraint, scaling any sequence that abides by it gives another; so each solution we find automatically implies solutions obtained from it by scaling by each non-zero value modulo our prime. Some of those, of course, will just be the same sequence shunted round its cycle a few steps; others, however, may be distinct sequences.
Since we're partitionining the available pairs, it suffices to start with the sequence generated by 0, 1 (the same as Fibonacci's initial condition), keep going until it cycles, see what pairs haven't yet showed up, explore where one of those leads and so on, until we've found sequences exhibiting all available pairs.
All this was self-evident to me at the outset so I just dived in and began exploring the sequences modulo various small primes without writing it all down; but, now that I'm reconstructing what I did it's worth recording, just so that the reader understands how I approached that.
One more side-effect of the arithmetic modulo a prime being a field is that every non-zero value is a multiple of every other non-zero value, so there are no primes modulo a prime – every non-zero is a unit – so all our allowed pairs are coprime, modulo the prime, automatically. So don't be mislead by a pair like 2, 4 showing up in a sequence modulo a prime, below; the sequence can still be coprime with those consecutive entries modulo the prime, as long as they're not the real entries in the natural sequence we've reduced modulo the prime. All we can tell, when looking at it modulo a prime, about whether that underlying sequence is coprime is whether it's all-zero (so every entry is a multiple of the given prime) or not.
The sequence 0, 1, 1, 2, 0, 2, 2, 1, 0 satisfies the recurrence rule and exhibits every allowed pair of successive entries. As a result, every sequence of interest is, modulo three, an endless repeat of this 8-cycle, with every fourth entry a multiple of three.
We get 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, a cycle with period 20, that gives a multiple of five every fifth entry. That only covers 20 of our 24 pairs; starting with one of the missing pairs leads to 1, 3, 4, 2, 1, a four-cycle that uses all of the other four pairs.
That four-cycle implies a permutation of its four entries, mapping each to the entry that follows it, and applying that permutation (while preserving zero) to the 20-cycle advances it 5 steps. (Which was a clue I missed at the time.)
Brute force lead to the sequences
each a 16-cycle, that can be obtained from each other by scaling. Between them they exibit all 48 allowed pairs of successive entries. These are just the results of scaling one another and each has a multiple of 7 every eight entries; the second half of each cycle is just the negation of the first. So every sequence following the rule has multiples of 7 in it.
The sequences starting with a 0 are:
each of which is a ten-cycle; and there are ten of them, obtained by scaling one another. They account for 100 of the 120 available pairs. Further search reveals one more ten-cycle and a pair of 5-cycles:
The first of these is a permutation of the non-zero values and, interestingly, can be read as an interleaving of the reverses of the other two.
It was at this point that it crossed my mind to try to solve for the golden ratio – or, rather, its equivalent in our prime fields. This arises in the analytic solution of Fibonacci's sequence as a solution to g.g = g +1; successive powers of any g satisfying this condition will form a sequence consistent with the recurrence relation. Since we're working in a prime field, however, we don't solve it by obtaining the usual golden ratio, (1 +√5)/2. We can rearrange the equation as g.(g −1) = 1, implying that g would be the second of an adjacent pair of non-zero values whose product is 1. That's easy enough to check for.
So the times that we have a solution for g neatly fit with the cases where I've seen zero-free cycles, at least thus far. Let's press on, then, to see what we get…
Given the lack of solutions I was expecting to only get cycles with zero in them. We have 12×14 allowed pairs, so let's see what sequences we get when we keep trying ones we haven't seen yet until they run out:
Six 28-cycles; indeed 12×14 = 6×28. The first three of them have zeros in them, each in four sub-cycles of length seven; but the big surprise (for me) was the three without zeros. So we get something interesting that we haven't seen before: solutions that aren't power series and don't visit 0.
I slept on it, during which it occurred to me to recast all of this as a record of exploration, rather than attempting to make it look like I somehow know all this stuff before I started. So say goodby to the past tense, I'll be writing as I go in the present from now on. I also had a few more ideas, both while I slept and in the day's work since.
First notice that, modulo 5, we only got one solution to our equation, g.g = g + 1. That's a quadratic equation, so we normally expect two solutions, although repeated roots are a thing. So let's look at that possibility: our root was 3, so if it's a repeated root we need to look at (x −3).(x −3) = x.x −6.x +9 which, modulo 5, is indeed equal to x.x −x −1, which is zero exactly for the solutions of our equation. So, fair enough, the single solution arises for a valid reason.
Now let's go back to modulo 3, where we had no solutions for integer g; but,
again, we expect a quadratic equation to have two solutions, so where are
they ? The usual answer to that is in the complex plane
, as a
conjugate pair given that our equation only has real coefficients. So take the
complex g = x +y.j, with j a square root of −1 and x, y integers modulo 3.
We'll be getting the same modulo each prime, in due course, so let's first see
what equation we'll be solving, before simplifying it modulo 3. We want the
cases where
and, as 1 has no imaginary part, this needs (2.x −1).y = 0; as our prime fields have no zero-divisors this means one of the factors must be zero. So the question boils down to the pair of equations, for x and y,
The form of these ensures that, when y isn't 0, we get a conjugate pair, as −y and y have the same square; which halves the number of candidates for y that we need to check.
Modulo 3, we've already seen there are no solutions with y = 0, so we have 2.x = 1, thus x = 2. That turns the second equation into 1 +y.y = 2×1 = 2, so y.y = 1, implying y = ±1. So 2 ±j work as g and generate power series solutions. Although those do have imaginary parts, we can construct any linear combination of them to get a solution, as long as the combination has zero imaginary part; and that's easy enough to arrange. So let's look at the powers of 2 +j, modulo 3 (and those of 2 −j can be obtained from it simply by negating the coefficient of j):
after which we inevitably loop, implying an 8-cycle, which is exactly what we got (and exactly what it takes to account for all 3×3 −1 allowed pairs to show up). Adding this to its conjugate (the equivalent for 1 −j, which is the cube of 1 +j), we get:
which is exactly the 8-cycle we have above. So – joy! – we do see all our solutions as sums of power series. We could try adding the cycle of powers of 2 +j to a shifted version of itself; that's equivalent to scaling by the entry we put first; but the only scalings available modulo 3 are 1 and −1; adding the cycle to its own negation gets the all-zero solution we're busy avoiding, and adding it to itself is the same as negating it or cycling it forward four steps, so still gets the same cycle. Note, in passing, that (g −(2 +j)).(g −(2 −j)) = (g +1 −j).(g +1 +j) = g.g +2 +2.g = g −g −1, so our conjugate pair of roots does give us a factorisation of the polynomial whose zeros are solutions to our equation.
Let's do that again modulo 7; we already know y = 0 gives no solution, so must have 2.x = 1, i.e. x = 4. So y.y = x.(x −1) −1 = 11 = 4 modulo 7; solved by y = ±2, a conjugate pair, just as we would expect. The powers of 4 +2.j modulo 7 are then
a 16-cycle, just like our solutions. Adding this to its conjugate, we get
which is, indeed, one of the solutions seen above, albeit cycled around a bit; and I already noted that the solutions are scalings of one another, so that accounts for all three.
Since I'm now getting my computer to help, I think I should give you a peek behind the scenes to see how I worked all that out – in a python session:
>>> [(4 +2j) ** i % 7 % 7j for i in range(17)] [(1+0j), (4+2j), (5+2j), (2+4j), 6j, (2+3j), (2+2j), (4+5j), (6+0j), (3+5j), (2+5j), (5+3j), 1j, (5+4j), (5+5j), (3+2j), (1+0j)] >>> [int((x + x.conjugate()).real) % 7 for x in _] [2, 1, 3, 4, 0, 4, 4, 1, 5, 6, 4, 3, 0, 3, 3, 6, 2]
because, at this point, it's only fair to note that my mental arithmetic isn't so reliable when it gets this messy. While I'm here, I should jot down – before I catch some sleep, after which I probably won't get back to this for a day or two – a stray concern: I'm not actually certain that factorisations stay unique, once we get into complexified prime rings; I suspect they do, but I'd better check.
Thus far, I've only seen the two solutions I expect, but it's worth watching out for surprises. Let's start by looking at modulo 5; as ever, that needs either y = 0 (the case we already checked) or 2.x = 1 modulo 5, implying x = 3; and y.y = x.(x −1) −1 = 0, which is indeed the solution we already have. So, at least up to 7, arithmetic modulo a prime doesn't give any surprise extra solutions to the equation.
For the lack of surprises to continue, we need the conjugate pair of roots to give us a factorisation of g.g −g −1, the polynomial that's zero at the solutions to our equation, as a product of factors, each of which subtracts one root from g. That would be
and, with y non-zero (to get a conjugate pair), we have 2.x = 1, reducing this to g.g −g −1 as required. That doesn't rule out the possibility of a surprise later, if we have distinct values for y with the same square other than by virtue of being each others negtion.
OK, so can that happen modulo 7 ? Let's just check for any other values whose squares are 4, though: the squares modulo 7 are 1, 4, 9 = 2, 16 = 2, 25 = 5 and 36 = 1, so we're safe there, at least.
In fact, thinking about it, consider any n, m satisfying n.n = m.m modulo p; let r = n/m modulo p and infer r.r = 1. In natural arithmetic, that means r.r = k.p +1 for some natural k, or k.p = r.r −1 = (r −1).(r +1) and, as p is prime, this implies one of r −1 and r +1 must be a multiple of p, hence r = ±1 modulo p. So, in fact, we can't have more than two solutions for y; we either get y = 0 or a conjugate pair x ±y for a single y. That might still leave scope for more than two solutions to x.x = x +1 modulo some p when y = 0, though.
Pause to consider when the cases q = 0 and 2.x = 1 can coincide, for the solution modulo som odd prime p. The x modulo p for which 2.x = 1 is, in the natural arithmetic, (p +1)/2; so 2.x −1 = p. Then 4.x.(x −1) +1 = 4.(x.x −x) +1 = (2.x −1).(2.x −1) = 0, so x.(x −1) = 1 precisely if 5 = 0 modulo p; so modulo 5 is in fact the only case where these two cases coincide.
Modulo 5 the squares are 1, 4, 4, 1, again only with the two repeats we expect of each value; and, interestingly, 2 and 3 both square to −1, which might be relevant to why we got no imaginary part to our root. Modulo which primes is there a square root of −1 ?
>>> [p for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ... 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) ... if any((i**2 +1) % p == 0 for i in range(p))] [2, 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97] >>> [x % 4 for x in _] [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
python tells me. Aside from two, where −1 is 1 and its own square, these are the primes that are one more than multiples of four. What are those square roots of −1 ?
>>> [(p, next(i for i in range(p // 2 +1) if (i**2 +1) % p == 0)) ... for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, ... 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) ... if p % 4 == 1] [(5, 2), (13, 5), (17, 4), (29, 12), (37, 6), (41, 9), (53, 23), (61, 11), (73, 27), (89, 34), (97, 22)]
Written by Eddy.