I’ve received the following note from Barry Cipra, bit-player’s Bureau Chief in Northfield, Minnesota, (where all hail broke loose yesterday):

Your latest postings [here and here] have motivated me to idle away some time with a variant of the problem(s) you discussed. To wit, I got to wondering what happens if you restrict yourself to taking sums of distinct pairs and positive differences of numbers from a (finite) set S — i.e., x+y and x–y with x > y in S.

It was easy, after a while, to see that the sum set is usually larger than the difference set. In particular, for the set {0, 1, 2, …, m}, the sum set is {1, 2, …, 2m–1}, while the difference set is {1, 2, …, m–1}. It seems, or at least seemed, obvious that the sum set is never smaller than the difference set, but a proof keeps slipping through my (fumbling) fingers, which suggests that either it isn’t true, or the proof is complicated, or the slow decline of my mathematical abilities has steepened and accelerated. Intuitively, each duplicate sum is associated with two duplicate differences: If a+d = b+c with a < b < c < d, then d–b = c–a and d–c = b–a. The problem, of course, is that you can have duplicate duplicates.

It seemed worth looking at how the sum/difference ratio tends toward 2 as one “grows” a set S by randomly adding numbers between 1 and some large upper bound, say m = 10,000. I wrote, ran, debugged, ran, debugged,…., and finally ran successfully a little (Basic) program to do this, and tried it with various values of m, printing out the ratio as each new (random) element got added. The number of elements required to reach any given ratio r (less than 2) seems to be proportional to sqrt(m). In particular, the number of elements to reach r=1.5 seems to be 2*sqrt(m). It would be most gratifying if this turned out to be asymptotically exact.

Barry also points out a connection with the birthday “paradox.” Here on Earth, any gathering of 23 or more people has a better-than-even chance of including at least two people with the same birthday. On Mars, where the year has 687 days, you need to assemble 32 people to have a fifty-fifty chance of such a coincidence. On Saturn, where people can have any of 1,055 birthdays, the minimum size of the group is 39. (I would add that on Pluto, with a year of 14,158 Plutonian days, the minimum likely size for a double-birthday party is 141 people. However, there can’t be that many people on Pluto, since it’s only a dwarf planet.) Anyway, the point of all this is that the number of people needed for a birthday coincidence grows in proportion to the square root of the number of possible birthdays. The calculation is similar when it comes to the number of elements in a set drawn at random from {0, 1, 2, …, m}, except that the probability we’re interested in is not that of finding two identical elements but rather that of having two pairs of elements with the same sum or difference.

Barry’s version of the problem has a satisfying symmetry. For both sums and differences, we’re looking at the upper triangle of a matrix, excluding the diagonal and everything below it. If there are no duplicates, or coincidences, then the sum set and the difference set are necessarily of the same size.

Inspired by Barry’s example, I have idled away a few of my own declining hours, and gone off on a bit of a tangent.

In an arbitrary finite set of non-negative integers, suppose there are n elements, and the largest element is m. If m is much larger than n, coincidences are unlikely among both the sums and the differences; in the limiting case, they have probability zero. If m = n–1, then the set must be the arithmetic progression {0, 1, 2, …, m}, and the number of coincidences is maximized. Barry’s algorithm for adding randomly chosen numbers to a set, one at a time, can be viewed as a way of exploring the transition between these two extremes. We can ask, at each stage of the process: What is the probability that a randomly chosen number, distinct from all the existing elements of the set, can be adjoined to the set without generating a coincidence?

Here is a somewhat different question. Instead of choosing numbers at random to add to the set, suppose we always insert the smallest number that can be adjoined to the set without creating a coincidence. In other words, we build the set from the bottom up. What does the resulting set look like?

