The National Academy of Sciences has decided to recognize a “paper of the year” published in its Proceedings. Surprisingly, the first paper to be anointed in this way is by a student. Even more surprising, it’s a mathematical paper. Why should these facts surprise me? Not because I think student mathematicians are unlikely to do work of distinction. On the contrary. But even though the National Academy is not quite the old-fogey’s club it once was, papers authored solely by students are not all that common in PNAS. And mathematical papers make up a tiny fraction of the journal’s content, which is dominated by work in the life sciences.

The winning paper is titled “Partition congruences and the Andrews-Garvan-Dyson crank” (PNAS October 25, 2005, vol. 102, no. 43, pp. 15373–15376). The author is Karl Mahlburg, a doctoral candidate in the Department of Mathematics at the University of Wisconsin in Madison, studying with Ken Ono. A commentary by Ono and George E. Andrews of Pennsylvania State University provides some background. There is also a superb nontechnical account of the work, written by Erica Klarreich for Science News.

Every morning I go fishing in the arXiv. Or at least that’s the way I’ve been thinking about this daily ritual: I cast my net over the waters and look to see what strange and wonderful creatures I’ve brought up from the deeps. Today it hit me that I have the metaphor backwards. I’m the fish, and what’s going on here is that the arXiv dangles lures in front of me to see if I’ll take the bait. Some days I’m just not biting. Today, however, I was snapping at one hook after another. I’ll be the first to admit that I sometimes choose a brightly colored bit of fluff in preference to a nutritious worm. (Although I did pass on today’s proof that P ≠ NP—or was it the converse?)

physics/0603229
Title: Laws of Graph Evolution: Densification and Shrinking Diameters
Authors: Jure Leskovec, Jon Kleinberg, Christos Faloutsos

How do real graphs evolve over time? What are “normal” growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log (log n))).

cond-mat/0603718
Title: Statistical Mechanics of Community Detection
Authors: Joerg Reichardt, Stefan Bornholdt

Starting from a general ansatz, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass…. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further we show, how hierarchies and overlap in the community structure can be detected….

physics/0603215
Title: Computer simulation of language competition by physicists
Authors: Christian Schulze, Dietrich Stauffer

… About every ten days a human language dies out, and in Brazil already more than half of the indigenous languages have vanished as a result of the European conquest. On the other hand, Latin has split in the last two millennia into several languages, from Portuguese to Romanian…. Thus similar to biology, also languages can become extinct or speciate into several daughter languages.

In contrast to biology, humans do not eat humans of other languages as regular food, and thus one does not have a complex ecosystem of predators eating prey as in biology. Instead, languages are meant for communication, and thus there is a tendency of only one language dominating in one region, like German in Germany etc. Will globalisation lead to all of us speaking one language in the distant future? For physics research, that situation has already arrived many years ago….

Thus in the history mankind we may have had first a rise, and later a decay, in the number of different languages spoken. In Papua New Guinea there are now 10³ languages, each spoken by about 10³ people; can this situation survive if television and mobile phones become more widespread there?

While we cannot answer these questions, we can at least simulate such ”survival of the fittest” among languages, in a way similar but not identical to biology….

physics/0510151
Title: Trainspotting: Extraction and Analysis of Traffic and Topologies of Transportation Networks
Authors: Maciej Kurant, Patrick Thiran

The knowledge of real-life traffic pattern is crucial for good understanding and analysis of transportation systems. This data is quite rare. In this paper we propose an algorithm for extracting both the real physical topology and the network of traffic flows from timetables of public mass transportation systems.

math.SP/0603630
Title: Sharp bounds for eigenvalues of triangles
Authors: B. Siudeja

The purpose of this paper is to prove the following theorem.

Theorem 1.1. Let T be a triangle in a plane of area A and perimeter L. Then the first eigenvalue λT of the Dirichlet Laplacian on T satisfies

The constants 9 and 16 are optimal.

math-ph/0603065
Title: Quasicrystals: algebraic, combinatorial and geometrical aspects
Authors: Edita Pelantová, Zuzana Masáková

math-ph/0603068
Title: A Spinorial Formulation of the Maximum Clique Problem of a Graph
Authors: Marco Budinich, Paolo Budinich

In this paper we propose a new representation of the maximum clique problem in complex space. After a brief review of this famous NP-complete problem, we show how the adjacency matrix of a graph can be expressed as the square of a symmetric complex matrix. The vectors forming this matrix have zero length and Cartan has shown that this geometry can be treated elegantly with spinors…. We finish with a formulation of the maximum clique problem in this formalism and show that each graph uniquely identifies a spinor whose properties surely deserve deeper studies.

The invention of the puzzle we now call Sudoku is generally credited to Howard Garns, an architect from Indianapolis. His first puzzles, which were known then as Number Place, were published in 1979. But now a curious precedent has turned up. More than 20 years earlier, in the 1950s, W. U. Behrens of Hannover, Germany, discussed very similar grids filled with numbers—not as a game or a puzzle for the amusement of newspaper readers but as a design for agricultural experiments. The connection is pointed out in a new paper (PDF) by R. A. Bailey and Peter J. Cameron of the University of London and Robert Connelly of Cornell University.

Both Sudoku and the Behrens designs trace their heritage back to Latin squares, studied by the 18th-century mathematician Leonhard Euler. In an n-by-n Latin square, each of the numbers from 1 through n appears exactly once in each column and row. A standard Sudoku puzzle is a 9-by-9 Latin square with the additional constraint that each number from 1 through 9 also appears exactly once in each of nine 3-by-3 blocks, or regions, into which the grid is subdivided.

What could this possibly have to do with agriculture? Suppose you’re testing several new seed varieties to see which ones produce the best yield. When you lay out test plots in a field, you need to be careful to avoid biases, such as putting all the samples of one variety in the area that has the most water or the richest soil. A Latin-square arrangement is a good start on such a design. With n crop varieties, an n-by-n Latin square assures that each plant type is equally represented in every column and every row, compensating for many common patterns of variation, such as a field that gets steadily moister from one side to the other. But a Latin-square arrangement cannot guarantee fairness in the presence of other patterns, such as compact patches of better or worse soil. And so Behrens proposed choosing designs from a subclass of all Latin squares, namely those in which numbers are distributed evenly not only among the columns and rows but also in predefined blocks. This subclass of Latin squares he called gerechte designs, meaning fair or impartial.

The blocks in Behrens’s designs are not always squares (obviously, an n-by-n array can be subdivided into smaller squares only if n itself is a perfect square). Here is a pattern he proposed for the case of n = 5. I have erased some of the numbers, in order to turn the diagram into an easy mini-pseudo-Sudoku puzzle:

Behrens did go on to consider the case of a 9-by-9 grid with 3-by-3 blocks, and so the following figure may well represent the first published Sudoku solutions:

The figure is taken from: Behrens, W. U. 1956. Feldversuchsanordnungen mit verbessertem Ausgleich der Bodenunterscheide. Zeitschrift für Landwirtschaftliches Versuchsund Untersuchsungswesen 2:176–193. (Scanned copy courtesy of Robert Connelly.) For the case of 4-by-4 grids, Bailey, Cameron and Connelly note an even earlier precedent: Yates, F. 1939. The comparative advantages of systematic and randomized arrangements in the design of agricultural and biological experiments. Biometrika 30:440–466.

Apart from illuminating the prehistory of Sudoku, Bailey, Cameron and Connelly also investigate a number of variations where additional symmetry conditions are imposed. For example, can you create a puzzle (on the standard Sudoku grid) where no number appears in the same relative location within any two of the nine blocks? Connelly also gives further examples and discussion at his web site. Some similar variations have also appeared on Ed Pegg’s marvelous MathPuzzle site.

Luna B. Leopold, the foremost American student of rivers and the landscapes they create, died February 23 at age 90. I never met him, but I’ve been a follower and a fan of his work, which I first encountered in 1966, when Scientific American published an article titled “River Meanders,” by Leopold and W. B. Langbein. Not many magazine articles stay with you for 40 years; this one was unforgettable. Before I read the article, landform features such as the sinuous path of a stream had seemed quite arbitrary or accidental—or they would have seemed so if I had ever bothered to think about them at all. Now they were suddenly revealed to have an explanation, an internal logic. With a bit of physics and mathematics and imagination, you could follow the steps of the dance by which rivers carve the land and the land guides the rivers.

Many years later I caught up with Leopold’s major textbook, Fluvial Processes in Geomorphology (co-authored with M. Gordon Wolman and John P. Miller, published in 1964 by W. H. Freeman). This is a much more engaging and accessible work than the title might suggest, and I can recommend it without reservation as summer-vacation reading, especially if you’re going to spend your vacation in a fluvial landscape—perhaps kayaking the Colorado. The book begins with a chapter composed almost entirely of questions provoked by simply looking at the land. Why do the Sandia Mountains in New Mexico rise abruptly and steeply on their west front but slope more gradually to the east? How did the Susquehanna River in Pennsylvania carve a channel straight through Kittatinny Mountain, Blue Mountain and Tuscarora Mountain, whereas lesser streams flow parallel to these ridges? How did ancient beaches on the coast of California wind up stranded 30 or 40 feet above sea level? In 1964 Leopold and his colleagues didn’t yet have answers for all these questions, but they did have a methodology for approaching them, as well as faith that the forces shaping the surface of the earth were something we could ultimately expect to understand.

The methodology was largely mathematical, and it’s interesting that Leopold, Wolman and Miller felt it necessary to apologize for that. “We are aware that the feelings of professional geomorphologists about numbers, graphs, and formulas range from acceptance and enthusiasm to bewiderment and forthright hostility. We have not gone out of our way to be mathematical, but whenever we felt that mathematics contributed either clarity or brevity to the discussion, it has been used.”

A notable early success of Leopold’s quantitative method was his discovery that the shape of a river channel and the flow of water through it can be understood through a set of simple power laws. At any given point along the course of a river, the width and the depth of the channel and the velocity of the water are each proportional to some power of the total quantity of water passing that point per unit time. For most rivers, the total volume increases steadily downstream; hence the width, the depth and the velocity must all increase monotonically as a river flows from its headwaters to its mouth. When this finding was first published (in a 1953 paper written by Leopold and Thomas Maddock, Jr.) it was surprising and controversial. Everyone knew that rivers get wider downstream, but the common impression was that they also get slower (because the landscape is generally flatter), and in most cases shallower (because of sediment buildup). Leopold and his colleagues made extensive measurements along some 20 rivers and showed that it just isn’t so. Width, depth and speed all increase steadily in the downstream direction. (The graphs below are for the Powder River at Locate, Montana. Straight lines plotted on a log-log scale are the telltale mark of a power law.)

Leopold’s explanation of river meandering also came as a surprise to many people. One might guess that anything falling from a height—including water flowing from the mountains to the sea—would seek out the line of steepest descent, or in other words the shortest path to the bottom. But a meandering river is obviously not following the shortest route to the sea. In some cases the length of the river is four or five times that of a direct route.

The image at the top of this article, made from the Space Shuttle Endeavour in 1994, shows the elaborate meanders of the Tobol and Tavda rivers in the West Siberian Plain. Why do rivers adopt (or create) such sinuous channels? The key to understanding Leopold’s answer to this question is the curvature of the path—a measure of how sharply it twists and turns. Assuming the path is reasonably smooth, it’s possible to measure the curvature at each point along a river’s course and to calculate a total curvature: the sum (or the integral) of the curvatures measured at all points along the path. Actually, the quantity of greatest interest is the sum of the squares of all the measured curvatures. Leopold found that for any given total channel length, the favored route is the one that minimizes the total squared curvature. In other words, the river tries to distribute its “budget” of curvature as evenly as possible all along its course, avoiding sharp bends where the square of the curvature would be very large. If such a sharp bend should ever develop, its banks would be rapidly eroded, restoring a minimum-total-curvature configuration.

