研究人员在拉姆齐理论（Ramsey Theory）领域取得了重大突破。他们利用 AlphaEvolve——一种由大语言模型（LLMs）驱动的新型元算法，发现了五个经典拉姆齐数的新下界。通过提高 R(3, 13)、R(3, 18)、R(4, 13)、R(4, 14) 和 R(4, 15) 已知的下界，该研究团队（包括 Prabhakar Raghavan、Ansh Nagda 和 Abhradeep Thakurta）证明了人工智能可以解决停滞数十年的复杂组合数学问题。这些发现标志着从人工设计的搜索启发式算法向机器进化的优化算法的转变，为探索数学结构中秩序与混沌的根本界限提供了一条新路径。
什么是拉姆齐数，为什么它们如此难以计算？
拉姆齐数（Ramsey numbers）记作 R(m, n)，代表一个完全图中的最小顶点数，使得对其进行的任何红蓝边着色都必然包含一个大小为 m 的红色团（clique）或一个大小为 n 的蓝色团。拉姆齐数以极难计算而闻名，因为随着 m 和 n 的增加，可能的图着色数量呈指数级增长，迅速超过了即使是世界上最强大的超级计算机的计算能力。
拉姆齐理论通常通过“聚会问题”类比来解释：它寻求在一场聚会中确保特定数量的人要么彼此都认识，要么彼此都是完全陌生人所需要的最低宾客人数。虽然概念简单——例如 R(3, 3) 等于 6——但其复杂性提升得如此之快，以至于 R(5, 5) 的确切值至今仍是未知数。传奇数学家保罗·埃尔德什（Paul Erdős）曾有一段著名的论述：如果一股拥有超强力量的外星势力要求人类计算出 R(5, 5)，否则就要毁灭地球，人类应该动用所有资源来完成这项任务；但如果他们要求计算 R(6, 6)，我们则应该准备战斗，因为这项计算极不可能是人类能完成的。
其困难在于数学家试图识别出秩序首次出现的“混沌中心”。由于没有已知的公式可以直接确定拉姆齐数，研究人员只能依靠寻找“下界”——即已知的不包含所需单色团的最大图规模。从历史上看，这些下界是使用专门为单个拉姆齐数设计的定制化、一次性算法发现的，这使得研究过程零散且难以在不同的数学案例中复制。
AlphaEvolve 如何利用大语言模型变异代码进行数学证明？
AlphaEvolve 作为一个复杂的代码变异代理，利用大语言模型迭代地改进搜索算法，而不仅仅是生成静态解决方案。通过将寻找组合结构的过程视为一个演化过程，该系统允许大语言模型扮演“工程师”的角色，修改自己的代码，以便更好地探索拉姆齐理论中广阔而复杂的领域。
与充当对话聊天机器人的传统人工智能应用不同，AlphaEvolve 作为一个元算法运行。该过程始于一个基础搜索结构，大语言模型随后通过建议架构更改、不同的启发式方法或优化策略来对其进行“变异”。这些变异会根据拉姆齐问题的数学约束进行测试。成功的变异——即那些能找到不含团的更大型图的变异——会得到强化，并作为进一步变异的基础。这创造了一个反馈循环，人工智能不仅是在搜索图，而是在演化出搜索该图的最有效方式。
Prabhakar Raghavan 及其同事采用的方法代表了对主导该领域多年的“手工打造”启发式算法的背离。AlphaEvolve 自动执行了这一发现过程，而不再需要人类数学家花费数月时间为 R(4, 13) 完善特定的搜索算法。这种元算法方法具有足够的通用性，可以同时应用于各种拉姆齐数，证明了单个 AI 驱动的系统可以取代数十个专门的人工编写工具。
R(3, 13) 和 R(4, 15) 的新下界是多少？
AlphaEvolve 为 R(3, 13) 和 R(4, 15) 发现的新下界分别为 61 和 159，有效地打破了保持已久的纪录。这些结果代表了目前已知的可以避开特定拉姆齐条件的图的最小规模，为寻找这些数字确切值的数学家提供了更窄的范围。
该研究成功更新了五个经典拉姆齐数的改良下界，具体如下：
- R(3, 13): 从 60 增加到 61
- R(3, 18): 从 99 增加到 100
- R(4, 13): 从 138 增加到 139
- R(4, 14): 从 147 增加到 148
- R(4, 15): 从 158 增加到 159
这些发现的意义超越了数字本身。为了验证 AlphaEvolve 的效能，研究人员使用该系统找回了所有已知确切值的拉姆齐数的下界。此外，该系统在广泛的其他案例中也匹配到了目前已知的最佳下界，包括那些之前研究人员使用的原始算法从未公开细节的案例。这让人们对 AlphaEvolve 的结果充满信心，并证明了其作为组合数学发现工具的鲁棒性。
数学发现的演化
这项研究标志着大语言模型在硬科学应用中的转折点。虽然大语言模型常因在创意写作中容易产生“幻觉”而受到批评，但它们在代码生成和变异方面的效用允许进行严格的验证过程。在拉姆齐理论的背景下，AlphaEvolve 产生的每一个结果都是数学上可验证的：一个图要么包含特定的团，要么不包含。这种客观真理使人工智能能够快速失败并快速学习，将其从创意引擎转变为数学证明的精密工具。
研究团队与基于大语言模型的代理之间的合作，弥合了纯数学与强化学习之间的关键鸿沟。通过使用 AlphaEvolve，Prabhakar Raghavan 团队推进了此前被认为需要人类直觉或极专业计算知识的问题。元算法“匹配并超越”历史基准的能力表明，我们正在进入一个人工智能可以发现过于复杂、以至于人类主导的搜索策略无法识别的模式和结构的时代。
未来影响及下一步计划
AlphaEvolve 在拉姆齐理论中的成功，为其在组合数学和图论中其他未解问题上的应用打开了大门。由于该系统是一个元算法，它不仅限于拉姆齐数。研究人员建议，它可以被调整用于寻找其他属性的极值图、优化网络拓扑，甚至辅助信息论中新型纠错码的发现。
随着代理的“演化”方面不断改进，我们可能会看到下界出现更大幅度的跃升。研究人员指出，虽然目前的改进是渐进的（将界限提高 1），但这些步骤对于最终确定确切值至关重要。未来版本的 AlphaEvolve 可能会整合更先进的推理能力，使人工智能不仅能变异搜索代码，还能假设新的数学特性，从而进一步缩小搜索空间。目前，组合数学领域在从图的无限复杂性中寻找秩序的征途中，拥有了一个强大的新盟友。
Comments
No comments yet. Be the first!