素数の隠れた構造を明らかにするブレイクスルー

 (science.org)
1 ポイント 投稿者 GN⁺ 2024-08-02 | 1件のコメント | WhatsAppで共有
  • James Maynard と Larry Guth による5月31日のプレプリントが、リーマン予想の特定の例外を排除し、素数分布の隠れた構造を探る165年来の難問に数十年ぶりの進展をもたらした
  • 中心となる対象はリーマンゼータ関数の非自明な零点で、Gauss による素数個数の推定と実際の素数分布との誤差を理解することに直接つながっている
  • コンピューターは10兆個を超える零点がすべて実部 1/2 にあることを確認しているが、数学者が求めているのは経験的な検証ではなく、別の位置が不可能であることの証明である
  • 今回の成果は、1940年の Albert Ingham 以来改善されていなかった3/4地点における零点数の上限を引き下げ、解析的整数論と調和解析を組み合わせて古い壁を破った
  • リーマン予想の完全な証明はなお遠いが、より短い区間で素数の個数を推定し、整数論の他の問題に取り組むための新しい道具につながる可能性がある

素数分布を読み解くリーマン予想

  • すべての自然数は、自分自身と1でしか割り切れない素数の積に分解でき、数学者たちはこの素数が数直線上でどのように並ぶのかを理解しようとしてきた
  • 素数は一見するとかなりランダムに見えるが、その中には隠れた構造があると考えられている
  • 過去165年間、その構造を探る中心にはリーマン予想があった
    • 証明されれば、素数を読み解くロゼッタストーンのような役割を果たしうる
    • Clay Mathematics Institute による100万ドルの賞金が懸けられている

Gauss の推定とゼータ零点

  • Carl Friedrich Gauss は1700年代末、16歳のときに素数は大きくなるほどまばらになることに気づき、X 以下の素数の個数はおおよそ X / ln X に比例すると推定した
  • この推定は、実際の素数の個数が曲線の上下に少しずつ揺れ動く形で、非常によく一致してきた
  • Bernhard Riemann は1859年、リーマンゼータ関数を用いて Gauss の曲線と実際の素数分布との差を扱おうとした
    • この関数は、実数成分と虚数成分をあわせ持つ複素数を入力として受け取る
    • リーマンゼータ関数が0になるゼータ零点は、Gauss の曲線周辺の誤差の変動を直接記述する

リーマン予想が求める制約

  • リーマン予想は、負の入力から生じる一部の自明な解を除けば、すべてのゼータ零点の入力において実部が 1/2でなければならないと予測する
  • この予想が真であれば、素数個数の変動は制限され、数直線上の素数分布に大きな塊や大きな隙間がないことを意味する
  • これまでにコンピューターは10兆個を超える非自明なゼータ零点を調べており、すべて正確に実部 1/2 上にあった
  • しかし経験的な検証だけでは十分ではない
    • Maynard は、証明は単に真であることを確認するだけでなく、なぜ真なのかを理解させ、素数を扱う強力な新手法を与えるものだと見ている
    • リーマン予想を証明するためのもっともらしい攻め筋さえ、まだ存在しない

今回の結果が狙った狭い隙間

  • 数学者たちはリーマン予想全体を直接証明できないため、ゼータ零点が存在しえない領域を狭める形で問題を分割して扱ってきた
  • 非自明なゼータ零点は、すでに0と1の間に閉じ込められている
  • また 1/2 を中心とする鏡映対称性があり、3/4地点の零点を排除すれば、1/4地点の零点も排除される
  • 従来の手法は 1/2 から 3/4 の間、または 3/4 から1の間ではよりうまく機能していたが、多くの零点が 3/4 に隠れている可能性は残っていた
  • 3/4 に位置しうる零点数の最良の上限は、1940年の英国の数学者 Albert Ingham の結果であり、その後誰もこれを改善できなかった

