🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

本文通过在强积产品中构建更大的独立集，并与大语言模型进行迭代协作，提出了奇数环 $C_7$ 、 $C_{11}$ 、 $C_{13}$ 和 $C_{15}$ 的香农容量改进下界。

原作者： Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

发布于 2026-07-31

📖 1 分钟阅读☕ 轻松阅读

原作者： Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

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

想象一下，你正试图通过一个充满噪音的对讲机频道发送一条秘密信息。每当你说话时，静电可能会扰乱你的话语，把“是”变成“否”。在信息论的世界里，科学家们提出了一个非常具体的问题：在无论空气中有多少静电的情况下，我们能以多快的速度发送信息，才能让接收者完美理解且零误差？这个极限被称为香农容量（Shannon capacity）。

为了计算出这个数值，数学家们使用了一种叫做“图（graph）”的工具，它其实就是一种由点和线组成的地图。你可以把这些点想象成你可能发送的不同信息，而线则代表了它们之间令人困惑的相似之处。如果两个点被连在一起，就意味着这两条信息可能会混淆。我们的目标是挑选出一组互不相连的点（信息），这样它们才是截然不同且不会产生混淆的。这组点的数量越大，你能发送的信息就越多。

棘手的地方在于，我们可以将这些地图组合起来，创造出更大、更复杂的地图。通过堆叠这些地图，我们有时可以发现以前看不见的大规模安全信息组。对于某些形状，比如偶数环，我们已经完全掌握了答案。但对于奇数环（比如 7 边形或 11 边形的形状），答案几十年来一直是一个顽固的谜团。这就像是在尝试寻找一个扭曲、打结的手镯上最大数量的不接触的点，而至今还没有人能找到那个绝对完美的排列方式。

这篇论文讲述了一群研究人员决定利用一种全新的助手来应对这些顽固的奇数环：大语言模型（LLM），也就是驱动智能聊天机器人的那种 AI。他们并没有仅仅编写代码来进行搜索，而是将 AI 视为一位创意伙伴。他们让 AI 查看这些奇数环中已知的最佳安全信息排列方式，然后尝试对它们进行微小的调整，看看能否让规模变得更大。

结果非常成功。研究团队与 AI 协作，为 7、11、13 和 15 边形的环发现了新的、更大的安全信息组。对于 7 边形环，他们找到了 134,753 个安全信息，这比之前的纪录 367 大得多。对于 11 边形环，他们找到了 21,909 个；对于 13 边形环，找到了 62,530 个；而对于 15 边形环，则找到了惊人的 8,076,974 个。

这些数字看起来可能只是一串数字，但它们代表了我们在理解如何无误地发送信息方面取得的实质性进展。通过找到这些更大的信息组，研究人员证明了在这些特定的嘈杂信道上，发送完美信息的最大速度比我们之前认为的要高。例如，对于 7 边形环，现在的速率极限已知大于 3.258020，而以前仅已知大于 3.257865。

这个故事之所以特别令人兴奋，不仅在于这些数字，更在于它们是如何被发现的。研究人员尝试使用了传统的计算机搜索方法，比如模拟退火算法（这就像摇晃一个装满拼图碎片的盒子直到它们契合），但这些方法都无法找到这些新的、更大的信息组。即使是基于 AI 构建的局部搜索算法也无法达到新的高度。只有通过与 AI 的反复对话——研究人员提供提示，而 AI 提出对现有模式的创造性修改——这些新的纪录才得以被打破。

该论文并不声称已经解决了所有奇数环的香农容量之谜；那个问题仍然悬而未决。然而，它表明通过将人类的数学直觉与现代 AI 的模式匹配能力相结合，我们可以推向知识的边界。研究人员验证了他们发现的每一个新信息组，以确保其在数学上的正确性，证明了 AI 不仅仅是在猜测，而是确实找到了人类专家所忽略的有效且更大的解。这表明，解决复杂数学难题的未来可能涉及人类与 AI 的团队协作，而 AI 则扮演着一个创造性火花的角色，帮助我们看到数字之舞中的下一步。

技术摘要：改进奇数循环香农容量的下界

问题陈述
图 $G$ 的香农容量 $\Theta(G)$ 量化了由 $G$ 定义的噪声信道的最大无误通信速率。其定义为 $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ ，其中 $\alpha(G^d)$ 是 $G$ 的 $d$ 次强积的独立数。虽然对于偶数循环 $\Theta(C_p) = p/2$ 且对于 $C_5$ 有 $\Theta(C_5) = \sqrt{5}$ ，但对于 $r > 2$ 的奇数循环 $C_{2r+1}$ ，其取值仍是未知的。确定 $\Theta(C_7)$ 是一个极其困难的开放性问题。建立下界的标准方法涉及在强积 $C_k^d$ 中构造大型独立集，以最大化量 $\alpha(C_k^d)^{1/d}$ 。

方法论
作者采用了一种与大语言模型（LLM）——具体为 ChatGPT-5.6 Sol Pro ——进行迭代交互的方法，以发现显式的组合构造。该方法不同于传统的启发式搜索（例如模拟退火或局部搜索算法），作者指出这些传统方法尽管经过了广泛尝试，仍未能达到所报告的界限。

该过程包括：

提示词工程（Prompting）： 作者向 LLM 提供了特定参数：循环长度 ( $k$ )、乘积维度 ( $d$ )、现有的最佳已知构造以及目标基数（cardinality）的提升量。
生成与执行： 模型生成搜索程序，在其环境中执行，并返回候选独立集。
迭代优化： 作者通过后续提示词引导模型，试图将基数推向超过初始结果的水平。
验证： 所有构造的集合都经过作者的严格验证，以确保它们构成有效的独立集（即任意两个向量在模 $k$ 的意义下，在每个坐标上的差异都不超过 1）。

主要贡献与结果
本文通过构造其强积中更大的独立集，提出了四个特定奇数循环改进后的下界：

$C_7$ （7-循环）： 作者在强 10-积 $C_7^{10}$ 中构造了一个大小为 134,753 的独立集。这改进了此前最佳的 $367^{1/5}$ 界的记录（该界来自 $C_7^5$ 中大小为 367 的独立集）。
- 新下界： $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ （此前为 $> 3.257865$ ）。
- 构造策略： 该集合是通过修改已知的规模为 367 的集合 $R$ （来自 Polak 和 Schrijver）得到的。作者从 $R$ 中删除特定向量以形成子集 $B$ ，然后利用 $B \times B$ 以及由 $R$ 和特定变换派生的附加向量来构造最终集合 $I$ 。
$C_{11}$ （11-循环）： 在 $C_{11}^6$ 中发现了一个大小为 21,909 的独立集。
- 新下界： $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ （此前为 $148^{1/3} > 5.289572$ ）。
- 构造策略： 从 $C_{11}^3$ 中大小为 148 的集合出发，作者定义了特定的子集（$DL, DR, BL, BR $）和辅助向量集（$ F_A, F_B, \dots$）来构造该集合。
$C_{13}$ （13-循环）： 在 $C_{13}^6$ 中发现了一个大小为 62,530 的独立集。
- 新下界： $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ （此前为 $247^{1/3} > 6.274305$ ）。
- 构造策略： LLM 在辅助图 $G_A$ （具有 134 个顶点）上实施了随机局部搜索，以找到一个包含 370 个向量的集合 $S \in \mathbb{Z}_{13}^4$ 。最终集合 $I$ 定义为 $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ 。
$C_{15}$ （15-循环）： 在 $C_{15}^8$ 中发现了一个大小为 8,076,974 的独立集。
- 新下界： $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ （此前为 $2842^{1/4} > 7.301397$ ）。
- 构造策略： 从 $C_{15}^4$ 中大小为 2842 的集合出发，作者删除了特定向量并添加了其他向量以形成基础集合 $R$ 。最终集合由 $B \times B$ （其中 $B \subset R$ ）以及根据邻接条件确定的查找表向量（ $W_0, W_1$ ）扩充而成。

此外，论文还报告了若干个不直接提升香农容量界的单个强积独立数的改进下界（例如 $\alpha(C_{11}^4) \geq 766$ ， $\alpha(C_{15}^3) \geq 383$ ）。

意义与主张
本文声称，这些结果对 $\Theta(C_7)$ 、 $\Theta(C_{11})$ 和 $\Theta(C_{15})$ 的已知下界实现了适度的改进，并对 $\Theta(C_{13})$ 实现了更显著的改进。

该工作的核心意义在于其方法论：

LLM 的效能： 这些构造是通过与 LLM 的迭代交互发现的，LLM 生成的独立集是那些手动搜索启发式算法（包括模拟退火和 AI 构建的局部搜索算法）在经过数月努力后仍无法找到的。
知识的作用： 作者认为，LLM 的成功可能源于其利用现有数学知识并对已知独立集进行“微小”修改的能力，这突显了 LLM 在寻找显式组合构造方面的潜力。
未来方向： 论文指出，研究允许 LLM 超越传统搜索启发式算法以寻找独立集的机制，是一个极具价值的未来研究方向。

作者对数值改进的幅度保持谦逊（例如 $\Theta(C_{15})$ 的增幅仅在小数点后第六位），但强调了这一发现过程的新颖性。所有构造和代码均已在公共仓库中公开。

技术摘要：改进奇数循环香农容量的下界

类似论文