Two stages of averaging control arbitrary dense advice patterns

Working research note, 3 October 2026.

How much of separately prepared work must be read when a matrix meets a query? This is our current test of the broader FPRD goal: understanding representations maintained by finite rules, bounded local access and bounded allocation.

The preceding result showed that adding one arbitrary parity pattern to a rectangle-consistent family preserves the leading mean read cost $n^2/4$. Its approximation error left open the scale of the saving. A direct argument now closes that gap: any fixed number of arbitrary additional patterns still permits only $O(n^{3/2})$ mean saving, within the specified systematic storage model. Row parities attain this saving order.

The proof averages over the two independently chosen query vectors in turn. At each stage, classical Rademacher contraction controls the benefit of choosing a pattern after seeing the query. No partition approximation is needed. This resolves the fixed-defect case, not the conjecture for all linear codes with $n$ advice bits.

1. Precise result

For independent uniform $u,v\in\mathbb F_2^n$, put $$S(B;u,v)=\sum_{ij}B_{ij}(2u_iv_j-1),\quad L_n=\{B:B_{ij}=x_i\oplus y_j\},\quad X_D=\max_{B\in D+L_n}S(B;u,v).$$ The arbitrary binary matrix $D$ is fixed independently of the query.

Theorem 1. For every $n\ge1$ and every $D$, $$\mathbb E X_D\le n^{3/2}. \tag{1}$$ The coset need not contain zero; its maximum may be negative on some queries. The statement concerns its mean, not its positive part.

For a binary linear matrix code $C$, define $$F(C)=\mathbb E\max_{B\in C}S(B;u,v),\qquad d=\dim((C+L_n)/L_n)=\dim C-\dim(C\cap L_n).$$

Corollary 2. Uniformly over such codes, $$F(C)\le n^{3/2}\bigl(1+2\sqrt{d\ln2}\bigr). \tag{2}$$ Thus a bounded number of independent departures from the four-cell rule gives $F(C)=O(n^{3/2})$, even if each departure affects every cell. The estimate also quantifies growing $d$, and implies $F(C)=o(n^2)$ when $d=o(n)$.

For storage, restrict to $r=\dim C\le n$. Store the $n^2$ raw entries of $A$ and the $r$ bits $\langle A,B_\ell\rangle$ for a fixed public basis of $C$. The exact minimum-support result 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{3}$$ Here $\tau_C$ counts advice reads too. Consequently, for each fixed integer $d_0\ge0$, the optimum over admissible codes with $d\le d_0$ has mean cost $$n^2/4-\Theta(n^{3/2}), \tag{4}$$ charged or free. The lower bound follows from (2), and the full-row code has $d=0$, dimension $n$, and saving $\Theta(n^{3/2})$. Equation (4) is an optimum over a class; individual codes can save less. The sharp secondary coefficient is not determined.

2. The classical scalar contraction inequality

If $T$ is a finite subset of $\mathbb R^m$, $\varepsilon_i$ are independent uniform signs, and each $\phi_i$ is 1-Lipschitz, then $$\mathbb E\max_{t\in T}\sum_i\varepsilon_i\phi_i(t_i) \le\mathbb E\max_{t\in T}\sum_i\varepsilon_i t_i. \tag{5}$$ There is no absolute value outside the sum or maximum. This convention allows the constant one used below.

Here is the finite-coordinate proof. With all other signs fixed, write their contribution as $A_t$ and the current coordinate as $z_t$. Averaging its sign gives $$\tfrac12\max_{s,t}\{A_s+A_t+\phi(z_s)-\phi(z_t)\} \le\tfrac12\max_{s,t}\{A_s+A_t+|z_s-z_t|\} =\tfrac12\max_{s,t}\{A_s+A_t+z_s-z_t\}.$$ The equality follows by exchanging $s,t$. The final expression is the sign average with $\phi$ replaced by the identity. Repeat for each coordinate and average the remaining signs. We will use $\phi(z)=|z|$.

