A sharp quadratic cost of combining compact fragments

Working research note, 3 October 2026.

A query supplies binary 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 first column. Direct storage reads $A_{ij}$ exactly when $u_i=v_j=1$; for uniform $u,v$, each entry is selected with probability $1/4$, so the mean is $n^2/4$ reads. Can an arbitrary linear encoding, helped by a small collection of extra stored parities, do better?

For the compact fragments studied here, the answer is no when the extra information has dimension smaller than linear in the matrix side length. Every encoding needs at least $(1/4-o(1))n^2$ reads on average. Storing the matrix entries themselves attains exactly $n^2/4$. This closes the logarithmic gap in the previous bound. The key is to count not only where a determinant vanishes, but how strongly it vanishes. That multiplicity bounds the rank lost at each binary input. A classical polynomial theorem limits the total multiplicity, yielding enough average rank for the entropy argument even when the determinant is zero at every binary input.

1. The distance statement

Let $T_1,\ldots,T_{n^2}$ be any basis of $\operatorname{Mat}_n(\mathbb F_2)$, with $n\ge2$, and set $G_i(u,v)=u^{\mathsf T}T_i v$. Both vectors are independent uniform binary vectors, including zero. Let $C\subseteq\mathbb F_2^{n^2}$ be nonempty with $|C|\le2^r$. Distance is unnormalized Hamming distance. Write $h_2$ for binary entropy and $h_2^{-1}:[0,1]\to[0,1/2]$ for its increasing inverse branch.

Theorem. For every such basis and set, if $0\le r\le n/2$, then $$\boxed{\mathbb E_{u,v}\operatorname{dist}(G(u,v),C) \ge \frac{n^2}{2}h_2^{-1}(1-2r/n).} \tag{1}$$ In particular, $r=o(n)$ gives $(1/4-o(1))n^2$. For $r\le n/4$, the bound is at least $a n^2/2$, where $h_2(a)=1/2$, so $a\approx0.1100$. The set need not be linear. The proof makes no efficiency assumption about finding its nearest point.

2. Multiplicity controls binary rank loss

For a nonzero formal polynomial $P$, its multiplicity at $x$ is the smallest total degree of a nonzero term in $P(x+Z)$. This is Hasse multiplicity, which works in characteristic two.

The multiplicity bound of Dvir, Kopparty, Saraf and Sudan, Lemma 2.7 in the 2009 preprint, states that for any finite subset $S$ of a field and nonzero polynomial of total degree $D$ in $m$ variables, $$\sum_{x\in S^m}\operatorname{mult}_x(P)\le D|S|^{m-1}. \tag{2}$$ There is no restriction $D<|S|$, and formal nonvanishing is sufficient.

Let $A(X)$ be an $n\times n$ matrix of affine linear polynomials over $\mathbb F_2$, with nonzero determinant $P$. At a point $x$ of rank $s$, constant invertible row operations make the last $n-s$ rows of $A(x)$ zero. In the translated determinant, every term then contains at least $n-s$ factors of positive degree. Hence $$n-\operatorname{rank}A(x)\le\operatorname{mult}_x(P).$$ Since $\deg P\le n$, (2) on the binary grid gives $$\mathbb E_x\operatorname{rank}A(x)\ge n/2. \tag{3}$$ Counting only whether a determinant vanishes misses this information. For example, $\operatorname{diag}(X,X+1)$ has formally nonzero determinant $X^2+X$, which vanishes at both binary points, but its rank is always one.

3. Partition the forms, then count unexplained information

Here is the matroid and entropy argument, with (3) replacing the earlier field-extension step. Work first over $K=\mathbb F_2(X_1,\ldots,X_n)$. For an index set $J$, let $\rho(J)$ be the rank of the columns $T_i^{\mathsf T}X$, $i\in J$, over $K$. Stack their evaluations at $n$ independent formal input vectors. The resulting map on matrices is injective: a matrix annihilating all these vectors is zero because the matrix of formal inputs is invertible. The original matrices are linearly independent even over this extension field. Each of the $n$ blocks has rank $\rho(J)$, so $$|J|\le n\rho(J).$$ Edmonds’s matroid partition theorem, Theorem 1, therefore partitions the $n^2$ indices into $n$ independent sets $B_j$. Each has size $n$. Their square column matrices $A_j(X)$ have nonzero determinants. By (3), $$M:=\mathbb E_u\sum_{j=1}^n\operatorname{rank}A_j(u)\ge n^2/2. \tag{4}$$

