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

Carl-Fredrik Nyberg-Brodda

doi:10.5802/crmath.554

Article de recherche - Algèbre, Algorithmes et outils informatiques

On the Dehn functions of a class of monadic one-relation monoids
[Sur les fonctions de Dehn d’une classe de monoïdes monadiques à une relation]

Carl-Fredrik Nyberg-Brodda ¹

¹ Laboratoire d’Informatique Gaspard-Monge, Université Gustave Eiffel (Paris)

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 713-730.

Résumé
Abstract

Nous donnons une famille infinie de monoïdes $Π_{N}$ (pour $N = 2, 3, \dots$ ), chacun avec une seule relation de définition de la forme $b U a = a$ , telle que la fonction de Dehn de $Π_{N}$ est au moins exponentielle. Plus précisément, nous démontrons que la fonction de Dehn $\partial_{N} (n)$ de $Π_{N}$ satisfait à $\partial_{N} (n) ⪰ 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 $b U a = 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 \geq 2$ , prouvée récemment par Cadilhac, Chistikov & Zetzsche, nous montrons que chaque $Π_{N}$ a un problème de mots décidable.

We give an infinite family of monoids $Π_{N}$ (for $N = 2, 3, \dots$ ), each with a single defining relation of the form $b U a = a$ , such that the Dehn function of $Π_{N}$ is at least exponential. More precisely, we prove that the Dehn function $\partial_{N} (n)$ of $Π_{N}$ satisfies $\partial_{N} (n) ⪰ 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 $b U a = 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 \geq 2$ , proved recently by Cadilhac, Chistikov & Zetzsche, we show that each $Π_{N}$ has decidable word problem.

Reçu le : 2022-11-13
Révisé le : 2023-07-12
Accepté le : 2023-08-14
Publié le : 2024-09-17

DOI : 10.5802/crmath.554

Classification : 20F10, 20F65

Note : The author is currently working as Attaché Temporaire d’Enseignement et de Recherche at the Laboratoire d’Informatique Gaspard-Monge, Université Gustave Eiffel (Paris, France).

Affiliations des auteurs :

Carl-Fredrik Nyberg-Brodda ¹

¹ Laboratoire d’Informatique Gaspard-Monge, Université Gustave Eiffel (Paris)

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2024__362_G7_713_0,
     author = {Carl-Fredrik Nyberg-Brodda},
     title = {On the {Dehn} functions of a class of monadic one-relation monoids},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {713--730},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.554},
     language = {en},
}

TY  - JOUR
AU  - Carl-Fredrik Nyberg-Brodda
TI  - On the Dehn functions of a class of monadic one-relation monoids
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 713
EP  - 730
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.554
LA  - en
ID  - CRMATH_2024__362_G7_713_0
ER  -

%0 Journal Article
%A Carl-Fredrik Nyberg-Brodda
%T On the Dehn functions of a class of monadic one-relation monoids
%J Comptes Rendus. Mathématique
%D 2024
%P 713-730
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.554
%G en
%F CRMATH_2024__362_G7_713_0

Carl-Fredrik Nyberg-Brodda. On the Dehn functions of a class of monadic one-relation monoids. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 713-730. doi : 10.5802/crmath.554. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.554/

Bibliographie
Cité par

[1] S. I. Adian 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] S. I. Adian 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] S. I. Adian; G. U. Oganesian 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] S. I. Adian; G. U. Oganesian 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] Gilbert Baumslag 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] Gilbert Baumslag Positive one-relator groups, Trans. Am. Math. Soc., Volume 156 (1971), pp. 165-183 | DOI | Zbl

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

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

[9] Michaël Cadilhac; Dmitry Chistikov; Georg Zetzsche 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] Alan Cain; Victor Maltcev Monoids Mon $〈 a, b : a^{α} b^{β} a^{γ} b^{δ} a^{ε} b^{φ} = b 〉$ admit finite complete rewriting systems (2013) (https://arxiv.org/abs/1302.2819v1)

[11] A. Cain; V. Maltcev Monoids Mon $〈 a, b : a^{α} b^{β} a^{γ} b^{δ} = b 〉$ admit finite complete rewriting systems (2013) (https://arxiv.org/abs/1302.0982)

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

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

[14] S. M. Gersten 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] Zeph Grunschlag Algorithms in geometric group theory, Ph. D. Thesis (1999), 127 pages (University of California, Berkeley, USA) | MR

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

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

[18] V. S. Guba 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] Michael Hoffmann; Richard M. Thomas A geometric characterization of automatic semigroups, Theor. Comput. Sci., Volume 369 (2006) no. 1-3, pp. 300-313 | DOI | MR | Zbl

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

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

[22] Markus Lohrey 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] W. Magnus Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann., Volume 106 (1932) no. 1, pp. 295-307 | DOI | Zbl

[24] Wilhelm Magnus; Abraham Karrass; Donald Solitar 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] Carl-Fredrik Nyberg-Brodda The word problem for one-relation monoids: a survey, Semigroup Forum, Volume 103 (2021) no. 2, pp. 297-355 | DOI | MR | Zbl

[26] G. U. Oganesian 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] G. U. Oganesian 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] N. Ruškuc Semigroup Presentations, Ph. D. Thesis, University of St Andrews (1995)

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

[30] X. Wang; W. Xie; H. Lin 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

Cité par Sources :

Commentaires - Politique