A NONAMENABLE FINITELY PRESENTED GROUP OF PIECEWISE PROJECTIVE HOMEOMORPHISMS

YASH LODHA AND JUSTIN TATCH MOORE

This paper is dedicated to the memory of William Thurston (1946–2012).

Abstract. In this article we will describe a finitely presented subgroup of the group of piecewise projective homeomorphisms of the real projective line. This in particular provides a new example of a finitely presented group which is nonamenable and yet does not contain a nonabelian free subgroup. It is in fact the first such example which is torsion free. We will also develop a means for representing the elements of the group by labeled tree diagrams in a manner which closely parallels Richard Thompson’s group F.

1. Introduction

The notion of an amenable group was introduced by John von Neumann as an abstract means for preventing the existence of paradoxical decompositions of the group: a discrete group is amenable if it admits a finitely additive translation invariant probability measure. At the heart of Banach and Tarski’s paradoxical decomposition of the sphere is the existence of a paradoxical decomposition of the free group on two generators. Since subgroups of amenable groups are easily seen to be amenable, it is natural to ask whether every nonamenable group contains a free group on two generators. Day was the first to pose this problem in print [7], where he attributed it to John von Neumann.

In 1980, Ol’shanskii solved the von Neumann-Day problem by producing a counterexample [16]. Soon after, Adyan showed that certain Burnside groups are also counterexamples [1][2]. These examples are not finitely presented and the restriction of the von Neumann-Day problem to the class of finitely presented groups remained open until Ol’shanskii and Sapir constructed an example in 2003 [17]. Shortly after, Ivanov published another finitely presented counterexample [11], that is somewhat simpler but similar in spirit to the Ol’shanskii-Sapir example. Both examples were produced by elaborate inductive constructions and are difficult to analyze. It is also interesting to note that both of these examples are based on the constructions of nonamenable torsion groups (they are torsion-by-cyclic) and in particular are far from being torsion free.

In his recent article [14], Monod produced a new family of counterexamples to the von Neumann-Day problem. They are all subgroups of the group H consisting of all piecewise projective transformations of the real projective line which fix the point at infinity. Monod demonstrated that H does not contain nonabelian free subgroups by adapting the method of Brin and Squier [4].

1991 Mathematics Subject Classification. Primary: 43A07; Secondary: 20F05.

Key words and phrases. amenable, finitely presented, free group, piecewise, projective, Thompson’s group, torsion free.

This research was supported in part by NSF grant DMS–1262019. The second author would like to thank Alain Valette for a number of helpful conversations concerning Monod’s example in [14] which took place while the author was visiting Université de Neuchâtel in January of 2013.

In this article, we will isolate a finitely presented nonamenable subgroup of Monod’s group H. To our knowledge, this provides the first finitely presented torsion free counterexample to the von Neumann-Day problem. Moreover, our presentations for this group are very explicit: it has a presentation with 3 generators and 9 relations as well as a natural infinite presentation. The group is generated by a(t) = t + 1 together with the following two homeomorphisms of ℝ:

b(t) = \begin{cases}t & if t ≤ 0 \\ \frac{t}{1−t} & if 0 ≤ t ≤ \frac{1}{2} \\ 3 − \frac{1}{t} & if \frac{1}{2} ≤ t ≤ 1 \\ t + 1 & if 1 ≤ t \end{cases} c(t) = \begin{cases}\frac{2t}{1+t} & if 0 ≤ t ≤ 1 \\ t & otherwise \end{cases}

The main result of this paper is the following.

Theorem 1.1. The group G_{0} generated by the functions a(t), b(t), and c(t) is nonamenable and finitely presented.

Since it is a subgroup of H, G_{0} does not contain a nonabelian free subgroup. We claim no originality in our proof that G_{0} is nonamenable; this is a routine modification of the methods of [14] which in turn relies on [9] [6].

It is interesting to note that, by an unpublished result of Thurston, a(t) and b(t) generate the subgroup P (ℤ) ≤ H, consisting of those homeomorphisms which are C^{1} and piecewise PSL_{2}(ℤ). He moreover observed that this group is isomorphic to Richard Thompson’s group F. Remarkably, the methods of [14] easily show that t ↦ t+1/2 and b(t) generate a nonamenable group, although at present it is unclear whether this group is finitely presented. In spite of the apparent strong parallels between the groups ⟨a, b, c⟩ and ⟨t ↦ t+1/2, b⟩ and Thompson’s F, however, neither [14] nor the present article seems to shed any light on whether or not F is amenable.

The paper is organized as follows. Section 2 contains a review of some of the preliminaries we will need later in the paper. Both an infinite and a finite presentation are described in Section 3 and it is demonstrated there how to prove that the finite presentation generates the infinite presentation. Tree diagrams for elements of the group are developed in Section 4. Finally, Section 5 contains a proof that the relations isolated in Section 3 suffice to give a presentation for ⟨a, b, c⟩.

2. Preliminaries

Our analysis of the group G_{0} will closely parallel the now well-established analysis of Thompson’s group F. The group F was first introduced in [13] where, among other things, it was established that F is finitely presented. We direct the reader to the standard reference [3] for the properties of F; additional information can be found in [5]. We shall mostly follow the notation and conventions of [3] [4].

We will take ω to include 0; in particular all counting will start at 0. Let 2^{ω} denote the collection of all infinite binary sequences and let 2^{<ω} denote the collection of all finite binary sequences. If i ∈ ω and u is a binary sequence of length at least i, we will let u ↾ i denote the initial part of u of length i. If s and t are finite binary sequences, then we will write s ⊆ t if s is an initial segment of t and s ⊂ t if s is a proper initial segment of t. If neither s ⊆ t nor t ⊆ s, then we will say that s and t are incompatible. The set 2^{<ω} is equipped with a lexicographic order defined by s <_{lex} t if t ⊂ s or s and t are incompatible and s(i) < t(i) where i is minimal such that s(i) ≠ t(i). If s and t are incompatible finite binary sequences such that s <_{lex} t and yet there is no u incompatible with both s and t such that s <_{lex} u <_{lex} t, then we say that s and t are consecutive.

