Teorema de Dejean

El teorema de Dejean (anteriormente conjetura de Dejean ) es una afirmación sobre repeticiones en cadenas infinitas de símbolos . Pertenece al campo de la combinatoria de palabras ; fue conjeturado en 1972 por Françoise Dejean y demostrado en 2009 por Currie y Rampersad y, de forma independiente, por Rao. ^{[ 1 ]}

En el estudio de cadenas, la concatenación se considera análoga a la multiplicación de números. Por ejemplo, si${\displaystyle s}$es cualquier cadena, entonces la concatenación${\displaystyle ss}$de dos copias de${\displaystyle s}$se llama el cuadrado de${\displaystyle s}$y denotado${\displaystyle s^{2}}$. Esta notación exponencial también puede extenderse a potencias fraccionarias: si${\displaystyle s}$tiene longitud${\displaystyle \ell }$, y${\displaystyle e}$es un número racional no negativo de la forma${\displaystyle n/\ell }$, entonces${\displaystyle s^{e}}$denota la cadena formada por el primero${\displaystyle n}$caracteres de la repetición infinita${\displaystyle sssss\dots }$. ^{[ 1 ]}

Una palabra libre de cuadrados es una cadena que no contiene ningún cuadrado como subcadena. En particular, evita repetir el mismo símbolo consecutivamente, repetir el mismo par de símbolos, etc. Axel Thue demostró que existe una palabra infinita libre de cuadrados utilizando un alfabeto de tres símbolos, la secuencia de diferencias entre elementos consecutivos de la secuencia Thue-Morse . Sin embargo, no es posible que una palabra infinita de dos símbolos (o incluso una palabra de dos símbolos de longitud mayor que tres) esté libre de cuadrados. ^{[ 1 ]}

Sin embargo, para alfabetos de dos símbolos, existen infinitas palabras libres de cubos, palabras sin ninguna subcadena de la forma${\displaystyle sss}$Un ejemplo de ello es la secuencia de Thue-Morse ; otro es la secuencia de Kolakoski . Más aún, la secuencia de Thue-Morse no contiene ninguna subcadena que sea una potencia estrictamente mayor que dos. ^{[ 1 ]}

En 1972, Dejean investigó el problema de determinar, para cada tamaño de alfabeto posible, el umbral entre exponentes.${\displaystyle e}$para el cual existe un infinito${\displaystyle e}$-palabra sin potencia, y los exponentes para los cuales no existe tal palabra. El problema fue resuelto para alfabetos de dos símbolos por la secuencia de Thue-Morse, y Dejean también lo resolvió para alfabetos de tres símbolos. Ella conjeturó una fórmula precisa para el exponente umbral para cada tamaño de alfabeto mayor; ^{[ 2 ]} esta fórmula es la conjetura de Dejean, ahora un teorema. ^{[ 1 ]}

Dejar${\displaystyle k}$sea ​​el número de símbolos en un alfabeto. Para cada${\displaystyle k}$, definir${\displaystyle \operatorname {RT} (k)}$, el umbral de repetición , para ser el ínfimo de exponentes${\displaystyle e}$tal que existe un infinito${\displaystyle e}$-palabra sin poder en un${\displaystyle k}$alfabeto de símbolos. Así, por ejemplo, la secuencia Thue-Morse muestra que${\displaystyle \operatorname {RT} (2)=2}$, and an argument based on the Lovász local lemma can be used to show that ${\displaystyle \operatorname {RT} (k)}$ is finite for all ${\displaystyle k}$.^[1]

Then Dejean's conjecture is that the repeat threshold can be calculated by the simple formula^[1][2]

${\displaystyle \operatorname {RT} (k)={\frac {k}{k-1}}}$

except in two exceptional cases:

${\displaystyle \operatorname {RT} (3)={\frac {7}{4}}}$

and

${\displaystyle \operatorname {RT} (4)={\frac {7}{5}}.}$

Dejean herself proved the conjecture for ${\displaystyle k=3}$.^[2] The case ${\displaystyle k=4}$ was proven by Jean-Jacques Pansiot in 1984.^[3] The next progress was by Moulin Ollagnier in 1992, who proved the conjecture for all alphabet sizes up to ${\displaystyle k\leq 11}$.^[4] This analysis was extended up to ${\displaystyle k\leq 14}$ in 2007 by Mohammad-Noori and Currie.^[5]

In the other direction, also in 2007, Arturo Carpi showed the conjecture to be true for large alphabets, with ${\displaystyle k\geq 33}$.^[6] This reduced the problem to a finite number of remaining cases, which were solved in 2009 and published in 2011 by Currie and Rampersad^[7] and independently by Rao.^[8]

An infinite string that meets Dejean's formula (having no repetitions of exponent above the repetition threshold) is called a Dejean word. Thus, for instance, the Thue–Morse sequence is a Dejean word.