#!/usr/bin/env python3 """ PROVENANCE: PROOF Computation 178 -- the non-balance counterexample does not scale, and why ========================================================================= WHAT THIS DOES. sec:open-structural carries non-balance, |sum_a v(a)| > 0, as a CONDITION rather than a derivation. comp 169 sharpened it (balance needs total coordination) and withdrew the step that would have closed it, because comp 152's mu_pm is an invariant law, naming no direction and paying nothing, that balances 31% of the time at |D| = 6. sec:non-balance-status says what would close the item: "an argument about correlation rather than about direction". This file does not supply that argument. What it does is measure how far the obstruction reaches, and the answer is: not far. BE PRECISE ABOUT WHAT WAS AND WAS NOT ALREADY THERE, because an earlier version of this file was not. sec:complement-asymmetry ALREADY gives the closed form: mu_pm "balances with probability C(|D|,|D|/2) 2^-|D|, about 0.31 at |D| = 6". So the book does not report a bare 31%, and this file does not supply the formula. What it adds is four things the book does not state: (a) that the symmetry package FORCES that law, so mu_pm is not one example among many but the ONLY complementation-invariant option on the all-parallel family; (b) the asymptotics, sqrt(2/(pi |D|)), hence about 1e-40 at |D| ~ 1e80; (c) that balance is EXACTLY IMPOSSIBLE at every odd |D|; (d) a bound needing no family at all, P(balance) <= 1/2 for any complementation-invariant law. (a) is the one that matters, because it converts a counterexample into a bound: if the package admits only this law, its balance probability pins the whole class. THE PACKAGE. sec:non-balance-status records mu_pm as invariant under relabelling of D, under per-property complementation v(a) -> -v(a), and under rotation. The middle one is load-bearing here and has not been used before. RESULT 1 -- COMPLEMENTATION INVARIANCE FORCES THE SIGNS TO BE I.I.D. On the all-parallel family v(a) = eps_a u, complementation at a is exactly eps_a -> -eps_a. The single-coordinate flips generate the group ({+-1}^n, *) acting on {+-1}^n by coordinatewise multiplication, which is SIMPLY TRANSITIVE. A law invariant under a transitive group action is uniform. So the sign vector is uniform on {+-1}^n, i.e. i.i.d. fair signs, and mu_pm's sign structure is not a modelling choice at all: it is the only complementation-invariant option. RESULT 2 -- SO THE BALANCE PROBABILITY IS AN EXACT BINOMIAL, AND IT VANISHES. Balance is (sum_a eps_a) u = 0, i.e. sum_a eps_a = 0, so P(balance) = C(n, n/2) / 2^n for n even, 0 for n ODD, which is 5/16 = 31.25% at n = 6, reproducing comp 152's measured 31%, and behaves as sqrt(2/(pi n)). At a substrate cardinality |D| ~ 1e80 it is about 8e-41. Two things worth saying separately: the counterexample is a SMALL-|D| phenomenon, and for ODD |D| it does not balance at all, ever. RESULT 3 -- AND A BOUND THAT NEEDS NO FAMILY AT ALL. For ANY law invariant under per-property complementation, balanced configurations pair off with unbalanced ones: flipping a single property a sends sum v to sum v - 2v(a) = -2v(a), which is nonzero because |v(a)| = 1. The flip preserves the law, so the balanced set and its image are disjoint of equal measure, giving P(balance) <= 1/2 for every complementation-invariant law on (S^6)^D, with no assumption of a shared hidden variable. The bound is ACHIEVED at |D| = 2, where it is also C(2,1)/4. WHAT THIS DOES NOT DO. It does NOT derive non-balance, and the item stays a condition. Three reasons, stated because each is a way this file could be misread: (a) A probability bound is not a derivation. The substrate is one configuration, not a draw, and sec:non-balance-status is explicit that non-balance's standing is a stability statement rather than a probabilistic one. This file bounds how badly a RANDOM law can behave; it says nothing about the actual v. (b) The vanishing in Result 2 is proved for the all-parallel family, which is the family the book's counterexample lives in. A different correlation structure is not covered by it, only by the weaker Result 3. (c) Result 3's 1/2 is not small. It forbids certainty, not balance. WHAT IT IS GOOD FOR. The register can say the known obstruction is bounded and does not scale, and can say WHY: the package leaves no other law to choose, so the one counterexample's probability bounds the class. At the substrate's own cardinality that number is 1e-40, and it is exactly zero at odd |D|. """ import math import itertools from fractions import Fraction from math import comb import numpy as np RNG = np.random.default_rng(20260929) def rule(): print("=" * 100) # --------------------------------------------------------------------------- def part1(): rule() print(" 1. THE REDUCTION: ON THE ALL-PARALLEL FAMILY, BALANCE IS A SIGN SUM") rule() print(" comp 152's mu_pm is v(a) = eps_a u, one shared u on S^6, signs +-1.") print(" Then sum_a v(a) = (sum_a eps_a) u, and |u| = 1, so") print() print(" balance <=> sum_a eps_a = 0.") print() print(" The directional content drops out entirely: the whole question is a") print(" statement about the sign vector. Checked directly on random draws.") print() ok = True for n in (4, 6, 7): u = RNG.normal(size=7); u /= np.linalg.norm(u) for _ in range(200): e = RNG.choice([-1, 1], size=n) tot = np.linalg.norm((e[:, None] * u).sum(0)) if (tot < 1e-9) != (e.sum() == 0): ok = False print(f" -> |sum v| = 0 iff sum eps = 0, over 600 draws : {ok}") print() return ok def part2(): rule() print(" 2. COMPLEMENTATION INVARIANCE FORCES THE SIGNS TO BE I.I.D.") rule() print(" sec:non-balance-status records mu_pm as invariant under per-property") print(" complementation v(a) -> -v(a). On this family that map IS eps_a -> -eps_a.") print() print(" The single-coordinate flips generate ({+-1}^n, *) acting on {+-1}^n by") print(" coordinatewise multiplication. That action is SIMPLY TRANSITIVE: for any") print(" two sign vectors there is exactly one flip pattern carrying one to the") print(" other, namely their coordinatewise product. A probability law invariant") print(" under a transitive group action is uniform on the orbit.") print() okall = True for n in (3, 4, 6): pts = list(itertools.product([-1, 1], repeat=n)) # exactly one group element carries x to y, for every ordered pair counts = set() for x in pts: for y in pts: g = tuple(a * b for a, b in zip(x, y)) # the unique flip pattern counts.add(sum(1 for h in pts if tuple(a*c for a, c in zip(x, h)) == y)) okall &= (counts == {1}) print(f" n = {n}: every ordered pair joined by exactly one flip pattern : {counts == {1}}") print() print(" So the ONLY complementation-invariant law on the sign vector is the") print(" uniform one. mu_pm's i.i.d. signs are not a modelling choice; they are") print(" the only option the book's own symmetry package leaves.") print() print(f" -> the sign law is forced uniform : {okall}") print() return okall def part3(): rule() print(" 3. HENCE AN EXACT BINOMIAL, WHICH VANISHES WITH |D|") rule() print(" P(balance) = P(sum eps = 0) = C(n, n/2)/2^n for n even, 0 for n odd.") print() print(f" {'|D|':>10}{'exact':>16}{'decimal':>12}{'sqrt(2/pi|D|)':>16}") for n in (2, 5, 6, 8, 10, 100, 1000): if n % 2: print(f" {n:>10}{'0':>16}{0.0:>12.6f}{'(|D| odd)':>16}") continue p = Fraction(comb(n, n // 2), 2 ** n) approx = math.sqrt(2 / (math.pi * n)) shown = str(p) if n <= 10 else f"C({n},{n//2})/2^{n}" print(f" {n:>10}{shown:>16}{float(p):>12.6f}{approx:>16.6f}") p6 = Fraction(comb(6, 3), 2 ** 6) print() print(f" At |D| = 6 this is {p6} = {float(p6):.4f}, which is comp 152's measured 31%.") print(" It is therefore not an accident of that experiment but the forced value.") print() big = 1e80 print(f" At a substrate cardinality |D| ~ 1e80 : P(balance) ~ {math.sqrt(2/(math.pi*big)):.2e}") print() print(" AND FOR ODD |D| IT IS EXACTLY ZERO, at every cardinality, because a sum") print(" of an odd number of +-1 is odd and cannot vanish. The counterexample") print(" does not merely become rare on half the cardinalities; it is unavailable.") print() ok = (float(p6) == 0.3125) print(f" -> the forced value reproduces comp 152's 31% at |D| = 6 : {ok}") print() return ok def part4(): rule() print(" 4. A BOUND WITH NO FAMILY ASSUMED: P(balance) <= 1/2") rule() print(" Let the joint law on (S^6)^D be invariant under per-property") print(" complementation, and nothing else. Flip a single property a:") print() print(" sum v -> sum v - 2 v(a) = -2 v(a) on the balanced set,") print() print(" which is nonzero because |v(a)| = 1. So the flip carries the balanced") print(" set into its complement, and it preserves the law, so the two sets have") print(" equal measure and are disjoint. Hence 2 P(balance) <= 1.") print() print(" No shared hidden variable, no all-parallel structure, no rotation") print(" invariance is used. Measured on three invariant laws:") print() def mc_parallel(n, N=200000): e = RNG.choice([-1, 1], size=(N, n)); return (e.sum(1) == 0).mean() def mc_generic(n, N=40000): v = RNG.normal(size=(N, n, 7)); v /= np.linalg.norm(v, axis=2, keepdims=True) s = RNG.choice([-1, 1], size=(N, n, 1)) return (np.linalg.norm((s * v).sum(1), axis=1) < 1e-9).mean() print(f" {'|D|':>6}{'all-parallel':>16}{'exact':>12}{'generic on S^6':>18}{'<= 1/2':>9}") ok = True for n in (2, 4, 6, 8): ex = comb(n, n // 2) / 2 ** n a, g = mc_parallel(n), mc_generic(n) ok &= (a <= 0.5 + 1e-2) and (g <= 0.5) print(f" {n:>6}{a:>16.5f}{ex:>12.5f}{g:>18.5f}{'ok':>9}") print() print(" The generic column is 0 because an atomless conditional law gives zero") print(" mass to a single point, which is comp 169's step (ii) seen from here.") print(" The bound is ACHIEVED at |D| = 2, where C(2,1)/4 = 1/2 exactly.") print() print(f" -> P(balance) <= 1/2 on every law tested : {ok}") print() return ok def part5(): rule() print(" 5. SCOPE: WHAT THIS DOES NOT DO") rule() print(" IT DOES NOT DERIVE NON-BALANCE. The item stays a condition and the") print(" register entry stands. Three ways this file could be misread:") print() print(" (a) A probability bound is not a derivation. The substrate is ONE") print(" configuration, not a draw from a law, and sec:non-balance-status is") print(" explicit that non-balance's standing is a stability statement rather") print(" than a probabilistic one. This bounds how badly a random law can") print(" behave and says nothing about the actual v.") print(" (b) Results 1 and 2 are proved for the ALL-PARALLEL family, which is") print(" where the book's counterexample lives. Other correlation structures") print(" are covered only by Result 3's weaker 1/2.") print(" (c) 1/2 is not small. Result 3 forbids certainty, not balance.") print() print(" WHAT IT IS GOOD FOR. The book already gives the closed form, so the") print(" formula is not the contribution. What it does not say is that the") print(" package FORCES that law, which turns one counterexample into a bound on") print(" the class; nor that the value goes as |D|^{-1/2}, is 1e-40 at the") print(" substrate's own cardinality, and is exactly zero at every odd |D|.") print() return True def part6(): rule() print(" 6. TAMPER TEST: WHICH SYMMETRY IS DOING THE WORK") rule() print(" If the bound came from the setup rather than from complementation") print(" invariance, dropping that invariance would change nothing. Drop it.") print() print(" Take the signs UNIFORM ON THE ZERO-SUM SET {eps : sum eps = 0}, with u") print(" still uniform on S^6. This law is still rotation-invariant, still") print(" invariant under relabelling, still names no direction and still pays no") print(" parameter. It balances with probability EXACTLY 1.") print() n = 6 zs = [e for e in itertools.product([-1, 1], repeat=n) if sum(e) == 0] u = RNG.normal(size=7); u /= np.linalg.norm(u) bal = 0 for _ in range(2000): e = np.array(zs[RNG.integers(len(zs))]) if np.linalg.norm((e[:, None] * u).sum(0)) < 1e-9: bal += 1 p_zero_sum = bal / 2000 p_iid = comb(n, n // 2) / 2 ** n print(f" |D| = {n}: zero-sum signs balance with probability {p_zero_sum:.4f}") print(f" i.i.d. signs balance with probability {p_iid:.4f}") print() print(" And it is NOT complementation-invariant: flipping one sign leaves the") print(" zero-sum set, so the law is not preserved. Checked:") e0 = np.array(zs[0]); e1 = e0.copy(); e1[0] *= -1 left = bool(abs(e1.sum()) > 0) print(f" flipping one sign takes sum {e0.sum()} to {e1.sum()}, off the set : {left}") print() print(" So the 1/2 bound and the binomial are carried by per-property") print(" complementation SPECIFICALLY, not by rotation invariance and not by the") print(" absence of a named direction. That is the assumption to challenge if") print(" anyone wants to reopen this, and it is one the book already asserts.") print() ok = p_zero_sum > 0.99 and p_iid < 0.4 and left print(f" -> dropping the symmetry restores certainty of balance : {ok}") print() return ok def main(): print() rule() print(" COMPUTATION 178. The non-balance counterexample does not scale") rule() print(""" comp 169 withdrew the step that would have closed non-balance, because comp 152's mu_pm balances 31% of the time while being invariant, naming no direction and paying nothing. This file does not close the item either. It shows the 31% is FORCED by the book's own symmetry package rather than chosen, and that it is the |D| = 6 value of a quantity that vanishes as |D|^{-1/2}. """) r1, r2, r3, r4, r5, r6 = part1(), part2(), part3(), part4(), part5(), part6() rule() print(" ASSESSMENT") rule() print(f" 1. balance on the all-parallel family is a sign-sum condition : {r1}") print(f" 2. complementation invariance forces the signs i.i.d. : {r2}") print(f" 3. so P(balance) = C(n,n/2)/2^n, and 31% at |D| = 6 is forced : {r3}") print(f" 4. P(balance) <= 1/2 for ANY complementation-invariant law : {r4}") print(f" 5. scope stated: this does not derive non-balance : {r5}") print(f" 6. tamper test: the bound is carried by that symmetry alone : {r6}") print() print(""" RESULT. Non-balance stays a condition. What changes is the reach of the counterexample that keeps it one. comp 152's mu_pm balances 31% of the time at |D| = 6, and the book already gives that as the closed form C(|D|,|D|/2) 2^-|D| rather than as a bare number: the formula is not this file's contribution and an earlier version implied it was. What the book does not say is that the law is FORCED. Per-property complementation, which the book already asserts of that law, acts simply transitively on the sign vector and so forces the signs to be i.i.d. uniform. The 31% is then not a feature of the construction but the forced value C(6,3)/2^6 = 5/16, and the same formula gives C(n,n/2)/2^n at every even |D|, which goes as sqrt(2/(pi|D|)): about 1e-40 at a substrate cardinality of 1e80, and exactly zero at every ODD cardinality. Independently of that family, complementation invariance alone caps any law at P(balance) <= 1/2, by pairing each balanced configuration with the unbalanced one a single flip produces. The bound is achieved at |D| = 2. None of this is a derivation, and the file says so three ways in part 5: a probability bound is not a statement about the one configuration the substrate actually has, the vanishing is proved only for the family the counterexample lives in, and 1/2 forbids certainty rather than balance. The register entry stands as written. What the book can now say is that the obstruction does not scale, and that the symmetry package it already asserts is what stops it.""") print() return all([r1, r2, r3, r4, r5, r6]) if __name__ == "__main__": import sys # Exit only on FAILURE. The website runs these in the browser under Pyodide, # where SystemExit is fatal even at status 0: it tears the runtime down, and the # page prints ERROR after output that was in fact correct. Falling off the end # hands the build gates the same status 0, and a failure still exits 1. if not main(): sys.exit(1)