On finitely presented expansions of semigroups, groups, and algebras

Finitely presented algebraic systems, e.g., groups, are fundamental in algebra and computation. They have computably enumerable word equality problems and are finitely generated (f.g.). We refer to f.g. algebraic systems with computably enumerable word equality problems as computably enumerable. Not all computably enumerable, f.g. algebraic systems are finitely presented. This talk explores the quest for finitely presented expansions of computably enumerable, f.g. algebraic systems. The expansion of algebraic systems, such as transforming groups into rings or introducing automorphisms, is an important technique in algebra, model theory, and theoretical computer science. Bergstra and Tucker proved that all computably enumerable algebraic systems with decidable word problems have finitely presented expansions. They, along with Goncharov, independently asked if every f.g. computably enumerable algebraic system has a finitely presented expansion. In this talk, we provide examples of f.g. computably enumerable semigroups, groups, and algebras that lack finitely presented expansions, thus answering the question of Bergstra-Tucker and Goncharov. Additionally, we construct examples of residually finite, infinite, and algorithmically finite group, answering Miasnikov and Osin’s question. These constructions rely on the interplay between key concepts from computability (e.g., simple and immune sets) and algebra (e.g., residual finiteness and the Golod-Shafaverevich theorem). This work is joint with A. Miasnikov.