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.
Thank you for this wonderful birthday present, and indeed for the cleverest touch (of misspelling my own middle name). Best regards, don