On the Dehn functions of a class of monadic one-relation monoids

Nyberg-Brodda, Carl-Fredrik

Comptes Rendus. Mathématique, Tome 362 (2024) no. G7, pp. 713-730

We give an infinite family of monoids ${\Pi }_N$ (for $N=2,3,\cdots$), each with a single defining relation of the form $bUa=a$, such that the Dehn function of ${\Pi }_N$ is at least exponential. More precisely, we prove that the Dehn function ${\partial }_N\left(n\right)$ of ${\Pi }_N$ satisfies ${\partial }_N\left(n\right)⪰N^{n/4}$. This answers negatively a question posed by Cain & Maltcev in 2013 on whether every monoid defined by a single relation of the form $bUa=a$ has quadratic Dehn function. Finally, by using the decidability of the rational subset membership problem in the metabelian Baumslag–Solitar groups $BS(1,n)$ for all $n\ge 2$, proved recently by Cadilhac, Chistikov & Zetzsche, we show that each ${\Pi }_N$ has decidable word problem.

Nous donnons une famille infinie de monoïdes ${\Pi }_N$ (pour $N=2,3,\cdots$), chacun avec une seule relation de définition de la forme $bUa=a$, telle que la fonction de Dehn de ${\Pi }_N$ est au moins exponentielle. Plus précisément, nous démontrons que la fonction de Dehn ${\partial }_N\left(n\right)$ de ${\Pi }_N$ satisfait à ${\partial }_N\left(n\right)⪰N^{n/4}$. Cela répond négativement à une question posée par Cain & Maltcev en 2013, à savoir si tout monoïde défini par une seule relation de la forme $bUa=a$ possède une fonction de Dehn quadratique. Enfin, en utilisant la décidabilité du problème de l’appartenance à un sous-ensemble rationnel dans les groupes métabéliens de Baumslag–Solitar $BS(1,n)$ pour tout $n\ge 2$, prouvée récemment par Cadilhac, Chistikov & Zetzsche, nous montrons que chaque ${\Pi }_N$ a un problème de mots décidable.

Classification : 20F10, 20F65

[1] Adian, S. I. Defining relations and algorithmic problems for groups and semigroups, Proceedings of the Steklov Institute of Mathematics, 85, American Mathematical Society, 1966 (Translated from the Russian by M. Greendlinger) | MR | Zbl

[2] Adian, S. I. Word transformations in a semigroup that is given by a system of defining relations, Algebra Logic, Volume 15 (1976), pp. 379-386 [Algebra i Logika 15, 6 (1976)] | DOI

[3] Adian, S. I.; Oganesian, G. U. On the word and divisibility problems in semigroups with a single defining relation, Math. USSR, Izv., Volume 12 (1978), pp. 207-212 [Izv. Akad. Nauk SSSR Ser. Mat. 42, 2 (1978)] | Zbl

[4] Adian, S. I.; Oganesian, G. U. On the word and divisibility problems for semigroups with one relation, Math. Notes, Volume 41 (1987), pp. 235-240 [Mat. Zametki 41, 3 (1987)] | DOI

[5] Baumslag, Gilbert A non-cyclic one-relator group all of whose finite quotients are cyclic, J. Aust. Math. Soc., Volume 10 (1969), pp. 497-498 | DOI | MR | Zbl

[6] Baumslag, Gilbert Positive one-relator groups, Trans. Am. Math. Soc., Volume 156 (1971), pp. 165-183 | DOI | Zbl | MR

[7] Baumslag, G.; Gersten, S. M.; Shapiro, M.; Short, H. Automatic groups and amalgams, J. Pure Appl. Algebra, Volume 76 (1991) no. 3, pp. 229-316 | DOI | MR | Zbl

[8] Bouwsma, Janet Brugh Semigroups presented by a single relation, Ph. D. Thesis, Pennsylvania State University, USA (1993)

[9] Cadilhac, Michaël; Chistikov, Dmitry; Zetzsche, Georg Rational subsets of Baumslag-Solitar groups, 47th International Colloquium on Automata, Languages, and Programming (Leibniz International Proceedings in Informatics LIPIcs), Volume 168, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, 116 | MR

