Exact integer multiplication with saving (community #7000/#7001)
OpenIntMul.Kappa.community_frontier7000_boundThere 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.00363005817)), where L(n) = max(ceil(log₂ n), 1). This is the full bound with no assumed algorithmic or analytic framework. Its proof is Open. The exact value is . The source construction retains five framework assumptions; this target asks to discharge them, and does not assume them. Construction credit: Jerry Chen / CubeJerry and the contributors identified in the source notices.
import Definitions.Def_IntMul_MultitapeModel
namespace IntMul.Kappa theorem community_frontier7000_bound : KappaBound (0.00363005817 : ℝ) := by sorry end IntMul.Kappa
Read-back
What the Lean code literally says, in plain math · Codex independent blind auditor
There exists a single deterministic Turing machine , with a finite alphabet containing five pairwise distinct symbols , a finite set of states with distinct start and halt states, and a fixed finite number of tapes, such that the following conditions hold. Every tape has cells indexed by the natural numbers, including cell ; tape is the input tape and tape is the output tape. For every state and every vector of scanned symbols, the machine’s transition function specifies one next state and, for each tape, one symbol to write and one movement, left, stationary, or right. For every such transition and tape, a scanned must be rewritten as and cannot cause a left movement, and a scanned symbol other than cannot be replaced by ; the input tape’s scanned symbol is always preserved; and in the halt state every vector of scanned symbols produces the same halt state, unchanged symbols, and stationary heads. A step updates the scanned cell of every tape simultaneously and changes each head position to , , or as directed, with natural-number subtraction giving . For every integer , there exists a real number such that, for every pair of Boolean lists each having exactly entries, there exists a natural number with for which the machine, after exactly steps from the following initial configuration, is in its halt state with the specified output: initially all heads are at cell , the state is the start state, the input tape contains , then the bits of , then , then the bits of , followed entirely by blanks, while every other tape contains at cell and blanks elsewhere; the output tape at time must contain at cell , followed by exactly bits representing in most-significant-bit-first order, padded with leading zeros, and blanks in every subsequent cell, where , with false interpreted as and true as . More explicitly, output position , for , contains bit of the natural number ; these are its lowest bits, and this product is less than . In addition, there exist a real constant and a natural-number threshold such that, for every natural number satisfying both and , and every such pair , a natural number giving that same halting state and exact output exists with , where for positive and the exponentiation is real exponentiation. The machine, , and are common to all inputs; the first bound may depend on , and the halting time may depend on both inputs. The threshold may be , but no behavior is required for or for pairs of unequal lengths; leading-zero inputs and inputs representing zero are included for every positive length, and . Although the quantified time permits , the distinct start and halt states prevent that time from satisfying the required halting condition. No final head positions or final contents of work tapes are prescribed, and the chosen time need not be the first halting time because the halt state freezes the configuration.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.