2 Means

2.1 The space of means

Definition 2.1 Let $(E,N)$ be a Banach space. Its dual space is the space of all bounded linear maps $E\to \mathbf{R}$. It is a Banach space with the norm $N^*(\lambda)=\sup_{f\in E_1}|\lambda(f)|$ where $E_1$ is the unit closed ball of $E$.

The weak-$*$ topology is the coarsest topology on $E^*$ such that evaluation maps $\lambda\mapsto \lambda(f)$ are continuous for all $f\in E$. It is a topological vector space (i.e. addition and multiplication maps are continuous maps) that is locally convex: There is a basis of neighborhoods of 0 given by convex open subsets.

Let us recall a crucial fact for us.

Theorem 2.1 (Banach-Alaoglu theorem) Let $(E,N)$ be a Banach space then the unit ball of $E^*$ is weak-$*$ compact.

For a set $X$, we by $\ell^\infty(X)$ the Banach space of all bounded real functions on $X$ with the norm $||f||_\infty=\sup_{x\in X}|f(x)|$.

Definition 2.2 (mean) A mean on $X$ is an element $m$ of $\ell^\infty(X)^*$ such that

1. For any non-negative bounded function $f$ on $X$, $m(f)\geq0$,
2. $m(1_X)=1$.

We define $M(X)$ to be the set of all means on $X$.

Any finitely supported probability yields an element of $M(X)$, we denote them by $\mathrm{Prob}_{f}(X)$. This space is exactly the space of finite combinations of Dirac masses. More generally, any countably supported probability measure on $X$ yields a mean.

Theorem 2.2 We have the following properties

1. For any $m\in M(X)$, $||m||=1$
2. The space of means $M(X)$ is a convex weak-* compact subset of $\ell^\infty(X)^*$
3. The space $\mathrm{Prob}_{f}(X)$ is weak-* dense in $M(X)$.

Proof. Let us observe that the first condition implies that if $f\leq g$ then $m(f)\leq m(g)$ since $g-f\geq 0$ and $m$ is linear.

1. For any $f\in\ell^\infty(X)$, $f\leq||f||_\infty \mathbf{1}_X$ and thus $m(f)\leq ||f||_\infty m(\mathbf{1}_X)=||f||_\infty$. So $||m||\leq 1$ and since $m(\mathbf{1}_X)=1$, $||m||=1$.
2. The two conditions defining means are convex and closed. Thus the set of means is an infinite intersections of closed convex subsets so it is closed and convex. By the first point it is a part of the unit ball and by Banach Alaoglu theorem, this is a closed subset of a compact Hausdorff space so it is compact.
3. Assume that $\mathrm{Prob}_{f}(X)$ is not weak-* dense in $M(X)$ then there is $m_0\in M(X) \setminus \overline{\mathrm{Prob}_{f}(X)}$ , so there is $f\in\ell^\infty(X)$ non-negative such that $\max_{m\in\mathrm{Prob}_{f}(X)} m(f)<m_0(f)$ (Hahn-Banach theorem). Let $\mu$ be this maximum, we have in particular, for $m=\delta_x$ and for $x\in X$ that $f(x)\leq\mu<m_0(f)$. So $||f||_\infty<m_0(f)$ and we have a contradiction.

To any mean $m$ on $X$, one can associate a finitely additive probability measure $\hat{m}$ in the following way:

$$\hat{m}(A)=m(\mathbf{1}_A).$$

Theorem 2.3 The map $m\mapsto \hat{m}$ is a bijection between means and finitely additive probability measures.

Proof. Let us prove injectivity first. The space of bounded functions with finite image is dense in $\ell^\infty(X)$. So since means are 1-Lipschitz on $\ell^\infty(X)$, it suffices to prove that if $\hat{m_1}=\hat{m_2}$ then $m_1(f)=m_2(f)$ for all functions $f$ with finite image. Such a function can be written $f=\sum_{i=1}^n\lambda_i\mathbf{1}_{X_i}$ where $\lambda_i\in \mathbf{R}$ and $(X_i)$ is a partition of $X$.

