Matt's Rotor Router Page
When Jim Propp first showed me his Rotor Router model (maybe in 2002?), I was amazed like everyone else at the beautiful and mysterious circles it produces. Playing around with it, I came to appreciate that it is somehow operating in a very precise way:
Here are my "challenge problems" on this topic:
Some discoveries of September 2009....
1.
First of all, here is a Moiré pattern that is very similar in some ways
to that found in the rotor router circle:
Moire.png (1.4 MB)
It is produced on the unit circle in the complex plane by mapping each pixel to
(z+1/z) / 2d
where d is the distance between pixels,
and then using a color map with periods 1 and i.
The formula is simple, but that didn't make it easy to find!
It can be derived via the integral of the observable splotch pattern,
1/z^2 - 1/2, adjusted to the grid size, with the right color map.
It is close to the derivitave of the ideal tent (odometer) function r^2(ρ^2 - ln ρ^2 - 1)
where ρ = (x^2 + y^2)/r^2, except for the real/complex technicality and a constant factor.
This is odd because one would naively expect the colors to be a real-valued Moiré
pattern of the tent function itself (the function giving how many times any particle has passed
through a given lattice point).
This picture gets many aspects of the fine Moiré detail right --
solid splotches vs. checkerboard vs. plaid, etc. -- but leaves others for the future
(the two types of two-color diagonal-square patterns, for example,
which seem to be oriented according to the square of the orientation of the Moiré
octagons).
If you are concerned about the sizes of the splotches,
the size goes down with increasing numbers of pixels,
both with this formula and in the original rotor router pictures.
2.
Second of all, if you look at the paths of individual particles
(which can be quite long,
for example particle number 3110212
has a path whose length is over 7 times the area of the circle!),
it is not too uncommon for a particle to take the same path as its predecessor,
but rotated by 90 degrees.
In fact, this reliably happens about two percent of the time
for the first few million particles.
(That this happens at all was first noticed in 2002 in the "older stuff" file below,
but it looked much rarer -- the majority of the time, when it happens, the new particle's
path actually continues one step longer than the previous path, and these cases were not
noticed originally.)
Looking for consecutive paths where one is a rotated prefix of the other,
we only see equal length paths or the second path being one step longer.
Strange, isn't it?
3.
Third of all, a new hypothesis, confirmed for the first few million steps...
The rotor router blob is always convex!
That is, it consists of exactly those lattice points which lie on or in its convex hull.
Every new point expands the convex hull.
This is just another step towards specifying what we mean by "it makes a circle",
but instead of being vague and fuzzy, convexity is concrete and easy to check.
4.
And now, I have finally taken a look at "how circular is the circle?", which is the
question which prompted Jim to write to me and me to look at this again...
And my answer is, so far as I can tell, it does not approach being a circle!
But wait, before you eat your hat, allow me to be more precise...
All I mean is that there are systematic deviations away from circularity that do not appear to go away.
If we take the center of the circle to be at (.5,.5), and compare each particle's distance from
this center to sqrt(n/pi), then these differences do not appear to approach zero.
They vary between roughly -1/3 and +1/3.
There are larger deviations near the beginning (such as the egregious particle #7, with a
deviation of nearly 0.8 pixels), but after particle #62, the deviation is
never again larger than 1/2 (half a pixel), and after particle #55004, the deviation is
never again larger than 0.34. The final particle I have seen exceeding a deviation of 1/3
is #344886, although admittedly I have only looked about ten times that far.
But particles continue to have deviations over 0.31 for as far as I have looked.
So, the natural question is, what is the spatial arrangement of these deviations?
The answere is here, in a picture that shows positive
deviations (particles that landed unduly far from the center) in white and negative
deviations (parts of the circle that are flattened towards the center) in blue
(+1/3 = pure white, -1/3 = pure blue).
The result looks quite systematic, and does not appear to be fading away as the circle grows,
except at the very beginning.
Now there are those who would say that as the shape grows larger, if it only deviates from
a perfect circle by +-1/3 of a pixel, then in the limit the shape
(scaled down to have diameter 1, say) is indeed a perfect circle.
They would of course be right, but with such a lax, anything-goes kind of definition,
even a totally fuzzy blob such as could be made with totally random walks would qualify
as a circle in such a limit!
We naturally have much higher expectations for the precise shapes produced by rotor routers.
So now we see that the highest point of a rotor router "circle" tends to be rather to the left
of the lowest point, and the rightmost point tends to be rather above the leftmost point,
in sharp contrast with what other circle-producing algorithms generate. So now you know how
to distinguish a large rotor router circle from an ordinary circle, and you can impress your
friends by telling the difference based on shape alone. This is the sense in which the shape
is different from a circle.
It looks like the arms in this windmill picture become narrower as they go out, as opposed to
having a limiting value in each radial direction. Their width presumably grows like sqrt(radius).
Note that although the windmill has a counterclockwise look to it,
the rotors rotate clockwise
(red went north or was absorbed, and will go east, then green, blue, yellow).
It would be very interesting to have a mathematical approximation to this windmill picture!
million particle picture on directed square grid with 2-state rotors
