Forgive me if this story is slightly stale. I meant to write it two weeks ago, but for some reason I kept putting it off.

A paper titled “Scheduling Algorithms for Procrastinators” has been posted on the computer-science section of the arXiv. The authors are Michael A. Bender (Stony Brook University), Raphaël Clifford (University of Bristol) and Kostas Tsichlas (University of Patras). They confess that they got a late start on writing the article, and they finished at the last minute.

Their theme brings to mind another well-known paper: “The Effects of Moore’s Law and Slacking on Large Computations,” by Chris Gottbrath, Jeremy Bailin, Casey Meakin, Todd Thompson and J. J. Charfman (all of the University of Arizona). Gottbrath et al. considered the options that you face when you are about to begin a long-running computational project. Suppose the job would take three years of continuous work on the best computer available today. The obvious, no-nonsense approach to the problem is to get to work immediately with a state-of-the-art machine, and finish three years hence. But Moore’s Law—the widely noted observation that computer performance doubles every 18 months—suggests an alternative. You could go to the beach for a year and a half; then, returning with an enviable tan, you could buy a machine twice as fast as anything on the market now, so that you would still finish after a total of three years.

Bender, Clifford and Tsichlas consider a slightly different and more-general class of tasks—not necessarily computations—whose shared trait is that the rate of progress toward a conclusion is nonconstant; instead, the pace of work accelerates as a deadline approaches. This is a familiar phenomenon, at least for the dawdlers among us; personally, I find that my productivity gets a big boost on the night before a major project is due, especially if the penalty for missing the deadline is being flunked or fired. Bender and his colleagues focus on tasks with a simple linear speed law, where the rate of work increases steadily as the deadline nears. In particular, they assume that the initial speed is zero and the acceleration is constant until the job is done.

Given a set of such tasks, each with its own start time, deadline and linear speed function, can we find an optimum schedule? The answer is a curiously qualified maybe. If there is a feasible schedule (one where all tasks are completed on time), then there’s an algorithm for finding an optimal schedule (one where the total processing time is minimal). The trouble is, deciding whether or not a feasible schedule exists looks to be a hard problem. No known algorithm can settle the question in polynomial time, and it hasn’t even been established that the problem is in the class NP (nondeterministic polynomial time). For a problem in NP, you may or not be able to find a solution efficiently, but if a candidate solution is dropped in your lap, you can quickly test its correctness; even this limited ability is not guaranteed for the procrastinating scheduler (or the scheduling procrastinator). The root of the difficulty comes from an unexpected quarter. It’s a matter of numerical computation: Scheduled procrastination is hard because evaluating sums of square roots is hard. (Quick: Which is larger, √7 + √26 or √10 + √21?)

There’s more on the sums-of-square-roots problem at The Open Problems Project. For more on how the square-root problem relates to procrastination, see the paper by Bender, Clifford and Tsichlas.

As for me, I’ve got to run; I have a pressing deadline.

Three readers (so far) have called my attention to errors in “The Semicolon Wars,” my latest American Scientist column.

First, I referred to the programming languages ML, Haskell and Miranda as “pure” functional languages. ML doesn’t belong in that group. Although it is a language that has deep roots in the functional-programming community, ML allows assignment statements that produce side effects, violating any reasonable standard of functional “purity.”

Second, one of the example Lua programs given in the illustration on page 302 is hopelessly confused. As published, the program reads:

function factI (n)
  local accumulator = 1
  for i = 1,n do
    accum = accumulator*i
  end
  return accum
end

The definition should be:

function factI (n)
  local accumulator = 1
  for i = 1,n do
    accumulator = accumulator*i
  end
  return accumulator
end

The story of this goof may be worth telling, at least briefly. I would never trust myself to write even the smallest program correctly without testing the code. In this case I did confirm that the program compiled successfully and gave sensible-looking results, and then I did a copy-and-paste to get the text into the illustration. So what went wrong? In the tested version of the program I named the local variable “accum.” Later, I worried that this abbreviated form might be a bit cryptic to some readers, and so I decided to spell the word out in full. Surely I could make such a trivial change without retesting…?

Mea culpa. And thanks to David Hemmendinger, Steve Christensen and Kirsten Chevalier for their alert reading.

The July-August issue of American Scientist is just up on the Web. My Computing Science column in the new issue is a grumpy, ill-tempered diatribe about the overproliferation of programming languages—and about the grumpy and ill-tempered bickering between advocates of various languages, which often sounds to me like the posturing of TV wrestlers promoting their next slamfest. Do we really have to come to blows over Python vs. Perl?

Shortly after the issue went to press, I discovered a recent article that I wish I’d seen sooner, because it so perfectly captures the mood I was trying to convey. The article is by Niklaus Wirth, who has contributed his fair share of the world’s programming languages, including Pascal, the Modula series and Oberon. Wirth’s article, which appears in IEEE Computer (Vol. 39, No. 1, pp. 28–39, January 2006), bears the curious title “Good Ideas, through the Looking Glass.” I’m not sure exactly how to parse those words. Do good ideas, when seen in the mirror, become bad ideas? Depends on the mirror, I guess. For what it’s worth, most of the ideas on Wirth’s list—especially in the realm of programming languages—are things he considers mistakes. He mentions such classics as the goto statement and the dangling-else problem, and he mocks the terse syntax of C and its offspring: x+++++y+1==++x+++y.

Wirth does not spare himself—although some of his criticism is strangely third-personal. “Pascal’s designer,” writes Pascal’s designer, “retained the goto statement as well as the if statement without a closing end symbol. Apparently, he lacked the courage to break with convention and made wrong concessions to traditionalists. But that was in 1968. By now, almost everybody understands the problem except for the designers of the latest commercial programming languages, such as C#.” Wow, he’s got ’em up against the turnbuckles in a hammerlock.

