La constante de Tribonacci y autómatas finitos

Información Básica

• ID del Artículo: 2510.10834
• Título: La constante de Tribonacci y autómatas finitos
• Autor: Jeffrey Shallit (Universidad de Waterloo)
• Clasificación: cs.FL cs.DM math.NT
• Fecha de Publicación: 21 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.10834

Resumen

Este artículo demuestra que no existe un autómata capaz de aceptar en paralelo las representaciones de Tribonacci de n y x, donde ψ = 1.839··· es la constante de Tribonacci, y x = ⌊nψ⌋. De manera similar, no existe un autómata de Tribonacci capaz de generar la palabra característica de Sturmian con pendiente ψ-1.

Antecedentes y Motivación de la Investigación

Contexto del Problema

1. Casos de éxito en la situación de Fibonacci: Para la razón áurea φ = (1+√5)/2, la secuencia (⌊φn⌋)_{n≥0} es sincrónica de Fibonacci, es decir, existe un autómata finito que puede aceptar en paralelo las representaciones de Zeckendorf de n y x si y solo si x = ⌊φn⌋.
2. Pregunta de generalización natural: ¿Existen propiedades similares para generalizaciones de números de Fibonacci (como los números de Tribonacci)?
3. Intersección de teoría de números y teoría de autómatas: Este problema implica conexiones profundas entre propiedades de números irracionales en teoría de números y teoría de autómatas finitos en informática teórica.

Motivación de la Investigación

• Explorar si la generalización de recurrencias de segundo orden (Fibonacci) a recurrencias de tercer orden (Tribonacci) mantiene la reconocibilidad de autómatas
• Comprender las diferencias fundamentales entre secuencias de recurrencia de orden superior y autómatas finitos
• Proporcionar fundamentos teóricos para problemas relacionados de teoría lógica y decidibilidad

Contribuciones Principales

1. Resultado negativo principal: Se demuestra que la secuencia (⌊ψn⌋)_{n≥0} no es sincrónica de Tribonacci, donde ψ es la constante de Tribonacci
2. No-automaticidad de secuencias de Sturmian: Se demuestra que la correspondiente secuencia característica de Sturmian no es automática de Tribonacci
3. Impacto en teoría lógica: Se demuestra que la función n → ⌊ψn⌋ no puede expresarse en la teoría de primer orden ⟨N,+,V'(n)⟩
4. Perspectivas matemáticas profundas: Se revela que la diferencia fundamental entre los casos de segundo y tercer orden radica en la ausencia de periodicidad

Explicación Detallada de Métodos

Definición de Tareas

Se estudian dos clases de problemas de autómatas:

1. Autómatas síncronos: Aceptan funciones f: N → N, con entrada en paralelo de n y x (representación de Tribonacci), aceptando si y solo si x = f(n)
2. Autómatas con salida (DFAO): Calculan secuencias (a_n)_{n≥0}, con entrada de la representación de Tribonacci de n, produciendo a_n como salida

Construcciones Matemáticas Centrales

Propiedades de los Números de Tribonacci

• Relación de recurrencia: T_i = T_ + T_ + T_, con valores iniciales T_0 = 0, T_1 = 1, T_2 = 1
• Expresión de forma cerrada: T_n = c_1ψ^n + c_2α^n + c_3β^n
• Donde ψ ≈ 1.839 es la raíz real de X³ - X² - X - 1, y α,β son raíces complejas conjugadas

Construcciones Técnicas Clave

Se definen:

• a(n) = ⌊ψn⌋
• b(n) = ⌊(ψ-1)(n+2)⌋ - ⌊(ψ-1)(n+1)⌋
• c(n) = ⌊ψ(n+1)⌋ - ⌊ψn⌋

Estrategia de Demostración

Línea Principal de Demostración

1. Argumento de reducción: Se demuestra que si a(n) es sincrónica, entonces b(n) es automática
2. Distinción de estados: Se construyen infinitos estados de autómata distinguibles
3. Aplicación del teorema de Myhill-Nerode: Se utiliza la distinción de estados para demostrar que no existe un autómata finito

Análisis Matemático Clave

Se utiliza la propiedad de la parte fraccionaria:

{ψT_n} = {2Re c_2(ψ-α)α^n}

Donde:

• γ = arg c_2(ψ-α) = 2.536155···
• ζ = arg α = 4.10695···
• El valor de c(T_n) depende de v(n) := γ + nζ mod 2π

Configuración Experimental

Métodos de Verificación Teórica

Este artículo es principalmente una demostración teórica, utilizando métodos de verificación que incluyen:

1. Cálculo numérico: Verificación de valores exactos de coeficientes complejos y parámetros
2. Aplicación del teorema de Kronecker: Demostración de propiedades de densidad
3. Verificación de independencia lineal: Confirmación de que ζ y 2π son linealmente independientes sobre los racionales

Cálculo de Parámetros Clave

