WELLDOC property for words generated by morphisms

Cet article étudie la propriété WELLDOC, une notion de distribution abélienne des occurrences dans les mots infinis, et fournit un critère pour déterminer si les mots générés par des morphismes possèdent cette propriété.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire une ville infinie, rue après rue, en suivant un plan très précis. Ce plan, c'est ce que les mathématiciens appellent un morphisme. Vous commencez par une seule brique (une lettre), vous la transformez en une petite rue, puis vous transformez chaque brique de cette rue en une nouvelle rue, et ainsi de suite, à l'infini.

Le papier dont nous parlons aujourd'hui, écrit par Svetlana Puzynina et Vladimir Shavelev, s'intéresse à une question fascinante : comment les briques sont-elles réparties dans cette ville infinie ?

Le Problème : La "Grille" Invisible

Dans le monde des nombres aléatoires (comme ceux utilisés pour les jeux vidéo ou la cryptographie), il y a un défaut caché appelé la "structure de réseau". Imaginez que vous lancez des fléchettes sur une cible. Si elles tombent parfaitement au hasard, elles couvrent toute la cible de manière uniforme. Mais si elles suivent un plan mathématique trop rigide, elles pourraient finir toutes alignées sur des lignes invisibles, comme des grains de riz sur une grille. C'est ce qu'on appelle une "structure de réseau" : c'est trop ordonné, pas assez aléatoire.

Les auteurs étudient une propriété appelée WELLDOC (pour Well Distributed Occurrences, ou "occurrences bien réparties").

• L'idée simple : Si vous prenez n'importe quel mot (par exemple, "chat") dans votre ville infinie, et que vous regardez tout ce qui se trouve avant chaque fois que ce mot apparaît, vous devriez pouvoir trouver des combinaisons de lettres qui correspondent à n'importe quel motif imaginable, même si vous regardez les choses sous un angle très spécifique (modulo un nombre $m$).
• La métaphore : C'est comme si, peu importe où vous vous placez dans la ville pour chercher un café ("le mot"), vous pouviez toujours trouver un chemin pour arriver à n'importe quelle adresse précise dans la ville, en respectant n'importe quelle règle de comptage que vous inventeriez. Si c'est le cas, la ville est "bien répartie" et ne souffre pas du défaut de la grille.

La Solution : La Règle du "1" et "Minus 1"

Les auteurs ont découvert une règle magique pour savoir si une ville construite par un plan (un morphisme) sera bien répartie ou non. Tout dépend d'un outil mathématique appelé matrice, qui résume comment les lettres se transforment.

Imaginez que cette matrice est une balance.

1. Pour les villes à deux lettres seulement (comme 0 et 1) :
   La ville sera parfaitement répartie (elle aura la propriété WELLDOC) si et seulement si le "poids" de cette balance (le déterminant de la matrice) est exactement 1 ou -1.

   • Analogie : C'est comme si la recette de transformation des briques était parfaitement équilibrée. Si le poids est 2, 3 ou autre, la ville finira par avoir des zones vides ou trop pleines, créant cette grille invisible indésirable.

2. Pour les villes avec plus de deux lettres (3, 4, 5... lettres) :
   La règle du "1 ou -1" reste nécessaire, mais ce n'est plus suffisant ! Il faut une condition supplémentaire.

   • L'ajout : Il faut s'assurer que les "retours" aux premières lettres (les chemins qui reviennent au point de départ) sont assez variés pour couvrir tout l'espace possible.
   • Analogie : Imaginez que vous avez une balance parfaite (poids 1), mais que vous n'avez que des briques rouges et bleues. Si vous essayez de construire une ville avec 5 couleurs, vous manquerez de briques vertes, jaunes et oranges pour remplir tous les coins. Les auteurs disent qu'il faut vérifier que les chemins de retour apportent assez de "couleurs" (de vecteurs) pour remplir tout l'espace.

Pourquoi est-ce important ?

Pourquoi se soucier de ces villes de lettres ?

