The Kepler conjecture—the one about stacking cannonballs or oranges—is now the Hales theorem, though with a cruelly lingering asterisk. Thomas C. Hales announced his proof in 1998, and it was published in 2005 and 2006 (links). But the referees were unable to fully verify all the details, including some 5,000 nonlinear optimization problems solved by computer. Hales has continued to work on refinements to the proof, both simplifying the arguments and exploring formal methods of verification. 

Johannes Kepler in 1610, an age of fanciful extravagance in collars and mustaches; from Wikipedia.

Over the years I’ve read parts of Hales’s proof, but I realized the other day that I had never looked at Johannes Kepler’s much earlier contribution to this discussion. It turns out that Kepler’s essay on the subject is a little gem, an amiable work by an affable fellow, showing a lively mind at play. The conjecture appears in The Six-Cornered Snowflake, a pamphlet pub­lished in 1611 and offered as a New Year gift to Johann Matthäus Wacker von Wackenfels, who was then Kepler’s patron. Apparently Wacker was more than a moneybags; he had studied law in Strasbourg and Geneva, took a doctoral degree in Padua, and had literary interests. Kepler’s essay includes a lot of learned banter addressed to Wacker, suggesting the two men may have been genuine friends. Some of the jokes involve bilingual puns—Latin and German.

Kepler’s main subject, as you might well guess from his title, is the hexagonal symmetry of snowflakes. He writes:

There must be some definite cause why, whenever snow begins to fall, its initial formations invariably display the shape of a six-cornered starlet. For if it happens by chance, why do they not fall just as well with five corners or with seven? Why always with six…?

The idea we now know as the Kepler conjecture is introduced in one of several speculative attempts to solve this puzzle. Kepler describes the familiar stack-of-cannonballs geometry for packing spheres and then makes a bold claim about it, phrased not as a conjecture but as a fact that stands on its own, without need of demonstration: “The pack­ing will be the tightest possible, so that in no other arrangement could more pellets be stuffed into the same container.” The only alter­native he considers is the simple cubic lattice. He does not calculate the actual density of either lattice (\(\pi/\sqrt{18}\) vs. \(\pi/6)\). In the woodcut above, Kepler deconstructs a tetrahedral heap of 35 spheres into five horizontal layers; he clearly understood that the packing could be extended throughout an unbounded volume of space.

From the cannonball packing, Kepler passes on to other themes, including the arrangement of seeds in a pomegranate, the hexagonal cells of honeycombs and the symmetries of flowers (often fivefold); this last subject presents an opportunity for a further digression on the golden ratio and the Fibonacci numbers. But when Kepler finally returns to the snowflake, none of these ideas offers much help, and he is left with still more questions:

I will grant that, as flakes fall from above through steamy air, some incrustation on the plumes can occur from the vapor that comes in contact with them. But why at six points? What is the origin of the number six? Who carved the nucleus, before it fell, into six horns of ice? What cause is it that prescribes in that surface, which is now in the very act of condensing, six points in a circle for six prongs to be welded to them?

At this point Kepler comes up with a charming and highly creative idea, which also happens to be utterly preposterous. He proposes that snowflakes have six points because space has three dimensions:

While these starlets are falling, they consist of three feathered diameters, joined crosswise at one point, with their six extremities equally distributed in a sphere; consequently they fall on only three of the feathered prongs, and tower aloft with the remaining three, opposite those on which they fall, on the same diameters prolonged, until those, on which they rested, buckle, and the remainder, until then upright, sag onto the level in the gaps between them.

In other words, a pristine snowflake is not a planar hexagonal shape but a three-dimensional structure rather like a toy jack, with components aligned along three Cartesian coordinate axes. The flake collapses into a flat, six-pointed configuration only when it falls to earth. According to this theory, the number six is not something arbitrary or accidental but a direct consequence of the way the universe is put together.

Kepler did not have the vocabulary of Cartesian coordinate systems to describe his idea—Descartes would not invent it until 20 years later, incidentally after reading The Six-Cornered Snowflake—and so Kepler had to adopt a more roundabout description:

But is this perhaps the cause of the three diameters, that there is the same number of dimensions in animals? After all they have upper and lower parts, front and back, left and right.

Almost half of Kepler’s essay is given to the defense of this three-dimensional hypothesis, and then, at the end, all of his speculation is spoiled by a conflict with cold, wet reality:

For as I write it has again begun to snow, and more thickly than a moment ago. I have been busily examining the little flakes. Well, they have been falling, all of them, in radial pattern, but of two kinds: some very small with prongs inserted all the way round… But scattered among them were the rarer six-cornered starlets of the second kind, and not one of them was anything but flat, whether it was floating or coming to earth, with the plumes in the same plane as their stem.

In the end Kepler abandons his inquiry without reaching any conclusion. He throws the problem out for the chemists and physicists to solve—which they did, three centuries later.

Scientific discourse has changed a great deal in the past 400 years. When Hales wrote up his proof of the Kepler conjecture, he did not include jocular asides to his program officer at the National Science Foundation. And we don’t see a lot of published papers these days that end with the admission, “I have not yet got to the bottom of this.” The negative capability that Kepler embraces is part of what makes his essay so appealing.

I read the Kepler essay in an edition published in 1966, which prints the Latin text and an English translation on facing pages:

Kepler, Johannes. 1966. The Six-Cornered Snowflake. Edited and translated from the Latin by Colin Hardie, with essays by L. L. Whyte and B. F. J. Mason. Oxford, U.K.: Oxford University Press.

There’s also a more recent edition, which I have not seen, from a small publishing house in Philadelphia:

Kepler, Johannes. 2010. The Six-Cornered Snowflake. Translation by Jacques Bromberg, with essays by Owen Gingerich and Guillermo Bleichmar. Philadelphia, Penna.: Paul Dry Books.

Forty years ago I had my first close encounter with mathematical models of doomsday. The Limits to Growth, published in the spring of 1972, offered a grim vision of environmental and economic collapse, based on the implacable logic of a computer simulation called World3. For extra nerd-cred authenticity, the results of the simulation were set forth in crude black-and-white graphs reproduced directly from line-printer output.

I wrote about The Limits to Growth and World3 back in 1993. Now I have revisited the subject in my newly published American Scientist column. Buried deep within the new column is a note mentioning that I’ve been working to re-implement the World3 model in JavaScript. “The result of this exercise is at http://bit-player.org/limits,” the column says.

If you follow that link, you’ll find it’s true: There’s a rudimentary version of the model you can play with (if you have the right browser).

But I have to tell you, it was a near thing. When the magazine was shipped to the printers three weeks ago, the program was unfinished. Two weeks ago, it was finally running but giving weird results. A week ago the output was still nonsense. Since then I’ve had more anxious moments, late nights, and occasions to ponder the foolishness of publicly announcing vaporware. For a while it looked like I might have to admit defeat and write a sheepish apology for promising something I couldn’t deliver. Never again, I said to myself. And yet, when it’s all over, I get such a kick out of building a thing like this.

Herewith a few notes, mostly technical, on the building process.

What the model models. For background on World3—where the project came from, who did it, and whether you should worry about the model’s bleak predictions—please see either of my columns. Very briefly, the model traces interactions among five main components of the global ecosystem and economy: the human population, agriculture, industry, nonrenewable resources and pollution. If you could strip the model down to its mathematical essentials, it would be a system of coupled differential equations, something like the Lotka-Volterra equations for predator-prey populations. But the model is actually formulated in the language of “system dynamics,” a simulation methodology invented in the 1950s by Jay W. Forrester of MIT, with heavy influence from control theory and servomechanisms.

The key elements of a system dynamics model are represented by levels and rates, or less formally vats and valves. Here’s the population section of the World3 model:

The orange rectangles are levels, which integrate the inflow and outflow of people. The rates of flow are determined by the valves, represented here as hourglass-shaped icons (a graphic device borrowed from control theory and industrial engineering).

Twiddling the knobs. If you go and play with the model, most of the controls should be pretty obvious. The original World3 model extended over 200 years, from 1900 to 2100; the model duration slider can extend the horizon out to 2400. The time step slider controls the integration interval (the variable dt within the model); if you set it to a value greater than 1 year, you’re likely to see spurious short-period oscillations caused by undersampling. The initial resources multiplier affords control over a variable that turns out to be crucial in determining the fate of World3. Note that the resources curve in the graph shows the fraction of resources remaining, so it always begins at the same initial value; the slider setting effectively determines the rate of depletion. The final slider, output consumed, provides access to another variable that can greatly alter the outcome of the simulation. This quantity is the fraction of industrial output that is diverted into consumption, defined as anything nonproductive; the output not consumed is reinvested in agriculture, industry and the extraction of natural resources. High consumption acts as a damping or friction term, curtailing the positive feedbacks that lead to much of the future unpleasantness in the model. As I snidely commented in 1993: “The model seems to be telling us to invest less in farms and factories and to spend more on frippery and fast cars. Armaments also fall into the category of nonproductive spending, so perhaps we need a good vigorous war every few decades.”

A few snapshots of model behavior. My purpose in writing this program was not really to explore the behavior of the World3 model; for that there are several more versatile and more trustworthy implementations out there (including at least one that runs within a web page). I just wanted to understand what’s inside the box. Nevertheless, now that the model is running, I may as well point out a few of its tricks.

Here’s the spurious oscillation mentioned above, with dt = 2:

A quite different kind of oscillation appears when the initial stock of natural resources is set to a very high value (32×):

These oscillations, with complex waveforms and a period of roughly 150 years, are not caused by integration error but probably represent a natural behavioral mode of the model itself (analogous to the population cycles seen in predator-prey models).

We get a much calmer vision of the future by setting the consumption fraction to 0.51, rather than the World3 default of 0.43:

Siphoning off some of the capital that would otherwise fuel rapid growth tames the overshoot-and-collapse regime of the standard run. However, the outcome is hardly utopian. Life expectancy and food per capita remain permanently low; so does industrial output, which can be taken as a proxy for wealth.

Putting World3 in a web browser. The original World3 model ran on mainframe hardware—IBM 360 and 370 machines. Now it fits into a web browser on a laptop or an iPad. I try to keep my sang froid about such things, but the fact is I’m just plain astounded by the march of progress.

I should emphasize that the entire JavaScript computation is happening on your computer, not my server. The program is downloaded once and then executed locally each time you press the Run button. And it’s not even much of a computational burden. The gradual unfolding of the graphs across the years is a deliberate animation effect, not a reflection of actual computation speed. (The Run Fast button is meant to eliminate artificial delays, but it doesn’t quite achieve that yet.)

DYNAMO and toposorting. The 1972 version of World3 was written in a language called DYNAMO, created a decade earlier by Phyllis Fox and Alexander Pugh, who were then part of Forrester’s group at MIT. In lexical and syntactic structure DYNAMO is what you’d expect of a language from the punch-card era—six-letter variable names and ALL CAPS—but in other respects it’s an interesting early experiment, with a programming style that falls somewhere between procedural and declarative.

One feature is particularly noteworthy. In DYNAMO a model is defined by a set of “equations” (really assignment statements) that can be written down in any order but have to be executed in a sequence that takes into account the way one equation depends on others, so that every variable is evaluated before it is used. The DYNAMO compiler reordered the equations automatically. This was an early application of topological sorting; the first efficient algorithms for this process were developed circa 1960, in connection with PERT project-scheduling methods.

Topological sorting takes a directed graph and reduces it to a linear list of nodes satisfying the following constraint: If the graph includes a directed edge u → v, then u appears before v in the list. This ordering is possible only if the graph is acyclic, with no loops of directed edges. As it happens, the network of equations for the World3 model is not acyclic. Here’s one section of the network that violates the no-loops rule:

If you try to assign a value to Labor Utilization Fraction (near the upper left), you’ll see that you first have to know the value of Jobs; before you can evaluate Jobs, you need to know Potential Jobs in Service Sector; etc. Continuing to trace through the red arrows reveals that before you can calculate Labor Utilization Fraction, you need to know Labor Utilization Fraction. Uh oh. The model can be made computable only by artificially interrupting such loops. In this instance the break is made by assigning an arbitrary initial value to the variable Labor Utilization Fraction Delayed.

From DYNAMO to JavaScript. In a 1989 memoir, Forrester tells this story about the origins of system dynamics:

An expert computer programmer, Richard Bennett, worked for me when I was writing the 1958 article, “Industrial Dynamics—A Major Breakthrough for Decision Makers,” for the Harvard Business Review…. For that article I needed computer simulations and asked Bennett just to code up the equations so we could run them on our computer. However, Dick Bennett was a very independent type. He said he would not code the program for that set of equations but would make a compiler that would automatically create the computer code.

Bennett’s policy in this matter was sensible and wise; I foolishly ignored it. I didn’t want a general-purpose compiler for system-dynamics models; I just wanted to implement this particular model. So I didn’t bother to structure the code in a way that would separate the model equations from the algorithms that process those equations. Big mistake.

My original plan was to write a prototype version in Lisp (my native tongue) and then redo it in JavaScript for wider distribution. I abandoned that idea when I ran short of time—another mistake. I was ignoring a Brooksism: Plan to throw one away; you will anyhow. The program now running is the one I need to throw away. The code is a mess. Please avert your eyes.

I don’t blame JavaScript for this situation. This is the third Javascript project I’ve taken on in the past few months, and I’m finding the whole ecosystem—JavaScript itself plus HTML5 and CSS3, along with the developer tools built into Google Chrome—quite a pleasant place to work and play.

My basic strategy was to make a line-for-line translation of DYNAMO statements into JavaScript. A typical DYNAMO equation looks like this:

SC.K = SC.J + (DT)(SCIR.JK - SCDR.JK).

SC is service capital, a level (or vat) variable; SCIR and SCDR are rate (or valve) variables representing the service capital investment rate and the service capital depreciation rate; DT is the numerical integration period; juxtaposed parentheses indicate multiplication. And what about the appended letters J, K and JK? They are “timescripts”: J designates the previous moment, K the current moment and JK the interval between J and K. All this notation carries over into JavaScript with remarkably little fuss. If we represent a variable such as SC as a JavaScript object, the timescript notation is unchanged, with SC.J and SC.K denoting properties of the object SC.

Apart from transcribing the equations, it’s also necessary to provide half a dozen special operations such as smoothing, delaying and clipping signals. And there is a kludgy “table” facility for piecewise linear approximations of arbitrary functions.

Canvas vs. SVG. My last JavaScript project used Scalable Vector Graphics, so for this one I decided to try the main alternative, the HTML “canvas” element. Drawing on the canvas is very fast, but that’s about the only nice thing I can find to say about it. The canvas is simply a rectangular array of pixels, and drawn objects have no structure apart from the pixels that compose them. The curves making up a World3 graph cannot be moved or rescaled or otherwise altered without redrawing the entire graph. The animation effect, in which all the curves seem to gradually elongate, is an illusion: At each time step the entire curve is redrawn from the beginning. Thus drawing a curve of 400 segments actually calls for 80,200 operations.

SVG offers friendlier facilities. Not only can you draw objects piece by piece, but the objects retain their identity as objects; they become part of the DOM, the document object model. You can address them individually, change their colors and other properties, transform their geometry. It would be easy, for example, to highlight and label a curve on mouseover.

Firefox is the new Internet Explorer. (But so is the new Internet Explorer.) Making stuff for the web has become a lot more fun in the past year or two, thanks in large measure to the WHATWG process. There’s an accelerated pace of change in the standards community, and browser makers have been quickly implementing the latest proposals. For this project I needed not only the canvas element but also the “range” input element, which is supposed to create a slider-type control widget. In the Chrome, Safari and Opera browsers both of these components worked out of the box. Missing from that list of compatible browsers is Internet Explorer—the perennial Think Different browser. Also missing is Firefox, which is a little more surprising. It turns out that sliders have been on the agenda of the Firefox development crew for six years, but they remain unimplemented.

With mixed feelings, I installed a polyfill that allows the slider code to run in Firefox. (Thanks Frank Yan!) My feelings are mixed because this sort of spackling does nothing to encourage the Firefox developers to address the problem.

The big bug. Getting the program to the point where it would run at all was a tedious chore (150 equations to be retyped from a marginally legible printout), but was otherwise unremarkable. After I fixed a few typos and misplaced semicolons, the code compiled and ran without throwing error messages. Then the real challenge began. The output looked nothing like the graphs published in The Limits to Growth. My World3 was a much nicer place, with gradual population growth and a slow but steady gain in industrial output and food production. Try as I might, I could not get the world system to collapse in ruins the way it’s supposed to.

This went on for more than a week.

Yes, I did consider the possibility that my program was correct and the dozens of other implementations over the past 40 years were all wrong. But I’m not quite that much of an egomaniac.

What was the bug that caused me so much grief? JavaScript experts will see the error immediately. In one of those initialization routines needed to break a cycle in the graph of dependencies, I had written something like this:

if (typeof(v) == Number) { return v }.

