跳转至

Bounds on Maximum Hermitian Hull Dimension of MDS Codes and MDS Codes With Explicit Hermitian Hulls

作者: Huimin Lao, Hao Chen, Yeow Meng Chee, San Ling, Yang Li
来源: IEEE Transactions on Information Theory
主题: 其他
相关性: 0/10
机构绿灯: Nanyang Technological University（US News 前 50，免分进入精读）
链接: https://doi.org/10.1109/tit.2026.3698563

一、领域脉络与小综述

这个方向是什么

本文研究的核心问题是：在有限域 \(\mathbb{F}_{q^2}\) 上，给定码长 \(n\) 和维数 \(k\)，所有最大距离可分（MDS）码中，Hermitian 核（Hermitian hull）的最大可能维数是多少？记这个最大值为 \(L_q(n,k)\)。Hermitian 核是码与其 Hermitian 对偶的交集，其维数直接决定了从该码构造量子纠错码（特别是纠缠辅助量子纠错码，EAQECC）时所需的纠缠资源量。因此，确定 \(L_q(n,k)\) 并构造达到该维数的 MDS 码，是编码理论与量子信息交叉领域的一个基础性问题。该方向目前处于活跃构造阶段：已有大量针对特定参数区间（如 \(k \leq q\)）的构造，但一般参数（尤其是 \(k \geq q+1\)）的完整刻画仍远未完成。

发展脉络（history）

根据本文引言及其引用的文献，该方向的发展脉络可梳理如下：

  1. 奠基工作：Hermitian 自正交码与量子纠错码的关联。早期工作（如 Ashikhmin & Knill, 2001；Ketkar et al., 2006）建立了从经典 Hermitian 自正交码（即 Hermitian 核维数等于 \(k\) 的码）构造量子稳定子码的标准方法。这奠定了研究 Hermitian 核维数的动机：核越大，构造量子码时所需的纠缠资源越少。

  2. 主要进展：GRS 码的 Hermitian 核构造。广义 Reed-Solomon（GRS）码是 MDS 码中最经典的一类。一系列工作（如 Fang et al., 2020；Chen et al., 2021；Luo et al., 2022）系统地研究了 GRS 码的 Hermitian 核维数，给出了 \(L_q(n,k)\) 在 \(k \leq q\) 时的下界和显式构造。这些工作表明，当 \(k \leq q\) 时，可以构造 Hermitian 核维数接近 \(k\) 的 MDS 码。但作者指出，这些构造依赖于 GRS 码的特定代数结构，当 \(k \geq q+1\) 时，GRS 码的维数受限于 \(q+1\)（因为 GRS 码的维数不能超过其定义域的大小 \(q+1\)），因此无法覆盖 \(k \geq q+1\) 的情形。

  3. 当前 Frontier：突破 GRS 码的限制。为了处理 \(k \geq q+1\) 的情形，研究者开始探索 GRS 码的推广类。Beelen et al. (2018) 引入了扭曲广义 Reed-Solomon（TGRS）码，这是一类比 GRS 码更广的 MDS 码类，其维数可以超过 \(q+1\)。Chen et al. (2022) 首次研究了 TGRS 码的 Hermitian 核，并构造了 Hermitian 自正交的 TGRS 码。本文正是在此基础上，系统研究 TGRS 码的 Hermitian 核维数，并试图回答一个由 Fang et al. (2020) 提出的开放问题：当 \(k \geq q+1\) 时，\(L_q(n,k)\) 的下界是什么？

子线索聚类

该方向的被引文献大致落在以下两条子线索上：

  • 线索一：基于 GRS 码的 Hermitian 核构造。这一簇的工作（Fang et al., 2020; Chen et al., 2021; Luo et al., 2022）专注于利用 GRS 码的代数结构（如选择特定的求值点和乘子）来控制其 Hermitian 核维数。其优势在于构造简单、理论成熟；其瓶颈在于维数 \(k\) 受限于 \(q+1\)，无法处理长码。
  • 线索二：基于非 GRS 码的 Hermitian 核构造。这一簇的工作（Beelen et al., 2018; Chen et al., 2022; 本文）探索 GRS 码的推广类（如 TGRS 码、代数几何码等），以突破维数限制。其优势在于能构造参数范围更广的 MDS 码；其瓶颈在于代数结构更复杂，对 Hermitian 核维数的精确控制更难。

