Posted by: matheuscmss | March 31, 2015

Subadditive cocycles and horofunctions (after Gouëzel and Karlsson)

Last March 25th, Sébastien Gouëzel gave the talk “Subadditive cocycles and horofunctions” at the Ergodic Theory and Dynamical Systems seminar of LAGA , Université Paris 13.

As it is always the case with Sébastien’s expositions, he managed to communicate very clearly the ideas of a mathematically profound subject (and, by the way, this topic is not directly related to his excellent Bourbaki seminar talk from March 21st).

In the sequel, I’ll transcript my lecture notes for Sébastien’s talk. Of course, all errors and mistakes are my entire responsibility.

1. Introduction

Let us warmup by giving a proof of the following theorem:

Theorem 1 (Kohlberg-Neyman (1981)) Let {\phi:\mathbb{R}^d\rightarrow\mathbb{R}^d} be a weak contraction of the Euclidean space {(\mathbb{R}^d, \|.\|)} in the sense that

\displaystyle \|\phi(x)-\phi(y)\|\leq \|x-y\|

for all {x,y\in\mathbb{R}^d}.Then, the sequence

\displaystyle \frac{\phi^n(0)}{n}

converges as {n\rightarrow\infty}.

Remark 1 The origin {0\in\mathbb{R}^d} can be replaced by any point {x_0\in\mathbb{R}^n} because

\displaystyle \|\phi^n(x_0)-\phi^n(0)\|\leq \|x_0\|

so that

\displaystyle \lim\limits_{n\rightarrow\infty}\frac{\phi^n(x_0) - \phi^n(0)}{n} = 0

As the reader might suspect, the fact that such an “innocent-looking” result was proved only in 1981 (in this paper here) indicates that its proof is not easy to find if we don’t use the “correct” setup.

For the purposes of this post, we will show Theorem 1 using a argument of Karlsson (from 2001).

Proof: The argument has two steps:

  • the first step is to show that the distance of {\phi^n(0)/n} to the origin converges;
  • the second step is to control the direction of {\phi^n(0)/n}.

The convergence of the distance

\displaystyle \|\frac{\phi^n(0)}{n}-0\| = \frac{\|\phi^n(0)\|}{n}:=\frac{u_n}{n}

follows from the subadditivity of {u_n}.

More precisely, since {\phi} is a weak contraction, we have that

\displaystyle \begin{array}{rcl} u_{n+m} &=& \|\phi^{n+m}(0)-0\|\leq \|\phi^n(\phi^m(0))-\phi^n(0)\| + \|\phi^n(0)-0\| \\ &\leq& \|\phi^m(0)-0\|+\|\phi^n(0)-0\| = u_m + u_n \end{array}

From this, it is not hard to see that {(u_n/n)_{n\in\mathbb{N}}} converges to {A:=\inf\limits_{n\in\mathbb{N}} u_n / n \geq 0}.

Indeed, given {\varepsilon>0}, we fix {n_0\in\mathbb{N}} such that

\displaystyle \frac{u_{n_0}}{n_0}<A+\varepsilon

Next, given {n\in\mathbb{N}}, we write {n=an_0+b} with {0\leq b <n_0}. From the subadditivity of {(u_n)}, we have that

\displaystyle u_n\leq a u_{n_0} + u_b\leq a u_{n_0} + \max\{u_b: 0\leq b < n_0\}:= au_{n_0} + C(n_0)

In particular,

\displaystyle \begin{array}{rcl} A&\leq& \frac{u_n}{n}\leq \left(\frac{a n_0}{n}\right) \frac{u_{n_0}}{n_0} + \frac{C(n_0)}{n} \\ &\leq& A + \varepsilon + \frac{C(n_0)}{n} \leq A + 2\varepsilon \end{array}

for all {n} sufficiently large (i.e., {n>C(n_0)/\varepsilon}). In other words, we have that

\displaystyle A\leq \liminf\limits_{n\rightarrow\infty} \frac{u_n}{n}\leq \limsup\limits_{n\rightarrow\infty}\frac{u_n}{n}\leq A+2\varepsilon

for any {\varepsilon>0}, that is, {\lim\limits_{n\rightarrow\infty}(u_n/n)=A}, as desired.

Next, let us control the direction of {\phi^n(0)/n}.

Observe that the case when {A=0} is easy: by definition, the sequence {\phi^n(0)/n} converges to the origin {0}, so that the proof of the theorem is complete in this situation.

Thus, it remains only to consider the case when {A>0}, i.e., the sequence {\phi^n(0)} goes to {\infty} with positive linear speed.

Fix a sequence {0<\varepsilon_i<A} such that {\varepsilon_i\rightarrow 0} as {i\rightarrow\infty}. Note that, by definition, for each {i\in\mathbb{N}}, one has

\displaystyle u_n-(A-\varepsilon_i)n\rightarrow\infty

as {n\rightarrow\infty}. This means that we can consider {n_i\geq 2^i} a sequence of “records” of the excursion of {\phi^n(0)} towards {\infty}, i.e.,

\displaystyle u_{n_i} - (A-\varepsilon_i)n_i \geq u_{n_i-l} - (A-\varepsilon_i) (n_i-l)

for all {0\leq l\leq n_i}.

Denote by {h_i} a linear form on {\mathbb{R}^d} of norm {1} so that {h_{n_i}(\phi^{n_i}(0)) = -\|\phi^{n_i}(0)\|}. Because {h_i} has norm {1} and {\phi} is a weak contraction, we see that

\displaystyle \begin{array}{rcl} h_i(\phi^l(0)) &=& h_i(\phi^l(0)-\phi^{n_i}(0)) + h_i(\phi^{n_i}(0)) \leq \|\phi^l(0) - \phi^{n_i}(0)\| - \|\phi^{n_i}(0)\| \\ &\leq& \|0-\phi^{n_i-l}(0)\|-\|\phi^{n_i}(0)\| = u_{n_i-l} - u_{n_i} \end{array}

for all {0\leq l\leq n_i}.

Since {n_i} is a sequence of records, we conclude that

\displaystyle h_i(\phi^l(0))\leq u_{n_i-l}-u_{n_i}\leq -(A-\varepsilon_i)l

for all {0\leq l\leq n_i}.

Now, we note that, up to taking a subsequence, one can assume that the sequence of linear forms {h_i} of norm {1} converges (in the weak-{\ast} topology) to a linear form {h}.

By construction, {h(\phi^l(0))\leq -Al} for all {l\in\mathbb{N}}. Geometrically, this means that the sequence {\phi^l(0)} stays to the right of a sequence of parallel hyperplanes moving with linear speed to infinity.

Indeed, this is easily visualized in two dimensions: after rotating the kernel of {h} in {\mathbb{R}^2}, we can suppose that {h(x,y)=-x}. In this case, the inequality {h(\phi^l(0))\leq -Al} means that {\phi^l(0)} belongs to the half-plane {H_l=\{(x,y)\in\mathbb{R}^2: x\geq Al\}}.

From this geometric input, it is not hard to complete the proof of the theorem.

In fact, we have that, on one hand, {\phi^l(0)\in H_l} for all {l\in\mathbb{N}}, and, on the other hand, for each {\varepsilon>0}, we have that {\phi^l(0)\in B_{l,\varepsilon}:=B((0,0),(A+\varepsilon)l)} for all {l} sufficiently large (because {\|\phi^l(0)\|/l=u_l/l\rightarrow A}).

From the strict convexity of the Euclidean ball {B_{l,\varepsilon}}, we obtain that {\phi^l(0)} belongs to the small lenticular regions {H_l\cap B_{l,\varepsilon}} whose geometries forces the direction of {\phi^l(0)} to be {\varepsilon}-close to the unit vector {e_1=(1,0)} perpendicular to the kernel of {h(x,y)=-x}. Since {\varepsilon>0} is arbitrary, we conclude that the directions of {\phi^l(0)} converge (to {e_1} in our current situation).

