The word problem

1. What is the word problem?

   Given a group G with a presentation <S|R>. The word problem asks us to decide whether two words in F(S), the free group generated by S, represent the same element of G. We are only allowed to use the information from S and R. A "theorem" about the "simplified" structure of G = <S|R> can't be used. Therefore, while the word problem seems to be a "trivial" problem, it might be hard, or even impossible, to design an algorithm that solves this problem. Here, an algorithm is a sequence of rules/moves that take two words as the input and return (after finitely many moves) whether these two words represent the same element of G or not. 

   It suffices to consider a special case of the word problem: determine whether a word represents the identity element, as deciding whether w_1, w_2 are the same corresponds to deciding whether w_1w_2^{-1} is the identity element. 

2. Some examples of "easy" cases

   The word problem might be "easy" in certain cases. For example, given a finite group G, if we choose S to be the set of all elements of G and write down all the results of the binary operation on G to form the set of relators R, then the information from R is already so clear that we can in turn calculate w_1w_2, (w_1w_2)w_3, (w_1w_2w_3)w_4, ... for any given word w = w_1w_2...w_n. It might be hard to write down this algorithm/program on a computer as there are too many cases to consider, but at least we have a solution. 

   Another example is finitely generated abelian group. By the classification of finitely generated abelian group, such a group must be of the form Z^r x Z/n_1 x Z/n_2 x ... x Z/n_k. One possible presentation is given by writing down the standard generating sets g_1, g_2, ..., g_r, s_1, s_2, ..., s_k consisting of r + k elements, the \binom{r + k}{2} commutativity relations and the fact that the order of s_1, s_2, ..., s_k must be n_1, n_2, ..., n_k respectively. To check whether a word represents the identity or not, we just need to check whether the number of appearances of g_i equals the number of appearances of g_i's inverse for each i = 1, 2, ..., r and whether the number of appearances of s_j is congruent to the number of appearances of s_j's inverse modulo n_j for each j = 1, 2, ..., k. 

3. A result of Heinrich Tietze: solvability of the word problem depends only on the group structure

   In the 1900s, the Austrian - German mathematician Heinrich Tietze (1880 - 1964) introduced four types of operations on presentations: removing a relator if it can be deduced from the other relators, adding a relator if it can be deduced from the available relators, adding one element to S if it can be represented in terms of the available elements of S, removing one element from S if it can be represented in terms of the other elements of S. It is easy to see that if the presentation P can be obtained from the presentation Q, then the presentation Q can also be obtained from the presentation P, as adding one element is the inverse of removing one element (i.e. applying both in turn does not change the presentation) and adding one relator is the inverse of removing one relator. 

   In 1908, Heinrich Tietze proved that any two presentations of the same group G can be obtained from each other via a sequence of Tietze transformations. Perhaps I would come back to this proof in a later post. As Tietze transformation allows us to "rewrite" certain moves in the algorithm, this result shows that whether the word problem can be solved or not depends only on the group structure, not the presentation. Therefore, solvability of the word problem is a group property. By the examples on section 1, if G is a finite group or a finitely generated abelian groups, then the word problem is solvable.