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), 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:

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:

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.

What the logic decides with more than one leaf, words in these connectives read by the gates, is GATES.