The overlap obstruction to composition
On this page · Permalink · Source line 622
CLAIM C08 The weighted fingerprint is compatible with products on disjoint witness coordinates. The same formula fails when the factors share a coordinate. The distinction isolates a concrete compatibility obligation, rather than asserting that all compression is impossible.
Proposition 20.1: Disjoint-variable factorization
If predicates \(A(u)\) and \(B(v)\) use disjoint witness-variable sets, then their weighted fingerprints satisfy
Proof
Expand the left side as a sum over the Cartesian product of witnesses:
Disjointness makes the exponent data independent and the factorization exact.
Counterexample 20.2: Shared-variable multiplication fails
For a single witness bit, define \({\operatorname{Tr}}_z(A)=A(0)+zA(1)\). Then in the Boolean \(w\) algebra,
but
whenever \(z\ne0\). Also,
which differ for field elements \(z\) with \(z^2\ne z\).
Proof
Evaluate \(w\) and \(1+w\) at zero and one. In the Boolean quotient \(w(1+w)=w+w^2=0\) and \(w^2=w\). The displayed identities follow directly. In \(\mathrm{GF}(16)\), any element outside \({\mathbb F_2}\) supplies the second inequality.
The input predicates are individually easy and their separate fingerprints are explicit. Their conjunction nevertheless imposes a common-witness requirement that ordinary multiplication of the summaries fails to preserve.
Theorem 18.1 explains a related all-size restriction: a fixed linear multiplicative summary retaining every witness cannot reduce the full witness algebra below dimension \(2^m\). That statement does not rule out all context-dependent nonlinear evaluation methods. It rules out the displayed context-free multiplicative compiler under its exact hypotheses.
The eight maintained claim groups end here. Their proofs do not assume a superpolynomial shared-generation bound or a polynomial-time weighted-trace evaluator. The appendices identify the exact source coverage, evidence, and closed-scope boundaries.