The Thue-Morse Transform

Cet article introduit la transformée de Thue-Morse, une opération sur les suites binaires basée sur les nombres « maléfiques » et « odieux », et démontre que ses itérations sur la suite classique de Thue-Morse génèrent de nouvelles familles de solutions au problème de Prouhet-Tarry-Escott tout en établissant des équations fonctionnelles et une formule exacte pour la complexité factorielle de ces suites.

L'essentiel

Le Titre : La "Transformée Thue-Morse"

Imaginez que vous avez une longue suite de lumières, allumées (1) ou éteintes (0). C'est ce qu'on appelle une séquence binaire. Le papier de Benoît Cloitre introduit un outil magique, une sorte de "machine à transformer" ces suites de lumières.

1. La Machine à Transformer (Le Concept de Base)

Prenons une séquence de départ, par exemple la célèbre séquence de Thue-Morse (une suite de 0 et de 1 très régulière mais qui semble aléatoire).

La machine fonctionne ainsi :

1. Elle regarde la séquence et note deux listes :
   • La liste des positions où il y a un 0 (les "mauvais" nombres, ou evil en anglais).
   • La liste des positions où il y a un 1 (les "méchants" nombres, ou odious en anglais).
2. Elle utilise ces deux listes pour réécrire la séquence originale. Elle dit : "Si tu es à une position qui était un 0, garde ta valeur. Si tu étais à une position qui était un 1, inverse ta valeur (0 devient 1, 1 devient 0)."

Le résultat est une nouvelle séquence de lumières.

