Mathematiker haben einen Durchbruch in der Erforschung des „gefährlichen“ Problems erzielt

Mathematiker betrachten die Collatz-Hypothese als „Sumpf“ und warnen sich gegenseitig, dass es sich lohnt, sich davon fernzuhalten. Inzwischen hat Terence Tao mehr Fortschritte gemacht als jeder andere seit Jahrzehnten.

Nimm eine beliebige Nummer. Wenn es gerade ist, teilen Sie es in zwei Teile. Wenn ungerade, multiplizieren Sie mit drei, addieren Sie eins. Wiederholen. Kommt irgendwann eine Zahl auf 1?

Erfahrene Mathematiker raten Anfängern, sich von der Collatz-Hypothese fernzuhalten. Sie nennen es ein Sirenenlied: Fallen Sie unter seinen Einfluss, und Sie können nie zu sinnvoller Arbeit kommen.

Die Collatz-Hypothese, vielleicht das einfachste der ungelösten Probleme der Mathematik, ist genau das, was sie so verräterisch attraktiv macht.

„Das ist eine sehr gefährliche Aufgabe. Die Leute sind davon besessen, auch wenn es völlig unmöglich ist “, sagte Jeffrey Lagarias , Mathematiker an der Universität von Michigan und Experte für die Collatz-Hypothese.

Doch 2019 wagte sich einer der besten Mathematiker der Welt daran und erhielt das bedeutendste aller Ergebnisse, die in mehreren Jahrzehnten erzielt wurden.

Am 8. September 2019 veröffentlichte Terence Tao einen Beweis dafür, dass die Collatz-Hypothese für alle Zahlen mindestens „fast“ wahr ist. Obwohl das Ergebnis des Tao kein vollständiger Beweis für die Hypothese ist, ist dies ein sehr schwerwiegender Durchbruch für eine Aufgabe, bei der es nicht so einfach ist, alle ihre Geheimnisse preiszugeben.

"Ich hatte nicht erwartet, das Problem vollständig zu lösen", sagte Tao, Mathematiker an der University of California in Los Angeles. "Aber ich habe mehr geschafft, als ich erwartet hatte."

Collatz Puzzle

Lothar Collatz hat wahrscheinlich in den 1930er Jahren eine gleichnamige Hypothese aufgestellt. Die Herausforderung klingt wie ein Partytrick. Nimm eine beliebige Nummer. Wenn es gerade ist, teilen Sie es in zwei Teile. Wenn ungerade, multiplizieren Sie mit drei, addieren Sie eins. Holen Sie sich eine neue Nummer. Wende die gleichen Regeln für ihn an. Die Hypothese besagt, was passiert, wenn Sie diesen Vorgang wiederholt ausführen.

Die Intuition legt nahe, dass die Startnummer das Endergebnis beeinflusst. Vielleicht werden einige Zahlen irgendwann auf 1 sinken. Vielleicht werden andere Zahlen auf unbestimmte Zeit zunehmen.

Collatz sagte jedoch voraus, dass dies nicht der Fall ist. Er schlug vor, dass, wenn Sie mit einer positiven ganzen Zahl beginnen und die angegebene Sequenz für eine lange Zeit wiederholen, Sie von einer beliebigen Anfangszahl zu 1 gelangen. Und wenn Sie zur Einheit gelangen, werden Sie die Hypothesenregeln in einer Endlosschleife fangen: 1, 4, 2, 1, 4, 2, 1 und so weiter bis unendlich.

Im Laufe der Jahre haben sich viele Aufgabenliebhaber für die attraktive Einfachheit der Collatz-Hypothese oder des sogenannten „3x + 1-Problems“ interessiert. Mathematiker haben bereits eine Billion Beispiele überprüft (dies ist eine Zahl mit 18 Nullen), ohne eine einzige Ausnahme von Collatz 'Vorhersage zu finden. Sie können selbst versuchen, einige Beispiele mit einem der vielen im Internet verfügbaren „ Collatz-Rechner “ auszuprobieren. Das Internet ist voll von ungerechtfertigten Amateur-Beweisen für eine Hypothese, deren Autoren behaupten, sie hätten sie beweisen oder widerlegen können.



