G.J. Wirsching

Unter dem Collatz-Problem versteht man eine Frage zum Verhalten der Iterationen der Collatz-Funktion f : ℕ → ℕ,

\begin{eqnarray}f(n)=\left\{ {\begin{array}{c} n/2\,{\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{gerade n,}\\ 3n+1\,\,{\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{ungerade n.}\end{array} } \right.\end{eqnarray}

Es ist ziemlich sicher, daß diese Iteration zuerst von Collatz in den 1930er Jahren untersucht wurde, obwohl keine schriftlichen Quellen aus dieser Zeit vorliegen. 1985 publizierte der englische Mathematiklehrer Thwaites einen Artikel unter dem Titel „My Conjecture“, in dem er behauptet, er habe das 3n+ 1 Problem erfunden, und zwar am 21. Juli 1952 um vier Uhr nachmittags. Vermutlich als Antwort darauf publizierte Collatz 1986 in einem kleinen chinesischen Journal (und in chinesischer Sprache) einen Artikel, in dem er seine Entdeckung des 3n+1 Problem in die 1930er Jahre datiert und sehr plausibel beschreibt. Er schreibt, er habe nach Zusammenhängen zwischen elementarer Zahlentheorie und elementarer Graphentheorie gesucht. Einen solchen Zusammenhang stellte er dadurch her, daß er zu einer zahlentheoretischen Funktion f : ℕ → ℕ einen gerichteten Graphen Γ_f assoziierte, indem er ℕ als Knotenmenge nahm und jeweils von n nach f(n) einen Pfeil zog. Der Graph Γ_f wird heute Collatz-Graph zur Funktion f genannt. Z. B. ist der Collatz-Graph der Funktion g(n) = n+1 ein bei 1 beginnender unendlich langer Weg:

\begin{eqnarray}1\to 2\to 3\to 4\to 5\to 6\to 7\to \ldots \end{eqnarray}

\begin{eqnarray}{f}_{q}(n)=\left\{ {\begin{array}{cc} n/2 & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{gerade n,}\\ qn+1 & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{ungerade n.}\end{array} } \right.\end{eqnarray}

In der mathematischen Forschungsliteratur findet das Collatz-Problem seit etwa 1972 Beachtung. 1985 erschien ein Überblicksartikel von J.C. Lagarias, der eine wahre Flut von bislang mehr als 100 Publikationen zum Collatz-Problem auslöste; siehe [1] für einen Überblick. Ein Beweis der 3n +1 Vermutung ist bisher (Ende 1999) noch nicht in Sicht, aber es gibt viele Teilresultate, die sich auf speziellere Fragestellungen oder auf Fragen über Verallgemeinerungen beziehen. Einige solcher Fragen sind:

1. Gibt es noch andere Zykel? Wieviele, und welche?
2. Endet jede f₃-Trajektorie in einem Zykel, oder gibt es eine divergente Trajektorie?
3. Von welchen Zahlen kann man beweisen, daß sie die 3n + 1 Vermutung erfüllen?
4. Was passiert, wenn man 3n + 1 durch qn + 1 ersetzt?
5. Gibt es noch andere interessante Verallgemeinerungen?
6. Kann es sein, daß das Collatz-Problem nicht entscheidbar ist?
7. Gibt es interessante Erweiterungen oder Umformulierungen des Collatz-Problems?

Zur ersten Frage setzen wir zunächst die Collatz-Funktion f₃ auf die ganzen Zahlen fort. Für negative Zahlen − n erhält man:

\begin{eqnarray}{f}_{3}(-n)=\left\{ {\begin{array}{cc} -n/2 & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{gerade n,}\\ -(3n-1) & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{ungerade n,}\end{array} } \right.\end{eqnarray}

\begin{eqnarray}{f}_{3}^{* }(n)=-{f}_{3}(-n)\end{eqnarray}

\begin{eqnarray}(1, 2),\quad (5, 14, 7, 20, 10), und

\begin{eqnarray}(17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34).\end{eqnarray}

Zum näheren Studium der Struktur möglicher Zykeln verändert man die Collatz-Funktion f₃ zur sog. 3n + 1 Funktion T : ℤ → ℤ,

\begin{eqnarray}T(n)=\left\{ {\begin{array}{cc}{T}_{0}(n)=\displaystyle\frac{n}{2} & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{gerade n,}\\ {T}_{1}(n)=\displaystyle \frac{3n+1}{2} & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{ungerade n.}\end{array} } \right.\end{eqnarray}

Hierbei wird ausgenutzt, daß 3n + 1 für ungerades n stets gerade ist. Eine T-Trajektorie entsteht aus einer f₃-Trajektorie dadurch, daß man in der letzteren jeweils die auf eine ungerade Zahl folgende Zahl wegläßt, z. B.:

\begin{eqnarray}\begin{array}{c}{f}_{3}:(27,82,41,124,62,31,94,47,142,\ldots )\\ T:(27,41,62,31,47,71,107,161,\ldots ).\end{array}\end{eqnarray}

\begin{eqnarray}x\mathop{\to }\limits^{{T}_{1}}\ldots \mathop{\to }\limits^{{T}_{1}}y\mathop{\to }\limits^{{T}_{0}}\ldots \mathop{\to }\limits^{{T}_{0}}z,\end{eqnarray}

\begin{eqnarray}{2}^{k}(y+1)={3}^{k}(x+1),\end{eqnarray}

\begin{eqnarray}{2}^{l}z=y.\end{eqnarray}

\begin{eqnarray}h=\displaystyle\frac{x+1}{{2}^{k}}=\displaystyle\frac{y+1}{{3}^{k}}\end{eqnarray}

\begin{eqnarray}y={2}^{l}x={2}^{l}({2}^{k}h-1),\end{eqnarray}

\begin{eqnarray}({2}^{k+l}-{3}^{k})h={2}^{l}-1.\end{eqnarray}

Auf der Suche nach der Möglichkeit von T-Zykeln, die nicht notwendig ein Kreislauf sind, bewiesen Böhm und Sontacchi 1978 die folgende Zykelbedingung:

Sei x ∈ ℤ. Dann gibt es genau dann ein n ∈ ℕ mit Tⁿ(x) = x, wenn es ganze Zahlen 0 ≤ v₀< v₁< … < v_k = n derart gibt, daß folgende Gleichung erfüllt ist:

\begin{eqnarray}({2}^{n}-{3}^{k})x=\displaystyle \sum _{j=0}^{k-1}{3}^{k-j-1}{2}^{vj}.\end{eqnarray}

Für festes k kann man (8) wieder als exponentiell diophantische Gleichung lesen, und mit Hilfe tiefliegender Resultate über Linearformen in Logarithmen konnten Belaga und Mignotte 1998 folgenden Satz beweisen:

Zu jeder natürlichen Zahl k gibt es nur endlich viele T-Zykel, in denen genau k Schritte des Typs T₁vorkommen.

Dieser Satz gilt nicht nur für die 3n + 1 Funktion T, sondern auch für eine etwas allgemeinere Klasse von Funktionen.

Zur zweiten Frage, die als unabhängig von der ersten zu betrachten ist, ist ziemlich wenig bekannt. Man kann nicht von vorne herein ausschließen, daß es eine unbeschränkte (also divergente) f₃-Trajektorie gibt, aber bewiesen ist das bis heute noch nicht. Andererseits gibt es durchaus Teilresultate.

Die Stoppzeit einer Startzahl x₀ ist nach Terras wie folgt definiert:

\begin{eqnarray}\sigma ({x}_{0})=\min \{n \in {\mathbb{N}}:{T}^{n}({x}_{0}){x}_{0}\};\end{eqnarray}

\begin{eqnarray}({x}_{0},{x}_{1},{x}_{2},\ldots )=({x}_{0},T({x}_{0}),{T}^{2}({x}_{0}),\ldots ),\end{eqnarray}

Es gibt positive Konstanten c, γ mit γ< 1 und

\begin{eqnarray}|\{n\in {\mathbb{N}}:n\le x,\sigma (n)=\infty \}|\,\, \le \,\, c{x}^{\gamma }.\end{eqnarray}

Hieraus folgt, daß eine eventuell existierende divergente Trajektorie nicht „zu langsam“ gegen ∞ divergieren darf.

Die dritte Frage ist vielfach variiert und mit unterschiedlichen Methoden angegangen worden. 1976 bemerkte Terras, daß die Paritäten (gerade/ungerade) der ersten n Zahlen

\begin{eqnarray}{x}_{0}{x}_{1}=T({x}_{0}),\ldots,{x}_{n}-1\end{eqnarray}

Terras entwickelte einen auf der Binomialverteilung beruhenden Beweis folgenden Satzes:

Die Menge aller Startzahlen x₀mit endlicher Stoppzeit hat die asymptotische Dichte 1.

Inzwischen gibt es eine ganze Reihe von sog. „Dichte 1“-Resultaten, die überwiegend als Verschärfungen dieses Satzes betrachtet werden können.

Diese „Dichte 1“-Resultate sind deutlich zu unterscheiden von Abschätzungen der Vorgängerdichte. Eine Zahl x ∈ ℕ heißt T-Vorgänger einer gegebenen Zahl a ∈ ℕ, wenn die T-Trajektorie mit Startzahl x die Zahl a enthält, wenn es also eine Schrittzahl n ≥ 0 gibt mit Tⁿ(x) = a. Die Menge der T-Vorgänger von a ist also gegeben durch

\begin{eqnarray}\mathcal{P}(a)=\{x\in {\mathbb{N}}:{T}^{n}(x)=a\, {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{ein n} \ge 0\}.\end{eqnarray}

\begin{eqnarray}Z_a (x) = \left| {\left\{ {n \in P(a):n \leqslant x} \right\}} \right|,\end{eqnarray}

\begin{eqnarray}\begin{array}{cc}{Z}_{1}(x)=x & {\rm{f}\rm{\ddot{u}}\rm{r}}\,\text{alle}\, x \in {\mathbb{N}}\end{array}.\end{eqnarray}

\begin{eqnarray}\begin{array}{cc}{Z}_{1}(x)\gt {x}^{\beta } & {\rm{f}\rm{\ddot{u}}\rm{r}}\,{\rm{gen}\rm{\ddot{u}}\rm{gend}}\,\text{gro}\unicode{x00DF}e\,x\in {\mathbb{N}}\end{array},\end{eqnarray}

\begin{eqnarray}\mathop{\mathrm{lim}\inf }\limits_{x\to \infty }\,\displaystyle\frac{{Z}_{a}(x)}{x}\gt 0\quad{\rm{f}\rm{\ddot{u}}\rm{r}}\quad a\rlap{/}{\equiv }0\,\mathrm{mod}\,3,\end{eqnarray}

Zur vierten Frage: Ersetzt man die Collatz-Funktion f₃ durch eine wie in (2) definierte Funktion f_q, so kann man analog zum Collatz-Problem die Frage stellen, ob jede f_q-Trajektorie die 1 enthält. Für q > 3 ist das i. allg. falsch: Franco und Pomerance nannten 1995 eine ungerade Zahl Crandall-Zahl, wenn es eine Startzahl x₀ ∈ ℕ gibt, deren f_q-Trajektorie die 1 nicht enthält. Sie bewiesen, daß jede Wieferich-Zahl eine Crandall-Zahl ist, und daß die Menge der Wieferich-Zahlen in den ungeraden Zahlen die relative asymptotische Dichte 1 hat. Das bedeutet, daß für „fast alle“ ungeraden Zahlen q > 3 eine qn + 1 Vermutung falsch ist.

Umfangreiche Computerexperimente, die von Matthews in Brisbane durchgeführt wurden, legen es nahe, daß ein qn+1 Algorithmus mit einer ungeraden Zahl q ≥ 5 schnell wachsende Trajektorien hat. Aber bisher gibt es noch für kein einziges q einen mathematischen Beweis dafür, daß der qn+1 Algorithmus tatsächlich eine divergente Trajektorie besitzt.

Ein anderer Typ von Verallgemeinerungen, der studiert wurde, sind die Hasse-Funktionen. Zur Konstruktion einer Hasse-Funktion benötigt man zwei teilerfremde natürliche Zahlen d, m mit d ≥ 2, und ein vollständiges Restsystem modulo d,

\begin{eqnarray}{A}_{d}=\{0,{r}_{1},\ldots,{r}_{d-1}\},\end{eqnarray}

\begin{eqnarray}H(x)=\left\{ {\begin{array}{cc}\displaystyle\frac{x}{d} & \text{falls}\,d|x,\\ \displaystyle \frac{mx-\phi (mx)}{d} & \text{sonst.}\end{array} } \right.\end{eqnarray}

Die in (3) definierte 3n + 1 Funktion T ist eine Hasse-Funktion mit d = 2, m = 3 und A₂ = {0,1}. Möller bewies 1978 ein „Dichte 1“-Resultat für Hasse-Funktionen unter der zusätzlichen Bedingung m< d^d(d−1); diese Bedingung ist im Fall der 3n + 1 Funktion T erfüllt.

Eine weitergehende Verallgemeinerung ist die auf periodisch-lineare Funktionen, die wie folgt definiert sind. Seien p ≥ 2 eine ganze Zahl, und a₀, …, a_p−1, b₀, …, b_p−1 rationale Zahlen, die den 2p Bedingungen

\begin{eqnarray}{a}_{k}p,\,{a}_{k}k+{b}_{k}\in {\mathbb{Z}}\,\,{\rm{f}\rm{\ddot{u}}\rm{r}}\,k=0,\ldots p-1,\end{eqnarray}

\begin{eqnarray}U(n)={a}_{k}n+{b}_{k}\,\,{\rm{f}\rm{\ddot{u}}\rm{r}}\,\,n=k\,\mathrm{mod}\,p\end{eqnarray}

Conway konstruierte 1972 eine periodischlineare Funktion g mit der Eigenschaft, daß das Grenzverhalten der g-Trajektorien das Halteproblem von Turing-Maschinen codiert. Daraus folgt, daß das Grenzverhalten der g-Trajektorien algorithmisch nicht entscheidbar ist; das ist ein Teilresultat zur sechsten Frage. Man kann aus Conways Resultat aber keine Informationen über die algorithmische Entscheidbarkeit des Grenzverhaltens der 3n+1 Trajektorien herleiten. Im Gegensatz zur 3n + 1 Funktion hat die von Conway konstruierte periodisch-lineare Funktion g die spezielle Eigenschaft b_k = 0 für jedes k = 0, …, p − 1.

Zur siebten Frage ist anzumerken, daß es Umformulierungen und Erweiterungen des Collatz-Problems in ganz verschiedene mathematische Kontexte gibt. Zunächst einmal ist die 3n +1 Funktion T durch (3) ganz offensichtlich auf der Menge ℤ₂ der 2-adischen Zahlen definiert, also auf den unendlichen Folgen (a₀, a₁, …) mit a_j ∈ {0, 1}, die man gewöhnlich in Form der (in der 2-adischen Metrik konvergenten) Reihe

\begin{eqnarray}a={a}_{0}+{a}_{1}\cdot 2+{a}_{2}\cdot {2}^{2}+\ldots =\displaystyle \sum _{j=0}^{\infty }{a}_{j}{2}^{j}\end{eqnarray}

Die Funktion T : ℤ₂ → ℤ₂ist surjektiv, nicht injektiv, unendlich oft differenzierbar, nicht analytisch, sie erhält das Haar-Maß auf ℤ₂, und sie ist stark mischend.

Wählt man für jedes j ≥ 0 die Ziffer a_j derart, daß

\begin{eqnarray}{T}^{j}(a)\equiv {a}_{j}\,\mathrm{mod}\,2\end{eqnarray}

\begin{eqnarray}{Q}_{\infty }:{{\mathbb{Z}}}_{2}\to {{\mathbb{Z}}}_{2},\end{eqnarray}

\begin{eqnarray}{Q}_{\infty }({\mathbb{N}})\subset \displaystyle\frac{1}{3}{\mathbb{Z}}.\end{eqnarray}

Eine Umformulierung in das Reich der holomorphen Funktionen auf der komplexen Einheitskreisscheibe ist durch folgenden Satz von Berg und Meinardus (1994) gegeben:

Die 3n + 1 Vermutung ist genau dann richtig, wenn die Funktional-Gleichung

\begin{eqnarray}h({z}^{3})=h({z}^{6})+\displaystyle\frac{1}{3z}\displaystyle \sum _{j=0}^{2}{\zeta }^{j}h({\zeta }^{j}{z}^{2}),\end{eqnarray}

\begin{eqnarray}h(z)={h}_{0}+\displaystyle\frac{{h}_{1}z}{1-z}\end{eqnarray}

Chamberland formulierte 1996 das Collatz-Problem als ein Problem der Dynamik analytischer Funktionen: Er entdeckte, daß die durch die Gleichung

\begin{eqnarray}{g}_{0}(x)=x+\displaystyle\frac{1}{4}-\displaystyle\frac{2x+1}{4}\cos (\pi x)\end{eqnarray}

\begin{eqnarray}{g}_{0}(x)=T(x)\,\,{\rm{f}\rm{\ddot{u}}\rm{r}}\,x\in {\mathbb{Z}}\text{.}\end{eqnarray}

1998 bestimmten Letherman, Schleicher und Wood alle ganzen Funktionen g : ℂ → ℂ, die einerseits die 3n+1 Funktion T fortsetzen und andererseits die Eigenschaft haben, daß alle ganzen Zahlen kritische Punkte von g sind. Dadurch gelang esihnen, das Collatz-Problem in die schon gut entwickelte Terminologie der holomorphen Dynamik zu übersetzen. Allerdings mußten sie feststellen, daß damit das Wesentliche des Collatz-Poblems nicht leicht zu fassen ist: Jede andere qn+1 Funktion läßt sich nämlich in ähnlicher Weise fortsetzen, und es scheint schwierig, einen Unterschied in der holomorphen Dynamik auszumachen.

Zum Abschluß bleibt noch zu erwähnen, daß das Collatz-Problem eine ganz praktische Anwendung hat. Einige Fragen zur 3n + 1 Dynamik, z. B. die Suche nach Startzahlen mit besonders großer Stoppzeit, können mit einem gut programmierten Computer angegangen werden. Das hat mehrere Autoren (z. B. Leavens und Vermeulen 1989 und 1992, später Roosendaal und andere) dazu veranlaßt, die 3n + 1 Iterationen dazu zu benutzen, Unterschiede zwischen verschiedenen Programmiersprachen und Programmiertechniken zu messen, oder die Qualität neu entwickelter Programmiersysteme zu untersuchen.