Higman embedding theorems

September 19, 2026

Higman embedding theorems

The celebrated Higman embedding theorem says that any finitely generated group embeds in a finitely presented group if and only if it is recursively presented (there is an algorithm to write down the relators). It was known previously that subgroups of finitely presented groups have to be recursively presented, but it took a lot of work and ingenuity to find the desired embedding for any finitely generated recursively presented group.

Finite presentability is considered nowadays a homotopical finiteness property: it says that the classifying space can be taken to have finite 2-skeleton. There are also homological finiteness properties, and the analogue of finite presentability is $\mathrm{FP}_2$ (over $\mathbb{Z}$ but this will always be the coefficient ring in this post), meaning that the augmentation ideal $I_G:= \ker (\mathbb Z G \to \mathbb Z)$ is finitely presented as a module over the integral group ring. A landmark paper of Bestvina--Brady shows that $\mathrm{FP}_2$ is much weaker than being finitely presented. Leary later showed another way in which it is much weaker:

Theorem 1 (Leary): Every countable group embeds in a group of type $\mathrm{FP}_2$.

His proof mimics Valiev's proof of the Higman embedding theorem, exposed in Lyndon and Schupp's classic text 'Combinatorial group theory'. Leary also points out that this is a rare instance of a theorem true for all countable groups (there are a couple of other examples on this blog), and asks, in view of Gromov's provocative assertion that all such theorems should be trivial, whether there is an easier proof. In this blog post I will try to give a brief sketch of both theorems simultaneously.

First, let me be more precise about what recursively presented means.

Diophantine Sets

Definition: A subset $ S $ of $ \mathbb{Z} ^n $ is said to be Diophantine if there exists a polynomial
\[
P(X_1, \ldots, X_n; Y_1, \ldots, Y_m)
\]
such that
\[
(s_1, \ldots, s_n) \in S \text{ if and only if } P(s_1, \ldots, s_n; Y_1, \ldots, Y_m) \text{ has an integer root}.
\]
We say that $ P $ enumerates $ S $.

As a non-trivial example, the set $ \mathbb{N} $ of natural numbers is Diophantine, since Lagrange's famous theorem says that an integer is non-negative if and only if it is a sum of four squares. Thus $ s \in \mathbb{N} $ if and only if the polynomial
\[
P(s; Y_1, \ldots, Y_4) = Y_1^2 + \cdots + Y_4^2 - s
\]
has a root.

Hilbert's Tenth Problem and Recursive Enumerability

One of the most famous decision problems is Hilbert's Tenth Problem. Hilbert asked for an algorithm which, when given a polynomial $ P(X_1, \ldots, X_m) $ with integer coefficients, decides whether or not $ P $ has an integer root. Matiyasevich showed that no such algorithm exists. In settling Hilbert's Tenth Problem, Matiyasevich actually established much more. Namely, all recursively enumerable sets are Diophantine! This is now a basic result of recursive function theory.

Definition: A set $ S \subseteq \mathbb{Z} ^n $ is recursively enumerable if $ S $ is Diophantine. The set $ S $ is said to be recursive if both $ S $ and its complement, $ \mathbb{Z} ^n - S $, are recursively enumerable.

The first thing we shall do is to exhibit a recursively enumerable set which is not recursive. The way to do this is to "arithmetise" one's formalism by assigning numbers to everything in sight. Since this was first done by Gödel, the numbers assigned are called "Gödel numbers." We shall assign positive integers to polynomials as follows. The function $ \alpha : \mathbb{Z} \to \mathbb{N} $ defined by
\[
\alpha(z) =
\begin{cases}
2|z| + 1 & \text{if } z \leq 0 \\
2|z| & \text{if } z > 0
\end{cases}
\]
is clearly one-to-one.

Fix $ X_0, X_1, \ldots, X_n, \ldots $ as our infinite list of variables. Assign to each monomial term
\[
T = cX_{i_1}^{e_1} \cdots X_{i_n}^{e_n}
\]
where $ 0 \neq c \in \mathbb{Z} $, each $ e_i \geq 1 $, and $ i_1 < i_2 < \cdots < i_n $, the number
\[
\beta(T) = 2^{\alpha(c)} p_{i_1+2}^{e_1} \cdots p_{i_n+2}^{e_n}
\]
where $ p_j $ is the $ j $-th prime. (Thus $ \beta(5X_0^3X_4^2) = 2^{10}3^{13}12^3 $.)

Each non-zero polynomial $ P $ in the $ X_i $ can be uniquely written as a sum of monomial terms
\[
P = T_1 + \cdots + T_k
\]
where the $ T_i $ do not differ only in their coefficients from $ \mathbb{Z} $, and $ \beta(T_1) < \cdots < \beta(T_k) $. To the polynomial $ P $ written as above, assign the number
\[
\gamma(P) = 2^{\beta(T_1)} \cdots p_k^{\beta(T_k)}.
\]
Certainly, given any non-zero polynomial $ P $ we can effectively calculate its Gödel number $\gamma(P)$.

Theorem 2: There exists a recursively enumerable non-recursive set of positive integers.

Proof: Let
\[
S = \{\gamma(P(X_{i_1}, \ldots, X_{i_n})) : P(e, X_{i_2}, \ldots, X_{i_n}) \text{ has a root where } e = \gamma(P)\}.
\]
In words, $ S $ is the set of Gödel numbers of polynomials such that, when their own number is substituted for the first variable occurring, the resulting polynomial has a root. The set $ S $ is clearly intuitively effectively enumerable. On the other hand,
$ S^* = \mathbb{Z} - S = \{z : z \text{ is not in the range of } \gamma \text{ or } z = \gamma(P(X_{i_2}, \ldots, X_{i_n})) \text{ but } P(\gamma(P), X_{i_2}, \ldots, X_{i_n}) \text{ does not have a root}\} $.

If $ S^* $ is recursively enumerable, let $ Q $ be a polynomial enumerating $ S^* $. That is, $ z \in S^* $ if and only if $ Q(z, X_{i_2}, \ldots, X_{i_n}) $ has a root.

We can now apply the classic diagonal argument. Let $ e^* = \gamma(Q) $. The embarrassing question to ask is "In which of the sets $ S $ or $ S^* $ is $ e^* $?" By the definition of $ Q $ we have
\[
e^* \in S^* \quad \text{iff} \quad Q(e^*, X_{i_2}, \ldots, X_{i_n}) \text{ has a root}.
\]
But then $ e^* = \gamma(Q) \in S $ by definition, which is a contradiction. $\blacksquare$

Definition: A subgroup $H$ of a finitely generated group $G$ is benign (resp. homologically benign) if the HNN-extension
\[G_H = 〈G, t : t^{-1}ht = h \quad h \in H〉\]
can be embedded in a finitely presented (resp. $\mathrm{FP}_2$) group.

Since any recursively presented group has the form $F/R$ where $F$ is a finitely generated free group and $R$ is a recursively enumerable normal subgroup of $F$, the lemma shows that in order to prove the Higman embedding theorem, it suffices to show that recursively enumerable subgroups of finitely generated free groups are benign. This is the overall strategy of the proof.

Lemma 3 (The Higman Rope Trick): If $ R $ is a benign (resp. homologically benign) normal subgroup of the finitely generated group $ F $, then $ F/R $ is embeddable in a finitely presented (resp. $\mathrm{FP}_2$) group.

Fix $ R $ as in the statement, and let $ H $ be an $ FP_2 $ group containing the group
$ F_R = \langle F, t : t^{-1}rt = r, \, r \in R \rangle $. Let $ L $ be the subgroup of $ F_R \leq H $ generated by $ F $ and
$ t^{-1}Ft $, so that $ L \cong F *_R F $. There is a homomorphism $ \phi : L \to F/R $
whose restriction to $ F $ is equal to the quotient map $ F \to F/R $ and whose restriction to
$ t^{-1}Ft $ is the trivial homomorphism. Viewing $ L $ as a subgroup of $ H $, the map $ l \mapsto (l, \phi(l)) $
defines a second copy of $ L $ inside $ H \times F/R $. Let $ K $ be the HNN-extension in which the
stable letter conjugates these two copies:

\[
K = \langle H \times F/R, s : s^{-1}(l, 1)s = (l, \phi(l)), \, l \in L \rangle.
\]
One then shows enough of the relations are redundant, or more fancifully makes the relations 'disappear'. According to MO, the name is a reference to the Indian Rope Trick, which is a famous magic trick in which a boy climbs up a rope and disappears, just like the relations 'disappear'.
Some general machinery also yields the following useful fact:

Lemma 4: Let $ G $ be a finitely generated group which is embeddable in a finitely presented (resp. $\mathrm{FP}_2$) group.

