On the Maximal Length of MDS Elliptic Codes

技术摘要：关于 MDS 椭圆码的最大长度

问题陈述
本文探讨了定义在有限域 $\mathbb{F}_q$ 上、维数为 $k$ 的非平凡最大距离可分（MDS）椭圆码的最大长度，记为 $MEC(k, q)$。虽然关于 MDS 码的主要猜想为一般线性码提出了特定的界限，但由椭圆曲线导出的码具有独特的约束。先前的工作已确立：当 $q \ge 289$ 且 $3 \le k \le (q + 1 - 2\sqrt{q})/10$ 时，界限 $MEC(k, q) \le \frac{q+1}{2} + \sqrt{q}$ 成立；且当 $q$ 为奇平方数且 $k$ 为奇数时，该界限取等号。然而，仍有三个关键缺口未解决：

1. 当 $q$ 为奇平方数时，界限 $\frac{q+1}{2} + \sqrt{q}$ 是否对偶数 $k$ 可达。
2. 当 $q$ 不是完全平方数时，$MEC(k, q)$ 的确切值。
3. 当域特征为 2 时（此时标准界限为非整数）的确切最大长度。

方法论
作者结合了代数几何与组合群论。核心方法论依赖于 Li 等人 [13] 建立的准则：椭圆码 $C(E, D, G)$ 不是 MDS 码，当且仅当除子 $G$ 的和（记为 $\text{sum}(G)$）落在有理点群 $E(\mathbb{F}_q)$ 中评估集 $D$ 的 $k$-和集（记为 $\Sigma_k(D)$）内。

分析通过根据 $q + 1 + \lfloor 2\sqrt{q} \rfloor$ 的奇偶性对问题进行划分展开：

• 组合约束：作者利用关于有限阿贝尔群中和集的引理（特别是 [14] 中的引理 8 和引理 9），证明如果评估集 $D$ 足够大且未包含在特定的陪集结构中，则 $k$-和集将覆盖整个群，从而违反 MDS 条件。
• 除子支撑分析：关键区别在于除子 $G$ 的支撑完全由 $\mathbb{F}_q$-有理点组成（记为 $MEC^*(k, q)$）的情况，与 $G$ 可能包含度数 $>1$ 的位的一般情况。
• 通过高次位构造：为了在仅使用有理点支撑无法达到上界的情况下实现上界，作者构造了显式的除子 $G$，其中包含一个满足 $\text{sum}([R]) = \mathcal{O}$（单位元）的 3 次位 $R$。此类位的存在性利用 Frobenius 自同态的性质及 $E(\mathbb{F}_{q^3})$ 的结构得以证明。

主要贡献与结果

1. 偶数维情况的解决（奇平方数 $q$）：

   • 限制于有理点：本文证明，如果 $G$ 的支撑被限制在 $\mathbb{F}_q$-有理点上，则界限 $\frac{q+1}{2} + \sqrt{q}$ 对偶数 $k$ 不可达。相反，最大长度严格为 $\frac{q+1}{2} + \sqrt{q} - 1$（定理 15，推论 16）。
   • 一般情况：通过在 $G$ 的支撑中构造包含一个 3 次位的码，作者证明了当 $q$ 为奇平方数时，界限 $\frac{q+1}{2} + \sqrt{q}$ 对偶数 $k$ 是可达的（定理 18，定理 23，定理 24）。这解决了第一个开放问题。

2. 非平方数 $q$ 与一般奇偶性：

   • 作者根据 $q + 1 + \lfloor 2\sqrt{q} \rfloor$ 的奇偶性，确立了 $MEC(k, q)$ 的统一公式。
   • 如果 $q + 1 + \lfloor 2\sqrt{q} \rfloor$ 为偶数，则 $MEC(k, q) = \frac{q + 1 + \lfloor 2\sqrt{q} \rfloor}{2}$。
   • 如果 $q + 1 + \lfloor 2\sqrt{q} \rfloor$ 为奇数，则 $MEC(k, q) = \frac{q + \lfloor 2\sqrt{q} \rfloor}{2}$。
   • 在这两种情况下，如果 $G$ 的支撑被限制在有理点上，则对于偶数 $k$，最大长度减少 1（定理 15，定理 29）。

3. 特征 2 域：

   • 本文提供了特征 2 域（$q = 2^a$）的完整解决方案。
   • 当 $q + 1 + \lfloor 2\sqrt{q} \rfloor$ 为奇数时（这发生在 $q$ 为指数 $a$ 为偶数的平方数时），最大长度为 $\frac{q + \lfloor 2\sqrt{q} \rfloor}{2} = 2^{a-1} + \sqrt{2^a}$（推论 32）。
   • 提供了二元域上的显式构造，包括有理点群为循环群的示例（推论 35，示例 36）。

意义
本文声称在指定参数范围（$q \ge 289$，$3 \le k \le (q + 1 - 2\sqrt{q})/10$）内，对 MDS 椭圆码最大长度的紧性问题提供了“完整解决”。其主要意义在于：

• 完善分类：确定了所有相关 $k$ 和 $q$ 奇偶性下 $MEC(k, q)$ 的确切值，包括先前未解决的偶数维和非平方域情况。
• 细化界限：证明了理论上限的可达性关键取决于除子 $G$ 的支撑。具体而言，它证明了将 $G$ 限制在有理点上会对偶数维的最大长度施加严格减 1 的惩罚，而这一限制只能通过利用高次位来克服。
• 实际相关性：结果对特征 2 域尤为相关，这些域广泛应用于密码学和通信系统，为这些领域的码构造提供了精确参数。

作者总结道，他们的工作提供了一个统一的框架，用于确定所有相关奇偶组合下的 $MEC(k, q)$，这依赖于最大椭圆曲线和特定 3 次位的存在性。