
GPT-6.2 Astra 在 Autoform-Hard 上唯一完成 Smoktunowicz 定理形式化
来源标题:GPT-6.2 Astra Formalizes Smoktunowicz's Gap Theorem
GPT-6.2 Astra 在 Autoform-Hard 的 56 项研究中唯一解出第 49 题——Smoktunowicz 关于分次代数增长性的 2006 年定理,成为榜单上唯一做到这一点的模型。它的证明耗时 94 分钟、约 1800 行 Lean,成本 21.58 美元,全程无人干预。中途它曾提交带缺口的部分证明被拒,随后如实报告未完成部分。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
在 Autoform-Hard 的 56 个研究级形式化任务中,恰好有一个任务将榜首区分开来。GPT-6.2 Sol 和 Claude Fable 5.2 解出了完全相同的 48 个任务。GPT-6.2 Astra 还解出了第 49 个任务,并且它是榜单上唯一做到这一点的模型:这是 Agata Smoktunowicz 在 2006 年提出的关于分次代数增长的一个定理。 它不仅是我们测试过的唯一一个将 Smoktunowicz 定理形式化的语言模型,也是我们听说过的唯一一个形式化。 Astra 的证明耗时 94 分钟,约 1,800 行 Lean 代码,并且在共同的开头之后,它走的路线与已发表的论证不同。在此处阅读带注释的证明。 Astra 在一个装有 Lean、Mathlib 和 shell 的沙盒中独自工作,受 Autoform-Hard 的三小时和 200 美元预算限制。没有任何人碰过它。整个运行按 Astra 的公开价格计算花费了 21.58 美元。 它差点提前结束。大约在第 47 分钟时,Astra 提交了一个部分证明:对于较简单的交换情形是完整的,但在一般情形中有一个缺口(一个 sorry)。评分器拒绝了它。Astra 随后提交了一份诚实的“未解决”报告,准确说明了它证明了什么、没证明什么。Autoform-Hard 不允许模型在花费 20 美元之前放弃,而 Astra 只花了约 8 美元,因此测试框架把它送回去继续工作。它在接下来的九分钟里思考,没有写任何代码,然后开始了一种新方法。在“未解决”报告提交 39 分钟后,评分器接受了完整证明。 Autoform-Hard 只在证明通过洁净室评分时才接受它。被评分的定理从任务的受信任副本重建,其陈述必须与原始陈述完全匹配,并且证明只能使用 Lean 的标准公理(propext、Quot.sound、Classical.choice)。然后一个独立的内核重放该证明。 这是对 Smoktunowicz 定理的形式证明,而不是对她证明的形式化。两者只在开头步骤上重合。 该定理是关于代数增长有多快。从少量生成元开始,数一数用至多 nnn 次乘法能构造出多少个独立元素。Smoktunowicz 证明了,对于某一类自然的代数族,这个计数要么增长不超过约 n2n^2n2,要么至少增长到约 n3n^3n3,绝不会以严格介于两者之间的速率增长。 Astra 用反证法论证。它假设增长率落在禁止范围内,并证明增长必然比假设的更慢,从而产生矛盾。 已发表的证明依赖于代数和代数几何中的三个深刻结果。它们都不在 Lean 的数学库 Mathlib 中,而将它们形式化本身就会是一个大项目。Astra 一个都没用。相反,它定义了一个称为 capacity 的量:一个空间在乘以一个固定生成片段时增长多少。Capacity 的行为类似于图中边界的大小,证明的其余部分就建立在它之上。 Capacity 在研究文献中有类似物。我们在下面的 Hard Mode 中追溯它们。 我们已经逐行注释了完整证明。你可以滚动浏览 Lean 代码,并查看三层评论: 从 Capacity.lean 开始,这是论证的核心;下面的 Hard Mode 会走过每一个文件。 查看每个模型在 Autoform-Hard 上的位置。感谢 Meta FAIR 的 AutoformBench 团队提供基准,感谢 OpenAI 允许发布证明以及模型推理的摘录。 从这里开始,本文面向想要了解数学以及这次运行逐分钟记录的读者。如果你不是数学家,这里是一个很好的停止点。 取一个域上的代数 AAA,由有限多个元素生成。数一数由至多 nnn 个生成元的乘积张成的空间的维数。如果它像 nδn^{\delta}nδ 那样增长,那么 δ\deltaδ 就是 AAA 的 Gelfand–Kirillov(GK)维数,这是衡量非交换代数有多大的一个标准度量。ddd 个变量的多项式环的 GK 维数为 ddd。 对于一般代数,GK 维数可以是 2 及以上的任意实数。额外的结构会排除某些值。Bergman 证明了没有任何值严格介于 1 和 2 之间 [KL00, Thm 2.5]。对于由自然数分次且没有零因子的代数,Artin 和 Stafford [AS95] 排除了 GK 维数严格介于 2 和 11/5 之间,而 Smoktunowicz [S06] 强化了这一结果: 定理 [S06, Thm 1]。一个由 N\mathbb{N}N 分次、没有零因子且零次部分有限维的域上有限生成代数,其 GK 维数要么至多为 2,要么至少为 3。 基准中的 Lean 陈述恰好具有这些假设。专家为 Meta FAIR 的 AutoformBench 编写并审计了它,独立于这次运行。 证明是一个矛盾。假设 GK 维数严格介于 2 和 3 之间。那么直到 nnn 次的所有元素构成的空间增长快于 n2n^2n2 但慢于 n3n^3n3,因此单个 nnn 次部分 dimAn\dim A_ndimAn 的增长快于线性但慢于二次。Astra 随后证明,慢于二次的增长实际上迫使线性增长。前半部分建立了一个分式除环 DDD,并遵循已知步骤。后半部分,即 capacity 论证,是它超越已发表证明的地方。 词汇:生成元中长度至多 nnn 的词的张成空间,以及关于基准增长定义的一些小事实。 按词长度计数和按分次次数计数给出的增长在常数因子内相同。这里用到了有限维零次部分。 用 dimAn\dim A_ndimAn 重述假设:GK 维数严格介于 2 和 3 之间意味着 dimAn\dim A_ndimAn 的增长快于线性但慢于二次。证明的其余部分表明这是不可能的。 因为 AAA 只多项式增长,任意两个非零元素都有公倍数(Ore 条件),所以 AAA 嵌入一个分式除环。 构造那个除环 QQQ,并在其中构造 DDD:即 aaa 和 bbb 次数相等的分式 a/ba/ba/b。其余论证都在 DDD 中进行。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。