Wednesday, January 16, 2008

Math books you can actually read

How many math books can you read cover-to-cover? How many have you? The problem is that while you can certainly read any discrete math (for ugrads) textbooks cover-to-cover you don't want to- you know most of it.

Computer Science Theory is better than math for this since the field is younger and the books often do not need as much background.

So, which books are just right- hard enough to have things in them of interest, but not so hard that you can't read them. Demanding you be able to read it `cover-to-cover' is rather demanding and also ambigous- do you need to understand everything? I'll define this to just be `read/understood over 90% of the book'

With that in mind, here are the books I've done that for. Its a short list.
  1. Recursively Enumerable Sets and Degrees by Soare. I had a course in 1980 (by Michael Stob- a PhD student of Soare) that covered about 1/2 of it (in preprint form). I understood about 3/4 of that course. But over the next 20 years I (slowly) read and understood the rest. By 2000 I had it all. I try to retain it by presenting a priority argument argument to someone once in a while. Its getting harder to find someone who wants to see these things who doesn't already know them. I did drag Steven Fenner into a room at CCC06 and forced him to see the proof that there is a minimal pair of r.e. degrees using a tree argument,
  2. Ramsey Theory by Graham, Rothchild, Spencer. I had about 1/3 of this in a course (by Spencer) in 1978. Over the next 30 years I've read more of it. Now I'm about done.
  3. Linear Orderings by Rosenstein. Great book, out of print now. Does lots of model theory (E-F games) and recursion theory in a more concrete setting.
  4. I've read several books by Brams and Taylor about fair division. All are readable. The nice things here is that the math is easy but probably new to most of us. Hardest theorem: there is an envy free discrete protocol to divide a cake between 4 people (or more).
  5. Communication Complexity by Kushilevitz and Nisan. Reviewed it and used it in a course twice. By the second time I had it all read.
  6. Proofs that really count by Benjamin and Quinn. This is about proofs of combinatorial identities done by showing that two expressions solve the same problem. Great topic, Great book.
