AMENABILITY AND RAMSEY THEORY JUSTIN TATCH MOORE Abstract. Thepurposeofthisarticleistoconnectthenotionof the amenability of a discrete group with a new form of structural Ramsey theory. The Ramsey theoretic reformulation of amenabil- ityconstitutesaconsiderableweakeningoftheFølnercriterion. As a by-product, it will be shown that in any non amenable group G, there is a subset E of G such that no finitely additive probability measureonGmeasuresalltranslatesofE equally. Theanalysisof discrete groups will be generalized to the setting of automorphism groups of ultrahomogeneous structures. 1. Introduction A group G is amenable1 if there is a finitely additive, translation invariant probability measure defined on all subsets of G. This no- tion was isolated by von Neumann from the Banach-Tarski paradox. Since then it has played an important role in a diverse cross section of mathematics. It has a large number of seemingly different equivalent formulations (see [17], [23]); two of the most celebrated are: Theorem 1.1. [20] [21] A group G is amenable if and only if there do not exist elements g (i < k) of G and a partition of G into sets A i i (i < k) such that, for some i < i, both {g A : i < i } and {g A : i ≤ 0 i i 0 i i 0 i < k} are partitions of G. 2000 Mathematics Subject Classification. Primary: 05D10, 05C55, 20F38, 20F65, 43A07; secondary: 03C15, 03E02. Key words and phrases. Amenable, extremely amenable, Fra¨ıss´e, Følner crite- rion, free group, invariant measurability, structural Ramsey theory, Thompson’s group, ultrahomogeneous. I would also like to thank Paul Larson, Lionel Nguyen van Th´e, and Todor Tsankov for reading drafts of this paper and offering comments. I am also grateful to the anonymous referee for their careful reading and suggesting a simplification and improvement to the proof of Theorem 1.4 (and in particular for pointing out that two sets are sufficient). The research presented in this paper was partially supported by NSF grant DMS–0757507. Any opinions, findings, and conclusions or recommendations expressed in this article are those of the author and do not necessarily reflect the views of the National Science Foundation. 1Throughout this paper, the adjective “left” is implicit in the usage of action, amenable, Følner, invariant, and translation unless otherwise stated. 1 2 JUSTIN TATCH MOORE Theorem 1.2. [5] (see also [11]) A group G is amenable if and only if for every finite A ⊆ G and every (cid:15) > 0 there is a finite B ⊆ G such that (letting 4 denote symmetric difference) X |(aB)4B| ≤ (cid:15)|B| a∈A The set B which satisfies the conclusion of this theorem is said to be (cid:15)-Følner with respect to A; the assertion that such sets exist for each (cid:15) > 0 is known as the Følner criterion. One of the main results of the present article is to formulate a weaker criterion for amenability than the Følner criterion. If A is a set, let Pr(A) denote the collection of all finitely additive probability measures on A. If G is a group, then the operation on G is extended to ‘1(G) affinely: X µν(A) = µ({x})ν({y}) xy∈A (Here and throughout we identify G with both a subset of ‘1(G) and a subset of Pr(G) by regarding its elements as point masses.) Observe that gν(E) = ν(g−1E). If A and B are finite subsets of G and (cid:15) > 0, then B is (cid:15)-Ramsey with respect to A if whenever E ⊆ B, there is a ν in Pr(B) such that • Pr(A)ν ⊆ Pr(B) and • |µν(E)−µ0ν(E)| ≤ (cid:15) for all µ and µ0 in Pr(A). The definition is unchanged if E is allowed to be an arbitrary subset of G (in particular if B is (cid:15)-Ramsey with respect to A, then so is any finite superset of B). Also, one obtains an equivalent statement if µ ranges over the elements of A — these are the extreme points of Pr(A). Observe that if ν is a finitely supported probability measure on G, then Pr(A)ν can be regarded as a copy of Pr(A). Thus B is (cid:15)-Ramsey with respect to A if whenever we induce an affine coloring of Pr(B) by assigning the values 0 and 1 to the elements of B, there is a copy of Pr(A) on which the coloring is (cid:15)-monochromatic. Theorem 1.3. Let G be a group. The following are equivalent: (1) For every E ⊆ G and every finite A ⊆ G, there is a µ in Pr(G) such that µ(gE) = µ(E) for all g in A. (2) For every finite A ⊆ G, there is a finite B which is 1-Ramsey 2 with respect to A. (3) For every finite A ⊆ G, there is a finite B which is 0-Ramsey with respect to A. (4) G is amenable. AMENABILITY AND RAMSEY THEORY 3 The equivalence of (1) and (4) was unexpected and while they are purely global statements about G involving its typically infinite sub- sets, the proof crucially employs the finitary interpolation provided by (2). Also notice that the only examples of 0-Følner sets are the trivial ones: a finite group is a 0-Følner set in itself. Thus (3) represents a new phenomenon for which the Følner criterion provides no analog. The proof of Theorem 1.3 will also provide a quantitative relationship between (cid:15)-Ramsey sets and (cid:15)-Følner sets; this is the content of Section 4. Let us say that a subset E of a group G is invariantly measurable if there is a µ in Pr(G) such that µ(gE) = µ(E) for all g in G. By the above theorem, a group is amenable exactly when all of its subsets are invariantly measurable. That the invariant measurability of sets can be witnessed by a single measure turns out not to be a phenomenon present in arbitrary groups. Theorem 1.4. There are two invariantly measurable subsets of F 2 which can not be simultaneously measured invariantly. Theorem 1.3 tells us that if a group G is not amenable, then there is a single set E ⊆ G which can not be measured invariantly. It is natural to ask to what extent E can be specified by a finite amount of information. Let A be a fixed finite subset of G. If E ⊆ G, define X A = {Eg−1 ∩A : g ∈ G}. E (When A is clear from the context, the superscript will be suppressed.) Thus if A is a ball about the identity, Eg−1 ∩ A is a “picture” of E centered at g where the scope of the image is specified by A. The set X is then the collection of all such pictures of E taken from different E vantage points in G. If Y is a collection of subsets of A, then we say that Y is realized in G if Y = X for some E ⊆ G. E A collection Y of subsets of a finite set A is (cid:15)-balanced if there is a probability measure µ on Y such that |µ({Y ∈ Y : a ∈ Y})−µ({Y ∈ Y : b ∈ Y})| ≤ (cid:15) whenever a and b are in A. Balanced will be taken to mean 0-balanced. It follows from the Hahn-Banach Separation Theorem that a collec- tion Y is unbalanced if and only if there is an f : A → R such that P f(a) = 0 and for every Y in Y , P f(a) > 0. a∈A a∈Y We will prove the following analog of Theorem 4.2 of [1]. Theorem 1.5. For a group G, the following are equivalent: (1) G is non amenable. 4 JUSTIN TATCH MOORE (2) There is a finite A ⊆ G and an unbalanced collection Y of subsets of A which is realized in G. (3) There is a finite A ⊆ G for which there is no finite B which is 0-Ramsey with respect to A. Thus in order to establish the non amenability of a group, it is suf- ficient to realize a subcollection of X Y = {Y ⊆ A : f(a) > 0} f a∈Y for some f : A → R such that P f(a) = 0. Balanced sets have a∈A been studied in game theory (e.g. [18]), although the focus has been on minimal balanced collections rather than the maximal unbalanced collections, which are most relevant to the present discussion. The above theorems concern the amenability of discrete groups. The amenability of a topological group G can be formulated as fol- lows: whenever G acts continuously on a compact space K, K sup- ports an Borel probability measure which is preserved by the action of G. A strengthening of amenability in this context is that of extreme amenability: every continuous action of G on a compact space has a fixed point. In [9], Kechris, Pestov, and Todorcevic discovered a very general correspondence which equates the extreme amenability of the automorphism group of an ordered Fra¨ıss´e structure with the Ramsey Property of its finite substructures. Theorem 1.6. [9] Let G be a closed subgroup of S . The following ∞ are equivalent: (1) G is extremely amenable. (2) G = Aut(G) where G is a Fra¨ıss´e structure with an order rela- tion and the finite substructures of G have the Ramsey Property. At the time of [9], it was unclear whether there was an analogous connection between amenability and Ramsey theory. In Section 7 it will be shown that such an analog does exist. The notation will be mostly standard. Following a set-theoretic con- vention, I will sometimes abbreviate {0,...,k −1} with k. The set of natural numbers is taken to include 0 and all counting will begin at 0. The letters i,j,k,l,m,n will be used to denote natural numbers unless otherwise stated. If H ⊆ G, then we will identify Pr(H) with the set of those µ in Pr(G) such that µ(H) = 1. 2. A Ramsey theoretic criterion for amenability In this section we will prove most of Theorem 1.3, deferring the equivalence of amenability with (3) to the next section. Before we AMENABILITY AND RAMSEY THEORY 5 begin, it will be necessary to extend the evaluation map (ν,E) 7→ ν(E) to a bilinear map on Pr(G)ב∞(G) by integration. We will only need this for finitely supported ν in which case X ν(f) = ν({g})f(g) g∈B We will define f(ν) = ν(f). Observe that the map (ν,f) 7→ ν(f) is bilinear. When proving the theorem, it will be natural to further divide the task as follows. Theorem 2.1. Let G be a group and H ⊆ G be closed under products and contain the identity of G. The following are equivalent: (1) For every E ⊆ G and every finite A ⊆ H, there is a µ in Pr(H) such that µ(g−1E) = µ(E) for every g ∈ A. (2) For every finite A ⊆ H, there is a finite B ⊆ H such that B is 1-Ramsey with respect to A. 2 (3) There is a positive q < 1 such that for every finite A ⊆ H, there is a finite B ⊆ H such that if f : B → [0,1], then there is a ν in Pr(B) such that for all g,g0 ∈ A, gν is in Pr(B) and |gν(f)−g0ν(f)| ≤ q. (4) For every finite A ⊆ H and (cid:15) > 0, there is a finite B ⊆ H such that if f : B → [0,1] then there is a ν in Pr(B) such that for all g,g0 ∈ A, gν is in Pr(B) and |gν(f)−g0ν(f)| < (cid:15). (5) There is a µ ∈ Pr(H) such that for every E ⊆ G, µ(g−1E) = µ(E) whenever g is in H. Remark 2.2. The above generality allows H to be the positive elements of the group with respect to some generating set. This will be useful below when reformulating the amenability problem for Thompson’s group F. Proof. Observe that trivially (5⇒1). It is therefore sufficient to prove (1⇒2⇒3⇒4⇒5). (1⇒2): Suppose that (2) is false for some finite A ⊆ H. I claim there is a set E ⊆ H such that for every µ ∈ Pr(H), there are g,h ∈ A such that |µ(g−1E)−µ(h−1E)| > 1 — a condition which implies the failure 2 of (1). By replacing G by a subgroup if necessary, we may assume that G is generated by A and in particular that G is countable. Let B n (n < ∞) be an increasing sequence of finite sets covering H. Define T n to be the collection of all pairs (n,E) where E is a subset of B which n 6 JUSTIN TATCH MOORE witness that B is not 1-Ramsey with respect to A. Let T = S T n 2 n n and if (n,E) and (n0,E0) are in T, define (n,E) < (n0,E0) if n < n0 T and E = E0 ∩ B . Observe that if (n0,E0) is in T and n < n0, then n n0 (n,E0∩B ) is in T . Thus (T,< ) is an infinite finitely branching tree n n T and hence there is an E ⊆ H such that (n,E∩B ) is in T for each n. n n If there were a measure ν such that |ν(g−1E) − ν(h−1E)| < 1 for all 2 g,h ∈ A, there would exist such a ν which has a finite support S. But this would be a contradiction since then S∪(A·S) would be contained in some B and would witness that (n,E ∩B ) was not in T . n n n (2⇒3): Let A ⊆ H be a given finite set and let B ⊆ H be finite and 1-Ramsey with respect to A. It suffices to prove that B satisfies the 2 conclusion of (3) with q = 3/4. Let f : B → [0,1] be given and define E = {b ∈ B : f(b) ≥ 1/2}. By assumption, there is a ν in Pr(B) such that Pr(A)ν ⊆ Pr(B) and for all g,g0 ∈ A, |gν(E) − g0ν(E)| ≤ 1/2. Also 1 1 0 ≤ min(gν(f − χ ),g0ν(f − χ )) E E 2 2 1 1 max(gν(f − χ ),g0ν(f − χ )) ≤ 1/2 E E 2 2 Notice that if 0 ≤ a,b ≤ 1/2, then |a − b| ≤ 1/2. Therefore for all g,g0 ∈ A |gν(f)−g0ν(f)| = 1 1 1 | (gν(E)−g0ν(E))+gν(f − χ )−g0ν(f − χ )| E E 2 2 2 1 1 1 ≤ |gν(E)−g0ν(E)|+|gν(f − χ )−g0ν(f − χ )| E E 2 2 2 ≤ 1/4+1/2. (3⇒4): Let A ⊆ H and (cid:15) > 0 be given. Let n be such that qn < (cid:15) and construct a sequence B (i ≤ n) such that, setting B = A, B i 0 i+1 satisfies the conclusion of (3) with respect to B . Construct ν (i < i i n) by downward recursion such that Pr(B )ν ⊆ Pr(B ) and for all i i i+1 g,g0 ∈ B , i |gν ···ν (f)−g0ν ···ν (f)| ≤ qn−i i n−1 i n−1 This is achieved by applying (3) to the function f defined on B by i i+1 f = f n−1 (cid:16) (cid:17) f (g) = (1/q)n−i−1 gν ···ν (f)− min g0ν ···ν (f) i i+1 n−1 i+1 n−1 g0∈Bi+1 if i < n−1. Our inductive hypothesis implies that the range of f is i contained within [0,1]. Therefore there is a ν such that Pr(B )ν ⊆ i i i Pr(B ) and i+1 |gν (f )−g0ν (f )| ≤ q i i i i AMENABILITY AND RAMSEY THEORY 7 holds for every g,g0 ∈ B and thus i (1/q)n−i−1|gν ···ν (f)−g0ν ···ν (f)| i n−1 i n−1 = (1/q)n−i−1|f(gν ···ν )−f(gν ···ν )| i n−1 i n−1 = |f (gν )−f (g0ν )| = |gν (f )−g0ν (f )| ≤ q. i i i i i i i i Multiplying both sides of the inequality by qn−i−1, we see that ν sat- i isfies the desired inequality. This completes the recursion. If ν = ν ···ν , then for all g,g0 in A = B we have that 0 n−1 0 |gν(f)−g0ν(f)| ≤ qn < (cid:15). (4⇒5): Observe that, by compactness, it is sufficient to prove that for every (cid:15) > 0, every finite list E (i < n) of subsets of H, and g i i (i < n) in H, there is a finitely supported µ ∈ Pr(H) such that for all i < n |µ(g−1E )−µ(E )| < (cid:15). i i i Set B = {e } ∪ {g : i < n} and construct a sequence B (i ≤ n) 0 G i i such that B satisfies (4) with B in place of A and (cid:15)/2 in place of i+1 i (cid:15). Inductively construct ν (i < n) by downward recursion on i. If i ν (i < j < n) has been constructed, let ν ∈ Pr(B ) be such that j i i+1 Pr(B )ν ⊆ Pr(B ) and i i i+1 |µν ···ν (E )−µ0ν ···ν (E )| < (cid:15)/2 i n−1 i i n−1 i for all µ,µ0 ∈ Pr(B ). Set µ = ν ···ν . If i < n, then since ν ···ν i 0 n−1 0 i−1 and g−1ν ···ν are in Pr(B ), i 0 i−1 i |g µ(E )−ν ···ν (E )| < (cid:15)/2 i i i n−1 i |µ(E )−ν ···ν (E )| < (cid:15)/2 i i n−1 i and therefore |µ(g−1E )−µ(E )| < (cid:15). (cid:3) i i i I will finish this section with the following basic example, which shows that existence of 0-Ramsey sets for Z is just the well known Pigeon Hole Principle. Suppose that A ⊆ Z is finite; without loss of generality, A = {0,...,m − 1}. Let B = {1,...,2m + m + 1} and suppose that E ⊆ B. Notice that {A ∩ (E − i) : i ∈ Z} has at most 2m elements and therefore there are 1 ≤ i < j ≤ 2m +1 such that for all 0 ≤ k < m, k +i is in E if and only if k +j is in E. Let ν be the uniform measure on the interval {i,...,j −1}. By our choice of i and j, |E ∩{i,...,j −1}| = |E ∩{i+k,...,j −1+k}| and thus ν(E) = ν(E −k) for all 0 ≤ k < m. 8 JUSTIN TATCH MOORE 3. The amenability problem for Thompson’s group F Perhaps the best known problem concerning the amenability of a specific group asks whether Richard Thompson’s group F is amenable. In this section I will discuss how this problem reduces to a natural finite Ramsey-theoretic statement. I will only briefly review the termi- nology and basic facts about Thompson’s group; the reader is referred to [2] and [10] for further background and justification for some of the statements made below. Thompson’s group F is the group with generators x (i < ∞) sat- i isfying the relations x−1x x = x whenever i < n. The positive i n i n+1 elements of F are the products of these generators. It is easy to see that x and x already generate the group and it is well known (see 0 1 [2]) that every element of F can be written as a fraction of positive elements. Thus by Ore’s theorem (see [17]), F is amenable if and only if its action on its positive elements is amenable. The action of F on its positive elements can be described as follows. Let (T, ) denote the free binary system on one generator. The ele- b ments of T are just formal sums — with associating parentheses — of some number of 1’s. They can naturally be thought of as rooted ordered binary trees in the sense of [2] and the following partial action of F on T x ·((A B) C) = A (B C) 0 b b b b x ·(S ((A B) C)) = S (A (B C)) 1 b b b b b b is equivalent to the partial action of F on its positive elements (see [10]). By unraveling the definitions, one can reformulate the amenability of F in the following way. Let T denote those elements of T with n n leafs and let A denote the set of probability measures on T . A n n copy of T in T is a collection of the form {T(U ,...,U ) : T ∈ T } m n 1 m m where U (1 ≤ i ≤ m) is an ordered sequence of elements of T with a i total of n leafs. Here T(U ,...,U ) denotes the result of substituting 1 m U for the ith occurrence of the generator in T. A copy of T in A is i m n a convex combination of copies of T in T (formally we take a convex m n combination of maps of the form T 7→ T(U ,...,U ) to obtain a map 1 m from T into A and then collect the range of this map). m n Theorem 3.1. The following are equivalent: (1) Thompson’s group F is amenable. (2) For every m there is an n such that if f : T → {0,1}, then n there is a copy of T in A on which f is constant. m n AMENABILITY AND RAMSEY THEORY 9 In order to see the relationship to Ramsey’s theorem, observe that Ramsey’s theorem can be formulated in the following way. If n and k are natural numbers, let n[k] denote all partitions of {1,...,n+1} into k+1 intervals. Notice that there are canonical bijections between this set and the k element subsets of {1,...,n} and also with sequences of natural numbers of length k+1 which add to n+1. If m ≥ k and X is in n[m], let X[k] denote all elements of n[k] which are refined by X. In this language, Ramsey’s theorem asserts that for every m and k there is an n such that if n[k] is colored red and blue, there is an X in n[m] such that X[k] is monochromatic. Let n[[k]] denote all families X of intervals in {1,...,n+1} such that: • the⊆-minimalelementsofX arethesingletonsof{1,...,n+1} and the ⊆-maximal elements of X are an element of n[k]. • any element of X with more than one element is the union of two other elements of X. • if x,y are in X, then x ⊆ y, y ⊆ x, or x∩y = ∅. Thus an element of n[[k]] is the result of starting with {{1},...,{n+1}} and iteratively joining consecutive pairs of intervals until one obtains a partition of {1,...,n+1} into k +1 intervals. There is a canonical correspondence between n[[k]] and sequences from T of length k + 1 where the total number of leaves is n+1. The amenability of Thompson’s group is now the statement that for every m and k there is an n such that if n[[k]] is colored with red and blue, there is a probability measure Ξ on n[[m]] such that Ξ[[k]] is monochromatic. (As above, Ξ is regarded as a formal convex combi- nation of elements X of n[[m]] and Ξ[[k]] consists of the corresponding convex combinations of the elements of the X[[k]]’s.) Observe that the case k = 1 is the strongest assertion and it is, modulo the definitions, the reformulation given in Theorem 3.1. 4. Comparing the Ramsey and Følner functions The purpose of this section is to define the Ramsey function of a finitely generated group with respect to a finite generating set and relate it to the Følner function which has been studied in, e.g., [3], [4], [8]. The main result of this section is due to Henry Towsner, answering a question in an early draft of this paper: The Følner function for a given group and generating set can be obtained from the Ramsey function by primitive recursion. Itisincludedwithhiskindpermission. We will now turn to the definitions of the Følner and Ramsey func- tions. Let G be a group with a fixed finite generating set S (which is not required to be closed under inversion). Let B denote the elements n 10 JUSTIN TATCH MOORE of G whose distance from the identity is at most n in the word metric. Define the following functions: • Føl (k) is the minimum cardinality of a 1/k-Følner set with G,S respect to the generating set S. • F (m,(cid:15)) is the minimum n such that there is a ν in Pr(B ) G,S n P such that Pr(B )ν ⊆ Pr(B ) and ||gν −ν|| < (cid:15). m n g∈Bm ‘1 • R (m,(cid:15)) is the minimum n such that B is (cid:15)-Ramsey with G,S n respect to B . m ˜ • R (m,(cid:15),l) is the minimum n such that if f (i < l) is a se- G,S i quence of functions from B into [0,1], then there is a ν ∈ n Pr(B ) such that Pr(B )ν ⊆ Pr(B ) and such that for every n m n g,g0 ∈ B and i < l, m |gν(f )−g0ν(f )| < (cid:15) i i ˜ ˜ Set R (m) = R (m,1/2) and R (m,(cid:15)) = R (m,(cid:15),1). The defi- G,S G,S G,S G,S nition of F is formulated so that it is a triviality that R (m,k) ≤ G,S G,S ˜ R (m,k) ≤ F (m,k) holds for all m and k. The following relation- G,S G,S ship holds between F and Føl : G,S G,S Føl (k) ≤ (2|S|+1)FG,S(1,1/k) G,S The reason for this is that the n-ball in G with respect to S contains at most (2|S|+1)n elements and if ν ∈ ‘1(G) is such that X ||gν −ν|| < (cid:15) ‘1 g∈S then the support of ν contains an (cid:15)-Følner set with respect to S [11]. The proof of Theorem 2.1 shows that R˜ (m,(cid:15)) ≤ Rp (m) G,S G,S whenever (3/4)p < (cid:15) (here Rp denotes the p-fold composition of G,S R ). Furthermore, it shows that G,S ˜ ˜ ˜ R (m,(cid:15),l) ≤ R (R (m,(cid:15),l−1),(cid:15)) G,S G,S G,S = R˜ (R˜ (...R˜ (m,(cid:15))...,(cid:15)),(cid:15)) ≤ Rlp (m) G,S G,S G,S G,S whenever l > 1. Finally we have the following proposition. ˜ Proposition 4.1. F (m,2(cid:15)|S|) ≤ R (m,(cid:15),|S|). G,S G,S ˜ Proof. Let B = B where n = R (m,(cid:15),|S|). Define n G,S C = {hgν −ν : g ∈ Si : ν ∈ Pr(B) and Pr(S)ν ⊆ Pr(B)}. X U = {ξ ∈ (‘1(B))S : ||ξ || < 2(cid:15)|S|} g ‘1 g∈S