Complexité d'un mot

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 (en anglais « subword complexity »).

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 $x$ est la fonction

$n\mapsto c_{x}(n)$

qui, pour chaque entier $n$, donne le nombre $c_{x}(n)$ de facteurs (ou blocs) distincts de longueur $n$ dans ce mot. On trouve aussi la notation $p_{x}(n)$ ou $P(x,n)$ pour la valeur en $n$ de cette fonction.

Premier exemple. Le mot infini

$u=01(10)^{\omega }=01101010\ldots$.

Il a pour complexité $c_{u}(0)=1,c_{u}(1)=2,c_{u}(2)=3$ et $c_{u}(n)=4$ pour $n\geq 3$

Deuxième exemple. Le mot infini de Champernowne

$x=0110111001011101111000\ldots$.

Ce mot est obtenu en concaténant les développements binaires des entiers naturels. Pour tout $n$, chacun des $2^{n}$ mots de longueur $n$ est facteur de $x$, donc la complexité du mot de Champernowne est $2^{n}$.

Justification de la terminologie

L'entropie topologique d'un mot infini $x$ est la limite

$\lim _{n\to \infty }{\frac {1}{n}}\log c_{x}(n)$

Cette limite existe, car on a

$c_{x}(n+m)\leq c_{x}(n)c_{x}(m)$

donc la fonction $\log c_{x}(n)$ 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 $x$, un résultat dû à Ethan M. Coven et Gustav Hedlund dit que si $c_{x}(n)\leq n$ pour un entier $n$, alors le mot $x$ est ultimement périodique. Plus précisément, on a:

Théorème (Coven, Hedlund) —  Soit $x$ un mot infini sur un alphabet à $k$ lettres. Les conditions suivantes sont équivalentes :

1. $c_{x}(n)<n+k-1$ pour un entier $n$,
2. $c_{x}(n)=c_{x}(n+1)$ pour un entier $n$,
3. la fonction $n\mapsto c_{x}(n)$ est bornée,
4. le mot $x$ est ultimement périodique.

Les mots infinis apériodiques de complexité minimale sont binaires (sur un alphabet à deux lettres), et ont une fonction de complexité égale à $n+1$. 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.

Théorème (Pansiot) —  Soit $x$ un mot infini purement morphique. La fonction de complexité de $x$ vérifie l'une des propriétés suivantes

1. $c_{x}(n)=\Theta (1)$,
2. $c_{x}(n)=\Theta (n)$,
3. $c_{x}(n)=\Theta (n\log \log n)$,
4. $c_{x}(n)=\Theta (n\log n)$,
5. $c_{x}(n)=\Theta (n^{2})$.

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 $\Theta (n^{2})$ : le morphisme

${\begin{array}{lcl}a&\mapsto &ab\\b&\mapsto &bc\\c&\mapsto &c\end{array}}$

engendre, à partir de la lettre $a$, le mot infini :

$abbcbc^{2}bc^{3}\cdots bc^{n}\cdots$

Sa complexité est en $\Theta (n^{2})$.

Un mot de complexité en $\Theta (n\log n)$ : le morphisme

${\begin{array}{lcl}a&\mapsto &abc\\b&\mapsto &bb\\c&\mapsto &ccc\end{array}}$

engendre, à partir de la lettre $a$, le mot infini :

$abcb^{2}c^{3}b^{4}c^{9}\cdots b^{2^{n}}c^{3^{n}}\cdots$

Sa complexité est $\Theta (n\log n)$.

Un mot de complexité en $\Theta (n\log \log n)$ : le morphisme

${\begin{array}{lcl}a&\mapsto &abab\\b&\mapsto &bb\end{array}}$

engendre, à partir de la lettre $a$, le mot infini :

$(aba)b^{3}(aba)b^{7}(aba)b^{3}(aba)b^{15}(aba)b^{3}(aba)b^{7}(aba)b^{3}(aba)b^{31}\cdots$

La suite des exposants des $b$ est :$1,3,1,7,1,3,1,15,1,3,1,7,1,3,1,31\cdots$. Sa complexité est $\Theta (n\log \log n)$ (ç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 Cassaigne et Nicolas (2010)). On sait :

Proposition —  Soit $x$ un mot infini binaire morphique. La fonction de complexité de $x$ vérifie l'une des propriétés suivantes :

1. il existe un entier $m\geq 1$ tel que $c_{x}(n)=\Theta (n{\sqrt[{m}]{n}})$,
2. $c_{x}(n)=O(n\log n)$.

On sait que pour tout entier $m\geq 1$, il existe effectivement un mot infini binaire morphique $x$ tel que $c_{x}(n)=\Theta (n{\sqrt[{m}]{n}})$.

Exemple

Soit $A=\{a,b_{0},b_{1},\ldots ,b_{m}\}$ un alphabet à $m+2$ lettres et considérons le morphisme $f:A^{*}\to A^{*}$ défini par

${\begin{array}{l}f(a)=ab_{m}\\f(b_{i})=b_{i}b_{i-1}\quad (i=1,\ldots ,m)\\f(b_{0})=b_{0}\end{array}}$

et soit $g:A^{*}\to \{0,1\}^{*}$ donné par $g(b_{i})=0$ pour $i=0,\ldots ,m-1$, $g(b_{r})=1$, et $g(a)=\varepsilon$. On voit que

$x=g(f^{\omega }(a))=g(ab_{r}f(b_{r})f^{2}(b_{r})\cdots )=10^{e_{0}}10^{e_{1}}10^{e_{2}}10^{e_{3}}\cdots )$

pour des entiers $e_{i}$, et on peut prouver que la suite de $e_{i}$ croît comme $i^{m}/m!$ d'où l'on peut déduire que $c_{x}(n)\sim n{\sqrt[{m}]{n}}$.

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 $b>1$ un entier. Pour tout nombre réel $\xi$ avec $0<\xi <1$, il existe un mot infini unique

$x=a_{0}a_{1}a_{2}\cdots a_{n}\cdots$

à éléments dans l'ensemble $\{0,1,\ldots ,b-1\}$ tel que

$\xi =\sum _{n=0}^{\infty }{\frac {a_{n}}{b^{n+1}}}=0,a_{0}a_{1}a_{2}\cdots a_{n}\cdots$

avec la condition supplémentaire que $x$ ne se termine pas par une infinité de $b-1$. Par exemple, en base 10, on a

$3/7=0,(428571)^{\omega }$.

Réciproquement, un développement en base $b$ 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

$c(\xi ,b,n)$

le nombre de facteurs de longueur $n$ du mot infini $x$ qui est le développement de $\xi$ en base $b$, en d'autre termes $c(\xi ,b,n)=c_{x}(n)$. On dira pour faire vite que c'est la complexité de $\xi$, au lieu de dire la complexité du développement de $\xi$. On a alors le théorème suivant

Théorème (Adamczewski, Bugeaud, Luca) —  Si $\xi$ est un nombre irrationnel algébrique, alors

$\lim _{n\to \infty }{\frac {c(\xi ,b,n)}{n}}=\infty$.

La conclusion du théorème dit que la fonction de complexité de $\xi$ croît plus vite que linéairement. La conséquence immédiate de ce théorème est que si $c(\xi ,b,n)=O(n)$, et si $\xi$ est irrationnel, alors $\xi$ 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 6 facteurs de longueur 6 du mot de Fibonacci $010010100100101001010\cdots$ sont $001010,010010,010100,100100,100101,101001$. Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les quatre mots contenant deux occurrences de $1$, et les deux qui en contiennent trois. La complexité abélienne prend donc la valeur 2.

Mots de complexité abélienne maximale

On note $\alpha _{x}$ la fonction complexité abélienne d'un mot $x$.

Propriété.- La complexité abélienne d'un mot infini $x$ sur $k$ lettres vérifie $\alpha _{x}(n)\leq {\binom {n+k-1}{k-1}}$ pour tout $n\geq 1$.

Cette borne est atteinte par la suite de Champernowne par exemple.

Mot de Thue-Morse

Le mot de Thue-Morse $t$ a la fonction de complexité suivante :

$\alpha _{t}(n)={\begin{cases}2&n{\text{ impair }}\\2&n>0{\text{ pair. }}\end{cases}}$

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 $n+1$ facteurs de longueur $n$, pour tout entier naturel $n$. 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 $x$ est constante et égale à $2$. Réciproquement, un mot apériodique qui a complexité abélienne constante égale à $2$ 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 $x$ est, pour tout entier $n$, le nombre de classes, pour cette relation d'équivalence, de l'ensemble des facteurs de longueur $n$ apparaissant dans $x$. La complexité $k$-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

${\binom {u}{x}}={\binom {v}{x}}$

pour tout mot $x$ de longueur au plus $k$. Dans cette définition,

${\binom {u}{x}}$

est le nombre d'occurrences du mot x comme sous-mot de $u$. Les coefficients binomiaux de mots ont des propriétés proches de celles des nombres. Ainsi, on a par exemple :

${\binom {ps}{z}}=\sum _{xy=z}{\binom {p}{x}}{\binom {s}{y}}$

Exemples

Les quatre mots $ababbba,abbabab,baabbab$ et $babaabb$ sont 2-binomialement équivalents. Si $w$ est l'un de ces quatre mots, on a en effet les coefficients suivants :

${\binom {w}{a}}=3,{\binom {w}{b}}=4$ et ${\binom {w}{aa}}=3,{\binom {w}{ab}}=7,{\binom {w}{ba}}=5,{\binom {w}{ab}}=6$.

Ces mots ne sont pas 2-binomialement équivalents. Par exemple, on a

${\binom {ababbba}{aab}}=3\quad$ et $\quad {\binom {abbabab}{aab}}=4$.

En effet, dans ce deuxième mot, le sous-mot $aab$ apparaît en 4 positions :