„Man muss nur in der Lage sein, mit 3 zu multiplizieren und durch 2 zu dividieren, und schon kann man damit spielen. Und es ist sehr verlockend ", sagte Mark Chamberlain , ein Mathematiker am Grinnel College, der ein beliebtes YouTube-Video zu diesem Problem mit dem Titel" Die einfachsten der unmöglichen Probleme "aufzeichnete.


Es gibt jedoch kaum echte Beweise.

In den 1970er Jahren haben Mathematiker gezeigt, dass fast alle Collatz-Sequenzen - eine Liste von Zahlen, die Sie erhalten, wenn Sie den Vorgang wiederholen - letztendlich zu einer Zahl führen, die kleiner als die ursprüngliche ist. Dies war ein schwacher Beweis dafür, dass fast alle Collatz-Sequenzen zu 1 führen, aber es war trotzdem so. Und von 1994 bis zum Tao-Ergebnis im Jahr 2019 hielt Ivan Korets den Rekord für den Nachweis des Mindestwerts. Andere Arbeiten versuchten auf ähnliche Weise, die Aufgabe anzugreifen und näherten sich nicht ihrem Hauptziel.

"Wir verstehen die Collatz-Frage nicht gut genug, daher wurde an diesem Thema nicht nennenswert gearbeitet", sagte Kannan Saundararajan , ein Mathematiker an der Stanford University, der an dieser Hypothese arbeitete.

Die Sinnlosigkeit dieser Versuche führte viele Mathematiker zu der Schlussfolgerung, dass diese Hypothese beim gegenwärtigen Wissensstand einfach nicht verfügbar ist und dass es für sie besser ist, ihre Zeit für andere Studien zu verwenden.

"Das Collatz-Problem ist für seine Komplexität bekannt - so sehr, dass Mathematiker in der Regel vor jeder Diskussion gewarnt werden, keine Zeit darauf zu verschwenden", sagte Joshua Cooper von der University of South Carolina.

Unerwarteter Rat

Zum ersten Mal interessierte sich Lagarias vor mindestens 40 Jahren als Student für diese Hypothese. Jahrzehntelang war er inoffizielle Kuratorin für alles, was mit ihr zu tun hatte. Er sammelte eine ganze Bibliothek von Werken, die mit ihr zu tun hatten, und veröffentlichte 2010 einige davon in Form eines Buches mit dem Titel: "The Decisive Challenge: Problem 3x +1 ".

"Jetzt weiß ich viel mehr über dieses Problem, und ich kann immer noch sagen, dass es unmöglich ist, es zu lösen", sagte Lagarias.

Tao verbringt seine Zeit normalerweise nicht mit unmöglichen Aufgaben. 2006 erhielt er den Fields-Preis , die höchste Auszeichnung in der Mathematik, und gilt als einer der besten Mathematiker seiner Generation. Er ist es gewohnt, Probleme zu lösen und keine Luftschlösser zu jagen.

"Dies sind die Risiken, die mit dem Beruf der Mathematiker verbunden sind", sagte er. "Sie können von einer der großen bekannten Aufgaben besessen sein, die über die Fähigkeiten einer Person hinausgehen und viel Zeit verlieren."

Es gelingt dem Tao jedoch nicht immer, Versuchungen aus diesem Bereich zu widerstehen. Jedes Jahr widmet er sich ein oder zwei Tagen den berühmtesten ungelösten Problemen der Mathematik. Im Laufe der Jahre verfolgte er mehrere Ansätze zur Collatz-Hypothese, jedoch ohne Erfolg.

Im August hinterließ ein anonymer Leser einen Kommentar in Taos Blog. Er schlug vor, die Collatz-Hypothese „für fast alle“ Zahlen zu lösen, ohne sie vollständig zu beweisen.

"Ich antwortete nicht, aber es brachte mich dazu, wieder über diese Aufgabe nachzudenken", sagte Tao.

