Nearly quadratic reads after independent preparation

Working research note, 3 October 2026.

Why stored answers can still be expensive to combine

Suppose a binary matrix is prepared and stored before a later query is known. The query supplies vectors $u,v$ and asks for the parity $u^{\mathsf T}Av$. For a $2\times2$ matrix, taking $u=(1,1)$ and $v=(1,0)$ asks for the parity of the two entries in the first column. An encoding can store that particular parity directly, but other choices of $u,v$ ask for different parities. How many stored bits must an exact algorithm read on average when the prepared matrix meets the query?

Our current model permits any invertible linear encoding of the matrix, plus a small space of extra stored parities. The encoding can make individual queries cheap. The result below says that, when the extra space has dimension at most order $n/\log n$, it cannot make the average query cheaper than order $n^2/\log n$. This applies to the Reed-Muller family previously studied and improves its $\Omega(n^{9/5})$ lower bound.

The proof groups output coordinates so that each group carries independent information for enough inputs. A small advice space cannot explain all that information; many coordinate errors must remain. Those errors become required reads through the established support characterization. The grouping is a proof device, not a restriction on the query algorithm or a new storage layout.

The remaining logarithmic gap is real in the statement: no quadratic bound or matching subquadratic query algorithm is proved here. The classical ingredients, verification scope and unresolved stronger claims are recorded at the end.

1. The precise distance theorem

All matrix ranks are over $\mathbb F_2$, unless another field is named. Let $n\ge2$, $d=n^2$, and let $T_1,\ldots,T_d$ be any basis of $\operatorname{Mat}_n(\mathbb F_2)$. Define $$G_i(u,v)=u^{\mathsf T}T_i v, \qquad u,v\text{ independent and uniform in }\mathbb F_2^n.$$ Zero inputs are included. Let $C\subseteq\mathbb F_2^d$ be any nonempty set with $|C|\le2^r$, and put $$\varepsilon=\mathbb E_{u,v}\operatorname{dist}(G(u,v),C), \qquad L=\lceil\log_2(2n)\rceil.$$ Distance is ordinary, unnormalized Hamming distance. Write $h_2(t)=-t\log_2t-(1-t)\log_2(1-t)$, with the usual endpoint values, and let $a\in(0,1/2)$ be the unique number satisfying $h_2(a)=1/2$. Numerically, $a$ is about $0.1100$.

Theorem. For every such basis and every such set, $$r\le\frac{n}{4L} \quad\Longrightarrow\quad \boxed{\varepsilon\ge\frac{a n^2}{2L}.} \tag{1}$$ The set $C$ need not be linear. No efficient nearest-point algorithm is assumed. The argument even permits a different set $C_u$ for each $u$, provided each has at most $2^r$ elements and is fixed before $v$ is drawn. Only the fixed linear-space case is needed for our stored-parity application.

2. A partition with enough average rank

Introduce formal variables $X=(X_1,\ldots,X_n)$ and work over the rational function field $K=\mathbb F_2(X)$. Regard the vectors $T_i^{\mathsf T}X\in K^n$ as a represented matroid. For an index set $J$, denote their rank by $\rho(J)$. We first check $$|J|\le n\rho(J). \tag{2}$$

Take $n$ independent formal vectors $X^{(1)},\ldots,X^{(n)}$, all in one common rational function field. The matrix having these vectors as columns is invertible: its determinant is a nonzero polynomial. Consequently the map $$T\longmapsto (T^{\mathsf T}X^{(1)},\ldots,T^{\mathsf T}X^{(n)})$$ is injective. The matrices indexed by $J$ remain linearly independent after extension of scalars, so the stacked evaluation has rank $|J|$. Each of its $n$ blocks has rank $\rho(J)$. Rank subadditivity proves (2).

Edmonds’s matroid partition theorem now partitions the indices into $n$ independent sets $B_1,\ldots,B_n$. Each has exactly $n$ elements, since there are $n^2$ elements in total and each independent set has size at most $n$. Let $A_j(X)$ be the square matrix whose columns are $T_i^{\mathsf T}X$, for $i\in B_j$. Its determinant is a nonzero polynomial of total degree $n$.

