Cobham's theorem for the Gaussian integers

Sintesi Tecnica: Il Teorema di Cobham per gli Interi Gaussiani

Enunciato del Problema
Il Teorema di Cobham è un risultato fondamentale nella teoria degli automi e nella teoria dei numeri, il quale afferma che una successione di numeri naturali è sia $k$-automatica che $\ell$-automatica (dove $k$ e $\ell$ sono interi multipliamente indipendenti) se e solo se la successione è eventualmente periodica. Sebbene questo teorema sia stato generalizzato in vari contesti logici e dinamici, rimaneva una lacuna significativa nella sua estensione dagli interi $\mathbb{Z}$ ai domini euclidei, specificamente agli interi gaussiani $\mathbb{Z}[i]$.

Lavori precedenti di Hansel e Safer hanno affrontato i sistemi di numerazione con base $\alpha = -m + i$ (dove $m \ge 1$) e insiemi di cifre di interi non negativi. Essi hanno dimostrato che se un sottoinsieme $S \subset \mathbb{Z}[i]$ è riconoscibile da due tali basi, l'insieme è sindetico. Avevano ipotizzato che un tale insieme debba essere eventualmente periodico (ovvero invariante per traslazione rispetto a due vettori $\mathbb{Z}$-linearmente indipendenti al di fuori di un insieme finito). Tuttavia, la loro dimostrazione si basava sulla Congettura delle Quattro Esponenziali, un'ipotesi profonda e non provata della teoria analitica dei numeri, lasciando la congettura irrisolta.

Metodologia
Gli autori forniscono una dimostrazione del teorema di Cobham per gli interi gaussiani che non dipende dalla Congettura delle Quattro Esponenziali. Il loro approccio generalizza il teorema alla più ampia famiglia possibile di numerazioni gaussiane (qualsiasi insieme di cifre finito generatore) e rimuove la dipendenza dalla profonda teoria analitica dei numeri.

La metodologia principale prevede:

1. Approssimazione di Dirichlet in $\mathbb{Z}[i]$: Invece di fare affidamento sulla densità del gruppo moltiplicativo $\langle \alpha, \beta \rangle$ in $\mathbb{C}$ (il che richiederebbe la Congettura delle Quattro Esponenziali), gli autori utilizzano un risultato più debole: che $1$ non sia un punto isolato nel gruppo moltiplicativo generato da due interi gaussiani multiplamente indipendenti. Ciò è stabilito dal Lemma 3, che dimostra che se $1$ fosse isolato, il gruppo sarebbe discreto, implicando una dipendenza moltiplicativa.
2. Pumping Lemma e Numeri di Ritorno: Gli autori analizzano la struttura degli automi a stati finiti (DFAO) che agiscono sulle espansioni degli interi gaussiani. Definiscono "numeri di ritorno" a specifici stati dell'automa. Applicando il teorema di van der Waerden agli stati degli automi, identificano progressioni aritmetiche di indici corrispondenti ai numeri di ritorno.
3. Analisi della Collinearità: Un passaggio critico riguarda il Lemma 14, che dimostra che se una successione di numeri di ritorno giace su una retta (è collineare), allora la base deve essere una radice di un intero. Di conseguenza, se la base non è una radice di un intero, i numeri di ritorno devono essere non collineari. Ciò permette la costruzione di due periodi $\mathbb{Z}$-linearmente indipendenti.
4. Propagazione del Periodo: Utilizzando una versione del teorema di Fine e Wilf adattata per gli interi gaussiani (Lemmi 18 e 19), gli autori mostrano come la periodicità locale (periodicità di passo) su sfere sovrapposte possa essere propagata a una periodicità globale. Costruiscono una copertura di $\mathbb{Z}[i]$ tramite sfere dove la configurazione esibisce periodi specifici derivati dai numeri di ritorno non collineari.

Contributi Chiave e Risultati
Il risultato primario è il Teorema 1, che afferma:

Sia $\alpha$ e $\beta$ due interi gaussiani multiplamente indipendenti con $|\alpha|, |\beta| > 1$. Se uno tra $\alpha$ o $\beta$ non è la radice di un intero, allora una configurazione $(a_z)_{z \in \mathbb{Z}[i]}$ è $\alpha$- e $\beta$-automatica se e solo se è eventualmente periodica.

Risultati tecnici chiave includono:

• Risoluzione della Congettura di Hansel e Safer: Il documento prova la congettura secondo cui gli insiemi riconoscibili da basi della forma $-m+i$ sono eventualmente periodici. Poiché $-m+i$ non è mai una radice di un intero per $m > 1$ (per il teorema di Niven), la condizione del Teorema 1 è soddisfatta.
• Necessità della Condizione: Gli autori mostrano che la condizione "una base non è radice di un intero" è stringente. Se entrambe le basi sono radici di interi, possono esistere configurazioni non eventualmente periodiche (ad esempio, la funzione caratteristica di $\mathbb{N}$ è $\alpha$-automatica se $\alpha$ è una radice di un intero).
• Generalizzazione dei Sistemi di Numerazione: La dimostrazione è valida per qualsiasi insieme di cifre finito $D$ che generi un sistema di numerazione, non solo per i "naturali" insiemi di cifre di interi non negativi considerati da Hansel e Safer.
• Corollario sulla Coniugazione: Il documento stabilisce che se un insieme $U \subset \mathbb{Z}[i]$ è $\beta$-automatico ed è uguale al suo coniugato complesso ($U = \bar{U}$), e non è eventualmente periodico, allora $\beta$ deve essere una radice di un intero.

Significato
Il lavoro sostiene di risolvere l'estensione del teorema di Cobham agli interi gaussiani senza fare affidamento su congetture analitiche non provate. Dimostrando che il risultato si basa su proprietà elementari degli automi e della geometria degli interi gaussiani (specificamente la non-isolazione di 1 nel gruppo moltiplicativo), gli autori "aprono la strada a Cobham per gli anelli numerici generali".

L'opera generalizza il teorema di Cobham-Semenov alle numerazioni gaussiane. Essa si collega inoltre al lavoro di Cabezas e Petite sulle sostituzioni a forma costante, implicando che configurazioni non triviali generate da basi gaussiane che non sono radici di interi non possono essere replicate da configurazioni standard $(k, k)$-automatiche. Gli autori osservano che, sebbene questo sia un primo passo, l'estensione ad altri anelli di interi (come $\mathbb{Z}[\zeta]$ o gli anelli quadratici interi) rimane una naturale direzione per ricerche future.