Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you either view the HTML version or    *
%_ * retrieve the article in DVI, PostScript, or PDF format.                *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{28-JUN-1999,28-JUN-1999,28-JUN-1999,28-JUN-1999}
 
\documentclass{era-l}
\usepackage{amssymb}

\newcommand {\DS}  {\displaystyle}
\newcommand {\TS}  {\textstyle}

\newcounter{AbcT}
\renewcommand{\theAbcT}{\Alph{AbcT}}

\newtheorem {Theorem}{Theorem}[section]
\newtheorem {Lemma}[Theorem]{Lemma}
\newtheorem {Corollary}[Theorem]{Corollary}
\newtheorem {Proposition}[Theorem]{Proposition}
\newtheorem {AbcTheorem}[AbcT]{Theorem}

\theoremstyle{remark}
\newtheorem {Claim}[Theorem]{Claim}

\theoremstyle{definition}
\newtheorem {Definition}[Theorem]{Definition}
\newtheorem {Example}[Theorem]{Example}
\newtheorem {Conjecture}[Theorem]{Conjecture}


\numberwithin{equation}{section}

\newcommand {\Heads}[1]   {\smallskip\pagebreak[1]\noindent{\bf #1{\hskip
0.2cm}}}
\newcommand{\Head}[1]{\Heads{#1:}}

\newcommand{\equ}[1]{\eqref{#1}}
\newcounter{DM@bibnum}
\newcommand{\bibnum}{\stepcounter{DM@bibnum}\parbox[c]{8mm}{[%
\arabic{DM@bibnum}]}}

\newcommand {\cond}   {\:|\:}
\newcommand {\B}[3] {{B(#1,#2,#3)}}
\newcommand {\Bt}[3] {{B'(#1,#2,#3)}}
\newcommand {\Bh}[3] {{{\hat B}(#1,#2,#3)}}
\newcommand {\C} {{\mathbb C}}
\DeclareMathOperator {\E} {{\mathbf{E}}}
\newcommand {\N} {{\mathbb N}}
\newcommand {\T} {{\mathbb T}}
\newcommand {\Z} {{\mathbb Z}}
\newcommand {\cP} {{\mathcal P}}
\newcommand {\cC} {{\mathcal C}}
\newcommand {\bF} {{\bar F}}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\co}{co}

\newcommand {\diff}       {\bigtriangleup}
\newcommand {\Borel}      {\mathcal B}
\newcommand {\intf} {\mu(f)}

\begin{document}
\title{Pointwise theorems for amenable groups}
\author{Elon Lindenstrauss}
\address{Institute of Mathematics, The Hebrew University, Jerusalem 
91904,
Israel}
\email{elon@math.huji.ac.il}

\issueinfo{5}{12}{}{1999}
\dateposted{June 30, 1999}
\pagespan{82}{90}
\PII{S 1079-6762(99)00065-7}
\def\copyrightyear{1999}
\copyrightinfo{1999}{American Mathematical Society}

\subjclass{Primary 28D15}
\date{January 18, 1999} 
\commby{Yitzhak Katznelson}
\keywords{Amenable groups, pointwise convergence, ergodic theorems}
\thanks{The author would like to thank the Clore Foundation for its 
support.}
\begin{abstract}
In this paper we describe proofs of the pointwise ergodic 
theorem and
Shannon-McMillan-Breiman theorem for discrete amenable groups,
along F\o lner sequences that obey some restrictions.
These restrictions are mild enough so that such sequences exist for
all amenable groups.
\end{abstract}
\maketitle

\section{Introduction}

The classical ergodic theory deals with measure preserving
$\Z$ 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 (\cite{OW87}).

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 \subset G$ 
and $\delta>0$ there
is a finite set $F \subset G$ such that
\[
| F \diff kF | < \delta |F| \qquad\text{for all $k \in K$}.
\]
Such a set $F$ will be called $\mathbf{(K, \delta)}$\textbf{-invariant}.
A sequence $F_1, F_2, \dots$ of finite subsets of $G$ will be called a
\textbf{F\o lner sequence}
if for every $K$ and $\delta>0$, for all large enough $n$ we have that
 $F_n$ is $(K, \delta)$-invariant. To avoid uninteresting complications,
we assume $|F_n| \geq n$.

Suppose now that $G$ acts from the left by measure preserving 
transformations on
a Lebesgue space $(X, \Borel, \mu)$ with $\mu(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 $\mu$
 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 $\Z$ actions.

\begin{Theorem}
If $G$ is amenable, and acts ergodically on $(X, \Borel, \mu)$, then for 
any
$f \in L^1(\mu)$, and F\o lner sequence $F_n$,
\[
A(F_n,f)(x) \underset{n \to \infty}{\longrightarrow} \int f(x) d \mu(x) 
\qquad \text{in $L^1$},
\]
where $A(F, f)(x)$ denotes the average
\[
A(F, f)(x) = \frac{1}{|F|} \sum_{g \in F} f (gx).
\]
\end{Theorem}

The obvious pointwise analogue of this fails, even for $G=\Z$. Indeed,
let
\[
F_n= \{n^2, n^2+1, \dots, n^2+n\}.
\]
Then it is not hard to find
ergodic systems $(X, \Borel, \mu)$ and functions $f \in L^\infty(\mu)$ 
such that
$A(F_n, f)(x)$ does not have a limit almost everywhere (in fact, in
\cite{JR79} it is shown that for {\em every} nontrivial $(X, \Borel, 
\mu)$
there is such an $f \in L^\infty(\mu)$).
Thus one needs to impose some clever condition on the F\o lner sequence 
to
have pointwise convergence. We shall use the following condition 
introduced
in \cite{Shu88}:

\begin{Definition}[A. Shulman]
A sequence of sets $F_n$ will be said to be tempered
if for some $C>0$ and all $n$,
\begin{equation}
\label{eq: require}
\Bigl |\bigcup_{k \leq n} F_k^{-1} F_{n+1} \Bigr | \leq C|F_{n+1}|.
\end{equation}
\end{Definition}

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

Our main results are the following:

\begin{Theorem}[Pointwise Ergodic Theorem]
\label{thm: pointwise ergodic}
Let $G$ be an amenable group acting ergodically on a measure space
$(X, \Borel, \mu)$, and let $F_n$ be a tempered F\o lner sequence. Then
for any $f \in L^1(\mu)$,
\[
\lim_{n \to \infty} A(F_n,f)(x) = \int f(x) d \mu(x) \qquad\text{a.e.}
\]
\end{Theorem}

We remark that the case of $f \in L^2$ follows from Shulman's result.


\begin{Theorem}[Generalized Shannon-McMillan-Breiman Theorem]
\label{thm: GSMB}
Let $\cP$ be a finite partition, and assume that $G$ is an amenable group
acting ergodically on a measure space $(X, \Borel, \mu)$. Let $h(\cP)$
denote the entropy of this process.
Assume that $F_n$
is a tempered sequence of F\o lner sets. Then for almost every $x$,
\[
\frac{-\log(\mu(\cP^{F_n} (x)))}{|F_n|} \to h(\cP) \qquad \text{as $ n 
\to \infty$.}
\]
\end{Theorem}

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 \cite{OW85} 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 $\Z$ and 
more general
groups is a version of the Vitali Covering Theorem. This is used to 
show that
from a collection $\bar {\mathcal F}$  of right translates of certain
sets $F_1, \dots, F_M$
that cover most of a big set
$F \subset G$ it is possible to extract
a disjoint subcollection that covers some
fixed fraction of the elements of $F$ (the sets $F_1, \dots, F_M$ are 
assumed to be
much smaller than $F$). For this to work, one needs that the
sets $F_n$ satisfy the \textbf{Tempelman
condition}
\[
|F_n^{-1} F_n | \leq C |F_n|.
\]


The basic new idea in our proof  is to treat the
subcollections of $\bar {\mathcal F}$ as random variables. What we show 
in
Lemma~\ref{lem: vitsub} is that it is possible to find a distribution 
on the subcollections
of $\bar {\mathcal  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. \cite{Tem67}, \cite{Em74}, 
\cite{OW83})
have been written
about pointwise
theorems along increasing F\o lner sequences
satisfying the Tempelman condition;
a similar result can be found also in \cite{Cal53}.
Shulman proved the pointwise ergodic theorem for not necessarily 
increasing F\o lner
sequence satisfying a modified form of Tempelman's condition,
and also the maximal ergodic theorem for $f \in L^2$ along
tempered sequences mentioned earlier. Shulman proves these results 
using a
 functional analysis argument; they can be found in 
\cite[Section~5.6]{Tem},
or in \cite{Shu88}.
Finally we remark that for $f \in L^{1+\epsilon}$, the pointwise 
ergodic theorem is
known for all {\em 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 
\cite{EG74} or \cite[Chapter~5]{Pat}.

Though superficially similar to \equ{eq: require}, Tempelman's condition
is much stronger.
In particular, there seems to be no reason that a general amenable group
have F\o lner sequences satisfying the Tempelman condition. On the 
other hand
the following is easy:

\begin{Proposition}
Every F\o lner sequence $F_n$
has a tempered subsequence. In particular, every amenable group has
a tempered F\o lner sequence.
\end{Proposition}

\begin{proof}
Let $F_n$ be a F\o lner sequence.
We define $n_i$ inductively as follows. We start with $n_1=1$.
If $n_1, \dots, n_i$ have been determined, we set
$\tilde F_{i} = \bigcup_{j \leq i} F_{n_j}$, and
take $n_{i+1}$ to be large enough so that $F_{n_{i+1}}$  is
$\bigl (\tilde F_i^{-1}, 1/|\tilde F_i| \bigr)$-invariant.
A simple calculation shows that
\[
\Bigl |\bigcup_{j \leq i} F_{n_j}^{-1} F_{n_{i+1}} \Bigr| < 2 |F_{n_{i+
1}}|,
\]
so the sequence $F_{n_i}$ satisfies \equ{eq: require} with $C=2$.
\end{proof}

Conversely, one can show that
for any group $G$, if $F_n$ is a tempered sequence of sets such that
$\bigcup_{n=1}^\infty F_n$ is not too small (for example, if it is 
equal to $G$),
then $F_n$ is automatically a F\o 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.

\section{Random selection of F\o 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 $\Z^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:

\begin{Lemma}
\label{lem: cover 1}
Let $\delta>0$ be given, and take $\epsilon$ to be small, and $M$ large
depending on $\delta$.
Let $\bF_1, \dots, \bF_M \subset G$
be a sequence of
finite sets such that
\begin{equation}
\label{eq: cond lem 1}
\Bigl | \bigcup_{j \leq i} \bF_j^{-1} \bF_{i+1} \Bigr | < (1+\epsilon) 
|\bF_{i+1}|,
\end{equation}
let $F$ be another finite subset of $G$
(usually much bigger than $\bF_M$),
and, for $i=1, \dots ,M$, let $A_i \subset F$ be a set such that $F_i 
A_i \subset F$.
Then there are sets $B(i,a)$ which are either $\bF_i a$
or $\emptyset$ (with $i=1, \dots, M$ and $a \in A_i$) such that
\[
(1+\delta) \Bigl | \bigcup_{i,a} B(i,a) \Bigr |  \geq \sum_{i,a} 
|B(i,a)| \geq \min_i |A_i| - \delta |F|.
\]
\end{Lemma}

Lemma~\ref{lem: cover 1} is a traditional covering lemma, where we 
extract out
of a given collection of translates of the $\bar 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 \equ{eq: cond lem 1} is used.

\begin{Lemma}
\label{lem: cover 2}
Let $\delta>0$, and $C>0$ be given.
Let $N \in \N$, and assume that the sets $\bF_1, \dots, \bF_N$  satisfy
\[
\Bigl | \bigcup_{j \leq i}\bF_j^{-1} \bF_{i+1} \Bigr | < C |\bF_{i+1}|.
\]
Let $F$ be a big finite subset of $G$, and let $A_j$ (for $j=1, \dots, 
N$) be sets
such that $\bF_j A_j \subset F$.
Then it is possible to find set-valued random variables $B(j,a)$ (for 
$j=1, \dots, N$ and
$a \in A_j$) such that
\begin{enumerate}
\item
$B(j,a)$ is either $\bar F_j a$ or $\emptyset$.
\item
If we set $\Lambda \colon F \to \N$ to be the random function
$\Lambda (g)  = \sum_{j,a} 1_{B(j,a)}(g)$,
then for all $g \in F$,
\[
\E( \Lambda(g) \cond \Lambda(g)>0) < (1+\delta).
\]
\item For some $\gamma>0$ that depends on $\delta$ and $C$,
\[
\E \Bigl ( \sum_{g \in G} \Lambda (g) \Bigr ) = \E \Bigl ( \sum_{j,a} 
|B(j,a)| \Bigr ) >
\gamma(\delta, C) \Bigl | \bigcup_{j=1}^N A_j \Bigr |.
\]
\end{enumerate}
\end{Lemma}

The main disadvantage of Lemma~\ref{lem: cover 2}
is that the random subcollection of sets $\{B(i,a)\}$ covers only a 
small percentage of $F$.
By combining Lemma~\ref{lem: cover 1} and Lemma~\ref{lem: cover 2} we can
overcome this problem. This combined lemma works with two-dimensional 
arrays
of F\o lner sets $\bF_{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)\succ(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'$.

\begin{Lemma}
\label{lem: vitsub}
For any $\delta$, $C>0$ and finite $K \subset G$, if $M$ is large enough
and $\epsilon$ small enough  (depending on all these parameters),
the following is true.
Suppose that we are given an array of finite subsets $\bF_{i,j}$ of $G$,
where $i=1, \dots, M$ and $j=1, \dots ,N_i$, such that
\begin{align*}
\Bigl | \bigcup_{(i',k') \preceq (i,k)}\bF_{i',
k'}^{-1} \bF_{i, k+1} \Bigr| &\leq C |\bF_{i,k+1}|
	\qquad\text{for $k=1 ,\dots, N_i-1$},\\
\Bigl | \bigcup_{(i',k') \preceq (i,N_{i})} K \bF_{i', k'}^{-1} \bF_{i+
1, k} \Bigr | &\leq 
(1+\epsilon) |\bF_{i+1,k}| \qquad\text{for $k=1, \dots, N_{i+1}$}.
\end{align*}
We also assume we are given $A_{i,j} \subset F$
(for $i=1,\dots,M$ and $j=1,\dots,N_i$) such that $\bF_{i,j} A_{i,j} 
\subset F$
and take $\alpha$ so that for all $i$
\[
\Bigl| \bigcup_{j=1}^{N_i} K A_{i, j} \Bigr| \geq \alpha |F|.
\]
Then it is possible to find set-valued random variables $B(i,j,a)$ (for 
$i=1, \dots, M$,
$j=1, \dots ,N_i$ and
$a \in A_{i,j}$) such that
\begin{enumerate}
\item
$B(i,j,a)$ is either $\bar F_{i,j} a$ or $\emptyset$.
\item
If we set $\Lambda \colon F \to \N$ to be the random function
$\Lambda (g)  = \sum_{i,j,a} 1_{B(i,j,a)}(g)$,
then for all $g \in F$,
\[
\E( \Lambda(g) \cond \Lambda(g)>0) < (1+\delta).
\]
\item Furthermore,
\[
\E \Bigl ( \sum_{g \in G} \Lambda (g) \Bigr ) = \E \Bigl ( \sum_{i,j,a} 
|B(i,j,a)| \Bigr ) >
(\alpha - \delta) |F|.
\]
\end{enumerate}
\end{Lemma}

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~\ref{lem: vitsub};
the other lemmas use similar algorithms.

\Head{An algorithm to generate the $B(i,j,a)$'s}
\begin{enumerate}
\item
We start with $(i,j) := (N, N_M)$.
\item
For every $a \in A_{i,j}$, we perform the following
independently of all other $b \in A_{i,j}$:
\begin{itemize}
\item
If $\bF_{i,j} a$ is disjoint from $B(i',j',a')$ for all $(i',j') \succ 
(i,j)$
and $a' \in A_{i',j'}$,
then $B(i,j,a) := \bF_{i,j}a$ with probability $\epsilon / |\bF_{i,j}|$ 
and
$\emptyset$ with probability $1- \epsilon / |\bF_{i,j}|$;
\item
otherwise
$B(i,j,a) := \emptyset$.
\end{itemize}
\item Unless $(i,j)=(1,1)$,
we replace $(i,j)$ by its immediate predecessor in lexicographic order,
and return to step~2.
\end{enumerate}


\section{The pointwise ergodic theorem}

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

\begin{Theorem}
Let $G$ be an amenable group acting ergodically on a measure space
$(X, \Borel, \mu)$, and let $F_n$ be a tempered F\o lner sequence. Then
for any $f \in L^1(\mu)$,
\begin{equation}
\label{eq: ergodic}
\lim_{n \to \infty} A(F_n,f)(x) = \int f(x) d \mu(x) \qquad\text{a.e.}
\end{equation}
\end{Theorem}

\begin{proof}
It suffices to show that for any $f \in L^1(\mu)$ with $f \geq 0$,
\[
\varlimsup_{n \to \infty} A(F_n,f)(x) \leq \int f(x) d \mu(x) 
\qquad\text{a.e.}
\]
Indeed, let $g \in L^1(\mu)$, and take $R$ very large. Then
\[
\begin{split}
\varlimsup_{n \to \infty} A(F_n, g)(x) &\leq \varlimsup_{n \to \infty} 
A(F_n, \max(g, -R))(x) \\
	&\leq  \int \max(g(x), -R) d \mu(x) \underset{R \to 
\infty}{\longrightarrow} \int g(x) d \mu(x).
\end{split}
\]
Applying this also to $-g$ we get \equ{eq: ergodic}.

Let $\delta>0$, $\intf = \int f(x) d \mu(x)$.
Recall that by assumption, there is a $C$ such that
$\bigl |\bigcup_{k \leq n}F_k^{-1} F_{n+1}\bigr| \leq C |F_{n+1}|$ for 
all $n$.
Assume that for some $c>1$,  the set
\[
B = \{ x \colon \varlimsup_{n \to \infty} A(F_n,f)(x) > c \intf \}
\]
has positive measure.
Take $K$ to be a finite set such that
\[
\mu(K B) >  1 - \delta.
\]
Let $\epsilon$ be small enough and $M$ big enough so that 
Lemma~\ref{lem: vitsub}
holds for the given $\delta$, $C$ and $K$. Take $B_n$ to be
\[
B_n = \{ x \colon  A(F_n,f)(x) > c \intf \}.
\]
It is clearly possible to find $a_i$ and $N_i$ so that
\[
B' = \bigcap_{i=1}^M \Bigl ( \bigcup_{j=1}^{N_i} B_{a_i + j - 1} \Bigr)
\]
has measure at least $\mu(B) - \delta/ |K|$, and so that for every $i$ 
and $t \geq a_{i+1}$,
\[
\Bigl | \bigcup_{j \leq  a_i+N_i-1} K F_j^{-1} F_{t} \Bigr| < (1+
\epsilon) |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+\delta) \intf,
\]
and for another set of equally large measure,
\[
A(F,1_{K B'})(x) > 1-3\delta;
\]
hence there is at least one $x_0$ satisfying both.

To apply Lemma~\ref{lem: vitsub}, set $\bF_{i,j} = F_{a_i+j-1}$ for 
$i=1,\dots, M$
and $j=1, \dots, N_i$, and take
\[
A_{i,j} = \{ g \in F \colon  A(\bF_{i,j}, f) (g x_0) > c \intf \text{ 
and } \bF_{i,j}g \subset F\}.
\]
Up to boundary effects which are easily seen to be negligible, every
$g \in F$ such that $gx_0 \in KB'$ is in $\bigcup_{j=1}^{N_i} K A_{i,j}$
for every $i$, hence
\[
\Bigl | \bigcup_{j=1}^{N_i} K A_{i,j} \Bigr | \geq (1-4\delta)|F|.
\]

Let
\[
\Lambda = \sum_{i,j} \sum_{a \in A_{i,j}} 1_{\B{i}{j}{a}} (g) \colon F 
\to \N
\]
be a random function as in Lemma~\ref{lem: vitsub}.
We estimate
\[
\E \Bigr ( \sum_{g \in F} \Lambda(g) f(g x_0) \Bigl )
\]
 in two ways.
By definition of the sets $A_{i,j}$, for any $a \in A_{i,j}$,
\[
\sum_{g \in \B{i}{j}{a}} f(g x_0) > c | \B{i}{j}{a}| \intf,
\]
and so
\[
\begin{split}
\E \Bigl ( \sum_{g \in F} \Lambda(g) f (g x_0) \Bigr ) &=
	 \E \Bigl ( \sum_{i,j,a} \sum_{g \in F} 1_{\B{i}{j}{a}} f (g) \Bigr )
	\geq c   \intf  \E \Bigl ( \sum_{i,j,a} |\B{i}{j}{a}| \Bigr ) \\
	& = c \intf  \E \Bigl (\sum_{g \in F} \Lambda(g) \Bigr )  \geq 
c(1-5\delta) |F| \intf.
\end{split}
\]
On the other hand,
\[
\begin{split}
\E \Bigl ( \sum_{g \in F} \Lambda(g) f(g x_0) \Bigr ) &=
	 \sum_{g \in F} f(g x_0) \E (\Lambda(g)) \\
	&\leq (1+\delta) |F| A(F, f)(x_0) \leq (1+\delta)^2 |F| \intf.
\end{split}
\]
Since $\delta$ was arbitrary and $c>1$ we get a contradiction.
\end{proof}


\section{The Shannon-McMillan-Breiman theorem}

We begin with some notation.
If $\cP$ is a measurable partition of $X$, and $F \subset G$, we set
\[
\cP^F = \bigvee_{g \in F} g^{-1} \cP.
\]
If $x \in X$, and $\cP$ is a partition, then $\cP(x)$ is the unique
element of $\cP$ containing $x$, and is called the 
$\mathbf{\cP}$\textbf{-name}
of $x$.
Like in the previous section, we assume throughout that $G$ acts 
ergodically on
$(X, \Borel, \mu)$.

A \textbf{process} is simply a space $(X, \Borel, \mu)$ on which $G$
acts, together with a partition $\cP$ of $X$.
The entropy $h(\cP)$ 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 $\Z$ actions
given in \cite[Chapter~5]{Rud}.
We recall the definition of the entropy
$h(\cP)$ of a process:

\begin{Definition}
For any $F \subset G$ and $\epsilon>0$, we set
\[
b(F, \epsilon, \cP) = \min \{|\cC| \colon \cC \subset \cP^F \text { and }
\mu( \bigcup \cC ) > 1 - \epsilon\}.
\]
Then the entropy $h(\cP)$ is defined as
\[
h(\cP) = \lim_{\epsilon \to 0} \varliminf_{n \to \infty} \frac{\log 
b(F_n, \epsilon, \cP)}{|F_n|}
\]
where $F_n$ is a F\o lner sequence for $G$.
\end{Definition}

For definiteness, we shall take all our logarithms in base~2. It can be 
shown
that the entropy does not depend on the F\o lner sequence used;
For simplicity we assume that $F_n$ is the same F\o 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 $\sum_{i} - p_i \log p_i$.


\begin{Theorem}
Let $\cP$ be a finite partition, and assume that $G$ is an amenable group
acting ergodically on a measure  space $(X, \Borel, \mu)$.
Assume $F_n$
is a tempered sequence of F\o lner sets. Then for almost every $x$,
\[
\frac{-\log(\mu(\cP^{F_n} (x)))}{|F_n|} \to h(\cP) \qquad \text{as $ n 
\to \infty$.}
\]
\end{Theorem}

We include a rough sketch of the proof.
It is divided into two parts:
One first shows using Lemma~\ref{lem: cover 1}
and the pointwise ergodic theorem (applied to
indicator functions of certain sets) that for any $\eta>0$
there
is a sequence of $\cC(n) \subset \cP^{F_n}$ of cardinality
\[
|\cC(n)| \leq 2^{(h+ \eta) |F_n|}
\]
such that for a.e. $x$ for all
$n$ large enough,
\[
\cP^{F_n} (x) \in \cC(n).
\]
From this it is easy to deduce that
\begin{equation}
\label{eq: smb sup}
\varlimsup_{n \to \infty} \frac{-\log(\mu(\cP^{F_n} (x)))}{|F_n|} \leq 
h(\cP) + 2 \eta \qquad\text{for a.e. $x$.}
\end{equation}
Indeed, let
\[
Y(n) =  \{ x \in \bigcup\cC(n) \colon \frac{-\log(\mu(\cP^{F_n} 
(x)))}{|F_n|} > h(\cP) + 2 \eta \}.
\]
Since
\[
\mu(Y(n)) \leq |\cC(n)| \times 2^{-(h+2\eta) |F_n|} \leq 2^{-\eta |F_n|},
\]
we have that $\sum_{n=1}^\infty \mu(Y(n)) < \infty$, 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 $\bigcup \cC(n)$, hence \equ{eq: 
smb sup} is
established.

For the other direction, we show using Lemma~\ref{lem: vitsub} that
if for a set of positive measure of $x$'s,
\[
\varliminf_{n \to \infty} \frac{-\log(\mu(\cP^{F_n} (x)))}{|F_n|} < 
h(\cP) - 2\eta,
\]
then for any $\delta>0$, if $F$ is invariant enough,
there is a set $X'$ of measure $1 - \delta$
such that
 for any $x \in X'$ there is a collection ${\mathcal F}(x) = \{F_{n_i} 
a_i\}_{i \in I}$, satisfying the following conditions:
\begin{enumerate}
\item $n_i \geq \delta^{-1}$ and $F_{n_i} a_i \subset F$ for all $i$;
\item $\mu(\cP^{F_{n_i}} (a_i x)) > 2^{(h(\cP) - 2\eta) |F_{n_i}|}$;
\item
$ (1+\delta) \bigl | \bigcup_{i \in I} F_{n_i} a_i \bigr | \geq \sum_{i 
\in I} |F_{n_i} |
\geq (1-\delta)|F|.$
\end{enumerate}
One now simply counts the number of $\cP^F$-names needed to cover $X'$. 
This turns
out to be smaller than $2^{(h(\cP) - \eta) |F|}$ as long as $\delta$ is 
smaller
than some function of $\eta$.
Returning to the definition of entropy, we see that
\[
h(\cP) = \lim_{\epsilon \to 0} \varliminf_{n \to \infty} \frac{\log 
b(F_n, \epsilon, \cP)}{|F_n|}
 \leq h(\cP) - \eta,
\]
a contradiction.


\begin{thebibliography}{AA}
\bibitem{Cal53} A. P. Calderon, \textit{A 
general ergodic
theorem}, Annals of Mathematics \textbf{58} (1953), no. 1, 
182--191. \MR{14:1071a}

\bibitem{Em74} W. R. Emerson, \textit{The 
pointwise
ergodic theorem for amenable groups}, American Journal of Mathematics
\textbf{ 96} (1974), no. 3, 472--478. \MR{50:7403}

\bibitem{EG74} W. R. Emerson and 
F. P.
Greenleaf, \textit{Groups structure and the pointwise ergodic theorem 
for
connected amenable groups}, Advances in Math. \textbf{ 14} (1974), 
153--172. \MR{52:5867}

\bibitem{JR79} A. del Junco and
J. Rosenblatt, \textit{Counterexamples in ergodic theory and number 
theory},
Math. Ann. \textbf{ 245} (1979), 185--197. \MR{81d:10042}

\bibitem{OW83} D. Ornstein and B. 
Weiss,
\textit{The Shannon-McMillan-Breiman theorem for a class of amenable 
groups},
Israel Journal of Mathematics \textbf{ 44} (1983), no. 1, 53--60. 
\MR{85f:28018}

\bibitem{OW85} D.  
Ornstein and B. Weiss,
\textit{The Shannon-McMillan-Breiman theorem for countable partitions},
unpublished, c. 1985, 4 pages.

\bibitem{OW87} D. Ornstein and B. 
Weiss,
\textit{Entropy and isomorphism theorems  for actions of amenable 
groups},
Journal D'analyse Math\'ematique \textbf{ 48} (1987), 1--142. \MR{88j:28014}

\bibitem{Pat} A. Paterson,
\textit{Amenability}, Mathematical Surveys and Monographs, vol. \textbf{ 
29}, 
American Mathematical
Society, Providence, Rhode Island, 1988. \MR{90e:43001}

\bibitem{Rud} D. Rudolph,
\textit{Fundamentals of Measurable Dynamics --- Ergodic theory on 
Lebesgue spaces},
Oxford University Press, New York, 1990. \MR{92e:28006} 

\bibitem{Shu88} A. Shulman, \textit{Maximal 
ergodic theorems
on groups}, Dep. Lit. NIINTI, No. 2184, 1988.

\bibitem{Tem67} A. Tempelman, \textit{Ergodic
theorems for general dynamical systems}, Dokl. Akad. Nauk SSSR 
\textbf{176} (1967), no. 4,
790--793; English translation: Soviet Math. Dokl. 
\textbf{ 8} (1967), no. 5,
1213--1216. \MR{36:2779}

\bibitem{Tem} A. Tempelman, \textit{Ergodic 
theorems
for group actions, informational and thermodynamical aspects},
Kluwer Academic Publishers, Dordrecht, 1992. \MR{94f:22007}

\end{thebibliography}
\end{document}