Obituary: Paul Erdos

Paul Erdos was one of the most brilliant and probably the most remarkable of mathematicians of this century. He greatly influenced many branches of mathematics and was the prime mover in the rapid growth of combinatorics, an area of mathematics fundamental to computer science.

He never had a "proper" teaching job, but constantly travelled around the world, in search of new challenges. Considering material possessions a nuisance, he lived for over 60 years out of half-full suitcases, which he never learnt to pack. His discarded suit was rejected by Oxfam.

Erdos was the quintessential mathematician: although he was interested in history, medicine and politics, he was dedicated to mathematics. He wrote some 1,500 papers, about five times as many as other prolific mathematicians, and had close to 500 collaborators. His enormous output even inspired a limerick:

A conjecture both deep and profound

Is whether the circle is round.

In a paper by Erdos,

Written in Kurdish,

A counterexample is found.

According to a wit, on a long train journey he would write a joint paper with the conductor.

Paul Erdos was born into an intellectual Hungarian-Jewish family in Budapest amidst tragic circumstances: when his mother returned home from the hospital she found that her two daughters had died of scarlet fever. Soon after the outbreak of the First World War, Erdos's father was taken prisoner by the Russians and returned home from Siberia only six years later. The young Erdos was brought up by his mother, a teacher of mathematics like his father, and he remained devoted to her all his life.

He was a child prodigy: as a small boy, he amused people by asking them how old they were and telling them how many seconds they had lived. He was educated mostly at home by his father, until 1930, when he entered the Peter Pzmny University in Budapest, where he was soon at the centre of a small group of outstanding young Jewish mathematicians. As a second- year undergraduate, he practically completed his doctorate under Leopold Fejer. His main result was a simple proof of an extension of Bertrand's Postulate, first proved by the Russian mathematician P.L. Chebyshev, that there is always at least one prime number between any positive integer and its double.

For Erdos, 1934 was a momentous year: not only did he graduate from the university, but he also received his doctorate, and got a fellowship to join the remarkable group of mathematicians that was brought together by Louis Mordell in Manchester. He also met Richard Rado and Harold Devonport, who became his great friends and collaborators.

In 1938, Erdos sailed for the United States, where he stayed for the next decade. During his first year, at the Institute for Advanced Study in Princeton, he wrote ground-breaking papers with A. Wintner and Mark Kac, which founded probabilistic number theory, with P. Turn he proved great results in approximation theory, and he solved the then outstanding problem in dimension theory. When his Fellowship at the institute was not renewed, he started his peregrinations, with stays at the University of Pennsylvania, Notre Dame, Purdue and Stanford.

The great mathematical event of 1949 was an elementary proof of the Prime Number Theorem, given by Atle Selberg and Erdos. The result, which predicts the distribution of primes with some accuracy, was first proved in 1986 by sophisticated methods, and it had been thought that no elementary proof could be given.

In 1954, he fell foul of the McCarthy era: despite being refused a re- entry visa, he left the US and, as a result, for the next nine years he was not allowed to return to America. Israel came to his aid with a job for three months at the Hebrew University of Jerusalem. Although officially he became a resident of Israel, he refused its citizenship and kept his Hungarian passport, claiming that he was a citizen of the world.

Although in 1963 he was allowed to return to America, and from then on spent most of his time there, he could never forgive the US government. From 1964, his mother, then aged 84, accompanied him on his travels. This was a golden period for Erdos, who never recovered from her death in 1971.

In over six decades of furious activity, he wrote fundamental papers on number theory, real analysis, geometry, probability theory, complex analysis, approximation theory, set theory and combinatorics. His first great love was number theory, while in his later years he worked mostly in combinatorics. In 1966, with John Selfridge, he solved a notorious problem in number theory that had been open for over 100 years, namely that the product of consecutive positive integers (like 4.5.6.7.8) is never an exact square, cube or any higher power.

With Rado and A. Hajnal, he founded partition calculus, a branch of set theory, which is a detailed study of the relative sizes of large infinite sets. Nevertheless, he will be best remembered for his contributions to combinatorics, an area of mathematics fundamental to computer science. He founded extremal graph theory, his theorem with A.H. Stone being of prime importance, and with A. Renyi he started probabilistic graph theory. He advocated the use of elementary methods, in addition to techniques requiring vast preparation, and decades before it was commonly accepted he had shown the power of random methods in mathematics. He showed that simply stated problems often lead to exciting phenomena, and left behind hundreds of exciting problems whose solutions will influence combinatorics for years to come.

Sexual pleasure revolted him; even an accidental touch by anyone made him feel uncomfortable. He never married or had a family, though he was very good with children. He lived for mathematics and relied on his friends to look after him; in his later years he particularly liked to be in Budapest, Memphis and Kalamazoo where, in addition to his mathematical friends, he found good medical care. He hated to be alone, and almost never was; he loved to attend conferences and enjoyed the attention of mathematicians. His aim in life was "to do mathematics: to prove and conjecture".

A favourite saying of his was, "Every human activity, good or bad, must come to an end, except mathematics." He died as he wished to, before his powers were greatly diminished: while attending a conference, he was killed by a massive heart attack.

Bela Bollobs

Paul Erdos, mathematician: born Budapest 26 March 1913; died Warsaw 20 September 1996.