
Proof.
Recall that the definition of
$\lambda (\phi ,\cdot {}_{x})$
does not depend on the choice of a point
$x\in X$
. Hence we may assume that
$x$
is a vertex of the minimal
$F$
invariant subtree of
$X$
and therefore, that the action of
$F$
on
$X$
is minimal. Let
$\Gamma =X/F$
be the finite quotient graph. Choose an orientation on
$\Gamma $
, a maximal tree
$T$
in
$\Gamma $
. Choose a basevertex
$p$
in
$\Gamma $
to be the image of
$x\in X$
in
$\Gamma $
. Note that in both
$X$
and
$\Gamma $
every edge has length
$1$
. Then there is a canonical isomorphism
$\psi :F\to {\pi}_{1}(\Gamma ,p)$
. Let
${S}_{T}$
and
${B}_{T}$
be the geometric bases corresponding to
$T$
for
${\pi}_{1}(\Gamma ,p)$
and
$F$
accordingly. Fix a bijection between ${B}_{T}$ and $A=\{{a}_{1},...,{a}_{k}\}$ and an automorphism $\alpha $ of $F$ induced by this bijection of the two free bases of $F$ .Let $g={x}_{1}...{x}_{n}\in F$ be a freely reduced word of length $n$ in $F({a}_{1},...,{a}_{k})$ . Let ${g}^{\prime}$ be a cyclically reduced word of length $n$ over $A$ obtained from $g$ by changing the last letter of $g$ if necessary. Thus ${g}^{\prime}{g}^{1}{}_{A}\le 2$ .Let ${w}^{\prime}$ be the cyclic word over $A$ defined by ${g}^{\prime}$ . Let $w$ be the result of rewriting ${w}^{\prime}$ as the cyclic word in ${B}_{T}$ . Then there is an integer $M\ge 1$ such that for each freely reduced word $z$ in ${B}_{T}$ of length at most $2$ $${n}_{w}\left(z\right)={\sum}_{u{}_{A}=M}c(u,z){n}_{w}\left(u\right)$$ where $c(u,z)\ge 0$ are some integers independent of $w$ . Let ${Z}_{i}$ be the set of freely reduced words of length $i$ in ${B}_{T}$ , for $i=1,2$ . Then$$\left\right{g}^{\prime}{}_{X}=\leftw\right{}_{X}={\sum}_{a\in {Z}_{1}}\ell \left(e\right(a\left)\right){n}_{w}\left(a\right)+{\sum}_{z\in {Z}_{2}}{r}_{z}{n}_{w}\left(z\right)={\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}\ell \left(a\right)c(u,a){n}_{{w}^{\prime}}\left(u\right)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z){n}_{{w}^{\prime}}\left(u\right),$$It follows from Lemma 4.1 and Lemma 4.2 that if $h\in F$ is cyclically reduced over ${B}_{T}$ then $\left\right\lefth\right{}_{X}\lefth{}_{x}\right\le N$ where $N=N\left(x\right)>0$ is some constant independent of $h$ . On the other hand by the Bounded Cancellation Lemma ( Lemma 3.7 ) there exists a constant ${N}^{\prime}>0$ such that for any cyclically reduced word $y$ over $A$ , we have $\left\right\lefty\right{}_{{B}_{T}}\lefty{}_{{B}_{T}}\right\le {N}^{\prime}$ . By construction ${g}^{\prime}$ is cyclically reduced over $A$ and ${g}^{\prime}{g}^{1}{}_{A}\le 2$ . Hence there exists a constant $L>0$ such that for every $g$ as above and each $u\in F$ with $u{}_{A}=M$ we have $\left\rightg{}_{x}\left\right{g}^{\prime}\left{}_{X}\right\le L$ and $\left{n}_{g}\right(u){n}_{{w}^{\prime}}(u\left)\right\le L$ .Therefore there is another constant ${L}^{\prime}>0$ independent of $f$ such that for every freely reduced word $g$ of length $n$ over $A$ $$\left{\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}\ell \left(e\right(a\left)\right)c(u,a){f}_{g}\left(u\right)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z){f}_{g}\left(u\right)\frac{g{}_{p}}{n}\right\le \frac{{L}^{\prime}}{n}.$$ If ${g}_{n}$ is a freely reduced word of length $n$ obtained by a nonbacktracking simple random walk of length $n$ on $F({a}_{1},...,{a}_{k})$ then for each $u\in F({a}_{1},...,{a}_{k})$ with $u{}_{A}=M$ we have $${lim}_{n\to \infty}{f}_{{g}_{n}}\left(u\right)=\frac{1}{2k(2k1{)}^{M1}}\text{almost surely.}$$ Therefore (*) implies that $$\lambda \left(\phi \right)=\frac{1}{2k(2k1{)}^{M1}}\left[{\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}\ell \left(e\right(a\left)\right)c(u,a)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z)\right]$$ Since $\ell \left(e\right(a\left)\right)=1,c(u,a),c(u,z)$ and ${r}_{z}$ are integers, it follows that $\lambda \left(\phi \right)$ is rational and, moreover, that $$2k\lambda \left(\phi \right)\in \mathbb{Z}\left[\frac{1}{2k1}\right].$$ Moreover, $\lambda \left(\phi \right)$ is computable in terms of an explicit isomorphism between $F$ and ${\pi}_{1}(\Gamma ,p)$ . □
Remark 4.4.
The formula (**) for
$\lambda \left(\phi \right)$
holds for an arbitrary structure of a metric graph on
$\Gamma $
, where the lengths of edges are allowed to be arbitrary positive real numbers and not necessarily
$1$
. If the length of all edges of
$\Gamma $
are rational, then by (**)
$\lambda \left(\phi \right)$
is also rational. Moreover, if these length of the edges are given to us in some algorithmically describable form then
$\lambda \left(\phi \right)$
is computable in terms of these lengths and of an an explicit isomorphism between
$F$
and
${\pi}_{1}(\Gamma ,p)$
.
5 Genericity
Convention 5.1.
Recall that
$\mathcal{C}\mathcal{\mathcal{R}}$
denotes the set of all cyclically reduced words in
$F=F({a}_{1},...,{a}_{k})$
. If
$S\subseteq F$
and
$n\ge 0$
we denote
$$\rho (S,n):=\#\{w\in S:w\le n\},$$
and
$$\gamma (S,n):=\#\{w\in S:w=n\},$$
Let
${P}_{n}$
be the uniform discrete probability measure on the set of all elements
$w\in F$
with
$\leftw\right=n$
. We extend
${P}_{n}$
to
$F$
by setting
${P}_{n}\left(w\right)=0$
for any
$w\in F$
with
$\leftw\right\ne n$
.
Similarly, let
${P}_{n}^{\prime}$
be the uniform discrete probability measure on the set of all cyclically reduced elements
$w\in F$
with
$\left\rightw\left\right=n$
. We extend
${P}_{n}$
to
$\mathcal{C}\mathcal{\mathcal{R}}$
by setting
${P}_{n}^{\prime}\left(w\right)=0$
for any
$w\in \mathcal{C}\mathcal{\mathcal{R}}$
with
$\left\rightw\left\right\ne n$
.
Thus
$\gamma (n,F)=2k(2k1{)}^{n1}$
for
$n>0$
.
For a number sequence
${x}_{n}$
with
${lim}_{n\to \infty}{x}_{n}=x\in \mathbb{R}$
we say that the convergence is exponentially fast if there exist
$0<\sigma <1$
and
$D>0$
such that for all
$n\ge 1$
we have
${x}_{n}x\le D{\sigma}^{n}$
.
Definition 5.2 (Genericity).
Let
$S\subseteq \mathcal{W}\subseteq F$
. We say that
$S$
is exponentially
$\mathcal{W}$
generic if
$${lim}_{n\to \infty}\frac{\gamma (n,S)}{\gamma (n,\mathcal{W})}=1$$
and the convergence is exponentially fast. The complement in
$\mathcal{W}$
of an exponentially
$\mathcal{W}$
generic set is called exponentially
$\mathcal{W}$
negligible.
In practice we are only interested in the cases
$\mathcal{W}=F$
and
$\mathcal{W}=\mathcal{C}\mathcal{\mathcal{R}}$
, the set of all cyclically reduced words in
$F$
. By definition
$S\subseteq F$
is exponentially
$F$
generic if and only if
${lim}_{n\to \infty}{P}_{n}\left(S\right)=1$
with exponentially fast convergence in this limit. Similarly
$S\subseteq \mathcal{C}\mathcal{\mathcal{R}}$
is exponentially
$\mathcal{C}\mathcal{\mathcal{R}}$
generic iff
${lim}_{n\to \infty}{P}_{n}^{\prime}\left(S\right)=1$
with exponentially fast convergence. Here there is a simple criterion of being exponentially negligible [35] in
$F$
and
$\mathcal{C}\mathcal{\mathcal{R}}$
:
It is not hard to deduce the following from Proposition 5.4 .
Lemma 5.3.
Let
$\mathcal{W}=F$
or
$\mathcal{W}=\mathcal{C}\mathcal{\mathcal{R}}$
. Then for a subset
$S\subseteq \mathcal{W}$
the following are equivalent:
 (1) The set $S$ is exponentially $\mathcal{W}$ negligible.
 (2) We have $$\frac{\gamma (n,S)}{(2k1{)}^{n}}{\to}_{n\to \infty}0\text{exponentially fast,}$$
 (3) We have $$\frac{\rho (n,S)}{(2k1{)}^{n}}{\to}_{n\to \infty}0\text{exponentially fast,}$$
 (4) We have $${limsup}_{n\to \infty}\sqrt[n]{\rho (n,S)}<2k1.$$
 (5) We have $${limsup}_{n\to \infty}\sqrt[n]{\gamma (n,S)}<2k1.$$
