Petr Ambrož

Anna Frid

Zuzana Masáková

Edita Pelantová

On the number of factors in codings of three interval exchange

Keywords: interval exchange, enumeration of factors, Sturmian words

We consider exchange of three intervals with permutation (3, 2, 1). The aim of this paper is to count the cardinality of the set 3iet(N ) of all words of length N which appear as factors in infinite words coding such transformations. We use the strong relation of 3iet words and words coding exchange of two intervals, i.e., Sturmian words. The known asymptotic formula #2iet(N )/N 3 ∼ 1 π 2 for the number of Sturmian factors allows us to find bounds 1 3π 2 + o(1) ≤ #3iet(N )/N 4 ≤ 2 π 2 + o(1).

Introduction

The study of infinite words arising from an exchange of several intervals was initiated by Rauzy, whereas dynamical systems connected with exchange of intervals has been already studied by Katok and Stepin [START_REF] Katok | Approximations in ergodic theory[END_REF]. The most explored subfamily of such words are Sturmian words corresponding to an exchange of two intervals [START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF]. Infinite words coding exchange of 3 intervals form the next interesting family.

The special case of Sturmian words is very well understood. For surveys on the properties of Sturmian words see [START_REF] Lothaire | Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and its Applications[END_REF][START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF].

Much less is known about codings of r intervals for r > 2. Combinatorial characterization of the language of such words was given first for r = 3 in [START_REF] Ferenczi | Structure of three-interval exchange transformations. II. A combinatorial description of the trajectories[END_REF], then for general r in [START_REF] Ya | Words with low complexity and interval exchange transformations[END_REF]. Boshernitzan and Caroll [START_REF] Boshernitzan | An extension of Lagrange's theorem to interval exchange transformations over quadratic fields[END_REF] have found a sufficient condition for substitutivity of an infinite word coding an exchange of r intervals. The necessity of this condition in the special case r = 3 and reverse-order permutation was demonstrated in [START_REF] Adamczewski | Codages de rotations et phénomènes d'autosimilarité[END_REF]. A criterion for substitution invariance of words coding exchange of 3 intervals with permutation (3,2,1) is given in [START_REF] Arnoux | Sturm numbers and substitution invariance of 3iet words[END_REF] and [START_REF] Baláži | Characterization of substitution invariant words coding exchange of three intervals[END_REF].

Actually, infinite words coding exchange of 3 intervals with permutation (3,2,1), here called 3iet words, constitute the central theme of this paper. They stand out among interval exchange words by the fact that, similarly to Sturmian words, they can be geometrically represented by cut-and-project sequences. This was first remarked in [START_REF] Langevin | Stimulateur cardiaque et suites de Farey[END_REF], then developed in [START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF]. Results of these papers are connected to the well known 3-distance theorem [START_REF] Sós | On the distribution mod 1 of the sequence nα[END_REF][START_REF] Alessandri | Three distance theorems and combinatorics on words[END_REF], and can be also explained in terms of the theorem of Katok [START_REF] Katok | Interval exchange transformations and some special flows are not mixing[END_REF] which states that when a k-interval exchange transformation is induced on a subinterval, the resulting transformation is a k or k + 1 interval exchange. An even more explicit connection between 3iet words and Sturmian words is displayed in [START_REF] Arnoux | Sturm numbers and substitution invariance of 3iet words[END_REF]. This connection allowed us to estimate the number of factors of 3iet words using the following enumeration formula for Sturmian words, first given by Lipatov [START_REF] Lipatov | A classification of binary collections and properties of homogeneity classes[END_REF]; see also [START_REF] Mignosi | On the number of factors of Sturmian words[END_REF][START_REF] Berstel | A geometric proof of the enumeration formula for Sturmian words[END_REF].

Theorem 1 [START_REF] Lipatov | A classification of binary collections and properties of homogeneity classes[END_REF][START_REF] Mignosi | On the number of factors of Sturmian words[END_REF][START_REF] Berstel | A geometric proof of the enumeration formula for Sturmian words[END_REF] The number #2iet(N ) of Sturmian factors of length N is given by

#2iet(N ) = 1 + N k=1 (N + 1 -k)ϕ(k) = 1 π 2 N 3 + O(N 2 log N ) ,
The aim of this paper is to show the following theorem.

Theorem 2 The asymptotic growth of the number of 3iet factors of length N is given by

1 3π 2 N 4 + O(N 3+δ ) ≤ #3iet(N ) ≤ 2 π 2 N 4 + O(N 3+δ ) ,
for arbitrary δ > 0.

The proof of Theorem 2 is divided into two parts, the upper bound is given in Theorem 9 in Section 5, the lower bound in Theorem 12 in Section 6. The lemmas on Sturmian words used in these sections may be of independent interest. Sections 3 and 4 describing properties of the Euler function and of Sturmian factors are auxiliary.

Precise values of #3iet(N ) for N ≤ 10 are found in Section 7.

Definitions of interval exchange words

Let A be a finite alphabet. A concatenation w = w 0 w 1 • • • w n-1 of letters w i ∈ A is called a word of length |w| = n. The number of occurrences of a letter a in the word w is denoted by |w| a . The set of all finite words over A together with the empty word is denoted by A * . We can also consider one-or two-sided infinite words

u = u 0 u 1 • • • ∈ A N , resp. u = • • • u -2 u -1 u 0 u 1 u 2 • • • ∈ A Z . A finite word w is a factor of an infinite word u = (u n ) if w = u i u i+1 • • • u i+n-1
for some i. The factors of an infinite word u form the language of u, which is denoted by L(u). We denote L n (u) = L(u) ∩ A n . The factor complexity of u is the function

C u : N → N given by C u (n) = #L n (u).
Sturmian words are aperiodic words with the smallest possible complexity, namely C u (n) = n + 1 for all n ∈ N. It is known [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF] that Sturmian words on {0, 1} are exactly the lower and upper mechanical words, which means that each Sturmian word u = (u n ) n∈Z ∈ {0, 1} Z is defined by

u n = (n + 1)α + β -nα + β or u n = (n + 1)α + β -nα + β ,
where α ∈ (0, 1) is irrational and β ∈ [0, 1). Another representation of Sturmian words is given by the two interval exchange. Define ε = 1 -α ∈ (0, 1), where α is the parameter used above. Consider the intervals [START_REF] Adamczewski | Codages de rotations et phénomènes d'autosimilarité[END_REF], and the corresponding transformation T ε : [0, 1) → [0, 1) defined by

