OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Section 1 (setting and unnumbered background): embeddings and Higman's theorem: The embedding direction of Higman's theorem for a fixed alphabet and a total enumeration of relators

Computable three-generator presentations embed in finitely presented groups.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A group presentation with three generators may have an infinite list of relators. The question is when such a group can occur as a subgroup of a finitely presented group.

Let AA be the three-letter alphabet A={a,b,c}.A=\{a,b,c\}.(1)✦ An unreduced signed word ww over the alphabet AA of (1) is a finite sequence of letters paired with signs +1+1 or −1-1, including the empty sequence.✦ Let 𝒲\mathcal W be the set of unreduced signed words over AA: 𝒲=(A×{+1,−1})*.\mathcal W=(A\times\{+1,-1\})^*.(2)✦ Let F(A)F(A) be the free group on AA, and write [w]∈F(A)[w]\in F(A) for the element represented by a word ww in (2).

A total computable enumeration of relators r:ℕ→𝒲r:\mathbb N\to\mathcal W is a function for which an algorithm terminates on every input nn and returns r(n)r(n). For a total computable enumeration r:ℕ→𝒲r:\mathbb N\to\mathcal W of relators, define the group GrG_r by the presentation Gr=⟨A∣[r(n)]=1(n∈ℕ)⟩.G_r=\langle A\mid [r(n)]=1\quad(n\in\mathbb N)\rangle.(3)

The Claim

Theorem 1. Let r:ℕ→𝒲r:\mathbb N\to\mathcal W be total and computable, and let GrG_r be the group in (3). There is a finitely presented group KK and an embedding i:Gr↪K.i:G_r\hookrightarrow K.(4)✦

In the paper, the result reads: an embedding is an injective group homomorphism, and Higman’s embedding theorem characterizes the finitely generated subgroups of finitely presented groups as the groups admitting a recursively enumerable set of defining relations.

What Is Checked

The claim (4) is stated over total computable enumerations of unreduced signed words on the fixed alphabet AA.