Motif inévitable

Soit ${\displaystyle A}$ un alphabet, et soit ${\displaystyle E}$ un autre alphabet, appelé l'alphabet des symboles de motifs ou des variables. Un motif est un mot non vide sur E. Un mot ${\displaystyle v}$ sur ${\displaystyle A}$ est une instance d'un motif ${\displaystyle p}$ s'il existe un morphisme non effaçant ${\displaystyle f:E^{+}\to A^{+}}$ tel que ${\displaystyle f(p)=v}$. Un mot ${\displaystyle w}$ évite le motif ${\displaystyle p}$ si aucun facteur ${\displaystyle v}$ de ${\displaystyle w}$ n'est une instance de ${\displaystyle p}$. Une définition équivalente est la suivante : le langage du motif ${\displaystyle p}$ est l'ensemble des mots ${\displaystyle f(p)}$, où ${\displaystyle f}$ est comme ci-dessus un morphisme non effaçant; un mot ${\displaystyle w}$ évite le motif ${\displaystyle p}$ si aucun facteur de ${\displaystyle w}$ n'est dans le langage de ${\displaystyle p}$. Si ${\displaystyle w}$ n'évite pas le motif ${\displaystyle p}$, on dit que ${\displaystyle w}$ rencontre ${\displaystyle p}$ ou contient une instance du motif ${\displaystyle p}$[1].

Par exemple, le mot ${\displaystyle aabaac}$ (où ${\displaystyle a,b,c}$ sont des lettres de ${\displaystyle A}$) rencontre le motif ${\displaystyle xyx}$ (${\displaystyle x}$ et ${\displaystyle y}$ sont des lettres de ${\displaystyle E}$); en effet, le facteur ${\displaystyle aba}$ de ${\displaystyle aabaac}$ est l'image de ${\displaystyle xyx}$ par le morphisme qui envoie ${\displaystyle x}$ sur ${\displaystyle a}$ et ${\displaystyle y}$ sur ${\displaystyle b}$. Le facteur ${\displaystyle aabaa}$ aussi est dans le langage du motif ${\displaystyle xyx}$ : il est l'image de ${\displaystyle xyx}$ par le morphisme qui envoie ${\displaystyle x}$ sur ${\displaystyle aa}$ et ${\displaystyle y}$ sur ${\displaystyle b}$. Le mot ${\displaystyle abac}$ évite le motif ${\displaystyle xx}$, puisqu'il ne contient pas de carré, c'est-à-dire pas deux facteurs consécutifs égaux[2].

Un motif ${\displaystyle p}$ est évitable s'il existe une infinité de mots sur un alphabet fini qui évitent ${\displaystyle p}$. De manière équivalente, un motif est évitable s'il existe un mot infini qui évite ${\displaystyle p}$. Dans le cas contraire, le motif ${\displaystyle p}$ est dit inévitable[2]. Par exemple, le motif ${\displaystyle xyx}$ est inévitable : tout mot assez long contient deux occurrences de la même lettre séparées par au moins une lettre.

• La suite de Prouhet-Thue-Morse évite les motifs ${\displaystyle xxx}$ (elle est sans cube) et ${\displaystyle xyxyx}$ (elle est sans facteur chevauchant)[3]^,[2].
• Les motifs ${\displaystyle x}$ et ${\displaystyle xyx}$ sont inévitables sur tout alphabet[4]^,[5].
• Le motif ${\displaystyle xx}$ est évitable sur trois lettres[3]^,[4]. Les mots qui évitent ce motif sont appelés mots sans carré[6]^,[2].
• Les motifs ${\displaystyle x^{n}}$ pour ${\displaystyle n\geq 3}$ sont évitables sur deux lettres : la suite de Prouhet-Thue-Morse est un exemple pour ${\displaystyle n=3}$[3].
• Les mots de Zimin (ou sesquipuissances) sont inévitables[5].
• Tout mot de longueur au moins 29 sur 3 lettres contient une occurrence du motif ${\displaystyle xyxzxyx}$

Ce motif est le point de départ d'études ou de recherches sur des objets auto-similaires, et donné lieu à plusieurs publications scientifiques ou plus ludiques[8], notamment