${\underline {a}}bb{\underline {a}}{\underline {b}}ab,{\underline {a}}bb{\underline {a}}a{\underline {b}},{\underline {a}}bba{\underline {a}}{\underline {b}},abb{\underline {ab}}a{\underline {b}}$.

Pour $k=1$, l'équivalence binomiale coïncide avec l'équivalence commutative.

On note $u\sim _{k}v$ le fait que $u$ et $v$ sont $k$-binomialement équivalents. La relation est compatible avec la concaténation :

$u\sim _{k}v\$ implique $\ pus\sim _{k}pvs$ pour tous mots $p,s$.

Complexité binomiale du mot de Thue-Morse

On note $c_{x}(n)$ la complexité d'un mot $x$, c'est-à-dire le nombre de facteur de longueur $n$ apparaissant dans $x$, et on note $b_{x,k}(n)$ ou plus simplement $b_{x}(n)$la complexité $k$-binomiale de $x$, c'est-à-dire le nombre classes de sous-mots $k$-équivalents de longueur $n$ du mot $x$. Pour le mot de Thue-Morse, on a le résultat suivant :

Théorème — Soit $k$ un entier positif. La complexité $k$-binomiale du mot de Thue-Morse a la forme suivante : pour $n<2^{k}$, on a

$b_{t}(n)=c_{t}(n)$,

et pour $n\geq 2^{k}$, on a :

$b_{t}(n)={\begin{cases}3\cdot 2^{k}-3&{\text{si }}n\equiv 0{\bmod {2}}^{k}\\3\cdot 2^{k}-4&{\text{sinon.}}\end{cases}}$

Ainsi, pour $n\geq 2^{k}$, la complexité $k$-binomiale du mot de Thue-Morse ne prend que 2 valeurs ; de plus, la deuxième valeur est égale à $c_{t}(2^{k}-1)$.

Complexité binomiale des mots sturmiens

La complexité $k$-binomiale d'un mot sturmien est égale à sa complexité en facteur. Plus précisément, on

Théorème — Soit $k\geq 2$ un entier. La complexité $k$-binomiale $b_{x}(n)$ d'un mot sturmien $x$ est égale à $n+1$ pour tout entier $n$.

Pour $k=1$, 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 $k$-binomialement équivalents.

Complexité cyclique

Définition

La complexité cyclique d’un mot infini $x$ est la fonction $c_{x}(n)$ qui compte le nombre de classes de conjugaison (ou mots circulaires, ou colliers) de facteurs de longueur $n$ dans le mot $x$ : pour être tout à fait précis : $c_{x}(n)$ est le nombre de classes de conjugaison que rencontre l’ensemble des facteurs de longueur $n$.

Exemple. Les cinq facteurs de longueur 4 du mot de Fibonacci infini $010010100100101001010\cdots$ sont $0100,1001,0010,0101,1010$. Ces facteurs se regroupent, par permutation circulaire, en deux classes : les trois mots forment contenant une seule occurrence de $1$, et les deux qui en contiennent deux. La complexité cyclique prend donc la valeur 2.

On a $a_{x}(n)\leq c_{x}(n)\leq p_{x}(n)$, où $a_{x}$ est la complexité abélienne et $p_{x}(n)$ 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 $x$ et $y$ 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 $n$ d’un mot sont conjugués, ce mot est périodique. En particulier, si $x$ est sturmien, alors $\liminf _{n\to \infty }c_{x}(n)=2$, mais ceci ne caractérise pas les mots sturmiens.

Mot de Thue-Morse

Pour le mot de Thue-Morse $t$ la fonction de complexité cyclique n'est pas bornée : on a $\liminf _{n\to \infty }c_{t}(n)=+\infty$,

Complexité en palindromes

Définition

La fonction de complexité en palindromes ou complexité palindromique d'un mot fini ou infini $x$ est la fonction

$n\mapsto p_{x}(n)$

qui, pour chaque entier $n$, donne le nombre $p_{x}(n)$ de facteurs (ou blocs) distincts de longueur $n$ dans ce mot qui sont des palindromes. Bien entendu, on a toujours $p_{x}(n)\leq c_{x}(n)$.

Exemple Le mot $x=01101001$, préfixe du mot de Prouhet-Thue-Morse a les facteurs 9 palindromes

$\varepsilon ,0,1,00,11,010,101,0110,1001$,

et $p_{x}(0)=1$, et $p_{x}(1)=p_{x}(2)=p_{x}(3)=p_{x}(4)=2$.

Exemple Le mot de Fibonacci infini $f=0100101001001\cdots$ a les facteurs palindromes

$\varepsilon ,0,1,00,010,101,1001,\cdots$,

et on peut démontrer que

$p_{f}(n)={\begin{cases}1&{\text{si }}n{\text{ est pair;}}\\2&{\text{sinon.}}\end{cases}}$

Cette propriété est caractéristique des mots sturmiens.

