Constructing linear codes from digraphs and groups

騒がしい部屋の中で秘密のメッセージを送ろうとしている場面を想像してみてください。ただ言葉をささやくだけでは、静電気や雑音によって言葉が乱れてしまうかもしれません。しかし、もしメッセージを巧妙なパターンで繰り返せば、たとえ一部が失われたとしても、聞き手は元の言葉を導き出すことができます。これが**誤り訂正符号（error-correcting codes）**の魔法です。これは、あなたのテキスト、写真、銀行振込をグリッチ（不具合）から守るための数学的なレシピです。何十年もの間、数学者たちは「ゴールドリックス（適温）」のような符号、つまり、素早く送信できるほど短く、多くのエラーを修正できるほど強く、そしてコンピュータが即座にチェックできるほど単純な符号を追い求めてきました。

これらの符号を構築するために、科学者たちはしばしば2つの強力なツールを使用します。一つは群（groups）（パターンの崩れを防ぎながら、いかに物をシャッフルするかを教える対称性のためのルールブックのようなもの）であり、もう一つはグラフ（graphs）（点とそれをつなぐ線による地図のようなもの）です。有名な地図の一種に**ケイリーグラフ（Cayley graph）**があります。これは、ある群の特定のルールに従って構築されたものです。2012年、研究者たちは、これらの特別な地図を用いることで、新しい種類の超効率的な符号を作成できることを発見しました。しかし、そこには落とし穴がありました。これらの地図は非常に厳格なルールに基づいて構築されていたため、作れる符号の種類が制限されていたのです。それは、素晴らしいレシピを持っているのに、特定のブランドの材料しか使わせてもらえないようなものでした。

現在、2人の数学者、コエン・デル・バジェ（Coen Del Valle）とシェリル・E・プレーガー（Cheryl E. Praeger）が、そのパントリーを開放しました。彼らは、特定の厳格な地図だけでなく、あらゆる種類の地図を使ってこれらの強力な符号を構築する方法を見出したのです。彼らはこれらを**グラフ符号（graph codes）およびダイグラフ符号（digraph codes）**と呼んでいます。標準的なグラフを「道が両方向に通っている地図」とするならば、**ダイグラフ（有向グラフ）**は「一方通行の道路がある地図」です。これらのより柔軟な地図を使用することで、より幅広い種類の誤り訂正符号を作成できることを著者らは示しています。彼らは、これらの新しい符号が従来の符号と同じくらい強力で効率的でありながら、想像しうるほぼすべての対称的な構造から構築できるという自由度を備えていることを証明しました。これは、エンジニアや科学者が、より優れた、より速く、より信頼性の高い通信システムを設計するための全く新しい道具箱を手に入れたことを意味しており、非常に重要なことです。

新しい設計図：厳格なルールから柔軟な地図へ

論文は、2012年のカウフマン（Kaufman）とルボトスキー（Lubotzky）による画期的な成果への謝辞から始まります。彼らは、「対称的なLDPC良質な符号」のファミリーを最初に構築しました。これを分解してみましょう。「LDPC」とは、チェックが容易であること（低密度パリティ検査）を意味し、「良質（good）」とは、効率的かつ強力であることを意味し、「対称的（symmetric）」とは、その部分を回転させたりシャッフルしたりしても、符号が同じように見えることを意味します。彼らはこれを**ケイリー符号（Cayley codes）**を用いて構築しました。これは、建物のすべての部屋が次の部屋の完璧なコピーであり、厳格な群のルールに従って配置されている家を建てるようなものです。

デル・バジェとプレーガーは、シンプルな問いを投げかけました。「本当にそれほど厳格なルールが必要なのだろうか？」彼らは、ケイリー符号の魔法は群のルールそのものから来るのではなく、使用される地図（グラフ）が**頂点推移的（vertex-transitive）**であるという事実から来ていることに気づきました。平たく言えば、地図がどの点から見ても同じに見えるということです。ある点に立ったとき、周囲の道のパターンは他のどの点の周囲のパターンとも同一に見えます。

著者らは、地図がこの「似通った外観」という特性を持っていれば、優れた符号を構築するためにケイリーグラフである必要はないことに気づきました。これが、彼らの2つの主要な発明へとつながりました。

1. グラフ符号（Graph Codes）: これらは、無向グラフ（道が両方向に通っている地図）に基づいて構築されます。出発点の点を選び、その隣人（隣接する点）を調べ、接続に対して小さな局所的符号を適用します。そして、地図全体がすべての点から同じように見えるため、この局所的なルールをいたるところにコピーします。
2. ダイグラフ符号（Digraph Codes）: これらは、有向グラフ（一方通行の道路がある地図）に基づいて構築されます。ここでは、少し注意が必要です。なぜなら、「外側」の隣人（道が進む方向）は、「内側」の隣人（道が入ってくる方向）とは異なる可能性があるからです。そのため、外向きの道に対して一つの局所的符号を適用し、内向きの道に対して別の符号を適用します。