A formal nonzero determinant need not be nonzero at enough binary inputs. We therefore evaluate over $\mathbb F_q$, where $q=2^L\ge2n$. The classical polynomial zero bound gives $$\Pr_{X\in\mathbb F_q^n}[\det A_j(X)=0]\le n/q\le1/2, \qquad \mathbb E\operatorname{rank}_{\mathbb F_q}A_j(X)\ge n/2. \tag{3}$$ The zero bound follows by induction on the number of variables: separate the highest power of the last variable, apply induction to its leading coefficient, and use the univariate root bound on the remaining fibers. A nonzero polynomial of total degree $D$ has at most $Dq^{m-1}$ zeros on $\mathbb F_q^m$. We apply it to each determinant separately; simultaneous nonvanishing is unnecessary.

Choose a binary basis $\beta_1,\ldots,\beta_L$ of $\mathbb F_q$. A uniform extension-field input has the unique expansion $X=\sum_\ell\beta_\ell u_\ell$, with independent uniform binary vectors $u_\ell$. Since the matrices depend linearly on the input, $$\operatorname{rank}_{\mathbb F_q}A_j(X) \le\sum_{\ell=1}^L\operatorname{rank}_{\mathbb F_2}A_j(u_\ell).$$ Binary ranks are unchanged by field extension. Taking expectations in this inequality and using (3), then summing over groups, proves $$M:=\mathbb E_u\sum_{j=1}^n\operatorname{rank}A_j(u) \ge\frac{n^2}{2L}. \tag{4}$$ This step is the source of the logarithmic loss.

3. Advice cannot explain all the selected information

Choose a nearest point $Z(u,v)\in C$, resolving ties in a fixed way, and write $e=G+Z$. Then $\mathbb E\operatorname{wt}(e)=\varepsilon$. For each fixed $u$, choose a column basis $K_j(u)\subseteq B_j$ of $A_j(u)$. This selection depends on $u$ and the public matrices, not on $v$. Put $p_i(u)=\Pr_v[e_i(u,v)=1]$.

As $v$ varies uniformly, the selected coordinates of $G$ are independent uniform bits. Their entropy, measured in bits, is therefore $|K_j(u)|$. Since they are determined by $Z$ and their selected errors, $$|K_j(u)| \le H(Z\mid u)+H(e_{K_j(u)}\mid u) \le r+\sum_{i\in K_j(u)}h_2(p_i(u)). \tag{5}$$ No independence of $Z$ and the errors is used.

The groups are disjoint, so selected errors are counted at most once. Thus $$E_{\mathrm{sel}}:= \mathbb E_u\sum_j\sum_{i\in K_j(u)}p_i(u) \le\varepsilon. \tag{6}$$ Sum (5) over groups and average over $u$. Apply entropy concavity with weights $\Pr[u]$ on the selected pairs $(u,i)$. Their total weight is exactly $M$, giving $$M\le nr+M h_2(E_{\mathrm{sel}}/M). \tag{7}$$ This is where retaining only the independent coordinates matters. Including all coordinates in the entropy sum would lose an additional $\log\log n$ factor. Selection can correlate with errors, but (6) is a direct inequality, not a multiplication of marginal probabilities.

Under the hypothesis of (1), $nr\le n^2/(4L)\le M/2$. Equation (7) therefore implies $h_2(E_{\mathrm{sel}}/M)\ge1/2$, hence $E_{\mathrm{sel}}\ge aM$. This implication also holds if the ratio exceeds $1/2$. Combining (4) and (6) proves the theorem.

4. Consequence for compact-fragment composition

Use the previously specified fragments $$F_A(x,y):y=Ax, \qquad Q_{u,v}(x,y):(x=v)\land(u^{\mathsf T}y=1).$$ Their compatibility bit is $u^{\mathsf T}Av$; the common boundary has $b=2n$ variables. The fixed-shape encoding has $3n^2+3n-1$ distinct variables and $20n^2+9n-11$ literal occurrences in the combined 3CNF. Private variables of the two fragments are disjoint. Explicit binary variable identifiers give actual formula length $N=\Theta(n^2\log n)$. The direct coefficient description instead has $N_0=\Theta(n^2)$; these are different representations of the input.

The matrix is independently prepared as $$w=R^{\mathsf T}\operatorname{vec}(A),\qquad Hw,$$ with public invertible $R$, public $H$, and advice space $U=\operatorname{im}H^{\mathsf T}$ of dimension $r$. For the prescribed family, $H$ has $n$ rows, so stored size is $S=n^2+n$ bits. The matrices and fixed addresses are chosen independently of $A,u,v$. These stored bits are the entire matrix-dependent initial state: no extra raw copy, metadata, pointer identity or earlier-query cache is available. A supplied dense encoding takes $O(Sn^2)$ Boolean operations to prepare. Its public description is fixed per input size and is not part of the varying fragment; no bound on this nonuniform public setup is needed.

