I am trying to understand the proof that a linear dehn function implies solvable conjugacy. I am referring to Notes on solvable and automatic groups by Michael Batty, after Panagiotis Papasoglu. Here is a screenshot of the proof:

enter image description here


  1. How do I use the $2 \delta$ thinness of a rectangle? [What is the $2\delta$ thinness of a rectangle]?
  2. Where have we used every possible combinations of elements of $S$?
  3. How does there being two different $i, j$ such that $x_i^{-1} g_1 x_i = x_j^{-1} g_1 x_j$?

Related question and its answer:

There is another math.se question on the same topic, which has an answer:

Consider the geodesic quadrangle in the Cayley graph with two "vertical sides" and two horizontal sides labelled $x, g_1, x^{-1}, g_2^{-1}$, the ("horizontal") sides $g_1,g_2$ are much shorter than the "vertical" sides labelled by $x$ because we assume, by contradiction, that there is no algorithm to find $x$ given $g_1,g_2$. We can also, as you noted, assume that $x$ is the shortest possible. Then each side is in a union of $2\delta$-neighborhoods of the other three sides (divide the quadrangle by a diagonal). The intersections of $2\delta$ neighborhoods of the short sides with the left vertical side are small. Therefore a large portion of the left side is in a $2\delta$-neighborhood of the right vertical side. That means for most $i$ $x_ig_1x_i^{-1}$ has length at most $d=2\delta(1+|g_1|+|g_2|)$. Here $x_i$ is the suffix of $x$ of length $i$. The length of $x$ can be assumed to be $\ge \exp(d)$, so for some $i<j$ we have $x_ig_1x_i=x_jg_1x_j$. But that implies, we can cut the subword between $x_i$ and $x_j$ from $x$ and still get a (shorter) conjugator $x'$, a contradiction.


  1. I am unsure I even know the definition of $2\delta neighbourhood$: Is it $nbhd_{2 \delta}(g) = \{ h \in G: |hg^{-1}| \leq 2\delta \}$?
  2. Given the above definition, how is it that each side is a $2\delta$ nbhd of the other sides?

My attempt: enter image description here

Of course, all the action is in step (2) which I have no idea how to make rigorous --- in particular, that $\delta$ thinness will force overlaps.

  • $\begingroup$ I think, "thin" is confused with "slim." For quadrilaterals, the later reads: Every side is contained in the closed $2\delta$-neighborhood of the union of the three other sides. $\endgroup$ Aug 13, 2020 at 21:08

1 Answer 1


Questions 1, 4, and 5