First consider just the constraints imposed by the sum set, ignoring coincidences among differences. Starting from the empty set {}, we can obviously go on to {0} and then to {0, 1}. Next we can insert 2, because the three sums 0+1 = 1, 0+2 = 2 and 1+2 = 3 are all distinct. But we cannot add 3 to the set, because that would introduce the coincidence 0+3 = 1+2. The next permissible element is 4; the set {0, 1, 2, 4} produces the sum set {1, 2, 3, 4, 5, 6} without coincidences. Going on from there, both 5 and 6 are excluded, but 7 is okay. Working with pencil and paper, I extended this set as far as {0, 1, 2, 4, 7, 12, 20, 29}. This gave me enough to go consult the Oracle of AT&T. I found the sequence listed as No. A010067 in Neil Sloane’s Encyclopedia of Integer Sequences. The sequence is described as follows: “A B₂ sequence: a(n) = least value such that sequence increases and pairwise sums of distinct elements are all distinct.” This was just what I had been looking for, and the success boosted my confidence that at least I had done the arithmetic right.

Now I tried the same method with the differences. Again the first few sets that yield no coincidences are {], {0} and {0, 1}, but in the subtractive case {0, 1, 2} fails, because 2–1 = 1–0. On the other hand, {0, 1, 3} is without conflicts. The series continues {0, 1, 3, 7, 12, 20, 30}. It was time to visit the Oracle again. This sequence is No. A025582, but the identifying tag line is not quite what I was expecting: “A B₂ sequence: a(n) = least value such that sequence increases and pairwise sums of elements are all distinct.” I had generated the series by looking at differences of distinct elements, but it turns out that sums of not-necessarily-distinct elements yield the same series. Curious.

Let’s consider the element-by-element differences between these two sequences, which I’m going to call S(n) for the sums of distinct pairs and D(n) for the differences of distinct pairs:

   n        D(n)       S(n)      D(n)-S(n)
   0          0          0            0
   1          1          1            0
   2          3          2            1
   3          7          4            3
   4         12          7            5
   5         20         12            8
   6         30         20           10
   7         44         29           15
   8         65         38           27
   9         80         52           28
  10         96         73           23
  11        122         94           28
  12        147        127           20
  13        181        151           30
  14        203        181           22
  15        251        211           40
  16        289        257           32
  17        360        315           45
  18        400        373           27
  19        474        412           62
  20        564        475           89

From the first few entries in this table one might well guess that the sums will always be lagging behind the differences, so that the D(n) – S(n) sequence grows monotonically. But then there’s a reversal at n = 10, and after that it’s not clear exactly what the trend will be. The obvious question is: Can S(n) ever be greater than D(n)? This time the Oracle can’t help us; a Sequence Server search for {0, 0, 1, 3, 5, 8, 10, 15, 27, 28} comes up empty.

I tried producing a few more terms of S(n) and D(n) and their differences. Struggling with a grotesquely inefficient program, I invested an hour of cpu time, which got me as far as n = 60:

   n        D(n)       S(n)      D(n)-S(n)
   0          0          0            0
   1          1          1            0
   2          3          2            1
   3          7          4            3
   4         12          7            5
   5         20         12            8
   6         30         20           10
   7         44         29           15
   8         65         38           27
   9         80         52           28
  10         96         73           23
  11        122         94           28
  12        147        127           20
  13        181        151           30
  14        203        181           22
  15        251        211           40
  16        289        257           32
  17        360        315           45
  18        400        373           27
  19        474        412           62
  20        564        475           89
  21        592        530           62
  22        661        545          116
  23        774        607          167
  24        821        716          105
  25        915        797          118
  26        969        861          108
  27       1015        964           51
  28       1158       1059           99
  29       1311       1160          151
  30       1394       1306           88
  31       1522       1385          137
  32       1571       1434          137
  33       1820       1555          265
  34       1895       1721          174
  35       2028       1833          195
  36       2253       1933          320
  37       2378       2057          321
  38       2509       2260          249
  39       2779       2496          283
  40       2924       2698          226
  41       3154       2873          281
  42       3353       3060          293
  43       3590       3196          394
  44       3796       3331          465
  45       3997       3628          369
  46       4296       3711          585
  47       4432       3867          565
  48       4778       4139          639
  49       4850       4446          404
  50       5122       4639          483
  51       5242       5021          221
  52       5297       5064          233
  53       5750       5322          428
  54       5997       5613          384
  55       6373       6003          370
  56       6800       6273          527
  57       6924       6493          431
  58       7459       6641          818
  59       7546       6979          567
  60       7788       7275          513