• |c_2(ψ-α)| = 0.608085···
• |α| = 0.73735···
• Se verificó que |2Re c_2(ψ-α)α^n| < 2-ψ para n ≥ 5

Resultados Experimentales

Resultados Teóricos Principales

Demostración Completa del Teorema 1

Se demuestra que:

1. La secuencia (a(n))_{n≥0} no es sincrónica de Tribonacci
2. La secuencia (b(n))_{n≥0} no es automática de Tribonacci

Demostración Constructiva de Distinción de Estados

• Para todo i < j, existe k tal que c(T_{i+k}) ≠ c(T_{j+k})
• Se utiliza el teorema de Kronecker para garantizar la existencia de infinitos tales k
• Se construyeron exitosamente infinitos estados distinguibles

Resultados de Teoría Lógica

Teorema 2

Se demuestra que la función n → ⌊ψn⌋ no puede expresarse en la teoría de primer orden ⟨N,+,V'(n)⟩, donde V'(n) es el número de Tribonacci más pequeño en la representación de Tribonacci de n.

Trabajo Relacionado

Resultados Conocidos en el Caso de Fibonacci

• Mousavi et al. e Hieronymi demostraron independientemente que n → ⌊φn⌋ es expresable en la estructura correspondiente
• Khani y Zarei también obtuvieron resultados similares mediante métodos diferentes
• Existen propiedades similares para números irracionales cuadráticos arbitrarios

Teoría de Sistemas Numéricos

• Teoría de representación de Zeckendorf
• Teoría de representación de secuencias de Fibonacci generalizadas
• Temas relacionados con números de Pisano

Conclusiones y Discusión

Conclusiones Principales

1. Diferencia fundamental: Existen diferencias esenciales entre los casos de Fibonacci y Tribonacci
2. Ausencia de periodicidad: El signo de F_{n+1} - φF_n es periódico, pero el signo de T_{n+1} - ψT_n no lo es
3. Existencia de resultados aproximados: Aunque los resultados exactos no son alcanzables, existen autómatas aproximados con error dentro de ±1

Limitaciones

1. Resultados negativos: Principalmente resultados negativos, sin proporcionar métodos de construcción alternativos
2. Específico de Tribonacci: Los resultados son específicos de recurrencias de tercer orden, requiriendo análisis separado para órdenes superiores
3. Precisión de métodos aproximados: Los límites de error del autómata aproximado pueden no ser suficientemente precisos

Direcciones Futuras

1. Otros números de Pisano: Investigación de sistemas numéricos basados en otros números de Pisano cúbicos
2. Generalizaciones de orden superior: Consideración de secuencias de recurrencia de k-ésimo orden
3. Algoritmos aproximados: Mejora de la precisión y eficiencia de autómatas aproximados

Evaluación Profunda

Fortalezas

1. Profundidad teórica: Se revela el impacto fundamental del orden de recurrencia en la reconocibilidad de autómatas
2. Técnicas de demostración: Combinación ingeniosa de análisis complejo, teoría de números y teoría de autómatas
3. Completitud: No solo se demuestran los resultados principales, sino que también se analiza el impacto en teoría lógica
4. Rigor matemático: El proceso de demostración es riguroso y los cálculos son precisos

Deficiencias

1. Insuficiencia constructiva: Los resultados son principalmente negativos en términos de existencia, careciendo de construcciones positivas
2. Aplicabilidad limitada: Los resultados son principalmente teóricos, con valor práctico limitado
3. Generalización: La generalización de métodos a otros problemas similares requiere verificación adicional

Impacto

1. Contribución teórica: Proporciona perspectivas importantes para investigación interdisciplinaria entre teoría de autómatas y teoría de números
2. Valor metodológico: Las técnicas de demostración tienen valor de referencia para problemas relacionados
3. Determinación de límites: Establece claramente los límites de aplicabilidad de métodos de autómatas

Escenarios Aplicables

1. Investigación teórica: Teoría de números, teoría de autómatas, teoría de lenguajes formales
2. Diseño de algoritmos: Diseño de algoritmos numéricos que deben considerar limitaciones de autómatas
3. Teoría de complejidad: Investigación de problemas de decidibilidad relacionados

Referencias Bibliográficas

El artículo cita 17 referencias importantes, abarcando:

• Textos clásicos de teoría de autómatas (Hopcroft & Ullman)
• Trabajos pioneros sobre autómatas de Fibonacci (Bruyère et al.)
• Fundamentos de teoría de números (Hardy & Wright)
• Investigaciones recientes relacionadas (Mousavi et al., Hieronymi et al.)

Evaluación General: Este es un artículo teórico de alta calidad que, mediante demostraciones matemáticas rigurosas, revela las diferencias fundamentales entre los casos de Fibonacci y Tribonacci en términos de reconocibilidad de autómatas. Aunque los resultados son principalmente negativos, proporciona contribuciones teóricas importantes para el desarrollo del campo, siendo particularmente significativo para comprender la relación entre secuencias de recurrencia y autómatas finitos.