Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey
Yihong Wu
cs.IT
2026-08-24
耶鲁 Yihong Wu 给出非渐近下界：Bernoulli 源线性编码的最优失真，就是无损压缩一部分、其余估零；证明初稿由 GPT-5.6 Sol 在交互中发现。
无损压缩 Bernoulli 信源时,线性编码器就能摸到香农熵 h(p):抛 n 个偏置为 p 的硬币,大约 nh(p) 个线性校验就够几乎无误还原。有损压缩允许平均 D 比例的比特解错,香农率失真函数是 R(D)=h(p)−h(D)。线性结构在这里严格达不到这条曲线。
Ancheta 在 1978 年给出线性编码器的失真下界。p=1/2 时,下界就是 (1−R)/2,而「留下前 Rn 比特、剩下的瞎猜」刚好打到。一般 p 时,对应的朴素方案是分时:对 R/h(p) 比例的比特做线性无损压缩,其余直接估成 0,得到失真 D=p(1−R/h(p))。Massey 在 1978 年问,线性编码器还能不能比这个分时更好,2009 年又重提。p=1/2 已被 Ancheta 肯定,一般 p<1/2 一直开着。
线性压缩器就是一个满行秩矩阵 H,把 n 比特映到 k 比特。最优逐位译码是后验边缘的 MAP:看到 HX=s,每位取更可能的 0 或 1。平均比特错误率 D(H) 就是各位「后验里较小那一侧」的期望。
关键引理把条件分布的熵绑到这些边缘上。把「HX=s」看成仿射子空间(陪集)A,PA 是 Bernoulli 测度在 A 上的条件律,e(A) 是按该测度加权的 Hamming 半径,也就是逐位 MAP 的条件损失。引理说 H(PA) ≤ (h(p)/p)·e(A)。对 s 取期望,再用 H(S)=H(X)−H(X|S)≤k,立刻得到非渐近逆定理:k/n ≥ h(p)(1−D(H)/p)。这和分时曲线是同一条,因此分时就是线性编码的最优。
证明把任意陪集收到零陪集上。Fourier 分析给出综合征在 0 处取最大质量;再对线性子空间的 Bernoulli 质量用半径做归纳上界。后半步也可以从铁磁 Ising 的 GKS 相关不等式读出来:零陪集的后验是铁磁的,全零的概率至少是各位边缘的乘积。
定理对任意满行秩 H 成立,不依赖渐近、随机矩阵或具体码构造。分时方案达到这条下界,因此 Massey 的问题答案是肯定的:线性编码器做有损压缩,最优就是无损压一部分、其余估零。
对偶说法落在二元对称信道 BSC 上。容量 CBSC=1−h(p)。线性码在速率 R 处于容量和 1 之间时,最优逐位 MAP 的比特错误率满足 Pb ≥ (p/h(p))(R−CBSC)。超过容量的线性码,误比特至少随「超容量多少」线性涨,系数是 p/h(p)。
没有数值模拟。紧性来自已知可实现的分时方案对上新的逆定理。图 1 画出 p=1/2 和 p=0.11 时香农 R(D)、Ancheta 逆、以及这条现已证紧的线性分时曲线,三条彼此分开。
对编码理论,这是一条干净的否定:强迫编码器线性,有损 Bernoulli 压缩就回不到香农极限,而且最优策略平凡。对做模型的人,记录本身更扎眼。证明初稿由 GPT-5.6 Sol 在作者引导的交互里发现,作者再简化成现在这篇自包含论证,并对技术内容负全责。事后用 Codex 做文献检索,发现若干引理零件已出现在编码和自旋玻璃文献里,包括 Sullivan 1967 的综合征众数、Cammarota 与 Russo 1991 的陪集 Bernoulli 测度、以及 GKS 不等式。
这更接近「模型在人的引导下写出一条后来能被文献部分回收的证明」,距离「机器独自关闭冷门猜想」还差一步。即便如此,把开了近五十年的问题写成可核对的短文,仍然是当前定理证明模型值得盯的样本。
这是理论短文,没有实验、没有有限长仿真、没有对非线性或近似线性方案的对照。失真只取 Hamming,字母表只取二元,编码器必须对 F2 线性。p=1/2 的特例不是新的。作者自己写明,若干支撑结果可从已有文献推出;GPT-5.6 的贡献是把它们收成这条熵不等式并打通主定理,不是从零发明整条工具链。交互过程、提示和失败路径没有公开,外部无法复现「发现」这一步。对偶的信道说法同样只覆盖线性码和逐位 MAP,不涉及最大似然码字译码或有限长界。