The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048

技術要約：長さ2048の3次リード・マラー符号の重み分布

問題提起
リード・マラー符号 $RM(r, m)$の重み分布は符号理論における古典的な問題であるが、その閉形式の解は次数$r \leqslant 2$およびその双対$r \geqslant m-3$についてのみ既知である。3次のコード（$r=3$）については、長さ1024（$RM(3, 10)$）までの個別計算によって完全な分布が確立されてきた。本論文は、この連鎖における次のステップである、長さ2048の3次リード・マラー符号$RM(3, 11)$の重み分布の計算に取り組むものである。二次的な目的は、10変数におけるすべての3次形式に対する2次非線形性$d_2(f)$を決定し、それによって$RM(3, 10)$内における$RM(2, 10)$の相対被覆半径$\rho_{2,3}(10)$ を確立することである。

手法
計算は、Sarwate型の再帰法に基づいている。これは、$RM(3, m+1)$の重み生成関数を、すべての3次形式$f$に対する$f + RM(2, m)$の余接重み生成関数の二乗和として表すものである。余接生成関数は$f$の$GL(m, 2)$ 軌道にのみ依存するため、この和は、軌道のサイズで重み付けされた軌道代表元へと簡約される。

$m=10$ における主要なボトルネックは、膨大な数の軌道（3,691,560個の非ゼロ軌道）と、単一の余接生成関数を評価するコストである。BrierとLangevinによる標準的な分割公式では、$m=10$ の場合、$2^{36}$ 個の斉次2次形式に対する外部列挙が必要となり、カタログの全パスを実行するには計算量的に不可能である。

これを克服するため、著者らは構造定理（定理1）を用いている。すなわち、すべての非退化なブール3次形式は、奇数次元における単一の軌道を除いて、非退化な超平面への制限を持つ。$m=10$（偶数次元）の場合、この定理は、すべての非退化な軌道が、自身も非退化である超平面への制限を持つことを保証する。これにより、余接生成関数を $2^{36}$ ではなく $2^{26}$ のサイズの商空間を用いて計算することが可能となり、1つの軌道あたり $2^{10}$ の削減を実現している。

余接重み生成関数の評価は、得られたアフィン余接に対する高速ウォルシュ・アダマール変換を用いて行われる。カタログの全パスには、合計で約65 CPU年を要した。結果のタイトネスを検証し、上界の効率を向上させるために、局所探索ヒューリスティック（貪欲降下法、$\tau$-移動、反復局所探索、およびビームサーチの組み合わせ）が開発された。このヒューリスティックは、最小重み $wt(f+q)$を実現する明示的な2次補正$q$ を見つけ出し、全列挙のわずかなコストで被覆半径の証明を与える。

主要な貢献と結果

1. $RM(3, 11)$ の重み分布：
   本論文は、$RM(3, 11)$の完全な重み分布（表1）を提示している。この結果は、10変数におけるすべての3,691,560個の非ゼロ$GL(10, 2)$ 軌道の、ブール3次形式の二乗余接重み生成関数と、ゼロ軌道の寄与を合算することによって組み立てられている。

2. 2次非線形性と相対被覆半径：
   各余接生成関数の最小の非ゼロ指数は、2次非線形性 $d_2(f)$ に対応する。計算の結果、10変数におけるすべての3次形式における $d_2(f)$ の最大値は408であることが判明した。

• 定理3： $RM(3, 10)$内における$RM(2, 10)$の相対被覆半径$\rho_{2,3}(10)$ は、正確に408である。
• この最大値は、179個の異なる軌道において達成される。これらの軌道の代表元およびそれらの「キッシング数」（最小重みを達成する2次形式の数）は表2に記載されている。
• すべての179個の極限形式は非退化である。

3. 被覆半径の下界の改善：
   この結果は、$RM(2, 10)$ の被覆半径に関する最良の既知の下界を400から408へと引き上げた。179個の軌道は、この下界の明示的な証拠として機能する。

4. 交互ランクとの関連：
   本論文は、$d_2(f)$ と3次形式の交互ランク（$arank$）との関係を確立している。導出された境界（定理4）を用いて、著者らは、$d_2(f) = 408$である任意の形式について、交互ランクが少なくとも6であることを示している。$m=10$において、最大交互ランクは7である。分析によれば、179個の極限軌道のうち177個は$arank = 7$であり、残りの2個は$arank = 6$である。これは、極限形式がその次元における最大可能な交互ランクを持つことを強制されていた低次元（$m \leqslant 9$）の場合とは対照的である。

5. ヒューリスティック探索とコキュービック境界：
   局所探索ヒューリスティックは、全列挙の約1000分の1のコストで、境界 $\rho_{2,3}(10) \leqslant 408$ を再現することに成功した。これを7次形式に適用したところ、このヒューリスティックは $RM(7, 10)$内における$RM(6, 10)$ の相対被覆半径の上界を50から32へと改善した（補題2）。

意義
本論文の意義は、主に $RM(3, 11)$ の重み分布を解決し、既知の3次コードの連鎖を拡張したことにある。非退化な超平面制限に関する構造定理は、以前の手法では「手の届かない」ものであった全カタログパスを可能にした決定的な要因として提示されている。

$\rho_{2,3}(10) = 408$ の決定は、被覆半径の文献において $RM(2, 10)$の最良既知の下界を更新する点で重要である。さらに、極限軌道の分析は構造的な洞察を提供する。モノミアル・トレース形式（以前の記録である400を保持していたもの）からバイノミアル・トレース多項式への移行、および極限形式が最大交互ランクに集中していることは、高次元（$m > 10$）における高非線形形式の探索に向けた新しい方向性を示唆している。著者らは、さらなる符号理論およびブール関数解析の研究を促進するために、列挙データおよび参照コードを公開している。