Proofs from THE BOOK

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.

But there are also upper bounds for the gaps in the sequence of prime numbers. A famous bound states that “the gap to the next prime cannot be larger than the number we start our search at.”

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:

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.

Which famous mathematical theorem has been proved most often? Pythagoras would certainly be a good candidate or the fundamental theorem of algebra, but the champion is without doubt the law of quadratic reciprocity in number theory. In an admirable monograph Franz Lemmermeyer lists as of the year 2000 no fewer than 196 proofs. Many of them are of course only slight variations of others, but the array of different ideas is still impressive, as is the list of contributors. Carl Friedrich Gauss gave the first complete proof in 1801 and followed up with seven more. A little later Ferdinand Gotthold Eisenstein added five more — and the ongoing list of provers reads like a Who is Who of mathematics.

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 noncommutative 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.

A fundamental theorem of linear algebra asserts that every symmetric real matrix A can be diagonalized.

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.

This is a classical, famous and important result by Leonhard Euler from 1734. One of its key interpretations is that it yields the first nontrivial value ζ(2) of Riemann’s zeta function (see the appendix on page 62). This value is irrational, as we have seen in Chapter 8.

This problem can be traced back to two letters of Carl Friedrich Gauss from 1844 (published in Gauss’ collected works in 1900). If tetrahedra of equal volume could be split into congruent pieces, then this would give one an “elementary” proof of Euclid’s theorem XII.5 that pyramids with the same base and height have the same volume. It would thus provide an elementary definition of the volume for polyhedra (that would not depend on continuity arguments).

Whether Sylvester himself had a proof is in doubt, but a correct proof was given by Tibor Gallai [Grünwald] some 40 years later. Therefore the following theorem is commonly attributed to Sylvester and Gallai. Subsequent to Gallai’s proof several others appeared, but the following argument due to L. M. Kelly may be “simply the best.”

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 11 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.

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.

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.

The “Borromean rings” — three rings arranged so that no two of them are linked, but the configuration cannot be taken apart without breaking one of the rings — form a classic artistic symbol, which appeared in the coat of arms of the aristocratic Borromeo family since the middle of the 15th century.

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 K₄, would give a planar embedding of K₅, which is impossible (see page 91).

Around 1950 Paul Erdős conjectured that every set of more than 2d points 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 ℝd which 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.

We will see the full power of this theorem in a graph theory application in Chapter 43. The paper is famous also because of a problem posed at its end, which became known as Borsuk’s Conjecture:

Set theory, founded by Georg Cantor in the second half of the 19th century, 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.”

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.

Gauss called this theorem, for which he gave four different proofs, the “fundamental theorem of algebraic equations.” It is without doubt one of the milestones in the history of mathematics. As Reinhold Remmert writes in his pertinent survey: “It was the possibility of proving this theorem in the complex domain that, more than anything else, paved the way for a general recognition of complex numbers.”

Now, this looks like a classical question of Euclidean geometry, and one could have guessed that surely the answer must have been known for a long time (if not to the Greeks). But when Fred Richman and John Thomas popularized the problem in the 1960s they found to their surprise that no one knew the answer or a reference where this would be discussed.

Among the many contributions of George Polya to analysis, the following has always been Erdős’ favorite, both for the surprising result and for the beauty of its proof.

In contrast to the determinant, which can be quickly calculated (e.g. by Gaussian elimination), computation of the permanent is provably difficult. Therefore a lot of research about permanents concerned bounds and approximation; the book by Minc [7] gives an excellent overview of the subject.

A few years later Paul Erdős improved this bound by removing the log n term, but what is more interesting, he showed that this is, in fact, a simple consequence of the theorem of Sperner (see page 213).

What is the most interesting formula involving elementary functions? In his beautiful article [2], whose exposition we closely follow, Jürgen Elstrodt nominates as a first candidate the partial fraction expansion of the cotangent function:

The probability depends on the distance d between the lines of the ruled paper, and it depends on the length ℓ of the needle that we drop — or rather it depends only on the ratio $$\frac{\ell}{d}$$ . A short needle for our purpose is one of length ℓ ≤ d. In other words, a short needle is one that cannot cross two lines at the same time (and will come to touch two lines only with probability zero). The answer to Buffon’s problem may come as a surprise: It involves the number π.

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.

Some mathematical theorems exhibit a special feature: The statement of the theorem is elementary and easy, but to prove it can turn out to be a tantalizing task—unless you open some magic door and everything becomes clear and simple.

In this chapter we are concerned with a basic theme of combinatorics: properties and sizes of special families $$\mathcal{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.

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.

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 Burnside– Frobenius Lemma in combinatorics.

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 T _n .

Infinite sums and products and their convergence have played a central role in analysis since the invention of the calculus, and contributions to the subject have been made by some of the greatest names in the field, from Leonhard Euler to Srinivasa Ramanujan.

This beautiful question was posed by the Japanese mathematician Sōichi Kakeya in 1917. It gained immediate prominence and, together with its higher-dimensional analogs, helped initiate a whole new field, today called geometric measure theory. To be precise, by “turning around” Kakeya had a continuous motion in mind that returns the needle to the original position with its ends reversed, like a Samurai whirling his pole. Any such motion takes place in a compact subset of the plane.

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 n2 cells of an n×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.

In Chapter 24 we discussed Van der Waerden’s conjecture, which established a lower bound for the permanent of a doubly stochastic matrix. There is also a wonderful theorem that gives an upper bound for integral matrices with prescribed row sums.

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.

Plane graphs and their colorings have been the subject of intensive research since the beginnings of graph theory because of their connection to the fourcolor 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 13 (page 89) 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.

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?

One of the fundamental results in graph theory is the theorem of Turan from 1941, which initiated extremal graph theory. Turan’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.

Let us see what Shannon meant by “channel” and “rate of transmission.” We are given a set V of symbols, and a message is just a string of symbols from V. We model the channel as a graph G = (V,E), where V is the set of symbols, and E the set of edges between unreliable pairs of symbols, that is, symbols which may be confused during transmission. For example, communicating over a phone in everyday language, we connnect the symbols B and P by an edge since the receiver may not be able to distinguish them. Let us call G the confusion graph.

In 1955 the number theorist Martin Kneser posed a seemingly innocuous problem that became one of the great challenges in graph theory until a brilliant and totally unexpected solution, using the “Borsuk–Ulam theorem” from topology, was found by László Lovász twenty-three years later.

Before tackling the proof let us rephrase the problem in graph-theoretic terms. We interpret the people as the set of vertices V and join two vertices by an edge if the corresponding people are friends. We tacitly assume that friendship is always two-ways, that is, if u is a friend of v, then v is also a friend of u, and further that nobody is his or her own friend.

Just as we started this book with the first papers of Paul Erdős in number theory, we close it by discussing what will possibly be considered his most lasting legacy — the introduction, together with Alfred Rényi, of the probabilistic method.