Von der Vermutung zur Gewissheit

Gespeichert von mk am Sa, 2.12.2017 - 21:52

Das Collatz-Problem ist also wieder einmal gelöst? Manch eine Augenbraue mag bei dieser Nachricht in die Höhe schnellen. Gibt es doch nicht wenige, die glauben, dass es überhaupt keine Lösung gibt. Wer soll diesen Artikel also lesen? Ich setze einfach darauf, dass es genügend gemeine Zeitgenossen gibt, die Spaß daran haben, einem Enthusiasten die Laune zu verderben, indem sie die vorgestellte Theorie widerlegen. Wir werden sehen!

Wer hat Schuld?

Vor langer Zeit, etwa in den 30er Jahren des letzten Jahrhunderts, hat der Student Lothar Collatz das nach ihm benannte Problem erstmals in die Öffentlichkeit getragen. So jedenfalls sagen es die Mehrzahl der Googlikationen. Wie es entdeckt wurde, lässt sich nicht mehr rekonstruieren, es war eben auf einmal da. Später erwirbt sich der Mathematiker und Physiker Collatz, geboren 1910 in Arnsberg (Sauerland) große Verdienste für seine Arbeiten auf dem Gebiet der angewandten und numerischen Mathematik. Er wird 80 Jahre alt. Mehr Informationen über ihn gibt es bei der Uni Hamburg. Auch die c't spendierte einen Artikel zu seinem 100. Geburtstag.

Die Vermutung

Was ist das Collatz-Problem (oder das 3x + 1 Problem oder die Collatz-Vermutung, wie das Rätsel auch genannt wird)? Es geht um Folgen ganzer Zahlen. Aus der Schule kennen wir zahlreiche Folgen. Am interessantesten sind jene, die gegen einen Grenzwert konvergieren (z. B. die Folge 1/20 + 1/21 + 1/22 + ... + 1/2n; sie läuft gegen 2). Jedoch, Konvergenz funktioniert wirklich gut nur mit reellen Zahlen. Auch Collatz-Folgen konvergieren nicht. Man muss sie abbrechen. Das tut man in der Regel, wenn die 1 erreicht ist. Und da sind wir auch schon bei einer Besonderheit dieser Folgen angekommen. Es ist nämlich keine Folge bekannt, die nicht mit den Zahlen (4, 2, 1) endet (vorausgesetzt, sie ist lang genug). Die Vermutung lautet also: Jede Collatz-Folge enthält dieses Tripel. Allein der Beweis fehlt bis heute. Was macht eine Beweisführung so schwer? Zum einen: Man muss zur Bestimmung eines Folgengliedes zunächst seine sämtlichen Vorgänger berechnen, ähnlich wie bei der Fakultätsfunktion (n! = 1∙2∙3∙...∙(n-1)∙n). Beim obigen Beispiel mit den Zweierpotenzbrüchen lässt sich dagegen das n-te Glied direkt bestimmen (etwa n5 = 1/32). Zum anderen: Es fehlen Eigenschaften wie etwa Monotonie, die es erlauben, Zahlenbereiche mithilfe von Intervallen einzugrenzen. Der Verlauf vor den letzten 3 Gliedern einer Collatz-Folge scheint dagegen völlig ungeordnet zu sein. Diese Eigenschaften verunsichern Mathematiker und Informatiker. Es könnte ja Folgen geben, die niemals bei der 1 ankommen. Da gibt es aber eine gute Nachricht: Man kann zeigen, dass tatsächlich alle Collatz-Folgen in endlich vielen Schritten die 1 erreichen. Dazu muss man die Folgen von einem besonderen Blickwinkel aus betrachten. Ausführlich ist das in meinem, zu dieser Seite gleichnamigen Buch dargelegt. Einige Aspekte daraus werden wir jetzt besprechen.

Ansichtssache

Wie sieht das Bildungsgesetz konkret aus? Es gibt im Wesentlichen zwei Versionen, die jedoch ineinander überführbar sind. Der erste Algorithmus, den wir den Klassischen nennen, arbeitet mit 3z + 1 im unteren Zweig:

Klassischer Algorithmus

Daneben gibt es die sogenannte konsolidierte (bereinigte) Variante. Sie rechnet mit (3z + 1)/2:

Konsolidierter Algorithmus