I 0 = [0, ε), I 1 = [ε, 1), I 0 ∪I 1 = [0,
T ε (x) = x + 1 -ε for x ∈ I 0 , x -ε for x ∈ I 1 . (1)
We can code the orbit of a point x 0 ∈ [0, 1) by the infinite word u ε,x0 = (u n ) n∈Z ∈ {0, 1} Z :

u n = 0 if T n ε (x 0 ) ∈ I 0 , 1 if T n ε (x 0 ) ∈ I 1 . (2)
The word u ε,x0 is the upper mechanical word corresponding to α = 1 -ε and β = x 0 . Similarly, lower mechanical words are obtained by coding exchange of intervals of the type (•, •]. It is the representation of Sturmian words by two interval exchange which will be the most used here.

Since the language of a Sturmian word does not depend on the initial point x 0 , but rather only on the parameter ε, we can denote the language of u ε,x0 by L(ε) and the set of factors of length M of u ε,x0 by L M (ε).

We study infinite words which generalize Sturmian words in the way that they code exchange of three intervals. Let ε, be real numbers satisfying

ε ∈ (0, 1) \ Q , max{ε, 1 -ε} < < 1 . (3)
The mapping T ε, (x) : [0, ) → [0, ) defined by

T ε, (x) =      x + 1 -ε for x ∈ I A := [0, -1 + ε) , x + 1 -2ε for x ∈ I B := [ -1 + ε, ε) , x -ε for x ∈ I C := [ε, ) , (4)
is called exchange of three intervals (i) with permutation (3, 2, 1). The orbit of a point x 0 ∈ [0, ) under the transformation T ε, of (4) can be coded by the infinite word u ε, ,x0 = (u n ) n∈Z in the alphabet {A, B, C}, where

u n =      A if T n ε, (x 0 ) ∈ I A , B if T n ε, (x 0 ) ∈ I B , C if T n ε, (x 0 ) ∈ I C . (5)
A visual representation of a 3 interval exchange transformation can be found, e. g., in [START_REF] Adamczewski | Codages de rotations et phénomènes d'autosimilarité[END_REF]. Since ε is irrational, the infinite word u is aperiodic. We call these words 3iet words. Again, the language of a 3iet word does not depend on the initial point x 0 , thus we denote it by L(ε, ). The factor complexity of 3iet words depends on the parameter in the following way: C(n) = 2n + 1, if ∈ Z + εZ, otherwise it satisfies C(n) = n + C for some constant C and sufficiently large n, see [START_REF] Adamczewski | Codages de rotations et phénomènes d'autosimilarité[END_REF]. Words with the latter complexity are called quasisturmian and described for example in [START_REF] Cassaigne | Sequences with grouped factors. Developments in Language Theory III (DLT'97)[END_REF][START_REF] Chernyat'ev | Words with minimal growth function[END_REF].

Asymptotic behaviour of the totient function

In determining the asymptotic behaviour of the number of 3iet factors, we shall strongly use asymptotic properties of the Euler totient function, where k ⊥ n means gcd(k, n) = 1. In our formulas, we will use the Landau big O notation; instead of a function f (n), we write O(g(n)) if there exists a constant

ϕ(n) = #{k ∈ N | k ≤ n, k ⊥ n} = n p|n p prime 1 - 1 p , (
K such that |f (n)| ≤ K|g(n)| for all n ∈ N.
The proof of the first asymptotic formula for the totient function can be found for example in [START_REF] Nathanson | Elementary methods in number theory[END_REF]:

n k=1 ϕ(k) = 3 π 2 n 2 + O(n log n) . (6)
Using the first equality from Theorem 1 and this formula, one can easily derive the following estimate found already in [START_REF] Lipatov | A classification of binary collections and properties of homogeneity classes[END_REF]:

#2iet(N ) = 1 + N k=1 (N + 1 -k)ϕ(k) = 1 π 2 N 3 + O(N 2 log N ) . (7)
Yet another formula involving the totient function will be useful. It can be easily derived that for any q, numbers coprime to q are in a certain sense uniformly distributed, namely

#{p ∈ N | p ⊥ q, p ≤ i} = ϕ(q) q i + O(2 ω(q) ) ,
where ω(q) is the number of prime divisors of q. From the result of Hardy and Wright [START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF] on the asymptotic behavior of ω(q), it follows that

#{p ∈ N | p ⊥ q, j ≤ p ≤ i} = ϕ(q) q (i -j) + O(q δ ) , for any δ > 0. (8)

Sturmian factors and Farey numbers

As we have already mentioned, for every fixed irrational ε ∈ (0, 1) and fixed M ∈ N, the number of factors of length M in the language L(ε) of a Sturmian word is exactly M + 1. Obviously, the set L M (ε) does not determine ε uniquely: the same set of M + 1 factors appears for uncountably many irrational ε which form an interval. As shown in [START_REF] Mignosi | On the number of factors of Sturmian words[END_REF], if for some irrational

ε 1 < ε 2 it holds that L M (ε 1 ) = L M (ε 2 ),
then there exists a rational p q such that ε 1 < p q < ε 2 and q ≤ M . Therefore the interval (0, 1) of admissible parameters ε is partitioned into small intervals determining classes of Sturmian words with distinct L M (ε). The partition is given by the Farey fractions of order M , i.e., all the reduced fractions in [0, 1] with denominator smaller than or equal to M . It is useful to consider the Farey fractions as an ordered list

F M : f 0 = 0 1 < f 1 < • • • < f r-1 < f r = 1 1 . The partition [0, 1] = ∪ r i=0 [f i , f i+1 ]
, where F M = {f i | i = 0, . . . , r}, is essential for describing Sturmian factors of length M . We shall thus speak about classes of Sturmian words of length M determined by intervals (f i , f i+1 ), i = 0, . . . , r -1. Every class contains M + 1 factors and of course, the same factor may belong to different classes. For M = 4, the division is illustrated in Figure 1 together with the corresponding sets of factors of length 4.

The possible numbers of letters 0 and 1 in factors corresponding to an interval (f i , f i+1 ) can be easily determined as follows. Lemma 3 Let M ∈ N be fixed, and let f i , f i+1 be two consecutive Farey fractions of order M . Let ε be an irrational in (f i , f i+1 ). Then for every factor w of length M of a Sturmian word with parameter ε we have

|w| 0 ∈ M f i , M f i + 1 , |w| 1 ∈ M -M f i , M -M f i -1 . Proof: Denote α = 1 -ε. If w = w 0 w 1 • • • w M -1
is a factor of a Sturmian word with parameter ε, there must exist β ∈ [0, 1) such that

w i = (i + 1)α + β -iα + β ∈ {0, 1} , for i = 0, 1, . . . , M -1 .
Therefore

|w| 1 = M -1 i=0 w i = M α + β ∈ M α , M α + 1 .
The language L M (ε) is the same for all ε ∈ (f i , f i+1 ) and we have

M α = M (1-ε) = M -M ε = M -M ε -1 = M -M f i -1. 2
Now consider words coding the transformations T fi defined as in [START_REF] Adamczewski | Codages de rotations et phénomènes d'autosimilarité[END_REF]. If f i = p q , then such a word is purely periodic and looks as

v (i) v (i) v (i) • • • = v (i) ω
, where v (i) is a primitive word of length q. Recall that a finite word v is said to be primitive if it cannot be written in the form v = ww • • • w = w k for any integer k ≥ 2. Therefore the language of the periodic word coding the transformation T fi has exactly q factors of length M for every M ≥ q. Let us denote the set of such factors by

L (i) M . As it is derived in [19], L M (ε) = L (i) M ∪ L (i+1) M , for all ε ∈ (f i , f i+1 ) . We have #L M (ε) = M + 1, #L (i) M = q i , and #L (i+1) M = q i+1
, where q i , q i+1 are the denominators of Farey fractions f i , f i+1 , respectively. Therefore we have

# L (i) M ∩ L (i+1) M = q i + q i+1 -M -1 . ( 9
)
5 The upper bound

The main tool which we use in this section is a link between 3iet words and Sturmian words over the alphabet {0, 1} by means of morphisms σ 01 , σ 10 : {A, B, C} * → {0, 1} * defined by

σ 01 : A → 0 , B → 01 , C → 1 , σ 10 : A → 0 , B → 10 , C → 1 . (10)
In [START_REF] Arnoux | Sturm numbers and substitution invariance of 3iet words[END_REF], the following statement is proved.

Theorem 4 A ternary word u is a 3iet word if and only if both σ 01 (u) and σ 10 (u) are Sturmian words.

Based on this strong relation, we define the notion of b-amicability.

Definition 1 Let w (1) , w (2) be finite words over the alphabet {0, 1}. We say that w (1) , w (2) form a bamicable pair, if there exists a 3iet factor w over {A, B, C} with exactly b letters B such that w (1) = σ 01 (w) and w (2) = σ 10 (w).

w (1) =

w (2) = w = 0 0 A 1 1 C 0 0 A 0 1 1 0 B 0 0 A 1 1 C
Fig. 2: Finite words w (1) = 0100101 and w (2) = 0101001 forming a 1-amicable pair. The corresponding ternary word is w = ACABAC.

The notion is illustrated in Figure 2. Note that due to Theorem 4, both words of a b-amicable pair are Sturmian factors from the same language L(ε) for some irrational ε ∈ (0, 1). Proof: Obviously, words forming a b-amicable pair must be of length at least M ≥ 2b. Consider an interval [f i , f i+1 ) such that the language L M (ε) for ε ∈ (f i , f i+1 ) contains an amicable pair and f i = p q , p ⊥ q. Corollary 6 then implies that b must satisfy

b ≤ M p q + 1 and b ≤ M -M p q + 1 ,
providing bounds on p, namely,

q b -1 M ≤ p ≤ q 1 - b -1 M .
Thus, we are looking for the number

M q=1 # p ∈ N p ⊥ q and q b-1 M ≤ p ≤ q 1 -b-1 M
With the use of ( 8) we can write

#Z M,b ≤ M q=1 ϕ(q) q q 1 - 2(b -1) M + M O M δ = = M -2b + 2 M M q=1 ϕ(q) + O(M 1+δ
) for all δ > 0.

Together with the asymptotic behavior of M q=1 ϕ(q) given in [START_REF] Ya | Words with low complexity and interval exchange transformations[END_REF], this implies the statement of the lemma. 2 Proof: The language L M (ε) contains M + 1 factors of length M . Choose such a factor w and consider the set of points x ∈ [0, 1) such that the orbit {T j ε (x)}, j = 0, 1, . . . , M -1, is coded by w. It can be easily shown that this set is a subinterval of [0, 1) of the type [•, •). Thus [0, 1) is divided into M + 1 disjoint subintervals; the division is done by M division points T -j ε (ε), j = 0, 1, . . . , M -1. Let us denote these intervals J i , i = 1, 2, . . . , M + 1, ordered so that x < y for any x ∈ J i and any y ∈ J i+1 . The corresponding words of length M are denoted by w (i) , i = 1, 2, . . . , M + 1. Note that T j (J i ) is an interval for all j = 0, 1, . . . , M -1.

Let us first find an upper bound for the number of 1-amicable pairs of Sturmian factors of length M . The following procedure is illustrated in Figure 3. Take two consecutive intervals, J i , J i+1 for some i = 1, . . . , M . It means that J i ∪ J i+1 is an interval which contains in its interior exactly one of the division points, say T -k ε (ε). If k = 0, then the word w (i) starts with 0 and the word w (i+1) starts with 1. More generally, one can show that words w (i) and w (i+1) have a common prefix v of length k and the set

T k ε (J i ∪ J i+1 ) is still an interval. Since T -k ε (ε) ∈ (J i ∪ J i+1 ) • , we have ε ∈ T k ε (J i ∪ J i+1 ) •
, and therefore the word w (i) has prefix v0 and the word w (i+1) has prefix v1.

If k = M -1, then w (i) = v0 and w (i+1) = v1 and they are not 1-amicable. On the other hand, if k < M -1, then T k+1 (J i ) = T k (J i ) + 1 -ε is an interval of the form [•, 1), and T k+1 (J i+1 ) = T k (J i+1 ) -ε is an interval of the form [0, •). We further have

T k+2 (J i ) = T k+1 (J i ) -ε = T k (J i ) + 1 -2ε , T k+2 (J i+1 ) = T k+1 (J i+1 ) + 1 -ε = T k (J i+1 ) + 1 -2ε .
and therefore the set T j (J i ∪ J i+1 ) is again an interval for all j, k + 2 ≤ j ≤ M -1, and thus the words w (i) and w (i+1) have a common suffix v of length Mk -2. Therefore we have w (i) = v01v and w (i+1) = v10v and the words w (i) and w (i+1) form a 1-amicable pair. Together, we have a 1-amicable pair of words w (i) and w (i+1) for i = 1, . . . , M , i = k. Their number is therefore M -1. 3: Iterations of consecutive intervals Ji, Ji+1 show that the corresponding words w (i) , w (i+1) form a 1-amicable pair.

0 1 ε T k (Ji+1) T k (Ji) T k+1 (Ji+1) T k+2 (Ji+1) T k+1 (Ji) T k+2 (Ji) ε 1 0 0 ε 1 Fig.
The previous considerations imply that the words w (i) , i = 1, . . . , M +1, are ordered lexicographically, where consecutive words differ only by interchange of 01 ↔ 10 at one place. The only exception is the pair of words w (i) and w (i+1) whose intervals J i , J i+1 are separated by the iteration T -M +1 ε (ε). These words are of the form w (i) = v0 and w (i+1) = v1, which corresponds to 'half' of the interchange 01 ↔ 10.

