🤖 AI

Improved Upper Bounds for Slicing the Hypercube

本文将切断所有 $n$ 维超立方体所有棱所需的最小超平面数量的已知上界，从 $\lceil 5n/6 \rceil$ 改进到了约 $4n/5$ ，这一结果是通过使用结合了推理大语言模型与自动超参数调优的 CPro1 工具，为 $n=10$ 构建了一个特定的解而实现的。

原作者： Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin, Blake Bruell, Mason DiCicco, Gábor N. Sárközy, Ryan Offstein, Daniel Reichman

发布于 2026-07-01

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin, Blake Bruell, Mason DiCicco, Gábor N. Sárközy, Ryan Offstein, Daniel Reichman

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

大局观：切割一个十维立方体

想象你有一个由金属丝构成的巨大、完美的立方体。在我们的三维世界中，一个立方体有 12 条棱。现在，想象这个立方体存在于十个维度中。这个“超立方体”拥有数千条棱（具体来说是 5,120 条）。

作者们解决的数学挑战是：你需要最少多少张平坦的薄片（超平面）才能切开这个十维立方体，使得每一条金属丝棱都被切成两半？

如果你要切断一条棱，薄片必须正好穿过金属丝的正中间，而不仅仅是碰到末端。

旧纪录 vs. 新纪录

五十多年来，人们能做到的最好结果是数学家帕特森（Paterson）在 1971 年建立的一个经验法则。他的规则说：“要切开一个大小为 $n$ 的立方体，你大约需要 $5/6$ $n$ 张薄片。”

对于一个十维立方体，帕特森的规则说你需要 9 张薄片才能确保每条棱都被切断。

突破：
本文的作者们发现了一种方法，仅用 8 张薄片就能完成任务。

旧方法： 需要 9 个平面。
新方法： 你只需要 8 个平面。

他们证明了，对于几乎任何尺寸的超立方体，你都可以用大约维度数量的 $4/5$ （甚至更少）的薄片来完成切割，这比以前的 $5/6$ 限制有了显著的改进。

他们是怎么做到的？（人类 + AI 的联手协作）

这是故事变得有趣的地方。作者们并不是仅仅坐在那里用铅笔和纸来解决这个问题。他们利用了人类数学家与一种特定类型的人工智能——CPro1 之间的“团队协作”。

把这个问题想象成试图在一片大小如银河系的干草堆中寻找一根特定的针。

人类的角色： 人类设定规则并充当“侦探”。他们知道之前的尝试之所以失败，是因为搜索空间过于庞大。他们还注意到 AI 部分成功案例中的一个模式：最好的解似乎具有大量的重复性（比如一个列表中的前几个数字总是相同的）。
AI 的角色： AI（CPro1）扮演了“超快速生成器”的角色。它编写了数千个不同的计算机程序（算法）来尝试寻找解。它尝试了不同的策略，比如“模拟退火”（一种通过冷却解来寻找最优解的方法）和“爬山法”（向上爬坡以寻找最高峰的方法）。
协作过程： AI 生成了一个巨大的“接近完美”的解列表。它自己无法找到那个完美的 8 片解。然而，人类观察了 AI 的那些“接近完美”的尝试，发现了隐藏的模式（即重复性），并手动调整了搜索规则，以迫使 AI 在那个特定区域进行搜索。一旦人类给了 AI 这个推动力，AI 便迅速找到了完美的 8 片解方案。

类比： 想象你正在寻找一件隐藏的宝藏。AI 是一个每分钟可以挖 10,000 个洞的机器人，但它不知道该往哪儿挖。人类则是地图阅读者。机器人到处乱挖并说：“嘿，我发现了很多看起来可能靠近宝藏的土堆。”人类看了看这些土堆，意识到：“啊！宝藏总是在红石头下面，”于是告诉机器人：“现在只在红石头下面挖。”机器人随即瞬间找到了宝藏。

“简化超立方体”的小技巧

为了让搜索更快，作者们使用了一个聪明的数学技巧，叫做简化超立方体（Reduced Hypercube）。

想象你有一个巨大且复杂的迷宫。与其试图一次性解决整个迷宫，不如意识到迷宫的许多部分都是彼此的相同副本。因此，你将迷宫缩小成一个微小的、简化的版本，它保留了所有重要的规则，但去除了无聊的重复部分。

在他们的数学处理中，他们将十个维度的立方体分组为较小的组，其中数值是相同的。这把一个庞大、无法解决的问题变成了一个更小、易于处理的谜题。这使得他们能够在几秒钟内检查数百万种可能性，而不是耗费数年时间。

他们的发现（结果）

针对十维情况： 他们找到了一个特定的 8 平面组合，能够切开所有的 5,120 条棱。
针对其他尺寸： 他们还发现了切开其他尺寸立方体（如 11、12 或 15 维）的新方法，且使用的平面比之前认为的更少。
规律： 他们注意到，“最佳”解总是具有非常结构化、重复性的外观。平面方程中的前几个数字总是完全相同的。这表明，切割这些立方体最有效的方式并非随机的，而是遵循着一种严格且优雅的模式。

为什么这很重要（根据论文所述）

论文强调了两个主要观点：

数学进展： 他们打破了一个著名的几何学问题中维持了 50 年之久的纪录。
我们如何做数学： 他们展示了目前解决这类难题的最佳方式不是“AI 独自完成”或“人类独自完成”，而是伙伴关系。AI 提供想法和模式的海量规模，而人类提供解释这些模式并引导搜索的洞察力。

作者明确指出，AI 并没有自主“思考”或“推导”出数学证明。AI 生成代码，人类解释结果，最后由人类撰写最终的数学证明。他们使用的工具是开源的，这意味着其他研究人员也可以使用同样的“人类-AI 团队”方法来解决其他困难的数学问题。

技术摘要：改进超立方体切割问题的上界

问题定义
本文研究了确定 $S(n)$ 的问题，即切割 $n$ 维超立方体 $Q_n$ 所有棱（edges）所需的最少超平面数量。超立方体 $Q_n$ 的顶点集为 $\{-1, 1\}^n$ 。如果一个超平面 $H$ 穿过一条棱的内部，则称其“切割”了该棱。若一组超平面中的每一个超平面都能切割 $Q_n$ 中的每一条棱，则称该集合为一个“完整解”。

在历史上，已知关于 $S(n)$ 的最佳上界是由 Paterson 确立的（由 O'Neil 在 1971 年报告），即 $S(n) \le \lceil 5n/6 \rceil$ 。尽管组合数学、几何学和理论计算机科学领域对此进行了大量关注，但这一界限在五十多年间一直未能得到改进。虽然下界方面近期取得了进展（目前为 $\Omega(n^{13/19} \log^{-32/12} n)$ ），但上界与下界之间的差距仍然巨大。

方法论
作者采用了一种结合了由大语言模型（LLM）驱动的自动化搜索与人类监督及数学洞察力的混合方法。

AI 驱动的算法发现 (CPro1)： 作者利用了 CPro1 系统，该系统使用 LLM 来生成、评估和调优用于解决组合问题的搜索算法。他们配置 CPro1 以提出多样化的策略（例如模拟退火、禁忌搜索），以寻找能够切割 $Q_n$ 棱的 $k$ 个超平面集合。该系统生成了数千个候选程序，并在“开发（dev）”实例（即已知解的实例）上进行评估，从而为更难的实例识别出有前景的策略。
局部搜索与自适应权重： 对 AI 生成的候选方案的分析表明，具有自适应边权重的局部爬山搜索算法最为有效。在这种方法中，未被切割边的“权重”会随着迭代次数的增加而增加，从而迫使算法优先处理困难的边并跳出局部最优解。
缩减超立方体与结构约束： 通过观察 AI 的部分解而获得的批判性数学洞察是存在一种“组合（composition）”结构。作者形式化了**缩减超立方体（reduced hypercube）**的概念，其中通过将超平面系数分组为相等的集合，将 $n$ $n$ 维超立方体投影到 $\ell$ $ℓ$ 维格点上。
- 强制执行特定的组合结构（例如对于 $n=10$ ，使用 $[6, 1, 1, 1, 1]$ ）可以极大地降低搜索空间的维度。
- 这种简化允许通过将 $n$ 维立方体映射到更小的网格上来实现高效的适应度计算。
- 作者观察到，在高性能的解中，每个超平面的前几个系数是相同的。他们手动引入了这一约束（将初始列固定为常数值），并将偏置项（bias terms）固定为 $0.5$ 以避免经过顶点。
人类综合： AI 系统（CPro1 和 OpenEvolve）成功复现了已知界限并找到了强大的部分解，但仅凭自身无法找到 $S(10) \le 8$ 的完整解。突破发生在人类研究人员从 AI 输出中综合提取洞察力时——具体而言是提取了边加权爬山策略和列组合约束——进而手动设计出了最终算法。该算法成功找到了 8 个切割 $Q_{10}$ 的超平面集合。

主要贡献与结果

改进的上界： 本文证明了对于所有非奇数倍的 5 的 $n$ ，都有 $S(n) \le \lceil 4n/5 \rceil$ 。如果 $n$ 是 5 的奇数倍，则 $S(n) \le 4n/5 + 1$ 。这改进了长达数十年的 $\lceil 5n/6 \rceil$ 界限。
$n=10$ 的构造： 本文的核心证明是给出了能切割 $Q_{10}$ 中所有 5,120 条棱的 8 个超平面的显式构造。作者提供了这些超平面的特定系数向量。
次可加性论证： 利用已知的次可加性性质 $S(k+\ell) \le S(k) + S(\ell)$ 以及新的 $S(10) \le 8$ 结果，作者推导出了适用于所有 $n$ 的一般界限。
关于部分切割的新下界： 作者为 $S(n, k)$ （即 $k$ 个超平面能切割的最大边数）提供了新的下界（汇总于表 1 和表 2）。这些结果包括实现完全切割时的紧确界。
方法论框架： 本文展示了一个工作流，即 AI 生成高容量的候选算法并识别结构化模式，随后由人类进行解释与综合，从而产生严谨的数学构造。

意义与主张
本文声称其主要贡献在于打破了超立方体切割问题长达 50 年的上界停滞状态。作者强调了所发现解的结构性特征，指出最优或接近最优的切割超平面似乎具有低维结构（重复系数）。

关于 AI 的角色，作者将其工作定位为“C 级”协作（实质性的人机协作），即双方都做出了本质性的贡献。他们认为，虽然 AI 工具可以探索庞大且难以处理的搜索空间并呈现可解释的模式，但目前仍需要人类监督来将这些模式综合成有效的数学证明和最终构造。作者强调，其研究成果是在个人机器上使用开源工具完成的，这表明这种 AI 辅助的发现对于没有工业规模计算资源的科研人员也是可及的。他们总结道，进一步改进 $S(n)$ 极有可能是可能的，并且 $S(n, k)$ 的界限问题是评估 AI 系统进行数学发现能力的极佳基准。