Algorithms in hyperbolic groups

Question

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?

Answer 1

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!

Answer 2

At the risk of being subjective (and possibly even argumentative), I feel like I should offer an answer to the implicit question, answered piquantly by Derek Holt:

'a large proportion of researchers in Geometric Group Theory appear to be interested only in the existence of algorithms and their complexity, rather than in actually using them to do computations'.

It's really wonderful for group theorists when we have algorithms that can actually be run on examples we care about. Derek has done a lot of great work on this, as have many others. A different recent example which I find very striking is Calegari--Walker's algorithm for finding surface subgroups of ascending HNN extensions of free groups, which they were able to use to find a surface subgroup in an old example of Sapir. (No surprise it hadn't been found by hand - the surface was of genus 32!)

But general results about the (non-)existence of algorithms or their complexity play another, completely different, role in group theory. Many researchers (I count myself among this number) are less interested in particular groups than in classes of groups: finitely presented groups, hyperbolic groups etc. In this setting, algorithmic results are not about computations at all, but rather play an important strategic role. They help us to orient ourselves in these classes of groups, get a sense of how 'wild' or 'tame' they are, and work out which sorts of questions are reasonable to pursue.

Here's a story which I think illustrates this point nicely.

A famous theorem of Adyan and Rabin (ca. 1956) asserts that the triviality problem for finitely presented groups is not algorithmically solvable. This result in turn relies on the Novikov--Boone theorem, which exhibits a group with unsolvable word problem. One reasonable interpretation is that the class of finitely presented groups is too 'wild' to classify. This is an important strategic result in combinatorial group theory, and one might be tempted to deduce that one should give up on the theory of finitely presented groups altogether.

Now fast forward to about 1980, and Gromov's discovery that, although the class of finitely presented groups is 'wild', a 'random' finitely presented group is in fact hyperbolic, and so has many nice algorithmic properties (linear Dehn function, automaticity etc). I think of this result as 'rescuing' combinatorial group theory from the Adyan--Rabin nightmare, using geometry.

Without any computation, these theorems give us great insight into how we should think about finitely presented groups: in short, an arbitrary fp group is intractable, but a generic fp group is quite nice.

Finally, it may be worth pointing out that these general facts are not just attractive; they have enormous 'strategic' importance, closing off certain directions of research and consequently focussing attention on others. For instance, it can be deduced from the Adyan--Rabin theorem that it's impossible to classify smooth 4-manifolds. Since classifying 3-manifolds (in the form of geometrization) was the dominant research direction in 3-manifold topology for decades, just imagine how different 4-manifold topology might be if a classification were believed possible!