Mahler equations for Zeckendorf numeration

Aquí presento un resumen técnico detallado del artículo "Mahler Equations for Zeckendorf Numeration" de Olivier Carton y Reem Yassawi, estructurado según los puntos solicitados.

1. Planteamiento del Problema

El artículo aborda la generalización de la teoría de secuencias regulares y ecuaciones de Mahler desde los sistemas de numeración clásicos (base-$k$) hacia sistemas de numeración basados en recurrencias lineales, específicamente el sistema de numeración de Zeckendorf (basado en los números de Fibonacci).

• Contexto Teórico:
  • El Teorema de Christol establece una conexión fundamental entre la algebraicidad de series formales sobre campos finitos y la computabilidad por autómatas finitos (secuencias $p$-automáticas).
  • La noción de regularidad (introducida por Allouche y Shallit) generaliza esto a secuencias generadas por autómatas ponderados sobre anillos conmutativos.
  • Becker y Dumas demostraron que, para una base $k \ge 2$, las secuencias $k$-regulares son soluciones de ecuaciones de Mahler ($k$-Mahler) y viceversa, siempre que la ecuación sea "aislante" (el coeficiente del término de orden cero es 1).
• El Desafío:
  • En la numeración base-$k$, la operación de multiplicar por $k$ corresponde a añadir un cero al final de la representación del número ($n \mapsto kn$). Esta propiedad de linealidad es crucial para las demostraciones clásicas que utilizan operadores de Cartier.
  • En el sistema de Zeckendorf ($Z$), donde los números se representan como sumas de Fibonacci sin dígitos consecutivos de 1, la función análoga $\phi(n)$ (que actúa como $n \mapsto kn$) no es lineal. Específicamente, $\phi(m+n) \neq \phi(m) + \phi(n)$ en general.
  • Esta no-linealidad rompe las herramientas estándar (como los operadores de Cartier), haciendo que la extensión directa de los resultados de Becker y Dumas sea no trivial. El problema central es determinar si existe una equivalencia entre las secuencias $Z$-regulares y las soluciones de ecuaciones de Mahler generalizadas para este sistema.

2. Metodología

Los autores desarrollan un marco teórico y constructivo que combina teoría de autómatas, teoría de números (específicamente propiedades de los números de Pisot) y álgebra de series formales.

• Definición del Operador $\Phi$:
  • Introducen un operador lineal $\Phi: R[[x]] \to R[[x]]$ definido por $\Phi(\sum f_n x^n) = \sum f_n x^{\phi(n)}$, donde $\phi(n)$ es la función que mapea la expansión de Zeckendorf de $n$ a la expansión de $n$ desplazada (análoga a multiplicar por la base).
  • Reconocen que $\Phi$ no es un homomorfismo de anillos ($\Phi(fg) \neq \Phi(f)\Phi(g)$) debido a la no-linealidad de $\phi$, pero sí lo es para series cuyos coeficientes no nulos tienen soportes disjuntos.
• Análisis del Defecto de Linealidad:
  • Definen el "defecto de linealidad" $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$.
  • Demuestran (Lema 18) que este defecto está acotado: $\delta(m, n) \in \{-1, 0, 1\}$.
  • Construyen un autómata determinista que, dada la representación de $m$ y $n$ en base Zeckendorf, calcula este defecto. Esto es crucial para rastrear los errores acumulados durante las operaciones.
• Construcción de Autómatas Ponderados:
  • Diseñan un autómata universal ponderado para ecuaciones de Mahler en base-$k$ (Teorema 2), que genera soluciones sin necesidad de operadores de Cartier.
  • Extienden esta construcción al caso de Zeckendorf (Sección 3.4.1). El autómata asociado a una ecuación $Z$-Mahler incluye estados adicionales para rastrear el defecto de linealidad $\delta$ y la estructura de la palabra de entrada, permitiendo calcular los coeficientes de la solución recursivamente.

3. Contribuciones Clave

1. Definición de Ecuaciones $Z$-Mahler:
   • Formalizan la ecuación $P(x, y) = \sum_{i=0}^d A_i(x) \Phi^i(y) = 0$, donde $\Phi$ es el operador basado en la función de Zeckendorf.
