The concept of a *proof from the Book* was devised by Paul Erdős. The Book contains the best possible proof of each theorem of mathematics. The idea has been popularised in a book of the same name by Martin Aigner and Gunter Ziegler, who have assembled a fine collection of short and beautiful proofs. All of mathematics is there, and I am sure that many people have found their book inspirational.

Yesterday in a lecture (I am writing this on Tuesday but it will be posted on Monday because of a time warp), Geoff Whittle suggested a related but slightly different concept, which I like. This is perhaps aimed more at professional mathematicians than at beginners. This is “Fifty proofs to read before you die”. Whereas the Book is something that only God (and perhaps now Erdős) can read, Whittle’s concept seems to me to be much more human. As with other lists of “Fifty Xs to Y before you die”, everyone can produce their own list, according to their own criteria, stated or implicit.

Geoff’s suggestion for such a proof is Nash-Williams’ proof of Kruskal’s Theorem asserting that finite trees are well-quasi-ordered by the minor relation. As far as I understood his thinking, this is a substantial proof, which is not only a work of art to be savoured, but has also provided tools and techniques of wide applicability. This last criterion makes Geoff’s concept a bit different, since a clumsy (or even ugly) proof may be more fruitful in the long run.

I don’t want to be dogmatic about the criteria, but I would be very interested in any suggestions you may have for this list. Either add your suggestion as a comment, or email it to me; if there is a response, I will produce a commented list at some point.

### Like this:

Like Loading...

*Related*

## About Peter Cameron

I count all the things that need to be counted.

Great idea!

Here’s hoping that this becomes a meme for mathematical bloggers!

Aiming it at professional mathematicians is a problem. I immediately thought of diagonalisation proofs, like Cantor’s proof that there are more reals than rationals, and the undecidability of the halting problem. But those are proofs that everyone should learn.

Dirichlet’s proof that there are infinitely many primes in any arithmetic progression whose starting term is coprime to its step size, *in full detail*. (I am probably swayed by the incomplete but well motivated account given in Körner’s Fourier Analysis book.)

I’ve been wondering about my own choice. Here are two proofs I like, one from group theory (I’ve been teaching it this semester) and the other from combinatorics.

From group theory I would choose the Schur-Zassenhaus theorem, asserting that if the finite groups

GandHhave coprime order, then any extension ofGbyHsplits. Schur dealt with the case whereGis abelian: the proof is one of the founding documents of homological algebra, and really shows very clearly what this machinery can do. Zassenhaus extended it to the general case (assuming that eitherGorHis soluble) using pure group theory; the wrinkle in the tail of the story is that the coprimeness means that one at least of the two groups has odd order, so once Feit and Thompson had done their work we knew that Zassenhaus’ extra condition was not necessary. (I don’t think I would include the Feit–Thompson theorem in the compulsory reading!)From combinatorics I would choose the Bruck–Ryser theorem, that a projective plane of order

ndoes not exist ifnis congruent to 1 or 2 (mod 4) and is not the sum of two squares. It is completely elementary (and ingenious), but we are on the edge of the Hasse–Minkowski theory of quadratic forms here, and so it is really an interplay between combinatorics and number theory.The simple probabilistic lower bound for the diagonal Ramsey number R(k,k) would be a good candidate. It is a nice and simple introduction to the probabilistic method for mathematicians who do not usually work with combinatorics.

How about Don Zagier’s “one-sentence proof” of Fermat’s theorem that an odd prime number is the sum of two squares if and only if ?

http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier.27s_.22one-sentence_proof.22

Pingback: Mathblogging.org Weekly Picks « Mathblogging.org — the Blog

Euclid’s proof of the infinitude of primes.

Ramanujan’s proof of the Bertrand Postulate

As a theoretical computer scientist, I’m a big fan of Irit Dinur’s proof of the PCP theorem for approximability of problems in NP (which is very different from the original proof, especially in that it is based on the 3-satisfiability problem which is at the center of the class NP – much more “satisfying”). The theorem itself is beautiful and opened up a whole area of theory of approximation algorithms, demonstrating that unless P=NP, not all NP problems are alike.