Jérôme Los

Natalia Viana Bedoya

Natalia A Viana Bedoya

A group from a map and orbit equivalence

come   L'archive ouverte pluridisciplinaire

Introduction

In this paper a central question is:

How to construct a group from a dynamical system? More specifically we want to find conditions for constructing a discrete subgroup of Homeo(S 1 ) from a single map Φ : S 1 → S 1 that is an expanding piecewise homeomorphism. We also want to understand which groups could appear.

The question is in fact a reverse problem for what is known as the Bowen-Series-like maps. In the late 70's R. Bowen and R. Bowen-C. Series discovered a new relationship between groups and dynamics in [B] and [BS], in the special class of Fuchsian groups. If G is a discrete subgroup of PSL(2, R), acting on H 2 by isometries, they constructed a map Φ G : S 1 → S 1 , under some geometric conditions on the action, and S 1 is the boundary ∂H 2 . The map Φ G is special: It is a piecewise Möbius diffeomorphism of S 1 , in particular it is piecewise analytic, and satisfies two strong properties: -Φ G is orbit equivalent to the G-action on S 1 . -Φ G is an expanding Markov map.

The idea of that construction has been revisited in [L] for hyperbolic surface groups, given combinatorially by a presentation P = X; R , in a particular class called "geometric", meaning that the associated Cayley 2-complex is planar. The classical presentations of surface groups are geometric in this sense.

AMS Subject Classification (2020): 20F65, 20F67, 37E10.

1

For a geometric presentation P of a hyperbolic surface group G, the map obtained: Φ P : S 1 → S 1 is a piecewise homeomorphism and S 1 is the Gromov boundary of G. The maps Φ P are different from the maps Φ G of [BS], even in the cases where they could be compared, i.e. for the classical presentations. Yet they satisfy the same main features: the Markov and the orbit equivalence properties. They verify a new relationship between the group and the dynamics: the topological entropy of the map equals the volume entropy of the group presentation.

The Markov property is useful to study the dynamics, in particular via the techniques in symbolic and ergodic dynamics (see [B] and more recently [BuS], [AJLM]). But this property is not central for the relationship between the group and the map. The orbit equivalence is the important relation between the group and the dynamics.

The constructions in [B], [BS] and [L] use the fact that Fuchsian groups are particular discrete subgroups of Homeo(S 1 ).

How particular are the Fuchsian groups, among the subgroups of Homeo(S 1 )? This is a famous geometrisation question, whose final answer has been obtained by Tukia [T], Gabai [G] and Casson-Jungreis [CJ] after a long serie of works starting with Nielsen in the 40's [N]. This geometrisation result will come back later.

The problem we consider here is new and similar to a geometrisation question: How particular are the class of maps obtained in [L] from surface group presentations, among piecewise homeomorphisms of S 1 ?

This paper gives a partial answer. The problem goes from the dynamics to the group: A map is given, as an expanding piecewise homeomorphism: Φ : S 1 → S 1 , the first goal is to construct a group from the map. We want to find dynamical conditions on Φ allowing to construct a group G Φ , so that G Φ and Φ satisfy some of the properties of the maps in [L] and in [BS]. The possible groups are naturally subgroups of Homeo(S 1 ) thus they act on S 1 . Therefore the notion of orbit equivalence between the group and the map makes sense. We say that Φ is a Bowen-Series-type map for a group G, acting on S 1 , if the two actions are orbit equivalent (see §6). There are in fact two questions:

• Can we construct a group G Φ , from Φ, which is orbit equivalent to Φ? • Can we recognize the group G Φ , in particular is it a surface group?

The map is a piecewise homeomorphism of the circle, this means it is given by a finite partition of S 1 and the restriction to each partition interval is a homeomorphism onto it's image. For reasons that will soon become clear, the number of partition intervals is even. A point at the boundary of two partition intervals is called a cutting point, at such points the map is not continuous. The map is expanding means that each partition interval is mapped onto an interval that contains it compactly thus the map is surjective and not globally injective.

This class of maps is thus very different from another class of piecewise homeomorphisms, the classical "interval exchange transformations" (see W. Veech [V] and H. Masur [M] for instance) that are piecewise isometries.

The conditions we found on the map Φ (see §2 for details) are:

• A Strong Expansivity condition (SE): each partition interval is mapped to an interval that contains it and intersects all but one partition interval.

• An Eventual Coincidence condition (EC): the left and right orbits of each cutting point coincide after some iterates.

• The conditions (E+) and (E-) that control the left and right orbits of the cutting points before the coincidence. Finally we do not restrict to maps Φ satisfying a Markov property, we replace it by a weaker condition which quantifies the expansivity:

• The constant slope conditions (CS): the map is conjugate to a piecewise affine map with constant slope (λ > 1). Under this set of conditions our main result is:

Proving that the group G Φ and the map Φ are orbit equivalent follows a similar strategy as in [BS] (see §6).

In the appendix (see §7), we give a direct proof that G Φ is a surface group, without using the geometrisation theorems of Tukia, Gabai and Casson-Jungreis. All the work has, in fact, been done before, the geometric action constructed in §5 is extended to a free, co-compact action on a 2-disc.

This paper gives only a partial answer to our question. In particular conditions (E+) and (E-) are not optimal (see Remark 2) and finding better conditions is a challenge. The construction of the group from the map has revealed some surprises. For instance the group relations obtained in ( §3) show how delicate it is for a set of generators to verify some relations. It also shows that groups that are not surface groups could appear with different choices in the constructions, which groups could appear is an intersting question. Another surprise is the relationship between the length of an element, for the specific generators constructed in ( §3), with the growth property of that element (see Proposition 11).

The condition (EC) is central in our approach, it seems to be a new dynamical condition and is interesting in its own right. The class of discontinuous maps satisfying condition (EC) is much larger than the one studied here.

The relationship between the growth properties of the map and of the group has not been considered in this paper. Some works are in progress in that direction. It turns out that the numbers λ > 1 appearing in condition (CS) are limited, for maps satisfying (EC) and (E ± ), they are algebraic integers.

Aknowledgements: This work was partially supported by FAPESP (2016/24707-4). We thanks the hospitality of our research institutes: I2M in Marseille and DM-UFSCar in São Carlos, Brazil. We thanks the French-Uruguayan laboratory (IFUMI) in Montevideo where this work has been completed. The authors would like to thank P. Haissinsky and M. Boileau for their interest in this work and some comments on an earlier versions of the paper. We would like to thank the anonymous referee of a previous version who pointed out a gap in one argument. Closing this gap has proved to be very interesting, for this work and possibly others.

A class of piecewise homeomorphisms on S 1

In this section we define the class of maps that will be considered throughout the paper. The map Φ : S 1 → S 1 is a piecewise orientation preserving homeomorphism of the circle. More precisely, there is a partition of S 1 with an even number of intervals such that:

S 1 = 2N j=1 I j , where each I j is half open, ( 1
)
and Φ j := Φ | I j is an orientation preserving homeomorphism, onto its image. In order to state the next properties of the map we introduce some notations.

Permutations and combinatorics

Let ζ, ι, δ, γ be permutations of {1, . . . , 2N }, such that:

• ζ is a cyclic permutation of order 2N , • ι is a fixed point free involution, i.e. for all j ∈ {1, . . . , 2N }, ι(j) = j and ι 2 = id, such that: ι(j) = ζ ±1 (j), ∀j ∈ {1, . . . , 2N }. This property implies that N > 1 and to avoid special cases we assume, for the rest of the paper, that N ≥ 4.

• γ := ζ -1 ι and δ := ζ ι.
Geometrically ζ is the permutation that realizes the adjacency permutation of the intervals {I 1 , . . . , I 2N } along a given positive orientation of S 1 . By convention I ζ(j) is the interval that is adjacent to I j in the positive direction. The interval I ι(j) is an interval that is not I j and is not adjacent to I j . The two intervals I γ(j) and I δ(j) are the adjacent intervals to I ι(j) (see Figure 1). In this paragraph we point out some elementary properties of these permutations that are important for the rest of the work.

Lemma 1. The permutations γ and δ are conjugated, more precisely γ = ι -1 δ -1 ι.

Proof. Since δ and δ -1 are conjugated and ι -1 δ -1 ι = ι(ιζ -1 )ι = ζ -1 ι = γ, then δ and γ are conjugated.

To simplify the notations we will sometimes use: j := ι(j).

Remark 1. The two permutations γ and δ have the same cycle structure. We obtain γ from δ -1 by changing j to j on its cycles. The cycle of γ that contains j and the cycle of δ that contains j have the same length. We denote this number by [j].

Lemma 2. The integers ζ -1 (j), j and δ m-1 (j) are in the same cycle of γ of length [j], for all j ∈ {1, . . . , 2N } and 0 < m ≤ [j].

Proof. From the definitions of ι, γ, δ and Lemma 1, we have:

γ(j) = ζ -1 ι(ι(j)) = ζ -1 (j) and δ m-1 (j) = ι(δ m δ -1 (j)) = (ιδ m ι -1 )ζ -1 (j) = γ -m (ζ -1 (j)). Lemma 3. If 1 ≤ m ≤ [j], then ζ(γ m (j)) = γ m-1 (j). In particular if [j] is even and k(j) = [j]/2 then ζ(δ k(j)-1 ζ(j)) = γ k(j)-1 (j). Proof. Notice that ζ(γ m (j)) = ζγ(γ m-1 (j)) = ζ(ζ -1 ι)(γ m-1 (j)) = γ m-1 (j), and sup- pose that [j] is even and let k(j) = [j]/2. From the first part of this Lemma, to obtain ζ(δ k(j)-1 ζ(j)) = γ k(j)-1 (j), it is enough to show that δ k(j)-1 ζ(j) = γ k(j) (j).
In fact, by Lemma 1 and the definition of δ we have:

γ k(j) (j) = ι -1 δ -k(j) ι(j) = δ k(j) ι(j) = δ k(j)-1 δι(j) = δ k(j)-1 ζ(j). Lemma 4. γ(δ m (j)) = δ m-1 (j) and δ(γ m (ζ -1 (j))) = γ m-1 (ζ -1 (j)), for m = 1, . . . , [j].
Proof. In fact, by Lemma 3 and ι, γ, δ, we have:

γ(δ m (j)) = ζ -1 ι(ιδ m (j)) = ζ -1 δ(δ m-1 (j)) = ζ -1 ζ(δ m-1 (j)) = δ m-1 (j), and δ(γ m (ζ -1 (j))) = ζι(ιγ m (ζ -1 (j))) = ζγ(γ m-1 (ζ -1 (j))) = γ m-1 (ζ -1 (j))).

The class of maps

From now on we assume that all the cycles of γ (and δ by Lemma 1), in its cycle decomposition, have even length larger than 4, i.e:

[j] is even and k(j) = [j]/2 ≥ 2, for all j ∈ {1, . . . , 2N }.

(2)

Let us define the properties of the map: Φ : S 1 → S 1 . Using the permutations above we consider the Strong Expansivity condition: (SE) ∀j ∈ {1, . . . , 2N }, the map Φ satisfies: Φ(I j ) I k = ∅ ⇔ k = ι(j), (see Figure 1). This condition has some immediate consequences: (I) Φ(I j ) I k = I k , ∀k = ι(j), γ(j), δ(j), (II) The map Φ has an expanding fixed point in the interior of each I j . This is immediate from the definition of ι and (I), since I j ⊂ Φ(I j ). (III) The map is surjective, non injective and each point z ∈ S 1 has 2N -1 or 2N -2 pre-images.

In order to fix the notations we write each interval

I j := [z j , z ζ(j)
). The points z j ∈ S 1 are called the cutting points of Φ.

Φj(z j ) Φj(z ζ(j) ) • z j I j • z ζ(j) • I δ(j) • I ι(j) • I γ(j) • Φj(I j ) Figure 1: Condition (SE)
The next condition makes the map Φ really particular, it is called the Eventual Coincidence condition: (EC) ∀j ∈ {1, . . . , 2N } and ∀n ≥ k(j) -1, where k(j) ≥ 2 is given by (2):

Φ n (Φ ζ -1 (j) (z j )) = Φ n (Φ j (z j )).
In other words, each cutting point has a priori two different orbits, one from the positive side and one from the negative side of the point. The condition (EC) says that after k(j) iterates these two orbits coincide. By (1) each

I j := [z j , z ζ(j) ) is half open, the notation Φ ζ -1 (j) (z j ) is well defined by continuity on the left of z j of Φ ζ -1 (j) .
The next set of conditions on the map gives some control on the first k(j) -1 iterates of the cutting points z j , namely: For all j ∈ {1, . . . , 2N } and all 0 ≤ m ≤ k(j) -2:

(E+) Φ m (Φ j (z j )) ∈ I δ m+1 (j) , (E-) Φ m (Φ ζ -1 (j) (z j )) ∈ I γ m+1 (ζ -1 (j)) .
These two conditions are interpreted as follows: Consider (E+), for m = 0 this is condition (SE) since Φ j (z j ) ∈ I δ(j) , (see Figure 1).

Then Φ j (z j ) is near the cutting point z δ(j) in I δ(j) , since Φ(Φ j (z j )) ∈ I δ 2 (j) (by m = 1) and I δ 2 (j) is the interval containing Φ δ(j) (z δ(j) ) (by m = 0 for z δ(j) ) and so on up to m = k(j) -2. The last condition quantifies the expansivity property of the map. It is not absolutely necessary but simplifies many arguments, it is called the Constant Slope condition: (CS) Φ is topologically conjugate to a piecewise affine map Φ with constant slope λ > 1.

Remark 2. In [L], if all relations have even length, the resulting maps satisfy condition (SE) (see Lemma 5.1 in [L]). In these cases the conditions (EC), (E+), (E-) are satisfied by a direct check. The condition (CS) is a consequence of the Markov property, by a Perron-Frobenius argument. The Markov property is not required here. The set of piecewise homeomorphisms of the circle satisfying conditions (SE), (EC), (E+), (E-), (CS) is thus non empty.

If the presentation P of the surface group G is geometric and has some relations with odd length then the constructions in [L] apply but not those in [B] and [BS]. For these presentations, some conditions similar but different to (E+) and (E-) are satisfied. When the presentation P has some relations of length 3, the condition (SE) is not satisfied (see Lemma 5.2 in [L]). In all these cases condition (CS) is satisfied and a condition similar to (EC) is satisfied fo some intergers k. The condition (EC) is crutial in this paper and is not satisfied by all possible maps constructed via the general Bowen-Series-like strategy. In particular it is not satisfied by the original map in [BS].

3 Construction of a group from the map Φ In this section we construct a familly of subgroups of Diffeo + (S 1 ), from any map Φ satisfying the properties of §2.2. The goal is to define some specific generators in Diffeo + (S 1 ) using the particular properties of the map. The first step is a simple construction of a finite collection of diffeomorphisms from Φ. In the next step we use the condition (EC) in a crucial way. We replace each diffeomorphism obtained in the first step by a parametrized familly satisfying "partial" equalities, among some compositions of the various diffeomorphisms. These particular compositions are given by the map Φ via the conditions (EC) and (E+), (E-). They are candidates to become some relations in Diffeo + (S 1 ). The next step is a delicate "tuning" of the diffeomorphims in the families above by adjusting some explicit parameters for the partial equalities to become global, defining the expected relations in Diffeo + (S 1 ). The collection of elements in Diffeo + (S 1 ) obtained in this section is used as a set of generators for an, a priori, familly of groups. This family of groups is the main object studied in the remaining parts of the paper. The families above are rather explicit and shows that the various constructions depend on many choices. One of the goal in the remaining parts of the paper will be to check that the groups obtained do not really depend on these choices.

A simple classe of diffeomorphisms from Φ

By condition (CS) we replace our initial piecewise homeomorphism Φ by the piecewise affine map Φ with constant slope λ > 1, where Φ = g -1 • Φ • g, for g ∈ Homeo + (S 1 ). The piecewise affine map Φ is defined by a partition: S 1 = 2N j=1 I j , where:

I j = [z j , zζ(j) ) := g -1 (I j ) and Φ j := Φ | I j
, for j ∈ {1, . . . , 2N }.

Lemma 5. Assume Φ : S 1 → S 1 is a piecewise homeomorphism of S 1 satisfying the conditions (SE) and (CS) with slope λ > 1. For each j ∈ {1, . . . , 2N }, using the notations above, there is a class of diffeomorphisms [f j ] ⊂ Diff + (S 1 ) such that:

(1) For each

f j ∈ [f j ], (f j ) | I j = Φ j and (f j ) | Φ ι(j) ( I ι(j) ) = ( Φ ι(j) ) -1 | Φ ι(j) ( I ι(j) )
,

(2) f j is a hyperbolic Möbius like diffeomorphism, i.e. with one attractive and one repelling fixed point and one pair of neutral points, i.e. with derivative one.

(3) (f j ) -1 = f ι(j) .
Proof. Since the intervals I j and Φ(I ι(j) ) are disjoint by condition (SE), then I j and Φ ι(j) ( I ι(j) ) are disjoint and the condition (1) has no constraints. By condition (CS) the slope of Φ in I j and I ι(j) is λ, then (f j ) | I j is affine of slope λ and

(f j ) | Φ( I ι(j)
) is affine of slope λ -1 . The map f j is defined on I j Φ ι(j) ( I ι(j) ), it remains to define it on the complementary intervals:

