The complexity of finite smooth words over binary alphabets

Este artículo demuestra que los factores de las palabras suaves son f-suaves y avanza en la conjetura de Sing sobre su complejidad, probándola para alfabetos pares, estableciendo una cota inferior para cualquier alfabeto binario y mejorando la cota superior para alfabetos impares.

Lo esencial

Imagina que las palabras son como torres de bloques de construcción. En el mundo de las matemáticas, hay un tipo especial de torres llamadas "palabras suaves" (smooth words). La más famosa es la "Palabra de Kolakoski", que es un patrón infinito que se construye a sí mismo siguiendo una regla muy estricta: si ves un bloque, te dice cuántos bloques del mismo tipo debes poner a continuación.

El problema es que estas torres infinitas son muy difíciles de estudiar directamente. Son como intentar contar cada átomo en un edificio que nunca termina de construirse.

La Gran Idea: Las "Fotografías" de la Torre

En este artículo, los autores Julien Cassaigne y Raphaël Henry proponen una solución brillante: en lugar de estudiar la torre infinita, estudiamos fotografías de trozos finitos de ella. Llamamos a estos trozos "palabras f-suaves" (f-smooth).

Piensa en esto así:

• La Torre Infinita (Palabra Suave): Es el edificio completo, eterno y perfecto.
• Las Fotografías (Palabras f-suaves): Son recortes de paredes o ventanas que puedes llevar en tu bolsillo.

El primer gran descubrimiento del artículo es confirmar una sospecha de los matemáticos: Cualquier trozo que puedas cortar de la torre infinita es una "fotografía" válida, y cualquier "fotografía" válida puede encajar en la torre infinita. Es como decir que si tienes una pieza de rompecabezas que encaja perfectamente, esa pieza pertenece al rompecabezas completo. Esto es crucial porque nos permite estudiar la complejidad de la torre infinita simplemente contando cuántas "fotografías" diferentes existen de cierto tamaño.

El Misterio de la "Complejidad"

Ahora, imaginemos que queremos saber cuántas "fotografías" diferentes podemos hacer de una torre de cierto tamaño.

• Si la torre es muy simple (como una pared de ladrillos idénticos), hay muy pocas fotos diferentes.
• Si la torre es caótica y llena de patrones extraños, hay millones de fotos diferentes.

A esto los matemáticos le llaman complejidad. La pregunta del millón es: ¿Cómo crece este número de fotos a medida que hacemos la torre más grande? ¿Crece como una línea recta? ¿Como un cuadrado? ¿O como algo más exótico?

La Conjetura del "Crecimiento Exótico"

Existe una conjetura (una suposición muy fuerte) que dice que el número de fotos crece siguiendo una fórmula muy específica que depende de los números que usamos para construir la torre (llamados $a$ y $b$). La fórmula es algo así como:
$$\text{Número de fotos} \approx n^{\text{algo complicado}}$$

Los autores de este artículo han logrado tres cosas importantes para resolver este misterio:

1. La Regla de los Números Pares (Alfabetos "Even"):
   Si los números que usamos para construir la torre son ambos pares (como 2 y 4) o ambos impares (como 1 y 3), han demostrado que la conjetura es verdadera. Han probado que la complejidad crece exactamente como se esperaba. Es como si hubieran encontrado la llave maestra para abrir la caja fuerte de estos casos.

2. El Piso Mínimo (Límite Inferior):
   Para cualquier combinación de números (pares o impares mezclados), han demostrado que la complejidad nunca puede ser menor de lo que predice la fórmula. Han establecido un "suelo" que la complejidad no puede cruzar. Es como decir: "No importa cuán simple parezca la torre, siempre tendrá al menos esta cantidad de patrones diferentes".

3. El Techo Mejorado (Límite Superior para Números Impares):
   Para los casos donde los números son impares (como 1 y 3, o 3 y 5), la situación es más difícil. Antes, teníamos un "techo" muy alto que decía "la complejidad no supera este número gigante". Los autores han bajado ese techo significativamente. Han encontrado un límite más ajustado, acercándose más a la respuesta real, aunque aún no han probado que sea exactamente la fórmula perfecta en este caso.

