Recently, I have been studying the concept of amenability on groups. This concept can be defined in a “combinatorial” or “finitary” fashion, using Følner sequences, and also in a more “functional-analytic” or “infinitary”‘ fashion, using invariant means. I wanted to get some practice passing back and forth between these two definitions, so I wrote down some notes on how to do this, and also how to take some facts about amenability that are usually proven in one setting, and prove them instead in the other. These notes are thus mostly for my own benefit, but I thought I might post them here also, in case anyone else is interested.

— 1. Equivalent definitions of amenability —

For simplicity I will restrict attention to countable groups ${G}$. Given any ${f: G \rightarrow {\mathbb R}}$ and ${x \in G}$, I define the left-translation ${\tau_x f: G \rightarrow {\mathbb R}}$ by the formula ${\tau_x f(y) := f(x^{-1} y)}$. Given ${g: G \rightarrow {\mathbb R}}$ as well, I define the inner product ${\langle f, g \rangle := \sum_{x \in G} f(x) g(x)}$ whenever the right-hand side is convergent.

All ${\ell^p}$ spaces are real-valued. The cardinality of a finite set ${A}$ is denoted ${|A|}$. The symmetric difference of two sets ${A, B}$ is denoted ${A \Delta B}$.

A finite mean is a non-negative, finitely supported function ${\mu: G \rightarrow {\mathbb R}^+}$ such that ${\| \mu \|_{\ell^1(G)}=1}$. A mean is a non-negative linear functional ${\lambda: \ell^\infty(G) \rightarrow {\mathbb R}}$ such that ${\lambda(1)=1}$. Note that every finite mean ${\mu}$ can be viewed as a mean ${\lambda_\mu}$ by the formula ${\lambda_\mu(f) := \langle f, \mu \rangle}$.

The following equivalences were established by Følner:

Theorem 1 Let ${G}$ be a countable group. Then the following are equivalent:

• (i) There exists a left-invariant mean ${\lambda: \ell^\infty(G) \rightarrow {\mathbb R}}$, i.e. mean such that ${\lambda(\tau_x f) = \lambda(f)}$ for all ${f \in \ell^\infty(G)}$ and ${x \in G}$.
• (ii) For every finite set ${S \subset G}$ and every ${\epsilon > 0}$, there exists a finite mean ${\nu}$ such that ${\| \nu - \tau_x \nu\|_{\ell^1(G)} \leq \epsilon}$ for all ${x \in S}$.
• (iii) For every finite set ${S \subset G}$ and every ${\epsilon > 0}$, there exists a non-empty finite set ${A \subset G}$ such that ${|(x \cdot A) \Delta A|/|A| \leq \epsilon}$ for all ${x \in S}$.
• (iv) There exists a sequence ${A_n}$ of non-empty finite sets such that ${|x \cdot A_n \Delta A_n| / |A_n| \rightarrow 0}$ as ${n \rightarrow \infty}$ for each ${x \in G}$. (Such a sequence is called a Følner sequence.)

Proof: We shall use an argument of Namioka.

(i) implies (ii): Suppose for contradiction that (ii) failed, then there exists ${S, \epsilon}$ such that ${\sup_{x \in S} \| \nu - \tau_x \nu\|_{\ell^1(G)} > \epsilon}$ for all means ${\nu}$. The set ${\{ (\nu - \tau_x \nu)_{x \in S}: \nu \in \ell^1(G) \}}$ is then a convex set of ${(\ell^1(G))^S}$ that is bounded away from zero. Applying the Hahn-Banach separation theorem, there thus exists a linear functional ${\rho \in (\ell^1(G)^S)^*}$ such that ${\rho((\nu-\tau_x \nu)_{x \in S}) \geq 1}$ for all means ${\nu}$. Since ${(\ell^1(G)^S)^* \equiv \ell^\infty(G)^S}$, there thus exist ${m_x \in \ell^\infty(G)}$ for ${x \in S}$ such that ${\sum_{x \in S} \langle \nu - \delta_x*\nu, m_x \rangle \geq 1}$ for all means ${\nu}$, thus ${\langle \nu, \sum_{x \in S} m_x - \tau_{x^{-1}} m_x \rangle \geq 1}$. Specialising ${\nu}$ to the Kronecker means ${\delta_y}$ we see that ${\sum_{x \in S} m_x-\tau_{x^{-1}} m_x \geq 1}$ pointwise. Applying the mean ${\lambda}$, we conclude that ${\sum_{x \in S} \lambda(m_x)-\lambda(\tau_{x^{-1}} m_x) \geq 1}$. But this contradicts the left-invariance of ${\lambda}$.

(ii) implies (iii): Fix ${S}$ (which we can take to be non-empty), and let ${\epsilon > 0}$ be a small quantity to be chosen later. By (ii) we can find a finite mean ${\nu}$ such that

$\displaystyle \| \nu - \tau_x \nu\|_{\ell^1(G)} < \epsilon/|S|$

for all ${x \in S}$.

Using the layer-cake decomposition, we can write ${\nu = \sum_{i=1}^k c_i 1_{E_i}}$ for some nested non-empty sets ${E_1 \supset E_2 \supset \ldots \supset E_k}$ and some positive constants ${c_i}$. As ${\nu}$ is a mean, we have ${\sum_{i=1}^k c_i |E_i| = 1}$. On the other hand, observe that ${|\nu - \tau_x \nu|}$ is at least ${c_i}$ on ${(x \cdot E_i) \Delta E_i}$. We conclude that

$\displaystyle \sum_{i=1}^k c_i |(x \cdot E_i) \Delta E_i| \leq \frac{\epsilon}{|S|} \sum_{i=1}^k c_i |E_i|$

for all ${x \in S}$, and thus

$\displaystyle \sum_{i=1}^k c_i \sum_{x \in S} |(x \cdot E_i) \Delta E_i| \leq \epsilon \sum_{i=1}^k c_i |E_i|.$

By the pigeonhole principle, there thus exists ${i}$ such that

$\displaystyle \sum_{x \in S} |(x \cdot E_i) \Delta E_i| \leq \epsilon |E_i|$

and the claim follows.

(iii) implies (iv): Write the countable group ${G}$ as the increasing union of finite sets ${S_n}$ and apply (iii) with ${\epsilon := 1/n}$ and ${S := S_n}$ to create the set ${A_n}$.

(iv) implies (i): Use the Hahn-Banach theorem to select an infinite mean ${\rho \in \ell^\infty({\mathbb N})^* \backslash \ell^1({\mathbb N})}$, and define ${\lambda( m ) = \rho( ( \langle m, \frac{1}{|A_n|} 1_{A_n} \rangle )_{n \in {\mathbb N}} )}$. (Alternatively, one can define ${\lambda(m)}$ to be an ultralimit of the ${\langle m, \frac{1}{|A_n|} 1_{A_n} \rangle}$.) $\Box$

Any countable group obeying any (and hence all) of (i)-(iv) is called amenable.

Remark 1 The above equivalences are proven in a non-constructive manner, due to the use of the Hahn-Banach theorem (as well as the contradiction argument). Thus, for instance, it is not immediately obvious how to convert an invariant mean into a Følner sequence, despite the above equivalences.

— 2. Examples of amenable groups —

We give some model examples of amenable and non-amenable groups:

Proposition 2 Every finite group is amenable.

Proof: Trivial (either using invariant means or Følner sequences). $\Box$

Proposition 3 The integers ${{\mathbb Z} = ({\mathbb Z},+)}$ are are amenable.

Proof: One can take the sets ${A_N = \{1,\ldots,N\}}$ as the Følner sequence, or an ultralimit as an invariant mean. $\Box$

Proposition 4 The free group ${F_2}$ on two generators ${e_1,e_2}$ is not amenable.

Proof: We first argue using invariant means. Suppose for contradiction that one had an invariant mean ${\lambda}$. Let ${E_1, E_2, E_{-1}, E_{-2} \subset F_2}$ be the set of all words beginning with ${e_1}$, ${e_2}$, ${e_1^{-1}, e_2^{-1}}$ respectively. Observe that ${E_2 \subset (e_1^{-1} \cdot E_1) \backslash E_1}$, thus ${\lambda(1_{E_2}) \leq \lambda(\tau_{e_1^{-1}} 1_{E_1}) - \lambda( 1_{E_1} )}$. By invariance we conclude that ${\lambda(1_{E_2}) = 0}$; similarly for ${1_{E_1}}$, ${1_{E_{-1}}}$, ${1_{E_{-2}}}$. Since the identity element clearly must have mean zero, we conclude that the mean ${\lambda}$ is identically zero, which is absurd.

Now we argue using Følner sequences. If ${F_2}$ were amenable, then for any ${\epsilon > 0}$ we could find a finite non-empty set ${A}$ such that ${x \cdot A}$ differs from ${A}$ by at most ${\epsilon |A|}$ points for ${x = e_1, e_2, e_1^{-1}, e_2^{-1}}$. The set ${e_1 \cdot (A \cap (E_2 \cup E_{-1} \cup E_{-2}))}$ is contained in ${e_1 \cdot A}$ and in ${E_1}$, and so

$\displaystyle |e_1 \cdot (A \backslash E_{-1})| \leq |A \cap E_1| + \epsilon |A|,$

and thus

$\displaystyle |A| - |A \cap E_{-1}| \leq |A \cap E_1| + \epsilon |A|.$

Similarly for permutations. Summing up over all four permutations, we obtain

$\displaystyle 4|A| - |A| \leq |A| + 4 \epsilon |A|,$

leading to a contradiction for ${\epsilon}$ small enough (any ${\epsilon < 1/2}$ will do). $\Box$

Remark 2 The non-amenability of the free group is related to the Banach-Tarski paradox (see my earlier lecture notes on this).

Now we generate some more amenable groups.

Proposition 5 Let ${0 \rightarrow H \rightarrow G \rightarrow K \rightarrow 0}$ be a short exact sequence of countable groups (thus ${H}$ can be identified with a normal subgroup of ${G}$, and ${K}$ can be identified with ${G/H}$). If ${H}$ and ${K}$ are amenable, then ${G}$ is amenable also.

Proof: Using invariant means, there is a very short proof: given invariant means ${\lambda_H}$, ${\lambda_K}$ for ${H, K}$, we can build an invariant mean ${\lambda_G}$ for ${G}$ by the formula

$\displaystyle \lambda_G(f) := \lambda_K( F )$

for any ${f \in \ell^\infty(G)}$, where ${F: K \rightarrow {\mathbb R}}$ is the function defined as ${F(xH) := \lambda_H( f(x \cdot) )}$ for all cosets ${xH}$ (note that the left-invariance of ${\lambda_H}$ shows that the exact choice of coset representative ${x}$ is irrelevant). (One can view ${\lambda_G}$ as sort of a “product measure” of the ${\lambda_H}$ and ${\lambda_K}$.)

Now we argue using Følner sequences instead. Let ${E_n}$, ${F_n}$ be Følner sequences for ${H, K}$ respectively. Let ${S}$ be a finite subset of ${G}$, and let ${\epsilon > 0}$. We would like to find a finite non-empty subset ${A \subset G}$ such that ${|(x \cdot A) \backslash A| \leq \epsilon |A|}$ for all ${x \in S}$; this will demonstrate amenability. (Note that by taking ${S}$ to be symmetric, we can replace ${|(x \cdot A) \backslash A|}$ with ${|(x \cdot A) \Delta A|}$ without difficulty.)

