Repair whole vectors: a quadratic bound beyond linear decomposition

Working research note, 2 October 2026.

Overview

Suppose a matrix $A$ is stored before the query vectors $u,v$ are known, and a later query asks for $u^{\mathsf T}Av$. The representation may add only $n$ parity checks to $n^2$ transformed matrix bits. The preceding method expressed an advice word as separately charged linear pieces, then corrected the coefficient of each piece. That can be wasteful when the pieces carry strongly correlated information.

The family constructed here makes the loss exact. It is connected and has full-rank advice, yet the best certificate from the preceding method gives only $\Theta(n^2/\log n)$, even after optimizing which coordinates and short directions it uses. The limitation belongs to that proof certificate, not to the query problem itself.

Repairing each correlated block as one vector-valued function retains the information discarded by a coordinate-by-coordinate decomposition. On the same family it proves $\Theta(n^2)$ average read cost for every stored matrix and every invertible matrix-coordinate choice. Thus the new argument recovers the missing logarithmic factor and separates the power of the two methods.

This remains a sufficient-condition result in the existing exact bit-read model. It does not give a subquadratic algorithm or settle the general quadratic conjecture, and novelty has not been established.

1. Model and the stronger sufficient condition

Work over $\mathbb F_2$. Compatibility of the independently prepared fragments $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$ is $u^{\mathsf T}Av$. Put $d=n^2$, and store

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

The $S=d+n$ bits are all matrix-dependent initial information. The encoding, addresses and algorithm are public and fixed. There is no hidden copy, metadata or prior-query cache. Storage is immutable. Algorithms are deterministic, adaptive and exact for every input; local computation, allocation and query-only preparation are free. Charge reads through the final answer, including deferred work.

Retain coordinates $J$, $g=|J|$, supplying all advice and the other independent bits free. Let $U=\operatorname{im}H_{*,J}^{\mathsf T}$. Partition $J$ into disjoint blocks. Suppose the projection of $U$ to block $j$ lies in a nonzero binary linear code $C_j$, whose minimum nonzero weight is $\lambda_j$ and maximum weight is $D_j$. Set

$$a=\max_j D_j/\lambda_j,\qquad q=\sum_j\dim C_j.$$

Zero-code blocks can be included separately with no correction or rank cost. If every projected code is zero, take the correction to be zero directly; the mean bound is then $g/4$, without defining an empty maximum. The hypotheses can be checked from the finite public matrices by enumeration; no efficient search or certification algorithm is claimed.

Theorem. For every such encoding, every invertible $R$, and every exact algorithm, for each fixed stored matrix $A$,

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

The query vectors are independent and uniform, including zero. Only retained reads are counted. A positive bound requires $q<g$; refining into individual coordinates can make the bound vacuous. Bounded aspect ratio $a$ and $g-q=\Omega(n^2)$ give quadratic mean and worst-case work. The codes form a containing product, not necessarily the exact advice space: correction may leave $U$, but stays in a space of dimension at most $q$.

Why vector repair has no output-dimension factor

For a function $f:V\times W\to C$ into any finite binary vector space, let $\varepsilon_1,\varepsilon_2$ be its separate additive-test failure probabilities. There is a bilinear $B$, valued in $C$, with

$$\Pr[f\ne B]\le222(\varepsilon_1+\varepsilon_2). \tag{2}$$

Use the classical group-valued repair bound $6\eta$, proved in the expansion note, on each first-variable slice. The repaired $f_1(u,v)=\ell_v(u)$ differs with probability $e\le6\varepsilon_1$. Its second-variable test fails with probability at most $\varepsilon_2+3e$. A nonzero linear map $V\to C$ is nonzero on at least half of $V$, since its kernel has codimension at least one. Thus $v\mapsto\ell_v$, valued in $\operatorname{Hom}(V,C)$, fails its additive test with probability at most $2\varepsilon_2+6e$. Repair this coefficient map and evaluate it. The final error is at most $e+6(2\varepsilon_2+6e)\le222(\varepsilon_1+\varepsilon_2)$. This is the same classical argument as for scalar output; the repair is not assumed to be a fixed linear decomposition of the original values.

Proof of the read bound

