The complexity of finite smooth words over binary alphabets

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een oneindig lang verhaal schrijft, maar met een heel rare regel: je mag alleen twee letters gebruiken, laten we zeggen "A" en "B". Maar hier is de truc: je mag niet zomaar willekeurig schrijven. Je moet een soort "spiegel" of "code" volgen die bepaalt hoe vaak je een letter herhaalt.

Dit is wat wiskundigen smooth words (gladde woorden) noemen. Het bekendste voorbeeld is een woord dat gemaakt is met alleen 1'en en 2'en, waarbij de cijfers aangeven hoe lang de blokken zijn. Bijvoorbeeld: "22" betekent twee 1'en, "11" betekent twee 2'en, enzovoort. Het is als een Russisch poppetje dat oneindig in elkaar steekt.

De vraag die wiskundigen al decennia stellen, is: Hoe complex is dit verhaal? Als je naar een stukje van dit verhaal kijkt, hoeveel verschillende stukjes (subwoorden) kun je vinden als je de lengte vergroot? Is het een simpel, voorspelbaar verhaal, of een chaotisch, onbegrijpelijk gedoe?

De auteurs van dit paper, Julien Cassaigne en Raphaël Henry, hebben een nieuw licht op deze vraag geworpen. Hier is wat ze hebben ontdekt, vertaald naar alledaags taal:

1. De "Grote Droom" en de "Kleine Steentjes"

De wiskundigen wilden oorspronkelijk het gedrag van het hele oneindige verhaal begrijpen. Maar dat is als proberen een heel bos te bestuderen door naar elke boom te kijken; te lastig!

Dus hebben ze een slimme truc bedacht: ze kijken niet naar het hele verhaal, maar alleen naar de kleine steentjes (de eindige stukjes) die eruit kunnen vallen. Ze noemen deze steentjes f-smooth words.

De ontdekking: Ze bewezen dat als je het hele oneindige verhaal goed bekijkt, het precies uit dezelfde soort steentjes bestaat als deze kleine verzameling. Het is alsof je ontdekt dat het hele bos precies uit dezelfde soort bladeren bestaat als de stapel bladeren die je op de grond hebt gevonden. Dit betekent dat je het hele bos kunt begrijpen door alleen die stapel bladeren te tellen.

2. De "Groeisnelheid" van het Woord

Nu de vraag: Hoe snel groeit het aantal verschillende steentjes naarmate je langer kijkt?

Als je een heel simpel woord hebt (zoals "ABABAB..."), groeit het aantal nieuwe stukjes heel langzaam (lineair).
Als je een heel chaotisch woord hebt, groeit het aantal exponentieel (explosief).
De auteurs denken dat deze "gladde woorden" ergens in het midden zitten. Ze groeien sneller dan lineair, maar niet zo snel als een explosie. Ze noemen dit een polynoom-groei.

Ze hebben een formule bedacht die voorspelt hoe snel dit groeit, afhankelijk van welke letters je gebruikt (bijvoorbeeld 1 en 2, of 3 en 5).

3. Het Verschil tussen "Even" en "Oneven"

Hier wordt het interessant, met een mooie analogie:

Het Even Geval (bijv. 2 en 4): Stel je voor dat je een symmetrische brug bouwt. Alles zit perfect in balans. De auteurs hebben bewezen dat voor deze "even" combinaties, hun voorspelling over de groeisnelheid 100% klopt. Het gedrag is voorspelbaar en mooi.
Het Oneven Geval (bijv. 1 en 3): Dit is als een brug die een beetje scheef staat. Het is nog steeds een brug, maar het gedrag is wat raarder. Hier hebben ze laten zien dat de groei minimaal zo snel gaat als ze dachten (een ondergrens), maar ze hebben ook een nieuwe, betere schatting gemaakt voor de maximale snelheid (een bovengrens). Het is alsof ze zeggen: "We weten zeker dat het niet trager gaat dan X, en we weten dat het niet sneller gaat dan Y, en Y is veel kleiner dan wat we eerder dachten."

4. Een Foutje in de Geschiedenis

In de inleiding vertellen ze ook over een eerdere poging van een andere onderzoeker (Huang) die dacht een oplossing te hebben gevonden. Het bleek dat die persoon een verkeerde "rekenmachine" (een definitie) had gebruikt. Het was alsof iemand probeerde de hoogte van een berg te meten met een liniaal die in feite een touw was. De auteurs hebben dit foutje opgelost en laten zien waarom de eerdere berekeningen niet klopten.

