An explicit algorithm for the Higman Embedding Theorem

V. H. Mikaelian · 2025

Read An explicit algorithm for the Higman Embedding Theorem by V. H. Mikaelian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04347.txt.

Description

Mikaelian gives, in a solo 2025 paper, an explicit algorithm for the Higman Embedding Theorem, a classic result in group theory. The theorem states that a finitely generated group can be embedded in a finitely presented group if and only if the group is recursive. The original proof shows that such a host group exists, but gives no clear recipe for building it.

The new algorithm takes any recursive group, given by its effectively enumerable generators and recursively enumerable relations, and writes out the finitely presented host group in full. The host can even be chosen to have just two generators. The method has been applied to the additive group of rational numbers, a case mentioned as open by earlier authors. It rests on standard constructions such as free products with amalgamation and HNN extensions, plus new modifications. The paper also analyzes which steps of the original proof remain non-explicit.

Catalog record

CREATORV. H. Mikaelian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE223 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04347

Browse the full library · About the Tower of Babel