Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Jain's round-seven construction from its network savings

Open
IntMul.Kappa.jain_round7_framework

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

complexity-theoryinteger-multiplicationturing-machines

Jain's round seven, with its finite certificates factored out. Let hbith^{\mathrm{bit}}hbit be the child-width histogram of the round-seven bit network (witness 1: PR #62 producer, lifted frames, late copies, deferred readouts, V leaves, staircase entrance corner), of width 529529529 with Wb=108516254W_b=108516254Wb​=108516254 roles, and hcxh^{\mathrm{cx}}hcx that of the round-six complex network, of width 576576576 with Wc=207387136W_c=207387136Wc​=207387136 roles and rank sum sc=∑ww nwcxs_c=\sum_w w\,n^{\mathrm{cx}}_wsc​=∑w​wnwcx​. Put β=1/1000\beta=1/1000β=1/1000. Let ab,ac,ε,x,C1,κa_b,a_c,\varepsilon,x,C_1,\kappaab​,ac​,ε,x,C1​,κ be real numbers with ab,ac≥0a_b,a_c\ge0ab​,ac​≥0 such that

  1. ∑wnwbit(w529)1−ab<Wb\displaystyle\sum_w n^{\mathrm{bit}}_w\Big(\frac{w}{529}\Big)^{1-a_b}<W_bw∑​nwbit​(529w​)1−ab​<Wb​;
  2. ∑wnwcx(w576)1−ac<Wc\displaystyle\sum_w n^{\mathrm{cx}}_w\Big(\frac{w}{576}\Big)^{1-a_c}<W_cw∑​nwcx​(576w​)1−ac​<Wc​;
  3. 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 the round: the OpenAI construction, Colkitt's framework and Jain's two 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 assumes that stage two is the complement time-reversal of stage one.

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_round7_framework (ab ac ε x C₁ κ : ℝ) (hab : 0 ≤ ab) (hac : 0 ≤ ac)
    (hbit : histMoment Jain.bitR7 529 (1 - ab) < 108516254)
    (hcx : histMoment Jain.cxR6 576 (1 - ac) < 207387136)
    (hasm : CrudeAssembly ab ac (1 / 1000) ε x C₁ κ 576 (histRankSum Jain.cxR6)) :
    KappaBound κ := by sorry

end IntMul.Kappa
Source
S. Jain, integer-mult-kappa, https://github.com/Swapnil-jain/integer-mult-kappa/tree/c05adfe1dfe85326dd6dcf12bfd53f435bd49bf3 — README 'Round seven', lean/Round7.lean (bitHist, cxHist, bit_moment, cx_moment, kappa_assembly), research/round7-moment-refinement (sharper moment certificate, merged PR #2, commit 44e13e3), scripts/certificate_round3.py (crude guard, beta=1/1000); 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