Proving Properties of $φ$-Representations with the Walnut Theorem-Prover

Dieser Artikel stellt eine neue, rechnerisch direkte Methode vor, die mit dem Walnut-Theorembeweiser klassische und neue Ergebnisse über $\phi$-Darstellungen, einschließlich der Arbeiten von Dekking und Van Loon, einheitlich und ohne Induktion beweist.

Das Wesentliche

Der magische Spiegel der Zahlen: Wie ein Computer-Tool die Geheimnisse der Goldenen Zahl entschlüsselt

Stellen Sie sich vor, Zahlen sind nicht nur trockene Symbole, sondern haben eine eigene Sprache. Normalerweise schreiben wir Zahlen im Zehnersystem (1, 2, 3...), weil wir zehn Finger haben. Aber was wäre, wenn wir eine Welt hätten, in der die Naturgesetze von der Goldenen Zahl (genannt $\phi$, gesprochen "Phi", etwa 1,618) bestimmt werden?

In dieser Welt sieht die Zahl 2 nicht wie "2" aus, sondern wie eine seltsame Kette von Nullen und Einsen: 10.01. Das ist die $\phi$-Darstellung.

Der Autor dieses Papers, Jeffrey Shallit, hat sich gefragt: "Wie können wir diese seltsamen Zahlenketten verstehen, prüfen und vorhersagen, ohne stundenlang mühsam zu rechnen?" Seine Antwort ist ein digitales Werkzeug namens Walnut.

1. Das Werkzeug: Walnut als der "Super-Detektiv"

Stellen Sie sich Walnut wie einen extrem cleveren, aber sehr geduldigen Detektiv vor. Dieser Detektiv ist ein Computerprogramm, das nicht rechnet, sondern logische Muster sucht.

• Das Problem: Früher mussten Mathematiker wie Frougny und Sakarovitch riesige, komplizierte Maschinen (sogenannte "Automaten") bauen, um zu prüfen, ob eine Zahl in dieser $\phi$-Sprache korrekt ist. Das war wie das Bauen eines riesigen Labyrinths aus Steinblöcken, um einen Weg zu finden.
• Die Lösung: Shallit hat Walnut benutzt. Er hat dem Detektiv einfach gesagt: "Suche nach Zahlen, die diese Regeln erfüllen." Und Zack! – Walnut hat das Labyrinth nicht aus Stein gebaut, sondern aus Lichtstrahlen. Er hat die Maschine automatisch entworfen, die genau das tut, was die alten Mathematiker mühsam von Hand konstruiert haben.

2. Die zwei Sprachen der Zahlen: Zeckendorf und Negafibonacci

Um die $\phi$-Sprache zu verstehen, braucht man zwei Übersetzer:

1. Zeckendorf-Sprache: Eine Art, Zahlen nur mit positiven Fibonacci-Zahlen (1, 1, 2, 3, 5, 8...) zu schreiben.
2. Negafibonacci-Sprache: Eine Version, die auch negative Fibonacci-Zahlen nutzt.

Stellen Sie sich vor, Sie wollen eine Summe von Geldmünzen zählen. Normalerweise nutzen Sie nur positive Münzen. Aber manchmal ist es einfacher, auch "Schulden" (negative Münzen) zu nutzen, um die Rechnung zu vereinfachen. Walnut kann zwischen diesen beiden Sprachen fließend wechseln und sie in die $\phi$-Sprache übersetzen.

3. Was hat der Detektiv gefunden? (Die Entdeckungen)

Sobald Walnut die Maschine gebaut hatte, konnte er sofort alte Rätsel lösen und neue finden. Hier sind die wichtigsten Entdeckungen, erklärt mit Metaphern:

• Der "Knopf-Drücker" für Beweise:
  Früher mussten Mathematiker Beweise führen, die wie ein langer, mühsamer Aufstieg einen steilen Berg hinauf waren (Induktion). Mit Walnut ist es, als hätte man einen Lift. Man drückt einen Knopf, und das Ergebnis kommt sofort heraus. Shallit hat damit Beweise für alte Theoreme gefunden, die in Minuten statt in Jahren erledigt waren.

• Die "Spiegel-Bilder" (Palindrome):
  Gibt es Zahlen, die in dieser $\phi$-Sprache wie Spiegelbilder aussehen? Zum Beispiel 101.101?
  Der Detektiv hat eine Liste erstellt, welche Zahlen das sind. Es ist wie ein Verzeichnis von Zahlen, die sich selbst im Spiegel betrachten können.

• Die "Turm-Höhen" (Länge der Zahlen):
  Wie viele Stellen hat eine Zahl in dieser Sprache? Shallit hat herausgefunden, dass die Länge der Zahl nicht wild wächst, sondern einem sehr strengen, fast rhythmischen Muster folgt – wie die Stufen einer Treppe, die nur bestimmte Höhen erlaubt.