The other fragment may be prepared using arbitrary query-only work. The combining algorithm is deterministic and exact, may choose reads adaptively, and may use arbitrary local computation and allocation. Old storage is immutable. All observations of old bits are charged through the final answer, including deferred query work after creating a composition handle. Free local computation strengthens the lower bound; it does not assert a fast query algorithm.

The established support characterization implies, on every stored matrix $A$, $$T(A,u,v)\ge \operatorname{dist}(R^{-1}\operatorname{vec}(uv^{\mathsf T}),U). \tag{8}$$ Each coordinate of the displayed query map is a bilinear form, and its coefficient matrices form a basis. The theorem applies to $C=U$, even if all advice reads are granted free. Therefore $$\forall R,H\text{ with }r\le n/(4L),\quad \forall\text{ exact allowed algorithms},\quad\forall A, \qquad \mathbb E_{u,v}T(A,u,v)\ge\frac{a n^2}{2L}. \tag{9}$$ This is a mean lower bound on every matrix, not merely a worst-case pair. It also gives a hard query uniformly over stored matrices through (8). Allowing a read to reveal at most $w_0$ old bits gives only the corresponding bound divided by $w_0$; it is not a unit-cost word lower bound of the same size.

For the continuing family $$n=2^{5k},\quad U=\mathrm{RM}(k,10k),\quad r=\sum_{i=0}^k\binom{10k}{i},$$ the standard binomial entropy estimate gives $r\le n^{2h_2(1/10)}=o(n/\log n)$, since $2h_2(1/10)<1$. Thus (9) holds for all sufficiently large $k$, and establishes $$\boxed{\mathbb E T= \Omega(n^2/\log n)=\Omega(b^2/\log b) =\Omega(N/(\log N)^2).} \tag{10}$$ In coefficient-description size it is $\Omega(N_0/\log N_0)$. Reading and decoding all $n^2$ basis bits gives an $O(n^2)$ upper bound with free computation. Hence the read bounds are within a logarithmic factor; there is no matching upper bound here. The hard formulas are polynomial in boundary width. This is not an exponential-in-width claim disguised by a large input.

The distance theorem also covers any injective linear storage with at most $n/(4L)$ extra bits: select a basis among its stored linear forms and view the remaining forms as advice. It does not cover every encoding with $n$ independent extra bits. For that larger redundancy, the established general bound remains as previously stated.

5. What has and has not been resolved

This improves the bound for the same Reed-Muller family and bypasses the unresolved conditional-entropy selection step. It uses no Reed-Muller property beyond its dimension. It does not prove the earlier all-map external-repair inequality, an exponentially small lower tail, or the desired $\Omega(n^2)$ mean bound. Those stronger assertions remain open.

The relevant classical inputs are Edmonds’s partition criterion, the Schwartz-Zippel polynomial zero bound, and entropy subadditivity and concavity. The additional argument here is their combination with extension-field rank averaging and disjoint selected coordinates, followed by the existing bit-access translation. This describes the proof’s content, not a claim of historical originality.

Earlier comparisons with systematic-storage and general linear data-structure bounds are recorded in the model note. A systematic raw-matrix theorem cannot be applied to an arbitrary invertible encoding without checking its probe costs. Likewise, (9) transfers to a particular machine implementation only if its initialization and observations satisfy this contract and each step reveals a bounded number of charged bits. No unrestricted SAT, Turing machine, scaffolding-automaton or language-recognition lower bound follows.

The next quantitative question is whether the logarithmic loss can be removed for this same family, or shown necessary by a matching encoding. The extension-field step identifies one specific place to examine; it does not establish a stronger binary rank estimate.

Sources and proof status

• Jack Edmonds, Minimum Partition of a Matroid Into Independent Subsets, Journal of Research of the National Bureau of Standards 69B (1965), Theorem1. Its criterion is precisely (2).
• J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, JACM 27 (1980), Lemma1 and Corollary1. The finite-grid bound used in (3) is also proved briefly above.
• The constraint encoding, exact adaptive support characterization, previous lower bounds and classical data-structure comparisons are in the linked foundations notes.

The proof above is written mathematics with imported classical theorems. Independent agent review checked both the field-extension and selected-entropy steps. No finite experiment is used as evidence for an unrestricted theorem, and no proof-assistant verification or novelty certification is claimed.

Subsequent result

The multiplicity argument removes the logarithmic loss and gives a matching mean leading constant for the prescribed family. The argument above is retained as the preceding proof.