Théorème de Dejean

Un carré est un mot de la forme xx, où x est un mot non vide. On peut aussi l'écrire sous la forme x². Un exemple de carré en français est le mot chercher. Un cube est un mot de la forme xxx[1].

Plus généralement, un mot w est une puissance d'exposant fractionnaire p/q s'il s'écrit sous la forme w=x^ky où y est un préfixe de x, et où la longueur de w est égale à p/q fois la longueur de x. Par exemple, le mot entente est une puissance 7/3, car il peut être écrit sous la forme (ent)2e. Le nombre rationnel p/q est appelé l'exposant, la longueur (du plus court) mot x est la période. Une répétition dont l'exposant est plus grand que 1 et plus petit que 2 est aussi appelé une sesquipuissance. Par exemple, le mot template est une sesquipuissance de période 5, d’exposant 7/5, et abaababaa=abaab^9/5 est une sesquipuissance, et contient d'autres répétitions en facteur, comme le carré aa ou abaabaab (d'exposant 8/3) ou ababa (d'exposant 5/2).

En 1906 et 1912, le mathématicien norvégien Axel Thue a donné un exemple d'un mot infini sur deux lettres de l'alphabet ne contenant pas de cubes et d'un mot infini sur 3 lettres ne contenant pas de carré. Il est facile de voir qu'il n'y a pas de mot infini sans carré sur 2 lettres, ou sans cube sur une lettre.

Plus généralement, on peut essayer d'éviter les puissances rationnelles, et pas seulement des puissances entières. Le théorème de Dejean concerne le plus grand exposant possible e tel qu'il n'existe aucun mot infini sur un alphabet à k lettres de l'alphabet qui évite les puissances d'exposant e ou plus. Cet exposant est noté RT(k) ; le sigle RT signifie « seuil de répétition » et provient de l'anglais « repetition threshold ». Le résultat de Thue peut se reformuler en : RT(2) = 2, car tout mot assez long contient un carré, et il existe des mots infinis (le mot de Thue-Morse par exemple) dont aucun facteur est une puissance >2.

En 1972, Françoise Dejean[2] démontre que RT(3) = 7/4. En d'autres termes, sur un alphabet à trois lettres, tout mot assez long (et Françoise Dejean a vérifié que tout mot de longueur 39 est de cette nature) contient une répétition d'exposant 7/4 ou plus, et il existe un mot infini sur trois lettres dont aucun facteur a un exposant > 7/4. Dans le même travail, elle conjecture que RT(4) = 7/5 (résultat prouvé par Pansiot en 1984) et que RT(k) = k/(k-1) pour k ≥ 5. C'est cette dernière affirmation qui est la véritable conjecture de Dejean, restée ouverte si longtemps, et qui a été démontrée en 2009, devenant le théorème de Dejean. En résumé, on a:

Un mot infini qui atteint ce seuil de répétition est appelé mot de Dejean[3].

Le premier résultat, après celui de Françoise Dejean elle-même, est dû à Jean-Jacques Pansiot[4] qui montre que RT(4) = 7/5. Moulin Ollagnier[5] a prouvé la conjecture pour 5 ≤ k ≤ 11 ; Mohammad-Noori et Currie l'ont prouvé pour 12 ≤ k ≤ 14. Une véritable percée est intervenue quand Carpi[6] a prouvé la conjecture pour tout k ≥ 33. Currie et Rampersad ont ensuite raffiné la construction de Carpi pour l'étendre à k ≥ 27. Ensuite, ils ont utilisé les techniques de Moulin Ollagnier pour résoudre les cas restants 15 ≤ k ≤ 26[7]. Par une autre technique, et presque simultanément, une preuve des cas restants, cette fois-ci pour 9 ≤ k ≤ 38, a été donnée par Michaël Rao[8]^,[9]. Une présentation succincte est donnée dans Berthé et Rigo 2015, Section 4.3 : Dejean's Theorem.

Un mot infini sur un alphabet de k lettres qui atteint le seuil de répétition RT(k) du théorème de Dejean est appelé un mot de Dejean[3]. Un facteur (fini) d'un mot dont l'exposant est exactement RT(k) est une répétition limite[3].

Chaque mot de Dejean possède des facteurs qui atteignent le seuil de répétition (bien sûr sans le dépasser !). On peut se demander quels sont les répétitions limite , et s'il y en a beaucoup dans un mot de Dejean.

Notons ${\displaystyle S^{(k)}(n)}$ le nombre de mots répétitions limite de longueur n sur un alphabet à k lettres[10], et

${\displaystyle \gamma (k)=\lim _{n\to \infty }{\sqrt[{n}]{S^{(k)}(n)}}}$.

