For a few hours yesterday the front page of the New York Times was stealing right clicks. If I right-clicked on a hyperlinked headline (or option-clicked, or made a two-fingered tap on the trackpad), I did not get the usual context menu; instead, I was taken directly to the target of the link. This is the proper behavior for an ordinary mouse click—or a left click with a two-button mouse—but not for a right click.

The first time this happened, I thought it was just a slip-of-the-finger, but the error was consistently repeatable across two different machines and three different browsers (Firefox, Chrome, Safari). Furthermore, it affected only the New York Times. Indeed, it was only the front page of the Times that was misbehaving; right clicks elsewhere in the paper worked normally.

The cause of this problem may have been an innocent goof, but I’m skeptical. When the Times first put up a paywall, not quite a year ago, readers quickly found holes in it. One of those holes involves right-clicking a link to get a copy of the URL, pasting it in the browser address bar, and removing the referrer cruft following the question mark. My guess is that someone at the Times decided it was time to close the hole.

I hasten to add that freeloading is not my reason for right-clicking on Times headlines. I pay my $15 per doublefortnight. But my newsreading habit is to peruse the entire front page, opening each article that interests me in a separate tab. The “open in new tab” command lives in the right-click contextual menu.

Regardless of why the Times was interfering with my Second Amendment right to bear mouse buttons, I was curious about how they were doing it. They weren’t just disabling the contextual menu entirely. (You can read a scornful account of that nefarious practice at About.com, which identifies itself as “A part of The New York Times Company.” (Not, in my view, the best part.)) On the NYT front page, right clicks worked as usual in ordinary text; they were only hijacking right clicks on links.

Regrettably, I’m not going to be able to answer the how’d-they-do-it question. Before I could find the offending code, some grownup at the Times called off the whole crazy experiment, and normal right-clickery was restored.

Although I couldn’t find the click-stealer, I found plenty else. The Times, it seems, prints all the JavaScript that fits. Some of it is unsurprising. jQuery is loaded. There are scripts to run slide shows and videos, to manage cookies, to serve ads, to provide menus and other navigation aids. But there’s lots more:

• beacon.js This may have something to do with all those little files named 1px.gif floating around like packing peanuts.
• revenuescience.js Apparently a product of an outfit called Audience Science. “AudienceScience is processing trillions of behaviors per day and over 270 billion attributes at any given moment.” You don’t say.
• krux-4.7.2.js The web site of Krux (which I had never heard of before) says: “Krux helps large and small websites control, energize, and responsibly monetize consumer data across screens and sources.” Reading further, I get the impression they are in the business of preventing snoopers from snooping on the snoopers who snoop on us. I’m certainly not having much luck snooping on their code. It looks like this:

  function(a){e(a)||A(b,c(a))}),h(b,c(a[1]),e(f)?f:function({o.js.apply(null,j)})):h(b,c(a[1]));

• gw.js Even deeper obfuscation. I believe this is a JavaScript program whose function is to write another JavaScript program into the page header. It seems to be one of the tools that Audience Science uses to process those trillions of “behaviors” per day.

Phooey on them, I say.

Yes, that’s one of those annoying QR codes that seem to be turning up all over the place lately. The jumble of red and blue pixels appears on the front of the holiday greeting cards that my wife Rosalind and I sent to a few friends and family-members last week. Since the card has an online component, I thought I might share it here with a wider circle of acquaintances. So let me take this opportunity to wish everyone a happy 2012—all 366 days of it.

If you have a QR reader on your cell phone, you should be able to scan the code directly from the screen. You’ll be taken to a web page where the same pattern appears, and tapping the red targets should eventually get you to a greeting-of-the-season. Unfortunately, the Javascript driving this transformation doesn’t seem to run very well on some phones. (I’ve tested it on iPhones, iPads and a Palm Pre, where it is balky but functional; I’ve had at a report that it fails entirely on at least one Android phone.) If anyone can offer hints or clues about what I might be doing wrong, I’ll be grateful.

In any case, the small-screen version of the program isn’t nearly as nice as the one for grown-up computers, which you can reach by clicking here or on the image above. And there’s more about my travails with cell-phone Javascript (and SVG) in the nerd notes.

Four hundred years ago, the idea that the Earth goes around the Sun rather than vice versa was not just a scientific breakthrough but also a cultural bombshell. People were asked to reimagine the world they were living in. Not everyone welcomed the opportunity. Books were burned. In the case of Giordano Bruno, an author was burned.

In the modern world, cosmological revolutions seem to cause hardly a ripple in public consciousness. Inflation, dark matter, dark energy—these ideas also call for a reimagining of the world we live in, but they have provoked very little fuss outside the community of science. It’s certainly a relief that no one will be burned at the stake over matters of cosmological doctrine. But are we really more liberal and open-minded, or just not paying attention?

Those are the final paragraphs of my new column in American Scientist. Here I want to say a few words more about the reception of these new ideas in cosmology, but first I should explain that the column is really about something else, namely the Bolshoi computer simulation of the large-scale structure of the universe, led by Joel Primack of UC Santa Cruz and Anatoly Klypin of New Mexico State University.

While preparing to write the column, I picked up Marcia Bartusiak’s recent book The Day We Found the Universe, which tells the story of the discovery that the “nebulae” we see in the sky are actually distant galaxies much like our own—what Kant called “island universes.” It’s a grand story, and Bartusiak gives a splendid account of it, with engaging portraits of the dozen or so principal players. Highly recommended.