Choose a nearest point $Z(u,v)\in C$ with fixed tie breaking and write $e=G+Z$, $\varepsilon=\mathbb E\operatorname{wt}(e)$. For each fixed $u$, select a column basis $K_j(u)\subseteq B_j$ of $A_j(u)$. Selection depends on $u$, not $v$. Its output bits are independent uniform bits as $v$ varies. Put $p_i(u)=\Pr_v[e_i=1]$. Entropy gives $$|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)).$$ The groups are disjoint. Consequently their total expected selected error $E_{\rm sel}$ is at most $\varepsilon$, without any independence assumption between selection and errors. Summing and applying concavity only to the selected coordinates, of total weight $M$, gives $$M\le nr+M h_2(E_{\rm sel}/M).$$ Since $M\ge n^2/2\ge nr$, $$\varepsilon\ge E_{\rm sel}\ge M h_2^{-1}(1-nr/M) \ge \frac{n^2}{2}h_2^{-1}(1-2r/n).$$ The inverse implication remains valid if the error fraction exceeds one half. The last inequality follows because both nonnegative factors are nondecreasing with $M$. This proves (1).

4. Exact composition contract and matching construction

The fragments are $F_A(x,y):y=Ax$ and $Q_{u,v}(x,y):(x=v)\land(u^{\mathsf T}y=1)$. Compatibility asks whether $u^{\mathsf T}Av=1$. The boundary has $b=2n$ variables. The established fixed-shape 3CNF construction has $3n^2+3n-1$ distinct variables and $20n^2+9n-11$ literal occurrences, with disjoint private auxiliaries. Binary variable identifiers give actual input length $N=\Theta(n^2\log n)$. The coefficient representation instead has $N_0=\Theta(n^2)$.

Independent matrix preparation stores $w=R^{\mathsf T}\operatorname{vec}(A)$ and $Hw$, where $R$ is any public invertible matrix of order $d=n^2$. The encoding and addresses are fixed independently of both fragments. For the prescribed family, $H$ has $n$ rows and rank $r$, with $U=\operatorname{im}H^{\mathsf T}$. Storage is exactly $S=d+n$ bits; a supplied dense encoding takes $O(Sd)$ Boolean operations to prepare. The public encoding description is fixed per size, rather than part of the varying input. These bits are the entire matrix-dependent initial state. There is no hidden raw copy, pointer-identity channel, metadata or prior-query cache.

Query-only preparation and subsequent local computation and allocation are unrestricted and free. Old storage is immutable. The combining algorithm is deterministic, adaptively reads bits, and must be correct for every $A,u,v$. Charge all such observations until the answer, including work deferred after creation of a composition handle. The established support characterization gives, on each individual $A$, $$T(A,u,v)\ge\operatorname{dist}(R^{-1}\operatorname{vec}(uv^{\mathsf T}),U).$$ This bound already grants the advice bits for free. The coordinates of the query map form a basis of bilinear forms, so (1) applies to every $R$.

In the prescribed family, $n=2^{5k}$, $U=\operatorname{RM}(k,10k)$, and $r=\sum_{i=0}^k\binom{10k}{i}\le n^{2h_2(1/10)}=o(n)$. Take monomial evaluation rows for $H$ and pad with $n-r$ zero rows. Thus every allowed encoding and exact algorithm has, on every stored matrix, $$\mathbb E_{u,v}T(A,u,v)\ge(1/4-o(1))n^2. \tag{5}$$ For a matching construction choose $R=I$, ignore advice, and read precisely those $A_{ij}$ for which $u_i v_j=1$. XOR their values. This algorithm is exact on every input and uses mean reads $$\mathbb E[\operatorname{wt}(u)\operatorname{wt}(v)]=n^2/4.$$ The optimal mean over permitted encodings and universally correct algorithms is therefore $n^2/4+o(n^2)$, uniformly in $A$. Worst-case optimal order is also $\Theta(n^2)$, since the mean lower bound and reading all basis bits give matching orders. In boundary and input terms the order is $\Theta(b^2)=\Theta(N/\log N)=\Theta(N_0)$, not exponential in the width. The mean leading term is $b^2/16$.

5. What is closed and what remains

The prescribed family’s quadratic mean-read question is settled, with a matching leading constant. More generally, (1) applies to any extra parity space of dimension at most $n/4$, and gives the same leading asymptotic bound whenever that dimension is $o(n)$.

The direct continuation considered $n$ genuinely independent extra stored bits. The entropy bound above becomes vacuous when $r\ge n/2$. The subsequent linear-advice theorem resolves quadratic order for every injective linear encoding into $n^2+n$ bits by applying this method to sums of queries. Its leading mean constant is not yet sharp. The earlier general bound was $n\log_2 n/48$. The all-map external-repair assertion and stronger tail estimates also remain unproved; they are not needed for (5).

The rank step is a direct application of the classical multiplicity theorem; the grouping uses classical matroid partition, followed by elementary entropy inequalities and the existing access characterization. The additional content here is their resource-preserving combination and the sharp mean cost for this precisely specified compact family. Historical novelty is not established. This is a written proof, not a proof-assistant verification or an inference from finite experiments. Mechanizing the present proof would not decide the remaining full-redundancy question. A read returning at most $w$ bits yields only the corresponding bound divided by $w$. No claim transfers automatically to unrestricted Turing machines, scaffolding automata, SAT algorithms, or P versus NP.