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.

Lattice QCD is something I’ve been trying to understand for 30 years. My latest attempt is chronicled in the new issue of American Scientist.

QCD is quantum chromodynamics, the theory of interactions between quarks and gluons. The lattice version of the theory appeals to those of us who like our physics in discrete, countable bits. In the lattice formulation, quarks and gluons exist only at the nodes of a four-dimensional spacetime grid. There’s no evidence that the universe really has such a rectilinear structure, but it turns out to be a useful fiction when you want to calculate things like the masses of quarks. In large measure we are all made of quarks, and so it seems like a good idea to know some basic facts about them.

In my quest to figure out what lattice QCD is all about, I’ve had a lot of help. Years ago, as an editor of magazine articles, I had the splendid opportunity to get one-on-one tutorials from Kenneth G. Wilson and from Claudio Rebbi. I received further help for this latest project, and for that I want to thank G. Peter Lepage of Cornell.

In a paper titled “Lattice QCD for Novices” (written and published in 1998 but posted on the arXiv in 2005), Lepage presented a simple Python program that illustrates some of the key ideas behind lattice QCD. The complete source code for the program is given within Lepage’s article, but to save readers the trouble of gathering the pieces and extracting them from a PDF, I have (with Lepage’s permission) made the program available here in the file qcd.py. I’ve also made some trivial changes for the sake of compatibility with more recent versions of Python.

Finally, thanks too to Massimo Di Pierro of Depaul University for a vizualization of lattice QCD in action.

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

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

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

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

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

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

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

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

Two of the best science-blog articles of 2007 appeared early in the year at Cosmic Variance. They were written by John Conway (not the John Conway, the other John Conway) and gave an inside view of what happens in a large experimental collaboration when there’s a hint of glory in the air. The CDF experiment—one of the two large detector groups at the Fermilab Tevatron—had found a bump, and it could be a sign of the fabled Higgs boson, the one Leon Lederman called the God particle. As Conway put it: “Holy crap!”

The bump consisted of a few data points that stood two standard deviations above the expected background level.

In medicine, two sigma is plenty of significance to decide whether a new drug will cure you or kill you, but physicists are more discriminating. Conway explained that they really needed five sigma to claim a discovery, although a lesser level might qualify as “evidence” or “indication.” Two sigma could too easily be dismissed as a statistical fluke.

Today Conway has posted the long-awaited followup. With a larger data sample, those dots and whiskers are back in their bins:

Conway is totally forthright about this outcome:

Gone! The data points all fell within an error bar or so of every bin…no excess, no bump, no Higgs… I am sure you are thinking “no tickets to Stockholm” too.

He then goes on to engage in a little preemptive spin control, in a paragraph aimed straight at the likes of me:

Now, gentle readers, one thing we’ve learned is that among you are many science journalists who use blogs as a means to catch wind of breaking news. You all have to have an angle, and a story to tell (sell). In the past, our field has been treated to stories of the ilk “300 Physicists Fail to Find Supersymmetry” with the subtitle “Study Illustrates the Risks of Big Science”. (New York Times, 1993). I sincerely hope that’s not your angle here, science writers! Our favorite put-down of that is to ask whether there should have been an 1888 story titled “Physicists Fail to Find Ether in Vacuum” about the Michelson and Morley null result. But okay, we’re nerds.

If I weren’t such a thick-skinned cynical journalist, I might chafe a little at this scolding-in-advance. I might ask, for example, what headline should have appeared on a contemporaneous story about the Michelson-Morley experiment. Is Conway suggesting that the Higgs boson is in the same conceptual category as the electromagnetic ether?

But I want to set aside my own defensiveness, and also try to disarm Conway’s. Even if we loutish journalists refrain from public cackling at this delicate moment, it seems all too likely that the next time Conway spots a two-sigma bump, he’s going to keep his mouth shut and his head down. We’ll all be the losers if that happens. What was so refreshing about this affair was that we could all follow the story as it unfolded, rather than waiting for the carefully vetted post-hoc redaction. (Given the eventual negative result, if the bump had been kept under wraps at the outset, we might never have heard of it at all.)

