\section{Detecting orbits of paths}\label{pathsec}

If $H_r$ is an exponential stratum and $\rho$ is a path of height $r$,
we let $\iota_r(\rho)$ equal the number of $r$-illegal turns in $\rho$.

\begin{lem}\label{detectnielsen}
Let $f\co G\rightarrow G$ be an efficient relative train track map.  If
$\rho$ is a circuit or edge path in $G$, then we can determine
algorithmically whether $\rho$ is a periodic Nielsen path; if $\rho$ is
Nielsen, then we can compute its period as well.
\end{lem}

\begin{proof}
Assume inductively that we can detect periodic Nielsen paths and
circuits in $G_{r-1}$.  We want to show that if $\rho$ is of height $r$,
then we can determine whether $\rho$ is Nielsen.

We first assume that $H_r=\{E_r\}$ is nonexponential.  Then $\rho$
splits as a concatenation of basic paths of height $r$ and paths in
$G_{r-1}$ (\lemref{pgsplit}), and it is Nielsen if and only if each of
these constituent paths is Nielsen.  Hence, we may assume that $\rho$ is
a basic path of height $r$, i.e., $\rho=E_r\gamma$ or
$\rho=E_r\gamma\bar{E}_r$ for some $\gamma\in G_{r-1}$.  If $E_rf=E_r$,
then $\rho$ is Nielsen if and only if $\gamma$ is Nielsen so that we are
done by induction.  If $E_r$ is neither constant nor linear, then
\lemref{attrlem} yields that $\rho$ cannot be Nielsen.

This leaves the case that $E_r$ is linear.  If $\rho=E_r\gamma$, then it
cannot be Nielsen (if $E_r\gamma$ were Nielsen, then \lemref{periodicpt}
would imply that we can slide $E_r$ to a constant edge, in violation of
efficiency of $f$).  Clearly, a path of the form $E_r\gamma\bar{E}_r$
can only be Nielsen if $\gamma$ is a (possibly negative) power of $u_r$,
which completes the proof for nonexponential $H_r$.

Now, assume that $H_r$ is exponential.  If an endpoint of $\rho$ is not
fixed, then $\rho$ cannot be Nielsen.  If both endpoints of $\rho$ are
fixed, we compute $\rho, \rho f, \rho f^2, \ldots$ until one of the
following three cases occurs:
\begin{itemize}
\item We encounter some image $\rho f^k$ that contains an $r$-legal path
whose length exceeds $2C_f$.  Then \lemref{critlen} implies that $\rho$
is not Nielsen.
\item We encounter some image $\rho f^k$ that contains fewer $r$-illegal
turns than $\rho$.  Since $f$ does not increase the number of
$r$-illegal turns, $\rho$ is not Nielsen.
\item We can express $\rho$ as
$\rho=\alpha_1\beta_1\alpha_2\beta_2\cdots\alpha_m\beta_m$, where the
$\alpha_i$ are Nielsen paths of height $r$, and the $\beta_i$ are
subpaths in $G_{r-1}$, such that we encounter some $\rho
f^k=\alpha_1(\beta_1 f^k)\cdots  \alpha_m(\beta_m f^k)$.  In this case,
$\rho$ is Nielsen if and only if the $\beta_i$ are Nielsen.
\end{itemize}

One of these three cases must occur eventually, and we can detect the
third case in a brute-force way by checking all possible decompositions
of $\rho$.

Finally, if $H_r$ is a zero stratum, then $\rho$ cannot possibly be
Nielsen, so that the proof is complete.
\end{proof}

If $u$ is a closed path and $\rho$ is an arbitrary edge path, we let
$p_u(\rho)$ equal the largest exponent $m$ so that $u^m$ is a prefix of
$\rho$.

\begin{lem}\label{nielsengrowth}
Let $f\co G\rightarrow G$ be a relative train track map with an
exponential stratum $H_r$ and a closed Nielsen path $u$ of height $r$.
If $\rho$ is an edge path of height $r$ and $k\geq 0$ an exponent such
that $p_u(\rho)=m$ and $p_u(\rho f^k)=l$, then $\iota_r(\rho)\geq
(2m-l-1)\iota_r(u)$.
\end{lem}

\begin{proof}
We express $\rho$ as $\rho=u^m\gamma$.  Since we have $p_u(\rho f^k)=l$,
we conclude that $p_{\bar u}(\gamma f^k)\geq m-l-1$, so that
$\iota_r(\gamma f^k)\geq (m-l-1)\iota_r(u)$.  Since $f$ does not
introduce new illegal turns, we have $\iota_r(\gamma)\geq
(m-l-1)\iota_r(u)$, so that $\iota_r(\rho)\geq (2m-l-1)\iota_r(u)$.
\end{proof}

\begin{lem}\label{detectgrowth}
Let $f\co G\rightarrow G$ be an efficient train track map and let
$\rho$ be a non-Nielsen path whose endpoints are fixed.  Then for any
$L>0$, we can compute an exponent $k_0>0$ such that $|\rho f^k|>L$
and $|\rho f^{-k}|>L$ (if $\rho f^{-k}$ exists) for all $k\geq k_0$.
\end{lem}

\begin{proof}
We assume inductively that the lemma holds for the restriction of $f$ to
$G_{r-1}$.  We first assume that $H_r=\{E_r\}$ is a nonexponential
stratum.  Then $\rho$ splits as a concatenation of basic paths of height
$r$ and paths in $G_{r-1}$, so that we may assume that $\rho$ is a
non-Nielsen basic path of height $r$, i.e., $\rho=E_r\gamma\bar{E}_r$ or
$\rho=E_r\gamma$.

Assume that $E_r$ is neither constant nor linear.  Then we can find a
prefix $R$ of $R_r$ as well as a prefix $S$ of $S_r$ (see
\lemref{attrlem} and \lemref{replem}) of length greater than $L$ for
which $|Rf|>|R|+C_f$ and $|Sf^{-1}|>|S|+C_f$.  Now \lemref{attrlem},
\lemref{replem}, and \lemref{bcc} imply that we can find some exponent
$k_0$ such that $R$ is a prefix of $\rho f^k$ and $S$ is a prefix of
$\rho f^{-k}$ for all $k\geq k_0$.  We conclude that $|\rho f^{\pm
k}|>L$ for all $k\geq k_0$.

If $E_r$ is constant, then the inductive hypothesis applied to $\gamma$
completes the proof.  This leaves the case that $E_r$ is linear.  Let
$s$ be the height of $\gamma$.  If $s$ is smaller than the height of
$u_r$, we conclude that no copy of $u_r$ will cancel completely in $\rho
f^k$ for any $k>0$, so that we have $|\rho f^{\pm k}|>L$ for all $k>L$.

If $s$ equals the height of $u_r$ and $H_s$ is nonexponential, then no
more than $|\gamma|$ copies of $u_r$ cancel in $|\rho f^k|$, so that we
have $|\rho f^{\pm k}|>L$ for all $k>L+|\gamma|$.  If $H_s$ is
exponential, then for all $k\geq 0$, the number of copies of $u_r$ that
cancel in $\rho f^k$ is bounded by $\iota_s(\gamma)$, so that $|\rho
f^k|>L$ if $k>L+\iota_s(\gamma)$.

We still need to study the length of $\rho f^{-k}$ for $k\geq 0$.  Let
$m=p_{u_r}(\gamma f^{-k})$ and $l=p_{u_r}(\gamma)$.  Then
\lemref{nielsengrowth} implies that $\iota_r(\gamma f^{-k})\geq
(2m-l-1)\iota_r(u_r)$.  This implies that $\iota_r(\rho f^{-k})\geq
k\iota_r(\bar{u}_r)+(2m-l-1)\iota_r(u_r)-2m\iota_r(u_r)=(k-l-1)\iota_r(u_r)$,
so that $|\rho f^{-k}|>L$ if $k>L+l+1$.

If $s$ exceeds the height of $u_r$, then, by definition of efficiency,
$H_s$ is also linear, and $\rho$ splits into subpaths of the form
$E_r\eta$, $E_s\eta$,  and $E_r\eta\bar{E}_s$, where $\eta\subset
G_{s-1}$.  The first two cases are done by induction on $s$, so that we
only need to consider the case $E_r\eta\bar{E}_s$.  This case is
essentially the same as the previous one (we need to apply
\lemref{nielsengrowth} to both $\eta$ and $\bar{\eta}$), except we need
to consider the possibility that there is a closed Nielsen path $\tau$
such that $u_r=\tau^a$, $u_s=\tau^b$, and $\eta=\tau^c$.  In this case,
we have $a\neq b$ (or else $E_r\bar{E}_s$ would be Nielsen, in violation
of efficiency), so that $|(E_r\eta\bar{E}_s)f^k|\geq k-c$, so that
$|(E_r\eta\bar{E}_s)f^k|>L$ if $k>L+c$.

Finally, assume that $H_r$ is exponential.  In this case, we compute
$\rho, \rho f, \ldots$ until we either find some $k_0$ such that $\rho
f^{k_0}$ has an $r$-legal subpath of $r$-length greater than $L+2C_f$
(in which case \lemref{critlen} yields that $|\rho f^k|>L$ for all
$k\geq k_0$), or, by \lemref{tricho}, we encounter some $k$ such that
$\rho f^k$ is a composition of indivisible Nielsen paths of height $r$
and paths in $G_{r-1}$.  Since $\rho$ is non-Nielsen, one of the
subpaths in $G_{r-1}$ must be non-Nielsen, so that we are done by
induction.

In order to understand lengths under backward iteration, we need to
consider two cases:  If $\rho$ is not a composition of indivisible
Nielsen paths of height $r$ and paths in $G_{r-1}$, then
\lemref{tricho} implies that the number of $r$-illegal turns has to go
up under backward iteration.  In this case, we simply compute $\rho
f^{-1}$, $\rho f^{-2}, \ldots$ until we find some $k_0$ for which $\rho
f^{-k_0}$ contains $L$ $r$-illegal turns, and we conclude that $|\rho
f^{-k}|>L$ for all $k\geq k_0$.

If $\rho$ is a concatenation of indivisible Nielsen paths of height $r$
and paths in $G_{r-1}$, then one of the subpaths $\gamma$ in $G_{r-1}$
is not Nielsen, so that the inductive hypothesis applies to $\gamma$.
\lemref{fppreim} guarantees that $\gamma f^{-k}$ exists for all $k\geq
0$, so that we are done.
\end{proof}

\begin{prop}\label{detectpathorbits}
Let $f\co G\rightarrow G$ be an efficient train track map, and let
$\rho_1$ and $\rho_2$ be paths whose endpoints are fixed.  Then we can
determine algorithmically whether $\rho_2$ is the image of $\rho_1$
under some power of $f^k$, and we can compute the exponent $k$ if it
exists.
\end{prop}

\begin{proof}
Using \lemref{detectnielsen}, we determine whether $\rho_1$ is a
periodic Nielsen path.  If it is, we simply enumerate all distinct images
of $\rho_1$ and check whether $\rho_2$ is among them.  If $\rho_1$ is
not Nielsen, we apply \lemref{detectgrowth} with $L=|\rho_2|$ to obtain
an exponent $k_0$.  Now we compute $\rho, \rho f, \ldots, \rho_1f^{k_0}$
and check whether $\rho_2$ is contained in this list.

If $\rho_2$ is contained in this list, we obtain a positive answer as
well as the desired exponent $k$.  If not, we switch $\rho_1$ and
$\rho_2$ and repeat the argument.
\end{proof}

\begin{thm}\label{computenielsen}
Let $f\co G\rightarrow G$ be an efficient train track map with an
exponential stratum $H_r$.  Then we can compute all indivisible periodic
Nielsen paths of height $r$ as well as their periods.
\end{thm}

\begin{proof}
Let $\alpha$ be an indivisible Nielsen path of height $r$.  Then
$\alpha$ contains exactly one $r$-illegal turn, and the $r$-length of
its two $r$-legal subpaths is bounded by $C_f$ (\lemref{bcc}).
Moreover, the first and last (possibly partial) edges of $\alpha$ are
contained in $H_r$.

For an edge $E$ in $H_r$, let $P_E$ be the set of maximal subpaths in
$G_{r-1}$ of $Ef$, and let $P=\cup_{E\in H_r} P_E$.  If $\beta$ is a
maximal subpath in $G_{r-1}$ of $\alpha$, then there exists some
$\gamma\in P$ and $k\geq 0$ such that $\beta=\gamma f^k$.

Let $\gamma$ be a path in $P$.  If $\gamma$ is Nielsen, we let
$L_\gamma=\max_{k} \{|\gamma f^k|\}$.  If $\gamma$ is not Nielsen,
\lemref{detectgrowth} with $L=C_f$ yields an exponent $k_0$ such that
$|\rho f^k|>L$ for all $k\geq k_0$.  We let $L_\gamma=\max_{0\leq k<k_0}
\{|\rho f^k|\}$.

Let $M=\max_{\gamma\in P} \{L_\gamma\}$ and observe that $\alpha$ has no
subpaths in $G_{r-1}$ whose length exceeds $M$.  Let $Q$ be the set of
all edge paths $\rho$ such that $\rho$ contains exactly one $r$-illegal
turn, the $r$-length of $r$-legal subpaths is bounded by $C_f$, the
length of subpaths in $G_{r-1}$ is bounded by $M$, and the first and
last edges are contained in $H_r$.  Clearly, if $\alpha$ is an
indivisible Nielsen path of height $r$, then $\alpha$ is a subpath of
some $\rho\in Q$.

We define a map $g\co Q\rightarrow G\cup \{\ast\}$\footnote{$\ast$ is
merely some termination symbol.} by letting $\rho g$ equal the unique
maximal subpath of $\rho f$ contained in $Q$ if $\rho f$ contains an
$r$-illegal turn, and we let $\rho g=\ast$ if $\rho f$ contains no
$r$-illegal turn.

For each $\rho\in G$, we compute $\rho, \rho g, \rho g^2, \ldots$ until
we either encounter $\ast$ (in which case $\rho$ has no Nielsen subpath)
or we find that $\rho g^k=\rho g^m$ for some $0\leq k<m$.  Then $\rho
g^k$ contains an indivisible Nielsen subpath $\alpha$, and we can easily
compute the endpoints of $\alpha$.  Moreover, if $k$ and $m$ are as
small as possible, then $m-k$ is the period of $\alpha$.  Since all
indivisible Nielsen paths of height $r$ show up in this fashion, the
proof is complete.
\end{proof}

\begin{cor}
Given an efficient relative train track map $f\co G\rightarrow G$, we
can compute an exponent $k\geq 1$ such that all periodic Nielsen paths of
$f^k$ have period one.
\end{cor}
{"config": "arxiv", "file": "0806.2889/paths.tex"}