I’m still busy digitizing a lifetime’s accumulation of clippings from magazines and journals, along with heaps of old tech reports, memos, and miscellaneous other cruft. There’s something slightly eerie about the process. So far I’ve emptied out a dozen file drawers, run several hundred pounds of paper through the scanner, and created thousands of PDFs. Yet my laptop is not a gram heavier. The glib explanation is that I’m just scraping pure information off the pages, leaving behind the ink and cellulose; I’m saving the bits and recycling the atoms. But is information so readily dematerialized? One of the manila folders I have just dredged up out of a filing cabinet is bulging with publications by the late Rolf Landauer, including several papers on the theme “Information is physical!”

I first met Rolf circa 1980. I had written a brief Scientific American article about some recent developments in optical computing technologies, and Rolf called to tell me I should never do anything so reckless and foolish and tasteless again. He took a dim view of photonics. This initial encounter was not a promising start to a friendship, but we got over it. He put me on his mailing list, which meant that I got a fat envelope once or twice a year, with reprints or preprints of his own latest work and often copies of other papers he thought I should being paying attention to.

Four of the articles in my Landauer folder have very similar titles:

• Information is Physical (Physics Today, 1991).
• The Physical Nature of Information (Physics Letters A, 1996).
• Information is a Physical Entity (Physica A, 1999).
• Information is Inevitably Physical (In Feynman and Computation, 1999).

If Landauer had lived longer (he died in 1999), I like to think that the next installment in the series would have been titled even more emphatically: Information is Physical, Damn It!

In all of these essays, Landauer’s thesis is straightforward:

Information is inevitably tied to a physical representation. It can be engraved on stone tablets, denoted by a spin up or down, a charge present or absent, a hole punched in a card, or many other alternative physical phenomena. It is not just an abstract entity; it does not exist except through a physical embodiment. It is, therefore, tied to the laws of physics and the parts available to us in our real physical universe.

This notion is obvious and totally uncontroversial–except to those who think it’s totally wrong. Doubters tend to focus on mathematical entities. Surely the integers exist as abstractions, independent of stone tablets and punchcards, no? And triangles would have three sides even if all the matter in the universe were annihilated–right? When it comes to numbers like π and e, one might well argue that they can exist only as abstractions; they can never be given a complete physical representation.

Landauer did not argue strenuously for his constructivist position within mathematics itself, but he did take a hard line about mathematical methods in the physical sciences:

There is a tendency to think of mathematics as a tool which somehow existed before and outside of our physical world. Mathematics, in turn, allowed the formulation of physical laws which then run the world, much as a process control computer runs a chemical plant. Here, instead, we emphasize that information handling has to be done in the real physical world, and the laws of physics exist as instructions for information handling in that real world. It, therefore, makes no sense to invoke operations, in the laws of physics, which are not executable, at least in principle, in our real physical world.

Our accepted laws of physics invoke continuum mathematics, which is, in turn, based on the notion that any required degree of precision can be obtained by invoking enough successive operations. But our real universe is unlikely to allow an unlimited sequence of totally reliable operations. The memory size is likely to be limited, perhaps, because the universe is limited. Even in an unlimited universe it is a strong presumption to invoke the possibility of assembling an arbitrarily large organized memory structure. Furthermore, in a world full of deleterious processes including noise, corrosion, electromigration, incident alpha particles and cosmic rays, earthquakes and spilled cups of coffee, it would be unreasonable to assume that each step in an unlimited sequence of operations can be carried out infallibly.

Those alpha particles and spilled cups of coffee bring me back to my little document-scanning project–my kitchen-table version of Google Books. I am well aware that my digitized archives are not disembodied abstractions, that the information I’ve scanned from Rolf’s preprints is still physical even if it’s less tangible, and that the bits remain vulnerable to all the perils of a material world. Indeed, the thought of losing all the files I’ve scanned–now that the paper originals are beyond recall–makes me itchy to plug in the back-up drive.

But the process of replicating the bits–which is even easier than capturing them in the first place–sends my mind off on another tangent. As Rolf said, we can represent information in many physical forms: as marks on paper, as magnetized domains on a metal-coated disk, as packets of electric charge, as base pairs in a DNA molecule, as beads on an abacus. When we build machinery to process this information, we can choose among many different computing technologies: transistors, brass gears, neurons, rubber bands and tinker toys, quantum dots, even photons in optical waveguides (though Rolf despised that last possibility, and he was skeptical about the quantum dots).

Somehow, this proliferation of physical embodiments for information does not strengthen the conviction that information is subordinate to its physical representation. When we can write the same message in so many forms–everything from lines in the sand to holograms–the message itself begins to seem just as substantial as the physical medium, and perhaps more enduring. I have digital documents that began life on eight-inch floppy disks 20 years ago. The files have migrated a dozen times or more to other media: five-and-a-quarter-inch floppies, three-and-a-half-inch floppies, Zip drives, digital audio tapes, CD-ROMs, a succession of hard disks. Most of the physical objects making up that long chain of transmission have long since succumbed to coffee spills, corrosion and other hazards, or else they have simply gotten lost. Yet the data persists, a sort of standing wave in the river of hardware rushing toward obsolescence and oblivion. Under the circumstances, it can be hard to keep in mind that the information depends for its very existence on those delicate shards of matter. It goes against the grain of the whole apparatus of computer science, where automata theory, the Church-Turing thesis, and the Turing equivalence of programming languages all encourage us to think that abstractions come first, and implementation is secondary.

These musings are not meant as an attempt to refute Landauer’s assertion. I still have to concede that I cannot record or express a pattern of bits without resorting to some physical medium, if only the gray matter in my own head. But the notion sits uncomfortably; it’s a conundrum. I wish I had a chance to chat with Rolf about it. But, sadly, Rolf Landauer is no longer physical.

Note: As far as can tell, none of the four Landauer papers I mention above are available online without payment. I am therefore taking the liberty of posting my scan of Rolf’s preprint of the information-is-a-physical-entity paper. I would also like to call attention to two recent articles about Landauer: a discussion of his contributions to solid-state physics by Bertrand I. Halperin and David J. Bergman, and a biographical memoir by Charles H. Bennett and Alan B. Fowler.

Someone out there is being paid to post comments on bit-player.org–and doubtless on tens of thousands of other blogs as well. The comments are mostly bland and inoffensive, sometimes effusive, always hastily composed. “Thanks for article..good work,” they say. “Amazing!!” “i like your article and i will be wating your net article….”

The payload attached to each of these comments is a link to a web site that someone wants to promote. Some of the sites are selling goods or services; others are billboards full of pay-per-view ads; a fair number are mysterious to me, being written in languages I don’t understand. I would not be astonished to learn that some of the sites are distributing malware.

Years ago, the first wave of comment spam was powered by scripts that flooded blogs and wikis and forums with hundreds of postings full of program-generated gibberish and long lists of links. That abuse was stopped by captchas and other simple filters, like the one I’ve been using here on bit-player. Another important defense is the “nofollow” tag, which instructs search engines to ignore links in comments, thereby eliminating the incentive of gaining PageRank points.

The comment spam arriving now is not generated by a Perl script. Somewhere in the world a person is being paid to read these very sentences, then to prove his or her humanity to the Turing-test filter, and finally to write a few words in response and sneak in a paid link. I’m both fascinated and appalled to learn that the Internet economy can support this activity. What’s the going rate for writing comment spam? Is it worth a penny to get your link briefly exposed to the vast daily readership of bit-player.org? How about a tenth of a penny?

I have a sinking feeling that the people doing this work are themselves victims of a scam, and that they’ll never see even the tenth of a penny. They have probably succumbed to a 21st-century version of the ads I used to see on matchbook covers: “Work at home! Make $500 a week stuffing envelopes in your spare time!”

Of all the ways that poor and desperate people are exploited, this is not the worst. Presumably the work is safe and sanitary, and it even rewards literacy. Some of my comment spammers would surely have interesting ideas to contribute if only they had the luxury of time.

