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 be a finite directed graph (hereafter a digraph) with an initial vertex, and edges labeled by elements of a finite set
in such a way that each vertex has at most one outgoing edge with any given label. A finite directed path in
starting at the initial vertex determines a word in the alphabet
, by reading the labels on the edges traversed (in order). The set
of words obtained in this way is an example of what is called a regular language, and is said to be parameterized by
. Note that this is not the most general kind of regular language; in particular, any language
of this kind will necessarily be prefix-closed (i.e. if
then every prefix of
is also in
). Note also that different digraphs might parameterize the same (prefix-closed) regular language
.
If is a set of generators for a group
, there is an obvious map
called the evaluation map that takes a word
to the element of
represented by that word.
Definition: Let be a group, and
a finite generating set. A combing of
is a (prefix-closed) regular language
for which the evaluation map
is a bijection, and such that every
represents a geodesic in
.
The intuition behind this definition is that the set of words in determines a directed spanning tree in the Cayley graph
starting at
, and such that every directed path in the tree is a geodesic in
. 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 be a hyperbolic group, and let
be a finite generating set. Choose a total order on the elements of
. Then the language
of lexicographically first geodesics in
is a combing.
The language described in this theorem is obviously geodesic and prefix-closed, and the evaluation map is bijective; the content of the theorem is that
is regular, and parameterized by some finite digraph
. In the sequel, we restrict attention exclusively to hyperbolic groups
.
Given a (hyperbolic) group , a generating set
, a combing
, one makes the following definition:
Definition: A function is weakly combable (with respect to
) if there is a digraph
parameterizing
and a function
from the vertices of
to
so that for any
, corresponding to a path
in
, there is an equality
.
In other words, a function is weakly combable if it can be obtained by “integrating” a function
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
, and bicombable if it changes by a bounded amount under either left or right multiplication by an element of
. The property of being (bi-)combable does not depend on the choice of a generating set
or a combing
.
Example: Word length (with respect to a given generating set ) is bicombable.
Example: Let be a homomorphism. Then
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 be a finite set which generates
as a semigroup. Let
denote word length with respect to
, and
denote word length with respect to
(which also generates
as a semigroup). Then the difference
is a bicombable quasimorphism.
The main theorem proved in the paper concerns the statistical distribution of values of a bicombable function.
Theorem: Let be a hyperbolic group, and let
be a bicombable function on
. Let
be the value of
on a random word in
of length
(with respect to a certain measure
depending on a choice of generating set). Then there are algebraic numbers
and
so that as distributions,
converges to a normal distribution with standard deviation
.
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 are two finite generating sets for a group
, then there is a constant
so that every word of length
in one generating set has length at most
and at least
in the other generating set. If one considers an example like
, one sees that this is the best possible estimate, even statistically. However, if one restricts attention to a hyperbolic group
, then one can do much better for typical words:
Corollary: Let be hyperbolic, and let
be two finite generating sets. There is an algebraic number
so that almost all words of length
with respect to the
generating set have length almost equal to
with respect to the
generating set, with error of size
.
Let me indicate very briefly how the proof of the theorem goes.
Sketch of Proof: Let be bicombable, and let
be a function from the vertices of
to
, where
is a digraph parameterizing
. There is a bijection between the set of elements in
of word length
and the set of directed paths in
of length
that start at the initial vertex. So to understand the distribution of
, we need to understand the behaviour of a typical long path in
.
Define a component of 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
without loops, with one vertex for each component of
, in an obvious way. Each component
determines an adjacency matrix
, with
-entry equal to
if there is a directed edge from vertex
to vertex
, and equal to
otherwise. A component
is big if the biggest real eigenvalue
of
is at least as big as the biggest real eigenvalue of the matrices associated to every other component. A random long walk in
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
.
A theorem of Coornaert implies that there are no big components of in series; i.e. there are no directed paths in
from one big component to another (one also says that the big components do not communicate). This means that a typical long walk in
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
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 corresponding to paths that spend almost all their time in a given big component
there is a central limit theorem
where the mean
and standard deviation
depend only on
. 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
; to finish the proof one must use bicombability.
It is not hard to show that if is a typical infinite walk in a component
, then the subpaths of
of length
are distributed like random walks of length
in
. What this means is that the mean and standard deviation
associated to a big component
can be recovered from the distribution of
on a single infinite “typical” path in
. Such an infinite path corresponds to an infinite geodesic in
, converging to a definite point in the Gromov boundary
. Another theorem of Coornaert (from the same paper) says that the action of
on its boundary
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
associated to components
and
for which some
takes
to a geodesic
ending at the same point in
as
. Bicombability implies that the values of
on
and
differ by a bounded amount. Moreover, since
and
are asymptotic to the same point at infinity, combability implies that the values of
on
and
also differ by a bounded amount. This is enough to deduce that
and
, and one obtains a (global) central limit theorem for
on
. qed.
This obviously raises several questions, some of which seem very hard, including:
Question 1: Let be an arbitrary quasimorphism on a hyperbolic group
(even the case
is free is interesting). Does
satisfy a central limit theorem?
Question 2: Let be an arbitrary quasimorphism on a hyperbolic group
. Does
satisfy a central limit theorem with respect to a random walk on
? (i.e. one considers the distribution of values of
not on the set of elements of
of word length
, but on the set of elements obtained by a random walk on
of length
, and lets
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 where
is a closed negatively curved Riemannian manifold; such quasimorphisms are defined by choosing a
-form
, and defining
to be equal to the integral
, where
is the closed oriented based geodesic in
in the homotopy class of
. De Rham quasimorphisms, being local, also satisfy a central limit theorem.
This locality manifests itself in another way, in terms of defects. Let be a quasimorphism on a hyperbolic group
. Recall that the defect
is the supremum of
over all pairs of elements
. A quasimorphism is further said to be homogeneous if
for all integers
. If
is an arbitrary quasimorphism, one may homogenize it by taking a limit
; one says that
is the homogenization of
in this case. Homogenization typically does not preserve defects; however, there is an inequality
. If
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)
with the prefix of
(with notation as above). When one homogenizes, one picks up another contribution to the defect from the interaction of the prefix of
with the suffix of
; 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 be a group, and let
be a homogeneous quasimorphism. Is there a quasimorphism
with homogenization
, satisfying
?
Example: The answer to question 3 is “yes” if is the rotation quasimorphism associated to an action of
on
by orientation-preserving homeomorphisms (this is nontrivial; see Proposition 4.70 from my monograph).
Example: Let be any homologically trivial group
-boundary. Then there is some extremal homogeneous quasimorphism
for
(i.e. a quasimorphism achieving equality
under generalized Bavard duality; see this post) for which there is
with homogenization
satisfying
. Consequently, if every point in the boundary of the unit ball in the
norm is contained in a unique supporting hyperplane, the answer to question 3 is “yes” for any quasimorphism on
.
Any quasimorphism on 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
is a free group. An interesting test case might be the homogenization of an infinite sum of Brooks functions
for some infinite non-nested family of words
.
If the answer to this question is false, and one can find a homogeneous quasimorphism which is not the homogenization of any “local” quasimorphism, then perhaps
does not satisfy a central limit theorem. One can try to approach this problem from the other direction:
Question 4: Given a function defined on the ball of radius
in a free group
, one defines the defect
in the usual way, restricted to pairs of elements
for which
are all of length at most
. Under what conditions can
be extended to a function on the ball of radius
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.
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
if and only if the bi-harmonic antisymmetric representative (for some fixed measure, that we may choose!) satisfies
. 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.
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