Look Who it Was Random video

Donald Knuth - Finding a solution to an open problem about projective planes (32/97)

2,502 views · Published 18 February 2016 · 5:41 · Indexed 29 October 2026

Channel: Web of Stories - Life Stories of Remarkable People · 2016 · Science & Technology

Watch on YouTube

To listen to more of Donald Knuth’s stories, go to the playlist: https://www.youtube.com/playlist?list=PLVV0r6CmEsFzeNLngr1JqyQki3wdoGrCn

Donald Knuth (b. 1938), American computing pioneer, is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humour. [Listener: Dikran Karagueuzian; date recorded: 2006]

TRANSCRIPT: Another open problem had been mentioned in one of my classes, having to do with projective planes – a finite kind of geometry – and the projective planes of one of the things Marshall Hall was good at was studying projective planes, and he had developed some of the major theories of it during the Second World War. These have lots of applications in code-breaking as well, and other… and kinds of code making from, you know, transmitting reliable codes. And I took his class on projective planes, and… and one of the things he mentioned is that no… that only one projective plane of order 32 is known, and only one is known of order 64, and so for whenever you had a power of two – two to the… two times two times two times two times two – and you'd… one of the projective plane of that size, basically, that… it was a question whether there was only… that projective plane was unique, or were there other kind of geometries with this size? And I… the first open case was of size 32. And I took a look at it, and I received in the mail, a result of a computer program that had been written by RJ Walker (I think he was in Princeton), and he had found all of the… and he had actually found new ones of size 32, by computer.  And… and he… he… and he had a list on this… of all of this… of the projective planes of a certain kind, which I later called a… a semi-field. And he had two lists, and both of the lists had 16 solutions on it. And the thing was, so this gave him 32 different projective planes of a size 32, 16 of them were of one kind and 16 of them were of another kind, and that's all the computer… his computer program found. But one of the 16 in the second list was the one that had been known for years and years. So I thought to myself, oh, all I have to do is find a pattern, a rule that would take every one on the first list, and find its corresponding mate on the second list, and then I will have a rule that I can take on and solve the next problem, 64, the next problem 128, and so on, because my rule that worked in the case of 32 would then be a general rule if I could find this pattern. And so I had gotten this list from him, it was in my mail at nine o'clock in the morning, and I remember riding up in the elevator with Professor Olga Todd, who was one of our… my professors, and I said, Mrs Todd, I think I'm going to have a theorem in 2 hours. I'm going to find a way to match these 16 with these 16. And well… and I just had a hunch that it was possible, and sure enough, you know, staring at it a little bit, I found a connection, and by noon I had a theorem that had solved many, many cases of this open problem about projective planes. I showed it to Marshall Hall, and he said, ‘Well Don, this is your thesis. Write this up and get out of here.’ You know, you don't have to wait and do, you know, do this other hard problem, just do this for your thesis. So I felt a little guilty of solving my PhD thesis problem in 2 hours and so I added, you know, I spent another few months refining the result and adding on some related theory. But basically I could write a thesis of about 70 pages, and that solved the problem that was considered by people in this very small sub group of the world, who were projective planologists, the finite projective plane people, that this was one of the problems that they had thought might never be solved. So I had… so that was nice. And it gave me a thesis.
 
Now, I… in order to graduate, I also… you know, Caltech had other requirements that I had to fill… fulfil too, but one of them, interestingly, had… was that you choose some other classic problem of mathematics, and you see… and you prepare for a month… read up on it, everything you can, and see if you can say something new about the problem.  And the problem that I studied was what's called the Thue-Siegel-Roth Theorem, in which Freeman Dyson had made one of the main contributions.  And I mention that just because I know Freeman Dyson is interviewed in this series of Peoples Archive [sic], and he's become a good friend since then, but I read his papers on the subject, when I was a grad student preparing for… I think he had recently… I think he graduated about 10 years before I did.

More from this channel