Conway concludes on a rousing note:

I challenge you journalists out there to tell it like it is: this is a great human adventure, with all the twists and turns any good adventure has.

Yes! I second that emotion. But we journalists can report the twists and turns only if we get to follow the twists and turns along with you, including the wrong turns.

The drawing below, brazenly swiped from a 1964 Martin Gardner column, illustrates the solution to a well-known puzzle. If you stack n bricks on a table, how far can you make them extend over the edge without toppling?

The answer given, for bricks of unit length, is one-half the nth harmonic number, the sum of the series 1/2 + 1/4 + 1/6 + 1/8 + … + 1/2n. Since this series diverges, the overhang can be as large as you please, given enough bricks (and a strong enough table).

In describing this result, Gardner uses the word “unbelievable,” and when I first read about it, that was my reaction too. It is one of those facts that are inescapably true, and yet still implausible. Now I learn that the truth is even stranger—that far larger overhangs can be achieved.

The overhang for the harmonic stack is approximately equal to 1/2 ln n; it turns out other stacks achieve an overhang on the order of the cube root of n. This is an enormous improvement. For a million bricks, the harmonic stack can’t get beyond 13.8 bricklengths, whereas the cube-root stack extends 100 bricklengths beyond the edge.

How is it done? I’m not telling. If you can’t figure out the trick, you’ll have to consult the links below.

The key idea in the alternative solutions has apparently been known for at least 20 years. (Actually, I’d be surprised if it wasn’t known to stonemasons centuries ago, as well as generations of children playing with wood blocks—but I don’t have a reference to support that conjecture.) Quite new, however, is the mathematical analysis showing exactly how large the overhang can be. Last year Mike Paterson of the University of Warwick and Uri Zwick of Tel Aviv University presented a paper at SODA (the Symposium on Discrete Algorithms) giving optimal solutions for n up to 30, and showing that the asymptotic rate of growth is n^1/3. Now Peterson and Zwick, along with Yuval Peres (Berkeley), Mikkel Thorup (AT&T Labs) and Peter Winkler (Dartmouth) have proved that order n^1/3 is the best that can achieved:

More specifically, we show that any n-block stack with an overhang of at least 6n^1/3 is unbalanced, and must hence collapse. Thus we conclude that the maximum overhang with n blocks is of order n^1/3.

Links: The 2006 Paterson-Zwick paper is here in the SODA proceedings (subscription required) and here in the arXiv. (It is also to appear in the American Mathematical Monthly.) The five-author proof is at the arXiv here.

Hardware is hard, whereas software is soft; the people who named these things knew what they were talking about.

A while ago, I volunteered to help a friend upgrade the disk drive of an Apple iBook. My first clue that this was going to be a fun project was learning that we needed a special tool called a spudger just to pry open the case. As it turned out, the spudging part of the job wasn’t really that bad; the sleek, black, nylon implement worked quite smoothly. (But so did an old putty knife.) Following instructions , I removed 3 Torx screws, 41 Phillips screws, 1 magnet, 3 rubber feet, 2 greasy springs, 4 strips of sticky tape, the battery, the keyboard, the Airport card, the RAM shield, the lower case, the bottom shield, the DC-in board, the upper case, the top shield, a restraining bracket, and the hard drive. Then I plugged in the new drive and replaced the restraining bracket, the top shield, …, sticky tape, greasy springs, rubber feet, magnet, Phillips screws and Torx screws. Finally, all the parts were back in the box and the case was snapped together again where I had spudged it apart. But when I pressed the power button: Total absence of joy. I pressed it again: Not a peep from the speaker, not a glimmer of light in the screen. Yet again: Nothing but a blank stare.

My purpose in writing about this low point in my career as a high-tech handyman is not to rant about the frustrations of technology or our throwaway culture, where nothing’s worth fixing and nobody knows how to fix it anyway. On the contrary, I want to take a moment to marvel at the elegance and ingenuity of microelectronic technology. After all, it’s the wonder of our age.

I recently had occasion to pull an old book off the shelf: Introduction to VLSI Systems by Carver Mead (Caltech) and Lynn Conway (then Xerox PARC, now University of Michigan).

This is a hands-on, do-it-yourself guide to designing silicon chips—arguably the most complex artifacts ever created by human minds and hands. (When Mead and Conway were writing, “VLSI” meant thousands of transistors on a chip; now it’s hundreds of millions.) Intricate as the circuits might be, Mead and Conway leave you feeling that you can understand absolutely everything about them, from the physics of electrons drifting through doped silicon, to the operation of individual transistors and logic gates, to the organization of those gates into higher-level modules such as adders and shift registers, to the layout of the patterns for the various layers, to the process of fabrication. I’ve always been particularly fond of the colorful layout diagrams, which look nothing like engineering drawings and everything like textile patterns.

Things have changed somewhat since the late 1970s—the era of the circuits described by Mead and Conway. Chip layouts were then checked and documented by printing them out at enlarged scale with a multicolor pen plotter. Quite a few of those plots wound up decorating engineer’s offices. (Maybe that was their real purpose.) If you tried to make a similar plot of a modern chip layout, it would cover a square kilometer. Nevertheless, even though this book is 30 years out of date, it is still the guidebook I would choose to take with me on any visit to the world of digital devices.

In their preface, Mead and Conway write: “In any given technology, form follows function in a particular way.” Yet what’s most extraordinary about the design of silicon circuits is how function follows form. It’s magic: When you print those patterns of interwoven colored stripes onto the surface of a silicon wafer, they come to life! They become active agents rather than mere geometric figures, capable of computing—almost capable of thinking. It’s as if the printed words in a book began reading themselves aloud and commenting on the story in which they occur.

If it’s surprising that mere geometric patterns can be transformed into a computing machine, I sometimes find it equally astonishing that mere machinery can be made to compute. The objects of computation are abstract entities such as numbers, bits, sets, logical operations. These things all seem (to me) to have an existence independent of any specific physical embodiment. When I think of a logical formula—P AND (Q OR R), say—I don’t ordinarily have in mind the little series-and-parallel network of transistors that Mead and Conway would design to implement this function in nMOS technology. P, Q and R are variables, or truth values, not voltages and currents. So why does our universe offer this curious mapping between physical structures and computational ones? Why is it possible to build computers? Why do we need to build them? Why can’t we just compute with pure thought stuff?

A few years ago, if I had written a paragraph like the one above, I would now be awaiting a letter or a phone call from Rolf Landauer, a wonderfully irascible physicist at IBM, who would forcefully remind me that “Information is physical!” Landauer died in 1999, so I no longer have the benefit of his critiques, but I’ve just discovered that his views on this issue are very ably representing in the final chapter of Mead and Conway, a chapter I had not properly appreciated when I first encountered their book. They write:

Computation is a physical process. Data elements must be represented by some physical quantity in a physical structure, for example, as the charge on a capacitor or the magnetic flux in a superconducting ring. These physical quantities must be stored, sensed, and logically combined by the elementary devices of any technology out of which we build computing machinery.

I’m not going to try to argue the contrary proposition—that computation is an abstract, mathematical process, which just happens to be modeled accurately by certain physical events and structures—but I would like to register my ongoing puzzlement at this close correspondence between the world of atoms and the world of numbers. I can believe it’s true that information is physical, but at a deep level I don’t get why it’s necessary.

Consider this: Since 1994, thanks to Peter Shor, we’ve had an algorithm for efficiently finding the prime factors of integers. But the algorithm only works on a quantum-mechanical computer; with a computer built according to the principles of classical physics, all known factoring algorithms require an effort that grows exponentially with the size of the integer. Someday, when the novelty has worn off, this situation will seem perfectly natural and unremarkable, but for now I am still bothered by the hint of a link between number theory and the laws of matter and energy. In this context, the quantum computer seems like a spudger—an overly specialized tool that you wouldn’t need if things were designed properly in the first place.

Mead and Conway is a terrific book, but it offers no useful advice on reviving an unresponsive iBook. For that I made an appointment at the Genius Bar of the local Apple Store. Quoth the genius: “Nevermore.” The cost of the repair would exceed the price of a comparable new iBook.

But this story has a happy ending, much to my surprise. Having already turned my friend’s computer into a plastic brick, I couldn’t do much further damage by spudging around inside it. And even if I failed to bring it back to life, performing an autopsy might teach me something. Over the next week I became adept at stripping the machine down to bare boards in half an hour. It didn’t take long to identify the cause of death. A small white plastic socket in the northeast corner of the circuit board was wobbling like a loose tooth. Evidently I hadn’t been gentle enough when I disconnected a cable during my first disassembly. That cable goes to the power button.

I fixed it with Krazy Glue and clothespins. Hardware is hard, but it’s no match for a well-practiced spudger.

Quantum computing gets a lot of attention, but we don’t hear much about quantum mathematics. The very idea is an affront to Platonist thinkers everywhere—those of us who consider the elements of mathematics to be independent of the physical universe. Is the truth of the Pythagorean theorem subject to the same uncertainty as the fate of Schrodinger’s cat? Surely the counting numbers 1, 2, 3,… should be the same in any universe, whether quantum or classical; indeed, if you’re a full-gospel, whole-Bible Platonist, you might well argue that those numbers existed even before there was a universe. (At the opposite extreme are the constructivists, who warn that the only numbers you can count on are those you have fingers for.)

Questions like these are easily settled by experiment: Just annihilate the universe, abolish space and time, and try doing a few sums in the void. I would put the proposition to the test right now except that I don’t want to miss this week’s episode of “1 vs. 100.”

Paul Benioff of Argonne National Laboratory has been thinking and writing about these issues for some time. A few weeks ago he posted a preprint on the arXiv titled “Space of quantum theory representations of natural numbers, integers, and rational numbers.” I’ve been struggling to understand that paper, along with a couple of earlier ones on the same theme (here and here). I’m still a long way from mastering this material, but here’s what I’ve made of it so far.

Even if you go along with the Platonist view that the true home of all things mathematical is an ideal realm outside of time and space, we don’t live in that realm. Whenever we want to do something with numbers (or other mathematical entities), we have to represent them somehow in this universe. We chalk them on the blackboard; we twiddle the beads of an abacus; we load patterns of bits into a computer memory; even mental arithmetic requires a mind, which in turn seems to require a body. Thus no one does mathematics without atoms and photons and other toys and tools of the physicist, and so perhaps it’s not utterly crazy to suppose that what we can accomplish in mathematics may depend to some extent on the laws of physics. All the evidence suggests that those laws are inescapably quantum mechanical.

Benioff argues that numbers have to be represented and manipulated in ways that accord with quantum principles; for example, all operations should be reversible, and they should enforce “unitarity,” meaning that the probabilities of all possible outcomes should sum to exactly 1. At the same time, it’s important that numbers behave like numbers: They have to obey familiar axioms of arithmetic, or they’re of no use to mathematics. In the case of the counting numbers (a.k.a. the natural numbers) we have to be able to add and multiply. For the integers (the natural numbers augmented with zero and negative values), subtraction must also be allowed. The rationals introduce division. And for all these kinds of numbers we should be able to determine if two numbers are equal, and put them in order if they are not.

Quantum computing is usually discussed in terms of qubits, or the quantum equivalent of binary digits. Benioff extends the discussion to qukits, the quantum equivalent of base-k digits. Think of a qukit as a black box that holds one of k values, but until you open the lid, you can’t be sure which value. Once you look inside, the uncertainty is resolved, and the box is found to contain a specific value. The question Benioff addresses is: How do you do arithmetic with such unruly numbers? If you can’t even be sure of what numbers you’re working with, how can you add or subtract them, or test them for equality? The answer, ultimately, is that you have to put up with a degree of uncertainty. In the quantum world, the commutative law of addition, a+b = b+a, is not a bedrock principle but a statement whose truth is a matter of probabilities.

