Word problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same…
≈ 15 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element of G . The word problems for certain groups provide well-known examples of undecidable problems. If A is a finite set of generators for G , then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G . If B is another finite generating set for G , then the word problem over the generating set B is equivalent to the word problem over the generating set A . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G . The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G , whether the words represent the same element of G . Some authors require the class K to be definable by a recursively enumerable set of presentations.
For a simple example, consider the group given by the presentation \langle a \, | \, a^3 = e \rangle . Writing A for the inverse of a , we have possible strings combining any number of the symbols a and A . Whenever we see aaa , or aA or Aa we may strike these out.
We should also remember to strike out AAA ; this says that since the cube of a is the identity element of G , so is the cube of the inverse of a . Under these conditions the word problem becomes easy. First reduce strings to the empty string, a , aa , A or AA .
Then note that we may also multiply by aaa , so we can convert A to aa and convert AA to a . The result is that the word problem, here for the cyclic group of order three, is solvable. This is not, however, the typical case. For the example, we have a canonical form available that reduces any string to one of length at most three, by decreasing the length monotonically.
In general, it is not true that one can get a canonical form for the elements, by stepwise cancellation. One may have to use relations to expand a string many-fold, in order eventually to find a cancellation that brings the length right down. The upshot is, in the worst case, that the relation between strings that says they are equal in G is an Undecidable problem.
Examples
The following groups have a solvable word problem: Automatic groups, including: Finite groups Negatively curved (aka. hyperbolic) groups Euclidean groups Coxeter groups Braid groups Geometrically finite groups Finitely generated free groups Finitely generated free abelian groups Polycyclic groups Finitely generated recursively absolutely presented groups, including: Finitely presented simple groups. Finitely presented residually finite groups One-relator groups, including: Fundamental groups of closed orientable two-dimensional manifolds.
Combable groups Autostackable groups Examples with unsolvable word problems are also known: Given a recursively enumerable set A of positive integers that has insoluble membership problem, \langle a, b, c, d \, | \, a^n b a^n = c^n d c^n : n \in A \rangle is a finitely generated group with a recursively enumerable presentation whose word problem is insoluble Every finitely generated group with a recursively enumerable presentation and insoluble word problem is a subgroup of a finitely presented group with insoluble word problem The number of relators in a finitely presented group with insoluble word problem may be as low as 14 or even 12. An explicit example of a reasonable short presentation with insoluble word problem is given in Collins 1986: \begin{array}{lllll}\langle & a,b,c,d,e,p,q,r,t,k & | & &\\ &p^{10}a = ap, &pacqr = rpcaq, &ra=ar, &\\ &p^{10}b = bp, &p^2adq^2r = rp^2daq^2, &rb=br, &\\ &p^{10}c = cp, &p^3bcq^3r = rp^3cbq^3, &rc=cr, &\\ &p^{10}d = dp, &p^4bdq^4r = rp^4dbq^4, &rd=dr, &\\ &p^{10}e = ep, &p^5ceq^5r = rp^5ecaq^5, &re=er, &\\ &aq^{10} = qa, &p^6deq^6r = rp^6edbq^6, &pt=tp, &\\ &bq^{10} = qb, &p^7cdcq^7r = rp^7cdceq^7, &qt=tq, &\\ &cq^{10} = qc, &p^8ca^3q^8r = rp^8a^3q^8, &&\\ &dq^{10} = qd, &p^9da^3q^9r = rp^9a^3q^9, &&\\ &eq^{10} = qe, &a^{-3}ta^3k = ka^{-3}ta^3 &&\rangle \end{array}
Partial solution of the word problem
The word problem for a recursively presented group can be partially solved in the following sense: Given a recursive presentation P = \langle X \, | \, R \rangle for a group G , define: S=\{\langle u,v \rangle : u \text{ and } v \text{ are words in } X \text{ and } u=v \text{ in } G\ \} then there is a partial recursive function f_P such that: f_P(\langle u,v \rangle) = \begin{cases} 0 &\text{if}\ \langle u,v \rangle \in S \\ \text{undefined/does not halt}\ &\text{if}\ \langle u,v \rangle \notin S \end{cases} More informally, there exists an algorithm that halts if u = v , but does not do so otherwise. It follows that to solve the word problem for P it is sufficient to construct a recursive function g such that: g(\langle u,v \rangle) = \begin{cases} 0 &\text{if}\ \langle u,v \rangle \notin S \\ \text{undefined/does not halt}\ &\text{if}\ \langle u,v \rangle \in S \end{cases} However u = v in G if and only if u v^{-1} = 1 in G . It follows that to solve the word problem for P it is sufficient to construct a recursive function h such that: h(x) = \begin{cases} 0 &\text{if}\ x\neq1\ \text{in}\ G \\ \text{undefined/does not halt}\ &\text{if}\ x=1\ \text{in}\ G \end{cases}
Example
The following will be proved as an example of the use of this technique: Theorem: A finitely presented residually finite group has solvable word problem. Proof: Suppose G = \langle X \, | \, R \rangle is a finitely presented, residually finite group. Let S be the group of all permutations of the natural numbers \mathbb{N} that fixes all but finitely many numbers.
Then: S is locally finite and contains a copy of every finite group. The word problem in S is solvable by calculating products of permutations.
There is a recursive enumeration of all mappings of the finite set X into S . Since G is residually finite, if w is a word in the generators X of G then w \neq 1 in G if and only if some mapping of X into S induces a homomorphism such that w \neq 1 in S . Given these facts, the algorithm defined by the following pseudocode: For every mapping of X into S If every relator in R is satisfied in S If w ≠ 1 in S return 0 End if End if End for defines a recursive function h such that: h(x) = \begin{cases} 0 &\text{if}\ x\neq 1\ \text{in}\ G \\ \text{undefined/does not halt}\ &\text{if}\ x=1\ \text{in}\ G \end{cases} This shows that G has solvable word problem.
Unsolvability of the uniform word problem
The criterion given above, for the solvability of the word problem in a single group, can be extended by a straightforward argument. This gives the following criterion for the uniform solvability of the word problem for a class of finitely presented groups: To solve the uniform word problem for a class K of groups, it is sufficient to find a recursive function that takes a finite presentation P for a group G and a word in the generators of G , such that whenever G \in K : f(P,w) = \begin{cases} 0 &\text{if}\ w\neq1\ \text{in}\ G \\ \text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ G \end{cases} Boone–Rogers Theorem: There is no uniform partial algorithm that solves the word problem in all finitely presented groups with solvable word problem.
In other words, the uniform word problem for the class of all finitely presented groups with solvable word problem is unsolvable. This has some interesting consequences. For instance, the Higman embedding theorem can be used to construct a group containing an isomorphic copy of every finitely presented group with solvable word problem.
It seems natural to ask whether this group can have solvable word problem. But it is a consequence of the Boone–Rogers result that: Corollary: There is no universal solvable word problem group. That is, if G is a finitely presented group that contains an isomorphic copy of every finitely presented group with solvable word problem, then G itself must have unsolvable word problem.
Remark: Suppose G = \langle X \, | \, R \rangle is a finitely presented group with solvable word problem and H is a finite subset of G . Let H^* = \langle H \rangle , be the group generated by H . Then the word problem in H^* is solvable: given two words h, k in the generators H of H^* , write them as words in X and compare them using the solution to the word problem in G . It is easy to think that this demonstrates a uniform solution of the word problem for the class K (say) of finitely generated groups that can be embedded in G . If this were the case, the non-existence of a universal solvable word problem group would follow easily from Boone–Rogers. However, the solution just exhibited for the word problem for groups in K is not uniform.
To see this, consider a group J = \langle Y \, | \, T \rangle \in K ; in order to use the above argument to solve the word problem in J , it is first necessary to exhibit a mapping e : Y \to G that extends to an embedding e^* : J \to G . If there were a recursive function that mapped (finitely generated) presentations of groups in K to embeddings into G , then a uniform solution of the word problem in K could indeed be constructed. But there is no reason, in general, to suppose that such a recursive function exists.
However, it turns out that, using a more sophisticated argument, the word problem in J can be solved without using an embedding e : J \to G . Instead an enumeration of homomorphisms is used, and since such an enumeration can be constructed uniformly, it results in a uniform solution to the word problem in K .
Proof that there is no universal solvable word problem group
Suppose G were a universal solvable word problem group. Given a finite presentation P = \langle X \, | \, R \rangle of a group H , one can recursively enumerate all homomorphisms h : H \to G by first enumerating all mappings h^\dagger : X \to G . Not all of these mappings extend to homomorphisms, but, since h^\dagger(R) is finite, it is possible to distinguish between homomorphisms and non-homomorphisms, by using the solution to the word problem in G . "Weeding out" non-homomorphisms gives the required recursive enumeration: h_1, h_2, \ldots, h_n, \ldots .
If H has solvable word problem, then at least one of these homomorphisms must be an embedding. So given a word w in the generators of H : \text{If}\ w\ne 1\ \text{in}\ H,\ h_n(w)\ne 1\ \text{in}\ G\ \text{for some}\ h_n \text{If}\ w= 1\ \text{in}\ H,\ h_n(w)= 1\ \text{in}\ G\ \text{for all}\ h_n Consider the algorithm described by the pseudocode: Let n = 0 Let repeatable = TRUE while (repeatable) increase n by 1 if (solution to word problem in G reveals h n (w) ≠ 1 in G) Let repeatable = FALSE output 0.
This describes a recursive function: f(w) = \begin{cases} 0 &\text{if}\ w\neq1\ \text{in}\ H \\ \text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ H. \end{cases} The function f clearly depends on the presentation P . Considering it to be a function of the two variables, a recursive function has been constructed that takes a finite presentation P for a group H and a word w in the generators of a group G , such that whenever G has soluble word problem: f(P,w) = \begin{cases} 0 &\text{if}\ w\neq1\ \text{in}\ H \\ \text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ H. \end{cases} But this uniformly solves the word problem for the class of all finitely presented groups with solvable word problem, contradicting Boone–Rogers. This contradiction proves G cannot exist.
Algebraic structure and the word problem
There are a number of results that relate solvability of the word problem and algebraic structure. The most significant of these is the Boone–Higman theorem: A finitely presented group has solvable word problem if and only if it can be embedded in a simple group that can be embedded in a finitely presented group.
It is widely believed that it should be possible to do the construction so that the simple group itself is finitely presented. If so one would expect it to be difficult to prove as the mapping from presentations to simple groups would have to be non-recursive.
The following has been proved by Bernhard Neumann and Angus Macintyre: A finitely presented group has solvable word problem if and only if it can be embedded in every algebraically closed group. What is remarkable about this is that the algebraically closed groups are so wild that none of them has a recursive presentation.
The oldest result relating algebraic structure to solvability of the word problem is Kuznetsov's theorem: A recursively presented simple group S has solvable word problem. To prove this let \langle X | R \rangle be a recursive presentation for S . Choose a nonidentity element a \in S , that is, a \neq 1 in S . If w is a word on the generators X of S , then let: S_w = \langle X | R\cup \{w\} \rangle.
There is a recursive function f_{\langle X | R\cup \{w\} \rangle} such that: f_{\langle X | R\cup \{w\} \rangle}(x) = \begin{cases} 0 &\text{if}\ x=1\ \text{in}\ S_w\\ \text{undefined/does not halt}\ &\text{if}\ x\neq 1\ \text{in}\ S_w. \end{cases} Write: g(w, x) = f_{\langle X | R\cup \{w\} \rangle}(x). Then because the construction of f was uniform, this is a recursive function of two variables. It follows that: is recursive.
By construction: h(w) = \begin{cases} 0 &\text{if}\ a=1\ \text{in}\ S_w\\ \text{undefined/does not halt}\ &\text{if}\ a\neq 1\ \text{in}\ S_w. \end{cases} Since S is a simple group, its only quotient groups are itself and the trivial group. Since a \neq 1 in S , we see a = 1 in S_w if and only if S_w is trivial if and only if w \neq 1 in S . Therefore: h(w) = \begin{cases} 0 &\text{if}\ w\ne 1\ \text{in}\ S\\ \text{undefined/does not halt}\ &\text{if}\ w=1\ \text{in}\ S. \end{cases} The existence of such a function is sufficient to prove the word problem is solvable for S . This proof does not prove the existence of a uniform algorithm for solving the word problem for this class of groups.
The non-uniformity resides in choosing a non-trivial element of the simple group. There is no reason to suppose that there is a recursive function that maps a presentation of a simple groups to a non-trivial element of the group. However, in the case of a finitely presented group we know that not all the generators can be trivial (Any individual generator could be, of course).
Using this fact it is possible to modify the proof to show: The word problem is uniformly solvable for the class of finitely presented simple groups.
See also
Combinatorics on words SQ-universal group Word problem (mathematics) Reachability problem Nested stack automata (have been used to solve the word problem for groups)
Text derived from https://en.wikipedia.org/w/index.php?oldid=1361010510 under CC BY-SA 4.0; modifications have been made.