S 1 -( I j Φ ι(j) ( I ι(j) )) = L j R j , (3)
where L j := [ Φ ι(j) (z δ(j) ), zj ] and R j := [z ζ(j) , Φ ι(j) (z ι(j) )] (see Figure 2). The existence of the diffeomorphism f j is a "differentiable connect-the-dots" construction. The constraints are the images of the extreme points: f j (∂ I j ) = ∂ Φ j ( I j ) and f j (∂ Φ ι(j) ( I ι(j) )) = ∂ I ι(j) , together with the derivatives at these points which are, respectively λ and λ -1 . The

• zδ(j) • zι(j) zj Lj Rj zζ(j) Φ ι(j) (z δ(j) ) Φ ι(j) (z ι(j) ) • zj • zζ(j) Φ j (z j ) Φ j (z ζ(j) ) zδ(j) R ι(j) zι(j) L ι(j) Φj Φ ι(j)
Figure 2: The connect-the-dot construction of f j ∈ Diff + (S 1 ) connect the dot construction is simple, we give some precisions since more details are required latter. Let X and Y be two disjoint intervals of S 1 , we denote ∂ ± X the two boundary points of X, where the indices ± refer to the orientation of the interval. Let Diff + (X, Y ) be the space of orientation preserving diffeomorphisms from X to Y . Let α, β ∈ R and dg be the derivative of g, we define:

Diff + α,β (X, Y ) = {g ∈ Diff + (X, Y ); dg(∂ -X) = α > 0, dg(∂ + X) = β > 0}, if α = β : Diff (mon) α,β (X, Y ) := {g ∈ Diff + α,β (X, Y ); dg is monotone}. (4)
We define f j on the two intervals L j and R j . The image of these intervals are, by condition (1), respectively: R ι(j) and L ι(j) . Since f j is required to be a diffeomorphism, the derivative df j varies continuously from λ > 1 to λ -1 < 1 along R j and from λ -1 < 1 to λ > 1 on L j . In other words:

f j |R j ∈ Diff + λ,λ -1 (R j , L ι(j) ) and f j |L j ∈ Diff + λ -1 ,λ, (L j ; R ι(j)
). Thus f j is highly non unique. By the intermediate values theorem and λ > 1 there is at least one point with derivative one, i.e. a neutral point, in each interval L j and R j .

Condition (2) requires the existence of exactly one neutral point N + j in R j and one neutral point N - j in L j . This is the simplest situation, it is realized if the derivative varies monotonically in R j and L j , in other words:

f j |R j ∈ Diff (mon) λ,λ -1 (R j , L ι(j) ) and f j |L j ∈ Diff (mon)
λ -1 ,λ, (L j ; R ι(j) ). By condition (SE), see (II), the map f j has exactly two fixed points, one expanding in I j and one contracting in I ι(j) . Therefore, with the above choices, condition (2) of the Lemma is satisfied for f j and f ι(j) . Let us denote by {f j } the subset of Diff + (S 1 ) satisfying conditions (1) and (2). Fixing f j ∈ {f j }, by construction we have f -1 j ∈ {f ι(j) }. Therefore the pair f j , f -1 j satisfies the condition (3) of Lemma 5.

We denote [f j ] the subset of Diff + (S 1 ) satisfying (1), (2), (3) of Lemma 5.

Dynamical properties of Φ

From now on the map Φ satisfies all the ruling conditions of §2.2, i.e. the conditions (SE), (EC), (E+), (E-), (CS). Lemma 6. Let Φ : S 1 → S 1 be a piecewise homeomorphism satisfying conditions (SE), (EC), (E+), (E-), (CS). Then there exists a maximal neigborhood V j of the cutting point z j , for all j ∈ {1, . . . , 2N }, such that Φ k(j) | V j is continuous and conjugate to an affine diffeomorphism Φ k(j) | V j with slope λ k(j) . The number λ > 1 is given by condition (CS) and k(j) is the integer of condition (EC) for the cutting point z j . The neighborhood V j of z j is the image of V j under g -1 ∈ Homeo + (S 1 ) that conjugates Φ to Φ.

Proof. As in the previous proof, we replace the piecewise homeomorphism Φ by the piecewise affine map Φ with constant slope λ > 1, using condition (CS) and the conjugacy given by g ∈ Homeo + (S 1 ). Let Z k(j) j ∈ S 1 be the point defined by condition (EC) for the cutting point z j , i.e.:

Z k(j) j = Φ k(j)-1 ( Φ ζ -1 (j) ( z j )) = Φ k(j)-1 ( Φ j ( z j )).
Suppose that Z k(j) j ∈ I a j , for some a j ∈ {1, . . . , 2N }.

Consider the pre-image of the point Z k(j) j from the left and the right, along the orbits of the cutting point z j . Namely we consider the points:

Z δ k(j)-1 (j) = Φ k(j)-2 ( Φ j ( z j )) ∈ I δ k(j)-1 (j) by (E+) , Z γ k(j)-1 (ζ -1 (j)) = Φ k(j)-2 ( Φ ζ -1 (j) ( z j )) ∈ I γ k(j)-1 (ζ -1 (j)) by (E-) .
In order to simplify the notations let us define (see Figure 3):

c j := γ k(j)-1 (ζ -1 (j)), d j := δ k(j)-1 (j), J c j := [z c j , Z c j ] ⊂ I c j , J d j := [Z d j , zζ(d j ) ] ⊂ I d j , (5)
From condition (EC) and the definitions above we obtain:

Φ c j (J c j ) ∩ Φ d j (J d j ) = Z k(j) j and Φ c j (J c j ) ∪ Φ d j (J d j ) is connected.
Define the ( Φ k(j)-1 )-preimages of J c j and J d j along the two orbits of z j , i.e. the left and the right orbits. These preimages belong respectively to the intervals I j and I ζ -1 (j) and we obtain:

V c j j = [ Φ -k(j)+1 ( z c j ), z j ] ⊂ I ζ -1 (j) and V d j j = [ z j , Φ -k(j)+1 ( z ζ(d j ) )] ⊂ I j . (6)
We define a neighborhood of the cutting point z j by

V j := V c j j ∪ V d j j . z c j • • z ζ(c j ) • z j Vj z ζ-1(j) • z ζ(j) • • • • I c j J c j • • I d j J d j • z d j • z ζ(d j ) • Φ k(j)-1 |V j Φ • • Z k(j) j • z ζ(a j )
• z a j I c j Φc j (zc j )

zc j • Φd j (z ζ(d j ) ) I d j
Figure 3: The neighborhood V j and its image by Φ k(j)

By condition (EC), Φ k(j) is continuous on V j and:

Φ k(j) ( V j ) = Φ c j (J c j ) ∪ Φ d j (J d j ) = [ Φ c j ( z c j ), Φ d j ( z ζ(d j ) )].
It satisfies, by condition (SE), the following property (see Figure 3):

Φ k(j) ( V j ) ∩ I k = ∅, ∀k = c j , d j . ( 7
)
By Lemma 3, the indices c j and d j in condition (7) are adjacent with: ζ(d j ) = c j . From Remark (1), the cycles containing j and c j are the same and thus k(c j ) = k(j). The map j) . Indeed, by definition of V c j j , V d j j and conditions (E±), the following properties are satisfied:

Φ k(j) | V j is affine of slope λ k(
∀z ∈ V d j j : Φ m (z) ∈ Ĩδ m (j) and ∀z ∈ V c j j : Φ m (z) ∈ Ĩγ m (ζ -1 (j)) , for m = 1, . . . , k(j) -1.
Then we obtain:

Φ k(j) (z) = Φ δ k(j)-1 (j) • • • • • Φ δ(j) • Φ j (z), ∀z ∈ V d j j and Φ k(j) (z) = Φ γ k(j)-1 (ζ -1 (j)) • • • • • Φ γ(ζ -1 (j)) • Φ ζ -1 (j) (z), ∀z ∈ V c j j . (8) Thus, Φ k(j) (z) is affine of slope λ k(j) for z ∈ V c j j ∪ V d j j = V j ,
as a composition of k(j) affine maps, each of slope λ, on each side. The definition of the intervals J d j and J c j in (5) implies that in the above composition, Φ δ k(j)-1 (j) and Φ γ k(j)-1 (ζ -1 (j)) are affine of slope λ and these intervals are the maximal with that property for the composition (8). This completes the proof of the maximality property. The neighborhood V j of the Lemma is then simply: V j = g( V j ), where g conjugates Φ with Φ.

Extensions

In this subsection we extend the construction of the diffeomorphisms in the classe [f j ] given by Lemma 5. The idea for these extensions comes from the properties (EC), (E±) and the expressions in (8) that are expected to become some partial equalities. The first step is to enlarge the intervals on which the diffeomorphisms constructed in Lemma 5 are affine. To that end we consider a collection of neighborhoods: ν j = ν j ( z j ) of the cutting points z j for all j ∈ {1, . . . , 2N }. These neighborhoods are choosen small enough to satisfy:

ν j ⊂ I j ∪ I ζ -1 (j) with ν j ∩ ν ζ(j) = ∅ and ν j ∩ ν ζ -1 (j) = ∅.
We define the λ-affine extension Φ ν j of Φ j which is a λ-affine map on the interval:

I ν j := I j ∪ ν j ∪ ν ζ(j) , satisfying: ( Φ ν j ) |I ν j is λ-affine and ( Φ ν j ) | I j = ( Φ j ) | I j . (9)
Proposition 1. If Φ satisfies the ruling conditions then there are small enough neighborhoods ν j for all j ∈ {1, . . . , 2N } so that the λ-affine extensions Φ ν j satisfy: Φ ν j (ν j ) ⊂ I δ(j) \ ν δ(j) and Φ ν j (ν ζ(j) ) ⊂ I γ(j) \ ν ι(j) for all j ∈ {1, . . . , 2N }.

Proof. From condition (SE): Φ j ( z j ) ∈ I δ(j) and Φ j ( z ζ(j) ) ∈ I γ(j) . The λ-affine extension Φ ν j is continuous at z j and z ζ(j) . Thus if the neighborhoods ν j , ν ζ(j) , ν δ(j) , ν ι(j) are sufficiently small then the conditions of the Proposition are satisfied by continuity.

If all the neighborhoods ν j are small enougth for Proposition 1 to apply then the sets

S 1 \ (I ν j ∪ Φ ν ι(j) (I ν ι(j) )) and S 1 \ (I ν ι(j) ∪ Φ ν j (I ν j )
) are non empty and each one has two connected components:

S 1 \ (I ν j ∪ Φ ν ι(j) (I ν ι(j) )) = L ν j ∪ R ν j and S 1 \ (I ν ι(j) ∪ Φ ν j (I ν j )) = L ν ι(j) ∪ R ν ι(j) . (10)
If all the neighborhoods ν j are small enough for the intervals in (10) to be non empty, then we define the following family of diffeomorphisms for j ∈ {1, . . . , 2N }:

[f ν j ] ⊂ Diff + (S 1
), "parametrised" by ν := {ν j : j ∈ {1, . . . , 2N }} such that:

[i] (f ν j ) |I ν j := ( Φ ν j ) |I ν j and (f ν j ) | Φ ν ι(j) (I ν ι(j) ) := ( Φ ν ι(j) ) -1 | Φ ν ι(j) (I ν ι(j) ) , [ii] (f ν j ) |L ν j ∈ Diff (mon) λ -1 ,λ (L ν j ; R ν ι(j) ) and (f ν j ) |R ν j ∈ Diff (mon) λ,λ -1 (R ν j ; L ν ι(j) ), [iii] (f ν j ) -1 := f ν ι(j) . (11)
The diffeomorphisms in the class [f ν j ] are similar but different to the class [f j ] of Lemma 5. They are affine on larger intervals and the diffeomorphisms f ν j and f ν ζ ±1 (j) are affine on a common interval: ν ζ(j) or ν j respectively.

Lemma 7. Let Φ satisfies the ruling assumptions: (SE), (EC), (E+), (E-), (CS), and Ṽ = { V j : j ∈ {1, . . . , 2N }} be the set of neighborhoods of Lemma 6. Then, for all j:

(a) V j satisfies Proposition 1: Φ Ṽ j ( V j ) ⊂ I δ(j) \ V δ(j) and Φ Ṽ j ( V ζ(j) ) ⊂ I γ(j) \ V ι(j) , and (b) Φ Ṽ δ k(j)-1 (j) • • • • • Φ Ṽ δ(j) • Φ Ṽ j | V j = Φ Ṽ γ k(j)-1 (ζ -1 (j)) • • • • • Φ Ṽ γ(ζ -1 (j)) • Φ Ṽ ζ -1 (j) | V j ,
where k(j) is the integer of condition (EC) at the cutting point z j .

Proof. From the proof of Lemma 6, the conditions ( 7) are satisfied for the neighborhoods V j . To simplify the formulation we consider the situation where k(j) = 3. Conditions ( 7) and (SE) implies, in particular that:

Φ 3 ( V j ) ⊂ Φ δ 2 (j) ( I δ 2 (j) ) and symmetrically Φ 3 ( V j ) ⊂ Φ γ 2 (ζ -1 (j)) ( I γ 2 (ζ -1 (j))
). Thus:

Φ -1 δ 2 (j) Φ 3 ( V j ) ⊂ I δ 2 (j) and Φ -1 γ 2 (ζ -1 (j)) Φ 3 ( V j ) ⊂ I γ 2 (ζ -1 (j))
. We focus on one side, for instance the δ(j)-side. The inclusion is in fact more restrictive:

Φ -1 δ 2 (j) Φ 3 ( V j ) = α; z ζ(δ 2 (j)) ⊂ I δ 2 (j) and α satisfies: α > Φ δ(j) ( z δ(j) ) ⊂ I δ 2 (j)
. Indeed, by condition (E+) for the cutting point z δ(j) , we have:

Φ δ 2 (j) ( Φ δ(j) ( z δ(j) )) ∈ I γ 2 (ζ -1 (j)) and Φ δ 2 (j) (α) / ∈ I γ 2 (ζ -1 (j))
, by ( 7). This implies:

Φ -1 δ 2 (j) Φ 3 ( V j ) ⊂ Φ δ(j) ( I δ(j) ) ∩ I δ 2 (j) and thus we obtain Φ -1 δ(j) • Φ -1 δ 2 (j) Φ 3 ( V j ) ⊂ I δ(j) . The map Φ -1 δ(j) • Φ -1 δ 2 (j) • Φ 3 | V j
is defined from V j to I δ(j) . It is an affine map of slope λ since Φ -1 δ(j) and Φ -1 δ 2 (j) are affine of slope λ -1 and Φ 3

| V j
is affine of slope λ 3 by Lemma 6.

By definition of the λ-affine extension Φ ν j with ν = Ṽ in (9) and, since:

Φ -1 δ(j) • Φ -1 δ 2 (j) • Φ 3 | V j ∩ Ĩj = Φ j | V j ∩ Ĩj , we obtain Φ Ṽ j ( V j ) = Φ -1 δ(j) • Φ -1 δ 2 (j) • Φ 3 ( V j ) ⊂ I δ(j)
, this is a part of the result (a) in the Lemma. We apply the same arguments to the neighborhood V δ(j) and we obtain:

Φ Ṽ δ(j) ( V δ(j) ) ⊂ I δ 2 (j) and Φ Ṽ δ 2 (j) • Φ Ṽ δ(j) ( V δ(j) ) ⊂ I γ 2 (ζ -1 (j)) . The last inclusion comes from Lemma 4 for k(j) = 3: δ 3 (j) = γ 2 (ζ -1 (j)). Hence, we obtain that: Φ Ṽ δ(j) ( V δ(j) ) and Φ Ṽ δ(j) • Φ Ṽ j ( V j ) are two disjoint sub-intervals of I δ 2 (j) and then V δ(j) ∩ Φ V j ( V j ) = ∅.
This completes the proof of condition (a) for the δ-side in the case k(j) = 3. For the γ-side we replace condition (E+) by (E-) and use the same arguments. The general argument, for any k(j), is the same with more compositions.

The neighborhoods

V j = V c j j ∪ V d j
j in the proof of Lemma 6 satisfy (8). Moreover, by definition of the λ-affine extension Φ Ṽ j on the interval I Ṽ j in ( 9), the two maps Φ Ṽ j and Φ Ṽ ζ -1 (j) are λ-affine on V j with:

Φ Ṽ j ( V j ) ⊂ I δ(j) \ V δ(j) and Φ Ṽ ζ -1 (j) ( V j ) ⊂ I γ(ζ -1 (j)) \ V ι(ζ -1 (j))
, from item (a). Hence, as in Lemma 6, both compositions in (b) are affine of slope λ k(j) and by (EC) they are equal on

{z j } = V c j j ∩ V d j j .
Thus we obtain the equality (b).

A parametrised extension family from Φ

The goal of this subsection is to extend further, in a parametrised way, the set of neighborhoods ν = {ν j : j = 1, . . . , 2N } used in the family f ν j in (11). The next step will be to adjust the parameters in the collection of diffeomorphisms so that the local equalities of condition (b) in Lemma 7 become global equalities in Diff + (S 1 ). We first enlarge the collection of neighborhoods, from V j to W j , on which the diffeomorphisms are affine. Recall the definition of V j via the left and right preimages of the intervals:

J c j := [ z c j , Z c j ] ⊂ I c j and J d j := [Z d j , z ζ(d j ) ] ⊂ V d j , given in (5).
Consider the intervals:

J c j := [∂ -(I Ṽ c j ); Z c j ] and J d j := [Z d j ; ∂ + (I Ṽ d j )], they satisfy: [i] I Ṽ c j ⊃ J c j ⊃ J c j and ĨV d j ⊃ J d j ⊃ J d j , [ii] Φ Ṽ c j (J c j ) ∩ Φ Ṽ d j (J d j ) = Z k(j) j by condition (EC) . (12)
Let

W j := Φ Ṽ c j (J c j ) ∪ Φ V d j (J d j )
, then from Lemma 7, exactly as in ( 7), it satisfy:

W j ∩ I Ṽ k = ∅, for all k = c j , d j and j ∈ {1, . . . , 2N }. ( 13
)
The neighborhood V j was defined as the preimages of the intervals J c j and J d j along the orbit of the cutting point zj . We do the same for the intervals J c j and J d j . The various preimages of J c j and J d j under Φ are well defined, for instance:

J d j ⊂ Φ δ k(j)-2 ( I δ k(j)-2 ) and thus ( Φ δ k(j)-2 ) -1 (J d j ) ⊂ I δ k(j)-2 .
We consider the Φ k(j)-1 pre-image of J d j and J c j along the two orbits of z j exactly as in ( 6), and we define:

W - j := Φ -k(j)+1 ∂ -(I Ṽ c j ) ; z j ⊂ I ζ -1 (j) , W + j := z j ; Φ -k(j)+1 ∂ + (I Ṽ d j ) ⊂ I j and W j := W - j ∪ W + j ⊃ V j . (14)
There are several λ-affine extensions replacing I V j , namely:

I W 1,0 j := W j ∪ I j ∪ V ζ(j) ; I W 0,1 j := V j ∪ I j ∪ W ζ(j) ; I W 1,1 j := W j ∪ I j ∪ W ζ(j) . ( 15
)
We denote the various λ-affine extensions, as in (9), by Φ W * j , where * stands for any pair in {(0, 0), (0, 1), (1, 0), (1, 1)}, and W (0,0) j = V j as a convention.

The enlargement operation: V j → W j defined above can be iterated by replacing the intervals I Ṽ j in definition ( 14) by any of the intervals I W * j . This iteration can be done "p" times on the left (-) and "q" times on the right (+). More precisely, consider the recursive definition for each j = 1, . . . , 2N :

W 0,0 j = V j , and W p,q j := Φ -k(j)+1 ∂ -(W p-1,q c j ) ; Φ -k(j)+1 ∂ + (W p ,q-1 ζ(d j )
) , for p, q > 0 and p ≤ p -1, q ≤ q -1.

(16)

This iterated enlargement defines a family of neigborhoods parametrised by the indices (p, q) (see Figure 4). We define a λ-affine extensions Φ W * j , for each set of neighborhoods in: W * = {W p j ,q j j , j ∈ {1, . . . , 2N }, p j ≥ 0, q j ≥ 0}, on the interval:

I p,q j := I W p,q j := W p,q j ∪ I j ∪ W p ,q ζ(j) . ( 17
)
The following result is a version of Lemma 7 for the neighorhoods W * j .

Proposition 2. For the intervals I p,q j and the extensions Φ W * j defined above, and all pair of finite intergers (p, q) ∈ N × N and j ∈ {1, . . . , 2N } the following properties are satisfied:

(a) Φ (p,q) j (W p,q j ) ⊂ I δ(j) \ W p,q δ(j) and Φ (p,q) j (W p,q ζ(j) ) ⊂ I γ(j) \ W p,q ι(j) , (b) Φ W * δ k(j)-1 (j) • • • • • Φ W * δ(j) • Φ W * j | W p,q j = Φ W * γ k(j)-1 (ζ -1 (j)) • • • • • Φ W * γ(ζ -1 (j)) • Φ W * ζ -1 (j) | W p,q j .
Proof. For (p, q) = (0, 0) the Proposition is Lemma 7, whose proof is based on the property (7). We observed that the condition ( 13) is exactly (7) when V j is replaced by

W j = W 1,1 j
as given in ( 16). The condition ( 13) can be expressed as:

( Φ W * ) k(j) (W 1,1 j ) ∩ Ĩk = ∅, for all k = c j , d j , in this case * = (1, 1)
. This is the first step of an induction giving, with an abuse of notations:

( Φ W * ) k(j) (W p,q j ) ∩ Ĩk = ∅, for all k = c j , d j , and all finite (p, q). (18)

The arguments in the proof of Lemma 7 are now used inductively, using (18) in place of (7) with no new difficulties.

Generators and relations from Φ

The family of diffeomorphisms [f ν j ] defined in (11) requires the collection of neighborhoods {ν j } to satisfy the conditions of Proposition 1. This is exactly part (a) in Lemma 7 (resp. Proposition 2) for the collection of neighborhoods { Ṽj } (resp. {W * j } ). Therefore the set of diffeomorphisms {f W * j ; j ∈ {1, . . . , 2N }} obtained from the neighborhoods {W * j } is well defined. In the previous notation, the set of "parameters" is hidden in the symbol * , it represents * = {(p j , q j ) ∈ N × N; j ∈ {1, . . . , 2N }}. The goal is to "adjust" these "parameters" in the familly {f W * j } so that the "partial" equalities in Proposition 2-(b) become global, i.e. equalities in Diff + (S 1 ). There are two main steps in the adjustment process:

(I) To adapt the collection of parameters {(p j , q j )} and thus the collection of neighborhoods W p j ,q j j in a coherent way in each cycle of the permutation δ.

(II) To adjust, in a coherent way, the non affine parts. This means that particular choices have to be made in the various spaces: Diff

(mon) λ -1 ,λ (L W j , R W ι(j) ) and Diff (mon) λ,λ -1 (R W j , L W ι(j) ) defined in (4).
The diffeomorphism f W * j is affine of slope λ on an interval I p j ,q ζ(j) j defined in (17) and is affine of slope λ -1 on an interval Φ W * ι(j) (I p ι(j) ,q δ(j) ι(j)

). The complementary intervals are defined by (10), for j = 1, . . . , 2N :

S 1 \ {I p j ,q ζ(j) j ∪ Φ W * ι(j) (I p ι(j) ,q δ(j) ι(j) )} = L q δ(j) ,p j j ∪ R q ζ(j) ,p ι(j) j . ( 19
)
The next result is a key step, it is an equality among some of the "variation intervals", the R * j or L * j , when the indices (p, q) satisfy some conditions. Lemma 8. With the above notations, the following equalities, among variation intervals around the cutting point z j are satisfied, for a, b, m, n ≥ 1:

(a) R a,b ζ -1 (j) = ( Φ W * j ) -1 • ( Φ W * δ(j) ) -1 • • • • • ( Φ W * δ k(j)-2 (j) ) -1 R a-1,b-1 δ k(j)-1 (j) , (b) L m,n j = ( Φ W * ζ -1 (j) ) -1 • ( Φ W * γ(ζ -1 (j)) ) -1 • • • • • ( Φ W * γ k(j)-2 (ζ -1 (j)) ) -1 L m-1,n-1 γ k(j)-1 (ζ -1 (j)) .
Proof. As in the proof of Lemma 7, we focus on the case k(j) = 3 and on one of the two symmetric equalities. For simplicity we use the parameters (p, q) only when it is necessary for the formulation, otherwise the indices are replaced by a "*", the important indices will be bolded, Figure 4 should help.

( ( ( ) ) ) ( ( ( ) ) ) and thus in the domaine of definition of Φ W * δ(j) . From the recursive definition of W p,a j in ( 16) we obtain Φ W * δ(j) • Φ p, * j W p,a j ⊂ I * ,a-1 δ 2 (j) and, in particular:

z j ~I j Ĩ j-1 ~0 1 2 0 1 2 0 1 2 0 1 2 V j Wj 2 , 1 F j-1 W ( W ) j-1 2 ,2 R j-1 1 ,2 I ~j d( ) 2 ( ( ( ) ) ) ( ( ( ) ) ) z ~j d( )+1 2 ( ) 0 1 2 F W j d( ) o F j W ( W ) j 2 ,1 j F W d( ) o ( W ) 2, 2 F W j F W o j-1 j-1 2 1 R 0 ,1 j d( ) 2 Figure 4: Variation interval equalities for k(j) = 3, with ι(j) = j and ζ ±1 (j) = j ± 1 By definition (see (19)), the variation interval R a,b ζ -1 (j) appearing in equality (a) is between W p,a j and Φ W * ι(ζ -1 (j)) [W b,q ι(ζ -1 (j)) ], see Figure 4, thus: R a,b ζ -1 (j) = [∂ + (W p,a j ), ∂ -(Φ W * ι(ζ -1 )(j) [W b,q ι(ζ -1 (j)) )]. ( 20
∂ + Φ W * δ(j) • Φ p, * j W p,a j = ∂ + I * ,a-1 δ 2 (j) . ( 21
)
The image by the same map of the other interval:

Φ W * δ(j) • Φ p, * j Φ W * ι(ζ -1 )(j) [W b,q ι(ζ -1 (j)) ] is one side of the equality (b) in Proposition 2 for W b,q ι(ζ -1 (j)) , it gives: Φ W * δ(j) • Φ p, * j • Φ W * ι(ζ -1 (j)) [W b,q ι(ζ -1 (j)) ] = Φ W * ι(δ 2 (j)) • Φ W * γ 2 (ζ -1 (j)) • Φ W * γ(ζ -1 (j)) [W b,q ι(ζ -1 (j)) ]. From (16) on W b,q ι(ζ -1 (j)) we have: Φ W * γ 2 (ζ -1 (j)) • Φ W * γ(ζ -1 (j)) [W b,q ι(ζ -1 (j)) ] ⊂ I b-1,q ι(δ 2 (j))
and in particular:

∂ -Φ W * γ 2 (ζ -1 (j)) • Φ W * γ(ζ -1 (j)) [W b,q ι(ζ -1 (j)) ] = ∂ -I b-1,q ι(δ 2 (j)) . Applying Φ W * ι(δ 2 (j)
) on both sides of this equality gives:

∂ -Φ W * ι(δ 2 (j)) • Φ W * γ 2 (ζ -1 (j)) • Φ W * γ(ζ -1 (j)) [W b,q ι(ζ -1 (j)) ] = ∂ -Φ W * ι(δ 2 (j)) [I b-1,q ι(δ 2 (j)) ] . (22)
Hence, from ( 20), ( 21) and ( 22) we obtain:

Φ W * δ(j) • Φ p, * j (R a,b ζ -1 (j) ) = [∂ + I * ,a-1 δ 2 (j) , ∂ -Φ W * ι(δ 2 (j)) [I b-1,q ι(δ 2 (j)) ] ] = R a-1,b-1 δ 2 (j)
, which is another formulation of the equality (a) in the case k(j) = 3. The equality (b) of the Lemma is obtained exactly by the same arguments on the other side of the neighborhood W * j . The general case, for any k(j), is obtained with the same arguments using k(j) -1 and k(j) compositions instead of 2 and 3 as above.

The following Lemma is stated in terms of the diffeomophisms f W * i given by (11) for the neighborhoods W p i ,q i i of z i defined in ( 16), for i = 1, . . . , 2N .

Lemma 9. For each cutting point z j of Φ there exist a collection of parameters (p i , q i ), for i and j in the same cycle of δ (resp. i and ζ -1 (j) in the same cycle of γ) and a partition of S 1 into 4k(j) intervals:

S 1 = A 0 A k(j) k(j)-1 m=1 A ± m k(j) m=1 D ± m ,
on which the compositions:

Ψ + j := f W * δ k(j)-1 (j) • • • • • f W * δ(j) • f W * j and Ψ - j := f W * γ k(j)-1 (ζ -1 (j)) • • • • • f W * γ(ζ -1 (j)) • f W * ζ -1 (j)
, satisfy the following properties:

(a) (Ψ + j ) |A ± m = (Ψ - j ) |A ± m , are affine maps of slope λ k(j)-2m for each m ∈ {0, . . . , k(j)}. (b)
The derivatives of Ψ + j and Ψ - j vary monotonically between λ k(j)-2(m-1) and λ k(j)-2m on D + m and between λ k(j)-2m and λ k(j)-2(m-1) on D - m , for each m ∈ {1, . . . , k(j)}.

Proof. Fix j ∈ {1, . . . , 2N } and consider the situation with k(j) = 3 which simplifies the computations.

•(i) Let A 0 := W p,p j for some integer p ≥ 1 large enough.

( )

( ) ) [ ] ( [ ] [ ] [ ] [ ] [ ] ) ( ( ) ( ) ( ) ( ) A 0 A 3 A 3 A 1 - A 1 + A 2 + A 2 - D 1 - D 2 D - D 3 D - D 1 + D 2 + D 3 + W j p,p F j-1 j-1 W p,p ( ) F j-1 F j-1 g( ) o W p,p ( ) j-1 g( ) j-1 g( ) F j-1 g ( ) 2 W p,p ( ) j-1 g ( ) 2 F j-1 F o o R j-1 p,p = F -1 j F -1 o R p-1,p-1 ( ) d ( j ) d ( j ) 2 F j-1 R p,p ( ) ( j-1) g = F -1 j R p-1,p-1 ( ) d ( j ) R j p -1 , p -1 = F F o R p, p ( ) g ( j -1) 2 j -1 g ( j -1) W j -1 p -1, p -1 W j +1 p -1, p -1
(Ψ + j ) |W p,p j = (Ψ - j ) |W p,p j
and is affine of slope λ k(j) for all p. This is property (a) for m = 0.

By applying Proposition 2-(b) to the neighborhood W p,p ι(γ 2 (ζ -1 (j))) , we obtain:

( Φ W * j • Φ W * δ(j) • Φ W * δ 2 (j) ) |W p,p γ 2 (ζ -1 (j)) = ( Φ W * ζ -1 (j) • Φ W * γ(ζ -1 (j)) • Φ W * γ 2 (ζ -1 (j)) ) |W p,p γ 2 (ζ -1 (j))
is affine of slope λ 3 , with the notation m = ι(m).

•(ii) Let A 3 := Φ W * j • Φ W * δ(j) • Φ W * δ 2 (j) W p,p γ 2 (ζ -1 (j))
.

By definition (11

)-[i]/[iii] of the diffeomorphisms f W * i , we obtain that (Ψ + j ) |A 3 = (Ψ - j )
|A 3 is affine of slope λ -3 . This is condition (a) for m = 3.

We define the partition and prove the Lemma on the positive side of the neighborhood W p,p j , see Figure 5.

From the two equalities in Lemma 8 we choose:

•(iii) Let D + 1 := R p,p ζ -1 (j) = ( Φ W * j ) -1 • ( Φ W * δ(j) ) -1 R p-1,p-1 δ 2 (j)
.

From definition (19) of the "variation intervals" R p,p * , the choice (iii) implies several other choices for other intervals W * , * i , for instance: W p,p δ(j) and W p,p ι(ζ -1 (j)) . Let us compute the derivatives of Ψ + j and Ψ - j , in the case k(j) = 3, via the chain rule:

dΨ + j (z) = df W * δ 2 (j) f W * δ(j) • f W * j (z) .df W * δ(j) f W * j (z) .df W * j (z), dΨ - j (z) = df W * γ 2 (ζ -1 (j)) f W * γ(ζ -1 (j)) • f W * ζ -1 (j) (z) .df W * γ(ζ -1 (j)) f W * ζ -1 (j) (z) .df W * ζ -1 (j) (z). ( 23
)
Claim. In D + 1 the derivatives dΨ + j and dΨ - j vary monotonically between λ 3 and λ. Indeed, by definition of D + 1 and (11)[ii], the first factor of dΨ + j (z) and the last factor of dΨ - j (z) in ( 23) vary monotonically between λ and λ -1 . The two other factors in dΨ ± j (z) are constant equal to λ. This is condition (b) for m = 1.

•(iv) Let A + 1 := Φ W * ι(ζ -1 (j)) [W p,p ι(ζ -1 (j))
]. The first index p is given by the previous choice in (i), the second one is a free choice. On A + 1 the map Ψ + j is affine of slope λ. Indeed, from (11) and Proposition 2 we have A + 1 ⊂ I j and Φ W * j (A + 1 ) ⊂ I δ(j) thus df W * j (z) and df W * δ(j) f W * j (z) are constant equal to λ. On the other hand, from (18), if z ∈ A + 1 then the factor df

W * δ 2 (j) f W * δ(j) • f W * j (z) is constant equal to λ -1 . For Ψ - j note, in (23), that f W * ζ -1 (j)
is affine of slope λ -1 on A + 1 ⊂ I j , and from (11) and Proposition 2, the other factors:

df

W * γ(ζ -1 (j)) f W * ζ -1 (j) (z) and df W * γ 2 (ζ -1 (j)) f W * γ(ζ -1 (j)) • f W * ζ -1 (j) (z)
, are both constant equal to λ. This implies that Ψ + j and Ψ - j are affine of slope λ. To obtain the equality:

Ψ + j |A + 1 = Ψ - j |A + 1 , we apply the equality in Proposition 2(b) to W p,p ι(ζ -1 (j)) , it gives: Φ W * δ(j) • Φ W * j • Φ W * ι(ζ -1 (j)) W p,p ι(ζ -1 (j)) = Φ W * ι(δ 2 (j)) • Φ W * γ 2 (ζ -1 (j)) • Φ W * γ(ζ -1 (j)) W p,p ι(ζ -1 (j))
. By applying each composition Ψ + j and Ψ - j to the interval

A + 1 = Φ W * ι(ζ -1 (j)) [W p,p ι(ζ -1 (j))
], a direct computation using the above equality gives:

Ψ - j (A + 1 ) = Ψ + j (A + 1 ) = Φ W * γ 2 (ζ -1 (j)) • Φ W * γ(ζ -1 (j)) [W p,p ι(ζ -1 (j))
]. This is condition (a) for m = 1.

•(v) Let A + 2 := Φ W * ι(ζ -1 (j)) • Φ W * ι(γ(ζ -1 (j))) [W p,p ι(γ(ζ -1 (j)))
]. By applying to A + 2 the same arguments used in (iv), we obtain condition (a) for m = 2. Between the intervals A + 1 and A + 2 there are the images of two variation intervals. An equality of these intervals holds if the corresponding parameters are coherent with Lemma 8. This equality is expressed as follows:

•(vi) Let D + 2 := ( Φ W * j ) -1 [R p-1,p-1 δ(j) ] = Φ W * ι(ζ -1 (j)) [R p,p γ(ζ -1 (j))
]. This variation interval equality is obtained from the one on the positive side of the neighborhood W p,p ι(ζ -1 (j)) for which the indices (p, p) are choosen to be coherent with the choice (v) and the choice R p,p γ(ζ -1 (j)) , i.e. ( Φ

W * ι(ζ -1 (j)) ) -1 • ( Φ W * j ) -1 [R p-1,p-1 δ(j) ] = R p,p γ(ζ -1 (j))
. The equality in (vi) is obtained from the above one by applying Φ W * ι(ζ -1 (j)) on both sides. The arguments to prove condition (b) for m = 2 on this interval D + 2 are exactly the same as for D + 1 . We apply the chain rule and check that only one term in the product varies monotonically between λ and λ -1 , the other terms being constant. The derivative thus varies monotonically in total between λ and λ -1 .

The last interval along the (+) side, for this case k(j) = 3, is also an interval on which a variation interval equality is satisfied:

•(vii) Let D + 3 := R p-1,p-1 j = Φ W * ι(ζ -1 (j)) • Φ W * ι(γ(ζ -1 (j))) [R p,p γ 2 (ζ -1 (j))
]. On this interval, the arguments above to prove condition (b) apply. The choice of the indices (p, p) and (p -1, p -1) comes from Lemma 8. The derivatives vary monotonically for one term in each product and the derivative vary globaly between λ -1 and λ -3 . This is condition (b) for m = 3. This completes the arguments on the positive side of the neighborhood W p,p j . The arguments are the same on the negative side, where the intervals are defined symmetrically, by replacing R by L, j by ζ -1 (j), γ by δ and for the type A intervals we consider the various images of the corresponding W -interval on the respective extension.

The choices of the parameters (p i , q i ) in the above arguments are non unique and are simply a coherence of the indices with respect to the shift property of Lemma 8.

For the general case, i.e. with any k(j), the arguments requires more compositions and each step is the same.

The variation interval equalities of Lemma 8 are central to define the partition of Lemma 9. For these equalities the "enlargement" process defined by replacing the neighborhoods V j by W p,q j in the definition (11) of f W * j is crucial, it allows many choices, in each cycle of the permutations δ or γ. By Lemma 9 the compositions Ψ + j and Ψ - j are equal except possibly on the intervals D ± m . In order to obtain a global equality for each of these compositions we have to "adjust" the various f W * i on the intervals of type D in the partition of Lemma 9.

Theorem 1. Let Φ be a piecewise homeomorphism of S 1 satisfying the ruling assumptions: (SE), (EC), (E+), (E-), (CS) and let [f W * j ] ⊂ Diff + (S 1 ) be the class of diffeomorphisms defined in (11) from the enlargement operations above. There is a choice of the diffeomorphisms: {ϕ j ∈ [f W * j ] : j ∈ {1, . . . , 2N }} so that each cutting point z j of Φ defines an equality in Diff + (S 1 ), called a cutting point relation:

(CP) ϕ δ k(j)-1 (j) • • • • • ϕ δ(j) • ϕ j = ϕ γ k(j)-1 (ζ -1 (j)) • • • • • ϕ γ(ζ -1 (j)) • ϕ ζ -1 (j) .
Proof. We fix a cutting point z j of Φ and the parameters (p i , q i ) for i and j in the same cycle of δ (resp. i and ζ -1 (j) in the same cycle of γ) given by Lemma 9.

From the partition of S 1 and the properties of Lemma 9, the equality of the two compositions Ψ + j and Ψ - j is satisfied in all the intervals of "type" A. The equality will be global, i.e. on S 1 if Ψ + j and Ψ - j agree on each intervals D ± m of Lemma 9. For this, we need to fix the various diffeomorphisms in their respective variation intervals, i.e. on the intervals R p,q i and L p ,q i given by ( 19). Let us consider for instance the interval D - 1 . From Lemma 8 we have to choose appropriate diffeomorphisms:

ϕ j ∈ [f W * j ] and ϕ γ k(j)-1 (ζ -1 (j)) ∈ [f W * γ k(j)-1 (ζ -1 (j))
] in the variation intervals (19) so that the following diagram is commutative:

D - 1 = L p,p j ϕj Lemma 8 / / L p-1,p-1 γ k(j)-1 (ζ -1 (j)) ϕ γ k(j)-1 (ζ -1 (j)) R p,p ι(j) Lemma 8 / / R p-1,p-1 ι(γ k(j)-1 (ζ -1 (j))) (24)
The pair of lower indices of L (resp. R) appearing in these equalities belong to the same cycle of δ and are at "distance" k(j) in the cycle. Moreover, the two intervals of type L (resp. R) above are related by an affine map of slope λ k(j)-1 , by Lemma 8. If we fixe: (ϕ j ) |L p,p j ∈ Diff (mon)

λ -1 ,λ L p,p j ; R p,p ι(j) , then we have to define:

(ϕ γ k(j)-1 (ζ -1 (j)) ) |L p-1,p-1 γ k(j)-1 (ζ -1 (j)) ∈ Diff (mon) λ -1 ,λ L p-1,p-1 γ k(j)-1 (ζ -1 (j)) ; R p-1,p-1 ι(γ k(j)-1 (ζ -1 (j)))
so that the diagram (24) commutes. The simplest possible choice for (ϕ j ) |L p,p j is when the derivative varies linearly. With this choice and Lemma 8, we define:

(ϕ γ k(j)-1 (ζ -1 (j)) ) |L p-1,p-1 γ k(j)-1 (ζ -1 (j))
so that the derivative vary also linearly.

The equality of the two compositions on D -

1 is satisfied for this choice. Indeed, by Lemma 9-(b), the derivative of the two compositions vary between the same values and linearly on the same interval. Note that if the derivative varies linearly on the interval L p,p j , the linearity is not satisfied for the inverse map. But fixing the map in some Diff (mon) λ -1 ,λ (X; Y), fixes the inverse map on Diff (mon) λ,λ -1 (Y; X). Thus for each variation interval that appears in the intervals D ± m of the partition in Lemma 9, a coherent choice exists so that the equality of the two compositions holds on each D ± m . For all these choices, the equality of the two compositions holds on S 1 . This is a cutting point relation (CP) associated to the cutting point z j .

-If the permutation δ has one cycle then the proof of the Theorem is complete.

-If the permutation δ has more than one cycle. We apply the previous arguments for one cycle of δ, say associated to the cutting point z j , as a step 1. This step 1 fixes the indices (p i , q i ) of the neighborhoods W * i in the cycle of δ(j). It also fixes the various ϕ i ∈ Diff + (S 1 ) in their respective variation intervals R * i and L * i , according to the partition of Lemma 9. Observe that the intervals of type A appearing in the partition of Lemma 9 are various images of all the intervals W * i for i in the cycle of δ(j). Thus if two cycles are disjoint the corresponding intervals W * are disjoint. Since δ has more than one cycle then at least one index is so that j and ζ(j) belong to different cycles. The second step is for the cycle of δ(ζ(j)). There are two different compositions Ψ ± j and Ψ ± ζ(j) of length k(j) and k(ζ(j)) and two partitions of S 1 given by Lemma 9. These two partitions have two variation intervals in common: L p,p j and R p-1,p-1 j , where the upper indices are fixed in step 1. Recall that during the proofs of Lemma 8 and 9 some of the indices (p i , q i ) are fixed by previous choices and other are free. In the present situation, for instance, the variation interval R p-1,p-1 j is fixed at step 1. This implies, for the partition associated to the cycle δ(ζ(j)), that the interval

A 0 = W α,p-1 ζ(j)
where α is a free choice. From Lemma 8 and the proof of Lemma 9 the two variation intervals L p,p j and R p-1,p-1 j are related respectively with:

L p-1,p-1 γ k(j)-1 (ζ -1 (j)) and R p,p γ k(j)-1 (ζ -1 (j))
for the cycle δ(j), and

L p+1,p+1 δ k(ζ(j))-1 (ζ(j)) and R p-2,p-2 δ k(ζ(j))-1 (ζ(j))
for the cycle δ(ζ(j)). Since the cycles δ(j) and δ(ζ(j)) are disjoint, the observation above implies that the last two intervals have not been fixed at step one for the cycle δ(j). The step 2 thus fixes the indices of the intervals W p i ,q i i for i in the cycle of δ(ζ(j)), in order that the partition of Lemma 9 is satisfied. This fixes the corresponding variation intervals. The diffeomorphisms ϕ i are fixed, as in step one, in each of the variation interval appearing as intervals of type D ± m . The upper indices are at least p -2 after step 2. We apply the same construction for each of the finitely many cycles. If the initial index p is larger than the number P (δ) of cycles then, after P (δ) steps, all the upper indices are positive and we obtain a cutting point relation (CP) associated to each cutting point. From a group theoretic point of view, the relations (CP) for cutting points in the same cycle of δ are conjugate. Thus the number of non conjugate relations (CP) is the number P (δ) of cycles of δ.

Definition 1. Let Φ be a piecewise homeomorphism of S 1 satisfying the ruling assumptions (SE), (EC), (E+), (E-), (CS). We define G X Φ the subgroup of Diff + (S 1 ) generated by the set of diffeomorphisms: X Φ = {ϕ j ∈ [f W * j ]; j ∈ {1, . . . , 2N }} given by Theorem 1. These generators verify, in particular, all the cutting point relations (CP).

There are many choices in the constructions leading to Theorem 1: -The parameters: (p i , q i ) in Lemma 9, for i and j in the same cycle of δ.

-The 2k(j) choices in the various spaces Diff 4 Some metric spaces associated to Φ

The groups G X Φ of Definition 1 are obtained, with many choices, from the map Φ. The classical strategy to study the geometry of such groups is via a geometric action on a well chosen metric space. Unfortunately no "natural" metric space is given here so we have to construct one from the given data, i.e. the dynamics of the map Φ. This is the goal of this section: to define a metric space suited to the particular class of dynamics of the maps Φ of section §2. The construction of an action will be given in the next section and, as for the metric space, it is not given a priori so it will be constructed from the available data, the map Φ. In the following we will not distinguish between the maps Φ and Φ as well as between the partition intervals I j and I j .

A first space: Γ 0 Φ

The first space we consider is directly inspired by one constructed by P. Haissinsky and K. Pilgrim [HP] (see also [H18]) in the context of coarse expanding conformal maps. In these papers, the authors use the dynamics of a map F on a compact metric space Y . They construct a graph out of a sequence of coverings of the space Y by open sets obtained from one covering by the sequence of pre-image coverings. They prove that if the map is "expanding", in a topological sense, then the resulting space is Gromov hyperbolic with boundary the space Y .

We use the same idea where the space is S 1 and the dynamics is given by Φ.

We replace their coverings by our partition and their sequence of pre-image coverings by the sequence of pre-image partitions. In order to fit with this description we use a partition by closed intervals, so that adjacent intervals do intersect in the simplest possible way, i.e. points. With our previous description we consider the initial partition: S 1 = 2N j=1 I j , with I j = [z j , z ζ(j) ], keeping the same notation for simplicity. Thus, each interval I j intersects the two adjacent intervals I ζ ±1 (j) exactly at a cutting points. We define the graph Γ 0 Φ by an iterative process (see Figure 6):

• Level 0: A base vertex v 0 is defined. • Level 1: (a) To each interval I j of the partition is associated a vertex v j . (b) v 0 is connected to v j by an edge. (c) v j is connected to v k if I j = I k and I j ∩ I k = ∅.
• Level 2: (a) A vertex v j 1 ,j 2 is defined for each non empty connected component (that is not a point) of I j 1 ,j 2 := I j 1 ∩ Φ -1 (I j 2 ). This notation is unambiguous since Φ -1 (I j 2 ) has only one connected components in • Level k: (a) We repeat level 2 by iteration, i.e. we consider a sequence of intervals {I j 1 ; I j 1 ,j 2 ; . . . ; I j 1 ,j 2 ,...,j k ; . . . } such that: I j 1 ,j 2 ,...,j k := I j 1 ,j 2 ,...,j k-1 ∩ Φ -k+1 (I j k ) = ∅. Notice that if the sequence j 1 , j 2 , . . . , j k defines an interval of level k then j i+1 = j i , for 1 ≤ i ≤ k -1, from condition (SE). (b) A vertex v j 1 ,j 2 ,...,j k is associated to the interval I j 1 ,j 2 ,...,j k , (c) v j 1 ,j 2 ,...,j k is connected to v j 1 ,j 2 ,...,j k-1 by an edge, (d) v j 1 ,j 2 ,...,j k is connected to v j 1 ,j 2 ,...,j k if:

I j 1 . (b) v j 1 is connected to v j 1 ,j 2 by an edge. (c) v j 1 ,j 2 is connected to v j 1 ,j 2 if I j 1 ,j 2 = I j 1 ,j 2 and I j 1 ,j 2 ∩ I j 1 ,j 2 = ∅. v0 v ζ -1 (j) vj vζ(j) vj,m
I j 1 ,j 2 ,...,j k = I j 1 ,j 2 ,...,j k and I j 1 ,j 2 ,...,j k ∩ I j 1 ,j 2 ,...,j k = ∅ .

Lemma 10. If Φ is a piecewise homeomorphism of S 1 satisfying the condition (SE) then the graph Γ 0 Φ , endowed with the combinatorial metric (each edge has length one), is Gromov hyperbolic with boundary S 1 .

Proof. We adapt word for word the proof in [HP]. Indeed, the essential ingredients for the proof in [HP] are the facts that each vertex is associated to a connected component of the pre-image cover with two properties:

• Each component has a uniformly bounded number of pre-images. In our case, each interval has at most 2N -1 pre-images.

• The size of each connected component goes to zero when the level goes to infinity. In our case, the size of the intervals I j 1 ,j 2 ,...,j k in the sequence of pre-images goes to zero when k goes to infinity by the expansivity property (SE). In fact a much weaker expansivity property than our condition (SE) would be enough to conclude that the graph is hyperbolic. Observe that the distance of any vertex to the base vertex is simply the level k and the edge connecting v j 1 ,j 2 ,...,j k to v j 1 ,j 2 ,...,j k , if any, belongs to the sphere of radius k centered at the base vertex. By this observation and our definition of the edges, each sphere of radius k centered at the based vertex is homeomorphic to S 1 . Therefore the limit space when k goes to infinity is homeomorphic to S 1 and the Gromov boundary ∂Γ 0 Φ is homeomorphic to S 1 .

The dynamical graph Γ Φ

Consider tree T Φ obtained from Γ 0 Φ by removing the edges on the spheres. We will define on T Φ an equivalence relation that identifies some vertices on some of the spheres using the specific properties (EC) of the map Φ.

I j = [z j , z ζ(j) ).
Labeling the edges: The edge defined by (v j 1 ,j 2 ,...,j k-1 , v j 1 ,j 2 ,...,j k ) is labelled by a symbol Ψ j k and the reverse edge, the same edge but read from v j 1 ,j 2 ,...,j k , is labelled Ψ j k .

We define a quotient map: Two vertices of T Φ are identified if they belong to the same level k > 1, we denote them v j 1 ,j 2 ,...,j k and v l 1 ,l 2 ,...,l k , and:

(a) There is an integer 0 ≤ r < k -1 such that: (a1) I j 1 ,...,j i = I l 1 ,...,l i as intervals in S 1 , for i = 1, . . . , r (if r = 0 the vertex is v 0 ). (a2) For all 1 ≤ p < k -r, the intervals I j 1 ,...,jr,j r+1 ,...,j r+p and I l 1 ,...,lr,l r+1 ,...l r+p are adjacent in the cyclique ordering of S 1 and: Φ r+m (I j 1 ,...,j r+p )∩Φ r+m (I l 1 ,...,l r+p ) = ∅, for all 0 ≤ m < p (Φ 0 denotes the identity).

(b) At level k, the intervals I j 1 ,...,j k and I l 1 ,...,l k are adjacent and:

(b1) Φ m (I j 1 ,...,j k ) Φ m (I l 1 ,...,l k ) = ∅, for all r < m < k and:

Φ k (I j 1 ,...,j k ) Φ k (I l 1 ,...,l k ) = one point, (b2) Φ k (I j 1 ,...,j k ) Φ k (I l 1 ,...,l k ) = a non degenerate interval.
Definition 2. The dynamical graph is defined by Γ Φ := T Φ / ∼ Φ , where ∼ Φ is the following relation:

(v) Two vertices v j 1 ,j 2 ,...,j k and v l 1 ,l 2 ,...,l k of T Φ are related if the conditions (a) and (b) above are satisfied. (e) Two edges, connecting vertices from level k to level k + 1, with the same label and starting from an identified vertex at level k are identified to an edge labeled with the common label.

Lemma 11. If Φ is a piecewise homeomorphism of S 1 satisfying the conditions (SE) and (EC) then the dynamical graph Γ Φ is well defined.

Proof. Let us start the study of the relation ∼ Φ when r = 0 in condition (a). Condition (a2) means, in particular, that the two intervals I j 1 and I l 1 are adjacent, so they have a cutting point z in common. Also, the k -1 first intervals in the sequence, up to I j 1 ,...,j k-1 and I l 1 ,...,l k-1 are adjacent with disjoint Φ m images for m < k -1. The condition (b1) says the Φ k images of I j 1 ,...,j k and I l 1 ,...,l k have one point in common. This point has to be the Φ k image of a cutting point z. By the eventual coincidence condition (EC) on Φ, there is indeed an integer k(z) for each cutting point, so that the two orbits of z coincide after k(z) iterates. Therefore condition (b1) is satisfied for this iterate k(z) and such a condition is satisfied for each cutting point and therefore for each pair of adjacent intervals. Since Φ is a piecewise orientation preserving homeomorphism then condition (b2) is satisfied for the same iterate k(z).

When r > 0, for each pair of adjacent intervals I j 1 ,...,jr,j r+1 and I j 1 ,...,jr,l r+1 as in condition (a2), the Φ r image of these intervals is as above, i.e. adjacent of level 1. Thus there is an integer k for which conditions (b1) and (b2) are satisfied. The identification in Definition 2-(v) is well defined and occurs at each level after some minimal level: k 0 = min{k(j)|j = 1, . . . , 2N }, where the k(j)'s are the integers of condition (EC).

1) b1) is a cutting point then all edges starting from the identified vertex at level k have different label and the identification (e) does not happen.

If the point Z = Φ k (I j 1 ,...,j k ) Φ k (I l 1 ,...,l k ) in condition (
2) If, on the other hand, Z = Φ k (I j 1 ,...,j k ) Φ k (I l 1 ,...,l k ) belongs to the interior of an interval I α then there is a sub-interval I j 1 ,...,j k ,α of I j 1 ,...,j k and an edge labeled Ψ α connecting v j 1 ,...,j k to v j 1 ,...,j k ,α and similarly an edge, labeled Ψ α , connecting v l 1 ,...,l k to v l 1 ,...,l k ,α in T Φ . The identification of the two vertices: v j 1 ,...,j k and v l 1 ,...,l k by ∼ Φ at level k implies that two edges labelled Ψ α start from the new vertex ṽ. The identification in Definition 2(e) identifies these two edges to a single edge, connecting ṽ to ṽ1 at level k + 1 and preserving the label Ψ α . This identification is well defined at level k + 1. The identification of type (e) is then applied inductively on each level following k + 1. At level k + 2, if the image Φ(Z) is a cutting point then, as in case 1), the identification of type (e) stops, i.e. the edges starting from ṽ1 have different label and no identification of type (e) occur. If Φ(Z) belongs to the interior of an interval I β then, as in case 2), two edges with label Ψ β start at ṽ1 and a new identification of type (e) occurs. The inductive identification of type (e), starting at ṽ, depends only on the orbit Φ m (Z):

