Word Problem For Groups - Examples

Examples

The following groups have a solvable word problem:

  • Automatic groups, including:
    • Finite groups
    • Polycyclic groups
    • Negatively curved groups
    • Euclidean groups
    • Coxeter groups
    • Braid groups
    • Geometrically finite groups
  • Finitely generated recursively absolutely presented groups, including:
    • Finitely presented simple groups.
  • Finitely presented residually finite groups
  • One relator groups (this is a theorem of Magnus), including:
    • Fundamental groups of closed orientable two-dimensional manifolds.
  • Combable groups

Examples with unsolvable word problems are also known:

  • Given a recursively enumerable set A of positive integers that has insoluble membership problem, ⟨a,b,c,d | anban = cndcn : n ∈ A⟩ is a finitely generated group with a recursively enumerable presentation whose word problem is insoluble (Collins & Zieschang 1990, p. 149)
  • 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 (Collins & Zieschang 1993, Cor. 7.2.6)
  • The number of relators in a finitely presented group with insoluble word problem may be as low as 14 by (Collins 1969) or even 12 by (Borisov 1969), (Collins 1972).
  • 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}

Read more about this topic:  Word Problem For Groups

Famous quotes containing the word examples:

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)

    “There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
    —Bernard Mandeville (1670–1733)

    “No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
    —André Breton (1896–1966)