Acta Polytechnica doi:10.14311/AP.2016.56.0462 Acta Polytechnica 56(6):462–471, 2016 © Czech Technical University in Prague, 2016 available online at http://ojs.cvut.cz/ojs/index.php/ap ITINERARIES INDUCED BY EXCHANGE OF THREE INTERVALS Zuzana Masákováa, Edita Pelantováa, Štěpán Starostab, ∗ a Faculty of Nuclear Sciences and Physical Engineering,Czech Technical University in Prague, Prague, Czech Republic b Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic ∗ corresponding author: stepan.starosta@fit.cvut.cz Abstract. We focus on a generalization of the three gap theorem well known in the framework of exchange of two intervals. For the case of three intervals, our main result provides an analogue of this result implying that there are at most 5 gaps. To derive this result, we give a detailed description of the return times to a subinterval and the corresponding itineraries. Keywords: interval exchange transformation; three gap theorem; return time; first return map. 1. Introduction The well-known three gap theorem provides informa- tion about gaps between consecutive integers n for which {αn} < β with α,β ∈ (0, 1), where the notation {x} = x−bxc stands for the fractional part of x. In particular, the gaps take at most three values, the longest one being the sum of the other two. This re- sult was first proved by Slater [14], but it appeared in different versions and generalizations multiple times since. For a nice overview of this problem we refer to [1]. The reason is that the theorem can be inter- preted in the framework of coding with respect to intervals [0,β), [β, 1) of rotation by the angle α on the unit circle. For irrational α and β = 1 −α, such coding gives rise to famous Sturmian words. The three gap theorem is then intimately connected with the dynamical system associated with codings of ro- tations, induced transformations, return times and return itineraries. See also [8] for a distinct setting of exchange of two intervals related to the three gap theorem. Codings of rotations are advantageously interpreted in the language of interval exchange. The simplest case provides Sturmian words as codings of exchange of two intervals. We follow the study on itineraries induced by exchange of two intervals, presented in [13], to study the exchange of three intervals. In this article we focus on codings of a non- degenerate symmetric exchange T : J → J of three intervals. The main result is the description of the return times to a general interval I ⊂ J and an insight into the structure of the set of I-itineraries, i.e., the finite words that are codings of the return trajectories to I (see the definition below). These results are given in Theorem 4.1 and then interpreted as analogues of the well-known three gap and three distance theorems (see Section 6). Particular attention is paid to the special cases when the set of I-itineraries has only three elements. These cases belong to the most interesting from the combinatorial point of view, since they provide infor- mation about return words to factors, and about the morphisms preserving three interval exchange words. These specific cases are studied in Section 5. This allows us to describe the return words to palindromic bispecial factors, which can be seen as a complement to some of the results in [6]. We also focus on substi- tutions fixing words coding interval exchange trans- formations. The latter has implications [12] for the question of Hof, Knill and Simon [10] about palin- dromic substitution invariant words with application to aperiodic Schrödinger operators. 2. Preliminaries 2.1. Combinatorics on words A finite word w = w0 · · ·wn−1 is a concatenation of letters of a finite alphabet A. The number n of letters in w is the length of w and is denoted by |w|. The set of all finite words over an alphabet A, including the empty word �, with the operation of concatenation forms a monoid, denoted by A∗. One considers also infinite words u = u0u1u2 · · · ∈ AN. If u ∈ A∗ ∪AN and u = vwz, for some v,w ∈ A∗ and z ∈ A∗ ∪AN, we say that v,w,z are factors of u. In particular, v is a prefix and z is a suffix of u. We write wz = v−1u, vw = uz−1. An infinite word u is said to be aperiodic if it does not have a suffix of the form wwww · · · . If the infinite word u contains at least two occur- rences of each of its finite factors, then it is said to be recurrent. If the distances between two consecutive occurrences of every factor are bounded, then u is uniformly recurrent. If w,v are factors of u such that vw is also a factor of u and vw contains w as its prefix and as its suffix but not anywhere else, then v is a return word to w in u. Thus u is uniformly recurrent if and only if each factor w of u has finitely many return words. The language of an infinite word u is the set of all its finite factors. It is denoted by L(u). The number of factors of u of length n defines the factor complexity function Cu : N → N. It is known that aperiodic 462 http://dx.doi.org/10.14311/AP.2016.56.0462 http://ojs.cvut.cz/ojs/index.php/ap vol. 56 no. 6/2016 Itineraries induced by exchange of three intervals infinite words have complexity Cu(n) ≥ n + 1 for n ∈ N. Sturmian words are aperiodic words with minimal factor complexity. 2.2. Exchange of three intervals Given a partition of an interval J into disjoint union of intervals J1, . . . ,Jk, the exchange of k intervals is a bijection determined by a piecewise translation permuting the intervals according to a prescribed per- mutation π. In the article, we consider the case: let k = 3, 0 < α < β < 1, and T : [0, 1) → [0, 1) be given by T(x) =   x + 1 −α if x ∈ [0,α) =: JA, x + 1 −α−β if x ∈ [α,β) =: JB, x−β if x ∈ [β, 1) =: JC. (1) The transformation T is an exchange of three intervals with the permutation (321). It is often called a 3iet for short. The orbit {Tn(ρ) : n ∈ Z} of a point ρ ∈ [0, 1) can be coded by an infinite word uρ = u0u1u2 . . . over the alphabet {A,B,C} given by un = X if Tn(ρ) ∈ JX for X ∈{A,B,C}. The infinite word uρ is called a 3iet word, the point ρ is called the intercept of uρ. An exchange of intervals satisfies the minimality condition if the orbit of any given ρ ∈ [0, 1) is dense in [0, 1), which amounts to requiring that 1 − α and β be linearly independent over Q. Then the word uρ is aperiodic, uniformly recurrent, and the language of uρ does not depend on the intercept ρ. The complexity of the infinite word uρ is known to satisfy Cuρ(n) ≤ 2n + 1 (see [6]). If for every n ∈ N equality is achieved, then the transformation T and the word uρ are said to be non-degenerate. A necessary and sufficient condition for a 3iet T to be non-degenerate is that T is minimal and 1 /∈ (1 −α)Z + βZ; (2) see [6]. 3. Itineraries in exchange of three intervals Definition 3.1. Given a subinterval I ⊂ [0, 1), we define the so-called return time to I as a mapping rI : I → Z+ = {1, 2, 3, . . .} such that rI(x) = min{n ∈ Z+ : Tn(x) ∈ I}. The prefix of the word ux of length rI(x) coding the orbit of x ∈ I under a 3iet T is called the I-itinerary of x and denoted RI(x). The set of all I-itineraries is denoted by ItI = {RI(x) : x ∈ I}. The map TI : I → I defined by TI(x) = TrI(x)(x) is called the first return map of T to I, or induced map of T on I. The indices in rI or RI are usually omitted, if this causes no confusion. For a given subinterval I ⊂ [0, 1) there exist at most five I-itineraries under a 3iet T. In particular, from the article of Keane [11], one can deduce what the intervals of points with the same itinerary are. We summarize it as the following lemma. Lemma 3.2. Let T be a 3iet defined by (1) and let I = [γ,δ) ⊂ [0, 1) such that δ < 1. Denote kα := min { k ∈ Z, k ≥ 0 : T−k(α) ∈ (γ,δ) } , kβ := min { k ∈ Z, k ≥ 0 : T−k(β) ∈ (γ,δ) } , kγ := min { k ∈ Z, k ≥ 1 : T−k(γ) ∈ (γ,δ) } , kδ := min { k ∈ Z, k ≥ 1 : T−k(δ) ∈ (γ,δ) } , and further A := T−kα(α), B := T−kβ (β), C := T−kγ (γ), D := T−kδ (δ). For x ∈ I, let Kx be a maximal interval such that for every y ∈ Kx, we have R(y) = R(x). Then Kx is of the form [c,d) with c,d ∈{γ,δ,A,B,C,D}. Consequently, # ItI ≤ 5. For a 3iet T, Lemma 3.2 implies that TI is an ex- change of at most 5 intervals. Consequently, the trans- formation TI has at most four discontinuity points. In fact, the following result of [9] says that independently of the number of I-itineraries, the induced map TI has always at most two discontinuity points. Proposition 3.3 [9]. Let T : J → J be a 3iet with the permutation (321) and satisfying the minimality condition, and let I ⊂ J be an interval. The first return map TI is either a 3iet with permutation (321) or a 2iet with permutation (21). In particular, in the notation of Lemma 3.2, we have D ≤ C. We will use two other facts about itineraries of an interval exchange, stated as Propositions 3.4 and 3.5. Both of these were proven in [12] for general interval exchange transformations with symmetric permuta- tion and thus hold also for 3iets with permutation (321). Note that a 3iet T is right-continuous. Therefore, if I = [γ,δ), then every word w ∈ ItI = {R(x) : x ∈ I} is an I-itinerary R(x) for infinitely many x ∈ I, which form an interval, again left-closed right-open. Proposition 3.4. Let T be a 3iet satisfying the min- imality condition and let I = [γ,δ) ⊂ [0, 1). There exist neighbourhoods Hγ and Hδ of γ and δ, respec- tively, such that for every γ̃ ∈ Hγ and δ̃ ∈ Hδ with 0 ≤ γ̃ < δ̃ ≤ 1 one has ItĨ ⊇ ItI, where Ĩ = [γ̃, δ̃). In particular, if # ItI = 5, then ItĨ = ItI. For an interval K = [c,d) ⊂ [0, 1) denote K = [1 −d, 1 − c). Then T(JX) = JX for any letter X ∈{A,B,C}. (3) 463 Z. Masáková, E. Pelantová, Š. Starosta Acta Polytechnica Proposition 3.5. Let T : [0, 1) → [0, 1) be a 3iet with permutation (321) satisfying the minimality con- dition. Let I ⊂ [0, 1) and let R1, . . . ,Rm be the I- itineraries. The I-itineraries are the mirror images of the I-itineraries, namely R1, . . . ,Rm. Moreover, if [γj,δj) := {x ∈ I : RI(x) = Rj } and [γ′j,δ ′ j) := TI ( [γj,δj) ) , for j = 1, . . . ,m, then {x ∈ I : R I (x) = Rj } = [1 −δ′j, 1 −γ ′ j). Convention: For the rest of the article, let T be a non-degenerate exchange of three intervals with permutation (321) given by (1). 4. Return time in a 3iet The aim of this section is to describe the possible return times of a non-degenerate 3iet T to a gen- eral subinterval I ⊂ [0, 1). Our aim is to prove the following theorem. Theorem 4.1. Let T be a non-degenerate 3iet and let I ⊂ [0, 1). There exist positive integers r1,r2 such that the return time of any x ∈ I takes value in the set {r1,r1 + 1,r2,r1 +r2,r1 +r2 + 1} or {r1,r1 + 1,r2,r2 + 1,r1 + r2 + 1}. First, we will formulate an important lemma, which needs the following notation. Given letters X,Y,Z ∈ {A,B,C} and a finite word w ∈ {A,B,C}∗, let ωXY→Z(w) be the set of words obtained from w re- placing one factor XY by the letter Z, i.e., ωXY→Z(w) = {w1Zw2 : w = w1XY w2 }. (4) Similarly, ωZ→XY (w) = {w1XY w2 : w = w1Zw2 }. (5) Clearly, v ∈ ωXY→Z(w) ⇔ w ∈ ωZ→XY (v). (6) By abuse of notation, we write v = ωXY→Z(w) instead of v ∈ ωXY→Z(w). Lemma 4.2. Assume that the orbits of points α,β,γ and δ are mutually disjoint. For sufficiently small ε > 0, we have the following relations between I- itineraries of points in I: (a) R(A−ε) = ωB→AC ( R(A + ε) ) , (b) R(A + ε) = ωAC→B ( R(A−ε) ) , (c) R(B−ε) = ωCA→B ( R(B + ε) ) , (d) R(B + ε) = ωB→CA ( R(B−ε) ) , (e) R(D + ε) = R(D−ε)R(δ −ε), (f) R(C−ε) = R(C + ε)R(γ + ε), where A,B,C,D are given in Lemma 3.2. Proof. We will first demonstrate the proof of the case (a). Let K = [A − ε,A + ε] with ε chosen such that K ⊂ I and α,β,γ,δ 6∈ Ti(K) for all 0 ≤ i ≤ kα with the only exception of Tkα(A) = α. (7) For simplicity, denote t = max{rI(x) : x ∈ K} the maximal return time. The existence of such ε follows trivially from the definition of the interval exchange transformation and the assumptions of the lemma. Let K− = [A−ε,A) and K+ = [A,A+ε]. It follows from the definition of A and condition (7) that for all i such that 0 < i ≤ kα we have Ti(K) ∩ I = ∅. Moreover, condition (7) implies that all such Ti(K) are intervals. It implies that for any x,y ∈ K, the prefixes of R(x) and R(y) of length kα + 1 are the same. Denote this prefix by w. The definition of kα implies that α ∈ Tkα(K). Since Tkα(K+) = [α,α + ε] ⊂ JB, we obtain Tkα+1(K+) = [ T(α),T(α) + ε ) . Furthermore, since Tkα(K−) = [α − ε,α) ⊂ JA, we obtain Tkα+1(K−) = [1 −ε, 1) ⊂ JC, and thus Tkα+2(K−) = [ T(α) −ε,T(α) ) . This implies that the set K′ = Tkα+2(K−) ∪ Tkα+1(K+) = [T(α) −ε,T(α) + ε] is an interval. As above, condition (7) implies that the set Ti(K′) is an interval for all i such that 0 ≤ i ≤ t−kα−1. It follows that min{i : Ti(K′) ∩K 6= ∅} = t−kα − 2 and con- dition (7) moreover implies that Tt−kα−2(K′) ⊂ K. Thus, the iterations x,T(x), . . . ,Tt−kα−2(x) of every x ∈ K′ are coded by the same word, say v. The whole situation is depicted in Figure 1. From what is said above, we can write down the I-itineraries of points from K, R(x) = { wACv if x ∈ K−, wBv if x ∈ K+. This finishes the proof of (a). The claim in item (c) is analogous to (a). Cases (b) and (d) are derived from (a) and (c) by the use of equivalence (6). Let us now demonstrate the proof of the case (e). Denote s = min{n ∈ Z+ : Tn(δ) ∈ I}. Let K = [D−ε,D + ε] with ε chosen such that K ⊂ I and α,β,γ,δ 6∈ Ti(K) for all 0 ≤ i ≤ kδ + s with the only exception of Tkδ (D) = δ. (8) The existence of such ε follows trivially from the def- inition of the interval exchange transformation and the assumptions of the lemma. 464 vol. 56 no. 6/2016 Itineraries induced by exchange of three intervals 0 1α βγ δ A A − ε A + ε 0 1α βγ δ T kα(A) = α T kα(A − ε) T kα(A + ε) T kα T kα 0 1α βγ δ T kα+1(A − ε) T 0 1α βγ δ T kα+2(A − ε) T kα+1(A + ε) T T 0 1α βγ δ T t(A − ε) T t−1(A + ε) T t−kα−2 T t−kα−2 . Figure 1. Situation in the proof of Lemma 4.2, case (a). Condition (8) implies that Ti(K) is an interval for all i such that 0 < i ≤ kδ +s. Moreover, Ti(K)∩I = ∅ for all i such that 0 < i < kδ. We obtain Tkδ (K)∩I = [δ−ε,δ). In other words, the I-itineraries of all points of K start with a prefix of length kδ which is equal to R(D − ε). Condition (8) and the definition of s implies that for all i such that kδ < i < s + kδ we have Ti(K) ⊂ JX for some X ∈ {A,B,C} and Ti(K) ∩ I = ∅. Moreover, Ti(K) ⊂ I for i = kδ + s. Thus, the iterations of points of Tkδ (K) = [δ−ε,δ)∪ Tkδ [D,D + ε] are coded by the same word of length s, namely R(δ−ε). Altogether, we can conclude that the I-itinerary of points in the interval [D,D + ε] is equal to R(D−ε)R(δ −ε). The situation is depicted in Figure 2. Case (f) can be treated in a way analogous to case (e). Now we can prove the main theorem describing the return times in 3iet. In the proof, it is sufficient to focus on the case when # ItI = 5, since, as we have seen from Proposition 3.4, the set of I-itineraries, and thus also their return times, for the other cases are only a subset of ItĨ for some “close enough” generic subinterval Ĩ ⊂ [0, 1). So throughout the rest of this section, suppose that # ItI = 5. This means by Lemma 3.2 that points A,B,C,D lie in the interior of the interval I = [γ,δ) and are mutually distinct. Moreover, by Proposition 3.3, we have D < C. Such conditions imply 12 possible orderings of A,B,C,D which give rise to 12 cases in the study of return times. We will describe them in the proof of Theorem 4.1 as cases (i)–(xii) and then show in Example 4.5 that all 12 cases may occur. Remark 4.3. Note that if γ = 0, i.e. we induce on an interval I = [0,δ), we have T−1(γ) = β and therefore necessarily B = C. Thus there are at most four I- itineraries. Due to Proposition 3.5, a similar situation happens if δ = 1. Proof of Theorem 4.1. We will discuss the 12 possi- bilities of ordering of points A,B,C,D in the interior of the interval [γ,δ) with the condition D < C. The structure of the set of I-itineraries will be best shown in terms of I-itineraries of points in the left neighbour- hood of the point D and right neighbourhood of the point C. For simplicity, we thus denote for sufficiently small positive ε R1 = R(D−ε), R2 = R(C + ε) and |R1| = t1, |R2| = t2. In order to be allowed to use Lemma 4.2, we will assume that the orbits of points α,β,γ and δ are mutually disjoint. Otherwise, we use Proposition 3.4 to find a modified interval Ĩ where this is satisfied and ItĨ = ItI. (i) Let A < B < D < C. We know that R(x) is constant on the intervals [γ,A), [A,B), [B,D), [D,C), and [C,δ). By definition R(x) = R2 for x ∈ [C,δ) and R(x) = R1 for x ∈ [B,D). We can derive from rule (e) of Lemma 4.2 that if x ∈ [D,C), then R(x) = R1R2. Further, we use rule (c) to 465 Z. Masáková, E. Pelantová, Š. Starosta Acta Polytechnica 0 1α βγ δ D D − ε D + ε 0 1α βγ δ T kδ (D − ε) T kδ (D + ε) T kδ T kδ 0 1α βγ δ T t(δ − ε) T t(δ + ε) T t T t . Figure 2. Situation in the proof of Lemma 4.2, case (e). show that R(x) = ωCA→B(R1) for x ∈ [A,B) and further by applying rule (a), we obtain that R(x) = ωB→AC ( ωCA→B(R1) ) for x ∈ [γ,A). Summarized, R(x) =   ωB→AC ( ωCA→B(R1) ) for x ∈ [γ,A), ωCA→B(R1) for x ∈ [A,B), R1 for x ∈ [B,D), R1R2 for x ∈ [D,C), R2 for x ∈ [C,δ). It is easy to see that the lengths of the above I- itineraries are t1, t1 − 1, t1, t1 + t2, t2, respectively. For that, realize that by definition (4) and (5) of the action of ωXY→Z and ωZ→XY , the length of the word ωB→AC ( ωCA→B(R1) ) is equal to the length of the itinerary R1, i.e. t1. Setting r1 = t1 − 1 and r2 = t2, we obtain the desired return times. The proofs of the other cases are analogous, we state the results in terms of R1 and R2. (ii) Let D < C < A < B. We obtain R(x) =   R1 for x ∈ [γ,D), R2R1 for x ∈ [D,C), R2 for x ∈ [C,A), ωAC→B(R2) for x ∈ [A,B), ωB→CA ( ωAC→B(R2) ) for x ∈ [B,δ), with lengths t1, t1 + t2, t2, t2 − 1, t2, respectively. We set r1 = t1 and r2 = t2 − 1. (iii) Let B < A < D < C. A discussion as above leads to R(x) =   ωCA→B ( ωB→AC(R1) ) for x ∈ [γ,B), ωB→AC(R1) for x ∈ [B,A), R1 for x ∈ [A,D), R1R2 for x ∈ [D,C), R2 for x ∈ [C,δ), with the corresponding lengths t1, t1 + 1, t1, t1 + t2, t2, respectively. We set r1 = t1 and r2 = t2. (iv) Let D < C < B < A. We obtain R(x) =   R1 for x ∈ [γ,D), R2R1 for x ∈ [D,C), R2 for x ∈ [C,B), ωB→CA(R2) for x ∈ [B,A), ωAC→B ( ωB→CA(R2) ) for x ∈ [A,δ), with lengths t1, t1 + t2, t2, t2 + 1, t2, respectively. We set r1 = t1 and r2 = t2. (v) Let A < D < B < C. We obtain R(x) =   ωB→AC(R1) for x ∈ [γ,A), R1 for x ∈ [A,D), R1R2 for x ∈ [D,B), R2ωB→AC(R1) for x ∈ [B,C), R2 for x ∈ [C,δ), with lengths t1 + 1, t1, t1 + t2, t1 + t2 + 1, t2, respectively. We set r1 = t1 and r2 = t2. (vi) Let D < A < C < B. We obtain R(x) =   R1 for x ∈ [γ,D), R1ωB→CA(R2) for x ∈ [D,A), R2R1 for x ∈ [A,C), R2 for x ∈ [C,B), ωB→CA(R2) for x ∈ [B,δ), with lengths t1, t1 + t2 + 1, t1 + t2, t2, t2 + 1, respectively. We set r1 = t1 and r2 = t2. (vii) Let B < D < A < C. We obtain R(x) =   ωCA→B(R1) for x ∈ [γ,B), R1 for x ∈ [B,D), R1R2 for x ∈ [D,A), R2ωCA→B(R1) for x ∈ [A,C), R2 for x ∈ [C,δ), 466 vol. 56 no. 6/2016 Itineraries induced by exchange of three intervals with lengths t1 − 1, t1, t1 + t2, t1 + t2 − 1, t2, respectively. We set r1 = t1 − 1 and r2 = t2. (viii) Let D < B < C < A. We obtain R(x) =   R1 for x ∈ [γ,D), R1ωAC→B(R2) for x ∈ [D,B), R2R1 for x ∈ [B,C), R2 for x ∈ [C,A), ωAC→B(R2) for x ∈ [A,δ), with lengths t1, t1 + t2 − 1, t1 + t2, t2, t2 − 1, respectively. We set r1 = t1 and r2 = t2 − 1. (ix) Let A < D < C < B. We obtain R(x) =   ωB→AC(R1) for x ∈ [γ,A), R1 for x ∈ [A,D), R1ωB→CA(R2) for x ∈ [D,C), R2 for x ∈ [C,B), ωB→CA(R2) for x ∈ [B,δ), with lengths t1 + 1, t1, t1 + t2 + 1, t2, t2 + 1, respec- tively. We set r1 = t1 and r2 = t2. (x) Let B < D < C < A. We obtain R(x) =   ωCA→B(R1) for x ∈ [γ,B), R1 for x ∈ [B,D), R1ωAC→B(R2) for x ∈ [D,C), R2 for x ∈ [C,A), ωAC→B(R2) for x ∈ [A,δ), with lengths t1 −1, t1, t1 + t2 −1, t2, t2 −1, respec- tively. We set r1 = t1 − 1 and r2 = t2 − 1. (xi) Let D < A < B < C. We obtain R(x) =   R1 for x ∈ [γ,D), R1R2 for x ∈ [D,A), ωCA→B(R2R1) for x ∈ [A,B), R2R1 for x ∈ [B,C), R2 for x ∈ [C,δ), with lengths t1, t1 + t2, t1 + t2 − 1, t1 + t2, t2, respectively. We set r1 = t1 − 1 and r2 = t2. (xii) Let D < B < A < C. We obtain R(x) =   R1 for x ∈ [γ,D), R1R2 for x ∈ [D,B), ωB→AC(R2R1) for x ∈ [B,A), R2R1 for x ∈ [A,C), R2 for x ∈ [C,δ), with lengths t1, t1 + t2, t1 + t2 + 1, t1 + t2, t2, respectively. We set r1 = t1 and r2 = t2. Remark 4.4. When describing the I-itineraries us- ing the words R1, R2, we could apply the rules of γ δ Type Lengths 6 25 99 100 A < B < D < C [2, 1, 2, 3, 1] 29 100 71 100 D < C < A < B [1, 15, 14, 13, 14] 77 100 4 5 B < A < D < C [88, 89, 88, 109, 21] 7 25 3 4 D < C < B < A [1, 13, 12, 13, 12] 1 100 3 4 A < D < B < C [2, 1, 2, 3, 1] 1 100 29 100 D < A < C < B [2, 14, 13, 11, 12] 1 4 99 100 B < D < A < C [1, 2, 3, 2, 1] 71 100 99 100 D < B < C < A [2, 13, 14, 12, 11] 1 25 37 50 A < D < C < B [2, 1, 4, 2, 3] 29 100 99 100 B < D < C < A [1, 2, 4, 3, 2] 1 100 99 100 D < A < B < C [1, 2, 1, 2, 1] 1 4 3 4 D < B < A < C [1, 12, 13, 12, 11] Table 1. The cases (i)–(xii) from the proof of The- orem 4.1 for α = 15 √ 5 − 15 , β = − 1 6 √ 5 + 23 as in Example 4.5. The endpoints of the interval I = [γ,δ) are in the first and second column. The last column contains a list of lengths of I-itineraries of all 5 subin- tervals of I starting from the leftmost one. Lemma 4.2 in a different order. By doing so, we would obtain the itineraries expressed differently, which yields interesting relations between words R1,R2. For example, in the case (ix), we derive that the I-itinerary of x ∈ [D,C) is R(x) = R1ωB→CA(R2) = R2ωB→AC(R1). Note also the symmetries between the cases (i) and (ii), (iii) and (iv), (v) and (vi), (vii) and (viii), in consequence of Proposition 3.5. Indeed, if we exchange the pair of points D ↔ C, B ↔ A, letters A ↔ C, and finally the inequalities “<” and “>”, we obtain a symmetric situation in the list of cases we discussed in the proof. In this sense, each of cases (ix) up to (xii) is symmetric to itself. Example 4.5. Set α = 15 √ 5 − 15 and β = − 1 6 √ 5 + 23 . Table 1 shows 12 choices of I = [γ,δ) which produce 12 distinct orders of the points A, B, C and D, shown in the third column. The last column contains the respective lengths of the 5 distinct I-itineraries. Let us describe in detail one of the cases, namely the case B < D < C < A. The induced interval is determined by setting γ = 29100 and δ = 99 100 . One can verify that B = T−0(β) = 1 6 √ 5 + 1 3 ≈ 0.706011329583298; D = T−2(δ) = 11 30 √ 5 + 37 300 ≈ 0.943224925083256; C = T−3(γ) = 8 15 √ 5 − 73 300 ≈ 0.949236254666554; A = T−1(α) = 11 30 √ 5 + 2 15 ≈ 0.953224925083256. It corresponds to the case (x) in the proof of The- orem 4.1 with R1 = CA and R2 = CAC. The I- 467 Z. Masáková, E. Pelantová, Š. Starosta Acta Polytechnica itinerary of a point x ∈ I = [γ,δ) is R(x) =   B for x ∈ [γ,B), CA for x ∈ [B,D), CACB for x ∈ [D,C), CAC for x ∈ [C,A), CB for x ∈ [A,δ). 5. Description of the case of three I-itineraries The cases (i)–(xii) in the proof of Theorem 4.1 cor- respond to the generic instances of a subinterval I in a non-degenerate 3iet which lead to 5 different I-itineraries. Let us focus on the cases where, on the contrary, the set of I-itineraries has only 3 ele- ments. First we recall two reasons why such cases are interesting. For a factor w from the language of a non- degenerate 3iet transformation T, denote [w] = {ρ ∈ [0, 1) : w is a prefix of uρ}. It is easy to see that [w] – usually called the cylinder of w – is a semi-closed interval and its boundaries belong to the set {T−i(z) : 0 ≤ i < n,z ∈{α,β}}. Clearly, a factor v is a return word to the factor w if and only if v is a [w]-itinerary. It is well known [16] that any factor of an infinite word coding a non-degenerate 3iet has exactly three return words and thus the set It[w] has three elements. The second reason why to study intervals I yielding three I-itineraries is that any morphism fixing a non- degenerate 3iet word corresponds to such an interval I. Details of this correspondence will be explained further in this section. Proposition 5.1. Let T be a non-degenerate 3iet and let I = [γ,δ) ⊂ [0, 1) be such that # ItI = 3. One of the following cases occurs: (i) B = D < A = C and R(x) =   R1 for x ∈ [γ,B), ωB→CA(R1R2) = ωB→AC(R2R1) for x ∈ [B,A), R2 for x ∈ [A,δ); (ii) A = D < B = C and R(x) =   R1 for x ∈ [γ,A), ωAC→B(R1R2) = ωCA→B(R2R1) for x ∈ [A,B), R2 for x ∈ [B,δ); (iii) B < A = C = D and R(x) =   ωCA→B(R1) for x ∈ [γ,B), R1 for x ∈ [B,A), R2 for x ∈ [A,δ); (iv) B = C = D < A and R(x) =   R1 for x ∈ [γ,A), R2 for x ∈ [A,B), ωAC→B(R2) for x ∈ [B,δ); (v) A = C = D < B and R(x) =   R1 for x ∈ [γ,A), R2 for x ∈ [A,B), ωB→CA(R2) for x ∈ [B,δ); (vi) A < B = C = D and R(x) =   ωB→AC(R1) for x ∈ [γ,A), R1 for x ∈ [A,B), R2 for x ∈ [B,δ). Sketch of a proof. Since by Lemma 3.2 the subinter- vals of I corresponding to the same itinerary are de- limited by the points A,B,C and D, we may have # ItI = 3 only if some of these points coincide, more precisely if #{A,B,C,D} = 2. The non-degeneracy of the considered 3iet implies that always A 6= B, which further limits the discussion. The six cases listed in the statement are the possibil- ities of how this may happen, respecting the condition D < C or D = C. In order to describe the itineraries, denote again R1 = R(D−ε) and R2 = R(C + ε) for ε > 0 sufficiently small. One can then follow the ideas of the proof of Lemma 4.2. 5.1. Return words to factors of a 3iet Let us apply Proposition 5.1 in order to provide the de- scription of return words to factors of a non-degenerate 3iet word. If a factor w has a unique right prolon- gation in the language L(T), i.e. there exists only one letter a ∈ A such that wa ∈ L(T), then the set of return words to w and the set of return words to wa coincide. And (almost) analogously, if a factor w has a unique left prolongation in the language L(T), say aw for some a ∈ A, then a word v is a return word to w if and only if ava−1 is a return word to aw. Consequently, to describe the structure of return words to a given factor w, we can restrict to factors which have at least two right and at least two left prolongations. Such factors are called bispecial. It is readily seen that the language of an aperiodic recur- rent infinite word u contains infinitely many bispecial factors. Before giving the description of return words to bispecial factors, we state the following lemma. Let us recall that for a word w the notation w denotes the reversal of w while for an interval [c,d) the notation [c,d) denotes the interval [1 −d, 1 − c). Lemma 5.2. Let w belong to the language of a non- degenerate 3iet T. Denote n = |w|. For the cylinder of its reversal w, one has [w] = Tn ([w]). 468 vol. 56 no. 6/2016 Itineraries induced by exchange of three intervals Proof. According to the definition of [w], for each [w]-itinerary r, the word rw belongs to the language and w occurs in rw exactly twice, as a prefix and as a suffix. In other words r is a return word to w. Moreover, [w] is the maximal (with respect to inclusion) interval with this property. It follows also that if r is an [w]-itinerary, then the word w−1rw is a Tn([w])-itinerary. Applying Proposition 3.5 to the interval Tn([w]) we obtain that s := w−1rw is an Tn([w])-itinerary. Since the word sw = rw has a prefix w and a suffix w, with no other occurrences of w, the word s is a return word to w and thus by definition of the cylinder, s = w−1rw belongs to [w]-itinerary for any Tn([w])-itinerary s. From the maximality of the cylinder we have Tn([w]) ⊂ [w]. Since the lengths of the intervals [w] and Tn([w]) coincide we see, in particular, that the length of the interval [w] is less or equal to the length of the interval [w]. But from the symmetry of the role w and w, their length must be equal and thus Tn([w]) = [w]. The language of T contains two types of bispecial factors: palindromic and non-palindromic. In [6], Ferenczi, Holton and Zamboni studied the structure of return words to non-palindromic bispecial factors. The following proposition completes this description. Proposition 5.3. Let w be a bispecial factor. If w is a palindrome, then its return words are described by the cases (i) and (ii) of Proposition 5.1. If w is not a palindrome, then its return words are described by the cases (iii) – (vi) of Proposition 5.1. Proof. Let w be a bispecial factor. If w is not a palindrome, the claim follows from Theorem 4.6 of [6]. Assume that w is a palindrome and let [w] = [T−`(L),T−r(R)) with L,R ∈ {α,β} and 0 ≤ `,r < |w|. By Lemma 5.2 we have [w] = T |w| ([w]). Since w = w, we have Iw = Iw, and thus Iw = [T−`(L),T−r(R)) = [1 −Tn−r(R), 1 −Tn−`(L)) = Iw. Since the considered 3iet is non-degenerate, the pa- rameters α,β satisfy (2). Consequently, the equation T−`(L) = 1 − Tn−r(R) has a solution if and only if R 6= L. Thus, we have neither A = C = D nor B = C = D and we are in the case (i) or (ii) of Proposition 5.1. 5.2. Substitutions fixing 3iet words Another application of Proposition 5.1 is providing some information about substitution having as a fixed point a non-degenerate 3iet word. A substitution over an alphabet A is a morphism η : A∗ →A∗ such that η(b) 6= � for b ∈A and there is a letter a ∈A satisfying η(a) = aw for some non-empty word w. The action of η can be naturally extended to infinite words u ∈AN by setting η(u) = η(u0)η(u1)η(u2) . . .. If η(u) = u, then u is said to be a fixed point of η. Obviously, a substitution always has the fixed point limn→∞ηn(a) where the limit is taken over the product topology. A substitution η is primitive if there exists an integer k such that for all a,b ∈A, the letter b occurs in ηk(a). 3iet words fixed by a substitution were studied in [3] and [5]. In [3] it was shown that a substitution fixing a non-degenerate 3iet word corresponds to an interval I such that the induced transformation is homothetic to the original one. More precisely, we have the following theorem. Theorem 5.4 [3]. Let ξ be a primitive substitution over {A,B,C} and let T be a non-degenerate 3iet. If substitution ξ fixes the word uρ coding the orbit of a point ρ ∈ [0, 1) under T , then there exists an interval I ⊂ [0, 1) such that the induced transformation TI is homothetic to T, the set of I-itineraries is equal to ItI = {RA,RB,RC}, and the substitution ξ satisfies either η = ξ or η = ξ2, where η(A) = RA, η(B) = RB and η(C) = RC. Using the above theorem together with Propo- sition 5.1, one can derive information about the itineraries which determine the substitution η. Corollary 5.5. Let η be a primitive substitution as in Theorem 5.4 fixing a non-degenerate 3iet word over the alphabet {A,B,C}. We have η(B) = ωAC→B ( η(AC) ) = ωCA→B ( η(CA) ) or η(B) = ωB→CA ( η(AC) ) = ωB→AC ( η(CA) ) . Proof. By Theorem 5.4, η corresponds to an interval I such that TI is homothetic to T. Since T is non- degenerate, also TI is non-degenerate, and therefore its discontinuity points C,D are distinct. By Proposi- tion 5.1, the three I-itineraries are of the form given by cases (i) or (ii). Example 5.6. We can illustrate the above corollary on the substitution η(A) = BCACAC, η(B) = BCACBBCAC, η(C) = BCAC. The morphism η satisfies the property given in Corol- lary 5.5 (see [12]). Namely, we have η(B) = BCACBBCAC = ωAC→B ( η(AC) ) = ωAC→B ( BCACACBCAC ) = ωCA→B ( η(CA) ) = ωCA→B ( BCACBCACAC ) . 469 Z. Masáková, E. Pelantová, Š. Starosta Acta Polytechnica Corollary 5.5 implies a relation of numbers of oc- currences of letters in letter images of η which may be used to get an interesting relation for the incidence matrix Mη of η. It is an integer-valued matrix defined by (Mη)ab = |η(a)|b for a,b ∈A. As a consequence of Corollary 5.5, we have for the columns of the incidence matrix Mη that Mη   1−1 1   =  |η(A)|A|η(A)|B |η(A)|C  −  |η(B)|A|η(B)|B |η(B)|C   +  |η(C)|A|η(C)|B |η(C)|C   = ±   1−1 1   . Thus, (1,−1, 1)> is an eigenvector of Mη correspond- ing to the eigenvalue 1 and −1, respectively. This fact has been already derived in [2] by other methods. 6. Gaps and distance theorems Let us reinterpret the statement of the main result (Theorem 4.1) from the point of view of three gap and three distance theorems which are narrowly connected with the exchange of two intervals. Under the name three gap theorem one usually refers to the description of gaps between neighbouring elements of the set G(α,δ) := { n ∈ N : {nα} < δ } ⊂ N, where α ∈ R\Q, δ ∈ (0, 1), see [15]. Sometimes one uses a more general formulation, namely the set G(α,ρ,γ,δ) := { n ∈ N : γ ≤{nα + ρ} < δ } ⊂ N, where moreover ρ ∈ R, 0 ≤ γ < δ < 1. The three gap theorem states that there exist integers r1,r2 such that gaps between neighbours in G(α,ρ,γ,δ) take at most three values, namely in the set {r1,r2,r1 + r2}. Let us interpret the three gap theorem in the frame- work of exchange of two intervals J0 = [0, 1 − α), J1 = [1 −α, 1). The transformation T : [0, 1) → [0, 1) is of the form T(x) = { x + α for x ∈ [0, 1 −α), x + α− 1 for x ∈ [1 −α, 1), (9) i.e., T(x) = {x + α}. Therefore we can write G(α,ρ,γ,δ) := { n ∈ N : Tn(ρ) ∈ [γ,δ) } , (10) and the gaps in this set correspond to return times to the interval [γ,δ) under the transformation T . Our Theorem 4.1 is an analogue of the three gap theorem in the form (10) generalized for the case when the transformation T is a non-degenerate 3iet. We see that there are 5 gaps, but still expressed using two basic values r1,r2. The so-called three distance theorem focuses on distances between neighbours of the set D(α,ρ,N) := { {αn + ρ} : n ∈ N, n < N } ⊂ [0, 1). The three distance theorem ensures the existence of ∆1, ∆2 > 0 such that distances between neighbours in D(α,ρ,N) take at most three values, namely in {∆1, ∆2, ∆1 + ∆2}. In the framework of 2iet T, we can write for the distances D(α,ρ,N) := { Tn(ρ) : n ∈ N, n < N } ⊂ [0, 1), (11) where α is the defining parameter of T as in (9), and ρ ∈ [0, 1). We could try to study the analogue of the three distance theorem in the form (11) for exchanges of three intervals. In fact, it can be derived from the results of [9] that if T is a 3iet with discontinuity points α,β, then D(α,β,ρ,N) := { Tn(ρ) : n ∈ N, n < N } has again at most three distances ∆1, ∆2, and ∆1 +∆2 for some positive ∆1, ∆2. The three distance theorem can also be used to derive that the frequencies of factors of length n in a Sturmian word take at most three values. Recall that the frequency of a factor w in the infinite word u = u0u1u2 . . . is given by freq(w) := lim N→∞ 1 N ( #{0 ≤ i < N : w is a prefix of uiui+1 . . .} ) , if the limit exists. It is a well known fact that the frequencies of factors of length n in a coding of an exchange of intervals are given by the lengths of cylinders corresponding to the factors. The boundary points of these cylinders are T−j(1 −α), for j = 0, . . . ,n− 1. Consequently, the distances in the set D(α, 1 −α,N) are precisely the frequencies of factors, and the three distance theorem implies the well known fact that Sturmian words have for each n only three values of frequencies of factors of length n, namely %1,%2,%1 + %2. The frequencies of factors of length n in 3iet words are given by distances between neighbours of the set{ T−n(α) : n ∈ N, n < N } ∪ { T−n(β) : n ∈ N, n < N } . In [4] it is shown, based on the study of Rauzy graphs, that the number of distinct values of frequencies in infinite words with reversal closed language satisfies #{ freq(w) : w ∈L(u), |w| = n} ≤ 2 ( Cu(n) −Cu(n− 1) ) + 1, which in case of 3iet words reduces to ≤ 5. Article [7] shows that the set of integers n for which this bound is achieved is of density 1 in N. 470 vol. 56 no. 6/2016 Itineraries induced by exchange of three intervals Acknowledgements The authors acknowledge financial support by the Czech Science Foundation grant GAČR 13-03538S. References [1] P. Alessandri and V. Berthé, Three distance theorems and combinatorics on words, Enseign. Math. (2), 44 (1998), pp. 103–132, doi:10.5169/seals-63900. [2] P. Ambrož, Z. Masáková, and E. Pelantová, Matrices of 3-iet preserving morphisms, Theor. Comput. Sci., 400 (2008), pp. 113–136, doi:10.1016/j.tcs.2008.02.044. [3] P. Arnoux, V. Berthé, Z. Masáková, and E. Pelantová, Sturm numbers and substitution invariance of 3iet words, Integers, 8 (2008), http://eudml.org/doc/117362. Article A14. [4] L. Balková and E. Pelantová, A note on symmetries in the Rauzy graph and factor frequencies, Theor. Comput. Sci., 410 (2009), pp. 2779–2783, doi:10.1016/j.tcs.2009.04.002. [5] P. Baláži, Z. Masáková, and E. Pelantová, Characterization of substitution invariant words coding exchange of three intervals, Integers, 8 (2008), http://eudml.org/doc/117368. Article A20. [6] S. Ferenczi, C. Holton, and L. Q. Zamboni, Structure of three-interval exchange transformations II: a combinatorial description of the trajectories, J. Anal. Math., 89 (2003), pp. 239–276, doi:10.1007/BF02893083. [7] S. Ferenczi and L. Q. Zamboni, Structure of k-interval exchange transformations: Induction, trajectories, and distance theorems, J. Anal. Math., 112 (2010), pp. 289–328, doi:10.1007/s11854-010-0031-2. [8] J. Florek and K. Florek, Billiard and the five-gap theorem, Discrete Math., 309 (2009), pp. 4123–4129, doi:10.1016/j.disc.2008.12.010. [9] L. S. Guimond, Z. Masáková, and E. Pelantová, Combinatorial properties of infinite words associated with cut-and-project sequences, J. Théor. Nombres Bordeaux, 15 (2003), pp. 697–725, doi:10.5802/jtnb.422. [10] A. Hof, O. Knill, and B. Simon, Singular continuous spectrum for palindromic Schrödinger operators, Comm. Math. Phys., 174 (1995), pp. 149–159, doi:10.1007/bf02099468. [11] M. Keane, Interval exchange transformations, Math. Z., 141 (1975), pp. 25–31, doi:10.1007/BF01236981. [12] Z. Masáková, E. Pelantová, and Š. Starosta, Exchange of three intervals: substitutions and palindromicity, submitted. [13] Z. Masáková and E. Pelantová, Itineraries induced by exchange of two intervals, Acta Polytechnica, 53 (2013), pp. 444–449, doi:10.14311/AP.2013.53.0444. [14] N. B. Slater, The distribution of the integers N for which θN < φ, Proc. Cambridge Philos. Soc., 46 (1950), pp. 525–534, doi:10.1017/s0305004100026086. [15] N. B. Slater, Gaps and steps for the sequence nθ mod 1, Math. Proc. Cambridge Phil. Soc., 63 (1967), pp. 1115–1123, doi:10.1017/S0305004100042195. [16] L. Vuillon, On the number of return words in infinite words constructed by interval exchange transformations, Pure Math. Appl. (PU.M.A.), 18 (2007), pp. 345–355, http://www.mat.unisi.it/ newsito/puma/public_html/18_3_4/Vuillon.pdf. 471 http://dx.doi.org/10.5169/seals-63900 http://dx.doi.org/10.1016/j.tcs.2008.02.044 http://eudml.org/doc/117362 http://dx.doi.org/10.1016/j.tcs.2009.04.002 http://eudml.org/doc/117368 http://dx.doi.org/10.1007/BF02893083 http://dx.doi.org/10.1007/s11854-010-0031-2 http://dx.doi.org/10.1016/j.disc.2008.12.010 http://dx.doi.org/10.5802/jtnb.422 http://dx.doi.org/10.1007/bf02099468 http://dx.doi.org/10.1007/BF01236981 http://dx.doi.org/10.14311/AP.2013.53.0444 http://dx.doi.org/10.1017/s0305004100026086 http://dx.doi.org/10.1017/S0305004100042195 http://www.mat.unisi.it/newsito/puma/public_html/18_3_4/Vuillon.pdf http://www.mat.unisi.it/newsito/puma/public_html/18_3_4/Vuillon.pdf Acta Polytechnica 56(6):462–471, 2016 1 Introduction 2 Preliminaries 2.1 Combinatorics on words 2.2 Exchange of three intervals 3 Itineraries in exchange of three intervals 4 Return time in a 3iet 5 Description of the case of three I-itineraries 5.1 Return words to factors of a 3iet 5.2 Substitutions fixing 3iet words 6 Gaps and distance theorems Acknowledgements References