ゲームのルール

著者らは単にこれらの符号を発明しただけでなく、それらが機能することを証明しました。もし選んだ局所的な「材料」（小さな符号）が地図の対称性を尊重していれば、最終的な巨大な符号も地図全体の対称性を尊重することを証明しました。これは極めて重要です。なぜなら、これはコードが対称的であることを意味し、デコード（復号）を容易にするための望ましい特性だからです。また、小さな符号が「単一軌道対称（single-orbit symmetric）」（一つのパターンが繰り返されることで生成されるという意味の専門用語）であれば、大きな符号の「双対（dual）」（エラーチェックに使用される関連符号）もまた、単純な繰り返しパターンによって生成されることも示しました。これにより、これらの新しい符号は高度に対称的であり、かつLDPC、つまり効率的でチェックが容易であることを意味します。

興味深い発見の一つは、**連結性（connectivity）**に関するものです。著者らは、もし地図が非連結（例えば、互いに触れていない2つの離れた島がある地図）であれば、大きな符号はそれぞれの島の上に構築された小さな符号の集合体になることを証明しました。これは、問題を大幅に簡素化します。つまり、連結された地図（一つの大きな島）に対して符号を構築することに集中すれば、残りの部分についても自動的に対処できるということです。

数字のゲーム：どれほど優れているのか？

著者らは理論にとどまらず、これらの符号が実際にどれほど優れているかを計算しました。彼らは主に2つの統計量に注目しました。

• レート（Rate）: メッセージの全サイズに対して、どれだけの有用な情報を送れるか。
• 相対距離（Relative Distance）: 符号が修正できるエラーの数。

彼らは、新しい符号が従来のケイリー符号と同等、あるいは場合によってはそれ以上の性能を発揮することを見出しました。具体的には、コードの「エラー戦闘力」を予測するために使用される数学的公式を改善しました。従来の公式はある一定の下限値を示していましたが、彼らの新しい公式はその限界をわずかに押し上げます。

これが現実世界で機能することを証明するために、彼らはこれらの新しい符号の**無限族（infinite family）**を構築しました。彼らは、$PSL_2(q)$（行列の群）と呼ばれる群に基づいた特定の有向グラフを使用し、素数 $p = 4093$ を用いました。彼らは、無限の数の素数 $q$ に対して、以下の条件を満たす符号を構築できることを示しました。

• レートが少なくとも $2/(p+1)$、すなわち約 $0.0005$ 以上。
• 相対距離が少なくとも $0.001$ 以上。

これらの数値は、コードがどれほど大きくなっても正の値を維持するため、彼らはこれを「良質なダイグラフ符号の無限族」と呼んでいます。これは、コードを大きくしても効率を失うことなく作り続けられることを証明しているため、大きな前進となります。

次は何が行われるのか？ 未解決の問い

論文は、数学界への挑戦状で締めくくられています。著者らは新しいコードの世界への架け橋を築きましたが、まだ未開拓の領域が存在します。彼らは3つの具体的な問いを提示しています。

1. ケイリーグラフから構築されていない、対称的な符号の無限族を見つけることができるか？（彼らはできると考えていますが、まだ証明はしていません）。
2. **適切なダイグラフ（proper digraph）**から構築された、対称的な符号の無限族を見つけることができるか？ 「適切なダイグラフ」とは、少なくとも一つの道が一方通行である地図のことです（AからBへ行けるとしても、必ずしもBからAへ戻れるとは限りません）。これは、ほとんどの既知の対称的な地図が双方向であるため、非常に困難な課題です。
3. 「外側」の符号と「内側」の符号が互いに異なるような、対称的な符号を構築できるか？

また、著者らは彼らの手法が、コードの直積（direct product）（2つのコードを一つの大きなコードに組み合わせること）のような、既知の他の符号構成を再現できることも指摘しています。実際、彼らは有名なペテルセングラフ（Petersen graph）（10個の点で構成される特定の非ケイリー地図）を用いて、高度に対称的でありながら、ケイリー符号としては構築できない符号を構築できることを示しました。これは、彼らの理論が実際に機能している具体的な例です。つまり、従来の厳格なルールでは到達できなかった、より優れた、あるいは異なる種類のコードを生み出せることを示しています。

要約すると、デル・バジェとプレーガーは、強力な数学的ツールを取り出し、その制約を緩めることで、より自由な環境下でさえもそれがより良く機能することを示しました。彼らは単に新しい符号を見つけたのではありません。彼らは、符号を構築するための新しい考え方を見出し、厳格な群のルールという扉によって閉ざされていた広大な可能性への扉を開いたのです。