• Die "Knott-Expansions" (Die vielen Gesichter einer Zahl):
  Eine Zahl kann auf viele verschiedene Arten in $\phi$ geschrieben werden, wenn man die strengen Regeln etwas lockert (wie wenn man 10.01 auch als 10.0011 schreiben darf).
  Dekking und Van Loon (andere Mathematiker) hatten eine komplizierte Formel entwickelt, um zu zählen, wie viele dieser "Gesichter" eine Zahl hat. Shallit hat mit Walnut gezeigt: "Eigentlich ist das gar nicht kompliziert." Er hat die Formel automatisch abgeleitet und sogar neue, einfachere Formeln gefunden.

4. Warum ist das wichtig?

Dieser Artikel ist nicht nur eine Sammlung von Formeln. Er ist eine Demonstration einer neuen Art zu denken.

Stellen Sie sich vor, Sie wollen herausfinden, ob ein bestimmter Schlüssel in ein Schloss passt.

• Der alte Weg: Sie bauen einen riesigen Schlüsselkasten, probieren jeden Schlüssel einzeln aus und schreiben ein Tagebuch darüber.
• Der Walnut-Weg: Sie geben dem Computer die Form des Schlosses und des Schlüssels. Der Computer sagt Ihnen sofort: "Ja, das passt" oder "Nein, das passt nicht", und zeigt Ihnen sogar, wie der perfekte Schlüssel aussieht.

Shallit zeigt uns, dass wir für viele mathematische Probleme nicht mehr so viel "schweres Denken" im Sinne von mühsamen Berechnungen brauchen müssen. Stattdessen können wir die Logik so formulieren, dass ein Computer die Arbeit der Mustererkennung übernimmt.

Fazit

Jeffrey Shallit hat mit diesem Papier gezeigt, dass die Welt der $\phi$-Zahlen (die goldenen Zahlen) voller versteckter Ordnung ist. Mit Hilfe seines "Super-Detektivs" Walnut konnte er alte Geheimnisse lüften, neue Muster entdecken und beweisen, dass Mathematik manchmal weniger wie schweres Kopfrechnen und mehr wie das Entdecken von Mustern in einem riesigen, digitalen Teppich aussieht.

Es ist ein Beweis dafür, dass Technologie und Mathematik zusammenarbeiten können, um die Schönheit der Zahlen für alle sichtbar zu machen – ganz ohne mühsames "Induktions-Graben".

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Proving Properties of φ-Representations with the Walnut Theorem-Prover" von Jeffrey Shallit auf Deutsch.

1. Problemstellung und Motivation

