by Jonathan Kujawa
Dr. Krieger works in the area of dynamic systems. Faithful 3QD readers will remember that we ran into this topic a few months ago when we talked about the Collatz conjecture and the mathematics of billiards (see here). Dynamical systems is the field which studies systems (the weather, the stock market, the hands on a clock, a ball ricocheting around a billiard table) which changes over time according to some rule.
A seemingly simple example of this is the Fibonacci sequence. You probably saw it as kid:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269,….
This is the sequence of numbers which starts with a 0 and 1, and then each subsequent number is the sum of the previous two: 0+1=1, 1+1=2, 1+2=3, 2+3=5, etc. To a mathematician this is a dynamical system. We can think of the nth number in the sequence as the state of the system after n seconds and the addition rule tells us how the system changes from one second to the next.
Last time we talked about dynamical systems we were interested in the question of whether such a system ever returns to its starting state. A properly working clock always ends up back where it was twenty-four hours ago. At the other extreme, the stock market will never end up back in the exact same state. Somewhere in the middle we have the billiard ball. It may or may not return, depending on the shape of the table and where you start the ball.
From this point of view the Fibonacci sequence is boring as all get out. It just gets bigger and bigger forever. But Dr. Krieger is the sort who isn't satisfied with such an answer. She asks questions like: You get a new number every time, but is it really “new” or “mostly old” [1]?
What do I mean? Well, we first need to recall the prime numbers. These are numbers like 2, 3, 5, and 7 which can't be evenly divided by another number (except 1 and itself, of course). On the other hand, 4, 6, 8, and 9 are not prime as they can be divided by 2's and 3's. That is, a non-prime can be written as a product of other numbers (like 24=4×6). If you keep subdividing you can eventually write any number as product of primes (like 24=2x2x2x3).
You should think of the prime numbers as the atoms of numbers: every number can be broken down into primes and you can't go any further. To stretch the analogy a little further, most folks are more excited when you discover a new atomic element than if you “just” discover a new combination of old elements. In the same spirit, you might think to ask if the Fibonacci sequence is made up of a few primes used over and over (like using 2 and 3 to make 6, 9, 12, 18, and 864), or if new primes are used as you go along.
If you are the sort of person to wonder such things, then you might also be the sort who is willing to sit down and factor Fibonacci numbers to see which primes occur. If you're old school or if you lived in 1913, then you factor numbers by hand. Fortunately we live in the internet era and Ron Knot has provided us with the first 300 Fibonacci numbers already factored completely. He's even marked out the new primes in green. New in the sense that they have never occurred as a factor in an earlier Fibonacci number. For example, In Dr. Knot's list we see that if we factor the 45th Fibonacci number we get:
1134903170 = 2 x 5 x 17 x 61 x 109441
In this case 109441 is a new prime number which we never saw in the first 44 Fibonacci numbers.
In fact, when we look at Dr. Knot's list we see that barring a few exceptions right at the beginning, every single Fibonacci number has at least one new prime number! Of course there are billions and billions of Fibonacci numbers and Dr. Knot's list is a drop in the bucket. Amazingly, back in 1913 Carmichael proved that, barring those first few exceptions, every single one of the infinitely many Fibonacci numbers has a new prime as a factor [2]!
It's a truly remarkable result. I can only imagine that Carmichael felt a bit like Robert Hooke when he first peered through a microscope: entire worlds previously unimagined just below the surface of the ordinary and everyday. Until Dr. Krieger's talk, I couldn't have imagined the Fibonacci numbers could hide such surprises.
Dr. Krieger herself worked on a different sequence:
0, 2, 6, 38, 1446, 2090918, 4371938082726, 19113842599189892819591078,…
In this case the rule for each number is to take the previous number, multiply it with itself and add two (so 2×2+2=6, 6×6+2=38, 38×38+2=2090918, etc.). That is, in a formula, the rule to go from one number to the next is:
Dr. Krieger then asked the same question as Carmichael: is it true that every number in this sequence has a new prime factor? Ignoring a few rogue exceptions at the beginning if needed, of course.
Dr. Krieger proved that the answer is yes! In fact she did much, much more than this. She proved it was true for any sequence which starts with zero as long as the rule to go from one number to the next looks like:
Here you can pick d to be any natural number greater than one (it could be 2, 3, 4, 5, 6, etc.) and c can be any integer except 0, -1, and -2.
Why are 0, -1, and -2 forbidden? Because if you use one of those, then the sequence of numbers you get may simply repeat itself over and over. You don't have a hope of getting new primes in this case. Try it when d is 2 and you'll see what I mean. Dr. Krieger shows this is the only thing which can go wrong.
In fact, Dr. Krieger did even more! She showed that you have, at worst, twenty-three exceptional numbers made only of old primes. In fact, almost always you only have one or two exceptions. She even showed that you are allowed to let c be a fractional number if you are willing to talk about the prime factors of the top and bottom of fractions.
If you watch the Numberphile video you'll see that the Mandelbrot set appears [3]. The Mandelbrot set is intimately related with these sequences. My favorite image of the Mandelbrot set is the very first one:
The Mandelbrot set is made by studying the same sequences we've been talking about. Namely, the ones whose rule looks like:
We now let c be any complex number. Despite their name, complex numbers aren't so complex. If we write i for the square root of -1, then every complex number looks like x+yi. So every complex number can be plotted as the point (x,y) on the usual xy-plane. And vice versa. So we should just think of the complex numbers as points we can draw the plane. For example, 0 can be written as 0+0i. Our old friend zero just gives us the point (0,0) at the very center of the plane.
If we let c be our favorite complex number, we get a rule for a sequence. Starting with 0, we can apply the rule and obtain our sequence of numbers. The sequence will be complex numbers and so gives us points in the plane. If those points race off towards the edge of the plane, then c is not in the Mandelbrot set. On the other hand, if the points of our sequence meander around but never stray too far from (0,0), then c is in the Mandelbrot set [4].
Now if on a separate sheet of paper we mark every point in the plane corresponding to a c which is in the Mandelbrot set, then we get the picture above. To get the fancy multicolored version, we color each point not in the Mandelbrot set according to how fast it races away. If it just strolls, you mark it red, if it jogs, mark it green, if it sprints mark it blue, and so on. The famous fractally edges you see in pictures of the Mandelbrot set are a visual way of showing that very close c's can race away at very different speeds.
Dr. Krieger is considering this rule when c is a fraction. Writing them as a complex number they all look like x+0i. This means that when we mark them on the plane they all lie on the horizontal line which goes through the center. Here's a picture of the Mandelbrot set with the xy-axes marked out:
What does the Mandelbrot set tell us about Dr. Krieger's work? Remember, Dr. Krieger told us these sequences have at most twenty-three exceptional numbers made of only old primes. And in fact they will usually only have a couple of exceptional numbers. In the Numberphile video Dr. Krieger remarked that your c should be very far inside in the Mandelbrot set to have a large number of exceptions. Why should that be so?
Here is one way to think about it: Numbers on the outside of the Mandelbrot set race off and so are getting very large very quickly. Large numbers usually have lots of prime factors and it's not likely they will only have old primes and hence be exceptional. It seems reasonable then to expect that if your c is going to have a large number of exceptional numbers, then it shouldn't even be near the edges of the Mandelbrot set.
But of course the whole point of the fractally nature of the Mandelbrot set is that nearby neighbors can act in quite different ways. The heuristic argument of the previous paragraph is not quite right. We need to understand what “far inside” should mean for the Mandelbrot set. Until we know that we won't know if the -7/4 from the video is really special, or not.
[1] A more clever person than I would be able to work in a Miracle Max reference at this point.
[2] Which, if you think about it, also means that there are infinitely many prime numbers. Even if you already knew that, it's neat to know that fact is hidden away in the Fibonacci sequence.
[3] A joke for fractal fans: What does the B. stand for in Benoit B. Mandelbrot? Benoit B. Mandelbrot!
[4] More precisely, if all the points given by the sequence stay within some circle centered on (0,0), then c is in the Mandelbrot set. If no such circle exists, then c is not in the Mandelbrot set. For example, using this rule we see that 2 is not in the set, but -2 is in the set.