Mot sans facteur carré

En combinatoire, et notamment en combinatoire des mots, un carré est un mot composé de deux parties égales consécutives, comme bonbon ou papa. En bio-informatique, un carré est appelé une répétition en tandem. Un mot sans facteur carré ou plus simplement un mot sans carré est un mot qui ne contient pas de facteur carré. Par exemple, le mot répétition contient le carré titi ; en revanche, le mot consécutivement est un mot sans carré. L'étude des mots sans carré fait partie, plus généralement, de l'étude des répétitions dans les mots, et de la possibilité de les éviter. On parle alors de répétitions évitables ou inévitables.

Il existe des mots infinis sans carré sur tout alphabet d'au moins trois lettres, comme l'a prouvé Axel Thue^[1],[2]. Sur un alphabet à deux lettres, un tel mot n'existe pas. Le mot de Prouhet-Thue-Morse contient des carrés, en revanche il est sans cube.

Une méthode fréquemment utilisée par construire des mots infinis sans carré, sans cube ou sans puissance plus élevée est par itération d'un morphisme. Si ce morphisme a la propriété de transformer une mot fini sans carré, sans cube ou sans puissance plus élevée en un mot de même nature, on parle d'un morphisme sans carré, sans cube ou sans puissance plus élevée.

Premiers exemples

• Sur un alphabet à deux lettres ${\displaystyle \{a,b\}}$, il n'existe que six mots sans carré non vides : ce sont les mots ${\displaystyle a,b,ab,ba,aba,bab}$.

• Sur un alphabet à trois lettres ${\displaystyle A=\{a,b,c\}}$, et partant de la lettre ${\displaystyle a}$, on remplace

${\displaystyle a}$ par ${\displaystyle abc}$, ${\displaystyle b}$ par ${\displaystyle ac}$, ${\displaystyle c}$ par ${\displaystyle b}$.

On alors obtient successivement

${\displaystyle {\begin{array}{l}a\\abc\\abcacb\\abcacbabcbac\end{array}}}$

En itérant et en prenant le point fixe de cette opération, on obtient le mot infini qui commence par

${\displaystyle abcacbabcbacabcacbacabcb\cdots }$.

Ce mot est sans carré. Cette construction est donnée par Marshall Hall Jr.^[3]. Dans la terminologie des répétitions, les carrés sont inévitables sur 2 lettres, mais évitables sur plus de 2 lettres.

Les constructions de Thue

Les premières constructions de Thue datent de 1906 et 1912. Plusieurs auteurs les ont, de façon indépendante, retrouvées, ou ont trouvé d'autres constructions. Les articles de Thue, même s'ils étaient écrits en allemand qui à l'époque était l'une des langues scientifiques par excellence ont été publiés dans un journal peu connu, et n'ont donc pas été largement reconnus.

Les constructions de Thue (1906)

Thue donne, dans son premier article^[1] datant de 1906, plusieurs constructions de mots infinis sans carré.

Un premier mot sans carré, sur un alphabet à 4 lettres, est obtenu comme suit : on part du mot ${\displaystyle abacbc}$, et on insère la lettre ${\displaystyle d}$ entre deux lettres du mot, à 4 places différentes. Ces 4 mots sont pris pour définir un morphisme :

${\displaystyle {\begin{array}{l}a\mapsto adbacbc\\b\mapsto abdacbc\\c\mapsto abadcbc\\d\mapsto abacdbc\end{array}}}$

En itérant à partir de la lettre a, on obtient le mot infini (les barres verticales sont censées faciliter la lecture) :

${\displaystyle adbacbc|abacdbc|abdacbc|adbacbc|abadcbc|abdacbc|abadcbc\cdots }$.

Le symbole ${\displaystyle d}$ sert de « marqueur » qui permet de retrouver la lettre qui a engendré un bloc donné.

Thue donne un autre mot sans carré, sur trois lettres cette fois-ci, obtenu comme suit : on remplace, dans un mot sans carré sur ${\displaystyle a,b,c}$, les lettres selon les règles suivantes :

${\displaystyle a\mapsto abac}$

${\displaystyle b\mapsto babc}$

${\displaystyle c\mapsto bcac}$ si la lettre avant ${\displaystyle c}$ est ${\displaystyle a}$

${\displaystyle c\mapsto acbc}$ si la lettre avant ${\displaystyle c}$ est ${\displaystyle b}$

En partant de a, on obtient

${\displaystyle abac|babc|abac|bcac|\cdots }$.

La construction de Thue (1912)

