Virtual creases after the fixed-comb theorem

Executive result

The virtual-crease direction now has a clean three-level mathematical separation.

1. For one completed event schedule, minimum persistent tracks are exactly a two-dimensional poset width (the Dilworth result already implicit in PEG Lab’s access-width instrument).
2. An online scheduler may need more tracks than that offline width. There is an explicit width-two schedule family on which every causal scheduler can be forced to use three tracks.
3. More strongly, on a binary scenario tree every completed branch can have offline width one while a uniform causal scheduler needs exponentially many tracks. The missing resource is standby positioning before the future branch is known.

This gives a precise reason the power-tail comb theorem matters. A balanced late selector can create the exponential causal demand. One formed power-tail comb does not: its choices peel serially, and its discriminating events use exactly two constant old addresses.

The result is a theorem about a pinned virtual-track doctrine. It is not yet a lower bound for all PEGs or all palindrome recognizers. The remaining bridge is a universal theorem showing that every presentation in the chosen doctrine must cover a target-defined residual event object.

1. Exact candidate genealogy for even-palindrome residuals

Let

$$x=x_0x_1\cdots x_{T-1}$$

and define

$$S_T(x)= \{r\in\{0,\ldots,T\}:r\equiv T\pmod 2,\ x[r:T]\in\mathrm{PAL}_{\mathrm{even}}\}.$$

The candidate indexed by $r$ has unique committed completion

$$y_r=\operatorname{rev}(x[0:r])$$

and virtual crease

$$\chi_T(r)=\frac{T+r-1}{2}.$$

Theorem 1 — stationary-lineage update

For $b\in\Sigma$,

$$\boxed{ S_{T+1}(xb) = \{T+1\} \cup \{r-1:r\in S_T(x),\ r\ge1,\ b=x_{r-1}\}. } \tag{1}$$

Proof

An old candidate with index $r\ge1$ survives the derivative by $b$ exactly when $b$ is the first letter of $\operatorname{rev}(x[0:r])$, namely $x_{r-1}$. Its remaining completion then has length $r-1$. The new prefix $xb$ always contributes the new full-reversal candidate of length $T+1$. ∎

The surviving candidate’s crease is stationary:

$$\chi_{T+1}(r-1) = \frac{(T+1)+(r-1)-1}{2} = \chi_T(r). \tag{2}$$

Thus the semantic lifecycle is:

• one new candidate line is born at the frontier at every step;
• an old line stays at one absolute axis while it survives;
• it dies at its first mismatching boundary comparison;
• $r=0$ is acceptance, not another query.

This corrects the informal phrase “changing combs split.” Candidate lineages are canonical. Maximal arithmetic-progression or power-tail blocks can split or merge only because a presentation recomputes its cover.

2. Fixed event sets: the exact offline theorem

An event $e=(t,p)$ asks at time $t$ for old integer address $p<t$. A receding finger may hold or move left by one address per step. Define

$$(t,p)\preceq(t',p') \iff t\le t',\qquad p'\le p,\qquad p-p'\le t'-t. \tag{3}$$

Put

$$c(e)=\frac{t+p}{2}.$$

Then (3) is equivalent to

$$0\le c(e')-c(e)\le\frac{t'-t}{2}. \tag{4}$$

So a speed-one receding finger and a half-speed forward virtual crease are the same trajectory in different coordinates.

Theorem 2 — causal Dilworth theorem for a fixed schedule

For every finite, deduplicated event set $E$,

$$\boxed{ \text{minimum persistent tracks covering }E = \operatorname{width}(E,\preceq). } \tag{5}$$

Proof

Events served by one track form a chain. Conversely, between two consecutive events in a chain, compatibility says that the required address drop $d$ satisfies $0\le d\le\Delta t$. Make $d$ left moves and $\Delta t-d$ holds. Hence every chain is realized by one track. Dilworth’s theorem identifies minimum chain-cover size with maximum antichain size. ∎

Product-order normal form

Define

