Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions

技术摘要：超越多项式：基于优良有理函数的最优局部可恢复码

问题陈述
局部可恢复码（LRCs）对于分布式和云存储系统至关重要，在这些系统中，通过访问少量其他坐标（局部性 $r$）来恢复单个擦除坐标的能力是关键。$(n, k, r)$-LRC 参数的基本限制是 Singleton 型界：$d \le n - k - \lceil k/r \rceil + 2$。满足该界的码被称为“最优”码。

Tamo 和 Barg 引入的最优 LRC 主导构造范式依赖于“优良多项式”。多项式 $f \in \mathbb{F}_q[X]$ 被称为 $(r, l)$-优良多项式，如果它的次数为 $r+1$，并且在 $l$ 个大小为 $r+1$ 的不相交子集上取常数值。此类子集的数量 $l$ 决定了码长 $n = (r+1)l$。然而，构造具有大 $l$ 值的优良多项式受到有限域算术性质以及多项式相关伽罗瓦群（具体为算术单值群）结构的限制。对于次数为 $r+1$ 的多项式，伽罗瓦群通常很大（接近对称群 $S_{r+1}$），这限制了完全分裂有理位的数量，从而限制了可达到的码长。

方法论
本文提出通过用优良有理函数替换优良多项式，对 Tamo-Barg 框架进行推广。该方法论整合理代数函数域理论和伽罗瓦理论，以分析和构造这些函数。

1. 优良有理函数的定义：作者定义有理函数 $h(x) \in \mathbb{F}_q(x)$ 为 $(r, l)$-优良函数，如果它的次数为 $r+1$，并且在射影直线 $\mathbb{P}^1(\mathbb{F}_q)$ 的 $l$ 个大小为 $r+1$ 的不相交子集上取常数值。
2. 函数域嵌入：最大化 $l$ 的问题被嵌入到代数函数域理论中。具体而言，$l$ 对应于扩张 $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$ 中完全分裂有理位的数量，记为 $\#T^1_{split}(h)$。
3. 伽罗瓦理论分析：作者通过考虑扩张的伽罗瓦闭包 $M_h$ 来分析位的分裂行为。他们利用 Zeta 函数和 Artin L-级数导出了 $\#T^1_{split}(h)$ 的公式，表明：
   $$\#T^1_{split}(h) \approx \frac{q}{\#G_h}$$
   其中 $G_h$ 是该扩张的伽罗瓦群。
4. 优化策略：与伽罗瓦群通常很大的多项式不同，作者专注于构造这样的有理函数，使得扩张 $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$ 本身是一个伽罗瓦扩张，且具有最小的伽罗瓦群大小（$\#G_h = r+1$）。这是通过利用有理函数域自同构群 $\text{PGL}(2, q)$ 的子群来实现的。
5. 显式构造：本文利用 $\text{PGL}(2, q)$ 的循环子群构造了优良有理函数的显式族。对于阶为 $r+1$ 的变换 $\phi \in \text{PGL}(2, q)$，函数 $h(x) = \sum_{i=0}^r \phi^i(x)$ 被证明能生成具有所需性质的伽罗瓦扩张。

主要贡献与结果

• 统一框架：本文建立了一个基于优良有理函数构造最优 LRC 的统一框架，扩展了 Tamo-Barg 范式。
• 定量界：利用 Hasse-Weil 界和 Riemann-Hurwitz 公式，作者导出了完全分裂有理位数量的显式下界。他们证明，对于次数为 $r+1$ 的优良有理函数 $h$，参数 $l$ 满足：
  $$l \ge \frac{q - 2\sqrt{q} + 1}{(r+1)!} - \text{修正项}$$
  然而，在伽罗瓦扩张的特定情况下，该界要紧密得多。
• 伽罗瓦情形刻画：当扩张为伽罗瓦扩张时，作者基于伽罗瓦群在 $\mathbb{P}^1(\mathbb{F}_q)$ 上的作用轨道结构，给出了 $\#T^1_{split}(h)$ 的精确刻画。他们表明，完全分裂位的数量约为 $q/(r+1)$，这比群大小为 $(r+1)!$ 的典型多项式情形大了 $(r)!$ 倍。
• 显式构造：
  • 次数 3 ($r=2$)：本文构造了一个有理函数 $h(x) = \frac{x^3 - 3w^2x + w^3}{x(x-w)}$。根据 $q \pmod 3$ 的不同，这生成了长度为 $q$、$q-1$ 或 $q+1$ 的 LRC。具体而言，如果 $q \equiv 2 \pmod 3$，码长为 $q+1$。
  • 次数 4 ($r=3$)：构造了一个有理函数 $h(x) = \frac{4x^4 - 12d^2x^2 + 8d^3x - d^4}{2x(x-d)(2x-d)}$。如果 $q \equiv 3 \pmod 4$，所得码的长度为 $q+1$。
• 最优性：构造的码是最优的，满足 Singleton 型界。关键在于，对于特定的局部性参数（$r=2, 3$）和域特征，这些构造实现了最大可能的码长 $n = q+1$（在整个射影直线上求值），这严格大于相同次数的优良多项式通常能达到的长度。

意义与主张
本文主张，优良有理函数的引入代表了相对于经典多项式方法的根本性进步。其主要意义在于能够直接控制伽罗瓦群的大小。虽然优良多项式受到大单值群（通常为 $S_{r+1}$）的限制，但通过 $\text{PGL}(2, q)$ 子群构造的有理函数可以实现最小的传递群大小（$r+1$）。

群大小的这种减小导致完全分裂有理位数量显著增加，从而使得在相同局部性 $r$ 下能够构造长度显著更长（$n \approx q$）的 LRC。作者强调，他们的方法提供了无限族的最优 LRC，其参数在相同次数下严格优于 Tamo-Barg 构造产生的参数。该方法被呈现为一种“自然且强大的扩展”，它利用射影直线和有理函数更丰富的代数和几何框架，克服了多项式构造固有的局限性。