Cheap composition requires short storage dependencies

The unchanged composition problem

Over the binary field, independently prepare the fragments y=Ax and x=v together with an odd inner product of u and y. Compatibility is

Write $d=n^2$ and $S=d+n$. Store $z=E\operatorname{vec}(A)$, where the public binary$S\times d$ matrix $E$ has rank$d$ and is chosen before either fragment. All matrix-dependent state is charged; addresses and layout are fixed. Exact deterministic queries may adapt their reads, with free local computation. Initial storage is immutable, there is no earlier-query cache, and the cost includes all reads through the final answer, including deferred composition.

The established support characterization identifies this expression with optimal worst-case reads, including adaptive algorithms. The kernel K records dependencies among stored bits. It is different from the bilinear query code used in the earlier distance-only limitation.

A conditional quadratic lower bound

Let $\Delta$ be the smallest weight of a nonzero vector in$K$. For every such $E$:

Consequently, if $\Delta$ is at least a fixed positive multiple of$n^2$, composition requires quadratically many reads. This holds for every identification of the quotient by K with the matrix space, not just a random choice of matrix coordinates. The hypothesis concerns E alone: enumerate K and measure its minimum nonzero weight. This is a finite check, not an assertion that checking it is efficient.

Proof. Put $t=T_E$ and choose a minimum-weight representative$s(u,v)$ for every query, assigning zero to zero queries. If$\Delta>3t$, the following vector belongs to$K$ and has weight at most $3t$, so it is zero:

The same reasoning applies in u. Thus s is additive in both arguments, hence bilinear over the binary field. Its linear extension from the tensor product is a right inverse of P, and has rank d. At least d of its coordinate bilinear forms are therefore nonzero. For any nonzero coefficient matrix B:

Indeed, outside the kernel of B transpose, exactly half the v give one. Averaging the weight of $s$ over independent uniform$u$ and $v$ gives$t\ge d/4$. Either this argument applies or$3t\ge\Delta$, proving the bound.

Where an unrestricted counterexample would have to live

Short dependencies can exist while remaining confined to a few coordinates. The same proof also treats that case. For t=T_E, let U be the union of supports of all kernel vectors of weight at most 3t, and put

Every additivity defect displayed above is supported in U. Outside U the representative s is therefore bilinear. Let T be its linear extension on those outside coordinates. On the matrix-unit basis, choose the inside coordinates of s and extend them linearly as B. Then P(T+B) is the identity. The restriction of P to the U coordinates has rank |U|−k_U, so T has rank at least d−|U|+k_U. At least that many outside coordinate forms are nonzero; the same averaging proves the inequality.

Thus a sequence of subquadratic encodings would have to satisfy

Almost all coordinates must be covered by short dependencies. Moreover, if k is the dimension of their span, choose a basis of k short vectors. Their supports cover U, giving |U| at most 3tk and k_U at least k. Hence

This last inequality alone is only linear when k=n and does not improve the existing general lower bound. Row-parity storage already has dependencies covering every coordinate. Coverage is necessary, not sufficient for cheap queries; the unresolved issue is their simultaneous compatibility.

Most kernels satisfy the conditional bound

Choose $K$ uniformly from the $n$-dimensional subspaces of the$S$-dimensional binary cube. For any positive λ, a union bound gives

To verify this directly, sample an injective linear map from$\mathbb F_2^n$ to $\mathbb F_2^S$. The image of each fixed nonzero vector is uniform on the nonzero$S$-vectors. Its lower-tail probability is at most twice the corresponding unbiased-binomial bound $\exp(-2a^2/S)$. Union over fewer than$2^n$ vectors and substitute the displayed deviation. The binomial bound follows from $\cosh(h/2)\le\exp(h^2/8)$.

Taking $\lambda=n$ shows that, except with probability at most$2e^{-n}$, every quotient identification with this K has

Randomness here selects a public encoding family; queries remain exact and deterministic. This uses the classical random-linear-code distance argument, reviewed in Doron, Mosheiff and Wootters, Introduction. We do not import their stronger concatenation results. The additional point here is the consequence uniform over every quotient identification.

Why nonlinear read choices cannot be discarded

For a two by two matrix, store the two entries and their parity in each row: six bits, exactly the prescribed budget. For each nonzero v, one of the three stored bits in a row equals its inner product with v. Read that bit in each row selected by u. Every query costs at most two reads, and a query selecting both rows requires two.

Now fix $u=(1,1)$ and require the read pattern to be linear in$v$. Patterns of weight at most two must use one bit in each row block. The patterns for$v=(1,0)$ and $v=(0,1)$ use distinct positions in each block; their sum has weight four. It cannot be a weight-two pattern for $v=(1,1)$. Thus some query needs at least three reads under a linear selector. Three is attained by choosing different worst vectors in the two row blocks.

The kernel has two disjoint weight-three generators. On a single-row slice, three weight-one representatives have a nonzero weight-three additivity defect. This also explains why the strict inequality Δ greater than 3t is needed for the lifting step.

The loss from linearizing even one slice can grow without bound. For$k\ge3$, set $n=2^k-1-k$. Store every nonzero parity of $k$ first-row entries, and store the other$n^2-k$ entries raw. This uses exactly$n^2+n$ bits. On the $k$-dimensional slice selecting those first-row entries, every nonzero query costs one read. Any linear selector has rank k; an information set in its image gives a vector of weight at least $k$. A basis selector attains$k$. This is a $\Theta(\log n)$ local gap, not a subquadratic construction for all queries.

Finite checker · Exact finite results. It enumerates all 64 read patterns and all 256 bilinear selectors in this example. Its purpose is to corroborate the counterexample, not prove the unbounded statements.

What this settles, and what it leaves open

The general quadratic hypothesis remains unresolved. The lower bound$n\log_2(n)/48$ and the covering-code upper bound remain unchanged. We have isolated a sufficient obstruction in K and a necessary structural condition for escaping it. Neither is a characterization.

The boundary width remains $b=2n$. Coefficient-description size is $\Theta(n^2)$; the fixed-shape explicit 3CNF encoding has size $\Theta(n^2\log n)$, including names and auxiliary clauses. Storage is $S=n^2+n$ bits. Dense per-matrix preparation takes $O(Sn^2)$ Boolean operations once the public$E$ is supplied. Its description is polynomial-sized; no efficient synthesis or minimum-distance certification is claimed. Query-local computation and allocation are free, so these are read bounds, not complete running-time bounds.

The proof is written and independently reviewed, not proof-assistant checked. The support characterization, elementary bilinear averaging and classical coding estimates are established ingredients. The compatibility argument is recorded as a useful elementary consequence without a novelty claim. No unrestricted SAT, Turing-machine or scaffolding lower bound follows without a resource-preserving access simulation; none is added here.