POINTWISE THEOREMS FOR AMENABLE GROUPS

ELON LINDENSTRAUSS

Abstract. In this paper we prove the pointwise ergodic theorem for general locally compact amenable groups along Følner sequences that obey some restrictions. These restrictions are mild enough so that such sequences exist for all amenable groups. We also prove a generalization of the Shannon-McMillan-Breiman theorem to all discrete amenable groups.

1. introduction

The classical ergodic theory deals with measure preserving ℤ actions. Many of the deep results of the classical ergodic theory have been generalized to actions of general amenable groups. A notable exception to this have been pointwise convergence results; indeed, even such basic theorems as the L^{1}-pointwise ergodic theorem or the Shannon-McMillan-Breiman (SMB) theorem were not known for general amenable groups (or even for discrete groups).

In this paper we develop general covering lemmas that are powerful enough to allow fairly straightforward generalizations of classical pointwise convergence results to general amenable groups. In particular, using these tools we prove the pointwise ergodic theorem for general amenable groups and the SMB theorem for discrete amenable groups. These tools can also be used to prove other pointwise results. For example, in [17] D. Ornstein and B. Weiss generalized J. Bourgain, H. Furstenberg, Y. Katznelson and Ornstein’s proof of the return time ergodic theorem [1] from G = ℤ to some amenable groups. Using our methods their proof can be extended to general discrete amenable groups. Most of the results presented in this paper have been announced in [10].

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

|F △ KF | < δ|F |.

Date: January 31, 2001.

The author gratefully acknowledges the support of the Clore Foundation and NSF grant DMS 97-29992.

where we use both | · | and m_{L} to denote the left Haar measure on G (for discrete G, we take this to be the counting measure on G). Such a set F will be called (K, δ)-invariant. A sequence F_{1}, F_{2}, … of compact subsets of G will be called a Følner sequence if for every compact K and δ > 0, for all large enough n we have that F_{n} is (K, δ)- invariant. In this paper all groups are assumed to be locally compact second countable.

Suppose now that G acts bi-measurably from the left by measure preserving transformations on a Lebesgue space (X, B, μ) with μ(X) = 1. We will use for any f: X → ℝ the symbol A(F, f)(x) to denote the average

A(F, f)(x) = \frac{1}{|F |} ∫_{F} f(gx) dm_{L}(g).

A key point in proving pointwise convergence results is working with appropriate Følner sequences. We shall use the following condition introduced by A. Shulman:

Definition 1.1. 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}| ≤ C|F_{n}|.  (1.1)

We shall refer to (1.1) also as the Shulman Condition. We can now state the pointwise ergodic theorem for general amenable groups:

Theorem 1.2 (Pointwise Ergodic Theorem). Let G be an amenable group acting on a measure space (X, B, μ) by measure preserving transformation, and let F_{n} be a tempered Følner sequence. Then for any f ∈ L^{1}(μ), there is a G-invariant f̄ ∈ L^{1}(μ) such that

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

In particular, if the G action is ergodic,

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

The case of f ∈ L^{2}(μ) follows from a result of A. Shulman (see [25], Section 5.6 or [22]).

Note that some restriction on the Følner sequence F_{n} in Theorem 1.2 is essential, 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, A. del Junco and J. Rosenblatt show in [7] that for every nontrivial (X, B, μ) there is such an f ∈ L^{∞}(μ)).

For discrete groups, the entropy of a process (i.e. a measure preserving action of G on X together with a finite or countable partition of X) can be defined in much the same way as done for G = ℤ via the entropy function of a partition (as in [19]) or using name counting (as in [21]). Alternatively, we can use the following theorem to define the entropy as the asymptotic logarithmic rate of decrease h(P) of the size of the atoms of P^{F_{n}} = ⋁_{g∈F_{n}} g^{−1}P. These definitions are all equivalent (see §4 for more details):

Theorem 1.3 (Generalized SMB Theorem). Let P be a finite partition, and assume that G is a discrete amenable group acting ergodically on a measure space (X, B, μ). Assume that F_{n} is a tempered sequence of Følner sets with |F_{n}|/ log n → ∞. Then there is a constant h(P) such that

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

a.e. and in L^{1}(μ).

The new element in this theorem is the existence of the limit a.e. The Shannon-McMillan theorem (i.e. the existence of the limit in L^{1}) was extended to discrete amenable groups by J. Kieffer in 1975 [9].

In [16], Ornstein and Weiss show how entropy theory can be extended to a significantly larger class of unimodular amenable groups, but as this theory is considerably more involved, proving the natural SMB analog in the general case is more complicated (indeed, even formulating what is the natural analog is far from trivial). We remark that even though we consider here only finite partitions, in [15] there is a simple argument showing that the pointwise ergodic theorem and the SMB theorem for finite partitions imply the SMB theorem for countable partitions.

A basic ingredient in many proofs of the pointwise theorems on ℤ 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}|.

A considerable number of papers (e.g. [24], [3], [14]) have been written about pointwise theorems along increasing Følner sequences satisfying the Tempelman condition; a similar result can be found already in [2]. In addition to the result mentioned earlier, Shulman proved the L^{1}-pointwise ergodic theorem for not necessarily increasing Følner sequence satisfying a modified form of Tempelman’s condition ([25], Section 5.6, or in [22]); this condition is more restrictive than the one we use in this paper, and in particular is equivalent to Tempelman’s condition for increasing Følner sequences .

The basic new idea in our proof that enables us to use Shulman’s condition instead of the stronger Tempelman condition, is to treat the subcollections of F̄ as random variables. What we show in Lemma 2.4 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.

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 [4] or [18], Chapter 5.

Though superficially similar to Shulman’s condition, Tempelman’s condition is much stronger (note, however that Shulman’s condition is a condition on the whole sequence, while Tempelman’s condition is a condition on the individual sets). In §5 we consider the “lamplighter group” ℤ ⋉ ∑_{i∈ℤ} ℤ/2. Starting with the work of Kaimanovich and Vershik [8], this group has been much studied, and have proved to be a very useful example of a finitely generated amenable group of exponential growth. Using A. Ruzsa’s extension [20] of Freiman’s theorem [5] (both can be found also in [12]), we show that this group has no Følner sequence satisfying Tempelman’s condition. We also show that in this group for any tempered Følner sequence F_{n}, |F_{n}| grows super exponentially. It seems plausible that these two statements hold in any finitely generated amenable group of exponential growth.

As we have seen, there are groups that have no Følner sequences satisfying Tempelman’s condition. On the other hand the following is easy:

Proposition 1.4. 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, then F_{n} is almost a Følner sequence: there is a Følner sequence F̂_{n} such that F_{n} ⊂ F̂_{n} and |F̂_{n}| ≤ C|F_{n}|. In particular G is amenable. The exact condition we need on ⋃_{n=1}^{∞} F_{n} is that it contains a left translate of all finite K ⊂ G; thus by (1.1) for all n large enough

|KF_{n}| < C|F_{n}|.

The existence of the Følner sequence F̂_{n} is now a consequence of the simple observation that if |K^{n}F | < C|F | then for some 0 ≤ i ≤ n we have that F̂ = K^{i}F satisfies |KF̂| ≤ C^{1/n}|F̂|, and so if (as we may sue without loss of generality) e ∈ K,

|F △ KF | < (C^{1/n} − 1)|F |.

In view of our results on the lamplighter group the following question (similar to one suggested to the author by D. Rudolph) seems natural:

Question 1.5. Does every amenable group G have a sequence of sets F_{n} ⊂ G for which the L^{1} pointwise ergodic theorem (Theorem 1.2) holds and such that |F_{n}| grows at most exponentially?

Between the time this paper has originally been written to its publication A. Shulman and A. Tempelman [23] proved a pointwise ergodic theorem for what they call isometric representations, which can be used to give an alternative proof of Theorem 1.2 for functions in L^{p}, with p strictly greater than 1. We also mention unpublished work of D. Ornstein and B. Weiss who have found another proof of Theorem 1.2 that is similar to ours but does not use random (sub)covers.

2. Random selection of Følner sets

In this section we prove the covering lemmas we need for establishing pointwise convergence results. The basic covering result is Lemma 2.1, which is also the result we use in the proof of the pointwise ergodic theorem. We then prove another covering lemma, Lemma 2.4, by applying Lemma 2.1 iteratively. This version, or more precisely its Corollary 2.7, is used in the proof of the SMB theorem.

The situation these lemmas deal with is the following: we are given an arbitrary collection F̄ of sets that are right translates of elements of a (finite) tempered sequence {F_{i}}_{i=1}^{N}, all contained in some compact F ⊂ G which is to be thought as a much bigger set then the F_{i}. From this collection F̄ we wish to extract (in a random way) a well behaved finite subcollection. The collection F̄ is specified by giving for any 1 ≤ i ≤ N the set A_{i} of a ∈ G for which F_{i}a ∈ F̄. Formally, a random subcollection can be specified by giving a space Ω, a probability measure on Ω and a map that assigns to a point ϵ⃗ ∈ Ω a subcollection F(ϵ⃗) of F̄.

What we will establish in the covering lemmas is that for a carefully chosen probability measure on Ω, on average the corresponding subcollections F(ϵ⃗) satisfy certain conditions that imply in particular that for a typical ϵ⃗ the subcollection F(ϵ⃗) are fairly disjoint (condition 2 of these lemmas), and that if the original collection F̄ is rich enough the sets in F(ϵ⃗) cover a significant portion of F (condition 3). This interpretation is carried out in detail in Corollary 2.7. Another useful property of the distribution of these subcollections is that they cover F more or less evenly (this is also a consequence of condition 3).

