Undecidability of the Diophantine problem for one-relator groups and one-relation monoids

2026/08/03 by Carl-Fredrik Nyberg-Brodda
Mathematics · #math.GR #math.RA

paper · pdf

14 pages. Comments welcome!

arxiv created 2026/08/03 · arxiv updated 2026/08/04

Abstract

We prove that the Diophantine problem, i.e. the problem of solving equations with coefficients, in one-relator groups and one-relation monoids is undecidable in general. Specifically, we show that for all d ≥ 2, the Diophantine problem for the Baumslag-Gersten group B_d = BG(1,d) and for a closely related one-relation monoid M_d are both undecidable. Both results are obtained by an encoding of a recent undecidability result due to Rybalov.

Citations

• The Diophantine problem in the Baumslag-Gersten group
• HNN extensions and embedding theorems for groups
• The theory of one-relator groups: history and recent progress
• The Adian-Rabin Theorem -- An English translation
• On the Diophantine problem in some one-relator groups
• A word-hyperbolic special monoid with undecidable Diophantine problem
• The Word Problem for One-relation Monoids: A Survey
• Solution sets for equations over free groups are EDT0L languages
• The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable