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:

    “In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
    —Michel de Montaigne (1533–1592)

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