Perfect $2$-codes over arbitrary alphabets

あなたは、ノイズと混沌に満ちた銀河を越えて秘密のメッセージを送っていると想像してください。文字を送信するたびに、いたずら好きなスペース・ゴブリンがその文字を別のものにすり替えたり、あるいは丸ごと消し去ったりしてしまうかもしれません。この混沌を生き抜くために、あなたはメッセージを一度送るだけでは足りません。コードの中に「予備の部品」を組み込んでおくのです。これが**誤り訂正符号（error-correcting codes）**の世界です。あなたのテキストメッセージや宇宙探査機、ストリーミングビデオが、意味不明なゴミへと変わってしまうのを防ぐための、目に見えない盾なのです。

この宇宙において、「完全符号（perfect code）」は聖杯のような存在です。それはパッキング・パズルのようなものです。巨大な箱（考えられるすべてのメッセージ）があり、そこにできるだけ多くの「安全地帯（実際的なメッセージ）」を詰め込もうとする試みです。各安全地帯には、保護のための半径が存在します。もしメッセージがゴブリンに襲われて少し変化してしまったとしても、それが依然としてある安全地帯の中に収まっていれば、受信者はそれが元々どのメッセージであったかを正確に知ることができます。コードが「完全」であるとは、これらの安全地帯が、隙間も重なりもなく、まるでジグソーパズルのようにぴったりと組み合わさっている状態を指します。もしパズルに隙間があれば、メッセージを失う可能性があり、もし重なりがあれば、送られたメッセージがどれであるか混乱してしまうかもしれません。

何十年もの間、数学者たちはこのパズルの究極のバージョン、すなわち、あらゆるサイズのアルファベットを用いて、一度に2つの誤りを修正できる「完全な2符号（perfect 2-code）」を見つけ出そうと格闘してきました。彼らは、3つ以上の誤りを修正できる完全な解は見つけてきましたが、単なる素数のべき乗ではない「変則的な」アルファベットサイズにおける、ちょうど2つの誤りを修正するケースについては、頑固で未解決の謎のまま残されてきました。それは、2、4、または8個のアイテムを完璧にパッキングする方法は知っているのに、6個や10個のアイテムではどうすれば完璧にできるのか全く分からない、という状況に似ています。

マイケル・ベネットによるこの論文は、まさにその特定の謎に深く切り込んでいます。著者は、非常に大規模で特定の種類の「変則的な」アルファベットサイズに対して、完全な2符号は単純に存在しないことを証明しようとしています。この論文は単なる推測ではありません。高度な数学、具体的には、数字が実際に触れ合うことなく、いかに接近できるかを測定するツール（数論的近似）を用いて、もしそのようなコードが存在するとすれば、それは算術の法則を打ち破るほど信じられないほど巨大で奇妙なものにならざるを得ないことを示しています。

主な発見は、強力な「進入禁止」ゾーンです。ベネットは、アルファベットのサイズが2のべき乗に一つの素数のべき乗を掛け合わせたもの（例えば $2^\alpha \times p^\beta$）である場合、完全な2符号を構築しようとしても無駄であることを証明しました。具体的には、もしそのようなコードが理論的に可能であるならば、関与する素数は$10^{10}$（100億）よりも大きく、2のべき乗は20よりも大きくなければならないことを示しています。さらに、もしそのようなコードが存在するならば、その素数は8で割ったときの余りが3でなければなりません。

この論文はさらに踏み込み、最大の素因数が13以下のアルファベットサイズにおける完全2符号の存在をも否定しています。事実、著者は、アルファベットサイズが $2^\alpha \times p^\beta$ であり、$\alpha$ が小さな値（20まで）である多くの特定の数値を含む場合、完全2符号は存在しないという長年の予想を裏付けています。著者は単に「可能性が低い」と言っているのではなく、そのようなコードが存在するための条件が数学的な矛盾を導き出すことを、厳密な数学的証明を用いて示しているのです。これは、世界中のあらゆる可能なアルファベットサイズについて否定しているわけではありませんが、最も一般的で興味深い「変則的な」サイズについては、事実上、扉を閉ざしてしまったことを意味します。

不可能なパズルの物語

マイケル・ベネットが何を解決しようとしたのかを理解するために、彼が取り組んだパズルを見てみましょう。あなたが特定のアルファベットで作ることができるすべての単語の巨大なグリッドがあると想像してください。あなたは、そのグリッド上に「ビーコン（符号語）」を配置したいと考えています。各ビーコンの周囲には、すべての単語（2つの誤りまでの距離にある単語）をカバーする円を描きます。コードが完全であるためには、これらの円が重なることなく、グリッド全体を覆わなければなりません。

数学者たちは、アルファベットのサイズが「素数のべき乗」（2, 3, 4, 8, 9, 16など）である場合、これらが完璧に機能する特別なケースがわずかにあることを古くから知っています。しかし、もしアルファベットのサイズが10や12、20のようなものだったらどうでしょうか？ これらは素数のべき乗ではない「合成数」です。1つの誤りを修正する場合、いくつかの解が存在することは分かっています。3つ以上の誤りを修正する場合、解が存在しないことも分かっています。しかし、2つの誤りを修正する場合については、それが未解決の問いでした。

