Motif inévitable

En informatique théorique, en combinatoire, et notamment en combinatoire des mots, un motif inévitable est un motif (au sens défini ci-dessous) qui apparaît dans tout mot assez long. Un motif est évitable sinon. Par exemple, le motif ${\displaystyle xx}$ est inévitable sur deux lettres et évitable sur trois lettres, parce que tout mot assez long sur deux lettres contient un carré (composé de deux facteurs consécutifs égaux), et qu'il existe des mots arbitrairement longs sans carré sur trois lettres.

Les motifs évitables et inévitables généralisent la notion de répétition dans les mots, et leur étude s'inscrit dans celle des régularités dans les mots.

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}$

Il est possible de s'intéresser aux motifs inévitables contenus dans l'écriture décimale (ou dans d'autres bases de numération) de nombres appartenant à des sous-ensembles de l'ensemble des entiers naturels. Ainsi 14 est un motif inévitable de l'ensemble ${\displaystyle S=\{124;1894\}}$ car les écritures des deux éléments de S contiennent les chiffres 1 et 4 dans cet ordre.

On s'intéresse aux motifs inévitables contenus dans l'écriture des nombres premiers qui sont eux-mêmes des nombres premiers. Plus précisément, on cherche le plus petit ensemble de nombres premiers dont au moins l'un des éléments apparait dans l'écriture de tout nombre premier. On a alors les résultats suivants^[7]:

• en base 2 l'ensemble inévitable minimal des nombres premiers est ${\displaystyle \{10;11\}}$^[a];
• en base 3 l'ensemble inévitable minimal des nombres premiers est ${\displaystyle \{2;10;111\}}$^[b];
• en base 4 l'ensemble inévitable minimal des nombres premiers est ${\displaystyle \{2;3;11\}}$^[c];
• en base 10 l'ensemble inévitable minimal des nombres premiers est ${\displaystyle \{2;3;5;7;11;19;41;61;89;409;449;499;881;991;6469;6949;9001;9049;9649;9949;60649;666649;946649;60000049;66000049;66600049\}}$.

Tout nombre premier écrit en base 10 contient l'un des motifs de l'ensemble donné ci-dessus. Par exemple 6 661 contient le motif 61.

On s'intéresse aux motifs inévitables contenus dans l'écriture en base 10 des puissances de deux qui sont eux-mêmes des puissances de deux. Il est conjecturé que l'ensemble inévitable minimal des puissances de deux est^[7]: ${\displaystyle \{1;2;4;8;65536\}}$.

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, MR 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, MR 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, MR 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) (MR 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