技術的概要：ランダムな低レート線形符号におけるリスト回復

問題定義

本論文は、十分に大きな素数体 $\mathbb{F}_p$ 上のランダムな線形符号のリスト回復特性を調査する。具体的には、符号の次元 $d$ が固定されたままブロック長 $n$ が無限大に発散する（本質的にゼロレートである）領域における研究である。

中心となる問題は、$(\alpha, \ell, L)$-リスト回復可能性を通じて定義される。符号 $C \subseteq \Sigma^n$ が $(\alpha, \ell, L)$-リスト回復可能であるとは、任意の入力リスト $S_1, \dots, S_n \subseteq \Sigma$（各々のサイズが $\ell$）に対して、$x_i \notin S_i$ となる座標の数が $\alpha n$ 以下となる符号語 $x \in C$ が、高々 $L$ 個しか存在しないことを意味する。

本論文は、入力リストのサイズ $\ell$ が $n$ とともに増加する際の、ランダムな $d$ 次元線形符号 $C \subseteq \mathbb{F}_p^n$ の挙動を取り扱う。目的は、出力リストのサイズ $L$ が小さく（具体的には情報理論的下界 $\frac{1+\epsilon}{1-\alpha \ell}$ に近い）保たれるような、最大限の $\ell$ を決定することである。

手法

証明戦略は、点集合の射影からの再構成に関する Matoušek、Pˇr´ıvˇetiv´y、Škovroˇn の研究に着想を得て、組合せ論的グラフ理論と代数幾何学を架橋するものである。手法は以下の 4 つの主要な段階を経て進行する。

1. グラフ理論的帰着:
   著者らは、リスト回復の失敗を、辺彩色多重グラフ上の問題へと翻訳する。もしある符号がリスト回復可能でなければ、その符号語の大部分の座標で指定されたリスト内に収まるメッセージの集合 $A$ が存在する。この構造は、多くの座標において、$A$ 内の点の対が同じ値に写像される（座標線形形式の同じファイバー内にある）ことを意味する。これらの対はマッチングを形成し、座標は辺の色として機能する。したがって、リスト回復の失敗は、多くの色クラスが大きなマッチングとなるようなグラフを生み出す。

2. 決定論的グラフ証明書:
   最大密度誘導部分グラフの議論を用いて、著者らは、多くの色クラスが大きなマッチングであるようなグラフが存在する場合、互いに素な色集合を持つ $d$ 個の全域木を支える頂点の部分集合を見出すことができることを証明する。これは、適切な拡張仮定の下で、色のランダムな部分集合がグラフを連結させることを示す確率的議論（補題 5 および補題 6）によって確立される。

3. 代数的証明書（非零行列式）:
   上記の $d$ 個の互いに素な全域木は、代数的系へと変換される。これらの木の辺は、$A$ 内の点間の差に関する線形方程式を課す。木が互いに素な色集合を持つため、結果として得られる系行列の行列式は、符号を定義する線形形式の係数に関する非零多項式となる。Schwartz–Zippel の補題により、線形形式（符号の生成行列の成分）が十分に大きな体から一様にランダムに選択される場合、この行列式が零となる確率は無視できるほど小さい。行列式が非零であれば、その系は証明書内のすべての点を一致させることを強制し、$A$ が異なるメッセージを含むという仮定と矛盾する。

4. 下限の構成:
   最適性を示すために、著者らは、リストサイズ $\ell$ が $n$ の指数関数（$\ell \ge 2^{\Omega(n)}$）である場合、次元が 2 以上である任意の線形符号に対する反例を構成する。彼らは 2 次元の部分符号を利用し、「一般化された算術ボックス」（基底ベクトルの有界係数による線形結合で形成された符号語の集合）を構築する。この集合は、すべての座標への射影が小さく（サイズ $\le \ell$）、かつ集合自体が許容される符号語の数を超えているように設計されている。

主要な貢献と結果

主要定理（上限）

本論文は、固定された次元 $d$、誤り率 $\alpha$、精度 $\epsilon$ に対して、十分に大きな素数体上のランダムな $d$ 次元線形符号が、高い確率で $(\alpha, \ell, \frac{1+\epsilon}{1-\alpha \ell})$-リスト回復可能であることを証明する。

• 範囲: これは、ある定数 $\delta > 0$ に対して、すべての入力リストサイズ $\ell \le 2^{\delta n / \log n}$ に対して同時に成り立つ。
• 最適性: リストサイズの上限における $n$ への依存性は、ほぼ最適である。著者らは、次元が 2 以上である任意の線形符号に対して、リストサイズ $\ell \ge 2^{\Omega(n)}$ ではリスト回復が失敗することを示している。

下限

本論文は、実行可能なリストサイズ $\ell \ge 2^{\delta n}$ に対して、次元が 2 以上であるいかなる線形符号も $(\alpha, \ell, \frac{1+\epsilon}{1-\alpha \ell})$-リスト回復可能ではないことを確立する。これは、ランダムな場合に達成可能なリストサイズ（$2^{n/\log n}$）と、一般的な符号における失敗の閾値（$2^n$）との間の指数関数的なギャップが、この領域における線形構造の根本的な限界であることを示している。

意義と主張

著者らは、この研究を、次元が固定されブロック長が増大する「相補的かつ本質的にゼロレートのランダム線形符号領域」の研究として位置づけている。

• ほぼ最適性: 達成可能なリストサイズ $\ell \approx 2^{n/\log n}$ が、次元が 2 以上である任意の線形符号に対してリスト回復が不可能となる理論的限界に近いことから、この結果は「ほぼ最適」であると主張されている。
• 手法の新規性: 証明は、決定論的グラフ理論的証明書（大きなマッチングから互いに素な全域木を見つけること）と、非零行列式基準の新奇な組み合わせを導入している。このアプローチは、点集合の再構成からの手法を符号理論へと適応させたものである。
• AI 支援証明: 著者らは明示的に、初期の結果は人間の推論によって導き出されたが、最終的かつ量的・質的に優れた証明は、AI ハンネス（GPT-5.5Pro を使用した UCLA Moonshot AI for Math）によって生成されたと述べている。彼らは、人間の指導なしに AI に直接問い合わせても定理が導き出されなかったと述べており、人間が直感的に問題を枠組み付け、AI が複雑な証明の合成を実行するという特定のワークフローを浮き彫りにしている。

本論文は、新しい応用や実験的提案を提示するものではなく、ランダムな低レート線形符号におけるリスト回復の理論的限界の確立に厳密に焦点を当てている。