Covering codes improve the composition upper bound

The same composition problem, a better construction

Over the binary field, the two fragments require y=Ax and, separately, x=v with an odd inner product of u and y. Compatibility is the bit below. The matrix is prepared before either query vector is known.

Store $S=n^2+n$ linear combinations of the matrix entries, with no other matrix-dependent information. Let L denote the best worst-case number of stored-bit reads for these queries. For comparison, let C denote the optimum under the same storage contract when every linear functional of the matrix is permitted as a query. Then:

This gives a better asymptotic upper bound for $L$ than the product-storage optimum $n\lceil n/2\rceil$. Both remain quadratic. The established lower bound for $L$ is still $n\log_2(n)/48$, for $n\ge64$. The hypothesis that L is of quadratic order remains unresolved.

The equality for C is a classical covering-code consequence, not a new lower bound for L. The larger query class has n squared query coefficients; our rank-one queries have only the two n-bit vectors u and v.

Why a covering code describes access

Write the stored vector as z=E vec(A), where E has S rows and rank n squared. A read pattern a returns the desired functional q exactly when:

The kernel K of E transpose has dimension n. All valid read patterns for one query form a coset $a+K$. The fewest reads equal its smallest Hamming weight, by the previously established support characterization, including exact adaptive algorithms. Taking the worst case over every q gives the covering radius of K: the greatest distance of any binary vector from K.

Conversely, any such K supplies an encoding: take E transpose to be a quotient map with kernel K. This storage/query connection is established in the linear-data-query literature, including Elimelech, Firer and Schwartz, Introduction. Here it is specialized to the fixed storage budget and the affine fragments.

The classical covering argument, with the budget exposed

Let p be the fraction of binary S-vectors in a radius-R Hamming ball. Cohen's covering argument gives the following sufficient condition:

Start with the zero code. If U is the uncovered set, adding a generator g changes U to its intersection with U+g. The average relative size of this intersection is the square of the relative size of U. Choose g attaining at most that average at every step. After n steps the uncovered fraction is at most (1-p) to the power 2 to the n, strictly below exp(-p times 2 to the n). The displayed condition makes it smaller than one point's fraction, so it is zero. The code has dimension at most n; extend it to dimension exactly n if needed.

For the reverse bound, covering the cube with 2 to the n balls requires their total volume to be at least the cube's volume. The binary Hoeffding tail bound therefore gives:

To see the matching second-order term directly, fix any positive c below the square root of ln(2)/2 and take R=floor(S/2-c n to the three-halves). The elementary binomial entropy estimate and its Taylor expansion give:

Here H subscript two is binary entropy. Since the coefficient of n is strictly below one, the sufficient condition holds for all sufficiently large n. Letting c approach the threshold proves the asserted asymptotic equality for C. It is an existence bound, not an efficient synthesis algorithm.

Cohen's theorem and its small-code regime are stated in Bazzi, Theorem 1.3 and Corollary 1.4; the iterative argument is described in Section 4.1. The original result is Cohen, A nonconstructive upper bound on covering radius (1983). We apply that classical argument, not a new covering theorem.

An explicit alternative with polynomial computation

A simpler, weaker construction avoids exhaustive public-code synthesis. For n at least 64, define:

Partition S coordinates into B blocks of length L and a tail of length r. On each block use the first-order Reed-Muller code, the truth tables of all affine Boolean functions on log base two of L variables. Use the repetition code on a nonempty tail. Their direct sum has dimension at most B(e+1)+1, hence at most n; enlarge it to dimension n.

For any block word f, its Walsh coefficients satisfy Parseval's identity: the sum of their squares is L squared. Some coefficient therefore has absolute value at least the square root of L. Choose the corresponding affine function and its constant term to obtain distance at most (L minus square root of L)/2. The tail costs at most floor(r/2). Thus:

The finite bound is strictly below n squared divided by two for every n at least 64: B is at least two and BL is greater than S/2, so B times square root of L is greater than n. At n=64 it gives 2,016 reads, compared with the product optimum of 2,048.

The Reed-Muller bound is classical; see Elimelech, Wei and Schwartz, Lemma 10 with covering order one. Given a public right inverse of E transpose, first lift q to a coefficient vector, then improve it blockwise using Walsh transforms. The resulting vector remains in the same coset, even after enlarging the kernel. Polynomial linear algebra constructs the public encoding.

Entries are worst-case read guarantees, not measured timings. The existence column uses the stronger, exactly checked integer condition 2 to the n times p at least S. It does not identify an optimal code. The explicit formula is also valid at the displayed n=16, although the strict-improvement statement above is for all n at least 64.

Resources and what remains open

The original fragments retain boundary width b=2n, coefficient input size N0=n squared plus 2n plus O(log n), and explicit 3CNF size N=Theta(n squared times log n). Storage is exactly S=n squared plus n bits. E depends only on n. All matrix-dependent state is charged; addresses, control, pointers and metadata carry no extra information. The other fragment is prepared independently. Old storage is immutable, queries start without an earlier matrix-dependent cache, and all reads through the final Boolean answer count, including work deferred by a lazy join.

These are deterministic exact access bounds with free query-local computation and allocation. Once E is supplied, dense matrix preprocessing costs O(S n squared) Boolean operations. The existence construction does not promise efficient public synthesis or coefficient selection. In the explicit construction, a dense query lift costs O(S n squared) Boolean operations; block Walsh transforms use O(S log S) arithmetic operations on O(log S)-bit integers. These costs are separate from stored-bit reads.

Consequently neither construction establishes a comparable total-time bound for a Turing machine or a scaffolding automaton. Such a statement would require a loader, access simulation and computation accounting. No new machine transfer, unrestricted SAT bound or language separation is claimed. The known scaffold-to-PEG transfer still reverses the language.

The next question is specific: can one kernel and one identification of its quotient with matrices give all rank-one syndromes subquadratic representatives? The sphere-volume lower bound above uses every syndrome and cannot answer that question. Further optimization of the classical all-query benchmark would not resolve this missing step.

Proof status and evidence

The mathematical arguments are written and independently reviewed by an agent, not formally verified. Their ingredients, including the access/ covering correspondence, are established literature. The contribution here is the budget-specific comparison and improved upper bound within this investigation; novelty is not claimed.

A finite checker verifies small Reed-Muller covering radii, two complete greedy-cover examples, the encoding/query identity for a small constructed instance, and exact integer sufficient conditions at selected sizes. These checks do not prove the asymptotic statement.

Finite checker · Verification scope · Preceding product-storage result