ラムジー理論――「完全な無秩序は存在しない」を証明する数学

この分野が答えようとしていること

「完全な無秩序は不可能である」――ラムジー理論はしばしばこの一文で要約される。十分に大きな構造は、それがどれほど乱雑に作られていても、内部に必ず秩序だった部分構造を含んでしまう。秩序とは、設計して置くものであると同時に、構造が一定の規模を超えたときに強制的に出現してしまうものでもある。それを定理として証明するのが、組合せ論のなかのラムジー理論である。

通俗的な説明と、構造的な分析

十分にランダムに、でたらめに並べれば、そこからパターンや規則性は消える――これが「無秩序」についての通俗的な感覚である。秩序とでたらめは対義語であり、努力してかき混ぜれば秩序は消せる、と私たちは素朴に思っている。

ラムジー理論は、これを正面から否定する。定番の入り口になるのが「パーティ問題」、あるいは「友人と他人の定理」と呼ばれる問いである。

パーティに何人かを集める。どの二人を取っても、その二人は「すでに知り合い」か「初対面」かのどちらかである。このとき問う。互いに全員が知り合いである3人組か、互いに全員が初対面である3人組か、そのどちらかが必ず存在する――それを保証するには、最低何人を集めればよいか。

答えは6人である。5人では保証できない。実際、5人なら、知り合い3人組も初対面3人組も作らずに済む並べ方が存在する。ところが6人になると、誰をどう選ぼうと、どんな知り合い関係になっていようと、必ず「全員が知り合いの3人組」か「全員が初対面の3人組」のどちらかが現れる。例外はない。

証明の考え方は、噛み砕けば追える。6人のうちの一人に注目する。その人から見て、残りの5人それぞれは「知り合い」か「初対面」のどちらかである。5人を2種類に振り分けるのだから、少なくとも3人は同じ種類に入る。これは鳩の巣原理と呼ばれる考え方の一つの現れである。鳩の巣原理とは、ものを箱に分けて入れるとき、ものの数が箱の数より多ければ、必ずどこかの箱に2個以上入る、という原理である。10羽の鳩が9つの巣に入れば、どこかの巣には必ず2羽以上いる。当たり前のことを言っているようだが、この当たり前が、6人のうち少なくとも3人は同じ種類になる、という保証の土台になっている。仮にその同じ種類の3人が、全員「注目した人と知り合い」だったとする。次に、この3人どうしの関係を見る。もし3人のなかに知り合いの組が一つでもあれば、その一組と、最初に注目した人を合わせて、知り合い3人組が完成する。逆に3人のあいだに知り合いの組が一つもなければ、その3人は互いに全員が初対面、つまり初対面3人組が完成している。どちらに転んでも、必ず3人組ができる。逃げ道はない。

これをグラフの言葉に翻訳すると、構造がはっきりする。6つの点を用意し、すべての点のあいだを線で結ぶ。各線を赤か青の2色で塗る。赤を「知り合い」、青を「初対面」とする。すると、どう塗り分けようと、赤い三角形か青い三角形が必ずできる。完全にでたらめに塗ったつもりでも、単色の三角形という秩序が出現してしまう。塗り方の自由をどう使いきっても、秩序からは逃げきれない。

この「保証するのに必要な最小の点数」をラムジー数と呼び、R(3,3) = 6 と書く。一般に R(s,t) は、「s個の点が全部赤でつながった組、またはt個の点が全部青でつながった組を保証するのに必要な、最小の点数」を指す。フランク・ラムジーが1930年に証明したのは、このR(s,t)がどんなsとtに対しても必ず有限の値として存在する、ということだった。無秩序へ逃げ込もうとしても、有限の規模で必ず捕まる。

この見方が見せてくれるもの

第一に、ラムジー数の奇妙な難しさが、この分野に独特の手触りを与えている。定義はこれ以上ないほど単純なのに、具体的な値を求めるのが恐ろしく難しい。R(3,3) = 6 は分かっている。R(4,4) = 18 も分かっている。ところが R(5,5) は、いまだに分かっていない。判明しているのは「43以上48以下のどこか」という範囲だけである。原理的には、43個から48個の点の塗り分けを全部調べれば答えは出るはずだが、その塗り分けの総数が天文学的で、世界中の計算機を動員しても総当たりが終わらない。

数学者ポール・エルデシュが残した有名なたとえがある。はるかに強大な異星人が地球に来て「R(5,5)の正確な値を言え、さもなくば地球を滅ぼす」と迫ったなら、人類は全数学者と全計算機を動員してその値を求めるべきである。しかし、もし異星人が「R(6,6)を言え」と要求してきたなら――人類は異星人を倒す方を選ぶべきだ。それほど、数をわずかに大きくしただけで、問題は手に負えなくなる。

