Étude combinatoire du mot de Thue-Morse ternaire

La combinatoire des mots est une branche des mathématiques et de l’informatique théorique qui applique l’analyse combinatoire aux mots finis ou infinis. Cette branche s’est développée à partir de plusieurs branches des mathématiques, telles que la théorie des nombres, la théorie des groupes, les probabilités et bien sûr la combinatoire. Elle a des liens avec divers thèmes informatiques, comme l’algorithmique du texte, la recherche de motifs, la compression de textes… La combinatoire des mots a pour objet d’étudier les propriétés des mots finis ou infinis. Elle remonte aux travaux du mathématicien norvégien Thue sur les suites sans répétitions de symboles, au début du 20e siècle. C’est Schützenberger qui est le fondateur de la combinatoire des mots moderne. Notamment, ses travaux avec Lyndon et Leutin ont donné naissance au livre Combinatorics on words, ouvrage collectif signé du nom de plume M. Lothaire et paru en 1983 [29]. La combinatoire de mots se développa rapidement à partir de cette date [3, 10, 9, 17, 28, 27]. Le mot t2 de Thue-Morse sur l’alphabet binaire {0, 1} est le mot infini engendré par le morphisme µ2 défini par µ2(0) = 01, µ2(1) = 10. Ce mot a été utilisé pour la première fois de façon implicite par le mathématicien français Prouhet en 1851, pour donner une solution à un problème de théorie des nombres appelé depuis le problème de Prouhet Tarry-Escott que nous rappellerons dans la suite du travail. Thue l’a découvert et utilisé dans un article publié en 1912 [44] qui, avec un autre article datant de 1906 [43], est l’article fondateur de la combinatoire des mots. En 1921 Morse va réutiliser ce mot pour donner un exemple d’une suite récurrente non périodique, résolvant ainsi un problème de géométrie différentielle [32]. Une généralisation naturelle du mot de Thue-Morse sur l’alphabet à q lettres Aq = {0, 1, …, q 1} est le mot infini tb;q engendré par le morphisme µb;q défini par : µb;q(k) = k(k + 1)…(k + b 1), où b ≥ 2 et les lettres sont exprimées modulo q. Une étude sur ce mot a été faite dans [41].

La complexité abélienne est une notion combinatoire utilisée dans l’étude des mots infinis. Cette idée est apparue quand Coven et Hedlund réalisèrent que les mots ultimement périodiques et les mots sturmiens peuvent être caractérisés en utilisant les vecteurs de Parikh [18]. Cette étude a été reprise et généralisée récemment par Richome, Saari et Zamboni dans [37], où la terminologie Complexité abélienne a été introduite. Depuis lors, l’étude des propriétés abéliennes des mots connait un essor [15, 19, 38, 45, 6]. Récemment, la notion de mots de retour a joué un rôle important dans l’étude des systèmes dynamiques (symboliques). Un facteur séparant deux occurrences successives d’un mot w dans un mot infini est appelé mot de retour de w. Cette définition est donnée par Durand dans [1]. Cette notion a été utilisée pour la caractérisation de certaines classes de mots [21, 31, 49]. Les mots de retour d’autres mots classiques ont été étudiés [7, 33]. Dans ce mémoire nous nous intéressons à l’étude du mot de Thue-Morse sur l’alphabet A3 = {0, 1, 2}. Il s’agit du mot t3 engendré par le morphisme µ3 défini par µ3(0) = 012, µ3(1) = 120 et µ3(2) = 201. Nous établissons des propriétés combinatoires de ce mot, axées sur l’équilibre, la complexité abélienne et les mots de retour. Le mot t3 de se généralise naturellement sur un alphabet Aq de taille q ≥ 3. Il s’agit, sur l’alphabet Aq = {0, 1, …, q 1}, du mot infini tq = tq;q engendré par le morphisme µq défini par : µq(k) = k(k + 1)…(k + q 1), où les lettres sont exprimées modulo q .

Alphabet, mots

On appelle alphabet A un ensemble fini de symboles. Les éléments de A sont appelés des lettres. Par exemple A = {1, a, x, } est un alphabet à quatre lettres. Soit A un alphabet. Un mot fini est une suite finie de lettres de A. La longueur d’un mot w sur A est le nombre de lettres qui le constituent. Elle est notée |w|. Pour toute lettre a de A, on note |w|a le nombre d’occurrences de a dans w. Par exemple, ababa est un mot fini sur l’alphabet A = {a, b} et nous avons |w| = 5 et |w|a = 3. Le mot vide, noté , est la suite ne contenant pas de lettre. L’ensemble des mots finis sur A est noté A∗ . L’ensemble des mots finis non vides sur A est noté A+. Un mot infini sur l’alphabet A est une suite de lettres de A indexée par N. Si w est un mot infini, on peut l’écrire sous la forme w = w1w2w3…wn… où les wi sont des lettres de A. L’ensemble des mots infinis sur A est noté A . L’ensemble des mots finis ou infinis sur A est noté A∞. Un mot infini u sur A est dit périodique s’il existe un mot w dans A tel que u = w . L’entier p = |w| est une période de u. Le mot u est dit ultimement périodique s’il existe deux mots v ∈ A∗ et w ∈ A+ tels que u = vw . Un mot non ultimement périodique est dit apériodique. On appelle concaténation l’opération binaire qui à deux éléments u = u1u2…un et v = v1v2…vm de A∗ associe uv = u1u2…unv1v2…vm. Le mot vide est l’élément neutre de cette opération. En effet, pour tout w ∈ A∗ , « w = w » = w. L’ensemble A∗ muni de la concaténation est un monoïde, d’élément neutre . De plus, chaque élément de A∗ a une unique représentation comme concaténation de lettres de A. Par conséquent, A∗ est un monoïde libre sur A. Un mot u de longueur n formé d’une seule lettre x est simplement noté u = x n . On définit la puissance n-ième d’un mot fini w comme étant la concaténation n fois de w ; on la note w n . Par extension w 0 = . On note w ∗ l’ensemble des puissances finies de w. ie si v ∈ w∗ , alors il existe un entier naturel m tel que v = wm.

