# Languages of general interval exchanges

Sébastien Ferenczi, Pascal Hubert, Luca Q. Zamboni

► To cite this version:

Sébastien Ferenczi, Pascal Hubert, Luca Q. Zamboni. Languages of general interval exchanges. Annali della Scuola Normale Superiore di Pisa, 2024, 33, 10.2422/2036-2145.202302_006. hal-04273835

HAL Id: hal-04273835

https://hal.science/hal-04273835v1

Submitted on 7 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
1

# LANGUAGES OF GENERAL INTERVAL EXCHANGE TRANSFORMATIONS

2

SÉBASTIEN FERENCZI, PASCAL HUBERT, AND LUCA Q. ZAMBONI

**ABSTRACT.** The languages generated by interval exchange transformations have been characterized by Ferenczi-Zamboni (2008) and Belov-Cernyatev (2010) under some extra conditions on the system. Lifting these conditions leads us to consider successively natural codings of standard interval exchange transformations, natural codings of affine interval exchange transformations, grouped codings of affine interval exchange transformations, and natural codings of generalized interval exchange transformations. We show that these four classes of languages are strictly increasing, and give necessary and/or sufficient (but not all equally explicit) combinatorial criteria to describe each of them. These work also, mutatis mutandis, for interval exchanges with flips.

3

4

5

6

Interval exchange transformations were originally introduced by Oseledec [37], following an idea of Arnold [1], see also [26]; the unit interval is partitioned into subintervals which are rearranged by piecewise translations. These *standard* exchange transformations have been successively generalized to:

7

8

* interval exchange transformations with flips [35], where some or all translations are replaced by affine maps of slope $-1$;

9

10

11

12

* affine interval exchange transformations, where the translations are replaced by affine maps of arbitrary nonzero slope (if some are negative we have a flipped affine interval exchange transformation), thus the Lebesgue measure is not preserved anymore; these appear in the precursor [2], the oldest published reference may be [29];

13

14

15

* generalized interval exchange transformations, where the translations are replaced by any continuous monotone nonconstant maps (if some are decreasing we have a flipped generalized interval exchange transformation), see [2] [32];

16

17

18

* systems of piecewise isometries, see [20], where the intervals are moved by isometries, but they or their images may be non-disjoint, thus the transformation may be non-injective; these include the interval translation mappings of [6].

19

20

21

22

These generalizations have seen a recent surge in activity (see [31] [32] [21] [22]) primarily centered on the conjugacy problem between these different classes of maps; in this context, standard and generalized interval exchange transformations are the extreme cases while affine interval exchange transformations constitute a fundamental middle step.

23

24

25

26

27

28

29

30

It was Rauzy [39] who first suggested using interval exchange transformations as a possible framework for generalizing the well-known interaction between dynamical systems, arithmetics and word combinatorics of [34] and [12]. In these papers, the languages which arise as *natural codings* of minimal rotations by two intervals, aka *Sturmian languages*, are identified with the *uniformly recurrent* languages of *complexity* $n+1$. Rauzy asked which languages arise as natural codings of interval exchange transformations through their defining intervals (see Definition 6), the Sturmian case corresponding to an exchange of two intervals. Several partial answers to Rauzy’s question were given for 3-interval exchange transformations in [14] [40] [15]. Then two

<footnote>Date: November 24, 2022.</footnote>

<footnote n="2010">2010 Mathematics Subject Classification. Primary 37B10; Secondary 68R15, 37E05.</footnote>
fairly general answers appeared independently for all numbers of intervals. In [17], see Theorem 15 below, two of the authors of the present paper solved the problem for the most studied case among standard unflipped interval exchange transformations, those satisfying a version of Keane's *i.d.o.c. condition*, a condition defined in [27] where it is shown to be stronger (indeed, strictly stronger) than minimality. This description makes use of two main ingredients: an *order condition* (see Definition 1) which dictates the way *bispecial* words can be *resolved* (see Section 1.1), and the absence of *connections* (see Definition 2). In contrast, the criterion in [25] uses a description of the evolution of *Rauzy graphs* which is somewhat cumbersome to state, but applies to all standard interval exchange transformations, including those with flips.

31

32

33

34

35

36

37

38

39

40

In the present paper, we aim to study the languages of interval exchange transformations in the most general framework. We prove first that for every transformation which is called an interval exchange, the language satisfies an order condition (Proposition 8), with a new definition (Definition 1) in the flipped cases, allowing the orders to change according to the number of flipped letters in each bispecial word. The order condition is intrinsically linked to the one-dimensional nature of interval exchange transformations, and constitutes a strong constraint on the possible ways of resolving the bispecials, thus those languages arising from interval exchange transformation form a small family, which becomes larger when all flips are allowed. The order condition fails in general for piecewise isometries (see Remark 3), and the characterization of the associated languages is completely unknown.

41

42

43

44

45

46

47

48

49

50

When the order condition is satisfied, to which extent do we need additional conditions? The following three counter-examples will be described in Section 6 below: they all satisfy an unflipped order condition.

51

52

53

* The language of Example 3 is not a natural coding of a standard interval exchange transformation, but is the natural coding of an affine interval exchange transformation.

54

55

* The language of Example 4 is not a natural coding of an affine interval exchange transformation, but is the coding of an affine interval exchange transformation, where the slope may take more than one value inside the coding intervals, we call it a *grouped coding* of an affine interval exchange transformation.

56

57

58

59

* The language of Example 9 is not a natural or grouped coding of an affine interval exchange transformation, but is the natural coding of a generalized interval exchange transformation.

60

61

Thus all these four families of languages are different, and we can characterize some cases by simple word-combinatorial conditions. Under an order condition

62

63

* by Theorem 19, *all* languages correspond to generalized interval exchange transformations,

64

* by Theorem 13, *recurrent* languages correspond to standard interval exchange transformations,

65

66

* additionnally, by Theorem 14, *aperiodic uniformly recurrent languages* correspond to minimal standard interval exchange transformations.

67

68

But for the affine case, the characterization of the languages is more complicated, and is very much linked to the extensive work of [29] [30] [8] [7] [11] [31], who build affine interval exchange transformations with wandering intervals semi-conjugated to a given standard interval exchange transformation. Thus our criteria to characterize their codings use Birkhoff sums as in these papers: what we get, under an order condition, are necessary or sufficient criteria for a language to correspond to an affine interval exchange transformation by a natural coding (Theorem 20 and

69

70

71

72

73

74
Corollary 21), and a not very explicit necessary and sufficient criterion for a language to correspond to an affine interval exchange transformation by a grouped coding (Theorem 22).

Then Section 6 is devoted to the examples distinguishing our families of languges. A still open problem is to find an aperiodic grouped coding of an affine interval exchange transformation which is not a natural coding of an affine interval exchange transformation; it is quite possible that these do not exist, and in that case the problems of characterizing the natural and grouped codings of affine interval exchange transformations might get a natural solution (Conjecture 1 and Question 3). Another problem is to build a language which is a natural coding of a generalized interval exchange transformation, but which is not a grouped coding of an affine interval exchange transformation. In Example 9, the first property comes from the fact that, by a blow-up process due to Denjoy [13], it is possible to build a generalized interval exchange transformation $T$, with a wandering interval, semi-conjugate to a given standard interval exchange transformation $T'$ (this is indeed the basis of the proof of our Theorem 19), but if $T'$ is conjugate to a rotation, the Denjoy-Koksma inequality [24] prevents such $T$ from being affine, even after subdividing the continuity intervals; we also prove that $T$ fails to satisfy some regularity condition called class $P$ in [24]. Another way to get such examples, allowing $T'$ to be any non purely periodic interval exchange transformation (not only a rotation) is given in Theorem 24 using Rokhlin towers. By using the results of [33], we have also been able to build exmmple where $T'$ is an interval exchange transformation naturally defined from any one of two famous translation surfaces, the *Eierlegende Wollmilch Sau* and the *Ornithorynque* (Section 6.5) but we could prove only that they are not natural codings of an affine interval exchange transformation.

All our results extend without further difficulty to flipped interval exchange transformation by using flipped order conditions (our counter-examples, however, are only written for the particular case where there are no flips).

# 1. LANGUAGES

## 1.1. Usual definitions.
Let $\mathcal{A}$ be a finite set called the *alphabet*, its elements being *letters*. A word $w$ of length $n = |w|$ is $a_1a_2\cdots a_n$, with $a_i \in \mathcal{A}$. The *concatenation* of two words $w$ and $w'$ is denoted by $ww'$.

By a language $L$ over $\mathcal{A}$ we mean a *factorial extendable language*: a collection of sets $(L_n)_{n \ge 0}$ where the only element of $L_0$ is the *empty word*, and where each $L_n$ for $n \ge 1$ consists of words of length $n$, such that for each $v \in L_n$ there exists $a, b \in \mathcal{A}$ with $av, vb \in L_{n+1}$, and each $v \in L_{n+1}$ can be written in the form $v = au = u'b$ with $a, b \in \mathcal{A}$ and $u, u' \in L_n$.

The *complexity function* $p: \mathbb{N} \to \mathbb{N}$ is defined by $p(n) = \#L_n$.

A word $v = v_1...v_r$ is a *factor* of a word $w = w_1...w_s$ or an infinite sequence $w = w_1w_2...$ if $v_1 = w_i, ...v_r = w_{i+r-1}$.

Let $W$ be a family of words or (one- or two-sided) infinite sequences. Whenever the set $L$ of all the factors of the words or sequences in $W$ is a language (namely, is factorial and extendable), we say that $L$ is the language generated by $W$ and denote it by $L(W)$.

A language $L$ is *recurrent* if for each $v \in L$ there exists a nonempty $w \in L$, such that $vw$ ends with $v$.
A language $L$ is uniformly recurrent if for each $v \in L$ there exists $w \in L_n$ such that $v$ is a factor of each word $w \in L_n$.

A language $L$ is *aperiodic* if for all nonempty words $w$ in $L$, there exists $n$ such that $w^n$ is not in $L$.

The *Rauzy graph* $G_n$ of a language $L$ is a directed graph whose vertex set consists of all words of length $n$ of $L$, with an edge from $w$ to $w'$ whenever $w = av, w' = vb$ for letters $a$ and $b$, and the word $avb$ is in $L$.

For a word $w$ in $L$, we call *arrival set of w* and denote by $A(w)$ the set of all letters $x$ such that $xw$ is in $L$, and call *departure set of w* and denote by $D(w)$ the set of all letters $x$ such that $wx$ is in $L$.

A word $w$ in $L$ is called *right special*, resp. *left special* if $\#D(w) > 1$, resp. $\#A(w) > 1$. If $w \in L$ is both right special and left special, then $w$ is called *bispecial*. If $\#L_1 > 1$, the empty word $\epsilon$ is bispecial, with $A(\epsilon) = D(\epsilon) = L_1$.

A bispecial word $w$ in $L$ is a *weak bispecial* if $\#\{awb \in L, a \in A(w), b \in D(w)\} < \#A(w) + \#D(w) - 1$.

A bispecial word $w$ in $L$ is a *neutral bispecial* if $\#\{awb \in L, a \in A(w), b \in D(w)\} = \#A(w) + \#D(w) - 1$.

A bispecial word $w$ in $L$ is a *strong bispecial* if $\#\{awb \in L, a \in A(w), b \in D(w)\} > \#A(w) + \#D(w) - 1$.

To resolve a bispecial word $w$ is to find all words in $L$ of the form $awb$ for letters $a$ and $b$.

The *symbolic dynamical system* associated to a language $L$ is the two-sided shift $S$ acting on the subset $X_L$ of $A^{\mathbb{Z}}$ consisting of all bi-infinite sequences such that $x_r \cdots x_{r+s-1} \in L_s$ for each $r$ and $s$, defined by $(Sx)_n = x_{n+1}$ for all $n \in \mathbb{Z}$.

For a word $w = w_0 \cdots w_t \in L$, the cylinder $[w]$ is the set $\{x \in X_L : x_0 = w_0, \dots, x_t = w_t\}$.

In many papers, $(X_L, S)$ is the one-sided shift the subset $X_L$ of $A^{\mathbb{N}}$ consisting of all infinite sequences such that $x_r \cdots x_{r+s-1}$ is in $L_s$ for every $r, s$. In the present paper, we shall use two-sided sequences $x \in X_L$, but also their infinite suffixes $(x_n, n \ge k)$ and infinite prefixes $(x_n, n \le k)$.

## 1.2. Languages with order conditions.

**Definition 1.** A language $L$ on an alphabet $A$ satisfies a local order condition if, for each bispecial word $w$, there exist two orders on $A$, denoted by $\le_{A,w}$ and $\le_{D,w}$, respectively $<_{A,w}$ and $<_{D,w}$ for the strict orders, such that whenever $awc$ and $bwd$ are in $L$ with letters $a \ne b$ and $c \ne d$, then $a <_{A,w} b$ if and only if $c <_{D,w} d$.

A language $L$ on an alphabet $A$ satisfies an $\mathcal{F}$-flipped order condition for $a$ (possibly empty) subset $\mathcal{F}$ of $A$ if there exist two orders on $A$, denoted by $\le_A$ and $\le_D$, respectively $<_A$ and $<_D$ for the strict orders, such that $L$ satisfies a local order condition where

* the order $<_{A,w}$ is the same as $<_A$ for all $w$,

* $<_{D,w}$ is the same as $<_D$ when the number of occurrences in $w$ of letters belonging to $\mathcal{F}$ is even,

* $<_{D,w}$ is the reverse order of $<_D$ when the number of occurrences in $w$ of letters belonging to $\mathcal{F}$ is odd.
163 **Definition 2.** In a language $L$, a locally strong bispecial word is a bispecial word $w$ such that
164 there exist nonempty subsets $A' \subset A(w)$, $D' \subset D(w)$ such that $\#\{awb \in L, a \in A', b \in D'\} >$
165 $\#A' + \#D' - 1$.

166 If a language $L$ on an alphabet $A$ satisfies a local order condition, a bispecial word $w$ has
167 a connection if there are letters $a <_{A,w} a'$, consecutive in the order $<_{A,w}$, letters $b <_{D,w} b'$,
168 consecutive in the order $<_{D,w}$, such that $awb$ and $a'wb'$ are in $L$, and neither $awb$ nor $a'wb$ is in
169 $L$.

170 In this section, we state general combinatorial properties of languages satisfying some order
171 conditions, or weaker properties, to be used in the next sections. Note that some of these use
172 the same ideas as Section 2.2 of [16], though the present context is both more combinatorial and
173 more general. Further properties with a more dynamical flavor will be studied at the beginning of
174 Sections 4 and 5.

175 **Lemma 1.** A language $L$ which satisfies a local order condition contains no locally strong bispe-
176 cial word, and thus no strong bispecial word.

177 **Proof**

178 Let $w$, $A'$, $D'$ be as in Definition 2. If $\#A'$ or $\#D'$ is 1, then the result is immediate. Assume
179 $\#A' = \#D' = 2$ and put $A' = \{a_1, a_2\}$, $D' = \{b_1, b_2\}$, $a_1 <_A a_2$, $b_1 <_D b_2$. If $a_1wb_2$ and $a_2wb_1$
180 both belong to $L$, this contradicts the local order condition. Now suppose we have proved the result
181 for all $A'$ and $D'$ such that $\#A' \le p$ and $\#D' \le q$; take now $A' = \{a_1 <_{A,w} \dots <_{A,w} a_p <_{A,w}$
182 $a_{p+1}\}$, $D' = \{b_1 <_{D,w} \dots <_{D,w} b_q\}$; then, let $r$ be the largest integer between 1 and $q$ such that
183 $a_pwb_r \in L$. By the local order condition, $a_iwb_j \in L$ for some $1 \le i \le p$ only if $j \le r$, thus by the
184 induction hypothesis there are at most $p+r-1$ possible $a_iwb_j$, $1 \le i \le p$, $1 \le j \le q$. Again by
185 the local order condition, if $a_{p+1}wb_j \in L$ $1 \le j \le q$, then $r \le j \le q$. Thus the number of possible
186 $awb$ belonging to $L$ with $a \in A'$ and $b \in D'$ is at most $p+r-1+q+1$ and we have extended the
187 induction hypothesis to $p+1$ and $q$. A similar reasoning extends it to $p$ and $q+1$, thus the result
188 holds for all possible $A'$ and $D'$.
189 □

190 For languages where each word has at most two right (resp. left) extensions, the absence of
191 strong bispecial words, the absence of locally strong bispecial words, and a local order condition
192 are all equivalent. In the general case, it is easy to find bispecials which are locally strong but not
193 strong (suppose for example that the possible $xwy$ are $awa, awb, bwa, bwb, cwc$), and a local order
194 condition is stricter than the absence of locally strong bispecials.

195 **Example 1.** Suppose $L$ is a language whose words of length 2 are ac, ad, ba, bc, cb, cc, da. Then
196 the empty word is not a locally strong bispecial, yet $L$ does not satisfy any local order condition.

197 Indeed, assume to the contrary that $\epsilon$ satisfies the order condition with respect to $<_{A,\epsilon}$ and $<_{D,\epsilon}$.
198 By possibly reversing both orders, we can assume $c <_{A,\epsilon} a$. Since $\{cb, ac, cc, ad\} \subset L$ this implies
199 $b <_{D,\epsilon} c <_{D,\epsilon} d$. This in turn implies $c <_{A,\epsilon} b <_{A,\epsilon} a$ (since $\{cb, bc, ad\} \subset L$) which in turn
200 implies $c <_{D,\epsilon} a <_{D,\epsilon} d$ (since $\{ba, cc, ad\} \subset L$). Also $b <_{A,\epsilon} d <_{A,\epsilon} a$ because $\{bc, da, ad\} \subset L$.
201 Finally, as ac and da are in $L$, we get $a <_{D,\epsilon} c$ which is a contradiction.

202 We can then choose $L_3$ to be made with acc, ada, bac, bad, bcb, bcc, cba, cbc, ccb, dac, where
203 each word has at most two left (resp. right) extensions and continue by resolving the bispecials so
204 that they are all neutral. We get a language without locally strong bispecials but not satisfying any
205 local order condition.
206 **Lemma 2.** A language *L* which has no strong bispecial factor has a finite number of weak bispecial
factors.
207

208 **Proof**

209 Let $s(n) = p(n + 1) - p(n)$. By Theorem 4.5.4 of [10], see also [9], if $L$ has only weak or neutral bispecials $s(n + 1) \le s(n)$ for all $n$, and, if additionally $L$ has a weak bispecial of length $n$, $s(n + 1) < s(n)$. This cannot happen infinitely many times as $p(n)$ is a growing function. $\square$
210
211
212

213 Another notion aiming at generalizing the properties of some natural codings of interval ex-
214 change tranformations is a *dendric* language, which is defined in [4] (under the name of tree sets):
215 it turns out that a language is dendric iff it has neither locally strong bispecial words nor weak
216 bispecial words, thus there is no inclusion relation between this family and the various order con-
217 ditions. However, by Lemmas 1 and 2, a language satisfying a local order condition is *ultimately*
218 dendric.
219

219 **Lemma 3.** If a language *L* satisfies a local order condition, a word *w* is a weak bispecial iff it has
220 a connection.
221

221 **Proof**

222 Let $A(w)$, ordered by $<_{A,w}$, be $\{a_1, \dots, a_p\}$, and $D(w)$, ordered by $<_{D,w}$, be $\{b_1, \dots, b_q\}$. If there
223 is no connection, then each $D(a_k w) \cap D(a_{k+1} w)$ has at least one element, and indeed exactly one
224 element by Lemma 1: thus the number of possible $awb$, which is $\sum_{k=1}^p \#D(a_k w)$, is $q+p-1$,
225 and $w$ is a neutral bispecial.
226

