Average-Radius List-Decodability of Random Linear Codes

技術要約：ランダム線形符号の平均半径リスト復号可能性

問題提起
本研究は、有限体 $\mathbb{F}_q$ 上のランダム線形符号における、リスト復号容量に迫るレートでの組合せ論的なリスト復号可能性（combinatorial list-decodability）を扱う。具体的には、標準的なリスト復号よりも強力なバリアントである**平均半径リスト復号可能性（average-radius list-decodability）**について調査している。

標準的な $(p, L)$-リスト復号可能性が、「半径 $pn$のハミング球内に含まれる符号語の数が$L$個を超えないこと」を要求するのに対し、**平均半径**$(p, L)$-リスト復道可能性は、「任意の中心$y \in \mathbb{F}_q^n$に対して、それに最も近い$L+1$個の符号語の平均的な分数ハミング距離が、厳密に$p$ よりも大きいこと」を要求する。平均距離は常に最大距離によって抑えられるため、これはより強力な条件である。

本研究以前には、以下のことが既知であった：

1. 一般的なランダム符号は、リストサイズ $O(1/\epsilon)$ で平均半径リスト復号可能性を達成する（Elias, 1991）。
2. ランダムなバイナリ線形符号は、これを $O(1/\epsilon)$ で達成する（Guruswami et al., 2021）。
3. 非バイナリのランダム線形符号については、平均半径設定に標準的なリスト復号の結果を適用することで、既知の最良の境界は $O(1/\epsilon^2)$ であった（Rudra and Wootters, 2018より導出）。

ここでの中心的な未解決問題は、一般的なアルファベット $\mathbb{F}_q$ 上のランダム線形符号が、一般のランダム符号やバイナリ線形符号の性能と一致する、平均半径リスト復号のための最適な $O(1/\epsilon)$ のリストサイズを達成できるか否かであった。

手法および証明のアプローチ
著者らは、非バイナリ・ランダム線形符号の標準的なリスト復号に対して $O(1/\epsilon)$ のリスト復号可能性を確立した Guruswami, Håstad, and Kopparty (GHK, 2010) の証明戦略を適応させている。しかし、GHK の議論は、ハミング球の幾何学的構造と、検討されるすべての符号語が固定された半径内に厳密に存在するという事実に強く依存している。この幾何学的な「増加するサポート（increasing-supports）」の議論は、個々のベクトルが球内に存在する必要はなく、単に平均的に近いことが求められる平均半径の設定では成立しない。

これを克服するために、本論文では GHK の証明における幾何学的なステップに代わる、2つの新しい技術的要素を導入している：

1. イェンセン/エントロピー計数境界 (Lemma 6): 球内のベクトルの数を数える代わりに、著者らは小さな線形独立集合の「総重量欠損（total weight deficit）」を制御する。$q$ 元エントロピー関数 $h_q$ に対するイェンセンの不等式を利用することで、サイズ $L = \Theta(1/\epsilon)$ の線形独立集合が大きな総欠損（すなわち、集合内のベクトル $v$ に対する $pn - |v|$ の総和が大きくなりすぎること）を持つことはできないことを示す。
2. 貪欲基底（Greedy-Basis）議論: 著者らは、最も近い符号語（または符号と中心の生成空間内の要素）を、重みの昇順で並べる。そして、そこから極大な線形独立部分列を貪欲に抽出する。スパン・ボール定理（Span-Ball Theorem）（GHK から適応させた Lemma 5）を用いて、この貪欲な基底が、順序付けられたリスト全体を通じて頻繁に出現することを証明する。具体的には、$r$ 個の基底ベクトルのスパンに含まれるベクトルは、高々 $O(r)$ 個である。この規則性により、独立な基底ベクトルから得られた欠損の境界を、最も近い符号語全体の集合へと転送し、それらの平均距離を抑えることが可能となる。

主要な結果
主要な定理（Theorem 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)$ のリストサイズと一致しており、非バイナリ線形符号におけるギャップを解消した。

証明は以下の2つの補題に基づいている：

• Lemma 5 (Span-Ball Bound): 高い確率で、ハミング球内にある小さな線形独立集合のスパンと、その球との交わりは、高々 $O(|S|)$ 個のベクトルである。
• Lemma 6 (Deficit Bound): 高い確率で、符号（および中心）の生成空間内にある小さな線形独立集合の総重量欠損は、$\epsilon n$ を超えない。

意義および主張
本論文は、GHK (2010) の結果（一般のランダム線形符号に対する標準的なリスト復号）を、より強力な平均半径の保証へと拡張し、かつ最適な $O(1/\epsilon)$ のリストサイズを維持できることを主張している。

• 統一: 本研究は、異なるアルファベットサイズおよび異なる復号バリアント（標準 vs 平均半径）にわたる、ランダム線形符号のリスト復号可能性に関する理解を統一する。
• 幾何学的障害の克服: 本研究は、標準的なリスト復号のための GHK 証明に内在する幾何学的制約が、平均半径の場合には必ずしも必要ではなく、代わりにエントロピーに基づく計数と貪欲な基底抽出で十分であることを示している。
• 限界: 著者らは、リストサイズは $O(1/\epsilon)$ であるものの、定数 $C_{p,q}$ は $p \to 1 - 1/q$ （高ノイズ領域）において劣化することを指摘している。また、$p$ や $q$ に依存しない絶対的な定数 $C$ が達成可能かという問い（バイナリの場合は既知であるが、一般的な $q$ については未解決）を今後の課題として残している。

本論文は、新しい応用や実験的な実装を提案するものではなく、純粋にランダム線形符号の組合せ論的な性質に焦点を当てており、その結果を確率論的組合せ論および符号理論における基礎的な進展として位置づけている。