Compact affine composition with redundant linear storage

Working research note, 2 October 2026.

Overview

Can a few extra stored answers make later combinations much cheaper? Consider an $n$ by $n$ binary matrix $A$. One constraint fragment requires $y=Ax$; an independently prepared fragment pins $x=v$ and requires $u^{\mathsf T}y=1$. Their compatibility is the bit $u^{\mathsf T}Av$ over $\mathbb F_2$. A stored row parity acts like a checksum: it can answer a query involving the whole row in one read instead of $n$ reads. The question is whether $n$ such extra bits can make every query comparably cheap.

The preceding note established the quadratic bound with no redundant linear storage. Here we establish the following bounds with exactly n redundant bits, retaining arbitrary linear re-encoding:

$$\frac{n\log_2 n}{48}\ \le\ L_n(n)\ \le\ n\lceil n/2\rceil \qquad(n\ge64). \tag{1}$$

Thus the extra bits do not collapse worst-case access to a constant or a logarithm: some query still needs at least $n\log_2 n/48$ reads. But the simple row-parity construction needs at most about $n^2/2$, leaving a large gap. The lower bound specializes a classical code-distance method and does not prove the working hypothesis $L_n(n)=\Omega(n^2)$.

The contract and what is counted

Put d=n^2. Before seeing u,v, preprocessing stores E vec(A), where E is any public full-column-rank (d+n) by d binary matrix. Its choice may depend on n, but not on A or the later query. These S=d+n bits are all matrix-dependent initial information. Their addresses and layout are fixed. No additional matrix-dependent code, metadata, pointers, root choices or retained raw copy are available. Preprocessing may perform arbitrary work; straightforward encoding costs O(d(d+n)) Boolean operations for a supplied E.

The other fragment is prepared separately. Its u,v and any state computed only from them are available free. The query must return the exact Boolean answer for every A,u,v. It may adaptively read encoded bits; computation, query-local allocation and access to copies are free. T counts initial-storage reads through the final answer, including work deferred after making a join handle. Each invocation starts without a previous matrix-dependent query cache. Old storage remains immutable. This is an access bound, not an optimal total-running-time claim.

The earlier support characterization removes adaptivity in this model:

$$\tau_E(q)=\min_{E^Ta=q}\operatorname{wt}(a),\qquad L_n(n)=\min_{\operatorname{rank}E=d}\max_{u,v}\tau_E(\operatorname{vec}(uv^T)). \tag{2}$$

Every correct terminating path needs at least tau_E(q) probes, and reading a minimum support attains that count with free computation. We use this fact without re-proving it. In particular a bound on max tau_E yields a query that is hard on every A, not merely a separately chosen hard matrix/query pair.

Why redundancy still leaves a lower bound

This proof specializes the code-distance method in Dvir, Golovnev and Weinstein, Static Data Structure Lower Bounds Imply Rigidity, Section 6.3 and Appendix A, Proposition 4, adapting Friedman. Primary source.

Let M have the m=2^(2n) query rows vec(uv^T). Its column space V has dimension d and minimum nonzero weight at least m/4. Choose minimum-support answers: M=HE, every row of H has weight at most t=max tau_E. Put K=rank H. Then

$$d\le K\le d+n.$$

Select K independent columns, then their k=floor(K/2) lightest. Each weighs at most 2mt/K. Their span W satisfies

$$\dim(W\cap V)\ge k-n.$$

The corresponding coefficient code D has length k and codimension at most n. For h=ceil(2n/log_2 n),

$$\sum_{j=0}^{h}\binom{k}{j}>2^n. \tag{3}$$

Sphere packing forces a nonzero D-word of weight at most 2h. Its nonzero image belongs to V, so

$$m/4\le (2h)(2mt/K),\qquad t\ge K/(16h)\ge n\log_2 n/48.$$

For completeness, the two numerical ingredients are explicit. Nonzero B has

$$\Pr_{u,v}[u^TBv=1]=(1-2^{-\operatorname{rank}B})/2\ge1/4.$$

For n>=64, writing ell=log_2 n gives

