A representation ready after every arriving coefficient

3 October 2026. Written construction; classical tabulation and incremental scheduling.

Can a representation remain useful while information arrives, with only bounded local work at each arrival? For the compact affine composition problem, the answer can be yes even when the eventual query is subquadratic. The representation need not finish every internal task before it becomes usable.

Prepare a binary matrix A independently of vectors u,v, then answer u^T A v over F2. The previous construction materialized separate block-answer trees with polynomial preparation. Here all blocks share a single universal tree. Each completed row band is processed while the next arrives. At most two unfinished bands stay in their original form, and the query pays to scan them.

The useful principle is that a maintained representation may combine completed summaries with a small, explicitly bounded unfinished part. Readiness is a guarantee about the cost of its future use, not a requirement that every summary already be complete.

1. Interface and theorem

Fix n>=1 and a public integer k with 1<=k<=n and $$k^2 2^{k^2+2k}\le n. \tag{1}$$ The matrix input gives unary k first, unary n second, and then n^2 coefficients in row-major order. Headers, delimiters and coefficients are all charged. These parameters and lengths are promised valid; no large-integer validation algorithm is implicit. There is one fixed program and one constant primitive budget per input symbol, independent of n,k and the coefficients. A separate raw-storage mode covers parameters outside (1).

Use finite tags, a fixed number of roots, immutable acyclic records of fixed arity, and fixed finite initialization. A primitive reads a root tag, follows a named field, copies a named root, branches on a finite tag, or allocates one bounded-arity record whose fields name older records. Multiple actions cost multiple primitives. There is no pointer identity, address arithmetic, mutable array, unbounded scalar register or free initial table. All allocated history counts, including abandoned jobs and snapshots. The local primitives are those of the previous construction; a fixed tuple can be represented by a fixed chain of records of arity at most three.

After each complete coefficient-arrival transition the loader supplies a snapshot handle. After t coefficients, its meaning is the n by n matrix A^(t) having that row-major prefix and zero in every unread position. A caller may retain these handles. Selecting a past handle by numerical time is not a free operation. The loader itself has only a fixed number of active roots.

Readiness theorem. There are absolute constants for which every valid input under (1) has a uniform immutable realization with:

• bounded primitives and allocation per header symbol and per coefficient;
• O(n+t) total preparation primitives and historical records through coefficient t, including all earlier snapshots;
• independent preparation of u,v in O(n) primitives and records;
• an exact answer u^T A^(t) v from any retained snapshot in $$T_Q,H_Q=O(n^2/k+nk+n), \tag{2}$$ where query time includes normalization and every deferred task, and H_Q counts all new query records.

For sufficiently large n, the public choice $$k=\left\lfloor\frac{\sqrt{\log_2 n}}2\right\rfloor$$ satisfies (1). Indeed, k^2+2k<=log_2(n)/4+sqrt(log_2 n), so the polynomial factor k^2 does not exhaust n. Therefore complete loading uses O(n^2) primitives and historical records, while $$T_Q,H_Q=O\!\left(\frac{n^2}{\sqrt{\log n}}\right). \tag{3}$$ The program receives k as data; it does not compute a logarithm in unit time. An explicit raw-mode tag, followed by unary n, handles all remaining bounded small sizes by the same row collector and a direct quadratic query. The asymptotic specialization is unaffected.

These are upper bounds, not optimality claims. They do not give a constant-cost query or an arbitrary-entry update interface.

2. Build one universal tree during the header

For a k by k block M, let a,b be k-bit vectors. Construct the full binary tree with path order $$\operatorname{vec}(M),\ a,\ b$$ and depth d=k^2+2k, whose leaf is a^T M b. A block’s k^2 data bits select a root of a depth-2k answer subtree. All blocks can point into the same universal tree; its contents do not depend on A.

The unary k header constructs a k-ruler. During the unary n header a coroutine constructs a k^2-ruler by nested traversals of the k-ruler, then the depth ruler, and performs depth-first tree construction. An explicit immutable continuation stack holds pending children and assignment prefixes, as in the previous construction. No host recursion or implicit stack is needed in the claimed program.

At a leaf, reverse the d-bit assignment list. Its first k^2 positions are matrix data, the next k positions are a and the last k are b. Locate the latter roots by ruler traversals. Scan the k matrix rows, restarting the retained b-root per row, and compute parity in finite control. This takes O(k^2) primitives and records per leaf. Branches, assignment lists, continuation frames and rulers together also fit $$O(k^2 2^{k^2+2k}). \tag{4}$$ All nodes are retained in the historical count, not just the final tree.