-If, for some m ≥ 0, Φ m (Z) is a cutting point then the identification starting at level k at ṽ stops at level k + m, as in case 1).

-If Φ m (Z) is not a cutting point for all m ≥ 0 then the identification of type (e) starting at ṽ does not stop and is well defined for each level k + m. The dynamical graph Γ Φ is well defined from the map Φ.

It is interesting to observe that the identification of type (e) is essentially a Stallings folding [Sta].

Lemma 12. If the map Φ satisfies the ruling assumptions: (SE), (EC), (E±), (CS) then every vertex w = v 0 in the dynamical graph Γ Φ of Definition 2 is identified with an interval I w of S 1 . This interval could be of the following types: Proof. From the proof of Lemma 11, if the vertex w of Γ Φ comes from a single vertex in T Φ then it is associated to an interval of the form I j 1 ,...,j k , this is an interval of type (i). Otherwise w comes from the identification of two vertices v j 1 ,j 2 ,...,j k and v l 1 ,l 2 ,...,l k satisfying conditions (a) and (b). The associated intervals in T Φ are of the form: I j 1 ,...,j k and I l 1 ,...,l k . They are adjacent along S 1 by condition (b), therefore I w := I j 1 ,...,j k I l 1 ,...,l k is an interval, associated to w by the identification (v), it is called of type (ii-v). It occurs at a level k ≥ k 0 , where k 0 = min{k(j), j = 1, . . . , 2N }.

At level k+1, if the case 2) in the proof of Lemma 11 is satisfied, there is an identification of type (e) of the vertices v j 1 ,j 2 ,...,j k ,α and v l 1 ,l 2 ,...,l k ,α . The corresponding intervals in T Φ : I j 1 ,j 2 ,...,j k ,α and I l 1 ,l 2 ,...,l k ,α are adjacent along S 1 thus I w := I j 1 ,j 2 ,...,j k ,α I l 1 ,l 2 ,...,l k ,α is an interval, associated to the vertex w obtained by the identification of type (ii-e).

Let us observe that the neighborhood:

V j = V c j j ∪ V d j
j in the proof of Lemma 6 is exactly an interval of the form: I w := I j 1 ,...,j k ∪ I l 1 ,...,l k , i.e. of type (ii-v) at level k(j).

It turns out that the identifications of type (ii-v) and (ii-e), as described above, can interact. This happens in the following situations: An identification of type (ii-e) occurs if Z = Φ k(j) (z j ) ∈ int(I α ) for some α. Assume that Z = Φ k(j) (z j ) ∈ V α ∩ I α . An identification of type (ii-e) occurs at level k(j) + 1 and, by condition (E+), Φ m (Z) ∈ I δ m (α) for m ≤ k(α) -1. This implies that Φ m (Z) is not a cutting point for all m ≤ k(α) -1. By condition 2) in the proof of Lemma 11 an identification of type (ii-e) occur from level k(j) + 1 up to level k(j) + k(α) -1. At level k(j) + k(α) an identification of type (ii-e) and of type (ii-v) occur at the same level. In this case, three intervals of the tree T Φ are involved :

I j 1 ,...,j k(j) ,α ,...α k(α) , I j 1 ,...,j k(j) ,α,...α k(α) , I l 1 ,...,l k(j) ,α,...α k(α) , where α = ζ -1 (α).

As in the previous cases, these intervals are pairewise adjacent along S 1 and the identification of both types (ii-e) and (ii-v) is associated to the union: I w := I j 1 ,...,j k(j) ,α ,...α k(α)

I j 1 ,...,j k(j) ,α,...α k(α) I l 1 ,...,l k(j) ,α,...α k(α) , this is an interval. For the next levels, the two cases 1) or 2) in the proof of Lemma 11 might occur, depending on the orbits of each cutting points, i.e. z j and z α .

The phenomenon described above, where two identifications of type (ii-e) and (ii-v) arise for the same vertex, can possibly occur at any level large enough. The intervals in T Φ that are involved are pairewise adjacent, as above, and the union of these interval is an interval. The number n m of these intervals depends on the map Φ via the orbits of the cutting points and on the level m.

From the proof of Lemma 11 there is a difference between the vertices of type (ii) obtained after an identification of type (v) or type (e) in Definition 2. A vertex obtained by an identification of type (v) has two incoming edges, i.e. from level k -1 to level k. A vertex obtained by an identification of type (e) has only one incoming edge, as the vertices of type (i). If necessary, we will mark the difference by denoting the corresponding vertices or intervals of type (ii-v) or type (ii-e).

Proposition 3. If Φ and Φ are two piecewise homeomorphisms of S 1 with the same combinatorics, i.e. the same permutations ζ and ι, the same properties (SE), (EC), (E+), (E-), (CS) with the same slope, then the graphs Γ Φ and Γ Φ are homeomorphic.

Proof. Since the combinatorics are the same, all the combinatorial data used in the constructions: k(j), γ and δ are the same for Φ and Φ . The identification of type (ii-v) defines vertices with two incoming edges, and 2N -2 outgoing edges, by condition (7) in the proof of Lemma 6. The vertices of types (i) and (ii-e) have one incoming edge and 2N -1 out going edges by condition (SE). The identifications process could be quite different for different maps but each resulting vertex has the same structure, even as a labeled graph. Therefore the two graphs are homeomorphic.

Lemma 13. Let Φ : S 1 → S 1 satisfying the conditions (SE), (EC), (E+), (E-), (CS) then there exists Φ : S 1 → S 1 with the same combinatorics as Φ so that the identifications of type (ii) in Lemma 12 are all 2 to 1.

Proof. The idea is to change the map Φ by changing the cutting points while preserving the combinatorics. We replace Φ by the affine map Φ via the conjugacy of condition (CS), the combinatorics are evidently the same. Consider the neighborhood V j of Lemma 6 and the λ-affine extension Φ Ṽ j of Lemma 7. Lemma 7 (a) implies:

Φ Ṽ j (V j ) ⊂ Ĩδ(j) \ V δ(j)
and conditions (E±), together with the definition of V j give:

Φ m ( Φ Ṽ j ( V j )) ∈ Ĩδ m+1 (j) and Φ m ( Φ Ṽ ζ -1 ( V j )) ∈ Ĩγ m+1 (ζ -1 ) , for 0 ≤ m ≤ k(j) -2. ( 25
)
The condition (EC) gives Z = Φ k(j) (z j ) ∈ Ĩα , for some α ∈ {1, . . . , 2N }. Consider the fixed point p α ∈ Ĩα of Φ α , given by condition (SE). The definition of the involution ι and condition (SE) implies that the fixed point p α belongs to the subinterval I α,α which is disjoint from I α,δ(α) ∪ I α,γ(α) . By definition of the intervals V j in Lemma 6 we obtain:

p α / ∈ V α ∪ V ζ(α) . If Z = p α then we do not change the cutting point z j . If Z = p α then either p α ∈ Φ k(j) (V + j ) for V + j := V j ∩ I j or p α ∈ Φ k(j) (V - j ) for V - j := V j ∩ I ζ -1 (j) . Assume, for instance, that p α ∈ Φ k(j) (V + j ) and let p α j = Φ -k(j) (p α ) ∈ V +
j ⊂ Ĩj , the other case is symmetric. The goal is to transform the map Φ to Φ so that p α j is the new cutting point. Since p α j ∈ V + j ⊂ Ĩj we define Φ j = Φ j on the interval [p α j , zζ(j) ). We define the map Φ ζ -1 (j) by the λ-affine extension of Φ ζ -1 (j) , i.e. from the interval [z ζ -1 (j) , zj ) to [z ζ -1 (j) , p α j ) as in (9). We apply the same construction for each cutting point. The permutations ζ and ι as well as all the k(j) are the same for Φ as for Φ. The properties in (25), coming from Lemma 7(a) and (E±) for Φ, imply that the conditions (E±) are satisfied by Φ . The condition (EC) is satisfied by Φ from the equality (b) in Lemma 7. Condition (CS), with slope λ is obviously satisfied. The two maps Φ and Φ have thus the same combinatorics.

The choice of the new cutting point p α j of Φ implies that Z = Φ k(j) (p α j ) = p α which is fixed by Φ since Φ = Φ outside the set V j and we observed that p α / ∈ V α ∪ V ζ(α) . Therefore we obtain: Φ m (Z ) = p α for all m ≥ 0 and thus this orbit is always outside the set V j . By the proof of Lemma 12 the identifications of type (ii-e) occur at all levels after level k(j) and do not interact with identifications of type (ii-v). Therefore the identifications of type (ii) in Lemma 12 are all with two intervals, i.e. are 2 to 1.

Remark 3. All the cutting points of the new map Φ are pre-periodic and thus the map satisfies a Markov property.

Lemma 14. The two graphs Γ Φ and Γ 0 Φ , endowed with the combinatorial metric (every edge has length one), are quasi-isometric.

Proof. Let us denote by d Γ 0 Φ and d Γ Φ the combinatorial distances in Γ 0 Φ and Γ Φ . The two sets of vertices V (Γ 0 Φ ) and V (Γ Φ ) are related by a map:

V : V (Γ 0 Φ ) → V (Γ Φ )
which is induced by the relation ∼ Φ of Definition 2 and is at most 2 to 1 by Lemma 13. Each vertex v ∈ V (Γ 0 Φ ) \ {v 0 } is identified with an interval I v := I j 1 ,...,j k and thus with a vertex of the tree T Φ . Two vertices of Γ 0 Φ with the same V -image correspond to adjacent intervals at the same level k, they are at distance one in Γ 0 Φ . Two vertices connected by an edge on a sphere S 0 p of radius p centered at the base vertex v 0 in Γ 0 Φ are mapped either to a single vertex in the sphere S p of radius p, centered at v 0 in Γ Φ or to two distinct vertices on the same sphere. These two vertices are connected in Γ Φ by a path of length at most k(j), for some j ∈ {1, . . . , 2N }, where k(j) is the integer in the condition (EC). We define K Φ := max{k(j)|j = 1, . . . , 2N } then we obtain:

d Γ Φ (V (v 0 α ), V (v 0 β )) ≤ K Φ .d Γ 0 Φ (v 0 α , v 0 β ) + C, for any pair of vertices (v 0 α , v 0 β ) in V (Γ 0 Φ ) × V (Γ 0 Φ
). Indeed a minimal length path between v 0 α and v 0 β is a concatenation of some paths along the spheres centered at v 0 and some paths along rays starting at v 0 . The length of the paths along the rays are preserved by the map V and the length of the paths along the spheres are at most expanded by a factor bounded by K Φ . On the other direction, the same observation and the fact that V could identify at most two vertices implies:

d Γ Φ (V (v 0 α ), V (v 0 β )) ≥ 1 K Φ d Γ 0 Φ (v 0 α , v 0 β ) -C.
Corollary 1. The graph Γ Φ , with the combinatorial distance, is hyperbolic with boundary homeomorphic to S 1 .

Proof. A metric space quasi-isometric to a Gromov hyperbolic space is Gromov hyperbolic with the same boundary [GdlH]. By Lemmas 10 and 14 the graph Γ Φ is hyperbolic with boundary S 1 . By Proposition 3 the same property is satisfied by Γ Φ .

5 An action of G X Φ on Γ Φ

The groups G X Φ of Definition 1 are subgroups of Homeo + (S 1 ) and are our main object of study for the rest of the paper. The natural way to study these groups is via a geometric action on a metric space. The graph Γ Φ of the previous section is a hyperbolic metric space that reflects the dynamics of the map Φ. It is our candidate metric space but an action of each G X Φ on Γ Φ has to be defined, via the data we have, the dynamics of Φ.

Recall that a geometric action of a group on a metric space is a morphism, acting by isometries that is co-compact and properly discontinuous. By Lemma 12, each vertex v ∈ V (Γ Φ ) is identified with an interval I v ⊂ S 1 and each g ∈ G X Φ is, in particular, a homeomorphism of S 1 . We need to understand, for g ∈ G X Φ how the interval g(I v ) is related to some I w for w ∈ V (Γ Φ ). An ideal situation would be that for "all v and all g there is w so that g(I v ) = I w ", we will see immediately that this ideal situation does not happens for all vertices (see Lemma 15). The idea for defining an action is to weaken this ideal situation and allow the two intervals g(I v ) and I w to be "close enough", i.e. to admit a controlled error.

A preliminary step

Let us describe how the generators ϕ j ∈ X Φ of the group do act on the partition intervals I m for all m ∈ {1, . . . , 2N }, i.e. on the intervals associated to vertices of level 1 in Γ Φ . Recall that in this section we do not distinguish between the intervals I j and Ĩj .

Lemma 15. If Φ is a piecewise homeomorphism of S 1 satisfying the conditions (SE), (E-), (E+), (EC) and (CS), let ϕ j ∈ X Φ be a generator of the group G X Φ given by Theorem 1. If I m is a partition interval, m ∈ {1, . . . , 2N } then ϕ j (I m ) satisfies one of the following conditions:

(I ζ -1 (j) ) = I ι(j),ζ -1 (j) ∪ R ι(j) ,
where L ι(j) and R ι(j) are defined in (3), they satisfy: L ι(j) I γ(j),γ 2 (j),...,γ k(ζ(j))-1 (j) , and R ι(j) I δ(j),δ 2 (j),...,δ k(j)-1 (j) , k(ζ(j)) and k(j) are the integers of condition (EC).

Proof. The proof is a case by case study.

(a) This is simply condition (SE) on the map Φ. (b) By Lemma 5 and the choices made in Theorem 1, the generators satisfy:

(ϕ j ) | Φ ι(j) (I ι(j) ) = ( Φ ι(j) ) -1 | Φ ι(j) (I ι(j) )
. Condition (SE) implies that: Φ ι(j) (I ι(j) ) ∩ I m = I m , for all m = j, ζ ±1 (j). Therefore we obtain:

I ι(j) ∩ Φ -1 |I ι(j) (I m ) = Φ -1 |I ι(j)
(I m ) which reads:

I ι(j),m = ϕ j (I m ) (see Figure 7). (c) The two situations are symmetric, we restrict to one of them, for instance to ϕ j (I ζ(j) ). By condition (SE), applied to I j and I ι(j) , we have: (i) ϕ j (I j ) ∩ I γ(j) I γ(j) , and (ii) ϕ ι(j) (I ι(j) ) ∩ I ζ(j) I ζ(j) .

