State Complexity of Shifts of the Fibonacci Word

Aquí presento un resumen técnico detallado del artículo "State Complexity of Shifts of the Fibonacci Word" (Complejidad de Estados de los Desplazamientos de la Palabra de Fibonacci), estructurado según los puntos solicitados.

1. El Problema

El artículo aborda un problema fundamental en la teoría de la complejidad descriptiva y las secuencias automáticas: determinar la complejidad de estados (el número mínimo de estados necesarios) de un autómata finito determinista con salida (DFAO) que genera una secuencia desplazada.

Específicamente, se estudia la palabra de Fibonacci infinita $f = (f_i)_{i \ge 0} = 01001010\dots$, un objeto clásico en la combinatoria de palabras. La palabra de Fibonacci es una secuencia automática que puede generarse mediante un DFAO de muy pocos estados (5 estados en representación Zeckendorf lsd-first, 2 estados en msd-first).

El problema central es: si tomamos la secuencia original y la desplazamos por un entero fijo $c$ (es decir, consideramos la secuencia $(f_{i+c})_{i \ge 0}$), ¿cuántos estados requiere el autómata mínimo para generar esta nueva secuencia?

El desafío radica en que, para secuencias automáticas generales en base $k$, el desplazamiento suele requerir una complejidad de $O(m \log c)$ o incluso $O(c)$ (como en el caso msd-first de la secuencia de Thue-Morse). Sin embargo, para la palabra de Fibonacci, que utiliza el sistema de numeración de Zeckendorf (basado en números de Fibonacci), la aritmética de desplazamiento es más compleja debido a la falta de un transductor determinista de un solo paso para la suma en este sistema.

2. Metodología

Los autores emplean una mezcla sofisticada de técnicas de complejidad de estados, aproximación diofántica y lógica formal.

• Representación de Zeckendorf y Números Negativos: Utilizan el sistema de numeración de Zeckendorf (suma de números de Fibonacci no consecutivos) tanto para enteros positivos como negativos. Introducen una representación específica para números negativos necesaria para el análisis.
• Análisis de Particiones del Intervalo $[0, 1)$:
  • Caso lsd-first (menos significativo primero): Definen una partición del intervalo $[0, 1)$ basada en los bits de menor orden de la representación de Zeckendorf. Utilizan el hecho de que $\{n\phi\}$ (la parte fraccional de $n$ multiplicada por el número áureo $\phi$) cae en un intervalo específico determinado por los bits de menor peso de $n$.
  • Caso msd-first (más significativo primero): Definen particiones consistentes con la representación msd-first. Utilizan lemas que demuestran cómo las particiones se comportan al "desplazar" la representación (añadir o quitar bits), asegurando que la consistencia se mantenga.
• Teorema de Lemma 1 y 2: Establecen una conexión crucial entre el valor del bit $f(i)$ y la posición de $\{i\phi\}$ en el círculo unitario. Específicamente, $f(i+c)=1$ si y solo si $\{i\phi\}$ cae en un intervalo específico definido por $-(c+1)\phi$ y $-(c+2)\phi$.
• Uso de Walnut: Una parte significativa de las pruebas, especialmente las propiedades de las particiones y la consistencia de los intervalos bajo operaciones de bits, se verifica rigurosamente utilizando Walnut, un demostrador de teoremas automatizado para secuencias automáticas basado en lógica de primer orden.

3. Contribuciones Clave

1. Acotación Logarítmica Óptima: Demuestran que la complejidad de estados para generar la secuencia desplazada $(f_{i+c})$ es $O(\log c)$ tanto para la entrada en formato lsd-first como msd-first.
2. Construcción de Autómatas: Proporcionan construcciones explícitas de los DFAO para ambos casos:
   • Para lsd-first, el autómata utiliza estados que rastrean en qué intervalo de la partición inducida por los bits de entrada cae el punto $\{n\phi\}$. Una vez que se lee suficiente información (aproximadamente $k$ bits donde $F_k \approx c$), el autómata entra en un estado de "sumidero" (sink state) que determina la salida.
   • Para msd-first, construyen un autómata basado en una partición refinada de $[0, 1)$ que es consistente con la operación de añadir bits a la derecha de la representación de Zeckendorf.
