Word problem for groups

For a fixed finitely generated group with specified generators, its word problem asks for an algorithm deciding whether an input word represents the identity. For a finitely presented group, positive answers can be enumerated from the relators, but there need not be an algorithm deciding both positive and negative answers. An effective reduction from a nonrecursive halting set proves unsolvability.

An amalgamated free product of finite cyclic groups has an effective normal form theorem for an amalgamated free product: multiplication, subgroup membership and subgroup identifications are finite table operations. Replacing an amalgamated syllable by its image in the neighbouring factor and combining adjacent syllables from one factor strictly decreases syllable count. A remaining alternating product outside the amalgamated subgroup is nonidentity. This supplies a terminating word problem for a group algorithm.

For $S\subseteq {\mathbb{N}}_{>0}$, form the Right-angled Artin group on generators $b_i$ indexed by $i\in \mathbb{Z}$, imposing $[b_i,b_j]=1$ precisely when $|i-j|\in S$. Translation $b_i\mapsto b_{i+1}$ is an automorphism. Its semidirect product with an infinite cyclic group generated by $t$ is countable and generated by $b_0,t$. If $n\notin S$, killing all $b_i$ except $b_0,b_n$ retracts the graph group onto the rank-two free group, so their commutator is nonidentity. This proves the displayed equivalence. For non-recursively-enumerable $S$, enumerable identities of finitely generated subgroups rules out an embedding of this two-generated group in any finitely presented group.

If a finitely generated group embeds in a finitely presented group, its null words in any fixed finite generating set form a recursively enumerable set. Choose words for the generator images in the larger group. Enumerate finite products of conjugates of its defining relators and their inverses, freely reduce, and compare with substituted words. Dovetailing over input words enumerates exactly the subgroup's identities. Choosing the finite image words is nonuniform, but their existence suffices for existence of an enumeration algorithm.

A finitely generated group $G$ has a soluble word problem for a group if and only if there are a simple group $S$ and a finitely presented group $P$ with embeddings $G\hookrightarrow S\hookrightarrow P$. The theorem does not require $S$ itself to be finitely presented. In particular, a finitely generated subgroup of a finitely presented simple group has soluble word problem. The primary statement is Theorem I of An algebraic characterization of groups with soluble word problem.

Let $S$ be a nontrivial simple group inside a finitely presented group $P$, and fix $a\ne 1$ in $S$. For an input word $w$ in $S$, enumerate products of conjugates in $P$ of $w^{\pm 1}$ and proofs in $P$ that such a product equals $a$. This search terminates exactly when $w\ne 1$: the normal closure of a nontrivial element of $S$ is all of $S$, and its conjugators are also elements of $P$, while a null word has only trivial conjugates. Run this search alongside the enumerable proofs that $w=1$. Exactly one search terminates, solving the word problem for a group on any specified finitely generated subgroup of $S$. No effective generating set for the possibly infinitely generated $S$ is needed.

A finitely generated group with soluble word problem for a group embeds in a countably generated simple group with a recursive presentation of a group. Start with $P_0=G\ast ⟨a⟩$, retaining decidable membership in $⟨a⟩$. At stage $n$, add a free infinite cyclic generator $z_n$. For every nonidentity base element $g$, conjugate $[g,z_n]$ to $a$ and conjugate $g{z}_n$ to $a$; also conjugate $z_n$ to $a$, using distinct stable letters. All associated subgroups are infinite cyclic, with decidable membership by effective cyclic membership in a free product. Britton's lemma preserves embeddings, decidable word problem and decidable membership in the inherited $⟨a⟩$.

In the union, any nontrivial normal subgroup contains some nonidentity $g$ and hence $a$, by the commutator-conjugation relation. The other relations force $z_n$ and then every old $g$ into the normal closure of $a$. Every stable letter becomes an old element at a later stage, so the normal closure of $a$ is the whole union. The union is nontrivial and simple. Effective word enumeration at each stage makes all relators recursively enumerable. A two-generator HNN embedding followed by the Higman embedding theorem embeds this simple envelope in a finitely presented group.