Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Round-eight certificate checkers: expUp, momentExpOK, stopOK

Definition
intmul_round8_certs_extra

by chstdu · Oct 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

certificateexact-arithmeticinteger-multiplication

The round-eight additions to the integer-multiplication κ-certificate checkers (Jain, repository integer-mult-kappa, file lean/Round8.lean). The function expUp is a rational upper bound for exe^xex on 0≤x<10 \le x < 10≤x<1 obtained from the power series with a geometric tail bound. On top of it, momentExpOK is the exp-form moment condition of the linear-network analysis: for every width class (w,n)(w, n)(w,n) of a histogram, w<mw < mw<m and a Lw<4a\,L_w < 4aLw​<4 with Lw=lnUp⁡(m/w)L_w = \operatorname{lnUp}(m/w)Lw​=lnUp(m/w), and ∑n w eaLw/m<W\sum n\,w\,e^{a L_w} / m < W∑nweaLw​/m<W. Finally stopOK checks a stopped saving: ab=(1−θ) a+θ aolda_b = (1-\theta)\,a + \theta\,a_{\text{old}}ab​=(1−θ)a+θaold​ exactly, and ab<θa_b < \thetaab​<θ.

Definition code
/-
  Round-eight additions to the integer-multiplication certificate checkers: an exponential
upper bound expUp, the exp-form moment condition momentExpOK, and the stopped-saving
guard stopOK (Jain, integer-mult-kappa, lean/Round8.lean).
-/

import Definitions.Def_intmul_certs_arith

namespace IntMul.Certs

def expUp (x : Q) : Q :=
  qadd (qadd (qadd (1, 1) x) (qdiv (qmul x x) (2, 1)))
    (qdiv (qmul x (qmul x x)) (qmul (6, 1) (qsub (1, 1) (qdiv x (4, 1)))))

-- moment bound through exp: every a * L_w < 4, every w < m, and sum n w E(a L_w) / m < W
def momentExpOK (h : List (Nat × Nat)) (a : Q) (m W : Nat) : Bool :=
  let step := fun (acc : Bool × Q) (p : Nat × Nat) =>
    let w := p.1; let n := p.2
    let al := qmul a (lnUp (m, w))
    let ok := acc.1 && (w < m) && qlt al (4, 1)
    if ok then (true, qadd acc.2 (qdiv (qmul (n * w, 1) (expUp al)) (m, 1))) else (false, acc.2)
  let r := h.foldl step (true, (0, 1))
  r.1 && qlt r.2 (W, 1)

-- stopped saving: ab = (1 - theta) a + theta aold, and ab < theta
def stopOK (a aold theta ab : Q) : Bool :=
  let v := qadd (qmul (qsub (1, 1) theta) a) (qmul theta aold)
  v.1 * ab.2 == ab.1 * v.2 && qlt ab theta

-- bit interchange, opposite bank orders (one-run histogram, moment at a*)

end IntMul.Certs
Source
Swapnil Jain, integer-mult-kappa, https://github.com/Swapnil-jain/integer-mult-kappa, file lean/Round8.lean (expUp, momentExpOK, stopOK).

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