Steven M. Bellovin gave a fascinating talk yesterday on a subject he knows nothing about. Okay, I should rephrase that. Bellovin knows everything you can know about his subject without actually knowing anything, but he’s careful to point out that he doesn’t really know, or else he couldn’t have given the talk. This conundrum will be easier to understand if I mention the subject: Bellovin’s presentation was on the security arrangements for authorizing the use of U.S. nuclear weapons. He has pieced together his information entirely from open sources, without any access to classified documents. (But many of the open sources are open only because Bellovin and his colleague Matt Blaze have filed requests under the Freedom of Information Act to obtain them.)

The specific security device at issue here is known as a Permissive Action Link, or PAL. It is the mechanism that is supposed to stop a nuclear weapon from being armed or launched without the explicit orders of the National Command Authority (a phrase that covers the President, the Secretary of Defense and perhaps others). Early nuclear weapons had no such special interlocks. If you could get physical possession of a bomb or a warhead, and you knew how to trigger it, there was nothing but common sense to stop you from setting it off. It was only in 1962 that President Kennedy signed an order directing the military to develop and install PALs, and the task was not completed until sometime in the 1970s. Very little has been published about how the locks work.

Bellovin, whose field is computer security and networking (“and why the two don’t get along”), became interested in PALs because of a connection with a murky episode in the history of cryptography. The idea of public-key cryptography—which revolutionized the field and is now a very widely used technique—first became known to the world at large in 1976, when Whitfield Diffie and Martin Hellman published and patented a cryptographic protocol based on the mathematics of discrete logarithms. But there were always rumors that related methods had been invented earlier in the “black” community of classified research. In 1997, declassified documents revealed that a similar idea had been discovered before 1970 at the British Government Communications Headquarters—GCHQ, the descendant of Alan Turing’s famous cryptographic skunk works at Bletchley Park. In the U.S., according to Bellovin, Admiral Bobby Ray Inman, director of the National Security Agency in the 1970s, claimed that public-key methods were known there a decade before Diffie and Hellman published their work. And in 1993, Jim Frazer, a recently retired NSA official, mentioned that the basis for the NSA’s invention of public-key ciphers was a document titled National Security Action Memorandum 160, or NSAM-160. This was President Kennedy’s 1962 directive on PALs.

At the time, NSAM-160 was still classified, but Bellovin and Blaze initiated a declassification review and eventually received a copy, along with a supporting memorandum written by Jerome Weisner, Kennedy’s science advisor. A scanned version of the memo is available online at Bellovin’s web site.

Even with access to NSAM-160 and a number of other declassified documents, Bellovin has not reached any definite conclusions about the nature of the PAL or its cryptographic technology, but he has formed some hypotheses. First of all, he thinks it unlikely that public-key cryptosystems ever had a direct role in the PAL itself. The early models were mechanical or electromechanical combination locks. More-recent versions incorporate microprocessors, but there is still no obvious need for elaborate cryptographic protocols. The key that ultimately gets dialed into the device is a number of either 6 or 12 digits, much too small to be secure in a public-key system.

A more-plausible idea is that public-key methods were developed to distribute the PAL keys to far-flung military bases. (Diffie and Hellman originally presented their idea as a “key exchange” protocol.)

Another hypothesis is even more intriguing. Bellovin asks whether the rumored cryptographic innovation at NSA in the 1960s might have been the invention of digital signatures, which are distinct from public-key ciphers but closely related. A digital signature is designed not to hide the content of a message but rather to establish its provenance or authenticity. This is obviously a major concern in managing nuclear armaments. Those who have their finger on the trigger want to know that a launch order really does come from the National Command Authority. And in the aftermath of such a folly, the survivors (if any) might like to know who is to be held accountable.

Whatever the mechanism of the PAL, Bellovin says, he really hopes that it works.

(I heard Bellovin speak at the University of North Carolina at Chapel Hill. Slides from his earlier talks on the same theme—and even an MP3 recording—are listed among his publications, along with texts on Permissive Action Links and the Prehistory of Public Key Cryptography that cover much of the same material. Bellovin, who spent many years at Bell Labs, is now at Columbia University. Early in his career he was one of the three originators of the Usenet newsgroup system—which, years before blogging came along, was a medium of personal expression open to anyone with a net connection.)

Among children of a certain age, everyone has a best friend—and exactly one. Ideally, the best-friend relationship is symmetric: If I am your best friend, then you are my best friend, too. But symmetry is not guaranteed, and it can happen that I like you best, but you have someone else you like better than me. Sad, but life is like that sometimes.

We can model best-friendship geometrically by letting distance—or, rather, nearness—stand for intensity of affection. Sprinkle a bunch of points at random on a plane, and then draw an arrow from each point to its nearest neighbor, which we take to be the point’s best friend. When the best friends are mutual, a bidirectional arrow links the two points. In other cases, a chain of arrows points from a to b to c and so on. Here is a best-friend graph constructed in just this way:

There are 100 dots in the diagram, which have spontaneously formed 30 constellations, or connected clusters. Some 40 of the dots represent disconsolate children who feel an attachment for someone who’s attached to someone else. (Note that some of the dots are so close that the arrows are obscured.)

Questions.

1. In general, what proportion of the children in this model are stuck in unrequited best-friendships?
2. How many clusters form, on average?
3. How do these quantities vary as a function of the overall number of children?
4. Adding a new child to the class or the neighborhood could disrupt some existing friendships: If a new point is inserted at a random position, how many existing bonds are likely to be broken or rearranged?
5. What about the geometry and topology of the model? Would it make a difference if the points were plotted on the surface of a torus? Would the results be different in one dimension (with all the points arrayed along a line) or in three dimensions (with the points distributed throughout a volume of space)?

Note that the best-friend problem is not equivalent to the well-known stable-marriage problem (on which there is an extensive literature). In the stable-marriage situation, matchings are always two-by-two: If I like you best but you prefer someone else, then I simply have to find another partner.

For a rather different perspective on the mathematics of friendship (and also enmity) see “Dynamics of Social Balance on Networks,” by T. Antal, P. L. Krapivsky, and S. Redner.

In the game of Chomp, the player who moves first always has a guaranteed winning strategy. This fact might seem to take all the suspense out of the game, but it doesn’t. Except in the smallest and simplest games, no one knows which first move will lead to the guaranteed victory. For me, this situation makes playing Chomp doubly frustrating. When I go first, I have no excuse for losing—but lose I do, even to mindless players like this Java applet by Andries E. Brouwer. Some recent work has taken a new approach to understanding the difficulty of Chomp. The results won’t necessarily help you win, but they may help you understand why finding a winning move can be hard.

Chomp is played on a rectangular field divided into east-west rows and north-south columns. Initially, all the cells of this array are filled with markers such as checkers or cookies. A move consists of choosing a cell and removing the marker there as well as all the markers to the north and east of it—thus taking a rectangular bite out of the array from the northeast corner. On each turn you are required to remove at least one marker. The object is to avoid taking the last, “poisoned” marker, in the southwest corner, thereby forcing your opponent to swallow it. The game was invented in the 1970s by David Gale of the University of California at Berkeley. The name was coined by Martin Gardner.

How do we know that the first player can always win in Chomp? It’s beguilingly simple. Suppose you go first and take just the smallest legal bite—the single marker in the northeast corner. Then I respond with a countermove that turns out to be a winner—a move so good that no matter what you do in reply, you are inevitably stuck with the poison pill at the end of the game. Well, if my move is so unanswerably brilliant, why didn’t you choose it as your own? You could have won by making my move at the outset. This argument hinges on a property of Chomp that sets it apart from many other games of strategy, such as chess: If a move is legal at any time during a game of Chomp, then it is legal as an opening move.

For a few special geometries it’s easy to find a winning strategy in Chomp. For square arrays and for shallow rectangles with just one or two rows, there are simple rules for choosing a move. Long rectangles with three or more rows, however, have resisted comprehensive analysis. Computational methods have identified the winning first move for thousands of specific array shapes, but they have failed to reduce the game to any simple formula. Below are the winning first bites in a few three-row games.

Note that the shape of the chewed-off rectangle varies from case to case.

In the past few years, three-row Chomp has been studied in detail by Doron Zeilberger and his students at Rutgers University. They have found no concise magic formula for winning the game, and yet the distribution of winning and losing moves is not random, either; there are strong regularities.

Any configuration of a three-row game can be mapped to a point in a three-dimensional space. The (x, y, z) coordinates of the point represent the number of columns occupied by three, two and one markers respectively, and each point in the space can be labeled as a winner or a loser. If the game had no ordering principle whatever, then winning and losing positions would be scattered completely at random within this volume. If there were some simple rule for winning (e.g., always choose y and z so that they are prime numbers), then obvious patterns would show up in the distribution of winning points. The truth lies somewhere between these extremes.

Zeilberger and his student Xinyu Sun defined sets of points they called “instant winner” positions. These are (x, y, z) points from which you can legally move to another point with a smaller value of x that turns out to be a loser. Zeilberger and Sun discovered that along certain lines within the space—lines where x and z are held constant but y increases—the distribution of instant-winner points starts out looking random but then seems to become “ultimately periodic,” with either a constant value or a simple repetitive pattern. The ultimate periodicity of the sequences was later proved by Steven Byrnes. (Byrnes was a high school student at the time. His proof won a $100,000 science fair prize, which is a lot more than most theorems earn for their authors. Byrnes is now an undergraduate at Harvard.)

Recently, the patterns observed in the (x, y, z) space of Chomp moves have been explored further by Eric J. Friedman of Cornell University and Adam Scott Landsberg of the Claremont Colleges. Their approach is quite different from the usual methods of game theory, number theory and combinatorics. They look upon the game as if it were a problem in physics, such as trying to understand the onset of magnetization in a metal or the growth of a crystal. Although the game itself is strictly deterministic—there is no rolling of dice in Chomp—Friedman and Landsberg are led to make probabilistic predictions about the winning chances of moves in various parts of the grid. In a physical system, it’s seldom possible to know all the details about the states of individual atoms, but one can nonetheless make reliable estimates of macroscopic properties. Likewise in Chomp, the exact location of winning and losing squares varies unpredictably with any small change in the initial configuration of the array, but the overall, large-scale geometry is highly consistent.

The diagrams reproduced here (courtesy of Friedman and Landsberg) show instant-winner positions for certain three-row games. Blue points are instant winners, tan points are not. The diagrams are slices through the (x, y, z) volume, the larger panel along the plane where x=700 and the smaller at x=350. What’s notable is the similarity of the two patterns—the solid wedge at the lower left, the salt-and-pepper cone at the upper left, the series of horizontal stripes (which correspond to Zeilberger’s ultimately periodic sequences). But the similarities are only present at large scale; the detailed distribution of the various stripes and other features changes totally from one diagram to the other. Friedman and Landsberg derive a “renormalization” procedure—an idea borrowed directly from physics—that can account for this persistence of large-scale structures even as all microscopic configuration becomes thoroughly mixed up. And they give a probabilistic prediction of where a winning play is most likely to be found.

For all the statistical flavor of Friedman and Landsberg’s analysis, they have one result that is not at all probabilistic. They prove that in three-row Chomp the winning strategy is unique; for any configuration of the game, there is one and only one move guaranteed to produce a victory.

Links::

• Friedman and Landsberg (PDF via ftp)
• Zeilberger 2001 and Zeilberger 2004
• Byrnes
• Andries E. Brouwer on Chomp

Deep Background:

