Parity complements: composition is small, streamed residuals need not be

Assessment156, 9 October2026. Written adaptation of a classical trellis mechanism, conditional representation contract, and a failed native transfer. This does not extend the admitted native language in reader36 or advance the root claim ledger.

Exact statement and payoff

Fix the actual left-to-right coordinate order of an ordinary n-bit terminal name. Let each completed row at this width be a parity halfspace H_i = {x in F_2^n : a_i x = b_i}, with nonzero a_i. Their union U has complement C = {x : Ax = d}, where the rows of A are a_i and d_i = 1+b_i. Thus composition can use intersection of affine systems instead of a table of all joint cell colors. A reduced system has at most n equations, or an explicit inconsistency flag. This is a semantic composition statement with polynomial bit storage, not a constant-cost join statement.

For nonempty C, at cut t write A = [L_t R_t] and set

kappa_t = rank(L_t) + rank(R_t) - rank(A).

The exact number of distinct nonempty suffix residuals of C is 2^kappa_t. The total number of residuals is 2^kappa_t plus one if an infeasible prefix exists. Complementing every residual gives exactly the same total count for U. Hence bounded kappa at every cut is an exact bounded-width criterion for a prepared, ordered, layered deterministic reader. It is not a bound on the local state of a persistent machine that can observe old storage while it reads.

This separates three resources: size of a semantic affine summary, size of a prepared streamed reader, and cost of constructing and retaining that reader. Only the first two are settled here. In particular, final bounded reader width is not sufficient to bound width during persistent composition.

1. Relation to the classical source

David Forney, MIT 6.451, Spring2005, Chapter10, sections10.2.1-10.2.2, Lemma10.1 and Theorem10.2, proves the state-space theorem by decomposing a linear code into past-only, future-only and state components. Equal state components have equal future cosets; different ones have disjoint future cosets. The canonical trellis realizes these states at every cut simultaneously.

Primary source: https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/1b67ae9f5c124c3bd56c8649afa5af47_chap10.pdf

The formula below uses a parity-check matrix, permits an affine right side and adds the infeasible-prefix sink required by a total recognizer. It is a written adaptation of that standard mechanism. The imported source supplies no ordinary Horn-name learner, old-top schedule, or real-time persistent join. This targeted proof extraction is not a dedicated multi-paper review.

2. Proofs and scope of the exact algebra

2.1 Complement closure avoids the atom table

A point is outside every H_i iff a_i x differs from b_i for every i. Over F_2 this is exactly Ax=d. Appending rows therefore intersects complements. Intersection is associative and commutative, so elimination to an equivalent reduced system preserves every later union answer. Contradiction represents the full union. The empty family has A with zero rows and represents the empty union.

The map x -> Ax has 2^r values, each with 2^(n-r) preimages, where r=rank(A). Consequently a literal common partition by all row truth values has 2^r nonempty atoms. It does not follow that U needs 2^r states or labels: all but one of those syndromes may have the same answer. With A=I_n and b_i=1, U consists of all nonzero words. Its common partition has 2^n singleton cells but its reader only tracks whether a one has occurred. Row-dependent partitions cannot be merged as reader36’s fixed masks, but this atom-count argument does not exclude a different summary algebra.

2.2 Exact residual count

Let P=im(L_t) and F=im(R_t), both subspaces of the equation-coordinate space. After prefix p the residual is

C_p = {z : R_t z = d + L_t p}.

It is nonempty exactly when L_t p belongs to P intersect (d+F). Since C is nonempty, this intersection is a nonempty affine coset of P intersect F. It has 2^dim(P intersect F) elements. Distinct right sides yield disjoint, nonempty solution sets, and every element of that intersection is reached by some prefix. Since P+F=im(A), the dimension is exactly kappa_t. All remaining prefixes, if any, have the single empty residual.

A deterministic layered reader reaching the same state on two prefixes must give equal answers on every common suffix. Therefore distinct residuals require distinct states. Conversely, take residuals themselves as states and let input bit c send C_p to C_pc. Equality of residuals makes this transition well defined. Acceptance at the final layer tests whether the empty word is in the residual. This achieves the count at every layer. Complementation is an injective map on subsets of the fixed suffix universe, so U has the same number of states. The empty residual becomes a universal accepting residual. It must not be merged with another live residual merely because its output is eventually accepting.

If Ax=d is inconsistent, C is empty, U is full, and a one-state reader suffices; the kappa formula is deliberately not used for this case. Zero columns, dependent or zero equations, t=0, t=n and n=0 cause no other exception.

For homogeneous C=ker(A), Forney’s form yields the same expression: dim(C)=n-r, dim(C_P)=t-rank(L_t), and dim(C_F)=n-t-rank(R_t). An affine translation preserves the count.

3. Dependencies and input order, not total rank

For A=I_n, kappa_t=0 at every cut, even though rank(A)=n. There is one live residual and, after a nonzero prefix, a dead residual.

For equality of two m-bit halves, C={xy:x=y}, take A=[I_m I_m]. At the middle cut both halves have rank m, so kappa_m=m. A total ordered reader needs 2^m live states there. The corresponding U is the union of m parity halfspaces {x_i+y_i=1}, the inequality predicate. Each single equation has kappa at most1. Thus bounded width for each independently completed row is not a closure criterion for their unions.

The same equalities in order x_1,y_1,x_2,y_2,… have kappa at most1 at every cut. The distinction is a property of the actual input order. Reordering an ordinary late name requires storage, routing and a schedule; this comparison supplies none of those operations for free.

There is a stronger obstruction to final-only validation. First compose all m inequality rows in the separated order. Then add rows {x_i=1}, i=1,…,m. The final complement imposes x=y and x=0, hence is the singleton zero word. Final kappa is zero everywhere, but the earlier version had kappa_m=m. Every such intermediate union is also a valid finite parity-row union. Consequently a gate which checks only the final system’s bounded kappa cannot justify maintaining a bounded-width normalized reader after every join. Arbitrarily large temporary width can disappear under later constraints, even with no contradiction.

This refutes that eager normalization scheme. A delayed representation with a charged pending readout is not refuted. Nor does a fixed positive budget B become union closed: each equation fits B=1, their growing union need not fit any fixed B.

4. What a charged prepared-reader contract does give

Take a single fixed W. A completed immutable binary decision DAG, already built in layers with at most W nodes per layer, has fixed degree2 and finite labels. With its root accessible in a bounded-radius old-top capsule, one branch lookup per input bit reads an n-bit query in O(n) observations, constant per-symbol work, and constant final-symbol output. The old structure is unmodified. There is no pointer-identity or numeric-address test. Opposite time orientation is possible by allocating the final layer first and then its predecessors. This describes paid readout once preparation and root routing are supplied; it is not an input construction for reader36’s language.

If two such prepared diagrams describe the same width and coordinate order, a synchronous product has at most W_1 W_2 nodes per layer and recognizes union by OR of terminal bits. For fixed W_1,W_2 there is a pointer implementation with O(n) work and allocation: read the two aligned layer tables forward into an immutable stack, then traverse that stack backward to create product layers. Each table has a fixed number of states and transitions, so its temporary local indices fit finite control. The two passes and the O(n) retained stack are charged. Every earlier diagram remains accessible from its retained root. For varying widths this is a family of bounds with constants dependent on W_1,W_2, not one fixed native automaton. Product construction is not an O(1) old-top join and needs actual preparation time after both operands are present.

For consistent affine operands the number of live residuals of their intersection is at most the product of their live counts: a prefix’s residual is the intersection of its two operand residuals. Hence kappa_join <= kappa_left+kappa_right at each cut. There is no bound independent of the number of joins. Minimization or Gaussian elimination may compress a product, but the operations and their scheduling still need to be paid. Arbitrary matrix indices and basis handles are not native primitives.

The Lab’s sealed-affine-boundaries control already gives O(n^2) coefficient storage, O(n^3) bounded-local immutable elimination work/allocation per join, and O(n^2) sequential membership, under its supplied affine boundary contract. It settles neither linear total preparation for ordinary extensional Horn rows nor constant work per late-name symbol. This packet uses that control rather than counting affine closure as a new native theorem.

4.1 A more concrete bounded-support receipt

There is a useful sufficient prepared contract that avoids Gaussian basis selection. Fix B once. Give each nonzero equation the interval from its first to its last nonzero coordinate, inclusive. Suppose at most B such intervals contain any coordinate. An interval schedule assigns each equation a reusable slot from a fixed set of B slots. Greedy assignment works: when an interval starts, at most B-1 other intervals containing that coordinate already occupy slots. Release its slot after processing its last coordinate.

A column record contains finite B-bit masks for starting slots, coefficients, ending slots, and right-side bits for ending equations. A fixed controller stores B parity accumulators and a permanent violation bit. At each ordinary query bit it resets starting slots, XORs that bit into coefficient-marked slots, then compares ending slots with their right sides. A failed comparison sets the violation bit. The output for U is that bit when the last column is read. Induction on columns proves that every live accumulator is exactly its equation’s partial dot product and every expired equation has been checked. A singleton support is reset, updated and checked at the same coordinate.

