Row-parity advice saves reads, but is not exactly optimal

Working research note, 3 October 2026.

The foundations program asks when saved work can support future computation with bounded local access and allocation. Its current test is composition: after preparing a binary matrix independently of a query, how much of the stored information must be read to answer $u^{\mathsf T}Av$?

The quadratic lower bound already establishes the optimal order when $n^2+n$ stored bits may be any injective linear encoding. The remaining question concerns the constant. Storing each row’s parity gives a better benchmark than raw entries alone: if a query selects most of a row, read its parity and the few excluded entries. The resulting mean cost is $$\frac{n^2}{4}-\frac{n^{3/2}}{2\sqrt{2\pi}}+\frac n4+O(\sqrt n).$$ Thus the quadratic order survives a saving of order $n^{3/2}$.

Could full-row advice be exactly optimal? In the model that grants advice reads for free, a two-by-two counterexample answers no. This finite example leaves the asymptotic leading constant and the best secondary term unresolved.

1. Which reads are counted?

Work over $\mathbb F_2$, with independent uniform $u,v\in\mathbb F_2^n$, including zero. In the systematic model, store every entry of $A$ and $r\le n$ parity bits $\langle A,B_\ell\rangle$, for fixed public matrices $B_1,\ldots,B_r$. Addresses and layout are public and fixed; these bits are the entire matrix-dependent initial state. There is no additional cache, metadata or pointer channel. Algorithms are deterministic and exact for every matrix and query. Local computation, allocation and query-only preparation are free; charge all observations of old bits through the final answer, including any work deferred after a composition handle.

Put $Q=uv^{\mathsf T}$, $B(z)=\sum_\ell z_\ell B_\ell$, and $C=\operatorname{span}\{B_\ell\}$. The existing support characterization gives the exact charged optimum, on every matrix: $$\tau(Q)=\min_{z\in\mathbb F_2^r} \bigl[\operatorname{wt}(Q+B(z))+\operatorname{wt}(z)\bigr]. \tag{1}$$ Each chosen parity replaces the corresponding raw-entry linear functional; the residual entries and chosen parity bits must both be read. Granting the parities free instead gives $\operatorname{dist}(Q,C)$. Hence $$\operatorname{dist}(Q,C)\le\tau(Q) \le\operatorname{dist}(Q,C)+r. \tag{2}$$ These quantities share their leading quadratic asymptotics, but are not equal. The chosen generating set can affect the charged cost.

The original model also permits an arbitrary invertible change of matrix coordinates. Its free-advice expression is $\operatorname{dist}(R^{-1}\operatorname{vec}(Q),C)$, where $R$ is public and invertible. That change need not preserve Hamming weight. A lower bound proved only for systematic storage therefore does not settle the original all-encoding question. The construction below is allowed in both.

2. The score formulation and row-parity construction

For binary matrices, using an integer inner product, $$\operatorname{wt}(Q+B)=\operatorname{wt}(Q)+\operatorname{wt}(B) -2\langle Q,B\rangle.$$ Define the score $S(B;u,v)=\sum_{ij}B_{ij}(2u_i v_j-1)$. Since $\mathbb E\operatorname{wt}(Q)=n^2/4$, $$\mathbb E\operatorname{dist}(Q,C) =\frac{n^2}{4}-\mathbb E\max_{B\in C}S(B;u,v). \tag{3}$$ For a sequence of codes, retaining the leading constant $1/4$ is equivalent to this expected maximum being $o(n^2)$.

Let $C_{\rm row}=\{y\mathbf1^{\mathsf T}:y\in\mathbb F_2^n\}$. Its $n$ full-row generators have disjoint supports. With $K=\operatorname{wt}(v)$, a selected row contributes score $2K-n$, while an unselected row contributes $-n$. Therefore $$\max_{B\in C_{\rm row}}S(B;u,v) =\operatorname{wt}(u)(2K-n)_+.$$ Writing $F_n$ for its free-advice mean gives $$\begin{aligned} F_n&=\frac n2\mathbb E\min(K,n-K)\\ &=\frac{n^2}{4} -\frac{n^2}{2^{n+1}}\binom{n-1}{\lfloor n/2\rfloor}, \qquad K\sim\operatorname{Bin}(n,1/2). \tag{4} \end{aligned}$$ For the binomial identity, use $(2k-n)\binom nk=n[\binom{n-1}{k-1}-\binom{n-1}{k}]$ and telescope over $k>n/2$.

