18 April 2008

Visualizing the Sieve of Eratosthenes (in the May Notices of the AMS)

From the May Notices of the AMS: Visualizing the Sieve of Eratosthenes, by David N. Cox.

The basic idea of the article is that we can color the point (n, m) whenever m and n are positive integers and m divides n; then interesting patterns appear among lattice points in the first quadrant. Alternatively, the row y = n contains colored points at x = n, 2n, 3n, ... and in general every nth column. The procedure generalizes the sieve of Erastosthenes; the number of marked points in the column x = n is just the number of divisors of n.

One pattern that appears comes about when we mark (3,1), (6,2), (9,3), and so on, so all the lattice points on a diagonal through the origin of slope 1/3 are colored; something similar happens for every k. But diagonals also appear "radiating" from points on the x-axis which are not the origin. For example, radiating out of the point (2520, 0) we have a diagonal of slope 1, which passes through the marked points (2521, 1), (2522, 2), ..., (2530, 10); this occurs because 2520 is divisible by each of 1 through 10. In general one sees

Cox points out some mysterious-seeming parabolic patterns of the marked points; for example he mentions a left-opening parabola with vertex (17956, 134). Now, 1342 is 17956 -- and so the parabola constains the points (17956-x2, 134 ± x) for each x. In fact, we have a parabola containing the points (k2-x2, k ± x) for each integer k. Cox says that no right-opening parabolas are observed; these would correspond to factorizations of the form (k2+x2, k ± ix) where i is the imaginary unit, but he's working over the integers! Of course, if you stare at the points you might see what you think are right-opening parabolas, but the appearance of those is probably just a coincidence. At this point I will wave my hands and intone the magic words "Ramsey theory". In any case, right-opening parabolas, should they exist, are certainly not given by such a simple rule.

(In the interests of the sentence preceding this one being entirely correct, I will define "simple" as "things I thought of while writing this post".) Anonymous said...

Cool! I'll have to check it out!

"At this point I will wave my hands and intone the magic words "Ramsey theory"." Love it! Anonymous said...

That sucker was 16 mgs! I click download without checking! Lucky I was at work not home.

I have no discipline: click click click - one day I'll be clicking away and someone from HR will whack me on the head