"""Check the arithmetic and finite prime-pair counts in the paper. Run python3 anc/verify.py. The default run also checks 24 real-arithmetic implications and requires the z3-solver Python package. The exact finite checks alone require only Python 3.9+ (use --incidences-only). Compare the output of a full run with anc/expected-output.log. Run without -O. """ import argparse from fractions import Fraction as F from itertools import combinations from math import factorial, isqrt def small_primes(limit): return tuple(n for n in range(2, limit + 1) if all(n % d for d in range(2, isqrt(n) + 1))) def check_incidence(scale, delta, primes): """Integrate both ways exactly at a rational scale and relative width.""" x = scale**2 left, right = 3 * scale / 2, 2 * scale factor = 1 + delta tall = [p for p in primes if left < p <= factor * right] short = [q for q in primes if x / right < q <= factor * x / left] # First integrate a product of counts on the intervals of constancy. events = {left, right} for p in tall: events.update((p / factor, F(p))) for q in short: events.update((x / q, factor * x / q)) ordered = sorted(t for t in events if left <= t <= right) integrated = F(0) for start, end in zip(ordered, ordered[1:]): t = (start + end) / 2 a = sum(t < p <= factor * t for p in tall) b = sum(x / t < q <= factor * x / t for q in short) integrated += (end - start) * a * b # Then sum intersection lengths for the individual prime pairs. sum_of_lengths = F(0) represented = set() for p in tall: for q in short: lo = max(left, p / factor, x / q) hi = min(right, F(p), factor * x / q) if lo >= hi: continue width = hi - lo assert width <= 2 * delta * scale assert scale / 2 < q < scale < p < 3 * scale assert x < p * q <= factor**2 * x < (1 + 3*delta) * x assert p * q not in represented represented.add(p * q) sum_of_lengths += width assert integrated == sum_of_lengths assert integrated <= 2 * delta * scale * len(represented) return len(represented) def check_finite_cases(): if not __debug__: raise ValueError("Run without -O because the checks use Python assertions.") counted, nonempty, incidences = 0, 0, 0 for scale in (F(5), F(17, 2), F(23), F(79, 3), F(64), F(101)): pool = small_primes(int(3 * scale)) # Thin deterministic patterns test missing primes and correlated gaps. patterns = [pool, pool[::2], pool[1::2], (), pool[:1]] if scale <= 9: patterns.extend(s for k in range(len(pool) + 1) for s in combinations(pool, k)) for primes in patterns: for delta in (F(1, 128), F(1, 9), F(1, 4), F(49, 100)): found = check_incidence(scale, delta, primes) counted += 1 nonempty += int(found > 0) incidences += found print(f"Finite incidence cases: {counted} ({nonempty} nonempty).") print(f"Positive-length prime pairs across all cases: {incidences}.") def check_upper_cover(): """Check the enlarged rectangles, including both product endpoints.""" cases = squares = lower_endpoints = upper_endpoints = pairs = 0 for x in (F(25), F(35), F(49), F(77), F(143), F(221), F(221, 2)): for delta in (F(1, 100), F(1, 5), F(1, 3), F(2, 5)): factor = 1 + delta primes = small_primes(int(factor * x / 2) + 1) for band in (F(3, 2), F(5, 2), F(4), F(6), F(9)): cases += 1 for p in primes: if not band < p <= 2 * band: continue for q in primes: if q < p or not x <= p * q <= factor * x: continue pairs += 1 squares += int(p == q) lower_endpoints += int(p * q == x) upper_endpoints += int(p * q == factor * x) # Positive-length part of both conditions is found # by intersecting their exact endpoint intervals. left = max(band / 2, p / factor, x / (factor * q)) right = min(2 * band, F(p), factor * x / q) assert left == p / factor and right == p assert right - left >= delta * band / 2 assert squares and lower_endpoints and upper_endpoints print(f"Upper-cover band cases: {cases}, with {pairs} pair occurrences.") print(f"Included {squares} squares, {lower_endpoints} lower and " f"{upper_endpoints} upper product endpoints.") def log_bounds(n): """Rational bounds from log n = k log 2 + 2 atanh((n - 2^k)/(n + 2^k)).""" def log_ratio(z): terms = 48 total = 2 * sum(z**(2*j + 1) / (2*j + 1) for j in range(terms)) tail = 2 * z**(2*terms + 1) / ((2*terms + 1) * (1 - z*z)) return total, total + tail k = n.bit_length() - 1 a, b = log_ratio(F(1, 3)) c, d = log_ratio(F(n - 2**k, n + 2**k)) return k*a + c, k*b + d def check_explicit_constants(): """Reconstruct the main numerical bounds directly using rational arithmetic.""" k = 512 mean_square_coefficient = F(3) assert F(25571, 10000) < mean_square_coefficient cutoff = 96 * 10**36 b = 9797 * 10**15 assert b**2 < cutoff assert b**15 * 500**656 < 1359**656 assert F(1359, 500) < sum(F(1, factorial(j)) for j in range(7)) assert k * 656**2 * 10**13 < 225 * b assert 2*b > 3*10**13 print("Cutoff: exact rational inequalities verified at x = 96 * 10^36.") # For N > e^2 the function 512 (log N)^2 / N strictly decreases. # Bracket its crossing of 10^-13, then bound the excess in x = N^2. lo, hi = 9790103351710472581, 9790103351710472582 assert k * 10**13 * log_bounds(lo)[0]**2 > lo assert k * 10**13 * log_bounds(hi)[1]**2 < hi assert F(16054, 100000) < 100*(F(cutoff, hi**2) - 1) assert 100*(F(cutoff, lo**2) - 1) < F(16055, 100000) print("Cutoff excess above the large-x delta crossing: between 0.16054% and 0.16055%.") assert F(20001, 10000) < k big_bad = mean_square_coefficient * 2**2 / (k * F(3, 4)**2) small_bad = mean_square_coefficient * F(2, 3)**2 / (k * F(1, 4)**2) good = F(1, 2) - big_bad - 4 * small_bad # Each good start gives at least (delta*N)^2/(16*L^2) ordered pairs. # A fixed pair covers at most 2*delta*N starts in Lebesgue measure. products_per_scale = good * k / (16 * 2) mass = products_per_scale / 3 width_coefficient = F(3*k, 4) assert (good, products_per_scale, mass) == (F(7, 24), F(14, 3), F(14, 9)) assert width_coefficient == 384 print(f"Rational bounds: good fraction {good}, products/N {products_per_scale}, " f"mass {mass}, interval coefficient {width_coefficient}.") def factor_products(x, upper): """Enumerate the semiprimes in the product interval by trial division.""" products = {} for n in range(int(x) + 1, int(upper) + 1): q = next((i for i in range(2, isqrt(n) + 1) if n % i == 0), None) if q is None: continue p = n // q if all(p % j for j in range(2, isqrt(p) + 1)): products[n] = (p, q) return products def check_translated_grids(): """Integrate over the grid shift and separately test all boundary shifts.""" starts = (F(35), F(77), F(143), F(221, 2), F(287, 3), F(1904, 25)) widths = (F(1, 16), F(1, 9), F(1, 4), F(1, 3)) cases = cells = edges = upper_hits = nonempty = 0 for x in starts: # The grid identity works for any factor band with separated prime ranges. scale = isqrt(int(x)) left, right = F(3 * scale, 2), F(2 * scale) for d in widths: u, step = 1 + d, d * right assert u * x / left < left primes = small_primes(int(max(u * right, u * x / left))) candidates = factor_products(x, u**2 * x) phases = {F(0), step, (right-left) % step} for p in primes: for event in (F(p), p/u, x/p, u*x/p): if left <= event <= right: phases.add((event-left) % step) ordered = sorted(phases) def products_at_shift(phase): t = left + phase seen = set() while t <= right: large = [p for p in primes if t < p <= u*t] small = [q for q in primes if x/t < q <= u*x/t] for p in large: for q in small: n = p*q assert candidates.get(n) == (p, q) assert n not in seen seen.add(n) t += step return seen kernel_integral = F(0) for p, q in candidates.values(): lo = max(left, p/u, x/q) hi = min(right, F(p), u*x/q) kernel_integral += max(F(0), hi-lo) grid_integral = F(0) for a, b in zip(ordered, ordered[1:]): mid_products = products_at_shift((a+b)/2) boundary_products = products_at_shift(a) grid_integral += (b-a) * len(mid_products) nonempty += int(bool(mid_products)) upper_hits += int(u**2*x in boundary_products) cells += 1 edges += 1 assert grid_integral == kernel_integral assert grid_integral <= step * len(candidates) cases += 1 assert nonempty and upper_hits print(f"Disjoint-grid checks: {cases} windows, {cells} open shift cells, " f"{edges} boundary shifts, upper-endpoint hits {upper_hits}.") if __name__ == "__main__": parser = argparse.ArgumentParser(description=__doc__) parser.add_argument("--incidences-only", action="store_true") options = parser.parse_args() if not options.incidences_only: from inequalities import check_arithmetic check_arithmetic() check_finite_cases() check_upper_cover() check_translated_grids() check_explicit_constants()