Expanding dependencies force quadratic composition reads

Working research note, 2 October 2026.

Overview

Suppose an $n$-by-$n$ binary matrix $A$ is prepared once. Later, a query supplies two binary vectors $u,v$ and asks for the single parity $u^{\mathsf T}Av$. The representation may store $n^2$ transformed matrix bits and only $n$ additional linear bits. It may choose any invertible matrix coordinates, and the query may choose its reads adaptively. Can those freedoms make every answer use far fewer than $n^2$ reads?

A storage dependency is a parity relation among stored coordinates. In the class studied here, the dependencies expand: combining any small, nontrivial set of them affects many stored positions. Intuitively, a local choice of checks cannot hide in a small part of the representation. This spreading turns cheap query witnesses into functions that are approximately additive in $u$ and $v$. Classical homomorphism correction makes those functions close to bilinear ones, and a rank argument shows that the resulting answers cannot all have sparse support.

The result is a worst-case $\Omega(n^2)$ read lower bound for every fixed amount of expansion and every fixed degree bound, uniformly over all invertible coordinate choices. The note also constructs expanding examples for which the earlier bounded-size check-packing method gives only a linear bound. Expansion is a sufficient condition, not a characterization: the unrestricted quadratic conjecture remains open, and novelty has not been established.

The composition problem comes from two independently prepared fragments: one requires $y=Ax$, while the other requires $x=v,\ u^{\mathsf T}y=1$. Their compatibility is exactly $u^{\mathsf T}Av$. The proof below studies the read cost of deciding that compatibility in the precise immutable linear-storage model.

1. Exact representation and statement

Put $d=n^2$, $S=d+n$, with $n\ge2$. Let $H$ be a public binary $n$-by-$d$ matrix. Its columns have even weight, so $H^{\mathsf T}\mathbf1=0$. Suppose constants $\alpha,D>0$ satisfy

$$\operatorname{wt}(H^{\mathsf T}x) \ge \alpha n\min\{\operatorname{wt}(x),n-\operatorname{wt}(x)\} \quad(x\in\mathbb F_2^n), \tag{1}$$

and each row of $H$ has at most $Dn$ ones. Thus a selection of vertices, unless empty or full, meets many columns oddly; no individual vertex belongs to too many columns. For four-element columns these are conditions on an ordinary finite hypergraph, independent of the queries or the claimed lower bound. They can be checked by enumerating all vertex subsets and counting row degrees. We do not claim a polynomial-time test of (1), or infer it from a successful query test.

For any public invertible $d$-by-$d$ matrix $R$, define

$$P=R[H^{\mathsf T}\mid I_d],\qquad E=P^{\mathsf T}. \tag{2}$$

Preprocessing a matrix $A$ stores exactly $z=E\operatorname{vec}(A)$. Equivalently, it stores $w=R^{\mathsf T}\operatorname{vec}(A)$ and the $n$ bits $Hw$. All matrix-dependent initial information is included in these $S$ bits. Addresses, the matrices $H,R$, and the algorithm are public and independent of $A,u,v$. There is no retained raw copy, hidden metadata, address-dependent information or previous-query cache. Old bits are immutable. The other fragment and all preparation depending only on $u,v$ are free. The deterministic query must answer exactly for every $A,u,v$; reads may be adaptive, and computation and query-local allocation are free. Count all old-bit reads from composition through the final answer, including any deferred work.

Theorem. Every such representation and exact algorithm has worst-case read cost

$$\boxed{\displaystyle T_E\ge \frac{n^2-n}{4(1+2664D/\alpha)}.} \tag{3}$$

Reading the $d$ independent bits $w$ is sufficient. Consequently fixed positive expansion and a fixed degree bound give matching $\Theta(n^2)$ order, uniformly over $R$. The constant in (3) is a conservative proof constant, not an optimum. In fact the proof allows the $n$ advice bits to be read free, and lower-bounds the reads of $w$ alone.

The existing exact support characterization applies to adaptive algorithms. Write $q=\operatorname{vec}(uv^{\mathsf T})$. If every query costs at most $t$, choose a support representation

$$R^{-1}q=H^{\mathsf T}c(u,v)+b(u,v),\qquad \operatorname{wt}(b(u,v))\le t. \tag{4}$$

The functions $c,b$ can be completely nonlinear. They are proof witnesses, not a presumed linear or efficiently computable query scheduler. No bound on $\operatorname{wt}(c)$ is used.

2. The classical correction ingredient, with constants

We use uniform independent variables throughout this section. For a map $h:V\to W$ between finite binary vector spaces, put

$$\eta=\Pr[h(x)+h(y)\ne h(x+y)].$$

There is a linear map $g$ with $\Pr[h\ne g]\le6\eta$. Here is the standard majority-correction proof, included to make constants and vector-valued targets explicit. If $\eta\ge1/6$, take the zero map. Otherwise set $A_x(y)=h(x+y)+h(y)$. For each fixed $x$,

$$\Pr_{y,z}[A_x(y)\ne A_x(z)]\le2\eta.$$

Indeed their sum is the sum of the additive defects at $(x+y,z)$ and $(y,x+z)$, each a uniform pair. The collision probability is therefore at least $1-2\eta$; its largest atom has probability at least $1-2\eta$. Let that unique atom be $g(x)$. The identity

$$A_{x+z}(y)=A_x(z+y)+A_z(y)$$

and a union bound of $6\eta<1$ show that $g(x+z)=g(x)+g(z)$. If $h(x)\ne g(x)$, the additive test at $(x,y)$ fails with probability at least $1-2\eta$. Averaging proves $\Pr[h\ne g]\le\eta/(1-2\eta)\le6\eta$.

This is the classical homomorphism-testing method of Blum, Luby and Rubinfeld, whose paper credits Coppersmith for the simplified analysis. We use its binary special case, not a new stability theorem.

For a scalar function $f:V\times W\to\mathbb F_2$, let $\varepsilon_1,\varepsilon_2$ be the probabilities of failure of additivity in the first and second arguments. It has a bilinear approximation $B$ with

$$\Pr[f\ne B]\le222(\varepsilon_1+\varepsilon_2). \tag{5}$$

To see this, repair each first-argument slice to a linear function. The result $f_1(u,v)=\ell_v(u)$ differs from $f$ on a fraction $e\le6\varepsilon_1$. Its second-argument defect probability is at most $\varepsilon_2+3e$. A nonzero linear defect $\ell_v+\ell_{v'}+\ell_{v+v'}$ is one on exactly half of the $u$’s. Hence the coefficient map $v\mapsto\ell_v$, with values in the dual of $V$, fails its additive test with probability at most $2\varepsilon_2+6e$. Repair that vector-valued map by the preceding argument. Evaluation of the resulting linear coefficient map is bilinear, and its distance from $f$ is at most

$$e+6(2\varepsilon_2+6e) \le222\varepsilon_1+12\varepsilon_2 \le222(\varepsilon_1+\varepsilon_2).$$

This argument does not assume that arbitrary tensor-product codes are robustly testable. It proves exactly the bilinear case used here.

3. Expansion converts cheap answers into approximate bilinearity

The additive defect of $q(u,v)$ is zero in either argument. Taking a three-term defect in (4) gives

$$H^{\mathsf T}\delta c=\delta b,\qquad \operatorname{wt}(\delta b)\le3t.$$

By (1), the smaller of $\operatorname{wt}(\delta c)$ and $n-\operatorname{wt}(\delta c)$ is at most $3t/(\alpha n)$. The possible complement is important: even columns cannot distinguish a message from its complement.

For ordered indices $i,k$, put $f_{ik}=c_i+c_k$. If a defect vector has weight $s$, exactly $2s(n-s)$ ordered pairs have defect one. Taking the smaller complementary weight gives, at every triple,

$$\sum_{i,k}\mathbf1[\delta f_{ik}\ne0]\le6t/\alpha.$$

Average over triples in both directions. There is one reference index $k$ for which

$$\sum_i(\varepsilon_{1,ik}+\varepsilon_{2,ik}) \le\frac{12t}{\alpha n}.$$