ϕ j (I ζ(j) ) ∩ I ι(j) = Φ -1 |I ι(j) (I ζ(j) ) ∩ I ι(j) = I ι(j),ζ(j) .
Thus, we obtain ϕ j (I ζ(j) ) = I ι(j),ζ(j) ∪ L ι(j) (see Figure 7).

To complete the proof we verify the properties of the interval L ι(j) (resp. R ι(j) ). With the notations of the cutting points, this interval is:

L ι(j) = [ϕ j (z ζ(j)
), z ι(j) ] (see Figure 7). By condition (E+) at z ζ(j) we have: ∀i,

0 ≤ i ≤ k(ζ(j)) -2 : Φi ( Φj (z ζ(j) )) ∈ I γ i+1 (j) . For i = 0: Φj (z ζ(j) ) = ϕ j (z ζ(j) ) ∈ I γ(j)
, and for i = 1: Φ( Φj (z ζ(j) )) ∈ I γ 2 (j) , this last condition means that the Φ image of the point ϕ j (z ζ(j) ) ∈ I γ(j) belongs to the same partition interval as the Φ image of the cutting point z ι(j) . Therefore the point ϕ j (z ζ(j) ) belongs to the interior of the last sub-interval of level 2 of the partition interval I γ(j) which is I γ(j),γ 2 (j) . This implies that: L ι(j) I γ(j),γ 2 (j) which is part of the statement. At this stage we only use the first iterate (i = 1) in conditions (E+). The proof of (c) is completed by applying the same arguments for all iterates: i ≤ k(ζ(j)) -2 in condition (E+), we obtain:

L ι(j) I γ(j),γ 2 (j),...,γ k(ζ(j))-1 (j) .

This completes the proof of statement (c) in this case. The symmetric situation in case (c), is obtained by replacing ζ by ζ -1 , γ by δ and condition (E+) by (E-).

Additional properties of Γ Φ

From the proof of Lemma 15, the intervals of level m + 1 ≤ k(j) -1 in the tree T Φ that are extrem in the interval I j , i.e. contain a cutting point, are of the form:

I j,δ(j),...,δ m (j) and I j,γ(j),...,γ m (j) .

The intervals of type (ii) and level k(j) in the proof of Lemma 12 are thus of the form:

I ṽj := I j,δ(j),...,δ k(j)-1 (j) ∪ I ζ -1 (j),γ(ζ -1 (j)),...,γ k(j)-1 (ζ -1 (j)) , (27)
where the first interval is extrem of level k(j) on the (+) side of zj and the second is extrem on the (-) side of the same cutting point. This interval is of type (ii-v). It contains sub-intervals of level k(j) + 1 and possibly one with the cutting point z j in its interior, as in case 2) in the proof of Lemma 11:

I ṽj ,α := I ζ -1 (j),γ(ζ -1 (j)),...,γ k(j)-1 (ζ -1 (j)),α ∪ I j,δ(j),...,δ k(j)-1 (j),α ,
For the next iterate of Φ, the condition (7) implies: Φ k(j)-1 (ϕ j (I ṽj )) ∩ I m = ∅ for all m = γ k(j)-1 (ζ -1 (j)), δ k(j)-1 (j). We observe that I ṽδ(j) ∩ I δ(j) is a subinterval of I δ(j),δ 2 (j),...,δ k(j) (j) of level k(j) and by Lemma 7-(a) we have: ϕ j (I ṽj ) ∩ I ṽδ(j) = ∅. Therefore ϕ j (I ṽj ) intersects all subintervals of level k(j) of I δ(j),δ 2 (j),...,δ k(j)-1 (j) , except one, i.e. I ṽδ(j) ∩ I δ(j) .

If I ṽj is replaced by I ṽζ(j) then the same arguments apply by replacing δ(j) with γ(j).

2) For I ṽl = I ζ -1 (l),γ(ζ -1 (l)),...,γ k(l)-1 (ζ -1 (l)) ∪ I l,δ(l),...,δ k(l)-1 (l) , we have

ϕ j (I ζ -1 (l),γ(ζ -1 (l)),...,γ k(l)-1 (ζ -1 (l)) ) = I ι(j),ζ -1 (l),γ(ζ -1 (l)),...,γ k(l)-1 (ζ -1 (l))
and ϕ j (I l,δ(l),...,δ k(l)-1 (l) ) = I ι(j),l,δ(l),...,δ k(l)-1 (l) because I ṽl ⊂ Φ ι(j) (I ι(j) ) and l / ∈ {j, ζ(j)}, this is the same argument as in case (3) of Proposition 5. Then:

ϕ j (I ṽl ) = I ι(j),ζ -1 (l),γ(ζ -1 (l)),...,γ k(l)-1 (ζ -1 (l)) ∪ I ι(j)
,l,δ(l),...,δ k(l)-1 (l) = I ι(j),ṽ l , with the notation (28).

The action

The goal in this paragraph is to define a map A g : Γ Φ → Γ Φ for all g ∈ G X Φ . Lemma 15, Proposition 5 and Proposition 6 are a guide line to this aim. From Lemma 12, each vertex v = v 0 of Γ Φ is identified with an interval I v of S 1 , and each g ∈ G X Φ maps I v to g(I v ), another interval of S 1 . We have to understand how each interval g(I v ) is related to some interval I w , for a vertex w of Γ Φ . Lemma 15 implies in particular that we cannot expect: "g(I v ) = I w " for all intervals I v . But it shows that if we allow a "small" error then we can associate to g(I v ) an interval I w . This is one way to interpret Lemma 15 case (c), and its consequences in Proposition 5 cases (1-b) and (2-b).

Definition 3. Let G X Φ be a group from Definition 1, and let Γ Φ be the dynamical graph of Definition 2 with vertex set V (Γ Φ ). For each v ∈ V (Γ Φ ), let I v be the interval associated to v by Lemma 12. For each generator ϕ j ∈ X Φ , j = 1, . . . , 2N , let: A ϕ j : V (Γ Φ ) → V (Γ Φ ) be a map defined as follows:

(1) If v = v 0 and ϕ j (I v ) intersects all partition intervals I k of level one except one, then:

A ϕ j (v) := v 0 (2) If v = v 0
and there exists w ∈ V (Γ Φ ) such that ϕ j (I v ) ⊆ I w and ϕ j (I v ) intersects all subintervals I w ⊂ I w of level one more than w, except possibly one, then:

A ϕ j (v) := w (3) (i) If v = v 0
and there exists w ∈ V (Γ Φ ) a vertex of type (i) or (ii-e) in Lemma 12 such that I w ⊂ ϕ j (I v ) and no other I w , for w of the same level as w is contained in ϕ j (I v ) then: A ϕ j (v) := w (ii) If v = v 0 and there exists w ∈ V (Γ Φ ) a vertex of type (ii-v) in Lemma 12 such that I w ⊂ ϕ j (I v ) and ϕ j (I v ) does not contain I w for w of level one less that w then:

A ϕ j (v) := w (4) A ϕ j (v 0 ) := v ι(j) If g = ϕ n 1 • • • • • ϕ n k we define A g := A ϕn 1 • • • • • A ϕn k . ϕ j (I v ) = I ṽδ(j) ∪ [R ι(j) \ I δ(j),...,δ k(j) (j) ].
Therefore ϕ j (I v ) contains the interval of type (ii) I ṽδ(j) of level k(j) and does not contain any interval of level k(j) -1. Thus, by Definition 3 case (3-ii) we obtain:

A ϕ j (v) = v ṽδ(j) .
2) If v is a vertex of type (ii), the image of the corresponding interval under ϕ j is given by Proposition 6, which gives:

(a) A ϕ j (ṽ j ) = v δ(j),δ 2 (j),...,δ k(j)-1 (j) and A ϕ j (ṽ ζ(j) ) = v γ(j),γ 2 (j),...,γ k(ζ(j))-1 (j) , by Proposition 6 case (1) and Definition 3 case (2). (b) A ϕ j (ṽ n ) = ṽι(j),n , for n / ∈ {j, ζ(j)}, by Proposition 6 case (3), Definition 3 case (2).

This completes the case by case proof for all the vertices in C v 0 .

Remark 5. The vertices studied in Proposition 7 are associated to intervals containing a cutting point, either in its boundary or in its interior. There are many other intervals, they are of the form I j 1 ,j 2 ,...,jr where j 2 / ∈ {γ(j 1 ), δ(j 1 )} or j 2 ∈ {γ(j 1 ), δ(j 1 )} and j 3 / ∈ {γ 2 (j 1 ), δ 2 (j 1 )} and so on. Suppose that v j 1 ,j 2 ,...,jr is a vertex associated to such an interval then:

(1) If j 1 = j: then A ϕ j (v j,j 2 ,...,jr ) = v j 2 ,...,jr , by the definition of I j 1 ,j 2 ,...,jr and Definition 3 case (2). (2) If j 1 = j: then A ϕ j (v j 1 ,j 2 ,...,jr ) = v ι(j),j 1 ,j 2 ,...,jr , by the definition of I j 1 ,j 2 ,...,jr , and Definition 3 case (2).

The following result is a co-compactness property for the maps A .

Proposition 8. For any vertex v ∈ V (Γ Φ ) \ {v 0 } of level n, there exists a group element g ∈ G X Φ of length l ≤ n so that:

A g (v) ∈ C v 0 .
Proof. Assume that v is of type (i) and let I v = I j 1 ,j 2 ,...,jn . If I v does not contain a cutting point z j 1 or z ζ(j 1 ) on its boundary, then by Remark 5 case (1), we have: I v ⊂ int(I j 1 ) and ϕ j 1 (I v ) = I j 2 ,...,jn is an interval of type (i) and level n -1 and thus: A ϕ j 1 (v) = v j 2 ,...,jn .

If I v = I j 1 ,j 2 ,...,jn is of type (i) and contains z j 1 or z ζ(j 1 ) on its boundary then ϕ j 1 (I v ) ⊂ I j 2 ,...,jn and intersects all subintervals of level n, as in Proposition 5 case (1-a) and thus: A ϕ j 1 (v) = v j 2 ,...,jn is a vertex of level n -1.

If I v = I j 1 ,j 2 ,...,jn is of type (ii) and does not contain z j 1 or z ζ(j 1 ) then, as above we obtain: A ϕ j 1 (v) = v j 2 ,...,jn is a vertex of level n -1.

If I v = I j 1 ,j 2 ,...,jn is of type (ii) and contains z j 1 or z ζ(j 1 ) on its interior then, as in Proposition 6 case (1), ϕ j 1 (I v ) ⊂ I j 2 ,...,jn and intersects all subintervals of level n maybe except one and thus A ϕ j 1 (v) = v j 2 ,...,jn is a vertex of level n -1.

In all cases, there is a generator ϕ j 1 so that A ϕ j 1 (v) is a vertex of level n -1. By iterating this argument, we obtain a finite sequence of generators: ϕ j 1 , ϕ j 2 , . . . , ϕ jm with m ≤ n -1 so that:

A ϕ jm •••••ϕ j 1 (v) ∈ C v 0 .
Let us extend the map A ϕ j , defined on the vertices of Γ Φ , to a map on the graph. We denote by e := (v, w) the edge connecting the vertices v and w in Γ Φ .

If k = j then the image of the two edges are A ϕ j (v 0 , v j ) = (v ι(j) , v 0 ) and A ϕ j (v 0 , v ζ(j) ) = (v ι(j) , v ι(j),ζ(j) ), these two edges are consecutive around v ι(j) . Hence A ϕ j preserves the cyclic ordering of the edges around v 0 . The proof for the other vertices is the same. From Proposition 7, Remark 5, Proposition 8 and since each generator ϕ j is orientation preserving, the natural cyclic ordering at each vertex is preserved by the action. By composition, the same is true for each element in G X Φ .

G X Φ is a surface group

The lenght of an element g ∈ G X Φ is, as usual, the length of the shortest word expressing it in the generators X Φ .

Proposition 11. Each element g ∈ G X Φ of length n admits a non trivial interval J g so that g| Jg is affine with slope λ n . In addition, if g has more than one expression of length n, then two expressions differ by some Cutting Point relations R z j of Theorem 1 for some j ∈ {1, . . . , 2N }.

Proof. Let us consider the collection of integers given by (EC): {k(j); j ∈ {1, . . . , 2N }}, with K 0 and K Φ the minimal and maximal values of this set.

We start the proof for the elements g ∈ G X Φ of length n ≤ K Φ , i.e with an expression:

g = ϕ jn • • • • • ϕ j 1 , satisfying, at least: ϕ j i+1 = ϕ j i for i = 1, . . . , n -1.
(I) By condition (SE), the map Φj 1 can be followed by any Φk , except k = ι(j 1 ) = j1 , for an iterate of length 2. This implies, from the definition of the generators in Definition 1, that for each j 2 = j1 , the element g = ϕ j 2 • ϕ j 1 admits J g = I j 1 ,j 2 as an interval where g| Jg is affine with slope λ 2 . This is the maximal possible slope for an element of length 2 in the group G X Φ . Thus this element cannot be expressed with less generators. The case n = K 0 is described below in (III), we assume here that K 0 > 2 and postpone the proof that g has only one expression of length 2 in this case. In addition there cannot be more elements of length 2, starting with ϕ j 1 , since G X Φ has 2N generators and ϕ j 1 can be followed by any of the 2N -1 generators different from ϕ j1 by condition (SE).

(II) For 2 < n < K 0 we replace, in the above arguments, condition (SE) by the conditions (E-) and (E+) and we obtain that for all n < K 0 the element g = ϕ jn •• • ••ϕ j 1 is of length n with only restriction that ϕ j i+1 = ϕ j i , for all i = 1, . . . , n -1. On the graph Γ Φ , all the vertices v in the interior of the ball Ball(v 0 , K 0 ) are of type (i) and, on the corresponding interval I v = I j 1 ,...,jn , the map g| I j 1 ,...,jn is affine with slope λ n , this is the maximal possible slope for an element of length n and we choose J g = I j 1 ,...,jn .

(III) For n = K 0 let us consider an integer j ∈ {1, . . . , 2N } so that k(j) = K 0 . The element: g = ϕ δ k(j)-1 (j) • . . . ϕ δ(j) • ϕ j has, at least, two expressions by Theorem 1. This element admits an interval V j given by Lemma 6 on which g| V j is affine with slope λ n . By definition of the generators in Theorem 1, the interval V j might not be maximal with the property that the element is affine of slope λ n . This interval is also denoted I ṽj in (27) and it is of type (ii) according to Lemma 12. We choose in this case J g = I ṽj .

By condition (7) in the proof of Lemma 6, the two expressions of g above can be followed by any ϕ α for α / ∈ {γ k(j)-1 (ζ -1 (j)), δ k(j)-1 (j)}. The two expressions of g, given by the cutting point relation R z j , have length n and have 2N -2 possible successors, i.e. elements of length n + 1 with the same beginning, by condition (7). The element g cannot have more than two expressions, by a counting argument as in (I), this also proves that in cases (I) and (II) (when n < K 0 ) the expression is unique. The elements g of length less than K 0 are covered by one of the above cases (II) or (III). In all the cases the interval J g is chosen either as I j 1 ,...,jn in the cases (i) or I ṽj in cases (ii). In addition, the element g has either exactly one expression of length n (case (i)) or exactly two (in case (ii)). If K 0 = K Φ then all the cases in Ball(v 0 , K Φ ) are covered.

(IV) For K 0 < n ≤ K Φ the arguments above are valid. Let g := ϕ jn • • • • • ϕ j 1 , it could happens that g has more than one expressions. By the above arguments, this is possible only if some sub-word of g, i.e. an expression of the form: g r = ϕ j r+k(jr ) •• • ••ϕ jr is so that the interval I j 1 ,...,j r-1 ,jr,...,j r+k(jr ) is contained in an interval of type (ii) I ṽ ,jr , given by ( 28), for some j r so that k(j r ) < n. In this case, the element g admits two expressions that differs by the cutting point relation R z jr of Theorem 1. For the intervals, we consider the following cases: (a) If for all possible j r we have n > r + k(j r ) then g is so that I j 1 ,...,jn is an interval of type (i) or of type (ii-e) and we choose J g = I j 1 ,...,jn . (b) If there is j r such that n = r + k(j r ) then g is associated to an interval I ṽ ,jr of type (ii-v) (see ( 28)) and we choose J g = I ṽ ,jr . This completes the proof for the elements of length less than K Φ .

(V) For an element g = ϕ jn • • • • • ϕ j 1 of length n > K Φ , the initial part of this expression of length K Φ , i.e. g 1 = ϕ j K Φ • • • • • ϕ j 1 is covered by the previous arguments. Thus there is an interval J g 1 so that g 1|J g 1 is affine with slope λ K Φ and two cases can occur: either J g 1 is of type (i) (resp. (ii-e)) or of type (ii-v). If J g 1 is of type (i) then, by the arguments in (II) above, g 1 has exactly 2N -1 possible continuations of length K Φ + 1 and g

2 = ϕ j K Φ +1 • ϕ j K Φ • • • • • ϕ j 1 is
one of these continuations. The same argument applies to g 2 and we obtain an interval J g 2 ⊂ J g 1 . If J g 1 is of type (ii-v) then, by the argument in case (III), g 1 has exactly 2N -2 possible continuations of length K Φ + 1 and g

2 = ϕ j K Φ +1 • ϕ j K Φ • • • • • ϕ j 1 is
one of these continuations. Again the same argument applies to g 2 . In all these cases we obtain an interval J g 2 so that g 2| Jg 2

