Extremal Projective Rigidity in Finite-Template Positive Propagation Systems: Gap-Free Forcing on Minimizers, Finite Certification, and Obstruction Taxonomy

We study extremal exponential growth in positive propagation systems driven by a finite template set and finite-type constraints.
Beyond gap-certified localization, we develop a gap-free upgrade: using a finite calibration potential on the reduced descriptor graph,
we show that any minimizing trajectory either becomes eventually periodic on a tight critical cycle or induces a recurrent aperiodic tight core.
On such an aperiodic minimizing core, explicit Doeblin minorization and positive return density force uniform projective contraction along minimizers.
In the gap-certified regime, the same pipeline yields a unique projective section with a fully explicit exponential rate.
All hypotheses admit finite verification with polynomial-time graph routines and finite automaton checks, and we formalize a finite obstruction taxonomy.

Introduction and positioning

The recurring structural problem is to understand long-horizon growth in constrained products of nonnegative matrices and to determine when extremal growth
exhibits rigidity: namely, that extremizing trajectories force convergence to a unique projective direction with an explicit rate.
The setting encompasses standard finite-state transfer-matrix formalisms, symbolic-dynamics cocycles, and Perron–Frobenius type propagation models.

Our contribution is a theorem chain that is simultaneously structural and certifiable:
a finite reduction produces a weighted directed graph whose extremal cycle mean governs the extremal growth rate;
a strict gap then localizes extremizers to a critical core; and explicit minorization plus syndetic return yields projective contraction
with computable constants. We make the precise finite obstructions explicit.

Related literature (orientation)

The use of projective metrics and Birkhoff-type contraction for positive operators is classical; see Birkhoff and Bushell.
Finite-state constraints connect naturally to symbolic dynamics (Lind–Marcus), and the extremal cycle-mean reduction is a standard finite-graph mechanism (Karp).
Our focus is the integrated, certificate-first synthesis in a single theorem pipeline.

Model and unified notation

Definition — Finite-Template Growth (FTG)

Fix $d\in\mathbb{N}$ and a finite set $\mathcal{T}\subset \mathbb{R}^{d\times d}_{\ge 0}$.
Assume uniform entry bounds: there exist $0<m_*\le M_*<\infty$ such that for every $T\in\mathcal{T}$,
every nonzero entry $T_{ij}$ lies in $[m_*,M_*]$.
Let $(\Sigma,\sigma)$ be an edge shift of finite type (SFT) and let $A:\Sigma\to \mathcal{T}$ be locally constant.
For $\omega\in\Sigma$ define $A^{(n)}(\omega)=A(\sigma^{n-1}\omega)\cdots A(\omega)$.

Definition — Cone interior and Hilbert metric

Let $\mathbb{R}^d_{>0}$ denote the interior of the positive cone.
For $x,y\in\mathbb{R}^d_{>0}$ define the Hilbert projective distance

Canonical Normalization and the Tight Subgraph

This section records the structural normalization that underlies the rest of the paper.
It converts the extremal-growth problem into the study of a canonically defined zero-set
(the tight transitions). Subsequent rigidity and obstruction statements are properties of this tight geometry.

Reduced costs

Let $G=(V,E)$ be the reduced finite graph produced by the descriptor reduction, with edge costs $c:E\to\mathbb{R}$.
Define the minimal cycle mean

Theorem — Canonical normalization by a potential

There exists a function (potential) $\phi:V\to\mathbb{R}$ such that the reduced costs

satisfy $c_\phi(e)\ge 0$ for all $e\in E$.

Proof

Let $\tilde c(e):=c(e)-\lambda_*$. For any directed cycle $\gamma$ of length $k$,
$\sum_{e\in\gamma}\tilde c(e)=k(\bar c(\gamma)-\lambda_*)\ge 0$, so $(G,\tilde c)$ has no negative cycles.
Fix a root $v_0$ in each reachable component and define $\phi(v)$ to be the minimum $\tilde c$-cost of a directed path from $v_0$ to $v$.
Then for any edge $e:u\to v$, optimality of $\phi(v)$ yields $\phi(v)\le \phi(u)+\tilde c(e)$, i.e.\ $\tilde c(e)+\phi(u)-\phi(v)\ge 0$.
This inequality is exactly $c_\phi(e)\ge 0$.

The tight subgraph

Definition — Tight edges and tight subgraph

Fix a potential $\phi$ as in Theorem .
Define the tight edges

where $V^{(0)}$ are vertices incident to $E^{(0)}$.

Minimizers are asymptotically tight

A (one-sided) path $\pi=(e_0,e_1,\dots)$ has length-$n$ average cost

We call $\pi$ minimizing if $\liminf_{n\to\infty}\mathrm{Avg}_n(\pi)=\lambda_*$.

Proposition — Asymptotic tightness of minimizing paths

Let $\pi$ be a minimizing path and fix $\phi$ as above.
Then the set of times $t$ with $e_t\notin E^{(0)}$ has asymptotic density $0$.
Equivalently, $E^{(0)}$ is visited with asymptotic density $1$ along $\pi$.

Proof

Because $E$ is finite and $c_\phi(e)\ge 0$, define

with the convention $\alpha=+\infty$ if $E^{(0)}=E$. When $E^{(0)}\ne E$, we have $\alpha>0$.
Let $N_n$ be the number of indices $t<n$ with $e_t\notin E^{(0)}$.
Then $\sum_{t=0}^{n-1} c_\phi(e_t)\ge \alpha N_n$.
On the other hand, telescoping the potential gives

where $v_n$ is the vertex reached after $n$ steps. Since $\phi$ is bounded on the finite reachable vertex set, $|\phi(v_0)-\phi(v_n)|\le C$.
Divide by $n$ and take $\liminf$. Minimizing implies $\liminf_{n\to\infty}\frac{1}{n}\sum_{t=0}^{n-1}(c(e_t)-\lambda_*)=0$,
hence $\liminf_{n\to\infty}\frac{1}{n}\sum_{t=0}^{n-1}c_\phi(e_t)=0$.
Therefore $\liminf_{n\to\infty}\alpha N_n/n=0$, which forces $N_n/n\to 0$.

A tight-core dichotomy

From infinite visits to syndetic recurrence

In several statements we avoid explicit density assumptions by working with essential components.

Definition — Essential SCC for a path

Let $\pi$ be a one-sided path in $G^{(0)}$. An SCC $H$ of $G^{(0)}$ is essential for $\pi$ if $\pi$ visits $H$ infinitely often.

Lemma — Finite essentiality implies a positive-density component

Let $\pi$ be a path in $G^{(0)}$ and let $\mathscr{S}$ be the finite set of SCCs essential for $\pi$.
Then at least one $H\in\mathscr{S}$ is visited with positive lower density by $\pi$ (measured in time indices).

Proof

Partition the time indices $t\ge 0$ by the SCC of $G^{(0)}$ containing the edge (or vertex) visited at time $t$.
Because $\mathscr{S}$ is finite, if every essential SCC had lower density $0$, then the union of their visits would have lower density $0$.
But $\pi$ is eventually contained in the union of its essential SCCs (any SCC visited only finitely often contributes only finitely many indices),
so the complement would have density $0$ and the union would have density $1$, a contradiction.

Corollary — Aperiodic essential SCC yields the aperiodic case

If $\pi$ has an aperiodic essential SCC, then there exists an aperiodic SCC visited with positive lower density.