Before we state the covering lemmas, we give some notational remarks. We will use probabilistic notations for the measure space Ω of possible ϵ⃗, and in particular denote the probability measure on Ω by ℙ. If Φ is a σ-algebra of measurable subsets of Ω, and X is a random variable, we can consider the conditional expectation function E(X |Φ). If P is an event, i.e. a measurable subset of Ω, then E(X | P) denotes the constant

E(X | {P, P^{∁}}) |_{P} .

These notations can be mixed:

E(X | Φ; P) = E(X | {P, P^{∁}} ∨ Φ) |_{P} .

Finally, if F is a collection of subsets of G, we let

∥F∥ = ∑_{B∈F} |B|

and

∪F = ⋃_{A∈F} A.

Lemma 2.1. Let G be a locally compact second countable group, and let δ > 0, and C > 0 be given. Let N ∈ ℕ, and assume that F_{1}, …, F_{N} are compact subsets of G satisfying

|⋃_{j≤i} F_{j}^{−1}F_{i+1}| < C|F_{i+1}|  1 ≤ i < N.  (2.1)

Let F be a compact subset of G, let A_{j} (for j = 1, …, N) be any sets such that F_{j}A_{j} ⊂ F, i.e. so that

F̄ = {F_{j}a : 1 ≤ j ≤ N a ∈ A_{j}}

is a collection of subsets of F.

Then it is possible to find a probability measure ℙ on a space Ω and a map ϵ⃗ ↦ F(ϵ⃗) from Ω to the set of subcollections of F̄ such that if Λ(g) = Λϵ⃗(g) is the counting function of F(ϵ⃗), i.e. the map F → ℝ depending on the implicit parameter ϵ⃗

Λϵ⃗(g) = ∑_{B∈F(ϵ⃗)} 1_{B}(g),

then 1. F(ϵ⃗) is finite a.s. and Λϵ⃗(g) is a measurable function on Ω × F.

2. For all g ∈ F,

E(Λ(g) | Λ(g) ≥ 1) ≤ (1 + δ).

3. Furthermore,

E(∥F(ϵ⃗)∥) = E(∫_{F} Λ(g)dm_{L}(g)) ≥ γ(δ, C)|⋃_{j=1}^{N} A_{j}|

with γ(δ, C) = δ/(1 + Cδ).

To keep technicalities to a minimum, we first consider the case where G is a discrete group, and so in particular is unimodular. To prove this lemma, we shall use the following simple estimate.

Lemma 2.2. Let S = ∑_{i=1}^{n} X_{i}, where the X_{i}’s are i.i.d random variables which are 1 with probability p and 0 with probability 1 − p. Then

E(S | S ≥ 1) ≤ 1 + (n − 1)p  (2.2)

Proof. The inequality (2.2) is equivalent to

\frac{np}{1 − (1 − p)^{n}} ≤ 1 + (n − 1)p.

Multiplying both sides by 1 − (1 − p)^{n} and rearranging we get

1 − p ≥ (1 − p)^{n}(1 + (n − 1)p)

which now follows from

(1 − p)^{−n+1} = (1 + p + p^{2} …)^{n−1} ≥ 1 + (n − 1)p.

Proof of Lemma 2.1 for discrete groups.

We take Ω to be

Ω = {{ϵ(j, a)}_{1≤j≤N, a∈G} : ∀j, a ϵ(j, a) ∈ {0, 1}}

and define a probability distribution on this space so that each ϵ_{j,a} is an independent {0, 1}-valued random variable which is one with probability p_{j} := δ/|F_{j}|.

We now give an algorithm which describes the map ϵ⃗ ↦ F(ϵ⃗). Algorithm A: how to generate F(ϵ⃗) given ϵ⃗ = {ϵ(j, a)}

1. We start with j = N, and {A_{i|N+1}}_{i=1}^{N} = {A_{i}}_{i=1}^{N}.

2. Set

Σ_{j} = {a : a ∈ A_{j} and ϵ(j, a) = 1}

and

F_{j}(ϵ⃗) = {F_{j}a : a ∈ Σ_{j}}

3. For all i < j, set A_{i|j} ⊂ A_{i|j+1} to be those a ∈ A_{i|j+1} such that F_{i}a is disjoint from F_{j} · Σ_{j}.

4. Unless j = 1, replace j by j − 1, and return to step 2.

5. F(ϵ⃗) = ⋃_{j=1}^{N} F_{j}(ϵ⃗).

Note that in addition to F(ϵ⃗) (and the closely related Σ_{j} = Σ_{j}(ϵ⃗)), this algorithm also yields sets A_{i|j} = A_{i|j}(ϵ⃗) 1 ≤ i < j ≤ N + 1, which are, of course, determined by ϵ⃗. In fact, for every j and i < j, A_{i|j} (which is to be interpreted as the set of all a ∈ A_{i} for which

F_{i}a ∈ F(ϵ⃗)

is still possible given steps N, N − 1, …, j) depends only on Φ_{j}, the smallest (σ-)algebra of subsets of Ω generated by the random variables ϵ(j′, a′) for j′ ≥ j and all a′ ∈ G. An important property of this algorithm is that once F_{N}(ϵ⃗) has been determined (i.e. given the value of Φ_{N}(ϵ⃗)), the random collection ⋃_{j=1}^{N−1} F_{j}(ϵ⃗) has exactly the same distribution as the distribution one obtains by applying the original algorithm on the tempered sequence {F_{j}}_{j=1}^{N−1} and the sets {A_{j|N}}_{j=1}^{N−1}.

We will need the auxiliary functions Λ_{j} (depending, as usual, on the implicit parameter ϵ⃗ ∈ Ω) which are simply the counting functions of F_{j}(ϵ⃗),

Λ_{j}(g) = ∑_{B∈F_{j}(ϵ⃗)} 1_{B}(g).

We remark that for every g, Λ_{j}(g) is Φ_{j} measurable, and that for j ≠ j′, the events Λ_{j}(g) > 0 and Λ_{j′}(g) > 0 are mutually exclusive.

We first show that for every g ∈ F

E(Λ(g) | Λ(g) ≥ 1) < (1 + δ).  (2.3)

Since the supports of the functions Λ_{j} are pairwise disjoint it is enough to deal with just one function Λ_{j}. Given Φ_{j+1}(ϵ⃗) (which determines A_{j|j+1}),

Λ_{j}(g) = ∑_{a∈A_{j|j+1}∩F_{j}^{−1}g} ϵ(j, a)

Thus given Φ_{j+1}(ϵ⃗), Λ_{j}(g) is the sum of

|A_{j|j+1} ∩ F_{j}^{−1}g| ≤ |F_{j}|

0,1 valued random variables (with the probability of 1 being p_{j}), and we can use Lemma 2.2 to see that

E(Λ_{j}(g)|Λ_{j}(g) > 1) = E(E(Λ_{j}(g) | Λ_{j}(g) > 1; Φ_{j+1}) | Λ_{j}(g) > 1)
≤ 1 + p_{j}|F_{j}| = 1 + δ.

We now turn to prove the second condition on F(ϵ⃗) in the statement of the lemma, namely

E(∑_{g∈F} Λ(g)) ≥ γ(δ, C)|⋃_{i=1}^{N} A_{i}|,  (2.4)

with the explicit constant

γ(δ, C) = \frac{δ}{1 + Cδ} .

We shall prove (2.4) by induction on N. The case N = 1 is easily established; in fact we shall need the (superficially) more general inequality (in this case an equality)

E(∑_{g∈F} Λ_{N}(g)) = ∑_{a∈A_{N}} |F_{N}a| E(ϵ(N, a)) = δ|A_{N}|.  (2.5)

Assume now that N > 1. By the recursive property of Algorithm A, and the induction hypothesis 2.4 applied to the tempered sequence {F_{j}}_{j=1}^{N−1} and the sets {A_{j|N}}_{j=1}^{N−1} (which are determined by Φ_{N}(ϵ⃗))

\begin{aligned}E(∥F(ϵ⃗)∥ | Φ_{N}) & = ∥F_{N}(ϵ⃗)∥ + E(∥ ⋃_{j=1}^{N−1} F_{j}(·)∥ | Φ_{N})(ϵ⃗) \\ & ≥ ∥F_{N}(ϵ⃗)∥ + γ(δ, C)| ⋃_{j=1}^{N−1} A_{j|N}(ϵ⃗)|. \end{aligned}  (2.6)

Recall that

A_{j|N} = A_{j} \ F_{j}^{−1}F_{N}Σ_{N}

(this is merely a reformulation of step 4 of Algorithm A), so

⋃_{j=1}^{N−1} A_{j|N} ⊃ ⋃_{j=1}^{N−1} A_{j} \ ( ⋃_{j=1}^{N−1} F_{j}^{−1}F_{N}) Σ_{N}  (2.7)

However, by (2.1) | ⋃_{j=1}^{N−1} F_{j}^{−1}F_{N}| ≤ C|F_{n}| and so combining equation (2.6) with (2.7) we get that

E(∑_{g∈F} Λ(g) | Φ_{N}) ≥ |F_{N}| × |Σ_{N}(ϵ⃗)| + γ(δ, C) (| ⋃_{j=1}^{N−1} A_{j}| − C|F_{N}| × |Σ_{N}(ϵ⃗)|) .

In view of (2.5), as long as Cγ(δ, C) < 1(which is always true for our choice of γ(δ, C)), this implies that

E(∑_{g∈F} Λ(g)) ≥ δ|A_{N}| + γ(δ, C) (| ⋃_{j=1}^{N−1} A_{j}| − Cδ|A_{N}|) .

The constant γ(δ, C) has been chosen so that when substituting it in the above equation one gets simply

E(∑_{g∈F} Λ(g)) ≥ γ(δ, C) (| ⋃_{j=1}^{N−1} A_{j}| + |A_{N}|)

which implies the desired inequality.

