Subgroup and Submonoid Membership in the lampshuffler of $\mathbb{Z}$

Abstract

The lampshuffler group of $\mathbb{Z}$ is the semidirect product $\mathrm{FSym}(\mathbb{Z})⋊\mathbb{Z}$, which consists of all permutations of $\mathbb{Z}$ that act as a translation outside a finite set. This infinite permutation group naturally contains as subgroups the wreath products $H\wr \mathbb{Z}$ for every finite group $H$. We prove that the Subgroup Membership Problem, and more generally, the Submonoid Membership Problem, are decidable in $\mathrm{FSym}(\mathbb{Z})⋊\mathbb{Z}$. Our proof reduces Subgroup and Submonoid Membership in $\mathrm{FSym}(\mathbb{Z})⋊\mathbb{Z}$ to Subgroup Membership in the wreath products $H\wr \mathbb{Z}$, which was shown to be decidable by Lohrey, Steinberg and Zetzsche (2015).

arXiv commentappears in SODA'27