On a perturbed Hofstadter $Q$-recursion

Dieser Artikel beweist, dass die von Mantovanelli eingeführte, durch einen Paritäts-Term gestörte Variante der Hofstadter-Q-Folge wohldefiniert ist und ein exaktes dyadisches Selbstähnlichkeitsverhalten mit einer asymptotischen Konvergenzrate von $O(1/\sqrt{\log n})$ aufweist, wobei die Struktur der Folge durch die Catalan-Zahlen gesteuert wird.

Das Wesentliche

Stellen Sie sich eine riesige, chaotische Stadt vor, in der die Straßenpläne sich ständig selbst ändern. Das ist die Welt der berühmten Hofstadter-Q-Folge. Seit Jahrzehnten versuchen Mathematiker, diese Stadt zu verstehen, aber sie ist so verwirrend, dass niemand weiß, ob man sie jemals vollständig durchqueren kann oder ob es irgendwann eine Sackgasse gibt, die das ganze System zum Stillstand bringt.

In diesem Papier stellt der Autor Benoît Cloitre eine neue, leicht modifizierte Version dieser Stadt vor. Er hat eine kleine, aber mächtige Regel hinzugefügt: Ein winziger „Schalter", der je nach Schrittzahl umschaltet (wie ein Licht, das zwischen An und Aus wechselt).

Hier ist die Geschichte dieser Entdeckung, einfach erklärt:

1. Das Chaos vs. Der geordnete Garten

Die ursprüngliche Stadt (die Q-Folge) ist wie ein wilder Dschungel. Die Wege kreuzen sich unvorhersehbar, und man weiß nicht, ob man jemals einen klaren Pfad findet.

Die neue Version (die „gestörte" Folge $\tilde{Q}$) ist wie ein perfekt angelegter, fraktaler Garten. Durch den kleinen Schalter (die Paritäts-Störung) verwandelt sich das Chaos in eine erstaunliche Ordnung. Die Stadt baut sich selbst immer wieder in kleineren und kleineren Kopien nach, wie eine Puppe, die in sich selbst eine noch kleinere Puppe enthält, und so weiter.

2. Die Brücken und die Wellen

Um dieses Muster zu verstehen, teilen die Autoren die Stadt in zwei Hälften:

• Die Brücken (A und B): Zwei parallele Straßen, die sich fast parallel verlaufen.
• Die Wellen (δ): Wenn man die Höhe der beiden Straßen vergleicht, entsteht eine Welle. Diese Welle geht nicht einfach zufällig hoch und runter. Sie formt sich zu perfekten Bögen (wie die Wellen im Meer oder die Bögen einer Brücke).

Das Tolle ist: Diese Bögen folgen einem strengen Bauplan. Sie sind nicht zufällig, sondern bauen sich aus kleineren Bögen auf, die sich in einem riesigen, sich wiederholenden Muster stapeln.

3. Die Zauberformel der Zahlen

Der Autor entdeckt, dass die Höhe dieser Bögen nicht zufällig ist, sondern von einer sehr speziellen mathematischen Familie von Zahlen abhängt, die Catalan-Zahlen genannt werden.

• Stellen Sie sich vor, Sie bauen eine Treppe. Bei jedem Schritt wird die Treppe nicht nur höher, sondern die Anzahl der möglichen Wege, sie zu bauen, folgt einer perfekten mathematischen Regel.
• In dieser Stadt bestimmen diese Catalan-Zahlen, wie hoch die Wellen werden. Je weiter man in die Zukunft (zu größeren Zahlen) schaut, desto höher werden die Bögen, aber sie wachsen langsamer als die Stadt selbst.

4. Die große Entdeckung: Der Weg nach oben

Die wichtigste Frage war: „Führt diese Stadt irgendwohin?"
Die Antwort ist ein klares JA.

• Die Richtung: Wenn man sehr weit in die Stadt hineinläuft (zu sehr großen Zahlen $n$), nähert sich das Verhältnis der Höhe der Straße zur Entfernung ($\tilde{Q}(n)/n$) immer mehr einer perfekten Mitte an: genau 1/2.
• Die Geschwindigkeit: Es ist nicht so, dass man sofort genau in der Mitte ist. Man schwingt leicht hin und her. Aber die Schwingungen werden mit der Zeit immer kleiner. Die Mathematik zeigt, dass diese Schwankungen mit einer sehr spezifischen Geschwindigkeit verschwinden: Sie werden kleiner, je mehr man durch die Wurzel aus dem Logarithmus der Zahl teilt.

5. Warum ist das wichtig?

Stellen Sie sich vor, die ursprüngliche chaotische Stadt (Q) ist ein riesiges, ungelöstes Rätsel. Die neue, geordnete Stadt ($\tilde{Q}$) ist wie ein Modell oder ein Ersatz.
Die Autoren vermuten, dass die chaotische Stadt sich fast genauso verhält wie die geordnete, nur mit einem kleinen „Rauschen" oder einer Verzerrung. Wenn man beweisen könnte, dass die ursprüngliche Stadt sich wie diese neue verhält, würde das bedeuten, dass auch die chaotische Stadt niemals in eine Sackgasse läuft und dass sie sich langfristig auch auf die Mitte 1/2 zubewegt.

Zusammenfassung in einem Bild

Stellen Sie sich einen Zauberer vor, der eine wilde, unkontrollierbare Flamme (die Q-Folge) in eine Schale hält. Die Flamme flackert wild und unvorhersehbar.
Der Zauberer fügt einen kleinen, regelmäßigen Windstoß hinzu (die Störung). Plötzlich verwandelt sich die wilde Flamme in einen perfekten, sich wiederholenden Lichttanz.
Die Mathematiker haben nun den Bauplan für diesen Tanz gefunden. Sie wissen genau, wie die Wellen aufgebaut sind, wie hoch sie werden und dass sie sich im Großen und Ganzen immer genau in der Mitte des Raumes bewegen.

Das Fazit: Durch eine winzige, kluge Änderung haben die Forscher ein chaotisches mathematisches Monster in ein verständliches, schönes Muster verwandelt, das uns hoffentlich eines Tages hilft, das ursprüngliche, wilde Monster zu zähmen.

Technische Zusammenfassung

Titel

On a perturbed Hofstadter Q-recursion (Über eine gestörte Hofstadter-Q-Rekursion)
Autor: Benoît Cloitre
Datum: April 2026 (vorgelegt auf arXiv)

---

1. Problemstellung und Hintergrund

Die Hofstadter-Q-Folge ($Q(n)$) ist eines der bekanntesten Beispiele für verschachtelte Rekursionen, definiert durch:
$$Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), \quad Q(1)=Q(2)=1$$
Trotz jahrzehntelanger Forschung ist die Natur dieser Folge weitgehend unverstanden. Es ist nicht bewiesen, ob $Q(n)$ für alle $n$ definiert ist, und das asymptotische Verhalten von $Q(n)/n$ ist unbekannt (es zeigt chaotisches Verhalten um den Wert $1/2$).