We now consider the general case of G second countable and locally compact. We let m_{L} denote the left Haar measure on G and m_{R} the right Haar measure defined by m_{R}(A) = m_{L}(A^{−1}). Recall that |A| denotes m_{L}(A) = m_{R}(A^{−1}). We denote by Δ(h) the modular function of G, defined by

∫ f(gh)dm_{L}(g) = Δ(h)^{−1} ∫ f(g)dm_{L}(g).  (2.8)

m_{L}, m_{R}, and Δ are related by the identity

Δ(g)^{−1}dm_{L}(g) = dm_{R}(g)

In the general case we shall use Poisson processes in order to choose those a’s for which F_{j}a ∈ F_{j}(ϵ⃗). We recall that a Poisson process on a σ-finite Lebesgue measure space (X, B, μ) (such as any compact F ⊂ G with either left or right Haar measure) is a probability measure on the space of random subsets Σ of X such that:

1. for any disjoint B_{j} ∈ B, the variables |Σ ∩ B_{j}| are independent;

2. the expected value of |Σ ∩ B| equals μ(B) for any B ∈ B.

Thus in this case we take Ω to be

Ω = {ϵ⃗ = (Υ_{j})_{j=1}^{N} : ∀j Υ_{j} is a locally finite subset of G}

(we say a set is locally finite if its intersection with any compact set is finite). Each Υ_{j} is taken independently according to a Poisson process on G (thus (Ω, ℙ) is simply a product of N Poisson processes); however there is some subtlety to choosing with respect to what measure. It turns out that the correct measure to take for defining the Poisson process Υ_{j} on G is the rescaled right Haar measure α_{j}m_{R} with α_{j} = δ/|F_{j}|. Algorithm B: a modification of Algorithm A for non-discrete groups

1. We start with j = N and {A_{i|N+1}}_{i=1}^{N} = {A_{i}}_{i=1}^{N}.

2. Set Σ_{j} = Υ_{j} ∩ A_{j|j+1} and

F_{j}(ϵ⃗) = {F_{j}a : a ∈ Σ_{j}}

3. Set for all i < j, A_{i|j} ⊂ A_{i|j+1} to be those a ∈ A_{i|j+1} such that F_{i}a is disjoint from F_{j} · Σ_{j}.

4. Unless j = 1, replace j by j − 1, and return to step 2.

5. F(ϵ⃗) = ⋃_{j=1}^{N} F_{j}(ϵ⃗).

The cautious reader may wish to verify that indeed

Λ(g) = Λϵ⃗(g) = ∑_{i=1}^{N} ∑_{B∈F(ϵ⃗)} 1_{B}(g)

as well as

Λ_{j}(g) = Λϵ⃗ ; j(g) = ∑_{i=1}^{N} ∑_{B∈F_{j}(ϵ⃗)} 1_{B}(g)

are measurable as a function on Ω×G. Since this is a fairly straightforward consequence of the way F(ϵ⃗) is defined using the Poisson process we omit the details.

To show that

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

it is again sufficient to show that for any j = 1, …, N, and ϵ⃗ ∈ Ω

E(Λ_{j}(g) | Λ_{j}(g) > 0; Φ_{j})(ϵ⃗) < 1 + ϵ.  (2.10)

This, in itself, is again a simple probabilistic lemma: Λ_{j}(g) is the number of elements of Υ_{j} in A_{j|j+1} ∩ F_{j}^{−1}g (which is also the number of elements of Σ_{j} in that set). The α_{j}m_{R} measure of this set is at most δ. Thus (2.10) (and hence equation (2.9)) follows from the following Lemma:

Lemma 2.3. Let Υ be chosen according to a Poisson process corresponding to the measure αm_{R} from a set A ⊂ G. Then

E(|Υ| | |Υ| > 0) ≤ 1 + αm_{R}(A)

Proof. If G is discrete this is exactly Lemma 2.2. Otherwise, the measure m_{R} has no atoms, and so by the elementary properties of a Poisson process, |Υ| has a Poisson distribution

ℙ(|Υ| = n) = exp(−αm_{R}(A))(αm_{R}(A))^{n}/n!,

and

E(|Υ| | Υ ≠ ∅) = \frac{∑_{n>1} nℙ(|Υ| = n)}{∑_{n>1} ℙ(|Υ| = n)}

= \frac{αm_{R}(A)}{1 − exp(−αm_{R}(A))}

≤ 1 + αm_{R}(A).

where the last inequality follows from the classical inequality e^{−x} ≤ (1 + x)^{−1}.

It remains to show that also in the general case

E(∫_{g} Λ(g)dm_{L}(g)) ≥ γ(δ, C)|⋃_{i=1}^{N} A_{i}|  (2.11)

Most of the argument works without any modifications; indeed, the only place where there is any difference is the treatment of the case N = 1, or more precisely, in the proof of (2.5). We first note that |F_{N}a| = Δ(a)|F_{N}|. We now calculate

E(∫_{F} Λ_{N}(g)dm_{L}(g)) = E( ∑_{a∈Σ_{N}} |F_{N}a|) = E( ∑_{a∈Σ_{N}} Δ(a))|F_{N}|. (2.12)

The Poisson process on G according to the measure α_{N}m_{R} satisfies, for every function f ∈ L^{∞}(G), that if Υ is (as above) a random finite set

E(∑_{a∈Υ} f(a)) = α_{N} ∫ f(x)dm_{R}(g).

Indeed, this follows immediately from the second property of a Poisson process listed earlier. In particular, applying this to f = 1_{A_{N}} Δ(·), and using (2.12), we see that

E(∫_{F} Λ(g)dm_{L}(g)) = α_{N}|F_{N}| ∫_{A_{N}} Δ(g)dm_{R}(g).

But Δ(g)dm_{R}(g) = dm_{L}(g), and α_{N}|F_{N}| = δ, so

E(∫_{F} Λ_{N}(g)dm_{L}(g)) = δ|A_{N}|.

This completes the proof of Lemma 2.1.

Lemma 2.1 can be applied iteratively to obtain a random subcollection of sets that cover an arbitrarily large percentage of F. The resulting covering lemma works with two-dimensional 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 D used to “fatten” the sets A_{i,j}.

Lemma 2.4. For any δ, C > 0 and finite D ⊂ G, if M is large enough (depending only on 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

1. For every i, F̄_{i,∗} = {F_{i,j}}_{j=1}^{N_{i}} satisfies the requirements of Lemma 2.1, i.e.

| ⋃_{k′<k} F_{i,k′}^{−1}F_{i,k}| ≤ C|F_{i,k}| for k = 2 …, N_{i}.

Denote F_{i,∗} = ∪F̄_{i,∗}.

2. In addition, the finite set sequences F̄_{i,∗} satisfy that for every 1 < i ≤ M and every 1 ≤ k ≤ N_{i}

|⋃_{i′<i} DF_{i′,∗}^{−1}F_{i,k}| ≤ (1 + δ)|F_{i,k}|.

We also assume we are given an array of sets A_{i,j} (for i = 1 … M and j = 1 … N_{i}) such that F_{i,j}A_{i,j} ⊂ F so that

F̄ = {F_{i,j}a: 1 ≤ i ≤ M, 1 ≤ j ≤ N_{i} and a ∈ A_{i,j}}

is a collection of subsets of F. Then it is possible to find a probability space (Ω, ℙ) and a map ϵ⃗ ↦ F(ϵ⃗) from Ω to finite subcollections of F̄ satisfying:

1. the counting function Λ: F → ℕ of F(ϵ⃗),

Λ(g) = ∑_{B∈F(ϵ⃗)} 1_{B}(g)

is measurable in Ω × F.

2. For all g ∈ F,

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

3. Furthermore

E(∥F(ϵ⃗)∥) = E(∫_{F} Λ(g)dm_{L}(g)) ≥ (1 − 2δ) min_{1≤i≤M} |DA_{i,∗}| (2.13)

Proof. For every 1 ≤ i ≤ M, starting with i = M and proceeding in descending order, we apply Lemma 2.1 on the tempered set sequence F̄_{i,∗} and sets

Ā_{i,∗|i+1} = {A_{i,j|i+1}}_{j=1}^{N_{i}}

to be determined later (the A_{i,j|i+1} themselves will be random variables depending on the finite subcollections selected for i′ > i). Since the probability space used in Lemma 2.1 depends only on the tempered set sequence (in our case F̄_{i,∗}) this already determines the measure space Ω we will use as a product of M probability spaces

Ω = Ω_{1} × ⋯ × Ω_{M}

with each Ω_{i} the probability space we get when we apply Lemma 2.1 to F̄_{i,∗}. We now set to describe the map

ϵ⃗ = (ϵ⃗_{1}, …, ϵ⃗_{M}) ↦ F(ϵ⃗)

with each ϵ⃗_{i} ∈ Ω_{i}.

For i = M take

A_{M,j|M+1} ≡ A_{M,j}

and denote the resulting random subcollection of

{F_{M,j}a : 1 ≤ j ≤ N_{M} and a ∈ A_{M,j}}

(that will depends only on ϵ⃗_{M}) by F_{M,∗}(ϵ⃗) = ⋃_{j=1}^{N_{i}} F_{M,j}(ϵ⃗) (where each F_{M,j} is a collection of right translates of F_{M,j}).

For i < M take

A_{i,j|i+1} = Aϵ⃗ ; i,j|i+1 = A_{i,j}\ ⋃_{i′>i} F_{i,j}^{−1} (∪F_{i′,∗}(ϵ⃗))

and denote the resulting random subcollection of

{F_{i,j}a : 1 ≤ j ≤ N_{i} and a ∈ A_{i,j|i+1}}

by

F_{i,∗}(ϵ⃗) = ⋃_{j=1}^{N_{i}} F_{i,j}(ϵ⃗_{i}).

Note that as before to avoid excessive indexing the dependence of the above symbols on ϵ⃗ is sometimes implicit. Set

\begin{matrix}Λ_{i,j}(g) ≡ Λϵ⃗_{i} ; i,j(g) = ∑_{B∈F_{i,j}(ϵ⃗_{i})} 1_{B}(g) \\ Λ_{i,∗}(g) = ∑_{j=1}^{N_{i}} Λ_{i,j}(g) \end{matrix}

and take Φ_{i,∗} to be the smallest σ-algebra determining ϵ′_{i} for all i′ ≥ i. Note that Φ_{i,∗}(ϵ⃗) determines F_{i′,∗} for all i′ ≥ i.

Again we leave the verification of the measurability condition to the reader. To verify the second conclusion of this lemma its suffice to note that by construction a set B ∈ F_{i,∗} is disjoint from every sets in F_{i′,∗} for i′ ≥ i, hence the support of the Λ_{i,∗} are disjoint. Thus

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

is a consequence of the fact that Lemma 2.1 gives us for every i that

E(Λ_{i,∗}(g) | Λ_{i,∗}(g) > 0) < (1 + δ).

It remains to prove that for M large enough (2.13) holds. The proof is by induction on M; for this we need a more quantified version of (2.13) namely

E(∑_{i=m}^{M} ∥F_{i,∗}(ϵ⃗_{i})∥) ≥ min(1 − 2δ, (M − m + 1)η) min_{m≤i≤M} |DA_{i,∗}| (2.14)

with

η = \frac{δ^{2}}{(1 + Cδ)|D|} = \frac{γ(δ, C)δ}{|D|}  (2.15)

The case m = M is essentially Lemma 2.1 (with a substantially weaker constant), since

|A_{M,∗}| ≥ \frac{|DA_{M,∗}|}{|D|}

and so by item 3 in the conclusion of Lemma 2.1

E(∥F_{M,∗}(ϵ⃗)∥) ≥ γ(δ, C)|A_{M,∗}| ≥ η|DA_{M,∗}|.

Note that the last inequality is far from being tight.

For the general case, we can clearly assume that

E( ∑_{m′>m} ∥F_{m′,∗}(ϵ⃗)∥) < (1 − 2δ) min_{m≤i≤M} |DA_{i,∗}|  (2.16)

as otherwise there is nothing to prove. By Lemma 2.1

E(∥F_{m,∗}(ϵ⃗)∥ | Φ_{m+1,∗}) ≥ γ(δ, C)|A_{m,∗|m+1}|.  (2.17)

Furthermore, for every 1 ≤ j ≤ N_{i}

A_{m,j|m+1} = A_{m,j}\ ⋃_{m′>m} ⋃_{B∈F_{m′,∗}} F_{m,j}^{−1}B

hence

DA_{m,∗|m+1} ⊃ DA_{m,j}\ ⋃_{m′>m} ⋃_{B∈F_{m′,∗}} DF_{m,∗}^{−1}B.

Since every B ∈ ⋃_{m′>m} F_{m′,∗} is a right translate of F_{m′,j′} for some j′ and

|DF_{m,∗}^{−1}F_{m′,j′}| ≤ (1 + δ)|F_{m′,j′}|

by assumption 2 of the lemma, we have that for any such B

|DF_{m,∗}^{−1}B| ≤ (1 + δ)|B|.

Thus we see that

|A_{m,∗|m+1}| ≥ \frac{1}{|D|} (|DA_{m,∗}| − (1 + δ) ∑_{m′>m} ||F_{m′,∗}||) .  (2.18)

Substituting (2.18) in (2.17), and averaging over ϵ⃗ we get that

E(∥F_{m,∗}(ϵ⃗)∥) ≥ \frac{γ(δ, C)}{|D|}|DA_{m,∗}|

− \frac{γ(δ, C)(1 + δ)}{|D|} E( ∑_{m′>m} ||F_{m′,∗}||)

≥ \frac{γ(δ, C)}{|D|} min_{m≤i≤M} |DA_{i,∗}|(1 − (1 + δ)(1 − 2δ))

≥ η min_{m≤i≤M} |DA_{i,∗}|

(2.19) where the second inequality follows from (2.16). Thus

E ( ∑_{m′ ≥ m} ∥F_{m′,∗}(ε⃗)∥) ≥ E ( ∑_{m′ > m} ∥F_{m′,∗}(ε⃗)∥) + η min_{m ≤ i ≤ M} |DA_{i,∗}|

and the induction is complete.

Definition 2.5. A collection F of subsets of G is δ-disjoint if for every A ∈ F there is an A′ ⊂ A such that |A′| ≥ (1 − δ)|A| and such that A′ ∩ B′ = ∅ for every A ≠ B ∈ F.

We will need the following simple and very general lemma to produce big δ-disjoint collections.

Lemma 2.6. Let F̄ be a collection of subsets of F ⊂ G such that

|∪F̄| ≥ α |F | and  (2.20)
∥F̄∥ − |∪F̄| < δ|F |  (2.21)

Then for any δ′ > 0 there is a subcollection F ⊂ F̄ which is δ′-disjoint and

|∪F| ≥ (α − \frac{2δ}{δ′} ) |F |

Proof. Let Λ̄ denote the function

Λ̄(g) = ∑_{B∈F̄} 1_{B}(g);

note that

∥F̄∥ − |F̄| = ∫_{F} max(0, Λ̄(g) − 1)dm_{L}(g)  (2.22)

We claim that the following collection has the desired properties:

F = {A ∈ F̄: |A ∩ ⋃_{B∈F̄\{A}} B| ≤ δ′|A|} .

By construction, F is δ′ disjoint. Furthermore, a set A is in F̄ \ F iff

∫_{A} 1_{Λ̄(g)>1}dm_{L}(g) > δ′|A|.

If {A_{1}, …, A_{r}} are precisely all the elements of F̄ that contain g, then

∑_{i=1}^{r} 1_{Λ̄(g)>1} = \begin{cases}Λ̄(g) & if Λ̄(g) > 1 \\ 0 & otherwise, \end{cases}

Thus

∑_{A∈F̄\F} |A| < \frac{1}{δ′} ∑_{A∈F̄} ∫_{A} 1_{Λ̄(g)>1}dm_{L}(g)

= \frac{1}{δ′} ∫_{F} 1_{Λ̄(g)>1}Λ̄(g)dm_{L}(g)

≤ \frac{1}{δ′} ∫_{F} 2 max(Λ̄(g) − 1, 0).

By (2.22) and (2.21),

∫_{F} 2 max(Λ̄(g) − 1, 0)dm_{L}(g) ≤ 2δ|F |,

hence

∑_{A∈F̄\F} |A| < \frac{2δ}{δ′} |F |.

But, using (2.20) this implies that

| ∪ F| ≥ | ∪ F̄| − ∑_{A∈F̄\F} |A| ≥ (α − \frac{2δ}{δ′})|F |,

and F has the desired properties.

Corollary 2.7. Let M, D, δ ∈ (0, 1/100), {F_{i,j}}, and {A_{i,j}} be as in the statements of Lemma 2.4 (and satisfying all the assumptions of that lemma). Let

α = \frac{min_{1≤i≤M} |DA_{i,∗}|}{|F |}.

Then the collection

F̄ = {F_{i,j}a: a ∈ A_{i,j}, 1 ≤ i ≤ M, 1 ≤ j ≤ N_{i}}

has a subcollection F that is 10δ^{1/4} disjoint such that

| ∪ F| ≥ (α − δ^{1/4})|F |.

Proof. Let F(ϵ⃗) be a randomly chosen subcollection of F̄. Then

E(∥F(ϵ⃗)∥ − | ∪ F(ϵ⃗)∥) = E(∫_{F} max(Λ(g) − 1, 0)dm_{L}(g))

\begin{matrix}= ∫_{F} ℙ(Λ(g) > 0) E(Λ(g) − 1 | Λ(g) > 0) \\ ≤ δ E(| ∪ F(ϵ⃗)|) ≤ δ|F |, \end{matrix} (2.23)

and in particular, we can use part 3 of Lemma 2.4 to deduce that

E(| ∪ F(ϵ⃗)|) ≥ (α − 3δ)|F |.

The expression for which we take expectation in (2.23) is non-negative, and so from Chebychev’s inequality we see that

ℙ (∥F(ϵ⃗)∥ − | ∪ F(ϵ⃗)∥ ≥ \sqrt{δ}|F |) ≤ \sqrt{δ}.

Similarly, | ∪ F(ϵ⃗)| is at most |F |, so if we set

p(α′) = ℙ(| ∪ F(ϵ⃗)| ≥ α′|F |)

we see that

α′ (1 − p(α′)) |F | + p(α′)|F | ≥ E(| ∪ F(ϵ⃗)|) ≥ (α − 3δ)|F |

hence

p(α′) ≥ \frac{α − α′ − 3δ}{1 − α′}

We take

α′ = (α − 3\sqrt{δ}),

and a simple calculation shows that for this α′

p(α′) ≥ 2\sqrt{δ}

hence there is some ϵ⃗ for which

∥F(ϵ⃗)∥ < |∪F(ϵ⃗)| + \sqrt{δ}|F |  (2.24)

(an event with probability ≥ 1 − \sqrt{δ}) and

|∪F(ϵ⃗)| > (α − 3\sqrt{δ})|F |  (2.25)

(an event with probability ≥ 2\sqrt{δ}). We can now apply Lemma 2.6 on F̄ = F(ϵ⃗) with δ′ = 10δ^{1/4} to get a 10δ^{1/4}-disjoint subcollection F with

| ∪ F| ≥ (α − δ^{1/4})|F |.

3. The Maximal Inequality and the Pointwise Ergodic Theorem

We first prove a maximal inequality for the averages A(F_{n}, f)(x), from which the pointwise ergodic theorem easily follows. For more on maximal inequalities see, e.g., [19, Section 3.2] [25, Chapter 5].

Definition 3.1. Let F_{n} be a sequence of measurable subsets of a group G with finite measure. We define the maximal function of f ∈ L^{1}(μ) as

M[f](x) := sup_{n} A(F_{n}, f)(x).

Theorem 3.2 (Weak 1-1 maximal inequality). Let G be an amenable group acting on a measure space (X, B, μ) by measure preserving transformations, and let F_{n} be a tempered sequence of compact sets. Then there is a c > 0, depending only on the sequence F_{n} but not on X, such that for any f ∈ L^{1}(μ),

μ{x: M[f](x) > λ} ≤ cλ^{−1}∥f∥_{1}  (3.1)

Proof. Let C be the constant involved in the definition of tempered sequences. We claim that

c = 2(1 + C) = \frac{2}{γ(1, C)}

will work. Set

M_{n}[f](x) := max_{1≤j≤n} A(F_{j}, f)(x),

and choose n_{0} to be large enough so that

D := {x: M_{n_{0}}[f](x) > λ}

has measure

μ(D) ≥ μ{x: M[f](x) > λ} − ϵ.

Take any (big) compact subset F′ ⊂ G , and set F = (⋃_{i≤n_{0}} F_{i})F′. Since G is amenable and ⋃_{i≤n_{0}} F_{i} compact, we can choose F′ so that |F | ≤ (1 + ϵ)|F′|

We first show that for every x ∈ X

∫_{F′} 1_{D}(gx)dm_{L}(g) ≤ cλ^{−1} ∫_{F} |f(gx)|dm_{L}(g).  (3.2)

Indeed, fix x ∈ X. Set for j = 1, …, n_{0}

A_{j} = {g ∈ F′: A(F_{j}, f)(gx) > λ}.

We now apply Lemma 2.1 for δ = 1. Let F(ϵ⃗) be a random collection of subsets of F with corresponding counting function Λ: F → ℕ as in Lemma 2.1. We estimate E(∫_{F} Λ(g)f(gx)dm_{L}(g)) in two ways. On the one hand, we use Fubini’s theorem and the fact that for every g, E(Λ(g)) ≤ 2 (this follows from part 2 in Lemma 2.1) to see that

\begin{aligned}E(∫_{F} Λ(g)f(gx)dm_{L}(g)) & = ∫_{F} E(Λ(g))f(gx)dm_{L}(g) \\ & ≤ 2 ∫_{F} |f(gx)|dm_{L}(g). \end{aligned}  (3.3)

On the other hand, for every a ∈ A_{j}, A(F_{j}, f)(ax) > λ, hence

\begin{aligned}∫_{F_{j}a} f(gx)dm_{L}(g) & = Δ(a) ∫_{F_{j}} f(gax)dm_{L}(g) \\ & = |F_{j}a|A(F_{j}, f)(ax) ≥ λ|F_{j}a| \end{aligned}

(where as before Δ is the modular function of G defined by (2.8)) Thus, using the third part in Lemma 2.1,

\begin{aligned}E(∫_{F} Λ(g)f(gx)dm_{L}(g)) & = E( ∑_{B∈F(ϵ⃗)} ∫_{B} f(gx)dm_{L}(g)) \\ & ≥ λ E (∥F(ϵ⃗)∥) ≥ λγ(1, C)|⋃_{j=1}^{n_{0}} A_{j}| \end{aligned} (3.4)

Finally, by definition,

|⋃_{j=1}^{n_{0}} A_{j}| = ∫_{F′} 1_{D}(gx)dm_{L}(g).  (3.5)

Combining equations (3.3), (3.4) and (3.5) we get (3.2).

To finish the proof, we take F as above and integrate (3.2) as follows

μ(D) = \frac{1}{|F′|} ∫_{X} ∫_{F′} 1_{D}(gx)dm_{L}(g)dμ(x)

≤ \frac{cλ^{−1}}{|F′|} ∫_{X} ∫_{F} |f(gx)|dm_{L}(g)dμ(x)

≤ cλ^{−1}(1 + ϵ) ∫_{X} |f(x)|dμ(x).

As ϵ is arbitrary, the theorem is proven.

Once the maximal inequality is known, we can follow a well trodden path to proving the pointwise ergodic theorem. Since this part is standard (see e.g. [19, pp. 92–93]), we only give a rough sketch of the argument.

Theorem 3.3. Let G be an amenable group acting on a measure space (X, B, μ) by measure preserving transformations, and let F_{n} be a tempered Følner sequence. Then for any f ∈ L^{1}(μ), there is a G-invariant f̄ ∈ L^{1}(μ) such that

lim_{n→∞} A(F_{n}, f)(x) = f̄(x)  a.e.  (3.6)

Proof. First we note that for any f ∈ L^{1}(μ) invariant under the action of G, the ergodic theorem obviously holds.

Denote by E the σ-algebra of all G-invariant subsets of X (i.e. all those A such that for all g, μ(gA △ A) = 0). It is clearly enough to prove the theorem for the closed subspace L^{1}(μ)_{0} of all those f such that the conditional expectation E_{μ}(f |E) = 0, where E_{μ} denotes taking the expectation according to the probability measure μ on X. For these f ∈ L^{1}(μ)_{0} we shall show that for a.e. x,

lim_{n→∞} A(F_{n}, f)(x) = 0.  (3.7)

A simple calculation shows that (3.7) is true for all f of the form f(x) = h(gx) − h(x) for some g ∈ G and h ∈ L^{∞}(μ), and that these f are in L^{1}(μ)_{0}. One further shows (for example by considering the dual space) that these f span a dense subspace of L^{1}(μ)_{0}.

To deduce the ergodic theorem for general f ∈ L^{1}(μ)_{0}, one presents it as f = f_{1} + f_{2}, with f_{1} ∈ L^{1}(μ)_{0} a function on the dense subset on which (3.7) holds, and ∥f_{2}∥_{1} < ϵ. We use the maximal inequality applied to f_{2} to deduce that

μ\{M[f_{2}](x) > \sqrt{ϵ}\} ≤ \frac{c}{\sqrt{ϵ}}∥f_{2}∥ ≤ c\sqrt{ϵ},

and so for all x outside of this set (a set of measure c\sqrt{ϵ}),

\overline{lim}_{n→∞}|A(F_{n}, f)(x)| ≤ lim_{n→∞} |A(F_{n}, f_{1})(x)| + |M[f_{2}](x)| ≤ c\sqrt{ϵ}

and since ϵ was arbitrary the theorem is established.

Note that for the pointwise ergodic theorem, unlike the situation in the maximal inequality, we need to assume that F_{n} is not only a tempered sequence of compact sets, but is in addition a Følner sequence. This is used to find a dense set of f ∈ L^{1}(μ)_{0} on which the pointwise ergodic theorem holds, namely h(gx) − h(x) for g ∈ G and h ∈ L^{∞}(μ).

4. The Shannon-McMillan-Breiman Theorem for Discrete Groups

In this section we prove the SMB Theorem for discrete groups. Throughout this section, G will denote a discrete amenable group. In order to state this theorem, we need to introduce a few notations. If P is a finite 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. We assume throughout that G acts ergodically on (X, B, μ).

A process is simply a space (X, B, μ) that G acts on together with a partition P of X. The entropy h(P) of the process can be defined in a few equivalent ways. Since we are mainly interested in the SMB theorem, we shall define the entropy using this theorem.

Theorem 4.1. Let P be a finite partition, and assume that G is a discrete amenable group acting ergodically on a measure space (X, B, μ). Assume F_{n} is a tempered sequence of Følner sets, with |F_{n}|/ log n → ∞. Then there is a constant h(P) such that

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

a.e. and in L^{1}(μ).

The constant h(P) is called the entropy of the process. Remarks:

1. Throughout this section, all logarithms are to base 2.

2. The usual definition of h(P) is via the entropy function

H(Q) = − ∑_{A∈Q} μ(A) log μ(A),

as follows:

\underline{h}(P) = lim_{n→∞} \frac{1}{|F_{n}|}H(P^{F_{n}});

implicit in this definition is that this limit always exists (see [16] or the appendix to [11] for a proof using the Ornstein Weiss quasitiling technique or [13, Chapter 4] for a different approach). To see that this definition coincides with our previous one, simply note that

\frac{1}{|F_{n}|}H(P^{F_{n}}) = − ∫_{X} \frac{log μ(P^{F_{n}}(x))}{|F_{n}|}dμ(x).

Since the integrand on the right hand side tends to h(P) in L^{1}, so does the left hand side.

3. Since we do not assume that F_{n} is monotone increasing, some control over how slowly |F_{n}| is allowed to grow is useful, even though it may well be that the very mild rate required in Theorem 4.1 is automatically satisfied for tempered sequences.

We now turn to prove Theorem 4.1. The next lemma is of a combinatorial nature:

Lemma 4.2. For any η > 0 there is an N = N(η) such that for any finite F ⊂ G, and any finite sequence F_{1}, F_{2}, …, F_{r} of finite subsets of G satisfying the growth condition

|F_{n}| ≥ max(8η^{−1}(log n + 1), N)  (4.2)

the number of 1/2-disjoint subcollections of

{F_{n}a: a ∈ F, n = 1, 2, … }

is at most c_{1}2^{η|F′|} where F′ is the set

F′ = [⋃_{i=1}^{r} F_{i}] F.

Proof. Let F be any 1/2-disjoint subcollection as above. We set A to be the multiset (i.e. a ‘set’ in which an element may appear more than once )

A = {a ∈ F: ∃n s.t. F_{n}a ∈ F}.

In general, this can be multiset if for n ≠ m both F_{n}a and F_{m}a ∈ F; the number of appearances of a in the multiset A is taken to be the number of integers n for which F_{n}a ∈ F. Since F is 1/2-disjoint, and clearly any B ∈ F is a subset of F′

2|F′| ≥ ∑_{B∈F} |B| ≥ N|A|

hence |A| ≤ 2|F′|/N. As elementary combinatorics show, if N is large enough there are at most c_{2}2^{η|F′|/2} choices of A. Given A, the collection F is specified by assigning to every a ∈ A an integer i(a) — the index of the F_{i} such that F_{i}a ∈ F (for a appearing more then once in A, say with multiplicity n, we assign to a n integers). This assignment can be encoded using words of a three letter alphabet (say {0, 1, ∗}) of length

∑_{a∈A}(log(i(a)) + 1).

A simple way to do this is fix some arbitrary order on the elements of F, which induces an order on A – say a_{1}, a_{2}, …, and encoding i(·) by specifying the binary expansion of i(a_{1}), i(a_{2}), … separated by ∗-symbols.

However, using the growth condition (4.2)

(log(i(a)) + 1) ≤ \frac{η}{8}|F_{i(a)}|

and so i(·) can be encoded using

\frac{η}{8} ∑_{B∈F} |B| ≤ \frac{η}{4}|F′|

digits of a three letter alphabet.

Thus the number of possible F is at most the number of possibilities of choosing A (which we showed above is at most c_{2}2^{η|F′|/2}) times the number of words of length at most \frac{η}{4}|F′| in a three letter alphabet, giving a number smaller than

c_{3}2^{η|F′|/2} × 3^{η|F′|/4} ≤ c_{1}2^{η|F′|}

We recall the standard notation for set sequences

\overline{lim}_{k→∞} B_{k} = ⋂_{k=1}^{∞} (⋃_{j=k}^{∞} B_{j})

Lemma 4.3. Assume that G acts ergodically on a measure space (X, B, μ), and that F_{n} is a tempered Følner sequence. Let B_{n} be subsets of X such that

μ(\overline{lim}_{k→∞}B_{k}) > 0.

Then for any δ > 0 and almost every x ∈ X there is a n(x) ∈ ℕ for which the following is true: for every n ≥ n(x) there is there is collection of sets

F = {F_{k_{i}}a_{i}: 1 ≤ i ≤ r}

with all a_{i} ∈ F_{n} and 1 ≤ k_{i} < n(x) such that:

1. a_{i}x ∈ B_{k_{i}} for all i.

2. F is δ-disjoint.

3. | ∪ F| ≥ (1 − δ)|F_{n}|.

Proof. We take B to be

B = \overline{lim} B_{i},

δ′ = δ^{4}/100, D to be a finite set such that

μ(DB) > 1 − δ/10

(the existence of such a D is a consequence of ergodicity, even if G is not discrete), and C to be the temperedness constant for the sequence F_{i}. Take M to be large enough so that Lemma 2.4 holds for δ′, C and D.

We now define two integer sequences m_{i} and N_{i}, 1 ≤ i ≤ M, as follows:

1. Set m_{1} = 1.

2. If m_{i} is known, set N_{i} to be large enough so that

μ(B \ ⋃_{j=m_{i}}^{m_{i}+N_{i}} B_{j}) < \frac{δ}{10M|D|}.

3. Finally, if N_{i} is known, use the fact that F_{n} is a Følner sequence to find an integer m_{i+1} large enough so that for all ℓ ≥ m_{i+1},

| ⋃_{j<m_{i}+N_{i}} DF_{j}^{−1}F_{ℓ}| ≤ (1 + δ′)|F_{ℓ}|.

Set B′ = ⋂_{i=1}^{M} ⋃_{j=m_{i}}^{m_{i}+N_{i}} B_{j}. Clearly

μ(B\B′) < ∑_{i=1}^{M} μ (B\ ⋃_{j=m_{i}}^{m_{i}+N_{i}} B_{j}) < \frac{δ}{10|D|}

so

μ(DB′) ≥ μ(DB) − δ/10 ≥ 1 − δ/5.

We define n(x) using the pointwise ergodic theorem for a.e. x as the smallest integers greater than m_{M} + N_{M} such that for every n ≥ n(x)

A(F_{n}, 1_{DB′})(x) > 1 − δ/2,

and from now till the end of the proof n will be fixed.

We now set for 1 ≤ j ≤ N_{i} F̄_{i,j} = F_{m_{i}+j−1}, and

A_{i,j} = {a ∈ F_{n}: ax ∈ B_{m_{i}+j−1} and F̄_{i,j}a ⊂ F_{n}}

For every i,

⋃_{j=1}^{N_{i}} DA_{i,j} ⊃ {a ∈ F_{n}: ax ∈ D ⋃_{j=1}^{N_{i}} B_{m_{i}+j−1}}

Hence

|⋃_{j=1}^{N_{i}} DA_{i,j}| ≥ |F_{n}|A(F_{n}, 1_{DB′})(x) ≥ (1 − δ/2)|F_{n}|.

We now apply Lemma 2.7 on the arrays F̄_{i,j}, A_{i,j} and the set

F̄ = [ ⋃_{j=1}^{n(x)} F_{j}] F_{n}

to deduce that there is a subcollection F of

{F̄_{i,j}a: a ∈ A_{i,j}}

that is 10δ′^{1/4} disjoint and satisfying

| ∪ F| ≥ (1 − δ/2 − δ′^{1/4})|F_{n}| ≥ (1 − δ)|F_{n}|.

This subcollection is the sought after collection.

Lemma 4.4. Assume that G acts ergodically on a measure space (X, B, μ). We take F_{n} to be a tempered Følner sequence, and set

h = ess-inf_{x∈X} \underline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|}  (4.3)

