Ages ago (in blog years) I mentioned some algorithmic ideas for getting passengers aboard airplanes faster, based on a 2005 paper by Steven Skiena and others. Since then, the queue at the departure gate has only gotten longer. Now another preprint on the same theme has landed in the arXiv. This one is by Jason H. Steffen, a postdoc at Fermilab.

Steffen assumes that the main impediment to speedy boarding is the time passengers need for stowing their carry-on luggage. He argues that the loading process will go faster if we make sure everyone has plenty of elbow room for cramming their wheely-bag into the overhead bin. Thus he favors boarding-line sequences generated by the following rule: If two passengers are seated near each other in the aircraft (in the same row or in adjacent rows), then they should not be adjacent in the queue.

I don’t necessarily agree with Steffen’s premise or his conclusion, but I have no evidence of my own to report, so let’s set that issue aside. I’m intrigued by a related, subsidiary question. If we assume that there is some optimal ordering for passengers as they enter the airplane, how do we organize the unruly and impatient mob at the departure gate so that everyone enters the plane in the specified order? Here are a few ideas.

Boarding Hats. Most airlines now use some kind of zone system, where the passengers are divided into several groups. As boarding time approaches, people mill around near the gate asking, “Have they called Group 2?” or “Is this the line for Group 4?” To achieve finer-grain control over boarding order, we would need larger numbers of smaller groups, which would make the process of finding the right group even more cumbersome. In the limiting case, each passenger would be assigned an individual boarding-sequence number, and the passengers would have to sort themselves into the correct sequence. People are actually rather good at this task, given enough information. When I was a schoolboy, my classmates and I could quickly line ourselves up in order of height, relying on an efficient parallel sorting algorithm. But that method works so well mainly because height is a visible trait. To bring to same efficiency to sorting passengers at the departure gate, the boarding sequence number must be as readily discernible as height. Thus I propose replacing the traditional boarding pass with the boarding hat, which has your number prominently printed on all sides. This innovation would be a special treat for the mathematical community, given the well-known genre of puzzles about mathematicians who can see the number on everyone else’s forehead but not their own.

The Boarding Buzzer. If you think a numbered paper hat is too undignified for airline passengers, here’s another replacement for the boarding pass. When you check in for a flight, suppose you get an electronic gadget like one of those buzzers that restaurants hand to customers who are waiting for a table. As I imagine the boarding buzzer, it has various blinking lights and sound effects and a display screen that counts down the minutes remaining until you are due to report to the gate. The time shown on the display is different for each passenger and is calculated to get everyone on board at just the right moment. When I first thought of this scheme, I dismissed it as preposterous technological excess. But when I told a friend about it, she said I shouldn’t blog it; I should patent it. Obviously I haven’t taken my friend’s advice, and so when I check in at an airport a few years from now and the agent hands me one of these contraptions, I’m going to be mightily annoyed to see that someone else has cashed in on my idea. Still, the device could have certain charms. It would allow you to wander throughout the airport rather than remain tethered to the departure lounge. If a flight were delayed or shifted to a different gate, the airline could notify you right away. Likewise, if you were on standby, you could be paged when a seat opened up.

Out-of-Order Execution. The problem of dealing with suboptimal sequences of events is familiar to designers of computer hardware. Many modern microprocessors analyze the stream of instructions awaiting execution and reorder them to improve throughput. If the next instruction in the stream can’t be executed immediately because its operands aren’t yet available, then maybe some other instruction can take its place. This principle could also be applied to airplane boarding. As passengers enter the jetway, their boarding passes are scanned, and so their actual order in the queue is known from that point forward. Suppose there were a small buffer area at the other end of the jetway, near the aircraft door, along with a display screen where passenger names could be listed. This scheme would allow groups of passengers to be rearranged at the last minute to avoid bottlenecks. The overall boarding order might not be ideal, but it could be locally optimized.

First Come, First Served. A few airlines have abolished seat assignments altogether: You line up at the gate, file onto the airplane, and take any unoccupied seat you choose. In my experience, the boarding process on open-seating flights is generally quick and efficient. But the protocol creates an incentive to be at the head of the queue, and so people start lining up at the gate quite early. Thus the airline gets the benefit of faster loading, but the passengers likely spend more time waiting in line.

The Worst of Both Worlds. Here’s an idea so bad I hesitate even to mention it, lest some airline decide to try it. Suppose all seats are assigned, but you don’t receive your assignment when you book a flight or when you check in at the airport. Instead the assignment is made as you hand in your boarding pass at the gate. This allows the airline to parcel out the seats in whatever order will optimize the boarding process, but it leaves the passengers with little or no control over where they sit. (After long observation you might figure out something about the assignment algorithm and thereby learn where not to stand in line.)

A final thought about luggage: If Steffen is right that carry-on baggage is the main cause of delay, some other tactics might be considered. What if passengers without carry-on bags were allowed to board first? By assumption they would board quickly, relieving congestion for the heavily laden crowd to follow. The policy might also induce some passengers to carry less luggage.

Then there’s the Russian-made aircraft I flew on once, many years ago. You reached the passenger cabin by walking through a lower deck lined with luggage racks, dropping off your bag on the way in and grabbing it on the way out. Probably preferable to wearing a numbered hat or carrying a buzzer.

Very likely you already know how to count, but let’s review anyway. The usual counting sequence for the natural numbers starts 1, 2, 3, 4, 5, … and goes on for quite some time. Some people prefer to start 0, 1, 2, 3, 4, 5, …, but they wind up in the same place at the end. (In general I side with the nullists who count from nothing, but today I find it convenient to join the unitarians: In what follows the least natural number is 1.)

Here’s a computer program for counting out the numbers in their standard sequence:

n = 1
do forever
   print n
   n = n + 1

The last line of this program defines a successor function: For every possible value of n, it names the next n. Since the program starts with n=1 and iterates the successor function forever, every natural number appears exactly once in the output.

What if we want to arrange the natural numbers in some other order, perhaps starting with a value other than 1? For example, we might want to count 2, 1, 4, 3, 6, 5, 8, 7, …. Altering the program to generate this sequence requires only minor adjustments:

n = 2
do forever
   print n
   if even(n)
      then n = n – 1
      else n = n + 3

