Flat segments cannot absorb unrestricted catenation

Working research note, 1 October 2026.

Understand when future computational behavior admits a representation maintained by finite rules with bounded local access and bounded allocation, and what structural obstructions prevent such a representation.

Question and answer

Can a fixed number of proper-list segments support both concatenation and head removal, with bounded work per call? Head removal is easy in this representation. Unrestricted concatenation is not: repeated self-concatenation forces exponential word growth, while bounded allocation increases the length of the longest proper list only linearly. This gives an obstruction for every controller within the flat-segment representation, including controllers that prepare auxiliary lists in advance. It is not an obstruction to other persistent sequence representations.

Model and observations

Fix a nonempty finite alphabet, a positive integer s, and a finite immutable initial heap. Proper lists use E and Cons_c(t), with one letter c and one proper-list tail t. Nodes are acyclic. Each new node points to old or earlier new nodes; old records cannot be modified. A descriptor has at most s ordered list pointers, and denotes the concatenation of their words, once per slot. Empty slots may be omitted. Sharing is permitted, including repeated use of the same list pointer in different slots. There are no repeat counts, implicit multiplicities, slices with compressed contents, or nested descriptors in the semantics of a slot. A slot is an ordinary proper list.

Descriptors may be fixed-arity immutable records, with a finite occupancy tag; creating one costs one record. Finite control and auxiliary graphs are allowed, but they do not change descriptor semantics. All fresh records, including background preparation, count toward allocation. Initialization is fixed, finite and independent of the future operation history. Let h be the maximum length of any proper list anywhere in that initial heap.

The observable contract is the decoded word and the letters/status returned by head removal. A concatenation call must return a valid descriptor for uv on descriptors for u and v, preserving all old versions. Calls may pass the same descriptor in both argument positions. Thus the derived single-operation contract double(D) returns a descriptor for ww when D denotes w. Repeating this operation uses only one current handle and a finite operation alphabet. Start with a descriptor for a single letter a, present in the fixed initial heap. An empty initialization followed by a single push gives the same setup with a different fixed h.

Positive constructions below inspect descriptor slots, list tags, and the first tail, never pointer identity. For the negative theorem grant arbitrary inspection of the entire old heap and arbitrary choice of new nodes. This stronger access cannot overcome the allocation bound, so the theorem applies in particular to bounded-local finite-rule controllers. No arbitrary future scaffold-context equivalence is asserted.

The capacity bound

Lemma. If a call allocates k fresh Cons nodes and the previous maximum proper-list length was H, the new maximum length is at most H+k.

Proof. A new proper list follows a chain of distinct fresh Cons nodes until it reaches an old proper list or E. The fresh part contains at most k nodes and the old suffix has length at most H. Old lists are unchanged. Other record kinds cannot appear in a proper-list chain. QED.

Let B_t be the cumulative number of fresh Cons nodes after t calls, counting all preparation and every abandoned intermediate. The lemma gives

H_t <= h+B_t.

Every descriptor with at most s slots therefore satisfies

|word(D_t)| <= s(h+B_t).                         (1)

Repeated pointers do not invalidate (1): there are at most s occurrences, each with length at most H_t. We do not count occurrences of shared nodes as separate allocations.

Theorem (flat-segment growth obstruction). For every fixed s>=1, every fixed finite initialization containing a singleton descriptor, and every constant allocation bound A, no implementation in this model can correctly perform all finite histories of double while allocating at most A total records per call. The same impossibility holds if only cumulative allocation at most At is required through t calls.

Proof. After t successful double calls the decoded length must be 2^t. Since B_t<=At, equation (1) requires

2^t <= s(h+At)                                  (2)

for every t. For fixed s,h,A, the exponential eventually exceeds the linear right side, a contradiction. This does not assume which lists the controller chooses, which states it visits, how it shares nodes, or which auxiliary structures it prepares. QED.

More generally, a representation allowing S_t explicit flat slots at time t must satisfy

S_t(h+B_t) >= 2^t.                              (3)

Thus fixed s requires B_t >= ceil(2^t/s)-h. These are necessary capacity bounds, not sufficient conditions for an implementation or claimed optimal costs for general words. They express a tradeoff between explicit segment capacity and list construction. Descriptor copying, access and control costs can only add obligations. The argument is elementary; its role is to decide whether the proposed representation class merits further synthesis work.

A sharp supplied-heap witness and a sharing pitfall

