This just in from Bill Gasarch: The quest for a rectangle-free four-coloring of the 17-by-17 grid is over. If you don’t know what that’s all about, and you’d like to find out, see Bill’s blog post from 2009 or my earlier comments (one, two, three).

The coloring above (along with several others) was found by Bernd Steinbach of Frieburg University and Christian Posthoff of the University of the West Indies. They win the $289 prize that Gasarch had offered for a solution.

Gasarch has posted more details on the Computational Complexity blog. But apparently we’re going to have to wait until May to learn how the coloring was found. The one interesting clue revealed so far is that the paper will be presented at the International Symposia on Multiple-Valued Logic.

Addendum 2012-02-11: For the benefit of those who don’t read the comments, I repeat a remark from reader Craig:

What I don’t like about this solution (or, indeed, the solutions to other related problems) is the arbitrariness. Is it not the case that you should be able to permute the rows and columns of any solution and arrive at a new solution? That being the case, I feel that you should be able to adjust the rows and columns here in order to highlight some kind of revealing pattern in the colouring.

Indeed, the matrix of dots shown above is one of (17!)² equivalent solutions. How should we choose one of those permutations to serve as a representative of the class?

Personally, I’m not optimistic about finding a “revealing pattern” in any of the 126513546505547170185216000000 permuted matrices. If there were some simple, concisely described rule governing the arrangement of the dots—other than the no-monochrome-rectangle criterion itself—then we could make use of that rule to find a solution, or at least to reduce the search space. When Steinbach and Posthoff reveal their secret method, maybe we’ll learn that such a rule exists, but I doubt it.

Even if we can’t make a pretty picture by permuting rows and columns, it would still be useful to have some canonical ordering, so that we could easily determine whether two arrays are members of the same equivalence class. I’m not sure how best to do that, but if we assign an ordering to the colors, we can at least sort them.

There is still some arbitrariness here. We have not dealt with the 4! orderings of the colors. Is there a smarter way to go about it?

The ever-puzzling Peter Winkler offered three problems in the August Communications of the ACM:

1. Does every positive integer divide some number of the form 1{0,1}*—that is, a positive integer whose decimal representation includes no digits other than 0 and 1?

2. Does every positive integer divide a Fibonacci number?

3. Is there an odd perfect number (an odd integer equal to the sum of its proper divisors)?

Answers to Problems 1 and 2 have now been published in the September CACM, so I won’t worry too much about spoiling anyone’s fun with the discussion below. Still, if you’d like to take a crack at the first two problems, do so before you read on. (As for Problem 3, you needn’t worry about my giving away the secret.)

Winkler’s solutions are based on the pigeonhole principle. If you divide successive 1{01}* numbers or successive Fibonacci numbers by any fixed integer n, the remainders necessarily lie between 0 and n–1. Furthermore, the sequence of remainders repeats cyclically. For example, the Fibonacci numbers modulo 3 are:

0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 . . .

The trick is to show that the cyclic sequence of remainders always includes zero. For details see Winkler’s solution page mentioned above. (CACM is behind a paywall, but I think these links will work for nonsubscribers.) A 2007 paper by Tanya Khovanova also explains what’s going on, and gives a couple of further enticing problems.

The pigeonhole argument answers the questions as posed, but it tells us very little about the structure of the solutions. Which 1{01}* numbers and which Fibonacci numbers are divisible by various integers n? Are there any interesting patterns in the results? I was curious, so I started computing.

The graph above shows the smallest 1{01}* numbers divisible by each n from 1 through 30. The standout pattern is the series of tall flagpoles for n a multiple of 9. It appears that 1{01}* numbers that include 9 among their divisors are rarities. I didn’t foresee this pattern, although I should have. It’s connected with the long-forgotten ritual of “casting out nines,” which in turn is based on the following fact: A decimal number is divisible by 9 if and only if the sum of its digits is divisible by 9. (Question: What are the smallest 1{01}* numbers divisible by 99 and by 999? Answers at the end of this article.)

Below is the analogous graph for Fibonacci numbers divisible by values of n between 1 and 30.

There are some interesting patterns here, too, but we need a bigger sample to see them clearly.

By the way, it’s important to notice that the ordinate axis of the Fibonacci graph gives the index of each Fibonacci number, not the Fibonacci number itself. I adopt this indexing convention :

The diagram below offers another way of looking at the mapping from integers n (on the left) to the smallest Fibonacci number F(m) divisible by n (on the right):

A few Fibonacci numbers are highly popular—notably F(12), F(24), F(30), F(60). Indeed, F(24) is the destination of 12 of the first 100 values of n. The reason for this clustering is not a deep mystery; Fibonacci numbers of the form F(6k) tend to be very “smooth” numbers, with an abundance of small factors. F(60) is equal to 1,548,008,755,920, a number that has 960 divisors. F(240) has more than 1.3 million divisors. These smooth numbers simply have more chances to be the smallest F(m) divisible by some n.

But the clustering also highlights an asymmetry. The solution of the Winkler problem says that we can draw a line from every n on the left to a specific F(m) on the right, the least Fibonacci number divisible by that n. What about the converse? Is every F(m) the least Fibonacci number divisible by some n? Can we draw a line from every F(m) on the right to some n on the left? The diagram as shown, which covers all n up to 100, has many gaps in the set of nodes on the right; for example, none of the numbers between F(61) and F(67) are among the smallest Fibonacci numbers divisible by an n ≤ 100. If we were to extend the computation to larger values of n, would all the gaps in the righthand column eventually be filled in? Let me state that question a little more formally: For every m, is there an n that divides F(m) but does not divide F(k) for any k < m?

This is a trick question. The answer is No because of F(2), which is “shadowed” by F(1), since F(1) = F(2) = 1. But F(2) is unique in this respect. If we set aside this one exception, is the statement true for all other F(m)? Now the answer is Yes, but trivially so. Every F(m) is divisible by F(m) itself, which cannot possibly divide any F(k) with k < m. (In the case of Fibonacci numbers that are prime, F(m) and 1 are obviously the only divisors.)

To avoid the trivial solution, we need to ask a more tightly constrained question, which I’ll phrase as a conjecture:

If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.

Is the conjecture true? If so, where do all those new divisors come from? What mechanism guarantees that every nonprime F(m) will introduce at least one divisor never seen before in the sequence of Fibonacci numbers? If the conjecture is false, then there are “unselfish” Fibonacci numbers that share all their proper divisors with their smaller siblings, keeping none for their own exclusive use. What is the smallest such unselfish F(m)? (For what it’s worth, a computational search shows that any counterexample to the conjecture must lie beyond F(382).)

I’m going to leave this question as a challenge. I’ll give an answer in an update—in the unlikely event that no one posts a complete solution in the comments section in the next 10 minutes. One further note: Unselfish numbers do exist among the 1{01}* numbers; the smallest example is 1111, whose only proper divisors are 11 and 101, both of which obviously divide lesser 1{01}* numbers. Thus if you want to assert that Fibonacci numbers behave differently in this respect, you might want to think about what distinguishes the two sequences.

Finally, more about patterns of divisibility in Fibonacci numbers. The dots in the figure below show the least m such that n divides F(m) for all n up to 1,000:

It’s interesting that the dots tend to line up along certain rays, namely those whose slope is a ratio of small integers. The slopes m/n = 1 and 1/2 are the most clearly delineated, but there are also aggregations detectable by eye at m/n = 1/4, 1/3, 2/3, 3/4 and 3/2. The ray at m/n = 2 has only four data points on it in the range up to n = 1,000, but it is significant for another reason: It marks the absolute boundary of the m/n ratio. In other words, not only is it true that every n divides some F(m), but furthermore the m in question is never greater than 2n.