• « ABACABA Amazing Pattern, Amazing Connections », Math Horizons,‎ février 2013 (lire en ligne)
• Sherioz, « Exploring Fractals with ABACABA », Chicago Geek Guy,‎ 21 avril 2016 (lire en ligne, consulté le 6 octobre 2017)
• Mike Naylor, « Abacaba! – Using a mathematical pattern to connect art, music, poetry and literature », 2011 (consulté le 6 octobre 2017)
• Craig Conley, Magic Words : A Dictionary, Weiser Books, 1^er octobre 2008, 360 p. (ISBN 978-1-60925-050-8, lire en ligne).

S'il existe un mot infini sur ${\displaystyle k}$ lettres qui évite un motif ${\displaystyle p}$, le motif est dit ${\displaystyle k}$-évitable. Sinon, il est ${\displaystyle k}$-inévitable. Si ${\displaystyle p}$ est évitable, le plus petit entier ${\displaystyle k}$ tel que ${\displaystyle p}$ est ${\displaystyle k}$-évitable, noté ${\displaystyle \lambda (p)}$, est appelé l'indice d'évitabilité de ${\displaystyle p}$[9]. Si ${\displaystyle p}$ est inévitable, son indice d'évitabilité est, par définition, ${\displaystyle \infty }$. Par exemple, comme le motif ${\displaystyle xyx}$ est inévitable, son indice est ${\displaystyle \infty }$. En revanche, l'indice d'évitabilité du motif ${\displaystyle xx}$ est 3, car il existe un mot sans carré infini sur trois lettres, et il n'en existe pas sur deux lettres. Ainsi ${\displaystyle \lambda (xx)=3}$.

Pour les motifs binaires, sur deux variables ${\displaystyle x}$ et ${\displaystyle y}$, on a[10]^,[11] :

• ${\displaystyle 1,x,xy,xyx}$ sont inévitables;
• les motifs ${\displaystyle xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy}$ ont l'indice d'évitabilité 3;
• tous les autres motifs ont l'indice d'évitabilité 2.

Une variable qui n’apparaît qu'une fois dans un motif est dite isolée. On associe à un motif ${\displaystyle p}$ une « formule » ${\displaystyle f}$ en remplaçant dans ${\displaystyle p}$ chaque variable isolée par un point. Les facteurs entre des points sont appelés des fragments.

Une occurrence d'une formule ${\displaystyle f}$ dans un mot ${\displaystyle w}$ est un morphisme non effaçant ${\displaystyle h}$ tel que l'image par ${\displaystyle h}$ de chaque fragment de ${\displaystyle f}$ est un facteur de ${\displaystyle w}$. Comme pour les motifs, l'indice d'évitabilité ${\displaystyle \lambda (f)}$ d'une formule ${\displaystyle f}$ est la taille du plus petit alphabet qui ne contient pas d'occurrence de la formule ${\displaystyle f}$. Si ${\displaystyle f}$ est la formule associée à un motif ${\displaystyle p}$, tout mot évitant ${\displaystyle f}$ évite aussi ${\displaystyle p}$, et on a donc ${\displaystyle \lambda (p)\leq \lambda (f)}$. S'il existe un mot infini qui évite ${\displaystyle p}$, il existe aussi un mot infini récurrent qui évite ${\displaystyle p}$. Ce mot récurrent évite aussi ${\displaystyle f}$, de sorte qu'on a ${\displaystyle \lambda (p)\leq \lambda (f)}$.

L'indice d'évitabilité de toute formule binaire, c'est-à-dire composée de deux variables, a été déterminé par Pascal Ochem et Matthieu Rosenfeld[12].

