Algorithmic problems for subsemigroups of infinite groups

Thesis

This thesis is concerned with several algorithmic problems for subsemigroups of infinite groups. The main objective is to construct algorithms that decide various properties of finitely generated subsemigroups of a given infinite group G (for example, a matrix group). Such problems might not be decidable in general. In fact, they gave rise to some of the earliest undecidability results in algorithmic theory. Nevertheless, when the group G admits additional structures, many algorithmic problems become decidable for its subsemigroups. In this thesis, we study the decidability and the complexity of these algorithmic problems in the cases where G is nilpotent, metabelian, or represented as a low-dimensional matrix group.

Two of the main problems we consider are the Identity Problem and the Group Problem. Given a finite subset X of a group G, the Identity Problem asks whether the semigroup ⟨X⟩ generated by X contains the neutral element, and the Group Problem asks whether this semigroup is a group. We show that both problems are decidable in finitely generated nilpotent groups of class at most ten, and in PTIME if the input is given as unitriangular matrices. We also show the decidability of these problems in finitely generated metabelian groups, as well as their NP-completeness in the special affine group SA(2,Z).

Apart from the Identity Problem and the Group Problem, we also consider Semigroup Intersection and Orbit Intersection. Given two finite subsets X and H of the group G, Semigroup Intersection asks whether the semigroups ⟨X⟩, ⟨H⟩ generated by X and H have empty intersection, while Orbit Intersection asks whether the sets S · ⟨X⟩ and T · ⟨H⟩ intersect for given elements S, T ∈ G. We show that Semigroup Intersection is decidable in class two nilpotent groups (PTIME if the input is given as unitriangular matrices), and that Orbit Intersection is decidable in the Heisenberg group H3(Q).

We apply a large variety of mathematical tools in the study of these problems, ranging from Lie algebra, algebraic geometry and number theory, to combinatorics, graph theory and convex geometry. By adding these techniques into the toolbox, we are able to significantly advance the current state of art in the algorithmic theory of semigroups.

Authors: Dong, R

• DOI: 10.5287/ora-kzb71yxky
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: computational group theory; infinite groups; decidability; semigroups
• Subjects: Combinatorial group theory; Logic