The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.

**Title**: Ergodic theory and amenable groups

**Lecturer**: Benjamin Weiss

**Date**: October 31, 2016.

**Main Topics**: Three equivalent notions of amenability, Basic concepts in ergodic actions, Furstenberg’s Ergodic proof of Szemerédi’s theorem

**Definitions:** Ergodic action, weak mixing, mixing, Banach limit, amenable group, left invariant mean, paradoxical decomposition, Følner sequence

## Introduction

Our presentation will go in reverse order that Benji Weiss presented. This is mostly to highlight the presentation of amenable groups, which is independent from ergodic actions. The punchline is that the tools of ergodic theory apply in amenable groups.

In the first half we present three equivalent definitions of amenable group. In the second half we look at basic concepts, theorem and equivalences in ergodic theory.

## Amenable groups

We will present three equivalent definitions of an amenable group and then show their equivalence.

### Almost invariance, Følner’s condition

We start with a practical definition that captures the asymptotic invariance of a group’s action.

**Definition 1 (Følner 1955)**. Let be a discrete countable group.

For define the pointwise product . Recall , and we use . The symmetric difference is denoted .

We say is **amenable** if there is a sequence of finite subsets of such that for all we have

Such a sequence is called a **Følner sequence**.

**Exercise**. Note that we may assume that contains the identity of and is symmetric, i.e. . Such an assumption only makes it

*harder*for a group to be amenable. Show that in this case in the definition of amenability we can replace the quantity by .

Later on we will need a finitary version of this definition. We add it here for contrast, but I realize it might be too abstract to grok at this moment. Feel free to come back to it later after you’ve seen some examples of amenable groups.

**Definition 1 (finite version)**. Let be a discrete countable group.

We say is **amenable** if for all , there is a such that

**Exercise**. Here are three abstract exercises to encourage you to play with the definitions. Define .

- Show if a group is amenable is the sense of definition 1, then it is amenable in the finite version of definition 1. (
**Easy**.) - Suppose that a group is not amenable. Write down what the finite version of definition 1 tells you. (
**Easy**.) Interpret this result as a statement about Cheeger constants. - Show that if , then for all . (
**Easy**.) - Show that . (Do it in two steps.) (
**Easy-ish**.) - Show if a group is amenable is the sense of definition 1, then it is amenable in the finite version of definition 1. Use exercise (4) above. (
**Medium**.)

### Examples

**Example**. Consider with the discrete topology. Let . For any finite set , let . Note that . (**Exercise**. Check this last line. Draw a picture.)

We look at two other quick examples of amenable classes of groups. We will not need these, but they illustrate that amenable groups form a broad class.

**Fact**. Abelian groups are amenable.

**The “Meatloaf” lemma.**. Let be a normal subgroup of . If any two of the following are amenable

- ,
- ,
- the quotient by ,

then the third is amenable.

From this we can conclude that solvable groups are amenable.

**Exercise**. The proof is left as an exercise. You may wish to watch this video to explain the name.

### Means and ultrafilter limits

The Følner condition definition was not the original definition for amenable groups. We present the original definition (due to von Neumann) here.

**Definition 2 (von Neumann 30s?)**. Let be a discrete countable group. Let be the collection of bounded functions from to . Let be the indicator function of .

A **(multiplicative left -invariant) mean** is a linear functional such that

- is positive ( implies ), of bounded norm 1 and (
*mean*), - for all where (
*left -invariant*), - for all (
*multiplicative*).

A group is **amenable** if there is a (multiplicative left -invariant) mean on .

**Example**. In particular, a mean on defines a left -invariant probability measure on by defining . (**Exercise**. Check this.)

The example shows that a mean contains at least enough information to define a measure on . However, a mean also assigns values to bounded linear functions that are not characteristic functions. In practice, this means that constructing a left -invariant mean can be complicated, even in the case where . In most (all?) interesting cases, the construction of a mean will involve a use of the axiom of choice. Sometimes this will be Zorn’s Lemma and other times it will be an ultrafilter limit (or Banach limit).

