Average-case complexity and decision problems in group theory

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 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 of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups B_n, all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type.     

On the hyperbolic limit points of groups acting on hyperbolic spaces

We study the hyperbolic limit points of a groupG acting on a hyperbolic metric space, and consider the question of whether any attractive limit point corresponds to a unique repulsive limit point. In the special case whereG is a (non-elementary) finitely generated hyperbolic group acting on its Cayley graph, the answer is affirmative, and the resulting mapg ⁺↦g ⁻, is discontinuous everywhere on the hyperbolic boundary. We also provide a direct, combinatorial proof in the special case whereG is a (non-abelian) free group of finite type, by characterizing algebraically the hyperbolic ends ofG. Partially supported by a grant from M.U.R.S.T., Italy.     

The isomorphism problem for toral relatively hyperbolic groups

We provide a solution to the isomorphism problem for torsion-free relatively hyperbolic groups with abelian parabolics. As special cases we recover solutions to the isomorphism problem for: (i) torsion-free hyperbolic groups (Sela, [60] and unpublished); and (ii) finitely generated fully residually free groups (Bumagin, Kharlampovich and Miasnikov [14]). We also give a solution to the homeomorphism problem for finite volume hyperbolic n-manifolds, for n≥3. In the course of the proof of the main result, we prove that a particular JSJ decomposition of a freely indecomposable torsion-free relatively hyperbolic group with abelian parabolics is algorithmically constructible.     

FINITELY GENERATED G′ AND POSITIVE LAWS

We conjecture that a finitely generated relatively free group G has a finitely generated commutator subgroup G′ if and only if G satisfies a positive law. We confirm this conjecture for groups G in the large class, containing all residually finite and all soluble groups.     

Some Isoperimetric Inequalities for Kernels of Free Extensions

If G is a hyperbolic group (resp. synchronously or asynchronously automatic group) which can be expressed as an extension of a finitely presented group H by a finitely generated free group, then the normal subgroup H satisfies a polynomial isoperimetric inequality (resp. exponential isoperimetric inequality).     

Howson's Property for Semidirect Products of Semilattices by Groups

An inverse semigroup S is a Howson inverse semigroup if the intersection of finitely generated inverse subsemigroups of S is finitely generated. Given a locally finite action θ of a group G on a semilattice E, it is proved that E*_θG is a Howson inverse semigroup if and only if G is a Howson group. It is also shown that this equivalence fails for arbitrary actions.     

Groups Whose Finite Homomorphic Images are Metahamiltonian

A group G is metahamiltonian if all its non-abelian subgroups are normal. It is proved here that a finitely generated soluble group is metahamiltonian if and only if all its finite homomorphic images are metahamiltonian; the behaviour of soluble minimax groups with metahamiltonian finite homomorphic images is also investigated. Moreover, groups satisfying the minimal condition on non-metahamiltonian subgroups are described.     

Limit sets of relatively hyperbolic groups

In this paper, we prove a limit set intersection theorem in relatively hyperbolic groups. Our approach is based on a study of dynamical quasiconvexity of relatively quasiconvex subgroups. Using dynamical quasiconvexity, many well-known results on limit sets of geometrically finite Kleinian groups are derived in general convergence groups. We also establish dynamical quasiconvexity of undistorted subgroups in finitely generated groups with nontrivial Floyd boundaries.     

On Turner’s theorem and first-order theory

A theorem of E.C. Turner states that if F is a finitely generated free group, then the test words are precisely the elements not contained in any proper retract. In this paper, we examine some ideas in model theory and logic related to Turner’s characterization of test words and introduce Turner groups, a class of groups containing all finite groups and all stably hyperbolic groups satisfying this characterization. We show that Turner’s theorem is not first-order expressible. However, we prove that every finitely generated elementary free group is a Turner group.     

Relative hyperbolicity and Artin groups

This paper considers the question of relative hyperbolicity of an Artin group with regard to the geometry of its associated Deligne complex. We prove that an Artin group is weakly hyperbolic relative to its finite (or spherical) type parabolic subgroups if and only if its Deligne complex is a Gromov hyperbolic space. For a two-dimensional Artin group the Deligne complex is Gromov hyperbolic precisely when the corresponding Davis complex is Gromov hyperbolic, that is, precisely when the underlying Coxeter group is a hyperbolic group. For Artin groups of FC type we give a sufficient condition for hyperbolicity of the Deligne complex which applies to a large class of these groups for which the underlying Coxeter group is hyperbolic. The key tool in the proof is an extension of the Milnor-Svarc Lemma which states that if a group G admits a discontinuous, co-compact action by isometries on a Gromov hyperbolic metric space, then G is weakly hyperbolic relative to the isotropy subgroups of the action.      

The residual finiteness of negatively curved polygons of finite groups

