A research project has successfully formalized a proof in Lean 4—a functional programming language and interactive theorem prover—demonstrating that integer multiplication can be performed in worst-case time of O(n (log n)^(1-κ)). In this context, 'n' represents the total encoded input length, and 'κ' (kappa) represents the exponent saving over the standard O(n log n) complexity. The project, hosted on GitHub as `integer-mult-bounds-lean`, provides a formal verification of a fixed multitape Turing machine that multiplies every pair of natural numbers using standard binary encodings.
The specific construction achieves a kappa value of approximately 0.0000468908 (or 2^-14.38). This result is significant because it represents a measurable improvement over previous historical bounds. The mechanism involves a complex architecture of 'rounded synthetic layers' and 'compact controls' on a T16 node. The proof includes the entire pipeline of the operation, from input preparation and distribution to the final transforms, output, and cleanup. By using Lean 4, the researchers ensure that the proof is mathematically sound and that the machine's transition functions—which only see the finite state and scanned symbols—adhere strictly to the defined semantics.
While the current kappa value is a milestone, the project is moving toward a long-term goal of an unconditional kappa of 0.0023. This would involve integrating a 'Design-B' compiler and a finite mixed-to-uniform compiler. Currently, the 'Design-B' compiler is in progress and is projected to offer a saving of roughly 0.0000600, which is about 28% higher than the current result. The project also maintains a 'native-machine' target, which is a deterministic machine with a fixed alphabet and one-dimensional tapes, though its current exponent saving is smaller than the active Mathlib result being pursued for the primary improvement route.