3. Switch signs to expose the exact score

Set $H_{ij}=(-1)^{D_{ij}}$, $W_{ij}=2u_iv_j-1$, and let all unqualified vectors $a,b,c$ below range over $\{-1,1\}^n$. Members of $D+L_n$ have entries $(1-H_{ij}a_ib_j)/2$. Define $$M(u,v)=\max_{a,b}\sum_{ij}H_{ij}W_{ij}a_ib_j.$$ Negating all row signs negates this bilinear form. Hence its minimum is $-M$, and the exact identity is $$X_D=\tfrac12\sum_{ij}W_{ij}+\tfrac12 M, \qquad \mathbb EX_D=-n^2/4+\tfrac12\mathbb EM. \tag{6}$$ We retain this negative term throughout.

For independent uniform signs $\varepsilon,\delta$, abbreviate $$R_{\rm col}=\mathbb E\|H^{\mathsf T}\varepsilon\|_1, \qquad R_{\rm row}=\mathbb E\|H\delta\|_1.$$ Every coordinate sum has second moment $n$, so $$R_{\rm col}\le n^{3/2},\qquad R_{\rm row}\le n^{3/2}. \tag{7}$$

4. First average: the row-query bits

Fix $v$, and let $\delta_j=1-2v_j$. Optimizing the row signs in $M$ first gives a sum of absolute row values. For a fixed $b$, when $u_i=0$ its absolute value is $|(Hb)_i|$; when $u_i=1$ it is $|(H\operatorname{diag}(\delta)b)_i|$. Thus, with $\varepsilon_i=2u_i-1$, its mean part is $$\tfrac12\bigl(\|Hb\|_1+ \|H\operatorname{diag}(\delta)b\|_1\bigr),$$ and its centered part is $$\tfrac12\sum_i\varepsilon_i \bigl(|(H\operatorname{diag}(\delta)b)_i|-|(Hb)_i|\bigr).$$ Use maximum-of-sum at most sum-of-maxima on these parts. Each centered absolute-value process is bounded by (5). Its linear sign supremum is $\|H^{\mathsf T}\varepsilon\|_1$; multiplication of $b$ by the fixed sign vector $\delta$ merely permutes its possible values. The minus sign in the second process has the same sign distribution. Therefore $$\mathbb E_u M(u,v)\le\tfrac12 Z(\delta)+R_{\rm col}, \quad Z(\delta)=\max_b\bigl(\|Hb\|_1+ \|H\operatorname{diag}(\delta)b\|_1\bigr). \tag{8}$$ This explicitly pays for a maximizing $b$ that depends on $u$; we have not interchanged expectation and maximum.

5. Second average: the column-query bits

Dualizing both norms in $Z$, then optimizing $b$, gives $$Z(\delta)=\max_{a,c}\sum_j|p_j+\delta_j q_j|, \qquad p=H^{\mathsf T}a,\quad q=H^{\mathsf T}c. \tag{9}$$ For any fixed $p,q$, the mean of each summand is $$(|p_j+q_j|+|p_j-q_j|)/2=\max(|p_j|,|q_j|)\le n.$$ Its centered part is $\delta_j(|p_j+q_j|-|p_j-q_j|)/2$. As before, split the two suprema and apply (5). For either choice of sign, $$\mathbb E_\delta\max_{a,c}\sum_j\delta_j|[H^{\mathsf T}(a\pm c)]_j| \le\mathbb E_\delta\max_{a,c}(a\pm c)^{\mathsf T}H\delta =2R_{\rm row}.$$ The half factors on the two centered processes give $$\mathbb E Z\le n^2+2R_{\rm row}. \tag{10}$$ Combining (8), (10), and (6), $$\mathbb EM\le n^2/2+R_{\rm row}+R_{\rm col}, \qquad \mathbb EX_D\le(R_{\rm row}+R_{\rm col})/2\le n^{3/2}.$$ This proves Theorem 1 uniformly in the arbitrary dense pattern.

