New Lower and Upper Bounds for the Grothendieck Constant
Rahul Saha, Alan Li, Anton Xue, Swarat Chaudhuri, Adam Klivans, Pravesh K Kothari, Raghu Meka
cs.CC, cs.DS
2026-08-12
上界压到 1.7818、下界从 1.6769 抬到 1.7135,首次确定 KG 十分位是 7;这对界出自人与长时程 AI 研究系统的协作。
Grothendieck 常数 KG 出自 1953 年的一条不等式:把定义在 ±1 号上的二次优化松弛成实向量问题,向量解的最优值最多比整数解好 KG 倍。常数的存在性早有证明,具体数值 70 多年没人算出来。它牵连很广,矩阵切范数等组合问题的近似算法、Banach 空间几何、调和分析与量子信息里都藏着这个常数,近似比直接由它决定。
数值上,两边纪录长期冻结。下界 1.6769 由 Davie(1984)和 Reeds(1991)用高维高斯构造独立给出,站了 40 多年;2026 年 Heilman 与 Jones–Malavolta 两项工作分别只把它抬高 10⁻²⁶ 和 10⁻¹²。上界 1.7822 是 Krivine 在 1977 年给出的,他同时猜想这就是精确值,该猜想 2011 年被 Braverman 等人推翻,之后的数值改进停留在 10⁻⁵ 量级。
上下界都围绕 Krivine 取整格式展开。取整格式是把向量解映射回 ±1 号的随机过程:先做一步无穷维的张量预处理,再用随机超平面切出符号。Krivine 用它证出上界,后续改进靠把超平面格式与别的低维格式「混合」。
上界一侧,论文引入极限 Krivine 格式(limiting Krivine schemes),一个能系统研究任意高维取整格式族的解析框架,并在其中构造出三次–五次格式:逐坐标相关函数取 (t − s₃²t³ + s₅²t⁵)/(1 + s₃² + s₅²) 的形状。此前所有工作只碰过一维或二维格式,这是第一个渐近意义下的高维构造,也正面回答了 Braverman 等人 2011 年提出的「升维能否改进上界」的问题。证明分解析与计算两步:解析步把逆级数的控制化归为对线性系数下界与非线性系数总量的估计;计算步用向外舍入的区间算术逐条验证有限条不等式,全部证书开源于 GitHub。
下界一侧,方向反过来:不构造具体的 gap 实例,去证明 Krivine 格式自身有天花板。对相关函数的 Taylor 系数,任何取整格式都满足仿射约束 b₃ ≥ 2b₁ − 11/6。仿射形式的关键性质是在混合与系数极限下保持,于是它约束了整个渐近族。配合 Naor 与 Regev 2014 年证明的「混合 Krivine 格式渐近最优」,天花板直接翻译成 KG ≥ 6π/11。
| 量 | 此前最佳 | 本篇 |
| 上界 | 1.7822(Krivine 1977,近年改进约 10⁻⁵) | π/(2log(1+√2)) − 3.47×10⁻⁴ ≈ 1.7818 |
| 下界 | 1.6769(Davie–Reeds,40 余年未动) | 6π/11 ≈ 1.7135 |
| 十分位 | 未知 | 7 |
上界改进量 3.47×10⁻⁴,比此前最佳改进大一个数量级以上;下界一步抬高 0.037,是 1984 年以来第一次实质移动。两条界合起来把 KG 钉在 1.7135 与 1.7818 之间,十分位确定为 7。
对理论侧的读者,这是 Grothendieck 常数问题几十年来最大的一次实质推进,也是「高维取整格式确实更强」的第一个证据。研究方式同样少见:这对界出自一个长期运行的人机协作项目,论文把数学研究描述为长时程任务(复杂目标、持久记忆、延迟回报),并专门写了一篇配套论文复盘协作流程。对关心 AI 系统能否撑起数月级数学研究的读者,这组数字本身就是数据点。
KG 的精确值仍然未知,1.7135 到 1.7818 之间还留着 0.068 的缝,百分位完全开放。下界论证依赖 Naor–Regev 的渐近最优性定理,天花板只对 Krivine 类格式成立——若存在该框架之外的取整方式,上界仍可能继续下探。AI 系统在发现过程中具体承担了什么、可靠到什么程度,本篇只有一句话交代,细节在配套论文里,单独读这一篇无法评估。