Dense exceptions preserve the leading composition constant

Working research note, 3 October 2026.

The broader foundations goal is to understand when future computation admits representations maintained by finite rules, bounded local access and bounded allocation. Here we continue the concrete matrix/query composition problem: how much must be read after the matrix and query have been prepared separately?

The previous structural result covered saved parity patterns satisfying a four-cell consistency rule, with exceptions confined to a small common set of cells. A single additional pattern can affect every cell, making that repair estimate ineffective. Nevertheless, we can now prove that one such pattern cannot change the leading mean cost of $n^2/4$. More generally, the conclusion survives $o(n)$ independent departures from the consistent family.

This argument settles the leading constant for an enlarged structural class. The subsequent two-stage contraction argument now proves the sharper $O(n^{3/2})$ saving bound for any fixed number of independent departures. The general dimension-$n$ code conjecture and arbitrary stored coordinate bases remain outside these conclusions.

1. Statement and storage contract

Let $$L_n=\{B:B_{ij}=x_i\oplus y_j\},\qquad S(B;u,v)=\sum_{ij}B_{ij}(2u_iv_j-1),\qquad F(C)=\mathbb E\max_{B\in C}S(B;u,v),$$ where $u,v$ are independent uniform binary vectors. For a linear code $C$, define its number of independent departures by $$d=\dim((C+L_n)/L_n)=\dim C-\dim(C\cap L_n). \tag{1}$$ This counts dimensions outside the local rule, not exceptional cells.

Theorem. There is an absolute constant $K$ such that, for every $n\ge2$ and every binary linear matrix code $C$, $$F(C)\le K\frac{n^2}{\sqrt{\log_2(n+1)}} +2n^{3/2}\sqrt{d\ln2}. \tag{2}$$ In particular $d=o(n)$ implies $F(C)=o(n^2)$, uniformly over all such families. For a single arbitrary fixed matrix $D$, $$F(L_n+\langle D\rangle)=O(n^2/\sqrt{\log(n+1)}). \tag{3}$$ The larger containing spaces are analytical relaxations. An admissible storage code still has $r=\dim C\le n$.

We retain exactly the systematic storage model of the linear-advice note: store the $n^2$ raw bits of $A$ and $r$ fixed public linear parities in immutable fixed-address storage. No other matrix-dependent state, metadata, routing or initialization is available. Algorithms are exact and deterministic on every $A,u,v$, and every old-bit observation costs one read through combination and the final answer, including deferred reads. Query-only preparation, local computation and allocation are free; the output is $u^{\mathsf T}Av$. Advice patterns are fixed before the inputs are chosen.

The established minimum-support characterization gives $$\mathbb E d(uv^{\mathsf T},C)=n^2/4-F(C),\qquad d(uv^{\mathsf T},C)\le\tau_C(u,v)\le d(uv^{\mathsf T},C)+r. \tag{4}$$ Here $\tau_C$ is optimal charged read cost, not unrestricted running time. Thus every admissible family with $d=o(n)$ has optimal mean read cost $(1/4-o(1))n^2$. Reading raw selected entries supplies the matching leading upper bound $n^2/4$. Full-row advice still supplies the better upper construction $n^2/4-\Theta(n^{3/2})$; (2) leaves a gap in the secondary order.

2. Approximate interactions, not individual cells

Fix one coset $D+L_n$, put $H_{ij}=(-1)^{D_{ij}}$, and write $a_i=(-1)^{x_i}$, $b_j=(-1)^{y_j}$. Its matrices have entries $$B_{ij}=(1-H_{ij}a_ib_j)/2. \tag{5}$$ For a real matrix $R$, use the unnormalized cut norm $$\|R\|_\square=\max_{I,J\subseteq[n]} \left|\sum_{i\in I,j\in J}R_{ij}\right|.$$ For every $0<\varepsilon\le1$, there are row and column partitions, each with at most $$q=2^{\lceil\varepsilon^{-2}\rceil}$$ nonempty parts, whose block-average matrix $H'$ satisfies $$H'_{ij}\in[-1,1],\qquad \|H-H'\|_\square\le\varepsilon n^2. \tag{6}$$

