← All papers
First page of Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points

Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points

Srihari Nanniyur, Siddhartha Jayanti

cs.DS Mar 14, 2026 · v1
Machine-verifies correctness of Toom-Cook multiplication in Lean 4 with Mathlib, using the Aristotle AI prover.
We present a machine-verified proof of the correctness of Toom-Cook multiplication with generalized integer evaluation points. Toom-Cook is a class of fast multiplication algorithms parameterized by a triple $(k_x, k_y, \vec v)$ consisting of two positive integer split sizes $k_x, k_y$ and a vector $\vec v$ of distinct evaluation points. As part of our proof, we verify that for any selection of $k_x+k_y-1$ distinct integer evaluation points, we can compute a threshold function $θ(k_x, k_y, \vec v)$ such that, if the algorithm's base-case problem size is set above this threshold, then the algorithm's termination is guaranteed regardless of the values of the operands. The threshold formula, which we derive by obtaining upper bounds on the subproblem sizes produced by the Toom-Cook recurrence, does not depend on the operands; it depends only on $k_x$, $k_y$, $\vec v$, and the base $b$ in which we operate. We write the proof in Lean 4, making use of the Mathlib library. We formalize the algorithm, our base case threshold formula, and our key lemma statements in Lean. We then use the AI theorem prover Aristotle to assist in completing the machine verification of the algorithm's correctness. This proof, through its synthesis of human input and AI assistance, demonstrates the considerable power of AI to automate the machine verification process.

Toom-Cook multiplication is a family of fast integer multiplication algorithms, but proving correctness and termination for general integer evaluation points has not been machine-verified. Determining a base-case threshold that guarantees termination regardless of operand values was an open verification challenge.

The authors formalize Toom-Cook multiplication in Lean 4 with Mathlib, parameterized by split sizes (kx, ky) and a vector of distinct integer evaluation points. They derive upper bounds on subproblem sizes in the recurrence to compute a threshold function theta(kx, ky, v) depending only on the parameters and base b, not on operands. The AI theorem prover Aristotle assists in completing the machine verification.

A fully machine-verified proof of correctness and termination for Toom-Cook with arbitrary integer evaluation points is produced. The threshold formula guarantees termination for any operands when the base-case size exceeds theta, verified end-to-end in Lean 4.