• Générateurs de nombres aléatoires : Les ordinateurs ont besoin de nombres "aléatoires" pour les jeux, les simulations et la sécurité. Les méthodes classiques ont souvent ce défaut de "grille" (structure de réseau).
• L'avantage des mots morphiques : Les mots générés par ces plans (morphismes) sont très rapides à produire par un ordinateur.
• Le résultat : Si vous choisissez un plan (un morphisme) qui respecte la règle du déterminant 1 ou -1 (et la condition supplémentaire pour les grands alphabets), vous obtenez une séquence de nombres qui n'a pas ce défaut de grille. C'est comme passer d'une ville où les gens sont coincés sur des rails, à une ville où les gens peuvent aller partout librement.

En Résumé

Ces chercheurs ont résolu une énigme ouverte : Comment savoir si un plan de construction infini crée une répartition parfaite ?

• La réponse : Regardez la "balance" de votre plan.
  • Si c'est un plan simple (2 lettres), le poids doit être 1 ou -1.
  • Si c'est un plan complexe (plus de 2 lettres), le poids doit être 1 ou -1 ET les chemins de retour doivent être assez diversifiés pour remplir tout l'espace.

C'est une recette précise pour construire des suites de nombres qui semblent vraiment aléatoires, sans les défauts cachés des méthodes anciennes, le tout en utilisant des constructions mathématiques très rapides à calculer.

Résumé technique

Voici un résumé technique détaillé de l'article « WELLDOC property for words generated by morphisms » de Svetlana Puzynina et Vladimir Shuravlev.

1. Problématique et Contexte

L'article étudie une propriété combinatoire des mots infinis appelée WELLDOC (pour Well Distributed Occurrences). Cette propriété concerne la régularité de la distribution des facteurs (sous-mots) dans un mot infini.

• Définition du problème : Un mot infini $w$ sur un alphabet $\Sigma$ satisfait la propriété WELLDOC si, pour tout facteur $u$ de $w$, tout entier $m \ge 1$ et tout vecteur $v \in (\mathbb{Z}/m\mathbb{Z})^{|\Sigma|}$, il existe une occurrence de $u$ dans $w$ telle que le vecteur de Parikh du préfixe précédant cette occurrence soit congru à $v$ modulo $m$.
  • Le vecteur de Parikh d'un mot compte le nombre d'occurrences de chaque lettre de l'alphabet.
• Motivation : Cette propriété a été introduite dans le contexte des générateurs de nombres pseudo-aléatoires (GPNR). Les générateurs congruentiels linéaires classiques souffrent d'un défaut de « structure de réseau » (lattice structure), où les points générés sont contenus dans des hyperplans équidistants, ne couvrant pas tout l'espace.
• Lien avec les mots morphiques : Il a été démontré que combiner des générateurs linéaires via un mot infini $w$ codant des ensembles de coupe-et-projection (quasi-cristaux) permet d'éliminer ce défaut si $w$ satisfait la propriété WELLDOC. Les auteurs cherchent à caractériser les morphismes qui génèrent de tels mots.

2. Méthodologie

Les auteurs utilisent une approche combinatoire et algébrique pour analyser les mots infinis générés par des morphismes (mots morphiques).

• Outils Algébriques :
  • Utilisation de la matrice de morphisme $A_\phi$ (matrice de Parikh) dont les entrées comptent les occurrences de lettres dans les images des lettres de l'alphabet.
  • Analyse des propriétés de déterminant de $A_\phi$ sur les anneaux $\mathbb{Z}$ et $\mathbb{Z}/m\mathbb{Z}$.
  • Étude des groupes additifs générés par les vecteurs de Parikh des « mots de retour » (return words) vers la première lettre du mot.
  • Utilisation de la théorie des sous-décalages (subshifts) et de la reconnaissabilité des morphismes (théorèmes de Mossé) pour prouver la nécessité des conditions.
