🔢 mathematics

Almost Golomb Sequences

Die Arbeit führt fast-Golomb-Folgen ein, bei denen eine endliche Gedächtnis-Trunkierung der ursprünglichen rekursiven Regel zu einem Wechsel von glattem Potenzwachstum zu oszillierendem linearem Wachstum führt, $r$ -Regulärität bewirkt und eine überraschende Selbstreferenz aufdeckt, bei der die ursprüngliche Golomb-Folge die maximale Multiplizität der gesamten Familie bestimmt.

Ursprüngliche Autoren: Benoit Cloitre

Veröffentlicht 2026-04-06

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Benoit Cloitre

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 Geschichte vom perfekten Zähler und seinen unperfekten Cousins

Stellen Sie sich vor, Sie haben eine sehr spezielle Art von Zähler, den wir Golomb nennen. Golomb ist ein perfektionistischer Organist. Er erstellt eine Liste von Zahlen, die einer strengen Regel folgt:

Die Zahl 1 erscheint genau 1 Mal.
Die Zahl 2 erscheint genau 2 Mal.
Die Zahl 3 erscheint genau 3 Mal.
Die Zahl 4 erscheint genau 4 Mal.
Und so weiter.

Das Ergebnis ist eine Liste, die sich selbst beschreibt: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5...
Golomb ist ein „ewiger" Zähler. Um zu wissen, wie oft eine Zahl vorkommt, muss er sich die gesamte Liste bis zum aktuellen Punkt ansehen. Er hat ein unendlich gutes Gedächtnis. Sein Wachstum ist sehr glatt und vorhersehbar, wie eine sanfte Kurve.

Das Experiment: Golomb mit einem „kurzen Gedächtnis"

Nun stellt sich Benoît Cloitre eine spannende Frage: Was passiert, wenn wir Golomb ein kurzes Gedächtnis geben?

Stellen Sie sich vor, Golomb vergisst die ferne Vergangenheit. Er kann sich nur an die letzten r Zahlen erinnern, die er gerade geschrieben hat. Wir nennen diese neuen Zähler „Fast-Golomb-Sequenzen" (Almost Golomb Sequences).

Golomb (r = ∞): Schaut auf die gesamte Liste zurück.
Fast-Golomb (r = 2, 3, 4...): Schaut nur auf die letzten 2, 3 oder 4 Zahlen zurück, um zu entscheiden, was als nächstes kommt.

Was passiert, wenn man das Gedächtnis kürzt?

Das ist der spannende Teil der Entdeckung. Wenn man Golomb das Gedächtnis nimmt, verändert sich sein Charakter komplett:

Von der glatten Kurve zum Zittern:
Der echte Golomb wächst wie eine glatte Welle. Die „Fast-Golomb"-Zähler hingegen beginnen zu zittern. Ihre Wachstumsrate schwankt hin und her. Sie wachsen zwar immer noch linear (wie eine gerade Linie), aber sie wackeln auf dieser Linie hin und her, als würden sie auf einem unebenen Boden laufen. Sie erreichen nie einen stabilen, ruhigen Zustand.
Der „Automaten"-Effekt:
Der echte Golomb ist so komplex, dass er sich nicht mit einfachen Regeln beschreiben lässt. Aber die „Fast-Golomb"-Zähler werden zu Automaten. Das bedeutet, ihr Verhalten folgt einem strengen, wiederkehrenden Muster, das man wie ein kleines Computerprogramm beschreiben kann. Je kleiner das Gedächtnis (r), desto einfacher ist das Programm, aber desto wilder ist das Zittern.
Die Entdeckung der „Korrektur-Geister":
Cloitre hat herausgefunden, dass man diese wilden Zitterbewegungen mit einfachen Formeln beschreiben kann, wenn man ein paar kleine „Korrektur-Geister" (mathematisch: Korrektursequenzen) hinzufügt. Diese Geister sind winzige Fehler, die auftreten, wenn das Gedächtnis zu kurz ist, aber sie folgen selbst wieder einem strengen Muster.

Das große Rätsel: Der Kreis schließt sich

Das Überraschendste an dieser Forschung ist das Ende der Geschichte.

Cloitre hat untersucht, wie oft bestimmte Zahlen in diesen „Fast-Golomb"-Listen vorkommen. Er hat festgestellt, dass die maximale Häufigkeit, mit der eine Zahl in einer Liste mit Gedächtnisgröße r vorkommt, nicht zufällig ist.

Es stellt sich heraus, dass die Häufigkeit selbst von der ursprünglichen, perfekten Golomb-Sequenz gesteuert wird!

Wenn Sie fragen: „Wie oft kommt die Zahl X maximal vor, wenn das Gedächtnis r groß genug ist?", ist die Antwort: „Genau so oft, wie die Zahl X im echten Golomb vorkommt."

Das ist wie ein Spiegel, der sich selbst betrachtet. Die Sequenz, die durch das „Vergessen" (das Kürzen des Gedächtnisses) entstanden ist, trägt am Ende den Fingerabdruck des Originals in sich. Der „Vater" (Golomb) regiert über seine „Kinder" (Fast-Golomb), auch wenn die Kinder versuchen, ihn zu vergessen.

Zusammenfassung in einer Metapher

Stellen Sie sich einen Dirigenten (Golomb) vor, der ein Orchester leitet.

Der echte Dirigent hört jedes einzelne Instrument, das jemals gespielt wurde, um den nächsten Takt zu bestimmen. Das Ergebnis ist eine perfekte, glatte Symphonie.
Die „Fast-Golomb"-Dirigenten sind Schüler, die sich nur an die letzten paar Takte erinnern können. Wenn sie dirigieren, wird das Musikstück unruhig und wackelig. Sie stolpern über ihre eigenen Schritte.
Aber am Ende der Aufführung stellt sich heraus: Die Art und Weise, wie oft die Schüler stolpern, folgt exakt dem Rhythmus, den der große Meister dirigiert hätte. Der Schüler trägt den Meister in sich, auch wenn er versucht, ihn zu vergessen.

Die Botschaft der Arbeit:
Selbst wenn man die Regeln eines komplexen Systems vereinfacht (indem man das Gedächtnis begrenzt), verschwindet die tiefe Struktur des Originals nicht. Sie versteckt sich nur in den Schwankungen und wartet darauf, entdeckt zu werden.

1. Problemstellung und Motivation

Das Papier untersucht eine Verallgemeinerung der berühmten Golomb-Folge (OEIS A001462). Die Golomb-Folge $(G(n))_{n \ge 1}$ ist die eindeutige nichtfallende Folge positiver ganzer Zahlen, in der die Zahl $n$ genau $G(n)$ -mal vorkommt. Sie wird durch die globale selbstreferenzielle Regel definiert:
$G\left(\sum_{k=1}^n G(k)\right) = n$
Diese Folge wächst asymptotisch glatt wie $n^{\phi-1}$ (wobei $\phi$ der goldene Schnitt ist) und ist für kein $k \ge 2$ $k$ -regulär (im Sinne von Allouche und Shallit).

Die Autoren führen fast-Golomb-Folgen (Almost Golomb Sequences) ein, indem sie den unendlichen kumulativen Summenbereich in der Definition durch ein Gleitfenster fester Größe $r$ ersetzen. Für ein festes $r \ge 2$ ist die fast-Golomb-Folge der Ordnung $r$ , bezeichnet als $(a(n))_{n \ge 1}$ , die nichtfallende Folge positiver ganzer Zahlen, die die folgende rekursive Bedingung erfüllt:
$a\left(a(n) + a(n-1) + \dots + a(n-r+1)\right) = n$
mit der Minimalitätsbedingung, dass $a(n)$ der kleinste Integer $\ge a(n-1)$ ist, der die Gleichung erfüllt (wobei $a(k)=0$ für $k \le 0$ gesetzt wird).

Das zentrale Problem besteht darin, zu verstehen, wie diese „Gedächtnis-Trunkierung" (von unendlich auf endlich) die strukturellen Eigenschaften der Folge verändert: Wachstum, Regularität und kombinatorische Struktur.

2. Methodik

Die Arbeit kombiniert analytische Beweise, konstruktive Rekursionen und computergestützte Verifikation:

Strukturelle Analyse: Es wird gezeigt, dass die Folge durch ihre „Lauf"-Struktur (Run structure) charakterisiert werden kann, wobei die Werte $m$ in Intervallen $[S_m, S_{m+1}-1]$ auftreten, wobei $S_m$ die Startposition des Wertes $m$ ist.
Automatentheorie: Die Autoren nutzen das Kriterium von Allouche und Shallit, um die $r$ -Regularität zu beweisen. Eine Folge ist $r$ -regulär, wenn der von ihrer $r$ -Kern-Unterfolge erzeugte $\mathbb{Z}$ -Modul endlich erzeugt ist.
Entschachtelung (Denesting): Für kleine Werte von $r$ ( $r \in \{2, 3, 4, 5\}$ ) werden explizite Formeln hergeleitet, die $a(rn+i)$ durch Linearkombinationen von verschobenen Werten von $a(n)$ und Korrektursequenzen ausdrücken.
Computergestützte Beweise: Für $r=4$ und $r=5$ werden die identifizierten Rekursionsmuster mit dem Theorem-Prover Walnut verifiziert. Dies bestätigt die Gültigkeit der gefundenen booleschen Rekursionen für die Korrektursequenzen über den gesamten Definitionsbereich.
Asymptotische Analyse: Durch die Untersuchung von Teilfolgen entlang geometrischer Progressionen (z. B. $n = c \cdot r^k$ ) wird das Konvergenzverhalten des Quotienten $a(n)/n$ analysiert.

3. Hauptbeiträge und Ergebnisse

A. $r$ -Regularität und Automatizität

Ein zentrales Ergebnis ist Satz 2.9: Für jedes $r \ge 2$ ist die Differenzfolge $d(n) = a(n+1) - a(n)$ $r$ -automatisch, und die Folge $(a(n))$ selbst ist $r$ -regulär.

Dies steht im starken Kontrast zur Golomb-Folge, die nicht $k$ -regulär ist.
Der Beweis reduziert die Bestimmung von $d(rn+i)$ auf ein endliches lokales Fenster von Daten.

B. Explizite Entschachtelungsformeln (Denesting)

Für $r \in \{2, 3, 4, 5\}$ werden explizite Formeln der Form $a(rn+i) = \text{Linearkombination} + \text{Korrektur}$ hergeleitet:

Fall $r=2$ (Dyadisch): Es wird eine geschlossene Formel für dyadische Blöcke gefunden. Die Folge erfüllt eine Mallows-artige verschachtelte Rekursion:
$a(n+1) = 1 + a(n + 1 - a(a(n)+1) + a(a(n)-1))$
Die Korrektur ist trivial (die Folge ist rein durch die Rekursion bestimmt).
Fall $r=3$ (Triadisch): Die Entschachtelung erfordert eine binäre Korrekturfolge $\varepsilon(n)$ , die $3$-automatisch ist und durch ein DFAO (Deterministischer endlicher Automat mit Ausgabe) generiert wird. Die Formeln hängen von der Position innerhalb des Triaden-Blocks ab.
Fälle $r=4$ und $r=5$ : Hier werden vier bzw. zwei Korrektursequenzen ( $\varepsilon_i$ bzw. $\varepsilon, \eta$ ) identifiziert, die durch komplexe boolesche Rekursionen (XOR, XNOR) gesteuert werden. Diese wurden mit Walnut zertifiziert.

C. Nicht-Konvergenz von $a(n)/n$

Im Gegensatz zur Golomb-Folge, bei der $a(n)/n^{\phi-1}$ gegen eine Konstante konvergiert, konvergiert der Quotient $a(n)/n$ für fast-Golomb-Folgen nicht.

