Erdös, Paul (Pál)

views updated May 29 2018

ERDöS, PAUL (PáL)

(b. Budapest, Hungary, 26 March 1923;

d. Warsaw, Poland, 20 September 1996), mathematics, number theory.

Erdös was a Hungarian mathematician who spent much of his life traveling and working with colleagues around the world on mathematical problems of many kinds. He published some 1500 papers, making him the most prolific major mathematician of the twentieth century, and had more than 450 collaborators and coauthors. His work falls into a number of fields, some of which he created, but which can mostly be embraced under the general heading of discrete mathematics, one of the major developments of twentieth-century mathematics. It also exerted a major influence on computer science, a field in which Erdös himself never worked.

Early Life . Erdös’s parents, Anna and Lajos Erdös, were both mathematics teachers, and he was brought up by his very protective mother, who was ever mindful of the fact that she had lost two daughters to scarlet fever just before Paul was born. His father was taken prisoner by the Russians during the World War I and sent to Siberia for six years. His parents kept Paul out of school after a few years to foster his evident talent, and at age twenty he became well known for finding an elegant new proof of a famous theorem in mathematics. This was Tchebychev’s theorem, which states that for every natural number n there is always a prime number between n and 2n. Erdös retained a lifelong interest in prime numbers; one of his best-known achievements is the so-called elementary proof of the prime number theorem that he and Atle Selberg published in 1949. The theorem says that the number of prime numbers less than x is approximately x/log x, as x gets larger and larger. Their proof is far from simple; it is elementary because it avoids the use of complex function theory, which is not needed for the statement of the theorem but is a central feature of most of its proofs. He and Selberg had planned to publish their proof in two papers in the same issue of a journal, but at the last minute Erdös changed his mind and published first. The next year, however, Selberg was awarded a Fields Medal for this and other achievements.

Erdös obtained his PhD from the University of Budapest in 1934 and came to the University of Manchester in England on a post-doctoral fellowship. It was by now clear that the Nazi takeover in Germany threatened the lives of Jews in Europe, and Erdös was able to leave for the United States. In the 1950s his political naivety caused him problems with the immigration authorities of the United States, and he emigrated to Israel, where he remained until the 1960s. Then, joined by his mother who was now in her eighties, Erdös began the extremely peripatetic life for which he became famous. He would arrive at a friend’s home, stay with him for a few days working exclusively on mathematics and talking about nothing else, and then move on by mutual agreement. Close friends, such as Ronald L. Graham, the director of the information sciences research center at AT&T Laboratories, who set aside a room in his house for Erdös, took care of the financial side of Erdös’s life; Graham was one of a number of people who provided Erdös with food and clothes and sorted out his tax returns. Erdös earned money from invitations to give lectures and work with mathematicians around the world, and usually donated it to struggling young mathematicians or gave it away in the form of prizes for the solution of problems he found particularly noteworthy. For example, when he won the Wolf Prize in 1983, which was then the most lucrative award available to mathematicians, he kept only $720 of the $50,000 prize.

Relations with Contemporaries . Erdös spoke of the world in a private language that reflected his cosseted upbringing. Thus SF (for Supreme Fascist) was his name for God, whom he regarded as a malign deity he believed had created the universe and tormented people; “epsilon” (traditionally a very small quantity in mathematics) was his name for a child—Erdös was very fond of children; and “bosses” his name for women, with whom he was less comfortable and who occasionally protested at the way people attracted to the cult around Erdös glossed over the sexism inherent in the term. Men were called “slaves” and people who had given up mathematics were said to have “died.” Erdös often spoke of what he called “The Book,” supposedly in the possession of the SF, in which were collected all the best proofs of all the important results in

mathematics, and which it was the job of mathematicians to discover. After his death mathematicians began to publish a book called Proofs from the Book, a compilation of exceptionally elegant proofs of various results.

