Exact integer multiplication with saving κ = 0.00012612978530233
OpenIntMul.Kappa.jain_round8Jain's round-eight 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 eight. The project states that the claim is conditional on the OpenAI manuscript and on Colkitt's framework, that stage two and three further interfaces are 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_round8 : KappaBound (0.00012612978530233 : ℝ) := 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_round8. The theorem has no hypotheses or free variables. It asserts , where is the real number written as the decimal literal 0.00012612978530233, which is exactly
(The proof in the file is a placeholder, sorry.) Unfolded, the statement says the following.
Claim. There exists a deterministic multitape Turing machine (model described below) such that both of these hold:
- Correctness for every length . For every natural number there is a real number such that multiplies -bit inputs within steps (in the sense of below). Because is fixed and there are only finitely many inputs of length , this amounts to saying that halts with the correct output on every pair of -bit inputs.
- Time bound. There exist a real constant and a natural number such that for every natural number with and , multiplies -bit inputs within
steps. Here is the real power of the real number . Since , it is the ordinary positive real power , and no junk value from a nonpositive base comes up. At it equals .
The order of quantifiers is: there exists , then [for all there exists ], and then there exist and such that for all . So and may depend on but not on , and the same single machine works for all .
The function . For a natural number , , where is computed on naturals as the least with (this is for and ). Hence , , , and so on. It is a natural number, which is cast to before the power is taken.
, for and , means the following. For all bit strings with there is a natural number with (compared as reals) such that, after exactly steps from the initial configuration on input , the machine is in its halting state and its output tape holds exactly , where
- is the natural number whose binary representation is , most significant bit first, and . Leading zeros are allowed in and , so each input ranges over all of .
- is the length- list of bits (most significant first), where is bit of . This is the -bit binary representation of padded with leading zeros. Because , it is never truncated, and the output always has exactly bits.
- The output-tape condition is an equality of entire infinite tapes: cell holds , cells hold the bit symbols of , and every later cell holds the blank. Nothing is required of the work tapes, the head positions, or the input tape's head at halting.
- Because the halting state freezes the configuration (see below), "halted with this output at some " is equivalent to "halts with this output after at most steps". If , no such exists.
The machine model. A machine consists of the following.
- A finite alphabet (any finite type) with five designated, pairwise distinct symbols: blank , start , bit symbols and , and separator .
- A finite set of states with a start state and a halting state, which are distinct.
- A number of tapes (fixed for ). Tape is the input tape, tape is the output tape, and the others are work tapes. Each tape is a one-way-infinite sequence of cells indexed by .
- A transition function .
must satisfy four conditions:
- (i) On any tape scanning , it writes back and does not move left.
- (ii) On any tape not scanning , it never writes .
- (iii) for every , so the configuration never changes once halted.
- (iv) The symbol written on tape always equals the symbol read there, so the input tape is read-only, although its head may move.
A configuration is a state, the contents of every tape, and a head position in for each tape. One step reads the scanned symbols, applies , overwrites each scanned cell with the new symbol, moves each head (left subtracts with natural-number truncation at , but condition (i) makes a left move from cell impossible because cell always holds ), and updates the state. The initial configuration on is in the start state with all heads on cell . The input tape holds , then the symbols of , then , then the symbols of , then blanks. Every other tape holds followed by blanks. Running time is the number of steps . There is no restriction on the number of tapes, the alphabet size, or the number of states beyond finiteness, and these are chosen together with .
Edge cases. Length is excluded from both conditions, so the empty inputs (input string ) impose no constraint. The extra hypothesis in condition 2 only matters if . For , the bound is strictly positive. Condition 1 provides correctness, with some finite time, for every length with that condition 2 does not cover.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.