a story lives forever
Sign in
Form submission failed!

Stay signed in

Recover your password?
Form submission failed!

Web of Stories Ltd would like to keep you informed about our products and services.

Please tick here if you would like us to keep you informed about our products and services.

I have read and accepted the Terms & Conditions.

Please note: Your email and any private information provided at registration will not be passed on to other individuals or organisations without your specific approval.

Video URL

You must be registered to use this feature. Sign in or register.


Inception of The Art of Computer Programming


Finding a solution to an open problem about projective planes
Donald Knuth Scientist
Comments (0) Please sign in or register to add comments

Another open problem had been mentioned in one of my classes, having to do with… with projective planes – a finite kind of geometry – and… and the projective planes of… of… one of the things Marshall Hall was good at was studying projective planes, and he had… had developed some of the major theories of it during the Second World War. These… these have lots of applications in… 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… so… for… 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… of that size, basically, that… that… it was a question whether there was only… that projective plane was unique, or were there… or were there other kind of geometries with this… with this size? And I… the first open case was of… was of size 32. And I took a look at… at it, and… 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… of all of this… of the projective planes of a certain kind, which I… I later called a… a semi-field. And… and he had… he had two lists, and both of the lists had… had 16 solutions on it. And the… the thing was, so… 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… was the one that had been known for years and years. So I… so I thought to myself, oh, all I have to do is find a… a pattern, a rule that would take every one on the first list, and… and find its corresponding mate on the second list, and then I will have a rule that I can take on and… and solve the next problem, 64, the next… 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… 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… 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… a little bit, I… I found… found a connection, and by noon I had… I had a theorem that had… 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… you don't have to wait and do, you know, do this other hard problem, just… just do this for your thesis. So I felt a little guilty of solving my PhD thesis problem in 2 hours and… and so I… I added, you know, I spent another… another few months refining the result and adding on some… some related theory. But basically I could write a thesis of about 70 pages, and… and that… and that solved the problem that… that was considered by… by people in this very small sub group of the world, who were… 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… and it gave me a thesis.
Now… now, I… in order to graduate, I also… you know, Caltech had other requirements that I had to fill… fulfil too, but… 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… I know Freeman Dyson is interviewed in this series of Peoples Archive [sic], and he's become a good friend since then, but I… 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.

Born in 1938, American computing pioneer Donald Knuth 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 humor.

Listeners: Dikran Karagueuzian

Trained as a journalist, Dikran Karagueuzian is the director of CSLI Publications, publisher of seven books by Donald Knuth. He has known Knuth since the late seventies when Knuth was developing TeX and Metafont, the typesetting and type designing computer programs, respectively.

Tags: WWII, Princeton University, Olga Todd, California Institute of Technology, Marshall Hall, RJ Walker, Freeman Dyson

Duration: 5 minutes, 41 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008