FAST GROWTH IN THE FØLNER FUNCTION FOR THOMPSON’S GROUP F

JUSTIN TATCH MOORE

Abstract. The purpose of this note is to prove a lower bound on the growth of Følner functions for Thompson’s group F. Specifically I will prove that, for any finite generating set Γ ⊆ F, there is a constant C such that Føl_{F,Γ}(C^{n}) ≥ exp_{n}(0).

1. Introduction

In this paper we will study the Følner function for Thompson’s group F. Recall that a finite subset A of a finitely generated group G is ε-Følner (with respect to a finite generating set Γ ⊆ G) if

∑_{γ∈Γ} |(A · γ) △A| < ε|A|

where △ denotes symmetric difference. The Følner function of G (with respect to Γ) is defined by

Føl_{G,Γ}(n) = min\{|A| : A ⊆ G is \frac{1}{n}-Følner w.r.t. Γ\}

with Føl_{G,Γ}(n) = ∞ if there is no 1/n-Følner set with respect to Γ. By Følner’s criterion, a group G is amenable if and only if its Følner function (with respect to any finite generating set Γ) is finite valued.

Thompson’s group F has many equivalent definitions; we will use the formulation in terms of tree diagrams defined below. The standard presentation of F is infinite, with generators x_{i} (i ∈ ℕ) satisfying

2000 Mathematics Subject Classification. 20F65, 43A07.

Key words and phrases. Følner function, tower function, Thompson’s group, amenable.

I would like to thank Matt Brin for his careful reading of drafts of this paper, catching errors, and suggesting improvements. In particular, the current formulation of Lemma 3.9 was suggested by him (the original formulation provided a weaker estimate). I would also like to thank the anonymous referee for their very careful reading and helpful comments and suggestions. This research was supported in part by NSF grant DMS–0757507.

x_{i}^{−1}x_{n}x_{i} = x_{n+1} for all i < n. It is well known, however, that F admits the finite presentation

⟨A, B | [AB^{−1}, A^{−1}BA] = [AB^{−1}, A^{−2}BA^{2}] = id⟩

(see [2]). Geoghegan conjectured that F is not amenable [5, p. 549] and at present this problem remains open.^{1} The goal of this paper is to establish the following lower bound on the Følner function for F.

Theorem 1.1. For every finite symmetric generating set Γ ⊆ F there is a constant C > 1 such that if A ⊆ F is a C^{−n}-Følner set with respect to Γ, then A contains at least exp_{n}(0) elements. In particular Føl_{F,Γ} is not eventually dominated exp_{p}(n) for any finite p.

Here exp_{p}(n) is the p-fold composition of the exponential function defined by exp_{0}(n) = n and exp_{p+1}(n) = 2^{exp_{p}(n)}. If it turns out that F is amenable, then Theorem 1.1 would be a step toward answering (negatively) the following question of Gromov [7, p. 578].

Question 1.2. Is there a primitive recursive function which eventually dominates every Følner function of an amenable finitely presented group?

While it is known that the Følner functions of amenable finitely generated groups can grow arbitrarily fast [4], this is not the case for finitely presented groups (since there are only countably many such groups). See [3] for what can be accomplished via wreath products of ℤ.

This note is organized as follows. In Section 2, I will review some of the basic definitions associated with F and fix some notational conventions. In Section 3, I will introduce the notion of a marginal set and prove some basic lemmas about them. These are sets which must have small intersections with Følner sets. They play a central role in the proof of the main result of the paper. Section 4 recasts the amenability of F in terms of its partial right action on the finite rooted ordered binary trees 𝒯 . Section 5 defines an operation on elements of 𝒯 which exponentially decreases their size and commutes with the partial right action of F. It is shown that the trees which are trivialized by this operation are marginal and it is this that allows the proof of Theorem 1.1.

1In fact Richard Thompson himself had studied the question of the amenablity of F already by the early 1970s [9], although the question was not well known until it was independently considered and popularized by Geoghegan.

2. Notation and background

I will use [2] as a general reference for Thompson’s group F, although the reader is warned that the notation in the present paper will differ somewhat from that of [2]. Let 𝒯 denote the collection of all finite rooted binary trees. For concreteness, we will view elements T of 𝒯 as finite sets of binary sequences which have the following property: for every infinite binary sequence x, there is a unique element of T which is an initial part of x. Thus an element T of 𝒯 is a record of the addresses of the leaves of the tree which it represents. The trivial tree is the set which consists only of the sequence of length 0.

The collection of finite binary sequences is equipped with the operation of concatenation (denoted uˆ v), the partial order ⊆ of extension (defined by u ⊆ uˆ v), and the lexicographic order (denoted u <_{lex} v). Note that u extends v includes the possibility that u = v. I will use ⟨⟩ to denote the sequence of length 0. 𝒯 can also be characterized as being those finite sets T of binary sequences such that:

• no element of T is an initial part of another element of T and • if u is a binary sequence, then uˆ 0 has an extension in T if and

only if uˆ 1 has an extension in T. If U and V are in 𝒯 , then we will say that U is dominated by V if every element of U has a extension in V. If T is in 𝒯 and u a finite binary sequence, define

T/u = {s : uˆ s ∈ T }.

If this set is non-empty, then it is again a member of 𝒯 (in which case T/u is the tree of descendants of u). Elements of 𝒯 come with a canonical ordering provided by <_{lex} and phrases such as the i^{th} element and the minimum element will always refer to the <_{lex}-order in this context. In this paper ℕ contains 0 and in particular counting will always start at 0. The letters i, j, k, and l will always be used to denote natural numbers.

A tree diagram is a pair (L, R) of elements of 𝒯 such that |L| = |R|. We view a tree diagram as describing a map of sequences defined by

s_{i}ˆ x ↦ t_{i}ˆ x