When row-parity reads are charged, a selected row costs $\min(K,n-K+1)$. Disjoint row supports make these choices independent in (1), so this is the encoding’s exact optimum, including adaptive algorithms. Its mean $Q_n$ is $$\begin{aligned} Q_n&=\frac n2\mathbb E\min(K,n-K+1)\\ &=F_n+\frac n2\Pr(K>n/2)\\ &=\frac{n^2}{4}-\frac{n^{3/2}}{2\sqrt{2\pi}} +\frac n4+O(\sqrt n). \tag{5} \end{aligned}$$ The second equality holds for odd sizes too: the difference of the two minima is exactly the indicator of $K>n/2$. Stirling’s formula gives $F_n=n^2/4-n^{3/2}/(2\sqrt{2\pi})+O(\sqrt n)$.

Storage is $S=n^2+n$ bits and matrix preparation costs $O(n^2)$ Boolean operations. Computing the query weights takes $O(n)$ query-only work. The compact affine fragments remain $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$: boundary width $b=2n$, coefficient description size $N_0=\Theta(n^2)$, and the established fixed-shape named CNF encoding has total size $N=\Theta(n^2\log n)$, including auxiliary variables. The saved reads have order $b^{3/2}$, or $(N/\log N)^{3/4}$ along this family. The total mean remains quadratic in $b$. A universal lower bound $n^2/4-o(n^{3/2})$ is already excluded by this construction; a lower bound $(1/4-o(1))n^2$ remains possible.

3. A complete two-by-two counterexample

Let $E_{11}$ have one entry equal to one and let $J_2$ be all ones. The dimension-two code $$C=\operatorname{span}\{E_{11},J_2\} =\{0,E_{11},J_2+E_{11},J_2\}$$ beats full-row advice in free mean distance. The sixteen equally likely pairs $(u,v)$ can be classified completely:

The singleton $E_{11}$ belongs to the code; the other three singletons have distance one. Each two-entry row or column has distance one, using $E_{11}$ or its complement. Thus $$\mathbb E\operatorname{dist}(uv^{\mathsf T},C)=\frac7{16} <\frac12=\mathbb E\operatorname{dist}(uv^{\mathsf T},C_{\rm row}).$$ Equivalently its mean saving is $9/16$, exceeding the row code’s $1/2$. This refutes the proposed exact inequality for every code of dimension at most $n$. It does not assert an improvement in charged cost or refute an asymptotic conjecture.

4. Why a generator search can miss an improvement

An explicit even-size family also explains the finite search issue. For even $n\ge2$, let $C_n$ contain matrices $B(y)$ with $$B(y)_{ij}=y_i\quad\text{except that}\quad B(y)_{1n}=y_2+\cdots+y_n\pmod2.$$ It has dimension $n$: the unchanged rows recover $y_2,\ldots,y_n$, and the first $n-1$ entries of row one recover $y_1$. Put $t=v_n$, $K=\operatorname{wt}(v)$, and $P=y_2+\cdots+y_n\pmod2$. Its score is $$y_1[2u_1(K-t)-(n-1)] +\sum_{i=2}^n y_i(2u_iK-n)+(2u_1t-1)P. \tag{6}$$ If $K<n/2$, every row coefficient is negative enough that the maximum is zero. If $K>n/2$, the coefficients for rows two through $n$ have magnitude at least two. Changing their maximizing choices costs at least two, while changing $P$ can help by at most one. Thus $y_i=u_i$ for $i\ge2$; the first coefficient is maximized by $y_1=u_1$. Averaging over $u$ gives a difference $-t/2$ from the row-code maximum.

At $K=n/2$, active rows two through $n$ have coefficient zero. Their parity can be chosen freely whenever one of their $u_i$’s is one. For $t=0$, the first row then gives mean gain $1/2$. For $t=1$, gain one occurs exactly when $u_1=1$ and at least one other $u_i=1$, with mean $1/2-2^{-n}$. In full:

Each balanced case has probability $2^{-n-1}\binom n{n/2}$, while $\Pr(K>n/2,t=1)=1/4$. Consequently the mean excess saving is exactly $$\Delta_n=\frac12(1-2^{-n})2^{-n}\binom n{n/2}-\frac18. \tag{7}$$ At $n=4$, the mean distance is $627/256$, below the full-row value $640/256$. The excess is also positive at $n=2,6,8$, but $\Delta_n\to-1/8$. This family therefore supplies finite counterexamples, not an asymptotic improvement over full-row advice.

Let $R_i$ denote full row $i$ and $E=E_{1n}$. Starting with the usual row-code generators $(R_1,\ldots,R_n)$, constructing $C_n$ requires changing that entry in every generator: the new generators are $R_i+E$. But the same row code has basis $(R_1,R_1+R_2,\ldots,R_1+R_n)$. Changing the entry only in its first generator gives $C_n$. Stability under single-entry moves in one chosen generator basis does not establish optimality among codes.

