Asymptotics of the number of required Dehn relators in hyperbolic groups

2012-04-16T13:59:13Z

If $G = \langle X | R \rangle$ is a $\delta$-hyperbolic group presentation, then Dehn's algorithm provides a linear time solution to the word problem, but the linear constant is horribly exponential in $\delta$ since the Dehn presentation consists of all words of length $8 \delta$ equal to the identity.

Are there any known lower bounds on the number of relators required to make Dehn's algorithm solve the word problem? In other words, does anyone know a family of groups for which the required number of Dehn relators is exponential in either the size of the original group's presentation or the original groups $\delta$.

Answer by Mark Sapir for Asymptotics of the number of required Dehn relators in hyperbolic groups

2012-04-16T15:20:41Z

Here is an idea of an example (just for a start). Take the finite group $A_n$ (it is hyperbolic). It has a short presentation, see this paper. The total size of relations is something like $\log |A_n|$. I am sure the $\delta$ for that presentation is about $\log |A_n|$ also. A Dehn presentation of $A_n$ should require about $|A_n|$ relators.

Actually one can take $S_n$ and generators $(i,i+1)$. The total size of the Coxeter presentation is $O(n^2)$. It would be interesting to find the $\delta$ for this presentation. It should be polynomial in $n$.

Update. Here is another, more realistic, idea (actually it can be made into a complete answer with a little effort involving reading Gromov's paper or, better, a paper by Yan Ollivier). Take the Ramanujan expander $\Gamma_i$: the number of vertices in $i$-th graph $\Gamma_i$ is $n_i$, the degree of each vertex is a constant $k$, the girth, the diameter, and the maximal length of a basic loop is $\log n_i$, the rank of the fundamental group of $\Gamma_i$ is $\sim k^{\alpha\log n_i}$ for some $\alpha<1/2$. Consider the Gromov random group $G_i$ corresponding to the graph $\Gamma_i$. It is hyperbolic with $\delta=O(\log n_i)$, the number of relations in every Dehn presentation (with sufficiently small Dehn constant) is aproximately the number of relators (because the relators do not have large pieces in common), i.e. the number of relators in any Dehn presentation is exponential in $\Delta$.

Asymptotics of the number of required Dehn relators in hyperbolic groups - MathOverflow

Asymptotics of the number of required Dehn relators in hyperbolic groups

Answer by Mark Sapir for Asymptotics of the number of required Dehn relators in hyperbolic groups