Paul Erdős

How to use this course

Paul Erdős wrote about 1,500 papers with more than 500 co-authors, more than any mathematician since Euler. He built few theories. He asked questions, often with a cash prize attached, and found short proofs that changed how whole fields were done. His idea that one can prove an object exists by showing that a random object works with positive probability is now a standard method in combinatorics, computer science and number theory. This course follows his life and the main lines of his work.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proof sketches and exercises with folded solutions. The order follows his career: elementary prime number theory (1932–1949), probabilistic number theory (1939–1940), Ramsey theory (1935–1947), the probabilistic method (1947–1975), random graphs (1959–1960), extremal combinatorics (1946–1961), and additive number theory (1936 onward). The companion module on Atle Selberg covers the elementary proof of the prime number theorem from the other side.

Timeline

Budapest, 1913–1930

Pál Erdős was born in Budapest on 26 March 1913, in Austria-Hungary. His parents, Lajos and Anna Erdős, were Jewish secondary-school mathematics teachers; the family name had earlier been Engländer. Days before his birth his two sisters, aged three and five, died of scarlet fever. He grew up as an only child, and his mother protected him closely.

In August 1914, at the start of the First World War, his father was captured by the Russian army and spent six years as a prisoner in Siberia, returning in 1920. He then taught his son English, and Erdős kept his father’s accent all his life. For much of his early schooling his mother kept him at home, with a German governess and private tutors.

Both parents introduced him to mathematics early, and he treated it as play all his life. Hungary at that time had an unusual culture of mathematical problem solving. The monthly journal KöMaL published problems for secondary-school students and printed the photographs of its best solvers. Erdős was a diligent solver, and his photograph appeared in each of his high-school years from 1927 to 1930. He stayed loyal to the journal later, proposing problems and writing articles for it. After the war Hungary went through revolution, a short-lived communist regime and then the conservative government of Miklós Horthy. A law of September 1920, the numerus clausus, limited Jewish admissions to universities to 6 per cent. Anna Erdős lost her teaching post in the upheavals of 1919–1920.

The university and the Anonymous circle, 1930–1934

In 1930 Erdős won a national examination, which gave him a place at the Pázmány Péter University in Budapest (now Eötvös Loránd University) despite the quota. He was 17. Within two years he had found a new elementary proof of Bertrand’s postulate, first proved by Pafnuty Chebyshev, that there is always a prime between \(n\) and \(2n\). Lesson 04 gives his argument. It made him known at once.

In the early 1930s the statue of Anonymous, the unnamed medieval chronicler of Hungary, in the City Park of Budapest became the weekly meeting place of a circle of young mathematicians, most of them Jewish. Erdős, Tibor Gallai and Pál Turán were at its centre; George Szekeres and Esther Klein belonged to it as well. Klein posed the question that convex position forces large convex polygons; Szekeres and Erdős solved it, and because Szekeres and Klein later married, Erdős called it the happy ending problem (Lesson 06). Turán became his closest collaborator for decades.

He received his doctorate in 1934, aged 21, under Lipót Fejér, the leader of Hungarian analysis. The thesis, Über die Primzahlen gewisser arithmetischer Reihen, concerned primes in arithmetic progressions. With anti-Jewish laws on the way, there was no future for him in Hungary. Louis Mordell arranged a fellowship in Manchester.

Manchester, Princeton and the war, 1934–1945

Erdős spent four years in Manchester, from 1934 to 1938. He met G. H. Hardy in 1934 and the young Polish mathematician Stanisław Ulam in 1935, who became a lifelong friend. In March 1938 Germany annexed Austria, and in September came the Munich agreement. Erdős left Hungary for good, travelling through England to the United States.

He held a fellowship at the Institute for Advanced Study in Princeton from 1938. It was extended for only six months; MacTutor records that the Institute found him uncouth and unconventional. Ulam then invited him to the University of Wisconsin in Madison. In these years Erdős worked with Mark Kac, Arthur Stone, Shizuo Kakutani and others; the Erdős–Kac theorem (Lesson 05) dates from this time.

In August 1941 Erdős and two companions on Long Island wandered near a military radio transmitter and were detained. The episode was harmless, but it left him with an FBI file. In 1943 Ulam invited him to the Manhattan Project at Los Alamos. Erdős declined, because he intended to return to Hungary after the war, and took a part-time post at Purdue University. In August 1945 he learned that his father had died of a heart attack in 1942, that his mother had survived, and that four of his aunts and uncles had been murdered in the Holocaust.

Primes by elementary means

For the general reader. “Elementary” in number theory means without complex analysis, not easy. Erdős’s first paper proved, using only the binomial coefficient \(\binom{2n}{n}\), that there is always a prime between \(n\) and \(2n\). Sixteen years later his elementary ideas, together with a formula of Selberg, gave a proof of the prime number theorem without complex analysis, which many had thought impossible.

Erdős’s proof

Let \(N=\binom{2n}{n}\). Since \(N\) is the largest of the \(2n+1\) terms in \((1+1)^{2n}\), we have \(N\ge 4^n/(2n+1)\). By Legendre’s formula the exponent of a prime \(p\) in \(N\) is \(\sum_{j\ge1}\big(\lfloor 2n/p^j\rfloor-2\lfloor n/p^j\rfloor\big)\). Each term is 0 or 1, and terms vanish once \(p^j>2n\). Three facts follow:

1. the power of \(p\) dividing \(N\) is at most \(2n\);
2. primes \(p>\sqrt{2n}\) divide \(N\) at most once;
3. primes with \(\tfrac{2n}{3}<p\le n\) do not divide \(N\) at all, when \(n\ge3\), because then \(p^2>2n\) and \(\lfloor 2n/p\rfloor-2\lfloor n/p\rfloor=2-2=0\).

Suppose there is no prime in \((n,2n]\). Then every prime factor of \(N\) is at most \(2n/3\), and

using the bound \(\prod_{p\le x}p<4^x\) of Exercise 4.1. This gives \(4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}\), which is false for \(n\ge 468\). For \(n\le467\) the primes \(2,3,5,7,13,23,43,83,163,317,631\), each less than twice the previous one, settle the claim.

The 1896 proofs used the Riemann zeta function as a function of a complex variable. In 1948 Selberg proved the elementary formula

summed over primes \(p,q\). Erdős used it in July 1948 to show that for every \(\varepsilon>0\) the interval \((x,(1+\varepsilon)x]\) contains at least \(\delta(\varepsilon)\,x/\log x\) primes for large \(x\). Selberg used this input to complete a first elementary proof of the prime number theorem, and soon found a second proof that avoided it. Disagreement about joint or separate publication led to a bitter dispute; both published in 1949, Selberg in the Annals of Mathematics and Erdős in the Proceedings of the National Academy of Sciences.

Probabilistic number theory

For the general reader. How many different prime factors does a typical large number have? Hardy and Ramanujan found that it is usually close to \(\log\log n\), a very slowly growing quantity. Erdős and Mark Kac proved in 1940 that the count is distributed like the bell curve, as if divisibility by different primes were independent coin flips. The result founded probabilistic number theory.

Let \(\omega(n)\) be the number of distinct primes dividing \(n\). Write \(\log_2 x=\log\log x\).

Proof. Write \(\omega(n)=\sum_{p\le x}X_p(n)\), where \(X_p(n)=1\) if \(p\mid n\). Choosing \(n\le x\) uniformly, \(\mathbb E X_p=\lfloor x/p\rfloor/x=1/p+O(1/x)\), so by Mertens’ theorem \(\sum_{p\le x}1/p=\log_2 x+O(1)\),

For \(p\ne q\), \(\mathbb E X_pX_q=\lfloor x/pq\rfloor/x\le 1/pq\) while \(\mathbb E X_p\,\mathbb E X_q\ge(1/p-1/x)(1/q-1/x)\), so \(\operatorname{Cov}(X_p,X_q)\le(1/p+1/q)/x\). Summed over all pairs this is at most \(2\pi(x)\log_2 x/x+O(1/\log x)=o(1)\). Hence \(\operatorname{Var}\omega\le\sum_p 1/p+O(1)=\log_2 x+O(1)\). Chebyshev’s inequality finishes the proof.

