Julia Robinson und Juri Matijassewitsch

Julia Robinson (1919–1985) und Juri Matijassewitsch (geboren 1947) sind die beiden Namen, die am engsten mit der Lösung von Hilberts zehntem Problem verbunden sind. Die US-Amerikanerin Robinson schuf ab 1950 gemeinsam mit Martin Davis und Hilary Putnam fast alle Bausteine des Beweises; der Leningrader Mathematiker Matijassewitsch fügte 1970 mit 22 Jahren das fehlende Teil hinzu. Das Ergebnis, heute DPRM-Satz genannt (nach Davis, Putnam, Robinson und Matijassewitsch), zeigt: Es gibt kein Verfahren, das für jede diophantische Gleichung entscheidet, ob sie ganzzahlige Lösungen hat.

Robinson war darüber hinaus eine Pionierin. 1976 wurde sie als erste Mathematikerin in die National Academy of Sciences der USA gewählt, 1983 übernahm sie als erste Frau die Präsidentschaft der American Mathematical Society. Matijassewitsch wurde einer der führenden Logiker der Sowjetunion und Russlands. Er leitete ab 1980 das Labor für mathematische Logik am Steklow-Institut in Sankt Petersburg und ist Mitglied der Russischen Akademie der Wissenschaften.

Hilberts zehntes Problem: Worum es geht

Auf dem Internationalen Mathematikerkongress in Paris stellte David Hilbert im Jahr 1900 eine Liste offener Probleme vor, die die Mathematik des 20. Jahrhunderts prägen sollte. Das zehnte davon lautet:

„Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.“

„Ganze rationale Zahlen“ ist ein alter Ausdruck für die gewöhnlichen ganzen Zahlen …, −2, −1, 0, 1, 2, … Eine diophantische Gleichung, benannt nach Diophant von Alexandria, ist eine Polynomgleichung mit ganzzahligen Koeffizienten, für die man ganzzahlige Lösungen sucht. Manche dieser Gleichungen haben unendlich viele Lösungen, etwa x² + y² = z² (zum Beispiel 3² + 4² = 5²) oder die Pellsche Gleichung x² − 2y² = 1 (zum Beispiel 3² − 2 · 2² = 1 und 17² − 2 · 12² = 1). Andere haben gar keine: x² + y² = 3 ist unlösbar, denn als Quadrate kommen nur 0 und 1 infrage, und keine Summe davon ergibt 3.

Hilbert fragte nicht nach der Lösung einer bestimmten Gleichung, sondern nach einem allgemeinen Verfahren, einem Algorithmus, der für jede beliebige diophantische Gleichung in endlich vielen Schritten „ja“ oder „nein“ sagt. Er rechnete offenbar damit, dass es ein solches Verfahren gibt. Um das Gegenteil beweisen zu können, musste man aber erst genau festlegen, was ein „Verfahren“ überhaupt ist. Das gelang erst 1936 Alan Turing und Alonzo Church, aufbauend auf Ideen von Kurt Gödel. Seitdem war eine negative Antwort denkbar.

Julia Robinson: Kindheit, Krankheit und der Weg nach Berkeley

Julia Hall Bowman wurde am 8. Dezember 1919 in St. Louis (Missouri) geboren. Ihre Mutter starb, als Julia zwei Jahre alt war. Sie und ihre zwei Jahre ältere Schwester Constance kamen zunächst zur Großmutter in die Wüste Arizonas; nach der Wiederheirat des Vaters zog die Familie nach Point Loma bei San Diego. Mit neun Jahren erkrankte Julia an Scharlach und danach an rheumatischem Fieber. Sie musste ein Jahr im Bett verbringen und versäumte insgesamt zwei Schuljahre. Eine Privatlehrerin brachte ihr den Stoff von vier Schuljahren in einem einzigen bei, und dabei entdeckte Julia ihre Freude an der Mathematik. Die Herzschwäche als Folge der Krankheit begleitete sie ihr Leben lang.

In der High School war sie das einzige Mädchen in den fortgeschrittenen Mathematik- und Physikkursen. 1936 begann sie mit 16 Jahren ein Studium am San Diego State College und wechselte 1939 an die University of California in Berkeley. Dort fand sie, was ihr bisher gefehlt hatte: ein lebendiges mathematisches Umfeld. Der Zahlentheoretiker Raphael Robinson unterrichtete sie, aus den gemeinsamen Gesprächen wurde Zuneigung, und im Dezember 1941 heirateten die beiden. Weil eine Regel der Universität verbot, dass Ehepaare in derselben Fakultät arbeiteten, konnte Julia Robinson lange keine reguläre Stelle im Mathematik-Department erhalten.

1948 promovierte sie bei dem Logiker Alfred Tarski in Berkeley. In ihrer Dissertation zeigte sie, dass sich die ganzen Zahlen mit den Mitteln der Logik innerhalb der rationalen Zahlen beschreiben lassen. Daraus folgt, dass es kein Verfahren gibt, das jede Aussage über die Arithmetik der rationalen Zahlen als wahr oder falsch entscheidet. Schon diese erste Arbeit zeigt das Thema ihres Lebens: Was lässt sich in der Zahlentheorie mechanisch entscheiden, und was nicht?

1949/50 arbeitete Robinson für die RAND Corporation an Fragen der Spieltheorie. In einer Arbeit von 1951 bewies sie, dass ein einfaches Lernverfahren, das „fiktive Spiel“, bei Zwei-Personen-Nullsummenspielen zu optimalen Strategien führt: Jeder Spieler reagiert immer wieder optimal auf die bisher beobachtete Spielweise des Gegners. Das Ergebnis wird in der Spieltheorie bis heute zitiert.

Robinsons Weg zum zehnten Problem: die Robinson-Hypothese

Diophantische Mengen

Um 1948 begann Robinson, sich mit der Frage zu beschäftigen, welche Mengen natürlicher Zahlen sich mithilfe diophantischer Gleichungen beschreiben lassen. Eine Menge S heißt diophantisch, wenn es ein Polynom P mit ganzzahligen Koeffizienten gibt, sodass gilt:

Zur selben Zeit vermutete der junge Logiker Martin Davis (1928–2023) in seiner Dissertation von 1950 etwas Weitreichendes: Jede Menge, die ein Computerprogramm auflisten kann (eine rekursiv aufzählbare Menge), sei diophantisch. Wäre das wahr, wäre Hilberts zehntes Problem unlösbar. Denn Turing hatte gezeigt, dass es auflistbare Mengen gibt, bei denen kein Programm für jede Zahl entscheiden kann, ob sie dazugehört. Davis und Robinson näherten sich dem Problem also von entgegengesetzten Seiten.

Die Hypothese von 1952

Das Haupthindernis war das exponentielle Wachstum. Polynome wachsen nur „polynomial“, während viele auflistbare Mengen Zahlen wie 2ⁿ enthalten, die viel schneller wachsen. Robinson zeigte 1952: Wenn es auch nur eine diophantische Beziehung zwischen zwei Zahlen gibt, die exponentiell, aber nicht übermäßig schnell wächst, dann ist sogar die Potenzrechnung a = b^c selbst diophantisch. Diese Annahme heißt seither Robinson-Hypothese. Für ihren Beweis nutzte sie raffiniert die Lösungen der Pellschen Gleichung.

Der Satz von Davis, Putnam und Robinson (1961)

Davis tat sich Ende der 1950er-Jahre mit dem Philosophen und Logiker Hilary Putnam (1926–2016) zusammen. Die beiden zeigten, dass jede auflistbare Menge „exponentiell diophantisch“ ist, also durch eine Gleichung beschrieben werden kann, in der Variablen auch im Exponenten stehen dürfen. Ihr Beweis setzte allerdings eine damals unbewiesene Annahme über Primzahlen voraus. Robinson fand einen Weg, auf diese Annahme zu verzichten, und 1961 erschien die gemeinsame Arbeit der drei in den Annals of Mathematics. Zusammen mit Robinsons Ergebnis von 1952 hing nun alles an einer einzigen Frage: Gilt die Robinson-Hypothese?

