🔢 mathematics

$2$-quasi-perfect Lee codes and abelian Ramanujan graphs: a new construction and relationship

この論文は、有限体 $\mathbb{F}_{q^2}$ の特定の生成集合から導出される新しい 2-準完全リー符号の無限族を構成し、それらがメスナガー、タン、およびチーによって構築された符号とリや有限ユークリッドグラフなどのアーベル・ラマヌジャングラフと密接に関連していることを示す統一的な理論的枠組みを提供するものである。

原著者： Shohei Satake

公開日 2026-04-22

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

CC BY 4.0

原著者： Shohei Satake

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

📡 1. 物語の舞台：通信と「エラー」

まず、私たちがスマホやインターネットでデータを送受信する場面を想像してください。
電波のノイズや障害物のせいで、送られたデータが少し壊れてしまうことがあります（これを「エラー」と呼びます）。

エラー修正コードは、壊れたデータを元の形に直すための「魔法のルール」のようなものです。
**リーコード（Lee Code）**という特定のルールを使えば、数字の並びが少しずれた場合でも、元の数字を推測して復元できます。

この論文の著者（佐々木翔平さん）は、**「2-準完全（2-quasi-perfect）」**と呼ばれる、非常に高性能な新しい「魔法のルール」を見つけました。

「完全」なら完璧に直せるが、作るのが難しすぎる。
「準完全」なら、ほぼ完璧に近い性能を持ちながら、現実的に作れる。
この新しいルールは、**「どんなに長いデータでも、ほぼ完璧に守れる」**というすごい特徴を持っています。

🧩 2. 新しい発見：「立方体の曲線」から生まれたルール

これまでの研究では、特定の条件を満たす「多項式（複雑な数式）」からコードを作ってきました。しかし、佐々木さんは全く新しいアプローチを取りました。

従来の方法： 特定の「鍵穴」に合う「鍵」を探すような、限られた設計図からコードを作っていた。
佐々木さんの方法： 有限体（数学の世界の「箱」）の中で、**「 $y = x^3$ という曲線」**という、とてもシンプルで美しい形からコードを作りました。

【イメージ】
これまでの研究者たちは、複雑なパズルを解いて鍵を作っていたのに対し、佐々木さんは「川の流れ（ $x^3$ の曲線）」そのものを見つめ、そこから自然に湧き上がるパターンをコードとして利用しました。
これにより、**「長さ $q-1$ の非常に長いデータ」**を、これまでとは異なる新しい方法で守れるようになりました。

🕸️ 3. 意外なつながり：「ラマヌジャン・グラフ」との出会い

この論文の最大の見どころは、**「エラー修正コード」と「グラフ理論（ネットワークの形）」**が実は同じものだった、と気づいた点です。

ラマヌジャン・グラフ（Ramanujan Graph）：
数学界で「最も効率的で美しいネットワーク」と呼ばれる存在です。
【イメージ】
巨大な都市の交通網を想像してください。
- 普通の道路網だと、A 地点から B 地点に行くのに、遠回りをしたり、渋滞（エラー）が起きやすかったりします。
- ラマヌジャン・グラフは、**「どの 2 地点も、最短距離で、かつ無駄なくつながっている」**という、神業のような交通網です。
- このネットワークは、ランダムに作られたように見えますが、実は数学的に完璧な秩序を持っています。
今回の発見：
佐々木さんが作った新しい「エラー修正コード」は、実はこの**「神業の交通網（ラマヌジャン・グラフ）」**をベースに作られていました。
さらに、過去の研究者（メスナガー、タン、キ氏ら）が見つけたコードも、実は別の種類の「神業の交通網（リ氏グラフや有限ユークリッドグラフ）」とつながっていることがわかりました。

【まとめると】
「コードを作る」という行為は、実は**「効率的なネットワーク（グラフ）を作る」ことと同じだったのです。
著者は、これらバラバラに見えたコードたちを、「ラマヌジャン・グラフという共通の土台」**で一つにまとめ上げました。

💡 4. なぜこれがすごいのか？（2 つの矛盾する性質）

この論文の最も面白い点は、**「ランダムなように見えるもの」と「完璧な秩序」**が共存していることです。

