An elementary proof of the Komlós conjecture
Sankeerth Rao Karingula, Shachar Lovett
math.CO, cs.CC
2026-09-18
Karingula 与 Lovett 给出 Komlós 猜想初等证明：单位欧氏向量配符号后无穷范数不超过 36。原证明由 Odin 智能体发现、常数约 7.5，这篇优先可读性，没有多项式时间算法。
Komlós 猜想是差异理论里的老问题，Spencer 写进讲义，Beck–Fiala 猜想是它的一个特例。给 n 个欧氏长度不超过 1 的向量，问能不能给每个向量配上 +1 或 -1，让带符号和的无穷范数被一个与 n、d 无关的常数挡住。
Spencer 的六标准差定理给出集合差异的 O(√n)。Banaszczyk 在 1998 年用向量平衡定理把 Komlós 推到 O(√log n)。此后 Gram–Schmidt walk 给出可构造版本。2026 年 Bansal 与 Jiang 第一次打破这个对数根号，做到 O((log n)^{1/4}(log log n)^{7/4})，Ercan 再去掉迭代对数，剩下 O((log n)^{1/4})。常数界一直没落地。
2026 年 9 月，Guo、Fang、Lu 给出证明，常数 C = 3√(2π)（约 7.5）。他们把发现归功于 Odin Automatic AI Research Agent，论证走 Banaszczyk 的凸体变换和密度的方向全变差。Karingula（Agentin AI）与 Lovett（UCSD）读懂这篇之后，抽出一份只靠组合、概率和初等微积分的证明，常数放松到 36。
核心量是移位距离：一个有限支撑的分布 P，沿向量 u 平移之后，与原分布的总变差。移位距离小，说明 P 和它的平移有大块重叠。
证明拆成两段。第一段是组合归纳。若 P 对每个 6vi 的移位距离不超过 1/3，就能找到一组符号，让均值加上带符号和仍落在 P 的支撑凸包里。归纳时沿最后一个向量做一次分裂：把质量按 max/min 分到一个新的 0/1 坐标上，重叠部分至少 1/3。对前 n-1 个向量归纳，再把质量拉回原来的支撑。只有一位的那些点有两个父节点，可以在 ±3v 之间连续分配，刚好补上最后那个符号。
第二段是造一个这样的 P。先在立方体 [-6,6]^d 上放一个乘积密度，每个坐标是帐篷函数的平方。沿 v 平移的总变差不超过 ||v||2 / √12。再把密度圆整到包含全部有理向量的网格。圆整不增加总变差。因为 ||vi||2 ≤ 1，移位距离小于 1/3。有理情形直接得出无穷范数 ≤ 36；实向量用有理逼近再取极限。
和 Guo 等人的关系：他们加一个额外坐标，把密度往零点重排。这里把额外坐标收成一个比特，用分裂算子代替凸几何。代价是常数从约 7.5 变成 36。作者明确没去压这个常数。
| 结果 | 界 | 说明 |
| Banaszczyk 1998 | O(√log n) | 此前长期最佳 |
| Bansal–Jiang / Ercan 2026 | O((log n)^{1/4}) | 第一次打破对数根号 |
| Guo–Fang–Lu 2026 | 3√(2π) ≈ 7.5 | AI 智能体发现 |
| 本篇 | 36 | 初等证明，有理输入有有限构造 |
有限构造对有理输入成立，没有多项式时间算法。强 Komlós 猜想（每个前缀和都被同一常数挡住）这篇碰不到，Guo 等人也碰不到。前缀版本目前最好的与维数无关的界仍是 Banaszczyk 的 O(√log n)。Aden-Ali 有一个在线随机算法，高概率达到同样的前缀阶。
对做理论的人，Komlós 从「差一个对数根号」变成「有一个具体常数」，而且证明可以在讨论班上从头写完。对看 AI 自动定理证明的人，故事更具体：Odin 先给出第一份证明，人类再把它改成不需要凸几何的版本。常数变差，可读性换上来。Lovett 本人是 Gram–Schmidt walk 的作者之一，这篇可以看成对 AI 证明的人工消化。
差异理论管舍入、去随机化和近似算法里的向量平衡。常数 36 对算法实践偏松，意义主要在存在性。
作者自己列了三条。常数 36 比 3√(2π) 差一截，没有优化。没有多项式时间算法，有理构造的支撑规模可以很大。强 Komlós / 前缀版本完全开放。
Odin 发现原证明这件事写在引言里，这篇没有复现那个智能体，也没有比较「AI 证明」和「人改写」在验证成本上的差别。写作过程用了 ChatGPT-6 Astra 迭代改证明和行文。对想跟进自动定理证明工程的人，这篇提供的是消化后的数学，不是系统论文。