🔢 mathematics

Graham conjecture on small sets in abelian groups

本文利用递归方法研究了阿贝尔群中小子集的可序列性问题，将已知结论从 $|A|\leq 9$ 提升至 $|A|\leq 20$ （零和子集提升至 $|A|\leq 22$ ），并证明了不含逆元对的零和子集在 $|A|\leq 23$ 时可序列化。

原作者： Simone Costa, Stefano Della Fiore, Mattia Fontana, Lluís Vena

发布于 2026-03-24

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Simone Costa, Stefano Della Fiore, Mattia Fontana, Lluís Vena

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文探讨了一个有趣的数学谜题，我们可以把它想象成是在玩一场**“数字积木”**的游戏。

1. 核心谜题：如何排列积木？

想象你有一盒特殊的积木，每块积木上都有一个数字（这些数字来自一个“阿贝尔群”，你可以简单理解为一种特殊的数字系统，比如时钟上的数字，或者普通的整数）。

规则：你手里有 $k$ 块积木，它们都不为零。
目标：你要把这些积木排成一列。
挑战：当你从左到右一块一块地把积木叠起来时，每一层叠起来的总高度（部分和）都必须独一无二。
- 比如：第一块是 3，总高度是 3。
- 第二块是 5，总高度变成 8。
- 第三块是 2，总高度变成 10。
- 如果在这个过程中，某次叠起来的总高度和之前某次的高度重复了，或者变成了0（在特定规则下），那这个排列就是“失败”的。
成功：如果你能找到一种排列方式，让所有中间的高度都不重复，那么这组积木就被称为**“可序列化的” (Sequenceable)**。

著名的“格雷厄姆猜想” (Graham Conjecture) 说：只要你的积木数量是有限的，且没有零，你永远都能找到一种排列方法，让所有高度都不重复。

2. 之前的进展：只能玩小一点的积木

在数学界，大家已经证明了这个猜想对于非常大的数字系统（比如非常大的质数）是成立的。但是，对于小数量的积木，大家之前只能证明：如果你手里的积木不超过 9 块，你肯定能排好。

一旦积木超过 9 块，大家就有点拿不准了，因为情况变得太复杂，像是一个巨大的迷宫，很难用传统的数学公式直接走通。

3. 这篇论文的突破：把大积木拆成小积木

作者们（Costa, Della Fiore, Fontana, Vena）想出了一个聪明的**“递归策略”**，就像是在玩俄罗斯套娃或者搭乐高时的“合并技巧”。

他们的“魔法”步骤：

寻找“好搭档”：他们证明，在任何一组积木中，你总能找到两块积木（比如 A 和 B），把它们合并成一块新的大积木（A+B），而且这块新积木不会和剩下的积木重复，也不会变成零。
化繁为简：一旦合并成功，原本 $k$ 块的难题，就变成了 $k-1$ 块的难题。
递归循环：如果 $k-1$ 块的难题能解决，那么原来的 $k$ 块通常也能解决。

这就好比你要解决一个 20 层的迷宫，你发现只要把其中两堵墙打通合并，就变成了一个 19 层的迷宫。如果你知道 19 层怎么解，那 20 层也就有希望了。

4. 他们做到了什么？

利用这个“合并策略”加上强大的计算机暴力搜索（就像让计算机在迷宫里尝试所有可能的走法，但用聪明的方法剪枝），他们把之前的纪录大大刷新了：

普通情况：以前只能保证 9 块 积木能排好。现在，他们证明了只要积木数量 不超过 20 块，你一定能找到一种完美的排列方式。
特殊情况（总和为零）：如果这组积木加起来刚好等于 0（就像天平平衡），这个界限可以提升到 22 块。
更特殊的情况（没有相反数）：如果这组积木里，没有互为相反数的对子（比如没有 3 和 -3 同时存在），界限甚至可以推到 23 块。

5. 他们是怎么做的？（计算机的角色）

虽然数学证明很优雅，但面对 20 块积木，可能的排列方式有 $20!$ （20 的阶乘）种，这是一个天文数字，人脑算不过来。

作者们写了一个计算机程序：

它像一个侦探，在排列的迷宫里搜索。
它记录下了所有“导致失败”的排列模式（比如“如果 A 和 B 挨着，高度就会重复”）。
通过数学逻辑（线性代数），它发现这些“失败模式”在积木数量达到 20 或 23 时，会产生逻辑矛盾（就像侦探发现嫌疑人不可能同时出现在两个地方）。
既然“找不到失败的排列”，那就意味着“成功的排列一定存在”。

