Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following spectacular image, created by Sam Derbyshire and described in John Baez's article "The Beauty of Roots":

enter image description here

In this image are plotted all the complex roots of all polynomials of degree $\le 24$ with coefficients drawn from the set $\{-1, 1\}$. There is some amazing structure in there, about which many questions can be asked! The symmetries about the $x$-axis, the $y$-axis, and the unit circle are easily explained, though: it is not hard to show that if $z$ is a root of a polynomial with coefficients in $\{-1,1\}$, then so are $\bar z$, $-z$, and $z^{-1}$.

Please do look at John Baez's aforementioned article for more zoomed images showing the beautiful detail in this distribution of roots. In particular, towards the interior of the unit circle, the distribution does not fall off smoothly, but seems to form fractal patterns, such as near $z = 4/5$, near $z = 4i/5$, and near $z = e^{i/5}/2$. In fact, these patterns are extremely reminiscent of the images produced by iterated function systems of affine transformations. With a little experimentation using David Eck's Chaos Game applet, I found that to produce fractals similar to these patterns, one only needs to use two affine maps, both of which are the composition of a scaling by about 70% and a rotation by $\arg z$, and differ by a translation. To illustrate:

enter image description here

enter image description here

I'm tempted to say that the whole distribution looks like a catalogue of such affine IFSs, the way the Mandelbrot set is like a catalogue of Julia sets.

My question is simple: Why is this so? What is the reason that the roots of $\{-1,1\}$ polynomials form such a fractal distribution, that behaves locally like an affine IFS?

share|improve this question
add comment

2 Answers 2

I can't give a complete answer, but I can make a few observations in the general direction of an answer. Note that most of this is based on memory from spending several hours looking at the behavior of these plots and observing how they relate to roots for individual polynomials. This is all "empirical math" (assuming that's even a thing, heh) but the patterns are pretty clear and while I doubt I have the mathematical background to make most of it rigorous I doubt it would be too difficult.

  • It's not limited to coefficients from $\{-1,1\}$; almost any collection of polynomials with coefficients chosen from a very limited set will produce similar patterns.

  • The character of the pattern is directly tied to the location on the complex plane, specifically the effect of multiplication. So I suspect that it catalogs the IFSs only insofar as the complex plane catalogs (some) affine transformations. Note that the Julia set formula, in contrast, lets the transformation vary during iteration with only an additive constant to alter the shape, which is why it has the more elaborate chaotic behavior vs. the IFS-like structure here.

  • Each fragment of a pattern roughly resembles a Cantor set, with fragments overlapping heavily except at the outer fringes. Each fragment is twisted according to the nature of complex multiplication, and the combination creates the similarity you noticed.

The latter two points are fairly intuitive given the nature of complex numbers and mostly apparent from inspection of the plots, but don't really do much to explain why, which I imagine is why Baez didn't remark on it.

Also unexplained are the gaps, such as those around the roots of unity. I don't recall the exact placements, but I recall it also being obvious why the locations of the gaps were relevant, but not why root density drops off so sharply around them. I could probably make some guesses, but only with copious handwaving involved.

On the other hand, except for the gaps, I believe the thick ring around the unit circle simply consists of more variations on the same patterns, denser and heavily overlapped, until detail is no longer visible.


Regarding variations on plots like this, the same approximate pattern appears regardless of polynomial degree, and for any set of coefficients of the form $\{-N, -(N - 1) ... -1, 1 ... N - 1, N\}$. The density of roots around the unit circle, the prominence of the gaps around certain points, and the character of the fringe inside the gaps all vary with degree; this is hard to see in Derbyshire's plot rather than one limited to polynomials of a single degree.

The shape of the overall plot changes if the coefficients are not chosen as above, being either of different magnitudes or chosen from more than one set. Note the plots on this page, particularly those near the bottom. The coloring indicates sensitivity of the points to changes in coefficients, which indicates which parts of the plot may distort asymmetrically.

My observations, in general, were:

Doing both in moderation creates... odd effects:

distorted polynomial root plot

share|improve this answer
    
Having a little more free time now, I'm interested in exploring this question again. What code did you use to generate these plots? Would you mind sharing it? –  Rahul Aug 19 '11 at 12:08
    
@Rahul Narain: It was about a dozen lines of Haskell, which simply enumerated the possible coefficients based on whatever generating scheme, passed each one at a time to a matrix calculation library that had a root finder, plotted the results on an in-memory bitmap, then saved the result as a .PNG. The plots above, with polynomials of degree 18 or so, took only a few minutes to create. Changing the polynomial parameters was done by edit-and-recompile. –  camccann Aug 19 '11 at 12:34
    
@Rahul Narain: I'd be happy to share but, 1) I don't recall where the code is right now, and 2) recompilation is not the most user-friendly approach to accepting input parameters. I could probably find and/or reimplement it tonight with modifications to be slightly less inconvenient to use, if you'd like. –  camccann Aug 19 '11 at 12:36
    
Well, the code you described doesn't sound too hard, now that I think about it. I think I'll try to write it myself and save you the trouble of looking for, cleaning up, and/or reimplementing it. But thanks! –  Rahul Aug 19 '11 at 13:50
    
@Rahul Narain: Well, I've been meaning to do a similar tidy-up on a different image rendering program, which the root plotting could then be dropped into easily, but it wouldn't be an immediate priority otherwise. If I do get around to it, I'll ping you with a comment here. –  camccann Aug 19 '11 at 14:19
add comment
up vote 2 down vote accepted

I recently noticed that at some point since I posted this question, the article by John Baez that inspired it has been updated. It now includes an explanation of the phenomenon in terms of compositions of the one-parameter families of functions $f_+(x) = 1 + zx$ and $f_-(x) = 1 - zx$, which are evidently the two affine maps I was speculating about in my question. The relationship between the set of roots and the compositions of $f_+$ and $f_-$ apparently is indeed analogous to the Mandelbrot-Julia correspondence. I don't entirely follow the argument in the updated article yet, but it seems clear that the answer to my question is in there, so I'm posting a link to it as this community wiki answer.

(Since this is CW, if anyone wants to edit in a concise restatement of the linked argument, go right ahead.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.