Overlapping affine fragments: a classical compatibility obstruction

The broader goal is to understand when future behavior admits a representation maintained by finite rules with bounded local access and allocation. The composition question here is whether independent preparation makes compatibility of overlapping constraints cheap. This interface differs from concatenating rows with disjoint output variables.

Statement and resource contract

Over $\mathbb F_2$, take $A,B\in\mathbb F_2^{n\times n}$ and $c\in\mathbb F_2^n$. Prepare separately the two individually satisfiable fragments

$$F_A(x,y):y=Ax,\qquad G_{B,c}(x,y):y=Bx+c.$$

Both share all $b=2n$ boundary variables $x,y$. After preparation, the requested Boolean answer is whether their conjunction is satisfiable. Exactly,

$$F_A\land G_{B,c}\text{ is satisfiable}\iff c\in\operatorname{im}(A+B).\tag{1}$$

Use the independent immutable, address-blind access contract in the composition access audit. Each operand has finitely many fixed opaque roots into independently prepared storage. Initialization shared by operands is fixed and input-independent. Each old-storage observation has at most $g\ge2$ possible outcomes. Finite handle metadata contributes at most $H$ bits in total. These bounds and the worst-case probe bound $T$ are uniform over $A,B,c$.

Pointers can be copied and followed through fixed named ports, but their numerical addresses, identity, ownership, heap sizes, allocation layout, timing and exceptions supply no uncharged input information. Missing ports are totalized; inspecting a resulting tag is charged. Operand-dependent executable code is not free metadata. Control, termination and fresh records depend only on public parameters, charged metadata and observed outcomes. There is no jointly prepared input-dependent state.

Claim. Every exact deterministic implementation satisfying this contract obeys

$$H+T\lceil\log_2g\rceil=\Omega(n^2).\tag{2}$$

Here $T$ counts old-information observations from receipt of both handles through the final compatibility answer, including any deferred query. The claim permits arbitrary finite separate preprocessing time and stored size $S$; it therefore also applies under polynomial preprocessing and storage restrictions. It is a worst-case claim, not an average over input matrices and not a claim for every fixed offset: $c=0$ is always compatible.

For fixed metadata and a fixed finite outcome alphabet, $T=\Omega(n^2)$. A lazy composition node may still be allocated in constant time: the final query must pay the outstanding information cost.

Proof: reduce the classical rank promise

Li, Sun, Wang and Woodruff prove in Theorem 1 of arXiv:1407.4755 that, in the additive two-party input model over a prime field,

$$R_{1/10}(\mathrm{Rank}_{n,n-1})=\Omega(n^2\log p).$$

Their promise is that the rank of the sum of the parties’ matrices is either $n$ or $n-1$. The theorem includes $p=2$ and public randomness with worst-case communication cost. This is the imported lower bound; no novelty is claimed for it.

Let Alice hold $A$ and Bob hold $B$. Choose four independent uniform public vectors $c_1,\ldots,c_4$. For each vector, run the exact compatibility procedure on independently prepared $F_A,G_{B,c_j}$. Bob may rebuild his representation locally for each public offset; local computation is free in the communication model. Reset the combining procedure for each call, and charge the metadata for every call.

For $M=A+B$,

$$\Pr_c[c\in\operatorname{im}M]=2^{\operatorname{rank}M-n}.$$

Declare full rank exactly when all four calls answer yes. At rank $n$ this is always correct. At rank $n-1$ its error is $2^{-4}=1/16<1/10$.

Reuse the audit’s storage-to-protocol simulation: represent an old reference symbolically by its owner, initial root and port word. Navigation and fresh symbolic records are determined by the public transcript. When an old observation is needed, its owner sends the outcome using at most $\lceil\log_2g\rceil$ bits. Hidden aliases do not change the transcript because identity tests are unavailable. The fixed public controller reproduces branching and termination. Thus each call costs at most $H+T\lceil\log_2g\rceil+O(1)$ communication, and four calls cost at most four times that amount. The imported theorem proves (2). This invokes the completed simulation contract; it does not reopen its earlier disjointness application.

Input size, storage and an upper bound

The dense coefficient description has $N_0=2n^2+n+O(n)=\Theta(n^2)$ bits including unary size headers. A fixed-shape 3CNF encoding pins private coefficient variables, uses private AND gates for coefficient-times-input bits, and private XOR chains for each output equation. Rename all auxiliaries apart between operands; only $x,y$ are shared. There are $\Theta(n^2)$ gates, variables, clauses and literal occurrences. Explicit indexed variable names yield $N=\Theta(n^2\log n)$ bits. Each operand is still individually satisfiable for every $x$.

Consequently the bound is $\Omega(b^2)=\Omega(N_0)=\Omega(N/\log N)$. These are compact inputs polynomial in boundary width; the bound is not exponential in $b$.

There is a matching $O(n^2)$ old-information-probe upper bound: independently store coefficients and offset in fixed-shape finite-bit lists, read them all, then solve (1) by Gaussian elimination on the observed data. Preparation and storage for this witness take $O(n^2)$ list primitives and nodes; explicit pointer encoding takes $O(n^2\log n)$ bits. In this probe measure computation and new allocation after observation are free. Hence optimal worst-case old-information probes are $\Theta(n^2)$ for constant metadata/alphabet.

This does not prove a matching quadratic local running time. Gaussian elimination and working storage must be charged in an actual machine implementation. A fixed local machine with at most a constant number of permitted old observations per step inherits the quadratic lower bound on post-preparation steps, but no matching upper time is asserted. Word observations give only the appropriately charged information bound (roughly $\Omega(n^2/w)$ for $w$-bit channels); unrestricted pointer identity and addresses require a different simulation. No blanket RAM, Turing-machine, SAT or complexity-class conclusion follows.

What the distinction explains

Row-fragment joins share inputs but have disjoint outputs. Their queries evaluate a specified linear functional, and two ready fragments preserve the existing subquadratic guarantee. Here both operands constrain the same outputs, and the query existentially tests their compatibility. Both the overlap and the query contract matter; overlap alone is not a hardness criterion.

The obstruction survives arbitrary independent summaries because discovering compatibility requires information crossing the operand boundary. Adding storage or delaying the answer cannot erase that requirement under the stated access contract. This is a classical scope separation, with an elementary reduction and a resource-preserving application of the existing simulation. It is a written proof, independently reviewed, not formally verified; no finite experiment or claim of new communication complexity is involved.

This compatibility claim is closed. The remaining program-level question is whether there is a useful structural condition on an operation together with its future-query family that supports bounded local composition and controlled deferred work. Any next candidate must explain a distinction beyond these completed examples, rather than refine this bound’s constant.