Sparse completion certificates: preparation without full levels

10 October 2026. Assessment 202. Written supporting construction and restricted failed transfer, independently reviewed. Native theorem 66 remains unchanged. This is not a new SAT recognition theorem or an external novelty claim.

Outcome

Complete binary levels are sufficient but unnecessary to fund a serial producer. A sparse row closed under flipping the last bit supplies a distinct later witness for each pair-construction job. The checked closure forces all jobs to finish before the right boundary, and the finished ordinary terminal trie answers content-sensitive queries. It does not give the truncated composition-work bound required by theorem 66. A preparation/deadline tradeoff below rules out eager ordinary-trie output before late pins, even with arbitrary charged preparation.

This separates two obligations that a semantic relation quotient does not charge: preparation of an individual completed predicate, and disturbance of all pending compositions when that predicate is selected. The first has a sparse-input solution below. The second remains the decisive problem.

1. Exact contract and controls

Use the ordinary right-first Horn encoding and fixed native model of theorem 66. A right row is a finite set X of nonempty binary target suffixes. Repetitions and arbitrary row interleaving are permitted. Require

$$p0\in X\quad\Longleftrightarrow\quad p1\in X$$

for every finite binary p, including the empty prefix. No pair list, length, decomposition, ruler or ready handle is supplied. Membership of the empty word is disallowed by a finite syntax flag.

The claimed output is a prepared row predicate at a boundary where all rows pass this closure gate: a standard immutable binary trie with a terminal flag at each node. Missing children are EMPTY. It has no deferred path capsules, union nodes, global lookup oracle, inherited acceptance masks or address tests. A query is charged for the actual row name followed by its actual target bits. It follows one child per bit and reads the final terminal flag; both positive and negative answers are local. This is row access, not arbitrary union of selected rows or free independent-store composition.

Section 12 already supplies arbitrary-name capsule row access. The maintained reader sections 32, 33, 34 provide content-sensitive reuse for common width, bounded width spectrum, or a linear mixed-prefix budget in a shared class universe. Their streamed cutoff capsules handle an arriving word without a backward delimiter walk. This construction does not replace those results or count their content-sensitive readout again. Its narrower contribution is to permit a separate serial producer to finish an ordinary materialized representation using sparse mandatory completion input, without a row-name/target-length compatibility gate.

2. The general witness schedule

Suppose jobs are released after ordinary words. Job i has cost at most $a(n_i+1)$, $n_i\ge1$. For every released job, a checked final property guarantees a later whole word of length $n_i$, called its witness. Suppose each actual witness word is used by at most d jobs, where a and d are fixed. Serve an ordinary work-conserving FIFO worker at rate 4ad per later target bit; unused service is discarded. Row-name bits, delimiters and EOF supply no credit in this argument.

If work remains at a passing boundary, consider its last uninterrupted busy period. Every job released in that period has its witness entirely inside it. If T is the number of target bits in the period, bounded witness multiplicity gives $\sum_i n_i\le dT$. Released work is at most $2a\sum_i n_i\le2adT$, whereas the still-busy worker receives 4adT steps. This is impossible. A batch that empties the worker ends that busy period; a later release starts a new one. The period begins at a release delimiter, so the word that caused that release contributes no prepaid service.

This is an adaptation of theorem 66’s completion argument, not a new scheduling lower bound. The substantive premise is a locally checked, release-respecting, bounded-multiplicity witness assignment. Mere final input length is insufficient. For example, an arbitrarily long earlier prefix followed by a first-width final singleton leaves a newly released positive-cost job unpaid. A later word shared by unboundedly many jobs is also insufficient at any fixed rate. Neither failure excludes a streamed producer that prepares the answer before release.

3. Check sibling completion on the actual input

Retain the ordinary foreground capsule dictionary of target words from the existing constructions. When the final bit of w=pb is consumed, retain the old endpoint terminal flag and the other child’s terminal flag at parent p. If the endpoint was already terminal, this is a duplicate and changes nothing. Otherwise, if its sibling was absent, this is the first member of the pair; if its sibling was present, it is the second.

Maintain one global unary count of half-present pairs across all rows. A first member increments it and a second member decrements it. No deletion occurs and each word belongs to exactly one such pair, so the counter is nonnegative and zero exactly when every observed pair is complete. The same target can also be a prefix of other targets; terminal flags, not existence of child subtrees, determine pair membership. Save the final parent observation while reading the final bit, rather than locating p after the delimiter. The current row’s foreground and worker fields are published together through the inherited outer-name capsule. Never restore a delayed captured row header or global counter.

During the word, retain a strict persistent FIFO of its bits and a unary length ruler. Save the FIFO root before appending each bit. At the delimiter that saved root is the ordinary forward route p. On a first member enqueue this root and the length ruler as one job. A second member or duplicate releases no job. All copies are bounded pointer fields, and every FIFO operation and discarded snapshot is paid by the word that created it.