Und er erkannte, dass die Hypothese von Collatz in gewisser Weise mit speziellen Arten von Gleichungen - partiellen Differentialgleichungen - vergleichbar war, die in den bedeutendsten Ergebnissen auftauchten, die er während seiner Karriere erzielt hatte.

Ein- und Ausgänge

Partielle Differentialgleichungen (PDEs) können verwendet werden, um viele der grundlegendsten physikalischen Prozesse im Universum zu modellieren, z. B. die Entwicklung von Flüssigkeiten oder den Durchgang von Gravitationswellen durch die Raum-Zeit. Sie treten in Situationen auf, in denen die zukünftige Position des Systems - beispielsweise der Zustand des Teichs fünf Sekunden nach dem Werfen eines Steins - von zwei oder mehr Faktoren abhängt, z. B. Viskosität und Wassergeschwindigkeit.

Es scheint, dass komplexe PDEs mit einer so einfachen Rechenaufgabe wie der Collatz-Hypothese wenig zu tun haben.

Aber Tao erkannte, dass sie etwas gemeinsam hatten. Es ist möglich, Werte in der PDE zu ersetzen, andere Werte abzurufen, den Vorgang zu wiederholen - und das alles, um den zukünftigen Zustand des Systems zu verstehen. Für jedes gegebene LDPE müssen Mathematiker wissen, ob die Anfangswerte am Eingang zu unendlichen Werten am Ausgang führen oder ob die Gleichungen unabhängig von den Anfangswerten immer endgültige Werte ergeben.


Terence Tao, inspiriert durch den Kommentar in seinem Blog, hat den größten Fortschritt seit Jahrzehnten bei der Untersuchung der Collatz-Hypothese erzielt

Für Tao lag dieses Ziel in der gleichen Größenordnung wie die Frage, ob Sie vom Collatz-Prozess unabhängig vom Anfangswert immer den gleichen Wert (1) erhalten. Infolgedessen erkannte er, dass Techniken zur Untersuchung von PDEs zur Untersuchung der Collatz-Hypothese geeignet sein könnten.

Eine besonders nützliche Technik verwendet eine statistische Methode, um das Langzeitverhalten einer kleinen Anzahl von Anfangswerten (etwa einer kleinen Anzahl von Anfangswasserkonfigurationen in einem Teich) zu untersuchen und das Ergebnis auf das Langzeitverhalten aller möglichen Anfangskonfigurationen des Teichs zu extrapolieren.

Stellen Sie sich im Zusammenhang mit der Collatz-Hypothese vor, wir hätten mit einer großen Stichprobe von Zahlen begonnen. Unser Ziel ist es zu untersuchen, wie sich diese Zahlen verhalten, wenn wir den Collatz-Prozess auf sie anwenden. Wenn fast 100% der Zahlen in der Stichprobe auf 1 oder sehr nahe an 1 kommen, können wir schließen, dass sich fast alle Zahlen gleich verhalten.

Damit diese Schlussfolgerung jedoch gerechtfertigt ist, muss die Stichprobe sorgfältig ausgewählt werden. Diese Aufgabe ähnelt der Zusammenstellung einer Stichprobe von Wählern bei den US-Präsidentschaftswahlen. Für eine sorgfältige Stichprobe der gesamten Bevölkerung sollten gewichtete Anteile für Republikaner und Demokraten, Männer und Frauen usw. verwendet werden.

Zahlen haben ihre eigenen "demografischen" Parameter. Gerade und ungerade Zahlen, durch 3 teilbare Zahlen und Zahlen, die sich auf noch schwierigere Weise voneinander unterscheiden. Durch das Erstellen einer Auswahl von Zahlen können Sie sicherstellen, dass bestimmte Arten von Zahlen nach einem ausgewogenen Prinzip eingegeben werden und andere nicht. Je besser Sie die Gewichte auswählen, desto genauer sind Ihre Schlussfolgerungen über alle Zahlen im Allgemeinen.

Gewichtete Wahl

