Persistent meanings and changing support coordinates

12 October 2026. Assessment 215. Primary-proof review and editorial pass. Native construction 71 and the mathematical target remain unchanged.

What the comparison resolves

Keeping an old row’s meaning and making that row cheap to combine with a new support are different operations. Classical persistence supplies the first; Patricia trees show how absolute keys can keep their meanings when a new branch is inserted. Neither result supplies the support-relative child views and short-alias merge bound required by frozen-support construction 71.

The useful next test remains a versioned-support adapter: retain an old FULL together with its old support, insert one branch, and immediately select that row by a short ordinary alias. The adapter must expose current-coordinate children, preserve literal membership and account for changed mixed budgets before the answer deadline. This review narrows the missing contract; it does not claim a new native theorem or a general lower bound.

Three complete primary arguments

Driscoll, Sarnak, Sleator and Tarjan, Making Data Structures Persistent, Journal of Computer and System Sciences 38 (1989), 86–124. All 39 pages were reviewed. The linked model fixes fields and entry pointers (§1, pp.87–89). Fat nodes trade logarithmic access for unrestricted indegree. Bounded-indegree node copying pays predecessor cascades with a potential (§2.3, pp.93–97); full persistence adds version order, inverse pointers and validity-interval repairs (§3.3, pp.100–108). Both give constant access overhead but amortized updates. Lazy recoloring and displaced-record invariants yield search-tree-specific worst-case bounds (§§4.2–5, pp.112–121). Combining versions and simultaneous multiversion changes remain separate questions (§6, p.123).

Okasaki and Gill, Fast Mergeable Integer Maps, ACM SIGPLAN Workshop on ML (1998), 77–86. All ten scanned pages were read. Sections 2–3 retain absolute leaf keys and internal prefix/branching-mask integers while removing unary structure. Complete-key comparison validates membership. With constant-cost word primitives and collision combination, lookup and insertion cost $O(\min(n,W))$ for $n$ bindings and word width $W$; general merge costs $O(n_0+n_1)$ (§4, pp.81–83). Merge treats equal, nested and incompatible prefixes separately, sharing both trees beneath one branch in the incompatible case. Bit disagreement uses word primitives; the big-endian variant explicitly searches for the highest set bit (§5, pp.83–84). Section 6 reports benchmarks. The university’s old PDF route returned 404; the archived author PDF supplied the original scan.

Midtgaard, QuickChecking Patricia Trees, TFP 2017 revised selected papers (2018), 59–78. All 20 manuscript pages were reviewed as a necessary correction companion. Sections 3.1–3.5 compare generated set-operation expressions with a sorted-list model through an abstraction function. Section 3.6 explains why uniform or small integers can miss machine-boundary errors. Sections 3.7–3.8, manuscript pp.11–15, isolate union of $\{\mathrm{min\_int},0\}$ and $\{\mathrm{min\_int},1\}$: signed ordering of one-bit masks mishandles the sign-bit branch and creates duplicate enumeration. The repair orders masks as unsigned values. The original SML merge contains the same signed comparisons; affected implementations were corrected. This is a concrete failure and repair, not a universal proof obtained from random tests. No algorithm listing is copied here; the original scan supplies the algorithm, and the companion supplies the signed-mask correction.

Which costs transfer, and which do not

The following is the Lab’s applicability analysis, not an additional theorem attributed to these papers.

A fixed word width gives a bounded key universe. A growing word width grants operations on growing labels. Neither choice by itself establishes one fixed automaton for unbounded ordinary binary names. Likewise, fixed outdegree in the native model does not establish the bounded indegree hypothesis of generic node copying: many row or source roots within one represented version can share one node; sharing only across historical versions does not itself violate that hypothesis. Version identifiers, addresses, timing and control flow cannot be used as uncharged answers or communication channels.

The deadline issue is also separate from total cost. An amortized constant update overhead can hide a long individual repair; a logarithmic operation may exceed the available short alias. Retaining a repair description helps only when its observable interference is bounded and every subsequent access has a charged schedule. DSST’s displaced-record invariants are a useful example of such a proof obligation, not a ready native implementation of support migration.

Carrying version retention through the composition boundary

Write an old row as $(U_0,X)$ with $X\subseteq U_0$. Retaining both immutable roots preserves its meaning after active support becomes $U_1\supset U_0$. For example, $U_0=X=\{00\}$ is FULL in the old support. After another row introduces 01, that old FULL must still reject 01. Keeping the old support and using the existing literal validator preserves this answer without eagerly rewriting every row.