There is no sign of such radial streaks or other distinctive patterns in the equivalent graph for the 1{01}* numbers:

As with the Fibonacci graphs, the vertical axis here represents not the numerical magnitude of an 1{01}* number but its index within the sequence. For example, the smallest 1{01}* number divisible by 18 is 1,111,111,110, which is the 1,022nd number in the 1{01}* sequence. (It’s more than coincidence that 1111111110₂ = 1022₁₀.) Hence there’s a dot at n = 18 and vertical coordinate 1,022. I have colored orange all the dots associated with n that are multiples of 9. The dots along the upper margin of the graph are off-scale and actually belong at much higher elevations. For example, the dot for n = 99 should be at height 262,143 (the index of 111,111,111,111,111,111). The dot at n = 999 belongs at height 134,217,727 (the index of 111,111,111,111,111,111,111,111,111).

Update 2011-10-09: More than a month ago I promised an answer to the question posed above: Is there a composite Fibonacci number for which all the proper divisors are also divisors of smaller Fibonacci numbers? When I asked the question, I had an answer for it. But a week later when I sat down to write up the proof, it fell apart like wet tissue. Since then the problem has been constantly with me. I’ve been waking up with it in the morning; I go to bed with it at night; it comes back to visit at idle moments during the day. Several times I’ve thought I had found a solution, but then the argument fell to pieces again. If some kindly reader had posted a full proof in the comments, I could have responded, “Yes, yes, exactly so. That’s just what I had in mind.” But only one reader came to my rescue (thanks, unekdoud!); although that suggestion seemed to be heading in the right direction, I wasn’t able to fill in all the details.

Now I have yet another proof. It’s the middle of the night as I write this, but I’m going to stay up and get this posted before the idea disintegrates again.

Here, copied from above, is a more precise statement of the problem, phrased as a conjecture:

If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.

I claim the conjecture is true, based on this assertion: If every divisor of F(m) also divides some smaller F(k), then the F(k) in question cannot be greater than F(m/2), while at least one of the divisors must be no smaller than √F(m). But this is impossible, because √F(m) > F(m/2) for all m > 2. (For odd m, take the ceiling of m/2.)

The key to the proof is again the cyclic pattern of remainders observed when the members of the Fibonacci sequence are taken modulo an integer. In particular, if an integer a divides F(m), then a also divides F(2m), F(3m), F(4m), . . .   For example, F(8) = 21 is divisible by 3 and 7, and these numbers are also divisors of F(16) = 987 and F(24) = 46,368.

An immediate consequence of this cyclic structure is the remarkable fact that F(k) divides F(m) if and only if k divides m. Again let me cite an example: F(15) = 610 is divisible by F(3) = 2 and by F(5) = 5 and by no other Fibonacci numbers. (The prime factors of 610 are 2, 5 and 61. Note that the factor 61 divides no smaller Fibonacci number, and so F(15) is a confirming instance of the conjecture.)

A further observation is that if m is prime, then F(m) cannot be divisible by any Fibonacci number.

Let’s look at the divisors of F(m) for composite values of m. We know that such divisors exist. They include every F(k) for which k divides m, as well as all the proper divisors of each such F(k). Suppose, contrary to the conjecture, that these known divisors comprise all the divisors of F(m). Then for each integer a that divides F(m) we can ask which F(k) it also divides. Actually, a given a might divide many F(k), but consider just the smallest member of this set. If a divides this minimal F(k), then it also divides F(2k), F(3k), and so on, but it divides no other Fibonacci numbers. Thus F(m) must be a member of this series, or in other words m must be a multiple of k. The smallest such multiple is m = 2k. This gives us half of the proof: If a divisor of F(m) also divides F(k), k can be no larger than m/2.

The second half is easier. Divisors come in pairs; they are integers a and b such that ab = F(m). Furthermore, if a ≤ √F(m), then b ≥ √F(m). Thus we conclude that b cannot be less than the square root of F(m) or more than F(m/2)—a contradiction.

The same reasoning applies with even greater force in the case of prime m. If we imagine that a divisor of F(m) is also a divisor of some smaller F(k), we are driven to the conclusion that k divides m, which can’t be so for prime m.

In the course of working all this out in my bumbling-stumbling way, while making lots of lists of Fibonacci numbers and their divisors, the patterns I was seeing suggested a slightly stronger conjecture:

Every Fibonacci number that is not a perfect power has at least one prime factor that appears in no smaller Fibonacci number.

The perfect-power exception excludes exactly five Fibonacci numbers: F(0) = 0, F(1) = 1, F(2) = 1, F(6) = 8 = 2³ and F(12) = 144 = 12². No other Fibonacci numbers are perfect powers; I find it interesting that this fact was proved only in the past few years, and only with the use of industrial-grade mathematical machinery. On the other hand, “my” conjecture was proved almost a century ago by the American mathematician R. D. Carmichael. If I had known that fact a few weeks ago, I would have slept better. But maybe learned less.

On the subject of the Collatz conjecture (also known as the 3x+1 problem), Paul Erdos remarked: “Mathematics is not yet ready for such problems.” Shizuo Kakutani joked that the problem was a Cold War invention of the Russians meant to slow the progress of mathematics in the West. Richard Guy listed it in an article titled “Don’t try to solve these problems!” All of these warnings to the unwary have had the expected effect: A bibliography compiled by Jeffrey Lagarias cites 200 works on the Collatz conjecture, and there are hundreds of other papers that didn’t make the list. This past week brought one more preprint: a claimed proof of the conjecture by Gerhard Opfer of the University of Hamburg.

The Collatz conjecture can be stated in terms of this little recursive program:

    procedure collatz(x)
        if x=1 then halt
        elseif even(x) then collatz(x/2)
        elseif odd(x) then collatz(3*x+1);

The conjecture makes the following claim: If x is any positive integer, then the program eventually halts. For example, starting with x=3, the successive values of x are 3, 10, 5, 16, 8, 4, 2, 1—and on reaching x=1 the program halts. You could try a few other starting values for yourself; x=27 is a popular choice; x=319,804,831 is even better. But please remember Guy’s advice. Also note that the Collatz conjecture has been verified numerically by Tomás Oliveira e Silva for all x up to 20 × 2⁵⁸ . Thus if you’re searching for a counterexample, you may as well start somewhere north of 5,764,607,523,034,234,880.

The conjecture is named for Lothar Collatz (1910–1990), who investigated the curious properties of the 3x+1 iteration when he was a young student, circa 1930. Opfer, the author of the new proposed proof, was a Ph.D. student of Collatz in the 1960s. This conjunction suggests a novelistic storyline: A mathematician struggles all his life with an intractable problem, then hands it on to his student, who dedicates his own career to the task, finally achieving triumphant success some 80 years after the story began. But apparently that’s not how it happened. Collatz never returned to the 3x+1 problem after the 1930s; almost all of his mature work was in numerical analysis. Opfer is also a numerical analyst and only recently turned to the 3x+1 problem. There’s no grand saga of a multigenerational obsession here.

