AI辅助离散几何猜想证明：从线性规划到可复现验证的工作流

问题背景：持续数十年的密度上限猜想

离散几何中存在一个经典问题：在平面上，单位距离避免集（unit-distance avoiding set）的最大可能密度是多少？这类集合的定义是集合中任意两点之间的距离都不等于 1。1967 年，Hallard Croft 构造了密度约为 0.2293 的集合（被称为 "Croft's Tortoise"），此后半个多世纪里，研究者不断尝试突破这一下界，同时也在收紧上界估计。

Erdős 和 Moser 曾猜想该密度上限为 0.25。经过 60 余年的努力，人工推导将上界从 0.2857 逐步收紧至 0.2565。2024 年，Rényi 数学研究所的 AI 团队通过结合线性规划与计算机搜索，首次将上界突破至 0.247，后续进一步优化至 0.2415，彻底否定了 Erdős 的 0.25 猜想。

核心方法：从几何到计算的转化

该证明的关键在于将几何问题转化为可计算的优化问题。研究团队采用了双重策略：

自相关函数分析：对于平面上的点集 A，定义自相关函数 f (x) = δ(A ∩ (A+x))，其中 δ 表示密度。该函数满足 f (0) = δ(A)，且对于所有单位向量 x，f (x) = 0。通过分析自相关函数的结构，可以将密度上界估计转化为线性约束系统。

线性规划形式化：研究团队为任意平面点集构建了一个大型线性规划问题，其解即为密度上界。这一转化使得原本的几何直觉问题变成了可计算的搜索任务。

AI 辅助搜索的工作流

1. 搜索空间的结构化定义

该问题具有两个关键性质，使其适合计算机搜索：

• 单调性：向配置中添加点不会弱化边界估计。这意味着可以安全地扩展候选配置而不用担心遗漏更优解。
• 离散性：对于任意给定配置，只有有限个点可能通过添加来改善边界。这极大地限制了搜索空间。

2. 束搜索（Beam Search）的实现

研究团队实现了改进的束搜索算法：

初始化：从空配置或启发式种子配置开始
迭代：
  - 对当前配置集合中的每个配置，生成所有可能的扩展
  - 评估每个扩展的边界改进潜力
  - 保留得分最高的k个配置（束宽）
终止：找到满足证明条件的配置或达到资源限制

3. Transformer 模型的引导作用

在搜索过程中，Transformer 模型承担了配置评估的启发式函数角色：

• 价值估计：预测给定配置扩展后可能带来的边界改进
• 优先级排序：在束搜索的剪枝阶段，优先保留被模型评估为高潜力的配置
• 搜索方向引导：通过学习历史成功配置的模式，引导搜索向更有希望的区域集中

这一方法最终找到了一个 23 点配置，足以将密度上界收紧至 0.247 以下。

验证策略与可信性保障

形式化验证链

AI 辅助数学证明面临的核心挑战是验证可信性。该研究采用了分层验证策略：

第一层：计算验证：线性规划求解器的输出经过独立验证，确保约束满足性和最优性证明的正确性。

第二层：配置验证：找到的 23 点配置经过符号计算验证，确认其确实满足所有约束条件。

第三层：人工审计：关键步骤经过数学家的形式化审查，发表在 Mathematical Programming 等期刊接受同行评议。

结果的可复现性保障

• 配置公开：关键配置以结构化格式公开，允许独立验证
• 代码开源：搜索算法和验证脚本提供可执行版本
• 参数文档化：束搜索的束宽、评估阈值等超参数完整记录

可复现的 AI 辅助证明工作流

基于该案例，可以提炼出以下可复现的工作流：

阶段一：问题形式化

• 将几何 / 组合问题转化为优化问题（线性规划、整数规划或约束满足问题）
• 识别并利用问题的结构特性（单调性、对称性、离散性）
• 定义搜索空间的边界和约束

阶段二：搜索策略设计

• 选择合适的搜索算法（束搜索、A*、蒙特卡洛树搜索等）
• 设计评估函数：结合人工启发式和 AI 模型预测
• 实现增量式搜索，利用中间结果动态调整策略

阶段三：AI 模型集成

• 使用 Transformer 或其他神经网络作为价值函数近似
• 在合成数据或历史成功案例上训练评估模型
• 实现人机协作：AI 提供候选，人类验证关键步骤

阶段四：验证与文档

• 对关键结果进行多层次的独立验证
• 记录搜索轨迹，确保结果可复现
• 准备形式化证明的补充材料

局限与风险

该方法存在以下限制：

搜索空间爆炸：尽管利用了离散性，配置空间仍可能随问题规模指数增长。对于更复杂的离散几何问题（如 Hadwiger-Nelson 问题），当前计算资源可能不足。

验证瓶颈：AI 发现的配置需要经过严格的形式化验证，这一过程目前仍高度依赖人工。完全自动化的形式化验证仍是开放问题。

可推广性：该工作流高度依赖于问题的特定结构（单调性、离散性）。对于不具备这些特性的数学问题，需要重新设计搜索策略。

结语

Erdős 单位距离猜想的突破展示了 AI 在辅助数学证明中的潜力：不是替代数学家的直觉，而是将计算搜索的规模扩展到人工无法触及的范围。通过将几何问题形式化为可计算的搜索任务，并利用 AI 模型引导搜索方向，研究团队成功找到了否定数十年猜想的反例配置。

这一案例为 AI 辅助数学研究提供了可复现的模板：问题形式化、结构化搜索、AI 引导、分层验证。随着形式化验证工具和 AI 推理能力的进一步发展，类似的工作流有望在更广泛的数学领域得到应用。

参考来源

• Rényi AI 团队关于解决 Erdős 猜想的技术报告
• Mathematical Programming 期刊发表的密度上界证明论文
• OpenAI 关于 AI 作为科学合作者的研究文档

ai-systems