Palabra sin cuadrados

Sobre un alfabeto binario${\displaystyle \{0,1\}}$, las únicas palabras libres de cuadrados son la palabra vacía${\displaystyle \epsilon ,0,1,01,10,010}$, y${\displaystyle 101}$.

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

Este número está acotado por${\displaystyle c(n)=\Theta (\alpha ^{n})}$, dónde${\textstyle 1.3017597<\alpha <1.3017619}$. ^{[ 2 ]} El límite superior en${\displaystyle \alpha }$Se puede encontrar mediante el lema de Fekete y la aproximación por autómatas . La cota inferior se puede encontrar hallando una sustitución que preserve la ausencia de cuadrados. ^{[ 2 ]}

Dado que existen infinitas palabras libres de cuadrados sobre alfabetos de tres letras, esto implica que también existen infinitas palabras libres de cuadrados sobre un alfabeto con más de tres letras.

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

Shur ^{[ 5 ]} propone un algoritmo llamado R2F (random-t(w)o-free) que puede generar una palabra libre de 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 ⁠${\displaystyle (k+1)}$-aria palabra sin cuadrados.

El algoritmo R2F es la entrada: tamaño del alfabeto${\displaystyle k\geq 2}$longitud de palabra${\displaystyle n>1}$Salida : a${\displaystyle (k+1)}$⁠ Palabra libre de cuadrados -arios w de longitud n . (Tenga en cuenta que${\textstyle \color {gray}\Sigma _{k+1}}$es el alfabeto con letras${\displaystyle \color {gray}\{1,...,k+1\}}$.) (Por una palabra)${\displaystyle \color {gray}w\in \Sigma _{k}}$,${\displaystyle \color {gray}\chi _{w}}$es la permutación de${\displaystyle \color {gray}\Sigma _{k}}$de tal manera que a precede a b en${\displaystyle \color {gray}\chi _{w}}$si el 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, ${\displaystyle \color {gray}w=136263163\in \Sigma _{6}}$tiene${\displaystyle \color {gray}\chi _{w}=361245}$.) elegir${\displaystyle w[1]}$en${\textstyle \Sigma _{k+1}}$uniformemente en un conjunto aleatorio${\displaystyle \chi _{w}}$a${\displaystyle w[1]}$seguido de todas las demás letras de${\textstyle \Sigma _{k+1}}$En orden ascendente, establezca el número N de iteraciones en 0. mientras${\displaystyle |w|<n}$elige j en ​${\textstyle \Sigma _{k}}$uniformemente al azar añadir${\displaystyle a=\chi _{w}[j+1]}$hasta el final de la actualización w${\displaystyle \chi _{w}}$desplazando los primeros j elementos a la derecha y estableciendo${\displaystyle \chi _{w}[1]=a}$ Incrementa N en 1. Si w termina con un cuadrado de rango r , elimina las últimas r letras de w.regresar w

Cada palabra libre de cuadrados (k+1)-aria 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 k-arias aleatorias utilizadas por el algoritmo R2F para construir un ⁠${\displaystyle (k+1)}$⁠ Palabra libre de cuadrados -aria de longitud n es$${\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).}$$Tenga en cuenta que existe un algoritmo que puede verificar la ausencia de cuadrados de una palabra de longitud n en${\displaystyle O(n\log n)}$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 de divide y vencerás. Una implementación ingenua puede requerir${\displaystyle O(n^{2})}$tiempo para verificar que una palabra de longitud n no sea cuadrada .

Se pueden generar palabras libres de cuadrados infinitas mediante morfismos libres de cuadrados . Un morfismo se denomina libre de cuadrados si la imagen de cada palabra libre de cuadrados es libre de cuadrados. Un morfismo se denomina k-libre de cuadrados si la imagen de cada palabra libre de cuadrados de longitud k es libre de 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${\displaystyle h(w)}$es libre de cuadrados para todo w libre de cuadrados de longitud 3. Es posible encontrar un morfismo libre de cuadrados mediante búsqueda por fuerza bruta .

El algoritmo square-free_morphism produce como resultado: un morfismo libre de cuadrados con el rango k más bajo posible . colocar${\displaystyle k=3}$mientras sea verdadero , establezca k_sf_words a la lista de todas las palabras libres de cuadrados de longitud k sobre un alfabeto ternario para cada${\displaystyle h(0)}$en k_sf_words hacer para cada${\displaystyle h(1)}$en k_sf_words hacer para cada${\displaystyle h(2)}$en k_sf_words hacer si${\displaystyle h(1)=h(2)}$luego salir del bucle actual (avanzar al siguiente)${\displaystyle h(1)}$) si${\displaystyle h(0)\neq h(1)}$y${\displaystyle h(2)\neq h(0)}$entonces si${\displaystyle h(w)}$es libre de cuadrados para todo w libre de cuadrados de longitud3 luego regresar${\displaystyle h(0),h(1),h(2)}$ incremento k por1

Sobre 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 un número infinito de palabras libres de cuadrados, comience con cualquier palabra libre de cuadrados como0 , y sucesivamente le aplicamos un morfismo libre de cuadrados h . Las palabras resultantes conservan la propiedad de ser libres de cuadrados. Por ejemplo, sea h un morfismo libre de cuadrados, entonces como${\displaystyle w\to \infty }$,${\displaystyle h^{w}(0)}$es una palabra infinita libre de cuadrados.

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

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

Cabe destacar que, con un alfabeto de más de tres letras, existen palabras sin cuadrados de cualquier longitud que no contengan una combinación arbitraria de dos letras.

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

Cabe destacar que, en alfabetos de más de tres letras, existen palabras sin cuadrados de cualquier longitud que no contengan una combinación arbitraria de tres letras.

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

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

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