Skip to main content

2004 | Buch | 3. Auflage

Proofs from THE BOOK

verfasst von: Martin Aigner, Günter M. Ziegler

Verlag: Springer Berlin Heidelberg

insite
SUCHEN

Über dieses Buch

From the Reviews:

"... Inside PFTB (Proofs from The Book) is indeed a glimpse of mathematical heaven, where clever insights and beautiful ideas combine in astonishing and glorious ways. There is vast wealth within its pages, one gem after another. Some of the proofs are classics, but many are new and brilliant proofs of classical results. ...Aigner and Ziegler... write: "... all we offer is the examples that we have selected, hoping that our readers will share our enthusiasm about brilliant ideas, clever insights and wonderful observations." I do. ... " Notices of the AMS, August 1999

"... the style is clear and entertaining, the level is close to elementary ... and the proofs are brilliant. ..." LMS Newsletter, January 1999

This third edition offers two new chapters, on partition identities, and on card shuffling. Three proofs of Euler's most famous infinite series appear in a separate chapter. There is also a number of other improvements, such as an exciting new way to "enumerate the rationals".

Inhaltsverzeichnis

Frontmatter

Number Theory

Frontmatter
Chapter 1. Six proofs of the infinity of primes

It is only natural that we start these notes with probably the oldest Book Proof, usually attributed to Euclid (Elements IX, 20). It shows that the sequence of primes does not end.

Martin Aigner, Günter M. Ziegler
Chapter 2. Bertrand’s postulate

We have seen that the sequence of prime numbers 2, 3, 5, 7, … is infinite. To see that the size of its gaps is not bounded, let N := 2 • 3 • 5•...• p denote the product of all prime numbers that are smaller than k + 2, and note that none of the k numbers $$N - 2,N + 3,N + 4,...,N + k,N + (k + 1)$$ is prime, since for 2≤ i ≤ k + 1 we know that i has a prime factor that is smaller than k + 2, and this factor also divides N, and hence also N + i. With this recipe, we find, for example, for k = 10 that none of the ten numbers $$2312,2313,2314,...,2321$$ is prime.

Martin Aigner, Günter M. Ziegler
Chapter 3. Binomial coefficients are (almost) never powers

There is an epilogue to Bertrand’s postulate which leads to a beautiful result on binomial coefficients. In 1892 Sylvester strengthened Bertrand’s postulate in the following way: $$In\;n > 2k,then\;at\;least\;one\;of\;the\;numbers\;n,n - 1,...,n - k + 1\;has\;a\;prime\;divisor\;p\;greater\;than\;k.$$.

Martin Aigner, Günter M. Ziegler
Chapter 4. Representing numbers as sums of two squares

This question is as old as number theory, and its solution is a classic in the field. The “hard” part of the solution is to see that every prime number of the form 4m + 1 is a sum of two squares. G. H. Hardy writes that this two square theorem of Fermat “is ranked, very justly, as one of the finest in arithmetic.” Nevertheless, one of our Book Proofs below is quite recent.

Martin Aigner, Günter M. Ziegler
Chapter 5. Every finite division ring is a field

Rings are important structures in modern algebra. If a ring R has a multiplicative unit element 1 and every nonzero element has a multiplicative inverse, then R is called a division ring. So, all that is missing in R from being a field is the commutativity of multiplication. The best-known example of a non-commutative division ring is the ring of quaternions discovered by Hamilton. But, as the chapter title says, every such division ring must of necessity be infinite. If R is finite, then the axioms force the multiplication to be commutative.

Martin Aigner, Günter M. Ziegler
Chapter 6. Some irrational numbers

This was already conjectured by Aristotle, when he claimed that diameter and circumference of a circle are not commensurable. The first proof of this fundamental fact was given by Johann Heinrich Lambert in 1766. Our Book Proof is due to Ivan Niven, 1947: an extremely elegant one-page proof that needs only elementary calculus. Its idea is powerful, and quite a bit more can be derived from it, as was shown by Iwamoto and Koksma, respectively: π2 is irrational ander is irrational for rational r ≠ 0.

Martin Aigner, Günter M. Ziegler
Chapter 7. Three times π2/6

We know that the infinite series $$ \sum\nolimits_{n \ge 1} {\frac{1}{n}} $$ does not converge. Indeed, in Chapter 1 we have seen that even the series $$ \sum\nolimits_{p \in p} {\frac{1}{p}} $$ diverges. However, the sum of the reciprocals of the squares converges (although very slowly, as we will also see), and it produces an interesting value.

Martin Aigner, Günter M. Ziegler

Geometry

Frontmatter
Chapter 8. Hilbert’s third problem: decomposing polyhedra

In his legendary address to the International Congress of Mathematicians at Paris in 1900 David Hilbert asked — as the third of his twenty-three problems — to specify

“two tetrahedra of equal bases and equal altitudes which can in no way be split into congruent tetrahedra, and which cannot be combined with congruent tetrahedra to form two polyhedra which themselves could be split up into congruent tetrahedra.”

Martin Aigner, Günter M. Ziegler
Chapter 9. Lines in the plane and decompositions of graphs

Perhaps the best-known problem on configurations of lines was raised by Sylvester in 1893 in a column of mathematical problems.

Martin Aigner, Günter M. Ziegler
Chapter 10. The slope problem

Try for yourself before you read much further to construct configurations of points in the plane that determine “relatively few” slopes. For this we assume, of course, that the n > 3 points do not all lie on one line. Recall from Chapter 9 on “Lines in the plane” the theorem of Erdös and de Bruijn: the n points will determine at least n different lines. But of course many of these lines may be parallel, and thus determine the same slope.

Martin Aigner, Günter M. Ziegler
Chapter 11. Three applications of Euler’s formula

A graph is planar if it can be drawn in the plane ℝ2 without crossing edges (or, equivalently, on the 2-dimensional sphere S2). We talk of a plane graph if such a drawing is already given and fixed. Any such drawing decomposes the plane or sphere into a finite number of connected regions, including the outer (unbounded) region, which are referred to as faces. Euler’s formula exhibits a beautiful relation between the number of vertices, edges and faces that is valid for any plane graph. Euler mentioned this result for the first time in a letter to his friend Goldbach in 1750, but he did not have a complete proof at the time. Among the many proofs of Euler’s formula, we present a pretty and “self-dual” one that gets by without induction. It can be traced back to von Staudt’s book “Geometrie der Lage” from 1847.

Martin Aigner, Günter M. Ziegler
Chapter 12. Cauchy’s rigidity theorem

A famous result that depends on Euler’s formula (specifically, on part (C) of the proposition in the previous chapter) is Cauchy’s rigidity theorem for 3-dimensional polyhedra.

Martin Aigner, Günter M. Ziegler
Chapter 13. Touching simplices

This is an old and very natural question. We shall call f(d) the answer to this problem, and record f (1) = 2, which is trivial. For d = 2 the configuration of four triangles in the margin shows f (2) ≥ 4. There is no similar configuration with five triangles, because from this the dual graph construction, which for our example with four triangles yields a planar drawing of K4, would give a planar embedding of K5, which is impossible (see page 67). Thus we have $$f(2) = 4$$.

Martin Aigner, Günter M. Ziegler
Chapter 14. Every large point set has an obtuse angle

Around 1950 Paul Erdös conjectured that every set of more than 2dpoints in ℝd determines at least one obtuse angle,that is, an angle that is strictly greater than $$\frac{\pi }{2}$$. In other words, any set of points in ℝdwhich only has acute angles (including right angles) has size at most 2d. This problem was posed as a “prize question” by the Dutch Mathematical Society — but solutions were received only for d = 2 and for d = 3.

Martin Aigner, Günter M. Ziegler
Chapter 15. Borsuk’s conjecture

Karol Borsuk’s paper “Three theorems on the

n

-dimensional euclidean sphere” from 1933 is famous because it contained an important result (conjectured by Stanislaw Ulam) that is now known as the Borsuk-Ulam theorem:

Every continuous map f: S

d

→ ℝ

d

maps two antipodal points of the sphere S

d

to the same point in ℝ

d

.

Martin Aigner, Günter M. Ziegler

Analysis

Frontmatter
Chapter 16. Sets, functions, and the continuum hypothesis

Set theory, founded by Georg Cantor in the second half of the 19th cen¬tury, has profoundly transformed mathematics. Modern day mathematics is unthinkable without the concept of a set, or as David Hilbert put it: “Nobody will drive us from the paradise (of set theory) that Cantor has created for us.”

Martin Aigner, Günter M. Ziegler
Chapter 17. In praise of inequalities

Analysis abounds with inequalities, as witnessed for example by the famous book “Inequalities” by Hardy, Littlewood and Pólya. Let us single out two of the most basic inequalities with two applications each, and let us listen in to George Pólya, who was himself a champion of the Book Proof, about what he considers the most appropriate proofs.

Martin Aigner, Günter M. Ziegler
Chapter 18. A theorem of Pólya on polynomials

Among the many contributions of George Pólya to analysis, the following has always been Erdős’ favorite, both for the surprising result and for the beauty of its proof. Suppose that $$ f(z) = {z^n} + {b_{n - 1}}{z^{n - 1}} + \cdots + {b_0}$$ is a complex polynomial of degree n ≥ 1 with leading coefficient 1. Associate with f(z) the set $$ C: = \left\{ {z \in :\left| {f(z)} \right| \le 2} \right\}$$ that is, Cis the set of points which are mapped under / into the circle of radius 2 around the origin in the complex plane. So for n = 1 the domain C is just a circular disk of diameter 4.

Martin Aigner, Günter M. Ziegler
Chapter 19. On a lemma of Littlewood and Offord
Martin Aigner, Günter M. Ziegler
Chapter 20. Cotangent and the Herglotz trick

What is the most interesting formula involving elementary functions? In his beautiful article [2], whose exposition we closely follow, Jiirgen Elstrodt nominates as a first candidate the partial fraction expansion of the cotangent function $$ \pi \cot \pi x = \frac{1}{x} + \sum\limits_{n = 1}^\infty {\left( {\frac{1}{{x + n}} + \frac{1}{{x - n}}} \right)\,(x \in } \backslash )$$.

Martin Aigner, Günter M. Ziegler
Chapter 21. Buffon’s needle problem

A French nobleman, Georges Louis Leclerc, Comte de Buffon, posed the following problem in 1777:

Suppose that you drop a short needle on ruled paper — what is then the probability that the needle comes to lie in a position where it crosses one of the lines?

Martin Aigner, Günter M. Ziegler

Combinatorics

Frontmatter
Chapter 22. Pigeon-hole and double counting

Some mathematical principles, such as the two in the title of this chapter, are so obvious that you might think they would only produce equally obvious results. To convince you that “It ain’t necessarily so” we illustrate them with examples that were suggested by Paul Erdös to be included in The Book. We will encounter instances of them also in later chapters.

Martin Aigner, Günter M. Ziegler
Chapter 23. Three famous theorems on finite sets

In this chapter we are concerned with a basic theme of combinatorics: properties and sizes of special families F of subsets of a finite set N = {1, 2, … , n}. We start with two results which are classics in the field: the theorems of Sperner and of Erdös-Ko-Rado. These two results have in common that they were reproved many times and that each of them initiated a new field of combinatorial set theory. For both theorems, induction seems to be the natural method, but the arguments we are going to discuss are quite different and truly inspired.

Martin Aigner, Günter M. Ziegler
Chapter 24. Shuffling cards

The analysis of random processes is a familiar duty in life (“How long does it take to get to the airport during rush-hour?”) as well as in mathematics. Of course, getting meaningful answers to such problems heavily depends on formulating meaningful questions. For the card shuffling problem, this means that we have to specify the size of the deck (n = 52 cards, say),to say how we shuffle (we’ll analyze top-in-at-random shuffles first, and then the more realistic and effective riffle shuffles), and finallyto explain what we mean by “is random” or “is close to random.”

Martin Aigner, Günter M. Ziegler
Chapter 25. Lattice paths and determinants

The essence of mathematics is proving theorems and so, that is what mathematicians do: They prove theorems. But to tell the truth, what they really want to prove, once in their lifetime, is a Lemma, like the one by Fatou in analysis, the Lemma of Gauss in number theory, or the BurnsideFrobenius Lemma in combinatorics.

Martin Aigner, Günter M. Ziegler
Chapter 26. Cayley’s formula for the number of trees

One of the most beautiful formulas in enumerative combinatorics concerns the number of labeled trees. Consider the set N = {1, 2,…, n}. How many different trees can we form on this vertex set? Let us denote this number by Tn.

Martin Aigner, Günter M. Ziegler
Chapter 27. Completing Latin squares

Some of the oldest combinatorial objects, whose study apparently goes back to ancient times, are the

Latin squares

. To obtain a Latin square, one has to fill the

n

2

cells of an (

n

x

n

)-square array with the numbers 1,2,…,

n

so that that every number appears exactly once in every row and in every column. In other words, the rows and columns each represent permutations of the set {1,…,

n}.