这个方向在追问的核心问题

  1. \(L_q(n,k)\) 的精确值是多少？ 目前只有上界（由码的 Singleton 界和 Hermitian 对偶的性质给出）和一些特定参数下的下界，精确值远未确定。
  2. 如何构造达到 \(L_q(n,k)\) 的 MDS 码？ 对于 \(k \geq q+1\) 的情形，是否存在非 GRS 的 MDS 码能达到比 GRS 码更大的 Hermitian 核维数？
  3. TGRS 码的 Hermitian 核维数能否被精确刻画？ 对于一般的扭曲参数，TGRS 码的 Hermitian 核维数是否有一个统一的公式或紧的界？
  4. 这些构造能否导出更优的量子纠错码？ 更大的 Hermitian 核维数意味着更少的纠缠资源，能否构造出参数更优的 EAQECC？

⚠️ 作者的 framing

作者将缺口 frame 为：“当 \(k \geq q+1\) 时，\(L_q(n,k)\) 的下界是未知的，这是一个由 Fang et al. (2020) 指出的开放问题。” 作者声称，通过引入 TGRS 码，他们可以部分解决这个问题，即证明 \(L_q(n,k) \geq k/2\) 并给出显式构造。

  • 被淡化或回避的竞争路线：作者主要聚焦于 TGRS 码，但并未深入讨论其他非 GRS 的 MDS 码类（如代数几何码、Gabidulin 码等）在解决该问题上的潜力。作者暗示 TGRS 码是“自然的推广”，但未提供证据表明其他码类在此问题上不如 TGRS 码有效。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？ 本文的引言和参考文献列表看起来是完整的，覆盖了该方向的主要工作。未见明显缺失的关键文献。

张力

未见明显对立引用。该方向的工作是累积性的：GRS 码的构造为 \(k \leq q\) 的情形提供了答案，而 TGRS 码的构造则试图将答案扩展到 \(k \geq q+1\) 的情形。不同工作之间没有根本性的矛盾，只是在参数覆盖范围和构造技巧上有所差异。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

  • 符号：

    • \(\mathbb{F}_{q^2}\)：一个含有 \(q^2\) 个元素的有限域，其中 \(q\) 是一个素数幂（\(q>2\)）。
    • \(n\)：码长，即码字（codeword）的长度。
    • \(k\)：码的维数，即码作为 \(\mathbb{F}_{q^2}\)-向量空间的维数。
    • \(d\)：码的最小距离。一个 \([n,k,d]_{q^2}\) 码是 \(\mathbb{F}_{q^2}^n\) 的一个 \(k\) 维子空间，其最小 Hamming 距离为 \(d\)。
    • MDS 码：满足 \(d = n - k + 1\) 的码，即达到 Singleton 界的码。
    • Hermitian 内积：对于 \(\mathbf{x} = (x_1, \dots, x_n), \mathbf{y} = (y_1, \dots, y_n) \in \mathbb{F}_{q^2}^n\)，其 Hermitian 内积定义为 \(\langle \mathbf{x}, \mathbf{y} \rangle_h = \sum_{i=1}^n x_i y_i^q\)，其中 \(y_i^q\) 是 \(y_i\) 在 \(\mathbb{F}_{q^2}\) 上的 \(q\) 次幂（即 Frobenius 自同构）。
    • Hermitian 对偶码：\(C^{\perp_h} = \{\mathbf{x} \in \mathbb{F}_{q^2}^n : \langle \mathbf{x}, \mathbf{y} \rangle_h = 0 \text{ for all } \mathbf{y} \in C\}\)。
    • Hermitian 核（Hermitian hull）：\(Hull_h(C) = C \cap C^{\perp_h}\)。其维数记为 \(\ell = \dim(Hull_h(C))\)。
    • \(L_q(n,k)\)：在所有 \([n,k]_{q^2}\) MDS 码中，Hermitian 核维数的最大值。
    • GRS 码：广义 Reed-Solomon 码。由一组求值点 \(\mathcal{A} = \{\alpha_1, \dots, \alpha_n\} \subseteq \mathbb{F}_{q^2}\) 和一组乘子 \(\mathbf{v} = (v_1, \dots, v_n) \in (\mathbb{F}_{q^2}^*)^n\) 定义：\(GRS_k(\mathcal{A}, \mathbf{v}) = \{(v_1 f(\alpha_1), \dots, v_n f(\alpha_n)) : f(x) \in \mathbb{F}_{q^2}[x], \deg(f) < k\}\)。
    • TGRS 码：扭曲广义 Reed-Solomon 码。是 GRS 码的推广，其定义中允许对多项式 \(f(x)\) 的某些高次项进行“扭曲”。具体定义见下文。

  • 模型：

    • 数据生成机制：我们考虑一个确定的代数编码问题。没有随机性。我们研究的是所有可能的 \([n,k]_{q^2}\) MDS 码的集合，并试图找出其中 Hermitian 核维数最大的那个。
    • 统计模型：不适用。这是一个纯组合/代数问题。

  • 可观测数据：

    • 研究者可以观测到的是码 \(C\) 本身（即其生成矩阵或校验矩阵）。Hermitian 核 \(Hull_h(C)\) 可以通过计算 \(C\) 和 \(C^{\perp_h}\) 的交集得到。
    • 想要但观测不到的是：在所有可能的 MDS 码中，Hermitian 核维数的最大值 \(L_q(n,k)\)。这是一个全局优化问题的解，无法直接观测，只能通过构造和证明来逼近。

