A counterexample to the Etzion-Silberstein conjecture

あなたは、ライトスイッチのグリッドを用いて、最も効率的なストレージ・システムを構築しようとしている熟練の建築家であると想像してください。デジタル通信の世界において、これらのグリッドは「コード」と呼ばれ、あなたのテキストメッセージや写真、動画がインターネットを移動する際に、かき乱されるのを防ぐ目に見えない守護者となります。目標は常に同じです。情報の損失を防ぐ能力を維持しながら、いかに多くの情報をそのグリッドの中に詰め込むかです。

何十年もの間、数学者たちは、フェラー図（階段状やブロックのピラミッドのような形をした図）におけるスイッチの配置に関する特定のパズルを解こうとしてきました。彼らは、どのような階段状の形状であっても、エラーを修正する能力を失うことなく、どれほどの情報が収まるかという理論的な「速度制限」を発見しました。この限界は、シングルトン境界（Singleton bound）と呼ばれます。2009年、二人の優れた数学者、エツィオンとシルバーシュタインは、大胆な推測をしました。彼らは、あらゆる可能な階段状の形状とあらゆる種類の誤り訂正ルールに対して、常にこの速度制限に正確に一致する「完全符号（perfect code）」を構築できるはずだと考えたのです。それはまるで、「どんな形の収納ボックスであっても、一滴もこぼさずに、常に満杯まで詰め込むことができる」と言っているようなものでした。このアイデアは一つの予想となり、より優れた誤り訂正符号を設計しようとする研究者たちの導きの星となりました。

しかし、ジテンドラ・プラジャパティによる新しい論文が登場し、その星を優しく、しかし断固として消し去りました。著者は、エツィオン＝シルバーシュタイン予想は実は間違っていることを証明したのです。特定の、奇妙な形の階段状のブロックを用いて、この形状では理論上の限界まで満一杯にすることは不可能であることを示しました。予測された12ユニットの情報量ではなく、可能な最大値は11なのです。これは、12枚のシャツが入るはずのスーツケースをパッキングするようなものです。満杯だと思って詰め込んでも、12枚目のシャツを押し込もうとすると、ジッパーが閉まらなかったり、生地が破れたりしてしまうのです。この論文は単に推測しているのではなく、大規模なコンピュータ検証による数学的証明を用いて、この特定の形状に対して12番目のユニットが数学的に不可能であることを示しています。

物語は、$E$ と呼ばれる図形から始まります。これは、5つのブロックを持つ4つの高い列と、1つのブロックを持つ2つの短い列で構成された階段状の図形です。ゲームのルールでは、この図形に書き込まれる「メッセージ（スイッチのパターン）」は、特定の「最小ランク距離（minimum rank distance）」、具体的には3のダメージに耐えられるほど強力でなければなりません。これは、ある有効なメッセージを別のものに変えるためには、少なくとも3つの異なる部分を変更しなければならないという要件です。古い理論に基づけば、この形状には12個の独立したメッセージを収めることができるはずでした。

しかし、著者はこれらのコードの構造を深く掘り下げ、隠れた罠を見つけ出しました。限界がより低いことを証明するために、論文は問題を「カーネル・リフト（kernel-lift）」のパズルへと分解します。巨大で複雑な機械（コード）を、より小さな核となるエンジン（より小さなコード）へと縮小しようとしていると考えてください。論文は、もし12メッセージの完全符号が存在するならば、それはMRDコードと呼ばれる非常に特定のタイプのエンジンに基づいている必要があることを示しています。既知のMRDエンジンのタイプは3種類しかありません。著者は、これらのパーツがどのように組み合わさるかの全容を調べるために、800万通り以上のバリエーションをチェックするという大規模な徹底調査を実行しました。

結果は、明白な「ノー」でした。コンピュータはあらゆる可能性をチェックしましたが、すべての場合において数学が破綻しました。「エンジン」は、ゲームのルールに違反することなく、12番目のメッセージの重みに耐えることはできなかったのです。論文は、この形状に対する12次元のコードの存在を明確に否定しています。代わりに、著者は11のメッセージを持つ動作可能な例を構築し、11こそが真の最大値であることを証明しました。これはシミュレーションや推測ではなく、独立したソフトウェア検証器によってダブルチェックされた、厳密でステップ・バイ・ステップの証明です。

論文はここで止まりません。また、「行錐伝播（row-cone propagation）」と呼ばれる巧妙なトリックも発見しました。失敗した12ブロックの階段状の図形を取り上げ、その上に新しい層を加え、さらに横にいくつかのブロックを加えることを想像してください。論文は、もし元の形状を完璧に満たすことができないのであれば、これらの新しい、より大きな形状を完璧に満たすこともできないことを示しています。つまり、この失敗は一度限りの偶然ではないということです。最小距離が3以上であるあらゆる複雑さのレベルにおいて、理論上の限界が12でありながら、実際には11に留まってしまう階段状の形状が存在するのです。

結局のところ、この論文は数学的知識の地図に対する重要な修正です。エツィオン＝シルバーシュタインの境界は優れたガイドラインではありますが、あらゆる形状に対して成立する自然法則ではないことを教えてくれます。「完璧なパッキング」は常に可能なわけではありません。著者は、最善のコード（次元11）の正確な設計図を提供し、次元12という夢が、これらの特定の図形に対しては数学的に不可能であることを証明しました。これは、抽象的な数学の世界において、たとえ最も優雅な推測であっても例外があり、時には真実が、私たちが望んだものよりもほんの一ブロック分だけ少ないことがあるということを思い出させてくれます。