The image above shows the mesh top of a patio table, photographed after a soaking rain. Some of the openings in the mesh retain drops of water. What can we say about the distribution of those drops? Are they sprinkled randomly over the surface? The rainfall process that deposited them certainly seems random enough, but to my eye the pattern of occupied sites in the mesh looks suspiciously even and uniform.

For ease of analysis I have isolated a square piece of the tabletop image (avoiding the central umbrella hole), and extracted the coordinates of all the drops within the square. There are 394 drops, which I plot below as blue dots:

Again: Does this pattern look like the outcome of a random process?

I come to this question in the aftermath of writing an American Scientist column that explores two varieties of simulated randomness: pseudo and quasi. Pseudorandomness needs no introduction here. A pseudorandom algorithm for selecting points in a square tries to ensure that all points have the same probability of being chosen and that all the choices are independent of one another. Here’s an array of 394 pseudorandom dots constrained to lie on a skewed and rotated lattice somewhat like that of the mesh tabletop:

Quasirandomness is a less familiar concept. In selecting quasirandom points the aim is not equiprobability or independence but rather equidistribution: spraying the points as uniformly as possible across the area of the square. Just how to achieve this aim is not obvious. For the 394 quasirandom dots shown below, the x coordinates form a simple arithmetic progression, but the y coordinates are permuted by a digit-twiddling process. (The underlying algorithm was invented in the 1930s by the Dutch mathematician J. G. van der Corput, who worked with one-dimensional sequences, and extended to two dimensions in the 1950s by K. F. Roth. For more details, see my American Scientist column, page 286, or the splendid book by Jiri Matousek.)

Which of these point sets, the pseudo or the quasi, is a better match for the raindrops? Here are the three patterns in miniature, placed side-by-side as an aid to comparison:

Each of the panels has a distinctive texture. The pseudorandom pattern has both tight clusters and large voids. The quasirandom dots are more evenly spaced (though there are several close pairs of points), but they also form distinctive, small-scale repetitive motifs, most notably a hexagonal structure that repeats with not-quite-crystalline regularity. As for the raindrops, they appear to be spread over the area at almost uniform density (in this respect resembling the quasirandom pattern), but the texture shows hints of swirly rather than latticelike structures (more like the pseudorandom example).

Rather than just eyeballing the patterns, we could try a quantitative approach to describing or classifying them. There are lots of tools for this purpose—radial distribution functions, nearest-neighbor statistics, Fourier methods—but my main motive for bringing up this question in the first place is to play with a new toy that I learned about in the course of reading up on quasirandomness. It is a quantity called discrepancy, which attempts to measure how much a point set departs from a uniform spatial distribution.

There are lots of variations on the concept of discrepancy, but I’m going to discuss just one measurement scheme. The idea is to superimpose rectangles of various shapes and sizes on the pattern, allowing only rectangles with sides parallel to the x and y axes. Here are three example rectangles drawn on the raindrop pattern:

Now count the number of dots enclosed by each rectangle, and compare it with the number of dots that would be enclosed—based on the rectangle’s area—if the distribution of dots were perfectly uniform throughout the square. The absolute value of the difference is the discrepancy D(R) associated with rectangle R:

D(R) = | N · area(R) – #(P ∩ R) |,

where N is the total number of dots and #(P ∩ R) denotes the number of dots P in rectangle R. For example, the rectangle at the upper left covers 10 percent of the area of the square, so its fair share of dots would be 0.1 × 394 = 39.4 dots. The rectangle actually encloses only 37 dots, and so the discrepancy associated with the rectangle is |39.4 — 37| = 2.4. Note that the density of dots in the rectangle could be either higher or lower than the overall average; in either case the absolute-value operation would give a positive discrepancy.

For the pattern as a whole, we can define the global discrepancy D as the worst-case value of this measure, or in other words the maximum discrepancy taken over all possible rectangles drawn in the square. Van der Corput asked whether point sets could be constructed with arbitrarily low discrepancy, so that D would always remain below some fixed bound as N goes to infinity. The answer is No, at least in one and two dimensions; the minimal growth rate is O(log N). Pseudorandom patterns generally have even higher discrepancy, O(√N).