总结

这篇论文就像是在说：

“以前我们只知道，如果你手里的积木少于 9 块，你肯定能排好。现在，我们发明了一种‘合并积木’的魔法，配合超级计算机的搜索，证明了只要你手里的积木不超过 20 块（甚至更多，视情况而定），你绝对能排出一列让所有高度都不重复的序列。”

这不仅解决了格雷厄姆猜想在小规模情况下的难题，也为未来解决更大规模的问题提供了一条新的、更有效的路径。

这是一份关于论文《阿贝尔群中小集合的格雷厄姆猜想（GRAHAM CONJECTURE ON SMALL SETS IN ABELIAN GROUPS）》的详细技术总结。

1. 研究背景与问题定义

核心问题：
本文主要研究阿贝尔群（Abelian Group）中有限子集的**可序列性（Sequenceability）**问题。

定义： 设 $A$ 是阿贝尔群 $G$ 的一个有限子集。如果 $A$ 的元素可以排列成一个序列 $a_1, a_2, \dots, a_{|A|}$ ，使得其所有部分和 $p_i = \sum_{j=1}^i a_j$ 两两不同，则称该排列为有效排列（valid ordering）。
序列性（Sequencing）： 如果一个有效排列还满足 $p_i \neq 0$ 对所有 $1 \le i \le |A|-1$ 成立，则称其为序列性排列。若集合 $A$ 存在这样的排列，则称 $A$ 是可序列的（sequenceable）。

相关猜想：

Graham/Alspach 猜想 (猜想 1.1)： 对于任意阿贝尔群 $G$ $G$ ，其任意非零子集 $A \subseteq G \setminus \{0\}$ $A \subseteq G ∖ {0}$ 都是可序列的。
- 现状： 对于素数阶循环群 $\mathbb{Z}_p$ ，Pham 和 Sauermann (2024) 结合早期结果证明了当 $p$ 足够大时猜想成立，但小素数及一般阿贝尔群（特别是循环群 $\mathbb{Z}_k$ ）的情况仍未解决。
- 已知界限： 此前对于一般阿贝尔群，该猜想仅被证明对 $|A| \le 9$ 成立（Alspach & Liversidge, 2019）。
CMPP 猜想 (猜想 1.2)： 针对零和子集（元素之和为 0）且不含逆元对（即 $\{x, -x\} \not\subseteq A$ ${x, - x} \neq \subseteq A$ ）的情况，猜想其也是可序列的。
- 已知界限： 此前在一般阿贝尔群中仅对 $|A| \le 10$ 成立。

2. 方法论：递归策略与计算验证

本文提出了一种递归方法（Recursive Approach），结合代数证明与计算机搜索，显著提高了已知界限。

2.1 核心引理：递归引理 (Recursive Lemma)

文章的核心在于引理 2.5 (Corollary 2.5)。该引理指出，对于阿贝尔群 $G$ 中的非零子集 $A$ （ $|A|=k$ ），要么 $A$ 本身是可序列的，要么存在两个不同的元素 $x_1, x_2 \in A$ ，使得它们的和 $x_1 + x_2$ 既不为 0 也不属于 $A \setminus \{x_1, x_2\}$ 。

操作： 如果存在这样的 $x_1, x_2$ ，可以将 $A$ 替换为更小的集合 $A' = (A \setminus \{x_1, x_2\}) \cup \{x_1 + x_2\}$ 。
逻辑： 如果 $A'$ 是可序列的，且满足特定条件，则可以通过构造证明 $A$ 也是可序列的。这将问题规模从 $k$ 降低到 $k-1$ 。

2.2 证明递归引理的两种途径

组合零点定理 (Combinatorial Nullstellensatz) 方法：
- 针对 $\mathbb{Z}_p$ 情况，构造了一个齐次多项式 $F_k$ 。
- 利用 Alon 的组合零点定理，证明了当 $10 \le k \le 23$ 且 $p$ 足够大时，存在 $x_1, x_2$ 使得 $F_k(x_1, \dots, x_k) \neq 0$ ，从而保证 $x_1+x_2$ 满足递归条件。
- 通过 Mathematica 计算了特定单项式的非零系数（见表 1）。
直接代数证明：
- 针对一般阿贝尔群，利用 Kneser 定理的思想，对满足“任意两元素之和仍在集合或零中”的集合结构进行了分类（定理 2.4）。
- 证明了除非 $A \cup \{0\}$ 本身构成一个子群，否则总能找到满足递归条件的元素对。对于子群情况，已有文献证明其可序列性。

