Some background (see e.g. the books by Ghys & de la Harpe or Bridson & Haefliger for more information):

Let $\Gamma$ be a group with a finite symmetric generating set $S$. Recall that $\Gamma$ is called a (word) hyperbolic group if the Cayley graph of $(\Gamma, S)$ is hyperbolic (in the sense of Gromov). This notion is independent of the choice of the generating set $S$.

Assuming $\Gamma$ to be hyperbolic, there is a finite directed graph canonically associated to $(\Gamma,S)$ called the geodesic automaton (GA), whose arrows are labelled by elements of $S$. Paths in the GA graph starting from a special basepoint correspond to segments of geodesics in the Cayley graph.

Now consider the recurrent vertices of the GA graph, i.e., the set of vertices that belong to loops. Following this paper by Haissinsky, Mathieu, and Mueller, let us say that the GA graph is strongly connected if given any two recurrent vertices, there is one path from one to the other.

For example, if $\Gamma = \mathbb{Z}$ and $S = \{1,-1\}$ then the GA graph is: GA graph of Z which is obviously not strongly connected.

Question. If $\Gamma$ is a nonelementary hyperbolic group, is the geodesic automaton graph strongly connected for some (all?) choice of $S$?


1 Answer 1


If I understand correctly, you are asking if the automaton graph is recurrent, that is there is only one non trivial recurrence class (a recurrence class is trivial if it is reduced to one vertex).

For Fuchsian groups, you can always find a generating set such that the automaton graph is recurrent. This was proved by Caroline Series in the paper The infinite word problem and limit sets in Fuchsian groups (Ergodic theory and dynamical system, 1981).

However, in general, we do not know how to construct such an $S$. Applying Cannon's method does not necessarily yields a recurrent graph. Here is an example. Take the free group with two generators $a,b$.

Taking the generating set $S=\{a,b,a^{-1},b^{-1}\}$ would give you a connected automaton. Indeed, two elements have the same cone-type if and only if their normal forms end with the same letter. So you have 5 cone-types which gives you 5 states in the automaton : $e$ (the neutral element), $a$, $b$, $a^{-1}$ and $b^{-1}$. You can go from $e$ to any other cone-type, except itself, and in fact you can go from any state to any other state except $e$ and its inverse.

Now, take the generating set $S'$ consisting of every element with one or two letters, that is $S'$ is the ball of radius 2 minus $e$ for the word metric coming from $S$. To compute the cone-types, first notice that if $g$ has odd $S$-length $2n+1$ (that is, it is at distance $2n+1$ from $e$ for the generating set $S$), then any $S$'-geodesic from $e$ to $g$ will have length $n+1$. More precisely, it will consist of $n$ increments of $S$-length 2 and 1 element of $S$-length 1. In particular, you can only extend such a geodesic adding increments of $S$-length 2. What it means is that once you reached a odd $S$-length element, you can only extend geodesics to odd $S$-length elements, while for an even $S$-length element, you can either extend it to another even $S$-length element, or add a $S$-length 1 increment and get stuck in the odd $S$-length component.

Note also that the only thing (besides parity) that counts, to know how you can extend geodesics, is the last letter in the normal form. Combining all this, you see there are 9 distinct cone-types : that of $e$, those of $a,b,a^{-1},b^{-1}$ and those of $ab,ab^{-1},ba,ba^{-1}$. In particular, note that $ab$ and $a^{-1}b$ have the same cone-type. You can go from $a$ to any other state with one letter (for example you can go from $a$ to $a^{-1}$ adding the element $ba^{-1}$, which you could not do using the generating set $S$). More generally, the sub-graph consisting of states with one letter is strongly connected. Similarly, the sub-graph consisting of states with two letter is strongly connected. You can also go from $ab$ to any state with one letter, except $b^{-1}$, etc...

The only thing you need to do is to choose an order on elements of $S'$ and to consider only geodesics that are shortest for the lexicographical order. But even if you need to remove some of the edges, this does not change the components. What you get in the end is a graph with exactly two recurrent classes (odd and even $S$-lengths cone-types). You can go from the even-type reccurent class to the odd one, but not the other way around. And of course, there is also one edge from $e$ to any other state.

I hope this was clear enough. You see here that even for the free group, given some generating set, it is very hard to tell whether you will get a recurrent automaton or not. Here it was possible to compute the cone-types, but this might be a very difficult task in general. Asking around, it seems to me that some people believe that it should be possible to always find a good $S$ (I mean with a recurrent associated automaton). Some others think that this is impossible to tell.

Now, I'll try to explain how you can get around this difficulty. I strongly recommend the survey of Danny Calegari The ergodic theory of hyperbolic groups (available on his webpage).

If you want to do dynamics on the path space of the automaton, say you have a function defined on this path space, you can look at the so-called maximal components. Those are the recurrent components of you graph such that the spectral data of your function (usually the dominant eigenvalue of the associated transfer operator) is maximal. What can go wrong is if you have a path from one maximal component to another one (but not the other way around, otherwise these would not be two different components).

This was explored in the paper of Danny Calegari and Koji Fujiwara Combable functions,quasimorphisms, and the central limit theorem (Ergodic theory and dynamical systems, 2010). See also the paper of Sébastien Gouëzel Local limit theorem for symmetric random walks in Gromov-hyperbolic groups (Journal of the AMS, 2014).

  • $\begingroup$ Thanks for the useful information. If I understood correctly, the question is open. $\endgroup$ Sep 11, 2018 at 12:30
  • $\begingroup$ @JairoBochi Sorry for the long delay. Haïssinsky told me that the free groups with generating set words of normal form-length 1 or 2 yields an automaton with poor properties. Computing the cone-types, I indeed found that you get a non-strongly connected graph, using your terminology. I think this answers partially your question. $\endgroup$
    – M. Dus
    Apr 28, 2020 at 9:17
  • $\begingroup$ This example illustrates nicely how transitivity can fail. The general comments are also helpful. Thanks! $\endgroup$ Apr 28, 2020 at 16:24
  • 1
    $\begingroup$ Incidentally, this example shows that you can have two group elements with two shortest word representations having an arbitrarily long common suffix, and yet determining different cone types: consider a^{2n} = a^2 ... a^2 and a^{2n+1} = a.a^2 ... a^2. $\endgroup$ Apr 29, 2020 at 12:46
  • $\begingroup$ @JairoBochi That's a very interesting remark ! $\endgroup$
    – M. Dus
    Apr 29, 2020 at 20:17

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.