Erdős for Epsilons: “The Boy Who Loved Math”

“If I invent time travel, will I be as famous as Paul Erdős?”

My daughter asked me this question after I’d read to her (for the nth time) the charming picture book “The Boy Who Loved Math: The Improbable Life of Paul Erdos“, with text by Deborah Heiligman and pictures by LeUyen Pham.

“The Boy Who Loved Math” (front cover). Artwork © LeUyen Pham 2013.

Erdős started life in a middle-class family in Hungary, achieving early renown as “The Magician of Budapest“, and ended his life unsalaried and homeless. That might sound like a downward career arc, but in fact the Erdős story is a success story, a tale of early promise fulfilled: by the time he left our world in 1996, he was one of the most widely-known mathematicians of the twentieth century, and was living exactly the way he wanted. He spent his life on the road, collaborating with hundreds of other mathematicians and giving inspiring talks about unsolved problems (usually his own) before moving on to the next stop on his endless tour. (Never mind who got Einstein’s office; I want to know who got Erdős‘ frequent flier miles.) He pioneered the mathematical study of networks known as graph theory — indeed, his penchant for promiscuous coauthorship with mathematicians who in turn coauthored papers with others gave rise to a network of exactly the sort that graph theory has been so helpful in dealing with. Long before actors had Kevin Bacon numbers, mathematicians had Erdős numbers.

Paul Erdős, with a young Terence Tao

Erdős also made important contributions to number theory and probability theory; some of his contributions were answers, while others were incisive questions. Many mathematicians got their first taste of fame by being the person who cracked an “Erdős problem”.

You can learn about Erdős‘ life from full-length biographies by Paul Hoffman and Bruce Schechter, as well as George Csicsery’s film “N is a Number” (see the References below). Now the book by Heiligman and Pham brings Erdős‘ life story to a new audience whose company Erdős always found congenial: “epsilons” (that’s Erdős-speak for “children”).

The subtitle “The Improbable Life of Paul Erdős” is a well-earned pun, describing not only one of the man’s chief areas of interest but also the way he lived. Without the benefit of hindsight, his choice of lifestyle seems unlikely to be sustainable. Can one survive in the academic world without a job or a source of income or a home, endlessly crowdsurfing from one university to another, buoyed up by willing hands in some sort of world-wide mathematical mosh pit? If a young person came to me and announced his or her intention of having this kind of career, I would strenuously advise against it. It’s fortunate nobody told Erdős (or if they did, it’s fortunate he didn’t listen) that there was no such profession. He went on to create it for himself.

Erdős‘ story is one we might think we don’t need to hear, because we’ve heard so many stories like it: a boy shows brilliance at an early age and goes on to make fundamental contributions to science despite his lack of social graces. Stories like that, when promulgated so much more broadly than other kinds of stories, perpetuate a stereotype of scientists that subtly tells girls (and non-prodigies) “This is what science looks like, and it doesn’t look like you.” But the book shows lots of other mathematicians, men and women who work in the network that Erdős created, leading fairly traditional lives, and the book makes it clear that they, and not Erdős, are the norm in the world of mathematics. Erdős “invented his own way to live” because traditional choices didn’t fit with his desire to build a life entirely around mathematics, but most of us who make a living practicing mathematics, even practicing it passionately, still prefer to live lives that are less one-sided.

One thing that distinguishes the Erdős story from others of the genre is the man’s generosity, both financial and mathematical; he would give away earnings and ideas as quickly as they came to him. Young Glen Whitney was one such beneficiary; in the late 1980s, a gift of $1000 from Erdős made it possible for Whitney to study mathematics at Harvard. Years later, when Whitney had finished a Ph.D. and gone on to a successful career in finance and tried to repay the loan, Erdös refused to accept the money, telling Whitney to pay it forward rather than pay it back. Whitney went on to do just that, devoting not just his money but his time to the mission of creating a museum of mathematics for young people.

So, even though Erdős was the recipient of many people’s generosity in practical matters, he found his own way to repay their care. Still, some of you may feel that the book, through its focus on Erdős and its stress on his idiosyncrasies, runs the risk of instilling restrictive stereotypes of mathematicians. If you’ve read the book, I’d like to know what you think about this issue. (There’s a reason this blog has a comments section!)

Heiligman and Pham have done an impressive job of getting small details right, even details that will matter to only a handful of readers. For instance, Pham’s pictures of the many mathematicians who were part of Erdös’ circle actually look a lot like the mathematicians in question. You may not have met Fan Chung (for instance), but those of us who have, and who read this book to our kids, will smile and say “That’s just what she looks like!”, and feel grateful that the illustrator took the time to capture so many people’s likenesses with such lively fidelity.

