Dyck Words, Pattern Avoidance, and Automatic Sequences

Dit artikel onderzoekt Dyck-woorden in binaire rijen, waarbij wordt aangetoond dat $7/3$-vrije woorden een beperkte nestingsdiepte hebben, en biedt een expliciete karakterisering en telling van Dyck-factoren in het woord van Thue-Morse.

De kern

Hier is een samenvatting van het onderzoek in eenvoudig Nederlands, met behulp van creatieve metaforen om de wiskundige concepten begrijpelijk te maken.

De Balans van de Haakjes: Een Reis door de Wiskunde van Parentheses

Stel je voor dat je een taal spreekt die alleen uit twee letters bestaat: 0 en 1. In dit onderzoek behandelen we de 0 als een open haakje ( en de 1 als een sluitend haakje ).

Een Dyck-woord is dan simpelweg een zinnetje in deze taal dat perfect in balans is. Denk aan een zinnetje als (()) of ()(). Alles is gesloten, er hangt niets in de lucht. Maar (() is geen goed Dyck-woord, want er hangt een haakje open. En )( is ook fout, want je begint met sluiten voordat je hebt geopend.

De onderzoekers (Lucas Mol, Narad Rampersad en Jeffrey Shallit) kijken naar hoe deze perfecte haakjes-zinnen zich gedragen in verschillende oneindige rijen van 0'en en 1'en. Ze stellen zich vragen als: "Hoe diep kunnen we in deze haakjes nesten?" en "Hoe vaak komen deze perfecte zinnen voor?"

Hier zijn de belangrijkste ontdekkingen, vertaald naar alledaagse taal:

1. De "7/3-regel": Hoeveel herhaling is te veel?

Stel je voor dat je een rijtje letters hebt dat je steeds weer herhaalt. Als je een woord te vaak herhaalt, wordt het saai en onnatuurlijk. Wiskundigen noemen dit een "macht".

• De ontdekking: De onderzoekers ontdekten dat als je een rijtje maakt dat niet te vaak herhaalt (minder dan 2,33 keer, oftewel $7/3$), dan is de diepte van de nesting (hoeveel haakjes er binnen elkaar zitten) beperkt.
• De metafoor: Het is alsof je een toren bouwt van blokken. Als je de regels voor herhaling streng houdt, kan je toren nooit hoger zijn dan 3 verdiepingen. Zodra je de regels iets versoepelt (meer herhaling toestaan), kun je torens bouwen die oneindig hoog zijn.
• Conclusie: Er is een scherpe grens. Bij $7/3$ is de wereld van haakjes "beheersbaar" (maximaal 3 lagen diep). Boven die grens wordt het een chaos van oneindig diepe nesten.

2. De Thue-Morse-reeks: De "Gouden Middelweg"

Er is een beroemde, oneindige rij van 0'en en 1'en die heet de Thue-Morse-reeks. Deze rij is bekend om zijn complexiteit en het feit dat hij nooit te veel herhalingen toelaat.

• De vraag: Hoeveel perfecte haakjes-woorden (Dyck-woorden) zitten er verstopt in deze rij? En hoe diep gaan ze?
• De ontdekking: De onderzoekers hebben een soort "zoekmachine" bedacht om precies te tellen hoeveel van deze haakjes-woorden er zijn van een bepaalde lengte. Ze hebben bewezen dat de diepte van deze nesten in de Thue-Morse-reeks nooit dieper gaat dan 2 lagen.
• De metafoor: Stel je de Thue-Morse-reeks voor als een enorme, ingewikkelde labyrint. De onderzoekers hebben een kaart getekend die precies laat zien waar de "perfecte kamers" (de Dyck-woorden) zitten. Ze ontdekten dat deze kamers nooit meer dan twee verdiepingen diep zijn. Ze hebben ook een formule bedacht om het aantal kamers op elke verdieping te tellen.

3. De "Walnut": De Wiskundige Robot

Een groot deel van dit onderzoek is gedaan met een computerprogramma genaamd Walnut.

• De metafoor: Denk aan Walnut als een super-intelligente robot die niet alleen rekent, maar ook logica begrijpt. Je kunt de robot een vraag stellen als: "Zijn er ergens in deze oneindige rij een rijtje haakjes dat 100 keer herhaald wordt?" De robot kijkt dan niet naar elk getal (want dat zijn er oneindig veel), maar gebruikt slimme patronen om te zeggen: "Nee, dat is onmogelijk, want de structuur van de rij staat dat niet toe."
• De onderzoekers hebben deze robot gebruikt om complexe bewijzen te leveren die voor een mens te ingewikkeld zouden zijn om met de hand te doen.

4. Andere Reeksen: Het Fibonacci- en Rudin-Shapiro-avontuur

De onderzoekers keken ook naar andere beroemde rijen:

• Fibonacci-woord: Hier zijn de regels heel streng. Er zijn maar heel weinig perfecte haakjes-woorden mogelijk (alleen 01 en 0101). Het is alsof je in een heel klein huisje woont; er is gewoon geen ruimte voor grote nesten.
• Rudin-Shapiro-reeks: Hier is het juist het tegenovergestelde. De onderzoekers bewezen dat je hier oneindig diepe nesten kunt vinden. Je kunt hier torens bouwen die zo hoog zijn als je wilt, zonder dat de structuur instort.

Waarom is dit belangrijk?

Op het eerste gezicht lijkt dit alleen maar over haakjes en getallen te gaan. Maar dit soort onderzoek helpt ons begrijpen hoe patronen werken in complexe systemen.

• Het helpt bij het begrijpen van datacompressie (hoe we informatie efficiënt opslaan).
• Het is relevant voor cryptografie (hoe we codes maken die moeilijk te kraken zijn).
• Het laat zien hoe wiskundige regels (zoals "niet te veel herhalen") de structuur van een systeem fundamenteel veranderen.

Kortom: De onderzoekers hebben laten zien dat als je de regels voor herhaling strak houdt, de wereld van haakjes beperkt en voorspelbaar blijft. Maar als je die regels loslaat, opent zich een wereld van oneindige diepte en complexiteit. En ze hebben de perfecte tools (zoals de robot Walnut) gevonden om deze geheimen te ontcijferen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Dyck words, pattern avoidance, and automatic sequences" van Lucas Mol, Narad Rampersad en Jeffrey Shallit, geschreven in het Nederlands.

Titel: Dyck-woorden, patroonvermijding en automatische rijen

1. Probleemstelling

Het artikel onderzoekt de eigenschappen van Dyck-woorden die voorkomen als factoren (substrings) in oneindige binaire rijen. Een Dyck-woord wordt gedefinieerd als een binaire string waarbij '0' wordt behandeld als een linkerhaakje en '1' als een rechterhaakje, en de string een gebalanceerde reeks haakjes voorstelt.

De auteurs richten zich op twee hoofdvragen:

1. Patroonvermijding en Nestingsdiepte: Wat is het verband tussen het vermijden van herhalingen (krachten) in een woord en de maximale "nestingsdiepte" (diepte van geneste haakjes) van de Dyck-factoren die erin voorkomen?
2. Telling in Automatische Rijen: Hoe kunnen we het aantal Dyck-factoren van een bepaalde lengte tellen in specifieke automatische rijen, zoals het Thue-Morse-woord en de Rudin-Shapiro-rij?

2. Methodologie

De auteurs combineren combinatorische bewijstechnieken met geautomatiseerd redeneren.

• Combinatorische Analyse: Er worden directe bewijzen geleverd voor eigenschappen van woorden, inclusief het construeren van specifieke morfismen om woorden met gewenste eigenschappen te genereren.
• Walnut Theorem Prover: Een groot deel van het werk wordt uitgevoerd met Walnut, een open-source theorema-prover voor automatische rijen. Dit systeem kan eerste-orde logica formuleren over automatische rijen en deze rigoureus verifiëren.
• Lineaire Representaties: Voor het tellen van factoren gebruiken de auteurs de theorie van $k$-regular rijen. Ze construeren lineaire representaties (vectoren en matrices) om het aantal Dyck-factoren van lengte $2n$ te berekenen.
• Gekoppelde Automaten: Voor rijen die niet direct "running-sum synchronized" zijn (zoals Rudin-Shapiro in basis 2), gebruiken ze geavanceerde technieken om automaten te construeren die de balans van haakjes in parallel met de index verwerken.

3. Belangrijkste Bijdragen en Resultaten

A. Patroonvermijding en Nestingsdiepte

• 7/3-krachten en Nesting: De auteurs bewijzen dat als een binair woord 7/3-kracht-vrij is (geen factor heeft met exponent $\ge 7/3$), de nestingsdiepte van elke Dyck-factor in dat woord beperkt is tot maximaal 3.
• Optimaliteit: Ze tonen aan dat dit resultaat scherp is: er bestaan Dyck-woorden die 7/3+-kracht-vrij zijn (geen factor met exponent $> 7/3$) met een willekeurig grote nestingsdiepte. Dit wordt bereikt door een specifieke constructie te gebruiken met morfismen $g$ (op een ternair alfabet) en $f$ (naar binair), waarbij $f(g^t(2))$ een Dyck-woord is met diepte $2t+2$.
• Overlap-vrije woorden: Ze geven een expliciete karakterisering van overlap-vrije Dyck-woorden en bewijzen dat er willekeurig lange overlap-vrije Dyck-woorden bestaan met diepte 2 en 3.

B. Dyck-factoren in het Thue-Morse-woord

• Karakterisering: Ze bewijzen dat de Dyck-factoren van het Thue-Morse-woord ($t$) exact de woorden zijn van de vorm $h(x)$, waarbij $x$ een factor is van een specifieke ternaire rij $s$ (de vaste punt van een morfisme) en $h$ een morfisme is dat $0 \to 01$,$1 \to 0011$, en$2 \to 001011$ toewijst.
• Beperkte Diepte: Als gevolg hiervan is de nestingsdiepte van elke Dyck-factor in het Thue-Morse-woord beperkt tot 2.
• Telling en Regulariteit: Ze bewijzen dat de rij $d(n)$, het aantal Dyck-factoren van lengte $2n$in het Thue-Morse-woord, een **2-regular rij** is. Ze construeren een lineaire representatie van rang 7 om$d(n)$ efficiënt te berekenen.
• Grenzen: Ze leiden scherpe bovengrenzen en ondergrenzen af:
  • $d(n) \le n$ voor alle $n \ge 1$ (met gelijkheid voor $n = 3 \cdot 2^i$).
  • $d(n) \ge n/2$ voor alle $n \ge 0$.
  • De gemiddelde waarde van $d(n)$ is asymptotisch $\frac{19}{24}n$.

C. Andere Automatische Rijen

• Fibonacci-woord: De enige niet-lege Dyck-woorden zijn $01$en$0101$.
• Period-doubling rij: De enige niet-lege Dyck-woorden zijn $01$,$0101$en$010101$.
• Rudin-Shapiro rij: In tegenstelling tot de bovenstaande rijen, bevat de Rudin-Shapiro rij Dyck-factoren met een willekeurig grote nestingsdiepte. De auteurs bewijzen dit via een inductieve constructie en tonen aan dat de verzameling van lengtes $n$ waarvoor een Dyck-factor bestaat, een 4-automatische verzameling is.

4. Significatie

Dit artikel is significant op meerdere vlakken:

1. Scherpheid van Grenzen: Het legt een precieze drempel vast tussen patroonvermijding (krachten) en de complexiteit van haakjes-nesting. Het toont aan dat $7/3$ een kritieke exponent is voor het beperken van de diepte van Dyck-woorden.
2. Toepassing van Automatische Methoden: Het demonstreert de kracht van Walnut en de theorie van automatische rijen om complexe combinatorische eigenschappen (zoals het tellen van specifieke factoren en het bepalen van nestingsdiepte) te analyseren die met handmatige methoden moeilijk te bewijzen zouden zijn.
3. Nieuwe Inzichten in Bekende Rijen: Het biedt een volledig nieuw perspectief op het Thue-Morse-woord en de Rudin-Shapiro-rij door ze te analyseren via de lens van haakjes-balans, wat leidt tot nieuwe sequenties (zoals A345199 in de OEIS) en structurele karakterisering.
4. Algoritmische Constructie: De paper biedt niet alleen bewijzen, maar ook expliciete algoritmen en automaten (DFAO's) om deze eigenschappen te verifiëren en te berekenen, wat bruikbaar is voor toekomstig onderzoek in de theoretische informatica.

Samenvattend verbindt dit werk de theorie van formele talen (Dyck-taal), combinatoriek op woorden (herhalingen) en de theorie van automatische rijen, en levert het zowel theoretische grenzen als praktische berekeningsmethodes op.