How can you find the rectangle that has maximum discrepancy for a given point set? When I first read the definition of discrepancy, I thought it would be impossible to compute exactly, because there are infinitely many rectangles to be considered. But after thinking about it a while, I realized there are only finitely many candidate rectangles that might possibly maximize the discrepancy. They are the rectangles in which each of the four sides passes through at least one dot. (Exception: Candidate rectangles can also have sides lying on the boundary of the enclosing square.)

Suppose we encounter the following rectangle:

The left, top and bottom sides each pass through a dot, but the right side lies in “empty space.” This configuration cannot be the rectangle of maximum discrepancy. We could push the right edge leftward until it just intersects a dot:

This change in shape reduces the area of the rectangle without altering the number of dots enclosed, and thus increases the density of dots. Alternatively, we could push the edge the other way:

Now we have increased the area, again without changing the count of enclosed dots, and thereby lowered the density. At least one of these actions must increase D(R), compared with the initial configuration. Thus every rectangle with all four sides touching dots or the edges of the square is a local maximum of the discrepancy function; by enumerating all rectangles in this finite set, we can find the global maximum.

There is also the irksome question of whether the rectangle is to be considered “closed” (meaning that points on the boundary are included in the area) or “open” (boundary points are excluded). I’ve sidestepped that problem by tabulating results for both open and closed boundaries. The closed form gives the highest discrepancy for densely populated rectangles, and the open form maximizes discrepancy for sparsely populated rectangles.

By considering only extrema of the discrepancy function, we make the counting problem finite—but not easy! In a square with N dots (all with distinct x and y coordinates), how many rectangles have to be considered? This turns out to be a really sweet little problem, with a simple combinatorial solution. I’m not going to reveal the answer here, but if you don’t feel like working it out for yourself, you could look it up in the OEIS or see a short paper by Benjamin, Quinn and Wurtz. What I will say is that for N = 394, the number of rectangles is 6,055,174,225—or double that if you count open and closed rectangles separately. For each rectangle, it’s necessary to figure out how many of the 394 points are inside and how many are outside. Pretty big job.

One way to reduce the computational burden is to retreat to a simpler measure of discrepancy. Much of the literature on quasirandom patterns in two or more dimensions uses a quantity called star discrepancy, or D*. The idea is to consider only rectangles “anchored” at the lower left corner of the square (which we can conveniently identify with the origin of the xy plane). In this case the number of rectangles is just N², or about 150,000 for N = 394.

Here is the rectangle that defines the global star discrepancy of the raindrop pattern:

The dark green rectangle at the bottom covers about 55 percent of the square and ought to encompass 216.9 dots, if the distribution were truly uniform. The actual number of dots included (assuming a “closed” rectangle) is 238, for a discrepancy of 21.1. No other rectangle anchored to the corner (0,0) has a greater discrepancy. (Note: Because of limited graphic resolution, the D* rectangle appears to extend horizontally all the way across the unit square; in fact the right edge lies at x = 0.999395.)

What does this result tell us about the nature of the raindrop pattern? Well, for starters, the discrepancy is fairly close to √N (which is 19.8 for N = 394) and not particularly close to log N (which is 6.0 for natural logs). Thus we get no support for the idea that the raindrop pattern might be more quasirandom than pseudorandom. The D* values for the other patterns shown above are in the ranges expected: 25.9 for the pseudorandom and 4.4 for the quasirandom. Contrary to the visual impression, the raindrop distribution seems to have more in common with a pseudorandom point set than a quasirandom one—at least by the D* criterion.

What about calculating the unrestricted discrepancy D—that is, looking at all rectangles rather than just the anchored rectangles of D*? A moment’s thought shows that this exhaustive enumeration of rectangles can’t change the basic conclusion in this case; D can never be less than D*, and so we can’t hope to move from √N toward log N. But I was curious about the computation anyway. Among those six billion rectangles, which one has the greatest discrepancy? Is it possible to answer this question without heroic efforts?

The obvious, straightforward algorithm for D generates all candidate rectangles in turn, measures their area, counts the dots inside, and keeps track of the extreme discrepancies seen along the way. I found that a program implementing this algorithm could determine the exact discrepancy of 100 pseudorandom or quasirandom dots in a few minutes. This outcome might seem to offer some encouragement for pushing on to higher N; however, the running time almost doubles every time N increases by 10, which suggests the computation would take a couple of centuries at N = 394.

I’ve invested a few days’ work in efforts to speed up this calculation. Most of the running time is spent in the routine that counts the dots in each rectangle. Deciding whether a given dot is inside, outside or on the boundary takes eight arithmetic comparisons; thus, at N = 394, there are more than 3,000 comparisons for each of the six billion rectangles. The most effective time-saving device I’ve discovered is to precompute all the comparisons. For each point that can become the lower left corner of a rectangle, I precompute a list of all the pattern dots above and to the right. For each potential upper right corner of a rectangle, I compile a similar list of dots below and to the left. These lists are stored in a hash table indexed by the corner coordinates. Given a rectangle, I can then count the number of interior dots just by taking the set intersection of the two lists.

With this trick, the estimated running time for N = 394 came down from two centuries to about two weeks. A big improvement—just enough encouragement to induce me to spend yet another day on further refinements. Replacing the hash table with an N × N array helped a little. And then I figured out a way to ignore all the smallest rectangles, those that cannot possibly be the max-D rectangle because they either contain too few dots or have too small an area. This improvement finally brought the running time down to the overnight range. The illustration below, which shows the rectangle of maximum discrepancy D for the raindrop pattern, took six hours to compute.

The max-D rectangle is clearly a slight refinement of the D* rectangle for the same point set. The D rectangle “should” contain 204.3 dots but actually has 229, for a discrepancy of D = 24.7.

Of course knowing that the exact discrepancy is 24.7 rather than 21.1 tells us nothing more about the nature of the raindrop pattern. As a matter of fact, I feel I know less and less about it as I compute more and more.

When I started this project, I had a pet theory about what might be happening in the tabletop to smooth out the distribution of drops and thereby make the pattern look more quasi- than pseudorandom. To begin with, think of droplets lying on a smooth pane of glass rather than a metal mesh. If two small droplets come close enough to touch, they merge into one larger drop, because that configuration has lower energy associated with surface tension. Perhaps something similar could happen in the mesh. If two adjacent cells of the mesh are both filled with water, and if the metal channel between them is wet, then water could flow freely from one drop to the other. The larger drop will almost surely grow at the expense of the smaller one, and the latter will eventually be annihilated. Thus we would expect a deficit of drops in adjacent cells, compared with a purely random distribution.

This idea still sounds pretty good to me. The only trouble is: It explains a phenomenon that may not exist. I don’t know whether my discrepancy measurements actually reveal anything important about the three patterns, but at the very least the measurements fail to provide evidence that the raindrop distribution is different from the pseudorandom distribution. True, the patterns look different, but how much should we trust our perceptual apparatus in a case like this? If you ask people to draw dots at random, most do a bad job of it, typically making the distribution too smooth and even. Maybe the brain is equally challenged when trying to recognize randomness.

Nevertheless, I suspect there is some mathematical property that will more effectively distinguish between these patterns. If anyone else would like to sink some time into the search, the xy coordinates for the three point sets are in a text file here.

Update 2011-06-24: This is just a brief note to suggest that if you’ve read this far, please go on and read the comments, too. There’s much of value there. I want to thank all those who took the trouble to propose alternative explanations or algorithms, and to point out weaknesses in my analysis. Special thanks to themathsgeek, who within 40 minutes after I first posted the item had come up with a far superior program for computing discrepancies. Also Iain, who pursued my offhand remarks about the perception of random patterns with actual experiments.

The first snow of the season is always a treat. When the flakes start flying, I want to go out and play. I even want to go out and shovel.

Here in the Boston area our first storm left a particularly magical landscape. Glistening flakes fell steadily all night, with little wind, so that every fencepost was topped by a fluffy white pompom in the morning. The decorations were remarkably regular and symmetrical. In the photo below I have carved a cross-section out of the snow lying atop the back-porch railing, which is 3½ inches wide.

The profile looks like a fairly good approximation to a semicircle. (Below is a red semicircle fitted to the image by eye.)