All the same, this kind of commercial graffiti is not something I want to encourage. The available countermeasures include prohibiting all links in comments, holding all comments until a moderator approves them, or requiring commenters to register with a verifiable email address. None of these options appeals to me, but I may have to consider them if the problem persists. For now, though, I’m going to continue the human approach–manually deleting spammy comments as quickly as I can get to them. I am also closing comments on all but the 10 most-recent items on bit-player; the spammers seem to favor older posts.

I have to add that spotting comment spam is not always as easy as you might think. Consider this comment, which came in response to a story about editorial changes at Scientific American magazine:

Many times, when i read your American Scientist columns, I have asked myself that is any other country’s scientist didn’t give anything to the world?

The text of the comment is pertinent to the topic; it raises a question that’s entirely appropriate in this context; and there’s clear evidence that the author has actually been reading bit-player (and even my American Scientist columns) rather than merely spewing comments at random. This is someone I would like to be able to welcome into the community. But the link associated with the comment was an ad for a web-hosting service, and another comment from the same IP number advertised a different service. Was I wrong to hit the delete button?

You’re welcome to comment below, but without spammy links, please.

As I have mentioned in the past, I’m fascinated by the acrobatics of bird flocks, especially the big congregations of European starlings that gather in the evening at this time of year. Evidently I’m not the only one with such an interest. In the past few years the subject has attracted the attention of quite a large flock of scientists, including not only biologists but also various luminaries in physics, mathematics and computer science.

Below are some notes on a few of the recent papers, but first I have to mention a classic from 20 years ago:

Reynolds, Craig W. 1987. Flocks, herds, and schools: a distributed behavioral model. Computer Graphics 21(4):25–33. Author archive.

This is the paper that began the modern era of flocking studies by proposing that animals could coordinate and synchronize their movements without any need for a leader or external cues. Others were thinking along the same lines at about the same time, but it was Reynolds who attracted wide notice with his enchanting computer animations of “boids” soaring through an imaginary three-dimensional space. Each individual in the flock acts according to simple, local, fixed rules, and the synchronized maneuvers emerge spontaneously.

Reynolds suggested three particular rules that might guide the behavior of each bird:

• Avoid collisions.
• Try to match the speed and heading of nearby birds.
• Move toward the center of the group in which you are flying.

Reynolds was working in computer graphics, and his ideas were soon taken up by movie studios and by the makers of video games. In a sense, his simulations only had to look right; they didn’t have to reflect what actually goes on in a starling’s head. But whether or not the birds were paying attention, students of animal behavior certainly were.

Much of the recent activity arises out of new field studies, conducted mainly by physicists.

Cavagna, Andrea, Irene Giardina, Alberto Orlandi, Giorgio Parisi, Andrea Procaccini, Massimiliano Viale and Vladimir Zdravkovic. 2008. The STARFLAG handbook on collective animal behaviour. 1: Empirical methods. Animal
Behaviour 76:217–236. Preprint.

Cavagna, Andrea, Irene Giardina, Alberto Orlandi, Giorgio Parisi and Andrea Procaccini. 2008. The STARFLAG handbook on collective animal behaviour. 2: Three-dimensional analysis. Animal Behaviour 76:237–248. Preprint.

This group, coordinated by Andrea Cavagna and Irene Giardina of the University of Rome La Sapienza, has been photographing starling flocks near the city’s main railroad station (the Termini), which is just a few blocks from the university. Using pairs of synchronized cameras, the observers have captured stereoscopic images and then applied special image-analysis software to reconstruct the three-dimensional trajectory of each bird. Similar techniques have been tried in the past, but only with small flocks (a few dozen birds). The Italian group has traced the motions of individual birds in groups of up to 2,600. The two papers cited above give technical details on how the data were gathered and analyzed.

Ballerini, Michele, Nicola Cabibbo, Raphael Candelier, Andrea Cavagna, Evaristo Cisbani, Irene Giardina, Alberto Orlandi, Giorgio Parisi, Andrea Procaccini, Massimiliano Viale and Vladimir Zdravkovic. 2008. Empirical investigation of starling flocks: a benchmark study in collective animal behaviour. Animal Behaviour 76:201–215. Preprint.

Ballerini, Michele, Nicola Cabibbo, Raphael Candelier, Andrea Cavagna, Evaristo Cisbani, Irene Giardina, Vivien Lecomte, Alberto Orlandi, Giorgio Parisi, Andrea Procaccini, Massimiliano Viale and Vladimir Zdravkovic. 2008. Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study. Proceedings of the National Academy of Science of the USA 105:1232–1237. Open access.

And here the same authors (with a few additions) report their results and conclusions. They base their interpretation on a computational model that is recognizably a descendant of the Reynolds scheme, but with one crucial modification. Reynolds and others assumed that each bird is influenced by all other birds within some fixed distance (a “metric neighborhood”); Ballerini et al. get a closer match to the data by assuming that a bird attends to the motions of a fixed number of near neighbors, regardless of distance (a “topological neighborhood”). In other words, the graph of interacting birds has nearly constant vertex degree; the typical degree is probably six or seven. The main significance of this algorithmic change is that it helps maintain the cohesion of the flock in spite of large variations in density.

Hildenbrandt, Hanno, Claudio Carere and Charlotte K. Hemelrijk. 2009. Self-organised complex aerial displays of thousands of starlings: a model. arXiv:0908.2677v1

Those same flocks at Termini have a role in this study as well; the model presented here draws on data from Ballerini et al. as well as videotapes made at Termini by Carere. (Carere is another physicist at Sapienza; Hildenbrandt and Hemelrijk are biologists at the University of Groningen.)

The model works on the same essential principles, but it differs in intellectual style and emphasis. Hildenbrandt et al. want to account for specific details of a flock’s behavior—not just the general tendency to fly in close formation but also the particular shapes of starling flocks, the maneuvers they perform, the altitudes they prefer, and so on. Reaching for this verisimilitude leads to a rather complicated model with many parameters in need of fine tuning, such as aerodynamic properties of the bird’s wing and body and banking angles in turns. Hildenbrandt et al. report some success in explaining the geometry of flocks (they tend to be horizontally flattened rather than spherical). They do less well in an attempt to account for an extra-dense layer of birds observed at the periphery of a flock.

Cucker, Felipe, and Steve Smale. 2007. Emergent behavior in flocks. IEEE Transactions on Automatic Control 52:852–862.

Chazelle, Bernard. 2009. Natural algorithms. Proceedings of the 20th Symposium on Discrete Algorithms, pp. 422-431. Preprint.

Chazelle, Bernard. 2009. The convergence of bird flocking. arXiv:0905.4241v1

Leaving behind the breathy wing-beats of living starlings, we enter a world of mathematical abstractions.

Cucker and Smale, peripatetic mathematicians currently at the City University of Hong Kong, take a stripped-down model of flocking and ask this question: Is it guaranteed that all the birds in the flock will eventually settle on the same velocity, and thus fly together forever? Chazelle, a theoretical computer scientist at Princeton, asks a follow-on question: If the birds do converge on the same speed and heading, how long might it take for them to do so, in the worst case?

The answer to the Cucker-Smale question turns out the be yes: Given certain preconditions and parameter values, convergence is certain. But Chazelle shows that it can take quite a while for the flock to reach consensus. For n birds adjusting their velocities in discrete steps, the upper bound is 2 ↑↑ (4 log n) steps. As I was saying just the other day, this up-arrow notation denotes an exponential tower of 2s with, in this case, 4 log₂ n levels. In other words, in a flock of a thousand birds, the convergence time is roughly

\[2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}\]

with 40 levels of exponentiation. This is a ridiculous number, far exceeding the lifetime of a starling (or of a universe, for that matter). As Chazelle notes: “Our bounds obviously say nothing about physical birds in the real world. They merely highlight the exotic behavior of the mathematical models.”

It is rather wonderful to reflect—as you stand in a field of corn stubble admiring the flocks of birds wheeling overhead in the evening sky—that these avian entertainments should be the starting point for a line of reasoning that ventures so far into the wild blue yonder of inexpressible numbers.