I’m not going to retell the whole story here, but I want to point out that it took 175 years for the idea of island universes to be accepted by astronomers. The earliest known proposal was by Thomas Wright in 1750; Bartusiak’s story culminates on January 1, 1925, when Edwin Hubble’s paper “Cepheids in Spiral Nubulae” was read to a joint session of the American Astronomical Society and the American Association for the Advancement of Science. In between, there was a great deal of backing and forthing. For example, William Herschel, the preeminent observational astronomer of the 18th century, initially supported the island-universe theory, but later he changed his mind. As late as 1900 many astronomers believed the nebulae were relatively small, nearby objects—perhaps protostars about to condense. It took new instruments and a barrelfull of observational evidence to overturn this view. (Specifically: telescopes that could resolve individual stars in distant galaxies, better spectroscopes, better photographic film, the understanding of redshifts, the discovery of a relation between period and luminosity in the stars called Cepheid variables.)

I find it wholly unsurprising that people might need a century or two to digest such a major shift in how we view the universe around us. What’s remarkable is that lately the pace of change has accelerated, and nobody seems to be having much trouble keeping up.

Consider what’s happened in cosmology in the 80-some years since Hubble’s revelation. There was the battle between the steady-state and the big-bang models, which can be traced back to the 1920s and 30s and that was finally resolved in the 1960s with the discovery of the cosmic background radiation. Then there’s “dark matter.” Fritz Zwicky pointed out in the 1930s that the dynamics of galaxies imply there’s a lot more mass out there than we’re seeing, and this discrepancy became more troubling with later observations. By the 1980s or 90s most astronomers had accepted the remarkable conclusion that we don’t know what the universe is made of; all of the familiar “baryonic” matter of stars and planets is a minority constituent; the bulk of the mass is some unidentified stuff that Primack dubbed cold dark matter.

Even weirder (if that’s possible) is the notion of cosmic inflation: In a period of 10^–36 second, the universe expanded by a factor of 10⁷⁸. The inflationary hypothesis was first put forward in 1980, was tweaked a bit later in that decade, and was soon swallowed whole by the cosmological community (with the exception of a very few skeptics).

Finally comes “dark energy,” the force that’s causing the cosmic expansion to accelerate. It’s well known that this concept goes back to the early years of general relativity, with Einstein’s cosmological constant Λ. But Einstein soon disavowed the idea, and it remained moribund until about 15 years ago, when two groups of astronomers found direct observational evidence that the expansion is indeed accelerating. The resurrection of Λ was so quick and total that this year’s Nobel prize in physics was awarded for this work.

I find it astonishing and disquieting to live in a universe that’s so very different from the one I was born into. We already had external galaxies in my childhood, and Fred Hoyle and George Gamow were sparring over the big-bang/steady-state issue. But I grew up with no inkling of dark matter, dark energy or cosmic inflation. Now it turns out that most of the universe disappeared over the event horizon in the inflationary era, a fraction of a second after it all began, and long before any of us had a chance to see what we were missing. Of what’s left, less than 1 percent is the kind of matter we know and love—and nobody has a very good idea what the rest of all that stuff might be.

Given the contentious history of earlier innovations in cosmology—starting, of course, with the post-Copernican civil war—I would have expected more controversy over these ideas. But the whole rapid-fire series of head-spinning revolutions seems to have been accepted rather placidly, both within astronomy and by the wider scientific community. Why so little resistance? Is the evidence so compelling as to overwhelm all opposition? Or, on the contrary, have we become so complacently accepting of what experts tell us to believe that we’ve lost all independent judgment.

In a telephone conversation I asked Primack how he would explain the lack of controversy. He broadened the scope of the question, pointing out that when you consider the public at large, rather than the scientific community, the issue is not uncritical acceptance but rather ignorance and indifference. A population that doubts Darwinian evolution and anthropogenic climate change is not too easily convinced by evidence or cowed by authority. If no one has risen up to denounce the teaching of dark matter and dark energy in the public schools, it’s simply because they are unaware of those ideas. I think Primack is right about this, but I don’t understand why questions about the basic nature of the universe—which once excited such passion—could now lie beneath the notice even of the most benighted citizens.

(By the way, the headline on this post is borrowed from my former boss, Gerard Piel, who published a book under that title. Now that Gerry is gone, I can confess that I never read the book, but I always liked the title.)

I went to a magic show the other day. Nick Trefethen was giving a demo of Chebfun, a Matlab extension package he is building in collaboration with his Oxford students and colleagues. In the course of the talk, several mathematical rabbits were pulled out of numerical hats.

The key idea in Chebfun is to represent any function of a real variable by a polynomial approximation.

  >> f = chebfun('sin(x) + sin(x.^2)', [0 10]);
  >> plot(f)

That wiggly line looks like a graph of y = sin(x) + sin(x²), but that’s an illusion. What is being plotted here is a certain polynomial of degree 118 that happens to approximate sin(x) + sin(x²) with high precision.

As I understand it, the chebfun construction algorithm works something like this. First you select N+1 points in the interval where the function is defined, and construct the unique polynomial of degree N that passes through all the points. If the error of this approximation is below a threshold, you’ve found your chebfun. Otherwise, choose a larger sample of points and try again.

The sample points are not evenly spaced across the interval. They are Chebyshev points, whose distribution varies as a cosine function, denser at the extremes and sparser in the middle. In this case, the process converged with 119 Chebyshev points:

In one respect the example above is an easy one: The function is quite smooth. Here’s something more challenging:

  >> hat = 1-abs(x-5)/5;
  >> h = max(f, hat);
  >> plot(h)