Benioff presents a specific implementation of quantum-theoretical numbers, based on a two-dimensional lattice of qukits. Each number occupies its own row of the lattice, with the digits arrayed from left to right. For integers, a designated qukit (actually a qubit, since it has just two states) serves as a sign bit. For rationals, this special qubit also marks the position of the decimal point (or “k-al” point), separating the integer part from the fractional part. On first glance, this lattice of qukits doesn’t seem too different from the hardware of an ordinary computer, but the quantum nature of the qukits brings some peculiarities. For example, the result of every operation has to go into a newly allocated row of the lattice; you can never erase or overwrite an existing value, because quantum operations have to be reversible and cannot destroy information.

Benioff introduces a set of parameters for his numbering system: m and h are the coordinates of a number within the lattice of qukits, k is the base of the qukits, and g is a “gauge-fixing function.” This last item sounds quite arcane, but I think it has a fairly simple explanation. You can imagine a qukit as a vector that can point in any of k directions; the gauge-fixing function defines a reference direction from which all the others are measured.

Here’s a taste of what Benioff has to say about his quantum numbers:

Transformations (k, (m, h), g) → (k’, (m’, h’), g’) in the parameter set induce transformations in the representation space. These consist of unitary translations that move the qukit strings on the lattice, transformations that change states of strings of base-k qukits to states of strings of base-k’ qukits, and unitary gauge transformations for each k….

An interesting result is that the axioms and theorems for each of the three types of numbers [i.e., natural numbers, integers and rationals] are invariant under these transformations. They represent symmetries of the systems. This is the case even though the specific expressions of the axioms and theorems in terms of basic arithmetic relations and operations are different for different representations. This is like the situation in physics where the laws of physics are invariant under Lorentz transformations even though their specific expression in different reference frames may be different.

Another interesting result is that qukits q_k where k is a prime number function as elementary qukits. These are the “elementary particles” as far as quantum representations of numbers are concerned. Qukits where k is not prime can be considered as composites of the prime number q_k.

If you want to delve more deeply into these matters, I must send you to Benioff’s paper. Here I want to return to the broad question of whether this line of inquiry can really lead us to some kind of quantum mathematics, as opposed to an abstract version of quantum computing. Personally, I’m not quite persuaded, although I find the proposition intriguing.

In most of this work the focus is on the representation of numbers, rather than the numbers themselves—a preoccupation that seems more characteristic of computing than of mathematics. Interesting mathematical properties of numbers tend to be independent of their representation; for example, the number seven is a prime whether you write it in decimal notation as 7, in binary as 111 or as the Roman numeral vii. Of course you must choose some representation, and the choice can make a difference in what you can accomplish. Benioff points out that unary notation (in which seven becomes 1111111) is inherently less efficient than other schemes, because the amount of work expended in manipulating a number is proportional to the number itself rather than to the logarithm of the number. For similar reasons Benioff objects to building all of arithmetic on the successor function (n → n+1). But this fretting over efficiency again suggests a more computational than mathematical frame of mind. After all, unary numbers and the successor function are essential building blocks in theories of the foundations of mathematics, such as in the Principia Mathematica of Whitehead and Russell—who were blissfully unconcerned with efficiency.

If you accept that the physical representation of mathematical objects is a fundamental issue in mathematics, then it’s an easy step to the conclusion that any such representation has to be consistent with quantum principles. But is the mathematical imagination truly fettered by the bounds of the physical universe? Mathematicians routinely reason about objects and operations that have no explicit material representation—irrational numbers, for example, or Georg Cantor’s infinite sets. A century ago, in response to another challenge from those who wanted to fence in the scope of mathematics, David Hilbert defiantly proclaimed: “No one shall expel us from the paradise that Cantor has created for us.”

