🔢 mathematics

Semidefinite and linear programming bounds for sum-rank-metric codes and non-existence results

本文利用半定规划和线性规划技术，建立了和秩度量码规模的新锐利上界，证明了这些上界优于现有方法，并利用它们证明了某些最优码和完美码的不存在性。

原作者： Aida Abiad, Antonina P. Khramova, Sven C. Polak, Ferdinando Zullo

发布于 2026-05-01

📖 1 分钟阅读🧠 深度阅读

原作者： Aida Abiad, Antonina P. Khramova, Sven C. Polak, Ferdinando Zullo

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试打包一个行李箱，但关于什么能装进去的规则非常奇怪。你不仅仅是在计算物品的数量；你正在以一种复杂、多层的方式测量它们彼此之间的“差异”。这就是和秩度量码（sum-rank-metric codes）的世界，这是一种用于组织数据的数学框架，应用于诸如在 shaky 网络上传输消息或在多台计算机之间存储文件等场景。

本文的主要目标是回答一个简单的问题：在这个行李箱中，你最多能装入多少件物品（码字），直到它们开始相互碰撞？ 如果它们靠得太近，数据就会受损。

以下是使用日常类比对本文发现的分解：

1. 问题：一个混合行李箱

将“和秩度量”想象为一个拥有两种类型隔间的行李箱：

汉明隔间（Hamming compartments）： 就像标准行李箱，你计算有多少只单独的袜子丢失或被交换。
秩隔间（Rank compartments）： 就像你关心衣物“图案”的行李箱（例如，是整件衬衫皱了，还是只是袖子皱了？）。

“和秩”度量是一种混合体。它既计算丢失的单个袜子，也计算图案褶皱。作者想知道这个极限：在这个混合行李箱中，你能装入多少套服装，使得没有两套服装过于相似？

2. 旧工具：用尺子测量

在这篇论文之前，数学家使用“尺子”（数学界）来猜测服装的最大数量。

线性规划（LP）界： 想象通过观察物品之间的平均空间来估算行李箱的容量。这是一个不错的猜测，但它假设物品的排列方式非常简单且可预测。
比率型界（Ratio-type Bound）： 这是另一把尺子，它查看你物品的“邻居”。它会问：“如果我选出一套服装，有多少其他服装就在它旁边？”

本文表明，对于某些特定类型的行李箱（具体来说，当只有“秩”部分起作用，或者当它只是一个标准的“汉明”行李箱时），这两把尺子实际上给出了完全相同的答案。它们是等价的。

3. 新工具：3D 扫描仪（SDP）

本文最大的创新是引入了一种名为**半定规划（SDP）**的新工具。

类比： 如果旧工具（LP）查看物品对（物品 A 和物品 B），那么新的 SDP 工具会同时查看三元组（物品 A、物品 B 和物品 C）。
为何重要： 想象试图将三个人塞进一辆小车里。如果你只查看 A 和 B 需要多少空间，你可能会认为他们能装下。但如果你同时查看这三个人，你就会意识到他们无法都舒适地坐下。SDP 工具捕捉到了旧工具遗漏的这些“群体动态”。
结果： 作者编写了一个计算机程序来运行这个新的 3D 扫描仪。他们发现，在许多情况下，这个新工具会说：“实际上，你能装入的服装数量比旧尺子预测的要少。”这意味着旧尺子过于乐观。新工具给出了更紧、更准确的极限。

4. “不可能”的行李箱（不存在性结果）

了解最大极限的终极目标是证明某些“完美”的行李箱不可能存在。

“完美”码： 想象一个打包得如此完美的行李箱，以至于完全没有浪费的空间。每一英寸都被利用，且没有两件物品靠得太近。在数学中，这被称为“完美码”。
“最大距离”码： 想象一个行李箱，其中的物品彼此之间的距离尽可能远，从而最大化安全边际。这就是"MSRD 码”。

作者利用他们新的、更锋利的尺子（SDP 和经过改进的 LP 界）来观察特定的行李箱尺寸。他们发现，对于许多这些尺寸，数学证明“完美”或“最大距离”的行李箱是无法建造的。

这就像试图用特定数量的砖块建造一座房子，这些砖块必须形成一个完美的正方形。你可能认为这是可能的，但如果你精确地测量砖块，你就会意识到数学上说不通——这座房子根本无法建造。本文列举了许多具体场景，在这些场景中，这些“完美”码在数学上是不可能的。

总结

背景： 一种测量数据错误的复杂方式（和秩度量）。
目标： 找出你可以安全存储的最大数据项数量。
创新： 一种新的数学"3D 扫描仪”（SDP），它查看三个物品的组，而不仅仅是成对物品。
发现： 这个新扫描仪证明，旧的估计值过高。
结论： 因为极限比我们想象的更紧，许多人们希望存在但实际上无法创建的“完美”数据存储系统，实际上是不可能的。

本文并不声称要建造一个新的行李箱或修复今天某个特定的网络；相反，它提供了一份更准确的数学景观地图，向我们展示了“完美”解决方案的确切位置（以及它们不存在的位置）。

以下是 Abiad、Khramova、Polak 和 Zullo 所著论文《求和秩度量码的半定规划与线性规划界及非存在性结果》的详细技术总结。

1. 问题陈述

本文解决了编码理论中的一个基本问题：确定在求和秩度量（sum-rank metric）下，具有指定最小距离 $d$ 的码的最大规模，记为 $A(q, n, m, d)$ 。

