最近提出的 o(n log n) 整数乘法算法 [pdf]
一项新的 AI 生成结果声称给出了一个运行时间严格优于 O(n log n) 的整数乘法算法，这让数学家和技术人员既兴奋又不安。评论者们梳理了 big-O 与 little-o 记号之间的技术细节，指出该算法很可能只对天文数量级的整数具有理论意义，并争论这种“银河级”改进在实践中究竟有多大价值。讨论的大部分内容围绕着：AI 系统生成的复杂证明，即使是顶尖人类专家也难以完全理解，这意味着什么；以及这对验证、对公司控制模型的依赖、和以人类为中心的数学研究未来会带来哪些问题。
渐近记号与 o(n log n) 的含义
- 多条评论澄清了 big-O 和 little-o 之间的区别。
- Big-O 被描述为“≤”（在常数意义下的上界），little-o 则是严格的“<”（增长严格慢于任何常数倍）。
- 多位发帖者纠正了不够精确的解释（例如错误地写成 o(2n+1) > o(2n) > o(n) 这样的链式关系）。
- 还有一些关于基于极限的定义（f/g 有界 vs f/g → 0）以及 Θ、Ω 及其“等号/不等号”类比的讨论。
新整数乘法结果的性质与实用性
- 其意义在于这是 o(n log n)，在渐近意义上比经典的基于 FFT 的 O(n log n) 严格更快。
- 多位评论者强调这是一种“银河级算法”：这种渐近改进只对天文数字般巨大的整数才有意义，远远超出任何实际用途。
- 现有的 O(n log n) 及相关基于 FFT 的方法，本来也并不用于大多数现实世界中的整数规模。
- 文中提到有人对一个 o(n log n) 上界做了 Lean 形式化（其中一个具体指数略小于 1）；欢迎贡献。
AI 生成的证明与数学理解
- 一个核心主题是：这个来自“公司”的新结果即使对顶尖专家来说也很难阅读，于是他们转而借助 LLM 来理解论文。
- 有些人认为这是一种自然且有用的新工作流：如果人类无法解析某种表述，但工具可以，那就用工具。
- 也有人称这是一种“不健康”的现象，认为数学本质上关乎人类理解和清晰交流，而不只是正确性。
- 对 LLM “理解”的能力存在怀疑，理由包括幻觉、缺乏自我评估能力，以及用 AI 检查 AI 的风险。
- 形式化证明助手（如 Lean）被视为更值得信赖，但仍受限于实现层面可能存在的 bug。
哲学与社会层面的担忧
- 讨论数学是否必须对人类可理解才有价值；有人认为不可理解的证明在被简化或应用之前，实际上是无用的。
- 有人担心前沿级“智能”正在变成少数公司的财产，甚至出现国家或企业对关键数学能力进行门控的情景。
- 几条评论把这描述为人类控制力和自主性的流失，并将强大的 AI 比作我们无法完全理解其运作机制的精灵。
对行文与语气的反应
- 许多人称赞这篇文章的文笔、坦诚，以及它传达出数学界情绪冲击的能力。
- 也有人批评“我其实没读过论文”这种立场，认为即便出于自嘲，这也有问题。