``A Life of Mathematics: Paul Erd\H{o}s (1913-1996)'' by B\'ela Bollob\'as as published in the December, 1996, issue of MAA's FOCUS

%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

\vglue 1cm
{\bf A Life of Mathematics:}

{\bf Paul Erd\H{o}s (1913-1996)}

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.} 

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

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 

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

\hskip 4cm
Trinity College, Cambridge, England 

\hskip 4cm
University of Memphis, Memphis, TN 

Institute for Advanced Study, Princeton, NJ