ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 5, Pages 82–90 (June 30, 1999) S 1079-6762(99)00065-7

POINTWISE THEOREMS FOR AMENABLE GROUPS

ELON LINDENSTRAUSS

(Communicated by Yitzhak Katznelson)

Abstract. In this paper we describe proofs of the pointwise ergodic theorem and Shannon-McMillan-Breiman theorem for discrete amenable groups, along Følner sequences that obey some restrictions. These restrictions are mild enough so that such sequences exist for all amenable groups.

1. Introduction

The classical ergodic theory deals with measure preserving ℤ actions. Since the 50’s, it has become increasingly clear that most of the results of the classical ergodic theory can be extended to actions of amenable groups, including such deep results as the isomorphism theorem for Bernoulli systems ([7]).

It is surprising, therefore, that two basic theorems of ergodic theory, the L^{1}- pointwise ergodic theorem and the Shannon-McMillan-Breiman theorem were not known for general amenable groups, even for the case of discrete groups considered here. While we consider only countable groups, the techniques we develop work also for general locally compact amenable groups. In addition, these techniques can be used to prove additional theorems on pointwise convergence. In the rest of this paper, all groups are assumed to be countable and discrete.

Amenability has many equivalent formulations; for us, the most convenient definition is that a discrete group G is amenable if for any finite K ⊂ G and δ > 0 there is a finite set F ⊂ G such that

|F △ kF | < δ|F | for all k ∈ K.

Such a set F will be called (K, δ)-invariant. A sequence F_{1}, F_{2}, … of finite subsets of G will be called a Følner sequence if for every K and δ > 0, for all large enough n we have that F_{n} is (K, δ)-invariant. To avoid uninteresting complications, we assume |F_{n}| ≥ n.

Suppose now that G acts from the left by measure preserving transformations on a Lebesgue space (X, B, μ) with μ(X) = 1. For simplicity we assume the G action to be ergodic, i.e., that there are no nontrivial G-invariant functions on X (this is not a real restriction, since we can always decompose the measure μ into its ergodic components). We recall the Mean Ergodic Theorem for amenable groups; this theorem can be easily proved by the same methods that work for ℤ actions.

\begin{matrix}c \\ ◯ \end{matrix}1999 American Mathematical Society

Received by the editors January 18, 1999.

1991 Mathematics Subject Classification. Primary 28D15.

Key words and phrases. Amenable groups, pointwise convergence, ergodic theorems.

The author would like to thank the Clore Foundation for its support.

Theorem 1.1. If G is amenable, and acts ergodically on (X, B, μ), then for any f ∈ L^{1}(μ), and Følner sequence F_{n},

A(F_{n}, f)(x) ⟶_{n→∞} ∫ f(x)dμ(x) in L^{1},

where A(F, f)(x) denotes the average

A(F, f)(x) = \frac{1}{|F |} ∑_{g∈F} f(gx).

The obvious pointwise analogue of this fails, even for G = ℤ. Indeed, let

F_{n} = {n^{2}, n^{2} + 1, …, n^{2} + n}.

Then it is not hard to find ergodic systems (X, B, μ) and functions f ∈ L^{∞}(μ) such that A(F_{n}, f)(x) does not have a limit almost everywhere (in fact, in [4] it is shown that for every nontrivial (X, B, μ) there is such an f ∈ L^{∞}(μ)). Thus one needs to impose some clever condition on the Følner sequence to have pointwise convergence. We shall use the following condition introduced in [10]:

Definition 1.2 (A. Shulman). A sequence of sets F_{n} will be said to be tempered if for some C > 0 and all n,

| ⋃_{k≤n} F_{k}^{−1}F_{n+1}| ≤ C|F_{n+1}|. (1.1)

Shulman proved that along such sequences, the maximal ergodic theorem holds for functions f ∈ L^{2}. An accessible source is [12, Section 5.6]; the relevant theorem is Corollary 6.2 there.

Our main results are the following:

Theorem 1.3 (Pointwise Ergodic Theorem). Let G be an amenable group acting ergodically on a measure space (X, B, μ), and let F_{n} be a tempered Følner sequence. Then for any f ∈ L^{1}(μ),

