4chanの匿名投稿が25年前の数学パズルの解決に役立った

2011年9月16日、あるアニメファンがオンライン掲示板4chanに、カルト的な人気を誇るテレビシリーズ『涼宮ハルヒの憂鬱』に関する数学の質問を投稿しました。タイムトラベルを題材としたこのアニメの第1期は、当初は時系列順に放送されず、再放送とDVD版でそれぞれエピソードの順序が変更されました。ファンたちはオンラインでエピソードを見るのに最適な順番について議論しており、4chanの投稿者はこう問いかけました。「視聴者があらゆる順番でシリーズを見たい場合、最短で見ることができるエピソードリストは何でしょうか？」

クアンタマガジン

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

1時間も経たないうちに、匿名の人物が答えを提示した。完全な解決策ではないものの、必要なエピソード数の下限を示したのだ。この議論は、エピソード数を問わず、全14話の『ハルヒ』第1期を視聴すれば、すべての可能な順番を確かめるためには少なくとも93,884,313,611話視聴する必要があることを示した。匿名の投稿者は「私が見落としている抜け穴がないか、（証明を）確認してください」と綴った。

この証明は数学界のレーダーに7年間も引っかからずにいました。当時、これに気づいたのはたった一人のプロの数学者で、その人物も綿密な検証を怠ったようです。しかし先月、オーストラリアのSF小説家グレッグ・イーガンが、必要なエピソード数の新たな上限を証明し、物語は大きく動きました。イーガンの発見はこの問題への関心を再び高め、2011年に匿名で投稿された下限値にも注目を集めました。現在、どちらの証明も、数学者たちが少なくとも25年間研究してきた謎の解決に大きく前進したとして、大きな注目を集めています。

数学者たちはすぐにイーガンの上限を検証した。上限は下限と同様に、任意の長さの級数に適用できる。その後、データ視覚化企業Kilnの数学者ロビン・ヒューストンと、ミルウォーキーのマルケット大学のジェイ・パントンが、匿名の4chan投稿者の作業を独立して検証した。「正しいかどうかを判断するのにかなりの労力を要しました」とパントンは述べた。主要なアイデアが明確に表現されていなかったからだ。

現在、ヒューストン氏とパントン氏は、フロリダ大学ゲインズビル校のヴィンス・ヴァッター氏と共同で、正式な論拠をまとめている。論文では、第一著者を「匿名の4chan投稿者」としている。

順列都市

テレビ番組にエピソードが 3 つしかない場合、視聴する順番は 123、132、213、231、312、321 の 6 通りあります。これらの 6 つの順番をつなげて、すべての順番を含む 18 のエピソードのリストを作成することもできますが、それよりもずっと効率的な方法があります。123121321 です。n 個のシンボルの集合のすべての可能な並べ替え (順列) を含むこのような順番は、「スーパー順列」と呼ばれます。

1993 年、ダニエルアシュロックとジェネットティロットソンは、異なる n の値に対する最短の超順列を見ると、階乗に関係するパターンがすぐに浮かび上がることを観察しました。階乗とは、n! の形式で表され、n までのすべての数を掛け合わせた数です (たとえば、4! = 4 × 3 × 2 × 1)。

シリーズが1エピソードのみの場合、最短のスーパー順列の長さは1!（通常の1とも呼ばれます）です。2エピソードのシリーズの場合、最短のスーパー順列（121）の長さは2! + 1!です。3エピソードの場合（上記の例）、長さは3! + 2! + 1!となり、4エピソードの場合（123412314231243121342132413214321）、長さは4! + 3! + 2! + 1!となります。スーパー順列の階乗則は（nのすべての値に対して真であると証明できた人は誰もいませんでしたが）常識となり、後に数学者によってn = 5の場合に確認されました。

そして2014年、ヒューストンはn = 6の場合、このパターンが破綻することを示し、数学者たちを驚かせました。階乗則によれば、6つのエピソードをあらゆる順序で視聴するには873話必要となるはずですが、ヒューストンは872話でそれを実現する方法を発見しました。また、n個のシンボルからなる短い超順列をn + 1個のシンボルからなる短い超順列に変換する簡単な方法があるため、ヒューストンの例は、nが6を超えるすべての値においても階乗則が破綻することを意味しました。

ヒューストンの構築は、スーパーパーミュテーション問題を、複数の都市を通る最短経路を求める有名な巡回セールスマン問題に置き換えることで機能します。より具体的には、スーパーパーミュテーションは「非対称」巡回セールスマン問題と関連しています。この問題では、2つの都市間の各経路にはコスト（必ずしも双方向で同じではありません）があり、すべての都市を通る最も安価な経路を見つけることが目標となります。