where s_{i} and t_{i} are the i^{th} elements of L and R respectively and x is any binary sequence. This map is defined not only on all infinite length binary sequences but also on all but finitely many finite binary sequences. The value of the associated map f at a sequence t will be denoted t · f when it is defined. If t is a finite sequence, then we will say that f acts properly on t if t · f is defined and the final digit of t · f agrees with that of t. Notice that f acts properly on t unless s · f is undefined for every proper initial part s of t. In particular, if f acts properly on t, it acts properly on any extension of t.

If two tree diagrams define the same map on infinite sequences, then they are said to be equivalent. Every tree diagram is equivalent to a unique minimal tree diagram; such a tree diagram is said to be reduced. Furthermore a tree diagram (S, T) is reduced if and only if whenever i < |S| − 1 it is not the case that both s_{i} and t_{i} end with 0 and s_{i+1} and t_{i+1} end with 1 (where s_{i} and t_{i} are the i^{th} elements of S and T respectively). See [2] for details.

Thompson’s group F is the collection of reduced tree diagrams with the operation defined by f · g = g ∘ f (i.e. “f followed by g”). F is generated by {x_{0}, x_{1}} where x_{0} and x_{1} are specified by:

            x_{0} = \begin{cases}00 ↦ 0 \\ 01 ↦ 10 \\ 1 ↦ 11 \end{cases} x_{1} = \begin{cases}0 ↦ 0 \\ 100 ↦ 10 \\ 101 ↦ 110 \\ 11 ↦ 111 \end{cases}

In our discussion of F “generator” will mean an element of the set Γ = {x_{0}, x_{1}, x_{0}^{−1}, x_{1}^{−1}} (this is really only relevant in Lemma 5.10). This includes the usage of Følner in Sections 4 and 5. If x_{n} is defined by x_{n+1} = x_{0}^{−n}x_{1}x_{0}^{n} for n ≥ 1, then we obtain the generators which yield the infinite presentation of F mentioned in the introduction.

Notice that the existence of constant C satisfying the conclusion of Theorem 1.1 for Γ implies the main theorem for all finite generating sets. This is because if Γ′ is any other finite generating set, there is a constant K > 0 such that any set which is ε-Følner with respect to Γ′ is Kε-Følner with respect to Γ.

I will also identify elements of F with the corresponding maps on sequences. If T is in 𝒯 and f is in F with f defined on all of T, then T · f is the pointwise image of T under f. It is easily checked that this results in an element of 𝒯 and hence this defines a partial right action of F on 𝒯 . If T is in 𝒯 and f is in F, then f acts properly on T if it acts properly on the elements of T. If Γ is a subset of F, then Γ acts properly on T if each element of Γ acts properly on T. Observe that if (S, T) is a reduced tree diagram which represents g and f acts properly on T, then (S, T · f) is reduced and represents f ∘ g. If f is in F, I will write (L_{f}, R_{f}) to denote the reduced tree diagram for f.

3. Marginal sets

In this section we will introduce the notion of a marginal set and collect some basic lemmas which we will use in Sections 4 and 5. Throughout this section “right” in an implicit adjective whenever applicable, although all statements have their corresponding “left” analogs. Fix, for the duration of the section, a group G with a finite symmetric generating set Γ.

Definition 3.1. A partial action of G on a set S is a partial function · : S × G → S such that:

• x · e = x for all x ∈ S;

• x · g = y if and only if x = y · g^{−1} for all g ∈ G and x, y ∈ S;

• x · (gh) = (x · g) · h for all g, h ∈ G and all x ∈ S for which all

computations involving · are defined. If E ⊆ S and g is in G, I will write E · g to denote {x · g : x ∈ E}.

Remark 3.2. Since the exponentiation is defined in G, it is entirely possible in general for x · g^{i} to be undefined while x · g^{j} is defined for some i < j.

Definition 3.3. A weighted ε-Følner set with respect to Γ is a function μ from a finite subset of S into (0, ∞) which satisfies

∑_{γ∈Γ} ∑_{s∈S} |μ(s · γ) − μ(s)| < ε ∑_{s∈S} μ(s)

where we adopt with the conventions that μ(s) = 0 if s is not in the domain of μ and μ(s · g) = 0 if s · g is undefined. The set {s ∈ S : μ(s) > 0} will be referred to as the support of μ. The function μ induces a finitely supported measure on S, also denoted μ, defined by μ(A) = ∑_{s∈A} μ(s). In the remainder of the paper, the generating set will always be clear from the context and we will often suppress mention of it.

Notice that an ε-Følner set is a set A ⊆ S such that the characteristic function 1_{A} is a weighted ε-Følner set. I will use μ ↾ A to denote μ · 1_{A}. We will need the following property of weighted Følner sets, which is what justifies their added generality in the present paper.

Lemma 3.4. Suppose G acts partially on sets S and T and that μ is a weighted ε-Følner set with respect to the action on S. If h : S → T satisfies that h(s · γ) = h(s) · γ (with both quantities defined) whenever μ(s) + μ(s · γ) > 0 and γ ∈ Γ, then ν(t) = ∑_{h(s)=t} μ(s) (s ranges over S) defines a weighted ε-Følner set (with respect to the action on T).

Proof. Let G, S, T, μ, and ν be as in the statement of the lemma. We need to verify that

∑_{γ∈Γ} ∑_{t∈T} |ν(t · γ) − ν(t)| < εν(T)

Let γ ∈ Γ and t ∈ T be fixed for the moment. First observe that if |ν(t · γ) − ν(t)| > 0, then t · γ is defined. This is because otherwise it must be the case that ν(t) > 0 and hence there must be an s such that h(s) = t and μ(s) > 0. In particular, this implies t · γ is defined.

Next we have that

∑_{h(u)=t·γ} μ(u) = ∑_{h(u)·γ^{−1}=t} μ(u) = ∑_{h(u·γ^{−1})=t} μ(u) = ∑_{h(s)=t} μ(s · γ)

The first equality is justified by the properties of a partial action; the second equality is justified by our assumption that μ(u) > 0 implies h(u · γ^{−1}) = h(u) · γ^{−1} with both quantities defined; the third equality is justified by the properties of a partial action and our assumption that μ(u) > 0 implies u · γ^{−1} is defined. Now it follows that

