Palabra sin cuadrados

En combinatoria , una palabra sin cuadrados es una palabra (una secuencia de símbolos) que no contiene ningún cuadrado. Un cuadrado es una palabra de la forma XX , donde X no está vacía. Por lo tanto, una palabra sin cuadrados también se puede definir como una palabra que evita el patrón XX .

Palabras finitas sin cuadrados

Alfabeto binario

En un alfabeto binario , las únicas palabras sin cuadrados son las palabras vacías , y . ${\displaystyle \{0,1\}}$ ${\displaystyle \epsilon ,0,1,01,10,010}$ ${\displaystyle 101}$

Alfabeto ternario

En un alfabeto ternario , existen infinitas palabras sin cuadrados. Es posible contar el número de palabras ternarias sin cuadrados de longitud n . ${\displaystyle \{0,1,2\}}$ ${\displaystyle c(n)}$

Este número está acotado por , donde . ^[2] El límite superior de se puede encontrar a través del Lema de Fekete y la aproximación por autómatas . El límite inferior se puede encontrar al encontrar una sustitución que preserve la ausencia de cuadrados. ^[2] ${\displaystyle c(n)=\Theta (\alpha ^{n})}$ ${\textstyle 1.3017597<\alpha <1.3017619}$ ${\displaystyle \alpha }$

Alfabeto con más de tres letras

Dado que hay infinitas palabras sin cuadrados en alfabetos de tres letras, esto implica que también hay infinitas palabras sin cuadrados en un alfabeto con más de tres letras.

La siguiente tabla muestra la tasa de crecimiento exacta de las palabras libres de cuadrados k -arios, redondeadas a 7 dígitos después del punto decimal, para k en el rango de 4 a 15: ^[2]

Palabras bidimensionales

Consideremos una función de a A , donde A es un alfabeto y se denomina palabra bidimensional. Sea la entrada . Una palabra es una línea de si existe tal que , y para . ^[3] ${\displaystyle {\textbf {w}}}$ ${\displaystyle \mathbb {N} ^{2}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle w_{m,n}}$ ${\displaystyle {\textbf {w}}(m,n)}$ ${\displaystyle {\textbf {x}}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle i_{1},i_{2},j_{1},j_{2}}$ ${\displaystyle {\text{gcd}}(j_{1},j_{2})=1}$ ${\displaystyle t\geq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}}$

Carpi ^[4] demuestra que existe una palabra bidimensional sobre un alfabeto de 16 letras, de modo que cada línea de esté libre de cuadrados. Una búsqueda por computadora muestra que no existen palabras bidimensionales sobre un alfabeto de 7 letras, de modo que cada línea de esté libre de cuadrados. ${\displaystyle {\textbf {w}}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle {\textbf {w}}}$

Generando palabras finitas sin cuadrados

Shur ^[5] propone un algoritmo llamado R2F (random-t(w)o-free) que puede generar una palabra sin cuadrados de longitud n sobre cualquier alfabeto con tres o más letras. Este algoritmo se basa en una modificación de la compresión de entropía : selecciona aleatoriamente letras de un alfabeto de k letras para generar una palabra sin cuadrados ⁠ ⁠ -ario. ${\displaystyle (k+1)}$

El algoritmo R2F tiene  como entrada: tamaño del alfabeto , longitud de palabra, salida : una palabra w -aria libre de cuadrados de longitud n . ${\displaystyle k\geq 2}$ ${\displaystyle n>1}$  ${\displaystyle (k+1)}$ (Tenga en cuenta que es el alfabeto con letras ). ${\textstyle \color {gray}\Sigma _{k+1}}$ ${\displaystyle \color {gray}\{1,...,k+1\}}$ (Para una palabra , es la permutación de tal que a precede a b en si el ${\displaystyle \color {gray}w\in \Sigma _{k}}$ ${\displaystyle \color {gray}\chi _{w}}$ ${\displaystyle \color {gray}\Sigma _{k}}$ ${\displaystyle \color {gray}\chi _{w}}$ La posición más a la derecha de a en w está a la derecha de la posición más a la derecha de b en w . Por ejemplo, tiene .) ${\displaystyle \color {gray}w=136263163\in \Sigma _{6}}$ ${\displaystyle \color {gray}\chi _{w}=361245}$ Elija de manera uniforme y aleatoria el conjunto seguido de todas las demás letras de en orden creciente y establezca el número N de iteraciones en 0. ${\displaystyle w[1]}$ ${\textstyle \Sigma _{k+1}}$  ${\displaystyle \chi _{w}}$   ${\displaystyle w[1]}$ ${\textstyle \Sigma _{k+1}}$ mientras que  elige j de manera uniforme y aleatoria ${\displaystyle |w|<n}$  ${\textstyle \Sigma _{k}}$ añadir al final de w actualizar desplazando los primeros j elementos a la derecha y estableciendo el incremento N en 1 si w termina con un cuadrado de rango r entonces eliminar las últimas r letras de w ${\displaystyle a=\chi _{w}[j+1]}$ ${\displaystyle \chi _{w}}$ ${\displaystyle \chi _{w}[1]=a}$    volver  w