Proposition 5.4.
Let
$\epsilon >0$
and let
$m>0$
be an integer. Then the set
is exponentially
$F$
generic.
$$\begin{array}{cc}W(m,\epsilon ):=\{& w\in F:\text{for any}u\ne 1\text{with}\leftu\right=m\text{we have}\end{array}$$ 
$$\begin{array}{cc}& \left{f}_{w}\right(u)\frac{1}{2k(2k1{)}^{m1}}<\epsilon \}\end{array}$$ 
$$\begin{array}{}\end{array}$$ 
Proposition 5.5.
Let
$\epsilon >0$
and let
$m>0$
be an integer. Then the set
is exponentially
$\mathcal{C}\mathcal{\mathcal{R}}$
generic.
We now give the definition of an “approximate” stretching factor, which will later be seen to be equivalent to the generic stretching factor of an automorphism introduced earlier.$$\begin{array}{cc}C(m,\epsilon ):=\{& w\in \mathcal{C}\mathcal{\mathcal{R}}:\text{for any}u\ne 1\text{with}\leftu\right=m\text{and for the cyclic word}\left(w\right)\end{array}$$ 
$$\begin{array}{cc}& \text{we have}\left{f}_{\left(w\right)}\right(u)\frac{1}{2k(2k1{)}^{m1}}<\epsilon \}\end{array}$$ 
$$\begin{array}{}\end{array}$$ 
Definition 5.6.
Let
$\phi :F\to Aut\left(X\right)$
be a free simplicial action without inversions of
$F=F({a}_{1},...,{a}_{k})$
on a simplicial tree
$X$
.
We say that a number
$\lambda \ge 0$
is a approximate stretching factor of
$\phi $
if for every
$p\in X$
and for any
$\epsilon >0$
the set
$$\{w\in F:\frac{w{}_{p}}{\leftw\right}\lambda \le \epsilon \}$$
is exponentially generic in
$F$
.
Similarly, we say that a number
$\lambda \ge 0$
is a approximate conjugacy stretching factor of
$\phi $
if for any
$\epsilon >0$
the set
$$\{w\in \mathcal{C}\mathcal{\mathcal{R}}:\frac{\left\rightw{}_{X}}{\left\rightw\left\right}\lambda \le \epsilon \}$$
is exponentially generic in
$\mathcal{C}\mathcal{\mathcal{R}}$
.
Proposition 5.7.
Let
$\phi :F\to Aut\left(X\right)$
be a free simplicial action of
$F=F({a}_{1},...,{a}_{k})$
on a simplicial tree
$X$
.
 (1) There is at most one approximate stretching factor for $\phi $ .
 (2) There is at most one approximate conjugacy stretching factor for $\phi $ .
 (3) If $\lambda $ is an approximate conjugacy stretching factor for $\phi $ then $\lambda $ is also an approximate stretching factor for $\phi $ .
 (4) If $\lambda $ is an approximate stretching factor for $\phi $ then $\lambda $ is also an approximate conjugacy stretching factor for $\phi $ .

Proof.
Parts (1) and (2) are obvious. We now establish (3). Indeed, suppose that $\lambda $ is an approximate conjugacy stretching factor for $\phi $ . Let $\epsilon >0$ and let $S$ be the set of all cyclically reduced words $w$ such that $\frac{\left\rightw{}_{X}}{\left\rightw\left\right}\lambda \ge \epsilon /2$ . Then $S$ is exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ negligible, so that $$\frac{\gamma (n,S)}{(2k1{)}^{n}}{\to}_{n\to \infty}0$$ exponentially fast. Let $p\in X$ . Put $M=max\left\{\right{a}_{i}{}_{p}:1\le i\le k\}$ . Let $N>0$ be an integer such that for any cyclically reduced word $u$ we have $\left\rightu{}_{p}\left\rightu\left{}_{X}\right\le N$ .Let ${S}^{\prime}$ be the set of all freely reduced words $w$ in $F$ that differ from an element of $S$ in at most the last letter. Then $\gamma (n,{S}^{\prime})\le 2k\gamma (n,S)$ and hence ${S}^{\prime}$ is exponentially $F$ negligible by Lemma 5.3 .Suppose $w\in F{S}^{\prime}$ is such that $\frac{N+2M}{\leftw\right}<\frac{\epsilon}{2}$ . Let $u$ be a cyclically reduced word obtained from $w$ by changing at most the last letter. Then $\leftu\right=\leftw\right$ and $u\in \mathcal{C}\mathcal{\mathcal{R}}S$ .Thus ${d}_{A}(w,u)\le 2$ and hence ${d}_{X}(wp,up)\le 2M$ . Thus $\left\rightu{}_{p}\leftw{}_{p}\right\le 2M$ . Also $\left\right\leftu\right{}_{X}\leftu{}_{p}\right\le N$ . Therefore $\left\right\leftu\right{}_{X}\leftw{}_{p}\right\le N+2M$ . Since $u\in \mathcal{C}\mathcal{\mathcal{R}}S$ , we have $\left\right\leftu\right{}_{X}\lambda \left\rightu\left\right<\epsilon \leftu\right$ . Since $\left\rightu\left\right=\leftu\right=\leftw\right$ , we have:$$\left\rightw{}_{p}\lambda \leftw\right<\epsilon w+N+2M\left\frac{w{}_{p}}{\leftw\right}\lambda \right<\frac{\epsilon}{2}+\frac{N+2M}{\leftw\right}<\epsilon .$$The set $\{w\in F:\frac{N+2M}{\leftw\right}\ge \frac{\epsilon}{2}\}$ is finite. Hence ${S}^{\prime}\cup \{w\in F:\frac{N+2M}{\leftw\right}\ge \frac{\epsilon}{2}\}$ is exponentially $F$ negligible and assertion (3) holds.The proof of (4) is similar to that of (3) and we leave the details to the reader. □
Theorem 5.8.
Let
$F=F({a}_{1},...,{a}_{k})$
and let
$\phi :F\to Aut\left(X\right)$
be a free simplicial action of
$F=F({a}_{1},...,{a}_{k})$
on a simplicial tree
$X$
.
Then the generic stretching factor
$\lambda \left(\phi \right)$
is also an approximate conjugacy stretching factor (and thus by Proposition 5.7 an approximate stretching factor).

