# Job 8610 check: run as python3 -I chk/chk.py Defs.lean Asymptotic.lean Exact.lean Census.lean # Decimal arithmetic (prec 50); no third-party modules. import sys, re from decimal import Decimal as D, getcontext getcontext().prec = 50 defs, asym, exact, census = [open(p, encoding='utf-8').read() for p in sys.argv[1:5]] ok = True def rep(name, cond, detail=''): global ok ok = ok and cond print(('PASS ' if cond else 'FAIL ') + name + (': ' + detail if detail else '')) L2 = D(2).ln() c5 = 3 * L2 * L2 - D(25) / 12 * L2 # 1. Lean statements (static text checks) rep('Phi divides by (n:R)', 'def Phi (p : ℝ) (n : ℕ) : ℝ := ∑\' j : ℕ, (1 + (((j : ℝ) + 1) / (n : ℝ))) ^ (-p)' in defs) rep('IsThreshold is Phi p n = 1', 'def IsThreshold (n : ℕ) (p : ℝ) : Prop := Phi p n = 1' in defs) for th in ('op5_threshold_leading', 'op5_threshold_second_order', 'op5_threshold_asymptotic'): m = re.search(r'theorem ' + th + r' \(Pfun : ℕ → ℝ\)\s*\(hP : ∀ n : ℕ, IsThreshold n \(Pfun n\)\)', asym) rep(th + ' assumes hP for all n (incl. n=0)', m is not None) rep('second_order conclusion is O(1)', re.search(r'Pfun n - \(\(n : ℝ\) \+ 3 / 2\) \* Real.log 2\) =O\[Filter.atTop\]\s*\(fun _ : ℕ => \(1 : ℝ\)\)', asym) is not None) rep('reachableMeasure := 2^nmin * tailSum', 'def reachableMeasure (p : ℕ) : ℝ :=\n (2 : ℝ) ^ (nmin p) * tailSum p (nmin p)' in exact) rep('L := -log reachableFraction', 'def L (p : ℕ) : ℝ := -Real.log (reachableFraction p)' in exact) rep('census_measure_eq is rfl', ':= rfl' in census and 'reachableMeasure p = (2 : ℝ) ^ (nmin p) * tailSum p (nmin p) := rfl' in census) rep('nminAsym = p/log2 - 5/2 (0-based)', 'def nminAsym (p : ℕ) : ℝ := (p : ℝ) / Real.log 2 - 5 / 2' in defs) # 2. Threshold P_n (Phi(P,n)=1, n>=1) against thresholdAsym def Phi(P, n): s = D(0); j = 0 while True: t = (-P * (1 + D(j + 1) / n).ln()).exp() s += t; j += 1 if t < D(10) ** -45: return s def thresh(n): lo, hi = n * L2 - 5, n * L2 + 5 # Phi decreasing in P for _ in range(140): mid = (lo + hi) / 2 if Phi(mid, n) > 1: lo = mid else: hi = mid return (lo + hi) / 2 rows = [] for n in (100, 200, 400, 800, 1600, 3200): P = thresh(n) d2 = (P - ((n + D(3) / 2) * L2 + c5 / n)) * n * n d1 = (P - (n + D(3) / 2) * L2) * n rows.append((n, d1, d2)) print(f'n={n} (P-(n+3/2)log2)*n={float(d1):.10f} (P-thresholdAsym)*n^2={float(d2):.6f}') rep('second order is O(1/n): (P-(n+3/2)log2)*n -> c5', abs(rows[-1][1] - c5) < D('2e-6'), f'c5={float(c5):.16f}') rep('remainder*n^2 ~ -0.00323 for n=100..3200', all(abs(r[2] + D('0.00323')) < D('0.0002') for r in rows)) # 3. nmin (0-based, least N with Phi_p(N+1) >= 1) and n_min = nmin+1 (1-based) def nmin(p): N = int(p / L2 - D(5) / 2) - 3 while Phi(D(p), N + 1) < 1: N += 1 return N for p, want in ((1000, 1441), (2000, 2883), (5000, 7211)): N = nmin(p) rep(f'p={p} nmin={N} (1-based n_min={N + 1})', N == want, f'p/log2-5/2={float(p / L2 - D(5) / 2):.6f} p/log2-3/2={float(p / L2 - D(3) / 2):.6f}') # 4. c(e) range over e in [0,1) ce = lambda e: -(L2 * L2) / 2 * (e * e - e + D(9) / 4) vals = [ce(D(k) / 1000) for k in range(1000)] lo_, hi_ = min(vals), max(vals) rep('c(e) range = [-(9/8)(log2)^2, -(log2)^2]', lo_ == ce(D(0)) and hi_ == ce(D('0.5')), f'[{lo_:.15f}, {hi_:.15f}]') rep('-(9/8)(log2)^2 < -(log2)^2', -D(9) / 8 * L2 * L2 < -L2 * L2) # 5. (CEIL) failure test 1-{y} < F(p) ~ -b/p, y=p/log2-3/2, over p <= 2e6 getcontext().prec = 30 inv = 1 / L2; best = (D(10), 0) for p in range(2, 2_000_001): y = p * inv - D('1.5') g = p * (1 - (y - int(y))) if g < best[0]: best = (g, p) rep('no (CEIL) failure candidate p<=2e6: min p(1-{y}) >> |b|', best[0] > D('0.01'), f'min p*(1-{{y}})={float(best[0]):.6f} at p={best[1]}, |b|={float(-c5):.6f}') print('ALL PASS' if ok else 'SOME FAIL')