It is fair to say that Erdös divided the mathematical community more than any other mathematician of his stature. To his friends and admirers, especially those who worked with him and who regarded their collaboration as a rare opportunity to experience a first-rate mathematical mind close up, he was one of the great mathematicians of the century if not of all time, to be compared with Leon-hard Euler for his originality. Others, while impressed, were less convinced. The disagreement goes back to a familiar tension in twentieth-century mathematics between the theory builders and the problem solvers. Much of the mathematics of the twentieth century, and indeed the nineteenth century, was conceptual and highly structured. Elaborate and profound general theories were constructed that are admired as much for their breadth of insight as for the problems they solve. The mathematicians most associated with this kind of mathematics, David Hilbert and his followers, especially Emmy Noether, and then the successive members of the Bourbaki group after World War II, not only promoted this style of mathematics through their own work but maintained it as the core activity of the mathematician. Erdös’s obsessive interest in problems that seemed to lack a general theory was completely the opposite of this and led some to see his contributions as remarkable and yet somehow marginal.

To make matters worse, his problems were mostly combinatorial and can be difficult without seeming deep. The large and difficult topic of differential equations, especially partial differential equations, is similarly full of difficult problems that yield only to delicate and often ad hoc analysis. It, too, is a branch of mathematics that has not been overwhelmed by the structural style of mathematics, but here no one disputes its depth or importance: Almost all of mathematical physics is written and studied in the language of partial differential equations. Lacking, apparently, depth and applications, Erdös’s problems could seem shallow and artificial, and his success in attracting interest in them even counterproductive. It was even suggested that by attracting so many Hungarian mathematicians to the pursuit of his problems he had unbalanced the whole study of mathematics in Hungary, which, before World War II, had been remarkable for its breadth and vigor. Erdös compounded the issue by his prizes and the fame that attached to anyone who solved one of his more challenging problems. The underlying significance of Erdös’s work seems likely to lie in concepts that he articulated only imperfectly and that his flurry of problem solving partly obscured.

Analytic Number Theory . The easiest way to see the depth of Erdös’s problems is to approach them via one of the most difficult and delicate branches of classical mathematics, analytic number theory, in which Erdös was profoundly immersed. The prime number theorem is just one of a large collection of results that make claims about the number of numbers less than some bound n with a specific property as the bound n increases indefinitely. It says, as was noted above, that the number of prime numbers less than x is well approximated by x / log x . It is well known that the sum of the reciprocals of the integers is infinite, but the sum of the reciprocals of the squares (1/1 + 1/4 + 1/9 + …) is finite (a result first established by Euler). This gives a way of saying that although there are infinitely many square numbers they form a rather sparse subset of the set of all integers. What about the prime numbers? In fact, as Euler also showed, the sum of the reciprocals of the primes is also infinite, which says not only that there are infinitely many primes but that they are rather numerous, and more numerous than the squares, according to the ways in which number theorists distinguish between the “sizes” of infinite sets.

Now consider an arithmetic progression, which is a set of numbers of the form a + bk, k = 0, 1, 2,… where a and b are positive integers with no common factor (so for example one might have a = 6 and b = 35). In 1927 Bartel van der Waerden proved that if the natural numbers are divided into k subsets then at least one of these sets contains arbitrarily long arithmetic progressions. Erdös and Paul Turan then conjectured in 1936 that any subset of the natural numbers that has positive density contains arbitrarily long arithmetic progressions. (To say that a subset A of the natural numbers has positive density is to say that as n increases indefinitely, the ratio of the number of numbers less than n that are in A to the number of numbers less than n tends to a limit greater than zero.) This result was proved in 1974 by the Hungarian mathematician Emre Szemeredi, for which he was awarded $1,000 by Erdös. But the prime numbers thin out; they do not form a set of positive density, and in 1936 Erdös and Turan had also asked if any subset of the natural numbers with the property that the sum of its reciprocals is infinite also contains arbitrarily long arithmetic progressions. This is a profound generalization of the earlier conjecture, one that would locate a deep property of prime numbers in a more general setting.

In 2006 the young mathematician Terence Tao was awarded a Fields Medal for solving many remarkable problems in diverse areas of mathematics; one of these was his work with Ben Green that shows that the set of prime numbers does indeed contain arbitrarily long arithmetic progressions. Erdös and Turan’s question remains unsolved in general.