Then for any δ > 0, N ∈ ℕ and almost every x ∈ X there is a n(x) ∈ ℕ for which the following is true: for every n ≥ n(x) there is there is collection of sets

F = {F_{k_{i}}a_{i}: 1 ≤ i ≤ r}

with all a_{i} ∈ F_{n} and N ≤ k_{i} < n(x) such that:

1. For every 1 ≤ i ≤ r,

\frac{− log(μ(P^{F_{k_{i}}}(a_{i}x)))}{|F_{k_{i}}|} ≤ h + δ.

2. F is δ-disjoint.

3. | ∪ F| ≥ (1 − δ)|F_{n}|.

Proof. Apply the previous lemma on the tempered Følner sequence

F_{N}, F_{N+1}, F_{N+2}, …

and the sets

B_{i} = \{x: \frac{− log(μ(P^{F_{N+i}}(x)))}{|F_{N+i}|} ≤ h + δ\}

Lemma 4.5. If G and (X, B, μ) are as above, and F_{n} a tempered Følner sequence with

|F_{n}|/ log n ⟶ ∞,  (4.4)

then for a.e. x ∈ X,

\overline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} ≤ ess-inf_{x′} \underline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x′)))}{|F_{n}|}.

Proof. Let h be defined as in (4.3), and δ > 0 arbitrary. Let N be large enough so that Lemma 4.2 holds for η = δ and so that

