
We classify the asymptotic densities of the $\Delta^0_2$ sets according to
their level in the Ershov hierarchy. In particular, it is shown that for $n
\geq 2$, a real $r \in [0,1]$ is the density of an $n$c.e.\ set if and only if
it is a difference of left$\Pi_2^0$ reals. Further, we show that the densities
of the $\omega$c.e.\ sets coincide with the densities of the $\Delta^0_2$
sets, and there are $\omega$c.e.\ sets whose density is not the density of an
$n$c.e. set for any $n \in \omega$.

We compare the random group model of Gromov and the model of generic groups
of Arzhantseva and Ol'shanskii.

Motivated by results on genericcase complexity in group theory, we apply the
ideas of effective Baire category and effective measure theory to study
complexity classes of functions which are "fractionally computable" by a
partial algorithm. For this purpose it is crucial to specify an allowable
effective density, $\delta$, of convergence for a partial algorithm. The set
$\mathcal{FC}(\delta)$ consists of all total functions $ f: \Sigma^\ast \to
\{0,1 \}$ where $\Sigma$ is a finite alphabet with $\Sigma \ge 2$ which are
"fractionally computable at density $\delta$". The space $\mathcal{FC}(\delta)
$ is effectively of the second category while any fractional complexity class,
defined using $\delta$ and any computable bound $\beta$ with respect to an
abstract Blum complexity measure, is effectively meager. A remarkable result of
Kautz and Miltersen shows that relative to an algorithmically random oracle
$A$, the relativized class $\mathcal{NP}^A$ does not have effective polynomial
measure zero in $\mathcal{E}^A$, the relativization of strict exponential time.
We define the class $\mathcal{UFP}^A$ of all languages which are fractionally
decidable in polynomial time at ``a uniform rate'' by algorithms with an oracle
for $A$. We show that this class does have effective polynomial measure zero in
$\mathcal{E}^A$ for every oracle $A$. Thus relaxing the requirement of
polynomial time decidability to hold only for a fraction of possible inputs
does not compensate for the power of nondeterminism in the case of random
oracles.

We show that for any positive integer $m\ge 1$,
$m$relator quotients of the modular group $M = PSL(2,\mathbb{Z})$
generically satisfy a very strong Mostowtype \emph{isomorphism rigidity}. We
also prove that such quotients are generically "essentially incompressible". By
this we mean that their "absolute $T$invariant", measuring the smallest size
of any possible finite presentation of the group, is bounded below by a
function which is almost linear in terms of the length of the given
presentation. We compute the precise asymptotics of the number $I_m(n)$ of
\emph{isomorphism types} of $m$relator quotients of $M$ where all the defining
relators are cyclically reduced words of length $n$ in $M$. We obtain other
algebraic results and show that such quotients are complete, Hopfian,
coHopfian, oneended, wordhyperbolic groups.

In this article we relate two different densities. Let $F_k$ be the free
group of finite rank $k \ge 2$ and let $\alpha$ be the abelianization map from
$F_k$ onto $ \mathbb{Z}^k$. We prove that if $S \subseteq \mathbb{Z}^k$ is
invariant under the natural action of $SL(k, \mathbb{Z})$ then the asymptotic
density of $S$ in $\mathbb Z^k$ and the annular density of its full preimage
$\alpha^{1}(S)$ in $F_k$ are equal. This implies, in particular, that for
every integer $t\ge 1$, the annular density of the set of elements in $F_k$
that map to $t$th powers of primitive elements in $\mathbb{Z}^k$ is equal to
to $\frac{1}{t^k\zeta(k)}$, where $\zeta$ is the Riemann zetafunction. An
element $g$ of a group $G$ is called a \emph{test element} if every
endomorphism of $G$ which fixes $g$ is an automorphism of $G$. As an
application of the result above we prove that the annular density of the set of
all test elements in the free group $F(a,b)$ of rank two is
$1\frac{6}{\pi^2}$. Equivalently, this shows that the union of all proper
retracts in $F(a,b)$ has annular density $\frac{6}{\pi^2}$. Thus being a test
element in $F(a,b)$ is an ``intermediate property'' in the sense that the
probability of being a test element is strictly between 0 and 1.

Given a free group $F_k$ of rank $k\ge 2$ with a fixed set of free generators
we associate to any homomorphism $\phi$ from $F_k$ to a group $G$ with a
leftinvariant seminorm a generic stretching factor, $\lambda(\phi)$, which is
a noncommutative generalization of the translation number. We concentrate on
the situation when $\phi:F_k\to Aut(X)$ corresponds to a free action of $F_k$
on a simplicial tree $X$, in particular, when $\phi$ 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 $\lambda=\lambda(\phi)$. We show that $\lambda \ge 1$ and is a
rational number with $2k\lambda\in \mathbb Z[ \frac{1}{2k1} ]$ for every
$\phi\in Aut(F_k)$. We also prove that the set of all $\lambda(\phi)$, where
$\phi$ varies over $Aut(F_k)$, has a gap between 1 and $1+\frac{2k3}{2k^2k}$,
and the value 1 is attained only for ``trivial'' reasons. Furthermore, there is
an algorithm which, when given $\phi$, calculates $\lambda(\phi)$.

