Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

Estas notas de introducción a la combinatoria de palabras exploran la complejidad factorial mínima de las palabras infinitas no triviales, presentando objetos clásicos como las palabras de Sturmian y ofreciendo una nueva demostración algebraica de un teorema de Tijdeman que generaliza resultados fundamentales de Morse y Hedlund.

Lo esencial

¡Claro que sí! Imagina que este documento es un mapa del tesoro, pero en lugar de buscar oro, buscamos patrones ocultos en el caos.

Aquí tienes una explicación de las "Notas de Clase" de Mélodie Andrieu, traducida al lenguaje cotidiano, con analogías para que cualquiera pueda entender la magia de las palabras infinitas.

---

🌟 El Gran Misterio: ¿Cuánto "ruido" necesita una historia infinita?

Imagina que tienes una cinta de video infinita. En esta cinta solo hay letras (como en un alfabeto de 2, 3 o más letras).

• Si la cinta es aburrida y repetitiva (como 12121212...), es fácil predecir qué viene después.
• Si la cinta es caótica y nunca se repite (como los dígitos de $\pi$), es impredecible.

Los matemáticos quieren medir "cuánto de interesante" es una de estas cintas infinitas. Para hacerlo, cuentan cuántas frases diferentes de longitud $n$ aparecen en la cinta. A esto lo llaman Complejidad.

• Poca complejidad: La cinta es muy repetitiva o muy predecible.
• Mucha complejidad: La cinta es un caos total (como una mezcla aleatoria de letras).

El objetivo de este curso es responder a dos preguntas sencillas:

1. ¿Cuál es la complejidad mínima posible para una cinta que sea "interesante" (es decir, que no sea una repetición aburrida)?
2. ¿Qué tipo de cintas logran ese mínimo?

---

📜 Capítulo 1: El descubrimiento clásico (El caso de 2 letras)

Imagina que solo tienes dos letras: A y B.

En los años 30, dos matemáticos (Morse y Hedlund) descubrieron una regla de oro:

• Si una cinta infinita de A y B tiene una complejidad baja (es decir, si el número de frases diferentes no crece rápido), entonces la cinta debe ser repetitiva (eventualmente periódica). Es como un disco rayado.
• Pero, ¿qué pasa si queremos una cinta que no sea repetitiva, pero que sea lo más simple posible?

¡Resulta que existe un "punto dulce"! La complejidad mínima para una cinta no repetitiva es exactamente $n + 1$.

• Si tienes frases de longitud 1, hay 2 opciones (A, B).
• Si tienes frases de longitud 2, hay 3 opciones.
• Si tienes frases de longitud 3, hay 4 opciones.

Estas cintas mágicas se llaman Palabras de Sturmian.

La analogía del Billar:
Imagina una mesa de billar cuadrada. Lanzas una bola con un ángulo "raro" (un ángulo que no es una fracción simple, como $\sqrt{2}$). La bola rebotará para siempre sin caer nunca en el mismo patrón exacto.

• Si marcas en un papel "1" cada vez que la bola choca con una pared vertical y "2" cuando choca con una horizontal, obtendrás una Palabra de Sturmian.
• Es una danza perfecta entre el orden y el caos. Es la forma más eficiente de ser interesante sin ser caótico.

---

🚀 Capítulo 2: El reto de las 3 o más letras

Ahora, el problema se pone difícil. Imagina que en lugar de 2 letras, tienes 3, 4 o 10 letras (un alfabeto más grande).

El problema:
Si intentas aplicar la misma regla que con 2 letras, te encuentras con trampas. Puedes crear cintas que parecen interesantes pero que en realidad son "trucos" (por ejemplo, una cinta que usa 3 letras, pero dos de ellas nunca aparecen juntas, o que son solo una copia de una cinta de 2 letras con una letra extra pegada al principio).

La solución de Tijdeman (1999):
Para evitar estos trucos, los matemáticos decidieron que una cinta "interesante" debe tener una propiedad especial: las letras deben aparecer con frecuencias que no se pueden relacionar matemáticamente entre sí (llamado "independencia racional").

• Analogía: Imagina que tienes 3 ingredientes. Si la cantidad de harina es siempre el doble que la de azúcar, están "relacionadas". Pero si la harina, el azúcar y la sal tienen cantidades que nunca guardan una proporción simple (como $\pi$ o $\sqrt{2}$), entonces son independientes.

El Teorema de Tijdeman:
Una vez que exigimos esta independencia, Tijdeman descubrió la nueva regla de oro para la complejidad mínima:

• Para un alfabeto de $d$ letras, la complejidad mínima es $(d - 1)n + 1$.
• Si tienes 2 letras: $(2-1)n + 1 = n + 1$ (¡Coincide con Sturmian!).
• Si tienes 3 letras: $(3-1)n + 1 = 2n + 1$.
• Si tienes 10 letras: $9n + 1$.

Esto significa que, a medida que añades más letras, la cinta necesita "crecer" un poco más rápido para seguir siendo interesante y no caer en la repetición.

---

🧮 Capítulo 3: La prueba algebraica (El truco de los matemáticos)

Hasta aquí, todo son reglas. Pero, ¿cómo se demuestra que no hay ninguna cinta "escondida" que rompa la regla?

En 2022, la autora y su colega Cassaigne encontraron una forma nueva y brillante de probar el teorema de Tijdeman. En lugar de usar solo combinatoria (contar letras), usaron Álgebra Lineal (matrices y vectores).

La analogía de la tubería de agua (Flujo):
Imagina que las palabras de la cinta son tuberías por donde fluye agua.

• Cada letra que entra en una tubería debe salir por otra.
• Los matemáticos crearon una "Matriz de Flujo" (Flow Matrix). Es como un plano de ingeniería que muestra cómo el agua (las letras) se mueve a través de las tuberías (las palabras).
• Usaron un teorema matemático (el de rango y nulidad) para demostrar que, si la cinta es "demasiado simple" (tiene poca complejidad), el sistema de tuberías se colapsa o se vuelve inconsistente, a menos que cumpla la regla de $(d-1)n + 1$.

El hallazgo sorpresa:
Al usar este método, descubrieron algo nuevo: todas estas cintas mínimas tienen una estructura especial llamada "Dendríticas" (del griego dendron, árbol).

• Analogía: Imagina que las palabras son ramas de un árbol. Si tomas cualquier palabra y miras cómo puede crecer hacia la izquierda o hacia la derecha, las opciones forman un árbol perfecto sin ciclos ni bucles. Es una estructura de "árbol genealógico" puro.

---

💡 Resumen para llevar a casa

1. El mundo de las palabras infinitas es como un universo de patrones.
2. La complejidad mide cuántas variaciones tiene ese patrón.
3. Las palabras de Sturmian (con 2 letras) son las "reinas" de la simplicidad: son tan simples como es posible sin ser aburridas. Se parecen a un billar perfecto.
4. Para más letras, la regla cambia. Necesitas un poco más de "ruido" para mantener la independencia. El teorema de Tijdeman nos dice exactamente cuánto ruido es necesario.
5. La nueva prueba usa matemáticas de "tuberías" (flujos) para demostrar que no hay atajos: si quieres ser interesante y simple, tu estructura debe ser un "árbol" perfecto.

¿Por qué importa?
Estas palabras no son solo juegos matemáticos. Aparecen en la naturaleza (en la disposición de las hojas en una planta, en la música, en la criptografía) y en la física (en el movimiento de partículas). Entender cómo se construyen las estructuras más simples del universo nos ayuda a entender la propia complejidad de la realidad.

Resumen técnico

Resumen Técnico: Palabras Infinitas con Complejidad de Factores Muy Baja

1. Problema y Contexto

El documento aborda un problema central en la combinatoria de palabras: la caracterización de la complejidad mínima de palabras infinitas sobre alfabetos finitos de tamaño $d \geq 1$.

• Definición de Complejidad: La función de complejidad $p_w(n)$ de una palabra infinita $w$ cuenta el número de factores (subpalabras) distintos de longitud $n$ que aparecen en $w$.
• El Teorema Clásico (Morse-Hedlund, 1938): Para alfabetos binarios ($d=2$), se sabe que una palabra es eventualmente periódica si y solo si su complejidad está acotada. Si la palabra no es periódica, su complejidad mínima es $p_w(n) = n + 1$. Las palabras que alcanzan este mínimo se llaman palabras de Sturmian.
• La Pregunta Central: ¿Cómo se generaliza este resultado a alfabetos de tamaño $d \geq 3$?
  • ¿Cuál es la complejidad mínima para palabras no triviales sobre $d$ letras?
  • ¿Qué define "no trivial" en este contexto? (La no periodicidad eventual resulta insuficiente para $d \geq 3$).
  • ¿Qué palabras alcanzan este mínimo y cuáles son sus propiedades estructurales?

2. Metodología

El artículo utiliza un enfoque híbrido que combina la combinatoria de palabras, la teoría de sistemas dinámicos, la teoría de números (fracciones continuas) y el álgebra lineal.

• Capítulo 1 (Fundamentos): Revisa el caso binario ($d=2$). Introduce las palabras de Sturmian, su conexión con las fracciones continuas, y sus descripciones geométricas (flujos lineales en el toro, billares, rotaciones de círculo). Se establece que la independencia racional de las frecuencias de las letras es una propiedad central de las palabras de Sturmian.
• Capítulo 2 (Generalización a $d$-arios): Analiza por qué la condición de "no periodicidad eventual" falla para $d \geq 3$ (existen palabras recurrentes uniformemente con complejidad $n+d-1$ que son esencialmente deformaciones de palabras de Sturmian). Propone reemplazar esta condición por la independencia racional de las frecuencias de las letras. Presenta el teorema de R. Tijdeman (1999) que establece el límite inferior de complejidad bajo esta nueva condición.
• Capítulo 3 (Prueba Algebraica Alternativa): Desarrolla una prueba nueva y conceptualmente diferente del teorema de Tijdeman (y una versión fortalecida) basada en el álgebra lineal.
  • Herramientas Clave:
    • Gráficos de Rauzy: Graficos dirigidos donde los nodos son factores de longitud $n$ y las aristas son factores de longitud $n+1$.
    • Matrices de Flujo: Una matriz rectangular $M$ (índices por factores de longitud $n$ y $n+1$) que codifica las relaciones de extensión izquierda y derecha. Se interpreta como una regla de Kirchhoff aplicada a la red de factores.
  • Estrategia de Prueba: Se utiliza el teorema de rango-nulidad y el estudio de la dimensión del núcleo de la matriz de flujo (sobre $\mathbb{Q}$ y $\mathbb{R}$) para relacionar la complejidad de la palabra con el grado de irracionalidad de sus frecuencias.

3. Contribuciones Clave y Resultados

A. Definición de "No Trivialidad" para $d \geq 3$

El autor establece que, para alfabetos de tamaño arbitrario, la condición adecuada para definir palabras "interesantes" o no triviales es que las frecuencias de las letras sean racionalmente independientes.

• Si las frecuencias son racionales o dependen racionalmente, la palabra tiende a ser periódica o "pobre" estructuralmente.
• La independencia racional es la generalización natural de la irracionalidad en el caso binario (Sturmian).

B. El Teorema de Tijdeman (1999) y su Generalización

El resultado principal es la determinación de la complejidad mínima para palabras con frecuencias raramente independientes.

• Teorema 2.12 (Tijdeman): Para una palabra infinita $d$-aria con frecuencias raramente independientes, la complejidad satisface:
  $$p_w(n) \geq (d-1)n + 1$$
  Existe al menos una palabra que alcanza este límite.
• Versión Fortalecida (Andrieu-Cassaigne, 2022): El teorema se refina utilizando el grado máximo de irracionalidad ($\Delta_w$) de las frecuencias (la dimensión del espacio vectorial generado por las frecuencias sobre $\mathbb{Q}$), incluso si las frecuencias no existen en el límite clásico (usando límites de subsecuencias):
  $$p_w(n) \geq (\Delta_w - 1)(n - 1) + d$$
  Cuando las frecuencias existen y son raramente independientes, $\Delta_w = d$, recuperando la fórmula original.

C. Prueba Algebraica Alternativa

El Capítulo 3 ofrece una prueba conceptualmente nueva del teorema de Tijdeman que difiere de la prueba combinatoria original de Tijdeman:

1. Se define la matriz de flujo $M$ asociada a los factores de una longitud crítica $m$.
2. Se demuestra que el vector de frecuencias pseudo-asintóticas de los factores pertenece al núcleo de $M$.
3. Mediante el teorema de rango-nulidad y propiedades de los grafos de Rauzy (semi-conectividad), se prueba que la dimensión del núcleo racional está acotada por $\Delta_w - 1$.
4. Esto implica que las frecuencias de las letras no pueden generar un espacio de dimensión $\Delta_w$ si la complejidad es demasiado baja, llevando a una contradicción.

D. Estructura Combinatoria: Palabras Dendríticas

Un resultado derivado importante de la nueva prueba es la caracterización estructural de las palabras que alcanzan la complejidad mínima de Tijdeman.

• Teorema 3.2: Toda palabra infinita $d$-aria con frecuencias raramente independientes y complejidad $p_w(n) = (d-1)n + 1$ es una palabra dendrítica.
• Definición: Una palabra es dendrítica si el gráfico de extensión de cada uno de sus factores es un árbol (conexo y sin ciclos).
• Esto conecta la complejidad mínima con una propiedad estructural fuerte, generalizando una propiedad conocida de las palabras de Sturmian.

4. Significado e Impacto

1. Unificación Teórica: El trabajo proporciona un marco unificado para entender la complejidad mínima en alfabetos de cualquier tamaño, resolviendo la ambigüedad sobre qué constituye una palabra "no trivial" en dimensiones superiores.
2. Nueva Perspectiva Algebraica: La introducción de las matrices de flujo y su análisis lineal ofrece una herramienta poderosa y elegante para atacar problemas de complejidad, complementando y superando las técnicas puramente combinatorias tradicionales.
3. Caracterización Estructural: Al demostrar que las palabras de complejidad mínima son dendríticas, el artículo avanza significativamente en la clasificación de estas palabras, vinculándolas con clases bien estudiadas como las palabras de Arnoux-Rauzy, episturmianas estrictas y codificaciones de intercambios de intervalos.
4. Relevancia Interdisciplinaria: Refuerza las conexiones profundas entre la combinatoria de palabras, la teoría de números (fracciones continuas multidimensionales), la teoría ergódica (sistemas dinámicos minimales) y el álgebra lineal.

En resumen, estas notas de conferencia no solo revisan el estado del arte sobre las palabras de Sturmian, sino que presentan resultados originales (prueba algebraica y caracterización dendrítica) que avanzan la comprensión de la complejidad mínima en alfabetos generales, estableciendo un nuevo estándar para la investigación en este campo.