Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

Deze collegeaantekeningen bieden een inleiding tot de combinatoriek van woorden met een lage factorcomplexiteit, waarbij wordt onderzocht hoe 'niet-triviale' oneindige woorden kunnen worden gedefinieerd en gekarakteriseerd, met name aan de hand van klassieke objecten zoals Sturmiaanse woorden en een nieuwe algebraïsche bewijsvoering voor een stelling van Tijdeman.

De kern

Infinite Words met een heel lage complexiteit: Een Reis door de Wiskunde van Patronen

Stel je voor dat je een oneindig lang touw hebt, bedekt met gekleurde kralen. Je kunt dit touw in verschillende kleuren kiezen: 2 kleuren (bijvoorbeeld rood en blauw), 3 kleuren, of zelfs 100 kleuren. De vraag die deze tekst onderzoekt is: Hoe "saai" of hoe "chaotisch" kan zo'n oneindig touw zijn?

De auteur, Mélodie Andrieu, neemt ons mee op een reis door de wiskundige wereld van "woorden" (reeksen van letters) en laat zien hoe we de complexiteit van deze patronen kunnen meten.

Hier is een samenvatting in begrijpelijk Nederlands, vol met analogieën.

1. De Basis: Hoe tellen we complexiteit?

Stel je voor dat je door een oneindig lange tekst loopt met een vergrootglas dat precies n letters tegelijk kan zien.

• Als je n = 1 doet, tel je hoeveel verschillende letters er zijn.
• Als je n = 2 doet, tel je hoeveel verschillende tweetallen (zoals "AB", "AA", "BA") er voorkomen.
• Als je n = 3 doet, tel je de drietallen, enzovoort.

Dit aantal noemen we de complexiteit.

• Een tekst die alleen maar "AAAAA..." is, heeft een zeer lage complexiteit. Er is maar 1 soort letter, 1 soort tweetal, 1 soort drietal. Het is saai en voorspelbaar.
• Een tekst die willekeurig is (zoals een willekeurige reeks cijfers van $\pi$), heeft een zeer hoge complexiteit. Er zijn bijna net zo veel verschillende patronen als er mogelijk zijn.

2. Het Grote Geheim van de Twee Kleuren (Sturmiaanse Woorden)

In de jaren 30 ontdekten wiskundigen Morse en Hedlund een fascinerend geheim voor teksten met slechts 2 kleuren (bijv. 0 en 1):

• Als een tekst niet volledig periodiek is (dus niet simpelweg "010101..." herhaalt), dan moet hij op zijn minst n + 1 verschillende patronen van lengte n hebben.
• De "minimaal interessante" teksten zijn diegene die precies n + 1 patronen hebben. Deze noemen we Sturmiaanse woorden.

De Analogie:
Stel je voor dat je een bal op een vierkante tafel laat stuiteren (een biljarttafel). Als je de bal onder een heel specifiek, "irrationeel" hoekje gooit (een hoek die je niet kunt schrijven als een breuk, zoals $\sqrt{2}$), zal de bal nooit precies dezelfde route twee keer afleggen, maar wel een prachtig, niet-willekeurig patroon vormen.
Sturmiaanse woorden zijn de code van zo'n biljartbal. Ze zijn niet saai (periodiek), maar ook niet chaotisch. Ze zijn de "perfecte balans" tussen orde en chaos. Ze zijn verbonden met de Gouden Snede (een beroemd getal in de natuur) en met het breken van getallen in breuken (kettingbreuken).

3. Wat als we meer dan 2 kleuren hebben? (De uitdaging)

Nu wordt het lastig. Wat gebeurt er als we 3, 4 of meer kleuren hebben?
De oude regel (n + 1) werkt niet meer. Als je gewoon een extra kleur toevoegt aan een Sturmiaans woord, krijg je een tekst die technisch gezien "minimaal complex" is, maar die eigenlijk saai is: de extra kleur komt maar één keer voor en verdwijnt dan. Dat is niet interessant.

De tekst stelt een nieuwe, strengere voorwaarde:
Om echt "interessant" te zijn, moeten alle kleuren oneindig vaak voorkomen, en moeten hun verhoudingen wiskundig onafhankelijk zijn.

• Analogie: Stel je een orkest voor. Als de viool (kleur 1) en de cello (kleur 2) spelen, en hun snelheden hebben een verhouding die je niet kunt uitdrukken als een breuk (zoals 1 tegen $\sqrt{2}$), dan ontstaat er een mooi, nooit herhalend patroon. Als de verhouding wel een breuk is (bijv. 1 tegen 2), vallen ze na een tijdje weer samen in een saai ritme.

4. Het Theorema van Tijdeman: De Nieuwe Wet

In 1999 bewees de wiskundige Tijdeman wat de minimale complexiteit is voor deze interessante, meerkleurige teksten.

• Voor 2 kleuren was de formule: $n + 1$.
• Voor d kleuren is de formule: $(d - 1)n + 1$.

Wat betekent dit?
Het betekent dat als je 3 kleuren hebt, de complexiteit lineair groeit met $2n + 1$. Als je 10 kleuren hebt, groeit het met$9n + 1$.
Dit is de "ondergrens" van chaos. Alles wat minder complex is dan dit, is wiskundig gezien "saai" of "periodiek", zelfs als het er op het eerste gezicht ingewikkeld uitziet.

5. De Nieuwe Wiskundige Sleutel: De "Stroom" (Flow)

De tekst introduceert een gloednieuwe manier (uit 2022) om dit te bewijzen, ontwikkeld door de auteur en haar collega J. Cassaigne.

In plaats van alleen te tellen, kijken ze naar stromen (flow).