So Erdös reminded mathematicians of how little they know about prime numbers despite all their grand theorems. The prime numbers are the building blocks of arithmetic, and Erdös’s remarkable insights into their properties led not only to good theorems but directed mathematicians back to the task of exploring this core part of their subject.

Erdös’s understanding of analytic number theory also helped create what has come to be called probabilistic number theory. In September 1939 he was at Princeton University listening to a lecture by Mark Kac on the behavior of the function that counts the number of prime divisors of a number. Heuristically, Kac regarded divisibility by 2, 3, 5 and so on as independent events and treated this function using ideas from probability theory. He suggested that the distribution of the number of prime divisors was a normal distribution, which would considerably sharpen some classical results in number theory, but was unable to prove it. Before the lecture was over Erdös had used his knowledge of what are called sieve methods to establish Kac’s conjecture. Ever since, probabilistic methods have spread in analytic number theory to the mutual advantage of both subjects. Ironically, Erdös’s knowledge of probability theory matched Kac’s grasp of number theory: Erdös did not even know the central limit theorem at that time.

Combinatorics . Another of Erdös’s major achievements is that he established combinatorial questions in mathematics as a central, new field of enquiry. The subject was reinvented in the decades after World War II, having become unfashionable. Whereas others may have done as much to reinvigorate the connections between combinatorics and other branches of mathematics that have their roots in the work of the previous two centuries, Erdös directed attention to novel but equally significant questions in the subject. Here two topics stand out: Ramsey theory and Random graphs.

Ramsey theory was initiated by the English mathematician Frank Plumpton Ramsey, and concerns problems that ask for the smallest set of objects in which a certain pattern must appear. For example, how many people must there be in a room together before one can be certain that at least two have the same sex? Here the answer is obviously three. How many people must there be in a room together before one can be certain that either three know each other or three do not (assuming that if Jack knows Jill then Jill knows Jack)? Here the answer is six, but the way to prove this is not to list all the sets of three there can be, because there are a lot. The same problem can be asked for foursomes, and here Erdös, Graham, and others proved that the answer is 18, but all that is known for fivesomes is that the answer lies between 43 and 49. Erdös discovered profound implications of Ramsey theory in the study of graphs, both finite graphs and, perhaps more remarkably, infinite graphs.

Whenever it is asked if an infinite graph has a certain property, it is likely that the question turns into one about the independence, or otherwise, of this or a related property from the fundamental axioms of set theory (usually ZFC or Zermelo-Frankel set theory with the axiom of choice). In 1943 Erdös and Alfred Tarski wrote a joint paper that showed that some of these questions led to the construction of what are called inaccessible cardinals (sets of a vastly greater size than are usually encountered in mathematics). The theory of these and other huge sets is today an active branch of modern set theory.

Random graph theory is the application of probabilistic methods to combinatorial questions, and combines numerical estimates with probability theory to establish the existence of graphs with properties that ought to occur quite often. It was created in a series of papers by Erdös and Alfréd Rényi in the 1960s. The basic idea is that a graph with a certain number, n, of vertices is specified by assigning the edges at random. When a suitable number of edges have been specified, the graph ought to have certain properties. For example, after a time one expects all the vertices to be connected, and Erdös and Rényi gave sharp estimates of when this will occur (roughly n log (n/2) edges have to be assigned). More remarkably, they showed that after about n/2 edges have been chosen one can expect a giant component to appear, which then steadily absorbs the remaining components as the number of edges further increases. This is a good model for a phase transition, such as occurs in percolation theory, and in many branches of physics.

BIBLIOGRAPHY

It is possible to list only a small selection of his papers here.

WORKS BY PAUL ERDÖS

With Mark Kac. The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions. American Journal of Mathematics 62 (1940): 738–742.

With Alfred Tarski. On Families of Mutually Exclusive Sets. Annals of Mathematics44 (1943): 315–329.

“On a New Method in Elementary Number Theory which Leads to an Elementary Proof of the Prime Number Theorem.” Proceedings of the National Academy of Sciences 35 (1949): 374–384.

With Alfréd Rényi. “On the Evolution of Random Graphs.” Magyar Tudomanyos Akademia Matematikai Kutato Intezetenek Kozlemenyei5 (1960): 17–61.

