The Conjugacy Relation on One-sided Subshifts is Non-treeable

Dit artikel toont aan dat de conjugatierelatie op éénzijdige subshifts met het alfabet $\{0,1\}$, vanuit het perspectief van de beschrijvende verzamelingenleer, niet-boomvormbaar en niet-amenable is.

De kern

De Onoplosbare Puzzel van de Eénzijdige Subshifts: Een Verhaal over Chaos en Ordening

Stel je voor dat je een enorme bibliotheek hebt, maar in plaats van boeken, zitten er hier oneindige rijen lichtjes in. Elke rij is een patroon van aan- en uitgaande lampjes (bijvoorbeeld 0 en 1). In de wiskunde noemen we deze rijen subshifts. Ze zijn als een onophoudelijke stroom van informatie die door een machine (een dynamisch systeem) wordt gegenereerd.

De vraag die de auteur, Ruiwen Li, zich stelt, is eigenlijk heel simpel: "Hoe moeilijk is het om te zeggen of twee van deze lichtjes-rijen eigenlijk hetzelfde patroon volgen?"

In de wiskundige wereld noemen we dit het vinden van een conjugatie. Als je de ene rij kunt omzetten in de andere door alleen maar een slimme, vaste regel toe te passen (een soort "vertaalcode"), dan zijn ze "geconjugeerd" ofwel "dezelfde".

Het Probleem: Twee Kanten van dezelfde Munt

Er zijn twee soorten van deze rijen:

1. Tweezijdige subshifts: De rij gaat oneindig naar links én rechts. Dit is als een lange trein die in beide richtingen rijdt.
2. Eénzijdige subshifts: De rij begint ergens en gaat alleen maar naar rechts. Dit is als een trein die uit een station vertrekt en nooit terugkomt.

Wiskundigen weten al lang dat het voor de tweezijdige varianten al heel erg ingewikkeld is om te bepalen of twee patronen hetzelfde zijn. Maar voor de éénzijdige varianten (die in de echte wereld vaak voorkomen, zoals bij datastromen) was het antwoord tot nu toe een raadsel.

De Ontdekking: Een Boom die niet bestaat

In dit paper bewijst Li iets heel belangrijks over de éénzijdige varianten met alleen maar 0'en en 1'en. Hij gebruikt een speciaal soort wiskunde (beschrijvende verzamelingenleer) om de "complexiteit" van dit probleem te meten.

Hij gebruikt twee mooie metaforen om dit te verklaren:

1. De Boom (Treeable):
   Stel je voor dat je alle mogelijke patronen in een gigantische boom moet plaatsen. Als je van elke boomtak naar beneden kunt lopen zonder ooit in een kringetje te belopen, dan is het probleem "oplosbaar" of "boom-achtig" (treeable). Het betekent dat er een duidelijke, logische structuur is die je kunt volgen.
   Li's ontdekking: De wereld van de éénzijdige subshifts is geen boom. Het is een wirwar van paden die in elkaar verstrikt zitten. Je kunt geen enkele boom tekenen die alle patronen correct ordent zonder dat het systeem instort.

2. De Vriendelijke Groep (Amenable):
   Stel je voor dat je een groep mensen hebt die proberen een eerlijke verdeling te maken van taart. Als de groep "vriendelijk" (amenable) is, kunnen ze altijd een eerlijke verdeling vinden zonder dat er ruzie ontstaat. In wiskundige termen betekent dit dat het systeem "rustig" en voorspelbaar is.
   Li's ontdekking: Deze groep patronen is niet vriendelijk. Het is een chaotische menigte waar geen eerlijke verdeling of simpele regel mogelijk is. Het is een "ruisende" wereld die zich niet laat temmen door simpele regels.

Hoe heeft hij dit bewezen? (De Magische Code)

Li heeft een slimme truc bedacht. Hij heeft een soort magische vertaalcode bedacht.

• Hij neemt een heel complex, wiskundig bewezen systeem (een groep van automaten die patronen manipuleren) dat al bekend staat als "chaotisch en niet-ordentelijk".
• Vervolgens heeft hij bewezen dat hij dit chaotische systeem kan "omtoveren" naar een systeem van éénzijdige subshifts (de lichtjes-rijen) zonder de chaos te verliezen.

Het is alsof hij een onoplosbare kubus van Rubik heeft genomen en die heeft omgebouwd tot een puzzel met lichtjes. Als de kubus onoplosbaar was, is de lichtjes-puzzel dat ook. Omdat hij wist dat de bron-chaos "geen boom" en "niet-vriendelijk" was, moet de nieuwe lichtjes-puzzel dat ook zijn.