From that, it is clear that b-amicable pairs can only be the pairs of words w (i) , w (i+b) , i = 1, . . . , M + 1 -b, with exceptions, namely those indices i, such that the interval J i ∪ • • • ∪ J i+b contains in its interior the iteration T -M +1 ε (ε). However, since we do not know the position of this point, it is difficult to determine the number of these exceptions, but it is at least one. Therefore the number of b-amicable pairs is at most Mb.

2

Now we are ready to prove the upper bound from Theorem 2.

Theorem 9

The number of 3iet factors of length N satisfies

#3iet(N ) ≤ 2 π 2 N 4 + O(N 3+δ )
for arbitrary δ > 0.

Proof: Combining Proposition 5 and Lemma 8, we see that

#3iet(N ) = N b=0 #3iet(N, b) = N b=0 # b-amicable pairs of length (N + b) ≤ ≤ N b=0 K∈Z N +b,b # b-amicable pairs of length (N + b) in the class K ≤ ≤ N b=0 N #Z N +b,b .
Putting in the estimate on #Z N +b,b from Lemma 7, we obtain

#3iet(N ) ≤ N N b=0 3 π 2 (N -b)(N + b) + N N b=0 O (N + b) 1+δ = = 3 π 2 N N 2 (N + 1) - 1 6 N (N + 1)(2N + 1) + O(N 3+δ ) = = 2 π 2 N 4 + O(N 3+δ ) . 2 6
The lower bound

Consider the following geometric representation of Sturmian and 3iet words by cut-and-project sequences. Given a strip in the Euclidean plane parallel to the (irrationally oriented) straight line y = εx, take all points of the lattice Z 2 and project them orthogonally to the straight line. It is known [START_REF] Langevin | Stimulateur cardiaque et suites de Farey[END_REF][START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF] that in such a way, one obtains a sequence of points with two or three distances between them. If the distances are two, say ∆ 1 , ∆ 2 , we can code them by two letters, and the resulting word is a Sturmian word. If the distances are three, they are of the form ∆ 1 , ∆ 2 , ∆ 1 + ∆ 2 . Coding these distances by three letters, we obtain a 3iet word. Moreover, Sturmian word is obtained only for a discrete set of values of the width of the considered strip. For details about this construction we refer to [START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF]. On the other hand, any Sturmian word u ε,x0 or a 3iet word u ε, ,x0 can be represented in this way, the parameter ε being the slope of the straight line and corresponding to the width of the strip [START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF][START_REF] Langevin | Stimulateur cardiaque et suites de Farey[END_REF]. If without loss of generality we take ε ∈ (0, 1), the widths of the strips giving rise to Sturmian words form a sequence

• • • < max{ε, 1 -ε} < 1 < 1 + ε < • • •
All parameters in between these values yield 3iet words. This geometric representation is illustrated in Figure 4, where 1 < 2 are two consecutive discrete values for which the cut-and-project scheme yields a Sturmian word. Projections of points in the strip S 1 with parameter 1 correspond to a Sturmian word u (1) over the alphabet {A, B}, where A stands for the projection of the horizontal side and B of the diagonal of a unit square. The strip S 2 corresponding to the value 2 gives a Sturmian word u (2) over {A, C}, where again, A is the projection of the horizontal side and C of the vertical side of the unit square. Note that the projection of a diagonal is the sum of projections of the vertical and horizontal sides. This corresponds to the fact that the infinite word u (2) arises from u (1) by replacing every B by AC.

Any strip S such that S 1 ⊂ S ⊂ S 2 gives rise to a 3iet word over the alphabet {A, B, C} where only some letters B have been replaced by AC. Enlarging the strip S from S 1 to S 2 causes more and more lattice points to fall into S and thus to split more and more distances B into CA. This procedure is illustrated in Figure 5 on a finite segment taken from Figure 4. To estimate the number in the right part of the equation, we use the relation [START_REF] Cassaigne | Sequences with grouped factors. Developments in Language Theory III (DLT'97)[END_REF]. Let us mention that an asymptotic formula for the number of Sturmian factors w with given |w| and |w| 1 was derived in [START_REF] Bédaride | On the number of balanced words of given length and height over a two-letter alphabet[END_REF].

Lemma 11

The number H M,b of Sturmian factors of length M with at least b letters 1 satisfies

H M,b ≥ 1 π 2 (M -b)M 2 + O(M 2+δ
) , for any δ > 0 .

Proof: Let f i be the i-th Farey fraction f i = pi qi . Consider the set

L (i) M . By Lemma 3, if b ≤ M -M f i -1, then every factor in L (i)
M has at least b letters 1. The inequality M -M f i -1 ≥ b can be rewritten as

p i ≤ M -b -1 M q i . (11)
By [START_REF] Boshernitzan | An extension of Lagrange's theorem to interval exchange transformations over quadratic fields[END_REF], the number of Farey fractions with the same denominator q = q i ≤ M satisfying ( 11) is equal to

M -b -1 M ϕ(q) + O(q δ ) , for any δ > 0 . (12)
Since the values of Farey fractions increase with i, there exists a maximal index, say s, such that every factor in the set

s i=0 L (i)
M has sufficient number of letters 1. Therefore

H M,b ≥ # s i=0 L (i) M .
In order to determine the cardinality of this union, we write it as a disjoint union, namely

s i=0 L (i) M = L (0) M ∪ s i=1 L (i) M \ L (i-1) M . Since #L (i) M = q i and #L (i-1) M
= q i-1 and equality (9) holds, we obtain

# L (i) M \ L (i-1) M = M + 1 -q i-1 , which implies H M,b ≥ 1 + s i=1 (M + 1 -q i-1 ) = s i=0 (M + 1 -q i ) -M + q s .
We group summands with the same values of q i = q. The number of such summands (for each q) is given by [START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF]. Therefore

H M,b ≥ M q=1 (M + 1 -q) M -b -1 M ϕ(q) + O(M 2+δ ) = = M -b M M 3 π 2 + O(M 2+δ ) ,
where we have used [START_REF] Berstel | A geometric proof of the enumeration formula for Sturmian words[END_REF]. The result easily follows. 2

The following theorem provides a slightly better lower bound on #3iet(N ) than that announced in Theorem 2. Instead of the constant 1 3 we obtain Proof: Combining the formula from Proposition 10 and Lemma 11, we have

#3iet(N ) ≥ 2 N/2 b=0 H N -b,b ≥ 2 π 2 N/2 b=0 (N -2b)(N -b) 2 + N/2 b=0 O (N -b) 2+δ = = 2 π 2 N/2 b=0 (N 3 -4N 2 b + 5N b 2 -2b 3 ) + O(N 3+δ ) = = 2 π 2 N 3 N 2 -4N 2 (N/2) 2 2 + 5N (N/2) 3 3 -2 (N/2) 4 4 + O(N 3+δ ) = = 2N 4 π 2 1 2 - 1 2 + 5 24 - 1 32 + O(N 3 log N ) = 17 48π 2 N 4 + O(N 3+δ ) .

7 Precise values for small lengths

We have seen for Sturmian words, that given N ∈ N, the interval (0, 1) of possible values of the parameter ε was divided into N k=1 ϕ(k) areas such that all Sturmian words with parameter within one area had the same set of N + 1 factors of length N . Similarly, one can expect that the family of possible pairs of parameters ε ∈ (0, 1) and ∈ max{ε, 1 -ε}, 1 will be divided into regions with the same set of factors of length N . The number of factors of a 3iet word with parameters in the interior of the regions will be equal to 2N + 1.

Let us describe the way to obtain the list of factors of length N for fixed parameters ε, . Denote d 1 = ε, d 2 = -1 + ε, the discontinuity points of the transformation T ε, . The domain of T ε, , namely [0, ), is divided by points T -j ε, (d 1 ), T -j ε, (d 2 ), j = 0, 1, . . . , N -1 generically into 2N + 1 subintervals. (This happens for ∈ Z + Zε and for small N also for other . Otherwise, some of these iterations coincide and the number of subintervals is smaller.) Each of these subintervals corresponds to one factor of length N occurring in the language of the infinite word u ε, ,x0 for any x 0 . The ordering of iterations T -j ε, (d 1 ), T -j ε, (d 2 ) in [0, ) depends on parameters ε, ; different orderings give rise to different lists of 3iet factors. Values of ε, providing the same ordering are given by linear inequalities in ε, . Figure 6 shows the division of the region of parameters ε, by these inequalities for factors of length 2. The set of all 3iet factors of length 2 is the union of lists given in the figure, i.e., 3iet(2) = {AA, AB, AC, BA, BB, BC, CA, CB, CC} , and #3iet(2) = 9 . In Figure 7, we give the same analysis for factors of length N = 3. Note that the region and its division into areas according to factors of given length must be symmetric with respect to the axis ε = 1/2. This corresponds to interchange of letters A ↔ C in all the factors. Figure 7 shows only one half of the picture.

The lists of factors of length 3 in individual areas of Figure 7 are given as follows. As we have proved above, asymptotically, the values from the last string of the table should fall between 17/48 and 2. It seems from the table that these bounds start to hold quite early, and perhaps it is possible to improve them.

  1365-8050 c 2011 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

  i) Usually one defines exchange of three intervals of lengths α, β, γ > 0 satisfying α + β + γ = 1. Our choice of parameters (3) implies relation α + 2β + γ = 1, where ε = α + β and = α + β + γ.

Fig. 1 :

 1 Fig. 1: Classes of Sturmian words of length 4.