Cada palabra libre de cuadrados (k+1)-arios puede ser la salida del algoritmo R2F, porque en cada iteración puede agregar cualquier letra excepto la última letra de w .

El número esperado de letras aleatorias k-arias utilizadas por el algoritmo R2F para construir una palabra ⁠ ⁠ ${\displaystyle (k+1)}$ -aria libre de cuadrados de longitud n es Nótese que existe un algoritmo que puede verificar la ausencia de cuadrados de una palabra de longitud n en el tiempo. Apostolico y Preparata ^[6] dan un algoritmo que utiliza árboles de sufijos. Crochemore ^[7] utiliza particionamiento en su algoritmo. Main y Lorentz ^[8] proporcionan un algoritmo basado en el método divide y vencerás. Una implementación ingenua puede requerir tiempo para verificar la ausencia de cuadrados de una palabra de longitud n . $${\displaystyle N=n\left(1+{\frac {2}{k^{2}}}+{\frac {1}{k^{3}}}+{\frac {4}{k^{4}}}+O\left({\frac {1}{k^{5}}}\right)\right)+O(1).}$$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n^{2})}$

Infinitas palabras sin cuadrados

Existen infinitas palabras sin cuadrados en cualquier alfabeto con tres o más letras, como lo demostró Axel Thue . ^[9]

Ejemplos

Primera diferencia de laSecuencia Thue-Morse

Un ejemplo de una palabra infinita sin cuadrados sobre un alfabeto de tamaño 3 es la palabra sobre el alfabeto obtenido al tomar la primera diferencia de la secuencia de Thue-Morse . ^[9] Es decir, de la secuencia de Thue-Morse ${\displaystyle \{-1,0,+1\}}$

${\displaystyle 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0...}$

Se forma una nueva secuencia en la que cada término es la diferencia de dos términos consecutivos de la secuencia de Thue-Morse. La palabra resultante sin cuadrados es

${\displaystyle 1,0,-1,1,-1,0,1,0,-1,0,1,-1,1,0,-1,...}$(secuencia A029883 en la OEIS ).

Sanguijuela'smorfismo

Otro ejemplo encontrado por John Leech ^[10] se define recursivamente sobre el alfabeto . Sea ⁠ ⁠ cualquier palabra sin cuadrados que comience con la letra ${\displaystyle \{0,1,2\}}$ ${\displaystyle w_{1}}$0 . Defina las palabras recursivamente de la siguiente manera: la palabra se obtiene de ⁠ ⁠ reemplazando cada ${\displaystyle \{w_{i}\mid i\in \mathbb {N} \}}$ ${\displaystyle w_{i+1}}$ ${\displaystyle w_{i}}$0 en ⁠ ⁠ ${\displaystyle w_{i}}$ con0121021201210 , cada uno1 con1202102012021 , y cada2 con2010210120102 . Es posible demostrar que la secuencia converge a la palabra infinita sin cuadrados

0121021201210120210201202120102101201021202102012021...

Generando infinitas palabras sin cuadrados

Se pueden generar infinitas palabras sin cuadrados mediante morfismo sin cuadrados . Un morfismo se denomina sin cuadrados si la imagen de cada palabra sin cuadrados es sin cuadrados. Un morfismo se denomina k-sin cuadrados si la imagen de cada palabra sin cuadrados de longitud k es sin cuadrados.

