数学者たちが共通の空間に隠された構造を発見

2017年秋、当時マサチューセッツ工科大学の学部生だったメータアブ・ソーニーは、1学期かけて1つの論文を研究するという大学院生の読書会に参加した。しかし、学期末には証明の複雑さに困惑し、次のステップに進むことを決めたとソーニーは振り返る。「本当に素晴らしい論文でした」と彼は言う。「全く予想外の論文に思えたんです」

この論文はオックスフォード大学のピーター・キーヴァッシュ氏によるもので、テーマは「デザイン」と呼ばれる数学的対象です。

デザイン研究の起源は1850年に遡ります。当時、イングランド北部の教区の牧師で数学にも手を染めていたトーマス・カークマンは、『淑女と紳士の日記』という雑誌に、一見単純な問題を提示しました。15人の女子生徒が1週間毎日3人ずつ並んで学校に通うとします。7日間を通して、同じ列に2人の女の子が2回以上並ばないように、女子生徒を並べることができますか？

すぐに、数学者たちはカークマンの質問のより一般的なバージョンを問うようになりました。集合にn個の要素 (15 人の女子生徒) がある場合、常にそれらの要素をサイズk (3 列) のグループに分類して、サイズtのすべての小さな集合(すべての女子生徒のペア) がそれらのグループの 1 つに正確に現れるようにすることはできますか。

このような構成は ( n , k , t ) 設計として知られ、それ以来、誤り訂正コードの開発、実験の設計、ソフトウェアのテスト、スポーツの予想や宝くじの当選などに役立てられてきました。

しかし、 kとtが大きくなるにつれて、それらの構築は極めて困難になります。実際、数学者はtの値が5を超える設計をまだ発見していません。そのため、2014年にキーヴァッシュが、そのような設計の構築方法を知らなくても、 nが十分に大きく、いくつかの単純な条件を満たす限り、そのような設計は常に存在することを示したとき、大きな驚きがもたらされました。

今回、キーヴァッシュ、ソーニー、そしてMIT大学院生のアシュウィン・サーは、さらに捉えどころのない物体、いわゆる「部分空間設計」も常に存在することを実証した。「彼らは、存在が全く自明ではない物体の存在を証明したのです」と、カリフォルニア工科大学の数学者デビッド・コンロンは述べた。

そのためには、キーヴァッシュの当初のアプローチ――ランダム性と綿密な構成を魔法のように融合させたもの――を、はるかに制約の厳しい状況でも機能させるよう改良する必要があった。こうして、現在MITで博士号取得を目指すソーニーは、ほんの数年前に頭を悩ませた論文と向き合うことになった。「その手法を完全に理解し、本当に苦労して取り組み、発展させていくのは、本当に本当に楽しかった」と彼は語った。

「私たちの想像を超えたもの」

数十年にわたって、数学者は集合と部分集合に関する問題（設計問題など）を、いわゆるベクトル空間と部分空間に関する問題に変換してきました。

ベクトル空間とは、その要素（ベクトル）が、単純な点の集合よりもはるかに厳密な関係で相互に関連付けられる特殊な集合です。点はあなたがどこにいるかを示します。ベクトルはあなたがどれだけの距離を、どの方向に移動したかを示します。ベクトルは加算したり減算したり、大きくしたり小さくしたりすることができます。

あなたが今いる部屋を考えてみましょう。そこには無数の点と、あなたのいる場所から部屋のあらゆる点へと伸びる無数のベクトルがあります。これらのベクトルはすべて、3つの基本的なベクトルから構成されます。1つはあなたの正面に水平に伸びるベクトル、もう1つはあなたの右に伸びるベクトル、そしてもう1つは上向きのベクトルです。これらのベクトルを足し合わせたり、実数を掛け合わせたり、あるいはその両方を行うことで、あなたが住んでいる3次元のベクトル空間を生成できます。（空間全体を生成するために必要なベクトルの数は、ベクトル空間の次元です。）

それぞれのベクトル空間には様々な部分空間が存在します。右向きと前向きのベクトルだけを取ります。これらは二次元部分空間、つまり床に平行な平面を定義します。

数学者はしばしば有限ベクトル空間と部分空間を扱いますが、そこではベクトルはあらゆる方向を指すことはできず（また、長さの概念も一定ではありません）、この世界では、各ベクトル空間には有限個のベクトルしか存在しません。

部分空間設計問題は、n次元ベクトル空間とその部分空間を扱います。このようなベクトル空間において、繰り返しますが、nが十分に大きく、単純な条件を満たす限り、任意のt次元部分空間がちょうど1つに含まれるようなk次元部分空間の集合を見つけられるでしょうか？このような対象は、( n , k , t )部分空間設計と呼ばれます。これは概念的には通常の設計問題に似ていますが、より厳密に制約された配置を伴います。

「これは、集合と部分集合、そしてベクトル空間と部分空間の間の非常に深い類推の一角であるため、重要な問題です」とスコットランドのセント・アンドリュース大学のピーター・キャメロン氏は述べた。

数学者たちがこの問題について考え始めてから50年が経ちますが、非自明な例はたった1つしか見つかっていません（より一般的な種類の部分空間設計が存在することは分かっていますが）。13次元ベクトル空間において、2次元部分空間を3次元部分空間で覆うことは、正確に1回しか不可能です。この結果を証明するには、膨大なコンピュータを用いた証明が必要でした。なぜなら、 n、k、tの値がこれほど小さい場合でも、数百万もの部分空間を扱うことになるからです。このようなシステムの複雑さは「単に私たちの想像を超えているだけでなく、想像を超えるものを超えているのです」と、この例の発見に貢献したイスラエル工科大学のトゥヴィ・エツィオン氏は述べています。

しかし、 kとtのいずれに対しても、部分空間設計は常に存在するのだろうか？一部の数学者は、概してそのような対象は不可能だと推測した。一方、長年にわたる設計研究に勇気づけられた他の数学者は、「証明するのは難しいかもしれないが、存在しない明白な理由がなければ、存在するはずだ」と考えた、とキーヴァッシュ氏は述べた。

デザインの分野と比べると、「この問題に関しては、何もありませんでした」とサー氏は言う。「そういうことが起こるたびに、少し好奇心が湧いてくるのだと思います。」

エラーを吸収するスポンジ

サーとソーニーは2017年にMITの学部生として出会い（そして同じ読書会に参加することになった）、数ヶ月後に「二人は一緒に研究を始め、それ以来ずっと研究を続けています」とコンロン氏は語る。「彼らは、私が瞬きするのも止まらないほどのペースで、質の高い研究成果を生み出しています。」

2 人の若い数学者は、部分空間設計の明確な例を 1 つだけ書き留めることさえ非常に困難であったことに興味をそそられ、その問題は組み合わせ論における重要な技術の限界を探るのに最適な方法であると考えたのです。

一方、キーヴァッシュ氏は2014年の選挙結果以来、この問題を心の片隅に抱えていた。昨年の会議でサー氏とソーニー氏が彼に声をかけ、3人は挑戦することに決めた。

彼らはキーヴァッシュが設計作業で示したのと同じ全体的な戦略に従ったが、より厳しい制約があったため、「実際には、すべてのステップの実装は大きく異なっていました」とキーヴァッシュは語る。まず、彼らはテンプレートと呼ばれる、慎重に選ばれたサブスペースのセットを用意した。このテンプレートは後に、ランダム性の海に浮かぶ構造の島として機能することになる。

次に、残りの部分空間の大部分をカバーするために、Rödl nibbleと呼ばれる、根本的にランダムなプロセスの修正版を適用しました。その結果、依然として処理しなければならない部分空間がまばらに混在する状態が残りました。表面的には、これらの部分空間は完全に構造化されていないように見え、適切にカバーできるクラスターにまとめることは不可能に思えました。

ここでテンプレートの出番が来た。彼らはテンプレートを分解し、そのサブスペースの一部を寄せ集めの中のサブスペースと組み合わせ、それらをきちんと覆える大きな配置にぴったりと押し込んだ。彼らは、あらゆる動きがより全体的な構造につながるように、これをどのように行っているかを注意深く追跡する必要があった。しかし最終的には、テンプレートを使用して、Rödl のニブルでは埋められなかったすべての穴を埋めることができた。スポンジのように、テンプレートは設計内のすべてのエラーを吸収した (結果として、この一般的な手法は「吸収」と呼ばれている)。「まるで隅にカーペットを敷こうとしているようなものです」と Sawhney 氏は言う。「カーペットが別の場所に飛び出してきて、それを押すと、どういうわけか、20 回押すとカーペットは平らになります。」

これで証明は完了です。設計作業と同様に、この結果は少なくとも理論的にはこれらのオブジェクトの構築に使用できることに留意することが重要ですが、nが非常に大きい場合に限られます。具体的かつ実用的な例を見つけることは、今後の課題です。

結局、この研究は、数学者がランダム性の力を利用して隠れた構造を探索するという、直感に反する新たな方法を示した。「あらゆる種類の予想外の構造が考えられます」と、西オーストラリア大学の数学者シェリル・プレーガー氏は述べた。

「この証明は、キーヴァッシュの手法が当初想定されていたよりも広い文脈で機能することを示しています」とキャメロン氏は述べた。これは、ランダム性と吸収を巧みに組み合わせることで、他の困難な問題にも対処できる可能性があることを示唆している。

ソーニーは学部生時代にキーヴァッシュの論文で初めてこれらの技術について読んだ時、魔法のように感じた。より深く理解した今でも、「この印象は消えない」という。

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