Local rectangle consistency limits the use of saved parities

Working research note, 3 October 2026.

The foundations program asks when future computational behavior can be represented using finite rules, bounded local access and bounded allocation. Its current composition question asks how much independently saved work must be read when a binary matrix meets a separately prepared query.

Here is a structural case in which we can answer more precisely. Suppose every saved parity pattern obeys a four-cell rule: the XOR of its entries around any rectangle is zero. Such patterns can overlap in many rows and columns. Nevertheless, with at most $n$ saved parities, their best mean read cost is $$\frac{n^2}{4}-\Theta(n^{3/2}). \tag{1}$$ The same conclusion survives $O(n^{3/2})$ exceptional cells, provided one common set of cells repairs the entire family. This is a result for a specified class of representations. The conjecture for all linear advice codes of dimension at most $n$ remains open.

The useful change in perspective is to study a rule shared by the whole representation, rather than add up the gains of individual generators. The preceding note showed why bounding every individual increment cannot work. The present rule controls total alignment with a future query, including overlapping generators and linear constraints among them.

1. Storage contract and the quantity being bounded

The two binary affine fragments are $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$. Their shared boundary has width $b=2n$. The coefficient description has size $N_0=\Theta(n^2)$; the fixed-shape named-CNF description has size $N=\Theta(n^2\log n)$, including variable names, clauses and private auxiliary variables. We use the input construction and minimum-support characterization in the linear-advice composition note.

Fix a public binary linear code $C\subseteq\mathbb F_2^{n\times n}$, of dimension $r\le n$, with a public independent basis $B_1,\ldots,B_r$. Independently prepare the matrix fragment by storing all $n^2$ entries of $A$, and the $r$ bits $\langle A,B_\ell\rangle$ over $\mathbb F_2$. Thus $S=n^2+r\le n^2+n$ stored bits. There is no other matrix-dependent initialization, metadata, address choice or hidden copy. The layout and encoding are fixed before the matrix and query are chosen.

Stored bits are immutable. A deterministic algorithm must answer $u^{\mathsf T}Av$ exactly for every $A,u,v$. Each adaptive observation has alphabet $\{0,1\}$ and costs one read. Routing, addresses, pointer identity and control flow supply no additional matrix-dependent channel. Charge reads made during combination and any work deferred until the answer. Local computation, allocation and query-only preparation are free in this model. The output is one bit. The query vectors $u,v$ are independent and uniform when taking a mean; the read lower bound holds on every stored matrix $A$.

Write $B(z)=\sum_\ell z_\ell B_\ell$ over $\mathbb F_2$. The minimum-support characterization gives the exact optimal charged cost $$\tau_C(u,v)=\min_{z\in\mathbb F_2^r} \left[\operatorname{wt}(uv^{\mathsf T}+B(z))+ \operatorname{wt}(z)\right]. \tag{2}$$ With advice reads free this is exactly $d(uv^{\mathsf T},C)$, and $$d(uv^{\mathsf T},C)\le\tau_C(u,v) \le d(uv^{\mathsf T},C)+r. \tag{3}$$ Attainability allows unrestricted query-only nearest-codeword search; it does not assert efficient local running time. Any particular exact algorithm has at least this many charged reads.

For integer-valued scores, define $$S(B;u,v)=\sum_{ij}B_{ij}(2u_iv_j-1),\qquad F(C)=\mathbb E_{u,v}\max_{B\in C}S(B;u,v).$$ The Hamming-weight identity gives $$\mathbb E d(uv^{\mathsf T},C)=\frac{n^2}{4}-F(C). \tag{4}$$ The outstanding systematic-storage conjecture is $F(C)=O(n^{3/2})$, uniformly for every $\dim C\le n$. This note proves it under a local consistency or common-repair hypothesis. Arbitrary changes of the stored coordinate basis belong to the larger model and are not covered by this new sharp estimate.

2. The four-cell rule and an exact containing-family calculation

