A simpler algorithm for integer multiplication below n log⁡n\log n, with a formally verified proof

Piaoyang Cui, Yiming Liu, David P. Woodruff

The authors give a multitape Turing-machine algorithm multiplying two n-bit integers in O(n(log⁡n)(1−κ))O(n(\log n)^{(1-\kappa )}) bit operations with κ=2−46\kappa = 2^{-46}. It reuses two fixed small networks from the prior construction and replaces the surrounding architecture with a single-grid method.

What was already known

An earlier sub-n log⁡n\log n algorithm used the two fixed networks inside the Harvey–van der Hoeven architecture and gave κ=2−182\kappa = 2^{-182} as stated in the comparison.

AI involvement AI-centered

Google credits its multi-agent campaign with simplifying the sub-n log⁡n\log n algorithm. The short paper credits language models with algorithmic simplification, Lean scripts and exposition. The authors verified the mathematical statements and the formal specification.

Importance Notable

The paper simplifies the architecture of a sub-n log⁡n\log n multiplier and improves the certified exponent in that comparison.

Technical verification Formal (Lean)

The Lean archive checks the multitape running-time bound and its finite network certificates under the standard Lean axioms. The short paper reports a separate check of exported proof terms.

Formal checking

Checked the multitape complexity bound and its finite network certificates.

Checker
Lean 4 kernel
Scope
The authors give a multitape Turing-machine algorithm multiplying two n-bit integers in O(n(log⁡n)(1−κ))O(n(\log n)^{(1-\kappa )}) bit operations with κ=2−46\kappa = 2^{-46}. It reuses two fixed small networks from the prior construction and replaces the surrounding architecture with a single-grid method.
Basis
Reported by the linked checker

Human understanding Few

The paper describes the architecture and division of checking work. It leaves the authors’ independent reconstruction of the model-assisted simplifications undocumented.

Other useful sources

Correction and publication history