lim_{n→∞} A(F_{n}, f)(x) = ∫ f(x)dμ(x) a.e.

We remark that the case of f ∈ L^{2} follows from Shulman’s result.

Theorem 1.4 (Generalized Shannon-McMillan-Breiman Theorem). Let P be a finite partition, and assume that G is an amenable group acting ergodically on a measure space (X, B, μ). Let h(P) denote the entropy of this process. Assume that F_{n} is a tempered sequence of Følner sets. Then for almost every x,

\frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} → h(P) as n → ∞.

The entropy of a process is defined in Section 4; an alternative point of view is that the Shannon-McMillan-Breiman theorem asserts that the above limit exists and is constant a.e., and then we can define the entropy to be this limit. We remark that even though we consider here only finite partitions, in [6] there is a simple argument showing that the pointwise ergodic theorem and the Shannon-McMillan-Breiman theorem for finite partitions imply the Shannon-McMillan-Breiman theorem for countable partitions.

A basic ingredient in many proofs of the pointwise theorems in ℤ and more general groups is a version of the Vitali Covering Theorem. This is used to show that from a collection F̄ of right translates of certain sets F_{1}, …, F_{M} that cover most of a big set F ⊂ G it is possible to extract a disjoint subcollection that covers some fixed fraction of the elements of F (the sets F_{1}, …, F_{M} are assumed to be much smaller than F). For this to work, one needs that the sets F_{n} satisfy the Tempelman condition

|F_{n}^{−1}F_{n}| ≤ C|F_{n}|.

The basic new idea in our proof is to treat the subcollections of F̄ as random variables. What we show in Lemma 2.3 is that it is possible to find a distribution on the subcollections of F̄ so that usually the subcollection is almost disjoint and covers most of F, and that these random subcollections cover F more or less evenly.

A considerable number of papers (e.g. [11], [2], [5]) have been written about pointwise theorems along increasing Følner sequences satisfying the Tempelman condition; a similar result can be found also in [1]. Shulman proved the pointwise ergodic theorem for not necessarily increasing Følner sequence satisfying a modified form of Tempelman’s condition, and also the maximal ergodic theorem for f ∈ L^{2} along tempered sequences mentioned earlier. Shulman proves these results using a functional analysis argument; they can be found in [12, Section 5.6], or in [10]. Finally we remark that for f ∈ L^{1+ϵ}, the pointwise ergodic theorem is known for all connected locally compact amenable groups G. The proof in this case makes use of the fact that such groups can be approximated by Lie groups. See [3] or [8, Chapter 5].

Though superficially similar to (1.1), Tempelman’s condition is much stronger. In particular, there seems to be no reason that a general amenable group have Følner sequences satisfying the Tempelman condition. On the other hand the following is easy:

Proposition 1.5. Every Følner sequence F_{n} has a tempered subsequence. In particular, every amenable group has a tempered Følner sequence.

Proof. Let F_{n} be a Følner sequence. We define n_{i} inductively as follows. We start with n_{1} = 1. If n_{1}, …, n_{i} have been determined, we set F̃_{i} = ⋃_{j≤i} F_{n_{j}}, and take n_{i+1} to be large enough so that F_{n_{i+1}} is (F̃_{i}^{−1}, 1/|F̃_{i}|)-invariant. A simple calculation shows that

|⋃_{j≤i} F_{n_{j}}^{−1}F_{n_{i+1}} | < 2|F_{n_{i+1}}|,

so the sequence F_{n_{i}} satisfies (1.1) with C = 2.

Conversely, one can show that for any group G, if F_{n} is a tempered sequence of sets such that ⋃_{n=1}^{∞} F_{n} is not too small (for example, if it is equal to G), then F_{n} is automatically a Følner sequence, and hence G is amenable.

These results are part of the author’s PhD thesis, conducted under the guidance of Prof. B. Weiss, from whom I learned all I know on amenable groups. I wish to thank him for many beneficial discussions and helpful suggestions. I would also like to thank A. Tempelman for pointing out A. Shulman’s result.

2. Random selection of Følner sets

