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

Cet article démontre, dans le cadre de la théorie descriptive des ensembles, que la relation de conjugaison sur les sous-décalages unilatéraux à deux symboles est non arborescente et non moyennable.

L'essentiel

Voici une explication simple et imagée de ce papier de recherche, traduite en français pour un public général.

🎬 Le Titre : "Les systèmes qui bougent ne peuvent pas être rangés dans un arbre"

Imaginez que vous êtes un bibliothécaire chargé de classer des millions de films. Mais ces films ne sont pas des histoires avec un début et une fin ; ce sont des boucles infinies de mouvements, comme une horloge qui tourne pour toujours ou un tapis roulant. En mathématiques, on appelle cela des systèmes dynamiques.

Le but de l'auteur, Ruiwen Li, est de répondre à une question fondamentale : Peut-on classer ces films les uns par rapport aux autres ? Plus précisément, peut-on dire si deux films sont "identiques" (ou conjugués), c'est-à-dire s'ils racontent la même histoire, juste avec des acteurs différents ou un décalage de temps ?

🧩 L'Analogie du Puzzle et de l'Arbre

Pour comprendre la découverte de l'auteur, utilisons deux métaphores :

1. Le Puzzle (La complexité) :
   Imaginez que chaque film est un puzzle géant. Si deux puzzles sont "conjugués", c'est qu'ils ont exactement les mêmes pièces, juste assemblées différemment. Le défi, c'est de savoir si on peut créer un catalogue (une liste) pour dire : "Ce puzzle est pareil à celui-là".

2. L'Arbre (La structure) :
   En mathématiques, on dit qu'une relation est "arborescente" (treeable) si on peut organiser tous les objets dans un grand arbre généalogique.

   • Exemple arborescent : Imaginez un arbre de famille. Vous pouvez dire : "Jean est le fils de Paul, Paul est le fils de Pierre". Tout est clair, tout a un ancêtre unique, pas de boucles. C'est facile à naviguer.
   • Exemple non-arborescent : Imaginez un labyrinthe où les chemins se croisent, se rejoignent et forment des boucles infinies. Vous ne pouvez pas tracer une ligne droite depuis le début jusqu'à la fin sans vous perdre dans des cercles vicieux.

🔍 Le Problème : Les "Subshifts" à sens unique

L'auteur s'intéresse à un type particulier de films appelés subshifts unilatéraux.

• L'image : Imaginez un ruban de film infini qui défile vers la droite. Vous ne pouvez pas le faire défiler en arrière (c'est "unilatéral").
• Le défi : Jusqu'à présent, les mathématiciens savaient que pour les films qui peuvent défiler dans les deux sens (gauche et droite), le problème de classement est très complexe, mais "gérable" (on peut le réduire à un arbre).
• La question : Et si on ne peut défiler que dans un sens ? Est-ce que ça devient encore plus compliqué ?

💡 La Découverte : C'est un Labyrinthe, pas un Arbre

Ruiwen Li a prouvé que pour ces films à sens unique (avec seulement deux symboles, 0 et 1, comme un code binaire simple), la réponse est NON.

Il a démontré que la relation de conjugaison (le fait de dire si deux films sont identiques) est non-arborescente (non-treeable) et non-amenable.

En langage simple :
Cela signifie que vous ne pouvez pas organiser ces systèmes dans un arbre généalogique propre. La structure de leurs similarités est trop chaotique, trop enchevêtrée. C'est comme essayer de classer des grains de sable en disant "celui-ci est le fils de celui-là", alors qu'ils forment une tempête de sable où tout se mélange en permanence.

🛠️ Comment a-t-il fait ? (L'ingénierie du chaos)

Pour prouver cela, l'auteur a construit une machine mathématique très astucieuse :

1. Le Laboratoire : Il a créé un espace rempli de systèmes dynamiques spéciaux, construits avec des blocs de construction très précis (des mots interdits).
2. Le Groupe de Transformations : Il a inventé un groupe de "magiciens" (des fonctions mathématiques) capables de transformer un système en un autre. Ces magiciens agissent comme des clés qui ouvrent des portes entre les systèmes.
3. Le Piège : Il a prouvé que ces magiciens forment une structure mathématique très puissante (un produit de groupes libres) qui crée inévitablement des boucles et des croisements.
4. Le Traducteur : Enfin, il a montré qu'on peut traduire n'importe quel système de ce laboratoire complexe vers nos simples films à sens unique (avec des 0 et des 1) sans perdre l'information.

Le résultat : Puisque le laboratoire est un labyrinthe impossible à ranger en arbre, et que nos films simples contiennent ce même labyrinthe, alors nos films simples sont aussi un labyrinthe impossible à ranger.

🌟 Pourquoi est-ce important ?

C'est une avancée majeure en théorie descriptive des ensembles (une branche des mathématiques qui mesure la "difficulté" des problèmes de classification).

• Avant, on pensait peut-être que les systèmes simples (unilatéraux) étaient plus faciles à classer que les systèmes complexes (bilatéraux).
• Ce papier dit : Non. Même avec les règles les plus simples (juste des 0 et des 1), le chaos est déjà là. La complexité est intrinsèque.

En résumé

Imaginez que vous essayez de ranger une bibliothèque de films infinis.

• Si c'était un arbre, vous pourriez dire : "Ce film est une version modifiée de ce film-là, qui est une version de celui-ci..." et vous auriez un catalogue parfait.
• Ruiwen Li nous dit que pour les films à sens unique, c'est impossible. C'est un labyrinthe infini où les chemins se croisent de manière imprévisible. Vous ne pouvez pas créer de catalogue simple. La complexité est inévitable, même dans le monde le plus simple qui soit.

C'est une preuve élégante que le chaos mathématique peut naître de règles extrêmement simples.

Résumé technique

Résumé Technique : La Relation de Conjugaison sur les Sous-décalages Unilatéraux est Non-Arborescente

1. Problématique et Contexte

L'article s'inscrit dans le cadre de la théorie descriptive des ensembles, spécifiquement dans l'étude de la complexité des relations d'équivalence sur les espaces de Borel standards. L'objectif principal est de déterminer la complexité de la relation de conjugaison (isomorphisme topologique) sur la classe des sous-décalages unilatéraux (one-sided subshifts) à alphabet binaire $\{0, 1\}$.

• Contexte théorique : La complexité des relations d'équivalence est mesurée par la réduction de Borel ($E \le_B F$). Les relations d'équivalence dénombrables (où chaque classe est dénombrable) forment une hiérarchie complexe.
• État de l'art :
  • Pour les sous-décalages bilatéraux (invertibles), il est connu que la relation de conjugaison est universelle parmi les relations d'équivalence dénombrables de Borel ($E_\infty$) [Clemens, 2009].
  • Des résultats récents (Deka et al., 2025) ont montré que pour les sous-décalages bilatéraux possédant la propriété de spécification, la relation est non-arborescente (non-treeable) et non-amenable.
  • Le problème ouvert : La complexité exacte de la conjugaison pour les sous-décalages unilatéraux (non-inversibles) restait inconnue, notamment pour l'alphabet binaire. Une question posée par Clemens (2009) demandait spécifiquement la complexité de l'isomorphisme sur $\{0, 1\}^\mathbb{N}$.

2. Méthodologie

L'auteur adopte une approche constructive et dynamique pour répondre à cette question. La stratégie repose sur trois piliers :

1. Construction d'une action de groupe :

   • L'auteur définit un alphabet auxiliaire $A$ contenant des symboles spécifiques ($a_i, \tilde{a}_i, \#$) et construit un espace de sous-décalages $S(A)$ définis par des mots interdits de la forme $\#w\#$.
   • Il introduit un sous-groupe dénombrable $\Gamma$ du groupe des automorphismes $\text{Aut}(A^\mathbb{Z})$. Ce groupe est engendré par six applications spécifiques ($f_1, \dots, f_6$) agissant localement sur les paires de symboles.
   • Il démontre que $\Gamma$ est isomorphe au produit libre de deux groupes libres de rang 2 : $(\mathbb{Z}_2 * \mathbb{Z}_2 * \mathbb{Z}_2)^2$. Ce groupe contient une copie de $F_2 \times F_2$ (produit de deux groupes libres de rang 2).

2. Propriétés de l'action :

   • L'action de $\Gamma$ sur l'espace $S(A)$ est montrée comme étant libre presque partout (a.e. free) et préservant une mesure de probabilité.
   • En s'appuyant sur un théorème de Pemantle et Peres (2000), l'auteur établit que la relation d'équivalence induite par une action libre de $F_2 \times F_2$ est non-arborescente et non-amenable.

3. Réduction de Borel (Codage) :

   • Pour transférer ces propriétés complexes à l'alphabet binaire $\{0, 1\}$, l'auteur construit une injection de Borel $\phi$ de l'espace $S(A)$ vers l'espace des sous-décalages unilatéraux transitifs sur $\{0, 1\}$.
   • Technique de codage : Chaque symbole de l'alphabet $A$ est remplacé par un mot binaire de longueur fixe (22) via une application $\rho$. Cette application est conçue pour être uniquement lisible (uniquely readable), garantissant que la structure du sous-décalage original est préservée sans ambiguïté.
   • L'auteur démontre que si deux sous-décalages $X_1, X_2 \in S(A)$ sont conjugués via un élément de $\Gamma$, alors leurs images $\phi(X_1)$ et $\phi(X_2)$ sont conjuguées par un homéomorphisme explicite construit à partir de la structure locale des mots codés.

3. Résultats Principaux

Le théorème central de l'article est le suivant :

Théorème 1.2 : La relation de conjugaison sur les sous-décalages unilatéraux transitifs à alphabet $\{0, 1\}$ est une relation d'équivalence de Borel dénombrable qui est non-arborescente (non-treeable) et non-amenable.

Détails des résultats :

• Non-arborescence : La relation ne peut pas être représentée par un graphe acyclique borélien. Cela implique une complexité structurelle supérieure à celle des relations hyperfinies.
• Non-amenabilité : La relation ne satisfait pas les conditions d'amenabilité (liées à l'existence de moyennes invariantes), ce qui la place dans une classe de complexité plus élevée que les relations hyperfinies.
• Réponse à la question de Clemens : L'article fournit une réponse partielle mais significative à la question de Clemens sur la complexité de l'isomorphisme des décalages unilatéraux, en établissant qu'elle est au moins aussi complexe que les relations induites par des actions de groupes non-amenables.