Waarom is dit belangrijk?

Voor de gewone leek klinkt dit misschien als abstracte wiskunde, maar het heeft grote gevolgen:

• De grenzen van kennis: Het laat zien dat er bepaalde vragen in de natuurkunde en informatica zijn die fundamenteel onoplosbaar zijn met simpele regels. Je kunt niet zomaar zeggen: "Dit patroon is hetzelfde als dat patroon" met een simpele checklist.
• De structuur van de realiteit: Het vertelt ons dat de wereld van dynamische systemen (hoe dingen veranderen in de tijd) veel chaotischer en complexer is dan we dachten, zelfs als we alleen maar kijken naar simpele 0'en en 1'en.

Kortom: Ruiwen Li heeft bewezen dat het proberen om alle mogelijke patronen van éénzijdige lichtjes-rijen in een nette, ordelijke lijst (een boom) te zetten, een onmogelijke taak is. De chaos is te diep geworteld. Het is een overwinning voor de wiskunde, omdat we nu precies weten waar de grenzen van onze ordening liggen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "The Conjugacy Relation on One-Sided Subshifts is Non-Treeable" van Ruiwen Li, geschreven in het Nederlands.

Titel: De conjugatie-relatie op éénzijdige subshifts is niet-baamvormig (non-treeable)

Auteur: Ruiwen Li (Nankai University)
Datum: 6 maart 2026 (voorgesteld)

---

1. Probleemstelling en Context

Dit artikel onderzoekt de beschrijvende verzamelingstheoretische complexiteit van de conjugatie-relatie op de klasse van éénzijdige subshifts (one-sided subshifts) met een alfabet van $\{0, 1\}$.

• Achtergrond: In de beschrijvende verzamelingstheorie worden equivalentierelaties op standaard Borel-ruimten vergeleken via Borel-reductie. Een relatie $E$ is "complexer" dan $F$ als $E$ Borel-reduceerbaar is tot $F$ ($E \le_B F$).
• Bestaande kennis: Voor tweezijdige subshifts (invertible subshifts) heeft John Clemens bewezen dat de conjugatie-relatie Borel-bireduceerbaar is met $E_\infty$, een universele tellbare Borel-equivalentierelatie. Dit impliceert dat de relatie zeer complex is, maar nog steeds binnen de klasse van tellbare Borel-relaties valt.
• Het open probleem: Hoewel de complexiteit van tweezijdige subshifts goed begrepen is, was de exacte complexiteit van de conjugatie-relatie op éénzijdige subshifts (waarbij de verschuiving $S$ niet-invertibel is) onbekend. Clemens stelde specifiek de vraag naar de complexiteit van de isomorfie van éénzijdige shifts op $\{0, 1\}^\mathbb{N}$.
• Doel: Het bewijzen dat deze relatie niet-baamvormig (non-treeable) en niet-amabel (non-amenable) is. Dit zijn eigenschappen die aangeven dat de relatie strikt complexer is dan hyperfinite relaties (zoals $E_0$) en niet kan worden gereduceerd tot relaties die voortkomen uit amabele groepswerkingen.

2. Methodologie

De auteur hanteert een constructieve aanpak die voortbouwt op eerdere resultaten van Deka, Kwietniak, Peng en Sabok (2025) over subshifts met het "specification property", maar past deze aan voor het niet-invertibele geval.

Stap 1: Constructie van een specifieke subshift-ruimte $S(A)$