• Gale, David. 1974. A Curious Nim-type game. American Mathematical Monthly 81:876-879.
• Gardner, Martin. 1973. Mathematical games: Sim, Chomp and Race Track: New games for the intellect (and not for Lady Luck). Scientific American 228(1):108-115.

Finally, thanks to Steve Strogatz of Cornell for alerting me to the work of Friedman and Landsberg.

I went to the Joint Mathematics Meetings two weeks ago with the idea that I would post reports live and on location from San Antonio. I was dazzled by the mere possibility of doing this. Sitting in a lecture hall, listening to a talk, connected to the Net via the invisible magic of WiFi, I could publish my notes before the speaker even sat down. For someone who can remember when “publishing” meant waiting a couple of weeks just to get proofs back from the press, this instant gratification is a beguiling idea. The problem, of course, is that the mind has not kept up with the technology. I found that I had to make a choice between attending the meeting (in the sense of paying attention, not just being present) and reporting on it. And if I had tried to regurgitate my undigested notes—well, the very thought of it is too disgusting to consider further.

So that’s my excuse for being 10 days late in filing these stories. In mathematics, however, once something is proved, it’s supposed to stay proved for at least a month, so I’m hoping there’s no harm done by the delay.

Some 1,750 talks and other presentations were listed in the program of the meetings. I was able to get to 30 of those talks, plus a couple of panel discussions and poster sessions—as well as the usual, raucus, all-night parties that gatherings of mathematicians are notorious for. The items that accompany this one cover just a handful of talks. My choices are not meant to represent the best of the program; they’re just some of the things that caught my attention.

Graph Limits and Graph Homomorphisms. Laszlo Lovasz (Microsoft). The field of graph theory has been transformed by recent interest in understanding properties of very large graphs, most notably those that describe communications networks such as the Internet and the Web. But the same thing that makes those graphs interesting makes them very hard to study: They have millions or billions of nodes and edges. Lovasz discussed an approach to this problem based on ideas from a very different area of mathematics—the concept of a limit in analysis. If you can show that a series of related graphs converges on a definite limit, then you may be able to use a small model to represent much larger graphs.

The Mathematics of Everyday Language. Keith J. Devlin (Center for the Study of Language and Information, Stanford University). Devlin has long been a spokesman—and showman!—for the mathematical community at large, but I have never before heard him speak on his own work. This talk was an excellent review of the entire sweep of modern linguistics, which happens to have been an early passion of my own. (”Modern” here means essentially post-Chomsky.) Without ever directly addressing the question, he made clear why a lecture on linguistics is approprriate for a mathematical conference.

The Shapes of Sacred Space: The Geometry of Ancient Maya Art and Architecture. Christopher Powell (Maya Exploration Center). For me, the phrase “sacred space” conjures up nothing but skepticism, so I went into this talk with an attitude. I came out with it, too. Powell and his colleagues have gone through measured drawings of Maya ruins looking for patterns such as golden-section rectangles and ratios that approximate the square root of 2. They found some, confirming their hypothesis. And when they failed to find such patterns, that also confirmed the hypothesis, because Maya craftsmen sometimes introduced deliberate imperfections as a gesture of humility before the gods. Also, the underlying “sacred” geometry is sometimes hidden, because it is the secret knowledge of shamans. Perhaps Powell is right about all this, but I would like to know what kind of observation would persuade him that his hypothesis is false. Also, how do you measure eroded, collapsed ruins accurately enough to be confident about distinguishing 1.618 (the golden ratio) from 1.600 (8/5), or 1.732 (the square root of 3) from 1.75 (7/4)? Despite all my doubts, however, one aspect of Powell’s work suggests a promising avenue of further research. He has been working with modern builders in Guatemala and southern Mexico, and he reports that they employ geometric methods that produce some of the same ratios.

