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... 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 un 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 , il n'existe que six mots sans carré non vides : ce sont les mots .
Sur un alphabet à trois lettres , et partant de la lettre , on remplace par , par , par . On alors obtient successivement
En itérant et en prenant le point fixe de cette opération, on obtient le mot infini qui commence par . Ce mot est sans carré. Cette construction est donnée par Marshall Hall Jr.. 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 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 , et on insère la lettre entre deux lettres du mot, à différentes. Ces 4 mots sont pris pour définir un morphisme :
En itérant à partir de la lettre a, on obtient le mot infini (les barres verticales sont censées faciliter la lecture) : . Le symbole 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 , les lettres selon les règles suivantes :
si la lettre avant est si la lettre avant est En partant de a, on obtient .
La construction de Thue (1912) Dans son long article, 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 :
. Il observe que, comme il n'y a pas de bloc dans la suite, deux symboles consécutifs sont séparés par 0, 1, ou 2 symboles . Il suffit de reporter la séquence de ces nombres pour obtenir une suite sur trois symboles : . En remplaçant par , par et par , 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.
Autres constructions
La suite asymétrique d'Arshon (1937) Dans un article en russe 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 :
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
Le premier est en position impaire 1, et il produit , le en position 2 produit , et le troisième symbole, en position impaire, produit . On obtient la suite (les barres verticales doivent améliorer la lisibilité) :
On continue : le en position 4 produit , le en position 5 produit , le en position 6 produit , etc. On construit ainsi une suite débutant par :
Arshon prouve que ce mot est sans carré. Cette suite est 3-automatique : on prend le morphisme sur 6 lettres donné par . Ce morphisme 3-uniforme engendre le mot infini
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, Morse et Hedlund partent, comme Thue, de la suite de Prouhet-Thue-Morse : .
Contrairement à Thue, ils remplacent deux bits consécutifs par le nombre qu'ils représentent en binaire, soit
puis ils identifient et (en d'autres termes, ils opèrent modulo 3). La suite obtenue est : . 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 :
et en identifiant ensuite et . 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 le morphisme suivant :
et ils prouvent qu'en itérant à partir de la lettre , on obtient un mot infini sans carré. Les perles de John Leech (1957) Dans une courte note, John Leech propose la construction suivante. On itère le morphisme défini par
L'image de chaque lettre est le mot transformé par . En itérant à partir de , on obtient
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 soit etc. On prend donc
L'itération donne :
La construction de Zech (1958) Theodor Zech donne le morphisme
Le mot infini est obtenu en itérant à partir de par exemple. La preuve est facilitée par le fait que les trois images se terminent toutes par .
La construction sans simplification de Dean (1963) Richard Dean 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 , la suite ne contient pas les blocs , , et . Pour simplifier l'exposé, Dean choisit les symboles et construit une suite sans carré sans les facteurs . 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 obtenue comme suite: On pose . Chaque est un mot de longueur qui est factorisé en quatre mots de longueur notés de sorte que . Le mot est défini par . On obtient
En fait, on se convainc très vite que les mots s'obtiennent en itérant, à partir de , le morphisme
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.. 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 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 est un tel morphisme, on construit une suite de mots sans carré en partant d'une lettre , et appliquant le morphisme indéfiniment : . Si les mots deviennent de plus en plus long, et si de plus le mot commence par , le mot infini, souvent noté
dont tous les sont préfixes, est un mot infini sans carré. Plus généralement, un morphisme sans puissance -ième est un morphisme qui préserve les mots sans puissances -ième et à nouveau, le mot infini est sans puissance -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 est infixe si aucun mot n'est facteur d'un mot , pour deux lettres . Une démonstration est donnée par Bean, Ehrenfeucht et McNulty., et aussi par Lothaire..
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 défini par
préserve les mots sans carré de longueur au plus 4, mais
contient le carré . 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 défini par , où est un mot sans carré de longueur sur les trois lettres . Le mot est un mot sans carré, de longueur , et contient un carré, donc n’est pas un morphisme sans carré. Mais on peut vérifier que préserve les mots sans carré de longueur .
Exemples
Les morphismes et donnés par
et
sont tous deux sans carré. 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. 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 puissances supérieures.
Le morphisme de Prouhet-Thue-Morse
est sans puissance -ième pour tout k>2.
Le morphisme de Fibonacci
engendre le mot de Fibonacci . Ce mot est sans puissance -ième (k≥4), mais le morphisme de Fibonacci lui-même n'est pas un morphisme sans puissance puisque
Un exemple de Bean, Ehrenfeucht et McNulty ; le morphisme défini par
est sans carré mais n'est pas sans cube.
L'existence de morphismes sans puissance a été prouvée : 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 -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.
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« Transition Property For Cube-Free Words », déposé sur Arxiv le 28 décembre 2018..