ランダムに選択された数値のセットでは、加算が暴走する可能性があります。

このようなセットのすべてのペアを合計すると、最初のリストよりもはるかに多くの数が含まれる可能性が高い新しいリストが作成されます。 10 個の乱数から開始すると、この新しいリスト (サムセットと呼ばれる) には約 50 個の要素が含まれます。 100 から始めて、合計はおそらく 5,000 程度になるでしょう。 1,000 個のランダムな初期数値により、合計の長さは 500,000 個の数値になります。

ただし、初期セットに構造がある場合、合計セットの数値がこれより少なくなる可能性があります。 別の 10 個の数値セット、つまり 2 から 20 までのすべての偶数を考えてみましょう。異なるペアを合計すると同じ数値になるため、10 + 12 は 8 + 14 および 6 + 16 と同じです。合計セットには 19 個の数値だけが含まれます。 50. セットが大きくなるにつれて、この違いはますます大きくなります。 1,000 個の数値からなる構造化リストには、2,000 個の数値だけを含むサムセットが含まれる場合があります。

1960年代、ある数学者は、 グレゴリー・フライマン は、加算と集合構造の間の関連性 (加算的組み合わせ論の数学的分野を定義する重要な関連性) を調査するために、小さな合計集合を持つ集合の調査を開始しました。 フライマンは目覚ましい進歩を遂げ、小さな合計を含む集合は、要素が非常に規則的なパターンで配置されている大きな集合に含まれる必要があることを証明しました。 しかしその後、この分野は停滞しました。 「フライマンの最初の証明は非常に理解しにくく、それが正しいという確信を持つ人は誰もいなかったほどでした。 したがって、それが及ぼしたであろうような影響は実際にはありませんでした」と述べた。 ティモシー・ガワーズ、コレージュ・ド・フランスとケンブリッジ大学の数学者であり、フィールズのメダリストでもあります。 "しかしその後 イムレ・ルザ 現場に突入した。」

一連の 2 論文 1990 年代に、ルザはエレガントな新しい議論でフライマンの定理を再証明しました。 何年か後、 カタリン・マートン2019年に亡くなった影響力のあるハンガリーの数学者は、元の集合の構造に関して小さな合計が何を意味するかという問題に微調整を加えた。 彼女は、セット内に出現する要素の種類と数学者が探すべき構造の種類を置き換えて、数学者がさらに多くの情報を抽出できるようになると考えました。 マートンの予想は証明システム、コーディング理論、暗号化と関連しており、加法的組み合わせ論において高い地位を占めています。

彼女の推測は「私たちが理解できなかった最も基本的な事柄の一つのように感じます」と述べた。 ベングリーン, オックスフォード大学の数学者。 それは「私が気にかけていることの多くを支えているようなものでした。」

グリーンはガワーズと協力し、 フレディマナー カリフォルニア大学サンディエゴ校の テレンス・タオ、カリフォルニア大学ロサンゼルス校のフィールズメダリストであり、イスラエルの数学者兼ブロガーが何を形成したか ギル・カライ と呼ばれるチーム数学者の」。 彼らは論文で予想のバージョンを証明した 9月XNUMX日に共有されました.

ネッツ・カッツこの研究には関与していないライス大学の数学者は、この証明を「非常に単純明快」であり、「多かれ少なかれ完全に思いがけない」ものであると述べています。

その後、タオ氏は証明を形式化する取り組みを開始した。 リーン、数学者が定理を検証するのに役立つプログラミング言語。 わずか数週間でその取り組みは成功しました。 １２月５日火曜日の早朝、 タオが発表した リーンは「ごめんなさい」（コンピュータが特定のステップを検証できない場合に表示される標準的な文）を一切言わずに、この推測を証明したということです。 これは、そのようなものの最も注目度の高い使用法です 2021 年以降の検証ツール、そして数学者がコンピュータが理解できる用語で証明を書く方法の変曲点を示しています。 これらのツールが数学者にとって使いやすいものになれば、長くて面倒な査読プロセスを代替できるかもしれない、とガワーズ氏は述べた。