Apply (5) to each $f_{ik}$, obtaining bilinear functions $B_i$. With $B=(B_i)_i$,

$$\mathbb E_{u,v}\operatorname{wt} (c+c_k\mathbf1+B)\le\frac{2664t}{\alpha n}. \tag{6}$$

The degree bound gives $\operatorname{wt}(H^{\mathsf T}e)\le Dn\operatorname{wt}(e)$. As $H^{\mathsf T}\mathbf1=0$, equation (6) implies

$$\mathbb E\operatorname{wt}(H^{\mathsf T}(c+B)) \le\frac{2664D}{\alpha}t. \tag{7}$$

Now the vector-valued function

$$L(u,v)=R^{-1}q(u,v)+H^{\mathsf T}B(u,v)$$

is bilinear. It extends to a linear map on the entire $d$-dimensional matrix space, with rank at least $d-n$: its first term is invertible, and the second term has rank at most $n$. Thus at least $d-n$ coordinates are nonzero bilinear forms. Every nonzero binary bilinear form is one on at least one quarter of uniformly random pairs, since a rank-$r$ form has probability $(1-2^{-r})/2$ of being one. Therefore

$$\frac{d-n}{4}\le\mathbb E\operatorname{wt}(L) \le\mathbb E\operatorname{wt}(b) +\mathbb E\operatorname{wt}(H^{\mathsf T}(c+B)) \le t(1+2664D/\alpha).$$

This proves (3). Bilinearity is a consequence of correction under expansion, not an assumption about the original read patterns. The proof remains valid under arbitrary $R$ precisely because the final argument uses rank.

4. Expansion coexists with the check-packing obstruction

For every fixed integer $\ell\ge2$, and every sufficiently large $n$, there is an $H$ with exactly $n^2$ weight-four columns such that:

• 1. holds with $\alpha=1/32$, and all row degrees are at most $9n$;
• no nonempty set of at most $\ell$ column positions sums to zero.

Here is an existence proof, including the loss incurred by removing bad configurations. Sample $M=n^2+\lceil\sqrt n\rceil$ independent uniform four-element subsets of $[n]$, with replacement. For a fixed subset of size $1\le s\le n/2$, an edge has odd intersection with probability at least

$$\frac{s\binom{n-s}{3}}{\binom n4}\ge\frac{s}{8n} \qquad(n\ge8).$$

Its odd-intersection count has mean at least $ns/8$. A binomial lower-tail bound gives probability at most $\exp(-ns/64)$ that the count is below $ns/16$. A union bound over all $s\le n/2$, using $\binom ns\le n^s$, tends to zero. Complementary subsets have identical odd-intersection counts. Each row degree has mean $4M/n=4n+o(1)$; an upper-tail bound and a union bound give maximum degree at most $9n$ with probability tending to one.

A zero-sum set of $j$ sampled positions uses at most $2j$ vertices, since every used vertex has even positive multiplicity. For a fixed set of $j$ positions, its probability is at most

$$\sum_{r\le2j}\binom nr \left(\frac{\binom r4}{\binom n4}\right)^j=O_j(n^{-2j}).$$

There are $O_j(n^{2j})$ choices of positions. Consequently the expected total number $X$ of forbidden sets of sizes $2,\ldots,\ell$ is $O_\ell(1)$. Markov’s inequality gives $X\le\lceil\sqrt n\rceil$ with probability tending to one. Choose an outcome meeting all three conditions. Delete one position from each forbidden set, then delete additional positions until exactly $n^2$ remain. In total exactly $\lceil\sqrt n\rceil$ positions were removed. Deletion creates no new zero sums, does not increase degrees, and leaves all odd-intersection counts at least

$$ns/16-\lceil\sqrt n\rceil\ge ns/32$$

for sufficiently large $n$. The case $j=2$ also removes repeated columns. The construction may depend on $\ell$; it makes no claim for a growing cutoff or about incidence-graph girth.

