% global_universality_theorems.tex

\section{From regional robustness to cover/atlas universality on compact normalized families}
\label{sec:global-universality-thms}

The robustness layer establishes a local principle:
whenever a robust certificate exists at a parameter value $\theta$, the same conclusions hold on an explicit neighborhood around $\theta$, with conservatively degraded constants.
This section records what is required to upgrade from ``open neighborhoods away from degeneracy'' to a global statement on a compact normalized parameter family.

\noindent\textbf{Terminology.} Throughout this section, "global" means \emph{on a fixed compact normalized family $\Theta$}, and "universality" is always understood \emph{within the certified class} in the \emph{cover-or-atlas} sense: either good-global contraction is certified, or an explicit boundary-atlas report localizes the obstruction/degeneracy set.


\subsection{Two global targets}

There are two distinct global goals.

\begin{itemize}[leftmargin=2em]
\item \textbf{Global regime decidability (already achieved on the certified class).}
For any instance in the certified class, the pipeline halts and returns a finite outcome object:
\emph{either} a robust contraction certificate, \emph{or} a concrete obstruction witness (OG1--OG4).
\item \textbf{Good-global contraction universality (stronger).}
On a parameter region $\Theta$, every parameter point lies in the contraction regime, so the exceptional set is empty and one can state a single uniform robustness radius on all of $\Theta$.
\end{itemize}

The remainder of this section concerns the second target.

\subsection{Paired radii convention}

In the robust certificate contract, perturbations may act on two layers: costs and template entries.
Accordingly, the local robustness radius naturally comes as a pair
\[
\boldsymbol{\varepsilon}^*(\theta) := (\varepsilon_c^*(\theta),\,\varepsilon_A^*(\theta)),
\]
meaning that the certificate remains valid whenever both perturbations satisfy
$\|\Delta c\| \le \varepsilon_c^*(\theta)$ and $\|\Delta A\| \le \varepsilon_A^*(\theta)$ in the RU-A metric.
For compactness and cover arguments, it is often convenient to also record the conservative scalar floor
\[
\varepsilon_{\min}^*(\theta) := \min\{\varepsilon_c^*(\theta),\,\varepsilon_A^*(\theta)\}.
\]
This scalar floor is sufficient for a single-radius cover statement, while the pair is the natural artifact for downstream reproducibility.

\subsection{Uniform margins and a global contraction theorem}

Let $\Theta$ be a compact parameter region.
For each $\theta\in\Theta$, the reduction stage produces a tight graph $H(\theta)$, face data, and (when obstruction gates do not fire) a Doeblin witness word $w(\theta)$ on an aperiodic tight SCC.

\begin{definition}[Uniform robust margins on a region]
\label{def:uniform_margins}
We say that $\Theta$ admits \emph{uniform robust margins} for a fixed witness word $w$ if there exist constants $\gamma_0,\delta_0>0$ and a fixed aperiodic tight SCC $H$ such that for every $\theta\in\Theta$:
\begin{itemize}[leftmargin=2em]
\item the tightness gap satisfies $\gamma(\theta)\ge \gamma_0$ and the tight-core graph equals $H(\theta)=H$;
\item the Doeblin witness product along $w$ satisfies $\min(P_w(\theta))\ge \delta_0$ on the active coordinates;
\item the recurrence forcing predicate RC1 holds on $H$ for the word $w$ (equivalently: the tight-language avoidance automaton contains no directed cycle).
\end{itemize}
\end{definition}

\begin{theorem}[Good-global contraction universality on $\Theta$ from uniform margins]
\label{thm:global_universality_uniform}
Assume $\Theta$ is compact and normalized.
If $\Theta$ admits uniform robust margins in the sense of Definition~\ref{def:uniform_margins} for a fixed Doeblin witness word $w$, then there exist:
\begin{itemize}[leftmargin=2em]
\item a paired uniform robustness radius
$\boldsymbol{\varepsilon}_{\mathrm{global}}=(\varepsilon_{c,\mathrm{global}},\varepsilon_{A,\mathrm{global}})$,
\item a conservative scalar floor
$\varepsilon_{\min,\mathrm{global}}:=\min\{\varepsilon_{c,\mathrm{global}},\varepsilon_{A,\mathrm{global}}\}>0$,
\item and a uniform rate pack $(\tau_{\mathrm{global}},C_{\mathrm{global}},\kappa_{\mathrm{global}})$,
\end{itemize}
with the following property.
For every $\theta\in\Theta$:
\begin{itemize}[leftmargin=2em]
\item every tight trajectory in the aperiodic SCC $H$ experiences Doeblin blocks with a bounded-gap modulus that is uniform over $\Theta$;
\item consequently, the associated projective dynamics contract uniformly with rate $\tau_{\mathrm{global}}<1$ and prefactor $C_{\mathrm{global}}$;
\item the same conclusions remain valid under all perturbations satisfying $\|\Delta c\|\le \varepsilon_{c,\mathrm{global}}$ and $\|\Delta A\|\le \varepsilon_{A,\mathrm{global}}$ (RU-A metric), and in particular for all perturbations of size at most $\varepsilon_{\min,\mathrm{global}}$ in either layer.
\end{itemize}
Moreover, $\boldsymbol{\varepsilon}_{\mathrm{global}}$ is computable from the uniform margins $(\gamma_0,\delta_0)$ and the fixed witness metadata (word length and uniform entry bounds) by taking the componentwise minimum of the explicit thresholds from RU-B and RU-C.
\end{theorem}