証拠の材料は何十年も煮詰まっていた。 ガワーズは 2000 年代初頭に最初のステップを構想しました。 しかし、カライ氏がこの分野の「聖杯」と呼んだものを証明するには20年かかりました。

グループ内

マートンの予想を理解するには、集合と演算から構成される数学的オブジェクトである群の概念をよく理解することが役立ちます。 整数 (無限の数の集合) と加算演算について考えてみましょう。 3 つの整数を加算するたびに、別の整数が得られます。 加算は、演算の順序を変更できる結合性など、グループ演算の他のいくつかのルールにも従います: 5 + (2 + 3) = (5 + 2) + XNUMX。

グループ内で、すべてのグループ プロパティを満たす小さなセットが見つかることがあります。 たとえば、任意の 1 つの偶数を加算すると、別の偶数が得られます。 偶数はそれ自体がグループであり、整数のサブグループになります。 対照的に、奇数はサブグループではありません。 XNUMX つの奇数を加算すると、元のセットには含まれない偶数が得られます。 ただし、すべての偶数に XNUMX を加算するだけで、すべての奇数を取得できます。 このようにシフトされたサブグループは剰余類と呼ばれます。 サブグループのすべてのプロパティを備えているわけではありませんが、多くの点でサブグループの構造が保持されています。 たとえば、偶数と同様に、奇数もすべて等間隔です。

マートンは、もしセットを持っていれば我々が呼ぶだろうと考えた A 合計がそれほど大きくないグループ要素で構成されます。 A それ自体である場合、いくつかのサブグループが存在します - それを呼び出します G — 特別な性質を持つ。 シフト G 剰余類を数回作成すると、それらの剰余類を組み合わせると元の集合が含まれます。 A。 さらに、彼女は剰余類の数が合計集合のサイズよりもはるかに速く増加することはないと仮定しました。彼女は、剰余類の数は、はるかに急速な指数関数的な増加ではなく、多項式係数によって関連付けられるべきだと信じていました。

これは非常に技術的な好奇心のように聞こえるかもしれません。 しかし、これは単純なテストに関係しているため、セットに要素を XNUMX つだけ追加するとどうなるでしょうか? — サブグループの全体的な構造は、数学者やコンピューター科学者にとって非常に重要です。 コンピューター科学者が一度にメッセージのほんの一部を解読できるようにメッセージを暗号化しようとするときも、同じ一般的な考え方が現れます。 また、確率的にチェック可能な証明、つまりコンピューター科学者が情報のいくつかの独立したビットのみをチェックすることによって検証できる証明の形式にも現れます。 これらの各ケースでは、構造内のわずか XNUMX つのポイントを操作して (長いメッセージからほんの数ビットをデコードしたり、複雑な証明の一部を検証したり)、より大きなより高いレベルの構造について何らかの結論を導き出します。

「すべてをグループの大きな部分集合であるかのように装うこともできます」と彼は言った トム·サンダース、ガワーズの元学生で、現在はオックスフォード大学のグリーンの同僚である、あるいはあなたは、「多くの付加的な偶然の存在から、あなたが望んでいたすべてを手に入れることができます。」 どちらの視点も役に立ちます。」

ルザ 1999年にマートン予想を発表、彼女を全面的に信頼しています。 「彼女は私やフライマンとは関係なく、おそらく私たちよりも先にその推測に達しました」と彼は言う。 「だから、彼女と話したとき、それを彼女の推測と呼ぶことにしたんです。」 それでも、数学者は現在、これを多項式フライマン-ルザ予想 (PFR) と呼んでいます。

ゼロとワン

多くの数学的オブジェクトと同様、グループはさまざまな形をとります。 マートンは、彼女の推測はすべてのグループに当てはまると考えました。 これはまだ示されていません。 新しい論文は、(0, 1, 1, 1, 0) のような XNUMX 進数のリストを要素とする特定の種類のグループについてそれを証明しています。 コンピューターはバイナリで動作するため、このグループはコンピューター サイエンスにおいて重要です。 しかし、これは加法的組み合わせ論でも役立ちます。 「これは、ちょっと遊んだり、何かを試したりできる、おもちゃのような環境です」とサンダース氏は語った。 「代数は、整数を扱うよりもはるかに優れています」と彼は付け加えました。

