06/01/2021
Die Collatz-Vermutung, auch bekannt als das 3n+1-Problem, ist eines der faszinierendsten und zugleich frustrierendsten ungelösten Probleme in der Mathematik. Ihre Einfachheit steht in starkem Kontrast zu ihrer hartnäckigen Unzugänglichkeit für einen Beweis. In diesem Artikel tauchen wir in die Welt der Collatz-Vermutung ein, erkunden ihre Ursprünge, Prinzipien, Teillösungen und verschiedene Perspektiven, um ein umfassendes Verständnis dieses mathematischen Rätsels zu vermitteln.
Ursprung und Geschichte der Collatz-Vermutung
Die Wurzeln der Collatz-Vermutung reichen bis ins Jahr 1937 zurück, als der deutsche Mathematiker Lothar Collatz sie erstmals formulierte. Obwohl sie nach ihm benannt ist, wurde sie im Laufe der Zeit auch unter verschiedenen anderen Namen bekannt, darunter das 3n+1-Problem, das Syracuse-Problem (benannt nach der Syracuse University) und das Hagelzahlen-Problem (aufgrund des Auf- und Absteigens der Zahlen in den Sequenzen). Collatz selbst hat seine ursprünglichen Ideen wohl nicht sofort veröffentlicht, da er nicht beweisen konnte, dass der beobachtete „triviale Kreis“ der einzige mögliche Zyklus ist.
Der Collatz-Graph zur Veranschaulichung
Um die Natur der Collatz-Vermutung besser zu verstehen, führte Collatz das Konzept des Collatz-Graphen ein. Ein Collatz-Graph ist ein gerichteter Graph, bei dem jede natürliche Zahl ein Knoten ist. Für jede Zahl n gibt es eine gerichtete Kante von n zu f(n), wobei f(n) die Collatz-Funktion ist. Diese Funktion ist wie folgt definiert:
C(n) = { n/2 wenn n gerade ist, 3n+1 wenn n ungerade ist }
Collatz experimentierte mit verschiedenen Funktionen, um Collatz-Graphen mit Kreisen zu finden. Er stellte fest, dass die Funktion C1(n), definiert als:
C1(n) = { n/2 wenn n gerade ist, n+1 wenn n ungerade ist }
einen Collatz-Graphen erzeugt, der nur den Kreis (1, 2) enthält. Im Gegensatz dazu erzeugte die Funktion C2(n), definiert als:
C2(n) = { n/2 wenn n gerade ist, 2n+1 wenn n ungerade ist }
einen Graphen ohne Kreise, bei dem alle Trajektorien gegen unendlich divergieren. Schließlich stieß er auf die heute berühmte Collatz-Funktion C(n) und beobachtete, dass sie scheinbar immer zum trivialen Kreis (1, 4, 2) führt. Dies führte zur Formulierung der Collatz-Vermutung.
Das Prinzip der Collatz-Vermutung
Die Collatz-Vermutung besagt, dass, egal mit welcher positiven ganzen Zahl man beginnt, die wiederholte Anwendung der Collatz-Funktion immer zur Zahl 1 führt. Anders ausgedrückt, jede Collatz-Folge mündet schließlich im Zyklus (1, 4, 2). Es gibt drei mögliche Szenarien für eine Collatz-Folge:
- Die Folge endet im (1, 4, 2)-Zyklus.
- Die Folge gerät in einen anderen Zyklus.
- Die Folge wächst unbegrenzt über alle Grenzen hinaus.
Die Collatz-Vermutung postuliert, dass nur das erste Szenario für alle Startzahlen zutrifft. Bisher konnte weder das Auftreten des zweiten noch des dritten Szenarios für eine bestimmte Folge ausgeschlossen werden. Es ist auch nicht bewiesen, dass es nur endlich viele Zyklen geben kann.
Die T-Funktion als Vereinfachung
In der Praxis wird oft eine etwas vereinfachte Funktion, die T-Funktion, anstelle der ursprünglichen Collatz-Funktion verwendet. Die T-Funktion ist definiert als:
T(n) = { n/2 wenn n gerade ist, (3n+1)/2 wenn n ungerade ist }
Die T-Funktion führt für ungerade Zahlen zwei Iterationen der C-Funktion in einem Schritt aus und reduziert den Zyklus (1, 4, 2) auf (1, 2). Die Collatz-Vermutung ist äquivalent zu der Aussage, dass für alle ganzen Zahlen n > 1 eine ganze Zahl k > 0 existiert, so dass Tk(n) < n ist. Dies bedeutet, dass jede Folge letztendlich abnehmen muss.
Computerberechnungen haben die Collatz-Vermutung für alle Startwerte bis zu 268 bestätigt (Stand Juli 2020). Diese enormen Berechnungen liefern zwar starke empirische Evidenz, stellen aber keinen mathematischen Beweis dar.
Die Teillösung von Terence Tao
Im Jahr 2019 erzielte der Mathematiker Terence Tao einen bedeutenden Fortschritt in Bezug auf die Collatz-Vermutung. Er bewies, dass die Collatz-Vermutung für „fast alle“ natürlichen Zahlen „fast“ zutrifft. Genauer gesagt, bewies Tao den folgenden Satz:
Sei f: N+1 → R eine Funktion mit limN→∞ f(N) = +∞. Dann gilt ColminN(N) < f(N) für fast alle N ∈ N+1.
Hierbei bezeichnet ColminN(N) das Minimum der Collatz-Folge, die mit N beginnt. Taos Ergebnis bedeutet, dass für die überwiegende Mehrheit der Zahlen die Collatz-Folge irgendwann sehr kleine Werte erreicht, obwohl er nicht beweisen konnte, dass sie immer 1 erreicht. Beispielsweise folgt aus Taos Satz, dass mindestens 99 Prozent der natürlichen Zahlen bis 1024, mit denen man die Collatzfolge startet, einen Endwert erreichen, der unter 200 liegt.
Tao verwendete Methoden aus der Theorie partieller Differentialgleichungen, um dieses Ergebnis zu erzielen. Er untersuchte statistisch eine Auswahl von Anfangswerten und analysierte dann das „Langzeitverhalten“ des Ensembles unter der Collatz-Transformation.
Darstellung im Dualsystem
Das Dualsystem bietet eine interessante Perspektive auf die Collatz-Funktion. Im Dualsystem ist es einfach zu erkennen, ob eine Zahl gerade oder ungerade ist: Gerade Zahlen enden mit 0, ungerade mit 1. Auch die Multiplikation mit 2 (Hinzufügen einer 0 rechts) und die Division durch 2 (Entfernen einer 0 rechts) sind einfache Operationen.
Die Collatz-Funktion kann im Dualsystem als eine abstrakte Maschine interpretiert werden, die Bitfolgen manipuliert. Die Verarbeitung einer ungeraden Zahl n im Dualsystem erfolgt in drei Schritten:
- Füge rechts eine 1 an die Binärzahl an (entspricht 2n + 1).
- Addiere das Ergebnis aus Schritt 1 zur ursprünglichen Zahl (entspricht n + (2n + 1) = 3n + 1).
- Entferne alle Nullen am rechten Rand der neuen Zahl (entspricht Divisionen durch 2).
Obwohl diese Regeln im Dualsystem sehr einfach sind, hat auch diese Darstellung bisher nicht zu einem Beweis der Collatz-Vermutung geführt.
Verallgemeinerungen der Collatz-Vermutung
Die Collatz-Vermutung wurde in verschiedene Richtungen verallgemeinert. Eine Verallgemeinerung betrachtet das Problem für alle ganzen Zahlen (nicht nur positive). In diesem Fall gibt es neben dem (1, 4, 2)-Zyklus noch weitere bekannte Zyklen, darunter (0), (-1, -2), (-5, -14, -7, -20, -10) und (-17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34). Es wird vermutet, dass alle Startwerte mit |n| < 108 in einem dieser bekannten Zyklen enden.
Eine andere Verallgemeinerung betrachtet Funktionen der Form C(n) = 3n + 3x für ungerade n. Es wird vermutet, dass diese Funktionen immer im Zyklus (4⋅3x, 2⋅3x, 1⋅3x) enden und nur diesen einen Zyklus besitzen.
Im Gegensatz dazu zeigen stochastische Modelle für das analoge (5n+1)-Problem ein ganz anderes Verhalten: Fast alle Iterierten sollten divergieren. Computersimulationen bestätigen dies, aber ein Beweis, dass auch nur ein Orbit des (5n+1)-Problems tatsächlich divergiert, steht noch aus.
Ist das Collatz-Problem gelöst?
Die kurze Antwort lautet: Nein, das Collatz-Problem ist noch nicht gelöst. Obwohl Terence Tao einen bedeutenden Teilerfolg erzielt hat und Computerberechnungen die Vermutung für enorme Zahlenbereiche bestätigen, fehlt weiterhin ein vollständiger mathematischer Beweis für alle natürlichen Zahlen. Die Collatz-Vermutung bleibt eines der großen ungelösten Rätsel der Mathematik und spornt weiterhin Mathematiker weltweit zu neuen Forschungsansätzen und Methoden an. Es ist möglich, dass zur Lösung dieses Problems völlig neue mathematische Werkzeuge und Perspektiven entwickelt werden müssen.
Ist 3x + 1 gelöst?
Die Frage „Ist 3x + 1 gelöst?“ bezieht sich direkt auf die Collatz-Vermutung, da 3x + 1 der Kern der Definition der Funktion für ungerade Zahlen ist. Wie bereits erwähnt, ist die Antwort weiterhin nein. Trotz der Einfachheit der 3x+1-Regel und der umfangreichen empirischen Evidenz bleibt die Frage, ob alle Folgen unweigerlich zu 1 führen, unbeantwortet. Die Beharrlichkeit dieses Problems unterstreicht die Tiefe und Komplexität, die in scheinbar einfachen mathematischen Fragestellungen verborgen liegen können.
Was ist ein Collatz-Graph?
Zusammenfassend lässt sich sagen, dass ein Collatz-Graph eine grafische Darstellung der Collatz-Funktion ist. Er besteht aus natürlichen Zahlen als Knoten und gerichteten Kanten, die von jeder Zahl n zu ihrem Wert unter der Collatz-Funktion C(n) führen. Der Collatz-Graph dient dazu, das Verhalten der Collatz-Folgen visuell zu untersuchen und mögliche Muster oder Zyklen zu erkennen. Die Vermutung, dass der Collatz-Graph von C zusammenhängend ist, ist eine graphentheoretische Formulierung der Collatz-Vermutung selbst.
Das Collatz-Problem bleibt eine Herausforderung und eine Quelle der Inspiration für Mathematiker. Seine Einfachheit und Tiefe machen es zu einem faszinierenden Beispiel für die ungelösten Geheimnisse, die die Welt der Zahlen bereithält.