🔢 mathematics

Brik's sequence: a strange recursion

Dieser Artikel untersucht die Eigenschaften der unendlichen binären Folge Brik-Folge und zeigt, dass sie rekurrent, aber nicht gleichmäßig rekurrent ist, eine exponentielle Faktorkomplexität aufweist, nicht morphisch ist und eine transzendente Dichte von Einsen besitzt.

Ursprüngliche Autoren: Jeffrey Shallit

Veröffentlicht 2026-05-11

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jeffrey Shallit

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

Stellen Sie sich vor, Sie bauen eine unendliche Geschichte, müssen aber eine sehr seltsame, rekursive Regel befolgen, um jedes neue Kapitel zu schreiben. Dies ist die Geschichte der „Brik-Folge", einer mathematischen Kuriosität, die von einem Studenten namens Garo Brik entdeckt und von Professor Jeffrey Shallit analysiert wurde.

Hier ist die einfache Aufschlüsselung dessen, was die Arbeit sagt, unter Verwendung alltäglicher Analogien.

Die Geschichtenerzähl-Regel

Stellen Sie sich vor, Sie haben einen Satz, nennen wir ihn B1: „101".
Um das nächste Kapitel (B2) zu schreiben, nehmen Sie den aktuellen Satz und hängen eine „zerstückelte" Version davon an.

Die Regel: Um die nächste Version zu erhalten, nehmen Sie die aktuelle, schneiden die ersten paar Buchstaben ab (entsprechend der Kapitelnummer) und kleben das abgeschnittene Stück ans Ende.
Beispiel:
- Kapitel 1: „101" (Länge 3).
- Kapitel 2: Nehmen Sie „101", schneiden Sie die ersten 1 Buchstaben ab („1"), übrig bleibt „01". Kleben Sie „01" ans Ende. Ergebnis: „10101".
- Kapitel 3: Nehmen Sie „10101", schneiden Sie die ersten 2 Buchstaben ab („10"), übrig bleibt „101". Kleben Sie „101" ans Ende. Ergebnis: „10101101".
- Kapitel 4: Nehmen Sie das vorherige Ergebnis, schneiden Sie die ersten 3 Buchstaben ab, kleben Sie den Rest ans Ende.

Wenn Sie dies für immer weitermachen, erhalten Sie eine unendliche Kette aus 1en und 0en. Die Arbeit untersucht die verborgenen Eigenschaften dieser unendlichen Kette.

Die großen Entdeckungen