Bei beiden ist das Haltesignal (oberer Zweig) bereits eingebaut. Denn ohne wird es auf Dauer etwas eintönig, wie man leicht mit der 1 als Startwert nachrechnet. Der mittlere Zweig sorgt für eine Abnahme der Folgenwerte, der Untere für eine Zunahme. Um den Unterschied in der Wirkung der Algorithmen zu erkennen, ist es Zeit, unseren Abakus zu benutzen (am besten in einem neuen Tab öffnen). Wir geben die 30 in das Feld 'Startwert' ein und klicken auf den 'Und los!'-Button. Die linke Spalte der Wertetabelle zeigt die Folgenglieder (den Rest kriegen wir später). Das Diagramm rechts oder unten, je nach verwendetem Endgerät, zeigt den Kurvenzug. Sieht zackig aus! Er erinnert an ein Sägeblatt. Die Form entsteht dadurch, dass im unteren Zweig von Algorithmus 1 bereits nach einem Durchlauf wieder eine gerade Zahl entsteht, die sogleich an den mittleren Zweig übergeben wird. Nun probieren wir die Checkbox 'konsolidiert'. Nun sind ein paar der Sägezähne verschwunden und die verbliebenen sind nicht mehr so scharf. Der untere Zweig kann jetzt nämlich mehrfach hintereinander durchlaufen werden. Dafür ist die Folge etwas kürzer. Falls nichts anderes gesagt wird, werden wir uns im Folgenden dem konsolidierten Algorithmus zuwenden. Zum einen, weil das ständige Auf und Ab des Ersten einen ganz sägkrank macht, zum anderen, weil nur der Zweite das Geheimnis der Collatz-Folgen preisgibt.

Bezugssystem

Bis jetzt haben wir nur Kritzeleien mit hässlichen Farben gesehen. Zeit, Ordnung in die Angelegenheit zu bringen. Wir befinden uns im II. Quadranten eines kartesischen Koordinatensystems. Die Ordinatenachse teilt die z logarithmisch ein. Die Abszissenachse bleibt linear. Diese ist eigentlich negativ zu zählen, aber wir wollen mal nicht so sein. Im Ursprung (0, 0) des Koordinatensystems liegt die 1. Die Achsen sind nicht eingezeichnet - man braucht sie auch nicht unbedingt. Alle Zahlen sind in sogenannte Horizontalbänder (kurz H-Band) einsortiert. Das sind die nummerierten abwechselnd roten und grünen Streifen im Hintergrund der Grafik. Die Nummer gibt an, wie viele Stellen genau eine Zahl in diesem Band für die Darstellung im binären Zahlensystem benötigt. Die führende 1 ist somit obligatorisch. Im H-Band 4 liegen beispielsweise ausschließlich die Zahlen 8 bis 15 (binär 1000 – 1111). Zum Kurvenzug: Es fällt auf, dass es nur zwei Richtungen gibt: diagonal und nach unten. Auf der Abakus-Seite soll jetzt die 13 untersucht werden. Die Senkrechten denke man sich nach unten verlängert (auch eine durch die 13). Der Schnittpunkt mit der (gedachten) x-Achse heißt Spaltenkoordinate oder kurz Spalte. Die 13 liegt also in Spalte 2. Die Bedeutung der Spalte ist, dass sie alle Schritte durch den unteren Zweig des Algorithmus bis zur 1 zählt. Ähnlich verhält es sich mit der Diagonale, die unter Beibehaltung der Richtung zur y-Achse weitergeführt wird. Die y-Achse hat also eine doppelte Funktion: Sie zählt auch die Diagonalen. Durch Einzelwerte wie die 2 oder 10, muss man sich ebenfalls eine Diagonale denken. Wie bei der Spalte wird auch hier ab der 0 gezählt. Die 13 liegt also auf Diagonale 5, was die Anzahl der Schritte durch den mittleren Zweig widerspiegelt. Man muss sich nur daran gewöhnen, dass die y-Achse diagonal abgeschnitten wird. Die 13 benötigt damit 7 Schritte durch den Algorithmus. Die Länge l einer Folge beträgt Spalte + Diagonale + 1 Glieder (l = c + d + 1). Die Startwerte im klassischen und konsolidierten Algorithmus besitzen die gleiche Spaltenzahl. Der Diagonalwert ist beim klassischen Algorithmus um den Spaltenwert größer als beim Konsolidierten. Die wichtigsten Daten einer Folge werden ganz unten auf der Abakus-Seite in der Zeile 'Abstract' zusammengefasst.

Verkettungen

Wir wenden uns nun wieder dem Algorithmus zu und interessieren uns für den allgemeinen Fall, dass die Zweige mehrfach hintereinander durchlaufen werden. Für die Spalte (mittlerer Zweig) gilt die Beziehung 

G-Kette

zwischen den Folgengliedern. Sie bildet sogenannte G-Ketten. Testen lässt sich das an Zahlen mit hoher Geradheit. Die Geradheit entspricht der Anzahl der aufeinanderfolgenden Nullen hinter der niederwertigsten 1, wenn man diese Zahl binär darstellt. Die einfachsten Beispiele sind die Zweierpotenzen in Spalte 0. Folgen, die es bis hierher schaffen, terminieren immer. Ein anderes Beispiel ist die 80 (dual 1010000). Sie besitzt die Geradheit 4. Die Geradheit nimmt mit jedem Schritt ab, denn durch 2 teilen, bedeutet nichts anderes als eine hintere binäre 0 zu streichen. Und das solange, bis am Ende eine ungerade Zahl übrig bleibt. Noch interessanter sind aber U-Ketten (unterer Zweig), die nach der Formel

U-Kette

gebildet werden. Zur Demonstration eigenen sich Zahlen der Art 2k - 1, wie etwa 1023. Für die Ausgabe begrenzt man die Folge am besten auf 11 oder 12 Punkte. Jetzt lohnt sich ein Blick auf die Wertetabelle. In der zweiten und dritten Spalte sind die Folgenglieder in das Binär- bzw. Ternärsystem umgerechnet. Wir sehen, dass die 1023 aus 10 Einsen besteht, oder anders ausgedrückt, die Ungeradheit 10 besitzt. Die Ungeradheit ist analog zur Geradheit, die Anzahl der hinteren Einsen in Binärdarstellung und es gilt Ungeradheit(z) = Geradheit(z + 1). Man erkennt, dass die Ungeradheit mit jedem Schritt abnimmt, bis schließlich eine gerade Zahl übrig bleibt. Und was tut sich in der Ternär-Spalte? Dort gibt es eine gegenläufige Bewegung bei den hinteren Zweien. Die Summe der Anzahlen von Einsen und Zweien ist eine Invariante. Sie gibt die Anzahl der Schritte durch eine U-Kette mit maximal möglicher Länge an. Die Anzahl der Zeilen zwischen den Trennlinien entspricht der Länge der Kette bis zur abschließenden geraden Zahl (diese eingeschlossen). Was bedeutet das nun alles?

  1. Alle U-Ketten sind von endlicher Länge, denn jeder Startwert ist eine konkrete Zahl, und deren Stellenzahl ist beschränkt.
  2. Innerhalb von Ketten gibt es das eingangs beschriebene Vorgänger-Problem nicht. Mithilfe der Formeln lässt sich jedes Glied innerhalb einer Kette direkt bestimmten und bei U-Ketten deren maximale Länge.
  3. Man kann auch rückwärts rechnen (dazu vertausche man auf einer Seite der Gleichungen entweder m und n oder Zähler und Nenner). Beide Ketten sind streng monoton, weil Exponentialfunktionen.

Das alles ist schon sehr nützlich für die Lösung des Terminierungsproblems. Aber leider fehlt die Möglichkeit, auch die Anzahl der Segmente einer Folge zu bestimmen. Die 1-Verschiebung bei der U-Kette ist übrigens der Grund dafür, dass man die Abbruchbedingung im Collatz-Algorithmus benötigt. Denn sie bewirkt gerade eine Verdoppelung der 1. Bei größeren Zahlen gibt es einen solchen Effekt nicht mehr. In einer Collatz-Folge kommt jede Zahl nur ein einziges Mal vor. Diese nicht ganz unwichtige Eigenschaft ist im Buch genauer beschrieben.

Von hinten betrachtet

Der Umstand, dass wohl alle Folgen das Tripel (4, 2, 1) enthalten, inspiriert zu dem Gedanken, dass vielleicht jede Collatz-Folge bei der 1 startet, anstatt dort zu enden. Und der Startwert ist in Wahrheit der Endpunkt, der über die Angabe der (c, d)-Koordinaten bestimmt wird. Daher entzückt die Option, rückwärts rechnen zu können. Direktes rückwärtsrechnen geht natürlich nicht, denn man muss sich ja ständig entscheiden, ob man weiter nach oben geht oder diagonal abbiegt. Es wäre also von Vorteil, wenn die Folge nur eine einzige U-Kette besäße. Tatsächlich ist es möglich, für jede Collatz-Folge eine zu ihr äquivalente Sequenz anzugeben, die nur eine Diagonale besitzt. Äquivalent bedeutet, beide Folgen lassen sich umkehrbar eindeutig ineinander umrechnen.

Diagonalfolge 9
Collatz-Folge mit Startwert 9 und äquivalente Diagonalfolge (blau)

Beispiel: Die Collatz-Folge mit Startwert 9 ist äquivalent zur Sequenz 9, 14, 22, 34, 52, 80, 128, 64, 32, 16, 8, 4, 2, 1. Beide Folgen besitzen die gleiche Anzahl an Spalten- und Diagonalschritten. Der Diagonalteil endet immer auf einer Zweierpotenz. Von einer Zweierpotenz kann man alle Diagonalen rückwärts berechnen und diese anschließend in Collatzfolgen umwandeln. Diese Berechnung ist hier allerdings nicht so einfach darzustellen und bleibt deshalb dem Buch vorbehalten. Das Rückwärtsrechnen eröffnet ganz neue Möglichkeiten. So kann man zu jedem Punkt im Koordinatensystem alle dort liegenden Startwerte für Collatz-Folgen berechnen. Dabei gibt es Orte, an denen keine Collatz-Folge startet, etwa bei (4, 5). Der Punkt liegt eine Diagonale unterhalb der 11. An anderen Positionen gibt es genau einen Startwert (z. B. die 7 bei (5, 6)). Im Allgemeinen sind es aber viele (z. B. 36, 37, 38 an (6, 9)) oder ganz viele wie an (11, 32). Dort gibt es etwa 20000 Startwerte aus dem Intervall [39976960, 49654187]. Alle Zahlen haben die gleiche Länge von 44 Gliedern, nehmen aber natürlich unterschiedliche Wege. Das Rückwärtsrechnen ist also nicht eindeutig. Das macht die Sache rechenintensiv. Deswegen tut man das am besten offline. Im Buch steht, wie es geht. Das Zahlenschema, das durch das Koordinatensystem abgebildet wird (das CD-Feld), erlaubt demnach den Zugang über zwei einander entgegengesetzte Operationen:

1. Die Vorgabe eines Startwertes liefert durch den Collatz-Algorithmus dessen Koordinaten im CD-Feld.
2. Die Vorgabe von (c, d)-Koordinaten liefert andererseits sämtliche Startwerte der Folgen, die an diesen Koordinaten beginnen.

Alles hat ein Ende, nur das „U” hat zwei

Es gilt noch zu klären, warum alle Collatz-Folgen notwendigerweise terminieren. Wieder Gelegenheit, ein bisschen zu spielen. Wir betrachten die Folge der Startwerte 1, 3, 151, 26512143, 318400215865581346424671, ... Wer errät die nächste Zahl? Diese sogenannten Simplexfolgen bestehen aus nur je einer U- und G-Kette. In jeder Spalte entspringt so eine Folge. U-Ketten haben zwei Enden und sind endlich. Bei einer Simplexfolge liegt ein Ende in Spalte 0. Simplexfolgen terminieren daher. Da aber jeder Startwert in einer Spalte liegt, in der eine Simplexfolge beginnt, müssen auch die zugehörigen Collatz-Folgen endlich sein, denn diagonal und nach unten geht ihr irgendwann der Platz aus.

Die Berechnung der Simplexdiagonalen stellt Hard- und Software vor gewisse Herausforderungen, denn die Zahlen wachsen hyperexponentiell mit jeder weiteren (soll heißen, sie wachsen mit dem Exponenten eines Exponenten). Mit einem Mittelklasserechner und ein paar Minuten Geduld kann man es immerhin bis in Spalte 13 schaffen.

Das Prinzip, das hinter dem Collatz-Problem steckt, ist also nicht so schwer zu verstehen. Die eine oder andere Behauptung bedarf natürlich des Beweises. Habe ich eigentlich schon erwähnt, dass ich zu der ganzen Thematik ein Buch geschrieben habe?