Direkt zum Inhalt

Zahlentheorie: Das Collatz-Problem, Sirenengesang für Mathematiker

Mathematiker warnen vor dem Collatz-Problem – zu schnell verliere man sich im einfachsten Problem der Mathematik. Terence Tao hat es dennoch gewagt. Mit Erfolg.
Ein Mann steht vor einer riesigen Tafel voller mathematischer BerechnungenLaden...

Die Collatz-Vermutung hat schon so einige Mathematiker fast in den Wahnsinn getrieben. Häufig wird es als das einfachste Problem der Mathematik bezeichnet, denn die Fragestellung ist erstaunlich simpel. Doch Experten warnen davor, zu tief darin einzutauchen. Denn wie ein Sirenengesang zieht es die Menschen in seinen Bann. Viele verlieren sich in dem Problem und finden nicht mehr heraus.

Doch Anfang 2019 wagte sich einer der renommiertesten Mathematiker der Welt wieder einmal an die Vermutung – und brachte dabei eines der bedeutendsten Ergebnisse seit Jahrzehnten hervor: Am 8. September veröffentlichte Terence Tao einen Beweis dafür, dass die Collatz-Vermutung zumindest für fast alle Zahlen fast wahr ist.

Ein einfaches Rätsel

Es gibt zwar keine schriftlichen Belege, doch man geht davon aus, dass der deutsche Mathematiker Lothar Collatz das nach ihm benannte Problem in den 1930er Jahren aufstellte. Tatsächlich klingt es wie ein Partytrick: Wähle eine beliebige Zahl; wenn sie ungerade ist, multipliziere sie mit 3 und füge 1 hinzu; ist sie gerade, dann teile sie durch 2. Das Ergebnis setzt man erneut in diese einfache Rechenvorschrift ein und wiederholt die Prozedur immer wieder.

Wahrscheinlich würde man erwarten, dass die sich daraus bildenden Ergebnisse stark von der anfangs gewählten Zahl abhängen. Für manche Startwerte könnte man irgendwann bei eins landen. Andere Zahlen könnten dagegen immer größere Werte hervorbringen und bis unendlich anwachsen. Doch Collatz sagte voraus, dass dieser Fall nicht eintritt. Er vermutete, dass jeder Startwert irgendwann zwangsläufig zur Eins führt. Sobald diese erreicht ist, ergeben die Regeln des Collatz-Problems eine endlose, sich wiederholende Schleife: 1, 4, 2, 1, 4, 2, 1, …

»Man lässt sich leicht von diesen großen, berühmten Problemen in den Bann ziehen, die weit über die Fähigkeit eines jeden hinausgehen. Dabei kann man viel Zeit verschwenden.« Terence Tao

Die betörende Einfachheit jener Vermutung zog über die Jahre etliche Hobbymathematiker und Rätselliebhaber an. »Man muss eine Zahl nur mit drei multiplizieren und durch zwei teilen können, und schon kann man damit herumspielen. Es ist sehr verlockend, sich daran zu versuchen«, erklärt der Mathematiker Marc Chamberland vom Grinnell College. Forscher haben inzwischen Trillionen (1018) von Startwerten getestet – alle folgen Collatzs Vorhersage. Online gibt es viele »Collatz-Rechner«, mit denen man verschiedene Zahlen nach dem einfachen Verfahren überprüfen kann. Zudem wimmelt es nur so von falschen Beweisen, in denen Amateure behaupten, das Problem auf die eine oder andere Weise gelöst zu haben.

Ein unmöglicher Beweis

In den 1970er Jahren konnten Mathematiker zeigen, dass fast alle Collatz-Folgen (die Liste der Zahlen, die man erhält, wenn man dem Vorgang folgt) irgendwann zu einem Ergebnis führen, das kleiner als der Startwert ist. Solche Beweise bestärken den Verdacht, dass Collatz richtig lag. In den kommenden Jahrzehnten blieben bedeutende Fortschritte allerdings aus. Deshalb sind viele Experten der Meinung, dass die Vermutung außerhalb der Reichweite des heutigen Verständnisses liegt – und dass es sinnvoller sei, seine Zeit anderen Themen zu widmen.

Terence Tao beschäftigt sich normalerweise nicht mit unmöglichen Problemen. 2006 gewann er die Fields-Medaille, eine der höchsten Auszeichnungen der Mathematik. Er ist es gewohnt, handfeste Probleme zu lösen, statt Hirngespinsten nachzujagen. »Das ist das Berufsrisiko eines Mathematikers«, erklärt er. »Man lässt sich leicht von diesen großen, berühmten Problemen in den Bann ziehen, die weit über die Fähigkeit eines jeden hinausgehen. Dabei kann man viel Zeit verschwenden.«

Doch auch Tao kann den Versuchungen nicht widerstehen. Jedes Jahr widmet er ein oder zwei Tage einem ungelösten Rätsel. Dabei unternahm er auch immer wieder Versuche, die Collatz-Vermutung zu lösen – jedoch ohne Erfolg.

Das sollte sich ändern, als im August 2019 ein anonymer Leser einen Kommentar auf Taos Blog hinterließ. Darin schlug er vor, das Problem nicht allgemein anzugehen, sondern es zunächst nur für fast alle Zahlen zu lösen. »Ich habe zwar nicht geantwortet, doch es hat mich zum Nachdenken gebracht«, erzählt Tao. Dabei fiel ihm auf, dass das Collatz-Problem mit so genannten partiellen Differenzialgleichungen zusammenhängt, die Taos Karriere in der Vergangenheit entscheidend prägten.

Komplizierte Gleichungen vereinfachen simples Problem

