Balanced Fibonacci word rectangles, and beyond

Resumo Técnico: Retângulos de Palavras de Fibonacci Balanceados e Além

1. Problema e Contexto

O artigo investiga as propriedades de "equilíbrio" (balanceamento) em matrizes retangulares infinitas geradas a partir de sequências de palavras (palavras infinitas). Especificamente, considera-se uma sequência infinita $(a_i)_{i \ge 0}$ sobre o alfabeto $\{0, 1\}$ (ou outros alfabetos) e define-se uma matriz infinita $A$ onde $a_{k,\ell} = a_{k+\ell}$.

O foco recai sobre os sub-retângulos $m \times n$ desta matriz, denotados por $A(i, m, n)$, que representam janelas deslocadas da sequência original. Define-se a soma total dos elementos de um retângulo como $T(i, m, n)$.

• Definição de Equilíbrio: Um par de dimensões $(m, n)$ é considerado balanceado se, ao variar o índice de início $i$, o número de ocorrências de cada símbolo (ou a soma total $T$) nos retângulos $A(i, m, n)$ assumir no máximo dois valores distintos.
• Motivação: Embora seja conhecido que palavras de Sturmian (como a palavra de Fibonacci) são balanceadas em 1D (blocos lineares), a generalização para 2D (retângulos) é mais complexa. Resultados anteriores (Anselmo et al.) mostraram que retângulos cujas dimensões máximas são números de Fibonacci são balanceados, mas a caracterização completa de quais pares $(m, n)$ são balanceados permanecia aberta.

2. Metodologia

Os autores empregam uma abordagem baseada em Teoria Automática e Lógica de Primeira Ordem, utilizando o software de verificação automática Walnut. A metodologia segue os seguintes passos:

1. Formulação Lógica: O critério de equilíbrio é expresso como uma fórmula na lógica de primeira ordem. Para palavras de Sturmian (associadas a irracionais quadráticos $\alpha$), a relação $x = \lfloor n\alpha \rfloor$ é expressível.
2. Construção de Autômatos: Utilizando o teorema de Cobham e generalizações para sistemas de numeração de Ostrowski, as fórmulas lógicas são traduzidas em autômatos finitos determinísticos.
3. Sistemas de Numeração:
   • Para a Palavra de Fibonacci, utiliza-se o sistema de numeração de Zeckendorf (soma de números de Fibonacci distintos).
   • Para a Palavra de Tribonacci, utiliza-se o sistema de numeração de Tribonacci.
   • Para a Palavra de Thue-Morse, utiliza-se o sistema de base $(-2)$ para facilitar o cálculo de diferenças e somas, convertendo posteriormente para base 2.
4. Verificação Automática: O software Walnut constrói os autômatos que aceitam exatamente os pares $(m, n)$ que satisfazem a condição de equilíbrio, permitindo a verificação de conjecturas e a descoberta de padrões estruturais.

3. Contribuições e Resultados Principais

A. Palavra de Fibonacci (Seção 2 e 3)

• Caracterização Automática: Os autores provam que existe um algoritmo que, dado um irracional quadrático $\alpha$, constrói um autômato finito que aceita os pares $(m, n)$ balanceados para a matriz de Sturmian associada a $\alpha$.
• Autômato para Fibonacci: Para a palavra de Fibonacci ($\alpha = \gamma = (3-\sqrt{5})/2$), foi construído um autômato de 15 estados (Figura 1) que decide se um par $(m, n)$ é balanceado.
• Corolário de Anselmo et al.: A prova automática confirma que se $\max(m, n)$ é um número de Fibonacci, o retângulo é balanceado.
• Propriedades Estruturais:
  • Proposição 5: Estabelece simetrias e periodicidades nas dimensões balanceadas baseadas em intervalos de números de Fibonacci.
  • Proposição 6: Analisa a densidade dos pares balanceados, mostrando que para qualquer $m$, existe um $j$ pequeno (limitado por $F_{i+1}$) tal que $(m, n+j)$ é balanceado.
• Teorema 7: Fornece uma descrição "legível por humanos" das condições de equilíbrio baseada na expansão de Zeckendorf de $m$ e $n$, categorizando-os em 5 casos distintos.
• Retângulos Diversos (Seção 5): Demonstram que o número de valores distintos de $T(i, m, n)$ para $m=n=F_{3k/2}$ cresce linearmente com $k$ (especificamente $\Theta(k)$), provando que o número de valores distintos não é limitado por uma constante para todas as dimensões.

B. Palavra de Tribonacci (Seção 6)

• Contexto: A palavra de Tribonacci é 2-balanceada em 1D. O problema é caracterizar $(m, n)$ para que os retângulos sejam 2-balanceados.
• Resultados (Teorema 10):
  • Se $m=1$, todos os retângulos são 2-balanceados.
  • Se $m=2$, existe um autômato de 77 estados que aceita os $n$ válidos. A sequência de $n$ válidos é complexa e não possui uma descrição simples em inglês.
  • Se $m \ge 3$, não existem retângulos $m \times n$ que sejam 2-balanceados. A prova envolve a construção de dois retângulos que diferem em pelo menos 3 ocorrências de um símbolo específico em uma submatriz $3 \times 3$.

C. Palavra de Thue-Morse (Seção 7)

• Contexto: A palavra de Thue-Morse é gerada pelo morfismo $0 \to 01, 1 \to 10$.
• Propriedades de Limite (Teorema 11):
  • A diferença entre o número de 1s e a metade da área do retângulo é limitada: $|2|A(i, m, n)|_1 - mn| \le 4$.
  • O equilíbrio (diferença máxima entre retângulos) é sempre 1, 2, 3 ou 4.
• Autômato de Cálculo (Teorema 12): Os autores construíram um autômato de 92 estados que, dado $m$ e $n$ em binário, determina o equilíbrio exato do retângulo.
  • Nota Técnica: O cálculo foi intensivo, exigindo 100 GB de RAM e autômatos intermediários com mais de 32 milhões de estados.
• Caracterização Exata (Teorema 14): Para $m, n \ge 3$, o equilíbrio é exatamente 3 se e somente se ambos $m$ e $n$ forem ímpares.

4. Significado e Impacto

• Generalização de Resultados: O trabalho generaliza resultados conhecidos sobre a palavra de Fibonacci para qualquer palavra de Sturmian associada a um irracional quadrático, fornecendo um método algorítmico universal para determinar o equilíbrio de retângulos.
• Poder da Verificação Automática: O artigo demonstra o poder do software Walnut na resolução de problemas combinatórios complexos em teoria das palavras, onde provas manuais seriam extremamente difíceis ou impossíveis devido à complexidade dos padrões.
• Limites de Equilíbrio: Estabelece limites rigorosos sobre o comportamento de palavras clássicas (Fibonacci, Tribonacci, Thue-Morse) em dimensões superiores, mostrando que o equilíbrio perfeito (constante) é raro em 2D, mas o equilíbrio limitado (com poucos valores) é uma propriedade estrutural forte.
• Recursos Abertos: Todo o código Walnut e arquivos Maple utilizados estão disponíveis publicamente, permitindo a reprodução e extensão dos resultados pela comunidade científica.

Em suma, o artigo fornece uma caracterização completa e algorítmica do problema de equilíbrio de retângulos em palavras infinitas clássicas, unindo teoria dos números, teoria das palavras e autômatos finitos.