In the preface of Proofs from THE BOOK, we read that "Paul Erdös often talked about The Book, in which God maintains the perfect proofs of mathematical theorems." As I read through the preface to this book, I began to ask some questions. What constitutes a "beautiful" proof? How about a "perfect" proof? Is there any such thing as a "perfect" proof? I don't know the answer to these questions. This book was inspired by Erdös and contains many of his suggestions. It was to appear in March, 1998 as a present to Erdös on his 85th birthday, but he died in the summer of 1997, so he is not listed as a co-author. Instead the book is dedicated to his memory.
The authors have no definition or characterization of what constitutes a "proof from The Book." Even after reading the book, I could not tell you why these proofs were chosen over others. Although my initial questions were not answered, I liked the book. I really enjoyed some of the proofs, most of which I had not seen. I filled in some of the details, and constructed the example of a flexible surface shown in chapter 11. Other proofs that I did not work through would be very interesting to study. One of the things I found most enjoyable about the book--and this may have something to do with what constitutes a perfect proof--was that each theorem that was proved was easy to state and understand. And no one proof was very long, either. Few proofs went over two pages in length. Many were under one page. Most proofs pulled ideas from several areas of mathematics, and it seems to be this wonderful mixing of diverse ideas that leads to many of these proofs being in this book. Some of the proofs are recent, some date back to Euclid and others are noted as folklore proofs.
The book is divided into five sections: Number Theory, Geometry, Analysis, Combinatorics and Graph Theory. Each section has several chapters, each about one central theorem or group of similar theorems. Most chapters are under ten pages long. Some chapters present several different proofs of one theorem. Other chapters presents several related theorems. For instance, the first chapter is called "Six proofs of the infinity of primes," and the eleventh chapter is "Three applications of Euler's formula." There is also very readable exposition in each chapter that gives some of the history of the different proofs presented, some background and definitions along with examples in the margins, and sometimes some open questions related to the theorems and proofs presented. A few chapters have appendices which give more background for those unfamiliar with the basic concepts. Each chapter also gives references and is thus somewhat self contained. I found it interesting to note that many of the proofs used either induction, sometimes in a non-standard way, or were proofs by contradiction.
In the Number Theory section, the chapters are: (1) Six proofs of the infinity of primes, (2) Bertrand's postulate, (3) Binomial coefficients are (almost) never powers, (4) Representing numbers as sums of two squares, (5) Every finite division ring is a field, and (6) Some irrational numbers. I found most of these chapters to be somewhat difficult, requiring some background in algebra and analysis and even topology to be easily understandable. My favorite of these chapters was (4) because of the simplicity of statement of this theorem by Fermat, and the use of geometry to help visualize part of the solution. There was also a series of annoying but minor errors in chapter (6) in the reductions of the fractions on page 31.
My favorite section, and also the longest, was the second section, on Geometry. The chapters are (7) Hilbert's third problem: decomposing polyhedra, (8) Lines in the plane and decompositions of graphs, (9) The slope problem, (10) Three applications of Euler's formula, (11) Cauchy's rigidity theorem, (12) The problem of the thirteen spheres, (13) Touching simplices, (14) Every large point set has an obtuse angle, and (15) Borsuk's conjecture. Some highlights in this section include an introduction to graph theory in chapter (8), an explanation of some spherical geometry and combined use of graph theory in chapter (12). The visualization of many of the results in this section was quite nice. Several chapters here and later in the book use the graph theory ideas and Euler's formula presented in this section.
The section on Analysis includes chapters (16) Sets, functions, and the continuum hypothesis, (17) In praise of inequalities, (18) A theorem of Pólya on polynomials, and (19) On a lemma of Littlewood and Offord. I enjoyed chapter (16) because it was the most understandable to me without struggle. I had seen several of the proofs before, even though this is not my area of expertise. I enjoyed chapter (17) more than I expected to from its title. It includes the Cauchy-Schwarz inequality and the inequality that relates the harmonic, geometric and arithmetic means. It also includes some other inequalities--about roots of polynomials and from graph theory--that use one or more of the above inequalities in their proofs.
The section on Combinatorics includes chapters (20) Pigeon-hole and double counting, (21) Three famous theorems on finite sets, (22) Cayley's formula for the number of trees, (23) Completing Latin squares, and (4) The Dinitz problem. Graphs and Euler's formula reappear in this section. The Marriage theorem is one of the three famous theorems in chapter (21). Chapter (22) includes four very different approaches to proving Cayley's theorem on the number of different labeled trees on n vertices. One proof gives a bijection, one uses linear algebra, a third uses recursion and induction and the fourth involves double counting. Each approach in interesting in its own right and together allow one to see the problem and solution from several different viewpoints. Could it be that there is no one perfect proof for some theorems?
The final section, on Graph Theory, includes chapters (25) Five-coloring plane graphs, (26) How to guard a museum, (27) Turán's graph theorem, (28) Communicating without errors, (29) Of friends and politicians and (30) Probability makes counting (sometimes) easy. Quite a bit of graph theory is used prior to this section of the book. Chapter (25) includes a discussion of the four-color theorem and the opinion that no book proof is yet available. I especially enjoyed chapter (26) since it was quite geometric in viewpoint, but all the sections seemed accessible given a strong undergraduate mathematical background.
A goal of the book is to make everything accessible to readers whose backgrounds include only a modest amount of technique from undergraduate mathematics--some linear algebra, basic analysis, number theory, and discrete mathematics. I would add modern algebra and topology to this list for some sections, and comment that more linear algebra than just being able to do calculations is needed. I think many undergraduates would be challenged by much of the material in this book, not because it is so very difficult, but because it pulls together ideas from several areas of mathematics. I found myself wondering whether it would be possible to put together a similar collection of proofs accessible to high school and early undergraduate mathematics students.
Anyone who enjoys the logic and reasoning of mathematics and has a strong undergraduate mathematics background should enjoy this book. I do not think it could be used as a text as such, although I think it would make for an excellent reading or resource book for a capstone course at the undergraduate level. Professional mathematicians will enjoy the book also. I would imagine that few mathematicians have seen all these proofs. The combination of ideas in many of the proofs should delight mathematicians everywhere.
Mary Shepherd, (firstname.lastname@example.org) is Assistant Professor of Mathematics at SUNY College at Potsdam in Potsdam, New York. Her special interests are differential geometry and music.