Working research · 2 October 2026

Overlapping sparse dependencies still require quadratic reads

Picture each zero-sum storage relation as a check joining several stored bits. The checks may overlap, but suppose no stored bit belongs to more than three independent checks. We prove that this locally sparse web still forces some matrix query to read quadratically many bits. The proof extracts disjoint obligations that every possible read pattern must meet.

The general quadratic conjecture remains unresolved. A separate construction shows why looking only for bounded-size obligations cannot settle the next case.

The representation condition and the bound

Over the binary field, independently prepared fragments require $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$ . Compatibility is the bit $u^{\mathsf T}Av$ . Store linear bits $z=E\operatorname{vec}(A)$ , where

d=n^2,\quad S=d+n,\quad \operatorname{rank}E=d,\qquad K=\ker E^{\mathsf T},\quad\dim K=n.

A vector in K describes a zero-sum relation among stored bits. Choose a basis of these relations as the rows of a matrix G. Suppose each column of G has at most three ones: each position participates in at most three chosen basis relations. Then, for every such E and every exact query algorithm,

\boxed{\displaystyle T_E\ge\frac{n(n+5)}{96}\qquad(n\ge2).}

Here T is worst-case stored-bit reads through the final answer. Adaptive reads and nonlinear choices of read patterns are allowed. Reading a basis of d stored bits is always sufficient, so the optimal asymptotic cost within this representation class is $\Theta(n^2)$ . The constant $1/96$ is a consequence of this proof, not an optimal constant.

The condition can be certified without solving queries: check that G has n independent rows, that $GE=0$ , and that its columns have weight at most three. These are polynomial-time checks of a supplied basis; finding such a basis is a separate problem. This condition concerns relations among stored bits, not the number of matrix entries used to form each stored bit. The matrix coordinates may be chosen arbitrarily.

Disjoint obligations force reads

A set J of generator columns summing to zero gives a vector $h_J\in K^\perp$ , its indicator. Thus the parity of a read pattern on J depends only on its query, not on which representative was chosen. There is a unique nonzero linear functional of the matrix-query coefficients with this parity. On rank-one queries it is a nonzero bilinear form:

h_J^{\mathsf T}a=u^{\mathsf T}B_Jv, \qquad E^{\mathsf T}a=\operatorname{vec}(uv^{\mathsf T}),\qquad B_J\ne0.

For uniform independent $u$ and $v$ , this bit is one with probability at least one quarter. Whenever it is one, every valid pattern must use at least one position in J. If m such nonempty sets are disjoint, their costs add:

\mathbb E_{u,v}\min_{E^{\mathsf T}a=\operatorname{vec}(uv^{\mathsf T})} \operatorname{wt}(a)\ge m/4,\qquad T_E\ge m/4.

This also bounds adaptive algorithms. On any terminating transcript, the requested functional must lie in the span of the inspected rows of E. Otherwise a perturbation of A invisible to every inspected bit would preserve the transcript while flipping the answer. Thus every exact transcript supplies a valid representative supported on its inspected positions.

This uses ordinary code duality and the existing bilinear averaging fact. It imposes no linearity on the map selecting a read pattern.

Why participation three supplies enough obligations

Repeatedly remove a nonempty zero-sum set of at most four columns of G, until none remains. Removed sets are disjoint. In the remaining matrix, columns are distinct and nonzero. At most n have weight one and at most $C=\binom n2$ have weight two.

Let $M$ be the number of remaining weight-three columns, viewed as triples of row indices. For each pair $p$ of row indices, let $d_p$ count triples containing $p$ . Then

\sum_p d_p=3M,\qquad \sum_p\binom{d_p}{2}\le C.

For the inequality, two triples sharing p differ on exactly two indices. There are only C possible differences. Two distinct unordered triple-pairs with the same difference cannot share a triple, since cancellation would make the pairs identical. They would therefore be four distinct columns summing to zero, contrary to termination.

Convexity now gives

\frac12\left(\frac{(3M)^2}{C}-3M\right)\le C, \qquad M\le\frac{2C}{3}.

At most $n+C+\lfloor2C/3\rfloor$ columns remain. Thus at least the following number were removed, in groups of size at most four:

S-n-C-\lfloor2C/3\rfloor \ge\frac{n(n+5)}6.

There are at least $n(n+5)/24$ disjoint obligations. Applying the packing argument proves the displayed lower bound. This is uniform over all identifications of the quotient by K with the matrix space.

Participation two gives a sharper constant

With at most two ones per column, there are at most $n(n+1)/2$ distinct nonzero column values. Group equal columns. In a group of size $l$ , every pair of positions gives a nonzero dual check. If a representative uses $w$ positions, exactly $w(l-w)$ pairs disagree. Each such check is one on at least a quarter of queries, while $w(l-w)\le lw$ . The expected group cost is therefore at least $(l-1)/8$ . Every zero column contributes at least $1/4$ .

T_E\ge\frac{S+z-h}{8} \ge\frac{n(n+1)}{16},

Here z counts zero columns and h counts distinct nonzero columns. This includes overlapping relations. For example, take every column of weight one or two twice. There are S columns and more than n distinct nonzero values. An invertible change of relation basis preserves that count, whereas a disjoint-support basis permits at most n values. Thus this example cannot be reduced to disjoint relation blocks by changing the basis.

No fixed check size settles participation four

The limitation is stronger than a failure to find pairs or quadruples. For every fixed integer $\ell\ge2$ , and all sufficiently large $n$ , there is a rank- $n$ generator $G$ with $S$ columns of weight at most four such that every nonzero dual check of size at most $\ell$ touches one designated set of only $n$ positions. Any disjoint packing of these checks has size at most $n$ . The same bound holds for fractional packings with total load at most one on each position.

Construction. Keep all $n$ unit columns. Independently select each weight-four column with probability

p=\frac{2n^2}{\binom n4}.

For sufficiently large $n$ this is at most one, and the expected number $M$ selected is $2n^2$ . A zero-sum set of $j$ distinct weight-four columns uses at most $2j$ row indices, since each used index occurs an even number of times. There are $O_\ell(n^{2j})$ such sets for $j\le\ell$ . Since $p=O(n^{-2})$ , the expected number $X$ of these forbidden sets, summed over $2\le j\le\ell$ , is $O_\ell(1)$ . Consequently

\mathbb E(M-X)=2n^2-O_\ell(1)>n^2.

Some outcome retains at least $n^2$ columns after deleting one weight-four column from each forbidden set. Keep exactly n squared of those, together with the $n$ unit columns. Deletion creates no new zero sums; the units guarantee rank $n$ . Every remaining check of size at most $\ell$ must therefore use a unit position. Summing the capacity constraints on those $n$ positions bounds even a fractional packing by $n$ .

This is a standard probabilistic alteration argument. The family may depend on ℓ. It does not produce cheap rank-one queries and does not refute the quadratic conjecture, even for participation four. It shows that increasing a fixed check-size cutoff cannot by itself complete this proof strategy.

Resources, provenance and remaining question

The model charges all matrix-dependent information in $S$ immutable stored bits, with fixed public addresses and no earlier-query cache. $E$ is public and input-independent. Query-vector preparation and query-local computation and allocation are free. Reads are charged from composition through the final answer, including deferred work. Boundary width is $b=2n$ ; coefficient input size is $\Theta(n^2)$ , and the explicit fixed-shape 3CNF size is $\Theta(n^2\log n)$ , including variable names and auxiliaries. Dense per-matrix preprocessing takes $O(Sn^2)$ Boolean operations.

G and E have polynomial-size descriptions. A supplied sparse basis is efficiently checked; the greedy packing can also be found in polynomial time by enumerating subsets of size at most four. No efficient synthesis of the probabilistic limiting family is claimed. These are bit-read bounds; no unrestricted SAT or Turing-machine/scaffold time bound follows without a separate access simulation.

Parity-check dependence and forbidden even configurations belong to classical coding and extremal-set theory. For a primary comparison,Tsunoda and Fujiwara, Section IIidentifies the zero-erasure X-code condition with absence of small dependent column sets. Their additional erasure-tolerance bounds have different hypotheses and are not imported here. The counting and alteration arguments above are supplied in full. Their budget-specific composition consequence is useful here; novelty is unestablished.

The proofs received independent agent review. Thefinite checkerand resultscorroborate only small extremal counts and concrete packing certificates. There is no proof-assistant verification or finite verification of the asymptotic existence argument.

We have a complete quadratic-order answer for participation at most three. The unrestricted general lower bound remains $n\log_2(n)/48$ . The remaining question concerns encodings with more complicated overlapping relations, where bounded-size packing is insufficient. Any further argument must use additional structure of the rank-one query family or a genuinely stronger way of charging overlapping obligations.