Proofs from THE BOOK

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

The book is dedicated to the mathematician Paul Erdős and the title refers to an idea of Erdős that there is perfect evidence to mathematical propositions, his Platonic conception of mathematics clearly making: I'm not qualified to say whether God exists or not - I rather doubt its existence. Nonetheless, I always say that the SF has this transfinite book that contains the best evidence of all mathematical propositions, proofs that are elegant and perfect.

Erdős referred lectures often jokingly to " The Book " ( The Book ), one of the most famous statements is, you need a mathematician not to believe in God, but you should believe in the Book ( You do not have to believe in God, but You Should believe in The Book ). According to the testimony of Erdos closely employee Bela Bollobás he did not take the idea too seriously, however. If he wanted to make a mathematician a compliment for a particularly elegant theorem in his eyes, he used to say, the proof would come straight out of the book (It's straight from the book).

Erdős still participated with notes and suggestions to the elaborations, but died before the publication of the book.

The authors tried to select only evidence that is understandable with the knowledge of the mathematics undergraduate studies.

The book covers the five areas of number theory, geometry, analysis, combinatorics and graph theory, in 40 chapters. The Kiss number problem (the problem of 13 balls ) was omitted from the second edition, as the evidence which followed a sketch by John Leech of 1956 and to complete these sought to be incomplete and the experiment proved its supplement as too extensive.

Chapter

Number Theory

Chapter 1: Six proofs of the infinity of primes (in addition to Euclid's proof three folkloric evidence, proof of Erdős and Fürstenberg's proof of the infinitude of primes )
Chapter 2: Bertrand's postulate (after the first published work of Paul Erdős 1932).
Chapter 3: The set of Erdős (1934 ), on the representation of binomial coefficients as l-th powers. Erdős passes it off from a tightening of Bertrand 's postulate by James Joseph Sylvester.
Chapter 4: The two-square theorem of Fermat: Every prime of the form 4m 1 is represented as the sum of two squares of natural numbers. There the evidence of Roger Heath- Brown ( 1984) will be presented ( with improvement of Don Zagier ) and Axel Thue (1902 ). One of the proofs uses a special case of the quadratic reciprocity law.
Chapter 5: Quadratic reciprocity law, with evidence after the third and sixth proof of the theorem of Carl Friedrich Gauss.
Chapter 6: The set of Wedderburn ( every finite skew field is commutative ), with the evidence of Ernst Witt ( 1931)
Chapter 7: Proof of the irrationality of pi ( after Ivan Niven 1947) and some other numbers like the Euler number, and their potencies (after Joseph Liouville, Charles Hermite ).
Chapter 8: Evidence of Euler's theorem ( Basel problem) that. Among other evidence of Akiva Jaglom and Isaac Jaglom, William LeVeque, Frits Beukers presented ( with C. Kolb, E. Calabi ).

Geometry

Chapter 9: Hilbert's third problem: decomposition of polyhedra, after the improvements and completions by Max Dehn's proof by Hugo Hadwiger, Kagan, Boltjanski and others.
Chapter 10: Sylvester's theorem and Tibor Gallai: For every arrangement of n points in the plane which do not all lie on a straight line, there is a line that contains exactly two of the points. Where is the proof of LM Kelly, the 1948 Coxeter published. Also generalizations of the set of Nicolaas Govert de Bruijn and Erdős be treated.
Chapter 11: a PR Scott 1970 marked assumption that points in the plane which do not all lie on a straight line, at least ( n-1) have slopes of the line passing through two points straight. Presented is the proof of Eli Goodman, Ricky Pollack and Peter Ungar (1982).
Chapter 12: Three applications of Euler's polyhedron formula (used for presenting the proof of Staudt ). Among other things, further proof of the theorem of Sylvester and Gallai is derived from it ( according to Norman Steenrod ) and a set of Georg Pick ( 1899): each elementary triangle, that is, with vertices that lie on an integer grid, but no other lattice points contains, has the surface area.
Chapter 13: The rigidity theorem for three-dimensional polyhedron of 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 of Joseph Zaks and Micha Perles are presented.
Chapter 15: A conjecture of Erdős (1950 ) that any amount in excess of points in d-dimensional Euclidean space provides at least one angle between the lines connecting the points, which is not an acute angle. Proof of Ludwig Danzer and Branko Grünbaum (1962 ), where they simultaneously demonstrated an enhanced presumption of Victor Klee.
Chapter 16: The refutation of Borsuk 's conjecture on 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: different sets of set theory, including Georg Cantor's proof ( diagonal argument) the Nichtabzählbarkeit of real numbers and a proof of the set of Schröder- Bernstein of Ernst Schröder and Felix Bernstein by Paul Cohen. Also on display is an elementary theorem on families of analytic functions by Wetzel (1962 ), the solution of the continuum hypothesis depends ( proof of Erdős ), and the enumeration of the rational numbers Calkin and Herbert Wilf.
Chapter 18: Cauchy- Schwarz inequality and inequality for the harmonic, arithmetic and geometric means ( proof of Cauchy and H. Alzer ). The latter inequality is (with only real zeros ) applied to the set of Laguerre on the location of zeros of polynomials and a set of Erdős and Gallai, which generalizes this (after George Polya 1940), as well as on a set of graph theory of Pal Turan.
Chapter 19: Fundamental Theorem of Algebra, is presented the evidence for a basic idea of Alembert ( 1746 ).
Chapter 20: the question of whether one can decompose a square into an odd number of triangles of equal area (see decomposition into equal-area triangles). This is not possible. Presented is the evidence of Paul Monsky, the only known evidence. It uses the valuation theory.
Chapter 21: a set of George Polya (1928 ), complex polynomials of degree n ( with leading coefficient equal to 1). C is the set that is shown by the circle of radius R 2 in the complex plane, L is any straight line in the complex plane. Then the orthogonal projection of C on L max 4 of the length of Polya has led the evidence back to a set of Chebyshev.
Chapter 22: Proof of a lemma of 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 a linear combination of n points on the amount greater than or equal to 1 shown with coefficients plus / minus 1.
Chapter 23: partial fraction decomposition of the cotangent, first given by Euler, with the evidence of Gustav Herglotz.
Chapter 24: the Buffon needle problem, according to E. Barbier ( 1860).

Combinatorics

Chapter 25: pigeonhole principle and double counting. Among other things, one of Erdős favorite questions to aspiring young mathematicians is mentioned there that he also Lajos Posa presented at their first meeting. As an application of double counting out Sperner's Lemma is mentioned ( by Emanuel Sperner ), from which the Brouwer fixed point theorem is derived.
Chapter 26: dissection of rectangles into rectangles by Max Dehn, Nicolaas Govert de Bruijn.
Chapter 27: Three famous evidence of finite sets. The set of Sperner (Proof by David Lubell ), the set of Erdős -Ko - Rado ( by Gyula Katona ) and the marriage theorem of Hall ( TE after Easter Field and Paul Halmos / H. Vaughan ) from the combinatorics.
Chapter 28: Analysis perfect cards mixtures ( Riffle Shuffle, analyzed by Edgar Gilbert and Claude Shannon 1955) by Persi Diaconis and David Aldous (1986). The proof is presented demonstrated in the book for at least 12 mixtures, Diaconis and Aldous that seven sufficient (but not less ).
Chapter 29: Lemma of Gessel and Viennot ( Ira Gessel, Gerard Viennot 1985) in enumerative combinatorics, with applications for example on determinants.
Chapter 30: the Cayley formula on the number of labeled trees ( Arthur Cayley 1889). There are four given evidence.
Chapter 31: Identities for products of infinite series and series with Zerfällungen (partitions), how they were treated, for example by Euler and Ramanujan. Treatment is a Bijektions - proof of an identity of Euler by Doron Zeilberger and Bressoud David.
Chapter 32: Completion of Latin squares. The way to do this was suggested by Trevor Evans in 1960, proved by Bohdan Smetaniuk 1981.

Graph Theory

Chapter 33: Problem by Jeff Dinitz (1978 ) on graph coloring, proved by Fred Galvin in 1995 assisted by Jeanette Janssen ( 1992). Is it possible the cells of an nxn square to color so that the colors are different in each row and column? In this case, each cell is a pallet ( list) assigned to one of n colors that can be different from cell to cell. Galvin proved that it is possible.
Chapter 34: the five -color set with color lists (as in Dinitz problem) with the proof of Carsten Thomassen (1979).
Chapter 35: The problem of museum guard of Victor Klee, with the solution of Vasek Chvátal (with n walls are at least (ie n / 3 rounded down) guards required for the " bad - most possible " arrangement of the walls).

Chapter 36: the set of Turan in extremal graph theory, for the five proofs are given (among other things of Turan, Erdős ).
Chapter 37: Calculation of the capacity of communication channels and graphs by Claude Shannon ( with a proof of Laszlo Lovasz ).
Chapter 38: Proof of the conjecture of Martin Kneser (1955 ) on the chromatic number of Kneser graphs, for after the proof of Laszlo Lovasz 1978 Imre Bárány and Joshua Greene ( 2002) gave simplified proofs. Presented is the proof of Greene.
Chapter 39: of friendship set in graph theory of Erdős, Alfred Renyi and Vera T. Sós ( with the evidence of the three ).
Chapter 40: application of the probabilistic method in graph theory Erdős and Renyi, for example on the estimation of Ramsey numbers.

218361