5. What remains to prove

The exact row-code extremality conjecture is false. A weaker, consequential systematic conjecture is $$\sup_{\substack{C\text{ linear}\\\dim C\le n}} \mathbb E\max_{B\in C}S(B;u,v)=O(n^{3/2}). \tag{8}$$ Together with (4), it would give optimal systematic mean $n^2/4-\Theta(n^{3/2})$, also when advice reads are charged by (2). The sharp coefficient of that secondary term is a further open question. For arbitrary encoded bases, even the leading constant remains unresolved by these calculations.

The existing summed-query proof settles quadratic order. Optimizing its integer parameter only modestly improves its positive constant; its division by the number of queries cannot provide the desired sharp estimate. The remaining work must control one query’s alignment with an entire fixed advice space, or exhibit a stronger encoding. No new unrestricted SAT, Turing-machine or scaffolding-automaton consequence follows from this note.

A subsequent score analysis proves that every fixed matrix has expected positive score at most $\sqrt{2\ln2}\sqrt n$. It also refutes a proposed way to sum that estimate over dimensions: some single code extensions gain order $\sqrt n\log n$, even from dimension $n-1$ to dimension $n$. Neither result settles (8).

A finite separation between systematic and arbitrary bases

At $n=2$, the minimum free mean distance over all invertible stored bases and dimension-at-most-two advice codes is $6/16$; restricting the stored basis to the raw entries gives $7/16$. Here is an explicit corrected witness. List coordinates as $(00,01,10,11)$, with integer masks read least significant bit first. Store $$w=(A_{00}+A_{11},A_{01},A_{10},A_{11}), \qquad C=\{0,7,10,13\}.$$ If $w=L\operatorname{vec}(A)$, then query coefficients transform by $L^{-\mathsf T}$, so here $$q'=(q_{00},q_{01},q_{10},q_{00}+q_{11}), \qquad q=\operatorname{vec}(uv^{\mathsf T}).$$ The nine nonzero rank-one queries become the masks $9,2,11,4,8,12,13,10,7$. Three are in $C$, and the remaining six have distance one. The zero query occurs seven times, giving mean $6/16$.

This is also a lower bound for every invertible basis: the nine nonzero queries stay distinct, while a dimension-two code contains at most three nonzero vectors. At least six query distances are therefore at least one. For systematic storage, total distance six would require all three nonzero codewords to be rank one. A plane consisting of rank-one matrices must have a common left factor or a common right factor: otherwise the sum of two generators has rank two. At size two, each of these six planes has total distance eight, as is checked directly by fixing its nonzero common factor. Every other plane misses at least seven of the nine queries. Section 3 attains total distance seven.

The witness originally proposed in the relayed suggestions used the transposed storage shear, $(A_{00},A_{01},A_{10},A_{00}+A_{11})$, with the same code. That pair gives $8/16$, not $6/16$. Keeping that storage but replacing the code by $\{0,3,13,14\}$ is an alternative repair. The distinction is between the storage transformation and its inverse transpose on queries. An exact checker and output enumerate all invertible bases and all codes of dimension at most two, corroborating the elementary minima above.

Disjoint copies on $n/2$ diagonal two-by-two blocks give exactly $n^2/4-5n/16$ free mean distance for even $n$, with advice dimension $n$. Their saving is only linear. This does not prove that arbitrary bases can improve the systematic optimum by only $O(n)$; no such general bound has been established. The reported size-three shear search is not needed for these conclusions and has not been independently reproduced here.

6. Provenance and verification

Joshua Gay relayed Grok-generated suggestions containing the score formulation, full-row construction and $n^{3/2}$ saving, and directed attention away from optimizing summed-query constants. The proposed exact extremal conjecture prompted the counterexamples here. The later basis-change suggestion was checked with the storage/query transpose correction described above. The identities and counterexamples have elementary written proofs; historical novelty is not established. The distinction between systematic raw storage with free redundancy and other models also appears explicitly in Ramamoorthy and Rashtchian, Sections 1.1 and 1.3.

An exact checker enumerates every query and codeword for the specified codes at $n=2,4$, and verifies the conditional table and (7) using rational arithmetic. Its recorded output is reproducible with Python’s standard library. These finite certificates corroborate the examples; the even-size formula rests on the written case proof. Neither the experiments nor independent agent reviews prove (8), and no proof-assistant verification is claimed.