¿Existen incontables palabras binarias infinitas libres de cubos?

Question

Sur Palabras binarias infinitas sin cubo se estableció que existen infinitas palabras binarias infinitas libres de cubos (véase la pregunta anterior para las definiciones de los términos). La construcción dada en respuesta a esa pregunta produce una infinidad contable de tales palabras. En un comentario a esa respuesta, planteé la cuestión de si existe una infinidad incontable de tales palabras. Mi comentario no ha suscitado ninguna respuesta; tal vez suscite más interés como pregunta.

Debo admitir que lo pregunto por mera curiosidad y que no tengo ningún interés en investigar la respuesta; simplemente me parece la pregunta lógica que hay que hacerse cuando se sabe que un conjunto es infinito.

Answer 1

Hay incontables palabras infinitas sin cubo. De hecho, considere cualquier palabra infinita libre de cubo en 2 letras $a$ y $b$ (digamos, la palabra Thue-Morse). Esta palabra contiene infinitas ocurrencias de $a $ . Sustituya algunas apariciones de $a$ por $a'$ y algunas apariciones de $a$ por $a''$ . Obtiene una nueva palabra infinita en $a',a'',b$ que también está libre de cubos (pero en 3 letras), un continuo de ellos. Uno puede entonces utilizar una sustitución de un alfabeto de 3 letras a un alfabeto de 2 letras que preserva cubo-libertad (véase Bean, Dwight R.; Ehrenfeucht, Andrzej; McNulty, George F.Avoidable patrones en cadenas de símbolos. Pacific J. Math. 85 (1979), no. 2, 261-294) para obtener un continuo de palabras libres de cubos en 2 letras.

Answer 2

Denote por $\mu$ la cartografía de la secuencia de Thue-Morse, $\mu(0)=01$ y $\mu(1)=10$ . Defina ahora una secuencia de mapas de palabras binarias a palabras binarias, $g$ de modo que $g_{\emptyset}(w)=w$ , $g_{0b}(w)=\mu^2(g_{b}(w))$ y $g_{1b}(w)=0\mu^2(g_{b}(w))$ . Ahora dada una secuencia binaria infinita $B=b_1b_2\dots$ defina $w_{B}$ sea el límite de $$g_{b_1}(w),g_{b_1b_2}(w),g_{b_1b_2b_3}(w),\dots$$ En $w_B$ darte incontables $7/3$ -palabras libres de potencia (así, en particular, libres de cubo) que además tienen infinitas superposiciones.

Este resultado más sólido se demuestra aquí . Creo que todas las construcciones conocidas de grandes familias de tales secuencias están definidas por mapeados iterativos.

Answer 3

También se puede considerar lo siguiente. Sea x la sucesión de Thue Morse. Sea X el cierre del conjunto de desplazamientos de secuencias, es decir, las secuencias obtenidas suprimiendo las primeras letras. Este conjunto es perfecto. Por tanto, X es incontable. También cada elemento de X es libre de cubos.
Lo único que hay que comprobar aquí es que X es perfecto. Para ello basta con comprobar que x es un punto límite. Para ello se puede utilizar el hecho de que x está generado por la sucesión $0 \rightarrow 01$ y $1 \rightarrow 10$ . La topología en $\{0,1\}^{\mathbb N}$ es el producto de la topología discreta sobre $\{0,1\}$ .

Answer 4

En "Problemas pendientes en la evitación de patrones" ( aquí ), James Currie escribió: "Se sabe [15] que el conjunto de cubefree $\omega$ -palabras sobre un alfabeto de 2 letras es incontable". La referencia [15] del artículo de Currie es aquí pretende establecer un método para generar el conjunto de todas las palabras infinitas fuertemente libres de cubos (ninguna subpalabra de la forma $BBb$ donde $b$ es el primer símbolo de $B$ llamado en este trabajo "irreducible"), y demuestra que un subconjunto particular es incontable.

Answer 5

Acabo de ver y responder a la pregunta anterior, pero tal vez debería repetir mi post:

He aquí algunos hechos profundos relacionados con los cfw binarios:

1) El conjunto de palabras binarias sin cubo infinitas derechas es un conjunto perfecto en sentido topológico: Para cualquier secuencia dada, existe una distinta que coincide con ella hasta la enésima letra. En particular, hay incontables cfw binarias.

2) Dada cualquier secuencia binaria finita, es decidible si se extiende a una palabra binaria infinita libre de cubos.

3) El número de cfw binarios (finitos) de longitud n crece exponencialmente con n.

Estos resultados (y otros análogos para palabras libres de k potencias sobre varios alfabetos) se demuestran en

http://dl.acm.org/citation.cfm?id=873885 y http://www.sciencedirect.com/science/article/pii/0195669895900519