Additive systems for $\mathbb{Z}$ are undecidable

1. Problemstellung

Das Paper adressiert das fundamentale Problem der additiven Kombinatorik: Unter welchen Bedingungen bildet eine Familie von Mengen $\mathcal{A} = \{A_0, A_1, \dots\}$ eine additive Basis für die ganzen Zahlen $\mathbb{Z}$?

Eine solche Familie heißt additive Basis für eine monoidale Struktur $M$ (hier $\mathbb{Z}$), wenn jede Zahl $n \in M$ genau einmal als endliche Summe $n = a_0 + a_1 + \dots$ dargestellt werden kann, wobei $a_i \in A_i$ und fast alle $a_i = 0$ sind.

• Hintergrund: Für die nicht-negativen ganzen Zahlen $\mathbb{N}_0$ ist dieses Problem vollständig gelöst (Satz von de Bruijn). Jede additive Basis für $\mathbb{N}_0$ ist eine Kontraktion eines „britischen Zahlensystems" (British number system), das durch eine Folge von Basen definiert ist.
• Die Herausforderung: Für $\mathbb{Z}$ ist die Situation weitaus komplexer. Es gibt keine analoge vollständige Charakterisierung. Das Paper untersucht, ob es möglich ist, zu entscheiden, ob eine gegebene Familie von Mengen eine additive Basis für $\mathbb{Z}$ ist. Die zentrale Frage lautet: Ist das Problem der Vollständigkeit (Completeness) einer solchen Familie algorithmisch entscheidbar?

2. Methodik

Der Autor entwickelt eine Brücke zwischen additiver Kombinatorik und der Theorie dynamischer Systeme.

A. Kanonische Sammlungen (Canonical Collections)

Der Kern der Methode ist die Einführung einer neuen Klasse von Mengenfamilien, genannt kanonische Sammlungen. Diese verallgemeinern bekannte Zahlensysteme für $\mathbb{Z}$ (wie das negabinary-System oder das balancierte Ternärsystem).

Eine kanonische Sammlung wird durch zwei Folgen definiert:

1. Eine Folge von Basen $(b_i)_{i \in \mathbb{N}_0}$ mit $b_i > 1$.
2. Eine Folge von Restklassensystemen $(T_i)_{i \in \mathbb{N}_0}$, wobei jedes $T_i$ ein vollständiges Restsystem modulo $b_i$ ist, das die 0 enthält.

Die Mengen der Sammlung haben die Form:
$$\mathcal{A} = \{ T_0, \ b_0 T_1, \ b_0 b_1 T_2, \ b_0 b_1 b_2 T_3, \ \dots \}$$
Eine solche Sammlung heißt vollständig (complete), wenn ihre direkte Summe genau $\mathbb{Z}$ ergibt.

B. Dynamische Systeme und Trajektorien

Der entscheidende methodische Schritt ist die Übersetzung des additiven Problems in ein dynamisches System.
Für eine gegebene kanonische Sammlung wird eine Folge von Abbildungen $f_i: \mathbb{Z} \to \mathbb{Z}$ definiert:
$$f_i(n) = \frac{1}{b_i} (n - t_i(n))$$
wobei $t_i(n)$ das eindeutige Element aus $T_i$ ist, das kongruent zu $n$ modulo $b_i$ ist.

• Trajektorie: Die Folge $n, f_0(n), f_1(f_0(n)), \dots$ wird als Trajektorie von $n$ bezeichnet.
• Äquivalenz: Eine Zahl $n$ lässt sich genau dann eindeutig als Summe aus $\mathcal{A}$ darstellen, wenn ihre Trajektorie in diesem dynamischen System schließlich konstant Null wird (d.h. nach endlich vielen Schritten $0$ erreicht).
• Vollständigkeit: Eine kanonische Sammlung ist genau dann vollständig für $\mathbb{Z}$, wenn die Trajektorie jeder ganzen Zahl $n \in \mathbb{Z}$ schließlich Null wird.

3. Wichtige Beiträge und Ergebnisse

Das Paper liefert drei Hauptergebnisse, die die Komplexität des Problems aufzeigen:

A. Äquivalenz zur Collatz-Vermutung (Theorem 1)

Der Autor konstruiert eine spezifische kanonische Sammlung $\mathcal{A}_C$, deren Vollständigkeit direkt äquivalent zur Wahrheit der Collatz-Vermutung ist.