Later, I began wondering why the snow would assume just this shape. Is it an equilibrium form that would be maintained indefinitely if the snowfall continued? Is there some deep and universal reason for the semicircular form, or is it just an accident, a matter of contingency, something peculiar to this snowfall but nothing to generalize about. Semicircular distributions are not all that common in nature. They turn up in the distribution of eigenvalues of certain random matrices, but that seems a pretty far-fetched explanation for the lumps of snow on my back porch.

I would expect the profile to vary somewhat with the properties of the snow—moisture content, size and form of the flakes, etc.—but I’m not at all sure just how it would vary. In the past 20 years there’s been lots written about the self-organized shape of sand piles, which are essentially conical in profile. Clearly, snow is not sand. It’s fluffier and stickier. A flake doesn’t necessarily have to be supported from below. It could adhere to a surface, perhaps with probability given by some function of the cosine of the slope….

That’s as far as I’d gotten when the next storm hit.

Perhaps I should note that my boyish joy at the first snowfall tends to dissipate as the winter wears on. 

Here’s the deal. I’m going to give you a square grid, with some of the cells colored and others possibly left blank. We’ll call this a template. Perhaps the grid will be one of these 3×3 templates:

You have a supply of transparent plastic overlays that match the grid in size and shape and that also bear patterns of black dots:

Note that each of these patterns has exactly three dots, with one dot in each row and each column. The six overlays shown are the only 3×3 grids that have this property.

Your task is to assemble a subset of the overlays and lay them on the template in such a way that dots cover all the colored squares but none of the blank squares. You are welcome to superimpose multiple dots on any colored square, but overall you want to use as few overlays as possible. To make things interesting, I’ll suggest a wager. I’ll pay you $3 for a correct covering of a 3×3 template, but you have to pay me $1 for each overlay you use. Is this a good bet?

Before going further, I should mention that not every conceivable template can be covered under these rules. To take an obvious example, no 3×3 template with fewer than three colored squares can possibly be covered by any combination of the six overlays. But I promise to submit only templates that can be covered by some combination of the given dot patterns; if I err about this, I forfeit the bet.

How does the game play out? If I give you the template marked “1″ above, you can easily win; just choose permutations a and b, which together cover all the colored squares and no others. You pay $2 and get $3. Template 2, with all nine squares colored, looks like it might be the toughest challenge. Clearly, it cannot be covered with fewer than three overlays, since we need a total of nine dots; and it turns out that exactly three overlays are required. Indeed, there are two ways of covering the template with three overlays: a + d + e and b + c + f. Thus this template is a breakeven proposition: You earn $3 and pay $3.

Now we come to template 3, which has eight colored squares and one blank. Surely if you can cover the full nine squares with just three overlays, then you should also be able to cover eight squares—no? I invite you to try it. In fact the only covering that works requires four overlays: b + d + e + f. Thus you shouldn’t take my bet, since I can always give you a template with just one blank, and you’ll have a net loss of $1.

Some background. I’ll return to the gaming table momentarily, but first let me explain what this is all about and where it came from. A few weeks ago, I was writing about “ranges of rankings,” which led me into the topic of permutation matrices. To recapitulate:

• A permutation matrix is a square matrix with a single 1 in each column and each row, and all the rest of the elements 0.
• An ormat is a superposition of permutation matrices, formed by applying the Boolean OR function to corresponding elements of the permutation matrices. For example:
• Not all square matrices with (0,1) entries can be formed by OR-ing permutation matrices, but there’s an efficient algorithm for deciding whether or not a given matrix is an ormat. (I thank some helpful commenters for enlightening me on this point.)
• Given an ormat, the total number of distinct permutation paths that can be threaded through the 1 entries of the matrix is equal to the permanent of the matrix. Calculating the permanent is known to be a hard computational problem.

In a comment, Barry Cipra posed the following query:

The permanent tells us the maximum number of different permutations that can be OR-summed to produce a given ormat, but what is the corresponding minimum number? Also, in how many different ways can the minimum be achieved?

