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

lmcs:13602 - Logical Methods in Computer Science, June 9, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:21)2025
The Identity Problem in the special affine group of $\mathbb{Z}^2$Article

Authors: Ruiwen Dong

We consider semigroup algorithmic problems in the Special Affine group $\mathsf{SA}(2, \mathbb{Z}) = \mathbb{Z}^2 \rtimes \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}) \leq \mathsf{SA}(2, \mathbb{Z}) \leq \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})$.


Volume: Volume 21, Issue 2
Secondary volumes: Selected Papers of the 38th ACM/IEEE Symposium on Logic in Computer Science (LICS 2023)
Published on: June 9, 2025
Accepted on: March 29, 2025
Submitted on: May 16, 2024
Keywords: Mathematics - Group Theory, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics

Consultation statistics

This page has been seen 1278 times.
This article's PDF has been downloaded 440 times.