Lebar Bajec, Iztok, and Frank H. Heppner. 2009. Organized flight in birds. Animal Behaviour 78:777–789. Preprint.

I mention this piece last, but it would actually be a good place to start if you want a primer on flocking. Frank Heppner, a biologist at the University of Rhode Island, is one of the pioneers of flocking-and-swarming studies; here, with a mathematical colleague from the University of Ljubljana, he reviews many of the recent contributions and puts them in historical context. The review includes a discussion of the more crystalline flying formations of large birds such as geese as well as the amorphous flocks of starlings.

This morning’s list of new submissions to the mathematics section of the arXiv brings a paper signed by “D. H. J. Polymath.” The name is too good to be true, of course. The paper is the first fruit of a project instigated by Timothy Gowers of Cambridge. In a blog post last January, Gowers asked “Is massively collaborative mathematics possible?” and proposed a problem that might serve as a test case. There were more than 100 responses, and soon the game was on. Discussion began in the comments section of Gowers’s blog and was later supplemented and summarized in a Wiki maintained by Michael Nielsen.

The problem under attack is known as the density Hales-Jewett theorem (hence Dr. Polymath’s initials). The ordinary version of the Hales-Jewett theorem states that if you play tic-tac-toe on a board of high enough dimension, the game can never end in a draw. When you have filled in all the boxes, some row or column or diagonal in the multidimensional grid must consist entirely of x’s or o’s—even if you’ve been trying to reach a stalemate position. The theorem also holds with more than two players and more than two symbols, provided the dimension of space is high enough. The “density” version of the theorem says that sometimes you can’t avoid a winning play even if you stop before filling in all the boxes: A grid-spanning line of solid x’s or o’s is certain to appear as soon as the density, or fraction of filled boxes, reaches a threshold level.

The density version of the Hales-Jewett theorem was proved almost 20 years ago by Hillel Furstenberg and Yitzhak Katznelson, so this is not an open problem. But the Furstenberg-Katznelson proof drew on some results from ergodic theory, a branch of mathematics that seems slightly exotic for a problem stated in such simple, finite terms. Gowers asked if there might be a purely combinatorial proof. And he focused attention specifically on the case where each row and column of the tic-tac-toe board has three positions and there are three players. In other words, the grid is a 3 × 3 × 3 ×  . . .  × 3 hypercube where each vertex is to be marked with one of three symbols.

The combinatorial proof is given in the Polymath paper, which also puts a bound on how high a dimension is needed. The bound is 2 ↑↑ O(1/δ³), where δ is the density and the double-arrow notation indicates an “exponential tower” of 2s — namely O(1/δ³) of them.

A collective pseudonym such as Polymath immediately brings to mind the famous Nicolas Bourbaki. As in the writings of that French group, the Polymath paper includes no listing of contributors. But there’s a difference: The Bourbakists were a secretive bunch, a sort of sleeper cell within mathematics, and historians have pieced together who did what only in retrospect. The Polymath group describes their style of work as “open source” mathematics. It’s all there on the web.

So said John Maynard Keynes, but what did he know about the long run? He was a swell who spent his mornings in bed, trading international currencies over tea and crumpets.

Yesterday was my day for the long run: I ran a marathon for the first time in my life. The race was the Baystate Marathon in Lowell, Massachusetts. I finished in 5:11:23, good enough for 1,494th place. (Complete results here.) Except for the leaden skies, the blustery wind, the temperatures falling from the 40s into the 30s, and the steady rain that later turned to “wintry mix” and then a bit of snow, it was a perfectly lovely day for a run along the Merrimack River. I had a splendid time. Really. And yet it would have been even more fun if it hadn’t gone on quite so long.

Somewhere around mile 20, I began reflecting on the fact that the leaders of the race had already finished more than an hour earlier, and by now they were probably showered and dressed and having something hot to eat. I had to ask myself: Why hadn’t I been running faster, so that I too could now be sitting somewhere comfortable and dry and warm? A mile later, as I slogged on, it dawned on me that surviving a marathon is basically an optimization problem. The essential task is to balance the pain of running faster against the suffering of staying on your feet longer. There’s a mathematical function to be minimized here. But what’s the form of that function?

Splashing on through the puddles, I didn’t make a lot of progress on that question, but several hours later, wrapped in a blanket and enjoying a grilled-cheese sandwich, I realized that a simple candidate function is just 1/t + t, where t is the total time of the run. This function clearly has the right boundary behavior. It diverges at t = 0, reflecting the common-sensical notion that running infinitely fast is infinitely painful. The function is also unbounded as t goes to infinity, since taking forever to complete the course would also be very unpleasant. In between these extremes, there must be at least one t of minimal misery.

To get quantitative results from this function, we need to plug in some constants and coefficients. Marathon times near zero are unrealistic, so we ought to replace t with t–a, where a is the best plausible finishing time. Then we need a coefficient b that sets the scaling between the two kinds of discomfort. The full expression becomes:

\[f(t)=\frac{b}{(t-a)} + (t-a)\]

The value of a in this expression is somewhat arbitrary, but a good guideline might be the current world record marathon time of about 2:04. If we set a = 120 minutes, there’s no need to worry that I’ll ever do better than that (and thereby flip over onto the negative branch of the hyperbola, where everyone runs backwards). With this parameter fixed, the location of the least-arduous marathon time depends only on the value of b, which defines the cost of speed vs. the cost of endurance. If my run in Lowell was a correct solution of the optimization problem, then my personal value of b is 36,481.

This line of reasoning has a curious corollary. If I want to improve my marathon time, I don’t have to learn to run faster; all I have to do is become less tolerant of prolonged standing or walking. This impatience will shift the point of minimum pain leftward, toward higher speeds and shorter elapsed times. For example, if I can just get my value of b down to 14,400, I’ll be running four-hour marathons. I don’t think I’ve ever heard of a training program based on this principle.

Update 2009-10-20: This morning it occurred to me that the same graph, relabeled, could also serve to predict the future course of my geriatric athletic career. I’ve been running for only a few years, and I never attempted distances greater than 10K until this summer. Thus it seems reasonable to suppose that with further effort I might improve somewhat. On the other hand, I’m about 30 years beyond the age at which distance runners tend to reach their peak, which argues that I’m running against the wind, so to speak. (In the long run, Keynes was right after all.)

Here’s a fancifully relabeled version of the graph that I find rather cheering.

Unfortunately, there’s no good reason to believe that either of these phenomena are truly described by a law of the specific form 1/t + t. The second term could be t², or even e^t. (The marathon “ranking standards” published by USA Track and Field appear to increase quadratically with age.)

Update 2009-10-23: Perhaps someone at The New York Times reads bit-player. In today’s paper there’s a story under the headline “Plodders Have a Place, but Is It in a Marathon?” Juliet Macur writes:

Purists believe that running a marathon should be just that — running the entire course at a relatively fast clip. They point out that a six-hour marathoner is simply participating in the event, not racing in it. Slow runners have disrespected the distance, they say, and have ruined the marathon’s mystique.

Thick-skinned as I am, this stings. My apologies to the purists, and to the mystique. I’ll just note that the hundreds of volunteers who put on the race in which I “participated” were marvelously supportive of us plodders. The high school students at the water stations did not abandon their posts, or lose their enthusiasm, after the fleet-footed runners passed by. And when I arrived at the finish line, hours after the winners, there were still fans applauding in the grandstand, and volunteers to wrap me in a blanket, bring me water, offer congratulations. They had been out in the rain as long as I had, and they weren’t done yet. Three cheers for them.

The new issue of American Scientist is on the newsstands and on the web. My “Computing Science” column takes a stab at explaining the Hubbard model, a staple of condensed-matter physics that I’ve been struggling to understand for at least a decade. Have I finally figured it out? You can see for yourself.

The issue also includes an announcement that this new column will be my last for a year. I’m taking a sabbatical—or is it a dekasabbatical? (Both etymology and academic habit imply that a sabbatical is a break from the routine that’s supposed to come along every seven years or so. I’ve been writing the column for seventeen years.)

