§ Hyperbolic groups have solvable word problem

I have never seen an elementary account of this in a 'trust these facts, now here is why hyperbolic groups have a solvable word problem'. I am writing such an account for myself. It's an account for building intuition, so no proofs will be provided except for the final theorem. All facts will be backed by intuition. Since most of it is geometric, it's easy to convey intuition.

§ Graphs of groups, quasi-isometry.

  • NOTE: I will consistently denote the inverse of gg by g−1g^{-1}.
We can convert any group into a graph by using the cayley graph of the group. We characterize hyperbolic space as a space where we can build 'thin triangles'. We also think of hyperbolic space as where geodesics from a given point diverge (in terms of angle) exponentially fast. The choice of generators for the cayley graph gives different graphs. We can assign a unique geometric object by considering cayley graphs upto quasi isometry. The cayley graph of a group with respect to different generating sets are quasi-isometric. We can now try to study properties that are invariant under quasi-isometry, since these are somehow 'represented faithfully by the geometry'.

§ Hyperbolicity enters the picture

We now say that a graph is hyperbolic if the cayley graph of the group is hyperbolic. We can show that hyperbolicity is preserved by quasi-isometry. So this property does not depend on the generating set.

§ Isoperimetric Inequality

If we have a finitely presented group G=⟨S∣R⟩G = \langle S | R \rangle, and ww is a word in the free group Free(S)Free(S), if [[w]]=1[[w]] = 1, we will have
w=∏i=1nuiri±1ui′ w = \prod_{i=1}^n u_i r_i^{\pm 1} u_i'
This follows almost by definition. Since we have quotiented by rr we can have elements of rr in between uu′u u'. We will need to have a u′u' since there's nothing else to cancel off the uu.

§ Area of a word

Let G=⟨S∣R⟩G = \langle S | R \rangle. Let ww be a word in SS such that [[w]]=e[[w]] = e. The area of the word ww is the minimal number of such uru′u r u' components we need to write it down. Formally:
Area(w)=min⁡n∣∏i=1nuir+i±1ui′ Area(w) = \min { n | \prod_{i=1}^n u_i r+i^{\pm 1} u_i'}
I don't understand the geometric content of this definition. I asked on mathoverflow .

§ Isopermetric function for a group

f:N→Nf: \mathbb N \rightarrow \mathbb N is a Dehn function or isoperimetric function if the area of the word is upper bounded by f(∣word∣)f(|word|). In some sense, the length of the word is the perimeter to the area, and this gives us a form of the isoperimetric inequality. Formally, ff is a Dehn function if for all words w∈F(S)w \in F(S) such that [[w]]=e[[w]] = e, we have A(w)≤f(∣w∣)A(w) \leq f(|w|). depending on the growth of ff, we say that GG has linear, quadratic, exponential etc. Dehn function.

§ Geometric content of Area

We define a map to be aninite, planar, oriented, connected and simply connected simplicial2-complex (!). A map DD is a diagram over an alphabet SS iff every edge e∈De \in D has a label lbl(e)∈Slbl(e) \in S such that lbl(e−1)=(lbl(e))−1lbl(e^{-1}) = (lbl(e))^{-1}. Hang on: what does it mean to invert an edge? I presume it means to go backwards along an edge. So we assume the graph is directed, and we have edges in both directions. A Van Kampen diagram over a group G=⟨S∣R⟩G = \langle S | R \rangle is a diagram DD over SS such that for all faces of DD, the label of the boundary of ff is labelled by some r±:r∈Rr^{\pm} : r \in R. The area of such a diagram is the number of faces.

§ Hyperbolic iff Linear Isopermetric Inequality is satisfied

A finitely presented group is hyperbolic if and of if its cayley grah satisfies the linear isoperimetric inequality.

§ Deciding if elements are conjugate to each other

  • If we can answer the question of whether two elements are conjugate to each other (does there exist a gg such that ghg′=?=kghg' =?= k), we can solve that an element is equal to the identity:
  • Pick k=ek = e. Then if we have ghg′=k=eghg' = k = e, then gh=ggh = g hence h=eh = e.
  • If we can check that an element is equal to the identity, we can check for equality of elements. two elements k,lk, l are equal iff kl′=ekl' = e.
  • So solving conjugacy automatically allows us to check of equality.

§ Proof that conjugacy is solvable for hyperbolic groups

Consider a solution to the problem of finding an xx such that xgx−1=hxgx^{-1} = h. We claim that due to the hyperbolicity of the space, such an xx cannot be "too long".

§ Key intuition for hyperbolicity allows us to control word length

  • Suppose we are interested to find a gg such that ghg−1=eghg^{-1} = e
  • We can think of this as a case where hh is the base edge of a triangle, ee is the opposite vertex, and g,g−1g, g^{-1} are the other two sides: 
    e
   / \
  g  g^{-1}
 /     \
+---h---+
  • If the space is euclidea, then gg and g−1g^{-1} can be as long as they want to be while hh stays the same. The angles gh,hg−1gh, hg^{-1} will become larger, and the angle gg−1gg^{-1} will become smaller as the length ggincreases.
  • In a hyperbolic space, because the angle sum is less than 180, if we move ee too far away, the hh will "bend" to maintain the angle sum to be less than 180. But this means that we have distorted the hh! There is a bound to how long we can make gg before we start distorting hh. This bound on gg is exponential in the length of hh.
  • Alternatively, in a CAT-0 space, the base of the triangle cannot be too far away from the centroid. So we can't have ee be moved too far away, because if gggets too large.

§ References