Much of Opfer’s paper is beyond my understanding, but I can piece together a crude guide to a few of the basic ideas. The proof begins with a mathematical change of venue. A problem originally posed in terms of the simplest kind of arithmetic on the natural numbers is transported to the realm of holomorphic functions on the complex plane. It’s like being swept up from a farm in Kansas and set down in the Land of Oz. The idea for this transformation comes from the work of Lothar Berg and Günter Meinardus in the 1990s, who established a direct connection between these two realms. They set up a certain system of equations for functions of a complex variable z, then showed that the Collatz conjecture is true if and only if the solutions of the equations all lie in a certain region. In the simplest case, the region is the open unit disc—the disc centered at the origin with |z| < 1. Who’d've thunk it? What we do in Oz has consequences back in Kansas!

How can those two very different problems be yoked together? As I (tenuously) understand it, the complex functions of Berg and Meinardus can be represented by formal power series whose integer coefficients encode information about the sequence of numbers generated in the Collatz iteration. The rest of the Opfer proof is all about those coefficients. Thus we click our heels and return from the Emerald City to the land of number theory.

At this point Opfer begins reasoning in terms of algorithms that generate sets of coefficients. I’m on much friendlier terms with algorithms than I am with holomorphic functions, but strangely enough this is where I begin to lose my footing as I try to follow Opfer’s steps. His aim is to show that all coefficients vanish except for those whose indices lie in a certain congruence class. (Specifically, he is seeking to prove that all coefficients η_j = 0 except those for which j = 3k–1, k ∈ 1, 2, 3, … .) He argues that his algorithms for generating the coefficients yield exactly this property. But this is where I get lost.

Opfer is not the first to announce a proof of the Collatz conjecture. The earlier attempts did not stand up to scrutiny, and in various corners of nerdom there’s already skepticism about this try, too. As for me, I can’t say whether there are gaps in Opfer’s proof because there are such wide gaps in my understanding of it. The paper has been submitted to Mathematics of Computation, which is certainly an appropriate journal for this work, and I’m content to wait and see what comes of the referreeing process.

Like many others, I first learned of the 3x+1 problem from Martin Gardner’s Scientific American column in the early 1970s. A decade later, when I briefly had a chance to fill Martin’s space in the magazine after his retirement, 3x+1 was one of the first subjects I wrote about (nearly illegible PDF—sorry; it’s my only copy). I’m delighted to have this opportunity to poke at the problem again. Even if the Opfer proof comes to nothing, it has given me an incentive to read some of the recent literature, including that illuminating trip to Oz courtesy of Berg and Meinardus. I would also like to recommend a book by Günther J. Wirsching, The Dynamical System Generated by the 3n + 1 Function (Springer, 1998). A version of at least one chapter is available online.

Jeffrey Lagarias also has a recent book: The Ultimate Challenge: The 3x+1 Problem (AMS, 2010), but I haven’t seen it yet. The volume reprints a number of survey articles and historical documents, including a 1985 American Mathematical Monthly article by Lagarias himself that is still the best starting point for those who want to ignore all good advice and dive into the problem. I am particularly eager to see another chapter: an English translation of the only paper in which Collatz discusses his work on 3x+1; it is an account in Chinese of a talk by Collatz at Qufu Normal University in 1986.

Several weeks ago, on the morning after the first winter storm here in the Boston area, I wrote about some peculiar snow geometry on porch railings. Now, following another storm (which I wish I could believe might be the last of the season), I have more puzzling snow shapes to present.

What gives rise to the quasi-periodic undulations in the snow filling my neighbors’ rain gutters?

Note that on the roof above the gutter the snow depth appears to be perfectly uniform. The scalloped shapes appear only in the gutters.

Elsewhere on the same house, the waves are less regular in period and smaller in amplitude, but they are still clearly present.

On the opposite side of a different house I find more undulations, this time in the gutters draining a relatively flat porch roof.

All of the gutters shown above are oriented northwest-southeast, and were roughly parallel to the prevailing wind direction during the storm (although winds were very light). Gutters perpendicular to these revealed little or no evidence of wavelike disturbances. Waves were also absent from other linear surfaces, such as railings, regardless or orientation.

I’ve seen no sign of such wavelike formations in any previous snowfall this winter. To my eye, the waveforms are cusplike—cycloidal, perhaps, rather than sinusoidal. The snow was fairly heavy and sticky (note the coating on tree branches); temperatures were just a few degrees below freezing; total accumulation was about 10 cm.

Anyone care to propose a mechanism?

Update: After a welcome day of warm rain, the answer has slowly emerged from the wilting snow, and it has nothing to do with subtleties of fluid dynamics or particle deposition.

In the photo above, peeking out from behind the last remnants of the melting snowdunes, are the metal spikes and straps that fasten the gutters to the fascia board. Their somewhat irregular spacing is a good match for the pattern of cusplike peaks. Of course! How could I have failed to think of that?

Why did the dunes appear only in this storm? Earlier snows were fluffier and deeper, and probably less affected by the hanger straps. Why only on certain sides of the houses? I’m not sure about that, but the one duneless gutter I’ve been to able to examine closely has a different hanger system, without the obstructing straps.

It’s been almost a year since Bill Gasarch gave us the problem of four-coloring the nodes of a 17 × 17 grid in such a way that no rectangle has all four corners the same color. (See my earlier commentary here and here.)

The problem remains open, the prize of $17² unclaimed.

A few weeks ago I had a momentary fantasy that I might have come upon the answer. I was browsing in a strange New England emporium called Building 19, full of merchandise found nowhere else (thankfully). From across the room I spotted a sofa cushion that looked like it might well be a rectangle-free four-colored grid.

Sadly, a closer look showed that the cushion is neither rectangle-free nor four-colored. Nor 17 × 17 for that matter. And the price tag reads $399.90, so if Bill wants to receive the solution in the form of tacky furniture, he’s going to have to up his offer.

But let us set aside these disappointments. There’s happier news from elsewhere. Martin Schweitzer has turned the square-free-rectangle problem into a game! He explains that he was exploring the new canvas element of HTML5, and thought the rectangle-free problem would make a nice Javascript programming project. The result is entertaining and may even lead to better intuition about the structure of the problem.

On the other hand, the hardest level (”Ninja”) in Schweitzer’s game is only a 12 × 12 array, so don’t think you’re going to click away at little colored squares and earn yourself $289.

The program requires a canvas-capable browser, such a recent version of Chrome, Firefox, Opera or Safari.

The National Research Council is getting ready to release a new assessment of graduate-education programs in the U.S. The previous study, published in 1995, gave each Ph.D.-granting department a numerical score between 0 and 5, then listed all the programs in each discipline in rank order. For example, here’s the top-10 list for doctoral programs in mathematics (as presented by H. J. Newton of Texas A&M University):

 rank    school                 score   
    1    Princeton               4.94
    2    Cal Berkeley            4.94
    3    MIT                     4.92
    4    Harvard                 4.90
    5    Chicago                 4.69
    6    Stanford                4.68
    7    Yale                    4.55
    8    NYU                     4.49
    9    Michigan                4.23
   10    Columbia                4.23

Note that the scores of the first two schools are identical (to two decimal places), and the first four scores differ by less than 1 percent. Given the uncertainties in the data, it seems reasonable to suppose that the ranking could have turned out differently. If the whole survey had been repeated, the first few schools might have appeared in a different order. Doctoral candidates in mathematics are presumably sophisticated enough to understand this point. Nevertheless, the spot at top of the list still carries undeniable prestige, even when you know that the distinction could be merely an artifact of statistical noise.