2.3 计算机搜索算法 (第 3 节)

为了处理递归步骤中的具体案例，作者设计了一个基于广度优先搜索 (BFS) 的算法，用于验证特定大小集合的可序列性。

搜索树结构： 节点表示当前的元素排列 $\omega$ 和约束矩阵 $C$ 。
约束矩阵 $C$ ： 记录部分和冲突产生的线性关系。如果某区间 $[i, j]$ 的部分和为 0，则对应一个向量 $v$ 满足 $\sum v_i a_i = 0$ 。
终止证书 (Terminal Certificates)： 算法在搜索过程中检查约束矩阵的行空间是否包含以下向量，若包含则产生矛盾，证明该排列路径无效：
1. 零元素证书： 行空间包含 $e_i$ $\implies a_i = 0$ (矛盾，因 $A$ 不含 0)。
2. 相等证书： 行空间包含 $e_i - e_j$ $\implies a_i = a_j$ (矛盾，因元素互异)。
3. 压缩证书 (Compression Certificate)： 利用递归引理，如果压缩后的集合 $A'$ 有已知序列，则 $A$ 中某些块不能为零和。若搜索发现这些块必须为零和，则产生矛盾。
实现细节： 使用 Python 和 NumPy 进行秩测试。算法在 $k \le 23$ 时非常高效，通常只需很少的层级即可找到矛盾。

3. 主要贡献与结果

本文通过上述递归框架和计算验证，将已知界限从 $|A| \le 9$ 大幅提升：

一般阿贝尔群 (定理 1.4)：
- 对于任意阿贝尔群 $G$ 和任意非零子集 $A \subseteq G \setminus \{0\}$ ，若 $|A| \le 20$ ，则 $A$ 是可序列的。
- 改进幅度： 从 9 提升至 20。
零和子集 (定理 1.5)：
- 若 $A \subseteq G \setminus \{0\}$ 且 $\sum_{x \in A} x = 0$ ，则当 $|A| \le 22$ 时， $A$ 是可序列的。
- 改进幅度： 从 9 提升至 22。
CMPP 猜想情形 (定理 1.6)：
- 若 $A \subseteq G \setminus \{0\}$ 满足 $\sum_{x \in A} x = 0$ 且不含逆元对（ $\{x, -x\} \not\subseteq A$ ），则当 $|A| \le 23$ 时， $A$ 是可序列的。
- 改进幅度： 从 10 提升至 23。

4. 技术细节与关键发现

递归的有效性： 论文指出，如果不使用递归引理（即仅使用纯树搜索算法），目前的计算能力仅能验证到 $|A| \le 10$ （与文献 [3] 一致）。递归引理通过减少问题规模，使得验证 $k=20, 22, 23$ 成为可能。
计算资源： 所有计算在拥有 2TB RAM 和 128 核 AMD CPU 的服务器上完成，代码已开源。
界限的突破： 对于 $k \le 23$ 的情况，作者通过计算机穷举证明了不存在反例。结合递归引理，证明了更大规模集合的可序列性。

5. 意义与影响

解决长期未决问题： 该工作显著推进了 Graham 猜想和 CMPP 猜想在一般阿贝尔群（特别是小集合）上的研究进程。
方法论创新： 成功结合了代数组合工具（组合零点定理、群结构分类）与大规模计算搜索。这种“递归降维 + 计算机验证”的框架为处理类似组合存在性问题提供了新范式。
应用前景： 序列性问题与 Heffter 数组、图论中的彩虹路径等组合设计问题密切相关。更小的集合界限意味着这些结构在更广泛的参数范围内存在。
未来方向： 虽然对于大素数 $p$ 已有渐近结果，但本文填补了小集合和一般群结构的空白。未来的工作可能尝试将递归界限进一步推高，或结合反集中性不等式（Anticoncentration inequalities）处理更复杂的群结构。

总结：
Costa 等人通过引入基于群结构分类的递归引理，并辅以高效的计算机搜索算法，成功将阿贝尔群中小集合可序列性的已知界限从 9 提升至 20（一般情况）、22（零和情况）和 23（CMPP 猜想情况）。这一成果不仅刷新了该领域的记录，也展示了代数方法与计算数学结合在解决经典组合猜想中的强大潜力。