OpenAIが整数乗算のn log n限界を破る論文を公開
Integer multiplication below n log n
OpenAIのmathリポジトリに「Integer multiplication below n log n」と題する論文が公開された。整数乗算の計算量がn log nを下回る可能性を示すもので、長年信じられてきた限界に挑戦する内容。論文はGitHub上で閲覧でき、関連する多数の数学プレプリントとともに並んでいる。
HNでの議論
80- TGower
我々はnlognから1/6129982163463555433433388108601236734474956488734408704を削り取った
- shmoil
n lg n ^ (1 - 2^{-182})には声を出して笑ってしまった。あまりにも面白い。
- wk_end
これには機械検証された証明が付随しているのか?
職場では完全にバイブコーディングモードなので、フロンティアモデルがどれほど強力か、そしてどれほど頻繁に自信過剰に微妙に(あるいはそうでもなく)間違ったことを述べるか、それを防ごうと多大な努力をしてもなお、よく理解している。
だからLeanによる開発や広範な人手による検証がない限り、少し懐疑的だし、むしろこれは間違っていてほしいとさえ思う。AIに対する肯定的でない感情のせいだけでなく、数学における美しさに対する私の性向からしても。n log nはここにあるものよりずっとずっと美しい。