Im Jahr 2026 führte Mantovanelli eine paritätsgestörte Variante $\tilde{Q}(n)$ ein, indem er den Term $(-1)^n$ zur Rekursion hinzufügte:
$$\tilde{Q}(n) = \tilde{Q}(n - \tilde{Q}(n-1)) + \tilde{Q}(n - \tilde{Q}(n-2)) + (-1)^n, \quad \tilde{Q}(1)=\tilde{Q}(2)=1$$
Diese kleine Störung hat einen drastischen Effekt: Sie ersetzt das chaotische Verhalten durch eine exakte dyadische Selbstähnlichkeit. Das Ziel dieses Papers ist es, die Wohldefiniertheit von $\tilde{Q}$ für alle $n$ zu beweisen und sein asymptotisches Verhalten präzise zu charakterisieren.

---

2. Methodik und Struktur der Analyse

Die Analyse basiert auf einer tiefen strukturellen Zerlegung der Folge $\tilde{Q}$ und der Entdeckung einer zugrunde liegenden deterministischen Maschine.

A. Paritätsaufspaltung und Subfolgen

Da alle Werte von $\tilde{Q}(n)$ ungerade sind, wird die Folge durch die Transformation $R(n) = (\tilde{Q}(n)+1)/2$ in zwei Subfolgen $A(m)$ und $B(m)$ zerlegt, die die ungeraden bzw. geraden Indizes abdecken. Dies führt zu zwei gekoppelten Rekursionen (RA) und (RB), die das Verhalten der Folge auf "Bögen" (arches) beschreiben.

B. Die Bogen-Zerlegung (Arch Decomposition)

Die Differenz $\delta(m) = B(m) - A(m)$ oszilliert und definiert eine natürliche Zerlegung in abwechselnde positive Bögen ($\delta \ge 0$) und negative Bögen ($\delta \le 0$).

• Die Nullstellen von $\delta$ markieren die Grenzen dieser Bögen.
• Die Struktur dieser Bögen wird durch eine Arch-Skelett-Hypothese (H1) beschrieben, die explizite Formeln für die Längen und Amplituden der Bögen liefert.

C. Der Interleave-Transducer (Verschachtelungs-Maschine)

Ein zentraler Durchbruch ist die Erkenntnis, dass die Rekursion als eine deterministische Maschine interpretiert werden kann, die zwei Binärbänder abwechselnd ausliest.

• Schritt-Wörter ($P_r, N_r$): Diese Wörter kodieren die Differenzen $\Delta A$ und $\Delta B$ innerhalb der Bögen.
• Verschachtelungsgesetze (Laws 1 & 2): Die Schritt-Wörter eines Bogen-Niveaus $r+1$ werden durch eine explizite Interleave-Operation (Verschachtelung) aus den Daten des vorherigen Niveaus $r$ konstruiert.
  • $P_{r+1} = \text{Interleave}(S_0, S_1, 0)$
  • $N_r = \text{Interleave}(P_r[2:], P_r[:-1], 1)$
• Diese Operation erzeugt eine selbstähnliche Struktur, bei der die Schritt-Wörter anti-palindromisch und balanciert sind (gleiche Anzahl von Nullen und Einsen).