If s and t are two sequences (s is finite but t may be infinite), then s^{⌢}t will be used to denote the concatenation of s and t. In some circumstances, ^{⌢} will be omitted; for instance we will often write s01 instead of s^{⌢}01. If ξ and η are infinite sequences, then we will say that ξ and η are tail equivalent if there are s, t, and ζ such that ξ = s^{⌢}ζ and η = t^{⌢}ζ. Given an infinite sequence s, s̃ is the sequence satisfying s̃(i) = 0 if s(i) = 1 and s̃(i) = 1 if s(i) = 0. The constant sequences 000..., 111... are denoted by ¯0, ¯1 respectively.

Let T denote the collection of all finite rooted ordered binary trees. More concretely, we view elements T of T as prefix sets — those sets T of finite binary sequences with the property that every infinite binary sequence has a unique initial segment in T. Observe that each element of T is finite and, for each m, there are only finitely many elements of T with m elements. There is also a natural partial ordering on T , which we will refer to as dominance: if every element of S has an extension in T, then we say that S is dominated by T. Notice that if S is dominated by T, then |S| ≤ |T |. If A is a finite set of binary sequences, then there is a unique minimal element T of T (with respect to the order of dominance) such that every element of A has an extension in T.

A tree diagram is a pair (L, R) of elements of T with the property that |L| = |R|. A tree diagram describes a map of infinite binary sequences as follows:

s_{i}^{⌢}ξ ↦ t_{i}^{⌢}ξ

where s_{i} and t_{i} are the ith elements of L and R, respectively, in the lexicographic order and ξ is any binary sequence. The collection of all such functions from 2^{ω} to 2^{ω} defined in this way is Thompson’s group F. Notice that the function associated to a tree diagram is also defined on any finite binary sequence u such that u has a prefix in L. We will follow [4] and write s.f for the result of applying a function f to the input s. Notice that this defines a partial action of F on the set of finite binary sequences: s.(fg) = (s.f).g, provided that all quantities are defined.

Thompson’s group F is generated by the following functions.

ξ.a = \begin{cases}0η & if ξ = 00η \\ 10η & if ξ = 01η \\ 11η & if ξ = 1η \end{cases} ξ.b = \begin{cases}0η & if ξ = 0η \\ 10η & if ξ = 100η \\ 110η & if ξ = 101η \\ 111η & if ξ = 11η \end{cases}

Recall that the real projective line is the set of all lines in ℝ^{2} which pass through the origin. Such lines can naturally be identified with elements of ℝ ∪ {∞} via the x-coordinate of their intersection with the line y = 1. In this article it will be useful to represent points on the real projective line by binary sequences derived from their continued fractions expansion. Define a map Φ : 2^{ω} → ℝ ∪ {∞} as follows. First define ϕ : 2^{ω} → [0, ∞] by

ϕ(0ξ) = \frac{1}{1 + \frac{1}{ϕ(ξ)}} ϕ(1ξ) = 1 + ϕ(ξ)

and set

Φ(0ξ) = −ϕ(ξ̃) Φ(1ξ) = ϕ(ξ).

This function is one-to-one except at ξ which are eventually constant. On sequences which are eventually constant, the map is two-to-one: Φ(s0¯1) = Φ(s1¯0) and Φ(¯0) = Φ(¯1) = ∞.

In the mid 1970s, Thurston observed that the functions a and b from the introduction become the generators a and b for Thompson’s group F defined above when “conjugated” by Φ. Moreover, the elements of F correspond exactly to those homeomorphisms f of ℝ which are piecewise PSL_{2}(ℤ) and which have continuous derivatives. We will generally take the viewpoint that Φ provides just another way of describing the real projective line, just as decimal expansions allow us to describe real numbers. In particular, we will regard the definitions of a and b in the introduction and the definitions given above in terms of sequences as being two ways of describing the same functions.

Since we will be proving that a group is finitely presented, it will be necessary to deal with formal words over formal alphabets. If G is a group and A is a subset of G, an A-word is a finite sequence of elements of the set A × (ℤ \ {0}). We typically denote a pair (a, n) as a^{n}, but we emphasize here that it is formally distinct from the group element a^{n}. The word length of an A-word is the sum of the absolute values of the exponents which occur in it.

In order to prove the nonamenability of G_{0}, we will need to employ Zimmer’s theory of amenable equivalence relations. Let X be a Polish space and let E ⊆ X^{2} be an equivalence relation which is Borel and which has countable equivalence classes. E is μ-amenable if, after discarding a μ-measure 0 set, E is the orbit equivalence relation of an action of ℤ. (This is not the standard definition, but it is equivalent by [6].) We will need the following two results.

Theorem 2.1. [21] If Γ is a countable amenable group acting by Borel automorphisms on a Polish space X and μ is any σ-finite Borel measure on X, then the orbit equivalence relation is μ-amenable.

Theorem 2.2. [9] (see also [15]) If Γ is a countable dense subgroup of PSL_{2}(ℝ), then the action of Γ on the real projective line induces an orbit equivalence relation which is not amenable with respect to Lebesgue measure.

We refer the reader to [12] and [15] for further information on amenable equivalence relations.

We will conclude this section by sketching a proof that the group G_{0} from the introduction is nonamenable. Let K denote the subgroup of PSL_{2}(ℝ) generated by the matrices

( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) ( \begin{matrix}\sqrt{2} & 0 \\ 0 & \frac{1}{\sqrt{2}} \end{matrix} ) .

Viewed as fractional linear transformations, K is generated by t + 1, 2t, and −1/t. Since K contains PSL_{2}(ℤ) as a proper subgroup, it is dense in PSL_{2}(ℝ) and hence by Theorem 2.2, the orbit equivalence relation of its action on the real projective line is not amenable with respect to Lebesgue measure. By Theorem 2.1, it is sufficient to show that G_{0} induces the same orbit equivalence relation on ℝ \ ℚ. To see this, it can be verified that the element bca^{−1}c^{−1}a coincides with t ↦ 2t on the interval [0, 1]. From this and the identity 2(r−n)+2n = 2r it follows that the orbits of G_{0} include the orbits of the action of ⟨t ↦ t+1, t ↦ 2t⟩ on ℝ\ℚ. Finally aba and ba^{−3} coincide with t ↦ −1/t on the intervals [−1, −1/2] and [1/2, 1] respectively. The assertion about orbits now follows from the fact that for any r ∈ ℝ, there is a n ∈ ℤ such that 2^{n}r is in [−1, −1/2] ∪ [1/2, 1] and (2^{n})(−1/(2^{n}r)) = −1/r.

3. The presentations