Maynard と Guth のアプローチ

  • Maynard は解析的整数論を専門とし、2022年に Fields Medal を受賞した数学者で、この10年間、毎週金曜の午後にこの問題を繰り返し考えてきたが、成果を得られずにいた
  • 2020年の American Mathematical Society の会合で、Maynard は調和解析を専門とする MIT の Larry Guth に助力を求めた
    • 調和解析は、物理学のアイデアを借りて音を構成音に分解する方法に関わる技法である
    • Guth も数年にわたってこの問題に取り組み、諦める直前に Maynard とともに突破口を見いだした
  • 2人はそれぞれの数学的言語から戦略を借り、深夜にメールでアイデアをやり取りしながら、非伝統的な方法でIngham の上限を破った

整数論全般へ広がる可能性

  • Maksym Radziwill は今回の研究を、ゼータ零点探索における50年ぶりの新しいアイデアだと評価し、長く放置されていた領域が再び動き出す可能性があると見ている
  • 改善された上限はリーマン予想全体の証明にはほとんど役立たないが、整数論全般に影響を与える可能性がある
    • 数学者は、より短い区間で素数の個数をよりよく推定できるようになる
    • Radziwill は、新しい戦略が自身の力学系に関する以前の研究を単純化する助けになる可能性があると見ている
    • Kakeya 問題にも役立つ可能性がある
    • Guth は、波の物理学と数の集合の分布との深い関係を探るために、このアイデアを使うことに関心を持っている

関連記事

1件のコメント

 
GN⁺ 2024-08-02
Hacker News のコメント

  • 5月に出た内容で、すでに Quanta により良い記事が掲載され、ここでも議論されていた
    https://www.quantamagazine.org/sensational-proof-delivers-ne...

  • この発見が素数に関するさらに大きなブレークスルーにつながり、大きな整数の素因数分解が容易になって、RSA のような公開鍵暗号が一夜にして無力化されるところを想像してみる
    コンシューマー向け CPU でも実運用サイズの鍵を誰でも破れるようになった場合、業界にはこうした状況に備えた災害復旧計画があるのだろうか？ 大手企業は、破られていない別の暗号体系へ素早く移行できるのだろうか？ 脱獄開発者やコンソール改造者、「デバイスの自由」を求める側にとっては天国のような日だろうが、全体への影響は壊滅的で、見積もるのも難しそうだ
    業界は突然の数論的ブレークスルーを起こり得る出来事とは見ていないのかと思う

    • RSA ではそうしたことが何度もあった
      米国政府が長い RSA 鍵の輸出を制限していた時期があり、かつて世界のかなりの部分が 128ビット RSA 鍵を使っていたが、Dixon 法のために急いで512ビット鍵へ移行した。その後、特殊数体篩（special number field sieve）のために1024ビットへ、一般数体篩（general number field sieve）のために再び2048ビットへと急いで引き上げられたが、相対的に見てそれほど昔の話でもない
      80年代の RSA 暗号化ハードウェアを見ると、512ビットを処理できることを誇らしげに掲げている機器がある。今では役に立たない
      https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf
      特殊/一般数体篩の複雑度の式は定数がいくつか違うだけだが、その定数を見ると、これが根本的な限界に見えるのか疑問に思う。その定数をさらに下げて、2048ビット鍵すら役に立たなくする方法がないと見るのは、本当に難しいのではないかと思う
      「RSA が破られたら何が起きるのか」と問う必要はない。こうしたことを何度も経験してきた立場からすると、また鍵サイズの引き上げに慌て、漏えいの可能性があるデータをすべて監査することになる、とすぐに言える
    • コンシューマー向けハードウェアで大きな整数を簡単に素因数分解する方法が見つかれば、RSA は主要な公開鍵アルゴリズムの一つなので非常に苦しいことになる
      ただし心配する前に、RSA がこれまで47年間の積極的な暗号解析に耐えてきた点を考えるべきだ。その間、より優れているとして提案された代替アルゴリズムは多かったが、しばらくして破られたものも多い
      楕円曲線アルゴリズムへ移行しようという流れも、主にはコンピューターが暗号化/復号をより簡単に処理できるからだ
      個人的に、10年後にも残っている公開鍵アルゴリズムに賭けるなら RSA に賭ける
    • この点で楕円曲線への移行が出てくるように思うし、署名とハンドシェイク（Diffie-Hellman）のどちらもすでにかなり進んでいるようだ
      災害復旧が1分で終わる作業ではないだろうが、RSA/DH が一夜にして安全でなくなるとしても、すべてがそのまま丸裸になるとは思えない。自分の SSH 鍵も今では複数の方式が混在している
    • 業界はひどい CrowdStrike アップデート一つにも備えられなかったが、それでも数日ほどで収拾はつけた
      壊滅的なシナリオに備える能力は過大評価され、生き残る能力は過小評価されているように思う
    • 高速な素因数分解の発見は極めてまれだと見る考え方がある。多くの賢い人たちが調べてきたのだから、今のところおそらく不可能だ、というものだが、その話自体が弱点なのかもしれない
      このリスクは、大規模な太陽嵐で電力網が崩壊し、変圧器製造の遅れと備蓄不足のために石器時代のような複数年にわたる復旧期間を経験するリスクと同じくらい現実的だが、その観点ではあまりに小さく理論的なので、多くの時間を費やすのは難しそうだ
      計画については、単に ECC に切り替えるのがそれほど簡単なのか分からない。ECC の実際の非対称暗号化は共有秘密に依存しているが、RSA が破られて交換チャネルが安全でないと仮定すると、RSA より中間者攻撃に脆弱になる可能性がある。簡単な置き換えではなさそうだ
      それとは別に、RSA はすでに破られており、その解法が暗号解読機関によって秘密に保たれている可能性もある。彼らにとってはブレークスルーを隠すことは非常に魅力的だろうし、「突然の数論的ブレークスルー」を抑え込む方法を探そうとするかもしれない

  • 人々はいつも素数の構造は複雑だと考えがちだが、実際には以前の間隔の倍数が到達できなかった間隔の大きさの再帰的構造にすぎないのだと思う
    以前の間隔をすべて追跡せずに「予測」しやすくなるわけではないが、本質的に複雑な構造ではない。こんな単純な構造がこれほど捉えにくいというのが面白い。3n+1 数列が複雑性を生んだり、ロジスティック写像がしきい値を超えると複雑になるのと似ている

    • 「すべての素数」を生成する生成器はかなり単純で決定的である
      しかし素数 n だけが与えられた状態で次の素数を得るには、非自明な剰余を再計算しなければならないため、数 n の二進表現だけでは次の素数が何かを素早く答える情報が十分にない。まずいくつかの基準点を事前に計算しておく必要がある。結局、複雑度はさらにあるものの、それでも単純で自明な部類であり、NP にすら入る問題ではない
    • ああ、そうだった。数学の中でも最も厳密で知的に威圧的な分野の一つである数論の基礎理論を与えることほど単純なものはないよね /s
    • なぜこれが解決済みの問題と見なされないのか気になる
      https://en.wikipedia.org/wiki/Information_theory
      https://en.wikipedia.org/wiki/Computational_irreducibility
      https://en.wikipedia.org/wiki/Aperiodic_tiling

  • 「専用の金曜午後の思考セッションで、彼はこの10年間ずっとこの問題に立ち返ってきたが、成果はなかった」というくだりは励みになる

    • Richard Hamming も金曜午後を深く大きなことを考える時間として空けていたと記憶している。素晴らしいやり方だ

  • Gauss 曲線とRiemann 曲線を特定の空間に描くと、さらに魔法めいたものが見える
    自明な零点と非自明な零点について何を言っているのかを見るには、この Wikipedia のアニメーションを見るとよい: [https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_I...](https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_Im_1_to_51.ogg)
    基本的には、実数と虚数の間に、まだ発見されていない別の関係があることを示唆しているのだと思う
    そして Riemann の数学は量子力学に関わっているので、これは重力理論を探すうえでも含意がある
    素数が重力理論に関わっている、あるいは関わり得るという点が、奇妙な科学のように感じられる

  • 「彼らはついに Ingham の境界を破るために、いくつか非正統的な手を打った」という表現が気になる
    他分野の方法を持ち込むことがなぜ非正統的なのか？ 工学の背景からすると、むしろよくあることだ。調和解析はオーディオ、波、電気解析、統計など多くの分野の基本ツールであり、そのアルゴリズムも内部的には純粋数学である
    ある基底系で反復構造を見つけたいなら、さまざまな描画手法を試し、問題に最も合うものを選ぶのが普通ではないかと思う

    • 引用文は、そのアプローチで非正統的な部分が単に調和解析のアイデアを使ったという意味には読めない。数論で調和解析を使うことはまったく新しいことではない
      解析的数論の最初の講義での核心的なアイデア、そして Riemann の有名な1859年の論文の核心的なアイデアは「調和解析」と言える。Riemann はこの分野の先駆者だったので、偶然でもない: https://old.reddit.com/r/math/comments/16bh3mi/what_is_the_b...
      現在の数論で最も熱い大きな潮流も、本質的には数体上の「高次元」調和解析である: https://en.wikipedia.org/wiki/Automorphic_form, https://en.wikipedia.org/wiki/Langlands_program. Langlands プログラムが一般化しようとしている一次元の場合は https://en.wikipedia.org/wiki/Tate%27s_thesis で、「数体上のフーリエ解析」とも呼ばれ、20世紀の数論で最も重要なアイデアの一つである
      Guth-Maynard 論文の引用文献の中には、1994年の本 H. Montgomery, Ten Lectures On The Interface Between Analytic Number Theory And Harmonic Analysis, No. 84. American Mathematical Soc., 1994 もある。1994年の時点ですでに10講分の接点があり、その本の引用数を見れば、はるかに多くの接点があったことがわかる。私も自分の論文の半分以上でこの本を引用した
      驚くべきなのは調和解析を使ったという事実そのものではなく、どこにどのように適用したかである。これは一般読者に伝えるのが本当に不可能な部分なので、記事の書き手を責めたいとは思わない
      「つながりを作ることがなぜ驚きなのか」と言っているように聞こえるが、ブレークスルーはしばしば新しいつながりから生まれるし、そうしたブレークスルーが時々起こるからといって、新しいつながりが驚くべきものではないということにはならない
    • 「非正統的」は少し強い表現かもしれないが、言おうとしているのは、別分野の既存手法を新しい形で適用したということだろう
      数学では、一見無関係に見える二つの領域の間の平行性を誰かが見抜き、一方の領域のアイデアをもう一方の領域への洞察として使う、という形の大きなブレークスルーがかなり頻繁にある
      難しいのは、こうした領域間のつながりはたいてい明白ではないという点にある。類似性を見るには、かなりの理解の飛躍が必要になることがある
    • 少しおかしな表現だ。記者が記者らしく書いただけだ
      数学のあらゆる発見には、ある程度「非正統的」な手が入っているとも言える。正統とは結局、これまで知られているすべてのことなのだから

  • 「一見するとかなりランダムに見えます。しかし実際には、素数の中にはこうした隠れた構造があると考えられています」という言葉から、仮想的な素数パターンとはどのようなものなのか気になる
    何か閉形式の公式のようなものが期待されているのだろうか？ リーマン予想が証明されたら、分布を理解するための次のステップは何になるのだろう？ それとも、その証明自体にこの答えが含まれていると期待されているのだろうか？

  • James Maynard の話を聞くたびに、彼は一世代に一人の天才だという思いがさらに強くなる
    すでに素数論に非常に多くの貢献をしており、自分が生きているうちにリーマン予想の証明が出るかもしれないという気がしてくる

  • 初めて見る図だが引き込まれるものがあり、気になる。素数を極座標グラフで描いたときに現れるパターンは最近発見されたものなのか、それとも昔から知られていて単に挿絵として使われているだけなのか？ 名前と歴史が知りたい

  • 少し脇道にそれるが、この一文は、自動証明器が扱う側面のうち、私たちがまだ考え始めているかどうかも分からない部分を思い起こさせる
    「Rutgers University の数学者 Alex Kontorovich は『それはセンセーショナルなブレークスルーです。この証明には、今後数年にわたって人々が掘り出すことになる新しいアイデアがぎっしり詰まっています』と語る」
    何かの証明は、厳密性を与える手段というより、その対象を見る新しい視点としてのほうが興味深い場合が多い。自動化された数学で、そうした方向の取り組みがあったのか気になる