# cert_p3_binned.py: exact-integer first-order certificate for the one-small-prime cases (1/11, 1/10) and (1/14, 1/8), # written from the mathematical text of the construction (not from the code that produced the constants). # Usage: python cert_p3_binned.py M PICKLE CLASSES G [TAG]. Writes certb__M.json. import sys, time, json, hashlib, pickle, math from fractions import Fraction as Fr from flint import fmpz_poly T_START = time.time() M = int(sys.argv[1]); PKL = sys.argv[2] TEXT_CLASSES = [tuple(int(t) for t in s.split(',')) for s in sys.argv[3].split(';')] GCLS = tuple(int(t) for t in sys.argv[4].split(',')) TAG = sys.argv[5] if len(sys.argv) > 5 else 'run' SCALE = 10 ** 18 SM = SCALE * M 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) ETA, ALPHA, EDGES = dpk['eta'], dpk['alpha'], list(dpk['edges']) assert EDGES[0] == ALPHA and EDGES[-1] == Fr(1, 2) NB = len(EDGES) - 1 for q in [ETA, ALPHA] + EDGES: assert (q * M).denominator == 1, f"M does not put {q} on the grid" iE, iA, iH = int(ETA * M), int(ALPHA * M), M // 2 iEdge = [int(e * M) for e in EDGES] C = {} for cls, x in zip(dpk['classes'], dpk['x']): if tuple(cls) in TEXT_CLASSES: C[tuple(cls)] = Fr(float(x)) assert set(C) == set(TEXT_CLASSES), (set(TEXT_CLASSES) - set(C)) log(f"M={M} pickle sha256={PKL_SHA} eta={ETA} alpha={ALPHA} edges={[str(e) for e in EDGES]} tag={TAG}") log("c:", {k: round(float(v), 6) for k, v in sorted(C.items())}) # Abel coefficients d_b[(j,k)], b = 1..NB def abel(cdict): D = {b: {} for b in range(1, NB + 1)} for (j, k, b), v in cdict.items(): if k == 0: assert b == 0 D[NB][(j, 0)] = D[NB].get((j, 0), 0) + v else: D[b][(j, k)] = D[b].get((j, k), 0) + v if b >= 2: D[b - 1][(j, k)] = D[b - 1].get((j, k), 0) - v return {b: {jk: v for jk, v in dd.items() if v != 0} for b, dd in D.items()} D = abel(C) DG = abel({GCLS: Fr(1)}) log("Abel d_b:", {b: {k: round(float(v), 4) for k, v in dd.items()} for b, dd in D.items()}, " g:", DG) # ---------------------------------------------------------------- primitives (as in cert_p3_exact.py) 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 zeros_pl(): return PL([0] * (M + 1), [0] * (M + 1)) def step_of(p, from_cell=0): lo, hi = p.lo, p.hi; cl = [0] * M; ch = [0] * M for i in range(from_cell, M): 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 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_from(prod, rnd): g = [0] * (M + 1); L = len(prod) for n in range(1, M + 1): if n - 1 < L: g[n] = rnd(prod[n - 1], SM) return g def conv_nn(f, g): return PL(_grid_from(_prod(f.cl, g.cl), fl), _grid_from(_prod(f.ch, g.ch), ce)) 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_sn(f, g): lo1 = _grid_from(_prod(_pos(f.cl), g.cl), fl); lo2 = _grid_from(_prod(_neg(f.cl), g.ch), ce) hi1 = _grid_from(_prod(_pos(f.ch), g.ch), ce); hi2 = _grid_from(_prod(_neg(f.ch), g.cl), fl) return PL([a - b for a, b in zip(lo1, lo2)], [a - b for a, b in zip(hi1, hi2)]) 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_from(_prod(fpl, gpl), fl), _grid_from(_prod(fph, gmh), ce), _grid_from(_prod(fmh, gph), ce), _grid_from(_prod(fml, gml), fl))] hi = [a + d - b - c for a, b, c, d in zip(_grid_from(_prod(fph, gph), ce), _grid_from(_prod(fpl, gml), fl), _grid_from(_prod(fml, gpl), fl), _grid_from(_prod(fmh, gmh), ce))] 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): 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 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 cell_at(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 add_iv(acc, x, s=1): return (acc[0] + x[0], acc[1] + x[1]) if s > 0 else (acc[0] - x[1], acc[1] - x[0]) S1 = kernel(iE, iA) # ---------------------------------------------------------------- machinery for one rough cutoff E[b] class Mach: def __init__(self, ecell, maxS, maxR, need_phi): self.R1 = kernel(iA, ecell) self.P, self.PS, self.TR, self.PHI = {}, {(1, 0): S1, (0, 1): self.R1}, {}, {} emax = Fr(ecell, M) 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), self.R1, bp else: prev, ker, div = (b - 1, 0), S1, b if prev not in self.PS: continue self.P[(b, bp)] = pl_div(conv_nn(self.PS[prev], ker), div) self.PS[(b, bp)] = step_of(self.P[(b, bp)]) for jk in need_phi: self.phi(*jk) def trunc_step(self, bb): if bb not in self.TR: self.TR[bb] = None if (sum(bb) < 2 or bb not in self.P) else step_of(self.P[bb], iH) return self.TR[bb] def phi(self, j, k): if (j, k) in self.PHI: return self.PHI[(j, k)] acc = zeros_pl() for bs in range(0, j + 1): for br in range(0, k + 1): if bs + br < 2 or (bs, br) not in self.P: continue sign = (-1) ** (j + k + 1) * (-1) ** (bs + br) comp = (j - bs, k - br) if comp == (0, 0): X = pl_trunc(self.P[(bs, br)], iH) else: if comp not in self.PS: continue X = conv_nn(self.trunc_step((bs, br)), self.PS[comp]) acc = pl_add(acc, X, sign) self.PHI[(j, k)] = pl_trunc(acc, iH) return self.PHI[(j, k)] def lin_phi(self, coef): acc = zeros_pl() for jk, cv in coef.items(): if cv != 0: acc = pl_add(acc, pl_scale(self.phi(*jk), cv)) return acc def H_beta(self, jb, kb, dd): coef = {} for (cj, ck), cv in dd.items(): ju, ku = cj - jb, ck - kb if ju >= 0 and ku >= 0 and ju + ku >= 2: coef[(ju, ku)] = coef.get((ju, ku), 0) + cv return self.lin_phi(coef) if coef else None # c-parts def f1_c(self, dd): acc = (0, 0) for jk, cv in dd.items(): if sum(jk) >= 2: acc = add_iv(acc, at1(pl_scale(self.phi(*jk), cv))) return acc def T0_c(self, dd): acc = (0, 0) for (j, k), cv in dd.items(): if (j, k) in self.P: acc = add_iv(acc, at1(pl_scale(self.P[(j, k)], cv * (-1) ** (j + k)))) if j + k >= 2: acc = add_iv(acc, at1(pl_scale(self.phi(j, k), -cv))) jmax = max((j for j, k in dd), default=0); kmax = max((k for j, k in dd), default=0) for jb in range(0, jmax + 1): for kb in range(0, kmax + 1): if (jb, kb) == (0, 0) or (jb, kb) not in self.PS: continue Hb = self.H_beta(jb, kb, dd) if Hb is None: continue X = conv_sn(step_of(Hb, iH), self.PS[(jb, kb)]) acc = add_iv(acc, at1(X), (-1) ** (1 + jb + kb)) return acc def A_cells(self, dd, twisted=True): """A(sigma).d on sigma-cells (c-part of the d = p row), and its untwisted version""" sgn = (lambda e: (-1) ** e) if twisted else (lambda e: 1) A = zeros_pl() for (cj, ck), cv in dd.items(): if cj >= 1: jz, kz = cj - 1, ck if jz + kz >= 2 and (jz, kz) in self.P: A = pl_add(A, pl_scale(self.P[(jz, kz)], cv * sgn(1 + jz + kz))) jmax = max((j for j, k in dd), default=0); kmax = max((k for j, k in dd), default=0) for jp in range(0, max(jmax, 1)): for kp in range(0, kmax + 1): coef = {} for (cj, ck), cv in dd.items(): ju, ku = cj - 1 - 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 = self.lin_phi(coef) if (jp, kp) == (0, 0): X = G else: if (jp, kp) not in self.PS: continue X = conv_sn(step_of(G, iH), self.PS[(jp, kp)]) A = pl_add(A, pl_scale(X, Fr(sgn(jp + kp)))) return [cell_at(A, M - i - 1) for i in range(iE, iA)] # needed Phi's: everything dominated by a class with nonzero d, plus (0, r) for the h-parts JMAX = max(j for (j, k, b) in TEXT_CLASSES + [GCLS]); KMAX = max(k for (j, k, b) in TEXT_CLASSES + [GCLS]) RMAX = int(1 / ALPHA) # rough pieces > alpha: at most floor(1/alpha) (minus boundary) while RMAX * ALPHA >= 1: RMAX -= 1 SMAX = int(1 / ETA) def needed(dd): return sorted({(j, k) for j in range(0, JMAX + 1) for k in range(0, KMAX + 1) if j + k >= 2 and any(cj >= j and ck >= k for (cj, ck) in dd)}) MAXS = max(JMAX, 5); MAXR = RMAX # ---------------------------------------------------------------- per-bin c-parts f1c = (0, 0); T0c = (0, 0); T0g = (0, 0); f1g = (0, 0) A_tw = [(0, 0)] * (iA - iE); A_un = [(0, 0)] * (iA - iE) HB = {} # (jb, kb, b) -> PL (c-part H_beta for bin term b) HBG = {} # (jb, kb, b) -> PL for the g-direction checks = {} MB = None for b in range(1, NB + 1): dd = D[b]; gg = DG[b] if not dd and not gg and b != NB: continue need = needed({**dd, **gg}) if b == NB: need = sorted(set(need) | {(0, r) for r in range(2, RMAX + 1)}) mach = Mach(iEdge[b], MAXS, MAXR, need) log(f"bin term b={b} (rough <= {EDGES[b]}): {len(mach.P)} powers, {len(mach.PHI)} Phi") if dd: f1c = add_iv(f1c, mach.f1_c(dd)); T0c = add_iv(T0c, mach.T0_c(dd)) at = mach.A_cells(dd, True); au = mach.A_cells(dd, False) A_tw = [add_iv(x, y) for x, y in zip(A_tw, at)]; A_un = [add_iv(x, y) for x, y in zip(A_un, au)] if gg: T0g = add_iv(T0g, mach.T0_c(gg)); f1g = add_iv(f1g, mach.f1_c(gg)) for jb in range(0, JMAX + 1): for kb in range(0, KMAX + 1): if (jb, kb) == (0, 0): continue if dd: h_ = mach.H_beta(jb, kb, dd) if h_ is not None: HB[(jb, kb, b)] = h_ if gg: h_ = mach.H_beta(jb, kb, gg) if h_ is not None: HBG[(jb, kb, b)] = h_ if b == NB: MB = mach else: del mach log("c-parts done") # ---------------------------------------------------------------- h-parts (full rough kernel, bin term NB) P, PS = MB.P, MB.PS SPHI0 = zeros_pl() for r in range(2, RMAX + 1): SPHI0 = pl_add(SPHI0, MB.phi(0, r)) def B_cells(twisted=True): sgn = (lambda e: (-1) ** e) if twisted else (lambda e: 1) Bf = zeros_pl() for k in range(2, RMAX + 1): if (0, k) in P: Bf = pl_add(Bf, pl_scale(P[(0, k)], Fr(sgn(1 + k)))) for kp in range(0, RMAX + 1): if kp * ALPHA >= Fr(1, 2) - ETA: break X = SPHI0 if kp == 0 else conv_sn(step_of(SPHI0, iH), PS[(0, kp)]) Bf = pl_add(Bf, pl_scale(X, Fr(sgn(kp)))) return [cell_at(Bf, M - i - 1) for i in range(iE, iA)] B_tw = B_cells(True); B_un = B_cells(False) nbA = sum(1 for x in A_un if not (x[0] <= 0 <= x[1])); nbB = sum(1 for x in B_un if not (x[0] <= 0 <= x[1])) log(f"untwisted d=p identity per sigma-cell: cells NOT containing 0: A.c {nbA}/{len(A_un)}, h-coefficient {nbB}/{len(B_un)}; " f"widths A {fz(max(x[1]-x[0] for x in A_un)):.2e}, B {fz(max(x[1]-x[0] for x in B_un)):.2e}") assert all(x[0] > 0 for x in B_tw), "B(sigma) not bounded away from 0" Hc = [iv_div((-a[1], -a[0]), bb) for a, bb in zip(A_tw, B_tw)] hmin, hmax = min(x[0] for x in Hc), max(x[1] for x in Hc) Bmin, Bmax = min(x[0] for x in B_tw), max(x[1] for x in B_tw) log(f"B in [{fz(Bmin):.4f}, {fz(Bmax):.4f}]; A.c in [{fz(min(x[0] for x in A_tw)):+.4f}, {fz(max(x[1] for x in A_tw)):+.4f}]; h in [{fz(hmin):+.4f}, {fz(hmax):+.4f}]") shl = [0] * M; shh = [0] * M for idx, i in enumerate(range(iE, iA)): hl, hh = Hc[idx]; ul, uh = S1.cl[i], S1.ch[i] cand = [hl * ul, hl * uh, hh * ul, hh * uh] shl[i] = fl(min(cand), SCALE); shh[i] = ce(max(cand), SCALE) SH = STEP(shl, shh) Q = {br: conv_sn(SH, PS[(0, br)]) for br in range(1, RMAX + 1) if (0, br) in PS} QS = {br: step_of(q) for br, q in Q.items()}; QT = {br: step_of(q, iH) for br, q in Q.items()} def psi(r): acc = zeros_pl() for br in range(1, r + 1): sign = (-1) ** r * (-1) ** (1 + br); comp = r - br if br not in Q: continue if comp == 0: X = pl_trunc(Q[br], iH) else: if (0, comp) not in PS: continue X = conv_sn(QT[br], PS[(0, comp)]) acc = pl_add(acc, X, sign) for br in range(2, r + 1): sign = (-1) ** r * (-1) ** br; comp = r - br T = MB.trunc_step((0, br)) if T is None: continue X = conv_sn(SH, T) if comp == 0 else conv_sn(QS[comp], T) acc = pl_add(acc, X, sign) return pl_trunc(acc, iH) SPSI = zeros_pl() for r in range(1, RMAX + 1): SPSI = pl_add(SPSI, psi(r)) log("Psi done") # h-part of T0 and f(1) T0h = (0, 0) for k in range(2, RMAX + 1): if k in Q: T0h = add_iv(T0h, at1(Q[k]), (-1) ** (1 + k)) T0h = add_iv(T0h, at1(SPSI), -1) SP0 = step_of(SPHI0, iH) KBMAX = 0 while (KBMAX + 1) * ALPHA < Fr(1, 2): KBMAX += 1 for kb in range(0, KBMAX + 1): if kb == 0: X = conv_ss(SP0, SH) else: if kb not in QS: continue X = conv_ss(SP0, QS[kb]) T0h = add_iv(T0h, at1(X), (-1) ** kb) SPS = step_of(SPSI, iH) for kb in range(1, KBMAX + 1): X = conv_sn(SPS, PS[(0, kb)]); T0h = add_iv(T0h, at1(X), (-1) ** (1 + kb)) f1h = at1(SPSI) T0 = add_iv(T0c, T0h) assert T0g[0] > 0 or T0g[1] < 0 tiv = iv_div((-T0[1], -T0[0]), T0g) F1c = add_iv(f1c, f1h) F1 = add_iv(F1c, iv_mul(tiv, f1g)) 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}]") assert F1[1] < 0 # ---------------------------------------------------------------- positivity def class_total_range(j, k, b): """open interval of totals of free (sub)vectors with j small, k rough, max rough in bin b (b = 0 iff k = 0)""" if k == 0: return (j * ETA, j * ALPHA) lo_b, hi_b = EDGES[b - 1], EDGES[b] return (j * ETA + (k - 1) * ALPHA + lo_b, j * ALPHA + k * hi_b) def realisable_free(j, k, b): lo, hi = class_total_range(j, k, b) return lo < 1 < hi if k >= 1 else (lo < 1 < hi) SCALEt = (tiv[0], tiv[1]) free_min = 0; free_arg = None for j in range(0, SMAX + 1): for k in range(0, RMAX + 1): for b in ([0] if k == 0 else range(1, NB + 1)): if not realisable_free(j, k, b): continue v = C.get((j, k, b), Fr(0)) lo = fl(v.numerator * SCALE, v.denominator) if (j, k, b) == GCLS: lo += min(0, tiv[0]) if j == 1: lo += hmin if lo < free_min: free_min, free_arg = lo, (j, k, b) log(f"free min >= {fz(free_min):+.5f} at {free_arg}") ext_min = 0; ext_arg = None for jb in range(0, SMAX + 1): for kb in range(0, KBMAX + 1): for bb in ([0] if kb == 0 else range(1, NB + 1)): if (jb, kb) == (0, 0): continue tlo, thi = class_total_range(jb, kb, bb) if tlo >= Fr(1, 2): continue terms = [HB[(jb, kb, b)] for b in range(max(bb, 1), NB + 1) if (jb, kb, b) in HB] gterms = [HBG[(jb, kb, b)] for b in range(max(bb, 1), NB + 1) if (jb, kb, b) in HBG] if not terms and not gterms and jb > 1: continue 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 br = (0, 0) for t_ in terms: br = add_iv(br, cell_at(t_, n)) for t_ in gterms: br = add_iv(br, iv_mul(tiv, cell_at(t_, n))) if jb == 1: br = add_iv(br, iv_mul((hmin, hmax), cell_at(SPHI0, n))) if jb == 0: br = add_iv(br, cell_at(SPSI, n)) val = iv_mul((fl(SCALE * n, M), ce(SCALE * (n + 1), M)), br) if val[0] < ext_min: ext_min, ext_arg = val[0], (jb, kb, bb, n / M) log(f"extended min >= {fz(ext_min):+.5f} at (jb, kb, b_beta, a) = {ext_arg}") 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 = dict(M=M, tag=TAG, pickle_sha256=PKL_SHA, edges=[str(e) for e in EDGES], classes={str(k): str(v) for k, v in C.items()}, g=str(GCLS), B=[str(Fr(Bmin, SCALE)), str(Fr(Bmax, SCALE))], h=[str(Fr(hmin, SCALE)), str(Fr(hmax, SCALE))], T0c=[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))], free_min=str(Fr(free_min, SCALE)), free_arg=str(free_arg), ext_min=str(Fr(ext_min, SCALE)), ext_arg=str(ext_arg), untwisted_dp_cells_not_containing_0=[nbA, nbB], verdict=verdict, margin=str(margin), seconds=round(time.time() - T_START, 1)) json.dump(out, open(f'certb_{TAG}_M{M}.json', 'w'), indent=1) log("wrote", f"certb_{TAG}_M{M}.json")