Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Rational arithmetic and certificate checkers for the integer-multiplication κ-records

Definition
intmul_certs_arith

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

certificateexact-arithmeticinteger-multiplication

Exact rational arithmetic on pairs of natural numbers (p,q)(p, q)(p,q) (numerator, positive denominator), with gcd normalization, the four operations, and a strict comparison. The function lnUp is a rational upper bound for ln⁡x\ln xlnx obtained from the identity ln⁡x=2k⋅2 artanh⁡x1/2k−1x1/2k+1\ln x = 2^k \cdot 2\,\operatorname{artanh}\frac{x^{1/2^k}-1}{x^{1/2^k}+1}lnx=2k⋅2artanhx1/2k+1x1/2k−1​ with the atanh series truncated and bounded from above. On top of these: rankSum (the weighted rank sum ∑w n\sum w\,n∑wn of a width histogram), momentOK (the moment condition of the linear-network analysis: for every width class (w,n)(w, n)(w,n) of the histogram, w<mw < mw<m and a⋅Lw<1a \cdot L_w < 1a⋅Lw​<1 with Lw=\lnUp(m/w)L_w = \lnUp(m/w)Lw​=\lnUp(m/w), and ∑n w/(m (1−aLw))<W\sum n\,w / (m\,(1 - a L_w)) < W∑nw/(m(1−aLw​))<W), and kappaOK (the parameter-assembly guard of the κ-record: with savings ab,aca_b, a_cab​,ac​, split β\betaβ, tolerances ε,x,c1\varepsilon, x, c_1ε,x,c1​, κ\kappaκ, and mc,scm_c, s_cmc​,sc​, it checks c1≥2+mcln⁡scc_1 \ge 2 + m_c \ln s_cc1​≥2+mc​lnsc​, the strict consistency constraints, and that every cost margin exceeds κ\kappaκ). These are the checkers for the computational certificates of the integer-multiplication κ-records of Jain (repository integer-mult-kappa), used verbatim from lean/Round6.lean.

Definition code
/-
  Exact rational arithmetic and certificate checkers for the integer-multiplication
  κ-record certificates (Jain, integer-mult-kappa). Rationals are pairs of naturals
  (numerator, denominator) with positive denominators; lnUp bounds ln from above
  via the atanh series. Checkers: rankSum, momentOK, kappaOK.
-/

namespace IntMul.Certs

abbrev Q := Nat × Nat

def norm (a : Q) : Q := let g := Nat.gcd a.1 a.2; if g = 0 then a else (a.1 / g, a.2 / g)
def qadd (a b : Q) : Q := norm (a.1 * b.2 + b.1 * a.2, a.2 * b.2)
def qmul (a b : Q) : Q := norm (a.1 * b.1, a.2 * b.2)
def qdiv (a b : Q) : Q := norm (a.1 * b.2, a.2 * b.1)
-- a - b, defined when b <= a
def qsub (a b : Q) : Q := norm (a.1 * b.2 - b.1 * a.2, a.2 * b.2)
def qlt (a b : Q) : Bool := a.1 * b.2 < b.1 * a.2
def qpow (a : Q) : Nat → Q
  | 0 => (1, 1)
  | k + 1 => qmul a (qpow a k)

-- 2 * (sum_{j<n} z^(2j+1)/(2j+1) + z^(2n+1) / ((2n+1)(1 - z^2)))
def atanhSum (z : Q) : Nat → Q
  | 0 => (0, 1)
  | j + 1 => qadd (atanhSum z j) (qdiv (qpow z (2 * j + 1)) (2 * j + 1, 1))
def twoAtanhUp (z : Q) (n : Nat) : Q :=
  qmul (2, 1) (qadd (atanhSum z n) (qdiv (qpow z (2 * n + 1)) (qmul (2 * n + 1, 1) (qsub (1, 1) (qmul z z)))))

-- halve x until x <= 2, counting the halvings (fuel bounds the loop)
def halve (x : Q) (k : Nat) : Nat → Q × Nat
  | 0 => (x, k)
  | f + 1 => if qlt (2, 1) x then halve (norm (x.1, 2 * x.2)) (k + 1) f else (x, k)

def lnUp (x : Q) : Q :=
  let p := halve x 0 64
  let y := p.1
  let base := qmul (p.2, 1) (twoAtanhUp (1, 3) 30)
  if qlt (1, 1) y then qadd base (twoAtanhUp (qdiv (qsub y (1, 1)) (qadd y (1, 1))) 30) else base

def rankSum (h : List (Nat × Nat)) : Nat := h.foldl (fun acc p => acc + p.1 * p.2) 0

-- moment bound: every a * L_w < 1, every w < m, and sum n w / (m (1 - a L_w)) < W
def momentOK (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 l := lnUp (m, w)
    let al := qmul a l
    let ok := acc.1 && (w < m) && qlt al (1, 1)
    if ok then (true, qadd acc.2 (qdiv (n * w, 1) (qmul (m, 1) (qsub (1, 1) al)))) else (false, acc.2)
  let r := h.foldl step (true, (0, 1))
  r.1 && qlt r.2 (W, 1)

def qmax (a b : Q) : Q := if qlt a b then b else a
def qmin (a b : Q) : Q := if qlt a b then a else b

-- The assembly of scripts/certificate_round3.py (crude guard), for given savings a_b, a_c, beta and the chosen
-- eps, x, kappa: every constraint is strict and every cost margin exceeds kappa. C1 = 1 + m_c ln s_c + 1 is
-- replaced by the check that the given C1 bounds 2 + m_c * (upper bound of ln s_c).
def kappaOK (ab ac beta eps x c1 kappa : Q) (mc sc : Nat) : Bool :=
  let gl : Q := (1, 10000000000000000)
  let one : Q := (1, 1)
  let tau := qsub one ab
  let sigma := qsub one ac
  let chi := qadd tau (qmul (qsub one beta) (if qlt tau sigma then qsub sigma tau else (0, 1)))
  let leaf := qadd sigma (qmul beta (qsub one sigma))
  let lam := qadd (qmax (qmax tau sigma) chi) gl
  let lamp := qadd (qmax lam leaf) gl
  let delta := qdiv (1, 10000000000000000000000) x
  let poly := qmul (qadd one x) delta
  let c1ok := !(qlt c1 (qadd (2, 1) (qmul (mc, 1) (lnUp (sc, 1)))))
  let cons := qlt lamp one && qlt (qmul eps (qsub (2, 1) lamp)) one
    && qlt (qmul eps c1) (qadd one x) && qlt (qadd (qmul (2, 1) eps) eps) (qadd one x)
    && qlt (qsub (qmul (2, 1) eps) one) (qmul lamp eps) && qlt eps one && qlt delta (1, 8)
  let margins := [qsub one eps, qmul eps (qsub one lamp), qsub (qsub one eps) poly, eps,
                  qmul (qmax eps (qsub one eps)) (qsub one tau)]
  c1ok && cons && margins.all (fun g => qlt kappa g)

-- assembly: kappa = 3666565558019/100000000000000000 with the two savings above

end IntMul.Certs
Source
Swapnil Jain, integer-mult-kappa, https://github.com/Swapnil-jain/integer-mult-kappa, file lean/Round6.lean (rational arithmetic and certificate checkers, generated by lean/gen.py).

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