Define the rectangle-consistent space $$L_n=\{B:B_{ij}=x_i\oplus y_j, \quad x,y\in\mathbb F_2^n\}. \tag{5}$$ Equivalently, every four-cell check vanishes: $$B_{ij}\oplus B_{i\ell}\oplus B_{kj}\oplus B_{k\ell}=0 \quad\text{for all }i,k,j,\ell. \tag{6}$$ For the reverse implication, fix an anchor $(k,\ell)$ and take $x_i=B_{i\ell}$, $y_j=B_{kj}\oplus B_{k\ell}$. Condition (6) then gives (5). The kernel of the label map consists of simultaneously complementing every $x_i$ and $y_j$, so $\dim L_n=2n-1$. In graph language this is the cut space of the complete bipartite graph. It is also the two-domain binary direct-sum family.

The larger space $L_n$ is an analytical relaxation. Storing all its independent parities would exceed the budget $r\le n$ for $n>1$. We use it only to upper-bound the score of admissible subcodes.

Put $$U=\operatorname{wt}(u),\quad V=\operatorname{wt}(v),\quad a=2V-n,\quad d=2U-n,\quad \mu_n=\mathbb E(2\operatorname{Bin}(n,1/2)-n)_+.$$

Proposition 1. For every query, $$\max_{B\in L_n}S(B;u,v) =\max\{0,Ua,Vd,n(U+V-n)\} =Ua_++Vd_+-a_+d_+. \tag{7}$$ Consequently $$F(L_n)=n\mu_n-\mu_n^2 =\frac{n^{3/2}}{\sqrt{2\pi}}- \frac{n}{2\pi}+O(\sqrt n). \tag{8}$$

Proof. Split row labels according to whether $u_i=1$ or $0$, and column labels according to whether $v_j=1$ or $0$. The score depends only on the number of selected labels in each of these four groups. With three counts fixed, it is affine in the fourth. Therefore some maximum occurs with each group entirely selected or entirely unselected. Empty groups cause no difficulty.

These sixteen corners give at most eight matrices, because complementing both label vectors preserves the matrix. They are zero, the all-ones matrix, the active and inactive full rows, the active and inactive full columns, $u_i\oplus v_j$, and its complement. Their scores are respectively $$0,\quad 2UV-n^2,\quad Ua,\quad -n(n-U),\quad Vd,\quad -n(n-V), \quad 2UV-n(U+V),\quad n(U+V-n).$$ The inactive-row, inactive-column and $u\oplus v$ scores are nonpositive. The all-ones score is at most the last score since $n(U+V)-2UV\ge0$. This leaves the four candidates in (7).

If $U,V\le n/2$, their maximum is zero. If $U\le n/2<V$, it is $Ua$, because $n(U+V-n)-Ua=(n-V)(2U-n)\le0$. The other mixed case is symmetric. If both exceed $n/2$, the last candidate is largest. In each case it equals the positive-part expression in (7).

Independence gives $\mathbb E Ua_+=\mathbb E Vd_+=n\mu_n/2$ and $\mathbb E a_+d_+=\mu_n^2$. Finally, the elementary binomial identity and Stirling estimate used in the row-parity note give $$\mu_n=n2^{-n}\binom{n-1}{\lfloor n/2\rfloor} =\sqrt{\frac n{2\pi}}+O(n^{-1/2}).$$ Substitution proves (8). $\square$

In particular every admissible $C\subseteq L_n$, however its generators overlap, satisfies $$\mathbb E\tau_C\ge\frac{n^2}{4}-n\mu_n+\mu_n^2. \tag{9}$$ The full-row code $\{y\mathbf1^{\mathsf T}\}$ has dimension $n$ and lies in $L_n$. Its free saving is $n\mu_n/2$; charging advice adds at most $n$ reads. This proves the matching secondary order in (1) for this class. It does not identify the best secondary coefficient under the dimension budget.

3. A common repair set controls exceptions

For a linear code $C$, define its local failure rate by $$\rho(C)=\Pr_{B,i,k,j,\ell} [B_{ij}\oplus B_{i\ell}\oplus B_{kj}\oplus B_{k\ell}=1], \tag{10}$$ where $B$ is uniform in $C$ and the four indices are independent and uniform in $[n]$. Repeated indices are allowed and give a zero check. This tests public parity patterns, not runtime observations of the stored matrix.