In this section we describe ways to choose in a random way a subcollection of sets from a given collection. This method will be used as a substitute for the Vitali covering argument, which is often used (sometimes implicitly) in proving the pointwise ergodic theorem for ℤ^{d} actions (or, more generally, for actions of discrete groups with polynomial growth).

We begin with a relatively simple covering lemma needed in the proof of the Shannon-McMillan-Breiman theorem for amenable groups:

Lemma 2.1. Let δ > 0 be given, and take ϵ to be small, and M large depending on δ. Let F̄_{1}, …, F̄_{M} ⊂ G be a sequence of finite sets such that

|⋃_{j≤i} F̄_{j}^{−1}F̄_{i+1}| < (1 + ϵ)|F̄_{i+1}|, (2.1)

let F be another finite subset of G (usually much bigger than F̄_{M}), and, for i = 1, …, M, let A_{i} ⊂ F be a set such that F_{i}A_{i} ⊂ F. Then there are sets B(i, a) which are either F̄_{i}a or ∅ (with i = 1, …, M and a ∈ A_{i}) such that

(1 + δ)|⋃_{i,a} B(i, a)| ≥ ∑_{i,a} |B(i, a)| ≥ min_{i} |A_{i}| − δ|F |.

Lemma 2.1 is a traditional covering lemma, where we extract out of a given collection of translates of the F̄_{i}’s a single subcollection that covers much of F and is close to being disjoint. The technique of considering such subcollections as random variables is used, but only in the proof. This is not the case in the following lemma, and in addition in this lemma a weaker form of (2.1) is used.

Lemma 2.2. Let δ > 0, and C > 0 be given. Let N ∈ ℕ, and assume that the sets F̄_{1}, …, F̄_{N} satisfy

|⋃_{j≤i} F̄_{j}^{−1}F̄_{i+1}| < C|F̄_{i+1}|.

Let F be a big finite subset of G, and let A_{j} (for j = 1, …, N) be sets such that F̄_{j}A_{j} ⊂ F. Then it is possible to find set-valued random variables B(j, a) (for j = 1, …, N and a ∈ A_{j}) such that

1. B(j, a) is either F̄_{j}a or ∅.

2. If we set Λ: F → ℕ to be the random function Λ(g) = ∑_{j,a} 1_{B(j,a)}(g), then for all g ∈ F,

E(Λ(g) | Λ(g) > 0) < (1 + δ).

3. For some γ > 0 that depends on δ and C,

E(∑_{g∈G} Λ(g)) = E(∑_{j,a} |B(j, a)|) > γ(δ, C)| ⋃_{j=1}^{N} A_{j}|.

The main disadvantage of Lemma 2.2 is that the random subcollection of sets {B(i, a)} covers only a small percentage of F. By combining Lemma 2.1 and Lemma 2.2 we can overcome this problem. This combined lemma works with twodimensional arrays of Følner sets F̄_{i,j} and possible centers A_{i,j}. It is also convenient to add another feature to this covering lemma: a fixed finite set K used to “fatten” the sets A_{i,j}. We use the notation (i, j) ≻ (i′, j′) to denote that (i, j) is larger in lexicographic order than (i′, j′) — i.e., i > i′ or i = i′ and j > j′.

Lemma 2.3. For any δ, C > 0 and finite K ⊂ G, if M is large enough and ϵ small enough (depending on all these parameters), the following is true. Suppose that we are given an array of finite subsets F̄_{i,j} of G, where i = 1, …, M and j = 1, …, N_{i}, such that

| ⋃_{(i′,k′)⪯(i,k)} F̄_{i′,k′}^{−1} F̄_{i,k+1}| ≤ C|F̄_{i,k+1}|  for k = 1, …, N_{i} − 1,

| ⋃_{(i′,k′)⪯(i,N_{i})} KF̄_{i′,k′}^{−1} F̄_{i+1,k}| ≤ (1 + ϵ)|F̄_{i+1,k}|  for k = 1, …, N_{i+1}.

We also assume we are given A_{i,j} ⊂ F (for i = 1, …, M and j = 1, …, N_{i}) such that F̄_{i,j}A_{i,j} ⊂ F and take α so that for all i

