• ### Asymptotic density and the Ershov hierarchy(1309.0137)

Aug. 17, 2014 math.LO
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$.
• ### On group-theoretic models of randomness and genericity(0705.4681)

Feb. 8, 2010 math.GT, math.GR
We compare the random group model of Gromov and the model of generic groups of Arzhantseva and Ol'shanskii.
• ### Some Quantitative Aspects of Fractional Computability(0706.4095)

June 27, 2007 math.GR, cs.CC
Motivated by results on generic-case 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.
• ### Random quotients of the modular group are rigid and essentially incompressible(math/0604343)

April 14, 2006 math.GT, math.GR
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 Mostow-type \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, co-Hopfian, one-ended, word-hyperbolic groups.
• ### Densities in free groups and $\mathbb{Z}^k$, Visible Points and Test Elements(math/0507573)

Nov. 30, 2005 math.GT, math.GR
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 zeta-function. 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.

April 6, 2005 math.GT, math.GR
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 left-invariant semi-norm a generic stretching factor, $\lambda(\phi)$, which is a non-commutative 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}{2k-1} ]$ 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{2k-3}{2k^2-k}$, and the value 1 is attained only for trivial'' reasons. Furthermore, there is an algorithm which, when given $\phi$, calculates $\lambda(\phi)$.
• ### Delzant's T-invariant, Kolmogorov complexity and one-relator groups(math/0305353)

Jan. 30, 2005 math.GT, math.GR
We prove that almost generically'' for a one-relator 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 one-relator groups and on the methods of the theory of Kolmogorov-Chaitin 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 one-relator groups with a cyclically reduced defining relator of length $n$: $I_{k,n}\sim \frac{(2k-1)^n}{nk!2^{k+1}}.$ Here $f(n)\sim g(n)$ means that $\lim_{n\to\infty} f(n)/g(n)=1$.
• ### Translation equivalence in free groups(math/0409284)

Jan. 10, 2005 math.GT, math.GR
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.
• ### Generic properties of Whitehead's Algorithm and isomorphism rigidity of random one-relator groups(math/0303386)

Aug. 27, 2004 math.GT, math.GR, cs.CC
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$.
• ### Relative hyperbolicity and Artin groups(math/0209058)

July 25, 2003 math-ph, math.MP, math.GR
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 two-generator subgroups $<a_i, a_j>$ for which $m_{ij}<\infty$.
• ### Genericity, the Arzhantseva-Ol'shanskii method and the Isomorphism Problem for One-Relator Groups(math/0210307)

Oct. 19, 2002 math.GT, math.GR
We apply the method of Arzhantseva-Ol'shanskii to prove that for an exponentially generic (in the sense of Ol'shanskii) class of one-relator 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 non-free subgroups. This means that a group $G$ in this class has has only one non-free $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 co-Hopfian. 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 JSJ-decomposition or the R-tree techniques deployed by Zlil Sela in his famous solution of the isomorphism problem for torsion-free word-hyperbolic groups.
• ### Average-case complexity and decision problems in group theory(math/0206273)

Aug. 22, 2002 math.GT, math.GR, cs.CC
We investigate the average-case complexity of decision problems for finitely generated groups, in particular the word and membership problems. Using our recent results on generic-case 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 non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem for $G$ is linear time, uniformly with respect to the collection of all length-invariant measures on $G$. For example, the result applies to all braid groups $B_n$.
• ### Generic-case complexity, decision problems in group theory and random walks(math/0203239)

June 10, 2002 math.GR, cs.CC
We give a precise definition of generic-case 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 linear-time generic-case complexity. We prove such theorems by using the theory of random walks on regular graphs.
• ### Bounded rank subgroups of Coxeter groups, Artin groups and one-relator groups with torsion(math/0201106)

Jan. 11, 2002 math.GT, math.GR
We obtain a number of results regarding freeness, quasiconvexity and separability for subgroups of Coxeter groups, Artin groups and one-relator groups with torsion.