Proposition 2. For every binary linear matrix code, $$F(C)\le n\mu_n-\mu_n^2+2\rho(C)n^2. \tag{11}$$ More precisely, there is one anchor and one linear repair map into $L_n$ which alter every codeword only on a common set of $h\le2\rho(C)n^2$ coordinates. The last term in (11) can be replaced by this $h$.

Proof. For a fixed rectangle, its check is a linear functional on $C$. It is either identically zero or equals one on exactly half the codewords. Thus the fraction of rectangle functionals nonzero on $C$ is $2\rho(C)$.

For an anchor $(k,\ell)$, let $H_{k,\ell}$ contain the cells $(i,j)$ whose anchored rectangle functional is nonzero on $C$. Averaging over anchors gives $$\mathbb E_{k,\ell}|H_{k,\ell}|=2\rho(C)n^2.$$ Choose an anchor with $h=|H_{k,\ell}|$ no larger than this mean, and define, for every $B\in C$, $$(TB)_{ij}=B_{i\ell}\oplus B_{kj}\oplus B_{k\ell}. \tag{12}$$ The map is linear, its image lies in $L_n$, and outside the single set $H_{k,\ell}$ every $B$ agrees with $TB$. Changing a matrix entry changes its score by at most one. Therefore, for every query and every codeword, $$S(B;u,v)\le S(TB;u,v)+h \le\max_{D\in L_n}S(D;u,v)+h.$$ Taking maxima and means proves (11). $\square$

The common set matters: an independently chosen nearest consistent pattern for each codeword need not repair the entire representation on the same coordinates. Linearity supplies the common-set estimate here.

For $\dim C\le n$, (4) and (11) give the charged and free lower bound $$\mathbb E\tau_C\ge \frac{n^2}{4}-n\mu_n+\mu_n^2-2\rho(C)n^2. \tag{13}$$ Thus $\rho(C)=o(1)$ ensures the leading constant $1/4$, and $\rho(C)=O(n^{-1/2})$ ensures an $O(n^{3/2})$ maximum saving. Together with full-row advice, this gives (1) for each class with a fixed bound $\rho(C)\le K/\sqrt n$, where $K$ is independent of $n$.

Another useful case is $C\subseteq L_n+P$, where all matrices in $P$ are supported in the first column. For $n\ge2$, choose an anchor in another column. The common repair set is contained in the first column, excluding the anchor row, so $h\le n-1$. This includes the singleton padding used in the preceding increment counterexample. Its large last-step gain is compatible with the new total-score bound.

The dimension budget does not imply a small local failure rate. For even $n$, let $D$ be the indicator of the first $n/2$ rows and first $n/2$ columns. Its rectangle check factors as a row-membership difference times a column-membership difference. Each difference is one with probability $1/2$, so the one-dimensional code $\{0,D\}$ has $\rho=1/8$. Equation (11) is a structural criterion, not a proof of the unrestricted conjecture.

4. Heavy overlap can have only a linear saving

The preceding investigation found a code with large unsigned bilinear fluctuations. Keeping the weight penalty allows an exact calculation instead. Let $$K_n=\{B(x):B(x)_{ij}=x_i\oplus x_j\},\qquad \dim K_n=n-1.$$ This is a subcode of $L_n$, with substantially overlapping generators.

Proposition 3. Its actual score is $$\max_{B\in K_n}S(B;u,v) =2\left\lfloor\frac{(U+V-n)_+^2}{4}\right\rfloor, \qquad F(K_n)=\frac{n-1}{8}. \tag{14}$$

Proof. Partition indices by $(u_i,v_i)$ into types $00,10,01,11$, with counts $a,b,c,d$. The diagonal of a cut matrix is zero. For an unordered pair, counting both matrix orientations, selecting the cut contributes $+2$ for a $11$–$11$ pair, $-2$ for any pair incident to $00$ or within $10$ or $01$, and zero for every other pair.