∑_{γ∈Γ} ∑_{t∈T} |ν(t · γ) − ν(t)| = ∑_{γ∈Γ} ∑_{t∈T} | ∑_{h(s)=t} μ(s · γ) − μ(s)|

≤ ∑_{γ∈Γ} ∑_{s∈S} |μ(s · γ) − μ(s)| < εμ(S) = εν(T).

□

Fix a partial action of G on a set S for the duration of this section. If g is in G, let d_{g} be the minimum length of a word in Γ which evaluates to g. We will need the following lemma.

Lemma 3.5. If ε > 0, μ is a weighted ε-Følner set and g is in G, then

∑_{s∈S} |μ(s · g) − μ(s)| < 2εd_{g}μ(S).

Proof. Let γ_{i} (i < d_{g}) be elements of Γ such that g = ∏_{i<d_{g}} γ_{i}. Let g_{j} = ∏_{i<j} γ_{i}.

∑_{s∈S} |μ(s · g) − μ(s)| ≤ ∑_{s∈S} ∑_{i<d_{g}} |μ(s · g_{i+1}) − μ(s · g_{i})|.

Notice that it may be that s · g_{i+1} is defined even though s · g_{i} is not. If this is the case, however, then

|μ(s · g_{i+1}) − μ(s · g_{i})| = |μ((s · g_{i+1}) · γ_{i}^{−1}) − μ(s · g_{i+1})|.

It follows that

∑_{i<d_{g}} ∑_{s∈S} |μ(s · g_{i+1}) − μ(s · g_{i})| ≤ ∑_{i<d_{g}} ∑_{σ=±1} ∑_{s∈S} |μ(s · γ_{i}^{σ}) − μ(s)|

which is less than 2εd_{g}μ(S). □

We will be interested in the following notion which ensures that a set has small intersection with any Følner set. The definition is motivated by the following simple observation. If μ is a finitely additive invariant probability measure on a group G and E ⊆ G satisfies that, for some g ∈ G, {E · g^{i} : i ∈ ℕ} is a pairwise disjoint family, then μ(E) = 0.

Definition 3.6. If g ∈ G, I ⊆ S, and E ⊆ S, then g marginalizes E off I if for every x ∈ E if x · g^{k} ∈ E and k > 0, then there is an i < k such that x · g^{i} is in I or is undefined. If I is the emptyset, then I will write g marginalizes E.

Definition 3.7. The k-marginal sets for the partial action of G on S are defined recursively as follows. The emptyset is 0-marginal. If there is a decomposition E = ⋃_{i<l} E_{i} ⊆ S and for each i < l, there is a g_{i} ∈ G and a k-marginal set I_{i} such that g_{i} marginalizes E_{i} off I_{i}, then E is (k + 1)-marginal. E ⊆ S is marginal if it is k-marginal for some k < ∞.

Remark 3.8. For a fixed partial action of a group G on a set S, it is immediate from the definition that a finite union of marginal sets is marginal and that a subset of a marginal set is marginal. Additionally, if E ⊆ S and g is in G, then g^{−1} marginalizes E \ (E · g) off E. In particular, if E is marginal, then so is E · g.

We will need the following lemma which shows that marginal sets have small intersections with Følner sets.

Lemma 3.9. Suppose ε > 0 and μ is a weighted ε-Følner set with support A. If E ⊆ S and g marginalizes E off S \ A, then μ(E) < d_{g}εμ(S).

Proof. For each x ∈ E ∩A, let Φ(x) denote the set of all x·g^{i} such that • x · g^{j} is defined and in the support of μ for all j ≤ i and

• μ(x · g^{i+1}) < μ(x · g^{j}) for all j ≤ i. Observe that each Φ(x) is finite and non empty. Because E is marginalized off S\A by g, {Φ(x) : x ∈ E} is a pairwise disjoint family. Observe that for a fixed x ∈ E

μ(x) ≤ ∑_{y∈Φ(x)} μ(y) − μ(y · g) = ∑_{y∈Φ(x)} |μ(y · g) − μ(y)|.

Summing over x ∈ E and applying Lemma 3.5 now gives the desired estimate. □

Lemma 3.10. If E ⊆ S is marginal, then there is a constant C such that if ε > 0 and μ is a weighted ε-Følner set, then μ(E) < Cεμ(S).

Proof. I will prove by induction on k that if E is k-marginal, then the conclusion of the lemma holds. If k = 0, then E is in fact empty and μ(E) = 0. Next suppose that E is (k + 1)-marginal. Let I_{i} (i < l), g_{i} (i < l), and E_{i} (i < l) be such that:

• for each i < l, g_{i} is in G and marginalizes E_{i} off I_{i};

• for each i < l, I_{i} is k-marginal;
• E = ⋃_{i<l} E_{i}.

By our inductive assumption, there are C_{i} (i < l) such that if μ is a weighted ε-Følner set, then μ(I_{i}) < C_{i}εμ(S). Set C = ∑_{i<l} C_{i} + 2d_{g_{i}}. Now if μ is a weighted ε-Følner set,

μ(E) = μ(⋃_{i<l} I_{i})+μ(⋃_{i<l} E_{i}\⋃_{i<l} I_{i}) ≤ ∑_{i<l} C_{i}εμ(S)+2d_{g_{i}}εμ(S) = Cεμ(S).

□

Lemma 3.11. If μ is a weighted ε-Følner set and ν is a function from a finite subset of S into [0, ∞) with ν ≤ μ pointwise and ν(S) ≥ (1 − δ)μ(S) for some δ satisfying 0 < δ < 1, then ν is a weighted (ε + 2|Γ|δ)/(1 − δ)-Følner set.

Proof. Let μ and ν be given as in the statement of the lemma. Fix an s ∈ S and γ ∈ Γ. If ν(s · γ) ≥ ν(s), then

|ν(s · γ) − ν(s)| ≤ μ(s · γ) − μ(s) + μ(s) − ν(s).

If ν(s · γ) ≤ ν(s), then

|ν(s · γ) − ν(s)| ≤ μ(s) − μ(s · γ) + μ(s · γ) − ν(s · γ).

In either case, we have

|ν(s · γ) − ν(s)| ≤ |μ(s · γ) − μ(s)| + μ(s) − ν(s) + μ(s · γ) − ν(s · γ).

Summing over s ∈ S and γ ∈ Γ and combining this with our hypotheses we obtain:

∑_{γ∈Γ} ∑_{s∈S} |ν(s · γ) − ν(s)| < εμ(S) + 2|Γ|δμ(S) ≤ \frac{ε + 2|Γ|δ}{1 − δ} ν(S).

□ Lemma 3.12. If E ⊆ S is marginal and S\E is non-empty, then there is a constant C such that if μ is a weighted ε-Følner set and Cε ≤ 1, then μ ↾ (S \ E) is a weighted Cε-Følner (and in particular the support of μ ↾ (S \ E) is non-empty).

Proof. Let E be marginal and let C_{0} be such that if ε > 0 and μ is a weighted ε-Følner set, then μ(E) < C_{0}εμ(S) and hence μ(S \ E) > C_{0}εμ(S). Set C = 2(1+2C_{0}|Γ|) and suppose that ε > 0 satisfies Cε ≤ 1 and that μ is a weighted ε-Følner set. It follows that C_{0}ε ≤ 1/2 and hence

\frac{ε + 2|Γ|C_{0}ε}{1 − C_{0}ε} ≤ 2(1 + 2|Γ|C_{0})ε.

Observe that the support of μ is not contained in E since μ(E) < C_{0}εμ(S) < μ(S). Hence by applying Lemma 3.11 with δ = C_{0}ε and ν = μ ↾ (S \ E), we obtain that μ ↾ (S \ E) is Cε-Følner. □

Definition 3.13. A subset A ⊆ G is Γ-connected if whenever x and y are in A, there are γ_{i} (i < l) in Γ such that, setting x_{0} = x and x_{i+1} = x_{i} · γ_{i}, then x_{i} is defined for each i ≤ l and y = x_{l}. A maximal Γ-connected subset of a given B ⊆ G is said to be a Γ-connected component of B.

Lemma 3.14. If ε > 0 and μ is a weighted ε-Følner set, then the support of μ contains a Γ-connected component A such that μ ↾ A is ε-Følner.

Proof. Let A_{i} (i < l) enumerate the Γ-connected components of the support of μ. Then since

∑_{i<l} ∑_{γ∈Γ} ∑_{s∈A_{i}} |μ(s · γ) − μ(s)| < ε ∑_{i<l} μ(A_{i}),

there must exist an i < l such that

∑_{γ∈Γ} ∑_{s∈A_{i}} |μ(s · γ) − μ(s)| < εμ(A_{i}).

Since A_{i} is a Γ-connected component, μ(s · γ) = μ ↾ A_{i}(s · γ) whenever s is in A_{i} and therefore A_{i} is ε-Følner. □

This Lemma has the following useful consequence.

Lemma 3.15. Let G be a group with a finite generating set Γ, acting on itself from the right. If A ⊆ G is a ε-Følner set, then there is a B ⊆ G which is an ε-Følner set such that B is Γ-connected, B contains the identity, and |B| ≤ |A|.

Proof. Fix an ε-Følner set A and let C be a Γ-connected component of A which is ε-Følner. Let g be any element of C and define B = g^{−1}C. It is easily verified that C is still Γ-connected and (right) ε-Følner. □

4. Følner sets of trees

Rather than studying Følner sets in F directly, it will be easier to deal with weighted Følner sets in the partial right action of F on 𝒯 which I will refer to as weighted Følner sets of trees. These are essentially weighted right Følner sets consisting of positive elements of F (positive with respect to the infinite presentation mentioned above). The reformulation of the amenability problem for F in terms of the existence of Følner sets of positive elements is well known [6] and part of a more general phenomenon (see [8, 1.28]), but we will need the more precise analytic consequences of the following lemmas.

Lemma 4.1. For every finite binary sequence u, the set E_{u} of all f ∈ F such that u is not extended by an element of R_{f} is marginal with respect to the right action of F on itself.

Proof. Let u be fixed and let g be the element of F which is the identity on sequences which do not extend u and which satisfies

(uˆ v) · g = uˆ (v · x_{0})

for all sequences v for which v · x_{0} is defined.

Now let f be an element of E_{u} and let t be the initial part of u which is in R_{f} (such a t exists by our assumption that u does not have an extension in R_{f}). Let s = t · f^{−1}. That is, s is the element of L_{f} such that

|{a ∈ L_{f} : a <_{lex} s}| = |{b ∈ R_{f} : b <_{lex} t}|

Observe that f · g^{n} can be represented by the tree diagram (A, B) defined by:

A = (L_{f} \ {s}) ∪ {sˆ v : tˆ v ∈ L_{g^{n}}}
B = (R_{f} \ {t}) ∪ {tˆ v : tˆ v ∈ R_{g^{n}}}.

That (A, B) is a reduced tree diagram follows from the characterization mentioned in Section 2 and the following facts:

• (L_{f}, R_{f}) and (L_{g^{n}}, R_{g^{n}}) are reduced;

• |{a ∈ A : a <_{lex} s}| = |{b ∈ B : b <_{lex} t}|;

• the minimum (maximum) elements of the sets

{sˆ v : tˆ v ∈ L_{g^{n}}} and {tˆ v : tˆ v ∈ R_{g^{n}}}

end in 0 (respectively 1).

Consequently u is extended by an element of R_{f·g^{n}} for all n > 0 and hence g marginalizes E_{u}. □

Lemma 4.2. There is a constant C such that if A ⊆ F is a (right) ε-Følner set, then there is a weighted Cε-Følner set of trees supported on a subset of {R_{f} : f ∈ A}.

