Cut-response factorization and linear observer dimension

Status: FPRD bridge theorem with a self-contained proof and exact finite audit. The communication-complexity and linear-algebra ingredients are standard; no novelty claim is made for them. The purpose is to place replay support, residual separation, retained information, and local presentation cost in one exact diagram.

1. Cut systems

A finite cut-response system is a tuple

$$(P,C,\Omega,\beta),\qquad \beta:P\times C\to\Omega.$$

Think of $p\in P$ as the past available at a cut, $c\in C$ as a possible future continuation, and $\beta(p,c)$ as the answer after the two are joined. The response row of $p$ is

$$\rho(p)=(\beta(p,c))_{c\in C}\in\Omega^C.$$

An exact deterministic summary is a pair of maps

$$e:P\to S,\qquad d:S\times C\to\Omega$$

such that $d(e(p),c)=\beta(p,c)$ for every $p,c$.

For a language $L$, take $\beta(p,c)=\mathbf 1_L(pc)$. With all continuations allowed, equality of response rows is exactly Myhill–Nerode right congruence. A finite $C$ gives a finite observation of that congruence.

2. Exact factorization theorem

Theorem. The smallest possible summary alphabet has cardinality

$$\min |S|=|\rho(P)|.$$

Equivalently, the exact deterministic one-way message cost of the cut is

$$\left\lceil\log_2|\rho(P)|\right\rceil$$

bits when fixed-length binary messages are used.

Proof. If $e(p)=e(p')$, the decoder receives the same summary for both pasts. Hence for every continuation $c$,

$$\beta(p,c)=d(e(p),c)=d(e(p'),c)=\beta(p',c).$$

Thus $\rho(p)=\rho(p')$: every summary fibre is contained in one response-row class. Therefore $|S|\ge |\rho(P)|$ after unused summary symbols are discarded. Conversely, let $S=\rho(P)$, let $e=\rho$, and define $d(r,c)=r_c$. This realizes the lower bound. The bit formula is the fixed-length binary encoding cost of that many symbols. $\square$

This also gives an immediate capacity transfer. If every presentation at resource bound $r$ lies in a family of at most $B(r)$ distinguishable cut states, then exactness on the chosen cut system requires

$$|\rho(P)|\le B(r).$$

The implication is model-independent. Its usefulness depends on proving a genuine, encoding-robust capacity bound $B(r)$ for the presentation class under study.

3. Linear observers

Let pasts be vectors $x\in\mathbb F_q^n$. Let $A\subseteq\mathbb F_q^n$ be a family of observers, with

$$\beta(x,a)=a\cdot x.$$

Write $U=\operatorname{span}(A)$ and $r=\dim U$.

Linear observer corollary. The response map has exactly $q^r$ distinct rows. Therefore the minimum exact summary has $q^r$ states and needs $\lceil r\log_2 q\rceil$ fixed-length bits.

Proof. The response map $T_A:x\mapsto(a\cdot x)_{a\in A}$ is linear. Its kernel is $U^\perp$, which has dimension $n-r$ under the standard nondegenerate pairing. Rank-nullity gives $\dim\operatorname{im}T_A=r$, so its image has $q^r$ elements. Apply the factorization theorem. $\square$

For independent coordinate blocks, observer dimensions add. If $V=V_1\oplus V_2$ and the observer span is $U_1\oplus U_2$, then the exact retained information is the sum of the two block dimensions. This is a literal direct-sum law, not an analogy.

4. Two opposite calibrations

Over $\mathbb F_2^n$:

1. Coordinate observers $A=\{e_1,\ldots,e_n\}$ each inspect one source coordinate, but their span has dimension $n$. Exact readiness for all of them requires $2^n$ states, or $n$ bits.
2. The single parity observer $A=\{(1,\ldots,1)\}$ inspects all $n$ source coordinates, but its span has dimension one. Its response family requires only two states, or one bit.

Thus the largest support used by one completed observer neither determines nor approximates the stationary information needed for the whole observer family. Observer span measures independent answer directions; support measures how one answer is computed.

5. Relation to adaptive replay and scaffolds

FPRD-T150 fixes one completed execution and extracts its backward replay slice. The cut theorem instead fixes a family of possible continuations and asks how many different answer rows the past can induce.

FPRD-T151 is the coordinate-observer case. Every chosen continuation exposes one old bit, while the family of continuations spans all $n$ answer directions. This is exactly the deterministic one-way INDEX matrix.

The persistent unary selector supplies the complementary machine calibration. It retains those $n$ bits in an immutable stack while using a degree-two, distance-two scaffold update at every input symbol. Hence three resources must remain separate:

$$\text{pointwise replay support},\qquad \text{cut-response information},\qquad \text{stationary local update cost}.$$

The cut-response theorem controls the middle quantity. It does not by itself lower-bound scaffold degree, descriptor distance, allocation, or query latency.

6. Consequence for the forgotten-action frontier

For a proposed bounded presentation class, a lower-bound program may now be split into two independent obligations:

1. construct cut families with large response dimension or many response rows;
2. prove that every presentation at resource bound $r$ has cut capacity at most $B(r)$.

The first obligation is semantic and can often be attacked by residual or linear-algebra methods. The second is representational and must survive changes of coordinates, persistent sharing, and stationary re-encoding. Large response dimension alone cannot prove a local-update lower bound, as the unary selector demonstrates.

This factorization identifies the missing theorem for FPRD-C02 more sharply: one needs a capacity bound for bounded stationary frontier presentations, not another count of residuals by itself.

7. Exact audit

The checker exhausts:

• all 74,954 Boolean response matrices with one through four pasts and one through four continuations;
• 4,066,394 candidate encodings using one fewer state than the number of distinct rows, all rejected;
• all 65,812 binary linear-observer families in ambient dimensions one through four;
• 8,396,936 linear response entries and 328,760 capacity comparisons.

It detects 32,028 failures of the false rule “observer dimension equals largest support” and 64,365 failures of the false rule “observer dimension equals number of observers.” Named coordinate-basis and full-parity witnesses fail in opposite directions.

The computation is evidence against indexing mistakes and false surrogate invariants. The proofs above establish the unbounded statements.

8. Comparators

• A. C.-C. Yao, Some complexity questions related to distributive computing, STOC 1979, DOI 10.1145/800135.804414.
• Rahul Jain and Ashwin Nayak, The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited, arXiv:1004.3165.
• Myhill–Nerode residual equivalence and rank-nullity are the classical ingredients on the automata and linear-algebra sides.

No external or specialist review is recorded for this FPRD synthesis.