Proof.
The proof is very similar to that of Theorem 4.3 . Since the minimal
$F$
invariant subtree of
$X$
contains the axes of all the nontrivial elements of
$F$
, we may again assume that the action of
$F$
on
$X$
is minimal. Choose a vertex $x\in X$ . Recall, that, using the notations from the proof of Theorem 4.3 , for any $w\in F$ $$\left{\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}c\right(u,a\left){f}_{w}\right(u)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z\left){f}_{w}\right(u)\frac{g{}_{p}}{n}\le \frac{{L}^{\prime}}{n}.$$ It follows from Lemma 4.1 and Lemma 4.2 that if $w\in F$ is cyclically reduced over ${B}_{T}$ then $\left\right\leftw\right{}_{X}\leftw{}_{x}\right\le N$ where $N=N\left(x\right)>0$ is some constant independent of $w$ . On the other hand by the Bounded Cancellation Lemma ( Lemma 3.7 ) there exists a constant ${N}^{\prime}>0$ such that for any cyclically reduced word $w$ over $A$ , we have $\left\right\leftw\right{}_{{B}_{T}}\leftw{}_{{B}_{T}}\right\le {N}^{\prime}$ . Hence for any cyclically reduced word $w$ over $A$ we have $\left\right\leftw\right{}_{X}\leftw{}_{x}\right\le {N}^{\prime \prime}$ where ${N}^{\prime \prime}={N}^{\prime \prime}\left(x\right)>0$ is some constant independent of $w$ .Therefore for any cyclically reduced $w\in F$ over $A$ with $\left\rightw\left\right=n$ $$\left{\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}c(u,a){f}_{w}\left(u\right)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z){f}_{w}\left(u\right)\frac{\left\rightw{}_{X}}{n}\right\le \frac{{L}^{\prime}+N}{n}.$$ Let $\epsilon >0$ We know that the set
$$\begin{array}{cc}C(M,\epsilon ):=\{& w\in \mathcal{C}\mathcal{\mathcal{R}}:\text{for any}u\ne 1\text{with}\leftu\right=M\text{and for the cyclic word}\left(w\right)\end{array}$$ $$\begin{array}{cc}& \text{we have}\left{f}_{\left(w\right)}\left(u\right)\frac{1}{2k(2k1{)}^{M1}}\right<\epsilon \}\end{array}$$ $$\begin{array}{}\end{array}$$ Hence (*) implies that for any $w\in C(M,\epsilon )$ $$\left\frac{1}{2k(2k1{)}^{M1}}\left({\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}c(u,a)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z)\right)\frac{\left\rightw{}_{X}}{n}\right\le \frac{{N}_{1}}{n}+{N}_{1}\epsilon .$$ for some constant ${N}_{1}>0$ independent of $w$ and $\epsilon $ .Thus by definition the number $$\frac{1}{2k(2k1{)}^{M1}}\left({\sum}_{a\in {Z}_{1}}{\sum}_{u{}_{A}=M}c(u,a)+{\sum}_{z\in {Z}_{2}}{\sum}_{u{}_{A}=M}{r}_{z}c(u,z)\right)$$ is an approximate conjugacy stretching factor for $\phi $ . In the proof of Theorem 4.3 we obtained the same formula for $\lambda \left(\phi \right)$ . □
Lemma 5.9.
Let
$F=F({a}_{1},...,{a}_{k})$
and let
$\phi :F\to Aut\left(X\right)$
be a free simplicial action of
$F=F({a}_{1},...,{a}_{k})$
on a simplicial tree
$X$
. Let
$\mu \ge 0$
.
Suppose there exists an exponentially
$\mathcal{C}\mathcal{\mathcal{R}}$
generic set
$S$
such that for any
$w\in S$
$$\frac{\left\rightw{}_{X}}{\left\rightw\left\right}\ge \mu .$$
Then
$\lambda \left(\phi \right)\ge \mu $
.

Proof.
Suppose, on the contrary, that
$\lambda \left(\phi \right)<\mu $
. Choose
$\epsilon >0$
such that
$\lambda \left(\phi \right)+\epsilon <\mu $
. Then there is an exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic set $R$ of cyclically reduced words such that for any $w\in R$ $$\frac{\left\rightw{}_{X}}{\left\rightw\left\right}\le \lambda +\epsilon .$$ The intersection $S\cap R$ is exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic and hence nonempty. Take $w\in S\cap R$ .Then $$\mu \le \frac{\left\rightw{}_{X}}{\left\rightw\left\right}\le \lambda +\epsilon <\mu ,$$ yielding a contradiction. □
6 Whitehead's Peak Reduction and rigidity of free group automorphisms
We need to recall some definitions related to Whitehead's algorithm for solving the automorphic equivalence problem in a free group. We refer the reader to [38, 43] for a detailed exposition.
Definition 6.1 (Whitehead automorphisms).
A Whitehead automorphism of
$F$
is an automorphism
$\tau $
of
$F$
of one of the following two types:
(1) There is a permutation
$t$
of
$\widehat{A}$
such that
$\tau {}_{\widehat{A}}=t$
. In this case
$\tau $
is called a relabeling automorphism or a Whitehead automorphism of the first kind.
(2) There is an element
$a\in \widehat{A}$
, the multiplier, such that for any
$x\in \widehat{A}$
$$\tau \left(x\right)\in \{x,xa,{a}^{1}x,{a}^{1}xa\}.$$
In this case we say that
$\tau $
is a Whitehead automorphism of the second kind. (Note that we always have
$\tau \left(a\right)=a$
in this case since
$\tau $
is an automorphism of
$F$
.) To every such
$\tau $
we associate a pair
$(S,a)$
where
$a$
is as above and
$S$
consists of all those elements of
$\widehat{A}$
, including
$a$
but excluding
${a}^{1}$
, such that
$\tau \left(x\right)\in \{xa,{a}^{1}xa\}$
. We will say that
$(S,a)$
is the characteristic pair of
$\tau $
.
Note that for any
$a\in \widehat{A}$
the inner automorphism
$ad\left(a\right)$
is a Whitehead automorphism of the second kind.
The following important result of Whitehead is known as the “peak reduction lemma”:
Proposition 6.2.
Let
$u,v$
be cyclic words with
$\left\rightu\left\right\le \left\rightv\left\right$
and let
$\phi \in Aut\left(F\right)$
be such that
$\phi \left(u\right)=v$
. Then we can write
$\phi $
as a product of Whitehead moves
$$\phi ={\tau}_{p}...{\tau}_{1}$$
so that for each
$i=1,...,p$
$$\left\right{\tau}_{i}...{\tau}_{1}\left(u\right)\left\right\le \left\rightv\left\right.$$
Moreover, if
$\left\rightu\left\right<\left\rightv\left\right$
then the above inequalities are strict for all
$i<p$
.
Definition 6.3 (Weighted Whitehead graph).
Let
$w$
be a nontrivial cyclically reduced word in
${\widehat{A}}^{*}$
. The weighted Whitehead graph
${\Gamma}_{w}$
of
$w$
is defined as follows. Let
$\left(w\right)$
be the cyclic word defined by
$w$
. The vertex set of
${\Gamma}_{w}$
is
$\widehat{A}$
. For every
$x,y\in \widehat{A}$
such that
$x\ne {y}^{1}$
there is an undirected edge in
${\Gamma}_{w}$
from
${x}^{1}$
to
$y$
labeled by the sum
${\hat{n}}_{w}\left(xy\right):={n}_{\left(w\right)}\left(xy\right)+{n}_{\left(w\right)}\left({y}^{1}{x}^{1}\right)$
.
There are
$k(2k1)$
undirected edges in
${\Gamma}_{w}$
. Edges may have label zero, but there are no edges from
$a$
to
$a$
for
$a\in \widehat{A}$
. It is easy to see that we have
${\Gamma}_{w}={\Gamma}_{v}$
for any cyclic permutation
$v$
of
$w$
or
${w}^{1}$
.
Convention 6.4.
Let
$w$
be a fixed nontrivial cyclically reduced word.
For two subsets
$X,Y\subseteq \widehat{A}$
we denote by
$X.Y$
the sum of all edgelabels in the weighted Whitehead graph
${\Gamma}_{w}$
of
$w$
of edges from elements of
$X$
to elements of
$Y$
. Thus for
$x\in \widehat{A}$
the number
$x.\widehat{A}$
is equal to
${n}_{w}\left(x\right)+{n}_{w}\left({x}^{1}\right)$
, the total number of occurrences of
${x}^{\pm 1}$
in
$w$
.
The next lemma, which is Proposition 4.16 of Ch. I in [38] , gives an explicit formula for the difference of the lengths of
$w$
and
$\tau \left(w\right)$
, where
$\tau $
is a Whitehead automorphism.
Lemma 6.5.
Let
$w$
be a nontrivial cyclically reduced word and let
$\tau $
be a Whitehead automorphism of the second kind with the characteristic pair
$(S,a)$
. Let
${S}^{\prime}=\widehat{A}S$
. Then
$$\left\right\tau \left(w\right)\left\right\left\rightw\left\right=S.{S}^{\prime}a.\widehat{A}.$$
The following important notion was introduced by Kapovich, Schupp and Shpilrain in [35] .
Definition 6.6 (Strict Minimality).
A nontrivial cyclically reduced word
$w$
in
$F$
is strictly minimal if for every noninner Whitehead automorphism
$\tau $
of
$F$
of the second kind we have
$$\left\right\tau \left(w\right)\left\right>\left\rightw\left\right.$$
The set of all strictly minimal elements in
$F$
is denoted
$SM$
.
An immediate consequence of the Peak Reduction Lemma is:
Proposition 6.7.
[35] Let
$w\in F$
be a cyclically reduced strictly minimal element. Then
$w$
is of minimal length in its
$Aut\left(F\right)$
orbit and for any
$\phi \in Aut\left(F\right)$
we have:
$$\leftw\right=\left\rightw\left\right\le \left\right\phi \left(w\right)\left\right\le \left\phi \right(w\left)\right.$$
Theorem 6.8.
Put
${c}_{0}:=1+\frac{2k3}{4{k}^{2}2k}$
. There exists an exponentially
$F$
generic set
$W\subseteq F$
with the following property.
For any
$\phi \in Aut\left(F\right)$
the following conditions are equivalent:
The following statement, together with Theorem 6.8 , implies Theorem F from the Introduction.
The following is Theorem G from the Introduction:

(1)
The automorphism
$\phi $
is simple.
 (2) We have $\lambda \left(\phi \right)=1.$
 (3) We have $\lambda \left(\phi \right)<1+\frac{2k3}{2{k}^{2}k}.$

(4)
For some
$w\in W$
we have
$\left\right\phi \left(w\right)\left\right=\left\rightw\left\right$
.

(5)
For every
$w\in W$
we have
$\left\right\phi \left(w\right)\left\right=\left\rightw\left\right$
.

(6)
For some
$w\in W$
we have
$\left\right\phi \left(w\right)\left\right\le {c}_{0}\left\rightw\left\right$
.
 (7) For every $w\in W$ we have $\left\right\phi \left(w\right)\left\right\le {c}_{0}\left\rightw\left\right$ .

Proof.
It is obvious that (1) implies (2) and that (2) implies (3). We will now prove that (3) implies (1).Let $\phi \in Aut\left(F\right)$ .Let $\epsilon >0$ be arbitrary. Put $T\left(\epsilon \right)$ be the set of all cyclically reduced words $w$ such that:
 $\bullet $ For any $x\in \widehat{A}$ $\left{f}_{w}\right(x)\frac{1}{2k}\le \epsilon /2$ .
 $\bullet $ For any $x,y\in \widehat{A}$ with $x\ne {y}^{1}$ $\left{f}_{w}\right(xy)\frac{1}{2k(2k1)}\le \epsilon /2$
By strict minimality of $w$ we have $\left\rightw\left\right\le \left\right\phi \left(w\right)\left\right$ . Moreover, by Proposition 6.2 (Peak Reduction Lemma) there is a decomposition $\phi ={\tau}_{p}{\tau}_{p1}...{\tau}_{1}$ such that each ${\tau}_{i}$ is a Whitehead move and for each $i=1,...,p1$ $$\left\right{\tau}_{i}{\tau}_{i1}...{\tau}_{1}\left(w\right)\left\right\le \left\right\phi \left(w\right)\left\right$$ with strict inequalities unless $\left\rightw\left\right=\left\right\phi \left(w\right)\left\right$ .Suppose first that $\left\rightw\left\right=\left\right\phi \left(w\right)\left\right$ . Then all inequalities above are equalities and by strict minimality of $w$ each ${\tau}_{i}$ is either inner or a relabeling automorphism. This implies that $\phi =\alpha \tau $ where $\alpha $ is inner and $\tau $ is a relabeling automorphism and that $\lambda \left(\phi \right)=1$ .Suppose now that $\left\rightw\left\right<\left\right\phi \left(w\right)\left\right$ . Then the preceding argument shows that in fact for any $z\in T\left(\epsilon \right)$ we have $\left\rightz\left\right<\left\right\phi \left(z\right)\left\right$ (since otherwise $\phi $ would be simple and so $\left\rightw\left\right=\left\right\phi \left(w\right)\left\right$ ).Denote ${z}_{0}=z$ and ${z}_{i}={\tau}_{i}{\tau}_{i1}...{\tau}_{1}\left(z\right)$ for $0<i\le p$ . Thus ${z}_{p}=\phi \left(z\right)$ . Since $\left\rightz\left\right<\left\right\phi \left(z\right)\left\right$ , there is some $i,1\le i\le p$ such that ${\tau}_{i}$ is a noninner Whitehead move of the second kind. Let $j$ be the smallest $i$ with this property. Then all ${\tau}_{i}$ with $i<j$ are either inner or relabeling automorphisms, $\left\rightz\left\right=\left\right{z}_{i}\left\right$ and ${z}_{i}\in T\left(\epsilon \right)$ .In particular, ${z}_{j1}\in T\left(\epsilon \right)$ and ${z}_{j1}$ is strictly minimal.Thus $$n=\left\rightz\left\right=\left\right{z}_{j1}\left\right\le \left\right{z}_{j}\left\right=\left\right{\tau}_{j}\left({z}_{j1}\right)\left\right<\left\right\phi \left(z\right)\left\right.$$ Let $(S,a)$ be the characteristic pair of ${\tau}_{j}$ and let ${S}^{\prime}=\widehat{A}S$ . Since ${\tau}_{j}$ is noninner, we have both $\leftS\right\ge 2$ , and $\left{S}^{\prime}\right\ge 2$ . Hence $\leftS\right\left{S}^{\prime}\right\ge 2(2k2)$ and there are at least $2(2k2)$ edges between $S$ and ${S}^{\prime}$ in the weighted Whitehead graph of ${z}_{j1}$ .Recall that $a.\widehat{A}$ is the total number of occurrences of ${a}^{\pm 1}$ in $z$ .By Lemma 6.5 , we have $\left\right{\tau}_{j}\left({z}_{j1}\right)\left\right\left\rightz\left\right=S.{S}^{\prime}a.\widehat{A}$ .By assumption on ${z}_{j1}$ we have $a.\widehat{A}\le n(\frac{1}{k}+\epsilon )$ and so $$\left\right{\tau}_{j}\left({z}_{j1}\right)\left\right\left\right{z}_{j1}\left\right=S.{S}^{\prime}a.\widehat{A}\ge 2n(2k2)\left(\frac{1}{k(2k1)}\epsilon \right)n\left(\frac{1}{k}+\epsilon \right).$$ Hence $$\left\right\phi \left(z\right)\left\right\ge \left\right{z}_{j}\left\right\ge n+2n(2k2)\left(\frac{1}{k(2k1)}\epsilon \right)n\left(\frac{1}{k}+\epsilon \right)$$ and so, since $n=\left\rightz\left\right$ , $$\frac{\left\right\phi \left(z\right)\left\right}{\left\rightz\left\right}\ge 1+(4k4)\left(\frac{1}{k(2k1)}\epsilon \right)\left(\frac{1}{k}+\epsilon \right)$$ Note that the above inequality holds for any element $z\in T\left(\epsilon \right)$ .Since $T\left(\epsilon \right)$ is exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic, this implies by Lemma 5.9 that $$\lambda \left(\phi \right)\ge 1+(4k4)(\frac{1}{k(2k1)}\epsilon )(\frac{1}{k}+\epsilon ).$$ Since $0<\epsilon <{\epsilon}_{0}$ was arbitrary, it follows that $$\lambda \left(\phi \right)\ge 1+(4k4)\frac{1}{k(2k1)}\frac{1}{k}=1+\frac{2k3}{2{k}^{2}k}>1.$$ This proves that (3) implies (1), so that (1), (2) and (3) are equivalent.Choose $0<{\epsilon}_{1}<{\epsilon}_{0}$ such that $$1+(4k4)\left(\frac{1}{k(2k1)}{\epsilon}_{1}\right)\left(\frac{1}{k}+{\epsilon}_{1}\right)<{c}_{0}=1+\frac{2k3}{4{k}^{2}2k}.$$ Put $W=T\left({\epsilon}_{1}\right)$ . The above argument shows that if for some $w\in W$ we have $$\frac{\left\right\phi \left(z\right)\left\right}{\left\rightz\left\right}<1+(4k4)\left(\frac{1}{k(2k1)}{\epsilon}_{1}\right)\left(\frac{1}{k}+{\epsilon}_{1}\right)$$ then $\phi $ is simple.With this $W$ we have proved that (5) implies (1). It is obvious that (1) implies (4)(7) and that each of (4), (5), (7) implies (6). Thus statements (1), (4), (5), (6), (7) are equivalent.We already know that (1), (2) and (3) are equivalent. This completes the proof of the theorem. □
Corollary 6.9.
Let
$F=F({a}_{1},...,{a}_{k})$
, where
$k\ge 2$
, and
$d$
be the word metric on
$F$
corresponding to the generating set
$A=\{{a}_{1},...,{a}_{k}\}$
. Let
$\phi \in Aut\left(F\right)$
. Then the following conditions are equivalent
 (1) The automorphism $\phi $ is simple.
 (2) The map $\phi :(F,d)\to (F,d)$ is a rough isometry.
 (3) The map $\phi :(F,d)\to (F,d)$ is a rough similarity.

