The Book of Evidence

Proofs from THE BOOK ( Engl. Proofs from THE BOOK ) is a book of mathematician Martin Aigner and Günter M. Ziegler and goes particularly elegant as a collection of mathematical proofs . It was first published in English in 1998 and in German in 2002 , as well as in other languages.

The book is dedicated to the mathematician Paul Erdős and the title refers to an idea by Erdős that there are perfect proofs to mathematical theorems, making clear his Platonic view of mathematics:

“I am not qualified to say whether God exists or not - I rather doubt his existence. Nonetheless, I always say that the SF has this transfinite book that contains the best proof of all mathematical theorems, proofs that are elegant and perfect. "

Erdős often jokingly referred to “Das Buch” ( The Book ) in lectures , one of the best-known statements being that as a mathematician you don't need to believe in God, but you should believe in the book (“You don't have to believe in God, but you should believe in The Book ”). According to Erdős' close colleague Béla Bollobás , however, he did not take the idea too seriously. Whenever he wanted to compliment a mathematician on what he considered to be a particularly elegant theorem, he would say that the proof "would come straight from the book" ( It's straight from the book ).

Erdős still took part in the elaborations with notes and suggestions, but died before the book was published.

The authors endeavored to choose only evidence that is understandable with the knowledge of undergraduate mathematics.

The book covers the five areas of number theory , geometry , analysis , combinatorics and graph theory in 40 chapters. The kiss number problem (problem of the 13 balls) was omitted from the second edition, since the proof, which followed a sketch by John Leech from 1956 and sought to complete it, turned out to be incomplete and the attempt to supplement it as too extensive.

chapter

Number theory

• Chapter 1: Six proofs for the infinity of prime numbers (in addition to Euclid's proof, three folklore proofs , a proof by Erdős and Fürstenberg's proof of the infinity of prime numbers ).
• Chapter 2: Bertrand's postulate (based on the first published work by Paul Erdős in 1932).
• Chapter 3: Erdős's (1934) theorem on the representation of binomial coefficients as l-th powers. Erdős derives it from a tightening of Bertrand's postulate by James Joseph Sylvester .
• Chapter 4: Fermat's two-squares theorem : Every prime number of the form 4n + 1 can be represented as the sum of two squares of natural numbers. The proof of Roger Heath-Brown (1984) (with improvement by Don Zagier ) and that of Axel Thue (1902) are presented. One of the proofs uses a special case of the law of square reciprocity .
• Chapter 5: Quadratic Reciprocity Law, with proofs after the third and sixth proof of Carl Friedrich Gauß's theorem .
• Chapter 6: Wedderburn's Theorem ( Every finite skew body is commutative. ) With the proof of Ernst Witt (1931).
• Chapter 7: Proof of the irrationality of pi (after Ivan Niven 1947) and some other numbers like Euler's number and its powers (after Joseph Liouville , Charles Hermite ).
• Chapter 8: Proofs for Euler's Theorem ( Basler Problem ) . Evidence from Akiva Jaglom and Isaak Jaglom , William LeVeque , Frits Beukers (with C. Kolb, E. Calabi) is presented, among others . ${\displaystyle \zeta (2)=\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {\pi ^{2}}{6}}}$

geometry

• Chapter 9: Hilbert's third problem: decomposition of polyhedra , after the improvements and completions of Max Dehn's proof by Hugo Hadwiger , Kagan , Boltjanski and others.
• Chapter 10: Theorem of Sylvester and Tibor Gallai : For every arrangement of n points in the plane that are not all on a straight line, there is a straight line that contains exactly two of the points. The evidence is given by L. M. Kelly, published by Coxeter in 1948. Generalizations of the theorem by Nicolaas Govert de Bruijn and Erdős are also discussed.
• Chapter 11: an assumption made by PR Scott in 1970 that points in the plane that do not all lie on a straight line have at least n-1 slopes of the straight lines passing through two points. The proof is presented by Eli Goodman, Ricky Pollack and Peter Ungar (1982). ${\displaystyle n\geq 3}$
• Chapter 12: Three Applications of Euler's Polyhedron Formula (for which Staudt's proof is presented). Among other things, another proof of Sylvester and Gallai's theorem is derived from it (after Norman Steenrod ) and a theorem by Georg Pick (1899): Every elementary triangle, i.e. with corner points that lie on an integer grid, but no further grid points contains, has the area . ${\displaystyle {\tfrac {1}{2}}}$
• Chapter 13: The rigidity theorem for three-dimensional polyhedra by Augustin Louis Cauchy , with the proof of Cauchy.
• Chapter 14: The question of the maximum number of pairwise touching d-dimensional simplices in d dimensions. Results by Joseph Zaks and Micha Perles are presented.
• Chapter 15: A conjecture by Erdős (1950) that any set of more than points in d-dimensional Euclidean space yields at least one angle between the lines connecting the points that is not an acute angle. Proof by Ludwig Danzer and Branko Grünbaum (1962), at the same time proving an extended conjecture by Victor Klee . ${\displaystyle 2^{d}}$
• Chapter 16: The refutation of the Borsuk conjecture about the decomposition of convex sets in d-dimensional space (first by Jeff Kahn and Gil Kalai 1994), with the proof of A. Nilli .

