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

2022/10/28 by Carl‐Fredrik Nyberg‐Brodda, Nyberg-Brodda, Carl-Fredrik
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #20F65 (secondary) #20M05 (primary) 20F10 #Chemical Synthesis and Analysis #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Rings and Algebras (math.RA) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2210.16123

openalex publication_date 2022/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an infinite family of monoids Π_N (for N=2, 3, …), each with a single defining relation of the form bUa = a, such that the Dehn function of Π_N is at least exponential. More precisely, we prove that the Dehn function ∂_N(n) of Π_N satisfies ∂_N(n) \succeq 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 ≥ 2, proved recently by Cadilhac, Chistikov & Zetzsche, we show that each Π_N has decidable word problem.

Related

• The Word Problem for One-relation Monoids: A Survey
• From Ideal Membership Problem for polynomial rings to Dehn Functions of Metabelian Groups
• Polynomially-bounded Dehn functions of groups
• The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable
• The Dehn function of Baumslag's Metabelian Group