**Exercise**. The following series of exercises will walk you through creating a left -invariant mean on . Look at Chapter 28, Problem 17 of the wonderful book Problems and Theorems in Classical Set Theory by Péter Komjáth. Note the important use of the axiom of choice.

Before we show that definition 1 and 2 are equivalent, we remind you about the notion of an ultrafilter limit. It replaces one notion of largeness (“the tail of a sequence”) with an ultrafilter notion of largeness (“in a specific ultrafilter”).

**Definition**. Let be an ultrafilter on . Let be a sequence in . For , define the

**-limit**of by

Such a limit is also sometimes called a

**Banach limit**.

The remarkable fact is that ultrafilter limits always converge! This is useful when defining measures and means.

**Fact**. Let be an ultrafilter on . For every sequence of real numbers, there is a (unique) such that .

In particular, it says that an ultrafilter can decide whether the sequence converges to or (depending on whether the evens are an ultrafilter set or whether the odds are an ultrafilter set.)

**Exercise**. If you’re interested in ultrafilter limits, here are some exercises for you.

- Prove the above fact (including uniqueness).
- Prove that different ultrafilter limits may assign different values to a sequence .
- Suppose that (in the first year calculus sense). Prove that , for any (nonprinciple) ultrafilter .

You can find more exercises in Chapter 17, problems 19 and 20 of Komjáth’s “Problems and Theorems in Classical Set Theory“.

Now we can prove the following result.

**Proposition (Følner 1955)**. If a group is amenable in the sense of Følner, definition 1, then it is amenable in the sense of Von Neumann, definition 2.

**Proof**. Suppose that satisfies the Følner condition, so has a Følner sequence . Let be an ultrafilter on . We define a linear functional by

It is an exercise to check -invariance of . See the exercises after the definition of mean for intuition on why this is the correct way to define a mean.

### Paradoxical decompositions

So far we have not spoken about non-amenable groups. This is partly because the conditions we have are better suited for showing amenability. We fix that by introducing another equivalent definition for amenability.

This definition is motivated by von Neumann’s study of the Banach-Tarski paradox.

**Definition 3**. We say that a group has a

**paradoxical decomposition**if there is a partition into disjoint sets and elements and such that

**Exercise**. Show that it is equivalent to ask that the sets are merely disjoint; their union need not be all of .

For other exercises, consult Chapter 19 of Komjáth’s “Problems and Theorems in Classical Set Theory“.

**Example**. Let be the free group on generators , with empty word . Let be the set of words in that start with an . Similarly we define and . Note that

Also we see that

(**Exercise**. Ignoring , find a paradoxical decomposition of where the are pairwise disjoint, and the are pairwise disjoint.)

The forward direction of the following is an easy exercise.

**Proposition (Tarksi)**. If group has a paradoxical decomposition, then it does not have a left invariant measure (and hence it is not amenable in the sense of von Neumann).

Conversely, if a group is amenable in the sense of von Neumann, then it does not have a paradoxical decomposition.

**Corollary**. The free group is not amenable.

Tarski’s original proof is combinatorial. We will give a (shocking) direct proof of the following fact, using graph theory.

**Theorem (Deuber-Simonovits-Sos 1995)**. If a countable discrete group is amenable in the sense of Følner (definition 1), then it has a paradoxical decomposition.

In order to prove this, we will require the following infinite version of Hall’s marriage theorem.

**Definition**. Let be a graph, and .

Define .

Now assume is a bipartition. For a matching is a subcollection such that every vertex in has degree (in ) and every vertex in has degree (in ).

**Theorem (Generalized Hall-Rado)**. Let be a countable, locally finite (i.e every vertex has finite degree) bipartite graph. Then there is a -matching iff