Comparaison des deux mesures de complexité

Soit $x$ un mot infini, et soit $p_{x}(n)$ sa complexité en palindromes et $c_{x}(n)$ sa complexité en facteurs. Bien entendu, on a toujours $p_{x}(n)\leq c_{x}(n)$. Il y a une borne bien meilleure :

$p_{x}(n)\leq {\frac {16}{n}}c_{x}{\bigl (}n+{\bigl \lfloor }{\frac {n}{4}}{\bigr \rfloor }{\bigr )}$

Cette propriété peut être raffinée dans le cas de mots infinis dont l'ensemble des facteurs est fermé par image miroir, c'est-à-dire tel que pour tout facteur $u$, l'image miroir $u^{\sim }$ est encore facteur.

Théorème (Baláži, Masáková, Pelantová) — Soit $x$ un mot infini dont l'ensemble des facteurs est fermé par miroir. Pour tout $n$,

$p(n)+p(n+1)\leq c(n+1)-c(n)+2$,

où $c(n$) (resp. $p(n)$) est le nombre de facteurs (resp. le nombre de facteurs palindromes) de longueur $n$ de $x$.

Exemple. Pour tout mot sturmien, on a $c(n)=n+1$. Ainsi, le membre droit de l'équation s'évalue en $c(n+1)-c(n)+2=3$. Il en résulte que $p(n)+p(n+1)\leq 3$. On verra que dans ce cas, on peut remplacer l'inégalité par une égalité. On a donc $p(n)+p(n+1)=3$, donc le nombre de palindromes est alternativement 1 et 2, comme déjà dit plus haut.

Le nombre moyen de facteurs palindromes distincts dans un mot aléatoire de longueur $n$ est $\theta ({\sqrt {n}})$.

Mots riches en palindromes

Soit $w$ un mot fini, et soit $\operatorname {Pal} (w)$ l'ensemble des facteurs de $w$ qui sont des palindromes, et soit ${\mathcal {P}}(w)$ le nombre d'éléments de $\operatorname {Pal} (w)$. On sait que pour tout mot fini $w$, on a

${\mathcal {P}}(w)\leq |w|+1$.

Un mot $w$ est riche en palindromes si l'inégalité est une égalité, donc si

${\mathcal {P}}(w)=|w|+1$.

De même, un mot infini est riche en palindromes si tous ses facteurs sont riches en palindromes. Les mots sturmiens, épisturmiens, et plus généralement les mots infinis qui codent des échanges d'intervalles symétriques sont riches. Le mot de Thue-Morse n'est pas riche. Le préfixe $01101001$ de longueur 8 du mot de Thue-Morse et riche puisqu'il a 9 facteurs palindromes. Un examen exhaustif montre que tous les mots binaires de longueur au plus 8 sont riches. Des définitions équivalentes ont été trouvées pour les mots riches :

Théorème — Soit $x$ un mot infini. Les conditions suivantes sont équivalentes :

• $x$ est riche en palindromes ;
• dans tout facteur $w$ de $x$, le plus long suffixe palindrome de $w$ est unioccurent dans $w$ ;
• chaque préfixe de $x$ a un suffixe palindrome unioccurrent ;
• tout mot de retour complet d'un facteur palindrome est lui-même un palindrome ;
• $p(n)+p(n+1)=c(n+1)-c(n)+2$ pour tout $n$.

Exemple. Prenons le mot infini de Fibonacci

$f=010010100100101001010\cdots$

qui est sturmien donc riche. Prenons par exemple le facteur $w=100100101001$. Les suffixes palindromes de ce mot sont $1,1001$ et $100101001$. Les deux premiers ont plusieurs occurrences dans w, le troisième, le plus long, n'a qu'une seule occurrence. Le préfixe $01001010$ a trois suffixes palindromes non vides, à savoir $0$, $010$, et $01010$. Le dernier est le seul qui est unirécurrent. Pour le facteur 1001, les deux mots de retour complets sont $1001001$ et $100101001$. Ils sont tous deux palindromes. Enfin, comme $c(n)=n+1$, on a $c(n+1)-c(n)+2=3$ pour tout $n$, et d'autre part le mot de Fibonacci a deux facteurs palindromes de longueur paire et un seul de longueur impaire pour toute longueur, donc $p(n)+p(n+1)=3$.

Théorème (Rukavicka) — Soit $x$ un mot infini riche en palindromes, sur un alphabet à $q>1$ lettres. Le nombre $p_{x}(n)$ de facteurs palindromes de longueur $n$ dans $x$ est majoré par :

$p_{x}(n)\leq (q+1)n(4q^{10}n)^{\log _{2}n}$.

Les mêmes arguments donnent aussi une majoration pour le nombre de facteurs d'un mot riche en palindromes :

Théorème (Rukavicka) — Soit $x$ un mot infini riche en palindromes, sur un alphabet à $q>1$ lettres. Le nombre $c_{x}(n)$ de facteurs de longueur $n$ dans $x$ est majoré par :