Baseball Decision-Making with Markov Chain Models. Thomas W. Polaski (Winthrop University). Bunt or swing away? Steal second or try the hit-and-run? Considering only the decisions facing the manager of the team at bat, Polaski models a baseball game as a finite-state machine. Each event in the game—a hit, a walk, an out, etc.—is represented as a transition from one state to another, with an attached probability. For example, in a state with one out and a runner on first, a successful sacrifice bunt would produce a transition to a state with two outs and a runner on second. But a failed bunt—a double play—leads to a state with three outs, which is an “absorbing” state, meaning the end of the inning. By adopting a few simplifications, Polaski models a half-inning of baseball with just 28 possible states and makes predictions about the wisdom of various choices. A comparison with 50 years of major-league statistics suggests that his model is not too far from what happens in the dugout. Nonetheless, I have a hard time thinking of Casey Stengel as a finite-state machine.

Small Gaps between Prime Numbers: The Work of Goldston-Pintz-Yildirim. Kannan Soundarajan (University of Michigan, Ann Arbor). Soundarajan began by pointing out that it’s been quite a good millennium, so far, for work on prime numbers. In the first few years we’ve had a proof that testing primality can be done in polynomial time, we’ve had the work described here on small gaps between primes, and we’ve had another intriguing result (see below) on primes in arithmetic progression.

What’s a small gap between primes? Except for 2 and 3, no consecutive integers can both be prime, so the smallest possible separation between two prime numbers is 2. Among the first few hundred primes, such “twins” are fairly common—3 and 5, 5 and 7, 11 and 13, 17 and 19, 29 and 31, 41 and 43…. But they get sparse as you go farther out the number line. Nevertheless, a celebrated conjecture says there is no end to twin primes; there are infinitely many of them, and they can be found even among arbitrarily large numbers. Proving this conjecture would be very big news in number theory. Dan Goldston, János Pintz and Cem Yildirim have not done that, but they’ve taken a step in the right direction. Soundarajan explains: “Resolving a long-standing open problem, they proved that there are infinitely many primes for which the gap to the next prime is as small as we want compared to the average gap between consecutive primes.”

One might ask: Why is this work being described by Soundarajan rather than by Goldston, Pintz or Yildirim? The answer is that the talk was part of a special session on “current events,” an innovation now in its fourth year at the Joint Mathematics Meetings. The talks in this series are modeled on those of the Bourbaki seminars held in Paris since 1948, where it’s a tradition for one mathematician to give an expository account of someone else’s work. The American version of this scheme is working very well; the “current events” talks are always among the best and best-attended events of the annual meeting. Soundarajan’s lecture was a thing of beauty. (Soundarajan is the co-recipient, along with Manjul Bhargava, of the first Ramanujan Prize awarded by the Shanmugha Arts, Science, Technology, Research Academy (SASTRA) in Tamil Nadu, India. But there’s another Ramanujan Prize—how confusing!)

Like the Bourbaki seminars, the current-events lectures are accompanied by printed notes of each talk. A pamphlet with the notes was handed out at the meetings, but they will also eventually be published online and in the Bulletin of the American Mathematical Society.

Patterns of primes. Ben Green (University of Bristol). Among the twin primes is one set of triplets—3, 5 and 7—but a little thought shows there can’t be any more: If p is a prime greater than 3, then either p+2 or p+4 must be divisible by 3, and hence is not a prime. Likewise there can’t be any prime quadruplets separated by intervals of 2. What about arithmetic progressions with larger differences between successive primes? Here is a 10-member progression of primes with a common difference of 210: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089. Two years ago, Ben Green and Terence Tao proved that the primes including arbitrarily long arithmetic progressions (arXiv preprint). This is one of those cases where the result didn’t come as much of a surprise, but the proof did. No one had seriously doubted that arbitrarily long progressions exist, but until Green and Tao showed the way, proving it seemed very difficult.

The proof itself remains very difficult. It was the subject of a “current events” lecture by Bryna Kry at last year’s Joint Meetings; this has just been published. This year, one of the authors gave an insider’s account.