Would you care to place a bet on the further behavior of this series? At n = 60, D(n) – S(n) looks like it’s still growing, on the average, but it’s also still fluctuating. Will any of the dips in the curve ever plunge deep enough to bring the balance below zero? Or will the overall upward trend prevail in the long run? Maybe it’s like π(x) – Li(x) in number theory. This function—the difference between the actual number of primes up to x and an estimate proposed by C. F. Gauss—is negative for all values of x anyone has ever calculated explicitly. Nevertheless, there’s a proof that π(x) – Li(x) does eventually become positive; indeed, it changes sign infinitely often. But the first such zero crossing is somewhere out in the remotest exurbs of the number line.

I debated: Is it worth the bother of writing a better program to add a few more lines to the table? If D(n) – S(n) is positive for all values of n up to n = 60, what is the probability of discovering a negative value at n = 61, or even n = 600? I have no idea how to answer that question mathematically, but psychologically the prospects seemed pretty dim. Nevertheless, I wrote the program. Here are the next four entries in the table:

   n        D(n)       S(n)      D(n)-S(n)
  61       8219       7587          632
  62       8502       8017          485
  63       8729       8373          356
  64       8941       9071         -130

There it is: S(64) is greater than D(64). And I soon learned that this excursion into negative territory is not a one-of-a-kind freak occurrence. In the interval between n = 0 and n = 500, D(n) – S(n) is positive for 301 values, negative for 198 values and 0 for 2 values. It seems a reasonable conjecture that positive and negative values occur equally often. Here’s a graph of D(n) – S(n) for n = 0 to n = 250:

Final note: Although I have just today blundered down this interesting path, I am assuredly not the first to pass this way. I gather that I need to do some reading on Sidon sequences. Are there also connections with Golomb rulers?

Kevin O’Bryant, whose work on sets that have more sums than differences was mentioned in this recent post, writes as follows:

Here’s a related problem that Mel Nathanson and myself (with Ruzsa and a few students) have also been thinking about. For a finite set A of integers, let S = {a + b : a,b \in A} be the sumset, and let T = {2a + b : a,b \in A}. Can it happen that S is larger than T? The answer is yes (we have a proof) but we don’t have a single example. Our proof gives a set that would have at least e²⁰⁰⁰ elements, so although our proof is “constructive”, it really isn’t in any practical sense. My professors thought “constructive” referred to a proof that didn’t use the axiom of choice, my generation thinks of it as an algorithm that runs in polynomial time, my students will have to worry about which polynomial. :)

Note that this problem, like the original MSTD problem, has the pleasant property of affine invariance: You can scale or translate the elements of the set by any constant, and the size of the S and T sets remains unchanged. In the case of an arithmetic progression, such as the n-element set {0, 1, 2,…, n–1}, the sumset S has 2n–1 elements, whereas the set T has 3n–2 elements. Thus |T| is greater than |S| by about n. For a random sampling of sets other than arithmetic progressions, it appears that |T| usually exceeds |S| by an even larger margin. I have no idea where to look for that elusive example with |T| < |S|.

Take a set of integers, say {0, 2, 5, 8, 11}, and write down all the numbers that can be represented as sums of two elements drawn from this set. For our example the answer is {0, 2, 4, 5, 7, 8, 10, 11, 13, 16, 19, 22}. Now construct the corresponding set of pairwise differences: {–11, –9, –8, –6, –5, –3, –2, 0, 2, 3, 5, 6, 8, 9, 11}. Note that there are only 12 distinct sums but 15 differences.

Let’s try it with another set, {5, 8, 17, 26, 41}:

sums: {10, 13, 16, 22, 25, 31, 34, 43, 46, 49, 52, 58, 67, 82}
diffs: {–36, –33, –24, –21, –18, –15, –12, –9, –3, 0, 3, 9, 12, 15, 18, 21, 24, 33, 36}

