Additive systems for $\mathbb{Z}$ are undecidable

这是一份关于 Andrei Zabolotskii 的论文《Additive systems for Z are undecidable》（整数集上的加法系统是不可判定的）的详细技术总结。

1. 研究问题 (Problem)

论文的核心问题是研究**整数集 $\mathbb{Z}$ 上的加法系统（Additive Systems）**的存在性与判定性。

• 定义：给定一个集合族 $A = \{A_0, A_1, \dots\}$，其中每个 $A_i \subset \mathbb{Z}$ 且包含 0。如果对于任意整数 $n \in \mathbb{Z}$，都存在唯一的表示法 $n = a_0 + a_1 + \dots$（其中 $a_i \in A_i$，且只有有限个 $a_i$ 非零），则称 $A$ 为 $\mathbb{Z}$ 的一个加法系统。
• 背景：
  • 对于非负整数集 $\mathbb{N}_0$，de Bruijn 定理已经给出了完整的刻画：任何 $\mathbb{N}_0$ 的加法系统都是“英式数字系统”（British number systems）的收缩（contraction）。
  • 对于整数集 $\mathbb{Z}$，问题要困难得多。现有的文献主要集中在两个集合的分解（$Z = A \oplus B$），而对于无限集合族的情况，缺乏系统的理论框架。
• 核心挑战：给定一个特定的集合族（特别是具有某种自然结构的族），如何判定其和集是否覆盖整个 $\mathbb{Z}$ 且表示唯一？即判定该集合族是否构成一个“完备的”（complete）加法系统。

2. 方法论 (Methodology)

作者采用了一种从加法组合数学向**动力系统（Dynamical Systems）**视角的转换方法：

1. 引入“规范集合”（Canonical Collections）：

   • 作者定义了一类特殊的集合族，称为“规范集合”。这类集合由两个序列定义：基数序列 $(b_i)_{i \in \mathbb{N}_0}$（$b_i > 1$）和剩余系序列 $(T_i)_{i \in \mathbb{N}_0}$，其中 $T_i$ 是模 $b_i$ 的完全剩余系且包含 0。
   • 集合族的形式为 $\{T_0, b_0 T_1, b_0 b_1 T_2, \dots\}$。
   • 这类集合天然地推广了 $\mathbb{N}_0$ 上的英式数字系统以及 $\mathbb{Z}$ 上的经典例子（如负二进制系统、平衡三进制系统）。

2. 构建关联动力系统：

   • 将加法分解问题转化为映射迭代问题。对于给定的规范集合，定义一系列映射 $f_i: \mathbb{Z} \to \mathbb{Z}$。
   • 对于任意整数 $n$，其在该集合中的“展开”过程等价于计算轨迹序列：$n, f_0(n), f_1(f_0(n)), \dots$。
   • 映射定义为 $f_i(n) = \frac{1}{b_i}(n - t_i(n))$，其中 $t_i(n)$ 是 $n$ 模 $b_i$ 在 $T_i$ 中的唯一代表元。
   • 关键引理：一个整数 $n$ 属于该集合的和集（即有唯一分解），当且仅当其在对应动力系统中的轨迹最终变为常数 0。

3. 归约到不可判定问题：

   • 通过构造特定的规范集合，将“判定集合是否完备”的问题归约到著名的未解决问题或不可判定问题：
     • Collatz 猜想（3n+1 问题）。
     • Fractran 的通用停机问题（Conway 提出的基于分数的编程语言）。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 理论框架的构建

• 定义了规范集合（Canonical Collections），为 $\mathbb{Z}$ 上的加法系统提供了一个统一且自然的数学结构。
• 证明了规范集合的和集总是**直和（Direct Sum）**的（即表示唯一性自动满足），因此问题的核心简化为判定其和集是否覆盖整个 $\mathbb{Z}$（完备性）。
• 指出了 de Bruijn 定理在 $\mathbb{Z}$ 上不成立的反例（即存在 $\mathbb{Z}$ 的加法系统不是规范集合的收缩）。

3.2 与 Collatz 猜想的等价性 (Theorem 1)

• 构造：作者构造了一个特定的规范集合 $A_C$，其基数序列为 $b_i = 4^{i+1}$，剩余系映射与 Collatz 函数 $f_C(n)$ 紧密相关。
• 结论：该规范集合 $A_C$ 是完备的（即构成 $\mathbb{Z}$ 的加法系统），当且仅当 Collatz 猜想成立。
• 意义：这意味着如果 Collatz 猜想为真，则 $A_C$ 覆盖所有整数；如果为假，则 $A_C$ 存在“空洞”。这展示了加法系统完备性问题的极端困难性。

3.3 不可判定性证明 (Theorem 2 & Corollary 2)

• 背景：Conway 证明了 Fractran 语言是计算通用的，因此 Fractran 的通用停机问题是不可判定的。
• 构造：作者定义了一类Fractran 型规范集合（Fractran-type canonical collections） $A_F$。这类集合由一个 Fractran 程序 $F$ 唯一确定，且只需有限数据即可描述。
• 结论：
  • Fractran 程序 $F$ 对所有输入都停机，当且仅当对应的规范集合 $A_F$ 是完备的。
  • 推论：判定一个 Fractran 型规范集合是否完备是不可判定的（Undecidable）。不存在一个通用算法，能够输入任意 Fractran 程序并输出其对应的集合是否构成 $\mathbb{Z}$ 的加法系统。

4. 意义与影响 (Significance)

1. 连接不同数学领域：
   该论文在加法组合数学（Additive Combinatorics）、数论（Number Theory）和计算理论（Computability Theory）之间建立了深刻的联系。它表明，看似简单的整数分解问题，其本质可能涉及最深层的未解猜想和不可判定性。

2. 揭示问题的复杂性：
   对于 $\mathbb{N}_0$，de Bruijn 定理给出了完全的分类和判定方法。然而，对于 $\mathbb{Z}$，即使限制在结构良好的“规范集合”类中，判定其完备性也是极其困难的，甚至达到了不可判定的程度。这解释了为何 $\mathbb{Z}$ 上的加法系统研究长期停滞不前。

3. 新视角的提出：
   通过引入**非自治动力系统（Non-autonomous dynamical systems）**的视角来研究加法系统，为分析此类问题提供了强有力的工具。这种将代数结构转化为轨迹迭代的方法，可能为未来研究其他群上的分解问题提供新思路。

4. 对未解猜想的启示：
   通过将 Collatz 猜想转化为加法系统的完备性问题，为证明或证伪 Collatz 猜想提供了新的数学语境（尽管目前并未直接解决该猜想，但建立了等价性）。

总结

Andrei Zabolotskii 的这篇论文证明了整数集 $\mathbb{Z}$ 上的加法系统完备性判定问题在一般意义上是不可判定的。通过定义“规范集合”并将其转化为动力系统轨迹问题，作者成功地将该问题归约到 Collatz 猜想和 Fractran 停机问题。这一结果不仅解决了该领域的理论困惑，也展示了组合数学问题与计算复杂性理论之间惊人的等价性。