But construction 71’s splice asks for children in one shared coordinate tree. Relative to $U_1=\{00,01\}$, the old predicate now has children FULL and EMPTY. Merely retaining the old root does not explain how those current children are obtained, what their mixed-budget contribution is, or how much work a selected-row merge performs. A chain of retained support adapters also needs a bound on traversal or an input-paid flattening mechanism. This is the exact point at which the naive persistence transfer stops.

The bookkeeping has a related obligation. Take common alias width $\ell=2$ and $C=1$. Rows named 00 and 01 both denote $\{0000\}$. Another row, named 10, adds support targets 0001, 0010 and 0100. Each unchanged row’s mixed count is successively 0, 1, 2 and 3. The final addition changes both old budget-validity flags without either old row receiving a record. The existing invariant that a record changes at most its own row’s contribution cannot simply be reused. A common cohort or shared summary might represent that collective change cheaply; no lower bound on all representations follows from this diagnostic.

A row satisfying $M_U(X)\le C\ell$ may contain arbitrarily many keys, so replacing FULL-aware views with an explicit integer map loses the desired alias-based guarantee. Nor may the final literal check be dropped: Patricia’s complete-key equality performs the rejection that construction 71’s streamed support validator must perform for skipped unary paths.

The earlier creation-order geometry failure remains relevant: immutable injective codes alone do not preserve a cheap union geometry. Theorem 70 and theorem 71 remain different checked subclasses. Replay still pays each traversal; affine joins still need their coordinate hypotheses; persistent causal and unary coherent algebras do not themselves maintain a branching current union. Entry 129’s growing-alphabet state/port results remain imported results with their original interface assumptions. This comparison gives neither a native language lower bound nor a direct PEG transfer; native recognition retains the reversal convention.

Classification and next decisive test

Construction 71 is best classified as an extension of the Lab’s coherent-cutoff and asymmetric-splice constructions. Confidence is high in that internal classification. Its checked first-row preparation, literal validator, mixed-budget gate and strict pending schedule are additional content beyond generic persistence or Patricia merging. The present comparison does not establish external originality of that combination. The concrete remaining uncertainty is whether a versioned support adapter can preserve those contracts under late growth, not whether ordinary persistent trees can retain old roots.

Allow a later support expansion while preserving previously built row predicates, their mixed budgets and constant local child views. Begin with one added support branch after many completed rows and an immediate short-alias selection; charge old-view conversion to the expanding record or a proved later ordinary-input witness. Retain literal validation and current source semantics. Variable alias service widths, nested ownership holes, clipped intervals and independent-store joins remain separate.

Do not replace this target with a general compiler exercise or an information-size argument. Begin with one added branch after many completed rows; expose the exact current child observations and mixed-budget change, then test the next short selection and immediate negative pin. Repeated growth additionally requires a bound on adapter depth. No supplied handles, padding, advice, free preprocessing or EOF drain may pay that work.

Editorial scope and verification

The pass covers the current checkpoint, constructions 69–71, the context-code geometry note, assessments 210–214, their research/code links and this review. The fixes and verification scope are recorded below. Historical result statements and stable routes are preserved. The homepage research date, publication ranking, root claims and mathematical counters are unchanged.

Primary PDFs, extracted text and OCR stay outside public source. The review records paper identities and source hashes in the integration receipt. Reviewed evidence, claims and history remain in GitLab; generated readings have one maintained source. No source listing is retyped or hand-maintained in a second copy.

Fixed visible missing spaces in historical checkpoint prose and 15 headings while retaining their original heading IDs. Converted five plain artifact references into readable links. Added the two missing historical checker projections; existing pending-substitution and review readers are reused. The geometry note now identifies construction 71 as a support-first successor, and construction 70 links both the geometry failure and the separate construction 71. Construction 69 already links its successor and needed no edit.

Rendered HTML, KaTeX, reading links, fragment destinations, source highlighting, every source-line anchor and exact raw-download bytes are inspected after the build; final scoped counts and outcomes are retained in the integration receipt. This includes newly linked historical source readers, not just the newest checker. No mathematical code or proof statement is changed. The existing full-suite failures are retained; this editorial and literature update uses scoped checks rather than rerunning unrelated compiler gates.

Browser viewport review is unavailable under the supported Sites workflow. Responsive layout and visual clipping remain unverified; a successful build is not presented as visual inspection.

Both the primary review and editorial duties complete scheduled 120 once. Mathematical count 134, window zero, reassessment 134 and native construction 71 remain unchanged. Next scheduled 121 is research; next primary review 125 and editorial 126. Publication is complete only after a pinned GitLab projection, terminal Site deployment and exact source-parity receipt. The installed legacy reverse writer remains a separate unverified follow-up.