- we have , and
- we have .

**Proof of Deuber-Simonovits**. We prove the contrapositive. Suppose that fails the finite Følner condition. We will find a condition that can be turned into an estimate for the Hall-Rado theorem. (It will become clear later what graph we will be using. You can skip to the box below if you only care about what that estimate is.)

So there is a symmetric such that for all we have .

Note that this can be interpreted as an "expansion property". It can be interpreted to say that the Cheeger constant of a Cayley graph is positive. (That remark was just for intuition, we will not use it.)

This gives the estimate .

Applying it again gives .

In general after applications we get .

Choose a large enough so that . Let . Note that it is symmetric.

We summarize this information:

**Expansion condition**There is a symmetric such that for all we have

We set up an application of the generalized Hall-Rado theorem to a graph . Let be a bipartite graph where and are each copies of . Put an edge if are in different copies of and there is a such that . (Since is symmetric this is a graph and not a directed graph.)

Note that the expansion condition, applied to , says that every vertex in must have at least neighbours. In fact, the expansion condition gives us the required condition for the Hall-Rado theorem for .

It produces two functions with disjoint domains () such that and are always edges and .

This means that and .

**Exercise.** Convince yourself (1) that the previous sentence is true, (2) that this is actually a paradoxical decomposition and (3) the Hall-Rado theorem actually gives us two such functions.

### Summary

Here is a summary of the previous sections.

**Theorem**. Let be a discrete countable group. TFAE:

- has a Følner sequence,
- admits a multiplicative left -invariant mean,
- has no paradoxical decompositions.

If any of these conditions happen, then we say that is amenable.

**Proof strategies**.

[.] We left this as an exercise using a diagonalization argument.

[.] This used the concept of a -limit.

[.] The fact that is more or less obvious and is left as an exercise.

[.] We presented the Hall’s Marriage argument that showed .

Historically, we also have the following

[.] Due to Følner 1955.

[.] Due to Tarski.

## Ergodic theory

Now we switch gears to talk about the ergodic theory. We introduce the basic notions with the ultimate goal of wanting to show how the tools of ergodic theory have been used to show Ramsey results.

### Definitions and examples

**Definition**. An

**measure preserving action**on a measure space is a quadruple where is a probability measure space and has the properties:

- , and
- for all . (
*measure preserving*)

The action is **ergodic** if in addition:

- If then .

We now present two classic examples.

**Example 1**. Irrational rotation. Fix an irrational number . Let be mod , which is the circle. Let . **Exercise**: Show that this is an ergodic action.

**Example 2**. Coin flipping, the 2-shift. Let , with the product measure where each point in gets measure . This is a compact space. The action .

### The ergodic theorem

The ergodic theorem, first proved by Birkhoff in 1931.

**Theorem (Birkhoff 1931)**. [THE ERGODIC THEOREM]

### Products, mixing and weak-mixing

We now get to two fundamental properties that an ergodic action may have. First we introduce the product action.

**Definition**. Let be an action on a measure space. The

**product action on the product space**is , where this is the product measure and the componentwise action.

A natural question is “When is the product of an ergodic action still ergodic?”. Let’s see what the answer is for our earlier examples.

**Example 1**. For an irrational rotation of , the product is not ergodic. Consider the subspace where is a constant, then , so this will be an invariant subspace.

**Example 2**. The product of the coin flipping shift action is just where each point has measure . This is ergodic.

This gives us the following definition.

**Definition**. Let be an ergodic action on a measure space. It is

**weakly mixing**if the product is ergodic.

The name comes from the following property which we will not really study here.

**Definition**. Let be an action on a measure space. It is

**mixing**if for all we have

**I don’t know why I wrote this. This is verbatim.**.

In ,

The following explains the name “weak-mixing”.

**Fact**. If an action is weak-mixing, then there is a set of density such that

**Definition**. Let . The (upper) density is defined as

