International Journal of Algebra and Computation

We develop a theory of generalized presentations of groups and give a generalized presentation of the automorphism group of the free group of countable rank, Aut(F_ω).

This article concerns a class of groups of Fibonacci type introduced by Johnson and Mawdesley that includes Conway's Fibonacci groups, the Sieradski groups, and the Gilbert–Howie groups. This class of groups provides an interesting focus for developing the theory of cyclically presented groups and, following questions by Bardakov and Vesnin and by Cavicchioli, Hegenbarth, and Repovš, they have enjoyed renewed interest in recent years. We survey results concerning their algebraic properties, such as isomorphisms within the class, the classification of the finite groups, small cancellation properties, abelianizations, asphericity, connections with Labeled Oriented Graph groups, and the semigroups of Fibonacci type. Further, we present a new method of proving the classification of the finite groups that deals with all but three groups.

Let G be a graph product of a collection of groups and H be the direct product of the same collection of groups, so that there is a natural surjection p : G → H. The kernel of this map p is called a graph product kernel. We prove that a graph product kernel of countable groups is special, and a graph product of finite or cyclic groups is virtually cocompact special in the sense of Haglund and Wise. The proof of this yields conditions for a graph over which the graph product of arbitrary nontrivial groups (or some cyclic groups, or some finite groups) contains a hyperbolic surface group. In particular, the graph product of arbitrary nontrivial groups over a cycle of length at least five, or over its opposite graph, contains a hyperbolic surface group. For the case when the defining graphs have at most seven vertices, we completely characterize right-angled Coxeter groups with hyperbolic surface subgroups.

The Whitehead problem is solved in the class of toral relatively hyperbolic groups G (i.e. torsion-free relatively hyperbolic groups with abelian parabolic subgroups): there is an algorithm which, given two finite tuples (u₁,…,u_n) and (v₁,…,v_n) of elements of G, decides whether there is an automorphism of G taking u_i to v_i for all i.

We show that the Magnus embedding, which embeds the free solvable group S_{d, r} of rank r and degree d into the wreath product ℤ^r ≀ S_{d-1, r}, is a quasi-isometry.

We give an example of a conjugacy separable, but not subgroup separable group. It is an adaptation of an example of Tavgen and the third author from [Closed orbits and finite approximability with respect to conjugacy of free amalgamated products, Math. Notes58 (1995) 1042–1048] to a theorem of Raptis [On finiteness conditions of certain graphs of groups, Internat. J. Algebra Comput.5 (1995) 719–724].

It is shown that the compressed word problem of a graph product of finitely generated groups is polynomial time Turing-reducible to the compressed word problems of the vertex groups. A direct corollary of this result is that the word problem for the automorphism group of a right-angled Artin group or a right-angled Coxeter group can be solved in polynomial time. Moreover, it is shown that a restricted variant of the simultaneous compressed conjugacy problem is polynomial time Turing-reducible to the same problem for the vertex groups. A direct corollary of this result is that the word problem for the outer automorphism group of a right-angled Artin group or a right-angled Coxeter group can be solved in polynomial time. Finally, it is shown that the compressed variant of the ordinary conjugacy problem can be solved in polynomial time for right-angled Artin groups.

Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic algebra and algorithmic group theory: (1) We define a modified reduction procedure on power circuits which runs in quadratic time, thereby improving the known cubic time complexity. The improvement is crucial for our other results. (2) We improve the complexity of the Word Problem for the Baumslag group to cubic time, thereby providing the first practical algorithm for that problem. (The algorithm has been implemented and is available in the CRAG library.) (3) The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of power circuits.