How about listing all the odd numbers first, followed by all the even numbers: 1, 3, 5, …, 2, 4, 6, …? That seems to be a valid permutation of the natural numbers, but there’s something strange and troubling about the idea of counting this way. When we begin ticking off 1, 3, 5, …, it’s not at all clear how we’re ever going to finish the odd numbers so that we can get started on the even ones. I don’t know how to write a program to generate this complete series. On the other hand, the successor function for such a program is easy enough to describe: It’s just n = n + 2. (Do you doubt this statement? Well, I admit it makes me queasy too. But show me a value of n for which the function fails to produce the correct successor.)

Here’s another ordering of the natural numbers, which looks even weirder:

3, 5, 7, 9, …, 6, 10, 14, 18, …, 12, 20, 28, 36, …, …, 8, 4, 2, 1

There’s a pattern in this series, which emerges when you poke at it a little. For the moment, ignore the final “…, 8, 4, 2, 1″ segment. We start out with the number 3 and then list all the odd numbers greater than 3 in order of increasing magnitude; when this first part of the sequence is finished, we take each of its elements in turn and double it, concatenating the results to form the next segment of the sequence; then in the third phase we take the same odd elements again and multiply each of them by four; the process continues in the obvious way. Thus the successive segments have the following structure:

3×2⁰, 5×2⁰, 7×2⁰, 9×2⁰, …
3×2¹, 5×2¹, 7×2¹, 9×2¹, …
3×2², 5×2², 7×2², 9×2², …
3×2³, 5×2³, 7×2³, 9×2³, …

The only natural numbers missing from this infinite sequence of infinite sequences are the powers of 2 (including 2⁰=1). Those missing values make up the final segment of the sequence. The really weird part is that the powers of 2 are listed in reverse order, from largest to smallest: …, 2⁴, 2³, 2², 2¹, 2⁰. Because of this inversion, we have an inside-out sequence, solidly anchored at both ends but all puffed up with infinities throughout the middle.

What inspires me to write about this curious counting sequence is an article in the latest issue of The American Mathematical Monthly, which landed in my mailbox over the weekend. The article, titled “On ordering the natural numbers, or the Sharkovski theorem,” is by Krzysztof Ciesielski and Zdzisław Pogoda of the Jagiellonian University in Krakow. They explain that the sequence was invented (discovered?) in 1964 by the Ukrainian mathematician Alexandr Nicolaevich Sharkovski. It arose in the context of dynamical systems and chaos theory. I’m not going to get into those topics, but I highly recommend reading Ciesielski and Pogoda’s article. What I want to talk about here is the process of counting in this strange order.

I certainly can’t exhibit a complete counting program for the Sharkovski sequence—a program that would begin with 3 and end with 1 and in between visit all the other natural numbers. After some thought and a bit of trial and error, however, I realized that I can write a successor function for the sequence. It’s a surprisingly sweet little function, concise and simple, which suggests that maybe the sequence is not quite as weird as it looks.

My first instinct in the search for a successor function was to do a case analysis, in effect supplying a separate function for each segment of the series. Each of the segments (except the last one, which I shall again ignore for the nonce) consists of numbers in a certain congruence class: 3, 5, 7, 9 are all of the form 2x+1 (where x ranges over the natural numbers); 6, 10, 14, 18 have the form 4x+2; 12, 20, 28, 36 follow the pattern 8x+4, and so forth. Thus the successor function would be a long series of clauses, one for each possible congruence class. The problem, of course, is that I’d need infinitely many clauses.

There’s a better way. For the first segment of the series—the part made up of odd numbers 3 or greater—the successor function is simple and obvious: n = n + 2. All the numbers of the second segment (3×2, 5×2, 7×2, 9×2) can be reduced to the corresponding odd numbers of the first segment; we just need to divide each of them by 2. For any number in the second segment we can find the correct successor by applying a series of three operations: divide by 2, add 2, multiply by 2. The formula is 2 × (2 + (n/2)). The later segments can be treated similarly, repeatedly dividing n by 2 until we reach an odd number, then adding 2, and finally multiplying by 2 as many times as we divided. This suggests a recursive formulation of the successor function:

function s(n)
  if odd(n)
     then return n + 2
     else return 2 * s(n/2)

That’s all there is to it, and it actually works most of the time! Specifically, it works for all values of n except powers of 2. Consider what happens for n=20. The predicate odd(20) fails, and so we take the else branch of the if statement. There we evaluate the expression 2 * s(20/2), which leads to a recursive invocation of s(10). Again the predicate odd(10) fails, and so we evaluate 2 * s(10/2). This time the recursive call is s(5); the predicate odd(5) succeeds, and so the then clause is selected, returning a value of 5+2=7. Now the two pending multiplications are completed, producing a final value of 2×2×7=28, which is indeed the correct successor of 20. Nothing to it!

I was surprised that so much of the structure of the Sharkovski sequence could be captured in just a few lines of code. But we still have to deal with the final segment of the series, the descending powers of 2—…, 2⁴, 2³, 2², 2¹, 2⁰. Can it be done without making too much of a mess?

Suppose we had on hand a predicate function twopower(n), which returns a value of true if n has no prime factors other than 2, and returns false otherwise. Then we could add an extra if clause to the successor function:

function s(n)
  if twopower(n)
     then return n/2
     elseif odd(n)
       then return n + 2
       else return 2 * s(n/2)

This function now gives the correct Sharkovski successor for every natural number with one exception. It works as before for odd numbers and for even numbers that are not powers of 2; and, given a power of 2, it returns the next lower power of 2. For example, if the argument n is equal to 4, s(n) returns a result of 2; for n=2, s(n) = 1. The remaining problem case is n=1. I’ll return to that issue below; in the meantime, let’s see how the auxiliary function twopower(n) might be implemented. Here’s how I would do it:

function twopower(n)
  if n==1
     then return true
     elseif odd(n)
       then return false
       else return twopower(n/2)

The logic here begins with the easy cases: If n is equal to 1 then it definitely is a power of 2, and if n is an odd number other than 1 then it definitely is not a power of 2. If neither of these descriptions apply, then n must be an even number. So we divide it by 2 and start over. The rules of the recursion ensure that any power of 2 will eventually be reduced to 1 (so that the function returns true) and any other natural number will eventually expose an odd factor other than 1 (so that the function returns false).

