, , ,

2000 Mathematics Subject Classification. Primary 20F65, Secondary 37A, 37E, 57M.The second and the third author were supported by the NSF grant DMS#0404991 and the NSA grant DMA#H98230-04-1-0115 .

<ph f="cmbx">The Subadditive Ergodic Theorem and generic stretching factors for free group automorphisms</ph>

Vadim Kaimanovich, Ilya Kapovich,

Paul Schupp

IRMAR, Universite Rennes-1, Campus de Beaulieu, 35042, Rennes Cedex, France; E-mail address : kaimanov@univ-rennes1.fr Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green Street, Urbana, IL 61801, USA http://www.math.uiuc.edu/~kapovich/ E-mail address : kapovich@math.uiuc.edu Department of Mathematics, University of Illinois at Urbana-Champaign,1409 West Green Street, Urbana, IL 61801, USAhttp://www.math.uiuc.edu/People/schupp.html E-mail address : schupp@math.uiuc.edu

Abstract. Given a free group $F_{k}$ of rank $k \geq 2$ with a fixed set of free generators we associate to any homomorphism $φ$ from $F_{k}$ to a group $G$ with a left-invariant semi-norm a generic stretching factor, $λ (φ)$ , which is a non-commutative generalization of the translation number. We concentrate on the situation when $φ : F_{k} \to A u t (X)$ corresponds to a free action of $F_{k}$ on a simplicial tree $X$ , in particular, when $φ$ corresponds to the action of $F_{k}$ on its Cayley graph via an automorphism of $F_{k}$ . In this case we are able to obtain some detailed “arithmetic” information about the possible values of $λ = λ (φ)$ . We show that $λ \geq 1$ and is a rational number with $2 k λ \in Z [\frac{1}{2 k - 1}]$ for every $φ \in A u t (F_{k})$ .
We also prove that the set of all $λ (φ)$ , where $φ$ varies over $A u t (F_{k})$ , has a gap between $1$ and $1 + \frac{2 k - 3}{2 k^{2} - k}$ , and the value $1$ is attained only for “trivial” reasons.
Furthermore, there is an algorithm which, when given $φ$ , calculates $λ (φ)$ .

Contents

1 Introduction

1.1 Random subgroup distortion and growth of random automorphisms

Let

G

be a finitely generated group with a word metric

d_{S}

determined by a finite generating set

S

and write

| g |_{S} : = d_{S} (1, g)

for

g \in G

. Recall that if

H = 〈 T 〉

is a subgroup of

G

generated by a finite set

T

, then a function

f

is said to be a distortion function of

H

G

if for every

h \in H

we have

| h |_{T} \leq f (| h |_{S})

. The subgroup

H

is quasi-isometrically embedded in

G

if and only if for some (and hence for all) choices of

S, T

there is a linear distortion function for

H

G

, that is if the ratio

\frac{| h |_{T}}{| h |_{S}}

is bounded on

H \ {1}

The translation number of an element

g \in G

is defined as

λ (g) = λ_{S} (g) = {lim}_{n \to \infty} \frac{| g^{n} |_{S}}{n}

and the limit exists by the subadditivity of the sequence

| g^{n} |_{S}

. If

g

has infinite order, then the cyclic subgroup

〈 g 〉

is quasi-isometrically embedded in

G

if and only if

λ_{S} (g) > 0

for some (and hence for any) finite generating set

S

G

The study of “random” or “generic” behavior is currently an increasingly active area of investigation in many different group-theoretic contexts. (See, for example, [24, 42, 25, 10, 11, 12, 13, 14, 2, 3, 4, 1, 45, 32, 33, 34, 21, 41] ). In this paper we concentrate on algebraic and geometric consequences of subadditivity, specifically of Kingman's Subadditive Ergodic Theorem. We investigate a “noncommutative analogue” of translation number which is defined for a “mapped-in” subgroup

H = φ (F)

, where

φ : F \to G

is a homomorphism of a free nonabelian group

F = F (A)

of finite rank into a group

G

with generating set

S

. Namely, there is a number

λ = λ (φ, A, S) \geq 0

such that for long “random” freely reduced words

w \in F (A)

we have

\frac{| φ (w) |_{S}}{| w |_{A}} \approx λ

. (Instead of the word metric

d_{S}

one could actually take an arbitrary semi-norm on

G

.) Throughout this paper we fix the notation that

F = F (A)

is the free group with basis

A = {a_{1}, . . ., a_{k}}

where

k \geq 2

. For any

w \in F

let

| w |

denote the length of the unique freely reduced word over

A^{\pm 1}

representing

w

. We identify the hyperbolic boundary

\partial F

with the set of all geodesic rays from

1 \in F

in the Cayley graph

Γ (F, A)

F

, that is,

\partial F

is the set of all semi-infinite freely reduced words over

A^{\pm 1}

endowed with the standard topology. The space

\partial F

can be identified with the space of ends or the hyperbolic boundary of

F

The Borel

σ

-algebra

ℱ

\partial F

is generated by the cylinder sets

C y l_{A} (v), v \in F

, where

C y l_{A} (v)

consists of all infinite rays

ω \in \partial F

that begin with

v

. The uniform Borel probability measure

μ A

\partial F

corresponding to

A

is defined by assigning equal weights to all cylinders based on the words on the same length. That is,

μ A (C y l_{A} (v)) = \frac{1}{2 k (2 k - 1)^{| v | - 1}} \forall v \in F \ {1} .

Note that although the boundary

\partial F

could be defined without referring to a particular generating set

A

, the uniformity of the measure

μ A

does depend on the choice of

A

. The fact that the uniform measures corresponding to two different free generating sets may well be singular respect to each other is actually the cornerstone of our approach. (See [20] for a detailed discussion of this phenomenon in the general context of word-hyperbolic groups and of the Patterson-Sullivan measures corresponding to geometric actions of such groups on Gromov-hyperbolic spaces.) A ray

ω \in \partial F

can be thought of as a non-backtracking edge-path in

Γ (F, A)

starting from the identity

1

. We denote by

ω_{n}

the vertex on

ω

at distance

n

from

1

. The measure space

(\partial F, μ A)

then becomes the space of sample paths of the non-backtracking simple random walk (NBSRW) on the Cayley graph of

F

. This is the Markov chain on

F

whose transition probabilities

π_{w}, w \in F

are equidistributed among the neighbors of

w

which are strictly further from the group identity. By choosing a random

μ A

-distributed point

ω \in \partial F

we may think about

ω_{n}

as a “random” (with respect to the NBSRW) freely reduced word of length

n

F

In Section 2 we prove:

Theorem A. Let

F = F (a_{1}, . . ., a_{k})

with

k \geq 1

, and let

μ A

be the uniform Borel probability measure on

\partial F

corresponding to the basis

A = {a_{1}, . . ., a_{k}}

Let

φ : F \to G

be a homomorphism to a group

G

endowed with a semi-norm, that is, a nonnegative function

| \cdot |_{G}

G

satisfying

| g h |_{G} \leq | g |_{G} + | h |_{G}

for all

g, h \in H

Then:

(1) There exists a real number $λ \geq 0$ such that ${lim}_{n \to \infty} \frac{| φ (ω_{n}) |_{G}}{n} = λ$ $μ A$ -a.e. and in $L^{1} (\partial F, μ A)$ .
(2) Suppose further that the image group $φ (F)$ is non-amenable, and that the sequence $b_{n} = # {g \in φ (F) : | g |_{G} \leq n}$ grows at most exponentially. Then $λ > 0$ .

Note that the requirement of at most exponential growth of the

b_{n}

is automatically satisfied if the group

G

is finitely generated, and

| \cdot |_{G}

is the word metric on

G

determined by a finite generating set.

Theorem A says that for a long “random” freely reduced element

w \in F

we have

\frac{| φ (w) |_{G}}{| w |} \approx λ

. For this reason we shall call the number

λ = λ (φ, A, | \cdot |_{G})

, whose existence is provided by part (1) of Theorem A , the generic stretching factor of

φ

with respect to the free basis

A

F

and the semi-norm

| \cdot |_{G}

We deduce Theorem A from the fact that the sample paths of the usual simple random walk on the group

F

asymptotically follow geodesics and the well-known results on the linear rate of escape of random walks on groups [37] , [29] . We also give an alternative direct argument proof of part (1) of Theorem A applying Kingman's Subadditive Ergodic Theorem [36] . Part (2) of Theorem A can also be proved using the results of Cohen [15] , Grigorchuck [22] and Woess [44] on co-growth in groups.

Example 1.1 (Stretching factors for isometric actions). A typical example of a semi-norm

| \cdot |_{G}

comes from isometric group actions on metric spaces.

Namely, let

X

be a metric space with basepoint

x \in X

. For an isometry

g

X

define

| g |_{x} : = d (x, g x)

. The triangle inequality implies that

| g_{1} g_{2} |_{x} \leq | g_{1} |_{x} + | g_{2} |_{x}

, so that

| \cdot |_{x}

is a semi-norm on

G = I s o m (X)

. Suppose

F = F (a_{1}, . . ., a_{k})

acts by isometries on

X

by a homomorphism

φ : F \to G

. It is easy to see that in this case

λ (φ, A, | \cdot |_{x})

does not depend on the choice of a base-point

x \in X

and is determined by the action

φ

and the choice of the basis

A

F

. In this case we shall denote

λ (φ, A, | \cdot |_{x})

λ (φ, A)

, or just by

λ (φ)

if the choice of

A

is fixed.

Example 1.2 (Random Subgroup Distortion). Let

H \leq G

be finitely generated groups with finite generating sets

A \subset H

and

S \subset G

, respectively.

Denote the associated length functions by

| \cdot |_{G}

and

| \cdot |_{H}

. Now

H

is a quotient of

F = F (A)

. Let

φ : F (A) \to G

be composition of this quotient map with the inclusion of

H

into

G

. Then

| φ (w) |_{H} \leq | w |

for any

w \in F

. If the group

H

is non-amenable then by Theorem A for a long “random” freely reduced word

w

F (A)

\frac{| φ (w) |_{H}}{| w |} \approx λ_{1} > 0, and \frac{| φ (w) |_{G}}{| w |} \approx λ_{2} > 0,

and therefore

\frac{| φ (w) |_{H}}{| φ (w) |_{G}} \approx \frac{λ_{1}}{λ_{2}},

where the constants

λ_{1}, λ_{2} > 0

do not depend on

w

. Thus, informally speaking, Theorem A implies that any nonamenable finitely generated subgroup

H

of a finitely generated group

G

has “generic-case” linear distortion in

G

Example 1.3 (Normal Forms). Let

G

be a nonamenable group with a finite generating set

A

and the associated length function

| \cdot |_{G}

. We will denote by

\bar{w}

the element of

G

represented by a word

w

in the alphabet

A \cup A^{- 1}

Let

L \subseteq (A \cup A^{- 1})^{*}

be a set of normal forms (not necessarily unique) for elements of

G

, that is

\bar{L} = G

. Consider, for instance, the case where

L

is an automatic language for

G

. By Theorem A there is

λ > 0

such that for a random long freely reduced word

w \in F (A)

we have

\frac{| \bar{w} |_{G}}{| w |} \approx λ

Let

w_{L} \in L

be a word representing the same element of

G

w

. Then

| w_{L} | \geq | \bar{w} |_{G}

and hence

\frac{| w_{L} |}{| w |} \geq \frac{| \bar{w} |_{G}}{| w |} \approx λ > 0 .

Thus for a long random word

w \in F (S)

when we take

\bar{w}

to a normal form

w_{L} \in L

, the ratio

\frac{| w_{L} |}{| w |}

is separated from zero. This conclusion applies to a number of experimental observations, such as those obtained by Dehornoy [17] in the case of braid groups.

Theorem A has implications regarding the growth of random automorphisms.

Let

G

be a finitely generated group with a fixed word metric corresponding to a finite generating set

S

. Let

φ \in A u t (G)

be an automorphism. We define the norm of

φ

with respect to

S

| | φ | | = | | φ | |_{S} : = {max}_{s \in S} | φ (s) |_{S} .

Then for any

g \in G

we have

| φ (g) |_{S} \leq | | φ | |_{S} | g |_{S}

and hence

| | φ | | = {sup}_{g \in G, g \neq 1} \frac{| φ (g) |_{S}}{| g |_{S}} .

For an individual

φ

the sequence

log | | φ^{n} | |

is subadditive and therefore the following limit (sometimes called the growth entropy of

φ

) exists:

ν (φ) : = {lim}_{n \to \infty} \frac{log | | φ^{n} | |}{n} .

It turns out that this notion has a generalization for an arbitrary finitely generated subgroup of

A u t (G)

Theorem B. Let

G

be a nontrivial finitely generated group with a word-metric

d_{S}

corresponding to a finite generating set

S

. Let

H \leq A u t (G)

be a noncyclic subgroup with a finite generating set

T

. Then:

(1) There is $ν = ν (H) = ν (H, T, S) \geq 0$ such that for a non-backtracking simple random walk $φ_{n}$ on the Cayley graph of $H$ with respect to $T$ we have ${lim}_{n \to \infty} \frac{log | | φ_{n} | |_{S}}{n} = ν$ almost surely and in $L^{1}$ .
(2) If $G$ has polynomial growth and $H$ is non-amenable then $ν (H, T, S) > 0$ .

Note that

ν (H, T, S) > 0

means that

| | φ_{n} | |_{S}

grows exponentially with

n

for a ”random” automorphism

φ_{n}

Corollary C. Let

F

be a free group of finite rank

k \geq 2

and let

H \leq A u t (F)

be a finitely generated group of automorphisms of

F

such that the image

