A sharp limit on repairing disjoint blocks

Working research note, 2 October 2026.

Overview

The preceding whole-vector theorem turns the organization of stored parity checks into a lower-bound certificate. It looks for disjoint groups with two properties: the groups should have small total dimension, and their nonzero words should have comparable Hamming weights. When both conditions hold, the certificate forces many reads to answer a later query $u^{\mathsf T}Av$.

The family here exposes a two-sided obstruction. Index the $n^2$ stored coordinates by binary strings and let the advice consist of truth tables of low-degree Boolean polynomials. Globally, this advice space has fewer than $n$ dimensions. Locally, however, every group smaller than a threshold can realize every bit pattern, so a containing code must spend one dimension per coordinate. A larger group avoids that cost, but it contains both the all-ones word and a much sparser affine-flat word. Their weights differ by a large factor. Small groups exhaust the dimension budget; large groups lose weight balance.

Classical Reed-Muller codes make this obstruction explicit, even after choosing arbitrary retained coordinates, arbitrary disjoint groups, and arbitrary larger linear spaces containing their restrictions. On the family below, the best numerical lower bound from that particular theorem is of order $n^{9/5}$, rather than $n^2$.

This has two distinct consequences. It proves an actual mean-read lower bound of order $n^{9/5}$ for this family, under every invertible choice of matrix coordinates. It also proves that optimizing the preceding theorem’s parameters cannot make that bound quadratic. It does not supply a query algorithm using $n^{9/5}$ reads or refute the quadratic conjecture.

1. The storage model and the certificate being limited

All vector spaces are over $\mathbb F_2$. The fragments are

$$F_A:\ y=Ax,\qquad G_{u,v}:\ x=v,\quad u^{\mathsf T}y=1.$$

Their compatibility is exactly $u^{\mathsf T}Av=1$. Put $d=n^2$. Independent matrix preprocessing stores

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

These $S=d+n$ bits are all matrix-dependent initial information. The encoding, addresses and algorithm are fixed and public. There is no hidden matrix copy, uncharged metadata or cache from previous queries. Storage is immutable. Algorithms are deterministic, adaptive, and exact for all inputs. Local computation, allocation and query-only preparation are free. Charge old-storage reads from composition through the answer, including deferred query work. The output is one bit.

The whole-vector theorem allows all advice and the independent bits outside a retained set $J$ to be free. Write $g=|J|$. Partition $J$ into nonempty disjoint blocks $B_j$, and choose linear codes

$$C_j\supseteq (\operatorname{rowspan}H)|_{B_j}.$$

Let $\lambda_j$ and $D_j$ be their minimum nonzero and maximum weights, and set $a=\max_j D_j/\lambda_j$, $q=\sum_j\dim C_j$. The numerical certificate is

$$\mathcal B(J,(C_j))=\frac{g-q}{4(1+1332a)}. \tag{1}$$

For every fixed matrix $A$, every invertible $R$, and every exact algorithm, (1) lower-bounds mean retained reads over independent uniform $u,v$, including zero. Its proof permits nonlinear choices of shortest answer patterns. We use this established sufficient theorem without re-proving it. An empty retained set has certificate zero.

The present result limits a single application of (1). It allows every puncturing, partition and containing code in that formula, but does not limit recursive correction, overlapping repair spaces, or all possible lower-bound arguments.

2. The explicit family and exact statement

For an integer $k\ge1$, take

$$m=10k,\qquad n=2^{5k},\qquad d=2^m=n^2.$$

Index the independent stored coordinates by the points of $\mathbb F_2^m$. Let $U=\mathrm{RM}(k,m)$ be the vectors obtained by evaluating all multilinear polynomials of degree at most $k$ on those points. Thus

$$r=\dim U=\sum_{i=0}^k\binom mi\le(em/k)^k=(10e)^k<n. \tag{2}$$

For completeness, with $x=k/m\le1$, $x^k\sum_{i\le k}\binom mi\le(1+x)^m\le e^{mx}=e^k$, which gives the inequality in (2). Distinct squarefree monomials are a basis of functions on the Boolean cube; this follows inductively by separating the last variable.

Use their evaluation vectors as the $r$ nonzero rows of $H$, and pad the remaining $n-r$ rows with zeros. This uses at most the authorized $n$ extra linear bits. The zeros can be omitted; they carry no information. The construction has polynomial description size and a direct evaluation algorithm. No search over matrices is needed.

Theorem. For this family, define $\mathcal B_*$ as the supremum of (1) over every retained set, every disjoint partition, and every containing linear code. Then

$$\boxed{\displaystyle \frac{d-r}{4(1+1332\,2^k)} \le\mathcal B_*<\frac{d}{3552\,2^k}.} \tag{3}$$

In particular, $\mathcal B_*=\Theta(n^{9/5})$. The lower endpoint is an actual mean-read lower bound for every $A,R$ and exact adaptive algorithm in the model. The upper endpoint bounds this certificate, not the number of reads needed by an algorithm. The elementary read-all upper bound remains $d$.

The exponent $9/5$ is a convenient explicit construction parameter. It is not asserted to be optimal among Reed-Muller choices or all methods.

3. Why small groups cannot save dimension

We first prove a classical local independence property:

$$|B|<2^{k+1}\quad\Longrightarrow\quad U|_B=\mathbb F_2^B. \tag{4}$$

If the restriction were proper, there would be a nonempty subset $T$ of $B$ such that the sum of every degree-at-most-$k$ polynomial over $T$ is zero. We show such a set has at least $2^{k+1}$ points.