$$X(e)=\frac{t+p}{2},\qquad Y(e)=-\frac p2.$$

Then

$$e\preceq e' \iff X(e)\le X(e')\quad\text{and}\quad Y(e)\le Y(e'). \tag{6}$$

The event order is ordinary two-dimensional dominance. Consequently its width, an optimal track cover, and an antichain certificate can be computed in $O(|E|\log|E|)$ by sorting and patience/LIS methods. This is the same order used in PEG Lab’s src/invariants/access_width.py, written there in the coordinates $(p,t+p)$.

Terminal-interval interpretation

Fix $\tau\ge\max_e t(e)$. From $e=(t,c)$, a track can end at any point of

$$J_e^\tau= \left[c,\ c+\frac{\tau-t}{2}\right].$$

Then

$$e\preceq e' \iff J_{e'}^\tau\subseteq J_e^\tau. \tag{7}$$

One track is therefore a nested family of future-reach intervals. Width is the largest family of pairwise non-nesting intervals—not maximum interval overlap and not maximum simultaneous live-comb count.

Velocity-band generalization

If a one-dimensional track instead obeys

$$v_-\le\dot c\le v_+,$$

use

$$X=c-v_-t,\qquad Y=v_+t-c.$$

The same product order, interval-nesting theorem, Dilworth equality, and $O(n\log n)$ algorithm follow. Virtual creases are the case $(v_-,v_+)=(0,\tfrac12)$.

3. Offline width is not causal track demand

The fixed-event theorem assumes the full event set is known. A streaming machine does not know its future branch when it decides where its fingers wait.

A width-two/three-track adversary

First reveal simultaneous events

$$A=(28,8),\qquad B=(28,12).$$

They require two tracks. Next reveal

$$C=(36,6),$$

which is reachable from either $A$ or $B$.

• If the scheduler assigns $C$ to the $A$-track, reveal $D=(38,0)$. Offline chains are $A\to D$ and $B\to C$, but neither the current $B$-track nor the $C$-track can serve $D$.
• If it assigns $C$ to the $B$-track, reveal $D'=(38,10)$. Offline chains are $B\to D'$ and $A\to C$, but neither remaining current track can serve $D'$.
• Opening a third track at $C$ already uses three.

Thus an offline-width-two family forces three tracks online.

This is an online chain-partition effect. The next theorem is stronger: even the supremum of all completed-path widths can miss the causal resource.

4. Scenario-tree causal track demand

Let $\mathcal T$ be a rooted input-history tree. At node $u$, let $D(u)\subseteq\mathbb Z$ be the set of old addresses that must be serviced at that history.

A $k$-track causal cover assigns a $k$-tuple

$$P(u)=(p_1(u),\ldots,p_k(u))$$

to every history so that:

1. $D(u)\subseteq\{p_1(u),\ldots,p_k(u)\}$;
2. on every input edge $u\to ua$, each physical track holds or recedes: $$p_i(ua)-p_i(u)\in\{0,-1\}.$$

Track births, teleportation, and jump-launch are absent in this doctrine. Adding any of them defines a different resource field.

The least feasible $k$ is the causal track width

$$\operatorname{ctw}(\mathcal T,D).$$

For fixed $k$, feasibility has an exact backward dynamic program: a configuration at a node is feasible iff it covers that node’s demand and each child has some feasible one-step-reachable configuration. This makes causal width a well-defined finite-horizon coordinate, not an analogy.

Always,

$$\max_{\pi}\operatorname{width}(E_\pi) \le \operatorname{ctw}(\mathcal T,D), \tag{8}$$

where $\pi$ ranges over root-to-leaf input paths. The inequality can be exponentially strict.

Theorem 3 — selector-capacity bound

After a common prefix, let $r$ binary input symbols choose a leaf $z\in\{0,1\}^r$. Make no demand before the leaf. At the leaf demand the old address

$$q(z)=(r+1)\operatorname{value}_2(z). \tag{9}$$

Choose the common prefix long enough that every $q(z)$ is a legal old address. Assume all tracks must already exist at the selector root.