Friends ask what I’m going to be doing for the next twelve months. Well, one of the great advantages of my line of work is that you get to learn something completely different with every issue of the magazine—flitting from pseudorandom numbers to genetic codes to ichnofossils to interval arithmetic to ferromagnets to programming languages to the childhood of C. F. Gauss, and on and on, like some maniacal butterfly visiting every pretty flower in the field. One of the great disadvantages of my line of work is that you get to learn something completely different with every issue of the magazine—and as soon as you start to make a little progress, you have to set it aside and start all over on a whole nother subject. Thus I’m looking forward to being a little more single-minded for a while. Just one flower. Now if only I knew which flower.

It’s orb-weaving season in my part of the world. Out in the ivy, I have four webs of the golden orb weaver, Argiope aurantia, all within one square meter.

The engineering talents of all the orb weavers are impressive, but what attracts the eye to these particular webs is that bizarre zig-zag decoration, known as a stabilimentum. What’s it for? Does it attract prey? Or mates? Does it camouflage the spider? Does it make the spider look larger than it is, to discourage predators? Does it make the web more conspicuous, to ward off inadvertent damage from passing birds or mammals? Maybe it’s just a skein of spare silk? Or a sunscreen.

Someday we may know the answer, but the spider never will.

A press release from the American Institute of Mathematics two weeks ago announced that all the congruent numbers up to 1 trillion have been enumerated. Two questions leap to mind. What the heck is a congruent number? And who cares?

I’ll return to those questions. But first I’d like to pause just a moment to marvel at the idea of calculating anything up to 10¹². A few decades ago, such a project would have been unthinkable. Today, counting to a trillion takes only an hour or so, even on plain vanilla hardware. This is truly one of the wonders of the age, and we shouldn’t grow too blasé about it. But the computation of all those congruent numbers involved a lot more than looping through “+1″ a trillion times, and it took considerably longer than an hour.

Okay, so what’s a congruent number? I would like to sidle up to that question rather than face it straightaway. The definition is not hard to understand—it’s all about right triangles with rational side lengths and integer areas—but when I started looking into this story, it took me a while to appreciate why those particular triangles might be worth thinking about.

Let’s begin with Pythagorean triples—sets of positive integers (a, b, c) that define a right triangle, with a and b giving the lengths of the legs and c the hypotenuse. The familiar (3, 4, 5) triangle is everybody’s favorite example. For which right triangles with integer side lengths is the area also an integer? That’s easy: All of them. The area of a right triangle is ab/2; in any Pythagorean triple either a or b (or both) must be an even number, which implies that ab/2 is a whole number. For the (3, 4, 5) triangle the area is (3 × 4)/2 = 6.

Knowing one such triangle, we can make more. Lots more. Just multiply a, b and c by any integer k, which has the effect of multiplying the area by k². If k = 2, we get the (6, 8, 10) triangle with area 24; k = 3 yields the (9, 12, 15) triangle with area 54, and so on. The resulting sequence of triangles is infinite but not very interesting; all the larger triangles are just scaled-up versions of the original, like photographic enlargements. We can view the entire infinite series as a single class of triangles, and take the smallest member of the series as the prototype. That smallest triangle is given by a primitive Pythagorean triple—one where a, b and c have no factors in common. It turns out there are also infinitely many primitive triples. Euclid bequeathed us an algorithm that will generate all of them, if you let it run forever.

Given this infinite set of infinite series of triangles, it’s clear that infinitely many integers can be the area of a Pythagorean triangle. But that certainly doesn’t mean that every positive integer has this property. For example, there’s no Pythagorean triangle with an area of 5. To convince yourself of this fact, just measure the area of every integer-sided right triangle with legs no longer than 10. None of those triangles has an area of 5, and no triangle with longer integer legs can have an area that small. In principle, the same laborious but reliable procedure could be applied to any integer N to determine whether or not it is the area of some Pythagorean triangle. Here are the first few integers that appear in such an enumeration ( sequence A009112.):

6, 24, 30, 54, 60, 84, 96, 120, 150, 180, 210, 216, 240, 270, 294, 330

Rational triangles. Suppose we relax the constraints a little, allowing the sides of a right triangle to be rational numbers—either fractions or integers but not irrational values such as the square root of 2. The area is still required to be an integer.

A first question is whether right triangles with fractional sides and integer areas even exist. Maybe the cupboard is bare; maybe there are no such triangles. But no, they do exist. Here’s a proof by example:

There’s no trickery here. If you’re in any doubt, do the arithmetic; you’ll find that the numbers define a genuine right triangle (the Pythagorean theorem holds) and the area really is exactly 7.

At last we have arrived in the realm of congruent numbers. A congruent number is an integer that’s the area of a right triangle with rational sides. All integer-sided right triangles are included in the category, along with those whose sides are rational fractions. Here’s a more formal definition:

A positive integer N is congruent if there exist rational numbers a, b and c such that a² + b² = c² and ab/2 = N.

All the same questions we were asking about Pythagorean triples also come up in this new context. Where do we find rational triangles with integer area, or how can we manufacture them? Which integers N can be the area of such a triangle? Answers aren’t quite as easy to come by in this case. In particular, the strategy of enumerating triangles from the smallest up won’t work, because there is no smallest rational triangle. There are other ways of imposing an ordering on the rationals, but none of them lead to a good algorithm for enumerating congruent numbers.

So where did I get the example illustrated above? I didn’t just stumble upon it by trying random rational triangles. Note that multiplying each rational side length by the common denominator of the fractions will return us to the land of integer-sided triangles. For the example shown, multiplying through by 60 yields a (175, 288, 337) triangle; these numbers have no factor in common, so they form a primitive Pythagorean triple. The area of the new triangle is 7 × 60 × 60, or 25,200. Thus we’ve recovered an integer triangle from a rational one; what’s more important, the process can be reversed to derive rational triangles from integer-sided ones.

I mentioned a Euclidean method for generating primitive Pythagorean triples. It goes like this: Take any two positive integers m and n that satisfy the following conditions:

• m > n;
• one of the numbers is odd and the other even;
• the numbers are coprime (no common factors other than 1).

Then (2mn, m² – n², m² + n²) is a primitive Pythagorean triple. By counting through all suitable values of (m, n) starting with (2, 1), all primitive triples are generated.

A postprocessing step built atop Euclid’s procedure will generate congruent numbers. The plan is to produce a primitive Pythagorean triple and calculate the area N = ab/2 of the corresponding triangle. If the area is “square-free”—that is, it has no pairs of repeated prime factors and thus cannot be divided evenly by a perfect square—then we’re done; that value of N is a congruent number and cannot be reduced to a smaller congruent number. But if N is not square-free, we can divide out each square factor, leaving a smaller triangle with rational sides and integer area, and thereby generating another congruent number.

A worked example: The (m, n) pair (5, 4) produce the primitive triple (9, 40, 41), with area N = (9 × 40)/2 = 180. Thus 180 is identified as a congruent number, but it is not square-free; it factors as 2² × 3² × 5. We can therefore divide the area by 4 and the sides by 2, producing a shrunken (9/2, 20, 41/2) triangle of area N = 45. In this way we learn that 45 is also a congruent number, but again it is not square-free. Dividing the area by 9 and the sides by 3 yields the (3/2, 20/3 and 41/6) triangle with area N = 5. And so 5, too, is congruent; it’s also square-free and therefore cannot be reduced further. There is no smaller triangle similar to the (9, 40, 41) triangle that has integer area.

This scheme can produce an unlimited supply of congruent numbers. Unfortunately, it’s not so well suited to answering the question of whether a particular integer is congruent. The problem is that the congruent values are not generated in order from smallest to largest. If we turn the crank for a while and discover that a certain integer N appears in the algorithm’s output, then we know for sure that N is congruent. But if N has not shown up, we can’t conclude that it is not among the congruent numbers; we might simply have to wait longer for N’s turn to come.

