Brik's sequence: a strange recursion

Technische Samenvatting: Brik's Reeks: Een vreemde recursie

Probleemstelling
Dit artikel onderzoekt de eigenschappen van een reeks binaire woorden $(B_i)_{i \ge 1}$ en het resulterende oneindige binaire getal $b$, gegenereerd door een specifieke recursieve iteratie voorgesteld door Garo Brik in 2018. De reeks wordt gedefinieerd door het basisgeval $B_1 = 101$ en de recurrente relatie $B_{i+1} = B_i C_i$ voor $i \ge 1$, waarbij $C_i$ het achtervoegsel van $B_i$ is verkregen door de eerste $i$ symbolen te verwijderen. Aangezien $B_{i-1}$ een voorvoegsel is van $B_i$ voor alle $i \ge 2$, convergeren deze woorden naar een unieke oneindige reeks $b$. Het artikel tracht de combinatorische en rekenkundige eigenschappen van $b$ te karakteriseren, waaronder zijn recurrentie, factorcomplexiteit, morfische aard en de dichtheid van het symbool '1'.

Methodologie
De analyse maakt gebruik van een combinatie van inductieve bewijzen, combinatorische argumenten over woordfactoren en technieken uit de analytische getaltheorie.

• Structurele Analyse: De auteurs stellen de lengte van de woorden $B_i$ en hun achtervoegseleigenschappen vast via triviale inductie. Zij maken gebruik van het concept van "randen" (voorvoegsels die ook achtervoegsels zijn) om te bewijzen dat specifieke indices "goed" zijn, wat betekent dat $B_i$ een rand is van $B_{\ell_i}$.
• Recurrentie en Complexiteit: Het artikel analyseert het voorkomen van factoren binnen $b$ om recurrentie-eigenschappen te bepalen. Het karakteriseert de verzameling van alle geldige factoren door verboden substrings te identificeren.
• Groeianalyse: De startposities van specifieke patronen (specifiek reeksen van $1$'s) worden bijgehouden met behulp van een recurrente relatie, waarbij groeisnelheden worden geanalyseerd met behulp van Knuth's tetratienotatie.
• Dichtheidsberekening: De dichtheid van $1$'s wordt afgeleid door het aantal $1$'s te analyseren in voorvoegsels van lengte $\ell_n = |B_n|$. De auteurs leiden een limietformule af die de binaire expansie van de reeks zelf omvat en maken gebruik van fouttermenanalyse ($E(N)$) om de limiet van specifieke voorvoegsels uit te breiden naar willekeurige voorvoegsels.
• Transcendentiebewijs: Om de aard van de dichtheidslimiet $\alpha$ te bepalen, past het artikel een vereenvoudigde versie toe van het "stotterende" criterium van Adamczewski en Bugeaud, dat de herhalingsstructuur van een reeks relateert aan de transcendentie van het getal gevormd door zijn binaire expansie.

Belangrijkste Bijdragen en Resultaten

1. Recurrente Eigenschappen:

   • Het oneindige woord $b$ wordt bewezen recurrent te zijn (elke eindige factor komt oneindig vaak voor), maar niet uniform recurrent.
   • Het artikel toont aan dat $b$ willekeurig lange reeksen van $1$'s bevat ($1^n$ voor alle $n$), wat uniform recurrentie uitsluit. De startpositie $r_n$ van de eerste voorkoming van $1^n$ volgt de recurrentie $r_{n+1} = 2^{r_{n-2}} + r_n$ voor $n \ge 2$, wat leidt tot extreem snelle groei (tetratie).

2. Factorcomplexiteit:

   • Er wordt een volledige karakterisering gegeven van de factoren van $b$: een binair woord is een factor van $b$ dan en slechts dan als het geen twee opeenvolgende $0$'s bevat.
   • Bijgevolg is het aantal onderscheiden factoren van lengte $n$ exact $F_{n+2}$ (het $(n+2)$-de Fibonacci-getal). Dit vestigt dat $b$ exponentiële factorcomplexiteit heeft.

3. Niet-morfische Aard:

   • Gebaseerd op de exponentiële factorcomplexiteit concludeert het artikel dat $b$ niet morfisch is. Dit volgt uit het resultaat van Ehrenfeucht, Lee en Rozenberg, dat stelt dat morfische reeksen polynoomfactorcomplexiteit moeten hebben (specifiek $O(n^2)$).

4. Dichtheid van 1's:

   • Het artikel bewijst dat de asymptotische dichtheid van $1$'s in $b$, aangeduid als $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$, bestaat.
   • De waarde wordt gegeven door de formule $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$, waarbij $b_i$ het $i$-de bit van de reeks is.
   • De numerieke waarde is ongeveer $0,64505878493452$.

5. Transcendentie:

   • De dichtheid $\alpha$ wordt bewezen transcendent te zijn. Het bewijs berust op het aantonen dat het bijbehorende getal $\beta = \sum b_i 2^{-i}$ transcendent is met behulp van het stotterende criterium. Aangezien $\beta$ niet rationeel kan zijn (aangezien dat beperkte factorcomplexiteit zou impliceren), en de reeks de vereiste "stotterende" structuur vertoont ($B_{n+1}$ bevat $B_n$ gevolgd door een herhaling van een achtervoegsel), moet $\beta$ (en dus $\alpha$) transcendent zijn.

Betekenis en Claims
Het artikel presenteert een reeks die, hoewel gedefinieerd door een eenvoudige iteratieve regel, subtiele en complexe eigenschappen vertoont die niet onmiddellijk voor de hand liggen. De primaire betekenis ligt in de ontdekking van een reeks die recurrent is maar niet uniform recurrent, exponentiële factorcomplexiteit bezit en een transcendent dichtheid van $1$'s genereert. De auteurs merken op dat de reeks voorkomt in de OEIS (als A334820, waarbij het eerste lid ontbreekt) en benadrukken de wisselwerking tussen de recursieve definitie en de resulterende rekenkundige eigenschappen.

Het artikel erkent uitdrukkelijk dat deze resultaten werden verkregen door experimenten met APL en samenwerking met ChatGPT 5.5 in mei 2026, waarbij alle claims vervolgens door de auteur werden herschreven en geverifieerd. Het werk dient als een casestudie in de eigenschappen van recursief gedefinieerde binaire woorden en de toepassing van transcendentiecriteria op combinatorische reeksen.