Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

Group Embeddings with Algorithmic Properties

We show that every countable group H with solvable word problem can be subnormally embedded into a 2-generated group G which also has solvable word problem. Moreover, the membership problem for H < G is also solvable. We also give estimates of time and space complexity of the word problem in G and of the membership problem for H < G.     

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.     

Automorphisms of Hyperbolic Groups and Graphs of Groups

Using the canonical JSJ splitting, we describe the outer automorphism group Out(G) of a one-ended word hyperbolic group G. In particular, we discuss to what extent Out(G) is virtually a direct product of mapping class groups and a free abelian group, and we determine for which groups Out(G) is infinite. We also show that there are only finitely many conjugacy classes of torsion elements in Out(G), for G any torsion-free hyperbolic group. More generally, let Γ be a finite graph of groups decomposition of an arbitrary group G such that edge groups G_e are rigid (i.e. Out(G_e) is finite). We describe the group of automorphisms of G preserving Γ, by comparing it to direct products of suitably defined mapping class groups of vertex groups.     

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.     

Groups with Polycyclic-by-Finite Conjugate Classes of Subgroups

Abstract

Neumann characterized the groups in which every subgroup has finitely many conjugates only as central-by-finite groups. If 𝔛 is a class of groups, a group G is said to have 𝔛-conjugate classes of subgroups if G/Core _G (N _G (H)) ∈ 𝔛 for every subgroup H of G. In this paper, we generalize Neumann's result by showing that a group has polycyclic-by-finite classes of conjugate subgroup if and only if it is central-by-(polycyclic-by-finite).     

Quasi-isometries between groups with infinitely many ends

Let G, F be finitely generated groups with infinitely many ends and let? be graph of groups decompositions of F, G such that all edge groups are finite and all vertex groups have at most one end. We show that G, F are quasi-isometric if and only if every one-ended vertex group of is quasi-isometric to some one-ended vertex group of and every one-ended vertex group of is quasi-isometric to some one-ended vertex group of?. From our proof it also follows that if G is any finitely generated group, of order at least three, the groups: and are all quasi-isometric. Received: April 7, 2000; revised version: October 6, 2000     

Large localizations of finite groups

We construct examples of localizations in the category of groups which take the Mathieu group M₁₁ to groups of arbitrarily large cardinality which are “abelian up to finitely many generators.” The paper is part of a broader study on the group theoretic properties which are or are not preserved by localizations.     

Uniformly generated submodules of permutation modules: Over fields of characteristic 0

This paper is motivated by a link between algebraic proof complexity and the representation theory of the finite symmetric groups. Our perspective leads to a new avenue of investigation in the representation theory of S_n. Most of our technical results concern the structure of “uniformly” generated submodules of permutation modules. For example, we consider sequences of submodules of the permutation modules M^(n−k,1k) and prove that if the sequence W_n is given in a uniform (in n) way – which we make precise – the dimension p(n) of W_n (as a vector space) is a single polynomial with rational coefficients, for all but finitely many “singular” values of n. Furthermore, we show that dim(W_n)<p(n) for each singular value of n≥4k. The results have a non-traditional flavor arising from the study of the irreducible structure of the submodules W_n beyond isomorphism types. We sketch the link between our structure theorems and proof complexity questions, which are motivated by the famous NP vs. co-NP problem in complexity theory. In particular, we focus on the complexity of showing membership in polynomial ideals, in various proof systems, for example, based on Hilbert's Nullstellensatz.     

Definability in algebraically closed groups

Let K be an abstract class of groups such that a countable group U exists possessing the following properties: 1) an arbitrary finitely generated subgroup of U belongs to K; 2) an arbitrary finitely generated subgroup from K is imbedded in U; 3) a recursive representaion of the group U exists with a solvable word identity problem. Then for arbitrary n ≥ 1 there exists ??-equation Ψ_n(v₀...v_n?1) such that for an arbitrary algebraically closed group G and for arbitrary x₀...x_n?1 ε G Classes of finite free nilpotent groups satisfy the conditions of the theorem.     

Profinite groups with nonabelian crowns of bounded rank and their probabilistic zeta function

It has been conjectured by Mann that the infinite sum Σ _H μ(H,G)/|G:H| ^s , where H ranges over all open subgroups of a finitely generated profinite group G, converges absolutely in some half right plane if G is positively finitely generated. We prove that the conjecture is true if the nonabelian crowns of G have bounded rank. In particular Mann’s conjecture holds if G has polynomial subgroup growth or is an adelic profinite group.     

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.     

On the Howson Property of HNN-Extensions with Nilpotent Base Group and Amalgamated Free Products of Nilpotent Groups

We give necessary and sufficient conditions under which an amalgamated free product of finitely generated nilpotent groups is a Howson group (that is the intersection of any two finitely generated subgroups is finitely generated). Also we prove that if G = ? t, K | t ^?1 At = B ?, where K is a finitely generated and infinite nilpotent group and A, B non-trivial infinite proper subgroups of K, then G is not a Howson group. The problem of deciding when an ascending HNN-extension of a finitely generated nilpotent group is a Howson group is still open.     

Central Automorphisms and Inner Automorphisms in Finitely Generated Groups

Let G be a group and Aut_c(G) be the group of all central automorphisms of G. We know that in a finite p-group G, Aut_c(G) = Inn(G) if and only if Z(G) = G′ and Z(G) is cyclic. But we shown that we cannot extend this result for infinite groups. In fact, there exist finitely generated nilpotent groups of class 2 in which G′ =Z(G) is infinite cyclic and Inn(G) < C* = Aut_c(G). In this article, we characterize all finitely generated groups G for which the equality Aut_c(G) = Inn(G) holds.     

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).     

Every finitely generated group is weakly exact

We show that every finitely generated group admits weak analogues of an invariant expectation, whose existence characterizes exact groups. This fact has a number of applications. We show that Hopf G-modules are relatively injective, which implies that bounded cohomology groups with coefficients in all Hopf G-modules vanish in all positive degrees. We also prove a general fixed point theorem for actions of finitely generated groups on ?_∞-type spaces. Finally, we define the notion of weak exactness for certain Banach algebras.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

Identities of PI-Algebras Graded by a Finite Abelian Group

We consider associative PI-algebras over an algebraically closed field of zero characteristic graded by a finite abelian group G. It is proved that in this case the ideal of graded identities of a G-graded finitely generated PI-algebra coincides with the ideal of graded identities of some finite dimensional G-graded algebra. This implies that the ideal of G-graded identities of any (not necessary finitely generated) G-graded PI-algebra coincides with the ideal of G-graded identities of the Grassmann envelope of a finite dimensional (G × ?₂)-graded algebra, and is finitely generated as GT-ideal. Similar results take place for ideals of identities with automorphisms.     

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.