Proof

Apply Lemma to $\mathscr{S}$ and note that if all positive-density SCCs were periodic then the aperiodic SCC would have density $0$.
Because it is essential, it must belong to $\mathscr{S}$, so some aperiodic SCC in $\mathscr{S}$ attains positive lower density.

Remark

This converts “positive lower density” conclusions into a consequence of finiteness plus infinite recurrence inside the tight graph.

Extremal selection principle

We now remove any existential ambiguity in the aperiodic branch by selecting a minimizing trajectory with maximal recurrence support.

Definition — Support of a minimizing trajectory

For a minimizing path $\pi$ in $G^{(0)}$, define its support

Lemma — Maximal-support minimizer

Among all minimizing trajectories, there exists one whose support is inclusion-maximal (with respect to the finite family of SCC subsets).

Proof

Because $G^{(0)}$ has finitely many SCCs, the family of possible supports is finite.
Choose a minimizing trajectory whose support has maximal cardinality.

Proposition — Selection rigidity

Let $\pi$ be a maximal-support minimizing trajectory.
If $\pi$ has any aperiodic essential SCC, then every minimizing trajectory has an aperiodic essential SCC.

Proof

Suppose $\pi$ has an aperiodic essential SCC $H$.
If some minimizing trajectory $\pi’$ had no aperiodic essential SCC, then all its essential SCCs would be periodic.
Then $\mathrm{Supp}(\pi’)$ would be strictly contained in $\mathrm{Supp}(\pi)$ (since $H$ would be absent), contradicting maximality of $\pi$.

Corollary — Structural dichotomy without existential asymmetry

Exactly one of the following holds:

• Every minimizing trajectory is eventually periodic inside $G^{(0)}$;
• Every minimizing trajectory has an aperiodic essential SCC.

Remark

This removes any dependence on selecting a special trajectory in the aperiodic case.
The dichotomy is intrinsic to the extremal structure of the tight graph.

Proposition — Tight-core dichotomy

Let $\pi$ be a minimizing path. Then exactly one of the following holds:

• $\pi$ is eventually trapped in a periodic SCC of $G^{(0)}$ (hence is eventually periodic);
• $\pi$ has an aperiodic essential SCC of $G^{(0)}$ (i.e., an aperiodic SCC visited infinitely often).

Proof

By Proposition , $\pi$ uses non-tight edges with density $0$.
Consider the SCC decomposition of $G^{(0)}$. Let $\mathscr{S}$ be the finite set of SCCs of $G^{(0)}$ visited infinitely often by $\pi$.
If every SCC in $\mathscr{S}$ is periodic, then switching between distinct SCCs requires traversing an edge not in $E^{(0)}$.
Such switches can occur only finitely often since non-tight edges have density $0$; hence $\pi$ is eventually trapped in a single periodic SCC (case (P)).
Otherwise, $\pi$ has an aperiodic essential SCC (case (A)); in particular, Corollary yields an aperiodic SCC visited with positive lower density when needed downstream.

Remark

The remainder of the paper analyzes the geometry of $G^{(0)}$.
Rigidity (projective contraction) is obtained from recurrence and Doeblin structure inside an aperiodic tight SCC.
Obstructions are finite failures of the corresponding tight-core regularity conditions.

Gap-Free Structural Rigidity (Headline Form)

We now state the gap-free rigidity result in a structurally primary form.
It is presented independently of any global strict gap hypothesis.

Theorem — Gap-Free Structural Rigidity

Assume:

• Finite-template reduction to a finite directed graph $G$,
• Existence of minimizing trajectories attaining the minimal cycle mean $\lambda_*$.

Let $G^{(0)}$ be the tight subgraph produced by canonical normalization.

Then exactly one of the following holds:

• Every minimizing trajectory is eventually periodic inside a periodic SCC of $G^{(0)}$;
• Every minimizing trajectory has an aperiodic essential SCC $H\subset G^{(0)}$ (visited infinitely often); along $H$ the system admits a recurrent Doeblin word inducing uniform projective contraction.

Proof — Proof sketch (structure)

By Proposition , every minimizing path asymptotically lives in $G^{(0)}$ and satisfies the tight-core dichotomy.
In case (i), eventual periodicity follows directly from periodic SCC trapping.
In case (ii), Corollary supplies an aperiodic SCC visited with positive lower density if one wishes to phrase results in density form; the face-certification and support-connectivity modules yield existence of a recurrent mixing block, inducing projective contraction via the gap-free module.

Remark

The strict-gap theorem becomes a corollary of Theorem .
Thus spectral separation is sufficient but not necessary for rigidity.

Sharp Obstruction Characterization (Tight-Core Boundary)

This section records a tight-core characterization of when the gap-free contraction mechanism is forced and when it cannot be triggered.
The statement is purely finite and uses only the tight geometry produced by the canonical normalization.

Theorem — Tight-core boundary for contraction

Assume the hypotheses of Theorem and let $G^{(0)}$ be the tight subgraph.
Exactly one of the following two alternatives holds:

• Periodic trapping: every minimizing trajectory is eventually trapped in a periodic SCC of $G^{(0)}$ (hence eventually periodic in the tight graph);
• Aperiodic essential core: every minimizing trajectory has an aperiodic essential SCC $H\subset G^{(0)}$.

Moreover, in the aperiodic alternative (A), the following are equivalent:

• there exists an aperiodic tight SCC $H\subset G^{(0)}$ on which the descriptor-face certificates hold
  (face map $S(\cdot)$ exists on $H$ and $\Gamma(H)$ is strongly connected);
• there exists a Doeblin word $w$ on an active face $S(H)$ that recurs along minimizing dynamics in $H$;
• Hilbert distances contract uniformly along every minimizing trajectory (with explicit constants depending only on the finite certificates for $H$).

Finally, failure of the contraction mechanism in the aperiodic regime is equivalent to the finite obstruction alternatives:

• OG2 holds on every aperiodic essential SCC (no consistent face map);
• OG3 holds on every aperiodic essential SCC (certificate graph $\Gamma$ not strongly connected).

Proof

The dichotomy (P)/(A) is exactly Proposition together with the selection upgrade (Corollary following Proposition ).

Assume (A). We prove (B1)$\Leftrightarrow$(B2)$\Leftrightarrow$(B3) and then the obstruction equivalence.

(B1)$\Rightarrow$(B2).
If the descriptor-face certificates hold on an aperiodic SCC $H$, then Corollary produces a Doeblin word $w$ on the certified face $S(H)$.
Because $H$ is essential for minimizing trajectories in the aperiodic regime, occurrences of $w$ recur along the minimizing dynamics inside $H$.
This gives (B2).

(B2)$\Rightarrow$(B3).
Each occurrence of the Doeblin word yields a uniform Hilbert contraction factor $\tau<1$ on the active face via the Doeblin$\Rightarrow$diameter$\Rightarrow$Birkhoff chain.
Since $w$ recurs along minimizers (either with positive lower density or bounded gaps inside $H$), Corollary yields exponential contraction with explicit rate.
This proves (B3).

(B3)$\Rightarrow$(B2).
Uniform projective contraction along minimizing trajectories implies the existence of a recurrent contraction block along the minimizing dynamics.
In the finite-template setting, such a block can be taken as a finite word $w$ in the template alphabet that recurs infinitely often along the tight dynamics.
By standard compactness/pigeonhole in the finite graph, one may choose $w$ to recur with bounded gaps along an essential SCC.
The contraction hypothesis forces $w$ to have a Doeblin minorization on the active face (otherwise Hilbert distances would not contract uniformly).
Thus a Doeblin word exists and recurs, giving (B2).

Obstruction equivalence in the aperiodic regime.
If OG2 or OG3 holds on every aperiodic essential SCC, then no aperiodic essential SCC admits the descriptor-face certificates, so (B1) fails, hence (B2) and (B3) fail.
Conversely, if (B1) fails for every aperiodic essential SCC, then by the obstruction taxonomy an aperiodic essential SCC must exhibit OG2 or OG3, and if the aperiodic regime holds for all minimizers this forces OG2 or OG3 on every aperiodic essential SCC.

Remark

Theorem isolates the exact finite boundary inside $G^{(0)}$:
periodic trapping versus an aperiodic essential core, and in the aperiodic case, certificate success versus the OG2/OG3 obstructions.

Parameter Chambers and Generic Cycle Selection

This section formalizes what is actually generic in linear parameter families: uniqueness of the minimizing cycle mean (off a finite hyperplane arrangement),
together with a finite chamber decomposition of parameter space on which the set of minimizing cycles is constant.
No claim of “generic aperiodicity” is made, since periodic/aperiodic is a combinatorial property of the selected critical SCC.

Linear parameter model and hyperplane arrangement

Fix a finite directed graph $G=(V,E)$ (after reduction) and a feature map $\psi:E\to\mathbb{Z}^k$.
For $\theta\in\mathbb{R}^k$ define edge costs

and for a directed cycle $\gamma$ define its mean cost

Let $\mathcal{C}$ be the finite set of simple directed cycles in $G$ and let

be the minimal cycle mean.

Definition — Degeneracy hyperplanes

For distinct cycles $\gamma\neq\gamma’$ define the affine functional

The degeneracy arrangement is the finite union of hyperplanes

Lemma — Unique minimizing cycle off $\mathcal{D}$

If $\theta\notin\mathcal{D}$, then there exists a unique cycle $\gamma_*(\theta)\in\mathcal{C}$ with $\mu_\theta(\gamma_*(\theta))=\lambda_*(\theta)$.

Proof

If two distinct cycles both attained the minimum, then $F_{\gamma,\gamma’}(\theta)=0$ for that pair, so $\theta\in\mathcal{D}$.

Chamber decomposition and critical SCC stability

Definition — Chambers

A parameter chamber is a connected component of $\mathbb{R}^k\setminus\mathcal{D}$.

Proposition — Finite chamber structure

$\mathbb{R}^k\setminus\mathcal{D}$ is a finite union of open polyhedral chambers.
On each chamber, the minimizing cycle $\gamma_*(\theta)$ is constant.

Proof

$\mathcal{D}$ is a finite arrangement of affine hyperplanes, so its complement has finitely many connected components,
each described by a finite system of strict linear inequalities $F_{\gamma,\gamma’}(\theta)\lessgtr 0$.
Within a fixed component, the sign pattern of all $F_{\gamma,\gamma’}$ is constant, hence the unique minimizer $\gamma_*$ is constant by Lemma .

Corollary — Computable periodic/aperiodic regime on chambers

Fix a chamber $\mathcal{U}$ and let $\gamma_*$ be its minimizing cycle.
Then the essential critical SCC of the tight graph is the SCC generated by $\gamma_*$ (in particular, it is periodic).
More generally, on lower-dimensional strata $\theta\in\mathcal{D}$ where multiple cycles tie, the tight critical subgraph may contain multiple cycles
and may be periodic or aperiodic depending on the gcd of cycle lengths in the resulting critical SCC.
All of these properties are decidable from the finite tight geometry.

Remark — What this means for “generic collapse”

In linear cost families, uniqueness of the minimizing cycle is the generic phenomenon, and that typically yields a periodic critical SCC.
Therefore, a genuine “generic collapse of periodic trapping” cannot be claimed at this level of parameterization without additional structure
(e.g.\ perturbing matrix entries rather than only linear cycle costs, or imposing a model where tight edges retain multiple cycles generically).
What is robust and breakout-relevant is the following: the entire periodic/aperiodic and certificate/obstruction boundary is finitely computable from $G^{(0)}$,
and parameter space admits a finite chamber stratification on which the boundary type is constant.

Reduced graph and extremal mean

We assume a finite descriptor collapse has been performed, producing a finite directed graph $G=(V,E)$ encoding
admissible descriptor transitions. Each edge $e\in E$ is labeled by a template (or a fixed-length block of templates) and carries
a real weight $c(e)$ representing the corresponding one-step log-growth contribution under a fixed cone norm.
(Only finiteness matters for the results below.)

For a directed cycle $\gamma=e_1\cdots e_k$ define the cycle mean

Definition — Extremal mean and critical subgraph

Define the extremal (minimal) cycle mean

Let $G_*=(V_*,E_*)$ denote the critical subgraph, the union of all cycles $\gamma$ with $\bar c(\gamma)=\lambda_*$.

Gap selection with explicit dependence

Theorem — Gap selection with explicit gap parameter

Assume there exists $\delta>0$ such that every directed cycle $\gamma$ in $G$ that is not fully contained in $G_*$ satisfies
$\bar c(\gamma)\ge \lambda_*+\delta$.
Then every shift-invariant probability measure on the SFT that minimizes the asymptotic average cost is supported on paths whose descriptor
trajectory lies in $G_*$.

Proof

Let $\mu$ be any shift-invariant probability measure on the admissible path space of $G$ (equivalently, on the SFT encoding the edges).
By the ergodic decomposition, it suffices to prove the claim for ergodic $\mu$.
For ergodic $\mu$, by Birkhoff’s theorem the $\mu$-almost sure time-average of edge costs equals the space average:

For each $\omega$, the empirical edge-frequency measures along the first $n$ edges are convex combinations of cycle measures up to boundary terms.
Equivalently, the vector of edge counts satisfies a flow-conservation identity with $O(1)$ defect, so that the mean cost over length $n$
is within $O(1/n)$ of a convex combination of cycle means (this is the standard cycle-decomposition of Eulerian flows on a finite digraph).
Thus, for any $\varepsilon>0$ and $n$ large, there exist cycles $\gamma_1,\dots,\gamma_m$ and weights $\alpha_j\ge 0$, $\sum_j\alpha_j=1$ such that

If $\omega$ uses an edge outside $E_*$ with positive asymptotic frequency, then at least one of the contributing cycles in any such decomposition must
not be fully contained in $G_*$ with positive weight, hence has mean $\ge \lambda_*+\delta$.
Since all cycles have mean $\ge \lambda_*$ by definition of $\lambda_*$, we obtain

where $\eta(\omega)\in[0,1]$ is the total asymptotic weight assigned to noncritical cycles (equivalently, the asymptotic frequency of edges outside $E_*$
up to a bounded linear comparison constant on a finite graph).
Therefore, any path that spends positive asymptotic frequency outside $E_*$ has asymptotic mean cost strictly greater than $\lambda_*$.
Consequently, any minimizing ergodic measure must satisfy $\eta(\omega)=0$ almost surely, i.e.\ it is supported on paths entirely contained in $G_*$.

Primitive block $\Rightarrow$ explicit Doeblin minorization and contraction