第二步：讲最小内核

本文的核心思路可以浓缩为以下最简特例：

最简特例：考虑 \(n = q^2 - 1\)，且 \(n\) 整除 \(q^2 - 1\)（这总是成立的）。设 \(\omega\) 是 \(\mathbb{F}_{q^2}\) 的一个本原元（primitive element），则 \(\mathcal{A} = \{1, \omega, \omega^2, \dots, \omega^{n-1}\}\) 是 \(\mathbb{F}_{q^2}^*\) 的一个循环子群。我们考虑一个经典的 GRS 码 \(C = GRS_k(\mathcal{A}, \mathbf{1})\)，其中乘子全为 1。

问题：这个 GRS 码的 Hermitian 核维数是多少？

核心思路：Hermitian 核 \(Hull_h(C)\) 由所有满足 \(\langle \mathbf{c}, \mathbf{c}' \rangle_h = 0\) 对所有 \(\mathbf{c}' \in C\) 成立的 \(\mathbf{c} \in C\) 组成。由于 \(C\) 是 GRS 码，其 Hermitian 对偶 \(C^{\perp_h}\) 也是一个 GRS 码（具体地，\(C^{\perp_h} = GRS_{n-k}(\mathcal{A}^q, \mathbf{u})\)，其中 \(\mathcal{A}^q = \{\alpha^q : \alpha \in \mathcal{A}\}\)，\(\mathbf{u}\) 是某个乘子向量）。因此，\(Hull_h(C) = C \cap C^{\perp_h}\) 是两个 GRS 码的交集。

关键观察：当 \(\mathcal{A}\) 是 \(\mathbb{F}_{q^2}^*\) 的乘法子群时，\(\mathcal{A}^q = \mathcal{A}\)（因为对任意 \(\alpha \in \mathcal{A}\)，\(\alpha^q\) 也在 \(\mathcal{A}\) 中）。这意味着 \(C\) 和 \(C^{\perp_h}\) 的求值点集相同。此时，两个 GRS 码的交集可以通过分析它们定义多项式的次数来刻画。具体地，\(C\) 由次数 \(<k\) 的多项式生成，\(C^{\perp_h}\) 由次数 \(< n-k\) 的多项式生成（经过乘子调整）。它们的交集由次数 \(< \min(k, n-k)\) 的多项式生成。因此，在这个特例下，Hermitian 核维数 \(\ell = \min(k, n-k)\)。

本文的推广：上述特例给出了一个下界 \(L_q(n,k) \ge \min(k, n-k)\)。但当 \(k \ge q+1\) 时，这个下界可能很弱（例如，当 \(k > n/2\) 时，\(\min(k, n-k) = n-k\)，可能远小于 \(k/2\)）。本文的核心贡献在于，通过引入 TGRS 码（它允许使用次数 \(\ge k\) 的多项式，从而突破 GRS 码的维数限制），证明对于 \(n \mid q^2-1\) 且 \(k \ge q+1\) 的情形，\(L_q(n,k) \ge k/2\)。这个下界比 \(\min(k, n-k)\) 更好（当 \(k > 2n/3\) 时，\(k/2 > n-k\)）。其证明思路是：构造一个 TGRS 码，使得其 Hermitian 核包含一个由次数在某个区间内的多项式生成的子空间，该子空间的维数至少为 \(k/2\)。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：本文研究了有限域 \(\mathbb{F}_{q^2}\) 上 MDS 码的最大 Hermitian 核维数 \(L_q(n,k)\)，特别是当 \(k \geq q+1\) 时的下界问题。
  2. 核心工具 / 方法：本文使用扭曲广义 Reed-Solomon（TGRS）码作为主要构造工具，通过精心选择扭曲参数和求值点，控制 TGRS 码的 Hermitian 核维数。
  3. 主要结论：对于 \(n \mid q^2-1\) 的情形，本文给出了 \(L_q(n,k)\) 的一个统一下界（定理 III.1），该下界改进了已有结果。特别地，当 \(n \geq q+1\) 且 \(k \geq q+1\) 时，证明 \(L_q(n,k) \geq k/2\)，并显式构造了达到该下界的 MDS 码（定理 III.2 和 III.3）。此外，还给出了 TGRS 码 Hermitian 自正交的充分条件（定理 IV.1），并构造了非 GRS 的 Hermitian 自正交 MDS 码（定理 IV.2）。

关键设定与假设

  • 设定：\(\mathbb{F}_{q^2}\) 是有限域，\(q>2\) 是素数幂。\(n\) 是码长，\(k\) 是维数，\(1 \leq k \leq n\)。码是 \(\mathbb{F}_{q^2}\) 上的线性码。
  • 假设：
    • MDS 假设：码 \(C\) 是 MDS 的，即其最小距离 \(d = n-k+1\)。这是本文研究对象的定义性假设。
    • \(n \mid q^2-1\) 假设：在主要结果（定理 III.1, III.2, III.3）中，假设 \(n\) 整除 \(q^2-1\)。这个假设保证了存在一个 \(n\) 阶乘法子群 \(\mathcal{A} \subseteq \mathbb{F}_{q^2}^*\)，这是构造 GRS 和 TGRS 码的常用技巧。作者在引言中承认，去掉这个假设是未来的工作。
    • TGRS 码的特定形式：本文考虑的 TGRS 码具有特定的扭曲形式（定义 II.3），其生成矩阵由求值点 \(\mathcal{A}\)、乘子 \(\mathbf{v}\) 和一个扭曲多项式 \(h(x)\) 定义。这个形式是 GRS 码的自然推广，但并非最一般的 TGRS 码。
  • 相比已有文献的放宽或强化：
    • 放宽：本文的主要结果（\(L_q(n,k) \geq k/2\)）适用于 \(k \geq q+1\)，这比之前基于 GRS 码的结果（仅适用于 \(k \leq q\)）的参数范围更广。
    • 强化：本文给出的 \(L_q(n,k)\) 下界（定理 III.1）在 \(k \geq q+1\) 时比之前已知的下界更强。

