サプライズ コンピューター サイエンスの証明が数学者を驚かせる

5 月 XNUMX 日の日曜日、Olof Sisask と Thomas Bloom は、彼らの分野で最大の未解決の問題に関する驚くべきブレークスルーを含む電子メールを受け取りました。 イリノイ大学アーバナ シャンペーン校の大学院生であるザンダー ケリーは、シサスクとブルームを派遣しました。 彼が書いた論文 カリフォルニア大学ロサンゼルス校のRaghu Mekaと。 ケリーとメカはどちらもコンピューター科学者であり、シサスクとブルームが研究している加法的組み合わせ論とは別の知的な世界でした。

「私の心はただ吹き飛ばされました。 ちょっと待って、彼らは本当にこれをやったのですか？ ストックホルム大学の講師である Sisask 氏は、次のように述べています。 組み合わせ論の分野のアウトサイダーである Kelley と Meka は、整数のセットのサイズに新しい (そして劇的に低い) 制限を発見したと述べました。または 3、8、および 13)。

ケリーとメカの主張はこれまでの記録を破り、 2020年達成 オックスフォード大学のリサーチフェローであるシサスクとブルームによる。 「ブルームとシサスクの仕事は、非常に強力な仕事でしたが、改善するのが非常に難しいという印象を与えました」と、ブルームのオックスフォード大学の同僚であるベン・グリーンは言いました。 「その場所に非常に行き詰まっているように見えました。」

ブルームとシサスクは、メールを受け取った時点で他に対応しなければならない差し迫った問題を抱えていましたが、ブルームは子犬を引き取ったばかりで、シサスクは引っ越しの最中だったのです。

数日のうちに、ブルームとシサスクは新しい証明が正しいと確信しました。 Sisask 氏は、これを「この分野で 20 年間で最大の成果」と呼んでいます。 他の人がケリーとメカのアイデアを評価することを熱望し、彼らは草案を作成しました レポート 証明を数学者により親しみやすい言葉で説明します。

Meka 氏は、コミュニティからの反応は「思っていたよりもポジティブなものでした。 すべてのフィードバックを見るのは素晴らしいことです。」

長引く進歩

ケリーとメカが回避しようとした等間隔の数列は、等差数列と呼ばれます。 それらは永遠に続くこともあれば、いくつかの用語のみを含むこともあります。 Kelley と Meka は XNUMX つの数字からなる数列に注目しました。 1936紙 ポール・エルデシュとポール・トゥラン著。

Erdős と Turán は、天井よりも小さい数がいくつあるかを知りたがっていました。 N 三項算術数列を作成せずにセットに入れることができます。 N 1,000、1 万、または想像を絶する巨大な数になる可能性があります。 彼らは次のように推測した N が大きくなると、XNUMX 期進行のないセットは信じられないほどまばらになる必要があります。 このようなセットを作成することは、XNUMX つのペアが同じ色ではないと主張しながら靴を集めるようなものです。 おそらく永遠に続けることもできますが、コレクションが大きくなるにつれて、コレクションを追加する速度がますます遅くなることに気付くでしょう.

「セットをどのように選んだとしても、セットに組み込まれる構造があります」と Meka は説明します。 「この構造がそこにあることを保証するには、実際にどのくらいのサイズのセットが必要ですか?」

1946年、フェリックス・ベーレンド 集合を構築する方法を見つけた 1 から N XNUMX 期進行を生じさせずに。 彼の方法は、セットが大きくなるという結果になりました。 N しましたが、痛々しいほどゆっくりです。 いつ N は 100,000 ですが、Behrend のセットには 171 個の要素しか含まれていません。 いつ N は 1 万で、彼のセットには 586 個の数字があります — 0.06 から 1 万の間の数字の 1% 未満です。

Behrend の集合は、数学者に作業の余地を与えました。1953 項の進行がない最大の集合は、少なくとも Behrend のものと同じ大きさでなければなりません。 XNUMX年、クラウス・ロス 天井を設けた、セットが必然的に XNUMX 項の進行を含まなければならないしきい値を見つけます。

ロスはエルデシュとトゥランの予想を次のように示して証明した. N が大きくなると、1 項進行のないセットは、0.02 から N までの数字のごく一部を構成することになります。 Behrend は、1 万から 1 万の間の要素の 40% がプログレッション フリー セット内に収まることを示しました。 Roth の式を正確に計算するのは困難ですが、それほど低くはありません。大まかな見積もりでは、パーセンテージを約 XNUMX% に制限しています。

しかし、その特定のギャップよりも顕著なのは、1 つの式の全体的な動作でした。 XNUMX ～ の間の要素の割合をプロットします。 N 各式が表すと、Behrend の数が次のように急速にゼロに縮小することがわかります。 N 成長します。 一方、ロスの分数は、ゆっくりと緩やかにゼロに向かってスライドします。 XNUMX つの曲線は非常に異なる形状であり、数学者が知る限り、等差数列のない集合に含まれる要素の真の割合は、それらの間のどこかにある可能性があります。

1980 年代から、「後から考えると、かなりの数の非常に有名な数学者によって、かなり漸進的な改善が行われました」と Green 氏は述べています。 ときどき、誰かが Roth の上限を XNUMX ～ XNUMX 本引き下げ、最終的にはかなり低くなりました。 対照的に、Behrend の下限は何十年も動揺していませんでした。 数学者たちは、Behrend が真の答えからそう遠くないかもしれないと考え始めた、と Bloom は言った。

Kelley と Meka の論文が 2023 年初頭に到着するまで、プログレッション フリー セットの最大サイズは、Behrend の式によって下から、Bloom と Sisask の式によって上から書き出されていました。 2020 年 XNUMX 月の Bloom と Sisask の論文は、進行のないセットは、 N/（ログ N) 要素。 しかし、彼らの結果は依然として Behrend の結果を上回りました。 Kelley と Meka の新しい上限は、Behrend が設定した下限に大幅に近づいています。

UCLA の著名な数学者 Terence Tao は次のように述べています。

それらの式は Behrend のものとほぼ同じですが、いくつかのパラメーターが微調整されているだけです。 として N が無限に近づくと、ケリーとメカの式のプロットは、最終的にはベーレンド曲線に似た曲線に落ち着きます。 ブルーム氏は、「そのような形でバウンドすることは、以前は不可能な夢のように思えました。

「彼らがこのような改善を行ったことに、私は本当にただただ驚きました」とグリーンは言いました。

別のタック

 Kelley と Meka はそれまで純粋数学の研究に完全に挑戦したことはありませんでしたが、彼らが始めたとき、算術数列は彼らになじみがありました。 一般に、コンピューター科学者は「私たちの問題を解決するのに役立つ技術を熱心に探しています」とケリー氏は述べています。 プログレッション フリー セットのサイズを研究するために歴史的に使用されてきたツールは、複雑性理論のコンピューター サイエンスのサブフィールドで広く使用されるようになりました。 このようなセットのサイズを絞り込む問題は、セットの内部構造を調査する手法を適用する典型的な例として、複雑さの理論家にはよく知られています。

2021 年後半、ケリーとメカは、標準的なタイプのコンピューター サイエンスの問題である、特定の協力ゲームでプレイヤーのチームが勝つ可能性を分析していました。 プログレッションフリーセットのサイズに関する研究からのテクニックが役立つかもしれないと彼らは思いついた. しかし、協力ゲームに適用するよりも、これらのテクニックを直接研究する方が簡単であることがわかりました。 「この問題を解決するための最善の方法は、ツール自体を実際に改善することであり、より巧妙な方法で使用することではありませんでした」と Kelley 氏は述べています。

「ある時点で、私たちはこの問題に直接取り組むことにしました」と Meka 氏は思い起こします。 XNUMX か月後、XNUMX 人の研究者は自分たちの戦略を理解し、その方法を目前の問題にどのように適用するかを解決する必要がありました。

どのようにして新しい上限に到達したかを確認するには、1 から N。 Call itあれを呼べ A。 の密度 A は 1 ～ の数値のパーセンテージです。 N それが含まれていること。 1 から Nの要素を選択しない場合 A 慎重に、いずれか A 高密度の場合、多くの算術級数が含まれる可能性があります。

証明の中で、ケリーとメカは次のように想像しました。 A 彼らは数列をほとんどまたはまったく持たず、その結果を追跡しようとしました。 もしも A 十分に密度が高く、プログレッションが存在しない場合、内部に一定レベルの構造が必要であることを示しました。 A それは必然的に矛盾をもたらすだろう、つまり A 結局のところ、少なくとも XNUMX つのプログレッションが含まれている必要があります。

その構造を理解するために、彼らはセットを考えました A + Aの XNUMX つの要素を追加することによって作成されるすべての数値で構成されます。 A. 彼らは気づいた A には比較的少ない数列が含まれており、これは要素間の冗長性を意味します。 A + A: からの異なる数のペア A 合計すると同じ数になることがよくあります。

密度は、1 から N しかし、いくつかのサブセットと比較すると、その間隔内の偶数の整数のみ、または 3 の倍数のみと言います。ケリーとメカは冗長性を次のように使用しました A + A の要素がある整数のサブセットを見つける A が特に多かった。

たとえば、A に 3 の倍数が不均衡に多く含まれている場合、ケリーとメカは 3 の倍数を含む部分に注目します。彼らはこの戦略を何度も繰り返しました。 整数のより小さなサブセットを見つけるたびに、 Aの密度は成長し続けます。 例えば、 A 10 から の間の整数の 1% を含む可能性があります N、その区間の 15 の倍数の 3%、25 の偶数の倍数の 3% です。

面白いことが起こるとき A は大きい。 この手順を繰り返すと、 A 一部のサブセットでは 100% を超えています。 もちろん、それは不可能です。 A たとえば、24 の倍数をすべて含むことはできますが、すべてを超えることはできません。 このパラドックスは、次の場合にのみ発生します。 A そもそも十分に大きいですが、そうなると、それは次の仮定を意味します A 算術進行が含まれていない場合は、間違っていたに違いありません。

それは「win-win の議論」です。 A 大きい、とメカは言った。 また A 多くの算術級数が含まれているか、冗長性が非常に高い A + A — その場合、サブセットを見つける手順 (「密度増加戦略」と呼ばれる) を使用して、進行が出現する必要があることを示すことができます。 A. 密度増加戦略はこの分野では使い古された青写真ですが、Kelley と Meka はそれを小規模な環境でも機能させることに成功しました。 Aはこれまで以上に。 これにより、プログレッション フリー セットのサイズの新たな上限が明らかになりました。

Kelley と Meka は、密度増分の設計図から独自のアイデアを組み合わせて構築しました。 彼らはまったく新しいフレームワークを思いつくのではなく、密集したサブセットを見つける方法を再考しました。 このために、彼らは「ふるい分け」と呼ばれる手法を使用しました。これは、セットを一定量シフトし、それ自体と交差させ、プロセスを何度も繰り返すことで構成されています。 交差を何度も繰り返した後、予測可能なプロパティを持つ高度に構造化されたセットが残ります。 ふるい分けは他の論文で使用されていましたが、XNUMX 項進行問題で試みられたことはありませんでした。

後ろ向き

Kelley と Meka は、従来の方法にふるいにかけるなど、無視されてきたツールを導入することで、プログレッション フリー セットのサイズ制限を驚くほど引き下げました。 「ケリーとメカは、公開されていたこれらの技術が、私たちが思っていたよりもはるかに強力であることをどういうわけか示しました」とブルームは言いました. これらのツールの有効性が新たに発見されたことを考慮して、彼は「すべてを振り返って再検討する必要があります」と付け加えました。

密度増加戦略は、70 年前に Roth の論文に初めて登場し、以来、算術数列に関するほとんどの論文で使用されてきました。 Green は、このフレームワークを使用して、Kelley と Meka と同じくらい低い境界を証明できることに驚きました。 「完全に根本的に異なる何かが必要になると思いました」と彼は言いました。

ケリーは、数学への進出を続けることに興奮しています。 「少なくとも精神的に関連していると考えられるさまざまな問題について、私は希望と夢に事欠きません」と彼は言いました。

ケリーとメカがかつて見過ごされていたアイデアの強さを発見したことは、数学的進歩のしばしば適切でない性質を示しています — タオにとっては呪いというよりは祝福のような性質です. 「数学がますます難しくなるというわけではありません」と彼は言いました。 "ああ、助かった。"