Block Tensor Rank of Sum-Rank Metric Codes

技术摘要：和-秩度量码的块张量秩

问题陈述
和-秩度量码（Sum-rank metric codes）通过将码字表示为被划分为固定块的矩阵元组，并以各块的秩之和作为权重，从而将汉明度量码（Hamming-metric codes）与秩度量码（rank-metric codes）进行了推广。虽然秩度量码中的张量秩不变量（即生成码的秩-1矩阵的最少数量）已被广泛研究，但一种专门针对和-秩码的块结构而设计的相应不变量尚未得到系统的开发。本文旨在解决如何定义并计算适用于和-秩码的“块张量秩”（block tensor rank）这一挑战，该指标需尊重块分解结构，并区别于支持集理论的不变量及现有的用于等价性测试的张量方法。

方法论与定义
作者引入了块简单张量（block-simple tensors）的概念，定义为完全支撑于单个块内的秩-1矩阵。和-秩码 $C$ 的块张量秩（记作 $btrk(C)$）定义为其线性张成空间包含$C$ 的最小块简单张量数量。

其核心方法论包括：

1. 生成元元组（Generator Tuples）： 通过线性映射将每个码与一组 3-张量（每个块一个）相关联。
2. 块分解（Blockwise Decomposition）： 证明整个码的块张量秩等于其各个块投影的张量秩之和。这使得全局问题可以简化为标准的秩度量码张量秩问题。
3. 坐标码论证（Coordinate-Code Argument）： 通过将码字相对于块简单基底的系数进行映射，构造一个定义在基域 $\mathbb{F}_q$ 上的线性块码（即“坐标码”）。这使得可以将经典的汉明度量界限转移到块张量秩的设定中。

主要贡献与结果

• 结构分解定理： 本文确立了 $btrk(C) = \sum_{i=1}^t trk(\pi_i(C))$，其中 $\pi_i(C)$ 是码在第 $i$ 个块上的投影，$trk$ 表示标准张量秩。该恒等式意味着计算块张量秩可以分解为对每个块进行独立的张量秩计算。
• 下界： 推导出了两个互补的下界：
  • 投影维度的界限（Projection-wise Bound）： 直接从分解定理导出，表明 $btrk(C) \ge \sum N_q(k_i, d_i)$，其中 $k_i$ 和 $d_i$ 分别是第 $i$ 个投影的维数和最小秩距离。
  • 坐标码界限（Coordinate-Code Bound）： 从码的全局参数 $(k, d)$ 导出，表明 $btrk(C) \ge N_q(k, d)$，其中 $N_q(k, d)$ 是具有维数 $k$ 和最小汉明距离 $d$ 的线性码的最短长度。
  • Singleton 与 Griesmer 细化： 通过对 $N_q(k, d)$ 应用经典的 Singleton 和 Griesmer 界限，作者推导出了 Singleton 坐标码界限（$btrk(C) \ge k + d - 1$）和 Griesmer 坐标码界限（$btrk(C) \ge G_q(k, d)$）。
• 极值概念：
  • BTR 码： 达到 Singleton 坐标码界限（$btrk(C) = k + d - 1$）的码。
  • 块张量秩极值码（Block-Tensor-Rank-Extremal Codes）： 达到更紧凑界限 $btrk(C) = N_q(k, d)$ 的码。
• 构造方法：
  • 块对角提升（Block-Diagonal Lifting）： 引入了一种通用方法，通过对角映射将经典的线性块码（“骨架”）提升为矩阵块，从而构造和-秩码。
  • BTR 系列码： 在特定的参数范围内（胖块、均匀 MDS 骨架和汇聚/Pooling 机制），利用 MDS 骨架（如 Reed–Solomon 码）提供了 BTR 码的显式构造。
  • Griesmer 最优系列码： 利用 Griesmer 最优骨架（如 Simplex 和 MacDonald 码），作者构造了达到 Griesmer 坐标码界限的码；这些码是极值的，但当 $G_q(k, d) > k + d - 1$ 时，不一定是 BTR 码。
• 与 MSRD 码的比较： 本文证明了 BTR 最优性和最大和-秩距离（MSRD）最优性是不同的概念。具体而言，在均匀 MDS 骨架提升机制下，码无法同时达到 BTR 阈值和均匀 MSRD 维数。此外，作者应用其投影间隙准则（projection-gap criterion）对现有构造（Chen [19] 和 Lao 等人 [20]）进行了评估，结果显示，虽然某些构造接近 BTR 阈值，但另一些（如某些 MSRD 码）由于其块投影具有较高的张量秩，表现出较大的间隙。

意义与主张
本文声称提供了第一个通过块适配张量秩视角分析和-秩码的系统框架。其意义在于：

1. 统一性： 将和-秩编码理论与张量分解理论及经典汉明度量界限联系起来。
2. 计算简化： 块分解定理将块张量秩的计算简化为已知的秩度量张量秩问题。
3. 新的最优性准则： 引入了 BTR 码和块张量秩极值码作为新的最优码类别，它们有别于 MSRD 码。
4. 结构洞察： 作者认为块张量秩可以作为衡量码的“代数经济性”（algebraic economy）的一种度量。他们指出，这一不变量可能在区分后量子密码学中的结构化码族与随机码族方面具有相关性，尽管他们并未提出具体的密码方案或攻击方法。

文章最后确定了一些开放性问题，包括在提升构造之外对 BTR 存在性的参数范围进行分类，以及使用块张量秩作为基于码的密码学中结构特征判别器的潜力。