2022/08/03 by Ruiwen Dong, Dong, Ruiwen
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Rings and Algebras (math.RA) #Rings, Modules, and Algebras #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2208.02164
openalex publication_date 2022/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a unitriangular matrix group of nilpotency class at most ten. We show that the Identity Problem (does a semigroup contain the identity matrix?) and the Group Problem (is a semigroup a group?) are decidable in polynomial time for finitely generated subsemigroups of G. Our decidability results also hold when G is an arbitrary finitely generated nilpotent group of class at most ten. This extends earlier work of Babai et al. on commutative matrix groups (SODA'96) and work of Bell et al. on SL(2, ℤ) (SODA'17). Furthermore, we formulate a sufficient condition for the generalization of our results to nilpotent groups of class d > 10. For every such d, we exhibit an effective procedure that verifies this condition in case it is true.