The Submonoid Membership problem in a group G asks, given a finitely generated submonoid M of G and an element g of G, whether g is contained in M. In many other decision problems (such as Subgroup Membership and Rational Subset Membership), decidability is preserved under finite extensions of the group G. In contrast, decidability of Submonoid Membership in G is not known to imply its decidability in finite extensions of G. In fact, in this talk we will give the first counterexample to this: we construct G as a quotient of the 7-dimensional lamplighter group, so that Submonoid Membership is decidable in G but undecidable in some finite extension of G (Shafrir 2024). We will show decidability of Submonoid Membership in quotients of n-dimensional lamplighter groups, by reducing it to solving '``S-unit equations'' in modules over rings of prime characteristic. We extend Derksen's idea of showing that the solution sets of these S-unit equations are effectively p-automatic, using a combination of automata theory, commutative algebra and number theory.
 

Date and Venue

Start Date
Venue
Online
End Date

Speaker

Ruiwen Dong

Speaker's Institution

Magdalen College, University of Oxford

Files

Area

Semigroups, Automata and Languages