[10] Cain, Alan; Maltcev, Victor Monoids Mon$\langle a,b:a^{\alpha }{b}^{\beta }{a}^{\gamma }{b}^{\delta }{a}^{\epsilon }{b}^{\phi }=b\rangle$ admit finite complete rewriting systems (2013) (https://arxiv.org/abs/1302.2819v1)

[11] Cain, A.; Maltcev, V. Monoids Mon$\langle a,b:a^{\alpha }{b}^{\beta }{a}^{\gamma }{b}^{\delta }=b\rangle$ admit finite complete rewriting systems (2013) (https://arxiv.org/abs/1302.0982)

[12] Casals-Ruiz, Montserrat; Kazachkov, Ilya; Zakharov, Alexander Commensurability of Baumslag-Solitar groups, Indiana Univ. Math. J., Volume 70 (2021) no. 6, pp. 2527-2555 | DOI | MR | Zbl

[13] Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. Word processing in groups, Jones and Bartlett Publishers, Boston, 1992 | MR | Zbl | DOI

[14] Gersten, S. M. Dehn functions and $l_1$-norms of finite presentations, Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989) (Mathematical Sciences Research Institute Publications), Volume 23, Springer, 1992, pp. 195-224 | DOI | MR | Zbl

[15] Grunschlag, Zeph Algorithms in geometric group theory, Ph. D. Thesis (1999), 127 pages (University of California, Berkeley, USA) | MR

[16] Gray, Robert D.; Steinberg, Benjamin A Lyndon’s identity theorem for one-relator monoids, Sel. Math., New Ser., Volume 28 (2022) no. 3, 59 | DOI | MR | Zbl

[17] Guba, V. S. Conditions for the embeddability of semigroups into groups, Mat. Zametki, Volume 56 (1994) no. 2, pp. 3-14 | DOI | MR | Zbl

[18] Guba, V. S. On a relation between the word problem and the word divisibility problem for semigroups with one defining relation, Izv. Math., Volume 61 (1997) no. 6, pp. 1137-1169 [Izv. Ross. Akad. Nauk Ser. Mat. 61, 6 (1997)] | DOI | Zbl

[19] Hoffmann, Michael; Thomas, Richard M. A geometric characterization of automatic semigroups, Theor. Comput. Sci., Volume 369 (2006) no. 1-3, pp. 300-313 | DOI | MR | Zbl

[20] Ivanov, S. V.; Margolis, S. W.; Meakin, J. C. On one-relator inverse monoids and one-relator groups, J. Pure Appl. Algebra, Volume 159 (2001) no. 1, pp. 83-111 | DOI | Zbl | MR

[21] Kobayashi, Yuji Finite homotopy bases of one-relator monoids, J. Algebra, Volume 229 (2000) no. 2, pp. 547-569 | DOI | MR | Zbl

[22] Lohrey, Markus The rational subset membership problem for groups: a survey, Groups St Andrews 2013 (London Mathematical Society Lecture Note Series), Volume 422, Cambridge University Press, 2015, pp. 368-389 | DOI | MR | Zbl

[23] Magnus, W. Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann., Volume 106 (1932) no. 1, pp. 295-307 | DOI | Zbl | MR

[24] Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald Combinatorial group theory: Presentations of groups in terms of generators and relations, Interscience Publishers [John Wiley & Sons], New York-London-Sydney, 1966 | MR | Zbl

[25] Nyberg-Brodda, Carl-Fredrik The word problem for one-relation monoids: a survey, Semigroup Forum, Volume 103 (2021) no. 2, pp. 297-355 | DOI | MR | Zbl

[26] Oganesian, G. U. Semigroups with one relation and semigroups without cycles, Math. USSR, Izv., Volume 20 (1983), pp. 89-95 [Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982)] | DOI | Zbl

[27] Oganesian, G. U. The isomorphism problem for semigroups with one defining relation, Math. Notes, Volume 35 (1984), pp. 360-363 [Mat. Zametki 35, 5 (1984) | DOI | Zbl

[28] Ruškuc, N. Semigroup Presentations, Ph. D. Thesis, University of St Andrews (1995)

[29] Thue, A. Probleme über Veränderungen von Zeichenreihennach gegebenen Regeln, Christiana Videnskabs-Selskabs Skrifter, Volume 10 (1914) | Zbl

[30] Wang, X.; Xie, W.; Lin, H. Finiteness and Dehn functions of automatic monoids having directed fellow traveller property, Semigroup Forum, Volume 79 (2009) no. 1, pp. 15-21 | DOI | MR | Zbl