ランダム性（擬似ランダム性）：
作ったグラフは、ランダムに作られたように見えます。統計的には、ランダムなネットワークと区別がつかないほど「自然」です。
完璧な秩序：
しかし、その中にある「コード」としてのルールは、非常に厳密で秩序だった構造を持っています。

【例え話】

ランダムな砂山は、どこを見ても同じように見えますが、特定の形（ピラミッド）を作るのは不可能です。
ピラミッドは完璧な形ですが、自然にできるものではありません。
この論文が示したのは、**「ランダムに見える砂山の中に、偶然ではなく、数学的な必然でピラミッドが隠れていた」**という驚きです。
- 一見ランダムに見えるネットワーク（グラフ）が、実は「エラーを完璧に防ぐための秩序（コード）」を内包していたのです。

🎯 結論：何ができるようになるの？

この研究によって、以下のことが明らかになりました。

新しいコードの設計図：
これまで難しかった「超長距離の通信」を守る、新しい高性能なエラー修正コードを、シンプルに作れるようになりました。
理論の統一：
「コードを作る」と「美しいネットワークを作る」が同じ問題だったことがわかり、数学の異なる分野（符号理論とグラフ理論）が手を取り合えました。
未来へのヒント：
「ランダムに見えるものの中に、完璧な秩序を見つける」という視点は、今後、より良い通信技術や暗号技術を開発する際の重要な指針になるでしょう。

一言で言うと：
「通信の守り神（コード）」と「数学の美しさ（グラフ）」が、実は双子の兄弟だったことを発見し、その絆を解き明かした論文です。

論文「2-準完全リー符号とアーベル・ラマヌジャングラフ：新しい構成と関係性」の技術的サマリー

1. 研究の背景と課題

リー距離（Lee distance）に基づく誤り訂正符号である「リー符号」の構成は、符号理論、数論、代数幾何、組合せ論の交差点にある重要な課題です。特に、完全符号（perfect code）の構成は古典的な問題ですが、Golomb-Welch 予想により、長さ $n$ の完全符号が存在するのは $t=1$ または $n=1,2$ の場合に限られることが示唆されており、一般の $t$ に対して完全符号の構成は困難です。

そのため、より現実的な目標として「 $t$ -準完全リー符号（ $t$ -quasi-perfect Lee codes）」の構成が注目されています。これは、 $t$ 個の誤りを訂正でき、かつ半径 $t+1$ で全体を覆う（covering radius が $t+1$ ）符号を指します。
既存の研究（Camarero-Martínez, Mesnager-Tang-Qi など）では、特定の多項式の解集合を用いた構成が提案され、これらがアーベル・ラマヌジャングラフ（Abelian Ramanujan graphs）と関連していることが示されてきました。しかし、以下の課題が残っていました。

任意に大きな長さを持つ 2-準完全リー符号の構成は依然として困難な開問題である。
特定の代数的構造がなぜそのような符号を生み出すのかを統一的に説明する理論的枠組みが欠如している。
既存の構成と既知のラマヌジャングラフ（Li のグラフ、有限ユークリッドグラフなど）との関係が明確にされていなかった。

2. 手法とアプローチ

本論文では、有限体 $\mathbb{F}_q$ （ $q=p^k, p \ge 5$ ）上の代数的構造を用いて、以下の 2 つのアプローチで問題を解決します。

2.1. 新しい符号の構成

生成集合 $H_q := \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ を用いて、新しい 2-準完全リー符号を構成します。

構成の定義: 有限体 $\mathbb{F}_q$ の加法群 $\mathbb{F}_q^2$ 上の Cayley グラフ $\text{Cay}(\mathbb{F}_q^2, H_q)$ を考え、その生成集合 $H_q$ から線形符号 $C(\mathbb{F}_q^2, H_q)$ を定義します。
証明手法: 符号が 2-準完全であるための必要十分条件（Mesnager-Tang-Qi による Lemma 2）を満たすことを示すために、以下の代数幾何学的な解析を行います。
- $H_q$ の和集合 $H_q^{(i)}$ （ $i$ 個の要素の和で表せる点の集合）のサイズを数え上げます。
- 三次曲線 $y=x^3$ 上の点に関する方程式系 $a = x+y+z, b = x^3+y^3+z^3$ の解の存在を、Hasse-Weil 境界（曲線の有理点の数の下限）を用いて証明します。
- 多項式 $F_{a,b}(x,y) = xy(x+y) - a(x+y)^2 + a^2(x+y) + b - a^3/3$ の絶対既約性を示し、曲線が十分な数の点を持つことを確認します。

2.2. 既存構成とラマヌジャングラフの統合

Mesnager-Tang-Qi によって提案された既存の符号構成と、組合せ論・数論でよく研究されている「Li のグラフ」および「有限ユークリッドグラフ（Finite Euclidean graphs）」との関係を明らかにします。

Li のグラフ: 有限体 $\mathbb{F}_{q^2}$ におけるノルム 1 の元からなる集合 $N_2$ を生成集合とする Cayley グラフ。
有限ユークリッドグラフ: 非退化二次形式 $Q(x,y)=1$ を満たす点の集合を生成集合とする Cayley グラフ。
統一的視点: これらのグラフの生成集合が、Mesnager-Tang-Qi 符号の生成集合 $H_+$ や $H_-$ と本質的に一致することを示し、既存の符号構成が「非退化二次形式」の枠組みで統一的に記述可能であることを証明します。

3. 主要な結果

3.1. 新しい 2-準完全リー符号の無限族の構成（定理 4）

$p \ge 5$ を素数、 $q=p^k \ge 14$ とする。生成集合 $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ から得られる符号 $C(\mathbb{F}_q^2, H_q)$ は、以下のパラメータを持つ 2-準完全 $p$ 進リー符号である。

長さ: $n = \frac{q-1}{2}$
次元: $k_{dim} = \frac{q-1}{2} - 2k$
特徴: この構成は Forey らによって最近発見された「アーベル・ほぼラマヌジャングラフ」に基づいており、既存の構成とは異なる代数的構造を持つ。特に、 $p \equiv 1, 7 \pmod{12}$ の場合にも新しいパラメータの符号を提供する。

3.2. 既存符号とラマヌジャングラフの同定（命題 16, 18）

Mesnager-Tang-Qi による符号 $C(\mathbb{F}_q^2, H_+)$ は、Li のグラフ（ $\text{Cay}(\mathbb{F}_q^2, N_2)$ ）の生成集合と一致する。
同様に、 $H_-$ は特定の二次形式 $Q(x,y)=xy$ に対応する有限ユークリッドグラフの生成集合と一致する。
任意の非退化二次形式 $Q$ に対して、その単位集合 $E_Q$ から得られる符号は、座標の置換と符号変化を除いて、 $H_+$ または $H_-$ のいずれかの符号と一致する。これにより、Mesnager-Tang-Qi による符号族は、有限ユークリッドグラフの枠組みで完全に記述可能であることが示された。

3.3. 数値例

$p=17, 19, 23, 5$ などの具体的なケースにおいて、新しい構成と既存の Mesnager-Tang-Qi 構成のパリティチェック行列を比較し、両者が同じパラメータを持つ場合でも代数的構造が異なることを示した。

4. 意義と結論

理論的意義

構成の拡張: 任意に大きな長さを持つ 2-準完全リー符号の新しい無限族を明示的に構成し、既存の構成とは異なる代数的基盤（ $y=x^3$ の曲線）を提供しました。
理論的統合: 符号理論とスペクトルグラフ理論の架け橋を強化しました。特に、2-準完全リー符号の構成が、Li のグラフや有限ユークリッドグラフといった既知のアーベル・ラマヌジャングラフと密接に関連していることを明らかにし、統一された理論的枠組みを提供しました。
構造とランダム性のパラドックス: 2-準完全符号は、スペクトル的にはランダムグラフと区別がつかない（擬ランダム性を持つ）ラマヌジャングラフから導かれますが、その一方で、符号の完全性を保証するためには、ランダムグラフには見られないような厳密な局所構造（Lemma 2 の条件）が要求されます。この「スペクトル的なランダム性」と「局所的な構造的規則性」の共存は、代数的構造の深遠な性質を示唆しています。

今後の展望

本論文は、他のアーベル・ラマヌジャングラフが新たな準完全リー符号の生成集合を持つかどうかという問いを提起しています。この研究は、リー符号の理論とスペクトルグラフ理論のさらなる融合を促すものであり、誤り訂正符号の設計における代数的手法の重要性を再確認させるものです。