Rational arithmetic and certificate checkers for the integer-multiplication κ-records
Definitionintmul_certs_arithExact rational arithmetic on pairs of natural numbers (numerator, positive denominator), with gcd normalization, the four operations, and a strict comparison. The function lnUp is a rational upper bound for obtained from the identity with the atanh series truncated and bounded from above. On top of these: rankSum (the weighted rank sum of a width histogram), momentOK (the moment condition of the linear-network analysis: for every width class of the histogram, and with , and ), and kappaOK (the parameter-assembly guard of the κ-record: with savings , split , tolerances , , and , it checks , the strict consistency constraints, and that every cost margin exceeds ). 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.
/-
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