So if $m$ is a mean $m(f)=\sum_{i=1}^n\lambda_i\hat{m}(X_i)$ and thus if $\hat{m_1}=\hat{m_2}$ then they coincide on finite image functions.

Let’s prove that the map is surjective. If $\mu$ is a finitely additive probability measure, for functions with finite image $f=\sum_{i=1}^n\lambda_i\mathbf{1}_{X_i}$, we define $\overline{\mu}(f)=\sum_{i=1}^n\lambda_i\mu(X_i)$. With this definition, $|\overline{\mu}(f)|\leq ||f||_\infty$. Thus $\overline{\mu}$ can be extended by uniform continuity to $\ell^\infty(X)$. Moreover, for all non-negative finite image function $f$, $\overline{\mu}(f)\geq0$, thus this holds for all non-negative bounded functions. The condition $\overline{\mu}(\mathbf{1}_X)=\mu(X)=1$ holds by construction.

2.2 Amenable groups

Let $G$ be a group acting on a space $X$. The group acts on $\ell^\infty(X)$ via the following formula:

$$\forall f\in \ell^\infty(X), x\in X, g\in G,\ (g\cdot f)(x)=f(g^{-1}x).$$

In particular, for $f=\mathbf{1}_A$, we have:

$$g\mathbf{1}_A=\mathbf{1}_{gA}.$$

Actually, $g\mathbf{1}_A(x)=\mathbf{1}_A(g^{-1}x)=1\iff g^{-1}x\in A\iff x\in gA.$

This defines a left action on $\ell^\infty(X)$ by linear maps that preserve the norm. Associated to this action, there is an action on the dual $\ell^\infty(X)^*$:

$$\forall \lambda\in \ell^\infty(X)^*, f\in \ell^\infty(X), g\in G,\ (g\cdot\lambda)(f)=\lambda(g^{-1}\cdot f).$$ The action on $\ell^\infty(X)$ preserves non-negative functions and constant functions are invariant. So the induced action on $\ell^\infty(X)^*$ let invariant the space of means. Let us see what it does mean for means and finitely additive probability measures.

Let $m$ be a mean, $g\in G$ and $A\subset X$,

$$\begin{align} \widehat{gm}(A)&=gm(\mathbf{1}_A)\\ &=m(g^{-1}\mathbf{1}_A)\\ &=m(\mathbf{1}_{g^{-1}A})\\ &=\hat{m}(g^{-1}A)\\ \end{align}$$

This means that the action on finitely additive probabilities satisfies the following formula:

$$g\hat{m}(A)=\hat{m}(g^{-1}A).$$ A mean $m$ is said to be invariant if for any $g\in G$, $gm=m$.

With the correspondence between means and finitely additive probability measures, we have the following alternative definition for amenability of groups.

Definition 2.3 A group $G$ is amenable if there is a invariant mean on $G$ for its action by left multiplications on itself.

Example 2.1 The group $\mathbf{Z}$ is amenable.

Proof. Let $\mu$ be a cluster point of the sequence $\mu_n=\frac{1}{2n+1}\sum_{i=-n}^n\delta_i$ in $M(\mathbf{Z})$. Since for any bounded function $f$ on $\mathbf{Z}$, we have $|1\cdot\mu_n(f)-\mu_n(f)|\leq|f(n+1)-f(-n)|/(2n+1)\to0$, $1\cdot\mu=\mu$ and it follows that $k\cdot\mu=\mu$ for any $k\in\mathbf{Z}$.

Let us see a few equivalent definitions of amenability. Below we denote by $\mathrm{Prob}(G)$ the set of countably supported probability measures on $G$ (with respect to the $\sigma$-algebra of all subsets of $G$).

