Coupled pieces: an average composition lower bound

Working research note, 2 October 2026.

Overview

Suppose a binary matrix $A$ is stored before the query vectors $u,v$ are known. Later, the query asks for the single parity $u^{\mathsf T}Av$. As in the preceding expansion theorem, the representation may choose any invertible matrix coordinates and add only $n$ linear checksum bits. This note asks what happens when those checksum directions fall into several interacting groups rather than one global group.

Think of two groups of parity checks. Each group may spread every local change across many stored positions, yet the two resulting parity patterns might be identical. Changing both groups together would then cancel completely. The joint hypothesis below rules out that cancellation quantitatively. It still allows the groups to share stored coordinates, so the representation need not split into independent blocks.

Under this condition, every exact algorithm needs $\Omega(n^2)$ reads on average over $u,v$, for every fixed stored matrix and every invertible choice of matrix coordinates. The proof combines average costs without paying an extra factor for the number of groups. It also permits a controlled set of exceptional coordinates, with an explicit loss in the bound.

The result settles this block-accounting question, not the general problem. The cancellation example shows why expansion of each group separately is insufficient, and no decomposition theorem for arbitrary representations is proved. The unrestricted quadratic conjecture remains unresolved, and novelty has not been established.

1. Model and checkable hypothesis

Over $\mathbb F_2$, the two constraint fragments are $y=Ax$ and $x=v,\ u^{\mathsf T}y=1$, where $A$ is $n$-by-$n$. Their compatibility is $u^{\mathsf T}Av$. Put $d=n^2$. Independently of the future query, store

$$w=R^{\mathsf T}\operatorname{vec}(A),\qquad Hw, \quad R\in\mathrm{GL}(d,2),\quad H\in\mathbb F_2^{n\times d}.$$

These $S=d+n$ bits are all matrix-dependent initial information. The encoding, addresses and algorithm are public and input-independent. There is no hidden raw copy, metadata or prior-query cache. Old storage is immutable. Query preparation depending only on $u,v$, local computation and allocation are free. The deterministic algorithm must answer exactly for every $A,u,v$, with adaptive reads allowed. Charge reads from composition through the final answer, including deferred work.

Choose a public set $J\subseteq[d]$ of retained coordinates, with $g=|J|=d-h$, and write $H_0=H_{*,J}$. The other $h$ columns of $H$ are unrestricted. Partition the $n$ message coordinates into nonempty sets $I_1,\ldots,I_k$, of sizes $m_j$. Assume

$$H_0^{\mathsf T}1_{I_j}=0\quad\text{for every }j, \tag{1}$$

and, for positive numbers $\lambda_j$,

$$\operatorname{wt}(H_0^{\mathsf T}x) \ge\sum_{j=1}^k\lambda_j \min\{\operatorname{wt}(x_{I_j}),m_j-\operatorname{wt}(x_{I_j})\} \quad\text{for every }x\in\mathbb F_2^n. \tag{2}$$

Let $\Delta_j$ be the maximum row weight in $H_0$ among rows in $I_j$, and put $\kappa=\max_j\Delta_j/\lambda_j$. Equation (1) allows a whole block to be complemented without changing its contribution. Equation (2) says those are the only invisible changes, and bounds how much a visible change can be concealed by cancellation.

These are hypotheses about finite public matrices, not about query algorithms. Given $J$, the partition and the weights, check (1), row weights and (2) directly; the last check can enumerate $2^n$ vectors. No polynomial-time certification or discovery of a suitable partition is claimed. Equations (1)-(2) imply

$$\ker H_0^{\mathsf T}=\operatorname{span}\{1_{I_1},\ldots,1_{I_k}\}, \qquad\operatorname{rank}H_0=n-k. \tag{3}$$

2. The bound

Theorem. For every encoding satisfying (1)-(2), every invertible $R$, and every exact algorithm in this model, its mean number of reads obeys, for each fixed matrix $A$,

$$\boxed{\displaystyle \mathbb E_{u,v}\operatorname{reads}(A,u,v) \ge \frac{g-\operatorname{rank}H_0}{4(1+2664\kappa)} =\frac{n^2-h-n+k}{4(1+2664\kappa)}.} \tag{4}$$

The expectation uses independent uniform $u,v\in\mathbb F_2^n$, including zero. The algorithm is exact, not merely correct with high probability. The result remains valid even if all $n$ advice bits $Hw$ and all $h$ exceptional bits $w_{[d]\setminus J}$ are supplied free: (4) already bounds the reads of retained bits alone.

If $\kappa$ stays bounded and $g\ge\varepsilon n^2$ for fixed $\varepsilon>0$, the mean and worst-case costs are $\Omega(n^2)$. Reading all independent coordinates gives the matching $O(n^2)$ bound. Neither the constant nor the full cost of query-local computation is optimized.

