数学者が「二段ベッド予想」を覆した

この物語 のオリジナル版はQuanta Magazineに掲載されました。

数学の多くは直感、つまり何が真実であるべきかという根深い感覚によって動かされます。しかし、時に直感は数学者を誤った方向に導くことがあります。初期の証拠は全体像を反映していないかもしれませんし、一見明白に思える命題が、後になって隠れた微妙なニュアンスを明らかにすることもあるでしょう。

意外なことに、3人の数学者が、確率論におけるよく知られた仮説「二段ベッド予想」がこのカテゴリーに該当することを示しました。グラフと呼ばれる数学的な迷路を二段ベッドのように積み重ねた際に、グラフを様々な方法で探索できるというこの予想は、一見自然で、自明とさえ思えました。「私たちの脳が伝えるものはすべて、この予想が正しいことを示唆しています」と、プリンストン大学のグラフ理論学者で、今回の研究には関わっていないマリア・チャドノフスキー氏は述べています。

しかし、彼らは間違っていました。先月、3人の数学者が反例を発表し、この予想を反証しました。この結果は、固体物質の性質に関する物理学の関連問題へのアプローチに新たな指針を与えるものです。しかし同時に、数学の仕組みに関するより深い疑問にも触れています。予想が正しいことを証明するために、多くの数学的努力が費やされています。予想を覆そうとするのは、より孤独な作業です。この新しい研究の背後にあるチームは、最終的に反例を見つけるまで何度も失敗しました。彼らの物語は、数学者が自分の仮定をもっと頻繁に疑う必要があることを示唆しています。

グラフ上のグラフ

1980年代半ば、オランダの物理学者ピーター・カステラインは、多孔質固体中を液体がどのように流れるかという仮説を数学的に証明しようと試みました。彼の研究は、二段ベッド予想を提唱するに至りました。

これを理解するには、グラフから始めます。グラフとは、線またはエッジで接続された点または頂点の集合です。

次に、グラフの正確なコピーを作成し、元のグラフの真上に配置します。それらの間に垂直の柱をいくつか描きます。これは、下のグラフの頂点と、上のグラフの対応する頂点を結ぶ追加の辺です。こうすることで、二段ベッドのような構造が完成します。

次に、下のグラフの辺を考えてみましょう。コインを投げます。表が出たら辺を消し、裏が出たら辺を残します。両方のグラフのすべての辺に対して、この手順を繰り返します。下の二段ベッドと上の二段ベッドは見た目は異なりますが、垂直の支柱で繋がっていることは変わりません。

最後に、下のグラフから2つの頂点を選びます。グラフの辺をたどって、片方の頂点からもう一方の頂点まで移動できますか？それとも、2つの頂点は切断されていますか？どんなグラフでも、経路が存在する確率を計算できます。今度は同じ2つの頂点に注目し、片方の頂点について、上のグラフでその頂点の真上の頂点までジャンプしてみましょう。下のグラフの開始頂点から上のグラフの終了頂点まで、経路は存在するでしょうか？

二段ベッド予想とは、下段のベッド上の経路を見つける確率は、上段のベッドにジャンプする経路を見つける確率と常に同じかそれ以上であるというものです。どのようなグラフから始めるか、二段ベッドの間に何本の垂直の柱を引くか、あるいはどの始点と終点を選ぶかは関係ありません。

数学者たちは何十年もの間、これが真実であるに違いないと考えていた。彼らの直感は、一つの二段ベッドの上を移動する方が二つの二段ベッドの間を移動するよりも容易であるはずだ、つまり、下の二段ベッドから上の二段ベッドへ移動するために必要な垂直方向のジャンプが、利用可能な経路の数を大幅に制限するはずだと告げていた。

数学者たちは、二段ベッド予想が成り立つことを望んでいました。これは、グラフからランダムに辺を削除した後に生じる経路やクラスターを扱うパーコレーション理論と呼ばれる分野の命題群に属します。これらのグラフは、スポンジの中を水が移動するのと同じように、多孔質材料中を流体がどのように移動、つまり浸透するかを簡略化したモデルと考えることができます。一方、二段ベッド予想は、流体が固体中を移動する確率に関する、物理学で広く信じられている仮定を示唆するものです。また、パーコレーションの物理学に関する関連問題の解決方法も示唆するでしょう。

