Complexité d'un mot

L'entropie topologique d'un mot infini ${\displaystyle x}$ est la limite

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

Cette limite existe, car on a

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

donc la fonction ${\displaystyle \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.

Le théorème suivant donne une classification des fonctions de complexités pour les mots purement morphiques.

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

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

engendre, à partir de la lettre ${\displaystyle a}$, le mot infini :

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

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

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

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

engendre, à partir de la lettre ${\displaystyle a}$, le mot infini :

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

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

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

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

engendre, à partir de la lettre ${\displaystyle a}$, le mot infini :

${\displaystyle (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 ${\displaystyle b}$ est :${\displaystyle 1,3,1,7,1,3,1,15,1,3,1,7,1,3,1,31\cdots }$. Sa complexité est ${\displaystyle \Theta (n\log \log n)}$ (ça demande un peu de calcul !).

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 :

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

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

${\displaystyle {\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 ${\displaystyle g:A^{*}\to \{0,1\}^{*}}$ donné par ${\displaystyle g(b_{i})=0}$ pour ${\displaystyle i=0,\ldots ,m-1}$, ${\displaystyle g(b_{r})=1}$, et ${\displaystyle g(a)=\varepsilon }$. On voit que

${\displaystyle 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 ${\displaystyle e_{i}}$, et on peut prouver que la suite de ${\displaystyle e_{i}}$ croît comme ${\displaystyle i^{m}/m!}$ d'où l'on peut déduire que ${\displaystyle c_{x}(n)\sim n{\sqrt[{m}]{n}}}$.

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

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

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

Le mot de Thue-Morse ${\displaystyle t}$ a la fonction de complexité suivante :

${\displaystyle \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[2]: 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.

Un mot sturmien est un mot infini binaire qui a exactement ${\displaystyle n+1}$ facteurs de longueur ${\displaystyle n}$, pour tout entier naturel ${\displaystyle 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[2] :

Propriété.- La complexité abélienne d'un mot sturmien ${\displaystyle x}$ est constante et égale à ${\displaystyle 2}$. Réciproquement, un mot apériodique qui a complexité abélienne constante égale à ${\displaystyle 2}$ est sturmien.

Formellement, deux mots u et v sont k-binomialement équivalents si

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

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

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

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

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

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

${\displaystyle {\binom {w}{a}}=3,{\binom {w}{b}}=4}$ et ${\displaystyle {\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

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

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

${\displaystyle {\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 ${\displaystyle k=1}$, l'équivalence binomiale coïncide avec l'équivalence commutative.

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

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

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

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

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

Pour ${\displaystyle 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 ${\displaystyle k}$-binomialement équivalents[4].

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

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

On a ${\displaystyle a_{x}(n)\leq c_{x}(n)\leq p_{x}(n)}$, où ${\displaystyle a_{x}}$ est la complexité abélienne et ${\displaystyle 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.

Propriété : Soient ${\displaystyle x}$ et ${\displaystyle 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 ${\displaystyle n}$ d’un mot sont conjugués, ce mot est périodique. En particulier, si ${\displaystyle x}$ est sturmien, alors ${\displaystyle \liminf _{n\to \infty }c_{x}(n)=2}$, mais ceci ne caractérise pas les mots sturmiens.

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

La fonction de complexité en palindromes ou complexité palindromique[9] d'un mot fini ou infini ${\displaystyle x}$ est la fonction

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

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

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

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

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

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

${\displaystyle \varepsilon ,0,1,00,010,101,1001,\cdots }$,

et on peut démontrer que

${\displaystyle 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.

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

${\displaystyle 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 ${\displaystyle u}$, l'image miroir ${\displaystyle u^{\sim }}$ est encore facteur.

Exemple. Pour tout mot sturmien, on a ${\displaystyle c(n)=n+1}$. Ainsi, le membre droit de l'équation s'évalue en ${\displaystyle c(n+1)-c(n)+2=3}$. Il en résulte que ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ est ${\displaystyle \theta ({\sqrt {n}})}$[13].

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

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

Un mot ${\displaystyle w}$ est riche en palindromes[15] si l'inégalité est une égalité, donc si

${\displaystyle {\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 ${\displaystyle 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 :

Exemple. Prenons le mot infini de Fibonacci

${\displaystyle f=010010100100101001010\cdots }$

qui est sturmien donc riche. Prenons par exemple le facteur ${\displaystyle w=100100101001}$. Les suffixes palindromes de ce mot sont ${\displaystyle 1,1001}$ et ${\displaystyle 100101001}$. Les deux premiers ont plusieurs occurrences dans w, le troisième, le plus long, n'a qu'une seule occurrence. Le préfixe ${\displaystyle 01001010}$ a trois suffixes palindromes non vides, à savoir ${\displaystyle 0}$, ${\displaystyle 010}$, et ${\displaystyle 01010}$. Le dernier est le seul qui est unirécurrent. Pour le facteur 1001, les deux mots de retour complets sont ${\displaystyle 1001001}$ et ${\displaystyle 100101001}$. Ils sont tous deux palindromes. Enfin, comme ${\displaystyle c(n)=n+1}$, on a ${\displaystyle c(n+1)-c(n)+2=3}$ pour tout ${\displaystyle 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 ${\displaystyle p(n)+p(n+1)=3}$.

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

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

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

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

${\displaystyle {\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

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

Pour tout mot fini ${\displaystyle w}$ de longueur ${\displaystyle k}$, on a

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

La conjecture[20] selon laquelle l'équation

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

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

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

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 ${\displaystyle f}$ est primitif si sa matrice d'incidence ${\displaystyle M(f)}$ (dont le coefficient d'indice ${\displaystyle a,b}$ donne le nombre le nombre d'occurrences de la lettre ${\displaystyle a}$ dans le mot ${\displaystyle f(b)}$) est primitive. Le morphisme est primitif si et seulement s’il existe un entier ${\displaystyle k}$ tel que toute lettre a une occurrence dans le mot ${\displaystyle f^{k}(b)}$, pour toute lettre ${\displaystyle 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 ${\displaystyle {\mathcal {D}}(u)=0}$, et pour le mot de Thue-Morse, ${\displaystyle {\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 ${\displaystyle k}$ pour tout entier naturel ${\displaystyle k}$. mais ce sont des mots périodiques. Voici un exemple[22] : soit ${\displaystyle k\geq 2}$ un entier naturel, et soit

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

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

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[23], mais elle est fausse pour des alphabets plus grands. Un contre-exemple est le mot infini engendré par le morphisme

${\displaystyle a\mapsto aabcacba,b\mapsto aa,c\mapsto a}$

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

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

${\displaystyle 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 ${\displaystyle 2^{k}}$ ou ${\displaystyle 3\cdot 2^{k}}$ .

Soit ${\displaystyle \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  ${\displaystyle F_{0}=0,F_{1}=1}$ et ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$. Alors

${\displaystyle 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}}}$

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

Pour un mot sturmien qui a la propriété que ${\displaystyle 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 ${\displaystyle y}$ avec la propriété que ${\displaystyle y^{n}}$ est à nouveau un facteur pour tout ${\displaystyle n}$.

On peut montrer que la fonction de complexité de Lie d'une suite ${\displaystyle k}$-automatique est également ${\displaystyle k}$-automatique[25].

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

Formellement, étant donné un mot infini

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

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

${\displaystyle 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 ${\displaystyle x}$ est la fonction ${\displaystyle a_{x}}$ qui à ${\displaystyle n}$ associe le nombre ${\displaystyle a_{x}(n)}$ de mots de longueur ${\displaystyle n}$ dans ${\displaystyle A(x)}$.

Exemples

• Le mot caractéristique des carrés : ${\displaystyle x=1100100001000000100\cdots }$. Par exemple ${\displaystyle 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 : ${\displaystyle t=011010011001011010010110011010011001011001101001\cdots }$. On peut montrer, directement ou comme corollaire du résultat plus général donné plus loin, que ${\displaystyle a_{t}(n)=2^{n}}$, c'est-à-dire que tout mot est dans la clôture arithmétique.
• Le mot de Fibonacci ${\displaystyle f=0100101001001010010100100101001001\cdots }$.

Il a été démontré[27] que ${\displaystyle a_{f}(n)=\theta (n^{3})}$. Les premières valeurs sont données dans la table suivante[27] : ${\displaystyle {\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}}}$

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[27] :

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

Pour les mots sturmiens de pente comprise entre ${\displaystyle 2/5}$ et ${\displaystyle 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 ${\displaystyle f:A^{*}\to A^{*}}$ est symétrique s'il existe une permutation circulaire ${\displaystyle \sigma }$ sur ${\displaystyle A}$ qui commute avec ${\displaystyle f}$, donc telle que ${\displaystyle f(\sigma (a))=\sigma (f(a))}$ pour toute lettre ${\displaystyle a}$. L'exemple typique est le morphisme de Thue-Morse, ou le morphisme ternaire ${\displaystyle 0\mapsto 012,\quad 1\mapsto 120,\quad 2\mapsto 201}$ associé à la permutation ${\displaystyle (012)}$. Les mots de engendrés par des morphismes symétriques sont eux-mêmes appelés des mots symétriques[28]. On a la propriété suivante :

Voici deux cas particuliers :

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

Quelles sont les suites de faible complexité arithmétique ? Anna Frid[29] 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

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

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

${\displaystyle 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

${\displaystyle t=0110100110010110\cdots }$

on a ${\displaystyle t(1,2)=t(1,4)=t(4,4)=t}$. Un mot ${\displaystyle x}$ est dit canoniquement ${\displaystyle p}$-régulier si ${\displaystyle x(k,p^{m})}$ est périodique pour tout ${\displaystyle m>0}$ et tout ${\displaystyle k}$ avec ${\displaystyle 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

${\displaystyle 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 ${\displaystyle m}$. On a par exemple ${\displaystyle z(1,2)=010101\cdots =z(2,4)}$ et ${\displaystyle z(1,4)=000\cdots ,z(3,4)=111\cdots }$. Il reste une définition. Un mot ${\displaystyle y}$ est dans l'orbite d'un mot ${\displaystyle x}$ si l'ensemble des facteurs de ${\displaystyle y}$ est contenu dans l'ensemble des facteurs de ${\displaystyle x}$[31]. L'énoncé est le suivant

Exemple. Nous avons déjà dit que le mot des pliages est canoniquement 2-régulier. On a de plus ${\displaystyle 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.

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

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

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

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

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

L'indice de récurrence est :

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

L'indice de récurrence initiale est :

${\displaystyle R'(m,x)}$ est la longueur du plus court préfixe de ${\displaystyle x}$ qui contient tous les facteurs de longueur ${\displaystyle 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 ${\displaystyle r(m,x)}$ par :

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

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

${\displaystyle ic(m,x)+m=r(m,x)}$.

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

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

Complexite pour Fibonacci

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

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

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

Ici, ${\displaystyle F_{k}}$ est le ${\displaystyle k}$-ième nombre de Fibonacci[35]. Comme on voit sur la table ci-dessus, on a en effet ${\displaystyle 5=ic(6,f)=F_{4}}$ et ${\displaystyle 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 ${\displaystyle t=0110100110010110\cdots }$, une formule similaire de constance est vérifiée : on a

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

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

Les mots sturmiens admettent la caractérisation suivante :