Semigroup intersection problems in the Heisenberg groups (Q6654128)

Let \(G\) be a group of matrices over an algebraic number field \(\mathbb{K}\), \(\mathcal{G}\) a subset of \(G\) and \(\langle \mathcal{G} \rangle_{\mathsf{s}}\) be the semigroup generated by \(\mathcal{G}\).\N\NIn this paper, the author consider the following two decision problems for the Heisenberg groups \(\mathrm{H}_{n}(\mathbb{K})\) and for nilpotent groups of class 2. (1) The Intersection Emptiness problem: given \(M\) finite sets of matrices \(\mathcal{G}_{1}, \ldots \mathcal{G}_{M}\), decide whether \(\bigcap_{i=1}^{M}\langle \mathcal{G}_{i}\rangle_{\mathsf{s}} = \emptyset\); (2) the Orbit Intersection problem: given two finite sets of matrices \(\mathcal{G}\), \(\mathcal{H}\) and matrices \(S, T \in G\), decide whether \(T \cdot \langle \mathcal{G} \rangle_{\mathsf{s}} \cap S \cdot \langle \mathcal{H} \rangle_{\mathsf{s}}=\emptyset\).\N\NIn a paper of \textit{A. Markov} [Dokl. Akad. Nauk SSSR, n. Ser. 57, 539-542 (1947; Zbl 0037.29706)], the undecidability of Intersection Emptiness was shown for two sets of \(4 \times 4\) integer matrices (the proof depends directly on a result by \textit{E. L. Post} [Bull. Am. Math. Soc. 52, 264-268 (1946; Zbl 0063.06329)], as one can see in the fine MR review at Markov's work by M. H. A. Newman [MR0022538]).\N\NLet \(\mathsf{UT}(n,\mathbb{Q})\) be the group of \(n \times n\) upper triangular rational matrices with ones along the diagonal. The first main result in this paper is Theorem 2.1: Let \(G\) be a 2-step nilpotent subgroup of \(\mathsf{UT}(n,\mathbb{Q})\) for some \(n\). Given finite subsets \(\mathcal{G}_{1}, \ldots, \mathcal{G}_{M}\) of \(G\), it is decidable in polynomial time whether \(\bigcap_{i=1}^{M}\langle \mathcal{G}_{i}\rangle_{\mathsf{s}} = \emptyset\). The second main result is Theorem 2.2: Intersection Emptiness is decidable (i) in polynomial time, in the Heisenberg groups \(\mathsf{H}_{n}(\mathbb{K})\) over a fixed algebraic number field \(\mathbb{K}\); (ii) in all finitely generated 2-step nilpotent groups, given by a finite presentation.\N\NIn Theorem 2.3 the author proves that Orbit Intersection is decidable in the Heisenberg group \(\mathsf{H}_{3}(\mathbb{Q})\).