Word problem for groups

Last updated

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group is the algorithmic problem of deciding whether two words in the generators represent the same element of . The word problem is a well-known example of an undecidable problem.

Contents

If is a finite set of generators for , then the word problem is the membership problem for the formal language of all words in and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on to the group . If is another finite generating set for , then the word problem over the generating set is equivalent to the word problem over the generating set . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group .

The related but different uniform word problem for a class of recursively presented groups is the algorithmic problem of deciding, given as input a presentation for a group in the class and two words in the generators of , whether the words represent the same element of . Some authors require the class 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, [1] 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. [2] Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems. [3] [4] [5]

It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group such that the word problem for is undecidable. [6] It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by William Boone in 1958. [7]

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.

The word problem is in fact solvable for many groups . 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 [8] and the Knuth–Bendix completion algorithm. [9] 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. [10] For a presentation of a group , will specify a certain number of generators

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

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

The effect of the relations in is to make various such strings represent the same element of . 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, consider the group given by the presentation . Writing for the inverse of , we have possible strings combining any number of the symbols and . Whenever we see , or or we may strike these out. We should also remember to strike out ; this says that since the cube of is the identity element of , so is the cube of the inverse of . Under these conditions the word problem becomes easy. First reduce strings to the empty string, , , or . Then note that we may also multiply by , so we can convert to and convert to . 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 is an Undecidable problem .

Examples

The following groups have a solvable word problem:

Examples with unsolvable word problems are also known:

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 for a group , define:
then there is a partial recursive function such that:

More informally, there exists an algorithm that halts if , but does not do so otherwise.

It follows that to solve the word problem for it is sufficient to construct a recursive function such that:

However in if and only if in . It follows that to solve the word problem for it is sufficient to construct a recursive function such that:

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 is a finitely presented, residually finite group.

Let 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. The word problem in is solvable by calculating products of permutations.
  3. There is a recursive enumeration of all mappings of the finite set into .
  4. Since is residually finite, if is a word in the generators of then in if and only if some mapping of into induces a homomorphism such that in .

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 ifEnd ifEnd for

defines a recursive function such that:

This shows 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:

To solve the uniform word problem for a class of groups, it is sufficient to find a recursive function that takes a finite presentation for a group and a word in the generators of , such that whenever :
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 is a finitely presented group that contains an isomorphic copy of every finitely presented group with solvable word problem, then itself must have unsolvable word problem.

Remark: Suppose is a finitely presented group with solvable word problem and is a finite subset of . Let , be the group generated by . Then the word problem in is solvable: given two words in the generators of , write them as words in and compare them using the solution to the word problem in . It is easy to think that this demonstrates a uniform solution of the word problem for the class (say) of finitely generated groups that can be embedded in . 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 is not uniform. To see this, consider a group ; in order to use the above argument to solve the word problem in , it is first necessary to exhibit a mapping that extends to an embedding . If there were a recursive function that mapped (finitely generated) presentations of groups in to embeddings into , then a uniform solution of the word problem in 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 can be solved without using an embedding . 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 .

Proof that there is no universal solvable word problem group

Suppose were a universal solvable word problem group. Given a finite presentation of a group , one can recursively enumerate all homomorphisms by first enumerating all mappings . Not all of these mappings extend to homomorphisms, but, since is finite, it is possible to distinguish between homomorphisms and non-homomorphisms, by using the solution to the word problem in . "Weeding out" non-homomorphisms gives the required recursive enumeration: .

If has solvable word problem, then at least one of these homomorphisms must be an embedding. So given a word in the generators of :

Consider the algorithm described by the pseudocode:

Letn = 0 Letrepeatable = TRUE while (repeatable)     increase n by 1     if (solution to word problem in G reveals hn(w) ≠ 1 in G)         Letrepeatable = FALSE output 0.

This describes a recursive function:

The function clearly depends on the presentation . Considering it to be a function of the two variables, a recursive function has been constructed that takes a finite presentation for a group and a word in the generators of a group , such that whenever has soluble word problem:

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 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 has solvable word problem.

To prove this let be a recursive presentation for . Choose a nonidentity element , that is, in .

If is a word on the generators of , then let:

There is a recursive function such that:

Write:

Then because the construction of was uniform, this is a recursive function of two variables.

It follows that: is recursive. By construction:

Since is a simple group, its only quotient groups are itself and the trivial group. Since in , we see in if and only if is trivial if and only if in . Therefore:

The existence of such a function is sufficient to prove the word problem is solvable for .

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

Notes

  1. Dehn 1911.
  2. Dehn 1912.
  3. Greendlinger, Martin (June 1959), "Dehn's algorithm for the word problem", Communications on Pure and Applied Mathematics, 13 (1): 67–83, doi:10.1002/cpa.3160130108.
  4. Lyndon, Roger C. (September 1966), "On Dehn's algorithm", Mathematische Annalen, 166 (3): 208–228, doi:10.1007/BF01361168, hdl: 2027.42/46211 , S2CID   36469569.
  5. Schupp, Paul E. (June 1968), "On Dehn's algorithm and the conjugacy problem", Mathematische Annalen, 178 (2): 119–130, doi:10.1007/BF01350654, S2CID   120429853.
  6. Novikov, P. S. (1955), "On the algorithmic unsolvability of the word problem in group theory", Proceedings of the Steklov Institute of Mathematics (in Russian), 44: 1–143, Zbl   0068.01301
  7. Boone, William W. (1958), "The word problem" (PDF), Proceedings of the National Academy of Sciences, 44 (10): 1061–1065, Bibcode:1958PNAS...44.1061B, doi: 10.1073/pnas.44.10.1061 , PMC   528693 , PMID   16590307, Zbl   0086.24701
  8. Todd, J.; Coxeter, H.S.M. (1936). "A practical method for enumerating cosets of a finite abstract group". Proceedings of the Edinburgh Mathematical Society. 5 (1): 26–34. doi: 10.1017/S0013091500008221 .
  9. Knuth, D.; Bendix, P. (2014) [1970]. "Simple word problems in universal algebras". In Leech, J. (ed.). Computational Problems in Abstract Algebra: Proceedings of a Conference Held at Oxford Under the Auspices of the Science Research Council Atlas Computer Laboratory, 29th August to 2nd September 1967. Springer. pp. 263–297. ISBN   9781483159423.
  10. Rotman 1994.
  11. Simmons, H. (1973). "The word problem for absolute presentations". J. London Math. Soc. s2-6 (2): 275–280. doi:10.1112/jlms/s2-6.2.275.
  12. Lyndon, Roger C.; Schupp, Paul E (2001). Combinatorial Group Theory. Springer. pp. 1–60. ISBN   9783540411581.
  13. Collins & Zieschang 1990, p. 149.
  14. Collins & Zieschang 1993, Cor. 7.2.6.
  15. Collins 1969.
  16. Borisov 1969.
  17. Collins 1972.
  18. Collins 1986.
  19. We use the corrected version from John Pedersen's A Catalogue of Algebraic Systems

Related Research Articles

In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain differential equations. The idea is to write the solution of the differential equation as a sum of certain "basis functions" and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:

The Knuth–Bendix completion algorithm is a semi-decision algorithm for transforming a set of equations into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra.

In mathematics, the Lasker–Noether theorem states that every Noetherian ring is a Lasker ring, which means that every ideal can be decomposed as an intersection, called primary decomposition, of finitely many primary ideals. The theorem was first proven by Emanuel Lasker for the special case of polynomial rings and convergent power series rings, and was proven in its full generality by Emmy Noether.

In the mathematical area of group theory, Artin groups, also known as Artin–Tits groups or generalized braid groups, are a family of infinite discrete groups defined by simple presentations. They are closely related with Coxeter groups. Examples are free groups, free abelian groups, braid groups, and right-angled Artin–Tits groups, among others.