主要结果

  • 定理 III.1（\(L_q(n,k)\) 的下界）：设 \(n \mid q^2-1\)，\(1 \leq k \leq n\)。则

    \[L_q(n,k) \geq \max_{0 \leq t \leq \min(k, n-k)} \left\{ \min\left(k - t, n - k - t, \left\lfloor \frac{n}{2} \right\rfloor - t \right) \right\}.\]

    • 直觉：这个下界是通过构造一族 TGRS 码得到的，这些码的 Hermitian 核维数可以通过参数 \(t\) 来调节。\(t\) 可以理解为“扭曲”的强度。通过优化 \(t\)，可以得到一个关于 \(n\) 和 \(k\) 的表达式。
    • 必要条件：\(n \mid q^2-1\)。
    • 解决的技术难点：需要分析 TGRS 码的 Hermitian 对偶的结构，并计算其与原始码的交集维数。这比 GRS 码的情形复杂得多，因为 TGRS 码的 Hermitian 对偶不再是简单的 GRS 码。

  • 定理 III.2（\(k \geq q+1\) 时的下界）：设 \(n \mid q^2-1\)，\(n \geq q+1\)，\(k \geq q+1\)。则 \(L_q(n,k) \geq k/2\)。

    • 直觉：这是定理 III.1 的一个推论。通过取 \(t = \lfloor k/2 \rfloor\)，可以验证定理 III.1 中的下界至少为 \(k/2\)。
    • 必要条件：\(n \mid q^2-1\)，\(n \geq q+1\)，\(k \geq q+1\)。
    • 解决的技术难点：需要证明存在一个 \(t\) 使得下界达到 \(k/2\)，并且这个 \(t\) 在允许的范围内（\(0 \leq t \leq \min(k, n-k)\)）。

  • 定理 III.3（显式构造）：在定理 III.2 的条件下，存在显式的 \([n,k]_{q^2}\) MDS 码，其 Hermitian 核维数至少为 \(k/2\)。这些码可以是 GRS 码或非 GRS 的 TGRS 码。

    • 直觉：这个定理表明，定理 III.2 的下界是可以达到的，并且给出了具体的构造方法。
    • 必要条件：同定理 III.2。
    • 解决的技术难点：需要根据 \(k\) 的奇偶性和 \(n\) 的具体值，设计不同的求值点、乘子和扭曲参数，以确保构造出的码是 MDS 的且 Hermitian 核维数满足要求。

  • 定理 IV.1（TGRS 码 Hermitian 自正交的充分条件）：给出了 TGRS 码 \(C\) 满足 \(C \subseteq C^{\perp_h}\)（即 Hermitian 自正交）的充分条件。

    • 直觉：这个条件涉及扭曲多项式 \(h(x)\)、求值点 \(\mathcal{A}\) 和乘子 \(\mathbf{v}\) 之间的代数关系。
    • 必要条件：无额外假设，但条件本身是代数性的。

  • 定理 IV.2（非 GRS 的 Hermitian 自正交 MDS 码）：利用定理 IV.1 的条件，构造了非 GRS 的 Hermitian 自正交 MDS 码。

    • 直觉：这表明 TGRS 码可以构造出 GRS 码无法实现的 Hermitian 自正交 MDS 码，从而扩展了可用的码类。

证明路线与技术技巧

  • 整体路线：

    1. 定义 TGRS 码：给出 TGRS 码的生成矩阵形式（定义 II.3）。
    2. 计算 Hermitian 对偶：推导 TGRS 码的 Hermitian 对偶码的结构（引理 II.5）。这是关键步骤，因为 TGRS 码的 Hermitian 对偶不再是简单的 TGRS 码，而是一个更复杂的码。
    3. 刻画 Hermitian 核：将 \(Hull_h(C) = C \cap C^{\perp_h}\) 转化为一个线性方程组问题。通过分析生成矩阵和其对偶生成矩阵的行空间，将 Hermitian 核的维数与某个矩阵的秩联系起来。
    4. 构造特定 TGRS 码：选择特定的求值点集 \(\mathcal{A}\)（\(\mathbb{F}_{q^2}^*\) 的 \(n\) 阶子群）、乘子 \(\mathbf{v}\) 和扭曲多项式 \(h(x)\)，使得步骤 3 中的矩阵具有特定的秩，从而得到 Hermitian 核维数的下界。
    5. 优化参数：通过调整扭曲参数 \(t\)，最大化 Hermitian 核维数的下界，得到定理 III.1。
    6. 特殊情况分析：针对 \(k \geq q+1\) 的情形，证明存在 \(t\) 使得下界至少为 \(k/2\)，并给出显式构造（定理 III.2 和 III.3）。
    7. 自正交条件：类似地，通过分析 Hermitian 对偶的包含关系，推导出 TGRS 码 Hermitian 自正交的充分条件（定理 IV.1），并构造例子（定理 IV.2）。

  • 关键跳跃点：

    • 引理 II.5 的证明：计算 TGRS 码的 Hermitian 对偶。这是整个证明的基石。难点在于 TGRS 码的生成矩阵不是 Vandermonde 矩阵的简单推广，其 Hermitian 对偶的生成矩阵需要通过对扭曲多项式进行某种“对偶”变换得到。作者通过引入一个辅助多项式 \(g(x)\) 并利用有限域上的线性代数技巧解决了这个问题。
    • 定理 III.1 的证明：将 Hermitian 核维数问题转化为一个关于多项式次数的组合优化问题。难点在于需要同时考虑原始码和对偶码的多项式空间，并找到它们的交集。作者通过将问题分解为几个子情形，并分别构造 TGRS 码来处理每个子情形，最终得到了一个统一的下界。

  • 技术技巧点名：

    • 有限域上的线性代数：贯穿全文，用于计算生成矩阵的秩、解线性方程组等。
    • Vandermonde 矩阵及其推广：GRS 码和 TGRS 码的生成矩阵都是 Vandermonde 矩阵的变体，其可逆性（从而 MDS 性质）依赖于求值点的互异性。
    • Frobenius 自同构：Hermitian 内积的定义依赖于 \(q\) 次幂映射，因此 Frobenius 自同构在分析 Hermitian 对偶时扮演了核心角色。
    • 多项式环的理想理论：在分析 TGRS 码的 Hermitian 对偶时，作者使用了多项式环 \(\mathbb{F}_{q^2}[x]\) 中的理想和商环的概念。

