🔢 mathematics

Beatty Sequences for a Quadratic Irrational: Decidability and Applications

Die Arbeit zeigt, dass inhomogene Beatty-Folgen für quadratische Irrationalzahlen synchronisiert sind, was zu einem einfachen Beweis für die Entscheidbarkeit ihrer additiven Theorie führt und die Lösung offener Probleme sowie die Charakterisierung bestimmter Folgen ermöglicht.

Ursprüngliche Autoren: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Veröffentlicht 2026-04-03

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die magische Brücke zwischen Zahlen und Automaten

Stellen Sie sich vor, Sie haben einen riesigen, unendlichen Zug von Zahlen, der sich durch die Natur zieht. In der Mathematik gibt es eine spezielle Art, solche Züge zu bauen, die Beatty-Folgen genannt werden. Man nimmt eine Zahl (sagen wir $\alpha$ , wie die berühmte „Goldene Zahl" $\phi$ ), multipliziert sie mit 1, 2, 3, 4... und rundet das Ergebnis immer ab.

Beispiel: Wenn $\alpha \approx 1,618$ ist, dann ist der Zug: 1, 3, 4, 6, 8, 9, 11...

Die Autoren dieser Arbeit haben sich gefragt: Können wir diese Züge mit einem einfachen Roboter verstehen?

1. Der Roboter und die „Ostrowski-Sprache"

Normalerweise sprechen wir Zahlen in unserem Dezimalsystem (1, 2, 3...). Aber für diese speziellen Züge ist das wie der Versuch, ein komplexes Gedicht in einer Sprache zu lesen, die man nicht beherrscht.

Die Autoren nutzen eine spezielle Sprache, die Ostrowski-Darstellung.

Die Analogie: Stellen Sie sich vor, unsere normalen Zahlen sind wie ein riesiger Stapel loser Ziegelsteine. Die Ostrowski-Darstellung ist wie ein fertiges, perfekt gefügte Mauerwerk, das speziell für die „Goldene Zahl" oder andere quadratische Irrationalzahlen gebaut wurde.
In dieser Sprache kann ein einfacher Roboter (ein endlicher Automat) die Zahlen lesen. Ein Automat ist wie ein kleiner Computer mit einem begrenzten Gedächtnis, der nur „Ja" oder „Nein" sagen kann, wenn er eine Zahl sieht.

Das Hauptergebnis der Arbeit ist: Wenn die Zahl $\alpha$ eine „quadratische Irrationalzahl" ist (eine Zahl, die man mit Wurzeln wie $\sqrt{2}$ oder $\sqrt{5}$ beschreiben kann), dann gibt es einen solchen Roboter, der sofort erkennt, ob eine Zahl $y$ zu dem Zug gehört, der durch $n$ erzeugt wird.

2. Die Synchronisation: Ein Tanz auf zwei Beinen

Der Begriff „synchronisiert" in der Arbeit klingt kompliziert, ist aber eigentlich sehr schön.

Die Metapher: Stellen Sie sich zwei Tänzer vor. Der eine tanzt die Schritte $n$ (1, 2, 3...), der andere tanzt die Schritte $y$ (die Ergebnisse des Zugs). Normalerweise sind diese Tänzer nicht synchron. Aber die Autoren zeigen, dass man für diese speziellen Zahlen einen Tanzmeister (den Automaten) bauen kann, der beide Tänzer gleichzeitig beobachtet.
Wenn der Tanzmeister sieht, dass $n$ und $y$ perfekt aufeinander abgestimmt sind (also $y = \lfloor n\alpha + \beta \rfloor$ ), klatscht er in die Hände („Akzeptiert"). Wenn nicht, bleibt er stumm.
Das Tolle ist: Dieser Tanzmeister braucht kein riesiges Gehirn. Er ist ein einfacher Automat, der nur ein paar Regeln befolgt.

3. Warum ist das so wichtig? (Die Entschlüsselung)

Früher war es oft unmöglich zu beweisen, ob bestimmte Eigenschaften dieser Zahlenfolgen wahr oder falsch sind. Es war wie ein Labyrinth ohne Ausgang.

Das neue Werkzeug: Da wir jetzt wissen, dass ein einfacher Automat diese Folgen „lesen" kann, können wir Logik anwenden. Wir können Fragen stellen wie: „Gibt es eine Zahl, die sich als Summe von drei Zahlen aus diesem Zug schreiben lässt?"
Die Entscheidungsmaschine: Die Autoren haben gezeigt, dass man für solche Fragen einen Algorithmus (eine Rechenregel) bauen kann, der immer eine Antwort findet: „Wahr" oder „Falsch". Es gibt keine Rätsel mehr, die unlösbar sind.
Walnut: Sie haben dieses Werkzeug in einer kostenlosen Software namens Walnut implementiert. Man kann dort einfach eine Frage auf Deutsch (oder Mathesprache) eingeben, und der Computer löst das Rätsel in Sekunden.

4. Was haben sie damit gelöst? (Die Anwendungen)

Mit diesem neuen „Roboter-Auge" haben sie alte, verstaubte Probleme gelöst, die andere Mathematiker jahrelang nicht knacken konnten:

Das Additions-Problem: Können wir jede große Zahl als Summe von zwei (oder drei, oder vier...) Zahlen aus dem Zug schreiben?
- Beispiel: Kann man jede Zahl größer als 12 als Summe von zwei Zahlen aus dem Zug $\lfloor n\sqrt{2} \rfloor$ schreiben? Der Roboter sagt: „Ja!"
Die Reble-Vermutungen: Ein Hobby-Mathematiker namens Don Reble hatte Vermutungen über Muster in diesen Folgen aufgestellt. Die Autoren haben diese mit dem Computer in weniger als einer Sekunde bewiesen.
Grahams Frage: Gibt es eine Gruppe von Zügen, die den gesamten Zahlenraum lückenlos abdecken, ohne sich zu überschneiden? Auch das können sie jetzt für bestimmte Zahlen entscheiden.
Geheimnisse des OEIS: Sie haben die „DNA" von mehreren Zahlenfolgen aus der Online-Enzyklopädie der ganzen Zahlen (OEIS) entschlüsselt und gezeigt, wie sie wirklich funktionieren.

5. Das große Fazit

Die Autoren haben eine Brücke gebaut zwischen zwei Welten:

Der Welt der Zahlenfolgen (die oft chaotisch und unvorhersehbar wirken).
Der Welt der Automaten (die strikt, logisch und berechenbar sind).

Die einfache Botschaft:
Wenn eine Zahl eine bestimmte Art von „Wurzel" hat (quadratisch irrational), dann ist ihre Zahlenfolge nicht chaotisch. Sie folgt einer perfekten, maschinenlesbaren Logik. Wir können diese Folgen nicht nur verstehen, sondern auch beweisen, was mit ihnen passiert, indem wir sie einfach einem kleinen Computer-Roboter vorlegen.

Es ist, als hätten sie für ein komplexes, unendliches Musikstück eine Partitur gefunden, die so einfach ist, dass ein Roboterklavier es perfekt spielen und sogar vorhersagen kann, welche Note als Nächstes kommt.

1. Problemstellung

Das Paper adressiert die Frage der Entscheidbarkeit (Decidability) der ersten Ordnungstheorie für inhomogene Beatty-Folgen, die durch quadratische Irrationalzahlen definiert sind.

Beatty-Folgen: Eine inhomogene Beatty-Folge ist definiert als die Folge $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ , wobei $\alpha$ und $\beta$ reelle Zahlen sind.
Der Kontext: Es ist bekannt, dass die Addition in bestimmten numerischen Systemen (wie der Fibonacci-Darstellung oder dem Ostrowski-System für quadratische Irrationalzahlen) durch endliche Automaten erkannt werden kann.
Das offene Problem: Während die Entscheidbarkeit für spezifische Fälle (wie den Goldenen Schnitt) bereits bekannt war, fehlte eine allgemeine Methode, um zu zeigen, dass die Theorie für beliebige quadratische Irrationalzahlen $\alpha, \beta$ (die im selben quadratischen Körper liegen) entscheidbar ist. Zudem wurden offene Probleme bezüglich additiver Basen, monochromatischer arithmetischer Progressionen und spezifischer OEIS-Folgen (On-Line Encyclopedia of Integer Sequences) nicht vollständig gelöst.

Das zentrale Ziel ist es, zu beweisen, dass die Abbildung $n \mapsto \lfloor n\alpha + \beta \rfloor$ synchronisiert ist, wenn $\alpha$ und $\beta$ im selben quadratischen Körper liegen, und daraus die Entscheidbarkeit der ersten Ordnungstheorie abzuleiten.

2. Methodik

Die Autoren kombinieren Methoden aus der automatischen Sequenzentheorie, der Kettenbruchtheorie und der logischen Modellierung.

Ostrowski-Darstellung: Statt des üblichen Dezimalsystems nutzen die Autoren das Ostrowski- $\alpha$ -Zahlsystem. Für eine quadratische Irrationalzahl $\gamma$ (mit rein periodischem Kettenbruch von $1/\gamma$ ) kann jede natürliche Zahl eindeutig als Linearkombination der Konvergenten $q_i$ des Kettenbruchs von $\gamma$ dargestellt werden.
Synchronisierte Folgen: Eine Folge $(s_n)$ heißt synchronisiert, wenn ein endlicher Automat existiert, der die Darstellungen von $n$ und $s_n$ parallel liest und akzeptiert genau dann, wenn $s_n$ der korrekte Wert ist.
Hauptbeweistechnik (Lemma & Theorem):
- Die Autoren nutzen eine Matrix-Methode für Kettenbrüche, um eine Identität herzustellen (Theorem 5), die den Zusammenhang zwischen $\lfloor n\gamma \rfloor$ und der Ostrowski-Darstellung von $n$ herstellt.
- Sie zeigen, dass für $\alpha, \beta \in \mathbb{Q}(\gamma)$ die Funktion $\lfloor n\alpha + \beta \rfloor$ durch Kombination synchronisierter Funktionen (Addition, Multiplikation mit Konstanten, Division mit Rest) konstruiert werden kann.
- Da die Addition in Ostrowski-Systemen für quadratische Irrationalzahlen durch Automaten erkennbar ist (basierend auf Arbeiten von Hieronymi, Terry, Baranwal et al.), folgt, dass auch die Beatty-Folge synchronisiert ist.
Implementierung mit Walnut: Die theoretischen Ergebnisse werden mit dem Open-Source-Tool Walnut implementiert. Walnut ist ein Theorembeweiser, der die Entscheidbarkeit erster Ordnung für automatische Folgen nutzt. Die Autoren übersetzen mathematische Aussagen in erste Ordnunglogik (mit Quantoren $\forall, \exists$ ) und lassen Walnut die Existenz entsprechender Automaten prüfen oder die Wahrheit der Aussagen verifizieren.

3. Wichtige Beiträge und Ergebnisse

A. Haupttheorem (Theorem 9 & Korollar 11)

Synchronisation: Wenn $0 < \gamma < 1$ eine quadratische Irrationalzahl ist, deren Kehrwert einen rein periodischen Kettenbruch hat, und $\alpha, \beta \in \mathbb{Q}(\gamma)$ , dann ist die Folge $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ $\gamma$ -Ostrowski-synchronisiert.
Entscheidbarkeit: Als direkte Konsequenz ist die erste Ordnungstheorie der natürlichen Zahlen mit Addition und der Funktion $n \mapsto \lfloor n\alpha + \beta \rfloor$ entscheidbar. Dies liefert einen neuen, vergleichsweise einfachen Beweis für bekannte Ergebnisse und verallgemeinert sie auf beliebige quadratische Irrationalzahlen im selben Körper.

B. Anwendungen auf additive Zahlentheorie (Abschnitt 7)

Es wird gezeigt, dass es entscheidbar ist, ob eine solche Beatty-Folge eine additive Basis (oder asymptotische additive Basis) der Ordnung $r$ bildet. Das heißt, man kann algorithmisch bestimmen, ob jede hinreichend große natürliche Zahl als Summe von $r$ Elementen der Folge dargestellt werden kann.

C. Lösung offener Probleme (Abschnitte 8–13)

Die Autoren lösen mehrere lange offene Vermutungen und Probleme, indem sie diese in Walnut-Formeln übersetzen:

Reble-Vermutungen: Beweis von Vermutungen über das Vorkommen monochromatischer arithmetischer Progressionen der Länge 3 im Fibonacci-Wort (OEIS A189377–A189379).
Graham-Frage: Ein Spezialfall von Grahams Frage nach eventual covering families (ECF) für quadratische Irrationalzahlen wird als entscheidbar bewiesen.
Hildebrand-Li-Li-Xie-Folge: Eine explizite Charakterisierung einer Folge $\tilde{c}(n)$ wird gegeben, die die Differenz zu einer anderen Folge berechnet (OEIS A000201 etc.).
Kimberling-Swappage-Probleme: Alternative Beweise für Vermutungen von Clark Kimberling über „swappage"-Folgen (OEIS A141104–A141107) werden geliefert, die explizite Formeln für diese Folgen ableiten.
Wurzel-2-Folgen: Sie konstruieren Automaten für sieben OEIS-Folgen, die mit $\sqrt{2}$ zusammenhängen, und beweisen Vermutungen von Michel Dekking und Benedict Irwin.

D. Umkehrung (Theorem 28)

Die Autoren beweisen die Umkehrung von Theorem 9: Wenn eine Beatty-Folge $(\lfloor n\alpha + \beta \rfloor)$ $\gamma$ -Ostrowski-synchronisiert ist, dann müssen $\alpha$ und $\beta$ notwendigerweise im Körper $\mathbb{Q}(\gamma)$ liegen. Dies schließt die Lücke zwischen der strukturellen Eigenschaft der Synchronisation und der algebraischen Natur der Parameter.

4. Signifikanz und Bedeutung

Methodischer Durchbruch: Das Paper demonstriert die enorme Kraft der Kombination aus Ostrowski-Darstellungen und automatischer Logik. Es zeigt, dass komplexe zahlentheoretische Probleme, die früher nur durch manuelle, fehleranfällige Beweise angegangen werden konnten, nun durch algorithmische Verifikation gelöst werden können.
Praktische Anwendbarkeit: Die Ergebnisse sind nicht nur theoretisch, sondern praktisch nutzbar. Die Autoren zeigen, dass viele Theoreme über Beatty-Folgen in Sekunden mit Walnut bewiesen werden können. Dies etabliert einen neuen Standard für die Untersuchung solcher Folgen.
Schließung von Wissenslücken: Durch die Lösung mehrerer offener Probleme (Reble, Kimberling, Graham, Hildebrand et al.) wird das Verständnis der additiven Struktur und der kombinatorischen Eigenschaften von Beatty-Folgen erheblich vertieft.
Verallgemeinerung: Während frühere Arbeiten oft auf den Goldenen Schnitt beschränkt waren, bietet dieses Paper einen allgemeinen Rahmen für alle quadratischen Irrationalzahlen, was die Theorie der Sturmischen Wörter und Beatty-Folgen vereinheitlicht.

Zusammenfassend stellt das Paper einen Meilenstein in der computergestützten Zahlentheorie dar, der die Entscheidbarkeit von Theorien über Beatty-Folgen für quadratische Irrationalzahlen etabliert und eine Vielzahl konkreter, offener Probleme durch den Einsatz von endlichen Automaten und Logik löst.