Cobham's theorem for the Gaussian integers

Technical Summary: Cobham's Theorem for the Gaussian Integers

Problem Statement
Cobham's Theorem is a foundational result in automata theory and number theory, stating that a sequence of natural numbers is both $k$-automatic and $\ell$-automatic (where $k$ and $\ell$ are multiplicatively independent integers) if and only if the sequence is eventually periodic. While this theorem has been generalized to various logical and dynamical contexts, a significant gap remained in its extension from the integers $\mathbb{Z}$ to Euclidean domains, specifically the Gaussian integers $\mathbb{Z}[i]$.

Previous work by Hansel and Safer addressed numeration systems with base $\alpha = -m + i$ (where $m \ge 1$) and non-negative integer digit sets. They demonstrated that if a subset $S \subset \mathbb{Z}[i]$ is recognizable by two such bases, the set is syndetic. They conjectured that such a set must be eventually periodic (i.e., invariant under translation by two $\mathbb{Z}$-linearly independent vectors outside a finite set). However, their proof relied on the Four Exponentials Conjecture, a deep and unproven hypothesis in analytic number theory, leaving the conjecture unsettled.

Methodology
The authors provide a proof of Cobham's theorem for Gaussian integers that does not rely on the Four Exponentials Conjecture. Their approach generalizes the theorem to the largest possible family of Gaussian numerations (any finite generating digit set) and removes the dependency on deep analytic number theory.

The core methodology involves:

1. Dirichlet Approximation in $\mathbb{Z}[i]$: Instead of relying on the density of the multiplicative group $\langle \alpha, \beta \rangle$ in $\mathbb{C}$ (which requires the Four Exponentials Conjecture), the authors utilize a weaker result: that $1$ is not an isolated point in the multiplicative group generated by two multiplicatively independent Gaussian integers. This is established via Lemma 3, which proves that if $1$ were isolated, the group would be discrete, implying multiplicative dependence.
2. Pumping Lemma and Return Numbers: The authors analyze the structure of finite state automata (DFAOs) acting on Gaussian integer expansions. They define "return numbers" to specific states in the automaton. By applying van der Waerden's theorem to the states of the automata, they identify arithmetic progressions of indices corresponding to return numbers.
3. Collinearity Analysis: A critical step involves Lemma 14, which demonstrates that if a sequence of return numbers lies on a line (is collinear), the base must be a root of an integer. Consequently, if the base is not a root of an integer, the return numbers must be non-collinear. This allows the construction of two $\mathbb{Z}$-linearly independent periods.
4. Period Propagation: Using a version of Fine and Wilf's theorem adapted for Gaussian integers (Lemmas 18 and 19), the authors show that local periodicity (step-periodicity) on overlapping balls can be propagated to global periodicity. They construct a covering of $\mathbb{Z}[i]$ by balls where the configuration exhibits specific periods derived from the non-collinear return numbers.

Key Contributions and Results
The primary result is Theorem 1, which states:

Let $\alpha$ and $\beta$ be two multiplicatively independent Gaussian integers with $|\alpha|, |\beta| > 1$. If one of $\alpha$ or $\beta$ is not the root of an integer, then a configuration $(a_z)_{z \in \mathbb{Z}[i]}$ is $\alpha$- and $\beta$-automatic if and only if it is eventually periodic.

Key technical findings include:

• Resolution of Hansel and Safer's Conjecture: The paper proves the conjecture that sets recognizable by bases of the form $-m+i$ are eventually periodic. Since $-m+i$ is never a root of an integer for $m > 1$ (by Niven's Theorem), the condition of Theorem 1 is satisfied.
• Necessity of the Condition: The authors show that the condition "one base is not a root of an integer" is sharp. If both bases are roots of integers, non-eventually periodic configurations can exist (e.g., the characteristic function of $\mathbb{N}$ is $\alpha$-automatic if $\alpha$ is a root of an integer).
• Generalization of Numeration Systems: The proof holds for any finite digit set $D$ that generates a numeration system, not just the "natural" non-negative integer digit sets considered by Hansel and Safer.
• Corollary on Conjugation: The paper establishes that if a set $U \subset \mathbb{Z}[i]$ is $\beta$-automatic and equal to its complex conjugate ($U = \bar{U}$), and is not eventually periodic, then $\beta$ must be a root of an integer.

Significance
The paper claims to settle the extension of Cobham's theorem to Gaussian integers without relying on unproven analytic conjectures. By demonstrating that the result holds based on elementary properties of automata and the geometry of Gaussian integers (specifically the non-isolation of 1 in the multiplicative group), the authors "open up the way to Cobham for general number rings."

The work generalizes the Cobham-Semenov theorem to Gaussian numerations. It also connects to the work of Cabezas and Petite on constant shape substitutions, implying that non-trivial configurations generated by Gaussian bases that are not roots of integers cannot be replicated by standard $(k, k)$-automatic configurations. The authors note that while this is a first step, the extension to other rings of integers (such as $\mathbb{Z}[\zeta]$ or quadratic integer rings) remains a natural direction for future inquiry.