# Summer Reading in Theory

*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.

*Algebraic Graph Theory*, by Norman Biggs. A wonderful book. First appeared in 1974.

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

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

*Elements of Number Theory*, by Ivan Vinogradov. Another small book that is loaded with ideas.

*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:

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

*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.

*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.

* 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*.

*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?

It is hard to say: As a high school student I really liked the Hebrew book “Mavo Lematematika” (Introduction to mathematics מבוא למתמטיקה) and also as a student I liked the Hebrew text books in Calculus (Meisler) Algebra (Levitzki)… .(Reading Hebrew was easier for me, and these are truly excellent books.) Also I like short book so for long book in my list I probably read only small parts. So here are books that influenced me as a grad student. (I think I was more influenced by papers and even more by things explained to me in lectures or privately.)

1) Eggelston: Convexity

2) Stanley: Combonatorics and commutative algebra

3) Lovasz and Plummer: Mathching theory

4) Yaglom and Yaglom: challenging mathematical problems with elementary solutions

5) Knuth: The art of computer programming (mainly the parts about tree enumeration and about the combinatorics of sorting)

If books that are collections of (mainly survey) papers are legal than I’d include Rota: studies in combinatorics and the AMS books on convexity and relations between combinatorics and other areas of mathematics. (re: 5 I hesitated between Knuth’s book and Moon’s short book counting labelled trees.)

(I also liked Biggs’ algebraic graph theory. A little later I liked Bollobas’ extremal graph theory.)

Yehezkel-Edmund Landau. 1929. Foundations of Analysis. 1951. Translation into English by F. Steinhardt of the German-language book Grundlagen Der Analysis by Edund Landau. 2nd Edn. 1960. Chelsea Publishing Company, New York.

Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton.

The first edition of Feller’s book on probability asserted that pairwise independence implied independence at all orders. It was fixed in the next edition. Longer story there, obviously.

A question about Feller’s book- usually later books are better since authors know better how to present material, and sometimes more math has been done to make earlier math more clear. So while you personally like Feller’s book, would you recommend a more modern source?

For Hardy and Wright, which I have read, I agree it holds up very well and I would recommend it. Glad to know its been updated.

Books on my list:

Hardy and Wright Number Theory

Godel Escher Bach I read at just the right time- I knew enough math to appreciate it, but not so much as to think it was trivial (by the way— its not trivial).

Anything by Martin Gardner

Soare’s book on r.e. Recursion Theory. Best book on the subject. Relevance to CS theory is less than it used to be (might be 0), but I still like it.

Proofs from the book- really great proofs!

The Code-breakers by Kahn. I read the edition that didn’t have anything on Public Key but it makes you realize what a breakthrough public key is.

Ramsey Theory by Graham, Rothchild, Spencer. Great to have the basics of Ramsey theory and also some advanced material all in one place. You can tell the authors loved their subject.

People, Problems, and Proofs by Lipton-Regan.

Problems with a Point by Gasarch

Both are excellent books-based-on-blogs which really expand the posts and fill in details. My opinion on the Gasarch book may be biased.

Given that mathos are taught to be professionally perverse, I’d still recommend ‘Counterexamples in Analysis’. Historically, Herstein’s Algebra was my first and most-loved book and Feller’s Probability is the only book of mine that’s lost its front cover through use. Lakatos’ Proofs and Refutations is in its own league.

Littlewood’s Miscellany. Snippets collected by the great Cambridge mathematician over a lifetime. He never talks down to you, and you have to work at some of the examples.

Tim Gowers (ed.), The Princeton Companion to Mathematics. Open it anywhere and read yourself into a new subject. More than just mathematics, too.

John Conway and Richard Guy, The Book of Numbers. The first chapter is called “The Romance of Numbers”, which is just what it is.

Martin Aigner and Günter Ziegler, Proofs from The Book. A delightful miscellany of the best possible proofs of a wide variety of theorems.

Loren Graham and Jean-Michel Kantor, Naming Infinity. The story of the Lusitania group at Moscow State University, led by Egorov and Lusin. This is a story of mathematical adventure, mysticism, loyalty, and great suffering.

Dear Peter Cameron:

Love your choices. Littlewood is wonderful and so is the Naming Infinity. The rest are great too. Great choices.

Best

Dick

Martin Gardner’s books, and later Ian Stewart’s

Concepts of Modern MathematicsP=NP shown in Advances in Combinatorial Optimization:Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems

By Diaby Moustapha, Karwan Mark H. Reading?

Dear L:

Can I call you l? The book you cite is the one that presents their claimed proof that P=NP. Is hat right? Ken and I have talked with them in the past. We tried to understand their claim, but cannot follow it fully. Have you studied it?

Best

Dick

Though it is very clear P=NP this proof is bogus.

Though it is very clear P=NP would you have any reason to believe why deciding 3SAT should definitely be in superlinear time?

Dear L:

I may doubt that SAT could not be in P, but I really do not doubt it cannot be done fast. This is the rationale behind the super-linear claim. Of course there is ZERO evidence to back this up.

Best

Dick

I think your rationale is for ‘self-reduction’ to witness and not for ‘Yes or No’.