Wissenschaftler nutzen partielle Differentialgleichungen (PDGs), um viele der grundlegendsten physikalischen Prozesse zu modellieren, etwa die Entwicklung eines Fluids oder die Ausbreitung einer Gravitationswelle durch die Raumzeit. PDGs tauchen immer dann auf, wenn die zukünftige Position eines Systems von zwei oder mehr Faktoren abhängt. Zum Beispiel hängt der Zustand eines Teichs, nachdem man einen Stein hineingeworfen hat, unter anderem von der Viskosität und der Geschwindigkeit des Wassers ab.

Auf den ersten Blick scheinen die komplizierten Gleichungen nicht viel mit der einfachen Arithmetik der Collatz-Vermutung zu tun zu haben. Doch Tao erkannte, dass sie einige Gemeinsamkeiten bergen. Um den künftigen Zustand eines Systems zu verstehen, muss man Zahlen in die PDGs einsetzen, wodurch man neue Werte erhält und diese erneut in die Gleichungen einsetzt. Diesen Prozess wiederholt man immer wieder. Mathematiker interessieren sich in der Regel dafür, ob die Startwerte für eine bestimmte PDG irgendwann zu unendlichen Ergebnissen führen oder ob die Ausgabe unabhängig vom Startwert stets endlich bleibt.

Als Tao darüber nachdachte, fiel ihm auf, dass die Fragestellung der des Collatz-Problems ähnelt. Dort möchte man erfahren, ob aus wiederholtem Einsetzen in eine Gleichung immer eine Eins folgt, unabhängig vom Startwert. Dadurch begann er die Methoden, mit denen man PDGs untersucht, auch auf das Collatz-Problem anzuwenden.

Als besonders nützlich erwies sich dabei ein statistisches Verfahren, um das Langzeitverhalten dynamischer Systeme vorherzusagen. Dabei betrachtet man die Gleichungen für einen Satz von Startwerten und extrapoliert daraus, wie sich das System für alle möglichen Anfangswerte entwickelt.

Im Rahmen der Collatz-Vermutung analysiert man das Problem entsprechend mit einer großen Stichprobe aus Zahlen. Wenn nahezu 100 Prozent der Zahlen in der Stichprobe entweder genau bei eins oder sehr nahe daran enden, könnte man daraus schließen, dass sich fast alle anderen Zahlen auch so verhalten werden.

Um diesen Schluss zu ziehen, muss man die Stichprobe aber sorgfältig auswählen. Wie bei einer Meinungsumfrage muss sie die herrschenden Ansichten im richtigen Verhältnis enthalten. Zahlen haben ihre eigenen demografischen Merkmale. Es gibt ungerade und gerade Zahlen, Zahlen, die Vielfache von drei sind, und so weiter. Wenn man eine repräsentative Stichprobe konstruieren möchte, muss man sie so gewichten, dass bestimmte Arten von Zahlen auftauchen und andere nicht – je besser man die Gewichtungen wählt, desto genauer die Rückschlüsse.

Gewichtige Entscheidungen

Tao hat etwas viel Komplizierteres erarbeitet, als bloß eine geeignete Stichprobe von Zahlen. Denn nach jedem Schritt im Collatz-Prozess ändert sich die Zahlenmenge, unter anderem werden die Werte auf Dauer kleiner. Zudem können sich die Zahlen verdichten. Wenn man etwa mit einer gleichmäßigen Verteilung von eins bis eine Million beginnt, kann es sein, dass die Ergebnisse nach fünf Collatz-Iterationen in einem kleinen Intervall mit winzigen Abständen zueinander liegen. Mit anderen Worten: Man kann mit einer guten Stichprobe starten, doch nach wenigen Schritten ist sie hoffnungslos verzerrt.

Tao gelang es aber, eine Stichprobe von Zahlen zu finden, die während des Collatz-Prozesses weitgehend ihre ursprünglichen Gewichtungen beibehält. Seine Ausgangsprobe enthält beispielsweise keine Vielfachen von drei, da der Collatz-Prozess diese Zahlen ohnehin schnell aussortiert. Durch diese und kompliziertere Anforderungen behält die Stichprobe ihre wichtigsten Eigenschaften bei, selbst wenn man den Collatz-Prozess mehrfach durchläuft.

Damit konnte Tao beweisen, dass fast alle Collatz-Startwerte – 99 Prozent oder mehr – irgendwann einen Wert erreichen, der in der Nähe von eins liegt. Konkret bedeutet das zum Beispiel, dass 99 Prozent aller Ausgangswerte, die größer als eine Billiarde sind, schließlich eine Zahl unter 200 erreichen.

Auf diese Weise wird Tao leider nicht endgültig beweisen können, ob Collatz vor rund 90 Jahren richtig lag. Der Grund dafür ist, dass die Stichprobe nach jedem Schritt ganz leicht verzerrt wird. Je länger der Collatz-Prozess weitergeht und die Zahlen sich der Eins nähern, desto ausgeprägter wird die Verzerrung.

Damit ist Taos Werk sowohl ein Triumph als auch eine Warnung für alle Neugierigen: Gerade wenn man denkt, dass man das Collatz-Problem in die Enge getrieben hat, entflieht es einem wieder. »Man kann der Vermutung so nahekommen, wie man will, doch sie bleibt immer außer Reichweite«, sagt  Tao.

Logo Quanta MagazineLaden...
Von »Spektrum der Wissenschaft« übersetzte und redigierte Fassung des Artikels »Mathematician Proves Huge Result on ›Dangerous‹ Problem« aus »Quanta Magazine«, einem inhaltlich unabhängigen Magazin der Simons Foundation, die sich die Verbreitung von Forschungsergebnissen aus Mathematik und den Naturwissenschaften zum Ziel gesetzt hat.
04/2020

Dieser Artikel ist enthalten in Spektrum - Die Woche, 04/2020

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnervideos