Two Quotients of One Machine

Abstract

Two Quotients of One Machine Myhill–Nerode cut complexity and locality cohomology of binary addition Driven by Dean A. Kulik September 2026 Abstract An n-bit modular adder is read two ways, and both readings are computed exactly. Theorem A (the reader cut). Present the input positions of (a,b) ↦ a+b mod 2ⁿ in an arbitrary order. The minimal Myhill–Nerode state count after a set S of positions has been read depends only on S — never on the order used to reach it — and factorises over the maximal runs of S: F(S) = PROD over maximal runs [l,r] of S of f(l,r) f(l,r) = 1 if [l,r] = [0,n-1] L = r - l + 1 2 if l = 0 and r < n-1 L+1 if l > 0 and r = n-1 2L+1 if 0 < l <= r < n-1 Memory is a cut functional, not a history functional. Theorem B (the relation residual). Model the same machine as a Cayley complex on ℤ/2ⁿ with generators 2⁰,…,2ⁿ⁻¹, declaring a square whenever its two moves touch disjoint bits. Then b_1^disjoint(n) = C(n,2) + (n-1) = (n-1)(n+2)/2 Both hold for all n. They are different invariants — one a rank, additive over pairs and identical for every reader; the other a state count, multiplicative over the runs of a cut and different for every reading order — and a once-plausible conjecture equating them is refuted structurally rather than numerically. What the two share is a sufficient statistic. On the object side the class of an undeclared square keeps only a seam bit and a carry-run depth; on the reader side a run keeps only a first-nontransparent depth and a carry mode. The exponentially large coordinate label — 2ⁿ basepoints there, 4^|S| assignments here — is in both cases the reader's own coordinates and not the object's structure. Consequence. The carry recurrence is intrinsic to binary addition. That one bit of retained state suffices is intrinsic to the bottom-anchored cut: the lower carry port is pinned at c₀ = 0, so nothing is owed and only the outgoing carry survives. Anchor the cut anywhere else and the retained state is not a collection of bits at all, because 2L+1 is odd. 1. Introduction A serial adder carries one bit. The question this paper answers is where that bit comes from — whether it is a fact about addition, about the circuit, or about the way the circuit is read. The investigation began from a different question. A programme on interfaces asks, for a system with declared local relations, how much structure a reader fails to absorb: the residual of a relation predicate, measured cohomologically. A companion question asks how much state a reader must retain to continue deterministically: a Myhill–Nerode quotient. Both are quotients of one transition system, and it was natural to conjecture that they measure the same thing — that the minimal retained memory counts the relation classes the predicate leaves open, or their orbits under the reader's own step. That conjecture is false, and its failure is the organising result. For the n-bit adder the residual is C(n,2) + (n−1), the same number for every reader. The memory depends entirely on the reading order and ranges from one bit to about 0.79n bits on the same arena with the same undeclared relations. The two cannot be equal under any counting map: one is a rank, additive over pair directions; the other is a state count, multiplicative over the runs of a cut. A sharper obstruction settles it — an interior run contributes 2L+1, which is odd, so the retained state of most cuts has no bit-decomposition and there is no register to count. What survives is better than the conjecture. Both quantities admit exact closed forms for all n, and both proofs turn on the same geometric object: the seam between a resolved carry chain and an unresolved one. The paper states and proves both, reports the verification, and logs the corrections — several of which were caught only because two independent readings of the same quantity disagreed. 2. The machine and its two quotients 2.1 The arena and the locality predicate Conventions. G_n = ℤ/2ⁿℤ with generating set {2⁰,…,2ⁿ⁻¹}. For i < n−1 the generator gives an edge x → x+2ⁱ. For i = n−1, x+2ⁿ⁻¹ = x−2ⁿ⁻¹, so that undirected edge is self-inverse and the graph is taken simple. Chains are over ℚ, computed over a prime field as a certificate; b₁(K) = dim_ℚ H₁. One orientation is chosen per undirected edge, with e_i(x) the oriented edge x → x+2ⁱ, so that e_{n−1}(y+2ⁿ⁻¹) = −e_{n−1}(y). That convention is what the top-case proof of §5.5 uses, so it is fixed here rather than introduced there. Throughout, ∂ is the chain boundary — never a cochain coboundary — and S_ij(x) := ∂r_ij(x). The vertex and edge counts are |V| = 2ⁿ and |E| = (n−1)2ⁿ + 2ⁿ⁻¹, the second because each of the n−1 lower generators contributes 2ⁿ distinct edges while the top generator's edges are shared in pairs. Hence b_1(graph) = |E| - |V| + 1 = (n-2)*2^n + 2^(n-1) + 1 Three predicates declare 2-cells. For a pair i < j and a vertex x, the square r_ij(x) has vertices x, x+2ⁱ, x+2ʲ, x+2ⁱ+2ʲ. • disjoint — declared exactly when the two moves touch disjoint bits at x. Three formulations of that condition agree, and the notebook confirms it on every triple to n = 9: (i) (x ⊕ (x+2ⁱ)) ∧ (x ⊕ (x+2ʲ)) = 0; (ii) some q in {i,…,j−1} has x_q = 0; (iii) bits i..j−1 of x are not all 1. Note what this is not: the generators 2ⁱ and 2ʲ always occupy distinct bits, so this is not static disjointness of supports but state-dependent carry overlap — the +2ⁱ chain must not reach bit j. • squares — every commuting square, which is all of them, since addition is abelian. • squares+carry — additionally the triangles A_i² = A_{i+1} for i = 0,…,n−2. Note what the locality predicate is refusing. Every pair of additions commutes globally. What it declines to certify is not commutation but locality: commutations that hold only through an overlapping carry chain. This is a state-dependent analogue of a Mazurkiewicz independence relation rather than that relation itself: in trace theory independence is a fixed, symmetric, irreflexive relation on an alphabet of actions, whereas here whether A_i and A_j count as independent depends on the basepoint. The related fact that, for token systems, the analogous complex computes the hard-core configuration space is an external theorem (Abrams), cited as context; nothing below proves it. Lemma (the descent identity). Let Z₁ be the cycle space of the shared 1-skeleton and put B_D = span{∂σ : σ declared}, B_A = span{∂σ : σ any square}, so B_D ⊆ B_A ⊆ Z₁. Both complexes have the same 1-skeleton, so b₁(D) − b₁(A) = dim B_A − dim B_D, that is b_1(D) = b_1(A) + dim(B_A / B_D) and the whole object-side question is the single number dim(B_A/B_D). 2.2 The reader and the cut The reader receives the input positions of (a,b) one at a time in a fixed order π = (p₁,…,p_n); after t steps it knows (a_p, b_p) for p in S_t = {p₁,…,p_t}. The outputs are the n sum bits of a+b mod 2ⁿ, and a sum bit is emitted as soon as no remaining input can change it. Two partial reads are the same state exactly when every completion gives identical not-yet-emitted outputs. That is the Myhill–Nerode quotient for this transducer; F(S) is the number of its classes. Two engines compute these. A brute-force enumerator that never mentions carries produces the Myhill–Nerode classes directly; a homology engine that never mentions readers produces b₁. They share no code. 3. Theorem A — the reader cut law 3.1 The local transfer machine For a known position q write p_q = a_q ⊕ b_q and g_q = a_q b_q. The carry recurrence is c_{q+1} = g_q ∨ (p_q c_q) and the output is s_q = p_q ⊕ c_q. So every known position is exactly one of three transfer types: (0,0) kill c_{q+1} = 0 (1,1) set c_{q+1} = 1 (0,1),(1,0) transparent c_{q+1} = c_q That is the whole local machine. Scanning a maximal run upward from its lower port, the unknown incoming carry survives exactly as long as positions are transparent. At the first nontransparent position the dependence on the incoming carry terminates: every output above it is already determined and need not be retained. Every run therefore has a canonical stopping depth d. 3.2 The four run factors Let Φ send an assignment on S to its tuple of per-run signatures. run what survives count interior, 0 < l ≤ r < n−1 depth d in 1..L x carry out in {0,1}, plus all-transparent 2L+1 bottom-anchored, l = 0 < r < n−1 c_0 = 0 known, all outputs emitted; only c_{r+1} 2 top, l > 0, r = n−1 unknown carry in, no observable carry out; only d L+1 full, [0,n−1] nothing unresolved 1 The interior count is the product of an owed-output ledger and a carry mode: L owed-prefix lengths times two carry-out values, plus one transparent state that transmits the unresolved carry and owes the whole run. The top run differs from the interior only in that the kill/set distinction after the decisive position has nowhere observable to go, because addition is mod 2ⁿ. 3.3 Gap independence Between two maximal runs lies at least one unread position, and a single unread position can kill, set or transmit the carry. Assigning the first unread position of a gap to (0,0) or (1,1) forces the carry entering the next run to any chosen value, whatever the run below did. Gaps therefore decouple adjacent run ports; distinct runs have disjoint read positions, so their signatures are chosen independently. This is the step that makes the count multiplicative rather than merely bounded. 3.4 Both Myhill–Nerode directions Equal summaries ⇒ equal futures. Process runs upward. Each gap has the same future input in both assignments and the run below has the same carry-transfer signature, so each run sees the same incoming carry; its signature then fixes its unresolved outputs and its outgoing carry. Induction gives identical future output under every completion. Distinct summaries ⇒ distinguishabl