Proof. Let U consist of all binary sequences of length 4, noting that if T dominates U, then every element of Γ acts properly on T. By Lemma 4.1, the set of f ∈ F such that U is not dominated by R_{f} is marginal. By Lemma 3.12, there is a constant C > 1 such that if A is ε-Følner and

A_{0} = {f ∈ A : U is dominated by R_{f}},

then A_{0} is Cε-Følner. Observe that if γ is a generator and f is in A_{0}, then L_{f·γ} = L_{f} and R_{(f·γ)} = (R_{f}) · γ. We are now finished by Lemma 3.4 applied to h(f) = R_{f} and μ = 1_{A_{0}}. □

5. An operation on elements of 𝒯

In this section I will define an operation ∂ on elements of 𝒯 which reduces their size logarithmically.

If T is in 𝒯 , then the end points of T are the maximum and minimum elements of T. All other elements of T are said to be interior.

Definition 5.1. Suppose that T is in 𝒯 . ∂T is the maximum U ∈ 𝒯 (with respect to the order of domination) which is dominated by T which satisfies the following defining conditions:

(1) U contains extensions of both 01 and 10;

(2) one of the following holds:

• if u <_{lex} v are interior elements of U, then 2|T/u| ≤ |T/v|;

• if u <_{lex} v are interior elements of U, then 2|T/v| ≤ |T/u|;

(3) the minimum (respectively the maximum) interior element of

U terminates with a 1 (respectively with a 0). If no such U exists, then ∂T is defined to be the trivial tree.

The following lemma justifies the use of maximum in the definition of ∂T.

Lemma 5.2. If there is a U satisfying the defining conditions for ∂T, then there is a maximum such U with respect to the order of domination.

Remark 5.3. Condition 3 is necessary to ensure the uniqueness of maximal elements of 𝒯 which satisfying the defining conditions for ∂T.

Proof. Suppose for contradiction that U and V are distinct maximal elements of 𝒯 , each dominated by T, which satisfy the defining conditions of ∂T. First I claim that condition 2 is satisfied in the same way for U and V. For this, it is sufficient to show that if W is in 𝒯 , contains extensions of both 01 and 10, and satisfies the first (second) option of condition 2 for T, then |T/01| < |T/10| (respectively |T/10| < |T/01|). Suppose that W satisfies the first option (the other case is symmetric). Let w be the greatest element of W extending 01 and w′ be the least element of W extending 10. Condition 2 implies that if u_{i} (i ≤ l) are the elements of W which extend 01, then

∑_{i<l} |T/u_{i}| < |T/u_{l}| = |T/w|

and hence |T/01| < 2|T/w|. It follows that

|T/01| < 2|T/w| ≤ |T/w′| ≤ |T/10|.

By replacing U and V with their mirror images if necessary, we will assume that the quantity |T/u| is increasing as u increases in U (or equivalently as u increases in V). Since U△V is non-empty, there is a minimum element of U which either properly extends an element of V or is properly extended by an element of V. By exchanging the roles of U with V if necessary, we may assume the former occurs.

First suppose that the minimum elements of U and V are the same. Let u be the greatest element of U such that it and all of its <_{lex}- predecessors extend an element of V (this extension may not be proper in the case of the predecessors of u). Let v be the element of V which u extends. Define

W = {w ∈ U : w ≤_{lex} u} ∪ {w ∈ V : v <_{lex} w}

and observe that W is in 𝒯 . Notice that |T/u| ≤ |T/v|. Also observe that since U does not dominate V, u is not the maximum element of U and therefore if x is an element of U such that x ≤_{lex} u, then |T/x| ≤ |T/u|. It follows that if x is an interior element of W in {w ∈ U : w ≤_{lex} u} and y is an interior element of W in {w ∈ V : v <_{lex} w}, then x ≤_{lex} u and v <_{lex} y which in turn implies

2|T/x| ≤ 2|T/u| ≤ 2|T/v| ≤ |T/y|.

Since both U and V satisfy condition 2, if x <_{lex} y are interior elements of W and either both are in U or both are in V, then 2|T/x| ≤ |T/y|. It follows that W satisfies condition 2 as well. Since U and V have the same minimum element and both satisfy condition 3, U and V have the same minimal interior element. Thus the minimum interior element of U is also the minimum interior element of W. Also, since V is not dominated by U, u is not the maximum element of W and v is not the maximum element of V. Moreover, it can not be the case that v is the maximum interior element of V. If this were the case, then v = xˆ 0 for some x. It would then follow that xˆ 1 would be the maximum element of V and would have an extension in U. This would imply that U dominates V, which we assumed was not the case. It follows that the maximum interior element of W is the same as the maximum interior element of V. Therefore W satisfies condition 3. But now W satisfies the defining conditions for ∂T, contradicting the maximality of V.

Now suppose that the minimum elements of U and V differ. Let v be such that vˆ 0 is the minimum element of V, noting that vˆ 1 is the minimum interior element of V. Define

W = {w ∈ U : vˆ 0 ⊆ w} ∪ {w ∈ V : vˆ 0 <_{lex} w}

and observe that W is in 𝒯 . Since vˆ 0 is not in U, it must be that both vˆ 00 and vˆ 01 have extensions in U and in particular, the minimum interior element of W is the same as the one of U. Since V is not dominated by U, v ≠ ⟨⟩. Since vˆ 0 is the minimum element of V, the entries of v are all 0 and hence vˆ 1 is not the maximum element of V or of W. Since every element of W not extending vˆ 0 is in V, it follows that the maximum interior element of W is the same as the maximum interior element of V. Therefore W satisfies condition 3. Next suppose that x <_{lex} y are interior elements of W. If both x and y are in U or both are in V, then 2|T/x| ≤ |T/y| follows from the fact that U and V satisfy condition 2 and that the minimum interior element of W is the same as that of U and that the maximum interior element of W is the same as that of V. Next suppose that x is in {w ∈ U : vˆ 0 ⊆ w} and y is in {w ∈ V : vˆ 0 <_{lex} w}. Observe that either y = vˆ 1 or vˆ 1 <_{lex} y. Since vˆ 0 is extended by an element of U, it must be that vˆ 1 is also extended by an element w of U which is in the interior of U. We now have