真实例子与应用

本文为纯理论，无实证例子。所有结果都是代数构造和定理证明。作者在结论部分提到，基于他们的构造，可以得到多族 MDS 纠缠辅助量子纠错码（EAQECC），但并未给出具体的数值例子或与现有 EAQECC 的参数对比。因此，本文的应用价值是理论上的：它为构造具有特定纠缠资源需求的 EAQECC 提供了新的码类。

🔎 结论是否比证明窄

  • 定理 III.1 和 III.2 的结论是严格证明的，没有过度 claim。作者明确指出了假设条件（\(n \mid q^2-1\)）。
  • 定理 III.3 声称“显式构造了 \([n,k]_{q^2}\) MDS 码，其 Hermitian 核维数至少为 \(k/2\)”。这个结论是证明的，但构造依赖于 \(n\) 和 \(k\) 的具体值，且分为 GRS 和非 GRS 两种情况。作者在证明中给出了每种情况下的具体参数选择，因此是严格的。
  • 定理 IV.1 和 IV.2 也是严格证明的。
  • 潜在比证明窄的地方：作者在引言中称他们的结果“部分解决了” Fang et al. (2020) 提出的开放问题。这个表述是准确的，因为他们只解决了 \(n \mid q^2-1\) 的情形，且只给出了下界 \(k/2\)，而非精确值。作者在结论中也明确指出了这一点，并提到去掉 \(n \mid q^2-1\) 的假设是未来工作。

四、开放问题

  1. 去掉 \(n \mid q^2-1\) 的假设：本文的主要结果都依赖于这个假设。对于一般的 \(n\)，\(L_q(n,k)\) 的下界是什么？能否用类似 TGRS 码的构造得到？扎根点：结论部分“It would be interesting to remove the condition \(n \mid q^2-1\) in our constructions.”
  2. 确定 \(L_q(n,k)\) 的精确值：本文给出了下界，但上界是什么？能否证明 \(L_q(n,k) \leq k/2\) 或更紧的上界？扎根点：引言部分“determining the exact value of \(L_q(n,k)\) is a challenging open problem.”
  3. 构造达到更大 Hermitian 核维数的 MDS 码：本文证明 \(L_q(n,k) \geq k/2\)，但能否构造出 Hermitian 核维数大于 \(k/2\) 的 MDS 码？例如，能否达到 \(k-1\) 或 \(n-k\)？扎根点：定理 III.2 的结论本身就是一个开放问题的答案，但“至少 \(k/2\)”可能不是紧的。
  4. 将 TGRS 码的构造推广到其他内积：本文研究的是 Hermitian 内积。类似的问题对于 Euclidean 内积或 Galois 内积是否成立？能否用类似的技术构造具有大 Euclidean 核或 Galois 核的 MDS 码？扎根点：引言部分提到了 Euclidean 核和 Hermitian 核，但本文只研究了后者。这是一个自然的推广方向。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论