Beatty Sequences for a Quadratic Irrational: Decidability and Applications

Aquí presento un resumen técnico detallado del artículo "Beatty Sequences for a Quadratic Irrational: Decidability and Applications" de Luke Schaeffer, Jeffrey Shallit y Stefan Zorcic.

1. Problema y Contexto

El artículo aborda la teoría de los sucesiones de Beatty inhomogéneas, definidas como la secuencia $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$, donde $\alpha$ es un número irracional y $\beta$ es un número real. El problema central es determinar la decidibilidad de la teoría lógica de primer orden de estas secuencias cuando se combinan con la operación de adición.

Históricamente, se sabía que para ciertos casos específicos (como el número áureo $\phi$ o secuencias de Sturmian asociadas a números cuadráticos), la teoría era decidible. Sin embargo, faltaba una caracterización general y un método sistemático para demostrar que, para cualquier par de números $\alpha, \beta$ pertenecientes al mismo cuerpo cuadrático $\mathbb{Q}(\gamma)$, la relación $y = \lfloor n\alpha + \beta \rfloor$ es computable mediante autómatas finitos. Además, el artículo busca aplicar esta decidibilidad a problemas abiertos en teoría de números aditiva y combinatoria.

2. Metodología

La metodología se basa en la intersección de la teoría de autómatas, la teoría de números (específicamente representaciones numéricas) y la lógica matemática. Los pilares fundamentales son:

• Representación de Ostrowski: Utilizan el sistema de numeración de Ostrowski basado en un número irracional cuadrático $\gamma$. En este sistema, cada entero natural se representa de manera única como una combinación lineal de los convergentes de la fracción continua de $\gamma$.
• Secuencias Sincronizadas: Introducen el concepto de secuencia sincronizada. Una secuencia $(s_n)$ es sincronizada si existe un autómata finito que, al recibir en paralelo las representaciones de $n$ e $y$ en el sistema de numeración de Ostrowski, acepta si y solo si $y = s_n$.
• El Software Walnut: Utilizan Walnut, un sistema de demostración de teoremas de código abierto que implementa procedimientos de decisión para secuencias automáticas y sincronizadas. Walnut permite traducir fórmulas de lógica de primer orden en autómatas finitos.
• Propiedades de Cierre: Se aprovechan las propiedades de cierre de las secuencias sincronizadas (suma, composición, funciones lineales) para construir autómatas complejos a partir de bloques básicos.

3. Contribuciones Clave y Resultados Principales

A. Teorema de Sincronización (Teorema 9)

El resultado central del artículo es la demostración de que si $\alpha$ y $\beta$ pertenecen al mismo cuerpo cuadrático $\mathbb{Q}(\gamma)$, donde $1/\gamma$ tiene una fracción continua puramente periódica, entonces la secuencia inhomogénea de Beatty $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ es $\gamma$-Ostrowski sincronizada.

• Esto implica que existe un autómata finito que reconoce la relación $y = \lfloor n\alpha + \beta \rfloor$ cuando $n$ e $y$ se codifican en el sistema de Ostrowski basado en $\gamma$.
• Se proporciona una prueba constructiva que permite generar este autómata algorítmicamente.

B. Decidibilidad de la Teoría Lógica (Corolario 11)

Como consecuencia directa del teorema anterior y de resultados previos sobre la adición en sistemas de numeración de Ostrowski, se demuestra que:

• La teoría de primer orden de los números naturales con adición y la función $n \mapsto \lfloor n\alpha + \beta \rfloor$ es decidible para $\alpha, \beta \in \mathbb{Q}(\gamma)$.
• Esto significa que cualquier afirmación lógica sobre estas secuencias (usando cuantificadores, adición, etc.) puede ser verificada como verdadera o falsa mediante un algoritmo.

C. Aplicaciones a Problemas Abiertos

Los autores utilizan sus técnicas para resolver o verificar múltiples problemas abiertos:

1. Bases Aditivas (Sección 7): Se demuestra que es decidible si una secuencia de Beatty forma una base aditiva (o base aditiva asintótica) de orden $r$. Se calcula efectivamente el menor $h$ tal que todo entero suficientemente grande es suma de $h$ elementos de la secuencia.
2. Conjeturas de Reble (Sección 8): Se prueban conjeturas sobre la existencia de progresiones aritméticas monocromáticas de longitud 3 en la palabra de Fibonacci, relacionadas con las secuencias OEIS A189377, A189378 y A189379.
3. Pregunta de Graham (Sección 9): Se demuestra la decidibilidad de cuándo un conjunto finito de pares $(\alpha_i, \beta_i)$ forma una "familia de cobertura eventual" (ECF), es decir, cuándo cubren exactamente una vez a los enteros suficientemente grandes.
4. Secuencias de Hildebrand et al. (Sección 10): Se proporciona una caracterización explícita y una prueba automática de una secuencia estudiada por Hildebrand, Li, Li y Xie, mostrando que la diferencia entre dos secuencias complementarias está acotada.
5. Problema de "Swappage" de Kimberling (Sección 11): Se ofrece una prueba alternativa y automática de conjeturas sobre las secuencias de "swappage" (intercambio) de Kimberling relacionadas con las secuencias de Wythoff.
6. Conjuntos de Complemento de Sumas (Sección 12): Se demuestra que el conjunto de complementos de sumas para números cuadráticos es automático en el sistema de Ostrowski.
7. Fracciones Decimales (Sección 14): Se desarrolla un método para comparar partes fraccionarias $\{ \alpha x + \beta \}$ dentro de la lógica de primer orden, resolviendo problemas sobre el orden cíclico de partes fraccionarias.

D. Converse (Teorema 28)

El artículo también prueba la recíproca del Teorema 9: si la secuencia $(\lfloor n\alpha + \beta \rfloor)$ es sincronizada en el sistema de Ostrowski de un $\gamma$ cuadrático, entonces necesariamente $\alpha$ y $\beta$ deben pertenecer a $\mathbb{Q}(\gamma)$.

4. Significado e Impacto

• Simplicidad y Automatización: La principal innovación es la simplicidad del método. En lugar de pruebas de decidibilidad complejas y ad-hoc, el enfoque basado en autómatas sincronizados y el software Walnut permite verificar teoremas complejos en segundos.
• Unificación: Unifica el tratamiento de diversas secuencias (Beatty, Sturmian, Wythoff) bajo un marco teórico común basado en cuerpos cuadráticos y representaciones de Ostrowski.
• Resolución de Problemas Abiertos: El artículo resuelve múltiples conjeturas que habían permanecido abiertas en la literatura de teoría de números y combinatoria en palabras, demostrando la potencia de los métodos automáticos en matemáticas puras.
• Herramienta Computacional: Refuerza el papel de Walnut como una herramienta esencial para la investigación en teoría de números computacional, permitiendo a los investigadores no solo verificar conjeturas, sino también descubrir nuevas propiedades y caracterizaciones explícitas de secuencias.

En resumen, el artículo establece un marco robusto y decidible para el estudio de las secuencias de Beatty inhomogéneas generadas por números cuadráticos, transformando problemas teóricos profundos en tareas computacionales manejables mediante autómatas finitos.