论文标题
有限类的nilpotent组中的身份问题
The Identity Problem in nilpotent groups of bounded class
论文作者
论文摘要
令$ g $为nilpotency类的unitriangular矩阵组。我们表明，身份问题（半群是否包含身份矩阵？），组问题（半群是一个组吗？）在多项式时间内可决定有限生成的$ g $。当$ g $是一个任意有限生成的nilpotent class的班级时，我们的可定性结果也会得出。这扩展了Babai等人的早期工作。在贝尔等人的交换矩阵组（苏打水组）和工作中。在$ \ mathsf {sl}（2，\ mathbb {z}）$（SODA'17）上。此外，我们为将结果概括为$ d> 10 $的nilpotent组制定了足够的条件。对于每一个这样的$ d $，我们都会展示一个有效的程序，以验证这种情况，以防万一。
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 $\mathsf{SL}(2, \mathbb{Z})$ (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.
