External repair reduces to deleting coefficient rows

Working research note, 2 October 2026.

Overview

We are trying to understand how much work remains when two constraint fragments have been prepared independently. In the current family, answering the compatibility question means computing $u^{\mathsf T}Av$ from $n^2+n$ stored linear bits about the matrix $A$.

The preceding note ruled out a proposed correction theorem that kept every corrected value inside the advice space. Allowing correction outside that space avoids the counterexample, but introduces a new requirement: the corrected bilinear map must have small rank.

Each output bit is a parity of basic products $u_i v_j$. Its coefficient row records which products occur in that parity. Here we show that, up to constant factors, searching over all low-rank bilinear corrections is the same as asking how many whole output bits must be discarded before the remaining rows have low rank. The minimum deletion count is a classical generalized Hamming weight. This is a concrete equivalent question, not a new access lower bound.

For example, the map $G(u,v)=(u_1v_1,u_1v_2)$ has two independent coefficient rows. One row must be deleted to reduce its rank to one. Keeping the first coordinate and zeroing the second incurs mean error $1/4$, since $u_1v_2=1$ on one quarter of uniform input pairs. No rank-one bilinear approximation has smaller mean error. The argument below extends this observation to every bilinear map.

1. The finite optimization problem

All vector spaces and ranks are over $\mathbb F_2$. Let $G:\mathbb F_2^n\times\mathbb F_2^n\to\mathbb F_2^d$ be bilinear. Its coefficient matrix $M_G$ has $d$ rows and $n^2$ columns; row $i$ contains the coefficients of the scalar form $G_i$. Equivalently, it represents the linear extension $\widehat G$ from matrix space to $\mathbb F_2^d$. Its rank is not tensor rank.

For an integer $q\ge0$, define $$A_q(G)=\min_{Q\text{ bilinear},\ \operatorname{rank}\widehat Q\le q} \mathbb E_{u,v}\operatorname{wt}(G(u,v)+Q(u,v)),$$ and $$D_q(G)=\min\{|J|: \operatorname{rank}(M_G\text{ with rows }J\text{ removed})\le q\}.$$ Expectations are uniform over independent inputs, including zero, and Hamming weight is unnormalized. All minima are over finite sets. No efficient optimization algorithm is asserted.

Lemma (bilinear approximation and row deletion). For every such $n,d,G,q$, $$\boxed{D_q(G)/4\ \le A_q(G)\ \le D_q(G)/2.} \tag{1}$$

A nonzero scalar bilinear form $u^{\mathsf T}Tv$, with $\operatorname{rank}T=t\ge1$, is one with probability $$\frac{1-2^{-t}}2\in[1/4,1/2).$$ Indeed, $Tv=0$ with probability $2^{-t}$; otherwise its inner product with uniform $u$ is balanced.

For any admissible $Q$, let $J$ contain the output coordinates where $G_i\ne Q_i$ as functions. Outside $J$, their coefficient rows agree, so the remaining rows of $G$ have rank at most $q$. Each changed coordinate contributes at least $1/4$ to mean error. Thus $D_q(G)\le |J|\le4\mathbb E\operatorname{wt}(G+Q)$. Conversely, delete an optimal set $J$ and obtain $Q$ by setting exactly those output functions to zero. Its rank is at most $q$, and its mean error is at most $|J|/2$. This proves (1).

In particular, arbitrary bilinear modifications cannot improve the order of cost over simply erasing entire output functions. This statement concerns approximation of bilinear maps, not erasing stored bits in an algorithm.

The classical code parameter

Put $W=\operatorname{im}\widehat G$ and $\rho=\dim W$. For a linear code $W$, its $j$-th generalized Hamming weight is $$d_j(W)=\min_{V\le W,\ \dim V=j}|\operatorname{supp}V|.$$ Then $$D_q(G)= \begin{cases} 0,&\rho\le q,\\ d_{\rho-q}(W),&\rho>q. \end{cases} \tag{2}$$ To see this, deleting $J$ leaves rank at most $q$ exactly when projection of $W$ outside $J$ has a kernel of dimension at least $\rho-q$. That kernel consists of codewords supported on $J$. Taking a subspace of exactly the required dimension proves both directions. This is the standard support definition and rank-nullity, not a new code invariant. Notice that it is a weight of $W$, not of the advice code.

2. Equivalent forms of the remaining repair question

Return to the prescribed family $$n=2^{5k},\quad d=n^2,\quad U=\mathrm{RM}(k,10k),\quad r=\dim U<n,\quad k\ge1.$$ For $f:\mathbb F_2^n\times\mathbb F_2^n\to U$, let $\mathcal E(f)$ be the sum of mean Hamming weights of its two separate additive defects, as defined in the preceding note. For ambient bilinear $G$, put $$\varepsilon_U(G)=\mathbb E_{u,v}\min_{z\in U} \operatorname{wt}(G(u,v)+z).$$ Fix a constant $c\ge1$ and set $q=\lfloor cr\rfloor$. The following uniform assertions are equivalent in existence of absolute constants, with the same $c$:

1. External repair: every $k,f$ admits bilinear $Q$ of rank at most $q$, with mean error at most $K\mathcal E(f)$.
2. Static approximation: every $k,G$ satisfies $A_q(G)\le C\varepsilon_U(G)$.
3. Rank deletion: every $k,G$ satisfies $D_q(G)\le L\varepsilon_U(G)$.

All constants are independent of $k,f,G$. None of these three uniform assertions is proved here. What is proved is their equivalence: $$1\Rightarrow2:\ C=1+6K;\qquad 2\Rightarrow3:\ L=4C;\qquad 3\Rightarrow1:\ K=222(1+L/2). \tag{3}$$

For the first implication choose a nearest-codeword selector $f$ for $G$, resolving ties in a fixed order. The residual $e=G+f$ has mean weight $\varepsilon_U(G)$. Bilinearity gives $\delta_i f=\delta_i e$. Each of the two defects has three summands with the same mean weight, so $\mathcal E(f)\le6\varepsilon_U(G)$. Apply external repair and the triangle inequality. The second implication is (1).

For the last implication, the established coordinatewise bilinear correction bound gives an ambient bilinear $G$ with $$\mathbb E\operatorname{wt}(f+G)\le222\mathcal E(f).$$ This follows by applying the scalar version of the whole-vector correction argument separately and summing; no rank bound is supplied by that argument. Because $f$ takes values in $U$, $\varepsilon_U(G)\le222\mathcal E(f)$. Rank deletion and (1) provide $Q$ with error from $G$ at most $L\varepsilon_U(G)/2$. The triangle inequality proves the last constant in (3).

This reduction removes arbitrary nonlinear functions from the statement to be proved. The remaining finite input is the coefficient matrix $M_G$; its mean distance is evaluated on rank-one inputs $uv^{\mathsf T}$. That distribution cannot be replaced by uniform matrix inputs. The left side $D_q$ depends only on the image space $W$; the right side $\varepsilon_U$ also depends on the parameterization of that space. For a small illustration, take $n=2,d=4,U=\langle e_1\rangle$. The four coefficient rows encoded as binary integers $(1,2,4,8)$ and $(1,9,6,11)$ both form bases. Their mean distances to $U$ are $3/4$ and $9/8$, respectively: after the first coordinate is ignored, the first map has three rank-one scalar forms, the second three rank-two forms. This illustrates the distribution issue; it is not an instance of the prescribed asymptotic RM family.

3. Consequences and limitations for composition

For an invertible query map $P_R(u,v)=R^{-1}\operatorname{vec}(uv^{\mathsf T})$, its image space is all of $\mathbb F_2^d$. Therefore $$D_q(P_R)=(d-q)_+.$$ The rank-deletion conjecture would give $$\varepsilon_U(P_R)\ge(d-q)_+/L. \tag{4}$$ For fixed $c$, this is quadratic in $n$. In fact, restricted to these full-rank maps alone, the deletion criterion is equivalent asymptotically to the desired uniform quadratic mean-distance bound. It is not a shortcut that establishes that bound. The all-$G$ formulation additionally controls rank-deficient maps and is stronger in its quantifiers.

Here the exact support argument lower-bounds reads for every stored matrix by the distance of its query vector from $U$, even when advice is supplied free. Conversely, with free advice, choose a nearest codeword and read the residual coordinates. This attains that distance. Charging advice adds at most $n$ reads. Thus, for each fixed public encoding, optimal average cost lies between $\varepsilon_U(P_R)$ and $\varepsilon_U(P_R)+n$. This uses arbitrary free query-only computation; it does not claim efficient nearest-codeword search.

A mere rank-gap inequality is weaker than the approximation criterion: $D_q(G)\ge(\rho-q)_+$, but equality need not hold. For a one-dimensional repetition image $W=\{0,1^d\}$ and $q=0$, the rank gap is one while $D_0=d$. A proof controlling only the rank gap cannot be silently used as a proof of rank-controlled repair.

Positive controls are exact maps with image in $U$, for which both sides of the deletion criterion vanish, and the preceding rounding witness’s ambient approximant: its rank $M\le r$ makes $D_q=0$. Neither is a counterexample to the criterion. Independent coefficient rows instead force deletion of one row per unit of rank reduction.

The resource model is unchanged: independently prepared compact affine fragments, boundary width $b=2n$, coefficient input size $\Theta(n^2)$, explicit named 3CNF size $N=\Theta(n^2\log n)$, stored size $S=n^2+n$, and dense preprocessing $O(Sn^2)$ binary operations. All matrix-dependent initialization is charged and storage is immutable. The controller is deterministic, adaptive and exact; charge old bit reads through composition and deferred answer, with local computation and allocation free. No addresses, metadata, hidden copies or caches supply uncharged matrix information. This note changes no machine compiler or language-recognition theorem and implies no unrestricted SAT, TM or scaffolding-automaton lower bound.

Provenance, verification, and next question

The support parameter in (2) is due to Victor K. Wei, Generalized Hamming Weights for Linear Codes, IEEE Transactions on Information Theory 37(5), 1412–1418 (1991), Section II. The proof here needs its definition, not a formula for Reed–Muller weights. The storage/distance connection is established in Ramamoorthy–Rashtchian; their raw-coordinate results do not automatically cover all invertible coordinate changes here. The scalar repair ingredient is classical and credited in the linked correction note. Robust tensor-product testing, such as Dinur–Sudan–Wigderson, requires its own hypotheses and does not supply the missing rank-deletion inequality.

The reduction is an elementary written argument, independently reviewed. Novelty is unestablished; no new lower bound is claimed. A finite checker and its output check the approximation sandwich and support identification in small dimensions, not the uniform conjecture.

Next, test whether $D_{\lfloor cr\rfloor}(G)/\varepsilon_U(G)$ stays bounded for this RM family for some fixed $c$, interpreting $0/0$ as zero. A counterexample needs unavoidable rank after deleting few output coordinates, together with small distance on rank-one inputs. Proving only ordinary code weights, correcting separate input slices, or knowing the rank gap does not meet those two obligations. The general access bound and the family’s existing $\Omega(n^{9/5})$ bound remain unchanged.