Submonoid Membership in n-dimensional lamplighter groups and S-unit equations

Abstract

We show that Submonoid Membership is decidable in n-dimensional lamplighter groups $(\mathbb{Z}/p\mathbb{Z})\wr {\mathbb{Z}}^n$ for any prime $p$ and integer $n$. More generally, we show decidability of Submonoid Membership in semidirect products of the form $\mathcal{Y}⋊{\mathbb{Z}}^n$, where $\mathcal{Y}$ is any finitely presented module over the Laurent polynomial ring ${\mathbb{F}}_p[X_1^{\pm },\dots ,X_n^{\pm }]$. Combined with a result of Shafrir (2024), this gives the first example of a group $G$ and a finite index subgroup $\tilde{G}\le G$, such that Submonoid Membership is decidable in $\tilde{G}$ but undecidable in $G$. To obtain our decidability result, we reduce Submonoid Membership in $\mathcal{Y}⋊{\mathbb{Z}}^n$ to solving S-unit equations over ${\mathbb{F}}_p[X_1^{\pm },\dots ,X_n^{\pm }]$-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 $\mathcal{Y}⋊{\mathbb{Z}}^n$ is effectively $p$-automatic.

Full version of conference paper at ICALP'25