FPRD cycle dual and gauge-reduced parity-comb theorem

Prepared: 29 July 2026
Status: proof package; the parity-comb theorem has been independently reconstructed twice
Novelty status: not assessed; make no novelty claim
Intended recipient: FPRD repository lead lane

0. What is already closed

The state-conditioned raw/canonical height theorem has been verified and captured at repository commit ba233faf. In particular,

$$h_{f,\le n}(N) \le H_{f,\le n}(N) \le (n+1)h_{f,\le n}(N).$$

The first inequality is an inequality between optimized sections. It is not the false pointwise assertion $h(M)\le H(M)$ for every individual presentation.

No further work on that theorem is requested here. This packet contains the next two results.

Part I. Exact cycle-mean dual for raw height on a fixed presentation

1. Augmented presentation graph

Let $M$ be a nonempty trim deterministic sequential integer-weighted machine. Form its augmented graph $\overline G_M$ by adding a boundary vertex $\ast$:

• each transition $e:p\to q$ is an oriented edge of weight $w(e)$;
• the initial weight is an edge $\ast\to q_0$;
• each final weight is an edge $q\to\ast$.

Extend a state potential by $z(\ast)=0$. Under the sign convention used here,

$$w^z(e) = w(e)+z(\operatorname{tail}e)-z(\operatorname{head}e). \tag{1}$$

This is the sign reversal of the repository’s literal gauge convention and is identical after replacing $z$ by $-z$.

For an oriented closed walk $C$, define

$$\operatorname{circ}_w(C) = \sum_{\text{forward traversals}}w(e) - \sum_{\text{backward traversals}}w(e), \tag{2}$$

and

$$\rho(w) = \max_{C\ne\varnothing} \frac{|\operatorname{circ}_w(C)|}{|C|}. \tag{3}$$

Put $\rho(w)=0$ if the graph has no edges.

Theorem A — exact $L^\infty$ gauge dual

For every finite oriented multigraph with integer edge weights,

$$\boxed{ \min_{z:V\to\mathbb R} \lVert w+\delta z\rVert_\infty = \rho(w) } \tag{4}$$

and

$$\boxed{ \min_{z:V\to\mathbb Z} \lVert w+\delta z\rVert_\infty = \lceil\rho(w)\rceil. } \tag{5}$$

Consequently,

$$\boxed{ \min_{\text{integer state gauges }z}h(M^z) = \left\lceil \max_C \frac{|\operatorname{circ}_M(C)|}{|C|} \right\rceil } \tag{6}$$

on the augmented presentation graph. Initial and final weights are included; there is no extra parity or integrality loss beyond the ceiling.

Proof

Gauge leaves every circulation invariant. Therefore

$$|\operatorname{circ}_w(C)| \le |C|\lVert w+\delta z\rVert_\infty,$$

which proves the lower bound.

For the converse, fix $t\ge\rho(w)$. Replace every oriented edge $e:u\to v$ by two arcs in a difference-constraints graph:

$$u\to v\text{ of length }t+w(e), \qquad v\to u\text{ of length }t-w(e). \tag{7}$$

The corresponding constraints are exactly

$$-t \le w(e)+z(u)-z(v) \le t. \tag{8}$$

Every directed cycle in the auxiliary graph is an oriented closed walk $C$ of length

$$t|C|+\operatorname{circ}_w(C),$$

which is nonnegative by the definition of $\rho$; reversing the walk handles the other sign. Thus the constraints have no negative cycle. Shortest-path potentials in each connected component give a feasible real potential and prove (4).

When $t$ and $w$ are integral, all auxiliary arc lengths are integral, so the shortest-path potential is integral. Set $t=\lceil\rho(w)\rceil$ to obtain (5).

Interpretation and prior-art boundary

After optimal weight pushing on a fixed graph, raw height is a maximum mean circulation. A pinned access-tree normalization can concentrate the total circulation on one chord or final coordinate. The raw/canonical gap is therefore a mean-versus-total effect on a fixed presentation.

This theorem is an application of standard difference constraints and maximum-cycle-mean / max-plus potential duality to the skew-symmetric bidirected expansion. Record it as useful infrastructure, not as established novelty.

Part II. One fixed target with a linear repaired height gap

2. Repaired coordinates

For a partial integer-valued target $g$, define

$$\widehat h_{g,\le n}(N) = \min_{\lambda,c\in\mathbb Z} h_{g+\lambda|\cdot|+c,\le n}(N), \tag{9}$$

$$\widehat H_{g,\le n}(N) = \min_{\lambda,c\in\mathbb Z} H_{g+\lambda|\cdot|+c,\le n}(N). \tag{10}$$

This is exactly the repository’s global length-and-constant repair.

3. The parity-comb target

Let $L_j=2^j$, and over the fixed alphabet $\{a,b,c,d\}$ define

$$w_j= \begin{cases} b^jca^{L_j},&j\text{ even},\\ b^jcd^{L_j},&j\text{ odd}, \end{cases}$$

$$\operatorname{dom}(f)=\{w_j:j\ge0\}, \qquad f(w_j)= \begin{cases} +L_j,&j\text{ even},\\ -L_j,&j\text{ odd}. \end{cases} \tag{11}$$

For $k\ge3$, put

$$N_k=k+1+L_k.$$

Let $e$ and $o$ be the largest even and odd indices at most $k$, and write $E=L_e$, $O=L_o$. Thus

$$\{E,O\}=\{L_k,L_k/2\}.$$

Set

$$n_k=k+E+O+2 = k+\frac32L_k+2. \tag{12}$$

Theorem B — gauge-reduced linear separation

For the single fixed target $f$, along the horizons $N_k$,

$$\boxed{ A_f(N_k)=n_k, \qquad \widehat h_{f,\le n_k}(N_k)=1, \qquad \widehat H_{f,\le n_k}(N_k)=\frac34L_k. } \tag{13}$$

Consequently,

$$\boxed{ \frac{\widehat H_{f,\le n_k}(N_k)} {\widehat h_{f,\le n_k}(N_k)} = \frac34L_k = \frac12n_k-\frac{k+2}{2} = \left(\frac12-o(1)\right)n_k. } \tag{14}$$

Thus the global length-and-constant repair does not collapse canonical height to raw height, even on one fixed target over one fixed alphabet and after both coordinates are minimized over all presentations at the exact minimum state budget.

4. Why the state budget forces the graph

The support residuals visible through horizon $N_k$ are exactly:

• $k+1$ spine residuals $q_0,\ldots,q_k$;
• $E$ positive $a$-countdown residuals $\{a^m\}$;
• $O$ positive $d$-countdown residuals $\{d^m\}$;
• the final residual $\{\varepsilon\}$.

They are pairwise distinguishable within the horizon. In particular:

• different countdown lengths are separated by the shorter accepting suffix;
• different spine positions have different supported continuations;
• identifying an $a$-countdown with a $d$-countdown accepts a malformed mixed-carrier word;
• identifying a spine state with a countdown or final state similarly accepts a malformed word.

Therefore every correct deterministic presentation needs at least

$$(k+1)+E+O+1=n_k$$

states. The evident comb attains the bound. Since the support exhausts the entire state budget, every at-most-$n_k$-state competitor has the same support quotient, one shared final endpoint $r_0$, and the same forced support-path transitions.

5. Why the BFS normalization is forced

The unique shortest access to $q_j$ is $b^j$. For every positive $a$-countdown state $A_m$, the unique shortest access is

$$b^jca^{L_j-m},$$

where $j$ is the least eligible even index. The $d$-chain statement is the odd analogue. Appending the known accepting suffix to any competing access of no greater length would create a second supported word within the horizon, which proves uniqueness, including against equal-length alternatives.

The shared final endpoint has the unique shortest access

$$ca=w_0.$$

Hence the BFS tree is independent of letter-order ties. The mandatory non-tree coordinates are the same-parity boundary edges and the final negative merge edge

$$D_1\xrightarrow d r_0.$$

6. Exact repaired canonical coordinates

Let

$$g_{\lambda,c}(w)=f(w)+\lambda|w|+c, \qquad \Delta_j=L_j-L_{j-2}=\frac34L_j.$$

Every at-most-$n_k$-state presentation has the following forced canonical coordinates:

$$e_j^+: \quad (1+\lambda)\Delta_j+2\lambda \qquad(j\ge2\text{ even}), \tag{15}$$

$$e_j^-: \quad (\lambda-1)\Delta_j+2\lambda \qquad(j\ge3\text{ odd}), \tag{16}$$