\begin{proof}
By RU-B (tight-core stability), any perturbation smaller than the explicit threshold determined by $\gamma_0$ preserves the tightness classification and the SCC decomposition.
By RU-C (Doeblin stability), the fixed Doeblin product along $w$ with entry floor $\delta_0$ persists under perturbations below the explicit telescoping-product threshold, yielding a degraded floor $\delta_0'$.
Since $H$ and $w$ are fixed throughout $\Theta$, the avoidance automaton used to encode RC1 is fixed.
RC1 holding implies that this finite automaton has no directed cycle; hence every tight trajectory must hit the Doeblin block within at most $L_{\mathrm{syn}}(H,w)\le |V(\mathsf{A}(H,w))|$ steps (Corollary~\ref{cor:Ls_size_bound}), giving a uniform recurrence modulus.
Combining the recurrence modulus with the Hilbert/Birkhoff contraction lemma and the explicit rate pack yields uniform projective contraction with constants depending only on $\delta_0'$ and the certificate geometry.
Taking the componentwise minimum of the explicit RU-B and RU-C thresholds produces a paired radius valid for all $\theta\in\Theta$.
\end{proof}

\subsection{A global theorem phrased in terms of degeneracy avoidance}

The uniform-margin hypothesis is clean, but one still wants a practical route to verify it.
A useful middle step is to express good-global contraction universality on compact normalized $\Theta$ within the certified class as the absence of certain degeneracy surfaces.

\begin{definition}[Degeneracy sets]
\label{def:degeneracy_sets}
Fix a witness word $w$ and consider a region $\Theta$ on which the tight SCC $H$ and the active coordinates are well-defined.
Define the following subsets of $\Theta$:
\begin{itemize}[leftmargin=2em]
\item $\mathcal{D}_{\gamma} := \{\theta\in\Theta : \gamma(\theta)=0\}$ (tightness degeneracy / tie surfaces),
\item $\mathcal{D}_{\delta}(w) := \{\theta\in\Theta : \min(P_w(\theta))=0\}$ (loss of strict positivity for the witness product),
\item $\mathcal{D}_{\mathrm{RC1}}(w) := \{\theta\in\Theta : \text{RC1 fails for }(H,w)\}$ (recurrence-forcing failure).
\end{itemize}
\end{definition}

\begin{proposition}[Good-global contraction universality from empty degeneracy on $\Theta$]
\label{prop:global_from_empty_deg}
Assume $\Theta$ is compact and that $H$ and $w$ are constant on $\Theta$.
If
\[\mathcal{D}_{\gamma}=\emptyset,\qquad \mathcal{D}_{\delta}(w)=\emptyset,\qquad \mathcal{D}_{\mathrm{RC1}}(w)=\emptyset,\]
then $\Theta$ admits uniform robust margins and Theorem~\ref{thm:global_universality_uniform} applies.
In particular, $\gamma$ and $\theta\mapsto \min(P_w(\theta))$ have strictly positive minima on $\Theta$.
\end{proposition}

\begin{proof}
On a region where $H$ and $w$ are fixed, $\gamma(\theta)$ is the minimum of finitely many strict reduced-cost separations among edges in the fixed reduced instance, hence is continuous.
The map $\theta\mapsto \min(P_w(\theta))$ is continuous because $P_w(\theta)$ is a finite product of matrices whose entries depend continuously on $\theta$.
On a compact set, each continuous function attains its minimum.
If the corresponding zero set is empty, the minimum must be strictly positive, giving constants $\gamma_0,\delta_0>0$.
RC1 being satisfied everywhere on $\Theta$ provides the recurrence-forcing item in Definition~\ref{def:uniform_margins}.
\end{proof}

