2025-11-10T03:12:56.960652

Cloitre's Self-Generating Sequence

Shallit
In 2009 Benoit Cloitre introduced a certain self-generating sequence $$(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots,$$ with the property that the sum of the terms appearing in the $n$'th run equals twice the $n$'th term of the sequence. We give a connection between this sequence and the paperfolding sequence, and then prove Cloitre's conjecture about the density of $1$'s appearing in $(a_n)_{n \geq 1}$.
academic

Cloitres selbstgenerierende Sequenz

Grundinformationen

  • Paper-ID: 2501.00784
  • Titel: Cloitre's Self-Generating Sequence
  • Autor: Jeffrey Shallit (University of Waterloo)
  • Klassifizierung: math.CO cs.DM cs.FL math.NT
  • Veröffentlichungsdatum: 3. Januar 2025
  • Paper-Link: https://arxiv.org/abs/2501.00784

Zusammenfassung

Im Jahr 2009 führte Benoit Cloitre eine spezielle selbstgenerierende Sequenz (an)n≥1=1,1,2,1,1,1,1,2,1,1,2,1,1,2,2,…(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots ein, die die Eigenschaft besitzt, dass die Summe aller Terme im nn-ten Lauf gleich dem Doppelten des nn-ten Terms der Sequenz ist. Dieses Paper etabliert eine Verbindung zwischen dieser Sequenz und der Papierfaltungssequenz und beweist Cloitres Vermutung über die Dichte der Ziffer 1 in der Sequenz.

Forschungshintergrund und Motivation

Forschungsfrage

Die Kernfrage dieser Arbeit ist die Analyse der Struktureigenschaften der Cloitreschen selbstgenerierenden Sequenz, insbesondere:

  1. Die Beziehung dieser Sequenz zu bekannten mathematischen Objekten (Papierfaltungssequenzen)
  2. Das Problem der asymptotischen Dichte der Ziffer 1 in der Sequenz

Bedeutung des Problems

Selbstgenerierende Sequenzen nehmen einen wichtigen Platz in der Kombinatorik ein, da sie komplexe Struktureigenschaften aufweisen und mit mehreren mathematischen Bereichen verbunden sind. Die Untersuchung der Cloitreschen Sequenz ist aus folgenden Gründen bedeutsam:

  • Erweiterung des Verständnisses der Eigenschaften selbstgenerierender Sequenzen
  • Etablierung neuer Verbindungen zu klassischen Sequenzen wie Papierfaltungssequenzen
  • Bereitstellung neuer Anwendungsfälle für die Automatentheorie in der Sequenzanalyse

Einschränkungen bestehender Forschung

Bestehende Forschungen zu ähnlichen Sequenzen (wie der Oldenburger-Kolakoski-Sequenz) zeigen, dass die asymptotischen Eigenschaften solcher Sequenzen oft schwer zu analysieren sind. Beispielsweise bleibt die Frage, ob die Dichte von 1 in der Oldenburger-Kolakoski-Sequenz 1/2 beträgt, eine ungelöste Vermutung.

Forschungsmotivation

Cloitre stellte in dem OEIS-Eintrag A157196 die Vermutung auf, dass die Dichte von 1 in dieser Sequenz 2/3 beträgt, was dieser Arbeit ein klares Ziel setzt.

Kernbeiträge

  1. Etablierung neuer Sequenzverbindungen: Erstmalige Entdeckung einer tiefgreifenden Verbindung zwischen der Cloitreschen selbstgenerierenden Sequenz und der regulären Papierfaltungssequenz
  2. Beweis der Dichtevermutung: Strenger Beweis von Cloitres Vermutung, dass die Dichte von 1 in der Sequenz 2/3 beträgt
  3. Bereitstellung präziser Grenzen: Beweis von 0≤3gn−2n≤40 \leq 3g_n - 2n \leq 4, wobei gng_n die Anzahl der 1en in den ersten nn Termen ist
  4. Entwicklung einer Automatenmethode: Verwendung endlicher Automaten und der Walnut-Software zur Bereitstellung eines Rahmens für rechnergestützte Verifikation der Sequenzanalyse
  5. Erweiterung auf allgemeine Fälle: Verallgemeinerung der Ergebnisse auf beliebige Papierfaltungssequenzen

Methodische Erläuterung

Aufgabendefinition

Untersuchung der Cloitreschen Sequenz (an)n≥1(a_n)_{n\geq 1}, die durch die folgende selbstgenerierende Regel definiert ist:

  • Die Sequenz nimmt Werte im Alphabet {1,2} an
  • Sie beginnt mit a1=1a_1 = 1
  • Die Summe aller Elemente im nn-ten Lauf ist gleich 2an2a_n

Kernmethodische Architektur

1. Sequenzkonstruktionskette

Das Paper konstruiert eine Reihe miteinander verbundener Sequenzen:

  • Reguläre Papierfaltungssequenz (pn)(p_n)
  • Binäre Version (qn)(q_n), die pn=(−1)qnp_n = (-1)^{q_n} erfüllt
  • Differenzensequenz erster Ordnung (dn)(d_n)
  • Absolutwertsequenz (dn′)(d'_n)
  • Positionen von Laufenden (en′)(e'_n)
  • Schließlich erhält man (bn)=(an)(b_n) = (a_n)

2. Automatendarstellung

Jede Sequenz kann durch einen endlichen Automaten dargestellt werden:

  • DFAO (Deterministische endliche Automaten mit Ausgabe): für Sequenzen mit endlichen Werten
  • Synchrone Automaten: für Sequenzen mit ganzzahligen Werten
  • Alle Automaten verwenden die binäre Darstellung mit dem niedrigstwertigen Bit zuerst

3. Walnut-Verifikationsrahmen

Verwendung der Walnut-Software für formale Verifikation:

eval q_test "?lsd_2 An (Q[2*n]=Q[n] & Q[4*n+1]=@0 & Q[4*n+3]=@1)":

Technische Innovationspunkte

1. Papierfaltungssequenzverbindung

Innovative Entdeckung der Verbindung zwischen der Cloitreschen Sequenz und der Papierfaltungssequenz: q2n=qn,q4n+1=0,q4n+3=1q_{2n} = q_n, \quad q_{4n+1} = 0, \quad q_{4n+3} = 1

2. Vermutungs-Verifikationsstrategie

Für komplexe Sequenzen (wie Positionen von Laufenden) wurde eine "Vermutungs-Automaten-dann-Verifikations"-Strategie angewendet, die eine effektive Methode zur Behandlung automatischer Sequenzen darstellt.

3. Mehrschichtige Sequenzanalyse

Durch die Konstruktion mehrerer Zwischensequenzen wird die komplexe selbstgenerierende Eigenschaft in handhabbare Automatenbefehle zerlegt.

Experimentelle Einrichtung

Rechenwerkzeuge

  • Walnut-Software: für Automatenbefehle und formale Verifikation
  • Endliche Automaten: Alle Sequenzen werden durch Automaten dargestellt und berechnet
  • OEIS-Datenbank: für Sequenzverifikation und Vergleich

Verifikationsmethoden

  1. Automatenkorrektheitsprüfung: Verifikation der Automatenkorrektheit durch mehrere Bedingungsprüfungen
  2. Rekursionsrelationsverifikation: Verifikation, dass die Sequenz die Rekursionsrelationen erfüllt
  3. Randbedingungsprüfung: Verifikation von Anfangsbedingungen und Spezialfällen

Implementierungsdetails

  • Verwendung der binären Darstellung mit dem niedrigstwertigen Bit zuerst
  • Automatenzustandszahl zwischen 4 und 32
  • Alle Berechnungen werden durch formale Walnut-Verifikation überprüft

Experimentelle Ergebnisse

Beweis des Hauptsatzes

Satz 2: Sei gng_n die Anzahl der 1en in der Sequenz a1a2⋯ana_1a_2\cdots a_n, dann gilt: 0≤3gn−2n≤40 \leq 3g_n - 2n \leq 4 Daher lim⁡n→∞gn/n=2/3\lim_{n\to\infty} g_n/n = 2/3.

Wichtige Verifikationsergebnisse

  1. Sequenzkonsistenz: Verifikation von bn=anb_n = a_n, d.h., die konstruierte Sequenz ist tatsächlich die Cloitresche Sequenz
  2. Selbstgenerierende Eigenschaft: Verifikation von σn=2bn\sigma_n = 2b_n, wobei σn\sigma_n die Summe des nn-ten Laufs ist
  3. Lauflänge: Beweis, dass die Lauflänge nur 1, 2 oder 4 sein kann
  4. Dichtegrenzen: Verifikation der Dichtegrenzen durch einen 16-Zustands-Automaten

Zusätzliche Erkenntnisse

Beweis, dass die Sequenz wn=min⁡{t≥1:et′≥n}w_n = \min\{t \geq 1 : e'_t \geq n\} die OEIS-Sequenz A091960 ist und erfüllt:

  • w1=1w_1 = 1
  • w2n=w2n−1+(wn mod 2)w_{2n} = w_{2n-1} + (w_n \bmod 2)
  • w2n+1=w2n+1w_{2n+1} = w_{2n} + 1

Verwandte Arbeiten

Hauptverwandte Sequenzen

  1. Oldenburger-Kolakoski-Sequenz: k:=1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,…k := 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, \ldots
    • Der nn-te Term ist gleich der Länge des nn-ten Laufs
    • Das Problem der Dichte von 1 bleibt ungelöst
  2. Dekking-Sequenz: 1,3,3,3,1,1,1,3,3,3,…1, 3, 3, 3, 1, 1, 1, 3, 3, 3, \ldots
    • Die Lauflängensequenz ist gleich der Sequenz selbst
    • Kann als Fixpunkt von Morphismen verstanden werden
  3. Papierfaltungssequenz: Durch iteratives Falten von Papier erzeugte Sequenz
    • Tiefe Verbindung zur binären Darstellung
    • Kann durch endliche Automaten berechnet werden

Einzigartigkeit des Beitrags dieses Papers

Die Cloitresche Sequenz ist leichter zu handhaben als die Oldenburger-Kolakoski-Sequenz, da sie eine subtile aber klare Verbindung zur binären Darstellung hat, was die Automatenmethode besonders wirksam macht.

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Dichtesatz: Strenger Beweis, dass die Dichte von 1 in der Cloitreschen Sequenz 2/3 beträgt
  2. Strukturverbindung: Etablierung einer tiefgreifenden Verbindung zur Papierfaltungssequenz
  3. Rechnerischer Rahmen: Demonstration der Stärke der Automatenmethode in der Sequenzanalyse

Universalität der Methode

Abschnitt 7 des Papers zeigt, dass alle Ergebnisse auf beliebige Papierfaltungssequenzen verallgemeinert werden können, obwohl es im allgemeinen Fall keine offensichtliche Analogie zur selbstgenerierenden Eigenschaft gibt.

Zukünftige Richtungen

  1. Untersuchung von Verbindungen zwischen anderen selbstgenerierenden Sequenzen und klassischen Sequenzen
  2. Entwicklung eines allgemeineren Automatenbewertungsrahmens
  3. Erkundung von Anwendungen in anderen mathematischen Bereichen

Tiefgreifende Bewertung

Stärken

  1. Methodische Innovation: Geschickte Kombination der Automatentheorie mit Sequenzanalyse
  2. Strenge: Alle Ergebnisse werden durch formale Verifikation überprüft
  3. Vollständigkeit: Nicht nur der Hauptvermutung bewiesen, sondern auch zusätzliche Struktureigenschaften entdeckt
  4. Erweiterbarkeit: Die Methode kann auf eine breitere Klasse von Sequenzen verallgemeinert werden

Technische Highlights

  1. Vermutungs-Verifikationsstrategie: Bietet eine praktische Methode für die Analyse komplexer automatischer Sequenzen
  2. Mehrschichtige Sequenzkonstruktion: Vereinfacht die Analyse komplexer Eigenschaften durch Zwischensequenzen
  3. Rechnerische Verifikation: Die Verwendung der Walnut-Software gewährleistet die Zuverlässigkeit der Ergebnisse

Einschränkungen

  1. Rechenkomplexität: Einige Automaten haben eine höhere Zustandszahl, was die Analyse komplexerer Sequenzen einschränken könnte
  2. Vermutungsabhängigkeit: Einige Automaten erfordern zunächst eine Vermutung und dann eine Verifikation, es fehlt eine systematische Konstruktionsmethode
  3. Verallgemeinerungsgrenzen: Obwohl auf beliebige Papierfaltungssequenzen verallgemeinerbar, geht die selbstgenerierende Eigenschaft verloren

Einflussfähigkeit

  1. Theoretischer Beitrag: Bereitstellung neuer Analysewerkzeuge für die Forschung selbstgenerierender Sequenzen
  2. Methodologischer Wert: Demonstration der Anwendung computergestützter Beweise in der Kombinatorik
  3. Praktizität: Bereitstellung einer Vorlage für die Untersuchung verwandter Sequenzen in der OEIS

Anwendbare Szenarien

Diese Methode ist besonders geeignet für:

  • Sequenzanalyse mit Bezug zur binären Darstellung
  • Untersuchung automatischer Sequenzen mit Rekursionsstruktur
  • Kombinatorische Sequenzen, die eine präzise Dichteanalyse erfordern

Literaturverzeichnis

Das Paper zitiert 14 wichtige Arbeiten, die klassische Arbeiten in den Bereichen Automatensequenztheorie, Papierfaltungssequenzen, Kolakoski-Sequenzen und verwandten Feldern umfassen und eine solide theoretische Grundlage für die Forschung bieten.