With all other selections fixed, the score is a convex quadratic in the number selected in any one of the three types $00,10,01$. Its within-type term is $-2t(m-t)$, and its cross-type terms are affine. A maximum can therefore put each of these types wholly on one side. Complement the cut labels to put $00$ on side zero. Put $10$ and $01$ there too: this removes penalties with $00$ and changes no other contribution. If $00$ is empty this choice is still permissible.

Selecting $t$ of the $11$ indices on the opposite side now gives $2t(d-a-t)$. Maximizing over $0\le t\le d$ yields the first formula in (14), since $d-a=U+V-n$.

The variable $T=U+V-n$ has law $\operatorname{Bin}(2n,1/2)-n$. It is symmetric with variance $n/2$, so $\mathbb ET_+^2=n/4$. It is odd with probability $1/2$, and $\Pr(T>0\text{ and odd})=1/4$ by symmetry. For positive integer $T$, the full score $2\lfloor T^2/4\rfloor$ is $(T^2-\mathbf1_{T\text{ odd}})/2$. Its expectation is $(n-1)/8$. $\square$

For comparison, independent uniform signs $\varepsilon,\delta$ give $$\mathbb E\max_{B\in K_n}|\varepsilon^{\mathsf T}B\delta| \ge\frac{n^2-n}{8}.$$ Indeed select $x_i=1$ when both signs equal one, and put $h=\sum x_i$. The selected bilinear sum is $h(\sum\varepsilon_i+\sum\delta_i)-2h^2$, whose expectation is $-(n^2-n)/8$. Taking its absolute value and then a maximum proves the bound. Discarding the outside-support penalty converts a code with only linear useful saving into a misleading quadratic fluctuation estimate.

5. Resources, provenance and the next precise question

For rectangle-consistent codes and the stated repair classes, the unavoidable mean post-preparation read cost is $n^2/4-O(n^{3/2})$. Full-row advice attains $n^2/4-\Theta(n^{3/2})$, charged or free. In boundary width this is $b^2/16-\Theta(b^{3/2})$ for the optimum within these classes. Its leading order is $\Theta(N_0)$, or $\Theta(N/\log N)$ in the named-CNF encoding. It is quadratic in boundary width, not quadratic in the complete formula-description size.

Matrix preprocessing costs $O(n^2+\sum_\ell\operatorname{wt}(B_\ell))\le O(n^3)$ bit operations using direct parity evaluation. The full-row upper construction uses $O(n^2)$ preparation. Public dense generator descriptions have at most $n^3$ bits; they are fixed encoding parameters, not uncharged matrix-dependent storage. Query preparation is independent of $A$. The bound charges composition plus deferred query reads and does not impose a separate lower bound on composition when the answer may be postponed.

The direct-sum structure and its local testing are classical. See Dinur and Golubev, Direct Sum Testing: The General Case, RANDOM 2019, Definition in Section 1 and Test 1/Theorem 1.1. Their general product-domain test has a different sampling rule; its general soundness theorem is not used here. Our two-domain anchor repair is proved directly. The additional content here is the exact expected-score calculation, the common linear-family repair bound, and their resource consequence in the saved composition model. Historical novelty is unestablished.

The proofs are written arguments, independently reviewed and reconciled. The finite checker and output corroborate the identities and common repair; they do not prove the infinite statements. No proof-assistant verification or new machine transfer is claimed. In particular the local pattern rule is not automatically a consequence of finite-rule maintainability. No unrestricted SAT, Turing-machine or scaffolding-automaton lower bound is inferred.

The next concrete case separates how many independent defects there are from how many cells they affect. For a fixed arbitrary matrix $D$, is $$\sup_{\substack{\dim C\le n\\ C\subseteq L_n+\langle D\rangle}} F(C)=O(n^{3/2}) \tag{15}$$ uniformly in $D$? A single generator outside $L_n$ can violate a positive fraction of all local checks, making (11) ineffective, yet a lone matrix already has small expected positive score. Equation (15) asks whether this remains true when that defect interacts with the whole consistent family. The subsequent two-stage contraction proof settles (15), and more generally proves the same secondary saving order for any fixed number of independent departures from $L_n$. It strengthens the intervening leading-constant result. The remaining general-code question concerns a growing number of independent departures; dimension at most $n$ does not bound that number by a constant.