For n>=1 take a heap consisting of E and a chain for a^n, hence all its suffixes. Let D have s slots, all pointing to that same chain. Its word is a^(sn). A valid output for double(D) has length 2sn in at most s slots, so some slot has length at least 2n. The old maximum is n, and the lemma forces at least n fresh Cons nodes.

This bound is attained for this supplied heap if arbitrary construction time and access are allowed: prepend n copies of a to the old a^n list and use the resulting a^(2n) pointer in all s output slots. This costs n Cons nodes and, when descriptors are heap records, one fresh descriptor. The exact n claim concerns Cons allocation for this family, not bounded-time synthesis for unknown n. A fixed initialization with longer constants is handled by choosing n at least their maximum length.

A tempting but wrong argument charges n new nodes separately to every slot and claims sn. Sharing refutes that claim. The longest-chain proof correctly counts physical nodes once. Unlike the main theorem, this one-call witness alone is about a supplied heap; it would not exclude a controller that kept helpful longer lists. The cumulative theorem explicitly includes such lists.

Positive controls: where flat segments suffice

Maintain a descriptor whose occupied slots are nonempty proper lists. For fixed s, inspecting and rewriting all its slots takes bounded work.

• Push(c): if empty, use Cons_c(E); otherwise prepend c to the first list. Allocate at most one Cons and one descriptor.
• Pop: if empty, return empty status. Otherwise read the first list’s head and replace it by its tail. If that tail is E, drop that slot. Allocate at most one descriptor and no Cons nodes. Determining emptiness of the tail reads its tag; from a descriptor root this needs depth at most three (descriptor to list to tail, with a conservative extra boundary level).
• Concatenate when the two occupied counts sum to at most s: join their slot tuples. Allocate at most one descriptor and no Cons nodes. No list contents are traversed.

These operations preserve descriptor validity and decoded words by direct inspection. Induction from empty descriptors proves all finite histories satisfying the occupancy precondition, including calls on retained versions. The precondition is decidable from finite occupancy tags and does not assume a controller exists. Overflow is not a successful unrestricted concatenation. No scan through an unbounded number of empty segments is hidden here.

Two other controls mark the scope. A binary rope can implement double by one Cat(D,D) node, achieving exponential decoded growth with linear allocation; this leaves the flat-list class. It does not by itself solve efficient head removal. An unbounded explicit slot array can duplicate its entries instead, but the descriptor size and copying are then unbounded. Encoded repetition counts also leave our literal flat-slot semantics.

Literature, contribution and next decision

Okasaki’s 1996 thesis, Section 7.2 and 7.2.1, pp. 91-95, uses structural abstraction and a recursive collection of collections for catenable lists. It obtains constant amortized time there; it is not a theorem about a fixed tuple of ordinary lists. The source explicitly identifies deletion of the distinguished element and restoration of the representation as the creative part. This is the relevant established direction for escaping the flat capacity bound.

Verified Purely Functional Catenable Real-Time Deques is a further primary comparison already studied in the preceding certificate work. Its richer representation must not be ruled out by this flat-segment argument. We import no lower bound or algorithmic theorem from either source into the elementary proof above. Nor is this an information-theoretic lower bound for all word representations: repeated a’s have a short description.

The additional result in this program is the explicit capacity criterion, its all-controller/all-history quantifiers within the stated class, and the resulting rejection of the proposed fixed-segment extension. The chain-growth and exponential-versus-linear ingredients are standard; novelty of this packaging is unestablished. Written proofs are unrestricted in t,s,n. The checker covers finite arithmetic instances, enumerated unary chain-growth states, the sharp witness, and finite push/pop/guarded-concatenation histories. It is not proof-assistant verification.

Decision. Stop seeking unrestricted catenation in a fixed flat tuple of proper lists. Continue the same bounded-realization goal with recursive composition, where one node can retain a whole old sequence as a component. The next decisive question is whether the branchwise synthesis proof extends to pieces of a shared, unbounded level, for example words of length 3^ell. Such words are correlated by length, so arbitrary independent tails cannot simply be assumed after decomposition. Specify rank-blind templates and indexed shape invariants before testing separation and preservation. Use the already inspected catenable source as a concrete test. Identify the precise step where independent-tail separation survives or fails; do not repeat the earlier helper audit or present another standard deque algorithm.

No result here separates languages, forbids all pumping methods, or preserves physical graph behavior under arbitrary scaffold contexts. Any later use of the scaffold compiler must retain native observation and virtual-initialization requirements; a scaffold-to-PEG transfer recognizes the reversed language.