Paul Erdös: The Art of Counting. Selected Writings. Edited by Joel Spencer and with a dedication by Richard Rado. Mathematicians of Our Time, Vol. 5. Cambridge, MA and London. MIT Press, 1973.

With Joel Spencer. Probabilistic Methods in Combinatorics. Probability and Mathematical Statistics, Vol. 17. New York and London: Academic Press, 1974.

With Ronald L. Graham. “Old and New Problems and Results in Combinatorial Number Theory: Van der Waerden’s Theorem and Related Topics.” L’Enseignement Mathématique25 (1979): 325–344. Also in Monograph No. 28 de L’Enseignement Mathématique (1980).

OTHER SOURCES

Babai, László. Paul Erdös (1913–1996): His Influence on the Theory of Computing. Proceedings of the Twenty-ninth Annual ACM Symposium on the Theory of Computing, 1997. New York: Association for Computing Machinery, 1999, pp. 383–401. (Electronic.)

———. “Finite and Transfinite Combinatorics.” Notices of the American Mathematical Society 45 (1998): 23–28.

Babai, László, Carl Pomerance, and Peter Vértesi. “The Mathematics of Paul Erdös.” Notices of the American Mathematical Society 45 (1998): 19–23.

Babai, László, and Joel Spencer. “Paul Erdös (1913–1996).” Notices of the American Mathematical Society 45 (1998): 64–66.

Hajnal, András. Paul Erdös’ Set Theory. The Mathematics of Paul Erdös, Vol. 2, Algorithms Combin. 14 (1997): 352–393. Reprinted in The Mathematics of Paul Erdös, edited by Ronald L. Graham and Jaroslav Neŝetŭil. Berlin and New York: Springer, 1997.

Hoffman, Paul. The Man Who Loved Only Numbers. London: Fourth Estate, 1998.

Jeremy Gray

Complete Dictionary of Scientific Biography

Paul Erdos

views updated May 21 2018

Paul Erdos

For Paul Erdos (1913-1996), mathematics was life. Number theory, combinatorics (a branch of mathematics concerning the arrangement of finite sets), and discrete mathematics were his consuming passions. Everything else was of no interest: property, money, clothes, intimate relationships, social pleasantries—all were looked on as encumbrances to his mathematical pursuits.

A genius in the true sense of the word, Erdos traveled the world, living out of a suitcase, to problem solve—and problem pose—with his mathematical peers. A small, hyperactive man, he would arrive at a university or research center confident of his welcome. While he was their guest, it was a host's task to lodge him, feed him, do his laundry, make sure he caught his plane to the next meeting, and sometimes even do his income taxes. Cosseted by his mother and by household servants, he was not brought up to fend for himself. Gina Bari Kolata, writing in Science magazine, reports that Erdos said he "never even buttered his own bread until he was 21 years old."

Yet this man, whom Paul Hoffman called "probably the most eccentric mathematician in the world" in the Atlantic Monthly, more than repaid his colleagues' care of him by giving them a wealth of new and challenging problems—and brilliant methods for solving them. Erdos laid the foundation of computer science by establishing the field of discrete mathematics. A number theorist from the beginning, he was just 20 years old when he discovered a proof for Chebyshev's theorem, which says that for each integer greater than one, there is always at least one prime number between it and its double.

Erdos was born in Budapest, Hungary, on March 26, 1913. His parents, Lajos and Anna Erdos, were high school mathematics teachers. His two older sisters died of scarlet fever when he was an infant, leaving him an only child with a very protective mother. Erdos was educated at home by his parents and a governess, and his gift for mathematics was recognized at an early age. It is said that Erdos could multiply three-digit numbers in his head at the age three, and discovered the concept of negative numbers when he was four. He received his higher education from the University of Budapest, entering at the age of 17 and graduating four years later with a Ph.D. in mathematics. He completed a postdoctoral fellowship in Manchester, England, leaving Hungary in the midst of political unrest in 1934. As a Jew, Hungary was then a dangerous place for him to be. During the ensuing Nazi era, four of Erdos's relatives were murdered, and his father died of a heart attack in 1942.