In mathematics, the HNN extension is an important construction of combinatorial group theory.

In cryptography, XTR is an algorithm for public-key encryption. XTR stands for 'ECSTR', which is an abbreviation for Efficient and Compact Subgroup Trace Representation. It is a method to represent elements of a subgroup of a multiplicative group of a finite field. To do so, it uses the trace over to represent elements of a subgroup of .

In computational algebra, the Cantor–Zassenhaus algorithm is a method for factoring polynomials over finite fields.

In mathematics, an absolute presentation is one method of defining a group.

In the mathematical subject of group theory, the rank of a groupG, denoted rank(G), can refer to the smallest cardinality of a generating set for G, that is

In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm. Small cancellation methods are also used for constructing Tarski monsters, and for solutions of Burnside's problem.

In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group in terms of the length of that relation. The growth type of the Dehn function is a quasi-isometry invariant of a finitely presented group. The Dehn function of a finitely presented group is also closely connected with non-deterministic algorithmic complexity of the word problem in groups. In particular, a finitely presented group has solvable word problem if and only if the Dehn function for a finite presentation of this group is recursive. The notion of a Dehn function is motivated by isoperimetric problems in geometry, such as the classic isoperimetric inequality for the Euclidean plane and, more generally, the notion of a filling area function that estimates the area of a minimal surface in a Riemannian manifold in terms of the length of the boundary curve of that surface.

In mathematics, a signalizer functor gives the intersections of a potential subgroup of a finite group with the centralizers of nontrivial elements of an abelian group. The signalizer functor theorem gives conditions under which a signalizer functor comes from a subgroup. The idea is to try to construct a -subgroup of a finite group , which has a good chance of being normal in , by taking as generators certain -subgroups of the centralizers of nonidentity elements in one or several given noncyclic elementary abelian -subgroups of The technique has origins in the Feit–Thompson theorem, and was subsequently developed by many people including Daniel Gorenstein who defined signalizer functors, George Glauberman who proved the Solvable Signalizer Functor Theorem for solvable groups, and Patrick McBride who proved it for all groups. This theorem is needed to prove the so-called "dichotomy" stating that a given nonabelian finite simple group either has local characteristic two, or is of component type. It thus plays a major role in the classification of finite simple groups.

In the mathematical subject of geometric group theory, the Baumslag–Gersten group, also known as the Baumslag group, is a particular one-relator group exhibiting some remarkable properties regarding its finite quotient groups, its Dehn function and the complexity of its word problem.

In mathematics, specifically group theory, a descendant tree is a hierarchical structure that visualizes parent-descendant relations between isomorphism classes of finite groups of prime power order , for a fixed prime number and varying integer exponents . Such groups are briefly called finitep-groups. The vertices of a descendant tree are isomorphism classes of finite p-groups.

Non-commutative cryptography is the area of cryptology where the cryptographic primitives, methods and systems are based on algebraic structures like semigroups, groups and rings which are non-commutative. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use of braid groups to develop cryptographic protocols. Later several other non-commutative structures like Thompson groups, polycyclic groups, Grigorchuk groups, and matrix groups have been identified as potential candidates for cryptographic applications. In contrast to non-commutative cryptography, the currently widely used public-key cryptosystems like RSA cryptosystem, Diffie–Hellman key exchange and elliptic curve cryptography are based on number theory and hence depend on commutative algebraic structures.

In the mathematical subject of group theory, a one-relator group is a group given by a group presentation with a single defining relation. One-relator groups play an important role in geometric group theory by providing many explicit examples of finitely presented groups.

In the mathematical subject of group theory, the Adian–Rabin theorem is a result that states that most "reasonable" properties of finitely presentable groups are algorithmically undecidable. The theorem is due to Sergei Adian (1955) and, independently, Michael O. Rabin (1958).

References