This is the classical weak-regularity energy argument. For completeness, start with the one-part partitions and let $H'$ be the orthogonal projection of $H$ onto their block-constant matrices. If (6) fails, choose a witness rectangle $I\times J$ and refine by its row and column sets. The new projection $H''$ satisfies $$|\langle H''-H',1_{I\times J}\rangle|>\varepsilon n^2, \qquad \|H''-H'\|_F^2>\varepsilon^2n^2.$$ The first identity uses orthogonality of the new residual to the witness; the second uses Cauchy-Schwarz and $|I||J|\le n^2$. Squared projection norm increases by this amount, while never exceeding $\|H\|_F^2=n^2$. At most $\lceil\varepsilon^{-2}\rceil$ refinements are needed, each doubling the number of parts on each side. Block averages remain in $[-1,1]$.

Replacing $H$ by $H'$ changes every score in (5) by at most $6\varepsilon n^2$, simultaneously for all queries and label choices. Indeed a signed product $a_ib_j$, restricted to any rectangle, splits into four signed rectangles and so has residual sum at most $4\|H-H'\|_\square$. Expanding $(2u_iv_j-1)a_ib_j$ gives the bound $(2\cdot4+4)/2=6$. This controls interaction error even when the two matrices disagree on a positive fraction of their entries.

3. Balanced query classes cannot produce positive score

Consider a block on which $H'$ has value $h\in[-1,1]$. Suppose exactly half of its row mass has $u=1$, and half of its column mass has $v=1$. Fractional masses are allowed in this argument. Let $\alpha_0,\alpha_1\in[-1,1]$ be the mean row signs conditional on $u$, and $\beta_0,\beta_1$ the corresponding column means. The mean score per cell is $$-\frac14-\frac h8 T,\qquad T=\alpha_1\beta_1-\alpha_1\beta_0 -\alpha_0\beta_1-\alpha_0\beta_0. \tag{7}$$ But $$|T|\le|\beta_1-\beta_0|+|\beta_1+\beta_0|\le2.$$ Thus (7) is at most $(-1+|h|)/4\le0$. This elementary four-sign inequality is the entire balanced-block step. It retains the negative score outside the selected query rectangle.

For the actual query, let $$Z(u,v)=\sum_{I}\left|\sum_{i\in I}u_i-|I|/2\right| +\sum_{J}\left|\sum_{j\in J}v_j-|J|/2\right|. \tag{8}$$ For any chosen signs, transport the excess mass in each partition part from the overrepresented query type to the other type, retaining its sign. This changes exactly the mass counted in (8). Changing a row query type changes each incident score by at most two, because $(1-hab)/2\in[0,1]$; the same holds for a column type. Hence transport changes total score by at most $2nZ$. It preserves the total mass of every partition part. The balanced version has nonpositive score by (7), so, pointwise and uniformly over the labels, $$X_D(u,v):=\max_{B\in D+L_n}S(B;u,v) \le6\varepsilon n^2+2nZ(u,v). \tag{9}$$ This argument permits signs chosen after seeing the query. There is no independence assumption on the maximizing labels.

Every count in (8) has binomial variance $|I|/4$ or $|J|/4$. Cauchy-Schwarz therefore gives $$\mathbb EZ\le\tfrac12\sum_I\sqrt{|I|} +\tfrac12\sum_J\sqrt{|J|}\le\sqrt{qn}.$$ Consequently, uniformly in the arbitrary matrix $D$, $$\mathbb EX_D\le A_n(\varepsilon):= 6\varepsilon n^2+2n^{3/2}2^{\lceil\varepsilon^{-2}\rceil/2}. \tag{10}$$ For $n\ge4$, choose $\varepsilon=\sqrt{2/\log_2n}$. Then $q\le2\sqrt n$, giving $A_n=O(n^2/\sqrt{\log n})$. Absorb the finitely many smaller values into the constant in (2).