Crochemore ^[11] demuestra que un morfismo uniforme h es libre de cuadrados si y solo si es 3-libre de cuadrados. En otras palabras, h es libre de cuadrados si y solo si es libre de cuadrados para todo w libre de cuadrados de longitud 3. Es posible encontrar un morfismo libre de cuadrados mediante una búsqueda de fuerza bruta . ${\displaystyle h(w)}$

El algoritmo square-free_morphism tiene  como resultado: un morfismo cuadrado-libre con el rango k más bajo posible . establecer  mientras True establecer k_sf_words a la lista de todas las palabras sin cuadrados de longitud k sobre un alfabeto ternario para cada en k_sf_words hacer para cada en k_sf_words hacer para cada en k_sf_words hacer si entonces romper el bucle actual (avanzar al siguiente ) si y entonces si es sin cuadrados para todos los w sin cuadrados de longitud ${\displaystyle k=3}$      ${\displaystyle h(0)}$      ${\displaystyle h(1)}$      ${\displaystyle h(2)}$      ${\displaystyle h(1)=h(2)}$   ${\displaystyle h(1)}$  ${\displaystyle h(0)\neq h(1)}$   ${\displaystyle h(2)\neq h(0)}$    ${\displaystyle h(w)}$ 3  luego  devuelve el incremento k por ${\displaystyle h(0),h(1),h(2)}$1

En un alfabeto ternario, hay exactamente 144 morfismos uniformes libres de cuadrados de rango 11 y ningún morfismo uniforme libre de cuadrados con un rango inferior a 11.

Para obtener infinitas palabras sin cuadrados, comience con cualquier palabra sin cuadrados como0 , y sucesivamente se le aplica un morfismo h sin cuadrados . Las palabras resultantes conservan la propiedad de no tener cuadrados. Por ejemplo, sea h un morfismo sin cuadrados, entonces como , es una palabra infinita sin cuadrados. ${\displaystyle w\to \infty }$ ${\displaystyle h^{w}(0)}$

Nótese que, si un morfismo sobre un alfabeto ternario no es uniforme, entonces este morfismo es libre de cuadrados si y sólo si es 5-libre de cuadrados. ^[11]

Combinaciones de letras en palabras sin cuadrados

Extender una palabra sin cuadrados para evitar ab .

Evite combinaciones de dos letras

En un alfabeto ternario, una palabra sin cuadrados de longitud superior a 13 contiene todas las combinaciones de dos letras sin cuadrados. ^[12]

Esto se puede demostrar construyendo una palabra sin cuadrados sin la combinación de dos letras ab . Como resultado, bcba cbca cbaca es la palabra sin cuadrados más larga sin la combinación ab y su longitud es igual a 13.

Tenga en cuenta que en un alfabeto de más de tres letras hay palabras sin cuadrados de cualquier longitud sin una combinación arbitraria de dos letras.

Evite combinaciones de tres letras

En un alfabeto ternario, una palabra sin cuadrados de longitud superior a 36 contiene todas las combinaciones de tres letras sin cuadrados. ^[12]

Sin embargo, hay palabras sin cuadrados de cualquier longitud sin la combinación de tres letras aba .

Tenga en cuenta que en un alfabeto de más de tres letras hay palabras sin cuadrados de cualquier longitud sin una combinación arbitraria de tres letras.

Densidad de una letra

La densidad de una letra a en una palabra finita w se define como donde es el número de ocurrencias de a en y es la longitud de la palabra. La densidad de una letra a en una palabra infinita es donde es el prefijo de la palabra w de longitud l . ^[13] ${\displaystyle {\frac {|w|_{a}}{|w|}}}$ ${\displaystyle |w|_{a}}$ ${\displaystyle w}$ ${\displaystyle |w|}$ ${\displaystyle \liminf _{l\to \infty }{\frac {|w_{l}|_{a}}{|w_{l}|}}}$ ${\displaystyle w_{l}}$

La densidad mínima de una letra a en una palabra ternaria infinita sin cuadrados es igual a . ^[13] ${\displaystyle {\frac {883}{3215}}\approx 0.2747}$

La densidad máxima de una letra a en una palabra ternaria infinita sin cuadrados es igual a . ^[14] ${\displaystyle {\frac {255}{653}}\approx 0.3905}$