A subgroup M⊂G is almost malnormal provided that for each g∈G−M, the intersection M ^g ∩M is finite. It is proven that the free product of two virtually free groups amalgamating a finitely generated almost malnormal subgroup, is residually finite. A consequence of a generalization of this result is that an acute-angled n-gon of finite groups is residually finite if n≥4. Another consequence is that if G acts properly discontinuously and cocompactly on a 2-dimensional hyperbolic building whose chambers have acute angles and at least 4 sides, then G is residually finite. Oblatum 17-VII-2000 & 13-II-2002?Published online: 29 April 2002     

Palindromic Width of Finitely Generated Solvable Groups

We investigate the palindromic width of finitely generated solvable groups. We prove that every finitely generated 3-step solvable group has finite palindromic width. More generally, we show the finiteness of the palindromic width for finitely generated abelian-by-nilpotent-by-nilpotent groups. For arbitrary solvable groups of step ≥3, we prove that if G is a finitely generated solvable group that is an extension of an abelian group by a group satisfying the maximal condition for normal subgroups, then the palindromic width of G is finite. We also prove that the palindromic width of ??? with respect to the set of standard generators is 3.     

Fibre products, non-positive curvature, and decision problems

We give a criterion for fibre products to be finitely presented and use it as the basis of a construction that encodes the pathologies of finite group presentations into pairs of groups where G is a product of hyperbolic groups and P is a finitely presented subgroup. This enables us to prove that there is a finitely presented subgroup P in a biautomatic group G such that the generalized word problem for is unsolvable and P has an unsolvable conjugacy problem. An additional construction shows that there exists a compact non-positively curved polyhedron X such that is biautomatic and there is no algorithm to decide isomorphism among the finitely presented subgroups of . Received: October 7, 1999.     

Fredholm Properties of Band-dominated Operators on Periodic Discrete Structures

Let (X, ~) be a combinatorial graph the vertex set X of which is a discrete metric space. We suppose that a discrete group G acts freely on (X, ~) and that the fundamental domain with respect to the action of G contains only a finite set of points. A graph with these properties is called periodic with respect to the group G. We examine the Fredholm property and the essential spectrum of band-dominated operators acting on the spaces l ^p (X) or c_0(X), where (X, ~) is a periodic graph. Our approach is based on the thorough use of band-dominated operators. It generalizes the necessary and sufficient results obtained in [39] in the special case and in [42] in case X = G is a general finitely generated discrete group. Submitted: May 21, 2007. Revised: September 25, 2007. Accepted: November 5, 2007.     

Presentations for a class of generalized Thompson’s groups

For a given group G and a monomorphism φ:G→G×G there is a group ?_φ(G), introduced by the author, which blends Thompson’s group F with G. Given a presentation of G we determine a presentation of ?_φ(G). In particular, we prove that ?_φ(G) is finitely generated (resp. finitely presented) if G is finitely generated (resp. finitely presented).     

Virtually Nilpotent Groups with (almost) All Localizations Trivial

A group G is generically trivial if and only if, for all prime numbers p the localization of G with respect to p is trivial. Taking off from a theorem of Casacuberta and Castellet , we prove that a virtually nilpotent group E is generically trivial if and only if E is perfect. Inspired by this result, we introduce the concept of almost generically trivial groups. Those are groups G such that, for only finitely many primes p the localization of G with respect to p is not trivial. We prove that a virtually nilpotent group E with finitely generated abelianization is almost generically trivial if and only if the abelianization of E is finite.     

The Schur property for subgroup lattices of groups

A classical theorem of Schur states that if the centre of a group G has finite index, then the commutator subgroup G′ of G is finite. A lattice analogue of this result is proved in this paper: if a group G contains a modularly embedded subgroup of finite index, then there exists a finite normal subgroup N of G such that G/N has modular subgroup lattice. Here a subgroup M of a group G is said to be modularly embedded in G if the lattice is modular for each element x of G. Some consequences of this theorem are also obtained; in particular, the behaviour of groups covered by finitely many subgroups with modular subgroup lattice is described. Received: 16 October 2007, Final version received: 22 February 2008     

On the homotopy type of p-completions of infra-nilmanifolds

Infra-nilmanifolds are compact K(G,1)-manifolds with G a torsion-free, finitely generated, virtually nilpotent group. Motivated by previous results of various authors on p-completions of K(G,1)-spaces with G a finite or a nilpotent group, we study the homotopy type of p-completions of infra-nilmanifolds, for any prime p. We prove that the p-completion of an infra-nilmanifold is a virtually nilpotent space which is either aspherical or has infinitely many nonzero homotopy groups. The same is true for p-localization. Moreover, we show by means of examples that rationalizations of infra-nilmanifolds may be elliptic or hyperbolic. Received: 12 December 2001 / Published online: 5 September 2002     

Operator norm localization property of relative hyperbolic group and graph of groups

In this article we study the spaces which have operator norm localization property. We prove that a finitely generated group Γ which is strongly hyperbolic with respect to a collection of finitely generated subgroups {H₁,…,Hn} has operator norm localization property if and only if each Hi, i=1,2,…,n, has operator norm localization property. Furthermore we prove the following result. Let π be the fundamental group of a connected finite graph of groups with finitely generated vertex groups GP. If GP has operator norm localization property for all vertices P then π has operator norm localization property.