This is where we pull the rabbit out of the hat—or at least several pairs of rabbit ears. To deal with the discontinuities sharp corners in this curve, the Chebfun system assembles 25 polynomial segments, each defined on a different interval. Some are linear, some of higher degree. But the entire structure is still treated as a single function, which can be operated on by other functions. For example, sum(h) calculates the integral over [0, 10], returning the result 8.598303617326401. And here’s the square root of those rabbit ears:

These are neat tricks, but why would one want to work with polynomial approximations to a function, rather than with the function itself? I’m too new to all this to answer that question with confidence, so I’ll quote the Chebfun Guide:

The aim of Chebfun is to “feel symbolic but run at the speed of numerics”. More precisely our vision is to achieve for functions what floating-point arithmetic achieves for numbers: rapid computation in which each successive operation is carried out exactly apart from a rounding error that is very small in relative terms.

For those who want to know more, I offer a few pointers:

The first published paper on Chebfun:

Battles, Zachary, and Lloyd N. Trefethen. 2004. An extension of MATLAB to continuous functions and operators. SIAM Journal on Scientific Computing 25:1743–1770. (PDF)

Trefethen’s argument favoring floating-point arithmetic over symbolic computation or exact rational arithmetic:

Trefethen, Lloyd N. 2007. Computing numerically with functions instead of numbers. Mathematics in Computer Science 1:9–19. (PDF)

A provocative account of why polynomial approximation is not as wonky as you may think:

Trefethen, Lloyd N. 2011. Six myths of polynomial interpolation and quadrature. Mathematics Today. (PDF)

Finally, Trefethen has a forthcoming book on Chebfun and related matters (which I have only just begun to read):

Trefethen, Lloyd N. To appear. Approximation Theory and Approximation Practice. (PDF)

Chebfun runs inside Matlab, the numerical computing environment from Mathworks. Chebfun itself has recently become open-source software (under a BSD license), but Matlab is proprietary. As far as I can tell, Chebfun does not not (yet?) run under Octave, the open-source alternative to Matlab.

Those are hot young stars in the Large Magellanic Cloud—one of the puppy-dog galaxies that follow the Milky Way around—photographed by the Hubble Space Telescope. (Detail cropped from a Wikipedia image.) Note that four rays seem to emanate from each of the brightest stars. The rays are not, of course, true beams of light radiating in the four cardinal directions. They are an artifact of the telescope’s structure: a diffraction pattern created by the four vanes of the “spider” that supports the secondary mirror within the barrel of the telescope. Many other telescopes have three-vane spiders that yield a six-pointed diffraction pattern.

Recently, in my lovable know-it-all manner, I was holding forth on the idea that this diffraction effect—a mere accident of instrumental design—might actually be the source of the familiar iconographic star, with its five or six angular points. In other words, we think of a star as something spiky, poking out in various directions, because we’re used to seeing telescopic images with this diffractive defect. At right is M. C. Escher’s interpretation of what stellar means. For other examples see the Hollywood Walk of Fame or the flags of the U.S. and the E.U. and those of more than 50 other countries, not to mention Texas.

Well, it turns out my cute idea about the cultural influence of telescopic photos is utterly bogus. If you need any evidence, the engraving reproduced below should suffice. It shows the muse Astronomia (a.k.a. Urania) pointing out the moon and stars to Ptolemy. The stars are five- or six-pointed scribbles that beg to be called asterisks. The engraving appears in the Margarita Philosophica of Gregor Reisch, published in 1504, which is a full century before Galileo turned his telescope to the heavens. Whatever those engraved stars are, they are not artifacts of telescope spider vanes.

The dictionary offers further evidence. For example, the starfish (genus Asterias, class Asteroidea) has had that name at least since 1538. And the asterisk—the typographical mark—has a citation in the OED going all the way back to 1382. These terms make sense only if the concept of a star was already associated in most people’s minds with a spiky polygon, rather than a dimensionless point of light in the night sky.

And that’s what puzzles me, because the stars really do appear to be dimensionless points of light. When I stare at the sky, I see some twinkling going on, but nowhere do I see pentagrams and hexagrams pinned to black velvet, or even the slightest hint of angularity. So where did this tradition get started? Did the Greek word ?????? already convey a sense of symmetrical spikiness, so that ancient Athenians would have understood why we call certain flowers asters? Is the same iconography prevalent in other cultures, say in China? Those 50+ star-studded flags (including China’s) suggest that the conventional stellar icon is at least recognized globally, but they don’t tell us where and when it all began. After my telescopic theory fell apart, I had a second hypothesis, namely that the star icon might come from the symbol-happy world of astrology, but I’ve found no support for this idea either. So I throw the question out to the starry void: How did the star get its points?

Addendum 2011-12-16: The illuminating comments below on ancient Egyptian paintings of stars would appear to settle part of my question: Well over 2,000 years ago, at least some people were already drawing stars in much the same way a modern kindergartner does. What I’d still like to know is why. Yes, there are many plausible just-so stories, but you’d think that someone at the time might have offered a word of explanation.

The other day I spent a pleasant afternoon leafing through The History and Practice of Ancient Astronomy, by James Evans (New York: Oxford University Press, 1998). It’s quite a thorough introduction to Greek and Egyptian ideas about the sky, but I did not find an answer to my question about the points of stars. The astronomers of that period were engrossed in charting the positions and motions of the stars, but one gets the impression they had no interest whatever in the nature of those bright objects—what they look like up close, what they’re made of, why they shine. Of course I don’t really believe the ancients were so lacking curiosity. Surely Aristotle holds forth somewhere on the substance of the stars? But I haven’t found it yet.

The curious document above was produced sometime in the spring of 1980 by Don Knuth to show off the typographical prowess of his new programs, TeX and Metafont. The software was then being introduced to the mathematical community through the publication of TeX and Metafont: New Directions in Typesetting, and I was writing a news item about it for Scientific American. At the time it seemed like a quaint, quirky and quixotic project, worth a column of type in the magazine even if nothing came of it in the long run. I would not have guessed that 30 years later TeX would be the foundation of a huge software superstructure—and would still be a part of my own professional life.

TeX is not the oldest software still in widespread use, but it may be the most stable. In the core of the system—the typesetting engine—very little has changed since 1990. And there will be even fewer revisions going forward. The current version of TeX is 3.1415926. Knuth has decreed that on his death the version number should be set equal to π and no further changes should ever be made. “From that moment on, all ‘bugs’ will be permanent ‘features.’”

I think—though this is subject to interpretation—that what Knuth wants to protect from all future meddling is not the text of the program itself, or even the underlying algorithms and data structures, but rather its operational specification. His intent in freezing TeX is to ensure that the same input should always yield the same output. Specifically, any software that calls itself TeX is supposed to pass his TRIP test suite.

I am of two minds about this policy. Mind One agrees with Knuth’s declaration: “Let us regard these systems as fixed points, which should give the same results 100 years from now that they produce today.” It’s comforting to think that all the TeX documents I’ve written over the years will still be readable a century hence. But Mind Two reminds me that in practice I have trouble maintaining TeX documents even for a few months, much less decades or centuries. What about those presentations done with the foils class that stopped working after an upgrade and that I’ve never bothered to fix? Or the articles using the pstricks package that won’t compile under pdflatex? TeX itself may be a fixed point in the software universe, but everything else spins dizzily around it.

The skeptical Mind Two has another argument as well: Under Knuth’s edict it’s not just the TeX markup language that can’t change; it’s also the architecture of the system. Knuth created his flawless soufflés and dæmon diarrhœa at an ASCII terminal wired to a PDP-10, and the only way he could see the product of his labors was to walk down the hall and retrieve hard copy from the AlphaType machine. We are no longer accustomed to such barbarities. TeX has been hauled halfway into the world of modern computing. Front-end software such as TeXShop provides a pleasanter interface. But the core programs still run in batch mode, as they did in the Dark Ages. To make even the smallest change in a document, you still need to throw away all the existing output and run a whole file (or set of files) through the compiler tool chain. Sometimes you have to do it twice. Or four times. Isn’t this ridiculous in a world of event-driven, interactive, multithreaded software? Will we still have to press the Typeset button in 2111?

Mind One replies: Of course not. By then we’ll just throw Moore’s Law at it: Automatically rerun TeX n times for every keystroke in the editor.

At this point Mind Three pipes up. (Did I mention that I’m of three minds?) The problem here, she says, is not that we can’t or shouldn’t alter TeX. It’s the utterly depressing notion that we’re incapable of building anything better, and that TeX will still be the typesetter to beat after another century. Surely, if we just stand tippytoe on the shoulders of Don Knuth, we can see a little farther. Who was the architect who said that every great building should have a bomb in the basement, set to blow itself up after 50 years and thereby clear the land for something greater still? Let’s make a new improved TeX. We’ll call it TNT.

Minds One and Two pounce in unison: You think we haven’t thought of that? What about ε-TeX? NTS? ExTeX? What about LuaTeX…?

•     •     •

This trinitarian meditation was inspired by a blog post I stumbled upon last week, in which an entity named Valletta Ventures, publisher of TeXPad for the Macintosh, attempts to port TeX (and also LaTeX) to the iPad; in this venture, Valletta Ventures eventually concedes defeat. The failure could be blamed on the scrutineers at the Apple App Store, who insist that every iPad program must be bundled up in a single executable. (My current TeX /bin directory has 342 entries.) But even if we were to let Apple off the hook here, the project still seems truly quaint, quirky and quixotic. Mind One says you shouldn’t expect to run a system as large and complex as TeX on a puffed-up cellphone. But Mind Two says: Why not? The iPad probably has more computational oomph than Knuth’s 1980 PDP-10.

In the end my sympathies lie with Mind Three, who sees the barrier to putting TeX on the iPad not as a lost opportunity but as a thin, bright glimmer of hope on the horizon. Maybe this protected market—the walled garden of Cupertino—will induce some young genius to create the next great mathematical writing system, an iPad app so good it will induce envy in all of us poor TeX users.

Looking at the issue more broadly, I think we often value stability and reliability a little too highly, and innovation too lowly. The world of computer science is overpopulated by walking fossils—not just TeX but also Unix, the Intel 86 architecture, TCP/IP. Quoting myself:

What has everybody been doing for the past 35 years? Can it be true that technologies conceived in the era of time-sharing, teletypes and nine-track tape are the very best that computer science has to offer in the 21st century?

As a remedy for this situation, the bomb in the basement may be a bit extreme. But I wonder if we shouldn’t try something like a reverse patent, where the whole world gets free use of an invention for the first 17 years, but then there’s an escalating schedule of royalties or taxes for those who fail to come up with a brighter idea.

•     •     •

One final question. When Knuth counts LAZY FOXES in his typographic specimen, where does he get the peculiar number 854.9176302? I would have thought 85491.76320.

As a high school kid in the 1960s, I wrote a snarky term paper arguing that retirement is wasted on old people. By the time you get your promised years of leisure, you’re too worn out to enjoy them. So I proposed a new order of working life: Everybody gets five or ten years off at the start, when they’re still full of spunk, in exchange for a promise to keep trudging away on the treadmill right up to the end.

I wasn’t able to arrange such a pretirement for myself, but the world now seems to be coming around to my way of thinking. Here’s some evidence, with data courtesy of the Bureau of Labor Statistics:

The proportion of Americans who stay on the job after age 65 was falling steadily for many years and got down to about 10 percent in the 1980s; but it has been rising since then, and the rate of increase accelerated after 2000. Today almost 17 percent of the 65+ cohort are still working. Meanwhile, the analogous curve for youths aged 16 to 24 is pretty much a mirror image. The employment rate peaked in the 1980s and has been declining since then. In the years between 2000 and 2010 it fell from just under 60 percent to 45 percent.

My pretirement hypothesis—the notion that we’re giving people an opportunity to waste their youth on the golf course rather than their old age—is just about the most benevolent interpretation one could possibly put on these trends. A less-rosy reading of the same data puts the blame on old geezers like me who just won’t get out of the way and give the youngsters their turn. For some reason, this view seems to be prevalent among recent grads who expected a job offer at the end of their studies but instead got only a bill from Sallie Mae.

An op-ed piece in the Sunday New York Times takes issue with this sour diagnosis. Edward L. Glaeser, an economist at Harvard, argues that what motivates the elders who linger in the work force is not greed, selfishness or indifference to their children’s aspirations; it’s economic necessity. Their houses are underwater; their 401k’s have swooned; they can’t afford to retire. Furthermore, the kids should be grateful that grandmom and grandpop have hung on to the family business:

It’s counterintuitive, but the forever work life of older Americans may turn out to be a good thing for young workers…. Recent studies in Britain and Germany find a positive correlation between labor-force participation among the elderly and youth employment. It’s not that older workers never crowd out younger workers, but there are myriad ways in which older workers also increase employment among the young. As older workers earn more, they can afford to buy more products produced by the young. Older workers may be entrepreneurs who employ younger workers, and they may pass along valuable skills to the young.

America has a terrible youth unemployment problem…. We have reason to worry that the current economic slowdown will create a lost generation of Americans who are now in their 20s. But it’s a mistake to imagine we can fix the problem of youth unemployment by encouraging older workers to retire.

According to Wikipedia, Glaeser, is 44 years old—right in the middle between the involuntary pretirees and the never-gonna-retirees.

Glaeser doesn’t discuss the demographic context of these changes, and neither did I in my high school term paper. Looking back on it now, I see a serious flaw in my proposal. Retirement plans, such as the Social Security system, work best with a pointy population pyramid, so that a wide base of young earners supports a smaller number of pensioners. My plan called for reversing the flow of resources, which would not have worked out well given the age structure of the U.S. population in the 1960s, with my own generation of Baby Boomers fattening the base of the pyramid. But the situation is different now; the pyramid is slimming down, and citizens in their 60s may soon outnumber those in their 20s. Maybe pretirement is worth a second look.

John McCarthy, the mind behind Lisp, died yesterday at age 84. The photographs below are from one of his web sites at Stanford. Many of his papers are available through a different web page. (I don’t know how long either of these sites will remain on the air.)

The Kiplingesque just-so story of how Lisp got its parentheses has been told several times, by McCarthy and others, but today seems an appropriate occasion to trot it out again. In the winter of 1958–59 McCarthy was at work on a paper that would eventually be published in Communications of the ACM as “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.” (There was never a Part II.) He was looking for good example programs to show that the new language was “neater than Turing machines” as a formalism for describing computable functions. In the end he came up with a demo much better than “Hello world!”

The following paragraphs are from McCarthy’s presentation to the first History of Programming Languages meeting in 1977 (ACM SIGPLAN Notices, Vol.13, No.8, August 1978; there’s an HTML-ized version).

Another way to show that LISP was neater than Turing machines was to write a universal LISP function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function eval[e, a], which computes the value of a LISP expression e—the second argument a being a list of assignments of values to variables (a is needed to make the recursion work). Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice.

S. R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.

The “notation representing LISP functions as LISP data,” was the parenthesized prefix syntax now beloved by Lispers and reviled or ridiculed by just about everybody else. McCarthy himself was not a big fan of this notation. He believed—to the end of his life, as far as I know—that the language deserved a more conventional “algebraic” syntax, perhaps something in the Algol tradition. The parenthesized lists were called S-expressions; the elements of the fancier notation were to be called M-expressions. In the 1977 talk McCarthy continued:

The unexpected appearance of an interpreter tended to freeze the form of the language, and some of the decisions made rather lightheartedly for the “Recursive functions…” paper later proved unfortunate…. The project of defining M-expressions precisely and compiling them or at least translating them into S-expressions was neither finalized nor explicitly abandoned. It just receded into the indefinite future, and a new generation of programmers appeared who preferred internal notation to any FORTRAN-like or ALGOL-like notation that could be devised.

I guess I’m part of that new, unregenerate, generation, who have never been weaned away from their (((()))).

In 2005 I attended an International Lisp Conference at Stanford. McCarthy was present throughout the proceedings but kept a low profile until the final discussion session, when he rose from his seat to make this pronouncement:

If someone set off a bomb in this room, it would wipe out half of the worldwide Lisp community. That might not be a bad thing for Lisp, because it would have to be reinvented.

There were two provocative aspects to this statement. First, the lecture hall where we were gathered held no more than a couple of hundred people, so if we represented half of the of worldwide Lisp community, the whole outfit must be pretty small potatoes. Second, if obliterating half the Lisp community would be good for the language, then we must have gone badly astray somwhere in the past 50+ years.

My own view (for what it’s worth) is quite different. I’m simply amazed that so many fundamentally sound ideas were formulated so clearly so early in the history of computation. If McCarthy could get so much right in 1958, what the hell have we been doing since then?

•     •     •

One more reminiscence of John McCarthy. He was a great prognosticator and futurist. In the introduction to a Scientific American special issue on information (September 1966), he wrote presciently about a the prospect of putting a computer in every home and about what we now call cloud computing. (He filled in more details on these themes in a 1970 paper.)

No stretching of the demonstrated technology is required to envision computer consoles installed in every home and connected to public-utility computers through the telephone system. The console might consist of a typewriter keyboard and a television screen that can display text and pictures. Each subscriber will have his own private file space in the computer that he can consult and alter at any time.

But not all of McCarthy’s predictions were precisely on target. In 1989 he wrote about the threat of the fax machine:

Unless e-mail is freed from dependence on the networks, I predict it will be supplanted by the telefax for most uses in spite of the fact it is more advantageous…. Unless e-mail is separated from special networks, telefaxing will prevail because it works by using the existing telephone network directly.

I say we should let him slide on that one. Overall, the world is a richer place for his contributions to it.

The area enclosed by a circle is πr². The volume inside a sphere is ⁴∕₃πr³. These are formulas I learned too early in life. Having committed them to memory as a schoolboy, I ceased to ask questions about their origin or meaning. In particular, it never occurred to me to wonder how the two formulas are related, or whether they could be extended beyond the familiar world of two- and three-dimensional objects to the geometry of higher-dimensional spaces. What’s the volume bounded by a four-dimensional sphere? Is there some master formula that gives the measure of a round object in n dimensions?

The text above is the opening paragraph of my new column in American Scientist. If you’d like to know how the story comes out, by all means go read the full column in the format of your choice: HTML, PDF, or ink-on-paper at better newsstands everywhere. For those in a hurry, here’s the gist in one equation, one code snippet and one graph:

The equation is the “master formula” mentioned above: Plug in the radius r and the number of spatial dimensions n, and you’ll get back the volume of the corresponding ball. (If the gamma function in the denominator is unfamiliar, think of it as a factorial that makes sense even when the argument is not an integer.)

        v[0, r_] := 1
        v[1, r_] := 2r
        v[n_,r_] := (2πr2/n) * v[n–2, r]

This version of the formula, given here in Mathematica notation, works only for integer n. It defines the volume of a 0-ball as 1 and the volume of a 1-ball as 2r. For larger n, the volume is calculated recursively: It’s 2πr²/n times the volume of a ball with the same radius in n–2 dimensions.

Finally, the graph shows the volume of a unit n-ball (i.e., r = 1) for values of n from 0 through 20. When I first saw these data, two things took me by complete surprise. First, I was perplexed to learn that the volume of an n-ball dwindles away to nothing as n gets large. Second, I was even more surprised that the relation is not monotonic but has a peak at finite n. If we consider only integer n, the unit 5-ball has the largest volume. If we allow the spatial dimension to become a continuous variable, the maximum is at approximately n = 5.26.

These facts still seem pretty weird to me. And, although they are hardly new discoveries—the formula cited above goes back to the middle of the 19th century—they seem not to be widely known. How come nobody ever told me about this stuff?

Well, it turns out somebody did tell me, long ago. A few days after the current issue of American Scientist was sent to the press, I came upon an old Martin Gardner column with the title “Circles and spheres, and how they kiss and pack.” Writing about the n-sphere (by which he means the same object I’m calling the n-ball), Martin remarks:

And something very queer happens to its n-volume as n increases. The area of the unit circle is, of course, π. The volume of the unit sphere is 4.1+. The unit 4-sphere’s hypervolume is 4.9+. In 5-space the volume is still larger, 5.2+, then in 6-space it decreases to 5.1+ and thereafter steadily declines. Indeed, as n approaches infinity the hypervolume of a unit n-sphere approaches zero!

These words were published in the May, 1968, issue of Scientific American. I was a faithful reader in those days and surely saw the column, but I retain no shred of memory.

In the same column Martin discusses another mind-boggler that I also mention. Consider this configuration of disks in a square:

The maroon disk in the middle, tangent to the four blue disks, has a radius of √2 – 1. In the analogous three-dimensional arrangement, with eight blue balls, the radius of the central maroon ball is √3 – 1; in n dimensions it is √n – 1. Now look at what happens when n = 9: The maroon ball, though still surrounded on all sides by blue balls, has expanded to a radius of 2 and thus reaches the edge of the enclosing cube. I learned of this conundrum from Barry Cipra, who gives an account of it in WHIMS I, the first volume in the AMS series What’s Happening in the Mathematical Sciences (1991). Barry wasn’t able to tell me anything about the provenance of the problem. Martin describes it as “an unpublished paradox discovered by Leo Moser,” a Canadian mathematician who died just a few years later. As far as I can tell, Moser never did publish anything about the problem. If anyone knows more about its origin, I’d be eager to hear about it.

A further note: The new American Scientist had not been out more than a day or two before I began getting letters arguing that the whole tale I’m telling is nonsensical because balls (or other shapes) that differ in dimension have volumes measured in different units. A unit 3-ball is neither larger nor smaller than a unit 2-ball, because one kind of volume is measured in cubic units and the other in square units. This issue is addressed in my column, though evidently not to the satisfaction of all readers. In retrospect, I think my discussion would have been clearer (and less controversial) if I had stated everything in terms of volume ratios rather than volumes. In other words, the numbers labeling the ordinate of the graph above should be understood as measuring the ratio of the volume of a unit n-ball to the volume of a unit n-cube. All measurements involve some such comparison, but in this case it’s really helpful to make it explicit.

