Polynomials evaluated in just two multiplications, verified in Lean with AI's help after years unpublished
thomasahle · x · 2026-09-11
A fun result—proved years ago but unpublished because the 100-page proof made the authors unsure, until AI-assisted Lean verification gave them confidence.
Core result: a quartic P(x) = x⁴ + a₃x³ + a₂x² + a₁x + a₀ can be evaluated in just two multiplications, by rewriting it as y = (x + b₀)x + b₁, then P(x) = (y + x + b₂)y + b₃, where b₀…b₃ come from cheap preprocessing of the coefficients.
Why it matters
- Polynomial evaluation underlies exp/sin computation, cryptographic hashes, and codes
- Over finite fields multiplication is especially costly, so a 2x speedup is significant
- Knuth and others showed n/2 multiplications suffice for degree n, but their preprocessing needs complex roots—numerically unstable and useless over finite fields; Rabin & Winograd's rational scheme adds 2logn extra multiplications
A neat example of human-generated math with AI/formal verification closing the confidence gap.
More from Research
- ParetoRSI-Gym benchmarks whether AI agents can recursively self-improve LLMs across domains — Haojin Wang · 2026-10-28
- Stanford's Ψ-0.6 is a unified vision-language world model with adaptive reasoning streams — Stanford · 2026-10-28
- Shanghai AI Lab's OpenESM shows energy-steered models can scale as foundation learners — Shanghai-AI-Laboratory · 2026-10-28
- CellTrack-Bench tests VLMs on microscopic cell tracking, exposing reasoning gaps — biohub · 2026-10-28
- Hybrid LLM agent scores 83.2%, beats nine VLA policies on new SO-101 robot arm benchmark — Truman Hickok · 2026-10-28
- DeepMind researcher: all of mathematics will soon be formalizable, with agents hunting proofs — ChrSzegedy · 2026-10-28