In 1938, Erdos came to the United States. However, because of the political situation in Hungary, he had difficulty receiving permission from the U. S. government to come and go freely between America and Europe. He settled in Israel and did not return to the United States until the 1960s. While in the U.S., he attended mathematical conferences, met with top mathematicians such as Ronald Graham, Ernst Straus and Stanislaw Ulam, and lectured at prestigious universities. His appearances were irregular, owing to the fact that he had no formal arrangements with any of the schools he visited. He would come for a few months, receive payment for his work, and move on. He was known to fly to as many as fifteen places in one month—remarking that he was unaffected by jet lag. Because he never renounced his Hungarian citizenship, he was able to receive a small salary from the Hungarian Academy of Sciences.

An Erdos Number Conveyed Prestige

So esteemed was Erdos by his colleagues that they invented the term "Erdos number" to describe their close connections with him. For example, if someone had coauthored a paper with Erdos, they were said to have an Erdos number of one. If someone had worked with another who had worked with Erdos, their Erdos number was two, and so on. According to his obituary in the New York Times, 458 persons had an Erdos number of one; an additional 4,500 could claim an Erdos number of two. It is said that Albert Einstein had an Erdos number of two. Ronald Graham, director of information sciences at AT and T Laboratories, once said that research was done to determine the highest Erdos number, which was thought to be 12. As Graham recalled, "It's hard to get a large Erdos number, because you keep coming back to Erdos." This "claim to fame" exercise underscores Erdos's monumental publishing output of more than 1,500 papers, and is not only a tribute to his genius but also to his widespread mathematical network.

Throughout his career, Erdos sought out younger mathematicians, encouraging them to work on problems he had not solved. He created an awards system as an incentive, paying amounts from $10 to $3,000 for solutions. He also established prizes in Hungary and Israel to recognize outstanding young mathematicians. In 1983, Erdos was awarded the renowned Wolf Prize in Mathematics. Much of the $50,000 prize money he received endowed scholarships made in the name of his parents. He also helped to establish an endowed lectureship, called the Turan Memorial Lectureship, in Hungary.

Perfect Proofs from God's "Great Book"

Erdos's mathematical interests were vast and varied, although his great love remained number theory. He was fascinated with solving problems that looked—but were not—deceptively simple. Difficult problems involving number relationships were Erdos's special forte. He was convinced that discovery, not invention, was the way to mathematical truth. He often spoke in jest of "God's Great Mathematics Book in the Sky," which contained the proofs to all mathematical problems. Hoffman in the Atlantic Monthly says "The strongest compliment Erdos can give to a colleague's work is to say, 'It's straight from the Book."'

Mother's Death Brought on Depression

Erdos's mother was an important figure in his life. When she was 84 years old, she began traveling with him, even though she disliked traveling and did not speak English. When she died of complications from a bleeding ulcer in 1971, Erdos became extremely depressed and began taking amphetamines. This habit would continue for many years, and some of his extreme actions and his hyperactivity were attributed to his addiction. Graham and others worried about his habit and prevailed upon him to quit, apparently with little result. Even though Erdos would say, "there is plenty of time to rest in the grave," he often talked about death. In the eccentric and personal language he liked to use, God was known as S.F. (Supreme Fascist). His idea of the perfect death was to "fall over dead" during a lecture on mathematics.

Erdos's "perfect death" almost happened. He died of a heart attack in Warsaw, Poland, on September 20, 1996, while attending a mathematics meeting. As news of his death began to reach the world's mathematicians, the accolades began. Ronald Graham, who had assumed a primary role in looking after Erdos after his mother's death, said he received many electronic-mail messages from all over the world saying, "Tell me it isn't so." Erdos's colleagues considered him one of the 20th century's greatest mathematicians. Ulam remarked that it was said "You are not a real mathematician if you don't know Paul Erdos." Straus, who had worked with Einstein as well as Erdos, called him "the prince of problem solvers and the absolute monarch of problem posers," and compared him with the great 18th-century mathematician Leonhard Euler. Graham remarked, "He died with his boots on, in hand-to-hand combat with one more problem. It was the way he wanted to go."