1. Das „wiederkehrende", aber „unvorhersehbare" Muster
Die Arbeit stellt fest, dass diese unendliche Geschichte rekurrent ist. Das bedeutet, wenn Sie irgendwo in der Geschichte einen kleinen Ausdruck finden (wie „1011"), wird genau dieser Ausdruck später immer wieder auftauchen. Sie werden niemals ausgehen, Orte zu finden, an denen er vorkommt.

Allerdings ist sie nicht gleichmäßig rekurrent. Stellen Sie sich das wie ein Lied vor, in dem sich eine bestimmte Note wiederholt, aber die Zeit zwischen den Wiederholungen immer länger wird – so lang, dass Sie möglicherweise eine Million Jahre warten müssten, bis sie das nächste Mal passiert. Die Lücken zwischen den Wiederholungen wachsen so schnell, dass sie fast unendlich werden.

2. Die „Kein-Doppel-Null"-Regel
Das auffälligste Merkmal dieser Folge ist eine strikte Regel: Man kann niemals zwei Nullen nebeneinander finden („00").

Die Arbeit beweist, dass jede Kombination aus 1en und 0en, die kein „00" enthält, schließlich in der Geschichte auftauchen wird.
Wenn Sie versuchen, einen Satz mit „00" zu schreiben, kann er in dieser Folge einfach nicht existieren. Es ist wie in einem Universum, in dem die Gesetze der Physik verbieten, dass zwei Schwarze Löcher sich berühren.

3. Das „explosive" Wachstum von „111..."
Die Arbeit untersucht, wie lange es dauert, bis eine Kette aus lauter 1en erscheint (wie „11", „111", „1111").

„1" erscheint sofort.
„11" erscheint etwas später.
„111" erscheint viel später.
„1111" erscheint weit später.

Die Arbeit berechnet, dass die Position, an der diese Ketten erscheinen, mit erschreckender Geschwindigkeit wächst, beschrieben durch ein mathematisches Konzept namens „Tetration" (wiederholte Exponentiation). Es wächst nicht nur schnell; es wächst so schnell, dass die Anzahl der Ziffern in der Position selbst zu einer Zahl wird, die mehr Ziffern hat als Atome im Universum.

4. Die „Mosaik"-Komplexität
Da die Folge „00" vermeidet, aber alles andere enthält, folgt die Anzahl der einzigartigen Muster einer bestimmten Länge der Fibonacci-Folge (1, 1, 2, 3, 5, 8...).
Die Arbeit kommt zu dem Schluss, dass diese Folge nicht „morphisch" ist. Mit anderen Worten: Man kann diese unendliche Geschichte nicht mit einem einfachen, repetitiven Satz von Anweisungen erzeugen (wie ein Computerprogramm, das einfach sagt: „Ersetze jede 1 durch 10 und jede 0 durch 01"). Die Regeln sind zu subtil und komplex dafür; es erfordert eine komplexere, selbstreferenzielle Logik.

5. Der „Goldene Schnitt" der 1en
Schließlich fragten die Autoren: „Wenn wir die gesamte unendliche Geschichte betrachten, welcher Prozentsatz der Zeichen sind 1en?"

Sie bewiesen, dass dieser Prozentsatz sich auf eine bestimmte Zahl einpendelt (ungefähr 64,5 %).
Noch überraschender bewiesen sie, dass dieser spezifische Prozentsatz eine transzendente Zahl ist. Das bedeutet, es ist eine Zahl, die nicht die Lösung einer einfachen algebraischen Gleichung sein kann (wie die Quadratwurzel aus 2 oder Pi). Es ist eine Zahl mit einem Grad an „mathematischer Seltsamkeit", der selten und tiefgründig ist.

Das Fazit

Die Arbeit nimmt ein einfach klingendes Spiel des „Schneidens und Einfügens" mit Binärzahlen und zeigt, dass es eine Struktur erzeugt, die:

Voll von sich wiederholenden Mustern ist, aber mit Lücken, die sich ins Unendliche erstrecken.
Streng verboten ist, „00" zu haben.
Zu komplex ist, um durch einfache Regeln erzeugt zu werden.
Von einer Dichte an 1en regiert wird, die eine mathematisch „wilde" Zahl ist.

Es ist eine Erinnerung daran, dass selbst die einfachsten Regeln, wenn sie rekursiv angewendet werden, Strukturen von unendlicher Tiefe und Überraschung schaffen können.

Technische Zusammenfassung: Briks Folge: Eine seltsame Rekursion

Problemstellung
Dieser Artikel untersucht die Eigenschaften einer Folge binärer Wörter $(B_i)_{i \ge 1}$ und der daraus resultierenden unendlichen binären Folge $b$ , die durch eine spezifische rekursive Iteration generiert wird, die 2018 von Garo Brik vorgeschlagen wurde. Die Folge ist definiert durch den Basisfall $B_1 = 101$ und die Rekursionsrelation $B_{i+1} = B_i C_i$ für $i \ge 1$ , wobei $C_i$ das Suffix von $B_i$ ist, das durch Entfernen der ersten $i$ Symbole erhalten wird. Da $B_{i-1}$ für alle $i \ge 2$ ein Präfix von $B_i$ ist, konvergieren diese Wörter zu einer eindeutigen unendlichen Folge $b$ . Der Artikel zielt darauf ab, die kombinatorischen und arithmetischen Eigenschaften von $b$ zu charakterisieren, einschließlich seiner Rekurrenz, Faktor-Komplexität, morphischer Natur und der Dichte des Symbols '1'.

Methodik
Die Analyse kombiniert induktive Beweise, kombinatorische Argumente zu Wortfaktoren und Techniken der analytischen Zahlentheorie.

Strukturelle Analyse: Die Autoren bestimmen die Länge der Wörter $B_i$ und ihre Suffixeigenschaften mittels trivialer Induktion. Sie nutzen das Konzept der „Ränder" (Präfixe, die auch Suffixe sind), um zu beweisen, dass bestimmte Indizes „gut" sind, was bedeutet, dass $B_i$ ein Rand von $B_{\ell_i}$ ist.
Rekurrenz und Komplexität: Der Artikel analysiert das Auftreten von Faktoren innerhalb von $b$ , um Rekurrenzeigenschaften zu bestimmen. Er charakterisiert die Menge aller gültigen Faktoren durch die Identifizierung verbotener Teilzeichenketten.
Wachstumsanalyse: Die Startpositionen spezifischer Muster (insbesondere Läufe von $1$'en) werden unter Verwendung einer Rekursionsrelation verfolgt, wobei die Wachstumsraten mit Hilfe der Tetrationsschreibweise von Knuth analysiert werden.
Dichteberechnung: Die Dichte der $1$'en wird durch Analyse der Anzahl der $1$'en in Präfixen der Länge $\ell_n = |B_n|$ abgeleitet. Die Autoren leiten eine Grenzformel her, die die Binärdarstellung der Folge selbst einbezieht, und verwenden eine Fehlerterm-Analyse ( $E(N)$ ), um den Grenzwert von spezifischen Präfixen auf beliebige Präfixe zu erweitern.
Transzendenzbeweis: Um die Natur des Dichtegrenzwerts $\alpha$ zu bestimmen, wendet der Artikel eine vereinfachte Version des „Stottern"-Kriteriums von Adamczewski und Bugeaud an, das die Wiederholungsstruktur einer Folge mit der Transzendenz der durch ihre Binärdarstellung gebildeten Zahl in Beziehung setzt.

Hauptbeiträge und Ergebnisse

Rekurrenzeigenschaften:
- Es wird bewiesen, dass das unendliche Wort $b$ rekurrent ist (jeder endliche Faktor erscheint unendlich oft), aber nicht uniform rekurrent.
- Der Artikel zeigt, dass $b$ beliebig lange Läufe von $1$'en enthält ( $1^n$ für alle $n$ ), was eine uniform Rekurrenz ausschließt. Die Startposition $r_n$ des ersten Auftretens von $1^n$ folgt der Rekursion $r_{n+1} = 2^{r_{n-2}} + r_n$ für $n \ge 2$ , was zu einem extrem schnellen Wachstum (Tetration) führt.
Faktor-Komplexität:
- Eine vollständige Charakterisierung der Faktoren von $b$ wird bereitgestellt: Ein binäres Wort ist genau dann ein Faktor von $b$ , wenn es keine zwei aufeinanderfolgenden $0$'en enthält.
- Folglich ist die Anzahl der verschiedenen Faktoren der Länge $n$ exakt $F_{n+2}$ (die $(n+2)$ -te Fibonacci-Zahl). Dies etabliert, dass $b$ eine exponentielle Faktor-Komplexität aufweist.
Nicht-morphische Natur:
- Basierend auf der exponentiellen Faktor-Komplexität schließt der Artikel, dass $b$ nicht morphisch ist. Dies folgt aus dem Ergebnis von Ehrenfeucht, Lee und Rozenberg, das besagt, dass morphische Folgen eine polynomiale Faktor-Komplexität aufweisen müssen (speziell $O(n^2)$ ).
Dichte der 1'en:
- Der Artikel beweist, dass die asymptotische Dichte der $1$'en in $b$ , bezeichnet als $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$ , existiert.
- Der Wert wird durch die Formel $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$ gegeben, wobei $b_i$ das $i$ -te Bit der Folge ist.
- Der numerische Wert beträgt ungefähr $0,64505878493452$.
Transzendenz:
- Die Dichte $\alpha$ wird als transzendent bewiesen. Der Beweis stützt sich darauf zu zeigen, dass die zugehörige Zahl $\beta = \sum b_i 2^{-i}$ unter Verwendung des Stottern-Kriteriums transzendent ist. Da $\beta$ nicht rational sein kann (da dies eine beschränkte Faktor-Komplexität implizieren würde) und die Folge die erforderliche „Stottern"-Struktur aufweist ( $B_{n+1}$ enthält $B_n$ gefolgt von einer Wiederholung eines Suffixes), muss $\beta$ (und somit $\alpha$ ) transzendent sein.

Bedeutung und Behauptungen
Der Artikel präsentiert eine Folge, die, obwohl sie durch eine einfache iterative Regel definiert ist, subtile und komplexe Eigenschaften aufweist, die nicht unmittelbar offensichtlich sind. Die primäre Bedeutung liegt in der Entdeckung einer Folge, die rekurrent, aber nicht uniform rekurrent ist, eine exponentielle Faktor-Komplexität besitzt und eine transzendente Dichte von $1$'en erzeugt. Die Autoren bemerken, dass die Folge in der OEIS erscheint (als A334820, wobei der Anfangsterm fehlt), und heben das Wechselspiel zwischen der rekursiven Definition und den daraus resultierenden arithmetischen Eigenschaften hervor.

Der Artikel erkennt ausdrücklich an, dass diese Ergebnisse durch Experimente mit APL und die Zusammenarbeit mit ChatGPT 5.5 im Mai 2026 erzielt wurden, wobei alle Behauptungen anschließend vom Autor umgeschrieben und verifiziert wurden. Die Arbeit dient als Fallstudie für die Eigenschaften rekursiv definierter binärer Wörter und die Anwendung von Transzendenzkriterien auf kombinatorische Folgen.

Die Geschichtenerzähl-Regel

Die großen Entdeckungen

Das Fazit

Mehr davon