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
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.
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.
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.
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.
We say is amenable if for all , there is a such that
- 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.)
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.
- the quotient by ,
then the third is amenable.
From this we can conclude that solvable groups are amenable.
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.
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).
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”).
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.
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.)
- 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.
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.
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.
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.
Conversely, if a group is amenable in the sense of von Neumann, then it does not have a paradoxical decomposition.
Tarski’s original proof is combinatorial. We will give a (shocking) direct proof of the following fact, using graph theory.
In order to prove this, we will require the following infinite version of Hall’s marriage theorem.
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 ).
- we have , and
- we have .
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:
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.
Here is a summary of the previous sections.
- 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.
[.] 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.
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
- , 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.
Products, mixing and weak-mixing
We now get to two fundamental properties that an ergodic action may have. First we introduce the product 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.
The name comes from the following property which we will not really study here.
The following explains the name “weak-mixing”.
- 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.
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.
- 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.
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.
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.
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.
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 .
- 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.