Paul Erdos: An Infinity of Problems

Paul Erdos died of a heart attack on Sept. 20 at the age of 83. Considered by many as one of the great mathematicians of this century and certainly one of the most prolific ever, he will be missed.

For more than 50 years, Erdos wandered the globe visiting mathematicians, attending meetings, teaching, and lecturing. He had become the center of an enormous web of collaboration (see Groups, Graphs, and Paul Erdos).

"One never knew where Erdos was, not even the country," Richard Bellman wrote in Eye of the Hurricane. "However, one could be sure that during the year ... Erdos was everywhere. He was the nearest thing to an ergodic particle that a human being could be."

At his death, Erdos had more than 1,500 published papers to his credit. He was active to the last days of his life. At least 50 papers on which he is listed as a coauthor are yet to appear, representing the results of various recent collaborative efforts.

Erdos was the supreme problem poser and problem 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, Erdos 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.

Erdos 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 Erdos 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 Erdos has the theory that God has a book containing all the theorems of mathematics with their absolutely most beautiful proofs, and when [Erdos] wants to express particular appreciation of a proof, he exclaims, 'This is one from the book!'"

Erdos 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, not-so-difficult Erdos 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?

Erdos 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," Erdos 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."

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

References:

Albers, Donald J., and G.L. Alexanderson, editors. 1985. Mathematical People: Profiles and Interviews. Boston: Birkhauser.

Baker, A., B. Bollobas, and A. Hajnal, editors. 1991. A Tribute to Paul Erdos. Cambridge, England: Cambridge University Press.

Bellman, Richard. 1984. Eye of the Hurricane. Singapore: World Scientific.

Graham, R.L., and J. Nesetril. 1996. The Mathematics of Paul Erdos I. Berlin: Springer-Verlag.

Hoffman, Paul. 1987. The man who loves only numbers. Atlantic Monthly 260(November):60-74.

Honsberger, Ross. 1996.From Erdos to Kiev: Problems of Olympiad Caliber. Washington, D.C.: Mathematical Association of America.

______. 1985. Mathematical Gems III. Washington, D.C.: Mathematical Association of America.

______. 1978. Mathematical Morsels. Washington, D.C.: Mathematical Association of America.

Kolata, Gina. 1996. Paul Erdos, 83, a wayfarer at math's pinnacle, is dead. New York Times (Sept. 24).

Peterson, I. 1995. Progressing to a set of consecutive primes. Science News 148(Sept.9):167.

Tierney, John. 1984. Paul Erdos is in town. His brain is open. Science 84 (October): 40-47.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.