Proof: charge average residuals before combining blocks

Let $q(u,v)=\operatorname{vec}(uv^{\mathsf T})$, and let $\pi_J$ project onto retained coordinates. With the free information just described, the minimum possible number of retained reads for this query is

$$\tau(q)=\min_c\operatorname{wt} (\pi_JR^{-1}q+H_0^{\mathsf T}c).$$

This is the existing support characterization, applied after projection. On every exact adaptive transcript the query functional belongs to the span of the free functionals and inspected coordinates; otherwise an invisible change in $A$ flips the answer. Conversely, a minimum residual can be read and combined with the free information. Thus every transcript, for every $A$, costs at least $\tau(q)$.

Choose arbitrary minimizing witnesses

$$\pi_JR^{-1}q=H_0^{\mathsf T}c(u,v)+b(u,v),\qquad t=\mathbb E_{u,v}\operatorname{wt}(b)=\mathbb E_{u,v}\tau(q).$$

No linearity is assumed for $c$ or $b$. In either argument the query has additive defect zero, so $H_0^{\mathsf T}\delta c=\delta b$. Each of the three residuals in a uniform additive test has the same distribution, giving $\mathbb E\operatorname{wt}(\delta b)\le3t$.

For indices $i,a$ in block $I_j$, consider $f_{ia}=c_i+c_a$. If a defect in that block has weight $s$, the number of ordered pairs with scalar defect one is $2s(m_j-s)$. Consequently (2) gives, at each test triple,

$$\sum_j\frac{\lambda_j}{m_j} \sum_{i,a\in I_j}1[\delta f_{ia}=1] \le 2\operatorname{wt}(\delta b). \tag{5}$$

Average the two kinds of additive tests. In each block choose a reference $a_j$ with no greater error than the block average. Writing $\varepsilon_{1,i},\varepsilon_{2,i}$ for the two rejection probabilities of $c_i+c_{a_j}$, we obtain

$$\sum_j\lambda_j\sum_{i\in I_j} (\varepsilon_{1,i}+\varepsilon_{2,i})\le12t.$$

The classical bilinear-correction lemma, with its full proof and the conservative constant 222 in the preceding note, gives bilinear functions $B_i(u,v)$. If $z(u,v)=\sum_jc_{a_j}(u,v)1_{I_j}$, then

$$\sum_j\lambda_j\mathbb E\operatorname{wt} ((c+z+B)_{I_j})\le2664t.$$

Equation (1) kills $H_0^{\mathsf T}z$. The row-degree bounds therefore yield

$$\mathbb E\operatorname{wt}(H_0^{\mathsf T}(c+B)) \le\sum_j\Delta_j\mathbb E\operatorname{wt}((c+z+B)_{I_j}) \le2664\kappa t.$$

The vector-valued bilinear function $L(u,v)=\pi_JR^{-1}q+H_0^{\mathsf T}B(u,v)$ extends to a linear map on matrix space. Its rank is at least $g-\operatorname{rank}H_0$, since $\pi_JR^{-1}$ has rank $g$. At least that many coordinates are nonzero bilinear forms, each one on at least a quarter of uniform query pairs. Thus

$$\frac{g-\operatorname{rank}H_0}{4} \le\mathbb E\operatorname{wt}(L) \le t+2664\kappa t.$$

This proves (4). The number of blocks has introduced no multiplier.

3. Independent pieces and genuinely crossing columns

If $H_0$ is block diagonal, with each block satisfying its own expansion inequality and having even columns, the output weights add exactly, giving (2). This resolves the original separate-piece question. It is essential to sum average residual costs, rather than add the worst cost of every block.

The theorem also includes representations that are not block diagonal. For example, let $n=2m$ and partition the rows into equal sets $A,B$. Choose each of $d=n^2$ columns independently by taking a uniform pair from $A$ and a uniform pair from $B$. Every column crosses the partition. For all sufficiently large even $n$, there is a choice satisfying (2) with $\lambda_A=\lambda_B=n/4$, and maximum row degree at most $8n$. Thus $\kappa\le32$, $\operatorname{rank}H=n-2$, and

$$\mathbb E\operatorname{reads}\ge \frac{n^2-n+2}{4(1+2664\cdot32)}.$$

To prove existence, complement within either block so its selected set has size $s_A,s_B\le m/2$. A random pair meets a set of size $s$ oddly with probability $p_s=2s(m-s)/(m(m-1))$. For $m\ge4$, $s/m\le p_s\le2/3$. The whole column has odd intersection with probability

