One advice matrix has a small score; one added dimension need not

Working research note, 3 October 2026.

The foundations program studies representations of future computation that can be maintained with bounded local access and allocation. The present composition question asks how much stored information must be read when a separately prepared binary matrix meets a query $u^{\mathsf T}Av$.

The row-parity note reduces one remaining systematic-storage question to the score $$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. The open conjecture is $F(C)=O(n^{3/2})$ for every linear matrix code of dimension at most $n$. Full-row advice attains this order of saving over raw storage.

The subsequent local rectangle-consistency note proves the total bound for an overlapping family defined by a four-cell rule, and quantifies a common repair set. It also computes the actual linear saving of the cut code that invalidates a drift-free fluctuation bound below.

Two results separate an individual matrix from an entire linear family:

• Every fixed matrix has expected positive score $O(\sqrt n)$. A proof below gives the stronger bound $\sqrt{2\ln2}\sqrt{\Delta(B)}$, where $\Delta(B)$ is its maximum row or column weight.
• It is false that every additional code dimension increases $F$ by only $O(\sqrt n)$. Explicit nested codes have a single increment of order $\sqrt n\log n$, even from dimension $n-1$ to dimension $n$.

The second result does not disprove the open conjecture. It rules out a proposed way of proving it by bounding every step of an arbitrary basis flag.

1. Scope of the score

Store the raw $n\times n$ binary matrix and at most $n$ fixed public linear parities, with no other matrix-dependent initial state. Addresses and layout are fixed and public; storage is immutable. Queries are deterministic and exact for every matrix. Charge every old-bit observation through the answer, including deferred work. Query-only computation, local computation and allocation are free in this model.

When the parity reads are free, the exact optimal cost is $\operatorname{dist}(uv^{\mathsf T},C)$, so its mean is $n^2/4-F(C)$. Charging the parity reads changes the optimum by at most $\dim C\le n$. Thus the proposed total bound would settle the systematic secondary order, but the increments studied below are increments of the free-advice score, not increments of charged query cost.

The underlying fragments remain $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$. They have boundary width $b=2n$, coefficient description size $N_0=\Theta(n^2)$, and fixed-shape named-CNF size $N=\Theta(n^2\log n)$, including private auxiliary variables. The storage budget is $S\le n^2+n$ bits. These restrictions do not include arbitrary changes of stored basis; that larger model remains separately identified in the row-parity note. No unrestricted SAT or machine lower bound follows here.

2. A bound for every fixed matrix

Proposition. Let $B$ be any fixed binary rectangular matrix and let $u,v$ be independent uniform binary vectors of the corresponding sizes. Let $\Delta$ be the largest row or column weight of $B$. Then $$\mathbb E(S(B;u,v))_+\le\sqrt{2\ln2}\sqrt\Delta. \tag{1}$$ In particular $\Delta\le n$ for an $n\times n$ matrix. The order $\sqrt n$ cannot be improved: a single full row has expectation $\sqrt{n/(8\pi)}+O(n^{-1/2})$. No optimal constant is asserted in (1).

Proof. The zero matrix is immediate. Otherwise put $m=\operatorname{wt}(B)>0$. Split the support into the four rectangles determined by $U=\operatorname{supp}(u)$ and $V=\operatorname{supp}(v)$, and call their sizes $a,b,c,d$, with $a$ in $U\times V$ and $d$ in $U^c\times V^c$. Then $$S=2a-m=a-b-c-d.$$ Introduce independent signs $\varepsilon=2u-\mathbf1$ and $\delta=2v-\mathbf1$. Their bilinear sum is $$Z=\varepsilon^{\mathsf T}B\delta=a-b-c+d,\qquad \mathbb EZ^2=m. \tag{2}$$ The last equality follows by expanding the square: different matrix entries have zero cross expectation.