Each first member has, on every passing input, its other member later in the same row. It has equal positive length. Different jobs have different (row,p) pairs, so these witnesses are distinct: $d=1$. The foreground gate is immediate and does not depend on worker completion. Closure may temporarily fail and later become true.

4. An explicit materialized producer and its readout

Each row owns one serial worker, a strict job FIFO and a committed ordinary terminal trie. A job for p of length $n-1$ takes the current committed root when it starts. Walk its saved forward route, one bit per local step, saving immutable frames containing the old terminal flag, direction and sibling. Missing subtrees supply virtual empty nodes. At p, set the terminals of children 0 and 1 to true, preserving their existing descendants. Preserve p’s own terminal flag. Return through the saved frames, allocating an ordinary node per frame; commit the resulting root and take the next job.

The route has $n-1$ bits. Descent, the two fixed child changes, ascent and commit require $O(n+1)$ bounded local actions and new nodes. Fix a uniform a covering the inherited FIFO primitives and these phases. The worker receives 4a actions on each later actual target bit of its row. Other rows have separate continuations, resumed after their next charged name lookup; interleaving cannot consume or duplicate their service. Only this serial worker changes its committed trie, so queued jobs need no rebase and completed jobs cannot restore old roots.

At any intermediate moment, the committed trie denotes the closure of the pairs whose jobs have committed. It can contain a mate that has not yet appeared. It is not an exact current-prefix predicate. The foreground literal dictionary remains exact. At any passing boundary, the witness schedule proves that every queue and active job is empty. Every observed pair is then complete, so the materialized root equals X exactly. No boundary traversal or queue drain is used. Retained versions passing the gate remain exact; a nonpassing snapshot is not exported as exact merely because its worker is empty.

A later ordinary row name routes to this root with charged lookup. Every query bit selects one old child, and the final terminal bit decides membership; encountering EMPTY yields a persistent false state. A fixed number of such already selected row predicates can be queried in a fixed product, charging all routes and observations. There is no all-row enumeration or independent-store join.

Fixing the inherited strict persistent sequences, dictionaries and packing compiler fixes the degree, radius, labels, finite control and per-symbol batch. Input is read in the stated ordinary orientation from empty initialization. The foreground validator, bit routes, queues, descent/return frames, stale snapshots, allocation, old-storage observations and output cost $O(N)$ logical work and retained records for actual encoded length N. The same fixed-batch packing uses $N+1$ physical nodes and $O(N\log(N+2))$ explicit pointer bits. No padding, advice, preprocessing, free EOF work, external handle, identity/address comparison or metadata/timing side channel is granted. This statement supplies a producer and row reader; it does not assert a new composed SAT language or transfer a PEG consequence beyond established recognition constructions.

5. Carry the attempt into composition: three failures

Radial answers lose content. For $n\ge2$, $X=\{0^n,0^{n-1}1\}$ and $Y=\{10^{n-1},10^{n-2}1\}$ are sibling-closed and occupy exactly the same length. They have the same radial band tree and every radial mixed budget. Nevertheless the ordinary target $0^n$ is present only in X. Negating the reachability answer reverses the corresponding pinned SAT outcomes. A length-only output cannot be repaired by faster enumeration; it omits the required observation.

Materialized content is too expensive for the old release bound. A single sibling pair at length n has n internal coordinates in its ordinary trie (including the root, excluding its two terminal leaves). Merging it into a nonempty conflicting singleton-pair trie can traverse a common prefix of length $n-2$ and requires $\Omega(n)$ return frames in this interface. Theorem 66 requires $O(k)$ additional work through band index k, where n is of order $2^k$. Preparation can be fully paid while this later union cost still violates that interface. More precisely, let the two rows be the sibling pairs below $p=0^{n-1}$ and $q=0^{n-2}1$. At every common-prefix depth 0 through $n-2$ the union has four residual words, whereas every nonempty input residual has one or two. None of these $n-1$ union residuals is an input node, and their different suffix lengths make them mutually distinct. A materialized join using only its two input tries therefore allocates at least $n-1$ new nodes, even with sharing. Earlier prepared joint variants or a different output form are outside this restricted contract. Empty-destination sharing does not fix this worst case. This is an interface mismatch, not a native-language lower bound: compressed paths, pending direct predicates and a different scheduler are not excluded.

Sibling closure and per-width simplicity do not imply a shared mixed budget. For a power of two $L\ge4$, take

$$X_L=\bigcup_{n=L}^{2L-1}\{0^n,0^{n-1}1\}.$$

There are L distinct widths in one class; each width slice has only $n-1$ mixed prefixes in its exact-width universe. Thus no fixed width-spectrum K covers all $X_L$. In the shared class universe U containing all words of lengths L through $2L-1$, the mixed prefixes are all zero-path prefixes at depths 0 through $2L-3$ and the terminal off-path words at lengths L through $2L-2$. The off-path words at shorter-than-maximum lengths lack their extensions. The zero prefix at depth $2L-2$ is full: its own terminal and both children are present. Hence $P_U(X_L)=(2L-2)+(L-1)=3L-3$. This family is already covered by section 34 with $C=3$, subject to its name compatibility gate. It is a control, not a new reuse theorem.

