🔢 mathematics

Sharper upper bounds for $q$ -ary $B_2$ codes from Toeplitz SDPs

本論文は、 $q$ 進 $B_2$ コードのレートに関する既存の情報理論的上界を、確率質量関数の差の分布が持つフーリエ解析的構造（非負三角多項式）をトプリッツ半正定値計画問題として最適化することで、 $q \in \{9, \dots, 13\}$ の場合にさらに厳密な値へと改善する手法を提案している。

原著者： Stefano Della Fiore

公開日 2026-03-31

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Stefano Della Fiore

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🍳 1. 背景：「B2 コード」とは何か？（料理のレシピ集）

まず、この論文が扱っている**「B2 コード」**とは何でしょうか？

想像してください。あなたは世界中のすべての料理の「レシピ」を、ある特定のルールに従って整理しようとしています。

ルール： 「どんな 2 つのレシピを混ぜ合わせても、その結果（味や見た目）が、他のどの 2 つのレシピを混ぜた結果とも絶対に同じにならないようにしなさい」というものです。

このルールを満たすようにレシピ（コード）を並べると、非常に効率的で、混同の起きない「最強の辞書」が作れます。しかし、この辞書に**「どれくらい多くのレシピを入れられるか（容量）」**には限界があります。

これまでの研究では、「この辞書には最大でこれだけのレシピが入るはずだ」という**「上限（天井）」**がいくつか提案されていました。でも、その天井は少し「甘く（高く）」見積もられているのではないか？というのがこの論文のスタート地点です。

🔍 2. 問題：これまでの計算は「粗い網」だった

これまでの研究（著者自身の過去の論文含む）では、この「天井」を計算する際に、**「2 つのレシピを混ぜたときに、偶然同じ味になる確率」**という、非常に単純なルールだけを使っていました。

例え話：
「料理を混ぜた結果が同じになる確率が 10% 以上あるなら、それはダメな組み合わせだ」という**「粗い網」**で漁をして、残った魚（可能なレシピ数）の大きさを推測していました。

しかし、この「粗い網」だと、**「実際にはありえないような、不自然なレシピの組み合わせ」**も「あり得る」として数えてしまい、結果として「天井」を必要以上に高く見積もってしまっていたのです。

🌊 3. 新発見：「波の干渉」を使う（フーリエ解析の力）

この論文の著者（ステファノ・デッラ・フィオレさん）は、**「もっと細かい網」**を使えば、より正確に天井を計算できることに気づきました。

それは**「フーリエ解析（波の分析）」**という数学の道具です。

例え話：
料理の味（レシピ）を、**「波」**に見立ててみましょう。

2 つのレシピを混ぜることは、**「2 つの波を重ね合わせる（干渉させる）」**ことと同じです。

過去の研究は、「波の高さ（確率）」だけを見ていました。

しかし、著者は**「波の形そのもの」に注目しました。「2 つの波を重ねたとき、『マイナス』の波（消し合う部分）が生まれてはいけない**」という、波の物理的な性質（非負性）を厳しくチェックするのです。

これを数学的に言うと、**「トプリッツ行列（Toeplitz matrix）」**という特殊な表を使って、波の形が「あり得る形」かどうかを厳密に判定する計算を行いました。

📉 4. 結果：天井が下がった！（より正確な限界）

この新しい「波の形をチェックする網」を使って計算し直したところ、驚くべき結果が出ました。

これまでの天井： 「最大で 100 個のレシピが入る！」
新しい天井： 「実は、95 個が限界だった！」

つまり、**「これまでは『もっと入るはずだ』と過大評価していたが、実はもっと少ない数しか入れられない」**という、より厳しく、より正確な限界が見つかったのです。

特に、9 種類から 13 種類の要素（q=9〜13）を使う場合において、この新しい計算結果は、これまで知られていたどの研究よりも「低い（＝より正確な）」天井を示しました。

