Average-Radius List-Decodability of Random Linear Codes

技术摘要：随机线性码的平均半径列表可译性

问题陈述
本研究探讨了在接近列表译容量的速率下，有限域 $\mathbb{F}_q$ 上随机线性码的组合列表可译性。具体而言，它研究了平均半径列表可译性（average-radius list-decodability）这一性质，这是标准列表可译性的一种更强的变体。

虽然标准的 $(p, L)$-列表可译性要求任何半径为 $pn$的汉明球内包含的码字不超过$L$个，但**平均半径**$(p, L)$-列表可译性则要求：对于任何中心$y \in \mathbb{F}_q^n$，距离$y$最近的$L+1$个码字的*平均*分式汉明距离必须严格大于$p$。由于平均距离总是受限于最大距离，因此这是一个更强的条件。

在此项工作之前，已知以下结论：

1. 通用随机码可以实现列表大小为 $O(1/\epsilon)$ 的平均半径列表可译性（Elias, 1991）。
2. 随机二元线性码也可以实现此特性，且列表大小为 $O(1/\epsilon)$（Guruswami 等人, 2021）。
3. 对于非二元随机线性码，已知的平均半径列表可译性的最佳界限是 $O(1/\epsilon^2)$（通过将 Rudra 和 Wootters (2018) 的标准列表译结果应用于平均半径设置而得出）。

核心开放性问题在于：对于一般字母表 $\mathbb{F}_q$ 的随机线性码，是否能实现与通用随机码和二元线性码性能相匹配的 $O(1/\epsilon)$ 最优列表大小。

方法论与证明方法
作者借鉴了 Guruswami, Håstad, 和 Kopparty (GHK, 2010) 的证明策略，该策略确立了非二元随机线性码在标准列表译下的 $O(1/\epsilon)$ 可译性。然而，GHK 的论证高度依赖于汉明球的几何结构，以及所有被考虑的码字都严格位于一个固定半径之内的这一事实。这种几何上的“递增支撑集”（increasing-supports）论证在平均半径设置中失效了，因为在平均半径设置中，码字只需要在平均意义上接近中心，而不必个别都落在球内。

为了克服这一点，本文引入了两个新的技术要素来取代 GHK 证明中的几何步骤：

1. Jensen/熵计数界限（引理 6）： 作者不再仅仅限制球内的向量数量，而是控制一个小型线性无关集合的“总权重亏损”（total weight deficit）。他们利用 $q$ 元熵函数 $h_q$ 上的 Jensen 不等式来证明：一个大小为 $L = \Theta(1/\epsilon)$ 的线性无关集合不可能拥有过大的总亏损（即集合中向量 $v$ 的 $(pn - |v|)$ 之和不能太大）。
2. 贪婪基（Greedy-Basis）论证： 作者按权重递增的顺序对最近的码字（或码的张成空间与中心的元素）进行排序。他们贪婪地提取一个极大线性无关子序列。利用张成空间-球定理（Span-Ball Theorem，引理 5，改编自 GHK），他们证明了这个贪婪基必须在有序列表中频繁出现。具体而言，$r$ 个基向量的张成空间内包含在球内的向量最多为 $O(r)$ 个。这种正则性使得作者能够将从独立基向量推导出的亏损界限转移到整个最近码字集合上，从而限制它们的平均距离。

主要结果
主定理（定理 1）确立了以下内容：

• 定理： 对于每个素数幂 $q$ 和每个 $p \in (0, 1-1/q)$，一个速率为 $R = 1 - h_q(p) - \epsilon$ 的随机 $\mathbb{F}_q$-线性码以至少 $1 - q^{-\Omega(n)}$ 的概率是 $(p, C_{p,q}/\epsilon)$-平均半径列表可译的。
• 这里，$C_{p,q}$ 是仅取决于 $p$ 和 $q$ 的常数。
• 该结果匹配了通用随机码和二元线性码所实现的 $O(1/\epsilon)$ 列表大小，解决了非二元线性码的差距问题。

证明依赖于两个引理：

• 引理 5（张成空间-球界限）： 以高概率，位于汉明球内的任何小型线性无关集合的张成空间与该球的交集仅包含 $O(|S|)$ 个向量。
• 引理 6（亏损界限）： 以高概率，码的张成空间（加中心）中的任何小型线性无关集合的 total weight deficit 不会超过 $\epsilon n$。

意义与主张
本文声称将 GHK (2010) 关于通用随机线性码标准列表译的结论，扩展到了更强的平均半径保证，并保持了相同的最优列表大小 $O(1/\epsilon)$。

• 统一性： 它统一了不同字母表大小和不同译码变体（标准 vs. 平均半径）下随机线性码的列表可译性理解。
• 克服几何障碍： 这项工作表明，GHK 在标准列表译中用于处理几何约束的几何限制对于平均半径情况并非必要；相反，基于熵的计数和贪婪基提取足以解决问题。
• 局限性： 作者指出，虽然列表大小为 $O(1/\epsilon)$，但常数 $C_{p,q}$ 会随着 $p \to 1 - 1/q$（高噪声状态）而退化。他们提出了一个开放性问题：是否可以实现一个与 $p$ 和 $q$ 无关的绝对常数 $C$（这在二元情况下是已知的，但在一般 $q$ 下仍是一个开放问题）。

本文并未提出新的应用或实验实现，而是专注于随机线性码的组合属性，将该结果定位为概率组合学和编码理论领域的一项基础性进展。