More prepared storage can reduce local composition work

3 October 2026. Written operational construction using classical tabulation.

Our broader question is how completed work becomes a representation that finite local rules can use later. The test here is the same compact affine composition problem: prepare a binary matrix A independently of vectors u,v, then answer the one-bit query u^T A v over F2.

The quadratic theorem restricts storage to n^2+n linear bits. Here we explicitly allow more storage. A uniform program using immutable records, a fixed number of roots, and bounded access and allocation per primitive can prepare block tables and answer in O(n^2/log n) primitive steps. Preparation and its entire retained history cost O(n^3), in steps and records respectively.

Thus finite locality alone does not force quadratic query time. The available storage is consequential. This construction still needs an unbounded number of local steps per answer; it does not provide constant-cost composition or a general characterization of persistent computation.

1. Exact model and resource statement

Let n>=1 and 1<=k<=n be public parameters, and put m=ceil(n/k). Inputs are serial bits with unary n,k headers: A in row-major order, and u,v in a separate input. The exact input lengths and common parameters are promised. The unary headers add O(n+k) symbols. They are data loaded by the program, not size-dependent finite control or free initialization. Each side builds its own rulers; there is no shared input-dependent preparation.

A primitive can inspect a root tag, follow one named field, copy a named root, branch on a finite tag/bit, or allocate one record with at most three fields pointing to named old roots. Multiple actions take multiple primitives. There is a fixed finite register set and finite control; parity is one control bit. Tags include End, bit values, List, Tick, Branch, leaf answers and two continuation stages. No pointer identity, address arithmetic, heap-size observation, integer-valued register or semantic oracle is permitted. Registers may change; old records never do. Initialization is fixed finite data containing End. Every input acquisition, internal primitive and allocated record is charged. Unreachable construction records are not discarded from the accounting.

Construction theorem. One fixed program, for every valid n,k,A,u,v, independently prepares handles and answers exactly u^T A v, preserving the prepared operands, with $$\begin{aligned} P_A, H_A&=O(n^2+m^2 k^2 4^k),\\ P_{u,v},\ H_{u,v}&=O(n+k),\\ T_Q&=O(m^2 k+n). \end{aligned}$$ Here P counts preparation primitives and H counts all allocated preparation records, including input copies, temporary lists and continuation history. The final matrix-and-table representation uses O(n^2+m2 4^k) records, but that smaller bound is not substituted for H_A. A register implementation allocates no new records during the query. A compiled scaffold can allocate one record per query primitive, adding O(T_Q) history.

For the public choice $$k=\max\{1,\lfloor(\log_2 n)/2\rfloor\},$$ we obtain P_A,H_A=O(n^3), query preparation O(n), and T_Q=O(n^2/log n) for large n. The program receives k in its header and works for every valid k; no unit-cost logarithm is used. A claim that it derives k from n alone is unnecessary here.

A conventional explicit encoding of the historical heap has O(H log(H+2)) bits, since every record has constant arity and finite labels. The displayed specialization therefore uses at most O(n^3 log n) bits, not n^2+n bits. It is an upper bound for this construction, not a lower bound or an optimal tradeoff.

2. Loading and aligning the blocks locally

Create unary rulers from the header symbols. Delimit matrix rows by resetting a cursor on the n-ruler; the input need not supply precomputed block handles. Accumulate each row in reverse order, then reverse it by repeated cons and tail operations. This costs O(n^2) primitives and records.

For each row, repeatedly traverse its own k-ruler to make chunks of k bits. If the row ends inside a chunk, append zero bits until that traversal ends. Reverse each chunk accumulator and its enclosing chunk-list accumulator. There are m chunks per row. Group rows into bands of k rows, padding the final band with zero rows. The padded side n’=mk satisfies n’<=n+k<=2n. A zero row of the required chunk-list shape can be constructed once from that public shape and shared within the matrix preparation.

It remains to turn a band of row chunks into matrix blocks without indexed access. Maintain a list of k current row-chunk cursors. One pass over this list collects each cursor’s head chunk into the next block, and its tail into the next cursor list. Reverse both accumulators. Each pass costs O(k), including all obsolete cursor-list records. There are m passes per band and m bands, so this stage costs O(m^2 k), which is O(n^2). Every cursor list has equal-length rows, so testing the first row’s End tag detects completion; no pointer comparison is used.

Consequently the entire reblocking stage costs O(n^2), counting all history. Each produced block is a list of k roots to k-bit lists in the correct row order. The independent query loader uses the same chunking convention for u,v in O(n+k) work and history. Its transitions inspect no matrix root. Padding query coordinates by zero leaves u^T A v unchanged.

3. Building every small answer tree

For a block M, build the complete binary tree of depth 2k. A root-to-leaf path specifies k row-query bits a followed by k column-query bits b. Its leaf is labelled by a^T M b. Thus the topology is fixed; only answer labels depend on M.

The depth is a cursor on a length-2k unary ruler. Depth-first construction uses an explicit immutable stack, not an uncharged recursive call stack. A Left frame stores the remaining-depth cursor, the reversed assignment prefix, and the parent frame. After the left subtree returns, replace the active stack root with a Right frame containing the left result and parent; descend with a 1 appended to the saved prefix. After the right return, allocate Branch(left,right) and continue at the parent. Descending left appends 0. Each such operation expands to a constant number of the declared primitives, with frame arity at most three.