Le cas binaire est le mieux connu, et différent des autres : on a RT(2)=2, et tout mot infini qui atteint ce seuil (i. e. contient des carrés mais pas de puissance d’ordre supérieure) est un mot sans chevauchement ; il contient une infinité de carrés. La croissance des mots sans chevauchement est polynomial [11] et donc γ(2)=0. On sait mieux : la fonction qui compte le nombre de mots binaires sans chevauchement est une fonction 2-régulière, comme il a été prouvé par Arturo Carpi en 1993[12]. Pour les autres valeurs de k, la croissance est exponentielle, comme prouvé pour k = 3,4 par Pascal Ochem[13] et pour 5 ≤ k ≤ 10 par Kolpakov et Rao[10]. Les estimations de Kolpakov et Rao de γ(k) pour 5 ≤ k ≤ 10 le sont avec une précision de 0.005.

Badkobeh, Crochemore et Yao[3] introduisent un autre seuil, noté FRT pour finite repetition threshold, pour désigner le plus petit seuil de répétition pour lequel il existe un mot infini ne contenant qu'un nombre fini de répétitions limite différents. Cette notion rend compte de la particularité du cas binaire : on a en effet FRT(2)=7/3. Il existe un mot binaire sans répétition d’exposant >7/3, et qui ne contient qu’un nombre fini de facteur d’exposant 7/3. Un tel mot est donné par Badkobeh et Crochemore[14]. Il a la propriété de ne contenir que deux facteurs d’exposant 7/3, et de plus seulement 12 carrés (une énumération montre que c'est la plus petite valeur possible), dont le plus long a longueur 16.

Les preuves de la conjecture de Dejean construisent en fait des mots pour lesquels le FRT coïncide avec le RT. On peut essayer de rendre le nombre fini de facteur d'exposant RT le plus petit possible :

Ainsi, il existe un mot infini sur un alphabet à 4 lettres qui ne contient pas de puissance d’exposant strictement plus grand que 7/5, et qui ne contient que deux facteurs qui sont des puissances d’exposant exactement 7/5. Les mots construits dans les autres preuves, celle de Pansiot et celle de Rao, contiennent chacun 24 puissances d’exposant 7/5. Sur un alphabet à 5 lettres, la preuve de Moulin Ollagnier fournit un mot qui a 360 puissances d’exposant 5/4 (dont les périodes sont 4, 12, et 44). Badkobeh, Crochemore et Yao[3] montrent que l’on peut réduire ce nombre à 60 (tous de période 4) ; ils conjecturent que l’on peut réduire ce nombre à 45, qui est le plus petit nombre possible. Chacun de ces mots donne une nouvelle preuve du seuil de répétition pour un alphabet à 4 respectivement 5 lettres.

• Françoise Dejean, « Sur un théorème de Thue », Journal of Combinatorial Theory, vol. 13, n^o 1,‎ 1972, p. 90-99.
• Jean-Jacques Pansiot, « À propos d'une conjecture de F. Dejean sur les répétitions dans les mots », Discrete Applied Mathematics, vol. 7,‎ 1984, p. 297-331.
• Jean Moulin Ollagnier, « Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters », Theoretical Computer Science, vol. 95, n^o 2,‎ mars 1992, p. 187-205 (DOI 10.1016/0304-3975(92)90264-g).
• Arturo Carpi, « On Dejean’s conjecture over large alphabets », Theoretical Computer Science, vol. 385, n^os 1-3,‎ octobre 2007, p. 137-151 (DOI 10.1016/j.tcs.2007.06.001).
• (en) Arseny M. Shur et Irina A. Gorbunova, « On the growth rates of complexity of threshold languages », RAIRO - Theoretical Informatics and Applications, vol. 44, n^o 1,‎ 2010, p. 175–192 (DOI 10.1051/ita/2010012)
• Michaël Rao, « Last cases of Dejean’s conjecture », Theoretical Computer Science, vol. 412, n^o 27,‎ juin 2011, p. 3010-3018 (DOI 10.1016/j.tcs.2010.06.020, lire en ligne). - Version courte dans les actes du colloque Words en 2009
• James Currie et Narad Rampersad, « A proof of Dejean’s conjecture », Mathematics of Computation, American Mathematical Society (AMS), vol. 80, n^o 274,‎ 2011, p. 1063-1070 (DOI 10.1090/s0025-5718-2010-02407-x).
• Roman Kolpakov et Michaël Rao, « On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters », Theoretical Computer Science, vol. 412, n^o 46,‎ 2011, p. 6507–6516 (DOI 10.1016/j.tcs.2011.08.006, arXiv 1105.3116)
• (en) Golnaz Badkobeh et Maxime Crochemore, « Fewest repetitions in infinite binary words », RAIRO - Theoretical Informatics and Applications, vol. 46, n^o 1,‎ 2011, p. 17–31 (DOI 10.1051/ita/2011109).
• Golnaz Badkobeh, Maxime Crochemore et Michaël Rao, « Finite repetition threshold for large alphabets », RAIRO-Theor. Inf. Appl., EDP Sciences, vol. 48, n^o 4,‎ 2014, p. 419-430 (DOI 10.1051/ita/2014017, Math Reviews 3302495, zbMATH 1302.68223, lire en ligne)
• Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, words and symbolic dynamics, Cambridge, Royaume Uni, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 159), mars 2016, 496 p. (ISBN 978-1-107-07702-7, lire en ligne)

• Mot sans carré
• Motif inévitable

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