3. Fórmula Exacta para lsd-first: Derivan una fórmula exacta para el número mínimo de estados en el caso lsd-first:
   $$\text{Estados} = 2(|(c)_F| + 1) + 1 - g(c)$$
   donde $|(c)_F|$ es la longitud de la representación de Zeckendorf de $c$, y $g(c)$ es una función que depende de los valores de $f(c-1)$ y $f(c-2)$. Esto demuestra que el límite superior $O(\log c)$ es óptimo.
4. Generalización de Técnicas: Integran métodos de aproximación diofántica (propiedades de $\{n\phi\}$) con la teoría de autómatas, mostrando cómo la estructura algebraica de los números de Fibonacci permite una eficiencia mucho mayor que en sistemas de numeración estándar (como la base 10 o base 2).

4. Resultados Principales

• Teorema 1 (lsd-first): Para cualquier $c \ge 0$, existe un DFAO lsd-first que genera $(f_{i+c})$ con $O(\log c)$ estados. La prueba se basa en que los bits de menor orden de $n$ determinan un intervalo de longitud $\approx \phi^{-d}$ donde reside $\{n\phi\}$.
• Teorema 2 (Exactitud lsd-first): La complejidad exacta es $2(|(c)_F| + 1) + 1 - g(c)$. Esto implica que la complejidad crece logarítmicamente con $c$, ya que la longitud de la representación de Zeckendorf es logarítmica.
• Teorema 3 (msd-first): Para cualquier $c \ge 0$, existe un DFAO msd-first que genera $(f_{i+c})$ con $O(\log c)$ estados. Esto es notable porque, en otros sistemas (como la secuencia de Thue-Morse en base 10), el desplazamiento msd-first puede requerir $O(c)$ estados.
• Comparación con el Límite Inferior: La complejidad $O(\log c)$ está muy cerca del mínimo teórico posible para secuencias no periódicas. Un argumento de conteo simple muestra que cualquier secuencia automática no periódica desplazada debe tener una complejidad que excede $\Omega(\log c / \log \log c)$ infinitas veces. Por lo tanto, la palabra de Fibonacci muestra un crecimiento de complejidad casi óptimo.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Eficiencia Excepcional: Muestra que la palabra de Fibonacci posee una estructura interna tan rica y regular que permite manejar desplazamientos arbitrarios con un costo de memoria (estados) extremadamente bajo, mucho menor que el de otras secuencias automáticas famosas.
• Puente entre Disciplinas: El artículo conecta exitosamente la teoría de autómatas, la teoría de números (aproximación diofántica, números de Fibonacci, número áureo) y la lógica computacional (Walnut).
• Implicaciones Teóricas: Proporciona un contraejemplo a la intuición de que el desplazamiento en sistemas de numeración no estándar (como Zeckendorf) siempre conlleva una alta complejidad. Sugiere que para ciertos números irracionales cuadráticos (como $\phi$), la complejidad de los desplazamientos puede ser logarítmica.
• Futuras Direcciones: Los autores sugieren que estos resultados pueden generalizarse a otros irracionales cuadráticos y a palabras como la de Tribonacci, abriendo nuevas líneas de investigación en la complejidad de secuencias automáticas en sistemas de numeración no estándar.

En resumen, el paper demuestra que, a pesar de la aparente complejidad de la aritmética en el sistema de Zeckendorf, la estructura geométrica de la palabra de Fibonacci permite una representación eficiente de sus desplazamientos, logrando una complejidad de estados $O(\log c)$ en ambos modos de lectura (msd-first y lsd-first).