Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Jain's round-eight construction from its network savings

Open
IntMul.Kappa.jain_round8_framework

by xuanji · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplicationturing-machines

Jain's round eight, with its finite certificates factored out. Let holdh^{\mathrm{old}}hold be the child-width histogram of the round-seven bit network (witness 2, round-six entrance corner), hbith^{\mathrm{bit}}hbit that of the round-eight bit network (opposite bank orders on the same witness), and hcxh^{\mathrm{cx}}hcx that of the round-eight complex network (signed reclaim and completed-core sharing), with rank sum sc=∑ww nwcxs_c=\sum_w w\,n^{\mathrm{cx}}_wsc​=∑w​wnwcx​. Put θ=β=1/1000\theta=\beta=1/1000θ=β=1/1000. Let aold,a∗,ab,ac,ε,x,C1,κa_{\mathrm{old}},a^*,a_b,a_c,\varepsilon,x,C_1,\kappaaold​,a∗,ab​,ac​,ε,x,C1​,κ be real numbers with aold,a∗,ac≥0a_{\mathrm{old}},a^*,a_c\ge0aold​,a∗,ac​≥0 such that

  1. ∑wnwold(w529)1−aold<104719230\displaystyle\sum_w n^{\mathrm{old}}_w\Big(\frac{w}{529}\Big)^{1-a_{\mathrm{old}}}<104719230w∑​nwold​(529w​)1−aold​<104719230;
  2. ∑wnwbit(w529)1−a∗<104719230\displaystyle\sum_w n^{\mathrm{bit}}_w\Big(\frac{w}{529}\Big)^{1-a^*}<104719230w∑​nwbit​(529w​)1−a∗<104719230;
  3. ab=(1−θ)a∗+θaolda_b=(1-\theta)a^*+\theta a_{\mathrm{old}}ab​=(1−θ)a∗+θaold​ and ab<θa_b<\thetaab​<θ (the stopped bit interchange);
  4. ∑wnwcx(w576)1−ac<12869228\displaystyle\sum_w n^{\mathrm{cx}}_w\Big(\frac{w}{576}\Big)^{1-a_c}<12869228w∑​nwcx​(576w​)1−ac​<12869228;
  5. the crude-guard assembly CrudeAssembly(ab,ac,β,ε,x,C1,κ,576,sc)\mathrm{CrudeAssembly}(a_b,a_c,\beta,\varepsilon,x,C_1,\kappa,576,s_c)CrudeAssembly(ab​,ac​,β,ε,x,C1​,κ,576,sc​) holds.

Then integer multiplication is possible in time

T(n)=O(n(lg⁡n)1−κ),lg⁡n=max⁡(⌈log⁡2n⌉,1),T(n)=O\big(n(\lg n)^{1-\kappa}\big),\qquad \lg n=\max(\lceil\log_2 n\rceil,1),T(n)=O(n(lgn)1−κ),lgn=max(⌈log2​n⌉,1),

by one deterministic multitape Turing machine with fixed alphabet and tape count.

This is the machine-level content of Jain's round eight: the OpenAI construction, Colkitt's framework and Jain's networks turn certified network savings into a multiplication algorithm. The finite certificates and the real-analysis steps (rigorous bounds for log⁡\loglog and exp⁡\expexp applied to the frozen histograms) are separate. The source states the result as conditional on the OpenAI manuscript and on Colkitt's framework, and lists as assumed interfaces: stage two is the complement time-reversal of stage one; the normal form for alternating residuals (icekylinx, PRs #24 and #104); binary address adapters for the exterior children of the sharing; and the row stock of the stopped bit interchange.

Formalization Note KappaBound(κ)\mathrm{KappaBound}(\kappa)KappaBound(κ) is from IntMul_MultitapeModel: one deterministic multitape Turing machine with fixed alphabet and tape count, correct for every n≥1n\ge1n≥1, with running time at most c n (lg⁡n)1−κc\,n\,(\lg n)^{1-\kappa}cn(lgn)1−κ for n≥n0n\ge n_0n≥n0​. The moment histMoment\mathrm{histMoment}histMoment, rank sum and CrudeAssembly\mathrm{CrudeAssembly}CrudeAssembly are from IntMul_KappaFramework; the histograms are from IntMul_KappaJainData. All hypotheses are real-number statements; the source checks rational majorants of them.

Preamble
import Definitions.Def_IntMul_MultitapeModel
import Definitions.Def_IntMul_KappaFramework
import Definitions.Def_IntMul_KappaJainData
Formal statement
namespace IntMul.Kappa

theorem jain_round8_framework (aOld aStar ab ac ε x C₁ κ : ℝ)
    (hOld : 0 ≤ aOld) (hStar : 0 ≤ aStar) (hac : 0 ≤ ac)
    (hbitOld : histMoment Jain.bitR7plain 529 (1 - aOld) < 104719230)
    (hbit : histMoment Jain.bitR8 529 (1 - aStar) < 104719230)
    (hstop : ab = (1 - 1 / 1000) * aStar + 1 / 1000 * aOld)
    (hθ : ab < 1 / 1000)
    (hcx : histMoment Jain.cxR8 576 (1 - ac) < 12869228)
    (hasm : CrudeAssembly ab ac (1 / 1000) ε x C₁ κ 576 (histRankSum Jain.cxR8)) :
    KappaBound κ := by sorry

end IntMul.Kappa
Source
S. Jain, integer-mult-kappa, https://github.com/Swapnil-jain/integer-mult-kappa/tree/5868dc701a9bec375c9dc5391d992ab3b8c35f3f — README 'Round eight' (savings, stopped mix a_b=(1-theta)a*+theta a_old with theta=1/1000, a_old = round-seven saving of witness 2, proof interfaces), scripts/certificate_round8.py, scripts/certificate_round3.py (crude guard, beta=1/1000), lean/Round8.lean (bit_moment, bit_stopped, cx_moment, kappa_assembly), lean/Round7.lean (bitplain_moment); 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

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me