logic.py
Checks: LOGIC: The truth values property; LOGIC: The meadow property; LOGIC: The defect theorem; LOGIC: The Kleene reading theorem; LOGIC: The pair theorem; LOGIC: The envelope theorem; LOGIC: The envelope's sharpness theorem; LOGIC: The ladder theorem; LOGIC: The order-6 shadow theorem; LOGIC: The ladder's reach property.
Cited on: LOGIC.
To run it: save logic.py; standard library only.
"""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()