$$p_{s_A}+p_{s_B}-2p_{s_A}p_{s_B} \ge(p_{s_A}+p_{s_B})/3 \ge(s_A+s_B)/(3m).$$

For $s=s_A+s_B>0$ the mean count is at least $2ns/3$. A binomial lower-tail bound puts the probability of a count below $ns/4$ at most $e^{-ns/12}$, using the weaker half-mean threshold. There are at most $4n^s$ choices with these reduced sizes, including block complements. Summing over $s$ tends to zero. Each row has mean degree $4n$, and the probability any row exceeds $8n$ also tends to zero. Both conditions therefore hold simultaneously. Repeated columns are allowed; this example makes no absence-of-short-dependencies claim.

By (3), the only kernel supports are the empty set, $A$, $B$, and the full set. A connected component would supply a kernel indicator. Since every column crosses $A,B$, neither block can be a component, so the support hypergraph is connected. No permutation of rows and columns makes a nontrivial block diagonal decomposition. We do not claim impossibility after arbitrary row basis changes; they are a different operation.

4. What fails: separately expanding groups can cancel

There is a sharp reason not to replace (2) by separate expansion tests. Take $n=2m$, $m\ge2$, and let $G$ be a vertex-edge incidence matrix of the complete graph on $m$ vertices, with its edges repeated as evenly as possible until there are exactly $d=4m^2$ columns. Put

$$H=\begin{bmatrix}G\\G\end{bmatrix}.$$

Every column has two entries in each block. Each graph edge occurs at least eight times, so for a subset of size $s\le m/2$, each block separately has odd-intersection count at least $8s(m-s)\ge4ms$. Its maximum degree is at most $9m$. Thus both restrictions have uniformly bounded degree-to-expansion ratio. Nevertheless

$$H^{\mathsf T}(x,x)=G^{\mathsf T}x+G^{\mathsf T}x=0$$

for every $x$. If $x$ is nonconstant, the proposed right side in (2) is positive. The hypothesis fails because the actual kernel is larger than the two block-complement directions.

More generally, let $C_j=\operatorname{im}(H_{0,I_j,*}^{\mathsf T})$. Assuming each restriction has only the constant kernel, absence of additional global kernel directions is equivalent to the $C_j$ forming an internal direct sum. Equation (2) requires quantitative Hamming separation as well as that algebraic condition. Disjoint coordinate supports suffice, but are not necessary. Merely testing each piece separately does not control cancellation.

This example is not a cheap-query construction. Subtracting corresponding rows replaces the advice matrix by $[G;0]$, revealing its redundancy. The cancellation refutes a particular sufficient-condition shortcut, not the unrestricted quadratic conjecture or all possible basis changes.

5. Established ingredients, resources and remaining obligation

The correction step is the same classical homomorphism-testing ingredient used in the preceding note, credited to Blum, Luby and Rubinfeld with Coppersmith’s majority analysis. No correction theorem is reproved here. The rank-one averaging and exact adaptive support characterization are also reused. The additional argument is the weighted charging across coupled blocks, the projected-rank cost for exceptional coordinates, and the explicit distinction between separate expansion and noncancellation. Novelty has not been established.

For equal weights, (2) is a familiar local-testability inequality for the code of block-constant vectors: a uniformly chosen column parity rejects with probability at least $\lambda\operatorname{dist}(x,C)/g$. With columns of size four, the tester reads four message coordinates. This is the standard rejection-versus-distance notion described in the primary paper of Dinur, Evra, Livne, Lubotzky and Mozes, Introduction and Theorem 1.1. We use that definition for provenance, not their construction of codes with constant rate and distance. In particular we do not infer the present query bound for every locally testable code: the block-constant kernel is used essentially to choose and correct references.

Input sizes remain $b=2n$, coefficient length $N_0=\Theta(n^2)$, and explicit fixed-shape 3CNF length $N=\Theta(n^2\log n)$, including names and auxiliary variables. Stored size is $S=n^2+n$; supplied dense encoding costs $O(Sn^2)$ operations per matrix. Public matrices have polynomial size, while discovery and exhaustive checking of the expansion certificate are not asserted polynomial-time. A quadratic read bound here is $\Omega(N/\log N)$, not an exponential bound in formula length.

The linked finite checker and recorded output verify only concrete small expansion and cancellation certificates. They do not verify the unbounded theorem, the probabilistic existence argument or any query lower bound. No proof-assistant verification or access-preserving simulation to Turing machines, scaffolding automata or unrestricted SAT is supplied.

The next decisive question concerns a more general kernel: can its invisible message directions be removed or handled with a quantitatively controlled correction map? A valid extension must prevent cancellation and control the cost of the chosen message coordinates. Block expansion now supplies the required accounting once such a certificate is available; it does not prove that every advice matrix admits one.