背景：求和秩度量推广了汉明度量（符号级错误）和秩度量（秩型错误）。它在多轮网络编码、分布式存储和空时编码等现代应用中至关重要。
挑战：虽然汉明度量和秩度量已有各种界，但求和秩度量的混合性质产生了独特的组合与代数现象。现有界（如 Singleton 界、汉明界、Plotkin 界和经典 Delsarte 线性规划界）往往无法提供紧的上界，或者无法在特定参数范围内排除最优码（如最大求和秩距离码（MSRD）或完美码）的存在性。
目标：利用谱图理论和优化技术（线性规划与半定规划）推导更精确的上界，并利用这些界证明极值码的非存在性。

2. 方法论

作者采用了一种结合代数图论、组合优化和计算实验的多面方法：

图论框架：他们将求和秩度量空间 $F_q^{n \times m}$ 关联到一个图 $\Gamma$ ，其中顶点是码字，边表示距离为 1。寻找最大码规模的问题等价于界定该图的独立数。
谱方法：他们利用求和秩度量图邻接矩阵的特征值来推导界。
- 比值型界（Ratio-type Bound）：基于图特征值的谱界。
- Lovász Theta 数：一种代数图论界。
线性规划（LP）：
- Delsarte LP：基于求和秩度量的关联方案，利用第二特征矩阵来约束距离分布。
- 比值型 LP：利用次多项式从比值型界推导出的线性规划公式。
半定规划（SDP）：
- Schrijver 型 SDP：作者引入了一种新的 SDP 界，扩展了 Delsarte 框架。虽然 Delsarte 的线性规划仅考虑成对距离，但该 SDP 引入了基于三个码字（特别是包含零向量的三元组）的约束，利用了编码这些三元组的矩阵的半正定性。
计算验证：作者使用 Julia 编程语言结合 Jordan 对称性约简包来计算各种参数下的这些界，并将其与已知理论界进行比较。

3. 主要贡献

A. 一种新的半定规划（SDP）界

本文针对求和秩度量引入了一种Schrijver 型 SDP 界。

机制：通过对码字三元组施加约束，加强了成对 Delsarte 线性规划。
性能：计算实验表明，在若干参数范围内，该 SDP 界严格优于现有最佳界（包括 Delsarte 线性规划、比值型界和经典编码界）。
层级关系：本文确立了层级关系： $A(q, n, m, d) \leq \text{SDP} \leq \text{Delsarte LP}$ 。

B. 极值情形下线性规划界的等价性

作者对Delsarte 线性规划界和比值型线性规划界进行了严格的比较：

秩度量情形（ $t=1$ ）：他们证明了对于双线性形式图（纯秩度量），Delsarte 线性规划的最优解恰好等于比值型线性规划的最优解。两者均等于 Singleton 界 $q^{m(n-d+1)}$ 。
汉明情形（ $n_i=m_i=1$ ）：他们证明了对于汉明图，在特定条件下（例如当 $q \geq \max\{d, t-d+2\}$ 时），这两个界是等价的。他们还提供了具体的反例（如二进制汉明码），在这些例子中两个界相等但严格小于 Singleton 界，从而证明了在这些特定情形下界是紧的。

C. 极值码的非存在性结果

利用新推导和精化的界，本文证明了某些最优码的不存在性：

MSRD 码：达到 Singleton 界的码。作者表明，对于特定参数（例如 $m=n=(2, \dots, 2)$ 且 $t \geq q-1$ 以及 $d=3$ ），比值型界严格小于 Singleton 界，从而证明了在这些范围内 MSRD 码不存在。
完美码：达到球堆积界且等号成立的码。
- 他们推导出了涉及求和秩度量中球体积的显式条件，在这些条件下完美码不存在。
- 他们利用同余论证（模 $p$ ）排除了加性完美码的存在。
- 他们表明，对于 $d=3$ ，比值型界通常严格优于球堆积界，从而证明了当 $t \not\equiv 1 \pmod q$ 时，完美码不存在。

4. 关键结果

更紧的上界：新的 SDP 界在许多测试场景中提供了求和秩码已知的最紧上界，优于 Delsarte 线性规划。
理论统一：在秩度量情形下证明 Delsarte 界与比值型界的等价性，统一了两种此前不同的方法，表明它们产生相同的结构极限。
非存在性定理：
- 定理 5.2/5.3：当 $t \geq q-1$ 时，对于 $m=n=(2, \dots, 2)$ ， $d=3$ 的 MSRD 码不存在。
- 定理 5.7/5.9：如果 $t \not\equiv 1 \pmod q$ ，则在 $m=(m, 1, \dots, 1)$ 的空间中， $d=3$ 的完美码不存在。
- 定理 5.10/5.11：如果 $t(q+1) \not\equiv 1 \pmod{q^2}$ ，则在 $m=n=(2, \dots, 2)$ 的空间中， $d=3$ 的完美码不存在。

5. 意义

方法论进步：这是 Schrijver 型 SDP 界首次应用于求和秩度量。它表明，除了经典线性规划之外，还需要优化技术才能有效地捕捉求和秩度量的“混合”性质。
解决开放问题：本文解决了求和秩设定中不同谱界与线性规划界之间关系的问题，阐明了它们在何时等价、何时发散。
实际影响：通过证明在特定参数范围内完美码和 MSRD 码不存在，本文引导研究人员避免在这些领域进行徒劳的最优构造搜索，并表明已知界很可能是真实的极限。
未来方向：这项工作突显了对称性约简在半定规划中处理更大参数的潜力，并表明一般求和秩设定中不同界之间的差距值得进一步的理论研究。

总之，本文通过引入强大的新优化工具（SDP）、统一现有的谱方法，并为先前未解决的案例中最优码的非存在性提供确凿证明，显著推进了对求和秩度量码的理解。