Cadena infinita única(ish) que evita un conjunto de patrones

Question

Sea $\Sigma$ sea un alfabeto finito de tamaño al menos 2. Una cadena (posiblemente infinita) $s$ sobre el alfabeto $\Sigma$ encuentra un patrón $p \in \mathbb{N}^*$ si existe un morfismo no decreciente $f: \mathbb{N} \to \Sigma^*$ (es decir, $f$ nunca toma un valor de palabra vacío) tal que $f(p)$ es una subcadena (o factor ) de $s$ . Por lo demás, $s$ evita $p$ .

Evidentemente, si $s$ evita $p$ entonces lo hace bajo cualquier permutación de letras en $\Sigma$ . Además, un desplazamiento a la izquierda de $s$ (sólo $s$ sin la primera letra) debe evitar $p$ también. Llamemos cadenas infinitas $s$ y $t$ equivalentes si pueden hacerse iguales tras una secuencia finita de desplazamientos a la izquierda (cada uno de ellos puede aplicarse a cada una de las cadenas) y/o permutación de letras en $\Sigma$ (aplicado sólo a una de las cadenas).

¿Existe un alfabeto $\Sigma$ y un conjunto finito de patrones $p_1, \ldots, p_n$ tal que todas las cadenas infinitas sobre $\Sigma$ evitar $p_1, \ldots, p_n$ son equivalentes (y, por supuesto, existe al menos una cadena de este tipo)?

Answer 1

No estoy seguro de que existan ejemplos para tu definición bastante fuerte de equivalencia; sin embargo, si modificas ligeramente el problema, hay algunos resultados conocidos. En primer lugar, consideremos las palabras bi-infinitas $s$ y $t$ (en lugar de palabras infinitas unidireccionales) y decir que $s$ y $t$ son equivalentes si tienen el mismo conjunto de factores finitos. Entonces, sobre $\{0,1\}$ se sabe que una palabra bi-infinita evita el conjunto de patrones $\{xxx, xyxyx\}$ si y sólo si es equivalente a la palabra bi-infinita de Thue--Morse (véase Gottschalk y Hedlund, "A characterization of the Morse minimal set", 1964). Ochem y Rosenfeld han realizado recientemente nuevos trabajos en este sentido: http://www.lirmm.fr/~ochem/morphisms/main.pdf (busque "esencialmente evita" en su documento).

De hecho, supongo que la respuesta a tu pregunta original debería ser "no". Si un patrón es evitable, entonces es evitable mediante una palabra uniformemente recurrente (o "casi periódica") $s$ (este es el resultado de Furstenberg ). Sin embargo, cada palabra infinita en el cierre de la órbita de desplazamiento de $s$ también evita el patrón, pero el cierre de la órbita de desplazamiento de una palabra aperiódica pero uniformemente recurrente es incontable (véase la Sección 13.7 de Lind y Marcus, Symbolic Dynamics and Coding). Puesto que el cierre de la órbita de desplazamiento es incontable, debe haber palabras en él que no sean equivalentes hasta algún desplazamiento inicial.