Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups

Details Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups

2003-03-31

arxiv.org/abs/math/0303386v4

Mathematics

Group Theory

final revised version, to appear in Pacific J. Math

Scientific paper

We prove that Whitehead's algorithm for solving the automorphism problem in a fixed free group $F_k$ has strongly linear time generic-case complexity. This is done by showing that the ``hard'' part of the algorithm terminates in linear time on an exponentially generic set of input pairs. We then apply these results to one-relator groups. We obtain a Mostow-type isomorphism rigidity result for random one-relator groups: If two such groups are isomorphic then their Cayley graphs on the \emph{given generating sets} are isometric. Although no nontrivial examples were previously known, we prove that one-relator groups are generically \emph{complete} groups, that is, they have trivial center and trivial outer automorphism group. We also prove that the stabilizers of generic elements of $F_k$ in $Aut(F_k)$ are cyclic groups generated by inner automorphisms and that $Aut(F_k)$-orbits are uniformly small in the sense of their growth entropy. We further prove that the number $I_k(n)$ of \emph{isomorphism types} of $k$-generator one-relator groups with defining relators of length $n$ satisfies \[ \frac{c_1}{n} (2k-1)^n \le I_k(n)\le \frac{c_2}{n} (2k-1)^n, \] where $c_1=c_1(k)>0, c_2=c_2(k)>0$ are some constants independent of $n$. Thus $I_k(n)$ grows in essentially the same manner as the number of cyclic words of length $n$.

Affiliated with

Also associated with

No associations

Rating

Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-101973