So how about you- have you found many book that hit that sweet spot between too easy and too hard. And that are well written.


  1. Maybe this is too low level, but Dexter Kozen's Automata & Computability book is great. I had it as the textbook for my undergrad automata class, but since then I've often read it in my spare time; I think I've been through the whole book by now. It is very enjoyable.

  2. "Topics in Algebra" by Herstein
    "Mathematical Analysis" by Apostol

    You did say math books!

    -- Amit C

  3. Intro to algorithms by CLR (the first version. I haven't updated myself with the new CLRS)

  4. Although they might not qualify as "Math Books For People in this Group", but I've enjoyed Paul Nahin's books : 1) "When Least is Best" and 2) "Dueling Idiots & other Probability Puzzlers"

  5. "Cauchy Schwarz Master Class" by Steele is wonderful.

  6. Stasys Jukna's "Extremal Combinatorics with applications in Computer Science" is great.

    There are lots of excellent problems too.

  7. # Information theory, by Cover and Thomas
    # Randomized Algorithms (Motwani-Raghavan): it's an old book, but even when I read it today, I realize just how well it flows.
    # Convex Optimization (Boyd/Vandenberghe): there's just something about the typesetting :)
    # Computational Complexity (Arora/Barak)
    # Convex Analysis (Rockafellar): A model of precision and clarity
    # (almost, but not quite in the pantheon): Approximation algorithms, (Vazirani)

  8. Grunbaum "Convex Polytopes"

  9. Suresh - definitely a +1 on B&V and Rockefellar.

    Other's I think are real page turners.

    Nocedal and Wright's Numerical Optimization
    Trefethen and Bau's Numerical Linear Algebra
    Dennis and Schnabel Numerical Methods for Unconstrained optimziation

  10. What about Concrete Mathematics from Graham, Knuth, and Patashnik?

  11. Probabilistic method by Alon and Spencer

  12. linear programming by V. Chvatal is a really amazing first book for the topic and easily readable cover to cover.

  13. You consider a book readable if you can get through it in 20-30 years? Odd...

    It's also interesting how I disagree with some suggestions on this list. CLR and Motwani-Raghavan are pretty good as references, but I find their organization disjointed making them hard to read straight through. Cover and Thomas I found hugely disappointing (poorly written and a lot of uninteresting material [to me]). Arora-Barak I have found good as a refresher if you already know the material, but hard to learn from.

    Oh, well, to each their own...

  14. 1. Naive Set Theory, by Paul Halmos. Just awesome.
    2. Conceptual Mathematics, by F. William Lawvere and Stephen H. Schanuel. An excellent introduction to category theory, and contains a picture-only proof of Cantor's Theorem that card(R) >!= card(N).
    3. Generatingfunctionology, by Herb Wilf. As cool as the title.
    4. Jewels of Stringology, by Maxime Crochemore and Wojciech Rytter. Yeah, it's an algorithms book, but it's still hot.

  15. The Probabilistic Method is great. And, although they aren't textbooks, I'm amazed that nobody's mentioned John Allen Paulos.

  16. Anonymous 11: Did you do all the problems? Reading Alon & Spencer is just not complete without doing the problems (much more so than other books I thnk)

  17. I read Sipser's Introduction to the Theory of Computation cover-to-cover, and I liked it a lot better than Kozen. It also does go into some topics that are seriously upper-level, which is pleasant.

  18. A couple more:

    Finite Dimensional Vector Spaces - Paul Halmos

    Algebra - Michael Artin

  19. "Characteristic Classes" by Milnor and Stasheff is pretty much essential reading for an algebraic topology graduate student. I think I must have read and understood about 90% of the book, it's extremely well written and I always go back to it.

    Otherwise, Nick Higham's "Writing for the Mathematical Sciences" is probably the only maths book that I've read cover-to-cover. But that's not quite a hardcore maths book.

  20. "Linear Algebra Done Right" by Axler.

  21. While we are on the subject.... I'm looking for a book with many worked out practical problems in probability (what we used to cal "word problems"). I'd like to periodically do some "drills" and build up my intuition in this area.


  22. If you give me thirty years, I feel confident that I could read and understand almost any math book.

  23. "Ideals, Varieties, and Algorithms" by Cox, Little and O'Shea.

  24. "Ideals, Varieties, and Algorithms" by Cox, Little and O'Shea.

  25. i'll heartily second sipser's intro to theory of computation. it's the only textbook i ever truly read cover-to-cover (and a solid fraction of it in one sitting)

  26. "Visual Complex Analysis" by Tristan Needham.

  27. Well I survived Bill's inflicting priority arguments on me ;)

    Most of these are (reasonably) short and sweet:

    Garey and Johnson's classic, "Computers and Intractability" Including doing ALL the exercises. (I didn't read through the whole catalogue of NP-complete problems at the end, though.)

    Oxtoby, "Measure and Category (2nd ed)" (Springer GTM 2)

    Koblitz, "An Intro to Number Theory and Cryptography" (Chock full of useful and elegant stuff. I just looked and can't find it on my shelf!! Somebody must have "borrowed" it (gasp).)

    Quigley, "Manual of Axiomatic Set Theory" Tiny little paperback on set theory. Where I first learned about AC, Zorn, well-orders, ordinals, cardinals, etc. Lets you fill in most of the proofs.

    Kunen, "Set Theory" While I'm on the subject ... Made it most of the way through this one, but petered out after Chapter 6 (in the middle of forcing).

    There are several other books that I enjoyed reading from the beginning but never got through, usually just running out of time. E.g.,
    Hartley Rogers's Recursive Functions text;
    Aki Kanamori's "The Higher Infinite" (great title, excruciatingly exact attention to detail in the writing)

  28. The Best books about cryptography are:
    Introduction to modern cryptography by Katz and Lindell.
    Foundations of Cryptography by Goldreich.

    They follow an axiomatic and rigorous approach using computational complexity theory.

    Generating Functionology by Wilf is very clear and beautiful book on combinatorics.

  29. "How to prove it" best book ever

  30. Complex Variables and Applications by Brown/Churchill

    Principles of Mathematical Analysis by Rudin

  31. This comment has been removed by the author.

  32. number theory books by William Levque