226 If there is a connection, then for some $l$ $D(a_l w) \cap D(a_{l+1} w)$ is empty. By the local order condi-
227 tion, if $b_j$ is the maximal element (for $<_{D,w}$ of $D(a_l w)$, or equivalently of $D(a_1 w) \cup \cdots \cup D(a_l w)$,
228 then $b_{j+1}$ is the minimal element (for $<_{D,w}$ of $D(a_{l+1} w) \cup \cdots \cup D(a_p w)$. By Lemma 1 applied first
229 to $\{a_1, \dots, a_l\}$ and $\{b_1, \dots, b_j\}$, then to $\{a_{l+1}, \dots, a_p\}$ and $\{b_{j+1}, \dots, b_q\}$, we get that the num-
230 ber of possible $awb$ is at most $j+l-1+p-l+q-j-1 = p+q-2$, thus $w$ is a weak bispecial. $\square$
231

232 **Corollary 4.** A language satisfying a local order condition has complexity $p(n) = kn+l$ for all $n$
233 large enough and with $0 \le k \le \#A-1$. Moreover, $k = \#A-1$ if and only if $L$ has no connection,
234 and in that case $l=1$.
235

235 **Proof**

This comes from Lemmas 1, 2, 3, and Theorem 4.5.4 of [10].
236
237

238 The following result is well known and could be deduced from Section 3.3 of [9], or Theorem
239 4.5.4 of [10].
240

240 **Lemma 5.** If a language *L* has no strong bispecial word, the left (resp. right) special words are
241 the prefixes (resp. suffixes) of a finite number of infinite suffixes (resp. prefixes) of sequences of
242 *X*<sub>*L*</sub>.
243

243 **Proof**

244 Suppose $v$ is left special, and $va$ and $vb$ are left special for letters $a \neq b$, then both $A(va)$ and
245 $A(vb)$ are strictly included in $A(v)$: indeed, otherwise, the possible $cvd$ in $L$ contain at least, for
246 example $cva$ for all $c$ in $A(v)$, $c'vb$ for at least two different $c'$ in $A(v)$, and some $c_i vd_i$ for each $d_i$
247 in $D(v) \setminus \{a, b\}$, and thus $v$ is a strong bispecial word.
248
249
248

249

250

251

252

253

254

Starting from each left special letter *e*, we extend it to the right by one letter at a time; each time two different extensions of the same word are left special, the arrival sets decrease strictly; thus, after a finite number of bifurcations, each new left special extension has the previous one as a prefix, and all these are prefixes of a finite number of sequences $ex_1...x_n$, which are infinite suffixes of sequences of $X_L$.

And a similar reasoning works for the right specials.

☐

255

256

**Lemma 6.** Let $L$ be a language satisfying a local order condition. If $G_n$ is connected (as a nonoriented graph) but $G_{n+1}$ is not connected, then some bispecial word in $L_n$ has a connection.

257

**Proof**

258

259

260

261

262

As $G_n$ is connected, if all pairs of vertices of $G_{n+1}$ which correspond to two consecutive edges of $G_n$ belong to the same connected component of $G_{n+1}$, $G_{n+1}$ is connected. Thus assume that for some $w \in L_n$ and letters $a$ and $b$, $aw$ and $wb$ are not in the same connected component of $G_{n+1}$; then, in particular $awb$ is not in $L$. But as every word is extendable to the left and right, there exist $a'$ and $b'$ such that $a'wb$ and $awb'$ are in $L$, thus $a \neq a'$, $b \neq b'$, and $w$ is bispecial.

263

264

265

Suppose $w$ has no connection. If $a_1w$ is in some connected component $U$ of $G_{n+1}$, so is $wx$ for every $x$ in $D(a_1w)$, hence also $wx$ is in $U$ for one element of $D(a_2w)$ and so on, hence all the $a_iw$ and all $wx$ for $x$ in $D(w)$ are in $U$, and this contradicts the fact that $G_{n+1}$ is not connected. ☐

266

267

268

269

Note that the terminology inherited from two different fields is somewhat counter-intuitive; a *connection* (so named for geometrical reasons) is necessary to *disconnect* the Rauzy graphs. But it is not a sufficient condition, see examples in [16].

270

271

272

An order condition on $L$ allows us to define an order on the set $X_L$, which will be used in Section 4 below. It is well-defined because of the order condition.

273

274

**Definition 3.** Suppose $L$ satisfies an $\mathcal{F}$-flipped order condition. Let $x$ and $y$ be in $X_L$. We define an order relation by $x < y$ if one or several of the following assertions is satisfied:

275

* $x_0 <_D y_0$,

276

* $x_i = y_i$ for $0 \le i \le k$, $k > 0$, $x_{k+1} <_D y_{k+1}$, an even number of the $x_i$, $0 \le i \le k$, is in $\mathcal{F}$,

277

* $x_i = y_i$ for $0 \le i \le k$, $k > 0$, $x_{k+1} >_D y_{k+1}$, an odd number of the $x_i$, $0 \le i \le k$, is in $\mathcal{F}$,

278

* $x_{-1} <_A y_{-1}$,

279

* $x_i = y_i$ for $k \le i \le -1$, $k < -1$, $x_{k-1} <_A y_{k-1}$, an even number of the $x_i$, $k \le i \le -1$, is in $\mathcal{F}$,

280

281

* $x_i = y_i$ for $k \le i \le -1$, $k < -1$, $x_{k-1} >_D y_{k-1}$, an odd number of the $x_i$, $k \le i \le -1$, is in $\mathcal{F}$.

282

283

284

**Lemma 7.** The order on $X_L$ is total, and every subset $Y$ of $X_L$ admits an upper bound and a lower bound in $X_L$.

285

**Proof**

286

287

For each $n$ we can find a word $y_m^{(n)}$, $-n \le m \le n$, such that $y_m^{(n)}$ is the largest, resp. smallest, element of the set $\{y_m, -n \le m \le n, y \in Y\}$ for the order defined on such words by Definition 3. Then $y_m^{(n+1)} = y_m^{(n)}$ for $-n \le m \le n$ and by definition of $X_L$ there is a sequence $y$ in $X_L$ such that $y^m = y^{(nの}_m$ for $-n \le m \le n$, which will be the desired upper, resp. lower bound. ☐

288

289

290
291

## 2. INTERVAL EXCHANGE TRANSFORMATIONS

A generalized interval exchange transformation is basically a bijection of the unit interval to itself, which is continuous and monotone on a finite number of subintervals which partition the unit interval. However, such maps can be built, by using semi-open intervals of continuity, only when $T$ is increasing on all these intervals. In the *flipped* cases, $T$ will have to stay undefined on a finite set of points.

**Definition 4.** Let $\mathcal{A}$ be a finite alphabet, $\mathcal{F}$ a possibly empty subset of $\mathcal{A}$. An $\mathcal{F}$-flipped generalized interval exchange transformation is a map $T$ defined on a disjoint union of open intervals $I_e$, $e \in \mathcal{A}$, such that the union of their closures is $[0, 1]$, continuous and (strictly) increasing on each $I_e$, $e \in \mathcal{F}^c$, continuous and (strictly) decreasing on each $I_e$, $e \in \mathcal{F}$, and such that the $T I_e$, $e \in \mathcal{A}$, are disjoint open intervals and the union of their closures is $[0, 1]$.

The $I_e$, indexed in $\mathcal{A}$, are called the *defining intervals* of $T$.

If the restriction of $T$ to each $I_e$ is an affine map, $T$ is an $\mathcal{F}$-flipped affine interval exchange transformation.

If the restriction of $T$ to each $I_e$ is an affine map of slope $\pm 1$, $T$ is an $\mathcal{F}$-flipped standard interval exchange transformation.

The endpoints of the $I_e$, resp. $T I_e$, excluding 0 and 1, will be denoted by $\gamma_i$, resp. $\beta_j$, for $i$, resp. $j$, taking $\#\mathcal{A} - 1$ values.

In this definition, the defining intervals $I_e$ are not necessarily the intervals of continuity of $T$, as it may happen that $I_e$ and $I_f$ are adjacent and sent to adjacent intervals with the same flips in the same order, thus $T$ may be extended to a continuous map on their union. Thus in the present paper an interval exchange transformation $T$ is always supposed to be given *together with its defining intervals* as keeping the same $T$ but changing the defining intervals would change the coding.

In all cases, $T$ is undefined on a finite number of points, namely the $\gamma_i$, 0 and 1. In the unflipped cases, $T$ can be extended to $[0, 1)$, resp. $(0, 1]$, by including in each $I_e$ its left (resp. right) endpoint. Also in this case, as did Keane in Section 5 of [27] for unflipped standard interval exchange transformations and Arnoux in Chapter 1 of [2] (Definition 1.4 and Lemma 1.5) for unflipped generalized interval exchange transformations, by carefully doubling the endpoints and their orbits, it is possible to extend $T$ to an homeomorphism on the union of the unit interval and a Cantor set.

Throughout this paper, all defining intervals will be nonempty open intervals. In the unflipped cases, all our results and proofs remain valid if we define $T$ with semi-open intervals, open on the right (resp. left), or define $T$ on Keane's set (mentioned above) and use closed intervals.

**Definition 5.** Let $I$ be the subset (with countable complement) of $(0, 1)$ where all $T^n$, $n \in \mathbb{N}$, are defined. Every statement concerning $T^n$ will be tacitly assumed to be valid if it is valid on $I$.

$T$ is minimal if every orbit is dense.

A wandering interval is an interval $J$ for which $T^J$ is disjoint from $J$ for all $n > 0$.

### 2.1. Codings.

**Definition 6.** For a generalized $\mathcal{F}$-flipped interval exchange transformation $T$, coded by $\mathcal{A}$, its natural coding is the language $L(T)$ generated by all the trajectories, namely the sequences $(x_n, n \in \mathbb{Z}) \in \mathcal{A}^{\mathbb{Z}}$ where $x_n = e$ if $T^n x$ falls into $I_e$, $e \in \mathcal{A}$.

Thus we can look at the symbolic system associated to $L(T)$. Note that the set $X_{L(T)}$ is the closure in $\mathcal{A}^{\mathbb{Z}}$ of the set of trajectories, for the product topology defined by the discrete topology on $\mathcal{A}$.
334 **Example 2.** A Sturmian language is the natural coding of the unflipped standard interval exchange transformation $T$ sending $(0, 1-\alpha)$ to $(\alpha, 1)$ and $(1-\alpha, 1)$ to $(0, \alpha)$ for $\alpha$ irrational; $T$ is conjugate to a rotation of angle $\alpha$ on the 1-torus.

337 **Remark 1.** The elements of $X_{L(T)}$ which are not actual trajectories of points under $T$ are called improper trajectories. For each improper trajectory $u$ in $X_{L(T)}$, either there exists an endpoint $\gamma$ of a defining interval $I_e$, and an integer $l \le 0$ such that $u$ is the limit of the trajectories of $x$ when $x$ tends to $T^l\gamma$, either from the left or from the right, or there exists an endpoint $\beta$ of a $TI_e$, and an integer $l \ge 0$ such that $u$ is the limit of the trajectories of $x$ when $x$ tends to $T^l\beta$, either from the left or from the right.

343 In the unflipped cases, if we define $T$ on Keane's set (as mentioned after Definition 4), each element of $X_{L(T)}$ is an actual trajectory for $T$; if we use semi-open intervals, each element of $X_{L(T)}$ is an actual trajectory, either for $T$ defined and coded with semi-open intervals $[a, b)$, or for $T$ defined and coded with semi-open intervals $[a, b]$, in the same way as Sturmian trajectories in [34].

348 We shall also consider slightly more general codings, by merging into intervals $\tilde{I}_e$ some adjacent intervals $I_e$ whose images by $T$ are also adjacent, and flipped in the same way. This is equivalent to taking the natural coding of another interval exchange transformation $\tilde{T}$, but when $T$ is affine, if we define $\tilde{T}$ by the intervals $\tilde{I}_e$ it will not necessarily be affine by our definition, as the slope is not constant on its defining intervals, see Example 4 below. Thus we define

353 **Definition 7.** A language $L$ is a grouped coding of an $F$-flipped affine interval exchange transformation $T$ if there exist intervals $\tilde{I}_e$, $e \in \tilde{A}$ such that

355 • each $\tilde{I}_e$ is an open interval, and a disjoint union (plus intermediate endpoints) of defining intervals of $T$,

357 • $T$ can be extended by continuity to a continuous monotone map on each $\tilde{I}_e$,

358 • $L$ is the coding of $T$ by the $\tilde{I}_e$, that is the language generated by the trajectories $(x_n, n \in \mathbb{Z}) \in \tilde{A}^{\mathbb{Z}}$ where $x_n = e$ if $T^n x$ falls into $\tilde{I}_e$, $e \in \tilde{A}$.

360 **2.2. Orders.**

361 **Definition 8.** A generalized interval exchange transformation defines two orders on $\mathcal{A}$:

362 • $e <_D f$ whenever the interval $I_e$ is strictly to the left of the interval $I_f$,

363 • $e <_A f$ whenever the interval $TI_e$ is strictly to the left of the interval $TI_f$.

364 These orders correspond to the two permutations used by Kerckhoff [28] to define standard interval exchange transformations: the unit interval is partitioned into semi-open intervals which are numbered from 1 to $k$, ordered according to a permutation $\pi_0$ and then rearranged according to another permutation $\pi_1$; in more classical definitions, there is only one permutation $\pi$, which corresponds to $\pi_1$ while $\pi_0 = \text{Id}$; note that sometimes the orderings are by $\pi_0^{-1}$ and $\pi_1^{-1}$.

369 **Proposition 8.** Let $T$ be a generalized $F$-flipped interval exchange transformation, for $F$ a subset of an alphabet $\mathcal{A}$. Then its language $L(T)$ satisfies an $F$-flipped order condition.

371 **Proof**

372 Let $<_A$ and $<_D$ be the orders from Definition 8.

373 Let $w = w_0 \cdots w_{r-1}$ be a bispecial word in $L(T)$. The cylinder $[w]$ is the interval $I_{w_0} \cap T^{-1}I_{w_1} \cap \cdots \cap T^{-r+1}I_{w_{r-1}}$; after deleting a finite number of points, this interval is partitioned into
<figure><img src="image_2.png" /><figcaption>FIGURE 1. A bispecial interval</figcaption></figure>

the $T[aw] = TI_a \cap [w]$, $a \in A(w)$. As $T[aw] \subset TI_a$ for all $a \in A(w)$, $T[aw]$ is (strictly) left of $T[a'w]$ whenever $a \le_A a'$.

Similarly, after deleting a finite number of points, $[w]$ is also partitioned into the $[wb] = I_{w_0} \cap T^{-1}I_{w_1} \cap \dots \cap T^{-r+1}I_{w_{r-1}} \cap T^{-r}I_b \subset T^{-1}I_{w_1} \cap \dots \cap T^{-r+1}I_{w_{r-1}} \cap T^{-r}I_b$.

The order (from left to right) between two intervals $[b] = I_b$ and $[b'] = I_{b'}$ is the order $<_D$. The order between $TI_{w_{r-1}} \cap I_b \subset I_b$ and $TI_{w_{r-1}} \cap I_{b'} \subset I_{b'}$ is also the order $<_D$. The order between $I_{w_{r-1}} \cap T^{-1}I_b$ and $I_{w_{r-1}} \cap T^{-1}I_{b'}$ is the same order if $T$ is increasing on $I_{w_{r-1}}$ or equivalently $w_{r-1} \in \mathcal{F}^c$, the opposite order otherwise. Similarly the order between $TI_{w_{r-2}} \cap I_{w_{r-1}} \cap T^{-1}I_b \subset I_{w_{r-1}} \cap T^{-1}I_b$ and $TI_{w_{r-2}} \cap I_{w_{r-1}} \cap T^{-1}I_{b'} \subset I_{w_{r-1}} \cap T^{-1}I_{b'}$ is the same as the last one, thus the order between $I_{w_{r-2}} \cap T^{-1}I_{w_{r-1}} \cap T^{-2}I_b$ and $I_{w_{r-2}} \cap T^{-1}I_{w_{r-1}} \cap T^{-2}I_{b'}$ is the same order as the last one if $T$ is increasing on $I_{w_{r-2}}$ or equivalently $w_{r-2} \in \mathcal{F}^c$, the opposite order otherwise. And so on, finally we get that the order between $[wb]$ and $[wb']$ is exactly the order $<_{D,w}$ defined in the second item of Definition 1.

Thus the intervals $T[aw]$ are ordered from left to right by the order $<_A$, while the $[wb]$ are ordered from left to right by the order $<_{D,w}$. The word *awc* exists whenever $T[aw] \cap [wc]$ is nonempty, similarly for *bwd*: as in Figure 1, we get that if *awc* and *bwd* exist, $a \neq c$, $b \neq d$, then $a <_A c$ iff $b <_{D,w} d$. Note that this is true also for the empty word, which is bispecial and for which no letter is in $\mathcal{F}$. Thus $L(T)$ does satisfy the $\mathcal{F}$-flipped order condition defined by $\le_A$ and $\le_D$. $\square$

**Remark 2.** By the same reasoning as in Proposition 8, we check that if $(x_n, n \in \mathbb{Z})$ in $X_{L(T)}$ is the (actual or improper) trajectory of some point $x$, $(y_n, n \in \mathbb{Z})$ in $X_{L(T)}$ is the (actual or improper) trajectory of some point $y$, $(x_n, n \in \mathbb{Z}) \le (y_n, n \in \mathbb{Z})$ for the order of Definition 3 if and only if $x \le y$ in the natural order on $(0, 1)$.

**Remark 3.** The language of an interval translation mapping [6] does not necessarily satisfy an $\mathcal{F}$-flipped order condition: it is possible that $TI_a$ intersects $TI_b$ for $a \neq b$, and, if $TI_a \cap TI_b$ intersects both $I_c$ and $I_d$, $c \neq d$, then the empty word is a locally strong bispecial, which contradicts the local order condition by Lemma 1.

**Question 1.** How to characterize the natural codings of systems of piecewise isometries, resp. interval translation mappings ?

Even for the latter family, almost nothing is known. Their complexity is the object of a question of Boshernitzan; it was proved to be linear in some particular cases by Cassaigne (unpublished).
We continue the study of languages satisfying order conditions, or weaker properties, by looking at *recurrence*. Recurrence and uniform recurrence of a language are defined in Section 1.1 above. A different concept is the recurrence of infinite sequences, which is a property of the associated symbolic dynamical system.

**Definition 9.** A bi-infinite sequence $x$ in $A^Z$, or an infinite suffix of it, is right recurrent if any factor $w$ of $x$ is equal to $x_{n_k}...x_{n_k+t}$ for a sequence $n_k$ tending to $+\infty$.

A bi-infinite sequence $x$ in $A^Z$, or an infinite prefix of it, is left recurrent if any factor $w$ of $x$ is equal to $x_{n_k}...x_{n_k+t}$ for a sequence $n_k$ tending to $-\infty$.

A bi-infinite sequence $x$ in $A^Z$ is recurrent if it is both left and right recurrent.

**Lemma 9.** Suppose $L$ has no strong bispecial word.

If an infinite suffix of a sequence in $X_L$ is right recurrent, it generates a uniformly recurrent language.

If an infinite prefix of a sequence in $X_L$ is left recurrent, it generates a uniformly recurrent language.

If a sequence in $X_L$ is left or right recurrent, it is recurrent and generates a uniformly recurrent language.

**Proof**

Let $w$ be any word in $L$; we look at the possible *return words* of $w$, namely words $v \neq w$ having $w$ as a prefix and as a suffix, but as no other subword. Extending $w$ from the left, before seeing $w$ as a suffix, there are several possible paths; bifurcations correspond to right special words of the form $wv$; by Lemma 5 these correspond to suffixes of $K$ infinite prefixes of sequences in $X_L$. If there are more than $K$ bifurcations, some $wv_1$ and $wv_2$ are different suffixes of the same infinite prefix; thus there is an occurrence of $w$ in the shortest suffix which is not the initial occurrence, thus we have already returned to $w$ before the bifurcation; hence we cannot see more than $K$ bifurcations, with at most $K'$ choices for each one, before returning to $w$. Thus there are at most $K'K$ return words of $w$.

If $x$ is right recurrent, as any prefix of $x$ occurs further to the right, the set of its factors is a language $L'$. For each factor $w$ of $x$, we see it infinitely many times, with at most $KK'$ ways of going from one occurrence to the next one. Thus we see $w$ in $x$ infinitely many times with bounded gaps, thus $w$ occurs in any long enough factor of $x$, and $L'$ is uniformly recurrent. And the same works for left recurrence.

Now, suppose for example $x \in X_L$ is right recurrent. Then it is also left recurrent: otherwise there exists a factor $w$ of $x$ which does not occur in $(x_n, n \le k)$; thus there exists arbitrarily long factors $v_{(m)}$ of $x$ with no occurrence of $w$; but then any infinite suffix of $x$ contains every $v_{(m)}$, and thus cannot generate an uniformly recurrent language. Hence any factor $w$ occurs in $x$ at infinitely many places to the right and to the left, and with bounded gaps, thus the language generated by $x$ is uniformly recurrent. $\square$

It will result from Proposition 12 that, under a local order condition, the recurrence of $L$ implies the recurrence of every sequence in $X_L$; here we prove first a weaker statement.
Lemma 10. Suppose $L$ has no locally strong bispecial, and is recurrent. Then if $w'w^n$ is in $L$ for all $n \in \mathbb{N}$, with $|w'| \le |w|$, then $w'$ is a suffix of $w$, and if $w^n w'$ is in $L$ for all $n$, then $w'$ is a prefix of $w$.

Proof 451

Suppose first $w'w$ is a non-initial factor of some $w'w^m$; then either $w'$ occurs as a suffix of $w$, or we have $w = w_1...w_l = w_{d+1}...w_l w_1...w_d$ for some $0 < d < l$; in the latter case, we get that $w = vv...v$ for a factor $v$ of length $p = d \wedge l$, and that $w'$ is a factor of $ww$ ending at index $d$ or $l-d$, and this factor is also a suffix of $w$.

Suppose $w'w^n$ is in $L$ for all $n$, and $w'$ is not a suffix of $w$. By recurrence, for each $n \ge 1$ $w'w^n$ must occur after $w'w^n$. As it cannot occur as a non-initial factor of some $w'w^N$, then for each $n \ge 1$ there is a right special word which is a prefix of some $w'w^N$ and has $w'w^n$ as a prefix; for infinitely many $p_n$, it will be of the form $w'w^{p_n}w_1$, for a fixed prefix $w_1$ of $w$, and followed by two fixed letters $b$ and $b'$. If $w_2$ is the longest common suffix of $w$ and $w'$, we get four different words of the form $aw_1w^{p_n}w_2b$, and thus a locally strong bispecial. And similarly for the second assumption. $\square$

462

Lemma 11. A finite or countable union of uniformly recurrent languages satisfies the measure condition: there exists an invariant probability measure $\mu$ on the symbolic system $(X_L, S)$ associated to $L$ such that $\mu[w] > 0$ for any $w \in L$.

Proof 466

Assume $L$ is a uniformly recurrent language and let $\mu$ be any invariant probability measure on the symbolic system $(X_L, S)$ associated to $L$. Such a measure $\mu$ can be constructed as in [5]. Fix $w$ in $L$. Then, for each positive integer $N$ there is at least one word $w_1$ of length $N$ with $\mu[w_1] > 0$, and, as $w$ is a factor of $w_1$ if $N$ is large enough, $[w_1]$ is included in $\bigcup_{i=0}^N S^i[w]$ from which it follows that $\mu[w] > 0$.

If $L$ is a finite or countable union of uniformly recurrent languages $L_i$, then each $L_i$ satisfies the measure condition for some measure $\mu_i$, and hence $L$ will satisfy the measure condition for any average of the measures $\mu_i$. $\square$

475

**Proposition 12.** Let $L$ be a recurrent language satisfying a local order condition. Then $L$ is a finite union of uniformly recurrent languages.

Proof 478

The Rauzy graph $G_1$ has at most $k$ connected components. The language $L$ restricted to any connected component of any of its Rauzy graphs $G_n$ still satisfies the local order condition. We apply repeatedly Lemma 6 to any of these languages: if $G_{n+1}$ has more connected components than $G_n$, then there exists a connected component $C_n$ of $G_n$ such that the Rauzy graph $C_{n+1}$ made with the edges of $C_n$ is not connected. Thus there is an edge missing in $C_{n+1}$ as in Lemma 3, and it cannot be elsewhere in $G_{n+1}$, thus this edge is missing in $G_{n+1}$ and there is a weak bispecial word in $L$ by the reasoning of Lemma 3. By Lemma 2 this happens a finite number of times, thus for $n$ large enough $G_n$ has at most $N$ connected components, and $L$ is a union of $N$ languages for which all Rauzy graphs are connected.

488

Suppose there is a word $w$ in $L$ for which no left extension is left special. Then, before $w = w_0 \cdots w_l$, we can see only one sequence of letters, denoted by $w_n$, $n < 0$. As $L$ is recurrent, $w$ must occur as some $w_s \dots w_t$, $s < t < 0$, thus the sequence $(w_n, n < 0)$ begins with a periodic infinite
prefix ... vvv. For any *m* large enough, this gives a loop in the Rauzy graph *G*<sub>*m*</sub>; it is impossible
492
493 both to enter this loop from any other point in *G*<sub>*n*</sub> and to exit from it to any other point in *G*<sub>*n*</sub>,
494 otherwise this contradicts Lemma 10. Thus the language generated by ... vvv corresponds to a full
495 connected component of *G*<sub>*m*</sub> for all *m* large enough, thus there are at most *N* such languages. Thus
496 *L* is the union of at most *N* languages satisfying the local order condition, where each language
497 either is generated by the *v*<sup>*n*</sup>, *n* ≥ 0, for a word *v*, or contains only words which can be extended
to a left special word.
498

Let $L'$ be one of these last languages, if they exist. Let $G_n'$ be its Rauzy graphs. Because there is
no strong bispecial word in $L'$, by Lemma 5 all left special words in $L'$ are prefixes of $K$ infinite
suffixes $W_i$; as every word of $L'$ can be extended to a left special, all the words of $L'$ are the factors
of the $W_i$.
500
501
502

Let *w* be a word of *L*': *w* must be a suffix of infinitely many words of *L*', because every word of
*L'* can be extended infinitely many times to the left; thus *w* occurs infinitely often in at least one
*W*<sub>*i*</sub>; hence all the prefixes of *W*<sub>*i*</sub> occur infinitely often in at least one *W*<sub>*j*</sub>, and if *j* ≠ *i*, then we can
drop *W*<sub>*i*</sub> and use only the other *W*<sub>*j*</sub> to generate *L*'. Thus, after a renumbering of the *W*<sub>*i*</sub>, *L*' is the
union of the languages *L*(*W*<sub>*i*</sub>), 1 ≤ *i* ≤ *q* ≤ *K*, where the *W*<sub>*i*</sub> are right recurrent infinite suffixes.
503
504
505
506
507
508

Then by Lemma 9 each $L(W_i)$ is uniformly recurrent, while any of language generated by the
$v^n$, $n \ge 0$, is also uniformly recurrent. $\square$
509
510
511

We can now prove our first main theorem, which we guess might also be deduced from understanding and rewriting the criterion of [25].
512
513

**Theorem 13.** For a language *L* on an alphabet *A* and *F* ⊂ *A*, the following are equivalent:

• (i) *L* satisfies an *F*-flipped order condition and is recurrent;

• (ii) *L* is the language of a standard *F*-flipped interval exchange transformation;

• (iii) *L* is the language of a generalized *F*-flipped interval exchange transformation without wandering intervals.
515
516
517
518

Proof
***

If *L* satisfies (i), by Proposition 12 and Lemma 11, *L* satisfies the measure condition of Lemma 11. We prove now that it implies (ii); this is indeed the same reasoning as in Proposition 4 of [17], modified to take into account flips and connections.
520
521
522
523

Let $\mu$ be as in the measure condition. Let $\mathcal{A} = L_1$, and let $T$ be the standard $\mathcal{F}$-flipped interval
524
525 exchange transformation defined by intervals $I_e, e \in \mathcal{A}$, of respective length $\mu[e]$ ordered from left
526 to right by the order $<_D$, while the $TI_e, e \in \mathcal{A}$, of respective length $\mu[e]$, are ordered from left to
527 right by the order $<_A$, and $T$ has slope 1 on the $I_e, e \in \mathcal{F}^c$, and slope $-1$ on the $I_e, e \in \mathcal{F}$.
528

Let $L' = L(T)$, $\mu'$ the shift-invariant measure on $X_{L'}$ defined by the Lebesgue measure on $(0, 1)$.
529

We prove inductively on *n* that *w* ∈ *L*<sub>*n*</sub> if and only if *w* ∈ *L*'<sub>*n*</sub>, and for these words *μ*[*w*] = *μ*'[*w*].
530
531
This is true for *n* = 1 by our choice of *T*. We denote by *A*<sub>*L*</sub>, *A*<sub>*L*</sub>'*, *D*<sub>*L*</sub>, *D*<sub>*L*</sub>' the arrival and departure
sets in *L* and *L*'.
532

Let the hypothesis be proved for *n*, and take a word *w* in *L* of length *n* − 1 (possibly the empty
one if *n* = 1. Because of the induction hypothesis, *A*<sub>*L*</sub>(*w*) = *A*<sub>*L*</sub>'(*w*), *D*<sub>*L*</sub>(*w*) = *D*<sub>*L*</sub>'(*w*), as they
depend only on *L*<sub>*n*</sub> and *L*'<sub>*n*</sub>.
533
534
If $w$ is not right special, $D_L(w)$ is made with a single letter $a$, and every word $xw$ is always
followed by $a$, thus $xwa$ is in $L$ if and only if $xw$ is in $L$, with $\mu[xwa] = \mu[xw]$; because of our in-
duction hypothesis, all this remains true with “prime” signs added. Thus our hypothesis is carried
over to all $awb$, for $a$ and $b$ letters. And similarly if $w$ is not left special.

539

Suppose now that $w$ is bispecial in $L$ (hence also in $L'$).

Let $A_L(w) = \{a_1, \dots, a_p\}$, in the $<_A$ order, and $D_L(w) = \{b_1, \dots, b_q\}$ in the $<_{D,w}$ order defined in the second item of Definition 1. Then what we shall show is that the situation is analogous to Figure 1 above.

Starting from the left, $D_L(a_1w)$ must contain $b_1$, otherwise $D_L(a_1w)$ contains some $b >_D b_1$,
while $A_L(wb_1)$ contains some $a >_A a_1$, $a_1wb$ and $awb_1$ exist, this contradicts the order condition.
Then $a_1wb_1$ is in $L$, and

• if $\mu[a_1w] \le \mu[wb_1]$, then, as $\mu$ gives positive measure to every cylinder, $D_L(a_1w)$ is reduced to the element $b_1$ and thus $\mu[a_1wb_1] = \mu[a_1w]$,

• if $\mu[a_1w] > \mu[wb_1]$, then $D_L(a_1w)$ contains also another element than $b_1$, thus it must
contains $b_2$, otherwise $a_1wb$ and $awb_2$ exist for some $b >_{D,w} b_2$ and $a >_A a_1$; hence
$A(wb_2)$ contains $a_1$, $A(wb_1)$ cannot contain $a >_A a_1$, thus is reduced to the element $a_1$ and
$\mu[a_1wb_1] = \mu[wb_1]$.

552

Thus $\mu[a_1wb_1] = \min(\mu[a_1w], \mu[wb_1]) > 0$; similarly, because of the definition of $L'$, $a_1wb_1$ is
in $L'$, and, using our induction hypothesis, we get

$$
\mu'[a_1 w b_1] = \min(\mu'[a_1 w], \mu'[w b_1]) = \min(\mu[a_1 w], \mu[w b_1]) = \mu[a_1 w b_1].
$$

Suppose we have proved that $a_rwb_s$ is in $L$ iff it is in $L'$, and $\mu[a_rwb_s] = \mu'[a_rwb_s]$, for every
$r \le i$, and $s \le j$; suppose that $a_iwb_j$ is in $L$ and $L'$, with $i < p$ or $j < q$.

Suppose first that $\sum_{r=1}^{i} \mu[a_r w] > \sum_{s=1}^{j} \mu[wb_s]$; then $j < q$ and $\cup_{r=1}^{i} D_L(a_r w)$ contains strictly $\{b_1, \dots, b_j\}$, thus by the order condition $D_L(a_i w)$ contains $b_{j+1}$, thus $a_iwb_{j+1}$ is in $L$ while $a_{i+1}wb_j$ is not in $L$. And we have again two cases:

• if $\sum_{r=1}^{i} \mu[a_r w] > \sum_{s=1}^{j+1} \mu[wb_s]$, then by the order condition $A_L(wb_{j+1})$ is reduced to the element $a_i$, thus $\mu[a_iwb_{j+1}] = \mu[wb_{j+1}]$,

• if $\sum_{r=1}^{i} \mu[a_r w] < \sum_{s=1}^{j+1} \mu[wb_s]$, then by the order condition $D_L(a_i w)$ contains (at least) the two elements $b_j$ and $b_{j+1}$, and either $\mu[a_iwb_{j+1}] = \sum_{r=1}^{i} \mu[a_r w] - \sum_{s=1}^{j} \mu[wb_s]$, or $\mu[a_iwb_{j+1}] = \sum_{s=1}^{j+1} \mu[wb_s] - \sum_{r=1}^{i} \mu[a_r w]$, according to which of these two quantities is positive.

But then $\sum_{r=1}^{i} \mu'[a_r w] > \sum_{s=1}^{j} \mu'[wb_s]$, and the same analysis applies to $L'$, thus we get the
same conclusions with “prime” signs added; as all estimates depend only on properties of words
of length $n$, we use our induction hypothesis to get $\mu'[a_iwb_{j+1}] = \mu[a_iwb_{j+1}]$, and our induction
hypothesis is carried to $i$ and $j+1$.

In the opposite case where $\sum_{r=1}^{i} \mu[a_r w] < \sum_{s=1}^{j} \mu[wb_s]$, then $i < p$, $a_iwb_{j+1}$ is not in $L$ while
$a_{i+1}wb_j$ is in $L$, and a similar reasoning applies, carrying our induction hypothesis to $i+1$ and $j$.

If $\sum_{r=1}^{i} \mu[a_r w] = \sum_{s=1}^{j} \mu[wb_s]$, then there is a connection. Then $i < p, j < q$, by the reasoning above $\mu[a_iwb_{j+1}] = \mu[a_{i+1}wb_j] = \mu'[a_iwb_{j+1}] = \mu'[a_{i+1}wb_j] = 0$ and the words $a_iwb_{j+1}$ and $a_{i+1}wb_j$ are not in $L$ and $L'$. This carries our induction hypothesis both to $i+1$ and $j$ and to $i$ and $j+1$.
574
575

In all cases our induction hypothesis is carried to all awb, for a and b letters, and is now proved for all words of length $n + 1$.

576

577
578

(ii) implies (iii), as a standard interval exchange transformation cannot have a wandering interval as it preserves the Lebesgue measure.

579

580
581
582

(iii) implies the $\mathcal{F}$-flipped order condition by Proposition 8. It implies recurrence as if a word $w$ of $L(T)$ is such that there is no $v \neq w$ beginning and ending with $w$, then the cylinder $[w]$ is a wandering interval. □

583

584
585
586

**Theorem 14.** Let $L$ be a language on an alphabet $\mathcal{A}$ and $\mathcal{F} \subset \mathcal{A}$. Then $L$ is the language of a generalized (resp. standard) $\mathcal{F}$-flipped minimal interval exchange transformation if and only if it is aperiodic, uniformly recurrent, and satisfies an $\mathcal{F}$-flipped order condition.

587
588
589

**Proof**

590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612

For any language $L$, the minimality of the system $(X_L, S)$ is equivalent to the uniform recurrence of $L$, see for example [38] ch 5.

If $T$ is an $\mathcal{F}$-flipped interval exchange transformation, $L(T)$ satisfies the required order condition by Proposition 8. If $T$ is minimal, $T$ has no periodic point, as finite orbits cannot be dense, thus $L(T)$ is aperiodic. The minimality of $T$ implies the minimality of $X_{L(T]}$ as arbitrarily long cylinders correspond to arbitrarily small intervals, thus $L(T)$ is uniformly recurrent.

In the other direction, we apply Theorem 13 to get a standard interval exchange transformation for which $L = L(T)$. $(X_L, S)$ is minimal, thus $T$ can be not minimal only if arbitrarily long cylinders do not correspond to arbitrarily small intervals. This happens only if an infinite trajectory $u = u_0 \cdots u_n \cdots$ corresponds to an interval $J$ in $(0, 1)$. But either $T^k u = u$ for some $k > 0$, which is excluded by aperiodicity, or else for all $k > 0$ $T^k J$ is disjoint from $J$ as they are in two disjoint cylinders; but this is excluded as $T$ is a standard interval exchange transformation, preserving the Lebesgue measure. □

Both Theorem 13 and Theorem 14 should be compared with the characterizations in [25]. A particular case of Theorem 14 is proved in [17], Theorem 2, for unflipped standard interval exchange transformations. It uses a modified version of the i.d.o.c. condition introduced by Keane [27]; in the present context, this condition we use can be stated as: there is at least one point $\gamma_i$ (of Definition 4), and there is no $i, j, k \ge 0$, such that $T^k \beta_i = \gamma_j$. Note that this condition depends on the defining intervals, and is not intrinsic to $T$ as the original Keane's condition. The i.d.o.c. condition could be generalized to flipped standard interval exchange transformations, but, to our knowledge, this has never been done, and it is not clear that any non-trivial example could satisfy it, as among flipped standard interval exchange transformations, the minimal ones constitute a small [36] albeit non-empty [35] set

Now we can restate our old theorem in a cleaner form.

613
614
615

**Theorem 15.** A language $L$ on at least two letters is the language of a standard unflipped interval exchange transformation satisfying the i.d.o.c. condition if and only if it satisfies an unflipped order condition, is aperiodic and uniformly recurrent, and has no connection.
This can be deduced from the present Theorem 14 by noticing that our i.d.o.c. condition implies Keane's one and thus minimality, and that for a minimal standard interval exchange transformation, our i.d.o.c. condition is just the absence of connections in $L(T)$.

Note that minimal generalized interval exchange transformation cannot have wandering intervals; this can also be proved by using the above results: by minimality the existence of a wandering interval for $T$ implies the existence of a wandering cylinder for the shift on $(X_{L(T)}, S)$, and this contradicts the measure condition for $L(T)$.

### 4. GENERALIZED INTERVAL EXCHANGE TRANSFORMATIONS

We turn again to the study of languages satisfying an order condition or a weaker property: we are now interested in non-recurrent elements of $X_L$.

**Lemma 16.** Suppose $L$ has no strong bispecial word. Let $x$ be in $X_L$. There exists $m$ such that the infinite prefix $(x_n, n \le -m)$ is left recurrent and the infinite suffix $(x_n, n \ge m)$ is right recurrent.

**Proof**

Suppose for all $m \ge m_0$ the infinite suffix $(x_n, n \ge m)$ is not right recurrent. Then for such $m$ there exists a word $w^{(m)}$ which occurs exactly once in $(x_n, n \ge m)$. As there is a finite number of letters, by going to a subsequence we can suppose all the $w^{(m)}$ begin by the same letter, and thus this letter occurs infinitely often in $(x_n, n \ge m_0)$. Thus the longest prefix of $w^{(m)}$ which occurs at least twice in $(x_n, n \ge m)$ is a nonempty $v^{(m)}$; then $v^{(m)}$ is right special, and, by applying Lemma 5 and going to a subsequence, we can suppose $v^{(m)}$ is a suffix of a fixed infinite prefix, and also that the letter following $v^{(m)}$ in $w^{(m)}$ is a fixed $a$. Now we can find $m < m'$ such that $v^{(m')}$ is not shorter than $v^{(m)}$, thus $v^{(m')}$ contains $v^{(m)}$, $v^{(m')}$ contains $v^{(m)}$, thus $v^{(m)}$ occurs in $(x_n, n \ge m')$, which contradicts the assumption that $v^{(m)}$ is the longest possible. And similarly for the other assumption. $\square$

**Proposition 17.** Suppose $L$ has no strong bispecial word. Then there are at most a finite number of orbits of $S$, namely sets $\{S^n x, x \in X_L\}$, such that $x$ is not recurrent.

**Proof**

If $x$ is not recurrent, then some $(x_n, n \ge k)$ is not right recurrent. Let $k$ be the largest of these $m$: it is finite by Lemma 16, and necessarily the infinite suffix $(x_n, n \ge k+1)$ has at least two left extensions. Thus $(x_n, n \ge k+1)$ is one of the finitely many infinite suffixes $W_i$ of Lemma 5. If $(x_n, n \ge l)$ is one of the $W_i$ for a sequence $l \to -\infty$, then it is the same $W_i$ by going to a subsequence, thus $x$ is periodic and hence recurrent. Thus there is a smallest $m = m_0$ such that $(x_n, n \ge m)$ is one of the $W_i$, thus for $m < m_0$ there is only one left extension for $(x_n, n \ge m)$, and the sequence $x$ is known (up to shifts) if we know $W_i$. As there are finitely many $W_i$, this give finitely many orbits. $\square$

**Lemma 18.** Let $L$ be a non-recurrent language satisfying an $F$-flipped order condition. We denote by $L'$, on $A' \subset A$, the language generated by all the recurrent sequences in $X_L$. $L'$ is nonempty, recurrent, satisfies an $F'$-flipped order condition for osme $F' \subset F$, and the orders defined on $X_L$ and $X_{L'}$ coincide on $X_{L'}$.
**Proof**

L' is not empty as there are recurrent sequences in $X_L$: indeed, by Lemma 16, there are always
right recurrent infinite suffixes $(x_n)$, $n \ge k$ and these can be extended to the left as for each $m \ge k$
the word $x_{k-1}\dots x_m$ occurs somewhere to the right, thus for some letter $x_{k-1}$ the word $x_{k-1}x_1\dots x_m$
occurs in $(x_n)$, $n \ge k$ for infinitely many $m$, hence for all $m \ge k$. Thus we get a right recurrent
infinite suffix $(x_n)$, $n \ge k-1$, and by iterating the process we get a recurrent bi-infinite sequence
$(x_n, n \in \mathbb{Z})$.

The other assertions are immediate as $L'$ is recurrent by construction and satisfies a restriction
of the order condition on $L$. □

**Theorem 19.** A language *L* is a natural coding of an *F*-flipped generalized interval exchange transformation iff *L* satisfies an *F*-flipped order condition.

**Proof**

The “only if” direction is Proposition 8. We suppose now *L* satisfies an *F*-flipped order condition.
We suppose also that *L* is not recurrent, otherwise we can conclude by Theorem 13. Let *L'* be as
in Lemma 18.

Let $z$ be in $X_L \setminus X_{L'}$; by Lemma 7 if the set $Z^- = \{t \in X_{L'}; t \le z\}$ and $Z^+ = \{t \in X_{L'}; t \ge z\}$ are nonempty, $Z^+$ has a unique lower bound $z^+ \in X_{L'}$ and $Z^-$ has a unique upper bound $z^- \in X_{L'}$; in that case, $z^+ > z^-$, otherwise $z$ would be in $X_{L'}$. If $\{t \in X_{L'}; t \le z\}$ is empty, we define $z^- = z^+$ to be the minimum of $X_{L'}$, and if $\{t \in X_{L'}; y \ge z\}$ is empty, we define $z^+ = z^-$ to be the maximum of $X_{L'}$.

We apply Theorem 13 to find a standard interval exchange transformation $T'$, coded by $A'$, such
that $L' = L(T')$. $T'$ is not necessarily unique, we choose one. By Remark 1, every sequence in
$X_{L'}$ is either the trajectory of a point $x$ under $T'$, or an improper trajectory associated to a point $x$;
$x$ is not unique for periodic sequences, but for a given sequence the set of possible $x$ is an interval.
For $z$ in $X_{L'} \setminus X_L$, if $z^- < z^+$, there is no $t$ in $X_{L'}$ between them, this is possible only if $z^+$ and $z^-$
are two improper trajectories associated to the same point $x$; then $x$ is unique as it is the rightmost
point of the interval associated to $z^-$ and the leftmost point of the interval associated to $z^+$, and
we call it $p(z)$. If $\{t \in X_{L'}; t \le z\}$ is empty, we define $p(z)$ to be the leftmost point in the domain
of $T'$, namely 0, and if $\{t \in X_{L'}; t \ge z\}$ is empty, we define $p(z)$ to be the rightmost point in the
domain of $T'$, namely 1. In all cases, for a given $z$, for $|m|$ large enough $(S^m z)^- = (S^m z)^+$, which
implies $p(S^{m+1}z) = T'p(S^m z)$.

By Proposition 17 and its proof, there are finitely many orbits in $X_L \setminus X_{L'}$; we describe them
as $S^n z_{(i)}$, $n \in \mathbb{Z}$, $1 \le i \le K$, where $z_{(i)}$ is chosen so that $(z_{(i)m}, m \le 0)$ is left recurrent but
$(z_{(i)m}, m \le 1)$ is not left recurrent. We can do the same reasoning in both directions, thus $z_{(i)} =$
$y_{(i)} w_{(i)} y'_{(i)}$ for an infinite prefix $y_{(i)}$ of a sequence in $X_{L'}$, an infinite suffix $y'_{(i)}$ of a sequence in
$X_{L'}$, a (possibly empty) finite word $w_{(i)}$ in $L$; we know also that $y_{(i)} = (z_{(i)m}, m \le 0)$, but $y'_{(i)}$ is
not necessarily the first left recurrent infinite suffix of $z_{(i)}$ as the latter might begin at a negative
coordinate.

We look at the possible $S^n z_{(i)}$ such that $p(S^n z_{(i)})$ is a given point: this is a possibly infinite
subset of $X_L$, we show that it has at most finitely many accumulation points for the usual topology:
indeed, any accumulation point is a limit of points in the same orbit; if $p(S^n z_{(i)}) = p(S^{n'} z_{(i)})$ for
$n \ne n'$, then $y'_{(i)}$ is periodic, equal to $vvv\dots$, $y_{(i)}$ is periodic, equal to $\dots v'v'v'$, and on this orbit
there are at most finitely many accumulation points, which are the iterates by $S$ of ...vvv... and
...v$v$v$v'$...

Thus for any given $x$ in $p(X_L \setminus X_{L'})$, all the $S^n z_{(i)}$ such that $p(S^n z_{(i)}) = x$ can be ordered (by the order on $X_{L'})$ in a sequence $\zeta_n(x)$, $n \in H(x)$, $H(x)$ being a finite or countable set. We now blow up $x$ to a closed interval $\hat{J}(x)$ which is divided into adjacent open intervals $J(\zeta_n(x))$, ordered from left to right by the growing order on $\zeta_n(x)$, where the length of $J(\zeta_n(x))$ is $2^{-|m|}$ if $\zeta_n(x) = S^m z_{(i)}$.

Namely, for $x$ in $p(X_L \setminus X_{L'})$, let $l(x)$ be the sum on $n \in H(x)$ of the lengths of $J(\zeta_n(x))$; $l(x)$ is finite; for $x$ in $(0, 1)$ and not in $p(X_L \setminus X_{L'})$, we put $l(x) = 0$. For all $x$ in $(0, 1)$, we define $\phi(x) = \sum_{y \in p(X_L \setminus X_{L'}) , y < x} l(y)$, this last sum being also finite; let $M = 1 + \phi(1) + l(1)$. Then we send each point $x$ in $(0, 1)$ to the interval (possibly reduced to a point) $\hat{J}(x) = [x + \phi(x), x + \phi(x) + l(x)];$ for $l(x) \neq 0$ we divide $\hat{J}(x)$ into $J_{\zeta_n(x)}$ as described above; the image of $(0, 1)$ by this Denjoy-type blow-up [13] [24] is $[0, M]$. On this interval we define $T$ by sending in an affine way $J(S^m z_{(i)})$ onto $J(S^{m+1} z_{(i)})$ for all $m$ and $i$, with a negative slope whenever $z_{(i)m}$ is in $\mathcal{F}$. If both $x$ and $T'x$ are not in $p(X_L \setminus X_{L'})$, we define $T(x+\phi(x)) = T'x + \phi(T'x)$. This leaves $T$ or $T^{-1}$ undefined on some points corresponding to $x$ where $T'$ or $T'^{-1}$ is undefined, on the endpoints of the $J(S^m z_{(i)})$ and finitely many images by $T^m$ of these endpoints. but also to $x$ (resp. $T'x$) not in $p(X_L \setminus X_{L'})$ but such that $T'x$ (resp. $x$) is in $p(X_L \setminus X_{L'})$; the latter case will happen only for finitely many points, and then the trajectory under $T'$ of either $x$ or $T'^x$ is some improper trajectory $(S^{m+1} z_{(i)})^+$ or $(S^{m+1} z_{(i)})^-$. Finally, we put in the interval $I_e, e \in \mathcal{A}$, all points $x+\phi(x)$ for $x$ not in $p(X_L \setminus X_{L'})$ such that $x$ is in the defining interval $I'_e$ of $T'$, and all the $J(S^m z_{(i)})$ for which $e = z_{(i)m}$. By the above considerations, all trajectories for $T'$ remain as actual or improper trajectories for $T$.

Because we have respected the order, $T$ is indeed a generalized interval exchange transformation with the required orders and $\mathcal{F}$, and its language is indeed $L$, as the sequences in $X_L$ are the actual or improper trajectories for $T$. $\square$

**Remark 4.** The blow-up we made in the above proof sends points $x$ to intervals $[x + \phi(x), x + \phi(x) + l(x)]$, while [8] [7] [11] [31] use intervals $[\phi(x), \phi(x) + l(x)]$ instead; the latter kind of blow-up is needed to build affine $T$, but two different points $x$ and $x'$ may be sent to the same point, though this will not happen if $T'$ is minimal as then between two different points there is always some $p(z)$, while in the former case the blow-up is always injective but does not produce affine interval exchange transformations. In the proof of Theorem 20 below we shall use a mixture of these two.

We shall see how this proof works on Examples 4 of Section 6.2 and 9 of Section 6.4.

## 5. AFFINE INTERVAL EXCHANGE TRANSFORMATION

**Theorem 20.** If $L$ is a natural coding of an $\mathcal{F}$-flipped affine interval exchange transformation for which the absolute value of the slope is $\exp \theta_e$ on the defining interval $I_e$, then $L$ satisfies an $\mathcal{F}$-flipped order condition and for each non recurrent sequence $z$ in $X_L$, $\sum_{n \ge 0} \exp \sum_{j=0}^n \theta_{z_j} < +\infty$, and $\sum_{n \ge 0} \exp - \sum_{j=-n}^{-1} \theta_{z_j} < +\infty$.

If $L$ satisfies an $\mathcal{F}$-flipped order condition and there exist real numbers $\theta_e, e \in \mathcal{A}$, such that for each non recurrent sequence $z$ in $L$, $\sum_{n \ge 0} \exp \sum_{j=0}^n \theta_{z_j} < +\infty$, and $\sum_{n \ge 0} \exp - \sum_{j=-n}^{-1} \theta_{z_j} < +\infty$, then $L$ is a group coding of an $\mathcal{F}$-flipped affine interval exchange transformation.
744 Proof

745 Let $z$ be a non recurrent sequence. Let $L'$ be as in the proof of Theorem 19. As $z$ is not recurrent,
746 $z$ cannot have all its words in the same uniformly recurrent component (of Proposition 12) of $L'$,
747 and thus not all its words in $L'$. Thus we can find a word $w = w_1...w_k$ which is not in $L'$ and ap-
748 pears only once in $z$; by Lemme 16 it will appear only finitely many times in each of the other non
749 recurrent sequences, and by Lemma 17 we can extend it so that it appears only in $z$ and its shifts.
750 Thus the cylinder $[w]$ is disjoint from all its iterates by $T$, and for the Lebesgue measure $\mu$ both
751 $\sum_{n \ge 0} \mu(T^n[w])$ and $\sum_{n \ge 0} \mu(T^{-n}[w])$ must be finite. Suppose $w = z_k...z_{k+k'}$; then $T$ is of slope
752 $\exp \theta_{z_k}$ on $[w]$, $\exp \theta_{z_{k+1}}$ on $[Tw]$, $\exp \theta_{z_{k-1}}$ on $T^{-1}[w]$ and so on, thus $\mu(T[w]) = \exp \theta_{z_k} \mu[w]$,
753 $\mu(T^2[w]) = \exp \theta_{z_{k+1}} \mu(T[w])$, $\mu([w]) = \exp \theta_{z_{k-1}} \mu(T^{-1}[w])$ and so on. Our conditions come
754 from replacing $k$ by 0, which amounts to multiplying by a constant.
755
756 We start now from $L$ and build a generalized interval exchange transformation $T$, as in the proof
757 of Theorem 19, but with two modifications.
758
759 First, the length we assign to the interval $J(S^m z_{(i)})$ is 1 for $m = 0$, then is defined such that
760 $J(S^m z_{(i)})$ is sent to $J(S^{m+1} z_{(i)})$ by an affine map of slope $\exp \theta_{z_{(i)m}}$ if $z_{(i)m}$ is in $\mathcal{F}^c$, $-\exp \theta_{z_{(i)m}}$
761 if $z_{(i)m}$ is in $\mathcal{F}$.
762 Second, when we make the blow-up of $(0,1)$ to the domain of $T$, we replace the map $x \to
763 $\phi(x) + x$ by the map $x \to \phi(x) + 1_K(x)x$ for some union of intervals $K$. To find $K$, we apply the
764 proof of Proposition 12 to the recurrent language $L'$: for some fixed $N$ large enough, its Rauzy
765 graph $G_N$ splits into a finite number of connected components, corresponding to languages which
766 either come from one purely periodic orbit or are aperiodic and uniformly recurrent. This implies
767 that there exist a finite number of $T'$-invariant sets $K_j$, which are finite unions of cylinders of
768 length $N$, and such that, on each $K_j$, either $T'$ is minimal, or every point is periodic (note that this
769 reproves Corollary 2.9 of [2], and extends it to flipped interval exchange transformations).
770 Now, for each $i$, we look at those points $p(S^m z_{(i)})$, $|m| \ge m_i$, where $m_i$ is chosen such that
771 $p(S^{m+1} z_{(i)}) = T' p(S^m z_{(i)})$, and let $K^c$ be the union of those $K_j$ which contain
772 at least one $p(S^{m_i} z_{(i)})$ or $p(S^{-m_i} z_{(i)})$ in their closure. If $x \ne x'$, our construction ensures that $x$
773 and $x'$ are blown-up into different points, unless maybe if $x$ and $x'$ belong to the same connected
774 $K'$ of the same $K_i$: in the latter case either minimality implies that there is at least one
775 $J(S^m z_{(i)})$ between their images, in which case again $x$ and $x'$ are blown-up into different points,
776 or periodicity implies that $x$ and $x'$ have the same trajectory, and this trajectory is not lost in the
777 blow-up as it remains as the improper trajectory of some endpoint of $K'$. Thus again all trajectories
778 for $T'$ remain as actual or improper trajectories for $T$.
779 The map $T$ built in this way is a generalized $\mathcal{F}$-flipped interval exchange transformation with
780 defining intervals $I_e$. By the same proof as in [8] [7] [11] [31], if the set $K$ in $(0,1)$ is blown up to
781 $\hat{K}$, $T$ is affine of slope $\exp \theta_e$ (resp. $-\exp \theta_e$ if $e$ is in $\mathcal{F}$) on each connected component of $I_e \cup \hat{K}^c$,
782 while each connected component of $I_e \cup \hat{K}$ is the union of finitely many $J(S^m z_{(i)})$, on which $T$ is
783 affine of slope $\exp \theta_e$ (resp. $-\exp \theta_e$ if $e$ is in $\mathcal{F}$) and finitely many intervals on which $T$ is affine
784 of slope 1 (resp. $-1$ if $e$ is in $\mathcal{F}$). Thus by dividing the intervals further we can make $T$ affine with
785 constant slope on its defining intervals, and $L$ is a grouped coding of an affine interval exchange
786 transformation. $\square$

758 First, the length we assign to the interval $J(S^m z_{(i)})$ is 1 for $m = 0$, then is defined such that
759 $J(S^m z_{(i)})$ is sent to $J(S^{m+1} z_{(i)})$ by an affine map of slope $\exp \theta_{z_{(i)m}}$ if $z_{(i)m}$ is in $\mathcal{F}^c$, $-\exp \theta_{z_{(i)m}}$
760 if $z_{(i)m}$ is in $\mathcal{F}$.
761 Second, when we make the blow-up of $(0,1)$ to the domain of $T$, we replace the map $x \to
762 $\phi(x) + x$ by the map $x \to \phi(x) + 1_K(x)x$ for some union of intervals $K$. To find $K$, we apply the
763 proof of Proposition 12 to the recurrent language $L'$: for some fixed $N$ large enough, its Rauzy
764 graph $G_N$ splits into a finite number of connected components, corresponding to languages which
765 either come from one purely periodic orbit or are aperiodic and uniformly recurrent. This implies
766 that there exist a finite number of $T'$-invariant sets $K_j$, which are finite unions of cylinders of
767 length $N$, and such that, on each $K_j$, either $T'$ is minimal, or every point is periodic (note that this
768 reproves Corollary 2.9 of [2], and extends it to flipped interval exchange transformations).
769 Now, for each $i$, we look at those points $p(S^m z_{(i)})$, $|m| \ge m_i$, where $m_i$ is chosen such that
770 $p(S^{m+1} z_{(i)}) = T' p(S^m z_{(i)})$, and let $K^c$ be the union of those $K_j$ which contain
771 at least one $p(S^{m_i} z_{(i)})$ or $p(S^{-m_i} z_{(i)})$ in their closure. If $x \ne x'$, our construction ensures that $x$
772 and $x'$ are blown-up into different points, unless maybe if $x$ and $x'$ belong to the same connected
773 component $K'$ of the same $K_i$: in the latter case either minimality implies that there is at least one
774 $J(S^m z_{(i)})$ between their images, in which case again $x$ and $x'$ are blown-up into different points,
775 or periodicity implies that $x$ and $x'$ have the same trajectory, and this trajectory is not lost in the
776 blow-up as it remains as the improper trajectory of some endpoint of $K'$. Thus again all trajectories
777 for $T'$ remain as actual or improper trajectories for $T$.
778 The map $T$ built in this way is a generalized $\mathcal{F}$-flipped interval exchange transformation with
779 defining intervals $I_e$. By the same proof as in [8] [7] [11] [31], if the set $K$ in $(0,1)$ is blown up to
780 $\hat{K}$, $T$ is affine of slope $\exp \theta_e$ (resp. $-\exp \theta_e$ if $e$ is in $\mathcal{F}$) on each connected component of $I_e \cup \hat{K}^c$,
781 while each connected component of $I_e \cup \hat{K}$ is the union of finitely many $J(S^m z_{(i)})$, on which $T$ is
782 affine of slope $\exp \theta_e$ (resp. $-\exp \theta_e$ if $e$ is in $\mathcal{F}$) and finitely many intervals on which $T$ is affine
783 of slope 1 (resp. $-1$ if $e$ is in $\mathcal{F}$). Thus by dividing the intervals further we can make $T$ affine with
784 constant slope on its defining intervals, and $L$ is a grouped coding of an affine interval exchange
785 transformation. $\square$

779 The map $T$ built in this way is a generalized $\mathcal{F}$-flipped interval exchange transformation with
780 defining intervals $I_e$. By the same proof as in [8] [7] [11] [31], if the set $K$ in $(0,1)$ is blown up to
781 $\hat{K}$, $T$ is affine of slope $\exp \theta_e$ (resp. $-\exp \theta_e$ if $e$ is in $\mathcal{F}$) on each connected component of $I_e \cup \hat{K}^c$,
782 while each connected component of $I_e \cup \hat{K}$ is the union of finitely many $J(S^m z_{(i)})$, on which $T$ is
783 affine of slope $\exp \theta_e$ (resp. $-\exp \theta_e$ if $e$ is in $\mathcal{F}$) and finitely many intervals on which $T$ is affine
784 of slope 1 (resp. $-1$ if $e$ is in $\mathcal{F}$). Thus by dividing the intervals further we can make $T$ affine with
785 constant slope on its defining intervals, and $L$ is a grouped coding of an affine interval exchange
786 transformation. $\square$

<figure><img src="image_3.png" /></figure>
**Corollary 21.** If $L$ satisfies an $\mathcal{F}$-flipped order condition and $X_L$ contains some non-recurrent sequences, a sufficient condition for $L$ to be a natural coding of an $\mathcal{F}$-flipped affine interval exchange transformation is that

• there exist real numbers $\theta_e, e \in A$, such that for each non recurrent sequence $z$ in $L$, $\sum_{n \ge 0} \exp \sum_{j=0}^n \theta_{z_j} < +\infty$, and $\sum_{n>0} \exp - \sum_{j=-n}^{-1} \theta_{z_j} < +\infty$,

• each factor of a recurrent sequence in $X_L$ is also a factor of a non-recurrent sequence in $X_L$.

**Proof**

With the notations of the proof of Theorem 20, the last condition implies that in the closure of every $K_j$ there is at least one $p(S^{m_i} z_{(i)})$ or $p(S^{-m_i} z_{(i)})$, thus $K$ is empty and there is no subinterval of $I_e$ on which $T$ is affine of slope $1 \ne \exp \theta_e$ or $-1 \ne -\exp \theta_e$, which ensures that $L$ is the natural coding of $T$. $\square$

This criterion will be further discussed in Section 6.3 below.

We can get a criterion for $L$ to be a grouped coding of an affine interval exchange transformation by essentially rephrasing Theorem 20.

**Definition 10.** Suppose $L$ satisfies an $\mathcal{F}$-flipped order condition. A language $\hat{L}$ is a splitting of $L$ if its letters are $e_i$, $e \in A$, $1 \le i \le k_e$, forming the set $\hat{A}$, such that $L = \phi(\hat{L})$ where we define $\phi(e_i) = e$ for all $e$ and $i$, and extend $\phi$ to a morphism for the concatenation on words, and $\hat{L}$ satisfies an $\hat{\mathcal{F}}$-flipped order condition, where

• $\hat{\mathcal{F}}$ is made of all the $e_i$ such that $e$ is in $\mathcal{F}$,

• if $e$ is in $\mathcal{F}^c$, $e_1, \dots, e_{k_e}$ are consecutive and ordered in the same way by the orders $<_A$ and $<_D$ of $\hat{L}$,

• if $e$ is in $\mathcal{F}$, $e_1, \dots, e_{k_e}$ are consecutive and ordered in opposite ways by the orders $<_A$ and $<_D$ of $\hat{L}$,

• if $e \le_A e'$, resp. $e \le_D e'$ in $L$, then $e_i \le_A e'_j$, resp. $e_i \le_D e'_j$, in $L'$ for all $i$ and $j$,

**Theorem 22.** $L$ is a group coding of an $\mathcal{F}$-flipped affine interval exchange transformation if and only $L$ satisfies an $\mathcal{F}$-flipped order condition and there exists a splitting $\hat{L}$ of $L$, and real numbers $\theta_e, e \in \hat{A}$, such that for each non recurrent sequence $z$ in $X_{\hat{L}}$, $\sum_{n \ge 0} \exp \sum_{j=0}^n \theta_{z_j} < +\infty$, and $\sum_{n>0} \exp - \sum_{j=-n}^{-1} \theta_{z_j} < +\infty$.

**Proof**

In one direction, we suppose $L$ is a grouped coding of $T$ affine, define $\hat{L}$ to be the natural coding of $T$ and apply Theorem 20. In the other direction, we start from $\hat{L}$ and use Theorem 20 to build an affine interval exchange transformation $T$ such that $\hat{L}$ is a grouped coding of $T$. But then $L = \phi(\hat{L})$ is a further grouped coding of $T$. $\square$

## 6. COUNTER-EXAMPLES AND QUESTIONS

### 6.1. Affine with natural coding.

**Example 3.** Let $L$ be generated by the bi-infinite sequence ... 111222.... Note that it is of complexity $n + 1$ but not uniformly recurrent, and in the founding paper [34] it is not included in
Sturmian languages, we can call it a fake Sturmian language. It satisfies the unflipped order condition with $1 <_D 2$, $1 <_A 2$, but (unsurprisingly as it is not recurrent) is not the language of a standard interval exchange transformation as that could only be the identity on two disjoint open intervals $I_1$ and $I_2$, and the only possible words are $1^n$ and $2^m$. However, $L$ is the natural coding of an affine interval exchange transformation: $L_2$ is the language of length 2 of any affine 2-interval exchange transformation, with the same orders, such that $TI_1$ is strictly longer than $I_1$, and, as $L$ is determined by $L_2$ because there is no bispecial word except the empty one, $L$ is indeed the natural coding of any of these affine interval exchange transformations.

Example 3 can also be dealt with as in Theorem 20, with $T'$ being the identity acting on $I_1$ and $I_2$.

Because of Theorem 20 and Corollary 21, if we want to build nontrivial examples of affine interval exchange transformation with a non recurrent language $L$ as a natural coding, we can just use [8] [7] [11] [31]: starting from a minimal standard interval exchange transformation $T'$, we find a point $x_*$ and a map $\theta$ constant on the defining intervals such that the Birkhoff sums $\sum_{j=0}^n \theta(T'^j x_*)$ and $\sum_{j=-1}^n \theta(T'^j x_*)$ behave as we need, then make a blow-up of all points in the orbit of $x_*$, and get an affine $T$ with a non-recurrent trajectory using an extra letter as in Example 9; note however that, because of the order condition, $x_*$ must be an endpoint of a defining interval of $T'$; if $x_*$ is not already such an endpoint, we can make it one with a modification of $T'$, by splitting the interval $I'_e$ containing $x_*$ into $I'_e \cap (0, x_*)$ and $I'_e \cap (x_*, 1)$. We can also get examples by blowing up two half-orbits, of two points $x_*$ and $x'_*$ so that the Birkhoff sums $\sum_{j=0}^n \theta(T'^j x_*)$ and $\sum_{j=-n}^{-1} \theta(T'^j x'_*)$ behave as we need, provided we then modify $T'$ so that $x_*$ and $x'_*$ are endpoints of defining intervals; this is always possible if $T'$ is minimal but non uniquely ergodic, as we can find two invariant measures $\nu$ and $\nu'$ and a vector $\theta$ so that $\sum \theta_e \nu(I_e) < 0$, $\sum \theta_e \nu'(I_e) > 0$, and then choose $x_*$ generic for $\nu$, $x_*$ generic for $\nu'$. But if $T'$ is uniquely ergodic, then we need $\sum \theta_e \nu(I_e) = 0$ for the invariant measure $\nu$, and, by [23], for any given $\theta$ the set of $x$ such that $\sum_{j=0}^n \theta(T'^j) \to -\infty$ or $\sum_{j=-1}^n \theta(T'^j x) \to +\infty$ is of measure 0.

## 6.2. Affine with grouped coding.

**Example 4.** Let $L$ the language generated by the bi-infinite sequence ...1112111..., which is a skew Sturmian language as defined in [34]. It satisfies the unflipped order condition with $1 <_D 2$, $2 <_A 1$, but is not the natural coding of any affine interval exchange transformation $T$: indeed, the sequence ...1111... in $X_L$ would define a fixed point $x$ for $T$, in the interior of [1], and, if $0 < y < x$ is the right endpoint of $T[2]$, $T$ would have to send $(0, x)$ to $(y, x)$ and $(x, 1-y)$ to $(x, 1)$, thus having a slope < 1 on a part of [1] and a slope > 1 on another part. However, if $\tilde{L}$ is the language generated by the bi-infinite sequence ...3332111..., as in Example 3 $\tilde{L}$ is the natural coding of any affine interval exchange transformation $T$ sending $I_1 = (0, x)$ to $(y, x)$, $I_3 = (x, 1-y)$ to $(x, 1)$, $\tilde{I}_2 = (1-y, 1)$ to $(0, y)$, with $0 < y < x < 1-y$. If we now code $T$ by the intervals $\tilde{I}_1 = I_1 \cup I_3$ and $\tilde{I}_2 = I_2$, we see that $L$ is indeed a grouped coding of an affine interval exchange transformation as in Definition 7.

We show how the proof of Theorem 19 works on Example 4. $L'$ is the language generated by the single sequence $y = ...111...$, and thus $T'$ is the identity acting on $I_1 = (0, 1)$. In the single non recurrent orbit ...11211..., $z$ is the point for which $z_0 = 2$, and we have $Sz < S^2z < S^3z < ... < y < z < ...S^{-3}z < S^{-2}z < S^{-1}z < z$, with $y$ being the limit of the $S^n z$ when $n \to \pm\infty$. Thus $p(S^n z) = 1$ for all $n \le 0$, $p(S^n z) = 0$ for all $n \ge 1$; our construction gives an affine interval exchange transformation $T$ sending $(0, 1)$ to $(1/2, 1)$, $(1, 2)$ to itself, $(2, 3)$ to $(2, 4)$, $(3, 4)$
to $(0, 1/2)$, while the cylinder $[1]$ is the interval $(0, 3)$ and the cylinder $[2]$ is the interval $(3, 4)$. $L$ is the natural coding of $T$ if we consider it as a generalized interval exchange transformation, but is only a grouped coding of an affine interval exchange transformation, as remarked above. Note that the fact that $T$ is affine is a (conceivably) accidental result of our choices of the lengths of the added intervals, see the proof of Theorem 20, and that the present map $T$ is slightly different from the one of Example 4; the latter could be obtained from the former by collapsing the interval $(1, 2)$, as in the second blow-up of Remark 4 (this is possible though $T'$ is not minimal because all the points in $(1, 2)$ have the same trajectory, ..., 1111..., and this will remain, as an improper trajectory, after the collapsing).

**6.3. Natural versus grouped.**

**Conjecture 1.** The conditions in Theorem 20 are necessary and sufficient for $L$ to be a natural coding of an $\mathcal{F}$-flipped affine interval exchange transformation.

Indeed, the last condition of Corollary 21 is satisfied if $T'$ is minimal, but also by Example 3 above. But this condition is *not necessary*, for different reasons shown in the following three examples, most significantly Example 7.

**Example 5.** Let $L$ be the language generated by the two infinite sequences ...111222... and ...3333... Then $K$ is a union of defining intervals of $T'$, so the grouped coding of Theorem 20 turns out to be a natural coding.

**Example 6.** Let $L$ be generated by ...121312131213... and ...114114114115115115... Then $K$ is nonempty and not a union of defining intervals, but an allowed value of $\theta_1$ is 0, and 1 is the only $e$ for which $I'_e$ contains strictly a connected component of $K$, thus again the proof of Theorem 20 provides a natural coding.

**Example 7.** Let $L$ be generated by ...332332331331... and ...413241324132...; then either $\theta_1 \neq 0$ or $\theta_2 \neq 0$, hence the proof of Theorem 20 would yield an interval exchange transformation with two different slopes, $1$ and $\exp\theta_e$, on $I_e$ for $e = 1$ or $e = 2$, thus $L$ is not the natural coding of any affine interval exchange transformation built by the proof of Theorem 20. However, $L$ is the natural coding of another affine interval exchange transformation, namely any member of the family defined by the orders $1 <_D 2 <_D 3 <_D 4$ and $4 <_A 3 <_A 1 <_A 2$, slopes $a$ on $I_1$, $1/a$ on $I_2$, $1$ on $I_3$ and $I_4$, and lengths $|I_1| = l+r$, $|I_2| = a(l+r)$, $|I_3| = al+2(a+1)r$, $|I_4| = l$, for any given $0 < a < 1$, $l > 0$ and $r > 0$.

The only example we know of a grouped coding which is not a natural coding is Example 4, which does not satisfy the condition on Birkhoff sums: whatever the value of $\theta_1$ and $\theta_2$, either the $\exp n\theta_1$, $n \ge 0$, or the $\exp n\theta_1$, $n < 0$, must be bounded away from 0 (while for the language $\tilde{L}$ of Example 4 we can take $\theta_1 < 0$ and $\theta_3 > 0$).

**Question 2.** Does there exist an aperiodic language which is a grouped coding of an affine interval exchange transformation, but not a natural coding of any affine interval exchange transformation?

Questions 1 and 2 suggest what we dare not call a conjecture.

**Question 3.** Is it true that $L$ is a group coding of an $\mathcal{F}$-flipped affine interval exchange transformation if and only if $L$ satisfies an $\mathcal{F}$-flipped order condition and there exist real numbers $\theta_e, e \in \mathcal{A}$, such that the two following conditions hold?
912

913

914

915

• For each non recurrent sequence z in L which is not ultimately periodic to the left,
$\sum_{n \ge 0} \exp \sum_{j=0}^{n} \theta_{z_j} < +\infty$.

• For each non recurrent sequence z in L which is not ultimately periodic to the right,
$\sum_{n>0} \exp - \sum_{j=-n}^{-1} \theta_{z_j} < +\infty$.

916

917

918

919

920

921

922

923

**Remark 5.** As in the last example above, the same language can be a coding of two fairly differ-
ent affine interval exchange transformations. In particular, Sturmian languages are languages of
standard interval exchange transformations, thus also of affine interval exchange transformations
without wandering intervals. It is known since [34] that if we want to generate a given Sturmian
language L by a standard 2-interval exchange transformation, the parameter $\mu[I_2]$ has two possi-
ble values, or one up to reversal of the orientation. If we want the interval exchange transformation
to be affine, we have two parameters, for example its slopes a and b on $I_1$ and $I_2$, and we do not
know which amount of freedom we have in this case.

924

925

**Question 4.** For a given L, what can be said of the set of (a, b) for which L is the language of the
corresponding affine interval exchange transformation?

926

927

About this question, it is worth mentioning a surprising example due to M. Shannon (unpub-
lished):

928

929

930

**Example 8.** One can build (by geometrical methods) a grouped coding of an affine interval ex-
change transformation $T$ which is a Sturmian language, associated to a rotation of angle $\alpha$, but
while $\alpha$ is in $\mathbb{Q}(\sqrt{3})$, all the parameters defining $T$ are in $\mathbb{Q}(\sqrt{5})$.

931

6.4. Generalized.

932

933

934

935

936

937

938

939

**Example 9.** Let $L'$ be the Sturmian language which is the natural coding of the unflipped standard
interval exchange transformation $T'$ sending $I_1 = (0, 1 - \alpha)$ to $(\alpha, 1)$ and $I_2 = (1 - \alpha, 1)$ to $(0, \alpha)$
for an irrational $\alpha < 1/2$. Let $y_n = i$ whenever $T^n \alpha$ is in $I_i$, $n \ge 0$, and $y'_n = i$ whenever $T^n(1 -$
$2\alpha)$ is in $I_i$, $n \le 0$; when $\alpha = \frac{3-\sqrt{5}}{2}$, $y$ is the so-called Fibonacci sequence on 1 and 2, and $y'$ is $y$
written backwards. Let $L$ be the language generated by the infinite sequence ...$y'_{-2}y'_{-1}y'_03y_0y_1y_2...$
It satisfies the unflipped order condition with $1 <_D 3 <_D 2$, $2 <_A 3 <_A 1$ (note that no other
unflipped order is possible, because of the way the empty bispecial is resolved, nor is any flipped
order because of the way the bispecial 0 is resolved).

940

941

942

943

By Theorem 19 L is the natural coding of a generalized interval exchange transformation, but
it is not the natural or grouped coding of any affine interval exchange transformation: this will be
a straightforward consequence of either one of two independent results we show below, Theorems
23 and Theorem 24.

944

945

946

947

948

949

950

951

952

953

Example 9 is a typical case to see how the proof of Theorem 19 works. Then $L'$ and $T'$ are
as described in its definition. Then the only not right recurrent orbit in $X_L$ is the one of $y'3y$
defined above. There is one $z$, the element of this orbit such that $z_0 = 3$. Because of the order
condition, the defining interval $I_3$ of $T$ must be between $I_1$ and $I_2$, and $TI_3$ between $TI_2$ and $TI_1$;
this implies that $p(z) = 1 - \alpha$ and $p(Tz) = \alpha$. And indeed $z^+$ is the element of the orbit $y'12y$
such that $z_0^+$ is the 1 just after $y'$, $z^-$ is the element of the orbit $y'21y$ such that $z_0^-$ is the 2 just
after $y'$; similarly $(Tz)^+$ is the element of the orbit $y'21y$ such that $(Tz)^+_{-1}$ is the 1 just before $y$,
$(Tz)^-$ is the element of the orbit $y'12y$ such that $(Tz)^-_{-1}$ is the 2 just before $y$. As there is no other
discontinuity $p(T^n z) = T'^{n-1}\alpha$ for $n \ge 1$, $p(T^{-n}z) = T'^{-n}(1 - \alpha)$ for $n \ge 1$. Thus we make the
above construction by replacing each point $T^m\alpha$, $m \ge 0$, by an interval $\hat{J}(T^m\alpha)$ of length $2^{-m-1}$,
the point $1 - \alpha$ by an interval $\hat{J}(1 - \alpha)$ of length 1, each point $T^{-m}(1 - 2\alpha)$, $m \ge 0$, by an interval
$\hat{J}(T^{-m}(1 - 2\alpha))$ of length $2^{-m-1}$.

956

**Theorem 23.** Let $L$ be non recurrent, and a natural coding of an unflipped generalized interval ex-
change transformation $T$. Suppose the language $L'$ of Lemma 18 is aperiodic, uniformly recurrent,
and its arrival and departure order are conjugate by a circular permutation. Then $T$ cannot be of
class P, class $P$ [24] meaning that, except on a countable set of points, $DT$ exists and $DT = h$
where $h$ is a function with bounded variation, and $|h|$ is bounded from below by a strictly positive
number.

963

Proof

A sequence in $X_L$ can be a trajectory for $T$ (actual or improper) either of a single point or of all
points in an interval; the intervals which correspond to a single trajectory include those coded by
non-recurrent trajectories, but possibly others; as intervals corresponding to different trajectories
are all disjoint, there are at most countably many of them; let $E_n, n \in \mathbb{Z}$, be these intervals.
We build another interval exchange transformation $\hat{T}$ on the interval $(0, 1)$ by making a deblow-
up: this will be done in two different ways corresponding to the inverses of the two blow-ups in
Remark 4. If $\sum_{n \in \mathbb{Z}} \mu(E_n) < 1$, $\mu$ being the Lebsegue measure, we just shrink each $E_n$ (including
its endpoints) to a single point, by sending $x$ to $x - \mu(]0, x[ \cup \cap_{n \in \mathbb{Z}} E_n)$, sending $(0, 1)$ to a smaller
interval, which we rescale to get $(0, 1)$. If $\sum_{n \in \mathbb{Z}} \mu(E_n) = 1$, we use the semi-conjugacy of [8] [7]
[11] [31]: let $x_n$ be the left end of $E_n$; the condition on the lengths of $E_n$ implies the $x_n$ are dense
in $(0, 1)$; then we send to $x_n$ all points in $E_n$, while a point $x$ which is not im any $E_n$ is sent to
the unique (by density of the $x_n$) point $x'$ such that $\sum_{x_n < x'} \mu(E_n) = x$. In both cases all intervals
coded by non-recurrent trajectories are shrunk to single points, and $\hat{T}$ has no wandering interval.
Then the natural coding of $\hat{T}$ is the language $L'$, as every recurrent trajectory of $T$ remains as an
actual or improper trajectory of $\hat{T}$, while non-recurrent trajectories of $T$ are not trajectories of $\hat{T}$.

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

By construction, each trajectory in $X_{L'}$ is the (actual or improper) trajectory under $\hat{T}$ of one
point in $(0, 1)$, and also the (actual or improper) trajectory under $T'$ of one point in $(0, 1)$. By
Remark 2 the order on $X_{L'}$, whether we consider trajectories of $T'$ or $\hat{T}$, corresponds to the natural
order on $(0, 1)$, thus we can make a bijective, continuous and increasing map $\psi$ from $(0, 1)$ to $(0, 1)$
such that $\psi \circ \hat{T} = T' \circ \psi$.

985

986

987

988

989

990

991

Suppose $T$ is of class P. Let $J$ be a wandering interval for $T$; then we have $\mu(T^n J) = \mu(J) \exp \sum_{j=0}^{n-1} \theta_j$
where $\exp \theta_j$ is the average value of $DT$ on $T^j J$. If $h$ is the function defining class $P$, we
define a function $\theta$, by $\theta(x) = \log h(x)$ when $x$ is not in any $E_n$, while, for any $x$ in $E_n$,
$\theta(x)$ is the logarithm of the average value of $h$ on $E_n$. Then the measures of $T^n J$ are given
by for $n > 0$, $\mu(T^n J) = \mu(J) \exp \sum_{j=0}^{n-1} \theta(T^j x)$ for some point $x$ in $J$, while for $n < 0$,
$\mu(T^n J) = \mu(J) \exp - \sum_{j=n}^{-1} \theta(T^j x')$ for some point $x'$ in $J$. As $J$ is a wandering interval, $\mu(T^n J)$
tends to 0 when $n$ goes to $\pm\infty$.

992

993

994

995

996

997

The deblow-up sends Birkhoff sums of $\theta$ under $T$ to Birkhoff sums of a function $\hat{\theta}$ under $\hat{T}$, thus
by the hypothesis these are Birkhoff sums of a measurable function under an irrational rotation,
and, as in the case of a natural coding, because of the unique ergodicity, we must have $\int \hat{\theta} d\mu = 0$
for the Lebesgue measure. The properties of $h$ imply that the function $\theta$ has bounded variation,
thus so does $\hat{\theta}$; but then by the Denjoy-Koksma inequality [24] the Birkhoff sums are bounded on
a subsequence corresponding to the denominators of the partial quotients of the angle, and we get
a contradiction.

999

☐

The above theorem applies to Example 9 or any example built in the same way from any Sturmian word, but also, in contrast with Theorem 24 or Corollary 26 below, we may equip $T'$ with extra points $\gamma_i$ which are not discontinuities, giving extra possibilities for building $L$. All these give counter-examples of languages which are natural codings of a generalized interval exchange transformation, but not natural codings of any generalized interval exchange transformation of class P, and thus not grouped codings of any affine interval exchange transformation.

1006

**Theorem 24.** Let $L'$ be a natural coding of a non purely periodic unflipped standard interval exchange transformation. Let $w_n = av_n b$, $a \in A$, $b \in A$, be an infinite sequence of bispecial words in $L'$. Let $u$ be the infinite prefix in $X_{L'}$ ending with $w_n$ for all $n$, and $v$ the infinite suffix beginning with $w_n$ for all $n$. Let $\omega$ be a symbol which is not a letter of $L'$, and $L$ be the language generated by the union of all words in $L'$ and the bi-infinite word $u\omega v$.

Then $L$ is a natural coding of a generalized interval exchange transformation, but not a grouped coding of any affine interval exchange transformation.

## Proof

We build a generalized interval exchange transformation with natural coding $L$ as in the proof of Theorem 19, by adding a point coded by $\omega$ at position $\gamma$, where $T'^{-|w_n|}\gamma$ is in $[w_n]$ for all $n$, and its image at position $\beta$, where $\beta$ is in $[w_n]$ for all $n$, and making a Denjoy-Koksma blow-up.

1018

Suppose $L$ is a grouped coding of an affine interval exchange transformation $T$. Let $\exp\theta(x)$ be the slope of $T$ at point $x$, $\theta$ is piecewise constant with $K \ge 0$ jumps. As $[\omega]$ is a wandering interval, we can write the $T^j[\omega]$ as a (Rokhlin) tower, in which each discontinuity of $\theta$ appears at most once. Thus $[\omega]$ is partitioned into at most $K+1$ disjoint intervals, on which for any $n > 0$ $\sum_{j=-n}^{-1} \theta(T^jx)$ and $\sum_{j=0}^{n} \theta(T^jx)$ are constant; we choose one of these subintervals, which is also a wandering interval, and call $Q_{-n}$ and $Q_n$ the respective value of these sums on it; when $n \to +\infty$, $Q_{-n} \to +\infty$ and $Q_n \to -\infty$.

We look now at the induced (or first return) map of $T$ on the interval $[w_n]$, for fixed $n$. By the standard reasoning of [27], this interval is partitioned into $R$ subintervals $J_{i,n}$, which are the bases of $R$ disjoint Rokhlin towers made with disjoint intervals $J_{i,n}$, ... $T^{h_{i,n}-1}J_{i,n}$, and then $T^{h_{i,n}}J_{i,n}$ is in $[w_n]$. The levels $T^lJ_{i,n}$ are in the defining interval corresponding to the $l+1$-th letter of the word $w_n$, and their union for fixed $l$ is an interval for $l \le h'_n - 1$, where $h'_n = \min_i h_{i,n}$. Among these towers, there is one for which $h_{i_0,n} = |w_n| + 1$ and $T^{h_{i_0,n}-1}[w_n]$ is in $[\omega]$. All the others are coded by orbits of $T'$, and $h'_n \to +\infty$ when $n \to +\infty$, otherwise the $w_n$ would be in a periodic orbit, which is impossible as they are bispecial.

1034

As $\omega$ is always followed by $w_n$, there is a subinterval of $[w_n]$ on which $\sum_{j=-1}^{l-1} \theta(T^jx) = Q_l$ for all $l \le h'_n$.

For fixed $n$, each discontinuity of $\theta$ appears at most once in the union of towers of bases $J_{i,n}$, and all these towers are adjacent from levels 0 to $h'_n - 1$; thus, for two different points $x$ and $x'$ in $[w_n]$ the values of $\theta(T^jx)$ and $\theta(T^jx')$ are different for at most $K$ distinct values of $j$ between 0 and $h'_n - 1$. Thus, taking also into account the replacement of $T^{-1}x$ by $T^l x$, there exists a constant $M$ such that for all $n$, all $l < h'_n$, all $x$ in $[w_n]$, $Q_l - M < \sum_{j=0}^l \theta(T^jx) < Q_l + M$.

1036

1037

1038

1039

1040

1041
As $\omega$ is always preceded by $w_n$, there is a subinterval of $J_{i_0,n}$ on which $\sum_{j=0}^{h_{i_0,n}-2} \theta(T^j x) = Q_{-h_{i_0,n}+1}$. This implies that $Q_{-h_{i_0,n}+1}$ is between $Q_{h_{i_0,n}-2} - M$ and $Q_{h_{i_0,n}-2} + M$ for all $n$, which is a contradiction because of their behaviour when $n \to +\infty$. $\square$

1045

This gives us many counter-examples, of natural codings of a generalized interval exchange transformation which are not grouped codings of any affine interval exchange transformation, including Example 9 for completely different reasons as the ones in Theorem 23, but for a given $T'$ a priori we cannot use all possible positions to add an interval $[\omega]$, nor can we create new points $\gamma_i$ as possible positions.

6.5. **Geometric.** In an intermediate case between the rotations of Theorem 23 and the general systems of Theorem 24, we give counter-examples which are not natural codings of an affine interval exchange transformation, starting from some famous $T'$, in which we can use all possible positions $\gamma_i$ to add an interval, but not create new points $\gamma_i$ as possible positions.

We construct examples with nice properties arising from exotic translation surfaces. We refer to [19] for an introduction on translation surfaces and their moduli spaces. The *Eierlegende Wollmilch Sau* and the *Ornithorynque* are square-tiled surfaces with remarquable properties. The Eierlegende Wollmilch Sau is described in Figure 2. In both cases, the Veech group of the translation surface is equal to $SL(2, \mathbb{Z})$. We consider $\phi$ a pseudo-Anosov homeomorphism in the affine group. When $\phi$ fixes a separatrix, using Veech's zippered rectangles method (see [41] or [42]), one can construct a self-similar interval exchange transformation $S$ acting on a transversal of the expanding foliation of $\phi$. We will call such interval exchange transformation a self-similar EW-interval exchange transformation (resp. self-similar Or-interval exchange transformation).

**Theorem 25.** Let $S$ be a self-similar EW-interval exchange transformation (resp. self-similar Or-interval exchange transformation) and $S'$ an affine interval exchange transformation semi-conjugate to $S$, then $S'$ is topologically conjugate to $S$. In particular, $S'$ has no wandering interval.

1067

**Proof**

<figure><img src="image_4.png" /><figcaption>FIGURE 2. The Eierlegende Wollmilch Sau EW.
The gluings of the squares follow the action of the quaternion group.
Multiplication by $i$ defines the square on the right, by $j$ the square on
top.</figcaption></figure>

We make the proof when the surface is the Eierlegende Wollmilch Sau, denoted by EW. It is
exactly similar for the Ornithorynque.

The interval exchange $S$ is a 9-interval exchange transformation defined on an interval $I$. The
intervals of continuity of $T$ are denoted by $I_1, \dots, I_9$. We consider the function $f$ from $I$ to $\mathbb{R}$ with
value at $x$, the logarithm of the slope of the affine interval exchange transformation $T'$ at $x$. The function $f$ is constant on the intervals of continuity of $T$ and is orthogonal to the lengths vector of the intervals of $S$ (see [8]). In other words, $f$ can be also considered as a vector belonging to a co-dimension one subset of $\mathbb{R}^9$. It is enough to prove that, for every $x$ there exist two sequences of positive integers $(n_i)$ and $(m_i)$ and a constant $C$ such that

$$ (1) \qquad \sum_{j=0}^{n_i} |f(S^j(x)| < C \quad \text{and} \quad \sum_{j=-m_i}^{0} |f(S^j(x)| < C. $$

This trivially implies that

$$ \sum_n \exp\left(\sum_{j=0}^n f(S^j(x))\right) $$

and

$$ \sum_n \exp\left(\sum_{j=-n}^0 f(S^j(x))\right) $$

are divergent series which contradicts the existence of wandering intervals and prove the topological conjugacy between $S$ and $S'$ (see [8] or [11]).

We now give some geometric background. The EW is a surface of genus 3 with 4 singularities. We recall that the real dimension of the relative homology with real coefficients $H_1(EW, \Sigma, \mathbb{R})$ is 9. That's related to the fact that $S$ is a 9-interval exchange transformation. The subspace, $H_1^{(0)}(EW, \Sigma, \mathbb{R})$, made of homology classes with zero holonomy has dimension 7. Since this surface is a covering of the torus, the homology of the surface splits over $\mathbb{Q}$ into the standard part that comes from the homology of the torus and the space $H_1^{(0)}(EW, \Sigma, \mathbb{R})$. The action of the affine group on $H_1^{(0)}(EW, \Sigma, \mathbb{R})$ is an action by a finite group (see [33] for precise definitions and a very detailed combinatorial approach to this problem). Let $\phi$ be the pseudo-Anosov homeomorphism from which $S$ is built. The result of Matheus and Yoccoz implies that $\phi$ acts on $H_1^{(0)}(EW, \Sigma, \mathbb{R})$ as an element of finite order.

In plain terms, the action of $\phi$ on the relative homology is given by a matrix $B$ (a loop in the Rauzy diagram). From the work of Zorich [43] and Forni [18], we know that the action of $\phi^*$ is responsible for the deviations of ergodic sums at special times of $T$. By construction $f$ is orthogonal to the Perron-Frobenius eigenvector of $B$. Thus $f$ is contained in the space generated by the contracting eigendirection of $B^t$ and its central space. We can forget the projection of $f$ on the contracting direction since it does not change the study of Birkhoff sums (see [11] for instance). Thus, up to taking some power of $\phi$ and considering the projection of $f$ on the central space, we can assume that $B^t f = f$.

We consider the sequence $I^{(p)}$ of intervals on which the induced map $S^{(p)}$ is similar to $S$. Let $C_1^{(p)}, \dots, C_9^{(p)}$ be the Rokhlin towers with base the continuity intervals of $I^{(p)}$ and $r_1^{(p)}, \dots, r_9^{(p)}$ their heights. For each $1 \le k \le 9$,

$$ C_k^{(p)} = \bigcup_{i=0}^{r_k^{(p)}-1} T^i(I_k^{(p)}) $$

where $I_1^{(p)}, \dots, I_9^{(p)}$ form a partition of $I^{(p)}$. The previous geometric discussion means that, there exists a constant $K$, such that, for every $p$ and every $k \in \{1, \dots, 9\}$, for every $y$ in the base of the
1099 tower $C_k^{(p)}$

$$ (2) \qquad \left| \sum_{i=0}^{r_k^{(p)}} f(S^i y) \right| = \left| \langle (B^t)^p f, e_k \rangle \right| = \left| \langle f, e_p \rangle \right| < K. $$

1100 The above formula comes from a classical argument that can be found, in a more general setting, in Zorich's work. The inequality (2) proves equation (1) for the basis of a Rokhlin tower taking $n_p = r_k^{(p)}$. 1101 1102

Since $S^{(p)}$ is minimal (because $S^{(p)}$ is conjugate to $S$ which is a minimal interval exchange transformation), there exists $\kappa > 0$ such that, for each point $x \in I_k^{(p)}$, there exists $j < \kappa$, with $(S^{(p)})^j(x)$ belongs to $I_k^{(p)}$. In other words, return times to continuity intervals of $S^{(p)}$ are bounded by a universal constant depending only on $S$. 1103 1104 1105 1106

Let now $x$ be in $s^i(I_k^{(p)})$. The itinerary of $x$ after time $r_k^{(p)}$ is a succession of towers $C_{1(x)}^{(p)}, \dots, C_{j(x)}^{(p)}$. By the previous remark, there exists $0 < j(x) < \kappa$ such that $j(x) = k$. Let

$$ n_p = r_k^{(p)} - i + r_{1(x)}^{(p)} + \dots + r_{j(x)-1}^{(p)} + i $$

It means that we follow the itinerary of $x$ until it comes back to its initial step, the step $i$ of the Rokhlin tower $k$. Thus the Birkhoff sum of $f$ from time 0 to time $n_p - 1$ is the sum along the towers $C_k^{(p)}, C_{1(x)}^{(p)}, \dots, C_{j(x)}^{(p)}$. Using bound (2), we have:

$$ \sum_{j=0}^{n_p-1} |f(T^j(x)| < K\kappa. $$

1107 This concludes the proof of Theorem 25.

1108 **Remark 6.** The same results hold for every EW-interval exchange transformation (resp. Or- 1109 interval exchange transformation) as soon as the slope of the corresponding linear flow is irra- 1110 tional. The proof goes along the same lines but is a little bit more technical.

1111 **Corollary 26.** Let $L$ be a non-recurrent language, satisfying an unflipped order condition, such 1112 that the language $L'$ of Lemma 18 is $L(S)$ for any EW-interval exchange transformation or Or- 1113 interval exchange transformation $S$ in Theorem 25 or Remark 6. Then $L$ is not a natural coding of 1114 any affine interval exchange transformation.

1115 **Proof**

1116 By Lemma 16, any non-recurrent orbit of $X_L$ coincides with orbits of $X_{L'}$ on an infinite prefix and 1117 an infinite suffix. Thus the estimates made in the proof of Theorem 25 on the Birkhoff sums of $S$ 1118 contradict the criterion in Theorem 20. $\square$

1119 **REFERENCES**

1120 [1] V.I. ARNOLD: Small denominators and problems of stability of motion in classical and celestial mechanics, *Usp. Math. Nauk*. 18 (1963), p. 91–192, (in Russian) translated in *Russian Math. Surveys* 18 (1963), p. 86–194.

1121 [2] P. ARNOUX: Un invariant pour les échanges d’intervalle et les flots sur les surfaces, (in French) *Thèse de 3e cycle*, Reims, 1981.

1122 [3] P. ARNOUX, G. RAUZY: Représentation géométrique de suites de complexité $2n + 1$, (in French) *Bull. Soc. Math. France* 119 (1991), 199–215.

1123 [4] V. BERTHÉ, C. DE FELICE, F. DOLCE, J. LEROY, D. PERRIN, C. REUTENAUER, G. RINDONE: Acyclic, 1124 connected and tree sets, *Monatsh. Math.* 176 (2015), p. 521–550.
1128 [5] M. BOSHERNITZAN: A unique ergodicity of minimal symbolic flows with standard block growth, *J. Analyse Math.* 44 (1984/85), p. 77–96.

1129 M. BOSHERNITZAN, I. KORNFELD: Interval translation mappings, *Ergodic Theory Dynam. Systems* 15 (1995), p. 821–832.

1130 [7] X. BRESSAUD, P. HUBERT, A. MAASS: Persistence of wandering intervals in self-similar affine interval exchange transformations. *Ergodic Theory Dynam. Systems* 30 (2010), p. 665–686.

1131 R. CAMELIER, C. GUTTIEREZ: Affine interval exchange transformations with wandering intervals, *Ergodic Theory Dynam. Systems* 17 (1997), p. 1315–1338.

1132 [9] J. CASSAIGNE: Complexité et facteurs spéciaux, (in French) Journées Montoises (Mons, 1994), *Bull. Belg. Math. Soc. Simon Stevin* 4 (1997), p. 67–88.

1133 [10] J. CASSAIGNE, F. NICOLAS: Factor complexity, *Combinatorics, automata and number theory*, p. 163–247, Encyclopedia Math. Appl., 135, Cambridge Univ. Press, Cambridge, 2010.

1134 [11] M. COBO: Piece-wise affine maps conjugate to interval exchanges. *Ergodic Theory Dynam. Systems* 22 (2002), p. 375–407.

1135 [12] E.M. COVEN, G.A. HEDLUND: Sequences with minimal block growth, *Math. Systems Theory* 7 (1973), p. 138–153.

1136 [13] A. DENJOY: Sur les courbes définies par les équations différentielles à la surface du tore. *J. Math. Pures Appl.* 11 (1932), p. 333–375.

1137 [14] G. DIDIER: Échanges de trois intervalles et suites sturmiennes, *J. Théor. Nombres Bordeaux*, 9 (1997), p. 463–478.

1138 [15] S. FERENCZI, C. HOLTON, L.Q. ZAMBONI: The structure of three-interval exchange transformations II: a combinatorial description of the trajectories, *J. Anal. Math.* 89 (2003), p. 239–276.

1139 [16] S. FERENCZI, P. HUBERT: Minimality and unique ergodicity of Veech 1969 type interval exchange transformations, to appear in *Geometriae Dedicata*, arXiv:2103.09018.

1140 [17] S. FERENCZI, L.Q. ZAMBONI: Languages of k-interval exchange transformations, *Bull. Lond. Math. Soc.* 40 (2008), p. 705–714.

1141 [18] G. FORNI: Deviation of ergodic averages for area-preserving flows on surfaces of higher genus, *Ann. of Math.* (2) 155 (2002), no. 1, p. 1–103.

1142 [19] G. FORNI, C. MATHEUS: Introduction to Teichmüller theory and its applications to dynamics of interval exchange transformations, flows on surfaces and billiards. *J. Mod. Dyn.* 8 (2014), no. 3-4, p. 271–436.

1143 [20] D. GABORIAU, G. LEVITT, F. PAULIN: Pseudogroups of isometries of R and Rips’ theorem on free actions on R-trees, *Israël J. Math.* 87 (1994), p. 403–428.

1144 [21] S. GHAZOUANI: Local rigidity for periodic generalised interval exchange transformations, *Invent. Math.* 226 (2021), p. 467–520.

1145 [22] S. GHAZOUANI, C. ULCIGRAI: A priori bounds for GIETS, affine shadows and rigidity of foliations in genus two, arXiv:2106.03529.

1146 [23] G. HALÁSZ: Remarks on the remainder in Birkhoff’s ergodic theorem, *Acta Math. Acad. Sci. Hungar.* 28 (1976), p. 389–395.

1147 [24] M.-R. HERMAN: Sur la conjugaison différentiable des difféomorphsimes du cercle à des rotations, (French), *Inst. Hautes Études Sci. Publ. Math.* 49 (1979), p. 5–233.

1148 [25] A.Ya. KANEL-BELOV, A.L. CHERNYAT’EV: Describing the set of words generated by interval exchange transformations, *Comm. Algebra* 38 (2010), p. 2588–2605.

1149 [26] A.B. KATOK, A.M. STEPIN: Approximations in ergodic theory, *Usp. Math. Nauk.* 22 (1967), p. 81–106 (in Russian), translated in *Russian Math. Surveys* 22 (1967), p. 76–102.

1150 [27] M.S. KEANE: Interval exchange transformations, *Math. Zeitsch.* 141 (1975), p. 25–31.

1151 [28] S. KERCKHOFF: Simplicial systems for interval exchange maps and measured foliations, *Ergodic Theory Dynam. Systems* 5 (1985), p. 257–271.

1152 [29] G. LEVITT: La décomposition dynamique et la différentiabilité des feuilletages des surfaces, (French) [Dynamic decomposition and differentiability of surface foliations] *Ann. Inst. Fourier (Grenoble)* 37 (1987), p. 85–116.

1153 [30] I. LIOUSSE: Dynamique générique des feuilletages transversalement affines des surfaces, (French) [Generic dynamics of transversely affine foliations of surfaces] *Bull. Soc. Math. France* 123 (1995), p. 493–516.

1154 [31] S. MARMI, P. MOUSSA, J.-C. YOCCOZ: Affine interval exchange maps with a wandering interval. *Proc. Lond. Math. Soc.* (3) 100 (2010), p. 639–669.
1181 [32] S. MARMI, P. MOUSSA, J.-C. YOCCOZ: Linearization of generalized interval exchange maps, *Ann. of Math.* (2) 176 (2012), p. 1583–1646.

1183 [33] C. MATHEUS, J.-C. YOCCOZ: The action of the affine diffeomorphisms on the relative homology group of certain exceptionally symmetric origamis, *J. Mod. Dyn.* 4 (2010), p. 453–486.

1184 [34] M. MORSE, G.A. HEDLUND: Symbolic dynamics II. Sturmian trajectories, *Amer. J. Math.* 62 (1940), p. 1–42.

1186 [35] A. NOGUEIRA: Nonorientable recurrence of flows and interval exchange transformations. *J. Differential Equations* 70 (1987), p. 153–166.

1188 [36] A. NOGUEIRA: Almost all interval exchange transformations with flips are nonergodic, *Ergodic Theory Dynam. Systems* 9 (1989), p. 515–525.

1190 [37] V.I. OSELEDEC: The spectrum of ergodic automorphisms, (in Russian) *Dokl. Akad. Nauk. SSSR* 168 (1966), p. 1009–1011.

1192 [38] N. PYTHEAS FOGG: Substitutions in dynamics, arithmetics and combinatorics, edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel, *Lecture Notes in Mathematics* 1794. Springer-Verlag, Berlin, 2002. xviii+402 pp. ISBN: 3-540-44141-7.

1195 [39] G. RAUZY: Échanges d'intervalles et transformations induites, (in French), *Acta Arith.* 34 (1979), p. 315–328.

1196 [40] M.-L. SANTINI-BOUCHARD: Échanges de trois intervalles et suites minimales, (in French), *Theoret. Comput. Sci* 174 (1997), p. 171-191.

1198 [41] W. VEECH, Gauss measures for transformations on the space of interval exchange maps, *Ann. of Math.* (2) 115 (1982), no. 1, 201–242.

1200 [42] J. C. YOCCOZ, Interval exchange maps and translation surfaces. Homogeneous flows, moduli spaces and arithmetic, 1–69, *Clay Math. Proc.*, 10, *Amer. Math. Soc.*, Providence, RI, 2010.

1202 [43] A. ZORICH, Deviation for interval exchange transformations, *Ergodic Theory Dynam. Systems* 17 (1997), no. 6, p. 1477–1499.

1204 AIX MARSEILLE UNIVERSITÉ, CNRS, CENTRALE MARSEILLE, INSTITUT DE MATHÉMATIQUES DE MARSEILLE, I2M - UMR 7373, 13453 MARSEILLE, FRANCE.

1206 Email address: ssferenczi@gmail.com

1207 AIX MARSEILLE UNIVERSITÉ, CNRS, CENTRALE MARSEILLE, INSTITUT DE MATHÉMATIQUES DE MARSEILLE, I2M - UMR 7373, 13453 MARSEILLE, FRANCE

1209 Email address: hubert.pascal@gmail.com

1210 INSTITUT CAMILLE JORDAN, UNIVERSITÉ CLAUDE BERNARD LYON 1, 43 BOULEVARD DU 11 NOVEMBRE 1918, F69622 VILLEURBANNE CEDEX (FRANCE)

1212 Email address: zamboni@math.univ-lyon1.fr