"""logic.py -- the logic a squarefree ring's own polynomials carry. QUESTION. Take a squarefree modulus M with prime set S and the ring Z/M, a product of the prime fields F_p, p in S (the CRT). Its IDEMPOTENTS are the residues reading 0 or 1 on every channel, one per subset T of S, written 1_T. The four ring polynomials AND(a, b) = ab, OR(a, b) = a + b - ab, NOT(a) = 1 - a, IMP(a, b) = 1 - a + ab are the Boolean connectives on the idempotents. What do the same polynomials do on the rest of the ring, what can a reader who applies only ring operations decide about a residue's truth, and where does that reader stop? THE ARGUMENT (written before this script). Every map built from ring operations acts channel by channel, so every statement below is a statement about one prime field F_p, lifted by the CRT. (1) THE TRUTH VALUES. A residue with a^2 = a reads 0 or 1 on every channel, since F_p has no other idempotent, so the idempotents of Z/M are the 2^|S| tuples 1_T; at a prime-power factor Z/q the only idempotents are still 0 and 1 (e(e - 1) = 0 with e and e - 1 coprime), so any modulus N has 2^omega(N) of them. The map n -> an is multiplicative iff a^2 xy = a xy for all x, y, which at x = y = 1 is a^2 = a: the multiplicative self-maps of Z/M of the form n -> an are exactly the idempotents. A product 1_T u with u a unit is a unit only if 1_T is, so only 1 = 1_S keeps any unit a unit. The MASS of T, #{x : x 1_T = x} / M, counts the residues vanishing off T: prod over T of p, over M, which is 1 / prod of the primes outside T; so mass(T and U) mass(T or U) = mass(T) mass(U). (2) THE MEADOW. Z/M is von Neumann regular (every a has an x with axa = a) iff M is squarefree: on a field take x = a^(-1) or 0; at a factor Z/q with q = p^r, r >= 2, the residue p has p x p = p only if p(px - 1) = 0 mod p^r, and px - 1 is a unit, so p = 0 mod p^r, false. The regular residues of Z/q are exactly 0 and the units. The PSEUDO-INVERSE a' inverts each nonzero channel and keeps each zero; the SUPPORT supp(a) is the set of channels where a is nonzero. Channel by channel: aa' = 1_supp(a), a'' = a, supp(a') = supp(a), supp(ab) = supp(ab') = supp(a) and supp(b); supp(a + b) contains the symmetric difference of the two supports and lies in their union; and (ab')b = a iff supp(a) lies in supp(b). (3) THE DEFECT. Write delta(a) = a^2 - a; delta(a) vanishes on channel p iff a reads 0 or 1 there. A Boolean law built from the four connectives holds on {0, 1}^n in Z, so LHS - RHS is a polynomial vanishing on {0, 1}^n; its multilinear reduction mod x_i^2 - x_i is then zero, so LHS - RHS lies in the ideal generated by the delta(x_i). Ten charted laws each carry a one-variable factor: a AND a - a = delta(a) a OR a - a = -delta(a) (a IMP a) - 1 = delta(a) (a OR NOT a) - 1 = delta(a) a AND NOT a = -delta(a) a AND (a OR b) - a = delta(a)(1 - b) a OR (a AND b) - a = -delta(a) b a AND (b OR c) - ((a AND b) OR (a AND c)) = delta(a) bc a OR (b AND c) - ((a OR b) AND (a OR c)) = -delta(a)(1 - b)(1 - c) a AND (a IMP b) - (a AND b) = -delta(a)(1 - b) and contraposition, both De Morgan laws and double negation hold as polynomial identities. The defect composes: delta(NOT a) = delta(a), delta(ab) = delta(a) delta(b) + delta(a) b + a delta(b), delta(a + b) = delta(a) + delta(b) + 2ab, each by expansion. OR and IMP are NOT-conjugates of AND, so by induction supp(delta(F)) lies in the union of the leaves' defect supports for every formula F in the four connectives, while bare + creates defect (delta(1 + 1) = 2). A non-classical x (x not 0 or 1 in F_p) becomes classical under AND with exactly two partners, 0 and x^(-1) (xy in {0, 1}); under OR with exactly 1 and 1 - (1 - x)^(-1), by conjugation; under NOT never. And a AND a = a is a^2 = a, so the relation "a AND b = a" is not even reflexive off the idempotents: the graded region has no order, and its degrees are LOCATED by channel, never ranked. (4) THE KLEENE SHADOW. Read a channel as T (1), F (0) or U (anything else). If one input is classical the connective's output class is strong Kleene's: AND with 0 is 0 and with 1 is the other input; OR dually; IMP with a = 0 or b = 1 is 1, with a = 1 it is b, with b = 0 it is NOT a. If both inputs are U, Kleene says U and the ring departs exactly when the output lands on 1 or 0: ab = 1 (b = a^(-1), itself U), a + b - ab = 0, i.e. (1 - a)(1 - b) = 1, and 1 - a + ab = 0, i.e. a(1 - b) = 1; each picks one partner per a, so p - 2 departures among the (p - 2)^2 unknown pairs, per binary connective. NOT never departs. (5) THE PAIR. With lambda = lcm(p - 1) over S, DIA(a) = a^lambda reads [a != 0] per channel and BOX(a) = 1 - (1 - a)^lambda reads [a = 1]; both land on the idempotents. DIA(NOT a) = NOT BOX(a) by definition. DIA(ab) = DIA a AND DIA b because F_p has no zero divisors; BOX(a OR b) = BOX a OR BOX b because (1 - a)(1 - b) = 0 iff a = 1 or b = 1. On the dual connective each leaks one way: DIA(a OR b) < DIA a OR DIA b exactly when a, b != 0 and (1 - a)(1 - b) = 1, which is p - 2 of the (p - 1)^2 pairs of nonzero inputs; BOX(a AND b) > BOX a AND BOX b exactly when ab = 1 with a != 1, also p - 2 pairs, and (a, b) -> (1 - a, 1 - b) carries the first set onto the second. So DIA can lose truth over OR and never create it. The gap DIA a - BOX a is DIA(delta(a)) = DIA a AND DIA(NOT a): the channels read "true to some degree and false to some degree" are the defect's support. The monadic laws BOX a AND a = BOX a, DIA a AND a = a, DIA and BOX idempotent and fixing each other's outputs, BOX(a IMP b) AND BOX a <= BOX b, and DIA(a AND DIA b) = DIA a AND DIA b hold channel by channel. THE WALL: once |S| >= 2 no polynomial computes the whole-ring test [a = 0 in Z/M] (NOT DIA a is the per-channel one); a polynomial's channel-p value depends on a mod p only, and a = 0 and a = 1_(S minus p) agree at p while the test reads 1 and 0. (6) THE ENVELOPE. Push NOT to the leaves (De Morgan is an identity). Per leaf keep only the two bits DIA a and BOX a; let the ROOF U evaluate the AND/OR tree in Boolean logic with DIA a at a positive leaf and NOT BOX a at a negated one, the FLOOR L with BOX a and NOT DIA a. Then channel by channel L <= BOX F <= DIA F <= U by induction: at a literal the conjugacy makes both ends exact; at AND, DIA is exact and BOX only gains; at OR, BOX is exact and DIA only loses; so the two leak directions are the two inequality slots. U = 0 certifies F false, L = 1 fully true. On a channel where every leaf is classical, U = L = F. SHARPNESS, read-once. Record a formula by (value set, U, L), the value set being every value F takes over inputs with its leaves' measured bits. The leaves of a read-once formula are independent, so AND and OR combine value sets as a product. The leaf classes are {0}, {1} and the graded set G = F_p minus {0, 1}, with bits (0, 0), (1, 1), (1, 0), and NOT permutes them. For p >= 5, |G| = p - 2 > (p - 1)/2, so for each unit t the sets G and tG^-1 meet: G*G = F_p^*, and by conjugation G OR G = F_p minus {1}. Every record with (U, L) = (1, 0) contains G (AND with {1} and OR with {0} keep a record, AND with {0} and OR with {1} send it to {0} or {1}), so a product of two such holds F_p^*, and 0 iff a factor does. The closure is six records: {0}, {1}, and (X, 1, 0) for X = G, F_p^*, F_p minus {1}, F_p. Each is achieved, since a (1, 0) set holds a graded value, neither 0 nor 1. So at p >= 5 every read-once formula of any size reaches both ends. At p = 3, G = {-1}, G*G = {1} and G OR G = {0}: forced, the rigidity. Repeated leaves break it at every p >= 3: the (p - 1)-fold AND of a leaf is a^(p - 1), 1 at every graded input, so at a graded leaf the floor 0 is never reached, and its OR dual misses the roof. (Checked after the record below, as V3.) (7) THE LADDER. For m dividing lambda let G_m(a) = BOX(a^m): per channel it reads [a^m = 1], i.e. a != 0 and ord(a) | m. G_1 = BOX and G_lambda = DIA; m | d gives G_m <= G_d; G_gcd(m, d) = G_m AND G_d, since ord | m and ord | d iff ord | gcd. The join G_m OR G_d equals G_lcm(m, d) iff on EVERY CHANNEL each divisor of p - 1 that divides the lcm divides m or d; the ring's own orders do not decide it (2 has order 12 in Z/35, yet there G_4 OR G_6 = G_12, channel 5 holding orders 1, 2, 4 and channel 7 orders 1, 2, 3, 6). The least lcm that can leak is lcm(2, 3) = 6, and it leaks exactly when a channel has p = 1 mod 3. The power map x -> x^r has prod over S of (1 + gcd(r - 1, p - 1)) fixed points (0, or x^(r-1) = 1 in a cyclic group of order p - 1). The map x -> x^j is idempotent on Z/M iff x^(j^2) = x^j for all x, iff j^2 = j mod lambda (taking j in 1..lambda): 2^omega(lambda) such maps, the idempotents of Z/lambda. (8) THE ORDER-6 SHADOW. BOX(a AND NOT a) reads [a(1 - a) = 1] = [a^2 - a + 1 = 0] = [Phi_6(a) = 0]. For p > 3 the roots of Phi_6 in F_p are the elements of order 6, present iff 6 | p - 1, i.e. p = 1 mod 3 (the primes splitting in Q(zeta_6)); at p = 2 there is none; at p = 3, Phi_6 = (x + 1)^2, one double root -1 of order 2 (3 ramifies: Phi_6's discriminant is -3). Every graded residue has the pair bits (1, 0), so the pair decides this shadow on a channel iff the shadow is constant on the graded residues: at p = 1 mod 3 it is not (order-6 elements read 1, others 0); at p = 2 mod 3 it is constantly 0; at p = 3 the graded region is the single point -1, which reads 1. The ladder reads it as G_6 AND NOT(G_2 OR G_3) at every p but the point -1 of p = 3, where gcd(6, p - 1) = 2 folds G_6 onto G_2. The pair does not pin that point, since -1 at p = 5 carries the same bits; the pin G_2(a) AND NOT BOX(a) AND G_2(NOT a) does, a = -1 with NOT a = 2 of order at most 2, which is p = 3, so the ladder formula OR the pin reads the shadow at every channel. (Checked after the record below, as L4's fourth line.) (9) THE LADDER'S REACH. A one-leaf reader applying the ladder to a and to NOT a sees exactly the pair (ord a, ord(1 - a)), 0 read as order 0. A shadow that is not a function of that pair escapes it, and two inputs with equal pairs and unequal shadows prove the escape. Two leaves: [ab = 1] depends on the relation between a and b, which no pair of one-leaf profiles holds. DESIGN. Seven sections of checks printing PASS or FAIL; per channel the checks run over every residue (or pair, or triple) of F_p for the primes stated, and ring-level checks through the CRT, exhaustive or sampled, read the lifting on Z/2310, Z/510510 and Z/1001 = 7 * 11 * 13, not a product of the first primes. E the truth values. The idempotent count against 2^omega(M) for every M in 2..3000, squarefree or not; the multiplicative maps n -> an against the idempotents over the full grid of x, y for every M <= 40; the unit test at Z/2310; the mass of all 32 T at Z/2310 by counting, and the product law over all pairs. M the meadow. Regularity by search for every M in 2..200 against squarefreeness; the regular residues of every prime power q = p^r <= 400, r >= 2, against {0} and the units. POSITIVE CONTROL: the search must find a non-regular residue at M = 12. Then the pseudo-inverse laws over all of Z/2310, and the support laws over every pair of Z/210 and 20,000 pairs of Z/510510. C the connectives and the defect. Boolean on the 32 idempotents of Z/2310, the residuation law (x AND a) <= b iff x <= (a IMP b) over all 32^3 triples. The ten deformations and the four identities over every triple of F_p, p <= 13, and of Z/30. The three composition laws over every pair of F_p, p <= 23. No creation over 5,000 random formulas to depth 4 on Z/510510, each leaf classical on an odd channel with probability 0.85 (on 2 always), a formula's defect support read against the union over the leaves it reads; CONTROL first: the same detector must see bare + create defect, 1 + 1 from the classical leaf 1. The AND and OR partners of every non-classical x, p <= 23, as sets. Reflexivity fails exactly off the idempotents of Z/2310. K the Kleene shadow. Every pair of F_p, p <= 23, every connective: mismatches with a classical input, and departures among U-U pairs. POSITIVE CONTROL: at p = 2 the two tables agree on every pair. Q the pair, per channel over every residue and pair, p <= 23 (the channel exponent is p - 1, which lambda is a multiple of), and 10,000 ring samples each on Z/510510 and Z/1001. The wall by its witness at Z/30; that a polynomial is channel-local is the wall's proof and is not run. V the envelope, by CLOSURE. Every leaf is a record (value, U, L, classical); AND and OR act on records; the set of records reachable from the leaves of F_p is closed under both, so the sandwich checked on the closure holds for every NNF formula of any size, repeated leaves included (the check is per input). p <= 23. Then SHARPNESS for read-once formulas, by CLOSURE too: a record is (value set, U, L), a leaf's value set being all residues of its measured class, and read-once AND/OR combine the sets as an independent product; the envelope is ACHIEVED when U = 1 implies a nonzero value in the set and L = 0 a value other than 1. The fixpoint under both operations holds every read-once formula's record, at every prime 3 <= p <= 97, and is compared with the six records the argument names. POSITIVE CONTROL: p = 3. L the ladder, on every residue of the seven channels of Z/510510 for every m | 240 (its lambda, a multiple of each p - 1 there): G_m against [ord | m], the ends, monotony, meet-exactness, the least defective lcm over all divisor pairs; G_2 OR G_3 against G_6 at every p <= 199; on 3000 samples of Z/510510, the 20 gates distinct as maps. The fixed-point count over all of Z/M for M in {30, 210, 1001, 2310}, r in 2..30. The idempotent power maps over all of Z/2310 (lambda 60) and Z/1001 (lambda 60), j in 1..60. The order-6 shadow at every p <= 199; the pair's blindness per p <= 199; the ladder formula at every (p, x), p <= 23, and the pin's support at every p <= 199. The reach: the first p <= 100 where [a^2(1 - a) = 1] is not a function of (ord a, ord(1 - a)), and CONTROL: Phi_6's shadow never is; the [ab = 1] witness at p = 7. PREDICTIONS, fixed before the run. E1 0 exceptions to 2^omega(M) over 2999 moduli. E2 the maps equal the idempotents at every M <= 40. E3 only 1_S keeps a unit. E4 32 masses equal 1 / prod(outside), the product law on all 1024 pairs. M0 the control finds exactly the residues of Z/12 reading 2 mod 4: 2, 6 and 10. M1 regular iff squarefree, 0 exceptions over 199 moduli; M2 the regular residues are {0} and the units at every prime power. M3 the pseudo-inverse laws hold on all 2310 residues. M4 the support laws hold on all 44,100 pairs and 20,000 samples. C1 Boolean on 32 idempotents, residuation on 32,768 triples. C2 all fourteen polynomial statements, zero exceptions. C3 composition, zero exceptions. C4 no creation, zero escapes; the control creates. C5 the AND partners of a non-classical x are 0 and 1/x, the OR partners 1 and 1 - 1/(1 - x). C6 a AND a = a exactly on the 32 idempotents of Z/2310. K1 zero classical-input mismatches; exactly p - 2 U-U departures per binary connective at every odd p <= 23; NOT none. K0 p = 2 agrees everywhere. Q1 DIA and BOX read [a != 0] and [a = 1]; DIA exact on AND and BOX on OR; the leaks are the sets the argument names, p - 2 each, and the bijection; the gap identity; the monadic laws: all zero exceptions. Q2 the wall's witness at Z/30 is 1_{3,5} = 16: 0 mod 2, 1 mod 3 and mod 5. V1 the sandwich holds on every closure record at every p <= 23, and U = L = value on every all-classical record; closures are finite and small (p + 4 records at odd p, 2 at p = 2). V2 sharpness: at every prime 5 <= p <= 97 the read-once closure is exactly the six predicted records, none unachieved. V0 at p = 3 the closure is five records, the singletons {0}, {1}, {-1} under (U, L) = (1, 0) beside {0} and {1} classical, two of them unachieved. L1 G_m = [ord | m] on every channel residue; G_240 = DIA (G_1 = BOX by definition); monotone, meet-exact; least defective lcm 6, and G_2 OR G_3 below G_6 exactly at the p = 1 mod 3; 20 distinct gates. L2 fixed-point counts match the product everywhere. L3 the idempotent power maps are the 8 solutions of j^2 = j mod 60 at both moduli. L4 Phi_6's shadow is [ord = 6] at every p != 3, and [a = -1] at p = 3; the pair is blind exactly at the p = 1 mod 3; the ladder formula agrees at every (p, x) but (3, -1), and the pin holds there alone. L5 the first collision of [a^2(1 - a) = 1] is at p = 11; Phi_6 never collides; the [ab = 1] witness a = 3, b = 5, b' = 3 at p = 7 has equal profiles (6, 6) and shadows 1 and 0. FINDINGS. Every prediction landed: 45/45 checks PASS. Added after the first run: the Z/35 join, V3, L4's fourth line and the controls read through the detectors; dropped: conjugacy and the polynomial locality, both true by construction. E 2^omega(M) with no exception over M = 2..3000; the maps n -> an are the idempotents at every M <= 40; one idempotent (1) keeps a unit; 32 masses and the product law on 1024 pairs. M the control's non-regular residues of Z/12 are [2, 6, 10]; regular iff squarefree with no exception over M = 2..200; 19 prime powers, regular exactly at 0 and the units; the pseudo-inverse laws on all of Z/2310; the support laws on every pair of Z/210 and 20,000 of Z/510510. C Boolean on 32 idempotents and residuation on 32^3 triples; all 14 polynomial statements with no failure; the composition laws on every pair, p <= 23; the detector sees 1 + 1 create defect, and 0 escapes over 5,000 formulas; the partners as predicted; a AND a = a on exactly the 32 idempotents. K p = 2 agrees everywhere; departures 1/1, 3/9, 5/25, 9/81, 11/121, 15/225, 17/289, 21/441 at p = 3..23, p - 2 each, AND, OR and IMP alike; no classical-input mismatch; NOT none. Q the reads, exactness, leaks with the bijection, gap and monadic laws on every residue and pair, p <= 23; the ring reads on 10,000 samples each of Z/510510 and Z/1001; the wall's witness is 16. V closures of 2, 7, 9, 11, 15, 17, 21, 23, 27 records at p = 2, 3, ..., 23, the sandwich and the classical collapse on every record: a proof for every NNF formula of any size. Read-once sharpness by closure: the control at p = 3 closes at 5 records, 2 unachieved, the rigidity; at all 23 primes 5 <= p <= 97 the closure is exactly the six predicted records, none unachieved, the finite check of an argument that holds at every p >= 5. L the gates read the order on every residue of the seven channels for all 20 m | 240, the ends, monotony and meets exact; the least leaking lcm is 6, G_2 OR G_3 leaking at the 21 primes p = 1 mod 3 up to 199 alone; 20 distinct gates; the fixed-point product at four moduli for r = 2..30; 8 idempotent power maps at both lambda = 60 moduli; the order-6 shadow at every p <= 199; the pair blind at exactly the 21 primes p = 1 mod 3 up to 199 (first 7, 13, 19, 31); the ladder formula off only at (3, 2), which is -1 at p = 3, and the pin true there alone; the first collision of [a^2(1 - a) = 1] at p = 11, none for Phi_6; the [ab = 1] witness holds. RUN RECORD. 0.9 s wall, peak commit 11.4 MB (memory guard, limit 512 MB). Run: python logic.py -- seconds, a few MB. """ import random from itertools import product from math import gcd, prod CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) def is_prime(n): return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1)) PRIMES = [p for p in range(2, 400) if is_prime(p)] ODD23 = [p for p in PRIMES if 3 <= p <= 23] def prime_factors(n): out, d = {}, 2 while d * d <= n: while n % d == 0: out[d] = out.get(d, 0) + 1 n //= d d += 1 if n > 1: out[n] = out.get(n, 0) + 1 return out def squarefree(n): return all(e == 1 for e in prime_factors(n).values()) def lam(M): out = 1 for p in prime_factors(M): out = out * (p - 1) // gcd(out, p - 1) return out # The connectives, on Z/M for any M. def AND(a, b, M): return a * b % M def OR(a, b, M): return (a + b - a * b) % M def NOT(a, M): return (1 - a) % M def IMP(a, b, M): return (1 - a + a * b) % M def delta(a, M): return (a * a - a) % M def DIA(a, M, L): return pow(a, L, M) def BOX(a, M, L): return (1 - pow((1 - a) % M, L, M)) % M def supp(a, S): return frozenset(p for p in S if a % p) def idem(T, S, M): """1_T: the residue reading 1 on T and 0 on the rest of S.""" x = 0 for p in S: if p in T: q = M // p x += q * pow(q, -1, p) return x % M def pinv(a, S, M): """The pseudo-inverse: invert each nonzero channel, keep each zero.""" x = 0 for p in S: r = a % p if r: q = M // p x += pow(r, -1, p) * q * pow(q, -1, p) return x % M def order(x, p): if x % p == 0: return 0 k, y = 1, x % p while y != 1: y = y * x % p k += 1 return k def section_e(): print("E the truth values") bad = [M for M in range(2, 3001) if sum(1 for x in range(M) if x * x % M == x) != 2 ** len(prime_factors(M))] check("E1 idempotent count = 2^omega(M), M = 2..3000", not bad, f"exceptions {bad[:5]}") ok = True for M in range(2, 41): maps = {a for a in range(M) if all(a * x * (a * y) % M == a * (x * y) % M for x in range(M) for y in range(M))} ok &= maps == {x for x in range(M) if x * x % M == x} check("E2 multiplicative n -> an are the idempotents, M <= 40", ok) S, M = (2, 3, 5, 7, 11), 2310 units = [u for u in range(M) if gcd(u, M) == 1] Ts = [frozenset(c for c, b in zip(S, bits) if b) for bits in product((0, 1), repeat=len(S))] keep = [T for T in Ts if any(gcd(idem(T, S, M) * u % M, M) == 1 for u in units)] check("E3 only 1_S keeps a unit a unit, Z/2310", keep == [frozenset(S)], f"{len(keep)} keeper(s)") mass = {} for T in Ts: e = idem(T, S, M) mass[T] = sum(1 for x in range(M) if x * e % M == x) / M ok1 = all(abs(mass[T] - 1 / prod(p for p in S if p not in T)) < 1e-12 for T in Ts) ok2 = all(abs(mass[T & U] * mass[T | U] - mass[T] * mass[U]) < 1e-12 for T in Ts for U in Ts) check("E4 mass(T) = 1/prod(primes outside T), product law", ok1 and ok2, f"{len(Ts)} masses, {len(Ts) ** 2} pairs") def section_m(): print("M the meadow") def regular(r, M): return any(r * x * r % M == r for x in range(M)) ctl = [r for r in range(12) if not regular(r, 12)] check("M0 CONTROL the search finds non-regular residues at M = 12", ctl == [2, 6, 10], f"non-regular {ctl}") bad = [M for M in range(2, 201) if all(regular(r, M) for r in range(M)) != squarefree(M)] check("M1 Z/M regular iff M squarefree, M = 2..200", not bad, f"exceptions {bad[:5]}") ok, n = True, 0 for p in PRIMES: q = p * p while q <= 400: reg = {r for r in range(q) if regular(r, q)} ok &= reg == {0} | {r for r in range(q) if r % p} n += 1 q *= p check("M2 regular residues of p^r (r >= 2) are 0 and the units", ok, f"{n} prime powers") S, M = (2, 3, 5, 7, 11), 2310 ok = True for a in range(M): b = pinv(a, S, M) ok &= (a * b * a % M == a and b * a * b % M == b and pinv(b, S, M) == a and a * b % M == idem(supp(a, S), S, M)) check("M3 aa'a = a, a'aa' = a', a'' = a, aa' = 1_supp(a), Z/2310", ok) def support_laws(a, b, S, M): sa, sb, bi = supp(a, S), supp(b, S), pinv(b, S, M) s_sum = supp(a + b, S) return (supp(a * b, S) == sa & sb and supp(a * bi, S) == sa & sb and supp(pinv(a, S, M), S) == sa and (sa ^ sb) <= s_sum <= (sa | sb) and ((a * bi * b % M == a) == (sa <= sb))) S2, M2 = (2, 3, 5, 7), 210 ok = all(support_laws(a, b, S2, M2) for a in range(M2) for b in range(M2)) rng = random.Random(1) S7, M7 = (2, 3, 5, 7, 11, 13, 17), 510510 ok2 = all(support_laws(rng.randrange(M7), rng.randrange(M7), S7, M7) for _ in range(20000)) check("M4 support laws: all pairs of Z/210, 20,000 of Z/510510", ok and ok2) LAWS = [ # (name, lhs - rhs, the stated deformation), on F_p or Z/M ("AND idempotence", lambda a, b, c, M: AND(a, a, M) - a, lambda a, b, c, M: delta(a, M)), ("OR idempotence", lambda a, b, c, M: OR(a, a, M) - a, lambda a, b, c, M: -delta(a, M)), ("a IMP a", lambda a, b, c, M: IMP(a, a, M) - 1, lambda a, b, c, M: delta(a, M)), ("excluded middle", lambda a, b, c, M: OR(a, NOT(a, M), M) - 1, lambda a, b, c, M: delta(a, M)), ("contradiction", lambda a, b, c, M: AND(a, NOT(a, M), M), lambda a, b, c, M: -delta(a, M)), ("absorption AND", lambda a, b, c, M: AND(a, OR(a, b, M), M) - a, lambda a, b, c, M: delta(a, M) * (1 - b)), ("absorption OR", lambda a, b, c, M: OR(a, AND(a, b, M), M) - a, lambda a, b, c, M: -delta(a, M) * b), ("distributivity AND", lambda a, b, c, M: AND(a, OR(b, c, M), M) - OR(AND(a, b, M), AND(a, c, M), M), lambda a, b, c, M: delta(a, M) * b * c), ("distributivity OR", lambda a, b, c, M: OR(a, AND(b, c, M), M) - AND(OR(a, b, M), OR(a, c, M), M), lambda a, b, c, M: -delta(a, M) * (1 - b) * (1 - c)), ("modus ponens", lambda a, b, c, M: AND(a, IMP(a, b, M), M) - AND(a, b, M), lambda a, b, c, M: -delta(a, M) * (1 - b)), ("contraposition", lambda a, b, c, M: IMP(a, b, M) - IMP(NOT(b, M), NOT(a, M), M), lambda a, b, c, M: 0), ("De Morgan AND", lambda a, b, c, M: NOT(AND(a, b, M), M) - OR(NOT(a, M), NOT(b, M), M), lambda a, b, c, M: 0), ("De Morgan OR", lambda a, b, c, M: NOT(OR(a, b, M), M) - AND(NOT(a, M), NOT(b, M), M), lambda a, b, c, M: 0), ("double negation", lambda a, b, c, M: NOT(NOT(a, M), M) - a, lambda a, b, c, M: 0), ] def random_formula(rng, leaves, depth): if depth == 0 or rng.random() < 0.3: return ("leaf", rng.randrange(leaves)) op = rng.choice(("AND", "OR", "NOT", "IMP")) if op == "NOT": return (op, random_formula(rng, leaves, depth - 1)) return (op, random_formula(rng, leaves, depth - 1), random_formula(rng, leaves, depth - 1)) def leaves(f): if f[0] == "leaf": return {f[1]} return set().union(*(leaves(g) for g in f[1:])) def evaluate(f, xs, M): if f[0] == "leaf": return xs[f[1]] if f[0] == "NOT": return NOT(evaluate(f[1], xs, M), M) a, b = evaluate(f[1], xs, M), evaluate(f[2], xs, M) return {"AND": AND, "OR": OR, "IMP": IMP}[f[0]](a, b, M) def section_c(): print("C the connectives and the defect") S, M = (2, 3, 5, 7, 11), 2310 Ts = [frozenset(c for c, b in zip(S, bits) if b) for bits in product((0, 1), repeat=len(S))] e = {T: idem(T, S, M) for T in Ts} inv = {v: T for T, v in e.items()} ok = all(inv.get(AND(e[T], e[U], M)) == T & U and inv.get(OR(e[T], e[U], M)) == T | U and inv.get(NOT(e[T], M)) == frozenset(S) - T and inv.get(IMP(e[T], e[U], M)) == (frozenset(S) - T) | U for T in Ts for U in Ts) le = lambda x, y: AND(x, y, M) == x ok2 = all(le(AND(e[X], e[A], M), e[B]) == le(e[X], IMP(e[A], e[B], M)) for X in Ts for A in Ts for B in Ts) check("C1 Boolean on the 32 idempotents; residuation on 32^3 triples", ok and ok2) bad = [] rings = [p for p in PRIMES if p <= 13] + [30] for name, lhs, dfm in LAWS: for M_ in rings: for a, b, c in product(range(M_), repeat=3): if (lhs(a, b, c, M_) - dfm(a, b, c, M_)) % M_: bad.append((name, M_)) break check("C2 the ten deformations and the four identities, F_p p <= 13 " "and Z/30", not bad, f"{len(LAWS)} statements, failures {bad[:3]}") ok = True for p in [2] + ODD23: for a, b in product(range(p), repeat=2): da, db = delta(a, p), delta(b, p) ok &= delta(NOT(a, p), p) == da ok &= delta(a * b % p, p) == (da * db + da * b + a * db) % p ok &= delta((a + b) % p, p) == (da + db + 2 * a * b) % p check("C3 the three composition laws, every pair of F_p, p <= 23", ok) S7, M7 = (2, 3, 5, 7, 11, 13, 17), 510510 def creates(v, read): allowed = frozenset().union(*(supp(delta(x, M7), S7) for x in read)) return not supp(delta(v, M7), S7) <= allowed def mostly_classical(rng): x = 0 for p in S7: r = (rng.randrange(2) if p == 2 or rng.random() < 0.85 else rng.randrange(2, p)) q = M7 // p x += r * q * pow(q, -1, p) return x % M7 ctl = creates((1 + 1) % M7, [1]) check("C4 CONTROL the detector sees bare + create defect", ctl, f"1 + 1 from the leaf 1 at Z/510510") rng = random.Random(2) escapes = 0 for _ in range(5000): f = random_formula(rng, 3, 4) xs = [mostly_classical(rng) for _ in range(3)] escapes += creates(evaluate(f, xs, M7), [xs[i] for i in leaves(f)]) check("C4 no creation over 5,000 formulas on Z/510510", escapes == 0, f"{escapes} escapes") ok = True cls = lambda v: v in (0, 1) for p in ODD23: for x in range(2, p): ok &= {y for y in range(p) if cls(x * y % p)} \ == {0, pow(x, -1, p)} ok &= {y for y in range(p) if cls(OR(x, y, p))} \ == {1, (1 - pow(1 - x, -1, p)) % p} check("C5 the AND partners 0 and 1/x, the OR partners 1 and " "1 - 1/(1 - x); p <= 23", ok) refl = [a for a in range(M) if AND(a, a, M) == a] check("C6 a AND a = a exactly on the idempotents of Z/2310", sorted(refl) == sorted(e.values()), f"{len(refl)} residues") def k3(op, x, y): """Strong Kleene on classes 0 (F), 1 (T), None (U).""" if op == "NOT": return None if x is None else 1 - x if op == "AND": if x == 0 or y == 0: return 0 return 1 if (x, y) == (1, 1) else None if op == "OR": if x == 1 or y == 1: return 1 return 0 if (x, y) == (0, 0) else None return k3("OR", k3("NOT", x, None), y) # IMP def section_k(): print("K the Kleene shadow") cls = lambda v: v if v in (0, 1) else None fns = {"AND": AND, "OR": OR, "IMP": IMP} agree = all(cls(fns[op](a, b, 2)) == k3(op, a, b) for op in fns for a in range(2) for b in range(2)) check("K0 CONTROL p = 2: ring and Kleene agree on every pair", agree) ok, rows = True, [] for p in ODD23: dep = {} for op, f in fns.items(): mis = sum(1 for a, b in product(range(p), repeat=2) if (cls(a) is not None or cls(b) is not None) and cls(f(a, b, p)) != k3(op, cls(a), cls(b))) dep[op] = sum(1 for a, b in product(range(2, p), repeat=2) if cls(f(a, b, p)) is not None) ok &= mis == 0 and dep[op] == p - 2 ok &= all(cls(NOT(a, p)) == k3("NOT", cls(a), None) for a in range(p)) rows.append(f"{p}:{dep['AND']}/{(p - 2) ** 2}") check("K1 classical inputs Kleene; U-U departures p - 2 per " "connective; NOT none", ok, " ".join(rows)) def section_q(): print("Q the pair") ok = {k: True for k in "read exact leak gap modal".split()} for p in [2] + ODD23: L = p - 1 D = lambda a: DIA(a, p, L) B = lambda a: BOX(a, p, L) for a in range(p): ok["read"] &= D(a) == (a != 0) and B(a) == (a == 1) ok["gap"] &= (D(a) - B(a)) == D(delta(a, p)) \ == AND(D(a), D(NOT(a, p)), p) ok["modal"] &= (AND(B(a), a, p) == B(a) and AND(D(a), a, p) == a and D(D(a)) == D(a) and B(B(a)) == B(a) and B(D(a)) == D(a) and D(B(a)) == B(a)) or_set, and_set = set(), set() for a, b in product(range(p), repeat=2): ok["exact"] &= (D(AND(a, b, p)) == AND(D(a), D(b), p) and B(OR(a, b, p)) == OR(B(a), B(b), p)) ok["modal"] &= AND(AND(B(IMP(a, b, p)), B(a), p), B(b), p) \ == AND(B(IMP(a, b, p)), B(a), p) ok["modal"] &= D(AND(a, D(b), p)) == AND(D(a), D(b), p) if D(OR(a, b, p)) != OR(D(a), D(b), p): ok["leak"] &= D(OR(a, b, p)) < OR(D(a), D(b), p) or_set.add((a, b)) if B(AND(a, b, p)) != AND(B(a), B(b), p): ok["leak"] &= B(AND(a, b, p)) > AND(B(a), B(b), p) and_set.add((a, b)) ok["leak"] &= len(or_set) == len(and_set) == max(p - 2, 0) ok["leak"] &= or_set == {(a, b) for a, b in product(range(1, p), repeat=2) if (1 - a) * (1 - b) % p == 1} ok["leak"] &= and_set == {(a, b) for a, b in product(range(p), repeat=2) if a * b % p == 1 and a != 1} ok["leak"] &= {((1 - a) % p, (1 - b) % p) for a, b in or_set} == and_set for k, v in ok.items(): check(f"Q1 {k}, every residue and pair, p <= 23", v) rng = random.Random(3) good = True for S, M in (((2, 3, 5, 7, 11, 13, 17), 510510), ((7, 11, 13), 1001)): Lm = lam(M) for _ in range(10000): a, b = rng.randrange(M), rng.randrange(M) good &= supp(DIA(a, M, Lm), S) == supp(a, S) good &= DIA(a, M, Lm) == idem(supp(a, S), S, M) good &= BOX(a, M, Lm) == idem(frozenset( p for p in S if a % p == 1), S, M) good &= DIA(AND(a, b, M), M, Lm) == AND(DIA(a, M, Lm), DIA(b, M, Lm), M) check("Q1 ring level: DIA = 1_supp, BOX = 1_{a = 1}, AND-exact; " "Z/510510 and Z/1001", good, "10,000 samples each") S3, M3 = (2, 3, 5), 30 w = idem(frozenset({3, 5}), S3, M3) wall = w == 16 and w % 2 == 0 and w % 3 == 1 and w % 5 == 1 check("Q2 the wall's witness 1_{3,5} is 16: 0 mod 2, 1 mod 3 and mod 5", wall, f"witness {w}") def env_leaf(p, v, neg): """A leaf record (value, U, L, classical) for the literal at value v.""" L = p - 1 d, b = int(DIA(v, p, L) == 1), int(BOX(v, p, L) == 1) val = NOT(v, p) if neg else v U, Lo = (1 - b, 1 - d) if neg else (d, b) return (val, U, Lo, v in (0, 1)) def env_combine(r, s, op, p): if op == "AND": return (r[0] * s[0] % p, r[1] & s[1], r[2] & s[2], r[3] and s[3]) return (OR(r[0], s[0], p), r[1] | s[1], r[2] | s[2], r[3] and s[3]) def section_v(): print("V the envelope") ok, sizes = True, [] for p in [2] + ODD23: recs = {env_leaf(p, v, n) for v in range(p) for n in (0, 1)} while True: new = {env_combine(r, s, op, p) for r in recs for s in recs for op in ("AND", "OR")} - recs if not new: break recs |= new for v, U, Lo, cl in recs: dia, box = int(v != 0), int(v == 1) ok &= Lo <= box <= dia <= U if cl: ok &= U == Lo == v and v in (0, 1) ok &= len(recs) == (2 if p == 2 else p + 4) sizes.append(f"{p}:{len(recs)}") check("V1 L <= BOX F <= DIA F <= U on the closure, every NNF formula; " "U = L = F on classical inputs, p <= 23", ok, " ".join(sizes)) results = {} for p in [q for q in PRIMES if 3 <= q <= 97]: G = frozenset(range(2, p)) recs = {(frozenset({0}), 0, 0), (frozenset({1}), 1, 1), (G, 1, 0)} while True: # NOT permutes the leaf classes, so these suffice new = set() for r in recs: for s in recs: new.add((frozenset(x * y % p for x in r[0] for y in s[0]), r[1] & s[1], r[2] & s[2])) new.add((frozenset(OR(x, y, p) for x in r[0] for y in s[0]), r[1] | s[1], r[2] | s[2])) new -= recs if not new: break recs |= new bad = [r for r in recs if (r[1] == 1 and not any(v != 0 for v in r[0])) or (r[2] == 0 and not any(v != 1 for v in r[0]))] results[p] = (recs, len(bad)) recs3, bad3 = results[3] want3 = {(frozenset({0}), 0, 0), (frozenset({1}), 1, 1)} | { (frozenset({v}), 1, 0) for v in (0, 1, 2)} check("V0 CONTROL p = 3: five read-once records, two unachieved", recs3 == want3 and bad3 == 2, f"{len(recs3)} records, {bad3} unachieved") ok, off = True, [] for p, (recs, nbad) in results.items(): if p == 3: continue F, units = frozenset(range(p)), frozenset(range(1, p)) want = {(frozenset({0}), 0, 0), (frozenset({1}), 1, 1)} | { (X, 1, 0) for X in (frozenset(range(2, p)), units, F - {1}, F)} if recs != want or nbad: ok = False off.append(p) check("V2 read-once closure is the six predicted records, all " "achieved, every prime 5 <= p <= 97", ok, f"{len(results) - 1} primes, off at {off}") ok = True for p in [q for q in PRIMES if 3 <= q <= 97]: for a in range(2, p): f, g = a, a for _ in range(p - 2): f, g = AND(f, a, p), OR(g, a, p) ok &= f == 1 and g == 0 # Fermat's a^(p-1) = 1 and its NOT-mirror: fails only on a # mistyped connective check("V3 repeated leaves: the (p - 1)-fold AND of a graded leaf is 1 " "and the OR 0, so an end is missed, every prime 3 <= p <= 97", ok) def divisors(n): return [d for d in range(1, n + 1) if n % d == 0] def section_l(): print("L the ladder") D240 = divisors(240) ok = {k: True for k in "gate ends mono meet".split()} least_bad = None for p in (2, 3, 5, 7, 11, 13, 17): L = p - 1 G = lambda a, m: BOX(pow(a, m, p), p, L) for a in range(p): o = order(a, p) for m in D240: ok["gate"] &= G(a, m) == (o != 0 and m % o == 0) ok["ends"] &= G(a, 240) == DIA(a, p, L) for m in D240: for m2 in D240: if m2 % m == 0: ok["mono"] &= G(a, m) <= G(a, m2) ok["meet"] &= G(a, gcd(m, m2)) == AND(G(a, m), G(a, m2), p) lc = m * m2 // gcd(m, m2) if OR(G(a, m), G(a, m2), p) != G(a, lc): if least_bad is None or lc < least_bad: least_bad = lc for k, v in ok.items(): check(f"L1 {k}, every residue of the seven channels, every m | 240", v) leaks, below = [], True for p in [q for q in PRIMES if q <= 199]: G = lambda a, m: BOX(pow(a, m, p), p, p - 1) below &= all(OR(G(a, 2), G(a, 3), p) <= G(a, 6) for a in range(p)) if any(OR(G(a, 2), G(a, 3), p) != G(a, 6) for a in range(p)): leaks.append(p) # below 6 every lcm of two divisors is one of them, so a leak at 6 # is the least one check("L1 a gate join leaks at lcm 6 on the seven channels; G_2 OR " "G_3 leaks exactly at the p = 1 mod 3, p <= 199, below G_6", least_bad == 6 and below and leaks == [p for p in PRIMES if p <= 199 and p % 3 == 1], f"lcm {least_bad}; {len(leaks)} leaking primes") M, L35 = 35, 12 G35 = lambda a, m: BOX(pow(a, m, M), M, L35) o12 = pow(2, 12, M) == 1 and all(pow(2, k, M) != 1 for k in (4, 6)) join = all(OR(G35(a, 4), G35(a, 6), M) == G35(a, 12) for a in range(M)) check("L1 Z/35: 2 has order 12, and still G_4 OR G_6 = G_12, the " "join read per channel", o12 and join) M7 = 510510 rng = random.Random(4) sample = [rng.randrange(M7) for _ in range(3000)] maps = {m: tuple(BOX(pow(a, m, M7), M7, 240) for a in sample) for m in D240} check("L1 the 20 gates are distinct maps on Z/510510", len(set(maps.values())) == 20 == len(D240), f"{len(set(maps.values()))} distinct on 3000 residues") ok = True for M in (30, 210, 1001, 2310): ps = prime_factors(M) for r in range(2, 31): ok &= sum(1 for x in range(M) if pow(x, r, M) == x) == \ prod(1 + gcd(r - 1, p - 1) for p in ps) check("L2 fixed points of x^r = prod(1 + gcd(r - 1, p - 1))", ok, "M in {30, 210, 1001, 2310}, r = 2..30") ok = True for M in (2310, 1001): Lm = lam(M) found = [j for j in range(1, Lm + 1) if all(pow(x, j * j, M) == pow(x, j, M) for x in range(M))] ok &= found == [j for j in range(1, Lm + 1) if (j * j - j) % Lm == 0] ok &= len(found) == 2 ** len(prime_factors(Lm)) check("L3 idempotent power maps = j^2 = j mod lambda, 2^omega(lambda)", ok, "Z/2310 and Z/1001, lambda 60") ok_shadow, blind = True, [] for p in [q for q in PRIMES if q <= 199]: L = p - 1 sh = {a: BOX(AND(a, NOT(a, p), p), p, L) for a in range(p)} phi6 = {a: int((a * a - a + 1) % p == 0) for a in range(p)} ok_shadow &= sh == phi6 if p != 3: ok_shadow &= all(phi6[a] == (order(a, p) == 6) for a in range(p)) else: ok_shadow &= [a for a in range(3) if phi6[a]] == [2] graded = {sh[a] for a in range(2, p)} if len(graded) > 1: blind.append(p) ok_blind = blind == [p for p in PRIMES if p <= 199 and p % 3 == 1] check("L4 BOX(a AND NOT a) = [Phi_6(a) = 0] = [ord a = 6], p <= 199; " "-1 at p = 3", ok_shadow) check("L4 the pair is blind exactly at the p = 1 mod 3, p <= 199", ok_blind, f"{len(blind)} blind channels, first {blind[:4]}") off = [] for p in [2] + ODD23: L = p - 1 G = lambda a, m: BOX(pow(a, m, p), p, L) for a in range(p): ladder = AND(G(a, 6), NOT(OR(G(a, 2), G(a, 3), p), p), p) if ladder != BOX(AND(a, NOT(a, p), p), p, L): off.append((p, a)) check("L4 the ladder formula reads the shadow everywhere but (3, -1), " "p <= 23", off == [(3, 2)], f"disagreements {off}") off, pins = [], [] for p in [q for q in PRIMES if q <= 199]: L = p - 1 G = lambda a, m: BOX(pow(a, m, p), p, L) for a in range(p): ladder = AND(G(a, 6), NOT(OR(G(a, 2), G(a, 3), p), p), p) pin = AND(AND(G(a, 2), NOT(BOX(a, p, L), p), p), G(NOT(a, p), 2), p) if pin: pins.append((p, a)) if OR(ladder, pin, p) != BOX(AND(a, NOT(a, p), p), p, L): off.append((p, a)) check("L4 the ladder formula OR the pin G_2(a) AND NOT BOX a AND " "G_2(NOT a) reads the shadow everywhere, p <= 199; the pin holds " "at (3, -1) alone", off == [] and pins == [(3, 2)], f"disagreements {off}, pin true at {pins}") def first_collision(shadow): for p in [q for q in PRIMES if q <= 100]: seen = {} for a in range(p): key = (order(a, p), order((1 - a) % p, p)) if seen.setdefault(key, shadow(a, p)) != shadow(a, p): return p return None c1 = first_collision(lambda a, p: int(a * a * (1 - a) % p == 1)) c0 = first_collision(lambda a, p: int((a * a - a + 1) % p == 0)) prof = lambda x, p: (order(x, p), order((1 - x) % p, p)) wit = (prof(5, 7) == prof(3, 7) == (6, 6) and 3 * 5 % 7 == 1 and 3 * 3 % 7 != 1) check("L5 CONTROL Phi_6's shadow never collides, p <= 100", c0 is None) check("L5 [a^2(1 - a) = 1] first collides at p = 11", c1 == 11, f"first collision p = {c1}") check("L5 [ab = 1]: a = 3, b = 5 and 3 share profile (6, 6) at p = 7", wit) def main(): section_e() section_m() section_c() section_k() section_q() section_v() section_l() print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed") raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()