Cobham's theorem for the Gaussian integers

Resumo Técnico: O Teorema de Cobham para os Inteiros Gaussianos

Enunciado do Problema
O Teorema de Cobham é um resultado fundamental na teoria dos autômatos e na teoria dos números, afirmando que uma sequência de números naturais é tanto $k$-automática quanto $\ell$-automática (onde $k$ e $\ell$ são inteiros multiplicativamente independentes) se, e somente se, a sequência for eventualmente periódica. Embora este teorema tenha sido generalizado para vários contextos lógicos e dinâmicos, uma lacuna significativa permanecia em sua extensão dos inteiros $\mathbb{Z}$ para os domínios euclidianos, especificamente os inteiros gaussianos $\mathbb{Z}[i]$.

Trabalhos anteriores por Hansel e Safer abordaram sistemas de numeração com base $\alpha = -m + i$ (onde $m \ge 1$) e conjuntos de dígitos de inteiros não negativos. Eles demonstraram que, se um subconjunto $S \subset \mathbb{Z}[i]$ é reconhecível por duas dessas bases, o conjunto é sindético. Eles conjecturaram que tal um conjunto deve ser eventualmente periódico (ou seja, invariante sob translação por dois vetores $\mathbb{Z}$-linearmente independentes fora de um conjunto finito). No entanto, sua prova dependia da Conjectura dos Quatro Exponenciais, uma hipótese profunda e não provada da teoria analítica dos números, deixando a conjectura não resolvida.

Metodologia
Os autores fornecem uma prova do teorema de Cobham para os inteiros gaussianos que não depende da Conjectura dos Quatro Exponenciais. A abordagem deles generaliza o teorema para a maior família possível de numerações gaussianas (qualquer conjunto de dígitos gerador finito) e remove a dependência de teoria profunda dos números analíticos.

A metodologia central envolve:

1. Aproximação de Dirichlet em $\mathbb{Z}[i]$: Em vez de depender da densidade do grupo multiplicativo $\langle \alpha, \beta \rangle$ em $\mathbb{C}$ (o que requer a Conjectura dos Quatro Exponenciais), os autores utilizam um resultado mais fraco: que $1$ não é um ponto isolado no grupo multiplicativo gerado por dois inteiros gaussianos multiplicativamente independentes. Isso é estabelecido via o Lema 3, que prova que, se $1$ fosse isolado, o grupo seria discreto, implicando dependência multiplicativa.
2. Lema de Bombeamento (Pumping Lemma) e Números de Retorno: Os autores analisam a estrutura de autômatos finitos de estados determinísticos (DFAOs) atuando sobre expansões de inteiros gaussianos. Eles definem "números de retorno" a estados específicos no autômato. Ao aplicar o teorema de van der Waerden aos estados dos autômatos, eles identificam progressões aritméticas de índices correspondentes a números de retorno.
3. Análise de Colinearidade: Um passo crítico envolve o Lema 14, que demonstra que, se uma sequência de números de retorno reside sobre uma reta (é colinear), a base deve ser uma raiz de um inteiro. Consequentemente, se a base não é uma raiz de um inteiro, os números de retorno devem ser não colineares. Isso permite a construção de dois períodos $\mathbb{Z}$-linearmente independentes.
4. Propagação de Período: Usando uma versão do teorema de Fine e Wilf adaptada para inteiros gaussianos (Lemmas 18 e 19), os autores mostram como a periodicidade local (periodicidade de passo) em bolas sobrepostas pode ser propagada para a periodicidade global. Eles constroem uma cobertura de $\mathbb{Z}[i]$ por bolas onde a configuração exibe períodos específicos derivados dos números de retorno não colineares.

Principais Contribuições e Resultados
O resultado primário é o Teorema 1, que afirma:

Sejam $\alpha$ e $\beta$ dois inteiros gaussianos multiplicativamente independentes com $|\alpha|, |\beta| > 1$. Se um de $\alpha$ ou $\beta$ não é a raiz de um inteiro, então uma configuração $(a_z)_{z \in \mathbb{Z}[i]}$ é $\alpha$- e $\beta$-automática se, e somente se, for eventualmente periódica.

Descobertas técnicas principais incluem:

• Resolução da Conjectura de Hansel e Safer: O artigo prova a conjectura de que conjuntos reconhecíveis por bases da forma $-m+i$ são eventualmente periódicos. Como $-m+i$ nunca é uma raiz de um inteiro para $m > 1$ (pelo Teorema de Niven), a condição do Teorema 1 é satisfeita.
• Necessidade da Condição: Os autores mostram que a condição "uma base não é raiz de um inteiro" é rigorosa. Se ambas as bases forem raízes de inteiros, configurações não eventualmente periódicas podem existir (por exemplo, a função característica de $\mathbb{N}$ é $\alpha$-automática se $\alpha$ for uma raiz de um inteiro).
• Generalização de Sistemas de Numeração: A prova é válida para qualquer conjunto de dígitos finito $D$ que gere um sistema de numeração, não apenas os "naturais" conjuntos de dígitos de inteiros não negativos considerados por Hansel e Safer.
• Corolário sobre Conjugação: O artigo estabelece que, se um conjunto $U \subset \mathbb{Z}[i]$ é $\beta$-automático e igual ao seu conjugado complexo ($U = \bar{U}$), e não é eventualmente periódico, então $\beta$ deve ser uma raiz de um inteiro.

Significância
O artigo afirma resolver a extensão do teorema de Cobham para os inteiros gaussianos sem depender de conjecturas analíticas não provadas. Ao demonstrar que o resultado se baseia em propriedades elementares de autômatos e da geometria dos inteiros gaussianos (especificamente a não isolação de $1$ no grupo multiplicativo), os autores "abrem o caminho para Cobham para anéis numéricos gerais".

O trabalho generaliza o teorema de Cobham-Semenov para numerações gaussianas. Ele também se conecta ao trabalho de Cabezas e Petite sobre substituições de forma constante, implicando que configurações não triviais geradas por bases gaussianas que não são raízes de inteiros não podem ser replicadas por configurações $(k, k)$-automáticas padrão. Os autores observam que, embora este seja um primeiro passo, a extensão para outros anéis de inteiros (como $\mathbb{Z}[\zeta]$ ou anéis de inteiros quadráticos) permanece uma direção natural para investigações futuras.