Of course, this convergence together with the fact that {\|\phi^l(0)\|/l = u_l/l \rightarrow A} as {l\rightarrow\infty} finishes the proof of the theorem. \Box

Remark 2 Note that, except for the last part of the proof (where the geometry [strict convexity] of balls entered in the discussion), Karlsson’s argument can be generalized to abstract Banach spaces in the place of {\mathbb{R}^d}: for instance, the existence of the linear functionals {h_i} follows from Hahn-Banach theorem, and the weak-{\ast} convergence of a subsequence of {h_i} is a consequence of Banach-Alaoglu theorem.

Remark 3 The statement of Theorem 1 is very sensitive on the choice of the norm. For example, this theorem is false for {\mathbb{R}^2} equipped with the supremum norm {\|(x,y)\|_{\infty} = \sup\{|x|,|y|\}}. In fact:

  • Karlsson’s argument fails because the information

    \displaystyle \phi^l(0)\in H_l\cap B_{\|.\|_{\infty}}((0,0), (A+\varepsilon)l)

    does not impose strong constraints in the direction of {\phi^l(0)} since the “ball”

    \displaystyle B_{\|.\|_{\infty}}((0,0), (A+\varepsilon)l)

    is now a square, and the “lenticular region”

    \displaystyle H_l\cap B_{\|.\|_{\infty}}((0,0), (A+\varepsilon)l)

    is a now rectangle of width {\varepsilon l} and height {2(A+\varepsilon)l}.

  • A weak {\|.\|_{\infty}}-contraction {\phi:\mathbb{R}^2\rightarrow\mathbb{R}^2} such that {\phi^n(0)/n} does not converge can be constructed as follows. Let {v=(1,0)} and {w=(1,1)}. Consider a sequence of times {(t_i)_{i\in\mathbb{N}}\subset\mathbb{R}} such that {t_i\ll t_{i+1}}. Using this sequence of times, we define {\gamma:[0,\infty)\rightarrow\mathbb{R}^2} so that {\gamma} follows a straight line segment in the direction {v} for time {t_1}, then a straight line segment in the direction {w} for time {t_2}, then a straight line segment in the direction {v} for time {t_3}, etc. (e.g., {\gamma(t)=tv} for {0\leq t\leq t_1}, {\gamma(t)=t_1v + (t-t_1)w} for {t_1\leq t\leq t_2}, etc.); Since {\gamma} consists of straight line segments of slopes {0} or {1}, one can see that {\gamma} is a geodesic ray for the supremum norm {\|.\|_{\infty}} (such that {\|\gamma(s)-\gamma(t)\|_{\infty} = |s-t|}); From {\gamma}, we define a weak {\|.\|_{\infty}}-contraction {\phi:\mathbb{R}^2 \rightarrow \mathbb{R}^2} by letting

    \displaystyle \phi(z) = \gamma(|h(z)|+1)

    where {h(z)=-x} for {z=(x,y)\in\mathbb{R}^2}. In this context, {\phi^n(0)=\gamma(n)} and, for an appropriate choice of times {t_i\ll t_{i+1}}, one can check that {\phi^n(0)/n} does not converge because its direction keeps oscillating between {v=(1,0)} and {w=(1,1)}.

2. Horofunctions

After this quick review of Karlsson’s proof of Kohlberg-Neyman theorem for weak contractions in Euclidean spaces, let us pass now to the study of weak contractions in metric spaces.

For this sake, we need the following tool (playing the role of “linear functionals”):

Definition 2 Let {(X,d)} be a metric space and {x_0\in X}. We say that a function {h:X\rightarrow \mathbb{R}} is a horofunction (or Busemann function) if there exists a sequence {(y_n)_{n\in\mathbb{N}}\subset X} such that

\displaystyle h(x) = \lim\limits_{n\rightarrow\infty} (d(y_n,x)-d(y_n,x_0))

Remark 4 By definition, {h(x_0)=0}. Furthermore, {h} is a {1}-Lipschitz function (because it is the limit of the {1}-Lipschitz functions {h_n(x):=d(y_n,x)-d(y_n,x_0)}).

