多项式求值提速一倍：旧证明被搁置多年，今由 AI 在 Lean 中验证
thomasahle · x · 2026-09-11
作者 thomasahle 分享一个「完全没用 AI 做出、但靠 AI 完成验证」的结果：多项式可以以两倍速度求值。
- 核心事实：n 次多项式传统 Horner 求值需 n 次乘法；他们多年前证明可大幅减少乘法次数（如四次多项式仅需 2 次乘法），但证明长达上百页，作者一直没有足够把握发表。
- 转折：如今用 AI 在 Lean 中完成形式化验证，证明的正确性终于得到确认。
- 技术思路：构造 H2、H4、H8 等嵌套多项式，用「平方差」技巧 H4 = (H2+x+a)(H2-x-a) 只花一次乘法就把次数翻倍；把多项式写成系数列表（如 H4 = [1,b,c,a,e]）并从左到右可解码各参数；最后构造两个共享前缀、交错可解码的多项式 H8 与 H'8，通过 P = x·H8 + H'8 合并，保持逐系数解码性。总策略是「始终同时构建两个兼容的」。
既是算法结果，也是 AI 辅助形式化验证（Lean）助力数学发表的实际案例。
所属事件:尘封多年的多项式求值证明经 AI 用 Lean 验证后发表(4 条相关)→
「研究」频道最新
- Wiz发布Cyber Model Arena：Gemini 3.8 Flash Cyber以74.9%居首 — rseroter · 2026-09-11
- Meta 发布 Auto-RecSys：工业级推荐模型上的自主研究 agent — omarsar0 · 2026-09-11
- SW-graph 曾赢下首届 ANN-benchmarks,作者回忆 2015 年检索算法往事 — srchvrs · 2026-09-11
- 新论文：自复制程序靠合作进化涌现，博弈论统一计算起源 — AdaptiveAgents · 2026-09-11
- 首尔国立大学多目标贝叶斯优化工作坊讲义全部公开 — kchonyc · 2026-09-11
- 对齐分割新工作 AlignAndSegment 入选 ECCV 2026 — ducha_aiki · 2026-09-11