I do believe that the curve in that graph is trying to tell us something important about geometry in higher-dimensional spaces. I have no clear idea what. Wisdom and insight are always welcome in the comments.

The ever-puzzling Peter Winkler offered three problems in the August Communications of the ACM:

1. Does every positive integer divide some number of the form 1{0,1}*—that is, a positive integer whose decimal representation includes no digits other than 0 and 1?

2. Does every positive integer divide a Fibonacci number?

3. Is there an odd perfect number (an odd integer equal to the sum of its proper divisors)?

Answers to Problems 1 and 2 have now been published in the September CACM, so I won’t worry too much about spoiling anyone’s fun with the discussion below. Still, if you’d like to take a crack at the first two problems, do so before you read on. (As for Problem 3, you needn’t worry about my giving away the secret.)

Winkler’s solutions are based on the pigeonhole principle. If you divide successive 1{01}* numbers or successive Fibonacci numbers by any fixed integer n, the remainders necessarily lie between 0 and n–1. Furthermore, the sequence of remainders repeats cyclically. For example, the Fibonacci numbers modulo 3 are:

0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 . . .

The trick is to show that the cyclic sequence of remainders always includes zero. For details see Winkler’s solution page mentioned above. (CACM is behind a paywall, but I think these links will work for nonsubscribers.) A 2007 paper by Tanya Khovanova also explains what’s going on, and gives a couple of further enticing problems.

The pigeonhole argument answers the questions as posed, but it tells us very little about the structure of the solutions. Which 1{01}* numbers and which Fibonacci numbers are divisible by various integers n? Are there any interesting patterns in the results? I was curious, so I started computing.

The graph above shows the smallest 1{01}* numbers divisible by each n from 1 through 30. The standout pattern is the series of tall flagpoles for n a multiple of 9. It appears that 1{01}* numbers that include 9 among their divisors are rarities. I didn’t foresee this pattern, although I should have. It’s connected with the long-forgotten ritual of “casting out nines,” which in turn is based on the following fact: A decimal number is divisible by 9 if and only if the sum of its digits is divisible by 9. (Question: What are the smallest 1{01}* numbers divisible by 99 and by 999? Answers at the end of this article.)

Below is the analogous graph for Fibonacci numbers divisible by values of n between 1 and 30.

There are some interesting patterns here, too, but we need a bigger sample to see them clearly.

By the way, it’s important to notice that the ordinate axis of the Fibonacci graph gives the index of each Fibonacci number, not the Fibonacci number itself. I adopt this indexing convention :

The diagram below offers another way of looking at the mapping from integers n (on the left) to the smallest Fibonacci number F(m) divisible by n (on the right):

A few Fibonacci numbers are highly popular—notably F(12), F(24), F(30), F(60). Indeed, F(24) is the destination of 12 of the first 100 values of n. The reason for this clustering is not a deep mystery; Fibonacci numbers of the form F(6k) tend to be very “smooth” numbers, with an abundance of small factors. F(60) is equal to 1,548,008,755,920, a number that has 960 divisors. F(240) has more than 1.3 million divisors. These smooth numbers simply have more chances to be the smallest F(m) divisible by some n.

But the clustering also highlights an asymmetry. The solution of the Winkler problem says that we can draw a line from every n on the left to a specific F(m) on the right, the least Fibonacci number divisible by that n. What about the converse? Is every F(m) the least Fibonacci number divisible by some n? Can we draw a line from every F(m) on the right to some n on the left? The diagram as shown, which covers all n up to 100, has many gaps in the set of nodes on the right; for example, none of the numbers between F(61) and F(67) are among the smallest Fibonacci numbers divisible by an n ≤ 100. If we were to extend the computation to larger values of n, would all the gaps in the righthand column eventually be filled in? Let me state that question a little more formally: For every m, is there an n that divides F(m) but does not divide F(k) for any k < m?

This is a trick question. The answer is No because of F(2), which is “shadowed” by F(1), since F(1) = F(2) = 1. But F(2) is unique in this respect. If we set aside this one exception, is the statement true for all other F(m)? Now the answer is Yes, but trivially so. Every F(m) is divisible by F(m) itself, which cannot possibly divide any F(k) with k < m. (In the case of Fibonacci numbers that are prime, F(m) and 1 are obviously the only divisors.)

To avoid the trivial solution, we need to ask a more tightly constrained question, which I’ll phrase as a conjecture:

If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.

Is the conjecture true? If so, where do all those new divisors come from? What mechanism guarantees that every nonprime F(m) will introduce at least one divisor never seen before in the sequence of Fibonacci numbers? If the conjecture is false, then there are “unselfish” Fibonacci numbers that share all their proper divisors with their smaller siblings, keeping none for their own exclusive use. What is the smallest such unselfish F(m)? (For what it’s worth, a computational search shows that any counterexample to the conjecture must lie beyond F(382).)

I’m going to leave this question as a challenge. I’ll give an answer in an update—in the unlikely event that no one posts a complete solution in the comments section in the next 10 minutes. One further note: Unselfish numbers do exist among the 1{01}* numbers; the smallest example is 1111, whose only proper divisors are 11 and 101, both of which obviously divide lesser 1{01}* numbers. Thus if you want to assert that Fibonacci numbers behave differently in this respect, you might want to think about what distinguishes the two sequences.

