← 返回 PaperDaily
大模型与智能体
这哥们用开源代码推翻了编码理论16年的著名猜想
编码理论里有个著名的Etzion–Silberstein猜想，断言一种“容量上界”总能被精确顶到。结果这篇论文用计算机穷举加精确约化，把一个12维的上界硬生生压到11维——差距只有1，但猜想已经凉透。更难得的是作者把验证包全部开源，任何人可复核，这种做事方式龙哥很欣赏。
龙哥读论文
发布于 2026-08-14 21:47:30
阅读 4
查看原文
原论文信息如下：
在数学的辽阔疆域里，最让人上头的事情之一，就是一个看起来“人畜无害”的猜想，被一个连小学生都能画出来的图案给终结了。Etzion–Silberstein猜想就是这么个倒霉蛋——它在编码理论里站了十几年，各路大神都以为它是对的，结果一个简单的列高(5,5,5,5,1,1)的格子图，在二元域上让它的上界从12掉到了11。听起来像只差一点点？但在数学里，反例从来不看差多少，而是“有一个就死了”。 引言 故事要从2009年说起。Etzion和Silberstein在构造子空间码时，引入了Ferrers图秩度量码的概念，并且给出一个看起来很自然的Singleton型上界。他们猜想：对于任意Ferrers图、任意最小秩距离、任意有限域，这个上界都是可以达到的。说白了，就是“无论形状多奇葩，总能在规定的格子里塞满信息比特，不多不少刚刚好”。
这个猜想一出来，就被当成一个“看似容易实则难啃”的硬骨头。许多研究者前赴后继，搞出了大量保证上界可达的图族。比如Etzion、Gorla、Ravagnani和Wachter-Zeh在2016年构造了一批最优Ferrers图秩度量码；Neri和Stanojkovski在2024年又证明了单调图族和MDS可构图族满足猜想。但整体而言，原猜想依旧“广泛开放”，连最近的论文都在说它“widely open”。
正是这种“大家都觉得它是对的”的背景下，Jitendra Prajapati的这篇论文给出了一个清脆响亮的反例，而且在最小域（二元域）上，挑了最小的不可约图族成员E6。更狠的是，作者不止给出反例，还附带了一个精确的、可复现的计算验证流程——把结论砸得死死的。
这里顺便提一句：Couvée和Neri在最近的工作中，把原猜想约化到了一类不可约图上，并且明确了“puncturing–inclusion MRD猜想”的失败情形与E-S猜想之间的联系。本文正是用他们分离出的不可约图E6作为“靶子”，顺带把五阶和六阶的puncturing–inclusion MRD猜想在二元域上也给推翻了。
问题背景及相关工作 要理解这个反例的分量，得先搞懂Ferrers图秩度量码到底是什么。把一个矩阵里的某些位置“镂空”，只允许在剩下的格子里填入数字，剩下的格子固定为0——这个镂空后剩余的“形状”就叫Ferrers图。Ferrers图必须是“顶部对齐且列高左对齐不增”的：每列的高度从左到右只降不升，所有格子靠上对齐。
所谓秩度量码，就是一组矩阵反例的诞生：Etzion–Silberstein猜想被推翻 先快速回顾一下主角的定义。Ferrers图（形象点说就是一堆“顶部对齐、左边齐整”的格子）上定义一个秩度量码，就是在这堆格子里填上二进制数，固定位置必须填0，并且要求任意两个不同的填法对应的矩阵之差，秩至少要达到某个阈值d。Etzion和Silberstein在2009年给出了一个维度上界（叫Singleton型上界），并且猜想：这个上界在任意有限域、任意Ferrers图、任意最小秩距离下都能取到。
本文选取的靶子，是列高为(5,5,5,5,1,1)的Ferrers图，记作E。所谓列高，就是从左往右每一列允许填数的格子数。注意最后一列只有1个格子，整个图形长得很像一块“缺了一角的砖”。这个图正是Couvée和Neri在2026年文章中分离出的不可约图E6，属于整个猜想“最难啃”的那一部分。
按E-S界公式，把d=3代进去，算出来上界是12：
图1：Etzion–Silberstein上界定义公式（ν_min表示所有j取值下ν_j的最小值，ν_j的值等于删除前j列和前d-1-j行后剩下的格子数）
图2：E图在d=3时三个ν值均为12，意味着E-S界给出的维度预测是12
听上去没啥毛病？问题就出在这里。作者证明：在二元域上，E上根本不存在12维的、最小秩距离为3的线性码——最大只能是11维，并且给出一个11维的显式码。上界是12，实际最大是11，这一高一低之间，E-S猜想就碎了。
图3：定理1的核心结论——二元域上E图的最小秩距离3码的维度不超过11
核心证明策略：从MRD码到核-提升问题 要证明“12维不存在”，直接枚举所有可能码是不可行的。作者的思路非常精彩——先把问题“约化”成一个更小、更可控的问题，然后用计算机精确穷举。
首先看E上任意一个矩阵的形状。因为最后两列高度只有1，所以任意支撑在E上的5×6矩阵，都可以分块写成下面这种形式：
图4：E上任意矩阵的分块结构，其中M是4×4块，r是顶行前4位，t是顶行后2位，右下角是2×2的零块
这里M是一个4×4的二进制矩阵，r和t都是行向量。零块是固定的，因为那些格子不在Ferrers图里。
如果存在一个12维的码C，把每个矩阵映射到它的4×4块M，这个投影映射在C上是单射（因为如果M=0，整个矩阵只剩顶行的一两个非零元素，秩最多是1，不满足最小秩距离3的要求）。于是投影的像U是一个12维的4×4矩阵空间。由于去掉顶行最多让秩减1，U中的非零矩阵秩至少为2。而4×4矩阵里，12维的秩至少为2的码，正好达到秩度量Singleton界，所以U是一个(4×4, 12, 2)的MRD码。MRD全称是Maximum Rank Distance，即最大秩距离码，这类码在秩度量编码理论中的地位相当于经典编码理论里的MDS码。
接下来关注t这个映射。t把U映射到F₂²，它的核K是一个子空间。因为如果t(M)=0，对应的矩阵尾部两列全是零，整个矩阵退化成一个5×4的秩距离3码，其维度不超过10（这也是由秩度量Singleton界决定的）。因此核K的维度正好是10。核K是U的一个余维数为2的子空间。
现在把r限制在K上，得到一个线性映射R: K→F₂⁴。对于K中一个秩为2的矩阵M，整个5×6矩阵的秩至少为3的条件，正好等价于：R(M)不在M的行空间里。用数学语言表达就是：
图5：核-提升问题中的关键条件——对每个秩2矩阵M，R(M)不能落在M的行空间中
反过来，如果给定一个(4×4, 12, 2) MRD码U，一个余维2的子空间K，以及满足上面条件的R，就可以构造出12维的码。这样，原问题和“找核-提升对(U, K, R)”变成了等价问题。这就是整篇论文的核心策略：把“存在12维码”转化为“存在满足特定约束的核-提升组合”，然后去穷举所有可能的组合。
精确计算的力量：三个MRD类与穷举消除 现在问题变成了：二元域上(4×4, 12, 2)的MRD码总共有多少种？这里的“种”指的是左乘右乘等价类。利用Frobenius内积的定义：
图6：Frobenius内积定义公式（Tr表示矩阵的迹，即对角线元素之和；Aᵀ表示矩阵A的转置）
对一个12维的MRD码U取正交补，得到一个4维的子空间S。可以证明S中所有非零矩阵都是可逆的——这种码叫作“扩散码”（spread code）。已知二元域上(4×4, 4, 4)扩散码只有三个等价类（这个结论来自de la Cruz等人的MRD码代数结构分类工作）。论文将这三个类分别命名为field类、第II类和第III类，并把每个类的基用十六进制编码明确写了出来。
图7：三个MRD码等价类详细信息表（包括自同构群大小、S的基、核轨道数量和覆盖的核总数）
对每个MRD码U，余维2的子空间K一共有多少个？这是一个高斯二项式系数的计算：在12维空间里选一个10维子空间，等价于在12维对偶空间里选一个2维子空间。算出来是2,794,155个。三个类加起来一共8,382,465个可能的K。
8百多万个核直接暴力枚举，其实也不是不能算，但作者更聪明——先用一个“秩二过滤器”大幅缩小范围。这个过滤器的核心是一个引理：如果(U, K, R)满足条件，那么K中秩2矩阵的数量A₂(K)必须精确等于105。这个结论的证明很巧妙：对每个2维子空间N（共有35个），考虑U中那些核包含N的矩阵，这构成一个4维子空间V_N，K与V_N的交集W_N的维度至少是2。条件是“R(M)不在M的行空间里”，这迫使W_N的维度恰好等于2。每个秩2矩阵的唯一右核N唯一确定，所以总数就是35×(2²-1)=105。
图8：核过滤器统计表——按MRD等价类列出核轨道数、最小A₂(K)值、经过过滤器后幸存的轨道数及表示的原始核数量
这一过滤非常犀利：第II类和第III类的所有核都被排除了（因为它们的A₂(K)最小值分别是117和113，都大于105）。field类原本有3,240个核轨道，经过过滤后只剩下4个核轨道幸存，对应的原始核数量只有70个。
最后一步，对这4个幸存的核轨道，逐一检查是否存在满足条件的R。每个秩2矩阵M给出一个析取约束：(R(M)n₁=1)或者(R(M)n₂=1)，其中n₁、n₂是M右零空间的一组基。这是一个精确的布尔可满足性问题（SAT问题）。作者使用CaDiCaL和CryptoMiniSat两个独立的SAT求解器，对4个核轨道分别求解，全部返回不可满足。也就是说，不存在满足所有约束的R。结论是：12维码不存在，最大维度只能是11。
图9：精确求解器中使用的分支策略——对每个未满足的析取约束，分支a=1或a=0,b=1，穷尽所有可能
值得一提的是，作者还做了三重独立的验证：一是用另一套语义计算重新求解全部186,562个核轨道代表，零个可满足；二是用完全不同的变量编码方式（48个变量对应U到F₂⁴的线性扩张）独立重构三个类和核轨道，结果一致；三是最直接的——不依赖任何轨道约化，直接枚举全部2,794,155个核（每个类），结论依然一致。三重验证加上SHA-256哈希清单，把可复现性做到了极致。
维度11的显式构造与验证 光证明“12维不存在”还不够，得确确实实拿出一个11维的码才算完整。论文给出了11个生成元的显式列表。每个5×6生成矩阵用6个十六进制数表示，每个数代表5比特的列向量。粗看这些数字是随机的，但经过精确的高斯消元验证，这11个生成元确实线性无关，它们张成一个11维的码，并且所有非零矩阵的秩至少为3。
图10：11维码的秩分布——0秩的有1个（零矩阵），3秩的有605个，4秩的有1098个，5秩的有344个
“0¹3⁶⁰⁵4¹⁰⁹⁸5³⁴⁴”这种表示法的意思是：码里一共有2048个矩阵（2¹¹个），其中1个零矩阵（秩0），605个秩3矩阵，1098个秩4矩阵，344个秩5矩阵。没有任何矩阵的秩小于3，因此这个码的最小秩距离确实是3。这样，上界11和下界11同时得到证明，问题彻底封死。
作者还注意到一个问题：转置后的Ferrers图（列高变为(6,4,4,4,4)）同样不满足E-S猜想。另外，在更小的不可约图E₄和E₅上，E-S猜想其实是成立的——这说明E₆是最小的反例，挑不出更小的了。
图11：生成矩阵的显式编码表——每一行表示一个生成矩阵的6个列向量（用十六进制表示）
反例的推广：行锥传播与任意距离 找到一个反例已经很厉害了，但能不能把反例推广到所有最小秩距离d≥3的情况？作者给出了一个极其优雅的推广机制，叫作“行锥传播”。
行锥操作的定义很简单：给定一个Ferrers图D，在它上面加一行（这一行可以通过所有列），再在右边追加b个高度为1的列（即b个单点列），其中b是该图在当前参数下的E-S上界值。记这个新图为R(D)。这个操作的效果是：最小秩距离从d提升到d+1，同时E-S上界b和最大可达维度a都保持不变。用数学语言表达就是：
图12：行锥传播引理的核心等式——上界b和最优维度a在行锥操作下保持不变，最小秩距离加1
为什么这个性质成立？上界这部分可以从E-S公式直接验证：在R(D)上计算d+1的ν值，恰好等于在D上计算d的ν值。而维度这部分，从R(D)上任意一个最小秩距离d+1的码出发，删除最上面一行，由于被删的行只包含一个非零行，秩最多减1，投影后得到一个D上的最小秩距离d的码，且投影是单射。反过来，给定D上任意一个a维最优码，需要构造一个R(D)上的最小秩距离d+1的码。这个构造的关键是利用Singleton界保证线段ℓ: A→F₂ᵇ是单射（因为a≤b），然后把每个矩阵M映射到分块矩阵M̂，左上角是零行和ℓ(M)，右下角是M和零块。由于两个对角块占用不同的行和列，秩正好是rk(M)+1≥d+1。
从E₀=E出发，反复应用行锥操作，得到一列Ferrers图E_t。对应的列高呈现出循环块结构：每迭代一次，前4列的高度加1，第5、6列高度加1，然后尾部追加12列高度为t的列、12列高度为t-1的列，依此类推。对每个E_t，最小秩距离是t+3，E-S上界恒为12，而最优维度恒为11——和原始的E₀一模一样。
图13：推广后的核心结论——对每个t≥0，E_t在距离t+3处的E-S上界恒为12，最优维度恒为11
递归构造还能保持秩分布的结构：秩分布从原始E₀的“0¹3⁶⁰⁵4¹⁰⁹⁸5³⁴⁴”变成E_t上的“0¹(3+t)⁶⁰⁵(4+t)¹⁰⁹⁸(5+t)³⁴⁴”——每个非零秩都加了t，而每个秩的矩阵个数保持不变。这个规律来自构造方式：每一层的M̂(i)的秩恰好比M(i)的秩大1。
图14：递归构造生成矩阵的公式——e_i是二元域F₂¹²的第i个标准基向量
最终结论：对每个最小秩距离d≥3，都存在一个Ferrers图（且可以选择不可约图），使得E-S界在二元域上不可达。这意味着E-S猜想不仅在个别图上失效，而是在无穷多个图上失效——从d=3开始，每一个距离都有反例。这个推广力度相当彻底。
龙迷三问 这篇论文到底在解决什么问题？ Etzion–Silberstein猜想被首次推翻。这篇工作最值得看的点是什么？ 论文通过精确计算证明二进制[E,12,3]码不存在，并构造出维度11的代码，同时将反例推广到所有最小秩距离d≥3。这篇工作的边界或风险在哪里？ 优点：证明过程严谨，计算可复现，提供了完整的验证包；缺点：依赖大量计算枚举，缺乏理论上的简洁解释。如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★☆
通过将维度12的假设代码投影到4×4 MRD码并利用核-提升条件，结合精确枚举和SAT求解器，证明不存在满足条件的代码，从而给出反例。实验合理度： ★★★☆☆
现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。学术研究价值： ★★★★☆
通过将维度12的假设代码投影到4×4 MRD码并利用核-提升条件，结合精确枚举和SAT求解器，证明不存在满足条件的代码，从而给出反例；更关键的是问题定义是否可复用到同类任务。稳定性： ★★★☆☆
现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。适应性以及泛化能力： ★★★☆☆
现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。硬件需求及成本： ★★★☆☆
现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。复现难度： ★★★☆☆
https://github.com/infinityscroll/etzion-silberstein-counterexample产品化成熟度： ★★★☆☆
论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。可能的问题： 依赖大量计算枚举，缺乏理论上的简洁解释。
[1] M. Calderini, M. Messia, and A. Neri, On the Etzion and Silberstein conjecture for block Ferrers diagrams, arXiv:2607.08239 (2026). [2] H. Beeloo-Sauerbier Couvée and A. Neri, Irreducible Ferrers diagrams in the Etzion–Silberstein conjecture, arXiv:2604.27868 (2026). [3] J. de la Cruz, M. Kiermaier, A. Wassermann, and W. Willems, Algebraic structures of MRD codes, Adv. Math. Commun. 10 (2016), 499–510. [4] T. Etzion, E. Gorla, A. Ravagnani, and A. Wachter-Zeh, Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory 62 (2016), 1616–1630. [5] T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory 55 (2009), 2909–2919. [6] A. Neri and M. Stanojkovski, A proof of the Etzion–Silberstein conjecture for monotone and MDS-constructible Ferrers diagrams, J. Combin. Theory Ser. A 208 (2024), 105937. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
