Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points

Srihari Nanniyur, Siddhartha Jayanti · 2026

Read Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points by Srihari Nanniyur, Siddhartha Jayanti (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14038.txt.

Introduction

Nanniyur and Jayanti present a machine-checked proof that Toom-Cook multiplication is correct for general integer evaluation points. Toom-Cook splits numbers into parts and rebuilds the product from values at chosen points. The proof covers any split sizes and any distinct integer points. A key step is a formula for the base-case threshold that guarantees the recursion ends. The proof is written in Lean 4 with Mathlib, with help from the AI prover Aristotle.

Catalog record

CREATORSrihari Nanniyur, Siddhartha Jayanti
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45476
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14038

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points Srihari Nanniyur, Siddhartha Jayanti Abstract 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 , v → ) \displaystyle(k_{x},k_{y},\vec{v}) consisting of two positive integer split sizes k x , k y \displaystyle k_{x},k_{y} and a vector v → \displaystyle\vec{v} of distinct evaluation points . As part of our proof, we verify that for any selection of k x + k y − 1 \displaystyle k_{x}+k_{y}-1 distinct integer evaluation points, we can compute a threshold function θ ⁡ ( k x , k y , v → ) \displaystyle\theta(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 \displaystyle k_{x} , k y \displaystyle k_{y} , v → \displaystyle\vec{v} , and the base b \displaystyle 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. 1 Introduction Large integer multiplication has applications across mathematics, computing, and physics. While the standard long multiplication (a.k.a. grade-school multiplication ) algorithm takes \displaystyle O(n^{2}) time to multiply two operands of \displaystyle n digits each, there are several fast multiplication algorithms that achieve an asymptotic speed-up, including Karatsuba ( \displaystyle O(n^{\log_{2}3}) ) [ 15 ] , Toom-Cook ( \displaystyle O(n^{1+\varepsilon}) ) [ 19 , 6 ] , Schönhage-Strassen ( \displaystyle O(n\log n\log\log n) ) [ 18 ] , and Harvey-van der Hoeven ( \displaystyle O(n\log n) ) [ 13 ] . Toom-Cook, the focus of this paper, is actually a class of algorithms parameterized by a triple \displaystyle(k_{x},k_{y},\vec{v}) consisting of two positive-integer split sizes \displaystyle k_{x},k_{y} and a vector \displaystyle\vec{v} of distinct evaluation points . In particular, to multiply \displaystyle x and \displaystyle y , the algorithm uses a divide-and-conquer approach that splits \displaystyle x into \displaystyle k_{x} pieces, splits \displaystyle y into \displaystyle k_{y} pieces, and constructs two polynomials \displaystyle p and \displaystyle q whose coefficients are the pieces of \displaystyle x and \displaystyle y respectively. It evaluates the polynomials at each of the points in the vector \displaystyle\vec{v}=\langle v_{1},\cdots,v_{k_{x}+k_{y}-1}\rangle , computes pointwise products to determine the pointwise evaluation of \displaystyle p\cdot q , and uses efficient polynomial interpolation to compute the final result. In the common case where \displaystyle k_{x}=k_{y}=k , Toom-Cook achieves a time complexity of \displaystyle O(n^{\log_{k}(2k-1)}) ; the exponent can get arbitrarily close to 1 at the expense of a fast-growing constant term hidden by the big- \displaystyle O [ 7 ] . Toom-3, i.e., Toom-Cook where \displaystyle k_{x}=k_{y}=3 , is widely used for fast multiplication of mid-to-large sized integers [ 9 ] . Formal (pencil-and-paper) proofs of correctness have been written for subclasses of the Toom-Cook family: for example, with \displaystyle\vec{v}=\langle 0,1,\cdots,2k-2\rangle [ 6 ] . A key step in such a proof is the derivation of a base case threshold , \displaystyle\theta , which specifies the instance size—i.e., number of digits—at which to switch from the recursive case to the base case. In this work, we derive a function \displaystyle\theta(k_{x},k_{y},\vec{v}) that computes base case thresholds for arbitrary split sizes \displaystyle k_{x},k_{y}>1 and point vector \displaystyle\vec{v}\in\mathbb{Z}^{k_{x}+k_{y}-1} , where the values in \displaystyle\vec{v} are distinct. We thereby—to our knowledge—provide the first formalization of the Toom-Cook algorithm that accounts for generalized integer evaluation points. (There are some other aspects that we do not generalize; see Section 2 .) We then machine-verify the algorithm in Lean. Our proof combines manual derivation and analysis with the use of AI tools, including Aristotle [ 1 ] for proving lemma goals in Lean and GPT-5 to aid in producing formalization strategies. Along with providing the rigor of machine certification for an algorithm in widespread use, these results also demonstrate the power of emerging AI tools to save time in the important yet erstwhile lengthy process of formal verification. 1.1 Multiplication algorithms The standard long multiplication (a.k.a. grade-school multiplication ) algorithm for integers has been known since antiquity. The earliest recorded explicit specification of this algorithm, to our knowledge, is contained in Brahmagupta’s Brahma-sphuta-siddhanta (c. 7th century CE) [ 5 ] . The quadratic running time of this algorithm was conjectured to be asymptotically optimal by Kolmogorov [ 14 ] . In 1962, Karatsuba [ 15 ] refuted this conjecture by devising a divide-and-conquer algorithm that reduces multiplication of two \displaystyle n -digit operands to three multiplications with operands that have roughly \displaystyle\nicefrac{{n}}{{2}} digits, thus achieving a running time of \displaystyle O\left(n^{\log_{2}3}\right) . Toom [ 19 ] and Cook [ 6 ] vastly generalized Karatsuba’s approach, showing that by dividing each problem into more subproblems of smaller size, multiplication can be performed in \displaystyle O(n^{1+\varepsilon}) time for arbitrarily small \displaystyle\varepsilon>0 . The Toom-Cook class of algorithms is the primary subject of this paper; we detail it in Section 2 . Schönhage and Strassen showed that multiplication can be performed in \displaystyle\tilde{O}(n) time using the Fast Fourier Transform (FFT) [ 18 ] . The exact running time of their algorithm is \displaystyle O(n\log n\log\log n) ; but they conjectured that \displaystyle O(n\log n) would be achievable and optimal. A recent series of papers [ 8 , 11 , 10 , 12 ] in this domain made steady progress on this conjecture. This line of work culminated in the celebrated algorithm of Harvey and van der Hoeven [ 13 ] , which uses more complicated FFT-based techniques to achieve \displaystyle O(n\log n) time complexity. However, this algorithm is galactic, i.e., it is only efficient at problem sizes too large for any practical context [ 13 ] . The Schönhage-Strassen conjecture remains open, since there is no proof of asymptotic optimality. In fact, we are not aware of any non-trivial general lower bounds on the asymptotic time complexity of integer multiplication. 1.2 Lean, Aristotle, and AI-assisted theorem proving Our Toom-Cook proof is specified in Lean, a language for formalizing and machine-verifying mathematical proofs. Given a Lean formalization of a proof, the Lean backend is able to check that proof’s correctness. Lean provides a large number of tactics , or commands specialized for solving particular types of proof goals. We also make extensive use of Mathlib, a library of mathematical tools and lemmas implemented in Lean. Aristotle, an AI tool developed by Harmonic, is capable of generating valid Lean proofs by itself. Given a piece of Lean code containing unfilled lemma headers, Aristotle will attempt to fill in the proofs of those lemmas, making no changes to the rest of the code. Harmonic’s October 2025 white paper on Aristotle [ 1 ] provides more information

Read the complete text