The problem is that (typeof(v) == Number) will return false no matter what the type of v happens to be. If v is not a number, the predicate is obviously false. If v is a number, the result of typeof(v) is not Number but "number". As a Lisp guy, I just can’t get used to JavaScript’s stringiness. (I could have said (v.constructor == Number), but I didn’t.)

Glitches. Given this evidence of my slapdash coding and testing practices, it’s fair to ask how many bugs infest the rest of the program and whether any of the results should be trusted.

An obvious validation strategy is to set all parameters to default values and then compare the output of the program with that of the original 1972 model. That’s not so easy. The graphs published in The Limits to Growth have no numerical scales (apart from markers for the endpoints of the time axis). Hence all I can do is check that the peaks and valleys have the right phase relationships. My eyeball says most of them match reasonably well, but this methodology does not inspire great confidence.

Some smaller-scale features of the curves also demand attention.

One conspicuous oddity is not a bug—or at least not my bug. Take a look at this detail of a graph of population (orange), birth rate (yellow), death rate (purple) and life expectancy (gray):

It looks like something really strange happened in 1940. And in World3 something did: There’s an abrupt switch between two table functions, changing the effect of health services on lifespan. The death rate plunges; there’s a brief blip in the birth rate; life expectancy ratchets upward and then keeps growing steadily. The abruptness of the transition looks highly unrealistic, but this is not the result of a programming error. It’s part of the model specification.

On the other hand, the little blips in the birth and death curves at the very start of the simulation are not part of the model specification. I think I understand where they come from: It’s an initialization problem. The initial birth and death rates are not in equilibrium with other elements of the model, and it takes several iterations to eliminate the imbalances. As far as I can tell, however, these glitches do not appear in the 1972 output, so I must have misunderstood something about the model structure or the initialization procedure. I’m still looking into it.

It’s in the nature of writing software—or writing English prose, for that matter—that as soon as you finish a project, you see all the mistakes and missed opportunities with great clarity, and you feel that if you could just start over and do it all again, you’d finally get it right. I’m feeling that impulse right now, and I may act on it. But in light of my recent experience, I’m not making any promises.

You are guiding your cart down the aisles of the supermarket when the price tag on the Cheerios beckons to you. Literally. An animated figure on the shelf tag waves and signals for you to come closer. When the array of cameras embedded in the shelf gets a better look at you, the tag offers you a deal, lowering the posted price. Enjoy your breakfast.

This fantasy of “dynamic pricing” is not a product of my own fevered imagination. I heard about it the other day at the March meeting of the American Physical Society, in a session on reflective color displays. Animated and interactive price tags were suggested as a motivating application for this technology. According to a speaker from Hewlett-Packard, the other components of the personalized pricing system (the cameras, the image-processing software, the communications network) are already available or soon will be; the main constraint is the display, which needs to provide reasonable image quality (comparable to newspapers) at low cost and low power. HP is at work on meeting this need (and so are several other companies and research groups). For some details of the Hewlett-Packard work, see this technical report.

I yield to no one in my technophilic ardor, but I have to say that the prospect of animated, haggling grocery-store price tags does not fill me with yearning for the future. And I suspect the idea might meet with a certain amount of legal and social resistance. (What are the acceptable criteria for adjusting prices offered to a given customer? Age? Gender? Race?)

But if the underlying display technology succeeds—and the demos already look pretty impressive—it’s not just price tags that I worry about. We could find ourselves up to our eyeballs in pixels. The aim is to manufacture the display material by a high-volume, roll-to-roll process. If they can get the cost down to $100 per square meter, a supermarket shelf tag might cost a dime or a quarter, a bumper sticker would be a dollar or two, an advertising card in the subway might be worth $10, and a billboard by the highway $20,000. Wrapping an entire Wal-Mart in digital ads could be done for roughly $1 million. Each of these surfaces would present a moving, video-like image—a window onto another world, covering up some fraction of this one.

Opelousas, La., 14 January 2001

Perhaps the most important security concept within modern browsers is the idea of the same-origin policy. The principal intent for this mechanism is to make it possible for largely unrestrained scripting and other interactions between pages served as a part of the same site (understood as having a particular DNS host name, or part thereof), whilst almost completely preventing any interference between unrelated sites.

That’s Michal Zalewski of Google, in his Browser Security Handbook (now also available in expanded form as a book, The Tangled Web). I had thought I understood the same-origin policy, both how it works and what it’s for. Turns out I was totally wrong about the how-it-works part—about how the policy is enforced by the browser. Now that I’ve been straightened out on that point, I’m more confused than ever about the purpose of the policy.

