3
$\begingroup$

I am learning a little bit about Dehn functions of group presentations and I came across a question that is probably pretty basic but that I was giving me trouble. I'll set some notation but essentially I want to understand why being able to compute an upper bound for the Dehn function means that the word problem is solvable.

Let $\phi: F(A) \to G$ be a surjective homomorphism of groups where $A$ is a finite set and $F(A)$ is the free group on $A$. Also assume that the kernel of this homomorphism is normally generated by a finite set $R$. In other words, we are given a finite presentation of $G$. Let $\delta : \mathbb{N} \to \mathbb{N}$ be the Dehn function of this presentation, namely, $\delta(n)$ is the smallest number such that every element $w \in F(A)$, with $\ell(w) \leq n$ and $\phi(w) = 1$, as the product of conjugates of $\delta(n)$ elements of $R$ (or there inverses). Namely, for such $w$, we have $$w = \prod_{i=1}^M p_i r_i^{\epsilon_i} p_i^{-1}$$ with $p_i \in F(A)$, where the above equality is in $F(A)$.

I was told that we can assume that there is a way to find such an expression with $M \leq \delta(n)$ and $\ell(p_i) \leq \ell(w) + M \rho$ where $\rho$ is the max length of the elements in $R$. Why is this the case?

I was thinking of this in terms of van Kampen diagrams where I see equations of the above from as "flowers". The Dehn function tells us how many "petals" we need. But I was hoping to have short "petals" (and not too many). Can you help me shorten the petals?

$\endgroup$
  • $\begingroup$ In addition to references given by Mark Sapir: see Lemma 2D2 here and its short proof (modulo the existence of van Kampen diagrams). It says, for a presentation $\langle S|R\rangle$ ($S,R$ not necessarily finite) with $M=\sup_{x\in R}|x|$ that is a relation $w\in F_S$ has length $n$ and area $A$ and then $w$ can be written as product of $A$ conjugates of $\le A$ elements of $R^\pm$ where the conjugating elements have length $\le n+MA$. Mark mentions the upper bound $\le n+4MA$, so I hope we made no mistake! $\endgroup$ – YCor Apr 4 at 7:38
  • $\begingroup$ This is an example of a result in combinatorial group theory for which I have never seen a purely algebraic proof. That is, a proof that makes no use of van Kampen diagrams, which are guess make implicit use of the geometry of the Euclidean plane. $\endgroup$ – Derek Holt Apr 5 at 7:46
2
$\begingroup$

It is, in particular, in my book "Combinatorial algebra: syntax and semantics" which can be found on my Web site. The length of each "petal" is at most the length of the word plus the Dehn function multiplied by a constant. The book contains a proof (in fact a stronger result is proved). It is essentially a copy of our proof (with A.Yu. Olshanskii) from the paper https://arxiv.org/pdf/math/9811107.pdf of 1998. A longer proof with a slightly worse estimate is in the introduction to my joint paper with Birget and Rips (there is only one such paper in the arXiv). It is where we prove that the word problem in a group with Dehn function $f(n)$ can be solved by a nondeterministic Turing machine in time $\sim f(n)$. And of course the original paper by Madlener and Otto contains a (nonlinear) estimate of the lengths of conjugates. Related statements about a double exponential relationship between Dehn function and isodiametric function of a f.p. group was proved by Gersten.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.