Counterexamples to Charpin's Conjecture on BCH codes

あなたは、嵐の中で友人にレシピを叫んでいるような、ノイズの多い無線通信路を通じて秘密のメッセージを送っているところを想像してみてください。メッセージの単語が吹き飛ばされたり、かき乱されたりしても正しく届くように、メッセージに余分な「安全ワード」を加えます。デジタル通信の世界では、これらの安全網は「誤り訂正符号」と呼ばれています。これらは、スマートフォンのデータストレージから深宇宙探査機の衛星通信に至るまで、あらゆる場面で支えとなっている、最も有名で強力な符号の一族である「BCH符号（発明者の名前から命名）」です。

数学者やエンジニアを数十年にわたって悩ませてきた大きな疑問があります。それは、「これらの符号は、エラーを修正する能力が一体どれほど高いのか？」という問いです。これを測定するために、私たちは「最小距離」という指標を用います。これは、その符号が確実に検知・修正できるエラーの最小数です。「ボーズ距離（Bose distance）」と呼ばれる有名な経験則があり、これはこの数値の安全で保守的な推定値を与えてくれます。長い間、専門家たちは、これらの符号の真の能力は、この安全な推定値よりも決して「大幅に」高くはないと考えてきました。彼らは、この「安全な推測」と「真の能力」の間の差は、スピードメーターが示す速度より常に時速4マイル程度しか速くない車のように、極めて小さく予測可能なものだと信じていたのです。この信念は非常に強固であり、「シャルピンの予想（Charpin's conjecture）」として知られる有名な仮説となりました。もしこの予想が正しいとすれば、単純な計数を行うだけで、これらの符号がどのように機能するかを正確に予測できることを意味します。

しかし、もしその予想が間違っていたらどうでしょう？ もし、特定の条件下において、これらの符号が驚くほど強化され、誰もが予想していたよりもはるかに多くのエラーを修正できるとしたら？ 実は、研究チームがまさにそれを発見したのです。彼らは単に小さな例外を見つけたのではありません。ルールを完全に打ち破る、全く新しい符号の一族を発見したのです。彼らは、この「安全な推測」と「真の能力」の間の差が、単に少し大きくなるだけではないことを証明しました。コードが大きくなるにつれて、その差は巨大になり続けるのです。実際、特定の符号においては、真の能力は旧来の推測をはるかに上回り、経験則が完全に崩壊してしまいます。これは単なる小さな修正ではありません。デジタル的な安全網の仕組みに関する理解における根本的な転換であり、自然界には私たちが想像していたよりもずっと多くの仕掛けが隠されていることを示しています。

大きな発見： 「4エラー」のルールを破る

本論文において、著者であるRun Zheng、Yaoran Yang、Yutong Zhang、およびMaosheng Xiongは、これらのBCH符号の限界をテストすることを目的としました。彼らの主な目的は、ボーズ距離と実際の距離の差は常に小さい（具体的にはバイナリ符号において4を超えない）という「シャルピンの予想」が、本当に正しいのかを検証することでした。

彼らの手法を理解するために、BCH符号を一つの「要塞」として想像してみてください。「ボーズ距離」は、誰もが合意している外壁の高さのようなものです。「最小距離」は、要塞内にある最も強固な地点の実際の高さです。長年、人々はその最も強固な地点が、合意された壁よりも数フィート高いことは決してないと想定してきました。しかし、著者たちは、この要塞の中に隠された、より高い塔へと続く秘密の入り口を探すことに決めたのです。

彼らは、「一般化リード・マラー符号（Generalized Reed-Muller codes）」と呼ばれるものを用いた巧妙な数学的トリックを使用しました。これらは、メッセージの「重み（またはサイズ）」について非常に厳格なルールを持つ、別の種類の符号だと考えてください。著者たちは、彼らが扱う特定のBCH符号が、実はこれらのより厳格な符号の中に隠れていることを示しました。この「親」となる符号の厳格なルールのために、BCH符号内のメッセージは、標準的な壁の高さが示唆するものよりも、はるかに「重く（＝より多くのエラーに対処できる）」なるよう強制されるのです。

結果はどうなったでしょうか？ 彼らは、真の最小距離がボーズ距離よりも厳密に大きい、無限の符号の一族を構築しました。実際、特定のパラメータ（符号長が$m \ge 10$かつ$m \neq 12$である数に関連する場合）において、その差は単なる「4」のような小さな数字ではありません。コードが長くなるにつれて、その差は著しく拡大していきます。

例えば、$m=13$に関連する長さ（これは符号長が8191であることを意味します）を持つバイナリ符号（ほとんどのコンピュータで使用される種類）を考えてみましょう。このとき、推定距離と実際の距離の差は $2^{\lfloor(13-1)/3\rfloor-1}$ となります。これは、差が8であることを計算しており、すでにシャルピンの予想が許容した限界の2倍に達しています。しかし、コードを大きくしていく（$m$を増やしていく）と、この差は単に8にとどまるのではなく、急速に拡大していきます。その差は符号長の立方根として成長するため、非常に大きな符号においては、真の能力は旧来の推定値を圧倒的に凌駕することになります。

なぜこれほど長く隠されていたのか？

「これほど重大な発見なら、なぜ今まで誰にも見つからなかったのか？」と疑問に思うかもしれません。著者らは、彼らが見つけた最小の反例には、符号長8191が必要であったと説明しています。予想の形成に役立てられた従来のコンピュータ探索では、511までの長さの符号しかチェックしていませんでした。それは、ネズミがいっぱいいる部屋の中で巨大なゾウを探しているようなものです。ネズミだけを見ていたら、ゾウを見ることは決してできないのです。彼らが発見した現象は、あまりにも巨大であるため、初期の小規模な実験では捉えることができなかったのです。

結論

本論文は、シャルピンの予想を決定的に覆しました。原始的短距離BCH符号の最小距離は、ボーズ距離の上方に固定された小さな数によって制限されるのではないことを示しています。むしろ、その差はコードが長くなるにつれて任意に大きくなり得ます。

著者らは単に推測したのではなく、厳密な数学的証明を提供しました。彼らは符号を構築し、正確な距離を計算し、その差が実在し、かつ重大であることを示しました。バイナリ符号については、その差が彼らの公式と正確に一致することも証明しており、疑いの余地を残していません。

この発見は、符号理論の景観を変えるものです。これは、これらの符号の性能を予測するために、単純な固定境界に頼ることはできないということを教えてくれます。代わりに、私たちはこれらの符号の中に隠された「塔」を求めて、より深く掘り下げなければなりません。なぜなら、デジタルな守護者であるこれらの符号の真の誤り訂正能力は、私たちがかつて望んでいたよりも、はるかに素晴らしいものだからです。