2|T/x| ≤ |T/w| ≤ |T/vˆ 1| ≤ |T/y|

(This is where the crucial use of condition 3 occurs.) Thus W satisfies condition 2. Again, W satisfies the defining conditions for ∂T, contradicting the maximality of V. □

Lemma 5.4. If ∂T has n elements, then T has more than 2^{n−2} elements.

Proof. There are n − 2 interior elements of ∂T and thus by condition 2 the total number of elements of T which extend an interior element of ∂T is at least ∑_{i=1}^{n−2} 2^{i−1} = 2^{n−2} − 1. Since ∂T is dominated by T, there are at least two elements of T remaining to be counted, putting the total greater than 2^{n−2}. □

Lemma 5.5. If g is in F, T is in 𝒯 , and g acts properly on ∂T, then ∂(T · g) = (∂T) · g.

Proof. First I will verify that if g and T are as in the statement of the lemma, then (∂T) · g is dominated by ∂(T · g). Since the action of g on the elements of ∂T does not change their final digit, (∂T) · g satisfies condition 3. Since the action of g preserves lexicographic order and extension of sequences, (∂T) · g satisfies condition 2. Finally, since the action of g on ∂T is proper, ∂T · g satisfies condition 1. It follows that (∂T) · g is dominated by ∂(T · g).

Next observe that if g acts properly on T, then g^{−1} acts properly on T · g. It follows that ∂(T · g) · g^{−1} is dominated by ∂(T · g · g^{−1}) = ∂T. Since g and g^{−1} are injections, it follows that ∂(T · g) and (∂T) · g have the same elements and hence are equal. □

Definition 5.6. Let ℰ be the set of all T ∈ 𝒯 such that neither of the following inequalities hold:

(+) |T/001| < |T/01| < |T/10|
(−) |T/001| > |T/01| > |T/10|

Define

𝒯 ^{+} = {T ∈ 𝒯 : |T/001| < |T/01| < |T/10|}
𝒯 ^{−} = {T ∈ 𝒯 : |T/001| > |T/01| > |T/10|}

Lemma 5.7. ℰ is marginal.

Proof. Define the following elements of F:

           a = \begin{cases}000 ↦ 000 \\ 0010 ↦ 001 \\ 0011 ↦ 0100 \\ 01 ↦ 0101 \\ 100 ↦ 011 \\ 101 ↦ 10 \\ 11 ↦ 11 \end{cases} b = \begin{cases}000 ↦ 000 \\ 0010 ↦ 001 \\ 0011 ↦ 01 \\ 01 ↦ 100 \\ 10 ↦ 101 \\ 11 ↦ 11 \end{cases}

(i.e. a = x_{0}^{2}x_{1}x_{4}x_{2}^{−2}x_{0}^{−2} and b = x_{0}^{2}x_{1}x_{3}^{−1}x_{0}^{−2}). Define

ℰ_{a} = {T ∈ 𝒯 : max(|T/001|, |T/10|) = |T/01|}
ℰ_{b} = {T ∈ 𝒯 : max(|T/001|, |T/10|) < |T/01|}

Notice that T is in ℰ_{max} = ℰ_{a} ∪ ℰ_{b} if and only if

|T/01| = max(|T/001|, |T/01|, |T/10|).

Furthermore, if T is in ℰ \ ℰ_{max}, then

|T/01| = min(|T/001|, |T/01|, |T/10|).

Observe that for all T ∈ 𝒯 such that T · a is defined, we have:

|(T · a)/001| = |T/0010| < |T/001|
|(T · a)/01| = |T/0011| + |T/01| + |T/100| > |T/01|
|(T · a)/10| = |T/101| < |T/10|

Therefore if T · a is in (ℰ_{a} ∪ ℰ_{b}) · a, then

max(|(T · a)/001|, |(T · a)/10|) < |(T · a)/01|

and hence T · a is in ℰ_{b}. Since ℰ_{a} is disjoint from ℰ_{b}, this shows that a marginalizes ℰ_{a}.

Observe that for all T ∈ 𝒯 such that T · b is defined, we have:

|(T · b)/001| = |T/0010| < |T/001|
|(T · b)/01| = |T/0011| < |T/001|
|(T · b)/10| = |T/01| + |T/10| > |T/10|

Define

ℛ = {T ∈ 𝒯 : max(|T/001|, |T/01|) < |T/10|}.

The above inequalities show that (ℰ_{b} ∪ ℛ) · b ⊆ ℛ. Since ℰ_{b} is disjoint from ℛ, this shows that b marginalizes ℰ_{b}.

Clearly the elements of ℰ \ ℰ_{max} lie in one of the following sets:

ℰ_{1} = {T ∈ 𝒯 : |T/001| > |T/01| = |T/10|}
ℰ_{2} = {T ∈ 𝒯 : |T/01| < min(|T/001|, |T/10|)}
ℰ_{3} = {T ∈ 𝒯 : |T/001| = |T/01| < |T/10|}

The proof will therefore be complete once it has been show that x_{0} marginalizes ℰ_{1} ∪ ℰ_{2} off ℰ_{max} and that x_{0} marginalizes ℰ_{3} off ℰ_{max}.

If T is in 𝒯 , then

|(T · x_{0})/01| = |T/001|
|(T · x_{0})/10| = |T/01|

If T is in 𝒯 ^{−} ∪ ℰ_{1} ∪ ℰ_{2}, then |T/001| > |T/01| and thus |(T · x_{0})/01| > |(T · x_{0})/10|. This yields:

(𝒯 ^{−} ∪ ℰ_{1} ∪ ℰ_{2}) · x_{0} ⊆ 𝒯 ^{−} ∪ ℰ_{max}

If T is in ℰ_{3}, then |T/001| = |T/01| and thus |(T ·x_{0})/01| = |(T ·x_{0})/10|. This yields:

ℰ_{3} · x_{0} ⊆ ℰ_{1} ∪ ℰ_{max}

This shows that x_{0} marginalizes ℰ_{1}∪ℰ_{3} off ℰ_{max} and that x_{0} marginalizes ℰ_{3} off ℰ_{max}. □

Definition 5.8. Let ℰ^{∗} be the set of all T ∈ 𝒯 such that neither of the following inequalities hold:

(2×) 2|T/001| ≤ |T/01| ≤ \frac{1}{2}|T/10|

(\frac{1}{2}×) \frac{1}{2}|T/001| ≥ |T/01| ≥ 2|T/10|

Observe that if T is not in ℰ^{∗} and T contains extensions of both 01 and 10, then ∂T is not the trivial tree since {00, 01, 10, 11} is then an element of 𝒯 which satisfies the defining conditions for ∂T.

Lemma 5.9. If T satisfies (+) and γ is a generator, then either T · γ is undefined, T · γ is in ℰ, or else T · γ satisfies (+) (and similarly for (−)). In particular, if 𝒜 ⊆ 𝒯 \ ℰ^{∗} is Γ-connected, then either all elements of 𝒜 satisfy (2×) or all elements of 𝒜 satisfy (\frac{1}{2}×).

Proof. This follows from the following equalities which hold whenever the relevant action is defined:

T/001 = (T · x_{0})/01
T/01 = (T · x_{0})/10
T/001 = (T · x_{1}^{±})/001
T/01 = (T · x_{1}^{±})/01.
□

Lemma 5.10. ℰ^{∗} is marginal.

Remark 5.11. Lemmas 5.9 and 5.10 have non trivial qualitative consequences for F -invariant probability measures on 𝒯 . If μ is an F - invariant probability measure on 𝒯 , then μ(ℰ^{∗}) = 0. Furthermore, μ(𝒯 ^{+}△(𝒯 ^{+} · Γ)) = 0 and therefore if μ is additionally ergodic, then it must be that μ assigns measure 1 either to the set of elements of 𝒯 which satisfy (2×) or else to the set of those which satisfy (\frac{1}{2}×).

Proof. Define the following elements of F:

             c = \begin{cases}00 ↦ 0 \\ 01 ↦ 100 \\ 10 ↦ 101 \\ 11 ↦ 11 \end{cases} d = \begin{cases}000 ↦ 00 \\ 001 ↦ 010 \\ 01 ↦ 011 \\ 1 ↦ 1 \end{cases}

(i.e. c = x_{0}x_{1}^{−1} and d = x_{0}^{2}x_{1}^{−1}x_{0}^{−1}). Define

𝒳 = {T ∈ 𝒯 ^{+} : 2|T/01| ≤ |T/10|}
ℰ_{4} = {T ∈ 𝒯 ^{+} : 2|T/01| > |T/10|}
ℰ_{5} = {T ∈ 𝒯 ^{+} : 2|T/001| > |T/01|}.

I first claim that (𝒳 ∪ ℰ_{4}) · c ⊆ 𝒳 ∪ ℰ. To see this, suppose that T is in 𝒯 ^{+}. Then

2|(T · c)/01| = 2|T/001| < |T/01| + |T/10| = |(T · c)/10|.

and hence if T · c is in 𝒯 ^{+}, it is in 𝒳 . Since T · c is not in 𝒯 ^{−}, it is either in 𝒯 ^{+} or in ℰ. This proves the claim. Since ℰ_{4} is disjoint from 𝒳 , it follows that c marginalizes ℰ_{4} off ℰ and hence that ℰ_{4} is marginal according to Lemma 5.7. Also, by Lemma 5.9, ℰ_{5} · x_{0} ⊆ ℰ_{4} ∪ ℰ and therefore ℰ_{5} is marginal because x_{0} marginalizes ℰ_{5} off ℰ_{4} ∪ ℰ.

Next define

𝒴 = {T ∈ 𝒯 ^{−} : |T/01| ≥ 2|T/10|}
ℰ_{6} = {T ∈ 𝒯 ^{−} : |T/01| < 2|T/10|}
ℰ_{7} = {T ∈ 𝒯 ^{−} : |T/001| < 2|T/01|}.

Arguing as above, (𝒴 ∪ℰ_{6})·d ⊆ 𝒴 ∪ℰ and hence d marginalizes ℰ_{6} off ℰ. Also ℰ_{7} ·x_{0} ⊆ ℰ_{6} ∪ℰ and consequently both ℰ_{6} and ℰ_{7} are marginal. Since ℰ^{∗} = ℰ ∪ ⋃_{i=4}^{7} ℰ_{i}, ℰ^{∗} is marginal and the proof is complete. □

Lemma 5.12. The set

{T ∈ 𝒯 : Γ does not act properly on ∂T }

is marginal.

Proof. First observe that

1^{i+1}0 · x_{0}^{−i} = 10
1^{i}0 · x_{0}^{−i} = 01.

Hence if T is in 𝒯 and T · x_{0}^{−i} is defined, then

|T/1^{i}0| = |(T · x_{0}^{−i})/01|
|T/1^{i+1}0| = |(T · x_{0}^{−i})/10|.

By Lemma 5.10, ℰ^{∗} is marginal. Also, it follows immediately from the definitions that for each f in F, the set of all T ∈ 𝒯 for which T · f is undefined is marginalized off the emptyset by f. By Remark 3.8, it follows that

ℰ^{∗∗} = ⋃_{i=0}^{16} ℰ^{∗} · x_{0}^{i} ∪ {T ∈ 𝒯 : ∃i ≤ 16 (T · x_{0}^{−i} is undefined)}

is marginal as well. Observe that if T is not in ℰ^{∗∗}, then {T · x_{0}^{−i} : 0 ≤ i ≤ 16} is a Γ-connected subset of 𝒯 \ℰ^{∗} and therefore by Lemma 5.9, one of the following two assertions holds:

(∀i < 16) 2|T/1^{i}0| < |T/1^{i+1}0|
(∀i < 16) 2|T/1^{i+1}0| < |T/1^{i}0|.

That is, the set of all T which satisfy neither of these assertions is marginal.

Now let U consist of all binary sequences of length 4, noting that U satisfies conditions 1 and 3. Furthermore if T is an element of 𝒯 such that ∂T dominates U, then every element of Γ acts properly on ∂T. Set R = {1^{i}0 : i < 14} ∪ {1^{15}} and let g denote the element of F defined by the tree diagram (U, R). If U fails to satisfy condition 2 with respect to T, then U · g fails to satisfy condition 2 with respect to T ·g and, in particular, T ·g must be in ℰ^{∗∗}. Therefore the set of T such that U does not satisfy the defining conditions for ∂T is marginalized by g off ℰ^{∗∗}. □

Lemma 5.13. There is a constant C such that if μ is a weighted ε-Følner set of trees and Cε ≤ 1, then there is a weighted Cε-Følner set of trees which is supported on a subset of

{∂T : (μ(T) > 0) ∧ (∂T is non trivial) ∧ (Γ acts properly on ∂T)}.

Proof. By Lemmas 3.12 and 5.12, there is a C such that if μ is a weighted ε-Følner set of trees and

𝒜 = {T ∈ 𝒯 : (μ(T) > 0) ∧ (Γ acts properly on ∂T)},

then μ ↾ 𝒜 is Cε-Følner. Now let such a μ be given and define 𝒜 as above. By Lemma 5.5,

(∂T) · γ = ∂(T · γ)

whenever γ is a generator and T is in 𝒜. Applying Lemma 3.4 to μ ↾ 𝒜 and h = ∂ gives the desired conclusion. □

Now we are ready to complete the proof of Theorem 1.1. I will first prove the following claim.

Claim 5.14. There exists a constant K > 1 such that if A ⊆ F is a K^{−n}-Følner set, then A contains an element with a tree diagram whose trees each contain at least exp_{n}(0) elements.

Proof. By Lemmas 4.2 and 5.13 there is a constant K > 1 such that:

(1) if A ⊆ F is an ε-Følner set and Kε ≤ 1, then there is a weighted Kε-Følner set of trees μ with support contained in {R_{f} : f ∈ A}; (2) if μ is a weighted ε-Følner set of trees and Kε ≤ 1, then there

is a weighted Kε-Følner set of trees ν which is supported on a subset of

{∂T : (μ(T) > 0) ∧ (∂T is non trivial) ∧ (Γ acts properly on T)}

Thus by (1), if A ⊆ F is K^{−(n+1)}-Følner, then there is an A′ ⊆ A such that {R_{f} : f ∈ A′} is an K^{−n}-Følner set. By applying (2) n times and observing that weighted Følner sets have non-empty supports, we have that there is an f ∈ A such that ∂^{n}R_{f} is non trivial. Let k_{i} = |∂^{n−i}R_{f}| and observe that by Lemma 5.4, k_{0} ≥ 4 and k_{i+1} > 2^{k_{i}−2}. It follows by induction that exp_{i}(0) + 2 < k_{i} and in particular that R_{f} contains at least exp_{n}(0) elements. □

By Theorem 1 and Proposition 2 of [1], if f is in F, then the distance from f to the identity is at least (k − 2)/3, where k is the common cardinality of the trees in the reduced tree diagram for f. In particular, if k is at least 3 — the minimum cardinality of a tree in any diagram representing a non-identity element — then the distance is at least k/16. It is easily verified that for all n > 0, \frac{1}{16} exp_{4n}(0) ≥ exp_{n}(0). If K is a constant which satisfies the conclusion of Claim 5.14, then define C = K^{4}.

I now claim that if A is C^{−n} Følner, then |A| ≥ exp_{n}(0). To see this, let A ⊆ F be C^{−n}-Følner. By Lemma 3.15, there is a finite A′ ⊆ F which is Γ-connected, C^{−n}-Følner, and satisfies |A′| ≤ |A|. Since A′ is K^{−4n}-Følner, our choice of K implies that A′ has an element a whose reduced tree diagram contains trees with at least exp_{4n}(0) leaves. It follows that the distance from a to the identity is at least \frac{1}{16} exp_{4n}(0) ≥ exp_{n}(0). Since A′ is Γ-connected, it must contain at least exp_{n}(0) elements and thus |A| ≥ |A′| ≥ exp_{n}(0), establishing Theorem 1.1.

References

[1] J. Burillo, S. Cleary, and M. I. Stein. Metrics and embeddings of generalizations of Thompson’s group F. Trans. Amer. Math. Soc., 353(4):1677–1689 (electronic), 2001.

[2] J. W. Cannon, W. J. Floyd, and W. R. Parry. Introductory notes on Richard Thompson’s groups. Enseign. Math. (2), 42(3-4):215–256, 1996.

[3] Anna Erschler. On isoperimetric profiles of finitely generated groups. Geom. Dedicata, 100:157–171, 2003.

[4] Anna Erschler. Piecewise automatic groups. Duke Math. J., 134(3):591–613, 2006.

[5] S. M. Gersten and John R. Stallings, editors. Combinatorial group theory and topology, volume 111 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 1987. Papers from the conference held in Alta, Utah, July 15–18, 1984.

[6] R. I. Grigorchuk. Growth and amenability of a semigroup and its group of quotients. In Proceedings of the International Symposium on the Semigroup Theory and its Related Fields (Kyoto, 1990), pages 103–108, Matsue, 1990. Shimane Univ.

[7] Misha Gromov. Entropy and isoperimetry for linear and non-linear group actions. Groups Geom. Dyn., 2(4):499–593, 2008.

[8] Alan L. T. Paterson. Amenability, volume 29 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 1988.

[9] Letter from Richard Thompson to George Francis, dated September 26, 1973.

Department of Mathematics, Cornell University, Ithaca, NY 14853– 4201, USA

E-mail address: justin@math.cornell.edu