For $G=[I_n\mid H]$, a nonempty zero-sum set of at most $\ell$ columns must touch one of the $n$ unit-column positions. Hence disjoint or fractional packings of such checks, with load at most one on every position, have total weight at most $n$. Yet (3) forces quadratic reads under every quotient identification $R$. This exhibits a real separation between the earlier packing argument and the expansion-and-correction argument. It does not assert that every four-column family expands.

5. Relation to existing rigidity results

There is a classical language for the coordinate issue. Dvir, Golovnev and Weinstein, Definition 6 use strong row rigidity for row rigidity under every invertible right change of basis. Their Lemma 2 also identifies general linear data structures with sparse matrix factorizations. The systematic equivalence in Natarajan Ramamoorthy and Rashtchian, Theorem 1 uses the original coordinate metric; their Theorem 2 supplies the known quadratic bound for rank-one queries with $n$ advice bits in that metric. It cannot simply be applied after an arbitrary change of coordinates.

There is a terminology trap: the latter paper’s Section 3.1 remark calls an average-distance, fixed-coordinate property “strong rigidity.” That is not the universal-change-of-basis definition above. Its local-decoding argument upgrades worst-case distance to average distance, not ordinary rigidity to invariance under arbitrary matrix coordinates.

For precision, let $Q$ be the rank-one query set, including zero, and set

$$\sigma_n=\min_{R\in\mathrm{GL}(d,2),\ \dim U\le n} \max_{q\in Q}\operatorname{dist}(R^{-1}q,U).$$

The unrestricted linear-storage optimum satisfies the elementary dictionary

$$\sigma_n\le L_n(n)\le\sigma_n+n. \tag{8}$$

For the first inequality, choose $d$ independent rows of any full-rank encoding $E$ as coordinates $w$; the remaining $n$ rows are linear advice $Hw$. Dropping the cost of its reads gives distance to $U=\operatorname{im}(H^{\mathsf T})$. For the reverse inequality, store those coordinates and a basis of $U$ as advice, padded to $n$ bits, then read all advice and the support of a nearest residual. These changes are input-independent and preserve the storage budget. Thus a quadratic answer for the full model is equivalent, at this scale, to a universal-basis row-rigidity assertion. The query table has exponentially many rows; this observation is not a polynomial-size circuit lower bound.

The present theorem restricts the advice subspace to the expanding family (1). Its additional mathematical content within this investigation is the conditional correction argument and the simultaneous expansion/packing- obstruction construction. The rigidity dictionary, homomorphism correction, rank averaging, concentration and alteration ingredients are established methods. No novelty assertion follows from the literature searches.

6. Resources, verification and next question

Boundary width is $b=2n$. The matrix coefficient input has $N_0=\Theta(n^2)$ bits. The existing explicit fixed-shape 3CNF encoding, including variable names and auxiliary variables, has $N=\Theta(n^2\log n)$. Storage is $S=n^2+n$. For fixed $\alpha,D$, (3) is $\Omega(b^2)=\Omega(N_0)=\Omega(N/\log N)$, not an exponential SAT bound. Dense per-matrix preprocessing costs $O(Sd)$ Boolean operations for a supplied public encoding. Public $R,H$ have polynomial descriptions; selection of the probabilistic public family and testing expansion are not claimed to run in polynomial time. Query-local work remains free, so the matching upper bound concerns reads only.

The proof has received two independent agent checks in addition to the parent’s review. It has not been mechanized, and no finite experiment is presented as verification of its unbounded or probabilistic statements. These are bounds for the specified immutable linear bit-access model. A Turing-machine or scaffolding consequence still needs an access-preserving simulation with charged initialization and observations; none is supplied here. There is no unrestricted SAT, language-recognition, or P-versus-NP conclusion.

The next unresolved question is whether low-expansion dependencies admit a useful decomposition into expanding pieces with controlled overlaps and costs, or instead allow an explicit subquadratic orientation. This must be resolved within the same compact composition model. Expansion is sufficient, not necessary: disjoint row-parity storage already has a quadratic bound and need not satisfy (1). A decomposition would have to handle the actual message kernel and interaction between pieces, rather than assume global bilinear read choices or merely increase a fixed check-size cutoff.