しかし、それは二段ベッド予想が正しいと誰かが証明できた場合にのみ実現する。誰も証明できなかったのには理由があった。

おそらく間違っている

カリフォルニア大学ロサンゼルス校の数学者、イゴール・パクは、二段ベッド予想の真偽について常に疑念を抱いていた。「彼は最初から懐疑的だった」と、彼の大学院生の一人、ニキータ・グラドコフは言う。「彼は古い予想を全く信じない人だ」。パクは、数学者がそうした予想の証明に注力する傾向を声高に批判してきた。彼は、「もし予想がすべて間違っていたらどうなるだろうか？」という問いかけからも、同様に重要な進歩が生まれると主張している。

パクが二段ベッド予想を疑ったのには、特別な理由があった。それは、あまりにも広範な主張に思えたからだ。彼は、それが本当に考えられるあらゆるグラフに当てはまるのか疑問に思っていた。「予想の中には、実質的な根拠に基づいたものもあれば、希望的観測に基づいたものもあります」と彼は言った。二段ベッド予想は後者のように思えた。

2022年、彼はそれを反証しようと試みた。1年間、何度も試行錯誤を繰り返した。その後、グラドコフにコンピューターを使い、あらゆるグラフを網羅的に総当たり方式で探索するよう指示した。この作業には高度なプログラミングが必要だと悟ったグラドコフは、高校時代からの友人で、現在マサチューセッツ工科大学の大学院生であるアレクサンドル・ジミンに協力を求めた。「私たちは大学時代、実際にルームメイトでした。寮にはちゃんとした二段ベッドがありました」とグラドコフは語った。

グラドコフ、パク、ジミンは、9頂点未満のグラフを全て手作業で検証することができました。これらのケースでは、二段ベッド予想が成り立つことを検証できました。しかし、より大きなグラフになると、考えられる状況の数が爆発的に増加しました。辺が削除される可能性やパスが形成される可能性をすべて考慮することは不可能でした。

研究チームは次に機械学習に着手した。ニューラルネットワークを訓練し、上段へのジャンプを優先する可能性のある迂回路を持つグラフを生成させた。生成された多くの例において、下段へのジャンプが上段へのジャンプよりもほんのわずかに確率が高いことがわかった。しかし、モデルは逆のグラフを発見することはできなかった。

もう一つ問題がありました。ニューラルネットワークが生成したグラフはどれも依然として大きすぎたため、数学者たちがコイン投げのステップにおけるすべての結果を調査することは不可能でした。チームは、結果のサブセットにおいて、上側のパスと下側のパスを見つける確率を計算する必要がありました。これは、世論調査が選挙結果を予測するために有権者のサブセットからサンプルを抽出しているのと似ています。

数学者たちは、ニューラルネットワークが提示する反例に対して99.99%以上の確信を持てるものの、100%ではないことに気づいた。彼らは、このアプローチを追求することで報われるかどうか疑問に思い始めた。数学コミュニティを納得させる可能性は低く、権威ある学術誌がこれを厳密な証明とみなすはずもなかった。「博士課程の学生には理論ではなく現実の仕事が必要だ」とパクはブログに記した。そしてグラドコフとジミンも間もなく仕事を探すことになるだろう。「だからこそ私たちは研究をやめたのだ」と彼は続けた。「何か他のことを試せばいいのに、なぜ諦めて論争を起こす必要があるのか​​？」

彼らは計算論的アプローチを諦めたが、問題について考えることをやめなかった。その後数ヶ月間、彼らはコンピューターを必要としない理論的議論を組み立てることに集中した。しかし、それを完成させるために必要なすべての要素が揃っていたわけではなかった。

その後、海外から突破口がもたらされた。

コンピューターが必要な人は誰ですか?

6月、ケンブリッジ大学のローレンス・ホロムは、二段ベッド問題のあるバージョンを別の文脈で反証しました。この予想の定式化では、グラフではなく、ハイパーグラフと呼ばれるオブジェクトについて問われました。ハイパーグラフでは、辺はもはや2つの頂点間の接続として定義されるのではなく、任意の数の頂点間の接続として定義されます。