$c_{x}(n)\leq (q+1)^{2}n^{4}(4q^{10}n)^{2\log _{2}n}$.

On peut se demander comment sont les mots infinis qui ne sont pas riches. On appelle défaut ou défaut palindromique d'un mot $w$ le nombre ${\mathcal {D}}(w)$ défini par

${\mathcal {D}}(w)=1+|w|-{\mathcal {P}}(w)$

Ce nombre est toujours positif ou nul. Pour un mot infini $x$, on pose

${\mathcal {D}}(x)=\max\{{\mathcal {D}}(w)\mid w{\text{ facteur de }}x\}$.

Ce défaut est nul si le mot est riche. Il est utile, pour simplifier l'énoncé qui suit, de poser

$T_{w}(n)=c_{w}(n+1)-c_{w}(n)+2-p_{w}(n)-p_{w}(n+1)$.

Pour tout mot fini $w$ de longueur $k$, on a

$2{\mathcal {D}}(w)=\sum _{n=0}^{k}T_{w}(n)$.

La conjecture selon laquelle l'équation

$2{\mathcal {D}}(x)=\sum _{n=0}^{\infty }T_{x}(n)$

est vraie pour tout mot infini $x$ a été prouvée. Le théorème s'énonce comme suit :

Théorème — Soit $x$ un mot infini dont l'ensemble des facteurs est fermé par miroir. Alors

$2{\mathcal {D}}(x)=\sum _{n=0}^{\infty }T_{x}(n)<\infty$.

Cela signifie aussi que si l'une des deux valeurs ${\mathcal {D}}(x)$ ou $\sum _{n=0}^{\infty }T_{x}(n)$ est infinie, l'autre l'est également.

Mots à défaut positif

Le défaut d'un mot peut être nul, positif non nul, ou infini si le mot lui-même est infini. Lorsque le mot a une forme particulière où construit au moyen d'un mécanisme bien connu, on peut donner des indications sur sa complexité en palindromes. Ceci est le cas de mots purement morphiques engendrés par des morphismes primitifs : un morphisme $f$ est primitif si sa matrice d'incidence $M(f)$ (dont le coefficient d'indice $a,b$ donne le nombre le nombre d'occurrences de la lettre $a$ dans le mot $f(b)$) est primitive. Le morphisme est primitif si et seulement s’il existe un entier $k$ tel que toute lettre a une occurrence dans le mot $f^{k}(b)$, pour toute lettre $b$ de l’alphabet. On considère ici les mots purement morphiques qui sont point fixes d'un morphisme primitif.

Pour le mot de Fibonacci par exemple, on a ${\mathcal {D}}(u)=0$, et pour le mot de Thue-Morse, ${\mathcal {D}}(u)=+\infty$. Tous les deux sont des mots purement morphiques points fixes d'un morphisme primitif.

Il existe de mots points fixes de morphismes primitifs de défaut $k$ pour tout entier naturel $k$. mais ce sont des mots périodiques. Voici un exemple : soit $k\geq 2$ un entier naturel, et soit

$z_{k}=01^{k}01^{k-1}001^{k-1}01^{k}0$.

Par exemple $z_{2}=0110100100110$. On peut montrer que le mot infini périodique $z_{k}^{\omega }$ a un défaut palindromique égal à $k$. Ce mot est point fixe du morphisme $0\mapsto z_{k},1\mapsto z_{k}$. Les auteurs de l’article ont formulé la conjecture suivante :

Conjecture (Zero Defect Conjecture ou conjecture du zéro défaut) — Un mot infini qui est point fixe d’un morphisme primitif a un défaut nul ou infini, ou alors il est périodique.

La conjecture est donc que si un mot a un défaut strictement positif et fini, il est périodique. La conjecture est vérifiée dans le cas d’un alphabet binaire, mais elle est fausse pour des alphabets plus grands. Un contre-exemple est le mot infini engendré par le morphisme

$a\mapsto aabcacba,b\mapsto aa,c\mapsto a$

donné par Michelangelo Bucci et Élise Vaslet. D'autres résultats ont été donnés par Kristina Ago, Bojan Bašić, Stefan Hačko et Danijela Mitrović.

Complexité de Lie

La complexité de Lie d'un mot infini à droite $w$ sur un alphabet $A$ est la fonction $L_{w}$ dont la valeur $L_{w}(n)$, pour un entier naturel $n$, est le nombre de classes de conjugaison (pour le décalage cyclique) de facteurs de longueur $n$ de $w$ avec la propriété que chaque élément de la classe de conjugaison apparaît dans $w$.

Exemples

1.- Soit $\mathbf {t}$ le mot de Thue-Morse, point fixe du morphisme qui envoie 0 sur 01 et 1 sur 10. On a :

$L_{\mathbf {t} }(n)={\begin{cases}1&{\text{si }}n=0{\text{ ou }}n=2^{k}{\text{ et }}k\geq 3\\2&{\text{si }}n=1,4{\text{ ou }}n=3\cdot 2^{k}{\text{pour }}k\geq 0\\3&{\text{si }}n=2\\0&{\text{sinon }}.\end{cases}}$

Ceci est en accord avec le fait que les seuls carrés dans le mot de Thue-Morse ont longueur $2^{k}$ ou $3\cdot 2^{k}$ .

Soit $\mathbf {f}$ le mot de Fibonacci, point fixe du morphisme qui envoie 0 sur 01 et 1 sur 0. Les nombres de Fibonacci sont définies par  $F_{0}=0,F_{1}=1$ et $F_{n}=F_{n-1}+F_{n-2}$. Alors

$L_{\mathbf {f} }(n)={\begin{cases}1&{\text{si }}n=0{\text{ ou }}n=F_{k}{\text{ ou }}n=2F_{k-1}{\text{ pour }}k\geq 4\\2&{\text{si }}n=1,2\\0&{\text{sinon }}.\end{cases}}$

Propriétés

On note $p_{w}(n)$ le nombre de facteurs de longueur $n$ du mot infini $w$. L'observation principale est la formule suivante :

Théorème — On a $L_{w}(n)\leq p_{w}(n)-p_{w}(n-1)+1$.

Pour un mot sturmien qui a la propriété que $p_{w}(n)=n+1$, le membre droit de l'inégalité est 2.

Il résulte de la formule que la fonction de complexité de Lie est uniformément bornée pour les mots dont la complexité en facteurs est linéaire. Il en résulte aussi comme corollaire que les mots infinis dont la complexité en facteurs est linéaire ont au plus un nombre fini de facteurs primitifs $y$ avec la propriété que $y^{n}$ est à nouveau un facteur pour tout $n$.

On peut montrer que la fonction de complexité de Lie d'une suite $k$-automatique est également $k$-automatique.

Les démonstrations de Bell et Shallit sont algébriques, Alessandro De Luca et Gabriele Fici donnent des preuves combinatoires.

Complexité arithmétique

La complexité arithmétique d'un mot infini est la fonction qui compte le nombre de mots de longueur donnée composés de lettres apparaissant à des positions en progression arithmétiques (et non seulement consécutives).

C'est une autre mesure de la complexité combinatoire des mots infinis qui est une extension de la complexité en facteurs. Les résultats sont moins spectaculaires que ceux concernant la complexité en facteurs.

Définition et exemples

Formellement, étant donné un mot infini

$x=a_{0}a_{1}\cdots a_{n}\cdots$,

où les $a_{i}$ sont des lettres, on appelle clôture arithmétique de $x$ l'ensemble

$A(x)=\{a_{i}a_{i+d}a_{i+2d}\cdots a_{i+kd}\mid d\geq 1,k\geq 0\}$.

La complexité arithmétique de $x$ est la fonction $a_{x}$ qui à $n$ associe le nombre $a_{x}(n)$ de mots de longueur $n$ dans $A(x)$.

Exemples

• Le mot caractéristique des carrés : $x=1100100001000000100\cdots$. Par exemple $111$ figure dans sa clôture arithmétique, parce qu'il y a un 1 en positions 1, 25 et 49.
• Le mot de Prouhet-Thue-Morse : $t=011010011001011010010110011010011001011001101001\cdots$. On peut montrer, directement ou comme corollaire du résultat plus général donné plus loin, que $a_{t}(n)=2^{n}$, c'est-à-dire que tout mot est dans la clôture arithmétique.
• Le mot de Fibonacci $f=0100101001001010010100100101001001\cdots$.

Il a été démontré que $a_{f}(n)=\theta (n^{3})$. Les premières valeurs sont données dans la table suivante : ${\begin{array}{|c|cccccccc|}\hline n&1&2&3&4&5&6&7&8\\\hline a_{f}(n)&2&4&8&16&30&52&83&128\\\hline \end{array}}$

Propriétés

Les résultats généraux sont plus rares que pour la complexité en facteurs.

Mots sturmiens. Pour les mots sturmiens, les résultats sont les suivants :

• La complexité arithmétique d'un mot sturmien est majorée par $O(n^{3})$.
• Pour tout mot sturmien de pente entre $1/3$ et $2/3$, la complexité est $\theta (n^{3})$.

Pour les mots sturmiens de pente comprise entre $2/5$ et $3/5$, il existe une formule explicite, un peu compliquée à expliquer.

Mots symétriques. Une autre catégorie de mots pour lesquels on connaît la complexité arithmétique est celle des mots purement morphiques engendrés par des morphismes symétriques. Un morphisme $f:A^{*}\to A^{*}$ est symétrique s'il existe une permutation circulaire $\sigma$ sur $A$ qui commute avec $f$, donc telle que $f(\sigma (a))=\sigma (f(a))$ pour toute lettre $a$. L'exemple typique est le morphisme de Thue-Morse, ou le morphisme ternaire $0\mapsto 012,\quad 1\mapsto 120,\quad 2\mapsto 201$ associé à la permutation $(012)$. Les mots de engendrés par des morphismes symétriques sont eux-mêmes appelés des mots symétriques. On a la propriété suivante :

