Beatty Sequences for a Quadratic Irrational: Decidability and Applications

Resumo Técnico: Sequências de Beatty para Irracionais Quadráticos: Decidibilidade e Aplicações

Autores: Luke Schaeffer, Jeffrey Shallit e Stefan Zorcic (Universidade de Waterloo).
Data: 3 de abril de 2026.

1. Problema e Contexto

O artigo aborda a teoria das sequências de Beatty, definidas como $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$, onde $\alpha$ e $\beta$ são números reais. O foco principal é investigar a decidibilidade da teoria lógica de primeira ordem dessas sequências quando $\alpha$ e $\beta$ pertencem ao mesmo corpo quadrático (ou seja, são da forma $a + b\sqrt{d}$ com $a,b,d \in \mathbb{Q}$).

Problemas anteriores estabeleceram a decidibilidade para casos específicos (como a razão áurea) ou para sequências de Sturmian, mas uma prova geral e simples para o caso inhomogêneo ($\beta \neq 0$) em corpos quadráticos, baseada em autômatos finitos, era uma lacuna que este trabalho preenche.

2. Metodologia

A abordagem central do artigo baseia-se na teoria dos autômatos finitos e na numeração de Ostrowski.

• Sincronização: Os autores definem uma sequência como "sincronizada" se existir um autômato finito que, ao receber em paralelo as representações de $n$ e $y$ em um sistema de numeração específico, aceite a entrada se e somente se $y = \lfloor n\alpha + \beta \rfloor$.
• Sistema de Numeração de Ostrowski: Utilizam-se as representações de Ostrowski baseadas em $\alpha$ (generalização do sistema de Zeckendorf/Fibonacci). Para irracional quadráticos $\gamma$, a relação de adição é computável por autômatos finitos neste sistema.
• Ferramenta Computacional (Walnut): O artigo demonstra a implementação prática dessas provas usando o software livre Walnut, um provador de teoremas para sequências automáticas. O Walnut permite expressar propriedades complexas em lógica de primeira ordem e verificar sua verdade ou gerar os autômatos correspondentes.

3. Principais Contribuições e Resultados Teóricos

• Teorema da Sincronização (Teorema 9):
  O resultado principal estabelece que, se $\gamma$ é um irracional quadrático tal que $1/\gamma$ possui uma fração contínua puramente periódica, e se $\alpha, \beta \in \mathbb{Q}(\gamma)$, então a sequência inhomogênea $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ é $\gamma$-Ostrowski sincronizada.

  • Implicação: Isso significa que a relação $y = \lfloor n\alpha + \beta \rfloor$ é reconhecível por um autômato finito.

• Decidibilidade da Teoria Lógica (Corolário 11):
  Como consequência direta da sincronização e dos resultados anteriores sobre adição em sistemas de Ostrowski, a teoria de primeira ordem dos números naturais com adição e a função $n \mapsto \lfloor n\alpha + \beta \rfloor$ é decidível. Isso fornece uma prova nova e simplificada para um resultado conhecido, mas anteriormente mais complexo.

• Teorema do Converse (Teorema 28):
  Os autores provam a recíproca: se a sequência $(\lfloor n\alpha + \beta \rfloor)$ é $\gamma$-Ostrowski sincronizada, então $\alpha$ e $\beta$ devem necessariamente pertencer ao corpo quadrático $\mathbb{Q}(\gamma)$. Além disso, fornecem um método computável para determinar $\alpha$ e $\beta$ a partir do autômato.

4. Aplicações e Solução de Problemas Abertos

O poder da metodologia é demonstrado através da resolução de diversos problemas em teoria dos números e combinatória:

• Bases Aditivas (Seção 7):
  É decidível determinar se o conjunto $\{\lfloor n\alpha + \beta \rfloor : n \ge 1\}$ forma uma base aditiva (ou base aditiva assintótica) de ordem $r$. O algoritmo encontra o menor $h$ tal que todo inteiro suficientemente grande pode ser escrito como soma de $h$ elementos da sequência.

  • Exemplo: Verificação de que certos inteiros são somas de dois elementos de uma sequência específica.

• Conjecturas de Don Reble (Seção 8):
  Prova automática de conjecturas relacionadas à existência de progressões aritméticas monocromáticas de comprimento 3 na palavra de Fibonacci (Sequências OEIS A189377, A189378, A189379).

• Pergunta de Graham (Seção 9):
  Resolve um caso especial da pergunta de Graham sobre famílias de cobertura eventual (ECF). É decidível se um conjunto finito de pares $(\alpha_i, \beta_i)$ no mesmo corpo quadrático cobre cada inteiro suficientemente grande exatamente uma vez.

• Sequências de Hildebrand et al. (Seção 10):
  Fornece uma caracterização explícita e prova de limites para a sequência $\tilde{c}(n)$, que é o $n$-ésimo inteiro positivo não contido na união de duas sequências de Beatty.

• Problema de "Swappage" de Kimberling (Seção 11):
  Fornece uma prova alternativa e automática para conjecturas de Kimberling sobre sequências derivadas das sequências de Wythoff (A141104, etc.), estabelecendo fórmulas fechadas para elas.

• Sequências Relacionadas a $\sqrt{2}$ (Seção 13):
  Constrói autômatos para sete sequências do OEIS relacionadas a $\sqrt{2}$ e prova conjecturas sobre elas, incluindo a igualdade entre A097509 e A276862.

• Partes Fracionárias (Seção 14):
  Desenvolve uma técnica para comparar partes fracionárias $\{ \alpha x + \beta \}$ usando autômatos, permitindo resolver problemas de ordenação circular de pontos na circunferência unitária.

5. Significado e Impacto

• Simplicidade Metodológica: O trabalho demonstra que problemas profundos em teoria dos números, que antes exigiam provas analíticas complexas ou ad-hoc, podem ser resolvidos de forma mecânica e sistemática usando autômatos finitos e lógica de primeira ordem.
• Generalização: Estende resultados conhecidos da razão áurea para qualquer irracional quadrático, unificando a teoria das sequências de Beatty inhomogêneas sob o guarda-chuva da sincronização de Ostrowski.
• Ferramenta Prática: A implementação no Walnut torna essas provas acessíveis e verificáveis. O artigo serve como um guia prático para pesquisadores aplicarem técnicas de autômatos a novas conjecturas em combinatória e teoria dos números.
• Limitações: O método é limitado a corpos quadráticos e depende do tamanho do período da fração contínua; períodos muito longos podem gerar autômatos com número excessivo de estados, tornando o cálculo computacionalmente inviável.

Em suma, o artigo estabelece uma ponte robusta entre a teoria dos números algorítmica e a teoria dos autômatos, fornecendo um quadro decidível para uma vasta classe de sequências definidas por funções de piso com coeficientes quadráticos.