ホロムはこの予想の反例を発見した。彼は、3つの頂点をそれぞれ辺で結ぶ小さなハイパーグラフを作成した。

グラドコフは偶然その論文を見つけ、まさに3人が求めていたものだと悟った。「夕方に見つけて、午前3時まで読みました。『わあ、これはすごい。本当に信じられない』と思いました」と彼は言った。彼は寝る前にジミンにテキストメッセージを送り、翌日2人は電話で話した。ホロムの反例を、元の二段ベッド予想を反証する正規グラフに書き換えることができるだろうか？

旧友である二人がハイパーグラフをグラフに変換する方法について考えたのは、これが初めてではなかった。昨年の初め、二人は一緒にコンサートに行く直前にこの問題について話し合った。「レッド・ホット・チリ・ペッパーズが歌っている時に、私はこの問題について考えていました」とグラドコフは言った。「当時は音楽をあまり聴いていませんでした。」その後、二人は特定の状況においてハイパーグラフからグラフへと変換できる手法を開発した。

彼らは、これらの手法をホロムのハイパーグラフに適用できることに気づいた。グラドコフ、パク、ジミンは、ハイパーグラフ内の3頂点の辺を、膨大な点群と通常の辺に置き換えた。こうして、7,222個の頂点が14,422本の辺で結ばれた巨大なグラフが完成した。そして、人工知能によるアプローチを放棄した後に構築した理論的議論を用いて、このグラフでは、上側のパスを見つける確率が下側のパスを見つける確率よりも1/10 ^（6,500 %）高いことを証明した。これは想像を絶するほど小さい数字だが、ゼロではない。二段ベッド予想は誤りだった。

プリンストン大学の数学者ノガ・アロン氏は、この結果は何事も当然のことと思わないことの重要性を示していると述べた。「直感的に真実である可能性が高いと思われるものであっても、疑念を持たなければならないのです。」

Gladkov、Pak、Zimin は、この推測を満たす小さなグラフの例を多数発見しましたが、結局のところ、それらのグラフは、十分な頂点と辺が与えられた場合に構築できる、より複雑で直感に反するグラフを反映していませんでした。

ホロム氏はこう言った。「私たちは、自分たちが思っているほど、これらすべてのことを本当に理解しているのだろうか？」

数学者たちは、二段ベッド予想の着想の源となった、立体内の連結位置に関する物理学の命題を今でも信じている。しかし、それを証明するには別の方法を見つける必要があるだろう。

パク氏は、数学者は数学的証明の本質についてより積極的な議論を行う必要があるのは明らかだと述べている。彼と彼の同僚たちは、最終的に物議を醸す計算手法に頼る必要はなく、この予想を完全に確実に反証することができた。しかし、数学研究においてコンピューターやAIをベースとしたアプローチが一般的になるにつれ、一部の数学者は、この分野の規範が最終的に変化する必要があるかどうかについて議論している。「これは哲学的な問題です」とアロン氏は述べた。「高い確率でのみ真となる証明を、私たちはどう見るべきでしょうか？」

「数学の未来は、このような確率論的な証明を受け入れることになるだろう」と、ラトガース大学の数学者ドロン・ザイルバーガー氏は述べた。彼は多くの論文でコンピューターを共著者として認めていることで知られている。「50年後か、もしかしたらそれよりも短い期間で、人々は新たな考え方を持つようになるだろう」

一方で、そのような未来が何か重要なものを脅かすのではないかと疑問を呈する人もいる。「確率論的な証明では、実際に何が起こっているのかについての理解や直感が薄れてしまうかもしれません」とアロン氏は述べた。

パク氏は、この種の研究成果が一般的になってきたら、数学者にとってその価値が失われないよう、専用のジャーナルを創設することを提案している。しかし、彼の主な目標は議論を促すことだ。「正解はありません」と彼は言う。「この種の次の研究成果が評価されるかどうか、コミュニティの皆さんにじっくり考えてもらいたいのです。」テクノロジーが数学に浸透し、変革を続けるにつれ、この問題はますます切迫したものになるだろう。

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