エルデシュと確率論的手法：偶然によって存在を証明する

エルデシュには家がなく、普通の意味での職もなく、ほとんど持ち物もなかった。彼はスーツケースを携えて大学から大学へと旅をして生涯を過ごし、同僚の玄関先に「私の脳は開いている」という言葉とともに現れては、数学者たちが今日もなお取り組み続ける定理と未解決問題の流れをあとに残していった。彼が生み出したあらゆるもののなかで、ひとつの発想が、証明のあり方そのものを変えたという点で際立っている。それは確率論的手法と呼ばれ、その核心には、ほとんどずるのように聞こえる一手がある。何かを構成することを拒むことによって、それが存在すると証明するのだ。

問い：秩序はいつ避けられないのか

単純そうに聞こえるパズルから始めよう。6人のパーティーでは、どの2人も友人か他人かのどちらかである。すると、どんな6人のなかにも、互いに全員が友人である3人か、互いに全員が他人である3人を必ず見つけられることがわかる。秩序が自らを現すよう強いるのだ。これがいつ起こらざるを得ないのかを研究する数学の分野がラムゼー理論であり、この問いに一つの数を結びつける。

ラムゼーの定理はこうした数が存在することを保証するが、それがどれほど大きいかは語らない。自然な続きの問いはこうだ。大きさ k のいかなる単色クラスターも避けながら、グループはどこまで大きくなれるのか。それに答えるには、そうした巧みな塗り分けが存在することを証明しなければならない。そしてまさにここで、それを手作業で構成するのは絶望的になる。可能な塗り分けの数が天文学的だからだ。

エルデシュの一手：構成するな、数えよ

1947年のエルデシュの洞察は、良い塗り分けを設計しようとするのをやめ、代わりに完全に無作為に塗り、あとは計算に仕事をさせることだった。その議論は、最後まで追えるほど短い。

最後のステップをもう一度読んでほしい。そこにこそ魔法のすべてがあるからだ。私たちは良い塗り分けを一度も作り出さなかった。一つも記述しなかった。平均的な塗り分けが欠点のなさにあまりに近いため、完璧なものが山のどこかに存在せざるを得ないことを示したのだ。この証明は、どの対象も特に指し示すことなく、特定の対象についての確実性を手渡してくれる。

なぜこれは革命的だったのか

エルデシュ以前、何かが存在することを証明するとは、ほとんどつねにそれを構成すること、あるいは少なくともそれを作り出す手順を記述することを意味していた。確率論的手法はその前提を打ち破った。それは、偶然性そのものが証明として役立ちうることを確立した。ランダムな試みがゼロより大きい何らかの確率で成功するなら、成功は可能なのだ、それで終わり、というわけだ。

この非構成的な趣は、この議論を数学のもっとも優美な結果のいくつかと同じ系譜に位置づける。カントールの対角線論法もまた、明示的な構成ではなく純粋な論理の力によって、何かの存在を、つまりいかなるリストにも欠けている数の存在を証明する。両者はあの静かで、ほとんど不安にさせるほどの力を共有している。約束したものを決して見せないにもかかわらず、結論は水も漏らさぬのだ。ここでの偶然性は、確率を直観的に理解するで扱われているのと同じ基盤の上に成り立っている。そこでは、ステップ3のエンジンである期待値の考えが、一から組み立てられている。

エルデシュの問題と、その AI の時代

エルデシュは定理を証明しただけではない。彼は問題を、それも何百もの問題を提起し、しばしば小さな賞金をつけた。それは厄介な練習問題に対する数ドルから、本当に深いと信じる問いに対する数千ドルにまでおよんだ。そうした問題の多くは今もなお未解決であり、erdosproblems.comで丁寧に整理・維持されている。

その禅

確率論的手法が美しいのは、良い手品が美しいのと同じ理由による。あなたはどのステップも見ているのに、だまされた箇所を見つけられず、それでいて結果はやはり不可能に感じられる。手品の仕掛けはない。期待値は本当に1を下回っているし、自らの平均を下回る整数は、本当にどこかで0まで落ち込まなければならない。確実性は完全で、構成は不在で、その両方が同時に真なのだ。

これこそ、エルデシュが残していった末永い教訓だ。存在と構成は同じものではない。完璧な対象がそこにあると知るためのもっとも清らかな道は、平均的な対象がほとんど完璧であることを証明し、その隔たりに残りを任せることだ、という場合があるのだ。無関係に見える考えを一本の線が結びつける別の結果については、オイラーの等式が逆の種類の美しさを差し出してくれる。エルデシュが数え上げから存在を呼び起こすところで、オイラーは一つの正確で必然的な数を突き止めるのだ。