For degree zero, the constant polynomial forces a nonempty $T$ to have even cardinality, hence at least two points. For the induction step choose a coordinate on which points of $T$ differ. Both slices are nonempty. For every polynomial $h$ of degree at most $k-1$ on the remaining coordinates, the tests $x_i h$ and $(1+x_i)h$ imply that each slice annihilates every such $h$. Each therefore has at least $2^k$ points by induction. Their union has at least $2^{k+1}$, proving (4).

This is the familiar dual-distance property of Reed-Muller codes, with an elementary proof included to expose precisely what is needed. In particular, even a small-dimensional global code looks completely unconstrained on every sufficiently small group of coordinates. A containing code on such a group must be the whole space, spending one dimension per coordinate.

4. Why large groups cannot have balanced weights

Fix any nonempty block $B$, of size $t$, and a point $x\in B$. Choose uniformly a codimension-$k$ affine flat through $x$. Its indicator is a product of $k$ affine linear functions, so its evaluation vector belongs to $U$. It is nonzero at $x$.

Every other point belongs to this random flat with probability

$$p=\frac{2^{m-k}-1}{2^m-1}<2^{-k}. \tag{5}$$

Indeed, the associated linear subspace has $2^{m-k}-1$ nonzero vectors, and symmetry treats all $2^m-1$ nonzero vectors equally. The expected weight of the flat indicator restricted to $B$ is $1+(t-1)p$. Some such nonzero restricted word therefore has at most that weight.

Every code $C\supseteq U|_B$ also contains the all-ones word. Consequently

$$\frac{D(C)}{\lambda(C)} \ge\frac{t}{1+(t-1)p}. \tag{6}$$

This argument concerns arbitrary subsets $B$, not just subcubes or unions of flats. Enlarging the containing code cannot evade it: the short word and the all-ones word remain present.

If (1) is positive, $q<g$, so at least one block has a proper containing code $C_j\ne\mathbb F_2^{B_j}$. By (4) its size is at least $2^{k+1}$. The right side of (6) increases with $t$, hence

$$a\ge\frac{2^{k+1}}{1+(2^{k+1}-1)p}>\frac{2^{k+1}}3.$$

Substitution in (1), using $g-q\le d$, gives the strict upper bound in (3). Zero certificates also satisfy that bound.

Thus for any fixed weight-ratio bound, once $k$ is large enough every admissible containing product has $q=g$: its certificate is exactly zero. Arbitrary deletion of coordinates cannot restore a useful rank gap. This supplies the requested counterexample to a universal bounded-ratio product-cover condition.

5. The matching certificate

The minimum nonzero weight of $U$ is $2^{m-k}$, while its maximum is $d$. Here is the standard induction for the lower distance bound. Write a polynomial as $f=g+x_mh$. If $h\ne0$, its degree is at most $k-1$ and

$$\operatorname{wt}(f)=\operatorname{wt}(g)+\operatorname{wt}(g+h) \ge\operatorname{wt}(h)\ge2^{m-k}.$$

If $h=0$, the table of $g$ is repeated twice and induction gives the same bound. The boundary cases of constant degree or degree equal to the number of variables are immediate. A product of $k$ independent affine factors attains weight $2^{m-k}$.

Retain every coordinate and choose the single containing code $C=U$. Then $a=2^k$, $q=r$, and (1) gives the lower endpoint of (3). Since $r<n$ and $d=n^2$, the two endpoints have the same asymptotic order. The matching construction here is a proof certificate, not a matching query algorithm.

The obstruction is not caused by padding advice with zeros. Extend $U$ to any $n$-dimensional subspace of $\mathbb F_2^d$. Properties (4) and (6) persist because all the old codewords remain. The same certificate ceiling therefore holds with $n$ independent advice rows. The matching lower endpoint above is proved for $U$, not arbitrary extensions.

Resources, provenance and remaining question

The boundary width is $b=2n$. The fragment descriptions use $\Theta(n^2)$ matrix coefficient bits, or $N=\Theta(n^2\log n)$ in the established explicit named 3CNF encoding, including auxiliary variables and their names. The input is polynomial in $b$; no exponential-in-$b$ lower bound is being asserted. Storage is $S=n^2+n$, with $n-r$ optional known zero slots. Dense matrix preprocessing costs $O(Sn^2)$ binary operations; public $R$ and $H$ have polynomial descriptions. The bound charges work after separate preparation, including any deferred answer work. It holds even with advice free, so also when those reads are charged.

The code family, its dimension, distance and dual-distance properties are classical. They are presented in Sections II-A–II-D of Abbe, Shpilka and Ye, Reed-Muller Codes: Theory and Algorithms, which credits the original Reed and Muller constructions. The needed properties and the flat-averaging calculation were proved explicitly above. The read-bound dependency is the preceding whole-vector theorem, built on classical homomorphism correction. The additional content here is their application to the precise optimization over retained coordinates and containing products. Novelty is unestablished. These are written proofs, not proof-assistant-verified statements.

No lower bound transfers automatically to all Turing-machine or scaffold implementations: the charged observations and initialized storage would need an access-preserving simulation. The language/graph-observation distinction and the scaffold-to-PEG reversal remain unchanged.

The next question is concrete: can one repair a function taking values in this Reed-Muller space inside that same space, controlling expected Hamming error by expected Hamming additive defects with a constant independent of $k$? Such a result would preserve rank $r$, rather than paying the sum of local containing dimensions. A counterexample would identify a further limitation of correction-based proofs. Neither answer is supplied here, and failure for arbitrary functions would not by itself rule out a repair argument for the particular query-induced functions.

The checker and recorded output examine small Reed-Muller restrictions and flat incidences. They do not establish (3) for the unbounded family or verify adaptive algorithms.