For the union of this coset with $L_n$, use the same partitions. The latter has $H=H'=1$ and zero approximation error. Its score is also bounded by the nonnegative right-hand side of (9). This proves (3) directly, without adding two expected maxima.

4. A sublinear number of independent departures

The family $C+L_n$ is the union of $2^d$ cosets $D+L_n$. Each random variable $X_D$ satisfies (10). Changing one bit of $u$ or $v$ changes each fixed score by at most $2n$, hence changes its maximum $X_D$ by at most $2n$. The bounded-differences exponential moment bound on the $2n$ independent query bits is therefore $$\mathbb E\exp(\lambda(X_D-\mathbb EX_D)) \le\exp(\lambda^2 n^3). \tag{11}$$ For clarity, expose the bits successively. Each Doob martingale difference has conditional range length at most $2n$; the conditional Hoeffding bound contributes $\lambda^2(2n)^2/8$ to the logarithmic moment. Summing $2n$ such contributions proves (11).

The maximum is at most the logarithm of the sum of the exponentials, divided by $\lambda$. Jensen’s inequality and (11) imply $$\mathbb E\max_D X_D \le A_n+\frac{d\ln2}{\lambda}+\lambda n^3.$$ Optimizing over $\lambda>0$ gives the second term in (2); for $d=0$ use (10) directly. Finally $C\subseteq C+L_n$, so its maximum is no larger. No independence among the coset maxima is needed.

This is a useful union bound only after an entire overlapping consistent family has been controlled. A union bound over individual arbitrary codewords would lose the structural information that made (10) possible.

5. Resources, provenance and the remaining question

The fragments remain $y=Ax$ and $x=v,u^{\mathsf T}y=1$, with boundary width $b=2n$, coefficient input $N_0=\Theta(n^2)$, and fixed-shape named-CNF size $N=\Theta(n^2\log n)$, including private auxiliaries and variable names. Stored size is $S=n^2+r\le n^2+n$. Direct matrix preparation takes $O(n^2+\sum_{\ell=1}^r\operatorname{wt}(B_\ell))\le O(n^3)$ bit operations; the matching leading upper construction takes $O(n^2)$. Public generator descriptions use at most $n^3$ bits and contain no matrix-dependent information. The partitions in the proof are analytical objects, not extra private storage or a claimed efficient query algorithm.

For $d=o(n)$, unavoidable mean reads are $b^2/16-o(b^2)$, of order $N_0$ or $N/\log N$. These reads include combination and deferred answer work. No separate composition-only lower bound is asserted when answering may be postponed. No new transfer to unrestricted Turing machines, scaffolding automata, SAT algorithms or arbitrary stored bases is established.

Weak regularity and dense-matrix cut approximation are classical. See Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175-220. Their bounded-entry matrix approximation controls all submatrix sums using few cut matrices. We give the block-average energy version explicitly because preserving entries in $[-1,1]$ is needed in (7). The bounded-differences method is also classical; see the baseline discussion in Warnke, On the method of typical bounded differences. The additional content here is their application to shifted consistent advice families via the balanced four-sign calculation, followed by the explicit defect-dimension and stored-read bounds. Historical novelty is unestablished.

These are written proofs with independent mathematical review reconciled by the parent authoring agent. No formal-kernel verification is claimed. Further mechanization would not resolve the remaining quantitative gap.

The sharper question left by this argument was whether $$\sup_{D}\;\sup_{\substack{C\subseteq L_n+\langle D\rangle\\ \dim C\le n}} F(C)=O(n^{3/2}). \tag{12}$$ The subsequent contraction proof settles (12), and every fixed number of independent departures, in the secondary order. The regularity proof above is retained as the preceding argument. The unrestricted systematic conjecture, its sharp secondary coefficient and the arbitrary-basis leading constant remain unresolved.