I'm stuck in some algorithms in hyperbolic groups, which may be rather simple.
Let $G$ be a hyperbolic group given by a finite presentation. It is known that the hyperbolicity constant $\delta$ can be computable from the given presentation (by papasoglu, but I could not find/read the related reference).
We also know there exists Dehn presentation for $G$ which allows to solve word problems in $G$. Here is my question. Is it clear how to obtain a Dehn presentation in practice?
In general, every relator in Dehn presentation is of form $wv$, where $w$ is a word of length upper bounded by a constant, for example, $8\delta+1$, and $v$ is of length strictly less than $u$ such that $u, v$ represent the same group element. So there are at most finitely many such relators.
But in practice, how to list these relators? Of course, $u, v$ are of finite length. There are finitely many choices to list. But how to know whether $u, v$ give the same group element? Is it amount to saying that $G$ has a soluble word problem?
In some practical cases, we can do it by other means. For example, in surface groups, we can use the group action on the hyperbolic plane to efficatively decide whether $u$ and $v$ give the same transformation.
So in general, is there a way to do this in algorithms? or researchers in math are just satisfied with the EXISTENCE of Dehn algorithms?
Best Answer
An algorithm for computing the hyperbolic "thinness" constant $\delta$ is described in the paper:
Epstein, David B. A.; Holt, Derek F Computation in word-hyperbolic groups. Internat. J. Algebra Comput. 11 (2001), no. 4, 467–487.
and I did implement it. It works OK on reasonably straightforward examples like surface groups, hyperbolic triangle groups, etc, but it takes a long time and uses a lot of memory on more difficult examples.
Papasoglu proved that if geodesic bigons in the Cayley graph are uniformly thin, then the group is hyperbolic, and it is possible to get a bound on the hyperbolic constant from his proof in terms of the bigon thinness constant, but it is something like doubly exponential. That is frustrating, given that the bigon constant is comparatively easy to compute in practice, and in all the examples we have ever computed, the hyperbolic constant is at most one more than the bigon constant. But attempts to derive a better bound have been unsuccessful so far. (I have discussed this with Papasoglu, who has tried to do this himself.)
As for your question, except in special cases, I don't know of any better way of finding a Dehn presentation other than by using the presentation given by the standard proof, which (as you said) takes all length reducing rewrite rules arising from group relators of length at most $8\delta+1$. That of course usually gives impracticably many rewrite rules, and it is unlikely that they are are all needed. And, as you said, you really need to be able to solve the word problem already in order to compute this list of relations - but in general you can do that: see below.
In practice, we can find a finite state automaton (fsa) that accepts all geodesic words, and then from that, using standard fsa operations, you could find an fsa that accepts all minimal non-geodesic words (i.e. all subwords geodesic), and enumerate its language up to length $4\delta+1$ to give a complete set of left hand sides of Dehn rewrite rules.
The difficulty here is that there does not seem to be any method known for verifying that a suspected Dehn presentation really is one. This is connected with the fact that decidability of "confluence on the identity" for a finite rewrite system is known to be undecidable in general, although I would guess that it might be decidable in the case of putative Dehn presentations of hyperbolic group.
However, if what you really want to do is to solve the word problem in practice in hyperbolic groups, then there really are practical methods for doing that. Just compute the automatic structure of the group (you can do that in GAP or Magma) and use that. In theory that yields a quadratic time algorithm for the word problem, whereas the Dehn algorithm is linear, but it is unlikely that you would notice that difference.
Concerning your final question, I do get the impression that a large proportion of researchers in Geoemtric Group Theory appear to be interested only in the existence of algorithms and their complexity, rather than in actually using them to do computations, which I find a strange attitude, but that is opinion based!