Word problem for groups

From Free net encyclopedia

In abstract algebra, the word problem for a finitely generated group G is the algorithmic problem of deciding, given as input two words in the generators for G, whether they represent the same element of G.

The related but different uniform word problem for finitely presented groups is the algorithmic problem of deciding, given as input a presentation for a group and two words in the generators, whether the words represent the same element in the group defined by the presentation.

History

The study of the word problem was first proposed by Max Dehn in 1911.

It was shown by Pyotr Sergeyevich Novikov in 1955 that there exists a finitely generated (in fact, a finitely presented) group G such that the word problem is for G is undecidable. It follows immediately that the uniform word problem is also undecidable. A much simpler proof was obtained by Boone in 1959.

The word problem was one of the first examples of an unsolvable problem to be found not in mathematical logic or the theory of algorithms, but in one of the central branches of classical mathematics, algebra. As a result of its unsolvability, several other problems in combinatorial group theory have been shown to be unsolvable as well.

It is important to realize that the word problem is in fact solvable for many groups G. For example, see Todd-Coxeter algorithm and Knuth-Bendix completion algorithm.

A More Concrete Description

In more concrete terms, the uniform word problem can be expressed as a rewriting question, for literal strings. For a presentation P of a group G, P will specify a certain number of generators

x, y, z, ...

for G. We need to introduce one letter for x and another (for convenience) for the group element represented by x⁻¹. Call these letters (twice as many as the generators) the alphabet A for our problem. Then each element in G is represented in some way by a product

abc ... pqr

of symbols from A, of some length, multiplied in G. The effect of the relations in G is to make various such strings represent the same element of G. In fact the relations provide a list of strings that can be either introduced where we want, or cancelled out whenever we see them, without changing the 'value', i.e. the group element that is the result of the multiplication.

For a simple example, take the presentation <x|x³>. Writing y for the inverse of x, we have possible strings of x′s and y′s. Whenever we see xxx, or xy or yx we may strike these out. We should also remember to strike out yyy; this says that since the cube of x is the identity element of G, so is the cube of the inverse of x. Under these conditions the word problem becomes easy. First reduce strings to e, x, xx, y or yy. Then note that we may also multiply by xxx, so we can convert yy to x. The result is that we can prove that the word problem here, for what is the cyclic group of order three, is soluble.

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 not decidable.

References

• Boone, Cannonito, Lyndon. Word Problems: Decision Problem in Group Theory. Netherlands: North-Holland. 1973.
• P. S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov 44 (1955), pp 1-143. (in Russian)
• W. W. Boone. The word problem. Annals of Mathematics, 70(2) (1959), pp 207-265
• J.J. Rotman. The Theory of Groups: An Introduction. Boston: Allyn and Bacon. 1965.
• J. Stillwell. The word problem and the isomorphism problem for groups. Bulletin AMS 6 (1982), pp 33-56