Example 1 Consider the Euclidean space {\mathbb{R}^2} and let {x_0=(0,0)}, {y_n=(n,0)}. The level sets of the function {h_n(z) = d(y_n,z)-d(y_n,x_0)} are the Euclidean balls centered at {y_n}: more precisely, {h_n} takes the value {r-n} on the circle of radius {r} centered at {y_n}. From this, one can see that {h_n} converges to the linear functional {h(x,y)=-x}. In this way, we see that linear functionals in Euclidean spaces are particular cases of horofunctions.

Example 2 Consider the plane {\mathbb{R}^2} equipped with the supremum norm {\|.\|_{\infty}}. Let {x_0=0} and {y_n=(n,n)}. A direct inspection reveals that the level sets of {h_n(z) = d_{\|.\|_{\infty}}(y_n, z) - d_{\|.\|_{\infty}}(y_n,x_0)} are translations along the diagonal of the first quadrant of {\mathbb{R}^2}, i.e., {(r,r)+Q} where {Q=\{(x,y)\in\mathbb{R}^2: x, y\geq 0\}}. In particular, {h_n} converges to the horofunction {h_{\infty}(x,y)=-\inf\{x,y\}}.

Remark 5 It is possible to show that any horofunction on a normed vector space can be estimated from below by a linear functional. In particular, the level sets of horofunctions provide more information on the location of points than the level sets of linear functionals.

Example 3 In the case of the hyperbolic plane, the horofunctions are the classical Buseman functions (whose level sets are the horospheres).

The same argument used by Karlsson to prove Theorem 1 allowed him to show the following result:

Theorem 3 (Karlsson (2002)) Let {(X,d)} be a separable metric space, {\phi:X\rightarrow X} a weak contraction, and {x_0\in X}.Then,

\displaystyle \lim\limits_{n\rightarrow\infty} \frac{d(\phi^n(x_0), x_0)}{n} = A\geq 0

and there exists a horofunction {h} such that {h(\phi^l(x_0))\leq -Al} for all {l\in\mathbb{N}}.

3. Iterated systems of contractions

Note that Karlsson’s theorem gives a geometrical description of the orbits of a single weak contraction, but one might wonder about the behavior of “random” compositions (cocycle) of several weak contractions.

In this direction, Gouëzel and Karlsson proved the following theorem:

Theorem 4 (Gouëzel-Karlsson) Let {T:(\Omega,\mathbb{P})\rightarrow (\Omega,\mathbb{P})} be a ergodic transformation, {(X,d)} be a metric space and {\phi:\Omega \rightarrow \textrm{Contraction}(X,d)} an (integrable) cocycle (where {\textrm{Contraction}(X,d)} is the set of weak contractions of {(X,d)}).Denote by {\phi^n(\omega) = \phi(\omega)\circ\dots\circ\phi(T^{n-1}(\omega))}. Then, there exists {A\geq 0} such that, for {\mathbb{P}}-almost every {\omega\in\Omega}, all {x_0\in X}, and some horofunction {h_{\omega}}, we have that

\displaystyle \frac{d(\phi^n(\omega)(x_0),x_0)}{n}\rightarrow A\geq 0


\displaystyle \frac{h_{\omega}(\phi^n(x_0))}{n}\rightarrow -A

as {n\rightarrow\infty}.

Remark 6 There is no hope to get this kind of convergence result if we compose the weak contractions in the other way around in the definition of {\phi^n(\omega)}. In fact, this is not hard to see in the context of the composition of random (large) hyperbolic matrices in {SL(2,\mathbb{R})} acting on the hyperbolic disk {\mathbb{D}^2}: since a large hyperbolic matrix {A} tends to concentrate a big chunk of {\mathbb{D}^2} near a boundary point {\xi(A)} associated to the unstable direction of {A}, we have that the compositions

\displaystyle A_n\circ\dots\circ A_1

