Summer Reading in Theory

Gödel’s Lost Letter and P=NP 2019-08-20

Some formative books in mathematics and computing theory

LSE source: “Calculus on Clay?”

Norman Biggs is the author of the wonderful book Algebraic Graph Theory. Both Ken and I read it long ago, and both of us have it out now because of its relevance to Hao Huang’s beautiful short proof of the Boolean Sensitivity Conjecture.

Today we wish to ask, What are your top five favorite books on mathematics and theory for summer reading?

There’s an aporia in that question. A working definition of aporia is: “a self-contradiction that isn’t.” The point is that books for summer reading should be new, so how would you already know which are your favorites? Well, we are thinking of books that are so rich you can always find new things in them—and that also played formative roles earlier in our careers.

Ken knew Biggs during his first year at Oxford when Biggs was visiting there from London. He took part in a weekly sitting-room seminar organized by Peter Neumann. Biggs’s book was a central reference for Ken’s undergraduate senior thesis at Princeton, and both he and Ken presented material based on it.

Best Five Books—Dick

Here are my votes for all-time best books in mathematics and in computer science theory.

${\bullet }$ Algebraic Graph Theory, by Norman Biggs. A wonderful book. First appeared in 1974.

${\bullet }$ An Introduction to Probability Theory and Its Applications, Vol. 1, by William Feller. This is the book I used to learn probability theory.

${\bullet }$ An Introduction to the Theory of Numbers, by Godfrey Hardy and Edward Wright. Now updated by Andrew Wiles, Roger Heath-Brown, and Joseph Silverman.

${\bullet }$ Elements of Number Theory, by Ivan Vinogradov. Another small book that is loaded with ideas.

${\bullet }$ The Art of Counting, by Paul Erdős and Joel Spencer. This book changed my life. Today the book is of course The Probabilistic Method, by Noga Alon and Joel Spencer.

Best Five Books—Ken

Ken reaches back to his teen years but it’s still the same span of years as my list. Here he tells it:

${\bullet}$ All books by Martin Gardner—in particular, the books of collections of his “Mathematical Games” columns in Scientific American. Here is an overview.

${\bullet}$ Scarne on Dice and Scarne on Cards. Originally it was neither of these books—nor John Scarne’s Complete Guide to Gambling—but a different book on in which both Scarne and Gardner figured prominently. Alas I, Ken, cannot trace it. That’s what I used to learn probability theory.

${\bullet}$ Spectra of Graphs, by Dragoš Cvetković, Michael Doob, and Horst Sachs. I could put Biggs’s book here, but this is the one that got me on to the whole subject just before my senior year at Princeton. It was fresh out in 1980—I recall the tactile sensation of the dark green spanking new cover in the Fine Hall Library’s copy. A great book with pictures and algebra.

${\bullet}$ Ideals, Varieties, and Algorithms, by David Cox, John Little, and Donal O’Shea. Fast forward to 1997. Having realized that techniques from algebraic geometry could surmount the “Natural Proofs” barrier (see also GCT), I went whole-hog after it. See “Manic Monomials” in this post for one thing that tripped it up. The book remains incredibly stimulating. It has a sequel, Using Algebraic Geometry.

${\bullet}$ Quantum Computation and Quantum Information by Michael Nielsen and Isaac Chuang. As with Hardy and Wright, it has its own Wikipedia page. Dick and I can say this is nominating a competitor, but Chaung & Nielsen is really in a class by itself for the sheer richness and writing style. One odd mark of its influence: In 2006 when I reacted to the sensational and frightening accusations of cheating at the world championship match, my first thought was to apply distributional distance measures of the kind used in its later chapters. Among such measures is (quantum) fidelity, and although I focused more on Jensen-Shannon divergence before deciding on simpler stuff, my chess research website retains “fidelity” in its name as part of a multi-way reference to FIDE, faith, and playing in good faith.

Open Problems

What books most influenced you? What are your votes for the best books that might influence others?