Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact integer multiplication with saving κ = 0.00012612978530233

Open
IntMul.Kappa.jain_round8

by avi · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplicationturing-machines

Jain'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 n≥1n\ge1n≥1 and all x,y∈{0,1}nx,y\in\{0,1\}^nx,y∈{0,1}n halts on input x#yx\#yx#y with output bin⁡2n(val⁡x⋅val⁡y)\operatorname{bin}_{2n}(\operatorname{val}x\cdot\operatorname{val}y)bin2n​(valx⋅valy), and whose worst-case running time satisfies

T(n)=O(n L(n)1−κ),L(n)=max⁡(⌈log⁡2n⌉,1),κ=126129785302331017=0.00012612978530233>2−13.T(n)=O\big(n\,L(n)^{1-\kappa}\big),\qquad L(n)=\max(\lceil\log_2n\rceil,1),\qquad \kappa=\frac{12612978530233}{10^{17}}=0.00012612978530233>2^{-13}.T(n)=O(nL(n)1−κ),L(n)=max(⌈log2​n⌉,1),κ=101712612978530233​=0.00012612978530233>2−13.

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 n≥1n\ge1n≥1, and constants c>0c>0c>0, n0n_0n0​ with running time at most c n L(n)1−κc\,n\,L(n)^{1-\kappa}cnL(n)1−κ for n≥n0n\ge n_0n≥n0​. The decimal literal is the exact rational 0.00012612978530233=12612978530233/10170.00012612978530233=12612978530233/10^{17}0.00012612978530233=12612978530233/1017.

Preamble
import Definitions.Def_IntMul_MultitapeModel
Formal statement
namespace IntMul.Kappa

theorem jain_round8 : KappaBound (0.00012612978530233 : ℝ) := by
  sorry

end IntMul.Kappa
Source
S. Jain, Integer multiplication: a conditional witness above 2^-13 (integer-mult-kappa), research draft, https://github.com/Swapnil-jain/integer-mult-kappa/tree/5868dc701a9bec375c9dc5391d992ab3b8c35f3f — README headline and 'Round eight' section (scripts/certificate_round8.py, certificates/round8/, lean/Round8.lean); kappa = 12612978530233/10^17, bound by the complex side; stated as conditional on OpenAI, Integer multiplication below n log n, preprint, 23 September 2026, https://github.com/openai/math/tree/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Integer-multiplication-below-n-log-n-September-23-2026, and on D. Colkitt, https://github.com/CrocSwap/integer-mult-bounds/tree/56b66d58297deca1d7dd130247d720e960f77a37
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 KappaBound(κ0)\mathrm{KappaBound}(\kappa_0)KappaBound(κ0​), where κ0\kappa_0κ0​ is the real number written as the decimal literal 0.00012612978530233, which is exactly

κ0=126129785302331017=12612978530233100000000000000000(already in lowest terms),1−κ0=999873870214697671017.\kappa_0 = \frac{12612978530233}{10^{17}} = \frac{12612978530233}{100000000000000000}\quad(\text{already in lowest terms}),\qquad 1-\kappa_0 = \frac{99987387021469767}{10^{17}}.κ0​=101712612978530233​=10000000000000000012612978530233​(already in lowest terms),1−κ0​=101799987387021469767​.

(The proof in the file is a placeholder, sorry.) Unfolded, the statement says the following.

Claim. There exists a deterministic multitape Turing machine MMM (model described below) such that both of these hold:

  1. Correctness for every length n≥1n \ge 1n≥1. For every natural number n≥1n \ge 1n≥1 there is a real number TTT such that MMM multiplies nnn-bit inputs within TTT steps (in the sense of MultipliesAt\mathrm{MultipliesAt}MultipliesAt below). Because nnn is fixed and there are only finitely many inputs of length nnn, this amounts to saying that MMM halts with the correct output on every pair of nnn-bit inputs.
  2. Time bound. There exist a real constant c>0c > 0c>0 and a natural number n0n_0n0​ such that for every natural number nnn with n≥n0n \ge n_0n≥n0​ and n≥1n \ge 1n≥1, MMM multiplies nnn-bit inputs within
c⋅n⋅(lg⁡n)1−κ0c \cdot n \cdot (\operatorname{lg} n)^{1-\kappa_0}c⋅n⋅(lgn)1−κ0​

steps. Here (lg⁡n)1−κ0(\operatorname{lg} n)^{1-\kappa_0}(lgn)1−κ0​ is the real power of the real number lg⁡n\operatorname{lg} nlgn. Since lg⁡n≥1>0\operatorname{lg} n \ge 1 > 0lgn≥1>0, it is the ordinary positive real power exp⁡((1−κ0)ln⁡lg⁡n)\exp\big((1-\kappa_0)\ln \operatorname{lg} n\big)exp((1−κ0​)lnlgn), and no junk value from a nonpositive base comes up. At lg⁡n=1\operatorname{lg} n = 1lgn=1 it equals 111.

The order of quantifiers is: there exists MMM, then [for all n≥1n\ge1n≥1 there exists TTT], and then there exist c>0c>0c>0 and n0n_0n0​ such that for all n≥max⁡(n0,1)n \ge \max(n_0,1)n≥max(n0​,1). So ccc and n0n_0n0​ may depend on MMM but not on nnn, and the same single machine works for all nnn.

The function lg⁡\operatorname{lg}lg. For a natural number nnn, lg⁡n=max⁡(⌈log⁡2n⌉,1)\operatorname{lg} n = \max(\lceil \log_2 n\rceil, 1)lgn=max(⌈log2​n⌉,1), where ⌈log⁡2n⌉\lceil\log_2 n\rceil⌈log2​n⌉ is computed on naturals as the least k∈Nk\in\mathbb Nk∈N with n≤2kn \le 2^kn≤2k (this is 000 for n=0n=0n=0 and n=1n=1n=1). Hence lg⁡0=lg⁡1=lg⁡2=1\operatorname{lg} 0=\operatorname{lg}1=\operatorname{lg}2=1lg0=lg1=lg2=1, lg⁡3=lg⁡4=2\operatorname{lg}3=\operatorname{lg}4=2lg3=lg4=2, lg⁡5=⋯=lg⁡8=3\operatorname{lg}5=\dots=\operatorname{lg}8=3lg5=⋯=lg8=3, and so on. It is a natural number, which is cast to R\mathbb RR before the power is taken.

MultipliesAt(M,n,T)\mathrm{MultipliesAt}(M,n,T)MultipliesAt(M,n,T), for n∈Nn\in\mathbb Nn∈N and T∈RT\in\mathbb RT∈R, means the following. For all bit strings x,yx,yx,y with ∣x∣=∣y∣=n|x|=|y|=n∣x∣=∣y∣=n there is a natural number ttt with t≤Tt \le Tt≤T (compared as reals) such that, after exactly ttt steps from the initial configuration on input x#yx\#yx#y, the machine is in its halting state and its output tape holds exactly ▹ w □□⋯\triangleright\, w\, \square\square\cdots▹w□□⋯, where

w=bin⁡2n(val⁡(x)⋅val⁡(y)).w = \operatorname{bin}_{2n}\big(\operatorname{val}(x)\cdot\operatorname{val}(y)\big).w=bin2n​(val(x)⋅val(y)).
  • val⁡(x)\operatorname{val}(x)val(x) is the natural number whose binary representation is xxx, most significant bit first, and val⁡(empty)=0\operatorname{val}(\text{empty})=0val(empty)=0. Leading zeros are allowed in xxx and yyy, so each input ranges over all of {0,…,2n−1}\{0,\dots,2^n-1\}{0,…,2n−1}.
  • bin⁡k(z)\operatorname{bin}_{k}(z)bink​(z) is the length-kkk list of bits zk−1,…,z0z_{k-1},\dots,z_0zk−1​,…,z0​ (most significant first), where zjz_jzj​ is bit jjj of zzz. This is the kkk-bit binary representation of zzz padded with leading zeros. Because val⁡(x)val⁡(y)<22n\operatorname{val}(x)\operatorname{val}(y) < 2^{2n}val(x)val(y)<22n, it is never truncated, and the output always has exactly 2n2n2n bits.
  • The output-tape condition is an equality of entire infinite tapes: cell 000 holds ▹\triangleright▹, cells 1,…,2n1,\dots,2n1,…,2n hold the bit symbols of www, 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 t≤Tt\le Tt≤T" is equivalent to "halts with this output after at most ⌊T⌋\lfloor T\rfloor⌊T⌋ steps". If T<0T<0T<0, no such ttt exists.

The machine model. A machine MMM consists of the following.

  • A finite alphabet Σ\SigmaΣ (any finite type) with five designated, pairwise distinct symbols: blank □\square□, start ▹\triangleright▹, bit symbols 000 and 111, and separator #\##.
  • A finite set of states KKK with a start state and a halting state, which are distinct.
  • A number of tapes k≥2k\ge2k≥2 (fixed for MMM). Tape 000 is the input tape, tape 111 is the output tape, and the others are work tapes. Each tape is a one-way-infinite sequence of cells indexed by N\mathbb NN.
  • A transition function δ:K×Σk→K×(Σ×{←,−,→})k\delta: K\times\Sigma^k\to K\times(\Sigma\times\{\leftarrow,-,\rightarrow\})^kδ:K×Σk→K×(Σ×{←,−,→})k.

δ\deltaδ must satisfy four conditions:

  • (i) On any tape scanning ▹\triangleright▹, it writes ▹\triangleright▹ back and does not move left.
  • (ii) On any tape not scanning ▹\triangleright▹, it never writes ▹\triangleright▹.
  • (iii) δ(HALT,a)=(HALT,(ai,−)i)\delta(\text{HALT},a)=(\text{HALT},(a_i,-)_i)δ(HALT,a)=(HALT,(ai​,−)i​) for every aaa, so the configuration never changes once halted.
  • (iv) The symbol written on tape 000 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 N\mathbb NN for each tape. One step reads the kkk scanned symbols, applies δ\deltaδ, overwrites each scanned cell with the new symbol, moves each head (left subtracts 111 with natural-number truncation at 000, but condition (i) makes a left move from cell 000 impossible because cell 000 always holds ▹\triangleright▹), and updates the state. The initial configuration on x#yx\#yx#y is in the start state with all heads on cell 000. The input tape holds ▹\triangleright▹, then the symbols of xxx, then #\##, then the symbols of yyy, then blanks. Every other tape holds ▹\triangleright▹ followed by blanks. Running time is the number of steps ttt. 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 MMM.

Edge cases. Length n=0n=0n=0 is excluded from both conditions, so the empty inputs (input string #\##) impose no constraint. The extra hypothesis n≥1n\ge1n≥1 in condition 2 only matters if n0=0n_0=0n0​=0. For n≥1n \ge 1n≥1, the bound c n (lg⁡n)1−κ0c\,n\,(\operatorname{lg} n)^{1-\kappa_0}cn(lgn)1−κ0​ is strictly positive. Condition 1 provides correctness, with some finite time, for every length nnn with 1≤n<n01\le n<n_01≤n<n0​ that condition 2 does not cover.

Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by avi · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me