Decidability of the membership problem for Baumslag Solitar group $BS(1,2)$

Question

Is the subsemigroup or subgroup membership problem for $BS(1,2)$ decidable ?

That is, given elements $g,g_1,g_2,\dots,g_n$ from $BS(1,2)$, is there a decision procedure to check whether $g$ belongs to the semigroup/subgroup generated by $\{g_1,g_2,\dots,g_n\}$?

Note that the decidability of the semigroup membership implies the decidability of subgroup memebership problem and the undecidability of the subgroup membership problem implies the undecidability of the semigroup membership problem.

Answer 1

There are two questions here, the "group" question and the "semigroup" question. The answer is "yes" to the group question and "I don't know" to the semigroup question.

The group question is often referred to as the generalised word problem (and archaically as the occurrence problem). A group is metabelian if its derived subgroup is abelian. The group $BS(1, 2)$ (and more generally $BS(1, n)$) is a metabelian group. Romanovskii proved that the generalised word problem is soluble for metabelian groups (the reference is: Romanovskii, N.S. Some algorithmic problems for solvable groups. Algebra i Logika, (1974) 13(1):26–34.). Hence, the answer to the "group" question is "yes".

For the semigroup question, I don't know the answer. In particular, you cannot just use "metabelian" as we did for the group question. This is because the free metabelian group of rank two has undecidable subsemigroup membership problem (the reference is: Lohrey, M. & Steinberg, B. Tilings and Submonoids of Metabelian Groups. Theory Comput. Syst. (2011) 48: 411-427. doi).

Answer 2

To extend the above answer from user1729, the subgroup membership problem is decidable for any Baumslag-Solitar group $BS(m,n)$, as they are all HNN-extensions $\mathbb{Z} \ast_{\mathbb{Z}}$, and so decidability follows by Theorem 1.1 of Foldings, graphs of groups and the membership problem, as $\mathbb{Z}$ is polycyclic-by-finite.

I think that the submonoid membership problem for Baumslag-Solitar groups is open in general. As mentioned in the comments, the problem of deciding membership in positively generated submonoids is decidable in $BS(m, n)$.

Note that as seen in the above answer, the problem of deciding membership in a finitely generated subgroup is sometimes called the generalized word problem, although this historically refers to the problem of deciding membership in one of the finitely many subgroups generated by subsets of the generating set, and so can occasionally cause confusion if the distinction is not made. For example, in $F_2 \times F_2$ one can decide membership in any subgroup generated by a subset of a generating set, but there are finitely generated subgroups of it for which membership is undecidable (a famous result due to Mikhailova).

Update 23 June 2020: A preprint appeared today, which claims that the rational subset membership problem is decidable for all solvable Baumslag-Solitar groups $BS(1, n)$. In particular, the submonoid membership problem is decidable for $BS(1, 2)$, as any f.g. submonoid is a rational subset.