Facteurs

Soient u ∈ A∞ et v ∈ A∗ . Le mot v est appelé facteur de u s’il existe u1 ∈ A∗ et u2 ∈ A∞ tels que u = u1vu2. Le facteur v est dit : préfixe de u si u1 est le mot vide ; suxe de u si u2 est le mot vide ; préfixe propre de u si u1 = et v = u ; suxe propre de u si u2 = et v = u. L’ensemble des préfixes (resp. suxes) de u est noté pref(u) (resp. suff(u)). Le nombre d’occurrences de v dans u est noté |u|v. Soit u un mot infini. L’ensemble des facteurs de longueur n de u est noté Fn(u). L’ensemble de tous les facteurs de u est noté F(u) et est appelé langage de u. Soit w = w1w2…wn un mot fini sur A. On désigne par w = wnwn−1…w2w1 le mot miroir de w. On dit que w est un palindrome si w = w. Par exemple, abba et 120021 sont des palindromes. Soient u un mot infini sur A, v un facteur de u et a une lettre de A. On dit que v est prolongeable à droite (resp. à gauche) par a, si va (resp. av) est un facteur de u. Le mot va (resp. av) est appelé un prolongement à droite (resp. à gauche) de v dans u. Le facteur v est dit spécial à droite (resp. à gauche) s’il admet au moins deux prolongements à droite (resp. à gauche). Il est dit bispécial s’il est à la fois spécial à droite et spécial à gauche. Soient u et v deux mots finis non vides. Si v est un préfixe (resp. un suxe) de u, alors v −1u (resp. uv−1 ) est le mot obtenu de u en effaçant le préfixe (resp. le suxe) v.

Complexité abélienne

Soient u un mot infini sur un alphabet Aq = {a0, a1, …, aq−1} et v un facteur de u. Le vecteur de Parikh de v est le q-uplet ψ(v) = (|v|a0 , |v|a1  …, |v|aq−1 ). On désigne par Ψn(u), l’ensemble des vecteurs de Parikh des facteurs de longueur n de u :

Ψn(u) = {ψ(v) : v ∈ Fn(u)}.

Notons que |v|a0 + |v|a1 + … + |v|aq−1 = |v|. La fonction de complexité abélienne de u est l’application définie de N dans N par :ρ ab u (n) = card(Ψn(u)).

Ainsi, la complexité abélienne ρ ab u d’un mot u est la fonction qui compte le nombre de vecteurs de Parikh de u de longueur donnée. Soient a et b deux lettres d’un alphabet A = {0, …, q 1} et v un mot fini sur A. Lorsque a = b, alors ψ(av) = ψ(vb). Lorsque a = b, alors ψ(av) ψ(vb) est le vecteur dont toutes les composantes sont 0 sauf sa (a + 1)e composante dont la valeur est 1 et sa (b + 1)e composante qui vaut 1. Ceci montre comment évoluent les vecteurs de Parikh lorsque nous considérons deux facteurs successifs de même longueur d’un mot w. Par conséquent, nous avons le résultat suivant, établi par Richomme, Saari et Zamboni dans [37].

Lemme 1.4.1 Soient v et w deux facteurs d’un mot inni u. Soient p et p + c les i e composantes respectives des vecteurs de Parikh de v et w, où p et c sont des naturels. Alors, pour tout l ∈ {0, 1, …, c}, il existe un facteur ul de u dont la ie composante du vecteur de Parikh est p + l.

Table des matières

Introduction générale
1 Préliminaires
1.1 Alphabet, mots
1.2 Facteurs
1.3 Morphismes
1.4 Complexité abélienne
1.5 Fréquences
1.6 Mots de retour
1.6.1 Utilisation des facteurs bispéciaux
1.6.2 Utilisation des ancêtres dans les mots morphiques
1.7 Mots privilégiés
2 Combinatoire du mot de Thue-Morse binaire
2.1 Introduction
2.2 Définitions
2.2.1 Relation de récurrence 1
2.2.2 Relation de récurrence 2
2.2.3 Définition directe
2.2.4 Définition par morphisme
2.3 Problème de Prouhet-Tarry-Escott
2.4 Le curieux produit infini
2.5 Partition de l’ensemble des entiers
2.6 Carrés magiques
2.7 Chevauchements
2.8 Équilibre et complexité abélienne
2.9 Mots de retour et facteurs privilégiés
2.9.1 Mots de retour
2.9.2 Facteurs privilégiés
3 Complexité abélienne du mot de Thue-Morse ternaire
3.1 Introduction
3.2 Définition et premières propriétés
3.3 Facteurs triprolongeables et équilibre
3.4 Complexité abélienne
4 Carrés de lettres, facteurs séparateurs et mots de retour dans le mot de Thue-Morse ternaire
4.1 Introduction
4.2 Fréquences
4.3 Carrés de lettres et facteurs séparateurs
4.4 Estimation du nombre de carrés de lettres dans les facteurs de t3
4.5 Facteurs biprolongeables et mots de retour dans t3
4.5.1 Facteurs bispéciaux biprolongeables
4.5.2 Mots de retour et facteurs privilégiés
Conclusion
Bibliographie

Télécharger le rapport complet