Also, the notes at the back of the book provide some details missing from the main text, such as the fact that it was Erdős‘ father who launched him on his life-long obsession with prime numbers by introducing them to the boy. Taking my cue from Erdős senior, I showed both of my kids how to use the sieve of Eratosthenes to find all primes under 100, as shown on page 13; both of them found the experience fun and empowering.

RAMSEY THEORY AND THE PROBABILISTIC METHOD

Figure 1

One of many formulas in the book, and one with special significance in Erdös’ life, is the condition

For values of n and k that satisfy the condition, the inequality has a surprising implication in a branch of mathematics called Ramsey theory. (A good place to learn about the subject is Martin Gardner’s essay “Ramsey Theory” listed in the References.) Figure 1 shows 5 dots arranged in a circle, joined by 10 line segments. (I’ll call a dot a “vertex” and a line segment an “edge”, as is customary. Places where two edges cross aren’t considered vertices.) Since each pair of points is joined by an edge, we call this a complete graph on 5 vertices, or a K₅ for short. Some of the edges are blue; the others are red. If you look at any three vertices in the picture, you’ll be able to check that the edges joining the three  vertices are neither all red nor all blue. That is, the picture does not contain a “monochromatic K₃“. (If you think you see three vertices forming a monochromatic K₃, remember that places where two edges cross aren’t considered vertices.)

Figure 2

More generally, we’ll use “K_n” to denote a collection of n vertices (having no three in a line) with each pair joined by an edge. Figure 1 demonstrates that it’s possible to have a red-and-blue-colored K₅ that contains no monochromatic K₃. Likewise, Figure 2 demonstrates that it’s possible to have a red-and-blue-colored K₆ that contains no monochromatic K₄. The dark magic of Erdos’ formula is that in many cases, it gives us a way to rigorously conclude that such configurations exist without drawing any pictures at all.

To see how the magic works, let’s revisit the problem that Figure 2 solves, and solve it in a curiously roundabout way. Imagine that instead of assigning the colors red and blue to the edges of a K₆ in some systematic fashion, we color the edges randomly (using an unbiased coin). What is the chance that our random coloring will fail to be free of monochromatic K₄‘s? That is: What is the chance that we’ll randomly construct a coloring of our K₆ that has at least one monochromatic K₄? Let’s break this down into sub-questions, such as: what is the chance that vertices a, b, c, and d will form a blue K₄? That is, what is the probability that the six edges ab, ac, ad, bc, bd, and cd are all blue? The answer to this sub-question is 1/2 × 1/2 × 1/2 × 1/2 × 1/2 × 1/2, or 1/2 to the sixth power (with one factor of 1/2 for each of the six edges that must all be blue), or 1/64. Likewise the chance that vertices a, b, c, and d will form a red K₄ is 1/64, so the chance that vertices a, b, c and d will form a monochromatic K₄ (blue or red) is 1/64 + 1/64 = 1/32.

But a, b, c, d is only one possible foursome. If we change the sub-question by replacing a,b,c,d by some other set of four vertices, the answer will still be 1/32. So what is the chance that at least one such foursome will host a monochromatic K₄? The number of foursomes is 15 (see the End Notes for why), and for each foursome the chance of being monochromatic is 1/32, so the chance that at least one of the 15 foursomes will host a monochromatic K₄ is at most 1/32 + 1/32 + … + 1/32 (that is, the sum of 15 terms equal to 1/32), which equals 15/32. (Don’t make the mistake of thinking that the chance is exactly 15/32; this would ignore the fact that it’s possible for several foursomes to host K₄‘s simultaneously. If you’re still wondering why we add up 15 terms equal to 1/32, see the End Notes.) Now comes the punchline: since we’ve shown that the chance of there being one or more monochromatic K₄‘s is at most 15/32, the chance of our randomly constructed coloring being free of K₄‘s is at least 1 minus 15/32, or 17/32. But that tells us (if we didn’t already know it from Figure 2) that there must exist at least one red-and-blue coloring of K₆ with no monochromatic K₄‘s in it; if there weren’t, the chance of our obtaining one from a random coloring would be 0, not 17/32 or greater.

Page 29 of “The Boy Who Loved Math”. Artwork © LeUyen Pham 2013.

You might want to read that paragraph again; if you didn’t find it unsettling, you probably didn’t understand it. This kind of proof (one that uses what’s called the Probabilistic Method) is deeply strange. Don’t confuse it with the kind of “probabilistic proof” that, under certain assumptions, is supposed to convince you that such-and-such a result is probably true. The method I’ve shown you gives you 100% certainty that such-and-such a result is true. It just does it in a disquieting way that leaves you less than 100% satisfied.

This underhanded method of proving that certain mathematical objects exist really comes into its own when big numbers are involved. Let’s say that (for some reason) you really want to know whether there exists a red-and-blue coloring of a K₁₀₀ with no monochromatic K₁₀. You wish with all your heart for a proof. In a flash there appears before you the demonic figure from Hungarian folklore called the Ördög, who offers to give you, in exchange for something you hold dear (of course!), a proof that such a coloring exists. You accept the deal, at which point the Ördög summons up a demonically wide calculator and begins to punch some buttons. “Okay, suppose we color our K₁₀₀ randomly, deciding the color of each of the 4,950 edges with a coin toss. Then the probability of any particular set of 10 vertices, with 45 edges, forming a monochromatic K₁₀ is 2/2⁴⁵ which is, let’s see, 1/17,592,186,044,416, while the number of 10-vertex families to worry about is 100-choose-10, which is, hold on a moment, 17,310,309,456,440. So the probability that our random coloring will give rise to one or more monochromatic K₁₀‘s is at most 17,310,309,456,440 / 17,592,186,044,416, or about .9769. That number is strictly less than 1, so there must exist at least one red-and-blue coloring of K₁₀₀ with no monochromatic K₁₀‘s in it.” The Ördög has held up his end of the bargain by proving that such a coloring exists, even though his argument gives you no idea whatsoever of how to find one! You are in the spooky situation of possessing a rigorous argument that shows you that a certain kind of mathematical object exists, but provides you no clues as to how to find it. Surely this isn’t what you expected the Ördög to provide you with when you wished for a proof. But it is what you asked for.

The situation is even more offensive to one’s sense of mathematical fair play than that. Let’s say you were to toss coins as the Ördög prescribed and you feel in your bones that you lucked out, obtaining a coloring of K₁₀₀ that’s free of monochromatic K₁₀‘s; how could you convince yourself that you’d succeeded? The obvious approach would be to check all 17,310,309,456,440 K₁₀‘s, to make sure none of them has been colored monochromatically. That clearly isn’t feasible. So not only have you been given an existence proof that provides no guidance for how to find what you’re looking for, but you also have no computationally feasible way of recognizing what you’re looking for even if it’s right in front of you!

THE ERDOS-TURAN CONJECTURE

Let’s end our brief tour of Erdős’ work with an example of an unsolved Erdős problem that’s so important that LeUyen Pham (on advice from her informant Ron Graham) chose to depict a fragment of it on page 29, above the Ramsey theory formula I discussed earlier:

S contains a k-AP for every k

You should imagine a big question mark hanging over that symbol (“implies”), because nobody currently knows whether the implication is true; that’s what Erdős wanted to know! Here “k-AP” means k-term arithmetic progression. For example, 5,11,17,23 is a 4-AP. It’s not a coincidence that I chose a 4-AP whose terms are all primes. Erdős noticed that the primes contain many such arithmetic progressions, and he wondered how long an arithmetic progression in the primes could be. Might the primes contain arithmetic progressions of length k, for each positive integer k? Erdős suspected that the answer was “yes”, but he suspected more. There’s an important way in which the set of primes, aside from being an infinite set, is “big”: the sum of the reciprocals of the primes diverges (that is, the infinite sum 1/2 + 1/3 + 1/5 + 1/7 + … eventually exceeds any pre-selected threshhold of “bigness” you may choose, if you include enough terms in the sum). Erdős, building on an earlier conjecture he’d made with Paul Turán, boldly conjectured that whenever a set of positive integers is big in this sense, it must contain k-AP’s for all positive integers k.

In a landmark result, Terence Tao (no longer the kid pictured above) and Ben Green bypassed the Erdős-Turán conjecture and showed that for every positive integer k, the set of primes contains a k-term arithmetic progression. This result caused a huge sensation in the mathematical world, and clinched most people’s opinion that the still-under-forty Tao, whose earlier work had marked him as one of the premier mathematicians of his generation, was likely to win a Fields Medal the next time the prize was awarded, as indeed he did. Yet I suspect that if Erdős had been around, he would have told Green and Tao “That is an extremely nice result, but it only applies to the set of primes, and maybe some other sets of a similar kind. Could you please now prove my conjecture?”

“The Boy Who Loved Math” (back cover). Artwork © LeUyen Pham 2013.