Doeblin constants from FTG bounds

Fix a strongly connected component of $G_*$ and a fixed product length $N$ such that along admissible length-$N$ paths in the component,
a chosen block product is primitive on a fixed face $S$ (i.e.\ its $S\times S$ restriction has all entries strictly positive).

Lemma — Primitive block implies explicit Doeblin window

Assume a product $B$ of length $N$ along the critical component satisfies: for some nonempty index set $S\subset\{1,\dots,d\}$,
the restriction $B_{S\times S}$ has all entries positive.
Under FTG bounds, one may take explicit constants

such that for all $i,j\in S$,

Proof

Since $B$ is a product of $N$ templates, each positive entry of $B$ is a sum of weights of length-$N$ paths in the template graph.
Every summand is a product of $N$ nonzero template entries, hence lies in $[m_*^N, M_*^N]$.
Because $B_{ij}>0$ for $i,j\in S$, there exists at least one contributing path, so $B_{ij}\ge m_*^N=\varepsilon$.
For the upper bound, the number of length-$N$ walks from $j$ to $i$ in a $d$-state system is at most $d^{N-1}$, so
$B_{ij}\le d^{N-1} M_*^N \le (d M_*)^N = U$.

Hilbert diameter and explicit contraction factor

Lemma — Doeblin bounds imply finite Hilbert diameter

Let $B$ be a positive matrix on indices $S$ satisfying $\varepsilon \le B_{ij}\le U$ for all $i,j\in S$.
Then for all $x,y\in \mathbb{R}^{S}_{>0}$,

Proof

Fix $x\in\mathbb{R}^S_{>0}$. For each $i\in S$,
\(
(Bx)_i=\sum_{j\in S} B_{ij}x_j.
\)
Using $\varepsilon\le B_{ij}\le U$ gives
\(
\varepsilon \sum_{j\in S} x_j \le (Bx)_i \le U \sum_{j\in S} x_j
\)
for all $i$.
Hence for any two indices $i,k\in S$,
\(
\frac{(Bx)_i}{(Bx)_k}\le \frac{U}{\varepsilon}.
\)
Applying this bound to both $x$ and $y$ and unwinding the definition of $d_H$ yields $d_H(Bx,By)\le 2\log(U/\varepsilon)$.

Lemma — Birkhoff contraction coefficient

For a positive linear map $B$ on $\mathbb{R}^S_{>0}$ with Hilbert diameter $\Delta(B)<\infty$,
the Birkhoff contraction coefficient satisfies

Remark

Lemma is classical; it is included as a named step because the explicit dependence of $\tau$ on $\Delta$ is the quantitative bridge
to computable convergence rates. Lemma makes $\Delta$ explicit under Doeblin bounds.

Syndetic return certificate $\Rightarrow$ explicit exponential rate

Definition — Syndetic return to a word

Let $w$ be a fixed admissible word (edge block) of length $|w|$ in the critical component.
We say $w$ is syndetic if there exists $L_{\mathrm{syn}}$ such that every admissible infinite path in the component
contains an occurrence of $w$ starting within each window of length $L_{\mathrm{syn}}+|w|$.

Lemma — Syndetic Doeblin return yields explicit exponential contraction

Assume $w$ is syndetic with gap bound $L_{\mathrm{syn}}$ and that the corresponding block product $B$ satisfies Doeblin bounds with
$\varepsilon,U$, hence $\Delta(B)\le 2\log(U/\varepsilon)$ and $\tau:=\tanh(\Delta(B)/4)<1$.
Then for any admissible product sequence $(A_t)$ on the component and any $x,y\in\mathbb{R}^S_{>0}$,

where one may take

Proof

Partition the time axis into consecutive windows of length $L_{\mathrm{syn}}+|w|$.
By syndeticity, each window contains an occurrence of the word $w$, hence a subproduct equal to $B$.
Write the full length-$n$ product as a concatenation of blocks, each containing one $B$.
Within each block, projective distance is nonexpansive under positive maps up to a bounded factor, and at the occurrence of $B$ the distance contracts
by at least factor $\tau$ (Lemma ).
Thus after $k$ occurrences of $B$ we have contraction by $\tau^k$.
Since in $n$ steps there are at least $k \ge \left\lfloor \frac{n}{L_{\mathrm{syn}}+|w|}\right\rfloor$ occurrences,
\(
d_H(\cdot)\le \tau^k d_H(x,y)\le \tau^{-1}\exp\!\left(-\frac{-\log\tau}{L_{\mathrm{syn}}+|w|}n\right)d_H(x,y),
\)
which is with the stated constants.

Main rigidity theorem with explicit constants

Theorem — Extremal projective rigidity with explicit rate

Assume FTG and descriptor reduction to a finite weighted digraph $G=(V,E)$ as above.
Assume further:

• (Gap) There exists $\delta>0$ such that every cycle not contained in $G_*$ has mean $\ge \lambda_*+\delta$.
• (Primitive block) There exists an admissible word $w$ of length $|w|$ on $G_*$ whose block product $B$ is positive on a face $S$.
• (Syndetic return) The word $w$ is syndetic on $G_*$ with gap bound $L_{\mathrm{syn}}$.

Then extremizers are supported on $G_*$ (Theorem ) and there exists a unique projective section $\xi(\omega)\in \mathbb{P}(\mathbb{R}^S_{>0})$
such that for all $x\in\mathbb{R}^S_{>0}$,

for all $n\ge 0$, where $x_0$ is any fixed reference vector, and with explicit constants:

Proof

By Theorem , extremizers are supported on the critical subgraph $G_*$.
On $G_*$, the primitive block hypothesis and Lemma give explicit Doeblin bounds $(\varepsilon,U)$ for $B$.
Lemmas and give a contraction factor $\tau<1$ in $d_H$.
Syndeticity and Lemma then yield exponential contraction with explicit rate $\kappa$.
Standard Cauchy-convergence in the complete metric space of projective classes over the cone interior yields a unique limit section $\xi$,
and the explicit rate follows from .

Descriptor-Face Certificates for Minimizing Cores

Descriptor Faces as Finite Certificates (Eliminating Interface Assumptions)

The gap-free module introduced two interface notions on a tight SCC $H$:
active-face invariance and support-connectivity on the active face.
Here we make both notions purely finite and certifiable outcomes of the descriptor reduction itself.

Canonical active face per descriptor state

In the descriptor reduction, each vertex $v\in V$ corresponds to a finite descriptor encoding which coordinates
are potentially active and which are structurally zero under admissible propagation.
Accordingly, each descriptor vertex carries a canonical support set

Definition — Face map and canonical active set

A face map for the reduced graph is a function $S:V\to 2^{\{1,\dots,d\}}$ such that for each edge $e:u\to v$
labeled by a template (or fixed-length block) $T_e$ we have:

• (Forward invariance) $T_e(\mathbb{R}^{S(u)}_{>0})\subseteq \mathbb{R}^{S(v)}_{>0}$;
• (No spurious activation) If $x\in \mathbb{R}^{S(u)}_{>0}$, then $(T_e x)_i =0$ for all $i\notin S(v)$.

Remark

Definition is checkable from template sparsity: it amounts to verifying that the support pattern of each $T_e$
maps the indicator of $S(u)$ into $S(v)$.

Face stability on SCCs as a finite fixed-point

Lemma — SCC face stability by intersection closure

Let $H$ be an SCC of the reduced graph and let $S:V\to 2^{\{1,\dots,d\}}$ be a face map.
Define the SCC face by

Then for every edge $e:u\to v$ inside $H$,

Proof

Since $S(H)\subseteq S(u)$ for each $u\in H$, we have $\mathbb{R}^{S(H)}_{>0}\subseteq \mathbb{R}^{S(u)}_{>0}$.
By forward invariance, $T_e(\mathbb{R}^{S(u)}_{>0})\subseteq \mathbb{R}^{S(v)}_{>0}$.
Because $S(H)\subseteq S(v)$, restricting to coordinates in $S(H)$ yields invariance on $S(H)$.

Support-connectivity on the SCC face as a finite graph property

Fix an SCC $H$ and its canonical face $S(H)$.
For each generator edge $e$ in $H$ labeled by $T_e$, define the induced coordinate support digraph on $S(H)$:
we draw an arrow $j\to i$ if $(T_e)_{ij}>0$ for some $e$ in $H$.

Definition — Coordinate support digraph on a face

Let $\Gamma(H)$ be the directed graph with vertex set $S(H)$ and an arrow $j\to i$ if there exists an edge $e$ in $H$ such that $(T_e)_{ij}>0$.

Lemma — Support-connectivity certificate

If $\Gamma(H)$ is strongly connected, then for every $i,j\in S(H)$ there exists an admissible word $w$ in $H$ such that the block product satisfies
$(B(w))_{ij}>0$.

Proof

Strong connectivity gives a coordinate path $j\to \cdots \to i$ realized by a sequence of generator matrices from edges of $H$.
Concatenate the corresponding edges to obtain a word $w$ whose product contains a positive contribution from $j$ into $i$.

Corollary — Doeblin word from aperiodic SCC + coordinate strong connectivity

Let $H$ be an aperiodic SCC of the tight graph and assume a face map $S(\cdot)$ is available.
If $\Gamma(H)$ is strongly connected, then there exists a word $w$ in $H$ whose block product is strictly positive on $S(H)\times S(H)$.

Remark

This replaces the “support-connectivity interface assumption” by the explicit finite certificate:
aperiodicity of $H$ (graph period $1$) and strong connectivity of $\Gamma(H)$.

Algorithmic extraction

[H]
\caption{Compute SCC face and coordinate support graph}
[1]
\Require SCC $H$ with face map $S(\cdot)$ and generator labels $T_e$
\Ensure $S(H)$ and coordinate digraph $\Gamma(H)$
\State $S(H)\gets \bigcap_{v\in H} S(v)$
\State Initialize $\Gamma(H)$ with vertex set $S(H)$
\ForAll{edges $e$ inside $H$}
\ForAll{$i,j\in S(H)$}
\If{$(T_e)_{ij}>0$} add arrow $j\to i$ \EndIf
\EndFor
\EndFor

[H]
\caption{Check OG2/OG3 as finite certificates}
[1]
\Require Tight SCC $H$, face map $S(\cdot)$, generator labels
\Ensure Either pass certificates or witnesses for OG2/OG3
\State Compute $S(H)$ and $\Gamma(H)$
\If{face-map constraints fail on some edge} \Return OG2 witness \EndIf
\If{$H$ aperiodic and $\Gamma(H)$ not strongly connected} \Return OG3 witness \EndIf
\If{$H$ aperiodic and $\Gamma(H)$ strongly connected} \Return Doeblin-ready \EndIf

Gap-Free Upgrade: Optimality Forces Regularity on Minimizers

Gap-Free Upgrade: Optimality Forces a Recurrent Aperiodic Core

Setup: potentials and reduced costs on a finite weighted digraph

Let $G=(V,E)$ be a finite directed graph. Let $c:E\to\mathbb{R}$ be an edge cost.
For a directed cycle $\gamma=e_1\cdots e_k$ define its mean cost

Let $G_*=(V_*,E_*)$ denote the union of all cycles $\gamma$ with $\bar c(\gamma)=\lambda_*$.

We write a path as $\pi=(e_0,e_1,\dots)$ and denote its length-$n$ partial mean cost by

A path $\pi$ is called minimizing if $\liminf_{n\to\infty} \mathrm{Avg}_n(\pi)=\lambda_*$.

Lemma 14.A: calibration without a strict gap

Lemma — Cycle-mean calibration via potentials

There exists a potential $\phi:V\to\mathbb{R}$ such that the reduced costs

satisfy $c_\phi(e)\ge 0$ for all $e\in E$.
Moreover, along any directed cycle $\gamma$,

so $\gamma$ is $\lambda_*$-critical iff every edge of $\gamma$ has $c_\phi(e)=0$ and the cycle uses only edges with $c_\phi=0$.

Proof

A standard construction uses Karp’s min mean cycle theorem together with a shortest-path potential on the reweighted graph.
Fix $\lambda_*$. Consider the reweighted costs $\tilde c(e):=c(e)-\lambda_*$.
By definition of $\lambda_*$, every directed cycle has nonnegative total $\tilde c$-cost:
for a cycle $\gamma$ of length $k$, $\sum_{e\in\gamma}\tilde c(e)=k(\bar c(\gamma)-\lambda_*)\ge 0$.
Hence the graph with edge weights $\tilde c$ has no negative cycles.

Define $\phi(v)$ to be the minimum $\tilde c$-cost of a directed path from an arbitrary root $v_0$ to $v$,
with $\phi(v)=+\infty$ if $v$ is unreachable (these vertices can be discarded since they do not lie on any bi-infinite admissible path).
Because there are no negative cycles, these minima are finite on the reachable part and are well-defined.

For any edge $e:u\to v$, optimality of $\phi(v)$ gives
$\phi(v)\le \phi(u)+\tilde c(e)$, i.e.\ $\tilde c(e)+\phi(u)-\phi(v)\ge 0$.
But $\tilde c(e)+\phi(u)-\phi(v)=c(e)-\lambda_*+\phi(u)-\phi(v)=c_\phi(e)$, proving $c_\phi(e)\ge 0$.

The cycle identity follows by telescoping $\phi$ along the cycle.

Definition — Tight-edge subgraph

Given a potential $\phi$ as in Lemma , define the tight-edge set

where $V^{(0)}$ are vertices incident to edges in $E^{(0)}$.

Remark

In the strict-gap setting, $E^{(0)}$ coincides (up to transient issues) with the critical subgraph $G_*$.
Without a strict gap, $E^{(0)}$ can contain multiple SCCs with equal mean; Lemma still provides a local optimality certificate.

Lemma 14.B: density/recurrence extraction on minimizing paths

Lemma — Aperiodic core or eventual periodicity on tight edges

Let $\pi=(e_0,e_1,\dots)$ be a minimizing path.
Then for every $\varepsilon>0$ there exists $N_\varepsilon$ such that for all $n\ge N_\varepsilon$,
the fraction of indices $t<n$ with $e_t\notin E^{(0)}$ is at most $\varepsilon$.
In particular, the set of tight edges $E^{(0)}$ is visited with asymptotic density $1$ along $\pi$.
Moreover, exactly one of the following holds:

• $\pi$ is eventually trapped in a periodic SCC of $G^{(0)}$ (hence is eventually periodic);
• there exists an aperiodic SCC $H$ of $G^{(0)}$ visited with positive lower density along $\pi$.

Proof

