Erfahrene Mathematiker warnen Nachwuchskräfte, sich von der Collatz-Vermutung fernzuhalten. Es ist ein Sirenenlied, sagen sie: Fallen Sie in Trance und Sie werden vielleicht nie wieder sinnvolle Arbeit leisten.
Die Collatz-Vermutung ist wahrscheinlich das einfachste ungelöste Problem in der Mathematik - und genau das macht sie so verführerisch.
Nachdruck der Originalgeschichte mit Genehmigung des Quanta Magazine, einer redaktionell unabhängigen Veröffentlichung der Simons Foundation, deren Aufgabe es ist, das Verständnis der Öffentlichkeit für die Wissenschaft zu verbessern, indem Forschungsentwicklungen und -trends in den Bereichen Mathematik, Physik und Biowissenschaften behandelt werden.
„Das ist ein wirklich gefährliches Problem. Die Leute sind davon besessen und es ist wirklich unmöglich “, sagte Jeffrey Lagarias, Mathematiker an der Universität von Michigan und Experte für die Collatz-Vermutung.
Anfang dieses Jahres wagte einer der führenden Mathematiker der Welt, sich dem Problem zu stellen - und erzielte eines der bedeutendsten Ergebnisse der Collatz-Vermutung seit Jahrzehnten.
Am 8. September veröffentlichte Terence Tao einen Beweis dafür, dass die Collatz-Vermutung zumindest für „fast“alle Zahlen „fast“gilt. Das Ergebnis von Tao ist zwar kein vollständiger Beweis für die Vermutung, aber es ist ein großer Fortschritt in Bezug auf ein Problem, das seine Geheimnisse nicht so leicht preisgibt.
"Ich hatte nicht erwartet, dieses Problem vollständig zu lösen", sagte Tao, ein Mathematiker an der University of California in Los Angeles. "Aber was ich getan habe, war mehr als ich erwartet hatte."
Das Collatz-Rätsel
Lothar Collatz hat wahrscheinlich die gleichnamige Vermutung in den 1930er Jahren aufgestellt. Das Problem klingt nach einem Partytrick. Wähle eine Zahl, eine beliebige Zahl. Wenn es ungerade ist, multiplizieren Sie es mit 3 und addieren Sie 1. Wenn es gerade ist, dividieren Sie es durch 2. Jetzt haben Sie eine neue Zahl. Wenden Sie die gleichen Regeln auf die neue Nummer an. Die Vermutung handelt davon, was passiert, wenn Sie den Vorgang wiederholen.
Die Intuition könnte darauf hindeuten, dass die Zahl, mit der Sie beginnen, die Zahl beeinflusst, mit der Sie enden. Vielleicht drehen sich einige Zahlen bis auf 1 herunter. Vielleicht marschieren andere bis ins Unendliche.
Aber Collatz sagte voraus, dass dies nicht der Fall ist. Er vermutete, dass, wenn Sie mit einer positiven ganzen Zahl beginnen und diesen Prozess lange genug ausführen, alle Startwerte zu 1 führen. Und wenn Sie 1 treffen, beschränken Sie sich nach den Regeln der Collatz-Vermutung auf eine Schleife: 1, 4, 2, 1, 4, 2, 1, für immer und ewig.
Im Laufe der Jahre haben sich viele Problemlöser für die verführerische Einfachheit der Collatz-Vermutung oder das sogenannte „3x + 1-Problem“interessiert. Mathematiker haben Billionen von Beispielen (das sind 18 Nullen) getestet, ohne eine einzige Ausnahme von Collatz 'Vorhersage zu finden. Sie können sogar selbst einige Beispiele mit einem der vielen „Collatz-Rechner“online ausprobieren. Das Internet steckt voller unbegründeter Beweise von Amateuren, die behaupten, das Problem auf die eine oder andere Weise gelöst zu haben.
„Man muss nur wissen, wie man mit 3 multipliziert und mit 2 dividiert, und schon kann man damit herumspielen. Es ist sehr verlockend, es zu versuchen “, sagte Marc Chamberland, ein Mathematiker am Grinnell College, der ein beliebtes YouTube-Video zum Problem mit dem Titel„ Das einfachste unmögliche Problem “produzierte.
Aber legitime Beweise sind selten.
In den 1970er Jahren haben Mathematiker gezeigt, dass fast alle Collatz-Sequenzen - die Liste der Zahlen, die Sie erhalten, wenn Sie den Vorgang wiederholen - schließlich eine Zahl erreichen, die kleiner ist als an der Stelle, an der Sie begonnen haben Von 1994 bis zu Taos Ergebnis in diesem Jahr hielt Ivan Korec den Rekord, um zu zeigen, wie viel kleiner diese Zahlen werden. Andere Ergebnisse haben sich in ähnlicher Weise mit dem Problem befasst, ohne sich dem Kernproblem zu nähern.
"Wir verstehen die Collatz-Frage überhaupt nicht so gut, daher wurde nicht viel daran gearbeitet", sagte Kannan Soundararajan, ein Mathematiker an der Stanford University, der an der Vermutung gearbeitet hat.
Die Sinnlosigkeit dieser Bemühungen hat viele Mathematiker zu dem Schluss gebracht, dass die Vermutung einfach außerhalb der Reichweite des gegenwärtigen Verständnisses liegt - und dass sie besser dran sind, ihre Forschungszeit woanders zu verbringen.
"Collatz ist ein notorisch schwieriges Problem - so sehr, dass Mathematiker dazu neigen, jeder Diskussion eine Warnung voranzustellen, keine Zeit damit zu verschwenden", sagte Joshua Cooper von der University of South Carolina in einer E-Mail.
Ein unerwarteter Tipp
Lagarias war vor mindestens 40 Jahren von der Vermutung als Student fasziniert. Seit Jahrzehnten ist er der inoffizielle Kurator aller Dinge Collatz. Er hat eine Bibliothek mit Artikeln zusammengestellt, die mit dem Problem zu tun haben, und 2010 hat er einige davon als Buch mit dem Titel The Ultimate Challenge: The 3x + 1 Problem veröffentlicht.
"Jetzt weiß ich viel mehr über das Problem und ich würde sagen, es ist immer noch unmöglich", sagte Lagarias.
Tao verbringt normalerweise keine Zeit mit unmöglichen Problemen. 2006 gewann er die Fields-Medaille, die höchste Auszeichnung für Mathematik, und gilt als einer der besten Mathematiker seiner Generation. Er ist es gewohnt, Probleme zu lösen, nicht Pfeifenträume zu verfolgen.
"Es ist eigentlich eine berufliche Gefahr, wenn Sie ein Mathematiker sind", sagte er. "Sie könnten von diesen großen, berühmten Problemen besessen sein, die weit über die Möglichkeiten eines jeden hinausgehen und Sie können viel Zeit verschwenden."
Aber Tao widersteht den großen Versuchungen seines Fachs nicht ganz. Jedes Jahr versucht er sein Glück für ein oder zwei Tage an einem der berühmten ungelösten Probleme der Mathematik. Im Laufe der Jahre unternahm er einige Versuche, die Collatz-Vermutung zu lösen, ohne Erfolg.
Dann hat im vergangenen August ein anonymer Leser einen Kommentar in Taos Blog hinterlassen. Der Kommentator schlug vor, die Collatz-Vermutung für „fast alle“Zahlen zu lösen, anstatt zu versuchen, sie vollständig zu lösen.
"Ich habe nicht geantwortet, aber ich habe wieder über das Problem nachgedacht", sagte Tao.
Und er erkannte, dass die Collatz-Vermutung in gewisser Weise den Arten von Gleichungen - partielle Differentialgleichungen genannt - ähnlich war, die in einigen der bedeutendsten Ergebnisse seiner Karriere vorkamen.
Eingänge und Ausgänge
Partielle Differentialgleichungen oder PDEs können verwendet werden, um viele der grundlegendsten physikalischen Prozesse im Universum zu modellieren, wie die Entwicklung einer Flüssigkeit oder die Schwerkraftwelligkeit durch Raum-Zeit. Sie entstehen in Situationen, in denen die zukünftige Position eines Systems - wie der Zustand eines Teichs fünf Sekunden nachdem Sie einen Stein hineingeworfen haben - von zwei oder mehr Faktoren abhängt, wie der Viskosität und Geschwindigkeit des Wassers.
Komplizierte PDEs scheinen nicht viel mit einer einfachen arithmetischen Frage wie der Collatz-Vermutung zu tun zu haben.
Aber Tao erkannte, dass an ihnen etwas Ähnliches war. Mit einer PDE schließen Sie einige Werte an, holen andere Werte heraus und wiederholen den Vorgang - alles, um den zukünftigen Zustand des Systems zu verstehen. Für eine bestimmte PDE möchten Mathematiker wissen, ob einige Startwerte letztendlich zu unendlichen Werten als Ausgabe führen oder ob eine Gleichung unabhängig von den Werten, mit denen Sie beginnen, immer endliche Werte liefert.
Für Tao hatte dieses Ziel den gleichen Reiz wie die Untersuchung, ob Sie immer die gleiche Zahl (1) aus dem Collatz-Prozess erhalten, unabhängig davon, welche Zahl Sie eingeben. Infolgedessen erkannte er, dass Techniken zum Studium von PDEs für den Collatz gelten könnten Vermutung.
Eine besonders nützliche Technik besteht darin, das Langzeitverhalten einer kleinen Anzahl von Startwerten (wie eine kleine Anzahl von Anfangskonfigurationen des Wassers in einem Teich) statistisch zu untersuchen und von dort auf das Langzeitverhalten aller möglichen zu extrapolieren Startkonfigurationen des Teiches.
Stellen Sie sich vor, Sie beginnen im Kontext der Collatz-Vermutung mit einer großen Stichprobe von Zahlen. Ihr Ziel ist es, das Verhalten dieser Zahlen bei der Anwendung des Collatz-Prozesses zu untersuchen. Wenn nahezu 100% der Zahlen in der Stichprobe genau bei 1 oder sehr nahe bei 1 landen, können Sie den Schluss ziehen, dass sich fast alle Zahlen gleich verhalten.
Damit die Schlussfolgerung gültig ist, müssen Sie Ihre Stichprobe sehr sorgfältig erstellen. Die Herausforderung besteht darin, eine Stichprobe von Wählern in einer Präsidentschaftswahl zu erstellen. Um die Umfrage genau auf die Gesamtbevölkerung hochzurechnen, müsste die Stichprobe mit dem richtigen Verhältnis von Republikanern und Demokraten, Frauen und Männern usw. gewichtet werden.
Zahlen haben ihre eigenen „demografischen“Merkmale. Es gibt natürlich ungerade und gerade Zahlen und Zahlen, die ein Vielfaches von 3 sind, und Zahlen, die sich auf subtilere Weise voneinander unterscheiden. Wenn Sie eine Stichprobe von Zahlen erstellen, können Sie sie so gewichten, dass sie bestimmte Arten von Zahlen und nicht andere enthält - und je besser Sie Ihre Gewichte auswählen, desto genauer können Sie Rückschlüsse auf Zahlen als Ganzes ziehen.
Gewichtige Entscheidungen
Taos Herausforderung war viel schwieriger, als nur herauszufinden, wie man eine erste Stichprobe von Zahlen mit den richtigen Gewichten erstellt. Bei jedem Schritt im Collatz-Prozess ändern sich die Zahlen, mit denen Sie arbeiten. Eine offensichtliche Änderung ist, dass fast alle Zahlen in der Stichprobe kleiner werden.
Eine andere, vielleicht weniger offensichtliche Änderung ist, dass die Zahlen sich zu verklumpen beginnen. Sie könnten beispielsweise mit einer schönen, einheitlichen Verteilung wie den Zahlen von 1 bis 1 Million beginnen. Aber fünf Collatz-Iterationen später konzentrieren sich die Zahlen wahrscheinlich in kleinen Intervallen auf die Zahlenreihe. Mit anderen Worten, Sie können mit einem guten Beispiel beginnen, aber fünf Schritte später ist es hoffnungslos schief.
"Normalerweise würde man erwarten, dass sich die Verteilung nach der Iteration völlig von der unterscheidet, mit der Sie begonnen haben", sagte Tao in einer E-Mail.
Taos wichtigste Erkenntnis bestand darin, herauszufinden, wie man eine Stichprobe von Zahlen auswählt, die während des gesamten Collatz-Prozesses ihre ursprünglichen Gewichte weitgehend beibehält.
Zum Beispiel wird Taos Ausgangsprobe so gewichtet, dass sie kein Vielfaches von 3 enthält, da der Collatz-Prozess sowieso schnell ein Vielfaches von 3 aussortiert. Einige der anderen Gewichte, die Tao sich ausgedacht hat, sind komplizierter. Er gewichtet seine Ausgangsstichprobe nach Zahlen, die einen Rest von 1 haben, nachdem sie durch 3 geteilt wurden, und nach Zahlen, die einen Rest von 2 haben, nachdem sie durch 3 geteilt wurden.
Das Ergebnis ist, dass das Beispiel, mit dem Tao beginnt, seinen Charakter beibehält, selbst wenn der Collatz-Prozess fortschreitet.
"Er hat einen Weg gefunden, diesen Prozess fortzusetzen, so dass Sie nach einigen Schritten immer noch wissen, was los ist", sagte Soundararajan. "Als ich das Papier zum ersten Mal sah, war ich sehr aufgeregt und fand es sehr auffällig."
Tao verwendete diese Gewichtungstechnik, um zu beweisen, dass fast alle Collatz-Ausgangswerte - 99 Prozent oder mehr - irgendwann einen Wert erreichen, der ziemlich nahe bei 1 liegt. Auf diese Weise konnte er Rückschlüsse auf 99 Prozent der Ausgangswerte ziehen, die schließlich größer als 1 Billiarde waren einen Wert unter 200 erreichen.
Es ist wohl das stärkste Ergebnis in der langen Geschichte der Vermutung.
"Es ist ein großer Fortschritt in unserem Wissen darüber, was bei diesem Problem passiert", sagte Lagarias. "Es ist mit Sicherheit das beste Ergebnis seit langem."
Mit ziemlicher Sicherheit ist Taos Methode nicht in der Lage, einen vollständigen Beweis für die Collatz-Vermutung zu liefern. Der Grund dafür ist, dass sein Startmuster nach jedem Schritt des Prozesses immer noch ein wenig schief läuft. Der Schräglauf ist minimal, solange das Sample noch viele verschiedene Werte enthält, die weit von 1 entfernt sind. Wenn der Collatz-Prozess jedoch fortgesetzt wird und die Zahlen im Sample näher an 1 rücken, wird der kleine Schräglaufeffekt immer deutlicher - auf dieselbe Weise dass eine geringfügige Fehleinschätzung in einer Umfrage bei einem großen Stichprobenumfang keine große Rolle spielt, bei einem kleinen Stichprobenumfang jedoch einen übergroßen Effekt hat.
Jeder Beweis der vollständigen Vermutung würde wahrscheinlich von einem anderen Ansatz abhängen. Infolgedessen ist Taos Arbeit sowohl ein Triumph als auch eine Warnung an den neugierigen Collatz: Gerade wenn Sie glauben, das Problem in die Enge getrieben zu haben, rutscht es weg.