$$D_1\to r_0: \quad -3+2\lambda, \tag{17}$$

$$\tau^{\mathrm{can}}(r_0) = 1+2\lambda+c. \tag{18}$$

The evident comb realizes the exact fixed-gauge formula

$$\begin{aligned} H_{g_{\lambda,c},\le n_k}(N_k) =\max\{& |1+2\lambda+c|,\ |-3+2\lambda|,\\ & \max_{\substack{2\le j\le e\\j\ \mathrm{even}}} |(1+\lambda)\Delta_j+2\lambda|,\\ & \max_{\substack{3\le j\le o\\j\ \mathrm{odd}}} |(\lambda-1)\Delta_j+2\lambda| \}. \end{aligned} \tag{19}$$

For integer $\lambda$:

• $\lambda=0$ leaves the latest boundary at $3L_k/4$;
• $\lambda\ge1$ makes the latest even boundary at least $3L_k/4$;
• $\lambda\le-1$ makes the latest odd boundary at least $3L_k/4$.

At $(\lambda,c)=(0,0)$, the raw-height-one comb has boundary coordinates $\pm\Delta_j$, merge coordinate $-3$, and final coordinate $+1$. Since $k\ge3$, the latest boundary dominates. This proves the canonical equality in (13).

Raw height one is attained by assigning $+1$ to $a$-edges, $-1$ to $d$-edges, and zero elsewhere. Repaired raw height zero is impossible: the repaired values at $w_0$ and $w_2$ differ by

$$3+5\lambda,$$

which is never zero for integer $\lambda$. This proves the raw equality.

7. Mechanism

The target forces two countdown carriers with incompatible slopes:

$$+1\quad\text{on the \(a\)-carrier}, \qquad -1\quad\text{on the \(d\)-carrier}.$$

A global length drift adds the same coefficient $\lambda$ to both. Choosing $\lambda=-1$ cancels the positive countdown-length coefficient but doubles the negative one; choosing $\lambda=+1$ does the reverse. Because exact minimum-state presentations must retain both carriers, one linear canonical obstruction always survives.

This is the first audited witness in this lane that survives the stated global length-and-constant repair. The earlier one-carrier sparse comb is a negative control: its target equals word length on its support, so $\lambda=-1$ collapses both repaired heights to zero.

8. Independent audit record

Two independent reconstructions agreed on all load-bearing points:

1. the exact horizon quotient and state count;
2. exhaustion of the state budget and the shared sole final state;
3. forced support-path transitions;
4. unique shortest accesses, including equal-length competitors;
5. all boundary, merge, and final canonical formulas;
6. the three-case lower bound over every integer $\lambda$;
7. the exact identity-gauge upper bound;
8. impossibility of repaired raw height zero;
9. absence of any same-budget alternative presentation that avoids the lower bound.

One audit also checked $k=3,\ldots,10$ and $\lambda\in[-12,12]$ with no failures. These finite checks support the proof but do not replace it.

9. Requested repository work

Please:

1. transcribe Theorem A as fixed-presentation infrastructure, with the augmented boundary vertex and the prior-art classification preserved;
2. transcribe Theorem B as a separate fixed-target theorem;
3. independently reconcile equations (15)–(19) with the repository’s normalization sign convention;
4. preserve the two-audit status and record any checker as supporting evidence rather than as proof;
5. keep the failed one-carrier sparse comb as a negative control, not as a repaired witness;
6. do not merge the result with richer baseline quotients or mode-dependent gauges.

10. Scope

What is proved:

• one fixed partial integer-valued target;
• one fixed finite alphabet;
• exact minimum-state budget at each selected horizon;
• minimization over all correct deterministic sequential presentations in that section;
• robustness under the repository’s global length-and-constant repair;
• a linear repaired canonical/raw separation.

What is not proved:

• novelty;
• a result inside the rational or finitely ambiguous rational class;
• robustness under mode-dependent, letter-dependent, or arbitrary finite-state baselines;
• a complete state-height Pareto curve;
• a general semantic characterization of canonical height.

The natural next mathematical question after capture is not another repair of this witness. It is whether the same incompatible-carrier mechanism can be transferred to a more natural doctrine or a rational/finitely ambiguous target, or used to compute a nontrivial segment of the full state-versus-repaired-height frontier.