Every finitely generated subgroup of $ G $ is benign (resp. homologically benign) in $ G $.
If $ H $ and $ K $ are benign subgroups of $ G $, then $ H \cap K $ and $\langle H, K\rangle $ are benign (resp. homologically benign) in $ G $.

At this point the proofs require slightly different lemmata owing to the different nature of the desired final result. For the Higman embedding theorem Valiev proves:

Lemma 5: Let $ S $ be a recursively enumerable set of integers. Then the subgroup
\[
\langle \{a_0^z b_0 c_0^z; z \in S\rangle
\] is a benign subgroup of the free group $\langle a_0, b_0, c_0 \rangle$.

This heavily relies on the interpretation of recursiveness in terms of Diophantineness and involves some tricky manipulations of both group theoretic and model theoretic formulae.

Leary proves a result which is similar in spirit:

Lemma 6: Fix $ l \geq 4 $, and for any integer $ s $ define $ v_s := c_0^s c_1^s \cdots c_l^s de^s $, an element of the free group $ H = \langle c_0, \ldots, c_l, d, e \rangle $ of rank $ l + 3 $. For any $ S \subseteq \mathbb{Z} $ with $ 0 \in S $, the subgroup
\[
V_S := \langle v_s : s \in S \rangle \leq \langle c_0, \ldots, c_l, d, e \rangle
\]
is homologically benign and is freely generated by the given elements.

Unlike Valiev's proof, the proof of this requires nothing about Diophantine equations. Instead, the encoding of an arbitrary subset $S$ of $\mathbb N$ in groups of type $\mathrm{FP}_2$ is replaced by the groups $G_L(S)$, which we discussed in a previous post.

From this point we will follow Leary and comment on the similarities with the Higman embedding theorem.
Let $ L $ be the free group $ L = \langle a, b \rangle $, and let $ F $ be the free group of rank $ l + 6 $ with $ F = \langle a, b, c_0, \dots, c_l, d, e, h \rangle $. Define a Gödel numbering $ \gamma $ of all words on the alphabet $ \{a, b, a^{-1}, b^{-1}\} $ by the formula

\[
\gamma(\emptyset) = 0, \quad \gamma(a) = 1, \quad \gamma(b) = 2, \quad \gamma(a^{-1}) = 3, \quad \gamma(b^{-1}) = 4,
\]

and extending to longer words by concatenation, viewing a concatenation of digits as a number. Thus $ \gamma $ is a bijection between the words and the subset of $ \mathbb{N} $ consisting of zero and all integers whose decimal digits lie in the set $ \{1, 2, 3, 4\} $.

To any word $ w $ on $ \{a, b, a^{-1}, b^{-1}\} $, associate a codeword $ g_w \in L $ defined by

\[
g_w := whc_0^{\gamma(w)}c_1^{\gamma(w)} \cdots c_l^{\gamma(w)}de^{\gamma(w)}.
\]

The subgroup $ G $ of $ F $ generated by all the elements $ g_w $ is freely generated by them.

Lemma 7: The subgroup $ G $ is benign in $ F $.

Analogously to Valiev's proof, Leary constructs a group $ F^* $ defined as the fundamental group of a graph of groups with one vertex group $ F $, and four edges corresponding to stable letters $ u_\lambda $ for $ \lambda \in \{a, b, a^{-1}, b^{-1}\} $, each of which defines an ascending HNN-extension of $ F $ with relations

\[
u_\lambda^{-1}au_\lambda = a, \quad u_\lambda^{-1}bu_\lambda = b, \quad u_\lambda^{-1}c_i u_\lambda = c_0^{\gamma(\lambda)}c_1^{\gamma(\lambda)} \cdots c_{i-1}^{\gamma(\lambda)}c_i^{\gamma(\lambda)} \cdots c_0^{-\gamma(\lambda)},
\]

\[
u_\lambda^{-1}du_\lambda = c_0^{\gamma(\lambda)}c_1^{\gamma(\lambda)} \cdots c_l^{\gamma(\lambda)}de^{\gamma(\lambda)}, \quad u_\lambda^{-1}eu_\lambda = e^{10}, \quad u_\lambda^{-1}hu_\lambda = \lambda h.
\]

In $ F^* $, we have that for any word $ w = \lambda_1 \cdots \lambda_n $,

\[
u_{\lambda_1}^{-1} \cdots u_{\lambda_n}^{-1} g_w u_{\lambda_n} \cdots u_{\lambda_1} = u_{\lambda_1}^{-1} \cdots u_{\lambda_n}^{-1} h d u_{\lambda_n} \cdots u_{\lambda_1} = g_w,
\]

and if $ w = u\lambda $ then $ u_{\lambda}g_w u_{\lambda}^{-1} = g_u $.

He then shows that in $ F^* $,

\[
G = F \cap \langle g_0, u_a, u_b, u_{a^{-1}}, u_{b^{-1}} \rangle.
\]
and uses this to conclude that $ G $ is benign in $ F^* $.

Corollary 8: Every subgroup of the free group $ L = \langle a, b \rangle $ is homologically benign.

Proof: Let $ N $ be a subgroup of $ L $, and define a subset $ S = S(N) \subseteq \mathbb{N} $ as the set of Gödel codes for words $ w $ on $ \{a, b, a^{-1}, b^{-1}\} $ that are equal (as elements of $ L $) to an element of $ N $:

\[
S = \{\gamma(w) : w \in N\}.
\]

Now let $ Y_S $ be the free product $ \langle a, b, h \rangle * V_S \leq F $, where $ V_S $ is as defined in the statement of Lemma 5. By that lemma, $ V_S $ is homologically benign, and hence $ Y_S $ is homologically benign in $ F $. Since $ Y_S $ is freely generated by $ \{a, b, h, v_s : s \in S\} $, it is easy to see that $ G \cap Y_S $ is freely generated by $ \{g_w : w \in N\} $. (Recall that $ v_s = c_0^s c_1^s \cdots c_l^s de^s $.) Hence $ G \cap Y_S $ is homologically benign. The subgroup generated by $ G \cap Y_S $ and the finite set $ \{c_0, \ldots, c_l, d, e, h\} $, which is equal to $ N * \langle c_0, \ldots, c_l, d, e, h \rangle $, is therefore also homologically benign and the intersection of this group with $ L $ is equal to $ N $. $\blacksquare$

We are now ready to complete the proof of Theorem 1. By the Higman--Neumann--Neumann embedding theorem, any countable group can be embedded in a 2-generator group. This 2-generator group is isomorphic to $ L/N $ for some normal subgroup $ N $. By Corollary 8, $ N $ is homologically benign, and so by the Higman rope trick, $ L/N $ can be embedded in an $ FP_2 $ group. The embedding from the Higman--Neumann--Neumann embedding theorem preserves recursiveness, so the same proof shows the Higman embedding theorem modulo the analogous results of Lemma 7 and Corollary 8 in this setting, which are more involved but also use the Godel numbering at key steps.

Other generalisations of the Higman embedding theorem

A corollary of the Higman embedding theorem is that

Theorem 9: There exists a finitely presented group $ H $ with unsolvable word problem.

Proof: Let $ S $ be a recursively enumerable non-recursive set of positive integers. The subgroup
\[
B = \operatorname{Gp}\{a^sbc^z; s \in S\}
\]
is a benign subgroup of the free group $ K = \langle a, b, c \rangle $. Since the subgroup $ \operatorname{Gp}\{a^sbc^z: z \in \mathbb{Z}\} $ is freely generated by the indicated generators, we have
\[
z \in S \quad \text{iff} \quad a^sbc^z \in B.
\]

Since $ B $ is benign, there is an embedding $ \phi $ of the group $ K_B = \langle K, t; t^{-1}Bt = B \rangle $ into a finitely presented group $ H $. Because $ K_B $ is an HNN extension, we have, for every element $ y $ of $ K $,
\[
y \in B \quad \text{iff} \quad t^{-1}yt = y.
\]

Thus
\[
z \in S \quad \text{iff} \quad \phi(a^sbc^z) = \phi(t^{-1}a^sbc^zt).
\]

Hence, a solution of the word problem for $ H $ would allow one to decide membership in $ S $. Since $ S $ is not recursive, $ H $ must have unsolvable word problem. $\blacksquare$

This dashed hopes for general algorithms for all finitely presented groups and initiated the field of decision problems in group theory. Since the Higman embedding theorem is such a fundamental result, there have been many important generalisations of it. We have already mentioned one in a previous post, due to Sapir, where one can add the word aspherical to hypothesis and conclusion. We list 3 others with only passing comments, since the proofs are extremely long, intricate, and technical:

Wagner: Given a finitely generated recursively presented group $R$, there exists a quasi-isometric malnormal embedding of $R$ into a finitely presented group $H$ such that the image of the embedding enjoys the Congruence Extension Property. A subgroup $ H $ is CEP-embedded in the group $ G $ if every normal subgroup of $ H $ is the intersection of $ H $ with some normal subgroup of $ G $. Moreover, the group $H$ can be constructed to have decidable word problem if and only if the word problem of $R$ is decidable.
Birget--Olshanskii--Rips--Sapir proved that the word problem of a finitely generated group is decidable in nondeterministic polynomial time if and only if this group can be embedded into a finitely presented group with a polynomial isoperimetric function. An isoperimetric function is a non-decreasing function $f: \mathbb N \to \mathbb{N}$ which measures the smallest number of two-cells in a van Kampen diagram over a presentation with boundary cycle at most a given length.

It is here and in an earlier companion paper that the notion of $S$-machines is introduced (Sapir's asphericity result also relies on this notion). An $ S $-machine is a kind of non-deterministic one-tape multi-head machine with ``very short memory''. Namely, the machine only ``sees'' what is written on a tape if two heads are sufficiently close to each other. A crucial component of the first paper is a very involved proof that an $ S $-machine is polynomially equivalent to an ordinary Turing machine. This fact is used to conclude that, given a Turing machine $ M $ with time-function $ T(n) $, one can construct an $ S $-machine $ S(M) $ with time function $ T(n)^3 $ accepting almost the same language as $ M $.

In the earlier companion paper, Birget--Rips--Sapir also prove that the Dehn function of a finitely presented group is equivalent to the time function of a two-tape Turing machine. The language accepted by this machine is exactly the set of words equal to 1 in the group. As a corollary of this and another result they conclude that for every language $ L $ over a finite alphabet there exists a finitely presented group $ G $ such that the non-deterministic time complexity of the word problem in $ G $ is polynomially equivalent to the nondeterministic time complexity of $ L $.
To solve the question of whether there exist non-amenable finitely presented groups with no free subgroups, Ol'shanskii--Sapir adapt and modify Higman's theory in the case of free Burnside groups to suit their purposes and use Higman-like embeddings to construct a finitely presented non-amenable group that does not contain a copy of $F_2$ (the HNN extensions lead to the appearance of free subgroups).
Their main result states that, for every sufficiently large odd $ n $, there exists a finitely presented group $ \tilde{B} $ with the following properties: (i) $ \tilde{B} $ is an ascending HNN extension of a finitely generated infinite group of exponent $ n $, (ii) $ \tilde{B} $ is an extension of a non-locally finite group of exponent $ n $ by an infinite cyclic group, (iii) $ \tilde{B} $ contains the free Burnside group $ B = B(2, n) $, (iv) $ \tilde{B} $ is non-amenable.
The main idea is to embed the free Burnside group $ B = B(m, n) $ of rank $ m \geq 2 $ and sufficiently large odd exponent $ n $ into a finitely presented group $ H $, and then construct a generalized HNN extension $ \tilde{B} = \langle H, t \mid tHt^{-1} = B' \rangle $ where $ B' $ is a subgroup of $ B $ generated by some long words satisfying certain very strong small cancellation conditions. The construction of this embedding again uses the notion of $S$-machines, viewed as inverse semigroups (pseudo-groups) of partial transformations of sets of words. Any such $ \tilde{B} $ is torsion-by-cyclic, satisfies the law $[x, y]^n = 1$, and does not contain copies of $ F_2 $.The main theorem is deduced from the following two difficult theorems of independent interest.

Theorem 10: For every sufficiently large odd exponent $ n $ and every $ s $, there exists a finitely presented group $ H $ containing $ B(s, n) $ such that (i) $ H^n \cap B(s, n) = 1 $, so $ B(s, n) $ canonically embeds in $ H/H^n $ and (ii) this embedding is CEP-embedding (here $ H^n $ denotes the subgroup of $ H $ generated by all $ n $-th powers in $ H $).

Theorem 11: For any sufficiently large odd exponent $ n $, the countably generated free Burnside group $ B(\infty, n) $ is CEP-embedded in some finitely generated free Burnside group.

One can use the latter theorem to recover the result of Obraztsov that every countable group of sufficiently large odd exponent $ n $ can be embedded into a finitely generated group of exponent $ n $

Search This Blog

On the shoulders of giants