The connection between ormats and my little game is probably apparent by now. The template of colored and blank squares is an ormat; the dotted overlays represent permutation matrices; to maximize your payoff in the game (or to minimize your loss), you need to answer Barry’s first question, finding the minimum number of permutations that can be combined to yield the given ormat.

For 3×3 matrices, we can solve this problem by exhaustive search, calculating the OR-sums of all possible combinations of the six 3×3 permutation matrices taken 1, 2, 3, …, 6 at a time. I did this with pencil and paper on a recent airplane trip. Here is a summary of the results:

Some of the numbers on this card are easy to explain. The six ormats with just three 1 entries are the permutation matrices themselves. There are six of them because there are 3! = 6 permutations of three things. There are no ormats with four 1 entries for a reason that bears thinking about: There can be no permutations that differ from one another in just one element. When you superimpose any of the six overlays shown above, you can wind up with three, five or six dots, but never four.

At the other end of the scale, it’s no surprise that there’s exactly one ormat with nine 1 entries, and that it takes three permutations to produce it. And then there are the nine ormats with eight 1 entries, which each require four permutations to be OR-ed. These are the single-blank patterns like template 3 above.

Based on these results, I began speculating about what I would see in a tabulation of all 4×4 ormats.

There would have to be 4! = 24 patterns with four 1 entries, and just one pattern with all 1s, generated by OR-ing four permutations. And there should be 16 ormats that require five permutations, namely the 16 matrices with a single 0 element. This last prediction seemed a little less self-evident than the others.

Pocket change and Cheerios. My thoughts about the single-zero (or single-blank) case went something like this. To cover 15 squares with sets of four dots each, we need at least four sets, or else we simply won’t have enough dots. So a useful starting point is one of the optimal arrangements that cover all 16 squares without gaps or overlaps. By this time I had grown tired of drawing zillions of dots, and so I started working with sets of coins.

In this arrangement each coin denomination forms a permutation, with no two pennies, nickels, dimes or quarters in the same row or the same column. We have successfully covered all the colored squares, but unfortunately we’ve also covered the blank at the lower right. Thus this pattern of coins is not an acceptable solution, but maybe we can fix it up somehow?

Moving the penny from the blank square to another square in the same column solves one problem but creates another: Now the arrangement of pennies is no longer a permutation. There are two pennies in the third row.

So now we have to shift another penny to restore the one-per-row-and-column property. Inevitably, this leaves a colored square uncovered. The only way we can cover that exposed square is to introduce a fifth permutation. Since I had run out of coin denominations, I chose a popular brand of breakfast toroids. Voila:

There’s nothing special about the particular moves I chose in this sequence. If you try some alternatives, you should be able to persuade yourself that moving the penny that covers the blank to any other square in the fourth column (or in the fourth row) would lead to essentially the same situation. Likewise the game would come out the same if the single blank square were placed anywhere else in the grid. And you could also start with a different set of initial permutations (provided they cover all the squares).

This coin-shuffling exercise demonstrates that we can cover any 4×4 template that has a single blank by combining no more than five permutations, but how do we know that five are actually needed? Maybe there’s some totally different arrangement that would do the job with just four permutations? Well, think about what such an arrangement would look like. It would have to differ at exactly one position from some other layout of permutations that covers the full 16-square grid. But no two permutations can differ at one and only one place. Thus the reason there can be no four-permutation cover of 15 squares is essentially the same as the reason no 4×4 ormat pattern can cover just five squares.

This argument generalizes to k×k matrices: For any integer k, there must be at least k ormat patterns that cannot be covered with fewer than k+1 permutations. But then comes the bigger speculative leap: Perhaps k+1 is an upper bound. Perhaps part of the answer to Barry’s question is that no k×k ormat pattern requires more than k+1 permutations. At one point I even had a “proof” of this conjecture. Then I wrote a program to check it, doing much the same thing I did with the dots on the airplane.

Out of bounds. My program found the expected 16 ormat patterns that require five permutations—and it found many more as well. In all it identified 2,032 4×4 ormats that can’t be composed from fewer than five permutations. And then came a bigger surprise: The program also found 480 patterns that require six permutations. So much for my proposed upper bound.

One of those problematic 480 ormats takes this form:

Looking over this pattern, I thought I understood where my earlier reasoning had gone awry. This matrix is just like the single-zero pattern, but with two zeros! (I do mean for that statement to make sense. Bear with me.) Suppose we start again with a set of four permutations that completely cover the grid, including the two blanks.

Then we can uncover each blank just as we did in the coin-shuffling procedure above, although we have to be careful the two sets of movements don’t interfere with each other. (Not much point in removing the penny from a blank square, then putting the nickel there.) Here is a strategy for clearing both blank squares while maintaining the one-per-column-and-row permutation property:

Inevitably, when we uncover the two blank squares, we also remove coins from two colored squares, which now have to be filled in again. The key point is that no single permutation can repair that damage, because the two open colored squares are in the same row. To cover both of those squares we need two additional permutations.

Other ways of reshuffling the coins avoid putting the two open squares in the same row or column, but they still foil all attempts to complete the covering with just five permutations. Try adding four Cheerios to the diagram below. If you cover both of the open blue squares, then either you also cover one of the blank squares or you wind up with two Cheerios in the same row.

So now it’s clear we need as many as six permutations to cover a 4×4 ormat. Does that suggest that the general upper bound might be k+2 rather than k+1? Or perhaps the appropriate formula is 2k–2? In support of this latter possibility I offer these two ormats, which require 8 and 10 permutations respectively:

Another wager. Having fooled myself several times about the upper bound on minimal ormat coverings, I feel I should build in a little margin for error before I invite you to make a further wager. We already have direct evidence that covering a k×k ormat can take as many as 2k–2 permutations. So I’ll be generous and offer a full $2k for a proper covering, while charging $1 per permutation. If k=3 or k=4, you can definitely make money on this deal. But is it a good bet for larger k? (Hint: I’d be willing to play the game on these terms for real money.)

•     •     •

Update 2010-08-19: No takers for my bet, eh? Too bad; I had already spent my winnings.

Barry Cipra, who raised the question about minimal ormat covers in the first place, sends this illuminating letter:

I’m going to tiptoe a short ways out on a long long limb and conjecture (really just guess) that the “worst case” behavior, in terms of the minimum number of permutations it takes to produce a given ormat, occurs for ormats of the following form, shown here for k=7:

So as not to abuse existing matrix terminology, I’ll call any (square) matrix of this type—i.e., whose entries below the main subdiagonal are all 0—”uppity triangular.” I can (and will!) show that this uppity triangular ormat for k=7 requires (at least) 16 permutations—and the number appears to grow concavely upwards from that, so I, for one, will definitely not take you up on your $2k wager.

The trick, I realized, is to view each ormat as the “shadow” of what I’ll call an “addmat.” If you let P1, P2, …, Pr be k×k permutation matrices, their addmat is simply the ordinary result of addition: S = P1 + P2 + … + Pr, whose entries are positive integers wherever one or more of the constituent permutations has a 1 and otherwise 0. The associated ormat is obtained by changing each of these entries to a 1, while leaving the 0’s alone. In this sense, the ormat’s 1’s are the “shadows” of the addmat’s positive entries.

What’s crucial is that addmats have a lovely little property not shared with their shadows: the row and columns sums of the entries of an addmat all equal the number of permutations that produce them, r.

Come now, let us reason together…. The uppity triangular ormat example above (for k=7) must come from an addmat of the form

where a, b, and all the *’s are positive integers. In particular, each * is at least 1. Since all row and column sums must be equal, the sum a+b must equal the sum of b and all 6 *’s above it. Hence a is at least 6. Likewise a+b must equal the sum of a and all 6 *’s above it, so b is also at least 6. Hence a+b is at least 12, which means the OR-sum that produced the given ormat involves at least 12 permutations.

This clearly generalizes to arbitrary k, which is more than “direct evidence” that covering a k×k ormat can take as many as 2k–2 permutations, it’s rigorous proof! But we can immediately do better, at least on a case-by-case basis. If we try to get by with just 12 permutations for this uppity triangular ormat, we quickly run into trouble. We obviously must have a = b = 6, and it follows that all the *’s above them are 1’s (to make those column sums 12). That is, we have the addmat

