What was already known
An earlier sub-n algorithm used the two fixed networks inside the Harvey–van der Hoeven architecture and gave as stated in the comparison.
AI involvement
Google credits its multi-agent campaign with simplifying the sub-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.
- Google’s account of the multiplication campaignGoogle’s account of the multiplication campaign
- Short paper’s AI disclosureShort paper’s AI disclosure
Importance
The paper simplifies the architecture of a sub-n multiplier and improves the certified exponent in that comparison.
Technical verification
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 bit operations with . 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
- Lean development for the multitape boundLean development for the multitape bound
Human understanding
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
Reviewed the primary result and its documented AI and checking scope.
Read this published revision