Remark. Any element of $\mathrm{Prob}(G)$ can be written $\mu=\sum_{i\in\mathbf{N}}\lambda_i\delta_{g_i}$ where $g_i\in G$, $\lambda_i\geq0$ and $\sum_{i\in\mathbf{N}}\lambda_i=1$. In particular, it can identified with a subset of the unit ball of $\ell^1(G)$. If $G$ is countable then $\mathrm{Prob}(G)$ is exactly the set of probability measures on $G$ but if $G$ is not countable then $\mathrm{Prob}(G)$ is not the set of all probability measures on $G$.

Definition 2.4 (Reiter's condition) A group $G$ satisfies Reiter’s condition if for any finite subset $E\subset G$ and $\varepsilon >0$, there is $\mu\in\mathrm{Prob}(G)$ such that $||g\mu-\mu||_1<\varepsilon$ for any $g\in E$.

Definition 2.5 (Følner's condition) A group $G$ satisfies Følner’s condition if for any finite subset $E\subset G$ and $\varepsilon >0$, there is a finite subset $F$ such that for all $g\in E$.

$$|gF\Delta F|<\varepsilon |F|.$$

Theorem 2.4 Let $G$ be a group. The following are equivalent.

1. The group $G$ is amenable.
2. The group $G$ satisfies Reiter’s condition.
3. The group $G$ satisfies Følner’s condition.

Proof. Let us prove that amenability implies Reiter’s condition. So, assume $G$ is amenable. There is an invariant mean $m$ on $G$. Since finitely supported probability measures are dense in $M(G)$ for the weak-* topology, we can find a net $\mu_i\in\mathrm{Prob}_{f}(G)$ converging to $m$. This means that for any $f\in\ell^\infty(G)$, $\mu_i(f)\to m(f)$ (this is the weak-* convergence). For $g\in G$, $g\mu_i(f)=\mu_i(g^{-1}f)$ and thus $g\mu_i$ converges to $gm$ as well. In particular, $g\mu_i-\mu_i$ converges to 0 for the weak topology of $\ell^1(G)$. For a finite set $E$, consider the space $$\left\{\oplus_{s\in E}s\mu-\mu,\ \mu\in\mathrm{Prob}(G)\right\}\subset\oplus_{s\in E}\ell^1(G).$$

This is convex subspace whose weak closure contains 0 (The direct sum $\oplus_{s\in E}\ell^1(G)$ is endowed with the product topology of the norm topology, its dual is $\oplus_{s\in E}\ell^\infty(G))$ and its weak topology is the product of the weak topologies on each copy of $\ell^1(G)$). But a convex subspace is weakly closed if and only if it is strongly closed (consequence of Hahn-Banach separation theorem). So the strong closure of the space above also contains $0$ and thus, for any $\varepsilon>0$, one can find $\mu\in\mathrm{Prob}(G)$ such that $||s\mu-\mu||_1<\varepsilon$ for all $s\in E$.

Let’s prove that Reiter’s condition implies Følner’s condition. For a finite subset $E\subset G$ and $\varepsilon>0$, let $\mu\in\mathrm{Prob}(G)$ given by Reiter’s condition. For $f\in\ell^1(G)$ and $r\geq0$, let $F(f,r)=\{t\in G,\ f(t)>r\}$ (an upper level subset of $f$). For non-negative functions $f,h\in\ell^1(G)$ with norm 1, we have $|\mathbf{1}_{F(f,r)(t)} − \mathbf{1}_{F(h,r)(t)}| = 1$ if and only if $f(t)\leq r\leq h(t)$ or $h(t) \leq r \leq f(t)$. Hence for two functions bounded above by 1 we have

$$|f(t)-h(t)|=\int_0^1\left|\mathbf{1}_{F(f,r)(t)} − \mathbf{1}_{F(h,r)(t)}\right|dr.$$ In particular, for $s\in E$ and $\mu\in\mathrm{Prob}(G)$.

$$\begin{align*} ||s\mu-\mu||_1&=\sum_{t\in G}|s\mu(t)-\mu(t)|\\ &=\sum_{t\in G}\int_0^1\left|\mathbf{1}_{F(s\mu,r)(t)} − \mathbf{1}_{F(\mu,r)(t)}\right|dr\\ &=\int_0^1\sum_{t\in G}\left|\mathbf{1}_{F(s\mu,r)(t)} − \mathbf{1}_{F(\mu,r)(t)}\right|dr\\ &=\int_0^1\left|sF(\mu,r)\Delta F(\mu,r)\right|dr \end{align*}$$

So, by the condition satisfied by $\mu$ and summing over all elements of $E$,

$$\begin{align*} \int_0^1\sum_{s\in E}\left|sF(\mu,r)\Delta F(\mu,r)\right|dr &\leq \varepsilon|E|\\ &=\varepsilon|E|\sum_{t\in G}\mu(t)\\ &=\varepsilon|E|\sum_{t\in G}\int_0^{\mu(t)}1dr\\ &=\varepsilon|E|\int_0^{1}\left|\{t\in G,\ \mu(t)>r\}\right|dr\\ &=\varepsilon|E|\int_0^{1}\left|F(\mu,r)\right|dr\\ \end{align*}$$

In particular, there is an $r>0$ such that $\sum_{s\in E}\left|sF(\mu,r)\Delta F(\mu,r)\right|\leq\varepsilon|E|\left|F(\mu,r)\right|$ and we have the Følner’s condition.

Let’s prove that the Følner’s condition implies amenability. Let $E$ be a finite set and $\varepsilon>0$. We can find an finite subset $F=F_{E,\varepsilon}$ (depending on $E$ and $\varepsilon$) such that $|gF\Delta F|\leq \varepsilon |F|$ for any $g\in E$. Let us define $\mu_F$ be $\sum_{g\in F}\frac{\delta_g}{|F|}\in \mathrm{Prob}(G)$. We have

$$||s\mu_F-\mu_F||_1\leq \varepsilon.$$

Take a cluster point of the net $\mu_{F_{E,\varepsilon}}$ (where finite subsets are ordered by inclusion) in $M(G)$. This yields an invariant mean.

2.3 The growth function of a finitely generated group

Let $G$ be a group generated by a finite set $S$.The word metric associated to $S$ is the metric $d_S$ defined by $d_S(g,g')$ is the minimal of a word in $S$ representing $g^{-1}g'$. This metric is invariant under left multiplication and it correspond this the length metric in the Cayley graph associated to $S$.

Definition 2.6 The growth function of $G$ associated to $S$ is the function $f\colon \mathbf{N}\to\mathbf{R}$ given by

$$f(n)=|B_S(e,n)|$$

where $B_S(e,n)$ is the closed ball of radius $n$ around the identity $e$ in the Cayley graph of $G$ associated to $S$.

Remark. One has $f(n)\leq(2|S|+1)^n$ since there are at most $k^n$ distinct words of length $n$ on an alphabet with $k$ letters.

Let us see that this growth function is coarsely independent of $S$.

Definition 2.7 Let $(X,d)$ and $(Y,d)$ be two metric spaces and $f\colon X\to Y$. Let $(\lambda,C)\in \mathbf{R}_+^2$. The function $f$ is said to be a $(\lambda,C)$-quasi-isometric embedding if for any $x,x'\in X$,

$$1/\lambda d(f(x),f(x'))-C\leq d(x,x')\leq \lambda d(f(x),f(x'))+C.$$ The function $f$ is said to be a quasi-isometric embedding if there exists $(\lambda,C)\in \mathbf{R}_+^2$ such that $f$ is a $(\lambda,C)$-quasi-isometric embedding.

The function $f$ is a $(\lambda,C, M)$-quasi-isometry if it is a $(\lambda,C)$-quasi isometric embedding and for any $y\in Y$, there is $x\in X$ such that $d(y,f(x))\leq M$. Finally, $f$ is said to be a quasi-isometry if there is $(\lambda,C, M)\in \mathbf{R}_+^3$ such that $f$ is a $(\lambda,C, M)$-quasi-isometry.

Proposition 2.1 Let $G$ be a group with two finite generating sets $S,S'$. Then the identity map $G\to G$ is a quasi-isometry between vertices of $\mathcal{G}(G,S)$ and $\mathcal{G}(G,S')$.

Proof. Let $m$ be the maximum of length of an element of $S$ for the word distance associated to $S'$. So, if $g=s_1...s_n$ where each element $S_i\in S^{\pm1}$ then by replacing each $s_i$ by a product of elements of $S'^{\pm1}$ of length at most $m$, we get that

$$|g|_S\leq m|g|_{S'}.$$ Permuting the role of $S$ and $S'$, we get $|g|_{S'}\leq m'|g|_{S}$ for some $m'$ and thus the identity is a quasi-isometry.

Definition 2.8 Let $G$ be a group generated by a set $S$ and let $f$ the associated growth function.

1. $G$ has polynomial growth of degree at most $k$ if $f(n)=O(n^k)$.
2. $G$ has exponential growth if $\limsup f(n)^{1/n}>1$.
3. $G$ has sub-exponential growth if $\limsup f(n)^{1/n}=1$.
4. $G$ has intermediate growth if it is neither of polynomial growth or of exponential growth.

Remark. Polynomial growth, exponential growth and sub-exponential growth does not depend on the choice of the finite generating set.

Example 2.2 The groups $\mathbf{Z}^k$ with its standard generating set $(1,0\dots,0),\dots,(0,\dots,0,1)$ has polynomial growth at most $k$. The free group $\mathbf{F}_k$ has exponential growth with exponent $2^k-1$ for its standard generating set.

Theorem 2.5 A finitely generated group $G$ with sub-exponential growth is amenable.

Proof. Let fix a finite symmetric generating set $S$ for $G$ and let us denote by $B(n)$ the ball of radius $n$ for the word metric on $G$.

We prove that $G$ satisfies Følner’s condition for $E=S$ (which is sufficient because any finite set can be included in some finite generating set).

We know that $\limsup |B(n)|^{1/n}=1$ and thus for any $\varepsilon>0$, for all $N$ there is $n>N$

$$|B(n+1)|/|B(n)|<1+\varepsilon.$$

Now, $$\frac{|sB(n)\setminus B(n)|}{|B(n)|}\leq \frac{|B(n+1)\setminus B(n)|}{|B(n)|}<\varepsilon.$$

so $$\frac{|sB(n)\Delta B(n)|}{|B(n)|}<2\varepsilon.$$

Theorem 2.6 Finitely generated abelian groups have polynomial growth

Proof. Let $G$ be a finitely generated abelian group with $n$ generators. The ball of radius $k\in\mathbf{N}$ has at most $(2k+1)^n$ elements and thus, it has polynomial growth.

Corollary 2.1 All finitely generated abelian groups are amenable.

Theorem 2.7 Finitely generated nilpotent groups have polynomial growth.

Proof. A group $G$ is nilpotent if there is a sequence of subgroup $G_0,G_1,G_2,\dots,G_n$ such that $G_0=G$, $G_{i+1}=[G,G_{i}]$ (which is normal in $G_{i}$ and $G_{i+1}/G_i$ is abelian) and $G_n=\{1\}$. Assume we know that $G_1=G'$ is finitely generated (see Exercice below). Arguing by induction, it suffices to prove that if $G$ is a finitely generated group with a normal finitely generated subgroup $N$ with polynomial growth and $G/N$ is abelian then $G$ has polynomial growth. Let $q_1,\dots,q_k$ generators for $G/N$ with preimages $g_1,\dots,g_k$ in $G$. Let $g\in G$ and $\pi(g)$ its image in $G/N$, we have $\pi(g)=t_1^{\alpha_1}\dots t_k^{\alpha_k}$ since $G/N$ is abelian. So $g$ can be written $g_1^{\alpha_1}\dots g_k^{\alpha_k}n$ with $n\in N$. Let $n_1,\dots,n_m$ be generators for $N$. Let $S=\{g_1,\dots, g_k,n_1,\dots,n_m\}$. This is a finite generating set of $G$. For the word distance associated $|\ |_S$ to this system, $|g|_S=(\sum|\alpha_i|)+|n|_S$, in particular if the ball $B_N(r)$ in $N$ has size bounded by $P(r)$ for some polynomial $P$ then $B_G(r)\leq (2r+1)^nP(r)$ and thus the growth is polynomial.

Remark. It is not true in general that the commutator subgroup of a finitely generated group is finitely generated.

Corollary 2.2 Finitely generated nilpotent groups are amenable.

2.4 Exercises

Exercise 2.1 Prove that a group $G$ is amenable if and only if there is a right invariant mean on $G$.

Exercise 2.2 Let $X$ be an uncountable set and $\mathcal{A}$ be the $\sigma$-algebra generated by countable subsets.

1. Prove that any element of $\mathcal{A}$ is either countable or co-countable (i.e. its complement is countable).
2. We define $m(A)=0$ if $A$ is a countable subset of $X$ and $m(A)=1$ if $A$ is co-countable. Prove that $m$ is a probability measure on $\mathcal{A}$.

Exercise 2.3 Prove that the group of affine transformations of the real line is amenable.

Exercise 2.4 Let $G$ be a group. For an orthogonal representation of $G$, $\pi\colon G\to \mathcal{O}(\mathcal{H})$ where $\mathcal{H}$ is a Hilbert space, we say that $\pi$ almost has invariant vectors if for all $\varepsilon >0$ and $F\subset G$ finite, there is a unitary vector $v\in\mathcal{H}$ such that $||\pi(g)(v)-v||<\varepsilon$.

The Koopman representation $\pi\colon G\to\mathcal{O}(\ell^2(G))$ is given by $\pi(g)(f)(h)=f(g^{-1}h)$ for $g,h\in G$ and $f\in\ell^2(G)$. Prove that a group $G$ is amenable if and only there is an almost invariant vector in $\ell^2(G)$ for this Koopman representation.

Exercise 2.5 A group $G$ has Kazhdan Property (T), if there is $\varepsilon>0$ such that for any unitary representation $\pi\colon G\to U(\mathcal{H})$ without invariant unit vector, for any unit vector $v\in \mathcal{H}$, $|\pi(g)(v)-v|>\varepsilon$.

Prove that an amenable group with Kazhdan property (T) is finite. (Hint: use the previous exercise)

Exercise 2.6 Prove that any two regular trees (i.e. trees with finite constant valency at least 3) are quasi-isometric. Deduce that any two free groups on $n,m\geq2$ generators are quasi-isometric.

Exercise 2.7 Prove that the growth type (bounded, polynomial, sub-exponential, exponential) of a finitely generated group does not depend on the choice of a finite generating system.

Exercise 2.8 Let $G$ be a finitely generated nilpotent group. The goal of this exercise is to prove that its commutator subgroup $G'=[G,G]$ is finitely generated. Let $S$ be a finite generating set of $G$.

1. Prove that any commutator can be written as a product of iterated commutators $[\dots[[s_1,s_2],s_3],\dots,s_n]$ with $s_i\in S$. (Hint: use iteratively the relation $xy=yx[x^{-1},y^{-1}]$).
2. Prove that there is a finite quantity of such iterated commutators of elements of $S$.
3. Conclude that $G'$ is finitely generated.

Exercise 2.9 Let $G$ be group. We say that $G$ is virtually something if there is a subgroup $H\leq G$ of finite index such $H$ is something (replace something by some adjective for groups).

1. Prove that a finite index subgroup $H$ of a finitely generated group $G$ is finitely generated.
2. Prove that if $G$ has a finite index subgroup then it has a normal finite index subgroup.
3. Prove that if $G$ is finitely generated and $H$ is a finite index subgroup then there are finite generating sets $S_G$ and $S_H$ of $G$ and $H$ such that $G$ and $H$ are quasi-isometric for the induced word metrics.
4. Prove that a finite index subgroup of a finitely generated group of polynomial growth is of polynomial growth as well.
5. More generally prove that the growth type of two quasi-isometric groups (for some word length associated to two finite generating sets) is the same. We say that the growth is an invariant of quasi-isometry.