Quadratic composition cost with arbitrary linear advice

Working research note, 3 October 2026.

Suppose one fragment describes a binary matrix $A$, while a second supplies vectors $u,v$ and asks whether $u^{\mathsf T}Av=1$. Preparing the matrix in advance can save work. For a $2\times2$ matrix, $u=(1,0)$ and $v=(1,1)$ ask for the parity of the first row, so one stored row-parity bit answers that query in one read. Other choices ask for columns or mixtures of entries. Can an arbitrary linear encoding of all $n^2$ entries, together with $n$ extra parity bits, make every query substantially cheaper?

It cannot, in the exact bit-access model specified below. Every encoding requires $\Omega(n^2)$ reads on average, on every stored matrix. Reading entries directly gives $O(n^2)$, so both optimal mean and worst-case costs have order $\Theta(n^2)$. This resolves the order question left by the small-advice theorem. The sharp leading constant for the larger advice class remains unknown.

The proof combines four independent queries. Because the extra stored parities form a linear space, four cheap approximations would combine into a cheap approximation of their sum. The summed query exposes enough independent information for the earlier matroid and multiplicity argument; its lower bound then transfers back to one query. The algorithm itself is still required to answer only one compatibility query.

1. Statement

Work over $\mathbb F_2$. Let $T_1,\ldots,T_{n^2}$ be any basis of $\operatorname{Mat}_n(\mathbb F_2)$, and put $$G(u,v)=(u^{\mathsf T}T_i v)_{i=1}^{n^2}.$$ Let $C\le\mathbb F_2^{n^2}$ have dimension $r$. Both input vectors are independent and uniform, including zero. Distance is unnormalized Hamming distance. Write $h_2^{-1}:[0,1]\to[0,1/2]$ for the increasing inverse branch of binary entropy.

Theorem. For every positive integer $k$, set $p=\lceil n/k\rceil$. Whenever $2pr\le n^2$, $$\boxed{\mathbb E\operatorname{dist}(G(u,v),C) \ge \frac{n^2}{2k} h_2^{-1}\!\left(1-\frac{2pr}{n^2}\right).} \tag{1}$$ In particular, $r\le n$, $k=4$, and $n\ge4$ give $$\mathbb E\operatorname{dist}(G,C) \ge \frac{n^2}{8}h_2^{-1}\!\left(1-\frac{2\lceil n/4\rceil}{n}\right) =\left(\frac{a}{8}-o(1)\right)n^2, \tag{2}$$ where $h_2(a)=1/2$, $a\approx0.1100$. Thus the asymptotic constant in this lower bound is about $0.01375$. It is not claimed optimal. The theorem also gives quadratic order for $r\le cn$ for any fixed constant $c$, by choosing a fixed integer $k>2c$.

2. Why summing queries helps

Write $d_C(x)=\min_{c\in C}\operatorname{wt}(x+c)$. Linearity gives $$d_C(x_1+\cdots+x_k)\le\sum_{a=1}^k d_C(x_a): \tag{3}$$ add minimizing codewords and use the Hamming triangle inequality. For independent pairs $(u_a,v_a)$, define $$Y=\sum_{a=1}^k G(u_a,v_a),\qquad \varepsilon_k=\mathbb E d_C(Y),\qquad \varepsilon=\mathbb E d_C(G(u,v)).$$ Then $\varepsilon_k\le k\varepsilon$. This is the only step requiring $C$ to be linear. An arbitrary set of $2^r$ advice vectors need not be closed under these sums.

3. Fewer independent groups suffice for the sum