|F_{j+N}| ≥ 8η^{−1}(log j + 1) for all j ≥ 1

We know that for a.e. x, and n large enough, 1–3 of Lemma 4.4 hold. Set

F′ = [ ⋃_{j=1}^{n(x)} F_{j} ∪ {e}] F_{n}

with n(x) as in Lemma 4.4. Since F_{n} is a Folner sequence, if n is large enough

|F′Δ F_{n}| < δ |F_{n}|  (4.5)

This means that for a.e. x, for n large enough the P^{F_{n}}-name of x is of a special form: there is a collection of sets F which is:

1. δ-disjoint

2. satisfies | ∪ F| ≥ (1 − δ)|F_{n}|,

3. Any B ∈ F is of the form F_{k}a with k ≥ N and a ∈ F_{n}.

4. For any B ∈ F

\frac{− log(μ(P^{B}(x)))}{|B|} ≤ h + δ.  (4.6)

Let C_{n} denote the set of all P^{F_{n}}-names of this form. We claim that each collection F gives rise to at most 2^{(h+5δ+2 log |P|δ)|F′|} of the P^{F_{n}}- names in C_{n}. Indeed, such a P^{F_{n}}-name (say of a point x ∈ X) is determined by

a. The P^{B}-name of x for all B ∈ F

b. The P-name of gx for every g ∈ F_{n} \ ∪F.

For every B ∈ F there are at most 2^{(h+δ)|B|} P^{B}-names for which (4.6) holds. Thus we see that the number of elements of C_{n} that correspond to F is at most

∏_{B∈F} 2^{(h+δ)|B|} × |P|^{|F_{n}\∪F|}.

Since F covers (1 − δ)|F_{n}| of F′,

|F_{n}\ ∪ F| ≤ |F′\ ∪ F| ≤ 2δ|F_{n}|

since it is δ-disjoint

∑_{B∈F} |B| ≤ \frac{|F′|}{1 − δ} ≤ (1 + 3δ)|F_{n}|.

Thus we see that indeed there are at most 2^{(h+5δ+2 log |P|δ)|F_{n}|} elements of C_{n} that correspond to F, as claimed. By Lemma 4.2, the number of possibilities for F is at most 2^{δ|F′|} ≤ 2^{2δ|F_{n}|}, hence

|C_{n}| ≤ 2^{(h+7δ+2 log |P|δ)|F_{n}|}.

Consider the set

Y_{n} = \{x: \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} > h + 8δ + 2 log |P|δ\} .

Notice that