Your questions 1,4,5 are basically the same. For our purposes a $\delta$-neighborhood of a set $A$, in a metric space $X$, is the set $$\bigcup_{x \in A} B(x,\delta)$$ where $B(x,\delta)$ is the $\delta$ radius ball around $x$ (some might say closed ball or whatever, it doesn't really make much of a difference). Your definition given in (4) works although the notes use $< 2 \delta$. As an aside I think it is better to think about distance in terms of distance in the Cayley graph.

A geodesic quadrilateral is $2\delta$-thin if the $2\delta$-neighborhood of the union of any three sides covers the fourth side. Basically the same as the thin triangle condition. The answer you cite gives a hint, and it is an exercise to show, that a space having the $\delta$-thin triangle condition will have $2\delta$-thin quadrilateral condition. The hint is to decompose into two triangles and use $\delta$-thinness.

Questions 2 and 3

(note $x=y_1...y_n$)

To answer question two the sides labeled $x$ have long segments, greater than $|S|^{2\delta}$, which are $2 \delta$ close. Call these segments $x'$. What that means is you can draw a path from one side to the other which is less than $2 \delta$, which gives you a word of length less than $2\delta$*.

If you have segments $x'$ of length greater $|S|^{2 \delta}$, as in the picture, you can connect $y_i$'s with a path of length less than $2\delta$*. Call these paths $u_i$. Since there are more than $|S|^{2 \delta}$ $y_i$'s in $x'$ we can use the pigeonhole principle to get that at least two $<2\delta$ segments, $u_i$ and $u_j$, that reads off the same word, $u$. If you read along the boundary that gives you the $x_i,x_j$ such that $x_i^{-1} g_1 x_i = x_j^{-1} g_1 x_j=u$.

*There is a slight error in what the length bounds of $x_i^{-1}g_1 x_i$. While the "straight across" is less than $2 \delta$ it is possible that will not correspond to the $x_i^{-1}g_1 x_i$ path. The picture below tries to illustrate what could go wrong.

Illustrating length of conjugate

The idea, in words, is that you can have one of the sides follow $g_1$ for a while and the other side does not follow at all. Instead of the $2\delta$ bound you get $|x_i^{-1}g_1 x_i| \leq 2\delta+|g_1|$ to account for this potential "following" behavior. From here you just change the constants that use that and the rest is fine. This is done in the Geometric group theory notes by Panos Papazoglou, cited in the question you link to.

  • $\begingroup$ Thank you for the explanation! Unfortunately, I am still confused; I feel I am missing a lot of details. Perhaps I should re-study much of this. (i) does "long segments greater than $|S|^{2 \delta}$ mean that the length of $x$ as a word is greater than $S^{2 \delta}$? (ii) "if you have segments of less greater than $|S|^{2 \delta}$": By segments, do you mean the segments of $x = \langle x_1 x_2 \dots x_n \rangle$, which will be $x_i = \langle x_1 x_2 \dots x_i \rangle$?... $\endgroup$ Aug 14, 2020 at 8:28
  • $\begingroup$ ... (iii) "...you can connect the segments with more than $|S|^{2 \delta}$ segments of length less than $2\delta$: This is meant to be read as: If the length of $x$ is $l > |S|^{2 \delta}$, then we can find the "vertical connections", one for each $x_i$, each of length less than $2\delta$? (iv) We are pigeon-holing "elements of $S$" into $2 \delta$ slots? Since the total number of strings of length $2 \delta$ is $|S|^{2 \delta$, we must have two of these vertical lines read the same word? $\endgroup$ Aug 14, 2020 at 8:42
  • $\begingroup$ ...(v)How do we finish the contradiction? Is it as follows: $x^{-1} g_1 x = g_2$, so $x_n^{-1} \dots (x_j^{-1} \dots x_i^{-1} \dots x_1^{-1} g_1 x_1 \dots x_i \dots x_j) \dots x_n = g_2$. We write this as $x_n^{-1} \dots x_{j+1}^{-1} x[:j]^{-1} g_1 x[:j] \dots x_n$? (Where the notation $x[:j]$ is the substring of $x$ upto $j$; $x[:j] := x_1 x_2 \dots x_j$). Hence, $x_n^{-1} \dots (x[:i]^{-1}g_1x[:i]) \dots x_n = g_2$? By replacing the segment of $x[:j]^{-1}g_1x[:j]$ with $x[:i]^{-1} g_1 x[:i]$, we have reduced the length of the string, because $i < j$, contradicts that $x$ was minimal $\endgroup$ Aug 14, 2020 at 8:44
  • 1
    $\begingroup$ (i) yes, assume $x$ is greater than the bound given (ii) the segment of $x$ is the part that is $2\delta$ close and sufficiently far from $g_i$, (III)(IV)(V) yes. $\endgroup$
    – user29123
    Aug 14, 2020 at 13:11
  • 2
    $\begingroup$ @Siddhath Bhat Thanks, if I had a tablet or something I would have drawn some pictures which would make it easier to follow. And yah, sometimes just doing your own proof is faster than trying to understand someone elses since you won't be caught up by weird phrasing or details they see as obvious when writing etc(especially when you are familiar with some of the ideas) $\endgroup$
    – user29123
    Aug 14, 2020 at 14:50

You must log in to answer this question.

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