Semidefinite lower bounds for covering codes

問題定義
本論文は、$K_q(n, r)$ を決定する問題を取り扱う。これは、語長 $n$、被覆半径 $r$ の $q$ 元被覆符号の最小サイズである。集合 $C \subseteq \{0, \dots, q-1\}^n$ が被覆半径 $r$ を持つとは、符号語を中心とする半径 $r$ のハミング球の和集合が、全ハミング空間を覆うことを意味する。この問題の特定の事例である $K_3(n, 1)$ は、「フットボール・プール問題」として知られており、最大で1つの誤りしか許容しない $n$ 回のサッカーの試合結果を保証するために必要な最小の予測数を求めるものである。上界は通常、具体的な符号を構成することによって確立されるが、本論文は $K_q(n, r)$ に対する改善された下界を導出することに焦点を当てている。

手法
著者らは、行列カットを用いたセミデフィニット・プログラミング（SDP）による被覆符号の下界を導入した Gijswijt (2005) の研究に基づいている。提示される手法は、以下の3つの主要な技術的進展を通じて、この下界を強化するものである。

1. ラッセール階層（Lasserre Hierarchy）の制約: 著者らは、0-1 プログラムのためのラッセール階層に着想を得た新しいセミデフィニット制約を導入している。具体的には、コードの3つの組（トリプル）の分布を分析することを含む、この階層の第2レベルを利用している。これにより、$\sum \lambda_i A_i(u) \ge \beta$ という形式の被覆不等式に従う、符号の特性ベクトルから導かれる行列 $N$ の構築へとつながる。
2. テリウェゲリア代数による対称性の簡約化: 結果となる SDP を計算可能にするため、著者らは対称性の簡約化を用いている。彼らは、ハミング・スキーム（バイナリおよび非バイナリの両方のケース）のテリウェゲリア代数を利用している。符号のペアおよびトリプルの軌道を、等長群 $Aut(q, n)$（およびその安定化部分群$Aut_0(q, n)$）の作用の下で特定することにより、行列変数の次元を削減している。
   • バイナリの場合 ($q=2$)、代数 $A_{2,n}$ は、それを小さな行列ブロックの直和へと写す $\ast$-同型写像 $\phi$ を用いてブロック対角化され、複雑さが $O(2^n)$ から $O(n^3)$ 変数へと減少する。
   • 非バイナリの場合 ($q \ge 3$)、同様のブロック対角化が代数 $A_{q,n}$ に適用され、複雑さが $O(n^4)$ 変数へと減少する。
3. 強化された目的関数: 本論文は、より強力な目的関数を提案している。コードサイズに関連する標準的な線形項を最小化する代わりに、著者らはコードサイズの3次のモーメントに対応する行列変数のトレースを最小化する。彼らは、この3次の目的関数が、以前に使用されていた線形または2次の目的関数よりも厳密にタイトな下界を与えることを証明している。

主な貢献

• 理論的枠組み: 本論文は、エラー訂正符号に対する Schrijver の下界を被覆問題へと一般化した、被覆符号のための厳密な SDP フレームワークを確立している。彼らは、ラッセール階層の文脈において、行列 $N$ および境界付き行列 $R(c, N)$ に対する制約を形式的に導出している。
• 対称性簡約アルゴリズム: 著者らは、バイナリおよび非バイナリのハミング・スキームの両方について、関連するテリウェリア代数のブロック対角化に関する明示的な公式を提供している。これには、行列カットの不等式とラッセール制約を簡約された変数空間へと変換するために必要な、詳細な組合せ論的係数（$\eta$ および $\alpha$）が含まれる。
• 計算実装: 著者らは、Julia プログラミング言語と SDPA-GMP ソルバーを用い、高精度算術（512ビットの BigFloat）を使用してこれらの下界を実装した。彼らは、SDP の生成を検証するための独立したコードを開発した。

結果
著者らは、広範なパラメータ ($q, n, r$) にわたる $K_q(n, r)$ の新しい下界を提示している。これらの結果は、バイナリ ($q=2$)、三元 ($q=3$)、および四元/五元 ($q=4, 5$) のケースをカバーする表1、2、および3にまとめられている。

• バイナリ・ケース: 新しい下界は、様々な $n$ と $r$ の値に対して、既知の下界を改善している（例：$K_2(13, 1), K_2(21, 1), K_2(13, 2)$）。著者らは、$K_2(18, 1)$ および $K_2(30, 1)$ について当初は改善された下界を見出したものの、これらの特定の値は後に Wu and Chen (2026) によって上回られたことを注記している。
• 非バイナリ・ケース: $K_3(13, 3)$ や $K_3(14, 4)$ などの三元符号（フットボール・プール問題）、および $q=4$ と $q=5$ に関して、大幅な改善が報告されている。
• 計算規模: 本論文は、対称性簡約された SDP の変数およびブロックサイズを報告している。例えば、バイナリ・ケースの $n=32$ において、簡約された SDP は 1,239 個の変数と、二乗和が 6,545 となるブロックサイズを持つ。計算時間は、インスタンスのサイズや不等式制約における非ゼロ係数の数に応じて、数秒から数日間に及んだ。

意義
本論文は、提案された手法が、幅広い被覆符号のパラメータに対して新記録を樹立する「より鋭い下界」をもたらすと主張している。被覆符号へのラッセール階層アプローチの拡張と、対称性の簡約化の効果的な利用により、既知の下界と上界の間のギャップを狭めることができることを著者らは示している。本研究は、これらの下界を計算するための体系的な方法を提供し、線形計画法の下界や、トリプル分布の制約や特定の目的関数の最適化を十分に活用していなかった以前の SDP アプローチに対する、より強力な代替手段を提供している。これらの結果は、被覆符号およびフットボール・プール問題の分野における更新されたベンチマークとして機能する。