Corollary 6

 6 A 3iet factor w of length N with precisely b letters B corresponds to a b-amicable pair of Sturmian factors of length N +b. Obviously, different b-amicable pairs give rise to different 3iet factors. Therefore we can express the number of 3iet words as the number of corresponding b-amicable pairs. Proposition 5 Let N ∈ N. Then #3iet(N ) = N b=0 #3iet(N, b) = N b=0 # b-amicable pairs of length (N + b) , where 3iet(N, b) denotes the set of 3iet factors of length N with precisely b letters B. Let us focus on b-amicable pairs of Sturmian factors. First, it is obvious that words which form a bamicable pair must both contain at least b letters 0 and b letters 1. As a consequence of Lemma 3, we have the following statement. Let b, M ∈ N and let ε be an irrational in (f i , f i+1 ), where f i , f i+1 are consecutive Farey fractions of order M . If L M (ε) contains a b-amicable pair, then b ≤ min M f i + 1, M -M f i . Lemma 7 Let Z M,b be the family of classes of Sturmian words of length M containing at least one b-amicable pair. Then for M < 2b we have #Z M,b = 0, and otherwise, #Z M,b ≤ 3 π 2 (M -2b)M + O(M 1+δ ) , for arbitrary δ > 0 .

Lemma 8

 8 Let ε ∈ (0, 1) be irrational. Let b, M ∈ N, 2b ≤ M . Then the number of distinct b-amicable pairs in class L M (ε) is at most Mb.

Fig. 4 :

 4 Fig. 4: Geometric representation of Sturmian and 3iet words by cut-and-project sequences.

Fig. 5 : 2 N/ 2 b=0#

 522 Fig. 5: Construction of 3iet factors with given number of letters C by substituting AC for suitable letters B in a Sturmian factor. Let now w (1) ∈ {A, B} * be a Sturmian factor of length M with at least b letters B, b ≤ M . By a suitable choice of the enlarged strip S, we obtain from w (1) a 3iet factor w of length M + b containing exactly b letters C. Such a word w satisfies |w| A ≥ |w| C , where the equality holds only if w = (CA) M . Since the role of letters A and C is symmetric over the set of all 3iet factors, the interchange A ↔ C in the factor w gives again a 3iet factor. Denoting by H M,b the number of Sturmian factors of length M with at least b letters B, we can summarize the above considerations by saying that

1 Ω 2 Ω 3 Ω 4 p 1 p 2 p 3 p 1 :

 123431 = 2ε, p 2 : ε = 1 2 , p 3 : = 2(1 -ε).

Ω 1 : 4 :Fig. 6 :

 146 Fig. 6: Division of the region of parameters ε, by inequalities for factors of length 2 and the corresponding lists of factors.

Ω 1 : 5 : 6 : 7 :Fig. 7 :

 15677 Fig. 7: Division of the region of parameters ε, by inequalities for factors of length 3.

Acknowledgements

We acknowledge financial support by the Czech Science Foundation grant 201/09/0584 and by the grants MSM6840770039 and LC06002 of the Ministry of Education, Youth, and Sports of the Czech Republic. The second author was supported also by RFBR grant 09-01-00244.


Sylwia Cichacz

Jakub Przybyło
email: przybylo@wms.mat.agh.edu.pl.

Irregular edge coloring of 2-regular graphs †

Keywords: irregular edge coloring, irregular coloring number, 2-regular graph, point distinguishing index

Let G be a simple graph and let us color its edges so that the multisets of colors around each vertex are distinct. The smallest number of colors for which such a coloring exists is called the irregular coloring number of G and is denoted by c(G). We determine the exact value of the irregular coloring number for almost all 2-regular graphs. The results obtained provide new examples demonstrating that a conjecture by Burris is false. As another consequence, we also determine the value of a graph invariant called the point distinguishing index (where sets, instead of multisets, are required to be distinct) for the same family of graphs.

Introduction

Consider a simple (without loops and multiple edges) undirected graph G. Let C be a color set, w : E(G) → C an edge coloring, and let M S w (v) denote the multiset of colors of all the edges incident with a vertex v in G. A coloring w is said to be irregular or vertex distinguishing if for any two distinct vertices u, v of G the corresponding multisets hold M S w (u) = M S w (v). We ask for the minimal number of colors needed to obtain an irregular edge coloring and we call it the irregular coloring number. Moreover, we denote by c(G) the irregular coloring number of a given graph G. Note that such a coloring does not exist at all if G contains an isolated edge or more than one isolated vertex. In such a case we set c(G) = ∞.

The irregular coloring number has also another interesting interpretation, and was introduced by Aigner and Triesch in [START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF] as a variant of another widely studied (in more than 40 papers, e.g. [START_REF] Chartrand | Irregular networks[END_REF][START_REF] Frieze | On Graph Irregularity Strength[END_REF][START_REF] Nierhoff | A tight bound on the irregularity strength of graphs[END_REF][START_REF] Przybyło | Irregularity strength of regular graphs[END_REF][START_REF] Przybyło | Linear bound on the irregularity strength and the total vertex irregularity strength of graphs[END_REF]) parameter, the irregularity strength of graphs. Namely, if we consider labelings of edges of a given graph G with positive integers, c(G) can be defined as the minimal cardinality of such a subset of N (the set of labels) that allows us to distinguish all the vertices of G by the sums of labels of edges incident with them, see [START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF] for details.

To provide an example, let us recall that in [START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF] the irregular coloring number was determined to be equal to three for K n (n ≥ 3) and K n,n (n ≥ 2). Other results, mostly for connected graphs, such as paths, cycles (see [START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF]) or complete multipartite graphs (see [START_REF] Wittmann | Vertex-distinguishing edge-colorings of 2-regular graphs[END_REF]), are also known. These are however difficult to generalize in case of their nonconnected equivalents. On the other hand, a general bound from [START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF], c(G) ≤ |G| -1 for graphs with c(G) < ∞ other than a triangle, is far from being sharp for numerous families of graphs. In particular, Aigner, Triesch and Tuza proved in [START_REF] Aigner | Irregular assignments and vertex-distinguishing edge-colorings of graphs, Combinatorics '90[END_REF] that for k-regular graphs, c(G) ≤ Cn 1 k , where C is a constant dependent only on k (k ≥ 2) and n is the order of the graph. Again determining the exact value of the irregular coloring number, or at least the best possible constant C, proved to be complicated, even for 2-regular graphs. A representative of such a family is simply a disjoint union of cycles and can be denoted as G = C m1 ∪ . . . ∪ C mt , where C i is a cycle of length i. The following upper bound was established by Aigner et al.. This bound was already best possible except for an additive constant term. On the other hand, the role of this constant is crucial in face of a conjecture by Burris we mention below. Several exact results were then obtained for some special 2-regular graphs. Among others, in [START_REF] Cichacz | Decompositions of pseudographs into closed trails of even sizes[END_REF] and [START_REF] Cichacz | Irregular edge-colorings of sums of cycles of even lengths[END_REF] the irregular coloring number was determined for unions of cycles of exclusively even lengths. Earlier, a particular, but very important case (we refer to this result at the end of the paper, explaining its significance), was solved by Aigner and Triesch, [START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF]. Namely, they showed that c(tC 3 ) = min(min{r :

r 3 r-1 2
≥ t, r ≡ 5(mod 6)}, min{r :

r 3 r-1 2 -1 ≥ t, r ≡ 5(mod 6)})
, where tC 3 consists of t disjoint triangles. As usual, let δ(G) and ∆(G) stand for the minimum and the maximum, resp., degree of a given graph G. Additionally, let n d (or n d (G)) denote the number of vertices of degree d in G. Note that if there exists any irregular edge coloring of G with k colors, then, by the standard combinatorial formula for the number of multisets of a given size, we must have that

k + d -1 d n d (1)
for each d 1. The following Vizing-type conjecture was posed by Burris in her PhD thesis [START_REF] Burris | Vertex-distinguishing edge-colorings[END_REF].

Conjecture 3 ([7]

) Let G be a graph without isolated edges, containing at most one isolated vertex, and let k be the minimum integer such that k+d-1

d n d (G) for 1 d ∆(G). Then c(G) = k or k + 1.
The aim of this paper is to determine the irregular coloring number for almost all (except a finite number) 2-regular graphs, see Corollary 12. Consequently, we will obtain infinitely many counterexamples against Conjecture 3, which will lead to its reformulation in weaker versions, see Conjectures 13 and 14.

As another consequence of our reasoning we also determine the value of the graph invariant called the point distinguishing chromatic index, χ 0 (G), for the same family of graphs. This parameter, introduced by Harary and Plantholt [START_REF] Harary | The point-distinguishing chromatic index, Graphs and applications[END_REF], differs from c(G) only by the requirement that sets, S w (v), instead of multisets, M S w (v), are distinct for all the vertices of G, where w : E(G) → C is an edge coloring. One can easily verify that both parameters coincide in the case of 2-regular graphs. For related problems see [START_REF] Balister | Packing Circuits into K n[END_REF][START_REF] Balister | Vertex distinguishing edge colorings of graphs with (G) = 2[END_REF][START_REF] Bazgan | On the Vertex-Distinguishing Proper Edge-Colorings of Graphs[END_REF][START_REF] Burris | Vertex-Distinguishing Proper Edge-Colorings[END_REF].

Equivalent problem

The problem of determining the smallest number of colors for which there exists an irregular edge coloring is in the case of 2-regular graphs equivalent to a different one. To state this new problem clearly we have to first specify some notations. In our reasoning we will admit (simple) graphs containing possible additional single loops at some of the vertices. Though these are actually pseudographs, we still call them graphs. A loop at a vertex v of such a graph is then denoted by vv (since it is uniquely determined by v). Analogously, an edge with ends u and v is denoted by uv (or vu).

