2026-07-21T03:18:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23531 2025-10-02T12:57:57Z ddc:004 open_access

Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations Dong, Ruiwen Submonoid Membership lamplighter groups S-unit equations p-automatic sets Knapsack in groups We show that Submonoid Membership is decidable in n-dimensional lamplighter groups (ℤ/pℤ) ≀ ℤⁿ for any prime p and integer n. More generally, we show decidability of Submonoid Membership in semidirect products of the form 𝒴 ⋊ ℤⁿ, where 𝒴 is any finitely presented module over the Laurent polynomial ring 𝔽_p[X₁^{±}, …, X_n^{±}]. Combined with a result of Shafrir (2024), this gives the first example of a group G and a finite index subgroup G̃ ≤ G, such that Submonoid Membership is decidable in G̃ but undecidable in G. To obtain our decidability result, we reduce Submonoid Membership in 𝒴 ⋊ ℤⁿ to solving S-unit equations over 𝔽_p[X₁^{±}, …, X_n^{±}]-modules. We show that the solution set of such equations is effectively p-automatic, extending a result of Adamczewski and Bell (2012). As an intermediate result, we also obtain that the solution set of the Knapsack Problem in 𝒴 ⋊ ℤⁿ is effectively p-automatic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ruiwen Dong 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.154 urn:nbn:de:0030-drops-235316 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.154 eng https://creativecommons.org/licenses/by/4.0/legalcode