Compact affine fragments: composition through stored linear information

Working research note, 2 October 2026.

Overview

Let a fragment impose $y=Ax$ over the field $\mathbb F_2$. Another fragment fixes $x=v$ and requires $u^{\mathsf T}y=1$. For example, with $A$ the identity, $u=(1,1)$, and $v=(1,0)$, their conjunction is satisfiable; replacing $v$ by $(1,1)$ makes it unsatisfiable. The answer is the parity $u^{\mathsf T}Av$. These are compact constraints with a single Boolean observation, rather than a request to print a long answer.

With exactly $n^2$ stored matrix bits and no redundancy, a linear change of basis cannot make every such query cheap: every invertible encoding has a query requiring at least $\lceil n^2/4\rceil$ reads. Allowing extra linear bits turns the problem into an exact minimum-support question. The later redundant-storage note proves a weaker $n\log_2(n)/48$ lower bound with $n$ extra bits and leaves the proposed quadratic bound open. These results concern the stated bit-probe contract, not every SAT algorithm or machine representation. Novelty is not claimed.

1. Fragments, size and the observation

Fix n>=2, d=n^2, and boundary B=(x_1,…,x_n,y_1,…,y_n), of width b=2n. For A in F_2^{n by n} and u,v in F_2^n set

$$F_A(x,y): y=Ax,\qquad G_{u,v}(x,y): (x=v)\land(u^Ty=1).$$

Private variables in separate encodings are distinct. Their compatibility is

$$\operatorname{SAT}(F_A\land G_{u,v})=u^TAv. \tag{1}$$

Indeed, the first relation and the pins determine y uniquely as Av; the final constraint then gives (1). This is an affine consistency problem. If the last constraint is omitted, the answer is always true. Consequently neither a lower bound for printing Av nor the mere construction of a lazy conjunction handle suffices for this question. All costs below run through the Boolean answer, including deferred evaluation.

A direct description consists of n and the n^2+2n coefficient/pin bits, with length N_0=n^2+2n+O(log n). There is also a fixed-shape 3CNF encoding, with clauses of size at most three. Introduce private coefficient bits c_ij, pin c_ij=A_ij, define z_ij=c_ij AND x_j, and compute each y_i as the XOR of its n products using a chain. An AND definition uses three clauses and seven literal occurrences; an XOR definition uses four clauses and twelve occurrences. There are n-1 XOR gates per row, of which the last has exposed output y_i. Thus F_A has exactly

$$V_F=3n^2,\quad C_F=8n^2-4n,\quad L_F=20n^2-12n.$$

For G use private bits pinned to u_i, products with y_i, an XOR chain, a unit requiring its final output to be one, and n pins for x. Counting the common boundary even when some variables do not occur gives

$$V_G=5n-1,\quad C_G=9n-3,\quad L_G=21n-11.$$

All gate definitions are functional, so existential projection preserves the two displayed relations. The combined formula has 3n^2+3n-1 distinct variables and 20n^2+9n-11 literal occurrences. With explicit binary variable identifiers and fixed clause delimiters its description size is N=Theta(n^2 log n), polynomial in b. The coefficient/template and explicit-CNF encodings must not be conflated. The CNF is a semantic presentation; it is not additional free matrix-dependent storage in the representation model below.

2. Exact representation and cost contract

Choose, for each n, an injective linear map

$$E:\mathbb F_2^d\longrightarrow\mathbb F_2^{d+r}.$$

The choice is public and independent of A,u,v. It may depend on n. Independent preprocessing of F_A stores exactly z=E vec(A), at fixed, publicly known bit positions. These d+r bits are the only A-dependent initial state. In particular there is no additional A-dependent layout, code, root selection, metadata, cached query result or uncharged pointer identity. S=d+r denotes stored bits, not machine words or heap nodes. Arbitrary linear preprocessing is allowed; multiplying by a supplied E takes O(d(d+r)) Boolean operations. The identity encoding takes O(d) preparation. The public description of E is not charged as A-dependent storage; query computation is free, which only strengthens the lower-bound adversary.