μ(Y_{n} ∩ (∪C_{n})) ≤ |C_{n}| × 2^{−(h+8δ+2 log |P|δ)|F_{n}|} ≤ 2^{−δ|F_{n}|}.

By the growth condition (4.2), for all n large enough

2^{−δ|F_{n}|} ≤ \frac{1}{n^{2}}

hence

∑_{n=1}^{∞} 2^{−δ|F_{n}|} < ∞,

and we may apply Borel-Cantelli to see that for a.e. x, for n large enough, x ∉ Y_{n} ∩ (∪C_{n}). However, we also know that for n large enough, x ∈ ∪C_{n}. Thus we see that for a.e. x, for n large enough, x ∉ Y_{n}, i.e.

\overline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} ≤ h + 8δ + 2 log |P|δ;

and since δ is arbitrary, the lemma is established.

Proof of Theorem 4.1. Set

h(P) = ess-inf_{x′} \underline{lim}_{n→∞} \frac{− log(μ(P^{F_{n}}(x′)))}{|F_{n}|}.

It follows directly from Lemma 4.5 that

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

exists and is equal to h(P) a.e.

To show L^{1}-convergence, set

B_{n} = \{x: h(P) − ϵ ≤ \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} ≤ h(P) + ϵ\} .

Notice that B_{n} is a union of complete atoms of P^{F_{n}}. Furthermore,

(h(P) − ϵ)μ(B_{n}) ≤ ∫_{B_{n}} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|}dμ(x)

≤ ∫_{X} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|}dμ(x)

≤ (h(P) + ϵ)μ(B_{n}) + ∫_{X\B_{n}} \frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|}dμ(x).

This last integral can be bounded as follows: set

μ̃(A) = \frac{μ(A \ B_{n})}{μ(X \ B_{n})}

and now

∫_{X\B_{n}}\frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|}dμ(x) = \frac{μ(X \ B_{n})}{|F_{n}|} ∫_{X} − log(μ̃(P^{F_{n}}(x)))dμ̃(x) −
− μ(X \ B_{n}) log(μ(X \ B_{n})).

(4.7)

The integral on the right hand side of (4.7) is the value of the entropy function on P^{F_{n}} with the measure μ̃, hence

(4.7) ≤ μ(X \ B_{n}) log |P| − μ(X \ B_{n}) log(μ(X \ B_{n})) ⟶ 0

as n → ∞, and so

\frac{− log(μ(P^{F_{n}}(x)))}{|F_{n}|} → h(P) in L^{1}.

5. The lamplighter group

In this section we take G to be the skew product ℤ ⋉ ∑_{i∈ℤ} ℤ/2 formally defined by

(i, a) · (j, b) = (i + j, σ^{j}a + b),

where σ: ∑_{i∈ℤ} ℤ/2 → ∑_{i∈ℤ} ℤ/2 is the shift automorphism

(σa)_{n} = a_{n−1}.

This group G is sometimes called the lamplighter group.

Theorem 5.1. For every C there is a finite K ⊂ G and δ > 0 such that if A ⊂ G is (K, δ)-invariant and C^{−1}|A| ≤ |B| ≤ |A| then

|B^{−1}A| ≥ C|A|.

Our proof relies on the following theorem of I. Ruzsa (see [20] or [12], Section 7.6):

Theorem 5.2 (I. Ruzsa). Let r ≥ 2 be an integer, and let G̃ be a commutative group in which the order of every element is at most r. Let Ã ⊂ G̃ be a finite set, |Ã| = n. If there is another B̃ ⊂ G̃ such that |B̃| = n and |Ã + B̃| ≤ αn, then Ã is contained in a subgroup H̃ of G̃ such that

|H̃| ≤ f(r, α)n,

where

f(r, α) = α^{2}r^{α^{4}}.  (5.1)

Remark: The condition |B̃| = n can clearly be weakened to |B̃| ≥ n, since otherwise we can replace B̃ by any subset of cardinality n. By suitably modifying f(r, α), this condition can be weakened further to |B̃| ≥ α^{−1}n:

Corollary 5.3. Let r and G̃ be as in Theorem 5.2, and Ã ⊂ G̃ be a finite set, |Ã| = n. For any C, α ≥ 1,if there is another B̃ ⊂ G̃ such that |B̃| ≥ C^{−1}n and |Ã + B̃| ≤ αn, then Ã is contained in a subgroup H̃ of G̃ such that

|H̃| ≤ f(r, (C + 1)α)n,

with f as in (5.1).

Proof. If the corollary holds for some group G̃, it also holds for all its subgroups, so we may as well assume G̃ is infinite. Choose some

g_{1}, g_{2}, …, g_{⌈C⌉} ∈ G̃

such that g_{i}B̃ are all disjoint, and set B̂ to be an arbitrary subset of cardinality n of

⋃_{i=1}^{⌈C⌉} (g_{i} + B̃).

Then

|Ã + B̂| ≤ (C + 1)αn

and the results follows from applying Theorem 5.2 on Ã and B̂.

We shall apply this for r = 2 and the group G̃ = ∑_{i∈ℤ} ℤ/2. We recall that ∑_{i∈ℤ} ℤ/2 is the countable group (… a_{−1}, a_{0}, a_{1} …) with a_{i} ∈ ℤ/2 and only a finite number of the a_{i} are non-zero; G̃ is also a vector space over ℤ/2. This vector space has a natural basis, consisting of the elements e_{i} ∈ G̃ which have only one non-zero coordinate at the ith place. For any A ⊂ G̃ we let ⟨A⟩ denote the subgroup (or equivalently the sub vector space) of G̃ spanned by A.

Lemma 5.4. Let H̃ be a finite dimensional subspace of the vector space G̃ over ℤ/2, such that e_{1}, …, e_{k} ∈ H̃. Then

dim(H̃ ∩ σ^{k}H̃) ≤ dim(H̃) − k.

Proof. Set, inductively

r_{1} = min {r : ∃v = ∑_{i} v^{i}e_{i} ∈ H̃ s.t. v^{r} ≠ 0, and v^{r′} = 0 ∀r′ < r}

and f_{1} = ∑_{i} f_{1}^{i}e_{i} ∈ H̃ a vector as in the right hand side of the above

equation for r = r_{1}. Similarly, we set for every 1 < ℓ ≤ k

r_{ℓ} = min {r : ∃v = ∑_{i} v^{i}e_{i} ∈ H̃ s. t. v^{r} ≠ 0, and v^{r′} = 0∀r′ < r r ≢ r_{1}, …, r_{ℓ−1} mod k }

(5.2)

and f_{ℓ} a vector as above for r = r_{ℓ}. Note that the fact that e_{1}, … e_{k} ∈ H̃ guarantees that none of the sets appearing in equation (5.2) are empty. Claim: f_{1}, f_{2}, …, f_{k} are linearly independent relative to H̃′ = H̃ ∩ σ^{k}H̃.

Assume to the contrary that

v = ∑_{i=1}^{k} a_{i}f_{i} ∈ σ^{k}H̃

and let ℓ be the least such that a_{ℓ} ≠ 0. Since v ∈ ⟨f_{ℓ}, f_{ℓ+1}, …, f_{k}⟩ it is of the form

v = e_{r_{ℓ}} + ∑_{i>r_{ℓ}} v^{i}e_{i}

But σ^{−k}v ∈ H̃, and is of the form

σ^{−k}v = e_{r_{ℓ}−k} + ∑_{i>r_{ℓ}−k} v^{i}e_{i}

which contradicts the way r_{ℓ} was chosen in (5.2). Thus the claim is established.

This shows that

dim(H̃/H̃′) ≥ k

and consequently

dim H̃′ ≤ dim H̃ − k

Proof of Theorem 5.1. Let G̃ = ∑_{i∈ℤ} ℤ/2. We will take K to be

K = {(k, 0), (0, e_{1}), (0, e_{2}), …, (0, e_{k})}

where k is some large integer depending only on C to be fixed later, and δ ≤ \frac{1}{100k}. We can present A as

A = ⋃_{i∈I}{i} × Ã_{i},

where ∅ ≠ Ã_{i} ⊂ G̃ and I ⊂ ℤ, and B^{−1} as B^{−1} = ⋃_{j∈J}{j} × B̃_{j}. Note that

(k, 0)A = ⋃_{i∈I}{i + k} × Ã_{i}
(0, e_{ℓ})A = ⋃_{i∈I}{i} × (e_{ℓ+i} + Ã_{i}).

Set A_{i} = {i} × Ã_{i} and B_{j} = {j} × B̃_{j}. The proof of Theorem 5.1 consists of two steps. Step A: There exist an i ∈ I and j ∈ J such that: (A.1) |B_{j}| ≥ C^{−2}|A_{i}| (A.2) |Ã_{i} △ Ã_{i−k}| < |Ã_{i}|/10. (A.3) For all 1 ≤ ℓ ≤ k,

|(e_{ℓ +i} + Ã_{i})Δ Ã_{i}| < \frac{| Ã_{i}|}{10}

(A.4) For both t = i, i − k

|σ^{t}(B̃_{j}) + Ã_{t}| < 10C| Ã_{t}|

The proof of this claim is based on a simple counting argument. Let

I_{1} = {i ∈ I: |Ã_{i} △ Ã_{i−k}| < |Ã_{i}|/10}.

34 ELON LINDENSTRAUSS

Since A is (K, δ)-invariant, and δ ≤ 1/100,

δ|A| ≥ |A △ (k, 0)A| = ∑_{i∈I} |Ã_{i} △ Ã_{i−k}| ≥ \frac{1}{10} ∑_{i∈I\I_{1}} |A_{i}|,

hence

∑_{i∈I_{1}} |A_{i}| ≥ 0.9|A|.

A similar calculation shows that if

