The Identity Problem in the special affine group of Z2
Ruiwen Dong · 2023
We consider semigroup algorithmic problems in the Special Affine group ${\text{SA}}(2,{\mathbb{Z}}) = {{\mathbb{Z}}^2} \rtimes {\text{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 ${\text{SA}}(2,{\mathbb{Z}})$. We show that both problems are decidable and NP-complete. Since ${\text{SL}}(2,{\mathbb{Z}}) \leq {\text{SA}}(2,{\mathbb{Z}}) \leq {\text{SL}}(3,{\mathbb{Z}})$, our result extends that of Bell, Hirvensalo and Potapov (SODA 2017) on the NP-completeness of both problems in ${\text{SL}}(2,{\mathbb{Z}})$, and contributes a first step towards the open problems in ${\text{SL}}(3,{\mathbb{Z}})$.