# Paul Erdős

Paul Erdős [ˈɛrdøːʃ] (ungarisch Erdős Pál; * 26. März 1913 in Budapest, Österreich-Ungarn; † 20. September 1996 in Warschau, Polen) war ein ungarischer Mathematiker und einer der bedeutendsten Mathematiker des 20. Jahrhunderts. Paul Erdős arbeitete mit Hunderten von Kollegen auf den Gebieten Kombinatorik, Graphentheorie und Zahlentheorie zusammen. Erdős ist im Zusammenhang mit der Erdős-Zahl bekannt. Von ihm stammt außerdem die Idee zu dem BUCH, in dem Gott die perfekten Beweise für mathematische Sätze aufbewahrt. Ein Versuch, diesem Buch nahezukommen, stellt Das Buch der Beweise von Aigner und Ziegler dar, das 1998 veröffentlicht wurde und an dem er vor seinem Tod noch mitwirkte.

## Leben

Paul Erdős wurde als drittes Kind einer jüdischen Familie geboren. Da seine beiden Schwestern im Alter von drei und fünf Jahren schon vor seiner Geburt gestorben waren, wuchs er als einziges Kind von Anna († 1971) und Lajos Erdős auf. Seine Eltern waren beide Mathematiklehrer und in religiöser Beziehung Freidenker, was sich auch auf Paul Erdős übertrug. Sein Vater wurde 1914 im ersten Kriegsjahr als Angehöriger der österreich-ungarischen Armee bei einem Angriff der Russen in Galizien gefangen genommen und verbrachte als Kriegsgefangener mehrere Jahre in Sibirien. Während seine Mutter unterrichtete, wurde Paul von einer deutschen Gouvernante erzogen. Schon mit drei Jahren konnte er rechnen und mit vier konnte er Freunden der Familie im Kopf ausrechnen, wie viele Sekunden sie schon lebten.
Seine Mutter ließ ihn aus Angst vor ansteckenden Krankheiten, an denen seine beiden Schwestern gestorben waren, nicht in die öffentliche Schule gehen, sondern von einem Privatlehrer unterrichten. Erdős war als Kind in Alltagsdingen sehr auf seine Mutter angewiesen und lernte zum Beispiel nach eigenen Angaben erst mit elf Jahren, sich die Schnürsenkel zu binden. Auch als er eine höhere Schule besuchen sollte, ging er nur jedes zweite Jahr in eine Schule, da seine Mutter ihre Meinung oft änderte.
Seine Mutter wurde unter der kurzen Herrschaft des kommunistischen Béla Kun (1919) Direktorin der Schule, wurde aber unter der 1920 beginnenden Herrschaft von Admiral Miklós Horthy entlassen. Der von dieser Regierung geschürte Antisemitismus ließ viele jüdische Wissenschaftler (darunter Edward Teller, John von Neumann, Leó Szilárd und Eugene Wigner) das Land verlassen. 1920 kehrte sein Vater aus der sibirischen Kriegsgefangenschaft zurück. Er hatte sich in der Kriegsgefangenschaft Englisch beigebracht, allerdings ohne die Aussprache zu beherrschen, und übertrug diesen Akzent auf seinen Sohn.
Mit 17 Jahren schrieb sich Paul Erdős 1930 an der Universität ein. Dies war ihm nur möglich, weil die Zulassungsbeschränkungen von 1920 im Jahr 1928 wieder gelockert wurden und Juden als Gewinner nationaler Wettbewerbe wieder studieren konnten. Nur vier Jahre später (1934) erlangte er den Doktortitel in Mathematik. Da der Antisemitismus immer mehr zunahm, ging er noch im selben Jahr mit einem Stipendium nach Manchester zu Harold Davenport, reiste aber innerhalb Englands weit umher und traf unter anderem Godfrey Harold Hardy in Cambridge und den ebenfalls emigrierten Stanisław Ulam. 1938 nahm er seine erste Position in den USA, als Stipendiat, an der Princeton University (New Jersey) ein. Diese behielt er aber nicht lange, da ihn die Institutsleitung von Princeton für „eigentümlich und unkonventionell“ hielt, und er folgte einer Einladung von Ulam nach Madison. Um diese Zeit begann er die Gewohnheit zu entwickeln, von Campus zu Campus zu reisen. Er hielt es nie lange an einem Ort aus und reiste bis zu seinem Tode zwischen mathematischen Instituten hin und her.
1941 machte Paul Erdős einen Ausflug mit seinen Kollegen Arthur Stone und Shizuo Kakutani. Sie wollten von einer Erhöhung mit einem Turm aufs Meer hinausblicken. Nur über Mathematik nachdenkend, übersahen sie ein Schild „Zutritt verboten“. Sie machten ein paar Erinnerungsfotos und wurden später wegen Spionage vom FBI verhaftet und verhört. Das Missverständnis klärte sich bald auf, der Eintrag in eine FBI-Akte schadete ihm aber später in der McCarthy-Ära.
Erst nach dem Krieg erfuhr er vom Schicksal seiner Verwandten in Ungarn, von denen viele im Holocaust umgekommen waren. Sehr besorgt war er um seine Mutter, die den Holocaust überlebt hatte. Sein Vater war 1942 an einem Herzanfall gestorben. Als er im Dezember 1948 nach zehnjähriger Pause seine Mutter und Freunde (Paul Turan, Vera T. Sós, Miklós Simonovits und andere) in Ungarn besuchte, gelang es ihm erst im Februar 1949, Ungarn wieder zu verlassen, da Stalin im beginnenden Kalten Krieg die Grenzen hatte abriegeln lassen. Dann pendelte er drei Jahre lang zwischen England und den USA hin und her, bevor er 1952 eine Stelle an der US-amerikanischen University of Notre Dame annahm.
Als er 1954 zu einer Konferenz nach Amsterdam reisen wollte, wurde ihm nach einer Untersuchung vor einer McCarthy-Kommission erklärt, dass er, wenn er die USA verlasse, nicht wieder einreisen dürfe, was Erdős aber nicht davon abhielt, zu dieser Konferenz zu fahren.
Da ihm auch die Niederlande und England Reise- und Aufenthaltsbeschränkungen auferlegten, nahm er in den 1960er Jahren eine Stellung an der Hebräischen Universität Jerusalem an. Trotz vieler Versuche erhielt er erst 1963 wieder eine Einreiseerlaubnis in die USA. Offiziell wurde keine Begründung angegeben, aus den Akten ergibt sich aber, dass seine Verhaftung 1941 und seine Kontakte zu dem chinesischen Zahlentheoretiker Loo-Keng Hua die Ursache waren.
Seine Stelle in Jerusalem behielt Erdős formell für 30 Jahre: Er reiste jedoch stets von Universität zu Universität, um mit anderen Mathematikern zusammenzuarbeiten. Er veröffentlichte etwa 1500 gemeinsame Artikel, so viele wie kein anderer Mathematiker. Daraus entstand auch die halb scherzhafte Erdős-Zahl. Die 504 Mathematiker, die direkt mit ihm zusammenarbeiteten, haben die Erdőszahl 1; solche, die nicht mit Erdős, aber mit jemandem mit Erdőszahl 1 zusammenarbeiteten, haben die Erdőszahl 2; usw.
Er schlief täglich nur vier bis fünf Stunden und putschte sich mit Kaffee, Koffeintabletten und Amphetamin auf, welches er aufgrund von Depressionen nach dem Tod seiner Mutter verschrieben bekam. 1979 bot ihm sein Freund Ronald Graham eine Wette um 500 US-Dollar an, da er sich sorgte, dass Erdős abhängig sei: Er werde es nicht schaffen, 30 Tage ohne Aufputschmittel durchzuhalten. Er hielt die 30 Tage durch, meinte aber, die Wette habe die Mathematik um einen Monat zurückgeworfen, da er keinen Gedanken zu Papier bringen konnte. Nach der Wette nahm er den Amphetaminkonsum wieder auf.
Paul Erdős führte ein materiell einfaches Leben, das der Mathematik gewidmet war. Mit den Preisgeldern, die er gewann, unterstützte er begabte Studenten, spendete sie oder setzte sie als Preisgelder für schwierige Aufgaben aus. 1977 stiftete er den israelischen Erdős-Preis, benannt zu Ehren seiner Eltern. Der Paul-Erdős-Preis der Ungarischen Akademie der Wissenschaften ist ihm zu Ehren benannt.
1973 wurde er Ehrenmitglied der London Mathematical Society. 1974 wurde Erdős in die American Academy of Arts and Sciences gewählt, 1977 in die Königlich Niederländische Akademie der Wissenschaften und 1980 in die National Academy of Sciences. 1983 erhielt er den Wolf-Preis. 1983 hielt er einen Plenarvortrag auf dem ICM in Warschau (Extremal problems in number theory, combinatorics and geometry) und 1970 war er Invited Speaker auf dem ICM in Nizza (On the application of combinatorial analysis to number theory, geometry and analysis).
Im September 1996 nahm Erdős an einer Konferenz in Warschau über Graphentheorie teil. Dort starb er, der im letzten Jahrzehnt seines Lebens an Herzrhythmusproblemen gelitten hatte, am 20. September infolge zweier Herzinfarkte. Er liegt auf dem jüdischen Friedhof in Rákoskeresztúr, einem Stadtteil von Budapest, begraben, auf dem auch seine Eltern liegen.

## Werk

Erdős’ hauptsächliche Arbeitsgebiete waren Zahlentheorie und Kombinatorik. Außerdem war er ein Pionier in der Anwendung wahrscheinlichkeitstheoretischer Argumente in der Zahlentheorie und der Graphentheorie. Erdős war nicht so sehr am Aufbau von Theorien interessiert, sondern an der Lösung spezieller Probleme, mit möglichst einfachen, eleganten und „einsichtigen“ Beweisen.
1931 fand er noch als Student in Budapest einen eleganten elementaren Beweis von Bertrands Vermutung, dass es für $n>1$ immer eine Primzahl zwischen $n$ und $2n$ gebe (den Beweis führte schon Pafnuti Lwowitsch Tschebyschow). 1948 erregte er Aufmerksamkeit, als er zusammen mit Atle Selberg einen „elementaren“ (also ohne Funktionentheorie auskommenden) Beweis des Primzahlsatzes gab, nachdem im 19. Jahrhundert schon Tschebyschow mit „elementaren“ Methoden Abschätzungen gegeben hatte. Die Frage, welchen Anteil Erdős am Beweis hatte, war seitdem lange umstritten. Nach dem „Augenzeugen“ Ernst Gabor Straus war Erdős’ Beitrag (der in einem Seminar von Paul Turán in Princeton entstand) von wesentlicher Bedeutung auch für Selbergs Beweis. Ausgangspunkt war eine von Selberg bewiesene Ungleichung, die Turan zu einem elementaren Beweis des Satzes von Dirichlet über Primzahlen in arithmetischen Folgen nutzte. Erdős bewies mit der Ungleichung eine Verallgemeinerung des oben erwähnten Satzes von Tschebyschow (nämlich, dass es zwischen $\,x$ und $\,x(1+\epsilon )$ eine Primzahl gibt, $\epsilon$ fest und $x$ genügend groß). Als er dies Selberg mitteilte, wollte dieser es zunächst nicht glauben, da er damit einen elementaren Beweis des Primzahlsatzes hätte, den er zuvor vergeblich versucht hatte. Selberg lehnte eine von Erdős angebotene gemeinsame Veröffentlichung ab und veröffentlichte schließlich einen Beweis, der Erdős’ Beitrag umging. Selberg erhielt unter anderem dafür die Fields-Medaille, Erdős ging leer aus. Nach den Erinnerungen von Ernst Straus spielte dabei Hermann Weyl eine wichtige Rolle, der Selberg, der seiner mathematischen Herangehensweise näher stand, protegierte und dafür sorgte, dass die Annals of Mathematics Erdős’ Artikel zurückwiesen. Mit Mark Kac veröffentlichte Erdős Arbeiten zur wahrscheinlichkeitstheoretischen Deutung des Primzahlsatzes und bewies 1939 den Satz von Erdős-Kac, der – grob gesprochen – sagt, dass die Anzahl der Primfaktoren einer natürlichen Zahl „normalverteilt“ ist. Erdős hörte Kac den Satz als Vermutung in einer Vorlesung in Princeton aussprechen und kam kurz nach Ende des Vortrags mit einem Beweis.
Von Erdős stammt auch eine einflussreiche Arbeit über Primzahlzwillinge von 1940. 1946 bewies er gemeinsam mit Arthur Herbert Copeland, dass die nach ihnen benannte Copeland-Erdős-Zahl eine normale Zahl ist. 1975 bewies er mit John L. Selfridge den Satz von Erdős-Selfridge, dass das Produkt aufeinanderfolgender natürlicher Zahlen keine echte Potenz sein kann.
In der Kombinatorik arbeitete er in der Theorie extremaler Graphen, kombinatorischer Fragen der elementaren Geometrie und in der Ramseytheorie, die das Auftauchen von Ordnungen in genügend großen zufälligen Strukturen vorhersagt. Hier war er am Erdős-Szekeres-Theorem von 1935 beteiligt, das quantitativ sehr viel genauere Angaben in der Ramseytheorie macht. Außerdem brachte er die Idee asymptotischer Abschätzungen aus der Zahlentheorie in die Kombinatorik ein. Dieses Gebiet wird manchmal auch kombinatorische Zahlentheorie genannt.
Beispiele für seine Ergebnisse in der Kombinatorik sind eine Verallgemeinerung des „Happy Ending Theorem“ mit George Szekeres 1935 (eine genügend große Anzahl von Punkten in der Ebene in allgemeiner Lage – das heißt: keine drei Punkte liegen auf einer Geraden – enthält eine beliebig vorgegebene Anzahl von Punkten, die ein konvexes Polygon bilden). In dieser Arbeit wurden von Szekeres (damals Chemieingenieur-Student) auch Sätze von Frank P. Ramsey wiederentdeckt, die bald darauf von Erdős unter anderem zur Ramsey-Theorie ausgebaut wurden. 1957 bewies er den Satz, dass es für alle $k,m$ immer einen Graphen mit der „chromatischen Zahl“ (Mindestanzahl der zu verschiedener Färbung benachbarter Ecken nötigen Farben) $k$ gibt, in dem alle Zyklen (geschlossenen Wege) länger als $m$ sind.
In einer Serie von 1959 bis 1968 entstandenen Arbeiten mit Alfréd Rényi entwickelte er die Theorie zufälliger Graphen mit $m$ Ecken und $n$ Kanten. Die beiden konnten insbesondere Phasenübergänge für das Auftauchen neuer Eigenschaften und Strukturen in Abhängigkeit von der Größe des Graphen $(m,n)$ beweisen. Diese Arbeiten hatten auch Auswirkungen in der Informatik.
Ebenso wie für seine Sätze ist er für seine Vermutungen bekannt. Eine dieser Vermutungen ist, dass sich in jeder Menge natürlicher Zahlen, für welche die Summe der Kehrwerte der Elemente divergiert, beliebig lange arithmetische Folgen befinden (in einer Arbeit mit Turan 1936 vermutet). Für den Beweis einer etwas schwächeren Version erhielt der Mathematiker Endre Szemerédi 1000 Dollar von Erdős. Hillel Fürstenberg gab später einen ergodentheoretischen Beweis.
In der Mengenlehre wirkte Erdős an der Entwicklung der unendlichen Kombinatorik an führender Stelle mit. Zusammen mit András Hajnal, Richard Rado und anderen untersuchte er Partitionseigenschaften von Ordinalzahlen und überabzählbaren Kardinalzahlen und bewies Varianten und Verallgemeinerungen des Satzes von Ramsey, siehe Satz von Erdős-Rado.
Erdős erzielte auch wichtige Resultate in der numerischen Mathematik, insbesondere in der Theorie der Approximation von Funktionen, zum Beispiel in einer Arbeit mit Paul Turan 1937, in der sie zeigten, dass die Lagrangeschen Interpolationspolynome einer beliebigen stetigen Funktion im Mittel gegen diese Funktion konvergieren für beliebige Gewichtfunktionen an den aus den Wurzeln eines Systems orthogonaler Polynome gebildeten Stützstellen.