Analysis

• Chapter 17: Various theorems of set theory, including Georg Cantor's proof (diagonal argument) that real numbers cannot be counted and a proof of the Schröder-Bernstein theorem by Ernst Schröder and Felix Bernstein after Paul Cohen . Also presented is an elementary theorem on families of analytical functions by Wetzel (1962), the solution of which depends on the continuum hypothesis (proof by Erdős), and the enumeration of rational numbers according to Calkin and Herbert Wilf .
• Chapter 18: Cauchy-Schwarz inequality and inequality for the harmonic , arithmetic and geometric mean (proof by Cauchy and H. Alzer). The latter inequality is applied to Laguerre's theorem on the position of the zeros of polynomials (with only real zeros) and to a theorem by Erdős and Gallai who generalizes it (after George Polya 1940), as well as to a theorem of Pál Turán's graph theory .
• Chapter 19: Fundamental theorem of algebra , the proof is presented according to a basic idea by d'Alembert (1746).
• Chapter 20: The question of whether you can divide a square into an odd number of triangles of equal area (see Division into triangles of equal area ). This is not possible. The proof is presented by Paul Monsky , the only known proof. He uses valuation theory .
• Chapter 21: A theorem by George Polya (1928) on complex polynomials of f nth degree (with leading coefficient 1). Let C be the set that f is mapped onto the circle with radius 2 in the complex plane, L is an arbitrary straight line in the complex plane. Then the orthogonal projection of C onto L is maximally of length 4. Polya reduced the proof to a theorem of Chebyshev.
• Chapter 22: Proof of a lemma from John Edensor Littlewood and Offord (1943, improved by Erdős) by Kleitman (1970). The lemma makes statements about the number of points in the unit circle in the complex plane, which can be represented as a linear combination of n points with a magnitude greater than or equal to 1 with coefficients ± 1.
• Chapter 23: Partial fraction decomposition of the cotangent function , first given by Euler, with the proof of Gustav Herglotz .
• Chapter 24: Buffon's needle problem , after E. Barbier (1860).

Combinatorics

• Chapter 25: Drawer principle and double counting . Among other things, one of Erdő's favorite questions to budding mathematicians is mentioned there, which he asked Lajos Pósa when they first met. Sperner's Lemma (by Emanuel Sperner ), from which Brouwer's Fixed Point Theorem is derived, is mentioned as an application of double counting .
• Chapter 26: Decomposition of rectangles into rectangles according to Max Dehn, Nicolaas Govert de Bruijn.
• Chapter 27: Three Famous Proofs About Finite Sets . The set of Sperner (Proof by David Lubell), the set of Erdős-co Rado (by Gyula Katona ) and the marriage set by Hall (by T. E. Easter Field and Paul Halmos  / H. Vaughan) from the combinatorics.
• Chapter 28: Analysis of perfect card shuffles (Riffle Shuffle, analyzed by Edgar Gilbert and Claude Shannon 1955) according to Persi Diaconis and David Aldous (1986). The proof is presented in the book for at least 12 mixtures, Diaconis and Aldous prove that seven are sufficient (but no less).
• Chapter 29: Lemma of Gessel and Viennot (Ira Gessel, Gerard Viennot 1985) in counting combinatorics, with applications for example to determinants.
• Chapter 30: The Cayley formula for the number of labeled trees ( Arthur Cayley 1889). Four pieces of evidence are given.
• Chapter 31: Identities for products of infinite series and series with disintegrations ( partitions ), such as those treated by Euler and Ramanujan. It deals with a bijection proof for an identity by Euler after Doron Zeilberger and David Bressoud .
• Chapter 32: Completion of Latin Squares . The possibility of this was suggested by Trevor Evans in 1960, and proved by Bohdan Smetaniuk in 1981.