Again the differences outnumber the sums, this time by a margin of 19 to 14.

It’s not hard to see why differences tend to be more numerous: Addition is commutative but subtraction isn’t. Thus the sums 5+8 and 8+5 both yield the single result 13, whereas 5–8 and 8–5 produce two distinct differences, –3 and +3. It is rumored that someone other than John Horton Conway once conjectured that the number of sums formed in this way never exceeds the number of differences. But the conjecture is false. A counterexample is the set {0, 2, 3, 4, 7, 11, 12, 14}, which has 26 distinct pairwise sums but only 25 differences:

sums: {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 28}
diffs: {–14, –12, –11, –10, –9, –8, –7, –5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14}

Melvyn B. Nathanson of Lehman College—the Bronx campus of the City University of New York—has lately called attention to such anomalous sets of integers, which he identifies by the abbreviation MSTD (more sums than differences). He has lots of questions. Why do such sets exist? Where are they found? How many are there? What is their structure?

This past April Nathanson discussed MSTD sets in a talk titled “Problems in Additive Number Theory” at the University of Montreal; the talk is available on the arXiv as math.NT/0604340. In June Nathanson delivered a follow-up talk, “Sets with More Sums than Differences,” at the SIAM Conference on Discrete Mathematics in Victoria, British Columbia; that paper was released last week on the arXiv as math.NT/0608148. Meanwhile Kevin O’Bryant of the College of Staten Island (another CUNY unit) has addressed somewhat different aspects of the MSTD problem in a paper titled “Many Sets Have More Sums than Differences” (math.NT/0608131).

The appeal of a problem like this one is that it seems to get a lot of mileage out of the simplest mathematics: adding, subtracting and counting—operations that most of us know how to do. As the papers of Nathanson and Bryant show, the math is not all so trivial, and yet an amateur like me can still hope to have some fun with these questions. I’ve been toying with MSTD sets for the past week or so.

First, a few preliminaries. A set, as defined for this discussion, is a collection of items without duplicates. For example, {1, 3} is a two-element set. There are four ways to add these elements in pairs—1+1, 1+3, 3+1 and 3+3—but two of those summations yield the same result, and so the “sumset” has just three elements, {1, 4, 6}. The order of the elements in a set has no significance, but for convenience I’ll always list them in ascending sequence. All the sets discussed here are finite.

For a clearer understanding of set sums and differences, it helps to write down an example in matrix format:

A set of n elements has n² pairwise sums and differences, but they are not all distinct. In the case of the sums, the matrix is symmetric, and so everything above the main diagonal is duplicated below it. Thus the maximum possible number of unique sums is given by counting the entries along the diagonal plus those in either the upper or the lower triangle, but not both. This number is equal to n(n+1)/2; for the example given here, where n=4, the maximum size of the sumset is 10. However, for the specific set shown here the maximum is not attained, because of a few “coincidences”: 4 appears as both 0+4 and 2+2, and 6 arises as both 2+4 and 3+3. Thus the sumset has only eight elements: {0, 2, 3, 4, 5, 6, 7, 8}.

The difference matrix is antisymmetric, and so the elements of both the upper and the lower triangles need to be counted. On the other hand, the diagonal of the difference matrix is all zeros. The maximum number of distinct differences is n(n–1)+1. Again, though, the maximum is not reached in this example; coincidences reduce the size of the “diffset” from 13 to 9. Still, the differences outnumber the sums, and so {0, 2, 3, 4} is not an MSTD set.

The smallest possible sumset or diffset has 2n–1 elements. (You might want to work out why.) It’s easy to construct a set that attains this minimum: Just choose elements in an arithmetic progression. For example, the set {0, 2, 4, 6} has the sumset {0, 2, 4, 6, 8, 10, 12} and the diffset {–6, –4, –2, 0, 2, 4, 6}, both of size 7. It’s also straightforward to build a set that generates the largest possible sumset and diffset; the trick is to make each element more than twice as large as the next smaller element, as in the set {0, 1, 3, 7}. This structure eliminates all coincidental duplicates in both the sums and the differences.

In the search for MSTD sets we don’t have to look at all possible sets of integers. It turns out that both the number of sums and the number of differences generated by a set remain unchanged if you add a constant to each member of the set. Likewise, multiplying each element by a constant also leaves the number of sums and differences invariant. In other words, you can transform each element x into ax+b (an affine transformation) without altering the size of the sumset or the diffset. This property is important because it means we can represent any MSTD set in a canonical form. We can shift it along the number line until its smallest element is 0, and we can shrink it down to its smallest possible span of integers by dividing out any factors that are common to all the nonzero elements. For example, the set {5, 8, 17, 26, 41} mentioned above has the canonical form {0, 1, 4, 7, 12}. Both of these sets have 19 differences and 14 sums.

Now for some questions.

What is the smallest MSTD set? The smallest known set is the example {0, 2, 3, 4, 7, 11, 12, 14} that I have already introduced. It has eight elements, and in the canonical representation the largest element is 14. There is one other known eight-element example, {0, 2, 3, 7, 10, 11, 12, 14}. A few seconds of computing is all it takes to show that there is no smaller eight-element MSTD set. But is there an example with fewer than eight elements? I don’t think so, but I can’t prove it. A brute-force search rules out any MSTD set with seven or fewer elements where the largest element is less than 81. Imre J. Ruzsa of the Mathematical Institute of the Hungarian Academy of Sciences claims that any MSTD set must have at least seven elements.

How many MSTD sets are there? In one sense, this is a very easy question. Given the affine invariance of MSTD sets, if just one such set exists, then we can generate infinitely many of them by translation and dilation. But most people would agree that these are all just copies of the same set in disguise. What we really want to know is the number of MSTD sets when they are all reduced to canonical form. Nathanson has shown that in this scheme of reckoning, too, the number of sets is infinite. He gives a formula for generating infinite families of MSTD sets. Starting with the example {0, 2, 3, 4, 7, 11, 12, 14}, the formula yields a sequence of progressively larger sets that Nathanson proves must all have more sums than differences: {0, 2, 3, 4, 7, 11, 15, 16, 18}, then {0, 2, 3, 4, 7, 11, 15, 19, 20, 22}, then {0, 2, 3, 4, 7, 11, 15, 19, 23, 24, 26}, and so on. The question then arises, are all MSTD sets members of such infinite families, or are there also “sporadic” MSTD sets?

How rare are MSTD sets? Having already established that there are infinitely many MSTD sets, it might seem that they can’t be very rare, but that’s not necessarily true. The primes are also infinite, yet they are vanishingly rare. Take the ratio of the number of primes less than N to the number of integers less than N; as N goes to infinity, the ratio goes to zero. MSTD sets could be rare in a similar sense. O’Bryant shows that within a certain infinite series of integer sets, the probability of finding an MSTD set is greater than zero. Does that result hold also for integer sets in general?

By how much can the number of sums exceed the number of differences? Let’s define the discrepancy Δ of a set as the number of differences minus the number of sums. For all “ordinary” sets, Δ ≥ 0. For MSTD sets, Δ is negative. In all the MSTD examples I’ve shown so far, Δ = –1, or in other words the number of sums is just 1 greater than the number of differences. I’ve been able to find lots of sets with Δ = –2; the smallest, with 11 elements, is {0, 1, 2, 4, 5, 9, 12, 13, 14, 16, 17}, which has 35 sums and only 33 differences. I’ve also stumbled upon a few sets with Δ = –3, such as the 16-element set {0, 1, 2, 4, 5, 9, 12, 13, 14, 16, 17, 21, 24, 25, 26, 28}, which has 56 sums and 53 differences. I’m guessing there is no lower bound on Δ. (Update: As I was smoothing out the last details of this report, I discovered a 1973 paper by Sherman K. Stein. He proves that the ratio of the number of differences to the number of sums can be made arbitrarily large or small.)

How are MSTD sets distributed among all integer sets? The trouble with even asking a question like this is that we can’t look at all integer sets. If we try to answer the question statistically, by choosing a representative sample of sets, then we have to wade into the messy business of deciding what sort of sample is representative. For lack of a better idea, I have tried the following approach. Assuming that all sets are in canonical form, I classify them by two parameters: n, the number of elements, and m, the largest element. Then for any given values of n and m I can either examine all sets (if n and m are small enough) or generate a random sample. Note that m cannot be less than n–1. If m = n–1, then there is only one possible set, namely the counting sequence 0, 1, 2,…, m. As m increases for a fixed value of n, so does the number of possible sets and the average gap between the elements. Now we can ask how Δ varies as a function of m and n. In the case of m = n–1, the answer can be given unequivocally: Δ = 0, because the set is an arithmetic progression, and both the number of sums and the number of differences is 2n–1. When m is much greater than n, Δ is almost surely positive. The reason is that the elements of the set are widely dispersed, and a coincidence in which different pairs of elements yield the same sum or the same difference is unlikely. In almost all sets with m >> n, the number of sums takes its maximum value n(n+1)/2 and the number of differences is also at its maximum, n(n–1)+1. If you do the subtraction, you’ll find that Δ increases in proportion to n².

The interesting region would appear to be the middle ground, where m is not too much larger than n. Here is a graph showing the frequency of Δ values for n = 10 and all values of m between 9 and 27.

As m increases, the distribution grows wider and shifts to the right—toward more-positive values of Δ. (Note that the graph is based on a complete enumeration of all sets, not on a statistical sampling.)

MSTD sets are so rare that in the graph above their frequency is indistinguishable from zero. Below we look exclusively at the frequency of MSTD sets as a function of m for three values of n.

It appears that MSTD sets are most common (or maybe one should say least rare) at the smallest value of m where such sets first appear. But this impression is somewhat misleading. As the graph below reveals, the absolute number of MSTD sets increases as a function of m (or, in the case of n = 8, remains constant). Although it’s true that the proportion of MSTD sets declines, that’s only because the total number of integer sets grows exponentially with m.

Thus if you are wandering aimlessly in the universe of integer sets, the number of sets with more sums than differences increases with m, but the probability that a randomly encountered member of the population has the MSTD property falls to zero as m increases.

Finally, where did this problem come from? The locus classicus appears to be an unpublished 1967 edition of a list of unsolved problems compiled by Hallard T. Croft of the University of Cambridge. Other authors, citing the Croft list, attribute the conjecture that differences always outnumber sums to John Horton Conway. Nathanson writes, however: “I asked Conway about this at the Logic Conference in Memory of Stanley Tennenbaum at the CUNY Graduate Center on April 7, 2006. He said that he had actually found a counterexample to the conjecture, and that this is recorded in unpublished notes of Croft.” The mention of Croft refers to the same 1967 list that others cite in attributing the conjecture to Conway. I have not seen this document; if anyone can send me a copy, I would be most grateful. Here are a few more slightly less obscure references:

Marica, John. 1969. On a conjecture of Conway. Canadian Mathematical Bulletin 12:233–234.

Ruzsa, Imre Z. 1984. Sets of sums and differences. In Séminaire de Théorie des Nombres, Paris, 1982–83, pp. 267–273. Boston: Birkhäuser.

Ruzsa, I. Z. 1992. On the number of sums and differences. Acta Mathematica Hungarica 59:439–447.

Stein, Sherman K. 1973. The cardinalities of A+A and A–A. Canadian Mathematical Bulletin 16:343–345.

The new issue (September-October) of American Scientist is available on the Web, and subscribers to the ink-and-paper edition should receive copies soon. My “Computing Science” column is more topical than I would like, given today’s headlines. I examine some ideas from graph theory and social-networking studies that intelligence agencies may (or may not—who knows?) be using to detect terrorist conspiracies.

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.

The banner image at the top of this page might be taken for an algorithmic attempt to imitate a fern, although in my opinion the pattern bears a closer resemblance to the two-dimensional corals known as sea fans, or gorgonians. The image below also reminds me of some sort of sessile sea creature—if not a sea fan, then maybe a crinoid.

I discovered this pattern (and several others like it) in the flagstones of a newly laid sidewalk on the campus of Duke University, and I assumed I was looking at a fossil of some kind. However, a helpful and erudite construction worker, who noticed me taking photographs, stopped to tell me that such patterns are of inorganic origin; they are produced by a mineral stain (probably an iron compound) propagating through the pores of the rock. This explanation makes the resemblance to my banner image somewhat more interesting and less of a coincidence. The banner pattern is generated by an algorithm called diffusion-limited aggregation, in which particles move randomly until they happen to touch the tendrils of the growing aggregate; then they stick fast. It’s not hard to imagine how molecules migrating through rock might behave in a similar way, but I have been unable to learn anything more about the origin of these flagstone false fossils. I’ll be grateful if anyone can enlighten me.

Update 2006-08-07: A helpful reader (see comment below, and thankyou Frank Horowitz) has provided exactly the clue I was seeking. Searching for “dentritic patterns” in combination with various other terms turns up lots of relevant references. The one closest to the mark is a splendid discussion by Jonathan Wonham in a blog called Connaissances. There’s also the fascinating story of Mochaware pottery.

Update 2006-08-09: I am deeply grateful to Florian Walchak, who points out (in the comment below) that the question I raised had been answered 300 years ago!

Update 2006-12-06: Further commentary and links.

A few years ago Michael Berry revealed that his first choice in reading matter, if he were stranded on a desert island, would be Abramowitz and Stegun, also known as Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, published by the National Bureau of Standards in 1964. For those of you seeking lighter fare for the beach this summer, I can recommend an article about Abramowitz and Stegun, written by David Alan Grier and appearing in the new issue of The American Mathematical Monthly. The article runs to 12 pages, making it considerably easier to fit in your tote bag than the xiv+1046 pages of the original.

Although I’ve had occasion to consult Abramowitz and Stegun from time to time, I have to admit that it never occurred to me to ask who Abramowitz and Stegun are or were, or how they came to compile their collection of formulas, graphs and tables. Yet it’s a fascinating story—a real page-turner! I don’t want to give it all away, so I’ll offer just a few teasers:

• Grier dispatches one of the two protagonists in the very first paragraph. Milton Abramowitz helped frame the project, but: “His role ended on a hot summer’s day in 1958, when he unwisely decided to mow the lawn of his home in suburban Washington. Succumbing to the heat, he collapsed and died, leaving Stegun as the sole editor.”
• Stegun is Irene Stegun (still living), who was “desperate for permanent employment” in 1943 and took a job with the Mathematical Tables Project, which was eventually absorbed into the National Bureau of Standards.
• The Mathematical Tables Project was launched in 1937 under the Works Progress Administration, the New Deal unemployment-relief agency. It created jobs for 450 “computers” in New York City. “All of the project’s computers were drawn from the city’s welfare rolls and were desperately poor. Most had been unemployed for at least a year. Only a few had attended high school.”
• Abramowitz and Stegun were not among the 450 computers but were mathematicians on the project’s Planning Committee. Yet even the members of this elite, according to Grier, “came from the margins of the mathematical community, from the ranks of people who lacked doctorates, or who were unemployed, or who were not fully considered scientists.”

Here are the bibliographic details for the Grier article: “Irene Stegun, the Handbook of Mathematical Functions, and the Lingering Influence of the New Deal,” by David Alan Grier, The American Mathematical Monthly, Vol. 113, No. 7, August-September 2006, pp. 585-597. It’s not available online. On the other hand, if your beach has WiFi, you can read Abramowitz and Stegun here and here and doubtless elsewhere.

Incidentally, Michael Berry’s second choice for his desert-island library is Gradshteyn and Ryzhik, or Table of Integrals, Series and Products, the Russian equivalent of Abramowitz and Stegun. This is also a book with lore and legend behind it. Specifically, the legend is that one of the authors was shot when an error in a table caused an aircraft or a missile to crash. That’s surely untrue, but I hope someday we’ll learn the real story. Maybe it will be next summer’s beach reading.