I feel like talking about some pure math, just for fun on a Sunday afternooon.
Back in 2006, Dan Christensen did something rather simple and got a surprisingly complex and interesting result. He took a whole bunch of polynomials with integer coefficients and drew their roots as points on the complex plane. The patterns were astounding!
Then Sam Derbyshire joined in the game. After experimenting a bit, he decided that his favorite were polynomials whose coefficients were all 1 or -1. So, he computed all the roots of all the polynomials of this sort having degree 24. That’s 224 polynomials, and about 24 × 224 roots—or about 400 million roots! It took Mathematica four days to generate the coordinates of all these roots, producing about 5 gigabytes of data.
He then plotted all the roots using some Java programs, and created this amazing image:
You really need to click on it and see a bigger version, to understand how nice it is. But Sam also zoomed in on specific locations, shown here:
Here’s a closeup of the hole at 1:
Note the line along the real axis! It’s oddly hard to see on my computer screen right now, but it’s there and it’s important. It exists because lots more of these polynomials have real roots than nearly real roots.
Next, here’s the hole at :
And here’s the hole at :
Note how the density of roots increases as we get closer to
this point, but then suddenly drops off right next to it. Note also the subtle patterns in the density of roots.
But the feathery structures as we move inside the unit circle are even more beautiful! Here is what they look near the real axis — this plot is centered at the point :
They have a very different character near the point :
But I think my favorite is the region near the point This image is almost a metaphor of how mathematical patterns emerge from confusion… like sharply defined figures looming from the mist as you drive by with your headlights on at night:
Now, you may remember that I said all this already in “week285″ of This Week’s Finds. So why am I talking about it again?
Well, the patterns I’ve just showed you are tantalizing, and at first quite mysterious… but ‘some guy on the street’ and Greg Egan figured out how to understand some of them during the discussion of “week285″. The resulting story is quite beautiful! But this discussion was a bit hard to follow, since it involved smart people figuring out things as they went along. So, I doubt many people understood it—at least compared to the number of people who could understand it.
Let me just explain one pattern here. Why does this region near :
look so much like the fractal called a dragon?
You can create a dragon in various ways. In the animated image above, we’re starting with a single horizontal straight line segment (which is not shown for some idiotic reason) and repeatedly doing the same thing. Namely, at each step we’re replacing every segment by two shorter segments at right angles to each other:
At each step, we have a continuous curve. The dragon that appears in the limit of infinitely many steps is also a continuous curve. But it’s a space-filling curve: it has nonzero area!
Here’s another, more relevant way to create a dragon. Take these two functions from the complex plane to itself:
Pick a point in the plane and keep hitting it with either of these functions: you can randomly make up your mind which to use each time. No matter what choices you make, you’ll get a sequence of points that converges… and it converges to a point in the dragon! We can get all points in the dragon this way.
But where did these two functions come from? What’s so special about them?
To get the specific dragon I just showed you, we need these specific functions. They have the effect of taking the horizontal line segment from the point 0 to the point 1, and mapping it to the two segments that form the simple picture shown at the far left here:
As we repeatedly apply them, we get more and more segments, which form the ever more fancy curves in this sequence.
But if all we want is some sort of interesting set of points in the plane, we don’t need to use these specific functions. The most important thing is that our functions be contractions, meaning they reduce distances between points. Suppose we have two contractions and from the plane to itself. Then there is a unique closed and bounded set in the plane with
Moreover, suppose we start with some point in the plane and keep hitting it with and/or in any way we like. Then we’ll get a sequence that converges to a point in And even better, every point in show up as a limit of a sequence like this. We can even get them all starting from the same
All this follows from a famous theorem due to John Hutchinson.
“Cute,” you’re thinking. “But what does this have to do with roots of polynomials whose coefficients are all 1 or -1?”
Well, we can get polynomials of this type by starting with the number 0 and repeatedly applying these two functions, which depend on a parameter :
and so on. All these polynomials have constant term 1, never -1. But apart from that, we can get all polynomials with coefficients 1 or -1 using this trick. So, we get them all up to an overall sign—and that’s good enough for studying their roots.
Now, depending on what is, the functions and will give us different generalized dragon sets. We need for these functions to be contraction mappings. Given that, we get a generalized dragon set in the way I explained. Let’s call it to indicate that it depends on .
Greg Egan drew some of these sets . Here’s one that looks like a dragon:
Here’s one that looks more like a feather:
Now here’s the devastatingly cool fact:
Near the point z in the complex plane, the set Sam Derbyshire drew looks a bit like the generalized dragon set Sz!
The words ‘a bit like’ are weasel words, because I don’t know the precise theorem. If you look at Sam’s picture again:
you’ll see a lot of ‘haze’ near the unit circle, which is where and cease to be contraction mappings. Outside the unit circle—well, I don’t want to talk about that now! But inside the unit circle, you should be able to see that I’m at least roughly right. For example, if we zoom in near , we get dragons:
which look at least roughly like this:
In fact they should look very much like this, but I’m too lazy to find the point and zoom in very closely to that point in Sam’s picture, to check!
Similarly, near the point , we get feathers:
that look a lot like this:
Again, it would be more convincing if I could exactly locate the point and zoom in there. But I think I can persuade Dan Christensen to do that for me.
Now there are lots of questions left to answer, like “What about all the black regions in the middle of Sam’s picture?” and “what about those funny-looking holes near the unit circle?” But the most urgent question is this:
If you take the set Sam Derbyshire drew and zoom in near the point z, why should it look like the generalized dragon set Sz?
And the answer was discovered by ‘some guy on the street’—our pseudonymous, nearly anonymous friend. It’s related to something called the Julia–Mandelbrot correspondence. I wish I could explain it clearly, but I don’t understand it well enough to do a really convincing job. So, I’ll just muddle through by copying Greg Egan’s explanation.
First, let’s define a Littlewood polynomial to be one whose coefficients are all 1 or -1.
We have already seen that if we take any number , then we get the image of under all the Littlewood polynomials of degree by starting with the point and applying these functions over and over:
a total of times.
Moreover, we have seen that as we keep applying these functions over and over to , we get sequences that converge to points in the generalized dragon set .
So, is the set of limits of sequences that we get by taking the number and applying Littlewood polynomials of larger and larger degree.
Now, suppose 0 is in . Then there are Littlewood polynomials of large degree applied to that come very close to 0. We get a picture like this:
where the arrows represent different Littlewood polynomials being applied to . If we zoom in close enough that a linear approximation is good, we can see what the inverse image of 0 will look like under these polynomials:
It will look the same! But these inverse images are just the roots of the Littlewood polynomials. So the roots of the Littlewood polynomials near will look like the generalized dragon set .
As Greg put it:
But if we grab all these arrows:
and squeeze their tips together so that they all map precisely to 0—and if we’re working in a small enough neighbourhood of 0 that the arrows don’t really change much as we move them—the pattern that imposes on the tails of the arrows will look a lot like the original pattern:
There’s a lot more to say, but I think I’ll stop soon. I just want to emphasize that all this is modeled after the incredibly cool relationship between the Mandelbrot set and Julia sets. It goes like this;
Consider this function, which depends on a complex parameter :
If we fix this function defines a map from the complex plane to itself. We can start with any number and keep applying this map over and over. We get a sequence of numbers. Sometimes this sequence shoots off to infinity and sometimes it doesn’t. The boundary of the set where it doesn’t is called the Julia set for this number
On the other hand, we can start with , and draw the set of numbers for which the resulting sequence doesn’t shoot off to infinity. That’s called the Mandelbrot set.
Here’s the cool relationship: in the vicinity of the number the Mandelbrot set tends to look like the Julia set for that number This is especially true right at the boundary of the Mandelbrot set.
For example, the Julia set for
looks like this:
is a tiny patch of the Mandelbrot set centered at the
same value of They’re shockingly similar!
This is why the Mandelbrot set is so complicated. Julia sets are
already very complicated. But the Mandelbrot set looks like a
lot of Julia sets! It’s like a big picture of someone’s face made of little pictures of different people’s faces.
Here’s a great picture illustrating this fact. As with all the pictures here, you can click on it for a bigger view:
But this one you really must click on!
So, the Mandelbrot set is like an illustrated catalog of Julia sets. Similarly, it seems the set of roots of Littlewood polynomials (up to a given degree) resembles a catalog of generalized dragon sets. However, making this into a theorem would require me to make precise many things I’ve glossed over—mainly because I don’t understand them very well!
So, I’ll stop here.
For references to earlier work on this subject, try “week285″.