def banner(s): print("\n" + "=" * 78 + "\n" + s + "\n" + "=" * 78) # --------------------------------------------------------------------------- # A. Computable proxy for K(C) # --------------------------------------------------------------------------- def compressed_bits(bitmatrix): packed = np.packbits(bitmatrix.astype(np.uint8).ravel()).tobytes() # raw LZMA stream (no container header) to reduce constant overhead comp = lzma.compress(packed, format=lzma.FORMAT_RAW, filters=[{"id": lzma.FILTER_LZMA2, "preset": 9 | lzma.PRESET_EXTREME}]) return 8 * len(comp) def section_A(): banner("A. Proxy for K(C): LZMA-compressed size of exposure matrix E (|L| x |H|)") rows = [] print(f"{'|L|':>5} {'|H|':>6} {'|L||H|':>8} | {'random':>8} {'ratio':>6} | " f"{'Bern(.1)':>8} {'ratio':>6} | {'global':>7} {'split':>7}") for L in (8, 32, 128): for H in (64, 256, 1024): n = L * H E_rand = rng.integers(0, 2, size=(L, H)) E_b01 = (rng.random((L, H)) < 0.1).astype(int) E_glob = np.ones((L, H), dtype=int) # same lie to everyone E_split = np.zeros((L, H), dtype=int); E_split[:, : H // 2] = 1 # rule-based split r = dict(L=L, H=H, LH=n, random=compressed_bits(E_rand), bern01=compressed_bits(E_b01), glob=compressed_bits(E_glob), split=compressed_bits(E_split)) rows.append(r) print(f"{L:>5} {H:>6} {n:>8} | {r['random']:>8} {r['random']/n:>6.3f} | " f"{r['bern01']:>8} {r['bern01']/n:>6.3f} | {r['glob']:>7} {r['split']:>7}") # fit slope of compressed bits vs |L||H| for random E x = np.array([r["LH"] for r in rows], float) y = np.array([r["random"] for r in rows], float) slope = float(np.polyfit(x, y, 1)[0]) yb = np.array([r["bern01"] for r in rows], float) slope_b = float(np.polyfit(x, yb, 1)[0]) h01 = -(0.1 * math.log2(0.1) + 0.9 * math.log2(0.9)) print(f"\nLinear fit, random E: bits ~= {slope:.3f} * |L||H| (theory: >= 1 - o(1))") print(f"Linear fit, Bernoulli(.1): bits ~= {slope_b:.3f} * |L||H| (entropy floor h(0.1) = {h01:.3f})") print("Structured E (global lie / rule-based split) stays near-constant: the Omega(|L||H|)") print("bound needs audience-specific, non-rule-based exposure. That is an assumption, not a theorem.") RESULTS["A"] = dict(rows=rows, slope_random=slope, slope_bern01=slope_b, entropy_bern01=h01) # --------------------------------------------------------------------------- # B. Crossover model # --------------------------------------------------------------------------- def hazard(n, m, q0, q): """Per-round detection probability. q0: per-observer chance an exogenous reality check contradicts the lie. q : chance one cross-observer record comparison exposes an audience-specific lie. m : fraction of other observers' records reachable through shared persistent memory.""" return 1.0 - (1.0 - q0) ** n * (1.0 - q) ** (m * n * (n - 1)) def lambertw0(z, tol=1e-15, maxit=200): """Principal branch W0 for real z >= -1/e (numpy/stdlib only, Halley iteration).""" if z < -1.0 / math.e - 1e-15: raise ValueError("z < -1/e") if abs(z + 1.0 / math.e) < 1e-14: return -1.0 w = math.log1p(z) if z > -0.3 else -1.0 + math.sqrt(2.0 * (1.0 + math.e * z)) for _ in range(maxit): ew = math.exp(w) f = w * ew - z wp1 = w + 1.0 if abs(wp1) < 1e-300: break dw = f / (ew * wp1 - (w + 2.0) * f / (2.0 * wp1)) w -= dw if abs(dw) < tol * (1.0 + abs(w)): break return w def flows(T, G, c, kappa, h, Lp, Delta, delta=1.0): """Brute-force expected per-round advantage of deceiving (from round 0) over honesty. Round d: if undetected at start (prob s^d): gain G, pay maintenance c*kappa*(d+1), then detected with prob h and pay Lp immediately. If detected earlier: -Delta.""" out = np.empty(T) surv = 1.0 for d in range(T): f = surv * (G - c * kappa * (d + 1) - h * Lp) - (1.0 - surv) * Delta out[d] = (delta ** d) * f surv *= (1.0 - h) return out def D_closed(t, G, c, kappa, h, Lp, Delta): """Closed-form undiscounted cumulative advantage after t rounds (t may be real).""" if h == 0.0: return G * t - c * kappa * t * (t + 1) / 2.0 s = 1.0 - h A = G - h * Lp + Delta geo = (1.0 - s ** t) / h arith = (1.0 - (t + 1) * s ** t + t * s ** (t + 1)) / (1.0 - s) ** 2 return A * geo - c * kappa * arith - Delta * t def Dinf_closed(G, c, kappa, h, Lp, Delta, delta): s = 1.0 - h x = delta * s A = G - h * Lp + Delta return A / (1 - x) - c * kappa / (1 - x) ** 2 - Delta / (1 - delta) def first_negative(cum, tol=1e-9): """cum[i] = D(i+1). Returns the first round count t >= 1 with D(t) < -tol.""" idx = np.where(cum < -tol)[0] return int(idx[0] + 1) if idx.size else None def bisect(f, lo, hi, it=200): flo = f(lo) for _ in range(it): mid = 0.5 * (lo + hi) fm = f(mid) if (fm > 0) == (flo > 0): lo, flo = mid, fm else: hi = mid return 0.5 * (lo + hi) def section_B(): banner("B1. Pure maintenance channel (no detection): t* = 2G/(c*kappa) - 1, delta* = 1 - c*kappa/G") ok = tot = 0 ex = [] for G in (0.5, 1.0, 2.0, 5.0): for ck in (0.001, 0.01, 0.05, 0.2): t_cf = 2 * G / ck - 1 T = int(t_cf) + 50 cum = np.cumsum(flows(T, G, 1.0, ck, 0.0, 0.0, 0.0)) t_num = first_negative(cum) t_pred = math.floor(t_cf) + 1 # first integer t with D(t)<0 (D(t_cf)=0) tot += 1; ok += (t_num == t_pred) # discounted dstar = 1 - ck / G dgrid = [d for d in (0.5, 0.9, 0.99, 0.999) if abs(d - dstar) > 1e-3 and 0 < d < 1] for d in dgrid: num = np.sum(flows(200000, G, 1.0, ck, 0.0, 0.0, 0.0, d)) if d < 0.9999 else None tot += 1; ok += ((num < 0) == (d > dstar)) ex.append(dict(G=G, c_kappa=ck, t_closed=t_cf, t_first_int_neg=t_num, delta_star=dstar)) for e in ex[:6]: print(f" G={e['G']:<4} c*kappa={e['c_kappa']:<6} t*(closed)={e['t_closed']:>9.2f} " f"first integer t with D<0 (numeric)={e['t_first_int_neg']:>6} delta*={e['delta_star']:.4f}") print(f" checks passed: {ok}/{tot}") RESULTS["B1"] = dict(passed=ok, total=tot, examples=ex) banner("B2. Pure detection channel (c=0): t* = a + W0(-ab e^{-ab})/b ; delta* = (G-hLp)/(G-hLp+h*Delta)") ok = tot = 0 ex = [] q0, q = 0.002, 0.01 for n in (2, 5, 10, 20): for m in (0.0, 0.25, 1.0): h = hazard(n, m, q0, q) for (G, Lp, Delta) in ((1.0, 2.0, 0.5), (3.0, 5.0, 1.0), (0.5, 0.0, 0.2)): A = G - h * Lp + Delta entry = dict(n=n, m=m, h=h, G=G, Lp=Lp, Delta=Delta) if G - h * Lp <= 0: entry.update(t_closed=0.0, note="never ahead (G <= h*Lp)") cum = np.cumsum(flows(50, G, 0, 0, h, Lp, Delta)) tot += 1; ok += (cum[0] <= 0) ex.append(entry); continue a = A / (h * Delta) b = -math.log(1 - h) z = -a * b * math.exp(-a * b) t_cf = a + lambertw0(z) / b # continuous root of closed-form D(t), independent of W t_root = bisect(lambda t: D_closed(t, G, 0, 0, h, Lp, Delta), 1e-9, 10 * a + 10) T = int(t_cf) + 200 cum = np.cumsum(flows(T, G, 0, 0, h, Lp, Delta)) t_int = first_negative(cum) tot += 1; ok += (abs(t_cf - t_root) < 1e-6 * max(1, t_cf)) tot += 1; ok += (t_int == math.floor(t_cf) + 1) # closed-form D(t) at integers equals brute-force cumulative sum ts = np.arange(1, T + 1) Dcf = np.array([D_closed(t, G, 0, 0, h, Lp, Delta) for t in ts]) tot += 1; ok += bool(np.allclose(Dcf, cum, rtol=1e-9, atol=1e-9)) dstar = (G - h * Lp) / (G - h * Lp + h * Delta) for d in (0.5, 0.8, 0.9, 0.95, 0.99): if abs(d - dstar) < 1e-4: continue num = Dinf_closed(G, 0, 0, h, Lp, Delta, d) brute = np.sum(flows(20000, G, 0, 0, h, Lp, Delta, d)) tot += 1; ok += ((num < 0) == (d > dstar)) and abs(num - brute) < 1e-6 * max(1, abs(num)) entry.update(t_closed=t_cf, t_root=t_root, t_first_int_neg=t_int, delta_star=dstar, t_marginal=math.log(A / Delta) / b) ex.append(entry) print(f" q0={q0} (reality check), q={q} (cross-record check); G=1, Lp=2, Delta=0.5 rows:") print(f" {'n':>3} {'m':>5} {'h(n,m)':>8} {'t*':>9} {'t_marg':>8} {'delta*':>8}") for e in ex: if e["G"] == 1.0 and "t_root" in e: print(f" {e['n']:>3} {e['m']:>5} {e['h']:>8.4f} {e['t_closed']:>9.2f} " f"{e['t_marginal']:>8.2f} {e['delta_star']:>8.4f}") elif e["G"] == 1.0: print(f" {e['n']:>3} {e['m']:>5} {e['h']:>8.4f} deception never ahead: G <= h*Lp") print(f" checks passed: {ok}/{tot}") RESULTS["B2"] = dict(passed=ok, total=tot, q0=q0, q=q, examples=ex)