There is an absolute constant c bounding (4) for this fixed program. On each n-header symbol, perform c or more builder primitives, alongside a constant amount of header parsing and n-ruler construction. Increase this fixed quantum once if needed to include final root installation. Condition (1) then guarantees that the tree is ready when the n header ends. The header supplies only n symbols, not an arbitrarily padded preparation interval. Idle builder slots do nothing.

Thus the table is built during charged input processing from fixed initialization. Its sharing is internal to matrix preparation. The independent query preparation uses none of its roots.

3. One completed band can be processed in the next band’s time

A full band consists of k consecutive rows, each of length n. The input collector conses each arriving bit onto the current reversed row. An n-ruler cursor detects row completion; a k-ruler cursor detects band completion. A completed row is consed onto a reversed row list. Closing a row, closing a band, resetting cursors and saving a snapshot require only a fixed number of local actions. Separate register banks hold collector and worker state.

Given a completed raw band, the worker performs the following bounded total job:

1. Reverse the row list and each row, producing chronological order.
2. Split each row into chunks of k, padding only the last column chunk with zero. Let m=ceil(n/k).
3. Maintain a k-element list of current row-chunk cursors. A pass takes the head chunk from each row to form the next block, and its tail to form the next cursor list. Reverse these two accumulators after each pass.
4. Scan each block’s k^2 bits in row-major order and follow those data edges from the shared universal root. Save the selected answer-subtree root.
5. Reverse the selected-root list into column order and publish a private Done result for the collector.

Step 3 is the explicit local reblocking method already proved in the previous note. It uses no integer indexing or unbounded set of registers: the k cursors live in an immutable list traversed one element at a time. Input normalization and chunking cost O(nk); cursor passes cost O(mk); data selection costs O(mk^2). Since mk<=n+k<=2n, the whole job costs at most c_1 nk primitives and historical records for an absolute c_1. This includes temporary and obsolete lists and the Done result. Promotion to the canonical representation is a separate bounded action described next.

At each coefficient arrival, first execute a fixed quantum Q>=c_1 of worker primitives, if a job is active. If the worker has reached Done, the collector then performs the entire bounded promotion: cons its result onto the canonical compiled-band stack, clear the canonical pending-band root, and set the worker idle. Only after this complete promotion does it collect the coefficient and emit the snapshot. This extra fixed amount of work is included in the per-arrival budget. A quantum may end halfway through any private worker step sequence, but never exposes half a promotion in a snapshot. A job starts when its full band has been collected. The next full band contains exactly nk arrivals, which provide enough work to finish and commit its predecessor. Consequently a second completed band never queues behind an unfinished predecessor. No FIFO, amortized reversal or unbounded job queue is assumed.

Every loop cursor, continuation and program counter of the worker is explicit finite-tag or pointer state. Pausing after any primitive and resuming at the next arrival therefore does not require uncharged computation. The old raw band root is retained until commit. Partial derived output can always be ignored without traversing or reclaiming it; its records remain counted.

4. The snapshot invariant, including an unfinished final row

After every complete arrival transition, exactly the received coefficients are partitioned chronologically into:

1. a prefix of completed, compiled full bands;
2. at most one pending full raw band;
3. the current band’s completed raw rows and its optional nonempty partial row.

Initially these components are empty. Collection extends only the last component. Closing a band transfers it to the pending component, whose predecessor has finished by the scheduling argument. A worker commit transfers its pending component to the compiled prefix. Removing the pending contribution and installing its compiled replacement both occur before the next snapshot is emitted. Thus no coefficient is duplicated or lost. The unread suffix contributes zero by definition.

A fixed chain of records stores these representation roots plus public shape roots. The snapshot need not retain worker progress to answer a query. Immutability preserves the partition in every older snapshot even after the active worker commits. The guarantee is at arrival boundaries, not at arbitrary microsteps inside a commit.

At a complete matrix’s last coefficient there is no finishing phase. The final band may have only partly paid for its predecessor, or it may just have become a pending full band. In every case the two raw components have at most 2nk coefficients. The same bound holds at intermediate prefixes, including a prefix that ends inside a row. No padding rows are constructed in an end-of-input burst.

The collector, worker quantum and snapshot construction allocate boundedly per arrival. Together with the charged header, this proves O(n+t) time and historical allocation. Retaining old versions is included. Branching a loader computation from a retained full loader state is possible by immutability, but the bound counts actual arrival transitions across branches, not just the longest branch. The snapshot-query interface does not require exposing those full loader states.

5. A query pays for all remaining work

