% syndetic_recurrence_tools.tex
% Finite recurrence tools: avoidance graph and syndetic return modulus for a fixed Doeblin word.

\section{Syndetic return to a certified Doeblin word via an avoidance graph}
\label{sec:syndetic-recurrence}

Fix a tight SCC $H$ and a word $w=e_1\cdots e_m$ on the edges of $H$.
This section formalizes a finite, checkable recurrence condition for $w$.
The outcome is dichotomous:
\begin{itemize}
\item either the avoidance dynamics contains a directed cycle, yielding an explicit witness that $w$ can be avoided for arbitrarily long times,
\item or the avoidance dynamics is acyclic, in which case $w$ must occur with bounded gaps along every infinite trajectory in $H$.
\end{itemize}
The second case is the concrete recurrence input (RC1) used in the gap-free contraction statements.

\begin{definition}[Finite recurrence input (RC1)]\label{def:rc1}
Let $H$ be a tight SCC and let $w$ be an edge word in $H$.
We say that $(H,w)$ satisfies \textbf{(RC1)} if the avoidance graph $\mathsf{A}(H,w)$ (Definition~\ref{def:avoidance-graph}) is acyclic.
In this case Algorithm~\ref{alg:syndetic} returns a finite modulus $L_{\mathrm{syn}}(H,w)$ such that every edge word of length $L_{\mathrm{syn}}(H,w)$ in $H$ contains an occurrence of $w$.
For notational compatibility with later sections, we also write $\mathcal{A}_{\neg w}(H):=\mathsf{A}(H,w)$.
\end{definition}


\subsection{Prefix automaton for a fixed word}
\label{subsec:prefix-automaton}

Let $m:=|w|$.
For a finite edge word $a=e'_1\cdots e'_k$ in $H$, define $\pi(a)\in\{0,1,\dots,m-1\}$ to be the length of the longest suffix of $a$ which is a proper prefix of $w$.
Equivalently, $\pi(a)=q$ means that the last $q$ edges of $a$ match $e_1\cdots e_q$, but $a$ does not yet contain a full occurrence of $w$ ending at the last edge.

Given $q\in\{0,\dots,m-1\}$ and an edge $e$ of $H$, define the update $\mathrm{next}(q,e)\in\{0,\dots,m\}$ to be the new matched-prefix length after appending $e$.
If $\mathrm{next}(q,e)=m$, then $w$ occurs ending at that step.
Otherwise $\mathrm{next}(q,e)\in\{0,\dots,m-1\}$.
This is the standard prefix automaton update (KMP-type) for a fixed pattern.

\subsection{Avoidance graph}
\label{subsec:avoidance-graph}

\begin{definition}[Avoidance graph]
\label{def:avoidance-graph}
Let $\mathsf{A}(H,w)$ be the directed graph on vertex set
\[
\{0,1,\dots,m-1\}\times V(H).
\]
There is a directed edge
\[
(q,x)\to(q',y)
\]
in $\mathsf{A}(H,w)$ if and only if there exists an edge $e:x\to y$ of $H$ such that $\mathrm{next}(q,e)=q'\in\{0,\dots,m-1\}$.
In other words, $\mathsf{A}(H,w)$ encodes the evolution of the matched-prefix state along paths in $H$ under the constraint that no step completes an occurrence of $w$.
\end{definition}

\begin{lemma}[Avoidance-cycle witness]
\label{lem:avoidance-cycle-witness}
If $\mathsf{A}(H,w)$ contains a directed cycle, then there exists an infinite trajectory in $H$ which avoids $w$ forever.
Consequently, no bound on gaps between occurrences of $w$ can hold uniformly over all infinite trajectories in $H$.
\end{lemma}

\begin{proof}
A directed cycle in $\mathsf{A}(H,w)$ corresponds to a nonempty edge word in $H$ which returns to the same matched-prefix state without ever completing $w$.
Repeating this cycle yields an infinite path in $H$ for which the prefix-state never reaches $m$, hence $w$ never occurs.
\end{proof}

\begin{lemma}[Syndetic modulus from acyclicity]
\label{lem:avoidance-syndetic}
If $\mathsf{A}(H,w)$ is acyclic, then there exists a finite integer $L_{\mathrm{syn}}(H,w)$ such that every length-$L_{\mathrm{syn}}(H,w)$ edge word in $H$ contains an occurrence of $w$.
In particular, every infinite trajectory in $H$ contains occurrences of $w$ with gaps at most $L_{\mathrm{syn}}(H,w)$.
\end{lemma}

\begin{proof}
If $\mathsf{A}(H,w)$ is acyclic, it has finite longest directed path length.
Along any edge word in $H$ that avoids $w$, the corresponding lifted path in $\mathsf{A}(H,w)$ never hits an accepting step ($\mathrm{next}=m$), so it remains a directed path in the avoidance graph.
Therefore any $w$-avoiding word has length at most the longest path length of $\mathsf{A}(H,w)$.
Taking $L_{\mathrm{syn}}(H,w)$ to be one plus that maximal length forces every longer word to contain $w$.
\end{proof}


\begin{corollary}[Explicit recurrence bound from automaton size]
\label{cor:Ls_size_bound}
If $\mathsf{A}(H,w)$ is acyclic and has $N$ vertices, then one may take
\[
L_{\mathrm{syn}}(H,w)\le N.
\]
In particular, since $N = m\,|V(H)|$, the bounded-gap modulus can be chosen at most $m\,|V(H)|$.
\end{corollary}

\begin{proof}
An acyclic directed graph on $N$ vertices has no directed path longer than $N-1$ edges, so $\ell_{\max}\le N-1$ in Algorithm~\ref{alg:syndetic}. Hence $L_{\mathrm{syn}}=\ell_{\max}+1\le N$.
\end{proof}

\begin{algorithm}[H]
\caption{Syndetic return check and modulus computation}\label{alg:syndetic}
\begin{algorithmic}[1]
\Require Tight SCC $H$, word $w$ on edges of $H$ of length $m$
\Ensure Either an avoidance-cycle witness, or a syndetic modulus $L_{\mathrm{syn}}(H,w)$
\State Build the avoidance graph $\mathsf{A}(H,w)$ (Definition~\ref{def:avoidance-graph})
\If{$\mathsf{A}(H,w)$ contains a directed cycle}
  \State Extract a directed cycle as a witness and \Return avoidance-cycle witness
\Else
  \State Compute the length $\ell_{\max}$ of a longest directed path in $\mathsf{A}(H,w)$ (DP on a topological ordering)
  \State \Return $L_{\mathrm{syn}}(H,w)\gets \ell_{\max}+1$
\EndIf
\end{algorithmic}
\end{algorithm}
