La complexité combinatoire d'un mot ou plus simplement la complexité d'un mot ou d'une suite est un moyen de mesurer, en combinatoire et en mathématique, et spécialement en combinatoire des mots, divers paramètres d'un mot qui expriment combien il est « compliqué ».
La complexité combinatoire est une mesure différente de la complexité algorithmique ou complexité de Kolmogorov. Ici, on considère le plus souvent la complexité en facteurs ().
Parmi les mots distingués dans les diverses mesures de complexité combinatoire, il y a ceux dont la complexité est particulièrement basse. Un mot de faible complexité est un mot infini dont la fonction de complexité est « à croissance lente »; on entend par là une fonction qui croît linéairement, ou polynomialement, en tout cas nettement moins vite qu'une exponentielle. Il existe de nombreuses familles de mots infinis, comme les mots automatiques, les mots morphiques, les mots sturmiens et les mots épisturmiens, qui ont une croissance lente en ce sens.
Une application importante de l'étude des mots infinis à croissance lente est à la théorie des nombres : les mots infinis qui représentent le développement d'un nombre sont à croissance lente si le nombre est rationnel ou transcendant, et plus rapide si le nombre est algébrique irrationnel. On dispose ainsi d'un moyen assez général pour construire des nombres transcendants.
La complexité d'un mot fini ou infini peut se mesurer aussi par le nombre de palindromes; on parle alors de complexité palindromique. Ces deux notions de complexité combinatoire sont liées. Encore une autre mesure de complexité est la complexité abélienne d'un mot.
Complexité en facteurs La fonction de complexité ou complexité en facteurs d'un mot fini ou infini est la fonction
qui, pour chaque entier naturel , donne le nombre de facteurs (ou blocs, ou plages) distincts de longueur dans ce mot. On trouve aussi la notation ou pour la valeur en de cette fonction.
Premier exemple. Le mot infini . Il a pour complexité et pour .
Deuxième exemple. Le mot infini de Champernowne . Ce mot est obtenu en concaténant les développements binaires des entiers naturels. Pour tout , chacun des mots de longueur est facteur de , donc la complexité du mot de Champernowne est .
Justification de la terminologie L'entropie topologique d'un mot infini est la limite
Cette limite existe, car on a , donc la fonction est sous-additive et la limite ci-dessus existe par le lemme de Fekete. Les mots de faible complexité sont les mots d'entropie nulle.
Complexité minimale
Pour un mot infini , un résultat dû à Ethan M. Coven et Gustav Hedlund dit que si pour un entier , alors le mot est ultimement périodique. Plus précisément, on a:
Les mots infinis apériodiques de complexité minimale sont binaires (sur un alphabet à deux lettres), et ont une fonction de complexité égale à . Ce sont les mots sturmiens. Le plus connu des mots sturmiens est le mot de Fibonacci.
Complexité de mots morphiques
Mots purement morphiques
Le théorème suivant donne une classification des fonctions de complexités pour les mots purement morphiques.
Exemples Les mots ultimement périodiques sont de complexité ultimement constante.
Le mot de Fibonacci est sturmien et morphique. Il est de complexité linéaire.
Un mot de complexité en : le morphisme
engendre, à partir de la lettre , le mot infini :
Sa complexité est en .
Un mot de complexité en : le morphisme
engendre, à partir de la lettre , le mot infini :
Sa complexité est .
Un mot de complexité en : le morphisme
engendre, à partir de la lettre , le mot infini :
La suite des exposants des est :. Sa complexité est (ça demande un peu de calcul !).
Mots morphiques
Les fonctions de complexité des mots morphiques ne sont pas encore complètement caractérisées en 2010 (voir ). On sait :
On sait que pour tout entier , il existe effectivement un mot infini binaire morphique tel que .
Exemple Soit un alphabet à lettres et considérons le morphisme défini par
et soit donné par pour , , et . On voit que
pour des entiers , et on peut prouver que la suite de croît comme d'où l'on peut déduire que .
Complexité et transcendance
Il y a un lien étroit entre la transcendance d'un nombre réel et la complexité du mot infini qu'est son développement dans une base donnée. Soit un entier. Pour tout nombre réel avec , il existe un mot infini unique
à éléments dans l'ensemble tel que
avec la condition supplémentaire que ne se termine pas par une infinité de . Par exemple, en base 10, on a . Réciproquement, un développement en base décrit un nombre réel unique. Un nombre réel est rationnel si et seulement si son développement est ultimement périodique.
On note
le nombre de facteurs de longueur du mot infini qui est le développement de en base , en d'autres termes . On dira pour faire vite que c'est la complexité de , au lieu de dire la complexité du développement de . On a alors le théorème suivant
La conclusion du théorème dit que la fonction de complexité de croît plus vite que linéairement. La conséquence immédiate de ce théorème est que si , et si est irrationnel, alors est transcendant. Or, il existe de nombreux mots infinis de complexité linéaire, et tous ces mots infinis représentent donc des nombres soit rationnels, soit transcendants.
Par exemple, tous les nombres irrationnels dont le développement est une suite automatique sont transcendants. Tous les nombres dont le développement est un mot sturmien sont transcendants. La même conclusion vaut pour les mots épisturmiens non ultimement périodiques.
Complexité abélienne
La complexité abélienne d'un mot fini ou infini est la fonction qui compte le nombre de facteurs de longueur donnée dans ce mot, à permutation de lettres près. C'est une autre mesure de la complexité combinatoire d'une suite.
Exemple. Les 7 facteurs de longueur 6 du mot de Fibonacci sont Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les cinq mots contenant deux occurrences de , et les deux qui en contiennent trois. La complexité abélienne prend donc la valeur 2.
Mots de complexité abélienne maximale On note la fonction complexité abélienne d'un mot .
Propriété.- La complexité abélienne d'un mot infini sur lettres vérifie pour tout . Cette borne est atteinte par la suite de Champernowne par exemple.
Mot de Thue-Morse Le mot de Thue-Morse a la fonction de complexité suivante :
En fait, une sorte de réciproque est vraie aussi: Si un mot infini binaire récurrent a la même fonction de complexité et la même fonction de complexité abélienne que le mot de Thue-Morse, alors il a les mêmes facteurs.
Mots sturmiens Un mot sturmien est un mot infini binaire qui a exactement facteurs de longueur , pour tout entier naturel . L'exemple paradigmatique de mot sturmien est le mot de Fibonacci.
Parmi les nombreuses propriétés des mots sturmiens, on a la caractérisation. :
Propriété.- La complexité abélienne d'un mot sturmien est constante et égale à . Réciproquement, un mot apériodique qui a complexité abélienne constante égale à est sturmien.
Complexité binomiale
Deux mots sont dits k-binomialement équivalents lorsqu'ils possèdent les mêmes sous-mots de longueur au plus k avec les mêmes multiplicités.. Cette mesure est un raffinement de l'équivalence abélienne et de la congruence de Simon.. La complexité k-binomiale d'un mot infini est, pour tout entier , le nombre de classes, pour cette relation d'équivalence, de l'ensemble des facteurs de longueur apparaissant dans .. La complexité -binomiale du mot de Thue-Morse, bien que le mot de Thue-Morse soit apériodique, ne prend que deux valeurs..
Définition Formellement, deux mots u et v sont k-binomialement équivalents si
pour tout mot de longueur au plus . Dans cette définition,
est le nombre d'occurrences du mot x comme sous-mot de . Les coefficients binomiaux de mots ont des propriétés proches de celles des nombres. Ainsi, on a par exemple :
Exemples Les quatre mots et sont 2-binomialement équivalents. Si est l'un de ces quatre mots, on a en effet les coefficients suivants : et . Ces mots ne sont pas 2-binomialement équivalents. Par exemple, on a et . En effet, dans ce deuxième mot, le sous-mot apparaît en 4 positions : . Pour , l'équivalence binomiale coïncide avec l'équivalence commutative.
On note le fait que et sont -binomialement équivalents. La relation est compatible avec la concaténation :
implique pour tous mots .
Complexité binomiale du mot de Thue-Morse On note la complexité d'un mot , c'est-à-dire le nombre de facteur de longueur apparaissant dans , et on note ou plus simplement la complexité -binomiale de , c'est-à-dire le nombre classes de sous-mots -équivalents de longueur du mot . Pour le mot de Thue-Morse, on a le résultat suivant :
Ainsi, pour , la complexité -binomiale du mot de Thue-Morse ne prend que 2 valeurs ; de plus, la deuxième valeur est égale à .
Complexité binomiale des mots sturmiens La complexité -binomiale d'un mot sturmien est égale à sa complexité en facteur. Plus précisément, on
Pour , la complexité binomiale est égale à la complexité abélienne, et vaut donc 2. Pour des valeurs plus grandes de k, on montre que deux facteurs distincts de même longueur d'un mot sturmien ne sont jamais -binomialement équivalents.
Voir aussi.. Complexité cyclique Définition La complexité cyclique d’un mot infini est la fonction Ne pas confondre avec la complexité « ordinaire » qui, dans ce contexte, est notée qui compte le nombre de classes de conjugaison (ou mots circulaires, ou colliers) de facteurs de longueur dans le mot : pour être tout à fait précis : est le nombre de classes de conjugaison que rencontre l’ensemble des facteurs de longueur .
Exemple. Les cinq facteurs de longueur 4 du mot de Fibonacci infini sont Ces facteurs se regroupent, par permutation circulaire, en deux classes : les trois mots forment contenant une seule occurrence de , et les deux qui en contiennent deux. La complexité cyclique prend donc la valeur 2.
On a , où est la complexité abélienne et est la complexité ordinaire. La complexité en facteurs, la complexité abélienne et la complexité cyclique peuvent être vues comme des actions de divers sous-groupes du groupe symétrique sur les indices d’un mot fini, à savoir respectivement le sous-groupe trivial, le groupe symétrique en entier et le sous-groupe cyclique engendré par la permutation (1,2,…,n).
Théorème : Un mot est ultimement périodique si et seulement si sa complexité cyclique est bornée.
Ceci est l’analogue du théorème de Morse-Hedlund.
Mots sturmiens
Propriété : Soient et deux mots infinis de même complexité cyclique. Si l’un des deux mots est sturmien, alors l’autre l’est également et, à un renommage des lettres près, ils ont même ensemble de facteurs.
La valeur minimale de la fonction de complexité cyclique d’un mot non périodique est 2, car si tous les facteurs de longueur d’un mot sont conjugués, ce mot est périodique. En particulier, si est sturmien, alors , mais ceci ne caractérise pas les mots sturmiens.
Mot de Thue-Morse
Pour le mot de Thue-Morse la fonction de complexité cyclique n'est pas bornée : on a ,
Complexité en palindromes
Définition La fonction de complexité en palindromes ou complexité palindromique d'un mot fini ou infini est la fonction
qui, pour chaque entier , donne le nombre de facteurs (ou blocs) distincts de longueur dans ce mot qui sont des palindromes. Bien entendu, on a toujours .
Exemple Le mot , préfixe du mot de Prouhet-Thue-Morse a les facteurs 9 palindromes , et , et .
Exemple Le mot de Fibonacci infini a les facteurs palindromes , et on peut démontrer que
Cette propriété est caractéristique des mots sturmiens.
Comparaison des deux mesures de complexité
Soit un mot infini, et soit sa complexité en palindromes et sa complexité en facteurs. Bien entendu, on a toujours . Il y a une borne bien meilleure. :