Samenvattend

Deze paper is als het vinden van de blauwdruk van een mysterieus, oneindig patroon.

Ze hebben bewezen dat je het patroon kunt begrijpen door alleen de kleine stukjes te tellen.
Ze hebben een formule gevonden die precies beschrijft hoe snel het patroon complexer wordt.
Voor sommige lettercombinaties (de "even" ones) is de formule perfect. Voor de andere (de "oneven" ones) hebben ze de schattingen flink verbeterd.

Het is een stukje wiskundig detectivewerk dat ons helpt begrijpen hoe complexe, oneindige patronen in de natuur (of in de wiskunde) eigenlijk werken. Het laat zien dat zelfs in de meest abstracte "woorden", er een diepe, regelmatige structuur schuilgaat.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "The complexity of finite smooth words over binary alphabets" van Julien Cassaigne en Raphaël Henry, vertaald en samengevat in het Nederlands.

Titel: De complexiteit van eindige gladde woorden over binaire alfabetten

1. Probleemstelling en Context

Het artikel richt zich op de combinatoriek van woorden, met name op het bestuderen van gladde woorden (smooth words). Een bekend voorbeeld is het Oldenburger-Kolakoski-woord ( $\kappa$ ) over het alfabet $\{1, 2\}$ , dat een vast punt is van de run-length encoding (het tellen van opeenvolgende gelijke tekens).

De centrale uitdaging is het beschrijven van de factorcomplexiteit (het aantal unieke substrings van lengte $n$ ) van deze woorden.

Gladde woorden ( $C^\infty$ ): Oneindige woorden die oneindig vaak "afgeleid" kunnen worden via run-length encoding.
Eindig gladde woorden ( $C^\infty_f$ of f-smooth): Een eindige versie van deze woorden, geïntroduceerd door Dekking. Het is bekend dat alle factoren van gladde woorden f-smooth zijn, maar de omgekeerde relatie en de exacte complexiteit waren lange tijd onopgelost.

Er bestaat een conjectuur van Sing (gebaseerd op werk van Dekking) dat de complexiteit $p_{C^\infty_f}(n)$ groeit als $\Theta(n^\rho)$ , waarbij $\rho = \frac{\log(a+b)}{\log((a+b)/2)}$ voor een binaal alfabet $\{a, b\}$ . Eerdere resultaten gaven alleen polynoombovengrenzen en -ondergrenzen, maar geen exacte asymptotische gedraging voor alle gevallen.

Daarnaast was er verwarring veroorzaakt door een fout in een eerdere publicatie van Huang ([11]), die een verkeerde definitie van de afgeleide gebruikte, wat leidde tot onjuiste complexiteitsconjecturen.

2. Methodologie

De auteurs hanteren een strikt combinatorisch en algebraïsch kader:

Definitie van Derivatie: Ze definiëren formele afgeleiden voor zowel oneindige als eindige woorden. Voor eindige woorden gebruiken ze een operator $D_f$ die de run-length encoding simuleert, maar met specifieke randvoorwaarden (de "cut"-functie) om te garanderen dat het woord binnen het alfabet blijft.
Relatie tussen $C^\infty$ en $C^\infty_f$ : Ze introduceren een nieuwe klasse van woorden, r-smooth woorden ( $C^\infty_r$ ), die fungeren als voorvoegsels (prefixen) van gladde woorden.
Bispeciale Factoren: De kern van de complexiteitsanalyse ligt in het tellen van bispeciale factoren (woorden die zowel links als rechts op meerdere manieren kunnen worden uitgebreid). De complexiteit wordt berekend via de som van de multipliciteiten van deze bispeciale factoren (gebaseerd op Theorem 1.5).
Boomstructuur: De bispeciale f-smooth woorden worden georganiseerd in oneindige binaire bomen ( $T, T^{(1)}, \dots, T^{(4)}$ ) gegenereerd door "primitieven" ( $P_{f,a}$ en $P_{f,b}$ ).
Spectrale Analyse: Voor het bepalen van de groei van de lengte van deze woorden in de bomen, gebruiken ze lineaire algebra. Ze definiëren matrices ( $M, P, N$ ) die de evolutie van het aantal letters op even en oneven posities beschrijven. De groei wordt bepaald door de spectrale straal (dominante eigenwaarde) van deze matrices.

3. Belangrijkste Bijdragen en Resultaten

A. Gelijkheid van Talen (Theorema 1.31)

De auteurs bewijzen dat over elk binaal alfabet $\{a, b\}$ , de verzameling van factoren van oneindige gladde woorden ( $L(C^\infty)$ ) exact gelijk is aan de verzameling van eindig gladde woorden ( $C^\infty_f$ ).

Consequentie: De factorcomplexiteit van gladde woorden is identiek aan die van f-smooth woorden: $p_{C^\infty}(n) = p_{C^\infty_f}(n)$ . Dit bevestigt de relevantie van het bestuderen van de eindige versie voor het begrijpen van de oneindige woorden.

B. Correctie van Eerdere Fouten

Ze identificeren en corrigeren een fundamentele fout in het werk van Huang ([11]). Huang gebruikte een verkeerde definitie van de afgeleide die leidde tot een grotere verzameling "woorden" en onjuiste exponenten voor de complexiteit. Dit artikel herstelt de correcte definitie en de daaruit voortvloeiende resultaten.

C. Asymptotische Complexiteit (Theorema 1.32 en 1.33)

De auteurs maken aanzienlijke vooruitgang in het bewijzen van Sing's conjectuur over de complexiteit $p_{C^\infty_f}(n) = \Theta(n^\rho)$ :

Ondergrens (Alle alfabetten): Ze bewijzen dat $p_{C^\infty_f}(n) = \Omega(n^\rho)$ voor elk binaal alfabet (zowel even als oneven).
Bovengrens en Exacte Groei (Even alfabetten): Voor alfabetten waar $a+b$ even is (bijv. $\{1, 2\}$ of $\{2, 4\}$ ), bewijzen ze dat $p_{C^\infty_f}(n) = \Theta(n^\rho)$ . Hiermee is de conjectuur voor even alfabetten volledig opgelost.
Verbeterde Bovengrens (Oneven alfabetten): Voor alfabetten waar $a+b$ $a + b$ oneven is (bijv. $\{1, 3\}$ ${1, 3}$ of $\{3, 5\}$ ${3, 5}$ ), bewijzen ze een nieuwe bovengrens $p_{C^\infty_f}(n) = O(n^\zeta)$ $p_{C_{f}^{\infty}} (n) = O (n^{ζ})$ .
- De exponent $\zeta$ is strikt kleiner dan de eerdere bovengrens $\beta$ uit Theorem 1.21.
- Hoewel $\zeta$ niet exact gelijk is aan de conjectuur $\rho$ (wat suggereert dat de exacte complexiteit voor oneven alfabetten mogelijk subtieler is of dat de methode nog niet scherp genoeg is), is het een aanzienlijke verbetering.

4. Significatie en Implicaties

Unificatie: Het artikel verenigt de theorie van gladde woorden over verschillende alfabetten door te tonen dat de structuur van factoren universeel is ( $L(C^\infty) = C^\infty_f$ ), ondanks verschillen in recurrentie en letterfrequenties.
Methodologische Doorbraak: Door de overgang van het tellen van bispeciale woorden naar het analyseren van de groei van boomgeneraties via spectrale matrixtheorie, bieden de auteurs een krachtig nieuw instrument voor het bestuderen van woordcomplexiteit.
Dichotomie: Het werk benadrukt een fundamenteel onderscheid tussen even en oneven alfabetten:
- Bij even alfabetten gedraagt de complexiteit zich voorspelbaar volgens de conjectuur.
- Bij oneven alfabetten is de structuur "pathologischer" (er zijn gladde woorden die niet alle f-smooth woorden bevatten), en de complexiteitsgroei is moeilijker te karakteriseren, hoewel de nieuwe bovengrens een grote stap voorwaarts is.
Foutcorrectie: Het artikel corrigeert de literatuur door de onjuiste resultaten van Huang te ontkrachten, wat essentieel is voor toekomstig onderzoek op dit gebied.

Kortom, dit artikel levert de meest complete analyse tot nu toe van de factorcomplexiteit van gladde woorden, lost het probleem volledig op voor even alfabetten en biedt de sterkste tot nu toe bekende resultaten voor oneven alfabetten.