第二に、それでも研究は進む。ラムジー数をぴたりと当てるのが絶望的に難しい一方で、「だいたいどれくらいの大きさになるか」を評価する研究は前進する。2023年、カリフォルニア大学サンディエゴ校のジャック・フェルストラーテとサム・マットフースが、R(4,t)――4個の赤い組、またはt個の青い組を保証する点数――について、90年以上も未解決だった評価を解決した。答えは、おおよそtの3乗に比例する大きさである。この問題は1930年代以来ほとんど進展がなく、二人は解決まで何年もかかったと語っている。注目すべきは、突破口が組合せ論の外から来たことである。有限幾何学に現れる「オナン配置」と呼ばれる擬似ランダムな構造を持ち込んだことが、決め手になった。古い分野に見えて、いまも動いている。

第三に、ラムジー理論は「無秩序」という概念そのものへの反省を迫る。私たちは「十分に乱雑にすれば、パターンは消せる」と思っている。ラムジー理論はそれを否定する。構造が一定の規模を超えると、どんな乱雑化の努力も、ある種の秩序の出現を防げない。秩序は規模の産物でもある、という見方は、パーティの人間関係から、数列の塗り分け、幾何学的な配置まで、さまざまな対象に共通して現れる。パーティ問題は氷山の一角で、「数を有限色で塗り分ければ、必ず等差数列が単色で現れる」というファン・デル・ヴェルデンの定理など、同じ精神の定理が数多く知られている。

第四に、応用もある。ラムジー的な議論――どんなに条件を悪くしても、これだけの構造は必ず残る、という保証――は、通信ネットワークの構造保証、計算機科学における計算量の下限の証明、誤り訂正符号の設計などで使われる。最悪のケースを相手にしなければならない工学にとって、「必ず残る構造」の保証は実用的な意味を持つ。

この分野の弱点・論争点

第一に、計算可能性の壁がある。これは弱点というより分野の本質だが、ラムジー数は小さなものを除いて事実上計算不能で、その状況が今後劇的に改善する見込みは薄い。「存在は証明できるが、値は求まらない」という、数学のなかでも独特の状態が続く。

第二に、証明が「存在」しか語らないことが多い。ラムジー理論の定理の大半は「秩序だった部分構造が必ず存在する」と述べるが、「それがどこにあるか」「どう見つけ出すか」は教えてくれない。存在を示す証明と、実際に構成してみせる証明のあいだのギャップが、この分野では特に大きい。鳩の巣原理がまさにそうで、「同じ箱に2個入る」ことは保証するが、それがどの箱かは言わない。

第三に、上界と下界の隔たりが大きい。多くのラムジー数について、「これ以上」という下からの評価と「これ以下」という上からの評価のあいだに、大きな開きが残っている。2023年のR(4,t)の進展も、この隔たりを詰めた成果だが、R(5,5)のような基本的な数ですら、依然として範囲でしか分かっていない。

第四に、上界の証明に現れる数の巨大さがある。ラムジー型の定理では、「十分大きければ」の「十分」が想像を絶する大きさになることがある。証明のなかに登場する数の上界が、指数関数よりはるかに速く増大する関数で与えられることも珍しくない。グラハム数――正式な数学の証明に使われた巨大な数として知られる――も、もとはラムジー理論の問題の上界として現れた。理論は「有限で必ず捕まる」と保証するが、その有限が、現実的な意味では無限とほとんど区別がつかないほど巨大なことがある。

入り口になる本

ラムジー理論だけを主題にした日本語の一般向け書籍は、ほぼ見当たらない。ただし、組合せ論の入門書のなかにラムジーの定理を扱った章を持つものがあり、そこが現実的な入り口になる。

• ジョージ・ポリア、ロバート・タージャン、ドナルド・ウッズ『組合せ論入門』（近代科学社）。スタンフォード大学での講義録をまとめたもので、目次に「ラムゼイの定理」が独立した一章として立っている。『いかにして問題を解くか』の著者ポリアと、計算機科学のネヴァンリンナ賞を第1回に受賞したタージャンによる本で、ラムジー理論に章単位で触れられる日本語の本としては、最も入り口に近い。

• ラスロー・ロバース、秋山仁、ピーター・フランクル『入門 組合せ論』（共立出版）。組合せ論の基本的な証明法を扱う章で、ラムジー理論の土台になる鳩の巣原理を平易に学べる。ラムジーの定理そのものの独立章はないが、「無秩序は不可能」という議論がどんな土台の上に立っているかを、まず掴むのに向く。

• イジー・マトウシェク『33の素敵な数学小景』（徳重典英訳、日本評論社、2014年）。組合せ論や離散幾何学の面白い話題を、一つ数ページのコンパクトな読み切りで集めた本。ラムジー理論的な発想の手触りに、軽く触れてみるのによい。

最初の一冊としてはポリアらの『組合せ論入門』を勧める。ラムジーの定理を独立の章で扱っているうえ、組合せ論全体の見取り図のなかにその定理を位置づけて読める。そこで物足りなくなれば、英語にはなるが、グレアム、ロスチャイルド、スペンサーによる古典的な専門書『Ramsey Theory』が、この分野の本格的な標準文献として待っている。