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.

2 Responses to Combable functions

Tobias Hartnick says:

May 4, 2010 at 9:03 am

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

http://arxiv.org/abs/1005.0077

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:
  
  May 4, 2010 at 10:25 am
  
  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)).
  
  Best,
  
  Danny

	Vikas Kumar on Roots, Schottky semigroups, an…
	Mapping class groups… on Chiral subsurface projection,…
	Danny Calegari on Groups quasi-isometric to…
	ianagol on Groups quasi-isometric to…
	Bill Thurston \| The… on Bill Thurston 1946-2012