# LOGIC — the logic a squarefree ring's own polynomials carry The object: a squarefree modulus M with prime set S, and the ring Z/M, which the CRT splits into the prime fields F_p, p ∈ S, one channel each. Four ring polynomials, **AND**, **OR**, **NOT** and **IMP**, are the Boolean connectives on its idempotents; this page states what the same polynomials do everywhere else, what a reader using only ring operations can decide about a residue's truth, and where that reader stops. Every map built from ring operations acts channel by channel, so each such map is a tuple of prime-field maps, one per channel, glued by the CRT, and nothing here needs S to be the first k primes: the rungs Z/p_k#, p_k# the product of the first k primes (TOWER.md), are one family of such M. A **shadow** is a predicate on one or more residues, read on each channel's own residues. ``` AND(a, b) = ab OR(a, b) = a + b − ab NOT(a) = 1 − a IMP(a, b) = 1 − a + ab ``` ## The truth values Tier: property. Verifier: proof; logic.py::section_e. A residue with a² = a reads 0 or 1 on every channel, since a field has no other idempotent. So the idempotents of Z/M are the 2^|S| residues 1_T, reading 1 on a subset T of S and 0 off it, and the four connectives act on two of them, 1_T and 1_V, as intersection, union, complement and (S ∖ T) ∪ V: the truth values are the Boolean lattice of subsets of S. At a prime-power factor Z/p^r of a modulus that is not squarefree the only idempotents are still 0 and 1, because e(e − 1) = 0 with e and e − 1 coprime, so every modulus N has 2^ω(N) of them, ω(N) counting the primes dividing N, and a fattened prime adds none. The map n ↦ an is multiplicative iff a²xy = axy for all x, y, which at x = y = 1 already says a² = a: the multiplicative maps of that form are exactly the idempotents. A product 1_T·u with u a unit is a unit only when 1_T is, so no truth value but 1_S keeps any unit a unit. The mass of T is the share of residues that 1_T fixes, the ones vanishing off T: ``` mass(T) = #{x : x·1_T = x} / M = 1 / ∏_{p ∈ S∖T} p, mass(T ∩ V) · mass(T ∪ V) = mass(T) · mass(V). ``` A truth value's mass is set by what it excludes, and it multiplies where a probability would add. ## The meadow Tier: property. Verifier: proof; logic.py::section_m. Z/M is von Neumann regular (every a has an x with axa = a) iff M is squarefree. On a field take x = a⁻¹, or anything at a = 0. At a factor Z/p^r with r ≥ 2 a nonzero non-unit a would need a(ax − 1) ≡ 0 mod p^r, and ax − 1 is a unit, so a ≡ 0: the regular residues of Z/p^r are exactly 0 and the units, and the residue p is not one. So a squarefree Z/M carries a total **pseudo-inverse** a′, inverting each nonzero channel and keeping each zero, and each residue a support supp(a), the channels where it is nonzero. A commutative ring with such an inverse is a **meadow** (Bergstra, Hirshfeld and Tucker 2009), whose axioms a″ = a and aa′a = a are among the laws below. Channel by channel: - aa′a = a, a′aa′ = a′, a″ = a, and aa′ = 1_supp(a). - supp(ab) = supp(ab′) = supp(a) ∩ supp(b), and supp(a′) = supp(a). - supp(a + b) contains the symmetric difference of the two supports and lies in their union. - (ab′)b = a iff supp(a) ⊆ supp(b): division undoes itself exactly when the divisor's support covers the dividend's. The script checks the pseudo-inverse laws on all of Z/2310, the support laws on every pair of Z/210 and 20,000 pairs of Z/510510, and regularity against squarefreeness at every M up to 200. ## The defect Tier: theorem. Verifier: proof; logic.py::section_c. Write δ(a) = a² − a, the defect; it vanishes on a channel iff a reads 0 or 1 there. A residue is **graded** on a channel where it reads neither and classical on one where it reads 0 or 1, so the defect's support is the set of channels where a is graded. Every Boolean law built from the four connectives fails only inside the ideal the defects generate, and fails nowhere a channel's inputs are classical. Proof. A law holds on {0, 1}ⁿ in Z, so the difference of its two sides is a polynomial vanishing on {0, 1}ⁿ; its reduction modulo the x_i² − x_i is a multilinear polynomial vanishing on {0, 1}ⁿ, hence zero, and that difference lies in the ideal generated by the δ(x_i). Ten common laws each carry a single-variable factor: ``` a AND a − a = δ(a) a OR a − a = −δ(a) (a IMP a) − 1 = δ(a) (a OR NOT a) − 1 = δ(a) a AND NOT a = −δ(a) a AND (a OR b) − a = δ(a)(1 − b) a OR (a AND b) − a = −δ(a) b a AND (b OR c) − (ab OR ac) = δ(a) bc a OR bc − ((a OR b) AND (a OR c)) = −δ(a)(1 − b)(1 − c) a AND (a IMP b) − (a AND b) = −δ(a)(1 − b) ``` so each holds whenever that one variable is classical, and contraposition, both De Morgan laws and double negation hold as identities. The defect composes, each line by expansion: ``` δ(NOT a) = δ(a) δ(ab) = δ(a)δ(b) + δ(a)b + aδ(b) δ(a + b) = δ(a) + δ(b) + 2ab ``` OR and IMP are NOT-conjugates of AND, so by induction supp δ(F) lies in the union of the leaves' defect supports for every formula F in the four connectives: nesting never creates non-classicality. Bare + does, since δ(1 + 1) = 2 is nonzero at every odd channel. On one channel F_p, a graded x is made classical by AND with exactly two partners in F_p, 0 and x⁻¹, since xy must land in {0, 1}; by OR with exactly 1 and 1 − (1 − x)⁻¹, by conjugation; by NOT never. And a AND a = a is a² = a, so "a AND b = a", the relation that orders the truth values, is not even reflexive at a graded residue: that order does not extend past the idempotents, and a residue's truth is located by channel rather than ranked by that order. The script checks the fourteen polynomial statements on every triple of F_p for p ≤ 13 and of Z/30, the composition laws on every pair for p ≤ 23, and 5,000 random formulas on Z/510510, none with a defect support outside the union of its leaves' defect supports. ## The Kleene reading Tier: theorem. Verifier: proof; logic.py::section_k. Read each channel at its coarsest grain: true for 1, false for 0 and unknown for anything else. The connectives then compute strong Kleene three-valued logic on every channel, except where two unknowns land on a truth value (ab = 1 under AND, (1 − a)(1 − b) = 1 under OR, a(1 − b) = 1 under IMP): p − 2 of the (p − 2)² unknown pairs per binary connective, all of them at p = 3. Proof. With a classical input the output class is 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. With both inputs unknown, Kleene says unknown, and the ring departs exactly when the output is 0 or 1: ab = 1 for AND, (1 − a)(1 − b) = 1 for OR, a(1 − b) = 1 for IMP (the other landings would need a zero divisor). Each fixes one unknown partner per unknown a, so p − 2 departures. NOT never departs. So, connective by connective, the ring's logic leaves unknown exactly what three-valued propagation does, except at the p − 2 pairs of unknown inputs whose output lands on 0 or 1, where it returns a truth value Kleene leaves unknown: what it adds is arithmetic. The script prints AND's 1/1, 3/9, 5/25, … , 21/441 departures at p = 3, … , 23 and checks the same p − 2 at each p for OR and IMP. ## The pair Tier: theorem. Verifier: proof; logic.py::section_q. With λ = lcm(p − 1) over S, the two collapses ``` ◇a = a^λ reads [a ≠ 0] on each channel: true to some degree □a = 1 − (1 − a)^λ reads [a = 1] on each channel: fully true ``` land on the truth values and form a dual pair, ◇ asking whether a is true to some degree on a channel, nonzero there, and □ whether it is fully true, 1: - ◇ NOT a = NOT □a, by definition. - ◇ commutes with AND exactly, since (ab)^λ = a^λ b^λ; □ commutes with OR exactly, since (1 − a)(1 − b) = 0 iff a = 1 or b = 1. - Each leaks one way on the dual connective. ◇(a OR b) falls below ◇a OR ◇b exactly when a, b ≠ 0 and (1 − a)(1 − b) = 1, which is p − 2 of the (p − 1)² pairs of nonzero inputs; □(a AND b) rises above □a AND □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. Under ◇, disjunction can lose truth and never create it. - The gap is the defect: ◇a − □a = ◇δ(a) = ◇a AND ◇ NOT a, so "true to some degree and false to some degree" is exactly the defect's support. - □a AND a = □a, ◇a AND a = a, ◇ and □ are idempotent and fix each other's outputs, □(a IMP b) AND □a ≤ □b, and ◇(a AND ◇b) = ◇a AND ◇b. Quantifying over channels is walled. Once |S| ≥ 2 no polynomial computes the whole-ring test [a = 0 in Z/M], 1_S at a = 0 and 0 elsewhere (NOT ◇a is the per-channel one): a polynomial's value at channel p depends on a mod p alone, and a = 0 and a = 1_{S∖{p}} agree at p while [a = 0] must read 1 at the first and 0 at the second (at Z/30 the witness is 16). The threshold read [|supp a| ≥ θ] is walled the same way, with |S| ≥ 2, at every 1 ≤ θ ≤ |S|. For θ < |S| take 1_T against 1_{T ∪ {q}} with |T| = θ − 1 and p ≠ q both outside T; for θ = |S| take 1_{S∖{q}} against 1_S. ◇ and □, reads of one channel's truth, come free as polynomials; a quantifier over channels needs a read that no channel supplies. A map that couples channels must take such a read from outside the polynomials, and the candidates differ in how many values they return: whether a ≠ 0 in Z/M returns two, the support's size |supp a| returns |S| + 1, and the size of a in [0, M) returns M. ## The envelope Tier: theorem. Verifier: proof; logic.py::section_v. Rewrite a IMP b as NOT a OR b, an identity of the polynomials, push NOT to the leaves by De Morgan and double negation, keep per leaf only the two bits ◇a and □a, and evaluate the AND/OR tree in Boolean logic twice: the roof U with ◇a at a positive leaf and NOT □a at a negated one, the floor L with □a and NOT ◇a. Then on every channel, for every formula F, ``` L ≤ □F ≤ ◇F ≤ U. ``` Proof by induction: at a literal the conjugacy makes both ends exact; at AND, ◇ is exact and □ only gains; at OR, □ is exact and ◇ only loses. The pair's two leak directions are exactly the two inequality slots. So U = 0 certifies F false and L = 1 certifies it fully true, a two-sided verdict computed inside the ring from two bits per leaf. On a channel where every leaf is classical, U = L = F. The script proves the sandwich for every formula of any size, repeated leaves included, by closure: the records (value, U, L, classical) reachable from the leaves of F_p by AND, by OR, number p + 4 at odd p, and every one satisfies it, for p ≤ 23. ## The envelope's sharpness Tier: theorem (read-once formulas, every p ≥ 5). Verifier: proof; logic.py::section_v. For a formula reading each leaf once, both ends of the envelope are reached at every channel with p ≥ 5: when U = 1 some inputs with the measured bits make F nonzero, and when L = 0 some make F other than 1, so neither bound can be tightened from the bits. The bits can still say more than the two bounds: when every input with the measured bits makes F a unit, as the proof shows can happen at (U, L) = (1, 0), the bits force ◇F = 1 though neither bound does. Proof. Track a formula by its value set over the inputs with the measured bits, with U and L; independent leaves make both connectives act on value sets as a product. The leaf classes are {0}, {1} and the graded set Γ = F_p ∖ {0, 1}. For p ≥ 5, |Γ| = p − 2 exceeds half of p − 1, so Γ and tΓ⁻¹ meet for every unit t and Γ·Γ = F_p^×; by conjugation Γ OR Γ = F_p ∖ {1}. Every value set with (U, L) = (1, 0) contains Γ, by induction: a graded leaf gives Γ; an AND with {1}, like an OR with {0}, keeps a set; an AND with {0}, like an OR with {1}, exits (1, 0); and two (1, 0) sets combine to a superset of Γ·Γ or of Γ OR Γ. So the value sets reachable are six: {0}, {1}, and Γ, F_p^×, F_p ∖ {1}, F_p under (U, L) = (1, 0). Each reaches both ends of its envelope, since a graded value is neither 0 nor 1. At p = 3 it fails: Γ is the single point −1, its own inverse and its own NOT-mirror, so (−1) AND (−1) = 1 and (−1) OR (−1) = 0 are forced, and two of the five reachable records (value set, U, L), {0} and {1} under (U, L) = (1, 0), each miss an end. Repeated leaves break it at every p ≥ 3: the (p − 1)-fold AND of one leaf is a^(p−1), which is 1 at every graded input, so at a graded leaf the floor's 0 is never reached, and the (p − 1)-fold OR misses the roof the same way. The script computes the closure at every prime 3 ≤ p ≤ 97 and finds the six value sets at each p ≥ 5, and checks both repeated-leaf witnesses at every prime 3 ≤ p ≤ 97. ## The ladder Tier: theorem. Verifier: proof; logic.py::section_l. Between □ and ◇ sits one **gate** per divisor m of λ: ``` G_m(a) = □(a^m) reads [a ≠ 0 and ord(a) | m] per channel. ``` G_1 = □ and G_λ = ◇; m | d gives G_m ≤ G_d; and G_gcd(m,d) = G_m AND G_d, since ord divides both iff it divides the 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 leak is read per channel, never on the ring's own orders: 2 has order 12 in Z/35, yet there G_4 OR G_6 = G_12, since channel 5 holds the orders 1, 2, 4 and channel 7 the orders 1, 2, 3, 6. The least lcm that can leak is lcm(2, 3) = 6, the least order with two distinct prime factors, and it leaks exactly when some channel has p ≡ 1 mod 3. The m-fold AND of a leaf is a^m, so □ of it is G_m: what repeated AND computes beyond the pair is exactly the multiplicative order. Mixed with NOT, a repeated leaf reads more, as the ladder's reach shows. Underneath lie the raw power maps. The fixed points of x ↦ x^r number ∏_{p ∈ S} (1 + gcd(r − 1, p − 1)) for r ≥ 1: per channel 0, or a root of x^(r−1) = 1 in a cyclic group of order p − 1. The power map x ↦ x^j is idempotent iff j² ≡ j mod λ (j taken in 1, … , λ), so the projections among the powers are the 2^ω(λ) idempotents of Z/λ, the identity and ◇ at their ends: the logic's projection lattice is the truth-value lattice one level down, on the exponents. At Z/510510, λ = 240 and its 20 divisors give 20 distinct gates. ## The order-6 shadow Tier: theorem. Verifier: proof; logic.py::section_l. The contradiction a AND NOT a, a formula with a repeated leaf and a negation, lies outside the read-once sharpness theorem and is fully true exactly at the roots of Φ₆: ``` □(a AND NOT a) = [a(1 − a) = 1] = [a² − a + 1 = 0] = [Φ₆(a) = 0]. ``` For p > 3 those roots are the elements of order 6, present iff p ≡ 1 mod 3, the primes that split in Q(ζ₆); at p = 2 there are none; at p = 3, Φ₆ = (x + 1)², one double root −1 of order 2, and 3 is the ramified prime (Φ₆'s discriminant is −3). Every graded residue carries the pair bits (1, 0), so the pair decides this shadow on a channel iff it is constant on the graded residues: it is blind at every p ≡ 1 mod 3, the shadow is identically false at p ≡ 2 mod 3, and at p = 3 the graded region is the one point −1. The envelope's floor is identically 0 here and can never certify it. The ladder reads it as G_6 AND NOT(G_2 OR G_3), the join's leak at 6 (G_m = □(a^m) reads the same predicate at every m, a divisor of λ or not), at every channel and residue except −1 at p = 3, where gcd(6, p − 1) = 2 folds G_6 onto G_2. One formula read on every channel cannot take the pair to pin that point, since −1 at p = 5 carries the same bits and reads 0, but the ladder can: G_2(a) AND NOT □a AND G_2(NOT a) holds exactly when a = −1 and NOT a = 2 has order at most 2, which is p = 3. The ladder formula OR that pin decides the shadow on every channel. The script checks the shadow and the blindness at every p ≤ 199, the bare formula at every residue for p ≤ 23, and the pinned formula at every residue for p ≤ 199. ## The ladder's reach Tier: property. Verifier: proof; logic.py::section_l. A one-leaf reader, a formula in one leaf a that reads it only through the gates on a and on NOT a, combined by the connectives, sees exactly the profile (ord a, ord(1 − a)), writing 0 for the order of 0, on whichever channel it is read. One such formula read on a set of channels decides a shadow there iff the shadow is a function of the profile over the residues of all of them, and two inputs with one profile on which the shadow differs prove an escape; the script looks for such pairs within one prime. The witnesses below are computed, and the section's tier is the paragraph above. - [a²(1 − a) = 1], which is □(a AND a AND NOT a), escapes: at p = 11 two residues share a profile and differ, and the script finds no such pair at a smaller prime. Φ₆'s shadow never collides: it is [ord a = 6] at p > 3 (the order-6 shadow), and at p ≤ 3 no two residues share a profile; nor do two channels collide, since −1 at p = 3 has the profile (2, 2), which elsewhere needs 1 − a = 2 of order 2. - [ab = 1] escapes every pair of one-leaf profiles: at p = 7 the inputs b = 5 and b = 3 share the profile (6, 6), while with a = 3 the product is 1 for the first and 2 for the second. Relative order is not a leaf quantity. What the logic decides with more than one leaf, words in these connectives read by the gates, is GATES.md.