Exact integer multiplication with saving κ = 0.00006397891967576
OpenIntMul.Kappa.jain_round7Jain's round-seven witness. There is one deterministic multitape Turing machine, with a fixed finite alphabet and a fixed number of tapes, that for every and all halts on input with output , and whose worst-case running time satisfies
This is the strongest exponent saving claimed so far in the line of work started by the OpenAI preprint: S. Jain's round seven with the sharper moment certificate merged into the same repository. The project states that the claim is conditional on the OpenAI manuscript and on Colkitt's framework, that stage two is assumed rather than machine-checked, and that it has not had independent review. Its finite rational certificates are checked in the Lean kernel; the analytic inequalities they rely on and the machine construction are not. This is the full bound with no assumed algorithmic or analytic framework. Its proof is Open.
Formalization Note KappaBound κ is from the shared IntMul_MultitapeModel: one machine correct for every , and constants , with running time at most for . The decimal literal is the exact rational .
import Definitions.Def_IntMul_MultitapeModel
namespace IntMul.Kappa theorem jain_round7 : KappaBound (0.00006397891967576 : ℝ) := by sorry end IntMul.Kappa
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back of IntMul.Kappa.jain_round7. The theorem has no hypotheses or free variables. It asserts for the single real constant
which is read exactly as this rational number in . So the exponent that appears below is .
Unfolding. is defined as for the function ,
where the power is the real power of the real number , and
Here is the least with , which is for . So , , and in general for . Since , the base of the real power is always at least , and no junk values from the real power arise. Also , but is never used, as explained next.
says that there exists a single machine (in the model described below) such that both of the following hold.
- Correctness for every input size. For every there exists a real with .
- Asymptotic time bound. There exist a real and an such that for every with and , holds.
The quantifier order is . The constants and may depend on but not on , and they are not otherwise bounded.
means the following. For all bit strings (lists of booleans of length exactly ), there exists with (compared as reals) such that, started on input , after exactly steps the machine is in its halting state and its output tape holds exactly . The pieces are defined as follows.
- is the binary value of , read most significant bit first, with . Leading zeros are allowed.
- is the length- list whose -th entry () is bit of . This is the -bit binary representation of , most significant bit first and zero-padded on the left. Since , no bits are lost.
- "The output tape holds " is an equality of the entire infinite tape. Cell holds , cells hold the symbols encoding the bits of in order, and every cell beyond holds the blank .
- Nothing is required about the work tapes, the head positions, or what happens before step .
- Because the halting state freezes the configuration (see below), "halted with this output after some steps" is the same as "halts with this output within at most steps".
Machine model. A machine consists of the following data.
- Alphabet. A finite alphabet with five pairwise distinct designated symbols: blank , start , , and separator . Other symbols are allowed.
- States. A finite set of states with a start state and a halting state, which are distinct.
- Tapes. A number of tapes . Tape is the input tape, tape is the output tape, and the rest are work tapes. Each tape has cells indexed by , and each tape has its own head at a position in .
- Transition function. A deterministic transition function .
The transition function is subject to four conditions:
- (a) when a head scans , it rewrites and does not move left;
- (b) is never written over a symbol other than ;
- (c) in the halting state, rewrites each scanned symbol unchanged, keeps the halting state, and does not move any head;
- (d) the symbol written on tape always equals the symbol scanned there, so the input tape is read-only.
One step works as follows. Read the scanned symbols and apply . Overwrite each scanned cell with the prescribed symbol. Move each head left (position , truncated at ), keep it in place, or move it right (). Change to the new state. Condition (a) and the fact that cell always holds mean the truncated left move at cell never actually occurs.
Initial configuration on . The machine is in the start state and all heads are on cell . The input tape holds , with bits encoded as . Every other tape holds .
Time is the number of steps. There is no space bound and no restriction on the number of tapes beyond , which is fixed for the machine.
Edge cases. The case is excluded from both conditions. Clause 1 only requires that multiplies correctly and halts, in some finite number of steps, on all inputs of every size . Clause 2 then requires, for all , the worst-case number of steps over all to be at most . The theorem is stated with its proof left as sorry.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.