New lower bounds for constant-weight codes via seeded bit-swap tabu search

想像してみてください。あなたはスーツケースに荷物を詰めようとしていますが、非常に奇妙なルールがあります。それは、詰め込むすべてのアイテムが全く同じサイズでなければならず、かつ、どの2つのアイテムも似すぎていてはいけないというルールです。もし似すぎていたら、暗闇の中で混ざり合って混乱を招く可能性があるからです。デジタル通信の世界では、この「スーツケース」はメッセージであり、「アイテム」は0と1のパターン（ビット）です。そして「サイズ」とは、そのパターンに含まれる1の数です。このパズルが「定数重み符号（constant-weight codes）」です。科学者たちは、Wi-Fiや深宇宙無線のようなノイズの多い通信路でデータを確実に送るために、これらの符号を使用します。これにより、たとえ数ビットが乱されても、受信側が送られた内容を正しく判別できるようにしています。目標は単純ですが、非常に困難です。つまり、いかに多くのユニークで区別可能なアイテムを、互いにぶつかることなくスーツケースに詰め込めるかということです。スーツケースが大きければ大きいほど（より多くのコードを詰め込めるほど）、一度に送れる情報量は多くなります。

ウィリアム・エコールズ（William Echols）は、巧妙なひねりを加えて、このパッキングの問題に取り組むことにしました。空のスーツケースから始めて、アイテムがうまく収まることを願いながらランダムに投げ入れるのではなく、彼は「シード（種）」を用いたアプローチを採用しました。これは次のように考えることができます。もし、より優れたレゴのお城を作りたいなら、ゼロから作り始めるのではなく、既存の素晴らしいお城を使い、いくつかのブロックを取り出し、それらを入れ替えて、さらに大きく、あるいはより頑丈にできるかどうかを試すのです。エコールズは、**タブー探索（tabu search）**と呼ばれるコンピュータ手法を用いました。これは、足跡を辿ってループに陥ることを拒む（足踏み状態を避けるため）、非常に頑固な探検家のようなものです。彼は、既存の高品質なコード設計を「シード」として用いることで、探索を導きました。その結果、これまで発見されていなかった、より大きな124個の新しいパッキング配置を見つけ出しました。これらの新しい配置は、私たちが一度に送れるメッセージの数の下限値を改善し、さらには高次元空間において中心にある球体にどれだけの数の球体が接することができるかという概念、すなわち「キッシング数（kissing numbers）」についても理解を深めてくれます。

パッキングのパズルと魔法の種

デジタル世界では、データは単なる0と1の長い文字列に過ぎません。時として、堅牢性を高めるために、特定の数の1を持つ文字列のみを許可することがあります。例えば、「重み」が5であると言った場合、すべての文字列は正確に5つの1を持たなければなりません。ここで、あなたがこれらの文字列のコレクションを持っていると想像してください。エラーを防ぐために、コレクション内のすべての文字列は、他のすべての文字列と十分に異なっていなければなりません。もし2つの文字列が似すぎていると、わずかなノイズによって一方が他方に変わってしまい、受信者が混乱してしまう可能性があります。文字列間の「距離」は、どれだけの箇所が異なっているかによって測定されます。

この分野における大きな疑問は、**「あなたのコレクションの中に、最大でいくつの文字列を詰め込めるか？」**ということです。この最大数は、$A(n, d, w)$ と表記されます。ここで、$n$ は文字列の長さ、$d$ は必要な最小距離、$w$ は1の数です。数十年にわたり、数学者やコンピュータ科学者は、様々な設定における最大のコレクションを見つけ出そうと試みてきました。彼らは優れたコレクションを見つけてきましたが、それが絶対的な最大であるかどうかを知らないことも多いのです。彼らに分かっているのは、これ以上はできないという限界値だけです。

「シード」戦略

これらの最大値を見つけようとするこれまでの試みは、コンピュータによる探索を用いていましたが、それはしばしば暗い森の中を彷なるようなものでした。コンピュータはランダムな推測からスタートし、時には良い経路を見つけることもありましたが、多くの場合、局所的な開けた場所に捕まってしまいました。そこが山の頂上であるように見えても、実際にはそうではなく、そのすぐ隣の丘の向こうにずっと大きな山があるということも知らずに、彼らはそこで立ち止まってしまうのです。