of random large hyperbolic matrices {A_i} will most likely take the origin {0} of {\mathbb{D}^2} near the random boundary point {\xi(A_n)}, and, thus {A_n\circ\dots\circ A_1(0)} will not converge; on the other hand, the compositions

\displaystyle A_1\circ A_2\circ \dots\circ A_n

of random large hyperbolic matrices {A_i} will most likely take the random point {A_2\circ\dots\circ A_n(0)} near the deterministic boundary point {\xi(A_1)} and this is why we expect convergence of {A_1\circ\dots\circ A_n(0)}.

Before saying a few words about the proof of Gouëzel-Karlsson theorem, let us put it into historical perspective by citing a couple of previous related results:

  • Karlsson and Ledrappier showed in 2006 the validity of Gouëzel-Karlsson theorem in the special case of a cocycle {\phi} of isometries (by exploiting in particular the fact that the composition of a horofunction and a isometry is still a horofunction);
  • Karlsson and Margulis proved in 1999 the following slightly weaker version of Gouëzel-Karlsson theorem: under the same assumptions of Theorem 4, for each {\varepsilon>0}, there exists an horofunction {h_{\omega,\varepsilon}} such that

    \displaystyle \frac{h_{\omega,\varepsilon}(\phi^n(x_0))}{n}

    converges to a value in the interval {[-A, -A+\varepsilon]} as {n\rightarrow\infty}.

Let us now conclude this post with a sketch of proof of Theorem 4.

The first observation is that the sequence

\displaystyle u_n(\omega)=d(x_0,\phi^n(\omega)(x_0))

is a subadditive cocycle in the sense that

\displaystyle \begin{array}{rcl} u_{n+m} &=& d(x_0,\phi^{n+m}(\omega)(x_0)) \leq d(x_0, \phi^n(\omega)(x_0)) + d(\phi^n(\omega)(x_0), \phi^{n+m}(\omega)(x_0)) \\ &=& u_n + d(\phi^n(\omega)(x_0), \phi^n(\omega)\phi^m(T^n(\omega))(x_0)) \\ &\leq& u_n(\omega) + u_m(T^n(\omega)) \end{array}

Here, we used that {\phi} takes its values in the set of weak contractions and {\phi^k(\omega)} was defined as {\phi^k(\omega)=\phi(\omega)\circ \dots \circ \phi(T^{k-1}(\omega))} (in this order).

In this setting, we can apply Kingman’s subadditive ergodic theorem to deduce the convergence of {u_n(\omega)/n}:

Theorem 5 (Kingman (1967)) Let {u_n} be a (integrable) subadditive cocycle. Then,

\displaystyle \frac{u_n(\omega)}{n}\rightarrow A \quad \textrm{ as } n \rightarrow \infty

almost surely and in {L^1}. (Here, {A} is independent of {\omega}.)

Therefore, the proof of Gouëzel-Karlsson theorem will be complete once we construct a horofunction {h_{\omega}} with the properties in the statement of Theorem 4.

Unfortunately, the information provided by Kingman’s theorem is not sufficient to build up the desired {h_{\omega}}. For this reason, Gouëzel and Karlsson were “forced” to show the following improvement of Kingman’s subadditive ergodic theorem:

Theorem 6 (Gouëzel-Karlsson) Let {u_n(\omega)} be a (integrable) subadditive cocycle such that

\displaystyle \frac{u_n(\omega)}{n}\rightarrow A>-\infty

Then, for {\mathbb{P}}-almost every {\omega}, there are {n_i=n_i(\omega)\rightarrow\infty} as {i\rightarrow\infty} and {\delta_l = \delta_l(\omega)\rightarrow 0} as {l\rightarrow\infty} such that, for all {i} and all {0\leq l\leq n_i},

\displaystyle u_{n_i}(\omega) - u_{n_i-l}(T^l(\omega))\geq (A-\delta_l)l

An important point of this theorem is that {\delta_l} is independent from {n_i}! In particular, this fact can be exploited to build up a horofunction {h_{\omega}} (obtained as the limit of a subsequence of suitable functions {h_{n_i}} defined in the spirit of Karlsson’s proof of Kohlberg-Neyman theorem) such that

