A Proof of the Most Informative Boolean Function Conjecture
Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff
cs.DS, cs.IT
2026-09-22
港中文与 Google 用微分方程加区间算术完整证明 Courtade–Kumar 猜想：任何布尔函数经 BSC 后的互信息都不超过独裁函数的 1−H₂(p)。
2013 年 Courtade 和 Kumar 问了一个干净的问题。X 在布尔立方 {-1,1}^n 上均匀，Y 是把每个坐标独立翻一次得到的噪声拷贝，信道是交叉概率为 p 的二元对称信道（BSC）。g 是任意布尔函数，只吐一个比特。这个比特关于 Y 能带多少互信息？
独裁函数只看某一个坐标，互信息正好是 1−H₂(p)，H₂ 是二元熵。他们猜想：没有任何布尔函数能超过这个数，维数随便多大。这就是 Courtade–Kumar 猜想，也叫最信息布尔函数猜想。
他们自己穷举验证了 n≤7。后来十年里，Pichler、Piantanida、Matz 证了更弱的双函数版本 I(f(X); g(Y))；Samorodnitsky 证了噪声足够大、|1−2p| 小于某个绝对常数时成立；Yu 把平衡情形的局部最优再配上计算机辅助，把参数范围往外推。完整的、不限维数、不限偏置的证明一直空着。
骨架是港中文 Chen、Gohari、Nair 2025 年的微分方程方法，本身又是网络信息论里辅助接收机方法的连续极限。跟着噪声半群走：g(X) 关于信道输出的条件熵，噪声加大时以「边能量」的速率增长。把立方沿一个坐标切开，边能量变成两半的能量加上一个两点代价。全维不等式于是塌成一个两点的 Bellman 不等式：给定两个 [0,1] 随机变量的均值和平均熵，边代价的下界必须盖住候选函数 A 的一种凹性缺口。
平衡情形的候选 ϕ 在前作里已经提出，Bellman 不等式当时还是猜想。这篇先证 ϕ，再引入偏置修正 ψ（把输出熵相对 1 的缺口加回去），取 B = max{ϕ, ψ}。ψ 单独不满足 Bellman 不等式，所以必须走这个点点最大值。
ζ 是四点矩约束下边代价的下确界。目标对定律线性，支撑最多五个原子，优化空间大约十四维。他们不直接搜，而是做显式下界：四点矩下界 L₄、支撑平面、log-sum 不等式。奇异边界用解析估计切掉，剩下紧盒子用向外舍入的区间算术穷尽，工具是 Arb、MPFR 和 mpmath.iv。证书是有理端点的二分剖分，每个叶子盒子要么与可行域不相交，要么某个充分不等式在整个盒子上成立。点抽样不算数。
Google 这边用 Stellar Colosseum 多代理框架跑 Gemini，在前作附录的推广猜想边界附近找到反例，逼出更强的下界。文中写得很直白：绝大多数新颖想法由 AI 产生，港中文提供了 max-ϕ 候选和一个关键下界；从平衡推到非平衡的 Part 2，模型没有人工介入。
主定理：对任意 n≥1、任意 p∈[0,1]、任意布尔 g，
I(g(X); Y) ≤ 1−H₂(p)，
等号由独裁函数及其补达到。
没有新的实验表。能核对的是证明范围：不再要求函数平衡，不再限制噪声强度，不再限制维数。独立工作方面，Vu Khac Ky 与 Tuan Tran 用另一套熵产生加谱方法也给出了证明，两篇约定同时挂 arXiv。
计算侧是一叠证书，覆盖小边界定理、接缝与端点、驻点 Case E、径向驻点、同侧盒子、对侧盒子，以及中心方块 [1/10, 9/10]² 上全部正熵可行点。论文加补遗共 251 页，刻意从第一原理重写引用过的证明，方便核验。
对做信息论和布尔分析的人，这是 2013 年以来这条线上的终点之一。独裁函数在坐标噪声下最能保信息，现在是定理。它和超压缩、等周、敏感度不等式是亲戚；更强的 Hellinger 型猜想还在外面。
对做 AI 的人，这篇更像一份工作记录：一个卡了十年的有限维优化，被多代理加区间算术拆开。Google 自己在加速科研的案例集里点过这道题。可复现的部分是证书和 Arb 记录，不是聊天记录。
从业者不要指望从这里抄一个算法。它不训练模型，也不给新的编码方案。它把一个被反复部分证明的不等式钉死了。
计算机辅助证明把正确性押在区间包络和证书程序上。作者分开核了对覆盖（二分树）和对算术（向外舍入），补遗 S.24 区分了原始运行、结构审计和独立重跑。这仍然不是一页纸的人类可扫证明。251 页「自包含」本身就是审计负担。
文中承认前作附录的推广猜想（Conjecture 5）是错的，AI 找到了边界反例。主猜想没被推翻，但说明候选函数的推广非常脆。
更强的 Hellinger 型猜想（蕴含 CK）这篇没碰。Ky–Tran 的另一条证明同时挂出，两边都还没互相核对。
「绝大多数新颖想法由 AI 产生」是作者自己的表述。读者能核的是定理陈述和证书哈希，不是想法归属。