Removing redundant advice without losing the read bound

Working research note, 2 October 2026.

Overview

Suppose a matrix $A$ is stored before the vectors $u,v$ are known, and a later query asks for $u^{\mathsf T}Av$. The representation keeps transformed matrix bits together with a short list of parity checks. Different lists can carry the same information: for example, listing checks $p,q,p+q$ supplies the same parity subspace as listing only $p,q$. A lower bound should depend on that subspace, not on how redundantly the checks are written down.

The preceding coupled-block bound did not directly survive every such change of presentation. Two separately expanding groups could cancel, creating more invisible directions than the block description allowed. Here the argument works directly with the subspace of parities supplied by the advice, so duplicated or recombined rows no longer matter. This resolves the earlier cancellation example.

The method has a sharp limit. A classical simplex code shows that correcting every direction in the subspace can cost a factor of order $\log n$. A second bound therefore corrects the short directions and uses distance for the long ones. This narrows the remaining structural question but does not settle the general quadratic conjecture, and novelty has not been established.

1. Model and a certificate on the advice subspace

All vector spaces are over $\mathbb F_2$. The independently prepared fragments are $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$, with $A\in\mathbb F_2^{n\times n}$. Compatibility is $u^{\mathsf T}Av$. Put $d=n^2$. Store exactly

$$w=R^{\mathsf T}\operatorname{vec}(A),\quad Hw, \qquad R\in\mathrm{GL}(d,2),\quad H\in\mathbb F_2^{n\times d}.$$

The encoding and addresses are public and fixed independently of the inputs. These $S=d+n$ bits are all matrix-dependent initial information; there is no other copy, metadata, cache or input-dependent address channel. Storage is immutable. The algorithm is deterministic, exact on every input, and may read adaptively. Local computation and allocation, and preparation using only $u,v$, are free. Reads are charged through the final answer, including any deferred work.

As before, retain $J\subseteq[d]$, $g=|J|=d-h$, and supply the other $h$ independent bits and all advice free. Let

$$U=\operatorname{im}(H_{*,J}^{\mathsf T})\subseteq\mathbb F_2^g, \qquad r=\dim U\le n.$$

This subspace, with its inherited Hamming weight, is unchanged by invertible row operations on $H$, or removal of redundant advice rows.

A linear decomposition of $U$ is a finite list $(a_i,\ell_i)$, with $a_i\in U$ and linear $\ell_i:U\to\mathbb F_2$, satisfying

$$z=\sum_i a_i\ell_i(z)\quad(z\in U).$$

Its cost on $z$ is $C(z)=\sum_i\operatorname{wt}(a_i)\ell_i(z)$, an ordinary nonnegative integer, whereas reconstruction uses binary sums. The triangle inequality gives $\operatorname{wt}(z)\le C(z)$. Bases give examples, but redundant lists are allowed.

Our certificate is a public finite probability distribution $\mathcal D$ over such decompositions, with

$$\mathbb E_{D\sim\mathcal D}C_D(z)\le K\operatorname{wt}(z) \quad\text{for every }z\in U. \tag{1}$$

This randomness is only an averaging device in the proof, not randomized query correctness or random preprocessing. The certificate is checkable from finite matrices and probabilities, by enumeration if necessary. No efficient search, polynomial certificate size, or efficient local query computation is asserted. The atoms must belong to $U$: allowing ambient unit vectors would make (1) trivial but destroy the rank argument below.

2. A bound independent of redundant advice rows

Theorem. If (1) holds, every exact algorithm in the stated model satisfies, for each fixed $A$ and every invertible $R$,

$$\boxed{\displaystyle \mathbb E_{u,v}\operatorname{reads}(A,u,v) \ge\frac{g-r}{4(1+1332K)}.} \tag{2}$$

The query vectors are independent and uniform, including zero. Only retained reads are counted. Thus bounded $K$ and $g=\Omega(n^2)$ give quadratic mean work, matching the order of reading all independent coordinates.

Proof. Write $q'=\pi_JR^{-1}\operatorname{vec}(uv^{\mathsf T})$. The exact support argument from the preceding note gives

