% ROBUST_CERTIFICATE_RU_A.tex
\section{Robust Certificate Contract (RU-A)}\label{sec:robust-certificate-ru-a}

This section freezes a single portable object that stores \emph{all} margins and thresholds needed to make robustness claims
mechanically traceable.
Later sections may assert ``the conclusion survives perturbation'' only by citing explicit fields of this object.

\subsection{Perturbation model}

We allow two perturbation channels:

\begin{itemize}[leftmargin=*]
\item \textbf{Cost perturbations.} The edge cost vector $c:E\to\mathbb{R}$ is perturbed to $\tilde c=c+\Delta c$ with
\[
\|\Delta c\|_\infty := \max_{e\in E} |\Delta c(e)| \le \varepsilon_c .
\]
\item \textbf{Template perturbations.} Each template matrix $A^{(k)}\in\mathbb{R}_+^{d\times d}$ is perturbed to
$\tilde A^{(k)}=A^{(k)}+\Delta A^{(k)}$ under one of the following metrics, which must be fixed in the certificate:
\begin{itemize}[leftmargin=*]
\item \emph{Absolute entrywise:} $\|\Delta A\|_{\infty,\mathrm{ent}}:=\max_{k,i,j} |\Delta A^{(k)}_{ij}| \le \varepsilon_A$.
\item \emph{Relative entrywise:} $|\Delta A^{(k)}_{ij}| \le \varepsilon_A\,A^{(k)}_{ij}$ for all $k,i,j$.
\end{itemize}
\end{itemize}

When both channels are present, we write $\varepsilon := (\varepsilon_c,\varepsilon_A)$ and define the \emph{robust radius}
as the largest admissible pair $\varepsilon^\star$ stored in the robust certificate.

\subsection{Margins and openness predicates}

Fix a calibrated subaction $u:V\to\mathbb{R}$ and level $\lambda_*$, and reduced costs $c_u$ as in \eqref{eq:reduced-cost-u}.
Write $H:=\{e\in E: c_u(e)=0\}$ for the tight edge set.

\begin{definition}[Tightness gap margin]\label{def:gamma-margin}
Assume $H\neq E$. The \emph{tightness gap} is
\[
\gamma := \min\{c_u(e): e\in E\setminus H\}.
\]
If $H=E$ we set $\gamma:=+\infty$.
\end{definition}

\begin{lemma}[Openness of the tightness sign test]\label{lem:open-tightness}
Let $\tilde c=c+\Delta c$ with $\|\Delta c\|_\infty\le \varepsilon_c$ and keep $(u,\lambda_*)$ fixed.
Then for every edge $e\in E$,
\[
| \tilde c_u(e) - c_u(e) | \le \varepsilon_c,
\qquad
\tilde c_u(e) := \tilde c(e)-\lambda_*+u(\mathrm{tail}(e))-u(\mathrm{head}(e)).
\]
In particular, if $\varepsilon_c < \gamma/2$, then
\[
e\in H \implies \tilde c_u(e) \le \gamma/2,
\qquad
e\notin H \implies \tilde c_u(e) \ge \gamma/2.
\]
\end{lemma}

Lemma~\ref{lem:open-tightness} is the primitive ``openness'' statement behind tight-core stability; RU-B upgrades it to
a combinatorial invariance theorem for the tight graph and its SCC decomposition.

\medskip

Next, fix a Doeblin word witness $w=w_1\cdots w_L$ (over the template index alphabet) and define its product
\[
P_w := A^{(w_L)}\cdots A^{(w_1)}.
\]
Let $\delta:=\min_{i,j}(P_w)_{ij}$ be the Doeblin margin on the relevant block.

\begin{definition}[Uniform entry bound]\label{def:template-entry-bound}
Fix a bound $M\ge 1$ satisfying $\max_{k,i,j} A^{(k)}_{ij}\le M$ on the block where the Doeblin witness is evaluated.
The certificate must store the value of $M$ used in robustness inequalities.
\end{definition}

\begin{lemma}[Openness of Doeblin positivity under absolute perturbations]\label{lem:open-doeblin}
Assume absolute entrywise perturbations with $\|\Delta A\|_{\infty,\mathrm{ent}}\le \varepsilon_A$ and
$\max_{k,i,j} A^{(k)}_{ij}\le M$.
Let $\tilde P_w := \tilde A^{(w_L)}\cdots \tilde A^{(w_1)}$.
Then
\[
\|\tilde P_w-P_w\|_{\infty,\mathrm{ent}}
\le
L\,(M+\varepsilon_A)^{L-1}\,\varepsilon_A,
\]
and therefore the perturbed Doeblin margin satisfies
\[
\delta'(\varepsilon_A):=\min_{i,j}(\tilde P_w)_{ij}
\ge
\delta - L\,(M+\varepsilon_A)^{L-1}\,\varepsilon_A.
\]
In particular, any $\varepsilon_A$ such that $\delta'(\varepsilon_A)>0$ guarantees that the \emph{same} word $w$
remains a valid Doeblin witness in the perturbed instance, with margin at least $\delta'(\varepsilon_A)$.
\end{lemma}