• De Analogie: Stel je voor dat de letters in het woord waterdruppels zijn die door een buizensysteem (een grafiek) stromen.
• Ze bouwen een stroommatrix (een soort rekenblad).
• Ze gebruiken regels uit de elektriciteit (Kirchhoff's wet): "Wat erin komt, moet eruit gaan."
• Door te kijken naar hoe deze stroom zich gedraagt in een wiskundige ruimte, kunnen ze bewijzen dat als de complexiteit te laag is, de "waterdruppels" (de letters) niet onafhankelijk genoeg kunnen stromen. Ze worden gedwongen om in een saai patroon te vallen.

6. Waarom is dit belangrijk? (De "Boom"-structuur)

Een van de mooiste resultaten van deze nieuwe bewijstechniek is dat alle teksten die aan deze minimale complexiteit voldoen, een speciale structuur hebben die dendrisch wordt genoemd.

• De Analogie: "Dendrisch" betekent "boom-achtig".
• Stel je voor dat je een woord bekijkt en probeert te voorspellen welke letter er daarna komt. Bij een "dendrisch" woord is er voor elke stap in het patroon precies één manier om terug te keren of verder te gaan, zonder dat er ingewikkelde lussen of kringen ontstaan. Het is als een boom: je kunt de takken volgen, maar je komt nooit in een kring terug waar je al was.
• Dit betekent dat deze "minimaal complexe" teksten een heel strakke, organische structuur hebben, net als de takken van een boom of de aderen in een blad.

Conclusie

Deze tekst is een gids voor studenten en onderzoekers die willen begrijpen hoe we de grens tussen chaos en orde kunnen meten in oneindige patronen.

• Vroeger: We wisten dat bij 2 kleuren de "Sturmiaanse woorden" de koninginnen waren van lage complexiteit.
• Nu: We weten dat bij meer kleuren de wet van Tijdeman geldt: $(d-1)n + 1$.
• De Nieuwe Wiskunde: We gebruiken nu "stroommatrices" en "waterdruppels" om te bewijzen dat deze patronen niet willekeurig zijn, maar een prachtige, boom-achtige structuur hebben die verbonden is met de diepste eigenschappen van getallen en beweging.

Kortom: Zelfs in een oneindig lange reeks van letters, als je kijkt naar de patronen, zie je een verborgen schoonheid en structuur die door de wiskunde perfect kan worden beschreven.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van de lezingnotities "Infinite Words with very Low Factor Complexity" van Mélodie Andrieu, geschreven in het Nederlands.

Titel: Oneindige Woorden met Zeer Lage Factorcomplexiteit: Een Inleiding tot Combinatoriek op Woorden

Auteur: Mélodie Andrieu
Datum: December 2025 (gepubliceerd op arXiv in maart 2026)
Context: Gebaseerd op lezingen tijdens de 7e editie van de conferentie Dyadisc (Valparaíso, Chili) en seminars sinds 2023.

---

1. Het Probleem en de Doelstelling

De kern van dit werk ligt in de combinatoriek op woorden, met name de studie van oneindige woorden over een eindig alfabet en hun factorcomplexiteit. De complexiteit $p_w(n)$ van een oneindig woord $w$ is het aantal unieke subwoorden (factoren) van lengte $n$ dat in $w$ voorkomt.

De centrale vragen die het paper adresseert zijn:

1. Wat is de minimale complexiteit van een "niet-triviaal" oneindig woord over een $d$-letterig alfabet?
2. Hoe moet "niet-trivialiteit" formeel worden gedefinieerd voor $d \geq 3$?
3. Welke woorden bereiken deze minimale complexiteit en wat zijn hun structurele eigenschappen?

Voor het binaire geval ($d=2$) is dit probleem sinds de jaren 40 volledig opgelost door het werk van Morse en Hedlund: niet-periodieke woorden hebben een minimale complexiteit van $n+1$, en de woorden die dit bereiken zijn de Sturmiaanse woorden. Het uitdaging in dit paper is om deze resultaten te generaliseren naar grotere alfabetten ($d \geq 3$).

---

2. Methodologie

Het paper gebruikt een combinatie van combinatorische, algebraïsche en dynamische systemen-methoden:

• Combinatorische Analyse: Gebruik van begrippen zoals factoren, rechts- en links-specifieke factoren, en de structuur van Rauzy-graafjes (gericht graafjes waarbij knopen factoren van lengte $n$ zijn en randen factoren van lengte $n+1$).
• Algebraïsche Benadering (Nieuw): De auteur introduceert een conceptueel nieuwe, zuiver algebraïsche bewijsvoering voor een bestaand stelling. Dit maakt gebruik van stroommatrices (flow matrices), die zijn gebaseerd op Kirchhoffs koppelingsregel voor elektrische circuits, toegepast op de Rauzy-graafjes.
• Dynamische Systemen: Koppeling van woorden aan dynamische systemen zoals rotaties op een cirkel, billiard-trajecten op een vierkant, en lineaire stromen op een torus.
• Getaltheorie: Gebruik van kettingbreuken (voor $d=2$) en het concept van rationele onafhankelijkheid van letterfrequenties.

---

3. Belangrijkste Bijdragen en Resultaten

Het paper is opgedeeld in drie hoofdstukken met de volgende bijdragen:

Hoofdstuk 1: De Klassieke Basis (Morse-Hedlund en Sturmiaanse Woorden)

• Morse-Hedlund Stelling (1938): Een oneindig woord is uiteindelijk periodiek dan en slechts dan als zijn complexiteit begrensd is. Als het woord niet-periodiek is, geldt $p_w(n) \geq n+1$.
• Sturmiaanse Woorden: Dit zijn de binaire woorden met exacte complexiteit $p_w(n) = n+1$.
• Verbinding met Kettingbreuken: De auteur toont aan dat Sturmiaanse woorden nauw verbonden zijn met kettingbreuken. De verhouding van de letterfrequenties ($f_1/f_2$) is een irrationaal getal, en de "run-length" sequentie van een renormalisatieproces op het woord correspondeert met de partiële quotiënten van de kettingbreuk van deze verhouding.
• Constructie: Sturmiaanse woorden kunnen efficiënt worden geconstrueerd via substituties ($\sigma_1, \sigma_2$) die gekoppeld zijn aan de kettingbreuk.

Hoofdstuk 2: Generalisatie naar $d$-letterige Alfabetten (Tijdeman's Stelling)

• Het Definities-probleem: Voor $d \geq 3$ is "niet-eindig periodiek" onvoldoende om interessante woorden te karakteriseren. Er bestaan "quasi-Sturmiaanse" woorden met lage complexiteit ($n+d-1$) die echter kunstmatig zijn (bijv. een Sturmiaans woord voorafgegaan door een vaste reeks letters).
• Rationele Onafhankelijkheid: De auteur stelt voor dat de juiste voorwaarde voor "niet-trivialiteit" de rationele onafhankelijkheid van de letterfrequenties is. Dit betekent dat de frequenties lineair onafhankelijk zijn over $\mathbb{Q}$.
• Tijdeman's Stelling (1999): R. Tijdeman bewees dat voor een $d$-letterig woord met rationeel onafhankelijke frequenties, de minimale complexiteit lineair is:
  $$p_w(n) \geq (d-1)n + 1$$
  Er bestaan woorden die deze ondergrens bereiken.
• Versterkte Versie (2022): De auteur en J. Cassaigne hebben een versterkte versie van Tijdeman's stelling bewezen. In plaats van te kijken naar de minimale graad van irrationaliteit ($\delta_w$), gebruiken ze de maximale graad van irrationaliteit ($\Delta_w$) van de frequenties. De ondergrens wordt dan:
  $$p_w(n) \geq (\Delta_w - 1)(n - 1) + d$$
  Dit is een scherpere schatting voor woorden waar de frequenties niet bestaan of variëren.

Hoofdstuk 3: Een Nieuw Algebraïsch Bewijs en Dendrische Structuur

• Algebraïsch Bewijs: In plaats van Tijdeman's oorspronkelijke combinatorische bewijs, bieden de auteurs een bewijs gebaseerd op lineaire algebra.
  • Ze definiëren de stroommatrix $M$ voor een Rauzy-graafje.
  • Ze analyseren de dimensie van de kern van deze matrix ($\ker(M)$) en gebruiken de rang-nulliteitstelling.
  • Ze tonen aan dat de vector van pseudo-frequenties van factoren in de kern van de stroommatrix ligt.
  • Door de dimensie van deze kern te relateren aan de complexiteit, leiden ze de ongelijkheid af.
• Dendrische Woorden: Een cruciale bijdrage is het bewijs dat alle oneindige $d$-letterige woorden met rationeel onafhankelijke frequenties en minimale complexiteit $(d-1)n+1 dendrisch zijn.
  • Een woord is dendrisch als het uitbreidingsgraafje (extension graph) van elke factor een boom is.
  • Dit resulteert in een karakterisering: De verzameling van woorden met minimale complexiteit en rationeel onafhankelijke frequenties coïncideert met de verzameling van dendrische woorden met deze frequenties.

---

4. Significatie en Impact

1. Unificatie van Gebieden: Het paper verbindt succesvol combinatoriek op woorden, lineaire algebra (via stroommatrices), en getaltheorie (kettingbreuken en rationele onafhankelijkheid).
2. Oplossing van een Open Probleem: Het biedt een versterkte versie van Tijdeman's stelling en een volledig algebraïsch bewijs, wat een nieuw perspectief biedt op een klassiek resultaat.
3. Karakterisering van Minimale Complexiteit: Voor $d \geq 3$ was het onduidelijk welke woorden de minimale complexiteit bereikten. Het paper toont aan dat deze woorden noodzakelijk dendrisch zijn. Dit is een belangrijke stap naar een volledige classificatie, vergelijkbaar met de rol van Sturmiaanse woorden voor $d=2$.
4. Nieuw Bewijsinstrument: De introductie van stroommatrices en de toepassing van Kirchhoffs regels op de structuur van woorden biedt een krachtig nieuw gereedschap voor toekomstig onderzoek in de combinatoriek op woorden.

Samenvattend biedt dit paper een diepgaande inleiding tot de theorie van oneindige woorden met lage complexiteit, generaliseert het fundamentele stellingen naar grotere alfabetten, en introduceert het nieuwe algebraïsche methoden die leiden tot een scherpere karakterisering van de structuur van deze woorden.