Consider all four possible quadrant excesses at once: $$T=(2a-m)_++(2b-m)_++(2c-m)_++(2d-m)_+.$$ At most one is positive, since two quadrants cannot both contain more than half the support. A diagonal excess is at most $Z$, and an off-diagonal excess is at most $-Z$. For example $2a-m=Z-2d$. Consequently $$T\le |Z|,\quad \mathbb ET=4\mathbb ES_+,\quad \Pr(T>0)=4\Pr(S>0). \tag{3}$$ The equalities use invariance under complementing either random vector.

Write $r_i,c_j$ for the row and column weights. Changing one input bit changes $S$ by at most $2r_i$ or $2c_j$, and $$4\sum_i r_i^2+4\sum_j c_j^2\le8\Delta m.$$ Since $\mathbb ES=-m/2$, the classical bounded-differences inequality gives $$p:=\Pr(S>0)\le \exp[-m/(16\Delta)]. \tag{4}$$ All its hypotheses hold here: the input bits are independent, and the displayed change bounds hold for every input. Combining (2)–(4) with Cauchy–Schwarz yields $$\mathbb ES_+\le\frac14 \sqrt{m\min\{1,4e^{-m/(16\Delta)}\}}. \tag{5}$$ As a function of nonnegative real $m$, the expression inside the square root increases to the breakpoint $m=16\Delta\ln4$, and decreases afterward: the exponential branch is already past its maximum at $m=16\Delta$. Substitution gives (1). $\square$

The useful step is the envelope $T\le|Z|$. The sign sum has second moment $m$, whereas a direct variance bound for $S$ can be of order $nm$. The tail estimate alone misses this gain.

If a code has a basis $B_1,\ldots,B_r$ with pairwise disjoint supports, then choices add without XOR cancellations, pointwise. Therefore $$F(C)=\sum_{\ell=1}^r\mathbb ES(B_\ell)_+ \le\sqrt{2\ln2}\sum_{\ell=1}^r\sqrt{\Delta(B_\ell)} \le\sqrt{2\ln2}\,r\sqrt n. \tag{6}$$ This proves the desired order for that subclass. An arbitrary linear code need not possess such a basis.

3. A single dimension can unlock a larger saving

For each integer $k\ge2$, set $r=2^k$ and $n=kr$. Partition the rows into $r$ groups of $k$ rows. Let $G_j$ consist of ones on all $n$ columns of group $j$, and zeros elsewhere. Define $$E=\operatorname{span}\{G_1,\ldots,G_r\},\qquad C=\left\{\sum_j z_jG_j:\sum_j z_j=0\pmod2\right\}. \tag{7}$$ Disjoint supports give dimensions $r$ and $r-1$, respectively, and $E=C+\langle G_1\rangle$. The smaller code permits only an even number of selected row groups.

Let $K=\operatorname{wt}(v)$, $A=2K-n$, and let $T_j$ count the active $u$-rows in group $j$. Choosing that group’s generator contributes $$a_j=2KT_j-kn=T_jA-n(k-T_j). \tag{8}$$ The $T_j$ are independent $\operatorname{Bin}(k,1/2)$ variables. The number $M$ of fully active groups consequently has distribution $\operatorname{Bin}(r,1/r)$, independently of $A$, with $$q_r:=\Pr(M\text{ odd}) =\frac{1-(1-2/r)^r}{2}\longrightarrow\frac{1-e^{-2}}2. \tag{9}$$

When $0<A\le n/(2k)$, every fully active group has score $kA$, and every other group has score at most $-n/2$. The unrestricted code chooses all $M$ positive groups. If $M$ is even, this choice already lies in $C$. If $M$ is odd, enforcing even parity requires an odd number of flips. Dropping one positive group costs $kA\le n/2$; adding a negative group costs at least $n/2$. Thus the exact difference of the two maxima is $kA$ for odd $M$, and zero otherwise. For $A\le0$, every group score is nonpositive and both maxima are zero.

