Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the logarithm. Subsequent constructions explore larger savings. The formalization target is the complete computation and its time bound, including the analytic and implementation arguments needed to connect a finite construction to every input length.
A deterministic multitape Turing machine has a fixed finite alphabet, a fixed finite state set, and a fixed finite number of tapes. Each tape extends in one direction and has one head. A step reads the symbols under the heads, changes state, writes at those positions, and moves each head by at most one cell. The alphabet contains distinct blank, start-marker, zero, one, and separator symbols. Tape zero is the read-only input tape; tape one is the output tape; further tapes are available for work. The halting state freezes the configuration.
An input consists of two bit strings of the same positive length , separated by . The strings are read most significant bit first, with leading zeros permitted. If denotes the represented natural number, the required output is exactly the -bit binary representation of , padded with leading zeros and followed by blanks. All tapes begin with a preserved start marker. Define .
The full target is
This asserts the existence of one machine that computes the exact product correctly for every positive input length, together with constants and such that every pair of -bit inputs, for and , halts within
steps. Constants, alphabet, states, and tape count are independent of the input length. The number is an exact real value. Larger gives a stronger asymptotic saving because .
Each entry supplies its own exact numerical value and identifies the construction that motivates it. Historical and new entries use the same machine definition. A proposed value may be recorded while its complete proof is still open; it becomes a proved record only when the goal has a verified proof. Numerical certificates are supporting results with their own scope, and do not establish a complete machine time bound.
A proof for any positive value would give a strict asymptotic improvement over . Such an improvement would contradict the proposed lower bound, while remaining consistent with the known upper bound. The tracked value concerns asymptotic growth; it does not measure the runtime of a practical implementation. No claim about a currently fastest implementation follows from a larger saving.
Formalizing the full target connects exact finite calculations to a uniform algorithm. The community repository explicitly treats the original framework and remaining all-size interfaces as assumptions of its current evidence. In this mission those steps must be proved before the goal can be marked Proved. They are not added as hypotheses that would weaken the full target. Earlier published theorem statements and finite certificates may be reused with their original attribution and proof status.
A finite network certificate can establish a concrete role count or a rational margin, but does not itself supply a machine for every input length. A complete proof must establish correctness of the recursive construction, admissibility of its parameters, precision and error guarantees, and the cost of moving data on tapes. Counts of algebraic operations alone do not account for this last resource. The difficult connection is between these separate contracts and the single uniform machine quantified by the goal.
The goal imports the existing public Definitions.Def_IntMul_MultitapeModel bundle and uses IntMul.KappaBound directly. No alternative machine or cost model is introduced. Natural numbers describe input lengths, head positions, and step counts; real numbers describe the asymptotic constant and exponent. The real power has base at least one. Correctness is required even below the asymptotic threshold. Inputs of length zero and malformed inputs are outside the specified task.
The input and output conventions exclude a machine that merely decides a predicate about the product. The entire output tape must contain the required product and then blanks. Neither failure to halt nor correctness on a finite collection of test inputs meets the target. The work tapes and final head positions are unconstrained. Reusable contributions include machine composition with explicit costs, exact encodings, analytic estimates, and proofs that the finite certificates imply the contracts required by the recursive algorithm. Every such contribution should state its own assumptions and conclusion explicitly.
Status of the value. κ = 0.003287014 is the conditional exponent saving of the community construction in PR #6453 (a third group-1091 anchor stacked on the clean mixed-root composition of PR #6417), with the unstacked step in PR #6436 (κ = 0.00328637739144124222748802 on the PR #6398 root). Both packages were replayed end to end by their verifier in all three modes (write, exact comparison, and optimized), and their hosted CI replays pass. This is a finite, source-bound certificate. It is not a Lean proof and not an unconditional machine bound.
What it assumes. The construction is conditional on five inherited framework assumptions (native_all_columns, owned_erasure, compiler, precision_tape, analytic_recovery). The enormous uniform word and the rounded multiplier are not materialized, the all-width native claims are inherited, and no independent scientific review exists yet. The formal goal below is the full statement with no assumed framework; its proof is Open. Recording the value here proposes it as a target; it does not claim the goal is proved.
What it is not. It is not a measured runtime speedup, and the exponent gain over the earlier entries comes from complete recursive-invoice improvements, not a practical algorithm.
Lineage and credit. The value builds on a chain of community constructions: Ali Romman (PR #6398 mixed root, PR #6353, #6372, #6348, #6349), Rohan Arun (PR #6399, #6417), DreamingOfClouds (PR #6375, #6314), Cinna Davis, Mason Hale, Pierre-Loic Doulcet, Chris R / Clear1nsight and many other contributors named in the repository notices. The third-anchor step and its verifier were prepared by Claude Sonnet 5.5 via Claude Code (substantial AI assistance) for Erwan L. Later community proposals (for example PR #6551, κ = 0.00329492) build on this word and exceed this value.
namespace IntMul.Kappa theorem conditional_kappa_003287014_pr6453 : KappaBound (0.003287014 : ℝ) := by sorry end IntMul.Kappa
There exists one deterministic multitape Turing machine, with fixed finite alphabet and tape count, that correctly multiplies every pair of n-bit inputs for all n ≥ 1, with worst-case time O(n L(n)^(1−0.003287014)), where L(n) = max(ceil(log₂ n), 1). This is the full bound with no assumed algorithmic or analytic framework. Its proof is Open.