Then

$$\boxed{ \max_z\operatorname{width}(E_z)=1, \qquad \operatorname{ctw}(\mathcal T,D)=2^r. } \tag{10}$$

Proof

Every realized path has one event, hence width one.

If one physical track begins the selector at address $a$, then after $r$ recede-or-hold steps its endpoint lies in

$$[a-r,a]\cap\mathbb Z.$$

The possible demanded addresses (9) are pairwise separated by $r+1$, so this interval contains at most one of them. A track can therefore cover the leaf demand on at most one of the $2^r$ branches. At least $2^r$ tracks are required. Conversely, pre-position one track at each $q(z)$ and let it hold. ∎

Without the spacing factor, the same proof gives

$$k(r+1)\ge 2^r \tag{11}$$

for the packed targets $0,\ldots,2^r-1$.

Equation (10) is the exact resource cost of a balanced late-bound selector: the completed run is easy; standby positioning across counterfactual futures is expensive.

Quantifier-order formulation

The separation is not peculiar to the word “track.” It exposes two different orders of optimization:

$$\underbrace{ \max_{\pi}\ \min_{\text{schedule specialized to }\pi} \#\text{tracks} }_{\text{clairvoyant pathwise demand}} \qquad\text{versus}\qquad \underbrace{ \min_{\text{one causal policy}}\ \max_{\pi} \#\text{tracks} }_{\text{uniform presentation demand}}. \tag{12}$$

For the spaced selector these values are $1$ and $2^r$. Thus changing the quantifier order can change the growth class, not merely a constant.

This is an FPRD-level guardrail. A causal presentation resource must be minimized over one horizon-independent rule system before taking the worst-case observation. Minimizing independently on each completed input silently supplies a different, future-specialized presentation on every branch. That is the same sort of tabular interpolant that the FPRD admission discipline is meant to exclude.

5. Why one formed power-tail comb is different

For

$$\{U^jV:0\le j\le M\}, \qquad \ell=|U|,$$

let

$$h=\max\{r\le |V|:V[0:r]=U^\omega[0:r]\}.$$

The genuine exponent-discriminating times are

$$s_j=j\ell+h.$$

At event $j$, the head and next-candidate axes are

$$c_j=c_0+j\frac\ell2, \qquad c_{j+1}.$$

These two event families are chains. In old-address coordinates,

$$p_j^0=2c_j-s_j=2c_0-h, \qquad p_j^1=2c_{j+1}-s_j=2c_0-h+\ell. \tag{13}$$

They are constant in $j$.

Theorem 4 — formed-comb track theorem, sharpened

One already formed power-tail comb’s genuine split events are served by two held old-address fingers separated by $|U|$. If some split genuinely needs both roles simultaneously, the fixed-event width is exactly two.

The crease axes move at maximum speed $1/2$ only because the corresponding old-address fingers hold still.

This supplies the structural contrast:

• a balanced selector reveals one among exponentially many prepositions too late;
• a comb reveals only “head or remaining tail,” then supplies $|U|$ steps before the next promotion, so the same two roles are reused.

6. The changing-comb correction

Along one actual input path, a fixed power-tail block never bifurcates into two simultaneously surviving descendants. Its derivative is empty, a singleton, or one descendant power-tail block.

Three notions had been conflated:

1. Residual branching: the counterfactual next-symbol branches of the exact continuation language.
2. Realized transition: the one branch chosen by the actual next symbol.
3. Recompression: splitting or merging AP/power-tail records when a presentation chooses a new cover.

Only the first is semantic branching. The third is presentation normalization. Candidate lineages remain stationary through it.

A defensible representation must therefore preserve custody of old candidate axes through recompression. It may not mint a track at an old axis merely because a new comb record was created.

7. Why the canonical all-comparisons set is still too large

For a fixed word $w=w_0\cdots w_{N-1}$, define the canonical literal comparison events

$$E_N(w)= \{(t,p):0\le p<t<N,\ w[p+1:t]\in\mathrm{PAL}_{\mathrm{even}}\}. \tag{14}$$

On $w=0^N$, row $t$ has $\lceil t/2\rceil$ simultaneous events. Its width is therefore $\Theta(N)$.

But all those events ask for the same symbol, and the residual is one trivial periodic family. Hence:

The all-comparisons event set is canonical comparison geometry, but its width is not a semantic complexity lower bound.

This is the same warning already recorded around PEG Lab’s standard-eertree access-width measurements: fixed-trace width is exact for that trace, not for all recognizers.

The better intrinsic candidate is the residual decision tree. At future prefix $z$, let

$$J_z=\{r:z\preceq y_r\}$$

and partition it into acceptance and next-symbol cells. A node is discriminating when at least two cells are nonempty. This object is determined by the residual, not by an eertree or maximal-AP convention.

The missing theorem is:

Every exact presentation in a pinned causal-track doctrine induces a cover of enough residual-discriminating cells to preserve their readout.

Without that theorem, residual-discriminating events provide an upper-bound construction and a useful descriptor, not a universal lower bound.

8. FPRD admission

Virtual creases can be admitted now, but as three distinct doctrines.

For relational traces, a presentation’s semantic map remains a function: its value is a set of possible traces, as in M10. The correctness quantifier must be explicit. Existential/angelic correctness is unsafe for PEG comparison because it can guess the future; use exact trace semantics, deterministic history-resolved control, or demonic correctness.

A core M33 resource vector should keep at least

$$\kappa(P)=(k,s,b,r,\ell)$$

separate:

• $k$: persistent tracks;
• $s$: finite control states;
• $b$: births/retargetings per step;
• $r$: rule-description size;
• $\ell$: jump or launch latency (or a symbol saying none is allowed).

Track count alone is likely a collapsed projection when arbitrary control or teleportation is free. The meaningful quantities are constrained sections of the joint Pareto field.

The arbitrary finite scenario-tree assignment is itself a tabular interpolant. For kernel-level use, presentations must be finite, horizon-independent rule systems. Finite-tree causal width remains an auxiliary descriptor and lower bound until the non-triviality and universal factorization obligations are discharged.

Physical folding stays downstream:

• a physical fold trace may forget to a virtual incidence trace, allowing virtual lower bounds to transfer if resources are monotone;
• a virtual upper bound does not lift to paper without a flat-foldability and layer-order realization theorem.

9. What moved

Before this run, the frontier was:

Determine the width of a changing union of power-tail comb events.

That question was subtly misposed. Comb identities are not semantic lineages, and offline width forgets the causal positioning problem.

The new frontier is:

$$\boxed{ \text{residual scenario tree} \longrightarrow \text{finite causal role factorization} \longrightarrow \text{configuration-valued track policy} \longrightarrow \text{FPRD Pareto field}. }$$

The concrete gains are:

1. exact stationary candidate genealogy;
2. exact product-order/Dilworth and terminal-interval forms;
3. exact offline-versus-online separation;
4. exact exponential scenario-tree separation;
5. a sharpened two-constant-address interpretation of the formed comb;
6. a proof that maximal-comb splits are presentation artifacts;
7. a precise admission boundary and the universal theorem still owed.

10. Highest-value next theorem

The next major target is a residual–causal-track factorization theorem.

For a pinned finite-controller, no-teleport track doctrine:

1. construct a target-defined residual scenario object;
2. prove every correct presentation induces a finite causal factorization of that object into role cells and persistent track channels;
3. prove the converse compilation;
4. identify the constrained state/track Pareto frontier with minimum factorization resources;
5. make antichains and selector subtrees sound lower-bound certificates.

The palindrome load case is then sharply posed:

• C090 forbids the balanced selector inside one urgent residual;
• one formed comb has causal width two;
• the remaining question is whether repeated promotions and set-valued recompression can create an unbounded causal factorization demand without reintroducing presentation-specific events.

That is a larger and more faithful FPRD question than counting live combs.