Working research · 2 October 2026

What a quadratic composition proof must use

When two parts of a constraint problem have been prepared separately, how much of their saved information must be read to combine them? Our test case stores a binary matrix and asks for the parity of a rectangle of its entries. A stored row parity can answer some such tests in one read. The question is whether a small cache can make every test cheap.

Two results narrow the search. Storing a full product of separate row and column encodings cannot beat the row-parity construction. For more general encodings, minimum code distance alone cannot prove the proposed quadratic lower bound. That broader question remains open.

The precise question and cost model

Work over the binary field. One independently prepared constraint fragment requires y=Ax; another pins x=v and requires an odd inner product of u with y. Their compatibility is the single bit below.

\operatorname{SAT}(F_A\land G_{u,v})=u^{\mathsf T}Av.

The matrix has n squared entries. Preprocessing stores n squared plus n linear combinations, at fixed public addresses, with no other matrix-dependent state. Queries are exact and may choose addresses adaptively. Local computation is free; reads of initial storage are counted through the final answer.

d=n^2,\quad S=d+n,\quad L_n(n)=\min_{\operatorname{rank}E=d}\max_{u,v} \min_{E^{\mathsf T}a=\operatorname{vec}(uv^{\mathsf T})}\operatorname{wt}(a).

The established support characterization makes this optimization valid even for adaptive reads. The known general bounds here remain:

n\log_2 n/48\le L_n(n)\le n\lceil n/2\rceil\qquad(n\ge64).

The hypothesis is that the lower bound can be strengthened to quadratic order. Neither result below settles it for arbitrary linear storage.

Separate row and column encodings are settled

Consider storing every entry of a transformed matrix Z=PAQ transpose, where P and Q are public full-column-rank matrices. This permits any changes of row and column basis and redundant coordinates on either side, but requires their full Cartesian product to be stored. With at most n squared plus n entries, the exact optimal worst-case probe count is:

T_{\mathrm{product}}(n)=n\lceil n/2\rceil.

Here is the complete argument. If P and Q have a and b rows, then a and b are at least n and their product is at most n(n+1). Either both are square, or exactly one has one additional row. In the square case, every transformed pair of query vectors is possible, including two all-ones vectors; that query reads all n squared independent stored bits. By transpose symmetry, the other case has P invertible and Q with n+1 rows.

Z=PAQ^{\mathsf T},\qquad \alpha=P^{-\mathsf T}u,\qquad CQ=\alpha v^{\mathsf T}.

The last equation is exactly the condition for the entries selected by the coefficient matrix C to return the requested bit. Its rows are independent equations. Therefore:

\tau_{P,Q}(u,v)=\operatorname{wt}(\alpha)\tau_Q(v),\qquad \tau_Q(v)=\min_{Q^{\mathsf T}c=v}\operatorname{wt}(c).

The kernel of Q transpose consists of zero and one nonzero vector k. Write h for the weight of k. Each fiber contains two vectors differing on exactly h coordinates. Outside those coordinates their common weight can be n+1-h; inside, the smaller of the two weights is at most floor(h/2). Both maxima can occur simultaneously. Hence:

\max_v\tau_Q(v)=n+1-h+\lfloor h/2\rfloor =n+1-\lceil h/2\rceil.

T(P,Q)=n\bigl(n+1-\lceil h/2\rceil\bigr)\ge n\lceil n/2\rceil.

Equality holds when Q is the identity with an all-ones row appended. This is precisely storage of the raw matrix and each row parity. Its preparation takes quadratic Boolean work and it preserves the operands.

This is a real restriction. General linear storage may include A11+A22, a rank-two coefficient matrix. Every individual product-storage cell has a coefficient matrix of rank at most one. Separate invertible changes of the query bases preserve that rank, so they cannot put all encodings into product form. Arbitrarily recombining stored bits can change the access cost and is not a cost-preserving normalization.

Code distance alone cannot close the gap

