↑ arvau

Wikipedia / 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. The word problems for certain groups provide well-known examples of undecidable problems.

is a finite set of generators, then the word problem is the membership problem for the formal language and a formal set of inverses that map to the identity under the natural map from the free monoid with involution.

The related but different uniform word problem of recursively presented groups is the algorithmic problem of deciding, given as input a presentation to be definable by a recursively enumerable set of presentations.

History

Throughout the history of the subject, computations in groups have been carried out using various normal forms. These usually implicitly solve the word problem for the groups in question. In 1911 Max Dehn proposed that the word problem was an important area of study in its own right, together with the conjugacy problem and the group isomorphism problem. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2. Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems.

It was shown by Pyotr Novikov is undecidable. It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by William Boone in 1958.

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.

. For example, polycyclic groups have solvable word problems since the normal form of an arbitrary word in a polycyclic presentation is readily computable; other algorithms for groups may, in suitable circumstances, also solve the word problem, see the Todd–Coxeter algorithm and the Knuth–Bendix completion algorithm. On the other hand, the fact that a particular algorithm does not solve the word problem for a particular group does not show that the group has an unsolvable word problem. For instance Dehn's algorithm does not solve the word problem for the fundamental group of the torus. However this group is the direct product of two infinite cyclic groups and so has a solvable word problem.

A more concrete description

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

is represented in some way by a product

. The string of length 0 (null string) stands for the identity element. The crux of the whole problem is to be able to recognise all can be represented, given some relations.

The effect of the relations. 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.

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

is an Undecidable problem.

Examples

The following groups have a solvable word problem:

Automatic groups, including:

Finitely generated recursively absolutely presented groupss, including:

One-relator groups, including:

  • Fundamental groups of closed orientable two-dimensional manifolds.

  • Combable groups

  • Autostackable groups

Examples with unsolvable word problems are also known:

  • 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:

Partial solution of the word problem

The word problem for a recursively presented group can be partially solved in the following sense:

  1. , define:

  2. such that:

, but does not do so otherwise.

such that:

if and only if such that:

Example

The following will be proved as an example of the use of this technique:

  1. Theorem: A finitely presented residually finite group has solvable word problem.

Proof: is a finitely presented, residually finite group.

be the group of all permutations of the natural numbers that fixes all but finitely many numbers. Then:

  1. is locally finite and contains a copy of every finite group.

  2. is solvable by calculating products of permutations.

  3. .

  4. .

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

such that:

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:

  1. of groups, it is sufficient to find a recursive function and a word :

    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:

  1. Corollary: itself must have unsolvable word problem.

Remark: can be solved without. Instead an enumeration of homomorphisms.

Proof that there is no universal solvable word problem group

.

:

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 hn(w) ≠ 1 in G)
        Let repeatable = FALSE
output 0.

This describes a recursive function:

. Considering it to be a function of the two variables, a recursive function has soluble word problem:

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:

  1. 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:

  1. 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:

  1. has solvable word problem.

.

, then let:

such that:

Write:

was uniform, this is a recursive function of two variables.

It follows that: is recursive. By construction:

is a simple group, its only quotient groups are itself and the trivial group. Therefore:

.

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:

  1. The word problem is uniformly solvable for the class of finitely presented simple groups.

See also

Notes

References