is affine with slope λ K Φ +1 . The proof of the Proposition is completed by induction.

By combining the various results above we obtain:

Lemma 16. For all g ∈ G X Φ , A g : Γ Φ → Γ Φ is a well defined morphism and the map A : G X Φ → Aut(Γ Φ ) defined by A (g) := A g is a geometric action of G X Φ on Γ Φ .
Proof. Each map A ϕ j is a bijective isometry on the compact sets C 0 by Proposition 9 and A ϕ j (C v ) = C Aϕ j (v) for any C v by Proposition 10. Therefore any composition:

A ϕ jn • • • • • A ϕ j 1 is an isometry. By definition, A ϕ jn • • • • • A ϕ j 1 = A ϕ jn •••••ϕ j 1
we have to check this expression does not depend on the expression of the group element g = ϕ jn • • • • • ϕ j 1 , i.e. this map is a well defined morphism.

By Proposition 11, the set of relations in G X Φ for the generating set X Φ are: 1) The trivial relations: ϕ j • ϕ ι(j) = Id, or 2) the cutting point relations R z j of Theorem 1, for j = 1, . . . , 2N .

We verify that the map A respects these relations and, by Proposition 8, it is sufficient to check it on the compact set C v 0 . 1) For the trivial relations: by Definition 3 we have A ϕ j (v 0 ) = v ι(j) and A ϕ ι(j) (v ι(j) ) = v 0 . For the other vertices v = v 0 in C v 0 we have either v = v j 1 ,γ(j 1 ),...,γ n (j 1 ) or v = v j 1 ,δ(j 1 ),...,δ n (j 1 ) , for n ≤ k(j 1 ) -1. The proof follows from the case by case study in the proofs of Proposition 7 and Proposition 9, we obtain: A ϕ ι(j) • A ϕ j = Id is the identity on C v 0 and thus on Γ Φ .

2) For the cutting point relations R z j : they are related to several properties of the map Φ and the space Γ Φ . It is associated to each cutting point of the map via the condition (EC), and to the equivalence relation of Definition 2 via the notion of vertices and intervals of type (ii-v) according to Lemma 12. This implies that the cutting point relations are also associated with the "loops", based at any vertex v by Corollary 2. Recall that the compact sets C v are defined in Remark 4 as the union of all the loops, based at v. By Proposition 10, A ϕ j (C v ) = C Aϕ j (v) and A ϕ j is a bijective isometry by Proposition 9. This implies, in particular, that each loop, based at v is mapped to a loop, based at A ϕ j (v), for all j and all v. Thus the map A respects all the cutting point relations.

By the Propositions 8 and 10, the map A is co-compact and thus A is a well defined, co-compact isometric morphism.

It remains to check that A is properly discontinuous. The graph Γ Φ is locally compact so a compact set in Γ Φ is contained in a ball of finite radius. If C 1 and C 2 are two compact sets in Γ Φ we can assume that C 1 is contained in a ball of radius R centered at v 0 . By Proposition 8 there are elements g ∈ G X Φ so that A g (C 2 ) ∩ C 1 = ∅. These elements have a length, in the generating set X Φ , which is bounded in term of the distance in Γ Φ , between C 1 and C 2 . Thus the set {g ∈ G X Φ : A g (C 2 ) ∩ C 1 = ∅} is finite and the action is properly discontinuous. Therefore the map A is a geometric action.

As a consequence of the above properties we obtain the following result: Theorem 2. Let Φ be a piecewise orientation preserving homeomorphism on the circle satisfying the conditions: (SE), (E+), (E-), (EC), (CS). Let G Φ := G X Φ be the sub-group of Homeo + (S 1 ) given in Definition 1 for one choice of generating set X Φ then:

(1) The group G Φ is discrete and does not depend on the choice in the generating set X Φ of Definition 1.

(2) The group G Φ is a Gromov-hyperbolic group with boundary S 1 .

(3) The group G Φ is a surface group.

• If Φ n (x) = Φ m (y) then there are two sequences of integers {j 1 , . . . , j n } and {l 1 , . . . , l m } such that:

ϕ jn • • • • • ϕ j 1 (x) = ϕ lm • • • • • ϕ l 1 (y).
This implies that y = g(x) for g = (ϕ lm

• • • • • ϕ l 1 ) -1 • ϕ jn • • • • • ϕ j 1 ∈ G Φ .
• For the other direction we assume y = g(x) and, since X Φ = {ϕ 1 , . . . , ϕ 2N } is generating G Φ , it is sufficient to restrict to g = ϕ j ∈ X Φ .

Recall that each generator ϕ j ∈ X Φ of Definition 1 is, by Lemma 5, a Möbius like diffeomorphism with exactly two neutral points, N + j and N - j , i.e. two points with derivative one. By construction, each interval of the partition satisfies: I j = [ z j , z ζ(j) ) ⊂ (N - j , N + j ) since (ϕ j ) | I j is expanding. By the chain rule we have:

ϕ ι(j) (N - ι(j) ) = N + j and ϕ ι(j) (N + ι(j) ) = N - j . Let us assume x is not a neutral point for ϕ j thus either: d(ϕ j (x)) > 1 or d(ϕ j (x)) < 1.

In the second case x = ϕ -1 j (y) and d ϕ -1 j (y) > 1. By this symmetry we assume that

x ∈ (N - j , N + j ). Two cases can arise: (a) x ∈ I j or (b) x ∈ (N - j , N + j ) \ I j . In case (a) ϕ j (x) = Φ(x) and thus y = Φ(x) and (x, y) are in the same Φ-orbit. In case (b) there is another symmetry:

x ∈ (N - j , z j ) or x ∈ ( z ζ(j) , N + j ), we assume that x ∈ (N - j , z j ). By definition, the neutral point satisfies: N - j ∈ (ϕ ι(j) ( z δ(j) ), z j ) = L j , and Lemma 15 (c) implies:

N - j ∈ L j ⊂ I ζ -1 (j),γ(ζ -1 (j)),...,γ k(j)-2 (ζ -1 (j)) and, by symmetry N + j ∈ R j . The definition of these intervals implies:

∀u ∈ I ζ -1 (j),γ(ζ -1 (j)),...,γ k(j)-2 (ζ -1 (j)) : Φ i (u) ∈ I γ i (ζ -1 (j)) , ∀i ∈ {0, . . . , k(j) -2}, and thus condition (b) implies:

Φ i (x) ∈ I γ i (ζ -1 (j)) , ∀i ∈ {0, . . . , k(j) -2}. With the same argument we obtain: y = ϕ j (x) ∈ (N + ι(j) , ϕ j ( z j )) ⊂ R ι(j) with R ι(j) ⊂ I δ(j),...,δ k(j)-1 (j) , and thus: Φ i (y) ∈ I δ i+1 (j) , ∀i ∈ {0, . . . , k(j) -2}. The Φ orbits of x and y satisfy thus: Φ k(j)-1 (y) = ϕ δ k(j)-1 (j) • • • • • ϕ δ(j) (y), and Φ k(j)-1 (x) = ϕ γ k(j)-2 (ζ -1 (j))

• • • • • ϕ γ(ζ -1 (j)) • ϕ ζ -1 (j) (x). ( 29
)
Recall that each cutting point z j defines a relation R z j in the group G Φ , by Theorem 1:

ϕ δ k(j)-1 (j) • • • • • ϕ δ(j) • ϕ j = ϕ γ k(j)-1 (ζ -1 (j)) • • • • • ϕ γ(ζ -1 (j)) • ϕ ζ -1 (j)
. If the relation R z j is applied to the point x we obtain: Φ k(j)-1 (ϕ j (x)) = ϕ γ k(j)-1 (ζ -1 (j)) [ Φ k(j)-1 (x)].

(30) Indeed, by replacing y = ϕ j (x) in the left hand side of the relation we obtain the first equality in (29) which is the left hand side of (30). The right hand side of ( 30) is obtained by replacing, in the right hand side of the relation the second equality in (29). Let us denote: j 1 := γ k(j)-1 (ζ -1 (j)) ∈ {1, . . . , 2N }, x 1 := Φ k(j)-1 (x) and y 1 := ϕ j 1 (x 1 ). The equality (30) implies that an alternative, similar to (a) or (b) above, applies again, more precisely:

(a 1 ) x 1 ∈ I j 1 or (b 1 ) x 1 / ∈ I j 1 .

In case (a 1 ) the equality (30) gives:

Φ k(j)-1 (y) = Φ[ Φ k(j)-1 (x)] = Φ k(j) (x), and the orbit equivalence is proved in this case.

In case (b 1 ), by derivation, the equality (30) gives: d Φ k(j)-1 (ϕ j (x)) = d Φ k(j)-1 (ϕ j (x)).dϕ j (x) = dϕ j 1 ( Φ k(j)-1 (x)).d Φ k(j)-1 (x) (31)

Recall that Φ is affine of slope λ > 1, therefore equality (31) implies: λ d(ϕ j )(x) = d(ϕ j 1 ) (x 1 ) > 1. This means that the alternative (b1) is exactly the same at the point x 1 than (b) was at the point x. This implies, in particular that: x 1 ∈ I ζ -1 (j 1 ) and, more precisely:

x 1 ∈ I ζ -1 (j 1 ),γ(ζ -1 (j 1 )),...,γ k(j 1 )-2 (ζ -1 (j 1 )) and y 1 = ϕ j 1 (x 1 ) ∈ I δ(j 1 ),...,δ k(j 1 )-1 , by the same arguments as for the points x and y. The previous arguments thus defines:

• a sequence of integers: {j, j 1 , . . . , j n , . . . } where each j m ∈ {1, . . . , 2N }, • a sequence of points: x n := Φ k(j n-1 )-1 (x n-1 ) and y n := ϕ jn (x n ), with the following alternative:

(a n ) x n ∈ I jn or (b n ) x n / ∈ I jn .

Lemma 17. With the above notations, if x ∈ (N - j , z j ) is such that there is an integer n 0 so that x n 0 ∈ I jn 0 then y n 0 = ϕ jn 0 (x n 0 ) = Φ(x n 0 ) and there is an integer K(n 0 ) such that Φ K(n 0 ) (y) = Φ K(n 0 )+1 (x).

Proof. The situation is the alternative (a n 0 ), similar to the initial alternative (a), for the iterate K(n 0 ) = (k(j n 0 ) -1) + (k(j n 0 -1 ) -1) + • • • + (k(j) -1).

At this point we need to consider the precise definition of the generators ϕ j as obtained by Theorem 1. In particular, each ϕ j is affine of slope λ on the intervals I W j of (17) containing I j and obtained from the neighborhoods W p,q j of each cutting point z j given by ( 16). Recall that the "variation intervals": L W j and R W j are defined by ( 19) and that: N - j ∈ L W j and N + j ∈ R W j . The variation intervals satisfy Lemma 8, which is an equality among some variation intervals together with a "shift" property of the parameters (p, q). In the current argument, we assume in the case (b) that: x ∈ (N - j , z j ), in this interval there is another alternative: (b') x ∈ L W j ∩ (N - j , z j ) or (b") x ∈ W p,q j ∩ (N - j , z j ). Proposition 12. With the above notations, if x ∈ W p,q j ∩ (N - j , z j ) then there exists an integer n 0 (p, q) ≥ 1 so that x n 0 ∈ I jn 0 , which is the alternative (a n 0 ). Proof. Recall that the intervals W p,q j are defined inductively from V j of Lemma 6 and, in particular V j = W 0,0 j . We prove the Proposition by induction, starting with: x ∈ V j ∩ (N - j , z j ). From the definition of V j given in (6) we obtain:

x 1 = Φk(j)-1 (x) ∈ I γ k(j)-1 (ζ -1 (j)) = I j 1 .

)

  These three intervals, by definition, are contained in I p, * j and belong to the domain of definition of Φ p, * j . The image of W p,a j under Φ p, * j is contained in I δ(j) by Proposition 2-(a)

Figure 5 :

 5 Figure 5: The partition of Lemma 9.

  (mon)λ -1 ,λ (X; X ) and Diff (mon) λ,λ -1 (Y, Y ) in the proof of Theorem 1, for each cycle of the permutation δ giving the relations (CP). There are thus, a priori, many different groups in Definition 1.

Figure 6 :

 6 Figure 6: The first levels of the graph Γ 0 Φ

  For T Φ we use the same definitions for the intervals and vertices of Level 0, Level 1: a), b), Level 2: a), b) and Level k: a), b), c) in Γ 0 Φ , but considering the original semi-open intervals:

  (i) I w = I j 1 ,...,j k , (ii) I w = I j some integer n = n(k, Φ). The intervalsI j i 1 ,...,j i kbelong to the same level k and are pairewise adjacent along S 1 .

  (a) If m = j then: ϕ j (I j ) ∩ I k = ∅ for all k = ι(j). (b) For all m = j, ζ ±1 (j) then: ϕ j (I m ) = I ι(j),m . (c) ϕ j (I ζ(j) ) = I ι(j),ζ(j) ∪ L ι(j) and ϕ j

Figure 7 :

 7 Figure 7: Image of the intervals I m under ϕ j

where α satisfies (7), this interval is of type (ii-e). More generaly, from Definition 2 of the equivalence relation ∼ Φ , an interval of type (ii-v) is of the form: I ṽ ,j := I ,ζ -1 (j),γ(ζ -1 (j)),...,γ k(j)-1 (ζ -1 (j)) ∪ I ,j,δ(j),...,δ k(j)-1 (j) ,

where is a finite sequence (possibly empty) in {1, . . . , 2N }. The corresponding vertices are denoted: ṽj , ṽj,α and ṽ ,j .

The next result induces an additional structure of the graph Γ Φ around each vertex.

Proposition 4. If the map Φ satisfies the ruling conditions: (SE), (EC), (E+), (E-) then the set of edges that are incident to a vertex v ∈ V (Γ Φ ) admit a natural cyclic ordering induced by the cyclic ordering of the partition intervals I j along S 1 . In addition each vertex has valency 2N .

Proof. By definition of Γ Φ , the cyclic ordering of the intervals I j along S 1 defines a cyclic ordering of the vertices of level 1 and thus a cyclic ordering on the edges incident at v 0 . By Proposition 3 the structure of Γ Φ depends only on the combinatorics of the map Φ.

To simplify the arguments we assume that the identification of type (ii) are all 2 to 1, as in Lemma 13.

If v = v j 1 ,...,jt ∈ V (Γ Φ ) is a vertex of type (i) or (ii-e) and level t ≥ 1: Then it is connected to one vertex of level t -1, i.e. to v = v j 1 ,...,j t-1 , and to 2N -1 vertices of level t + 1, by condition (SE). At level t + 1, these vertices w i are ordered by the ordering of the sub-intervals I w i along the interval I v as sub-intervals of S 1 . Recall that the ordering along S 1 is expressed by the permutation ζ (see § 2.1). By condition (SE) these vertices at level t + 1 are: v j 1 ,...,jt,ζ(jt) , v j 1 ,...,jt,ζ 2 (jt) , . . . , v j 1 ,...,jt,ζ 2N -1 (jt) .

The edges arriving at these vertices, from v, are labelled respectively: Ψ ζ(jt) , . . . , Ψ ζ 2N -1 (jt) . The vertex at level t -1 is v j 1 ,...,j t-1 and the reverse edge, i.e from v to it, is labelled Ψ jt . Therefore, for the vertices of type (i) or (ii-e), there is indeed a cyclic ordering of the edges at the vertex v induced by the permutation ζ.

If v is a vertex of type (ii-v): Then, there is j ∈ {1, . . . , 2N } and a finite sequence in {1, . . . , 2N } so that v is identified with an interval I ṽ ,j as in (28). From the equivalence relation ∼ Φ , the vertex v has two incoming edges and they are adjacent by Lemma 3. These two edges are labelled, reading from v, as:

And there are 2N -2 out-going edges, ordered by the ordering along S 1 . By condition (7) in the proof of Lemma 6, they are labelled as:

) . In all cases, i.e. for the vertices of type (i), (ii-e) or (ii-v), 2N edges are incident at v and they are cyclically ordered by the permutation ζ and thus by the ordering of the intervals along S 1 .

Corollary 2. Each pair of consecutive edges for the natural cyclic ordering, at any vertex v, is associated to exactly one "cutting point" relation of Theorem 1.

Proof. By the proof of Theorem 1, each "cutting point" relation is associated to a cycle of the permutation δ or γ. From the proof of Lemma 15, a cycle of the permutation δ or γ is also associated to the iteration of Φ via conditions (E+), (E-). In term of the edges in Γ Φ , the cycle defines the following loop, given by the sequence of labeled edges:

, Ψ δ k(j)-1 (j) , . . . , Ψ δ(j) , Ψ j , for each j = 1, . . . , 2N . The two edges labeled Ψ ζ -1 (j) and Ψ j are adjacent by definition of ζ. Moreover, since the cycles of the permutations are disjoint, each pair of consecutive edges is associated to exactly one "cutting point" relation.

defined by the union of the loops associated to the pairs of adjacent edges in Corollary 2 (see Figure 8 for C v 0 ). The extreme points of the compact set C v 0 correspond to vertices of type (ii-v), the other vertices are of type (i) according to Lemma 12. In this part we study the action of each generator ϕ j on the set of intervals corresponding to the vertices of the compact set C v 0 . Lemma 15 is the first step and most of the arguments are exactly like in its proof. Observe that C v 0 is contained in the ball of Γ Φ : Ball(v 0 , K Φ ) where the radius K Φ = max{k(j) : j ∈ {1, . . . , 2N }} was defined in the proof of Lemma 14.