Proof.
It is obvious that (1) implies (2) and that (2) implies (3). We will now show that (3) implies (1). Suppose that $\phi $ is a rough similarity, so that there exist $\lambda >0$ and $D>0$ such that for any $w\in F$ $$\lambda \leftw\rightD\le \left\phi \right(w\left)\right\le \lambda \leftw\right+D.$$ Then obviously $\lambda =\lambda \left(\phi \right)$ . By Theorem 6.8 either $\phi $ is simple or $\lambda \left(\phi \right)>1$ .Assume the latter. Put ${\lambda}_{0}=\frac{1+\lambda}{2}$ . Thus $1<{\lambda}_{0}<\lambda $ .Consider the ball ${B}_{n}$ of radius $n$ in $F$ , where $n>>1$ . For any $w\in F$ with $\leftw\right\ge n/{\lambda}_{0}$ we have $$\left\phi \right(w\left)\right\ge \lambda \leftw\rightD\ge \lambda n/{\lambda}_{0}D>n,$$ so that $\phi \left(w\right)\notin {B}_{n}$ .Thus only the elements of length $\le n/{\lambda}_{0}$ may be potentially taken to ${B}_{n}$ by $\phi $ .The number of such elements is smaller than $\#{B}_{n}$ since ${\lambda}_{0}>1$ and $n/{\lambda}_{0}<n$ . This contradicts the fact that $\phi :(F,d)\to (F,d)$ is a bijection. Therefore $\phi $ is simple, as required. □
Theorem 6.10.
Let
$F=F({a}_{1},...,{a}_{k})$
where
$k\ge 2$
. Let
$\phi :F\to X$
be a free minimal action on
$F$
on a simplicial tree
$X$
without inversions.
Then exactly one of the following occurs:
 (1) There is a simple automorphism $\alpha $ of $F$ such that $X$ is $\phi \circ \alpha $ equivariantly isomorphic to the Cayley graph of $F$ with respect to $\{{a}_{1},...,{a}_{k}\}$ . In this case $\lambda \left(\phi \right)=1$ .
 (2) We have $\lambda \left(\phi \right)\ge 1+\frac{1}{k(2k1)}$ .

Proof.
Let
$\Gamma =X/F$
and let
$T$
be a maximal tree in
$\Gamma $
and let
$B=\{{b}_{1},...,{b}_{k}\}$
be the geometric basis of
$F$
corresponding to
$T$
. Let
$\psi \in Aut\left(F\right)$
be defined by
$\alpha \left({b}_{i}\right)={a}_{i}$
for
$i=1,...,k$
. Note that because of Lemma 4.2 for any cyclic word $w$ over $B$ we have $\left\rightw{}_{X}\ge \leftw\right{}_{B}$ . Suppose first that $\alpha $ is not a simple automorphism. Then $\lambda \left(\alpha \right)\ge 1+\frac{2k3}{k(2k1)}$ .Hence for every $\epsilon >0$ there exists an exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic set $R\left(\epsilon \right)\subseteq \mathcal{C}\mathcal{\mathcal{R}}$ such that for any $w\in R\left(\epsilon \right)$ $$\frac{\left\rightw{}_{B}}{\left\rightw{}_{A}}=\frac{\left\right\alpha \left(w\right){}_{A}}{\left\rightw{}_{A}}\ge 1+\frac{2k3}{k(2k1)}\epsilon .$$ Since $\left\rightw{}_{X}\ge \leftw\right{}_{B}$ , it follows that $$\frac{\left\rightw{}_{X}}{\left\rightw{}_{A}}\ge 1+\frac{2k3}{k(2k1)}\epsilon .$$ Since $\epsilon >0$ was arbitrary, it follows by Lemma 5.9 that $$\lambda \left(\phi \right)\ge 1+\frac{2k3}{k(2k1)}\ge 1+\frac{1}{k(2k1)},$$ as required.Suppose now that $\alpha $ is a simple automorphism. We will assume that $\alpha =Id$ , and it will be easily seen that the general case is similar.If $\Gamma $ is a wedge of $k$ loopedges then the statement of the theorem holds. Suppose $\Gamma $ is not of this form. Then there exist edges $e,{e}^{\prime}\in E(\Gamma T)$ , ${e}^{\prime}\ne {e}^{1}$ , such that $\left[t\right(e),o({e}^{\prime}){]}_{T}$ has length at least $1$ . Let $z$ be the freely reduced word of length $2$ in $B$ corresponding to the sequence $e{e}^{\prime}$ . Let $\epsilon >0$ be arbitrary. Let $C(2,\epsilon /2)\subseteq \mathcal{C}\mathcal{\mathcal{R}}$ be defined as in Proposition 5.5 . Thus $C(2,\epsilon /2)$ consists of all cyclically reduced words ${w}^{\prime}$ such that for the cyclic word $w=\left({w}^{\prime}\right)$ and for every freely reduced word $xy$ in $A$ $$\left{f}_{w}\right(xy)\frac{1}{2k(2k1)}\le \epsilon /2.$$ Then $C(2,\epsilon /2)$ is exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic. Let ${w}^{\prime}\in C(2,\epsilon /2)$ be arbitrary and let $w=\left({w}^{\prime}\right)$ . Note that $\left\right{w}^{\prime}{}_{A}=\left{w}^{\prime}\right{}_{B}=\left\rightw{}_{A}=\leftw\right{}_{B}$ and $\left\rightw{}_{X}=\left{w}^{\prime}\right{}_{X}$ .Then $$\left\rightw{}_{X}\ge \leftw\right{}_{B}+{n}_{w}\left(z\right)+{n}_{w}\left({z}^{1}\right)=\left\rightw{}_{A}+{n}_{w}(z)+{n}_{w}({z}^{1})$$ and so $$\frac{\left\right{w}^{\prime}{}_{X}}{\left\right{w}^{\prime}{}_{A}}=\frac{\left\rightw{}_{X}}{\left\rightw{}_{A}}\ge 1+{f}_{w}\left(z\right)+{f}_{w}\left({z}^{1}\right)\ge 1+\frac{1}{k(2k1)}\epsilon .$$ Since $\epsilon >0$ was arbitrary, Lemma 5.9 implies that $\lambda \left(\phi \right)\ge 1+\frac{1}{k(2k1)}$ , as required. □
7 Application to the geometry of automorphisms
Definition 7.1.
Let
$F=F({a}_{1},...,{a}_{k})$
. An automorphism
$\phi $
of
$F$
is said to be
$(s,m)$
hyperbolic, where
$s>1$
and
$m\ge 1$
is an integer, if for every nontrivial cyclic word
$w$
we have
$$s\left\rightw\left\right\le max\left\{\right\left{\phi}^{m}\right(w\left)\right,\left{\phi}^{m}\right(w\left)\right\left\right\}.$$
An automorphism is hyperbolic if it is
$(s,m)$
hyperbolic for some
$s>1,m\ge 1$
.
The following lemma is an easy consequence of the above definition:
The following is Theorem E from the Introduction:
We can now prove Corollary I from the Introduction:
Lemma 7.2.
Let
$\phi \in Aut\left(F\right)$
be
$(s,m)$
hyperbolic and let
$w$
be a cyclic word of minimal length in its
$\langle \phi \rangle $
orbit. Then for any
$n\ge 2$
we have
$$\left\right{\phi}^{mn}\left(w\right)\left\right\ge {s}^{n1}\left\rightw\left\right.$$
 Proof. By definition of hyperbolicity of $\phi $ we have $$\left\right{\phi}^{m}\left(u\right)\left\right\le \left\rightu\left\right\Rightarrow s\left\rightu\left\right\le \left\right{\phi}^{m}\left(u\right)\left\right.$$ Note that by the choice of $w$ we have $\left\rightw\left\right\le \left\right{\phi}^{m}\left(w\right)\left\right$ . Hence applying (!) with $u={\phi}^{m}\left(w\right)$ we get $s\left\right{\phi}^{m}\left(w\right)\left\right\le \left\right{\phi}^{2m}\left(w\right)\left\right$ . Then, using (!), by induction on $n$ we see that for any $n\ge 1$ $$\left\right{\phi}^{m(n+1)}\left(w\right)\left\right=\left\right{\phi}^{mn+m}\left(w\right)\left\right\ge s\left\right{\phi}^{m}\left(w\right)\left\right.$$ This in turn implies that for any $n\ge 1$ $$\left\right{\phi}^{m(n+1)}\left(w\right)\left\right=\left\right{\phi}^{mn+m}\left(w\right)\left\right\ge {s}^{n}\left\right{\phi}^{m}\left(w\right)\left\right\ge {s}^{n1}\left\rightw\left\right.$$ This proves Lemma 7.2 . □