I am fascinated by the way that Leopold and his colleagues happened upon this least-curvature principle. In the 1966 Scientific American article Leopold and Langbein write:

We first recognized the principal characteristics of the actual curve traced out by a typical river meander in the course of a mathematical analysis aimed at generating meander-like curves by means of “random walk” techniques…. In our random-walk study one of the constraints we adopted was that the path was to begin at some point A and end at some other point B in a given number of steps. In other words, the end points and the length of the path were fixed but the path itself was “free.”

The mathematics involved in finding the average, or most probable, path taken by a random walk of fixed length had been worked out in 1951 by Hermann von Schelling of the General Electric Company. The exact solution is expressed by an elliptic integral, but in our case a sufficiently accurate approximation states that the most probable geometry for a river is one in which the angular direction of the channel at any point with respect to the mean down-valley direction is a sine function of the distance measured along the channel.

Note that the path itself is not a sine wave; it is a curve generated by letting the direction vector vary sinusoidally as one moves along the length of the path. (Leopold calls it a “sine-generated curve.”)

There’s more to this story than I can tell here. If the goal is to minimize the total squared curvature of the path, that’s easy enough to do: Just draw a straight line from A to B. This suggests again that the line of steepest descent ought to be the favored route for a river. The reason for lengthening the path and then bending it into a sinuous curve is not fully explained in the Scientific American article, but Leopold and Langbein discuss it in a 1962 paper titled “The Concept of Entropy in Landscape Evolution.” Here they also give details about some remarkable early experiments in computer simulations of river action.

Leopold transformed the study of landscapes by insisting on quantitative methods, but he was certainly not just a numbers guy. Luna Leopold was the son of Aldo Leopold, one of the founders and heroes of the conservation movement in the U.S. It was Luna who assembled and edited his father’s essays, which were published posthumously in 1948 as A Sand County Almanac. Luna Leopold himself later became a passionate advocate for environmental preservation, entering into the controversies over the Alaska pipeline and a proposal to build an airport in the Florida Everglades.

Leopold studied civil engineering and meteorology before taking a Ph.D. in geology at Harvard. He had a long career at the U.S. Geological Survey, serving as Chief Hydrologist for a decade. During his years in Washington he continued doing field work by setting up gaging stations on Watts Branch, a stream that flows into the city from the eastern Maryland suburbs, joining the Anacostia River a few miles from the Capitol. In a 1994 book, A View of the River, Leopold urged amateurs in “backyard hydrology” to do the same with any nearby stream, and he offered some practical advice: “The easiest way to measure velocity is by floats, and the best float is an orange peel. It has just the right specific gravity to float nicely at the surface, it is brightly colored and thus easily seen, and it is readily available.”

After leaving the Geological Survey in 1972, Leopold taught at the University of California, Berkeley. He was still actively working in the weeks before his death. In an obituary for the Washington Post Patricia Sullivan writes:

Well known for his scientific fieldwork, he also made bows and arrows, hunted and fished, rode horses, composed piano and guitar music, danced, flew planes, painted landscapes, wrote poetry, bound books, acted on stage, built furniture, claimed to cook strawberry shortcake in a camp Dutch oven and told campfire stories. He floated on a raft through the Grand Canyon to measure the depth of the Colorado River.

The portrait below (courtesy University of California, Berkeley) shows him at work on the East Fork River near Boulder, Wyoming, circa 1974, “attired in his typical Stetson, Filson cruiser coat and gloves.” When we make the movie of his life, we’re going to have to bring back Gary Cooper.

