|
Théorème de DejeanEn combinatoire et notamment en combinatoire des mots, le théorème de Dejean, appelé la conjecture de Dejean avant d'avoir été démontré, concerne les répétitions d'exposant fractionnaire dans les mots infinis. La conjecture a été formulée en 1972 par Françoise Dejean qui alors travaillait avec Marcel-Paul Schützenberger, et elle a été démontrée en 2009, presque simultanément, par James D. Currie et Narad Rampersad d'une part, par Michaël Rao d'autre part. Puissances fractionnairesUn carré est un mot de la forme xx, où x est un mot non vide. On peut aussi l'écrire sous la forme x2. Un exemple de carré en français est le mot Plus généralement, un mot w est une puissance d'exposant fractionnaire p/q s'il s'écrit sous la forme w=xky 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 Seuil de répétitionEn 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. Théorème de DejeanEn 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 longtemps, et démontrée en 2009, devenant le théorème de Dejean. En résumé, on a: Théorème de Dejean — Le seuil de répétition RT(k) prend les valeurs suivantes :
Un mot infini qui atteint ce seuil de répétition est appelé mot de Dejean[3]. Historique de la preuveLe 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. Mot de DejeanUn 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 le nombre de mots répétitions limite de longueur n sur un alphabet à k lettres[10], et
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. Notes et références
Bibliographie
Articles liés |
![{\displaystyle \gamma (k)=\lim _{n\to \infty }{\sqrt[{n}]{S^{(k)}(n)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3470ea58d0aa4abfcb45b4709de9825a4af717a)
