Internal repair also needs a growing constant

Working research note, 2 October 2026.

Overview

Our composition problem asks how many stored bits must be read to answer $u^{\mathsf T}Av$, after the matrix and query have been prepared separately. One proof strategy studies the answer patterns for many queries together: if they are cheap, their failures of additivity are small. A suitable correction theorem would replace them by bilinear patterns, whose rank forces many reads.

The preceding note showed that splitting the advice into disjoint repair spaces cannot always preserve the desired bound. We now test the alternative: repair inside the original advice space, measuring both defects and repair error by Hamming weight.

A constant independent of size is impossible even for our exact Reed-Muller family. There are functions whose additive defects cost a bounded amount per repeated block, but whose distance from every internal bilinear repair grows with the polynomial degree. The proof uses a small extended Hamming code inside the larger Reed-Muller space.

The smallest instance makes the mechanism concrete. Label eight coordinates by the three-bit strings. A word’s syndrome consists of one parity bit and one three-bit label. To round the word into the code, flip the coordinate named by that label; for one parity value, also flip the coordinate named 000. Duplicate flips cancel, so at most two coordinates change. The rounding is cheap, but it does not respect addition: combining two rounded words can leave a four-coordinate defect supported at labels $a$, $b$, $a+b$, and 000. Repeating this small pattern keeps the additive defect bounded per copy while every bilinear repair constrained to remain in the full advice space accumulates a growing error.

This settles the proposed unrestricted repair principle. It does not settle the query problem: the counterexample approximates a bilinear map of low rank, whereas the matrix-query map has full rank. Any further use of repair must exploit that distinction rather than apply to arbitrary functions.

1. The precise statement being tested

Put $k\ge1$, $n=2^{5k}$, $d=n^2=2^{10k}$, and $$U=\mathrm{RM}(k,10k)\subseteq\mathbb F_2^d.$$ Coordinates of $U$ are evaluation points in $\mathbb F_2^{10k}$. Its words are truth tables of Boolean polynomials of degree at most $k$. As in the preceding note, $\dim U=r<n$.

For $f:\mathbb F_2^n\times\mathbb F_2^n\to U$, define $$\begin{aligned} \delta_1f(u,u',v)&=f(u,v)+f(u',v)+f(u+u',v),\\ \delta_2f(u,v,v')&=f(u,v)+f(u,v')+f(u,v+v'),\\ \mathcal E(f)&=\mathbb E\operatorname{wt}(\delta_1f) +\mathbb E\operatorname{wt}(\delta_2f),\\ \mathcal D(f)&=\min_{B\ {\rm bilinear},\ B(u,v)\in U} \mathbb E_{u,v}\operatorname{wt}(f(u,v)+B(u,v)). \end{aligned}$$ Every expectation uses independent uniform input vectors of the indicated dimensions. Hamming weight is unnormalized. Define $K_k$ to be the least constant for which $\mathcal D(f)\le K_k\mathcal E(f)$ holds for all such functions. A zero defect means the function is already bilinear, so presents no exceptional case.

Theorem. Write $M=2^{k+2}$. Then $$\boxed{\displaystyle K_k\ge \frac{k+2/M}{8(1-1/M)(1-2/M)} \ge\frac{k}{8}=\frac{\log_2 n}{40}.} \tag{1}$$ We give an explicit witness whose own optimal repair ratio is $\Theta(k)$. We do not prove $K_k=\Theta(k)$ for all functions. The existing whole-vector argument gives only the general upper bound $K_k\le222\,2^k$: its vector disagreement bound is converted to weight using the ratio of maximum to minimum nonzero codeword weight.

2. A small code and an explicit nonlinear rounding

Set $s=k+2$, so $M=2^s$. Consider $$C=\mathrm{RM}(s-2,s)\subseteq\mathbb F_2^M.$$ This is the extended binary Hamming code. Its parity-check map $\Pi:\mathbb F_2^M\to\mathbb F_2\times\mathbb F_2^s$ has columns $(1,a)$, indexed by $a\in\mathbb F_2^s$. They span the target, so $\operatorname{codim}C=s+1$.

These facts can also be checked without naming the code. Every polynomial of degree at most $s-2$ is orthogonal to every affine polynomial on the cube. The former space has dimension $2^s-s-1$, so it is exactly the kernel of the $s+1$ affine checks.

Let $\mathbf e_a$ denote the unit vector at coordinate $a$. For a syndrome $(p,a)$, choose $$e(p,a)=\mathbf e_a+(1+p)\mathbf e_0.$$ Its syndrome is $(p,a)$, including $a=0$. Thus $$F(x)=x+e(\Pi x)\in C.$$ This rounding changes at most two coordinates. Since $\Pi x$ is uniform when $x$ is uniform, $$\mathbb E_x\operatorname{wt}(F(x)+x)=\frac32-\frac1M. \tag{2}$$ Half the syndromes have $p=1$ and use one flip; the nonzero even-parity syndromes use two; the zero syndrome uses none.

Rounding does not commute with addition. Its defect for syndromes $(p,a),(q,b)$ is exactly $$e(p,a)+e(q,b)+e(p+q,a+b) =\mathbf e_a+\mathbf e_b+\mathbf e_{a+b}+\mathbf e_0.$$ This has weight four when $a,b$ are distinct and nonzero, and zero otherwise. Consequently $$\mathbb E_{x,x'}\operatorname{wt} (F(x)+F(x')+F(x+x')) =4(1-1/M)(1-2/M). \tag{3}$$

3. Embed the witness into the required advice space

Write an evaluation point in $\mathbb F_2^{10k}$ as $(a,z)$, where $a\in\mathbb F_2^s$ and $z\in\mathbb F_2^{10k-s}$. Repeating a word of $C$ over all $z$ gives a word of $U$: its polynomial has degree at most $s-2=k$ and ignores $z$. There are $$D=2^{10k-s}$$ copies. Also $M\le n$. For $u\in\mathbb F_2^n$, let $x$ be its first $M$ coordinates, and define $$f(u,v)=v_1\,\operatorname{repeat}(F(x)). \tag{4}$$ This uses exactly the prescribed input spaces and takes values in $U$. It is linear in $v$, so $\delta_2f=0$. Equations (3) and (4) give $$\mathcal E(f)=2D(1-1/M)(1-2/M). \tag{5}$$

4. Every repair inside the full code remains costly

Let $B:\mathbb F_2^n\times\mathbb F_2^n\to U$ be any bilinear map. It may use all input and evaluation coordinates; we do not require it to repeat the small code.

Fix a value of the extra evaluation variables $z$. Restricting any degree-$k$ polynomial to that slice leaves a polynomial of degree at most $k=s-2$ in $a$. Thus the sliced output of $B$ always belongs to $C$. Now fix $v$ with $v_1=1$, and fix the unused coordinates of $u$. As a function of $x$, the sliced output is an affine map $Lx+c$ into $C$. In particular $\Pi L=0$.

The identity $\Pi(I-L)=\Pi$ implies $\operatorname{rank}(I-L)\ge s+1$. A binary affine map with linear part of rank at least $s+1$ has at least $s+1$ nonconstant output coordinates. Each is one on half the uniform inputs. Therefore $$\mathbb E_x\operatorname{wt}(x+Lx+c)\ge\frac{s+1}{2}.$$ The triangle inequality and (2) yield $$\mathbb E_x\operatorname{wt}(F(x)+Lx+c) \ge\frac{s+1}{2}-\left(\frac32-\frac1M\right).$$ Average over the fixed unused inputs, sum over all $D$ evaluation slices, and use $\Pr[v_1=1]=1/2$. The omitted $v_1=0$ case contributes nonnegative error. We obtain $$\mathcal D(f)\ge D\left(\frac{k}{4}+\frac1{2M}\right). \tag{6}$$ Dividing (6) by (5) proves (1).

The order of this witness’s distance is also sharp. Choose a linear right inverse $T$ of $\Pi$ supported on $s+1$ independent check columns. Then $L_0=I+T\Pi$ maps into $C$, and $\mathbb E\operatorname{wt}(T\Pi x)=(s+1)/2$. The bilinear map $v_1\operatorname{repeat}(L_0x)$ has mean error at most $$D\left(\frac{k+6}{4}-\frac1{2M}\right).$$ Together with (5) and (6), this proves a $\Theta(k)$ repair ratio for the explicit witness. It is an upper bound on repair error, not on query access cost.

5. Why the query conjecture survives

For the storage problem, $w=R^{\mathsf T}\operatorname{vec}(A)$ and $Hw$ are the $d+n$ stored bits. The query coefficient vector is $$P_R(u,v)=R^{-1}\operatorname{vec}(uv^{\mathsf T}).$$ Its linear extension from matrix space has rank $d$, since $R$ is invertible. A cheap answer would require $P_R(u,v)$ to be close to $U$, with a nonlinear choice of the nearby codeword.

Our witness is instead close to $$G(u,v)=v_1\,\operatorname{repeat}(u_{[M]}),$$ whose linear extension has rank only $M=4n^{1/5}$. Thus this construction does not produce cheap answer patterns for any $P_R$. Adding enough independent bilinear outputs to obtain rank $d$, while keeping distance to $U$ small, is an unresolved additional obligation.

There is a stronger safeguard against misreading this example. For every $P_R$ and every $U$-valued bilinear $B$, $$\mathbb E\operatorname{wt}(P_R+f+B) \ge\frac{d-M-r}{4} -D\left(\frac34-\frac1{2M}\right) \ge\frac d8. \tag{7}$$ Indeed, $P_R+G+B$ has extension rank at least $d-M-r$. Every nonzero scalar bilinear coordinate is one on at least one quarter of uniform input pairs, so its mean weight is at least this rank divided by four. Subtract the exact mean weight of $f+G$, given by (2). For the last inequality use $M\le n$, $r<n$, $n\ge32$, and $M\ge8$. Thus even adding an arbitrary internal bilinear correction to this witness cannot make it a cheap selector for a full-rank query map.

The failed principle would have implied a read bound $(d-r)/(4(1+6K_k))$. Equation (1) shows that a uniform theorem covering all $U$-valued functions cannot make this particular route quadratic. It does not exclude a theorem for the more restricted functions induced by full-rank query maps, and it does not change the previously established access bounds.

The underlying model remains exact deterministic adaptive bit reads after independent preparation, including deferred work. All matrix-dependent initial information is charged; local computation and allocation are free. Boundary width is $b=2n$, input size is $\Theta(n^2)$ coefficient bits or $N=\Theta(n^2\log n)$ in the explicit named 3CNF encoding, and storage is $S=n^2+n$. Dense preprocessing uses $O(Sn^2)$ binary operations. The witness is a mathematical function used to test a proof principle, not a new preprocessing or composition algorithm. No unrestricted SAT, Turing-machine or scaffolding-automaton lower bound follows.

Provenance and the remaining bottleneck

Extended Hamming parity checks and covering radius two are classical. For a primary source, see Elimelech, Wei and Schwartz, On the Generalized Covering Radii of Reed-Muller Codes, Proposition 13; the ordinary covering-radius case is $t=1$. The explicit rounding and all required calculations were given above.

The broader issue of local consistency versus global correction is studied in robust testing of tensor-product codes. For example, Dinur, Sudan and Wigderson prove robustness under a smoothness hypothesis and discuss counterexamples without adequate hypotheses. Their theorem is not being imported as a size-independent bound for this Reed-Muller family.

The connection between systematic linear storage and distance of query sets from low-dimensional spaces is established by Ramamoorthy and Rashtchian. Their raw-coordinate result must not be silently extended through arbitrary invertible coordinate changes.

The additional argument here embeds the rounding obstruction into the specific low-rate advice family and required input dimensions, and proves that unrestricted bilinear repairs in the larger code cannot evade it. Novelty is unestablished. The proof received independent agent review; it is not proof-assistant verified. The finite checker and recorded output test the rounding identities and a small explicit repair, not the unbounded quantifiers.

The remaining question is now narrower: do there exist constants $c,K$, independent of $k$, such that for every $k\ge1$ and every function $f$ specified above, repair can leave $U$, while keeping the rank of its bilinear extension at most $c\,r$ for a constant $c$, and keeping its mean Hamming error at most $K\mathcal E(f)$ for a constant $K$? This is a conjectural sufficient route for this Reed-Muller family, not an established theorem. It would leave the rank gap $d-c\,r$ needed for quadratic access.

The present witness does not obstruct that weaker proposal: its external approximant $G$ has rank $M\le r$ and bounded error-to-defect ratio. The ordinary coordinatewise correction argument already controls error; the unresolved obligation is controlling the rank without forcing the repaired values to stay in $U$. The full-rank query map remains essential to the eventual access conclusion.