Propriété — Soit $x$ un mot symétrique sur un alphabet à $q$ lettres. Alors $a_{x}(1)=q$ et

$a_{x}(n)=k^{n-2}q^{2}\quad (n\geq 2)$,

où $k$ est un diviseur de $q$.

Voici deux cas particuliers :

• Si $x$ est un mot symétrique périodique, alors $a_{x}(n)=q^{2}$ pour tout $n\geq 2$.
• Si $x$ est symétrique non périodique et si $q$ est un nombre premier, alors $a_{x}(n)=q^{n}$ pour tout $n$. C'est le cas pour le mot de Prouhet-Thue-Morse.

Suites de complexité arithmétique linéaire

Quelles sont les suites de faible complexité arithmétique ? Anna Frid a caractérisé les mots infinis de complexité arithmétique linéaire. Pour formuler cette caractérisation, il faut donner quelques définitions. D'abord une notation. Pour un mot infini

$x=x_{1}x_{2}\cdots x_{n}\cdots$

où les $x_{i}$ sont des lettres, on note $x(k,d)$ le mot commençant en $x_{k}$ et formé des lettres de $x$ prises à intervalle $d>0$, formellement

$x(k,d)=x_{k}x_{k+d}x_{k+2d}\cdots x_{k+nd}\cdots$

Par exemple, pour le mot de Prouhet-Thue-Morse

$t=0110100110010110\cdots$

on a $t(1,2)=t(1,4)=t(4,4)=t$. Un mot $x$ est dit canoniquement $p$-régulier si $x(k,p^{m})$ est périodique pour tout $m>0$ et tout $k$ avec $1\leq k<p^{m}$. Par exemple, la suite de Prouhet-Thue-Morse n'est pas canoniquement 2-régulière. En revanche, la suite de pliage de papier

$z=00\ 10\ 01\ 10\ 00\ 11\ 01\ 10\cdots$

est canoniquement 2-régulière. On peut s'en convaincre pour les petites valeurs de $m$. On a par exemple $z(1,2)=010101\cdots =z(2,4)$ et $z(1,4)=000\cdots ,z(3,4)=111\cdots$. Il reste une définition. Un mot $y$ est dans l'orbite d'un mot $x$ si l'ensemble des facteurs de $y$ est contenu dans l'ensemble des facteurs de $x$. L'énoncé est le suivant

Propriété — Un mot infini uniformément récurrent et non périodique est de complexité arithmétique linéaire si et seulement s'il appartient à l'orbite d'un mot $x$ qui est $p$-régulier canonique pour un nombre premier $p$, et vérifie $x(p^{a},p^{a})=x(p^{b},p^{b})$ pour deux entiers $a\neq b$.

Exemple. Nous avons déjà dit que le mot des pliages est canoniquement 2-régulier. On a de plus $z(2,2)=z(4,4)=z$, donc la deuxième condition est remplie également.

Dans cet article, A. Frid donne une autre caractérisation des suites de complexité linéaire par des suites dites de Toeplitz d'un type spécifique.

Suites de complexité arithmétique maximale

Konieczny et Müllner classifient les suites automatiques $x$ sur un alphabet fini $A$ avec la propriété que chaque mot sur $A$ apparaît dans $x$ le long d'une progression arithmétique. Plus généralement, ils obtiennent une formule asymptotique pour la complexité arithmétique (et même polynomiale) des sous-mots d'une séquence automatique donnée.

Complexité non-répétitive

La complexité non-répétitive et la complexité non-répétitive initiale sont deux mesures de complexité introduites par T. K. Subrahmonian Moothathu, étudiée par Jeremy Nicholson et Narad Rampersad, et par Medková, Pelantová et Vandomme, et considérées par Yann Bugeaud et Dong Han Kim sous une forme un peu différente. Ces mesures sont liées à l'indice de récurrence et de récurrence initiale dans un mot infini.

Définitions

Les notations varient avec les auteurs. Soit $x$ un mot infini et $m$ un entier.

La complexité non-répétitive initiale est définie par Moothathu comme suit :

$ic(m,x)$ est la longueur du plus court préfixe de $x$ qui ne contient pas le début d'une deuxième occurrence du préfixe de longueur $m$.

La complexité non-répétitive est par définition :

$nc(m,x)$ est la longueur du plus court facteur de $x$ qui ne contient pas le début d'une deuxième occurrence du préfixe de longueur $m$.

L'indice de récurrence est :

$R(m,x)$ est la longueur du plus court facteur de $x$ qui contient tous les facteurs de longueur $m$.

L'indice de récurrence initiale est :

$R'(m,x)$ est la longueur du plus court préfixe de $x$ qui contient tous les facteurs de longueur $m$.

