Combable functions

The purpose of this post is to discuss my recent paper with Koji Fujiwara, which will shortly appear in Ergodic Theory and Dynamical Systems, both for its own sake, and in order to motivate some open questions that I find very intriguing. The content of the paper is a mixture of ergodic theory, geometric group theory, and computer science, and was partly inspired by a paper of Jean-Claude Picaud. To state the results of the paper, I must first introduce a few definitions and some background.

Let \Gamma be a finite directed graph (hereafter a digraph) with an initial vertex, and edges labeled by elements of a finite set S in such a way that each vertex has at most one outgoing edge with any given label. A finite directed path in \Gamma starting at the initial vertex determines a word in the alphabet S, by reading the labels on the edges traversed (in order). The set L \subset S^* of words obtained in this way is an example of what is called a regular language, and is said to be parameterized by \Gamma. Note that this is not the most general kind of regular language; in particular, any language L of this kind will necessarily be prefix-closed (i.e. if w \in L then every prefix of w is also in L). Note also that different digraphs might parameterize the same (prefix-closed) regular language L.

If S is a set of generators for a group G, there is an obvious map L \to G called the evaluation map that takes a word w to the element of G represented by that word.

Definition: Let G be a group, and S a finite generating set. A combing of G is a (prefix-closed) regular language L for which the evaluation map L \to G is a bijection, and such that every w \in L represents a geodesic in G.

The intuition behind this definition is that the set of words in L determines a directed spanning tree in the Cayley graph C_S(G) starting at \text{id}, and such that every directed path in the tree is a geodesic in C_S(G). Note that there are other definitions of combing in the literature; for example, some authors do not require the evaluation map to be a bijection, but only a coarse bijection.

Fundamental to the theory of combings is the following Theorem, which paraphrases one of the main results of this paper:

Theorem: (Cannon) Let G be a hyperbolic group, and let S be a finite generating set. Choose a total order on the elements of S. Then the language L of lexicographically first geodesics in G is a combing.

The language L described in this theorem is obviously geodesic and prefix-closed, and the evaluation map is bijective; the content of the theorem is that L is regular, and parameterized by some finite digraph \Gamma. In the sequel, we restrict attention exclusively to hyperbolic groups G.

Given a (hyperbolic) group G, a generating set S, a combing L, one makes the following definition:

Definition: A function \phi:G \to \mathbb{Z} is weakly combable (with respect to S,L) if there is a digraph \Gamma parameterizing L and a function d\phi from the vertices of \Gamma to \mathbb{Z} so that for any w \in L, corresponding to a path \gamma in \Gamma, there is an equality \phi(w) = \sum_i d\phi(\gamma(i)).

In other words, a function \phi is weakly combable if it can be obtained by “integrating” a function d\phi along the paths of a combing. One furthermore says that a function is combable if it changes by a bounded amount under right-multiplication by an element of S, and bicombable if it changes by a bounded amount under either left or right multiplication by an element of S. The property of being (bi-)combable does not depend on the choice of a generating set S or a combing L.

Example: Word length (with respect to a given generating set S) is bicombable.

Example: Let \phi:G \to \mathbb{Z} be a homomorphism. Then \phi is bicombable.

Example: The Brooks counting quasimorphisms (on a free group) and the Epstein-Fujiwara counting quasimorphisms are bicombable.

Example: The sum or difference of two (bi-)combable functions is (bi-)combable.

A particularly interesting example is the following:

Example: Let S be a finite set which generates G as a semigroup. Let \phi_S denote word length with respect to S, and \phi_{S^{-1}} denote word length with respect to S^{-1} (which also generates G as a semigroup). Then the difference \psi_S:= \phi_S - \phi_{S^{-1}} is a bicombable quasimorphism.

The main theorem proved in the paper concerns the statistical distribution of values of a bicombable function.