In this section we will describe both a finite and infinite presentation of the group G_{0} defined in the introduction. We start with the following two primitive functions defined on infinite binary sequences:

ξ.x = \begin{cases}0η & if ξ = 00η \\ 10η & if ξ = 01η \\ 11η & if ξ = 1η \end{cases} ξ.y = \begin{cases}0(η.y) & if ξ = 00η \\ 10(η.y^{−1}) & if ξ = 01η \\ 11(η.y) & if ξ = 1η \end{cases}

(The function x is nothing but the function a described in the previous section.) From these functions, we define families of functions x_{s} (s ∈ 2^{<ω}) and y_{s} (s ∈ 2^{<ω}) which act just as x and y, but localized to those binary sequences which extend s.

ξ.x_{s} = \begin{cases}s^{⌢}(η.x) & if ξ = s^{⌢}η \\ ξ & otherwise \end{cases} ξ.y_{s} = \begin{cases}s^{⌢}(η.y) & if ξ = s^{⌢}η \\ ξ & otherwise \end{cases}

If s is the empty-string, it will be omitted as a subscript. The functions x_{s} are elements of F and, by the discussion in the previous section, define partial maps on 2^{<ω}. Notice that t.x_{s} is defined exactly when t has a prefix in {s00, s01, s1} or else is incompatible with s (equivalently t.x_{s} is defined exactly when t is not an initial part of s0).

The relationship between these functions and the functions a, b, and c of the introduction is expressed by the following proposition.

Proposition 3.1. For all ξ in 2^{ω}, ϕ(ξ.y) = 2ϕ(ξ) and

Φ(ξ).a = Φ(ξ.x)  Φ(ξ).b = Φ(ξ.x_{1})  Φ(ξ).c = Φ(ξ.y_{10}).

Remark 3.2. The effects of doubling on continued fractions, which is closely related to the identity Φ(ξ).c = Φ(ξ.y_{10}), was first worked out by Hurwitz [10]. Raney introduced transducers for making calculations such as these in [19].

Proof. We will only prove the identities ϕ(ξ.y) = 2ϕ(ξ) and Φ(ξ).c = Φ(ξ.y_{10}); the remaining verifications are similar and left to the reader. We will first verify the identity ϕ(ξ.y) = 2ϕ(ξ). Observe that, since ϕ and y are continuous, it suffices to verify this equality for sequences which are eventually constant. The proof is now by induction on the minimum digit beyond which the sequence is constant. For the base case we have:

ϕ(¯0.y) = ϕ(¯0) = 0 = 2 · 0 ϕ(¯1.y) = ϕ(¯1) = ∞ = 2 · ∞.

In the inductive step, we have three cases:

ϕ(00ξ.y) = ϕ(0(ξ.y)) = \frac{1}{1 + \frac{1}{ϕ(ξ.y)}} = \frac{1}{1 + \frac{1}{2ϕ(ξ)}} = \frac{2}{2 + \frac{1}{ϕ(ξ)}} = 2ϕ(00ξ)

ϕ(01ξ.y) = ϕ(10(ξ.y^{−1})) = 1+ \frac{1}{1 + \frac{1}{ϕ(ξ.y^{−1})}} = 1+ \frac{1}{1 + \frac{2}{ϕ(ξ)}} = \frac{2}{1 + \frac{1}{1+ϕ(ξ)}} = 2ϕ(01ξ)

ϕ(1ξ.y) = ϕ(11(ξ.y)) = 2 + ϕ(ξ.y) = 2 + 2ϕ(ξ) = 2(1 + ϕ(ξ)) = 2ϕ(1ξ).

Next we turn to the verification of Φ(ξ).c = Φ(ξ.y_{10}). Observe that if ξ does not extend 10, then Φ(ξ) is outside the interval (0, 1) and we have Φ(ξ).c = Φ(ξ) = Φ(ξ.y_{10}). The remaining case follows from the identity we have already established, noting that \frac{2t}{t+1} = \frac{2}{1+1/t}:

Φ(10ξ).c = (\frac{1}{1 + \frac{1}{ϕ(ξ)}} ) .c = \frac{2}{2 + \frac{1}{ϕ(ξ)}} = \frac{1}{1 + \frac{1}{2ϕ(ξ)}} = \frac{1}{1 + \frac{1}{ϕ(ξ.y)}} = Φ(10ξ.y_{10}).

□

From this point forward, we will identify a, b, and c with x, x_{1}, and y_{10}, respectively and suppress all mention of Φ.

We now return to our discussion of the generators. It is straightforward to verify that the following relations are satisfied by these elements, where s and t are finite binary sequences:

(1) x_{s}^{2} = x_{s0}x_{s}x_{s1};

(2) if t.x_{s} is defined, then x_{t}x_{s} = x_{s}x_{t.x_{s}};
(3) if t.x_{s} is defined, then y_{t}x_{s} = x_{s}y_{t.x_{s}};
(4) if s and t are incompatible, then y_{s}y_{t} = y_{t}y_{s};
(5) y_{s} = x_{s}y_{s0}y_{s10}^{−1}y_{s11}.

We will refer to these relations collectively as R. The first two groups of relations are known to give a presentation for F: the function x_{1^{n}} corresponds to the nth generator in the standard infinite presentation of F. We will use F to denote the group generated by {x_{s} : s ∈ 2^{<ω}} (this presentation of F first appeared in [8]).

First observe that if s and t are incompatible then x_{s} commutes with both x_{t} and y_{t}. Also notice that any y_{s} is conjugate by an element of F to exactly one of y, y_{0}, y_{1}, or y_{10} (to see uniqueness, observe that whether ¯0 or ¯1 are in the closure of the support of g is invariant under conjugation and hence none of y_{0}, y_{10}, and y_{1} are conjugate to eachother). Define X = {x_{s} : s ∈ 2^{<ω}}, Y = {y_{s} : s ∈ 2^{<ω}}, and Y_{0} to be the set of all y_{s} such that s is not a constant binary sequence. Observe that Y_{0} consists of those elements of Y which are conjugate to y_{10} by an element of F. The group G_{0} defined in the introduction is therefore generated by the (redundant) generating set S_{0} = X ∪ Y_{0}.

Let R_{0} be those relations in R which only refer to generators in S_{0} and let G be the group generated by S = X ∪ Y. The rest of the paper will focus on proving the following theorem.

Theorem 3.3. The relations R give a presentation for G and the relations R_{0} give a presentation for G_{0}. Moreover, G and G_{0} admit finite presentations.

In the remainder of this section, we will prove that G and G_{0} are finitely presented assuming that R and R_{0} give presentations for these groups. The finite generating sets for these groups are {x, x_{1}, y_{0}, y_{1}, y_{10}} and {a, b, c} = {x, x_{1}, y_{10}}, respectively. Before proceeding, it will be necessary to define the other generators as words in terms of these generators; these definitions will be compatible with equalities which hold in G. We begin by declaring

y = xy_{0}y_{10}^{−1}y_{11}  x_{0} = x^{2}x_{1}^{−1}x^{−1}  x_{10} = x_{1}^{2}x^{−1}x_{1}^{−1}xx_{1}^{−1}.

Observe that 0.x^{−n} = 0^{n+1} and 1.x^{n} = 1^{n+1} and set

x_{0^{n+1}} = x^{n}x_{0}x^{−n} x_{1^{n+1}} = x^{−n}x_{1}x^{n}

y_{0^{n+1}} = x^{n}y_{0}x^{−n} y_{1^{n+1}} = x^{−n}y_{1}x^{n}.

If s ∈ 2^{<ω} is nonconstant, fix a word f_{s} in {x, x_{1}} such that 10.f_{s} = s and define

x_{s} = f_{s}^{−1}x_{10}f_{s} y_{s} = f_{s}^{−1}y_{10}f_{s}.

Next we note the following two standard properties of F.

Proposition 3.4. [13] If g is any element of F and s is a finite binary sequence such that s.g is defined, then x_{s}g = gx_{s.g}. In particular if g, x_{s} and x_{s.g} are expressed as words in {x, x_{1}}, then the above equality is derivable from the relations in (1) and (2) above.

Proposition 3.5. If u <_{lex} v are incompatible binary sequences, then there is a g in F and s <_{lex} t each of length at most 3 such that s.g = u and t.g = v.

Proof. (sketch) If u <_{lex} v are incomparable binary sequences, define the type of the pair to be the answers to the following three questions: is u constantly 0? are u and v consecutive? is v constantly 1? It can be checked that two pairs u <_{lex} v and v′ <_{lex} v′ have the same type if and only if there is a f in F such that u.f = u′ and v.f = v′. Futhermore, all types can be represented by pairs of sequences of length at most 3. □

From these propositions it follows that every relation in (4) is conjugate via an element of F to a relation in (4) indexed by sequences of length at most 3. The relations in (5) are conjugate via elements of F to a relation y_{s} = x_{s}y_{s0}y_{s10}^{−1}y_{s11} where s ∈ {0, 10, 1}. The relations in (3) can be expressed as y_{s}g = gy_{s} where s ∈ {0, 10, 1} and g ∈ F such that s.g = s. These can be derived from relations y_{s}x_{t} = x_{t}y_{s} where s.x_{t} = s and s, t are binary sequences of length at most 3. In particular G and G_{0} are finitely presented. In the case of G_{0}, one can check that the following list of 9 relations actually suffice:

x_{1}x^{−2}x_{1}x = x^{−1}x_{1}xx_{1}x^{−1} x_{1}x^{−3}x_{1}x^{2} = x^{−2}x_{1}x^{2}x_{1}x^{−1}

                    y_{10}x_{0} = x_{0}y_{10}  y_{10}x_{01} = x_{01}y_{10}
                   y_{10}x_{11} = x_{11}y_{10}  y_{10}x_{111} = x_{111}y_{10}
                   y_{01}y_{10} = y_{10}y_{01}  y_{001}y_{10} = y_{10}y_{001}
                         y_{10} = x_{10}y_{100}y_{1010}^{−1}y_{1011}.

(Notice that all of the above relations except the last assert that a pair of elements of the group commute. In each case this is because they are supported on disjoint sets, where the support g is the set of x such that x.g ≠ x.) When expressed in terms of the original generators, these become:

ba^{−2}ba = a^{−1}baba^{−1} ba^{−1}a^{−2}ba^{2} = a^{−2}ba^{2}ba^{−1}
ca^{2}b^{−1}a^{−1} = a^{2}b^{−1}a^{−1}c cab^{2}a^{−1}b^{−1}ab^{−1}a^{−1} = ab^{2}a^{−1}b^{−1}ab^{−1}a^{−1}c
ca^{−1}ba = a^{−1}bac ca^{−2}ba^{2} = a^{−2}ba^{2}c
caca^{−1} = aca^{−1}c ca^{2}ca^{−2} = a^{2}ca^{−2}c
c = b^{2}a^{−1}b^{−1}aca^{−1}bc^{−1}a^{−1}cab^{−1}ab^{−1}.

4. Tree diagrams

Before proceeding further, we will pause to describe how the elements of ⟨a, b, c⟩ can be described in terms of tree diagrams, similar to those associated to Thompson’s group F. This section is not essential for understanding the proof of Theorem 1.1 in the subsequent section, although the reader may find the material here is useful in visualizing what is happening in the main proofs.

Let T̃ denote the collection of all finite sets S of reduced words in the alphabet {0, 1, y, y^{−1}} which satisfy the following properties:

• S is nonempty;

• the result of deleting all occurrences of y and y^{−1} in members of S defines a bijective map between S and an element of T ;

• if uy^{n} is a prefix of some element of S, then any element of S which has u

as a prefix, also has uy^{n} as a prefix; Elements of T̃ be be visualized as follows. Let S be in T̃ and T is the result of removing the occurrences of y and y^{−1} from elements of S. We can think of T as defining a rooted ordered binary tree, whose vertexes correspond to the prefixes of elements of T. The elements of S can be specified by an assignment of an integer to each vertex of T. For instance if S = {0, 1yy0y^{−1}, 1yy1}, then the associated labeled tree is:

[figure: 2; −1]

(here and below unspecified labels are 0).

A labeled tree diagram is a pair S → T of elements of T̃ such that S and T have the same number of vertexes. The key point is now to define the appropriate notion of equivalence of tree diagrams. First we define a notion of equivalence on T̃. Two (possibly infinite) words in the alphabet {0, 1, y, y^{−1}} are equivalent if one can be converted into the other by the following substitutions:

y00 ⇔ 0y  y01 ⇔ 10y^{−1}  y1 ⇔ 11y
y^{−1}0 ⇔ 00y^{−1}  y^{−1}10 ⇔ 01y  y^{−1}11 ⇔ 1y^{−1}.

