#!/usr/bin/env python3 """ PROVENANCE: PROOF Computation 190 -- Born agreement on every reduced distinction graph: the forced atom vanishes, as a theorem with a rate ====================================================================================== THE ITEM. The crossing rule reproduces Born statistics iff the tension variable is uniform in its own quantile, which fails exactly where the law of |T(C)| under mu = Bern(1/2)^|D| carries an atom. comp 187 showed that for a generic admissible T the only atom is the FORCED one, at zero, of mass mu(independent sets of (D, delta)), since eq:pos puts |T(C)| = 0 on exactly the distinction-free configurations. comp 183 showed the forced atom is at least 2^-c with c the vertex cover number, that reducedness (P1(iii), comp 184) makes c grow, and MEASURED by hill-climbing that no reduced family keeps the atom finite. What the register carried as missing was the theorem: that the forced atom vanishes for EVERY reduced delta, not only for the graphs searched. This file proves it, with an explicit rate, in two lemmas, and then checks both lemmas and the resulting bound on every family the earlier computations tabulated. DEFINITIONS, as the book has them. (D, delta) is the distinction graph, |D| = n. A configuration C is a subset of D; mu picks each property independently with probability 1/2. C is independent if no two of its properties are distinct, and eq:pos says |T(C)| = 0 iff C is independent, for every admissible T. So the forced atom is a_0(delta) = mu(C independent) = i(G) / 2^n, with i(G) the number of independent sets. REDUCED (comp 184, P1(iii)): the map u -> N(u) = {b : delta(u, b)} is injective; at most one property may have an empty distinction set. A MATCHING is a set of pairwise disjoint distinctions; it is MAXIMAL if no distinction can be added. LEMMA 1 (the atom is bounded by any matching). Let M be a matching of delta with |M| = m. Each distinction {u, v} in M has both of u, v in C with probability 1/4, and these m events concern disjoint pairs of properties, so they are independent under mu. An independent C contains no distinction, so none of the m events occurs: a_0(delta) <= (3/4)^m. LEMMA 2 (reducedness forces a large matching). Let M be a MAXIMAL matching and V(M) its 2m properties. I = D \\ V(M) is independent, since any distinction inside it could be added to M. So every u in I has N(u) contained in V(M), and injectivity of N on I bounds |I| by the number of subsets of V(M): n - 2m <= 4^m, hence m >= (1/2) log_2 (n - 2m). THEOREM. For every reduced (D, delta) with |D| = n, and any maximal matching of size m, a_0(delta) <= (3/4)^m <= U(n) := max( (3/4)^{n/4}, (n/2)^{-log_2(4/3)/2} ), since either 2m > n/2, giving the first term, or 2m <= n/2, in which case 4^m >= n - 2m >= n/2 gives the second. U(n) -> 0, so the forced atom vanishes on every reduced distinction graph, uniformly, with no genericity assumption on delta. At the |D| ~ 10^80 of a realised substrate, U = (5 x 10^79)^{-0.2075} ~ 10^-17. WHAT THIS CLOSES, AND WHAT IT DOES NOT. With comp 187, every atom but the forced one belongs to T rather than to delta. So Born agreement is now a theorem on the distinction-graph side for every admissible delta, and what remains is a condition on the law of T alone: that its contingent per-configuration content does not tie, which an admissible T can violate (T = min(1, T_ex) is admissible and has an atom at one that grows) and which is exactly the residual freedom item 1 of the structural front carries. Two residues counted twice have become one, counted once. CHECKS, every one exact where exact is reachable. 1. Lemma 1 on 200 random graphs at |D| = 12..16: a_0 <= (3/4)^m for a greedy maximal matching, with a_0 computed exactly over all 2^|D| configurations. 2. Lemma 2 on the same graphs when reduced, and on the extremal reduced family (comp 183's subset graphs, c = 3..9, |D| up to 520): n - 2m <= 4^m always; and the inequality FAILS for the star and for K_k plus enough isolated properties, the non-reduced families comp 180 found failing, so the hypothesis is doing the work (a non-reduced graph may still satisfy it; reducedness guarantees it). 3. The theorem's bound U(n) against the extremal family's exact atom, computed in closed form: i(subset graph) = sum over A subset of S of 2^{2^{c - |A|} - 1}. Over comp 183's range c = 3..7 the atom falls as |D|^-1.1 (its sampled -1.10, reproduced within 0.05); the closed form shows the exponent drifts to -1, since the A = {} term alone gives 2^-c = 1/(|D| + 1 - c). U(n) falls as |D|^-0.21: the bound is universal, not sharp. 4. The maximum atom over ALL reduced graphs at |D| <= 6, exhaustively, and over hill-climbed reduced graphs at |D| = 8..16, against U(n). 5. Tamper: add t false twins of every leaf of the c = 3 subset graph (what reducedness forbids); |D| grows from 10 to 73, the maximal matching stays at m = 3, Lemma 2 fails once |D| - 2m > 64, and the exact atom (closed form, checked against the 2^17 enumeration at t = 1) converges to 2^-c = 1/8 as comp 183 found: without reducedness the bound (3/4)^m stops falling and the atom stays finite. A "pass": Lemma 1 holding on every graph tested; Lemma 2 holding on every reduced graph and failing on the star and on K_k plus enough isolated properties; every exact atom below U(n); the extremal exponent over c = 3..7 within 0.05 of -1.10; the twin tamper breaking Lemma 2 with the atom pinned within 1e-6 of 2^-c. """ import itertools import math import numpy as np LOG_RATE = -math.log2(4 / 3) / 2 # exponent of the universal bound, -0.2075 # --- graphs ----------------------------------------------------------------------- def neighbourhoods(n, edges): N = [set() for _ in range(n)] for u, v in edges: N[u].add(v); N[v].add(u) return N def is_reduced(n, edges): """u -> N(u) injective (comp 184's reducedness: at most one empty distinction set).""" N = neighbourhoods(n, edges) return len({frozenset(s) for s in N}) == n def maximal_matching(edges): used, M = set(), [] for u, v in sorted(edges): if u not in used and v not in used: M.append((u, v)); used.add(u); used.add(v) return M def bits_table(n): m = np.arange(1 << n, dtype=np.int64) out = np.empty((n, 1 << n), dtype=np.int8) for a in range(n): out[a] = (m >> a) & 1 return out def atom_exact(n, edges, bt=None): """mu(C independent) over all 2^n configurations.""" bt = bits_table(n) if bt is None else bt bad = np.zeros(1 << n, dtype=np.int8) for u, v in edges: bad |= bt[u] & bt[v] return int((bad == 0).sum()) / (1 << n) def subset_graph(c): """comp 183's extremal reduced graph: a cover S of size c and one independent property for every nonempty subset of S. |D| = c + 2^c - 1.""" edges, idx = [], c for k in range(1, c + 1): for T in itertools.combinations(range(c), k): for s in T: edges.append((s, idx)) idx += 1 return idx, edges def subset_graph_atom_exact(c): """Closed form: an independent set is A subset of S (S is independent) plus any set of leaves whose subset avoids A; the leaves free of A are the nonempty subsets of S \\ A, 2^{c-|A|} - 1 of them. Exact in big integers.""" n = c + (1 << c) - 1 i = sum(math.comb(c, a) * (1 << ((1 << (c - a)) - 1)) for a in range(c + 1)) return i / (1 << n), n def U(n): return max((3 / 4) ** (n / 4), (n / 2) ** LOG_RATE) def star(n): return [(0, i) for i in range(1, n)] def k_plus_iso(k): return list(itertools.combinations(range(k), 2)) # --- parts ------------------------------------------------------------------------ def part1_lemma1(): print("\n (1) LEMMA 1: a_0 <= (3/4)^m for any matching, exact atoms, 200 random graphs") rng = np.random.default_rng(190) worst, count = 0.0, 0 bts = {n: bits_table(n) for n in (12, 14, 16)} for n in (12, 14, 16): for _ in range(67 if n < 16 else 66): p = rng.uniform(0.05, 0.6) edges = [e for e in itertools.combinations(range(n), 2) if rng.random() < p] m = len(maximal_matching(edges)) a0 = atom_exact(n, edges, bts[n]) worst = max(worst, a0 / (3 / 4) ** m if m else a0) count += 1 print(f" {count} graphs; largest a_0 / (3/4)^m = {worst:.4f} (must be <= 1)") return worst <= 1.0 + 1e-12 def part2_lemma2(): print("\n (2) LEMMA 2: n - 2m <= 4^m on reduced graphs; and it FAILS without reducedness") rng = np.random.default_rng(191) ok_reduced, tested = True, 0 for n in (12, 14, 16, 20, 30): for _ in range(40): p = rng.uniform(0.1, 0.6) edges = [e for e in itertools.combinations(range(n), 2) if rng.random() < p] if not is_reduced(n, edges): continue m = len(maximal_matching(edges)); tested += 1 ok_reduced &= (n - 2 * m <= 4 ** m) print(f" {tested} random reduced graphs: inequality holds on all = {ok_reduced}") ok_ext = True for c in range(3, 10): n, edges = subset_graph(c) m = len(maximal_matching(edges)) ok_ext &= (n - 2 * m <= 4 ** m) print(f" subset graph c = {c}: |D| = {n:4d}, m = {m:2d}, n - 2m = {n - 2*m:4d} <= 4^m = {4**m}: {n - 2*m <= 4**m}") fails = [] for n in (8, 16, 32): m = len(maximal_matching(star(n))); fails.append(n - 2 * m <= 4 ** m) print(f" star |D| = {n:2d}: reduced = {is_reduced(n, star(n))}, n - 2m = {n - 2*m} <= 4^m = {4**m}: {n - 2*m <= 4**m}") for k, n in ((4, 30), (6, 120)): edges = k_plus_iso(k); m = len(maximal_matching(edges)); fails.append(n - 2 * m <= 4 ** m) print(f" K_{k} + {n-k} isolated: reduced = {is_reduced(n, edges)}, n - 2m = {n - 2*m} <= 4^m = {4**m}: {n - 2*m <= 4**m}") return ok_reduced and ok_ext, not any(fails) def part3_extremal(): print("\n (3) THE BOUND U(n) AGAINST THE EXTREMAL REDUCED FAMILY, exact atoms in closed form") print(f" {'c':>3} {'|D|':>5} {'m':>3} {'atom':>12} {'(3/4)^m':>10} {'U(n)':>10} below") xs, ys, ok = [], [], True for c in range(3, 10): a0, n = subset_graph_atom_exact(c) _, edges = subset_graph(c); m = len(maximal_matching(edges)) ok &= a0 <= (3 / 4) ** m <= U(n) + 1e-15 xs.append(math.log(n)); ys.append(math.log(a0)) print(f" {c:3d} {n:5d} {m:3d} {a0:12.3e} {(3/4)**m:10.3e} {U(n):10.3e} {a0 <= U(n)}") slope = np.polyfit(xs[:5], ys[:5], 1)[0] slope_hi = np.polyfit(xs[-3:], ys[-3:], 1)[0] print(f" extremal atom ~ |D|^{slope:.2f} over c = 3..7 (comp 183 measured -1.10), ~ |D|^{slope_hi:.2f} over c = 7..9,") print(f" drifting to -1 since the A = {{}} term alone is 2^-c; the bound falls as |D|^{LOG_RATE:.2f}") # the check in comp 183's own terms: at c = 3..7 its sampled atoms were 0.193 -> 0.011 print(f" comp 183's sampled 0.193 (c=3) and 0.011 (c=7) against exact {subset_graph_atom_exact(3)[0]:.3f} and {subset_graph_atom_exact(7)[0]:.4f}") return ok, slope def part4_search(): print("\n (4) THE LARGEST ATOM OVER REDUCED GRAPHS: exhaustive at |D| <= 6, hill-climbed at 8..16") ok = True for n in (4, 5, 6): bt = bits_table(n); pairs = list(itertools.combinations(range(n), 2)); best = 0.0 for mask in range(1 << len(pairs)): edges = [pairs[i] for i in range(len(pairs)) if mask >> i & 1] if is_reduced(n, edges): best = max(best, atom_exact(n, edges, bt)) ok &= best <= U(n) + 1e-12 print(f" |D| = {n}: all reduced graphs, max atom = {best:.4f}, U(n) = {U(n):.4f}") rng = np.random.default_rng(192) for n in (8, 10, 12, 14, 16): bt = bits_table(n); pairs = list(itertools.combinations(range(n), 2)); best = 0.0 for restart in range(6): edges = set(e for e in pairs if rng.random() < 0.3) while not is_reduced(n, list(edges)): edges ^= {pairs[rng.integers(len(pairs))]} cur = atom_exact(n, list(edges), bt) for step in range(300): e = pairs[rng.integers(len(pairs))] trial = set(edges); trial ^= {e} if not is_reduced(n, list(trial)): continue a = atom_exact(n, list(trial), bt) if a >= cur: edges, cur = trial, a best = max(best, cur) ok &= best <= U(n) + 1e-12 print(f" |D| = {n:2d}: hill-climbed max atom = {best:.4f}, U(n) = {U(n):.4f}") return ok def twin_subset_atom_exact(c, t): """The c-subset graph with every leaf repeated 1 + t times (t false twins): same counting as subset_graph_atom_exact with the free leaves multiplied by 1 + t.""" n = c + (1 + t) * ((1 << c) - 1) i = sum(math.comb(c, a) * (1 << ((1 + t) * ((1 << (c - a)) - 1))) for a in range(c + 1)) return i / (1 << n), n def part5_tamper(): print("\n (5) TAMPER: false twins, which reducedness forbids; c = 3 subset graph, t twins per leaf") c = 3 n, edges = subset_graph(c); N = neighbourhoods(n, edges) # closed form against the exact enumeration at t = 1 (|D| = 17) twins, idx = list(edges), n for leaf in range(c, n): for s in N[leaf]: twins.append((s, idx)) idx += 1 exact1 = atom_exact(idx, twins); closed1, n1 = twin_subset_atom_exact(c, 1) print(f" closed form at t = 1: |D| = {n1}, atom = {closed1:.6f}; enumeration over 2^{idx}: {exact1:.6f}") print(f" {'t':>3} {'|D|':>4} {'m':>3} {'n-2m':>5} {'4^m':>4} Lemma 2 {'atom':>10} {'2^-c':>6}") broke, pinned, ok_form = False, True, abs(exact1 - closed1) < 1e-12 for t in range(0, 10): tw, idx = list(edges), n for leaf in range(c, n): for _ in range(t): for s in N[leaf]: tw.append((s, idx)) idx += 1 m = len(maximal_matching(tw)); a0, n2 = twin_subset_atom_exact(c, t) assert n2 == idx lemma2 = n2 - 2 * m <= 4 ** m broke |= (not lemma2) and (not is_reduced(n2, tw)) pinned &= a0 >= 2 ** -c print(f" {t:3d} {n2:4d} {m:3d} {n2 - 2*m:5d} {4**m:4d} {'holds ' if lemma2 else 'FAILS '} {a0:10.6f} {2**-c:6.4f}") last = twin_subset_atom_exact(c, 9)[0] print(f" the matching never grows, (3/4)^m stays at {(3/4)**3:.4f}, and the atom sits on 2^-c to {abs(last - 2**-c):.1e}") return broke and pinned and ok_form and abs(last - 2 ** -c) < 1e-6 def main(): print("=" * 100) print(" Computation 190 -- Born agreement on every reduced distinction graph: a theorem with a rate") print("=" * 100) checks = [] checks.append(("Lemma 1 holds on every graph tested", part1_lemma1())) l2_ok, l2_fails = part2_lemma2() checks.append(("Lemma 2 holds on every reduced graph tested", l2_ok)) checks.append(("Lemma 2 fails on the star and on K_k plus enough isolated properties", l2_fails)) ext_ok, slope = part3_extremal() checks.append(("extremal atoms below (3/4)^m and below U(n)", ext_ok)) checks.append(("extremal exponent over c = 3..7 within 0.05 of comp 183's -1.10", abs(slope + 1.10) < 0.05)) checks.append(("largest reduced atom below U(n), exhaustive and hill-climbed", part4_search())) checks.append(("false twins break Lemma 2 and pin the atom on 2^-c", part5_tamper())) nD = 1e80 print(f"\n AT SUBSTRATE SCALE: |D| = 1e80 gives U = {U(nD):.1e}; the forced atom is below that on every reduced delta.") print("\n" + "=" * 100) for name, ok in checks: print(f" {'ok ' if ok else 'FAIL'} {name}") print("=" * 100) print(" THEOREM: for every reduced (D, delta), a_0 <= (3/4)^m <= U(|D|) -> 0. The distinction-graph") print(" side of Born agreement is closed; what remains is the law of T, which is item 1's residual.") print(" PASS" if all(ok for _, ok in checks) else " FAIL") if __name__ == "__main__": main()