Cobham's theorem for the Gaussian integers

技术摘要：高斯整数的 Cobham 定理

问题陈述
Cobham 定理是自动机理论和数论中的一个基础性结果，它指出：一个自然数序列既是 $k$-自动的又是 $\ell$-自动的（其中 $k$ 和 $\ell$ 是乘法独立的整数），当且仅当该序列是最终周期的。虽然该定理已被推广到各种逻辑和动力学语境中，但在从整数 $\mathbb{Z}$ 向欧几里得整环，特别是高斯整数 $\mathbb{Z}[i]$ 的扩展方面，仍存在显著空白。

Hansel 和 Safer 此前的研究探讨了以基 $\alpha = -m + i$（其中 $m \ge 1$）且具有非负整数数字集的数制系统。他们证明了如果一个子集 $S \subset \mathbb{Z}[i]$ 能被两种这样的基识别，则该集合是稠密的（syndetic）。他们曾猜想，这样的集合必须是最终周期的（即在两个 $\mathbb{Z}$-线性无关的向量平移下，在有限集之外保持不变）。然而，他们的证明依赖于四指数猜想（Four Exponentials Conjecture），这是一个深奥且尚未被证实的解析数论假设，使得该猜想悬而未决。

方法论
作者提供了一个针对高斯整数的 Cobham 定理证明，该证明不依赖于四指数猜想。他们的方法将该定理推广到了最大规模的高斯数制族（任何有限生成数字集），并消除了对深层解析数论的依赖。

核心方法论包括：

1. $\mathbb{Z}[i]$ 中的狄利克雷逼近（Dirichlet Approximation）： 作者并未依赖于乘法群 $\langle \alpha, \beta \rangle$ 在 $\mathbb{C}$ 中的稠密性（这需要四指数猜想），而是利用了一个较弱的结果：即 $1$在由两个乘法独立的高斯整数生成的乘法群中不是孤立点。这是通过引理 3 建立的，该引理证明了如果$1$ 是孤立的，则该群是离散的，从而意味着乘法依赖性。
2. 泵引理与返回数（Pumping Lemma and Return Numbers）： 作者分析了作用于高斯整数展开式的有限状态自动机（DFAOs）的结构。他们定义了回到自动机特定状态的“返回数”。通过对自动机状态应用 van der Waerden 定理，他们识别出了对应于返回数的算术级数索引。
3. 共线性分析： 一个关键步骤是引理 14，它表明如果一个返回数序列位于一条直线上（即共线），则该基必须是某个整数的根。因此，如果该基不是某个整数的根，则返回数必须是非共线的。这使得构造两个 $\mathbb{Z}$-线性无关的周期成为可能。
4. 周期传播： 利用一种适用于高斯整数的 Fine 和 Wilf 定理版本（引理 18 和 19），作者展示了如何将重叠球体上的局部周期性（步进周期性）传播到全局周期性。他们构造了一个由球体覆盖的 $\mathbb{Z}[i]$，其中配置表现出由非共线返回数导出的特定周期。

主要贡献与结果
主要结果是定理 1，它指出：

令 $\alpha$ 和 $\beta$ 为两个乘法独立的高斯整数，且 $|\alpha|, |\beta| > 1$。如果 $\alpha$ 或 $\beta$ 其中之一不是整数的根，那么配置 $(a_z)_{z \in \mathbb{Z}[i]}$ 是 $\alpha$-和 $\beta$-自动的，当且仅当它是最终周期的。

关键技术发现包括：

• 解决 Hansel 和 Safer 的猜想： 本文证明了由形式为 $-m+i$ 的基识别的集合是最终周期的这一猜想。由于根据 Niven 定理，对于 $m > 1$，$-m+i$ 永远不是整数的根，因此满足定理 1 的条件。
• 条件的必要性： 作者表明“其中一个基不是整数的根”这一条件是尖锐的（sharp）。如果两个基都是整数的根，则可能存在非最终周期的配置（例如，$\mathbb{N}$ 的特征函数在 $\alpha$ 是整数的根时是 $\alpha$-自动的）。
• 数制系统的推广： 该证明适用于任何具有生成数制系统的有限数字集 $D$，而不局限于 Hansel 和 Safer 所考虑的“自然”非负整数数字集。
• 关于共轭的推论： 本文确立了，如果一个集合 $U \subset \mathbb{Z}[i]$ 是 $\beta$-自动的且等于其复共轭（$U = \bar{U}$），并且不是最终周期的，那么 $\beta$ 必须是整数的根。

意义
该论文声称在不依赖未证实的解析猜想的情况下，解决了高斯整数的 Cobham 定理扩展问题。通过证明该结果基于自动机基本性质和高斯整数的几何性质（特别是 $1$ 在乘法群中的非孤立性），作者“为推广到一般数环的 Cobham 定理开辟了道路”。

这项工作将 Cobham-Semenov 定理推广到了高斯数制。它还与 Cabezas 和 Petite 关于常数形状替换（constant shape substitutions）的工作相联系，这意味着由非整数根的高斯基生成的非平凡配置，无法通过标准的 $(k, k)$-自动配置来复制。作者指出，虽然这只是第一步，但向其他整数环（如 $\mathbb{Z}[\zeta]$ 或二次整数环）的扩展仍是未来研究的一个自然方向。