A trail of length n in a graph G is an alternating sequence v 0 e 0 v 1 e 1 . . . e n-1 v n of n + 1 vertices and n edges (or loops) of G such that the e i = v i v i+1 , 0 ≤ i < n, are pairwise distinct. We usually identify such a trail with the graph (subgraph) G spanned by its edges (and loops), i.e., where V (G ) = {v 0 , . . . , v n } and E(G ) = {e 0 , . . . , e n-1 }. In some cases we will write G simply as a sequence of its "consecutive" vertices v 0 v 1 . . . v n (where we will usually identify all the sequences corresponding to the same graph G ). Such a trail is called closed if v 0 = v n , or open otherwise. Obviously, some special representatives of trails are paths and cycles. Let us additionally assume that a single loop does not constitute a graph, hence a single loop is neither a closed trail, nor a cycle. Note that a closed trail may be regarded as an Eulerian graph, i.e., a connected graph with all the degrees being even integers (where a loop adds 2 to the degree of a vertex), while an open trail is just a connected graph with exactly two vertices of odd degrees. In general, we will call a graph even if the degrees of all its vertices are even integers. Now given an irregular edge coloring w : E → {1, . . . , k} of a 2-regular graph G = C m1 ∪ . . . C mt , we define the graph H of such a coloring as follows. Let its vertex set contain all the colors, hence V (H) = {1, . . . , k}, and let us draw an edge in H whenever colors i and j (i = j possibly) meet at some vertex in G. In other words, E(H) = {S w (v) : v ∈ V (G)}. Since our coloring is irregular, we never draw an edge (or loop) twice in H. It is also easy to observe that when we traverse consecutive vertices of a given cycle C mi , we obtain a closed trail in H as a result. Therefore, H is just a sum of t closed trails of lengths m 1 , . . . , m t , hence is an even subgraph of size G of a graph M k , where M k is defined to be the complete graph K k with a single loop added at each vertex. Conversely, if we have an even subgraph H of the graph M k which can be written as a sum of t edge disjoint closed trails of lengths m 1 , . . . , m t , then reversing our process, i.e., traversing each of these closed trails and painting the consecutive edges of the corresponding cycle from G with the colors of the vertices encountered in H, yields an irregular edge coloring of G. Thus we have reduced our problem to the following one.

Observation 4 For any 2-regular graph G = C m1 ∪ . . . C mt , the irregular coloring number is equal to the smallest k for which there exists a subgraph of the graph M k that is an edge disjoint sum of closed trails of lengths m 1 , . . . , m t . 2

Necessary condition

Consider a problem defined by Observation 4, where we want to determine the smallest possible k complying with the stated requirements for G = C m1 ∪ . . . C mt . Note that an obvious necessary condition for such a k is a requirement that there is at least one even subgraph of size m 1 + . . . + m t in M k . We must however require something more from such a subgraph. The number of its possible loops might be limited. It is because closed trails of length 3 cannot contain loops, a closed trail of length 4 may have at most one loop, the one of length 5, two loops, etcetera. A general function L on the maximal possible number of loops in a closed trail of length m (m ≥ 3) is the following.

L(m) =    0, for m = 3, 1, for m = 4, m 2
, for m ≥ 5. We may then denote that in total

L(m 1 , . . . , m t ) = L(m 1 ) + . . . + L(m t ).
On the other hand, we have only k loops available in M k . Combining these two facts, we obtain the following function L k on the maximal possible number of loops in the required even subgraph of M k .

L k (m 1 , . . . , m t ) = min{k, L(m 1 , . . . , m t )}.
Finally, we obtain the following necessary condition.

Observation 5 For any collection of lengths m 1 , . . . , m t , m i ≥ 3, and any k, if there exists an even subgraph of size m 1 + . . .

+ m t in M k containing at most L k (m 1 , . . . , m t ) loops, then (1 • ) m 1 + . . . + m t ≤ k 2 -k 2 + L k (m 1 , . . . , m t ) if k is even, (2 • ) m 1 + . . . + m t ≤ k 2 + L k (m 1 , . . . , m t ) if k is odd and either k ≡ 5(mod 6) or m i ≥ 4 for at least one i, (3 • ) m 1 + . . . + m t ≤ k 2 and m 1 + . . . + m t = k 2 -1 if k ≡ 5(mod 6
) and m j = 3 for all j.

Proof: There are k 2 edges and k loops in M k . Since the subgraph whose existence we assumed cannot have more than L k (m 1 , . . . , m t ) loops, the bound from (2 • ) is obvious. In (1 • ) on the other hand, the degree of each vertex in M k is odd. Since our aim is to find an even subgraph of M k , we must additionally remove at least as many edges (loops do not change the degrees of the vertices) as there are in a perfect matching, that is k 2 , from M k . In (3 • ) in turn, which is a very special case, we have m 1 = . . . = m t = 3, hence L k (m 1 , . . . , m t ) = 0, and there is no even subgraph of K k (M k without loops) containing all except exactly one (that is k 2 -1) of its edges. 2

Now, consider for instance the lengths 3, 3, 6, 6 and k = 6. Then L 6 (3, 3, 6, 6) = 6 and 6 2 -6 2 + 6 = 18, hence our necessary condition (see (1 • )) is fulfilled. Nevertheless, as one can easily check, it is not enough for the existence of the edge disjoint closed trails of specified lengths in M 6 . Surprisingly, it occurs that for k large enough the necessary conditions from Observation 5 are also sufficient. This fact, which also allows us to determine the exact value of the irregular coloring number for almost all 2-regular graphs, is the main result of this paper, see Theorem 11 and Corollary 12.

It is worth noting that for the general case, not only starting from a given (large) n, it is known that c(G) ≤ √ 2n + 1 for any 2-regular graph, even if we require the coloring to be proper. This bound is off by at most two from the real value, and is a consequence of the following Corollary 1.2 from Balister [START_REF] Balister | Packing Circuits into K n[END_REF], with two additional simple cases that must be verified separately, i.e., G = C 8 and

C 4 ∪ C 4 . Theorem 6 ([3]) Let L = t i=1 m i , m i ≥ 3;
then we can write some subgraph of K N as an edgedisjoint union of closed trails of lengths m 1 , . . . , m t if and only if either

(1) N is odd, L = N 2 or L ≤ N 2 -3, or (2) N is even, L ≤ N 2 -N 2 .
4 The idea and lemmas

The main idea of the proof of Theorem 11 is based on the following result concerning simple graphs due to Balister.

Theorem 7 ([4]

) There exist absolute constant N and ε > 0 such that for any even simple graph G on n vertices with n ≥ N and δ(G) ≥ (1 -ε)n, and for any collection of integers m 1 , . . . , m t with m i ≥ 3 and

t i=1 m i = |E(G)|
, one can write G as the edge-disjoint union of closed trails T 1 , . . . , T t with T i of length m i for i = 1, . . . , t. In addition, given any fixed v ∈ V (G), we can also ensure that T 1 meets v.

Note that if we want to prove the sufficiency of the conditions (1 • )-(3 • ) from Observation 5, then given the lengths m 1 , . . . , m t , m i ≥ 3, of the cycles of a 2-regular graph and the corresponding k complying with (1 • )-(3 • ), our aim is to construct a subgraph of M k which is an edge disjoint sum of closed trails of the given lengths (compare also with Observation 4). A natural approach is now to first find a ("small") number of necessary closed trails in M k "covering" all the loops we should use in our construction. If we are able to do it using not too many (bounded by a constant) edges at each vertex, then after removing them (together with all the loops) from M k , we will be able to use Theorem 7 above for the resulting graph and the remaining set of lengths, provided that k is large enough.

A realization of the first part of this plan is contained in Lemma 10. It is preceded by the following two auxiliary lemmas. First of them will help us to "close" open trails of odd lengths by joining their ends with paths of length two. The second, in turn, will be used later in the construction of closed trails of lengths four taking form of the triangles with single loops.

Lemma 8 Let G be a simple graph of order n ≥ 51 and with minimum degree δ ≥ n -11, and let U be a set of at most n 2 disjoint pairs of its vertices {{x 1 , y 1 }, . . . , {x k , y k }} (x i = y i ). Then there exist vertices z 1 , . . . , z k such that x i z i y i , i = 1, . . . , k, form a set of k edge disjoint paths of length 2 in G, and that G obtained from G by removal of all the edges of these paths has minimum degree δ ≥ n -14.

Proof: It is sufficient to choose pairwise distinct z 1 , . . . , z k such that x i z i y i , i = 1, . . . , k, are the edge disjoint paths in G. Assume then that U is a maximal subset of U for which we can find vertices z i (or equivalently paths of length two) complying with these requirements, and let Z be the set of the middle vertices of the obtained paths. Suppose that U = U (hence |U | = |Z | ≤ n 2 -1) and let {x, y} ∈ U U . Now, to complete the proof, it is sufficient to get a contradiction by finding a path complying with our requirements for this pair of vertices. Note that any element z ∈ M := N G (x) ∩ N G (y) constitute a middle vertex of some path of length 2 in G with endpoints x and y. A given such z cannot be used in construction of the desired path by one of the two following reasons. First of all we need to exclude z ∈ Z (since z i must be pairwise distinct). Second, we need to eliminate the ends of these (at most two) potential paths from U in which x or y might be a middle vertex (since the paths are supposed to be edge disjoint), i.e., at most four vertices. Consequently, we are still left with at least

|M | -|Z | -4 ≥ (2δ -n) -( n 2 -1) -4 ≥ n -22 -( n 2 -1) -4 > 0 appropriate candidates for z, a contradiction. 2
Lemma 9 Let G be a simple graph of order n ≥ 34 and with minimum degree δ ≥ n -5, and let W = {v 1 , . . . , v l } be a subset of its vertices. Then there exist l edge disjoint triangles, H 1 , . . . , H l , in G such that v i is a vertex of H i for each i, and that G obtained from G by removal of all the edges of these triangles has minimum degree δ ≥ n -11.

Proof: It is sufficient to show our assertion in the case when W = V (G). By the Dirac condition, the graph G contains a Hamilton cycle C. To prove the theorem, for each vertex v i ∈ W = V (G) we will choose a distinct edge e i = u i w i of the cycle C such that ∆ i = v i u i w i forms a triangle in G (then each vertex will belong to exactly three of these triangles), v i u i , v i w i / ∈ E(C), and that the triangles obtained are edge disjoint. Let W be a maximal size subset of W for which we can choose such edges (or equivalently triangles). Denote by E the set of these edges (E ⊆ E(C)), and let H be the set of the corresponding triangles. For a given vertex v , let T v denote the set of the edges of C whose ends span in G triangles together with v , each containing exactly one edge of C.

Then |T v | ≥ n -2(n -δ) -2 = 2δ -n -2.
It is because each vertex which is not adjacent with v meets, hence excludes, at most two of the n edges of C, and we additionally exclude the two edges of C which might span, together with v , triangles containing more than one edge of C in G. Analogously, for a given edge e = u w of C, let T e denote the set of the vertices spanning in G triangles together with e , each containing exactly one edge of C, hence

|T e | ≥ |N G (u ) ∩ N G (w )| -2 ≥ 2δ -n -2.
Suppose now that the theorem is false, hence W = W (W = V (G)), and let v ∈ W W . Then at least one edge of C, say e = uw, does not belong to any of the triangles from H. Note that by the maximality of W , there cannot exist an edge xy ∈ T v E such that vxy is a triangle in G which is edge disjoint with all the triangles from H. Denote then by F the set of these edges xy ∈ T v ∩ E for which the triangle vxy is edge disjoint with all the triangles from H except the one containing xy. Observe that if x y ∈ T v F , then x y must be incident with one of at most two triangles of H containing v, hence there can be at most 4 such edges in

T v . Consequently, |F | ≥ |T v | -4 ≥ 2δ -n -6.
Analogously, by the maximality of W , there cannot exist a vertex z ∈ T e W such that zuw is a triangle in G which is edge disjoint with all the triangles from H. Denote by U the set of these vertices z ∈ T e ∩ W for which the triangle zuw is edge disjoint with all the triangles from H. Observe that if z ∈ T e U , then zu or zw must be an edge of a triangle from H, hence there are at most 6 such vertices in T e . It is because each of the vertices u, w is incident with at most three edges of the triangles from H which do not belong to C (contained in at most two triangles from H for each of them). Consequently,

|U | ≥ |T e | -6 ≥ 2δ -n -8, hence |F | + |U | ≥ 4δ -2n -14 ≥ 2n -34 ≥ n = |W | > |W |.
Therefore, since F ⊆ E and U ⊆ W , the set H must contain a triangle ∆ j = v j u j w j such that v j ∈ U and u j w j ∈ F . Then, by the definitions of F and U , ∆ = vu j w j and ∆ = v j uw form triangles in G which are edge disjoint with the ones from H {∆ j }. Moreover, ∆ and ∆ are also edge disjoint, since by the definition of U , the edges e = uw and u j w j must be independent. The obtained collection of triangles, (H {∆ j }) ∪ {∆ , ∆ }, contradicts the maximality of W . 2

Lemma 10 Let n ≥ 51 and let m 1 , . . . , m t ≥ 4 be integers such that s = t i=1 L(m i ) ≤ n. Then for any γ = 0, 1, 2 there exists a subgraph G of M n of maximum degree at most 12 (not taking loops into account) containing exactly s loops, which is an edge disjoint union of closed trails T 1 , . . . , T t of lengths m 1 , . . . , m t-1 , m t + γ, respectively.

Proof: In other words, we need to find t edge disjoint closed trails T 1 , . . . , T t of specified lengths in M n , such that their sum G is a graph of maximum degree at most 12 (not taking loops into account) which contains s loops.

First partition the sequence m 1 , . . . , m t-1 (note that we omit m t ) into three subsequences e 1 , . . . , e r , f 1 , . . . , f l , o 1 , . . . , o k containing all its even elements of lengths at least 6, all elements equal to four, and all odd elements, respectively (hence e i ≡ 0(mod 2), e i ≥ 6, f i = 4 and o i ≡ 1(mod 2) for all i).

Let G = M n , G = (V, E), and let V = {a 1 , . . . , a n }. Then C = a 1 . . . a n a 1 forms a Hamilton cycle in G. We begin our construction from the first of the subsequences. Note that r i=1 ei 2 = r i=1 L(e i ) ≤ n -L(m t ). Therefore, we can construct the first r closed trails one after another by simply taking consecutive blocks of ei 2 , i = 1, . . . , r, vertices on the Hamilton cycle C together with the edges of this cycle joining these vertices, then closing each of the obtained paths up by adding the edge joining its ends, and finally attaching all the loops adjacent with it. This way, the first trail E 1 of length e 1 is of the form a 1 a 1 a 2 a 2 . . . a L(e1) a L(e1) a 1 and contains loops at the vertices a 1 , . . . , a L(e1) . Subsequently, the trail E 2 of length e 2 is defined by the sequence a L(e1)+1 a L(e1)+1 a L(e1)+2 a L(e1)+2 . . . a L(e1)+L(e2) a L(e1)+L(e2) a L(e1)+1 , etcetera. Now take L(m t ) consecutive (after those already used) vertices on the Hamilton cycle C and join them with a path (in particular we may have a path reduced to one point when L(m t ) = 1), adding to this path all the loops encountered. To create a closed trail of length m t + γ from this open trail, we join its ends with a path avoiding the edges of the cycle C (and the edges already used) of length at most γ + 3 ≤ 5. Since we still have a very dense graph (even after removing the edges already used in our construction and all the edges of C), it is easy to find such a path using a greedy algorithm (taking at each step the first "suitable" vertex/edge). This way we have already constructed the closed trails containing r i=1 L(e i ) + L(m t ) consecutive loops of the Hamilton cycle. Moreover, each vertex of G meets at most 4 edges (and at most one loop) from the sum of these trails.

Let v 1 , . . . , v l be the subsequent l consecutive vertices on the Hamilton cycle C (with loops at them unused), and denote W = {v 1 , . . . , v l }. Then v l = a q for some q ≤ n. Let us temporarily remove from G the edges a q+1 a q+2 , a q+2 a q+3 , . . . , a n-1 a n (we may need them in the further part of our construction), all the edges of the closed trails already constructed and all the (n) loops. Denote the graph obtained by G 1 . Note that δ 1 ≥ n -5, where δ 1 is the minimum degree of G 1 . Let H be the collection of triangles in G 1 guaranteed by Lemma 9. Joining these triangles with the loops at v 1 , . . . , v l , resp., we obtain the desired closed trails of length four (f 1 , . . . , f l = 4) in G.

Remove from G 1 the edges of the triangles from H and denote the graph obtained by G 2 . By Lemma 9, which we have used, its minimum degree is at least n-11. Now add back the edges a q+1 a q+2 , a q+2 a q+3 , . . . , a n-1 a n together with the loops incident with them to this graph. We will use some of them to create open trails of lengths o 1 -2, . . . , o k -2, which will be then completed to form the desired closed trails. Again we do it by simply taking the proper consecutive bits of C together with all the incident loops. For instance, the first of such open trails is of the form a q+1 a q+1 a q+2 a q+2 . . . a L(o1) a L(o1) (since o 1 is odd, L(o 1 ) = o1-1

2 ). Let {{x 1 , y 1 }, . . . , {x k , y k }} be the pairs of the corresponding ends of these open trails, and let us remove all the edges of these trails and all the remaining loops. Since we have just removed only some part of the edges (and loops) which we had formerly added back to G 2 , we still have δ 3 ≥ n -11, where δ 3 is the minimum degree of the obtained graph G 3 . By Lemma 8 we can now easily find k edge disjoint paths of length 2 that complete our construction of the trails of lengths o 1 , . . . , o k . Moreover, these paths can be chosen in such a way that if we remove their edges from G 3 , then the minimum degree of the graph obtained will be at least n -14. Since initially all the vertices of G had degree n -1 (not taking loops into account), then the graph obtained as a sum of all the closed trails constructed has maximum degree at most 13 (not taking loops into account) and exactly s loops. Finally, since such a graph is even, its maximum degree cannot in fact exceed 12 (not taking loops into account). 2

Main result

Theorem 11 There exists an absolute constant K such that for any k ≥ K the following conditions are sufficient for existence of a subgraph of M k which is an edge disjoint union of closed trails of lengths m 1 , . . . , m t , where m i ≥ 3.

(

• ) m 1 + . . . + m t ≤ k 2 -k 2 + L k (m 1 , . . . , m t ) if k is even, ( 1
• ) m 1 + . . . + m t ≤ k 2 + L k (m 1 , . 2
. . , m t ) if k is odd and either k ≡ 5(mod 6) or m i ≥ 4 for at least one i,

(3 • ) m 1 + . . . + m t ≤ k 2 and m 1 + . . . + m t = k 2 -1 if k ≡ 5(mod 6
) and m j = 3 for all j.

Proof: Let N and ε be the constants from Theorem 7. Assume that N 0 ≥ N is the smallest integer such that k -16 ≥ (1 -ε)k for each k ≥ N 0 , and let K = max{N 0 , 51}. We shall prove that this K complies with our requirements. Assume that the lengths m 1 , . . . , m t are ordered in such a way that all threes are placed at the end of the sequence. Let n = t i=1 m i , L = L k (m 1 , . . . , m t ), and assume that k ≥ K complies with the assumptions of the theorem, hence (1 • )-(3 • ) are fulfilled. We will first use Lemma 10 to find in M k closed trails "covering" all the loops we want to use in our construction. In most of the cases this will be exactly L loops, but in some special situations we shall limit this number to L -1 or L -2.

Assume first that k is odd. Below we define the value of a constant L (L ≤ L), dependent on the given cases. This in fact will be the number of loops which we will use while applying Lemma 10. Let

L = L if n -k 2 ≤ L -3 and L = n -k 2 otherwise.
Note that L ≥ 0 in all these cases. It is obvious for L = L. For L = L -1, on the other hand, if we had L < 0, hence L = 0, then n = k 2 + 0 -1 would have to be divisible by 3 (because if L = 0, then m i = 3 for all i). Consequently, we would get a contradiction with (3 • ), since k 2 -1 is divisible by 3 (k odd) only for k ≡ 5(mod 6). Finally, for L = L -2, if we had L < 0, then we would analogously as above either obtain k 2 -2 = 3t (for L = 0) or k 2 + 1 -2 = 3t + 1 (for L = 1). In both cases we obtain a contradiction with the fact that k 2 -2 is never divisible by three. Let s be the least integer (s ≥ 0) such that