🏗️ 5. 具体的な手法：「半正定値計画（SDP）」という魔法の計算機

著者はこの計算をどう行ったのでしょうか？
**「半正定値計画（SDP）」**という、現代のコンピュータが得意とする高度な最適化アルゴリズムを使いました。

例え話：
複雑な迷路の出口を探すとき、手探りで歩くのではなく、**「空から迷路全体を俯瞰して、最短かつ不可能なルートを除く」**ような計算をコンピュータにさせました。

この計算は非常に重く、**「トプリッツ SDP（Toeplitz SDP）」**という名前がついています。著者はこれを工夫して実行し、これまで誰も到達できなかった「より低い天井」の数値を導き出しました。

💡 まとめ：なぜこれが重要なのか？

この論文の貢献は 3 つあります。

新しい視点： 「確率」だけでなく、「波の形（フーリエ解析）」まで含めて考えることで、より厳しい制限を見つけ出した。
数学的な証明： 「波がマイナスにならない」という性質を、コンピュータが解ける形（SDP）に変換して証明した。
実用的な成果： 特定の条件下（q=9〜13）で、**「データ通信や暗号の理論的な限界」**を、これまでより正確に（厳しく）見積もることができた。

一言で言えば：
「これまでは『もっと入るはずだ』と楽観的に考えていたデータ容量の限界を、**『実はもっと厳しいルールがあるから、もっと少ない数しかない』**と、数学とコンピュータの力で証明し直しました」というお話です。

これは、将来の通信技術や暗号設計において、「無駄な期待を持たず、より現実的な設計図を描く」ための重要な一歩となります。

論文「Sharper upper bounds for q-ary B2 codes from Toeplitz SDPs」の技術的サマリー

1. 問題の背景と定義

本論文は、q 進 B2 コード（q-ary B2 codes）のレート（符号率）に対する情報理論的な上限（upper bound）の改善を目的としています。

B2 コードの定義: 長さ $n$ $n$ の q 進符号 $C_n$ $C_{n}$ が B2 コードであるとは、任意の 2 つの符号語 $c_i, c_j$ $c_{i}, c_{j}$ （ $1 \le i \le j \le M$ $1 \leq i \leq j \leq M$ ）の和 $c_i + c_j$ $c_{i} + c_{j}$ （実数上の和）がすべて一意である（重複しない）ことを指します。
- $q=2$ の場合、これは通常の「2-分離可能コード（2-separable code）」の定義と同等です。
目的: 符号長 $n$ が無限大に発散する際の漸近的なレート $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$ の上限をより厳密に（小さく）見積もることです。既存の研究（Lindström [3], Della Fiore–Dalai [5], Wang [7] など）では、エントロピー最大化の問題を解く際に、確率変数の差の分布に対する制約が粗いもの（単に $P(X=Y) \ge 1/q$ ）しか用いられておらず、上限が緩いままでした。

2. 手法とアプローチ

著者は、2 つの独立同分布（i.i.d.）q 進確率変数 $X, Y$ の差 $D = X - Y$ の分布が持つ完全なフーリエ解析的構造を解明し、これを半正定値計画問題（SDP）に定式化することで、エントロピーの上限を厳密化しました。

2.1 フーリエ解析的定式化

確率質量関数（pmf） $P$ を持つ $X$ とその独立なコピー $Y$ に対し、差 $D=X-Y$ の pmf を $r$ とします。
$D$ の特性関数 $\psi_D(\theta)$ は、 $X$ の特性関数 $\phi(\theta)$ を用いて $\psi_D(\theta) = |\phi(\theta)|^2$ と表せます。
したがって、 $D$ の pmf $r$ のフーリエ級数 $R(\theta) = \sum r_k e^{ik\theta}$ は、非負の三角多項式（nonnegative trigonometric polynomial）でなければなりません。
従来の研究 [5] では、この非負性 $R(\theta) \ge 0$ を無視し、単に $r_0 = P(X=Y) \ge 1/q$ という制約のみを用いてエントロピーを最大化していました。これにより得られた上限は粗いものでした。

