Exact integer multiplication with saving κ = 0.003287014
OpenIntMul.Kappa.conditional_kappa_003287014_pr6453There 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.
import Definitions.Def_IntMul_MultitapeModel
namespace IntMul.Kappa theorem conditional_kappa_003287014_pr6453 : KappaBound (0.003287014 : ℝ) := by sorry end IntMul.Kappa
Read-back
What the Lean code literally says, in plain math · claude-sonnet-5-5
Read-back of IntMul.Kappa.conditional_kappa_003287014_pr6453 (written blind by an independent auditor from the Lean code and the imported definitions only)
The statement has no hypotheses and no free variables. It asserts one closed proposition: KappaBound κ for the specific real number κ = 0.003287014 = 3287014/10^9. The proof body is sorry.
KappaBound κ unfolds to MulTimeBound g_κ, where g_κ(n) = n · (lg n)^(1−κ) and lg n = max(⌈log₂ n⌉, 1); the exponent is the real number 1−κ = 0.996712986 (real exponentiation).
MulTimeBound g says there exists a deterministic multitape Turing machine M such that (1) for every n ≥ 1, M halts correctly on all pairs of n-bit inputs within some finite step bound; and (2) there exist a real c > 0 and a natural n₀ such that for every n ≥ max(n₀, 1) and every pair of n-bit strings x, y, M halts with exactly the output ▷ followed by the 2n-bit binary representation of val(x)·val(y) (most significant bit first, zero-padded on the left) and then blanks, in at most c·g_κ(n) steps. M, then c, then n₀ are chosen in that order; c and n₀ are otherwise unrestricted.
The machine model: finite alphabet with distinct blank, start marker ▷, 0, 1 and separator #; finite state set with distinct start and halting states; k ≥ 2 tapes (tape 0 read-only input holding ▷ x # y, tape 1 output, the rest work tapes); a transition function δ constrained so that ▷ is never overwritten and never moved left across, ▷ is never written elsewhere, the halting state freezes the configuration, and the input tape is never changed. Nothing is required of the other tapes or head positions at halt. No bound is placed on the number of tapes, symbols or states beyond finiteness (fixed once M is chosen).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.