技术摘要：关于互为约数之自然数多重集可能和的研究

问题陈述

本文研究了由有限个正整数组成的多重集 $A$ 所生成的可能和集合 $\text{span}(A)$ 的结构特征。具体而言，本研究将范围限制在元素构成“可约链”（divisible chain）的多重集中。也就是说，对于任何两个元素 $a_i, a_j \in A$，要么 $a_i$ 整除 $a_j$，要么 $a_j$ 整除 $a_i$。

此类多重集的元素可以用形式 $d_0, d_0d_1, \dots, d_0d_1\cdots d_k$ 来表示，其中 $d_0=1$ 且对于 $i > 0$ 有 $d_i > 1$。多重集 $A$ 可表示为一个元组 $(a_0, a_1, \dots, a_k)$，其中 $a_i$ 表示成本为 $p_i$ 的标记（token）的重数。集合 $\text{span}(A)$ 由所有满足 $0 \le c_i \le a_i$ 的和 $\sum c_i p_i$ 组成。

主要目标包括：

1. 描述这些特定多重集的 $\text{span}(A)$ 的结构。
2. 提供一个判别准则，用于确定两个此类多重集 $A$ 和 $B$ 是否生成相同的和集（即 $\text{span}(A) = \text{span}(B)$）。
3. 开发用于判定和等价性以及成员资格（$n \in \text{span}(A)$）的算法。

方法论

本文采用了一种以初等交换（elementary exchanges）为核心的组合方法。在索引 $i$ 处的初等交换（记作 $e_i$）通过将 $d_i$ 个成本为 $p_i$ 的标记替换为一个成本为 $p_{i+1}$ 的标记来改变多重集。这一操作保持了多重集的总和不变，但改变了其组成。

核心方法论包括：

• 归一化（Normalization）： 定义了一种“恰当的”初等交换，即当 $a_i > 2(d_i - 1)$ 时进行的交换。本文引入了算法 1，它通过迭代应用恰当的初等交换，将任何任意的 $\{d_i\}$-集合转换为一个规范（normal）集合，其中满足 $a_i \le 2(d_i - 1)$。该算法的循环条件明确检查 while A[i] > 2(d_i - 1)，尽管伪代码中的 Require 子句提到了 $0 \le a_i < d_i$，但算法的运行逻辑及其对规范集合的定义侧重于上界 $a_i \le 2(d_i - 1)$。
• 分解（Decomposition）： 通过识别“关键索引”（critical indices，即满足 $a_j < d_j - 1$ 或 $j$ 为最后一个索引的情况）来分析规范集合。这使得将规范集合分解为不可约子多重集成为可能。
• 归纳证明： 利用对多重集之和的归纳以及模算术性质，建立关于可达和的界限以及表示唯一性的证明。

核心贡献与结果

1. 在恰当交换下的不变性

本文确立了：如果多重集 $A$ 满足 $a_i > 2(d_i - 1)$，那么在索引 $i$ 处执行初等交换不会改变可能的和集：
$$\text{span}(A) = \text{span}(e_i(A))$$
这导出了推论 2.1，指出归一化过程（算法 1）保持了 $\text{span}$ 不变。因此，$\text{span}(A) = \text{span}(\text{norm}(A))$。

2. 规范集合的特征描述

本文定义了一个规范（normal）集合为满足对于所有 $i$ 都有 $a_i \le 2(d_i - 1)$ 的集合。本文证明了对于规范集合，其 $\text{span}$ 唯一确定了该多重集：

• 命题 3.2： 若 $A$ 和 $B$ 是规范 $\{d_i\}$-集合且 $\text{span}(A) = \text{span}(B)$，则 $A = B$。
• 定理 3.2： 对于任意 $\{d_i\}$-集合 $A$ 和 $B$，$\text{span}(A) = \text{span}(B)$ 当且仅当 $\text{norm}(A) = \text{norm}(B)$。

3. 结构分解

对于规范集合 $A$，本文提供了分解定理（定理 3.1）。若基于关键索引将 $A$ 分解为不可约子多重集 $A_1, \dots, A_s$，则 $A$ 的 $\text{span}$ 是这些分量的缩放 $\text{span}$ 的直和：
$$\text{span}(A) = \bigoplus_{i=1}^s p_{j_{i-1}+1} \cdot \{0, 1, \dots, p_{j_i-1}^{-1}\text{sum}(A_j)\}$$
这种结构意味着 $\text{span}(A)$ 中的任何元素都可以唯一地表示为来自这些不可约分量缩放 $\text{span}$ 的元素之和。

4. 算法

本文提出了两种主要的算法：

• 归一化算法： 将任何集合转换为其唯一的规范形式，从而通过简单的元组比较来判定 $\text{span}$ 的等价性。
• 成员资格算法： 从分解中隐式导出，允许通过检查其表示是否符合分解后的结构来判定特定整数 $n$ 是否属于 $\text{span}(A)$。

5. 反例与局限性

本文指出不变性命题的逆命题是错误的；即使不满足条件 $a_i > 2(d_i - 1)$，初等交换仍可能保持 $\text{span}$ 不变（例如在特定的 2-集合中）。然而，归一化过程保证了无论操作顺序如何，都能得到唯一的规范形式（推论 3.1）。

意义与主张

本文声称为具有相互约数之自然数的多重集的和集提供了完整的结构描述。其主要意义在于：

1. 规范表示： 确立了每个此类多重集都有一个保持其 $\text{span}$ 不变的唯一“规范”形式，从而有效地解决了等价性问题。
2. 算法可判定性： 提供了具体的、有限的程序来判定两个集合是否生成相同的和集，并检查特定值的成员资格。
3. 泛化性： 虽然问题是针对 $\{d_i\}$-集合进行阐述的，但作者指出，其逻辑可以从更简单的 $d$-集合（单一整数 $d$ 的幂）推广到一般情况。

这项工作受到整数拆分（引用 [AE04]）的启发，并为理解具有层级约数约束的标记系统提供了一个严谨的组合框架。作者明确感谢了 Fedor Petrov 教授对证明过程的验证，这强调了本文在组合领域内对数学正确性的关注。