Proposition 5. With the above definitions and notations, the image under ϕ j of the intervals I v of type (i), associated to the vertices in C v 0 by Lemma 12, are given by the following cases:

1) If the cutting point z j is a boundary point of I v then, for 0 ≤ m ≤ k(j) -2:

(a) if I v = I j,δ(j),δ 2 (j),...,δ m (j) then ϕ j (I v ) ⊂ I δ(j),...,δ m (j) with ϕ j (I v ) ∩ I δ(j),...,δ m (j),α = ∅, for all possible such α ∈ {1, . . . , 2N },

, where R ι(j) satisfies the properties (c) in Lemma 15.

2

(a) if I v = I j,γ(j),δ 2 (j),...,γ m (j) then ϕ j (I v ) ⊂ I γ(j),...,γ m (j) with ϕ j (I v ) ∩ I γ(j),...,γ m (j),α = ∅, for all possible such α ∈ {1, . . . , 2N }, (b) if

, where L ι(j) satisfies the properties (c) in Lemma 15.

3) If I v is of type (i) and does not contain z j or z ζ(j) as a boundary point then it has the form:

1) If the cutting point z j belongs to the boundary of I v and v is a vertex of type (i) according to Lemma 12 then it is given by ( 26). Let us consider this set of intervals.

(a) If I v = I j,δ(j),δ 2 (j),...,δ m (j) .

For m = 1, the argument in the proof of Lemma 15-(a) implies: ϕ j (I j,δ(j) ) ⊂ I δ(j) and ϕ j (I j,δ(j) ) ∩ I δ(j),α = ∅ for all such possible α.

The same argument applies for all 1 ≤ m ≤ k(j) -2 and we obtain the statement (1-a) in this case.

, the arguments in the proof of Lemma 15-(c) apply and we obtain, for all 1 ≤ m ≤ k(j) -2:

2) If z j is replaced by z ζ(j) then δ(j) is replaced by γ(j), the condition (E+) is replaced by (E-) and the same arguments apply, by symmetry.

3) If the interval I v of type (i), level r > 1 and does not contain the cutting points z ζ(j) or z j then it has the form I j 1 ,...,jr with j 1 = j and if j 1 = ζ ±1 (j) then j 2 = γ(j) or δ(ζ -1 (j)). In these cases, the arguments in Lemma 15-(b) apply and ϕ j (I j 1 ,...,jr ) = I ι(j),j 1 ,...,jr .

For the next result we consider the intervals of type (ii) of Lemma 12. They are associated to the "extreme points" of the compact C v 0 (see Figure 8). At level k(j), around z j , they are given by the intervals I ṽj in (27). Proposition 6. With the above definitions and notations the image, under ϕ j , of the intervals I ṽm of type (ii) associated to the vertices in C v 0 are given by the following cases:

) and it intersects all sub intervals of level k(j) (resp. k(ζ(j)) ), except one. 2) ϕ j (I ṽl ) = I ι(j),ṽ l , with the notation (28) for l / ∈ {j, ζ(j)}.

Proof. 1) From the definition of the neighborhood V j in Lemma 6, we observe that the interval I ṽj of ( 27) satisfies :

The generators ϕ j given by Theorem 1, together with Lemma 7 gives:

From the construction of the neighborhood V j in Lemma 6 we obtain: Φ m (ϕ j (I ṽj )) ⊂ I δ m+1 (j) for all m = 0, . . . , k(j)-2, and thus : ϕ j (I ṽj ) ⊂ I δ(j),δ 2 (j),...,δ k(j)-1 (j) .

The goal of this subsection is to show that the map A g is well defined and can be extended to a map on the graph Γ Φ . In particular we need to check that the map A g does not depend on the expression, in the generators, of the element g.

The next subsection will be about proving that this map defines a geometric action. These are the main technical parts of the proof.

The definition of the map A g is new and not standard. As a warm up, let us check it is well defined for each generator ϕ j on the vertices of level 1. For this we compute ϕ j (I m ) for j and m ∈ {1, . . . , 2N }. Lemma 15 gives all the possibilities: • If m = j then, case (a) in Lemma 15 and case (1) of Definition 3 gives:

With case (4) of Definition 3, we obtain, for each generator ϕ j , that A ϕ j maps the ball of radius one centered at v 0 in Γ Φ , to the ball of radius one centered at v ι(j) .

Proposition 7. The map A ϕ j of Definition 3 is well defined for all the vertices in the compact set C v 0 for all j ∈ {1, . . . , 2N }.

Proof. We already checked that A ϕ j is well defined for the vertices of level ≤ 1. Let us verify this property for all the vertices in C v 0 .

1) If v is a vertex of type (i) in C v 0 , the image of the corresponding interval by ϕ j is given by Proposition 5. For these cases either v = v j 1 ,γ(j 1 ),...,γ n (j 1 ) or v = v j 1 ,δ(j 1 ),...,δ n (j 1 ) , for some j 1 and n ≤ k(j 1 ) -2.

(a) If j 1 = j, ζ ±1 (j), Proposition 5 case (3) gives: ϕ j (I j 1 ,j 2 ,...,jn ) = I ι(j),j 1 ,j 2 ,...,jn and by Definition 3 case (2): either A ϕ j (v) = v ι(j),j 1 ,γ(j 1 ),...,γ n (j 1 ) or A ϕ j (v) = v ι(j),j 1 ,δ(j 1 ),...,δ n (j 1 ) . (b) If j 1 = j, then Proposition 5 case (2-a) gives: ϕ j (I j,γ(j),...,γ n (j) ) ⊂ I γ(j),...,γ n (j) , (resp.

by case (1-a): ϕ j (I j,δ(j),...,δ n (j) ) ⊂ I δ(j),...,δ n (j) ). In addition ϕ j (I v ) intersects all subintervals of level n + 1. By Definition 3 case (2) we obtain:

, with R ι(j) ⊂ I δ(j),...,δ k(j)-1 (j) , and there are two different situations:

is an interval of level k(j) and R ι(j) is contained in an interval of level k(j)-1 and thus does not contain an interval of level k(j) -1. Recall that the interval of type (ii) containing the cutting point z δ(j) is given by ( 27):

. By Lemma 7 it satisfies: ϕ j (I ṽj ) ∩ I ṽδ(j) = ∅, which implies: R ι(j) ∩ I ṽδ(j) = I δ(j),...,δ k(j) (j) , these equalities together give:

Proposition 9. The map A ϕ j is well defined on the vertex set V (Γ Φ ). It extends to a well defined map on the set of edges as: A ϕ j (v, w) := (A ϕ j (v), A ϕ j (w)) and is a bijective isometry, for all j = 1, . . . , 2N.

Proof. Each map A ϕ j is well defined on C v 0 by Proposition 7. By Remark 5 and Proposition 8 the maps are well defined on V (Γ Φ ). It is enough to prove the result for the compact set C v 0 . Let (v, w) be an edge in C v 0 , we can assume v is v j 1 ,γ(j 1 ),...,γ n (j 1 ) , (resp. v = v j 1 ,δ(j 1 ),...,δ n (j 1 ) ), and w = v j 1 ,γ(j 1 ),...,γ n+1 (j 1 ) , (resp. w = v j 1 ,δ(j 1 ),...,δ n+1 (j 1 ) ), for some n ≤ k(j 1 ) -2. 1) If n < k(j 1 ) -2 then the two vertices are of type (i) and we compute the image of each vertex by Proposition 7, this gives the following cases: (a) If j 1 = j, then by Proposition 7 case (1-a) and (1-(c)-(i)), the image of each vertex gives:

(A ϕ j (v), A ϕ j (w)) is an edge in C v ι(j) . (b) If j 1 = j, then by Proposition 7, case (1-b), the image of each vertex gives:

2) If n = k(j 1 ) -2 then v is of type (i) and w of type (ii).

(a) If j 1 / ∈ {ζ ±1 (j), j} then, by Proposition 7, (1-a) for v and case (2-b) for w we obtain:

then by Proposition 7, case (1-b) for v and case (2-a) for w we obtain:

, then by Proposition 7 case (1-c-ii) the image of v is of type (ii) and by Proposition 7, case (2-a) the image of w is of type (i). In these cases, we obtain:

For all the edges in C v 0 , the map A ϕ j is well defined by A ϕ j (v, w) := (A ϕ j (v), A ϕ j (w)).

In particular no two edges are mapped to the same one. Therefore each A ϕ j is a bijective isometry, when restricted to C v 0 , for the combinatorial metric on Γ Φ . In addition, the map A ϕ j increases or decreases by one the level of both vertices. The proof for the other compact sets C v is the same and thus the map is well defined on Γ Φ .

Proposition 10. For every vertex v of Γ Φ , A ϕ j (C v ) = C Aϕ j (v) and A ϕ j preserves the natural cyclic ordering of the edges given by Proposition 4.

Proof. From the proof of Proposition 9 we obtain:

. This is the statement for v = v 0 . For the other vertices the proof is the same. The cyclic ordering of Proposition 4 for the edges in Γ Φ reflects the cyclic ordering of the intervals along the circle, it is given by the cyclic permutation ζ. Let us consider (v 0 , v k ) and (v 0 , v ζ(k) ) two consecutive edges around v 0 . By Proposition 9, the image under A ϕ j depends on the value of k.

), these two edges are consecutive at the vertex v ι(j) .

Proof. (1) The group acts geometrically on a discrete metric space by Lemma 16 so it is a discrete group. The graph Γ Φ and the action of Definition 3 does not depend on the particular generating set X Φ , they only depend on the map Φ.

(2) By Lemma 16 and Corollary 1 the group acts geometrically on a Gromov hyperbolic space with boundary S 1 . Therefore the group is Gromov hyperbolic with boundary S 1 by the Milnor-Swartz Lemma (see for instance §3 in [GdlH]).

(3) The group is a convergence group by a result of E. Freden [F]. Therefore the conditions of [G], [T] and [CJ] are satisfied and the group G Φ is virtually a surface group.

In order to complete the proof of the Theorem it suffices to check: Claim. The group G Φ is torsion free. Proof of the Claim. We already observed that each g ∈ G Φ has bounded expansion and contraction factors by Proposition 11. This implies, in particular, that the action A g is free. Indeed any vertex v = v 0 of Γ Φ is associated to an interval I v . We observe that for any g ∈ G Φ and any v, g(I v ) satisfies either:

In the last case g(I v ) intersects 2N-1 intervals of the same level than I v by Lemma 15. The Definition 3 of the action implies it is free. We also obtain, by this observation, that each element g ∈ G Φ is associated to an interval I v as above on which g is expanding. This expansion property implies that g n = id for all g ∈ G Φ and all n.

By [Zi] a virtual surface group which is torsion free is a surface group, this completes the proof.

Orbit equivalence

In this section we complete the proof of the main theorem: the group and the map are orbit equivalent. Let us recall the definition of orbit equivalence, as given in [BS].

Definition 4. A map Φ : S 1 → S 1 and a group G acting on S 1 are orbit equivalent if, except for a finite number of pairs of points (x, y)

The following result is the first statement of the main Theorem.

Theorem 3. If Φ : S 1 → S 1 is an orientation preserving piecewise homeomorphism satisfying the conditions (SE), (EC), (E±) and (CS), then the group G Φ of Theorem 1 and Φ are orbit equivalent.

Proof. The arguments in the proof use the piecewise affine map Φ conjugate to Φ by condition (CS) via some g ∈ Homeo(S 1 ). The orbit equivalence is preserved by conjugacy and the above statement is valid for the map Φ and the group obtained from G Φ by conjugacy via the same g. One direction of the orbit equivalence is direct from the definition of the map and the group. This is the alternative (a1) with n 0 = 1. For the induction step we assume: x ∈ (W p,q j \ W p-1,q-1 j ) ∩ (N - j , z j ). Recall that the proof of Lemma 8 used a "shift" argument for the indices: (p, q) → (p -1, q -1). The same arguments imply that if x ∈ W p,q j then:

x 1 = Φk(j)-1 (x) ∈ W p-1,q-1 j 1 , with j 1 = γ k(j)-1 (ζ -1 (j)). Thus after finitely many steps, depending on (p, q) we obtain: x m = Φk(j m-1 )-1 (x j m-1 ) ∈ W 0,0 jm = V jm and finally: x m+1 = Φk(jm)-1 (x jm ) ∈ I jm .

Back to the main argument, it remains to consider the situation where the alternative (b n ) occurs for all n ∈ N. This implies, by Lemma 17 and Proposition 12, that x satisfies the alternative (b'), i.e. x ∈ L W j ∩ (N - j , z j ). Lemma 18. Assume that x and x are two points in L W j ∩ (N - j , z j ) such that there is n 0 1 so that x n 0 satisfies (a n 0 ) and xn 0 satisfies (b n 0 ) but xn 0 +1 satisfies (a n 0 +1 ) then the following inequalities are satisfied:

Proof. By definition of ϕ j in Theorem 1 and x, x ∈ L W j then the derivative d(ϕ j ) is strictly increasing in L W j ∩ (N - j , z j ) between 1 and λ > 1. It remains to prove that: N - j < x < x < z j . From the hypothesis on x and x, we have:

x n 0 = Φ k(j n 0 -1 )-1 (x n 0 -1 ) ∈ I jn 0 by (a n 0 ), and

Therefore xn 0 < x n 0 since I ζ -1 (jn 0 ) occurs before I jn 0 along the cyclic ordering of S 1 and thus x < x since the map Φ is orientation preserving.

Lemma 19. If the point x ∈ [N - j , z j ] is such that the alternative (b n ) occurs for all n ∈ N then x is a neutral point, i.e. x = N - j .

Proof. A point x so that the alternative (b n ) is satisfied for all n is an accumulation point of the sequence x of Lemma 18 when n 0 goes to infinity. This sequence is decreasing by Lemma 18 and the derivative is strictly decreasing in [1, λ]. The only accumulation point of this sequence is when the derivative of ϕ j is 1 and thus x = N - j .

This completes the proof of Theorem 3 and thus of the main Theorem.

Appendix

In this Appendix we give a direct proof of:

Theorem. The group G Φ of Definition 1 is a surface group.

This result has been obtained in Theorem 2 of section 5, by using the very strong geometrisation theorem of Tukia [T], Gabai [G] and Casson-Jungreis [CJ]. The proofs of this geometrisation theorem, in one way or another, rely on extending the group action on the circle to an action on a disc. Our approach is not an exception to this general strategy. Here we already have an important ingredient: a geometric action given by Definition 3 on the hyperbolic metric graph Γ Φ of Definition 2. We need to prove that Γ Φ can be embedded in a plane and the action can be extended to a planar action. We define a 2-complex Γ

(2) Φ , in analogy with the Cayley 2-complex: • For each closed path in Γ Φ , associated to a cutting point relation R z j by Corollary 2 (see Figure 8), we define a two disc ∆ z j whose boundary is a polygone with 2.k(j) sides, where k(j) is given by condition (EC) at z j .

• We glue "isometrically" a disc ∆ z j along a closed path in Γ Φ , as above, associated to R z j . Isometrically means that each side of ∆ z j has length one and is glued along the corresponding edge in Γ Φ , also of length one. We denote by Γ

(2) Φ the 2-complex obtained by gluing all possible such discs. The graph Γ Φ is naturally the 1-skeleton of Γ

(2) Φ .

Lemma 20. The 2-complex Γ

(2) Φ is homeomorphic to R 2 . The action A g , g ∈ G Φ extends to a free, co-compact, properly discontinuous action A g of G Φ on Γ

(2) Φ .

Proof. By the Propositions 9 and 10, the action A g maps the link at a vertex v ∈ V (Γ Φ ) to the link at w = A g (v) and this action preserves the cyclic ordering of Proposition 4. This implies, in particular, that adjacent edges at v are mapped to adjacent edges at w. Recall that adjacent edges define a relation R z j by Corollary 2 for some j ∈ {1, . . . , 2N }. Therefore a closed path Π 0 , based at v in Γ Φ associated to a relation R z j is mapped to a closed path Π 0 , based at w, associated to R z j . We extend the action A g on Γ Φ to an action A g on Γ

(2) Φ by declaring that if A g (Π 0 ) = Π 0 then the disc ∆ z j based at v is mapped by A g to the disc ∆ z j based at w.

The set of 2-cells ∆ z j for all j ∈ {1, . . . , 2N }, glued along each pair of adjacent edges at v in Γ

(2) Φ , defines a neighborhood of v in Γ

(2)

Φ . This neighborhood is a 2-disc. Indeed, by the natural cyclic ordering of the edges at v, exactly two 2-cells are glued along an edge. Observe that the boundary of this neighborhood is a subset of the graph Γ Φ which is precisely the boundary of the compact set C v of Remark 4. This 2-disc is embedded in R 2 and this property is true for each vertex. Thus Γ

(2) Φ is homeomorphic to R 2 , since each point has a neighborhood homeomorphic to a 2-disc and Γ

(2) Φ is contractible since any basic loop in Γ Φ bounds a disc in Γ

(2) Φ . The extended action A g defined above is co-compact, free, and properly discontinuous, exactly as the action A g is on Γ Φ .

Proof of the Theorem. The quotient of Γ

(2) Φ by the action A g is a compact surface since Γ

(2) Φ is homeomorphic to R 2 and the action is co-compact and free.