Notes of Enric Ventura’s talk

On the difficulty of inverting automorphisms of free groups

Joint work with Pedro Silva and Manuel Ladra

1. Motivation

I will give an application of the asymetry of the metric on Outer space.

Question [Myasnikov]: Can you find a group where multiplication is easy but inverting is difficult ?

Multiplying in {Aut(F_n)} is very easy. Inversion does not seem to be.


\displaystyle  \begin{array}{rcl}  a\mapsto a, b\mapsto a^n b, c\mapsto b^n c \end{array}

Then inverse involves a tower of power {n} operations.

We shall formalize the problem, and see that inversion is not that hard, in fact.

1.1. Inversion growth

1.2. Notation

Definition 1 In a group {G} generated by {\{a_1 ,\ldots,a_k\}}, define norms for automorphisms as follows,

\displaystyle  \begin{array}{rcl}  \|\theta\|_{1} =\sum|a_i \theta|, \quad \|\theta\|_{\infty} =\max_{i}|a_i \theta| \end{array}

Definition 2 In a group {G}, let {\alpha(n)} be the worst norm of the inverse of automorphisms of length {\leq n}.

Question: How does this function grow ?

We shall concentrate on the free group {F_r}. One uses cyclic length (min of lengths of cyclic conjugates), although it does not satisfy triangle inequality. One uses a third length, where one maximizes over conjugations (where the same conjugation is applied to all generators). This gives three inversion growth functions, {\alpha_r}, {\beta_r} and {\gamma_r}, which are not equivalent.

2. Lower bounds for free groups

2.1. Rank {2} case

Theorem 3 {\alpha_2} is quadratic, {\beta_2} and {\gamma_2} are linear.

2.2. Rank {\geq 3} case

Theorem 4 {\alpha_r \geq \Omega(n^r)}, {\beta_r} is at most polynomial and {\gamma_r \geq \Omega(n^{r-1})}.

I expect that all three functions are exactly polynomial of nearby degrees.

2.3. Proof of the lower bound on {\gamma_r}

Use the obvious generalization of the example above. Generators are sent to cyclically reduced elements, so cyclic lengths are easy to calculate.

2.4. Proof of the lower bound on {\alpha_r}

One wins a factor of {n} by composing the previous example with conjugation by a large element.

3. Upper bounds

We use the asymetric distance on Outer space (see Martino’s talk).

Definition 5 For {\epsilon>0}, the {\epsilon}-thick part {X_{\epsilon}} of Outer space is the set of metric graphs in which all cycles have length {\geq\epsilon}.

Theorem 6 (Bestvina, Algom-Kfir) On {X_{\epsilon}}, {d(x,y)\leq M(r,\epsilon)d(y,x)}.

Corollary 7 All three inversion functions are bounded above by {n^{M(r,1/r)}}.

Indeed, given {\phi\in Aut(F_r)}, consider a rose {x}. Then {\log\|\phi\|_{\infty}} equal {d(x,x\phi)} up to constants. {\log\|\phi^{-1}\|_{\infty}=d(x,x\phi^{-1})=d(x\phi,x)}. Both {x} and {x\phi} belong to {X_{1/r}}.

4. Case {r=2}

Theorem 8 For {r=2},

\displaystyle \beta_2 (n)=\gamma_2(n)=n \textrm{ exactly. } n^{2/16}\leq\alpha_2 (n)\leq (n-1)^{2}/2 .

Proof uses a decomposition of automorphisms. Every {\theta} can be written

\displaystyle  \begin{array}{rcl}  \theta=\psi_1 \phi \psi_2 \lambda_g \end{array}

where {\lambda_g} is inner, {\psi_i} are letter permutations and {\phi} is positive.

5. Fixed subgroups

Fixators of automorphisms can be complicated: for instance, generated by unexpectedly long elements (Stallings).

Theorem 9 (Bestvina-Handel) Fixed point sets of arbitrary automorphisms have rank {\leq n}.

They introduced train tracks for that purpose. Later extensions to endomorphisms.

5.1. Inertia

Definition 10 Say a subgroup {H\subset F_n} is inert if {rank(H\cap K)\leq rank(K)} for every subgroup {K\subset F_n}.

Theorem 11 (Dicks, Ventura 1996) Fixed point sets of sets of monomorphisms are inert.

Does this hold for general endomorphisms ?

Theorem 12 (Martino-Ventura, Ciobanu-Dicks) There exist subgroups which are not fixed point sets.

5.2. Algorithmic issues

Theorem 13 (Maslakova 2003, corrected by Dicks 2011) Fixed subgroups of endomorphisms are computable.

Theorem 14 (Ventura 2010) Given a subgroup, one can decide wether it is the fixed point set of a set of endomorphisms (resp. endomorphisms).

But I cannot decide if it is the fixed point set of a single endomorphism (resp. endomorphism).


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s