By taking ${n}$ large enough, we can find ${F_n}$ such that ${\pi(x) \cdot F_n}$ differs from ${F_n}$ by at most ${\epsilon |F_n|/2}$ elements for all ${x \in S}$, where ${\pi: G \rightarrow K}$ is the projection map. Now, let ${F'_n}$ be a preimage of ${F_n}$ in ${G}$. Let ${T}$ be the set of all group elements ${t \in H}$ such that ${S \cdot F'_n}$ intersects ${F'_n \cdot t}$. Observe that ${T}$ is finite. Thus, by taking ${m}$ large enough, we can find ${E_m}$ such that ${t \cdot E_m}$ differs from ${E_m}$ by at most ${\epsilon |E_m|/2|T|}$ points for all ${t \in T}$.

Now set ${A := F'_n \cdot E_m = \{ zy: y \in E_m, z \in F'_n \}}$. Observe that the sets ${z \cdot E_m}$ for ${z \in F'_n}$ lie in disjoint cosets of ${H}$ and so ${|A| = |E_m| |F'_n| = |E_m| |F_n|}$. Now take ${x \in S}$, and consider an element of ${(x \cdot A) \backslash A}$. This element must take the form ${xzy}$ for some ${y \in E_m}$ and ${z \in F'_n}$. The coset of ${H}$ that ${xzy}$ lies in is given by ${\pi(x) \pi(z)}$. Suppose first that ${\pi(x) \pi(z)}$ lies outside of ${F_n}$. By construction, this occurs for at most ${\epsilon |F_n|/2}$ choices of ${z}$, leading to at most ${\epsilon |E_m| |F_n|/2 = \epsilon |A|/2}$ elements in ${(x \cdot A) \backslash A}$.

Now suppose instead that ${\pi(x) \pi(z)}$ lies in ${F_n}$. Then we have ${xz = z' t}$ for some ${z' \in F'_n}$ and ${t \in T}$, by construction of ${T}$, and so ${xzy = z'ty}$. But as ${xzy}$ lies outside of ${A}$, ${ty}$ must lie outside of ${E_m}$. But by construction of ${E_m}$, there are at most ${\epsilon |E_m|/2|T|}$ possible choices of ${y}$ that do this for each fixed ${x, t}$, leading to at most ${\epsilon |E_m| |F_n|/2 = \epsilon |A|/2}$. We thus have ${|(x \cdot A) \backslash A| \leq \epsilon |A|}$ as required. $\Box$

Proposition 6 Let ${G_1 \subset G_2 \subset \ldots}$ be a sequence of countable amenable groups. Then ${G := \bigcup_n G_n}$ is amenable.

Proof: We first use invariant means. An invariant mean on ${\ell^\infty(G_n)}$ induces a mean on ${\ell^\infty(G)}$ which is invariant with respect to translations by ${G_n}$. Taking an ultralimit of these means, we obtain the claim.

Now we use Følner sequences. Given any finite set ${S \subset G}$ and ${\epsilon > 0}$, we have ${S \subset G_n}$ for some ${n}$. As ${G_n}$ is amenable, we can find ${A \subset G_n}$ such that ${|(x \cdot A) \Delta A| \leq \epsilon |A|}$ for all ${x \in S}$, and the claim follows. $\Box$

Proposition 7 Every countable virtually solvable group ${G}$ is amenable.

Proof: Every virtually solvable group contains a solvable group of finite index, and thus contains a normal solvable subgroup of finite index. (Note that every subgroup ${H}$ of ${G}$ of index ${I}$ contains a normal subgroup of index at most ${I!}$, namely the stabiliser of the ${G}$ action on ${G/H}$.) By Proposition 5 and Proposition 2, we may thus reduce to the case when ${G}$ is solvable. By inducting on the derived length of this solvable group using Proposition 5 again, it suffices to verify this when the group is abelian. By Proposition 6, it suffices to verify this when the group is abelian and finitely generated. By Proposition 5 again, it suffices to verify this when the group is cyclic. But this follows from Proposition 2 and Proposition 3. $\Box$