Soutenance de thèse de HENRY Raphaël
Titre de thèse
Complexité et minimalité pour les substitutions et les mots lisses
Complexity and minimality for substitutions and smooth words
Résumé de la thèse
La dynamique symbolique et la combinatoire des mots sont deux approches complémentaires pour évaluer la complexité des mots infinis, ces derniers étant souvent des versions discrètes de processus plus complexes. Cette thèse explore deux notions centrales pour décrire les mots infinis : la complexité des facteurs est la fonction qui compte les mots finis de chaque longueur, et la récurrence uniforme/minimalité est une propriété qui contrôle comment les occurrences de mots finis sont réparties.
Les substitutions sont une des principales manières de générer des mots infinis et ont donné naissance à une théorie prolifique qui est au cœur de la dynamique symbolique. En nous intéressant d'abord au problème du calcul de la complexité d'un mot morphique donné, nous présentons une revue des résultats de Pansiot et de Devyatov qui décrivent les classes de complexité possibles. Ensuite, en nous fondant sur la caractérisation des sous-shifts substitutifs minimaux donnée récemment par Shimomura, nous étudions à quel point un sous-shift peut être non-minimal. Pour cela nous caractérisons et comptons les composantes minimales de ces sous-shifts.
Au-delà du cadre substitutif, le mot de Oldenburger-Kolakoski pose des questions notoirement difficiles à propos de sa récurrence, de sa complexité et de ses fréquences. En considérant la généralisation que sont les mots lisses sur des alphabets de deux entiers, nous présentons nos contributions à deux problèmes sur ce sujet. En premier nous étudions la complexité du langage des mots lisses finis, dont la conjecture est
qu'elle croît comme Θ(n^ρ) où ρ dépend de l'alphabet. Nous prouvons la borne inférieure dans le cas général et la borne supérieure quand les deux lettres sont des entiers pairs, et nous améliorons la borne supérieure quand les deux lettres sont des entiers impairs. En second nous étudions les mots lisses sur les alphabets pairs et impairs, qui ont l'avantage d'avoir une représentation S-adique. Nous prouvons que ces mots sont uniformément récurrents, et, avec des conditions sur l'alphabet, qu'ils ont une complexité linéaire et sont uniquement ergodiques.
Thesis resume
Symbolic dynamics and combinatorics on words are two complementary approaches to evaluate how complex infinite words are, where infinite words are often seen as discrete representations of more complex processes. This thesis explores two major notions to describe infinite words: the factor complexity is the function that counts the number of finite words of each length, and uniform recurrence/minimality is the property that controls how occurrences of finite words are spread.
Substitutions are one of the primary ways to generate infinite words and gave birth to a fruitful theory in symbolic dynamics. Driven by the problem of computing the complexity class of a given morphic word, we begin by presenting a review of the results of Pansiot and Devyatov that describe the possible complexity classes. Then, inspired by the recent characterization of minimal substitution subshifts by Shimomura, we investigate how non-minimal a substitution subshift can be. To do so we characterize and count the minimal components of these subshifts.
Outside of the substitutive framework, the famous Oldenburger-Kolakoski word raises difficult questions about its recurrence, its factor complexity and its frequencies. By considering a generalization of this word called smooth words over 2-integer alphabets, we present contributions to two connected problems. We first study the factor complexity of the language of finite smooth words, which is conjectured to grow like Θ(n^ρ) where ρ depends on the alphabet. We prove the lower bound in the general case and the upper bound when the two letters are even integers, and we improve the known upper bound when the two letters are odd integers. Then we study smooth words over even and odd alphabets, which happen to have an S-adic representation. We prove that these words are uniformly recurrent, and, under conditions on the
alphabet, that they have linear factor complexity and are uniquely ergodic.