$$\tau(u,v)=\min_{z\in U}\operatorname{wt}(q'+z).$$

Every adaptive transcript, for every stored $A$, requires at least $\tau(u,v)$ retained reads. Otherwise an unobserved change of the matrix preserves its transcript and free information but flips its answer. Choose minimizing residuals $b=q'+z$, without assuming linearity of these choices, and set $t=\mathbb E\operatorname{wt}(b)$.

In either separate additive test, $\delta z=\delta b\in U$, since $q'$ is bilinear. Each of the three residuals has the same marginal distribution, so $\mathbb E\operatorname{wt}(\delta z)\le3t$. For a fixed decomposition, apply the existing scalar bilinear-correction lemma to $f_i=\ell_i(z(u,v))$. It gives a bilinear $B_i$ with error at most $222(\varepsilon_{1,i}+\varepsilon_{2,i})$. Averaging its weighted error over decompositions and using (1) gives

$$\mathbb E_D\sum_i\operatorname{wt}(a_i)\Pr[f_i\ne B_i] \le222\sum_{j=1}^2\mathbb E_{D,\mathrm{test}_j} C_D(\delta_j z) \le1332Kt. \tag{3}$$

Choose one decomposition no worse than this average, and put $B=\sum_i a_i B_i$. It is bilinear and valued in $U$. Consequently $\mathbb E\operatorname{wt}(z+B)\le1332Kt$. The bilinear map $L=q'+B$, extended linearly to matrix space, has rank at least $g-r$: the first summand has rank $g$, while the second has image in $U$. At least $g-r$ output coordinates are nonzero bilinear forms. Each is one on at least a quarter of uniform query pairs. Hence

$$(g-r)/4\le\mathbb E\operatorname{wt}(L) \le t+1332Kt.$$

This proves (2). The correction lemma is the classical homomorphism-testing ingredient, with constants and proof in the preceding expansion note.

3. Recovering the block result and resolving its cancellation example

In the block theorem, $z=H_0^{\mathsf T}x$ determines $x$ modulo a constant on each block. Choose a reference coordinate uniformly in each block. Use row $i$ of $H_0$ as atom, and the well-defined linear functional $x_i+x_{\mathrm{ref}}$ as its coefficient. The even-column condition guarantees reconstruction. A block containing $s$ ones has expected number of nonzero coefficients $2s(m-s)/m\le2\min(s,m-s)$. The weighted expansion and row-degree assumptions therefore give (1) with $K\le2\kappa$. Equation (2) recovers the previous constant $2664\kappa$.

Now consider the example $H=[G;G]$, where $n=2m$ and $G$ is the incidence matrix of the complete graph on $m$ vertices, with edges repeated as evenly as possible to give $d=4m^2$ columns. The advice subspace is simply $U=\operatorname{im}G^{\mathsf T}$, of dimension $m-1$. The previous estimates give cut weight at least $4m\min(s,m-s)$ and maximum row weight at most $9m$. Uniform reference choice on this single graph gives $K\le2(9m)/(4m)=9/2$. Thus, under every matrix coordinate choice,

$$\mathbb E\operatorname{reads}\ge \frac{n^2-m+1}{4(1+5994)}.$$

The larger invisible-message kernel causes no difficulty here. Duplicating the list of graph parities does not change its span. This is a positive resolution of the saved example, not a claim that every kernel has bounded correction cost.

4. A sharp obstruction to constant-cost linear decomposition

Let $U_r$ be the classical binary simplex code

$$U_r=\{(x\cdot a)_{a\in\mathbb F_2^r\setminus\{0\}}: x\in\mathbb F_2^r\}.$$

Every nonzero word has weight $\Delta=2^{r-1}$: a nonzero linear functional is one on exactly half of $\mathbb F_2^r$, and the omitted zero vector contributes nothing.

Proposition. The smallest possible constant in (1), allowing arbitrary finite distributions and redundant linear decompositions, is exactly

$$K(U_r)=\frac{r}{2(1-2^{-r})}. \tag{4}$$

For any decomposition, discard terms with zero atom or zero functional. The identity on the $r$-dimensional space is a sum of the remaining rank-one maps, so at least $r$ terms remain. On uniform $z\in U_r$, each nonzero coefficient is one half the time and each atom weighs $\Delta$. Thus mean cost is at least $r\Delta/2$, whereas mean word weight is $\Delta(1-2^{-r})$. Averaging over decompositions preserves this lower bound. Conversely, choose a uniformly random ordered basis of $U_r$. For each fixed nonzero $z$, its coefficient vector is uniform among nonzero binary $r$-vectors, of mean weight $r/[2(1-2^{-r})]$. This achieves (4).

The obstruction fits our storage budget: take $n=2^s$, $s\ge2$, $r=2s\le n$. The simplex length is $n^2-1$; append one zero coordinate and pad its generator with zero rows to make $H$ an $n$-by-$n^2$ matrix. The required constant grows like $\log_2 n$. Padding advice does not supply new information. Thus even averaging over all linear choices of coordinates cannot provide a uniform constant in this certificate.

This is a limitation on this sufficient condition. It is neither a subquadratic query construction nor an obstruction to nonlinear correction. In fact the next result proves quadratic worst-case reads for this example.

5. Combine correction on short directions with distance outside them

Let $W\subseteq U$ have a certificate (1) with constant $K$, using atoms and functionals on $W$. Put

$$\delta=\min\{\operatorname{wt}(z):z\in U\setminus W\}, \quad\delta=+\infty\text{ if }W=U.$$

Let $T=\max_{u,v}\tau(u,v)$. Then

$$\boxed{\displaystyle T\ge\min\left\{\frac\delta3, \frac{g-r}{4(1+1332K)}\right\}.} \tag{5}$$

Every exact algorithm has worst-case retained reads at least $T$. Unlike (2), (5) alone is a worst-case conclusion.

If $3T\ge\delta$ there is nothing to prove. Otherwise choose the same minimum residuals $b$ and $z=q'+b$. Every additive defect has weight at most $3T<\delta$, so $\delta z=\delta b$ belongs to $W$. The function $z\bmod W$ is therefore bilinear. Lift it by any linear section $U/W\to U$ to a bilinear $B_0$. Then $z+B_0$ is valued in $W$, and its additive defects are still $\delta b$. Apply the proof of (3) on $W$, obtaining bilinear $B_1$ valued in $W$. The final $q'+B_0+B_1$ still loses at most $r$ in rank. This gives $t\ge(g-r)/[4(1+1332K)]$, and $T\ge t$ proves (5). No weight bound on $B_0$ is needed: its cost is paid in rank, not by coordinatewise correction. The conditional average conclusion in this branch does not imply an unconditional average bound when $W\ne U$.

For $W=0$, use the empty decomposition and $K=0$. The simplex example then has $g=d$, $\delta=d/2$, and $T\ge\min\{d/6,(d-r)/4\}=d/6$ for the parameters above. This recovers the order already obtainable by the earlier distance method. For $W=U$, (5) reduces to the correction bound. A natural checkable choice is the span of all words in $U$ of weight below a specified threshold; words outside that span have at least the threshold weight. Whether its correction constant is small remains a separate obligation.

Scope and next question

The classical ingredients are binary linear algebra, the simplex code, the exact adaptive support argument, and homomorphism correction. For correction provenance see Blum, Luby and Rubinfeld, including their credit to Coppersmith. The simplex family also appears in Ma and Luo, Section 4; our elementary Hamming-weight calculation is given above, and uses none of their symbol-pair results. The additional arguments here are the subspace certificate, its exact simplex limitation, and the combined distance/correction bound. Novelty is unestablished, and there is no proof-assistant verification.

Resources remain $b=2n$, $N_0=\Theta(n^2)$ coefficient bits, $N=\Theta(n^2\log n)$ for the existing explicit named 3CNF encoding, and $S=n^2+n$ stored bits. Dense per-matrix preprocessing costs $O(Sn^2)$ binary operations. Certificate construction can be exponential; it is a proof hypothesis, not a charged algorithm provided to the combiner. Public $R,H$ have polynomial descriptions. No unrestricted SAT or machine lower bound follows without an access-preserving simulation.

The next question is now specific: can a short-word subspace $W$ have a controlled decomposition cost while the remaining directions have large weight? A universal assertion needs proof, and (4) prevents silently setting $W=U$ with a constant. A decisive next test should involve interacting short and long directions, rather than another direct sum whose costs simply separate. The general quadratic conjecture remains unresolved.

The finite checker and recorded output enumerate all ordered bases of simplex spaces of dimensions one through four, and all messages and reference choices for one repeated four-vertex graph. They corroborate those finite certificates only, not the general query bounds or their proofs.