I_{2} = {i ∈ I_{1} : |(e_{ℓ+i} + Ã_{i}) △ Ã_{i}| < |Ã_{i}|/10, 1 ≤ ℓ ≤ k} then

\frac{| A |}{100} ≥ ∑_{ℓ = 1}^{k} |AΔ (0, e_{ℓ})A| ≥ \frac{1}{10} ∑_{i∈I_{1}\I_{2}} | Ã_{i}|

hence

∑_{i∈I_{2}} |A_{i}| ≥ 0.8|A|.  (5.3)

Let i_{0} ∈ I_{2} be such that |A_{i_{0}}| is maximal. Then by (5.3)

|A_{i_{0}}| ≥ \frac{0.8|A|}{|I_{2}|}.

We now note that

C|A| ≥ |B^{−1}A| ≥ |B^{−1}A_{i_{0}}| ≥ |J| × |A_{i_{0}}|,

and so if we let j_{0} ∈ J be such that |B_{j_{0}}| is maximal then

|B_{j_{0}}| ≥ \frac{|B|}{|J|} ≥ \frac{|A|}{C|J|} ≥ \frac{|A_{i_{0}}|}{C^{2}}.  (5.4)

Consider

B_{j_{0}}A = ⋃_{i∈I}{j_{0} + i} × (σ^{i}(B̃_{j_{0}}) + Ã_{i}) .

Since |B_{j_{0}}A| ≤ |B^{−1}A| ≤ C|A|, for most i ∈ I, |σ^{i}(B̃_{j_{0}}) + Ã_{i}| is not much larger than C|Ã_{i}|; the exact quantitative result we need is that if

I_{3} = {i ∈ I_{2} : |σ^{i}(B̃_{j_{0}}) + Ã_{t}| ≤ 10C|Ã_{t}| for both t = i, i − k}

then

∑_{i∈I_{3}} |A_{i}| ≥ |A|/5.  (5.5)

Indeed, it follows from the definition of the set I_{1} that for every i ∈ I_{2} ⊂ I_{1}, |A_{i−k}| ≥ 0.9|A_{i}|, and so

∑_{i∈I_{2}\I_{3}} |A_{i}| < 2 ∑_{i∈I_{2}\I_{3}} min(|A_{i}|, |A_{i−k}|)

≤ \frac{1}{5C} ∑_{i∈I_{2}\I_{3}} (|σ^{i}(B̃_{j_{0}}) + Ã_{i}| + |σ^{i−k}(B̃_{j_{0}}) + Ã_{i−k}|)

≤ \frac{2}{5C} |B_{j_{0}}A| ≤ \frac{2|A|}{5}.

In particular, I_{3} is non-empty; let i_{3} ∈ I_{3}. The claim is established for i = i_{3} and j = j_{0}. Step B: If k is large enough (depending only on C), conditions (A.1)– (A.4) of Step A are mutually exclusive.

Set

Ã′ = Ã_{i} ∩ Ã_{i−k}.

Then

|Ã′| ≥ |Ã_{i}|/2  (5.6)

and thus from properties (A.1)–(A.4) we see that Ã′ satisfies the following:

|B̃_{j}| ≥ |Ã′|/10C^{2}  (5.7)
|σ^{i}(B̃_{j}) + Ã′| = |B̃_{j} + σ^{−i}(Ã′)| ≤ 20C|Ã′|  (5.8)
|σ^{i−k}(B̃_{j}) + Ã′| = |B̃_{j} + σ^{−i+k}(Ã′)| ≤ 20C|Ã′|  (5.9)

By Corollary 5.3 we can conclude that if

H̃ = \left⟨{ \atop Ã′}\right⟩

then for some β = β(C) that depends only on C (which can be easily worked out explicitly from the statements of the corollary)

|H̃| ≤ β|Ã′|.

By (A.2), (A.3), and (5.6)

|(e_{ℓ + i} + Ã′)Δ Ã′| ≤ |(e_{ℓ + i} + Ã_{i})Δ Ã_{i}| + 2 |Ã_{i}Δ Ã_{i−k}| ≤ \frac{6|Ã′ |}{10}

and so (e_{ℓ+i} + Ã′) ∩ Ã′ ≠ ∅ which of course implies that

e_{ℓ+i} ∈ Ã′ − Ã′ ⊂ H̃ for every 1 ≤ ℓ ≤ k.

Let π: G̃ → G̃/H̃ be the natural projection. Then since Ã′ is in the kernel of π

|σ^{i}B̃_{j} + Ã′| ≥ |π ∘ σ^{i}(B̃_{j})| × |Ã′|,

and similarly for i − k. Thus using (5.8) and (5.9)

|π ∘ σ^{t}(B̃_{j})| ≤ 20C

for both t = i, i − k. This implies that B̃_{j} is contained in at most 20C cosets of σ^{−i}H̃ as well as 20C cosets of σ^{−i+k}H̃, so B̃_{j} is contained in 400C^{2} cosets of σ^{−i}H̃ ∩ σ^{−i+k}H̃. By Lemma 5.4,

|σ^{−i}H̃ ∩ σ^{−i+k}H̃| ≤ 2^{−k}|H̃| ≤ β2^{−k}|Ã′|,

and so

|B̃_{j}| ≤ 400C^{2}β(C)2^{−k}|Ã|;

if k is sufficiently large (depending on C) we obtain a contradiction to Step A.

The following corollaries are now immediate:

Corollary 5.5. There is no Følner sequence F_{n} for the lamplighter group G satisfying the Tempelman condition

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

Corollary 5.6. For every tempered Følner sequence F_{n} for the lamplighter group G

\frac{|F_{n+1}|}{|F_{n}|} ⟶ ∞.

It follows that the growth of |F_{n}| is super-exponential.

Acknowledgments: The results of this paper 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, V. Lev for giving a very clear exposition of Ruzsa’s results, and last but not least, my wife Abigail Reiss for her help and encouragement in the preparation of this paper.

References

[1] J. Bourgain, Pointwise ergodic theorems for arithmetic sets (Appendix: The return time theorem jointly with H. Furstenberg, Y. Katznelson and D. Ornstein), Publ. Math. I.H.E.S. 1989, 69, pp 5–45.

[2] A. P. Calderon, A general ergodic theorem, Annals of Mathematics, 1953, vol 58, no. 1, pp 182–191.

[3] W. R. Emerson, The pointwise ergodic theorem for amenable groups, American Journal of Mathematics, 1974, vol. 96, no. 3, pp 472–478.

[4] W. R. Emerson and F. P. Greenleaf, Groups structure and the pointwise ergodic theorem for connected amenable groups, Advances in Math., 1974, vol. 14, pp 153–172.

[5] G. A. Freiman Structure theory of set addition, Asterisque, 1999, bf 258, pp 1–33.

[6] M. Gromov, Groups of polynomial growth and expanding maps, Publ. Math. I.H.E.S. 1981, 53, pp 53–73.

[7] A. del Junco and J. Rosenblatt , Counterexamples in ergodic theory and number theory, Math. Ann. 1979, 245, pp 185–197.

[8] V. Kaimanovich and A. Vershik, Random walks on discrete groups: boundery and entropy, Ann. Prob. 1983, vol. 11 no. 3, pp 457–490.

[9] J. Kieffer, A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space, Ann. Prob. 1975, vol. 3, 1031–1037.

[10] E. Lindenstrauss, Pointwise theorems for amenable groups (research announcement), Electronic Research Announcements of the AMS, 1999, vol. 5, pp 82–90.

[11] E. Lindenstrauss and B. Weiss, Mean topological dimension, Israel J. of Math. 2000, 115, pp 1–24.

[12] M. Nathanson, Additive number theory — inverse problems and the geometry of sumsets, GTM #165, 1996, Springer-Verlag, New York.

[13] J. M. Ollagnier, Ergodic theory and statistical mechanics, LNM #1115, 1980, Springer-Verlag, New York.

[14] D. Ornstein and B. Weiss, The Shannon-McMillan-Breiman theorem for a class of amenable groups, Israel Journal of Mathematics, 1983, vol. 44 No. 1, pp 53–60.

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

[16] D. Ornstein and B. Weiss, Entropy and isomorphism theorems for actions of amenable groups, Journal D’analyse Mathematique, 1987, vol. 48, pp 1– 142.

[17] D. Ornstein and B. Weiss, Subsequence ergodic theorems for amenable groups, Israel Journal of Mathematics, 1992, vol. 79, pp 113–127.

[18] A. Paterson, Amenability, Mathematical Surveys and Monographs 29, 1988, American Mathematical Society, Providence, Rhode Island.

[19] K. Petersen, Ergodic theory, 1983, Cambridge studies in advanced mathematics 2, Cambridge University Press, Cambridge, UK.

[20] I. Ruzsa, An analog of Freiman’s theorem in groups, Structure theory of set addition, Astrisque 1999 258, xv, 323–326.

[21] D. Rudolph, Fundamentals of Measurable Dynamics — Ergodic theory on Lebesgue spaces, 1990, Oxford University Press, Oxford, Great Britain.

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

[23] A. Schulman and A. Tempelman, Pointwise ergodic theorems for isometric representations, preprint.

[24] A. Tempelman , Ergodic theorems for general dynamic systems, Dokl. Akad. Nauk SSSR, 1967, vol. 176, no. 4, pp 790–793 (English translation: Soviet Math. Dokl., 1967, vol. 8, no. 5, pp. 1213–1216.)

[25] A. Tempelman, Ergodic theorems for group actions, informational and thermodynamical aspects, 1992, Kluwer Academic Publishers, Dordrecht, The Netherlands.

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

Current address: School of Mathematics, Institute for Advanced Study, Olden lane, Princeton NJ 08540 and Department of Mathematics, Stanford University, Stanford, CA 94305

E-mail address: elon@ias.edu