Cobham's theorem for the Gaussian integers

Technisches Resümee: Cobhams Theorem für die Gaußschen Zahlen

Problemstellung
Das Cobhamsche Theorem ist ein grundlegendes Resultat der Automatentheorie und Zahlentheorie. Es besagt, dass eine Folge natürlicher Zahlen genau dann sowohl $k$-automatisch als auch $\ell$-automatisch ist (wobei $k$ und $\ell$ multiplativ unabhängige ganze Zahlen sind), wenn die Folge schließlich periodisch ist. Während dieses Theorem in verschiedene logische und dynamische Kontexte verallgemeinert wurde, blieb eine signifikante Lücke bei seiner Erweiterung von den ganzen Zahlen $\mathbb{Z}$ auf euklidische Körper, spezifisch die Gaußschen Zahlen $\mathbb{Z}[i]$.

Vorherige Arbeiten von Hansel und Safer befassten sich mit Numerationssystemen mit der Basis $\alpha = -m + i$ (wobei $m \ge 1$) und nicht-negativen ganzzahligen Ziffernmenge. Sie zeigten, dass, falls eine Teilmenge $S \subset \mathbb{Z}[i]$ durch zwei solche Basen erkennbar ist, die Menge syndetisch ist. Sie vermuteten, dass eine solche Menge schließlich periodisch sein muss (d. h. invariant unter Translation durch zwei $\mathbb{Z}$-linear unabhängige Vektoren außerhalb einer endlichen Menge). Ihr Beweis stützte sich jedoch auf die Vier-Exponentialen-Vermutung (Four Exponentials Conjecture), eine tiefe und unbewiesene Hypothese der analytischen Zahlentheorie, was die Vermutung ungeklärt ließ.

Methodik
Die Autoren liefern einen Beweis für das Cobhamsche Theorem für Gaußsche Zahlen, der nicht auf der Vier-Exponentialen-Vermutung beruht. Ihr Ansatz verallgemeinert das Theorem auf die größtmögliche Familie von Gaußschen Numerationen (jede endliche erzeugende Ziffernmenge) und entfernt die Abhängigkeit von tiefer analytischer Zahlentheorie.

Die Kernmethodik umfasst:

1. Dirichlet-Approximation in $\mathbb{Z}[i]$: Anstatt sich auf die Dichte der multiplikativen Gruppe $\langle \alpha, \beta \rangle$ in $\mathbb{C}$ zu verlassen (was die Vier-Exponentialen-Vermutung erfordert), nutzen die Autoren ein schwächeres Resultat: Dass $1$ kein isolierter Punkt in der multiplikativen Gruppe ist, die von zwei multiplativ unabhängigen Gaußschen ganzen Zahlen erzeugt wird. Dies wird über Lemma 3 etabliert, welches beweist, dass, falls $1$ isoliert wäre, die Gruppe diskret wäre, was multiplikative Abhängigkeit implizieren würde.
2. Pumping-Lemma und Rückkehrzahlen: Die Autoren analysieren die Struktur endlicher Zustandsautomaten (DFAOs), die auf Gaußschen ganzen Expansionen operieren. Sie definieren „Rückkehrzahlen“ (return numbers) zu spezifischen Zuständen des Automaten. Durch Anwendung des Satzes von van der Waerden auf die Zustände der Automaten identifizieren sie arithmetische Progressionen von Indizes, die Rückkehrzahlen entsprechen.
3. Kolliniaritätsanalyse: Ein kritischer Schritt ist Lemma 14, das zeigt, dass, falls eine Sequenz von Rückkehrzahlen auf einer Geraden liegt (kolliniar ist), die Basis eine Wurzel einer ganzen Zahl sein muss. Folglich müssen die Rückkehrzahlen, falls die Basis keine Wurzel einer ganzen Zahl ist, nicht-kolliniar sein. Dies ermöglicht die Konstruktion von zwei $\mathbb{Z}$-linear unabhängigen Perioden.
4. Perioden-Propagation: Unter Verwendung einer Version des Fine-Wilf-Theorems, angepasst für Gaußsche Zahlen (Lemmata 18 und 19), zeigen die Autoren, dass lokale Periodizität (Schritt-Periodizität) auf überlappenden Kugeln auf globale Periodizität propagiert werden kann. Sie konstruieren eine Überdeckung von $\mathbb{Z}[i]$ durch Kugeln, in denen die Konfiguration spezifische Perioden aufweist, die aus den nicht-kolliniaren Rückkehrzahlen abgeleitet sind.

Wesentliche Beiträge und Ergebnisse
Das primäre Resultat ist Theorem 1, welches besagt:

Sei $\alpha$ und $\beta$ zwei multiplativ unabhängige Gaußsche ganze Zahlen mit $|\alpha|, |\beta| > 1$. Wenn eine von $\alpha$ oder $\beta$ keine Wurzel einer ganzen Zahl ist, dann ist eine Konfiguration $(a_z)_{z \in \mathbb{Z}[i]}$ genau dann $\alpha$- und $\beta$-automatisch, wenn sie schließlich periodisch ist.

Wesentliche technische Erkenntnisse umfassen:

• Lösung der Hansel-und-Safer-Vermutung: Das Paper beweist die Vermutung, dass Mengen, die durch Basen der Form $-m+i$ erkennbar sind, schließlich periodisch sind. Da $-m+i$ (gemäß Niven's Theorem) für $m > 1$ niemals eine Wurzel einer ganzen Zahl ist, ist die Bedingung von Theorem 1 erfüllt.
• Notwendigkeit der Bedingung: Die Autoren zeigen, dass die Bedingung „eine Basis ist keine Wurzel einer ganzen Zahl“ scharf ist. Falls beide Basen Wurzeln ganzer Zahlen sind, können nicht-schließlich periodische Konfigurationen existieren (z. B. ist die Charakteristische Funktion von $\mathbb{N}$ $\alpha$-automatisch, wenn $\alpha$ eine Wurzel einer ganzen Zahl ist).
• Verallgemeinerung von Numerationssystemen: Der Beweis gilt für jede endliche Ziffernmenge $D$, die ein Numerationssystem erzeugt, nicht nur für die „natürlichen“ nicht-negativen ganzzahligen Ziffernmengen, die von Hansel und Safer betrachtet wurden.
• Korollar zur Konjugation: Das Paper stellt fest, dass, falls eine Menge $U \subset \mathbb{Z}[i]$ $\beta$-automatisch ist und gleich ihrer komplexen Konjugierten ist ($U = \bar{U}$), und nicht schließlich periodisch ist, dann $\beta$ eine Wurzel einer ganzen Zahl sein muss.

Bedeutung
Das Paper beansprucht, die Erweiterung des Cobhamschen Theorems auf die Gaußschen Zahlen ohne Rückgriff auf unbewiesene analytische Vermutungen geklärt zu haben. Durch den Nachweis, dass das Resultat auf elementaren Eigenschaften von Automaten und der Geometrie der Gaußschen Zahlen (speziell der Nicht-Isolation von $1$ in der multiplikativen Gruppe) basiert, ebnen die Autoren „den Weg für Cobham für allgemeine Zahlringe“.

Die Arbeit verallgemeinert das Cobham-Semenov-Theorem auf Gaußsche Numerationen. Sie verbindet sich auch mit der Arbeit von Cabezas und Petite über Substitutionen mit konstanter Form, was impliziert, dass nicht-triviale Konfigurationen, die durch Gaußsche Basen (die keine Wurzeln ganzer Zahlen sind) erzeugt werden, nicht durch Standard-$(k, k)$-automatische Konfigurationen repliziert werden können. Die Autoren merken an, dass dies zwar ein erster Schritt ist, die Erweiterung auf andere Ringe der ganzen Zahlen (wie $\mathbb{Z}[\zeta]$ oder quadratische Eisenzahlringe) jedoch eine natürliche Richtung für zukünftige Untersuchungen darstellt.