Mot sans facteur carré

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Article principal : Combinatoire des mots.

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.

Premiers exemples[modifier | modifier le code]

Sur un alphabet à deux lettres, il n'existe que six mots sans carré non vides. Sur l'alphabet , ce sont les mots .

Sur un alphabet à trois lettres , on peut partir de la lettre , et remplacer

  • par ,
  • par ,
  • par .

On obtient successivement

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.[3].

Dans la terminologie des répétitions, les carrés sont inévitables sur 2 lettres, mais évitables sur plus de 2 lettres.

Autres exemples[modifier | modifier le code]

Plusieurs auteurs ont, de façon indépendante, retrouvé les premières constructions de Thue 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) étaient publiés dans un journal peu connu, et n'ont donc pas été largement reconnus.

Les constructions de Thue (1906)[modifier | modifier le code]

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 , et on insère la lettre entre deux lettres du mot, à 4 places 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ée 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 :

En partant de a, on obtient

.

La construction de Thue (1912)[modifier | modifier le code]

Dans son long article[2], Axel Thue cherche, mais sans y parvenir, à classer toutes les suites sans carré. 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 ce nombre 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.

Cette construction a été retrouvée en 1963 par C. H. Braunholtz[4].

La suite asymétrique d'Arshon (1937)[modifier | modifier le code]

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 :

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)[modifier | modifier le code]

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

.

Ils remplacent deux digits consécutifs par le nombre qu'il 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)[modifier | modifier le code]

Ces deux auteurs proposent[7] 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)[modifier | modifier le code]

Dans une courte note[8], 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 a, 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 a soit a etc. On prend donc

L'itération donne :

La construction de Zech (1958)[modifier | modifier le code]

Theodor Zech[9] 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)[modifier | modifier le code]

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 , 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 mot 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.

Extension aux graphes[modifier | modifier le code]

Le nombre de Thue (en) 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é.

Nombre de mots sans carré[modifier | modifier le code]

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

Notons le nombre de mots sans carré de longueur sur un alphabet à lettres. On sait depuis longtemps que croît exponentiellement pour . On connaît maintenant[11] un très bon encadrement pour ces valeurs. On a par exemple :

Notes et références[modifier | modifier le code]

  1. a et b A. Thue, Über unendliche Zeichenreihen, Norske Vid. Skrifter I Mat.- Nat. Kl., Christiania 7 (1906) 1–22.
  2. a et b A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1–67.
  3. Marshall Hall Jr., « Generators and relations in groups - The Burnside problem, », dans Lectures on Modern Mathematics, t. II, , p. 42-92
  4. C. H. Braunholtz, « An infinite sequence of 3 symbols with no adjacent repeats », American Math. Monthly, vol. 70,‎ , p. 675-676.
  5. C. E. Arshon, « Démonstration de l'existence de suites asymétriques infinies (en russe avec un long résumé en français) », Mat. Sbornik, vol. 2,‎ , p. 769-779.
  6. Marston Morse et Gustav Hedlund, « Unending chess, symbolic dynamics and a problem in semigroups », Duke Math. Journal, vol. 11,‎ , p. 1-7.
  7. David Hawkins et Walter E. Mientka, « On sequences which contain no repetitions », Math. Student, vol. 24,‎ , p. 185-187.
  8. C'est la Mathematical Note n° 2726: John Leech, « A problem on strings of beads », The Mathematical Gazette, vol. 41,‎ , p. 277– 278. Un peu plus tard, J. C. Shepherdson, dans : « A Historical Note on Note 2726 », Math. Gazette, vol. 42, no 342,‎ , p. 306 rappelle l'existence des articles de Thue, et que Thue aussi a considéré des mots sans carré bilatères.
  9. Theodor Zech, « Wiederholungsfreie Folgen », Z. angew. Math. Mech., vol. 38, no 5/6,‎ , p. 206-209.
  10. Richard A. Dean, « A sequence without repeats on  », American Math. Monthly, vol. 72,‎ , p. 383-385.
  11. Arseny M. Shur, « Growth Properties of Power-Free Languages », dans Giancarlo Mauri et Alberto Leporati (éditeurs), Developments in Language Theory - 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 6795), , p. 28-43


Bibliographie[modifier | modifier le code]

  • M. Lothaire (1983), Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. « Encyclopedia of Mathematics and its Applications » (no 17), (ISBN 978-0-201-13516-9, présentation en ligne)
    Une seconde édition révisée est parue chez Cambridge University Press, dans la collection Cambridge Mathematical Library, en 1997, ISBN 978-0521599245.
  • Trygve Nagell, Atle Selberg, S. Selberg et K. Thalberg (éditeurs), Selected Mathematical Papers of Axel Thue, Oslo, Norvège, Universitetsforlaget, pp. 139—158, 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.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]