翻訳は簡単です。各順列を「都市」と考え、各順列から他の各順列へのパスを想像してください。スーパー順列問題では、すべての順列をリストする可能な限り短い数字のシーケンスが必要なので、目標は、開始順列に追加する数字を可能な限り少なくする方法で順列を通過することです。したがって、各パスのコストは、2 番目の順列を取得するために最初の順列の末尾に追加する必要がある数字の数であると宣言します。たとえば、n = 3 の例では、231 から 312 へのパスは 1 ドルかかります。これは、312 を取得するには 231 の末尾に 2 を追加するだけですむためです。一方、231 から 132 へのパスは 2 ドルかかります。これは、32 を追加する必要があるためです。この設定では、都市を通る最も安価なパスは、最短のスーパー順列に直接対応します。

この翻訳により、ヒューストンは巡回セールスマンアルゴリズムの力をスーパーパーミュテーション問題に応用することができました。巡回セールスマン問題はNP困難問題として有名で、すべてのケースを解ける効率的なアルゴリズムは存在しません。しかし、一部のケースを効率的に解くアルゴリズムや、良好な近似解を生成するアルゴリズムが存在します。ヒューストンは後者のアルゴリズムを用いて、872桁のスーパーパーミュテーションを生成しました。

彼が導き出したのは近似解に過ぎないため、必ずしも最良の超順列ではないかもしれない。パントン氏によると、数学者らは現在、6つの記号を用いた最短の超順列を求める大規模なコンピュータ探索を行っているという。「探索は有限時間で終わることは分かっていますが、それが1週間か100万年かは分かりません」と彼は言った。「進捗状況バーもありません。」

間違った順序

ヒューストン氏の研究が行われた時点で、匿名の4chan投稿はインターネットの片隅に3年近く放置されていた。マウント・アリソン大学の数学者ナサニエル・ジョンストン氏は、投稿から数日後、別のウェブサイトに同じ投稿のコピーが掲載されているのに気づいた。彼がアニメファンだったからではなく、Googleで「超順列」関連の検索ワードをいくつも入力していたからだ。

ジョンストンはその議論を読んで、もっともらしいと思ったものの、綿密に検証する努力はしなかった。当時、数学者たちは超順列の階乗公式はおそらく正しいと考えており、問題の正確な答えを知っていると思えば、下限値はあまり興味深いものではないと考えていた。つまり、超順列研究のエピソードは順序が逆だったのだ。

ジョンストン氏はその後、いくつかのウェブサイトで下限値について言及したが、「特に気に留めた人はいなかったと思う」とヒューストン氏は語った。

そして今年9月26日、カリフォルニア大学リバーサイド校の数学者ジョン・バエズ氏が、ヒューストン氏の2014年の発見についてTwitterに投稿した。これは、一見数学的なパターンに見えるものの実際には当てはまらないという一連のツイートの一部だった。このツイートは、数十年前に数学を専攻し、その後SF小説家として数々の賞を受賞するキャリアをスタートさせたイーガン氏の目に留まった（1994年の画期的な小説は、幸運な偶然にも『順列都市』というタイトルだった）。「私は数学への興味を失っていません」とイーガン氏はメールで述べた。

イーガンは、ヒューストンのものよりもさらに短い超順列を構築できるのではないかと考えました。彼は順列ネットワークを介した短い経路の構築方法に関する論文を文献から探し、数週間後、まさに求めていたものを見つけました。そして1、2日で、n個のシンボルに対する最短の超順列の長さの新たな上限を導き出しました。n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3。これは従来の階乗の公式に似ていますが、多くの項が削除されています。

「これは（これまでの）上限を完全に打ち破った」とヒューストン氏は語った。

一方、匿名の 4chan 投稿者の下限は、新しい上限に非常に近かった。 n! + (n – 1)! + (n – 2)! + n – 3 となる。イーガンの結果が公開されると、ジョンストンは他の数学者に匿名の投稿者の証明を思い出させ、ヒューストンとパントンはすぐにそれが正しいことを証明した。ヒューストンの研究と同様に、新しい下限と上限はどちらも巡回セールスマン問題によって超順列で現れる。下限は、すべての都市を通る経路は、コストが 1 ドルを超える経路を最低限の数通る必要があることを示し、上限は、n ごとに 1 ドルと 2 ドルの接続のみを使用する特定の経路を構築する。

ハルヒファンにとって、イーガンの計算法は、わずか93,924,230,411話で、シーズン1のあらゆる順番で視聴する方法を明確に示したものです。視聴者は今すぐに一気見を始めることもできますし、数学者がこの数を削減できるかどうか様子を見ることもできます。匿名の投稿者が示した下限値は、この削減によって約4000万話以上は節約できないことを示していますが、シーズン2の好調なスタートを切るには十分です。

WIREDのその他の素晴らしい記事