• Konstruktion: Die Basen und Restsysteme werden so gewählt, dass die zugehörigen Abbildungen $f_i$ das Verhalten der Collatz-Funktion ($3n+1$ für ungerade, $n/2$ für gerade) simulieren.
• Ergebnis: Die Sammlung $\mathcal{A}_C$ ist genau dann eine additive Basis für $\mathbb{Z}$, wenn jede positive ganze Zahl unter der Collatz-Iteration schließlich den Zyklus $1 \to 4 \to 2 \to 1$ erreicht und damit in der dynamischen Sichtweise „Null" wird.
• Implikation: Da die Collatz-Vermutung offen ist, ist die Vollständigkeit dieser spezifischen kanonischen Sammlung ebenfalls ungelöst.

B. Undecidabilität durch Fractran (Theorem 2 & Korollar 2)

Das stärkste Ergebnis des Papers ist der Nachweis der algorithmischen Unentscheidbarkeit.

• Fractran: Der Autor nutzt die Programmiersprache Fractran (entwickelt von John Conway), die bekanntermaßen Turing-vollständig ist. Das universelle Halteproblem für Fractran ist unentscheidbar.
• Konstruktion: Es wird eine Familie von „Fractran-Typ"-kanonischen Sammlungen $\mathcal{A}_F$ definiert, die durch ein gegebenes Fractran-Programm $F$ parametrisiert sind. Die dynamischen Abbildungen $f_i$ simulieren die Iteration von Fractran.
• Ergebnis: Ein Fractran-Programm $F$ hält für alle Eingaben genau dann, wenn die zugehörige kanonische Sammlung $\mathcal{A}_F$ vollständig ist.
• Folgerung: Da das universelle Halteproblem für Fractran unentscheidbar ist, ist auch das Problem, zu entscheiden, ob eine gegebene kanonische Sammlung (speziell vom Fractran-Typ) eine additive Basis für $\mathbb{Z}$ ist, unentscheidbar.

4. Signifikanz und Bedeutung

Dieses Paper hat tiefgreifende Implikationen für mehrere mathematische Gebiete:

1. Grenzen der Entscheidbarkeit in der additiven Kombinatorik: Es zeigt, dass selbst für sehr gutartige, strukturierte Familien von Mengen (kanonische Sammlungen), die eine natürliche Verallgemeinerung von Zahlensystemen darstellen, die Frage nach der Vollständigkeit algorithmisch unlösbar sein kann. Dies steht im starken Kontrast zum Fall von $\mathbb{N}_0$, wo eine vollständige Charakterisierung existiert.
2. Verbindung scheinbar unabhängiger Probleme: Das Paper etabliert eine direkte Verbindung zwischen additiver Kombinatorik und berühmten, schwer lösbaren Problemen der theoretischen Informatik und Zahlentheorie (Collatz, Halteproblem). Es demonstriert, dass Fragen über die Überdeckung von $\mathbb{Z}$ durch Summenmengen die gleiche Komplexität wie universelle Berechnungsprobleme haben können.
3. Dynamische Systeme als Werkzeug: Die Methode, additive Zerlegungen als Trajektorien in nicht-autonomen dynamischen Systemen zu interpretieren, bietet einen neuen, mächtigen Rahmen zur Analyse solcher Probleme. Sie erlaubt es, bekannte Ergebnisse aus der Theorie der dynamischen Systeme auf Probleme der additiven Zahlentheorie zu übertragen.
4. Fehlende Analogie zu de Bruijn: Das Paper bestätigt, dass es für $\mathbb{Z}$ keine einfache Analogie zu de Bruijns Theorem für $\mathbb{N}_0$ gibt. Nicht jede additive Basis für $\mathbb{Z}$ ist eine Kontraktion einer kanonischen Sammlung, und selbst innerhalb der kanonischen Sammlungen ist die Vollständigkeit nicht durch einfache lokale Bedingungen (wie die der Basenfolgen allein) charakterisierbar.

Zusammenfassend beweist Zabolotskii, dass das Problem der Existenz eindeutiger Darstellungen ganzer Zahlen durch additive Systeme von einer solchen algorithmischen Komplexität ist, dass es im Allgemeinen nicht lösbar ist, und verknüpft dies elegant mit den tiefsten offenen Fragen der Mathematik.