One further note: The Department of Earth and Planetary Science at Berkeley has set up a web site, The Virtual Luna Leopold Project, that lists 182 of Leopold’s publications and provides PDF copies of more than 100 of them, including all the articles and papers mentioned above, and also an excellent American Scientist article from 1962, titled simply “Rivers.”

But now I’m back, and the announcement you are reading at this moment should be followed—or is it preceded?—by several more posts in short order.

Actually, to tell the truth, I’ve gone nowhere geographically, but I’ve been busy finishing a column for the next issue of American Scientist.

I’ve been away for a couple of weeks.

I need to explain my neglect of this blog.

I used to play hooky at the library. That tells you what kind of reckless, rebellious youth I was. When I skipped school, I would take the subway downtown and spend the day in the sunstruck Science and Industry room of the Free Public Library of Philadelphia. Another time, at the end of my junior year in high school, I told my parents I was going to the beach for the summer, a fib I had concocted so they wouldn’t worry about me; I actually ran away to the Van Pelt Library of the University of Pennsylvania, where I wrote a novel about a kid who goes to the beach for the summer. (Yes, I know, what a waste! Next time I’ll write about a kid who goes to the library for the summer.)

I confess these truancies in order to make the point that I have a longstanding, sentimental attachment to libraries. This is not a matter of nostalgia; I’m not someone who wants to abolish the Internet and bring back the card catalogue. But entering a library always brings me an intense anticipatory pleasure, tinged with the remnant sensation that there’s something mildly illicit about it: I’m not doing what I’m supposed to be doing, I’m doing something better.

This weekend I have again run away to the library, with the excuse of tracking down a few fugitive references for an upcoming column. One item I needed was at the Library of Congress. My last visit there was some six years ago (pre-9/11), and I expected a bristling security gauntlet. Strolling up to the library from the Capitol South Metro station, I couldn’t help noticing how Washington has become a city of bollards and barricades. The measures to fend off truck bombs—especially the massive steel barriers that rise hydraulically out of the street—are somehow more conspicuous than the monuments they protect, just as at the zoo we see the cages more than the animals.

Inside the library, however, not much has changed—and happily it still feels like a library, not a prison or an army base. Renewing my reader card took less than five minutes; getting through the x-ray and the magnetometer and the body scan was as easy as boarding an airplane; soon I was installed at a mahogany desk under the Italianate octagonal dome of the Jefferson Building. I think this room may be my favorite among all library locales. Yes, the main reading room at the British Museum is bigger, and Room 315 at the New York Public Library carries more clout in American literary circles, but the Jefferson reading room has them beat for charm and comfort. It’s just like Washington itself. I think Henry Adams said—or at least he should have said—that no matter how big and powerful Washington becomes, it will always be a provincial capital. Likewise the Library of Congress, though a truly great library in some respects, will always be a place where dabblers like me can come and pretend they’re doing real scholarship.

(By the way, has anyone ever pointed out that the reading room of the New York Public Library is all rectilinear rows and columns, like the Manhattan streets, whereas the reading room of the Library of Congress has concentric rings and radial avenues, like the city that surrounds it?)

Along with southern charm, the LC also offers remarkable efficiency. Books burble up out of the unseen stacks on a conveyor system that makes the softest possible ticking and swishing noises, quieter than silence itself. In less than 40 minutes a crepe-soled messenger delivered the volume I’d come all this way to see:

Wagner, Rudolf: Gespräche mit Carl Friedrich Gauß in den letzten Monaten seines Lebens. Herausgegeben von Heinrich Rubner. Göttingen: Vandenhoeck & Ruprecht. (Series: Nachrichten der Akademie der Wissenschaften in Göttingen. Philologisch-Historische Klasse; Jahrgang 1975, Nr. 6.) P3 .N33 Jahrg. 1975, Nr. 6

Now if only I could read German. I shouldn’t have cut so many classes.