Collatz-Problem

Das Collatz-Problem, auch als (3n + 1)-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde.

Problemstellung

Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden:

• Beginne mit irgendeiner natürlichen Zahl n > 0.
• Ist n gerade, so nimm als nächstes n / 2,
• ist n ungerade, so nimm als nächstes 3n + 1.

So erhält man z. B. für die Startzahl n = 19 die Folge

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...

Anscheinend mündet jede Folge mit n > 0 in den Zyklus 4, 2, 1 – egal welche Startzahl n man probiert hat. Die Collatz-Vermutung lautet:

Jede so konstruierte Zahlenfolge mündet in den Zyklus 4, 2, 1, egal, mit welcher natürlichen Zahl n > 0 man beginnt.

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 $ für einen Beweis der Vermutung und 100 $ für ein Gegenbeispiel.
• 1996 versprach Bryan Thwaites 1000 englische Pfund.
• Paul Erdős bot 500 Pfund für eine Lösung, sagte aber über das Collatz-Problem:

  „Mathematics is not yet ready for such problems.“ (Die Mathematik ist für solche Probleme noch nicht bereit.)

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.

Publizierte Quellen

• 1971: Das Collatz-Problem wird in der gedruckten Version eines 1970 gehaltenen Vortrags von H. S. M. Coxeter zum vermutlich ersten Mal veröffentlicht.^[1]
• 1976: Riho Terras ist der Autor der ersten wissenschaftlichen Publikation mit Forschungsergebnissen zum Collatz-Problem.^[2]
• 1985: In der Zeitschrift American Mathematical Monthly erscheint ein Überblicksartikel von Jeffrey Lagarias.^[3] 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:

$g(n) = \begin{cases} \tfrac{2}{3} n & \text{wenn} \quad n \equiv 0 \mod 3, \\ \tfrac{4}{3} n - \tfrac{1}{3} & \text{wenn} \quad n \equiv 1 \mod 3, \\ \tfrac{4}{3} n + \tfrac{1}{3} & \text{wenn} \quad n \equiv 2 \mod 3.\end{cases}$

Diese Permutation besitzt den Fixpunkt 1 und außerdem zumindest die Zykel (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.

• 1985: Bryan Thwaites veröffentlicht eine Mitteilung, er habe die Vermutung am 21. Juli 1952 um vier Uhr nachmittags gefunden.^[4]
• 1986: Lothar Collatz lässt eine Darstellung seines Entdeckungswegs zur (3n+1)-Vermutung ins Chinesische übersetzen und im Journal einer Universität in Qufu, Shandong, China, an der er einen Vortrag darüber gehalten hatte, veröffentlichen.^[5]

Der Collatz-Graph einer Funktion

Orbits der ersten 30 natürlichen Zahlen (ohne 27) unter der Collatz-Funktion. Alle Orbits enden bei Eins.

Collatz’ Beschreibung seiner Motivation der (3n+1)-Vermutung ist sehr plausibel:^[6] 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

$f:\mathbb{N} \to \mathbb{N}$

ist ein gerichteter Graph, bestehend aus der Menge der natürlichen Zahlen als Knotenmenge und zu jeder natürlichen Zahl n einer gerichteten Kante von n nach f(n).

Die einfachste solche Funktion ist die Nachfolgerabbildung

$s:\mathbb{N} \to \mathbb{N}, \quad s(n) = n+1,$

deren Collatz-Graph aus einem unendlich langen Weg besteht:

$1 \to 2 \to 3 \to 4 \to 5 \to \ldots$

Um mehr Beispiele zu haben, suchte er zunächst nach einer möglichst „einfachen“ zahlentheoretischen Funktion, deren Collatz-Graph einen Kreis enthält. Eine solche Funktion f muss auf gewissen natürlichen Zahlen n „aufsteigen“, also die Relation n < f(n) erfüllen, und auf anderen natürlichen Zahlen m „absteigen“, also die Relation m > f(m) erfüllen. So stieß er zunächst auf die Funktion

$C_1(n) := \begin{cases} n/2 & \text{wenn } n \text{ gerade ist,} \\ n+1 \quad & \text{wenn } n \text{ ungerade ist.} \end{cases}$

Den Collatz-Graph dieser Funktion kann man wie folgt beschreiben: Die Knoten sind, nach Definition, die positiven ganzen Zahlen. Ist der Knoten k gerade, besitzt k die beiden Vorgängerknoten k-1 und 2k, sonst nur 2k. Außerdem gilt

$C_1^2(n) = C_1(C_1(n)) = \begin{cases} \frac{n}{4} & \text{wenn } n \text{ durch 4 teilbar ist,} \\ \frac{n}{2} + 1 & \text{wenn } n \text{ durch 2, aber nicht durch 4 teilbar ist,} \\ \frac{n+1}{2} \quad & \text{wenn } n \text{ ungerade ist.} \end{cases}$

Daraus folgt

$C_1^2(n) < n \qquad \text{ wenn } n > 2,$

und das hat zur Folge, dass der Collatz-Graph von C₁ nur den Kreis (1,2) besitzt und dass die C₁-Trajektorie zu jeder beliebigen Startzahl in diesen Kreis mündet.

Weil diese Argumentation ziemlich einfach ist, suchte Collatz weiter: der Collatz-Graph der Funktion

$C_2(n) = \begin{cases} n/2 & \text{wenn } n \text{ gerade ist,} \\ 2 n + 1 \quad & \text{wenn } n \text{ ungerade ist,} \end{cases}$

enthält keinen Kreis, da jede ungerade Zahl auf eine größere ungerade Zahl abgebildet wird, und die C₂-Trajektorien daher alle gegen unendlich divergieren.

Der nächste Versuch ist die Collatz-Funktion

$C:\mathbb{N} \to \mathbb{N}, \quad C(n) = \begin{cases} n/2 & \text{wenn } n \text{ gerade ist,} \\ 3 n + 1 & \text{wenn } n \text{ ungerade ist.} \end{cases}$

Zu dieser Funktion fand Collatz nur den „trivialen Kreis“ (1,4,2) – er schrieb, er habe seine Ideen deshalb nicht veröffentlicht, weil er nicht beweisen konnte, dass der „triviale Kreis“ der einzige sei.

Den Collatz-Graphen zu C untersuchten unter anderem Paul J. Andaloro,^[7] Ștefan Andrei, Manfred Kudlek und Radu Ștefan Niculescu.^[8] Sie gewannen unendliche Teilmengen der natürlichen Zahlen, für welche die Collatz-Folge bei 1 endet.

Verbreitung des Collatz-Problems

Es wird berichtet, dass Collatz das Problem beim Internationalen Mathematikerkongress 1950 in Cambridge (Massachusetts) mündlich verbreitete.^[9] Stanisław Marcin Ulam und Shizuo Kakutani, die auf diesem Kongress zu Vorträgen eingeladen waren, stellten das Problem immer wieder in Gesprächen 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.

Nach Riho 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:

• Douglas R. Hofstadter nannte in seinem Buch Gödel, Escher, Bach diejenigen Startzahlen, deren Collatz-Trajektorie im Zykel (1,4,2) endet, wondrous numbers (wundersame Zahlen).^[10]
• Nach Brian Hayes werden sie auch hailstone numbers (Hagelschlag-Zahlen) genannt.^[11]

Prinzipielles

Für eine C-Trajektorie als Zahlenfolge kann man drei einander ausschließende Fälle unterscheiden:

• die Folge endet im (1,4,2)-Zyklus,
• die Folge wächst über alle Grenzen,
• die Folge gerät in einen anderen Zyklus.

Die Vermutung besagt, dass nur der erste Fall eintritt, aber weder der zweite noch der dritte Fall konnte bisher ausgeschlossen werden. Es ist auch nicht bekannt, ob es nur endlich viele Zyklen geben kann.

Da 3n + 1 für ungerade n stets gerade ist und somit die folgende Iteration immer die Division durch 2, wird statt der Collatz-Funktion C meistens die etwas einfacher zu handhabende Funktion

$T:\mathbb{N} \to \mathbb{N}, \quad T(n) = \begin{cases} n/2 & \text{wenn } n \text{ gerade ist,} \\ (3 n + 1) / 2 & \text{wenn } n \text{ ungerade ist,} \end{cases}$

verwendet, die also für ungerade n zwei C-Iterationen auf einmal macht und den der Vermutung zufolge stets erreichten Zyklus von (1,4,2) auf (1,2) reduziert. Die k-fache Abbildung T^k bildet 2^km auf m und 2^km − 1 auf 3^km − 1 ab, insbesondere vergrößert die wiederholte Abbildung mit C oder T bestimmte Startwerte um beliebig große Faktoren.

Berechnungen mit Computern ergaben:^[12]

• Alle positiven ganzen Zahlen bis 20×2⁵⁸ (ca. 5,76×10¹⁸) als Startwerte bestätigen die Vermutung (Stand Januar 2009).^[13]
• Ein anderer Zyklus der T-Iteration als (1,2) müsste aus mindestens 10.439.860.591 Zahlen, davon mindestens 6.586.818.670 ungerade Zahlen, bestehen.^[14]
• Für unendlich viele positive ganze Zahlen n sind mindestens 6,143 log n Iterationen mit T erforderlich, um 1 zu erreichen.^[15] Stochastische Modelle sagen voraus, dass durchschnittlich (2 / log(4/3)) log n ≈ 6,952 log n Schritte benötigt werden, und dass für mindestens die Hälfte aller Zahlen mindestens so viele T-Iterationen erforderlich sind.
• Für genügend große X ist die Anzahl der positiven ganzen Zahlen kleiner oder gleich X, die als Startwert die Vermutung bestätigen, mindestens X^0,84.^[16]

Verallgemeinerungen

Für das auf alle ganzen Zahlen als Startwerte ausgeweitete Collatz-Problem gibt es außer dem (1,4,2)-Zyklus noch mindestens vier weitere Zyklen:

• (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).

Die drei letzten Zyklen mit positiven statt negativen Vorzeichen entstehen auch mit der Definition C(n) = 3n − 1 statt C(n) = 3n + 1 für ungerade n.

Marc Chamberland definierte eine stetige Funktion, welche die diskrete Collatz-Folge auf den Bereich der reellen Zahlen erweitert.^[17] Simon Letherman, Dierk Schleicher und Reg Wood betrachteten Funktionen im Bereich der komplexen Zahlen als Erweiterung.^[18] Allgemeine Vermutung: (3n + 3^x) endet immer in $4\cdot 3^x,\; 2\cdot 3^x,\; 1\cdot3^x$ und besitzt nur diesen einen Zyklus.

Literatur

• Jeffrey C. Lagarias: The 3x+1 problem and its generalizations, The American Mathematical Monthly 92, Januar 1985, S. 3–23 (englisch; 1986 mit dem Lester-R.-Ford-Preis ausgezeichnet; bei MathDL; beim CECM)
• Günther J. Wirsching: The dynamical system generated by the 3n+1 function, Springer-Verlag, Berlin 1998, ISBN 3-540-63970-5 (englisch; revidierte Version der Habilitationsschrift von 1996)
• Jeffrey C. Lagarias: The 3x+1 problem: An annotated bibliography (1963–1999) (sorted by author), arXiv:math/0309224 [math.NT], 2003–2011 (englisch)
• Jeffrey C. Lagarias: The 3x+1 problem: An annotated bibliography, II (2000–2009), arXiv:math/0608208 [math.NT], 2006–2009 (englisch)
• Jeffrey C. Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, American Mathematical Society, Providence RI 2010, ISBN 978-0-8218-4940-8 (englisch)
  • darin Jeffrey C. Lagarias: The 3x+1 problem: An overview (PDF-Datei, 518 kB), S. 3–29 (englisch)

Weblinks

 Wikibooks: Collatzfolgen und Schachbrett – Lern- und Lehrmaterialien

• On the 3x + 1 problem von Eric Roosendaal, ein Distributed-computing-Projekt, das sich mit dem Collatz-Problem beschäftigt (englisch)
• Collatz Conjecture von Jon Sonntag, ein auf BOINC basierendes Projekt, das sich mit der Suche nach Gegenbeispielen beschäftigt (englisch)
• Das Collatz-Problem von Jürgen Dankert – Interaktives Skript zum (3n+1)- und (3n−1)-Problem zum Erzeugen von Folgen mit beliebig großen Startzahlen

Einzelnachweise

1. ↑ H. S. M. Coxeter: Cyclic sequences and frieze patterns: The fourth Felix Behrend memorial lecture, Vinculum 8, 1971, S. 4–7 (englisch); Nachdruck in Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, S. 211–218
2. ↑ Riho Terras: A stopping time problem on the positive integers (PDF-Datei, 632 kB), Acta Arithmetica 30, 1976, S. 241–252 (englisch)
3. ↑ Lagarias: The 3x+1 problem and its generalizations, 1985 (englisch)
4. ↑ Bryan Thwaites: My conjecture, Bulletin of The Institute of Mathematics and its Applications 21, März/April 1985, S. 35–41 (englisch)
5. ↑ 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; die einzige Veröffentlichung von Collatz zu diesem Problem); 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)
6. ↑ Günther J. Wirsching: Über das 3n+1 Problem, Elemente der Mathematik 55, November 2000, S. 142–155
7. ↑ Paul J. Andaloro: The 3x+1 problem and directed graphs (PDF-Datei, 3,8 MB), Fibonacci Quarterly 40, 2002, S. 43–54 (englisch)
8. ↑ Ștefan Andrei, Manfred Kudlek, Radu Ștefan Niculescu: Some results on the Collatz problem (PDF-Datei, 157 kB), Acta Informatica 37, 2000, S. 145–160 (englisch)
9. ↑ Lagarias: The 3x+1 problem: An overview, 2010, S. 5 (englisch)
10. ↑ 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)
11. ↑ Brian Hayes: Computer recreations: On the ups and downs of hailstone numbers (PDF-Datei, 1,1 MB), Scientific American 250, Januar 1984, S. 10–16 (englisch)
12. ↑ Lagarias: The 3x+1 problem: An overview, 2010, S. 16–17 (englisch)
13. ↑ Tomás Oliveira e Silva: Empirical verification of the 3x+1 and related conjectures in Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, 2010, S. 189–207 (englisch)
14. ↑ Shalom Eliahou: The 3x+1 problem: new lower bounds on nontrivial cycle lengths, Discrete Mathematics 118, August 1993, S. 45–56 (englisch; Resultat unter Verwendung der Gültigkeit der Vermutung bis 20×2⁵⁸)
15. ↑ David Applegate, Jeffrey C. Lagarias: Lower bounds for the total stopping time of 3x+1 iterates, Mathematics of Computation 72, April 2003, S. 1035–1049 (englisch)
16. ↑ Ilia Krasikov, Jeffrey C. Lagarias: Bounds for the 3x + 1 problem using difference inequalities, Acta Arithmetica 109, 2003, S. 237–258 (englisch)
17. ↑ Marc Chamberland: A continuous extension of the 3x+1 problem to the real line (PDF-Datei, 159 kB), Dynamics of continuous, discrete and impulsive dynamical systems 2, 1996, S. 495–509 (englisch)
18. ↑ Simon Letherman, Dierk Schleicher, Reg Wood: The 3n+1-problem and holomorphic dynamics (PostScript-Datei, 815 kB), Experimental Mathematics 8, 1999, S. 241–251 (englisch)