Let us call

n

the

order

of the Latin square. Here is the problem we want to discuss. Suppose someone started filling the cells with the numbers {1, 2,…,

n

}. At some point he stops and asks us to fill in the remaining cells so that we get a Latin square. When is this possible? In order to have a chance at all we must, of course, assume that at the start of our task any element appears at most once in every row and in every column. Let us give this situation a name. We speak of a

partial Latin square

of order

n

if some cells of an (

n

x

n

)-array are filled with numbers from the set {1,…,

n

} such that every number appears at most once in every row and column. So the problem is:

When can a partial Latin square be completed to a Latin square of the same order?

Martin Aigner, Günter M. Ziegler
Chapter 28. The Dinitz problem

The four-color problem was a main driving force for the development of graph theory as we know it today, and coloring is still a topic that many graph theorists like best. Here is a simple-sounding coloring problem, raised by Jeff Dinitz in 1978, which defied all attacks until its astonishingly simple solution by Fred Galvin fifteen years later.

Martin Aigner, Günter M. Ziegler
Chapter 29. Identities versus bijections

Consider the infinite product (1 + x)(1 + x2)(1+ x3)(1+ x4) … and expand it in the usual way into a series $$\sum {_{n \geqslant 0}{a_n}{x^n}} $$ by grouping together those products that yield the same power xn. By inspection we find for the first terms (1)$$\prod\limits_{k \geqslant 1} {\left( {1 + {x^k}} \right) = 1 + x + {x^2} + 2{x^3} + 2{x^4} + 3{x^5} + 4{x^6} + 5{x^7} + ....} $$ So we have e. g. a6 = 4 a7 = 5, and we (rightfully) suspect that a n goes to infinity with n→ ∞.

Martin Aigner, Günter M. Ziegler

Graph Theory

Frontmatter
Chapter 30. Five-coloring plane graphs

Plane graphs and their colorings have been the subject of intensive research since the beginnings of graph theory because of their connection to the four-color problem. As stated originally the four-color problem asked whether it is always possible to color the regions of a plane map with four colors such that regions which share a common boundary (and not just a point) receive different colors. The figure on the right shows that coloring the regions of a map is really the same task as coloring the vertices of a plane graph. As in Chapter 11 (page 65) place a vertex in the interior of each region (including the outer region) and connect two such vertices belonging to neighboring regions by an edge through the common boundary.

Martin Aigner, Günter M. Ziegler
Chapter 31. How to guard a museum

Here is an appealing problem which was raised by Victor Klee in 1973. Suppose the manager of a museum wants to make sure that at all times every point of the museum is watched by a guard. The guards are stationed at fixed posts, but they are able to turn around. How many guards are needed?

Martin Aigner, Günter M. Ziegler
Chapter 32. Turán’s graph theorem

One of the fundamental results in graph theory is the theorem of Turán from 1941, which initiated extremal graph theory. Turán’s theorem was rediscovered many times with various different proofs. We will discuss five of them and let the reader decide which one belongs in The Book.

Martin Aigner, Günter M. Ziegler
Chapter 33. Communicating without errors

In 1956, Claude Shannon, the founder of information theory, posed the following very interesting question:

Suppose we want to transmit messages across a channel (where some symbols may be distorted) to a receiver. What is the maximum rate of transmission such that the receiver may recover the original message without errors?

Martin Aigner, Günter M. Ziegler
Chapter 34. Of friends and politicians

It is not known who first raised the following problem or who gave it its human touch. Here it is:

Suppose in a group of people we have the situation that any pair of persons have precisely one common friend. Then there is always a person (the “politician”) who is everybody’s friend.

Martin Aigner, Günter M. Ziegler
Chapter 35. Probability makes counting (sometimes) easy

Just as we started this book with the first papers of Paul Erdos in number theory, we close it by discussing what will possibly be considered his most lasting legacy — the introduction, together with Alfred Résnyi, of the

probabilistic method

. Stated in the simplest way it says:

If, in a given set of objects, the probability that an object does not have a certain property is less than 1, then there must exist an object with this property.

Martin Aigner, Günter M. Ziegler
Backmatter
Metadaten
Titel
Proofs from THE BOOK
verfasst von
Martin Aigner
Günter M. Ziegler
Copyright-Jahr
2004
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-05412-3
Print ISBN
978-3-662-05414-7
DOI
https://doi.org/10.1007/978-3-662-05412-3