At a leaf, reverse the assignment list and advance a cursor k positions to locate b. Scan the k block rows. For each row, restart the named b-root, scan corresponding matrix and b bits, and update the parity using that row’s a bit. Only a fixed collection of list cursors and finite bits is needed. This evaluates a^T M b in O(k^2) primitives and at most O(k^2) new records, including the assignment reversal. The actual reversal allocation is only O(k); the larger bound safely includes all activity.

Induction on the remaining ruler length proves that the returned tree has precisely the required leaves. A full tree has 4^k leaves and 4^k-1 internal nodes. Its assignment lists and continuation frames also remain allocated. Total construction cost and all allocation per block are O(k^2 4^k), proving the matrix-preparation bound after summing over m^2 blocks and adding reblocking.

All program subroutines have a fixed call graph; the sole unbounded recursion above is the explicit continuation stack. One can assign a fixed register bank to the finite list of subroutines and expand their field accesses into individual primitives. Counters are ruler cursors. This establishes fixed roots, finite rules, radius at most one for old addresses, arity three and allocation at most one per primitive without assuming a growing machine description.

4. Composition and the final answer

The matrix handle retains a nested list of block-tree roots. The query handle retains the u-chunks and v-chunks. To process one matrix block row, keep the current u-chunk root and reset the v-chunk cursor to its saved first root. For each block tree, follow k branches using that u-chunk and k more using the current v-chunk. XOR the leaf label into finite control, then advance the tree and v-chunk cursors. At a block-row end, advance the matrix row and u-chunk cursors.

No operation jumps to an integer-selected address. Resetting a cursor copies a root already held by the controller. The total cost is O(m^2 k+n), including all list routing, tag observations and the final answer. Merely returning a lazy pair of operands is not the measured endpoint.

After any completed prefix of block pairs, the accumulator equals the XOR of their local bilinear answers. The invariant starts at zero and each leaf preserves it. Upon termination it is $$\bigoplus_{i,j} u_i^{\mathsf T} A_{ij}v_j=u^{\mathsf T}Av.$$ Here u_i,v_j are padded k-bit blocks. This proves correctness for every input, without averaging or randomization. All prepared operands remain intact and may be queried again; each query has the stated cost. No evolving answer cache is assumed.

5. Input sizes and machine scope

The constraint fragments remain $$F_A(x,y):y=Ax,\qquad Q_{u,v}(x,y):(x=v)\land(u^{\mathsf T}y=1).$$ Boundary width is b=2n. Coefficient input size, including the unary public headers, is N0=Theta(n^2); the earlier fixed-shape named CNF realization has N=Theta(n^2 log n). For logarithmic k the query upper bound is O(b^2/log b), equivalently O(N0/log N0) and O(N/(log N)^2) for that encoding. Preparation/history bounds O(n^3) become O(b^3) or O((N/log N)^(3/2)) in steps/records; pointer bits carry the additional logarithmic factor stated above. No claim about arbitrary input CNF parsing or arbitrary SAT instances is made.

The source primitives meet the reviewed simultaneous-record contract: bounded finite observations and copied addresses, immutable old records, constant allocation, and fixed finite initial data. The prepared graphs are created during charged loading; they are not supplied as free size-dependent initialization. With s fixed roots, the compiler gives degree max(1,s+3) and native distance two when each primitive is treated as one clocked input action.

This is a consequence for the complete encoded, clocked client. Sequentially loading a matrix and a query may preserve matrix roots while query preparation does not inspect them; equivalently, the independently prepared heaps can be combined over fixed initialization. We do not assert real-time recognition of the unpadded raw input language or a free mechanism for receiving arbitrary remote handles. A scaffold-to-PEG recognition conclusion would still involve one reversal. The written operational proof is not a new formally verified compiler artifact.

6. What this resolves

Classical tabulation exchanges preparation/storage for later computation. Ramamoorthy and Rashtchian, Section 1.4, record the polynomial-space vector-matrix-vector construction in their discussion of the classical Four Russians method. Their cell-probe statement is not itself a certificate for our immutable local machine. The proof above supplies that operational accounting; the tabulation idea is not claimed new, and historical novelty of this presentation is unestablished.

The quadratic theorem and this construction concern different storage budgets. Even the completed tree leaves are linear functions of A, so nonlinear summaries are not needed for this distinction. The quadratic restriction cannot be attributed to locality alone. Conversely, this construction remains far from constant-cost composition and does not show that its large prepared tables can be maintained cheaply after changes to A.

The proposed operational test is now closed by a written construction. Optimizing the table constants or polynomial preparation exponent is not needed for its conclusion. The broader remaining issue is maintenance: when can a prepared representation absorb further work or changes with bounded local access and allocation while retaining its future guarantees? That requires an explicit update/reuse interface; this static result supplies neither a universal answer nor an automatic new research target.

Verification

Two independent reviews checked the loader, operational scope and compiler hypotheses. The executable check uses immutable bounded-arity nodes and explicit DFS frames. Its output checks all matrices and queries for n<=2, and four seeded matrices with 24 query pairs each for n=3 through7 and k<=min(n,3), including nondivisible padding. It checks exact answers, operand immutability, no query allocation, and absence of matrix references in independently prepared query nodes.

The checker parses a flat matrix stream using a unary width cursor. Its reported operation counts measure heap observations and allocations; they exclude host input delivery, control branches and root copies. Those require only a constant-factor expansion in the written program, but the numerical counts are not exact transition counts.

These are finite algorithmic checks. Python instrumentation and the host’s input/oracle loops are not a proof-assistant verification of a finite-state compiler, nor do they establish the unrestricted bounds. The universal proof and accounting are written above. No formal mechanization was undertaken because this checkpoint concerns operational applicability of a classical construction rather than an unresolved algebraic inequality.