There’s something curious about this procedure. In its structure and its action the twopower predicate is remarkably similar to the successor function itself. Both procedures involve a recursion on n/2, which terminates only when all the factors of 2 have been divided out. Indeed, every time a successor is calculated, this sequence of divisions is performed twice, first in the twopower predicate and then in the main body of s(n). Surely we ought to be able to avoid this wasteful duplication. Can’t we just do a test at the bottom of the main recursion to find out whether or not we’re dealing with a power of 2?

Yes, we can. And the change to the s(n) program is tiny. We just replace the twopower(n) predicate with the predicate n==1.

function s(n)
  if n==1
     then return n/2
     elseif odd(n)
       then return n + 2
       else return 2 * s(n/2)

For odd numbers greater than or equal to 3, and for even numbers that are not powers of 2, this procedure again works exactly like the earlier versions. To see how powers of 2 are handled, we can trace the execution of s(4). Neither the n==1 nor the odd(n) predicates are satisfied, and so we fall through to the last line, generating a recursive call s(2). Again the value of n is neither equal to 1 nor odd, so the last line of the definition is activated once more, generating the procedure call s(1). Now the n==1 test is true, and so the value is n/2, or 1/2. Climbing back up through the chain of pending multiplications produces the final value s(4) = 2 * 2 * 1/2 = 2. We get the right answer, and we’ve eliminated the duplicated recursion when testing for powers of two.

Very nice. But there’s still that pesky exception: What happens if you ask the Sharkovski successor function for the successor of 1?

Well, what’s supposed to happen? As the series is presented to us in the Ciesielski and Pogoda article, 1 has no successor. This makes sense in the context where the sequence was originally defined, but if you look at the sequence merely as a counting order, that abrupt end point is very strange. When Giuseppe Peano set out to define the natural numbers, one of the axioms was that every natural number has a successor.

I can think of four ways of dealing with this situation.

Option 1: Ignore it and it will go away. If we start counting through the Sharkovski sequence at n=3, we’re never going to reach n=1 anyway, so why worry about it? But by this argument we could just use n = n + 2 as the successor function, which takes all the fun out of the game.

Option 2: Abide by the rule that 1 has no successor. If the program is asked to provide such a nonexistent result, it halts and prints an error message: “Sorry, but you have fallen off the end of the number line.” This behavior may be the right choice, but I resist it strenuously, on aesthetic grounds. The problem is that the value n=1 can be generated internally, during the recursive processing of a higher power of 2, or it can be presented from the outside, as the initial argument to s(n). These two cases have to be treated differently. It’s entirely possible to do that, but the resulting program is ugly and artificial.

Option 3: Accept what the program tells us, and run with it. In other words, don’t adapt the code to the mathematics; bend the math to suit the code. According to the last version of s(n) given above, what is the next Sharkovski number after 1? Why it’s 1/2 of course! I’ll concede that 1/2 is a fairly strange-looking natural number, but maybe the idea is not totally indefensible. We got to this point by counting down …, 2⁴, 2³, 2², 2¹, 2⁰. It’s not so bizarre to suggest continuing with 2^–1. Indeed, we could take a step further. Changing the expression n==1 to n<=1 will ensure that 1/2 also has a successor, namely 1/4, which is followed by 1/8, etc. Now the sequence is infinite at the top, which makes me feel less claustrophobic. (Note that this decision does not change the domain of the function to cover all the rationals. We still can’t calculate the successor of 1/3 or 3/2. We’ve extended the definition of a natural number rather modestly. Previously, natural numbers of the form 2^k required k to be a nonnegative integer; now it can be any integer.)

Option 4: Let the successor of 1 be 3. This choice has the effect of turning the Sharkovski sequence into a giant cycle (with a lot of infinities in the middle) and acknowledges the unique role of 1 as the only odd number that’s a power of 2. The code is not very different from what we’ve already seen:

function s(n)
  if odd(n)
     then return n + 2
     elseif (n==2)
       then return 1
       else return 2 * s(n/2)

In this version we don’t need a special case to deal with n=1; it is treated the same as all the other odd numbers. But now we do need special handling for n=2. In this respect the two solutions seem roughly equal by standard measures of kludginess. The cyclic version might deserve extra credit because it never dabbles in nonintegral values of n.

I have a closing thought. What happens if we try to simplify the successor function even further? Starting from either of the two final versions of s(n) given above, and eliminating the special cases, we wind up with this variant:

function s(n)
  if odd(n)
     then return n + 2
     else return 2 * s(n/2)

But that’s exactly where we began! It’s our first approximation to a successor function, derived by ignoring the problem of those annoying descending powers of 2 at the end of the Sharkovski sequence. This version has an appealing symmetry and simplicity. Odd numbers are treated one way, even numbers another. No other distinctions are necessary.

What does this oversimplified function produce? It yields this:

1, 3, 5, 7, …, 2, 6, 10, 14, …, 4, 12, 20, 28, …, 8, 24, 40, 56, …

That’s rather pretty, and indeed seems more orderly—more “sequential”—than the Sharkovsky sequence itself. At the same time, it leads me to wonder whether we’re really dealing with a sequence at all, rather than a collection of disjoint sequences. What do the dots between those segments really mean? How do we know that the segments should be assembled in the given order? There’s nothing in the successor function to favor that arrangement over, say,

4, 12, 20, 28, …, 1, 3, 5, 7, …, 8, 24, 40, 56, …, 2, 6, 10, 14, ….

In the case of the Sharkovski sequence, there’s an extrinsic reason for imposing a total order, having to do with the origin of the sequence in the study of dynamical systems. The elements of the sequence correspond to the fundamental periods of periodic points in such systems. Sharkovski proved that if a dynamical system has a point with period n, then it also has at least one point with period m for every m that comes later than n in the Sharkovski sequence. (In particular, this means that a period-3 point must be accompanied by points of all other periods: deterministic chaos.)

Unfortunately, there’s no such justification if we look upon a sequence as just an arbitrary arrangement of numbers, ordered according to its own internal logic. I’m not sure such a logic exists in this case.

Notes: Neil J. A. Sloane, who is never out of sequence, already has a reference to Ciesielski and Pogoda, but the sequence is indexed under A005408, the odd numbers. Getting the full Sharkovski sequence into Sloane’s index would be as challenging as writing a program to generate it.