Finally, more about patterns of divisibility in Fibonacci numbers. The dots in the figure below show the least m such that n divides F(m) for all n up to 1,000:

It’s interesting that the dots tend to line up along certain rays, namely those whose slope is a ratio of small integers. The slopes m/n = 1 and 1/2 are the most clearly delineated, but there are also aggregations detectable by eye at m/n = 1/4, 1/3, 2/3, 3/4 and 3/2. The ray at m/n = 2 has only four data points on it in the range up to n = 1,000, but it is significant for another reason: It marks the absolute boundary of the m/n ratio. In other words, not only is it true that every n divides some F(m), but furthermore the m in question is never greater than 2n.

There is no sign of such radial streaks or other distinctive patterns in the equivalent graph for the 1{01}* numbers:

As with the Fibonacci graphs, the vertical axis here represents not the numerical magnitude of an 1{01}* number but its index within the sequence. For example, the smallest 1{01}* number divisible by 18 is 1,111,111,110, which is the 1,022nd number in the 1{01}* sequence. (It’s more than coincidence that 1111111110₂ = 1022₁₀.) Hence there’s a dot at n = 18 and vertical coordinate 1,022. I have colored orange all the dots associated with n that are multiples of 9. The dots along the upper margin of the graph are off-scale and actually belong at much higher elevations. For example, the dot for n = 99 should be at height 262,143 (the index of 111,111,111,111,111,111). The dot at n = 999 belongs at height 134,217,727 (the index of 111,111,111,111,111,111,111,111,111).

Update 2011-10-09: More than a month ago I promised an answer to the question posed above: Is there a composite Fibonacci number for which all the proper divisors are also divisors of smaller Fibonacci numbers? When I asked the question, I had an answer for it. But a week later when I sat down to write up the proof, it fell apart like wet tissue. Since then the problem has been constantly with me. I’ve been waking up with it in the morning; I go to bed with it at night; it comes back to visit at idle moments during the day. Several times I’ve thought I had found a solution, but then the argument fell to pieces again. If some kindly reader had posted a full proof in the comments, I could have responded, “Yes, yes, exactly so. That’s just what I had in mind.” But only one reader came to my rescue (thanks, unekdoud!); although that suggestion seemed to be heading in the right direction, I wasn’t able to fill in all the details.

Now I have yet another proof. It’s the middle of the night as I write this, but I’m going to stay up and get this posted before the idea disintegrates again.

Here, copied from above, is a more precise statement of the problem, phrased as a conjecture:

If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.

I claim the conjecture is true, based on this assertion: If every divisor of F(m) also divides some smaller F(k), then the F(k) in question cannot be greater than F(m/2), while at least one of the divisors must be no smaller than √F(m). But this is impossible, because √F(m) > F(m/2) for all m > 2. (For odd m, take the ceiling of m/2.)

The key to the proof is again the cyclic pattern of remainders observed when the members of the Fibonacci sequence are taken modulo an integer. In particular, if an integer a divides F(m), then a also divides F(2m), F(3m), F(4m), . . .   For example, F(8) = 21 is divisible by 3 and 7, and these numbers are also divisors of F(16) = 987 and F(24) = 46,368.

An immediate consequence of this cyclic structure is the remarkable fact that F(k) divides F(m) if and only if k divides m. Again let me cite an example: F(15) = 610 is divisible by F(3) = 2 and by F(5) = 5 and by no other Fibonacci numbers. (The prime factors of 610 are 2, 5 and 61. Note that the factor 61 divides no smaller Fibonacci number, and so F(15) is a confirming instance of the conjecture.)

A further observation is that if m is prime, then F(m) cannot be divisible by any Fibonacci number.

Let’s look at the divisors of F(m) for composite values of m. We know that such divisors exist. They include every F(k) for which k divides m, as well as all the proper divisors of each such F(k). Suppose, contrary to the conjecture, that these known divisors comprise all the divisors of F(m). Then for each integer a that divides F(m) we can ask which F(k) it also divides. Actually, a given a might divide many F(k), but consider just the smallest member of this set. If a divides this minimal F(k), then it also divides F(2k), F(3k), and so on, but it divides no other Fibonacci numbers. Thus F(m) must be a member of this series, or in other words m must be a multiple of k. The smallest such multiple is m = 2k. This gives us half of the proof: If a divisor of F(m) also divides F(k), k can be no larger than m/2.

The second half is easier. Divisors come in pairs; they are integers a and b such that ab = F(m). Furthermore, if a ≤ √F(m), then b ≥ √F(m). Thus we conclude that b cannot be less than the square root of F(m) or more than F(m/2)—a contradiction.

The same reasoning applies with even greater force in the case of prime m. If we imagine that a divisor of F(m) is also a divisor of some smaller F(k), we are driven to the conclusion that k divides m, which can’t be so for prime m.

In the course of working all this out in my bumbling-stumbling way, while making lots of lists of Fibonacci numbers and their divisors, the patterns I was seeing suggested a slightly stronger conjecture:

Every Fibonacci number that is not a perfect power has at least one prime factor that appears in no smaller Fibonacci number.

The perfect-power exception excludes exactly five Fibonacci numbers: F(0) = 0, F(1) = 1, F(2) = 1, F(6) = 8 = 2³ and F(12) = 144 = 12². No other Fibonacci numbers are perfect powers; I find it interesting that this fact was proved only in the past few years, and only with the use of industrial-grade mathematical machinery. On the other hand, “my” conjecture was proved almost a century ago by the American mathematician R. D. Carmichael. If I had known that fact a few weeks ago, I would have slept better. But maybe learned less.