Heuristic and idea of proof. The \(X_p\) behave like independent Bernoulli variables with means \(1/p\), and the central limit theorem applies to their sum, whose variance \(\sum 1/p\) diverges. Kac had the heuristic; Erdős supplied the sieve. Truncate to primes \(p\le y=x^{1/\psi(x)}\) for a slowly growing \(\psi\); this changes \(\omega\) by at most \(\psi(x)\), which is negligible after dividing by \(\sqrt{\log_2 x}\). For primes up to \(y\), the sieve shows that the joint distribution of the \(X_p\) is close to that of independent variables, so the central limit theorem transfers. The paper is The Gaussian law of errors in the theory of additive number theoretic functions, American Journal of Mathematics 62 (1940).

Ramsey theory and the happy ending

For the general reader. Among any six people, three know each other or three are strangers. Frank Ramsey proved in 1930 that such order is unavoidable in any large enough system. In 1935 Erdős and Szekeres rediscovered the idea, applied it to geometry, and gave the first good estimates. Twelve years later Erdős showed with a coin-tossing argument that those estimates are of the right type.

The Ramsey number \(R(k,l)\) is the least \(N\) such that every red–blue colouring of the edges of \(K_N\) contains a red \(K_k\) or a blue \(K_l\).

Proof. Colour \(K_N\) with \(N=R(k-1,l)+R(k,l-1)\) and fix a vertex \(v\). It has \(N-1\) neighbours, so either at least \(R(k-1,l)\) are joined to it in red or at least \(R(k,l-1)\) in blue. In the first case the red neighbourhood contains a blue \(K_l\), or a red \(K_{k-1}\) which together with \(v\) is a red \(K_k\). The second case is symmetric. The binomial bound follows by induction from \(R(k,2)=k\) and Pascal’s rule.

The happy ending problem

The conjecture is known for \(n\le6\). In 2017 Andrew Suk proved \(N(n)=2^{n+o(n)}\). The same paper contains the monotone subsequence theorem: every sequence of \(rs+1\) distinct real numbers has an increasing subsequence of length \(r+1\) or a decreasing subsequence of length \(s+1\).

The probabilistic method

For the general reader. To show that a needle exists in a haystack, it is enough to show that a randomly chosen straw is a needle with positive probability. Erdős used this idea in 1947 to show that some colourings of large networks have no orderly pattern at all, though no one could construct one. He then used it to build objects that seemed paradoxical. The method is now a branch of mathematics.

Proof. Colour each edge of \(K_n\) red or blue independently with probability \(\tfrac12\). A fixed set of \(k\) vertices is monochromatic with probability \(2\cdot2^{-\binom k2}\). By the union bound, the probability that some \(k\)-set is monochromatic is at most \(\binom nk2^{1-\binom k2}<1\). So some colouring has no monochromatic \(K_k\). For \(n=\lfloor2^{k/2}\rfloor\), \(\binom nk2^{1-\binom k2}<\frac{n^k}{k!}2^{1-k^2/2+k/2}\le\frac{2^{1+k/2}}{k!}<1\) for \(k\ge3\).

Combined with Lesson 06, \(\sqrt2\le R(k,k)^{1/k}\le4\) asymptotically. No explicit colouring achieving an exponential bound of this type is known even now, and the gap between the constants \(\sqrt2\) and 4 resisted improvement until 2023, when Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe lowered the upper constant to \(4-\varepsilon\).

Deletion: high girth and high chromatic number

Proof sketch. Take \(G(n,p)\) with \(p=n^{\theta-1}\), \(0<\theta<1/g\). The expected number of cycles of length at most \(g\) is \(\sum_{i=3}^{g}\frac{(n)_i}{2i}p^i\le\sum_{i\le g}n^{\theta i}=o(n)\), so by Markov’s inequality, with probability more than \(\tfrac12\) there are fewer than \(n/2\) short cycles. Let \(a=\lceil\tfrac3p\log n\rceil\). The probability of an independent set of size \(a\) is at most \(\binom na(1-p)^{\binom a2}\le\big(ne^{-p(a-1)/2}\big)^a\to0\). For large \(n\) both good events occur together. Delete one vertex from each short cycle. The remaining graph has at least \(n/2\) vertices, girth greater than \(g\), and independence number less than \(a\), so its chromatic number is at least \(\frac{n/2}{a}\ge\frac{n^{\theta}}{6\log n}>k\).

The local lemma

The union bound needs \(mp<1\); the local lemma needs only that dependence is limited, whatever \(m\) is. It appeared in Erdős and Lovász’s paper on 3-chromatic hypergraphs. In 2010 Robin Moser and Gábor Tardos turned it into an efficient algorithm.

Random graphs

For the general reader. Start with \(n\) isolated points and add links at random, one by one. For a long time the network is a dust of small pieces. Then, quite suddenly, a giant connected piece appears and swallows a fixed fraction of all points. Erdős and Alfréd Rényi discovered this phase transition in 1960, and it made random graphs a subject in their own right.

In On random graphs I (1959) Erdős and Rényi studied \(G(n,M)\), a uniformly random graph on \(n\) labelled vertices with \(M\) edges. The same year Edgar Gilbert introduced \(G(n,p)\), in which each of the \(\binom n2\) edges is present independently with probability \(p\). The two models behave alike when \(M\approx p\binom n2\). The long paper On the evolution of random graphs (1960) described how \(G(n,M)\) changes as \(M\) grows.

A property has threshold \(p_0(n)\) if it holds with probability tending to 0 when \(p\ll p_0\) and to 1 when \(p\gg p_0\). The first moment method: if \(\mathbb E X\to0\) then \(\Pr(X>0)\to0\). The second moment method: if \(\operatorname{Var}X=o\big((\mathbb E X)^2\big)\) then \(\Pr(X>0)\to1\).

Idea for the giant component. Explore the component of a vertex by breadth-first search. Each vertex discovered has about \(\mathrm{Bin}(n,c/n)\approx\mathrm{Poisson}(c)\) new neighbours, so the exploration resembles a Galton–Watson branching process with Poisson(\(c\)) offspring. That process dies out with probability 1 if \(c\le1\), and survives with probability \(\beta\), the positive root of \(\beta=1-e^{-c\beta}\), if \(c>1\). Surviving explorations merge into one giant component.

Extremal graphs and set systems

For the general reader. How many links can a network have without containing some forbidden pattern? Turán answered this in 1941 for complete subgraphs. Erdős and Arthur Stone found in 1946 that for every other pattern the answer is governed by a single number, its chromatic number. In the same spirit, Erdős, Chao Ko and Richard Rado found how large a family of sets can be if every two members overlap.

Let \(\mathrm{ex}(n,H)\) be the maximum number of edges in a graph on \(n\) vertices with no subgraph isomorphic to \(H\).

The lower bound comes from the Turán graph, which is \(r\)-colourable and so contains no \(H\). Erdős and Stone proved the upper bound for \(H\) a complete \((r+1)\)-partite graph with parts of size \(t\); Erdős and Miklós Simonovits observed that this gives the formula for every \(H\). For bipartite \(H\) (\(r=1\)) the theorem says only \(\mathrm{ex}(n,H)=o(n^2)\), and the true order is often unknown. That is the start of the bipartite Turán problem, a subject Erdős kept supplying with conjectures.

Intersecting families

The family of all \(k\)-sets containing a fixed element shows the bound is sharp. The theorem was proved in 1938 but published only in 1961.

Katona’s proof (1972). Arrange \(1,\dots,n\) around a circle in a cyclic order \(\sigma\). A set is an arc of \(\sigma\) if its elements are consecutive. At most \(k\) of the \(n\) arcs of length \(k\) can belong to an intersecting family when \(n\ge2k\): if arc \(A\) is in \(\mathcal F\), every other arc in \(\mathcal F\) must start or end strictly inside \(A\), and these \(2(k-1)\) arcs pair off into disjoint pairs. Now count pairs \((\sigma,F)\) with \(F\in\mathcal F\) an arc of \(\sigma\). There are at most \(k\cdot(n-1)!\) of them. Each \(F\) is an arc of exactly \(k!\,(n-k)!\) cyclic orders. Hence \(|\mathcal F|\,k!\,(n-k)!\le k\,(n-1)!\), which is the bound.