Theorem: Let G be a hyperbolic group, and let \phi be a bicombable function on G. Let \overline{\phi}_n be the value of \phi on a random word in G of length n (with respect to a certain measure \widehat{\nu} depending on a choice of generating set). Then there are algebraic numbers E and \sigma so that as distributions, n^{-1/2}(\overline{\phi}_n - nE) converges to a normal distribution with standard deviation \sigma.

One interesting corollary concerns the length of typical words in one generating set versus another. The first thing that every geometric group theorist learns is that if S_1, S_2 are two finite generating sets for a group G, then there is a constant K so that every word of length n in one generating set has length at most nK and at least n/K in the other generating set. If one considers an example like \mathbb{Z}^2, one sees that this is the best possible estimate, even statistically. However, if one restricts attention to a hyperbolic group G, then one can do much better for typical words:

Corollary: Let G be hyperbolic, and let S_1,S_2 be two finite generating sets. There is an algebraic number \lambda_{1,2} so that almost all words of length n with respect to the S_1 generating set have length almost equal to n\lambda_{1,2} with respect to the S_2 generating set, with error of size O(\sqrt{n}).

Let me indicate very briefly how the proof of the theorem goes.

Sketch of Proof: Let \phi be bicombable, and let d\phi be a function from the vertices of \Gamma to \mathbb{Z}, where \Gamma is a digraph parameterizing L. There is a bijection between the set of elements in G of word length n and the set of directed paths in \Gamma of length n that start at the initial vertex. So to understand the distribution of \phi, we need to understand the behaviour of a typical long path in \Gamma.

Define a component of \Gamma to be a maximal subgraph with the property that there is a directed path (in the component) from any vertex to any other vertex. One can define a new digraph C(\Gamma) without loops, with one vertex for each component of \Gamma, in an obvious way. Each component C determines an adjacency matrix M_C, with ij-entry equal to 1 if there is a directed edge from vertex i to vertex j, and equal to 0 otherwise. A component C is big if the biggest real eigenvalue \lambda of M_C is at least as big as the biggest real eigenvalue of the matrices associated to every other component. A random long walk in \Gamma will spend most of its time entirely in big components, so these are the only components we need to consider to understand the statistical distribution of \phi.

A theorem of Coornaert implies that there are no big components of C(\Gamma) in series; i.e. there are no directed paths in C(\Gamma) from one big component to another (one also says that the big components do not communicate). This means that a typical long walk in \Gamma is entirely contained in a single big component, except for a (relatively short) path at the start and the end of the walk. So the distribution of \phi gets independent contributions, one from each big component.

The contribution from an individual big component is not hard to understand: the central limit theorem for stationary Markov chains says that for elements of G corresponding to paths that spend almost all their time in a given big component C there is a central limit theorem  n^{-1/2}(\overline{\phi}_n - nE_C) \to N(0,\sigma_C) where the mean E_C and standard deviation \sigma_C depend only on C. The problem is to show that the means and standard deviations associated to different big components are the same. Everything up to this point only depends on weak combability of \phi; to finish the proof one must use bicombability.

