Opinion 86: For God So Loved the World, that He gave [one of his most talented] begotten Sons, that Whoever Masters His Art of Computer-Programming Shall Not Perish and Crash, but have Everlastingly Bug-Free (yet with short-lasting running times) Programs

By Doron Zeilberger

Written: Jan. 10, 2008.

Dedicated to Donald Erwin Knuth (b. January tenth, 1938) on his 1001000100Zeck.'s Birthday

Another title could have been: "Blessed are the meek constants-and their lovers- for they shall inherit mathematics".

One of the greatest giants of our time is turning 70 today. The Newton, Diderot, and Guttenberg of our own computer-age. What makes him even a greater giant is that, according to streotype, he does not fit the image of the creative genius at all. Creative geniuses do not care about such trifling details as constants and spelling out middle names. They only care about the big picture.

We all know of Don's obsession with completeness, or as he modestly says "at least the appearance of completeness". Let me quote from Dennis Shasha and Cathy Lazere's book "Out of Their Minds", that in the chapter dedicated to Don, says:

When other computer scientists might be satisfied to say that an algorithm takes time proportional to the square of the input, Knuth would prove that it takes exactly 3.65 times the square of the input".
Even this is an understatement. Knuth would replace the 3.65 by 3.652643454353... and even more digits. Contrast this with the ruling paradigm in computational complexity theory, with its POL vs. EXP dichotomy, implicitly implying that "polynomial time" is "feasible". Nonsense, even with small exponents, if the constant is huge, then such a "feasible" algorithm is not very practical, for example the Seymour-Robertson-Thomas excluded minors algorithms.

So Knuth is very right to worry about constants. And he gets his hands dirty and does the coding all by himself, and he gave us such great programs as TeX, and its fully-detailed manuals. He taught us by example the art of computer programming, and he modestly claims that it is art in the sense of the artisan rather than that of the artist. But his perfect artisanship became the most refined of fine arts.

What Birthday present can one give to the guru who has everything?. I thought of surprising him by researching the few remaining middle names in the indexes of ACP and Concrete Math, that are left with only the middle initial. But, this plan came to nothing.

But even more than middle names, Knuth loves constants. So I am currently working on a complete Maple implementation of the Birkhoff-Trijinkski method for finding asymptotics of solutions of linear recurrence equations with polynomial coefficients, exposited in an article that Jet Wimp and I wrote back in 1985. The drawback of that method is that it can't find the constant in front. But, hopefully, the asymptotics that I would be able to get would be so good, so as to enable one to empirically find it to great accuracy, and then using either L3 of Ferguson, one would be able to guess the value in terms of π and e. In particular, one should be able to get the asymptotics, to any desired order, using this method, for the number of involutions, that was so beautifully described, using another method (Laplace's) at the end of 5.1.4 (ACP III). I will link to it from here, as soon as I finish it.
[Added April 6, 2008: I just finished it. Here is the article and the program . ]

In the above-mentioned Shasha-Lazere book, Knuth modestly says about himself:

"Some scientists are like explorers who go out and plant the flag in new territory; others irrigate and fertilize the land and give it laws and structure."

Without the laws and structure, the new flags won't do much good, and besides, Knuth's role model and life-time achievements constitute one of the most significant flag-planting of our time.

Happy Birthday, Don, and may you never finish your seven volumes, since this will guarantee that you will live for ever, or at least, for many decades to come.

I'd like to thank Jeff Shallit who has asked me, and quite a few other people, to sing Knuth's praise, on his 70th birthday, today, Jan. 10, 2008.
Added Jan. 23, 2008: Since Don Knuth famously does not use Email, I printed this page (and its appendix) and snail-mailed it, on Jan. 3, 2008, to him with the warning "dated material", "open on Jan. 10", on the enevelope. Don returned it with hand-written annotations and at the end wrote:
Thank you for this wonderful birthday present, and indeed for the cleverest touch (of misspelling my own middle name). Best regards, don

[if you didn't notice, Don's middle name is Ervin, not Erwin]
Opinions of Doron Zeilberger