• Er wordt een alfabet $A$ gedefinieerd met symbolen $\{a_i, \tilde{a}_i, \# \mid 1 \le i \le 6\}$.
• Er wordt een verzameling $S(A)$ geconstrueerd bestaande uit subshifts $X(R)$ die worden gedefinieerd door een verzameling verboden woorden $R \subset (A \setminus \{\#\})^*_{odd}$.
• De ruimte $S(A)$ wordt een compacte metrische ruimte gemaakt via de Vietoris-topologie.

Stap 2: Groepswerking en Automorfismen

• Er wordt een groep $\Gamma$ geconstrueerd, gegenereerd door zes specifieke automorfismen $f_1, \dots, f_6$ van de volledige shift $A^\mathbb{Z}$.
• Deze automorfismen zijn " #-behoudend" en werken lokaal op basis van een blokcode $g_i$. Ze wisselen symbolen $a_i$ en $\tilde{a}_i$ om afhankelijk van de context, maar laten andere symbolen onveranderd.
• Belangrijk resultaat: De groep $\Gamma$ is isomorf met $(\mathbb{Z}_2 * \mathbb{Z}_2 * \mathbb{Z}_2)^2$. Deze groep bevat een kopie van $F_2 \times F_2$ (het directe product van twee vrije groepen op twee generatoren).
• De groep $\Gamma$ werkt op de ruimte $S(A)$. De auteur bewijst dat deze werking:
  1. Een maat behoudt (preserves a probability measure).
  2. Vrij is (a.e. free).
  3. Geen "bijna triviale" elementen bevat (geen elementen die behalve op een eindig aantal woorden de identiteit zijn).

Stap 3: Reductie naar Éénzijdige Subshifts

• Om het resultaat over te dragen naar éénzijdige subshifts met alfabet $\{0, 1\}$, wordt een Borel-injectie $\phi: S(A) \to \text{Transitive One-sided Subshifts}$ geconstrueerd.
• Codering: Elk symbool $a \in A$ wordt afgebeeld op een vast woord $\rho(a)$ van lengte 22 over het alfabet $\{0, 1\}$. Deze codering is uniek leesbaar (uniquely readable), wat betekent dat de oorspronkelijke structuur van de subshift volledig herstelbaar is uit de gecodeerde versie.
• De afbeelding $\phi$ behoudt de conjugatie-relatie: als $X_1$ en $X_2$ conjugate zijn onder de werking van $\Gamma$, dan zijn $\phi(X_1)$ en $\phi(X_2)$ conjugate als éénzijdige subshifts.

3. Belangrijkste Resultaten

Het hoofdstelling van het artikel is Stelling 1.2:

De conjugatie-relatie op transitive éénzijdige subshifts met het alfabet $\{0, 1\}$ is een niet-baamvormige (non-treeable) en niet-amabele (non-amenable) tellbare Borel-equivalentierelatie.

Technische details van het bewijs:

1. Niet-baamvormig (Non-treeable): Omdat de groep $\Gamma$ isomorf is met een groep die $F_2 \times F_2$ bevat, en omdat de werking maatbehoudend en vrij is, volgt uit een stelling van Pemantle en Peres (2000) dat de geïnduceerde equivalentierelatie niet-baamvormig is. Een relatie is treeable als deze geïnduceerd kan worden door een acyclische Borel-graaf; dit is onmogelijk voor werkingen van niet-amabele groepen zoals $F_2 \times F_2$ onder deze voorwaarden.
2. Niet-amabel (Non-amenable): Omdat de groep $\Gamma$ zelf niet-amabel is (het bevat vrije subgroepen), en de werking vrij is, is de geïnduceerde equivalentierelatie per definitie niet-amabel (volgens een stelling van Gao).
3. Overdracht: De constructie van de injectie $\phi$ toont aan dat deze complexe structuur "ingebouwd" kan worden in de klasse van éénzijdige subshifts over $\{0, 1\}$.

4. Bijdrage en Significatie

• Beantwoording van een open vraag: Het artikel beantwoordt een vraag van Clemens (2009) over de complexiteit van éénzijdige shifts. Het toont aan dat deze relatie niet "simpel" is (zoals hyperfinite relaties) en zelfs niet-baamvormig is.
• Verschil met tweezijdige subshifts: Voor tweezijdige subshifts is de conjugatie-relatie universeel ($E_\infty$), maar het was onduidelijk of dit ook gold voor éénzijdige subshifts. Dit resultaat plaatst de complexiteit van éénzijdige subshifts in een specifieke, hoge complexiteitsklasse (niet-baamvormig), wat suggereert dat ze fundamenteel anders gedragen dan hun invertibele tegenhangers in termen van classificatie.
• Methodologische innovatie: De auteur lost het probleem op dat het inkrimpen van het alfabet (van een groot alfabet naar $\{0, 1\}$) voor éénzijdige subshifts niet-triviale aanpassingen vereist. De constructie van de unieke leesbare codering $\rho$ is een cruciale technische prestatie die de overdracht van complexiteit mogelijk maakt zonder de dynamische eigenschappen te verliezen.
• Implicaties voor de classificatietheorie: Het resultaat bevestigt dat het classificeren van dynamische systemen (zelfs voor relatief eenvoudige systemen als subshifts) intrinsiek zeer complex is en niet kan worden gereduceerd tot tellbare structuren of amabele groepswerkingen.

Kortom, het paper levert een fundamenteel bewijs dat de classificatieproblematiek voor éénzijdige subshifts een hoge mate van wiskundige complexiteit bezit, vergelijkbaar met de meest complexe tellbare Borel-relaties die bekend zijn.