# cert_p4_exact_v3.py: exact-integer first-order certificate for the case (1/18, 1/6), written from the # mathematical text of the construction. Usage: python cert_p4_exact_v3.py M NB NQ PICKLE [TAG]. # Writes cert4v3__M.json. import sys, time, json, hashlib, pickle from fractions import Fraction as Fr from flint import fmpz_poly T_START = time.time() M = int(sys.argv[1]); NB = int(sys.argv[2]); NQ = int(sys.argv[3]) PKL = sys.argv[4] if len(sys.argv) > 4 else 'cont_h2_sol_e18a6nb_reg0.10.pkl' TAG = sys.argv[5] if len(sys.argv) > 5 else 'main' assert M % 36 == 0 SCALE = 10 ** 18; SM = SCALE * M ETA, ALPHA = Fr(1, 18), Fr(1, 6) iE, iA, iH = M // 18, M // 6, M // 2 assert (iA - iE) % NB == 0 and (iA - iE) % NQ == 0, "block counts must divide the s-range cells" def log(*a): print(f"[{time.time() - T_START:7.1f}s]", *a, flush=True) def fl(a, b): return a // b def ce(a, b): return -((-a) // b) def fz(x): return float(Fr(x, SCALE)) raw = open(PKL, 'rb').read(); PKL_SHA = hashlib.sha256(raw).hexdigest(); dpk = pickle.loads(raw) assert dpk['eta'] == ETA and dpk['alpha'] == ALPHA TEXTS = {'main': [(0, 3), (0, 4), (1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (4, 1), (4, 2), (6, 1)], '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) def _real(j, k): # exact realisability with positive measure (open conditions) if k == 0: return j * ETA < 1 < j * ALPHA return j * ETA + k * ALPHA < 1 < j * ALPHA + Fr(k, 2) _seen = set() C = {} for (j, k, b), x in zip(dpk['classes'], dpk['x']): if TEXT is not None: if (j, k) in TEXT and b in (0, 1): assert (j, k) not in _seen; _seen.add((j, k)); C[(j, k)] = Fr(float(x)) else: if abs(float(x)) > 0 and _real(j, k): assert (j, k) not in _seen; _seen.add((j, k)); C[(j, k)] = Fr(float(x)) if TEXT is not None: assert set(C) == set(TEXT), C.keys() log(f"M={M} NB={NB} NQ={NQ} pickle sha256={PKL_SHA} tag={TAG}") log("c:", {k: round(float(v), 6) for k, v in sorted(C.items())}) # ------------------------------------------------------------------ primitives class PL: __slots__ = ('lo', 'hi') def __init__(self, lo, hi): self.lo, self.hi = lo, hi class STEP: __slots__ = ('cl', 'ch') def __init__(self, cl, ch): self.cl, self.ch = cl, ch def zpl(): return PL([0] * (M + 1), [0] * (M + 1)) def zst(): return STEP([0] * M, [0] * M) def step_of(p, c0=0, c1=None): c1 = M if c1 is None else c1 cl = [0] * M; ch = [0] * M; lo, hi = p.lo, p.hi for i in range(c0, c1): a, b = lo[i], lo[i + 1]; cl[i] = a if a < b else b a, b = hi[i], hi[i + 1]; ch[i] = a if a > b else b return STEP(cl, ch) def st_trunc(s, c0, c1=None): c1 = M if c1 is None else c1 return STEP([s.cl[i] if c0 <= i < c1 else 0 for i in range(M)], [s.ch[i] if c0 <= i < c1 else 0 for i in range(M)]) def st_add(a, b, sign=1): if sign > 0: return STEP([x + y for x, y in zip(a.cl, b.cl)], [x + y for x, y in zip(a.ch, b.ch)]) return STEP([x - y for x, y in zip(a.cl, b.ch)], [x - y for x, y in zip(a.ch, b.cl)]) def kernel(i0, i1): cl = [0] * M; ch = [0] * M for i in range(i0, i1): cl[i] = fl(SCALE * M, i + 1); ch[i] = ce(SCALE * M, i) return STEP(cl, ch) def _prod(a, b): if not any(a) or not any(b): return [] return [int(x) for x in (fmpz_poly(a) * fmpz_poly(b)).coeffs()] def _grid(prod, rnd, off=-1): g = [0] * (M + 1); L = len(prod) for n in range(0, M + 1): k = n + off if 0 <= k < L: g[n] = rnd(prod[k], SM) return g def _pos(a): return [x if x > 0 else 0 for x in a] def _neg(a): return [-x if x < 0 else 0 for x in a] def conv_nn(f, g): return PL(_grid(_prod(f.cl, g.cl), fl), _grid(_prod(f.ch, g.ch), ce)) def conv_sn(f, g): lo = [a - b for a, b in zip(_grid(_prod(_pos(f.cl), g.cl), fl), _grid(_prod(_neg(f.cl), g.ch), ce))] hi = [a - b for a, b in zip(_grid(_prod(_pos(f.ch), g.ch), ce), _grid(_prod(_neg(f.ch), g.cl), fl))] return PL(lo, hi) def conv_ss(f, g): fpl, fph, fml, fmh = _pos(f.cl), _pos(f.ch), _neg(f.ch), _neg(f.cl) gpl, gph, gml, gmh = _pos(g.cl), _pos(g.ch), _neg(g.ch), _neg(g.cl) lo = [a + d - b - c for a, b, c, d in zip(_grid(_prod(fpl, gpl), fl), _grid(_prod(fph, gmh), ce), _grid(_prod(fmh, gph), ce), _grid(_prod(fml, gml), fl))] hi = [a + d - b - c for a, b, c, d in zip(_grid(_prod(fph, gph), ce), _grid(_prod(fpl, gml), fl), _grid(_prod(fml, gpl), fl), _grid(_prod(fmh, gmh), ce))] return PL(lo, hi) def corr_sn(f, g): """G(s) = int f(u) g(u - s) du at grid s = n/M, f signed STEP, g nonnegative STEP: (1/M) sum_i f_i g_{i-n} (PL in s)""" gr_l = g.cl[::-1]; gr_h = g.ch[::-1] # reversed: index j -> g_{M-1-j}; sum_i f_i g_{i-n} = coeff at (M-1+n) off = M - 1 lo = [a - b for a, b in zip(_grid(_prod(_pos(f.cl), gr_l), fl, off), _grid(_prod(_neg(f.cl), gr_h), ce, off))] hi = [a - b for a, b in zip(_grid(_prod(_pos(f.ch), gr_h), ce, off), _grid(_prod(_neg(f.ch), gr_l), fl, off))] return PL(lo, hi) def pl_div(p, k): return PL([fl(x, k) for x in p.lo], [ce(x, k) for x in p.hi]) def pl_add(p, q, sign=1): if sign > 0: return PL([a + b for a, b in zip(p.lo, q.lo)], [a + b for a, b in zip(p.hi, q.hi)]) return PL([a - b for a, b in zip(p.lo, q.hi)], [a - b for a, b in zip(p.hi, q.lo)]) def pl_scale(p, c): c = Fr(c); num, den = c.numerator, c.denominator if num >= 0: return PL([fl(num * x, den) for x in p.lo], [ce(num * x, den) for x in p.hi]) return PL([fl(num * x, den) for x in p.hi], [ce(num * x, den) for x in p.lo]) def pl_trunc(p, n0): return PL([0] * n0 + p.lo[n0:], [0] * n0 + p.hi[n0:]) def iv_mul(a, b): ps = [a[0] * b[0], a[0] * b[1], a[1] * b[0], a[1] * b[1]] return (fl(min(ps), SCALE), ce(max(ps), SCALE)) def iv_div(a, b): assert b[0] > 0 or b[1] < 0, "division by an interval containing 0" qs = [Fr(x * SCALE, y) for x in a for y in b] return (fl(min(qs).numerator, min(qs).denominator), ce(max(qs).numerator, max(qs).denominator)) def add_iv(a, b, s=1): return (a[0] + b[0], a[1] + b[1]) if s > 0 else (a[0] - b[1], a[1] - b[0]) def cell(p, n): return (min(p.lo[n], p.lo[n + 1]), max(p.hi[n], p.hi[n + 1])) def at1(p): return (p.lo[M], p.hi[M]) def iv_scale(a, c): c = Fr(c); num, den = c.numerator, c.denominator if num >= 0: return (fl(num * a[0], den), ce(num * a[1], den)) return (fl(num * a[1], den), ce(num * a[0], den)) # ------------------------------------------------------------------ kernels, powers D_{j,k} = S_j * R_k, Lemma K kernels Phi S1 = kernel(iE, iA); R1 = kernel(iA, iH) P = {}; PS = {(1, 0): S1, (0, 1): R1} MAXS, MAXR = 9, 5 for b in range(0, MAXS + 1): for bp in range(0, MAXR + 1): if b + bp < 2 or b * ETA + bp * ALPHA > 1: continue if bp >= 1: prev, ker, div = (b, bp - 1), R1, bp else: prev, ker, div = (b - 1, 0), S1, b if prev not in PS: continue P[(b, bp)] = pl_div(conv_nn(PS[prev], ker), div); PS[(b, bp)] = step_of(P[(b, bp)]) log(f"powers: {len(P)}") TR = {} def trs(bb): if bb not in TR: TR[bb] = None if (sum(bb) < 2 or bb not in P) else step_of(P[bb], iH) return TR[bb] PHI = {} def phi(j, k): if (j, k) in PHI: return PHI[(j, k)] acc = zpl() for bs in range(0, j + 1): for br in range(0, k + 1): if bs + br < 2 or (bs, br) not in P: continue sign = (-1) ** (j + k + 1) * (-1) ** (bs + br); comp = (j - bs, k - br) if comp == (0, 0): X = pl_trunc(P[(bs, br)], iH) else: if comp not in PS: continue X = conv_nn(trs((bs, br)), PS[comp]) acc = pl_add(acc, X, sign) PHI[(j, k)] = pl_trunc(acc, iH); return PHI[(j, k)] def lin_phi(coef): acc = zpl() for jk, cv in coef.items(): if cv != 0: acc = pl_add(acc, pl_scale(phi(*jk), cv)) return acc def H_beta(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 lin_phi(coef) if coef else None L0 = zpl() for k in range(2, MAXR + 1): L0 = pl_add(L0, phi(0, k)) L0S = step_of(L0, iH) # Lambda0 * 1_{>=1/2} as a STEP # rough sums: R_all, E'+ = R2 + R4, E'- = R1 + R3 + R5 (STEPs); PL versions on [1/2,1] (R1 vanishes there) def rsum(ms, as_step=True): s = zst(); p = zpl() for m in ms: if m == 1: s = st_add(s, R1) else: s = st_add(s, PS[(0, m)]); p = pl_add(p, P[(0, m)]) return s, p RALL, RALLp = rsum([1, 2, 3, 4, 5]); EP, EPp = rsum([2, 4]); EM, EMp = rsum([1, 3, 5]) def E_conv(Xpl, Xst, rho_c=None, twisted=True, nodelta=False): """E_rho^{(c)} * X as PL, with E_rho^{(c)} = sum_m rho(c+m) R_m (twisted: (-1)^c E; untwisted: E_u = delta + R_all); X given as PL and STEP""" if twisted: out = zpl() if nodelta else PL(list(Xpl.lo), list(Xpl.hi)) out = pl_add(out, conv_sn(Xst, EP)); out = pl_add(out, conv_sn(Xst, EM), -1) if (rho_c or 0) % 2 == 1: out = PL([-x for x in out.hi], [-x for x in out.lo]) return out out = zpl() if nodelta else PL(list(Xpl.lo), list(Xpl.hi)) return pl_add(out, conv_sn(Xst, RALL)) def E_point(x_cell, rho_c, twisted=True): """E_rho^{(c)} on grid cell x_cell (x >= 1/2, so R1 and delta vanish): sum_{m>=2} rho(c+m) R_m""" lo = hi = 0 for m in range(2, MAXR + 1): v = cell(P[(0, m)], x_cell); s = ((-1) ** (rho_c + m)) if twisted else 1 lo, hi = add_iv((lo, hi), v, s) return (lo, hi) log("kernels ready") # XS(.;1/2) = T(1/2) * E with T(1/2) = R_all 1_{>=1/2} (= R2..R5 on [1/2,1], a PL there) T12p = pl_trunc(RALLp, iH); T12s = step_of(T12p, iH) XS12 = E_conv(T12p, T12s, 0, True) XS12s = step_of(XS12) cmp = max(max(abs(a + b) for a, b in zip(XS12.lo[iH:], L0.hi[iH:])), 0) log(f"cross-check Lambda0 = -XS(.;1/2) on [1/2,1]: max |XS12.lo + L0.hi| = {fz(cmp):.2e} (enclosure widths, should be small)") # ------------------------------------------------------------------ rows T2 (-> H2) and the c-part of T1 def A_cells(base, twisted, cell_lo, cell_hi): """A_base(sigma).c on sigma-cells [cell_lo, cell_hi): free rho(base + j' + k') c[base+j',k'] D_{j',k'}(t) + extended rho(base+1+jw+kw) sum_y c[base+jw+jy, kw+ky](D_w * Phi_y tr)(t)""" rho = (lambda d: (-1) ** d) if twisted else (lambda d: 1) A = zpl() for (cj, ck), cv in C.items(): if cj >= base: jz, kz = cj - base, ck if jz + kz >= 2 and (jz, kz) in P: A = pl_add(A, pl_scale(P[(jz, kz)], cv * rho(base + jz + kz))) jmax = max(j for j, k in C); kmax = max(k for j, k in C) for jp in range(0, jmax + 1): for kp in range(0, kmax + 1): coef = {} for (cj, ck), cv in C.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 G = lin_phi(coef) if (jp, kp) == (0, 0): X = G else: if (jp, kp) not in PS: continue X = conv_sn(step_of(G, iH), PS[(jp, kp)]) A = pl_add(A, pl_scale(X, rho(base + 1 + jp + kp))) return [cell(A, M - i - 1) for i in range(cell_lo, cell_hi)] EL0 = {} # (rho offset parity, twisted) -> PL of E_rho^{(c)} * Lambda0tr def EL0_pl(c, twisted): key = (c % 2 if twisted else 0, twisted) if key not in EL0: EL0[key] = E_conv(L0, L0S, c, twisted) return EL0[key] def B_cells(c1, c2, twisted, cell_lo, cell_hi): """E_rho^{(c1)}(t) + (E_rho^{(c2)} * Lambda0tr)(t) on sigma-cells""" X = EL0_pl(c2, twisted); out = [] for i in range(cell_lo, cell_hi): n = M - i - 1 out.append(add_iv(E_point(n, c1, twisted), cell(X, n))) return out i2E = 2 * iE A2t = A_cells(2, True, i2E, iA); B2t = B_cells(2, 3, True, i2E, iA) A2u = A_cells(2, False, i2E, iA); B2u = B_cells(2, 3, False, i2E, iA) nb = sum(1 for x in A2u if not x[0] <= 0 <= x[1]) + sum(1 for x in B2u if not x[0] <= 0 <= x[1]) log(f"untwisted T2 identity: cells not containing 0: {nb}/{2 * len(A2u)} (A width {fz(max(x[1]-x[0] for x in A2u)):.2e}, B width {fz(max(x[1]-x[0] for x in B2u)):.2e})") B2min, B2max = min(x[0] for x in B2t), max(x[1] for x in B2t) H2c = [iv_div((-a[1], -a[0]), b) for a, b in zip(A2t, B2t)] # H2 on sigma-cells [2iE, iA) H2min, H2max = min(x[0] for x in H2c), max(x[1] for x in H2c) log(f"B2 in [{fz(B2min):+.4f}, {fz(B2max):+.4f}]; H2 in [{fz(H2min):+.4f}, {fz(H2max):+.4f}]; max H2 cell width {fz(max(x[1]-x[0] for x in H2c)):.3e}") def H2_at(i): # H2 on u-cell i (absolute cell index); 0 outside [2iE, iA) return H2c[i - i2E] if i2E <= i < iA else (0, 0) # H2 as STEP on [2iE, iA); S2 cells; H2*S2 STEP H2S = STEP([0] * M, [0] * M) for i in range(i2E, iA): H2S.cl[i], H2S.ch[i] = H2_at(i) S2s = PS[(2, 0)] H2S2 = STEP([0] * M, [0] * M) for i in range(i2E, iA): v = iv_mul(H2_at(i), (S2s.cl[i], S2s.ch[i])); H2S2.cl[i], H2S2.ch[i] = v # ------------------------------------------------------------------ threshold blocks: W's coupled pieces, Omega's middle term psi = STEP([0] * M, [0] * M) for i in range(iE, iA): psi.cl[i], psi.ch[i] = S1.cl[i], S1.ch[i] def G_pm(q): """threshold theta = q/M: T = R_all 1_{>=theta}; G+ = T*E'-, G- = T + T*E'+ (both PL, >= 0)""" T = st_trunc(RALL, q) Gp = conv_nn(T, EM) Gm_conv = conv_nn(T, EP) Tp = PL([0] * (M + 1), [0] * (M + 1)) # T as PL: on [q, 1/2) it is the R1 kernel (a step); use its cell bounds at both cell ends (conservative PL-from-step) for n in range(M + 1): a_l = T.cl[n - 1] if n - 1 >= 0 else 0; b_l = T.cl[n] if n < M else 0 a_h = T.ch[n - 1] if n - 1 >= 0 else 0; b_h = T.ch[n] if n < M else 0 Tp.lo[n] = a_l if a_l < b_l else b_l; Tp.hi[n] = a_h if a_h > b_h else b_h Gm = pl_add(Tp, Gm_conv) return Gp, Gm def PN(Gp, Gm, twisted): Gps, Gms = step_of(Gp), step_of(Gm) if twisted: Pf = pl_add(pl_add(Gm, conv_nn(Gms, EP)), conv_nn(Gps, EM)) Nf = pl_add(pl_add(Gp, conv_nn(Gps, EP)), conv_nn(Gms, EM)) else: Pf = pl_add(Gm, conv_nn(Gms, RALL)); Nf = pl_add(Gp, conv_nn(Gps, RALL)) return Pf, Nf # fixed-threshold X_rho = E_rho^{(2)} * XS(.;1/2), and E_rho^{(3)} * Lambda0tr, for the psi-correlation (pieces 1, 2a, 3) def Wphi_main(twisted): X2 = E_conv(XS12, XS12s, 2, twisted) EL3 = EL0_pl(3, twisted) f13 = STEP([0] * M, [0] * M); f2 = STEP([0] * M, [0] * M) for i in range(i2E, iA): # u-cells; evaluate the bracket at x = 1 - u (cell M - i - 1) n = M - i - 1 e2 = E_point(n, 2, twisted); x2 = cell(X2, n); l3 = cell(EL3, n) b13 = add_iv(e2, l3); b2 = x2 v13 = iv_mul(H2_at(i), b13); v2 = iv_mul(H2_at(i), b2) f13.cl[i], f13.ch[i] = v13; f2.cl[i], f2.ch[i] = v2 return f13, f2 blk = (iA - iE) // NB # v2: J for the extended (j_b, k_b) = (1, 0) positivity term (fixed threshold 1/2 piece) fJ0 = STEP([0] * M, [0] * M) for i in range(i2E, iA): v = iv_mul(H2_at(i), cell(XS12, M - i - 1)); fJ0.cl[i], fJ0.ch[i] = v JPOS = corr_sn(fJ0, psi) Wt13, Wt2 = Wphi_main(True); Wu13, Wu2 = Wphi_main(False) W13t = corr_sn(Wt13, psi); W2t = corr_sn(Wt2, psi); W13u = corr_sn(Wu13, psi); W2u = corr_sn(Wu2, psi) OMmid = zpl() prevG = None def thr_data(q): Gp, Gm = G_pm(q) return dict(G=(Gp, Gm), T=PN(Gp, Gm, True), U=PN(Gp, Gm, False)) for b in range(NB): s_lo, s_hi = iE + b * blk, iE + (b + 1) * blk # block of s' cells [s_lo, s_hi) q_lo, q_hi = iH - s_hi, iH - s_lo # thresholds theta_lo = 1/2 - s_hi, theta_hi = 1/2 - s_lo D_hi = prevG if prevG is not None else thr_data(q_hi) # theta_hi of block b = theta_lo of block b-1 D_lo = thr_data(q_lo); prevG = D_lo G_hi, G_lo = D_hi['G'], D_lo['G'] # XS bounds on the block: [G-(hi) - G+(lo), G-(lo) - G+(hi)] XSb = PL([a - c for a, c in zip(G_hi[1].lo, G_lo[0].hi)], [a - c for a, c in zip(G_lo[1].hi, G_hi[0].lo)]) psib = st_trunc(psi, s_lo, s_hi) fbJ = STEP([0] * M, [0] * M) # v2: J's threshold-block piece (XS bounds on the block, no E) for i in range(i2E, iA): v = iv_mul(H2_at(i), cell(XSb, M - i - 1)); fbJ.cl[i], fbJ.ch[i] = v JPOS = pl_add(JPOS, corr_sn(fbJ, psib), -1) for twisted in (True, False): Pl, Nl = D_lo['T' if twisted else 'U']; Ph, Nh = D_hi['T' if twisted else 'U'] XE = PL([a - c for a, c in zip(Ph.lo, Nl.hi)], [a - c for a, c in zip(Pl.hi, Nh.lo)]) fb = STEP([0] * M, [0] * M) for i in range(i2E, iA): n = M - i - 1; v = iv_mul(H2_at(i), cell(XE, n)); fb.cl[i], fb.ch[i] = v g = corr_sn(fb, psib) if twisted: W2t = pl_add(W2t, g, -1) else: W2u = pl_add(W2u, g, -1) # Omega's middle' term: (H2 * S_b2) * (slab_b * E), slab(s') = R_all 1_{[1/2 - s', 1/2)}, nested in s' -> bounds at the block ends Sb2 = conv_nn(psib, S1) w = STEP([0] * M, [0] * M) for i in range(i2E, iA): v = iv_mul(H2_at(i), cell(Sb2, i)); w.cl[i], w.ch[i] = v sl_n = st_trunc(RALL, iH - s_lo, iH); sl_w = st_trunc(RALL, iH - s_hi, iH) # narrow (s' = s_lo) and wide (s' = s_hi) slabs def slab_pl(sl): # step -> PL bounds (min/max of adjacent cells, zeros included) lo = [0] * (M + 1); hi = [0] * (M + 1) for n_ in range(M + 1): a_l = sl.cl[n_ - 1] if n_ >= 1 else 0; b_l = sl.cl[n_] if n_ < M else 0 a_h = sl.ch[n_ - 1] if n_ >= 1 else 0; b_h = sl.ch[n_] if n_ < M else 0 lo[n_] = min(a_l, b_l); hi[n_] = max(a_h, b_h) return PL(lo, hi) pn, pw = slab_pl(sl_n), slab_pl(sl_w) SE_lo = pl_add(pl_add(pn, conv_nn(sl_n, EP)), conv_nn(sl_w, EM), -1) SE_hi = pl_add(pl_add(pw, conv_nn(sl_w, EP)), conv_nn(sl_n, EM), -1) SEb = PL(SE_lo.lo, SE_hi.hi) OMmid = pl_add(OMmid, conv_ss(w, step_of(SEb))) log(f"threshold blocks done ({NB})") def s_cells(p): return [cell(p, i) for i in range(iE, iA)] W2t_c, W2u_c = s_cells(W2t), s_cells(W2u) Wt_c = [add_iv(a, b) for a, b in zip(s_cells(W13t), W2t_c)] Wu_c = [add_iv(a, b) for a, b in zip(s_cells(W13u), W2u_c)] A1t = A_cells(1, True, iE, iA); B1t = B_cells(1, 2, True, iE, iA) A1u = A_cells(1, False, iE, iA); B1u = B_cells(1, 2, False, iE, iA) nb1 = sum(1 for x in A1u if not x[0] <= 0 <= x[1]) + sum(1 for x in B1u if not x[0] <= 0 <= x[1]) nbw = sum(1 for x in Wu_c if not x[0] <= 0 <= x[1]) log(f"untwisted T1 identity: c/H1 coefficient cells not containing 0: {nb1}/{2 * len(A1u)}; W (actual H2) cells not containing 0: {nbw}/{len(Wu_c)} " f"(W width {fz(max(x[1]-x[0] for x in Wu_c)):.2e})") B1min, B1max = min(x[0] for x in B1t), max(x[1] for x in B1t) H1c = [iv_div((-(a[1] + w_[1]), -(a[0] + w_[0])), bb) for a, w_, bb in zip(A1t, Wt_c, B1t)] H1min, H1max = min(x[0] for x in H1c), max(x[1] for x in H1c) log(f"B1 in [{fz(B1min):+.4f}, {fz(B1max):+.4f}]; H1 in [{fz(H1min):+.4f}, {fz(H1max):+.4f}]; max H1 cell width {fz(max(x[1]-x[0] for x in H1c)):.3e}") SH1 = STEP([0] * M, [0] * M) for idx, i in enumerate(range(iE, iA)): v = iv_mul(H1c[idx], (S1.cl[i], S1.ch[i])); SH1.cl[i], SH1.ch[i] = v # ------------------------------------------------------------------ Psi_h and Omega_H2 (functions of a), f(1), T0 RLOW = st_trunc(RALL, 0, iH) # R_all restricted to (alpha, 1/2) def Psi(Sh): """Psi_h(a) = -(((S_h * R_all 1_{<1/2}) 1_{>=1/2}) * E)(a) (slab identity; equals S_h*XS12 - ((S_h*R_all)tr)*E exactly)""" X = pl_trunc(conv_sn(Sh, RLOW), iH) t = E_conv(X, step_of(X, iH), 0, True) return PL([-x for x in t.hi], [-x for x in t.lo]) PSI1 = Psi(SH1) X = pl_trunc(conv_sn(H2S2, RLOW), iH); t3p = E_conv(X, step_of(X, iH), 0, True) OM = pl_add(OMmid, t3p, -1) # Omega = middle' - term3' (term1 cancels exactly; DERIVED) log("Psi_H1 and Omega_H2 done") def T0_c(dd, twisted): rho = (lambda d: (-1) ** d) if twisted else (lambda d: 1) acc = (0, 0) for (j, k), cv in dd.items(): if (j, k) in P: acc = add_iv(acc, at1(pl_scale(P[(j, k)], cv * rho(j + k)))) if j + k >= 2: acc = add_iv(acc, at1(pl_scale(phi(j, k), cv * rho(1)))) # the prime: rho(1) f(1) c-part 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 PS: continue Hb = H_beta(jb, kb, dd) if Hb is None: continue acc = add_iv(acc, at1(pl_scale(conv_sn(step_of(Hb, iH), PS[(jb, kb)]), rho(1 + jb + kb)))) return acc DIAG = [] def T0_h(twisted): rho = (lambda d: (-1) ** d) if twisted else (lambda d: 1) acc = (0, 0) def tag(name, before, after): DIAG.append((twisted, name, fz(after[1] - after[0] - (before[1] - before[0])), fz((after[0] + after[1] - before[0] - before[1]) // 2))) # free j=1: (S_H1 * E_rho^{(1)})(1); free j=2: (H2S2 * E_rho^{(2)})(1) [x = 1: delta terms vanish] b0 = acc; acc = add_iv(acc, dot_cells(H1c, KtT if twisted else KtU)); tag('H1 kernel (free j=1, prime, ext jb=0, ext jb=1)', b0, acc) b0 = acc; acc = add_iv(acc, at1(E_conv(zpl(), H2S2, 2, twisted, nodelta=True))); tag('free j=2', b0, acc) # prime: rho(1) * (Psi_H1 + Omega)(1) b0 = acc; acc = add_iv(acc, iv_scale(at1(OM), rho(1))); tag('prime Omega', b0, acc) # extended j_b = 0: ((Psi + Omega) tr) * sum_{kb>=1} rho(1+kb) R_kb POs = step_of(OM, iH) b0 = acc; acc = add_iv(acc, at1(E_conv(OM, POs, 1, twisted, nodelta=True))); tag('ext jb=0 Omega', b0, acc) # extended j_b = 1, H1 part: Lambda0tr * S_H1 * E_rho^{(2)} # extended j_b = 1, H2 part: int s(s) W2_rho(s) ds over s-cells W2 = W2t_c if twisted else W2u_c b0 = acc for idx, i in enumerate(range(iE, iA)): v = iv_mul((S1.cl[i], S1.ch[i]), W2[idx]); acc = add_iv(acc, (fl(v[0], M), ce(v[1], M))) tag('ext jb=1 H2', b0, acc) # extended j_b = 2 (sigma <= alpha): Lambda0tr * H2S2 * E_rho^{(3)} Y = conv_ss(L0S, H2S2) b0 = acc; acc = add_iv(acc, at1(E_conv(Y, step_of(Y), 3, twisted))); tag('ext jb=2', b0, acc) return acc # ---- H1 kernels (DERIVED): Lambda1(1;s) = (1/s)[XS12(1-s) - Z0(s)], Z0(s) = R_all(1-s) + corr(E'(1-v)1_{v>=1/2}, R_all)(s); # (E_rho^{(1)} * Lambda1(.;s))(1) = (1/s)[X1(1-s) - Z1(s)], X1 = E_rho^{(1)} * XS12, Z1(s) = rho(1) R_all(1-s) + corr(F1'(1-v)1_{v>=1/2}, R_all)(s), # F1' = E'_rho + rho(1) E' + E' * E'_rho. T0's H1-kernel: K_T0(s) = s(s)[E_rho^{(1)}(1-s) + (Lambda0tr * E_rho^{(2)})(1-s)] + (E_rho^{(1)} * Lambda1(.;s))(1). def flip_step(f): """phi(v) = f(1 - v) on cells: cell v <-> cell M-1-v; restricted to v >= 1/2 (cells >= iH)""" cl = [0] * M; ch = [0] * M for v in range(iH, M): cl[v], ch[v] = f.cl[M - 1 - v], f.ch[M - 1 - v] return STEP(cl, ch) EPm = st_add(EP, EM, -1) # E' = E'+ - E'- (signed STEP) def EpEp(): # E' * E' as PL: E'+*E'+ + E'-*E'- - 2 E'+*E'- a = conv_nn(EP, EP); b = conv_nn(EM, EM); c = conv_nn(EP, EM) return pl_add(pl_add(a, b), pl_add(c, c), -1) EEp = step_of(EpEp()) def Fprime(twisted): if twisted: # -(2E' + E'*E') f = st_add(st_add(EPm, EPm), EEp) return STEP([-x for x in f.ch], [-x for x in f.cl]) ERA = step_of(conv_nn(RALL, EP)); ERM = step_of(conv_nn(RALL, EM)) # E' * R_all = R_all*E'+ - R_all*E'- return st_add(st_add(RALL, EPm), st_add(ERA, ERM, -1)) def RALL_at(n): # R_all on x-cell n (x >= 1/2: R2..R5) lo = hi = 0 for m in range(2, MAXR + 1): v = cell(P[(0, m)], n); lo += v[0]; hi += v[1] return (lo, hi) def H1_kernel_terms(twisted): rho1 = -1 if twisted else 1 Z0c = s_cells(corr_sn(flip_step(EPm), RALL)) Z1c = s_cells(corr_sn(flip_step(Fprime(twisted)), RALL)) X1 = E_conv(XS12, XS12s, 1, twisted) EL2 = EL0_pl(2, twisted) Kf, Kt = [], [] for idx, i in enumerate(range(iE, iA)): n = M - 1 - i; inv = (S1.cl[i], S1.ch[i]); ra = RALL_at(n) z0 = add_iv(ra, Z0c[idx]); z1 = add_iv(iv_scale(ra, rho1), Z1c[idx]) kf = iv_mul(inv, add_iv(cell(XS12, n), z0, -1)) k1 = iv_mul(inv, add_iv(cell(X1, n), z1, -1)) k0 = iv_mul(inv, add_iv(E_point(n, 1, twisted), cell(EL2, n))) Kf.append(kf); Kt.append(add_iv(k0, k1)) return Kf, Kt def dot_cells(H, K): acc = (0, 0) for h_, k_ in zip(H, K): v = iv_mul(h_, k_); acc = add_iv(acc, (fl(v[0], M), ce(v[1], M))) return acc KfT, KtT = H1_kernel_terms(True); KfU, KtU = H1_kernel_terms(False) f1H1 = dot_cells(H1c, KfT) log(f"H1 kernels: f(1) H1-part {[round(fz(x), 4) for x in f1H1]} (conv route {[round(fz(x), 4) for x in at1(PSI1)]})") f1c = (0, 0) for jk, cv in C.items(): f1c = add_iv(f1c, at1(pl_scale(phi(*jk), cv))) F1c = add_iv(f1c, add_iv(f1H1, at1(OM))) T0u = add_iv(T0_c(C, False), T0_h(False)) log(f"untwisted T0 identity (actual data): [{fz(T0u[0]):+.3e}, {fz(T0u[1]):+.3e}] (must contain 0)") log("T0 h-part widths (untwisted):", [(n_, round(w_, 4)) for t_, n_, w_, m_ in DIAG if not t_]); _tc = T0_c(C, False); log(f"T0 c-part width (untwisted): {fz(_tc[1]-_tc[0]):.4f}") _tct = T0_c(C, True); T0 = add_iv(_tct, T0_h(True)) log(f"twisted T0 parts (midpoints): c-part {fz((_tct[0]+_tct[1])//2):+.4f};", [(n_, round(m_, 4)) for t_, n_, w_, m_ in DIAG if t_]) for jk, cv in sorted(C.items()): _x = T0_c({jk: Fr(1)}, True); log(f" twisted T0 coefficient of class {jk}: {fz((_x[0]+_x[1])//2):+.5f} (c = {float(cv):+.4f}, contribution {float(cv)*fz((_x[0]+_x[1])//2):+.4f})") T0g = T0_c({(0, 3): Fr(1)}, True) tiv = iv_div((-T0[1], -T0[0]), T0g) phi03 = at1(phi(0, 3)) F1 = add_iv(F1c, iv_mul(tiv, phi03)) log(f"T0(c) in [{fz(T0[0]):+.5f}, {fz(T0[1]):+.5f}]; T0(g) in [{fz(T0g[0]):+.5f}, {fz(T0g[1]):+.5f}]; t in [{fz(tiv[0]):+.5f}, {fz(tiv[1]):+.5f}]") log(f"f(1) at c: [{fz(F1c[0]):+.5f}, {fz(F1c[1]):+.5f}]; on the segment: [{fz(F1[0]):+.5f}, {fz(F1[1]):+.5f}]") OUT = dict(M=M, NB=NB, NQ=NQ, tag=TAG, pickle_sha256=PKL_SHA, c={str(k): str(v) for k, v in C.items()}, B2=[str(Fr(B2min, SCALE)), str(Fr(B2max, SCALE))], H2=[str(Fr(H2min, SCALE)), str(Fr(H2max, SCALE))], B1=[str(Fr(B1min, SCALE)), str(Fr(B1max, SCALE))], H1=[str(Fr(H1min, SCALE)), str(Fr(H1max, SCALE))], T0u=[str(Fr(T0u[0], SCALE)), str(Fr(T0u[1], SCALE))], T0=[str(Fr(T0[0], SCALE)), str(Fr(T0[1], SCALE))], T0g=[str(Fr(T0g[0], SCALE)), str(Fr(T0g[1], SCALE))], t=[str(Fr(tiv[0], SCALE)), str(Fr(tiv[1], SCALE))], f1=[str(Fr(F1[0], SCALE)), str(Fr(F1[1], SCALE))], untwisted_bad=[nb, nb1, nbw]) if not F1[1] < 0: OUT['verdict'] = 'FAIL (f(1) not certified negative)' json.dump(OUT, open(f'cert4v3_{TAG}_M{M}.json', 'w'), indent=1) log("VERDICT FAIL: f(1)_hi >= 0"); sys.exit(0) # ------------------------------------------------------------------ positivity 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 tot_range(j, k): return (j * ETA + k * ALPHA, j * ALPHA + Fr(k, 2)) if k > 0 else (j * ETA, j * ALPHA) free_min = 0; free_arg = None H1lo = min(x[0] for x in H1c) for j in range(0, 19): for k in range(0, MAXR + 1): if not realisable_free(j, k): continue v = C.get((j, k), Fr(0)); lo = fl(v.numerator * SCALE, v.denominator) if (j, k) == (0, 3): lo += min(0, tiv[0]) cands = [lo] if j == 1: cands = [lo + H1lo] if j == 2: cands = [lo + H2min, lo] # sigma <= alpha (H2) or sigma > alpha (no H2) for x in cands: if x < free_min: free_min, free_arg = x, (j, k) log(f"free min >= {fz(free_min):+.5f} at {free_arg}") ext_min = 0; ext_arg = None EXT = {} JCHK = [0, 0] 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 HB = {} for jb in range(0, 10): for kb in range(0, 4): if (jb, kb) != (0, 0): h_ = H_beta(jb, kb, C); HB[(jb, kb)] = h_ HBg = {kb: (phi(0, 3 - kb) if 3 - kb >= 2 else None) for kb in range(0, 4)} PO = pl_add(PSI1, OM) # coarse s_beta blocks for j_beta = 1: H1 range and Psi_{H2q} qb = (iA - iE) // NQ # sparse tables over H2 cells [i2E, iA): range min of lower bounds, range max of upper bounds _lo = [H2c[u - i2E][0] for u in range(i2E, iA)]; _hi = [H2c[u - i2E][1] for u in range(i2E, iA)] SPmin, SPmax = [_lo], [_hi] while (1 << len(SPmin)) <= len(_lo): k = len(SPmin); h = 1 << (k - 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): l -= i2E; r -= i2E k = (r - l + 1).bit_length() - 1 return (min(SPmin[k][l], SPmin[k][r - (1 << k) + 1]), max(SPmax[k][l], SPmax[k][r - (1 << k) + 1])) QB = [] for q in range(NQ): c0, c1 = iE + q * qb, iE + (q + 1) * qb h1r = (min(H1c[i - iE][0] for i in range(c0, c1)), max(H1c[i - iE][1] for i in range(c0, c1))) Sh = STEP([0] * M, [0] * M) for i in range(iE, iA): # s' cell i: u ranges over cells [c0 + i, c1 + i] (straddle included) l, r = c0 + i, c1 + i if l > iA - 1: lo_, hi_ = 0, 0 else: lo_, hi_ = rq(l, min(r, iA - 1)) if r >= iA - 1: lo_, hi_ = min(lo_, 0), max(hi_, 0) v = iv_mul((lo_, hi_), (S1.cl[i], S1.ch[i])); Sh.cl[i], Sh.ch[i] = v QB.append((c0, c1, h1r, Psi(Sh))) log(f"positivity: {NQ} coarse s_beta blocks ready") for jb in range(0, 10): for kb in range(0, 4): if (jb, kb) == (0, 0): continue tlo, thi = tot_range(jb, kb) if tlo >= Fr(1, 2): continue Hb = HB[(jb, kb)]; Hg = HBg[kb] if jb == 0 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 base = cell(Hb, n) if Hb is not None else (0, 0) if Hg is not None: base = add_iv(base, iv_mul(tiv, cell(Hg, n))) a_iv = (fl(SCALE * n, M), ce(SCALE * (n + 1), M)) if jb == 0: upd(iv_mul(a_iv, add_iv(base, cell(PO, n))), (jb, kb, n / M)) elif jb == 1 and kb == 0: ib = M - n - 1 # s_b = 1 - a exactly: one s-cell if not (iE <= ib < iA): continue l0 = cell(L0, n) jc = cell(JPOS, ib) br = add_iv(add_iv(base, iv_mul(H1c[ib - iE], l0)), jc) upd(iv_mul(a_iv, br), (jb, kb, n / M, ib / M)) for (c0, c1, h1r, ps) in QB: # consistency: v1's coarse-block enclosure of the same J must overlap if c0 <= ib < c1: pc = cell(ps, n); JCHK[0] += 1 if pc[1] < jc[0] or jc[1] < pc[0]: JCHK[1] += 1 elif jb == 1: # realisable s_beta range for this a-cell: s in [max(eta, tau_lo - kb/2), min(alpha, tau_hi - kb*alpha)] (kb = 0: s = tau) s_lo_ = max(ETA, tau_lo - Fr(kb, 2)) if kb > 0 else max(ETA, tau_lo) s_hi_ = min(ALPHA, tau_hi - kb * ALPHA) if kb > 0 else min(ALPHA, tau_hi) if s_lo_ > s_hi_: continue l0 = cell(L0, n) for (c0, c1, h1r, ps) in QB: if Fr(c1, M) < s_lo_ or Fr(c0, M) > s_hi_: continue br = add_iv(add_iv(base, iv_mul(h1r, l0)), cell(ps, n)) upd(iv_mul(a_iv, br), (jb, kb, n / M, c0 / M)) elif jb == 2: # realisable small total sigma for this a-cell: [max(2eta, tau_lo - kb/2), tau_hi - kb*alpha]; H2 applies for sigma <= alpha sg_lo = max(2 * ETA, tau_lo - Fr(kb, 2)) if kb > 0 else max(2 * ETA, tau_lo) sg_hi = (tau_hi - kb * ALPHA) if kb > 0 else tau_hi if sg_lo > sg_hi: continue l0 = cell(L0, n) c_lo, c_hi = int(sg_lo * M), min(int(sg_hi * M), M - 1) rng = [] if c_lo <= iA - 1: rng.append(rq(max(c_lo, i2E), min(c_hi, iA - 1))) if sg_hi > ALPHA: rng.append((0, 0)) h2r = (min(x[0] for x in rng), max(x[1] for x in rng)) br = add_iv(base, iv_mul(h2r, l0)) upd(iv_mul(a_iv, br), (jb, kb, n / M)) else: upd(iv_mul(a_iv, base), (jb, kb, n / M)) log(f"extended min >= {fz(ext_min):+.5f} at {ext_arg}") log(f"v2 consistency: (1,0) cells checked against v1 coarse blocks: {JCHK[0]}, non-overlapping: {JCHK[1]} (must be 0)") for key in sorted(EXT): log(f" extended min for (j_b, k_b) = {key}: {fz(EXT[key][0]):+.5f} at {EXT[key][1]}") m_ = min(free_min, ext_min) margin = 1 - Fr(-m_) / Fr(-F1[1]) if m_ < 0 else Fr(1) verdict = "PASS" if m_ > F1[1] else "FAIL" log(f"VERDICT {verdict}: min f >= {fz(m_):+.5f}, f(1)_hi = {fz(F1[1]):+.5f}, scaled margin >= {float(margin):.4f}") OUT.update(free_min=str(Fr(free_min, SCALE)), free_arg=str(free_arg), ext_min=str(Fr(ext_min, SCALE)), ext_arg=str(ext_arg), verdict=verdict, margin=str(margin), seconds=round(time.time() - T_START, 1), ext_by_class={str(k): [str(Fr(v[0], SCALE)), str(v[1])] for k, v in EXT.items()}, v2_check=JCHK) json.dump(OUT, open(f'cert4v3_{TAG}_M{M}.json', 'w'), indent=1) log("wrote json")