リストは固定長で、各ビットは 0 または 1 のいずれかになります。リストを加算するには、1 + 1 = 0 という規則に従って、各エントリを別のリストの対応する部分に追加します。つまり、(0, 1, 1, 1) , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1)。 PFR は、セットが完全なサブグループではないが、グループのような特徴がある場合に、そのセットがどのようなものになるかを理解する試みです。

PFR を正確にするために、次のようなバイナリ リストのセットがあると想像してください。 A。 次に、要素のすべてのペアを次から取得します。 A そしてそれらを合計します。 結果として得られる合計は、次の合計を構成します。 A A + A。 の要素がある場合、 A がランダムに選択されると、ほとんどの合計は互いに異なります。 あれば k の要素 A、つまり、周りにあるでしょう。 k²合計セット内の /2 要素。 いつ k 大きい — たとえば 1,000 — k²/2 はよりもはるかに大きいです k。 しかし、もし A はサブグループ、のすべての要素です A + A である Aこれは、 A + A と同じサイズです A そのもの。

PFR は、ランダムではないがサブグループでもないセットを考慮します。 これらのセットでは、要素の数は A + A やや小さい — たとえば 10k、または100k。 「構造の概念が単なる正確な代数構造であるよりもはるかに豊かな場合、これは非常に役立ちます。」と彼は言いました。 シャチャー・ロヴェット、カリフォルニア大学サンディエゴ校のコンピューター科学者。

数学者が知っていた、この性質に従う集合はすべて「実際の部分群にかなり近い」とタオ氏は述べた。 「それは、他の種類の偽のグループが横たわっているわけではないという直感でした。」 フライマンは、この声明のバージョンを彼のオリジナルの著作で証明しました。 1999 年に、Ruzsa はフライマンの定理を整数から二項リストの設定まで拡張しました。 彼は証明した 要素の数が A + A のサイズの定数倍です A, A サブグループ内に含まれています。

しかし、ルザの定理では部分群が巨大であることが必要でした。 マートンの洞察は、XNUMX つの巨大なサブグループに含まれるのではなく、 A 元の集合以下のサブグループの剰余類の多項式に含まれる可能性がある A.

「本当のアイデアを見ると、本当のアイデアがわかる」

XNUMX 年代の変わり目頃、ガワーズは等間隔の数値の文字列を含む集合に関する別の問題を研究していたときに、フライマンの定理のルザの証明に遭遇しました。 「特定のセットに関するもっと緩やかな情報から構造情報を取得するような、このようなものが必要でした」とガワーズ氏は語った。 「少し前に、ルザがこの素晴らしい証拠を作成してくれたことがとても幸運でした。」

ガワーズは、予想の多項式バージョンの潜在的な証明を考え出し始めました。 彼のアイデアはセットから始めることでした A 合計が比較的小さかったので、徐々に操作します A サブグループに入れます。 結果のサブグループが元のセットに類似していることを証明できた場合 A、彼はその推測が真実であると簡単に結論付けることができました。 ガワーズ氏は自分のアイデアを同僚と共有しましたが、誰もそれを完全な証拠にまとめることができませんでした。 ガワーズの戦略はいくつかのケースでは成功したが、他のケースでは操作に時間がかかった A 多項式フライマン・ルザ予想​​の望ましい結論からはさらに遠ざかります。

やがて、フィールドは動き始めました。 2012年、サンダースは PFRがほぼ証明されました。 しかし、彼が必要としたシフトされたサブグループの数は、ほんの少しではあるものの、多項式レベルを上回っていました。 「彼がそれをやったら、それは緊急性が下がったことを意味しましたが、それでも本当に素晴らしい問題であり、私はとても気に入っています」とガワーズ氏は語った。

しかし、ガワーズのアイデアは同僚の記憶とハードドライブの中に生き続けました。 「そこには本当のアイデアがある」と、ガワーズの生徒でもあったグリーンは語った。 「実際のアイデアを見れば、本当のアイデアがわかります。」 この夏、グリーン、マナーズ、タオはついにガワーズのアイデアを煉獄から解放した。