The article by Ciesielski and Pogoda is a translation (from the Polish, by Abe Shenitzer) of a chapter from their book, Mathematical Diamonds, published in Warsaw in 1997. I’m curious about the rest of the chapters. Perhaps some enterprising mathematical publisher will bring out the whole book in English.

I often use a computer to create graphics, but there was a time when I used graphics to compute. That era came back to me the other day in the library. I was browsing among dusty volumes in the folio section when I came upon this:

The Design of Diagrams
for Engineering Formulas
and
The Theory of Nomography

by

Laurence I. Hewes, B. Sc., Ph. D.
and
Herbert L. Seward, Ph. B., M. E.

McGraw-Hill Book Company, Inc.
1923

The clerk at the circulation desk observed that there was no record anyone had ever borrowed this book. Although the records don’t go all the way back to 1923, I wouldn’t be surprised if I’m the first reader of this volume in 30 or 40 years.

It’s a book full of nomograms and similar graphic devices, with instructions on how to create them. Here’s a simple example for calculating the volume of a torus:

If you know any two of d, V and D, you can find the third quantity by laying a straightedge across the scales. (Quick quiz: What’s that constant in the formula V = 2.4674d²D?)

I used to see computational aids like this all the time. Some magazine I read in the seventies (I’m not sure which one—maybe Electronics?) published a new nomogram every month. But now such diagrams have a decidedly fusty look. They’re like tools you might find in an old blacksmith shop or a tannery; it’s a challenge just to figure out how they worked and what they were used for. You find yourself admiring the workers who created useful products with such implements.

The graphic device below is for calculating the strength of a metal plate pierced by rivet holes:

Did the engineers who specified the half-inch gusset plates for certain joints on the I-35W bridge in Minneapolis rely on such aids? The preliminary report from the National Transportation Safety Board (.pdf) doesn’t comment on the computational methods that might have been used when the bridge was designed in the early 1960s. In any case, it’s not at all obvious which is more error-prone—pencil and paper, slide rule, nomogram, CAD software.

The Theory of Nomography—as Hewes and Seward term their art—could hardly be more distant from modern computing practice. For one thing, it converts arithmetic into geometry; nowadays, we’re more likely to go the opposite way. A nomogram also emphasizes a static, declarative style of representing knowledge: A single diagram embodies all the relations of several variables, and one method solves for any unknown. Most digital computing is procedural rather than declarative; the emphasis is on step-by-step algorithms to go from givens to answers.

I’m not about to give up silicon in favor of paper computers, but I do find some of these diagrams both beautiful and illuminating. Here’s a nomogram for solving the quadratic equation z²+pz+q=0:

Instead of three straight-line scales, as in the formula for the volume of a torus, we have two linear scales and a hyperbola. A moment’s thought reveals why the diagram must have this form: For any combination of the coefficients p and q, the equation must have either two roots or no (real) root. One branch of the hyperbola carries all the positive roots and the other all the negative values of z. Poking around in the diagram brings various properties of the equation into sharp focus. For example, if you lay a straightedge across the diagram in such a way that it passes through the point p=0, then it will either cut the two branches of the hyperbola symmetrically (if q is negative) or it will miss both branches (if q is positive). This is no surprise—the roots of z²+q=0 had better be plus and minus the square root of q—but the graphic presentation carries a lot of explanatory force.

Hewes and Seward give an even more elaborate tableau for solving a cubic equation:

The dashed line drawn across this diagram represents a straightedge placed so as to solve the particular instance z³+4z²-4z+0.5=0. The straightedge is set to the points 4 and –4 on the left and right scales, and then the roots are read off by projecting vertically from the intersections of this line with the curve labeled 0.50. Working by eye, the roots appear to lie at about 0.15 and 0.7. Newton’s method—the archetype of iterative, step-by-step computations—gives 0.14758497342482376768480 and 0.69902089681305967783231. (On the SAGE server at the University of Washington, finding each of those roots took a couple of hundredths of a second.)

Note: Ask Dr. Math has an informative article on nomograms (or nomographs) with lots of references. One of the references led me to a 1999 lecture by Thomas Hankins, published in Isis (Hankins, Thomas L. 1999. Blood, dirt, and nomograms: A particular history of graphs. Isis 90(1):50–80). Hankins traces the origin and early history of the nomogram, which I had never known. Both the name and the concept came from Maurice d’Ocagne of the École des Ponts et Chaussées in Paris toward the end of the 19th century. Their first uses were in calculations needed for railroad construction.

Update 2008-03-05: Ron Doerfler, in a blog called Dead Reckonings, has several illuminating and thorough essays on the construction of nomographs, including a very fishy example laid out on an elliptic curve. The rest of the blog is also worth reading. Thanks to Mitch Burrill for the pointer.

My friends up north tell me they have quite enough snowflakes already, thank you. Nevertheless, Janko Gravner and David Griffeath are making more. Or, rather, they’re making snowfakes (the word is theirs, not mine):

In case there’s any doubt, the image above is not a photograph of a real snowflake; it’s an incredible simulation.

Mathematical and computational models of snowflakes have a long history, perhaps going back to the snowflake curve of Helge von Koch. I say “perhaps” because Koch, a Swede, seems not to have been much interested in snow; his 1904 paper on the subject was all about nowhere-differentiable everywhere-continuous curves. By the 1970s and 80s, however, there was a serious search for simple rules that would give rise to realistic snowflake patterns.

In a series of three long and detailed papers, all written over the course of little more than a year, Gravner and Griffeath recapitulate the entire history of this effort, and then they advance the state of the art. They begin with cellular automata, especially a model first discussed in 1984 by Norman H. Packard. They go on to two-dimensional models based on the idea of diffusion-limited aggregation (which is also the process that generated the banner atop the bit-player.org page). Finally they develop the three-dimensional model that produced the image above. They write:

The key features of our model are diffusion of vapor, anisotropic attachment of water molecules, and a narrow semi-liquid layer at the boundary. All three ingredients seems to be essential for faithful emulation of the morphology observed in nature.

All three papers and much more (movies, a slide show, even source code if you want your own snowfaking machine) are available at the Snowfake site. The first of the papers has also been published in Experimental Mathematics.