The other fragment is prepared independently from u,v. Give the query algorithm u,v and any state computed solely from them for free. This grants more access than a bounded local implementation, and cannot hide information about A. The algorithm is deterministic, exact for every A,u,v, and may choose stored-bit addresses adaptively. T counts reads of the initial encoded bits until the answer. Reads of a bit already learned can be cached. Computation, query-local allocation and access to copied values are free in this measure. Initial storage is immutable; any temporary work leaves both operands intact. Each invocation starts without A-dependent state from an earlier query beyond z. Amortization over an evolving cache is a different contract.

Word access is a separate variant: one probe reveals a fixed block of at most w stored bits. Its lower bound follows by expanding each word read into at most w bit reads. This does not charge merely the output bit or infer time from the number of possible answers.

3. A bound independent of the chosen linear basis

Proposition. With r=0, every allowed encoding and exact adaptive query algorithm has some query (u,v) requiring at least ceil(n^2/4) stored-bit probes on every matrix A. Reading all n^2 encoded bits is an upper bound. Therefore the optimum worst-case bit-probe order is Theta(n^2)=Theta(b2).

Proof. Fix a row-major vectorization and write q=vec(uv^T). Since E is invertible, (1) becomes the linear functional

$$q^T\operatorname{vec}(A)=c^Tz,\qquad c=E^{-T}q.$$

For this fixed query, every exact decision-tree path must read every coordinate where c is one. If a path omits such a coordinate, flip that encoded bit. Every encoded string is valid because E is bijective. All probed values, and hence the whole adaptive path, remain unchanged, but the correct answer flips. Thus adaptive access does not reduce the Hamming-weight cost of this parity.

For each coordinate k, c_k is a nonzero linear functional of q, hence equals u^T B_k v for some nonzero n by n matrix B_k. If B_k has rank rho_k, uniform independent u,v satisfy

$$\Pr[u^TB_kv=1]=\frac{1-2^{-\rho_k}}2\ge\frac14.$$

To see this, B_k v vanishes on exactly a fraction 2^{-rho_k} of v; for every other v, exactly half the u give inner product one. Linearity of expectation now gives E[wt(c)]>=d/4. Some query therefore has weight at least d/4, completing the proof. This lower bound permits every invertible linear change of basis, not just the raw matrix layout. It does not permit nonlinear encodings.

For fixed-block w-bit access the same proof gives T>=ceil(n^2/(4w)). Reading all blocks gives O(ceil(n^2/w)); hence this order is also sharp. In explicit CNF bits, the bit-probe lower bound is Omega(N/log N); in coefficient bits it is Omega(N_0). The bound is quadratic in the exposed width but remains linear in the information stored about A. No exponential compact-SAT bound follows.

4. Redundant linear storage: the exact remaining question

Let E have d+r rows and full column rank. For a fixed query q define

$$\tau_E(q)=\min\{\operatorname{wt}(a): E^Ta=q\}.$$

Exact characterization. The optimal number of encoded-bit probes for this query is tau_E(q), even if the deterministic exact algorithm is adaptive.

For the upper bound, read the coordinates selected by a minimizing a and XOR them. For the lower bound, let I be the positions inspected on a terminating path. If q is not in the span of the rows of E indexed by I, linear algebra gives a vector delta annihilated by these rows but with q^T delta=1. Replacing vec(A) by vec(A)+delta preserves the entire path and flips the answer. Thus q must lie in that span, implying |I|>=tau_E(q). Repeated probes do not help. Free computation can find a minimizing a by finite enumeration; no efficient synthesis claim is needed for this exact probe characterization.

The sustained question is now concrete:

$$L_n(r)=\min_{\operatorname{rank}E=n^2}\ \max_{u,v\in\mathbb F_2^n} \min_{E^Ta=\operatorname{vec}(uv^T)}\operatorname{wt}(a). \tag{2}$$

The proposition establishes L_n(0)=Theta(n^2). Our working hypothesis to test is L_n(n)=Omega(n^2): adding n linear stored bits to n^2 bits would not change the quadratic order. This is a hypothesis, not a theorem or a novelty claim. The zero-redundancy proof does not establish it: when r>0, the coordinates of z are dependent, flipping an arbitrary encoded bit need not give a valid input, and each q has multiple coefficient representations. The minimum over those representations cannot be interchanged with the earlier expectation.