$$k\ge n^2/3,\quad h\le3n/\ell,\quad \log_2(k/h)\ge5\ell/6,\quad \binom{k}{h}\ge(k/h)^h\ge2^{5n/3}>2^n.$$

Here sphere packing applies because dim D>=k-n: disjoint radius-h balls would occupy more than 2^k strings if D had minimum distance greater than 2h. The m query rows are a proof device, not stored advice or an exponential formula input. Their common length cancels from the inequality.

A construction showing what the extra bits can do

Store the raw matrix and one parity p_i=sum_j A_ij for each row. This has exactly d+n linear bits and takes O(n^2) Boolean work to prepare. For every row selected by u, choose between:

• reading the entries selected by v;
• reading p_i and the entries selected by the complement of v.

Either choice computes the same row inner product. XOR the chosen row answers. If k is the weight of v, the probe count is

$$\operatorname{wt}(u)\min\{k,\,1+n-k\} \le n\lceil n/2\rceil.$$

The algorithm leaves both operands intact, uses one parity accumulator, and can make its choices before reading any matrix-dependent bit. Query scanning and address computation are not charged in this bit-probe measure. For v=(1,…,1), each selected row costs only one read. Thus extra storage really helps some queries, while the lower bound rules out uniformly constant or logarithmic access for this storage budget.

Sizes and machine consequences

The boundary width is b=2n. Coefficient descriptions have total size N_0=n^2+2n+O(log n). The earlier fixed-shape 3CNF realization has explicit binary-description size N=Theta(n^2 log n). No auxiliary formula or coefficient bits are available free as additional matrix storage. Thus the lower bound is

$$\Omega(b\log b) =\Omega(\sqrt{N_0}\log N_0) =\Omega(\sqrt{N\log N}).$$

It concerns composition plus the final Boolean query after independent preparation. It does not lower-bound preprocessing, allocation or the cost of merely constructing a lazy conjunction handle. It is not exponential in b and gives no superpolynomial SAT lower bound.

If a fixed-block word probe reveals at most w encoded bits, it gives the conditional lower bound ceil(n log_2 n/(48w)) word probes. Likewise a machine transition that can observe at most P such bits requires at least n log_2 n/(48P) transitions on a worst query. These consequences require the entire storage/initialization contract above. They do not cover every TM or scaffolding-automaton representation. Neither a free input-dependent initial graph nor arbitrary pointer identity is supplied by the compiler theorem. A loader and its cost would have to be specified separately. No new compiler or scaffold construction is asserted here; a later scaffold-to-PEG transfer would still reverse the recognized language.

Provenance and the precise remaining gap

The quantitative method is classical. The adaptation here uses the full rank-one query evaluation space directly, so it needs no randomly selected constant-rate subcode. The preceding support characterization justifies its use for exact adaptive queries with linear storage. Neither this application nor its explicit constant establishes novelty.

Ramamoorthy and Rashtchian’s Equivalence of Systematic Linear Data Structures and Matrix Rigidity, Theorem 2, gives a quadratic bound at this redundancy for raw input plus linear advice. Its hypothesis is stronger than our arbitrary re-encoding contract. Theorem 3 also implies an Omega(n) bound with S=n^2+n one-bit cells allowing arbitrary encodings, including nonlinear ones. That broader bound and our stronger linear-only bound concern different models. Primary source.

The unresolved question is still whether L_n(n)=Omega(n^2). One candidate route is to exploit more than the fact that each nonzero bilinear function is nonzero on at least one quarter of queries. In the proof, the extra storage permits an n-dimensional enlargement of the bilinear function space. Does the rank-one query structure prevent a sparse generating family for that enlargement? Equivalently, can one construct an encoding with uniformly subquadratic minimum supports in (2)? A systematic-storage theorem cannot answer this by silently changing basis. No claim of current open status in the literature is made.

Verification and continuation

This is a written proof with independent agent review, not a formal kernel proof. The checker checks the row-parity coefficient identity for all queries at n=2..6 and selected exact integer sphere-volume inequalities. Its output records the finite scope. Neither finite checks nor the previous Lean semantic lemma establish this unrestricted resource bound. The preceding note and its finite evidence remain available unchanged as the zero-redundancy baseline.