Taos Aufgabe war viel komplizierter, als nur zu verstehen, wie man eine erste Auswahl von Zahlen mit den richtigen Gewichten erstellt. Bei jedem Schritt des Collatz-Prozesses ändern sich die Zahlen, mit denen Sie arbeiten. Eine offensichtliche Änderung ist, dass fast alle Zahlen in der Stichprobe abnehmen.

Eine andere, vielleicht weniger offensichtliche Veränderung besteht darin, dass sich die Zahlen möglicherweise in Gruppen ansammeln. Sie können beispielsweise mit einer schönen einheitlichen Zahlenverteilung von eins bis eine Million beginnen. Nach fünf Iterationen konzentrieren sich die Zahlen wahrscheinlich auf mehrere kleine Intervalle der Zahlenreihe. Mit anderen Worten, Sie können mit einem guten Sample beginnen, das in fünf Schritten hoffnungslos verzerrt wird.

"Normalerweise kann man davon ausgehen, dass sich die Verteilung nach der Iteration vollständig von der ursprünglichen unterscheidet", sagte Tao. Seine Schlüsselidee war es jedoch, ein Muster von Zahlen zu erstellen, das im Collatz-Prozess größtenteils seine ursprünglichen Gewichte beibehält.

Zum Beispiel wird das erste Beispiel von Tao so gewichtet, dass es keine durch drei teilbaren Zahlen hat, da der Collatz-Prozess solche Zahlen immer noch ziemlich schnell eliminiert. Einige andere von Tao gewählte Gewichte sind schwieriger. Er bevorzugt Zahlen, bei denen der Rest durch 3 gleich 1 ist, und weicht von Zahlen ab, bei denen der Rest durch 3 gleich 2 ist.

Dadurch behält die Probe, mit der Tao beginnt, auch nach dem Start des Collatz-Prozesses ihren Charakter.

"Er hat einen Weg gefunden, diesen Prozess fortzusetzen, so dass nach ein paar Schritten immer noch klar ist, was passiert", sagte Saundararajan. "Als ich diese Arbeit zum ersten Mal sah, war ich sehr glücklich und entschied, dass es erstaunlich war."

Tao verwendete seine Gewichtszuweisungstechnik, um zu beweisen, dass fast alle Anfangswerte - mindestens 99% - letztendlich einen Wert nahe 1 erreichten. Dies ließ ihn den Schluss zu, dass 99% der Anfangswerte größer als eine Billiarde sind Infolgedessen werden Werte von weniger als 200 erreicht.

Dies ist wohl das stärkste Ergebnis in der langen Geschichte dieser Hypothese.

"Dies ist ein großer Durchbruch in unserem Wissen darüber, was mit dieser Aufgabe geschieht", sagte Lagarias. "Dies ist definitiv das beste Ergebnis seit langem."

Die Tao-Methode ist mit ziemlicher Sicherheit nicht in der Lage, den vollständigen Beweis der Collatz-Hypothese zu erbringen. Der Grund ist, dass seine anfängliche Auswahl nach jedem Schritt immer noch ein wenig verzerrt ist. Die Verzerrung ist minimal, während die Stichprobe noch viele verschiedene Werte enthält, die weit von 1 entfernt sind. Im Collatz-Verfahren tendieren jedoch alle Zahlen in der Stichprobe zu eins, und eine kleine Verzerrung wird größer - genau wie ein kleiner Fehler bei der Berechnung des Abstimmungsergebnisses Ein großer Wert bei einer großen Stichprobe, der sich jedoch stark auf das Ergebnis auswirkt, wenn die Stichprobe klein ist.

Alle Beweise für eine vollständige Hypothese werden höchstwahrscheinlich auf einem anderen Ansatz beruhen. Infolgedessen ist Taos Arbeit sowohl ein Triumph als auch eine Warnung für alle Interessierten: Sobald Sie den Eindruck haben, dass Sie die Aufgabe in die Enge getrieben haben, entgeht sie Ihnen.

"Man kann der Collatz-Hypothese willkürlich nahe kommen, aber sie bleibt immer noch unerreichbar", sagte Tao.