ベネットの論文は、特定の種類の合成数に焦点を当てています。それは、$2^\alpha \times p^\beta$ という形をしたものです。これは、たくさんの2の積に、単一の素数 $p$ のコピーを掛け合わせたアルファベットサイズです（例：5, 7, 11など）。質問はこうです。「これらのサイズに対して、完全な2符号を構築できるか？」

数学的な探偵工作

ベネットは、単にコードを構築しようとして失敗したのではなく、ある特殊な多項式の「根（ルート）」を見ることで、それらが存在しないことを証明しました。この方程式は、もし完全なコードが存在するならば、ビーコンがどこにあるべきかを示す地図のようなものです。もし完全なコードが存在するならば、この地図には2つの特定の整数点（根）が互いに非常に近い位置に存在しなければなりません。

著者の画期的な発見は、これら2つの点（$r_1$ と $r_2$ と呼びましょう）が「S単元（S-units）」である必要があるという点でした。平易に言えば、これらを構成する素因数は、非常に限定された、特定の数字のリスト（アルファベットのサイズと2を割る素数）からのみ抽出されるという意味です。

ここが巧妙な部分です。ベネットは、完全なコードが存在するためには、これら2つの数が驚くほど近くに、つまり、その大きさに対して差が極めて小さくなければならないことを示しました。しかし、ディオファントス近似（数字を分数でいかに良く近似できるかを研究する分野）と呼ばれる有名な数学の分野によれば、制限された素因数を持つ数字は、それらが非常に小さくない限り、互いにこれほど接近することはできません。

彼はこれを、問題の幾何学から導き出された特定の方程式と組み合わせました：
$$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$$
この方程式こそが「決定的な証拠（smoking gun）」です。これは、アルファベットのサイズ $q$ を、2つの根の間の距離に直接結びつけています。

大いなる真実

この方程式と数論の強力なツールを用いることで、ベネットは一連の「不可能」の結果を証明しました：

1. 「小さな素数」の禁止： アルファベットサイズの最大の素因数が13以下である場合、完全な2符号は不可能です。彼は、根になり得るすべての数字のペアを列挙し、それらのどれもがこの方程式に適合しないことを示すことで、これを行いました。
2. 「巨大な数」の障壁： アルファベットが $2^\alpha \times p^\beta$ である一般的なケースにおいて、もしコードが存在するならば、素数 $p$ は $10^{10}$（100億）よりも大きくなければならないことを証明しました。さらに厳しく言えば、2のべき乗（$\alpha$）は20よりも大きくなければなりません。
3. 「Mod 8」の規則： もしそのようなコードが存在するならば、素数 $p$ は8で割ったときに3の余りとなる数（3, 11, 19など）でなければなりません。

この論文は次のように述べています。「私たちは小さな数を確認しましたが、それらは機能しませんでした。大きな数の場合、数学によれば、それらはあまりにも巨大であり、かつ非常に厳格なルールに従わなければならないため、実質的に存在しないも同然です。」

シュレーダー・ヒパラクス・サプライズ

この論文の最も愉快な部分の一つは、古典的な組合せ論におけるシュレーダー・ヒパラクス数（スーパー・カタラン数とも呼ばれる）という数列をどのように使用しているかです。これらの数は、括弧の配置方法やグリッド上の経路の数を数える問題によく現れますが、突然、誤り訂正符号の証明の途中に登場します。

ベネットは、これらの数を用いて複雑な方程式を展開しました。それは、混沌としたノイズの中に隠れたパターンを見つけるようなものです。この数を用いて方程式を展開することで、もし関与する数が途方もなく大きくない限り、完全なコードに求められる「近接性」を許容できないほど、項が急速に増大することを示せたのです。

最終的な判決

では、結論は何でしょうか？ この論文は、数学界の長年の疑念を裏付けています。すなわち、任意のアルファベットにおける完全な2符号はおそらく存在しないということです。

この論文は、宇宙に隠れているかもしれない「唯一の完全なコード」を見つけたと主張しているわけではありません（なぜなら、もし存在するとしても、それは $10^{10}$ よりも大きく、不可能な制約に従わなければならないことを証明しているからです）。しかし、事実上、大部分のケースを排除しています。10、15、21といったアルファベットサイズへの扉を閉ざし、その可能性を、実質的に存在しないと考えられるほど巨大な数の領域へと押しやっています。

著者の仕事は、「負の証明」の勝利です。宝物を見つける代わりに、彼は宝箱が空であること、あるいは少なくとも、それを開けるための鍵にはまだ発明されていない錠前が必要であることを証明したのです。これらの特定のアルファベットサイズに対して誤り訂正符号を構築しようとしている人々にとって、メッセージは明確です。完全な2符号を探すのはやめなさい。そこには存在しません。