グリーン、タオ、マナーズは、ガワーズの 37 年前のアイデアに戻ることを考えるまでに、20 ページも協力して取り組んできました。 23月XNUMX日には 紙彼らは、確率変数と呼ばれる確率論の概念を使用して、小さな合計を持つ集合の構造を調査することに成功しました。 この切り替えを行うことで、グループはセットをより細かく操作できるようになりました。 「確率変数を扱うことは、どういうわけかセットを扱うことよりもはるかに厳格ではありません」とマナーズ氏は言いました。 確率変数を使用すると、「確率の XNUMX つを少しだけ微調整できるので、より良い確率変数が得られるかもしれません。」

この確率論的な観点を使用すると、グリーン、マナーズ、タオは、セット内の要素の数を扱う作業から、エントロピーと呼ばれる量である確率変数に含まれる情報の測定に移行することができました。 エントロピーは加法的組み合わせ論にとって新しいものではありませんでした。 実はタオちゃん しようとした 2000 年代後半にこのコンセプトが普及しました。 しかし、多項式フライマン-ルザ予想でそれを使用しようとした人はまだ誰もいませんでした。 グリーン、マナー、タオは、それが強力であることを発見しました。 しかし、彼らはまだその推測を証明できなかった。

グループが新しい結果を噛み締めながら、ガワーズの眠っていたアイデアを開花させることができる環境をついに構築したことに気づきました。 要素の数ではなく、エントロピーを使用してセットのサイズを測定した場合、技術的な詳細ははるかに適切に解決される可能性があります。 「ある時点で、20 年前にティムが出した古いアイデアのほうが、私たちが試していたアイデアよりもうまくいく可能性が高いことに気づきました」とタオ氏は語った。 「そこで私たちはティムをプロジェクトに戻しました。 そして、すべてのピースが驚くほどうまく組み合わされます。」

それでも、証明がまとまるまでに解明すべき詳細がたくさんありました。 「私たち9人全員が他のことで非常に忙しかったのは、ある意味愚かでした」とマナーズは語った。 「この素晴らしい結果を発表して世界に伝えたいと考えていますが、実際にはまだ中間試験を書かなければなりません。」 最終的にグループは押し進め、XNUMX月XNUMX日に論文を投稿した。 彼らは、もし A + A よりも大きくない k の倍の大きさ Aをタップし、その後、 A 約程度しかカバーできない k¹² 以下のサブグループのシフト A。 これは潜在的に膨大な数のシフトになります。 ただし、これは多項式であるため、指数関数的に速く増加するわけではありません。 k 大きくなる k 指数の中にありました。

数日後、タオさんは が始まった 証明を形式化する。 彼は、バージョン管理パッケージ GitHub を使用して、次のメンバーからの貢献を調整し、共同で正式化プロジェクトを実行しました。 世界中の25人のボランティア。 彼らは、と呼ばれるツールを使用しました 青写真 によって開発されました パトリック・マソパリ・サクレー大学の数学者、タオの言葉を翻訳する取り組みを組織する 呼ばれます 「数学英語」をコンピュータコードに。 ブループリントでは、とりわけ、 チャート 証明に含まれるさまざまな論理的ステップを示します。 すべての泡がタオの言うところの「美しい緑の色合い」で覆われると、チームは完成しました。 彼らは論文内にいくつかの非常に小さなタイプミスを発見した — オンラインで メッセージ, タオ氏は、「プロジェクトの最も数学的に興味深い部分は形式化するのが比較的簡単だったが、最も時間がかかったのは技術的な『明白な』ステップだった」と述べた。

マートンは、彼女の有名な予想が証明されるわずか数年前に亡くなりましたが、その証拠は彼女の考えを反映しています 人生の仕事 エントロピーと情報理論について。 「私がやろうとしていたフレームワークよりも、このエントロピー フレームワークで実行した方が、すべてがはるかにうまく機能します」とガワーズ氏は言いました。 「私にとって、それはまだどこか魔法のように思えます。」

クアンタ では、視聴者により良いサービスを提供するために一連のアンケートを実施しています。 私たちのものを取ってください 数学読者アンケート そしてあなたは無料で当選するためにエントリーされます クアンタ マーチ。