This is the same family and observation throughout. The next step is to check (2) against established general-linear data-structure and rigidity results, and either prove the n-extra-bit hypothesis or construct a counterexample. A result for raw input plus advice does not by itself cover all E in (2).

5. Published comparison bounds and their limits

Chakraborty, Kamma and Larsen, Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication, Theorem 1.3, allow the raw matrix plus r arbitrary advice bits, with free advice access. For the same F_2 Boolean query they prove tr=Omega(n^3/log n) when n<=r<=n^2/64, and t=Omega(n^2/log n) when r<n. Here t counts raw matrix entries. We use the conservative 1/64 range stated in the proof, rather than the 1/4 range in its introduction. This is an imported systematic-storage theorem, not a theorem for arbitrary compiled layouts.

Chattopadhyay, Koucky, Loff and Mukhopadhyay, Simulation Beats Richness, Theorem I(a), give an unrestricted static encoding bound Omega(n/log(sw/n)) for exact VMV with s cells of w<=n bits. It applies to this family by (1). This published consequence is weaker numerically than our restricted proposition but allows substantially more representations. We do not claim it is the latest or strongest bound.

Natarajan Ramamoorthy and Rashtchian, Equivalence of Systematic Linear Data Structures and Matrix Rigidity, define general linear data structures and relate systematic linear queries to rigidity. Their rank-one query family is exactly the family in (2). Their systematic linear bound gives Omega(n^2) raw-bit probes at r=n, for sufficiently large n, in our matrix side-length notation. Their data length is n^2. This is direct prior art for the proposed investigation; a general re-encoding cannot silently be normalized to their raw-input layout at unchanged probe cost. Their paper also strengthens general cell-probe bounds. These results must be checked before claiming an extension of (2).

The parity decision-tree argument and the bilinear rank probability are standard elementary ingredients. This note’s contribution is the explicit constraint realization, precise representation scope, complete short proof, and a single residual storage question. No new fundamental theorem is claimed.

6. Why the old communication argument is insufficient here

For this family an unrestricted communication protocol can send u,v to the matrix holder using 2n bits; that party computes the answer and returns one bit. Thus total deterministic communication is at most 2n+1. A lower bound on total communication alone cannot yield the quadratic probe proposition. The latter uses the restriction that each reply must be an actual stored coordinate, rather than an arbitrary answer computed by a collaborating matrix holder. Asymmetric or structured communication methods can retain more information about the interface; they are not ruled out by this observation.

More generally, if complete raw descriptions of total length N_0 are retained, a uniform implementation can copy them in O(N_0) old-bit probes, then perform any terminating compatibility computation on the copies. This costs possibly large total work. It limits universal lower bounds on initial-storage probes under free computation; it says nothing comparable about total transitions. Polynomial initial storage alone does not remove this distinction.

7. Machine and preservation scope

Any implementation of the stated representation whose transition observes at most P encoded bits inherits a worst-case Omega(n^2/P) transition lower bound when r=0. Query-local allocations and persistent copies do not evade it: the necessary information must first be read. Raw bit cells may be packaged into fixed-shape pointer storage or separate tapes; every input-dependent structural field or metadata bit must still be included in the storage contract.

This does not prove the bound for all scaffold or TM presentations of the compatibility language. The compiler remains forward and resource-sensitive; it neither justifies arbitrary preloaded initialization nor turns this storage restriction into a universal recognizer restriction. A loader must be supplied and charged separately before invoking it. A scaffold-to-PEG language transfer still introduces reversal. No machine compiler is formalized or tested here.

The bound concerns one fixed compatibility operation, not equivalence of stored graph behavior under arbitrary future contexts. The mathematical argument preserves the exact Boolean answer; the scan upper bound preserves old storage. Stronger representation invariants require their own proof.

Verification

The checker and output check small CNF projections, the compatibility identity, the bilinear rank formula and basis-change support calculations. They do not certify the unrestricted proposition, imported theorems, redundant-storage hypothesis, word-RAM timing or a scaffold implementation. The proof above is written and has independent agent review; no Lean resource theorem was added.