AI-Verified Lean Proof Shows Quartic Polynomials Need Only Two Multiplications
thomasahle · x · 2026-09-11
A fun result done without AI but verified by AI in Lean: any quartic polynomial can be evaluated with just two multiplications via y = (x + b₀)x + b₁, then P(x) = (y + x + b₂)y + b₃. The author's original 100-page proof sat unpublished for years until the Lean verification. Context: Knuth showed n/2 multiplications suffice for degree n, but his preprocessing needs complex roots — numerically unstable and useless over finite fields; Rabin & Winograd's rational fix costs 2log n extra multiplications. With polynomial evaluation everywhere from exp/sin to cryptographic hashes, a 2x speedup over finite fields matters.
More from Research
- HABIT-Bench: Best agent memory system scores just 33.61% at inferring user habits — SJTU · 2026-10-28
- MatAnyone-E brings 7.4x faster 4K video matting via sparse memory propagation — mmlab-ntu · 2026-10-28
- CodeCap-Bench: executable code beats natural language as video captions — Jiafu Tang · 2026-10-28
- NVIDIA's ThinkWorld learns robot skills from unlabeled human videos via chain-of-dynamics reasoning — nvidia · 2026-10-28
- Omni-InteractScope benchmarks proactive interaction in continuous omnimodal streams — Qwen · 2026-10-28
- Memory Tax study: dedicated agent memory systems often lose to naive RAG — UIUC-CS · 2026-10-28