Semigroup Intersection Problems in the Heisenberg Groups

Source abstract

Abstract. We consider two algorithmic problems concerning subsemigroups of Heisenberg groups and, more generally, 2-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 [Formula: see text] over any algebraic number field [Formula: see text]. 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, Beals, Cai, Ivanyos, and Luks (1996), who showed its decidability in commutative matrix groups. We show that Orbit Intersection is decidable in the Heisenberg group [Formula: see text].