Die Tribonacci-Konstante und endliche Automaten

Grundinformationen

• Papier-ID: 2510.10834
• Titel: Die Tribonacci-Konstante und endliche Automaten
• Autor: Jeffrey Shallit (University of Waterloo)
• Klassifizierung: cs.FL cs.DM math.NT
• Veröffentlichungsdatum: 21. Oktober 2025 (arXiv-Preprint)
• Papierlink: https://arxiv.org/abs/2510.10834

Zusammenfassung

Dieses Papier beweist, dass es keinen Automaten gibt, der die Tribonacci-Darstellungen von n und x parallel akzeptiert, wobei ψ = 1.839··· die Tribonacci-Konstante ist und x = ⌊nψ⌋. Ähnlich gibt es keinen Tribonacci-Automaten, der die charakteristische Sturmian-Sequenz mit Steigung ψ-1 erzeugen kann.

Forschungshintergrund und Motivation

Problemhintergrund

1. Erfolgreiche Fälle im Fibonacci-Fall: Für das Goldene Verhältnis φ = (1+√5)/2 ist die Sequenz (⌊φn⌋)_{n≥0} Fibonacci-synchron, d.h. es existiert ein endlicher Automat, der die Zeckendorf-Darstellungen von n und x parallel akzeptiert, genau dann wenn x = ⌊φn⌋.
2. Natürliche Verallgemeinerungsfrage: Existieren ähnliche Eigenschaften auch für Verallgemeinerungen der Fibonacci-Zahlen (wie Tribonacci-Zahlen)?
3. Schnittstelle zwischen Zahlentheorie und Automatentheorie: Dieses Problem betrifft die tiefe Verbindung zwischen Eigenschaften irrationaler Zahlen in der Zahlentheorie und der Theorie endlicher Automaten in der theoretischen Informatik.

Forschungsmotivation

• Erforschung, ob die Verallgemeinerung von Rekurrenzen zweiter Ordnung (Fibonacci) zu Rekurrenzen dritter Ordnung (Tribonacci) die Erkennbarkeit durch Automaten bewahrt
• Verständnis der grundlegenden Unterschiede zwischen Rekurrenzsequenzen höherer Ordnung und endlichen Automaten
• Bereitstellung theoretischer Grundlagen für verwandte logische Theorien und Entscheidungsprobleme

Kernbeiträge

1. Hauptnegatives Ergebnis: Beweis, dass die Sequenz (⌊ψn⌋)_{n≥0} nicht Tribonacci-synchron ist, wobei ψ die Tribonacci-Konstante ist
2. Nicht-Automatizität von Sturmian-Sequenzen: Beweis, dass die entsprechende charakteristische Sturmian-Sequenz nicht Tribonacci-automatisch ist
3. Auswirkungen auf die Logiktheorie: Beweis, dass die Abbildung n → ⌊ψn⌋ nicht in der Theorie erster Ordnung ⟨N,+,V'(n)⟩ ausdrückbar ist
4. Tiefe mathematische Einsichten: Enthüllung, dass der grundlegende Unterschied zwischen zweiter und dritter Ordnung in der fehlenden Periodizität liegt

Methodische Erläuterung

Aufgabendefinition

Untersuchung zweier Klassen von Automatenproblemen:

1. Synchrone Automaten: Akzeptieren Funktionen f: N → N, wobei n und x (in Tribonacci-Darstellung) parallel eingegeben werden, und akzeptieren genau dann, wenn x = f(n)
2. Ausgabeautomaten (DFAO): Berechnen Sequenzen (a_n)_{n≥0}, wobei die Tribonacci-Darstellung von n eingegeben wird und a_n ausgegeben wird

Kernmathematische Konstruktion

Eigenschaften der Tribonacci-Zahlen

• Rekurrenzrelation: T_i = T_ + T_ + T_, mit Anfangswerten T_0 = 0, T_1 = 1, T_2 = 1
• Geschlossene Form: T_n = c_1ψ^n + c_2α^n + c_3β^n
• Wobei ψ ≈ 1.839 die reelle Wurzel von X³ - X² - X - 1 ist, und α,β sind komplex konjugierte Wurzeln

Schlüsseltechnische Konstruktion

Definition:

• a(n) = ⌊ψn⌋
• b(n) = ⌊(ψ-1)(n+2)⌋ - ⌊(ψ-1)(n+1)⌋
• c(n) = ⌊ψ(n+1)⌋ - ⌊ψn⌋

Beweisstrategien

Hauptbeweisidee

1. Reduktionsargument: Beweis, dass wenn a(n) synchron ist, dann b(n) automatisch ist
2. Zustandsunterscheidung: Konstruktion unendlich vieler unterscheidbarer Automatenzustände
3. Anwendung des Myhill-Nerode-Theorems: Verwendung der Zustandsunterscheidung zum Beweis der Nichtexistenz eines endlichen Automaten

Kritische mathematische Analyse

Verwendung der Eigenschaften von Bruchteilen:

{ψT_n} = {2Re c_2(ψ-α)α^n}

Wobei:

• γ = arg c_2(ψ-α) = 2.536155···
• ζ = arg α = 4.10695···
• Der Wert von c(T_n) hängt von v(n) := γ + nζ mod 2π ab

Experimentelle Einrichtung

Theoretische Verifikationsmethoden

Dieses Papier ist hauptsächlich ein theoretischer Beweis mit folgenden Verifikationsmethoden:

1. Numerische Berechnung: Verifikation der exakten Werte von Koeffizienten und Parametern
2. Anwendung des Kronecker-Theorems: Beweis von Dichtheitseigenschaften
3. Verifikation der linearen Unabhängigkeit: Bestätigung, dass ζ und 2π über den rationalen Zahlen linear unabhängig sind

Berechnung kritischer Parameter

• |c_2(ψ-α)| = 0.608085···
• |α| = 0.73735···
• Verifikation, dass |2Re c_2(ψ-α)α^n| < 2-ψ für n ≥ 5 gilt

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

Vollständiger Beweis von Theorem 1

Beweis, dass:

1. Die Sequenz (a(n))_{n≥0} nicht Tribonacci-synchron ist
2. Die Sequenz (b(n))_{n≥0} nicht Tribonacci-automatisch ist

Konstruktiver Beweis der Zustandsunterscheidung

• Für alle i < j existiert ein k, so dass c(T_{i+k}) ≠ c(T_{j+k})
• Verwendung des Kronecker-Theorems zur Garantie unendlich vieler solcher k
• Erfolgreiche Konstruktion unendlich vieler unterscheidbarer Zustände

Logiktheoretische Ergebnisse

Theorem 2

Beweis, dass die Abbildung n → ⌊ψn⌋ nicht in der Theorie erster Ordnung ⟨N,+,V'(n)⟩ ausdrückbar ist, wobei V'(n) die kleinste Tribonacci-Zahl in der Tribonacci-Darstellung von n ist.

Verwandte Arbeiten

Bekannte Ergebnisse im Fibonacci-Fall

• Mousavi et al. und Hieronymi bewiesen unabhängig, dass n → ⌊φn⌋ in der entsprechenden Struktur ausdrückbar ist
• Khani und Zarei erhielten ähnliche Ergebnisse mit verschiedenen Methoden
• Ähnliche Eigenschaften gelten für beliebige quadratische irrationale Zahlen

Theorie der Zahlensysteme