4. Contributions Clés

1. Extension aux systèmes non-inversibles : C'est l'un des premiers résultats majeurs établissant une complexité élevée (non-arborescence) pour des systèmes dynamiques non-inversibles (unilatéraux), comblant un vide dans la littérature par rapport aux systèmes bilatéraux.
2. Réduction à l'alphabet binaire : La construction ingénieuse de l'application $\rho$ permet de réduire un problème défini sur un alphabet complexe à l'alphabet binaire minimal $\{0, 1\}$, montrant que la complexité intrinsèque n'est pas un artefact de la taille de l'alphabet.
3. Méthodologie de réduction : L'article propose une méthode robuste pour encoder des actions de groupes complexes dans des sous-décalages unilatéraux tout en préservant la relation de conjugaison, ouvrant la voie à d'autres études de classification.

5. Signification et Impact

• Classification des systèmes dynamiques : Ce résultat renforce l'idée que la classification des systèmes dynamiques topologiques (même dans des classes restreintes comme les sous-décalages) est intrinsèquement difficile et ne peut pas être réduite à des structures dénombrables simples (comme les graphes dénombrables ou les arbres).
• Théorie descriptive des ensembles : Il enrichit la hiérarchie des relations d'équivalence dénombrables de Borel en fournissant un exemple naturel de relation non-arborescente et non-amenable dans le contexte des systèmes unilatéraux.
• Perspectives futures : Ce travail suggère que la relation de conjugaison sur les sous-décalages unilatéraux pourrait être universelle ($E_\infty$), bien que cela nécessite encore une preuve de réduction inverse. Il ouvre également des questions sur la complexité pour d'autres classes de systèmes non-inversibles.

En conclusion, l'article de Ruiwen Li démontre que la complexité de la conjugaison pour les sous-décalages unilatéraux est fondamentalement élevée, défiant toute tentative de classification simple par des structures dénombrables, et établit des bornes inférieures strictes pour cette relation d'équivalence.