Groups with decidable word problem that do not embed in groups with decidable conjugacy problem
- PDF / 236,716 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 213 Views
Groups with decidable word problem that do not embed in groups with decidable conjugacy problem Arman Darbinyan1
Received: 18 February 2020 / Accepted: 11 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We show the existence of finitely presented torsion-free groups with decidable word problem that cannot be embedded in any finitely generated group with decidable conjugacy problem. This answers a well-known question of Collins from the early 1970’s. 1 Introduction Introduced by Max Dehn in 1911, [7], the word problem and the conjugacy problem, along with the group isomorphism problem, are considered as the central algorithmic problems in combinatorial and geometric group theory. Let G = X be a group with a given finite generating set X . If we consider the elements of X ∪ X −1 as formal letters and denote by (X ∪ X −1 )∗ the set of finite words from the alphabet X ∪ X −1 , then each finite word from (X ∪ X −1 )∗ in a natural way represents an element in G, and vice versa: for each element g ∈ G there exists a word (in fact, countably many words) w ∈ (X ∪ X −1 )∗ that represent g, in which case we write w =G 1. It is said that G has decidable word problem if there exists an algorithm that for each w ∈ (X ∪ X −1 )∗ decides whether or not w =G 1. It is said that G has decidable conjugacy problem
The author acknowledges the support by the ERC-grant GroIsRan No. 725773.
B Arman Darbinyan
[email protected]
1
Department of Mathematics, Texas A&M, Blocker Building, 3368 TAMU, 155 Ireland Street, College Station, TX 77840, USA
123
A. Darbinyan
if there exists an algorithm that for each pair of words u, v ∈ (X ∪ X −1 )∗ decides whether or not u and v represent conjugate elements in G. The connections between the word and conjugacy problems have been studied extensively by various authors. It is easy to see that decidability of the conjugacy problem implies decidability of the word problem, nevertheless, in general, the converse is not true. The first examples of finitely generated groups with decidable word problem but undecidable conjugacy problem were constructed by Miller III [14] and by Collins [5]. For other results about connections between the word and conjugacy problems in groups see, for example, [13–15]. If G is a finitely generated group with decidable word problem, then it is an easy observation that all its finitely generated subgroups have decidable word problem as well. In contrast, there are known examples of finitely generated groups with decidable conjugacy problem that have subgroups of index two with undecidable conjugacy problem. See [6,10]. Given a finitely generated group G with decidable word problem, it is natural to ask whether or not G can be embedded into a finitely generated group with decidable conjugacy problem. As observed by Collins, [11], Macintyre constructed groups with torsions that have decidable word problem but cannot be embedded in groups with decidable conjugacy problem. However, that construction in an essential way makes use of
Data Loading...