Viele Fachleute bezweifelten, dass die Hypothese stimmt. Robinson selbst hielt jahrelang an ihr fest. Ihre Schwester Constance Reid berichtete, dass Julia sich jedes Jahr beim Ausblasen der Geburtstagskerzen dasselbe wünschte: dass das zehnte Problem gelöst werde, ganz gleich von wem. Sie könne den Gedanken nicht ertragen, zu sterben, ohne die Antwort zu kennen.

Juri Matijassewitsch: Vom Olympiade-Talent zum Durchbruch

Juri Wladimirowitsch Matijassewitsch wurde am 2. März 1947 in Leningrad, dem heutigen Sankt Petersburg, geboren. Er besuchte die Schule Nr. 239, eine der bekanntesten Mathematikschulen der Sowjetunion, und ein Jahr lang das von Andrei Kolmogorow gegründete Internat für Physik und Mathematik in Moskau. Bei Mathematik-Olympiaden war er sehr erfolgreich, 1964 auch bei der Internationalen Mathematik-Olympiade in Moskau.

Im selben Jahr begann er sein Studium an der Universität Leningrad, wo der Logiker Sergei Maslow sein Betreuer wurde. Schon als Student versuchte er sich an Hilberts zehntem Problem, kam aber nicht weiter und wandte sich anderen Themen zu. Im Herbst 1969 bekam er eine neue Arbeit von Julia Robinson zur Besprechung in die Hand. Er erkannte sofort, wie er später schrieb, dass sie eine „frische und wunderbare Idee“ enthielt, und nahm das Problem wieder auf. Anfang Januar 1970 hatte er den Beweis, mit 22 Jahren. Noch im selben Jahr erwarb er den sowjetischen Doktorgrad eines Kandidaten der Wissenschaften, 1972 folgte die höhere Promotion zum Doktor der Wissenschaften.

Der Beweis von 1970: Fibonacci-Zahlen und der DPRM-Satz

Das fehlende Glied

Matijassewitsch zeigte, dass eine bestimmte exponentiell wachsende Beziehung diophantisch ist: die Beziehung „v ist die 2u-te Fibonacci-Zahl“. Die Folge, die auf Leonardo von Pisa zurückgeht, beginnt mit 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …; jedes Glied ist die Summe der beiden vorigen. Die Glieder mit geradem Index (1, 3, 8, 21, 55, …) wachsen von Schritt zu Schritt etwa um den Faktor 2,618, also exponentiell. Damit war die Robinson-Hypothese bewiesen.

Ein Schlüssel war eine Teilbarkeitseigenschaft, die Matijassewitsch in einem populären Buch des Mathematikers Nikolai Worobjow über Fibonacci-Zahlen fand: Ist das Quadrat der n-ten Fibonacci-Zahl F_n ein Teiler von F_m, dann ist F_n ein Teiler von m. Ein Beispiel: F₄ = 3, und 3² = 9 teilt F₁₂ = 144; tatsächlich ist 3 ein Teiler von 12. Mit solchen Eigenschaften gelang es, die Fibonacci-Beziehung durch ein System gewöhnlicher Polynomgleichungen auszudrücken.

Der DPRM-Satz

Die Folgerung ergibt sich so: Es gibt nach Turing eine auflistbare Menge, für die kein Programm die Zugehörigkeit entscheiden kann. Nach dem DPRM-Satz wird diese Menge durch eine diophantische Gleichung beschrieben. Gäbe es Hilberts Verfahren, könnte man damit auch die Zugehörigkeit zu dieser Menge entscheiden. Das ist unmöglich.

Der Satz hat überraschende Nebenwirkungen. Da die Primzahlen auflistbar sind, gibt es ein Polynom, dessen positive Werte (bei Einsetzen natürlicher Zahlen) genau die Primzahlen sind; 1976 wurde ein solches Polynom mit 26 Variablen explizit angegeben. Matijassewitsch zeigte außerdem, dass neun Unbekannte ausreichen, um jede auflistbare Menge diophantisch darzustellen. Und berühmte offene Fragen wie die Vermutung von Christian Goldbach oder die Riemannsche Vermutung lassen sich als Aussage formulieren, dass eine bestimmte diophantische Gleichung keine Lösung hat.