2.2 トープリッツ半正定値計画（Toeplitz SDP）への帰着

三角多項式 $R(\theta)$ が非負であるという条件は、その係数 $r_k$ によって構成される無限族のトープリッツ行列が半正定値（PSD）であることと等価であることが知られています（Herglotz の定理や Fejér-Riesz の因数分解に関連）。
著者は、この事実を用いて、エントロピー最大化問題を以下の凸最適化問題として再定式化しました：
- 目的関数: $D$ のエントロピー $H(D) = -\sum r_k \log r_k$ の最大化
- 制約条件:
  1. $r_k \ge 0, \sum r_k = 1$ （確率分布）
  2. $r_{-k} = r_k$ （対称性）
  3. $r_0 \ge 1/q$ （衝突確率の制約）
  4. すべての $N \ge 1$ に対して、トープリッツ行列 $T^{(N)}(r)$ が半正定値である（ $T^{(N)}(r) \succeq 0$ ）

2.3 数値的評価

無限個の制約条件を扱うため、 $N \le N_{\max}$ まで切り詰めた切断されたトープリッツ SDP（Truncated Toeplitz SDP）を数値的に解くことで、エントロピーの上限 $h^F_q$ を計算しました。
得られた $h^F_q$ を用いて、B2 コードのレート上限 $R_b \le \frac{h^F_q}{\log q + h^F_q}$ を導出しました。

3. 主要な貢献

フーリエ解析的緩和の導入: i.i.d. 差分布 $D=X-Y$ に対して、その特性関数が非負三角多項式であるという事実を明示的に利用した緩和手法を提案しました。
SDP 定式化の明確化: フーリエ係数の非負性条件が、無限族のトープリッツ半正定値制約と等価であることを示し、これを標準的な SDP として定式化しました。
レート上限の厳密化: 上記の改良されたエントロピー上限を、プレフィックス・サフィックス法（prefix-suffix method）に組み込むことで、q 進 B2 コードの漸近的なレート上限を厳密に改善しました。
数値的検証: $q \in \{9, 10, 11, 12, 13\}$ に対して数値計算を行い、既存の最良の上限を凌駕する新しい値を得ました。

4. 結果

表 I（Numerical Comparison）に示されるように、 $q=9$ から $13 $までの範囲において、提案手法による新しいレート上限（$ R^{new}_q$）は、Lindström [3]、Della Fiore–Dalai [5]、Wang [7] の既存のすべての上限よりも厳密（小さい）な値となっています。

例 ( $q=9$ $q = 9$ ):
- 既存最良 (Wang [7]): 0.55841
- 提案手法 (Ours): 0.55792
例 ( $q=13$ $q = 13$ ):
- 既存最良 (Wang [7]): 0.55454
- 提案手法 (Ours): 0.55206

これらの結果は、 $q$ が大きくなるにつれて改善の幅が顕著であることを示唆しています。

5. 意義と展望

理論的意義: コード理論におけるレート上限の導出において、単なる「衝突確率（collision probability）」の制約だけでなく、分布全体の「正定値性（positive definiteness）」という構造情報を SDP を通じて活用することで、より tight な上限が得られることを実証しました。
手法の汎用性: このフーリエ/トープリッツ SDP のアプローチは、他の符号族（例えば、より高次の和集合に関する条件を持つ符号など）や、構造化された離散差のエントロピー制御が必要な問題にも拡張可能である可能性があります。
今後の課題: 緩和のギャップ（spectral factorization の非負係数条件を課していないことによるギャップ）がどの程度存在するか、あるいは厳密になる条件を明らかにすることが今後の研究課題として挙げられています。

総じて、本論文は半正定値計画（SDP）と調和解析の強力な組み合わせを用いて、情報理論的な符号限界の計算精度を飛躍的に向上させた重要な成果です。