L(m 1 ) + . . . + L(m s ) ≥ L .
Let m s ≤ m s be the least integer so that s-1 i=1 L(m i ) + L(m s ) = L , and set γ = m s -m s if m s -m s ≤ 2, or γ = 0 otherwise. By Lemma 10 there exists a subgraph G of M k of maximum degree at most 12 (not taking loops into account) containing exactly L loops, which is an edge disjoint union of closed trails T 1 , . . . , T s of lengths m 1 , . . . , m s-1 , m s + γ, respectively. Let G be a graph obtained from M k by removing all the edges of G and all the (k) loops. Since M k (k odd) is an even graph, G is an even graph as well. Moreover, δ(G ) ≥ k -13. Note that by our construction (by the choice of L actually), either m s -m s -γ

+ t i=s+1 m i = ||G ||, or m s -m s -γ + t i=s+1 m i ≤ ||G || -3, hence there exists m t+1 such that m s -m s -γ + t+1 i=s+1 m i = ||G || and m t+1 = 0 or m t+1 ≥ 3.
By Theorem 7, G can be written as the union of closed trails of lengths m s -m s -γ, m s+1 , . . . , m t+1 (where we ignore the lengths equal to 0 if there are any), such that the closed trail of length m s -m s -γ contains any fixed vertex v of the formerly constructed closed trail T s . By joining these two trails together, we obtain a one of length m s , hence complete the construction. (Note that the closed trail of length m t+1 plays only a technical role in our reasoning.)

Assume now that k is even. This time we shall use exactly L loops while applying Lemma 10. Let then analogously as above s be the least integer (s ≥ 0) such that

L(m 1 ) + . . . + L(m s ) ≥ L.
Let m s ≤ m s be the least integer so that

m s -m s -γ + t+1 i=s+1 m i ∈ {||G || - k 2 , ||G || - k 2 -1, ||G || - k 2 -2}. (2)
In order to apply now Theorem 7, we need to first modify the graph G by removing some edges from it, so that it is even and have a proper size (i.e., m s -m s -γ+ t+1 i=s+1 m i ). If the sum in (2) equals ||G ||-k 2 , we simply remove a perfect matching, that is k 2 independent edges, from G . Its existence is guaranteed e.g. by the Dirac condition for hamiltonicity (G still has "large" minimum degree compared to its order). In the remaining two cases, we first remove a star K 1,3 (for ||G || -k 2 -1), or two independent stars K 1,3 (for ||G || -k 2 -2), and then a matching of the remaining (all except the ones in the stars) vertices from G . Since then we obtain a simple even graph of the desired size and with the minimum degree δ ≥ k -16, we analogously as above finish our proof by first applying Theorem 7 to this graph, and then joining the obtained closed trails of lengths m s -m s -γ and m s + γ. We must point out here that K from Corollary 12 above is very large. It is due to its dependency on the size of N , which is very large, and , which is extremely small, from Theorem 7 of Balister. In particular ≤ 10 -24 , hence K ≥ 16 • 10 24 , see [START_REF] Balister | Packing closed trails into dense graphs[END_REF] for more details and references. As we have already mentioned our result also provides many counterexamples disproving Conjecture 3. These include the case already pointed out in the introduction, i.e., G = tC 3 with 3t = r+1 for r ≡ 5(mod 6) or r ≡ 1(mod 6)). Nevertheless, we suspect that one of the following conjectures, the first of which implies the other, should hold.

Conjecture 13 Let G be a graph without isolated edges, containing at most one isolated vertex, and let k be the minimum integer such that k+d It is worth noting at the end that the question whether the conjecture by Burris holds for graphs with ∆(G) ≥ 3 remains open. A limited number of (small) examples with ∆(G) = 3 we have verified did not give a negative answer to that question.

