"""p5rig.py: a separately written RIGOROUS first-order enclosure of the (1/20, 1/5) function, written blind from the mathematical text. Arithmetic: exact integer convolutions (vconv.py); outward binary64 interval operations; raw positive window updates and signed suffix sums use aggregate error bounds. The mesh enters through division by the exact integer M; outward read-outs. Model: eta = 1/20, alpha' = 1/5, bins of the largest rough part; f = c[j,k,b] + [k = 3, 1 <= j <= 3, tau <= alpha'] H_j(tau). Exact rewrites used (each an identity): (Z) XS_k(t; 1/2) - XS_k(t; 1/2 - sig) = Z_k(t; sig): Z_1 = -R1(t)1_W(t), Z_2 = P11 - R2(t)1_W(t), Z_3 = -P12 + P21, where P_{br,m}(t; sig) = int_{W(sig)} R_br(u) R_m(t - u) du, W(sig) = [1/2 - sig, 1/2) (nonnegative, increasing in sig). (L) Lambda^{(j)}_k(a; tau) = S_j(tau) Z_k(a - tau; tau) + int w_j(sig, tau) Z_k(a - tau; sig) dsig, w_1 = 0, w_2 = -s(sig) s(tau - sig), w_3 = s(sig) S_2(tau - sig) - S_2(sig) s(tau - sig) (from M_j = rho^{*j}/j!). (Y) sum_kw sg(kw) R_kw * Z_{3-kw} = Ytilde: twisted -4 P12 + 2 P21, untwisted 0 (R_a * R_b = C(a+b, a) R_{a+b}). (B) In row j_D, the free completions plus the extended ones with j_y = 0 add up to S_dj(u) B_J(1 - tau) (J = j_D + dj); in cert mode B_J(1 - tau) H_J(tau) = -A_J(1 - tau) - I_J(tau) by the forcing of H_J (exact); check mode keeps the product. Usage: p5rig.py M [cert|check] [Q] [Mc] [Qc] (Mc: coarse resolution for the far strata, M % Mc == 0; Qc: tau_b groups; reads constants_p5.tsv from the working directory) """ import sys import time from fractions import Fraction as Fr import numpy as np from flint import fmpz_poly from vconv import Exact, dn, nz_range, pos_neg, scale_exp, to_poly, up U = 2.0 ** -53 INF = np.inf def gam(n): return 1.01 * n * U / (1.0 - n * U) def iadd(a, b): return (dn(a[0] + b[0]), up(a[1] + b[1])) def isub(a, b): return (dn(a[0] - b[1]), up(a[1] - b[0])) def ineg(a): return (-a[1], -a[0]) def iscal(c, a): if c >= 0: return (dn(c * a[0]), up(c * a[1])) return (dn(c * a[1]), up(c * a[0])) def imul(a, b): p1 = a[0] * b[0]; p2 = a[0] * b[1]; p3 = a[1] * b[0]; p4 = a[1] * b[1] return (dn(np.minimum(np.minimum(p1, p2), np.minimum(p3, p4))), up(np.maximum(np.maximum(p1, p2), np.maximum(p3, p4)))) def idiv(a, b): b0 = np.asarray(b[0], float); b1 = np.asarray(b[1], float) assert np.all((b0 > 0) | (b1 < 0)), "divisor interval contains 0" return imul(a, (dn(1.0 / b1), up(1.0 / b0))) def iunion(a, b): return (np.minimum(a[0], b[0]), np.maximum(a[1], b[1])) def isum(a): lo = np.asarray(a[0], float); hi = np.asarray(a[1], float); n = lo.size g = gam(n + 1) slo = float(np.sum(lo)) - g * float(np.sum(np.abs(lo))) - 1e-300 shi = float(np.sum(hi)) + g * float(np.sum(np.abs(hi))) + 1e-300 return (float(dn(dn(slo))), float(up(up(shi)))) def isel(a, idx): return (a[0][idx], a[1][idx]) def izeros(n): return (np.zeros(n), np.zeros(n)) def ifloat(x): return (float(x[0]), float(x[1])) def ihM(c, M): Mf = float(M) return (dn(np.asarray(c[0], float) / Mf), up(np.asarray(c[1], float) / Mf)) def fmt_bound(x, places=5, upper=False): """Decimal endpoint rounded outward from the exact binary64 value (an audit's fix).""" x = float(x) if not np.isfinite(x): return str(x) n, d = x.as_integer_ratio() scale = 10 ** places q = -((-n * scale) // d) if upper else (n * scale) // d sign = "-" if q < 0 else "" q = abs(q) return f"{sign}{q // scale}.{q % scale:0{places}d}" def fmt_iv(a, places=5): return f"[{fmt_bound(a[0], places)}, {fmt_bound(a[1], places, upper=True)}]" ETA, AL = Fr(1, 20), Fr(1, 5) EB = [Fr(1, 5), Fr(1, 4), Fr(1, 3), Fr(5, 12), Fr(1, 2)] def bins_of(k): return [0] if k == 0 else [1, 2, 3, 4] def realisable(j, k, b): if k == 0: if b != 0: return False lo, hi = j * ETA, j * AL else: if not 1 <= b <= 4: return False lo, hi = j * ETA + (k - 1) * AL + EB[b - 1], j * AL + k * EB[b] return lo < 1 < hi def rough_range(k, b): return (k - 1) * AL + EB[b - 1], k * EB[b] def load_c(path="constants_p5.tsv"): c = {} for line in open(path): if line.startswith("#"): continue cls, _v, hx = line.rstrip("\n").split("\t") j, k, b = eval(cls) assert realisable(j, k, b) c[(j, k, b)] = float.fromhex(hx) return c def combo_range(M, terms_lo, terms_hi, n_lo, n_hi): """vconv's exact combination, converting only grid points n in [n_lo, n_hi] (n <= M). terms: (sign, F, a0, G, b0), F, G >= 0 segments.""" out = [] L = n_hi - n_lo + 1 for terms, lower in ((terms_lo, True), (terms_hi, False)): terms = [t for t in terms if t[1].size and t[3].size] G = np.zeros(L) if terms: SF = scale_exp([t[1] for t in terms]); SG = scale_exp([t[3] for t in terms]) if SF is not None and SG is not None: assert SF >= 0 and SG >= 0 base = min(t[2] + t[4] for t in terms) need = n_hi - base acc = fmpz_poly([]) for sgn, Fa, a0, Ga, b0 in terms: down = (sgn > 0) == lower sh = a0 + b0 - base if need - sh <= 0: continue A = to_poly(Fa, SF, upper=not down); B = to_poly(Ga, SG, upper=not down) P = A.mul_low(B, need - sh) if sh: P = P.left_shift(sh) acc = acc + P if sgn > 0 else acc - P co = acc.coeffs() S = SF + SG; Mf = float(M) for idx in range(L): k = n_lo + idx - base - 1 if 0 <= k < len(co): v = float(int(co[k])) if lower: G[idx] = dn(np.ldexp(dn(dn(v) / Mf), -S)) else: G[idx] = up(np.ldexp(up(up(v) / Mf), -S)) out.append(G) return out[0], out[1] class SparseMinMax: """range min of lo / range max of hi over index intervals [i0, i1] (inclusive).""" def __init__(self, lo, hi): self.lo = [np.asarray(lo, float)]; self.hi = [np.asarray(hi, float)] k = 1 while (1 << k) <= len(lo): p, q = self.lo[-1], self.hi[-1]; s = 1 << (k - 1) self.lo.append(np.minimum(p[:-s], p[s:])); self.hi.append(np.maximum(q[:-s], q[s:])) k += 1 def query(self, i0, i1): i0 = np.asarray(i0); i1 = np.asarray(i1) ln = i1 - i0 + 1 k = np.floor(np.log2(np.maximum(ln, 1))).astype(int) lo = np.full(i0.shape, np.inf); hi = np.full(i0.shape, -np.inf) for kk in np.unique(k): sel = k == kk a, b = i0[sel], i1[sel] - (1 << kk) + 1 lo[sel] = np.minimum(self.lo[kk][a], self.lo[kk][b]); hi[sel] = np.maximum(self.hi[kk][a], self.hi[kk][b]) return lo, hi # ---------------- kernels ---------------- class K5: def __init__(self, M, X, jmax=7, kmax=4): assert M % 60 == 0 self.M = M ie, ia, ih = M // 20, M // 5, M // 2 eb = [M // 5, M // 4, M // 3, 5 * M // 12, M // 2] self.ie, self.ia, self.ih, self.eb = ie, ia, ih, eb i = np.arange(M) inv_lo = np.zeros(M); inv_hi = np.zeros(M) inv_lo[1:] = dn(M / (i[1:] + 1.0)); inv_hi[1:] = up(M / i[1:].astype(float)) mk = lambda m: (np.where(m, inv_lo, 0.0), np.where(m, inv_hi, 0.0)) self.s = mk((i >= ie) & (i < ia)) self.rb = {b: mk((i >= eb[b - 1]) & (i < eb[b])) for b in range(1, 5)} self.r = mk((i >= ia) & (i < ih)) clip = lambda lohi, d: (np.maximum(dn(lohi[0] / d), 0.0), up(lohi[1] / d)) self.S = [None, self.s] for j in range(2, jmax + 1): self.S.append(clip(X.nn(self.S[-1], self.s), j)) self.Rk = [None, self.r] for k in range(2, kmax + 1): self.Rk.append(clip(X.nn(self.Rk[-1], self.r), k)) self.Rb = {} for b in range(1, 5): P = [None, self.rb[b]] for n in range(2, kmax + 1): P.append(clip(X.nn(P[-1], self.rb[b]), n)) if b == 1: for k in range(1, kmax + 1): self.Rb[(k, b)] = P[k] continue rl = mk((i >= ia) & (i < eb[b - 1])) Ql = [None, rl] for n in range(2, kmax + 1): Ql.append(clip(X.nn(Ql[-1], rl), n)) for k in range(1, kmax + 1): acc = P[k] items = [(1, P[n], Ql[k - n], 'nn') for n in range(1, k)] if items: cl = X.cells(*X.combo_grid(items)) acc = (np.maximum(dn(acc[0] + cl[0]), 0.0), up(acc[1] + cl[1])) self.Rb[(k, b)] = acc self.D = {} for j in range(jmax + 1): for k in range(kmax + 1): for b in bins_of(k): if j + k == 0: continue if k == 0: self.D[(j, 0, 0)] = self.S[j] elif j == 0: self.D[(0, k, b)] = self.Rb[(k, b)] else: self.D[(j, k, b)] = X.nn(self.S[j], self.Rb[(k, b)]) half = (np.arange(M) >= ih).astype(float) self.half = half self.Lam = {} for jy in range(jmax + 1): for ky in range(kmax + 1): if jy + ky < 2: continue for by in bins_of(ky): if not np.any(self.D[(jy, ky, by)][1] * half): continue kk = jy + ky items = [] for bs in range(jy + 1): for br in range(ky + 1): if (bs, br) in ((0, 0), (jy, ky)): continue for bB in bins_of(br): for bR in bins_of(ky - br): if max(bB, bR) != by: continue DB = self.D[(bs, br, bB)] if not np.any(DB[1] * half): continue sgn = (-1) ** (kk + 1) * (-1) ** (bs + br) items.append((sgn, (DB[0] * half, DB[1] * half), self.D[(jy - bs, ky - br, bR)], 'nn')) clo, chi = X.cells(*X.combo_grid(items)) if items else (np.zeros(M), np.zeros(M)) lo = dn(clo - self.D[(jy, ky, by)][1]); hi = up(chi - self.D[(jy, ky, by)][0]) self.Lam[(jy, ky, by)] = (lo * half, hi * half) # XS_k(.; 1/2) and Lambda0_k = -XS_k(.; 1/2) on a >= 1/2 self.Lam0 = {} for k in range(1, 4): items = [((-1) ** (k + br), (self.Rk[br][0] * half, self.Rk[br][1] * half), self.Rk[k - br], 'nn') for br in range(1, k)] cl = X.cells(*X.combo_grid(items)) if items else (np.zeros(M), np.zeros(M)) xs = iadd(cl, (self.Rk[k][0] * half, self.Rk[k][1] * half)) self.Lam0[k] = (-xs[1] * half, -xs[0] * half) # ---------------- the certificate ---------------- class Cert5: def __init__(self, M, c, mode="cert", Q=4, seed=1, log=print): self.M, self.mode, self.log, self.Q = M, mode, log, Q self.ie, self.ia, self.ih = M // 20, M // 5, M // 2 assert self.ie % Q == 0 self.t0 = time.monotonic() self.X = Exact(M) self.Kn = K5(M, self.X) log(f"{self.tl()} kernels (M = {M}; {len(self.Kn.Lam)} Lambda_y; {self.X.nconv} exact products)") self.c = dict(c) self.sg = (lambda d: 1 - 2 * (d % 2)) if mode == "cert" else (lambda d: 1) self.rng = np.random.default_rng(seed) self._ec = {} def tl(self): return f"[{time.monotonic() - self.t0:8.1f}s]" def EC(self, J, K, bw, c=None): c = self.c if c is None else c key = (J, K, bw, id(c)) if key not in self._ec: acc = None for (jy, ky, by), L in self.Kn.Lam.items(): v = c.get((J + jy, K + ky, max(bw, by)), 0.0) if v: t = iscal(v, L) acc = t if acc is None else iadd(acc, t) self._ec[key] = acc return self._ec[key] @staticmethod def _add(acc, t): return t if acc is None else iadd(acc, t) def Ac(self, jD, c=None): c = self.c if c is None else c Kn, X, sg = self.Kn, self.X, self.sg acc = None for (jp, kp, bp), Dk in Kn.D.items(): v = c.get((jD + jp, kp, bp), 0.0) if v: acc = self._add(acc, iscal(sg(jD + jp + kp) * v, Dk)) items = [] for jw in range(0, 8): for kw in range(0, 5): for bw in bins_of(kw): e = self.EC(jD + jw, kw, bw, c) if e is None: continue if jw + kw == 0: acc = self._add(acc, iscal(sg(1 + jD), e)) else: items.append((sg(1 + jD + jw + kw), Kn.D[(jw, kw, bw)], e, 'ns')) if items: acc = self._add(acc, X.cells(*X.combo_grid(items))) return acc if acc is not None else izeros(self.M) def setup(self): Kn, X, sg, M = self.Kn, self.X, self.sg, self.M self.A = {jD: self.Ac(jD) for jD in range(4)} self.RL0 = {0: Kn.Lam0[3]} for kw in (1, 2): self.RL0[kw] = X.signed(Kn.Rk[kw], Kn.Lam0[3 - kw]) self.B = {} for jD in range(4): acc = iscal(sg(jD + 3), Kn.Rk[3]) for kw in range(3): acc = iadd(acc, iscal(sg(1 + jD + kw), self.RL0[kw])) self.B[jD] = acc R1, R2 = Kn.Rk[1], Kn.Rk[2] self.Wk = {(1, 1): (R1, R1), (1, 2): (R1, R2), (2, 1): (R2, R1)} # P_{br,m}: (R_br, R_m) self.Yc = {(1, 2): -4.0, (2, 1): 2.0} if self.mode == "cert" else {(1, 2): 0.0, (2, 1): 0.0} self.log(f"{self.tl()} rows set up ({self.X.nconv} exact products)") # ---------------- windows ---------------- class Win: def __init__(self, C): self.C = C; M = C.M self.G = {key: [np.zeros(M + 1), np.zeros(M + 1)] for key in C.Wk} # [lower at n = nlo, upper at n = nhi] self.nlo = 0; self.nhi = 0 self._add(1) def _add(self, bound): C = self.C; M = C.M n = self.nlo if bound == 0 else self.nhi i = C.ih - n - 1 for key, (Rbr, Rm) in C.Wk.items(): hr = Rbr[bound][i] / float(M) if hr: self.G[key][bound][i + 1:] += hr * Rm[bound][:M - i] if bound == 0: self.nlo += 1 else: self.nhi += 1 def step(self): self._add(0); self._add(1) def comp(self, key, gl, gh): """lower and upper grid values of P_key at grid indices gl (lower window) / gh (upper window), widened.""" wl = 1.0 - gam(self.nlo + 3); wh = 1.0 + gam(self.nhi + 3) return dn(np.maximum(self.G[key][0][gl], 0.0) * wl), up(self.G[key][1][gh] * wh) def _pts(self, x0, x1, shift): """grid indices covering x in closed cells [x0, x1) shifted down by 'shift' cells over two cells: points j-shift-1, j-shift, j-shift+1.""" j = np.arange(x0, x1) return [j - shift - 1, j - shift, j - shift + 1] if shift is not None else [j, j + 1] def zcomb(self, win, coef, pts, delta=None, cells=None, l=None): """interval of sum_key coef[key] * P_key over the points pts (min/max), plus delta-terms -R_br(x) 1(x in W) for (br, cdel) in delta.""" lo = 0.0; hi = 0.0 for key, cf in coef.items(): if cf == 0.0: continue plo = np.minimum.reduce([win.comp(key, p, p)[0] for p in pts]); phi = np.maximum.reduce([win.comp(key, p, p)[1] for p in pts]) t = iscal(cf, (plo, phi)) lo = dn(lo + t[0]); hi = up(hi + t[1]) if delta: ih = self.ih for br, cdel in delta: R = self.Kn.Rk[br] c0, c1 = cells # the (one or two) x-cells as index arrays rlo = np.minimum(R[0][c0], R[0][c1]); rhi = np.maximum(R[1][c0], R[1][c1]) # Contract: x runs over the closed cells c0..c1, i.e. [c0 h, (c1 + 1) h], and sig over the closed cell l, i.e. # [l h, (l + 1) h]. sure: x is in W(sig) = [1/2 - sig, 1/2) for every such (x, sig); maybe: for at least one. # The closed x-range includes its right endpoint; the indicator is zero at x = 1/2. sure = (c0 >= ih - l) & (c1 < ih - 1) # The closed sig-cell includes sig = (l + 1) h, whose window starts at x = 1/2 - (l + 1) h (included). maybe = (c1 >= ih - l - 2) & (c0 <= ih - 1) dl = np.where(sure, rlo, 0.0); dh = np.where(maybe, rhi, 0.0) t = iscal(cdel, (dl, dh)) lo = dn(lo + t[0]); hi = up(hi + t[1]) return (lo, hi) def Zk(self, win, k, pts, cells, l): if k == 1: return self.zcomb(win, {}, pts, delta=[(1, -1.0)], cells=cells, l=l) if k == 2: return self.zcomb(win, {(1, 1): 1.0}, pts, delta=[(2, -1.0)], cells=cells, l=l) return self.zcomb(win, {(1, 2): -1.0, (2, 1): 1.0}, pts) def Yt(self, win, pts): return self.zcomb(win, self.Yc, pts) def at1m(self, m): """grid points of x = 1 - tau for tau in the closed cells m (array): cell M-1-m -> points M-1-m, M-m.""" return [self.M - 1 - m, self.M - m] def at1m_shift(self, i, l): """x = 1 - (s_i + sig'), s in closed cell i, sig' in cell l: x in cells M-i-l-2, M-i-l-1 -> points M-i-l-2 .. M-i-l.""" return [self.M - i - l - 2, self.M - i - l - 1, self.M - i - l] # ---------------- correlation with s ---------------- def corr_s(self, g, m0, m1, j_lo, j_hi): """C(y) = int g(tau) s(tau - y) dtau at grid points y = j/M, j in [j_lo, j_hi]; g an interval array on tau-cells [m0, m1).""" M = self.M gt = (g[0][::-1].copy(), g[1][::-1].copy()) # cells k = m1-1-m s = self.Kn.s rs = nz_range(s[1]); a0, a1 = rs (Ep0, Ep1), (Em0, Em1) = pos_neg(gt) Klo = np.maximum(s[0][a0:a1], 0.0); Khi = s[1][a0:a1] lo_terms = [(1, Klo, a0, Ep0, 0), (-1, Khi, a0, Em1, 0)] hi_terms = [(1, Khi, a0, Ep1, 0), (-1, Klo, a0, Em0, 0)] # C(j) = (gt * s)(grid n = m1 - j) n_lo, n_hi = m1 - j_hi, m1 - j_lo if n_hi < 0: return np.zeros(j_hi - j_lo + 1), np.zeros(j_hi - j_lo + 1) nl = max(n_lo, 0) Plo, Phi = combo_range(M, lo_terms, hi_terms, nl, n_hi) clo = np.zeros(j_hi - j_lo + 1); chi = np.zeros(j_hi - j_lo + 1) # index for j: n = m1 - j -> position n - nl js = np.arange(j_lo, j_hi + 1); ns = m1 - js ok = ns >= nl clo[ok] = Plo[ns[ok] - nl]; chi[ok] = Phi[ns[ok] - nl] return clo, chi # ---------------- forcing ---------------- def solve(self): M, ie, ia, ih = self.M, self.ie, self.ia, self.ih Kn = self.Kn s, S2 = Kn.s, Kn.S[2] cert = self.mode == "cert" rng = self.rng self.H = {}; self.Hx = {} tc = lambda lo_i, hi_i: M - 1 - np.arange(lo_i, hi_i) def setH(J, H): self.H[J] = H x = izeros(M); x[0][J * ie:ia] = H[0]; x[1][J * ie:ia] = H[1] self.Hx[J] = x # H3 m3 = np.arange(3 * ie, ia) A3 = isel(self.A[3], M - 1 - m3); B3 = isel(self.B[3], M - 1 - m3) if cert: assert np.all(B3[0] > 0) setH(3, idiv(ineg(A3), B3)) else: v = rng.normal(size=len(m3)); setH(3, (v.copy(), v.copy())) self.check_row(3, iadd(A3, imul(B3, self.H[3]))) # A_J at 1 - tau, zero outside H_J's support (for the substitutions) self.Ax = {}; self.Bx = {} for J in (1, 2, 3): x = izeros(M); y = izeros(M) mm = np.arange(J * ie, ia) a = isel(self.A[J], M - 1 - mm); b = isel(self.B[J], M - 1 - mm) x[0][J * ie:ia] = a[0]; x[1][J * ie:ia] = a[1]; y[0][J * ie:ia] = b[0]; y[1][J * ie:ia] = b[1] self.Ax[J] = x; self.Bx[J] = y # pass A: I23 (rows sigma in [2ie, ia)) and I13 (rows s in [ie, ia)), both from H3 I23 = izeros(M); I13 = izeros(M); I12 = izeros(M) self._subst(I23, 2, 3, s, sub=True) # -int s(tau - sigma) A3(1 - tau) (or the product form) self._subst(I13, 1, 3, S2, sub=True) # -int S2(tau - s) A3(1 - tau) self.window_pass_A(I23, I13) # H2 m2 = np.arange(2 * ie, ia) A2 = isel(self.A[2], M - 1 - m2); B2 = isel(self.B[2], M - 1 - m2) I23r = isel(I23, m2) if cert: assert np.all(B2[1] < 0) setH(2, idiv(ineg(iadd(A2, I23r)), B2)) else: v = rng.normal(size=len(m2)); setH(2, (v.copy(), v.copy())) self.check_row(2, iadd(iadd(A2, imul(B2, self.H[2])), I23r)) self.I23 = I23 # pass B: I12 from H2 (and the substitution with A2 + I23) self._subst(I12, 1, 2, s, sub=True, extra=I23) self.window_pass_B(I12) m1 = np.arange(ie, ia) A1 = isel(self.A[1], M - 1 - m1); B1 = isel(self.B[1], M - 1 - m1) I1r = iadd(isel(I12, m1), isel(I13, m1)) if cert: assert np.all(B1[0] > 0) setH(1, idiv(ineg(iadd(A1, I1r)), B1)) else: v = rng.normal(size=len(m1)); setH(1, (v.copy(), v.copy())) self.check_row(1, iadd(iadd(A1, imul(B1, self.H[1])), I1r)) self.I12, self.I13 = I12, I13 for J in (3, 2, 1): H = self.H[J] self.log(f"{self.tl()} H{J} within {fmt_iv((H[0].min(), H[1].max()))}, max width {np.max(H[1] - H[0]):.3e}; " f"B{J} within {fmt_iv((self.Bx[J][0][J*ie:ia].min(), self.Bx[J][1][J*ie:ia].max()))}") def check_row(self, J, T): ok = (T[0] <= 0) & (T[1] >= 0) hw = (T[1] - T[0]) / 2; mid = (T[1] + T[0]) / 2 self.log(f"{self.tl()} CHECK T{J} (untwisted, random data): 0 in {int(ok.sum())}/{len(ok)} cells; max |mid| {np.abs(mid).max():.3e}, " f"max half-width {hw.max():.3e}") if not hasattr(self, "checks"): self.checks = {} self.checks[J] = (int(ok.sum()), len(ok)) def _subst(self, I, jD, J, Kker, sub, extra=None): """I(sigma) += int Kker(tau - sigma) X(tau) dtau, tau in H_J's support, sigma-cells [jD ie, ia), where X = B_J(1 - tau) H_J(tau): cert mode X = -(A_J(1 - tau) + extra(tau)) exactly (the forcing of H_J); check mode keeps the product. tau in cells i+l, i+l+1.""" M, ie, ia = self.M, self.ie, self.ia if self.mode == "cert": Xv = self.Ax[J] if extra is None else iadd(self.Ax[J], extra) sup = np.zeros(M, bool); sup[J * ie:ia] = True Xv = ineg((np.where(sup, Xv[0], 0.0), np.where(sup, Xv[1], 0.0))) else: Xv = imul(self.Bx[J], self.Hx[J]) ii = np.arange(jD * ie, ia) for l in range(ie * (J - jD), ia): idx = np.minimum(ii + l, M - 1); idx2 = np.minimum(ii + l + 1, M - 1) xu = iunion(isel(Xv, idx), isel(Xv, idx2)) kl = ifloat(ihM((Kker[0][l], Kker[1][l]), M)) t = imul(kl, xu) I[0][ii] = dn(I[0][ii] + t[0]); I[1][ii] = up(I[1][ii] + t[1]) def window_pass_A(self, I23, I13): """Ytilde terms of I23 and I13 (H3 only).""" if self.mode != "cert": return M, ie, ia = self.M, self.ie, self.ia Kn = self.Kn s, S2 = Kn.s, Kn.S[2] win = self.Win(self) H3x = self.Hx[3] m3 = np.arange(3 * ie, ia) for l in range(0, ia): if ie <= l < ia - 2 * ie: # I23: -int H3(tau) s(u) Ytilde(1 - tau; u), u = tau - sigma in cell l, sigma-cells [2ie, ia) ii = np.arange(2 * ie, ia - l) H3u = iunion(isel(H3x, ii + l), isel(H3x, np.minimum(ii + l + 1, M - 1))) Y = self.Yt(win, self.at1m_shift(ii, l)) t = imul(imul(ifloat(ihM((s[0][l], s[1][l]), M)), H3u), Y) I23[0][ii] = dn(I23[0][ii] - t[1]); I23[1][ii] = up(I23[1][ii] - t[0]) # I13 (a): +int H3(tau) S2(u) Ytilde(1 - tau; u), u = tau - s in cell l, s-cells [ie, ia) if 2 * ie <= l < ia - ie: ii = np.arange(ie, ia - l) H3u = iunion(isel(H3x, ii + l), isel(H3x, np.minimum(ii + l + 1, M - 1))) Y = self.Yt(win, self.at1m_shift(ii, l)) t = imul(imul(ifloat(ihM((S2[0][l], S2[1][l]), M)), H3u), Y) I13[0][ii] = dn(I13[0][ii] + t[0]); I13[1][ii] = up(I13[1][ii] + t[1]) if ie <= l < ia - 2 * ie: # I13 (b): -2 int dsig' s(sig') sum_tau H3(tau) Ytilde(1 - tau; sig') s(tau - sig' - s) Yg = self.Yt(win, self.at1m(m3)) g = imul((H3x[0][m3], H3x[1][m3]), Yg) jl, jh = ie + l, ia + l + 1 C = self.corr_s(g, 3 * ie, ia, jl, jh) ii = np.arange(ie, ia - l - ie) # y = s + sig' with s in cell i, sig' in cell l: grid points i+l .. i+l+2 p = [ii + l - jl, ii + l + 1 - jl, np.minimum(ii + l + 2 - jl, jh - jl)] Clo = np.minimum.reduce([C[0][q] for q in p]); Chi = np.maximum.reduce([C[1][q] for q in p]) coef = iscal(-2.0, ifloat(ihM((s[0][l], s[1][l]), M))) t = imul(ifloat(coef), (Clo, Chi)) I13[0][ii] = dn(I13[0][ii] + t[0]); I13[1][ii] = up(I13[1][ii] + t[1]) win.step() def window_pass_B(self, I12): if self.mode != "cert": return M, ie, ia = self.M, self.ie, self.ia s = self.Kn.s win = self.Win(self) H2x = self.Hx[2] for l in range(0, ia): if ie <= l < ia - ie: # I12: +int H2(tau) s(u) Ytilde(1 - tau; u), u = tau - s in cell l, s-cells [ie, ia) ii = np.arange(ie, ia - l) H2u = iunion(isel(H2x, ii + l), isel(H2x, np.minimum(ii + l + 1, M - 1))) Y = self.Yt(win, self.at1m_shift(ii, l)) t = imul(imul(ifloat(ihM((s[0][l], s[1][l]), M)), H2u), Y) I12[0][ii] = dn(I12[0][ii] + t[0]); I12[1][ii] = up(I12[1][ii] + t[1]) win.step() # ---------------- weights w_J(sig', tau) on (l, m) cells ---------------- def wJ(self, J, l, m): """interval of w_J(sig', tau) for sig' in cell l, tau in cells m (array): w_2 = -s(sig')s(tau-sig'), w_3 = s S2 - S2 s.""" Kn = self.Kn s, S2 = Kn.s, Kn.S[2] def two(K, d): d0 = np.clip(d - 1, 0, self.M - 1); d1 = np.clip(d, 0, self.M - 1) z0 = d - 1 < 0; z1 = d < 0 lo = np.minimum(np.where(z0, 0.0, K[0][d0]), np.where(z1, 0.0, K[0][d1])); hi = np.maximum(np.where(z0, 0.0, K[1][d0]), np.where(z1, 0.0, K[1][d1])) return (lo, hi) d = m - l sl = (s[0][l], s[1][l]); S2l = (S2[0][l], S2[1][l]) if J == 2: return ineg(imul(sl, two(s, d))) return isub(imul(sl, two(S2, d)), imul(S2l, two(s, d))) # ---------------- pass C: T0, f(1), positivity window terms ---------------- def pass_C(self): M, ie, ia, ih = self.M, self.ie, self.ia, self.ih Kn = self.Kn; sg = self.sg S = Kn.S; s = Kn.s cert = self.mode == "cert" win = self.Win(self) Hx = self.Hx T0w = (0.0, 0.0); f1w = (0.0, 0.0) PhiD = {k: izeros(M - ih) for k in (1, 2)} # jb = 0 diagonal parts, a-cells [ih, M) Line = {jb: izeros(ia) for jb in (1, 2)} # (jb, 0, 0) line H-integrals, indexed by tau_b-cell mall = np.arange(ie, ia) aidx = np.arange(ih, M) for l in range(0, ia): if l >= ie: # ---- f(1) and T0 at x = 1 - tau Z3 = self.Zk(win, 3, self.at1m(mall), None, l) Yg = self.Yt(win, self.at1m(mall)) Z3l = (Z3[0][l - ie], Z3[1][l - ie]); Yl = (Yg[0][l - ie], Yg[1][l - ie]) for J in (1, 2, 3): if l >= J * ie: cf = ifloat(ihM(imul((Hx[J][0][l], Hx[J][1][l]), (S[J][0][l], S[J][1][l])), M)) f1w = ifloat(iadd(f1w, imul(cf, Z3l))) T0w = ifloat(iadd(T0w, imul(iscal(-1.0, cf), Yl))) # -H_J S_J Ytilde (j_w = 0 diagonal) # off-diagonal sums over tau-cells m (J = 2, 3), and the j_w >= 1 terms of T0 m = mall wf = izeros(len(m)); wt = izeros(len(m)) for J in (2, 3): w = self.wJ(J, l, m) hw = imul((Hx[J][0][m], Hx[J][1][m]), w) wf = iadd(wf, hw); wt = iadd(wt, iscal(-1.0, hw)) # j_w >= 1: -sg(jw) H_J(tau) S_jw(tau - sig') S_jy(sig') (J = jw + jy), and -2 H3 s(sig') S2(tau - sig') [J=3, jw=1, jy=2 w-part] def twoc(K, d): d0 = np.clip(d - 1, 0, M - 1); d1 = np.clip(d, 0, M - 1) return (np.minimum(np.where(d - 1 < 0, 0.0, K[0][d0]), np.where(d < 0, 0.0, K[0][d1])), np.maximum(np.where(d - 1 < 0, 0.0, K[1][d0]), np.where(d < 0, 0.0, K[1][d1]))) for J, jw in ((2, 1), (3, 1), (3, 2)): jy = J - jw t = imul(imul((Hx[J][0][m], Hx[J][1][m]), twoc(S[jw], m - l)), (S[jy][0][l], S[jy][1][l])) wt = iadd(wt, iscal(-float(sg(jw)), t)) t = imul(imul((Hx[3][0][m], Hx[3][1][m]), twoc(S[2], m - l)), (s[0][l], s[1][l])) wt = iadd(wt, iscal(-2.0, t)) f1w = ifloat(iadd(f1w, isum(imul(ihM(ihM(wf, M), M), Z3)))) T0w = ifloat(iadd(T0w, isum(imul(ihM(ihM(wt, M), M), Yg)))) # ---- positivity jb = 0 diagonal: (1/M) sum_J H_J(l) S_J(l) Z_k(a - tau; l), a-cells [ih, M) cfs = (0.0, 0.0) for J in (1, 2, 3): if l >= J * ie: cfs = ifloat(iadd(cfs, imul((Hx[J][0][l], Hx[J][1][l]), (S[J][0][l], S[J][1][l])))) cfs = ifloat(ihM(cfs, M)) pts = self._pts(ih, M, l) cells = (aidx - l - 1, aidx - l) for k in (1, 2): Zk = self.Zk(win, k, pts, cells, l) PhiD[k] = iadd(PhiD[k], imul(cfs, Zk)) # ---- (jb, 0, 0) lines, jb = 1, 2: a = 1 - tau_b, sum_{J > jb} int H_J(tau_b + tau') Lambda^{(J-jb)}_3(a; tau') dtau' for jb in (1, 2): for J in range(jb + 1, 4): j = J - jb if l < j * ie: continue ii = np.arange(jb * ie, ia - l) if len(ii) == 0: continue Hu = iunion(isel(Hx[J], ii + l), isel(Hx[J], np.minimum(ii + l + 1, M - 1))) Z = self.Zk(win, 3, self.at1m_shift(ii, l), None, l) t = imul(imul(ifloat(ihM((S[j][0][l], S[j][1][l]), M)), Hu), Z) Line[jb][0][ii] = dn(Line[jb][0][ii] + t[0]); Line[jb][1][ii] = up(Line[jb][1][ii] + t[1]) if ie <= l < ia - 2 * ie: # w_2 part of the (1,0,0) line, J = 3: -s(sig') sum_tau H3(tau) s(tau - tau_b - sig') Z3(1 - tau; sig') m3 = np.arange(3 * ie, ia) g = imul((Hx[3][0][m3], Hx[3][1][m3]), (Z3[0][m3 - ie], Z3[1][m3 - ie])) jl, jh = ie + l, ia + l + 1 C = self.corr_s(g, 3 * ie, ia, jl, jh) ii = np.arange(ie, ia - l - ie) p = [ii + l - jl, ii + l + 1 - jl, np.minimum(ii + l + 2 - jl, jh - jl)] Clo = np.minimum.reduce([C[0][q] for q in p]); Chi = np.maximum.reduce([C[1][q] for q in p]) coef = iscal(-1.0, ifloat(ihM((s[0][l], s[1][l]), M))) t = imul(ifloat(coef), (Clo, Chi)) Line[1][0][ii] = dn(Line[1][0][ii] + t[0]); Line[1][1][ii] = up(Line[1][1][ii] + t[1]) win.step() self.T0w, self.f1w, self.PhiD, self.Line = T0w, f1w, PhiD, Line # Conservative |Z_k| bounds: the upper accumulator now uses sigma = (ia + 1)/M, which contains W(alpha'). # The current positivity routing skips the crude-bound consumer of these arrays. Zabs = {} for k in (1, 2, 3): keys = {1: [], 2: [(1, 1)], 3: [(1, 2), (2, 1)]}[k] hi = np.zeros(M) for key in keys: g = win.G[key][1] * (1.0 + gam(win.nhi + 3)) hi = up(hi + np.maximum(g[:-1], g[1:])) if k in (1, 2): hi = up(hi + Kn.Rk[k][1]) # delta-term bound R_k(x) (window indicator dropped) Zabs[k] = (np.zeros(M), hi) self.Zabs = Zabs self.log(f"{self.tl()} pass C done: f(1) window part {fmt_iv(f1w)}, T0 window part {fmt_iv(T0w)}") # ---------------- jb = 0 off-diagonal by the kappa aggregate ---------------- def kappa_phi(self, omega, m_range): """Phi_k(a) (k = 1, 2) = int dtau int dsig omega(sig, tau) Z_k(a - tau; sig) = sum_br c_{k,br} (R_{k-br} * Xi_br)(a), with Xi_br(v) = int R_br(v - tau) kappa(tau, v - tau) dtau and kappa(tau, u) = int_{sig >= 1/2 - u} omega(sig, tau) dsig. omega(m) returns the interval of omega(sig, tau) for sig in the cells ls = [ie, ia) and tau in cell m (signed).""" M, ie, ia, ih = self.M, self.ie, self.ia, self.ih Kn = self.Kn; X = self.X Xi = {1: izeros(M), 2: izeros(M)} qs = np.arange(ih - ia, ih) n = ia - ie for m in m_range: om = ihM(omega(m), M) SL = np.concatenate([np.cumsum(om[0][::-1])[::-1], np.zeros(1)]); SH = np.concatenate([np.cumsum(om[1][::-1])[::-1], np.zeros(1)]) AL_ = np.concatenate([np.cumsum(np.abs(om[0])[::-1])[::-1], np.zeros(1)]); AH = np.concatenate([np.cumsum(np.abs(om[1])[::-1])[::-1], np.zeros(1)]) SL = dn(SL - gam(n + 2) * AL_); SH = up(SH + gam(n + 2) * AH) Lf = np.clip(ih - qs, ie, ia) - ie; Lp = ih - qs - 1 okp = (Lp >= ie) & (Lp < ia) pl = np.where(okp, om[0][np.clip(Lp - ie, 0, n - 1)], 0.0); ph = np.where(okp, om[1][np.clip(Lp - ie, 0, n - 1)], 0.0) klo = dn(SL[Lf] + np.minimum(pl, 0.0)); khi = up(SH[Lf] + np.maximum(ph, 0.0)) for br in (1, 2): R = Kn.Rk[br] Y = imul((R[0][qs], R[1][qs]), (klo, khi)) Ylo = np.concatenate([[0.0], Y[0], [0.0]]); Yhi = np.concatenate([[0.0], Y[1], [0.0]]) Uu = ihM((np.minimum(Ylo[:-1], Ylo[1:]), np.maximum(Yhi[:-1], Yhi[1:])), M) ps = slice(m + ih - ia, m + ih + 1) Xi[br][0][ps] = dn(Xi[br][0][ps] + Uu[0]); Xi[br][1][ps] = up(Xi[br][1][ps] + Uu[1]) Phi = {1: ineg(Xi[1])} cv = X.cells(*X.combo_grid([(1, Kn.Rk[1], Xi[1], 'ns')])) Phi[2] = isub(cv, Xi[2]) return {k: (Phi[k][0][ih:], Phi[k][1][ih:]) for k in (1, 2)} def phi_offdiag(self): ie, ia = self.ie, self.ia ls = np.arange(ie, ia) def omega(m): om = izeros(len(ls)) for J in (2, 3): if m >= J * ie: om = iadd(om, imul((self.Hx[J][0][m], self.Hx[J][1][m]), self.wJ(J, ls, np.full(len(ls), m)))) return om self.PhiO = self.kappa_phi(omega, range(2 * ie, ia)) # ---------------- f(1), T0, T0(g) ---------------- def f1_T0(self): M, ie, ia, ih = self.M, self.ie, self.ia, self.ih Kn = self.Kn; S = Kn.S last = M - 1 e00 = self.EC(0, 0, 0) f1 = iadd(((float(e00[0][last]), float(e00[1][last])) if e00 is not None else (0.0, 0.0)), self.f1w) T0 = (float(self.A[0][0][last]), float(self.A[0][1][last])) # free + j_y = 0 extended parts: sum_J int S_J(tau) B_J(1 - tau) H_J(tau) dtau (check) = -sum_J int S_J (A_J + I_J) (cert) for J in (1, 2, 3): mm = np.arange(J * ie, ia) if self.mode == "cert": IJ = {3: izeros(len(mm)), 2: isel(self.I23, mm), 1: iadd(isel(self.I12, mm), isel(self.I13, mm))}[J] X_ = ineg(iadd(isel(self.Ax[J], mm), IJ)) else: X_ = imul(isel(self.Bx[J], mm), isel(self.Hx[J], mm)) T0 = iadd(T0, isum(imul(ihM(isel(S[J], mm), M), X_))) T0 = ifloat(iadd(T0, self.T0w)) self.f1 = ifloat(f1); self.T0 = T0 if self.mode == "check": ok = T0[0] <= 0 <= T0[1] self.log(f"{self.tl()} CHECK T0 (untwisted, random data): {fmt_iv(T0, 6)} {'CONTAINS 0' if ok else 'EXCLUDES 0'}") self.check_T0 = ok return g = {(0, 3, 4): 1.0} A0g = self.Ac(0, c=g) T0g = (float(A0g[0][last]), float(A0g[1][last])) L = Kn.Lam[(0, 3, 4)] f1g = (float(L[0][last]), float(L[1][last])) self.T0g, self.f1g = T0g, f1g assert T0g[1] < 0 or T0g[0] > 0 tint = idiv(ineg(T0), T0g) self.tint = (float(tint[0]), float(tint[1])) self.log(f"{self.tl()} f(1) before the solve {fmt_iv(self.f1)}; T0(c) {fmt_iv(T0)}; T0(g) {fmt_iv(T0g)}; f1(g) {fmt_iv(f1g)}; " f"t* [{fmt_bound(self.tint[0], 6)}, {fmt_bound(self.tint[1], 6, True)}]") # ---------------- positivity ---------------- def positivity(self, t): M, ie, ia, ih = self.M, self.ie, self.ia, self.ih Kn = self.Kn res = {"min": (INF, None), "max": (-INF, None)} per = {} def upd(f, tag, pos=None): lo = np.atleast_1d(f[0]); hi = np.atleast_1d(f[1]) if lo.size == 0: return k = int(np.argmin(lo)); kk = int(np.argmax(hi)); kh = int(np.argmin(hi)) w = (tag, int(pos[k]) if pos is not None else k) if lo[k] < res["min"][0]: res["min"] = (float(lo[k]), w) if hi[kk] > res["max"][0]: res["max"] = (float(hi[kk]), (tag, int(pos[kk]) if pos is not None else kk)) if tag not in per: per[tag] = (float(lo[k]), w[1], float(hi[kh])) else: p0, p1, p2 = per[tag] per[tag] = (min(p0, float(lo[k])), w[1] if lo[k] < p0 else p1, min(p2, float(hi[kh]))) c = self.c # free classes for j in range(0, 21): for k in range(0, 5): for b in bins_of(k): if j + k < 2 or not realisable(j, k, b): continue v = c.get((j, k, b), 0.0) base = (v, v) if (j, k, b) == (0, 3, 4): base = iadd(base, (t, t)) if k == 3 and 1 <= j <= 3: lo_, hi_ = rough_range(3, b) ii = np.arange(j * ie, min(j * ia, M)) # tau in closed cell i realisable: (1 - tau) in (lo, hi) for some tau in the cell (conservative) ok = np.array([(1 - Fr(int(i) + 1, M) < hi_) and (1 - Fr(int(i), M) > lo_) for i in ii]) ii = ii[ok] Hv = iunion(isel(self.Hx[j], ii), izeros(len(ii))) if False else isel(self.Hx[j], ii) # H_j applies for tau <= alpha' (cells < ia); beyond, c alone f = iadd((np.full(len(ii), base[0]), np.full(len(ii), base[1])), Hv) upd(f, ("free", j, k, b), ii) else: upd(base, ("free", j, k, b)) # one-large vectors ac = np.arange(ih, M) A = (dn(ac / M), up((ac + 1) / M)) L0 = {k: isel(Kn.Lam0[k], ac) for k in (1, 2, 3)} Phi = {k: iadd(self.PhiD[k], self.PhiO[k]) for k in (1, 2)} gC = {(0, 3, 4): 1.0} Hsp = {J: SparseMinMax(self.Hx[J][0], self.Hx[J][1]) for J in (1, 2, 3)} Cj = {1: Kn.s, 2: iscal(3.0, Kn.S[2]), 3: iscal(7.0, Kn.S[3])} crude = {} for jb in range(0, 10): for kb in range(0, 3): for bb in bins_of(kb): if jb + kb == 0: continue e = self.EC(jb, kb, bb) cp = isel(e, ac) if e is not None else izeros(len(ac)) if kb >= 1 and jb == 0: eg = self.EC(0, kb, bb, c=gC) if eg is not None: cp = iadd(cp, iscal(t, isel(eg, ac))) tag = ("ext", jb, kb, bb) ky = 3 - kb # realisable a-cells and tau_b-cells if kb == 0: if jb == 0: continue ib = np.arange(jb * ie, min(jb * ia, M)) aidx = M - 1 - ib ok = aidx >= ih ib, aidx = ib[ok], aidx[ok] ai = aidx - ih inner = isel(cp, ai) if 1 <= jb <= 3: inb = ib < ia Hv = (np.where(inb, self.Hx[jb][0][np.minimum(ib, M - 1)], 0.0), np.where(inb, self.Hx[jb][1][np.minimum(ib, M - 1)], 0.0)) inner = iadd(inner, imul(Hv, isel(L0[3], ai))) if jb <= 2: ln = (np.where(ib < ia, self.Line[jb][0][np.minimum(ib, ia - 1)], 0.0), np.where(ib < ia, self.Line[jb][1][np.minimum(ib, ia - 1)], 0.0)) inner = iadd(inner, ln) f = imul(isel(A, ai), inner) upd(f, tag, aidx) continue if jb in (1, 2) and kb in (1, 2): continue # handled at a coarse resolution by far_strata() rlo, rhi = rough_range(kb, bb) # tau_b range for a-cell j: tau_b in (rest - rhi, rest - rlo) intersected with [jb eta, jb alpha'] (cells) jj = ac tb_lo = np.array([max(jb * ie, int(np.floor((1 - Fr(int(x) + 1, M) - rhi) * M))) for x in jj]) tb_hi = np.array([min(max(jb * ia - 1, jb * ie), int(np.ceil((1 - Fr(int(x), M) - rlo) * M))) for x in jj]) okc = tb_lo <= tb_hi if jb == 0: okc = np.array([(1 - Fr(int(x) + 1, M) < rhi) and (1 - Fr(int(x), M) > rlo) for x in jj]) if not okc.any(): continue jj = jj[okc]; ai = jj - ih inner = isel(cp, ai) if jb == 0: inner = iadd(inner, isel(Phi[ky], ai)) elif jb <= 3: lo_i, hi_i = tb_lo[okc], tb_hi[okc] hlo, hhi = Hsp[jb].query(np.minimum(lo_i, M - 1), np.minimum(hi_i, M - 1)) if kb <= 1: inner = iadd(inner, imul((hlo, hhi), isel(L0[ky], ai))) if jb <= 2: key = (jb, ky) if key not in crude: acc = izeros(M) for J in range(jb + 1, 4): j = J - jb Hm = float(np.max(np.abs(np.concatenate([self.Hx[J][0], self.Hx[J][1]])))) cv = self.X.cells(*self.X.nn_grid(Cj[j], self.Zabs[ky])) acc = iadd(acc, iscal(up(Hm), cv)) crude[key] = acc cb = isel(crude[key], jj) inner = iadd(inner, (-cb[1], cb[1])) f = imul(isel(A, ai), inner) upd(f, tag, jj) return res, per def run(self): self.setup() self.solve() if self.mode == "check": self.pass_C_check() return self.pass_C() self.phi_offdiag() self.f1_T0() far_best, far_per = far_strata(self, self.Mc, self.Qc, log=self.log) out = [] for t in self.tint: f1t = ifloat(iadd(self.f1, iscal(t, self.f1g))) res, per = self.positivity(t) if far_best[0] < res["min"][0]: res["min"] = (far_best[0], ("far",) + tuple(far_best[1])) mn = res["min"][0] m = float(dn(1.0 - float(up(mn / f1t[1])))) if f1t[1] < 0 else -INF out.append((t, f1t, res, m, per)) self.log(f"{self.tl()} endpoint t = {t!r}: f(1) within {fmt_iv(f1t)}; min f >= {fmt_bound(mn)} at {res['min'][1]}; " f"max f <= {fmt_bound(res['max'][0], 5, True)}; scaled margin m >= {fmt_bound(m)}") for tag in sorted(per, key=lambda k: per[k][0])[:12]: self.log(f" {str(tag):20s} stratum min within [{fmt_bound(per[tag][0])}, {fmt_bound(per[tag][2], 5, True)}] (lower end at {per[tag][1]})") self.margin = min(o[3] for o in out) self.log(f"{self.tl()} RESULT M = {self.M}: scaled margin on the segment >= {fmt_bound(self.margin)} (exact {self.margin!r}); " f"{'PASS' if self.margin > 0 else 'NO PASS'} at this M ({self.X.nconv} exact products)") def pass_C_check(self): """untwisted T0 check (all Ytilde terms vanish; f(1) not needed).""" self.T0w = (0.0, 0.0); self.f1w = (0.0, 0.0) self.f1_T0() def far_strata(F, Mc, Qc, log=print): """the one-large strata (jb in {1,2}, kb in {1,2}) at a coarse resolution Mc (F.M % Mc == 0): kernels at Mc, H from the fine certificate by unions over the r = F.M/Mc fine cells of each coarse cell (valid enclosures), tau_b in Qc groups. Returns the minimum lower bound and the per-stratum minima. These strata carry no g-term, so the result holds at every t.""" assert F.M % Mc == 0 and Mc % 60 == 0 r = F.M // Mc C = Cert5(Mc, F.c, mode="cert", Q=1, log=lambda *a: None) C.setup() ie, ia, ih = C.ie, C.ia, C.ih Hx = {J: (F.Hx[J][0].reshape(Mc, r).min(axis=1), F.Hx[J][1].reshape(Mc, r).max(axis=1)) for J in (1, 2, 3)} C.Hx = Hx sp = {J: SparseMinMax(*Hx[J]) for J in (1, 2, 3)} Kn = C.Kn; S = Kn.S aend = Mc - ie - ia + 1 na = aend - ih groups = {} for jb in (1, 2): lo_c, hi_c = jb * ie, ia edges = np.linspace(lo_c, hi_c, Qc + 1).round().astype(int) groups[jb] = [(int(edges[q]), int(edges[q + 1])) for q in range(Qc) if edges[q + 1] > edges[q]] Psi = {(jb, k, q): izeros(na) for jb in (1, 2) for k in (1, 2) for q in range(len(groups[jb]))} def Hr(J, g0, g1, l): hl, hh = sp[J].query(np.array([g0 + l]), np.array([min(g1 + l, Mc - 1)])) return (float(hl[0]), float(hh[0])) win = C.Win(C) aa = np.arange(ih, aend) for l in range(0, ia): if l >= ie: pts = C._pts(ih, aend, l); cells = (aa - l - 1, aa - l) Z = {k: C.Zk(win, k, pts, cells, l) for k in (1, 2)} for jb in (1, 2): for J in range(jb + 1, 4): j = J - jb if l < j * ie: continue for q, (g0, g1) in enumerate(groups[jb]): coef = ifloat(ihM(imul(Hr(J, g0, g1, l), (S[j][0][l], S[j][1][l])), Mc)) for k in (1, 2): Psi[(jb, k, q)] = iadd(Psi[(jb, k, q)], imul(coef, Z[k])) win.step() ls = np.arange(ie, ia) for q, (g0, g1) in enumerate(groups[1]): def omega(m, g0=g0, g1=g1): return imul(Hr(3, g0, g1, m), C.wJ(2, ls, np.full(len(ls), m))) P = C.kappa_phi(omega, range(2 * ie, ia)) for k in (1, 2): Psi[(1, k, q)] = iadd(Psi[(1, k, q)], (P[k][0][:na], P[k][1][:na])) A = (dn(aa / Mc), up((aa + 1) / Mc)) L0 = {k: isel(Kn.Lam0[k], aa) for k in (1, 2)} best = (INF, None); per = {} for jb in (1, 2): for kb in (1, 2): ky = 3 - kb for bb in (1, 2, 3, 4): e = C.EC(jb, kb, bb) cp = isel(e, aa) if e is not None else izeros(na) rlo, rhi = rough_range(kb, bb) tag = ("ext", jb, kb, bb) spans = [(g0, g1, q) for q, (g0, g1) in enumerate(groups[jb])] + [(ia, jb * ia, None)] for g0, g1, q in spans: if g1 <= g0: continue # realisable: some tau_b in [g0, g1]/Mc and rest in a-cell with rest - tau_b in (rlo, rhi) ok = np.array([(Fr(g0, Mc) < 1 - Fr(int(x), Mc) - rlo) and (Fr(g1, Mc) > 1 - Fr(int(x) + 1, Mc) - rhi) for x in aa]) if not ok.any(): continue inner = cp if q is not None: hl, hh = sp[jb].query(np.array([g0]), np.array([g1 - 1])) if kb <= 1: inner = iadd(inner, imul((float(hl[0]), float(hh[0])), L0[ky])) inner = iadd(inner, Psi[(jb, ky, q)]) f = imul(A, inner) lo = f[0][ok] k_ = int(np.argmin(lo)) v = float(lo[k_]) if v < best[0]: best = (v, (tag, int(aa[ok][k_]) * r)) if tag not in per or v < per[tag]: per[tag] = v log(f"far strata (jb in {{1,2}}, kb in {{1,2}}) at Mc = {Mc}, Qc = {Qc}: min >= {fmt_bound(best[0])} at {best[1]}; " + "; ".join(f"{k[1:]}: {fmt_bound(v)}" for k, v in sorted(per.items(), key=lambda kv: kv[1])[:4])) return best, per def main(): M = int(sys.argv[1]) if len(sys.argv) > 1 else 600 mode = sys.argv[2] if len(sys.argv) > 2 else "cert" Q = int(sys.argv[3]) if len(sys.argv) > 3 else 1 if mode == "cert": c = load_c() else: rng = np.random.default_rng(12345) c = {(j, k, b): float(rng.normal()) for j in range(0, 8) for k in range(0, 5) for b in bins_of(k) if j + k >= 2} C = Cert5(M, c, mode=mode, Q=Q) C.Mc = int(sys.argv[4]) if len(sys.argv) > 4 else M C.Qc = int(sys.argv[5]) if len(sys.argv) > 5 else 16 C.run() if __name__ == "__main__": main()