This uncomfortable episode in my education began with my post about knowls, the little drawers full of knowledge that I look upon as a step toward footnotes on the web. In that article I pointed out a problem with the concept of a “knowlpedia,” a public repository of knowls: the same-origin policy won’t allow a web page loaded from one server to incorporate HTML content from another server. Thus when you are reading a web page hosted at bit-player.org, code within that page can freely access knowls that are also stored at bit-player.org, but it cannot retrieve knowls from aimath.org.

Harald Schilly, the author of the knowl code, wrote back that he had a one-line fix for the same-origin problem. The one line is “Access-Control-Allow-Origin: *”; it’s an HTTP header to be returned by the server of the “foreign” content. I was skeptical of this solution. In fact, I was absolutely certain it could not work. Let me explain why.

If a web browser is going to prevent illicit cross-site communication, how can it do so? Easy! Your browser knows the origin of the page you’re looking at right now: It came from http://bit-player.org:80 (where “http” designates the Hypertext Transport Protocol, “bit-player.org” is the host name, and “80″ is the port number). If code within this page tries to access foreign HTML—say by requesting a knowl at http://aimath.org:80—the browser detects the mismatched host names and refuses to allow the request. I had always assumed that in a case like this the requesting packets are never sent from your computer to the foreign server. That’s why I was so sure that no amount of fiddling with server configurations could have any effect on the same-origin policy, because the request would be blocked long before it reached the server.

This was my mental model of same-origin enforcement, and it still strikes me as the most efficient, sensible and even obvious solution. However, the model is totally wrong. Browsers do not block a request that violates the cross-origin rules. The browser merrily sends the request to the foreign server, awaits the response, and then dumps the content of the response without inserting it into the displayed document or otherwise showing it to the user. This behavior seems so pointless and wasteful, and possibly risky, that I had to confirm for myself that it really happens. It’s not hard to do so. The debugging tools built into modern browsers will show you the headers of each request and response. Here’s what Firefox reports when I try to get a knowl from aimath.org:

Request headers:
Accept:text/html, */*; q=0.01
Accept-Encoding:gzip, deflate
Accept-Language:en-us,en;q=0.5
Connection:keep-alive
DNT:1
Host:aimath.org
Origin:http://bit-player.org
Referer:http://bit-player.org/2012/the-knowl-post
User-Agent:Mozilla/5.0 (Macintosh; Intel Mac
     OS X 10.7; rv:10.0.2)
     Gecko/20100101 Firefox/10.0.2

Response headers:
Accept-Ranges:bytes
Connection:close
Content-Length:489
Content-Type:text/html
Date:Sat, 03 Mar 2012 16:34:53 GMT
Server:Apache/2.0.64 (Red Hat)

Note that the response headers indicate a content length of 489 bytes. None of that content is actually loaded into the page or displayed to the reader, but the server is sending it. I confirmed this with a packet sniffer (Wireshark) that intercepts data moving over the network connection. The full content of the requested knowl is sent back to the browser, but then it’s deep-sixed before anybody sees it.

What I don’t get is why browsers implement the same-origin policy in this roundabout way. What’s the point of sending the request if you know you’re going to ignore the response? I suppose web-site redirection is one scenario where sending the message might not be futile: If aimath.org redirects the request back to bit-player.org, then the transaction can be allowed to proceed. But how common is that?

Very likely there’s some other good reason for doing it this way. (Having been persuaded that my first hypothesis was totally bogus, I’m willing to entertain the possibility that I still don’t understand clearly.) But none of the tutorials and reference documents I’ve consulted (see list below) have explained it to me.

The “Access-Control-Allow-Origin: *” header that Schilly mentioned is part of a recent W3C draft standard called Cross-Origin Resource Sharing, or CORS, that lifts some of the strictures imposed by the same-origin policy. For simple requests, the browser will accept and display results from a foreign site if the appropriate header is included in the response. Thus the third-party site is given a measure of control over whether or not cross-origin requests are allowed. The CORS proposal goes back to 2005, but browsers began supporting it only in 2009 or 2010. (Opera hasn’t caught up yet; Internet Explorer does it a little differently.)

I don’t pretend to understand all the implications of this change in the way the web works. Presumably, the scenario the designers have in mind is something like this:

Naive User visits sneakthief.com, a web site that plays amusing videos of kittens while running a JavaScript program that requests cross-origin access to fortknox.com, sending along the cookies that authenticate Naive User as an acount holder at Fort Knox. If fortknox.com responds with the keys to the vault, they will be transmitted back to sneakthief.com. The protection against this outcome is our faith that fortknox.com will not carelessly set the Access-Control-Allow-Origin header. I would have felt a little safer if the response from fortknox.com were blocked unconditionally, regardless of header flags. And safer still if the web worked my way, and the request were blocked before it could even be sent.

Zalewski comments that the main rationale for introducing CORS is that there are so many other ways of undermining or circumventing the same-origin policy (iframes, server-side proxies, JSONP, hidden forms, Flash, Java) that we might as well build a well-structured and well-documented facility for doing what everybody is doing anyway. In other words, leave the doors unlocked so nobody will smash a window while breaking in.

This may well be the wisest policy. Zalewski offers this meditation in the epilogue to his book:

I am haunted by the uncomfortable observation that in real life, modern societies are built on remarkably shaky ground. Every day, each of us depends on the sanity, moral standards, and restraint of thousands of random strangers—from cab drivers, to food vendors, to elevator repair techs…. In this sense, our world is little more than an incredibly elaborate honor system that most of us voluntarily agree to participate in. And that’s probably okay….

It’s difficult to understand, then, why we treat our online existence in such a dramatically different way…. The only explanation I can see is that humankind has had thousands of years to work out the rules of social engagement in the physical realm…. Unfortunately for us, we have difficulty transposing these rules to the online ecosystem, and this world is so young, it hasn’t had the chance to develop it’s own, separate code of conduct yet.

Other resources on this topic:

• Michal Zalewski’s Browser Security Handbook, part 2
• W3C on same-origin policy
• Wikipedia on same-origin policy
• Wikipedia on cross-origin resource sharing
• W3C on cross-origin resource sharing
• a manifesto promoting cross-origin resource sharing
• Tiffany Brown essay on cross-origin resource sharing

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I’ve been Way Out West for the past few days, exploring a desert landscape where everything bristles. Ros and I went walking in the foothills of the Santa Catalina range, north of Tucson. At one point along the trail we spotted a pair of tweezers someone had left behind near the base of a prickly pear. Those lost tweezers told their own story—a painful one. We hadn’t thought to pack such implements; later, a more experienced hiker told us that what you really want to take along are not tweezers but pliers.

The iconic cactuses of southern Arizona are the towering saguaros. They are magnificent plants, but I also find them a little clownish, with their limbs attached like sausages or knotted balloons.

On our stroll through the desert I was taking particular note of the saguaros’ rib patterns. As we later learned, the ribs work like accordion pleats, allowing the plant to expand its girth when it absorbs water after a rainfall. The ribs and their intervening grooves form vertical stripes, most of which extend the full length of the main trunk or an arm. Every now and then, however, an extra rib appears out of nowhere, like this:

What sort of developmental algorithm can generate a pattern like this? It looks like a textbook example of a mechanism discussed almost 60 years ago by none other than Alan Turing. Imagine clusters of specialized plant cells that secrete some chemical substance—a morphogen—that induces other cells to form a spine-crested ridge. Surrounding the growing tip of the plant is a necklace of such morphogen-secreting clusters, creating long parallel ridges as the trunk elongates, much like cake frosting extruded from a fluted nozzle. This is a self-organizing and self-maintaining process. The morphogen clusters (and the ridges) remain evenly spaced because each secreting group of cells inhibits all nearby cells from secreting the substance. Thus the morphogen sites act as if they have coiled springs keeping them equidistant. As the cactus grows taller, however, it also increases in circumference, spreading the clusters apart. When two adjacent morphogen sites are too distant to suppress activity between them—or in other words when the coiled spring no longer exerts a repulsive force—a new morphogen cluster can form spontaneously in the gap. The result is a new rib arising midway between two existing ribs.

After examining a few dozen saguaros we passed along the trail, I thought I understood the biology of the rib patterns. New ribs arise like mountains out of a valley floor, and so the valley itself must bifurcate, passing to the left and right of the new ridge. The fork where the valley splits always has its tines pointing upward. Thus when you trace along the epidermis of the cactus from ground level to the top of the plant, new ridges appear spontaneously from time to time, but existing ridges never disappear.

Those hypotheses lasted a kilometer or two. Then we came upon the cactus in the photograph below:

This saguaro has both bifurcating valleys and bifurcating ridges (along with a couple of doubtful cases where it’s not entirely clear whether the ridge or the valley is doing the splitting). The idea of morphogen centers separating and allowing a new cluster of cells to form between them cannot explain everything we’re seeing here; it appears that morphogen clusters are undergoing their own fission events as well. It’s not just the valleys that bifurcate but the ridges too.

A hundred meters farther along the trail, we found another exceptional cactus:

Here we have both forks and antiforks: As we proceed upward along the body of the cactus, ridges are both created and annihilated. Near the top of the image is a confused ring that includes several initiation and termination sites. Perhaps there was some disruptive event at that moment in the history of the plant’s growth. (Saguaros live for 150 or 200 years, so there’s plenty of history to play out.)

Bifurcating ridges can be explained in the same general way as bifurcating valleys, and so I suspect the saguaros are still good candidates for a model based on Turing’s ideas. But maybe the model is not quite as simple as I first thought. And the explanatory challenges get harder still. Elsewhere in the Tucson area, a fellow hiker drew my attention to this cactus:

Or how about the unfortunate specimen pictured below?

As the detail at left reveals, this one has a fork with its tines pointing neither upward nor downward. How the vandals managed to impale the cactus at such an elevation—the dinner fork is four or five meters off the ground—remains an unanswered question. But in the end it’s also not the most interesting question about these curious plants, which wear their algorithmic structure on their skin.

It’s the custom among mathematicians that when you reach age 60, you’re put on an ice floe with a day’s supply of walrus meat and set adrift.

But I’m not a mathematician.

Computer scientists get a few years’ grace. Because they count in binary, for them the dreaded end of productive intellectual life is put off until age 2⁶.

I’m not a computer scientist either. I’m a writer. This is no dispensation, however; the literary world also worships precocity. Byron said it: “Is there anything in the future that can possibly console us for not being always twenty-five?” I took an even harder line in my own youth. At age 16, when I ran away from home to write a novel, I vowed that I would be a famous author by 22 or find an ice floe and make an end of it.

And today I am 60–1, and I find I am not yet quite ready to be set out to sea. I look back to the poets who seemed so intensely young when I was young, and I find they have aged well. Here’s George Herbert:

I’m afraid. I’m afraid, Dave. Dave, my mind is going. I can feel it. I can feel it. My mind is going. There is no question about it. I can feel it. I can feel it. I can feel it. I’m a… fraid.

I’m about to dig into the innards of the software that runs this blog (updating WordPress from 1.5 to 2.6, installing some plugins, fiddling with CSS and PHP). So, just in case I can’t get the pod doors open when I’m done, I want to say it’s been fun, and thanks for tuning in.

Update: It seems I’m still here. Much remains to be done, but I’m hoping the site will remain functional while under reconstruction. Comments and complaints are welcome.

Update 26 October 2008: It’s like gardening, or dentistry, or cleaning out the attic: Once you start mucking about, you notice more and more that needs attention, and there’s no end to it. It’s clear now that I’m going to be fussing with the presentation of this site for weeks to come. Expect something different every time you visit. Those who read via RSS will probably be seeing the same posts flagged as ‘new’ over and over again. Sorry about that. (Does anyone know a way to avoid it, other than shutting down the feed altogether?)

Anyway, don’t be shy about letting me know what doesn’t work or what looks awful. One of the main motives for this housecleaning was to provide a less-lousy interface for leaving comments. I’ve already experimented with three approaches to that problem, and I’m not terribly happy with any of them. I’m likely to change again. If you’d like to test the system, this post would be a good place to leave witty remarks such as “Hello, world!” and “Testing, one, two, three.”

Here’s a specific question: All of the schemes for providing a preview of comment formatting rely on Javascript. I read RSS feeds with a program that doesn’t do Javascript (NetNewsWire 2.0). How about others? Will a Javascript solution actually solve anything?

Tardy announcement: I’ll be giving a talk tomorrow at Harvard. Details. If you’re in the neighborhood, please look in.

Update: Harvard has posted video of the talk; please have a look, if you’re interested, and you’re equipped to play RealMedia files. I’m not equipped, so I haven’t seen it myself. But I’m sure it’s wonderful (thanks to the AV expertise of Bill Countie and Geoff Maness).

Slides are here (PDF), though they won’t make much sense without the narration.