6. Several independent departures

The containing family $C+L_n$ is a union of $2^d$ cosets. Changing one query bit changes any fixed score by at most $2n$, and therefore changes a coset maximum by at most $2n$. The classical bounded-differences exponential moment bound gives $$\mathbb E e^{\lambda(X_D-\mathbb EX_D)}\le e^{\lambda^2n^3}.$$ One way to see the constant is to expose the $2n$ query bits and apply conditional Hoeffding to martingale differences of range length $2n$. The logarithmic moment is at most $2n\lambda^2(2n)^2/8$. Log-sum-exp, Theorem 1 and Jensen now give $$F(C)\le\mathbb E\max_D X_D \le n^{3/2}+\frac{d\ln2}{\lambda}+\lambda n^3.$$ Optimize $\lambda>0$; handle $d=0$ with Theorem 1 directly. This proves (2). No independence between the coset maxima is assumed, and no positive-part bound for an individual coset is required.

7. Exact resources, provenance and what remains

We retain the established contract. The affine fragments are $y=Ax$ and $x=v,u^{\mathsf T}y=1$, with boundary $b=2n$, coefficient description $N_0=\Theta(n^2)$, and fixed-shape named-CNF description $N=\Theta(n^2\log n)$, including variable names, clauses and private auxiliary variables. Systematic storage has $S=n^2+r\le n^2+n$ immutable bits in a public fixed layout, with no other matrix-dependent initialization, metadata, address or pointer channel. The encoding is fixed independently of $A,u,v$.

An exact deterministic algorithm must answer correctly on every matrix and query. Every old-bit observation costs one read, through combination and any deferred query work until the final one-bit answer. Local computation, query-only preparation and allocation are free. Equation (3) gives a read bound on every stored $A$; attainability permits unrestricted query-only minimum-support search and is not a fast-runtime assertion.

Direct matrix preparation costs $O(n^2+\sum_\ell\operatorname{wt}(B_\ell))\le O(n^3)$. The row construction prepares in $O(n^2)$; public encoding coefficients use at most $n^3$ bits independent of $A$. Full $L_n$ and its cosets are analytical relaxations, not advice within the dimension budget. For fixed $d_0$, the class optimum is $b^2/16-\Theta(b^{3/2})$, of leading order $N_0$ or $N/\log N$, not quadratic in complete input size. No unrestricted SAT, Turing-machine or scaffolding-automaton lower bound or new machine transfer is inferred.

Scalar Rademacher contraction is classical, associated with Ledoux and Talagrand. The exact no-outer-absolute version used here appears with proof in Mohri and Munoz Medina, Learning Algorithms for Second-Price Auctions with Reserve, JMLR 17 (2016), Appendix A, Lemma 14. We reproduced the finite argument to make its convention and constant explicit. The last maximum bound reuses classical bounded differences as in the preceding note. The contribution here is the two successive conditioning/contraction steps for shifted consistent patterns and the resulting composition bound. Historical novelty is unestablished; no new contraction principle is claimed.

The proof is a complete written argument with independent mathematical review reconciled by the parent authoring agent. It is not formally verified. No finite experiment is used to prove its universal claim. Mechanization is deferred because it would not resolve the remaining general-code question.

The fixed-number-of-defects question is now closed in secondary order. Do not treat each new fixed value of $d$ as another research problem. The next issue is the $\sqrt d$ loss when the number of independent departures grows. At $d=\Theta(n)$, (2) permits quadratic saving and therefore does not settle the unrestricted systematic conjecture $F(C)=O(n^{3/2})$ for $\dim C\le n$. The coset maximum argument uses only the number of representatives, losing their linear relations. A consequential next step is to exploit those relations or construct a linear family showing that a growing saving factor really occurs. The sharp secondary coefficient, arbitrary-basis leading constant and connection to dynamically maintained representations remain separate.