多数の無法性

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

今年、Quantaはこれまでに、数学的パターンの発生を回避する方法を研究するラムゼー理論における3つの大きな進歩を記録してきました。最初の成果は、{2, 4, 6}や{21, 31, 41}のように、3つの等間隔の数字を含まない整数集合の大きさに新たな上限を設けました。2つ目と3つ目の成果も同様に、全てが接続されているか、全てが互いに分離している点のクラスターを含まないネットワークのサイズに新たな限界を設けました。

証明は、関係する数が無限に大きくなった場合に何が起こるかを扱っています。逆説的ですが、これは厄介な現実世界の量を扱うよりも簡単な場合もあります。

例えば、分母が非常に大きい分数に関する2つの問題を考えてみましょう。例えば、1/42503312127361 の小数展開はどうなるか、あるいは、分母が大きくなるにつれてこの数は0に近づくかどうかを問うことができます。最初の問題は現実世界における具体的な量に関する問題であり、n が大きくなるにつれて 1/ nという量が「漸近的に」どのように変化するか（0にどんどん近づいていく）を問う2番目の問題よりも計算が困難です。

「これはラムゼー理論全体を悩ませている問題です」とメリーランド大学のコンピュータ科学者、ウィリアム・ガサーチ氏は述べた。「ラムゼー理論は漸近的に非常に良好な結果をもたらすことで知られています。」しかし、無限大よりも小さい数を解析するには、全く異なる数学的ツールボックスが必要になる。

ガサーチ氏は、ラムゼー理論において、力ずくでは解けないほど大きな有限数に関する問題を研究してきた。あるプロジェクトでは、今年の最初の画期的な成果である、イリノイ大学アーバナ・シャンペーン校の大学院生ザンダー・ケリー氏とカリフォルニア大学ロサンゼルス校のラグー・メカ氏による2月の論文の有限バージョンに取り組んだ。ケリー氏とメカ氏は、3項数列、つまり等間隔の数のパターンを避けながら、1からNまでの整数を集合にいくつ含めることができるかという新たな上限を発見した。

KelleyとMekaの結果はNが比較的小さい場合でも当てはまりますが、その場合特に有用な境界値を与えるものではありません。Nが非常に小さい値の場合は、非常に単純な方法に固執する方がよいでしょう。例えばNが5であれば、1からNまでのすべての可能な数の集合を見て、最も大きな累乗のない集合、つまり{1, 2, 4, 5}を選び出すだけです。

しかし、考えられる異なる答えの数は急速に増え、このような単純な戦略を採用するのは難しくなる。1から20までの数字からなる集合は100万通り以上ある。1から200までの数字を使った集合は10の^60乗通り以上ある。これらのケースに最適な漸進フリー集合を見つけるには、効率改善戦略を使ってもかなりの計算能力が必要になる。「多くのパフォーマンスを引き出せるようにする必要がある」とイェール大学のコンピュータ科学者、ジェームズ・グレン氏は述べた。2008年、ガサーチ氏、グレン氏、メリーランド大学のクライド・クラスカル氏は、Nが187までの最大の漸進フリー集合を見つけるプログラムを作成した（これまでの研究では、157の場合だけでなく、150までの答えも得られていた）。グレン氏によると、さまざまなトリックを駆使したにもかかわらず、プログラムを完成させるのに数ヶ月かかったという。

計算負荷を軽減するために、研究チームはプログラムが行き止まりの検索を行わないようにする簡単なテストを使用し、セットを小さな部分に分割して個別に分析しました。

ガサーチ、グレン、そしてクラスカルは、他にもいくつかの戦略を試した。有望なアイデアの一つは、ランダム性に着目したものだった。数列のない集合を作る簡単な方法は、集合に1を入れ、次に等差数列を作らない次の数を常に追加していくことだ。この手順を10に達するまで続けると、{1, 2, 4, 5, 10}という集合が得られる。しかし、これは一般的には最善の戦略ではないことが判明した。「1から始めないではどうだろう？」とガサーチは言った。「ランダムな場所から始めれば、実際にはより良い結果が得られる」。研究者たちは、なぜランダム性がそれほど有用なのか全く分かっていないと彼は付け加えた。

ラムゼー理論の他の2つの新しい結果の有限バージョンを計算することは、漸化自由集合のサイズを決定することよりもさらに厄介です。これらの結果は、エッジと呼ばれる線で接続されたノードで構成される数学的ネットワーク（グラフと呼ばれる）に関するものです。ラムゼー数r ( s , t )は、グラフがs個の接続されたノードのグループ、またはt個の非接続のノードのグループのいずれかを含むことを避けられなくなる、グラフに必要な最小のノード数です。ラムゼー数の計算は非常に困難で、r (5, 5)さえも未知であり、43から48の間のどこかにあります。

1981年、現在オーストラリア国立大学のコンピューター科学者であるブレンダン・マッケイ氏は、ラムゼー数の計算を簡素化することを目的としたnautyというソフトウェアプログラムを開発しました。nautyは、研究者が単に反転または回転しただけの2つのグラフを確認する時間を無駄にしないよう支援します。「もし誰かがその領域にいてnautyを使っていないなら、ゲームオーバーです。必ず使わなければなりません」と、ロチェスター工科大学の数学者スタニスワフ・ラジショフスキ氏は述べました。それでも、必要な計算量はほとんど計り知れません。2013年、ラジショフスキ氏とヤン・グッジボー氏は、r (3, 10) が最大で42であることを証明しました。「計算にはCPU年で約50年かかったと思います」と、ベルギーのルーヴェン・カトリック大学のコンピューター科学者であるグッジボー氏は述べました。

ラムゼー数を正確に計算できない場合は、例を用いてその値を絞り込むことができます。例えば、45ノードのグラフで、5ノードがすべて接続されておらず、5ノードがすべて切断されていないグラフが見つかった場合、r (5, 5) が45より大きいことが証明されます。ラジショフスキー氏によると、ラムゼー数を研究する数学者たちはかつて、ラムゼーグラフと呼ばれるこれらの例を見つけることは簡単だと考えていました。しかし、実際はそうではありませんでした。「素晴らしくクールな数学的構成が最良の構成をもたらすという期待があり、それを研究する人を増やす必要があるだけでした」と彼は言います。「私は、それがますます混沌としていると感じています。」

ランダム性は理解の妨げにもなり、また便利なツールにもなる。インディアナ州立大学のコンピューター科学者、ジェフリー・エクソー氏は、ラムゼーグラフを生成するためのランダム手法の改良に長年を費やしてきた。2015年に発表された、記録を破る数十もの新たなラムゼーグラフを発表した論文で、エクソー氏とミロス・タタレビッチ氏はランダムグラフを生成し、その後、不要なクラスターの数を減らすエッジを削除または追加することで徐々に調整を加え、ラムゼーグラフを完成させた。しかし、ラジショフスキー氏によると、エクソー氏の手法はもはや芸術と言えるほどだ。複数の手法を組み合わせたり、どのような種類のグラフから始めるべきか判断したりする必要があることもある。「多くの人が試しますが、できません」とラジショフスキー氏は言う。

ラムゼーグラフを生成するために開発された技術は、将来的にはより広く役立つ可能性があると、化合物を表すグラフなど、他の種類のグラフの作成にも取り組んできたゲッジボー氏は述べた。「これらの技術を転用・調整することで、他の種類のグラフをより効率的に生成できるようになる可能性は低くありません（逆もまた同様です）」と、同氏は電子メールで述べている。

しかし、ラジショフスキー氏にとって、小さなラムゼー数を研究する理由ははるかに単純だ。「なぜなら、それは未解決問題だからです。誰も答えを知らないからです」と彼は言った。「些細なケースは手作業で解きますが、もう少し大きなケースになるとコンピューターが必要になります。そして、もう少し大きなケースになると、コンピューターでさえ十分ではありません。そこで課題が生まれるのです。」

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