• Zeckendorf-Darstellungstheorie
• Darstellungstheorie verallgemeinerter Fibonacci-Sequenzen
• Pisano-Zahlen-bezogene Zahlensysteme

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Grundlegende Unterschiede: Es existieren wesentliche Unterschiede zwischen dem Fibonacci- und dem Tribonacci-Fall
2. Fehlende Periodizität: Das Vorzeichen von F_{n+1} - φF_n ist periodisch, aber das Vorzeichen von T_{n+1} - ψT_n ist nicht periodisch
3. Näherungsergebnisse existieren: Obwohl exakte Ergebnisse unerreichbar sind, existieren Automaten-Näherungen mit Fehlern in ±1

Einschränkungen

1. Negative Ergebnisse: Hauptsächlich negative Ergebnisse ohne alternative Konstruktionsmethoden
2. Spezifisch für Tribonacci: Ergebnisse sind spezifisch für Rekurrenzen dritter Ordnung; höhere Ordnungen erfordern separate Analysen
3. Genauigkeit von Näherungsmethoden: Die Fehlergrenzen von Näherungs-Automaten könnten nicht präzise genug sein

Zukünftige Richtungen

1. Andere Pisano-Zahlen: Untersuchung von Zahlensystemen basierend auf anderen kubischen Pisano-Zahlen
2. Verallgemeinerung auf höhere Ordnungen: Betrachtung von k-ter Ordnung Rekurrenzsequenzen
3. Näherungsalgorithmen: Verbesserung der Genauigkeit und Effizienz von Näherungs-Automaten

Tiefe Bewertung

Stärken

1. Theoretische Tiefe: Enthüllung des grundlegenden Einflusses der Rekurrenzordnung auf die Automatenerkennung
2. Beweistechniken: Geschickte Kombination von komplexer Analysis, Zahlentheorie und Automatentheorie
3. Vollständigkeit: Nicht nur Hauptergebnisse bewiesen, sondern auch Auswirkungen auf die Logiktheorie analysiert
4. Mathematische Strenge: Präzise und rigorose Beweise mit exakten Berechnungen

Schwächen

1. Mangel an Konstruktivität: Hauptsächlich negative Existenzergebnisse ohne positive Konstruktionen
2. Begrenzte Anwendbarkeit: Ergebnisse sind hauptsächlich theoretischer Natur mit begrenztem praktischem Wert
3. Verallgemeinerbarkeit: Die Verallgemeinerbarkeit der Methoden auf andere ähnliche Probleme bedarf weiterer Verifikation

Einflussfaktor

1. Theoretischer Beitrag: Wichtige Einsichten für die Schnittstelle zwischen Automatentheorie und Zahlentheorie
2. Methodologischer Wert: Beweistechniken sind für verwandte Probleme wertvoll
3. Grenzbestimmung: Klare Bestimmung der Anwendbarkeitsgrenzen von Automatenmethoden

Anwendungsszenarien

1. Theoretische Forschung: Zahlentheorie, Automatentheorie, Theorie formaler Sprachen
2. Algorithmisches Design: Entwurf numerischer Algorithmen, die Automatenbeschränkungen berücksichtigen
3. Komplexitätstheorie: Untersuchung verwandter Entscheidungsprobleme

Literaturverzeichnis

Das Papier zitiert 17 wichtige Arbeiten, die folgende Bereiche abdecken:

• Klassische Lehrbücher der Automatentheorie (Hopcroft & Ullman)
• Bahnbrechende Arbeiten zu Fibonacci-Automaten (Bruyère et al.)
• Zahlentheoretische Grundlagen (Hardy & Wright)
• Verwandte aktuelle Forschung (Mousavi et al., Hieronymi et al.)

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Papier, das durch rigorose mathematische Beweise die grundlegenden Unterschiede zwischen dem Fibonacci- und dem Tribonacci-Fall in Bezug auf die Automatenerkennung enthüllt. Obwohl es hauptsächlich negative Ergebnisse sind, leistet es wichtige Beiträge zur theoretischen Entwicklung des Feldes, insbesondere zum Verständnis der Beziehung zwischen Rekurrenzsequenzen und endlichen Automaten von tiefgreifender Bedeutung.