S Ébastien

Pascal Hubert
email: hubert.pascal@gmail.com

RIGIDITY OF GENERALIZED VEECH 1969/SATAEV 1975 EXTENSIONS OF ROTATIONS

Keywords:

. We study the property of rigidity, in function of the Ostrowski expansions of the marked points by α: we prove that T is rigid when α has unbounded partial quotients, and that T is not rigid when the natural coding of the underlying rotation with marked points is linearly recurrent. But there remains an interesting grey zone between these two cases, in which we have only partial results on the rigidity question; they allow us to build the first examples of non linearly recurrent and non rigid interval exchange transformations.

. In the present paper, we study more general systems, by marking r points and taking d copies of the torus, for any r ≥ 1, d ≥ 2, and extending the rotation by the symmetric group S d .

.

In that paper, we focussed on the measure-theoretic property of rigidity, meaning that for some sequence q n the q n -th powers of the transformation converge to the identity (Definition 5 below). Experimentally, in the class of interval exchange transformations, the absence of rigidity is difficult to achieve (indeed, by Veech [16] it is true only for a set of measure zero of parameters) and all known examples satisfy also the word-combinatorial property of linear recurrence (Definition 3 below) for their natural coding. Indeed, for the systems studied in [5], we proved rigidity is equivalent to absence of linear recurrence, and thus to α having unbounded partial quotients. For the more general systems considered in the present paper, adaptations of the techniques of [5] do allow us to prove that T is rigid (for every invariant measure) and not linearly recurrent when α has unbounded partial quotients, and that T is uniquely ergodic, linearly recurrent, and not rigid when the natural coding of the underlying rotation with marked points is linearly recurrent (under an extra condition on the permutations, we prove also that T is not of rank one); this linear recurrence requires α to have bounded partial quotients and the marked points to satisfy some conditions on their Ostrowski expansions by α.

But, in sharp contrast with [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF], there is no similar equivalence in the present class of systems, and this leaves an interesting grey zone, when α has bounded partial quotients but the Ostrowski expansions of the marked points do not satisfy the conditions required for linear recurrence; this means that in the Rokhlin towers defined by the rotation (see Section 3.1 below) the marked points β i come too close either to one another or to the points 0, α, 1 -α. In these cases we prove some partial results, namely a sufficient condition (Theorem 15) for non-rigidity (for every ergodic invariant measure) and a sufficient condition (Theorem 17) for rigidity (for every invariant measure): the latter puts all the grey zone on the rigid side for Veech 1969, while, with two (or more) marked points, the former allows us to build the first known examples of non linearly recurrent and non rigid interval exchange transformations, answering Question 8 of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF]: Theorem 1. There exists a two-point extension of a rotation with two marked points which is a non linearly recurrent and non rigid interval exchange.

These conditions are enough to give a full characterization of rigidity for the simplest generalizations of Veech 1969, when we take two copies of the torus and a small number of marked points (for higher numbers of marked points, the question is not untractable but the results become extremely tedious to state). In general, the grey zone seems quite complicated, with many different cases using different techniques, and we seem to be far from a complete characterization of rigidity in our class.

1. DEFINITIONS 1.1. Word combinatorics. We begin with basic definitions. We look at finite words on a finite alphabet A = {1, ...k}. A word w 1 ...w s has length |w| = s (not to be confused with the length of a corresponding interval). The concatenation of two words w and w ′ is denoted by ww ′ . Definition 1. A word w = w 1 ...w s occurs at place i in a word v = v 1 ...v s ′ or an infinite sequence v = v 1 v 2 ... if w 1 = v i , ...w t = v i+s-1 . We say that w is a factor of v. A language L over A is a set of words such if w is in L, all its factors are in L, A language L is minimal if for each w in L there exists n such that w occurs in each word of L with n letters. The language L(u) of an infinite sequence u is the set of its finite factors. A word w is called right special, resp. left special if there are at least two different letters x such that wx, resp. xw, is in L. If w is both right special and left special, then w is called bispecial. 1.2. Symbolic dynamics and codings. Definition 2. The symbolic dynamical system associated to a language L is the one-sided shift S(x 0 x 1 x 2 ...) = x 1 x 2 ... on the subset X L of A N made with the infinite sequences such that for every s ′ < s, x s ′ ...x s is in L. For a word w = w 1 ...w s in L, the cylinder [w] is the set {x ∈ X L ; x 0 = w 1 , ...x s-1 = w s }. For a system (X, T ) and a finite partition Z = {Z 1 , . . . Z ρ } of X, the trajectory of a point x in X is the infinite sequence (x n ) n∈IN defined by

x n = i if T n x falls into Z i , 1 ≤ i ≤ ρ.
Then L(Z, T ) is the language made of all the finite factors of all the trajectories, and X L(Z,T ) is the coding of X by Z.

Note that the symbolic dynamical system (X L , S) is minimal (in the usual sense, every orbit is dense) if and only if the language L is minimal as in Definition 1. Definition 3. A language L or the symbolic system (X L , S) is linearly recurrent if there exists K such that in L, every word of length n occurs in every word of length Kn.

1.3. Boshernitzan's criteria for symbolic systems. Definition 4. For an invariant measure µ on (X L , S), let e n (S, µ) be the smallest positive measure of the cylinders of length n.

The following sufficient condition for unique ergodicity is known as Boshernitzan's criterion; it is defined, named, and its sufficiency is proved for codings of interval exchange transformations in [START_REF] Veech | Boshernitzan's criterion for unique ergodicity of an interval exchange transformation[END_REF], then this is extended to every symbolic dynamical system in [START_REF] Boshernitzan | A condition for unique ergodicity of minimal symbolic flows[END_REF]. Proposition 2. If (X L , S) is minimal, the system is uniquely ergodic if there exists an invariant measure such that lim sup n→+∞ ne n (S, µ) > 0.

The following result on linear recurrence is also due to M. Boshernitzan, but was written by T. Monteil in [START_REF] Ferenczi | Infinite words with uniform frequencies, and invariant measures[END_REF], Exercise 7.14. Proposition 3. If (X L , S) is minimal, the system is linearly recurrent if and only if there exists an invariant measure on (X L , S) such that lim inf n→+∞ ne n (S, µ) > 0.

1.4. Measure-theoretic properties. Let (X, T, µ) be a probability-preserving dynamical system. Definition 5. (X, T, µ) is rigid if there exists a sequence q n → ∞ such that for any measurable set A µ(T qn A∆A) → 0. Definition 6. In (X, T ), a Rokhlin tower is a collection of disjoint measurable sets called levels F , T F , . . . , T h-1 F . F is the basis of the tower. If X is equipped with a partition P such that each level T r F is contained in one atom P w(r) , the name of the tower is the word w(0) . . . w(h -1).

A symbolic system is generated by families of Rokhlin towers

F i,n , ..., T h i,n -1 F i,n , 1 ≤ i ≤ K, n ≥ 1, if each
level in each tower is contained in a single atom of the partition into cylinders {x 0 = i}, and for any word W in L(T ) there exist i and n such that W occurs in the name (for this partition) of the tower of basis F i,n . If a symbolic system is generated by families of Rokhlin towers, then, for any invariant measure, any measurable set can be approximated in measure by finite unions of levels of towers. Definition 7. (X, T, µ) is of rank one if there exists a sequence of Rokhlin towers such that the whole σ-algebra is generated by the partitions {F n , T F n , . . . , T hn-1 F n , X \ ∪ hn-1 j=0 T j F n }. 1.5. Rotations. The dynamical behavior of a rotation R of angle α on the 1-torus is linked with the Euclid continued fraction expansion of α. We assume the reader is familiar with the notation α = [0, a 1 , a 2 , ...]; we define in the classical way the convergents pn qn by p -1 = 1, q -1 = 0, p 0 = 0,

q 0 = 1, p n+1 = a n+1 p n + p n-1 , q n+1 = a n+1 q n + q n-1 . Let α n = |q n α -p n |. We recall Definition 8. α has bounded partial quotients if the a i are bounded.
Throughout the paper, except when we need more precision, we use C as a generic notation for constants.

VEECH AND SATAEV EXAMPLES

Definition 9. The Veech 1969 system is defined, if Rx = x+α modulo 1, by T (x, s) = (Rx, σ(x)s), s = 1, 2, where • σ(x) = σ 0 if x is in the interval [0, β[, σ 0 being the exchange E, 0 β 1 -α 1 1 1 + β 2 -α 2 1 1 1 2 1 3 2 1 2 2 2 3 0 α α + β 1 1 1 + α 1 + α + β 2 T 1 3 T 2 1 T 1 2 T 2 3 T 1 1 T 2 2 FIGURE 1. Veech 1969 • σ(x) = σ 1 if x is in the interval [β, 1[, σ 1 being the identity I.
This is defined (in a slightly different terminology) in the famous paper [START_REF] Veech | Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod 2[END_REF], where Veech considers also the variant where σ 0 = I, σ 1 = E. We can identify [0, 1[×{s} with [s -1, s[; then T is also an interval exchange transformation as in Figure 1 (note that six intervals appear in the picture, but two of them move together thus T is indeed a 5-interval exchange transformation).

We can generalize Veech 1969 naturally by marking several points β i , and taking more than two copies of the intervals: thus we take r + 1 different permutations on {1, ..., d}, changing permutation each time we cross a point β i : these transformations are defined by Sataev [START_REF] Sataev | The number of invariant measures for flows on orientable surfaces, (Russian)[END_REF] in 1975 for d = r + 1, clearly without knowledge of Veech's work. Then these systems appear in [START_REF] Stewart | Irregularities of uniform distribution[END_REF] for r = 1 and all d, and in [START_REF] Merrill | Cohomology of step functions under irrational rotations[END_REF] for all r and d, but only in the particular case of extensions by the commutative group Z/dZ, where all the permutations are circular; some of these systems are also considered in [START_REF] Guenais | PARREAU: Valeurs propres de transformations liées aux rotations irrationnelles et aux fonctions en escalier (eigenvalues of transformations arising from irrational rotations and step functions[END_REF].

In general the β i will be chosen to be rationally independent from α, but if there is only one β and it is equal to 1 -α, we get the square-tiled interval exchange transformations of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF] (though the geometrical model is not the same); thus, to generalize both [START_REF] Veech | Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod 2[END_REF][START_REF] Sataev | The number of invariant measures for flows on orientable surfaces, (Russian)[END_REF], and the square-tiled interval exchange transformations, we keep the possibility of choosing one of the β i to be 1 -α.

Throughout this paper we take α irrational, 0 < β 1 < .... < β r < 1 irrational, with possibly β t = 1 -α; more precisely, if the index t exists, then β t = 1 -α; otherwise β i = 1 -α for all i. We choose σ 0 , ..., σ r , permutations of {1, ..., d}. We always suppose σ j = σ j+1 , 0 ≤ j ≤ r -1, as otherwise we could delete some β i . We take all the β i , i = t, and all the β i -β j not in Z(α). We shall need sometimes another inequality, which generalizes the non-commutation condition used in [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF], and which we call the product inequality: namely, when β t = 1 -α we ask that σ r σ t-1 = σ 0 σ t , when β j = 1 -α for all j we ask that σ r = σ 0 .

Definition 10. The generalized Veech -Sataev system is defined, if Rx = x + α modulo 1, by T (x, s) = (Rx, σ(x)s), 1 ≤ s ≤ d, where • σ(x) = σ j if β j ≤ x < β j+1 , 1 ≤ j ≤ r -1, • σ(x) = σ 0 if 0 ≤ x < β 1 , • σ(x) = σ r if β r ≤ x < 1.
T can be seen also as an interval exchange transformation on at most d(r + 1) intervals, or with the following geometric model, generalizing the Masur-Smillie geometrical model for Veech 1969 In the other direction, the condition on the permutations ensures that the surface defined above is connected, and the flow is minimal as the conditions on the β i ensure there is no connection, except possibly (if β t = 1 -α) d connections between 1 -α and 0, each one staying inside one torus; these connections do not separate the surface into several parts.

0 β 1 β j β j+1 β r 1 σ 0 σ 1 σ j σ r FIGURE 2. Generalized Veech -

THE ROTATION WITH MARKED POINTS AND THE OSTROWSKI EXPANSION

3.1. Rokhlin towers. The rotation R can be coded either by the partition Z of the interval into [0, 1 -α[ and [1 -α, 1[, or by the partition Z ′ of the interval by the points β 1 , .., .β r . This gives two languages L and L ′ , and two symbolic systems. The first one is the natural coding of R: it is assimilated to R itself and denoted by (X, R). The second one is called the rotation with marked points and denoted by (X ′ , S).

It is well known, and written for example in [START_REF] Guenais | PARREAU: Valeurs propres de transformations liées aux rotations irrationnelles et aux fonctions en escalier (eigenvalues of transformations arising from irrational rotations and step functions[END_REF], that for the rotation R its natural coding is generated by two families of Rokhlin towers, made of intervals. We shall now describe precisely the towers at stage n, or n-towers.

At each stage n ≥ 1, there are one large tower made of q n intervals (or levels) of length α n-1 and one small tower made of q n-1 intervals (or levels) of length α n. . These are described in Figure 3 if n is odd, we make all our comments in that case; the case when n ≥ 2 is even can be deduced, mutatis mutandis, from Figure 4. Namely, the large tower is represented by the lower rectangle, and the small tower by the upper rectangle.The rotation R sends the basis [-α n-1 +α n +α, α n +α[ to an interval which we put just above it, and call a level of the large tower; this interval is sent by R just above, and so on until, by R qn-1 applied to the basis of the large tower, we reach the top of the large tower, [-α n-1 , 0[. Then the left part of this top,

[-α n-1 , -α n-1 + α n [ is sent by R onto he basis [-α n-1 + α, -α n-1 + α n + α[ of
the small tower, and we go up in the small tower until, by R q n-1 -1 applied to the basis of the small tower, we reach the top of the small tower, [0, α n [.

(0) (0) (1) (a n+1 -1) (a n+1 ) α 0 0 α n -α n-1 α -α n-1 α n α -α n-1 + α n -α n-1 + α n 0 -α n+1 α n + α 1 -α 1 -α FIGURE 3.
Rokhlin n-towers for the rotation, n odd Where we go next from [0, α n [ or [-α n-1 + α n , α n [ is shown at the bottom of the picture, one application of R goes to the point just above, in the basis of the large tower. For any x, R qn x is the point situated at distance α n to the left of x (extending the intervals if one of these points is not in the picture). Note that the three points 1 -α, 0 and α can be considered as very close together in the n-towers.

Each level of each tower is included in one atom of the partition Z. At the beginning, if α > 1 2 , the large 1-tower has one level, the interval [1 -α, 1[ and the small 1-tower has one level, the interval [0, 1 -α[, Figure 3 is still valid. If α < 1 2 , the 1-towers, which are still given by Figure 3, are more complicated, but we can define 0-towers: the large 0-tower has one level, the interval [0, 1 -α[ and he small 0-tower has one level, the interval [1 -α, 1[. The large tower is partitioned from left to right into a n+1 + 1 columns, of width α n except for the last one which is of width α n+1 , and except for α < 1 2 , n = 0, where there are only a 1 columns and thus Figure 4 does not apply. We denote the columns as in Figure 3 or 4, and include the whole small tower in column (0). The description of R defines immediately the next towers: to get the large n + 1-tower we stack the columns of the n-tower above each other, with the column

(0) (0) (1) (a n+1 -1) (a n+1 ) α 0 0 -α n α n-1 α n-1 + α -α n 0 α n+1 -α n + α 1 -α 1 -α FIGURE 4.
Rokhlin n-towers for the rotation, n even (a n+1 -1) at the bottom, then (a n+1 -2), ..., (0), and the small n-tower at the top, while the n-column (a n+1 ) becomes the small n + 1-tower.

Note that all levels are semi-open intervals, closed on the left, open on the right, and thus each column includes its left vertical side and not its right one.

The following lemma will be fundamental in our computations: we shall use it when α has bounded partial quotients, as it quantifies the linear recurrence of the natural coding of the rotation, but we can state and prove it in the general case. Lemma 5. Suppose x or y, or both, are in the basis of the large n-tower, and x = y + z, α n+1 ≤ z ≤ α n . Then the smallest k > 0 such that α lies between R k x and R k y, with α = R k x, is at least q n + q n-1 and at most q n+2 + q n+1 + q n . Proof y is at a distance z to the left of x; then for all m R m y is at the same distance of R m x on the circle. We make all computations with n odd, the even case is similar. To simplify notations, we write them for x and y which are not on the sides of any n-columns, thus excluding a countable set. However, we notice they are still valid on this countable set, because of our conventions that the columns are closed on the left, open on the right and we allow α = R k y when saying α appears between the two orbits.

• (i) Suppose first x is in the basis of the large n-tower and not y. Then x is at a distance at most α n from the left of the large tower, thus in column (0); y is to the left of the large tower and at less than α n from it, thus between -α n-1 + α and -α n-1 + α n + α, thus in the basis of the small tower (see Figure 9 below). y is at a distance d 1 from the left of this basis, x is at a distance 0 < d 2 < z from the left of the large tower, with d 1 + z = d 2 + α n . We make q n + q n-1 iterations of R. The orbit of x goes up through the large and small towers, and at the q n + q n-1 -th iteration hits the basis of the large tower, at a point situated d 2 to the right of α, The orbit of y goes up through the small tower, at the q n-1 -th iteration hits the basis of the large tower at a point situated d 1 to the right of α, then at the q n + q n-1 -th iteration hits this basis again, α n left of the previous hit, thus left of α as d 1 -α n = d 2 -z < 0; and before the q n + q n-1 -th iteration α does not appear between the two orbits. • (ii) Suppose x and y are in the basis of the large tower and in two different columns. Then these columns must be adjacent, and, after at most a n+1 q n iterations of R, during which α does not appear between the two orbits, we are in the situation of case (i). • (iii) Suppose x and y are in the basis of the large tower and in the same column. This column cannot be column (a n+1 ), and x is at distance d 3 from the right of its column. After at most a n+1 q n + q n-1 = q n+1 iterations of R, during which α does not appear between the two orbits, the orbit of x hits the basis of the large tower, at a point situated d 3 from its right end, and y also, at distance d 3 + z from the right. At this moment, if d 3 < α n+1 , then the orbit of x is in column (a n+1 ) and the orbit of y is in column (a n+1 -1) and we are in the situation of case (ii). If d 3 > α n+1 , the orbits of x and y are in column (a n+1 -1), and we are again in case (iii), but with d 3 replaced by d 3 -α n+1 . As d 3 < α n and α n = a n+2 α n+1 + α n+2 , after at most a n+2 such laps, during which α does not appear between the two orbits, we are in the situation of case (ii). • (iv) Suppose finally y is in the basis of the large n-tower and not x. Then x is to the right of the large tower and at less than α n from it, and y is to the right of α; after q n iterations of R, during which α does not appear between the two orbits, we are in the situation of case (ii) or (iii). Thus, by taking case (i) for the minimum, and summing our estimates for the maximum, we get the required result. Corollary 6. Let β and β ′ be any two points on the circle. Suppose x = y + z, α n+1 ≤ z ≤ α n , and β lies between x and y, with

β = x. Then the smallest k > 0 such that β ′ lies between R k x and R k y, with β ′ = R k x, is at most q n+2 + q n+1 + q n .
Proof By Lemma 5 this is true for β ′ = α and any β, just because β is in one of the n-towers and is the image of some point in the basis of the large one. As R commmutes with every translation, this is true also for any β and β ′ .

Ostrowski expansion.

We now put the points β i , i = t, in the picture. By partitioning the two towers for R as in Figure 5 (for odd n), we get r + 2 towers generating the rotation with

α β 1 β 2 β 3 β 4 β 5 β 6 0 0 FIGURE 5.
Rokhlin n-towers for the rotation with marked points marked points S, for which each level of each tower is included in one atom of the partition Z ′ (if β t = 1 -α, only r + 1 towers are needed as 1 -α is on the side of one tower).

For each 1 ≤ i ≤ r, i = t, and n ≥ 1 we define b n+1 (β i ) as an integer between 0 and a n+1 .

Definition 11. b n+1 (β i ) is b = 0 if β i is in column (b)
of the large n-tower (for R), and 0 if β i is either in column (0) of the large n-tower or in the small n-tower.

For odd n (resp. even n ≥ 2) let x n (β i ) be the (positive) distance of β i to the left (resp. right) side of the large and small n-towers in Figure 5 (resp. 6).

Proposition 7.

For each i = t, the b n (β i ) are given by a form of alternating Ostrowski expansion of β i by α, where the Markovian condition is b n

(β i ) = a n implies b n+1 (β i ) = 0. For i = t, β i is in Z(α) if and only if either b n (β i ) = a n -1 for all n large enough, or b 2n (β i ) = a 2n for all n large enough, or b 2n+1 (β i ) = a 2n+1 for all n large enough. For i = t, j = t, β i -β j is in Z(α) if and only if b n (β i ) = b n (β j ) for all n large enough. Proof We fix an i = t. Then b n+1 (β i ) = x n (β i ) α n . Now, x n+1 (β i ) is the distance of β i to the right (resp. left) side of its n-column if n is odd (resp. even). Thus we get x n (β i ) = b n+1 (β i )α n + α n -x n+1 (β i ) if β i is not in column (a n+1 ), x n (β i ) = b n+1 (β i )α n + α n-1 -x n+1 (β i ) if β i is in column a n+1 . Note that if β i is in column (a n+1
) in the large n-tower, then it is in the small n + 1-tower. Thus b n+1 (β i ) = a n+1 implies b n+2 (β i ) = 0, and this is the only Markovian condition they have to satisfy. Thus when

x n (β i ) = b n+1 (β i )α n + α n-1 -x n+1 (β i ), then x n+1 (β i ) = α n+1 -x n+2 (β i ) and x n (β i ) = a n+1 α n -x n+2 (β i ).
Together with the formula when b n+1 (β i ) < a n+1 , this gives an expansion

x 1 (β i ) = n≥1 (-1) n+1 bn+1 α n with bn = b n (β i ) + 1 if b n (β i ) < a n , bn = b n if b n (β i ) = a n .
Thus the bn satisfy he Markovian condition bn-1 = a n-1 if bn = 0.

Thus we identify the bn with the alternating Ostrowski expansion of x 1 (β i ) by α defined in [START_REF] Arnoux | Trajectories of rotations[END_REF].

If α > 1 2 , x 1 (β i ) is either β i or β i + α -1; if α < 1 2 , using the 0-towers, we can define 0 ≤ b 1 (β i ) ≤ a 1 -1 and x 0 (β i ) in the usual way, so that x 1 (β i ) = -x 0 (β i )+((b 1 (β i )+1)α)∧(1-α), and x 0 (β i ) is either 1 -β i or 1 -α -β i .
In both cases, we get an expansion of β i by α, which is

β i = n≥0 (-1) n+1
bn+1 α n with a suitable b1 , thus our b n (β i ) do provide a form of alternating Ostrowski expansion of β i by α.

The last conditions come from the fact that if β i = R k α for k > 0 then β i is in the same column as α, namely column a n -1, in the n -1-towers for all n large enough, while if β i = R k α for k < 0 then β i is in the same column as 0, and this alternates between 0 (in the small tower) and a n , and in both cases the converse is true by construction of the towers, as the vertical distance from β i to α (resp. 0) in the n -1-towers is ultimately constant while the horizontal distance tends to zero with n. Similarly, β i = R k β j if and only if in the n -1-towers β i is in the same column as β j for all n large enough.

As a consequence, we can build β i with any prescribed sequence 0 ≤ b n (β i ) ≤ a n satisfying the Markovian condition.

Linear recurrence.

To prove the next theorem, we need some new notations.

Definition 12. For a given n, each β i , i = t, appears in a single position in the n-towers as in Figure 6; it is determined by x n (β i ), from Definition 11. We shall use also

• y n (β i ) = y if β i = R y β ′ i where β ′ i is in the basis of the large n-tower, • x ′ n (β i ) = α n-1 -x n (β i ), • x n (β i , β j ) = x n (β j , β i ) = |x n (β i ) -x n (β j )|, • x n (β i , α) = x n (α, β i ) = |x ′ n (β i ) -α|., • y ′ n (β i ) = q n -y n (β i ) if β i is in the large n-tower, y ′ n (β i ) = q n + q n-1 -y n (β i ) if β i is in the small n-tower, • when β i is in the small tower, y ′′ n (β i ) = y n (β i ) -q n , • y n (β i , β j ) = y n (β j , β i ) = |y n (β i ) -y n (β j )|.
It is worth mentioning that β i and β j are close to each other in the n-towers vertically either if y n (β i , β j ) is small or if y n (β i ) + y ′ n (β j ) is small, and β i and β j are close to each other in the n-towers horizontally either if

x n (β i , β j ) is small or if x n (β i ) + x ′ n (β j
) is small. Though this will not be mentioned explicitly, each time we claim β i and β j are far from each other in one of these senses, this means that we have checked both conditions. Theorem 8. The symbolic system (X ′ , S) is linearly recurrent if and only all the following conditions are satisfied

• α has bounded partial quotients,

α β 2 β 1 0 0 y n (β 2 ) y ′ n (β 1 )
y n (β 2 )

y n (β 1 , β 2 ) x n (β 1 , β 2 ) x n (β 1 ) x ′ n (β 2 ) FIGURE 6.
Positioning the β i in the n-towers

• for each i = t, the number of consecutive n such that b n (β i ) = a n -1 is bounded,
• for each i = t, the number of consecutive n such that b 2n (β i ) = a 2n and the number of consecutive n such that b 2n+1 (β i ) = a 2n+1 are bounded,

• for each i = t, j = t with j = i, the number of consecutive n such that b n (β j ) = b n (β i ) is bounded.
Proof We suppose first our conditions are not satisfied.

If α has unbounded partial quotients, there exists n such that q n α n is arbitrarily small. In the large n-tower, with α in the basis and 1 -α just below 0, we see a cylinder, for the natural coding, of length q n -1 and Lebesgue measure α n ; this is a union of cylinders for the coding with marked points, of the same length and of smaller measure. As the Lebesgue measure is the only invariant measure by R, this contradicts linear recurrence by Proposition 3.

If b n+1 (β i ) = a n+1 -1, then by construction of the towers x n+1 (β i , α) = x n (β i , α) and y n+1 (β i ) = y n (β i ). If this holds for all M ≤ n ≤ M +N, then x M (β i , α) = x M +N (β i , α) ≤ α M +N and y M +N (β i ) = y M (β i ) ≤ q M .
Thus, for example, in the large M + N-tower we see a cylinder (for the coding with marked points) of measure x M +N (β i , α) and length y M +N (β i ). The product of these quantities is at most q M α M +N ≤ θ -N q M +N α M +N ≤ θ -N C, where θ is the golden ratio. Thus, if N is allowed to be arbitrarily large, this contradicts linear recurrence by Proposition 3.

If b n+1 (β i ) = a n+1 , then β i is in the small n + 1-tower, with x ′ n+1 (β i ) = x n (β i ) and y ′ n+1 (β i ) = y ′ n (β i ), and then x ′ n+1 (β i ) = x n+2 (β i ) and y ′ n+1 (β i ) = y ′ n+2 (β i ). If this holds for all M ≤ n ≤ M + 2N, y ′ M +2N (β i ) = y ′ M (β i ) ≤ q M .
In the large M + 2N-tower we see a cylinder of measure

x M +2N (β i ) ≤ α M +2N and length y ′ M +2N (β i ).
If N is allowed to be arbitrarily large, we conclude as in the previous case.

If b n+1 (β i ) = b n+1 (β j ), then x n+1 (β i , β j ) = x n (β i , β j ) and y n+1 (β i , β j ) = y n (β i , β j ). If this holds for all M ≤ n ≤ M + N, then y M +N (β i , β j ) = y M (β i , β j ) ≤ q M . In the M + N-towers we see a cylinder of measure x M +N (β i , β j ) ≤ α M +N and length y M +N (β i , β j ). If N is allowed to be arbitrarily large, we conclude as in the previous cases.

We suppose now all our conditions are satisfied. In particular, α has bounded partial quotients.

If b n+1 (β i ) = a n+1 -1, then x n (β i , α) ≥ α n+2 . Otherwise, x n (β i , α) = x m (β i , α)
for the first m > n for which b m+1 (β i ) = a m+1 -1, and we know m ≤ n + K. Thus we get that for all n,

x n (β i , α) ≥ α n+K+2 ≥ Cα n . If b n (β i ) = a n -1, then by construction of the towers y n (β i ) ≥ q n-1 . Otherwise, y n (β i ) = y m (β i )
for the last m < n for which b m (β i ) = a m -1, and we know m ≤ n -K. Thus we get that for all n, y n (

β i ) ≥ q n-K-1 ≥ Cq n . If b n-1 (β i ) = a n-1 -1, by construction of the towers the result y n-1 (β i ) ≥ Cq n-1 implies, when y ′′ n (β i ) is defined, that y ′′ n (β i ) ≥ Cq n . If b n+1 (β i ) = a n+1 , then x ′ n (β i ) ≥ α n+1 . Otherwise, x ′ n (β i ) = x ′ m (β i )
for the first m > n such that m -n is even and b m+1 (β i ) = a m+1 , and we know m ≤ n + K. Thus we get that for all n,

x ′ n (β i ) ≥ α n+K+1 ≥ Cα n . If b n+2 (β i ) = a n+2 , then x ′ n+1 (β i ) ≥ α n+2
and by construction of the towers x n ≥ α n+2 (β i being far from one side of the n + 1-towers, is far from the opposite side of the n-towers). Otherwise,

x ′ n+1 (β i ) = x ′ m+1 (β i )
for the first m > n such that m -n is even and b m+2 (β i ) = a m+2 , and we know m ≤ n + K. Thus we get that for all n,

x n (β i ) ≥ α n+K+2 ≥ Cα n . If b n-1 (β i ) = a n-1
, then β i is not in the small n -1-tower, thus far from the top in the n-towers: we have y ′ n ≥ q n-1 . Otherwise, y n (β i ) = y m (β i ) for the last m < n such that n -m is even and b m-1 (β i ) = a m-1 , and we know m ≤ n -K. Thus we get that for all n,

y ′ n (β i ) ≥ q n-K-1 ≥ Cq n . If b n+1 (β i ) = b n+1 (β j )
, then β i and β j are not in the same column in the n-towers. Because of the previous results on x n and x ′ n , each of them is at a distance greater than Cα n from the sides of their column, thus

x n (β i , β j ) ≥ Cα n . Otherwise, x n (β i , β j ) = x m (β i , β j ) for the first m > n for which b m+1 (β i ) = b m+1 (β j
), and we know m ≤ n + K. Thus for all n,

x n (β i ) ≥ Cα n+K ≥ Cα n . If b n (β i ) = b n (β j )
, then by construction of the towers y n (β i , β j )) ≥ q n-1 . Otherwise, y n (β i ; β j ) = y m (β i , β j ) for the last m < n for which b m (β i ) = b m (β j ), and we know m ≤ n -K. Thus we get that for all n, y n (β i , β j ) ≥ q n-K-1 ≥ Cq n .

A cylinder H of length h (for the coding with marked points) is an interval [y, x[ for which each iterate by R -m , 1 ≤ m ≤ h -1, is in a single atom of Z ′ . For a given measure µ(H) = x -y, the minimal value of h is reached when either x and R -h+1 y, or y and R -h+1 x, are endpoints of atoms of Z ′ (otherwise the interval [y, x[ could be extended to the left or to the right). We take n such that µ(H) is smaller than α n ; then as in the proof of Lemma 5 we see H in the n-towers or less than α n from the right or left of Figure 7. Then the above computations imply that h is at least Cq n and µ(H) at least Cα n . Hence we get the linear recurrence from Proposition 3.

The following lemma will be used later.

Proof

This is proved by looking in the towers for S, using the fact that, by the proof of Theorem 8, all y n (β i ), y ′ n (β i ), y ′′ n (β i ) and y n (β i , β j ) are at least Cq n . Then W corresponds to a set of trajectories which coincides on |W | consecutive symbols, but some (in particular, the leftmost and rightmost ones) are different on the letter before and the letter after. If all these trajectories are at a distance between α n+1 and α n for some n ≥ 2, then W can be seen in the n-towers.

As W is right special, it must end just before we see either a β i , i = t, or 1 -α between the leftmost and rightmost trajectories in W (as in Lemma 5 the rightmost one is allowed to hit the considered β i or 1 -α but not the leftmost). In the first case, these two trajectories disagree on the level containing β i ; in the second case, the two trajectories disagree left and right of 1 -α, and on the next letter as they are left and right of 0; in both cases, then they agree again until we see again 1 -α or some β j between the leftmost and rightmost trajectories in W , thus for a length at least Cq n . As W is left special, it begins just after we see either a β i , i = t, or 0 between the leftmost and rightmost trajectories in W , thus by Corollary 6 its length is at most q n + q n+1 + q n+2 ≤ C ′ q n , and thus the claimed property is proved.

RIGIDITY FOR GENERALIZED VEECH -SATAEV

4.1. The natural coding of T . We look now at the natural coding of T , namely its coding by the partition into the d(r + 1) intervals used In Definition 10 (though they are not necessarily the intervals of continuity of T , see Figure 1 above), and we call it (Y, T ). We denote by s i the i-th interval in the s-th copy of [0, 1[. A trajectory x of T under this natural coding projects on a trajectory φ(x) of the rotation with marked points (X ′ , S), by applying the map φ(s i ) = i letter to letter. Because all the σ i are bijective, and their compositions also, as in Lemma 5 of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF] for any word w in L(T ), there are exactly d words v such that φ(w) = φ(v), and for each of these words either v = w or on the letters v i = w i for all i.

As (X ′ , S) is generated by the r + 2 towers in Figure 5,(Y,T ) is generated by d(r + 2) Rokhlin towers. More precisely, by construction of the towers, for all n, the trajectories of the natural coding of R are covered by disjoint occurrences of M n and P n , the names of the large and small n-towers. The trajectories of the coding with marked points S are covered by the names of the towers in Figure 5: these are denoted by P n,i , 1 ≤ i ≤ r 1 < r + 2, and M n,j , r 1 + 1 ≤ j ≤ r + 2, r 1 depending on n (we number them from right to left if n is odd, from left to right otherwise). The trajectories of T are covered by d(r + 2) words P n,i,j and M n,i,j , 1 ≤ j ≤ d which are all the words which project on on P n,i and M n,i by φ.

Proposition 10. If the minimality condition of Proposition 4 is satisfied, (Y, T ) is linearly recurrent if and only if (X ′ , S) is linearly recurrent. In this case, (Y, T ) is uniquely ergodic.

Proof Let [w] be a cylinder for (Y, T ): for the Lebesgue measure µ on both sets we have µ[w] = 1 d µ[φw], and, for any invariant measure ν on (Y, T ), on (X ′ , S) ν projects on µ, the unique invariant measure, thus µ

[φw] = φv=φw ν[v] ≥ ν[w].
Hence, under the assumption of minimality, the result on linear recurrence in both directions comes from Proposition 3, while unique ergodicity comes from Proposition 2.

The non-exotic cases.

We use now all the preliminary work to derive results generalizing those in [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF]. We do consider these generalizations as non-trivial but do not claim them to be unexpected.

Proposition 11. If α has unbounded partial quotients, (Y, T ) is rigid for any invariant measure.

Proof

In trajectories of R, by construction of the towers we have

P n+1 = P a n+1 n M n , M n+1 = P n for all n. Thus P n+2 = (P a n+1 n M n ) a n+2 P n , M n+2 = P n+1 = P a n+1 n M n .
As M n is shorter than P n disjoint occurrences of the word P a n+1 n fill a proportion at least 1 -2 a n+1 +1 of the length of both M n+2 and P n+2 .

In trajectories of S, the construction of the towers and the above remark imply that a proportion at least 1 -2 a n+1 +1 of the length of all M n+2,j and P n+2,j is covered by concatenations of the type P n,j 1 ...P n,ja n+1 of length q n a n+1 . Moreover, all these concatenation contain, at the same place, cycles of the form P c n,j n,i j , where the c n,j , 1 ≤ j ≤ r 2 ≤ r + 1 (r 2 depending on n) are the successive numbers of n-columns containing no β l , between two column containing at least one β l or between the sides of the towers and a column containing at least one β l (here column (0) is replaced by its intersection with the large tower). Thus r 2 j=1 c n,j ≥ a n+1 -r. In trajectories of T , we look at the words which project by φ on cycles P c n,i . n and i being fixed, each P n,i,j can be followed by exactly one P n,i,j , and thus the P n,i,j , 1 ≤ j ≤ d, are grouped into at most d disjoint strings, each one containing at most d words P n,i,j . After the last P n,i,j of each string, the only P n,i,j ′ we can see is the first one of the same string. Then, if we move by T d!qn inside one of the words which project on the cycle P c n,j n,i j , we go to the same level in the same tower of name P n,i,j , except if we are in the last d! words projecting on this cycle. In each concatenation P n,j 1 ...P n,ja n+1 mentioned above, these "good" words represent r 2 j=0 (c n,j -d!)∨0 ≥ a n+1 -r -(r + 1)d! of the words in L(T ) projecting on that concatenation, and thus a proportion at least 0 ∨ (1 -2rd! a n+1 ) of the length of all M n+2,i,j and P n+2,i,j . All the levels of the same n-tower have the same measure by a given invariant µ, thus if E is a union of levels of the towers of name P n,i,j , we have µ(E∆T d!qn E) ≤ 2rd a n+1 . Now for every set E and n large enough, E can be δ n -approximated (for the invariant measure µ) by unions of levels of the towers of name P n,i,j or M n,i,j ; but the towers of name M n,i,j have total measure at most 2 a n+1 since they represent a smaller fraction of the length of all M n+2,i,j and P n+2,i,j . Thus

µ(E∆T d!qn E) ≤ 2rd+4 a n+1 + δ n .
Hence if the a n are unbounded T is rigid.

The notion of average d-separation is defined in [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF], where comments and explanations on this and related notions can be found.

Definition 13. For two words of equal length w

= w 1 . . . w N and w ′ = w ′ 1 . . . w ′ N , their Hamming or d-distance is d(w, w ′ ) = 1 N #{i; w i = w ′ i }.
A language L on an alphabet A is average dseparated for an integer e ≥ 1 if there exists a language L ′ on an alphabet A ′ , a K to one (for some K ≥ e) map φ from A to A ′ , extended by concatenation to a map φ from L to L ′ , such that for any word w in L, there are exactly K words v such that φ(w) = φ(v), and for each of these words either v = w or d(w, v) = 1, and a constant C, such that if v i and v ′ i , 1 ≤ i ≤ e, are words in L, of equal length N, satisfying

• e i=1 d(v i , v ′ i ) < C, • φ(v i ) is the same word u for all i, • φ(v ′ i ) is the same word u ′ for all i, • v i = v j for i = j.
Then {1, . . . N} is the disjoint union of three (possibly empty) integer intervals I 1 , J 1 , I 2 (in increasing order) such that

• v i,J 1 = v ′ i,J 1 for all i, • e i=1 d(v i,I 1 , v ′ i,I 1 ) ≥ 1 if I 1 is nonempty, • e i=1 d(v i,I 2 , v ′ i,I 2 ) ≥ 1 if I 2 is
nonempty, where w i,H denotes the word made with the h-th letters of the word w i for all h in H.

This implies in particular that

#J 1 ≥ N(1 -e i=1 d(v i , v ′ i )). We call d-separation the average d-separation with K = e = 1, L = L ′ , φ the identity.
The proof of next proposition will follow step by step the proof of Proposition 44 of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF]. The main difference is that in [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF] L(T ) projects by φ on L(R), while here it projects on the more complicated L(S). Hence Lemma 9 above will replace Lemma 42 of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF].

Proposition 12. If the product inequality before Definition 10 and the minimality condition of Proposition 4 are satisfied, and the rotation with marked points (X ′ , S) is linearly recurrent, L(T ) is average d-separated with e = d.

Proof

We take L ′ = L(S), K = d. Let v i and v ′ i be as in Definition 13.

We compare first u and u ′ ; note that if we see l in some word φ(z) we see some s l at the same place on z;

thus d(z, z ′ ) ≥ d(φ(z), φ(z ′ )) for all z, z ′ ; in particular, if d(u, u ′ ) = 1, then d(v i , v ′ i ) = 1
for all i and our assertion is proved. Thus we can assume d(u, u ′ ) < 1. We partition {1, . . . N} into successive integer intervals where u and u ′ agree or disagree: we get intervals I 1 , J 1 , . . . , I g , J g , I g+1 , where g is at least 1, the intervals are nonempty except possibly for I 1 or I g+1 , or both, and for all j, u J j = u ′ J j , and, except if I j is empty, u I j and u ′ I j are completely different, i.e. their distance d is one. Then for i ≤ g -1, the word u J i = u ′ J i is right special in the language L(S), and this word is left special if i ≥ 2.

(H0) We suppose first that u J 1 = u ′ J 1 is also left special and u Jg = u ′ Jg is also right special.

Then, by Lemma 9, either #J j is smaller than a fixed m 1 , or 1 ≤ #I j+1 ≤ 2 and

#I j+1 + #J j+1 > C#J j ,
Similar considerations for S -1 imply that for j > 1 either #J j < m 1 , or 1 ≤ #I j ≤ 2 and #J j-1 + #I j > C#J j .

We look now at the words v i and v ′ i for some i; by the remark above, v i,I j and v ′ i,I j are completely different if I j is nonempty. As for v i,J j and v ′ i,J j , they have the same image by φ, thus are equal if they begin by the same letter, completely different otherwise.

Moreover, suppose that J j has length at least m 1 , and v i,J j = v ′ i,J j = Y (i), projecting on a right special word Y in L(S) ending with the letter j; then Y (i) ends with the letter s(i) j . Bispecial words in L(S) are described in the proof of Lemma 9; if Y ends just before we see a β i , i = t, after Y in L(S) we see the letters j 1 or j 2 , these denoting the two adjacent intervals around β i , then the same j 3 . Thus after Y (i) in L(T ) we see the letters (σs(i)) j 1 or (σs(i)) j 2 for some σ, then the letters (σ j 4 σs(i)) j 3 or (σ j 5 σs(i)) j 3 , these two permutations denoting the σ(x) on the two mentioned intervals. If Y ends just before we see 1 -α, after Y in L(S) we see the letters j 6 or j 7 , these denoting the two adjacent intervals around 1 -α, then the letters r or 0, denoting the two adjacent intervals around 0, then the same j 8 . Thus after Y (j) in L(T ), if β t = 1 -α we see the letters (σs(i)) j 6 and (σs(i)) j 7 for some σ, then the letters (σ t-1 σs(i)) 0 and (σ t σs(i)) r , then the letters (σ 0 σ t-1 σs(i)) j 8 and (σ r σ t σs(i)) j 8 ; if β j = 1 -α for all j, we see the letters (σs(i)) j 6 and (σs(i)) j 7 for some σ, then the letters (σ ′ σs(i)) 0 and (σ ′ σs(i)) r , for some σ ′ , then the letters (σ 0 σ ′ σs(i)) j 8 and (σ r σ ′ σs(i)) j 8 . In both cases, this gives us the first letters of the two words v i,J j+1 and v ′ i,J j+1 .

We estimate c = d i=1 d(v i , v ′ i ), by looking at the indices in some set G j = J j ∪ I j+1 ∪ J j+1 , for any 1 ≤ j ≤ g -1;

• if both #J j and #J j+1 are smaller than m 1 the contribution of G j to the sum c is at least 1 2m 1 +1 as I j+1 is nonempty by construction;

• if #J j ≥ m 1 , and for at least one i v i,J j and v ′ i,J j are completely different, then the contribution of G j to c is bigger than min

( 1 2 , C 1 C 1 +1 ) as either #J j+1 < m 1 or #J j + #I j+1 > C 1 #J j+1 ; • if #J j ≥ m 1 and for all i, v i,J j = v ′ i,J j = Y (i)
; then, because the v i are all different and project by φ on the same word, the s(i) in the last letter of Y (i) takes d different values when i varies; the hypotheses imply that, in the notations of the previous paragraph σ j 4 σs(i) = σ j 5 σs(i) for at least one i, and σ 0 σ t-1 σs(i)) = σ r σ t σs(i), resp. σ 0 σ ′ σs(i)) = σ r σ ′ σs(i), for at least one i. This ensures that for this i, v i,J j+1 and v ′ i,J j+1 are completely different. As #J j+1 + #I j+1 > C 1 #J j , the contribution of G j to c is bigger than C; • if #J j+1 ≥ m 1 , we imitate the last two items by looking in the other direction. Now, if g is even, we can cover {1, . . . Q} by sets G j and some intermediate i l , and get that c is at least a constant C. If g is odd and at least 3, by deleting either I 1 and J 1 , or J g and I g+1 , we cover at least half of {1, . . . Q} by sets G j and some intermediate i l , and c is at least C.

Thus if d i=1 d(v i , v ′ i ) is smaller than a constant C, we must have g = 1; then if d i=1 d(v i , v ′ i ) < 1, v i,J 1 = v ′ i,J 1 .
Thus if c is smaller than C, we get our conclusion under the extra hypothesis (H0).

For the end of the proof of average d-separation, without the hypothesis (H0), we refer the reader to the end of the proof of Proposition 44 in [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF], as there is nothing different.

As is proved in Theorem 3 of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF], for uniquely ergodic systems average d-separation implies non-rigidity, but we shall not use that here, as Theorem 15 below gives a simpler and more general proof. We use now the stronger notion of d-separation: Proposition 13. If the minimality condition is satisfied, (X ′ , S) is linearly recurrent, and, for all

1 ≤ u ≤ d, σ j (u) = σ j+1 (u), 0 ≤ j ≤ r -1, j = t, σ r σ t-1 (u) = σ 0 σ t (u) (resp. σ r (u) = σ 0 (u) if β j = 1 -α for all j), then L(T ) is d-separated and (Y, T ) is not of rank one.

Proof

Then in Proposition 12 we can replace e = d by e = 1, with the same proof. Then the proof of Theorem 10 of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF] applies without modifications. This last proposition is satisfied in particular for Veech 1969. 4.3. Isolated points. In Theorem 8, the absence of linear recurrence comes from the fact that in the Rokhlin towers some β i , i = t, comes "too close", horizontally and vertically, to α, or 0 (which is close to α), or another β j . Thus we define an opposite notion, which we call the isolation (in the towers) of these points.

Definition 14. In the Ostrowski expansion of Proposition 7, for integers

n ≥ 1, M ≥ 1 • for j = t, β j is (n, M)-isolated if there exist n -M ≤ m 1 ≤ n, n -M ≤ m 2 ≤ n, m 2 odd, n -M ≤ m 3 ≤ n, m 3 even, n -M ≤ m ′ i ≤ n, 1 ≤ i ≤ r, i = j, satisfying b m 1 (β j ) = a m 1 -1, b m 2 (β j ) = a m 2 , b m 3 (β j ) = a m 3 , b m ′ i (β j ) = b m ′ i (β i ), for all 1 ≤ i ≤ r, i = j, • α is (n, M)-isolated if for all 1 ≤ i ≤ r, there exist n -M ≤ m i ≤ n, n -M ≤ m ′ i ≤ n, m ′ i odd, n -M ≤ m ′′ i ≤ n, m ′′ i even, satisfying b m i (β i ) = a m i -1, b m ′ i (β i ) = a m ′ i , b m ′′ i (β i ) = a m ′′ i .
To make statements simpler, we shall write sometimes that always one of the β i is isolated to denote there exists M such that for all m, there exists 1 ≤ j ≤ r, j = t such that β j is (m, M)isolated, and, mutatis mutandis, we shall write that always one of the β i or α is isolated.

Theorem 8 says that T is linearly recurrent whenever always all the β i , i = t, and α, are isolated; but weaker assumptions can also be useful. The first one is a sufficient condition for unique ergodicity. Proposition 14. If the minimality condition is satisfied, α has bounded partial quotients, and there exists M and a sequence p k → +∞ such that for all k, all β i , i = t, and α are (p k , M)-isolated, T is uniquely ergodic.

Proof

By the proof of Theorem 8, this condition implies that lim sup n→+∞ ne n (S, µ) > 0 for the Lebesgue (and unique invariant) measure µ; thus by the proof of Proposition 10 lim sup n→+∞ ne n (T, µ) > 0 for the Lebesgue measure µ, and we conclude by Proposition 2. Proposition 14 will be used to build uniquely ergodic examples when needed; note that its hypothesis is not equivalent to the unique ergodicity of T : it is not satisfied by Veech 1969 if the sequence b n (β) is made of strings of increasing lengths where either b n = a n -1 or b n = a n , b n+1 = 0, while T is uniquely ergodic by [START_REF] Veech | Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod 2[END_REF].

Then, as we mentioned above, for our systems non-rigidity will be implied by weaker conditions than the ones ensuring average d-separation.

Theorem 15. Suppose the minimality condition is satisfied, α has bounded partial quotients, and there exists M such that

• either for all n, there exists 1 ≤ j ≤ r, j = t, such that β j is (n, M)-isolated,

• or the product inequality is satisfied, and for all n, either α is (n, M)-isolated or there exists 1 ≤ j ≤ r, j = t, such that β j is (n, M)-isolated, then (Y, T ) is not rigid for any ergodic invariant measure.

Proof

Let µ be an ergodic invariant measure for T . Assume that (Y, T ) is rigid; then there exists a sequence Q k tending to infinity such that µ(D∆T Q k D) tends to zero for each of the d(r + 2) intervals D defining the natural coding of T . We fix ǫ and k such that for all these intervals

µ(D∆T Q k D) < ǫ. Let A D,k = D∆T Q k D; by the ergodic theorem, for each D and k 1 N N -1 j=0 1 T j A D,k (z) tends to µ(A D,k
), for almost all z; we can choose a set Λ of full µ-measure on which this convergence holds for all D and k. Thus for all z in Λ and all k, there exists N 0 (k) such that for all N larger than N 0 (k) and all D,

1 N N -1 j=0 1 T j A D,k (z) < ǫ.
By summing these d(r + 2) inequalities, we get that

d(z 0 . . . z N -1 , z Q k . . . z Q k +N -1 ) < d(r + 2)ǫ
for all N > N 0 (k). Moreover, for z in some set Λ ′ of full µ-measure, we can choose N 0 (k) such that for all N > N 0 (k) these inequalities are also satisfied if we replace z by any of the d different points z ′ such that φ(z ′ ) = φ(z).

We shall now show that this is not possible by estimating d i=1 d(x i 0 . . . x i N -1 , y i 0 . . . y i N -1 ) for the d points x i such that φ(x i ) is a given point x and the d points y i such that φ(y i ) is a given point y. We take n ≥ 1 such that α n+1 ≤ x -y ≤ α n , and N much larger than q n ; we shall look at the trajectories of x and y in the n-towers.

We partition {0, . . . N -1} into successive integer intervals where x and y agree or disagree: we get intervals I 1 , J 1 , . . . , I h , J h , I h+1 as in the proof of Proposition 12; for all l, x J l = y J l , x I l and y I l are either empty or completely different, i.e. their distance d is one. Except maybe the first one, each J l begins after we see α or a β i , i = t, between the trajectories of x and y, and ends before we see 1 -α or a β i , i = t, between the trajectories of x and y. of the previous paragraph. The contributions are the expected ones until we reach the top of the small n-tower, whose contribution is τ q n-1 -1,n . Then the orbit of x crosses levels 0, 1, ... of the large n-tower, staying to the right of β i , 1 -α or 0 (because we have excluded that x is in the leftmost part of width ǫα n of column (0)), until we reach the q n -1-th iterate of x, which is still at least ǫq n levels below the top. As long as g ≤ q n -q n-1 -1, there is no β i , 1 -α or 0 between the right part of level g of the large n-tower and the left part of level g + q n-1 of the large n-tower, thus the contributions are the expected ones until the orbit of x reaches level q n -q n-1 -1 of the large n-tower, whose contribution is τ qn-1 . Then for g ≥ q n + q n-1 , there is no β i , 1 -α or 0 between this right part of level g of the large n-tower and the left part of level g + q n-1 -q n of the small n-tower, there is no β i , 1 -α or 0 in this level g + q n -q n-1 of the small n-tower because the orbit of xt has not reached the upper ǫq n levels, there is no β i , 1 -α or 0 between this level g + q n -q n-1 of the small n-tower and the left part of the same level of the large n-tower. Thus the contributions are still as expected and our result holds.

Theorem 17. If α has bounded partial quotients, all the β i cluster on α, σ k σ j = σ j σ k for all j, k, then (Y, T ) is rigid for any invariant measure.

Proof For any k, we choose

n = m k + [ N k 2 ]
. For a given ǫ, by the proof of Theorem 8, if k is large enough the hypotheses of Lemma 16 are satisfied, and its results hold with Ξ n and θ h,n .

By definition, for all h and h ′ , θ h ′ ,n is of the form θ ′ θ h,n θ ′-1 where θ ′ is some composition of the σ(x). As all these commute, θ h,n is a constant θ n for all h, and ψ qn (x) = θ n for all x in Ξ n .

Moreover, if x is in level h in the n-towers, R qn x is in level h -q n-1 if x is in column (0) between levels q n-1 and q n + q n-1 -1, in level h + q n -q n-1 if x is in the small tower, in level h if x is in any other level. Thus, again as the σ(x) commute, ψ qn (R qn x) = θ n for all x in R -qn Ξ n , and similarly ψ qn (R lqn x) = θ n for all x in R -lqn Ξ n , hence ψ lqn (x) = θ l n for all x in ∩ l-1 l ′ =0 R -l ′ qn Ξ n . Let 1 ≤ ζ n ≤ d! be the order of the permutation θ n : then ψ ζnqn (x) is the identity for x in a set of measure at least 1 -6d!ǫ.

As also |R ζnqn x -x| < Cd! qn , we get that the sequence ζ n q n is a rigidity sequence for (Y, T ).

Theorem 17 is valid in particular when the permutations σ i correspond to the addition of some elements of Z/dZ, as in [START_REF] Veech | Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod 2[END_REF], [START_REF] Stewart | Irregularities of uniform distribution[END_REF] or [START_REF] Merrill | Cohomology of step functions under irrational rotations[END_REF]. The same technique, with more work, applies when the σ i do not commute, but only in some very particular cases.

Proposition 18. Suppose d = 3, r = 1, with one marked point β = 1 -α, and the two values of σ(x) are a transposition and a circular permutation. For every α with bounded partial quotients, we can find β such that T is rigid for any invariant measure.

Proof

For this, we use again the quantity ψ n (x) = σ(R n-1 x)...σ(x). For any of our systems with r = 1, we can define by recursion three quantities:

• if β is in the large n-tower, and n is odd, ψ 1,n , resp. ψ 2,n , is the value of ψ qn on the basis of the large n-tower left, resp. right, of the vertical of β, ψ 3,n is the value of ψ q n-1 on the basis of the small n-tower; • if β is in the large n-tower, and n is even, ψ 1,n , resp. ψ 2,n , is the value of ψ qn on the basis of the large n-tower right, resp. leftt, of the vertical of β, ψ 3,n is the value of ψ q n-1 on the basis of the small n-tower; • if β is in the small n-tower, and n is odd, ψ 2,n , resp. ψ 3,n , is the value of ψ q n-1 on the basis of the small n-tower left, resp. right, of the vertical of β, ψ 1,n is the value of ψ qn on the basis of the large n-tower; • if β is in the small n-tower, and n is even, ψ 2,n , resp. ψ 3,n , is the value of ψ q n-1 on the basis of the small n-tower right, resp. left, of the vertical of β, ψ 1,n is the value of ψ qn on the basis of the large n-tower;

The construction of the towers implies that

• if β is in the large n-tower and b n+1 (β) = a n+1 , ψ 1,n+1 = ψ 3,n ψ b n+1 1,n ψ a n+1 -b n+1 2,n , ψ 2,n+1 = ψ 3,n ψ b n+1 +1 1,n ψ a n+1 -b n+1 -1 2,n , ψ 3,n+1 = ψ 2,n ; • if β is in the large n-tower and b n+1 (β) = a n+1 , ψ 1,n+1 = ψ 3,n ψ a n+1 1,n = ψ 3,n ψ b n+1 1,n ψ a n+1 -b n+1 2,n , ψ 2,n+1 = ψ 2,n , ψ 3,n+1 = ψ 1,n ; • if β is in the small n-tower, ψ 1,n+1 = ψ 3,n ψ a n+1 1,n , ψ 2,n+1 = ψ 2,n ψ a n+1 1,n , ψ 3,n+1 = ψ 1,n .
Given α, we shall build a β clustering on α, such that for infinitely many n with β close to α in the n-tower both ψ 1,n and ψ 1,n-1 are circular permutations, or equivalently have signature 1.

We build β by its b n (β), We put N 0 = 0 and choose an M 0 > N 0 + 2; for N 0 + 1 ≤ n ≤ M 0 -1, we choose any 0 ≤ b n (β) ≤ a n -1, so that β stays in the large n-tower, which implies in particular, because of the hypothesis on σ(x) and the definition of T , that ψ 1 (n) and ψ 2 (n) have opposite signatures. If ψ 1,M 0 -1 has signature +1, we put M ′ 0 = M 0 -1. Otherwise, we choose 0 ≤ b M 0 (β) ≤ a M 0 -1; then if ψ 1,M 0 has signature +1, we put M ′ 0 = M 0 . If both ψ 1,M 0 and ψ 1,M 0 -1 have signature -1, ψ 3,M 0 = ψ 2,M 0 -1 and ψ 2,M 0 have signature +1, and the signature of ψ 1,M 0 +1 is (-1) b M 0 +1 ; if we choose b M 0 +1 even this will be +1. We choose an even b M 0 +1 < a M 0 +1 (this is always possible as we may take b M 0 +1 = 0), and put M ′ 0 = M 0 + 1. Thus in all cases ψ 1,M ′ 0 has signature +1 and β is in the large M ′ 0 -tower. If ψ 1,M ′ 0 -1 has also signature +1, we define N ′ 0 = M ′ 0 . Otherwise, ψ 1,M ′ 0 -1 has signature -1, ψ 3,M ′ 0 = ψ 2,M ′ 0 -1 has signature +1, ψ 2,M ′ 0 has signature -1, and the signature of φ 1,M 0 +1 is (-1) a M 0 +1 -b M 0 +1 , and we choose b M 1 +1 (β) so that ψ 1,M ′ 0 +1 has signature +1; if a M 0 +1 > 1, we can do it such that β is in the large M 0 + 1-tower and put N ′ 0 = M 0 + 1. If a M 0 +1 = 1, we choose b M 0 +1 = 1 and β is in the small M 0 + 1-tower. Using the recursion formulas above, we get that ψ 2,M ′ 0 +1 has signature -1, ψ 3,M ′ 0 +1 has signature +1, ψ 1,M ′ 0 +2 has signature +1, ψ 3,M ′ 0 +2 has signature +1, and β is in the large M ′ 0 + 2-tower. We put N ′ 0 = M 0 + 2. Then we choose N 1 > N ′ 0 and for N ′ 0 ≤ n ≤ N 1 we choose b n (β) = a n -1. The recursion formulas imply that, for all those n, ψ 1,n has signature +1, ψ 2,n has signature -1, ψ 3,n has signature -1. Then we choose b N 1 +1 = a N 1 +1 -1 (which may imply that β is in the small N 1 +1-tower), and start the same process again with N 0 replaced by N 1 . Thus we define sequences

N k ≤ M k ≤ M ′ k ≤ N ′ k < N k+1
, and we choose N k+1 so that N k+1 -N ′ n tends to infinity.

We can now adapt the proof of Theorem 17. For any k, we choose n = [

N k+1 -N ′ k 2
]. For a given ǫ, by the proof of Theorem 8, if k is large enough the hypotheses of Lemma 16 are satisfied, and its results hold with Ξ n and θ h,n . Moreover, by the proof of Lemma 15, θ 0,n = ψ 1,n . All this is still true if we replace n by n -1.

By definition, for all h, θ h ′ ,n is of the form θ ′ θ 0,n θ ′-1 where θ ′ is some composition of the σ(x). Thus the signature of θ h,n is +1 for all h, and so is the signature of θ h,n-1 . This implies that all the θ h,n and θ h,n-1 are circular permutations, and thus commute.

We conclude as in Theorem 17 that ψ 3qn (x) is some θ 3 h,n , and thus the identity, for all x in a set of measure at least 1 -Cǫ, and that the sequence 3q n is a rigidity sequence for (Y, T ).

4.5.

The cases d = 2. In these cases, which constitute the most immediate generalizations of Veech 1969, the two possible permutations are the identity I and the exchange E. Not only they commute, but, if we have two sequences of such permutations σ i,l = σ i,r for all 1 ≤ i ≤ K, then σ K,l ...σ 1,l and σ K,r ...σ 1,r are equal if K is even, different if K is odd. Thus, as we shall see in the two following propositions, a cluster of an even number of marked points (different from 1 -α) behaves as if there was no marked point at all, and a cluster of an odd number of such marked • if β 2 is the rightmost of the points β 2 , β 3 , β 4 . By the ergodic theorem, for N large, there are about ρN ≤ α n N indices j such that β 2 -ρ ≤ T j x ≤ β 2 , and at least about C 2 α n N indices j such that β 2 -C 2 α n ≤ T j x ≤ β 2 ; • If β 2 is the middele one of the points β 2 , β 3 , β 4 , suppose for example β 3 is the leftmost one. By the ergodic theorem, for N large, there are about ρN ≤ α n N indices j such that β 3 ≤ T j y ≤ β 3 + ρ, and at least about C 2 α n N indices j such that β 3 ≤ T j y ≤ β 3 + C 2 α n . We group the I l and J l in intervals K g , using β = β 2 in the first two cases, β = β 3 in the last case. Take the first case for example: for a proportion at least C 2 of the K g , J l + (g) ends at a j such that T j x is to the right of β 2 , and between β 2 and the verticals of β 3 and β 4 . Hence for these j we cannot see β 3 or β 4 between the trajectories of x and y before j and after the basis of the towers, or after j and before the top of the towers; thus for these K g the permutations giving the first letter of #J l -(g+1) are the same as when β 2 is isolated. The vertical distances from β 2 to α, 1 -α and β 1 being bounded from below as in the previous case, both #J l + (g) and #J l -(g+1) are at least C 0 q n ; thus for this proportion C 2 of the K g there is a contribution of 1 to the global d-sum on a length at least C 0 q n ≥ C 0 C 1 #K g . The other cases are similar, and we conclude that the global d-sum cannot be close to 0.

Note that in the particular case of d = 2, two different permutations are different on all points, so we could make the above reasonings on each d(x i 0 . . . x i N -1 , y i 0 . . . y i N -1 ), but that would not simplify significantly the computations.

Lemma 9 .

 9 If (X ′ , S) is linearly recurrent, when W is a bispecial word in L(S), of length greater than an initial constant C 0 , then if W U is in L(S) with fixed |U| ≤ C|W |, then U can only be one of two words U 1 and U 2 , where the first letters of U 1 and U 2 are different, possibly the second letters of U 1 and U 2 are different, and then the l-th letters of U 1 and U 2 are the same for l ≤ |U 1 | ∧ |U 2 |.

FIGURE 7 .

 7 FIGURE 7. All β i cluster on α

  Sataev[START_REF] Masur | TABACHNIKOV: Rational billiards and flat structures[END_REF]: we build a surface by gluing d tori, the interval [β i , β i+1 [ in the right edge of the s-th torus being glued with the same interval in the left edge of the σ i s-th torus, and mutatis mutandis for the intervals [0, β 1 [ and [β r , 1[. Then we take the directional flow of slope α, going from one torus to the other when crossing the gluing lines, and T is its first return map on the union of the d left vertical sides.This model allows us to give a minimality condition for generalized Veech -Sataev systems.Proposition 4. If α and all the β i are irrational, all the β i , i = t, and all the β i -β j are not in Z(α), an NSC for minimality is that no strict subset of {1 . . . d} is invariant by all the σ i .Proof If a strict subset A of {1 . . . d} is invariant by all the σ i , then ∪ i∈A [0, 1[×{i} is invariant by T , and T is not minimal.

We can make examples satisfying the hypotheses of Proposition 20 for every value of α. For example, if all a n are equal to 1, for

) can be successively 1, 0, 0, 1, 0, 0, 1, 0, 0...

Suppose that for some j = t β j is (n, M)-isolated. We group the I l and J l into intervals K g = I l -(g) ∪ J l -(g) ∪ I l -(g)+1 ∪ J l -(g)+1 ... ∪ I l + (g) ∪ J l + (g) where J l -(g) begins after β j , J l + (g) ends before β j , and no other J l inside K g has any of these two properties. By Corollary 6, for all g #K g ≤ 2(q n + q n+1 + q n+2 ) ≤ C 1 q n , while #K g ≥ q n because two times where β j is between the trajectories of x and y are separated by at least q n . Also, by the proof of Theorem 8, y n (β j ), y ′ n (β j ), y ′′ n (β j ) and all y n (β i , β j ), i = j, are at least C 2 q n , thus for each g we have #J l -(g) ≥ C 2 q n , #J l + (g) ≥ C 2 q n . Now, for each i, x i J l + (g) and y i J l + (g) are either equal or completely different. If for at least one i they are completely different, then d i=1 d(x i J l + (g) , y i J l + (g) ) ≥ 1 and d i=1 d(x i Kg , y i Kg ) ≥ C 3 . Otherwise, we deduce the first letters of x i J l -(g+1) and y i J l -(g+1) from the common last letter of x i J l + (g) and y i J l + (g) as in the proof of Proposition 12 above, and find that they must be different for at least one i, because the permutations σ j 1 which is σ(x) on the interval left of β j and σ j 2 on the interval right of β j have different values on at least one point. Then d i=1 d(x i J l -(g+1) , y i J l -(g+1) ) ≥ 1 and d i=1 d(x i K g+1 , y i K g+1 ) ≥ C 3 . Thus we have always d i=1 d(x i Kg∪K g+1 , y i Kg∪K g+1 ) ≥ C 4 . We extend {0, ...N -1} by at most C 1 q n on the left and on the right to a set K ′ made with an even number of

Suppose that α is (n, M)-isolated: then we make a similar reasoning. Now our interval K g are defined by J l -(g) begins after α, J l + (g) ends before 1 -α, and no other J l inside K g has any of these two properties. To get that the first letters of some x i J l -(g+1) and y i J l -(g+1) must be different, we use that σ 0 σ t-1 and σ r σ t , resp. σ 0 and σ r if β j = 1 -α for all j, have different values on at least one point. By the proof of Theorem 8, all

Under the hypotheses of the theorem, this last relations holds for all n and all x and y with α n+1 ≤ x -y ≤ α n , thus this contradicts rigidity.

Theorem 15 applies in particular when (X ′ , S) is linearly recurrent, even when σ 0 σ t = σ r σ t-1 , resp. σ 0 = σ r if β j = 1 -α for all j (as soon as there is at least one β j = 1 -α, otherwise we are in the cases of [START_REF] Ferenczi | Rigidity of interval exchanges[END_REF]). As mentioned in the introduction, this gives the first known examples of non rigid non linearly recurrent interval exchange transformations (note that we could get further examples for any r ≥ 2 and d ≥ 2):

Proof of Theorem 1 Suppose the conditions of Theorem 15 are satisfied but not those of Theorem 8. This is possible for example if we build β 1 = 1 -α and β 2 = 1 -α with prescribed Ostrowski expansions such that, for a fixed M, for all m β 2 is (m, M)-isolated, while there are unbounded strings of consecutive b n (β 1 ) = a n -1. Then (X ′ , S) is not linearly recurrent and (Y, T ) is not rigid, and not linearly recurrent by Proposition 10. Unique ergodicity will be satisfied by Proposition 14 if we ensure β 1 is (p k , M)-isolated for a sequence p k . Now, if we take r = 2 and d = 2, with β 1 and β 2 as above, and we alternate between the two possible permutations, the identity and the exchange, changing when we cross β 1 and β 2 , we get the examples claimed in the theorem.

When (X ′ , S) is not linearly recurrent, Lemma 9 is not satisfied, and we do not know whether (Y, T ) is average d-separated.

4.4.

In the grey zone: rigidity. We call grey zone the cases when α has bounded partial quotients, but (X ′ , S) is not linearly recurrent. We could conclude to non-rigidity when the hypotheses of Theorem 15 are satisfied, but there are still many other cases. When Theorem 15 does not apply, then for all n some β i and β j and/or β i , i = t, and α are too close in the n-towers. The simplest case is when all the β i come close to α simultaneously. Definition 15. We say that all the β i cluster on α if there exist two sequences m k and N k , tending to infinity, with m k + N k < m k+1 , such that for all 1 ≤ i ≤ r, i = t, we have

We recall that T n (x, s) = (R n x, ψ n (x)s) where

Lemma 16. Suppose that for a given n, for all i = t, either x n (β i , α) < ǫα n and y n (β i ) < ǫq n , or

point of the level h in the large n-tower (the basis being level 0). Then, on a set Ξ n of measure at least 1 -6ǫ, whenever x is in level h of the large or small n-tower, then

Proof

We do the proof for n odd. We delete the set Ξ n , of small measure as claimed, made with the x in any of the five following sets: 7, we show the n-towers and what we see less than α n to their left. The set we delete is between dotted lines, or between dotted line and sides, in the n-towers; the β i are confined to the small rectangles near α and 0 (remember 1 -α is just below 0). If x is in the large n-tower but not in column (0), using the above exclusions, we see that whenever the orbit of x is in level g, there is no β i , 1 -α or 0 between this trajectory and x g , and thus the contribution of level g to ψ qn (x) is τ g,n , and the claimed formula holds.

If x is in the q n-1 first levels in column (0), the contribution of level g is τ g,n until we reach the top of the large n-tower; then the orbit of x crosses levels 0, 1, ... of the small n-tower, staying to the right of β i , 1 -α or 0. Hence there is no β i , 1 -α or 0 between this right part of level g of the small n-tower and and the left part of level g of the large n-tower, the contribution of this level g to ψ qn (x) is τ g,n , and our formula holds.

If x is in column (0) (either in the large or in the small n-tower) above the q n-1 first levels but below the upper ǫq n levels (of this column, that is of the small n-tower), we continue the reasoning points behaves as an isolated marked point. In theory, with both these properties together with Theorems 15 and 17, we could solve completely the question of rigidity for d = 2 and any number of marked points. However, as the reader may be convinced by studying Proposition 20 below, a full result would be unduly complicated to state, let alone to prove, so we shall limit ourselves to a complete study of the cases when 1 ≤ r ≤ More precisely:

• if r = 1 and β = 1 -α, (the Veech 1969 case), or r = 2 and

) is linearly recurrent, rigid for any invariant measure otherwise; • if r = 2 and β j = 1 -α for all j, or r = 3 and β t = 1 -α, (Y, T ) is non-rigid for any ergodic invariant measure if always one of the β i is isolated, rigid for any invariant measure otherwise; • if r = 3 and β j = 1 -α for all j, or r = 4 and β t = 1 -α, (Y, T ) is non-rigid for any ergodic invariant measure if always α or one of the β i is isolated, rigid for any invariant measure otherwise.

Proof For Veech 1969, Theorem 15 does not apply if and only if (X ′ , S) is not linearly recurrent, and then we can use Theorem 17 to get rigidity. This is true also when r = 2 and β t = 1 -α, as we change permutation, from I to E or from E to I, when we cross β i , thus σ 0 = σ r , σ t = σ t-1 , and the product inequality is satisfied.

When r = 2 and β j = 1 -α for all j, σ 0 = σ r ; when r = 3 and β t = 1 -α, σ t = σ t-1 , σ 0 = σ r , hence in both these cases the product inequality is not satisfied. Thus Theorem 15 applies only when always one of the β i is isolated, and Theorem 17 applies when all β i cluster on α. There remains the case where α is always isolated but β 1 and β 2 can be very close. In that case, we choose an n such that x n (β 1 , β 2 ) < ǫα n and y n (β 1 , β 2 ) < ǫq n . Suppose for example that β 2 is higher than β 1 in the n-towers; let σ i,l , resp. σ i,r , be the permutation σ(x) on the left (resp. right) of β i on the same level of the n-towers, i = 1, 2, let σ j 1 , ..., σ j h be the values of σ(x) on the successive levels between β 1 and β 2 . Then σ i,l = σ i,r for i = 1, 2, and thus σ 2,l σ j h , ..., σ j 1 σ 1,l = σ 2,r σ j h , ..., σ j 1 σ 1,r by the remark at the beginning of Section 4.5 and commutation. Hence we can make the same reasoning as in Lemma 16: supposing for example that in the n-towers β 2 is higher than β 1 and to its right,

, with β ′ i in the basis of the large n-tower; we delete a small set made with the images by

of the basis of the large n-tower, and the upper two levels of the small n-tower. Then for the non-deleted x we get the same formula as in Lemma 16, and, as in Theorem 17 we conclude that 2q n is a rigidity sequence for T .

When r = 3 and β j = 1 -α for all j, σ 0 = σ r ; when r = 4 and β t = 1 -α, we have σ t = σ t-1 and σ 0 = σ r , hence in both these cases the product inequality is always satisfied. Therefore the only case when we cannot apply Theorem 15 or Theorem 17 is when α and the β i are never isolated, but the β i do not cluster on α; thus infinitely often α is close to one of the β i , for example β 3 , while β 1 and β 2 are very close. For such an n, the reasoning of the last case applies again, and, by deleting all what we have deleted in this case and all we have deleted in Lemma 16, for the non-deleted x we get the same formula as in Lemma 16, and, as in Theorem 17 we conclude that 2q n is a rigidity sequence for T .

In the examples of the next proposition, one of the β i (to make things simpler, we take always the same one, β 1 ) will be close to α infinitely often, while the other three will be always far from α and β 1 but infinitely often close together. This allows non-rigidity though none of our β i or α is always isolated.

Proposition 20. Suppose d = 2, we have four marked points β 1 , β 2 , β 3 , β 4 different from 1 -α, the minimality condition is satisfied, α has bounded partial quotients, there exist M 0 and two sequences m k and N k , tending to infinity, with

Then T is not rigid for any ergodic invariant measure.

Proof

By the proof of Theorem 8, there exists a fixed constant C 0 , depending only on the size of the partial quotients of α, such that,

• for any β, if there exist n -

Our hypotheses ensure that for our system, the first result holds for every n with β = β 2 , and also (because of the values of b

Using the other part of the proof of Theorem 8, we choose M 1 > M 0 , depending only on the size of the partial quotients of α, such that,

• for any

2 . Now we make the beginning of the proof of Theorem 15 above: to contradict rigidity, we have to estimate d i=1 d(x i 0 . . . x i N -1 , y i 0 . . . y i N -1 ) for the d points x i such that φ(x i ) is a given point x and the d points y i such that φ(y i ) is a given point y. We take n ≥ 1 such that α n+1 ≤ ρ = x -y ≤ α n , and N much larger than q n ; we shall look at the trajectories of x and y in the n-towers.

For this n, we place β 2 , β 3 , β 4 in the n-towers. We call β the one which is lowest, β ′′ the highest, β ′ the middle one. As in the proof of Theorem 15, we cut {0, ...N -1} into intervals I l and J l and group them into intervals K g = I l -(g) ∪ J l -(g) ∪ I l -(g)+1 ∪ J l -(g)+1 ... ∪ I l + (g) ∪ J l + (g) where J l -(g) begins after β, J l + (g) ends before β, and no other J l inside K g has any of these two properties. We have again that for all g #K g ≤ C 1 q n . and #K g ≥ q n . The beginning of J l -(g) and the end of J l + (g) correspond to a j such that β is between T j x and T j y, which is equivalent to T j y ∈ [β -ρ, β[; by the ergodic theorem, for N large, there are about ρN ≥ α n+1 N such indices j. We call "bad" those j for which

4 [, which correspond at most to about N α n+1 2 indices. By deleting all K g for which J l + (g) ends before a bad j, we keep at least half of the intervals K g . Again, we look at the transition between K g and K g+1 for the non-deleted K g . The beginning of J l + (g) is α or a β i ; the possible one making J l + (g) shortest is either α or β 1 , which is at least C 0 q n far (vertically) from β; thus #J l + (g) is at least C 0 q n . For each i, x i J l + (g) and y i J l + (g) are either equal or completely different. If for at least one i they are completely different, this gives a contribution of 1 to the global d-sum on the length of J l + (g) . Now, by our hypothesis, both β ′ and β ′′ are α n+1 4 close (horizontally) to β and C 0 qn 2 close (vertically) to β. Thus the fact that our K g has not been deleted guarantees that after seeing β between T j y and T j x, we shall see β ′ between T j ′ y and T j ′ x, β ′′ between T j ′′ y and T j ′′ x, with j < j ′ < j ′′ < j + C 0 qn 2 ; and we do not see either 1 -α or β 1 before as we are far enough from the top of the towers. Thus J l -(g+1)+2 begins with β ′′ , and ends before a point which, in the case that makes it shortest, is either β 1 or 1 -α and is at least C 0 qn 2 far (vertically) from β ′′ . If x i J l + (g) and y i J l + (g) are equal for all i, we shall deduce from their common last letter the first letters of x i J l -(g+1)+2 and y i J l -(g+1)+2 as in the proof of Proposition 12 above. For that we use again the remark at the beginning of Section 4.5: let σ 1,l , σ 2,l , σ 3,l , resp. σ 1,r , σ 2,r , σ 3,r be the permutations σ(x) on the left (resp. right) of β, β ′ , β ′′ on the same level of the n-towers. The two permutations involved in computing the letter we want are, by commutation, σσ 3,l σ 2,l σ 1,l and σσ 3,r σ 2,r σ 1,r for a fixed σ, and these are different. This gives a contribution of 1 to the global d-sum on the length of J l -(g+1) + 2.

Thus, for each non-deleted K g , there is a contribution of 1 to the global d-sum on a length at least C 0 qn 2 ≥ C 0 2C 1 #K g . The non-deleted K g make a proportion at least 1 2C 1 of {0, ...N -1}, thus the global d-sum cannot be close to 0.

Suppose now m k + N k + M 0 ≤ n ≤ m k+1 + M 1 . Then β 2 is (n, M 0 + M 1 ) isolated and, after fixing x and y we conclude as in the proof of Theorem 15 that the global d-sum cannot be close to 0.

Suppose now m

For these n, our hypotheses ensure that there exist n ≤ m

, By the proof of Theorem 8, this implies that both x n (β 2 , β 3 ) and x n (β 2 , β 4 ) are at least C 2 α n .

We fix an n and place β 2 , β 3 , β 4 in the n-towers. Again, we fix x = y + ρ, define the I l and J l .

• If β 2 is the leftmost of the points β 2 , β 3 , β 4 . By the ergodic theorem, for N large, there are about ρN ≤ α n N indices j such that β 2 ≤ T j y ≤ β 2 + ρ, and at least about C 2 α n N indices j such that β 2 ≤ T j y ≤ β 2 + C 2 α n ;