"""p4rig3.py: a separately written enclosure of the (1/18, 1/6) function, written blind from the mathematical text. Arithmetic: validated binary64 interval operations with outward nextafter. Raw incremental-window updates and nonnegative kappa suffix sums use nearest rounding followed by aggregate error bounds. Signed functional sums use an absolute-sum correction. Every polynomial product is exact integer arithmetic on outward integer images (vconv.py, python-flint fmpz_poly); no floating-point transform is used. Known nonnegative convolution lowers are clipped at zero. Printed enclosure endpoints are rounded outward by fmt_bound. Exact identities used: - K(t; s') := sum_kw sg(2+kw) (R_kw * Lambda1(.; s') tr)(t) = -(1/s') (U * rho 1_W(s'))(t - s'), with U = (sum_kw sg(2+kw) R_kw) * Q: U = sum_n (-2)^n R_n when twisted and U = delta when untwisted, since R_a * R_b = C(a+b, a) R_{a+b}; computed by incremental windows. - Phi1 = int H1 Lambda1 and Phi2a = int H2 S2 Z(. - tau; tau) dtau by incremental windows; Phi2b = int ds' s(s') int dtau H2(tau) s(tau - s') Z(a - tau; s') = -(Q * Xi)(a) with ONE exact convolution, where Xi(v) = int H2(tau) rho(v - tau) kappa(tau, v - tau) dtau and kappa(tau, u) = int_{s' >= 1/2 - u} s(s') s(tau - s') ds' (u < 1/2), since Z(.; s') = -(Q * rho 1_W(s')). Usage: p4rig3.py M [cert|check] [Q] (reads constants_frozen.tsv from the working directory) """ import sys import time from fractions import Fraction as Fr import numpy as np from vconv import Exact, dn, up U = 2.0 ** -53 INF = np.inf def gam(n): return 1.01 * n * U / (1.0 - n * U) # ---------------- interval helpers (an interval is a pair (lo, hi) of floats or arrays) ---------------- 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): """exact float c times interval 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): """the exact real c / M for an interval c (scalars or arrays), outward.""" Mf = float(M) return (dn(np.asarray(c[0], float) / Mf), up(np.asarray(c[1], float) / Mf)) # ---------------- outward decimal read-outs (audit fix 2) ---------------- def fmt_bound(x, places=5, upper=False): """Decimal endpoint rounded outward from the exact binary64 value.""" 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)}]" # ---------------- data ---------------- def strict_classes(): eta, al = Fr(1, 18), Fr(1, 6) out = set() for j in range(0, 19): for k in range(0, 7): if j + k >= 2 and j * eta + k * al < 1 < j * al + k * Fr(1, 2): out.add((j, k)) return out def load_c(path="constants_frozen.tsv"): c = {} for line in open(path): if line.startswith("#"): continue cls, _v, hx = line.rstrip("\n").split("\t") j, k, _b = eval(cls) c[(j, k)] = float.fromhex(hx) real = strict_classes() return {jk: v for jk, v in c.items() if jk in real and v != 0.0} # ---------------- kernels (exact convolutions) ---------------- class Kernels3: def __init__(self, M, X, jmax=6, kmax=5): assert M % 36 == 0 self.M = M; self.X = X ie, ia, ih = M // 18, M // 6, M // 2 self.ie, self.ia, self.ih = ie, ia, ih 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)) sm = (i >= ie) & (i < ia); rg = (i >= ia) & (i < ih) self.s = (np.where(sm, inv_lo, 0.0), np.where(sm, inv_hi, 0.0)) self.r = (np.where(rg, inv_lo, 0.0), np.where(rg, inv_hi, 0.0)) self.S = [None, self.s] for j in range(2, jmax + 1): lo, hi = X.nn(self.S[-1], self.s) self.S.append((np.maximum(dn(lo / j), 0.0), up(hi / j))) self.R = [None, self.r] for k in range(2, kmax + 1): lo, hi = X.nn(self.R[-1], self.r) self.R.append((np.maximum(dn(lo / k), 0.0), up(hi / k))) self.D = {} for j in range(jmax + 1): for k in range(kmax + 1): if j + k == 0: continue if k == 0: self.D[(j, 0)] = self.S[j] elif j == 0: self.D[(0, k)] = self.R[k] else: self.D[(j, k)] = X.nn(self.S[j], self.R[k]) half = (np.arange(M) >= ih).astype(float) self.half = half # Lemma K kernels (ambiguity A1 reading, confirmed by the audit): Lam_y = [-D_y + (-1)^{k+1} sum_B (-1)^{|B|} (D_B 1_{>=1/2} * D_{y-B})] 1_{>=1/2} self.Lam = {} for jy in range(jmax + 1): for ky in range(kmax + 1): if jy + ky < 2: continue if not np.any(self.D[(jy, ky)][1] * half): continue k = jy + ky items = [] for bs in range(jy + 1): for br in range(ky + 1): if (bs, br) in ((0, 0), (jy, ky)): continue DB = self.D[(bs, br)] if not np.any(DB[1] * half): continue sgn = (-1) ** (k + 1) * (-1) ** (bs + br) items.append((sgn, (DB[0] * half, DB[1] * half), self.D[(jy - bs, ky - br)], 'nn')) if items: clo, chi = X.cells(*X.combo_grid(items)) else: clo, chi = np.zeros(M), np.zeros(M) lo = dn(clo - self.D[(jy, ky)][1]); hi = up(chi - self.D[(jy, ky)][0]) self.Lam[(jy, ky)] = (lo * half, hi * half) lo = np.zeros(M); hi = np.zeros(M) for ky in range(2, kmax + 1): if (0, ky) in self.Lam: lo = dn(lo + self.Lam[(0, ky)][0]); hi = up(hi + self.Lam[(0, ky)][1]) self.Lam0 = (lo, hi) # ---------------- the certificate ---------------- class Cert3: def __init__(self, M, c, mode="cert", Q=4, seed=1, log=print): self.M = M; self.mode = mode; self.log = log; self.Q = Q self.h = 1.0 / M self.ie, self.ia, self.ih = M // 18, M // 6, M // 2 assert self.ie % Q == 0, "Q must divide M/18" self.t0 = time.monotonic() self.X = Exact(M) self.Kn = Kernels3(M, self.X, jmax=6, kmax=5) log(f"{self.tl()} kernels built (M = {M}; {len(self.Kn.Lam)} Lambda_y; {self.X.nconv} exact integer products so far)") 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_): key = (J, K_) if key not in self._ec: acc = None for (jy, ky), L in self.Kn.Lam.items(): v = self.c.get((J + jy, K_ + ky), 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, base): """A1 c (base 1) or A2 c (base 2) as a function of t (cells); the extended completions combined exactly at grid level.""" Kn = self.Kn; X = self.X; sg = self.sg acc = None for jp in range(0, 7): for kp in range(0, 6): if jp + kp == 0: continue v = self.c.get((base + jp, kp), 0.0) if v: acc = self._add(acc, iscal(sg(base + jp + kp) * v, Kn.D[(jp, kp)])) items = [] for jw in range(0, 7): for kw in range(0, 6): e = self.EC(base + jw, kw) if e is None: continue if jw + kw == 0: acc = self._add(acc, iscal(sg(base + 1), e)) else: items.append((sg(base + 1 + jw + kw), Kn.D[(jw, kw)], 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_rows(self): Kn = self.Kn; X = self.X; sg = self.sg R = Kn.R; L0 = Kn.Lam0 self.RL0 = {0: L0} for kw in range(1, 6): self.RL0[kw] = X.signed(R[kw], L0) acc = None for k in range(1, 6): acc = self._add(acc, iscal(sg(2 + k), R[k])) for kw in range(0, 6): acc = self._add(acc, iscal(sg(3 + kw), self.RL0[kw])) self.B2f = acc acc = None for k in range(1, 6): acc = self._add(acc, iscal(sg(1 + k), R[k])) for kw in range(0, 6): acc = self._add(acc, iscal(sg(2 + kw), self.RL0[kw])) self.B1f = acc self.A2f = self.Ac(2) self.A1f = self.Ac(1) acc = None for k in range(1, 6): acc = self._add(acc, iscal(sg(1 + k), R[k])) self.Rs1 = acc # = Dsum0 acc = None for k in range(1, 6): acc = self._add(acc, iscal(sg(2 + k), R[k])) self.Rs2 = acc acc = None for kb in range(0, 6): acc = self._add(acc, iscal(sg(2 + kb), self.RL0[kb])) self.KH1 = acc acc = None for kb in range(0, 6): acc = self._add(acc, iscal(sg(3 + kb), self.RL0[kb])) self.K0s = acc # window kernels: rho = R1 + R2 on the window [1/3, 1/2); Q = delta + Q+ - Q-, Q+ = R2 + R4, Q- = R1 + R3 + R5 self.rho = iadd(R[1], R[2]); self.Qp = iadd(R[2], R[4]); self.Qm = iadd(iadd(R[1], R[3]), R[5]) # U = (sum_kw sg(2+kw) R_kw) * Q: twisted sum_n (-2)^n R_n (U+ = 4R2 + 16R4, U- = 2R1 + 8R3 + 32R5, plus delta); untwisted delta if self.mode == "cert": self.Up = iadd(iscal(4.0, R[2]), iscal(16.0, R[4])) self.Um = iadd(iadd(iscal(2.0, R[1]), iscal(8.0, R[3])), iscal(32.0, R[5])) else: self.Up = izeros(self.M); self.Um = izeros(self.M) self.log(f"{self.tl()} rows set up (B2, B1, A2c, A1c, RL0, window kernels; {self.X.nconv} exact products)") # ---------------- H2 ---------------- def solve_H2(self): M, ie, ia = self.M, self.ie, self.ia ms = np.arange(2 * ie, ia); tc = M - 1 - ms A2 = isel(self.A2f, tc); B2 = isel(self.B2f, tc) self.B2range = (float(B2[0].min()), float(B2[1].max())) if self.mode == "cert": assert np.all(B2[1] < 0), "B2 not negative" H2 = idiv(ineg(A2), B2) else: v = self.rng.normal(size=len(ms)); H2 = (v.copy(), v.copy()) T2 = iadd(A2, imul(B2, H2)) ok = (T2[0] <= 0) & (T2[1] >= 0) hw = (T2[1] - T2[0]) / 2; mid = (T2[1] + T2[0]) / 2 self.log(f"{self.tl()} CHECK T2 (untwisted, random data): 0 in {int(ok.sum())}/{len(ok)} sigma-cells; max |mid| {np.abs(mid).max():.3e}, " f"max half-width {hw.max():.3e}") self.check_T2 = (int(ok.sum()), len(ok)) self.H2 = H2 self.H2x = izeros(M); self.H2x[0][2 * ie:ia] = H2[0]; self.H2x[1][2 * ie:ia] = H2[1] self.A2x = izeros(M); self.A2x[0][2 * ie:ia] = A2[0]; self.A2x[1][2 * ie:ia] = A2[1] self.B2x = izeros(M); self.B2x[0][2 * ie:ia] = B2[0]; self.B2x[1][2 * ie:ia] = B2[1] self.log(f"{self.tl()} H2 on [2eta, alpha'): within {fmt_iv((H2[0].min(), H2[1].max()))}; B2 within {fmt_iv(self.B2range)}") # ---------------- windows: W_n = [1/2 - n h, 1/2) ---------------- class Win: """Grid sums for Q+/- * (rho 1_W), with lower window W_nlo and upper window W_nhi. In cert mode, while useU is true, U+/- streams stop at lower W_(2*ie) and upper W_(2*ie+1). They are consumed only for ie <= l < 2*ie. Setting useU=False disables further U updates; the stored U arrays then make no claim about the current window. _two supplies the aggregate arithmetic widening. """ def __init__(self, C): self.C = C; M = C.M z = lambda: np.zeros(M + 1) self.Plo = [z(), z()]; self.Phi = [z(), z()] # [Q+, Q-] self.Ulo = [z(), z()]; self.Uhi = [z(), z()] # [U+, U-] self.useU = C.mode == "cert" self.nlo = 0; self.nhi = 0 self.add_hi() def _add(self, i, bound, arrs, kers): C = self.C; M = C.M hr = C.rho[bound][i] / float(M) # one rounding (covered by the gamma(n+3) widening) if hr: for G, Kk in zip(arrs, kers): G[i + 1:] += hr * Kk[bound][:M - i] def add_lo(self): C = self.C; i = C.ih - self.nlo - 1 self._add(i, 0, self.Plo, (C.Qp, C.Qm)) if self.useU and self.nlo < 2 * C.ie: self._add(i, 0, self.Ulo, (C.Up, C.Um)) self.nlo += 1 def add_hi(self): C = self.C; i = C.ih - self.nhi - 1 self._add(i, 1, self.Phi, (C.Qp, C.Qm)) if self.useU and self.nhi < 2 * C.ie + 1: self._add(i, 1, self.Uhi, (C.Up, C.Um)) self.nhi += 1 def step(self): self.add_lo(); self.add_hi() def _two(self, win, l, j0, j1, Glo, Ghi, with_delta): """X(t') = [delta] + G+ - G- at the shifted points t' = t - s' for t in the closed cells [j0, j1) and almost every s' in cell l: t' ranges over the two cells j-l-1, j-l (three grid points); window between W_l and W_{l+1}.""" assert win.nlo == l and win.nhi == l + 1 assert self.ih <= j0 <= j1 <= self.M assert 0 <= l < self.ia if Glo is win.Ulo or Ghi is win.Uhi: assert Glo is win.Ulo and Ghi is win.Uhi assert win.useU and self.mode == "cert" and self.ie <= l < 2 * self.ie wl = 1.0 - gam(win.nlo + 3); wh = 1.0 + gam(win.nhi + 3) s0, s1, s2 = slice(j0 - l - 1, j1 - l - 1), slice(j0 - l, j1 - l), slice(j0 - l + 1, j1 - l + 1) def tmin(Gr): return np.minimum(np.minimum(Gr[s0], Gr[s1]), Gr[s2]) def tmax(Gr): return np.maximum(np.maximum(Gr[s0], Gr[s1]), Gr[s2]) Pp_lo = dn(tmin(Glo[0]) * wl); Pm_lo = dn(tmin(Glo[1]) * wl) Pp_hi = up(tmax(Ghi[0]) * wh); Pm_hi = up(tmax(Ghi[1]) * wh) if with_delta: rl, rh = self.rho r_lo = np.minimum(rl[s0], rl[s1]); r_hi = np.maximum(rh[s0], rh[s1]) jj = np.arange(j0, j1) - self.ih d_lo = np.where(jj <= l - 1, r_lo, 0.0); d_hi = np.where(jj <= l, r_hi, 0.0) else: d_lo = 0.0; d_hi = 0.0 return (dn(dn(d_lo + Pp_lo) - Pm_hi), up(up(d_hi + Pp_hi) - Pm_lo)) def invs(self, l): return (float(dn(self.M / (l + 1.0))), float(up(self.M / float(l)))) # ---------------- pass 1 (s'-cells of [eta, 2 eta)) ---------------- def pass1(self): M, ie, ia, ih, h, Q = self.M, self.ie, self.ia, self.ih, self.h, self.Q win = self.Win(self) WK = izeros(ie); Line = izeros(ie) aPsi = M - ie - ia + 1 nPsi = aPsi - ih gs = ie // Q Psi = (np.zeros((Q, nPsi)), np.zeros((Q, nPsi))) tK0, tK1 = M - 2 * ie, M - ie assert tK0 - 2 * ie - 1 >= ih # t - s' > 1/2 there, so U's delta part vanishes on the K range H2x = self.H2x S2 = self.Kn.S[2] Phi2a = izeros(M - ih) sl_i = np.arange(ie, 2 * ie) tstart = time.monotonic() for l in range(0, ia): if 2 * ie <= l < ia: # Phi2a(a) = int H2(tau) S2(tau) Z(a - tau; tau) dtau, Z = -X (window tau, shift tau), tau-cell l X = self._two(win, l, ih, M, win.Plo, win.Phi, True) coef = imul(ihM((self.H2[0][l - 2 * ie], self.H2[1][l - 2 * ie]), M), (S2[0][l], S2[1][l])) Phi2a = iadd(Phi2a, imul(ifloat(coef), ineg(X))) if ie <= l < 2 * ie: X = self._two(win, l, ih, M, win.Plo, win.Phi, True) L1 = imul(ineg(X), self.invs(l)) # Lambda1(a; s'), a-cells [ih, M) if self.mode == "cert": XU = self._two(win, l, tK0, tK1, win.Ulo, win.Uhi, False) Kc = imul(ineg(XU), self.invs(l)) # K(t; s'), t-cells [tK0, tK1) else: Kc = izeros(tK1 - tK0) # untwisted: U = delta, which vanishes on this range Krev = (Kc[0][::-1], Kc[1][::-1]) # aligned with s-cells i = ie .. 2ie-1 (t-cell M-1-i) idx = sl_i + l H2u = iunion(isel(H2x, idx), isel(H2x, idx + 1)) hH2u = ihM(H2u, M) WK = iadd(WK, imul(hH2u, Krev)) L1line = (L1[0][M - 1 - sl_i - ih], L1[1][M - 1 - sl_i - ih]) Line = iadd(Line, imul(hH2u, L1line)) base = ie + l blk_lo = H2x[0][base:base + Q * gs].reshape(Q, gs).min(axis=1) blk_hi = H2x[1][base:base + Q * gs].reshape(Q, gs).max(axis=1) nxt = base + (np.arange(Q) + 1) * gs blk_lo = np.minimum(blk_lo, H2x[0][nxt]); blk_hi = np.maximum(blk_hi, H2x[1][nxt]) hb = ihM((blk_lo[:, None], blk_hi[:, None]), M) Psi = iadd(Psi, imul(hb, (L1[0][None, :nPsi], L1[1][None, :nPsi]))) win.step() self.WK, self.Line, self.Psi, self.gs, self.aPsi = WK, Line, Psi, gs, aPsi self.Phi2a = Phi2a self.log(f"{self.tl()} pass 1 (windows) done in {time.monotonic() - tstart:.1f}s; WK max width {np.max(WK[1] - WK[0]):.3e}") # ---------------- pass 2: Phi1 by incremental window convolutions; no new polynomial product ---------------- def pass2(self): M, ie, ia, ih = self.M, self.ie, self.ia, self.ih win = self.Win(self) win.useU = False Phi1 = izeros(M - ih) tstart = time.monotonic() for l in range(0, ia): if l >= ie: X = self._two(win, l, ih, M, win.Plo, win.Phi, True) L1 = imul(ineg(X), self.invs(l)) hH = ihM((self.H1[0][l - ie], self.H1[1][l - ie]), M) Phi1 = iadd(Phi1, imul(ifloat(hH), L1)) win.step() self.Phi1 = Phi1 self.log(f"{self.tl()} pass 2 (Phi1 by windows) done in {time.monotonic() - tstart:.1f}s; Phi1(1) within {fmt_iv((Phi1[0][-1], Phi1[1][-1]))}") # ---------------- H1 ---------------- def solve_H1(self): M, ie, ia, ih, h = self.M, self.ie, self.ia, self.ih, self.h s_lo, s_hi = self.Kn.s sl_i = np.arange(ie, 2 * ie) WIf = izeros(ie) for l in range(ie, 2 * ie): idx = sl_i + l hs = (float(dn(s_lo[l] / float(M))), float(up(s_hi[l] / float(M)))) if self.mode == "cert": A2u = iunion(isel(self.A2x, idx), isel(self.A2x, idx + 1)) WIf = iadd(WIf, imul(hs, ineg(A2u))) # s(s') B2(1-sigma) H2(sigma) = -s(s') A2c(1-sigma) exactly else: B2u = iunion(isel(self.B2x, idx), isel(self.B2x, idx + 1)) H2u = iunion(isel(self.H2x, idx), isel(self.H2x, idx + 1)) WIf = iadd(WIf, imul(hs, imul(B2u, H2u))) WI = iadd(WIf, self.WK) si = np.arange(ie, ia); tc = M - 1 - si A1 = isel(self.A1f, tc); B1 = isel(self.B1f, tc) WIall = izeros(ia - ie); WIall[0][:ie] = WI[0]; WIall[1][:ie] = WI[1] self.B1range = (float(B1[0].min()), float(B1[1].max())) if self.mode == "cert": assert np.all(B1[0] > 0), "B1 not positive" H1 = idiv(ineg(iadd(A1, WIall)), B1) else: v = self.rng.normal(size=ia - ie); H1 = (v.copy(), v.copy()) T1 = iadd(iadd(A1, imul(B1, H1)), WIall) ok = (T1[0] <= 0) & (T1[1] >= 0) hw = (T1[1] - T1[0]) / 2; mid = (T1[1] + T1[0]) / 2 self.log(f"{self.tl()} CHECK T1 (untwisted, random data): 0 in {int(ok.sum())}/{len(ok)} s-cells; max |mid| {np.abs(mid).max():.3e}, " f"max half-width {hw.max():.3e}") self.check_T1 = (int(ok.sum()), len(ok)) self.H1 = H1 self.log(f"{self.tl()} H1 on [eta, alpha'): within {fmt_iv((H1[0].min(), H1[1].max()))}; B1 within {fmt_iv(self.B1range)}") # ---------------- Phi1, Phi2 by the Xi aggregates ---------------- def _xi_kappa(self): """Xi(v) = int H2(tau) rho(v - tau) kappa(tau, v - tau) dtau on v-cells (full-length arrays).""" M, ie, ia, ih, h = self.M, self.ie, self.ia, self.ih, self.h s_lo, s_hi = self.Kn.s rl, rh = self.rho lo = np.zeros(M); hi = np.zeros(M) qs = np.arange(ih - ia, ih) # u-cells of [1/3, 1/2) ls = np.arange(ie, ia) # s'-cells sp_lo = np.concatenate([np.zeros(1), s_lo]); sp_hi = np.concatenate([np.zeros(1), s_hi]) # index + 1 (so -1 -> 0) for m in range(2 * ie, ia): # s(tau - s') for tau in cell m, s' in cell l: cells m-l-1, m-l (zero outside the support) a = m - ls - 1; b = m - ls ok_a = a >= 0; ok_b = b >= 0 sa_lo = np.where(ok_a, s_lo[np.clip(a, 0, M - 1)], 0.0); sb_lo = np.where(ok_b, s_lo[np.clip(b, 0, M - 1)], 0.0) sa_hi = np.where(ok_a, s_hi[np.clip(a, 0, M - 1)], 0.0); sb_hi = np.where(ok_b, s_hi[np.clip(b, 0, M - 1)], 0.0) lp = s_lo[ls] * np.minimum(sa_lo, sb_lo) hp = s_hi[ls] * np.maximum(sa_hi, sb_hi) n = len(ls) # suffix sums SL[L'] = sum_{l >= ls[0] + L'} lp, SU likewise (nonnegative; relative gamma widening) SL = np.concatenate([np.cumsum(lp[::-1])[::-1], np.zeros(1)]) SU = np.concatenate([np.cumsum(hp[::-1])[::-1], np.zeros(1)]) SL = np.maximum(dn(dn(SL * (1.0 - gam(n + 3))) / float(M)), 0.0) SU = up(up(SU * (1.0 + gam(n + 3))) / float(M)) # kappa(tau, u), u in cell q: lower from cells l >= ih - q, upper from cells l >= ih - q - 1 (clipped to [ie, ia]) Llo = np.clip(ih - qs, ie, ia) - ie; Lhi = np.clip(ih - qs - 1, ie, ia) - ie k_lo = SL[Llo]; k_hi = SU[Lhi] Y_lo = dn(rl[qs] * k_lo); Y_hi = up(rh[qs] * k_hi) # v-cells p: u in cells p-m-1, p-m -> q' = p - m in [ih - ia, ih] Ylo_ext = np.concatenate([np.zeros(1), Y_lo, np.zeros(1)]); Yhi_ext = np.concatenate([np.zeros(1), Y_hi, np.zeros(1)]) U_lo = np.minimum(Ylo_ext[:-1], Ylo_ext[1:]); U_hi = np.maximum(Yhi_ext[:-1], Yhi_ext[1:]) # q' = ih-ia .. ih hH = ihM((self.H2[0][m - 2 * ie], self.H2[1][m - 2 * ie]), M) pr = imul(ifloat(hH), (U_lo, U_hi)) ps = slice(m + ih - ia, m + ih + 1) lo[ps] = dn(lo[ps] + pr[0]); hi[ps] = up(hi[ps] + pr[1]) return lo, hi def phis(self): """Phi2b = int ds' s(s') int dtau H2(tau) s(tau - s') Z(a - tau; s') = -(Q * Xi)(a), Xi from _xi_kappa; Phi2 = Phi2a - Phi2b.""" ih = self.ih X = self.X t = time.monotonic() Xik = self._xi_kappa() cv = X.cells(*X.combo_grid([(1, self.Qp, Xik, 'ns'), (-1, self.Qm, Xik, 'ns')])) QXi = iadd(Xik, cv) # (Q * Xi)(a), Q = delta + Q+ - Q- self.Phi2b = (-QXi[1][ih:], -QXi[0][ih:]) self.Phi2 = isub(self.Phi2a, self.Phi2b) self.Phi = iadd(self.Phi1, self.Phi2) self.log(f"{self.tl()} Phi2b by the kappa aggregate ({time.monotonic() - t:.1f}s); Phi2(1) within {fmt_iv((self.Phi2[0][-1], self.Phi2[1][-1]))}; " f"widths at a=1: Phi2a {self.Phi2a[1][-1] - self.Phi2a[0][-1]:.3e}, Phi2b {self.Phi2b[1][-1] - self.Phi2b[0][-1]:.3e}") # ---------------- f(1), T0, T0(g) ---------------- def f1_T0(self): M, ie, ia, ih, h = self.M, self.ie, self.ia, self.ih, self.h Kn = self.Kn; sg = self.sg; D = Kn.D last = M - 1 e00 = self.EC(0, 0) f1 = (0.0, 0.0) if e00 is None else (float(e00[0][last]), float(e00[1][last])) f1 = ifloat(iadd(f1, (self.Phi[0][-1], self.Phi[1][-1]))) T0 = (0.0, 0.0) for (j, k), v in self.c.items(): if j + k >= 1 and (j, k) in D: T0 = iadd(T0, iscal(sg(j + k) * v, (D[(j, k)][0][last], D[(j, k)][1][last]))) si = np.arange(ie, ia); tc = M - 1 - si T0 = iadd(T0, isum(imul(ihM(self.H1, M), imul(isel(Kn.s, si), isel(self.Rs1, tc))))) mi = np.arange(2 * ie, ia); tm = M - 1 - mi T0 = iadd(T0, isum(imul(ihM(self.H2, M), imul(isel(Kn.S[2], mi), isel(self.Rs2, tm))))) ac = np.arange(ih, M); rc = M - 1 - ac for jb in range(0, 7): for kb in range(0, 6): if jb + kb == 0: continue e = self.EC(jb, kb) if e is None: continue v = isum(imul(ihM(isel(D[(jb, kb)], rc), M), isel(e, ac))) T0 = iadd(T0, iscal(sg(1 + jb + kb), v)) T0 = iadd(T0, isum(imul(ihM(isel(self.Rs1, rc), M), self.Phi))) inner = imul(self.H1, isel(self.KH1, tc)) inner = (inner[0].copy(), inner[1].copy()) inner[0][:ie] = dn(inner[0][:ie] + self.WK[0]); inner[1][:ie] = up(inner[1][:ie] + self.WK[1]) T0 = iadd(T0, isum(imul(ihM(isel(Kn.s, si), M), inner))) T0 = iadd(T0, isum(imul(ihM(self.H2, M), imul(isel(Kn.S[2], mi), isel(self.K0s, tm))))) T0 = iadd(T0, iscal(sg(1), f1)) self.f1 = f1; self.T0 = ifloat(T0) if self.mode == "check": ok = self.T0[0] <= 0 <= self.T0[1] self.log(f"{self.tl()} CHECK T0 (untwisted, random data): enclosure {fmt_iv(self.T0, 6)} {'CONTAINS 0' if ok else 'EXCLUDES 0'}") self.check_T0 = ok return L02 = Kn.Lam[(0, 2)]; L03 = Kn.Lam[(0, 3)] f1g = (float(L03[0][last]), float(L03[1][last])) T0g = iscal(sg(3), (D[(0, 3)][0][last], D[(0, 3)][1][last])) T0g = iadd(T0g, iscal(sg(2), isum(imul(ihM(isel(D[(0, 1)], rc), M), isel(L02, ac))))) T0g = ifloat(iadd(T0g, iscal(sg(1), f1g))) self.f1g, self.T0g = f1g, T0g assert T0g[1] < 0 or T0g[0] > 0, "T0(g) interval contains 0" tint = idiv(ineg(self.T0), T0g) self.tint = (float(tint[0]), float(tint[1])) self.log(f"{self.tl()} f(1) before the solve within {fmt_iv(f1)}; T0(c) within {fmt_iv(self.T0)}; T0(g) within {fmt_iv(T0g)}; " f"f1(g) within {fmt_iv(f1g)}; t* within [{fmt_bound(self.tint[0], 6)}, {fmt_bound(self.tint[1], 6, True)}]") # ---------------- positivity (as p4ind/p4rig2.py) ---------------- def positivity(self, t): M, ie, ia, ih, h, Q = self.M, self.ie, self.ia, self.ih, self.h, self.Q 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)) where = (tag, (int(pos[k]) if pos is not None else k)) if lo[k] < res["min"][0]: res["min"] = (float(lo[k]), where) 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]), where[1], float(hi[kh])) else: per[tag] = (min(per[tag][0], float(lo[k])), where[1] if lo[k] < per[tag][0] else per[tag][1], min(per[tag][2], float(hi[kh]))) si = np.arange(ie, ia) H1 = self.H1; H2x = self.H2x for (j, k) in sorted(strict_classes()): v = self.c.get((j, k), 0.0) base = (v, v) if (j, k) == (0, 3): base = iadd(base, (t, t)) if j == 1: ok = (2 * (M - si - 1) <= k * M) & (6 * (M - si) >= k * M) f = iadd((np.full(ok.sum(), base[0]), np.full(ok.sum(), base[1])), (H1[0][ok], H1[1][ok])) upd(f, ("free", j, k), si[ok]) elif j == 2: mi = np.arange(2 * ie, 2 * ia) ok = (2 * (M - mi - 1) <= k * M) & (6 * (M - mi) >= k * M) mm = mi[ok] f = iadd((np.full(len(mm), base[0]), np.full(len(mm), base[1])), isel(H2x, mm)) upd(f, ("free", j, k), mm) else: upd(base, ("free", j, k)) ac = np.arange(ih, M) A = (dn(ac / M), up((ac + 1) / M)) Lam0 = isel(Kn.Lam0, ac) Phi = self.Phi L02 = isel(Kn.Lam[(0, 2)], ac) H1cmin = np.minimum.accumulate(H1[0]); H1cmax = np.maximum.accumulate(H1[1]) H2p_lo = np.minimum.accumulate(H2x[0][2 * ie:2 * ia]); H2p_hi = np.maximum.accumulate(H2x[1][2 * ie:2 * ia]) Psi_cmin = np.minimum.accumulate(self.Psi[0], axis=0); Psi_cmax = np.maximum.accumulate(self.Psi[1], axis=0) gs = self.gs; nPsi = self.Psi[0].shape[1] for jb in range(0, 10): for kb in range(0, 3): if jb + kb == 0: continue ok = (18 * (M - ac - 1) <= (3 * jb + 9 * kb) * M) & (18 * (M - ac) >= (jb + 3 * kb) * M) if not ok.any(): continue e = self.EC(jb, kb) cp = isel(e, ac) if e is not None else izeros(len(ac)) tag = ("ext", jb, kb) if jb == 0: inner = iadd(cp, Phi) if kb == 1: inner = iadd(inner, iscal(t, L02)) f = imul(A, inner) upd(isel(f, ok), tag, ac[ok]) elif jb == 1 and kb == 0: sl = np.arange(ie, ia); aidx = M - 1 - sl - ih lineH2 = izeros(ia - ie); lineH2[0][:ie] = self.Line[0]; lineH2[1][:ie] = self.Line[1] inner = iadd(iadd(isel(cp, aidx), imul(H1, isel(Lam0, aidx))), lineH2) f = imul(isel(A, aidx), inner) upd(f, tag, sl) elif jb == 2 and kb == 0: mi = np.arange(2 * ie, 2 * ia); aidx = M - 1 - mi - ih inner = iadd(isel(cp, aidx), imul(isel(H2x, mi), isel(Lam0, aidx))) f = imul(isel(A, aidx), inner) upd(f, tag, mi) elif jb == 1: aa = ac[ok]; ai = aa - ih pe = np.minimum(ia, M - aa - kb * ia) good = pe > ie aa, ai, pe = aa[good], ai[good], pe[good] H1r = (H1cmin[pe - 1 - ie], H1cmax[pe - 1 - ie]) term1 = imul(H1r, isel(Lam0, ai)) nq = np.minimum((pe - ie + gs - 1) // gs, Q) assert np.all(ai < nPsi) q = np.maximum(nq - 1, 0) ps_lo = np.where(nq > 0, Psi_cmin[q, ai], 0.0); ps_hi = np.where(nq > 0, Psi_cmax[q, ai], 0.0) beyond = pe > 2 * ie ps_lo = np.where(beyond, np.minimum(ps_lo, 0.0), ps_lo); ps_hi = np.where(beyond, np.maximum(ps_hi, 0.0), ps_hi) inner = iadd(iadd(isel(cp, ai), term1), (ps_lo, ps_hi)) f = imul(isel(A, ai), inner) upd(f, tag, aa) elif jb == 2: aa = ac[ok]; ai = aa - ih pe = np.minimum(2 * ia, M - aa - kb * ia) good = pe > 2 * ie aa, ai, pe = aa[good], ai[good], pe[good] H2r = (H2p_lo[pe - 1 - 2 * ie], H2p_hi[pe - 1 - 2 * ie]) inner = iadd(isel(cp, ai), imul(H2r, isel(Lam0, ai))) f = imul(isel(A, ai), inner) upd(f, tag, aa) else: f = imul(A, cp) upd(isel(f, ok), tag, ac[ok]) return res, per def run(self): self.setup_rows() self.solve_H2() self.pass1() self.solve_H1() self.pass2() self.phis() self.f1_T0() if self.mode == "check": return out = [] for t in self.tint: f1t = ifloat(iadd(self.f1, iscal(t, self.f1g))) res, per = self.positivity(t) mn = res["min"][0] if not f1t[1] < 0: m = -INF else: ratio = float(up(mn / f1t[1])) m = float(dn(1.0 - ratio)) 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):18s} stratum min within [{fmt_bound(per[tag][0])}, {fmt_bound(per[tag][2], 5, True)}] " f"(lower end at cell {per[tag][1]})") self.endpoints = out 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 (exact integer convolutions: {self.X.nconv} products)") def main(): M = int(sys.argv[1]) if len(sys.argv) > 1 else 720 mode = sys.argv[2] if len(sys.argv) > 2 else "cert" Q = int(sys.argv[3]) if len(sys.argv) > 3 else 4 if mode == "cert": c = load_c() else: rng = np.random.default_rng(12345) c = {(j, k): float(rng.normal()) for j in range(0, 7) for k in range(0, 6) if j + k >= 2} C = Cert3(M, c, mode=mode, Q=Q) C.run() if __name__ == "__main__": main()