Das Collatz-Problem, auch als (3n+1)-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde. Es hat Verbindungen zur Zahlentheorie, zur Theorie dynamischer Systeme und Ergodentheorie und zur Berechenbarkeitstheorie in der Informatik.
Das Problem ist zwar einfach zu formulieren, aber notorisch schwierig. Jeffrey Lagarias, der als Experte für das Problem gilt, zitiert eine mündliche Mitteilung von Paul Erdős, der es als „absolut hoffnungslos“ bezeichnete.Jeffrey Lagarias: The 3x+1 problem: An overview, www.arxiv.org, 2021, S. 14 „Mathematics is not yet ready for such problems.“ und S. 23 „Hopeless. Absolutely hopeless.“ (englisch)
Problemstellung Einleitung mini|400px|Säulendiagramm. Häufigkeit für Längen von Collatz-Folgen. Im Diagramm ist der Beitrag zur Häufigkeit nach Startwert eingefärbt
Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden: Beginne mit einer beliebigen natürlichen Zahl . Ist gerade, so nimm als nächstes . Ist ungerade, so nimm als nächstes . Wiederhole die Vorgehensweise mit der erhaltenen Zahl. Zum Beispiel ergibt sich mit der Startzahl die Folge 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, … Die Folge tritt somit in einen Zyklus ein, in dem die Zahlen 4, 2, 1 ständig wiederholt werden.
Die Collatz-Vermutung lautet nun: Die Zahlenfolge mündet immer in den Zyklus 4, 2, 1, egal, mit welcher positiven natürlichen Zahl man beginnt. Diese Vermutung wurde bislang weder bewiesen noch widerlegt.
Mathematische Formulierung der Vermutung Formulierung der Vermutung mit Hilfe des Bildungsgesetzes Bezeichne mit die natürlichen Zahlen ohne die Null. die natürlichen Zahlen mit der Null.
Sei und die Collatz-Funktion
Definiere den Collatz-Orbit
Dann lautet die Vermutung:
Zu jedem existiert ein , so dass .
Erläuterungen Für den Orbit gilt somit , usw.
Um die Vermutung zu beweisen, muss man für jedes zeigen, dass ein solches existiert. Um die Vermutung zu widerlegen, muss man ein finden, für das ein solches nicht existiert.
Eine gleichwertige Aussage der Vermutung ist, dass das kleinste Element jedes Collatz-Orbits die Zahl ist.
Wegen der simplen Formulierung der Problemstellung werden im Internet immer wieder angebliche Beweise veröffentlicht. Ein häufiger logischer Fehlschluss, der gemacht wird, besteht darin, das Problem lediglich neu zu formulieren, anstatt es tatsächlich zu beweisen.
Preisgeld für die Lösung Trotz zahlreicher Anstrengungen gehört diese Vermutung noch immer zu den ungelösten Problemen der Mathematik. Mehrfach wurden Preise für eine Lösung ausgelobt: 1970 bot H. S. M. Coxeter 50 Dollar für einen Beweis der Vermutung und 100 Dollar für ein Gegenbeispiel.H. S. M. Coxeter: Cyclic sequences and frieze patterns: The fourth Felix Behrend memorial lecture, Vinculum 8, 1971, S. 4–7 (englisch); Nachdruck mit Kommentar in Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, S. 211–218 (Vermutung auf S. 214; Zentralblatt-Rezension) 1982 versprach Bryan Thwaites in der Zeitung The Times 1000 Pfund für einen Beweis oder eine Widerlegung (Angebot 1996/1998 erneuert).PHS: The Times Diary. Sums of money, The Times 61228, 17. Juli 1982, S. 8 und The Times Diary. Aftermath, The Times 61320, 25. August 1982, S. 8C. Williams, B. Thwaites, A. van der Poorten, W. Edwards, L. Williams: Ulam’s conjecture continued again, PPC Calculator Journal 9, September 1982, S. 23–24 (englisch)Bryan Thwaites: Two conjectures, or how to win £1100, The Mathematical Gazette 80, März 1996, S. 35–36 (englisch)Bryan Thwaites: Try to Win auf nrich, 10. März 1998 (englisch) Paul Erdős bot angeblich 500 Dollar für eine LösungJeffrey C. Lagarias, The 3x + 1 problem and its generalizations, The American Mathematical Monthly, Volume 92, Issue 1, S. 3–23, 1985. doi:10.1080/00029890.1985.11971528 und sagte über das Collatz-Problem: „Mathematics is not yet ready for such problems.“ („Die Mathematik ist für solche Probleme noch nicht bereit.“) und „Hopeless. Absolutely hopeless.“ („Hoffnungslos. Absolut hoffnungslos.“) Der Mathematiker Richard Guy warnte 1983 vor diesem und drei anderen auch heute noch ungelösten Problemen:Richard K. Guy: Don’t try to solve these problems! American Mathematical Monthly 90, 1983, S. 35–41 (englisch, doi:10.1080/00029890.1983.11971148; Zentralblatt-Rezension); Nachdruck in Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, S. 231–239Darren Glass: MAA Review zu Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, MathDL, 31. März 2011 (englisch) „Don’t try to solve these problems!“ („Versuche nicht, diese Probleme zu lösen!“)
Ursprung und Geschichte Der Ursprung der Collatz-Vermutung liegt insofern etwas im Nebel, als aus der mutmaßlichen Entstehungszeit bisher keine schriftlichen Dokumente mit einer Beschreibung des Problems öffentlich zugänglich sind. Es wird berichtet, dass Collatz das Problem beim Internationalen Mathematikerkongress 1950 in Cambridge (Massachusetts) mündlich verbreitete.Jeffrey Lagarias: The 3x+1 problem: An overview, www.arxiv.org, 2021, S. 3 (englisch). Stanisław Ulam und Shizuo Kakutani, die auf diesem Kongress zu Vorträgen eingeladen waren, stellten das Problem immer wieder in Gesprächen dar und werden deshalb in diesem Zusammenhang häufig genannt. Als Lothar Collatz 1952 seine Professur in Hamburg antrat, erzählte er seinem Hamburger Kollegen Helmut Hasse von der Vermutung. Dieser verbreitete das Problem während eines Forschungsaufenthalts an der Syracuse University, deshalb erhielt das Collatz-Problem auch den Namen Syracuse-Vermutung. Publikationen zur Entstehung und Verbreitung: 1971 wurde das Collatz-Problem in der gedruckten Version eines 1970 gehaltenen Vortrags von H. S. M. Coxeter zum vermutlich ersten Mal schriftlich veröffentlicht. 1972 erfuhr Martin Gardner von der Beschäftigung der akademischen Hacker am MIT mit dem (3n+1)-ProblemITEM 133 (Schroeppel, Gosper, Henneman & Banks) aus M. Beeler, R. W. Gosper, R. Schroeppel: HAKMEM, MIT AI Memo 239, 29. Februar 1972 (englisch). und beschrieb es in seiner Kolumne Mathematical Games im Scientific American.Martin Gardner: Mathematical Games, Scientific American 226, Juni 1972, S. 114–118 (englisch); Nachdruck mit Kommentar in Wheels, life, and other mathematical amusements, W. H. Freeman and Company, New York 1983, ISBN 0-7167-1588-0, S. 196–197 und 203–204. Die Vermutung wurde durch diese und weitere Veröffentlichungen unter anderem von John ConwayJ. H. Conway: Unpredictable Iterations in: Proceedings of the 1972 Number Theory Conference. University of Colorado, Boulder, Colorado, 1972, S. 49–52 (englisch; Zentralblatt-Rezension); Nachdruck in Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, S. 219–223. inner- und außerhalb von Fachkreisen weithin bekannt. 1976 veröffentlichte Riho Terras die ersten wissenschaftlichen Forschungsergebnisse direkt zum Collatz-Problem.Riho Terras: A stopping time problem on the positive integers (PDF, 632 kB; 24. Oktober 1974), Acta Arithmetica 30, 1976, S. 241–252 (englisch; Zentralblatt-Rezension)dazu Riho Terras: On the existence of a density (PDF, 132 kB; 27. Juli 1978), Acta Arithmetica 35, 1979, S. 101–102 (englisch; Zentralblatt-Rezension). Terras zeigte mit probabilistischen Methoden, dass
für fast alle (bezüglich der logarithmischen Dichte) gilt. 1985 erschien in der Zeitschrift American Mathematical Monthly ein Überblicksartikel von Jeffrey Lagarias. Lagarias berichtet darin über Collatz’ Interesse an zahlentheoretischen Funktionen und Graphentheorie, und er zitiert einen Notizbucheintrag vom 1. Juli 1932, in dem Collatz die folgende Permutation der positiven ganzen Zahlen betrachtet:
Diese Permutation besitzt den Fixpunkt 1 und außerdem zumindest die Zyklen (2, 3), (4, 5, 7, 9, 6) und (44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66). In dem zitierten Notizbucheintrag stellt Collatz die auch heute noch offene Frage, ob die mit 8 beginnende g-Trajektorie zyklisch wird oder gegen unendlich divergiert. Die ebenfalls weiterhin offene Frage, ob weitere Zyklen existieren, ist wie die (3n+1)-Vermutung eines der von Guy beschriebenen Probleme, die man nicht zu lösen versuchen solle.Guy: E17. Permutation sequences, 2004 (englisch). 1985 veröffentlichte Bryan Thwaites eine Mitteilung, er habe die Vermutung am 21. Juli 1952 um vier Uhr nachmittags als Aufgabe zur Unterhaltung seiner Schüler gestellt (er beanspruchte bereits 1982 die Entdeckung im Jahr 1952).Bryan Thwaites: My conjecture, Bulletin of The Institute of Mathematics and its Applications 21, März/April 1985, S. 35–41 (englisch; Zentralblatt-Rezension). 1986 ließ Lothar Collatz eine Darstellung seines Entdeckungswegs zur (3n+1)-Vermutung ins Chinesische übersetzen und in einem Journal der Pädagogischen Universität Qufu, Shandong, China, an der er einen Vortrag darüber gehalten hatte, veröffentlichen.Lothar Collatz: Über die Entstehung des (3n+1)-Problems, Journal of Qufu Normal University Natural Science Edition 12 No. 3, 1986, S. 9–11 (chinesische Übersetzung aus dem Deutschen von Zhi-Ping Ren); On the motivation and origin of the (3n+1)-problem in Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, S. 241–247 (englische Übersetzung aus dem Chinesischen). Dies blieb die einzige Veröffentlichung von Collatz zu diesem Problem.
Nach Terras’ Publikation 1976 begann nach und nach eine rege wissenschaftliche Beschäftigung mit dem Collatz-Problem, die mittlerweile weit mehr als hundert Publikationen mit neuen Forschungsergebnissen umfasst. Im populärwissenschaftlichen Bereich entstanden neue Bezeichnungen: 1979 nannte Douglas R. Hofstadter in seinem Buch Gödel, Escher, Bach diejenigen Startzahlen, deren Collatz-Trajektorie im Zyklus (1,4,2) endet, wondrous numbers, wundersame Zahlen.Douglas R. Hofstadter: Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, New York 1979, ISBN 0-465-02685-0, S. 400–402 (englisch). 1984 nannte Brian Hayes die Zahlen von Collatz-Folgen in der Kolumne Computer recreations im Scientific American hailstone numbers, Hagelschlagzahlen.Brian Hayes: Computer recreations: On the ups and downs of hailstone numbers (PDF; 1,1 MB), Scientific American 250, Januar 1984, S. 10–16 (englisch). 1994 zeigte Ivan Korec, dass für die Anfangswerte fast überall für den Collatz-Algorithmus einen Wert unter erreichen. 2019 zeigte Terence Tao, dass die Collatz-Vermutung für die natürlichen Zahlen fast zutrifft, siehe Abschnitt Collatz-Problem#Teillösung von Tao.Kevin Hartnett: Mathematician proves huge result on ‘dangerous’ problem, Quanta Magazine, 11. Dezember 2019 (englisch). Tao nützte dabei probabilistische Methoden und zeigte mittels der logarithmischen Dichte, dass das Infimum des Collatz-Orbits für die Elemente fast überall für jede divergierende Funktion beschränkt ist, egal wie langsam diese divergiert (zum Beispiel ).
Collatz-Graph einer Funktion mini|hochkant=0.5|Ausschnitt aus dem Collatz-Graphen zur Collatz-Funktion
Collatz’ Beschreibung seiner Motivation der (3n+1)-Vermutung ist sehr plausibel:Günther J. Wirsching: Über das 3n+1 Problem, Elemente der Mathematik 55, November 2000, doi:10.5169/seals-5637, S. 142–155 (Zentralblatt-Rezension) Er assoziiert zunächst ganz allgemein zu einer beliebigen Funktion auf den natürlichen Zahlen mit Werten in den natürlichen Zahlen einen gerichteten Graphen, der von Lagarias im oben erwähnten Überblicksartikel Collatz-Graph genannt wird. Der Collatz-Graph einer zahlentheoretischen Funktion
ist ein gerichteter Graph, bestehend aus der Menge der natürlichen Zahlen als Knotenmenge und zu jeder natürlichen Zahl einer gerichteten Kante von nach .
Die einfachste solche Funktion ist die Nachfolgerabbildung
deren Collatz-Graph aus einem unendlich langen Weg besteht: