# Sources of the computations in thmB/ The programs that produced the outputs in `outputs_thmB.log` (the two separately written programs of the audit, a copy of one of them, `independent_p1_k8.py`, and a third, separately written program, `k8_bound.py`, the last two written and run after the audit), and the two input files that `exact_certificate.py` reads, verbatim except as stated for each. For each program two hashes are given: "as run" is the SHA-256 of the file that produced the outputs (provenance); "as shipped" is the SHA-256 of the text below (integrity), which `unpack.py` checks. Parsed with docstrings dropped, each shipped program is identical to the program as run with the path change listed for it. The input files are shipped byte for byte; the runs did not record their hashes, and the files were not modified after the runs. #### file: exact_certificate.py - kind: script - as run: SHA-256 1397bab2c0b24e2fdbf0ed535d2f49a557510bf343acaeb30f6ef14606160d4a - as shipped: SHA-256 7e0361989102cf56d7cb9d6bb34a881a0ae7175e846f31519810d956c1c0930b - identity: identical, after dropping docstrings and comments, to the file as run with 1 declared change(s) of a machine-specific path, which now read: `SOURCE = Path(__file__).resolve().parent` - trailing newline: yes ~~~~~~~~~~~~ python #!/usr/bin/env python3 """Exact-integer, outward-rounded P0 certificate, written independently. Every function bound is an integer divided by SCALE. The mesh is exactly 1/N. Nonnegative convolutions are exact polynomial products: coefficients are packed in base 256**width, where width is chosen to preclude all carries. Python's arbitrary-precision integer multiplication is exact. All subsequent divisions are rounded outwards. The 2 by 2 perturbation argument uses Fraction throughout. This certifies the reported c boxes OFF the exceptional vector (1/2,1/2), and separately encloses that vector, which is removed by FM's strip modification. The decimal JSON constants are treated as exact finite decimals. """ import argparse from dataclasses import dataclass from fractions import Fraction as Q import json from pathlib import Path import random SCALE = 10**18 SOURCE = Path(__file__).resolve().parent def ceildiv(a,b): return -((-a)//b) def floorq(x): return x.numerator//x.denominator def ceilq(x): return ceildiv(x.numerator,x.denominator) def pack_convolution(a,b,length): assert min(a)>=0 and min(b)>=0 bound = min(len(a),len(b))*max(a)*max(b) if bound == 0: return [0]*length width = max(1,(bound.bit_length()+7)//8) assert 256**width > bound aa = int.from_bytes(b''.join(x.to_bytes(width,'little') for x in a),'little') bb = int.from_bytes(b''.join(x.to_bytes(width,'little') for x in b),'little') product = (aa*bb).to_bytes((len(a)+len(b))*width,'little') return [int.from_bytes(product[i*width:(i+1)*width],'little') for i in range(length)] def test_packing(): rng=random.Random(137) for n in [1,2,7,31]: a=[rng.randrange(10**18) for _ in range(n)] b=[rng.randrange(10**18) for _ in range(n)] expected=[sum(a[i]*b[k-i] for i in range(n) if 0<=k-ihalf else [half] worst=None for a in cells: lower=upper=0 for col,k in enumerate(ks): if k-j<2: continue il,iu=I[k-j].lo[a],I[k-j].hi[a] products=[cl[col]*il,cl[col]*iu,ch[col]*il,ch[col]*iu] lower+=min(products) upper+=max(products) right=a+1 if end>half else a bound=min(a*lower,right*lower,a*upper,right*upper)//(N*S) if worst is None or bound-S minima.append(dict(j=j,lower_scaled=worst[0],a_cell=worst[1], lower=float(Q(worst[0],S)))) # The genuinely distinct two-large-component vector. lower=upper=0 for col,k in enumerate(ks): rowlo=rowhi=0 for r in range(2,k-1): rowlo+=H[r].lo[half]*H[k-r].lo[half] rowhi+=H[r].hi[half]*H[k-r].hi[half] products=[cl[col]*rowlo,cl[col]*rowhi,ch[col]*rowlo,ch[col]*rowhi] lower+=min(products) upper+=max(products) halfbox=[lower//(4*S*S),ceildiv(upper,4*S*S)] if den==11: assert halfbox[1]<-S assert min(cl)>-S result=dict(eta=f'1/{den}',N=N,scale=S, p_intervals_scaled=p,t_intervals_scaled=t, type_I_intervals_scaled=mass, c3_c4_solution_box_scaled=exact_box, c3_c4_solution_box=[[float(Q(v,S)) for v in pair] for pair in exact_box], solution_box_inside_original_JSON=True, perturbation_row_norm=str(norm),perturbation_row_norm_float=float(norm), original_c_lo_scaled=cl,original_c_hi_scaled=ch, min_free=float(Q(min(cl),S)),extended_minima=minima, min_extended_lower=min(x['lower'] for x in minima), two_half_interval_scaled=halfbox, two_half_interval=[float(Q(v,S)) for v in halfbox], verdict='EXACTLY CERTIFIED OFF (1/2,1/2); strip modification required') Path(f'exact_eta{den}_N{N}.json').write_text(json.dumps(result,indent=2)+'\n') return result if __name__=='__main__': p=argparse.ArgumentParser() p.add_argument('--eta',type=int,nargs='+',default=[12,11]) args=p.parse_args() test_packing() for den in args.eta: N=4800 if den==12 else 4400 result=certificate(den,N) print(json.dumps(result),flush=True) ~~~~~~~~~~~~ #### file: independent_p1.py - kind: script - as run: SHA-256 95f6bd2389bf3592495d0552849f7933f25b89dec6b79c45a8f8713565fea221 - as shipped: SHA-256 95f6bd2389bf3592495d0552849f7933f25b89dec6b79c45a8f8713565fea221 - identity: identical, after dropping docstrings and comments, to the file as run - trailing newline: yes ~~~~~~~~~~~~ python #!/usr/bin/env python3 """Independent P1/P2 quadrature, exact enclosures, and shape checks. Float calculation: integrated recurrence s H_k(s)=int_0^(s-nu) H_{k-1}. Exact calculation: rational step bounds, integer polynomial products, outward integer divisions. No NumPy arithmetic participates in an exact certificate. All output files are in the current run directory. """ import argparse from fractions import Fraction as Q import itertools import json import math from pathlib import Path import numpy as np from scipy.integrate import cumulative_trapezoid from exact_certificate import pack_convolution, ceildiv, test_packing S = 10**18 def quadrature(num, den, N): assert N % den == 0 shift = num*N//den nu = num/den x = np.arange(N+1)/N h = np.zeros(N+1) mask = x > 2*nu h[mask] = np.log((x[mask]-nu)/nu)/x[mask] vals = {2: float(h[-1])} for k in range(3, 9): primitive = cumulative_trapezoid(h, x, initial=0) h = np.zeros(N+1) h[shift:] = primitive[:N+1-shift]/x[shift:] h[:k*shift+1] = 0 vals[k] = float(h[-1]) lower = 1-2*vals[4]-4*vals[5]-20*vals[6]/3-25*vals[7]/3 return dict(nu=f'{num}/{den}', N=N, I=vals, bound_float=lower) def exact(num, den, N): assert N % den == 0 shift = num*N//den lo1, hi1 = [0]*N, [0]*N for i in range(shift, N-shift): lo1[i] = (N*S)//(i+1) hi1[i] = ceildiv(N*S, i) lo, hi = lo1[:], hi1[:] vals = {} for k in range(2, 9): # Arrays represent H_{k-1}=f^{*(k-1)}/(k-1)!, hence divide by k. if k*num >= den: vals[k] = [0,0] # Exact empty support, including endpoint equality. continue low = [0]+[v//(N*S*k) for v in pack_convolution(lo,lo1,N)] high = [0]+[ceildiv(v,N*S*k) for v in pack_convolution(hi,hi1,N)] vals[k] = [low[-1],high[-1]] lo = [min(low[i],low[i+1]) for i in range(N)] hi = [max(high[i],high[i+1]) for i in range(N)] # True support begins at k nu; remove cell-bound support leakage. lo[:k*shift] = [0]*(k*shift) hi[:k*shift] = [0]*(k*shift) lower = Q(1)-sum(c*Q(vals[k][1],S) for k,c in [(4,Q(2)),(5,Q(4)),(6,Q(20,3)),(7,Q(25,3))]) out = dict(nu=f'{num}/{den}',N=N,scale=S,I_scaled=vals, I_display={k:[float(Q(z,S)) for z in v] for k,v in vals.items()}, lower_exact=str(lower),lower_display=float(lower), lower_decimal_floor_6=str(Q((lower*10**6).numerator//(lower*10**6).denominator,10**6))) Path(f'exact_p1_{num}_{den}_N{N}.json').write_text(json.dumps(out,indent=2)+'\n') return out def G(x): k=len(x) N1=sum(v<=Q(1,2) for v in x) N2=sum(x[i]+x[j]<=Q(1,2) for i in range(k) for j in range(i+1,k)) return Q(1)-Q(N1+N2,2)-Q((-1)**k,2) def sampling(): rng=np.random.default_rng(7132026) report=[] for nu in [.126,.13,1/7,.15,.20,.24,.25,.27,.32]: for k in range(2,8): if k*nu>=1: continue xx=nu+(1-k*nu)*rng.dirichlet(np.ones(k),size=30000) inside=np.all(((xx>nu)&(xx<1-2*nu))|((xx>2*nu)&(xx<1-nu)),axis=1) xx=xx[inside] if not len(xx): continue n1=(xx<=.5).sum(axis=1) n2=sum((xx[:,i]+xx[:,j]<=.5).astype(int) for i in range(k) for j in range(i+1,k)) gg=1-(n1+n2)/2-(-1)**k/2 assert gg.max()<=0 expected={2:0,3:0,4:-3,5:-6,6:-10,7:-12.5}[k] assert gg.min()>=expected report.append(dict(nu=nu,k=k,samples=len(xx),min=float(gg.min()),max=float(gg.max()))) boundaries = [tuple([Q(1,2)]*2),(Q(1,2),Q(1,4),Q(1,4)), tuple([Q(1,4)]*4),(Q(3,20),Q(1,5),Q(3,10),Q(7,20))] ties=[dict(x=list(map(str,x)),G=str(G(x))) for x in boundaries] assert G(boundaries[0])==Q(-1,2) assert G(boundaries[1])==Q(-1,2) assert G(boundaries[2])==Q(-9,2) assert G(boundaries[3])==Q(-7,2) # Also exhaust every positive rational composition with each part > 1/8, # denominators 16, 20, 24, 28, 32. Nondecreasing order avoids duplicates. exhaustive_count=0 repeated_count=0 minima={} def partitions(total,k,start): if k==1: if total>=start: yield (total,) else: for a in range(start,total//k+1): for tail in partitions(total-a,k-1,a): yield (a,)+tail for den in [16,20,24,28,32]: for k in range(2,8): for parts in partitions(den,k,den//8+1): xx=tuple(Q(a,den) for a in parts) gg=G(xx) assert gg<=0 exhaustive_count+=1 minima[k]=min(minima.get(k,Q(0)),gg) groups=[(a,len(list(b))) for a,b in itertools.groupby(xx)] if any(e>=2 for a,e in groups): repeated_count+=1 d1=sum(a<=Q(1,2) for a,e in groups) d2=0 for counts in itertools.product(*(range(e+1) for a,e in groups)): if sum(counts)==2 and sum(t*a for t,(a,e) in zip(counts,groups))<=Q(1,2): d2+=1 ordinary=1-Q(d1+d2,2) if len(groups)==1 and k in [2,3]: assert ordinary==Q(1,2) else: assert ordinary<=0 return dict(seed=7132026,random=report,total_samples=sum(x['samples'] for x in report), boundary_checks=ties,exhaustive_count=exhaustive_count, repeated_factor_ordinary_divisor_checks=repeated_count, exact_grid_minima={k:str(v) for k,v in minima.items()}) def main(): parser=argparse.ArgumentParser() parser.add_argument('--exact',action='store_true') args=parser.parse_args() if args.exact: test_packing() for num,den,N in [(3,20,8000),(1,7,9800)]: print(json.dumps(exact(num,den,N)),flush=True) else: data=dict(quadrature=[quadrature(num,den,N) for num,den in [(3,20),(1,7)] for N in [28000,56000,112000]],sampling=sampling()) Path('independent_p1_results.json').write_text(json.dumps(data,indent=2)+'\n') print(json.dumps(data),flush=True) if __name__=='__main__': main() ~~~~~~~~~~~~ #### file: independent_p1_k8.py - kind: script (a copy of independent_p1.py, written and run after the audit, that adds the term in I_8 to the bound and leaves the enclosure arithmetic unchanged; it imports exact_certificate.py) - as run: SHA-256 cefee740fe0b156ac1503ba9fd4aa95b30ecc9b666ca083bd015cba60b7d2c9b - as shipped: SHA-256 cefee740fe0b156ac1503ba9fd4aa95b30ecc9b666ca083bd015cba60b7d2c9b - identity: the file as run, byte for byte - trailing newline: yes ~~~~~~~~~~~~ python #!/usr/bin/env python3 """Independent P1/P2 quadrature, exact enclosures, and shape checks. Float calculation: integrated recurrence s H_k(s)=int_0^(s-nu) H_{k-1}. Exact calculation: rational step bounds, integer polynomial products, outward integer divisions. No NumPy arithmetic participates in an exact certificate. All output files are in the current run directory. k8 copy (14 Nov 2026): a copy of the supplement's independent_p1.py (thmB/), changed only to add the dimension-8 term -(35/3) I_8 to the lower bound, for 1/9 <= nu < 1/8 (Phi >= -35/2 in dimension 8: N1 <= 8, N2 <= 28; times 1/(1-c) = 2/3). Dimensions 9 and up do not occur when 9 nu >= 1, which exact() asserts. With c8 = 0, exact() writes the original's output (same dict, same file name). The enclosure arithmetic is untouched. """ import argparse from fractions import Fraction as Q import itertools import json import math from pathlib import Path import numpy as np from scipy.integrate import cumulative_trapezoid from exact_certificate import pack_convolution, ceildiv, test_packing S = 10**18 def quadrature(num, den, N): assert N % den == 0 shift = num*N//den nu = num/den x = np.arange(N+1)/N h = np.zeros(N+1) mask = x > 2*nu h[mask] = np.log((x[mask]-nu)/nu)/x[mask] vals = {2: float(h[-1])} for k in range(3, 9): primitive = cumulative_trapezoid(h, x, initial=0) h = np.zeros(N+1) h[shift:] = primitive[:N+1-shift]/x[shift:] h[:k*shift+1] = 0 vals[k] = float(h[-1]) lower = 1-2*vals[4]-4*vals[5]-20*vals[6]/3-25*vals[7]/3 lower_k8 = lower-35*vals[8]/3 return dict(nu=f'{num}/{den}', N=N, I=vals, bound_float=lower, bound_float_k8=lower_k8) def exact(num, den, N, c8=Q(35,3)): assert N % den == 0 assert 9*num >= den # no dimension 9 or more: the formula below stops at k = 8 shift = num*N//den lo1, hi1 = [0]*N, [0]*N for i in range(shift, N-shift): lo1[i] = (N*S)//(i+1) hi1[i] = ceildiv(N*S, i) lo, hi = lo1[:], hi1[:] vals = {} for k in range(2, 9): # Arrays represent H_{k-1}=f^{*(k-1)}/(k-1)!, hence divide by k. if k*num >= den: vals[k] = [0,0] # Exact empty support, including endpoint equality. continue low = [0]+[v//(N*S*k) for v in pack_convolution(lo,lo1,N)] high = [0]+[ceildiv(v,N*S*k) for v in pack_convolution(hi,hi1,N)] vals[k] = [low[-1],high[-1]] lo = [min(low[i],low[i+1]) for i in range(N)] hi = [max(high[i],high[i+1]) for i in range(N)] # True support begins at k nu; remove cell-bound support leakage. lo[:k*shift] = [0]*(k*shift) hi[:k*shift] = [0]*(k*shift) lower = Q(1)-sum(c*Q(vals[k][1],S) for k,c in [(4,Q(2)),(5,Q(4)),(6,Q(20,3)),(7,Q(25,3)),(8,Q(c8))]) out = dict(nu=f'{num}/{den}',N=N,scale=S,I_scaled=vals, I_display={k:[float(Q(z,S)) for z in v] for k,v in vals.items()}, lower_exact=str(lower),lower_display=float(lower), lower_decimal_floor_6=str(Q((lower*10**6).numerator//(lower*10**6).denominator,10**6))) if Q(c8) == 0: # Original mode: the original's dict and file name, so the output can be compared byte for byte. Path(f'exact_p1_{num}_{den}_N{N}.json').write_text(json.dumps(out,indent=2)+'\n') return out out['k8_coefficient'] = str(Q(c8)) out['formula'] = '1 - 2 I4 - 4 I5 - (20/3) I6 - (25/3) I7 - (' + str(Q(c8)) + ') I8, each I_k at its upper enclosure' out['lower_decimal_floor_10'] = str(Q((lower*10**10).numerator//(lower*10**10).denominator,10**10)) Path(f'exact_p1_k8_{num}_{den}_N{N}.json').write_text(json.dumps(out,indent=2)+'\n') return out def G(x): k=len(x) N1=sum(v<=Q(1,2) for v in x) N2=sum(x[i]+x[j]<=Q(1,2) for i in range(k) for j in range(i+1,k)) return Q(1)-Q(N1+N2,2)-Q((-1)**k,2) def sampling(): rng=np.random.default_rng(7132026) report=[] for nu in [.126,.13,1/7,.15,.20,.24,.25,.27,.32]: for k in range(2,8): if k*nu>=1: continue xx=nu+(1-k*nu)*rng.dirichlet(np.ones(k),size=30000) inside=np.all(((xx>nu)&(xx<1-2*nu))|((xx>2*nu)&(xx<1-nu)),axis=1) xx=xx[inside] if not len(xx): continue n1=(xx<=.5).sum(axis=1) n2=sum((xx[:,i]+xx[:,j]<=.5).astype(int) for i in range(k) for j in range(i+1,k)) gg=1-(n1+n2)/2-(-1)**k/2 assert gg.max()<=0 expected={2:0,3:0,4:-3,5:-6,6:-10,7:-12.5}[k] assert gg.min()>=expected report.append(dict(nu=nu,k=k,samples=len(xx),min=float(gg.min()),max=float(gg.max()))) boundaries = [tuple([Q(1,2)]*2),(Q(1,2),Q(1,4),Q(1,4)), tuple([Q(1,4)]*4),(Q(3,20),Q(1,5),Q(3,10),Q(7,20))] ties=[dict(x=list(map(str,x)),G=str(G(x))) for x in boundaries] assert G(boundaries[0])==Q(-1,2) assert G(boundaries[1])==Q(-1,2) assert G(boundaries[2])==Q(-9,2) assert G(boundaries[3])==Q(-7,2) # Also exhaust every positive rational composition with each part > 1/8, # denominators 16, 20, 24, 28, 32. Nondecreasing order avoids duplicates. exhaustive_count=0 repeated_count=0 minima={} def partitions(total,k,start): if k==1: if total>=start: yield (total,) else: for a in range(start,total//k+1): for tail in partitions(total-a,k-1,a): yield (a,)+tail for den in [16,20,24,28,32]: for k in range(2,8): for parts in partitions(den,k,den//8+1): xx=tuple(Q(a,den) for a in parts) gg=G(xx) assert gg<=0 exhaustive_count+=1 minima[k]=min(minima.get(k,Q(0)),gg) groups=[(a,len(list(b))) for a,b in itertools.groupby(xx)] if any(e>=2 for a,e in groups): repeated_count+=1 d1=sum(a<=Q(1,2) for a,e in groups) d2=0 for counts in itertools.product(*(range(e+1) for a,e in groups)): if sum(counts)==2 and sum(t*a for t,(a,e) in zip(counts,groups))<=Q(1,2): d2+=1 ordinary=1-Q(d1+d2,2) if len(groups)==1 and k in [2,3]: assert ordinary==Q(1,2) else: assert ordinary<=0 return dict(seed=7132026,random=report,total_samples=sum(x['samples'] for x in report), boundary_checks=ties,exhaustive_count=exhaustive_count, repeated_factor_ordinary_divisor_checks=repeated_count, exact_grid_minima={k:str(v) for k,v in minima.items()}) def main(): parser=argparse.ArgumentParser() parser.add_argument('--exact',action='store_true') parser.add_argument('--point',action='append',default=[], help='NUM/DEN:N, exact enclosure with the k = 8 term (repeatable)') parser.add_argument('--c8',default='35/3',help='coefficient of I_8 for --point runs (0 = original mode)') parser.add_argument('--quad',action='append',default=[], help='NUM/DEN, float quadrature at N = 28000, 56000, 112000 (repeatable)') args=parser.parse_args() if args.point or args.quad: test_packing() for p in args.point: nd,N=p.split(':') num,den=map(int,nd.split('/')) print(json.dumps(exact(num,den,int(N),Q(args.c8))),flush=True) if args.quad: data=[quadrature(*map(int,nd.split('/')),N) for nd in args.quad for N in [28000,56000,112000]] Path('quadrature_k8.json').write_text(json.dumps(data,indent=2)+'\n') print(json.dumps(data),flush=True) elif args.exact: test_packing() for num,den,N in [(3,20,8000),(1,7,9800)]: print(json.dumps(exact(num,den,N)),flush=True) else: data=dict(quadrature=[quadrature(num,den,N) for num,den in [(3,20),(1,7)] for N in [28000,56000,112000]],sampling=sampling()) Path('independent_p1_results.json').write_text(json.dumps(data,indent=2)+'\n') print(json.dumps(data),flush=True) if __name__=='__main__': main() ~~~~~~~~~~~~ #### file: k8_bound.py - kind: script (written separately, after the audit, without sight of the code of the other three programs; it needs python-flint, and numpy for its floating-point channel C) - as run: SHA-256 850d7afdcafcc333f19bd7420f189e25383a0257031cf41493c6e153ec54ebaf - as shipped: SHA-256 45f31139a3df753e5f31423573fd7d9c358f43cd870b1836a97a0f1bcc9688e2 - identity: identical, after dropping docstrings and comments, to the file as run (its module docstring was rewritten without internal names) - trailing newline: yes ~~~~~~~~~~~~ python #!/usr/bin/env python3 """ k8_bound.py -- independent rigorous enclosure of the right-hand side of Theorem B(a) of the paper (its section on Theorem B: Proposition prop:sieve-parity and the proof of part (a)), extended by the k = 8 term: B(nu) = 1 - 2 I_4 - 4 I_5 - (20/3) I_6 - (25/3) I_7 - (35/3) I_8, I_k(nu) = (1/k!) * int_{x_i > nu, x_1+...+x_k = 1} dx_1...dx_{k-1} / (x_1...x_k) (= 0 if k nu >= 1). The coefficient of I_k is (1/(1-c)) * |min Phi on dimension k| with c = -1/2, so 2/3 * (3, 6, 10, 25/2, 35/2). For k = 8, Phi = 1 - N1/2 - N2/2 - 1/2 >= 1/2 - 8/2 - 28/2 = -35/2. I_9 = 0 for nu >= 1/9, which covers both target nu. Written from the paper and the method description in the supplement's README only; no code of the supplement's thmB/ (independent_p1.py, exact_certificate.py) or of the copy independent_p1_k8.py was read. Let f(x) = 1_{x > nu} / x on (0, 1] and F_k = f * ... * f (k-fold). Then I_k = F_k(1) / k!. Mesh step h = 1/N with nu = m0/N exactly. Everything is an integer at scale S = 10^18 (value * S), divisions rounded outward. CHANNEL A (convolution; exact integer polynomial products, python-flint fmpz_poly): cell j = [j h, (j+1) h). flo_j = floor(S N/(j+1)), fhi_j = ceil(S N/j) for j >= m0, else 0 (f a.e. in [flo_j, fhi_j]/S on cell j). U_k[m], L_k[m]: bounds of S*F_k(t) valid for EVERY t in cell m. For t = (m + a) h, 0 <= a < 1: F_k(t) = sum_j int_{cell j} f(x) F_{k-1}(t-x) dx and the window of t - x for x in cell j covers a fraction (1-a) of cell m-j-1 and a of cell m-j, so with P = fhi * U_{k-1} (polynomial product) F_k(t) <= (h/S^2) [ (1-a) P_{m-1} + a P_m ] <= (h/S^2) max(P_{m-1}, P_m), and likewise from below with Q = flo * L_{k-1} and min. Cells with (m+1) <= k m0 lie in t < k nu, where F_k = 0. At t = 1 (m = N, a = 0): Q_{N-1} / (N S^2) <= F_k(1) <= P_{N-1} / (N S^2). CHANNEL B (integral recurrence; plain integer cumulative sums, no convolution): G_k = F_k / k! satisfies t G_k(t) = int_0^{t-nu} G_{k-1}(s) ds (multiply F_k by t = sum x_i and use symmetry). H_{k-1}(u) = int_0^u G_{k-1} is nondecreasing, so for t in cell m: Hlo(m-m0)/(m+1) <= S N ... (see code), and I_k = G_k(1) = H_{k-1}(1 - nu) in [Hlo(N-m0), Hhi(N-m0)] / (S N). CHANNEL C (floating point, NOT part of any bound): trapezoid version of the recurrence, for comparison only. Each fmpz_poly product is checked against the definition: exact evaluation of A(r) B(r) - P(r) modulo two 61-bit primes at random r, and the coefficient that gives F_k(1) is recomputed as a plain Python integer dot product. """ import sys, json, time, random, math from fractions import Fraction from itertools import accumulate import flint S = 10**18 COEF = {4: Fraction(2), 5: Fraction(4), 6: Fraction(20, 3), 7: Fraction(25, 3), 8: Fraction(35, 3)} KMAX = 8 PRIMES = [(1 << 61) - 1, 2305843009213693921] # 2^61-1 (Mersenne prime) and another 61-bit prime, checked below RNG = random.Random(20261114) def ceil_div(a, b): return -((-a) // b) def is_probable_prime(n): return flint.fmpz(n).is_prime() def horner_mod(coeffs, r, p): acc = 0 for c in reversed(coeffs): acc = (acc * r + c) % p return acc def check_product(A, B, P, N, tag, log): """A, B: python int lists; P: python int list of the claimed product. Exact modular evaluation check + one direct coefficient.""" for p in PRIMES: r = RNG.randrange(2, p - 1) lhs = (horner_mod(A, r, p) * horner_mod(B, r, p)) % p rhs = horner_mod(P, r, p) if lhs != rhs: raise SystemExit(f"PRODUCT CHECK FAILED {tag} mod {p}") i = N - 1 direct = sum(A[j] * B[i - j] for j in range(max(0, i - len(B) + 1), min(i, len(A) - 1) + 1)) if direct != P[i]: raise SystemExit(f"DIRECT COEFFICIENT CHECK FAILED {tag}") # a few random coefficients as well for _ in range(3): i = RNG.randrange(0, len(P)) direct = sum(A[j] * B[i - j] for j in range(max(0, i - len(B) + 1), min(i, len(A) - 1) + 1)) if direct != P[i]: raise SystemExit(f"DIRECT COEFFICIENT CHECK FAILED {tag} at {i}") log.append(f"product check ok: {tag}") def f_images(N, m0): SN = S * N flo = [0] * N fhi = [0] * N for j in range(m0, N): flo[j] = SN // (j + 1) fhi[j] = ceil_div(SN, j) return flo, fhi def polymul(A, B): P = flint.fmpz_poly(A) * flint.fmpz_poly(B) c = [int(x) for x in P.coeffs()] return c def channel_A(N, m0, log, check=True): """returns {k: (num_lo, num_hi)} with num_lo/(N S^2 k!) <= I_k <= num_hi/(N S^2 k!)""" flo, fhi = f_images(N, m0) U, L = fhi[:], flo[:] # F_1 = f out = {} NS = N * S for k in range(2, KMAX + 1): t0 = time.time() if k * m0 >= N: # k nu >= 1: I_k = 0 exactly (empty slice); the mesh bound gives 0 too, recorded as exact 0 out[k] = (0, 0) # sanity: the mesh bound must also give 0 here i = N - 1 ph = sum(fhi[j] * U[i - j] for j in range(0, i + 1)) if ph != 0: raise SystemExit(f"support inconsistency at k={k}") log.append(f"A k={k}: k*m0 >= N, I_k = 0 (mesh upper bound also 0)") continue last = (k == KMAX) P = polymul(fhi, U) Q = polymul(flo, L) if check: check_product(fhi, U, P, N, f"A N={N} k={k} upper", log) check_product(flo, L, Q, N, f"A N={N} k={k} lower", log) P += [0] * max(0, N - len(P)) Q += [0] * max(0, N - len(Q)) out[k] = (Q[N - 1], P[N - 1]) if not last: Un = [0] * N Ln = [0] * N start = k * m0 # cells m <= k m0 - 1 lie in t < k nu for m in range(start, N): pm1 = P[m - 1] if m >= 1 else 0 qm1 = Q[m - 1] if m >= 1 else 0 Un[m] = ceil_div(max(pm1, P[m]), NS) Ln[m] = min(qm1, Q[m]) // NS U, L = Un, Ln log.append(f"A N={N} k={k} done in {time.time()-t0:.1f}s") return out def channel_B(N, m0, log): """returns {k: (num_lo, num_hi)} with num_lo/(S N) <= I_k <= num_hi/(S N)""" flo, fhi = f_images(N, m0) Glo, Ghi = flo, fhi out = {} for k in range(2, KMAX + 1): Hlo = [0] + list(accumulate(Glo)) # Hlo[i] = sum_{m= N: out[k] = (0, 0) if Hhi[N - m0] != 0: raise SystemExit(f"B support inconsistency at k={k}") continue out[k] = (Hlo[N - m0], Hhi[N - m0]) if k < KMAX: nGlo = [0] * N nGhi = [0] * N for m in range(max(m0, 1), N): nGhi[m] = ceil_div(Hhi[m - m0 + 1], m) nGlo[m] = Hlo[m - m0] // (m + 1) Glo, Ghi = nGlo, nGhi return out def channel_C(nu_num, nu_den, N): """floating point trapezoid recurrence; NOT rigorous; comparison only""" import numpy as np m0 = N * nu_num // nu_den h = 1.0 / N t = np.arange(N + 1) * h G = np.zeros(N + 1) G[m0 + 1:] = 1.0 / t[m0 + 1:] G[m0] = 0.5 / t[m0] res = {} for k in range(2, KMAX + 1): H = np.concatenate([[0.0], np.cumsum((G[1:] + G[:-1]) * h / 2)]) Gn = np.zeros(N + 1) Gn[m0:] = H[:N + 1 - m0] / np.where(t[m0:] > 0, t[m0:], 1) G = Gn res[k] = float(G[N]) return res def bound_from(Ilo, Ihi): lo = Fraction(1) - sum(COEF[k] * Ihi[k] for k in COEF) hi = Fraction(1) - sum(COEF[k] * Ilo[k] for k in COEF) paper_lo = Fraction(1) - sum(COEF[k] * Ihi[k] for k in COEF if k <= 7) # paper's formula, no k = 8 term paper_hi = Fraction(1) - sum(COEF[k] * Ilo[k] for k in COEF if k <= 7) return lo, hi, paper_lo, paper_hi def dec_down(x, d=10): return f"{math.floor(x * 10**d)}" if False else str(Fraction(math.floor(x * 10**d), 10**d)) def fmt_floor(x, d=10): n = math.floor(x * 10**d) s = f"{abs(n):0{d+1}d}" return ("-" if n < 0 else "") + s[:-d] + "." + s[-d:] def fmt_ceil(x, d=10): n = -math.floor(-x * 10**d) s = f"{abs(n):0{d+1}d}" return ("-" if n < 0 else "") + s[:-d] + "." + s[-d:] def run(nu_num, nu_den, N, channels, check=True): assert (N * nu_num) % nu_den == 0, "nu must be a mesh point" m0 = N * nu_num // nu_den log = [] rec = {"nu": f"{nu_num}/{nu_den}", "N": N, "m0": m0, "S": S} for p in PRIMES: assert is_probable_prime(p) if "A" in channels: t0 = time.time() a = channel_A(N, m0, log, check=check) Ilo = {k: Fraction(a[k][0], N * S * S * math.factorial(k)) for k in a} Ihi = {k: Fraction(a[k][1], N * S * S * math.factorial(k)) for k in a} lo, hi, plo, phi = bound_from(Ilo, Ihi) rec["A"] = {"secs": round(time.time() - t0, 1), "I": {k: [fmt_floor(Ilo[k], 14), fmt_ceil(Ihi[k], 14)] for k in a}, "B_lo_exact": f"{lo.numerator}/{lo.denominator}", "B_lo_dec_down": fmt_floor(lo), "B_hi_dec_up": fmt_ceil(hi), "paperformula_lo_dec_down": fmt_floor(plo), "paperformula_hi_dec_up": fmt_ceil(phi), "k8_term_hi_dec_up": fmt_ceil(COEF[8] * Ihi[8], 14)} if "B" in channels: t0 = time.time() b = channel_B(N, m0, log) Ilo = {k: Fraction(b[k][0], N * S) for k in b} Ihi = {k: Fraction(b[k][1], N * S) for k in b} lo, hi, plo, phi = bound_from(Ilo, Ihi) rec["B"] = {"secs": round(time.time() - t0, 1), "I": {k: [fmt_floor(Ilo[k], 14), fmt_ceil(Ihi[k], 14)] for k in b}, "B_lo_exact": f"{lo.numerator}/{lo.denominator}", "B_lo_dec_down": fmt_floor(lo), "B_hi_dec_up": fmt_ceil(hi), "paperformula_lo_dec_down": fmt_floor(plo), "paperformula_hi_dec_up": fmt_ceil(phi)} if "C" in channels: c = channel_C(nu_num, nu_den, N) val = 1 - sum(float(COEF[k]) * c[k] for k in COEF) rec["C_float_not_rigorous"] = {"I": {k: c[k] for k in c}, "B": val} rec["log"] = log return rec if __name__ == "__main__": # usage: k8_bound.py nu_num nu_den N channels(e.g. AB or ABC) [nocheck] > out.json nu_num, nu_den, N = int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]) channels = sys.argv[4] check = not (len(sys.argv) > 5 and sys.argv[5] == "nocheck") rec = run(nu_num, nu_den, N, channels, check=check) print(json.dumps(rec, indent=1)) ~~~~~~~~~~~~ #### file: cert_p0_eta11_N4400.json - kind: input (the constants of the construction of Remark 6.1 at eta = 1/11, read by exact_certificate.py) - as run: SHA-256 e0c7b4b532d2dd1f89df26f0d5089b50cde391372f08694ce34ff418b0c5469a - as shipped: SHA-256 e0c7b4b532d2dd1f89df26f0d5089b50cde391372f08694ce34ff418b0c5469a - identity: the file as read, byte for byte - trailing newline: no ~~~~~~~~~~~~ json { "N": 4400, "eta": "1/11", "cutoff": "1/2", "cstar": [ -0.7391755723416993, -0.8358101744849988, 0.31217462420813585, 0.48738063792549907, -0.8296948091041714, 0.4631042941136239, -0.8014777994556567, 0.3756391612127266, -0.6444478482004645 ], "c_lo": [ -0.7527689144825065, -0.8759486299848499, 0.31217462420813585, 0.48738063792549907, -0.8296948091041714, 0.4631042941136239, -0.8014777994556567, 0.3756391612127266, -0.6444478482004645 ], "c_hi": [ -0.7197737680186387, -0.8037934940004737, 0.31217462420813585, 0.48738063792549907, -0.8296948091041714, 0.4631042941136239, -0.8014777994556567, 0.3756391612127266, -0.6444478482004645 ], "min_free": -0.8759486299848499, "min_extended_lower_bound": -0.8990317944809829, "f1_box": [ -1.0408641526976576, -0.9592865520210422 ], "verdict": "CERTIFIED" } ~~~~~~~~~~~~ #### file: cert_p0_eta12_N4800.json - kind: input (the same construction at eta = 1/12, read by exact_certificate.py) - as run: SHA-256 f4bbaca604b13e56b59de620181a97c0345b76bd2e630b03357ab656b3f76cd7 - as shipped: SHA-256 f4bbaca604b13e56b59de620181a97c0345b76bd2e630b03357ab656b3f76cd7 - identity: the file as read, byte for byte - trailing newline: no ~~~~~~~~~~~~ json { "N": 4800, "eta": "1/12", "cutoff": "1/2", "cstar": [ -0.7002766381366258, -0.7200182602728663, 0.33473079440939435, 0.25199072143332457, -0.7108977606400687, 0.2183884277856845, -0.6858104956947514, 0.14279186066545108, -0.5509824908238576, -0.08935054644792369 ], "c_lo": [ -0.7140163892580224, -0.7553990947917341, 0.33473079440939435, 0.25199072143332457, -0.7108977606400687, 0.2183884277856845, -0.6858104956947514, 0.14279186066545108, -0.5509824908238576, -0.08935054644792369 ], "c_hi": [ -0.6816987220055012, -0.6911839194455617, 0.33473079440939435, 0.25199072143332457, -0.7108977606400687, 0.2183884277856845, -0.6858104956947514, 0.14279186066545108, -0.5509824908238576, -0.08935054644792369 ], "min_free": -0.7553990947917341, "min_extended_lower_bound": -0.7791869427182393, "f1_box": [ -1.0411979417391546, -0.9589446467880999 ], "verdict": "CERTIFIED" } ~~~~~~~~~~~~