The Thue-Morse Transform

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

De Magische Spiegel van de Getallen: Een Reis door de Thue-Morse Transformatie

Stel je voor dat je een heel lange rij van lichtjes hebt, sommige branden (1) en sommige zijn uit (0). Dit is een binaire reeks. De beroemdste rij van dit type is de Thue-Morse-reeks. Deze rij is niet willekeurig; hij heeft een heel specifieke, mysterieuze structuur die wiskundigen al eeuwen fascineert.

In dit nieuwe onderzoek introduceert Benoît Cloitre een nieuw spelletje, een soort magische spiegel genaamd de Thue-Morse-transformatie. Als je deze spiegel op een rij lichtjes houdt, krijg je een nieuwe rij lichtjes terug. Maar het echte wonder is wat er gebeurt als je deze spiegel herhaaldelijk gebruikt op het resultaat van de vorige keer.

1. De Magische Spiegels (De Transformatie)

Hoe werkt deze spiegel?
Stel je hebt een rij lichtjes. De spiegel kijkt naar twee soorten posities:

De "Kwaadaardige" posities (Evil): De plekken waar het lichtje uit staat (0).
De "Boosaardige" posities (Odious): De plekken waar het lichtje aan staat (1).

De spiegel doet het volgende:

Hij neemt de nieuwe rij en vult de plekken die "Kwaadaardig" waren in de oude rij met het patroon van de oude rij zelf.
Hij vult de plekken die "Boosaardig" waren in de oude rij met het tegenovergestelde patroon (uit wordt aan, aan wordt uit).

Als je dit een keer doet, krijg je een nieuwe rij. Als je dit nog eens doet op die nieuwe rij, krijg je weer een andere. Cloitre heeft ontdekt dat als je dit oneindig vaak doet, je een toren krijgt van verschillende rijen, elk met zijn eigen unieke, maar gerelateerde structuur.

2. Het Geheim van de "Maskers" (De Formule)

Het meest verbazingwekkende is dat Cloitre een simpele formule heeft gevonden om deze hele toren te beschrijven, zonder dat je hoeft te blijven spiegelen.

Stel je voor dat elk getal een sleutel is, gemaakt van een reeks schakelaars (0 en 1).

De Thue-Morse-reeks (het begin) kijkt naar alle schakelaars en telt of er een oneven aantal aan staat.
De volgende rijen in de toren kijken niet meer naar alle schakelaars. Ze hebben een masker op.

Dit masker is een getal $m$ . Als je dit masker op de schakelaars van een getal legt, blokkeert hij sommige schakelaars. De rij kijkt alleen naar de schakelaars die niet door het masker worden bedekt.

Geen masker ( $m=0$ ): Je kijkt naar alles (de klassieke Thue-Morse).
Een ander masker ( $m=1, 2, 3...$ ): Je kijkt alleen naar specifieke patronen.

Het is alsof je door verschillende gekleurde brillen kijkt. Elke bril (elk masker) laat een ander patroon van lichtjes zien, maar ze komen allemaal voort uit dezelfde bron.

3. De Gouden Delen (Het Prouhet-probleem)

Waarom is dit belangrijk? Wiskundigen hebben al lang gezocht naar een manier om getallen in groepen te verdelen zodat de sommen van hun machten (bijvoorbeeld de som van de getallen zelf, of de som van hun kwadraten) precies gelijk zijn. Dit heet het Prouhet-Tarry-Escott-probleem.

De klassieke Thue-Morse-reeks deed dit al voor twee groepen. Cloitre's onderzoek toont aan dat elke nieuwe rij in zijn toren dit ook doet, maar dan beter of op een andere manier.

Het is alsof je een taart hebt. De klassieke methode deelt de taart in twee gelijke stukken.
Cloitre's nieuwe methoden kunnen de taart verdelen in stukken die niet alleen qua grootte, maar ook qua "gewicht" (de som van de getallen) perfect in evenwicht zijn, zelfs als je de taart in heel veel kleine stukjes snijdt.

Elk masker in zijn toren geeft een nieuwe, perfecte manier om getallen te verdelen.

4. De Dans van de Getallen (Samenstellingen)

In de oude wiskunde waren de regels voor hoe deze getallen met elkaar omgaan vrij simpel en statisch (als een robot die altijd hetzelfde doet). Cloitre ontdekt dat in zijn nieuwe toren de regels dynamisch worden.

De "Kwaadaardige" en "Boosaardige" getallen dansen nu op een complexere manier. De correcties die nodig zijn om de dans te laten slagen, zijn niet meer statische getallen, maar volgen een eigen, automatisch patroon. Het is alsof de robot-dansers nu een muzikant hebben die de muziek aanpast aan hun bewegingen, waardoor de dans veel rijker en interessanter wordt.

5. De Structuur van de Stad (Factor Complexiteit)

De auteur kijkt ook naar hoe "chaotisch" of "geordend" deze rijen zijn. Hij meet dit door te kijken naar hoeveel verschillende stukjes (woorden) van een bepaalde lengte er in de rij voorkomen.

Voor de klassieke rij is dit patroon bekend.
Voor de nieuwe rijen in de toren (vooral die met een speciaal type masker, genaamd "Mersenne") heeft Cloitre een exacte formule gevonden.

Het is alsof hij de plattegrond van een stad heeft getekend. Hij kan precies voorspellen hoeveel verschillende straten (patronen) er zijn op elke afstand, en hoe de stad groeit naarmate je verder kijkt.

6. Verder dan de Basis (Andere Werelden)

Tot slot laat Cloitre zien dat dit idee niet alleen werkt met het standaard "binaire" systeem (0 en 1).

Je kunt het ook doen met andere bases (bijvoorbeeld in een systeem met 3 of 4 cijfers).
Je kunt het zelfs toepassen op een heel ander systeem dat gebaseerd is op de Fibonacci-getallen (1, 1, 2, 3, 5, 8...). Hier werkt de "spiegel" ook, maar het patroon is anders en minder perfect dan in de binaire wereld. Dit opent de deur naar een heel nieuw universum van getallenpatronen.

Conclusie

Kortom, Benoît Cloitre heeft een nieuwe manier gevonden om naar oude getallenproblemen te kijken. Hij heeft laten zien dat als je een simpele regel (de Thue-Morse-transformatie) herhaaldelijk toepast, je een toren van nieuwe wiskundige structuren krijgt.

Elke verdieping in deze toren biedt:

Nieuwe, perfecte manieren om getallen te verdelen (oplossingen voor het Prouhet-probleem).
Complexe, maar voorspelbare patronen in hoe getallen met elkaar interageren.
Een helder inzicht in de structuur van deze rijen.

Het is een mooi voorbeeld van hoe een klein, simpel idee (een spiegel die lichtjes omdraait) kan uitgroeien tot een enorme, rijke wiskundige wereld.

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

Titel: The Thue–Morse Transform

Auteur: Benoît Cloitre
Onderwerp: Getaltheorie, Automatische rijen, Combinatoriek op woorden, Het Prouhet-Tarry-Escott probleem.

1. Probleemstelling en Achtergrond

Het artikel introduceert een nieuwe operator, de Thue-Morse-transformatie (TM-transformatie), die werkt op binaire rijen. De klassieke Thue-Morse rij $t(n)$ (de pariteit van het aantal enen in de binaire representatie van $n$ ) is historisch gezien centraal in de oplossing van het Prouhet-Tarry-Escott (PTE) probleem. Dit probleem vraagt om een partitie van een verzameling gehele getallen in twee deelverzamelingen zodat de sommen van de machten tot een bepaalde graad $k$ in beide deelverzamelingen gelijk zijn.

De klassieke constructie van Prouhet gebruikt de rij $t(n)$ om getallen in "boze" (evil, waar $t(n)=0$ ) en "boze" (odious, waar $t(n)=1$ ) getallen te verdelen, wat leidt tot een perfecte partitie voor machten tot graad $L-1$ op het interval $[0, 2^L)$ .

Cloitre stelt de vraag wat er gebeurt als men deze transformatie iteratief toepast. Wat is de structuur van de rij die ontstaat als men de TM-transformatie toepast op de klassieke Thue-Morse rij, en vervolgens weer op het resultaat, enzovoort? Het doel is om deze iteraties expliciet te beschrijven en de arithmetische gevolgen te analyseren.

2. Methodologie

De auteur hanteert een combinatie van methoden:

Definitie van de Operator: De TM-transformatie $T(\sigma)$ wordt gedefinieerd voor een binaire rij $\sigma$ door de posities van de nullen ( $v_\sigma$ , "evil") en enen ( $u_\sigma$ , "odious") te registreren. Een nieuwe rij $\tau = T(\sigma)$ wordt gedefinieerd door de relaties $\tau(v_\sigma(n)) = \tau(n)$ en $\tau(u_\sigma(n)) = 1 - \tau(n)$ .
Iteratie: Men start met de klassieke Thue-Morse rij $a_0 = t$ en definieert een toren van rijen $a_{m+1} = T(a_m)$ .
Expliciete Formules: In plaats van alleen recursief te werken, zoekt de auteur naar een gesloten vorm (closed form) voor $a_m(n)$ gebaseerd op bit-posities.
** genererende Functies:** Om de PTE-eigenschappen te bewijzen, wordt gebruik gemaakt van genererende functies en productfactorisaties, een techniek die terugvoert op werk van Borwein en Ingalls.
Automatische Rijen en Substitutie: De structuur van de rijen wordt geanalyseerd via hun eigenschappen als automatische rijen (berekend door eindige automaten) en via desubstitutie-argumenten voor de factorcomplexiteit.