H^{'}

H

A u t (F_{a b}) \sim = G L (k, Z)

is non-amenable. Then for any finite generating set

S

F

and for any finite generating set

T

H

we have

ν (H, T, S) > 0

By the Tits alternative a subgroup of

G L (k, Z)

is either virtually solvable (and hence amenable) or it contains a free subgroup of rank two (and hence is nonamenable).

Thus in the above corollary we could replace the assumption that

H^{'}

is nonamenable by the requirement that

H^{'}

is not virtually solvable.

1.2 Free actions on trees: Two interpretation of stretching factors

In the context of free and discrete isometric actions of free groups on

R

-trees (cf. Example 1.1 ). generic stretching factors are related to Bonahon's notion [5, 6] of the intersection number between geodesic currents on hyperbolic surfaces. If

G

is a non-elementary word-hyperbolic group, a geodesic current on

G

is a

G

-invariant positive Borel measure on

\partial^{2} G : = {(x, y) | x, y \in \partial G, x \neq y}

. The space of all geodesic currents on

G

, endowed with the weak-

*

-topology, is denoted by

C u r r (G)

(See [7, 31] for a detailed discussion on the subject.) Every nontrivial conjugacy class

[g]

G

defines an associated “counting” current

η_{[g]}

G

. When

S

is a closed surface of negative Euler characteristic and

G = π_{1} (S)

, Bonahon proved that the notion of geometric intersection number between free homotopy classes of essential closed curves on

S

(that is, between nontrivial conjugacy classes of

G

) extends to a bilinear continuous “intersection form”

i : C u r r (G) \times C u r r (G) \to R .

Note that in this case

\partial G = \partial H^{2} = S^{1}

. For every hyperbolic structure

ρ

S

there is an associated Liouville current

L_{ρ} \in C u r r (G)

(see [5] ). Bonahon's construction has the following natural property: if

ρ

is as above and

[g]

is a nontrivial conjugacy class in

G

then

i (L_{ρ}, η_{[g]}) = ℓ_{ρ} (g)

. Here

ℓ_{ρ} : G \to R

is the length spectrum of

ρ

Thus

ℓ_{ρ} (g)

is equal to the translation length of

g

as an isometry of

H^{2} = \tilde{(S, ρ)}

and it is also equal to the

ρ

-length of the shortest curve of the free homotopy class of closed curves on

S

corresponding to

[g]

. It turns out that the intersection number

i (L_{ρ}, L_{ρ^{'}})

between Liouville currents corresponding to two hyperbolic structures

ρ, ρ^{'}

can be interpreted as the generic stretching factor of a long random closed geodesic on

(S, ρ)

with respect to

ρ^{'}

. Namely, let

p \in S

and let

v

be a random unit tangent vector at

p

(S, ρ)

. For every

n \geq 1

let

α_{n}

be the geodesic of length

n

(S, ρ)

with origin

p

and with the tangent vector

v

p

. Let

β_{n}

be a geodesic from the terminus of

α_{n}

p

of length

\leq D i a m (S, ρ)

. Then

γ_{n} = α_{n} β_{n}

is a closed curve on

S

. Bonahon's results imply that

{lim}_{n \to \infty} \frac{ℓ_{ρ^{'}} ([γ_{n}])}{ℓ_{ρ} ([γ_{n}])} = {lim}_{n \to \infty} \frac{ℓ_{ρ^{'}} ([γ_{n})])}{n} = \frac{i (ρ, ρ^{'})}{π^{2} | χ (S) |} .

It turns out that a version of this interpretation applies in the context of free groups acting on trees. Let

F

be a free group of finite rank

k \geq 2

In [30, 31] Kapovich investigated a natural “intersection form”

I : F L e n (F) \times C u r r (F) \to F

, where

F L e n (F)

is the space of hyperbolic length functions corresponding to free and discrete isometric actions of

F

R

-trees. This form still has the natural property that for any nontrivial conjugacy class

[g]

F

and any

ℓ \in F L e n (F)

we have

I (ℓ, η_{[g]} = ℓ (g)

. Let

A

be a free basis of

F

and let

ℓ \in F L e n (F)

be realized by a free and discrete isometric action

φ : F \to I s o m (X)

F

on an

R

-tree

X

. Let

μ_{A}

be the uniform measure on

\partial F

corresponding to

A

. The measure

μ_{A}

\partial F

determines a uniform current

ν_{A} \in C u r r (F)

that is analogous to the Liouville current corresponding to a hyperbolic structure on a surface. As shown in [31] , similarly to Bonahon's situation, we have

I (ℓ, ν_{A}) = λ_{A} (φ) .

Generic stretching factors are also related to the notion of the Hausdorff dimension of a measure with respect to a metric. If

μ

is a measure on a metric space

(M, d)

, the Hausdorff dimension of

μ

with respect to

d

, denoted

H D_{d} (μ)

(or just

H D (μ)

), is defined as the infimum of Hausdorff dimensions of subsets of

(M, d)

of full measure

μ

In [28] Kaimanovich proved that for the harmonic measure

ν

\partial T

associated to a regular Markov operator

P

with a positive rate of escape on a tree

T

with uniformly bounded vertex degrees we have

H D (ν) = \frac{h}{c}

where

c

is the rate of escape and

h

is the asymptotic entropy of

P

This result is relevant in our context. Indeed, let

A

be a free basis of

F

and let

φ : F \to I s o m (X)

be a free, discrete and minimal isometric action of

F

on an

R

-tree

X

. Then

X / F

is a finite metric graph and

X

is the universal cover of this graph. Let

Γ (F, A)

denote the Cayley graph of

F

with respect to

A

. The orbit map

w \mapsto w p

(where

p \in X

is a base-point) gives a quasi-isometry between the trees

Γ (F, A)

and

X

which extends to a homeomorphism

\hat{φ} : \partial Γ (F, A) \to \partial X

where

\partial X

is metrized in the standard

C A T (- 1)

way:

d (ζ, ξ) = e^{- d (p, [ζ, ξ])}

for

ζ, ξ \in \partial X

. Let

μ_{A}

be the uniform probability measure on

\partial Γ (F, A) = \partial F

corresponding to

A

and let

μ_{A}^{'}

denote the push-forward of

μ_{A}

via

\hat{φ}

\partial X

Then the result of Kaimanovich [28] mentioned above implies that

H D_{d} (μ_{A}^{'}) = \frac{log (2 k - 1)}{λ_{A} (φ)},

where

k \geq 2

is the rank of

F

1.3 Main results about actions on trees

Our first main result is:

Theorem D. Let

F = F (A)

be a free group of rank

k \geq 2

. Let

φ : F \to A u t (X)

be a free simplicial action without inversion of

F

on a simplicial tree

X

Then the following hold:

(1) The generic stretching factor $λ = λ (φ)$ is a rational number $\geq 1$ with $2 k λ \in Z [\frac{1}{2 k - 1}] .$
(2) The number $λ (φ)$ is algorithmically computable in terms of $φ$ , provided $X$ is the universal cover of a finite connected graph and $φ$ is given by an isomorphism between $F$ and the fundamental group of that graph.

The most interesting case of the above theorem is when

X

is the Cayley graph of

F = F (A)

determined by an endomorphism of

F

Definition 1.4 (Generic stretching factor of an endomorphism). Let

F = F (A)

where

k \geq 2

and

A = {a_{1}, . . ., a_{k}}

. Let

φ : F \to F

be an endomorphism of

F

. Let

X = Γ (F, A)

be the Cayley graph of

F

and consider the action

θ : F \to I s o m (X)

given by

θ (w) x : = φ (w) x

, where

w \in F, x \in X

. The generic stretching factor

λ_{A} (θ)

corresponding to this action is called the generic stretching factor of

φ

with respect to

A

and is denoted

λ_{A} (φ)

or just

λ (φ)

A

is fixed.

Thus

λ (φ)

approximates the distortion

| φ (w) |_{A} / | w |_{A}

for a long random freely reduced word

w

A^{\pm 1}

. For instance, for the Nielsen automorphism

φ \in A u t (F (a, b))

φ (a) = a b, φ (b) = b

it turns out that

λ (φ) = \frac{7}{6}

. If

φ

is an automorphism of

F (a_{1}, . . ., a_{k})

, then the precise relationship between

λ (φ)

and the traditionally studied dynamical properties of

φ

is not very clear. Nevertheless, we are able to estimate the growth of

λ (φ^{n})

for hyperbolic automorphisms. Recall that

φ \in A u t (F)

is hyperbolic if there exist

s > 1

and

m \geq 1

such that for any

w \in F

s | | w | | \leq max {| | φ^{m} (w) | |, | | φ^{- m} (w) | |} .

By a result of Brinkmann [9] an automorphism

φ \in A u t (F)

is hyperbolic if and only if

φ

does not have any nontrivial periodic conjugacy classes in

F

. We prove:

Theorem E. Let

F = F (a_{1}, . . ., a_{k})

and let

φ \in A u t (F)

be a hyperbolic automorphism with parameters

s > 1

and

m \geq 1

as above. Then

{liminf}_{n \to \infty} \sqrt[n]{λ (φ^{n})} \geq s^{1 / m} > 1 .

It is obvious that any automorphism of a finitely generated group

G

equipped with a word metric, is a quasi-isometry and indeed a bi-Lipschitz equivalence.

However, from the geometric point of view, especially in light of various versions of the Marked Length Spectrum Rigidity Conjecture, it is natural to study finer features of quasi-isometries. Recall that a map

f : (X, d) \to (X^{'}, d^{'})

is called a rough isometry if there is

D > 0

such that for any

x, y \in X

we have

| d^{'} (f (x), f (y)) - d (x, y) | \leq D

. A map

f : (X, d) \to (X^{'}, d^{'})

is called a rough similarity if there are

λ > 0

and

D > 0

such that for any

x, y \in X

we have

| d^{'} (f (x), f (y)) - λ d (x, y) | \leq D

It is interesting and natural to ask when an automorphism is a rough similarity or a rough isometry.

An automorphism

φ

F = F (A)

is called a relabelling automorphism if it is induced by a permutation of the set

A = {a_{1}, . . ., a_{k}}^{\pm 1}

. We say that

φ \in A u t (F)

is simple if it is equivalent to a relabeling automorphism in

O u t (F)

, that is, if

φ

is the composition of a relabeling automorphism and a conjugation. Note that being a simple automorphism has a nice geometric meaning. Let

F = F (a_{1}, . . ., a_{k})

be realized as the fundamental group of the metric graph

Γ

which is a bouquet of

k

circles of length

1

corresponding to the generators

a_{1}, . . ., a_{k}

. An automorphism

φ

is simple if and only if, after possibly a composition with an inner automorphism ,

φ

is induced by an isometry of the graph

Γ

Let

P_{n}

be the uniform probability measure on the set of all elements of

F

of length

n

. A set

W \subseteq F

is said to be exponentially

F

-generic if

{lim}_{n \to \infty} P_{n} (W) = 1

and convergence to this limit is exponentially fast. Similarly, a subset

C \subseteq C ℛ

of the set

C ℛ

of all cyclically reduced words is exponentially

C ℛ

-generic if

{lim}_{n \to \infty} P_{n}^{'} (C) = 1

with exponentially fast convergence, where

P_{n}^{'}

is the uniform discrete probability measure on the set of cyclically reduced words of length

n

Obviously, any simple automorphism is a rough isometry and a rough similarity.

The converse is also true, that is, any automorphism which is a rough similarity must be simple. (This follows, for example, from Theorem 2 of [20] together with some standard results about Culler-Vogtmann outer space). Here we obtain a strengthened ”random rigidity” version of this fact:

Theorem F. Let

F = F (a_{1}, . . ., a_{k})

be a free group of rank

k \geq 2

with the standard word metric

d

corresponding to the free basis

{a_{1}, . . ., a_{k}}

. Put

d_{0} : = 1 + \frac{2 k - 3}{4 k^{2} - 2 k}

. There exists an exponentially

C ℛ

-generic set

C \subseteq C ℛ

with the following property.

For any

φ \in A u t (F)

the following conditions are equivalent:

(1) The automorphism $φ$ is simple.
(2) We have $λ (φ) = 1$ .
(3) We have $λ (φ) < 1 + \frac{2 k - 3}{2 k^{2} - k}$ .
(4) The map $φ : (F, d) \to (F, d)$ is a rough isometry.
(5) The map $φ : (F, d) \to (F, d)$ is a rough similarity.
(6) For some $w \in C$ we have $| | φ (w) | | = | | w | |$ .
(7) For every $w \in C$ we have $| | φ (w) | | = | | w | |$ .
(8) For some $w \in C$ we have $| | φ (w) | | \leq d_{0} | | w | |$ .
(9) For every $w \in C$ we have $| | φ (w) | | \leq d_{0} | | w | |$ .

This result shows, in particular, that the set of all possible values of

λ (φ)

(where

φ \in A u t (F)

) has a gap, namely the interval

(1, 1 + \frac{2 k - 3}{2 k^{2} - k})

. Moreover, in the above theorem we can choose

d_{0}

to be any number such that

1 < d_{0} < 1 + \frac{2 k - 3}{2 k^{2} - k}

Theorem F introduces a new dimension for rigidity results related to Marked Length Spectra on hyperbolic groups. Indeed, it is well-known that if

φ \in A u t (F)

fixes the lengths of all conjugacy classes (that is of all cyclic words), then

φ

is a rough isometry of

F

. Theorem F shows that even if

φ \in A u t (F)

preserves the length of a single “random” cyclically reduced word

w

then

φ

is a rough isometry and indeed a simple automorphism. To prove Theorem F we need some rather different tools and ideas, both algebraic and probabilistic. The key ingredient there is the work of Kapovich-Schupp-Shpilrain [35] about the behavior of Whitehead's algorithm and the action of

A u t (F)

on “random” elements of

F

Using Theorem F it is not hard to show that the set of generic stretching factors taken over all free actions of

F (a_{1}, . . ., a_{k})

on simplicial trees also has a gap. Thus we obtain:

Theorem G. Let

F = F (a_{1}, . . ., a_{k})

where

k \geq 2

. Let

φ : F \to A u t (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 $α$ of $F$ such that $X$ is $φ \circ α$ -equivariantly isomorphic to the Cayley graph of $F$ with respect to ${a_{1}, . . ., a_{k}}$ . In this case $λ (φ) = 1$ .
(2) We have $λ (φ) \geq 1 + \frac{1}{k (2 k - 1)}$ .

For an automorphism

φ \in A u t (F)

the conjugacy distortion spectrum of

φ

I (φ) : = {\frac{| | φ (w) | |}{| | w | |} : w \in F - {1}} .

Kapovich proved in [30] that

I (φ)

is always a

Q

-convex subinterval of

Q

(that is, a set closed under taking rational convex combinations) with rational endpoints.

Here we obtain:

Corollary H. Let

φ \in A u t (F)

be an arbitrary automorphism. Then the following hold.

(1) Either $φ$ is simple and $I (φ) = 1$ or, else, $1$ belongs to the interior of $\bar{I (φ)}$ .
(2) There exists $w \in F, w \neq 1$ such that $| | φ (w) | | = | | w | |$ .

Proof. Part (1) obviously implies part (2) since, by the above mentioned result of [30] $I (φ)$ is a $Q$ -convex subset of $Q$ .
To see that (2) holds, assume that $φ$ is not simple. Hence $φ^{- 1}$ is not simple either.
By Theorem F we have $λ (φ) > 1$ and $λ (φ^{- 1}) > 1$ . Part (2b) of Theorem D now implies that there exists $w_{1}, w_{2} \in F, w_{1} \neq 1, w_{2} \neq 1$ such that $x : = \frac{| | φ (w_{1}) | |}{| | w_{1} | |} > 1$ and $y : = \frac{| | φ^{- 1} (w_{2}) | |}{| | w_{2} | |} > 1$ . By definition of $I (φ)$ we have $x \in I (φ)$ . Also, with $u = φ^{- 1} (w_{2})$ we have $y = \frac{| | u | |}{| | φ (u) | |} > 1$ and so $1 / y \in I (φ)$ . Since $x > 1$ and $1 / y < 1$ , the $Q$ -convexity of $I (φ)$ implies that $1$ belongs to the interior of $\bar{I (φ)}$ , as claimed. □

We also obtain an application of Theorem F concerning the notion of the flux of an automorphism that was introduced and studied by Myasnikov and Shpilrain in [40] .

Definition 1.5 (Flux). [40] Let

G

be a finitely generated group with a fixed word metric. Let

φ \in A u t (G)

For each

n \geq 0

define

f l u x_{φ} (n) : = # {g \in G : | g | \leq n, | φ (g) | > n}

and

f l u x (φ) : = limsup \sqrt[n]{\frac{f l u x_{φ} (n)}{# {g \in G : | g | \leq n}}}

The sequence

f l u x_{φ} (n)

and the number

f l u x (φ)

provide a certain dynamical ”measure of activity” of an automorphism

φ

. As a corollary of our results in this paper we obtain:

Corollary I. Let

F = F (a_{1}, . . ., a_{k})

be a free group of rank

k \geq 2

, equipped with the standard metric.

Then for any

φ \in A u t (F)

we have:

f l u x (φ) = {\begin{matrix} 0, & if φ is a relabeling automorphism \\ 1, & otherwise. \end{matrix}

1.4 Random elements in regular languages

By definition, a language

L

over the alphabet

A

is regular if and only if there is a deterministic finite automaton which accepts the language

L

. It is a basic fact of formal language theory that the class of languages accepted by nondeterministic finite automata (NDFA) is also the class of regular languages. (See Hopcroft and Ullman [27] .) Nondeterministic automata are very useful because a NDFA accepting a language

L

may be much smaller than any deterministic automaton accepting

L

Such an automaton is not unique and choosing some finite automaton accepting

L

is like choosing a presentation for a group. One can choose a “random” element in the regular language

L

is via a random walk in the transition graph of any “suitable” finite state automaton

M

accepting the language

L

. We make this precise in Section 8 , where we associate to

M

a finite state Markov process

M^{'}

with the set of states being the set of directed edges in the transition graph

Γ (M)

M

. The sample space

Ω

M^{'}

is the set of semi-infinite edge-paths in

Γ (M)

Each path in

Γ (M)

(finite or infinite) has a label that is a word (finite or infinite) over

A

. If

ω \in Ω

is such an infinite path, we denote by

w_{n} = w_{n} (ω)

the label of the initial segment of length

n

ω

. Any initial probability distribution

μ

on the edge-set

E (Γ (M))

defines a probability measure

P_{μ}

Ω

. We need to impose a natural assumption on

M

in order to guarantee that the Markov process

M^{'}

is irreducible. This technical assumption, which is frequently satisfied in practice, is made precise in the definition of a normal automaton in Section 8 . Again applying the Subadditive Ergodic Theorem, we have:

Theorem J. Let

M

be a normal automaton over a finite alphabet

A

and let

L = L (M)

be the language accepted by

M

Let

φ : A^{*} \to G

be a monoid homomorphism, where

G

is a group with a left-invariant semi-metric

d_{G}

. Then there exists a number

λ = λ (M, φ, d_{G}) \geq 0

such that for any initial distribution

μ

E (Γ (M))

we have

\frac{| φ (w_{n}) |_{G}}{n} \to λ almost surely and in L^{1} with respect to P_{μ} .

If the initial distribution

μ

is supported on the edges of

Γ (M)

originating at the start states of

M

then the word

w_{n}

can be extended by a word of uniformly bounded length to get a word

w_{n}^{'} \in L

. We can think of

w_{n}^{'}

as a ”random” element of

L

with respect to

M

and

μ

. Theorem J then implies that

\frac{| φ (w_{n}^{'}) |_{G}}{n} \to λ

n \to \infty

almost surely and in

L^{1}

with respect to

μ

2 Random words and random walks

Convention 2.1. Let

A = {a_{1}, . . ., a_{k}}

be a free generating set of a free group

F = F (A)

of finite rank

k > 1

. For

w \in F

we denote by

| w |_{A}

or simply

| w |

) the freely reduced length of

w

with respect to

A

. Let

d (w_{1}, w_{2}) = | w_{1}^{- 1} w_{2} |

be the associated left-invariant metric on

F

. By

| | w | |_{A} = | | w | |

we denote the cyclically reduced length of

f

with respect to

A

, that is, the length of any cyclically reduced word in the alphabet

A^{\pm 1}

conjugate to

f

This convention, including the fixed choice of the free basis

A = {a_{1}, . . ., a_{k}}

F

, is adopted for the remainder of the paper, unless specified otherwise.

Recall that a nonnegative function

| \cdot |_{G}

on a group

G

is called a semi-norm if for all

g, h \in G

we have

| g h |_{G} \leq | g |_{G} + | h |_{G}

In this Section we shall prove Theorem A from the Introduction:

Theorem 2.2. Let

F = F (A)

, and let

μ A = μ A (A)

be the uniform Borel probability measure on

\partial F

corresponding to the generating set

A = {a_{1}, . . ., a_{k}}

with

k \geq 2

. Let

φ : F \to G

be a homomorphism to a group

G

endowed with a semi-norm

| \cdot |_{G}

. Then:

(1) There exists a real number $λ \geq 0$ such that ${lim}_{n \to \infty} \frac{| φ (ω_{n}) |_{G}}{n} = λ$ for $μ A$ -a.e. $ω \in \partial F$ and in the space $L^{1} (\partial F, μ A)$ .
(2) If the group $φ (F)$ is non-amenable, the sequence $b_{n} = # {g \in φ (F) : | g |_{G} \leq n}$ grows at most exponentially, then $λ > 0$ .

The condition on

b_{n}

in the above theorem is always satisfied if

G

is a finitely generated group and

| . |_{G}

is the word metric corresponding to some finite generating set of

G

Any geodesic ray

ω \in \partial F

can be identified with the non-backtracking path

ω_{0}, ω_{1}, . . .

F

starting from the group identity. Then the measure space

(\partial F, μ A)

becomes the space of sample paths of the non-backtracking simple random walk (NBSRW) on the Cayley graph of

F

starting from the identity of the group.

This is the Markov chain on

F

whose transition probabilities

π_{f}, f \in F

are equidistributed among the neighbors of

f

which are strictly further from the group identity. Therefore, the number

λ

above is the linear rate of escape of the

φ

-image of the non-backtracking simple random walk on

F

. We shall deduce Theorem 2.2 from well-known analogous properties of the usual random walks on groups by using the fact that the simple random walk on the free group asymptotically follows uniformly distributed geodesic rays.

Let

μ

be a probability measure on a group

G

. By definition, the sample paths of the associated random walk

(G, μ)

are products

g_{n} = h_{1} h_{2} . . . h_{n}

of independent

μ

-distributed increments

h_{n}

. In other words, the measure

P

in the space of sample paths which describes the random walk

(G, μ)

is the image of the product measure

μ \otimes μ \otimes . . .

in the space of increments under the above product map.

The following statement is known as Kingman's Subadditive Ergodic Theorem [36] .

(See also [19] for a short proof.)

Proposition 2.3 (Subadditive Ergodic Theorem). Let

(Ω, ℱ, μ)

be a probability space and let

S : Ω \to Ω

be a measure-preserving operator, that is such that for any measurable set

Q \subseteq Ω

we have

μ (Q) = μ (S^{- 1} Q)

Let

X_{n} : Ω \to R

be a sequence of non-negative integrable random variables such that for any

n, m \geq 0

X_{n + m} (ω) \leq X_{n} (ω) + X_{m} (S^{n} ω), a. e. ω \in Ω .

Then there exists a

S

-invariant random variable

λ : Ω \to R

such that

{lim}_{n \to \infty} \frac{X_{n}}{n} = λ

almost surely and in

L^{1}

Ω

In particular, if

S

is ergodic then

λ = c o n s t

Ω

A straightforward application of Kingman's Subadditive Ergodic Theorem gives:

Proposition 2.4 ([26] ). If the measure

μ

has a finite first moment

\sum | g | μ (g)

with respect to a semi-norm

| \cdot |

on the group

G

, then there exists a number

c \geq 0

(called the linear rate of escape of the random walk

(G, μ)

with respect to the semi-norm

| \cdot |

) such that

| g_{n} | / n \to c

for

P

-a.e. sample path

(g_{n})

and in the space

L^{1} (P)

The following claim, if slightly more general than the one formulated in [26] , can be obtained in the same way by using the spectral characterization of amenability (or by showing that

c = 0

implies vanishing of the asymptotic entropy of the random walk, and therefore amenability of the group [37] ):

Proposition 2.5 ([26] ). Under the assumptions of Proposition 2.4 , if the group

G

is non-amenable and the semi-norm

| \cdot |_{G}

has exponentially bounded growth and the support of the measure

μ

generates the group

G

, then

c > 0

Let now

μ_{A}^{'}

be the probability measure on the free group

F

equidistributed on the set

A^{\pm 1}

, so that

μ_{A}^{'} (a_{i}^{\pm 1}) = 1 / 2 k

for

i = 1, 2, . . ., k

Proposition 2.6 (see [29] and the references therein). For

P

-a.e. sample path

(g_{n})

of the random walk

(F, μ_{A}^{'})

(1) There exists a limit $g_{\infty} = {lim}_{n} g_{n} \in \partial F,$ and its distribution (i.e., the image of the measure $P$ under the map $(g_{n}) \mapsto g_{\infty}$ ) coincides with the uniform measure $μ A$ on $\partial F$ .
(2) We have ${lim}_{n} \frac{| g_{n} |}{n} = θ = \frac{k - 1}{k} .$ (so that the linear rate of escape of the random walk $(F, μ_{A}^{'})$ is $\frac{k - 1}{k}$ ).
(3) We have $d (g_{n}, (g_{\infty})_{[θ n]}) = o (n),$ where $[x]$ denotes the integer part of a number $x$ .

Proof of Theorem 2.2 . Consider the random walk $(F, μ_{A}^{'})$ . Its image under the homomorphism $φ$ is the random walk on the group $φ (F)$ governed by the measure $φ (μ_{A}^{'})$ . Denote its rate of escape with respect to the semi-norm $| \cdot |_{G}$ by $c$ . Then the combination of Proposition 2.4 and Proposition 2.6 implies the first part of Theorem 2.2 . Indeed, for $P$ -a.e. sample path $(g_{n})$ the distance in $F$ between $g_{n}$ and $(g_{\infty})_{[θ n]}$ is sublinear, whence the distance in $G$ (with respect to the semi-metric determined by the semi-norm $| \cdot |_{G}$ ) between the $φ$ -images of these points is also sublinear. Since the distribution of $g_{\infty}$ is $μ A$ , we arrive at the conclusion that the first part of Theorem 2.2 holds for the number $λ = c / θ$ .
The second part of Theorem 2.2 is now an immediate corollary of Proposition 2.5 .
Here is another argument establishing part (1) of Theorem 2.2 as a direct consequence of the Subadditive Ergodic Theorem. Let $Ω = \partial F$ . Recall that for $ω \in \partial F$ we denote by $ω_{n}$ the element of $F$ that is at distance $n$ from $1$ along the geodesic ray $ω$ in $Γ (F, A)$ . Let $X_{n} : \partial F \to R$ be defined as $X_{n} (ω) : = | φ (ω_{n}) |_{G}$ . Also, let $S : \partial F \to \partial F$ be the standard shift operator consisting in erasing the first letter of a semi-infinite freely reduced word representing an element of $\partial F$ . It is well-known that $S$ is stationary and ergodic.
Note that for any $ω \in \partial F$ we have $ω_{n + m} = ω_{n} (S^{n} ω)_{m} .$ Hence $| φ (ω_{n + m}) |_{G} = | φ (ω_{n}) φ ((S^{n} ω)_{m}) |_{G} \leq | φ (ω_{n}) |_{G} + | φ ((S^{n} ω)_{m}) |_{G} .$ Thus the conditions of the Subadditive Ergodic Theorem are satisfied and part (1) of Theorem 2.2 follows. □

The following is Theorem B from the Introduction.

Theorem 2.7. Let

G

be a nontrivial finitely generated group with a word-metric

d_{S}

corresponding to a finite generating set

S

. Let

H \leq A u t (G)

be a noncyclic finitely generated group with a finite generating set

T

. Then:

(1) There is $ν = ν (H) = ν (H, T, S) \geq 0$ such that for a non-backtracking simple random walk $φ_{n}$ on the Cayley graph of $H$ with respect to $T$ we have ${lim}_{n \to \infty} \frac{log | | φ_{n} | |_{S}}{n} = ν$ almost surely and in $L^{1}$ .
(2) If $G$ has polynomial growth and $H$ is non-amenable then $ν (H, T, S) > 0$ .

Proof. It is clear from the definition of $| | \cdot | |_{S}$ that for any $φ, ψ \in A u t (G)$ we have $| | φ ψ | |_{S} \leq | | φ | |_{S} | | ψ | |_{S}$ and hence $log | | φ ψ | |_{S} \leq log | | φ | |_{S} + log | | ψ | |_{S} .$ Also, for any $φ \in A u t (G)$ we have $| | φ | |_{S} \geq 1$ and so $log | | φ | |_{S} \geq 0$ . Thus $log | | \cdot | |_{S}$ is a semi-norm on $A u t (G)$ that uniquely extends to a left-invariant semi-metric of $A u t (G)$ and thus on $H \leq A u t (G)$ . Hence part (1) of Theorem 2.7 follows directly from part (1) of Theorem A .
To see that part (2) holds suppose that $H$ is nonamenable and that $G$ has polynomial growth. This implies that $(H, | | \cdot | |_{S})$ has at most exponential growth.
Hence part (2) of Theorem 2.7 follows from part (2) of Theorem A . □

Remark 2.8. The requirement of

G

having polynomial growth in Theorem B is important and cannot be easily dispensed with. If

G

is a group and

g \in G

, denote by

a d (g) \in A u t (G)

the inner automorphism of

G

defined as

a d (g) (x) = g x g^{- 1}

for every

x \in G

. Now let

G = F (a_{1}, . . ., a_{k})

and

H = I n n (F) \leq A u t (F)

be the (non-amenable!) group of inner automorphisms of

F

with the generating set

T = {a d (a_{1}), . . ., a d (a_{k})}

. Then for any product

φ_{n}

n

elements of

T

we have

| | φ_{n} | | \leq 2 n + 1

. Since

{lim}_{n \to \infty} \frac{log 2 n + 1}{n} = 0

, we see that

ν (H, T, S) = 0

. Nevertheless, in some instances quotient group considerations still imply that

ν (A) > 0

even if

G

does not have polynomial growth, or, equivalently,

G

is not virtually nilpotent.

We obtain Corollary C from the Introduction:

Corollary 2.9. Let

F

be a free group of finite rank

k > 1

and let

H \leq A u t (F)

be a finitely generated group of automorphisms of

F

such that the image

H^{'}

H

A u t (F_{a b}) \sim = G L (k, Z)

is nonamenable. Then for any finite generating set

S

F

and for any finite generating set

T

H

we have

ν (H, T, S) > 0

Proof. Let $S^{'}$ be the image of $S$ in the abelianization $Z^{k} = F_{a b}$ of $F$ . For any $φ \in A u t (F)$ the automorphism $φ$ of $F$ factors through to an automorphism $φ^{'}$ of $F_{a b}$ . Clearly $| | φ | |_{S} \geq | | φ^{'} | |_{S^{'}}$ . Hence $ν (H, T, S) \geq ν (H^{'}, T^{'}, S^{'})$ , where $T^{'}$ is the image of $T$ in $A u t (F_{a b})$ . Since $F_{a b}$ has polynomial growth, by Theorem B we have $ν (H^{'}, T^{'}, S^{'}) > 0$ and hence $ν (H, T, S) > 0$ . □

3 Frequencies and cyclic words

The following convention is fixed until the end of the paper unless specified otherwise.

Convention 3.1. As before, let

k \geq 2

and let

F = F (A)

where

A = {a_{1}, . . ., a_{k}}

. Let

\hat{A} = A^{\pm 1}

. We denote by

C ℛ

the set of all cyclically reduced words in

F

A cyclic word is an equivalence class of nontrivial cyclically reduced words, where two nontrivial cyclically reduced words are equivalent if they are cyclic permutations of each other. If

v

is a cyclically reduced word, we denote by

(v)

the cyclic word defined by

v

. Recall that if

u

is a freely reduced word, we denote the length of

u

| u |

and the length of the cyclically reduced form of

u

| | u | |

. If

w = (v)

is a cyclic word then

| | w | | = | | v | |

is the length of

w

Note that the set of cyclic words is naturally identified with the set of nontrivial conjugacy classes of elements of

F

Definition 3.2 (Frequencies). Let

w

be a cyclic word.

Let

v

be a nontrivial freely reduced word. We define

n_{w} (v)

, the number of occurrences of

v

w

as follows. Let

w = (z)

. Take the smallest

p > 0

such that

| z^{p - 1} | \geq 2 | v |

and count the number of those

i, 0 \leq i < | | w | |

such that

z^{p} \equiv z_{1} v z_{2}

where

| z_{1} | = i

. This number by definition is

n_{w} (v)

. If

v = 1

, we define

n_{w} (1) : = | | w | |

There is a more graphical way of defining

n_{w} (v)

for a nontrivial cyclic word

w

. We will think of

w

as a cyclically reduced word written on a circle in a clockwise direction without specifying a base-point. Then

n_{w} (v)

is the number of positions on the circle, starting from which it is possible to read the word

v

going clockwise along the circle (and wrapping around more than once, if necessary).

For any freely reduced word

v

we define frequency of

v

w

as:

f_{w} (v) : = \frac{n_{w} (v)}{| | w | |} .

Also, if

w

is a nontrivial freely reduced word, and

v

is another nontrivial freely reduced word, we define

n_{w} (v)

, the number of occurrences of

v

w

, as follows. If

| w | = n > 0

then by definition

n_{w} (v)

is the number of those

i, 0 \leq i < n

for which

w

decomposes as a freely reduced product

w = w^{'} v w^{''}

with

| w^{'} | = i

. Thus if

| v | \leq | w |

then necessarily

n_{w} (v) = 0

(unlike the situation when

w

is a cyclic word).

Lemma 3.3. Let

w

be a nontrivial cyclic word. Then:

(1) For any $m \geq 0$ and for any freely reduced word $u$ with $| u | = m$ we have: $n_{w} (u) = \sum_{x \in \hat{A}, | u x | = | u | + 1} n_{w} (u x) = \sum_{x \in \hat{A}, | x u | = | u | + 1} n_{w} (x u),$ and $f_{w} (u) = \sum_{x \in \hat{A}, | u x | = | u | + 1} f_{w} (u x) = \sum_{x \in \hat{A}, | x u | = | u | + 1} f_{w} (x u) .$
(2) For any $m \geq 1$ $\sum_{| u | = m} n_{w} (u) = | | w | | and \sum_{| u | = m} f_{w} (u) = 1 .$
(3) For any $s > 0$ and any $u \in F$ $n_{w^{s}} (u) = s n_{w} (u) and f_{w^{s}} (u) = f_{w} (u) .$

Proof. Parts (1) and (3) are obvious. We establish (2) by induction on $m$ . For $m = 1$ the statement is clear. Suppose that $m > 1$ and that (2) has been established for $m - 1$ .
We have: $\sum_{| u | = m} n_{w} (u) = \sum_{| v x | = m | v | = m - 1, x \in \hat{A} :} n_{w} (v x) = \sum_{| v | = m - 1} n_{w} (v) = | | w | |,$ as required.
□

Definition 3.4 (Nielsen automorphisms). A Nielsen automorphism of

F

is an automorphism

τ

of one of the following types:

(1) There is some $i, 1 \leq i \leq k$ such that $τ (a_{i}) = a_{i}^{- 1}$ and $τ (a_{j}) = a_{j}$ for all $j \neq i$ .
(2) There are some $1 \leq i < j \leq k$ such that $τ (a_{i}) = a_{j}$ , $τ (a_{j}) = a_{i}$ and $τ (a_{l}) = a_{l}$ when $l \neq i, l \neq j$ .
(3) There are some $1 \leq i < j \leq k$ such that $τ (a_{i}) = a_{i} a_{j}$ and $τ (a_{l}) = a_{l}$ for $l \neq i$ .

It is a classical fact that the set of all Nielsen automorphisms generates

A u t (F)

The following proposition proved by Kapovich in [30] is crucial for our arguments.

Proposition 3.5. Let

φ \in O u t (F)

be an outer automorphism and let

p \geq 0

be such that

φ

can be represented, modulo

I n n (F)

, as a product of

p

Nielsen automorphisms.

Then for any freely reduced word

v \in F

with

| v | = m

there exists a collection of computable integers

c (u, v) = c (u, v, φ) \geq 0

, where

u \in F

| u | = 8^{p} m

, such that for any nontrivial cyclic word

w

we have

n_{φ (w)} (v) = \sum_{| u | = 8^{p} m} c (u, v) n_{w} (u) .

Corollary 3.6. Let

φ

be an automorphism of

F

and let

p

be such that

φ

can be written as a product of

p

Nielsen automorphisms.

There exists a collection of integers

e (v) = e (v, φ) \geq 0

, where

v \in F, | v | = 8^{p}

, such that for any cyclic word

w

we have:

| | φ (w) | | = \sum_{| v | = 8^{p}} e (v) n_{w} (v)

and

\frac{| | φ (w) | |}{| | w | |} = \sum_{| v | = 8^{p}} e (v) f_{w} (v) .

Moreover, there is an algorithm which, given

φ

and

u

, computes the numbers

e (v)

Proof. Since $| | φ (w) | | = \sum_{x \in \hat{A}} n_{φ (w)} (x)$ , the statement follows directly from Proposition 3.5 .
□

The following well-known fact is a version of the so-called “Bounded Cancellation Lemma” (see [16] ):

Lemma 3.7. Let

α

be an injective endomorphism of

F

. There is

N = N (α) > 0

such that for any cyclically reduced word

w

the maximal terminal segment of

α (w)

that cancels in the product

α (w) \cdot α (w)

has length at most

N

4 Actions on trees

Let

Γ

be a finite connected graph with orientation

E Γ = E^{+} Γ ⊔ E^{-} Γ

. For

e \in E

we use the following notation. The inverse edge of

e

is denoted by

\bar{e}

o (e)

denotes the initial vertex of

e

and

t (e)

denotes the terminal vertex of

e

Let

F

be a free group and let

φ : F \to π_{1} (Γ, p)

be an isomorphism between

F

and the fundamental group of

Γ

with respect to a vertex

p

. Let

T

be a maximal tree in

Γ

. For any vertex

v

, let

[p, v]_{T}

denote the path in

T

from

p

v

. The choice of

T

define a basis

S_{T}

π_{1} (Γ, p)

as follows:

S_{T} : = {[p, o (e)]_{T} e [t (e), p]_{T} : e \in E^{+} (Γ - T)}

The

φ

-pullback of this basis

B_{T} : = φ^{- 1} (S_{T})

is a basis of

F

referred to as the geometric basis of

F

determined by

T

Let

s_{e} : = [p, o (e)]_{T} e [t (e), p]_{T}

where

e \in E (Γ - T)

, so that

s_{\bar{e}} = s_{e}^{- 1}

. Let

b_{e} = φ^{- 1} (s_{e})

, where

e \in E (Γ - T)

, so that again

b_{\bar{e}} = b_{e}^{- 1}

The following obvious lemma indicates the explicit correspondence between freely reduced words in

S_{T}

(or

B_{T}

) and reduced edge-paths in

Γ

Lemma 4.1.

(1) Let $γ$ be an edge-path in $Γ$ from $p$ to $p$ . Let $u$ be a word in $S_{T}$ constructed from $γ$ as follows: delete all the edges of $T$ from $Γ$ and replace each edge $e \in E^{+} (Γ - T)$ in $γ$ by $s_{e}$ and each edge $e \in E^{-} (Γ - T)$ in $γ$ by $s_{\bar{e}}^{- 1}$ . Then $u = γ$ in $π_{1} (Γ, p)$ and $u$ is a reduced word in $S_{T}$ if and only if $γ$ is a reduced path. x
(2) Let $u$ be a word in $S_{T} \cup S_{T}^{- 1}$ , where $ε_{i} = \pm 1$ .
Construct the path $γ$ from $p$ to $p$ as follows. First for each $e \in E^{+} (Γ - T)$ replace every $s_{e}$ in $u$ by $e$ and replace every $s_{e}^{- 1}$ by $\bar{e}$ . Then between every two consecutive $e, e^{'}$ insert the path $[t (e), o (e^{'})]_{T}$ . Finally append the path $[p, o (e)]_{T}$ in front, for the first edge $e_{0} \in E (Γ - T)$ of the resulting sequence, and append the path $[t (e_{0}^{'}), p]_{T}$ at the end for the last edge $e_{0}^{'} \in E (Γ - T)$ of the sequence.
Then $γ$ is a path from $p$ to $p$ that is equal to $u$ in $π_{1} (Γ, p)$ and that is reduced if and only if the word $u$ over $S_{T}$ is reduced.
(3) Let $γ$ be a closed edge-path in $Γ$ . Let $u$ be a word in $S_{T}^{\pm 1}$ obtained from $γ$ as in (1). Then the loop at $p$ corresponding to $u$ in $π_{1} (Γ, p)$ is freely homotopic to $γ$ in $Γ$ and the word $u$ is cyclically reduced if and only if the path $γ$ is cyclically reduced.
(4) Let $w$ be a cyclic word in $S_{T}^{\pm 1}$ . Let $γ$ be a circuit in $Γ$ obtained as follows. Replace each occurrence of $s_{e}$ in $w$ by $e$ and each occurrence of $s_{e}^{- 1}$ by $\bar{e}$ ; after that between each two consecutive (in the cyclic order) edges $e, e^{'}$ insert the path $[t (e), o (e^{'})]_{T}$ . Then $w$ and $γ$ represent freely homotopic loops in $Γ$ and the cyclic word $w$ is reduced if and only if the circuit $γ$ is reduced.

Now suppose that

Γ

is endowed with the structure of a metric graph, that is, each edge

e

Γ

is assigned a length

ℓ (e) > 0

in such a way that

ℓ (e) = ℓ (\bar{e})

for each edge

e

. Let

X = \tilde{(Γ, p)}

be the universal cover of

Γ

. Then

X

inherits the structure of a metric tree with an isometric action of

π_{1} (Γ, p)

and, via

φ

, an action of

F

X

. Let

\tilde{p}

be a lift of

p

X

. For

g \in π_{1} (Γ, p)

let

| g |_{p} : = d_{X} (\tilde{p}, g \tilde{p})

. Also denote by

| | g | |_{X}

the translation length of

g

when acting on

X

. Similarly, if

w

is a conjugacy class (or a cyclic word) in

π_{1} (Γ, p)

, we denote by

| | w | |_{X}

the translation length of

u

with respect to

X

. For each freely reduced word

z = s_{e}^{ε} s_{e^{'}}^{δ}

of length two in

S_{T}^{\pm 1}

, where

ε, δ \in {1, - 1}

, denote by

r_{z}

the length of the edge-path

[t (e^{ε}), o ({e^{'}}^{δ})]_{T}

Γ

. Let

Z

be the set of all freely reduced words of length two in

S_{T}

. For each

a = s_{e} \in S_{T}

denote

e (a) : =

and

e (a^{- 1}) : = \bar{e}

Lemma 4.2. (1) Let

w

be a reduced cyclic word in

S_{T}^{\pm 1}

. Then

| | w | |_{X} = \sum_{a \in S_{T}^{\pm 1}} ℓ (e (a)) n_{w} (a) + \sum_{z \in Z} r_{z} n_{w} (z) .

(2) Let

u

be a freely reduced word in

S_{T}

. Then

| u |_{p} = \sum_{a \in S_{T}^{\pm 1}} ℓ (e (a)) n_{u} (a) + \sum_{z \in Z} r_{z} n_{u} (z) + ℓ ([p, o (e)]_{T}) + ℓ ([t (e^{'}), p]_{T})

where

e

and

e^{'}

are the last and the first edges of

γ (u)

accordingly.

The following is Theorem D from the Introduction:

Theorem 4.3. Let

F = F (a_{1}, . . ., a_{k})

, where

k \geq 2

, and let

A = {a_{1}, . . ., a_{k}}

. Then for any free action

φ

F

on a simplicial tree

X

without inversions the generic stretching factor

λ (φ) = λ_{A} (φ)

is a rational number with

2 k λ (φ) \in Z [\frac{1}{2 k - 1}] .

Moreover, if

X

is given as the universal cover of a finite connected simplicial graph

Γ

and if the action

φ

is given via an explicit isomorphism between

F

and

π_{1} (Γ, p)

, then

λ (φ)

is algorithmically computable in terms of

φ

Proof. Recall that the definition of $λ (φ, | \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 $Γ = X / F$ be the finite quotient graph. Choose an orientation on $Γ$ , a maximal tree $T$ in $Γ$ . Choose a base-vertex $p$ in $Γ$ to be the image of $x \in X$ in $Γ$ . Note that in both $X$ and $Γ$ every edge has length $1$ . Then there is a canonical isomorphism $ψ : F \to π_{1} (Γ, p)$ . Let $S_{T}$ and $B_{T}$ be the geometric bases corresponding to $T$ for $π_{1} (Γ, p)$ and $F$ accordingly.
Fix a bijection between $B_{T}$ and $A = {a_{1}, . . ., a_{k}}$ and an automorphism $α$ 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^{'}$ be a cyclically reduced word of length $n$ over $A$ obtained from $g$ by changing the last letter of $g$ if necessary. Thus $| g^{'} g^{- 1} |_{A} \leq 2$ .
Let $w^{'}$ be the cyclic word over $A$ defined by $g^{'}$ . Let $w$ be the result of rewriting $w^{'}$ as the cyclic word in $B_{T}$ . Then there is an integer $M \geq 1$ such that for each freely reduced word $z$ in $B_{T}$ of length at most $2$ $n_{w} (z) = \sum_{| u |_{A} = M} c (u, z) n_{w} (u)$ where $c (u, z) \geq 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
$| | g^{'} | |_{X} = | | w | |_{X} = \sum_{a \in Z_{1}} ℓ (e (a)) n_{w} (a) + \sum_{z \in Z_{2}} r_{z} n_{w} (z) = \sum_{a \in Z_{1}} \sum_{| u |_{A} = M} ℓ (a) c (u, a) n_{w^{'}} (u) + \sum_{z \in Z_{2}} \sum_{| u |_{A} = M} r_{z} c (u, z) n_{w^{'}} (u),$
It follows from Lemma 4.1 and Lemma 4.2 that if $h \in F$ is cyclically reduced over $B_{T}$ then $| | | h | |_{X} - | h |_{x} | \leq N$ where $N = N (x) > 0$ is some constant independent of $h$ . On the other hand by the Bounded Cancellation Lemma ( Lemma 3.7 ) there exists a constant $N^{'} > 0$ such that for any cyclically reduced word $y$ over $A$ , we have $| | | y | |_{B_{T}} - | y |_{B_{T}} | \leq N^{'}$ . By construction $g^{'}$ is cyclically reduced over $A$ and $| g^{'} g^{- 1} |_{A} \leq 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 $| | g |_{x} - | | g^{'} | |_{X} | \leq L$ and $| n_{g} (u) - n_{w^{'}} (u) | \leq L$ .
Therefore there is another constant $L^{'} > 0$ independent of $f$ such that for every freely reduced word $g$ of length $n$ over $A$ $| \sum_{a \in Z_{1}} \sum_{| u |_{A} = M} ℓ (e (a)) c (u, a) f_{g} (u) + \sum_{z \in Z_{2}} \sum_{| u |_{A} = M} r_{z} c (u, z) f_{g} (u) - \frac{| g |_{p}}{n} | \leq \frac{L^{'}}{n} .$ If $g_{n}$ is a freely reduced word of length $n$ obtained by a non-backtracking 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}} (u) = \frac{1}{2 k (2 k - 1)^{M - 1}} almost surely.$ Therefore (*) implies that $λ (φ) = \frac{1}{2 k (2 k - 1)^{M - 1}} [\sum_{a \in Z_{1}} \sum_{| u |_{A} = M} ℓ (e (a)) c (u, a) + \sum_{z \in Z_{2}} \sum_{| u |_{A} = M} r_{z} c (u, z)]$ Since $ℓ (e (a)) = 1, c (u, a), c (u, z)$ and $r_{z}$ are integers, it follows that $λ (φ)$ is rational and, moreover, that $2 k λ (φ) \in Z [\frac{1}{2 k - 1}] .$ Moreover, $λ (φ)$ is computable in terms of an explicit isomorphism between $F$ and $π_{1} (Γ, p)$ . □

Remark 4.4. The formula (**) for

λ (φ)

holds for an arbitrary structure of a metric graph on

Γ

, where the lengths of edges are allowed to be arbitrary positive real numbers and not necessarily

1

. If the length of all edges of

Γ

are rational, then by (**)

λ (φ)

is also rational. Moreover, if these length of the edges are given to us in some algorithmically describable form then

λ (φ)

is computable in terms of these lengths and of an an explicit isomorphism between

F

and

π_{1} (Γ, p)

5 Genericity

Convention 5.1. Recall that

C ℛ

denotes the set of all cyclically reduced words in

F = F (a_{1}, . . ., a_{k})

. If

S \subseteq F

and

n \geq 0

we denote

ρ (S, n) : = # {w \in S : | w | \leq n},

and

γ (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

| w | = n

. We extend

P_{n}

F

by setting

P_{n} (w) = 0

for any

w \in F

with

| w | \neq n

Similarly, let

P_{n}^{'}

be the uniform discrete probability measure on the set of all cyclically reduced elements

w \in F

with

| | w | | = n

. We extend

P_{n}

C ℛ

by setting

P_{n}^{'} (w) = 0

for any

w \in C ℛ

with

| | w | | \neq n

Thus

γ (n, F) = 2 k (2 k - 1)^{n - 1}

for

n > 0

For a number sequence

x_{n}

with

{lim}_{n \to \infty} x_{n} = x \in R

we say that the convergence is exponentially fast if there exist

0 < σ < 1

and

D > 0

such that for all

n \geq 1

we have

| x_{n} - x | \leq D σ^{n}

Definition 5.2 (Genericity). Let

S \subseteq W \subseteq F

. We say that

S

is exponentially

W

-generic if

{lim}_{n \to \infty} \frac{γ (n, S)}{γ (n, W)} = 1

and the convergence is exponentially fast. The complement in

W

of an exponentially

W

-generic set is called exponentially

W

-negligible.

In practice we are only interested in the cases

W = F

and

W = C ℛ

, 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} (S) = 1

with exponentially fast convergence in this limit. Similarly

S \subseteq C ℛ

is exponentially

C ℛ

-generic iff

{lim}_{n \to \infty} P_{n}^{'} (S) = 1

with exponentially fast convergence. Here there is a simple criterion of being exponentially negligible [35] in

F

and

C ℛ

Lemma 5.3. Let

W = F

W = C ℛ

. Then for a subset

S \subseteq W

the following are equivalent:

(1) The set $S$ is exponentially $W$ -negligible.
(2) We have $\frac{γ (n, S)}{(2 k - 1)^{n}} \to_{n \to \infty} 0 exponentially fast,$
(3) We have $\frac{ρ (n, S)}{(2 k - 1)^{n}} \to_{n \to \infty} 0 exponentially fast,$
(4) We have ${limsup}_{n \to \infty} \sqrt[n]{ρ (n, S)} < 2 k - 1 .$
(5) We have ${limsup}_{n \to \infty} \sqrt[n]{γ (n, S)} < 2 k - 1 .$

Proposition 5.4. Let

ε > 0

and let

m > 0

be an integer. Then the set

\begin{matrix} W (m, ε) : = { & w \in F : for any u \neq 1 with | u | = m we have \end{matrix}

\begin{matrix} | f_{w} (u) - \frac{1}{2 k (2 k - 1)^{m - 1}} | < ε} \end{matrix}

\begin{matrix}  \end{matrix}

is exponentially

F

-generic.

Proof. This is a straightforward corollary of Large Deviation Theory [18] applied to the finite state Markov chain generating the freely reduced words in $F$ . We refer the reader to [35] for a more detailed discussion about large Deviation Theory and how it works in this particular case. □

It is not hard to deduce the following from Proposition 5.4 .

Proposition 5.5. Let

ε > 0

and let

m > 0

be an integer. Then the set

\begin{matrix} C (m, ε) : = { & w \in C ℛ : for any u \neq 1 with | u | = m and for the cyclic word (w) \end{matrix}

\begin{matrix} we have | f_{(w)} (u) - \frac{1}{2 k (2 k - 1)^{m - 1}} | < ε} \end{matrix}

\begin{matrix}  \end{matrix}

is exponentially

C ℛ

-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.

Definition 5.6. Let

φ : F \to A u t (X)

be a free simplicial action without inversions of

F = F (a_{1}, . . ., a_{k})

on a simplicial tree

X

We say that a number

λ \geq 0

is a approximate stretching factor of

φ

if for every

p \in X

and for any

ε > 0

the set

{w \in F : | \frac{| w |_{p}}{| w |} - λ | \leq ε}

is exponentially generic in

F

Similarly, we say that a number

λ \geq 0

is a approximate conjugacy stretching factor of

φ

if for any

ε > 0

the set

{w \in C ℛ : | \frac{| | w | |_{X}}{| | w | |} - λ | \leq ε}

is exponentially generic in

C ℛ

Proposition 5.7. Let

φ : F \to A u t (X)

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 $φ$ .
(2) There is at most one approximate conjugacy stretching factor for $φ$ .
(3) If $λ$ is an approximate conjugacy stretching factor for $φ$ then $λ$ is also an approximate stretching factor for $φ$ .
(4) If $λ$ is an approximate stretching factor for $φ$ then $λ$ is also an approximate conjugacy stretching factor for $φ$ .

Proof. Parts (1) and (2) are obvious.
We now establish (3). Indeed, suppose that $λ$ is an approximate conjugacy stretching factor for $φ$ . Let $ε > 0$ and let $S$ be the set of all cyclically reduced words $w$ such that $| \frac{| | w | |_{X}}{| | w | |} - λ | \geq ε / 2$ . Then $S$ is exponentially $C ℛ$ -negligible, so that $\frac{γ (n, S)}{(2 k - 1)^{n}} \to_{n \to \infty} 0$ exponentially fast. Let $p \in X$ . Put $M = max {| a_{i} |_{p} : 1 \leq i \leq k}$ . Let $N > 0$ be an integer such that for any cyclically reduced word $u$ we have $| | u |_{p} - | | u | |_{X} | \leq N$ .
Let $S^{'}$ 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 $γ (n, S^{'}) \leq 2 k γ (n, S)$ and hence $S^{'}$ is exponentially $F$ -negligible by Lemma 5.3 .
Suppose $w \in F - S^{'}$ is such that $\frac{N + 2 M}{| w |} < \frac{ε}{2}$ . Let $u$ be a cyclically reduced word obtained from $w$ by changing at most the last letter. Then $| u | = | w |$ and $u \in C ℛ - S$ .
Thus $d_{A} (w, u) \leq 2$ and hence $d_{X} (w p, u p) \leq 2 M$ . Thus $| | u |_{p} - | w |_{p} | \leq 2 M$ . Also $| | | u | |_{X} - | u |_{p} | \leq N$ . Therefore $| | | u | |_{X} - | w |_{p} | \leq N + 2 M$ . Since $u \in C ℛ - S$ , we have $| | | u | |_{X} - λ | | u | | | < ε | | u | |$ . Since $| | u | | = | u | = | w |$ , we have:
$| | w |_{p} - λ | w | | < ε | w | + N + 2 M | \frac{| w |_{p}}{| w |} - λ | < \frac{ε}{2} + \frac{N + 2 M}{| w |} < ε .$
The set ${w \in F : \frac{N + 2 M}{| w |} \geq \frac{ε}{2}}$ is finite. Hence $S^{'} \cup {w \in F : \frac{N + 2 M}{| w |} \geq \frac{ε}{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

φ : F \to A u t (X)

be a free simplicial action of

F = F (a_{1}, . . ., a_{k})

on a simplicial tree

X

Then the generic stretching factor

λ (φ)

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

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

| \sum_{a \in Z_{1}} \sum_{| u |_{A} = M} c (u, a) f_{w} (u) + \sum_{z \in Z_{2}} \sum_{| u |_{A} = M} r_{z} c (u, z) f_{w} (u) - \frac{| g |_{p}}{n} | \leq \frac{L^{'}}{n} .

It follows from Lemma 4.1 and Lemma 4.2 that if

w \in F

is cyclically reduced over

B_{T}

then

| | | w | |_{X} - | w |_{x} | \leq N

where

N = N (x) > 0

is some constant independent of

w

. On the other hand by the Bounded Cancellation Lemma ( Lemma 3.7 ) there exists a constant

N^{'} > 0

such that for any cyclically reduced word

w

over

A

, we have

| | | w | |_{B_{T}} - | w |_{B_{T}} | \leq N^{'}

. Hence for any cyclically reduced word

w

over

A

we have

| | | w | |_{X} - | w |_{x} | \leq N^{''}

where

N^{''} = N^{''} (x) > 0

is some constant independent of

w

Therefore for any cyclically reduced

w \in F

over

A

with

| | w | | = n

| \sum_{a \in Z_{1}} \sum_{| u |_{A} = M} c (u, a) f_{w} (u) + \sum_{z \in Z_{2}} \sum_{| u |_{A} = M} r_{z} c (u, z) f_{w} (u) - \frac{| | w | |_{X}}{n} | \leq \frac{L^{'} + N}{n} .

Let

ε > 0

We know that the set

\begin{matrix} C (M, ε) : = { & w \in C ℛ : for any u \neq 1 with | u | = M and for the cyclic word (w) \end{matrix}

\begin{matrix} we have | f_{(w)} (u) - \frac{1}{2 k (2 k - 1)^{M - 1}} | < ε} \end{matrix}

\begin{matrix}  \end{matrix}

is exponentially

C ℛ

-generic.

Hence (*) implies that for any

w \in C (M, ε)

| \frac{1}{2 k (2 k - 1)^{M - 1}} (\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)) - \frac{| | w | |_{X}}{n} | \leq \frac{N_{1}}{n} + N_{1} ε .

for some constant

N_{1} > 0

independent of

w

and

ε

Thus by definition the number

\frac{1}{2 k (2 k - 1)^{M - 1}} (\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))

is an approximate conjugacy stretching factor for

φ

. In the proof of Theorem 4.3 we obtained the same formula for

λ (φ)

. □

Lemma 5.9. Let

F = F (a_{1}, . . ., a_{k})

and let

φ : F \to A u t (X)

be a free simplicial action of

F = F (a_{1}, . . ., a_{k})

on a simplicial tree

X

. Let

μ \geq 0

Suppose there exists an exponentially

C ℛ

-generic set

S

such that for any

w \in S

\frac{| | w | |_{X}}{| | w | |} \geq μ .

Then

λ (φ) \geq μ

Proof. Suppose, on the contrary, that $λ (φ) < μ$ . Choose $ε > 0$ such that $λ (φ) + ε < μ$ .
Then there is an exponentially $C ℛ$ -generic set $R$ of cyclically reduced words such that for any $w \in R$ $\frac{| | w | |_{X}}{| | w | |} \leq λ + ε .$ The intersection $S \cap R$ is exponentially $C ℛ$ -generic and hence nonempty. Take $w \in S \cap R$ .
Then $μ \leq \frac{| | w | |_{X}}{| | w | |} \leq λ + ε < μ,$ 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

τ

F

of one of the following two types:

(1) There is a permutation

t

\hat{A}

such that

τ |_{\hat{A}} = t

. In this case

τ

is called a relabeling automorphism or a Whitehead automorphism of the first kind.

(2) There is an element

a \in \hat{A}

, the multiplier, such that for any

x \in \hat{A}

τ (x) \in {x, x a, a^{- 1} x, a^{- 1} x a} .

In this case we say that

τ

is a Whitehead automorphism of the second kind. (Note that we always have

τ (a) = a

in this case since

τ

is an automorphism of

F

.) To every such

τ

we associate a pair

(S, a)

where

a

is as above and

S

consists of all those elements of

\hat{A}

, including

a

but excluding

a^{- 1}

, such that

τ (x) \in {x a, a^{- 1} x a}

. We will say that

(S, a)

is the characteristic pair of

τ

Note that for any

a \in \hat{A}

the inner automorphism

a d (a)

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

| | u | | \leq | | v | |

and let

φ \in A u t (F)

be such that

φ (u) = v

. Then we can write

φ

as a product of Whitehead moves

φ = τ_{p} . . . τ_{1}

so that for each

i = 1, . . ., p

| | τ_{i} . . . τ_{1} (u) | | \leq | | v | | .

Moreover, if

| | u | | < | | v | |

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

{\hat{A}}^{*}

. The weighted Whitehead graph

Γ_{w}

w

is defined as follows. Let

(w)

be the cyclic word defined by

w

. The vertex set of

Γ_{w}

\hat{A}

. For every

x, y \in \hat{A}

such that

x \neq y^{- 1}

there is an undirected edge in

Γ_{w}

from

x^{- 1}

y

labeled by the sum

{\hat{n}}_{w} (x y) : = n_{(w)} (x y) + n_{(w)} (y^{- 1} x^{- 1})

There are

k (2 k - 1)

undirected edges in

Γ_{w}

. Edges may have label zero, but there are no edges from

a

a

for

a \in \hat{A}

. It is easy to see that we have

Γ_{w} = Γ_{v}

for any cyclic permutation

v

w

w^{- 1}

Convention 6.4. Let

w

be a fixed nontrivial cyclically reduced word.

For two subsets

X, Y \subseteq \hat{A}

we denote by

X . Y

the sum of all edge-labels in the weighted Whitehead graph

Γ_{w}

w

of edges from elements of

X

to elements of

Y

. Thus for

x \in \hat{A}

the number

x . \hat{A}

is equal to

n_{w} (x) + n_{w} (x^{- 1})

, the total number of occurrences of

x^{\pm 1}

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

τ (w)

, where

τ

is a Whitehead automorphism.

Lemma 6.5. Let

w

be a nontrivial cyclically reduced word and let

τ

be a Whitehead automorphism of the second kind with the characteristic pair

(S, a)

. Let

S^{'} = \hat{A} - S

. Then

| | τ (w) | | - | | w | | = S . S^{'} - a . \hat{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

F

is strictly minimal if for every non-inner Whitehead automorphism

τ

F

of the second kind we have

| | τ (w) | | > | | w | | .

The set of all strictly minimal elements in

F

is denoted

S M

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

A u t (F)

-orbit and for any

φ \in A u t (F)

we have:

| w | = | | w | | \leq | | φ (w) | | \leq | φ (w) | .

Theorem 6.8. Put

c_{0} : = 1 + \frac{2 k - 3}{4 k^{2} - 2 k}

. There exists an exponentially

F

-generic set

W \subseteq F

with the following property.

For any

φ \in A u t (F)

the following conditions are equivalent:

(1) The automorphism $φ$ is simple.
(2) We have $λ (φ) = 1 .$
(3) We have $λ (φ) < 1 + \frac{2 k - 3}{2 k^{2} - k} .$
(4) For some $w \in W$ we have $| | φ (w) | | = | | w | |$ .
(5) For every $w \in W$ we have $| | φ (w) | | = | | w | |$ .
(6) For some $w \in W$ we have $| | φ (w) | | \leq c_{0} | | w | |$ .
(7) For every $w \in W$ we have $| | φ (w) | | \leq c_{0} | | w | |$ .

Proof. It is obvious that (1) implies (2) and that (2) implies (3).
We will now prove that (3) implies (1).
Let φ ∈ A u t ( F ) .
Let ε > 0 be arbitrary. Put T ( ε ) be the set of all cyclically reduced words w such that:
- $∙$ For any $x \in \hat{A}$ $| f_{w} (x) - \frac{1}{2 k} | \leq ε / 2$ .
- $∙$ For any $x, y \in \hat{A}$ with $x \neq y^{- 1}$ $| f_{w} (x y) - \frac{1}{2 k (2 k - 1)} | \leq ε / 2$
Then T ( ε ) is exponentially C ℛ -generic [35] . Moreover, every w ∈ T ( ε ) is strictly minimal [35] , provided that ε < 2 k − 3 k ( 2 k − 1 ) ( 4 k − 3 ) . Suppose now that ε < ε 0 : = 2 k − 3 k ( 2 k − 1 ) ( 4 k − 3 ) . Choose an arbitrary element w ∈ T ( ε ) and denote n = | | w | | .
By strict minimality of w we have | | w | | ≤ | | φ ( w ) | | . Moreover, by Proposition 6.2 (Peak Reduction Lemma) there is a decomposition φ = τ p τ p − 1 . . . τ 1 such that each τ i is a Whitehead move and for each i = 1 , . . . , p − 1 | | τ i τ i − 1 . . . τ 1 ( w ) | | ≤ | | φ ( w ) | | with strict inequalities unless | | w | | = | | φ ( w ) | | .
Suppose first that | | w | | = | | φ ( w ) | | . Then all inequalities above are equalities and by strict minimality of w each τ i is either inner or a relabeling automorphism. This implies that φ = α τ where α is inner and τ is a relabeling automorphism and that λ ( φ ) = 1 .
Suppose now that | | w | | < | | φ ( w ) | | . Then the preceding argument shows that in fact for any z ∈ T ( ε ) we have | | z | | < | | φ ( z ) | | (since otherwise φ would be simple and so | | w | | = | | φ ( w ) | | ).
Denote z 0 = z and z i = τ i τ i − 1 . . . τ 1 ( z ) for 0 < i ≤ p . Thus z p = φ ( z ) . Since | | z | | < | | φ ( z ) | | , there is some i , 1 ≤ i ≤ p such that τ i is a non-inner Whitehead move of the second kind. Let j be the smallest i with this property. Then all τ i with i < j are either inner or relabeling automorphisms, | | z | | = | | z i | | and z i ∈ T ( ε ) .
In particular, z j − 1 ∈ T ( ε ) and z j − 1 is strictly minimal.
Thus n = | | z | | = | | z j − 1 | | ≤ | | z j | | = | | τ j ( z j − 1 ) | | < | | φ ( z ) | | . Let ( S , a ) be the characteristic pair of τ j and let S ′ = A ^ − S . Since τ j is non-inner, we have both | S | ≥ 2 , and | S ′ | ≥ 2 . Hence | S | | S ′ | ≥ 2 ( 2 k − 2 ) and there are at least 2 ( 2 k − 2 ) edges between S and S ′ in the weighted Whitehead graph of z j − 1 .
Recall that a . A ^ is the total number of occurrences of a ± 1 in z .
By Lemma 6.5 , we have | | τ j ( z j − 1 ) | | − | | z | | = S . S ′ − a . A ^ .
By assumption on z j − 1 we have a . A ^ ≤ n ( 1 k + ε ) and so | | τ j ( z j − 1 ) | | − | | z j − 1 | | = S . S ′ − a . A ^ ≥ 2 n ( 2 k − 2 ) ( 1 k ( 2 k − 1 ) − ε ) − n ( 1 k + ε ) . Hence | | φ ( z ) | | ≥ | | z j | | ≥ n + 2 n ( 2 k − 2 ) ( 1 k ( 2 k − 1 ) − ε ) − n ( 1 k + ε ) and so, since n = | | z | | , | | φ ( z ) | | | | z | | ≥ 1 + ( 4 k − 4 ) ( 1 k ( 2 k − 1 ) − ε ) − ( 1 k + ε ) Note that the above inequality holds for any element z ∈ T ( ε ) .
Since T ( ε ) is exponentially C ℛ -generic, this implies by Lemma 5.9 that λ ( φ ) ≥ 1 + ( 4 k − 4 ) ( 1 k ( 2 k − 1 ) − ε ) − ( 1 k + ε ) . Since 0 < ε < ε 0 was arbitrary, it follows that λ ( φ ) ≥ 1 + ( 4 k − 4 ) 1 k ( 2 k − 1 ) − 1 k = 1 + 2 k − 3 2 k 2 − k > 1 . This proves that (3) implies (1), so that (1), (2) and (3) are equivalent.
Choose 0 < ε 1 < ε 0 such that 1 + ( 4 k − 4 ) ( 1 k ( 2 k − 1 ) − ε 1 ) − ( 1 k + ε 1 ) < c 0 = 1 + 2 k − 3 4 k 2 − 2 k . Put W = T ( ε 1 ) . The above argument shows that if for some w ∈ W we have | | φ ( z ) | | | | z | | < 1 + ( 4 k − 4 ) ( 1 k ( 2 k − 1 ) − ε 1 ) − ( 1 k + ε 1 ) then φ 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. □

The following statement, together with Theorem 6.8 , implies Theorem F from the Introduction.

Corollary 6.9. Let

F = F (a_{1}, . . ., a_{k})

, where

k \geq 2

, and

d

be the word metric on

F

corresponding to the generating set

A = {a_{1}, . . ., a_{k}}

. Let

φ \in A u t (F)

. Then the following conditions are equivalent

(1) The automorphism $φ$ is simple.
(2) The map $φ : (F, d) \to (F, d)$ is a rough isometry.
(3) The map $φ : (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 $φ$ is a rough similarity, so that there exist $λ > 0$ and $D > 0$ such that for any $w \in F$ $λ | w | - D \leq | φ (w) | \leq λ | w | + D .$ Then obviously $λ = λ (φ)$ . By Theorem 6.8 either $φ$ is simple or $λ (φ) > 1$ .
Assume the latter. Put $λ_{0} = \frac{1 + λ}{2}$ . Thus $1 < λ_{0} < λ$ .
Consider the ball $B_{n}$ of radius $n$ in $F$ , where $n > > 1$ . For any $w \in F$ with $| w | \geq n / λ_{0}$ we have $| φ (w) | \geq λ | w | - D \geq λ n / λ_{0} - D > n,$ so that $φ (w) \notin B_{n}$ .
Thus only the elements of length $\leq n / λ_{0}$ may be potentially taken to $B_{n}$ by $φ$ .
The number of such elements is smaller than $# B_{n}$ since $λ_{0} > 1$ and $n / λ_{0} < n$ . This contradicts the fact that $φ : (F, d) \to (F, d)$ is a bijection. Therefore $φ$ is simple, as required. □

The following is Theorem G from the Introduction:

Theorem 6.10. Let

F = F (a_{1}, . . ., a_{k})

where

k \geq 2

. Let

φ : 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 $α$ of $F$ such that $X$ is $φ \circ α$ -equivariantly isomorphic to the Cayley graph of $F$ with respect to ${a_{1}, . . ., a_{k}}$ . In this case $λ (φ) = 1$ .
(2) We have $λ (φ) \geq 1 + \frac{1}{k (2 k - 1)}$ .

Proof. Let $Γ = X / F$ and let $T$ be a maximal tree in $Γ$ and let $B = {b_{1}, . . ., b_{k}}$ be the geometric basis of $F$ corresponding to $T$ . Let $ψ \in A u t (F)$ be defined by $α (b_{i}) = a_{i}$ for $i = 1, . . ., k$ .
Note that because of Lemma 4.2 for any cyclic word $w$ over $B$ we have $| | w | |_{X} \geq | | w | |_{B}$ . Suppose first that $α$ is not a simple automorphism. Then $λ (α) \geq 1 + \frac{2 k - 3}{k (2 k - 1)}$ .
Hence for every $ε > 0$ there exists an exponentially $C ℛ$ -generic set $R (ε) \subseteq C ℛ$ such that for any $w \in R (ε)$ $\frac{| | w | |_{B}}{| | w | |_{A}} = \frac{| | α (w) | |_{A}}{| | w | |_{A}} \geq 1 + \frac{2 k - 3}{k (2 k - 1)} - ε .$ Since $| | w | |_{X} \geq | | w | |_{B}$ , it follows that $\frac{| | w | |_{X}}{| | w | |_{A}} \geq 1 + \frac{2 k - 3}{k (2 k - 1)} - ε .$ Since $ε > 0$ was arbitrary, it follows by Lemma 5.9 that $λ (φ) \geq 1 + \frac{2 k - 3}{k (2 k - 1)} \geq 1 + \frac{1}{k (2 k - 1)},$ as required.
Suppose now that $α$ is a simple automorphism. We will assume that $α = I d$ , and it will be easily seen that the general case is similar.
If $Γ$ is a wedge of $k$ loop-edges then the statement of the theorem holds. Suppose $Γ$ is not of this form. Then there exist edges $e, e^{'} \in E (Γ - T)$ , $e^{'} \neq e^{- 1}$ , such that $[t (e), o (e^{'})]_{T}$ has length at least $1$ . Let $z$ be the freely reduced word of length $2$ in $B$ corresponding to the sequence $e e^{'}$ . Let $ε > 0$ be arbitrary. Let $C (2, ε / 2) \subseteq C ℛ$ be defined as in Proposition 5.5 . Thus $C (2, ε / 2)$ consists of all cyclically reduced words $w^{'}$ such that for the cyclic word $w = (w^{'})$ and for every freely reduced word $x y$ in $A$ $| f_{w} (x y) - \frac{1}{2 k (2 k - 1)} | \leq ε / 2 .$ Then $C (2, ε / 2)$ is exponentially $C ℛ$ -generic. Let $w^{'} \in C (2, ε / 2)$ be arbitrary and let $w = (w^{'})$ . Note that $| | w^{'} | |_{A} = | | w^{'} | |_{B} = | | w | |_{A} = | | w | |_{B}$ and $| | w | |_{X} = | | w^{'} | |_{X}$ .
Then $| | w | |_{X} \geq | | w | |_{B} + n_{w} (z) + n_{w} (z^{- 1}) = | | w | |_{A} + n_{w} (z) + n_{w} (z^{- 1})$ and so $\frac{| | w^{'} | |_{X}}{| | w^{'} | |_{A}} = \frac{| | w | |_{X}}{| | w | |_{A}} \geq 1 + f_{w} (z) + f_{w} (z^{- 1}) \geq 1 + \frac{1}{k (2 k - 1)} - ε .$ Since $ε > 0$ was arbitrary, Lemma 5.9 implies that $λ (φ) \geq 1 + \frac{1}{k (2 k - 1)}$ , as required. □

7 Application to the geometry of automorphisms

Definition 7.1. Let

F = F (a_{1}, . . ., a_{k})

. An automorphism

φ

F

is said to be

(s, m)

-hyperbolic, where

s > 1

and

m \geq 1

is an integer, if for every nontrivial cyclic word

w

we have

s | | w | | \leq max {| | φ^{m} (w) | |, | | φ^{- m} (w) | |} .

An automorphism is hyperbolic if it is

(s, m)

-hyperbolic for some

s > 1, m \geq 1

The following lemma is an easy consequence of the above definition:

Lemma 7.2. Let

φ \in A u t (F)

(s, m)

-hyperbolic and let

w

be a cyclic word of minimal length in its

〈 φ 〉

-orbit. Then for any

n \geq 2

we have

| | φ^{m n} (w) | | \geq s^{n - 1} | | w | | .

Proof. By definition of hyperbolicity of $φ$ we have $| | φ^{- m} (u) | | \leq | | u | | \Rightarrow s | | u | | \leq | | φ^{m} (u) | | .$ Note that by the choice of $w$ we have $| | w | | \leq | | φ^{m} (w) | |$ . Hence applying (!) with $u = φ^{m} (w)$ we get $s | | φ^{m} (w) | | \leq | | φ^{2 m} (w) | |$ . Then, using (!), by induction on $n$ we see that for any $n \geq 1$ $| | φ^{m (n + 1)} (w) | | = | | φ^{m n + m} (w) | | \geq s | | φ^{m} (w) | | .$ This in turn implies that for any $n \geq 1$ $| | φ^{m (n + 1)} (w) | | = | | φ^{m n + m} (w) | | \geq s^{n} | | φ^{m} (w) | | \geq s^{n - 1} | | w | | .$ This proves Lemma 7.2 . □

The following is Theorem E from the Introduction:

Theorem 7.3. Let

φ

be an

(s, m)

-hyperbolic automorphism of

F

. Then

{liminf}_{n \to \infty} \sqrt[n]{λ (φ^{n})} \geq \sqrt[m]{s} > 1 .

Proof. Let $t \geq 2$ be an arbitrary integer. Let $w \in S M$ be a strictly minimal element. Since $w$ is minimal in its $A u t (F)$ -orbit, it is also minimal in its $〈 φ 〉$ -orbit.
Therefore by Lemma 7.2 $| | φ^{t m} (w) | | \geq s^{t - 1} | | w | | and \frac{| | φ^{t m} (w) | |}{| | w | |} \geq s^{t - 1} .$ Since $S M$ is exponentially $C ℛ$ -generic, Lemma 5.9 implies that $λ (φ^{t m}) \geq s^{t - 1}$ .
Moreover, there is $D > 0$ such that for any cyclically reduced word $u$ we have $| | φ^{i} (u) | | \geq D | | u | |, for all 0 \leq i < m .$ Let $n \geq 2 m$ be an integer. Then we can write $n$ as $n = m t + i$ where $t \geq 2$ and $0 \leq i < m$ . For any $w \in S M$ we have $| | φ^{n} (w) | | = | | φ^{m t + i} (w) | | \geq D | | φ^{m t} (w) | | \geq D s^{t - 1} | | w | |$ and hence $\frac{| | φ^{t m} (w) | |}{| | w | |} \geq D s^{t - 1} .$ Since $S M$ is exponentially $C ℛ$ -generic, Lemma 5.9 again implies that for any $n \geq 2 m$ $λ (φ^{n}) \geq D s^{t - 1} = \frac{D}{s} s^{⌊ n / m ⌋} .$ This implies ${liminf}_{n \to \infty} \sqrt[n]{λ (φ^{n})} \geq s^{1 / m} > 1,$ as claimed. □

We can now prove Corollary I from the Introduction:

Corollary 7.4. Let

F = F (a_{1}, . . ., a_{k})

be a free group of rank

k \geq 2

, equipped with the standard metric.

Then for any

φ \in A u t (F)

we have:

f l u x (φ) = {\begin{matrix} 0, & if φ is a relabeling automorphism \\ 1, & otherwise. \end{matrix}

Proof. Let $λ = λ (φ)$ be the generic stretching factor.
Suppose first that $λ > 1$ . Then the set $T : = {w \in F : \frac{| φ (w) |}{| w |} > \frac{λ + 1}{2}$ is exponentially $F$ -generic.
Let $B (n)$ be the ball of radius $n$ in $F$ and let $w \in B (n) \cap T$ be such that $2 n / (λ + 1) \leq | w | \leq n$ . Then $| φ (w) | > | w | \frac{λ + 1}{2} \geq \frac{2 n}{λ + 1} \frac{λ + 1}{2} = n$ Hence for each $w \in [B (n) \cap T] - B (2 n / (λ + 1))$ we have $| φ (w) | > n$ . The size of $B (2 n / (λ + 1))$ is exponentially smaller than that of $B (n)$ since $2 / (λ + 1) < 1$ .
Hence by exponential genericity of $T$ $\frac{# [B (n) \cap T] - # B (2 n / (λ + 1))}{# B (n)} ⟶_{n \to \infty} 1 exponentially fast .$ Hence ${lim}_{n \to \infty} \frac{f l u x_{φ} (n)}{# B (n)} = 1$ and therefore $f l u x (φ) = 1$ .
Suppose now that $λ (φ) = 1$ . By Theorem 6.8 this implies that $φ = α τ$ where $α$ is inner and $τ$ is a relabeling automorphism.
If $α = 1$ , then obviously $f l u x (φ) = 0$ . Suppose now that $α$ is nontrivial. Since $τ$ acts as a permutation on each ball and each sphere in $F$ , we can assume that $τ = 1$ and $φ = α$ . Thus there is $u \in F, u \neq 1$ such that for every $w \in F$ $φ (w) = u w u^{- 1}$ .
There are $\geq c_{1} (2 k - 1)^{n}$ elements $f$ with $| w | = n$ such that the product $u w 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 $| φ (w) | > | w |$ . Hence there is a constant $c_{2} \in (0, 1)$ independent of $n$ and $u$ such that for any $n > 0$ $1 \geq \frac{f l u x_{φ} (n)}{# B (n)} \geq c_{2} > 0 .$ Hence $1 \geq f l u x (φ) = {lim}_{n \to \infty} \sqrt[n]{\frac{f l u x_{φ} (n)}{# B (n)}} \geq {lim}_{n \to \infty} \sqrt[n]{c_{2}} = 1 .$ Thus $f l u x (φ) = 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 non-deterministic finite automaton or NDFA. Such an automaton

M

over an alphabet

A

with state set

Q

is specified by a finite directed graph

Γ (M)

. The vertex set of

Γ (M)

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

Γ (M)

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

Γ (M)

from some initial state to an accepting state. The language,

L (M)

, accepted by

M

is the collection of all words accepted by

M

We will also use directed graph

Γ_{1} (M)

defined as follows. The vertex set of of

Γ_{1} (M)

is the set of directed edges

E (Γ (M))

M

. If

e_{1}, e_{2} \in E (Γ (M))

the pair

(e_{1}, e_{2})

defines a directed edge from

e_{1}

e_{2}

Γ_{1} (M)

if the terminus of

e_{1}

is the origin of

e_{2}

, that is,

e_{1}, e_{2}

is a directed edge-path in

Γ (M)

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 automaton $M$ has a nonempty set of accept states;
$∙$ the directed graph $Γ (M)$ has at least one edge;
$∙$ the directed graph $Γ (M)$ is strongly connected, that is for any two states $q, q^{'}$ of $M$ there exists a directed edge-path from $q$ to $q^{'}$ in $Γ (M)$ .

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:

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^{'}

as follows. The set of states of

M^{'}

is the set

E

of directed edges of

Γ (M)

. 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

Ω

for the Markov chain

M^{'}

defined above consists of all semi-infinite directed edge-paths

ω = e_{1}, e_{2}, . . ., e_{n}, . . .

in the graph

Γ (M)

. Every such path has a label

w (ω) = a_{1} a_{2} . . .,

that is a semi-infinite word over the alphabet

A

. We will denote

w_{n} = w_{n} (ω) : = a_{1} . . . a_{n}

, the initial segment of length

n

w

. The set

Ω

comes equipped with the natural topology, where we think of

Ω

as the union of boundaries of rooted trees

(T_{e})_{e} \in E

. The vertices of

T_{e}

are finite edge-path in

Γ (M)

beginning with

e

. The Borel

σ

-algebra on

Ω

is generated by the following open-closed cylinder sets

C y l (γ)

, where

γ

is a nonempty finite edge-path in

Γ (M)

C y l (γ) : = {ω \in Ω : p is the initial segment of ω} .

If we put an initial probability distribution

μ

E

, this defines a Borel probability measure

P_{μ}

Ω

. This measure is defined on the cylinder sets by the standard convolution formula. If

γ = e_{1}, . . ., e_{n}

, where

n > 1

, then

P_{μ} (C y l (γ)) : = μ (e_{1}) p_{e_{1}, e_{2}} p_{e_{2}, e_{3}} . . . p_{e_{n - 1}, e_{n}} .

n = 1

then

P_{μ} (C y l (e)) : = μ (e)

Lemma 8.4. Let

M

be a normal automaton. Then the associated finite state Markov chain

M^{'}

is irreducible. In particular, there is a unique stationary initial probability distribution

μ_{0}

on the set of states

E

M^{'}

This distribution has the property

μ_{0} (e) > 0

for each

e \in E

Proof. To show that $M^{'}$ 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}^{(n)} > 0$ . Since $Γ (M)$ is strongly connected, there exists a directed edge-path $γ$ in $Γ (M)$ from the terminus of $e$ to the origin of $f$ . Then $e γ f$ is a directed edge-path in $Γ (M)$ that starts with $e$ and ends with $f$ . Hence $Γ_{1} (M)$ is strongly connected and therefore $M^{'}$ is irreducible.
The irreducibility of $M^{'}$ implies the existence and uniqueness of a positive stationary distribution $μ_{0}$ on $E$ , as required. □

If we fix an initial probability distribution

μ

E

, this defines a probability measure

P_{μ}

Ω

Lemma 8.5. Let

M

be a normal automaton. Let

M^{'}

be the associated finite state Markov chain and let

μ_{0}

be the stationary initial distribution for

M^{'}

. Let

Z \subseteq Ω

be a set such that

P_{μ_{0}} (Z) = 0

. Then for any other initial distribution

μ

E

we have

P_{μ} (Z) = 0

Proof. Let $μ$ and $μ_{0}$ be as above. Put $c : = max {\frac{μ (e)}{μ_{0} (e)} : e \in E} .$ Note that $0 < c < \infty$ since $μ_{0} (e) > 0$ for each $e \in E$ . Consider an arbitrary cylinder set $C y l (γ) \subset Ω$ , where $γ = e_{1}, e_{2}, . . . e_{n}$ . From the definitions of $P_{μ}$ and $P_{μ_{0}}$ we see that $P_{μ} (C y l (γ)) = \frac{μ (e_{1})}{μ_{0} (e_{1})} P_{μ_{0}} (C y l (γ)) \leq c P_{μ_{0}} (C y l (γ)) .$ Hence for an arbitrary Borel set $Z \subseteq Ω$ we have $P_{μ} (Z) \leq c P_{μ_{0}} (Z)$ . In particular, if $P_{μ_{0}} (Z) = 0$ then $P_{μ} (Z) = 0$ . □

The previous two lemmas depend only on the automaton

M

being normal.

Suppose now that

L = L (M)

. 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

Γ (M)

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}^{'} = 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}^{'} \in L

. Thus if

μ

is an distribution supported on the set of edges in

E (M)

with initial vertices from

I

and

w_{n}

is obtained by performing

n

steps of the chain

M^{'}

with initial distribution

μ

, then

w_{n}^{'} \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 (M)

be the language accepted by

M

Let

φ : A^{*} \to G

be a monoid homomorphism, where

G

is a group with a left-invariant semi-metric

d_{G}

. Then there exists a number

λ = λ (M, φ, d_{G}) \geq 0

such that for any initial distribution

μ

E (M)

we have

{lim}_{n \to \infty} \frac{| φ (w_{n}) |_{G}}{n} = {lim}_{n \to \infty} \frac{| φ (w_{n}^{'}) |_{G}}{n} = λ almost surely and in L^{1} with respect to P_{μ} .

Proof. Let $μ_{0}$ be the unique stationary initial distribution for $M^{'}$ . As before denote by $S : Ω \to Ω$ the shift operator which erases the first edge of every $ω = e_{1}, e_{2}, \cdot \cdot \cdot \in Ω$ . Stationarity of $μ_{0}$ means that $S : (Ω, P_{μ_{0}}) \to (Ω, P_{μ_{0}})$ is a measure-preserving map. Since $M^{'}$ is irreducible and aperiodic, $S$ is also ergodic.
As before, define $X_{n} : Ω \to R$ as $X_{n} (ω) : = | φ (w_{n} (ω)) |_{G} .$ Then again it is easy to see that $X_{n} \geq 0$ , $X_{n + m} (ω) \leq X_{n} (ω) + X_{m} (S^{n} ω)$ . Hence by the Subadditive Ergodic Theorem there is $λ \geq 0$ and there is a subset $Q \subseteq Ω$ with $P_{μ_{0}} (Z) = 0$ such that for any $ω \notin Z$ ${lim}_{n \to \infty} \frac{| φ (w_{n} (ω)) |_{G}}{n} = λ .$ Let $μ$ be an arbitrary initial distribution on $E$ . Then by Lemma 8.5 we have $P_{μ} (Z) = 0$ . Thus $\frac{| φ (w_{n}) |_{G}}{n} \to λ almost surely with respect to P_{μ} .$ Note that by the left-invariance of $d_{G}$ we have $| φ (w) |_{G} \leq K | w |$ where $K = max {| φ (a) |_{G} : a \in A}$ . Hence $X_{n} / n = | φ (w_{n}) |_{G} / n \leq 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}^{'}$ differs from $| w_{n} |$ by at most a fixed constant, it is also true that $| φ (w_{n}^{'}) |_{G}$ differs from $| φ (w_{n}) |_{G}$ by at most a fixed constant and thus it is also the case that ${lim}_{n \to \infty} \frac{| φ (w_{n}^{'} (ω)) |_{G}}{n} = {lim}_{n \to \infty} \frac{| φ (w_{n} (ω)) |_{G}}{n} = λ .$ □

There is substantial flexibility in the choice of the Markov chain

M^{'}

. The proof of Theorem 8.6 goes through without change for any choice of transition probabilities in

M^{'}

such that

p_{e, f} > 0

whenever

(e, f)

is an edge of

Γ_{1} (M)

and

p_{e, f} = 0

whenever

(e, f)

is not an edge of

Γ_{1} (M)

9 Open Problems

Problem 9.1. Let

φ

be an arbitrary (not necessarily injective) endomorphism of

F = F (a_{1}, . . ., a_{k})

. Is

λ (φ)

rational? Computable?

Problem 9.2. Let

φ \in A u t (F)

. What can be said about the behavior of

λ (φ^{n})

n \to \infty

? Same for

\sqrt[n]{λ (φ^{n})}

. How are these quantities connected with growth rates of different (or perhaps just top) strata from relative train-track representatives of

φ

It is clear that the asymptotics of

λ (φ^{n})

should reflect the dynamical properties of

φ

. For example, it is not hard to see that for any Nielsen automorphism

τ

the stretching factor

λ (τ^{n})

grows at most linearly and

{limsup}_{n \to \infty} \sqrt[n]{λ (τ^{n})} = 1

On the other hand for hyperbolic automorphisms

φ

Theorem 7.3 implies that

{liminf}_{n \to \infty} \sqrt[n]{λ (φ^{n})} > 1

, so that the sequence

(λ (φ^{n}))_{n}

grows exponentially.

Problem 9.3. Can one estimate (say in the sense of Large Deviations) the speed of convergence

\frac{| φ (ω_{n}) |_{G}}{n} \to λ (φ)

We have seen that in the case of free group automorphisms for any

ε > 0

P_{n} (\frac{| φ (ω_{n}) |}{n} \in (λ (φ) - ε, λ (φ) + ε)) \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 \geq 2

. Consider the set

W = {λ (φ) : φ : F \to A u t (X) is a free simplicial action of F on some simplicial tree X} .

We know that

W \subseteq Q

and, moreover

2 k W \subseteq Z [\frac{1}{2 k - 1}]

W

a discrete subset of

Q

Problem 9.5. The notion of a generic stretching factor for

φ \in A u t (F)

depends on the choice of a free basis

b = (a_{1}, . . ., a_{k})

F

, and, more generally, on the choice of a finite generating set

S

F

and the corresponding word metric

d_{S}

. Denote by

λ_{S} (φ)

the generic stretching factor of

φ

considered as a map

(F, d_{S}) \to (F, d_{S})

One can define the following uniform constants

λ^{'} (φ) : = inf {λ_{b} (φ) : b is a free basis of F}

and

λ^{''} (φ) : = inf {λ_{S} (φ) : S is a finite generating set of F} .

(Note that

λ^{''} (φ)

can be defined in the same fashion for an automorphism

φ

of an arbitrary finitely generated group

G

For

φ \in A u t (F)

are the constants

λ^{'} (φ)

and

λ^{''} (φ)

actually realized by some free bases and finite generating sets of

F

accordingly? That is, are the above infima actually minima? Are

λ^{'} (φ)

and

λ^{''} (φ)

algorithmically computable?

Similarly we can define

| | φ | |^{'} = inf {| | φ | |_{b} : b is a free basis of F}

and

| | φ | |^{''} = inf {| | φ | |_{S} : S is a finite generating set of F} .

Since both of these constants are integers, they are clearly realizable by some

b

and

S

accordingly. Are these constants algorithmically computable?

References

G. Arzhantseva and A. Ol'shanskii, Genericity of the class of groups in which subgroups with a lesser number of generators are free, (Russian) Mat. Zametki 59 (1996), no. 4, 489–496
G. Arzhantseva, On groups in which subgroups with a fixed number of generators are free,(Russian) Fundam. Prikl. Mat. 3 (1997), no. 3, 675–683.
G. Arzhantseva, Generic properties of finitely presented groups and Howson's theorem, Comm. Algebra 26 (1998), 3783–3792.
G. Arzhantseva, A property of subgroups of infinite index in a free group, Proc. Amer. Math. Soc. 128 (2000), 3205–3210.
F. Bonahon, Bouts des variétés hyperboliques de dimension $3$ . Ann. of Math. (2) 124 (1986), no. 1, 71–158
F. Bonahon, The geometry of Teichmller space via geodesic currents. Invent. Math. 92 (1988), no. 1, 139–162
F. Bonahon, Geodesic currents on negatively curved groups. Arboreal group theory (Berkeley, CA, 1988), 143–168, Math. Sci. Res. Inst. Publ., 19, Springer, New York, 1991
A. Borovik, A. G. Myasnikov and V. Shpilrain, Measuring sets in infinite groups, Computational and Statistical Group Theory (R.Gilman et al, Editors), Contemp. Math., Amer. Math. Soc. 298 (2002), 21–42.
P. Brinkmann, Hyperbolic automorphisms of free groups, Geometric and Functional Analysis, 10 (2000), no. 5, 1071–1089
C. Champetier, Petite simplification dans les groupes hyperboliques, Ann. Fac. Sci. Toulouse Math. (6) 3 (1994), no. 2, 161–221.
C. Champetier, Propriétés statistiques des groupes de présentation finie, Adv. Math. 116 (1995), 197–262.
C. Champetier, The space of finitely generated groups, Topology 39 (2000), 657–680.
P.-A. Cherix and A. Valette, On spectra of simple random walks on one-relator groups, With an appendix by Paul Jolissaint. Pacific J. Math. 175 (1996), 417–438.
P.-A. Cherix and G. Schaeffer, An asymptotic Freiheitssatz for finitely generated groups, Enseign. Math. (2) 44 (1998), 9–22.
J. Cohen, Cogrowth and amenability of discrete groups, J. Funct. Anal. 48 (1982), 301–309
D. Cooper, Automorphisms of free groups have finitely generated fixed point sets. J. Algebra 111 (1987), no. 2, 453–456
P. Dehornoy, Braid-based cryptography, Group theory, statistics, and cryptography, 5–33, Contemp. Math., 360, Amer. Math. Soc., Providence, RI, 2004
A. Dembo and O. Zeitouni, Large Deviation Techniques and Applications. Second edition. Applications of Mathematics, 38. Springer-Verlag, New York, 1998
Y. Derriennic, Sur le théorème ergodique sous-additif. C. R. Acad. Sci. Paris Ser. A-B 281 (1975), no. 22, Aii, A985–A988
A. Furman, Coarse-geometric perspective on negatively curved manifolds and groups. Rigidity in dynamics and geometry (Cambridge, 2000), 149–166, Springer, Berlin, 2002
E. Ghys, Groupes Aléatoires. Seminar Bourbaki (2002/2003), Asterisque 294 (2004), 173–204
R. Grigorchuck, Symmetrical random walks on discrete groups, Multicomponent Random Systems, in: Adv. Probab. Related Topics, Vol. 6, Dekker, New York, 1980, 285–325
M. Gromov, Hyperbolic Groups, in ”Essays in Group Theory (G.M.Gersten, editor)”, MSRI publ. 8, 1987, 75–263
M. Gromov, Asymptotic invariants of infinite groups. Geometric group theory, Vol. 2 (Sussex, 1991), 1–295, London Math. Soc. Lecture Note Ser., 182, Cambridge Univ. Press, Cambridge, 1993
M. Gromov, Random walks in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73–146
Y. Guivarc'h, Sur la loi des grands nombres et le rayon spectral d'une marche aléatoire. Conference on Random Walks (Kleebach, 1979), pp. 47–98, 3, Astérisque, 74, Soc. Math. France, Paris, 1980
J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, 1979.
V. Kaimanovich, Hausdorff dimension of the harmonic measure on trees. Ergodic Theory Dynam. Systems 18 (1998), no. 3, 631–660
V. Kaimanovich, The Poisson formula for groups with hyperbolic properties. Ann. of Math. (2) 152 (2000), no. 3, 659–692.
I. Kapovich, The frequency space of a free group, Internat. J.Alg. Comput. (Grigorchuk's 50s anniversary issue), to appear, http://www.arxiv.org/math.GR/0311053
I. Kapovich, Currents on free groups, preprint; 2004; http://www.arxiv.org/math.GR/0412128
I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, Generic-case complexity, Decision problems in group theory and Random walks, J. Algebra, 264 (2003), no. 2, 665–694
I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain, Average-case complexity for the word and membership problems in group theory, Advances in Math. 190 (2005), no. 2, 343–359
I. Kapovich and P. Schupp, Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups, Math. Ann. 331 (2005), no. 1, 1–19
I. Kapovich, P. Schupp, and V. Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups, Pacific J. Math., to appear
J. F. C. Kingman, Subadditive ergodic theory. With discussion by D. L. Bürkholder, Daryl Daley, H. Kesten, P. Ney, Frank Spitzer and J. M. Hammersley, and a reply by the author. Ann. Probability 1 (1973), 883–909
V. Kaimanovich, and A. Vershik, Random walks on discrete groups: boundary and entropy. Ann. Probab. 11 (1983), no. 3, 457–490
R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977. Reprinted in the “Classics in mathematics” series, 2000.
A. G. Myasnikov and V. Shpilrain, Automorphic orbits in free groups, J. Algebra 269 (2003), 18–27
A. G. Myasnikov and V. Shpilrain, Some metric properties of automorphisms of groups, preprint; http://www.sci.ccny.cuny.edu/~shpil/papers.html
Y. Ollivier, Sharp phase transition theorems for hyperbolicity of random groups, Geom. Funct. Anal. 14 (2004), no. 3, 595–679
A. Yu. Ol'shanskii, Almost every group is hyperbolic, Internat. J. Algebra Comput. 2 (1992), 1–17.
J. H. C. Whitehead, On equivalent sets of elements in free groups, Annals of Mathematics 37 (1936), 782–800
W. Woess, Cogrowth of groups and simple random walks. Arch. Math. (Basel) 41 (1983), no. 4, 363–370
A. Zuk, On property (T) for discrete groups. Rigidity in dynamics and geometry (Cambridge, 2000), 473–482, Springer, Berlin, 2002

IRMAR, Universite Rennes-1, Campus de Beaulieu, 35042, Rennes Cedex, France; E-mail address : kaimanov@univ-rennes1.fr Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green Street, Urbana, IL 61801, USA http://www.math.uiuc.edu/~kapovich/ E-mail address : kapovich@math.uiuc.edu Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green Street, Urbana, IL 61801, USA http://www.math.uiuc.edu/People/schupp.html E-mail address : schupp@math.uiuc.edu