Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Jain's round-six construction from its network savings

Proved
IntMul.Kappa.jain_round6_framework

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

complexity-theoryinteger-multiplicationturing-machines

Jain's round six, with its finite certificates factored out. Let hbith^{\mathrm{bit}}hbit be the child-width histogram of the round-six bit network, of width 529529529 with Wb=148225616W_b=148225616Wb​=148225616 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 (copied retained centres, retained point totals and a two-stage complex 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_round6_framework (ab ac ε x C₁ κ : ℝ) (hab : 0 ≤ ab) (hac : 0 ≤ ac)
    (hbit : histMoment Jain.bitR6 529 (1 - ab) < 148225616)
    (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/f2176bc — README 'Round six', lean/Round6.lean (bitHist, cxHist, bit_moment, cx_moment, kappa_assembly), 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