3. Belangrijkste Bijdragen en Resultaten

A. De Expliciete "Masker"-Formule

Het meest fundamentele resultaat is het vinden van een expliciete, niet-recursieve formule voor de $m$ -de iteratie $a_m(n)$ .
Laat $n = \sum b_p(n) 2^p$ de binaire expansie zijn. De rij wordt gegeven door:
$a_m(n) = \bigoplus_{p \ge 0, \, p \ \& \ m = 0} b_p(n)$
Hierbij is $\oplus$ de XOR-som (optelling modulo 2) en $p \ \& \ m$ de bit-wise AND.

Interpretatie: De parameter $m$ fungeert als een masker. Alleen de binaire posities $p$ die geen gemeenschappelijke bits hebben met $m$ (d.w.z. $p \ \& \ m = 0$ ) dragen bij aan de pariteit.
Dit betekent dat de iteraties een duidelijke dyadische structuur hebben die volledig wordt bepaald door de binaire representatie van het indexgetal $m$ .

B. Oplossingen voor het Prouhet-Tarry-Escott (PTE) Probleem

De rijen $a_m$ genereren nieuwe families van oplossingen voor het PTE-probleem.

Voor een gegeven masker $m$ en een intervalgrootte $N = B(m) \cdot L$ (waarbij $B(m)$ een macht van 2 is die afhangt van $m$ ), zijn de sommen van machten $k$ gelijk voor beide partities ( $a_m(n)=0$ en $a_m(n)=1$ ) voor alle $k < s_m L$ .
Hier is $s_m$ het aantal geselecteerde bit-posities per periode.
Dit generaliseert de klassieke Prouhet-construction: terwijl Prouhet de graad vergrootte door het interval te vergroten, vergroot deze constructie de graad door het masker $m$ te kiezen dat meer posities selecteert.

C. Generaliseerde "Evil" en "Odious" Getallen

De auteur definieert generaliseerde evil ( $v_m$ ) en odious ( $u_m$ ) getallen voor elke rij $a_m$ .

In het klassieke geval ( $m=0$ ) voldoen deze aan eenvoudige lineaire composities met constante correcties (bijv. $u(u(n)) = 2u(n)$ ).
Voor $m > 0$ worden de correcties niet langer constant, maar worden ze beschreven door automatische rijen (de "correction functions" $c_m(n)$ ).
Er worden functionele vergelijkingen afgeleid die deze composities beschrijven, waarbij de correctie afhangt van de pariteit van $m$ en de specifieke bit-posities in het masker.

D. Factor Complexiteit

Voor de "Mersenne-niveaus" (waar $m = 2^k - 1$ ) wordt de factor complexiteit (het aantal unieke substrings van lengte $n$ ) volledig bepaald.

Er is een exact lineair regime voor kleine $n$ : $p_{a_m}(n) = 2n$ .
Hierna volgt een complex, stuksgewijs lineair patroon dat wordt afgeleid via een desubstitutie-argument op de afgeleide rij $\Delta(n) = a_m(n) \oplus a_m(n+1)$ .
Voor niet-Mersenne niveaus is de structuur complexer en blijft een volledige formule een open probleem.

E. Uitbreidingen

Het artikel onderzoekt ook twee uitbreidingen:

d-ary Generalisatie: De methode wordt uitgebreid naar basis $d$ (in plaats van alleen basis 2), wat leidt tot PTE-partities met $d$ klassen.
Andere Zaden: De transformatie wordt toegepast op andere rijen, zoals de "meta-Thue-Morse" rij $M_2$ en de Fibonacci-Thue-Morse rij (gebaseerd op Zeckendorf-notatie). Hoewel de structuur anders is, blijven er interessante PTE-achtige eigenschappen en partities bestaan.

4. Significatie

Dit artikel is significant omdat het:

Een unificerend kader biedt voor een hele toren van automatische rijen die voortkomen uit iteratie van de Thue-Morse transformatie.
De link legt tussen bit-masking (combinatoriek op binaire getallen) en PTE-partities (getaltheorie).
Toont aan dat de klassieke eigenschappen van de Thue-Morse rij (zoals de constante correcties in composities) kunnen worden verrijkt tot een rijkere structuur van automatische correcties.
Nieuwe, expliciete families van PTE-oplossingen biedt die verder gaan dan de traditionele methoden, met controleerbare graad en aantal klassen.
De complexiteit van deze rijen volledig karakteriseert voor een belangrijke subklasse (Mersenne-niveaus), wat inzicht geeft in de combinatorische structuur van iteratieve transformaties.

Kortom, Cloitre transformeert een enkelvoudig concept (de Thue-Morse rij) in een veelzijdig wiskundig systeem met diepe connecties naar getaltheorie, automata-theorie en combinatoriek.