2. Teorema Principal (Teorema 1):
   • Establecen que si $P(x, y) = 0$ es una ecuación $Z$-Mahler aislante (el coeficiente de $y$ es 1), entonces cualquier solución $f(x)$ es una secuencia $Z$-regular. Es decir, los coeficientes de $f$ pueden ser generados por un autómata ponderado que lee las expansiones de Zeckendorf.
   • Esto generaliza el resultado de Becker y Dumas al sistema de Zeckendorf.
3. Construcción Directa de Autómatas (Teorema 2 y 29):
   • Proporcionan una construcción explícita de un autómata ponderado que genera la solución de una ecuación de Mahler aislante.
   • A diferencia de las pruebas anteriores que dependían de operadores de Cartier, su método es directo y revela una estructura universal en los autómatas que generan secuencias regulares.
   • Acotan el número de estados del autómata en función del exponente $d$, la altura $h$ de la ecuación y la constante áurea $\phi$.
4. Contraejemplo de Ecuaciones No Aislantes:
   • Demuestran que la condición de "aislamiento" es necesaria. Proporcionan un ejemplo (Proposición 38) de una ecuación $Z$-Mahler no aislante cuya solución tiene coeficientes que crecen demasiado rápido para ser una secuencia $Z$-regular (violando el crecimiento polinómico característico de las secuencias regulares).
5. Generalización a Sistemas de Pisot:
   • Aunque se centran en Zeckendorf, argumentan que sus resultados y técnicas se pueden extender a cualquier sistema de numeración generado por la recurrencia de un número de Pisot.

4. Resultados Principales

• Equivalencia Parcial: Existe una correspondencia fuerte entre las secuencias $Z$-regulares y las soluciones de ecuaciones $Z$-Mahler aislantes.
  • Dirección 1: Toda secuencia $Z$-regular es solución de una ecuación $Z$-Mahler (Corolario 34).
  • Dirección 2: Toda solución de una ecuación $Z$-Mahler aislante es $Z$-regular (Teorema 29).
• Límites de Crecimiento: Se demuestra que las soluciones de ciertas ecuaciones no aislantes pueden tener coeficientes que crecen exponencialmente o superpolinómicamente, lo cual es incompatible con la definición de regularidad (Lema 5).
• Complejidad del Autómata: El número de estados del autómata generado para una ecuación de altura $h$ y exponente $d$ es del orden de $O(d \cdot h^2 \cdot \phi^h)$, lo cual es significativamente mayor que en el caso base-$k$ ($O(d \cdot h)$) debido a la necesidad de rastrear el defecto de linealidad.

5. Significado e Impacto

• Avance en Teoría de Autómatas y Numeración: El trabajo cierra una brecha importante en la teoría de secuencias automáticas y regulares, extendiendo resultados clásicos de base-$k$ a sistemas de numeración más complejos y naturales como el de Zeckendorf.
• Nuevas Herramientas de Prueba: La eliminación de la dependencia de los operadores de Cartier y el uso de autómatas para calcular el defecto de linealidad ofrece una nueva metodología que podría aplicarse a otros sistemas de numeración no estándar.
• Conexión con Teoría de Números y Dinámica: El artículo conecta la teoría de autómatas con propiedades de los números de Pisot y la estructura de los conjuntos de Meyer, sugiriendo vínculos profundos entre la computabilidad, la algebraicidad y la geometría de números.
• Problemas Abiertos: Los autores identifican preguntas abiertas cruciales, como la caracterización completa de las secuencias $Z$-regulares (sin la restricción de ser soluciones de ecuaciones aislantes) y la extensión de resultados tipo Cobham a sistemas mixtos (base-$k$ y Zeckendorf).

En resumen, el artículo establece un marco robusto para el estudio de la regularidad en sistemas de numeración de Pisot, demostrando que la estructura algebraica de las ecuaciones de Mahler sigue siendo una herramienta poderosa incluso cuando la linealidad de la base se pierde, siempre que se introduzcan las correcciones adecuadas mediante autómatas.