The Identity Problem in the special affine group of ${\mathbb{Z}}^2$

Abstract

We consider semigroup algorithmic problems in the Special Affine group $\mathsf{SA}(2,\mathbb{Z})={\mathbb{Z}}^2⋊\mathsf{SL}(2,\mathbb{Z})$, which is the group of affine transformations of the lattice ${\mathbb{Z}}^2$ that preserve orientation. Our paper focuses on two decision problems introduced by Choffrut and Karhumäki (2005): the Identity Problem (does a semigroup contain a neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of $\mathsf{SA}(2,\mathbb{Z})$. We show that both problems are decidable and NP-complete. Since $\mathsf{SL}(2,\mathbb{Z})\le \mathsf{SA}(2,\mathbb{Z})\le \mathsf{SL}(3,\mathbb{Z})$, our result extends that of Bell, Hirvensalo and Potapov (2017) on the NP-completeness of both problems in $\mathsf{SL}(2,\mathbb{Z})$, and contributes a first step towards the open problems in $\mathsf{SL}(3,\mathbb{Z})$.