Put $p=\pi_JR^{-1}\operatorname{vec}(uv^{\mathsf T})$. Choose minimum residuals $b=p+z$, $z\in U$, and write $t_j=\mathbb E\operatorname{wt}(b_j)$, $t=\sum_jt_j$. The existing exact support argument lower-bounds every transcript, for every $A$, by $\operatorname{wt}(b)$.

Since $p$ is bilinear, $\delta z_j=\delta b_j$. Each additive test has expected defect weight at most $3t_j$. Every nonzero defect in $C_j$ weighs at least $\lambda_j$, so the sum of its two test failure probabilities is at most $6t_j/\lambda_j$. Apply (2) inside $C_j$. For the resulting bilinear $B_j$,

$$\mathbb E\operatorname{wt}(z_j+B_j) \le D_j\Pr[z_j\ne B_j] \le1332(D_j/\lambda_j)t_j.$$

The direct sum $B$ lies in $\bigoplus_jC_j$, of dimension $q$. Consequently the linear extension of $p+B$ to matrix space has rank at least $g-q$. Each nonzero bilinear output coordinate is one on at least one quarter of uniform query pairs. Therefore

$$(g-q)/4\le\mathbb E\operatorname{wt}(p+B) \le(1+1332a)t,$$

which proves (1). Average costs were summed before correction; there is no factor for the number or dimension of the blocks.

2. One family separates the two methods

Let $r\ge64$ be a power of two, $n=2^r$, $M=n/r$, and $d=n^2$. Divide the $n$ advice-message coordinates into $M$ blocks of size $r$. In each block include every nonzero vector of $\mathbb F_2^r$ as a column, repeated $r$ times. These core columns number

$$M r(n-1)=d-n.$$

Add the $n$ bridge columns $e_{j,t}+e_{j+1,t}$, for every block $j$ cyclically and every $t\in[r]$. This gives an $n$-by-$d$ matrix $H$. It has full row rank, because the core columns include every unit vector. Its support hypergraph is connected: columns within each core connect its rows, and the bridges connect successive cores. Hence row and column permutations cannot split it into nontrivial disjoint blocks. We do not claim irreducibility under arbitrary linear coordinate changes.

Every nonzero message in a core produces weight $\Delta=rn/2$, by the simplex-code calculation. Each generator row of $H$ has weight $\Delta+2$.

Give the $n$ bridge coordinates free and retain all cores. Their advice space is the direct sum of $M$ repeated simplex codes, each of dimension $r$ and aspect ratio one. Thus $g=d-n$, $q=n$, and (1) gives

$$\boxed{\displaystyle \mathbb E_{u,v}\operatorname{reads}(A,u,v) \ge\frac{n^2-2n}{5332}} \tag{3}$$

for every $A,R$. Reading all $d$ independent coordinates supplies a matching upper bound in asymptotic order. Bridges do not need to be charged for the lower bound. This is a connected storage family whose hard core is exposed by granting the bridges free, not a claim about arbitrary dense interactions.

3. Even the optimized previous certificate loses a logarithm

For clarity, write $\rho=\dim U_J$, where $U_J=\operatorname{im}H_{*,J}^{\mathsf T}$. For any retained set $J$, any $W\subseteq U_J$, and any valid averaged linear-decomposition constant $K$ on $W$, the previous theorem certifies the numerical bound

$$B(J,W,K)=\min\left\{\frac{\delta(U_J\setminus W)}3, \frac{|J|-\rho}{4(1+1332K)}\right\}. \tag{4}$$

The distance is infinity if $W=U_J$. This number is a lower-bound certificate, not an access algorithm’s cost.

Proposition. For the family above, the supremum of (4) over all these choices is $\Theta(d/r)=\Theta(n^2/\log_2n)$.

Upper bound, including every choice of retained coordinates

If $W$ is proper, some projected generator row lies outside $W$, since the rows span $U_J$. Its weight is at most $rn/2+2$, so $B\le rn/6+2/3\le d/r$ for our parameters.

Suppose $W=U_J$, and put $g=|J|$. If $g<36d/r$, the numerator alone gives $B<9d/r$. Otherwise call a core heavy if it retains at least $16n$ coordinates. Light cores retain fewer than $16d/r$ in total, and there are at most $n\le d/r$ bridge coordinates. Heavy cores therefore retain total mass $m_*\ge g-17d/r\ge g/2$.

Consider one heavy core with $m$ retained coordinates. Each nonzero column type $a\in\mathbb F_2^r$ has multiplicity $0\le k_a\le r$. Let $C x$ be the retained encoding of message $x$, and set

$$F(x)=\sum_a k_a(-1)^{x\cdot a}=m-2\operatorname{wt}(Cx).$$

Character orthogonality, or Parseval’s identity, gives

$$\sum_x F(x)^2=n\sum_a k_a^2\le nr m.$$

There are thus at most $4nr/m\le r/4$ messages with $\operatorname{wt}(Cx)<m/4$. Let $L$ be this set. It contains $\ker C$, and $\dim\operatorname{span}L\le r/4$. Hence

$$\operatorname{codim}_{\operatorname{im}C} \operatorname{span}(CL) =r-\dim\operatorname{span}L\ge3r/4. \tag{5}$$

Now take any linear decomposition of $U_J$, discarding terms with zero atom or zero functional. Its atoms span $U_J$, and their projections onto this core span $\operatorname{im}C$. By (5), at least $3r/4$ atoms have projected weight at least $m/4$. Thus their total projected weight is at least $3rm/16$. Sum this over the disjoint heavy cores. On a uniform word of $U_J$, each nonzero linear coefficient is one half the time. Expected decomposition cost is at least $3r m_*/32$, whereas expected word weight is at most $g/2$. Every averaged decomposition certificate must therefore have

$$K\ge\frac{3r m_*}{16g}\ge\frac{3r}{32}.$$

This argument applies to every decomposition before averaging, so random choices and redundant lists cannot evade it. Substituting into (4) gives $B<d/r$. Together, all cases give $B\le9d/r$.

Matching certificate

Take all coordinates and $W=U$. Use the original generator rows as basis atoms. If a message has $s$ nonzero blocks, its codeword weighs at least $s\Delta$, while the decomposition costs at most $sr(\Delta+2)$. Thus $K\le r(1+2/\Delta)\le2r$, and (4) gives

$$B\ge\frac{d-n}{4(1+2664r)}=\Omega(d/r).$$

This proves the claimed sharp order for the optimized certificate. It limits a single application of (4), including arbitrary puncturing, subspaces, and averaged linear decompositions. It does not limit recursive arguments, vector-valued correction, or query algorithms. Equation (3) demonstrates a strictly stronger lower bound on the very same family.

Dependencies, scope and next question

Group-valued homomorphism repair is classical Blum–Luby–Rubinfeld, with the simplified analysis credited there to Coppersmith. The vector-valued bilinear estimate is its direct two-stage consequence, proved above; no new general stability theorem is claimed. Parseval is standard character orthogonality, as developed in O’Donnell, Chapter 1. The simplex family and rank argument are also established ingredients. The additional content is the resource application, the explicit family, and the sharp separation between these two sufficient-condition methods. Novelty is unestablished, and there is no proof-assistant verification.

Boundary width is $b=2n$; input size is $\Theta(n^2)$ coefficient bits or $N=\Theta(n^2\log n)$ in the existing explicit named 3CNF encoding, including auxiliary variables. Storage is $S=n^2+n$. Public $H$ and $R$ have polynomial descriptions, and dense per-matrix preprocessing uses $O(Sn^2)$ binary operations. The family is explicit along an infinite sequence of $n$; small numerical instances are not claimed to establish its asymptotic bounds. No unrestricted SAT, Turing-machine or scaffold lower bound follows without the required access-preserving simulation.

The next structural question is whether advice can be covered by codes on disjoint retained coordinate blocks with bounded weight ratios and total containing dimension well below the number of retained coordinates. The rank budget $q$, not just distance or block size, must be controlled. Dense cross-block correlations may make $q$ too large. A counterexample to a proposed universal covering condition would narrow this route without refuting the quadratic query conjecture. The finite checker and recorded output check character identities for all multiplicity patterns in one small case and the construction for $n=16,r=4$. That construction is below the parameter range of the asymptotic method-separation theorem. These checks do not verify general repair, adaptive query bounds, or the unbounded proofs.