When I turn the crank on my own little program for generating congruent numbers, these are the first 101 values to pop out, in order of appearance:

6, 30, 60, 15, 84, 21, 210, 180, 45, 5, 330, 630, 70, 924, 231, 546, 504, 126, 14, 1320, 1560, 390, 840, 1386, 154, 2340, 585, 65, 1224, 306, 34, 990, 110, 2730, 3570, 1710, 190, 2574, 286, 4620, 1155, 5610, 5016, 1254, 2310, 1716, 429, 7140, 1785, 7980, 1995, 3036, 759, 4290, 7956, 1989, 221, 10374, 10920, 8970, 3900, 975, 39, 7854, 11970, 1330, 14490, 1610, 11550, 462, 4914, 6630, 12540, 3135, 19320, 4830, 6090, 4080, 1020, 255, 11856, 2964, 741, 18480, 23184, 5796, 1449, 161, 25200, 6300, 1575, 175, 7

Here’s the same list sorted into ascending order of magnitude:

5, 6, 7, 14, 15, 21, 30, 34, 39, 45, 60, 65, 70, 84, 110, 126, 154, 161, 175, 180, 190, 210, 221, 231, 255, 286, 306, 330, 390, 429, 462, 504, 546, 585, 630, 741, 759, 840, 924, 975, 990, 1020, 1155, 1224, 1254, 1320, 1330, 1386, 1449, 1560, 1575, 1610, 1710, 1716, 1785, 1989, 1995, 2310, 2340, 2574, 2730, 2964, 3036, 3135, 3570, 3900, 4080, 4290, 4620, 4830, 4914, 5016, 5610, 5796, 6090, 6300, 6630, 7140, 7854, 7956, 7980, 8970, 10374, 10920, 11550, 11856, 11970, 12540, 14490, 18480, 19320, 23184, 25200

The problem, again, is that we can’t conclude anything about the numbers that don’t appear in this collection. For example, 13 is absent, even though it is in fact a congruent number; it just doesn’t turn up until we get well down the list—it comes from the 49,485th triangle examined, which has sides (780/323, 323/30, 106921/9690). On the other hand, 8 is unlisted because it is not congruent; it will never show up in the output hopper no matter how long we keep cranking away.

Here are the first 101 true congruent numbers (sequence A003273):

5, 6, 7, 13, 14, 15, 20, 21, 22, 23, 24, 28, 29, 30, 31, 34, 37, 38, 39, 41, 45, 46, 47, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65, 69, 70, 71, 77, 78, 79, 80, 84, 85, 86, 87, 88, 92, 93, 94, 95, 96, 101, 102, 103, 109, 110, 111, 112, 116, 117, 118, 119, 120, 124, 125, 126, 127, 133, 134, 135, 136, 137, 138, 141, 142, 143, 145, 148, 149, 150, 151, 152, 154, 156, 157, 158, 159, 161, 164, 165, 166, 167, 173, 174, 175, 180, 181, 182, 183, 184, 188, 189

Ancient history. The search for congruent numbers does not stretch back all the way to Pythagorus or Euclid, although Diophantus apparently considered a couple of special cases. L. E. Dickson’s big history of number theory attributes the first full statement of the problem to “an anonymous Arab manuscript, written before 972.” Other sources cite the works of Abu Bakr al-Karaji, a mathematician who worked in Baghdad at the end of the 10th century. A couple of centuries later Fibonacci, who straddled the Arabic and European worlds, had more to say about the problem in his Liber Quadratorum. Later still, Pierre de Fermat proved (in a marginal note, for which he had sufficient room!) that 1 is not a congruent number. (The proof extends to 4 and 9 and 16 and all other square numbers, none of which are congruent.)

These early writers formulated the problem in a somewhat different way than the rational-triangle scheme explained above. Given an integer N, they asked whether it’s possible to find three perfect squares in arithmetic progression with the interval between the squares equal to N. In other words, they sought a number s² such that s² – N, s², and s² + N are all perfect squares. For example, if N = 24, then the solution is s = 5; the three perfect squares are 25 – 24 = 1, 25, and 25 + 24 = 49.

The two versions of the problem—the integer-area right triangles and the squares in arithmetic progression—are equivalent, although that’s not exactly obvious. Here’s the connection: If a² + b² = c² and ab/2 = N, then setting s = c/2 guarantees that s² – N, s², and s² + N are all perfect squares. (For the algebraic exercise proving this, see the book by Neal Koblitz cited below.)

By the way, the squares-in-arithmetic-progression version is where we get the term “congruent numbers.” The three numbers s² – N, s², and s² + N are all congruent modulo N. For example, 1, 25 and 49 are all congruent to 1 modulo 24. If you ask me, “congruent numbers” is a poor excuse for a name, and is particularly confusing in the context of triangles, where “congruent” has another meaning altogether. But after a thousand years I suppose it’s too late to fix it. “Karaji numbers,” anyone?

By 1915, all the integers up to 100 had been classified as either congruent or noncongruent. But as recently as 1980, when Ronald Alter wrote a brief review of the status of the problem, there were still 189 square-free numbers less than 1,000 for which the question of congruence remained unsettled. Then everything changed in 1983. In that year the nature of the congruent-number problem was transformed by Jerrold B. Tunnell of Rutgers, who not only found a better way to calculate congruent numbers but also showed why it’s worth the effort to do so.

From right triangles to elliptic curves. Before I go on, a warning: I am about to walk up to the blackboard with a piece of chalk in my hand and impersonate one of those masterful, self-confident lecturers who rattle off long trains of equations, invent lemmas on the fly, and always come to QED just as the blackboard fills up and the class ends. In my case any such air of mastery is a complete illusion; I’m just learning this stuff as I go along. But I’ll do my best to make it an entertaining illusion.

So here goes. It’s not hard to see that any product of perfect squares is also a perfect square: a²b²c² = (abc)². Therefore, if N is a congruent number, and s² – N, s², and s² + N are all squares, we can set the product of these three factors equal to another square; call it y². Thus we get the equation:

y²  =  (s² – N) s²(s² + N).

Multiplying the three terms on the right, this becomes:

y²  =  (s²)³ – N²s².

Now perform a simple substitution of variables, setting s² = x:

y² = x³ – N²x.

This is the equation of an elliptic curve—another mathematical object with a really unfortunate name. An elliptic curve looks nothing like an ellipse. Here’s the graph of a particular elliptic curve, the one for N = 6:

The two pieces of the blue line mark the locus of all points (x, y) that satisfy the equation

y² = x³ – 36x.

And the hot pink dot? That marks a rational point on the curve—a point where x and y both take on rational values. (Insiders, I’m told, call it a ratpoint.) Specifically, the dot identifies the point x = 25/4, y = 35/8. If you care to plug those numbers into the equation, you’ll find that indeed 1225/64 = 15625/64 – 225, and so the point does lie on the curve.

Tunnell, elaborating on earlier work of Kurt Heegner, showed that N is congruent if the elliptic curve y² = x³ – N²x passes through a certain kind of point on the (x, y) plane. Specifically, we have to search for points whose x and y coordinates are both rational numbers, but we ignore the three points with y = 0. Then the x coordinate of the point has to satisfy three more conditions. Letting x = u/v, we require that:

• u and v are perfect squares,
• v is even,
• u has no factors in common with N.

If we can find just one point on the curve that matches all these properties, then we can generate an infinity of other rational points. Moreover, the existence of such a point implies, according to Tunnell’s theorem, that N is congruent. (The hot pink point above clearly qualifies.) Thus the congruent-number problem appears to be solved: We have an unambiguous criterion for deciding if a given N is congruent or not. Just construct the corresponding elliptic curve and check the ratpoints.

Regrettably, we’ve been set up for yet another disappointment. Searching for rational points on elliptic curves is a task for which we have no efficient general method. We’re really no better off than trying to generate all Pythagorean triples.