We prove that ``almost generically'' for a onerelator group Delzant's
$T$invariant (which measures the smallest size of a finite presentation for a
group) is comparable in magnitude with the length of the defining relator. The
proof relies on our previous results regarding isomorphism rigidity of generic
onerelator groups and on the methods of the theory of KolmogorovChaitin
complexity. We also give a precise asymptotic estimate (when $k$ is fixed and
$n$ goes to infinity) for the number $I_{k,n}$ of isomorphism classes of
$k$generator onerelator groups with a cyclically reduced defining relator of
length $n$: \[ I_{k,n}\sim \frac{(2k1)^n}{nk!2^{k+1}}. \] Here $f(n)\sim g(n)$
means that $\lim_{n\to\infty} f(n)/g(n)=1$.

Motivated by the work of Leininger on hyperbolic equivalence of homotopy
classes of closed curves on surfaces, we investigate a similar phenomenon for
free groups. Namely, we study the situation when two elements $g,h$ in a free
group $F$ have the property that for every free isometric action of $F$ on an
$\mathbb{R}$tree $X$ the translation lengths of $g$ and $h$ on $X$ are equal.
We give a combinatorial characterization of this phenomenon, called translation
equivalence, in terms of Whitehead graphs and exhibit two difference sources of
it. The first source of translation equivalence comes from representation
theory and $SL_2$ trace identities. The second source comes from geometric
properties of groups acting on real trees and a certain power redistribution
trick. We also analyze to what extent these are applicable to the tree actions
of surface groups that occur in the Thurston compactification of the
Teichmuller space.

We prove that Whitehead's algorithm for solving the automorphism problem in a
fixed free group $F_k$ has strongly linear time genericcase 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 onerelator groups. We obtain a Mostowtype isomorphism rigidity
result for random onerelator 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 onerelator 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 onerelator groups with defining
relators of length $n$ satisfies \[ \frac{c_1}{n} (2k1)^n \le I_k(n)\le
\frac{c_2}{n} (2k1)^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$.

Let $G=<a_1,..., a_n  a_ia_ja_i... = a_ja_ia_j..., i<j>$ be an Artin group
and let $m_{ij}=m_{ji}$ be the length of each of the sides of the defining
relation involving $a_i$ and $a_j$. We show if all $m_{ij}\ge 7$ then $G$ is
relatively hyperbolic in the sense of Farb with respect to the collection of
its twogenerator subgroups $<a_i, a_j>$ for which $m_{ij}<\infty$.

We apply the method of ArzhantsevaOl'shanskii to prove that for an
exponentially generic (in the sense of Ol'shanskii) class of onerelator groups
the isomorphism problem is solvable in at most exponential time.
This is obtained as a corollary of our more general result that for any fixed
integers $m>1, n>0$ there is an exponentially generic class of $m$generator
$n$relator groups where every group has only one Nielsen equivalence class of
$m$tuples generating nonfree subgroups. This means that a group $G$ in this
class has has only one nonfree $m$generated subgroup, namely $G$ itself.
Hence for any homomorphism for an $m$generated group to $G$ the image of this
homomorphism is either free or is equal to $G$. Applied to injective
homomorphisms from $G$ to itself this implies that $G$ is coHopfian. Moreover,
every automorphism of $G$ is "freely induced", that is, it lifts to an
automorphism of the free group $F_m$.
All of these results are obtained by folding methods without using the theory
of JSJdecomposition or the Rtree techniques deployed by Zlil Sela in his
famous solution of the isomorphism problem for torsionfree wordhyperbolic
groups.

We investigate the averagecase complexity of decision problems for finitely
generated groups, in particular the word and membership problems. Using our
recent results on ``genericcase complexity'' we show that if a finitely
generated group $G$ has the word problem solvable in subexponential time and
has a subgroup of finite index which possesses a nonelementary wordhyperbolic
quotient group, then the averagecase complexity of the word problem for $G$ is
linear time, uniformly with respect to the collection of all lengthinvariant
measures on $G$. For example, the result applies to all braid groups $B_n$.

We give a precise definition of ``genericcase complexity'' and show that for
a very large class of finitely generated groups the classical decision problems
of group theory  the word, conjugacy and membership problems  all have
lineartime genericcase complexity. We prove such theorems by using the theory
of random walks on regular graphs.

We obtain a number of results regarding freeness, quasiconvexity and
separability for subgroups of Coxeter groups, Artin groups and onerelator
groups with torsion.