• Stratégie de preuve :
  • Suffisance : Démontrer que si les conditions algébriques sont remplies, alors l'ensemble des vecteurs de Parikh des préfixes couvre tout l'espace $(\mathbb{Z}/m\mathbb{Z})^{|\Sigma|}$. Cela repose sur le fait que si $\det(A_\phi) = \pm 1$, la matrice est inversible modulo $m$, permettant de « résoudre » n'importe quel vecteur cible.
  • Nécessité : Montrer que si les conditions ne sont pas remplies (déterminant non unitaire ou vecteurs de retour ne générant pas l'espace), il existe un module $m$ et un vecteur cible inatteignables. Cela est prouvé en utilisant l'existence de facteurs « coupants » (cutting factors) lorsque le morphisme n'est pas reconnaissable ou lorsque le déterminant pose problème.

3. Contributions Clés et Résultats Principaux

Le résultat central de l'article est un critère nécessaire et suffisant pour qu'un mot infini généré par un morphisme possède la propriété WELLDOC.

A. Cas des alphabets binaires (Théorème 1)

Pour un mot binaire infini récurrent $w$ généré par un morphisme $\phi$ :

• $w$ satisfait la propriété WELLDOC si et seulement si le déterminant de la matrice du morphisme est égal à $\pm 1$ ($\det A_\phi = \pm 1$).
• Note : Les mots périodiques triviaux ($0^\infty$,$1^\infty$) sont exclus de cette caractérisation car ils satisfont trivialement la propriété mais ont un déterminant différent.

B. Cas des alphabets non-binaires (Théorème 2)

Pour un mot infini $w$ sur un alphabet $\Sigma$ ($|\Sigma| \ge 2$) généré par un morphisme $\phi$ :

• $w$ satisfait la propriété WELLDOC si et seulement si deux conditions sont réunies :
  1. $\det A_\phi = \pm 1$.
  2. Les vecteurs de Parikh des mots de retour à la première lettre de $w$ (les facteurs entre deux occurrences consécutives de la première lettre) génèrent le groupe additif $\mathbb{Z}^{|\Sigma|}$.

C. Décidabilité

• Les auteurs prouvent que la condition sur les vecteurs de retour (condition 2 du Théorème 2) est décidable. Ils proposent un algorithme qui calcule les vecteurs de Parikh des retours modulo $m$ et vérifie s'ils génèrent le groupe $(\mathbb{Z}/m\mathbb{Z})^{|\Sigma|}$ pour tous les nombres premiers $m$.

D. Applications et Exemples

• Mots de Sturmian et Épisturmian : L'article rétablit le fait que les mots de Sturmian et épisturmian générés par des morphismes satisfont la propriété WELLDOC. Cela découle du fait que les matrices de ces morphismes ont un déterminant $\pm 1$ et que les vecteurs de retour génèrent l'espace.
• Contre-exemple : Un exemple est fourni montrant un morphisme sur un alphabet de taille 3 avec $\det A_\phi = 1$, mais où la propriété WELLDOC échoue car les vecteurs de retour ne génèrent pas $\mathbb{Z}^3$. Cela confirme que la condition sur les retours est indispensable pour les alphabets non-binaires.

4. Signification et Impact

• Théorique : Ce travail complète la caractérisation des mots morphiques possédant des propriétés de distribution uniforme abélienne. Il établit un lien fort entre l'algèbre linéaire (déterminant de la matrice de substitution) et la combinatoire des mots (distribution des facteurs).
• Pratique (Cryptographie et Simulation) : La propriété WELLDOC est cruciale pour la conception de générateurs de nombres pseudo-aléatoires sans défaut de structure de réseau. Les résultats permettent de sélectionner efficacement des morphismes (générant des mots très rapidement) pour construire des séquences aléatoires de haute qualité, évitant ainsi les biais statistiques liés aux structures de réseaux des générateurs linéaires classiques.
• Algorithmique : La preuve de la décidabilité de la condition offre un outil pratique pour vérifier si un morphisme donné est adéquat pour des applications de génération aléatoire.

En résumé, l'article fournit une réponse complète à la question ouverte posée par Guimond et al. (2013) concernant la caractérisation des morphismes générant des mots WELLDOC, en distinguant clairement les cas binaires et non-binaires et en intégrant des outils avancés de la théorie des systèmes dynamiques symboliques.