数学者デヴィッド・ハーヴェイが認める、AIが示した「ありえない」整数乗算アルゴリズムの衝撃
The recently proposed o(n log n) integer multiplication algorithm [pdf]
UNSW SydneyのDavid Harvey氏が、AIが提案した整数乗算のo(n log n)アルゴリズムに関する見解を公開。自身は論文を読まずClaudeに解説を求めたが、主張はもっともらしいと判断。従来のO(n log n)から(log n)^εへの改善は、過去の改良と比べて桁違いに大きいと強調する。人間とLLMの「思考速度」の差にも言及している。
私のコミュニティの誰もが、その帰結と向き合わなければならない。たとえば、私たちが学部生のレポートをもはや受け取らないのと同じ理由で、人間が数学研究論文の著者として真剣に扱われる期間は、そう長くはないだろう。
HNでの議論
268- jdb1729
> o(n log n) の結果について、たとえば Lean での形式化された証明があるとよい。私が知る限り、まだ存在しない。
この結果は @platypii と私によって Lean で完全に形式化されています（Mathlib の TM2 マシン上）。指数は現在 1-2^-14.38 で、改良が続いています: https://github.com/platypii/integer-mult-bounds-lean
貢献歓迎です！
- Kapura
> 私は実際に論文を読んでいない。実は、密接に関連する3つの論文 [TC26a], [TC26b], [TC26c] があり、どれも読んでいない。読もうとしたが、すぐに諦めた。数学のダンプは説明が充実しているようには見えない。代わりに、Fable に [TC26a] を説明してもらった。Fable は議論を理解しているようで、正しいと考えている。
これは健全な状態とは思えない。
- kenferry
> この状況でもう一つ強調したい側面がある。2週間の非常に
> 厳しい作業の後、私は [TC26a] のほんの一部しか理解できなかった。Fable に
> 論文について尋ねると、まったく新しいコンテキストから始めても、ほんの数分で
> 全体を読み理解するようだ。私の擬人化的な
> 用語に不快感を覚える読者もいるかもしれないが、LLM が論文に関する
> あらゆる種類の質問に、非常に細かい技術的詳細も含めて、正確かつ明快に
> 答えられるという意味で、「理解する」というのは正確だと信じている。それはまさに
> 人間の同僚が何かを「理解した」と私が判断する方法だ。この人間と LLM の
> 「思考の速さ」の隔たりは、控えめに言っても落ち着かない。
これは非常に奇妙だ。というのも、これらのシステムに関する私の経験とまったく一致しないからだ。確かに、彼らは一般に自信ありげに聞こえるが、私にとって理解が難しい（たとえば）コードは、通常、機械にとっても理解が難しい。そして、彼は私より疲れを知らないが、より賢いわけではない。
この数学者は Fable が理解しているかどうかを評価するのに非常に適した立場にいるが、それは奇妙で私の経験に反している。
- jdb1729
> 新しい結果は、固定有限体上の多項式乗算、たとえば F2[x] での乗算に対する新しい計算量限界を直接導くものではない。この問題の最先端は、次数 n の多項式を時間 O(n log n 4^log*(n)) で乗算するアルゴリズムである [HvdH19]。
@platypii と私は、素数位数の有限体上の DFT に対する同じ改良の Lean 証明を得た（畳み込み定理を介して多項式乗算を導く）: https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebron
この場合、タイトルには「O(n log n)」とあるが、重要なのはこれが「o(n log n)」であり、単なる「O(n log n)」ではないという点だ。前者は後者の真部分集合である。n ビットの整数2つを O(n log n) 時間で乗算する方法は、FFT によってすでに知られていた。
- CH-Abhinav
ここは初めてですが、これは一般的にどう役立つのですか？ ほとんどの場合、時間計算量が低くても Strassen よりも GEMM を使います。ただ聞いただけです、何も知らないので :)
- kleiba2
AI はどうやら人間のためには論文を書かないらしいというのは興味深い。専門家でさえ理解に苦しむ。しかし他の AI は理解する。つまり AI は基本的に他の AI のために論文を書いているのだ。
- yaoke259
素晴らしい記事とイントロをありがとう、シドニー出身の仲間として、夢中で読みました！ 数学の達人ではない私には、技術的な詳細は頭を素通りしましたが、その文章のおかげでこの分野の人々に深く共感でき、とても啓発されました。数学のダンプがどれほど大変なことだったか、そしてそれが分野をどれほど揺るがしたかに全く気づいていませんでした。私たちは皆、この「オンデマンドの知能」というものを一緒に解明しようとしているのだと思います。