エコールズは、ゼロから始めるのをやめることが鍵であると気づきました。彼は**「シード初期化（seeded initialization）」**というテクニックを用いました。ランダムな開始点を生成する代わりに、既存の高品質なコード（「シード」）を取り出し、それを探索の出発点として使用したのです。

彼はこれを、2つの遊び心のある方法で行いました。

1. ダイレクト・シーディング（直接的な種まき）： 既存のコードを取り出し、トラブル（距離の不足）を最小限に抑えるように注意深く選ばれた、1つの余分な単語を追加しました。これにより、少し大きく、少し乱れた開始点が作成されました。
2. ネイバー・シーディング（近傍の種まき）： 彼は、わずかに異なる問題に対するコードを調べました。例えば、長さが30のコードが必要な場合、長さ29の優れたコードを取り出し、すべての単語に0を1つ追加して長さを30にし、それを開始点として使用します。あるいは、長さ31のコードを取り出し、0を1つ削って使用することもあります。

これらの「シードされた」開始点を得た後、彼は**ビット・スワップ・タブー探索（bit-swap tabu search）**を実行しました。この探索を、文字列の中の1の位置が椅子の役割を果たす「椅子取りゲーム」だと想像してください。アルゴリズムはビットを入れ替え、文字列をより際立たせようと試みます。「タブー」の部分とは、アルゴリズムが直前に行った動きを記憶し、それをすぐに元に戻すことを拒否することを意味します。これにより、円を描いてぐるぐる回るのではなく、新しい領域を探索することを強制します。

結果：124の新しい発見

このスマートなシード戦略を用いることで、エコールズは従来の最高記録を塗り替える124個の新しい構成を見つけ出しました。これらは単なる小さな改善ではありません。中には劇的な飛躍もあります。

例えば：

• 長さ39で特定の制約があるコードの場合、これまでの最高記録は1,014語でした。新しい手法は1,118語を見つけました。これは104の増加です！
• 長さ40の場合、記録は1,170から1,230へと跳ね上がりました。
• 長さ56の場合、数は2,414から2,477へと増えました。

これらの数字は、特定の条件下で、混乱なく送ることが確実にできるユニークなメッセージの最大数を表しています。この論文は、これらが真の数学的限界（絶対的な最大値）であると主張しているわけではありませんが、これよりも確実に優れたものが存在することを証明しています。これは「下限（lower bound）」を押し上げるものであり、つまり、少なくともこれだけのアイテムをスーツケースに詰め込めることが確実になったことを意味します。

キッシング数：驚くべき副作用

物語はここでさらに面白くなります。この論文は、**キッシング数（kissing numbers）**と呼ばれる概念にも触れています。部屋の中央に巨大なボールがあると想像してください。中央のボールに重なり合うことなく、かつ中央のボールに接するように、同じサイズの他のボールをいくつ配置できるでしょうか？3次元空間では、その答えは12です。しかし、高次元（例えば32次元や33次元）では、その答えを見つけることははるかに困難です。

これらのキッシング数の数学は、エコールズが見つけた定数重み符号と深く結びついています。彼が特定のパラメータ（具体的には $A(n, 8, 8)$）に対してコードを改善したことにより、自動的に32、33、34、および37次元におけるキッシング数の下限値も向上しました。

例えば、次元32（$\tau_{32}$）について、以前の推定では、少なくとも345,408個のボールが中央のボールに接することができるとされていました。新しいコードを用いることで、その数は346,432へと跳ね上がりました。これはわずかなパーセンテージの増加ですが、高次元幾何学の世界では、もう一つボールが収まる場所を見つけることは、大きな勝利なのです。

まとめ

ウィリアム・エコールズは、単に優れたコードをいくつか見つけただけではありません。彼は、盲目的に探索を始めるのではなく、既存の知識から「種」を利用するという、いかに賢明な開始方法をとるべきかを示したのです。この論文は、124の具体的な改善が可能であることを証明しており、これらのデジタル文字列の中に、どれだけのデータを確実に詰め込めるかという新しい、より高い底上げを与えてくれました。これは、時には、ゼロからすべてを構築しようとするよりも、すでに知っていることの上に立つことが、前進するための最善の方法であるということを思い出させてくれます。