The records use O(n) nodes and O(n log(n+2)) explicit pointer bits. They form an immutable linked stream with finite labels and degree1; the query requires one local record observation per actual bit, no coordinate reordering, arithmetic address, or EOF scan. Its finite state depends on B, not n or the number of expired equations. Record construction and root routing remain prerequisites. Building from supplied support intervals uses a schedule, but those intervals are not part of the native input in this investigation.

Two aligned prepared streams can be joined by concatenating their slot fields, using disjoint slot sets of sizes B_1 and B_2. Forward scanning into a stack and backward immutable construction charge O(n) work and storage for fixed B_1+B_2. The resulting bound is B_1+B_2, so repeated composition is still not closed at one fixed B. Repacking into B slots, if possible, needs a paid operation and cannot be inferred from final kappa alone. This receipt shows exactly what stronger local observation would suffice: a learned per-coordinate coefficient and expiration instruction, available as the query bit arrives.

5. Actual encoding and unsuccessful learning routes

In reader36 the input supplies ordinary incidence names, not a_i, b_i, a width, a decomposition, or a ready classifier handle. A parity-halfspace promise must be checked or explicitly made a restriction; the present note does not smuggle such coefficients into the input.

For a nonzero halfspace on n bits an extensional row has 2^(n-1) distinct target words. Its target characters alone cost n2^(n-1). Duplicates cost their actual characters as well. With m equality-halfspace rows at width2m the target-character cost is Theta(m^22^(2m)); source names only increase N. The 2^m prepared-reader state count therefore is not a superlinear-in-N storage bound for that witness. It also does not lower-bound a native machine’s observations: the machine may route into old records or keep a different summary.

Several apparently affordable learning steps fail the stated deadline argument:

• A point p in H and membership of p+e_j for all j determine every coefficient: a_j=0 exactly when p+e_j is also in H; then b=a p. This is a correct learning identity. Using an existing streamed membership reader separately on each n-bit neighbor costs n queries and Theta(n^2) input/probe steps. Starting those queries at the right-row boundary supplies forbidden post-boundary work. The long prior row does not automatically schedule probes of its final version.
• Gaussian elimination on the affine hull of all listed points can recover the hyperplane and detect deviations. Straight bit-level insertion may cost polynomial work per point, not constant work per actual symbol. Aggregate exponential row length does not pay a repeated polynomial factor per point.
• Taking an early handful of points does not certify the final affine hull: arbitrary order can keep early points in a smaller affine subspace. Duplicates make a bound based on a fixed number of initial records still less useful.
• Even a final compressed affine system with bounded kappa does not repair the intermediate-width example in section3. The interface needs either a hereditary gate, a paid incremental normalizer, or a representation that directly answers while normalization is pending.

These are failures of particular cost arguments, not lower bounds on learning. No advice, padding, address-derived information, free EOF work, or supplied coordinate permutation is used to turn them into a positive transfer.

6. Evidence and next decisive test

tools/research/check_parity_cut_residuals.py compares literal solution sets and suffix residuals with an independent bit-matrix rank routine, including affine inconsistency, duplicate/zero equations and empty dimensions. It also checks literal halfspace unions, the joint-atom count, and the order/intermediate-width families. A separate prepared column-record constructor and reader are compared with literal membership for every pair of nonzero equations through n=5, including slot reuse and singleton intervals. Finite enumeration supports the formulas; section2 is their proof. The script is not a native implementation or a charged preparation experiment.

Next: test a hereditary bound on coordinate cuts of every composed version, together with input-built coefficient receipts. The decisive requirement is an incremental, immutable normalizer whose pending state is directly readable as the ordinary endpoint name arrives. Start with at most B crossing parity constraints at each actual coordinate cut, B fixed, and determine whether their supports and expiration events can be learned and routed from the extensional rows without supplied endpoints. A support-count gate is stronger than the basis-invariant kappa gate, but may permit a real paid schedule. Do not assume that bounded final rank, bounded final kappa, or the length of an earlier row already provides this schedule.

The existing replay, affine, causal/cubical and native SAT controls are preserved. This packet gives no matching-diagram extraction and no positive-path monotone readout contract: affine consistency and negated membership remain stronger observations. Entry129’s exponential diagram bounds and the growing-alphabet qualification remain exactly as before. No new native recognition claim is made, so there is no new PEG transfer; any eventual native L result gives reversal(L) under the existing correspondence, subject to its precise language contract.