The preceding lower-bound proof used an evaluation code: list every query answer as a function of the matrix entries. It has dimension d=n squared, length m=4 to the n, and every nonzero codeword occupies at least one quarter of the positions. Those parameters do not force quadratic access.

Limitation. For every n at least 256 there exists a different binary linear query matrix M with exactly those dimension and length parameters, relative distance at least one quarter, and an encoding into S=n squared plus n bits answering every query in O(n log n) reads.

This is an existence proof for other query families. It is not an encoding for our rank-one queries, not an explicit compact-fragment construction, and not a refutation of the quadratic hypothesis.

Set the following integer parameters:

S=n^2+n,\quad \ell=\lceil\log_2 S\rceil,\quad a=\lfloor n/(4\ell)\rfloor,\quad t=\lceil2S/a\rceil.

Choose a uniformly random n by S binary parity-check matrix R. Every nonzero vector is in its kernel with probability 2 to the minus n. The probability that any vector of weight below a is in the kernel is at most:

2^{-n}\sum_{j=1}^{a-1}\binom Sj \le 2^{-n}S^a\le2^{-3n/4}<1.

Fix a successful R. Its kernel has dimension at least d. Choose a d-dimensional subspace D of that kernel and let E inject d bits into D. Every nonzero encoded vector has weight at least a.

Independently generate each row of H by t trials. A trial chooses one of S coordinates uniformly, then includes its unit vector with probability one half. XOR the chosen vectors. Every row has weight at most t, including when coordinates repeat. For any nonzero z in D of weight w, the probability of an odd dot product with one such row is:

p_z=\frac{1-(1-w/S)^t}{2} \ge\frac{1-e^{-2}}2>\frac38.

With m independent rows, the multiplicative Chernoff bound gives a probability at most exp(-m/48) that Hz has weight below m/4. Union-bound over the fewer than 2 to the d nonzero vectors in D. For m at least 128d:

\Pr[\exists z\in D\setminus\{0\}:\operatorname{wt}(Hz)<m/4] <2^d e^{-m/48}<1.

Fix a successful H and put M=HE. Then M has rank d and relative distance at least one quarter. Store Ex; its query row is answered by reading at most t coordinates and taking their parity. For n at least 256:

a\ge n/(8\ell),\qquad t\le16S\ell/n+1=O(n\log n).

Taking m=4 to the n matches the rank-one evaluation code even in its number of query positions. Randomness proves existence of fixed matrices; query answers thereafter are deterministic and exact. Finding the matrices efficiently and storing their public query descriptions are not asserted.

What this changes

There are now two precise limits on the investigation. Full product encodings cannot beat row parities. Conversely, strengthening a proof that knows only dimension, query count and the one-quarter distance threshold cannot yield a quadratic theorem. The remaining route must address rank-one queries under genuinely more general linear storage.

The original compact family still has boundary width b=2n, coefficient description size proportional to n squared and explicit 3CNF bit size proportional to n squared times log n. Its storage budget and charged composition-plus-query cost are unchanged. The constructed comparison codes impose no new lower bound on SAT, Turing machines or scaffolding automata. Any transfer still requires an explicit loader, observation contract and simulation overhead; a scaffold-to-PEG transfer reverses the recognized language.

Provenance and evidence

The product calculation is elementary linear algebra and the covering radius of a one-dimensional binary kernel. The limitation uses the classical random parity-check argument and Chernoff concentration. No novelty claim is made. The additional content here is their precise consequence for the two proposed routes within this composition problem.

Dvir, Golovnev and Weinstein, Section 6.3 and Appendix A, supplies the code-distance method used in the preceding lower bound, adapting Friedman. For a modern primary discussion of the classical random-linear-code argument, see Doron, Mosheiff and Wootters. Their concatenated-code results are not premises of the construction here.

Both written arguments received independent agent review. They are not kernel-verified. The finite checker tests small product encoders and the parity probability formula, not the asymptotic existence theorem.

Finite checker · Exact verification scope