\displaystyle \frac{h_{\omega}(\phi^l(\omega))}{l}\leq -(A-\delta_l)

for all {l}. Of course, since {\delta_l\rightarrow 0} as {l\rightarrow\infty}, the previous estimate permits to conclude the proof of Gouëzel-Karlsson theorem.

Finally, the proof of Gouëzel-Karlsson improvement of Kingman’s theorem is similar in spirit to the usual proofs of Kingman’s result (based on the combinatorics of pieces of orbits of {T} where the values of the cocycle fluctuates near a given value).

However, the technical details are somewhat intrincate and, for this reason, Sébastien decided that it was a better idea to explain why the naive approach based on the study of times where the cocycle attains its “records” (as in Karlsson’s proof of Kohlberg-Neyman theorem) does not work.

So, we close this post by following him in the explanation of two naive strategies that fail in proving Theorem 6.

We begin by taking a sequence {\varepsilon_i\rightarrow0} as {i\rightarrow\infty}. By definition, for {\mathbb{P}}-almost every {\omega}, we have that

\displaystyle u_n(\omega) - (A-\varepsilon_i)n\rightarrow\infty

Thus, it makes sense to consider a sequence {n_i} of successive “records”, i.e.,

\displaystyle u_{n_i}(\omega) - (A-\varepsilon_i)n_i\geq u_{n_i-l}(\omega)-(A-\varepsilon_i)(n_i-l)

for all {0\leq l\leq n_i}. Of course, the previous inequality can be rewritten as

\displaystyle u_{n_i}(\omega) - u_{n_i-l}(\omega)\geq (A-\varepsilon_i)l

which looks like the conclusion of Theorem 6 except that the argument of {u_{n_i-l}} is {\omega} instead of {T^l(\omega)}!

At this point, we have the impression to be “close” to show Theorem 6, but this is not the case. Indeed, suppose that we try to overcome the difficulty of the previous paragraph by making the “change of variables” {v_n(\omega')=u_n(T^{-n}\omega)} (in hope of finding {T^l(\omega)} in the place of {\omega} in the argument of {u_{n_i-l}}). It is not hard to check that {v_n} is a subadditive cocycle with respect to {T^{-1}}. In particular, we can repeat our discussion with {u_n} replaced by {v_n} in order to find a sequence of “records”/good times {n_i} for almost every {\omega'}.

By doing so, we have that almost every {\omega'} belongs to infinitely many of the subsets

\displaystyle O_n'=\{\omega': n \textrm{ is a ``good'' time w.r.t. } v\}

Logically, we are not directly interested in the cocycle {v}, but rather on {u}. In other words, even though we got some information about the sets {O_n'}, we are really interested in the subsets

\displaystyle O_n=T^{-n}(O_n') = \{\omega: n \textrm{ is a good time w.r.t. } u\}

Here, it is tempting to conjecture that the fact that almost every {\omega} belongs to infinitely many {O_n} (from which case we would be able to deduce Theorem 6) is an immediate consequence of the fact that almost every {\omega'} belongs to infinitely many {O_n'}. Unfortunately, this conjecture is simply wrong if we do not have extra information about the structure of the subsets {O_n}: for example, let {O_n=O} be a fixed subset of positive but not full {\mathbb{P}}-measure; the ergodicity of {T} implies that {\mathbb{P}}-almost every {\omega'} belongs to infinitely many {O_n'=T^{n}(O)}, but it is obvious that the complement of {O} is a subset of positive {\mathbb{P}}-measure subset consisting of {\omega} which do not belong to a single {O_n=O}!

In summary, a naive combination of the “records” strategy and a change of variables do not lead us anywhere close to showing Theorem 6, and, in fact, a more sophisticated combinatorial strategy is needed here.


  1. Nice post, Matheus! A weaker version of Theorem 6 (with n_i depending on delta_ell) was proved by Karlsson and Margulis (1999). I like to think of that result as an “Ergodic Pliss Lemma”.

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


%d bloggers like this: