Paul Erdos and an Infinity of Problems

Paul Erdős (1913-1996) was arguably the supreme mathematical problem poser and solver of modern times. His interests were mainly in number theory and combinatorics, though they ranged into topology and other areas of mathematics. He was fascinated by relationships among numbers, and numbers served as the raw materials for many of his conjectures, questions, and proofs.

Born in Hungary in 1913, Erdős demonstrated a quick and nimble mind for mathematics at an early age. In a 1979 interview, he recalled: "It was fairly obvious that I could calculate very well when I was four. At that age, I told my mother that if you take away 250 from 100, you have 150 below 0." Entirely on his own, he had discovered negative numbers.

Erdős made his initial mark as a mathematician at the age of 18, when he discovered an elegant proof of the theorem that, for each integer greater than 1, there is always a prime number between it, n, and double the number, 2n. For example, the prime number 3 lies between 2 and 4. The interval between 10 and 2 x 10, or 20, has the prime numbers 13, 17, and 19.

Though Erdős wasn't the first to prove this theorem, his accomplishment was striking because it considerably improved upon a famous result. A little later, he proved his own theorem that there is always a prime of the form 4k + 1 and 4k + 3 between n and 2n. For example, the interval between 100 and 200 contains the prime-number pair 101 and 103 (k = 25).

In 1978, mathematician Ross Honsberger noted: "Paul Erdős has the theory that God has a book containing all the theorems of mathematics with their absolutely most beautiful proofs, and when [Erdős] wants to express particular appreciation of a proof, he exclaims, 'This is one from the book!'"

Erdős loved problems that people could understand without learning a mass of definitions. His hallmark was the deceptively simple, precisely stated problem and the succinct and ingenious argument to settle the issue. Though simply stated, however, his problems were often notoriously difficult to solve.

Here's a sample Erdős problem that concerns sequences of +1's and −1's. Suppose there are equal numbers of +1's and −1's lined up in a row. If there are two +1's and two −1's, for example, a row could consist of +1 +1 −1 −1. Because these terms can be listed in any order, there are in fact six different ways to write such a row.

Of course, the sum of all the numbers in a row is zero. However, it's interesting to look at the partial sums in each row. In the example above, the partial sums are +1 (after one term), +2 (after two terms), +1 (after three terms), and 0 (after four terms). The problem is to determine how many rows out of all the possibilities yield no partial sum that is negative.

Of the six different rows for n = 2, only two escape a negative partial sum. Of the 20 rows for n = 3, just five have exclusively nonnegative partial sums; for n = 4, 14 out of 70 rows have this particular characteristic; and so on. The answer turns out to be a sequence called the Catalan numbers: 1/(n + 1) times the number of different rows for n +1's and n −1's.

One can liken these rows to patrons lined up at a theater box office. The price of admission is 50 cents, and half the people have the exact change while the other half have one-dollar bills.Thus, each person provides one unit of change for the cashier's later use or uses up one unit of change. In how many ways can the patrons be lined up so that a cashier, who begins with no money of her own, is never stuck for change?

Erdős enjoyed offering monetary rewards for solving particular problems, ranging from $10,000 for what he called "a hopeless problem" in number theory to $25 for something that he considered not particularly difficult but still tricky, proposed in the middle of a lecture.

One problem worth a $3,000 reward concerns an infinite sequence of integers, the sum of whose reciprocals diverges. The conjecture is that such a sequence contains arbitrarily long arithmetic progressions.

"This would imply that the primes contain arbitrarily long arithmetic progressions," Erdős remarked. "This would be really nice. And I don't expect to have to pay this money, but I should leave some money for it in case I leave."

He continued parenthetically, "There I mean leave on the trip for which one doesn't need a passport."

Erdős had once remarked that mathematics is eternal because it has an infinity of problems. In the same spirit, his own contributions have enriched mathematics. Erdős problems—solved and unsolved—abound in the mathematical literature, lying in wait to provoke thought and elicit surprise.