| ⋃_{j=1}^{N_{i}} KA_{i,j}| ≥ α|F |.

Then it is possible to find set-valued random variables B(i, j, a) (for i = 1, …, M, j = 1, …, N_{i} and a ∈ A_{i,j}) such that

1. B(i, j, a) is either F̄_{i,j}a or ∅.

2. If we set Λ: F → ℕ to be the random function Λ(g) = ∑_{i,j,a} 1_{B(i,j,a)}(g), then for all g ∈ F,

E(Λ(g) | Λ(g) > 0) < (1 + δ).

3. Furthermore,

E(∑_{g∈G} Λ(g)) = E(∑_{i,j,a} |B(i, j, a)|) > (α − δ)|F |.

It is easy to describe explicitly these set-valued random variables — or what is equivalent, give a randomized algorithm to generate them. We give (without proof) the randomized algorithm that works for Lemma 2.3; the other lemmas use similar algorithms. An algorithm to generate the B(i, j, a)’s:

1. We start with (i, j) := (N, N_{M}).

2. For every a ∈ A_{i,j}, we perform the following independently of all other b ∈

A_{i,j}:

• If F̄_{i,j}a is disjoint from B(i′, j′, a′) for all (i′, j′) ≻ (i, j) and a′ ∈ A_{i′,j′}, then B(i, j, a) := F̄_{i,j}a with probability ϵ/|F̄_{i,j}| and ∅ with probability 1 − ϵ/|F̄_{i,j}|;

• otherwise B(i, j, a) := ∅.

3. Unless (i, j) = (1, 1), we replace (i, j) by its immediate predecessor in lexicographic order, and return to step 2.

3. The pointwise ergodic theorem

Once one has proved the covering lemmas, proving pointwise theorems is not much more difficult than it is for ℤ. The following proof of the pointwise ergodic theorem is a typical application of the tools we described in the previous section.

Theorem 3.1. Let G be an amenable group acting ergodically on a measure space (X, B, μ), and let F_{n} be a tempered Følner sequence. Then for any f ∈ L^{1}(μ),

lim_{n→∞} A(F_{n}, f)(x) = ∫ f(x)dμ(x) a.e. (3.1)

Proof. It suffices to show that for any f ∈ L^{1}(μ) with f ≥ 0,

\overline{lim}_{n→∞}A(F_{n}, f)(x) ≤ ∫ f(x)dμ(x) a.e.

Indeed, let g ∈ L^{1}(μ), and take R very large. Then

\overline{lim}_{n→∞}A(F_{n}, g)(x) ≤ \overline{lim}_{n→∞}A(F_{n}, max(g, −R))(x)

≤ ∫ max(g(x), −R)dμ(x) ⟶_{R→∞} ∫ g(x)dμ(x).

Applying this also to −g we get (3.1).

Let δ > 0, μ(f) = ∫ f(x)dμ(x). Recall that by assumption, there is a C such that |⋃_{k≤n} F_{k}^{−1}F_{n+1}| ≤ C|F_{n+1}| for all n. Assume that for some c > 1, the set

B = \{x: \overline{lim}_{n→∞}A(F_{n}, f)(x) > cμ(f)\}

has positive measure. Take K to be a finite set such that

μ(KB) > 1 − δ.

Let ϵ be small enough and M big enough so that Lemma 2.3 holds for the given δ, C and K. Take B_{n} to be

B_{n} = {x: A(F_{n}, f)(x) > cμ(f)}.

It is clearly possible to find a_{i} and N_{i} so that

B′ = ⋂_{i=1}^{M}( ⋃_{j=1}^{N_{i}} B_{a_{i}+j−1})

has measure at least μ(B) − δ/|K|, and so that for every i and t ≥ a_{i+1},

| ⋃_{j≤a_{i}+N_{i}−1} KF_{j}^{−1}F_{t}| < (1 + ϵ)|F_{t}|.

We now use the Mean Ergodic Theorem to deduce that if F is an invariant enough set, for a set of x’s of large measure,

A(F, f)(x) < (1 + δ)μ(f),

and for another set of equally large measure,

A(F, 1_{KB′})(x) > 1 − 3δ;

hence there is at least one x_{0} satisfying both.