For the linear parameter families treated in \S\ref{sec:param-chambers}, the parameter space decomposes into finitely many polyhedral chambers on which the tight graph and the witness metadata are constant.
In that setting, Proposition~\ref{prop:global_from_empty_deg} can be applied chamberwise, and good-global contraction universality on compact normalized $\Theta$ within the certified class reduces to taking minima over the finitely many certified chambers.

\subsection{Region-mode coverage as a certificate of good-global contraction on compact normalized families}

RU-E provides a covering principle: each robust certificate at $\theta$ certifies a whole neighborhood around $\theta$.
A global statement on $\Theta$ follows once the union of certified neighborhoods covers $\Theta$.

\begin{proposition}[Good-global contraction certificate via region coverage]
\label{prop:global_via_cover}
Assume $\Theta$ is compact and normalized.
Suppose region mode produces a finite family of robust certificates $\{\mathcal{C}_i\}$ with certified paired radii $\boldsymbol{\varepsilon}^*(\mathcal{C}_i)$ such that
\[\Theta \subset \bigcup_i B(\theta_i,\,\varepsilon_{\min}^*(\mathcal{C}_i)),\]
where $B(\theta,\varepsilon)$ denotes the ball in parameter space used for sampling and $\varepsilon_{\min}^*$ is the conservative scalar floor.
Then $\Theta$ admits a \emph{good-global contraction certificate} within the certified class on the compact normalized family $\Theta$.
One may set
\[
\gamma_0 := \min_i \gamma(\mathcal{C}_i),\qquad
\delta_0 := \min_i \delta(\mathcal{C}_i),\qquad
\boldsymbol{\varepsilon}_{\mathrm{global}} := \bigl(\min_i \varepsilon_c^*(\mathcal{C}_i),\;\min_i \varepsilon_A^*(\mathcal{C}_i)\bigr),
\]
and conclude uniform contraction on all of $\Theta$ with explicit degraded constants.
\end{proposition}

\begin{proof}
The conclusion is exactly the RU-E covering theorem applied to the finite subcover exhibited by region mode.
Uniformity follows by taking minima over the finite family.
\end{proof}

\begin{proposition}[Finite termination of region mode under a uniform scalar floor]
\label{prop:termination}
Assume $\Theta\subset\mathbb{R}^d$ is compact and normalized and admits a uniform lower bound
\[\inf_{\theta\in\Theta} \varepsilon_{\min}^*(\theta) \ge \varepsilon_0>0\]
for the conservative scalar floors returned by the pipeline.
Then a grid net of mesh $\varepsilon_0/2$ produces a finite cover, hence region mode terminates with a good-global contraction certificate within the certified class on the compact normalized family $\Theta$.
\end{proposition}

\begin{proof}
Compactness implies $\Theta$ can be covered by finitely many balls of radius $\varepsilon_0/2$.
At each ball center, the pipeline returns a certificate with scalar floor at least $\varepsilon_0$.
Therefore each such certificate neighborhood contains the corresponding grid ball, giving a finite cover of $\Theta$.
\end{proof}

\subsection{A practical push: hybrid chamberwise verification}

The most practical route to good-global contraction universality on compact normalized families (within the certified class) is a hybrid procedure:

\begin{itemize}[leftmargin=2em]
\item use the chamber mechanism to identify regions on which $(H,w)$ are constant,
\item on each chamber, either prove degeneracy sets are empty (Proposition~\ref{prop:global_from_empty_deg}), or close coverage via region mode (Proposition~\ref{prop:global_via_cover}),
\item if coverage fails, the uncovered pieces are automatically labeled as ``near degeneracy'' and come with obstruction witnesses.
\end{itemize}

The key point is that the framework never hides the boundary: good-global contraction universality on compact normalized $\Theta$ within the certified class is exactly the claim that all named degeneracies are absent on $\Theta$.
When they are present, the pipeline returns a concrete finite witness locating them.

\begin{algorithm}[H]
\caption{Hybrid cover/atlas check on compact normalized $\Theta$ within the certified class (certificate-driven)}
\label{alg:global-universality}
\begin{algorithmic}[1]
\Require Compact region $\Theta$ (parameterization), perturbation metric (RU-A contract)
\Ensure Either a GlobalUniversalityReport for compact normalized $\Theta$ within the certified class, or an explicit near-degeneracy/obstruction report
\State Partition $\Theta$ into chambers where $(H,w)$ are constant (by the tight-core/chamber mechanism)
\For{each chamber $\Omega$}
  \State Run region mode on $\Omega$ with adaptive refinement
  \If{coverage closes}
    \State Record chamberwise global bounds $\gamma_0(\Omega),\delta_0(\Omega),\boldsymbol{\varepsilon}_{\mathrm{global}}(\Omega)$
  \Else
    \State Record uncovered set and its near-degeneracy label (tie surface, positivity collapse, or RC1 failure)
  \EndIf
\EndFor
\State If all chambers close coverage, take minima of chamberwise bounds to form a global report on $\Theta$
\end{algorithmic}
\end{algorithm}

\begin{remark}[What is and is not proved ``globally'']
The results above provide two globally valid statements.

\begin{itemize}[leftmargin=2em]
\item On the certified class, the pipeline provides a global decidability frontier: it always returns a finite obstruction or a finite robust contraction certificate.
\item On a parameter family $\Theta$, a good-global contraction universality statement is achieved when either uniform margins are proved or region-mode coverage closes.
\end{itemize}

If neither occurs, the output is still constructive: one gets an explicit description of where and how universality can fail.
\end{remark}

\subsection{Beyond compact families: normalization for cover/atlas universality within the certified class}

When one asks for cover/atlas universality beyond a fixed compact normalized family, the obstruction is usually not conceptual but topological: the raw parameter space is typically \emph{noncompact} (because of scaling degrees of freedom, unbounded costs, or templates whose entries can blow up or collapse to zero).
The cover/atlas conclusions above are therefore best viewed as \emph{compact} statements within the certified class.

In many positive-template models, however, the noncompactness is largely artificial.
Two standard reductions convert noncompact questions into compact ones:

\begin{itemize}[leftmargin=2em]
\item \textbf{Projectivization/scaling.}
The extremal growth rate is homogeneous under simultaneous scaling of templates.
Working in projective coordinates (or fixing a canonical scale) removes this degree of freedom.
\item \textbf{Canonical normalization.}
One may fix a normalization such as $\max_{i,j} A_k(i,j)=1$ (entrywise), or $\|A_k\|_1=1$ (column-stochastic scaling), provided the admissible class is closed under the chosen normalization and the pipeline invariants are scale-invariant.
\end{itemize}

The practical upshot is that a cover/atlas universality theorem can often be stated as a compact cover/atlas universality theorem on a normalized parameter space within the certified class, together with an explicit description of the boundary faces where normalization breaks (typically exactly the named degeneracies $\gamma=0$ or $\delta=0$).

\begin{proposition}[Cover/atlas universality via compact normalization within the certified class]
\label{prop:global_via_normalization}
Suppose the admissible parameter space $\Theta_{\mathrm{raw}}$ admits a continuous normalization map
\[\mathcal{N}:\Theta_{\mathrm{raw}}\to\Theta_{\mathrm{norm}}\]
into a compact set $\Theta_{\mathrm{norm}}$ such that:

\begin{itemize}[leftmargin=2em]
\item the pipeline predicates (tightness, Doeblin positivity, and the RC1 automaton) are invariant under the normalization, and
\item the robust margins $(\gamma,\delta)$ and the paired robust radius $\boldsymbol{\varepsilon}^*$ can be chosen as functions of $\mathcal{N}(\theta)$.
\end{itemize}

If $\Theta_{\mathrm{norm}}$ admits a good-global contraction certificate within the certified class on the compact normalized family $\Theta_{\mathrm{norm}}$ (for example by Proposition~\ref{prop:global_from_empty_deg} or by closing region-mode coverage as in Proposition~\ref{prop:global_via_cover}), then the corresponding universality conclusion holds for all parameters $\theta\in\Theta_{\mathrm{raw}}$ whose normalization is defined.
Moreover, the complement is explicitly contained in the normalization boundary, which is a subset of the named degeneracy loci.
\end{proposition}

\begin{proof}
By hypothesis, the decision predicates and the robustness radii depend only on the normalized parameters.
Therefore the uniform contraction conclusion on $\Theta_{\mathrm{norm}}$ pulls back to $\Theta_{\mathrm{raw}}$ wherever $\mathcal{N}$ is defined.
The only possible failure modes are points where normalization is undefined or discontinuous, which in positive-template settings correspond to entries collapsing to zero or to tightness degeneracies; these are contained in the exceptional set described earlier.
\end{proof}

\begin{remark}[What remains to claim a truly ``global'' theorem]
Proposition~\ref{prop:global_via_normalization} turns the remaining work into two concrete tasks.

\begin{itemize}[leftmargin=2em]
\item Verify that your chosen normalization $\mathcal{N}$ preserves the admissible class and the pipeline invariants.
\item Prove (or certify) good-global contraction universality within the certified class on the compact normalized space $\Theta_{\mathrm{norm}}$.
\end{itemize}

The second task is exactly the compact problem solved by the chamberwise + region-mode machinery.
The first task is model-dependent but typically elementary (it is an algebraic check once the normalization is fixed).
\end{remark}