But wait! We’re not done yet. From the properties of elliptic curves, Tunnell derived yet another criterion—and this one turns out to be the key to a simple and practical test. It all hinges on the number of integer solutions to some quadratic equations that on first glance appear to be arbitrary strings of symbols plucked out of thin air. The criterion is this: If N is a square-free congruent number, and if N is odd, then the number of integer solutions to the equation N = 2x² + y² + 8z² must be exactly double the number of integer solutions to N = 2x² + y² + 32z². (If both equations have no integer solutions, the condition is satisfied, since 2 × 0 = 0.) For even N, the two equations are slightly different, but the test works in exactly the same way.

The graphic above shows the 361 square-free numbers up to 1,000 that pass the Tunnell test. The height of each dot indicates the number of integer solutions to the equation N = 2x² + y² + 8z² (or the corresponding equation for even N). The two values of N with 160 solutions are 689 and 761. (It’s curious that in most cases—308 out of 361—the number of solutions is actually zero. I don’t know what this means or whether that pattern continues with larger N.) [See Update 2009-10-10, below.]

What sets the Tunnell criterion apart from all the others is that we can actually carry out the test in a reasonable and predictable amount of time. For any given N, counting the solutions should be doable in time proportional to N^3/2, simply by trying all integer values of x, y and z less than the square root of N.

So that’s it, right? Problem solved at last? Well, no, there’s still a small hitch—a bit of awkward fine print. Tunnell proved that if N is square-free and congruent, then the criterion on the number of integer solutions must be satisfied. This much is unconditionally true. But what about the converse? If the criterion is satisfied, can we be certain that N is a congruent number? In this direction, the proof is not unconditional. It’s contingent on a proposition known as the Birch–Swinnerton-Dyer conjecture, which is widely believed, and supported by an abundance of empirical evidence, but still unproved. Which leaves just enough doubt to make the game still interesting.

Why should anyone care about this stuff? On first acquaintance, the search for congruent numbers sounds like one of those mathematical pastimes that appeal to amateurs (like me!) but don’t really command the attention of the research community. There are so many kinds of cutely named numbers out there—perfect, amicable, lucky, happy—and not all of them carry deep significance. The congruent numbers might well be just another amusing sideshow. But it turns out they’re not. There’s serious mathematics here, enough to engage the interest of serious mathematicians.

Elliptic curves have been a focus of intense scrutiny for decades. Henri Poincaré studied them in the early years of the 20th century. In the 1920s Louis Mordell proved a theorem about the rational points on elliptic curves: Even when there are infinitely many points, they all come from a finite set of “generators”; the number of generators and hence the number of infinite families is called the rank of the curve. In the 1950s Yutaka Taniyama and Goro Shimura, with later refinements by André Weil, worked out a conjecture about elliptic curves and another class of mathematical objects, called modular forms. Andrew Wiles and Richard Taylor proved part of that conjecture in the course of settling Fermat’s Last Theorem in the 1990s; the rest of the Taniyama-Shimura conjecture has since been proved as well.

And now we have the Birch–Swinnerton-Dyer conjecture, one of the famous million-dollar math problems. I’m not going to try to explain the conjecture in any detail—I’ve used up all my chalk, and probably my readers’ patience, too—but I think the basic idea goes something like this. On the one hand we have an elliptic curve, drawn in the (x, y) plane. On the other hand we have something called an L-function, which is defined on the plane of complex numbers. Think of the L-function as an undulating landscape with mountains rising above the plane and submarine canyons deep under it. The topography of this surface is determined in part by points selected from the elliptic curve, so there’s a connection between the two objects. The conjecture formulated in the 1960s by Bryan Birch and Peter Swinnerton-Dyer says that the shape of the L-function in the neighborhood where it passes through zero gives us information about the rank of the elliptic curve and thus about the number of rational points.

There’s an analogy between the BSD conjecture and an even more celebrated problem on the million-dollar list, the Riemann hypothesis. The zeros of the Riemann zeta function (which is much like an L-function), carry information about the distribution of prime numbers. The Birch–Swinnerton-Dyer conjecture invites us to suppose that the zeros of L-functions of certain elliptic curves tell us something about the distribution of congruent numbers.

Incidentally, the BSD conjecture must be one of the earliest products of computer-driven experimental mathematics. The numerical explorations that led to the conjecture were done with the EDSAC, the pioneering electronic computer built at the University of Cambridge.

The trillion triangles. Hand-waving about elliptic curves and L-functions might provide vague a rationale for interest in congruent numbers, but one part of the story I still didn’t get was why anyone would bother to compute mass quantities of congruent numbers. So I asked Michael Rubinstein of the University of Waterloo. Rubinstein had earlier computed the congruent numbers up to 10⁹, and it was his challenge that provoked the recent thousandfold expansion of the inventory. Rubinstein explained:

I’m interested in the statistical distribution of congruent numbers. A few years ago, Brian Conrey, Jon Keating, myself, and Nina Snaith came up with a prediction for the asymptotic number of congruent numbers up to x, akin to the prime number theorem. This prediction grew out of remarkable models created by the same researchers and David Farmer for related elliptic curve L-functions that were inspired by random matrix theory and based on a number of unproved assumptions.

The prediction is that the number of congruent numbers less than x, arising from even-rank elliptic curves, is asymptotically

\[c x^{3/4} \log(x)^{11/8}\]

where c is a constant. Our model doesn’t let us completely nail down the constant c, and the data will help us understand what the correct constant is. The asymptotic behaviour stabilizes at a logarithmic rate, so going to 10¹² is only 50 percent better than going to 10⁸.

It will also provide a good amount of data for studying the statistics of ‘higher rank elliptic curves’ in the family of elliptic curves related to congruent numbers. The correct model to use for higher rank elliptic curves is not really understood, and the billions of congruent numbers found will end up yielding several million higher rank curves with which we hope to gain insight into the statistics of higher rank curves (compared to just thousands of higher rank curves from earlier computations).

The enumeration of the trillion triangles was done by two teams. William Hart of the University of Warwick and Gonzalo Tornaria of the Universidad de la Republica in Uruguay ran their program on a computer called Selmer at Warwick. Mark Watkins of the University of Sydney, David Harvey of the Courant Institute and Robert Bradshaw of the University of Washington used the SAGE computer at Washington.

The strategy of the computation is based on the Tunnell criterion, but it turns out there’s a better way to go about it than explicitly counting the number of integer solutions to those various quadratic equations in (x, y, z). Tunnell showed that all the information about the number of solutions could be encoded in a formal power series, which looks like this:

\[A(q) = a_{1}q^{1} + a_{2}q^{2} + a_{3}q^{3} + a_{4}q^{4} + ... \]

It’s a “formal” series in the sense that we don’t actually care about evaluating the sum for any particular value of q; instead, we just want to know the various coefficients a_i. This is how the Tunnell criterion gets encoded in the series: If a_i is zero in this series, and if i is a square-free number, then i is congruent. (Actually, there are two separate series, one for odd i and one for even i.)

The odd and even power series are generated by a couple of formidable-looking products. Here’s the one for the odd series:

\[A(q)=q\prod_{n=1}^\infty(1-q^{8n})(1-q^{16n})\left(1+\sum_{n=1}^\infty 2q^{2n^2}\right)\]

Since both the overall product and the sum in the third factor call for infinitely many values of n, we can’t multiply out this whole expression. Fortunately, though, it turns out that larger n contribute only to higher coefficients, and so we can compute early terms in the series without worrying about what might happen later. Kent Morrison notes that taking just the factors

\[q(1-q^8)(1-q^{16})(1-q^{16})(1+2q^2+2q^8+2q^{18})\]

is enough to generate all the odd congruent numbers up to 25. Those five factors expand to:

\[A(q)=q^1+2q^3+q^9-2q^{11}-4q^{17}-2q^{19}-3q^{25}+...\text{ higher terms}\]

The terms missing from this series—those with a zero coefficient—are just the odd square-free congruent numbers in this range: 5, 7, 13, 15, 21, 23.

