Decidability problem for exponential equations in finitely presented groups. (English) Zbl 1522.20126
Let \(G\) be a group. An exponential equation over \(G\) is an equation of the form
\[
(a_{1}g_{1}^{x_{1}}a_{2}g_{2}^{x_{2}} \ldots a_{n}g_{n}^{x_{n}}=1
\]
where \(a_{1}, g_{1}, \dots, a_{n}, g_{n} \in G\) and \(x_{1},\dots, x_{n}\) are variables which take values in \(\mathbb{Z}\).
Let \(G\) be a recursively presented group, and let \(n\) be a fixed natural number. The \(\mathsf{EE}[n]\)-problem for \(G\) is the following: given an exponential equation over \(G\) with \(n\) variables, decide if it has a solution or not. By \(\mathsf{WP}\) and \(\mathsf{CP}\), the authors denote the word and the conjugacy problems for \(G\), respectively.
From the equivalence \(g=1 \Leftrightarrow (\exists z \in \mathbb{Z})(g=1^{z})\) it follows that \(\mathsf{EE}[1] \Rightarrow \mathsf{WP}\). J. McCool proved in [Can. J. Math. 22, 836–838 (1970; Zbl 0216.08702)] that the implication \(\mathsf{WP} \Rightarrow \mathsf{EE}[1]\) is not valid in general in the class of recursively presented groups. A. Yu. Ol’shanskii and M. V. Sapir in [Groups Geom. Dyn. 16, No. 4, 1289–1339 (2022; Zbl 1511.20165)] have found a finitely presented example with decidable \(\mathsf{CP}\) and undecidable \(\mathsf{EE}[1]\).
The main result of this paper is Theorem A: There exists a finitely presented group with decidable \(\mathsf{EE}[1]\) and undecidable \(\mathsf{EE}[2]\). Moreover, this group has decidable conjugacy problem.
Let \(G\) be a recursively presented group, and let \(n\) be a fixed natural number. The \(\mathsf{EE}[n]\)-problem for \(G\) is the following: given an exponential equation over \(G\) with \(n\) variables, decide if it has a solution or not. By \(\mathsf{WP}\) and \(\mathsf{CP}\), the authors denote the word and the conjugacy problems for \(G\), respectively.
From the equivalence \(g=1 \Leftrightarrow (\exists z \in \mathbb{Z})(g=1^{z})\) it follows that \(\mathsf{EE}[1] \Rightarrow \mathsf{WP}\). J. McCool proved in [Can. J. Math. 22, 836–838 (1970; Zbl 0216.08702)] that the implication \(\mathsf{WP} \Rightarrow \mathsf{EE}[1]\) is not valid in general in the class of recursively presented groups. A. Yu. Ol’shanskii and M. V. Sapir in [Groups Geom. Dyn. 16, No. 4, 1289–1339 (2022; Zbl 1511.20165)] have found a finitely presented example with decidable \(\mathsf{CP}\) and undecidable \(\mathsf{EE}[1]\).
The main result of this paper is Theorem A: There exists a finitely presented group with decidable \(\mathsf{EE}[1]\) and undecidable \(\mathsf{EE}[2]\). Moreover, this group has decidable conjugacy problem.
Reviewer: Egle Bettio (Venezia)
MSC:
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F70 | Algebraic geometry over groups; equations over groups |
| 20F05 | Generators, relations, and presentations of groups |
References:
| [1] | Bier, A., and Bogopolski, O., Exponential equations in acylindrically hyperbolic groups. Preprint, 2021. arXiv:2106.11385v1 |
| [2] | Bilanovic, I., Chubb, J., and Roven, S., Detecting properties from presentations of groups. Arch. Math. Log.59(2020), 293-312. · Zbl 1481.03043 |
| [3] | Donald, J., Collins, on embedding groups and the conjugacy problem. J. Lond. Math. Soc. (2)1(1996), 674-682. · Zbl 0185.05101 |
| [4] | Dudkin, F. and Treyer, A., Knapsack problem for Baumslag-Solitar groups. Siberian J. Pure Appl. Math.18(2018), no. 4, 43-55. · Zbl 1438.20033 |
| [5] | Figelius, M., Ganardi, M., Lohrey, M., and Zetzsche, G., The complexity of knapsack problems in wreath products. In: Proceedings of the 47th international colloquium on automata, languages, and programming, ICALP 2020, Leibniz International Proceedings in Informatics, 168, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Germany, 2020, pp. 126:1-126:18. |
| [6] | Frenkel, E., Nikolaev, A., and Ushakov, A., Knapsack problems in products of groups. J. Symb. Comput.76(2016), 96-108. · Zbl 1401.20031 |
| [7] | Ganardi, M., König, D., Lohrey, M., and Zetzsche, G., Knapsack problems for wreath products. In: Proceedings of STACS (2018), Leibniz International Proceedings in Informatics, 96, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Germany, 2018, pp. 1-13. · Zbl 1491.20078 |
| [8] | Kharlampovich, O., The word problem for the Burnside varieties. J. Algebra173(1995), 613-621. · Zbl 0831.20040 |
| [9] | König, D., Lohrey, M., and Zetzsche, G., Knapsack and subset sum problems for nilpotent, polycyclic, and co-context-free groups. In: Algebra and computer science, Contemporary Mathematics, 677, American Mathematical Society, Providence, RI, 2016, pp. 138-153. · Zbl 1392.68205 |
| [10] | Lohrey, M., Rational subsets of unitriangular groups. Int. J. Algebra Comput.25(2015), nos. 1-2, 113-121. · Zbl 1330.20048 |
| [11] | Lohrey, M., Knapsack in hyperbolic groups. J. Algebra545(2020), no. 1, 390-415. · Zbl 1485.20085 |
| [12] | Lohrey, M. and Zetzsche, G., Knapsack in graph groups, HNN-extensions and amalgamated products. Theory Comput. Syst.62(2018), no. 1, 192-246. · Zbl 1386.68073 |
| [13] | Lohrey, M. and Zetzsche, G., Knapsack and the power word problem in solvable Baumslag-Solitar groups. In: Proceedings of the 45th international symposium on mathematical foundations of computer science, MFCS 2020, Leibniz International Proceedings in Informatics, 170, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Germany, 2020, pp. 67:1-67:15. · Zbl 1542.20138 |
| [14] | Lyndon, R. C. and Schupp, P. E., Combinatorial group theory, Springer, Berlin, 1977. · Zbl 0368.20023 |
| [15] | Mccool, J., Unsolvable problems in groups with solvable word problem. Can. J. Math.22(1970), 836-838. · Zbl 0216.08702 |
| [16] | Mishchenko, A. and Treier, A., Knapsack problem for nilpotent groups. Groups Complex. Cryptol.9(2017), no. 1, 87-98. · Zbl 1382.20039 |
| [17] | Myasnikov, A., Nikolaev, A., and Ushakov, A., Knapsack problems in groups. Math. Comp.84(2015), no. 292, 987-1016. · Zbl 1392.68207 |
| [18] | Ol’Shanskii, A. Yu., SQ-universality of hyperbolic groups. Mat. Sb.186(1995), no. 8, 119-132. · Zbl 0864.20023 |
| [19] | Ol’Shanskii, A. Y. and Sapir, M. V., The conjugacy problem and Higman embeddings. Mem. Amer. Math. Soc.170(2004), no. 804, vii + 131. · Zbl 1055.20023 |
| [20] | Ol’Shanskii, A. Y. and Sapir, M. V., Subgroups of finitely presented groups with solvable conjugacy problem. Int. J. Algebra Comput.15(2005), nos. 5-6, 1-10. · Zbl 1100.20029 |
| [21] | Ol’Shanskii, A. Yu. and Sapir, M. V., Algorithmic problems in groups with quadratic Dehn function. Preprint, 2020. arXiv:2012.10417v1 · Zbl 1168.20016 |
| [22] | Soare, R. I., Turing computability. Theory and applications, Springer, Berlin, 2016. · Zbl 1350.03001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