Two elements of T̃ are equivalent if the sets of equivalence classes of their elements coincide. In terms of labeled tree diagrams, this means that S and T are equivalent if T can be obtained from S by a sequence of substitutions of the following form:

[figure: m; i; j; k]  ⇔  [figure: m − 1; i + 1; j − 1; k + 1]

In many simple computations, labels are either 0, 1 or −1. In this case it is convenient to use • and ∘ to indicate the labels 1 and −1 respectively. The substitution rule above then becomes a pair of substitutions: [figure: •] ⇔ [figure: •; ∘; •] and [figure: ∘] ⇔ [figure: ∘; •; ∘].

Notice that if S and T are equivalent elements of T̃, then S and T have the same number of leaves.

Equivalence of labeled tree diagrams is generated by the equivalence of trees, together with the following manipulations on tree diagrams:

• If S → T is a labeled tree diagram, then we can insert a caret below the i^{th} leaf of S and below the i^{th} leaf of T to produce an equivalent diagram S′ → T′. The labels of the top vertexes of the new carets are the same as the original vertexes; the leaves of the new carets are labeled 0.

• If S → T is a labeled tree diagram, then we may add 1 to the label of the i^{th} leaves of S and of T to produce an equivalent diagram S′ → T′.

If S → T is a labeled tree diagram and S has no labels, then it describes a continuous function g : 2^{ω} → 2^{ω} as follows. If ξ is an infinite sequence in the alphabet {0, 1, y, y^{−1}} with only finitely many occurrences of y or y^{−1}, then define lim ξ to be the unique infinite binary sequence η such that every prefix of η occurs as a prefix of a sequence equivalent to ξ. If s_{i} and t_{i} are the i^{th}-least elements of S and T respectively in the lexicographic order, then define g(s_{i}ξ) = lim t_{i}ξ. It is easy to check that the generators can be described as follows:

a = ( [figure]→ [figure])  b = ( [figure]→ [figure])  c = ( [figure]→ [figure: •])

In fact we can modify this definition slightly in order to associate a function to any labeled tree diagram: define g(lim s_{i}ξ) = lim t_{i}ξ. We leave it to the reader to verify that this is a well defined map. The equivalence of tree diagrams is set up so as to capture exactly when the corresponding functions coincide. We will eventually see that the collection of all functions arising in this way is a group which then coincides with the group G of the previous section. Notice that if S → T and T → U are labeled tree diagrams, then the composition of the two functions associated to these diagrams is the same as that described by S → U. In particular T → S is the inverse of S → T.

We will conclude this section with a illustrative computation. Notice that t ↦ 2t correspond to the diagram [figure] → [figure: ∘; •]. Conjugating t ↦ t + 1 by t ↦ 2t yields t ↦ t + 2, the square of the first map. In terms of labeled tree diagrams, this computation can be carried out as follows:

([figure]→ [figure: ∘; •])^{−1} · ([figure]→ [figure]) · ([figure]→ [figure: ∘; •]) =
([figure: ∘; •] → [figure]) · ([figure]→ [figure]) · ([figure]→ [figure: ∘; •]) =
[figure: ∘; •] → [figure: ∘; •] = [figure: ∘; •] → [figure: ∘; •] = [figure: ∘; •; ∘; •] → [figure: •; ∘; •; ∘]

[figure]→ [figure]= ([figure]→ [figure])^{2}

5. Sufficiency of the relations

In this section, we will prove that the relations in R and R_{0} are sufficient to give presentations for G and G_{0}. We will use without proof that the relations in R which only refer to the generators in X give a presentation for F (see [3] [5]). The strategy of the proof is as follows. First, we will argue that any S-word can be put into a standard form by applying the relations. Standard forms are not unique, but are organized in a way which better facilitates further symbolic manipulations. We will then define the notion of a sufficiently expanded standard form, argue that every standard form can be sufficiently expanded by applying the relations in R, and that any sufficiently expanded standard form which represents an element of F is an X-word.

We will begin by defining some terminology. In what follows, we will say that an S-word Ω_{1} is derived from an S-word Ω_{0} if it is the result of applying substitutions of the following forms:

y_{t}^{i}x_{s}^{±1} ⇒ x_{s}^{±1}y_{t.x_{s}^{±1}}^{i} y_{s} ⇒ x_{s}y_{s0}y_{s10}^{−1}y_{s11}
y_{u}y_{v} ⇔ y_{v}y_{u}  x^{i+j} ⇔ x^{i}x^{j}  y^{i+j} ⇔ y^{i}y^{j}
delete an occurrence of y^{i}y^{−i}

where s, t, u, v ∈ 2^{<ω} are such that t.x_{s} is defined and u and v are incompatible, and i, j are nonzero integers of the same sign. We will write this symbolically as Ω_{0} ⇒ Ω_{1}. Notice that each of these substitutions corresponds either to a relation in R or to a group-theoretic identity. Also observe that only S_{0}-words can be derived from S_{0}-words.

Definition 5.1. An S-word Ω is in standard form if it is the concatenation of a X-word followed by a Y -word and whenever Ω(i) = y_{s}^{m}, Ω(j) = y_{t}^{n}, and s ⊆ t, then j ≤ i. We will write standard form to mean an S-word in standard form. The depth of a standard form Ω is the least l such that there is binary sequence s of length l such that y_{s} occurs in Ω (if Ω is an X-word, then we say that Ω has infinite depth).

Notice in particular that a given y_{s} can occur at most once in a standard form (although possibly with an exponent other than ±1). Observe that any group element which is expressible by a word in standard form allows us to describe the group element via a labeled tree diagram in the sense of the previous section.

Lemma 5.2. For every s ∈ 2^{<ω} and every l ∈ ω, there is a standard form Ω which can be derived from y_{s}^{±1} such that:

(1) if x_{u} occurs in Ω, then u extends s;

(2) if y_{u} occurs in Ω, then u extends s, has length at least l, and the exponent of y_{u} is ±1;

(3) if y_{u} and y_{v} occur in Ω and u ≠ v, then u and v are incompatible.

Proof. The proof is by induction on l − |s|. If l − |s| = 0, there is nothing to do since y_{s} already satisfies the conclusion of the lemma. If l − |s| > 0, then y_{s} ⇒ x_{s}y_{s0}y_{s10}^{−1}y_{s11} and we can apply the induction hypothesis to obtain Ω_{s0}, Ω_{s10}, Ω_{s11} which satisfy the conclusion of the lemma for y_{s0}, y_{s10}^{−1}, and y_{s11} respectively for the same value of l. By conclusion 1 of the lemma, we can apply substitutions of the form y_{v}x_{u} ⇒ x_{u}y_{v} for incompatible u and v move the occurrence of x_{u} in

x_{s}Ω_{s0}Ω_{s10}Ω_{s11}

to the left, placing the word a standard form which satisfies the conclusions of the lemma. The case of y_{s}^{−1} is handled similarly using the substitution y_{s}^{−1} ⇒ x_{s}^{−1}y_{s00}^{−1}y_{s01}y_{s1}^{−1}. □

Lemma 5.3. If Ξ is an X-word, then there is an l_{0} such that if Ω is a standard form of depth l ≥ l_{0}, then ΩΞ ⇒ Ω′ for some standard form Ω′ of depth at least l − k where k is the word length of Ξ.

Proof. If Ξ = x_{s}^{±1}, then observe that if t is a finite binary sequence of length at least 2 greater than that of s, then t.x_{s}^{±1} is defined and its length differs from the length of Ω by at most 1. Thus by repeated applications of the substitution y_{t}^{i}x_{s}^{±1} ⇒ x_{s}^{±1}y_{t.x_{s}^{±1}}^{i}, the final occurrence of x_{s} in Ωx_{s}^{±1} can be moved to the left of all occurrences of a y_{t}. This results in a standard form in which the depth is changed by at most 1. The general case now follows by induction. □

Lemma 5.4. If Ω is any S-word and l ∈ ω, then Ω ⇒ Ω′ for some standard form Ω′ of depth at least l.

Proof. The proof by induction on the word length n of Ω. The case n = 1 is handled by Lemma 5.2. Assume n > 1 and let l be given. By making a substitution of the form a^{±(k+1)} ⇒ a^{±k}a^{±1} if necessary, we may assume that Ω = Ω_{0}Ω_{1} where Ω_{i} is an S-word of positive length. By our induction hypothesis Ω_{1} ⇒ ΞΥ, where Ξ and Υ are X- and Y -words respectively and Υ has depth l. Let k be the word length of Ξ and let m ≥ l be such that if y_{u} occurs in Υ, u has length less than m. By our induction hypothesis, there is a standard form Ω′_{0} of depth at least m + k such that Ω_{0} ⇒ Ω′_{0}. By Lemma 5.3 we have that Ω′_{0}Ξ ⇒ Ω′′_{0} for some standard form Ω′′_{0} of depth at least m, we have:

Ω ⇒ Ω_{0}Ω_{1} ⇒ Ω_{0}ΞΥ ⇒ Ω′_{0}ΞΥ ⇒ Ω′′_{0}Υ

Finally, notice that since the depth of Ω′′_{0} is at least m, Ω′ = Ω′′_{0}Υ is a standard form of depth at least l, as desired. □

If Ω is standard form and y_{s} occurs in Ω, we say that s is exposed in Ω if there is a finite binary sequence u extending s such that if t is a binary sequence compatible with u and y_{t} occurs in Ω, then t is an initial part of s.

Definition 5.5. A standard form Ω is sufficiently expanded if whenever y_{s} occurs in Ω and s is not exposed in Ω, then:

• y_{s0} occurs in Ω if y_{s} occurs positively in Ω;

• y_{s1} occurs in Ω if y_{s} occurs negatively in Ω.

The motivation for this definition is as follows. Suppose that Ω is a standard form which is not sufficiently expanded and that this is witnessed by Ω(i) = y_{s}^{n} for n > 0. If we substitute

x_{s}y_{s0}y_{s10}^{−1}y_{s11}y_{s}^{n−1}

for y_{s}^{n} in Ω, then whenever y_{t} occurs before y_{s} in Ω, t.x_{s} is defined. A similar conclusion holds — with x_{s}^{−1} replacing x_{s} — if n < 0 and the substitution

x_{s}^{−1}y_{s00}^{−1}y_{s01}y_{s1}^{−1}y_{s}^{n+1}

is applied. This plays an important role in the proof of the next lemma.

Lemma 5.6. If Ω is a standard form, then there is a sufficiently expanded standard form which can be derived from Ω.

Proof. We will prove the lemma by defining a well-founded partial ordering ◁ on the set of standard forms and a notion of expansion on standard forms which are not sufficiently expanded in such a way that produces a smaller standard form in this ordering. Here a partial order is well-founded if it has no infinite strictly decreasing sequences. We will define the ordering first.

If Ω is an S-word, let T (Ω) denote the minimal prefix set which has the property that if y_{t} occurs in Ω, then t has an extension in T. If Ω_{0} and Ω_{1} are standard forms, define Ω_{0} ◁ Ω_{1} if |T (Ω_{0})| < |T (Ω_{1})| or |T (Ω_{0})| = |T (Ω_{1})| and |k_{0}| < |k_{1}| where k_{i} is the exponent in Ω_{i} of the ≤_{lex}-maximal s such that y_{s} occurs in at least one of Ω_{0} or Ω_{1} and for which k_{0} ≠ k_{1} (if y_{s} occurs in only one of the Ω’s, then the other exponent is 0). Notice that for a fixed m there are only finitely many prefix sets of cardinality m. In particular the collection F of all finite binary sequences which have an extension in a prefix set of cardinality m is finite. Since the lexicographic ordering on ω^{F} is a well-order, ◁ is well-founded.

Now suppose that Ω is a standard form which is not sufficiently expanded as witnessed by Ω(i) = y_{s}^{n}. For simplicity, suppose that n > 0 and apply the substitution

y_{s}^{n} ⇒ x_{s}y_{s0}y_{s10}^{−1}y_{s11}y_{s}^{n−1}