Theorem 7.3.
Let
$\phi $
be an
$(s,m)$
hyperbolic automorphism of
$F$
. Then
$${liminf}_{n\to \infty}\sqrt[n]{\lambda \left({\phi}^{n}\right)}\ge \sqrt[m]{s}>1.$$

Proof.
Let
$t\ge 2$
be an arbitrary integer. Let
$w\in SM$
be a strictly minimal element. Since
$w$
is minimal in its
$Aut\left(F\right)$
orbit, it is also minimal in its
$\langle \phi \rangle $
orbit. Therefore by Lemma 7.2 $$\left\right{\phi}^{tm}\left(w\right)\left\right\ge {s}^{t1}\left\rightw\left\right\text{and}\frac{\left\right{\phi}^{tm}\left(w\right)\left\right}{\left\rightw\left\right}\ge {s}^{t1}.$$ Since $SM$ is exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic, Lemma 5.9 implies that $\lambda \left({\phi}^{tm}\right)\ge {s}^{t1}$ .Moreover, there is $D>0$ such that for any cyclically reduced word $u$ we have $$\left\right{\phi}^{i}\left(u\right)\left\right\ge D\left\rightu\left\right,\text{for all}0\le i<m.$$ Let $n\ge 2m$ be an integer. Then we can write $n$ as $n=mt+i$ where $t\ge 2$ and $0\le i<m$ . For any $w\in SM$ we have $$\left\right{\phi}^{n}\left(w\right)\left\right=\left\right{\phi}^{mt+i}\left(w\right)\left\right\ge D\left\right{\phi}^{mt}\left(w\right)\left\right\ge D{s}^{t1}\left\rightw\left\right$$ and hence $$\frac{\left\right{\phi}^{tm}\left(w\right)\left\right}{\left\rightw\left\right}\ge D{s}^{t1}.$$ Since $SM$ is exponentially $\mathcal{C}\mathcal{\mathcal{R}}$ generic, Lemma 5.9 again implies that for any $n\ge 2m$ $$\lambda \left({\phi}^{n}\right)\ge D{s}^{t1}=\frac{D}{s}{s}^{\lfloor n/m\rfloor}.$$ This implies $${liminf}_{n\to \infty}\sqrt[n]{\lambda \left({\phi}^{n}\right)}\ge {s}^{1/m}>1,$$ as claimed. □
Corollary 7.4.
Let
$F=F({a}_{1},...,{a}_{k})$
be a free group of rank
$k\ge 2$
, equipped with the standard metric.
Then for any
$\phi \in Aut\left(F\right)$
we have:
$$flux\left(\phi \right)=\{\begin{array}{cc}0,& \text{if}\phi \text{is a relabeling automorphism}\\ 1,& \text{otherwise.}\end{array}$$

Proof.
Let
$\lambda =\lambda \left(\phi \right)$
be the generic stretching factor. Suppose first that $\lambda >1$ . Then the set $$T:=\{w\in F:\frac{\left\phi \right(w\left)\right}{\leftw\right}>\frac{\lambda +1}{2}$$ is exponentially $F$ generic.Let $B\left(n\right)$ be the ball of radius $n$ in $F$ and let $w\in B\left(n\right)\cap T$ be such that $2n/(\lambda +1)\le \leftw\right\le n$ . Then $$\left\phi \right(w\left)\right>\leftw\right\frac{\lambda +1}{2}\ge \frac{2n}{\lambda +1}\frac{\lambda +1}{2}=n$$ Hence for each $w\in \left[B\right(n)\cap T]B(2n/(\lambda +1\left)\right)$ we have $\left\phi \right(w\left)\right>n$ . The size of $B(2n/(\lambda +1\left)\right)$ is exponentially smaller than that of $B\left(n\right)$ since $2/(\lambda +1)<1$ .Hence by exponential genericity of $T$ $$\frac{\#\left[B\right(n)\cap T]\#B(2n/(\lambda +1\left)\right)}{\#B\left(n\right)}{\u27f6}_{n\to \infty}1\text{exponentially fast}.$$ Hence $${lim}_{n\to \infty}\frac{flu{x}_{\phi}\left(n\right)}{\#B\left(n\right)}=1$$ and therefore $flux\left(\phi \right)=1$ .Suppose now that $\lambda \left(\phi \right)=1$ . By Theorem 6.8 this implies that $\phi =\alpha \tau $ where $\alpha $ is inner and $\tau $ is a relabeling automorphism.If $\alpha =1$ , then obviously $flux\left(\phi \right)=0$ . Suppose now that $\alpha $ is nontrivial. Since $\tau $ acts as a permutation on each ball and each sphere in $F$ , we can assume that $\tau =1$ and $\phi =\alpha $ . Thus there is $u\in F,u\ne 1$ such that for every $w\in F$ $\phi \left(w\right)=uw{u}^{1}$ .There are $\ge {c}_{1}(2k1{)}^{n}$ elements $f$ with $\leftw\right=n$ such that the product $uw{u}^{1}$ is freely reduced as written, where ${c}_{1}>0$ is a constant independent of $n$ and $u$ . For each such element we have $\left\phi \right(w\left)\right>\leftw\right$ . Hence there is a constant ${c}_{2}\in (0,1)$ independent of $n$ and $u$ such that for any $n>0$ $$1\ge \frac{flu{x}_{\phi}\left(n\right)}{\#B\left(n\right)}\ge {c}_{2}>0.$$ Hence $$1\ge flux\left(\phi \right)={lim}_{n\to \infty}\sqrt[n]{\frac{flu{x}_{\phi}\left(n\right)}{\#B\left(n\right)}}\ge {lim}_{n\to \infty}\sqrt[n]{{c}_{2}}=1.$$ Thus $flux\left(\phi \right)=1$ and the proof is complete.□
8 Random elements in regular languages
The most reasonable way of choosing a “random” element in the regular language
$L$
is via a random walk in the transition graph of an automaton
$M$
accepting
$L$
. It turns out that the natural model of computation here is that of a nondeterministic finite automaton or NDFA. Such an automaton
$M$
over an alphabet
$A$
with state set
$Q$
is specified by a finite directed graph
$\Gamma \left(M\right)$
. The vertex set of
$\Gamma \left(M\right)$
is the set
$Q$
of states of
$M$
and
$Q$
comes equipped with a distinguished nonempty subset
$I$
of initial or start states. The directed edges of
$\Gamma \left(M\right)$
are labelled by elements of
$A$
and these edges are treated as transitions of
$M$
. If
$q\in Q$
is a state and
$a\in A$
is a letter, we allow multiple edges labelled
$a$
with origin
$q$
and we also allow the case when there are no such edges. Nondeterministic automata are thus by their nature ”partial”. There is a distinguished subset of
$Q$
of accepting states. A word
$w$
over
$A$
is said to be accepted by
$M$
if there exists a directed path with label
$w$
in
$\Gamma \left(M\right)$
from some initial state to an accepting state. The language,
$L\left(M\right)$
, accepted by
$M$
is the collection of all words accepted by
$M$
.
We will also use directed graph
${\Gamma}_{1}\left(M\right)$
defined as follows. The vertex set of of
${\Gamma}_{1}\left(M\right)$
is the set of directed edges
$E(\Gamma (M\left)\right)$
of
$M$
. If
${e}_{1},{e}_{2}\in E(\Gamma (M\left)\right)$
the pair
$({e}_{1},{e}_{2})$
defines a directed edge from
${e}_{1}$
to
${e}_{2}$
in
${\Gamma}_{1}\left(M\right)$
if the terminus of
${e}_{1}$
is the origin of
${e}_{2}$
, that is,
${e}_{1},{e}_{2}$
is a directed edgepath in
$\Gamma \left(M\right)$
.
Definition 8.1 (Normal Automaton).
Let
$A$
be a finite alphabet. A normal automaton over a finite alphabet
$A$
is a nondeterministic finite state automaton
$M$
over
$A$
such that the following conditions hold:
The third condition in the above definition is the most important one as it is responsible for the irreducibility of a Markov chain naturally associated to a normal automaton: $\bullet $ the automaton $M$ has a nonempty set of accept states;
 $\bullet $ the directed graph $\Gamma \left(M\right)$ has at least one edge;
 $\bullet $ the directed graph $\Gamma \left(M\right)$ is strongly connected, that is for any two states $q,{q}^{\prime}$ of $M$ there exists a directed edgepath from $q$ to ${q}^{\prime}$ in $\Gamma \left(M\right)$ .
Definition 8.2 (Associated Markov chain).
Let
$M$
be a normal automaton over a finite alphabet
$A$
. We define an associated finite state Markov chain
${M}^{\prime}$
as follows. The set of states of
${M}^{\prime}$
is the set
$E$
of directed edges of
$\Gamma \left(M\right)$
. If the origin of
$f$
is not the terminus of
$e$
we put the transition probability
${p}_{e,f}=0$
. If the origin of
$f$
is equal to the terminus of
$e$
we put
${p}_{e,f}=1/m$
, where
$m$
is the total number of outgoing directed edges from the terminus of
$e$
.
Convention 8.3.
Note that the sample space
$\Omega $
for the Markov chain
${M}^{\prime}$
defined above consists of all semiinfinite directed edgepaths
$$\omega ={e}_{1},{e}_{2},...,{e}_{n},...$$
in the graph
$\Gamma \left(M\right)$
. Every such path has a label
$$w\left(\omega \right)={a}_{1}{a}_{2}...,$$
that is a semiinfinite word over the alphabet
$A$
. We will denote
${w}_{n}={w}_{n}\left(\omega \right):={a}_{1}...{a}_{n}$
, the initial segment of length
$n$
of
$w$
. The set
$\Omega $
comes equipped with the natural topology, where we think of
$\Omega $
as the union of boundaries of rooted trees
$({T}_{e}{)}_{e}\in E$
. The vertices of
${T}_{e}$
are finite edgepath in
$\Gamma \left(M\right)$
beginning with
$e$
. The Borel
$\sigma $
algebra on
$\Omega $
is generated by the following openclosed cylinder sets
$Cyl\left(\gamma \right)$
, where
$\gamma $
is a nonempty finite edgepath in
$\Gamma \left(M\right)$
:
$$Cyl\left(\gamma \right):=\{\omega \in \Omega :p\text{is the initial segment of}\omega \}.$$
If we put an initial probability distribution
$\mu $
on
$E$
, this defines a Borel probability measure
${P}_{\mu}$
on
$\Omega $
. This measure is defined on the cylinder sets by the standard convolution formula. If
$\gamma ={e}_{1},...,{e}_{n}$
, where
$n>1$
, then
$${P}_{\mu}\left(Cyl\right(\gamma \left)\right):=\mu \left({e}_{1}\right){p}_{{e}_{1},{e}_{2}}{p}_{{e}_{2},{e}_{3}}...{p}_{{e}_{n1},{e}_{n}}.$$
If
$n=1$
then
${P}_{\mu}\left(Cyl\right(e\left)\right):=\mu \left(e\right)$
.
Lemma 8.4.
Let
$M$
be a normal automaton. Then the associated finite state Markov chain
${M}^{\prime}$
is irreducible. In particular, there is a unique stationary initial probability distribution
${\mu}_{0}$
on the set of states
$E$
of
${M}^{\prime}$
.
This distribution has the property
${\mu}_{0}\left(e\right)>0$
for each
$e\in E$
.
If we fix an initial probability distribution
$\mu $
on
$E$
, this defines a probability measure
${P}_{\mu}$
on
$\Omega $
.

Proof.
To show that
${M}^{\prime}$
is irreducible we have two prove that for any two edges
$e,f\in E$
there is
$n>0$
such that the
$n$
step transition probability
${p}_{e,f}^{\left(n\right)}>0$
. Since
$\Gamma \left(M\right)$
is strongly connected, there exists a directed edgepath
$\gamma $
in
$\Gamma \left(M\right)$
from the terminus of
$e$
to the origin of
$f$
. Then
$e\gamma f$
is a directed edgepath in
$\Gamma \left(M\right)$
that starts with
$e$
and ends with
$f$
. Hence
${\Gamma}_{1}\left(M\right)$
is strongly connected and therefore
${M}^{\prime}$
is irreducible. The irreducibility of ${M}^{\prime}$ implies the existence and uniqueness of a positive stationary distribution ${\mu}_{0}$ on $E$ , as required. □
Lemma 8.5.
Let
$M$
be a normal automaton. Let
${M}^{\prime}$
be the associated finite state Markov chain and let
${\mu}_{0}$
be the stationary initial distribution for
${M}^{\prime}$
. Let
$Z\subseteq \Omega $
be a set such that
${P}_{{\mu}_{0}}\left(Z\right)=0$
. Then for any other initial distribution
$\mu $
on
$E$
we have
${P}_{\mu}\left(Z\right)=0$
.
The previous two lemmas depend only on the automaton
$M$
being normal.
 Proof. Let $\mu $ and ${\mu}_{0}$ be as above. Put $$c:=max\{\frac{\mu \left(e\right)}{{\mu}_{0}\left(e\right)}:e\in E\}.$$ Note that $0<c<\infty $ since ${\mu}_{0}\left(e\right)>0$ for each $e\in E$ . Consider an arbitrary cylinder set $Cyl\left(\gamma \right)\subset \Omega $ , where $\gamma ={e}_{1},{e}_{2},...{e}_{n}$ . From the definitions of ${P}_{\mu}$ and ${P}_{{\mu}_{0}}$ we see that $${P}_{\mu}\left(Cyl\right(\gamma \left)\right)=\frac{\mu \left({e}_{1}\right)}{{\mu}_{0}\left({e}_{1}\right)}{P}_{{\mu}_{0}}\left(Cyl\right(\gamma \left)\right)\le c{P}_{{\mu}_{0}}\left(Cyl\right(\gamma \left)\right).$$ Hence for an arbitrary Borel set $Z\subseteq \Omega $ we have ${P}_{\mu}\left(Z\right)\le c{P}_{{\mu}_{0}}\left(Z\right)$ . In particular, if ${P}_{{\mu}_{0}}\left(Z\right)=0$ then ${P}_{\mu}\left(Z\right)=0$ . □
Suppose now that
$L=L\left(M\right)$
. For each state
$q$
choose a shortest path from
$q$
to an accept state and let
${u}_{q}$
be the word in
${A}^{*}$
labelling that path. This is possible since
$\Gamma \left(M\right)$
is strongly connected and the set of accept states is nonempty by the assumption on
$M$
. Note that
${u}_{q}$
is the empty word if and only if
$q$
is an accept state.
The lengths of
${u}_{q}$
are bounded above by some constant depending on
$M$
. For a finite walk
${w}_{n}$
denote
${w}_{n}^{\prime}={w}_{n}{u}_{q}$
where
$q$
is the state in which
${w}_{n}$
ends. Note that if
${w}_{n}$
begins in a state from
$I$
then
${w}_{n}^{\prime}\in L$
. Thus if
$\mu $
is an distribution supported on the set of edges in
$E\left(M\right)$
with initial vertices from
$I$
and
${w}_{n}$
is obtained by performing
$n$
steps of the chain
${M}^{\prime}$
with initial distribution
$\mu $
, then
${w}_{n}^{\prime}\in L$
can be thought of as a ”random” element of
$L$
.
We can now prove (a slight generalization of ) Theorem J from the Introduction:
Theorem 8.6.
Let
$M$
be a normal automaton over the alphabet
$A$
and let
$L=L\left(M\right)$
be the language accepted by
$M$
.
There is substantial flexibility in the choice of the Markov chain
${M}^{\prime}$
. The proof of Theorem 8.6 goes through without change for any choice of transition probabilities in
${M}^{\prime}$
such that
${p}_{e,f}>0$
whenever
$(e,f)$
is an edge of
${\Gamma}_{1}\left(M\right)$
and
${p}_{e,f}=0$
whenever
$(e,f)$
is not an edge of
${\Gamma}_{1}\left(M\right)$
.
Let
$\phi :{A}^{*}\to G$
be a monoid homomorphism, where
$G$
is a group with a leftinvariant semimetric
${d}_{G}$
. Then there exists a number
$\lambda =\lambda (M,\phi ,{d}_{G})\ge 0$
such that for any initial distribution
$\mu $
on
$E\left(M\right)$
we have
$${lim}_{n\to \infty}\frac{\left\phi \right({w}_{n}){}_{G}}{n}={lim}_{n\to \infty}\frac{\left\phi \right({w}_{n}^{\prime}){}_{G}}{n}=\lambda \text{almost surely and in}{L}^{1}\text{with respect to}{P}_{\mu}.$$

Proof.
Let
${\mu}_{0}$
be the unique stationary initial distribution for
${M}^{\prime}$
. As before denote by
$\mathcal{S}:\Omega \to \Omega $
the shift operator which erases the first edge of every
$\omega ={e}_{1},{e}_{2},\cdot \cdot \cdot \in \Omega $
. Stationarity of
${\mu}_{0}$
means that
$\mathcal{S}:(\Omega ,{P}_{{\mu}_{0}})\to (\Omega ,{P}_{{\mu}_{0}})$
is a measurepreserving map. Since
${M}^{\prime}$
is irreducible and aperiodic,
$\mathcal{S}$
is also ergodic. As before, define ${X}_{n}:\Omega \to \mathbb{R}$ as $${X}_{n}\left(\omega \right):=\left\phi \right({w}_{n}\left(\omega \right)){}_{G}.$$ Then again it is easy to see that ${X}_{n}\ge 0$ , ${X}_{n+m}\left(\omega \right)\le {X}_{n}\left(\omega \right)+{X}_{m}\left({\mathcal{S}}^{n}\omega \right)$ . Hence by the Subadditive Ergodic Theorem there is $\lambda \ge 0$ and there is a subset $Q\subseteq \Omega $ with ${P}_{{\mu}_{0}}\left(Z\right)=0$ such that for any $\omega \notin Z$ $${lim}_{n\to \infty}\frac{\left\phi \right({w}_{n}\left(\omega \right)){}_{G}}{n}=\lambda .$$ Let $\mu $ be an arbitrary initial distribution on $E$ . Then by Lemma 8.5 we have ${P}_{\mu}\left(Z\right)=0$ . Thus $$\frac{\left\phi \right({w}_{n}){}_{G}}{n}\to \lambda \text{almost surely with respect to}{P}_{\mu}.$$ Note that by the leftinvariance of ${d}_{G}$ we have $\left\phi \right(w){}_{G}\le Kw$ where $K=max\left\{\right\phi \left(a\right){}_{G}:a\in A\}$ . Hence ${X}_{n}/n=\left\phi \right({w}_{n}){}_{G}/n\le K$ and by the Dominated Convergence Theorem almost sure convergence of ${X}_{n}/n$ implies ${L}^{1}$ convergence.Since ${d}_{G}$ is a seminorm on $G$ and the length of any path ${w}_{n}^{\prime}$ differs from $\left{w}_{n}\right$ by at most a fixed constant, it is also true that $\left\phi \right({w}_{n}^{\prime}){}_{G}$ differs from $\left\phi \right({w}_{n}){}_{G}$ by at most a fixed constant and thus it is also the case that $${lim}_{n\to \infty}\frac{\left\phi \right({w}_{n}^{\prime}\left(\omega \right)){}_{G}}{n}={lim}_{n\to \infty}\frac{\left\phi \right({w}_{n}\left(\omega \right)){}_{G}}{n}=\lambda .$$ □
9 Open Problems
Problem 9.1.
Let
$\phi $
be an arbitrary (not necessarily injective) endomorphism of
$F=F({a}_{1},...,{a}_{k})$
. Is
$\lambda \left(\phi \right)$
rational? Computable?
Problem 9.2.
Let
$\phi \in Aut\left(F\right)$
. What can be said about the behavior of
$\lambda \left({\phi}^{n}\right)$
as
$n\to \infty $
? Same for
$\sqrt[n]{\lambda \left({\phi}^{n}\right)}$
. How are these quantities connected with growth rates of different (or perhaps just top) strata from relative traintrack representatives of
$\phi $
?
It is clear that the asymptotics of
$\lambda \left({\phi}^{n}\right)$
should reflect the dynamical properties of
$\phi $
. For example, it is not hard to see that for any Nielsen automorphism
$\tau $
the stretching factor
$\lambda \left({\tau}^{n}\right)$
grows at most linearly and
${limsup}_{n\to \infty}\sqrt[n]{\lambda \left({\tau}^{n}\right)}=1$
.
On the other hand for hyperbolic automorphisms
$\phi $
Theorem 7.3 implies that
${liminf}_{n\to \infty}\sqrt[n]{\lambda \left({\phi}^{n}\right)}>1$
, so that the sequence
$\left(\lambda \right({\phi}^{n}){)}_{n}$
grows exponentially.
Problem 9.3.
Can one estimate (say in the sense of Large Deviations) the speed of convergence
$\frac{\left\phi \right({\omega}_{n}){}_{G}}{n}\to \lambda \left(\phi \right)$
?
We have seen that in the case of free group automorphisms for any
$\epsilon >0$
$${P}_{n}\left(\frac{\left\phi \right({\omega}_{n}\left)\right}{n}\in \left(\lambda \right(\phi )\epsilon ,\lambda (\phi )+\epsilon )\right)\to 1$$
with exponentially fast convergence as
$n\to \infty $
. Are there any other situations where the speed of convergence in Theorem A can be estimated?
Problem 9.4.
Let
$F=F({a}_{1},...,{a}_{k})$
where
$k\ge 2$
. Consider the set
$$W=\left\{\lambda \right(\phi ):\phi :F\to Aut(X\left)\text{is a free simplicial action of}F\text{on some simplicial tree}X\right\}.$$
We know that
$W\subseteq \mathbb{Q}$
and, moreover
$2kW\subseteq \mathbb{Z}\left[\frac{1}{2k1}\right]$
.
Is
$W$
a discrete subset of
$\mathbb{Q}$
?
Problem 9.5.
The notion of a generic stretching factor for
$\phi \in Aut\left(F\right)$
depends on the choice of a free basis
$b=({a}_{1},...,{a}_{k})$
of
$F$
, and, more generally, on the choice of a finite generating set
$S$
of
$F$
and the corresponding word metric
${d}_{S}$
. Denote by
${\lambda}_{S}\left(\phi \right)$
the generic stretching factor of
$\phi $
considered as a map
$(F,{d}_{S})\to (F,{d}_{S})$
.
One can define the following uniform constants
$${\lambda}^{\prime}\left(\phi \right):=inf\left\{{\lambda}_{b}\right(\phi ):b\text{is a free basis of}F\}$$
and
$${\lambda}^{\prime \prime}\left(\phi \right):=inf\left\{{\lambda}_{S}\right(\phi ):S\text{is a finite generating set of}F\}.$$
(Note that
${\lambda}^{\prime \prime}\left(\phi \right)$
can be defined in the same fashion for an automorphism
$\phi $
of an arbitrary finitely generated group
$G$
).
For