To apply Lemma 2.3, set F̄_{i,j} = F_{a_{i}+j−1} for i = 1, …, M and j = 1, …, N_{i}, and take

A_{i,j} = {g ∈ F: A(F̄_{i,j}, f)(gx_{0}) > cμ(f) and F̄_{i,j}g ⊂ F }.

Up to boundary effects which are easily seen to be negligible, every g ∈ F such that gx_{0} ∈ KB′ is in ⋃_{j=1}^{N_{i}} KA_{i,j} for every i, hence

| ⋃_{j=1}^{N_{i}} KA_{i,j}| ≥ (1 − 4δ)|F |.

Let

Λ = ∑_{i,j} ∑_{a∈A_{i,j}} 1_{B(i,j,a)}(g): F → ℕ

be a random function as in Lemma 2.3. We estimate

E( ∑_{g∈F} Λ(g)f(gx_{0}))

in two ways. By definition of the sets A_{i,j}, for any a ∈ A_{i,j},

∑_{g∈B(i,j,a)} f(gx_{0}) > c|B(i, j, a)|μ(f),

and so

\begin{aligned}E(∑_{g∈F} Λ(g)f(gx_{0})) & = E(∑_{i,j,a} ∑_{g∈F} 1_{B(i,j,a)}f(g)) ≥ cμ(f) E(∑_{i,j,a} |B(i, j, a)|) \\ & = cμ(f) E(∑_{g∈F} Λ(g)) ≥ c(1 − 5δ)|F |μ(f). \end{aligned}

On the other hand,

\begin{aligned}E(∑_{g∈F} Λ(g)f(gx_{0})) & = ∑_{g∈F} f(gx_{0}) E(Λ(g)) \\ & ≤ (1 + δ)|F |A(F, f)(x_{0}) ≤ (1 + δ)^{2}|F |μ(f). \end{aligned}

Since δ was arbitrary and c > 1 we get a contradiction.

4. The Shannon-McMillan-Breiman theorem

We begin with some notation. If P is a measurable partition of X, and F ⊂ G, we set

P^{F} = ⋁_{g∈F} g^{−1}P.

If x ∈ X, and P is a partition, then P(x) is the unique element of P containing x, and is called the P-name of x. Like in the previous section, we assume throughout that G acts ergodically on (X, B, μ).

A process is simply a space (X, B, μ) on which G acts, together with a partition P of X. The entropy h(P) of the process can be defined in a few equivalent ways. Our approach to entropy is via name-counting, and our proof follows rather closely the proof of the classical Shannon-McMillan-Breiman theorem for ℤ actions given in [9, Chapter 5]. We recall the definition of the entropy h(P) of a process:

Definition 4.1. For any F ⊂ G and ϵ > 0, we set

b(F, ϵ, P) = min{|C|: C ⊂ P^{F} and μ(⋃ C) > 1 − ϵ}.

Then the entropy h(P) is defined as

h(P) = lim_{ϵ→0} \underline{lim}_{n→∞} \frac{log b(F_{n}, ϵ, P)}{|F_{n}|}

where F_{n} is a Følner sequence for G.

For definiteness, we shall take all our logarithms in base 2. It can be shown that the entropy does not depend on the Følner sequence used; For simplicity we assume that F_{n} is the same Følner sequence for which we want to prove the Shannon-McMillan-Breiman theorem. For ergodic G actions, this definition is known to be equivalent to the more usual definition via the entropy function ∑_{i} −p_{i} log p_{i}.

Theorem 4.2. Let P be a finite partition, and assume that G is an amenable group acting ergodically on a measure space (X, B, μ). Assume F_{n} is a tempered sequence of Følner sets. Then for almost every x,

\frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} → h(P) as n → ∞.

We include a rough sketch of the proof. It is divided into two parts: One first shows using Lemma 2.1 and the pointwise ergodic theorem (applied to indicator functions of certain sets) that for any η > 0 there is a sequence of C(n) ⊂ P^{F_{n}} of cardinality

|C(n)| ≤ 2^{(h+η)|F_{n}|}

such that for a.e. x for all n large enough,

P^{F_{n}}(x) ∈ C(n).