¿Por qué importa esto?

Imagina que estás tratando de predecir el clima. Si solo sabes que "llueve a veces", es difícil. Pero si descubres una fórmula exacta que te dice cuántas gotas de lluvia caerán en un minuto basándote en la temperatura, puedes predecir el futuro con mucha precisión.

En el mundo de las matemáticas, entender cómo crecen estas "palabras suaves" nos ayuda a entender:

• Cómo se organizan los patrones en la naturaleza.
• Cómo funcionan los algoritmos de compresión de datos (como los que usan para enviar fotos por WhatsApp).
• La frontera entre el orden y el caos.

En Resumen

Este artículo es como un mapa de exploración. Los autores han confirmado que el territorio de las "palabras suaves" es más ordenado de lo que pensábamos en ciertos casos (cuando los números son pares) y han trazado límites más precisos en los casos difíciles (cuando son impares). Han demostrado que, aunque estas torres infinitas parecen caóticas, siguen reglas matemáticas profundas y elegantes que podemos empezar a descifrar.

Han corregido errores de trabajos anteriores (como un mapa mal dibujado que usaba una regla de construcción incorrecta) y han puesto los cimientos sólidos para que, en el futuro, alguien pueda terminar de resolver el rompecabezas completo.

Resumen técnico

1. El Problema y el Contexto

El artículo aborda el estudio de la complejidad de factores (el número de subpalabras distintas de longitud $n$) de las palabras suaves (smooth words) sobre alfabetos binarios $\{a, b\}$ con $1 \le a < b$.

• Palabras Suaves ($C^\infty$): Son palabras infinitas que son infinitamente derivables bajo la operación de codificación de longitudes de ejecución (run-length encoding). El ejemplo más famoso es la palabra de Oldenburger-Kolakoski ($\kappa_{2,1}$) sobre $\{1, 2\}$.
• Palabras f-suaves ($C^\infty_f$): Son la versión finita de las palabras suaves. Se definen como palabras finitas que pueden derivarse hasta la palabra vacía ($\varepsilon$) mediante una operación de derivación finita $D_f$.
• La Conjetura Central: Se ha conjeturado (Dekking, Sing) que la complejidad de factores de las palabras f-suaves crece asintóticamente como:
  $$p_{C^\infty_f}(n) = \Theta\left(n^\rho\right) \quad \text{donde} \quad \rho = \frac{\log(a+b)}{\log\left(\frac{a+b}{2}\right)}$$
• El Desafío: Aunque se conocían cotas polinómicas, la conjetura exacta del exponente $\rho$ no estaba demostrada para todos los casos. Además, existía una dicotomía no resuelta sobre si los factores de las palabras suaves infinitas coincidían exactamente con el conjunto de palabras f-suaves, especialmente en alfabetos donde $a+b$ es par o impar.
• Error Previo: El artículo identifica y corrige un error en un trabajo previo de Huang ([11]), quien utilizó una definición incorrecta de la derivada finita, lo que llevó a cotas superiores erróneas para alfabetos impares.

2. Metodología

Los autores emplean una combinación de teoría de palabras combinatorias, análisis de estructuras de árboles y teoría espectral de matrices.

1. Definición de Palabras r-suaves: Introducen un concepto dual, las palabras r-suaves (derivables hacia la derecha), para demostrar que todo factor de una palabra suave infinita es f-suave.
2. Análisis de Factores Bispeciales: Utilizan la teoría de factores bispeciales (palabras que pueden extenderse a la izquierda y derecha con cualquier letra del alfabeto) para calcular la complejidad. La complejidad $p(n)$ se relaciona con la suma de las multiplicidades de los factores bispeciales.
3. Estructura de Árboles (F-Primitivas):
   • Definen las f-primitivas ($P_{f,a}, P_{f,b}$), que son las operaciones inversas de la derivación.
   • Demuestran que los factores bispeciales fuertes y débiles forman árboles binarios infinitos generados por estas primitivas.
   • Reducen el problema de contar la complejidad al estudio de la longitud de las palabras en las generaciones de estos árboles.