How much can these artificial snowflakes tell us about the formation of real ones? In modeling there always seems to be an interesting tension between simplicity and realism. Choose too crude an approximation and you never make contact with the real world; but a model that’s too complicated can be as hard to understand as nature itself. In this case, though, all three of the Gravner-Griffeath approaches seem to have something to teach us. Even the most abstract model, the cellular automaton, offers a hint of where those feathery patterns come from: an essential element of the automaton rules is that cells become active only if some but not all of their neighbors are active, favoring the growth of a structure that’s connected but not solid. The diffusion-limited aggregation models derive from a similar underlying principle but add a lot more physics, since the simulated water molecules can move through space. The 3D models include still more details and simulate the crystal-growth process in a way that begins to illuminate physical concepts such as the phase diagram.

For those who insist on real snowflakes, there’s the impressive work of Kenneth G. Libbrecht on exhibit at snowccrystals.com. (Don’t be put off by the sales pitch for the Snowflake Store; there’s good physics here.) Libbrecht has also written on snowflakes for my own magazine, American Scientist, but I’m not going to include a link because, sadly, the article is being held for ransom behind a paywall.

From the listener’s point of view, the utility curve for mathematics talks seems to look something like the plot at right. If you already know everything about a subject before you walk into the room, you’re not likely to learn much. At the opposite extreme, if your prior knowledge is absolutely zero, it’s again all too likely that you’ll remain just as ignorant afterwards as you were before. The existence of a peak between these zeroes is my optimistic hypothesis. (The nonexistence of regions where the function dips into negative territory is also asserted on faith, although I’m less sure about this. Over the years there have been a few talks where I felt I knew less at the end than at the beginning.)

I’ve had little experience with the know-it-all end of the curve, but I could give a fairly detailed account of what life is like near the ignoramibus end. In the past four days I’ve wandered into a a number of talks from which I was not equipped to profit—but there’s not much point in my discussing those. The paragraphs that follow are brief and hasty notes on some of the talks that taught me something.

Diffusion of knowledge

Steve Smale was one of the organizers of a session titled “The Mathematics of Information and Knowledge.” I went to Smale’s own talk in the session partly because it’s always worthwhile finding out what Smale has on his mind, but also because I was puzzled by that opaque and generic title. It might describe almost anything.

What Smale wanted to talk about was recent work on learning and vision, done in collaboration with Tomaso Poggio of MIT. Smale alluded to Noam Chomsky’s observations about “poverty of stimulus”: a child needs to see an elephant only once or twice to be able to recognize elephants forever after. Computational learning algorithms come nowhere near this level of efficiency; if you want a computer program to recognize elephants, you’ll need to show it many examples.

In their study of recognition algorithms, Smale and Poggio have chosen to work with simple grayscale images, which require less care and feeding than elephants. Their aim is to create a distance function that will measure the similarity of any two images, classifying them in much the way the human visual system does. For example, an image of a cat should be closer to another image of a cat than it is to an image of a dog. The ordinary Euclidean distance function is not much help here. If images have a million pixels, then each possible image is represented by a point in a million-dimensional space. The Euclidean distance between two such points doesn’t tell us much about cats and dogs; besides, there’s so much elbow room in a high-dimensional space that “closeness” doesn’t mean much. Some kind of drastic dimensional reduction is needed.

Image recognition algorithms have a long history, and techniques of dimensional reduction are a longstanding problem in statistics. What’s new here? Unfortunately, this is where I begin to slide down to the wrong end of the knowledge curve. What I’ve been able to piece together (both from Smale’s talk and from an earlier talk by Peter W. Jones of Yale) is that the key is to transform the problem into a new space that comes equipped with a new coordinate system and a new distance metric. The metric tries to measure distance based entirely on “local” information. Conventional similarity measures serve to determine which of the images are near neighbors, but then other methods define longer-range relations.

One such metric, called diffusion geometry, measures distance in terms of a random walk. In a database of images, for example, the distance between two images is the expected number of steps needed to get from one image to the other, taking each step by choosing a nearest neighbor at random. A benefit of this scheme is that it respects the structure of any clusters present in the population. Two images are close if there is one short path between them, but also if there are many long paths.

Techniques like these can be applied not only to image recognition but also to text mining, bioinformatics, internet search engines and doubtless other fields. Indeed, another aspect of the story came out in Fan Chung’s talk on the PageRank algorithm that search engines employ to match queries against web pages. It had never occurred to me that searching the web for the word “elephant” is so much like the process that goes on inside my head when I see and recognize an elephant. Perhaps this is what was so brilliant about the invention of Google: the search engine doesn’t really search (in the sense of sequentially considering all the possibilities); it recognizes.

Zeta functions of graphs

No sense pretending: I didn’t even know that graphs have zeta functions. I guess the celebrity of Riemann’s zeta function in number theory is so great that it has overshadowed other members of the family—at least for me. The Riemann zeta function involves a product of powers of all the prime numbers, but this is a concept that can be extended to other realms. In graphs, the analog of a prime number is a path that satisfies certain criteria: It must be “closed, backtrackless, tailless and primitive.” The graph-theory zeta function is defined in terms of these prime paths.

In number theory, the zeta function has a special place because it tells us something about the distribution of primes among the natural numbers. In particular, there’s a connection between the distribution of the primes and the positions of the zeroes of the zeta function (this is the Riemann Hypothesis). There’s a similar hypothesis in graph theory, although it concerns the “poles” rather than the zeroes of the zeta function. (A pole is a place where the function becomes infinite or undefined.) There may even be practical consequences of all this: The distribution of the poles affects the abundance of a special family of graphs called Ramanujan graphs, which have applications in computing and communication.

Audrey Terras and Wen-Ching Winnie Li both gave major talks on zeta functions of graphs. In addition, there were other sessions devoted to Ramanujan graphs and related topics.

Percolation

On this subject I thought I was at least near the middle of the knowledge curve, but I learned that I still have lots to learn.

The mathematical version of percolation has a connection to what happens in coffee pots and septic tanks, but it’s a pretty distant and abstract connection. The process happens on a lattice of some kind, such as a grid or a honeycomb. You color the nodes of the lattice black or white at random and then ask whether there’s a continuous path of one color that extends all the way across the lattice. In a four-sided lattice, if there’s a black path that extends all the way from the left edge to the right edge, then there can’t be a white path from top to bottom.

Percolation was a lively topic in the 1970s. (I’m fond of the problem in part because one of my own early experiments, when I first got my hands on a computer, was building a Lotus 1-2-3 spreadsheet to simulate percolation.) But I had thought that all the interesting questions had been settled by the early 1980s, especially in the work of Harry Kesten. Evidently not.