Als Robinson von dem Beweis erfuhr, schrieb sie Matijassewitsch einen Brief, aus dem ihre Freude spricht:

„Wenn Sie wirklich 22 sind, freut es mich besonders, dass Sie ein Baby waren, als ich die Vermutung zum ersten Mal aufstellte, und dass ich nur warten musste, bis Sie erwachsen sind!“

Zusammenarbeit über den Eisernen Vorhang

Bis 1970 hatten Robinson und Matijassewitsch keinen Kontakt; er kannte nur ihre veröffentlichten Arbeiten. Danach entwickelte sich trotz des Kalten Krieges und der Briefzensur ein reger Austausch. 1971 lernten sich die beiden persönlich kennen, im selben Jahr besuchten Julia und Raphael Robinson Leningrad. Gemeinsam bewiesen Robinson und Matijassewitsch, dass sich jede diophantische Gleichung auf eine mit nur 13 Unbekannten zurückführen lässt (veröffentlicht 1975). Mit Davis verfassten sie einen vielzitierten Überblick über die „positiven Aspekte einer negativen Lösung“, der 1976 in einem Band über die Hilbertschen Probleme erschien.

Matijassewitsch betonte stets, wie viel sein Beweis den Vorarbeiten von Robinson, Davis und Putnam verdankte. Deshalb trägt der Satz heute alle vier Namen, oft in der Reihenfolge DPRM oder MRDP.

Julia Robinsons späte Jahre und Ehrungen

Die Lösung des zehnten Problems machte Robinson international bekannt. 1976 wurde sie als erste Mathematikerin in die National Academy of Sciences gewählt; erst danach erhielt sie in Berkeley eine volle Professur. 1982 hielt sie die Noether-Vorlesung der Association for Women in Mathematics, benannt nach Emmy Noether. Im selben Jahr wurde sie zur Präsidentin der American Mathematical Society gewählt und trat das Amt 1983 als erste Frau an. 1983 erhielt sie zudem ein MacArthur-Stipendium. Damit steht sie in einer Reihe mit Mathematikerinnen wie Sophie Germain und Sofja Kowalewskaja, die gegen große Widerstände ihren Weg gingen.

Robinson selbst sah diese „ersten Male“ mit gemischten Gefühlen:

„Was ich wirklich bin, ist eine Mathematikerin. Statt als erste Frau dies oder das in Erinnerung zu bleiben, wäre es mir lieber, man erinnerte sich an mich, wie es sich für einen Mathematiker gehört: einfach wegen der Sätze, die ich bewiesen, und der Probleme, die ich gelöst habe.“

Im Sommer 1984 erkrankte sie an Leukämie und konnte ihre Amtszeit nicht mehr voll ausfüllen. Julia Robinson starb am 30. Juli 1985 im Alter von 65 Jahren.

Matijassewitschs weitere Arbeiten: Primzahlsieb, Vierfarbensatz und Riemann

Nach seinem Durchbruch arbeitete Matijassewitsch an der Leningrader Abteilung des Steklow-Instituts für Mathematik, seit 1980 als Leiter des Labors für mathematische Logik. Ab 1995 lehrte er zudem als Professor an der Universität Sankt Petersburg. 1997 wurde er korrespondierendes, 2008 ordentliches Mitglied der Russischen Akademie der Wissenschaften. Zu seinen Auszeichnungen gehören der Markow-Preis der Akademie der Wissenschaften der UdSSR (1980), ein Forschungspreis der Humboldt-Stiftung (1998) und Ehrendoktorate französischer Universitäten. 1993 erschien sein Buch Hilbert’s Tenth Problem, das bis heute als Standardwerk gilt.