Additive problems and progressions

For the general reader. Some of Erdős’s best-known legacies are questions. In 1936 he and Turán asked whether every set of integers of positive density contains arbitrarily long evenly spaced runs. The answer, Szemerédi’s theorem of 1975, and Erdős’s stronger conjecture behind the Green–Tao theorem on primes, are among the central results of modern mathematics. This lesson treats three additive problems and their proofs.

Sidon sets

A set \(A\subseteq\{1,\dots,N\}\) is a Sidon set if all sums \(a+b\) (\(a\le b\) in \(A\)) are distinct. Simon Sidon asked Erdős about them in the 1930s.

Zero-sum subsequences

Proof for \(n=p\) prime. Let \(a_1,\dots,a_{2p-1}\) be the integers. Over \(\mathbb F_p\) consider the polynomials

They have degree \(p-1\) each, and \(2(p-1)<2p-1\) variables, so by the Chevalley–Warning theorem the number of common zeros is divisible by \(p\). The zero vector is one common zero, so there is another, \(x\). Let \(I=\{i:x_i\ne0\}\). By Fermat, \(x_i^{p-1}=1\) for \(i\in I\), so \(g(x)=0\) says \(|I|\equiv0\pmod p\), and \(f(x)=0\) says \(\sum_{i\in I}a_i\equiv0\). Since \(0<|I|\le2p-1\), \(|I|=p\). The general case follows because the property is multiplicative in \(n\) (Exercise 10.2).

Progressions

Erdős went further and conjectured that \(\sum_{a\in A}1/a=\infty\) is enough. This remains open, and he offered a large prize for it. The primes satisfy the hypothesis, and in 2004 Ben Green and Terence Tao proved that they contain arbitrarily long progressions. Erdős met Tao in Adelaide in 1985, when Tao was ten. Other Erdős problems in this vein include the Erdős–Szemerédi sum–product conjecture (1983), that \(\max(|A+A|,|A\cdot A|)\ge|A|^{2-\varepsilon}\) for finite sets of integers, and the Erdős discrepancy problem, solved by Tao in 2015.

The travelling mathematician, 1945–1971

After the war Erdős never again held a regular full-time position. He moved between universities in the United States and England, staying with collaborators, working on several problems at once, and leaving when the work was done. In late 1948 he visited Hungary for the first time in ten years and saw his mother and surviving family. The same year brought the elementary proof of the prime number theorem and the dispute with Selberg described in Lesson 04. In 1951 he received the Cole Prize in number theory of the American Mathematical Society, and in 1952 he took a temporary post at the University of Notre Dame, declining a permanent offer.

In 1954, after he travelled to the International Congress in Amsterdam, the US immigration service refused him a re-entry visa. Officials cited his correspondence with a Chinese mathematician who had returned to China and his 1941 FBI record. For nine years he could not enter the United States. He spent much of that time in Israel, first for three months at the Hebrew University of Jerusalem and then as a permanent visiting professor at the Technion in Haifa, and in Europe. From 1956 Hungary allowed him to come and go freely, which was rare in the Eastern bloc. He was elected a corresponding member of the Hungarian Academy of Sciences in 1956 and a full member in 1962, and from 1962 he had a position at its Mathematical Institute.

This period produced his collaboration with Alfréd Rényi on random graphs (1959–1960), the Erdős–Rado work on partition relations for infinite cardinals, which founded the partition calculus of set theory, and the Erdős–Ko–Rado and Erdős–Ginzburg–Ziv theorems of 1961. In November 1963 the United States granted him a visa again. That year, at a number theory conference, he met Ronald Graham, who became his closest friend in America. Graham kept a room for him, stored his papers, managed his finances and later administered the prizes he offered for problems. Erdős travelled with two suitcases, appeared at a colleague’s door with the words “my brain is open”, and expected his host to organize meals while he did mathematics.

Last years, the Book and the legacy, 1971–1996

From the age of 84 his mother travelled with him everywhere, and she died in 1971, aged 91. Afterwards he began taking antidepressants and amphetamines. Graham once bet him 500 dollars that he could not stop for a month. Erdős won the bet, complained that mathematics had been set back a month, and resumed.

He had a private vocabulary that his colleagues learned. Children were “epsilons”. God was the “Supreme Fascist”, who kept a book, “the Book”, with the most elegant proof of every theorem. He did not believe in God, he said, but one should believe in the Book. Martin Aigner and Günter Ziegler’s Proofs from THE BOOK (1998) collects proofs in this spirit, several of them his.

Honours

He received the Wolf Prize in Mathematics for 1983/84, shared with Shiing-Shen Chern, for contributions to number theory, combinatorics, probability, set theory and analysis. He was a plenary speaker at the British Mathematical Colloquium (1957), an honorary member of the London Mathematical Society (1973), a foreign member of the Royal Netherlands Academy of Arts and Sciences (1977), an invited speaker at the International Congress of Mathematicians (1983), and a Foreign Member of the Royal Society (1989). He belonged to academies in eight countries, including the US National Academy of Sciences, and held about fifteen honorary doctorates.

Death

On 20 September 1996, while attending a conference in Warsaw, he had a heart attack and died, aged 83. He is buried next to his parents in the Jewish cemetery on Kozma Street in Budapest. He had suggested as his epitaph that he had finally stopped getting dumber.

Legacy

• Collaboration: about 1,500 papers with 511 co-authors. His most frequent partners were András Sárközy, András Hajnal and Ralph Faudree. The Erdős number, the collaboration distance to him, was described by Casper Goffman in 1969 and is now a standard example of a social network.
• Methods: the probabilistic method, random graphs and the partition calculus are whole fields that start from his papers.
• Problems: he offered prizes from 25 to 10,000 dollars for problems; many remain open, and a public database of Erdős problems has catalogued them since 2024.
• Students and the Hungarian school: his doctoral students include Géza Fodor (1954), Joseph Kruskal (1954) and Béla Bollobás (1967), and his influence shaped the Budapest school of combinatorics of László Lovász and Endre Szemerédi.
• Biography: Paul Hoffman’s The Man Who Loved Only Numbers and Bruce Schechter’s My Brain Is Open (both 1998), and George Csicsery’s film N Is a Number (1993).

Sources and further reading

Biography

1. J. J. O’Connor and E. F. Robertson, Paul Erdős, MacTutor History of Mathematics.
2. Paul Erdős, Wikipedia.
3. Paul (Pál) Erdős, Mathematics Genealogy Project.
4. V. T. Sós, Paul Erdős, 1913–1996, Aequationes Mathematicae 54 (1997).
5. L. Babai, In and out of Hungary: Paul Erdős, his friends, and times.
6. B. Bollobás, Paul Erdős, Biographical Memoirs of Fellows of the Royal Society 45 (1999).
7. P. Hoffman, The Man Who Loved Only Numbers, Hyperion, 1998.
8. B. Schechter, My Brain Is Open, Simon & Schuster, 1998.
9. The elementary proof of the prime number theorem: an historical perspective, D. Goldfeld.

Mathematics

1. P. Erdős, Beweis eines Satzes von Tschebyschef, Acta Sci. Math. (Szeged) 5 (1932).
2. P. Erdős, G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935).
3. P. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936).
4. P. Erdős, M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940).
5. P. Erdős, A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946).
6. P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947).
7. P. Erdős, On a new method in elementary number theory which leads to an elementary proof of the prime number theorem, Proc. Natl. Acad. Sci. USA 35 (1949).
8. P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959).
9. P. Erdős, A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959); On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960).
10. P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. 12 (1961).
11. P. Erdős, A. Ginzburg, A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10F (1961).
12. N. Alon, J. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016.
13. M. Aigner, G. M. Ziegler, Proofs from THE BOOK, Springer, 1998 and later editions.
14. Erdős problems, database maintained by T. Bloom.