4. Análisis Asintótico:
   • Para la cota inferior, calculan la longitud promedio de las palabras en cada generación del árbol.
   • Para la cota superior, buscan una cota inferior para la longitud mínima ($l_i$) de las palabras en la generación $i$ del árbol.
   • En alfabetos impares, modelan la evolución de las longitudes mediante matrices lineales y aplican el Teorema de Perron-Frobenius para determinar la tasa de crecimiento espectral.

3. Contribuciones Clave y Resultados Principales

El artículo presenta tres teoremas principales que avanzan significativamente en la comprensión de la complejidad de estas palabras:

A. Igualdad de Lenguajes (Teorema 1.31)

• Resultado: Se demuestra que, sobre cualquier alfabeto binario, el conjunto de factores de las palabras suaves infinitas es exactamente el conjunto de palabras f-suaves:
  $$L(C^\infty) = C^\infty_f$$
• Implicación: Esto confirma que $p_{C^\infty}(n) = p_{C^\infty_f}(n)$. Aunque no prueba que todas las palabras suaves tengan la misma complejidad (especialmente en alfabetos pares donde existen palabras suaves "patológicas"), establece que estudiar $C^\infty_f$ es suficiente para entender la complejidad de los factores de las palabras suaves.

B. Cota Inferior General y Cota Superior para Alfabetos Pares (Teorema 1.32)

• Cota Inferior: Se prueba que para cualquier alfabeto binario $\{a, b\}$:
  $$p_{C^\infty_f}(n) = \Omega(n^\rho)$$
  donde $\rho = \frac{\log(a+b)}{\log((a+b)/2)}$. Esto confirma la parte inferior de la conjetura de Sing.
• Cota Superior (Alfabetos Pares): Si $a$ y $b$ son ambos pares (alfabeto par), se demuestra que:
  $$p_{C^\infty_f}(n) = \Theta(n^\rho)$$
  Esto resuelve completamente la conjetura de la complejidad para el caso de alfabetos pares.

C. Nueva Cota Superior para Alfabetos Impares (Teorema 1.33)

• Resultado: Para alfabetos donde $a$ y $b$ son impares, se obtiene una nueva cota superior que mejora las conocidas anteriormente (incluyendo las de Huang, que eran incorrectas).
  $$p_{C^\infty_f}(n) = O(n^\zeta)$$
  donde $\zeta$ depende de la raíz dominante de un polinomio característico específico (o una fórmula cerrada si $a=1$).
• Mejora: El exponente $\zeta$ es estrictamente menor que la cota anterior $\beta$ propuesta por Sing, acercándose más al valor conjeturado $\rho$, aunque aún no se ha probado que $\zeta = \rho$ en este caso.

4. Significado e Impacto

1. Resolución de la Conjetura en Casos Específicos: El trabajo cierra definitivamente el problema de la complejidad para alfabetos binarios donde la suma de los caracteres es par, confirmando la hipótesis de crecimiento polinomial $\Theta(n^\rho)$.
2. Corrección de Literatura: Al identificar el error en la definición de la derivada en el trabajo de Huang, el artículo corrige la literatura existente y proporciona un marco correcto para futuros estudios sobre alfabetos impares.
3. Herramientas Nuevas: La introducción de las palabras r-suaves y el análisis detallado de la estructura de los árboles de primitivas f proporcionan nuevas herramientas metodológicas para estudiar la complejidad de lenguajes definidos por operaciones de derivación.
4. Diferenciación de Casos: El artículo clarifica la dicotomía entre alfabetos pares e impares. Mientras que en los pares la estructura es más regular (permitiendo la prueba completa), en los impares la estructura es más compleja, lo que explica por qué la prueba de la cota superior exacta sigue siendo un desafío abierto, aunque se ha mejorado significativamente.

En resumen, este artículo representa un avance fundamental en la combinatoria de palabras, proporcionando la primera prueba rigurosa de la conjetura de complejidad para una clase amplia de alfabetos y estableciendo nuevas cotas más ajustadas para el caso restante.