The Rademacher tail bound gives $\Pr(|A|>n/(2k))\le2e^{-n/(8k^2)}$. It follows directly from $\mathbb Ee^{tA}=(\cosh t)^n\le e^{nt^2/2}$ and Markov’s inequality. Since all score maxima lie between zero and $n^2$, $$F(E)-F(C)=q_r k\mathbb EA_+ +O(n^2e^{-n/(8k^2)}). \tag{10}$$ The binomial identity in the row-parity note gives $$\mathbb EA_+=n2^{-n}\binom{n-1}{\lfloor n/2\rfloor} =\sqrt{n/(2\pi)}+O(n^{-1/2}).$$ As $n=k2^k$ and $k/\log_2 n\to1$, (10) proves $$F(E)-F(C)= \left(\frac{1-e^{-2}}{2\sqrt{2\pi}}+o(1)\right) \sqrt n\log_2 n. \tag{11}$$ This disproves a uniform $O(\sqrt n)$ bound on every increment.

The entire larger code still has $F(E)=(1/\sqrt{2\pi}+o(1))k\sqrt n$, by the same typical-event calculation: its maximum there is $MkA_+$ and $\mathbb EM=1$. That is much smaller than $n^{3/2}$. The obstruction is a constraint that postpones useful choices until one final direction removes it, not a counterexample to the total-score conjecture. Indeed, adding the disjoint generators one at a time gives this same code an inexpensive flag.

4. The obstruction persists at the full dimension budget

In each group, take the first-column cells of its first $k-1$ rows. Let $D$ be the span of the corresponding $r(k-1)$ singleton matrices. Put $E'=E+D$ and $C'=C+D$. Each $G_j$ has a nonzero support outside those cells, so $$\dim E'=n,\quad \dim C'=n-1,\quad C'+\langle G_1\rangle=E'.$$ For each query, the singleton cells can be optimized separately in either code; their common contribution cancels in the difference. Remove them from the group supports. Each residual group score differs from (8) by at most $k-1$. A fully active group now has the common score $$g(v)=kA-(k-1)(2v_1-1).$$ On $|A|\le n/(4k)$, every other group has residual score at most $-3n/4+k-1\le-n/2$, while $g(v)_+\le n/4+k-1\le n/2$. The parity argument therefore gives the exact difference $g(v)_+\mathbf1_{\{M\text{ odd}\}}$. Using $|g(v)_+-kA_+|\le k-1$ and the same tail bound, $$F(E')-F(C')=q_r k\mathbb EA_++O(k) +O(n^2e^{-n/(32k^2)}).$$ Thus (11) holds even for the final increment $n-1\to n$.

These are admissible public parity spaces with at most $n$ extra bits. Their parities can be prepared in $O(n^2)$ Boolean operations: first compute the disjoint group parities, then their required pairwise sums and the singleton copies. Their explicit dense generator descriptions take at most $O(n^3)$ bits, are fixed independently of $A$, and convey no query-dependent information. Padding with free singleton advice is legitimate in the score model, but it supplies no corresponding charged marginal-gain claim. In boundary units the free-score increment is $\Theta(\sqrt b\log b)$; along the named-CNF family it is $\Theta((N/\log N)^{1/4}\log N)$.

5. What this resolves

The single-matrix estimate is now a written theorem, and the universal per-dimension square-root estimate is refuted. The original systematic conjecture (8) remains open. A proof must control the whole code, or justify an amortized choice of directions; it cannot charge every affine-coset comparison the same $O(\sqrt n)$ amount. No conclusion is established about the sharp secondary coefficient or the leading constant for arbitrary encoded bases.

The proposed single-matrix estimate and increment approach appeared in Grok-generated suggestions relayed by Joshua Gay. The proofs and counterexample here were checked against their exact quantifiers. The probabilistic input to (4) is classical McDiarmid bounded differences, stated with these hypotheses as Theorem 1 of Warnke, On the method of typical bounded differences. The remaining ingredients are elementary sign orthogonality, binomial parity, and Stirling asymptotics. Historical novelty is unestablished; these are research notes, with no proof-assistant verification claimed.

An exact checker checks the quadrant identities for all matrices through size three and the two increment constructions at $n=8$. Its recorded output is finite corroboration. The unrestricted estimates and asymptotic obstruction rest on the written proofs above.