First, since $c_\phi(e)\ge 0$ for all edges and $c_\phi(e)>0$ for $e\notin E^{(0)}$,
let

Because $E$ is finite and the set is nonempty unless $E^{(0)}=E$, we have $\alpha>0$ when nonempty.

For the length-$n$ prefix of $\pi$, telescoping gives

where $v_t$ is the head vertex after $t$ steps (so $e_t:v_t\to v_{t+1}$).
Since $\phi$ is bounded on the finite reachable vertex set, say $|\phi|\le B_\phi$, the boundary term is bounded by $2B_\phi$.
Hence

By minimizing assumption, $\liminf_{n\to\infty}\frac{1}{n}\sum_{t=0}^{n-1}(c(e_t)-\lambda_*)=0$.
Divide by $n$ and take liminf to obtain
$\liminf_{n\to\infty}\frac{1}{n}\sum_{t=0}^{n-1} c_\phi(e_t)=0$.
But each non-tight edge contributes at least $\alpha$, so if $N_n$ denotes the number of indices $t<n$ with $e_t\notin E^{(0)}$,
we have $\sum_{t=0}^{n-1} c_\phi(e_t)\ge \alpha N_n$.
Thus $\liminf_{n\to\infty} \alpha N_n/n =0$, which implies $N_n/n\to 0$ along a subsequence and in fact forces:
for every $\varepsilon>0$ there exists $N_\varepsilon$ such that for all $n\ge N_\varepsilon$, $N_n/n\le \varepsilon$
(otherwise a positive lower bound on $N_n/n$ would force a positive lower bound on the liminf).

This proves that tight edges occur with asymptotic density $1$.

For the dichotomy: consider the SCC decomposition of $G^{(0)}$.
Since $\pi$ uses tight edges with density $1$, it enters SCCs of $G^{(0)}$ infinitely often.
Let $\mathscr{S}$ be the finite set of SCCs of $G^{(0)}$ that are visited infinitely often by $\pi$.
At least one SCC in $\mathscr{S}$ is visited with positive lower density (pigeonhole principle on visits within prefixes).
If every SCC in $\mathscr{S}$ is periodic (a directed cycle), then the only way to visit more than one SCC infinitely often is to traverse non-tight
connecting edges between SCCs infinitely often. But non-tight edges have density $0$; hence such switches can occur only finitely often.
Therefore $\pi$ is eventually trapped in a single periodic SCC, yielding eventual periodicity (case (P)).
Otherwise, some SCC in $\mathscr{S}$ is aperiodic and is visited with positive lower density (case (A)).

Remark

Lemma is the gap-free replacement for “gap localizes to a unique core.”
It says: minimizing trajectories spend density-$1$ time on locally tight edges; if they do not become eventually periodic, they must spend positive density time
in an aperiodic recurrent tight SCC.

Lemma 14.C: Doeblin word on an aperiodic minimizing SCC (assumption interface)

The following step depends on structural zeros and the active face $S$ on which the dynamics lives.
In our program, the descriptor reduction is designed so that on each recurrent SCC one can identify an invariant active face.
We state this explicitly as an interface assumption; it is checkable and becomes a finite obstruction if it fails.

Remark

Active-face invariance is now treated as a certified outcome of the descriptor reduction via the face map $S(\cdot)$ (Definition ) and SCC face $S(H)$ (Lemma ).

Lemma — Aperiodic tight SCC yields a Doeblin word (certified)

Assume $H$ is an aperiodic SCC of the tight graph $G^{(0)}$.
Assume the descriptor reduction provides a face map $S(\cdot)$ (Definition ) and let $S(H)$ be the canonical SCC face.
If the coordinate support digraph $\Gamma(H)$ on $S(H)$ (Definition ) is strongly connected, then there exists an admissible word $w$ in $H$
whose block product $B(w)$ is strictly positive on $S(H)\times S(H)$.
Consequently, $w$ is a Doeblin word on $S(H)$ with explicit bounds $\varepsilon=m_*^{|w|}$ and $U=(dM_*)^{|w|}$.

Proof

This follows from Corollary :
aperiodicity of $H$ provides mixing of vertex transitions, while strong connectivity of $\Gamma(H)$ provides coordinate reachability on $S(H)$.
Concatenation yields a word with strictly positive $S(H)\times S(H)$ block, and explicit Doeblin bounds follow from FTG entry bounds.

Remark

The additional hypothesis “support connectivity on $S$” is precisely where structural-zero obstructions can live.
In the gap-free upgrade, these become explicit finite obstructions rather than hidden assumptions.

Theorem 14.1: Gap-free dichotomy and projective regularity along minimizers

Theorem — Gap-free dichotomy on minimizing paths

Assume FTG and a finite descriptor reduction to a weighted digraph $G=(V,E)$ with min mean $\lambda_*$.
Fix a calibrating potential $\phi$ as in Lemma and tight graph $G^{(0)}$.
Let $\pi$ be a minimizing path.

Then exactly one of the following holds:

• $\pi$ is eventually periodic on a tight periodic SCC of $G^{(0)}$;
• $\pi$ visits an aperiodic tight SCC $H$ with positive lower density. If the descriptor-face certificates hold on $H$ (face map $S(\cdot)$ and strong connectivity of $\Gamma(H)$ on $S(H)$),
  then there exists a Doeblin word $w$ in $H$ whose occurrences along $\pi$ have positive lower density.

Proof

Lemma gives the dichotomy (P) vs (A) at the level of the tight graph.
In case (A), apply Lemma to obtain a Doeblin word $w$ on $H$.
Since $\pi$ visits $H$ with positive lower density and $H$ is strongly connected, standard return-time arguments in a finite SCC imply that
any fixed word $w$ appearing in $H$ has positive lower density of occurrences along $\pi$ (possibly after restricting to visits inside $H$).

Corollary — Gap-free projective regularity along minimizing paths

In the setting of Theorem , assume case (A) and that a Doeblin word $w$ exists on an active face $S$
and occurs along $\pi$ with lower density $\rho>0$ (or, in the stronger case, with bounded gaps $L_{\mathrm{syn}}$).
Then Hilbert distances contract exponentially along $\pi$ with an explicit rate determined by $(d,m_*,M_*,|w|)$ and $\rho$ (or $L_{\mathrm{syn}}$),
yielding a unique calibrated projective direction along $\pi$.

Proof

Each occurrence of the Doeblin word $w$ yields a contraction by a uniform factor $\tau<1$ in Hilbert metric via the same Doeblin$\Rightarrow$diameter$\Rightarrow$Birkhoff chain as in the main paper.
If occurrences have bounded gaps $L_{\mathrm{syn}}$, we recover the same explicit rate as Theorem 13. X.
If only a positive lower density $\rho$ is known, then in $n$ steps the number of occurrences is at least $\rho n – o(n)$, giving
$d_H(\cdot)\le \tau^{\rho n – o(n)}d_H(\cdot)$ and hence exponential decay with rate approximately $\rho(-\log\tau)$.
Uniqueness of the projective limit follows by Cauchy convergence of images of any two initial vectors under repeated contraction events.

Gap-free obstructions (preview)

The gap-free theorem introduces additional finite obstructions beyond (O1)–(O4) of the gap-based pipeline:

• tight graph has only periodic SCCs visited by minimizers (forces periodic regime);
• active face is not invariant on the minimizing SCC (face-instability);
• structural zeros prevent support-connectivity on the active face (no primitive block even in aperiodic SCC);
• return density of Doeblin words degenerates to $0$ on minimizing paths (requires stronger recurrence assumptions or extra certificate).

These are finite and will be formalized in the obstructions module.

How the gap-certified theorem fits (as a specialization)

Corollary — Gap-certified rigidity as a certifiable specialization

Assume the strict gap hypothesis of Theorem holds, so minimizing measures are supported on the critical subgraph $G_*.$
If, moreover, there exists a Doeblin word $w$ on the active face of a critical component that is syndetic with bound $L_{\mathrm{syn}},$
then the conclusions of Theorem hold with the explicit constants stated there.

Proof

Under strict gap, minimizers localize to $G_*.$ The remaining steps are exactly the Doeblin$\Rightarrow$diameter$\Rightarrow$Birkhoff contraction chain
together with the syndetic return lemma, as already proved in the main text.

Formal obstruction taxonomy

Gap-Free Obstructions and Finite Witnesses

This section refines the obstruction taxonomy to account for the gap-free upgrade.
The central point is that removing the strict gap introduces new failure modes tied to
the tight-edge graph induced by calibration and to face stability on minimizing supports.

Tight-edge graph and its SCC structure

Fix a calibrating potential $\phi$ and define the tight-edge graph $G^{(0)}=(V^{(0)},E^{(0)})$ by
$E^{(0)}=\{e\in E: c_\phi(e)=0\}$ as in the gap-free module.

Definition — Gap-free obstruction predicates

We say the gap-free pipeline is obstructed if at least one of the following holds.

• Every SCC of $G^{(0)}$ that is visited infinitely often by minimizing paths is periodic
  (i.e.\ each such SCC is a single directed cycle). Equivalently, the tight recurrence class contains no aperiodic SCC.
• For each tight SCC $H$ that is visited with positive lower density by a minimizing path,
  the descriptor reduction fails to provide a consistent face map $S(\cdot)$ on $H$ (Definition ).
• There exists an aperiodic tight SCC $H$ such that the SCC face $S(H)$ exists, but the coordinate digraph $\Gamma(H)$ on $S(H)$ is not strongly connected (Definition ).
• Although an aperiodic tight SCC $H$ and a Doeblin word $w$ exist, there exist minimizing paths
  whose lower density of occurrences of $w$ is zero.

Finite witnesses

Theorem — Finite witnesses for OG1–OG4

Each obstruction OG1–OG4 admits a finite certificate witness.

• SCC decomposition of $G^{(0)}$ with a proof that all recurrent SCCs are cycles.
  A witness is a list of SCCs visited by a given minimizing run, each shown to have period equal to its size.
• For each candidate SCC $H$, a witness is a pair of edges in $H$ that disagree on support propagation, forcing face changes,
  or a finite set of words in $H$ that activates an outside coordinate from an $S$-supported start.
• A witness is an explicit pair $(H,S)$ together with a finite search bound $N_{\max}$ such that for every admissible word $w$ of length $\le N_{\max}$ in $H$,
  the product $B(w)$ has a structural zero on $S\times S$. (This is checkable because the set of words is finite for each fixed length.)
• A witness is a minimizing path (or a finite-state strategy generating one) plus an avoidance automaton showing that occurrences of $w$ can be forced to have arbitrarily long gaps,
  yielding zero lower density.

Remark

In practice OG4 is typically eliminated by strengthening recurrence from “positive lower density” to a syndetic (bounded-gap) return
certificate on the minimizing SCC. This restores the explicit global rate constants as in the gap-certified specialization.

Algorithmic checks (pseudocode)

[H]
\caption{Build tight-edge graph and classify SCC periodicity}
[1]
\Require Reduced graph $G=(V,E)$, costs $c$, and calibrating potential $\phi$
\Ensure Tight graph $G^{(0)}$ and a list of SCCs labeled periodic/aperiodic
\State $E^{(0)} \gets \{e\in E:\ c(e)-\lambda_* + \phi(\mathrm{tail}(e))-\phi(\mathrm{head}(e)) = 0\}$
\State Compute SCC decomposition of $G^{(0)}$
\ForAll{SCCs $H$}
\State Compute the gcd of cycle lengths in $H$ (period)
\If{period = 1 and $|H|>1} label aperiodic \Else label periodic \EndIf
\EndFor

[H]
\caption{Face-stability test on an SCC (OG2)}
[1]
\Require Tight SCC $H$, templates/blocks labeling its edges
\Ensure Either invariant face $S$ or witness of face instability (OG2)
\State Initialize $S \gets$ intersection of supports of images of a positive test vector under generators of $H$
\Repeat
\State Propagate $S$ through each generator; if new coordinates activate, update $S$
\Until{$S$ stabilizes or contradiction found}
\If{$S$ stabilizes and all generators preserve $\mathbb{R}^S_{>0}$} \Return $S$
\Else \Return witness of OG2 \EndIf

[H]
\caption{Primitivity / Doeblin word search on $(H,S)$ (OG3)}
[1]
\Require Aperiodic SCC $H$, invariant face $S$, bounds $(m_*,M_*)$, horizon $N_{\max}$
\Ensure Either Doeblin word $w$ or OG3 witness
\For{$N=1$ to $N_{\max}$}
\ForAll{admissible words $w$ of length $N$ in $H$}
\State Form product $B(w)$ restricted to $S\times S$
\If{$B(w)$ is strictly positive on $S\times S$} \Return $w$ \EndIf
\EndFor
\EndFor
\State \Return OG3 witness (no Doeblin word up to $N_{\max}$)

[H]
\caption{Return-density / syndetic check for a word $w$ (OG4)}
[1]
\Require SCC automaton for $H$, word $w$
\Ensure Either bounded-gap $L_{\mathrm{syn}}$ or witness of OG4
\State Build avoidance automaton $\mathcal{A}_{\neg w}$
\If{$\mathcal{A}_{\neg w}$ has a directed cycle}
\State \Return OG4 witness (arbitrarily long gaps possible)
\Else
\State $L_{\mathrm{syn}} \gets$ length of the longest path in $\mathcal{A}_{\neg w}$
\State \Return $L_{\mathrm{syn}}$
\EndIf

Definition — Finite obstruction predicates

• (O1) No gap: there exist cycles $\gamma_1\subseteq G_*$ and $\gamma_2\not\subseteq G_*$ with $\bar c(\gamma_2)=\lambda_*$.
• (O2) No primitive block on core: on every face-restricted critical component, no admissible block product is positive on its active face.
• (O3) No syndetic return: for every candidate Doeblin word $w$ on $G_*$, the “avoid-$w$” automaton contains a cycle (unbounded gaps).
• (O4) Descriptor explosion: the descriptor construction does not yield a finite graph $G$ under the stated bounds.

Theorem — Certificate completeness

If none of (O1)–(O4) holds, then the hypotheses of Theorem can be satisfied on a critical component and extremal projective rigidity holds.
If any of (O1)–(O4) holds, then at least one required certificate component fails, and rigidity cannot be concluded from this pipeline.

Remark

The taxonomy is intentionally finite: each obstruction is witnessed by a finite object (a pair of cycles, a finite search failure for primitivity,
a cycle in an avoidance automaton, or non-finiteness of the descriptor space).

\appendix

Computing $\lambda_*$, a calibrating potential, and the tight subgraph

This appendix records an explicit finite procedure to compute the objects in Section .
All steps are standard finite graph algorithms; we include them to make the normalization fully machine-checkable.

Computing the minimal cycle mean

Let $G=(V,E)$ with $|V|=n$, $|E|=m$, and costs $c:E\to\mathbb{R}$.
The minimal cycle mean

can be computed in $O(nm)$ time using Karp’s algorithm.

[H]
\caption{Karp minimal cycle mean}
[1]
\Require Directed graph $G=(V,E)$, costs $c(e)$
\Ensure $\lambda_*$
\State Choose any ordering of vertices and initialize $d_0(v)=0$ for all $v\in V$
\For{$k=1$ to $n$}
\ForAll{$v\in V$}
\State $d_k(v)\gets \min_{(u\to v)\in E}\big(d_{k-1}(u)+c(u\to v)\big)$
\EndFor
\EndFor
\ForAll{$v\in V$}
\State $M(v)\gets \max_{0\le k\le n-1}\frac{d_n(v)-d_k(v)}{n-k}$
\EndFor
\State $\lambda_*\gets \min_{v\in V} M(v)$
\State \Return $\lambda_*$

Computing a calibrating potential

Set $\tilde c(e)=c(e)-\lambda_*$.
Then $G$ has no negative cycles with respect to $\tilde c$ by definition of $\lambda_*$.
A potential $\phi$ such that $c_\phi(e)=\tilde c(e)+\phi(u)-\phi(v)\ge 0$ for all $e:u\to v$ can be obtained from shortest-path distances.

[H]
\caption{Calibrating potential via shortest paths}
[1]
\Require Graph $G=(V,E)$, reduced costs $\tilde c(e)=c(e)-\lambda_*$
\Ensure Potential $\phi$ with $c_\phi(e)\ge 0$ for all $e$
\State Add a super-source $s$ with zero-cost edges $(s\to v)$ to every $v\in V$
\State Run Bellman–Ford on $(V\cup\{s\},E\cup\{(s\to v)\})$ with costs $\tilde c$ to compute distances $\phi(v)=\mathrm{dist}(s,v)$
\State \Return $\phi$

Remark

Because there are no negative cycles, Bellman–Ford terminates and returns finite distances.
The inequality $\phi(v)\le \phi(u)+\tilde c(u\to v)$ is exactly $c_\phi(u\to v)\ge 0$.

Extracting the tight subgraph and its SCC structure

Given $\phi$, compute $c_\phi(e)$ and define $E^{(0)}=\{e:c_\phi(e)=0\}$ as in Definition .
This yields the tight subgraph $G^{(0)}$. SCC decomposition runs in $O(n+m)$ time (Tarjan/Kosaraju).
Aperiodicity of an SCC is certified by computing the gcd of its cycle lengths (linear-time in the SCC via a spanning tree + back-edge depth differences).

[H]
\caption{Tight subgraph + SCC periodicity labels}
[1]
\Require $G=(V,E)$, costs $c$, $\lambda_*$, potential $\phi$
\Ensure Tight graph $G^{(0)}$ and SCCs labeled periodic/aperiodic
\State $E^{(0)}\gets \{u\to v\in E:\ c(u\to v)-\lambda_*+\phi(u)-\phi(v)=0\}$
\State Compute SCC decomposition of $G^{(0)}$
\ForAll{SCCs $H$}
\State Compute $\mathrm{per}(H)=$ gcd of cycle lengths in $H$
\If{$\mathrm{per}(H)=1$ and $|H|>1$} label aperiodic \Else label periodic \EndIf
\EndFor

Complexity summary

All objects in Section are computable in polynomial time from the reduced finite graph:

• Karp minimal mean: $O(nm)$.
• Bellman–Ford potential: $O(nm)$.
• Tight graph extraction: $O(m)$.
• SCC decomposition: $O(n+m)$.

Thus the canonical normalization and tight geometry can be produced and checked algorithmically as part of the finite certification pipeline.

Certification algorithms (pseudocode)

[H]
\caption{Compute extremal mean and critical subgraph}
[1]
\Require Weighted digraph $G=(V,E)$ with cost $c:E\to\mathbb{R}$
\Ensure $\lambda_*$ and critical subgraph $G_*$
\State Compute $\lambda_* \gets$ KarpMinCycleMean$(G,c)$
\State Initialize $E_* \gets \emptyset$
\ForAll{edges $e\in E$}
\If{$e$ lies on some cycle with mean $\lambda_*$} \Comment{detect via potentials or cycle test}
\State $E_* \gets E_* \cup \{e\}$
\EndIf
\EndFor
\State Output $G_*=(V_*,E_*)$ where $V_*=$ vertices incident to $E_*$

[H]
\caption{Gap certificate (finite)}
[1]
\Require $G$, $G_*$, costs $c$
\Ensure Either $\delta>0$ or witness of (O1)
\State Compute $\lambda_* \gets$ min cycle mean on $G$
\State Compute $\lambda_{\mathrm{out}} \gets$ min cycle mean on the subgraph induced by edges $E\setminus E_*$
\If{$\lambda_{\mathrm{out}} = \lambda_*$}
\State Return witness cycles (O1)
\Else
\State Return $\delta \gets \lambda_{\mathrm{out}} – \lambda_*$
\EndIf

[H]
\caption{Primitive-block and Doeblin constants on a critical SCC}
[1]
\Require Critical SCC $\mathcal{C}$, templates $\mathcal{T}$, bounds $(m_*,M_*)$, search horizon $N_{\max}$
\Ensure Either a Doeblin word $w$ with constants $(\varepsilon,U,\tau)$ or witness of (O2)
\For{$N=1$ to $N_{\max}$}
\ForAll{admissible words $w$ of length $N$ in $\mathcal{C}$}
\State Form block product $B(w)$
\If{$B(w)$ is positive on active face $S$}
\State $\varepsilon \gets m_*^{|w|}$; $U\gets (dM_*)^{|w|}$
\State $\Delta \gets 2\log(U/\varepsilon)$; $\tau \gets \tanh(\Delta/4)$
\State \Return $(w,\varepsilon,U,\tau)$
\EndIf
\EndFor
\EndFor
\State \Return witness of (O2)

[H]
\caption{Syndetic return check for a word $w$ on an SFT}
[1]
\Require SFT automaton for the critical component, word $w$
\Ensure Either gap bound $L_{\mathrm{syn}}$ or witness of (O3)
\State Build avoidance automaton $\mathcal{A}_{\neg w}$ for paths avoiding $w$
\If{$\mathcal{A}_{\neg w}$ contains a directed cycle}
\State \Return witness cycle (O3)
\Else
\State $L_{\mathrm{syn}} \gets$ length of the longest path in $\mathcal{A}_{\neg w}$
\State \Return $L_{\mathrm{syn}}$
\EndIf

Constants ledger (dependencies)

Given $(d,m_*,M_*)$ and a selected Doeblin word $w$ of length $|w|$ with syndetic bound $L_{\mathrm{syn}}$:

References (minimal)

• G. Birkhoff, Extensions of Jentzsch’s theorem, Trans. Amer. Math. Soc. 85 (1957).
• P. Bushell, Hilbert’s metric and positive contraction mappings, Arch. Ration. Mech. Anal. 52 (1973).
• R. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math. 23 (1978).
• D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press (1995).