Mot sans facteur carré

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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é.

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 \{a,b\}, ce sont les mots a,b,ab,ba,aba,bab.

- Sur un alphabet à trois lettres A=\{a,b,c\}, on peut partir de la lettre a, et remplacer

  • a par abc,
  • b par ac,
  • c par b.

On obtient successivement

\begin{array}{l}a\\abc\\abc acb\\abc acb abc bac\end{array}

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

abc acb abc bac abc acb aca bcb\cdots.

Ce mot est sans carré. Cette construction est donnée par Marshall Hall Jr.[3].

Autres exemples[modifier | modifier le code]

Plusieurs auteurs ont, de façon indépendante, retrouvé les premières constructions de Thue ou 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 abacbc, et on insère la lettre d entre deux lettres du mot, à 4 places différentes. Ces 4 mots sont pris pour définir un morphisme :

\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) :

adbacbc|abacdbc|abdacbc|adbacbc|abadcbc|abdacbc|abadcbc\cdots.

Le symbole d 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 a, b, c, les lettres selon les règles suivantes :

\begin{array}{l}
  a\mapsto abac \\
  b\mapsto babc\\
  c\mapsto bcac\quad\text{si la lettre avant}\ c\ \text{est}\ a \\
  d\mapsto acbc\quad\text{si la lettre avant}\ c\ \text{est}\ b
\end{array}

En partant de a, on obtient

abac|babc|abac|bcac|\cdots.

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 :

0110 1001 1001 0110 1001 0110 0110 1001\cdots.

Il observe que, comme il n'y a pas de bloc 111 dans la suite, deux symboles 0 consécutifs sont séparés par 0, 1, ou 2 symboles 1. Il suffit de reporter ce nombre pour obtenir une suite sur trois symboles :

210 201 210 120 210\cdots.

En remplaçant 2 par a, 1 par b et 0 par c, 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 :

\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

123

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

123|132|312

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

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 \{1,2,3,\bar1,\bar2,\bar3\} donné par

\begin{array}{l}
  1\mapsto 1\bar 23 \\2\mapsto 2\bar 31\\3\mapsto 3\bar 12
\end{array}\qquad\begin{array}{l}
  \bar 1\mapsto \bar 32\bar 1 \\\bar 2\mapsto \bar 13\bar 2\\\bar 3\mapsto \bar 21\bar 3
\end{array}.

Ce morphisme 3-uniforme engendre le mot infini

1\bar 23|\bar 13\bar 2|3\bar 12|\bar 32\bar 1|3\bar 12|\bar 13\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)[modifier | modifier le code]

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

0110 1001 1001 0110 1001 0110 0110 1001\cdots.

Ils remplacent deux digits consécutifs par le nombre qu'il représentent en binaire, soit

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

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

102 1201 0201 2102\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 :

\begin{array}{l}
  0\mapsto03 \\
  1\mapsto20\\
  2\mapsto21\\
  3\mapsto02
\end{array}

et en identifiant ensuite 0 et 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)[modifier | modifier le code]

Ces deux auteurs proposent[7] le morphisme suivant :

\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 b, 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

\begin{array}{l}
  a\mapsto abc bac bca bcb a \\
  b\mapsto bca cba cab cac b\\
  c\mapsto cab acb abc aba c
\end{array}

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

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 a soit a etc. On prend donc

\begin{array}{l}
  a\mapsto cab acb abc aba c\\
  b\mapsto abc bac bca bcb a\\
  c\mapsto bca cba cab cac b
\end{array}

L'itération donne :

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

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

Theodor Zech[9] donne le morphisme

\begin{array}{l}
  a\mapsto abc aba cba bcb \\
  b\mapsto acb cab aca bcb\\
  c\mapsto aca bac bca bcb
\end{array}

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

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 x,x^{-1}, y, y^{-1}, la suite ne contient pas les blocs xx^{-1}, x^{-1}x, yy^{-1} et y^{-1}y. Pour simplifier l'exposé, Dean choisit les symboles 1,2,3,4 et construit une suite sans carré sans les facteurs 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 des la suite de mots (w_n) obtenue comme suite: On pose w_0=1234. Chaque w_n est un mot de longueur 2^{n+2} qui est factorisé en quatre mot de longueur 2^n notés A_n,B_n,C_n,D_n de sorte que

w_n=A_nB_nC_nD_n.

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

w_{n+1}=w_nA_nD_nC_nB_n.

On obtient

\begin{array}{l}
  w_0=1234 \\
  w_1=12341432\\
  w_2=1234 1432 1232 1434\\
  w_3=1234 1432 1232 1434 1234 1434 1232 1432
\end{array}

En fait, on se convainc très vite que les mots w_n s'obtiennent en itérant, à partir de 1, le morphisme

\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.

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 :
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 :
4, 12, 36, 96, 264, 696, \ldots

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

1,301759^n<c_3(n)<1,301761^n

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,‎ 1964, p. 42-92
  4. C. H. Braunholtz, « An infinite sequence of 3 symbols with no adjacent repeats », American Math. Monthly, vol. 70,‎ 1963, 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,‎ 1937, p. 769-779.
  6. Marston Morse et Gustav Hedlund, « Unending chess, symbolic dynamics and a problem in semigroups », Duke Math. Journal, vol. 11,‎ 1944, p. 1-7.
  7. David Hawkins et Walter E. Mientka, « On sequences which contain no repetitions », Math. Student, vol. 24,‎ 1956, p. 185-187.
  8. C'est la Mathematical Note n° 2726: John Leech, « A problem on strings of beads », The Mathematical Gazette, vol. 41,‎ 1957, p. 277– 278. Un peu plus tard, J. C. Shepherdson, dans : « A Historical Note on Note 2726 », Math. Gazette, vol. 42, no 342,‎ 1958, 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,‎ 1958, p. 206-209.
  10. Richard A. Dean, « A sequence without repeats on x, x^{-1}, y, y^{-1} », American Math. Monthly, vol. 72,‎ 1965, 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),‎ 2011, 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),‎ 1983 (ISBN 978-0-201-13516-9, résumé)
    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.,‎ 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]