If I remain a tad doubtful about the mathematical status of quantum-theoretical numbers, I do think they offer an interesting perspective on quantum computing. So far, no one has succeeded in building a practical quantum computer with a large number of interacting qubits (or qukits). Technological skeptics contend it will not be done any time soon. Benioff’s work turns this argument on its head. Quantum computers are the only ones we can build, he says, because we live in a world where quantum physics is the law of the land. We may think we have classical computers, but that’s an illusion. We merely have quantum computers that are heavily biased toward specific classical outputs, but they always retain the possibility of delivering a quantum surprise. Usually we regard computing—whether it’s done with a machine or with pencil and paper—as an approximation to a mathematical ideal. If a calculation shows that a+b does not equal b+a, we don’t question the commutative law of addition; we look for a bug or an error. But maybe we need to consider the possibility that it’s the quantum computation that’s the ultimate reality, and the mathematical law is just our convenient and tidy approximation to it.

Doing some laundry last night, I threw a duvet cover and nine pairs of socks into the dryer together. (Household hint: Don’t.) The duvet cover is a giant fabric pouch with a slit along one side; think of a queen-size pita pocket. Initially, all the socks were outside the pouch. When I pulled the load out of the dryer, all but three of the socks were inside the cover.

There’s nothing obvious about the geometry of this big, floppy bag that would suggest it has any special ability to capture socks. It’s not shaped like a fish trap with a funnel opening. In the random tumbling of the dryer, I would have thought that socks would move into or out of the opening with the same probability. But if that’s the case, then finding a 15–3 distribution is quite a fluke. There are 2¹⁸ = 262,144 ways of arranging the socks in two groups, and only 5,220 of them have three or fewer socks in one of the groups. That’s less than 2 percent and a little beyond the 2σ level of unlikelihood. Does Maxwell’s sock demon live in my dryer?

The mathematics section of the arXiv archived 989 preprints in October. Why is that fact worth noting? Because arXiv papers are identified by numbers of the format YYMMNNN, with two digits for the year, two digits for the month, and a three-digit sequence number. Ten more papers and all the world’s mathematicians would have been put on involuntary furlough, forbidden to sum another series or solve another equation until month’s end. It would have been rather like the state of New Jersey shutting down when the legislature fails to pass a budget bill. (I realize there are people who would find neither event regrettable.)

The arXiv is now introducing a new numbering scheme, with room for 9,999 papers per month. “If current growth rates continue,” says the announcment, “we expect to change the sequence number to 5-digits NNNNN in 10 to 15 years.” The new format continues to allocate two digits to the year. The arXivists seem to have no worries about disambiguating centuries. They weren’t panicked by Y2K, and apparently they’re not afraid of 9108 either, when the arXiv will have its own centenary.

Trivia note: Curiosity moved me to look up the very first paper issue by the arXiv (although the site was not then arxiv.org but rather xxx.lanl.gov). Paper 9108001 is “Exact Black String Solutions in Three Dimensions,” by James H. Horne and Gary T. Horowitz; the abstract begins, “A family of exact conformal field theories is constructed which describe charged black strings in three dimensions.” I can all too easily imagine that paper 9108.00001 in the new series will be on the same topic.

I can cook anything, as long as the recipe starts with “Take it out of the freezer” and ends with “Put it in the microwave.”

Go ahead and scoff, but I’m proud of my culinary accomplishments. Furthermore, I submit that the art of microwaving frozen foods is not without intellectual challenge. Inferior technique could leave some bits of your burrito still frozen while other parts are overcooked. The underlying cause of this well-known problem has lately been explored in depth and detail through computer simulations done by Motohiko Tanaka and Motoyasu Sato of the National Institute for Fusion Science in Toki, Japan. They present their results in an arXiv preprint.

The first mystery of microwave cookery is that it works at all. To heat a substance, you have to agitate the molecules, augmenting their random motions. Radiation at visible or infrared wavelengths does a good job of this: A visible or infrared photon is absorbed by a single molecule, which then goes bouncing off in some unpredictable direction. But microwaves are orders of magnitude too large and slow and weak to stimulate individual molecules. (In this respect the prefix micro is misleading; the wavelengths range from about a centimeter up to 10 or 20 centimeters.) A microwave’s energy is spread out over many millions of molecules—a situation that doesn’t seem like a very promising way to get them all moving in different directions.