Prepare u and v independently as ordinary forward lists using cons and reversal in O(n) work. Their preparation does not inspect matrix storage. Given a snapshot, reverse its stack of compiled bands to restore chronological order; this costs O(n/k) new records and steps. The selected roots within each band are already in column order.

For each compiled band, retain the root of its k consecutive u bits. Reset v to its first root. For each selected block root, traverse k query edges with those u bits and k with the next v chunk. In a short final column chunk, use zero after the v-list ends, until the k-ruler ends. XOR the reached leaf into one finite parity bit. Restart the retained u-chunk for each column block; after the band, advance the main u cursor by k. All resets copy already named roots; there is no address selection by integer.

There are at most n/k compiled bands and ceil(n/k) blocks per band. Routing and edge traversal cost O(n^2/k+n). The XOR of their answers is exactly the contribution of the compiled row prefix because the universal leaf computes each a^T M b and padding is zero.

Next normalize the pending raw band, if present, followed by the current raw rows, into chronological order. For each such row use the next u bit, restart v at its retained first root and scan the present matrix bits. A partial row uses only the corresponding prefix of v. An empty partial row is omitted and consumes no u bit. All missing columns and rows are zero. Reversing and scanning the at most 2nk present coefficients costs O(nk+n), including newly allocated lists. Ignore every unfinished worker product.

The snapshot partition proves that these contributions sum to u^T A^(t) v. This establishes (2) and includes composition, normalization, raw work and final output. A lazy pair of operands is not the endpoint. Queries leave snapshots and prepared vectors intact. Query allocations are separately charged; this note does not claim allocation-free queries or an evolving answer cache.

6. Scope, input size and what has changed

The compact constraint fragments remain $$F_A(x,y):y=Ax,\qquad Q_{u,v}(x,y):(x=v)\land(u^{\mathsf T}y=1).$$ For a complete matrix, boundary width b=2n and coefficient-description size N0=Theta(n^2), including headers. The fixed-shape named CNF encoding has N=Theta(n^2 log n). The specialization (3) therefore gives O(b^2/sqrt(log b)), O(N0/sqrt(log N0)), or O(N/(log N)^(3/2)) query time for these encodings. Loading and historical records are O(b^2), or O(N/log N). This loader consumes the promised coefficient stream, not an arbitrary CNF serialization.

An explicit pointer encoding uses O(n^2 log n) bits at complete readiness, including historical nodes. O(n^2) records must not be equated with n^2+n bits. Data-dependent choices of shared subtree roots also fall outside the earlier fixed-layout linear-bit model. The quadratic theorem is unchanged.

Every arrival runs a fixed number of source primitives; composing those primitives gives a bounded local record transition with fixed constants. The reviewed compiler contract applies to that explicit input client, with fixed finite initialization and the additional native frontier layer. The query phase still takes an unbounded number of steps and needs charged clock actions in a complete compiled recognition client. There is no strict real-time recognition claim for the unpadded query suffix, no free delivery of remote handles, and no unrestricted machine or SAT lower bound. Scaffold-to-PEG recognition would retain its one reversal.

This resolves the proposed readiness test positively: bounded work as coefficients arrive can maintain subquadratic future queries, even for every saved prefix. The earlier count excluding separate full block tables did not exclude shared structure. The result gives a construction in one interface, not a characterization of all maintainable representations.

The mechanism depends on predictable append order. A later arbitrary edit could invalidate summaries anywhere; the proof supplies no bounded edit operation. Improving the logarithmic factor is not necessary for this conclusion. The broader unresolved task is to identify which operation interfaces preserve a bounded unfinished part and which require a genuinely different representation.

Provenance and verification

Tabulation is classical. Ramamoorthy and Rashtchian’s Section 1.4 records the classical polynomial-space vector-matrix-vector upper bound and credits Artazarov, Dinic, Kronrod and Faradzev. That cell-probe result is background, not an imported certificate for this local streaming interface. The universal tree, explicit band job, deadline and prefix partition above give the written operational proof. Scheduling work over subsequent arrivals is also a standard algorithmic idea. Historical novelty of their combination here is unestablished.

Two independent model reviews checked the shared-tree construction, deadlines, storage units, raw-tail routing and prefix extension. The finite checker and output test shared-tree selection and the snapshot partition on small matrices and partial rows. They are a semantic model with host lists, integer indices and recursion; they are not an implementation or verification of the finite-rule scheduler, and do not establish its asymptotic resource bound. That bound follows the written local construction and accounting. Some small algebraic test parameters deliberately lie outside the header promise, so they test identities rather than admissible whole input runs. No proof-assistant verification or universal optimality claim is made.