Dans son long article^[2], Axel Thue poursuit le but de classer toutes les suites sans carré, sans toutefois y parvenir complètement. Durant cette étude, il construit un mot sans carré à partir de la suite de Prouhet-Thue-Morse :

${\displaystyle 01101001100101101001011001101001\cdots }$.

Il observe que, comme il n'y a pas de bloc ${\displaystyle 111}$ dans la suite, deux symboles ${\displaystyle 0}$ consécutifs sont séparés par 0, 1, ou 2 symboles ${\displaystyle 1}$. Il suffit de reporter la séquence de ces nombres pour obtenir une suite sur trois symboles :

${\displaystyle 210201210120210\cdots }$.

En remplaçant ${\displaystyle 2}$ par ${\displaystyle a}$, ${\displaystyle 1}$ par ${\displaystyle b}$ et ${\displaystyle 0}$ par ${\displaystyle c}$, on retrouve la suite mentionnée plus haut. Cette suite est parfois appelée la suite ternaire de Thue-Morse. La construction a été retrouvée en 1963 par C. H. Braunholtz^[4].

Autres constructions

La suite asymétrique d'Arshon (1937)

Dans un article en russe^[5] mais avec un long résumé en français, le mathématicien russe C. E. Arshon propose une construction générale qui, dans le cas ternaire, donne un mot infini sans carré (qu'il appelle asymétrique). Dans le cas binaire, une version simplifiée redonne la suite de Prouhet-Thue-Morse. Arshon considère les deux morphismes :

${\displaystyle {\begin{array}{l}1\mapsto 123\\2\mapsto 231\\3\mapsto 312\end{array}}\qquad {\begin{array}{l}1\mapsto 321\\2\mapsto 132\\3\mapsto 213\end{array}}}$

Le premier sert pour produire des mots à partir de symboles en position impaire dans un mot, le deuxième pour les symboles en position paire. On commence par le mot

${\displaystyle 123}$

Le premier ${\displaystyle 1}$ est en position impaire 1, et il produit ${\displaystyle 123}$, le ${\displaystyle 2}$ en position 2 produit ${\displaystyle 132}$, et le troisième symbole, en position impaire, produit ${\displaystyle 312}$. On obtient la suite (les barres verticales doivent améliorer la lisibilité) :

${\displaystyle 123|132|312}$

On continue : le ${\displaystyle 1}$ en position 4 produit ${\displaystyle 321}$, le ${\displaystyle 3}$ en position 5 produit ${\displaystyle 312}$, le ${\displaystyle 2}$ en position 6 produit ${\displaystyle 132}$, etc. On construit ainsi une suite débutant par :

${\displaystyle 123|132|312|321|312|132\cdots }$

Arshon prouve que ce mot est sans carré. Cette suite est 3-automatique : on prend le morphisme sur 6 lettres ${\displaystyle \{1,2,3,{\bar {1}},{\bar {2}},{\bar {3}}\}}$ donné par

${\displaystyle {\begin{array}{l}1\mapsto 1{\bar {2}}3\\2\mapsto 2{\bar {3}}1\\3\mapsto 3{\bar {1}}2\end{array}}\qquad {\begin{array}{l}{\bar {1}}\mapsto {\bar {3}}2{\bar {1}}\\{\bar {2}}\mapsto {\bar {1}}3{\bar {2}}\\{\bar {3}}\mapsto {\bar {2}}1{\bar {3}}\end{array}}}$.

Ce morphisme 3-uniforme engendre le mot infini

${\displaystyle 1{\bar {2}}3|{\bar {1}}3{\bar {2}}|3{\bar {1}}2|{\bar {3}}2{\bar {1}}|3{\bar {1}}2|{\bar {1}}3{\bar {2}}\cdots }$

où les lettres en position paire sont barrées. Dans un deuxième temps, on « efface » les barres sur les lettres par le morphisme lettre-à-lettre qui identifie une lettre et sa copie barrée.

La construction de Morse et Hedlund (1944)

Dans leur article^[6], Morse et Hedlund partent, comme Thue, de la suite de Prouhet-Thue-Morse :

${\displaystyle 01101001100101101001011001101001\cdots }$.

Contrairement à Thue, ils remplacent deux bits consécutifs par le nombre qu'il représentent en binaire, soit

${\displaystyle {\begin{array}{l}00\mapsto 0\\01\mapsto 1\\10\mapsto 2\\11\mapsto 3\end{array}}}$

puis ils identifient ${\displaystyle 0}$ et ${\displaystyle 3}$ (en d'autres termes, ils opèrent modulo 3). La suite obtenue est :

${\displaystyle 102120102012102\cdots }$.

C'est la suite ternaire de Thue-Morse, au codage près. On obtient le même mot différemment, en itérant le morphisme sur 4 lettres donné par :

${\displaystyle {\begin{array}{l}0\mapsto 03\\1\mapsto 20\\2\mapsto 21\\3\mapsto 02\end{array}}}$

et en identifiant ensuite ${\displaystyle 0}$ et ${\displaystyle 3}$. L'intérêt de cette construction est de montrer que le mot ternaire de Thue-Morse est une suite automatique.

Le morphisme de Hawkins et Mientka (1956)

Ces deux auteurs proposent^[7] le morphisme suivant :

${\displaystyle {\begin{array}{l}a\mapsto bacbcacbabcbaca\\b\mapsto bacbabcbacbcacbaca\\c\mapsto bacbcabacabcbaca\end{array}}}$

et ils prouvent qu'en itérant à partir de la lettre ${\displaystyle b}$, on obtient un mot infini sans carré.

Les perles de John Leech (1957)

Dans une courte note^[8], John Leech propose la construction suivante. On itère le morphisme défini par

${\displaystyle {\begin{array}{l}a\mapsto abcbacbcabcba\\b\mapsto bcacbacabcacb\\c\mapsto cabacbabcabac\end{array}}}$

L'image de chaque lettre est le mot transformé par ${\displaystyle (a\to b,b\to c,c\to a)}$. En itérant à partir de ${\displaystyle a}$, on obtient

${\displaystyle abcbacbcabcba\ bcacbacabcacb\ cabacbabcabac\ bcacbacabcacb\cdots }$

En fait, Leech est intéressé par la construction d'une suite biinfinie sans carré. Pour cela, il recentre chaque mot sur la lettre du milieu. Pour obtenir une convergence, il faut modifier le morphisme de sorte que la lettre centrale de l'image de ${\displaystyle a}$ soit ${\displaystyle a}$ etc. On prend donc

${\displaystyle {\begin{array}{l}a\mapsto cabacbabcabac\\b\mapsto abcbacbcabcba\\c\mapsto bcacbacabcacb\end{array}}}$

L'itération donne :

${\displaystyle {\begin{array}{c}a\\cabacb\ a\ bcabac\\\cdots abcbacbcabcba\ cabacb\ a\ bcabac\ abcbacbcabcba\cdots \end{array}}}$

La construction de Zech (1958)

Theodor Zech^[9] donne le morphisme

${\displaystyle {\begin{array}{l}a\mapsto abcabacbabcb\\b\mapsto acbcabacabcb\\c\mapsto acabacbcabcb\end{array}}}$

Le mot infini est obtenu en itérant à partir de ${\displaystyle a}$ par exemple. La preuve est facilitée par le fait que les trois images se terminent toutes par ${\displaystyle abcb}$.

La construction sans simplification de Dean (1963)

Richard Dean^[10] construit une suite sans carré sur quatre symboles avec la propriété supplémentaire que deux symboles appareillés ne peuvent se suivre. De façon plus imagée, si les quatre sont ${\displaystyle x,x^{-1},y,y^{-1}}$, la suite ne contient pas les blocs ${\displaystyle xx^{-1}}$, ${\displaystyle x^{-1}x}$, ${\displaystyle yy^{-1}}$ et ${\displaystyle y^{-1}y}$. Pour simplifier l'exposé, Dean choisit les symboles ${\displaystyle 1,2,3,4}$ et construit une suite sans carré sans les facteurs ${\displaystyle 13,31,24,42}$. Il obtient ceci en imposant que les symboles en position paire dans la suite sont des symboles pairs, et les symboles en position impaire sont impairs. La suite est la limite de la suite de mots ${\displaystyle (w_{n})}$ obtenue comme suite: On pose ${\displaystyle w_{0}=1234}$. Chaque ${\displaystyle w_{n}}$ est un mot de longueur ${\displaystyle 2^{n+2}}$ qui est factorisé en quatre mot de longueur ${\displaystyle 2^{n}}$ notés ${\displaystyle A_{n},B_{n},C_{n},D_{n}}$ de sorte que

${\displaystyle w_{n}=A_{n}B_{n}C_{n}D_{n}}$.

Le mot ${\displaystyle w_{n+1}}$ est défini par

${\displaystyle w_{n+1}=w_{n}A_{n}D_{n}C_{n}B_{n}}$.

On obtient

${\displaystyle {\begin{array}{l}w_{0}=1234\\w_{1}=12341432\\w_{2}=1234143212321434\\w_{3}=12341432123214341234143412321432\end{array}}}$

En fait, on se convainc très vite que les mots ${\displaystyle w_{n}}$ s'obtiennent en itérant, à partir de ${\displaystyle 1}$, le morphisme

${\displaystyle {\begin{array}{lcl}1&\mapsto &12\\2&\mapsto &34\\3&\mapsto &14\\4&\mapsto &32\end{array}}}$

D'autres constructions, ou les mêmes, ont été données par Kurosaki, Shyr, Dejean.

Le mot infini de Dean a fait l'objet d'une étude par Golnaz Badkobeh, Tero Harju, Pascal Ochem et Matthieu Rosenfeld^[11]. Les auteurs considèrent les mots de Dean finis qu'ils définissent comme des mots réduits sans carré. Ils montrent que si w est un mot de Dean de longueur au moins 59 alors il y a au plus six mots réduits de longueur 3 qui sont évités par w. Ils construisent un mot de Dean infini évitant six mots réduits de longueur 3. Ils construisent également des mots de Dean infinis ayant un exposant critique bas et qui évitent moins de mots réduits de longueur 3. Enfin, ils montrent que la fréquence minimale d'une lettre dans un mot de Dean est de 8/59 et que le taux de croissance est proche de 1,45818.

Morphismes sans carré

Un morphisme ${\displaystyle f}$ qui transforme un mot sans carré en un mot sans carré, donc qui préserve les mots sans carrés, est appelé lui-même un morphisme sans carré. Si ${\displaystyle f}$ est un tel morphisme, on construit une suite de mots sans carré en partant d'une lettre ${\displaystyle a}$, et appliquant le morphisme indéfiniment :

${\displaystyle a,f(a),f(f(a)),\dots ,f^{n}(a)\dots }$.

Si les mots deviennent de plus en plus long, et si de plus le mot ${\displaystyle f(a)}$ commence par ${\displaystyle a}$, le mot infini, souvent noté

${\displaystyle f^{\omega }(a)}$

dont tous les ${\displaystyle f^{n}(a)}$ sont préfixes, est un mot infini sans carré. Plus généralement, un morphisme sans puissance ${\displaystyle k}$-ième est un morphisme qui préserve les mots sans puissances ${\displaystyle k}$-ième et à nouveau, le mot infini ${\displaystyle f^{\omega }(a)}$ est sans puissance ${\displaystyle k}$-ième.

Un théorème d'Axel Thue et de Maxime Crochemore

Le théorème suivant, démontré par Axel Thue, permet de démontrer simplement pour de nombreux exemples de morphismes qu'ils engendrent des mots sans carrés. Dans cet énoncé et dans la suite, on ignore systématiquement le mot vide qui ne joue pas de rôle dans ce contexte. Un morphisme ${\displaystyle f}$ est infixe si aucun mot ${\displaystyle f(a)}$ n'est facteur d'un mot ${\displaystyle f(b)}$, pour deux lettres ${\displaystyle a,b\in A}$. Une démonstration est donnée par Bean, Ehrenfeucht et McNulty^[12], et aussi par Lothaire^[13].

La condition d'être infixe est notamment réalisée par les morphismes uniformes, pourvu qu'ils soient injectifs sur l'alphabet.

Maxime Crochemore a étendu ce théorème à des morphismes plus généraux.

Dans le cas des morphismes uniformes, on retrouve la borne de Thue.

Sur un alphabet à 3 lettres, on peut donner une formulation encore plus précise :

Le morphisme ${\displaystyle f:\{a,b,c\}^{+}\to \{a,b,c,d,e\}^{+}}$ défini par

${\displaystyle f(a)=deabcbda,\ f(b)=b,\ f(c)=c}$

préserve les mots sans carré de longueur au plus 4, mais ${\displaystyle f(abcba)=deabcbdabcbdeabcbda}$ contient le carré ${\displaystyle (abcbd)^{2}}$. Ceci montre que l'on ne peut pas remplacer l'entier 5 par 4 dans le théorème précédent.

Un tel résultat n'existe pas pour des alphabets plus grands. Si l'alphabet A au plus de 3 lettres, il existe pour tout n des morphismes qui préservent des mots sans carrés de longueur n sans être des morphismes sans carré. Il en est ainsi du morphisme ${\displaystyle f:\{a,b,c,d\}^{+}\to \{a,b,c,d,e\}^{+}}$ défini par

${\displaystyle f(a)=eaxa,f(b)=b,f(c)=c,f(d)=d}$,

où ${\displaystyle x}$ est un mot sans carré de longueur ${\displaystyle n}$ sur les trois lettres ${\displaystyle b,c,d}$. Le mot ${\displaystyle ax}$ est un mot sans carré, de longueur ${\displaystyle n+1}$, et ${\displaystyle f(ax)=eaxax}$ contient un carré, donc ${\displaystyle f}$ n’est pas un morphisme sans carré. Mais on peut vérifier que ${\displaystyle f}$ préserve les mots sans carré de longueur ${\displaystyle n}$.

Exemples

Les morphismes ${\displaystyle h}$ et ${\displaystyle g}$ donnés par ${\displaystyle h(a)=abcab,\ h(b)=acabcb,\ h(c)=acbcacb}$ et ${\displaystyle g(a)=abacb,\ g(b)=abcbac\ g(c)=abcacbc}$ sont tous deux sans carré^[12],[2]. La somme des longueurs des images des lettres est dans les deux cas égale à 18 (5+6+7). Il a été prouvé par Arturo Carpi^[16] qu'il n existe pas de morphismes sans carré dont la somme des longueurs des images des lettres est plus petite.

Puissances supérieures

Exemples

Voici quelques exemples de morphismes sans puissance supérieures.

Le morphisme de Prouhet-Thue-Morse

${\displaystyle t(a)=ab,\ t(b)=ba}$

est sans puissance ${\displaystyle k}$-ième pour tout k>2.

Le morphisme de Fibonacci

${\displaystyle t-\phi (a)=ab,\ \phi (b)=a}$

engendre le mot de Fibonacci ${\displaystyle abaababaabaababaababa\cdots }$. Ce mot est sans puissance ${\displaystyle k}$-ième, mais le morphisme de Fibonacci lui-même n'est pas un morphisme sans puissance 4^e puisque ${\displaystyle \phi (b^{3}a)=a^{4}b}$

Un exemple de Bean, Ehrenfeucht et McNulty^[12] ; le morphisme défini par

${\displaystyle h(a)=abacbab,\ h(b)=cdabcabd,\ h(c)=cdacabcbd,\ h(d)=cdacbcacbd}$

est sans carré mais n'est pas sans cube.

L'existence de morphismes sans puissance a été prouvée^[12] : pour tout alphabet ternaire, il existe un morphisme sans carré de l'alphabet dans lui-même, pour tout alphabet binaire, il existe un morphisme sans cube de l’alphabet dans lui-même.

Morphismes sans cube

Le cas des morphismes sans cube diffère de celui des autres morphismes sans puissance ${\displaystyle k}$-ième ; être sans cube une condition moins restrictive que d'être sans carré. On a le résultat suivant :

L'existence d'un tel morphisme uniforme, sur un alphabet binaire, a été prouvé notamment par Currie et Rampersand^[18].

Mots sans cube avec transitions

Un cas de régularité sur les mots sans cubes a été établi par Elena A. Petrova et Arseny M. Shur^[19].

Les auteurs montrent que ce résultat implique l'existence de mots infinis sans cube ayant une complexité en facteurs très élevés.

Suite k-Thue

Une ${\displaystyle d}$-sous-suite d'une suite ${\displaystyle a_{0},a_{1},\ldots ,a_{n},\ldots }$ est toute une sous-suite ${\displaystyle a_{i},a_{i+d},,a_{i+2d}}$ d'éléments pris à distance ${\displaystyle d}$. Une suite k-Thue une suite dans laquelle chaque ${\displaystyle d-}$sous-suite, pour ${\displaystyle 1\leq d\leq k}$, est non répétitive, c'est-à-dire qu'elle ne contient pas de sous-suites égales consécutives. Une suite de 1-Thue est une suite sans facteur carré. Par exemple,

a b d c b c

est une suite sans carré, donc 1-Thue, mais elle n'est pas 2-Thue parce que la 2-sous-suite b c c contient un carré. De même,

a b c a d b

est une suite sans carré, mais elle n'est pas 3-Thue à cause de la 3-sous-suite a a.

La notion de suite k-Thue a été introduite par Currie et Simpson^[20]. À leur suite Grytczuk a proposé^[21] la conjecture selon laquelle, pour tout ${\displaystyle k}$, il suffit de ${\displaystyle k+2}$ symboles pour construire une suite de ${\displaystyle k}$-Thue de longueur arbitraire. Jusqu'à présent (2020), la conjecture a été confirmée pour ${\displaystyle k=1,\ldots ,8}$^[22].

Nombre de mots sans carré

• Le nombre de mots ternaires sans carré de longueur 1, 2, … est la suite A006156 de l'OEIS. Elle commence par :

${\displaystyle 3,6,12,18,30,42,60,\ldots }$

• Le nombre de mots sur quatre lettres sans carré de longueur 1, 2, … est la suite A051041 de l'OEIS. Elle commence par :

${\displaystyle 4,12,36,96,264,696,\ldots }$

Notons ${\displaystyle c_{k}(n)}$ le nombre de mots sans carré de longueur ${\displaystyle n}$ sur un alphabet à ${\displaystyle k}$ lettres. On sait depuis longtemps que ${\displaystyle c_{k}(n)}$ croît exponentiellement pour ${\displaystyle k\geq 3}$. On connaît maintenant^[23] un très bon encadrement pour ces valeurs. On a par exemple :

${\displaystyle 1,301759^{n}<c_{3}(n)<1,301761^{n}}$

Extensions

Extension aux graphes

Le nombre de Thue d'un graphe G est le plus petit entier k tel que G possède une k-coloration pour laquelle la suite des couleurs sur tout chemin simple (qui ne passe pas deux fois par le même sommet) est sans carré. Un résultat significatif est que le nombre de Thue d'un graphe planaire est borné^[24].

Mot sans carré extrémal

Jarosław Grytczuk, Hubert Kordulewski et Artur Niewiadomski ont introduit la notion de mot sans carré extrémal. Pour cela, ils appellent extension d'un mot ${\displaystyle w}$ tout mot obtenu par insertion d'une lettre dans le mot. Un mot ${\displaystyle w}$ sans carré est extrémal si toute extension de ${\displaystyle w}$ contient un carré. Ainsi, sur l'alphabet à deux lettres ${\displaystyle a,b}$, le mot ${\displaystyle aba}$ est sans carré extrémal : les 8 extensions ${\displaystyle {\color {red}a}aba}$, ${\displaystyle {\color {red}b}aba}$, ${\displaystyle a{\color {red}a}ba}$, ${\displaystyle a{\color {red}b}ba}$, ${\displaystyle ab{\color {red}a}a}$, ${\displaystyle ab{\color {red}b}a}$, ${\displaystyle aba{\color {red}a}}$, ${\displaystyle aba{\color {red}b}}$, obtenu par l'insertion d'une lettre contiennent toutes un carré.

Sur un alphabet à trois lettres, le mot

${\displaystyle abcabacbcabcbabcabacbcabc}$

est un mot sans carré extrémal, et c'est le plus court mot ternaire sans carré extrémal^[25].

Les auteurs prouvent :

Il existe des mots sans carré extrémaux pour les longueurs 25, 41, 48, 50, 63, 71, 72, 77, 79, 81, 83, 84, 85 et pour tout entier supérieur ou égal à 87^[26].

Une étude et des extensions sont données par Lucas Mol, Narad Rampersad et Jeffrey Shallit^[27].

Une question naturelle est de savoir si un analogue du théorème est valable pour des alphabets plus grands. L'étude numérique systématique est compliquée par le fait que si on dispose de quatre lettres, il y a deux possibilités d'extension d'un mot sans carré à chaque position intérieure. En fait, les auteurs^[25] n'ont pas trouvé des mots extrémaux sur quatre lettres de longueur au plus 100 et ils conjecturent qu'il n'en existe pas.

Une variante du concept de mot extrémal est la notion de mot « nonchalant » définie par Jarosław Grytczuk, Hubert Kordulewski et Bartłomiej Pawlik et publiée sur arxiv^[28]. Un tel mot est produit par une succession d'insertions de lettres dans un mot sans carré tout en conservant le caractère sans carré, en choisissant à chaque étape la dernière occurrence (la plus à droite) qui conserve l'absence de carré. Un exemple est

${\displaystyle 1,12,121,1213,12131,121312,1213121,12131231}$

Le dernier mot est obtenu par l'insertion de la lettre ${\displaystyle 3}$ en avant-dernière position. Les auteurs conjecturent qu'une telle séquence nonchalante infinie de mots sans carré existe.

Mot binaire avec peu de carrés

Tout mot binaire assez long contient au moins trois carrés. Plus précisément^[29], notent que le mot ${\displaystyle 010011000111001101}$ de longueur 18 contient 2 carrés, et que tout mot binaire lus long en contient au moins trois.

Bien que les carrés soient inévitables sur un alphabet à deux lettres, Entringer, Jackson et Schatz^[30] ont prouvé qu'il existe des mots binaires infinis ne contenant aucun carré d'ordre ≥ 3 (L'ordre d'un carré ${\displaystyle xx}$ est la longueur ${\displaystyle |x|}$ de ${\displaystyle x}$). La construction d'Entringer, Jackson et Schatz, telle que présentée par Gabric et Shallit^[31], est comme suit : on part d'un mot arbitraire sans carré ${\displaystyle z}$ sur l'alphabet {0,1,2} et lui applique le morphisme uniforme

${\displaystyle h(0)=1100}$, ${\displaystyle h(1)=0111}$, ${\displaystyle h(2)=1010}$.

Les auteurs prouvent que le mot ${\displaystyle h(z)}$ résultant n'a aucun carré d'ordre ≥ 3 ; en fait, les seuls carrés qui apparaissent sont ${\displaystyle 0^{2}}$, ${\displaystyle 1^{2}}$, ${\displaystyle (01)^{2}}$, ${\displaystyle (10)^{2}}$, et ${\displaystyle (11)^{2}}$. On peut prendre comme mot de départ le mot de Thue sur 3 lettres ${\displaystyle t=210201210120210\cdots }$.

L'observation de Entringer, Jackson et Schatz a été améliorée par Fraenkel et Simpson^[32] : ils ont montré l'existence de mots binaires ayant seulement trois carrés distincts. Leur construction est, d'après Gabric et Shallit^[31], difficile à établir.

Pascal Ochem^[33] donne, en 2006, une construction différente : il considère le morphisme

${\displaystyle \sigma (0)=00011001011000111001011001110001011100101100010111}$

${\displaystyle \sigma (1)=00011001011000101110010110011100010110001110010111}$

${\displaystyle \sigma (2)=00011001011000101110010110001110010111000101100111}$

et il montre que si ${\displaystyle x}$ est un mot sans puissance d'exposant strictement plus grand que 7/4, alors ${\displaystyle \sigma (x)}$ ne contient que trois carrés.

Harju et Nowotka^[34] engendrent un mot binaire infini avec trois carrés en définissant le morphisme (non uniforme)

${\displaystyle \zeta (0)=111000110010110001110010}$

${\displaystyle \zeta (1)=111000101100011100101100010}$

${\displaystyle \zeta (2)=111000110010110001011100101100}$

qu'ils appliquent au mot ternaire de Thue. Ils montrent que le mot obtenu contient seulement trois carrés.

Encore une autre construction a été donnée par Badkobeh et Crochemore^[35],[29]. Ils définissent le morphisme

${\displaystyle \xi (0)=000111}$

${\displaystyle \xi (1)=0011}$

${\displaystyle \xi (2)=01001110001101}$.

Ils montrent que l'image par ${\displaystyle \xi }$ du mot de Thue ternaire ne contient que les trois carrés ${\displaystyle 00}$, ${\displaystyle 11}$ et ${\displaystyle 1010}$. Ils montrent aussi qu'il contient les seuls cubes ${\displaystyle 000}$ et ${\displaystyle 111}$.

Une autre construction enfin est donnée par Gabric et Shallit^[31]. Ils donnent le morphisme

${\displaystyle \eta (0)=00011101}$

${\displaystyle \eta (1)=001110001101}$

${\displaystyle \eta (2)=0011000111001101}$

Ils montrent que le mot infini ${\displaystyle \eta (t)}$, où t est le mot de Thue ternaire, ne contient que les carrés 00,11, et 1010. Ils montrent aussi que ce mot est 2-automatique et peut être engendré par un (automate ?) à 27 états.

Mots sans carré en progression arithmétique

Soit

${\displaystyle w=w_{0}w_{1}w_{2}\cdots }$

un mot infini, où chaque ${\displaystyle w_{i}}$ est une lettre ; on note ${\displaystyle [w]_{p}}$ le mot infini formé en prenant les lettres de ${\displaystyle p}$ en ${\displaystyle p}$, formellement :

${\displaystyle [w]_{p}=w_{0}w_{p}w_{2p}\cdots }$.

La question suivante a été posée (et résolue ) par Tero Harju^[36] : « Pour un entier ${\displaystyle p}$ donné, existe-t-il un mot sans carré ${\displaystyle w}$ sur 3 lettres tel que ${\displaystyle w_{p}}$ est aussi sans carré ? » La réponse est positive pour ${\displaystyle p\geq 3}$, négative pour ${\displaystyle p=2}$. À la fin de son article, Harju pose les questions suivantes : Question 1.- Existe-t-il in mot infini sans carré ${\displaystyle w}$ sur trois lettres tel que les mots ${\displaystyle [w]_{p}}$ pour ${\displaystyle p\geq 3}$ contiennent tous un carré ?

Question 2.- Existe-t-il deux entiers ${\displaystyle (p,q)}$ premiers entre eux tels qu'il existe un mot infini sans carré ${\displaystyle w}$ sur trois lettres pour lequel ${\displaystyle [w]_{p}}$ et ${\displaystyle [w]_{q}}$ sont tous deux sans carrés.

Question 3.- Existe-t-il, pour tout mot sans carré ${\displaystyle v}$ sur trois lettres, un mot sans carré ${\displaystyle w}$ et un entier ${\displaystyle p\geq 3}$ tel que ${\displaystyle [w]_{p}=v}$.

Des réponses affirmatives à ces trois questions ont été données par Currie, Harju, Ochem, et Rampersad^[37].

Un problème semblable est étudié par Matthieu Rosenfeld^[38] :

Il considère une technique non constructive pour montrer que les carrés sont évitables par un mot infini même si l'on exige que certaines lettres de l'alphabet apparaissent à certaines occurrences. Il montre Nous montrons que si les positions de lettres prédéterminées sont à une distance d'au moins 19 (resp. 3 ou 2) les unes des autres, alors on peut éviter les carrés sur 3 lettres (resp. 4 ou 6 lettres). Le nombre de solutions est exponentiel. Certains calcul ont été faits par ordinateur.

Notes et références

Bibliographie

Thue

• [Thue (1906)] Axel Thue, « Über unendliche Zeichenreihen », Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania, n^o 7,‎ 1906, p. 1-22.
• [Thue (1912)] Axel Thue, « Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen », Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania, n^o 1,‎ 1912, p. 1-67.
• [Thue (1977)] Trygve Nagell, Atle Selberg, S. Selberg et K. Thalberg (éditeurs), Selected Mathematical Papers of Axel Thue, Oslo, Universitetsforlaget, 1977
  Dans cette collection d’œuvres choisies, l'article de 1906 figure aux pages 139—158, et l'article de 1912 aux pages 413—477.

Lothaire

• M. Lothaire (1983), Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. « Encyclopedia of Mathematics and its Applications » (n^o 17), 1983 (ISBN 978-0-201-13516-9, présentation en ligne)
• [Lothaire (1997)] M. Lothaire, Combinatorics on words, Cambridge University Press, coll. « Cambridge Mathematical Library », 1997, 2^e éd., xviii+238 (ISBN 978-0-521-59924-5, DOI 10.1017/CBO9780511566097, MR 1475463, présentation en ligne)

Articles

• [Bean, Ehrenfeucht, McNulty (1979)] Dwight R. Bean, Andrzej Ehrenfeucht et George F. McNulty, « Avoidable patterns in strings of symbols », Pacific J. Math., vol. 85, n^o 2,‎ 1979, p. 261-294 (MR 0574919).
• [Crochemore (1982)] Maxime Crochemore, « Sharp characterizations of squarefree morphisms », Theor. Comput. Sci., vol. 18, n^o 2,‎ 1982, p. 221-226 (DOI 10.1016/0304-3975(82)90023-8, lire en ligne).
• [Brandenburg (1983)] Franz-Joseph Brandenburg, « Uniformly growing k-th power-free homomorphisms », Theor. Comput. Sci., vol. 23,‎ 1983, p. 69-82.

• [Wlazinski (2018)] Francis Wlazinski, « A uniform cube-free morphism is k-power-free for all integers k ≥ 4 », RAIRO - Theoretical Informatics and Applications, vol. 51, n^o 4,‎ 2018, p. 205–216 (ISSN 0988-3754, DOI 10.1051/ita/2017015, HAL hal-01417750)
• [Gabric Shallit (2021)] Daniel Gabric et Jeffrey Shallit, « The simplest binary word with only three squares », RAIRO - Theoretical Informatics and Applications, vol. 55, n^o 3,‎ 2021 (ISSN 0988-3754, DOI 10.1051/ita/2021001, arXiv 2007.08188)

Voir aussi

• Perles de Dijkstra
• La suite de Prouhet-Thue-Morse est sans facteur cubique.
• La suite de Fibonacci est sans facteur biquadratique.

Liens externes

• (en) Eric W. Weisstein, « Squarefree Word », sur MathWorld

• Portail des mathématiques
• Portail de l'informatique théorique