D. Zwei Beweiswege

Der Beweis für die Konvergenz erfolgt über zwei parallele Pfade:

1. Route B (Frequenzen, Unbedingt): Analyse der Besuchshäufigkeiten (Visit Multiplicities) der Werte $A(m)$ und $B(m)$ auf dyadischen Blöcken. Dies führt zu einer exakten Frequenzverteilung, die durch Catalan-Zahlen und zentrale Binomialkoeffizienten gesteuert wird.
2. Route A (Amplituden, Bedingt): Analyse der Amplituden der Bögen ($V^+(r)$). Dies erfordert zwei zusätzliche, numerisch verifizierte, aber noch nicht allgemein bewiesene Vermutungen (Observations 9.4 und 9.10), die eine exakte Identität für die Amplituden-Zuwächse liefern.

---

3. Hauptergebnisse

A. Wohldefiniertheit und Konvergenzrate (Unbedingt)

Der Autor beweist, dass $\tilde{Q}(n)$ für alle $n \ge 1$ wohldefiniert ist und $1 \le \tilde{Q}(n) \le n$ gilt.
Das Hauptresultat (Theorem 1.1a) ist die Konvergenz:
$$\left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| = O\left(\frac{1}{\sqrt{\log n}}\right)$$
Dies bedeutet, dass die Folge gegen $1/2$ konvergiert, wobei die Abweichung mit der Rate $1/\sqrt{\log n}$ abnimmt. Dieser Beweis ist unbedingt (erfordert keine ungelösten Vermutungen) und stützt sich auf die Frequenzanalyse (Route B) und die Eigenschaften der Interleave-Operation.

B. Exakte Hüllkurven-Konstante (Bedingt)

Unter der Annahme zweier numerisch überprüfter Eigenschaften (die "Record Claim" und die Identifikation von Lauflängen):

• Die Amplituden-Zuwächse $W_r$ der Bögen folgen exakt der Formel:
  $$W_r = \binom{2r+1}{r}$$
• Dies führt zu einer präziseren asymptotischen Beschreibung des maximalen Fehlers:
  $$\limsup_{n \to \infty} \left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| \sqrt{\log_2 n} = \frac{1}{3\sqrt{2\pi}}$$
  Dieser Wert ($\approx 0.133$) beschreibt die exakte Hüllkurve der Oszillationen.

C. Verbindung zur originalen Hofstadter-Folge

Numerische Experimente deuten darauf hin, dass die Differenz zwischen der chaotischen Folge $Q(n)$ und der gestörten Folge $\tilde{Q}(n)$ durch die Amplituden von $\tilde{Q}$ gesteuert wird:
$$Q(n) - \tilde{Q}(n) = O\left(\frac{n}{\sqrt{\log n}}\right)$$
Da $n/\sqrt{\log n} = o(n)$, würde ein Beweis dieser Vermutung implizieren, dass auch die originale Hofstadter-Folge $Q(n)$ für alle $n$ definiert ist und $Q(n)/n \to 1/2$ konvergiert.

---

4. Signifikanz und Bedeutung

1. Lösung eines offenen Problems: Das Paper liefert den ersten strengen Beweis für die Wohldefiniertheit und Konvergenz einer nicht-trivialen Hofstadter-artigen Folge.
2. Strukturelle Einsicht: Die Entdeckung der Interleave-Transducer-Struktur und der Catalan-Dualität bietet ein neues Werkzeug zum Verständnis verschachtelter Rekursionen. Es zeigt, dass scheinbar chaotische Systeme durch eine tiefe, selbstähnliche Ordnung (gesteuert durch Catalan-Zahlen und Binomialkoeffizienten) beherrscht werden können.
3. Verbindung zur Kombinatorik: Die Arbeit verbindet Meta-Fibonacci-Folgen mit der analytischen Kombinatorik (Catalan-Generierende Funktionen, Kernel-Methode) und zeigt, wie sich diese Strukturen in der asymptotischen Analyse niederschlagen.
4. Proxy für das Chaos: Die gestörte Folge $\tilde{Q}$ dient als "handhabbarer Proxy" für die originale, chaotische $Q$-Folge. Das Verständnis von $\tilde{Q}$ könnte der Schlüssel zum Beweis der Eigenschaften von $Q$ sein.
5. Erweiterbarkeit: Die Methoden werden auch auf andere gestörte Folgen (z.B. die Conway-Mallows-Folge) angewendet, wobei dort ein anderer Grenzwert ($1/(2\phi)$) vermutet wird, was auf eine tiefe Interaktion zwischen Paritätsstörungen und Verschachtelungstiefe hindeutet.

Fazit

Benoît Cloitre gelingt es, durch eine elegante Kombination aus diskreter Dynamik, Kombinatorik (Catalan-Zahlen) und analytischer Methoden die chaotische Natur einer Hofstadter-Variante zu zähmen. Das Paper liefert nicht nur einen Konvergenzbeweis, sondern enthüllt eine fraktale, selbstähnliche Struktur, die durch eine deterministische Maschine gesteuert wird, und setzt damit neue Maßstäbe für die Analyse nichtlinearer Rekursionen.