A few weeks ago I commented on the discovery of some curious precursors of Sudoku, drawn up in the 1950s as designs for agricultural experiments. Now even earlier antecedants of the puzzle have been discovered by Christian Boyer, a specialist in recreational mathematics. Writing in the French magazine Pour la Science, Boyer describes and reproduces several puzzles originally published in French newspapers and magazines in the 1890s. None of these puzzles is a genuine Sudoku, but the family resemblance is striking. Several of them have nine-by-nine grids to be filled in with numbers, and a few of the nine-by-nine grids are subdivided into three-by-three blocks.

Among the many near misses, Boyer cites the puzzle shown at right as the closest known approach to a pre-invention of the Sudoku. (Image source: Christian Boyer.)

It was composed by B. Meyniel and published on 6 July 1895 in the daily newspaper La France. The instructions present the problem as a magic square, to be filled with the numbers from 1 through 9 so that all rows, all columns and all diagonals have the same sum (namely, 45). The three-by-three subgrids familiar to Sudoku players are not mentioned in the instructions or distinguished in the diagram. Nevertheless, if you try to solve the puzzle as if it were a Sudoku, you’ll find that it works: Each number from 1 through 9 appears exactly once in each subgrid. Actually, there are two such Sudoku solutions. (Meyniel’s rules exclude one of these solutions by requiring a “diabolical” magic square, in which the broken diagonals also yield the magic sum.)

Boyer presents several more fin de siecle puzzles that are Sudoku-like in one way or another. The text of his article (but not the illustrations) is available online from Pour la Science, and a supplementary document with more details and newspaper clippings is at Boyer’s web site.

The ABC Evening News ended today’s broadcast with a riff on the date—06/06/06. We heard about a 6-pound, 6-ounce newborn, and a 66-year-old man celebrating his birthday. I’ve always been a little perplexed by this fascination with 666. The book that started it all (Revelation, or The Apocalypse of John) was written a full millennium before the Hindu-Arabic numeral “6″ appeared on the scene. The idea of place-value notation, which is essential if we want to give any meaning to “666,” was still centuries in the future. If we’re worried about ‘the number of the beast,” shouldn’t we be looking out for the dread sequence of symbols DCLXVI?

Well, can you? And can you prove it? Peter G. Doyle and John Horton Conway can. In a 35-page article posted to the arXiv last week they write:

In this paper we show that it is possible to divide by three. Specifically, we prove that for any sets A and B, if there is a one-to-one correspondence between 3 × A and 3 × B then there is a one-to-one correspondence between A and B. Here 3 denotes the standard three-element set {0, 1, 2} and × denotes Cartesian product.

They hasten to add that they were not the first to prove this result. The problem has a history. In 1901 Felix Bernstein solved the easier case of division by 2. “Bernstein also indicated how to extend his results to division by any finite n,” Doyle and Conway write, “but we are not aware of anyone other than Bernstein himself who ever claimed to understand this argument.” In 1922, Waclaw Sierpinski found a simpler proof for division by 2 but failed in his attempts to extend the method to division by 3. Then, four years later, Sierpinski’s student Adolf Lindenbaum announced that he had a proof of divisibility by 3, but he gave no details, and when Lindenbaum died in the mass murders at Paneriai in 1941, the proof was lost. Lindenbaum’s announcement was made in a paper written jointly with Alfred Tarski, who must have known Lindenbaum’s proof at the time, but he was unable to reconstruct it later; in 1949 Tarski came up with a different proof of his own. Doyle and Conway think that their proof is probably equivalent to the lost proof of Lindenbaum.

How can questions about dividing by 2 or 3 possibly be a subject of serious mathematical inquiry in the 21st century? Well, that’s what’s so wonderful about modern math. Earlier generations of mathematicians—going all the way back to Pythagoras and Euclid—could have solved such problems in an eyeblink, whereas deep thinkers today find them a daunting challenge. (We call this progress!)

To explain why division has gotten so much harder, I have to confess that I have neglected to mention an important condition: Doyle and Conway insist on a proof that does not rely on the axiom of choice (see also the official web site), a concept introduced into set theory in 1904 by Ernst Zermelo. If you accept the axiom of choice, you assume that from any collection of nonempty sets you can always choose one element from each set. This may seem like an innocent assumption, but some of its consequences are not so obvious, and it has remained mildly controversial throughout the past century. In any case, if you can get along without such an assumption, so much the better.

What does the axiom of choice have to do with division by 3? We usually think of division as a process in arithmetic, but the problem addressed by Doyle and Conway lies in the domain of set theory. They seek a one-to-one correspondence between the elements of two sets. For finite sets this kind of pairing operation is straightforward, and it can even be done readily enough for certain infinite sets—namely those whose elements can be “well ordered,” or arranged in a definite sequence. For example, the infinite set of natural numbers has the familiar ordering 1, 2, 3,…, and the rational numbers can be put in a sequence such as 1/1, 1/2, 2/1, 1/3, 3/1…. Do all sets have a well-ordering? It turns out that the answer is yes only if you admit the axiom of choice. And since Doyle and Conway want a proof whose validity is independent of this axiom, they must somehow show a one-to-one correspondence without first ordering the elements of the sets.

If you’d like to know how they do it, by all means read the paper! It is a remarkably lucid—and at times entertaining—example of mathematical writing.

According to Doyle, the paper was written in 1990 and has been available on Doyle’s web site since 1994, but until now it has never been more widely circulated. A footnote linked to the byline suggests why:

John Conway collaborated on the research reported here, and has been listed as an author of this work since it was first distributed in 1994. But he has never approved of this exposition, which he regards as full of ‘fluff’.

I’m a sucker for ‘fluff’.