Graph theory

• Chapter 33: Jeff Dinitz (1978) problem on graph coloring, proved by Fred Galvin in 1995 after preliminary work by Jeanette Janssen (1992). Is it possible to color the cells of an n × n square so that the colors are different in each row and column? Each cell is assigned a palette (list) of n colors, which can also differ from cell to cell. Galvin proved it was possible.
• Chapter 34: The five-color theorem with color lists (as in the Dinitz problem) with the proof of Carsten Thomassen (1979).
• Chapter 35: The problem of the museum guards by Victor Klee, with the solution by Vašek Chvátal : With n walls, at least (n / 3 rounded ) guards are necessary for the "worst possible" arrangement of the walls. ${\displaystyle \lfloor {\frac {n}{3}}\rfloor }$
• Chapter 36: Turan's theorem in extremal graph theory , for which five proofs are given (among others by Turan, Erdős).
• Chapter 37: Computation of the capacity of communication channels and graphs according to Claude Shannon (with a proof by Laszlo Lovasz ).
• Chapter 38: Proof of the conjecture of Martin Kneser (1955) about the color number of Kneser graphs, for which Imre Bárány and Joshua Greene (2002) gave simplified proofs after the proof of Laszlo Lovasz 1978 . The proof is presented by Greene.
• Chapter 39: The friendship theorem of the graph theory by Erdős, Alfred Renyi and Vera T. Sós (with their proof).
• Chapter 40: Applications of the probabilistic method in graph theory according to Erdős and Renyi, for example to the estimation of Ramsey numbers.

Others

• Other mathematicians have published their own candidates, for example, Sergei Tabachnikov .
• The number theorist Godfrey Harold Hardy wrote the essay “ Apology of a Mathematician ” in 1940 , in which he fundamentally deals with the question of aesthetics in mathematics and also asks the question of the “most elegant proofs”.

Sources and web links

• Proofs from THE BOOK. Springer, Berlin 2014, ISBN 3-540-63698-6 (5th edition: ISBN 978-3-662-44205-0 ).
• The BOOK of Evidence. Springer, Berlin 2014, ISBN 3-540-42535-7 (4th edition: ISBN 978-3-662-44456-6 ).
• Günter M. Ziegler's homepage with a list of the editions and language versions.
• Review of Proofs from THE BOOK by Mary Shepard, Mathematical Association of America (1999).
• God's secret work. At: Zeit.de.
• Aigner, Ziegler: Diamonds for the “Book of Evidence”. PDF.

References

1. ↑ Supreme Fascist (Supreme Fascist) is a term often used by Erdős for God.
2. ↑ Erdős, quoted in Paul Hoffman: The man who only loved numbers. 1998, p. 27.
3. ↑ Aigner, Ziegler in the foreword to The Book of Proofs.
4. ^ Paul Hoffman: The Man Who Only Loved Numbers. 1998, Chapter 1 Straight from the Book.
5. ^ "So he always used 'The Book' as a joke to enliven his lectures. It should not be taken seriously. ”
   In: Béla Bollobás: Graphs Extremal and Random. Interview, University of Singapore, 2007, PDF.
6. ^ Hoffman: The Man Who Only Loved Numbers. P. 26.
7. ↑ Aigner, Ziegler, foreword to The Book of Evidence.
8. ↑ In the fourth English edition, Springer Verlag 2009.
9. ↑ PL Chebyshev and S. Ramanujan gave other evidence .
10. ↑ The division into an even number is trivial.
11. ^ Monsky, in: American Mathematical Monthly. Vol. 77, 1970, p. 161.
12. ↑ It was found by Bernt Lindström as early as 1972, but little noticed at the time.
13. ↑ Chvatal, in: Journal of Combinatorial Theory. Vol. 18, 1975, p. 39.
14. ↑ Tabachnikov, Proofs (not) from the book, Mathematical Intelligencer, 2014, No. 2