A counterexample to the Etzion-Silberstein conjecture

技术摘要：Etzion–Silberstein 猜想的反例

问题陈述
Etzion–Silberstein 猜想断言，对于任何 Ferrers 图 $D$、任何最小秩距离 $d$ 以及任何有限域 $\mathbb{F}_q$，线性 Ferrers 图秩度量码的维度的 Singleton 型上界都是可达的。具体而言，该猜想断言存在一个维度为 $k = \nu_{\min}(D, d)$ 的码，其中 $\nu_{\min}$ 是一个由图几何结构导出的组合界限。虽然该界限已被证明在大量的图族中是可达的，但该猜想在一般情况下（特别是针对小域）仍处于开放状态。

方法论
作者通过在二进制域 $\mathbb{F}_2$ 上构造一个特定的反例来推翻该猜想。该方法结合了组合归约、最大秩距离（MRD）码的分类以及穷举计算验证。

1. 反例选择： 作者关注列高为 $(5, 5, 5, 5, 1, 1)$ 且最小秩距离 $d=3$ 的 Ferrers 图 $E$。Etzion–Silberstein 界限预测其维度为 12。
2. 归约为核提升问题（Kernel-Lift Problem）： 存在一个二进制 $[E, 12, 3]$ 码的存在性被归约为在二进制 $[4 \times 4, 12, 2]$ MRD 码内是否存在一种特定结构。具体而言，当且仅当存在一个余维数为 2 的子空间 $K$ 位于 MRD 码 $U$ 内，且存在一个线性映射 $R: K \to \mathbb{F}_2^4$，使得对于每一个秩为 2 的矩阵 $M \in K$，向量 $R(M)$ 都不包含在 $M$ 的行空间内时，维度为 12 的码才存在。
3. MRD 码分类： 该证明依赖于对二进制 $[4 \times 4, 4, 4]$ 铺展码（spread codes，即所需 MRD 码的正交补）的分类。此类码恰好存在三个等价类。
4. 穷举排除：
   • 作者枚举了这三个 MRD 类中所有可能的余维数为 2 的子空间（核）$K$。总搜索空间包含 8,382,465 个核。
   • 应用了一个“秩-二过滤器”（引理 4），该过滤器证明任何有效的核必须恰好包含 105 个秩为 2 的矩阵。该过滤器完全排除了其中的两个等价类，并将剩余类中的搜索减少到四个特定的核轨道（orbits）。
   • 对于剩下的四个轨道，约束系统（要求对于所有秩为 2 的 $M$，满足 $R(M) \notin \text{row}(M)$）被编码为一组仿射奇偶方程。
5. 验证： 产生的约束系统被证明是不可满足的，使用了独立的 SAT 求解器（CaDiCaL 和 CryptoMiniSat）以及自定义验证器。验证过程包括对所有核进行不经过轨道缩减的原始枚举，以确保可复现性。

关键结果

• 上界： 作者证明了任何支持在 $E$ 上的二进制线性码，其最小秩距离为 3 时，其维度至多为 11。
• 下界： 构造了一个支持在 $E$ 上且最小秩距离为 3 的显式二进制 11 维线性码。
• 反驳： 由于最优维度为 11 而 Etzion–Silberstein 界限为 12，因此对于情形 $(E, 3)$ 在 $\mathbb{F}_2$ 上，该猜想是错误的。
• 传播： 利用“行锥传播”（row-cone propagation）恒等式，作者展示了该反例可以被扩展，从而为每一个最小秩距离 $d \geq 3$ 生成反例。具体而言，对于每个 $d \geq 3$，都存在一个 Ferrers 图，其界限预测维度为 12，但最优维度为 11。
• 极小性： 图 $E$（对应于不可约族 $E_n$ 中的 $n=6$）被确定为该失败实例中最小的实例；该族中较小的图在 $\mathbb{F}_2$ 上均能达到其界限。

意义与主张
本文确立了 Etzion–Silberstein 猜想并非普遍成立，即使是在最小的有限域上也是如此。作者声称其结果在负面层面解决了该猜想，并指出相关的抽样-包含（puncturing–inclusion）MRD 猜想在实例 $(n, d, \mathbb{F}) = (5, 3, \mathbb{F}_2)$ 下同样失效。

该工作强调了计算的严谨性和可复现性。证明被描述为“有限、精确且可独立复现的”，它依赖于精确的二进制算术而非浮点近似。作者提供了一个完整的验证包，包括显式的码构造、求解器日志以及数据的加密哈希值，允许独立研究人员验证不存在维度为 12 的码这一结论。该结果将一般性的猜想归约为不可约族，表明即使在这些基本结构内部，Singleton 型界限也不总是可达的。