The committee appointed by the NRC to conduct the new graduate-school study wants to avoid this “spurious precision problem.” They’ve adopted some jazzy statistical methods—mainly a technique called resampling—to model the uncertainty in the data, and they’ve also decreed that the results will be presented differently. There will be no sorted master list showing overall ranks in descending order. Instead the programs in each discipline will be listed alphabetically, and each program will be given a range of possible ranks. For example, a program might be estimated to rank between fifth place and ninth place. Let’s call such a range of ranks a rank-interval, and denote it {5, 6, 7, 8, 9} or {5–9}.

For a hypothetical set of 10 institutions, A through J, here’s what a set of rank-intervals might look like.

Acknowledging the uncertainty in your findings is commendable. But let’s be realistic. If you actually want to make use of these results—for example, if you’re a student choosing a grad-school program—the first thing you’re going to do is sort those bars into some sort of rank order, trying to figure out which school is best and how they all stack up against one another. In other words, you’re going to undo all the elaborate efforts the NRC committee has put into obscuring that information.

Below is one possible ordering of the bars. I have sorted first on the top of the rank-intervals, then, if two columns have the same top rank, I’ve sorted on the bottom rank. Other sorting rules give similar but not identical results. For example, sorting on the midpoints of the intervals would interchange columns B and F.

Question 1. Does sorting a set of rank-intervals by one of these simple rules yield a consistent and meaningful total ordering of the data? To put it another way, can you trust this attempt to reconstruct a ranking?

I hasten to add that this is not really a practical question about finding the best grad school. If you’re facing such a choice in real life, the NRC rank-intervals are not the only available source of information. But, for the sake of the mathematical puzzle, let’s pretend that all we know about schools A through J is embodied in those ranges of rankings.

It turns out that rank-intervals have some fairly peculiar behavior. Ranges of ratings are not a problem. If the NRC merely gave each school a fuzzy rating on the 0-to-5 scale, no one would have much trouble interpreting the results. But when you turn fuzzy ratings into fuzzy rankings, there are hidden constraints. For example, not all sets of rank-intervals are well-formed.

The set at left is impossible because there’s no one in last place. (We can’t all be above average.) The example at right is also nonsensical because D has no ranking at all. For a set of rank-intervals to be valid, there has to be at least one entry in each row and each column.

That’s a necessary condition, but not a sufficient one, as the two graphs below illustrate.

Do you see the problem with the example at left? Column B has a rank-interval of {1–2}, but in fact B can never rank first because A has no alternative to being first. The case at right is conceptually similar but a little subtler: If B is ranked third, then either first place or second place will have to remain vacant.

The underlying issue here is the presence of constraints or linkages within a set of rankings. Suppose you have calculated ratings and rankings of several schools, and then some new information turns up about one school. You can change the rating of that school without any need to adjust other ratings, but not so the ranking. If a school goes from third place to fourth place, the old fourth-place school has to move to some other rung of the ladder, and somebody has to fill the vacancy in third place. These interdependencies are obvious in a non-fuzzy ranking, but they also exist in the fuzzy case. You can’t just assign arbitrary rank-intervals to the items in a set and assume they’ll all fit together. This observation leads to a second question:

Question 2. What are the admissible sets of rank-intervals? How do we characterize them?

I have a partial answer to this question. It goes like this. Any ranking of k things must be a permutation of the integers from 1 through k. A permutation can be embodied in a permutation matrix—a square k × k matrix in which every row has a single 1, every column has a single 1, and all the other entries are 0. For example, here are the six possible 3 × 3 permutation matrices:

They correspond to the rankings (1, 2, 3), (1, 3, 2), (2, 1, 3), (3, 1, 2), (2, 3, 1) and (3, 2, 1).

Since a permutation matrix represents a specific (non-fuzzy) ranking, we can build up a set of rank-intervals by taking the OR-sum of two or more permutation matrices. What do I mean by an OR-sum? It’s just the element-by-element sum of the matrices using the boolean OR operator, ∨, instead of ordinary addition. OR has the following addition table:

                      0 ∨ 0 = 0
                      0 ∨ 1 = 1
                      1 ∨ 0 = 1
                      1 ∨ 1 = 1

For the first two 3 × 3 matrices shown above the arithmetic sum is:

whereas the OR-sum looks like this:

Every valid set of rank-intervals must correspond to an OR-sum of permutation matrices, simply because a set of rank-intervals is in fact a collection of permutations. The converse also holds: Any OR-sum of permutation matrices yields an admissible set of rank-intervals. Thus the OR-sums of permutation matrices—let’s call them ormats for brevity—are in one-to-one correspondence with the admissible sets of rank-intervals. (There’s just one catch when applying this idea to the NRC study. The columns of an ormat may well have “gaps,” as in the column pattern (0 1 1 0 0 1 1), which corresponds to the rank-interval {2–3, 6–7}. Will the NRC allow such discontinuous ranges in their grad-school assessments? Perhaps the issue will never come up in practice. In any case, I’m ignoring it here.)

Arithmetic sums of permutation matrices form an open-ended, infinite series; in contrast, there are only finitely many distinguishable OR-sums. The reason is easy to see: Ormats have k² entries, each of which can take on only two possible values, and so there can’t be more than \(2^{k^{2}}\) distinct matrices. Because of the various constraints on the arrangement of the entries, the actual number of ormats is smaller. For example, at k = 3 the \(2^{k^{2}}\) upper bound allows for 512 ormats, but there are only 49:

Thus we come to the next question.

Question 3. For each k ≥ 1, how many distinct ormats can we build by OR-ing subsets of k × k permutation matrices? Is there a closed-form expression for this number?

I have answers only for puny values of k.

   k       upper bound        # of ormats  
   1                 1                  1
   2                16                  3
   3               512                 49
   4            65,536              7,443
   5        33,554,432          6,092,721
   6    68,719,476,736                  ?

The tallies of ormats were calculated by direct enumeration, which is not a promising approach for larger k. (I note—to spare folks the bother of looking—that the sequence 1, 3, 49, 7443, 6092721 does not yet appear in the OEIS.)

To extend this series, we might try to exploit the internal structure and symmetries of the ormats. By sorting the columns and rows of the matrices, we can reduce the 49 3×3 ormats to just six equivalence classes, with the following exemplars:

Enumerating just these reduced sets of matrices should make it possible to reach larger values of k, but I have not pursued this idea. (Furthermore, the two-dimensional sorting of matrices looks to be a curiously challenging task in itself.)

By the way, I think the number of ormats will approach the \(2^{k^{2}}\) upper bound asymptotically as k increases. Many of the features that disqualify a matrix from ormathood—such as all-zero rows or columns—become rarer when k is large. I have tested this conjecture by generating random (0,1) matrices and then counting how many of them turn out to be ormats.

For k = 1 through 5 the results are in close agreement with the actual counts of ormats, and up to k = 10 the trend is clearly upward. But continuing this inquiry to larger values of k will depend on a positive answer to the next question.

Question 4. Given a square matrix with (0,1) entries, is there an efficient algorithm for deciding whether or not it is an OR-sum of permutation matrices, and thus an admissible set of rank-intervals?

The question asks for a recognition predicate—a procedure that will return true if a matrix is an ormat and otherwise false. If efficiency doesn’t matter, there’s no question such an algorithm exists. At worst, we can generate all the k × k ormats and see if a given matrix is among them. But that’s like saying we can factor integers by producing a complete multiplication table. It just won’t do in practice. Isn’t there a quick and easy shortcut, some distinctive property of ormats that will let us recognize them at a glance?