**Exercise**. Density is just a measure of largeness, but here are some exercises about it if you want to understand it better.

- The set of all even numbers has density .
- The set of square numbers has density .
- Every finite set has measure .
- If is defined, then .
- There are sets where the density is not defined.

There was a question from the audience about mixing vs weak-mixing. The following example distinguishes them.

**Example**. Let be the group of all measure-preserving transformations of with the Lebesgue measure.

Topologize it to make it a Polish group so that if for all we have .

Generically, is weak-mixing but not mixing.

This is actually two results, one due to Halmos (“In general a measure preserving transformation is mixing” 1944) and one due to Rokhlin (“A ‘general’ measure-preserving transformation is not mixing.” 1948). The titles are hilariously contradictory, but in reality one is referring to weak-mixing and the other is refering to mixing.

### The correspondence principle

Ultimately, we will want to talk about Furstenberg’s 1977 proof of Szemerédi’s theorem. To do this we introduce the correspondence principle, which connects measure and density.

**The Correspondence Pinciple**. Let have positive density. There is an ergodic system and a set such that TFAE:

- ,
- has positive density.

Whatever happens here is relfected in the set of positive density. Once you have multiple recurrence in the ergodic setting, then you get it in the set of positive density.

Furstenberg’s proof of Szemerédi’s theorem uses the following ergodic result.

**Theorem (Furstenberg 1977)**. If is weak-mixing, , and is fixed, then

**Sketch of proof of the correspondence principle**. Fix of positive density. Let .

We need to define a measure on each set , where and is finite. Here is the basic open set given by the finite function . It will be enough to define the measure on this set because of the Caratheodory extension theorem.

Fix an ultrafilter . For a finite , define

where counts the number of times that the “pattern of occurs in “, to be precise

where is a function that evalutes to if the statement is true and if it is false.

Note that this isn’t an ergodic measure, but we can fix that.

**Multiple recurrence for an irrational rotation**. Let be an irrational rotation. There is a sequence such that for a fixed ,

**Proof**. Suppose that is given by the rotation by . Take a suquence so that .

In the next lecture we will see how this applies to Furstenberg’s proof.

### Amenable groups and ergodic theory

We now make the connection between amenable groups and ergodic theory.

**Definition**. We need a structural theorem for that can be proved using a Reiss-representation style argument. Suppose is a measure-preserving action of for each .

Define to be the linear span of the functions of the form , where and .

Define to be the -invariant onto functions.

We can write , and it comes with two projection functions that project functions down to the corresponding subspace.

**The ergodic theorem for amenable groups**. Suppose is amenable, is a Følner sequence, and is a measure-preserving action of for each . Then for all we have

Note that

For example, we can look at the 2-shift of an amenable group as it acts on , with the product measure where the points in each get measure .

## References

- Birkhoff (“Proof of the ergodic theorem“, 1931)
- Deuber-Simonovits-Sós (“A note on paradoxical metric spaces.”, 1995) – Graph theory proof.
- Halmos (“In general a measure preserving transformation is mixing“, 1944) – Weak mixing
- Rokhlin (“A ‘general’ measure-preserving transformation is not mixing”, 1948) – not strong mixing
- Furstenberg (“Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions“, 1977)
- Szemerédi (“On sets of integers containing no elements in arithmetic progression“, 1975) – Proof of Szemerédi’s theorem
- Følner (“On groups with full Banach mean value“, 1955) – equivalence of amenable

### Expository material and exercises

- Tao (“Some notes on amenability“, 2009) – Notes about amenability
- Tao (“254A, Lecture 10: The Furstenberg correspondence principle“, 2008) –
- Zhao (“Szemerédi’s Theorem via Ergodic Theory“, 2011) – Exhaustive primer about the topic
- Komjath (“Problems and Theorems in Classical Set Theory“, 2006) – Exercises about amenability, Ultrafilter limits and paradoxical decompostitions.