7
$\begingroup$

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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Mark: Did you try ${\mathbb Z_2}^n$? $\endgroup$
    – Misha
    Commented Apr 16, 2012 at 17:30
  • $\begingroup$ I hadn't even considered finite groups, but amusingly the alternating and symmetric groups might be "the easiest example to bear in mind" for my purposes, thanks! $\endgroup$
    – Jeff Burdges
    Commented Apr 16, 2012 at 19:57
  • $\begingroup$ @Misha: This can also work. I am only afraid that the growth function of an Abelian group is polynomial. Anyway, this example should be feasible. $\endgroup$
    – user6976
    Commented Apr 16, 2012 at 20:20
  • $\begingroup$ @Misha: $\mathbb{Z}_2^n$ probably works too. The diameter of $\mathbb{Z}_2^n$ is $n$. So $\delta$ must be about $n$ too. Now if you consider arbitrary two permutations $\sigma,tau$ of $1,...,n$, then words $x_{\sigma 1}...x_{\sigma n}x_{\tau 1}...x_{\tau n}$ is equal to 1 in the group. If $\sigma$ and $\tau$ are sufficiently random, these words should not have long common subwords. So the Dehn presentation should have exponentially many relations. It all needs to be checked of course. $\endgroup$
    – user6976
    Commented Apr 16, 2012 at 20:46
  • $\begingroup$ The problem with $\mathbb{Z}_2^n$ (which does not exist in random groups) is that there are many small relations (=short loops in the Cayley graph). Most very long words contain one of the short words, so I do not see a reason why Dehn presentation does not consist of short relations. The defining relations are all of length $\le 4$. $\endgroup$
    – user6976
    Commented Apr 17, 2012 at 0:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .