🔢 mathematics

Resolution of Erdős Problem #728: a writeup of Aristotle's Lean proof

本文介绍了利用 GPT-5.2 Pro 与 Aristotle 系统相结合，通过对二项式系数进行一种新颖的逐素数分析，生成了一个展示阶乘整除性中对数间隙现象的 Lean 形式化证明，从而实现了对埃尔德什问题 #728 的首次全自动 AI 解析。

原作者： Nat Sothanaphan

发布于 2026-01-27

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Nat Sothanaphan

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

核心概览：AI 数学家团队

想象一下，有一位著名的退休数学天才保罗·埃尔德什（Paul Erdős），他一生都在留下一个巨大的“待办事项”清单，上面全是未解之谜。其中一个谜题——#728，已经无人问津数十年了。

最近，由超智能 AI（GPT-5.2 Pro）和专门的数学检查机器人（Aristotle）组成的团队终于解决了它。他们不仅仅是猜出了答案；他们构建了一个严密的、循序渐进的证明，计算机可以验证其 100% 正确。这篇论文的作者只是将那段计算机代码翻译成人类可以阅读的故事。

谜题：阶乘的平衡术

这个问题探讨的是关于阶乘（例如 $5! = 5 \times 4 \times 3 \times 2 \times 1$ ）的问题。

想象你有一大堆代表 $n!$ 的积木。你想看看是否可以建造两个较小的塔 $a!$ 和 $b!$ ，以及第三个小塔 $k!$ ，使得这两个小塔能完美地嵌入大塔之中，且没有任何积木剩余。

用数学语言表达就是： $a! \times b!$ 能否整除 $n! \times k!$ ？

谜题的核心在于：这个“间隙”（ $k$ ）可以有多大？

如果 $k$ 很小，把积木塞进去很容易。
如果 $k$ 很大，通常是不可能的。
诀窍在于找到一个“金发姑娘区”（Goldilocks zone，意指恰到好处的区域）：让 $k$ 大到具有研究意义，但又不至于大到让积木无法放入。

AI 团队证明了，你可以找到无穷多种情况，使得这个间隙（ $k$ ）大约等于总数的对数（logarithm）。用通俗的话说：如果你的总积木数是一百万，间隙大约是 14；如果你的数字是十亿，间隙大约是 20。它增长得非常缓慢，但它确实在增长。

策略：“进位”游戏

为了解决这个问题，数学家们必须通过质数（2, 3, 5, 7 等）的视角来审视该问题。他们使用了一个叫做库默尔定理（Kummer's Theorem）的规则，这就像是加法中的“进位”游戏。

类比：溢出的水桶
想象你在用一种特定的语言（进制 $p$ ）进行加法运算。

当两个数字相加的结果超过了一个位置的容量时，你会将多出的部分“进位”到下一个位置。
目标： AI 需要找到一个数字（ $m$ ），当它被翻倍时，会产生大量的进位（就像水桶反复溢出一样）。
障碍： 与此同时，AI 还必须确保紧随 $m$ 之后的数字（如 $m+1, m+2...$ ）不会出现“尖峰”——即由于某个质数的高次幂导致的突然、大规模的可整除性，这会破坏平衡。

这就像是在走钢丝：

钢丝（“进位”条件）： 你需要选择一个“进位丰富”的数字。当你翻倍它时，它应该尽可能频繁地让水桶溢出。这创造了一个可整除性的“安全网”，有助于使等式成立。
尖峰（“坏”条件）： 你必须避开那些紧随其后的几个整数能被某个质数的高次幂整除的数字。这些是会把你从钢丝上撞下来的“尖峰”。

他们是如何找到解法的

AI 并没有随机挑选一个数字。它使用了一种计数论证（一种统计学策略）：

搜索区域： 他们观察了一个巨大的数字范围（从 $M$ 到 $2M$ ）。
过滤器： 他们计算了这个范围内有多少个数字是“坏”的（要么进位不够，要么出现了尖峰）。
结果： 他们证明了“坏”候选数字的数量实际上小于该范围内候选数字的总数。
结论： 由于“好”的数字比“坏”的数字多，因此在这一堆数字中一定至少存在一个“好”的数字。

这就像在说：“如果你有一个装有 1,000 个弹珠的罐子，其中只有 900 个是红色的（坏的），那么剩下的里面一定至少有 100 个是蓝色的（好的）。” AI 证明了对于任何足够大的罐子，总会存在一个“好”的弹珠。

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

首次 AI 独立证明： 这是 AI 系统首次自主解决埃尔德什著名的数学问题，并生成了人类可以验证的形式化证明。
“对数间隙”： 他们确认了数字之间的间隙可以是逻辑对数的。虽然论文指出，这个间隙可能比这稍微大一点（正如数学家特伦斯·陶教授所暗示的那样），但这一证明建立了一个稳固、可靠的基准。
方法论： 所使用的方法（计数进位并避开尖峰）与埃尔德什本人过去使用的技术类似，但在这里被应用于一个更复杂、动态的目标。

总结

这篇论文报告了一个 AI 团队如何解决一个 40 年前的数学谜题。他们展示了你总能找到一组特定的数字，使得一个复杂的阶乘等式完美平衡。他们通过将数字视为会溢出的水桶（进位），并证明你总能找到一个既能提供足够有用进位、又不会在错误的地方溢出过多的水桶，从而完成了这项工作。

技术摘要：Erdős 问题 #728 的解决

问题陈述
本文研究了 Erdős 问题 #728，该问题探讨在阶乘整除性约束下：
$a! b! \mid n! (a + b - n)!$
所能允许的最大间隙 $k := a + b - n$ 的大小。若不施加额外约束，则存在平凡解（例如通过取极大的 $a$ 和 $b$ 使 $k$ 任意大）。为了使问题具有非平凡性，作者施加了条件，即 $a$ 和 $b$ 远离极端值，具体为对于某个 $0 < \varepsilon < 1/2$ ，满足 $\varepsilon n \le a, b \le (1-\varepsilon)n$ 。目标是在这些约束条件下，确定 $k$ 相对于 $n$ 的增长规模。

方法论与证明策略
证明过程通过将阶乘整除性条件转化为关于二项式系数和 $p$ 进估值（ $p$ -adic valuations）的问题来进行。

简化为二项式整除问题：
通过令 $n = 2m$ ， $b = m$ ， $a = m + k$ ，原条件等价于：
$\binom{m+k}{k} \mid \binom{2m}{m}$
这要求证明对于每一个素数 $p$ ，左侧的 $p$ 进估值小于或等于右侧的 $p$ 进估值：
$\nu_p\left(\binom{m+k}{k}\right) \le \nu_p\left(\binom{2m}{m}\right)$
通过 Kummer 定理进行估值分析：
利用 Kummer 定理， $\nu_p\left(\binom{2m}{m}\right)$ 被识别为在基数 $p$ 下进行 $m + m$ 加法时产生的进位次数。项 $\nu_p\left(\binom{m+k}{k}\right)$ 则由连续块 $m+1, \dots, m+k$ 中任何项的最大估值 $V_p(m, k)$ 所界定。
核心需要满足的不等式为：
$V_p(m, k) \le \kappa_p(m)$
其中 $\kappa_p(m)$ 是 $m+m$ 在基数 $p$ 下的进位计数。
逐个素数的分析：
作者根据素数 $p$ 相对于 $k$ 的大小，将分析分为两个区间：
- 大素数 ( $p > 2k$ )： 在此范围内，不等式自动成立。由于区间长度 $k$ 小于 $p/2$ ，在块 $m+1, \dots, m+k$ 中最多只有一个数能被 $p$ 整除。如果某个高次幂 $p^J$ 整除了某项，则 $m$ 的基数 $p$ 展开式会迫使在倍增时至少产生 $J$ 个进位，从而满足条件。
- 小素数 ( $p \le 2k$ )： 这是主要难点。作者采用概率计数论证，在大型区间 $[M, 2M]$ $[M, 2 M]$ 中寻找一个整数 $m$ $m$ ，使其能同时满足对所有 $p \le 2k$ $p \leq 2 k$ 的两个条件：
  - 进位丰富型 (Carry-Rich)： $m$ 的基数 $p$ 展开式在前 $L_p$ 个位置中拥有许多大于等于 $\lceil p/2 \rceil$ 的数字。这会在 $m$ 倍增时强制产生大量进位 ( $\kappa_p(m)$ )。
  - 无尖峰型 (Spike-Free)： 块 $m+1, \dots, m+k$ 中的任何整数都不会被异常高的 $p$ 次幂整除（具体而言， $V_p(m, k)$ 被保持在阈值 $J_p + t(M)$ 以下）。
通过联合界限 (Union Bound) 证明存在性：
作者定义了不满足进位条件或尖峰条件的整数 $m$ 的“坏”集合。通过使用关于大数字分布的 Chernoff 界以及针对尖峰条件的简单计数，他们证明了这些坏集合的总测度严格小于区间 $[M, 2M]$ 的大小。因此，存在一个“好”的 $m$ 能同时满足所有相关素数的整除条件。

关键结果
本文确立了 定理 1 (对数间隙窗口)：
对于任何常数 $0 < C_1 < C_2$ 且 $0 < \varepsilon < 1/2$ ，存在无穷多个三元组 $(a, b, n) \in \mathbb{N}^3$ ，使得：

$\varepsilon n \le a, b \le (1-\varepsilon)n$
$a! b! \mid n! (a + b - n)!$
$C_1 \log n < a + b - n < C_2 \log n$

该构造产生的间隙 $k$ 随 $n$ 对数级增长。作者指出，目前的证明得出 $k \asymp \log n$ ，但通过进一步改进，该方法有可能扩展到 $k = \exp(c\sqrt{\log n})$ ，不过目前的写法侧重于对数区间。

意义与主张

首个由 AI 解决的 Erdős 问题： 作者声称这是第一个“完全由 AI 系统自主解决”的 Erdős 问题。所使用的系统是 GPT-5.2 Pro 与 Harmonic 公司的定理证明器 “Aristotle” 的结合。
形式化验证： 证明是以 Lean 定理证明器的形式生成的，随后被翻译成本文呈现的非形式化数学内容。
方法论贡献： 本工作扩展了 Erdős 和 Pomerance 关于中心二项式系数约数的既有技术。以往的工作侧重于“进位贫乏型”（进位少）整数或固定间隙大小，而本证明通过构造“进位丰富型”整数来处理大小为 $k \asymp \log n$ 的增长窗口。
独立性： 作者指出，在他们的初步工作之后，Carl Pomerance 独立推导出了类似的结论，并且该论证的修正版也被用于解决 Erdős 问题 #729 和 #401。

本文并未声称解决了该问题在绝对最强形式下的情况（注意到可能存在更大的间隙），但断言成功解决了 Erdős 所提出的特定的对数间隙问题。