If we could replace the OR-sum with the ordinary arithmetic sum, the answer would be yes. Permutation matrices have the handy property that all rows and columns sum to 1. An arithmetic sum of r permutation matrices has rows and columns that all sum to r. (It is a semi-magic square.) The converse is also true (though harder to prove): If a matrix of nonnegative integers has rows and columns that all sum to r, it is a sum of r permutation matrices. This fact yields a simple test: Sum the rows and the columns and check for equality.

Unfortunately, the trick won’t work for ormats, because the boolean OR operation throws away even more information than summing does. Because 0 ∨ 1 = 1 ∨ 0 = 1 ∨ 1, infinitely many sets of operands map into the same result, and there’s no obvious way to recover the operands or even to determine how many permutation matrices entered into the OR-sum.

Maybe there’s some other clever trick for recognizing ormats, but I haven’t found it. Let me make the question more concrete. Below are three (0,1) square matrices. Two of them are ormats but the third is not. Can you tell the difference?

If it’s so hard to recognize an ormat, how did I count the ormats among a bunch of randomly generated (o,1) matrices? By hard work: I reconstructed the set of permutations allowed by each matrix. Visualize a permutation as a path threading its way through the matrix from left to right, connecting only non-zero elements and touching each column and each row just once. When you have drawn all possible permutation paths, check to see if every non-zero element is included in at least one path; if so, then the matrix is an ormat. Note that this is not an efficient recognition procedure. In the worst case (namely, an all-ones matrix), there are k! permutations, so this method has exponential running time. But k! is better than \(2^{k^2}\); and, besides, for sparse matrices the number of permutations is much smaller than k!. The 10 × 10 matrix presented as an example at the start of this post gives rise to 580 permutations, a manageable number. Here’s what they look like, plotted as a spider web of red paths across the bar chart.

Every nonzero site is visited by at least one permutation path, so this set of rank-intervals is indeed valid.

This process of lacing permutations through a matrix finally brings me back to Question 1, about how to make sense of the NRC’s fuzzy ranking scheme. Let’s take a small example:

Examining the graph above shows that A must rank either first or second—but which is more likely? In the absence of more-detailed information, it seems reasonable to assume the two cases are equally likely; we assign them each a probability of 1/2. Similarly, B has the rank-interval {1–3}, and so we might suppose that each of these three cases has probability 1/3. Continuing in the same way, we assign probabilities to every element of the matrix.

But wait! This can’t be right; our probabilities have sprung a leak. Any proper set of probabilities has to sum to 1. Our procedure assures that each column obeys this rule, but there is no such guarantee for the rows. In row 1, we’re missing one-sixth of our probability, and in row 2 we have an excess of 1/2; row 4 comes up short by 1/3.

Is there any self-consistent assignment of probabilities for the elements of this matrix? Sure. As a matter of fact, there are infinitely many such assignments, including this one:

I’ll return in a moment to the question of how I plucked those particular numbers out of the air, but note first what they imply about the ranking of items A through D. For item A, with the rank-interval {1–2}, the odds are two-to-one that it ranks first rather than second. B has the behavior we expected from the outset, with probability uniformly distributed over the three cases. But if you pick either C or D, each with the rank-interval {2–4}, your chance of getting second place is only 1/6, and half the time you’ll be in last place.