Wendelin Werner, the recent Fields medalist, gave the series of three Colloquium Lectures this year, and percolation was a major topic within his presentation. Greg Lawler, in a Current Events talk, also touched on the subject. On the final day of the meeting I heard another hour-long discussion of percolation by Gabor Pete.

The new twist that seems to have attracted this attention is the question of whether solutions to percolation problems are stable in the presence of noise or uncertainty. For example, if a lattice configuration has a percolating black path, what’s the probability that changing the color of a single site will destroy the path? It’s not hard to get approximate or experimental answers to questions like these—you might be able to do it with a spreadsheet—but the work reported here in San Diego is on the trail of exact and rigorous results.

The patron saint of hopeless problems

Jeffrey Lagarias has devoted no end of thought, labor and scholarship to problems that he acknowledges are “hopeless.” The best-known example is the 3X+1 problem: Iterate the map X → X/2 if X is even, X → (3X+1)/2 if X is odd, and determine whether the process always reaches the same terminal loop. In San Diego Lagarias spoke on another hopeless problem: “Basic ternary digit sets and associated tiles.” Given a set of digits, can you represent all real numbers by concatenating those digits? For standard digit sets such as {0,1} or {0,1,2} or{0,1,2,3,4,5,6,7,8,9}, the answer is yes. The set {–1,0,1}, known as balanced ternary, also works: It is said to be a “basic” digit set. But what about {0,1,π}? For this trio of digits, it can’t be done: No matter how you arrange the digits, there will be gaps on the number line that you cannot fill. The problem is deciding which digit sets are basic. Trying ternary representations of the form {0, 1 –q} yields a peculiar list of values of q for which the set is not basic. Trying to discover a formula that would generate that list of q’s is now on the Lagarias list of hopeless problems.

Ringing up primes

This comes from a very diverting lecture by Brian Conrey on the Riemann hypothesis:

“The probability that an N-digit number is prime is approximately 1/(2.3N). For example, given a seven-digit telephone number, the probability is about 1/16. So, let’s try the experiment: How many of you have a prime phone number? (If only I were a little quicker at mental primality testing—gotta practice that Pollard rho algorithm—I could have raised my hand.)

The best of all possible lectures

Judith Grabiner spoke on the history of the idea of optimization in mathematics. Her story began with Heron of Alexandria, who explain the optical principle that the angle of incidence equals the angle of reflection by showing that this geometry yields the shortest path. Later, Fermat gave a subtly different rule for the law of refraction: The optimum path is the one that minimizes time rather than distance. Maupertuis then subsumed both of these ideas under the principle of least action. I have always found these laws of nature mildly mysterious. It’s not that I doubt their truth or applicability; my problem is that I don’t see why nature should “want” to minimize distance or time or action. Nature has all the time and space in the world—Where’s the need to be stingy with these resources.

Grabiner gave a thought-provoking review of the philosophical and theological background to these optimization principles. In this context it’s not hard to see a link between Leibniz’s work in the calculus and his optimistic philosophy, epitomized and satirized in the slogan “All is for the best in this best of all possible worlds.” In the world according to Leibniz, “God is the great optimizer,” and we should expect to find that the laws of nature are as simple as possible. Newton had a quite different but equally theological basis for his belief that the universe is ideally suited to human habitation. The question I’m left with, then, is how to account for the prevalence of optimization principles in the absence of such theistic underpinnings.

Sophie Germaine’s mathematical oeuvre

For me, this talk by David Pengelley was the big surprise of the meeting. Sophie Germain is perhaps the most famous of women mathematicians before the 20th century. But not one line of her own mathematical writing had been known; our only primary source was a footnote in a paper by Legendre. But now two great troves of letters and manuscripts have been uncovered in Paris and Florence, and suddenly we know that Germain was far more accomplished and ambitious than anyone had guessed. She had a full plan for proving Fermat’s Last Theorem; although it couldn’t have succeeded, it was a masterful attempt. As this story unfolds over the next few years—hopefully with publication of the papers—it’s going to be fascinating.

There’s lots more that’s worthy of mention, but it’s Thursday, the meeting is over, I’m at the airport in San Diego on my way home, and I’m exhausted. Happily, I can point out that I’m not the only one blogging this meeting. In particular, Adriana Salerno has been writing for the American Mathematical Society. (There’s a link on the AMS web site, but it’s well hidden; go here.)

There’s a lot of mathematics going on here in San Diego, and I’m taking notes. But for now, what I have to offer is a bucket of pixels:

It’s hard to get excited about the architecture of convention centers. They’re like airports: You’re pleasantly surprised if they’re merely functional. In many respects the San Diego convention center is no better than any other. It squats on an enormous tract of bayside property, cutting off a downtown neighborhood from the waterfront. But one tent-like wing (above) has genuine visual interest. (As the trash cans and “Wet Floor” signs at right indicate, it also seems to have a leaky roof.) The adjacent stairway (below) offers the public (arduous) access to the waterfront. No one seems to be using it, but it does make a rather handsome abstraction.

Much as we despise airports, we all love railroad terminals. Below is a bit of the old Santa Fe Depot, still in use by Amtrak. It is seen from (and reflected in) the trolley terminal next door.

I often gripe about a meeting schedule that has talks starting at 7:45. On the other hand, that agenda gets you out and about in time to see aspects of city life you might otherwise miss.

San Diego has some of the most distinctive street plumbing in the country (below). Note the Dalek fire hydrant. The chromed pipe in the foreground is labeled “suction connection.” Like the hydrant, it’s for use in firefighting, but whereas the hydrant supplies water under pressure, the suction connection merely provides access to a water reservoir and needs a pumper truck to supply pressure.

Of course that silvery cylinder (bent into a segment of a torus) is an irresistible target for experiments in projective geometry.

In the exhibit hall (below), legendary hacker hunter and astronomer Cliff Stoll is hawking the Acme Klein Bottle. The sales pitch is a high-energy performance that hasn’t been equalled since the glory days of the Vegematic.

More to come.