Theorem 1 ( 2 √

 12 [START_REF] Aigner | Irregular assignments and vertex-distinguishing edge-colorings of graphs, Combinatorics '90[END_REF])Let G = C m1 ∪ . . . ∪ C mt be a simple 2-regular graph of order n = t i=1 m i . Then c(G) 9 √ n + O(1).It was then improved by Wittmann. Theorem 2 ([17]) Let G = C m1 ∪ . . . ∪ C mt be a simple 2-regular graph of order n = t i=1 m i . Then c(G) √ 2n + O(1).

s- 1 i=1

 1 L(m i )+L(m s ) = L, and let γ = m s -m s if m s -m s ≤ 2, or γ = 0 otherwise. By Lemma 10 there exists a subgraph G of M k of maximum degree at most 12 (not taking loops into account) containing exactly L loops, which is an edge disjoint union of closed trails T 1 , . . . , T s of lengths m 1 , . . . , m s-1 , m s + γ, respectively. Let G be a graph obtained from M k by removing all the edges of G and all the (k) loops. Note that m s -m s -γ+ t i=s+1 m i ≤ ||G ||-k 2 , where the degrees of all the vertices in G are odd. Let us define m t+1 = ||G ||-k 2 -(m s -m s -γ+ t i=s+1 m i ) if this number equals at least 3, or set m t+1 = 0 (for definiteness) otherwise. Consequently,

2 6 Conclusions 2 +

 62 By Observation 4, Observation 5 and Theorem 11 we obtain the following corollary.Corollary 12 Let G = C m1 ∪ . . . ∪ C mt be a 2-regular graph and let k be the smallest integer for which(1 • )-(3 • ) hold. If k ≥ K, then c(G) = k (hence also χ 0 (G) = k).2Consequently, we have determined the exact value of c(G) for all 2-regular graphs of order n > K-1 (K -1) = K 2 (where we must have taken the worst case (2 • ) into account), hence for all except a finite number. One can calculate that then c(G) ∈ { √ 2n -1, √ 2n , √ 2n + 1}, what can be conveniently confronted with the result by Wittmann, see Theorem 2.

2 - 1 2 -r+1 2 < 3t r+1 2

 2122 for any r ≡ 4(mod 6), where we should have c(G) ∈ {r, r + 1} according to Conjecture 3, while in fact, c(G) = r + 2, see[START_REF] Aigner | Irregular Assignments and Two Problems á la Ringel, Topics in Combinatorics and Graph Theory[END_REF] or Corollary 12. Many other counterexamples can however be derived from Corollary 12 (e.g., G = tC 3 with r+1

- 1 d

 1 n d (G) for 1 d ∆(G). Then c(G) ∈ {k, k + 1, k + 2}.Conjecture 14 There exists an absolute constant A such that for each graph G without isolated edges which contains at most one isolated vertex, if k is the minimum integer such that k+d-1 d n d (G) for 1 d ∆(G), then k ≤ c(G) ≤ k + A.

Acknowledgements

The authors would like to thank Paul Balister for his valuable suggestions.

Research supported by a grant N201 1247/33.


Li Peng

Bo Tan
email: botan@163.com

Sturmian Sequences and Invertible Substitutions †

Keywords:

It is known that a Sturmian sequence S can be defined as a coding of the orbit of ρ (called the intercept of S) under a rotation of irrational angle α (called the slope). On the other hand, a fixed point of an invertible substitution is Sturmian. Naturally, there are two interrelated questions: (1) Given an invertible substitution, we know that its fixed point is Sturmian. What is the slope and intercept? (2) Which kind of Sturmian sequences can be fixed by certain non-trivial invertible substitutions? In this paper we give a unified treatment to the two questions. We remark that though the results are known, our proof is very elementary and concise.

Introduction

Sturmian sequences are infinite words over a binary alphabet with minimal complexity, and these sequences admit several equivalent definitions under different names. In this paper, we adopt the following definition.

Let α ∈ [0, 1]\Q and ρ ∈ R. We define, for n ∈ N = {0, 1, 2, • • •}, S α,ρ (n) = α(n + 1) + ρ -αn + ρ , S α,ρ (n) = α(n + 1) + ρ -αn + ρ , and call S (resp. S ) the lower (resp. upper) Sturmian sequence with slope α and intercept ρ. Obviously, we can assume that ρ ∈ S := R/Z. It is easy to see that Sturmian sequences are over the alphabet A = {0, 1}. In other words, S, S ∈ A N , where A N is the set of infinite sequences over A.

Sturmian sequences are extensively studied by many authors, and excellent descriptions can be found in Chapter 2 of [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF] by J. Berstel & P. Séébold, and in Chapter 6 of [START_REF] Lothaire | Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications[END_REF] by P. Arnoux.

Let A = {0, 1} be the alphabet, and A * (resp. F (A)) stand for the free monoid (resp. free group) generated by A. The empty word ε is their identity element. For u ∈ A * , |u| denotes the length of u (thus |ε| = 0), and |u| i denotes the number of occurrences of the letter i in the word u. The mirror of a word

w = w 0 w 1 • • • w n-1 , where w i ∈ A, is the word w n-1 • • • w 1 w 0 .
A morphism τ : A * → A * is called a substitution of A * . Two substitutions τ and σ are said to be conjugate, if there is a word w ∈ A * such that τ (i)w = wσ(i) for any i ∈ A; or vice versa.

If a substitution τ can be extended to an automorphism of F (A), we say that it is invertible. In particular, an invertible substitution τ is non-erasing, that is, both τ (0) and τ (1) are different from ε.

On the structure of invertible substitutions, Wen & Wen [START_REF] Wen | Local isomorphisms of invertible substitutions[END_REF] showed that any invertible substitution is a composition of the following three substitutions: π = (1, 0), σ = (01, 1) and φ = (10, 0), where the notation (u, v) denotes the substitution 0 → u, 1 → v.

A substitution τ can also be extended to a mapping of A N . And τ is called Sturmian if τ (ξ) is a Sturmian sequence for any Sturmian sequence ξ. Mignosi & Séébold [START_REF] Mignosi | Morphismes sturmiens et règles de Rauzy[END_REF] proved that a Sturmian substitution is also a composition of the above three substitutions. Therefore, a substitution is Sturmian if and only if it is invertible.

A substitution is called non-trivial if it is not the identity. From the above results, we know that, given a non-trivial invertible substitution τ , if ξ is a fixed point of τ (i.e. τ (ξ) = ξ), then ξ is a Sturmian sequence (with the following exceptions of non-primitive substitutions: (01 n , 1) which fixes 01 ∞ , and (0, 10 n ) which fixes 10 ∞ ).

Naturally, we ask the following two interrelated questions: QUESTION 1. Given an invertible substitution with a fixed point, what is the slope and the intercept? QUESTION 2. Which kind of Sturmian sequence can be fixed by certain non-trivial substitutions?

The first question was tackled in Tan & Wen [START_REF] Tan | Invertible substitutions and Sturmian sequences[END_REF]. In fact, the slope is just the ratio of the frequencies of the two letters in the fixed point, and it is easy to determine via the substitution matrix. And the intercept is obtained by a very delicate comparison of the intercepts between the substitutions in a same conjugate class.

Yasutomi [START_REF] Yasutomi | On Sturmian sequences which are invariant under some substitutions[END_REF] gave a complete answer to the second question, by considering how the three elementary invertible substitutions change the slope and intercept of a Sturmian sequence. Later, Baláži, Masáková & Pelantová [START_REF] Baláži | Complete characterization of substitution invariant Sturmian sequences[END_REF] and Berthé, Ei, Ito & Rao [START_REF] Berthé | On substitution invariant Sturmian words: an application of Rauzy fractals[END_REF] gave alternative proofs of the characterization via the cutand-project scheme and the Rauzy fractal respectively. These proofs are somewhat technical and lengthy.

In this paper, we recall a characterization of the invertible substitution, and then provide a unified treatment to the two questions. With help of the characterization, our proofs are very elementary and concise.

Auxiliary Results

The shift function is the mapping T :

A N → A N defined by T (x 0 x 1 x 2 x 3 • • •) = x 1 x 2 x 3 • • •.
And the shift changes the intercept of a Sturmian sequence in an obvious way. Lemma 2.1 We have that T S α,ρ = S α,α+ρ , T S α,ρ = S α,α+ρ .

We mention several special cases: S α,α = S α,α , called the characteristic sequence and also denoted by

C α ; S α,0 = 0C α , S α,0 = 1C α ; S α,1-α = 10C α , S α,1-α = 01C α .
The next lemma is also readily checked.

Lemma 2.2 If ρ n → ρ + (in S), that is, ρ n tends to ρ in S anticlockwisely, then S α,ρn → S α,ρ and S α,ρn → S α,ρ ; If ρ n → ρ -(in S), then S α,ρn → S α,ρ and S α,ρn → S α,ρ .

The following characterization of invertible substitutions is shown in [START_REF] Tan | Invertible substitutions and Sturmian sequences[END_REF], which is essentially equivalent to the geometrical representation [START_REF] Ei | Decomposition theorem on invertible substitutions[END_REF]. The reader is referred to these papers for more details. 3 The slope and intercept of a substitutive Sturmian sequence

Let τ be an invertible substitution with a fixed point ξ. The substitution matrix of τ is defined as M = (|τ (j)| i ) i,j=0,1 . We will assume that M is primitive, and its Perron-Frobenius eigenvalue is denoted by λ. The slope and intercept of ξ are denoted by α and ρ respectively. In this section, given an invertible substitution τ , we calculate the slope α and intercept ρ. It is easy to determine α via the substitution matrix M .

Lemma 3.1 We have that M 1 -α α = λ 1 -α α . (1)
The following theorem on the intercept is due to [START_REF] Tan | Invertible substitutions and Sturmian sequences[END_REF] (under a big guise).

Theorem 3.2 Let τ be a primitive invertible substitution with a fixed point. With the above notations, we have that

ρ = 1 -α - 1 1 -λ (α, α -1)P (u) = 1 -α - 1 1 -λ (|u|α -(|u| + 1)α ), (2)
where P (u) = (|u| 0 , |u| 1 ) T is the Parikh vector of u; λ is the Galois conjugate of λ; and u is the word associated with τ as in Theorem 2.3.

Proof: For any n ∈ N, let (u n , v n ) be the pair associated with τ n , that is,

either τ n (01) = u n 01v n τ n (10) = u n 10v n or τ n (01) = u n 10v n τ n (10) = u n 01v n . Then u n = τ n-1 (u) τ n-2 (u) • • • τ (u) u; v n = v τ (v) • • • τ n-2 (v) τ n-1 (v). (3)
Thus, if v = , the limit lim n→∞ v n exists, say S. And then both 0S and 1S are Sturmian, which implies that S = C α (the characteristic word). Let here '⊂' is due to the facts that 0 ∈ [-α, 1 -α] and 0 < 1 -λ < 1. This implies that m = (n + 1)α .

Hence, ρ = 1 -α + 1 λ-1 (nα -(n + 1)α ). Again ρ is strictly monotone as a function of n. By arguing as in the proof of the necessity, ρ(0) = 1 -α and ρ( M -2) = α. Then from the range of ρ, we get

n ∈ {0, 1, • • • , M -2}.
This means that η is a fixed point of τ n in the conjugate class of τ (See Eq.( 4)).

In general, if

ρ ∈ 1 -α - 1 1 -λ K Z[α]
for some K ∈ Z + , the same argument (with τ K in place of τ ) shows that η is a fixed point of some substitution in the conjugate class of τ K . So it suffices to show

ρ ∈ 1 -α - 1 1 -λ K Z[α]
for some K ∈ Z + . Now we will show that for any ρ ∈ Q(α) there exist an integer K such that ρ ∈ 1 -α - Putting K = m -m, we have

(1 -λ K )β ∈ Z[α],
and this concludes the proof of the sufficiency. 2

Theorem 2 . 3

 23 Let τ be a substitution. Then τ is invertible if and only if there exist u and v ∈ A * , such that either τ (01) = u01v τ (10) = u10v or τ (01) = u10v τ (10) = u01v .

  ξ n := u n 10C α → η and ξ n := u n 01C α → η as n → ∞. Then both η and η are fixed points of τ . Let us remark that the conclusion also holds when v = . Moreover, if u = , then η = η ; if u = , then η = 10C α , and η = 01C α . Now by Lemma 2.1, ξ n = u n 10C α = S α,-(|un|+1)α , and ξ n = u n 01C α = S α,-(|un|+1)α . So ρ = lim -(|u n | + 1)α (in S).

K

  Z[α]. Put β := 1 -α -ρ ∈ Q(α). Take p ∈ Z + such that pβ ∈ Z[α]. From Eq.(1), we have λZ[α] ⊂ Z[α]. Since λ + λ ∈ Z, λZ[α] ⊂ Z[α]. Thus λ n ∈ Z[α].By Pigeonhole Principle, there exist m < m such that λm -λ m ∈ pZ[α]. Since λλ = det M = 1, 1 -λ m -m ∈ pλ m Z[α] ⊂ pZ[α].

From Eq.(3) we infer that |u n | = |τ n-1 (u) • • • τ (u)u| = (1, 1)(M n-1 + • • • + M + I)P (u). Since the left and right eigenvector associated with distinct eigenvalues respectively are orthogonal to each other, we obtain from Eq.( 1) that (α, α -1)M = λ(α, α -1). So,

Since both u0 and u1 are factors, the mirror word of u is a prefix of

It remains to show that ρ ∈ [0, 1] : Since

we only need to show ρ n ∈ (0, 1). This is the case because (α, α -

Let τ be invertible with det M = 1. Denote τ = M = |τ (01)|. If ϕ is a conjugate substitution of τ , then they have the same substitution matrix (thus have the same slope α), and the same word vu. Moreover, when ϕ runs through Con(τ ), the class of conjugate substitutions of τ , the length of the corresponding word u runs through all the integers between 0 and τ -2. so, by Theorem 3.2, we have (recalling that ρ(ϕ) is the intercept of the fixed point of ρ)

Let us consider some special cases:

Then ρ(ϕ) = 1 -α, and ϕ has two fixed points, namely 01C α and 10C α .

Then, Taking the lengths into account in the formula ϕ(01) = u01v, we get ϕ(0) = u0, so

Then P (u) = (M -I)(0, 1) T , ρ = 0, and ϕ fixes 0C α . Now (α, ρ) is already obtained for τ . It remains to distinguish that the fixed point is S α,ρ or S α,ρ .

• if ρ ∈ N -Nα, then S α,ρ = S α,ρ ;

• if ρ ∈ N-Nα, then, recalling ρ = 1-α+(α, α-1)(M -I) -1 P (u), we have (M -I) -1 P (u) ∈ Z 2 . So (M -I) -1 P (u) ∈ {(0, 0) T , (0, 1) T , (1, 0) T , (1, 1) T }, thus ρ ∈ {1 -α, 0, 1, α}.

And all these cases are already studied.

As a byproduct, we have shown the following well-known result.

Proposition 3.3 The Sturmian sequence S α,ρ is a fixed point of some non-trivial invertible substitution if and only if S α,ρ is also.

Characterization of substitutive Sturmian sequences

In this section, we give the proof of the following characterization which is due to Yasutomi [START_REF] Yasutomi | On Sturmian sequences which are invariant under some substitutions[END_REF].

, η be the Sturmian sequence with slope α and intercept ρ. Then η is a fixed point of some non-trivial substitution if and only if

• α is a Sturm number, i.e. a quadratic irrational with α ∈ (0, 1);

, and ρ is between α and 1 -α Proof: We first prove the necessity. Obviously, we have that α is a quadratic irrational, and λ ∈ Q(α) by Lemma 3.1. Taking complexconjugate in Eq.( 1) yields M

. By Perron-Frobenius Theorem, α > 1 or α < 0, that is α is a Sturm number. By Theorem 3.2, ρ = 1 -α - Now we continue the proof. Suppose (α, ρ) satisfies the conditions; η is the corresponding Sturmian sequence. Since α is Sturm, there exists τ which fixes C α by the preceding theorem. And replacing τ 2 by τ if necessary, we assume that det M = 1.

We will show that η is a fixed point of a non-trivial substitution by writing ρ in a suitable form.

Consider firstly the case that ρ ∈ 1 -α -