Weithin bekannt ist ein hübsches Ergebnis, das er mit Boris Stetschkin fand: ein visuelles Primzahlsieb, gewissermaßen ein geometrischer Verwandter des Siebs von Eratosthenes. Man markiert auf der Parabel y = x² die Punkte über x = −2, −3, −4, … und über x = 2, 3, 4, … und verbindet jeden linken Punkt (−i | i²) mit jedem rechten Punkt (j | j²). Die Verbindungsgerade hat die Steigung j − i und schneidet die y-Achse genau bei y = i² + (j − i) · i = i · j. Jede zusammengesetzte Zahl wird so von mindestens einer Geraden getroffen; die Primzahlen bleiben übrig.

Daneben fand Matijassewitsch neue, überraschende Umformulierungen des Vierfarbensatzes, der besagt, dass vier Farben genügen, um jede Landkarte so zu färben, dass benachbarte Länder verschiedene Farben haben. In jüngerer Zeit beschäftigte er sich mit der Riemannschen Zetafunktion und ihren Nullstellen, also mit dem Problem, das Bernhard Riemann 1859 aufgeworfen hatte.

Zeitleiste: Hilberts zehntes Problem

1. 1900 Hilbert stellt in Paris sein zehntes Problem
2. 1919 Julia Bowman (später Robinson) wird am 8. Dezember in St. Louis geboren
3. 1947 Juri Matijassewitsch wird am 2. März in Leningrad geboren
4. 1948 Robinson promoviert bei Alfred Tarski in Berkeley
5. 1952 Robinson veröffentlicht die nach ihr benannte Hypothese
6. 1961 Davis, Putnam und Robinson: Jede auflistbare Menge ist exponentiell diophantisch
7. 1970 Matijassewitsch beweist die Robinson-Hypothese; Hilberts zehntes Problem ist negativ gelöst
8. 1975 Robinson und Matijassewitsch: Reduktion auf 13 Unbekannte
9. 1983 Robinson tritt als erste Frau das Amt der AMS-Präsidentin an (seit 1976 Mitglied der National Academy of Sciences)
10. 1985 Julia Robinson stirbt am 30. Juli

Bedeutung heute: Unentscheidbarkeit in der Zahlentheorie

Der DPRM-Satz brachte die Unentscheidbarkeit, die Gödel und Turing in der Logik entdeckt hatten, mitten in die klassische Zahlentheorie. Er zeigt, dass schon so elementare Objekte wie ganzzahlige Polynomgleichungen die volle Komplexität beliebiger Computerprogramme in sich tragen. Für die Praxis bedeutet das: Kein Computeralgebrasystem kann jemals jede diophantische Gleichung automatisch lösen; für einzelne Klassen von Gleichungen gibt es dagegen sehr wohl Verfahren.

Die Forschung an Varianten des Problems geht weiter. Ob es ein Entscheidungsverfahren für Gleichungen gibt, bei denen rationale Lösungen gesucht werden, ist bis heute offen. Für die ganzen Zahlen in algebraischen Zahlkörpern legten 2024/25 zwei Forschergruppen (Peter Koymans und Carlo Pagano sowie Levent Alpöge, Manjul Bhargava, Wei Ho und Ari Shnidman) unabhängig voneinander Beweise vor, dass auch dort kein allgemeines Verfahren existiert.

Julia Robinsons Name lebt in den weltweit veranstalteten Julia-Robinson-Mathematikfestivals für Schülerinnen und Schüler fort, 2008 erschien der Dokumentarfilm Julia Robinson and Hilbert’s Tenth Problem. Den größeren Zusammenhang beschreibt der Artikel über die Mathematik des 20. Jahrhunderts.

Häufige Fragen

Quellen und weiterführende Literatur

• Martin Davis: Hilbert’s Tenth Problem is Unsolvable. In: American Mathematical Monthly 80 (1973), S. 233–269.
• Martin Davis, Hilary Putnam, Julia Robinson: The Decision Problem for Exponential Diophantine Equations. In: Annals of Mathematics 74 (1961), S. 425–436.
• Juri Matijassewitsch: Hilbert’s Tenth Problem. MIT Press, Cambridge (Massachusetts) 1993.
• Constance Reid: Julia. A Life in Mathematics. Mathematical Association of America, Washington 1996.
• MacTutor History of Mathematics: Julia Robinson (englisch)
• MacTutor History of Mathematics: Yuri Matiyasevich (englisch)