Une formule ${\displaystyle f}$ est dite divisible par une formule ${\displaystyle f'}$ si ${\displaystyle f}$ n'évite pas ${\displaystyle f'}$, en d'autres termes s'il existe un morphisme non effaçant ${\displaystyle h}$ tel que l'image par ${\displaystyle h}$ de tout fragment de ${\displaystyle f'}$ est un facteur d'un fragment de ${\displaystyle f}$. Si ${\displaystyle f}$ est divisible par ${\displaystyle f'}$, alors tout mot évitant ${\displaystyle f'}$ évite aussi ${\displaystyle f}$, donc ${\displaystyle \lambda (f)\leq \lambda (f')}$. Le retourné ${\displaystyle f^{R}}$ d'une formule ${\displaystyle f}$ et ${\displaystyle f}$ ont même indice d'évitabilité, donc ${\displaystyle \lambda (f^{R})=\lambda (f)}$. Par exemple, le fait que ${\displaystyle ABA{\cdot }AABB}$ est 2-évitable implique que ${\displaystyle ABAABB}$ ou ${\displaystyle BAB{\cdot }AABB}$ sont 2-évitables.

R. J. Clark a introduit[13] la notion de base de ${\displaystyle n}$-évitabilité pour les formules : c'est le plus petit ensemble ${\displaystyle X}$ de formules tel que, pour tout indice ${\displaystyle i\leq n}$, toute formule évitable à ${\displaystyle i}$ variables est divisible par une formule à au plus ${\displaystyle i}$ variables dans ${\displaystyle X}$.

Une formule circulaire[14] est une formule dont chaque fragment est obtenu par une permutation circulaire des lettres du précédent, par exemple ${\displaystyle ABA{\cdot }BAB}$ ou ${\displaystyle ABCA{\cdot }BCAB{\cdot }CABC}$.

Clark a montré que l'index d'évitabilité est au plus 4 pour toute formule circulaire et pour toute formule de la base de 3-évitabilité, et donc pour toute formule évitable contenant au plus 3 variables. Cette propriété a été précisé par Gamard et al.[14]

Les mots de Zimin sont définis par récurrence par

${\displaystyle Z_{0}=\varepsilon }$ et ${\displaystyle Z_{n}=Z_{n-1}a_{n}Z_{n-1}}$,

où ${\displaystyle a_{1},\dots ,a_{n},\dots }$ sont des lettres. Les premiers mots sont : ${\displaystyle a,aba,abacaba,abacabadabacaba}$

On s'intéresse à la longueur des mots sur un alphabet à ${\displaystyle q}$ lettres qui contient en facteur une copie du mot de Zimin ${\displaystyle Z_{n}}$, c'est-à-dire une image du mot ${\displaystyle Z_{n}}$, où chaque lettre est remplacée par un mot non vide. Ainsi, le mot

${\displaystyle aabbaacccaabbaa}$

est une copie de ${\displaystyle abacaba}$, de même ${\displaystyle abacaba}$ est une copie de ${\displaystyle aba}$ (en remplace au choix ${\displaystyle a}$ par ${\displaystyle aba}$ et ${\displaystyle c}$ par ${\displaystyle b}$, ou on laisse ${\displaystyle a}$ inchangé et on remplace ${\displaystyle b}$ par ${\displaystyle bacab}$). Plus généralement, ${\displaystyle Z_{n}}$ contient deux copies de ${\displaystyle Z_{n-1}}$, et ${\displaystyle Z_{n}}$ est une copie de ${\displaystyle Z_{n-1}}$ obtenue en remplaçant les occurrences de la première lettre ${\displaystyle a_{1}}$ par ${\displaystyle aba}$.

On définit une fonction ${\displaystyle f(n,q)}$ par :

${\displaystyle f(n,q)}$ est le plus petit entier ${\displaystyle M}$ tel que tout mot de longueur ${\displaystyle M}$ sur un alphabet à ${\displaystyle q}$ lettres contient en facteur une copie du mot de Zimin ${\displaystyle Z_{n}}$.

On a ${\displaystyle f(1,q)=1}$ et ${\displaystyle f(2,q)=2q+1}$. La deuxième égalité vient du fait que, par le principe du tiroir, au moins une lettre apparaît trois fois dans tout mot de longueur ${\displaystyle 2q+1}$. La copie de ${\displaystyle Z_{2}=aba}$ consiste en la première et la troisième occurrence de cette lettre, le facteur non vide qui les sépare étant l'image de la lettre ${\displaystyle b}$. D'autre part, la borne est atteinte puisque le mot ${\displaystyle a_{1}a_{1}a_{2}a_{2}\cdots a_{q}a_{q}}$ de longueur ${\displaystyle 2q}$ ne contient pas de copie de ${\displaystyle aba}$.

Une relation de récurrences sur ${\displaystyle f(n,q)}$ est donnée par la formule suivante de Cooper et Rorabaugh[15] :

${\displaystyle f(n+1,q)\leq (f(n,q)+1)(q^{f(n,q)}+1)-1}$.

Un mot de longueur ${\displaystyle (f(n,q)+1)(q^{f(n,q)}+1)-1}$ se factorise en effet en ${\displaystyle q^{f(n,q)}+1}$ mots, chacun de longueur ${\displaystyle f(n,q)}$ séparés par une lettre. Chacun des facteurs de longueur ${\displaystyle f(n,q)}$ contient une copie de ${\displaystyle Z_{n}}$. Comme il y en a ${\displaystyle q^{f(n,q)}+1}$, deux de ces facteurs sont égaux. Comme ces deux copies sont séparées par au moins une lettre, ceci fournit une copie de ${\displaystyle Z_{n+1}}$. On peut améliorer cette majoration dans le cas de 3 lettres[16] :

${\displaystyle f(3,q)\leq 2^{q+1}(q+1)!}$

En fait, on a même[17] :

${\displaystyle f(3,q)=\theta (2^{q}q!)}$.

Des majorations et minorations pour d'autres cas font intervenir une fonction tour (tower en anglais) d'itération d'exponentiation, notée ${\displaystyle T}$ et définie par :

${\displaystyle T(0,k)=1}$ et ${\displaystyle T(n+1,k)=k^{T(n,k)}}$.

Ainsi

${\displaystyle T(1,k)=k}$, ${\displaystyle T(2,k)=k^{k}}$, ${\displaystyle T(3,k)=k^{k^{k}}}$, ${\displaystyle T(4,k)=k^{k^{k^{k}}}}$.

Avec ces notations, on a:

${\displaystyle f(n,q)\leq T(n,q)}$

et aussi une minoration sous forme d'une tour d'exponentielles, même dans le cas d'un alphabet binaire[17]^,[18]^,[19] :

${\displaystyle f(n,q)\leq T(n,q)}$ et ${\displaystyle f(n,2)\geq T(n-3,2)}$ (pour ${\displaystyle n\geq 4}$).

Chapitres dans des livres

• (en) Jean-Paul Allouche et Jeffrey O. Shallit, Automatic sequences : Theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3, Math Reviews 1997038, zbMATH 1086.11015).
• Jean Berstel, Aaron Lauve, Christophe Reutenauer et Franco V. Saliola, Combinatorics on words : Christoffel words and repetitions in words, American Mathematical Society et Centre de recherches mathématiques, coll. « CRM Monograph Series » (n^o 27), 2008, 504 p. (ISBN 978-1-4200-7267-9, zbMATH 1161.68043).
• Julien Cassaigne, « Unavoidable patterns », dans M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2011 (réimpr. 2011) (1^re éd. 2002) (ISBN 978-0-521-18071-9, Math Reviews 1905123, zbMATH 1221.68183), p. 111-134.
• (en) N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Édité par Valérie Berthé, Sébastien Ferenczi, Christian Mauduit et Anne Siegel, Springer-Verlag, coll. « Lecture Notes in Mathematics » (n^o 1794), 2002, 402 p. (ISBN 3-540-44141-7, zbMATH 1014.11015, lire en ligne).

Articles

• [2014] Joshua Cooper et Danny Rorabaugh, « Bounds on Zimin word avoidance », Congressus Numerantium, vol. 222,‎ 2014, p. 87-95 (ISSN 0384-9864, Math Reviews 3328869).
• [2015] Wojciech Rytter et Arseny M. Shur, « Searching Zimin patterns », Theoret. Comput. ci., vol. 571,‎ 2015, p. 50-57 (DOI 10.1016/j.tcs.2015.01.004).
• [2016] Joshua Cooper et Danny Rorabaugh, « Asymptotic density of Zimin words », Discrete Math. Theor. Comput. Sci., vol. 18, n^o 3,‎ 2016, article n^o 3 (25 pages) (Math Reviews 3625459).
• [2019] David Conlon, Jacob Fox et Benny Sudakov, « Tower-type bounds for unavoidable patterns in words », Transactions of the American Mathematical Society, vol. 372, n^o 9,‎ 2019, p. 6213-6229 (DOI 10.1090/tran/7751, arXiv 1704.03479).
• [2017] Arnaud Carayol et Stefan Göller, « On Long Words Avoiding Zimin Patterns », dans Heribert Vollmer et Brigitte Vallée (éditeurs), 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 66), 2017 (ISBN 978-3-95977-028-6, ISSN 1868-8969, DOI 10.4230/LIPIcs.STACS.2017.19, lire en ligne), p. 19:1-19:13.
• [2019] Arnaud Carayol et Stefan Göller, « On Long Words Avoiding Zimin Patterns », Theory of Computing Systems, vol. 63, n^o 5,‎ 2019, p. 926–955 (DOI 10.1007/s00224-019-09914-2).

Thèse

• Pascal Ochem, Évitement de motifs (Habilitation universitaire), Université de Montpellier, 2019, 124 p. (lire en ligne).

• Portail de l'informatique théorique