where I now wish to call your attention to the entry labeled “@”. To make its row-sum equal 12, we need @ = 10. But that means its column sum (with the 5 *’s above it) is at least 15, which cannot be! So we are forced to try larger values of a and/or b—which is to say, we need more permutation matrices to produce this addmat.

It turns out you can’t satisfy the row and column sum condition until you get to a = b = 8. I won’t take you through all the steps, but just give you a taste with the penultimate possibility, a = 7, b = 8. The best you can hope for in this case is

Note that I put as much of the “weight” in the last two columns as close to the 7 and 8 as possible, so that I could use the smallest possible value (10) as the entry with 5 positive entries above it. This makes the last three rows, and the right three columns all have the same sum, 15, but now we see a problem in the 12’s column: Its sum is at least 16. So once again, we’re screwed. It’s only with the next attempt that we avoid contradiction:

This matrix finally has all its row and column sums equal. Please note, this may or may not be an actual addmat of a set of 16 permutation matrices—I suspect it probably is, but I haven’t bothered to check. All we know is that it satisfies a necessary condition of being an addmat, namely that its row and column sums are all equal. (It’d be nice if that were also a sufficient condition, but something tells me it isn’t.)

This example, which can clearly be played out for larger values of k, suggests that not only are you safe with a $2k wager, but with a $(2k+2) wager and higher I’ve played around with this a bit, and persuaded myself that the number of permutation matrices will go to 2k + a lot—for k=10, if I did things correctly, you need 24 permutations (or possibly more, if the uppity triangular matrix the analysis leads to is not an actual addmat). I am entirely convinced that some additional careful thought can streamline the analysis into a nice, slick proof. I’m just not sure I haven’t already made a mistake, and built an elaborate house of cards….

Does any of this jibe with what you’ve already found to be the case?

It does indeed jibe.

First of all, to answer a small question Barry left open, here is a set of 16 permutations that will successfully cover his 7×7 “uppity triangular” matrix:

{1,2,3,4,5,6,7} {2,1,4,3,6,7,5} {1,3,2,5,4,7,6} {1,3,4,2,6,5,7}
{2,3,1,5,6,4,7} {1,2,3,5,6,7,4} {1,2,4,5,3,6,7} {1,2,4,5,6,3,7}
{1,2,4,5,6,7,3} {1,3,4,5,2,6,7} {1,3,4,5,6,2,7} {1,3,4,5,6,7,2}
{2,3,4,1,5,6,7} {2,3,4,5,1,6,7} {2,3,4,5,6,1,7} {2,3,4,5,6,7,1}

This was found with a simple greedy search.

My own attempts to find an upper bound have focused not on uppity triangular matrices but on matrices I’ve been calling “flags,” like this 7×7 case:

This matrix also requires 16 permutations for a proper covering. To see why, try threading permutations through the columns of the matrix, starting at the left edge and in each column choosing a 1 element (never a 0) from a different row. Because of the block of zeros at the upper left, the first three elements of every permutation must lie in rows 4 through 7. Thus each permutation “uses up” three of the last four rows in the first three columns, and the rest of the permutation can revisit this range of rows only once. It follows that each permutation can touch only one element in the 4×4 block of 1s in the lower right corner of the matrix, and at least 16 permutations are needed to cover all the 1s in the matrix. Showing that 16 are sufficient is not hard.

This kind of analysis works for any odd k, and thus we know that such matrices can require as many as

permutations. (For even k the situation is a little less symmetrical, and I haven’t worked out the exact details.)

These results give us a lower bound on the upper bound on the number of permutations that may be needed to cover a k×k ormat. But we haven’t proved it’s the true upper bound. Are there other ormats that require even more permutations? My guess is no, but keep in mind that almost all my conjectures along these lines have turned out to be wrong.

The snarXiv is a ran­dom high-energy the­ory paper gen­er­a­tor incor­po­rat­ing all the lat­est trends, entropic rea­son­ing, and excit­ing mod­uli spaces. The arXiv is sim­i­lar, but occa­sion­ally less ran­dom.

Inspiring! Soon bit-player, too, will be generated by a context-free grammar, and no one will know the difference.

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.