Martin Aigner.Gunter M.Ziegler Proofs from THE BOOK Fifth Edition ②Springer
Martin Aigner · Günter M. Ziegler Proofs from THE BOOK Fifth Edition
Preface Paul Erdos liked to talk about The Book,in which God maintains the perfect proofs for mathematical theorems,following the dictum of G.H.Hardy that there is no permanent place for ugly mathematics.Erdos also said that you need not believe in God but,as a mathematician,you should believe in The Book.A few years ago,we suggested to him to write up a first (and very modest)approximation to The Book.He was enthusiastic about the idea and,characteristically,went to work immediately,filling page after page with his suggestions.Our book was supposed to appear in March 1998 as a present to Erdos'85th birthday.With Paul's unfortunate death in the summer of 1996,he is not listed as a co-author.Instead this book is dedicated to his memory. Paul Erd6s We have no definition or characterization of what constitutes a proof from The Book:all we offer here is the examples that we have selected,hop- ing that our readers will share our enthusiasm about brilliant ideas,clever insights and wonderful observations.We also hope that our readers will enjoy this despite the imperfections of our exposition.The selection is to a great extent influenced by Paul Erdos himself.A large number of the topics were suggested by him,and many of the proofs trace directly back to him, or were initiated by his supreme insight in asking the right question or in making the right conjecture.So to a large extent this book reflects the views of Paul Erdos as to what should be considered a proof from The Book “The Book A limiting factor for our selection of topics was that everything in this book is supposed to be accessible to readers whose backgrounds include only a modest amount of technique from undergraduate mathematics.A little linear algebra,some basic analysis and number theory,and a healthy dollop of elementary concepts and reasonings from discrete mathematics should be sufficient to understand and enjoy everything in this book. We are extremely grateful to the many people who helped and supported us with this project-among them the students of a seminar where we discussed a preliminary version,to Benno Artmann,Stephan Brandt,Stefan Felsner,Eli Goodman,Torsten Heldmann,and Hans Mielke.We thank Margrit Barrett,Christian Bressler,Ewgenij Gawrilow,Michael Joswig, Elke Pose,and Jorg Rambau for their technical help in composing this book.We are in great debt to Tom Trotter who read the manuscript from first to last page,to Karl H.Hofmann for his wonderful drawings,and most of all to the late great Paul Erdos himself. Berlin,March 1998 Martin Aigner.Giinter M.Ziegler
Preface Paul Erdos˝ Paul Erdos liked to talk about The Book, in which God maintains the perfect ˝ proofs for mathematical theorems, following the dictum of G. H. Hardy that there is no permanent place for ugly mathematics. Erdos also said that you ˝ need not believe in God but, as a mathematician, you should believe in The Book. A few years ago, we suggested to him to write up a first (and very modest) approximation to The Book. He was enthusiastic about the idea and, characteristically, went to work immediately, filling page after page with his suggestions. Our book was supposed to appear in March 1998 as a present to Erdos’ 85th birthday. With Paul’s unfortunate death ˝ in the summer of 1996, he is not listed as a co-author. Instead this book is dedicated to his memory. “The Book” We have no definition or characterization of what constitutes a proof from The Book: all we offer here is the examples that we have selected, hoping that our readers will share our enthusiasm about brilliant ideas, clever insights and wonderful observations. We also hope that our readers will enjoy this despite the imperfections of our exposition. The selection is to a great extent influenced by Paul Erdos himself. A large number of the topics ˝ were suggested by him, and many of the proofs trace directly back to him, or were initiated by his supreme insight in asking the right question or in making the right conjecture. So to a large extent this book reflects the views of Paul Erdos as to what should be considered a proof from The Book. ˝ A limiting factor for our selection of topics was that everything in this book is supposed to be accessible to readers whose backgrounds include only a modest amount of technique from undergraduate mathematics. A little linear algebra, some basic analysis and number theory, and a healthy dollop of elementary concepts and reasonings from discrete mathematics should be sufficient to understand and enjoy everything in this book. We are extremely grateful to the many people who helped and supported us with this project — among them the students of a seminar where we discussed a preliminary version, to Benno Artmann, Stephan Brandt, Stefan Felsner, Eli Goodman, Torsten Heldmann, and Hans Mielke. We thank Margrit Barrett, Christian Bressler, Ewgenij Gawrilow, Michael Joswig, Elke Pose, and Jörg Rambau for their technical help in composing this book. We are in great debt to Tom Trotter who read the manuscript from first to last page, to Karl H. Hofmann for his wonderful drawings, and most of all to the late great Paul Erdos himself. ˝ Berlin, March 1998 Martin Aigner · Günter M. Ziegler
VI Preface to the Fifth Edition It is now almost twenty years that the idea to this project was born dur- ing some leisurely discussions at the Mathematisches Forschungsinstitut in Oberwolfach with the incomparable Paul Erdos.At that time we could not possibly imagine the wonderful and lasting response our book about The Book would have,with all the warm letters,interesting comments and suggestions,new editions,and as of now thirteen translations.It is no exaggeration to say that it has become a part of our lives. In addition to numerous improvements and smaller changes,many of them suggested by our readers,the present fifth edition contains four new chap- ters,which present an extraordinary proof for the classical spectral theorem from linear algebra,the impossibility of the Borromean rings as a highlight from geometry,the finite version of Kakeya's problem,and an inspired proof for Minc's permanent conjecture. We thank everyone who helped and encouraged us over all these years.For the second edition this included Stephan Brandt,Christian Elsholtz,Jurgen Elstrodt,Daniel Grieser,Roger Heath-Brown,Lee L.Keener,Christian Leboeuf,Hanfried Lenz,Nicolas Puech,John Scholes,Bernulf WeiBbach, and many others.The third edition benefitted especially from input by David Bevan,Anders Bjorner,Dietrich Braess,John Cosgrave,Hubert Kalf,Gunter Pickert,Alistair Sinclair,and Herb Wilf.For the fourth edi- tion,we were particularly indebted to Oliver Deiser,Anton Dochtermann, Michael Harbeck,Stefan Hougardy,Hendrik W.Lenstra,Guinter Rote, Moritz W.Schmitt,and Carsten Schultz for their contributions.For the present edition,we gratefully acknowledge ideas and suggestions by Ian Agol,France Dacar,Christopher Deninger,Michael D.Hirschhorn,Franz Lemmermeyer,Raimund Seidel,Tord Sjodin,and John M.Sullivan,as well as help from Marie-Sophie Litz,Miriam Schloter,and Jan Schneider. Moreover,we thank Ruth Allewelt at Springer in Heidelberg and Christoph Eyrich,Torsten Heldmann,and Elke Pose in Berlin for their continuing sup- port throughout these years.And finally,this book would certainly not look the same without the original design suggested by Karl-Friedrich Koch,and the superb new drawings provided for each edition by Karl H.Hofmann. Berlin,June 2014 Martin Aigner.Giinter M.Ziegler
VI Preface to the Fifth Edition It is now almost twenty years that the idea to this project was born during some leisurely discussions at the Mathematisches Forschungsinstitut in Oberwolfach with the incomparable Paul Erdos. At that time we could ˝ not possibly imagine the wonderful and lasting response our book about The Book would have, with all the warm letters, interesting comments and suggestions, new editions, and as of now thirteen translations. It is no exaggeration to say that it has become a part of our lives. In addition to numerous improvements and smaller changes, many of them suggested by our readers, the present fifth edition contains four new chapters, which present an extraordinary proof for the classical spectral theorem from linear algebra, the impossibility of the Borromean rings as a highlight from geometry, the finite version of Kakeya’s problem, and an inspired proof for Minc’s permanent conjecture. We thank everyone who helped and encouraged us over all these years. For the second edition this included Stephan Brandt, Christian Elsholtz, Jürgen Elstrodt, Daniel Grieser, Roger Heath-Brown, Lee L. Keener, Christian Lebœuf, Hanfried Lenz, Nicolas Puech, John Scholes, Bernulf Weißbach, and many others. The third edition benefitted especially from input by David Bevan, Anders Björner, Dietrich Braess, John Cosgrave, Hubert Kalf, Günter Pickert, Alistair Sinclair, and Herb Wilf. For the fourth edition, we were particularly indebted to Oliver Deiser, Anton Dochtermann, Michael Harbeck, Stefan Hougardy, Hendrik W. Lenstra, Günter Rote, Moritz W. Schmitt, and Carsten Schultz for their contributions. For the present edition, we gratefully acknowledge ideas and suggestions by Ian Agol, France Dacar, Christopher Deninger, Michael D. Hirschhorn, Franz Lemmermeyer, Raimund Seidel, Tord Sjödin, and John M. Sullivan, as well as help from Marie-Sophie Litz, Miriam Schlöter, and Jan Schneider. Moreover, we thank Ruth Allewelt at Springer in Heidelberg and Christoph Eyrich, Torsten Heldmann, and Elke Pose in Berlin for their continuing support throughout these years. And finally, this book would certainly not look the same without the original design suggested by Karl-Friedrich Koch, and the superb new drawings provided for each edition by Karl H. Hofmann. Berlin, June 2014 Martin Aigner · Günter M. Ziegler
Table of Contents Number Theory_ .1 1.Six proofs of the infinity of primes..............................3 2.Bertrand'spostulate.......................................9 3.Binomial coefficients are(almost)never powers.................15 4.Representing numbers as sums of two squares...................19 5.The law of quadratic reciprocity ...............25 6.Every finite division ring is a field..............................33 7.The spectral theorem and Hadamard's determinant problem.......37 8.Some irrational numbers......................................45 9.Three times2/6................53 Geometry_ 61 10.Hilbert's third problem:decomposing polyhedra.................63 11.Lines in the plane and decompositions of graphs.................73 12.The slope problem................................79 13.Three applications of Euler's formula..........................85 14.Cauchy's rigidity theorem.....................................91 15.The Borromean rings don't exist...............................95 16.Touching simplices..........................................103 17.Every large point set has an obtuse angle...................... 107 18.Borsuk'sconjecture.........................................113 Analysis 121 19.Sets,functions,and the continuum hypothesis..................123 20.In praise of inequalities......................................139 21.The fundamental theorem of algebra..........................147 22.One square and an odd number of triangles ....................151
Table of Contents Number Theory 1 1. Six proofs of the infinity of primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Bertrand’s postulate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3. Binomial coefficients are (almost) never powers . . . . . . . . . . . . . . . . . 15 4. Representing numbers as sums of two squares . . . . . . . . . . . . . . . . . . . 19 5. The law of quadratic reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6. Every finite division ring is a field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7. The spectral theorem and Hadamard’s determinant problem . . . . . . .37 8. Some irrational numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 9. Three times π2/6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Geometry 61 10. Hilbert’s third problem: decomposing polyhedra . . . . . . . . . . . . . . . . .63 11. Lines in the plane and decompositions of graphs . . . . . . . . . . . . . . . . . 73 12. The slope problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .79 13. Three applications of Euler’s formula . . . . . . . . . . . . . . . . . . . . . . . . . . 85 14. Cauchy’s rigidity theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 15. The Borromean rings don’t exist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 16. Touching simplices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 17. Every large point set has an obtuse angle . . . . . . . . . . . . . . . . . . . . . . 107 18. Borsuk’s conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Analysis 121 19. Sets, functions, and the continuum hypothesis . . . . . . . . . . . . . . . . . . 123 20. In praise of inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 21. The fundamental theorem of algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 147 22. One square and an odd number of triangles . . . . . . . . . . . . . . . . . . . . 151
VIⅢ Table of Contents 23.A theorem of Polya on polynomials ...........................159 24.On a lemma of Littlewood and Offord.........................165 25.Cotangent and the Herglotz trick..............................169 26.Buffon's needle problem.....................................175 Combinatorics 179 27.Pigeon-hole and double counting............................. 181 28.Tiling rectangles............................................ 193 29.Three famous theorems on finite sets..........................199 30.Shuffing cards.............................................205 31.Lattice paths and determinants................................215 32.Cayley's formula for the number of trees...................... 221 33.Identities versus bijections...................................227 34.The finite Kakeya problem...................................233 35.Completing Latin squares 239 Graph Theory 245 36.The Dinitz problem........................................247 37.Permanents and the power of entropy .253 38.Five-coloring plane graphs ................................ 261 39.How to guard a museum.........265 40.Turan's graph theorem...................................... .269 41.Communicating without errors...............................275 42.The chromatic number of Kneser graphs.......................285 43.Of friends and politicians....................................291 44.Probability makes counting(sometimes)easy..................295 About the lllustrations 304 Index 305
VIII Table of Contents 23. A theorem of Pólya on polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 24. On a lemma of Littlewood and Offord . . . . . . . . . . . . . . . . . . . . . . . . . 165 25. Cotangent and the Herglotz trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 26. Buffon’s needle problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Combinatorics 179 27. Pigeon-hole and double counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 28. Tiling rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 29. Three famous theorems on finite sets . . . . . . . . . . . . . . . . . . . . . . . . . . 199 30. Shuffling cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 31. Lattice paths and determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 32. Cayley’s formula for the number of trees . . . . . . . . . . . . . . . . . . . . . . 221 33. Identities versus bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 34. The finite Kakeya problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 35. Completing Latin squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Graph Theory 245 36. The Dinitz problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .247 37. Permanents and the power of entropy . . . . . . . . . . . . . . . . . . . . . . . . . .253 38. Five-coloring plane graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 39. How to guard a museum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 40. Turán’s graph theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 41. Communicating without errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 42. The chromatic number of Kneser graphs . . . . . . . . . . . . . . . . . . . . . . . 285 43. Of friends and politicians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 44. Probability makes counting (sometimes) easy . . . . . . . . . . . . . . . . . . 295 About the Illustrations 304 Index 305