2. La Tour de Séquences (L'Itération)

Le génie de l'auteur est de ne pas s'arrêter là. Il prend la nouvelle séquence, la passe dans la machine, et obtient une troisième. Il recommence encore et encore.

• Niveau 0 : La séquence originale.
• Niveau 1 : La première transformation.
• Niveau 2 : La deuxième transformation.
• ... et ainsi de suite, jusqu'à l'infini.

Cela crée une tour de séquences, comme des étages d'un immeuble. Chaque étage a sa propre structure, mais ils sont tous liés.

3. La Formule Magique (Le Masque)

L'auteur a découvert une astuce incroyable pour décrire n'importe quel étage de cette tour sans avoir à faire toute la machine.

Imaginez que chaque nombre entier (0, 1, 2, 3...) est écrit en binaire (comme un code à base de 0 et 1).

• Chaque étage de la tour (disons l'étage $m$) porte un masque spécial.
• Ce masque est un nombre qui dit : "Regarde seulement les chiffres du code binaire qui sont à certaines positions spécifiques."
• Si le chiffre à cette position est 1, on l'ajoute au compte. Si c'est 0, on ne fait rien.
• Le résultat final (0 ou 1) dépend de la parité (pair ou impair) du nombre de 1 trouvés.

L'analogie : C'est comme si chaque étage de la tour avait un tampon différent. Pour savoir si une lumière est allumée ou éteinte à l'étage 5, vous ne regardez que les bits de votre numéro de maison qui correspondent au "mot de passe" de l'étage 5. C'est une règle simple et précise qui remplace des calculs compliqués.

4. Pourquoi est-ce utile ? (Le Problème Prouhet-Tarry-Escott)

À quoi sert tout cela ? À résoudre un vieux casse-tête mathématique : Comment diviser un groupe de nombres en deux équipes pour que leurs sommes soient égales ?

• Le problème : Si vous prenez les nombres de 0 à 15, pouvez-vous les séparer en deux groupes (Groupe A et Groupe B) de sorte que la somme des nombres, la somme de leurs carrés, la somme de leurs cubes, etc., soit exactement la même pour les deux groupes ?
• La solution classique : La séquence de Thue-Morse originale (Niveau 0) le fait déjà pour les carrés.
• La découverte de ce papier : En montant dans la tour (en changeant le masque), on peut créer des groupes qui restent égaux non seulement pour les carrés, mais aussi pour les cubes, les puissances 4, 5, et bien plus encore ! Plus on monte dans la tour, plus on peut résoudre ce problème pour des puissances très élevées.

C'est comme si on trouvait de nouvelles façons de peser des objets sur une balance pour qu'elle reste parfaitement équilibrée, même avec des poids très complexes.

5. Les Extensions (Au-delà du binaire)

L'auteur montre que cette machine n'est pas limitée aux seuls 0 et 1 :

• Version "Base-d" : On peut faire la même chose avec des chiffres de 0 à 9 (ou plus), comme si on utilisait un système décimal au lieu de binaire.
• Version "Fibonacci" : On peut essayer d'appliquer cette machine à une suite de nombres basée sur la suite de Fibonacci (1, 1, 2, 3, 5...). C'est comme essayer de faire tourner la même machine avec un carburant différent. Les résultats sont différents, mais la logique reste fascinante.

En Résumé

Ce papier nous dit :

1. Il existe une machine simple qui transforme des suites de nombres.
2. En répétant cette machine, on crée une famille infinie de suites nouvelles.
3. On a trouvé une formule simple (un "masque") pour prédire le résultat de n'importe quelle répétition.
4. Ces nouvelles suites sont des outils puissants pour résoudre des problèmes d'équilibre mathématique (sommes de puissances) que l'on ne pouvait pas résoudre aussi facilement auparavant.

C'est un peu comme découvrir que si vous pliez une feuille de papier d'une certaine manière, puis encore, et encore, vous obtenez des motifs géométriques parfaits qui peuvent servir à construire des ponts mathématiques très solides.

Résumé technique

1. Problématique et Contexte

L'article s'inscrit dans le domaine de la théorie des nombres et de la combinatoire des mots, en se concentrant sur la généralisation du problème de Prouhet-Tarry-Escott (PTE). Ce problème classique consiste à partitionner un ensemble d'entiers en deux sous-ensembles disjoints de telle sorte que les sommes des puissances $k$-ièmes des éléments soient égales pour tous les degrés $k$ jusqu'à un certain seuil.

La construction classique de Prouhet utilise la séquence de Thue-Morse $t(n) = s_2(n) \pmod 2$ (où $s_2(n)$ est la somme des bits binaires de $n$) pour partitionner les entiers en nombres « maléfiques » (evil, somme de bits paire) et « odieux » (odious, somme de bits impaire).

L'auteur introduit une nouvelle opération, la Transformée de Thue-Morse (TM-transform), agissant sur les séquences binaires. Le but principal est d'étudier l'orbite de la séquence de Thue-Morse classique sous l'itération de cette transformée, révélant une structure hiérarchique riche qui généralise les solutions PTE et les propriétés arithmétiques des nombres maléfiques et odieux.

2. Méthodologie

La méthodologie repose sur plusieurs piliers techniques :

• Définition de la Transformée : Pour une séquence binaire $\sigma$ (commençant par 01 et prenant chaque valeur infiniment souvent), on définit les nombres maléfiques $v_\sigma(n)$ (positions des 0) et odieux $u_\sigma(n)$ (positions des 1). La transformée $T(\sigma) = \tau$ est définie par les relations de récurrence :
  $$\tau(v_\sigma(n)) = \tau(n) \quad \text{et} \quad \tau(u_\sigma(n)) = 1 - \tau(n)$$
  avec $\tau(0)=0$.
• Itération et Formule Explicite : En partant de la séquence de Thue-Morse classique $a_0 = t$ et en définissant $a_{m+1} = T(a_m)$, l'auteur démontre que cette tour de séquences admet une forme close explicite basée sur des masques de bits.
• Analyse Arithmétique et Automatique : L'étude utilise les propriétés des séquences automatiques, les fonctions génératrices, et l'analyse des compositions de fonctions (itérations de nombres maléfiques/odieux généralisés).
• Complexité des Facteurs : Pour les niveaux spécifiques (niveaux de Mersenne), l'auteur utilise une méthode de « désubstitution » sur la séquence dérivée pour calculer exactement la complexité des facteurs (nombre de sous-mots distincts).
• Généralisations : L'approche est étendue aux bases $d$ (généralisation $d$-aire) et à d'autres systèmes de numération (comme la numération de Zeckendorf pour l'analogie Fibonacci).

3. Contributions Clés et Résultats Principaux

A. La Tour de Thue-Morse et la Formule Masquée

Le résultat central est l'identification explicite de la $m$-ième itération $a_m(n)$. Pour tout $m \ge 0$ et $n \ge 0$ :
$$a_m(n) = \bigoplus_{p \ge 0, \, p \,\&\, m = 0} b_p(n)$$
où $b_p(n)$ est le $p$-ième bit de $n$, $\oplus$ est le XOR, et $\&$ est le ET bit à bit.

• Interprétation : Le paramètre $m$ agit comme un masque. Seuls les bits de $n$ dont les positions sont disjointes du support binaire de $m$ contribuent à la somme.
• Structure : Cela génère une famille de séquences automatiques dont la structure est contrôlée par le nombre de positions de bits sélectionnées par le masque.

B. Solutions Généralisées au Problème PTE

Pour chaque niveau $m$ et une longueur d'intervalle appropriée $N$, la partition induite par $a_m$ fournit de nouvelles familles de solutions au problème PTE.

• Degré de PTE : Le degré de validité des sommes de puissances égales est $s_m L - 1$, où $s_m$ est le nombre de positions de bits sélectionnées par le masque $m$ sur une période, et $L$ est un paramètre d'échelle.
• Généralisation : Cela étend la construction classique de Prouhet (qui correspond au cas $m=0$) en permettant d'augmenter le degré de validité non pas par itération de morphismes, mais par le choix du masque $m$. De plus, en croisant plusieurs niveaux ($k$ niveaux), on obtient des partitions en $2^k$ classes.

C. Équations Fonctionnelles pour les Nombres Généralisés

L'article étudie les nombres maléfiques et odieux généralisés $v_m(n)$ et $u_m(n)$ associés à $a_m$.

• Lois de Composition : Les itérations composées (ex: $u_m(u_m(n))$) satisfont des équations fonctionnelles rigides.
• Correction Non-Triviale : Contrairement au cas classique ($m=0$) où les termes de correction sont constants (0 ou 1), pour $m > 0$, les termes de correction deviennent des séquences automatiques non triviales (notées $c_m(n)$). Ces corrections dépendent de la parité de $m$ et de la structure du masque.
• Interactions Inter-niveaux : Des équations fonctionnelles croisées sont établies pour les compositions entre différents niveaux de la tour ($u_m \circ u_{m'}$).

D. Complexité des Facteurs (Niveaux de Mersenne)

Pour les niveaux où $m = 2^K - 1$ (nombres de Mersenne), l'auteur détermine complètement la complexité des facteurs $p_{a_m}(n)$.

• Régime Linéaire Initial : Pour $n \le B+1$ (où $B$ est une période liée à $m$), la complexité est exactement $2n$.
• Formule Hiérarchique : Au-delà de ce régime, la complexité suit une formule par morceaux précise, obtenue via l'analyse de la séquence dérivée $\Delta(n) = a_m(n) \oplus a_m(n+1)$, qui est un point fixe d'une substitution uniforme.

E. Extensions au-delà du Binaire

• Base $d$ : Le mécanisme PTE est généralisé à n'importe quelle base $d$, utilisant des racines de l'unité pour les fonctions génératrices.
• Séquence Méta-Thue-Morse : L'article montre que la séquence $M_2$ (définie par Campbell et Cloitre) suit le même cadre de factorisation, prouvant que la transformée n'est pas limitée à la graine classique.
• Analogie Fibonacci : L'application de la transformée à la séquence de Thue-Morse-Fibonacci (numération de Zeckendorf) est explorée. Bien que la factorisation en produit simple disparaisse (à cause de la dépendance des chiffres de Fibonacci), une récurrence de transfert permet d'obtenir des résultats partiels sur les défauts de PTE (balance exacte au degré 0, formules explicites pour les degrés 1 et 2).

4. Signification et Impact

Ce travail apporte plusieurs avancées significatives :

1. Unification : Il unifie la théorie des séquences automatiques, le problème PTE et la théorie des nombres maléfiques/odieux sous un seul opérateur itératif.
2. Nouvelles Solutions PTE : Il fournit une méthode systématique pour générer de nouvelles familles de solutions PTE avec des degrés contrôlables par un paramètre binaire ($m$), dépassant les constructions morphiques classiques.
3. Richesse Arithmétique : Il révèle que l'itération de la transformée de Thue-Morse produit une structure arithmétique beaucoup plus riche que le cas initial, transformant des corrections constantes en séquences automatiques complexes.
4. Ouverture de Problèmes : L'article ouvre la voie à l'étude des orbites de la transformée sur d'autres séquences automatiques ou morphiques, et pose des questions sur la complexité des facteurs pour les niveaux non-Mersenne et la généralisation complète en base $d$.

En résumé, Benoît Cloitre démontre que la transformée de Thue-Morse est un outil puissant pour explorer la structure profonde des partitions d'entiers et des séquences automatiques, offrant des formules explicites là où l'on s'attendait souvent à des comportements chaotiques ou purement algorithmiques.