Actually, Erdős had a better strategy for steering the course of mathematics than just asking people to solve the problems he cared about: he offered prize money, and for a proof of the Erdős-Turán conjecture he offered a $3000 jackpot. Before Erdős‘ death, and afterwards, other people managed his finances for him, and contributed to the kitty as needed; so if anyone ever proves the conjecture, the reward is still there, and is worth about $5000. Unfortunately, there is no reward for disproving the conjecture!

Next time: A review of “Really Big Numbers” by Richard Schwartz.

This article was written with help from John Baez, Tibor Beke, Ron Graham, Sandi Gubin (who suggested the title), Vickie Kearn, Joe Malkevitch, Henri Picciotto, Richard Schroeppel, Richard Schwartz, and James Tanton. Thanks to Deborah Heiligman and LeUyen Pham for permission to include pictures from their book.

END NOTES

Why, in a set of six vertices, are there 15 foursomes?  If you’ve got six vertices, and you want to choose four of them to include in a foursome, that’s equivalent to choosing two of them to exclude from the foursome. So the number of foursomes is the same as the number of pairs. And why is the number of pairs 15? You might think that the number of pairs would be 6 × 5, or 30, because there are 6 ways to choose the first vertex, and then for each choice of the first vertex, there are 5 ways to choose the second vertex. But this ignores the fact that the edge joining vertex x to vertex y is the same as the edge joining vertex y to vertex x. Or putting it differently, when an edge passes through two vertices, there’s no “first” or “second” vertex on the edge, and by pretending otherwise, we’ve overcounted the edges by a factor of 2. So the correct answer is half of 30, or 15.

The question “In a set of n vertices, how many k-element subsets are there?” is so central in mathematics that the answer has its own symbol: , pronounced “n choose k“. There’s a nice formula for it: it’s n! divided by k!(n–k)!, where m! (pronounced “m factorial“) signifies 1 × 2 × 3 × … × m. The number of edges in a K_k is   (e.g., and ), so if one randomly colors the edges of a K_k red and blue, the chance that all edges will be the same color is , or . There are only different k-element subsets that could turn out to be colored monochromatically, so the chance of there being at least one monochromatic K_k in a red-and-blue colored K_n is at most times . In the case where n is 100 and k is 10, this product is just slightly less than 1.

Some readers of the first version of this essay wondered why we add 15 terms equal to 1/32. “Isn’t there a different formula for computing probabilities that at least one of several listed events will occur?” Yes, there is an exact formula, but it only applies when the events are known to be statistically independent. In the absence of statistical independence, the equation you might be thinking of doesn’t apply. Fortunately, we can still obtain an inequality that will serve our purpose. A homely analogy with predicting weather will serve: if the chance of rain tomorrow is 20%, and the chance of snow tomorrow is 25%, then the chance of rain-or-snow tomorrow is at most 20%+25%, or 45%. It might be smaller than the sum of the two probabilities, but it can’t be larger! In the same way, if you buy 15 lottery tickets, but each has only 1/32 chance of winning, then the chance that one or more of your tickets will be a winner is at most 15/32. Change winning tickets into monochromatic K₄‘s and you’ve got the wacky argument I used to prove that some blue/red-colored K₆ must be free of monochromatic K₄‘s.

If you have a hard time with probability but are good at counting, there’s a way to recast the Ördög’s argument that doesn’t involve any mention of randomness. We ask the question “How many colorings of a K₁₀₀ have at least one monochromatic K₁₀?”, and we show that the answer is strictly less than the total number of red-blue colorings. This implies that there exists at least one red-blue coloring of a K₁₀₀ with no monochromatic K₁₀‘s in it.  More broadly, whenever 2 times is smaller than 2 to the power of , there exists at least one red-blue coloring of a K_n with no monochromatic K_k‘s in it.Like the probability-based proof, this counting-based proof gives us no clue how to actually find such a coloring. Some proofs that use Erdős‘ probabilistic method can be reformulated as counting arguments. Other applications of Erdős‘ method are harder to rephrase in non-probabilistic terms.

REFERENCES

George Csicsery, “N Is a Number: A Portrait of Paul Erdős“.

Martin Gardner, “Ramsey Theory”, in “Penrose Tiles to Trapdoor Ciphers and the Return of Dr. Matrix”.

Deborah Heiligman and LeUyen Pham, “The Boy Who Loved Math: The Improbable Life of Paul Erdos“.

Paul Hoffman, “The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth” .

Bruce Schechter, “My Brain is Open: The Mathematical Journeys of Paul Erdős“.