论文标题
海森堡小组的半群交叉路口问题
Semigroup intersection problems in the Heisenberg groups
论文作者
论文摘要
我们考虑了有关海森堡组的子序列以及更普遍的两步nilpotent群体的两个算法问题。第一个问题是交点空虚，它询问有限数量的有限生成的半群是否具有空的交集。马尔可夫在1940年代首次研究了这个问题。我们表明，在任何代数数字$ \ mathbb {K k} $的Heisenberg组的直接产品中，在Heisenberg组$ \ operatatorName {h} _ {n} _ {h} _ {n}（\ mathbb {k}）$中，相交空虚是可决定的。我们还将可决定性结果扩展到任意有限生成的2步尼尔植物组。 第二个问题是轨道相交，它询问在两个半群中乘以两个矩阵的轨道是否相互相交。这个问题首先由Babai等人研究。 （1996年），他在交换矩阵组中表现出其可决定性。我们表明，在Heisenberg Group $ \ operatatorName {h} _ {3}（\ Mathbb {q}）$中，轨道交点是可决定的。
We consider two algorithmic problems concerning sub-semigroups of Heisenberg groups and, more generally, two-step nilpotent groups. The first problem is Intersection Emptiness, which asks whether a finite number of given finitely generated semigroups have empty intersection. This problem was first studied by Markov in the 1940s. We show that Intersection Emptiness is PTIME decidable in the Heisenberg groups $\operatorname{H}_{n}(\mathbb{K})$ over any algebraic number field $\mathbb{K}$, as well as in direct products of Heisenberg groups. We also extend our decidability result to arbitrary finitely generated 2-step nilpotent groups. The second problem is Orbit Intersection, which asks whether the orbits of two matrices under multiplication by two semigroups intersect with each other. This problem was first studied by Babai et al. (1996), who showed its decidability within commutative matrix groups. We show that Orbit Intersection is decidable within the Heisenberg group $\operatorname{H}_{3}(\mathbb{Q})$.