Das Paper befasst sich mit der φ-Repräsentation (auch Basis-φ-Entwicklung genannt) von Zahlen, wobei $\phi = \frac{1+\sqrt{5}}{2}$ der goldene Schnitt ist. Jede nicht-negative reelle Zahl $z$ kann als Summe $z = \sum a_i \phi^i$ mit $a_i \in \{0, 1\}$ dargestellt werden. Eine kanonische Darstellung ist eindeutig, wenn die Bedingung $a_i a_{i+1} \neq 1$ (kein Vorkommen von „11") erfüllt ist und keine unendliche Folge $010101\dots$ am Ende auftritt.

Ein klassisches Ergebnis von Frougny und Sakarovitch besagt, dass die kanonische φ-Repräsentation einer nicht-negativen ganzen Zahl $n$ durch einen endlichen Automaten berechnet werden kann. Dieser Automat akzeptiert drei parallele Eingaben:

1. Die Zahl $n$ im Zeckendorf-System (Darstellung als Summe von Fibonacci-Zahlen ohne aufeinanderfolgende 1en).
2. Den linken Teil der φ-Repräsentation ($x$).
3. Den rechten Teil der φ-Repräsentation ($y$), wobei $y$ umgekehrt ($y^R$) eingelesen wird („folded representation").

Das Problem bestand darin, dass der ursprüngliche Beweis von Frougny und Sakarovitch schwer lesbar war und der Automat nicht explizit konstruiert wurde. Zudem waren viele Eigenschaften dieser Darstellungen (z. B. über Palindrome, Summen der Ziffern oder spezielle Erweiterungen wie „Knott-Expansionen") bisher nur durch komplexe, induktive Beweise zugänglich.

2. Methodik: Der Walnut-Theorem-Prover

Die zentrale Methodik dieses Papers ist die Anwendung des Walnut-Tools, einer Software zur automatischen Beweissführung für Eigenschaften automatischer Folgen und endlicher Automaten.

• Logischer Ansatz: Shallit formuliert die mathematischen Eigenschaften der φ-Repräsentation als Aussagen in der Prädikatenlogik erster Stufe (First-Order Logic).
• Automatische Konstruktion: Walnut nutzt ein Entscheidungsverfahren für eine Erweiterung der Presburger-Arithmetik. Wenn eine logische Formel mit freien Variablen (z. B. $n, x, y$) wahr ist, berechnet Walnut automatisch einen endlichen Automaten, der genau die Werte annimmt, die die Formel erfüllen.
• Komponentenbasierte Konstruktion: Der Autor baut den Frougny-Sakarovitch-Automaten modular aus kleineren, leicht verständlichen Teilautomaten auf:
  • Normalizer: Konvertiert beliebige Binärstrings in kanonische Zeckendorf- oder NegaFibonacci-Darstellungen.
  • Shifters: Verschiebt Darstellungen nach links oder rechts (entspricht Multiplikation mit $\phi$ bzw. $\phi^{-1}$).
  • Bit-Extraktion: Isoliert bestimmte Bits (z. B. das letzte Bit).
  • Konverter: Wandelt zwischen Zeckendorf- und NegaFibonacci-Systemen um.
• Lineare Darstellungen: Für Funktionen wie die Summe der Ziffern oder die Anzahl bestimmter Darstellungen werden lineare Darstellungen (Tripel aus Vektor, Matrix-Morphismus und Vektor) berechnet, die eine effiziente Berechnung ($O(\log n)$) und Analyse erlauben.

3. Schlüsselbeiträge

1. Explizite Konstruktion des Frougny-Sakarovitch-Automaten: Shallit zeigt, wie der Automat mit nur 116 Zuständen (bzw. 39 Zuständen für die kanonische Variante) direkt aus den mathematischen Formeln abgeleitet werden kann. Dies macht das theoretische Ergebnis praktisch nutzbar.
2. Vereinheitlichung und Automatisierung von Beweisen: Das Paper demonstriert, dass viele bekannte Ergebnisse der Literatur (insbesondere von Dekking und Van Loon) nicht durch mühsame Induktion, sondern durch einfaches „Abfragen" des Automaten in Walnut bewiesen werden können.
3. Neue Ergebnisse: Durch die automatische Analyse werden zahlreiche neue Sätze und Sequenzen entdeckt, die zuvor unbekannt waren.

4. Wichtige Ergebnisse

Das Paper liefert Beweise und neue Erkenntnisse in folgenden Bereichen:

• Spezielle Zahlenfolgen:
  • Exakte Formeln für die φ-Repräsentation von Fibonacci-Zahlen ($F_n$) und Lucas-Zahlen ($L_n$) wurden bestätigt und verallgemeinert.
  • Es wurde gezeigt, dass die Länge der linken und rechten Teile der Darstellung periodische Muster aufweisen.
• Ziffernsummen:
  • Ein Beweis für eine Vermutung von Dale Gerdemann (2012): Die Summe der Ziffern in der Zeckendorf-Darstellung ist immer kleiner oder gleich der Summe der Ziffern in der kanonischen φ-Darstellung.
  • Berechnung der linearen Darstellung für die Summe der Bits des linken und rechten Teils der φ-Repräsentation.
• Spezielle Darstellungsformen:
  • Knott-Expansionen: Darstellungen, die nicht mit „011" enden. Der Automat erlaubt die Zählung dieser Darstellungen ($Tot_\kappa(n)$) und liefert geschlossene Formeln für Fibonacci- und Lucas-Zahlen.
  • Natürliche Expansionen: Wo die Länge des rechten Teils gleich der Länge des linken Teils ist.
  • DVL-Expansionen: Eine von Dekking und Van Loon eingeführte Variante, die „11" erlaubt, aber nur unter spezifischen Bedingungen.
• Strukturelle Eigenschaften:
  • Charakterisierung von Palindromen und Anti-Palindromen in φ-Repräsentationen.
  • Untersuchung von „vertikalen Läufen" von Einsen (wie lange eine 1 an einer bestimmten Position $i$ in aufeinanderfolgenden Zahlen $n, n+1, \dots$ steht).
  • Verbindung der Bits der φ-Repräsentation zu Sturmischen Folgen und Lucas-Darstellungen.
• Algebraische Zahlen: Erweiterung der Methode auf algebraische Zahlen der Form $m\phi + n$ (mit $m, n \in \mathbb{Z}$), um deren φ-Repräsentation zu berechnen.

5. Signifikanz und Fazit

Die Bedeutung dieses Papers liegt in der Demonstration der Kraft automatischer Beweissysteme in der Zahlentheorie und Kombinatorik.

• Effizienz: Komplexe Probleme, die zuvor Jahre an manueller Arbeit oder komplizierte Induktionsbeweise erforderten, können nun in wenigen Zeilen Walnut-Code gelöst werden.
• Reproduzierbarkeit: Die Ergebnisse sind nicht nur bewiesen, sondern die zugrundeliegenden Automaten und linearen Darstellungen sind explizit verfügbar und überprüfbar.
• Erweiterbarkeit: Die Methode ist nicht auf $\phi$ beschränkt, sondern kann prinzipiell auf alle quadratischen Pisot-Zahlen angewendet werden.
• Neue Entdeckungen: Der „automatische" Ansatz hat zu neuen Sequenzen in der OEIS (On-Line Encyclopedia of Integer Sequences) und neuen mathematischen Vermutungen geführt, die ohne dieses Werkzeug schwer zu finden gewesen wären.

Zusammenfassend stellt das Paper einen Paradigmenwechsel dar: Statt mathematische Eigenschaften durch manuelle Analyse zu beweisen, werden sie durch die Konstruktion und Analyse endlicher Automaten, die durch logische Formeln definiert sind, „automatisch" abgeleitet. Dies macht die Theorie der φ-Repräsentationen zugänglicher und erweiterbar.