Presentations and the Word Problem

What a presentation is

You already know groups from Volume I as sets with an operation. Geometric group theory begins with a different gesture: hand someone an alphabet of generators and a list of relations, and ask what group those rules force. The data ⟨S | R⟩ is a group presentation. Formally it names the quotient F(S)/N, where F(S) is the free group on S and N is the normal closure of R — the smallest normal subgroup containing every relator. Everything that is true in the group is exactly what you can derive from the relators; nothing else is imposed.

Familiar groups as presentations:

  Z/nZ      = < a | a^n >
  Z x Z     = < a, b | a b a^-1 b^-1 >        (one commutator relator => abelian)
  D_n       = < r, s | r^n, s^2, s r s r >     (dihedral, order 2n)
  S_3       = < a, b | a^3, b^2, b a b a >     (same shape, n = 3)
  Z         = < a | >                          (no relators => free of rank 1)
  F_2       = < a, b | >                        (free of rank 2: NO relations)

Reading the Z x Z relator: a b a^-1 b^-1 = 1 says ab = ba.
A relator w means 'the word w equals the identity'.

A relator is a word set equal to 1; the relation r^n means a^n = e.

When are two words equal?

Here is the central difficulty. A word in the generators is just a string like a b a⁻¹ b a. Two strings represent the same group element iff one can be turned into the other by inserting/deleting trivial pieces s s⁻¹ and by inserting/deleting relators. The word problem asks: given a word w, is w = 1 in the group? Equivalently, given w and v, is w = v? This is a decision problem, and you must take it seriously — there is no automatic procedure handed to you by the symbols.

Proving a b = b a in Z x Z = < a, b | aba^-1 b^-1 >:

  start:    a b
  insert the relator (= 1) on the right:
            a b . (b^-1 a^-1 b a)        <- this inserted word is a conjugate of the relator, = 1
            = a (b b^-1) a^-1 b a
            = a a^-1 b a
            = b a                          done.

Every equality in a finitely presented group is, in principle,
such a finite chain of relator-insertions and free cancellations.
The trouble: there is no a-priori bound on how LONG the chain must be.

A derivation is a finite sequence of relator insertions and free cancellations — but its length is uncontrolled.

Why it can be undecidable

The honest, sobering fact: there is a finitely presented group whose word problem is algorithmically unsolvable (Novikov 1955, Boone 1958). No program can take a word in that group and always correctly decide whether it equals 1. This is not a gap in our cleverness; it is a theorem, built by encoding a Turing machine inside group relations. So the geometric program is not a luxury — for general groups, there is no symbolic shortcut, and the only handle is *shape*.