It is not hard to show that if \gamma is a typical infinite walk in a component C, then the subpaths of \gamma of length n are distributed like random walks of length n in C. What this means is that the mean and standard deviation E_C,\sigma_C associated to a big component C can be recovered from the distribution of \phi on a single infinite “typical” path in C. Such an infinite path corresponds to an infinite geodesic in G, converging to a definite point in the Gromov boundary \partial G. Another theorem of Coornaert (from the same paper) says that the action of G on its boundary \partial G is ergodic with respect to a certain natural measure called a Patterson-Sullivan measure (see Coornaert’s paper for details). This means that there are typical infinite geodesics \gamma,\gamma' associated to components C and C' for which some g \in G takes \gamma to a geodesic g\gamma ending at the same point in \partial G as \gamma'. Bicombability implies that the values of \phi on \gamma and g\gamma differ by a bounded amount. Moreover, since g\gamma and \gamma' are asymptotic to the same point at infinity, combability implies that the values of \phi on g\gamma and \gamma' also differ by a bounded amount. This is enough to deduce that E_C = E_{C'} and \sigma_C = \sigma_{C'}, and one obtains a (global) central limit theorem for \phi on G. qed.

This obviously raises several questions, some of which seem very hard, including:

Question 1: Let \phi be an arbitrary quasimorphism on a hyperbolic group G (even the case G is free is interesting). Does \phi satisfy a central limit theorem?

Question 2: Let \phi be an arbitrary quasimorphism on a hyperbolic group G. Does \phi satisfy a central limit theorem with respect to a random walk on G? (i.e. one considers the distribution of values of \phi not on the set of elements of G of word length n, but on the set of elements obtained by a random walk on G of length n, and lets n go to infinity)

All bicombable quasimorphisms satisfy an important property which is essential to our proof of the central limit theorem: they are local, which is to say, they are defined as a sum of local contributions. In the continuous world, they are the analogue of the so-called de Rham quasimorphisms on \pi_1(M) where M is a closed negatively curved Riemannian manifold; such quasimorphisms are defined by choosing a 1-form \alpha, and defining \phi_\alpha(g) to be equal to the integral \int_{\gamma_g} \alpha, where \gamma_g is the closed oriented based geodesic in M in the homotopy class of g. De Rham quasimorphisms, being local, also satisfy a central limit theorem.

This locality manifests itself in another way, in terms of defects. Let \phi be a quasimorphism on a hyperbolic group G. Recall that the defect D(\phi) is the supremum of |\phi(gh) - \phi(g) -\phi(h)| over all pairs of elements g,h \in G. A quasimorphism is further said to be homogeneous if \phi(g^n) = n\phi(g) for all integers n. If \phi is an arbitrary quasimorphism, one may homogenize it by taking a limit \psi(g) = \lim_{n \to \infty} \phi(g^n)/n; one says that \psi is the homogenization of \phi in this case. Homogenization typically does not preserve defects; however, there is an inequality D(\psi) \le 2D(\phi). If \phi is local, one expects this inequality to be an equality. For, in a hyperbolic group, the contribution to the defect of a local quasimorphism all arises from the interaction of the suffix of (a geodesic word representing the element) g with the prefix of h (with notation as above). When one homogenizes, one picks up another contribution to the defect from the interaction of the prefix of g with the suffix of h; since these two contributions are essentially independent, one expects that homogenizing a local quasimorphism should exactly double the defect. This is the case for bicombable and de Rham quasimorphisms, and can perhaps be used to define locality for a quasimorphism on an arbitrary group.

This discussion provokes the following key question:

Question 3: Let G be a group, and let \psi be a homogeneous quasimorphism. Is there a quasimorphism \phi with homogenization \psi, satisfying D(\psi) = 2D(\phi)?

Example: The answer to question 3 is “yes” if \psi is the rotation quasimorphism associated to an action of G on S^1 by orientation-preserving homeomorphisms (this is nontrivial; see Proposition 4.70 from my monograph).

Example: Let C be any homologically trivial group 1-boundary. Then there is some extremal homogeneous quasimorphism \psi for C (i.e. a quasimorphism achieving equality \text{scl}(C) = \psi(C)/2D(\psi) under generalized Bavard duality; see this post) for which there is \phi with homogenization \psi satisfying D(\psi) = 2D(\phi). Consequently, if every point in the boundary of the unit ball in the \text{scl} norm is contained in a unique supporting hyperplane, the answer to question 3 is “yes” for any quasimorphism on G.

Any quasimorphism on G can be pulled back to a quasimorphism on a free group, but this does not seem to make anything easier. In particular, question 3 is completely open (as far as I know) when G is a free group. An interesting test case might be the homogenization of an infinite sum of Brooks functions \sum_w h_w for some infinite non-nested family of words \lbrace w \rbrace.  

If the answer to this question is false, and one can find a homogeneous quasimorphism \psi which is not the homogenization of any “local” quasimorphism, then perhaps \psi does not satisfy a central limit theorem. One can try to approach this problem from the other direction:

Question 4: Given a function f defined on the ball of radius n in a free group F, one defines the defect D(f) in the usual way, restricted to pairs of elements g,h for which g,h,gh are all of length at most n. Under what conditions can f be extended to a function on the ball of radius n+1 without increasing the defect?

If one had a good procedure for building a quasimorphism “by hand” (so to speak), one could try to build a quasimorphism that failed to satisfy a central limit theorem, or perhaps find reasons why this was impossible.

This entry was posted in Ergodic Theory and tagged , , , , , , . Bookmark the permalink.

2 Responses to Combable functions

  1. Tobias Hartnick says:

    For a positive answer to Question 2 for random walks with symmetric i.i.d increments see

    Interestingly, the assumption of hyperbolicity can be dropped alltogether (although in terms of examples it remains probably the most interesting case).

    A remarkable fact used in the proof of the main theorem is the observation (due to Burger and Monod) that every quasimorphism can be made biharmonic with respect to almost any given symmetric measure by adding a bounded function. This seems not to be so widely known, but is very useful in many situations.

    Traditionally, many people in the subject are used to work with homogeneous quasimorphisms. This is often a good approach, since e.g. conjugation-invariance is a very strong property. However, one should not forget that there also exist other quasimorphisms with nice properties, such as harmonic ones. By a slight extension of the Burger-Monod result mentioned above we show in the above paper that given any equivalence class of quasimorphisms (i.e. a family of quasimorphism which are at bounded distance from each other) and a “nice” symmetric measure on the group (e.g. assume the support is finite and generates the whole group), there always exists a unique bi-harmonic, antisymmetric (f(g)^{-1} = -f(g)) quasimorphism in this class. This representative has a couple of remarkable properties (largely independent of the choice of measure!). The most remarkable one I learned from Th. Huber (unfortunately still unpublished): Every such bi-harmonic antisymmetric representative minimizes the defect within the given equivalence class.

    This yields e.g. a major simplification to Question (3) above: There exists a positive solution \phi if and only if the bi-harmonic antisymmetric representative (for some fixed measure, that we may choose!) satisfies D(\psi) = 2D(\phi). This does not (yet) answer Question (3), but it tells you where to look for examples.

    In any case, I hope that the paper cited above will increase the popularity of harmonic quasimorphisms in geometric and (particularly) measurable group theory.

    • Danny Calegari says:

      Dear Tobias – thanks for this comment. I intend to write a blog post at some point about your beautiful paper with Bjorklund, but it might take a while since I have an 8 day old new baby . . . Although it is true that the experts have known about harmonic quasimorphisms since Burger-Monod, I think your paper is the most impressive use of such representatives (that I know), and the application is wonderful.

      As you know, Joseph Maher and I recently worked out a special case of your central limit theorem – for the rotation quasimorphism for groups acting on a circle. This case is nice because of the relationship between harmonic quasimorphism and harmonic measure on the circle. I wonder whether there is an interesting interaction of harmonic measure with order structures for other natural quasimorphisms, e.g. from actions on causal manifolds like Shilov boundaries (after Clerc-Koufany), where one uses the order structure to integrate measures along causal paths?

      One nice application of your theorem is that for any group in which scl does not vanish identically, one has that scl of a random walk of length n grows like at least order sqrt(n). By a completely different method, Joseph and I have shown that scl of a random walk of length n grows like at most order n/log(n) (and equality is achieved in hyperbolic groups and mapping class groups). It would be very interesting to come up with some finitely presented examples with intermediate growth of scl (i.e. strictly bigger than sqrt(n) and strictly smaller than n/log(n)).



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s