The fellow across the aisle is a stranger to me, but I know we share a destination. He’s scanning the index of the meeting program, presumably looking for friends or colleagues delivering a paper. When I unfold myself from seat 22D and stroll toward the back of the plane, I spot a few more of us. Someone is working on foils in LaTeX. Someone else is doodling on squared paper, making lots of little stairstep diagrams—they could be Young tableaux or they could be some kind of self-avoiding walks. The group of three college kids playing cards in row 32 might be on their way to a football game, but when I overhear a snippet of conversation that includes the phrase “convex hull,” I conclude they are not just Chargers fans.

It’s time again for the Joint Mathematics Meeting, held this year in sunny San Diego—which is actually quite soggy at the moment. (In front of my hotel this morning I found a manhole cover that had floated free of its foundation sometime during last night’s downpour.)

We’ll muddle through (and try not to fall in). Sometime over the next few days, maybe I’ll even learn what all those little stairstep diagrams were all about.

In this season of giving and getting, you’ve got to admire the marketing savvy of the One Laptop Per Child project. They named their introductory sales campaign “Give One, Get One.” The computers cost $200 apiece. For a donation of $400, you send one machine to a child somewhere far away (Afghanistan, Cambodia, Haiti, Mongolia and Rwanda are mentioned as possible destinations), and you get another for your own gadget-happy life.

The question that everyone seems to ask about OLPC is whether laptop computers are really what the children of Afghanistan, Cambodia, etc., need most urgently. Well, reason not the need! What I find most appealing (and most subversive) about the whole idea is that it leapfrogs over matters of brute survival. If children lack adequate food and shelter, is that grounds for denying them intellectual diversion and enrichment as well?

In connection with an earlier attempt to bring computers to children, Alan Kay wrote (pdf):

[A computer] can be like a piano: (a product of technology, yes), but one which can be a tool, a toy, a medium of expression, a source of unending pleasure and delight… and, as with most gadgets in unenlightened hands, a terrible drudge!!

So let’s not deny the world’s children either delight or drudgery. Once OLPC achieves its goal, I say we start a One Piano Per Village program.

But enough about giving. What about getting? What’s the new computer like?

They call it the XO. I’ve had mine for only a few days, and I’ve hardly begun to play with it, so all I can report here are first impressions. Basically, I think it’s brilliant, but I also wish the system software had been built on a somewhat different model.

The hardware is undeniably cute. No one will mistake it for a Sony Vaio or a Dell Inspiron. I wouldn’t be surprised if the XO becomes something of a fashion statement, the laptop to be seen with at Starbucks, or for liveblogging NANOG or SODA. I’ve heard complaints that the keyboard is too small for adult fingers, but typing on these little green keys can hardly be worse than thumbing a Treo or Blackberry. (Disclaimer: I type with two fingers, so I’m not much of a judge of keyboard ergonomics.)

If the styling has a whiff of Fisher-Price about it, there’s also some thoughtful ingenuity at work here, and designers of machines for grownups might learn something from it. The screen is gorgeous—crisp and bright in its standard color mode, with a secondary black-and-white mode that’s legible in full sunlight. The screen also swivels 360 degrees and can be laid face-up over the keyboard, so that the XO can be used as a tablet for reading e-books and the like.

There’s no disk drive; the machine has 256 megabytes of RAM and a gigabyte of flash memory for nonvolatile storage. Three USB ports and a slot for SD memory cards offer opportunities for supplemental storage. One consequence of the no-moving-parts architecture is that the computer is absolutely silent in use—no clicking or whirring from a disk drive, no fan noise.

The wifi transceiver is amazing. I never knew I had so many well-connected neighbors—people named linksys and netgear, for example. No other computer I’ve had in the house has ever detected any of these networks. Why is the wireless card in my other laptop (which cost an order of magnitude more, by the way) so wimpy in comparison? The XO can also form ad hoc “mesh” networks with other XOs, but evidently I’m the first XOwner in my neighborhood, so I haven’t been able to experiment with that capability.

When it comes to software, I can’t be quite so wholeheartedly enthusiastic. There are some bright spots. A set of four programs called TamTam provide first-rate tools for creating and playing music; the calculator is very elegantly done; there’s a cool built-in oscilloscope, and a “Write” program that seems just right for the intended audience. Also a Python interpreter named Pippi. And the software called Etoys is a highly ambitious system, willed into existence by Alan Kay and a bunch of his friends, which looks like a plaything but has a complete Smalltalk development environment inside.

Some other spots are not so bright. For one thing, the software is just not finished yet. Some basic capabilities (printing, a sleep mode) are not yet implemented, and there are various buttons that don’t yet have functions. The web browser is primitive (no tabs, very limited facilities for bookmarks). There’s an RSS reader that doesn’t seem to work. An update planned for early next year is supposed to fix some of these problems.

Anyway, software is always behind schedule; I can wait. As a matter of fact, I’d be happier if they had taken longer and built the software in a different way.

I have opined elsewhere that computing is in a horrible rut, unable to escape the grip of precedents established in the distant past. A case in point is the Unix operating system, which is now almost 40 years old but is still with us in the form of Linux and OS X. The longevity of Unix argues that it must be quite a solid product, and I won’t argue with that. On the other hand, it’s a sad commentary on progress in computer science if no one has had a better idea since 1969.

OLPC offered a rare opportunity. It was a chance to start fresh, to throw away the past, to build a computer that has no legacy code to run; there was no need to worry about backward compatibility. But that’s not the way the project evolved. The XO software turns out to be a sugar-coated version of the Linux operating system. I can understand the reasons for choosing this path. Building an entirely new software system from scratch would have slowed the project down, and it would have raised the risk of catastrophic failure. Adopting Linux provided a major head start and allowed the project to draw on a global community of experienced programmers. But the choice also had an opportunity cost. A multiuser operating system designed in the era of timesharing and dumb terminals, and tuned to the needs of professional programmers, is not an ideal match for a laptop built for kids.

When I say the XO software is sugar-coated Linux, that’s just what I mean: The user-interface layer is named Sugar. It’s an interesting program, which tries to escape the ubiquitous desktop metaphor by emphasizing community and interaction. Instead of launching a program or application, the user starts an “activity.” Many activities can be shared with other XOwners; for example, two XOs can be set up to use acoustic signals to measure the distance between them. One intriguing “feature” of Sugar is the absence of a conventional file system. You don’t create documents and then decide where to put them and what to name them. Pointers to all activities are saved automatically in reverse chronological order in a linear list called the journal.