(if n = 1, the y_{s}^{n−1} term is omitted) followed by substitutions of the form y_{t}^{m}x_{s} ⇒ x_{s}y_{t.x_{s}}^{m} to move x_{s} to the left, forming a new word Ω′ which is the concatenation of a X-word followed by a Y -word. At this point, the only thing preventing Ω′ from being a standard form is the newly introduced occurrences of y_{s0}, y_{s10}, and y_{s11}. Observe that y_{s1} can not occur in Ω′; for this to happen, s1 would have to equal t.x_{s} for some t such that t.x_{s} is defined, and such a t does not exist. Furthermore, if y_{t} occurs in Ω′ and t properly extends one of the sequences s0, s10, or s11, then y_{t} must occur before any occurrence of y_{s0}, y_{s10}, or y_{s11} in Ω′. Similarly, if t is a proper initial part of s0, s10, and s11 and y_{t} occurs in Ω′, then t is actually an initial part of s and thus the occurrence is after the point of the substitution. We may therefore apply substitution of the form y_{u}y_{v} ⇔ y_{v}y_{u} for incompatible u and v in order to move any two distinct occurrences of y_{s0}, y_{s10}, or y_{s11} to the same position in Ω′, resulting in a word Ω′′ which is now in standard form.

It now suffices to show that Ω′′ ◁ Ω. Since s was not exposed in Ω, each of s00, s01, and s1 has an extension in T (Ω); recall that, by assumption, y_{s0} does not occur in Ω. It follows that t.x_{s} is defined for every element t of T (Ω) and that T (Ω′) = {t.x_{s} : t ∈ T (Ω)}. Hence T (Ω) and T (Ω′) have the same cardinality. Notice that if y_{s} occurs in Ω′′, it occurs in Ω′ and hence T (Ω′) dominates T (Ω′′). It follows that T (Ω′′) has cardinality at most that of T (Ω). If T (Ω′′) has the same cardinality as T (Ω), then s is the ≤_{lex}-maximal sequence such that the exponent of y_{s} in Ω and Ω′′ differs and in this case, it decreases by one in absolute value. Thus we have shown Ω′′ ◁ Ω. □

Let B denote the set {0, 1, y, y^{−1}} and let B^{<ω} denote the collection of all finite strings of elements of B. If Λ is in B^{<ω} and Λ(i) is either y or y^{−1}, we will say that Λ(i) is an occurrence of y^{±}. We will use B-words to analyze the evaluation of standard forms at binary sequences. The following symbolic manipulations correspond to the recursive definition of the function y : 2^{ω} → 2^{ω}.

Definition 5.7. Suppose that Λ is in B^{<ω}. An application of one of the substitutions

y00 ⇒ 0y  y01 ⇒ 10y^{−1}  y1 ⇒ 11y
y^{−1}0 ⇒ 00y^{−1}  y^{−1}10 ⇒ 01y  y^{−1}11 ⇒ 1y^{−1}

at an occurrence of y^{±} is said to advance that symbol. If several advances of occurrences of y^{±} are applied to Λ, resulting in Λ′, then we say that Λ can be advanced to Λ′, denoted Λ ⇒ Λ′.

Definition 5.8. Suppose that Λ is in B^{<ω}. An occurrence of y^{±} is a potential cancellation in Λ if repeatedly advancing it results in an occurrence of the substring yy^{−1} or y^{−1}y in the modified word.

Lemma 5.9. Suppose that Λ is in B^{<ω} and contains no potential cancellations. Then advancing any occurrence of a y^{±} results in a word with no potential cancellations.

Proof. Suppose that Λ is given and that the ith occurrence of y^{±} is advanced to create Λ′. The only possibility for introducing a potential cancellation is if i > 1 and a potential cancellation occurs at the i − 1st occurrence of a y^{±} in Λ′. Return to Λ and advance the i − 1st occurrence of y^{±} as much as possible to produce Λ′′. Suppose for a moment that after advancing, this occurrence is a y; notice that the next symbol is either 0 or y. We now have the following cases:

yy00 ⇒ y0y
yy01 ⇒ y10y^{−1} ⇒ 11y0y^{−1}
yy1 ⇒ y11y ⇒ 1111yy
y0y00 ⇒ y00y ⇒ 0yy
y0y01 ⇒ y010y^{−1} ⇒ 10y^{−1}0y^{−1} ⇒ 1000y^{−1}y^{−1}
y0y1 ⇒ y011y ⇒ 10y^{−1}1y
y0y^{−1}0 ⇒ y000y^{−1} ⇒ 0y0y^{−1}
y0y^{−1}10 ⇒ y001y ⇒ 0y1y ⇒ 011yy
y0y^{−1}11 ⇒ y01y^{−1} ⇒ 10y^{−1}y^{−1}

The above lines list the possible contexts for two occurrences of y^{±} in the i − 1st and ith in Λ′′ where the first occurrence is positive. In the above cases, the ith occurrence of y^{±} is advanced in Λ′′ and then the i − 1st occurrence is advanced as much as possible, demonstrating that a cancellation does not occur. The case in which the i − 1st occurrence of y^{±} in Λ′′ is y^{−1} is handled by symmetry — the rules for advancement and potential cancellation are invariant under the following involution:

y ⇔ y^{−1} 0 ⇔ 1.
□

Lemma 5.10. Suppose that Λ is in B^{<ω} and contains no potential cancellations. There is a finite binary sequence u such that Λ^{⌢}u can be advanced to s^{⌢}y^{n} for some binary sequence s, where n is the number of occurrences of y^{±} in Λ.

Proof. The proof is by induction on the number of occurrences of y^{±} in Λ. If there is only one occurrence, advance the occurrence as many times as possible, resulting in s^{⌢}y, s^{⌢}y^{−1}, s^{⌢}y^{⌢}0, or s^{⌢}y^{−1}^{⌢}1 for some finite binary sequence s. In the first case we are finished; in the remaining cases, the choices u = 10, u = 0, and u = 0 work. Now suppose that Λ contains n+1 occurrences of y^{±}. Induction and Lemma 5.9 reduce the general case to the two special cases y0y^{n} and y^{−1}1y^{n}. In these cases, use u = 0^{2^{n}}, observing that y^{n}0^{2^{n}} can be advanced to 0y^{n}. □

Lemma 5.11. If Ω is a sufficiently expanded standard form then either Ω is an X-word or else Ω does not have the same evaluation as an X-word.

Proof. Notice that it is sufficient to prove the lemma when Ω is a sufficiently expanded standard form which is a Y -word of positive length. Suppose that such an Ω is given and let g : 2^{ω} → 2^{ω} be the evaluation of Ω in G. It will be sufficient to construct finite binary sequences u and v such that the value of g at u^{⌢}ξ is v^{⌢}y^{n}(ξ) for some n > 0. This is because if ξ = 0^{2^{n}}10^{2^{n}}1 …, then the value of g at u^{⌢}ξ is v^{⌢}01^{2^{n}}01^{2^{n}} …, which is not tail equivalent to u^{⌢}ξ.

