Still more on World3 and The Limits to Growth. Two weeks ago I gave a talk at Harvard on all this, and the video is now online. Look for the Brian Hayes–March 30 link near the bottom of the page.

The slides are here.

And, by the way, the slides were done with deck.js, a JavaScript-and-HTML framework I had never tried. Both preparing the slides and presenting them went very smoothly. Running the talk from within a browser has obvious advantages when you’re talking about Internet things; you don’t have to break out of Powerpoint or Keynote to go to a web page. Using Mathjax for TeX stuff is effortless. So is posting your slides on the web. On the other hand, navigation may not be obvious at a glance. Use the arrow keys. The M and G keys also do helpful things.

The March–April American Scientist has been out for a couple of weeks. My “Computing Science” column looks at the future of scientific illustration in a world where we do most of our reading not on paper but on a screen of some kind—a screen that has a computational engine behind it.

My hope for those future illustrations is that they won’t just sit on the page looking pretty. They’ll do stuff. They’ll make good use of the available computing machinery. They’ll invite the reader to interact and explore. Below is my attempt to give an example of the kind of illustration I have in mind. It’s an interactive version of the familiar population pyramid, based on data from the U.N. and built with HTML, CSS, SVG and the d3.js JavaScript library from Michael Bostock. Please play.

I’m optimistic and enthusiastic about the digital future of science publishing. The digital present is another matter. One indicator of how far we still have to go is that some of you have no idea what that population-pyramid illustration is supposed to look like, because it doesn’t appear on your screen. If you’re reading this with an older web browser, you may see a static placeholder illustration or an error message or nothing at all. If you’re reading the RSS feed, I offer my apologies, but there’s nothing I can do to help.

Apart from problems of accessibility and compatibility, there’s a deeper issue I want to address here. If the aim is to enhance the literature of science, we have to keep in mind that very little of that literature takes the form of HTML, CSS, SVG and JavaScript. Almost all journal articles and preprints are distributed as PDFs. I have no idea how to make my little animated population pyramid work inside a PDF.

“PDF” stands for Faux Paper Document. PDFs look just like their printed prototypes, with all the typographical niceties—justification, hyphenation, kerning of letter pairs, ligatures. It’s as if the words and pictures had been skimmed off the page and pasted onto the screen (which is in fact pretty close to how the process works). This fidelity to the print tradition follows directly from the history of PDF: It was an outgrowth of PostScript, which was an outgrowth of InterPress, which was developed as software for use in the printing trades. The successful imitation of paper documents is a laudable achievement. As a culture, we have several hundred years of effort invested in learning how to present information effectively and attractively on the printed page; we shouldn’t let that go to waste. However, using a multigigahertz, multigigabyte computing machine as a standin for a sheet of dried cellulose seems a bit of a waste. It’s rather like early printers striving to reproduce the stylistic quirks of scribes writing with quill pens.

HTML can’t match the designerly refinement of PDF, but it is more versatile, livelier, and even playful. HTML documents do tricks. Where PDF is for the suits, HTML/CSS/JavaScript is the home of hackers.

But, again, few scholarly papers are published in HTML. There are a number of reasons for this, but to me the one that seems most salient is a certain lack of thinginess. In my column I write:

Why do authors and readers prefer PDFs for this kind of publication? One factor may be this: A PDF is something you possess. You download it from a server, give it a name, store it in a folder. It’s yours; it stays put. A website built out of HTML has a different character. It’s not a thing you own but a place you visit. You can’t take it home with you—although perhaps you can send a postcard or keep a small souvenir in the form of a bookmark.

“HTML” is an abbreviation for Highly Temporary Markup Language.

If we take this view seriously, then what the world needs is a way to encapsulate HTML documents so that they become first-class, discrete objects—things you can keep, rename, pass around, copy, delete, annotate, modify. For years I thought that this capability should be built into web browsers—that you should be able to press a button to download and store a fully functional and totally self-contained local copy of any web page. My favorite browser of the 1990s, called iCab, came pretty close to this ideal, but for many modern web pages the client-side approach is either unworkable or undesirable. With pages that rely on technologies such as AJAX, it’s not possible to make a fully self-sufficient local copy. And often there are page elements you don’t really want to include in your private copy, such as navigational menus and “Like” buttons and comment forms.

An alternative strategy is to let the author of the HTML document take responsibility for creating a downloadable, autonomous version, with content tailored for that environment. A technology for doing this sort of thing already exists: It’s the EPUB format used by various eBook readers. An EPUB document is essentially a collection of HTML files, CSS stylesheets and various forms of metadata wrapped up in a zip archive. SVG is supported, along with MathML. The 3.0 standard says JavaScript is also acceptable, but that statement is accompanied by a list of warnings that sound like the side-effect disclosures in a pharmaceutical ad.

Apple’s new iBooks Author program also produces some kind of encapsulated HTML, but of course it works only in the Apple sector of the universe. If you’d rather affiliate with a different proprietary dominion, there’s something called CDF from Wolfram Research. (The initials stand for “Conrad’s Document Format.”)

Still another approach would be to stick with PDF but make it more fun. According to the PDF 1.7 specification (which, as you might guess, comes in the form of a PDF), a JavaScript compiler is supposed to be available within PDF documents, and Adobe has an Acrobat JavaScript API document. But as far as I can tell scripting is commonly used only for validating forms and playing slideshows.

The latest version of Acrobat does have a pretty cool interactive viewer for three-dimensional objects. Three years ago Alyssa Goodman and her colleagues at Harvard published a paper in Nature that made use of that viewer. This was apparently the first scientific publication to include a 3D PDF. I don’t know of another example since. And I have never seen any other kind of interactive graphics embedded in a PDF.

For more on all this, I invite you to read my column in the format of your choice: good old-fashioned paper, fine artisanal HTML (with whiz-bang JavaScript graphics), or the pixelated form of paper we call PDF.

This just in from Bill Gasarch: The quest for a rectangle-free four-coloring of the 17-by-17 grid is over. If you don’t know what that’s all about, and you’d like to find out, see Bill’s blog post from 2009 or my earlier comments (one, two, three).

The coloring above (along with several others) was found by Bernd Steinbach of Frieburg University and Christian Posthoff of the University of the West Indies. They win the $289 prize that Gasarch had offered for a solution.

Gasarch has posted more details on the Computational Complexity blog. But apparently we’re going to have to wait until May to learn how the coloring was found. The one interesting clue revealed so far is that the paper will be presented at the International Symposia on Multiple-Valued Logic.

Addendum 2012-02-11: For the benefit of those who don’t read the comments, I repeat a remark from reader Craig:

What I don’t like about this solution (or, indeed, the solutions to other related problems) is the arbitrariness. Is it not the case that you should be able to permute the rows and columns of any solution and arrive at a new solution? That being the case, I feel that you should be able to adjust the rows and columns here in order to highlight some kind of revealing pattern in the colouring.

Indeed, the matrix of dots shown above is one of (17!)² equivalent solutions. How should we choose one of those permutations to serve as a representative of the class?

Personally, I’m not optimistic about finding a “revealing pattern” in any of the 126513546505547170185216000000 permuted matrices. If there were some simple, concisely described rule governing the arrangement of the dots—other than the no-monochrome-rectangle criterion itself—then we could make use of that rule to find a solution, or at least to reduce the search space. When Steinbach and Posthoff reveal their secret method, maybe we’ll learn that such a rule exists, but I doubt it.

Even if we can’t make a pretty picture by permuting rows and columns, it would still be useful to have some canonical ordering, so that we could easily determine whether two arrays are members of the same equivalence class. I’m not sure how best to do that, but if we assign an ordering to the colors, we can at least sort them.

There is still some arbitrariness here. We have not dealt with the 4! orderings of the colors. Is there a smarter way to go about it?

Imagine, if you will, the year 2020, when a billion people around the planet are at their screens. And each is able to withdraw from a great repository any fragments of anything that has been published, as well as the private documents he or she has access to. So, you’re able to bring to your screen not just encyclopedias, not just novels, not just the works of Horace and Cicero and Marcus Aurelius and Shakespeare and Goethe, but obscure stuff from South America and Africa that people have written in the last 5 minutes. And [you're able] to make comments and footnotes and to transclude and quote from anything else that’s published, with automatic royalty.

That’s Ted Nelson, the prophet of hypertext, writing in Byte in 1990. We still have a few years to go before 2020, and yet almost everything Nelson foresaw is already upon us. More than two billion people around the world are sitting at their screens. The encyclopedias and novels are online, along with Horace, Cicero and the rest. Twitter will show you what’s been written in South America and Africa in the last five minutes. For commenting, transcluding and quoting, we have Facebook and many other thriving channels of commerce and communication (even blogs like this one). So what remains to be invented before we arrive in Nelson’s stately pleasure dome of Xanadu? Well, “automatic royalty” hasn’t shown up yet. More surprising—and more annoying—we still don’t have footnotes on the web.

It’s a worrisome lack. How are scholars to annotate and document—not to mention digress and distract—without footnotes or some similar device? In a recent essay Alexandra Horowitz cites Edward Gibbon, J. L. Austin, Nicholson Baker and David Foster Wallace as authors whose work would be diminished or even destroyed if stripped of notes. I would add Vladimir Nabokov to the list, for his novel-in-notes Pale Fire. Martin Gardner deserves mention as well—not for his columns in Scientific American, where footnotes and marginalia were sadly forbidden, but for his annotated editions of Lewis Carroll and others. And the most important example of all is the Talmud, the archetypal hypertext of modern times. We should be able to do stuff like that that in HTML!

Why are footnotes not a standard feature of web life? Perhaps because the founders believed that the central mechanism of the web—the anchor tag <a href= … >—adequately served the purpose. And people do use <a> tags for notes. For example, there’s the Wikipedia protocol, where clicking on a footnote link^[1] sends you on a trip to the bottom of the page, where you’ll find a helpful caret to take you back where you came from. This scheme does a good job of mimicking the ink-on-paper experience of footnotes—and ignores all the capabilities and possibilities of a new medium.

Back in 1995, the HTML 3.0 proposal included a <fn> tag for footnotes. But HTML 3.0 was stillborn, and the 3.2 version that replaced it a few months later dropped footnote support (and much else). HTML5 now offers the <aside> tag, which sounds like it ought to be the semantically correct way to mark up footnotes. But I have yet to see any website in the wild actually using <aside> that way. And the (still tentative) HTML5 standard suggests that footnotes were not the the original intent of the tag:

The aside element … can be used for typographical effects like pull quotes or sidebars, for advertising, for groups of nav elements, and for other content that is considered separate from the main content of the page.

It’s not appropriate to use the aside element just for parentheticals, since those are part of the main flow of the document.

Yeah, whatever. But what makes the web such a grand playground is that you can always build your own tools and toys if you don’t like the standard kit. Which brings me to all those blue links with dotted underscores in the paragraphs above. I assume you’ve tried them out by now. The device is called a knowl, and I discovered it the other day while browsing on the home page of the American Institute of Mathematics in Palo Alto. The knowl’s inventor is Harald Schilly of the University of Vienna.

It’s all done with a dab of jQuery and a dollop of CSS. The markup in the HTML file is just a mutant anchor tag:

<a knowl="wikitag.html">Wikipedia protocol</a>

where the normal “href” has been replaced by “knowl.” The jQuery code installs an onClick handler for each instance of this structure found in the text; the onClick function calls out to the server, loads the content of the note, and adds that text to the document tree as a sibling of the current node. CSS rules add a bit of border styling. The little drawer-like pane opens just below the current paragraph (or whatever other HTML element contains the reference to the knowl).

The knowl is not quite everything I would wish for in a footnote utility. A minor issue is that the “next-sibling” rule for placing the text of the knowl doesn’t always do the right thing. A less-minor issue is that the authoring process is overly arduous. Every knowl goes into a separate file, so writing the text requires a change of mental focus and also creates a lot of file-system clutter. I’d rather include the text of the note at the point of reference (the way it’s done in LaTeX, say). That could be accomplished with an easy change to the JavaScript. On the other hand, the system’s reliance on JavaScript is in itself problematic. The world of knowls is off-limits to those who write on hosted platforms such as WordPress.com or Blogger, because they forbid JavaScript in posts. I wonder if the same visual effects could be achieved entirely with CSS3 animations?

When Schilly and his colleagues at AIM developed the knowl, their goal was not to satisfy my footnote fetish. As a matter of fact, they seem to have a rather different vision of how knowls might be used—not as a medium for the Shandean digressions of self-indulgent writers like me but as shared nuggets of wisdom, offered as a public resource. David Farmer, director of programs at AIM, writes: “I envision a time when the Internet has a repository of such knowls, reliable and ready to be referenced anywhere.”

Unfortunately, there’s a technical impediment to making that vision a reality. When I started writing this post, I thought it would be only appropriate to transclude the definition of transclusion that’s given in one of the knowls above. So I constructed a knowl linking to the file on aimath.org where that text exists. This knowl has such a link. If you click it, you’ll find that it doesn’t work: The little blue drawer slides open, but it is empty. The reason is that the page you are reading now was downloaded from bit-player.org, but when you click that knowl, it tries to access HTML content from aimath.org; that attempt runs afoul of the browser’s “same-origin policy.” There are ways of evading this security provision, but they come with a faint scent of hackery. Without them, though, I don’t think we can have our public repository of knowls. It looks like we’ll each have to serve up our own wit and drollery.

Update 2012-02-28: Harald Schilly has shown me that transclusion is not a vain dream after all. The solution relies on a fairly recent technology called Access Control for Cross-Site Requests, and it requires a cooperating server to set an appropriate flag in an HTTP header. This knowl is fetched from appspot.com, the hosting arm of the Google App Engine, which allows cross-site connections from anywhere. If you are reading this page with a recent Webkit browser (Google Chrome, Safari) or a recent Mozilla browser (Firebox), the magic drawer should open with a note inside. But Opera does not implement the method, and I think Internet Explorer is also a holdout, although I don’t have the means to check. I was totally unaware of this trick, and I’m grateful to Schilly for enlightening me.

^ Hi! I’m a Wikipedia-style footnote. I feel lonely and exposed and painfully out of context down here.

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.

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.

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.

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 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.

Slide behind the wheel of this dreamboat. Push the electronic control button. Then sit back and let transistors take over.

There’s something curiously tentative about this vision of the future of motoring, as seen from 1964. You’re invited to push the button and let the transistors take over. But you’ve still got your hands on the wheel; apparently you’re still responsible for driving the dreamboat.

Other early discussions of automatic automobiles are also fuzzy about exactly who or what is in charge. A notable example is the General Motors Futurama exhibit at the 1939 Worlds Fair in New York. “Safe distance between cars is maintained by automatic radio control,” intones the narrator, above creepy organ music. This certainly suggests something other than seat-of-the-pants driving. But the next sentence narrows the scope of that automatic control: “Curved sides assist the driver in keeping his car within the proper lane under all circumstances.” Thus the technology is merely assistive, not autonomous. And what’s that about “curved sides”? Norman Bel Geddes, the designer of the exhibit, explains all in Magic Motorways, published in 1940. It’s very low-tech. Freeway lanes are to be separated by high curbs of concave cross-section, which deflect a straying car back into its lane. (Later in the book Bel Geddes also discusses more elaborate guidance systems, involving buried conductors.)

The reprise of Futurama at the 1964 World’s Fair—an exhibit that I attended, along with 29 million other people—was even vaguer about the question of autonomous vehicles. We saw lots of miniature automobiles moving in close order along gleaming freeways, and personally I came away with the impression that all those vehicles were under computer control. But the transcript of the narration includes only a single sentence on the topic, and it’s open to almost any interpretation: “Vehicles electronically paced, travel routes remarkably safe, swift and efficient.”

Why so coy about the prospect of cars that would drive themselves without human intervention? Maybe the concept was just too outlandish for credibility, particularly in 1939. Or maybe GM recognized that their natural audience is made up of car enthusiasts, who want to drive their dreamboats, not just be carried along as electronically paced, radio-controlled passengers.

In any case, the coyness has now evaporated, and these days everybody is talking about truly autonomous vehicles. DARPA runs contests for them; an Italian group has driven them across Europe and Asia; Google has a “secret” fleet of them. And I too am talking about autonomous vehicles: “Leave the Driving to It” is my latest American Scientist column.

Note: The artwork above is from an RCA advertisement in the September 1964 issue of Scientific American. Stylistically, the painting owes something to the Futurama exhibits, but I’d like to make a wild guess that the (uncredited) artist who created this rendering lived in Minneapolis. That brightly lighted, colonnaded building to the right of center looks to me very much like a building at Hennepin and Washington (now owned by ING) that was completed in 1964, just as this ad appeared. The architect was Minoru Yamasaki, the designer of the World Trade Center.