
% canonical_normalization.tex
\section{Canonical Normalization and the Tight Subgraph}\label{sec:core-truth}

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 \emph{tight} transitions). Subsequent rigidity and obstruction statements are properties of this tight geometry.

\subsection{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
\[
\lambda_* := \min_{\gamma\ \text{cycle}} \frac{1}{|\gamma|}\sum_{e\in\gamma} c(e).
\]

\begin{theorem}[Canonical normalization by a potential]\label{thm:canonical-normalization}
There exists a function (potential) $\phi:V\to\mathbb{R}$ such that the \emph{reduced costs}
\[
c_\phi(e):=c(e)-\lambda_*+\phi(\mathrm{tail}(e))-\phi(\mathrm{head}(e))
\]
satisfy $c_\phi(e)\ge 0$ for all $e\in E$.
\end{theorem}

\begin{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$.
\end{proof}

\subsection{The tight subgraph}

\begin{definition}[Tight edges and tight subgraph]\label{def:tight}
Fix a potential $\phi$ as in Theorem \ref{thm:canonical-normalization}.
Define the tight edges
\[
E^{(0)} := \{e\in E:\ c_\phi(e)=0\},
\qquad
G^{(0)} := (V^{(0)},E^{(0)}),
\]
where $V^{(0)}$ are vertices incident to $E^{(0)}$.
\end{definition}

\subsection{Period and aperiodicity of a tight SCC}

\begin{definition}[Period of a strongly connected digraph]\label{def:period}
Let $H$ be a strongly connected directed graph. Its \emph{period} is
\[
\mathrm{per}(H):=\gcd\{\,|\gamma| : \gamma\text{ is a directed cycle in }H\,\}.
\]
We call $H$ \emph{aperiodic} if $\mathrm{per}(H)=1$, and \emph{imprimitive} otherwise.
\end{definition}

\subsection{Minimizers are asymptotically tight}

A (one-sided) path $\pi=(e_0,e_1,\dots)$ has length-$n$ average cost
\[
\mathrm{Avg}_n(\pi) := \frac{1}{n}\sum_{t=0}^{n-1} c(e_t).
\]
We call $\pi$ \emph{minimizing} if $\liminf_{n\to\infty}\mathrm{Avg}_n(\pi)=\lambda_*$.

\begin{proposition}[Asymptotic tightness of minimizing paths]\label{prop:asymptotic-tight}
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$.
\end{proposition}

\begin{proof}
Because $E$ is finite and $c_\phi(e)\ge 0$, define
\[
\alpha := \min\{c_\phi(e): e\in E\setminus E^{(0)}\},
\]
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
\begin{align*}
\sum_{t=0}^{n-1} c_\phi(e_t)
&= \sum_{t=0}^{n-1}\big(c(e_t)-\lambda_*\big) + \phi(v_0)-\phi(v_n),
\end{align*}
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$.
\end{proof}

\subsection{A tight-core dichotomy}

For a subset $A\subseteq\mathbb{N}$, write its \emph{lower asymptotic density} as
\[
\underline d(A):=\liminf_{n\to\infty}\frac{|A\cap\{0,1,\dots,n-1\}|}{n}.
\]

\begin{proposition}[Tight-core dichotomy]\label{prop:tight-dichotomy}
Let $\pi$ be a minimizing path and let $T:=\{t\ge 0:\ e_t\in E^{(0)}\}$ be its set of tight times.
For each SCC $H$ of the tight graph $G^{(0)}$, set
\[
T_H:=\{t\in T:\ v_t\in H\},
\]
where $v_t$ is the tail vertex of $e_t$.
Then there exists at least one SCC $H$ with $\underline d(T_H)>0$.
Moreover, exactly one of the following holds:
\begin{itemize}
\item[(P)] every SCC $H$ with $\underline d(T_H)>0$ is imprimitive, i.e.\ $\mathrm{per}(H)>1$ (Definition~\ref{def:period});
\item[(A)] there exists an aperiodic SCC $H$ of $G^{(0)}$ with $\underline d(T_H)>0$, i.e.\ $\mathrm{per}(H)=1$.
\end{itemize}
\end{proposition}

\begin{proof}
Let $T:=\{t\ge 0:\ e_t\in E^{(0)}\}$ be the set of \emph{tight times} along $\pi$.
By Proposition~\ref{prop:asymptotic-tight}, $T$ has asymptotic density $1$, hence lower density $1$.
For each strongly connected component $H$ of the tight graph $G^{(0)}$, set
\[
T_H:=\{t\in T:\ \text{the time-$t$ vertex $v_t$ lies in }H\}.
\]
The sets $(T_H)_H$ form a \emph{finite} partition of $T$ indexed by the SCCs of $G^{(0)}$.
If every $T_H$ had lower density $0$, then their finite union $T$ would also have lower density $0$, contradicting $\underline d(T)=1$.
Therefore there exists at least one SCC $H$ with $\underline d(T_H)>0$.

If among the SCCs with $\underline d(T_H)>0$ there is an aperiodic one, we are in case (A).
Otherwise every SCC visited with positive lower density along tight times is imprimitive, which is case (P).
\end{proof}


\begin{remark}\label{rem:core-truth-bridge}
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.
\end{remark}
