Donald Knuth’s Christmas Tree Lecture Tackles a ‘Curious Problem’ in Combinatorial Geometry – InApps 2022

Photo courtesy of Wikipedia.

In 1962, 24-year-old Donald Knuth started writing “The Art of Computer Programming“ — and he’s still working on it. Revered among programmers, the book is “widely considered to be among the best scientific writings of the century,” according to one web page at Stanford (where Knuth is a professor emeritus).

And it’s one more example of how one man’s commitment to his craft can leave a tangible legacy of materials for others to build on.

Here’s how one Stanford web page summarizes Knuth’s legacy. “Literate programming, attributed to Knuth, essentially holds that computer programs should be developed with an eye toward human comprehension more than computer readability. He maintains that the very act of communicating one’s work clearly to other people will improve the work itself.” The frequently-asked-questions section of Knuth’s personal site even explains that “I retired early because I realized that I would need about 20 years of full-time work to complete “The Art of Computer Programming,” which I have always viewed as the most important project of my life…

“My full-time writing schedule means that I have to be pretty much a hermit…”

And yet last week, at the age of 79, he emerged to give a new “Christmas Tree” lecture at Stanford. It’s an annual tradition, which Knuth lays out on his “Computer Musings” blog.

”No tuition is charged, no attendance is taken, no credit is given. Each talk is independent of the others, and pitched at an audience of non-specialists… I try to minimize the jargon and complications by stressing the motivation and the paradigms and the high-level picture, without sweeping the details entirely under the rug.”

Or, as the i-Programmer site describes it, “It is a well established Stanford University tradition that in December Donald Knuth puts on a flamboyant jumper, and delivers a public lecture that, if at all possible, features a tree structure of some sort or another.”

For some, it was like visiting a favorite relative over the holidays. And it was also a chance to see a great mind in action.

The lecture’s announcement described it as “a curious problem in combinatorial geometry.” But it also offered a glimpse into the life of a ground-breaking mathematician — and how much delight he feels for his subject. “It’s also always fun when I have a good story to tell.” Knuth begins.

His lecture’s title was “A Conjecture That Had to Be True,” but he also shared an enthusiastic subtitle. “Why is it so much fun to do research.” He began with an example that occurred to him in April — one that’s headed for an upcoming update to “The Art of Computer Programming.” This year he’s writing about a data structure called “dancing links,” and he’s extended it to a math problem from the world of art.

Mondrian paintings were famous for having rectangles inside of rectangles — “a pattern, of course, that people have been working on long before Mondrian.” But is there a pattern to the rectangles within rectangles?

Knuth explains that people think mathematicians have already solved every problem, but “they keep coming up, several times a year. This is an example.” He dives right in, trying to shrink a pattern of rectangles-within-rectangles into numbers. (“I’m an integer-oriented person, so I want to convert this into something I understand better.”)

Creating what he calls a “reduced pattern,” Knuth draws a grid where each coordinate represents where imaginary lines are intersected by at least one of the corners of a rectangle.

After scribbling out a “reduced pattern” diagram, finally creating a very rough grid, he extracts another warm laugh from the audience when he says sincerely, “Well actually, just look at the book.” Then points a finger to a perfectly drawn diagram on the page. “So, here it is.”

But what’s the minimum number of rectangles within rectangles? He warns this is a little tricky, because “There are lots of wrong ways to get the answer.” (The correct answer is n + n -1, “So in this case, seven. Three plus five minus one.”) He dubs this an example of “tightly-paved” rectangles — tight because it’s hitting the lower limit for the number of possible rectangles (while still using every vertical and horizontal line in the grid at least once).

He’s on the verge of teaching his audience something incredibly useful — but first, he’s going to make them laugh. “Now everybody knows that the internet is a wonderful resource for finding out about any subject — so I looked up ‘tight paving’ with Google, and here’s what it showed me.” He pulls up images of construction sites.

“In other words, I knew nobody else had used ‘tight paving’ for a mathematical discussion.” The audience laughs again.

But now the revelation. “For the last 30 years or more, there has been a wonderful tool for all kinds of problems of this form, and it’s been online for a long time.” He introduces the audience to The On-Line Encyclopedia of Integer Sequences (a site so old, the word “online” was still hyphenated.) “And this is just the nicest thing since sliced bread for mathematics, because you compute your way into the literature. If you want to know if anybody else has ever studied a problem, all you have to do is evaluate the first few cases of it, and then you look it up, and there it is.”

But there’s more to the story. “Not only is this a great resource, but the thing is well curated. I mean, within a day I had seven people commenting on it and, you know, improving my presentation and checking everything. So OEIS is just fantastic.” And that’s important because his entry at OEIS says there is “a simple generating function, and a simple closed form” to produce the sequence of integers — but since he’d submitted that as a problem to American Math Monthly, asking readers to calculate the correct solution, it would only be revealed after the magazine had published the solution. Knuth points out there’s a great irony.

“The way they published it, it sounds as though I was able to solve this problem.”

Knuth had identified “this beautiful pattern” that was true for smaller grids of rectangles within rectangles — but was that enough? “There was a happy ending to the story,” he says, “because Walter Stromquist was the referee of this problem, and the editor liked it so much that he even told me the referee’s name, and got me in correspondence with Walter Stromquist” — and fortunatey, Stromquist had found a proof.

But there’s a larger lesson there for us all…

Knuth shares a fascinating story about 19th-century mathematician (and pastor) Thomas Penyngton Kirkman, best known for the Kirkman Schoolgirl Problem. Kirkman had also worked on a mathematical phenomenon known as “triple systems,” and a funny thing happened when Knuth looked at one of the mathematican’s papers. It generalized the triple systems with formulas “which he claims are true. But when I looked what his reasoning was — why it was true — it was basically that God wouldn’t want the formula to be any more complicated than mine.”

“So he hadn’t really proved his formula… He just sort of said that it had to be true. Because it was too hard to believe that it could be false.”

And this happens more often than you’d think. Knuth remembers a time he’d analyzed factoring algorithms, determining to the 20th decimal place the average size of a random number’s largest factors. He’d found a published solution, “But it disagreed in the 16th decimal. And so here I had a very natural mathematical problem, and it agreed with a very natural mathematical expression — up to 16 decimals, and then it failed.

For a week he probed the mathematical mystery without identifying where the discrepancy was coming from. “Finally it turned out that my program was right, but I had used a formula for numerical integration that’s only correct if the fourth derivative of the function you’re integrating is continuous. And this particular function had a discontinuous fourth derivative.”

Then he shrugs his shoulders in a “whaddya gonna do” gesture — and the audience laughs sympathetically.

“Now another time, I was analyzing the binary Euclidian algorithm…”

Actually, this is a story about another mathematician’s analysis, but it builds up to the same lesson. “Just because you have agreement to a lot of places doesn’t mean that the conjecture has to be true. I’ve seen it go both ways.”

But his larger talk ends with one more lesson for his audience. “This is the way research goes. And when you do find a proof, then you’re really happy for a couple days.

“And of course, then the next day you find another problem.”

Donald Knuth’s blog recently announced that videotapes of past lectures are now being digitized and shared online. Happy Holidays!!