The work on small gaps between primes and the theorem on arithmetic progressions of primes have interesting connections. It was an early false start by Goldston and Yildirim that gave Green and Tao a key tool for their proof. And the two results apparently have deeper connections. Green commented, “If you don’t have arbitrarily small gaps, then there must be something very weird about primes in arithmetic progression.”

Longest alternating subsequences of permutations. Richard P. Stanley (MIT). In the past decade or so, there’s been a surprisingly big fuss over what might seem to be a very small question: What is the distribution of the longest increasing subsequence in a random permutation of integers? Here’s an example of such a permutation—a random ordering of the integers from 0 through 9:

{2 4 9 6 3 5 0 7 1 8}

A subsequence of the permutation is a set of numbers drawn from this list in order, from left to right, but the numbers needn’t be consecutive elements of the list. For example, {2 6 8} is a subsequence of the permutation—indeed, it is an increasing subsequence. The process of searching for the longest increasing subsequence has a certain tension built in to it: You want to start as far to the left as possible but you also want to start with a small number, and those two desiderata may be in conflict. In this case the longest increasing subsequences have five elements, and there are three of them: {2 3 5 7 8}, {2 4 5 7 8} and {2 4 6 7 8}.

Finding the longest subsequences in any specific permutation is not much of a challenge (but see the note below). What interests mathematicians is the distribution of lengths of longest subsequences for large samples of permutations. After much labor, the exact nature of that distribution was pinned down a few years ago by Jinho Baik, Percy Deift and Kurt Johansson. The answer turns out to be a very complicated mathematical object. It was worth expending all that effort to find the answer because the longest-increasing-subsequence problem has connections to many distant areas of mathematics and physics, even including the airplane boarding problem discussed here a few days ago. (If you want to know more, see the review article by David Aldous and Persi Diaconis.

Richard P. Stanley has looked at a variation on this problem: instead of counting increasing subsequences, he looks at alternating subsequences, those with a “sawtooth” profile of alternating ascents and descents. In the permutation given above, the longest alternating subsequences have eight elements. There are five of them: {2 4 3 5 0 7 1 8}, {2 6 3 5 0 7 1 8}, {2 9 3 5 0 7 1 8}, {4 6 3 5 0 7 1 8} and {4 9 3 5 0 7 1 8}. Why do alternating sequences grow longer than increasing ones? Basically, because there are more ways to form an alternating subsequence. It turns out that the distribution of longest alternating subsequences is much easier to describe and understand than that of longest increasing subsequences. On the other hand, so far these sequences have none of the ramifications or applications of the increasing ones. For more, see the online Postscript version of Stanley’s talk.

Note: I remarked above that it’s not much of a challenge to find the longest subsequences in a specific permutation, but I have to confess that the task gave me a spot of trouble. I didn’t trust myself to identify the longest increasing and alternating subsequences by hand, so I wrote a little program to do it. I thought that would take a few minutes. But generating subsequences is one of those problems that looks easy only until you decide you’d like to get the right answer.

Update (July 7, 2006): A little late, I’ve just learned that Harold Widom of the University of California at Santa Cruz has proved that the distribution has the form conjectured by Stanley. Widom’s paper is here.

“It would have been a very enjoyable ride altogether, that evening’s spin along the banks of the Rhine, if I had not been haunted at the time by the idea that I should have to write an account of it next day in my diary. As it was, I enjoyed it as a man enjoys dinner when he has got to make a speech after it, or as a critic enjoys a play.”

Jerome was a blogger. The diary he mentions in the passage above was not a private journal for his inmost thoughts; it was a travelogue, which would be published as soon as he got back to London. What’s more, his companions on that evening spin along the banks of the Rhine knew perfectly well that they would soon be reading their own words filtered through Jerome’s imagination, and if they said something particularly asinine, the whole world would know about it. This knowledge must have raised the anxiety level for both the author and his friends.

In the modern age of blogging, nothing has changed but the time scale. When I take a stroll with friends along the banks of the San Antonio River, they don’t have to wait until we all return home to read my account of the evening. They can have it with their breakfast the next morning. Fortunately for them and me, my friends never say anything asinine; our conversations are filled with scintillating wit.

I am here in San Antonio for the annual Joint Mathematics Meetings, an event I have attended for the past 10 or 12 years. Large academic gatherings are all alike, but each one is alike in its own way. This one is distinguished by its jointness: There are two main sponsoring organizations—the American Mathematical Society and the Mathematical Association of America. Roughly speaking, the AMS represents the interests of research mathematicians, whereas the MAA has a focus on the teaching of mathematics at the undergraduate level. There’s also the National Association of Mathematicians, the Association of Women in Mathematics, the Society for Industrial and Applied Mathematics, and the Association of Symbolic Logic, all of which are also sponsors of the Joint Meetings, plus the National Council of Teachers of Mathematics, which is not (officially) represented here. If we could start over, it seems possible that the world of mathematics could get along with somewhat fewer societies, associations, and councils—but it’s too late for that. We may as well celebrate the diversity and enjoy the jointness.

As a science writer attending these meetings, I feel I should try to sample a bit of everything, but I gravitate to the AMS sessions, the ones with new research results to report. This isn’t just elistism and showing off (although those reasons would be more than enough). Now that mathematics is such a pop phenomenon, with a spate of math movies and plays and even a TV show, I have to dig deeper to find a topic I can have to myself for a little while. This week, I’ve been hanging out in the AMS Special Section on Mahler Measure and Heights of Polynomials, and so far I have not noticed crowds of reporters in the back of the room. I hope to write a little something on the subject before USA Today ruins it for me. But I’m not quite ready yet.

In the meantime, I’d like to say something about that pop phenomenon. Several years ago, Bob Osserman of the Mathematical Sciences Research Institute in Berkeley pointed out to me that some sort of cultural shift seemed to be underway, as mathematics was going from unspeakable to inescapable in various areas of the arts and entertainment. At the time, Tom Stoppard’s play “Arcadia” and the film “Good Will Hunting” were both popular hits. I was relentlessly skeptical. It’s just an illusion, I said; there have always been such works, but we forget them. Or if it’s real, it won’t last. If it lasts, it will do more harm than good. A few years later, at another of these Joint Meetings, I was the designated naysayer in a panel discussion on mathematics and the movies, organized by Allyn Jackson and Keith Devlin. On this occasion the film version of “A Beautiful Mind” had just opened. I took the dour position that no one really cared about mathematics; they just wanted stories about oddball geniuses. Last year at the Joint Meetings, we saw previews of a new television series, “NUMB3RS.” I predicted that it wouldn’t last to the end of its first season. This year, the Joint Meetings included a special reception to celebrate the fabulous success of “NUMB3RS,” attended by Judd Hirsch, among other bold-face names. I didn’t go. It’s not that I’m bitter or a snob or a sore loser. It’s just that I couldn’t be pulled away from a fascinating session on probability and stochastic processes.

The mathematical community seems to have adapted gracefully to its newfound celebrity. Rather than growing conceited, it may even be taking itself a little less seriously than it once did. For the past few years, a highlight of the meetings has been a quiz show called “Who Wants to Be a Mathematician?,” in which local high school students compete for cash prizes. The TV show that inspired this idea did not fare as well as “NUMB3RS,” but the mathematical spinoff is still going strong, conducted with great showmanship by Mike Breen and Annette Emerson of the AMS and Bill Butterworth of DePaul University.

This year there was an even wilder event: The Great Pi/e Debate, where Colin Adams and Tom Garrity (both of Williams College) stood up as champions for those famous numbers. Like any good debate, it was full of bombast and devoid of content. Also, the humor was not excessively sophisticated. The crowd loved it, but I have to report that I was slightly disappointed. I had actually come to learn something, and in particular I had hoped to solve a small, recurrent, personal problem. I write for an audience of nonspecialists, and when I mention pi or e, I sometimes need to append a brief phrase explaining or introducing those symbols. That’s easy for pi; as Adams quickly pointed out, pi is the ratio of a circle’s circumference to its diameter. But what is e? The customary identifying phrase is “the base of the natural logarithms,” but that’s not terribly helpful; those who need a definition of e probably also need a little help with “natural logarithms.” Garrity, in his (winning) defense of e, took a different approach, emphasizing that the function y = e^x is its own derivative. This is an interesting and important property of e, but again it’s not the pithy slogan I was looking for. On the other hand, solving my little problem was hardly the aim of the debate. I’m looking forward to next year’s mud-wrestling/wet-teeshirt contest between phi and gamma.

I am at gate C21 at Houston Intercontinental, en route to San Antonio. The flight is late and overbooked; there’s a crowd of hopeful standbys at the podium. The first-class plutocrats are already aboard, and now the rest of us are filing on, one section at a time. “Passengers in rows 25 to 29 are invited to board the aircraft” was the first announcement. Ten minutes later they called for rows 20 to 29. My boarding pass is for seat 14B.

Frequent flyers understand the rationale behind this routine. By filling the airplane from back to front, the theory goes, passengers sitting in the rear won’t have to wait in the aisle while the couple in 8-A and 8-B stow their luggage, fetch blankets and pillows, argue over who gets the window, settle into their seats, get up again to retrieve a book from the overhead bin, and then discover that their tickets are actually for 18 A and B.

A recent paper reveals the awful truth. The airlines’ last-shall-be-first strategy doesn’t work. We might be better off lining up in random order.

The paper, posted in the physics division of the arXiv, is by Eitan Bachmat, Daniel Berend, Luba Sapir and Natan Stolyarov (all of Ben-Gurion University) and Steven Skiena of the State University of New York at Stony Brook. The authors call forth quite a dazzling array of high-powered mathematical tools in the course of their analysis. The geometric context of the problem turns out to be a two-dimensional spacetime with a Lorentz metric; there’s a combinatorial element to the story, involving longest increasing subsequences; from there, I’m afraid it gets even deeper, and at one point we find ourselves dealing with “the normalized discrepancy of the largest eigenvalue of an N x N matrix in the Gaussian unitary ensemble (GUE).”

For all that, the ultimate outcome is clear enough, and it even makes intuitive sense. Suppose there are 29 rows of seats with six seats per row, and the flight is full. Suppose further that the last-first policy can be enforced perfectly, so that all the passengers in row 29 are first in line, followed by those in row 28, and so on. Boarding should be a completely orderly process, with everyone sitting down after the minimum possible delay, no? No. The problem is that no one in rows 1 through 28 can reach their row until at least some of the six passengers in row 29 seat themselves. Then, everyone forward of row 28 has to wait for the next six people to sort themselves out. Under this regime the total boarding time is proportional to N, the total number of passengers. Lining up in random order offers a good chance of getting everyone aboard in time proportional to the square root of N.

If we insist on trying to find an improvement over the random result, we might be better off lining up with all the window seats first, then the middles and finally the aisles—a scheme that some airlines are apparently trying, with loading “zones.” Another algorithm for an airplane with 29 rows of six seats each would line the passengers up according to row number in this sequence: 29 23 17 11 5 28 22 16 10 4…. Then the question becomes: Is the flying public ready for announcements of the form, “We are now boarding all rows N where N is congruent to 5 modulo 6″?

Addendum: Once I finally got aboard, I discovered a further complication: The airplane didn’t actually have 29 rows. My seat in 14B was directly behind row 12. Evidently, Continental Airlines suffers from triskaidekaphobia.

Ask any molecule what it thinks about the second law of thermodynamics and it will laugh at the question. All the same the molecules, collectively, uphold the second law.