Take independent formal vectors $X_1,\ldots,X_k$, each of length $n$, and work over the rational function field $K=\mathbb F_2(X_1,\ldots,X_k)$. For each $i$, form the column $$L_i(X)=\begin{pmatrix}T_i^{\mathsf T}X_1\\ \vdots\\T_i^{\mathsf T}X_k\end{pmatrix} \in K^{kn}.$$ Let $\rho(J)$ be the rank of columns indexed by $J$. We claim $$|J|\le p\rho(J),\qquad p=\lceil n/k\rceil. \tag{4}$$ To see this, stack evaluations at $p$ disjoint batches of $k$ fresh formal vectors, in one common extension field. Each batch has rank $\rho(J)$. All $pk\ge n$ vectors together span the input space: any chosen $n$ of these generic vectors have formally nonzero determinant. Consequently a matrix annihilating them is zero. The $T_i$, $i\in J$, remain linearly independent over the extension field, so the total stacked rank is $|J|$, proving (4).

Edmonds’s matroid partition theorem, Theorem 1 partitions the coordinates into at most $p$ independent groups $B_j$. A group of size $s_j$ has an $s_j$-row square minor with formally nonzero determinant of degree at most $s_j$.

For such a minor, determinant multiplicity at a binary input is at least its rank deficiency. Translating to that input and making constant row operations leaves each vanished row with only positive-degree entries. Every determinant term therefore has at least that many positive-degree factors. The binary-grid multiplicity bound of Dvir, Kopparty, Saraf and Sudan, Lemma 2.7 says that the expected multiplicity of a nonzero polynomial of degree at most $s_j$ is at most $s_j/2$. Hence the full group’s expected rank is at least $s_j/2$. This uses Hasse multiplicity over $\mathbb F_2$; it does not assume that the determinant is nonzero somewhere on the binary grid. Summing over the groups gives $$M:=\mathbb E_U\sum_j\operatorname{rank}L_{B_j}(U) \ge \frac12\sum_j s_j=\frac{n^2}{2}, \tag{5}$$ where $U=(u_1,\ldots,u_k)$.

4. Entropy forces error in the sum

Choose a nearest codeword $Z(U,V)\in C$, with fixed tie breaking, and let $e=Y+Z$. For fixed $U$, choose a maximal independent set of columns $K_j(U)\subseteq B_j$, so $|K_j(U)|=\operatorname{rank}L_{B_j}(U)$. The choice depends only on $U$. As the independent uniform tuple $V=(v_1,\ldots,v_k)$ varies, the corresponding bits of $Y$ are independent and uniform. If $p_i(U)=\Pr_V[e_i=1]$, then $$|K_j(U)|\le H(Z\mid U=u)+H(e_{K_j(U)}\mid U=u) \le r+\sum_{i\in K_j(U)}h_2(p_i(U)).$$ Here the conditional notation refers to the fixed tuple $u$. The groups are disjoint, so their total expected selected error $E_{\rm sel}$ is at most $\varepsilon_k$. Summing and applying entropy concavity only over selected coordinates gives $$M\le pr+M h_2(E_{\rm sel}/M).$$ Since $M\ge n^2/2\ge pr$, inversion yields $$\varepsilon_k\ge E_{\rm sel} \ge M h_2^{-1}(1-pr/M) \ge \frac{n^2}{2}h_2^{-1}(1-2pr/n^2). \tag{6}$$ The inverse bound also holds when $E_{\rm sel}/M>1/2$. The last expression uses monotonicity of both nonnegative factors as $M$ increases. Combining (6) with $\varepsilon_k\le k\varepsilon$ proves (1). No independence between coordinate selection and error probabilities was assumed.

5. Consequence for independently prepared fragments

The fragments are $$F_A(x,y):y=Ax,\qquad Q_{u,v}(x,y):(x=v)\land(u^{\mathsf T}y=1).$$ Their compatibility is the bit $u^{\mathsf T}Av$. There are $b=2n$ boundary variables. The existing fixed-shape 3CNF realization has $3n^2+3n-1$ distinct variables and $20n^2+9n-11$ literal occurrences, using disjoint private auxiliaries. Actual binary variable-name encoding gives $N=\Theta(n^2\log n)$; coefficient input size is $N_0=n^2+2n+O(\log n)$.