\begin{remark}\label{rem:relative-perturbations}
For relative entrywise perturbations, one may rewrite Lemma~\ref{lem:open-doeblin} with $\varepsilon_A$ interpreted as a
relative factor and with $M$ replaced by the corresponding upper envelope on the block.
The robust certificate must record which perturbation metric is used and the bound actually fed into the estimate.
\end{remark}

\subsection{Robust certificate object}

We now freeze the schema.

\begin{definition}[Robust certificate object]\label{def:robust-certificate-object}
A \emph{robust certificate} is a structured object containing:
\begin{itemize}[leftmargin=*]
\item a model fingerprint (\texttt{model\_hash}) and the perturbation metric (\texttt{perturbation\_metric});
\item the calibration data $(u,\lambda_*)$ used for reduced costs, together with the tight set $H$;
\item margins and thresholds:
\begin{itemize}[leftmargin=*]
\item \texttt{tight\_gap\_gamma} storing $\gamma$ from Definition~\ref{def:gamma-margin};
\item \texttt{eps\_tight} such that $\varepsilon_c<\texttt{eps\_tight}$ implies Lemma~\ref{lem:open-tightness};
\item \texttt{doeblin.word} storing $w$, \texttt{doeblin.L} storing $L$, and \texttt{doeblin.delta} storing $\delta$;
\item \texttt{doeblin.M} storing the bound $M$ from Definition~\ref{def:template-entry-bound};
\item \texttt{eps\_doeblin} such that $\varepsilon_A<\texttt{eps\_doeblin}$ implies $\delta'(\varepsilon_A)>0$ in Lemma~\ref{lem:open-doeblin};
\item a rate pack section that records the contraction constants used in the unperturbed instance and provides
explicit degraded constants as functions of $(\varepsilon_c,\varepsilon_A)$ whenever $\varepsilon\le \varepsilon^\star$.
\end{itemize}
\item the aggregate robust radius \texttt{eps\_star}: a pair $\varepsilon^\star=(\varepsilon_c^\star,\varepsilon_A^\star)$ satisfying
\[
\varepsilon_c^\star \le \texttt{eps\_tight},
\qquad
\varepsilon_A^\star \le \texttt{eps\_doeblin},
\]
and any additional thresholds required by later robustness layers (RU-C and RU-D).
\end{itemize}
\end{definition}

\subsection{Concrete JSON schema (pipeline-facing)}

The TeX contract above is mirrored by a pipeline-facing JSON schema and an example instance.
These are provided as separate files in the repository root:

\begin{itemize}[leftmargin=*]
\item \texttt{robust\_certificate\_schema.json}
\item \texttt{robust\_certificate\_example.json}
\end{itemize}

For readability, we also display a concise schema skeleton here:

\begin{verbatim}
{
  "model_hash": "string",
  "perturbation_metric": {
    "cost_norm": "linfty",
    "matrix_metric": "absolute_entrywise|relative_entrywise",
    "matrix_norm": "linfty_entrywise"
  },
  "calibration": {
    "lambda_star": "number",
    "u_potential": "array[number]"
  },
  "tight_core": {
    "tight_edges": "array[edge_id]",
    "tight_gap_gamma": "number",
    "tight_lipschitz_Kc": "number",
    "eps_tight": "number",
    "tight_graph_hash": "string_or_null"
  },
  "doeblin": {
    "word": "array[template_id]",
    "L": "integer",
    "M_bound": "number",
    "U_bound": "number",
    "delta": "number",
    "eps_doeblin": "number",
    "delta_prime_formula": "string",
    "U_prime_formula": "string"
  },
  "recurrence": {
    "mode": "combinatorial|hypothesis",
    "eps_recurrence": "number",
    "details": "object"
  },
  "rate_pack": {
    "projective_diameter_bound": "number",
    "tau_unperturbed": "number",
    "tau_prime_formula": "string",
    "eps_rate": "number",
    "kappa_prime_formula": "string"
  },
  "eps_star": {
    "eps_c_star": "number",
    "eps_A_star": "number"
  }
}
\end{verbatim}

\begin{remark}\label{rem:robustness-spine}
Every later statement of the form ``the conclusion survives perturbation'' must cite:
a margin field, the chosen perturbation metric, an explicit computed threshold, and the degraded constants produced
when $\varepsilon\le\varepsilon^\star$.
No other robustness language is permitted.
\end{remark}