One clue to how microwaves induce heating is what you’re not supposed to put in the microwave oven: aluminum foil. Metals have an abundance of free electrons, which are accelerated by the electric field of the microwaves. This field changes polarity a few billion times per second, and so the electrons slosh back and forth through the foil at that frequency. This motion of the electrons does not in itself constitute heating because it is not random; on the contrary, it is a highly organized oscillation—an alternating electric current. But the oscillating electrons collide with imperfections in the metal, and soon the orderly movement degrades into heat.

So much for tinfoil; most of us eat little in the way of metallic food. And nonmetals do not have an abundance of electrons (or other charged particles) free to move under the influence of an alternating electric field. What foods have is water. Although the H₂O molecule is electrically neutral, it has positive and negative poles, where opposite charges congregate (most of the positive charge on the hydrogen atoms, most of the negative charge on the oxygen). When this dipole structure is immersed in an electric field, it takes up a preferred orientation, antiparallel to the applied potential. Since the microwave field changes direction at a frequency of a few gigahertz, the water molecules must continually flip or spin to keep pace. As with the sloshing of the electrons in tinfoil, this rotation of the water molecules can’t be considered heat because it’s too orderly; all the molecules are twirling in synchrony. But in liquid water the molecules are tightly packed, and as they spin they bump into one another like dancers on a crowded floor. These collisions randomize the motion, and so the temperature of the water rises.

Tanaka and Sato study this process in a simulated volume of water measuring about 40 Ångstroms on a side and containing about 2,700 water molecules. The molecules are attracted to one another through electrical forces, but there’s also a “hard core” repulsion that prevents them from getting too close. In the simulation, all of the forces acting on each molecule are recalculated every femtosecond (10^–15 second), after which the positions and orientations of the molecules are updated. The system is allowed to come to equilibrium at a specified temperature during an initialization phase that lasts for a simulated time of 100 picoseconds (100 × 10^–12 second), and then the microwave field is turned on for 500 picoseconds. Tanaka and Sato use an unrealistically intense field—about a million volts per centimeter—in order to speed up the process. (Although the simulated time is only about half a nanosecond, the actual running time on a cluster of four-processor Pentium workstations is 48 hours.)

In liquid water at 300 Kelvins (roughly room temperature), Tanaka and Sato find that microwave heating is quite efficient: The colliding, spinning molecules raise the temperature to about 350 Kelvins. But here’s the problem: In ice, unlike liquid water, Tanaka and Sato see almost no heating. The reason is that water molecules in an ice crystal are immobilized by strong electrostatic bonds, and microwaves have too little energy to break them free. In the oscillating microwave field, the ice molecules wobble back and forth a bit, but they cannot twirl, and thus they cannot collide. Tanaka and Sato don’t explicitly discuss the culinary implications of their work, but the inference is obvious: It’s because of this icy recalcitrance to microwaves that nuking a frozen burrito takes as much skill as baking a perfect soufflé or whipping up a sauce Bearnaise.

Interestingly, microwaves also lose much of their sizzle when water is superheated to 400 Kelvins. Under these conditions, the water molecules are easily set to spinning, but the bonds between them are so feeble that the rotation is not converted into random, thermal motion. I am tempted to see a certain philosophical significance in this curious behavior. There’s been much written about the specialness of the water molecule—most notably the geometric quirk that makes solid ice lighter than liquid water. If it were otherwise—if rivers and lakes and oceans could freeze from the bottom up—life would have had a hard time getting established on planet Earth. Now we know that modern slacker civilization also depends on a peculiarity of the water molecule. If we didn’t have this glorious interval of susceptibility to microwaves in a narrow window of temperatures near 300 Kelvins, I’d have to survive on Poptarts in the toaster oven.