Notas

1. "A006156 - OEIS". oeis.org . Consultado el 28 de marzo de 2019 .
2. Shur, Arseny (2011). "Propiedades de crecimiento de lenguajes sin potencia". Computer Science Review . 6 (5–6): 28–43. doi :10.1016/j.cosrev.2012.09.001.
3. Berthe, Valerie; Rigo, Michel, eds. (2016), "Prefacio", Combinatoria, palabras y dinámica simbólica , Cambridge University Press, págs. xi–xviii, doi :10.1017/cbo9781139924733.001, ISBN 9781139924733
4. Carpi, Arturo (1988). "Configuraciones no repetitivas multidimensionales". Ciencias Informáticas Teóricas . 56 (2): 233–241. doi : 10.1016/0304-3975(88)90080-1 . ISSN  0304-3975.
5. Shur, Arseny (2015). "Generación eficiente de palabras sin cuadrados". Ciencias Informáticas Teóricas . 601 : 67–72. doi : 10.1016/j.tcs.2015.07.027 . hdl : 10995/92700 .
6. Apostolico, A.; Preparata, FP (febrero de 1983). "Detección óptima fuera de línea de repeticiones en una cadena". Ciencias de la Computación Teórica . 22 (3): 297–315. doi : 10.1016/0304-3975(83)90109-3 . ISSN  0304-3975.
7. Crochemore, Max (octubre de 1981). "Un algoritmo óptimo para calcular las repeticiones en una palabra". Information Processing Letters . 12 (5): 244–250. doi :10.1016/0020-0190(81)90024-7. ISSN  0020-0190.
8. Main, Michael G; Lorentz, Richard J (septiembre de 1984). "Un algoritmo O(n log n) para encontrar todas las repeticiones en una cadena". Journal of Algorithms . 5 (3): 422–432. doi :10.1016/0196-6774(84)90021-x. ISSN  0196-6774.
9. Berstel, Jean (1994). "Los artículos de Axel Thue sobre repeticiones en palabras y una traducción" . Departamentos de Matemáticas e Informática, Universidad de Québec en Montreal. ISBN 978-2892761405. OCLC  494791187.
10. Leech, J. (1957). "Un problema sobre hilos de cuentas". Math. Gaz . 41 : 277–278. doi :10.1017/S0025557200236115. S2CID  126406225. Zbl  0079.01101.
11. Berstel, Jean (abril de 1984). "Algunos resultados recientes sobre palabras sin cuadrados". Simposio anual sobre aspectos teóricos de la informática . Apuntes de clase sobre informática. 166 : 14–25. doi :10.1007/3-540-12920-0_2. ISBN 978-3-540-12920-2.
12. Zolotov, Boris (2015). "Otra solución al problema de Thue de palabras no repetidas". arXiv : 1505.00019 [math.CO].
13. Khalyavin, Andrey (2007). "La densidad mínima de una letra en una palabra ternaria infinita sin cuadrados es 883/3215" (PDF) . Journal of Integer Sequences . 10 (2): 3. Bibcode :2007JIntS..10...65K.
14. Ochem, Pascal (2007). "Frecuencia de letras en palabras infinitas sin repetición". Ciencias Informáticas Teóricas . 380 (3): 388–392. doi :10.1016/j.tcs.2007.03.027. ISSN  0304-3975.

Referencias

• Berstel, Jean ; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras. Serie monográfica CRM. Vol. 27. Providence, RI: American Mathematical Society . ISBN. 978-0-8218-4480-9.Zbl 1161.68043  .
• Lothaire, M. (1997). Combinatoria de palabras . Cambridge: Cambridge University Press . ISBN. 978-0-521-59924-5..
• Lothaire, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 90. Con prólogo de Jean Berstel y Dominique Perrin (reimpresión de la edición de tapa dura de 2002). Cambridge University Press . ISBN 978-0-521-18071-9.Zbl 1221.68183  .
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, Anne (eds.). Sustituciones en dinámica, aritmética y combinatoria . Lecture Notes in Mathematics. Vol. 1794. Berlín: Springer-Verlag . ISBN. 978-3-540-44141-0.Zbl 1014.11015  .