Before the query, store $E\operatorname{vec}(A)$, where $E$ is any public full-column-rank $(n^2+n)$-by-$n^2$ binary matrix fixed per size. The $S=n^2+n$ encoded bits are the entire matrix-dependent initial state. Addresses and layout are public and fixed. There is no additional raw copy, input-dependent metadata, pointer identity, root choice or prior-query cache. A supplied dense encoding takes $O(Sn^2)$ Boolean operations to prepare. Query-only preparation is independent and free.

A deterministic query algorithm must be exact for every $A,u,v$. It may adaptively read the immutable old bits, with arbitrary free local computation and allocation. Every old-bit observation is charged through the final Boolean answer, including deferred work after creating a composition handle. Repeated reads do not reveal additional information but still cost reads.

Choose $n^2$ independent rows of $E$, giving stored basis bits $w$. The remaining $n$ bits are $Hw$. If the basis matrix is $R^{\mathsf T}$, the query coefficients in these coordinates are $R^{-1}\operatorname{vec}(uv^{\mathsf T})$; they form a basis of bilinear forms. The advice code $C=\operatorname{im}H^{\mathsf T}$ has dimension at most $n$. This is an analysis of the given encoding, not a claim that arbitrary changes of storage coordinates preserve probe costs.

The established support characterization says every correct path, on each individual matrix, costs at least $\tau_E(q)=\min_{E^{\mathsf T}a=q}\operatorname{wt}(a)$. Granting the advice free only weakens that bound and gives $$T(A,u,v)\ge\tau_E(\operatorname{vec}(uv^{\mathsf T})) \ge d_C(R^{-1}\operatorname{vec}(uv^{\mathsf T})).$$ Thus (2) holds for the mean read cost on every $A$, for every allowed encoding and universally correct algorithm. Some query is hard on every $A$; it may be chosen using $E$, independently of $A$.

For an upper bound store entries directly, pad with $n$ zero bits, and read exactly those entries with $u_i v_j=1$. Preparation costs $O(n^2)$; mean reads are exactly $n^2/4$, and worst-case reads at most $n^2$. Consequently optimal mean and worst-case orders are both $$\boxed{\Theta(n^2)=\Theta(b^2)=\Theta(N/\log N)=\Theta(N_0).}$$ This upper bound witnesses the order only. The stronger previously established covering-code upper bounds for worst-case queries remain valid and are not superseded by this simpler construction.

An observation returning at most $w$ encoded bits yields the corresponding conditional lower bound divided by $w$. Applying it to a machine requires its entire initialization and observation interface to satisfy this contract. No unrestricted Turing-machine, scaffolding-automaton, SAT, or P versus NP conclusion follows. The sum of queries used in the proof creates no new input requirement, storage, or preprocessing allowance.

6. Provenance and remaining question

The ingredients are classical: Edmonds’s partition theorem, the DKSS multiplicity bound, entropy, Hamming subadditivity, and the existing exact support characterization. The additional argument here combines independent query sums with the grouped-rank bound, allowing arbitrary linear advice of dimension $n$. The earlier systematic-storage result of Ramamoorthy and Rashtchian assumes raw input storage plus linear advice; that statement alone does not cover arbitrary matrix coordinates. Historical novelty of the present combination has not been established. The proof is written rather than formally verified; it does not rely on finite experiments.

The quadratic-order question for $S=n^2+n$ linear storage is settled here. The quantitative continuation asks whether its optimal mean cost is still $(1/4-o(1))n^2$, as proved earlier for advice dimension $o(n)$, or whether $n$ independent parities can save a fixed positive fraction of that mean. Equation (2) leaves this constant gap. The claim of a sharp $1/4$ leading constant for this larger class is a conjecture, not a consequence of the four-query proof. The uniform external-repair assertion for rank-deficient bilinear maps also remains unproved and is not needed for this result.

Subsequent quantitative update, 3 October 2026. The row-parity construction improves the charged mean upper bound to $n^2/4-n^{3/2}/(2\sqrt{2\pi})+n/4+O(\sqrt n)$. It preserves the quadratic order proved here. A finite counterexample rules out exact full-row optimality in systematic free-advice distance; it does not settle the asymptotic leading constant for arbitrary encodings.