Where do these numbers come from? Instead of starting with the assumption that probability is uniformly distributed over each rank-interval, assume that each possible permutation of the ranks is equiprobable. For this matrix there are six allowed permutations: (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (2, 1, 3, 4) and (2, 1, 4, 3). Observe that four of the six ordering put A first, and only two permutations place A second. We can also tally up such “occupation numbers” for all the other matrix elements:

Dividing these numbers by the total number of permutations, 6, yields the probabilities given above.

We can do the same computation for the 10 × 10 example matrix, which turns out to allow 580 permutations:

If you care to check, you’ll find that each column and each row sums to 580; dividing all the entries by this number yields a probability matrix with columns and rows that sum to 1 (also known as a doubly stochastic matrix).

This process of tabulating permutation paths recovers some of the information we would have gotten from the arithmetic sum of the permutation matrices—information that was lost in the OR-ing operation. But we get back only some of the information because we have to assume that each permutation included in the OR-sum appears only once. (This is just another way of saying that the allowed permutations are equiprobable.) There’s no particularly good reason to make this assumption, but at least it leads to a feasible probability matrix.

Is there any way of calculating the entries in the doubly stochastic matrix without explicitly tracing out all the permutation paths? I’m sure there is. I think the construction of the matrix can be approached as an integer-programming problem, and perhaps through other kinds of optimization technology. What seems less likely is that there’s some simple and efficient shortcut algorithm. But I could be wrong about that; there’s a lot of mathematics connected with this subject that I don’t understand well enough to write about (e.g., the Birkhoff polytope). I hope others will fill in the gaps.

Getting back to the assessment of grad schools—have we finally found the right way to understand those rank-intervals that the NRC promises to publish any day now? My sense is that a semi-magic square (or, equivalently, a doubly stochastic matrix) will give a less-misleading impression than a simple eyeball sorting on the spans or midpoints of the rank-intervals. But what a lot of bother to get to that point! How many prospective grad students are going to repeat this analysis?

Acknowledgment: Thanks to Geoff Davis of PhDs.org for introducing me to this story. PhDs.org will have the new ratings as soon as the NRC releases them, and may even find a way to make them intelligible! Disclaimer: I’ve done paid work for the PhDs.org web site (but this is not a paid endorsement).

Update 2010-07-27: If you’ve gotten this far, please read the comments as well. A number of commenters have provided important insights and context, which have helped me understand what’s going on in the matrices I’ve been calling ormats. But I’m still a bit murky about the best way to recognize and count them. I’m not sure that publishing my still-murky thoughts is terribly helpful, but maybe someone else will read what follows and give us a dazzling, gemlike synthesis.

For the ormat-recognition problem (Question 4 above), three basic approaches have been mentioned: enumerating the permutation paths through the matrix, examining matrix minors, and looking for perfect matchings in a bipartite graph defined by the matrix. It seems to me that all of these methods are doing the same thing.

Start with Barry Cipra’s method of minors. The basic operation is to choose a nonzero matrix element, then delete the row and the column in which that element occurs. You then apply the same operation to the remaining, smaller matrix.

In tracing permutation paths, we’re looking for sequences of nonzero elements, drawing one element from each column and each row. A way of organizing this search is to choose a nonzero element and then, after recording its location, delete the corresponding column and row, so that no other elements can be chosen from that column or row.

In the method based on Hall’s theorem, as explained by John R., we view the ormat as the adjacency matrix of a bipartite graph, where every nonzero element designates an edge connecting a row vertex to a column vertex. To find a matching, we delete an edge, along with the two vertices it connects (and also all the other edges incident on those vertices). Then we recurse on the smaller remaining graph. (See further update below.) If you translate this operation on the graph back into the language of matrices, deleting an edge and its endpoints amounts to deleting a row and a column of the adjacency matrix.

I am not asserting that these three algorithms are all identical, but they all rely on the same underlying operation. To say more, we would need to consider the control structure of the algorithms—how the basic operations are organized, how the recursion works, all the details of the bookkeeping. I don’t trust myself to make those comparisons without trying to implement the three methods, which I have not yet done. However, at this point I just don’t see how any method can guarantee correct results without something resembling backtracking (or else exhaustive search through an exponential space). After all, we’re not looking for just one matching in the graph, or one decomposition into matrix minors, or one permutation path; we have to examine them all.

Here’s a further hand-wavy argument for the essential difficulty of the task. For a (0,1) matrix, the number of permutation paths that avoid all zero entries is equal to the permanent of the matrix. Computing the permanent of such a matrix is known to be #P-complete.

Update 2010-07-31: With lots of help from my friends, I think I finally get it. Although there could be as many as k! permutation paths in a k × k matrix, you don’t need to examine all of the paths to decide whether or not the matrix is an ormat. It’s enough to establish that one such path passes through each nonzero element. This is what the algorithm based on Hall’s theorem does. As Frans points out in a comment below, I misunderstood the essential nature of that algorithm (in spite of having it explained to me several times). There is no recursive deconstruction into progressively smaller matrix minors; instead, we just loop over all the nonzero elements of the matrix, find the minor associated with each such element, then check for a perfect matching in the minor. (Still more refinements are possible—but already we have a polynomial algorithm.)

With this efficient recognizer predicate, it’s easy to measure the proportion of ormats in random matrices at larger values of k:

As expected, the fraction of ormats approaches 1 beyond about k = 20.

So much for identifying ormats. I am still unable to extend the series of exact counts beyond k = 5. The tabulations for random (0,1) matrices suggest that for k = 6 there should be about 20 billion ormats, and counting that high is just too painful. I need to work out the symmetries of the problem.

As far as I can tell, assigning exact probabilities to the nonzero matrix elements requires a full enumeration of all the permutation paths, and thus a calculation equivalent to the permanent. There may be a useful approximation.

Barry Cipra asks a really good question: The permanent tells us the maximum number of permutations that could possibly be included in a given ormat, but what is the minimum number? A naive upper bound is the number of 1s in the matrix, but I don’t see an easy path to an exact count. But enough for now.

The school of philosophy called Antipodianism briefly flourished on the fringes of the Hellenistic world more than 2,000 years ago. The sect held that every person has an opposite number, a mirror image who inverts all our beliefs, feelings, actions and attitudes. If I smile, my antipodian counterpart frowns; when I wake, she sleeps. If I’m a Mac, she’s a PC. For every liberal Democrat there’s an antipodian Tea Party Republican. In this way the universe is held in balance. It’s an enforced equilibrium, which none of us has the power to upend, hard as we might try.

The earliest of the Antipodians believed that every such matched pair (commonly designated A and ∀) live at diametrically opposite points on the surface of the earth. This arrangement ensures that A and ∀ can never meet—thereby averting a cosmic catastrophe. A later quantum-field version of Antipodianism relaxed the geographic constraint by allowing for the creation and annihilation of A∀ pairs, but that idea never really caught on.

One day an Antipodian master was teaching an exchange student from New Zealand. The child was crafty.

“Is it not true,” she asked, “that A and ∀ always do the opposite thing?”

“Yes, antisymmetry demands it,” the master replied.

“If A walks north, ∀ must walk south?” the child asked.

Again the master assented.

“If A goes east, ∀ must go west?”

“Yes.”

“If A turns to the right, ∀ must turn to the left, no?”

The master agreed, although he sensed trouble coming.

“I’m afraid the universe is out of joint,” said the child. “If A goes north and turns to the right, while ∀ goes south and turns to the left, afterwards they are both walking east. They are doing the same thing.”

Needless to say, this was a moment of crisis in Antipodian doctrine. The Pythagoreans, you may recall, resolved a similar impasse by resorting to violence. When some upstart challenged their precept that “all is number” by showing that no known number can be the square root of 2, the Pythagoreans tossed the troublemaker out of the boat. But in this case the Antipodian master kept his calm.

“Ah my little Kiwi,” he said to the student. “You are clever but not wise. Your own statements refute your claim. Did you not begin by saying that A and ∀ always do the opposite thing? When A walks 10 paces north, ∀ walks 10 paces south. When A turns right, ∀ turns left. But now you would have us believe they both take a step forward, contradicting the most basic law of their nature. What really happens is that A walks forward and ∀ walks backward. Thus A goes eastward and ∀ westward, and all is well with the world.”

Through this brittle sophistry the master extricated himself from the classroom—though he may have had to walk backwards to make good his escape. He never taught again. The Kiwi student went on to a brilliant career studying the weak interactions of neutral K mesons. As for Antipodianism, it vanished without a trace.

Or maybe it left a tiny trace. I’ve never visited the antipodes, but I hear that corkscrews Down Under turn the other way.

Martin Gardner died over the weekend. He was 95 and living in Norman, Oklahoma, not too far from his birthplace in Tulsa.

Like many others, I grew up on Martin’s “Mathematical Games” column in Scientific American. Later I joined the staff of that magazine—but don’t imagine that Martin and I became office buddies. As a matter of fact, I never once saw him in the office. He worked at home. He attended none of our editorial meetings. We never had lunch together. Indeed, I never would have met him at all except for the coincidence that we lived a few blocks apart, and every now and then I would be called upon to deliver a package of urgent proofs. (By the way, his address in those days was on Euclid Avenue!)

Someone on the magazine staff described Martin as “a shy woodland creature,” and the tag stuck. Looking back, however, I think it tells only half the story. Yes, Martin was no schmoozer, and he preferred to stay out of the spotlight, both in person and in print. Most of his best-known columns reported on someone else’s discoveries—Conway’s game of life, RSA’s cryptosystem, Penrose’s tilings. He delighted in annotating other people’s work, as in his celebrated edition of Lewis Carroll. Yet he was anything but timid or retiring. In an argument, the shy woodland creature was a grizzly bear. He had strongly held opinions and philosophical convictions, and he knew the worth of his own work. He was a man of ideas, to be taken seriously, yet also a man who had fun with his ideas.

As a celebration of Martin’s peculiar genius, I would like to revive the little puzzle that formed the basis of his very first column, in January of 1957. (He had published a few articles in Scientific American earlier, but this was the first column to appear under the “Mathematical Games” title.)

On the bingo card above, choose any number, circle it, and cross out all the other numbers in the same column or row. Now select a second number from among those that remain unmarked, and again circle your choice and then cross out the rest of the column and row. Continue in this way until there are no unmarked numbers left to choose.

The sum of the circled numbers is 57. How did I know that? How did Martin construct the matrix?

Update 2010-05-29: Here is Martin’s own explanation of the 1957 puzzle:

Like most tricks, this one is absurdly simple when explained. The square is nothing more than an old-fashioned addition table, arranged in a tricky way. The table is generated by two sets of numbers: 12, 1, 4, 18, 0 and 7, 0, 4, 9, 2. The sum of these numbers is 57. If you write the first set of numbers horizontally above the top row of the square, and the second set vertically beside the first column [see Fig. 9], you can see at once how the numbers in the cells are determined. The number in the first cell (top row, first column) is the sum of 12 and 7, and so on through the square.

You can construct a magic square of this kind as large as you like and with any combination of numbers you choose. It does not matter in the least how many cells the square contains or what numbers are used for generating it. They may be positive or negative, integers or fractions, rationals or irrationals. The resulting table will always possess the magic property of forcing a number by the procedure described, and this number will always be the sum of the two sets of numbers that generate the table.

Fred Gruenberger may well have been the first blogger on computational topics. When he was writing, back in the 1970s, there was no RSS, and so he distributed his musings in a monthly newsletter called Popular Computing. A typical issue was 16 or 20 typewritten pages–stapled, folded, stamped and delivered by mail. It was always worth reading.

Gruenberger had been working and playing with computers since the 1940s. For a long stretch he was at the RAND Corporation, the famous think tank in Santa Monica. Later he taught at Cal State Northridge. In addition to Popular Computing he was involved in the startup of Datamation magazine and published at least a dozen books. I haven’t been able to learn much about his later years; he died in 1998.

A slogan that appeared in some issues of Popular Computing proclaimed: “The way to learn computing is to compute.” I took this advice to heart, although I was hampered by a total lack of hardware. Later on I acquired a programmable calculator, which helped on some of the problems and exercises.

The problem reproduced above appeared in the December 1976 issue of Popular Computing (Vol. 4, No. 12). At the time, I made no attempt to work this one out, but evidently the problem seemed interesting enough to be worth filing away. When I came upon the old clipping recently, I gave it a closer look and realized I have no idea how to answer Gruenberger’s question, though the impediment now is not lack of hardware.

Gruenberger asks us to trace a planar path whose steps are indexed by the odd integers starting at 3. For each number N we turn right 90 degrees before taking a step if N is a prime congruent to 1 mod 6; we turn left 90 degrees before moving one unit if N is a prime congruent to −1 mod 6; otherwise we continue straight ahead in whatever direction we happen to be facing.

In his typewriter graphics, Gruenberger plotted the trajectory from N=3 through 97. Below I continue the path through N=199.

But something’s amiss here. Gruenberger wrote:

Eventually the path will cross itself, so that the cell containing 111 will also contain 147. Similarly, one cell will contain both 91 and 179.

Those two self-intersections are nowhere to be found in the diagram. When I first noticed this discrepancy, I assumed I must have made a mistake somewhere. (This eagerness to blame myself is not mere knee-jerk humility; I have years of experience to back it up.) Eventually, though, I concluded that it was Gruenberger who had made the wrong turn. I believe he mistakenly went left at 127, as shown in the brown trail below:

The brown continuation of the red path includes the two coincidences mentioned in Gruenberger’s problem statement. But the left turn at N=127 is incorrect, because 127 is a prime equal to (6×21)+1, and thus it should specify a right turn. The error is of no great consequence, but it does reveal something interesting: Gruenberger must have been plotting these paths by hand. Most likely he wrote a program to compute the series of residue classes, then traced out the trajectory on squared paper.

Setting aside this anomaly, Gruenberger was quite right that the path does intersect itself. Here’s the trail continued through N=1,001:

And if that’s not tangled enough, here’s what it looks like at N=10,001:

Gruenberger asks for “a list of the contents of those cells containing more than one number, arranged in the order of the smallest number in the cell.” It’s not hard to identify some cells that belong on such a list. The table below includes all multiply-occupied cells discovered when tracing the path up to N=1,001, sorted as Gruenberger requests:

                   x    y    values of N
                 -11   28    (137 337)
                 -15   27    (147 683)
                 -16   27    (149 349 685)
                 -18   26    (155 355)
                 -19   27    (159 691)
                 -19   28    (161 693)
                 -19   29    (163 695)
                 -17   31    (171 319)
                 -18   32    (175 315)
                 -19   32    (177 701)
                 -20   32    (179 703)
                 -22   31    (185 769)
                 -23   31    (187 771)
                 -24   31    (189 773)
                 -30   41    (245 269)
                 -30   42    (247 271)
                 -27   40    (281 733)
                 -26   40    (283 735)
                 -26   37    (289 725)
                 -23   35    (299 715)
                 -22   35    (301 761)
                 -21   35    (303 759)
                 -20   35    (305 757)
                 -17   27    (351 687)
                 -18   27    (353 689)
                 -17   24    (361 673)
                 -16   24    (363 675)
                 -15   24    (365 677)
                 -17   21    (379 667)
                 -17   22    (381 669)
                 -17   23    (383 671)
                 -20   22    (391 631)
                 -20   21    (393 633)
                 -20   20    (395 635)
                 -20   19    (397 637)
                 -22   19    (401 593)
                 -22   18    (403 591)
                 -22   17    (405 589)
                 -22   16    (407 587)
                 -27   15    (419 575)
                 -27   14    (421 573)
                 -28   14    (423 819)
                 -29   14    (425 549)
                 -32   14    (431 539)
                 -32   13    (433 537)
                 -26   10    (563 831)
                 -26   11    (565 829)
                 -27   13    (571 823)
                 -28   18    (607 811)
                 -22   32    (707 767)
                   4   -6    (923 971)
                   4   -7    (925 969)
                   4   -8    (927 967)
                   4   -9    (929 989)
                   5   -9    (931 991)

Is this list the answer to Gruenberger’s question? No, it’s not, because there’s no reason to stop at an arbitrary limit such as N=1,001. Indeed, the list above is not even a prefix of the complete answer. The smallest value of N appearing in the list is 137, but the trail will eventually revisit cells occupied by smaller values of N. For example, continuing the experiment to N=10,001 reveals a bunch of intersections quite close to the beginning of the path, including a site that’s visited five times:

                   x    y    values of N
                   1    0    (5 1621)
                   1    1    (7 1623)
                   2    1    (9 4725)
                   3    1    (11 1263)
                   3    2    (13 1265)
                   5    3    (19 1635)
                   6    3    (21 1637)
                   7    4    (25 7537)
                   7    5    (27 7319 7539)
                   7    6    (29 7505 7541)
                   6    6    (31 1643 7323 7503 7543)
                   6    7    (33 1645 7325)
                   6    8    (35 1647 7327)
                   6    9    (37 1649 7329)

One point still missing from this list is the origin–the site at x=0, y=0, N=3. Does the path ever revisit its starting point? If so, at what value (or values) of N does it come back home? Since I don’t know the answer to this question, I guess I’ll have to leave it as an exercise for the reader.

I suspect that the problem Gruenberger meant to pose (or thought he was posing) was to generate a list of self-intersection sites arranged in their natural order of occurrence–that is, the order in which the crossings are created when you construct the path starting from the origin. This natural-order list is not at all the same as a list “arranged in the order of the smallest number in the cell.” The natural-order list is easy to generate step by step. All you need to do is obey the left/right/straight rules, plot the resulting sequence of positions on the xy lattice, and leave behind a trail of breadcrumbs so you can check at each step to see if the site has been visited before. This task is a matter of straightforward computation–just the kind of assignment that Gruenberger favored. The natural-order list begins:

                   x    y    values of N
                 -30   41    (269 245)
                 -30   42    (271 247)
                 -18   32    (315 175)
                 -17   31    (319 171)
                 -11   28    (337 137)
                 -16   27    (349 149)
                 -18   26    (355 155)
                 -32   13    (537 433)
                 -32   14    (539 431)
                 -29   14    (549 425)
                 -27   14    (573 421)

Thus the prime path first crosses itself when N=269, a value that shares the same coordinates as N=245, namely x=−30, y=41. There are 56 such crossings up to N=1,001, and 112,988 self-intersections up to N=10⁶.

*     *     *

There is a wilder, conjectural answer to Gruenberger’s challenge–which I’m pretty sure he did not have in mind. It goes like this: Maybe the complete list of revisited values of N is simply the list of all N. In other words, maybe the Gruenberger prime path fills up the entire lattice of integers, crossing over itself everywhere many times.

In 1921 George Pólya published a celebrated proof that a random walk on the lattice of integers is recurrent in one or two dimensions, though not in higher dimensions. Recurrent means that the walk returns to each point along its length with probability 1, and indeed visits every point in its domain infinitely often. Is it possible that the prime path is also recurrent?

Pólya’s theorem is one of those mind-expanding results that seem impossible on first acquaintance, and then inevitable, and finally just so amazing that you want to go kiss a mathematician. I have to confess that I’ve never gotten all the way through Pólya’s original paper (it’s not long, but it’s in German). On the other hand, I can highly recommend a little book by Peter Doyle and Laurie Snell, Random Walks and Electric Networks, which gives several alternative proofs of the theorem; it was published in the MAA’s Carus Monograph series, and there’s a postprint available on the arXiv.

The key insight underlying Pólya’s result, as I understand it, is this: If you never revisit a former home, then you must be spending eternity somewhere else, and you can do that only if your universe has enough somewhere elses that you’ll never run out of new territories to visit. Suppose that, some eons after starting your journey, you find yourself at distance r from the origin. If you’re living in a one-dimensional universe, then there are just two places you could be at that moment, namely at +r or −r. It doesn’t matter how far you run; there are still just two points at any given distance from the origin. In two dimensions, a fugitive at distance r has a little more room to maneuver; the number of available points grows in proportion to r, forming a circle of radius r. But this is still not enough room to get lost in. Only in three dimensions or more is there a nonzero probability of escape. In three dimensions, the space available at radius r is proportional to r². In this three-dimensional world, the volume of empty space grows faster than a random walker’s expected distance from home.

What does all this have to do with Gruenberger’s prime path? Well, it’s no secret that the distribution of prime numbers looks convincingly random–if you look at it in just the right way. And in particular the distribution of primes in various residue classes, such as 6K+1 and 6K−1, seems to behave at least approximately like a random variable. All this suggests we might consider viewing the Gruenberger prime trail as if it were a random walk through the two-dimensional lattice of integers. Because the space is two-dimensional, it’s a good guess that the walk should be recurrent.

The original recurrence results of Pólya refer to a simple random walk, where at each step the walker chooses randomly among the available directions and then moves one unit in that direction. For example, in the two-dimensional lattice of integers there are four possible directions: north, south, east, west. The simple random walk is not the best model of the Gruenberger process, which is more like a nonreversing random walk–a path where on each step the walker can turn left or turn right or go straight ahead but can never make a 180-degree about-face. We can further refine the random-walk model of the Gruenberger process by biasing the choice made at each step to reflect the changing abundance of prime numbers. Primes grow scarcer as their magnitude increases; in the vicinity of a given value of N, the probability that a randomly chosen number is prime is approximately 1/log N. Since the Gruenberger path goes straight for all composite numbers and turns only when N is prime, the trail will have longer and longer straight segments, and rarer turns, as N increases. A random walk can mimic this behavior by choosing an action at each step according to this logic:

    if random(1.0) > 2/log(N)
       then go straight
       elseif randomboolean()
           then turn left
           else turn right

(The proportion of primes is given as 2/log(N) rather than 1/log(N) because the Gruenberger process is defined on odd numbers only, which immediately eliminates half of the composites.)

One way to compare the various kinds of random walks is to measure the root-mean-square displacement–the distance from the origin to the final position of the walker, averaged over many realizations of the random process. For a simple random walk, the RMS displacement for an N-step walk converges to \(\sqrt{N}\); for the nonreversing random walk the average displacement is \(\sqrt{2N}\). The biased random walk based on the distribution of primes also appears to yield an RMS distance proportional to the square root of the number of steps; numerically the curve looks something like \(\sqrt{10N}\). I’m not entirely sure that’s the true form of the curve, but the geometric details don’t really make much difference. If I understand correctly, all three of these random processes should be recurrent in the sense of Pólya.

Does the same reasoning apply to the Gruenberger prime path? There are two sides to this question.

The naysayer points out that Pólya’s theorem applies to random walks, but there’s nothing truly random about the sequence of primes. After all, we have a straightforward, deterministic algorithm for generating primes, as well as an efficient algorithm for testing whether any given integer is prime or composite. The essence of a random process is that every time you run it you get a different result, but there’s only one sequence of prime numbers, and so the Gruenberger prime path will come out exactly the same every time. According to this view of things, the kind of probabilistic reasoning that goes into the proof of Pólya’s recurrence theorem is out of bounds here. For randomness to make any sense, you need to average over some ensemble of independent instances. For example, you could average over the 50 salmon-pink paths in the graph below, which represent 50 independent realizations of a biased random walk; you can’t average over the prime path itself (green), because there’s only that one path.

The yeasayer retorts that a single path is all you need–if the path is infinitely long. Indeed, the salmon-colored trails above could be interpreted not as 50 distinct runs of a random process but as 50 segments of a single long path, which repeatedly loops around through the point at x=0, y=0, wanders off in various directions, and then comes back home yet again. In essence, everything that could possibly happen in an infinite set of random paths happens somewhere within a single infinite path; all possible variety is already present there.

I’m not sure how to settle this dispute between Dr. Yea and Professor Nay. When an argument hinges on the nature of randomness, the meaning of infinity and patterns in the distribution of the primes, I known I’m in over my head.

So I’ll leave that deep question unresolved and say a final word about a lesser curiosity. In the Gruenberger process, we’re using the congruence classes of prime numbers mod 6 as a kind of coin flip to decide which way to turn. Is it a fair coin flip? For small values of N, it certainly doesn’t look fair:

                               6x+1      6x−1
       primes <     100         11        12
       primes <    1000         80        86
       primes <   10000        611       616
       primes <  100000       4784      4806
       primes < 1000000      39231     39265

There’s a persistent excess of −1 primes, and the imbalance seems to be getting steadily larger. As a result, the prime path has a “winding number” that reaches 8.5 at N=10⁶; that is, the path makes eight and a half net counterclockwise revolutions. Does the windup continue with still larger N? I gather that the definitive answer is “Yes and No.” For more see the masterful paper by Andrew Granville and Greg Martin cited above.

[Correction 2010-02-19: reflected the accent on Pólya.]

Four colors suffice for any planar map: We’ve known that since 1977. If a map is divided into countries or provinces or other regions, and you want to color the map so that no two adjacent regions have the same color, you’ll never need more than four crayons. But there are a couple of definitions that have to be accepted if this theorem is to hold. First, “adjacent” means that two regions share a boundary segment, not merely a point or a discontinuous set of points. Second, a “region” has to be a connected area, so that you can reach any point in the interior from any other such point without crossing a boundary.

A few days ago the strange and wonderful Strange Maps blog called attention to this map of the Principality of Liechtenstein:

(The map comes from the Wikimedia Commons Atlas of Liechtenstein, which has a larger image.)

It seems that Liechtenstein is divided into 11 communes, which emphatically do not satisfy the connectivity requirement of the four color map theorem. Just four of the communes consist of a single connected area (Ruggell, Schellenberg and Mauren in the north, and Triesen in the south). All the rest of the communes have enclaves and/or exclaves. (I confess that I didn’t know the distinction between these words until yesterday. They make a nice pair.) The most fragmented commune is Vaduz, which includes the principality’s capital. Vaduz consists of six isolated pieces; the smallest is a sliver about a kilometer northeast of the town of Planken.

In the map above, each commune is assigned its own color, and so we have an 11-coloring. It’s easy to see we could make do with fewer colors, but how many fewer? I have found a five-clique within the map; that is, there are five communes that all share a segment of border with one another. It follows that a four-coloring is impossible. Is there a five-coloring? What is the chromatic number of Liechtenstein?