# cert2_v2.py: the second-order certificate engine (version 2), used for the case (eta, alpha') = (1/20, 1/5). # Usage: python cert2_v2.py M NB PICKLE TAG (environment: KPROF, GBIN, BLOCKS). Writes cert2v2__M.json. import sys, os, time, json, hashlib, pickle from fractions import Fraction as Fr from math import comb sys.path.insert(0, __import__('os').path.dirname(__import__('os').path.abspath(__file__))) import dpl T_START = time.time() def log(*a): print(f"[{time.time() - T_START:7.1f}s]", *a, flush=True) M_, NB_, PKL_, TAG_ = sys.argv[1:5] M = int(M_); NB = int(NB_) dpl.init(M) from dpl import (D, SCALE, fl, ce, fz, dz, d_add, d_neg, d_scale, d_div, d_trunc, d_cell, d_ends, d_ends_rev, d_at1, d_at0, d_from_cells, d_const_cells, d_minlow, d_maxup, d_maxwidth, d_kernel, conv_nn, conv_sn, conv_ss, corr_sn, corr_nn, cell_mul, cell_neg_quot, cell_add, cell_contains0, iv_mul, iv_div, add_iv, iv_scale, _pos_lo, _pos_hi, _neg_lo, _neg_hi) raw = open(PKL_, 'rb').read(); PKL_SHA = hashlib.sha256(raw).hexdigest(); dpk = pickle.loads(raw) ETA, ALPHA = Fr(dpk['eta']), Fr(dpk['alpha']) assert (M * ETA).denominator == 1 and (M * ALPHA).denominator == 1 and M % 2 == 0 iE, iA, iH = int(M * ETA), int(M * ALPHA), M // 2 KPROF = None if os.environ.get('KPROF', 'all') == 'all' else set(int(x) for x in os.environ['KPROF'].split(',')) assert M > 0 and NB > 0 assert 0 < ETA < ALPHA < Fr(1, 2) assert 6 * ALPHA >= 1, "rough-count cutoff 5 is insufficient" assert 10 * ETA >= ALPHA, "small-count power cutoff 9 is insufficient" MSTAR = max(j for j in range(1, 20) if j * ETA < ALPHA) log(f"cert2 (second order): M={M} NB={NB} pickle sha256={PKL_SHA} tag={TAG_} KPROF={'all' if KPROF is None else sorted(KPROF)} eta={ETA} alpha'={ALPHA} m*={MSTAR}") # ---------------------------------------------------------------- bins and constants EDGES = [Fr(e) for e in dpk['edges']] if 'edges' in dpk else [ALPHA, Fr(1, 2)] if EDGES[0] != ALPHA: EDGES = [ALPHA] + [e for e in EDGES if e > ALPHA] assert EDGES[-1] == Fr(1, 2), EDGES assert len(EDGES) >= 2 and EDGES[0] == ALPHA assert all(a < b for a, b in zip(EDGES, EDGES[1:])), "unordered bin edges" NBIN = len(EDGES) - 1 for q in EDGES: assert (q * M).denominator == 1, f"M does not put {q} on the grid" iEdge = [int(e * M) for e in EDGES] def class_total_range(j, k, b): if k == 0: return (j * ETA, j * ALPHA) lo_b, hi_b = EDGES[b - 1], EDGES[b] return (j * ETA + (k - 1) * ALPHA + lo_b, j * ALPHA + k * hi_b) def realisable_bin(j, k, b): lo, hi = class_total_range(j, k, b); return lo < 1 < hi TEXTS = {'v2main': [(0, 3), (0, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 1), (4, 2), (5, 1), (5, 2), (6, 1), (6, 2)]} TEXT = TEXTS.get(TAG_) C3 = {} for cls, x in zip(dpk['classes'], dpk['x']): j, k, b = (int(t) for t in cls) if abs(float(x)) == 0: continue if k == 0: b = 0 if NBIN == 1 and k >= 1: b = 1 if (k == 0 and b != 0) or (k >= 1 and not 1 <= b <= NBIN): continue if TEXT is not None and (j, k) not in TEXT: continue if not realisable_bin(j, k, b): continue assert (j, k, b) not in C3 C3[(j, k, b)] = Fr(float(x)) if TEXT is not None: assert sorted((j, k) for (j, k, b) in C3) == sorted(TEXT), sorted(C3) assert max(j for (j, k, b) in C3) <= 9 def abel(cdict): Dd = {b: {} for b in range(1, NBIN + 1)} for (j, k, b), v in cdict.items(): if k == 0: Dd[NBIN][(j, 0)] = Dd[NBIN].get((j, 0), 0) + v else: Dd[b][(j, k)] = Dd[b].get((j, k), 0) + v if b >= 2: Dd[b - 1][(j, k)] = Dd[b - 1].get((j, k), 0) - v return {b: {jk: v for jk, v in dd.items() if v != 0} for b, dd in Dd.items()} GBIN = int(os.environ.get('GBIN', str(NBIN))) GCLS = (0, 3, GBIN if NBIN > 1 else 1) DB = abel(C3); DG = abel({GCLS: Fr(1)}) log(f"bins: edges {[str(e) for e in EDGES]}; {len(C3)} constants; g = {GCLS}") log("c:", {kk: round(float(v), 6) for kk, v in sorted(C3.items())}) # ---------------------------------------------------------------- kernels (global: uncut rough kernel), powers, Lemma K kernels phi S1 = d_kernel(iE, iA); R1 = d_kernel(iA, iH) def build_powers(Rker): Pd = {}; PSd = {(1, 0): S1, (0, 1): Rker} for b in range(0, 10): for bp in range(0, 6): if b + bp < 2 or b * ETA + bp * ALPHA > 1: continue if bp >= 1: prev, ker, div = (b, bp - 1), Rker, bp else: prev, ker, div = (b - 1, 0), S1, b if prev not in PSd: continue Pd[(b, bp)] = d_div(conv_nn(PSd[prev], ker), div); PSd[(b, bp)] = Pd[(b, bp)] return Pd, PSd P, PS = build_powers(R1) log(f"powers: {len(P)}") def Rk(k): return R1 if k == 1 else PS[(0, k)] def Sst(r): return PS[(r, 0)] class Phis: def __init__(self, Pd, PSd): self.P, self.PS, self.TR, self.PHI = Pd, PSd, {}, {} def trs(self, bb): if bb not in self.TR: self.TR[bb] = None if (sum(bb) < 2 or bb not in self.P) else d_trunc(self.P[bb], iH) return self.TR[bb] def phi(self, j, k): if (j, k) in self.PHI: return self.PHI[(j, k)] acc = dz() for bs in range(0, j + 1): for br in range(0, k + 1): if bs + br < 2 or (bs, br) not in self.P: continue sign = (-1) ** (j + k + 1) * (-1) ** (bs + br); comp = (j - bs, k - br) if comp == (0, 0): X = d_trunc(self.P[(bs, br)], iH) else: if comp not in self.PS: continue X = conv_nn(self.trs((bs, br)), self.PS[comp]) acc = d_add(acc, X, sign) self.PHI[(j, k)] = d_trunc(acc, iH); return self.PHI[(j, k)] def lin_phi(self, coef): acc = dz() for jk, cv in coef.items(): if cv != 0: acc = d_add(acc, d_scale(self.phi(*jk), cv)) return acc def H_beta(self, jb, kb, dd): coef = {} for (cj, ck), cv in dd.items(): ju, ku = cj - jb, ck - kb if ju >= 0 and ku >= 0 and ju + ku >= 2: coef[(ju, ku)] = coef.get((ju, ku), 0) + cv return self.lin_phi(coef) if coef else None GPH = Phis(P, PS) phi = GPH.phi def rsum(ms): s = dz() for m in ms: if m == 1: s = d_add(s, R1) elif (0, m) in P: s = d_add(s, P[(0, m)]) return s RALL = rsum([1, 2, 3, 4, 5]); EP = rsum([2, 4]); EM = rsum([1, 3, 5]) def E_conv(X, rho_c, twisted=True, nodelta=False): """E_rho^{(c)} * X: twisted (-1)^c (delta + E'+ - E'-) * X; untwisted (delta + R_all) * X""" if twisted: out = dz() if nodelta else X out = d_add(out, conv_sn(X, EP)); out = d_add(out, conv_sn(X, EM), -1) return d_neg(out) if (rho_c or 0) % 2 == 1 else out out = dz() if nodelta else X return d_add(out, conv_sn(X, RALL)) log("kernels ready") # exact values of (f*g)(1) and int f g, without building the whole convolution (no curvature needed at a grid point) def _N_at(F, G, k, mode): a, b = F; c, d = G; tot = 0 if mode == 'conv': # n + m = k - 1 for n in range(max(0, k - M), min(M, k)): m = k - 1 - n if m < 0 or m >= M: continue an, bn, cm, dm = a[n], b[n], c[m], d[m] if an or bn: tot += (an * cm + bn * dm) + 2 * (an * dm + bn * cm) else: # corr at s = 0: n = m for n in range(M): an, bn, cm, dm = a[n], b[n], c[n], d[n] if (an or bn) and (cm or dm): tot += 2 * (an * cm + bn * dm) + (an * dm + bn * cm) return tot def val_sn(f, g, mode): """interval of (f*g)(1) (mode 'conv') or int f g (mode 'corr'), f signed, g >= 0""" S6 = 6 * M * SCALE glo = _pos_lo(g.la, g.lb); ghi = _pos_hi(g.ua, g.ub) lo = fl(_N_at(_pos_lo(f.la, f.lb), glo, M, mode), S6) - ce(_N_at(_neg_hi(f.la, f.lb), ghi, M, mode), S6) hi = ce(_N_at(_pos_hi(f.ua, f.ub), ghi, M, mode), S6) - fl(_N_at(_neg_lo(f.ua, f.ub), glo, M, mode), S6) return (lo, hi) # ---------------------------------------------------------------- one bin machine per edge (rough kernel cut at the edge) class Mach(Phis): def __init__(self, ecell): if ecell == iH: Pd, PSd = P, PS else: Pd, PSd = build_powers(d_kernel(iA, ecell)) Phis.__init__(self, Pd, PSd) if ecell == iH: self.PHI = GPH.PHI; self.TR = GPH.TR def f1_c(self, dd): acc = (0, 0) for jk, cv in dd.items(): if sum(jk) >= 2: acc = add_iv(acc, iv_scale(d_at1(self.phi(*jk)), cv)) return acc def T0_c(self, dd, twisted): rho = (lambda d: (-1) ** d) if twisted else (lambda d: 1) acc = (0, 0) if not dd: return acc for (j, k), cv in dd.items(): if (j, k) in self.P: acc = add_iv(acc, iv_scale(d_at1(self.P[(j, k)]), cv * rho(j + k))) if j + k >= 2: acc = add_iv(acc, iv_scale(d_at1(self.phi(j, k)), cv * rho(1))) jmax = max(j for j, k in dd); kmax = max(k for j, k in dd) for jb in range(0, jmax + 1): for kb in range(0, kmax + 1): if (jb, kb) == (0, 0) or (jb, kb) not in self.PS: continue Hb = self.H_beta(jb, kb, dd) if Hb is None: continue acc = add_iv(acc, iv_scale(val_sn(d_trunc(Hb, iH), self.PS[(jb, kb)], 'conv'), rho(1 + jb + kb))) return acc def A_dpl(self, base, twisted, dd): """A_base(x).c as a DPL in x = 1 - sigma (free part + extended part), DESIGN_GM""" rho = (lambda d: (-1) ** d) if twisted else (lambda d: 1) A = dz() if not dd: return A for (cj, ck), cv in dd.items(): if cj >= base: jz, kz = cj - base, ck if jz + kz >= 2 and (jz, kz) in self.P: A = d_add(A, d_scale(self.P[(jz, kz)], cv * rho(base + jz + kz))) jmax = max(j for j, k in dd); kmax = max(k for j, k in dd) for jp in range(0, jmax + 1): for kp in range(0, kmax + 1): coef = {} for (cj, ck), cv in dd.items(): ju, ku = cj - base - jp, ck - kp if ju >= 0 and ku >= 0 and ju + ku >= 2: coef[(ju, ku)] = coef.get((ju, ku), 0) + cv if not coef: continue Gk = self.lin_phi(coef) if (jp, kp) == (0, 0): X = Gk else: if (jp, kp) not in self.PS: continue X = conv_sn(d_trunc(Gk, iH), self.PS[(jp, kp)]) A = d_add(A, d_scale(X, rho(base + 1 + jp + kp))) return A MACH = {b: Mach(iEdge[b]) for b in range(1, NBIN + 1)} log(f"bin machines ready: {NBIN}") # ---------------------------------------------------------------- rough-count profile: B_{j,K}, brackets, slab chains KALL = list(range(2, 6)) def kin(k): return (KPROF is None) or (k in KPROF) def rho_(d, twisted): return (-1) ** d if twisted else 1 _RPHI = {} def RPHI(kw, ky): if (kw, ky) not in _RPHI: if (0, ky) not in P: _RPHI[(kw, ky)] = None elif kw == 0: _RPHI[(kw, ky)] = phi(0, ky) elif (0, kw) not in PS: _RPHI[(kw, ky)] = None else: _RPHI[(kw, ky)] = conv_sn(d_trunc(phi(0, ky), iH), PS[(0, kw)]) return _RPHI[(kw, ky)] _BK = {} def Bk(j, twisted): key = ('B', j % 2 if twisted else 0, twisted) if key not in _BK: acc = dz() for k in KALL: if not kin(k): continue if (0, k) in P: acc = d_add(acc, P[(0, k)], rho_(j + k, twisted)) for kw in range(0, k - 1): X = RPHI(kw, k - kw) if X is None: continue acc = d_add(acc, X, rho_(j + kw + 1, twisted)) _BK[key] = acc return _BK[key] def EB(c, twisted): """free-completion bracket sum_{k in K} rho(c+k) R_k + sum_{k in K} sum_{kw+ky=k, ky>=2} rho(c+1+kw) (R_kw * Phi_{0,ky}tr), as a DPL in x""" key = ('E', c % 2 if twisted else 0, twisted) if key not in _BK: acc = dz() for k in KALL: if not kin(k): continue if (0, k) in P: acc = d_add(acc, P[(0, k)], rho_(c + k, twisted)) for kw in range(0, k - 1): X = RPHI(kw, k - kw) if X is None: continue acc = d_add(acc, X, rho_(c + 1 + kw, twisted)) _BK[key] = acc return _BK[key] def blocks(lo_c, hi_c): n_c = hi_c - lo_c; bl = max(1, -(-n_c // NB)) return [(c0, min(c0 + bl, hi_c)) for c0 in range(lo_c, hi_c, bl)] def slab_br(br, t_lo, t_hi): Rb = Rk(br) return (d_trunc(Rb, iH - t_lo, iH), d_trunc(Rb, iH - t_hi, iH)) def conv_chain(kw, sl, m): cur = sl if kw >= 1: cur = conv_nn(cur, Rk(kw)) if m >= 1: cur = conv_nn(cur, Rk(m)) return cur def coefK(j, i, b, kw, ky, br, twisted): tot = 0 for i1 in range(0, i - b + 1): i2 = i - i1 s_out = rho_(j + i1 + kw + 1, twisted) tot += comb(i - b, i1) * s_out * (-1) ** (i2 + ky + 1) * (-1) ** b * (-1) ** br return tot def H_times_x(Hd, X, lo_u): """f(u) = H(u) X(1 - u) on u-cells [lo_u, iA) (X a DPL in x)""" return d_from_cells([cell_mul(d_ends(Hd, u), d_ends_rev(X, M - u - 1)) for u in range(lo_u, iA)], lo_u) def H_times_u(Hd, X, lo_u): """f(u) = H(u) X(u) on u-cells [lo_u, iA)""" return d_from_cells([cell_mul(d_ends(Hd, u), d_ends(X, u)) for u in range(lo_u, iA)], lo_u) # ---------------------------------------------------------------- refined threshold blocks (gm2/DESIGN_SO.md addendum 1): Part A exact at the block # start tau0, Part B the sawtooth rho(tau) = int_{tau0}^{tau} R_br(1/2 - t) dt times the range of g = R_kw * R_m on a window of width dtau. # BLOCKS=plain restores the narrow/wide (first-order) block bound for comparison. BLOCKMODE = os.environ.get('BLOCKS', 'refined') ALLCOMBOS = sorted(set((kw, br, k - kw - br) for k in KALL if kin(k) for kw in range(0, k) for br in range(1, k - kw + 1) if not ((br >= 2 and (0, br) not in PS) or (kw >= 2 and (0, kw) not in PS) or (k - kw - br >= 2 and (0, k - kw - br) not in PS)))) _GD = {} def g_dpl(kw, m): if (kw, m) not in _GD: if kw == 0 and m == 0: _GD[(kw, m)] = None elif kw == 0: _GD[(kw, m)] = Rk(m) elif m == 0: _GD[(kw, m)] = Rk(kw) else: _GD[(kw, m)] = conv_nn(Rk(kw), Rk(m)) return _GD[(kw, m)] def _sparse(vals, op): tab = [vals] while (1 << len(tab)) <= len(vals): h = 1 << (len(tab) - 1); a = tab[-1] tab.append([op(a[i], a[i + h]) for i in range(len(a) - h)]) def q(l, r): k = (r - l + 1).bit_length() - 1 return op(tab[k][l], tab[k][r - (1 << k) + 1]) return q _GR = {} def g_range(kw, m, dtc, kind): """(Gl, Gu) per cell n: the range of g = R_kw * R_m (>= 0) on the window of g-cells [iH-1-n-dtc, iH-1-n] (kind 'corr': argument 1/2 - y - s, s in [0, dtau], y in cell n) or [n-iH-dtc, n-iH] (kind 'conv': argument z - 1/2 - s, z in cell n); off-grid cells count as 0""" key = (kw, m, dtc, kind) if key in _GR: return _GR[key] g = g_dpl(kw, m) qlo = _sparse([min(a, b) for a, b in zip(g.la, g.lb)], min); qhi = _sparse([max(a, b) for a, b in zip(g.ua, g.ub)], max) Gl = [0] * M; Gu = [0] * M for n in range(M): c_lo, c_hi = (iH - 1 - n - dtc, iH - 1 - n) if kind == 'corr' else (n - iH - dtc, n - iH) vals_lo = []; vals_hi = [] if c_lo < 0 or c_hi >= M: vals_lo.append(0); vals_hi.append(0) a_, b_ = max(c_lo, 0), min(c_hi, M - 1) if a_ <= b_: vals_lo.append(qlo(a_, b_)); vals_hi.append(qhi(a_, b_)) Gl[n] = max(0, min(vals_lo)); Gu[n] = max(0, max(vals_hi)) _GR[key] = (Gl, Gu) return _GR[key] def rho_dpl(br, bl): """rho(tau) = int_{tau0(block)}^{tau} R_br(1/2 - t) dt on the tau-cells of the blocks bl, as a DPL (linear bounds from the min/max of R_br's enclosure on the mirrored cell; the cumulative sums are exact integrals of R_br's linear bounds)""" Rb = Rk(br); la = [0] * M; lb = [0] * M; ua = [0] * M; ub = [0] * M for (c0, c1) in bl: acc_lo = acc_hi = 0 for c in range(c0, c1): n = iH - 1 - c rl = max(0, min(Rb.la[n], Rb.lb[n])); ru = max(Rb.ua[n], Rb.ub[n]) la[c] = acc_lo; lb[c] = acc_lo + fl(rl, M); ua[c] = acc_hi; ub[c] = acc_hi + ce(ru, M) acc_lo += fl(max(Rb.la[n] + Rb.lb[n], 0), 2 * M) acc_hi += ce(Rb.ua[n] + Rb.ub[n], 2 * M) return D(la, lb, ua, ub) def W_dpl(b, br, bl): rho = rho_dpl(br, bl); S = Sst(b); lo_c, hi_c = bl[0][0], bl[-1][1] return d_from_cells([cell_mul(d_ends(S, c), d_ends(rho, c)) for c in range(lo_c, hi_c)], lo_c) def H_pm(Hd): lp = _pos_lo(Hd.la, Hd.lb); up = _pos_hi(Hd.ua, Hd.ub); ln = _neg_lo(Hd.ua, Hd.ub); un = _neg_hi(Hd.la, Hd.lb) return D(lp[0], lp[1], up[0], up[1]), D(ln[0], ln[1], un[0], un[1]) def _gI(G, Ip, Im, c): """c * [Gl I+ - Gu I-, Gu I+ - Gl I-] per cell (G constant per cell, I+- >= 0 DPLs), as a DPL""" Gl, Gu = G lo_a = [fl(gl * ipa - gu * ima, SCALE) for gl, gu, ipa, ima in zip(Gl, Gu, Ip.la, Im.ua)] lo_b = [fl(gl * ipb - gu * imb, SCALE) for gl, gu, ipb, imb in zip(Gl, Gu, Ip.lb, Im.ub)] hi_a = [ce(gu * ipa - gl * ima, SCALE) for gl, gu, ipa, ima in zip(Gl, Gu, Ip.ua, Im.la)] hi_b = [ce(gu * ipb - gl * imb, SCALE) for gl, gu, ipb, imb in zip(Gl, Gu, Ip.ub, Im.lb)] X = D(lo_a, lo_b, hi_a, hi_b) return d_scale(X, c) def slab_corr(Hd, lo_u, i, coefs, combos, at0=False): """sum_b sum_combos coef(b, kw, br, m) * int int H(u) X_tau(1 - u) S_b(tau) S_{i-b}(u - tau - sigma) dtau du for each coefficient function in coefs; DPLs in sigma (or intervals at sigma = 0 if at0). kw = m = 0 terms vanish here (argument 1 - u > 1/2 is outside the slab).""" combos = [cb for cb in combos if cb[0] + cb[2] >= 1] res = [((0, 0) if at0 else dz()) for _ in coefs] def acc_(o, X): if at0: res[o] = add_iv(res[o], X) else: res[o] = d_add(res[o], X) for b in range(1, i + 1): bl = blocks(b * iE, iA); dtc = max(c1 - c0 for c0, c1 in bl) cmb = [cb for cb in combos if any(cf(b, *cb) != 0 for cf in coefs)] if not cmb: continue for (c0, c1) in bl: Kb = d_trunc(Sst(b), c0, c1); K = Kb if b == i else conv_nn(Kb, Sst(i - b)) if BLOCKMODE == 'refined': X0 = {cb: conv_chain(cb[0], d_trunc(Rk(cb[1]), iH - c0, iH), cb[2]) for cb in cmb} for o, cf in enumerate(coefs): Q = dz() for cb, X in X0.items(): cv = cf(b, *cb) if cv: Q = d_add(Q, d_scale(X, cv)) f = H_times_x(Hd, Q, lo_u) acc_(o, val_sn(f, K, 'corr') if at0 else corr_sn(f, K)) else: ch = {} for cb in cmb: sn, sw = slab_br(cb[1], c0, c1); ch[cb] = (conv_chain(cb[0], sn, cb[2]), conv_chain(cb[0], sw, cb[2])) for o, cf in enumerate(coefs): Q = dz() for cb, (Xn, Xw) in ch.items(): cv = cf(b, *cb) if cv > 0: Q = d_add(Q, D([cv * a for a in Xn.la], [cv * a for a in Xn.lb], [cv * a for a in Xw.ua], [cv * a for a in Xw.ub])) elif cv < 0: Q = d_add(Q, D([cv * a for a in Xw.ua], [cv * a for a in Xw.ub], [cv * a for a in Xn.la], [cv * a for a in Xn.lb])) f = H_times_x(Hd, Q, lo_u) acc_(o, val_sn(f, K, 'corr') if at0 else corr_sn(f, K)) if BLOCKMODE != 'refined': continue Hp, Hm = H_pm(Hd) for br in sorted(set(cb[1] for cb in cmb)): W = W_dpl(b, br, bl) Ip, Im = corr_nn(Hp, W), corr_nn(Hm, W) for o, cf in enumerate(coefs): PB = None for cb in cmb: if cb[1] != br: continue cv = cf(b, *cb) if not cv: continue t_ = _gI(g_range(cb[0], cb[2], dtc, 'corr'), Ip, Im, cv) PB = t_ if PB is None else d_add(PB, t_) if PB is None: continue if b < i: acc_(o, val_sn(PB, Sst(i - b), 'corr') if at0 else corr_sn(PB, Sst(i - b))) else: acc_(o, (PB.la[0], PB.ua[0]) if at0 else PB) return res def coupling(j, i, Hd): """(twisted, untwisted) C_{j,i}[H_{j+i}](sigma) as DPLs in sigma (DESIGN_GM): free + i2 = 0 part, then the i2 >= 1 slab terms""" lo_u = (j + i) * iE res = [corr_sn(H_times_x(Hd, EB(j + i, tw), lo_u), Sst(i)) for tw in (True, False)] ext = slab_corr(Hd, lo_u, i, [lambda b, kw, br, m, tw=tw: coefK(j, i, b, kw, br + m, br, tw) for tw in (True, False)], ALLCOMBOS) return d_add(res[0], ext[0]), d_add(res[1], ext[1]) def coupling_at0(i, Hd): """(twisted, untwisted) C_{0,i}[H_i] at sigma = 0, as intervals""" lo_u = i * iE res = [val_sn(H_times_x(Hd, EB(i, tw), lo_u), Sst(i), 'corr') for tw in (True, False)] ext = slab_corr(Hd, lo_u, i, [lambda b, kw, br, m, tw=tw: coefK(0, i, b, kw, br + m, br, tw) for tw in (True, False)], ALLCOMBOS, at0=True) return add_iv(res[0], ext[0]), add_iv(res[1], ext[1]) # ---------------------------------------------------------------- Step A: top-down forcing H = {}; untw_bad = {} for j in range(MSTAR, 0, -1): lo_c = j * iE; cells = range(lo_c, iA) At = dz(); Au = dz() for b in range(1, NBIN + 1): At = d_add(At, MACH[b].A_dpl(j, True, DB[b])); Au = d_add(Au, MACH[b].A_dpl(j, False, DB[b])) Btw, Bun = Bk(j, True), Bk(j, False) num = [d_ends_rev(At, M - u - 1) for u in cells] bad = sum(1 for u in cells if not cell_contains0(d_ends_rev(Au, M - u - 1))) + sum(1 for u in cells if not cell_contains0(d_ends_rev(Bun, M - u - 1))) wA = max(max(x[2] - x[0], x[3] - x[1]) for x in num) for i in range(1, MSTAR - j + 1): Ct, Cu = coupling(j, i, H[j + i]) bu = sum(1 for u in cells if not cell_contains0(d_ends(Cu, u))) bad += bu num = [cell_add(x, d_ends(Ct, u)) for x, u in zip(num, cells)] log(f" T{j}: coupling to H{j+i}: twisted width max {fz(d_maxwidth(Ct, lo_c, iA)):.3e}; untwisted cells not containing 0: {bu}/{len(cells)}") Bc = [d_ends_rev(Btw, M - u - 1) for u in cells] zc = [u for u, bb in zip(cells, Bc) if not ((bb[0] > 0 and bb[1] > 0) or (bb[2] < 0 and bb[3] < 0))] if zc: log(f"T{j}: B may vanish on {len(zc)} cells, sigma in [{zc[0]/M:.5f}, {zc[-1]/M:.5f}]"); sys.exit(2) Hc = [cell_neg_quot(n_, b_) for n_, b_ in zip(num, Bc)] H[j] = d_from_cells(Hc, lo_c); untw_bad[j] = bad log(f"T{j}: B in [{fz(min(min(x[0], x[1]) for x in Bc)):+.4f}, {fz(max(max(x[2], x[3]) for x in Bc)):+.4f}]; " f"H{j} in [{fz(d_minlow(H[j], lo_c, iA)):+.4f}, {fz(d_maxup(H[j], lo_c, iA)):+.4f}]; A-part width max {fz(wA):.3e}; " f"H width max {fz(d_maxwidth(H[j], lo_c, iA)):.3e}; untwisted A/B/C cell ends not enclosing 0: {bad}") # ---------------------------------------------------------------- Step B: T0 and f(1) def Omega_rK(Hd, r, kset): """Omega^K_r[H](a) as a DPL in a (DESIGN_GM addendum 2; b = r term by the per-br slab identity; 1 <= b <= r-1 terms by blocks: refined (Part A at tau0 + Part B, DESIGN_SO addendum 1) for m >= 1, narrow/wide for m = 0)""" out = dz() HS = H_times_u(Hd, Sst(r), r * iE) Hp = Hm = None for k in kset: if k < 1: continue for br in range(1, k + 1): m = k - br if (br >= 2 and (0, br) not in PS) or (m >= 2 and (0, m) not in PS): continue X = d_trunc(conv_sn(HS, d_trunc(Rk(br), 0, iH)), iH) if m >= 1: X = conv_sn(X, Rk(m)) out = d_add(out, X, (-1) ** (r + k + 1) * (-1) ** r * (-1) ** br) for b in range(1, r): sgb = (-1) ** (r + k + 1) * (-1) ** b * (-1) ** br bl = blocks(b * iE, iA); dtc = max(c1 - c0 for c0, c1 in bl) if m == 0 or BLOCKMODE != 'refined': for (c0, c1) in bl: Kk = conv_nn(d_trunc(Sst(b), c0, c1), Sst(r - b)) w = H_times_u(Hd, Kk, r * iE) sn, sw = slab_br(br, c0, c1) Xn, Xw = conv_chain(0, sn, m), conv_chain(0, sw, m) out = d_add(out, conv_ss(w, D(Xn.la, Xn.lb, Xw.ua, Xw.ub)), sgb) continue for (c0, c1) in bl: # Part A: the chain exact at tau0 = c0 Kk = conv_nn(d_trunc(Sst(b), c0, c1), Sst(r - b)) w = H_times_u(Hd, Kk, r * iE) out = d_add(out, conv_sn(w, conv_chain(0, d_trunc(Rk(br), iH - c0, iH), m)), sgb) if Hp is None: Hp, Hm = H_pm(Hd) # Part B: S_{r-b} J+- convolved with the window range of R_m W = W_dpl(b, br, bl) Jp, Jm = corr_nn(Hp, W), corr_nn(Hm, W) S_ = Sst(r - b) Ap = d_from_cells([cell_mul(d_ends(S_, y), d_ends(Jp, y)) for y in range(M)], 0) Am = d_from_cells([cell_mul(d_ends(S_, y), d_ends(Jm, y)) for y in range(M)], 0) Gl, Gu = g_range(0, m, dtc, 'conv') Gd = D(list(Gl), list(Gl), list(Gu), list(Gu)) out = d_add(out, d_add(conv_nn(Ap, Gd), conv_nn(Am, Gd), -1), sgb) return out KSET = [k for k in KALL if kin(k)] T0t = (0, 0); T0u = (0, 0) for _b in range(1, NBIN + 1): T0t = add_iv(T0t, MACH[_b].T0_c(DB[_b], True)); T0u = add_iv(T0u, MACH[_b].T0_c(DB[_b], False)) log(f"T0's c-part: twisted [{fz(T0t[0]):+.6f}, {fz(T0t[1]):+.6f}]; untwisted [{fz(T0u[0]):+.6f}, {fz(T0u[1]):+.6f}]") for i in range(1, MSTAR + 1): ct, cu = coupling_at0(i, H[i]) log(f"T0's H{i} part: twisted [{fz(ct[0]):+.6f}, {fz(ct[1]):+.6f}]; untwisted [{fz(cu[0]):+.6f}, {fz(cu[1]):+.6f}] (must contain 0)") T0t = add_iv(T0t, ct); T0u = add_iv(T0u, cu) log(f"untwisted T0 (actual data): [{fz(T0u[0]):+.4e}, {fz(T0u[1]):+.4e}] (must contain 0)") F1c = (0, 0) for _b in range(1, NBIN + 1): F1c = add_iv(F1c, MACH[_b].f1_c(DB[_b])) log(f"f(1)'s c-part: [{fz(F1c[0]):+.6f}, {fz(F1c[1]):+.6f}]") OMK = {} for r in range(1, MSTAR + 1): OMK[r] = Omega_rK(H[r], r, KSET) part = d_at1(OMK[r]) log(f"f(1)'s H{r} part: [{fz(part[0]):+.6f}, {fz(part[1]):+.6f}]") F1c = add_iv(F1c, part) T0g = (0, 0); PHIG1 = (0, 0) for _b in range(1, NBIN + 1): T0g = add_iv(T0g, MACH[_b].T0_c(DG[_b], True)); PHIG1 = add_iv(PHIG1, MACH[_b].f1_c(DG[_b])) tiv = iv_div((-T0t[1], -T0t[0]), T0g) F1 = add_iv(F1c, iv_mul(tiv, PHIG1)) log(f"T0(c) in [{fz(T0t[0]):+.6f}, {fz(T0t[1]):+.6f}]; T0(g) in [{fz(T0g[0]):+.6f}, {fz(T0g[1]):+.6f}]; t in [{fz(tiv[0]):+.6f}, {fz(tiv[1]):+.6f}]") log(f"f(1) at c: [{fz(F1c[0]):+.6f}, {fz(F1c[1]):+.6f}]; on the segment: [{fz(F1[0]):+.6f}, {fz(F1[1]):+.6f}]") # ---------------------------------------------------------------- Step C: positivity (per-cell ranges: local first-order losses only) def realisable_free(j, k): if k == 0: return j * ETA < 1 < j * ALPHA return j * ETA + k * ALPHA < 1 < j * ALPHA + Fr(k, 2) def kset_of(kb): return sorted(set(k - kb for k in range(1, 6) if kin(k) and k - kb >= 1)) if KPROF is not None else list(range(1, 6)) free_min = 0; free_arg = None for j in range(0, int(1 / ETA) + 1): for k in range(0, 6): for bb in ([0] if k == 0 else range(1, NBIN + 1)): if not realisable_bin(j, k, bb): continue v = C3.get((j, k, bb), Fr(0)); lo = fl(v.numerator * SCALE, v.denominator) if (j, k, bb) == GCLS: lo += min(0, tiv[0]) cands = [lo] if 1 <= j <= MSTAR and kin(k): hlo = d_minlow(H[j], j * iE, iA) cands = [lo + hlo] if j == 1 else [lo + hlo, lo] for x in cands: if x < free_min: free_min, free_arg = x, (j, k, bb) log(f"free min >= {fz(free_min):+.6f} at {free_arg}") _L0K = {} def L0K(kb): ks = tuple(kset_of(kb)) if ks not in _L0K: acc = dz() for ky in ks: if ky >= 2 and (0, ky) in P: acc = d_add(acc, phi(0, ky)) _L0K[ks] = acc return _L0K[ks] _POK = {} def POK(kb): ks = tuple(kset_of(kb)) if ks not in _POK: acc = dz() for r in range(1, MSTAR + 1): acc = d_add(acc, OMK[r] if list(ks) == KSET else Omega_rK(H[r], r, list(ks))) _POK[ks] = acc return _POK[ks] def J_fnK(jb, i2, ks): """(j_b >= 1, k_b = 0) h-term with i2 >= 1 small fragments, per rough count, as a DPL in sigma_beta (slab terms via slab_corr: kw = 0)""" combos = sorted(set((0, br, k - br) for k in ks for br in range(1, k + 1) if not ((br >= 2 and (0, br) not in PS) or (k - br >= 2 and (0, k - br) not in PS)))) def cf(b, kw, br, m): k = br + m if kw != 0 or k not in ks: return 0 return (-1) ** (i2 + k + 1) * (-1) ** b * (-1) ** br return slab_corr(H[jb + i2], (jb + i2) * iE, i2, [cf], combos)[0] JK = {jb: {i2: J_fnK(jb, i2, kset_of(0)) for i2 in range(1, MSTAR - jb + 1)} for jb in range(1, MSTAR)} log("J functions ready:", {jb: list(JK[jb]) for jb in JK}) ext_min = 0; ext_arg = None; EXT = {} def upd(val, arg): global ext_min, ext_arg key = arg[:2] if key not in EXT or val[0] < EXT[key][0]: EXT[key] = (val[0], arg) if val[0] < ext_min: ext_min, ext_arg = val[0], arg def make_rq(j): lo_c = j * iE lo_ = [min(H[j].la[u], H[j].lb[u]) for u in range(lo_c, iA)]; hi_ = [max(H[j].ua[u], H[j].ub[u]) for u in range(lo_c, iA)] SPmin, SPmax = [lo_], [hi_] while (1 << len(SPmin)) <= len(lo_): kk = len(SPmin); h = 1 << (kk - 1); a_, b_ = SPmin[-1], SPmax[-1] SPmin.append([min(a_[i], a_[i + h]) for i in range(len(a_) - h)]); SPmax.append([max(b_[i], b_[i + h]) for i in range(len(b_) - h)]) def rq(l, r): out_lo = []; out_hi = [] if r >= iA: out_lo.append(0); out_hi.append(0); r = iA - 1 if l < lo_c: out_lo.append(0); out_hi.append(0); l = lo_c if l <= r: l2, r2 = l - lo_c, r - lo_c; kk = (r2 - l2 + 1).bit_length() - 1 out_lo.append(min(SPmin[kk][l2], SPmin[kk][r2 - (1 << kk) + 1])); out_hi.append(max(SPmax[kk][l2], SPmax[kk][r2 - (1 << kk) + 1])) return (min(out_lo), max(out_hi)) if out_lo else (0, 0) return rq RQ = {j: make_rq(j) for j in range(1, MSTAR + 1)} QB = {} def get_QB(jb, kb): key = (jb, tuple(kset_of(kb))) if key not in QB: lst = [] for (c0, c1) in blocks(jb * iE, iA): hr = RQ[jb](c0, c1 - 1); oms = [] for i2 in range(1, MSTAR - jb + 1): Hsh = d_const_cells([RQ[jb + i2](c0 + i, c1 + i) for i in range(i2 * iE, iA)], i2 * iE) oms.append(Omega_rK(Hsh, i2, kset_of(kb))) lst.append((c0, c1, hr, oms)) QB[key] = lst return QB[key] HBB = {}; HBG = {} for jb in range(0, int(1 / (2 * ETA)) + 1): for kb in range(0, 4): for b in range(1, NBIN + 1): HBB[(jb, kb, b)] = MACH[b].H_beta(jb, kb, DB[b]); HBG[(jb, kb, b)] = MACH[b].H_beta(jb, kb, DG[b]) def sum_d(lst): acc = None for x in lst: if x is None: continue acc = x if acc is None else d_add(acc, x) return acc def min_aq(n, L0_, L1_): """lower bound of min over a in a-cell n of a * L(a), L the linear function with (scaled) end values L0_, L1_ (a > 0): the endpoint values minus the convexity slack (h^2/8) * 2 L' = (h/4) max(L1 - L0, 0)""" return min(fl(n * L0_, M), fl((n + 1) * L1_, M)) - ce(max(L1_ - L0_, 0), 4 * M) def t_ends(Hg, n): """lower bound ends of t * Hg on a-cell n, t in tiv (the min of linear functions is concave, so the chord through the end minima is below)""" if Hg is None: return (0, 0) out = [] for lo_, hi_ in ((Hg.la[n], Hg.ua[n]), (Hg.lb[n], Hg.ub[n])): out.append(min(fl(tv * hv, SCALE) for tv in tiv for hv in (lo_, hi_))) return tuple(out) def mulL(Hv, L0e, e): """lower bound of Hv * L0(a) at a-end e (Hv a constant)""" return fl(Hv * (L0e[e] if Hv >= 0 else L0e[2 + e]), SCALE) for jb in range(0, int(1 / (2 * ETA)) + 1): for kb in range(0, 4): for bbeta in ([0] if kb == 0 else range(1, NBIN + 1)): if (jb, kb) == (0, 0): continue tlo, thi = class_total_range(jb, kb, bbeta) if tlo >= Fr(1, 2): continue Hb = sum_d([HBB[(jb, kb, b)] for b in range(max(bbeta, 1), NBIN + 1)]) Hg = sum_d([HBG[(jb, kb, b)] for b in range(max(bbeta, 1), NBIN + 1)]) L0b = L0K(kb); hasH = (jb >= 1 and jb <= MSTAR and len(kset_of(kb)) > 0) QBl = get_QB(jb, kb) if (hasH and kb >= 1 and jb < MSTAR) else None for n in range(iH, M): tau_lo, tau_hi = 1 - Fr(n + 1, M), 1 - Fr(n, M) if tau_hi <= tlo or tau_lo >= thi: continue tg = t_ends(Hg, n) b0 = (Hb.la[n] if Hb is not None else 0) + tg[0]; b1 = (Hb.lb[n] if Hb is not None else 0) + tg[1] if jb == 0: Pk = POK(kb); upd((min_aq(n, b0 + Pk.la[n], b1 + Pk.lb[n]),), (jb, kb, n / M)) elif hasH and kb == 0: ib = M - n - 1 if ib >= iA: upd((min_aq(n, b0, b1),), (jb, kb, n / M)); continue if ib < jb * iE: continue Hj = H[jb] pr = cell_mul((Hj.lb[ib], Hj.la[ib], Hj.ub[ib], Hj.ua[ib]), d_ends(L0b, n)) L0_, L1_ = b0 + pr[0], b1 + pr[1] for i2 in range(1, MSTAR - jb + 1): Jd = JK[jb][i2]; L0_ += Jd.lb[ib]; L1_ += Jd.la[ib] upd((min_aq(n, L0_, L1_),), (jb, kb, n / M, ib / M)) elif hasH: # beta's kb rough parts: the largest in bin bbeta, the others in [alpha', E[bbeta]], so their total lies in # [E[bbeta-1] + (kb-1) alpha', kb E[bbeta]]; with one bin this is the old [kb alpha', kb/2] sg_lo = max(jb * ETA, tau_lo - kb * EDGES[bbeta]); sg_hi = min(jb * ALPHA, tau_hi - EDGES[bbeta - 1] - (kb - 1) * ALPHA) if sg_lo > sg_hi: continue if sg_hi > ALPHA: upd((min_aq(n, b0, b1),), (jb, kb, n / M, 'noH')) L0e = d_ends(L0b, n); Hj = H[jb] u_lo = max(jb * iE, int(sg_lo * M) - 1); u_hi = min(iA - 1, int(min(sg_hi, ALPHA) * M)) for u in range(u_lo, u_hi + 1): if Fr(u + 1, M) < sg_lo or Fr(u, M) > min(sg_hi, ALPHA): continue Hv = (Hj.la[u], Hj.lb[u], Hj.ua[u], Hj.ub[u]) m0 = min(mulL(h_, L0e, 0) for h_ in Hv); m1 = min(mulL(h_, L0e, 1) for h_ in Hv) L0_, L1_ = b0 + m0, b1 + m1 if QBl is not None: for (c0, c1, hr, oms) in QBl: if c0 <= u < c1: for om in oms: L0_ += om.la[n]; L1_ += om.lb[n] break upd((min_aq(n, L0_, L1_),), (jb, kb, n / M, u / M, 'b%d' % bbeta)) else: upd((min_aq(n, b0, b1),), (jb, kb, n / M)) log(f"extended min >= {fz(ext_min):+.6f} at {ext_arg}") for key in sorted(EXT): log(f" extended min for (j_b, k_b) = {key}: {fz(EXT[key][0]):+.6f} at {EXT[key][1]}") m_ = min(free_min, ext_min) margin = 1 - Fr(-m_) / Fr(-F1[1]) if (m_ < 0 and F1[1] < 0) else Fr(-1) verdict = "PASS" if (F1[1] < 0 and m_ > F1[1] and all(v == 0 for v in untw_bad.values()) and T0u[0] <= 0 <= T0u[1]) else "FAIL" log(f"VERDICT {verdict}: min f >= {fz(m_):+.6f}, f(1)_hi = {fz(F1[1]):+.6f}, scaled margin >= {float(margin):.5f} (print rounding: quote the JSON value rounded down); untwisted bad {untw_bad}") json.dump(dict(M=M, NB=NB, tag=TAG_, engine='second-order DPL (gm2/cert2_v2.py)', script_sha256=hashlib.sha256(open(__file__, 'rb').read()).hexdigest(), dpl_sha256=hashlib.sha256(open(dpl.__file__, 'rb').read()).hexdigest(), block_mode=BLOCKMODE, kprof=('all' if KPROF is None else sorted(KPROF)), eta=str(ETA), alpha=str(ALPHA), mstar=MSTAR, edges=[str(e) for e in EDGES], gcls=list(GCLS), pickle_sha256=PKL_SHA, c={str(kk): str(v) for kk, v in sorted(C3.items())}, T0=[str(Fr(x, SCALE)) for x in T0t], T0u=[str(Fr(x, SCALE)) for x in T0u], T0g=[str(Fr(x, SCALE)) for x in T0g], t=[str(Fr(x, SCALE)) for x in tiv], f1=[str(Fr(x, SCALE)) for x in F1], free_min=str(Fr(free_min, SCALE)), ext_min=str(Fr(ext_min, SCALE)), ext_arg=str(ext_arg), untwisted_bad=untw_bad, verdict=verdict, margin=str(margin)), open(f'cert2v2_{TAG_}_M{M}.json', 'w'), indent=1)