Der Quotient oszilliert zwischen zwei expliziten rationalen Grenzwerten.
Beispiele:
- Für $r=2$ : Grenzwerte sind $3/4$ und $2/3$ .
- Für $r=3$ : Grenzwerte sind $8/15$ und $5/8$ .
- Für $r=4$ : Grenzwerte sind $25/48$ und $10/21$ .
- Für $r=5$ : Grenzwerte sind $93/200$ und $87/200$ .
Dies wird durch die Analyse der Korrekturmuster entlang geometrischer Folgen bewiesen (Lemma 2.8).

D. Kombinatorische Interpretationen

$r=2$ : Die Multiplizität $N_2(n)$ (wie oft $n$ vorkommt) hängt nur von der zweiten höchstwertigen Bitstelle von $n-1$ ab. Die Differenzfolge $d(n)$ wird durch eine einfache boolesche Zelluläre Automatenregel generiert: $d(2n)=1$ und $d(2n+1) = d(n) \cdot d(n+1)$ .
$r=3$ : Die Struktur der Differenzfolge lässt sich durch eine palindromische Substitutionsregel beschreiben, die eine verzögerte Rückkopplung (delayed-feedback) darstellt.

E. Die Golomb-Meta-Struktur (Konjektur)

Ein numerisches Phänomen wird entdeckt: Die maximale Multiplizität $M(r) = \sup_n N_r(n)$ der fast-Golomb-Folge der Ordnung $r$ scheint durch die Golomb-Folge selbst gesteuert zu werden.

Es wird definiert: $j_k$ ist die kleinste Ordnung $r$ , für die $M(r) \ge k$ gilt.
Die Daten zeigen, dass für $k \ge 4$ die Differenzen $j_{k+1} - j_k$ exakt den Werten der Golomb-Folge $G(k)$ entsprechen.
Konjektur 9.1: $j_{k+1} - j_k = G(k)$ und $j_k = S(k-1) + 2$ , wobei $S$ die Partialsumme von $G$ ist.
Dies wird auf zwei Teilkonjekturen reduziert: Die „Prefix Conjecture" ( $a_r(r) = G(r-1)$ ) und das „Domination Lemma" (die maximale Multiplizität wird am Rand des Fensters erreicht).

4. Bedeutung und Ausblick

Die Arbeit hat mehrere wichtige Implikationen für die Theorie der selbstreferenziellen Folgen:

Übergang von Analytik zu Automatizität: Sie zeigt, wie eine kleine Änderung in der Definition (unendliches vs. endliches Gedächtnis) die Folge von einem analytischen Objekt (mit irrationaler Wachstumsrate) in ein diskretes, automatentheoretisches Objekt (mit rationalen Oszillationen und endlicher Regularität) verwandelt.
Struktur der $r$ -Regularität: Sie liefert konkrete Beispiele für $r$ -reguläre Folgen, die durch komplexe Korrektursequenzen gesteuert werden, und demonstriert die Effektivität von Werkzeugen wie Walnut für den Beweis solcher Eigenschaften.
Selbstbezug in der Hierarchie: Die Entdeckung, dass die ursprüngliche Golomb-Folge die Struktur der Familie ihrer „fast"-Varianten kontrolliert (Meta-Struktur), deutet auf eine tiefe, noch unverstandene Verbindung zwischen diesen Folgenklassen hin.
Offene Fragen: Das Papier wirft Fragen zum Verhalten für $r \to \infty$ (Phasenübergang zur Golomb-Folge), zur Konvergenz der Cesàro-Mittel für $r \ge 3$ und zur kombinatorischen Struktur für $r \ge 4$ auf.

Zusammenfassend etabliert das Papier eine neue Klasse von Folgen, die als Brücke zwischen klassischen selbstreferenziellen Folgen und der Theorie der $k$ -regulären Folgen dient, und liefert sowohl strenge Beweise als auch faszinierende numerische Vermutungen über deren tiefere Struktur.