The sugar layer is nifty, but it’s also perilously thin. Underneath lies the Unix command line, and at present there are many things that can be done only by reciting the proper command-line incantations (many of them preceded by a magic ’sudo’). Will the kids master that kind of wizardry?

Maybe I shouldn’t worry; I’m sure they’re better equipped and quicker learners than I am. In any case, it’s their judgment that counts, not mine.

The latest cute trick from Google is a service for producing quantitative graphics on demand. For example, here’s a bar chart of the traffic to this web site over the past year:

The cute part is how you get Google to produce the graphic. The whole specification—including data, scales, labels and stylistic preferences—gets packed into a URL. In this case, the URL reads as follows (with line breaks added for clarity):

http://chart.apis.google.com/chart?
chs=450x300
&cht=bvs
&chbh=27,6
&chtt=bit-player.org+hits+per+month
&chco=ee2233
&chf=bg,s,efedea
&chxt=x,y
&chxl=0:|J|F|M|A|M|J|J|A|S|O|N|D|
      1:|0|20,000|40,000|60,000|80,000|100,000
&chd=t:54.9,59.1,61.3,69.5,83.6,77.6,60.3,60.5,69.2,77.3,86.0,-1

(If you want the key to decode all this curious bric-a-brac, see the Google Chart API Developer’s Guide.)

There’s something vaguely unsettling about this whole idea. When the web was young, a URL was a resource locator—in other words, the address of a document stored on a server somewhere. Times have changed, and most web servers now assemble pages by issuing queries to a database rather than by grabbing documents from a simple file system; the “back end” server fetches some text here, an image there, an ad from a third source. Still, the basic paradigm remains information retrieval; the vast majority of web sites are in the business of serving up some kind of pre-cooked static content, even when it’s embellished with dynamic sauce. But I really don’t think that Google Charts works that way. I don’t think they’ve produced an archive of all possible graphs and were just waiting for me to send the URL that retrieved the one you see above.

The charts service raises anew a question that comes up all the time in computing: What should we compute just once and store away in case it’s needed again later, and what should we recompute every time? Years ago we had precomputed tables of logarithms and trig functions, but now it’s easier to just calculate those numbers on the fly. Evidently graphs have now entered that realm as well—things so cheap to compute it’s not worth hanging onto them. Note that the graph you’re looking at above is not one that I produced when I wrote and published this page; instead, when you opened the page, your web browser (or RSS reader) sent a new request to Google’s servers, which then regenerated the graph from scratch. If a thousand people read the page, the graph will be recreated a thousand times. It’s monstrously profligate and inefficient, but I guess that’s what makes computers so wonderful.

One constraint on this mechanism is the length of the URL. Is there a limit? I didn’t know the answer, and so I turned—where else?—to Google. I quickly found a helpful web page that says the standards are silent on this issue, but some web browsers and servers impose a limit of as few as 2,000 characters. The Google Charts designers probably had this limit in mind when they created their scheme for cramming data into a URL. There are actually three encodings available. Above I chose a method in which each data point is a number between 0.0 and 100.0 and values are separated by commas; this allows for a few hundred data points before you start bumping into the 2,000-character limit. The most compact encoding packs each data item into a single ASCII character in the ranges from A=0 to Z=25, a=26 to z=51 and 0=52 to 9=61. Not the most intuitive encoding, but it allows for a further cute trick: graphing words and phrases.

http://chart.apis.google.com/chart?chs=200x200&cht=lc&chd=s:Agraphisworth1000words

Copy the URL into the location bar of a browser window, change the text at the end of the line, and you can see a graph of your name and address.

It’s time for my bimonthly self-promotional horn toot. The new issue of American Scientist is now available online, and paper copies should soon be stuffing mailboxes everywhere. My “Computing Science” column is on a new class of “holographic” algorithms invented a few years ago by Leslie G. Valiant of Harvard. The ideas have been further developed by Jin-Yi Cai of the University of Wisconsin (who is currently visiting Harvard as a Radcliffe Fellow) and several students and colleagues both at Wisconsin and in China.

If you want to know what holographic algorithms are all about, you’ll have to go read the column. I’m not going to rehash it here. Instead, I’m going to recycle a few paragraphs of a version of the column that might have been but never will be. This was a false start, an attempt at a lead that wound up leading me in the wrong direction:

It was the final day of a workshop, and I joined a group for dinner at a farmhouse restaurant in the village of Muggia, around the corner from Trieste, where Italy meets Istria. As the evening was winding down, we sat drinking the last of the wine, watching the sun sink into the Adriatic, and debating the P = NP question. The debate was somewhat lopsided: No one at the table was willing to defend the proposition that P is indeed equal to NP. But there was plenty of room for argument between hard-liners who insisted that P is most certainly not equal to NP and those who took a more agnostic view.

What are P and NP? They are classes of computational tasks or problems. Roughly speaking (I’ll try to speak less roughly in a moment), the class P includes all the things we know how to compute quickly. NP is a larger class, encompassing all the problems known to be in P and many others besides; for these additional tasks we don’t have efficient algorithms, and yet no one has proved that such algorithms don’t exist. If it should turn out that P = NP, then thousands of seemingly hard problems actually have some quick shortcut solution, if only we could find the secret.

A mathematician at my end of the table took an inflexible position: P = NP is not only wrong but unthinkable—a notion akin to time travel or perpetual motion. I had been lurking silently through most of this conversation, but at this point I spoke up. Time travel seems implausible, I said, because it would undermine causality, and perpetual motion would violate the conservation of energy. What bedrock principle would be overturned by the discovery that P = NP? The mathematician replied: “Do you believe in miracles? No? Well, wouldn’t it be miraculous if we lived in a universe where every last one of those NP problems has an easy solution?”

This was good enough for me on that mild summer night in Muggia. The fact is, however, the miracle argument cuts both ways. There’s a subclass of NP problems, designated NP-complete, with a special property: If there’s an efficient algorithm for any one of these tasks, the same method can be used to solve all NP problems efficiently. Thus for P to be different from NP requires the “miracle” that not even one out of thousands of NP-complete problems has a quick solution….

One more note on the column. This is difficult subject matter, and my grasp of it is tenuous. I could not have written the piece without a lot of help and hand-holding from Valiant and Cai, who were reading drafts and answering phone calls up until the very moment the issue went to press. I have a reason for thanking them here rather than in the column itself: If I’ve goofed in spite their efforts, I don’t want them implicated.