Ces deux dernières mesures sont les contraposées logiques des indices de non-répétivité.

Bugeaud et Kim définissent une fonction notée $r(m,x)$ par :

$r(m,x)$ est la longueur du plus court préfixe de $x$ qui contient deux occurrences (éventuellement chevauchantes) du préfixe de longueur $m$.

Le lien entre ces ceux définitions est donné par la relation :

$ic(m,x)+m=r(m,x)$.

Les relations entre les valeurs de ces divers indices sont les suivantes :

$ic(m,x)\leq nc(m,x)\leq c(m,x)\leq R(m,x)+1-m$.

Exemples

Complexite pour Fibonacci

m	ic	r
4	5	9
5	5	10
6	5	11
7	8	15

Pour le mot de Fibonacci $f=abaababaabaab\cdots$, on a

$ic(m,f)=F_{k}$ pour $F_{k}-2<m\leq F_{k+1}-2$ et $k\geq 3$.

Ici, $F_{k}$ est le $k$-ième nombre de Fibonacci. Comme on voit sur la table ci-dessus, on a en effet $5=ic(6,f)=F_{4}$ et $8=ic(7,f)=F_{5}$. La fonction est donc constante entre deux nombres de Fibonacci consécutifs (ajustés).

Pour le mot de Thue-Morse $t=0110100110010110\cdots$, une formule similaire de constance est vérifiée : on a

$ic(m,t)=3\cdot 2^{k-1}$ pour $2^{k-1}<m\leq 2^{k}$.

Propriétés

Les mots ultimement périodiques sont caractérisées avec cette nouvelle mesure de complexité comme suit :

Propriété — Les conditions suivantes sont équivalentes :

• $x$ est ultimement périodique
• $ic(m,x)\leq m$ pour tout $m$ assez grand
• il existe $M$ tel que $ic(m,x)\leq M$ pour tout $m\geq 1$.

Les mots sturmiens admettent la caractérisation suivante :

Propriété — Un mot $x$ est un mot sturmien si et seulement si $ic(m,x)\leq m+1$ pour $m\geq 1$, avec égalité pour une infinité de $m$.

Une propriété de transcendance

Théorème — Soit $x=x_{1}x_{2}\cdots$ un mot infini non périodique sur un alphabet fini d'entiers. Si

$\liminf _{m\to \infty }{\frac {r(m,x)}{m}}<\infty$,

alors le nombre réel dont le développement en fraction continue est$[0;x_{1},x_{2},\ldots ]$ est transcendant.

Notes et références

Bibliographie

• (en) Jean-Paul Allouche, Michael Baake, Julien Cassaigne et David Damanik, « Palindromic complexity », Theoretical Computer Science, vol. 292, n^o 1,‎ 2003, p. 9-31 (ISSN 0304-3975, DOI 10.1016/S0304-3975(01)00212-2, lire en ligne)
• (en) Boris Adamczewski et Yves Bugeaud, « Transcendence and Diophantine approximation », dans Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, Automata and Number Theory, Cambridge University Press, coll. « Encyclopedia of mathematics and its applications » (n^o 135), 2010 (ISBN 978-0-521-51597-9), p. 410-451
• (en) Srecko Brlek et Christophe Reutenauer, « Complexity and palindromic defect of infinite words », Theoretical Computer Science, vol. 412, n^os 4-5,‎ 2011, p. 493-497 (DOI 10.1016/j.tcs.2010.11.025, lire en ligne)
• (en) Srecko Brlek, Sylvie Hamel, Maurice Nivat et Christophe Reutenauer, « On the palindromic complexity of infinite words », International Journal of Foundations of Computer Science, vol. 15, n^o 2,‎ 2004, p. 293-306 (DOI 10.1142/S012905410400242X).
• (en) Julien Cassaigne et François Nicolas, « Factor complexity », dans Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, Automata and Number Theory, Cambridge University Press, coll. « Encyclopedia of mathematics and its applications » (n^o 135), 2010 (ISBN 978-0-521-51597-9), p. 163-247
• (en) Gwenaël Richomme, Kalle Saari et Luca Q. Zamboni, « Abelian Complexity of minimal subshifts », Journal of the London Mathematical Society, vol. 83, n^o 1,‎ 2011, p. 79-95 (DOI 10.1112/jlms/jdq063).
• (en) Jason P. Bell et Jeffrey Shallit, « Lie complexity of words », Theoretical Computer Science, vol. 927,‎ août 2022, p. 98–108 (DOI 10.1016/j.tcs.2022.06.001, arXiv 2102.03821)

• Alessandro De Luca et Gabriele Fici, « On the Lie complexity of Sturmian words », Theoretical Computer Science, vol. 938,‎ 26 novembre 2022, p. 81–85 (DOI 10.1016/j.tcs.2022.10.009, arXiv 2206.00995).

Voir aussi

• Théorème de périodicité de Fine et Wilf
• Longueur palindromique d'un mot
• Suite de Piatetski-Shapiro