%From bollobas@math.ias.edu Wed Dec 25 19:08:55 1996 %From: Bela Bollobas%Date: Wed, 25 Dec 1996 19:08:51 -0500 %To: nevai@math.ohio-state.edu \magnification=\magstep2 \vglue 1cm \centerline {\bf A Life of Mathematics:} \centerline {\bf Paul Erd\H{o}s (1913-1996)} \bigskip Paul Erd\H{o}s died of a massive heart attack on September 20 1996, while attending a mini-semester at the Banach Center in Warsaw. His passing is a tremendous loss to mathematics and it marks the end of an era. Not only did he write many more papers (about 1500, some still to be published) with many more coauthors (probably close to 500) than anybody else, but he also posed many more inspiring unsolved problems and personally knew many more mathematicians than anybody else in the history of mathematics. For over six decades, Erd\H{o}s dedicated his life to mathematics: he wrote fundamental papers in number theory, interpolation and function theory, geometry, set theory, group theory, complex function theory, probability theory and combinatorics, among others. His prodigious output even inspired a limerick: {\hskip1.5cm A conjecture both deep and profound} {\hskip 1.5cm Is whether the circle is round. } {\hskip2cm In a paper of Erd\H{o}s,} {\hskip 2cm Written in Kurdish,} {\hskip 1.5cm A counterexample is found.} \noindent There is no doubt that number theory and combinatorics were closest to his heart: in number theory he did brilliant work on diophantine problems, additive number theory, the distribution of primes, the divisibility of sequences, polynomials, and bases; in combinatorics his major contributions were in Ramsey theory, extremal graph theory, extremal combinatorics, and the theory of random graphs. He practically created probabilistic number theory, partition calculus for cardinals, extremal graph theory and the theory of random graphs, and he was instrumental in the rapid growth of combinatorics in the last few decades. Erd\H{o}s was born on March 26, 1913, into an intellectual Hungarian-Jewish family in Budapest amidst tragic circumstances: when his mother returned home from the hospital, carrying the little Paul, she found that her two daughters had died of scarlet fever. Both his parents taught mathematics and physics. He was hardly a year and a half when, at the beginning of the First World War, during the first great offensive of the Austro-Hungarian army, his father was taken prisoner by the Russians and returned from Siberia only six years later. The young Erd\H{o}s was brought up by his mother and a German {\it Fr\"aulein}. Throughout his life, Erd\H{o}s remained devoted to his mother. He was a child prodigy: he discovered negative numbers for himself before he turned four. With the exception of about three years spent in schools, Erd\H{o}s was educated at home, mostly by his father. In 1930 Erd\H{o}s entered the P\'eter P\'azm\'any University in Budapest, and was soon the leading figure of a small group of outstanding young Jewish mathematicians. His love of problems was already in evidence: much of the time the group followed up the problems proposed by Erd\H{o}s. He obtained his first result not long after entering the university: by sharpening a method of Landau, he gave a beautiful proof of Chebyshev's theorem that there is always a prime between a positive integer and its double. A little later, Erd\H{o}s followed this up by a simple proof of the following extension of Chebyshev's theorem, first proved by Sylvester and rediscovered by Schur: if $n>k$ then, in the set of integers $n,n+1,\ldots,n+k-1$, there is a number containing a prime divisor greater than~$k$. (Thus the case $n=k+1$ is precisely Chebyshev's theorem.) The basis of his doctoral dissertation, done nominally under the direction of the great Hungarian analyst Leopold Fej\'er, was also on a similar theme: it concerned primes between $n$ and $2n$ in certain arithmetic progressions. These results established Erd\H{o}s as {\it the magician of Budapest}, and he was soon in touch with Schur, Landau, Mordell, Davenport, and others. In 1934, Erd\H{o}s not only graduated from the university, but also received his doctorate and got a Fellowship to Manchester, to join the exceptional group of mathematicians led by Louis Mordell. Following the Hungarian tradition, he had wanted to go to Germany, but ``Hitler got there first''. On October~1, 1934, Erd\H{o}s arrived in England, his first stop being Cambridge, where he met Harold Davenport and Richard Rado, who were to become his close friends and collaborators, and the great English mathematicians G.H.~Hardy and J.E.~Littlewood. Erd\H{o}s spent four fertile and happy years in Manchester, working mostly on number theory. Nevertheless, his {\it wanderlust} was already in evidence: from 1934 he hardly ever slept in the same bed for seven consecutive nights, frequently leaving Manchester for Cambridge, London, Bristol and other universities. In 1938 Erd\H{o}s left Manchester for the Institute for Advanced Study in Princeton: he was to stay in the U.S. for the next ten years. The year 1938/39 at Princeton was his {\it annus mirabilis\/}: he wrote outstanding papers with Mark Kac and Aurel Wintner, that practically created {\it probabilistic number theory}, his collaboration with Paul Tur\'an in {\it approximation theory\/} rose to new heights, and he solved a major problem of W.~Hurewicz in {\it dimension theory}. Amazingly, in spite of this embarrassment of riches, his Fellowship at the Institute was not continued, and Erd\H{o}s was forced to embark on his life as a wandering scholar, with the University of Pennsylvania, Notre Dame, Purdue, Stanford and Syracuse as some of the major stops. The flow of important results continued: in 1943, with A.~Tarski, he started the theory of large cardinals by proving the first results about {\it inaccessible cardinals}, and in 1946, with A.~H.~Stone, he proved the fundamental theorem of extremal graph theory. In 1948, Erd\H{o}s returned to Europe for a few months; during his visit to Hungary, he saw his mother for the first time in over a decade, and he met the few relatives who survived the Holocaust. His tour of Europe enabled him to do joint work with N.~J.~de~Bruijn and J.~F.~Koksma, and he renewed his friendship with Alfr\'ed R\'enyi, who was also to become one of his most important collaborators. The {\it prime number theorem} states that $\pi (x)$, the number of primes not exceeding $x$, is asymptotic to $x/\log x$. Ever since Hadamard and de~la~Vall\'ee Poussin had proved this in 1896 with the aid of complex function theory, it had been a major problem whether it could be proved by {\it `elementary'} means, without appealing to results in complex function theory. The great mathematical event of 1949 was that Atle Selberg and Erd\H{o}s found exactly such a proof. The starting point was Selberg's asymptotic formula: $$\sum_{p\le x} (\log p)^2 + \sum_{p,q\le x}\log p \log q =2x\log x+O(x),$$ which Selberg proved by an ingenious elementary method. From this Erd\H{o}s deduced by elementary means that for every $c>0$ there is a positive $\delta (c)$ such that if $x$ is sufficiently large then $$\pi ((1+c)x)-\pi (x) > \delta (c) x/\log x.$$ Using his asymptotic formula and the method of Erd\H{o}s, Selberg completed an elementary proof of the prime number theorem. Later both Selberg and Erd\H{o}s found simpler elementary proofs. In 1954, when he was already in possession of a 'green card' (permanent residence permit), Erd\H{o}s applied for a reentry visa to the US, to enable him to attend the International Congress of Mathematicians in Amsterdam. In the climate of anticommunist hysteria, the visa was refused. Nevertheless, Erd\H{o}s sailed for Europe. The immigration authorities were intransigent: Erd\H{o}s lost his green card and for nine years he was persona non grata in the US. Erd\H{o}s could never forget that `Sam' tried to starve him to death. Israel came to his aid, with jobs in Jerusalem and at the Technion in Haifa. He was even offered citizenship, which he politely turned down, but from then on Israel was his place of permanent residence. >From 1964, his mother, then aged 84, accompanied him on his travels, their first trip being to Israel. They were eager to make up for lost time, and revelled in each other's company: as she always said, she did not travel to see the world but to be with her son. For seven blissful years, they travelled all over Europe and America, and even went to Australia. Her death, in 1971, was a terrible blow to him, from which he never recovered: he lost weight and had to take caffeine tablets and pep pills to help his concentration and to ward off his depression. He needed the stimulus of meeting new mathematicians with new ideas and problems, so he travelled more than ever, occasionally even visiting a country for just a single day. In the last twenty years, he tended to visit Hungary for the summer, and spent most of his time in the US, with occasional longer stays in Israel, Canada, England, Germany and France. Rather than diminishing, from the 1950s his output was even greater than before, with more and more joint papers. In a series of papers with Alfr\'ed R\'enyi, he founded the theory of random graphs. Their main discovery is that for many a monotone increasing property, sharp {\it `phase transition'} occurs: graphs of size a little less than a certain threshold are very unlikely to have the property, while graphs with a few more edges are almost certain to have that property. The year 1958 saw the appearance of his first joint paper with Andr\'as Hajnal, with whom he was to write over fifty joint papers on transfinite combinatorics. In 1965, in the {\it giant triple paper}, a difficult paper of over 100 pages, written with Rado and Hajnal, he founded partition calculus. To the great disappointment of Erd\H{o}s, the beauty of later problems was rather spoilt when {\it `independence reared its ugly head'}. In 1966 Erd\H{o}s started his collaboration with his second most frequent coauthor, Andr\'as S\'ark\"ozi: they wrote close to 50 papers on divisibility properties of sequences, many of them jointly with Endre Szemer\'edi. In 1975, Erd\H{o}s and John Selfridge published a solution to a 150 years old problem: the product of two or more consecutive positive integers is never a square, a cube, or any higher power. The elementary proof was an extension of an earlier method of Erd\H{o}s. All in all, Erd\H{o}s wrote at least twenty papers with a dozen people; in addition to Hajnal, S\'ark\"ozy, R\'enyi, Tur\'an and Szemer\'edi, with Ralph Faudree, Richard Schelp, Vera T. S\'os, Ron Graham, Cecil Rousseau, Stephan Burr and Ernst Straus. This phenomenal amount of joint work was the result of his brilliance and his ability to 'keep his mind open': to expect the unexpected and to find hidden connections. In addition to the host of brilliant results he proved, Paul Erd\H{o}s will probably be best remembered for three great contributions to mathematics. Firstly, he proved over and over again that {\it elementary methods} have their place in mathematics. Needless to say, here `elementary' is not used as a synonym for `simple': often the opposite is the case since a proof that does not make much use of sophisticated machinery is frequently involved and ingenious. Secondly, he was the first to fully realize and exploit the power of {\it random methods} in order to attack a great variety of problems which have nothing to do with randomness or probability theory. By now it is well known in mathematics that an appropriate random choice is frequently the best way to show the existence of a seemingly paradoxical object, while its explicit construction may run into formidable difficulties. Nevertheless, Erd\H{o}s was the apostle of random methods: he was the first to recognize their power, which he exploited repeatedly, many years before it became accepted wisdom. For many years, the probabilistic method was called {\it the Erd\H{o}s method}. His third major general contribution to mathematics was through his problems. As a {\it problem poser}, Erd\H{o}s towered above everybody else: in the entire history of mathematics there is nobody remotely like him. He has left behind hundreds of exciting problems that are easy to formulate but go to the very heart of the matter. The innocence of these questions frequently misleads outsiders, who do not realize that the solutions may lead to deep phenomena. To add spice to his problems, from the 1950s he offered monetary rewards for the solutions, reflecting his estimate of the difficulty of the problem. The first one to claim his reward was Ernst Specker in 1954. Needless to say, the reward itself was never comparable to the glory accompanying the solution of `an Erd\H{o}s problem'. Erd\H{o}s was a remarkable man in every way. Although he was interested in medicine, history and politics, he lived for mathematics with a passion rare even among great scientists. He also had a passionate desire to be free: to go where and when he wanted, without being constrained in any way, whether by politics, finance or convention. He regarded material possessions a `nuisance', and lived very modestly, carrying almost nothing on his travels, relying on his friends to look after him. He was always eager to help mathematicians, especially young ones: many a well-established mathematician practically owes his career to him. He never had a `proper' permanent job, but was content to live on the fees he received for his lectures and shorter stays. He made a determined effort to be everywhere all the time. For most of his life he conducted an extensive correspondence: having dispensed with the personal news in no time, he turned to what mattered, new problems and new results. In his later years letters gave way to the telephone, which he used compulsively. Considering his unrelenting life-style, his health was surprisingly robust to the very end, although in his last years he had trouble with his feet and his eye-sight rather deteriorated. In Budapest, Kalamazoo and Memphis, he not only found good mathematical friends, but also excellent health care; during a conference in Kalamazoo in June 1996, he was fitted with a pace-maker. It is not only his constant travel and total disregard of material possessions that gave him his reputation of being an eccentric. He invented and used a small personal vocabulary: for him a child was an {\it epsilon}, a girl was a {\it boss} and a boy a {\it slave}, alcohol was {\it poison}; a mathematician {\it preached} (lectured), a slave was {\it captured} (married) and was later {\it liberated} (divorced), and so on. Like G.~H.~Hardy, he considerd God malicious: he gives us colds, makes us late, hides our glasses and notebooks, sends us storms and traffic jams and, most importantly, is delighted if we fail to do a good deed when we have a chance. He claimed that Hindi was the best language because the two greatest evils sound almost the same: old age (budha) and stupidity (budhu). He awarded himself letters after his name, each abbreviation having its own story: he became p.g.o.m. (poor great old man) when his mother died, l.d. (living dead) at 60, a.d. (archeological discovery) at 65, c.d. (counts dead) at 70, and so on. Many honours were bestowed on him. Although he did not care about them, he was happy that they enabled him to help people in need. In 1984 he shared the Wolf Prize with Shiingshen Chern, and promptly gave away most of the \$50,000 he received. In 1973 the London Mathematical Society elected him an honorary member, and in 1975 he was Visiting Fellow Commoner in Trinity College, Cambridge. He was a member of the Hungarian Academy of Science~(1956), the U.S. National Academy of Science~(1979), the Indian National Science Academy~(1988), the Royal Society~(1989), and other academies. He received numerous honorary degrees, including degrees from the University of Cambridge (1991), the Technion in Haifa (1992) and the Charles University in Prague (1992). Recently, a documentary film was made about him by George Csicsery, with support from the American Mathematical Society and other scientific organizations. Erd\H{o}s always hoped that his work would be carried on: {\it ``Let him be blessed who takes my place!''}, he proclaimed, paraphrasing the great Hungarian poet Endre Ady. A year ago he started to show signs of old age but his death from a heart attack was unexpected. He was never married and left behind no close blood relations, but his many many friends will miss him terribly. The world is much poorer without him. \vskip 2cm \hskip 6cm B\'ela Bollob\'as \medskip \hskip 4cm Trinity College, Cambridge, England \hskip 4cm University of Memphis, Memphis, TN \hskip4cm Institute for Advanced Study, Princeton, NJ \bye