To see that the preparation certificate alone does not imply any fixed shared budget, take all sibling pairs at width L, and one sibling pair at width $2L-1$. Closure holds, while every prefix through depth L is mixed in U, giving $P_U\ge2^{L+1}-1$. This case has a bounded width spectrum, so section 33 can cover its suitably named encoding. It refutes only the proposed implication from closure to the aggregate budget. It does not separate the union of all older sufficient classes.

5.1 Carry the obstruction through arbitrary charged preparation

The two-input example excludes only reuse of the actual input nodes. A stronger restricted contract permits arbitrary preparation but requires one ordinary exact materialized terminal trie after every completed left block, before any late target pin is supplied. Auxiliary data and arbitrary local scheduling are allowed; pending OR predicates, compressed edges and inherited acceptance masks are not permitted in the required output. A node’s children and terminal bit alone must denote its residual language. Physical identity, addresses, metadata, timing and control flow do not change that denotation.

Let $q=2^m$, $m\ge1$, and choose q distinct ordinary intermediate names $v_i$ of length m. For an arbitrary $H\ge1$ define $n=H+m+1$ and prepare right rows

$$X_i=\{0^H v_i0,0^H v_i1\}.$$

All rows satisfy the sparse closure gate. The right records have actual length

$$N_R=2q(9+m+n),$$

using the established ordinary Horn syntax. There is no padding. Use the same one-bit source name u for all later selections. Every nonempty subset T of rows can be selected with at most

$$L=q(11+m)+c_0$$

actual left/phase characters, for a fixed syntax constant $c_0$. No query target has arrived yet.

For each depth $d=0,\ldots,H$, the output after selecting T has a node at common prefix $0^d$, with residual language

$$\{0^{H-d}v_i b:i\in T,\ b\in\{0,1\}\}.$$

For fixed d, different nonempty T give different residual languages. Different depths have different positive residual word lengths, so none of these nodes can coincide across depths either. Sharing cannot identify nodes with distinct residual languages. Across all possible T there are therefore exactly $(H+1)(2^q-1)$ required distinct residuals of this form.

Suppose P records were prepared before the selections, counting initialization and all preparation, and the algorithm can allocate at most B records per subsequent actual symbol. Some T has at most $P/(2^q-1)$ of its $H+1$ required nodes already available. Even allowing all left symbols to build that output, it must allocate at least

$$H+1-\frac{P}{2^q-1}$$

new records. A necessary condition for the declared output contract is

$$H+1\le \frac{P}{2^q-1}+BL.$$

This is a preparation/deadline tradeoff, not just an output-size observation: each individual result has a linear-size shared prefix, but the same pre-query preparation must serve every later selection subset.

For any fixed native implementation, $P\le A(1+N_R)$ for a fixed A; fixed initialization is included by increasing A. First choose a power-of-two q so large that $2^q-1>8Aq$. Then choose H sufficiently large that m+10 is negligible compared with H and $BL<H/2$. The displayed necessary inequality fails. Thus no one fixed native implementation can meet this ordinary materialized-output-at-left-boundary contract on all these sparse rows, even with arbitrary charged linear preparation. The argument counts distinct semantic residual nodes, not pointer bit capacity, and adds no communication side channel. A nonuniform family whose constants depend on q is a different assertion.

The deadline is deliberately stronger than language recognition: the native task normally permits the late pin’s actual bits to pay for readout and can retain pending shared predicates. Those operations are exactly what the restricted contract excludes. This result does not rule out persistent recognition, compressed-spine output, preparation of shared auxiliary views, or the existing bounded-window constructions. It tells the next construction to preserve a queryable pending form rather than insist on an eagerly materialized union.

6. Exact surviving target

The sparse completion certificate resolves a paid producer subproblem but does not remove either of the consumer gates above. The next mathematical test is a prefix-dependent depth profile: represent the zero-spine comb $X_L$ and its ordinary-name-selected unions with long, differently located spines. Charge both shared prefix comparison and the length-profile union; preserve a bounded number of directly queryable pending contexts while arbitrary short intermediate names select long rows. Start with two spines having a long common prefix and distinct sets of terminal depths. Neither a free longest-common-prefix oracle nor an uncharged terminal-depth mask is allowed. Compare section 33.7 and section 34 before claiming a new class. Independent-store joins and unrestricted radial profiles remain separate.

The already completed replay controls charge each fork separately; affine-fragment joins do not supply a new coordinate map; persistent causal sharing does not pay a query; unary coherent controls do not identify content-bearing branches. Entry 129’s established quotient and growing-alphabet state/port bounds remain unchanged. None is used here as an information-size explanation of local access.

Evidence, independent review, failed-route reopen gates and publication disposition are recorded in assessment 202. The accompanying finite audit models immutable trie frames, pair gates, interleaved worker service, exact eligible snapshots, incomplete boundaries and the explicit mixed-count controls. Its Python sets and integers are semantic oracles, not native primitives.