The finite binary sequence u will be constructed by a recursive procedure. Let u ↾ i_{0} be the finite binary sequence such that the last entry of Ω is a power of y_{u↾i_{0}}. Suppose that u ↾ i has been defined and that y_{u↾i} occurs in Ω. If u ↾ i is exposed in Ω, then let u ↾ l be any finite binary sequence extending u ↾ i which witnesses this. Otherwise, define u(i) = 0 if y_{u↾i} occurs positively in Ω and u(i) = 1 if y_{u↾i} occurs negatively in Ω. Define Λ to be the result of simultaneously inserting y^{n} after s ↾ i whenever y_{s↾i}^{n} occurs in Ω. Notice that by the choice of our sequence u, Λ does not contain potential cancellations: any occurrence of y except for the final occurrence of y^{±}, is followed by 0y^{±} and any occurrence of y^{−1} except for the final occurrence of y^{±} is followed by 1y^{±}. It follows from Lemma 5.10 that there is a sequence s such that Λ^{⌢}s can be advanced to vy^{n} for some binary sequence v, where n is the number of occurrences of y^{±} in Λ (this number coincides with the number of steps of the recursive procedure above, which is at least 1). Set u to be the concatenation of u ↾ l followed by s.

Recall now that we have assumed that Ω is a Y -word; g = y_{t_{k}}^{n_{k}} … y_{t_{1}}^{n_{1}}.

ξ.g = ξ.(y_{t_{1}}^{n_{1}} ⋯ y_{t_{k}}^{n_{k}}) = (⋯ (ξ.y_{t_{1}}^{n_{1}}). · · ·).y_{t_{k}}^{n_{k}}

Let ξ_{i} be the result of applying the y_{t_{1}}^{n_{1}} ⋯ y_{t_{i−1}}^{n_{i−1}} to ξ. Observe that if t_{i+1} is an initial part of ξ, then it is still an initial part of ξ_{i}. This follows from the fact that if j ≤ i, then t_{j} either extends t_{i+1} or else is incompatible with t_{i+1}. In particular, if t_{i+1} is not an initial part of ξ, then ξ_{i+1} = ξ_{i}. If t_{i+1} is an initial part of ξ_{i}, then ξ_{i+1} = t_{i+1}^{⌢}y^{n_{i}}(η_{i}), where ξ_{i} = t_{i}^{⌢}η_{i}. It follows from Λ^{⌢}s ⇒ vy^{n} that ξ.g = v^{⌢}(η.y^{n}), where η is such that ξ = u^{⌢}η. □

To see that this finishes the proof of the main theorem, suppose that Ω is an S-word which evaluates to the identity function in G. By Lemma 5.4, Ω ⇒ Ω′ for some word Ω′ in standard form. By Lemma 5.6, Ω′ ⇒ Ω′′ for some word Ω′′ which is in standard form and which is sufficiently expanded. In particular, Ω′′ is equivalent to Ω by the relations in R; if Ω was an S_{0}-word, then Ω′′ is an S_{0} word and the derivation Ω ⇒ Ω′ ⇒ Ω′′ utilizes only relations in R_{0}. By Lemma 5.11, Ω′′ is an X-word. Since R includes a presentation for F, Ω′′ can be reduced to the identity using the relations in R_{0}.

References

[1] S.I. Adyan. The Burnside Problem and Identities in Groups. volume 95 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin, 1979.

[2] S.I. Adyan. Random walks on free periodic groups. Izv. Akad. Nauk SSSR Ser. Mat. 46(6):1139–1149, 1982.

[3] J. Belk. Thompson’s group F. Ph.D. Thesis, Cornell University, 2004. arXiv:0708.3609.

[4] M.G. Brin, C.C. Squier. Groups of piecewise linear homeomorphisms of the real line. Invent. Math., 79(3):485–498, 1985.

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

[6] A. Connes, J. Feldman, B. Weiss. An amenable equivalence relation is generated by a single transformation. Ergodic Theory Dynamical Systems, 1(4):431–450, 1982.

[7] M.M. Day. Means for the bounded functions and ergodicity of the bounded representations of semi-groups. Trans. Amer. Math. Soc., 69:276–291, 1950.

[8] P. Dehornoy. Geometric presentations for Thompson’s groups. J. Pure Appl. Algebra, 203(1– 3):1–44, 2005.

[9] É. Ghys, Y. Carriére. Relations d’équivalence moyennables sur les groupes de Lie. C. R. Acad. Sci. Paris Sér. I Math, 300(19):677–680, 1985.

[10] A. Hurwitz. Über die Kettenbruch-Entwicklung der Zahl e. Phys.-6kon. Ges., Königsberg, 1891. Mathematische Werke, 2:129—133, Basel: Birkhäuser, 1933.

[11] S.V. Ivanov. Embedding free Burnside groups in finitely presented groups. Geometriae dedicata, 111:87–105, 2005.

[12] A.S. Kechris, B.D. Miller, Topics in Orbit Equivalence. volume 1852 of Lecture Notes in Mathematics Springer, Berlin, 2004.

[13] R. McKenzie, R.J. Thompson, An elementary construction of unsolvable word problems in group theory. pp. 457–478 in Word Problems, Boone, Cannonito, Lyndon Eds., North Holland, 1973.

[14] N. Monod. Groups of piecewise projective homeomorphisms. Proc. Natl. Acad. Sci., 110(12):4524–4527, 2013

[15] J. Tatch Moore. A brief introduction to amenable equivalence relations. submitted

[16] A.Y. Ol’shanskii. On the question of the existence of an invariant mean on a group. Uspekhi Mat. Nauk, 35(4):199–200, 1980.

[17] A.Y. Ol’shanskii, M.V. Sapir. Non-amenable finitely presented torsion-by-cyclic groups. Publ. Math. Inst. Hautes Études Sci., 96:43–169, 2003.

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

[19] G.N. Raney. On continued fractions and finite automata. Math. Ann., 206:265–283, 1973.

[20] J. von Neumann. Zur allgemeinen Theorie des Maßes. Fund. Math., 13:73–116, 1929.

[21] J. Zimmer. Amenable ergodic group actions and an Application to Poisson boundaries of random walks. Journal of Functional Analysis, 27:350–372, 1978.

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

E-mail address: yl763@cornell.edu