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:

    “Histories are more full of examples of the fidelity of dogs than of friends.”
    —Alexander Pope (1688–1744)

    “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)

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