The Mathematical Nomad, Paul Erdős
The man who loved only numbers …and people
Mathematical truth is immutable; it lies outside physical reality … This is our belief; this is our core motivating force. Yet our attempts to describe this belief to our nonmathematical friends are akin to describing the Almighty to an atheist. Paul embodied this belief in mathematical truth. His enormous talents and energies were given entirely to the Temple of Mathematics. He harbored no doubts about the importance, the absoluteness, of his quest.
This is how American mathematician Joel Spencer remembers the now legendary late Hungarian mathematician Paul Erdős (1913–1996). Throughout his life, the nomadic Erdős was known for many things, not least of all his personal eccentricities, unimaginable cognitive abilities and purity of mission.
Born in Austria-Hungary two years before the breakout of World War I, he thought himself mathematics from books and could multiply three-digit numbers in his head before the age of four. Living out of a suitcase traveling from university to university, throughout his life he survived off speaking fees and modest endowments from various universities. As a teenager, he reproved Chebyshev’s theorem before the age of 20. He was awarded a doctorate in mathematics in addition to his undergraduate degree at age 21. In his 83 years of life, he published over 1500 academic papers with more than 500 collaborators, making him the most prolific mathematician in history, comparable only with Leonard Euler.
Here’s to Paul Erdős, who dedicated his life solely to mathematics — and his friends.
Paul Erdős was born in Budapest, Austria-Hungary on the 26th of March 1913 to parents Lajos and Anna Erdős. His parents were both high school math teachers, which, in Hungary at the time required them to have Ph.Ds in mathematics. His two older sisters died at ages 3 and 5 from scarlet fever a few days before he was born, and so he grew up an only child. Protective of her son, his mother Anna reportedly kept Erdős away from school for most of his formative years, instead choosing to tutor him at home until age 10. This she did, in addition to being the sole provider for the household following Erdős’ father’s capture during World War I. As his mother went to work during the day, a German governess was hired to look after Paul (O’Connor and Robertson, 2000).
The quintessential child prodigy, Erdős’ fascination with mathematics developed early as he taught himself to read by going through math books that his parents left around the house. By the time he was four, he could calculate in his head how many seconds a person had been alive (Hoffman, 1998). Once, when asked by a friend of his parents how much 250 less than 100 is, the three-year old Erdős is reported to have replied ”150 below zero”, already having discovered negative numbers. Being math teachers, his parents would both encourage Erdős’ talents for mathematics. Already at the age of 16, his father introduced him to infinite series and set theory, which would become lifelong obsessions for him.
During high school, Erdős would regularly solve the problems posed in the Középiskolai Matematikai és Fizikai Lapok (KöMaL), a monthly publication of Math and Physics texts for Secondary Schools often credited with a large share of Hungarian students’ success in mathematics in the late 19th and early 20th century (Babai, 2001). As an adult, Erdős would later go on to publish several articles about problems in elementary plane geometry in the periodical, despite its target audience’s median age of 17–18 years old. In 1962, future combinatorial mastermind László Lovász reportedly came across one of Erdős’ articles and was “so enchanted that he read it nearly 20 times”. It was also through KöMaL that Erdős would first meet his long time collaborators Pál Turan (1910–1976) and Tibor Gallai (1912–1992).
During the post-world war I period in Europe, Hungary in 1920 fell under the rule of a right-wing conservative (some say nationalist) admiral named Miklós Horthy. Horthy enacted the first European antisemitic laws similar to those Hitler would introduce in Germany thirteen years later, including limiting the number of Jews that were permitted to study in Hungarian universities. Despite this “Numerus Clausus” law, Erdős, Turan and Gallai would all enter Pázmány Péter University in Budapest on account of their winning national mathematics competitions.
Erdős entered university to study mathematics at the age of 17 in 1930 (Bruno & Baker, 1999). He was awarded his doctorate in addition to an undergraduate degree in 1934 for his dissertation entitled Über die Primzahlen gewisser arithmetischer Reihen (“On Primes in Certain Artithmetic Series”). In his dissertation he proved the existence of prime numbers between n and 2n in certain arithmetic progressions. Reportedly, his proofs were “striking for their elegance”, despite being formulated by a 19-year old. His advisor was Lipót Fejér, the thesis advisor of numerous other Hungarian geniuses including John von Neumann, George Pólya and Erdős’ friend Pál Turán. Following his graduation, Erdős accepted a post-doctoral fellowship at the University of Manchester working with Louis J. Mordell, who arranged for him to receive a four-year fellowship there (Babai, 1996). Already during this tenure, he travelled widely in the UK, meeting G.H. Hardy and Stanislaw Ulam in 1934 and ’35, respectively.
His wanderlust was already in evidence. […] From 1934 he hardly ever slept in the same bed for seven consecutive nights”. — Béla Bollobás
As Hitler took Austria in the Anschluss of March 1938, Erdős had to cancel his planned trip home for the spring, only to return briefly during the summer before hastily returning to England, and then America. In the U.S., Erdős accepted a year-long scholarship of $1500 at the Institute for Advanced Study, mingling in Princeton University’s Fine Hall with fellow European refugees the likes of Albert Einstein, Kurt Gödel, John von Neumann, Oscar Morgenstern and Eugene Wigner. Even in 1996, Erdős would remember 1938–39 as his best year (Babai, 1996). As Erdős did not conform to Princeton’s standards (reportedly being perceived as “uncouth and unconventional”) however, he was only offered six-month extensions to his fellowship and eventually instead took up an invitation from Ulam to visit at the University of Wisconsin — Madison, setting out on what would become a lifelong trek from institution to institution, all over the world.
“In the taxonomy of mathematicians, there are problem solvers and theoreticians“ — Sylvia Nasar
Erdős was the former (see the Two Cultures of Mathematics by Gowers, 2000 for an in-depth discussion of the differences). Believing strongly in the practice of mathematics as a social activity, most of his papers were written with co-authors. As of the writing of this essay, Erdős had 80,587 citations on his 1,525 publications on Google Scholar, with a reported 511 different collaborators (Oakland University, 2015), although as his childhood friend would recall:
I don’t think Erdős actually wrote many papers himself. His handwriting was abominable. Readable, but childlike. — Andrew Vázsonyi
In 1845 Joseph Bertrand (1822–1900) conjectured that there is always at least one prime between n and 2n for n ≥ 2. Bertrand himself verified the statement for all numbers in the interval 2 < n < 3,000,000. The conjecture was proved by Pafnuty Chebyshev (1821–1894) in 1852. A simpler proof using the properties of the Gamma function was later provided by Ramanujan in 1919.
At age 19, Erdős in 1932 published his first paper, providing a surprising elementary proof using binomial coefficients and the Chebyshev function ϑ(x). The paper, entitled Beweis eines Satzes von Tschebyschef (“On a proof of a theorem of Chebyshev”) was published in Acta Scientifica Mathematica. His proof considers the middle binomial coefficient:
A lower bound is:
Indeed, the binomial coefficient in equation 1 is the largest term in the 2n+1-term sum:
The first part of Erdős’ proof shows that if there is no prime p with n < p ≤ 2n, then we can put an upper bound on the binomial coefficient that is smaller than 4ⁿ / (2n +1) unless n is “small”. This verifies Bertrand’s postulate for all sufficiently large n. The second part deals with small the cases where n is “small”. These are dealt with by hand. For a narration of these cases, see Galvin (2015).
The Prime Number Theorem
In July 1948, Erdős met Norwegian mathematician Atle Selberg at the Institute for Advanced Study. From their brief encounter, an elementary proof of the Prime Number Theorem appeared (Babai, 1996). Originally emerging as a consequence of the independent works of Legendre, Gauss and Dirichlet, the prime number theorem states:
The theorem was famously independently proved by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using the Riemann zeta function. Selberg in March 1948 established that the asymptotic formula
Where the Jacobi theta function ϑ(x) is equal to the sum of the log of primes less than or equal to x and O(x) is an upper bound for x expressed in Big O notation. By July, both Selberg himself and Erdős had used Selberg’s formula to prove the prime number theorem. Who of the two proved the result first became somewhat of a priority dispute (Goldfeld, 2004), leading the two to unfortunately never collaborate again.
Of Erdős’ most consequential results, his contributions to the development of Ramsey theory clearly stand out. Ramsey theory is the branch of mathematics concerned with studying the ‘conditions under which order must appear’. A typical example of a such a problem starts out with a mathematical structure (such as a graph), which is then cut into pieces. A typical question is “How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property?”
The Erdős-Szekeres Theorem (1935)
The Erdős-Szekers theorem makes precise one of the corollaries of Ramsey theory, namely that given r and s any sequence of distinct real numbers with length at least (r - 1)(s - 1) + 1 contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s. The result was first shown in Erdős and Szekers’ influential 1935 paper A combinatorial problem in geometry:
The Erdős-Szekeres theorem (1935)
Any real sequence of at least ad + 1 terms contains either an ascending subsequence of a + 1 terms or a descending subsequence of d + 1 terms.
A subsequence is a sequence that can be derived from another sequence by deleting some of the elements without changing the order of the sequence. For instance, given the sequence ABCD, its subsequences are ABC, BCD, AB, BC, CD, AC, AD, BC and BD. Given r = 2 and s = 2:
For r = 2 and s = 2, the formula tells us that any permutation of three numbers has an increasing subsequence of length three or a decreasing subsequence of length two. Among the six permutations of the numbers 1,2,3: • 1,2,3 has an increasing subsequence of all three numbers
• 1,3,2 has a decreasing subsequence: 3,2
• 2,1,3 has a decreasing subsequence: 2,1
• 2,3,1 has two decreasing subsequences: 2,1 and 3,1
• 3,1,2 has two decreasing subsequences: 3,1 and 3,2
• 3,2,1 has three decreasing subsequences: 3,2, 3,1, and 2,1.
In their paper Erdős and Szekeres used proof by induction to show that f(n) = (n - 1)² + 1, where f(n) denotes the least integer such that any subsequence of f(n) real numbers must contain a monotone subsequence of length n. Steele (1995) later reviewed six different proofs of the same theorem, including the original proof by Erdős and Szekeres (1935), those by the pigeon-hole principle (Hammersley, 1972; Black, 1971; Seidenberg, 1959), one by one-to-one correspondence (Standon and White, 1986) as well as one that follows from Dilworth’s theorem (1950). The most widely cited proof is likely that of Hammersley (1972). The key idea of this proof by pigeon-hole is to place the elements of the sequence x₁, x₂, …, xₘ with m = n² + 1 into a set of ordered columns by the following rules: a) let x₁ start the first column, and b) for i ≥ 1, if xᵢ is greater than or equal to the value that is on top of a column, put xᵢ on top of the first such column, and c) otherwise start with a new column xᵢ (Steele, 1995).
There are two points of notice in Hammersley’s proof. The first is that the elements of any column correspond to an increasing subsequence. The second is that the only time we shift to a later column is when we have an element that is smaller than one of its predecessors. Thus, given k columns in the final construction, one can trace back from the last and find a monotone subsequence of length k. Since n² + 1 numbers are placed into the column structure, one must either have more than n columns or some column of greater height than n. Either way, there must be a monotone subsequence of length n + 1 (Steele, 1995).
The “slickest and most systematic” of the proofs, according to Steele, is that which “is naturally suggested by dynamic programming”, presented in a single page by Seidenberg (1959):
Proof of the Erdős-Szekeres theorem (Seidenberg, 1959)
Given a sequence of length (r - 1)(s - 1) + 1, label each number nᵢ in the sequence with a pair (aᵢ, bᵢ) where: • aᵢ is the length of the longest monotonically increasing subsequence ending with nᵢ and
• bᵢ is the length of the monotonically decreasing subsequence ending with nᵢ.Each two numbers in the sequence are labeled with a different pair: if i < j and nᵢ ≥ nⱼ then aᵢ < aⱼ and on the other hand if nᵢ ≥ nⱼ then bᵢ < bⱼ. But, there are only (r - 1)(s - 1) possible labels if aᵢ is at most r - 1 and bᵢ is at most s - 1. So, by the pigeonhole principle, there must exist a value of i for which aᵢ or bᵢ is outside this range.If aᵢ is out of range then nᵢ is part of an increasing sequence of length at least rᵢ. If bᵢ is out of range then nᵢ is part of a decreasing sequence of length at least s.
The Happy Ending Theorem (1935)
It was Erdős and Szekeres’ mutual friend Esther Klein who in 1932 first observed that:
The Happy Ending theorem
Any set of five points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral.
Points in general position in the plane are points which no three belong to a line. Convex quadrilateral are polygons with four edges and four corners whose interior angles are less than 180°, such as rectangles, rhomboids, trapezoids and parallelograms. The three distinct types of placements of five points in general position in the plane are (Morris & Soltan, 2016):
The problem statement and theorem was one of the first influential results that eventually led to the development of Ramsey theory. Erdős called the result the “Happy Ending Problem” because it eventually lead the marriage of Szekeres and Klein. The theorem is a particular case of the more general theorem proved by Erdős and George Szekeres in the same 1935 paper that proved the Erdős-Szekeres theorem of monotonically increasing and decreasing infinite subsequences, namely that:
Erdős & Szekeres' Generalization of the Happy Ending Theorem (1935)
For any positive integer n, any sufficiently large finite set of points in the plane in general position has a subset of n points that form the vertices of a convex polygon.
The Erdos-Szekeres conjecture (1935)
While the Erdős-Szekeres theorem (1935) proves the existence of the finite number g(n), in the same paper Erdős and Szekeres also conjectured what the number g(n) is:
The Erdős-Szekeres conjecture
The smallest number of points m for which any general position arrangement contains a convex subset of n points is 2ⁿ⁻² + 1.
The conjecture is known to hold for its known values of g(3), g(4), g(5), g(6). It is trivial to observe that g(3) = 3, i.e. that any three points in the plane that do not belong to a line form a triangle with interior angles less than 180°. Klein’s observation in the happy ending theorem is that g(4) = 5. That g(5) = 9 was first proven by Endre Makai, but first appeared in print in a proof by Kalbfleisch, Kalbfleisch and Stanton (1971). A computer-aided proof that g(6) = 17 was proved by Szekeres & Peters (2006). They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons. The value of g(n) is unknown for values larger than n = 6, and the Erdős-Szekeres conjecture still remains open.
For the results mentioned, and (literally) thousand others, Erdős was throughout his life recognized as a first-rate mathematician. Although he was never awarded the prestigious Fields Medal, he was awarded several other prestigious awards for his mathematical achievements.
In 1951 he was awarded the Cole Prize of the American Mathematical Society for his many papers on the theory of numbers, in particular for his paper On a new method in elementary number theory which leads to an elementary proof of the prime number theorem, published in the Proceedings of the National Academy of Sciences in 1949. In 1984, he was awarded the prestigious Wolf Prize in mathematics by the Wolf Foundation in Israel for “for his numerous contributions to number theory, combinatorics, probability, set theory and mathematical analysis, and for personally stimulating mathematicians the world over”. He donated most of the money from the award to the Department of Mathematics at the Technion for the establishment of a memorial fund in the name of his mother Anna (Israel Institute of Technology, 1997).
During the last decades of his life he was awarded at least fifteen (!!) honorary doctorates, and became a member of the scientific academies of eight countries, including in his native Hungary, the U.S., UK and Israel.
Among his family members, Erdős’ father had died of a heart attack in 1942, but due to the war, Erdős didn’t learn of this until 1945. His mother survived the prosecution of Jews in Hungary by hiding. Erdős saw her again in 1948 when he went back to Hungary for the first time since before the war. Eventually, as Erdős began moving from institution to institution in America, his mother began traveling with him. Erdős reportedly held her hand as she went to bed each night, right up until her death in 1971 in Calgary where Erdős was giving a lecture.
Starting around the time of the death of his mother in 1971, Erdős fell depressed and began taking medication, first antidepressants then amphetamines in the form of Benzedrine/Ritalin, supposedly at a dose of 10 to 20 milligrams per day. As one of the leading scientists in Hungary, he had no trouble finding doctors to prescribe him what he wanted. Around the same time (perhaps unsurprisingly) he also began increasing the number of work-hours of the day, upwards of 19 at the most (Hoffman, 1998).
Worried about his drug use, Graham in 1979 famously bet Erdős $500 that he could not stop taking amphetamines for a month (Hill, 2004). Erdős quit cold turkey and after 30 days won the bet, prompting him to proclaim:
You’ve showed me I’m not an addict. But I didn’t get any work done. I’d get up in the morning and stare at a blank piece of paper. I’d have no ideas, just like an ordinary person. You’ve set mathematics back a month.
After the month break, Erdős promptly resumed his use of amphetamines. According to mathematician Jochanan Schonheim “He took the pills discreetly and never talked about it, though he didn’t keep it a secret either. In the last years of his life, he stopped using those pills because of heart problems. He had a pacemaker at the end.” (Karpel, 2002).
As a tribute to his prolific career, Erdős’ collaborators came up with the idea of an Erdős number, describing the “collaborative distance” between Erdős and another researcher, as measured by authorship of published papers. For instance: Erdős himself has Erdős number 0. People who co-authored a paper with Erdős have Erdős number 1. People who co-authored a paper with someone of Erdős number 1 have Erdős number 2 and so on. In his lifetime his three most frequent collaborators were András Sárközy (62 papers), András Hajnal (56 papers) and Ralph Faudree (50 papers). His friend Pál Turán wrote 30 papers with Erdős, while Graham co-authored 28.
The description of an Erdős number was published by Casper Goffman in a 1969 paper entitled And what is your Erdős number? in the American Mathematical Monthly. Later the Erdős number gained prominence as a tool to study how mathematicians cooperate to find answers to unsolved problems. Today, several projects are devoted to studying connectivity among researchers, using the Erdős number as a proxy. For example, Erdős collaboration graphs can tell us how authors cluster, how the number of co-authors per paper evolves over time, or how new theories propagate.
He loved to play silly tricks to amuse children and to make sly jokes and thumb his nose at authority. But most of all, Erdős loved those who loved numbers, mathematicians. — Bruce Schechter (1998)
Over the years, Erdős accrued as much fame for his personality as he did for his mathematics. Described by his biographer Paul Hoffman as “probably the most eccentric mathematician in the world”, famously Erdős developed his only language to accompany his unique nomadic lifestyle, referring to himself as a PGOM, LD, AD, LD, CD, a “poor great old man, living dead, archaeological discovery, legally dead, counts dead”. Famously, possessions meant little Erdős, who carried most of his belongings in “two half-full suitcases” as he travelled from institution to institution, living with friends and colleagues.
“When I contemplated leaving mathematics to go to the Technical University and become an engineer, Erdős said: “I’ll hide, and when you enter the gate of the Technical University, I will shoot you”. This settled the issue. — Andrew Vázsonyi
Despite his wandering lifestyle, Erdős was famously absentminded, regularly misplacing his passport, wallet and glasses. Characteristically, he would blame his absentmindedness on “the SF”, “supreme fascist”, his own idiosyncratic term for God. In addition to his use of such terms, Erdős is often remembered for his use of aphorisms such as “There are three signs of senility. The first sign is that man forgets his theorems. The second sign is that he forgets to zip up. The third sign is that he forgets to zip down.”
Erdős began learning English at age 7 when his father returned from Siberia, where he had learned English to pass along the hours in captivity. Having had no English teacher, his father had however not learned how to pronounce words, and so set about teaching his son English with a strange Hungarian accent. The accent remained one of Erdős’ most characteristic traits throughout his life.
Anecdotes about Erdős’ cognitive abilities abound. His childhood friend Andy Vázsonyi tells stories of being only a teenager when Erdős came to see him in his father’s shoe store in Budapest.
"I was sitting in the back of the shop one day, when Erdős knocked at the door and entered. "Give me a four digit number,” he said. “2,532,” I replied. “The square of it is 6,411,024. Sorry, I am getting old and cannot tell you the cube”, he said. “How many proofs of the Pythagorean Theorem do you know?” “One,” I said. “I know 37,” he replied. "Did you know that the points of a straight line do not form a countable set?” He proceeded to show me Cantor’s proof of using the diagonal. “I must run,” and with that he left."- Excerpt, The World's Most Beloved Mathematical Genius "Leaves" by Andrew Vázsonyi (1996)
In addition to his mathematical genius, unusual lifestyle and eccentric personality, Erdős was known to his friends, collaborators and admirers for his compassion for other people.
Money received from awards and other jobs, Erdős generally donated to people in need and various worthy causes. Living off stipends and modest fees from universities and conferences, any money left over he used to fund cash prizes for proofs of problems he found interesting. The prizes varied from $25 to several thousand dollars. The most famous of such ‘Erdős problems’ is likely the Collatz conjecture, for which Erdős offered $500 for the person who comes up with a solution.
In “N is A Number: A Portrait of Paul Erdos”, Ron Graham tells the story of a young mathematician who was admitted to Harvard, but whose parents wouldn’t agree to pay for him, despite being able to afford it. Having only met the student once randomly, Erdős gave him $1000 saying “Pay me back if you can. If you can’t, please do the same for someone else”.
Indicative of his principled, compassionate life, shortly before his death in 1996 Erdős renounced an honorary degree from the University of Waterloo over what he considered to be the unfair treatment of his colleague Adrian Bondy who was dissmissed from his tenured position for his acceptance of a teaching position in France.
Erdős died in Warsaw, Poland on September 20th 1996, age 83. He was attending a conference when he had a heart attack (Bruno, 1999). His death was remembered by most of the worlds’ foremost news publications, including obituaries in The Chicago Tribune, The New York Times, The Independent, The Washington Post and many others.
To find another life this century as intensely devoted to abstraction, one must reach back to Ludwig Wittgenstein (1889–1951), who stripped his life bare for philosophy. But whereas Wittgenstein discarded his family fortune as a form of self-torture, Mr. Erdős gave away most of the money he earned because he simply did not need it … And where Wittgenstein was driven by near suicidal compulsions, Mr. Erdős simply constructed his life to extract the maximum amount of happiness. — The Economist, 1996
In my opinion there are two canonical biographies of Erdős’ life. One, heavily cited in this essay, is Paul Hoffman’s 1998 book entitled “The Man Who Loved Only Numbers”. The other, is the documentary film made about Erdős in 1993, entitled “N is a Number: A Portrait of Paul Erdos”. In addition, I would recommend to interested readers one article: Paul Erdős just left town by László Babai and a book: Erdős on graphs: His Legacy of Unsolved Problems written by his friends Fan Chung and her husband Ron Graham.
Other resources are available at Oakland University’s Erdős Number Probject website at: https://oakland.edu/enp/erdosdeath/.
This essay is part of a series of stories on math-related topics, published in Cantor’s Paradise, a weekly Medium publication. Thank you for reading!