The big computation by Bradshaw et al. used essentially this same scheme, with a few refinements and optimizations. The challenge is that when you’re trying to compute all the terms of the series out to a_{1,000,000,000,000}q^{1,000,000,000,000}, you wind up multiplying some enormous numbers. I don’t mean just that the numbers are too big to fit into the registers of a 32-bit or a 64-bit computer. They’re too big to fit into the main memory of a computer with 128 gigabytes of RAM. Moreover, the arithmetic has to be done exactly; approximations are useless. Thus a major part of the effort in setting up the computation was devising efficient “out of core” multiplication routines for ridiculously large numbers. The basic algorithm was a fast-fourier-transform method.

And the result? Up to 10¹², the computation identified 3,148,379,694 square-free congruent numbers number candidates with N in the residue classes 1, 2, and 3 modulo 8. I look forward to reading more about the analysis of their distribution. [See Update 2009-10-10, below.]

References and resources. Two weeks of reading and tinkering have not made me the master of this subject. For those who would like to explore further I can offer some resources I’ve found helpful, listed in no particular order.

• Ed Eikenberg has posted some lecture notes from a talk on elliptic curves and congruent numbers given in 2000.
• William Stein offers slides from a Harvard lecture in 2001.
• The web page for another William Stein course (this one at the University of Washington in 2006) provides notes and handouts and a collection of function definitions that will let you play with congruent numbers and elliptic curves in the Sage computer mathematics system.
• Koblitz, Neal. 1993. Introduction to Elliptic Curves and Modular Forms. Second edition. New York: Springer-Verlag. Some kind soul has posted page images for the first chapter online.
• Guy, Richard K. 2004. Unsolved Problems in Number Theory. Third edition. New York: Springer. (Section D27, p. 306, discusses congruent numbers.)
• Tunnell, J. B. 1983. A classical diophantine problem and modular forms of weight 3/2. Inventiones Mathematicae 72:323–334. (Available online via the DigiZeitschriften.)
• Barry Cipra writes on the recent trillion-trangle computation: Tallying the class of congruent numbers, ScienceNOW, September 23, 2009. (Get it now, while it’s free.)
• Dickson, Leonard Eugene. 1952. History of the Theory of Numbers. New York: Chelsea Pub. Co. (For congruent numbers see Vol. 2, Chapter 16, p. 459.)
• Brown, Ezra. 2000. Three Fermat trails to elliptic curves. The College Mathematics Journal 31:162–172. Free PDF available online (unlike most CMJ articles), apparently because it won a Polya prize.
• Rubin, Karl, and Alice Silverberg. 2002. Ranks of elliptic curves. Bulletin of the American Mathematical Society 39:455–474. Online.
• Silverberg, Alice. 2001. Open questions in arithmetic algebraic geometry. In Arithmetic Algebraic Geometry, Institute for Advanced Study/Park City Mathematics Series 9, pp. 83–142. Providence: American Mathematical Society. Postscript preprint.
• The American Institute of Mathematics web page on congruent numbers, which includes several helpful appendices, such as a discussion of FFT multiplication, an essay on congruent numbers by Kent Morrison and a link to the paper by Bradshaw, Hart, Harvey,
  Tornaria and Watkins reporting the trillion-triangle computation. (At this writing, the posted version of the paper is still an incomplete draft.)
• Conrey, J. B., J. P. Keating, M. O. Rubinstein and N. C. Snaith. 2000. On the frequency of vanishing of quadratic twists of modular L-functions. arXiv preprint. (This paper and the one listed below discuss conjectures about the distribution of congruent numbers, among other topics.)
• Conrey, J. Brian, Jon P. Keating, Michael O. Rubinstein and Nina C. Snaith. 2004. Random matrix theory and the Fourier coefficients of half-integral weight forms. arXiv preprint.
• Brown, Jim. 2007. Congruent numbers and elliptic curves. PDF (Brown refers to this text as lecture notes for an undergraduate course, but in fact it is a very polished and well-organized expository article. Includes some Sage code for working with rational points of elliptic curves.)
• Alter, Ronald. 1980. The congruent number problem. American Mathematical Monthly 87:43–45. (Tables of what was known and unknown shortly before Tunnell’s breakthrough.)

Special thanks to David Farmer for alerting me to this story in the first place and to Michael Rubinstein for help understanding what it all means.

Update 2009-10-10: In the comments, Barry Cipra points out that the quadratic equations in the Tunnell criterion necessarily have no solution whenever N is congruent to 5, 6, or 7 modulo 8. In fact all of the zero-solution points in the graph I presented above come from such N. Numbers in the residue classes 0 and 4 modulo 8 cannot be square-free. If we plot only those N that are square-free and congruent to 1, 2 or 3 modulo 8, we are left with just 53 square-free congruent-number candidates up to 1,000:

Only the numbers in these three residue classes were included in the trillion-triangle computation.

Sometime this morning, a web page that I visit occasionally changed its appearance from this:

to this:

The images are grabbed from Firefox on OS X; same effect in Safari. Some CSS forensics reveals what’s gone wrong here: Google has added a “height:28px” property to the style for the two buttons, and boosted their type size from 13 pixels to 16. (Type inside the search box is also given the giant billboard treatment.) Apparently the height property prevents the browser from using those cute jelly-bean widgets for the buttons.

Can we strike a bargain, Google? I’ll let you take over the world and track my every movement; I’ll sign over all my copyrights and promise never to block your advertising, if you’ll just give me my widgets back. Go ahead and Be Evil; just Don’t Be Ugly.

Or am I going to have to override you in userContent.css?

Update: Marissa Mayer, Google’s Vice President for Search Products & User Experience, explains:

For us, search has always been our focus. And, starting today, you’ll notice on our homepage and on our search results pages, our search box is growing in size. Although this is a very simple idea and an even simpler change, we’re excited about it — because it symbolizes our focus on search and because it makes our clean, minimalist homepage even easier and more fun to use. The new, larger Google search box features larger text when you type so you can see your query more clearly. It also uses a larger text size for the suggestions below the search box, making it easier to select one of the possible refinements.

For Firefox users who find the “supersized” page a nonimprovement, I offer the following quick hack:

@-moz-document domain(google.com) {
  .lsb, .gac_sb {
	font-size:13px ! important;
	height:inherit ! important;
	}

  .lst, .gac_m {
	font-size:14px ! important;
	}

}

Add these lines to your userContent.css file (see the Customizing Mozilla site for further instructions). This seems to fix the widget problem and the input-field text size, but all the drop-down gadgetry is still a mess and maybe the dropdown menu of suggestions. This will break if Google’s next whim is to change the class names “lsb,” “lst,” etc. If anyone has a cleaner solution, please pass it on.

I’ve been goofing off in Nova Scotia for a few days. In Halifax I climbed up to the Citadel, a hilltop fortress built to protect the city from the French and later rebuilt to fend off the Americans; now it welcomes both those nationalities and anyone else willing to pay $12 for the tour and the costume show.

In one room of the museum I discovered the curious diagrams reproduced at right. These figures are extracted from a poster on military codes designed for ship-to-shore communication. Signals were sent by hoisting large balls or disks on a mast reaching high above the fortress ramparts; ships in the harbor could reply by raising similar signal disks on their own masks.

The part of the code shown here obviously pertains to the transmission of numbers, but I’ve never seen a weirder system of numeration. Based on these diagrams and others, I infer that the signal disks were raised on three halyards. (A fourth halyard is present in the diagrams but always seems to be empty.) Each halyard could display zero or one or two disks, and each displayed disk could be in either an upper or a lower position. That comes to five possible patterns per halyard, and thus 5³ = 125 patterns in all. What baffles me is why the ten decimal digits were assigned to the specific patterns shown in the diagrams. Who counts in the sequence 1, 2, 3, 4, 5, 0, 6, 7, 8, 9, 9, 9?

I’m not even sure I understand the basic signaling protocol. When I first looked at the poster, I assumed that the ten digits were represented thus:

Presumably, the three encodings for ‘9′ were equivalent, and any of them could be used at the signaler’s option.

Later, after much musing over this puzzle, I decided that another interpretation of the diagrams seemed more plausible:

In this scheme at least the numerals from 1 through 5 have some kind of logic to them, in that the number of disks shown matches the numeral being transmitted; in essence we have a unary notation within that limited range. On the other hand, if this interpretation of the diagrams is correct, we have to ask: Why did the designers stop at 5? They could have extended the same unary scheme to the range from 1 to 6, and then used doubled disks at the top of the mast for the numerals 7, 8 and 9.

If we were creating a code like this today, I’m sure everyone’s first impulse would be a system based on binary notation. It’s not terribly surprising that the British naval authorities circa 1850 didn’t think of that. But I still find the apparent arbitrariness of this numerical code utterly perplexing. Am I missing some pattern in the data, either obvious or subtle? (I suppose the encoding could be deliberately obscure, but there’s no evidence that this was meant to be a secret code, and the mere existence of the poster—which appears to be a 19th-century artifact—suggests otherwise.)

Added 2009-09-10: Below is the signal mask on which the disks were displayed, seen from the landward side. The disks (actually fabric-covered crossed hoops, which have an approximately circular cross section from any azimuth) were 36 inches in diameter. I think the diameter of the mast is about 12 inches at the base.

* * *

The Googleverse has so far failed to solve this mystery for me, but in the process of searching I stumbled upon a remarkable book that suggests there was some lucid thinking in the 19th century on themes that we would now identify as information theory. The book is A Manual of Signals: For the Use of Signal Officers in the Field, and for Military and Naval Students, Military Schools, Etc., by Albert J. Myer. The full text is available on Google Books in either HTML or PDF.

Myer founded the U.S. Army Signal Corps just before the outbreak of the Civil War. He had studied medicine, writing a dissertation on “A New Sign Language for Deaf Mutes,” and had also worked as a telegraph operator. Then, in the army, he devised the signaling method commonly known as wigwag, using a single flag waved to the left and the right. Fort Myer in Virginia is named for him. (These biographical snippets come from a Signal Corps history, which offers much further detail.)

Myer’s book was first published in 1864 and then revised in 1868, but it takes quite a modern mathematical approach to problems of communication and information. He begins with a tutorial on permutations and combinations, then applies these ideas to the encoding of signals:

We wish for example to make a large number of signals…. We take any few different and simple known signs, sounds, motions, or indications, which we can easily make, and we join them together, twos or threes, or more at a time, making one after another into many and different and more complex signs or arrangements. Each of these new signs becomes, when a meaning is given to it, a signal. We can increase the number of such signals to any limit by continuing to join together the known signals in greater numbers or in new arrangements.

That’s a pretty good description of Σ*, the set of all strings over a finite alphabet.

* * *

Guest update 2009-09-10: The following comes from Barry Cipra.

I have an idea for an alternative interpretation of the way digits are meant to be represented by disks on halyards. My basic premise is that a distant viewer can tell the difference between a disk being up high and it being down low, but cannot accurately judge which halyard a disk is on unless there’s at least one disk on each halyard. (In particular, two disks on outer halyards could be confused with two disks on adjacent halyards if the mast is at an angle to the distant viewer.) In this case, the digits 0 through 9 can be unambiguously represented as follows:

In other words, basically your second interpretation for 0 through 8, but with an extra “anchoring” pip for the numbers 1 through 5, but your first interpretation for the number 9. This makes it clear why the small-number format stops at 5.

If my premise is correct (or accepted as correct), then out of the 216 distinct patterns, there are only 1+5+25+125 = 156 unambiguous signals possible. That is, there is 1 signal with no halyards having any disks, 5 with exactly one halyard showing at least one disk, 25 with exactly two halyards showing at least one disk each, and 125 with disks showing on all three halyards.

But maybe we should also require the meaning of a pattern to be unambiguous when the orientation of the ship is uncertain — i.e., A,B,C should have the same meaning as C,B,A. If I’ve thought through things correctly, this cuts the number of unambiguous signals down to 1+5+15+75 = 96.

It would be great to find out how the Navy really did things!

* * *

Update 2009-09-17: Many thanks to Jim Ward (in the comments) for unearthing a 2007 document by Spurgeon G. Roscoe that illuminates the history of this signaling system, even if it doesn’t quite pin down how the code worked.

Roscoe describes a system of signaling towers founded by Edward, Duke of Kent, during his busy tenure as military commander in the Maritime Provinces at the end of the 18th century. Kent’s optical telegraph line was to run from Halifax to Annapolis in Nova Scotia and on to Fredericton in New Brunswick. It is not known with certainty how much of the network was completed or whether it ever served as a practical communications link. (Roscoe is skeptical, pointing out among other things that the territory around the Bay of Fundy is very foggy.)

The chart on exhibit at the Citadel in Halifax is not directly connected with the Kent telegraph system; it comes from a later era and is identified as a device for ship-to-shore communication; nevertheless, there is an unmistakable familial resemblance. Sketches reproduced by Roscoe give the following code system for the Duke of Kent’s overland telegraph:

This is merely a cyclic permutation of positions 0, 6, 7, 8 and 9 in the Citadel code. (On first glance there also seems to be a mirror reversal involved, but that’s not the case; we’re merely looking at the signal mast from the opposite direction.)

Roscoe says nothing about how to interpret these diagrams—whether, for example, the display for “6″ consisted of six disks or a single disk in the lower right corner, or one of the other schemes discussed above or in the comments. But his description of how messages were composed seems so impossibly cumbersome that it leaves me wondering if this plan was ever really put into practice. Apparently, alphabetic characters did not have codes of their own; each letter was encoded in a sequence of numerals. In one system, “A” was 2, 3, 0; “B” was 1, 4, 0; “Q” was 4; “T” was 2, 3. (The compact, single-digit encoding of “Q” makes this a kind of anti-Hamming code.) Can anything so maladaptive have survived the trial of use in the field?

Update 2009-09-22: This is a response to Carl Witty’s comment. I’m putting it here in the main text rather than in a further comment because I think Witty has essentially solved the mystery.

Witty’s interpretation of the Roscoe manuscript rules out all schemes in which the code is “cumulative” — where the signal for 3, for example, consists of the disks numbered 1, 2 and 3. Instead, digits 1 through 6 are each represented by a single displayed disk, and digits 7 through 9 each consist of a single pair of disks. (The triple code for 9 is to be interpreted as an “OR”: Any of the three positions can be used with the same meaning.) Then these digits — which are really just opaque symbols, with no numerical meaning — are combined in various ways to represent the letters of the alphabet and the numbers from 1 to 99. (Supplementary flags bring the range of numbers up to 499.)

Thus when Roscoe indicates that the letter S has the coding “1, 3, 5,” that means the disks labeled 1, 3 and 5 are all displayed simultaneously in order to transmit an S.

There’s a test for this hypothesis. If the scheme is to be workable, the alphabetic and numerical codes composed by displaying two or three or four digits at once must have a particular form. There can be no repeated digits in any encoding, and no two of the digits can use the same position on the mast. Specifically, in the Duke of Kent code illustrated in the 2009-09-17 update above, there can be no composite code that calls for both a 1 and a 7, or a 3 and an 8 or a 9 and a 5.

Does the code transcribed by Roscoe pass this test? Roscoe actually gives two codes, both apparently found in an 1802 “Signal Book” from Camperdowne Station in Nova Scotia. Roscoe’s second listing of alphabetic and numeric encodings does indeed satisfy the constraints. Indeed, it obeys a stronger restriction: No combination of symbols in the code calls for hoisting more than two disks on a single halyard. For example, the code avoids not only 1 and 7 but also 2 and 7.

The other code that Roscoe lists fails the test — or so it seems at first glance. There are patterns such as “1, 7″ encoding the number 54 and “3, 8″ for 64. But on looking closer, it appears that this code adheres to a different set of constraints: There are no instances where a 6 appears together with either a 1 or 2, or where 7 is combined with 3 or 4, or finally where 8 comes together with 5 or 0. These are exactly the restrictions that have to be applied in the Citadel code!