From this it is easy to deduce that

(4.1)  \overline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} ≤ h(P) + 2η  for a.e. x.

Indeed, let

Y (n) = \{x ∈ ⋃ C(n): \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} > h(P) + 2η\}.

Since

μ(Y (n)) ≤ |C(n)| × 2^{−(h+2η)|F_{n}|} ≤ 2^{−η|F_{n}|},

we have that ∑_{n=1}^{∞} μ(Y (n)) < ∞, hence we can use the Borel-Cantelli lemma to deduce that a.e. x is not in Y (n) for all n large enough. We already know a.e. x is eventually in ⋃ C(n), hence (4.1) is established.

For the other direction, we show using Lemma 2.3 that if for a set of positive measure of x’s,

\underline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} < h(P) − 2η,

then for any δ > 0, if F is invariant enough, there is a set X′ of measure 1 − δ such that for any x ∈ X′ there is a collection F(x) = {F_{n_{i}}a_{i}}_{i∈I}, satisfying the following conditions:

1. n_{i} ≥ δ^{−1} and F_{n_{i}}a_{i} ⊂ F for all i;

2. μ(P^{F_{n_{i}}} (a_{i}x)) > 2^{(h(P)−2η)|F_{n_{i}} |};

3. (1 + δ)|⋃_{i∈I} F_{n_{i}}a_{i}| ≥ ∑_{i∈I} |F_{n_{i}}| ≥ (1 − δ)|F |.

One now simply counts the number of P^{F} -names needed to cover X′. This turns out to be smaller than 2^{(h(P)−η)|F |} as long as δ is smaller than some function of η. Returning to the definition of entropy, we see that

h(P) = lim_{ϵ→0} \underline{lim}_{n→∞} \frac{log b(F_{n}, ϵ, P)}{|F_{n}|} ≤ h(P) − η,

a contradiction.

References

[1] A. P. Calderon, A general ergodic theorem, Annals of Mathematics 58 (1953), no. 1, 182–191. MR 14:1071a

[2] W. R. Emerson, The pointwise ergodic theorem for amenable groups, American Journal of Mathematics 96 (1974), no. 3, 472–478. MR 50:7403

[3] W. R. Emerson and F. P. Greenleaf, Groups structure and the pointwise ergodic theorem for connected amenable groups, Advances in Math. 14 (1974), 153–172. MR 52:5867

[4] A. del Junco and J. Rosenblatt, Counterexamples in ergodic theory and number theory, Math. Ann. 245 (1979), 185–197. MR 81d:10042

[5] D. Ornstein and B. Weiss, The Shannon-McMillan-Breiman theorem for a class of amenable groups, Israel Journal of Mathematics 44 (1983), no. 1, 53–60. MR 85f:28018

[6] D. Ornstein and B. Weiss, The Shannon-McMillan-Breiman theorem for countable partitions, unpublished, c. 1985, 4 pages.

[7] D. Ornstein and B. Weiss, Entropy and isomorphism theorems for actions of amenable groups, Journal D’analyse Mathématique 48 (1987), 1–142. MR 88j:28014

[8] A. Paterson, Amenability, Mathematical Surveys and Monographs, vol. 29, American Mathematical Society, Providence, Rhode Island, 1988. MR 90e:43001

[9] D. Rudolph, Fundamentals of Measurable Dynamics — Ergodic theory on Lebesgue spaces, Oxford University Press, New York, 1990. MR 92e:28006

[10] A. Shulman, Maximal ergodic theorems on groups, Dep. Lit. NIINTI, No. 2184, 1988.

[11] A. Tempelman, Ergodic theorems for general dynamical systems, Dokl. Akad. Nauk SSSR 176 (1967), no. 4, 790–793; English translation: Soviet Math. Dokl. 8 (1967), no. 5, 1213– 1216. MR 36:2779

[12] A. Tempelman, Ergodic theorems for group actions, informational and thermodynamical aspects, Kluwer Academic Publishers, Dordrecht, 1992. MR 94f:22007

Institute of Mathematics, The Hebrew University, Jerusalem 91904, Israel

E-mail address: elon@math.huji.ac.il