S Ébastien Ferenczi

BILLIARDS IN REGULAR 2n-GONS AND THE SELF-DUAL INDUCTION

Keywords: Mathematics Subject Classification. Primary 37B10; Secondary 11J70, 37A25, 37E05, 68R15. 1

 to the underlying one-parameter family of n-interval exchange transformations. This allows us to show that, in that family, for n = 3 non-periodicity is enough to guarantee weak mixing, and in some cases minimal self-joinings, and for every n we can build examples of n-interval exchange transformations with weak mixing, which are the first known explicitly for n > 6.

In [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], see also [START_REF] Smillie | Corinna Geodesic flow on the Teichműller disk of the regular octagon, cutting sequences and octagon continued fractions maps[END_REF], John Smillie and Corinna Ulcigrai develop a rich and original theory of billiards in the regular octagons, and more generally of billiards in the regular 2n-gons, first studied by Veech [START_REF] Veech | Teichmüller curves in moduli space, Eisenstein series and an application to triangular billiards[END_REF]: their aim is to build explicitly the symbolic trajectories, which generalize the famous Sturmian sequences (see for example [START_REF] Arnoux | Gérard Représentation géométrique de suites de complexité 2n + 1. (French) [Geometric representation of sequences of complexity 2n+1[END_REF] among a huge literature), and they achieve it through a new renormalization process which generalizes the usual continued fraction algorithm. In the present shorter paper, we show that similar results, with new consequences, can be obtained by using an existing, though recent, theory, the self-dual induction on interval exchange transformations.

As in [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], we define a trajectory of a billiard in a regular 2n-gon as a path which starts in the interior of the polygon, and moves with constant velocity until it hits the boundary, then it re-enters the polygon at the corresponding point of the parallel side, and continues travelling with the same velocity; we label each pair of parallel sides with a letter of the alphabet (A 1 , ...A n ), and read the labels of the pairs of parallel sides crossed by the trajectory as time increases; studying these trajectories is known to be equivalent to studying the trajectories of a one-parameter family of n-interval exchange transformations, and to this family we apply a slightly modified version of the self-dual induction defined in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF]. Now, the self-dual induction is in general not easy to manipulate, as its states are a family of graphs, and its typical itineraries, or paths in the so-called graph of graphs, are quite complicated to describe; but in our main Theorem 7 below, we show that for any non-periodic n-interval exchange in this particular family, after at most 2n -2 steps our self-dual induction goes back, up to small modifications, to the initial state of another member of the family. This gives us a renormalization process, which differs from the one in [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF] essentially because it is applied to lengths of intervals instead of angles, and allows us to compute the whole itinerary of the original interval exchange transformation under the self-dual induction in function of a single sequence of integers between 1 and 2n -1, which act as the partial quotients of a continued fraction algorithm applied to initial lengths of subintervals.

As a consequence we achieve the building of symbolic trajectories in a different way from [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], as we do not use our renormalization on lengths to get a renormalization of the trajectories, but rather use the full knowledge of the self-dual induction to build the trajectories by families of nested words, giving at once all the bispecial words and the names of a family of Rokhlin towers spanning the dynamical system. This in turn gives us original results on the weak mixing problem: namely for n = 3 we show that all non-periodic members of our family are weakly mixing, and that the boundedness of the partial quotients mentioned above implies the once famed property of minimal self-joinings, while for general n we build some sequences of partial quotients implying weak mixing, which give, as far as we know, the first construction of weakly mixing n-interval exchange transformations for n > 6; this last family of examples is built by using Rokhlin towers in a way which is innovating in comparison with the existing constructions such as those in [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF].

The present paper stems from an idea of Pascal Hubert, to whom the author is very much indebted; though the paper owes its very existence to [START_REF] Smillie | Corinna Geodesic flow on the Teichműller disk of the regular octagon, cutting sequences and octagon continued fractions maps[END_REF] [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], it does not use any result of those papers, and in this respect it is self-contained, though of course it relies heavily on [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], and on [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF][8] for one theorem. We choose to focus on the word-combinatorial point of view: the geometry underlying the self-dual induction, and thus a full comparison between the methods of the present paper and those of [START_REF] Smillie | Corinna Geodesic flow on the Teichműller disk of the regular octagon, cutting sequences and octagon continued fractions maps[END_REF] [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], will be treated in a forthcoming paper of Vincent Delecroix and Corinna Ulcigrai [START_REF] Delecroix | Corinna Diagonal changes for surfaces in hyperelliptic strata. A natural extension to the self-dual Ferenczi-Zamboni induction for iet[END_REF].

1. A short presentation of the self-dual inductions Definition 1. An n-interval exchange transformation I with probability vector (α 1 , α 2 , . . . , α n ), and permutation π is defined by

Ix = x + π -1 (j)<π -1 (i) α j - j<i α j .
when x is in the interval

∆ i = j<i α j , j≤i α j .

We denote by β

i , 1 ≤ i ≤ n -1, the i-th discontinuity of I -1 , namely β i = π -1 (j)≤π -1 (i) α j , while γ i is the i-th discontinuity of I, namely γ i = j≤i α j . Then ∆ i is the interval [γ i-1 , γ i [ if 2 ≤ i ≤ n -1, while ∆ 1 = [0, γ 1 [ and ∆ n = [γ n-1 , 1[. I satisfies the infinite distinct orbit condition or i.d.o.c. of Michael Keane [12] if the n -1 negative orbits {I -m γ i } m≥0 ,1 ≤ i ≤ n -1, of the discontinuities of I are infinite disjoint sets.
The self-dual induction is a process defined in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] for any n-interval exchange transformations which satisfies the i.d.o.c. condition, is symmetric, i.e. the permutation π is defined by πj = n+1-j, 1 ≤ i ≤ n, and has alternate discontinuities, i.e. β i < γ i for each 1 ≤ i ≤ n-1 and γ i < β i+1 for each 1 ≤ i ≤ n -2. It aims to build the points where the negative orbits of the discontinuities of I approximate the discontinuities of I -1 . Indeed, we want to build n -1 nested families of subintervals

E i,k = [β i -l i,k , β i + r i,k [, 1 ≤ i ≤ n -1, starting from E i,0 = ∆ i ,
so that the E i,k are the intervals containing β i , and whose endpoints are the successive I -m γ j which fall closest to β i , where for any j and j , I -m γ j is after I -m γ j if m > m. Let γ i,k be the first element I -m γ j , m > 0, 1 ≤ j ≤ n -1, which falls in the interior of E i,k ; it exists by minimality. Thus we could tentatively define E i,k+1 by partitioning E i,k into two subintervals [β i -l i,k , γ i,k [ and [γ i,k , β i + r i,k [, and setting E i,k+1 to be the one of these two subinbtervals which contains β i ; it is well defined because of the i.d.o.c. condition, see Proposition 1 below.

However, it may very well happen that, for example, γ 1,k = I -5 γ 1 while γ 2,k = I -2 γ 1 and γ 2kn+1 = I -3 γ 1 , which creates a desynchronisation between the tentatives E 1,k+1 and E 2,k+1 ; then it seems natural to wait before cutting

E 1,k , that is to put E 1,k+1 = E 1,k .
Thus, for each i and k, we decide either to put E i,k+1 = E i,k or to define E i,k+1 as the subinterval

[β i -l i,k , γ i,k [ or [γ i,k , β i + r i,k [ which contains β i .
There are many possible decisions of cutting or not at each stage, and thus a priori many self-dual inductions; however, for a given interval E = E i,k , the first strict subinterval of E to be generated by any self-dual induction is the same, independently of the decisions; thus all sequences of decisions for which E i,k+1 = E i,k for infinitely many k yield the same sequences of different intervals, though not numbered in the same way.

Throughout this paper, we say that i chooses -, resp. takes -,

if β i is in [β i -l i,k , γ i,k [, resp. E i,k+1 = [β i -l i,k , γ i,k [; i chooses +, resp. takes +, if β i is in [γ i,k , β i + r i,k [, resp. E i,k+1 = [γ i,k , β i + r i,k [; i is modified if E i,k+1 = E i,k
, not modified otherwise. Note that the choice of i at stage k depends only on the interval E = E i,k , and not on the particular sequence of decisions we have taken or of the exact value of k, though the fact that i takes or not at stage k does depend on these last elements. The l i,k and r i,k are called the half-lengths at stage k.

[9] describes a way of making self-dual inductions without the desynchronization problem mentioned above, with the added bonus that it yields a complete description of the trajectories, see Section 3 below. It uses combinatorial objects called trees of relations, which describe the states of the induction, in the same way as permutations describe the states of the classical Rauzy or Zorich induction. Numerous examples of trees of relations appear in Section 2 below, while the reader is referred to [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] for more details and all proofs: we just recall that at each stage the tree of relations is the key to a description of the induced map of I on E 1,k ∪ ...E n-1,k (see the discussion after Definition 5 in Section 4 below), hence the use of the term "induction". Definition 2. A tree of relations G is a (non-oriented) graph with n -1 vertices i, 1 ≤ i ≤ n -1, and n -2 edges labelled +, -, or =, such that G is connected, and two adjacent edges never have the same label.

For a tree of relations G, we define its map s: s(i) is the only j such that there is an = edge between i and j, or s(i) = i if there is no such edge.

Each tree can be written in several ways, for example 1 -2 =3 and 3 =2 -1 define the same object. Note that we use hats to avoid writing formulas such as 1 = 2. Now we define an operation on trees of relations.

Definition 3. Let G be a tree of relations; a positive induction branch is a maximal connected subtree of G withoutedges. A negative induction branch is a maximal connected subtree of G without + edges.

An instruction on G is an application ι from {1, ...n -1} to {-, +}, invariant by the map s. An accepted induction branch for the instruction ι is a positive induction branch for which ιi = + on all vertices, or a negative induction branch for which ιi = -on all vertices. Let B the set of the vertices of a union of accepted induction branches for ι; the tree of relations J B (G) is defined by the vertices i, 1 ≤ i ≤ n -1, and the following edges

• if i ∈ B, j ∈ B, ιi = ιj = +, and i +j in G, then s(i) =s(j) in J B (G), • if i ∈ B, j ∈ B, ιi = ιj = -, and i -j in G, then s(i) =s(j) in J B (G), • if i ∈ B, j ∈ B, ιi = ιj = +, and i =j in G, then i +j in J B (G), • if i ∈ B, j ∈ B, ιi = ιj = -, and i =j in G, then i -j in J B (G),
• if i ∈ B or j ∈ B, the edge between i and j in G stays in J B (G) with the same label.

We can now describe the algorithm defined in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF]: we start from

E i,0 = ∆ i , 1 ≤ i ≤ n -1.
We can then make a self-dual induction such that at each stage k, there is a tree of relations G k , whose map s is denoted by s k , such that

• l j,k + r j,k = l i,k + r i,k if there is an edge i =j in G k , • l i,k = l j,k if there is an edge i +j in G k , • r i,k = r j,k if there is an edge i -j in G k .
At stage 0, the tree of relations is 1 -(n -1) +2 -(n -2) +3... whenever that expression makes sense; for small n it is just 1 for n = 2, 1 -2 for n = 3, 1 -3 +2 for n = 4.

At stage k, i chooses +, resp. -if and only if ι k (i) = +, resp. -, where the instruction ι k (i) is the sign of l i,k -r s k (i),k = l s k (i),k -r i,k , this quantity being nonzero because of Proposition 1 below.

To go from stage k to stage k + 1, we choose a union of accepted induction branches for ι k , whose vertices form the set B k , and we decide to modify i for every i ∈ B k , and not to modify i for i ∈ B k ; we say that we induce on the union of induction branches whose vertices form B k . Then at stage k + 1,

G k+1 = J B k (G k ).
This process can be iterated indefinitely. The decisions defined in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], when at each stage we induce on the union of all accepted induction branches, do not block the process: namely, in an infinite sequence of such inductions, each i has to be modified infinitely many times. In Section 2 below we shall use a modification of this algorithm, which is shown in Corollary 8 to be only slightly slower (some modifications are delayed by at most 4n -4 stages), thus the process will not be blocked either, and gives all the nested intervals we aim to build.

The various results of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] will be quoted when we are ready to use them in Sections 2, 3, 4, but we state here a result which is not explicitly written in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF]: Proposition 1. Let I be a symmetric n-interval exchange with alternate discontinuities. Then, if I satisfies the i.d.o.c. condition, in every self-dual induction β i = γ i,k for every i and k. If we can iterate indefinitely a self-dual induction with the decisions described above, such that every i is modified at infinitely many stages and β i = γ i,k for every i and k, then I satisfies the i.d.o.c. condition.

Proof

The first assertion comes immediately from the definition of the i.d.o.c. condition. Under the hypotheses of the second assertion, we can follow the proof of Theorem 2.9 of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], and show that the language of I satisfies the hypotheses of Proposition 7 or Theorem 2 of [START_REF] Ferenczi | Languages of k-interval exchange transformations[END_REF], and this implies the i.d.o.c. condition.

A self-dual induction on 2n-gon type interval exchange transformation

The trajectories we defined in the introduction can also be generated by interval exchange transformations in the following way. Definition 4. A 2n-gon-type n-interval exchange transformation I is a symmetric n-interval exchange transformation with alternate discontinuities, such that in the initial stage of the self-dual induction described above, the half-lengths are l j,0 = l j , r j,0 = r j , where for some l > 0, r > 0,

r j = r cos π n -2j 2n , l j = l cos π n-2j+1 2n cos π 2n ,
with the normalisation relation

l 1 + r 1 + ...l n-1 + r n-1 + l 1 = 1. For every point x in [0, 1[, its trajectory is the infinite sequence (x k , k ∈ IN) defined by x k = i if I k x falls into ∆ i , 1 ≤ i ≤ n.
For such an interval exchange transformation, it will be useful to define r n and l n by the same formulas, thus l n = l 1 , r n = 0. Proposition 2. Every trajectory of the billiard in a regular 2n-gon is coded by a trajectory of a 2n-gon type n-interval exchange transformation, with

r = | tan θ|, l = 1 2 sin π n -| tan θ| 1 + cos π n for some -π 2n < θ < π 2n . Proof
The sides of the 2n-gon are labelled A 1 , ..., A n from top to bottom on the right, and two parallel sides have the same label. We draw the diagonal from the right end of the side labelled A i on the right to the left end of the side labelled A i on the left. There always exists i such that the angle θ between the billiard direction and the orthogonal of this diagonal is between -π 2n and π 2n . We put on the circle the points -ie ijπ n from j = 0 to j = n, which are the vertices of the 2n-gon; our diagonal is the vertical line from -i to i, we project on it the sides of the polygon which are to the right of the diagonal, partitioning it into intervals I 1 , ... I n , and the sides of the polygon which are to the left of the diagonal, partitioning it into intervals J 1 , ... J n . The transformation which exchanges the intervals (I 1 , ...

I n ) with the (J 1 , ...J n ) is identified with the interval exchange transformation I on [-1, 1[ whose discontinuities are γ j = -cos jπ n + tan θ sin jπ n , 1 ≤ j ≤ n -1, while the discontinuities of I -1 are β j = -γ n-j , composed with the map x → -x if θ < 0. I is a symmetric n-interval exchange transformation with alternate discontinuities.
And if θ > 0, the trajectories are generated by I with the coding 1

→ A i , 2 → A i-1 , ... i → A 1 , i + 1 → A n , ....n → A i+1 . In the initial state r j = γ j -β j = 2 tan θ cos π n-2j 2n , l j = β j -γ j-1 = 2 cos π n-2j+1 2n cos π(n-1) 2n -tan θ sin π(n-1)

2n

. If θ < 0, the trajectories are generated by I with the coding 1

→ A i+1 , 2 → A i+2 , ... n -i → A n , n -i + 1 → A 1 , ....n → A i . In the initial state r j = β n-j -γ n-j = -2 tan θ cos π n-2j 2n , l j = γ n-j+1 -β n-j = 2 cos π n-2j+1 2n -cos π(n+1) 2n + tan θ sin π(n+1) 2n
. Thus in both cases we have the claimed result, after normalizing to get total length one.

Thus we have a one-parameter family of interval exchange transformations, depending on the parameter θ, or, equivalently, l r . Note that r = 0 when θ = 0, l = 0 when θ = π 2n or θ = -π 2n . The following well-known and deep result is a consequence of the Veech alternative, see [START_REF] Veech | Teichmüller curves in moduli space, Eisenstein series and an application to triangular billiards[END_REF] and [START_REF] Vorobets | Plane structures and billiards in rational polygons: the Veech alternative. (Russian)[END_REF]. Proposition 3. Let I be a 2n-gon-type n-interval exchange transformation: either every orbit is periodic, or I satisfies the i.d.o.c. condition and is uniquely ergodic (i.e. has one invariant probability measure).

We shall now prove our main result, Theorem 8 below: if we apply the self-dual induction to this family, after a bounded number of steps we come back to this family (after renormalizing, making a permutation φ on the letters {1, ..., n -1}, and possibly exchanging the left and right half-lengths). The following technical lemmas will be needed for the proof: Lemma 4. For any 1 ≤ i ≤ n such that 2i is an integer, let

λ i = cos π 2n cos π n-2i 2n cos π n-2i+1 2n .
Then, for integer

1 ≤ i ≤ n -1, λ i l i r = lr i , and λ i+ 1 2 (l i + l i+1 )r = l(r i + r i+1 ).
The λ i are positive and strictly decreasing in i, with

λ 1 = 2 cos 2 π 2n = 1 + cos π n , λ n 2 = 1, λ n-1 2 = 1 2 , λ n = 0.

Proof

The formulas either are immediate or come from trigonometric equalities, which imply also

λ i = 1 2 1 + cos π n + sin π n tan π n-2i+1 2n
, thus the λ i are indeed decreasing.

Note that the same formulas would give an infinite λ1 2 .

Lemma 5. We define for

1 ≤ t ≤ n -1,1 ≤ j ≤ n -1, x(j, t) = j u=j-t+1 l u - j u=j-t r u if j > t + 1, x(j, t) = x(t -j + 1, t) = t-j+1 u=j l u - t-j+1 u=j r u if j ≤ [ t 2 ] .
then for every j ≥ s + 1

x(j, 2s + 1) = 1 -λ s+1 r l l s+1 l 1 l j-s , x(j, 2s) = 1 λ s+ 1 2 l r -1 r s + r s+1 r 1 r j-s = λ s+ 1 2 r l -1 l s + l s+1 r 1 r j-s ,
while for j ≤ s we have x(j, 2s + 1) = x(2s + 2 -j, 2s + 1), x(j, 2s) = x(2s + 1 -j, 2s).

Proof Trigonometric equalities imply r j + r j-1 = cl j , l j + l j-1 = c r j-1 , r j-u + r j+u = c u r j , l j-u + l j+u = c u l j , for constants independent of j; these are satisfied for all values of j provided we extend the defining formulas to get (virtual) l j and r j when j is not between 1 and n.

Inputting these relations into the expression of x(j, 2s + 1), we get x(j, 2s + 1) = c s l j-s , immediately for j ≥ 2s+2, and taking into account the fact that r 0 = 0 for s+1 ≤ j ≤ 2s+1; thus we can identify the constant c s from the formula when j = s + 1. A similar reasoning works for x(j, 2s). Thus we have x(j, 2s + 1) = l s+1 -r s+1 l 1 l j-s , x(j, 2s) = ls+l s+1 -rs-r s+1 r 1 r j-s , which give the final formulas because of Lemma 4. Lemma 6. We define for

1 ≤ t ≤ n -1,1 ≤ j ≤ n -1, y(j, t) = j+t u=j l u - j+t-1 u=j r u if j ≤ n -t, y(n -j, t) = x(n -t + j, t) = n-j u=n-t+j l u - tn-j u=n-t+j r u if j ≤ [ t 2 ].
then for every j ≤ n -s

y(j, 2s) = 1 -λ n-s r l l n-s l 1 l j+s , for every j ≤ n -s -1, y(j, 2s + 1) = 1 λ n-s-1 2 l r -1 r n-s-1 + r n-s r 1 r j+s = λ n-s-1 2 r l -1 l n-s-1 + l n-s r 1 r j+s ,
while for other value of j we use y(n -j, t) = x(n -t + j, t).

Proof

The proof is similar to the proof of Lemma 5. Note that (virtually) l n+1 + l n = r n = 0, thus we get y(j, 2s) = l n-s -r n-s l 1 l j+s , y(j, 2s + 1) = l n-s-1 +l n-s -r n-s-1 -r n-s r 1 r j+s , and we conclude by Lemma 4.

Theorem 7. Given any 2n-gon type n-interval exchange transformation I, satisfying the i.d.o.c. condition, there exists an algorithm of self-dual induction following the rules of Section 1, an integer 2 ≤ m ≤ 2n -2, and d = ±1, such that after m steps the half-lengths

(l φ(j),m , r φ(j),m ), 1 ≤ j ≤ n -1, are proportional to (l cos π n-2j+1 2n cos π 2n , r cos π n-2j 2n ) if d = +1 and to (r cos π n-2j 2n , l cos π n-2j+1 2n cos π 2n ) if d = -1, where l r = g( l r ) and • in Case 1 defined by l r > λ 1 , d = 1, φ = Id and g(y) = y -λ 1 ;
• in Case 2i defined by

λ i > l r > λ i+ 1 2 , 1 ≤ i ≤ n -1, d = -1, φ(j) = i -j + 1 for 1 ≤ j ≤ i, φ(j) = n -j + i for i + 1 ≤ j ≤ n -1, and g(y) = λ 1 2λ i λ i -y y -λ i+ 1 2 ; • in Case 2i + 1 defined by λ i+ 1 2 > l r > λ i+1 , 1 ≤ i ≤ n -1, d = 1, φ(j) = i + j for 1 ≤ j ≤ n -i -1, φ(j) = 1 -n + j + i for n -i ≤ j ≤ n -1, and g(y) = λ i+ 1 2 y -λ i+1 λ i+ 1 2 -y .

Proof

We fix an n ≥ 3.

Case 1

Step 1 In the initial stage, l j,0 = l j , r j,0 = r j , 1 ≤ j ≤ n -1, the tree of relations is 1 -(n -1) +2 -..., and its map s is the identity; here we have l j > r j for all j and 1, 2, ...(n -1) all choose +; we induce on the union of all positive induction branches in the tree of relations, which are all accepted: these are 1, (n -j) +(j + 1), 1 ≤ j ≤ p -1, if n = 2p, or (n -j) +(j + 1), 1 ≤ j ≤ p -1, and (p + 1), if n = 2p + 1. After this induction, we arrive in stage 1 with half-lengths 1 ≤ j ≤ n -1 l j,1 = l j -r j r j,1 = r j and tree of relations

1 -(n -1) =... =i -(n -i) =(i + 1) -(n -i -1) =(i + 2) -...
Step 2 In stage 1, the map s is defined by s(1) = 1, s(n -j) = j + 1 and s(j

+ 1) = n -j, 1 ≤ j ≤ p -1 if n = 2p or n = 2p + 1, and s(p + 1) = p + 1 if n = 2p + 1.
We check that, for j > 1, l j,1 -r s()j,1 = x(j, 1) and thus is positive by Lemma 5; 2, ..., (n -1) choose + and we induce on the union of all positive induction branches to the right of (and including) (n -1) =2, all of them being accepted; these are (n -j) =(j + 1), 1 ≤ j ≤ p -1, if n = 2p, or (n -j) =(j + 1), 1 ≤ j ≤ p -1, and (p + 1), if n = 2p + 1. After this induction, we arrive in stage 2, with the same tree of relations as in stage 0, and half-lengths l j,2 = x(j, 1) r j,2 = r j . Thus, by Lemma 5, if we put l j = l j,2 and r j = r j,2 , we get the required formulas, computing l r from l 1 = x(1, 1), r 1 = r 1 .

Note that in stage 1, we did not know a priori the sign of l 1,1 -r 1,1 , which will be determined by the value of l r , thus at this stage the instruction ι is not fully known, and indeed not the same for all values of l r of Case 1; but this value has no influence on the admitted induction branches (strictly) right of 1, so our choice not to modify 1 is permitted whether 1 chooses + or -, but this choice is different from the one defined in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] if l 1,1 -r 1,1 > 0, as in that case we should have induced on the union of all positive induction branches, including the branch 1.

We shall check that throughout the process, either the parameters determining the choices of j are quantities x(j, t) or (in the second half of cases) y(j, t), whose sign is known by Lemma 5 or Lemma 6, or the rules of the self-dual induction defined in Section 1 above allow us not to modify j, such as for j = 1 in Step 2 of Case 1 above.

Case 2i for 1 ≤ i < n 2
Step 1 In the initial stage 1,... i choose -, (i + 1)... (n -1) choose +; we induce on the union of positive induction branches in the tree of relations which are to the right of (and including) (n-i) +(i+1): these are (n-j) +(j +1), i ≤ j ≤ p-1, if n = 2p, or (n-j) +(j +1), i ≤ j ≤ p -1, and (p + 1), if n = 2p + 1. After this induction, we arrive in stage 1 with half-lengths

1 ≤ j ≤ i l j,1 = l j r j,1 = r j i + 1 ≤ j ≤ n -i l j,1 = l j -r j r j,1 = r j n -i + 1 ≤ j ≤ n -1 l j,1 = l j r j,1 = r j and tree of relations 1 -(n -1) +... +i -(n -i) =(i + 1) -(n -i -1) =(i + 2) -...
Step 2. In stage 1, we check that i, (n -i), (i + 1), (n -i -1), (i + 2), and everything to the right, choose -; we induce on the negative induction branch which is to the right of (and including) i. After this induction, we arrive in stage 2 with half-lengths

1 ≤ j ≤ i -1 l j,2 = l j r j,2 = r j j = i l j,2 = l j r j,2 = r j -l j i + 1 ≤ j ≤ n -i l j,2 = l j -r j r j,2 = -x(j, 1) n -i + 1 ≤ j ≤ n -1 l j,2 = l j r j,2 = r j
and tree of relations

1 -(n -1) +... +i =(i + 1) -(n -i) =(i + 2) -(n -i -1) =(i + 3) -...
We make now the recursion hypothesis that in stage 3a -1 we have the half-lengths

1 ≤ j ≤ i -a l j,3a-1 = l j r j,3a-1 = r j j = i -a + 1 l j,3a-1 = l j r j,3a-1 = -x(j, 2i -1) i -a + 2 ≤ j ≤ i + a -1 l j,3a-1 = x(j, 2i) r j,3a-1 = -x(j, 2i -1) i + a ≤ j ≤ n -i + a -1 l j,3a-1 = l j -r j r j,3a-1 = -x(j, 2a -1) n -i + a ≤ j ≤ n -1 l j,3a-1 = l j r j,3a-1 =
i +(i + 1) -(i -1)... +(i + a -2) -(i -a + 2) +(i + a -1) - arriving at the vertex (i -a + 1).
This hypothesis is satisfied for a = 1. Then

Step 3a. In stage 3a -1, (n -i + a), (i + a -1) and (i + a) choose +, and we induce on this positive induction branch with three vertices. We get the tree of relations made of the main branch

1 -(n-1) +...(i-a) -(n-i+a) =(i+a) -(n-i+a-1) =(i+a+1) -(n-i+a-2) =(i+a+2) -...

and of the secondary branch

i +(i + 1) -(i -1)... +(i + a -2) -(i -a + 2) +(i + a -1) -(i -a + 1)
+ arriving at the vertex (i + a).

Step 3a + 1. In stage 3a, (i -a), (n -i + a), (i + a), (n -i + a -1), and everything to the right, choose -; we induce on the negative induction branch which is in the main branch to the right of (and including) i -a. We get the tree of relations made of the main branch

1 -(n -1) +...(i -a) =(i + a) -(n -i + a) =(i + a + 1) -(n -i + a -1) =(i + a + 2) -...

and of the secondary branch

i +(i + 1) -(i -1)... +(i + a -2) -(i -a + 2) +(i + a -1) -(i -a + 1)
+ arriving at the vertex (i + a).

Step 3a + 2. In stage 3a + 1, (i -a), (i + a), (n -i + a), and everything to the right, choose -; we induce on the negative induction branch which is in the main branch to the right of (and including) (i -a). We get the recursion hypothesis for a + 1.

The recursion continues as far as stage 3i -1. At step 3i -2, we have a (last) negative induction on the negative induction branch which is in the main branch to the right of (and including) 1 =(2i -1) -..., and in stage 3i -1 we get the (straight) tree of relations

i +(i + 1) -(i -1)... +(2i -1) -1 =(2i) -(n -1) =(2i + 1) -(n -2) =(2i + 2)....
Step 3i In stage 3i -1, 1, 2i, (n -1), (2i + 1), and everything to the right, choose +; we induce on the union of positive induction branches which are to the right of (and including) 1 =2i: they are of the form b =c except for the rightmost one which may be reduced to a single vertex. We get the tree of relations i +(i + 1) -(i -1)... +(2i -1) -1 +2i -(n -1) +(2i + 1) -(n -2) +(2i + 2).... and the half-lengths l j,3i = x(j, 2i) r j,3i = -x(j, 2i -1). By Lemma 5 we get constants K and K such that that

l j,3i = Kr n-j+i r j,3i = K l n-j+i if j ≥ i + 1, l j,3i = Kr i-j+1 r j,3i = K l i-j+1 if j ≤ i.
Thus if we put l j = r i-j+1,3i and r j = l i-j+1,3i for j ≤ i, l j = r n-j+i,3i and r j = l n-j+i,3i for j > i, we get the required formulas, computing l r from l 1 = -x(i, 2i -1),

r 1 = x(i, 2i) = x(i + 1, 2i).
Each induction has been on a union of accepted union branches which are all positive or all negative, so we can speak of positive induction or negative induction. With this convention, the sequence of inductions has the signs + -(+ --) i-1 +, where the positive inductions are on three-vertices induction branches, except the first and last ones which are on unions of two (or one)-vertices induction branches, and the negative inductions are on an induction branch which is absorbing more and more vertices on its left during the process. Note that each j for 2 ≤ j ≤ 2i -1 is not modified in the later stages of the process, though we do not know if it chooses -or +; as in Case 1, this is allowed by the rules as these choices do not modify the fact that we induce on unions of accepted induction branches, but the resulting self-dual induction is possibly slower than the one defined in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF].

Case 2i + 1 for 1 ≤ i < n-1 2
Then steps 1 and 2 are as in case 2i, but in stage 3 we induce on the negative branch which is to the right of i. The recursion hypothesis becomes that in stage 3a we have the tree of relations made of the main branch 1 -(n-1) +..(i-a) -(n-i+a) +(i-a+1) =(i+a+1) -(n-i+a-1) =(i+a+2) -(n-i+a-2) =(i+a+3) -... and of the secondary branch (i + 1) -i +(i + 2) -(i -1)... +(i + a -1) -(i -a + 2) +(i + a) arriving at the vertex (i -a + 1).

The recursion continues as far as stage 3i.We end after step 3i+1 with the tree of relations

(i + 1) -i +(i + 2) -(i -1).... +2i -1 +(2i + 1) -(n -1) +(2i + 2) -(n -2) +(2i + 3)....
and the half-lengths l j,3i+1 = x(j, 2i + 1) r j,3i+1 = -x(j, 2i).

Thus if we put l j = l 3i+1,i+j and r j = r 3i+1,i+j for j ≤ n -i -1, l j = l 3i+1,j-n+i+1 and r j = r 3i+1,j-n+i+1 for j ≥ n -i, we get the required formulas, computing l r from l 1 = x(i + 1, 2i + 1), r 1 = -x(i + 1, 2i).

The sequence of inductions has the signs (+ --) i +, where the positive inductions are on three-vertices induction branches, except the first and last ones which are on unions of two (or one)-vertices induction branches, and the negative inductions are on an induction branch which is absorbing more and more vertices on its left during the process.

Case n when n = 2p

In step 1 we can only induce on the negative induction branch p; then in step 4a -2 we induce on the positive induction branch (p + a) +(p -a + 1), in step 4a -1 we induce on the positive induction branch (p + a) =(p -a + 1), in step 4a we induce on the negative induction branch (p -a) -(p + a), in step 4a + 1 we induce on the negative induction branch (p -a) =(p + a), for 1 ≤ a ≤ p -1. In step 4p -2 we induce on the positive induction branch 1.

The sequence of inductions has the signs -(+ + --) p-1 +, where every induction is on a two-vertices induction branch, except the first and last ones which are on a one-vertex induction branch. In stage 4p -2 the tree of relations is the initial one and the half-lengths are l j,4p-2 = y(j, 2p -1) r j,4p-2 = -x(j, 2p -1).

If we put l j = r p-j+1,4p-2 and r j = l p-j+1,4p-2 for j ≤ p, l j = r 3p-j,4p-2 and r j = l 3p-j,4p-2 for j > p, we get the required formula, computing l r from l 1 = -x(p, 2p -1), r 1 = y(p, 2p -1).

Case n when n = 2p + 1 The sequence of inductions has the signs + --(+ + --) p-1 +, starting from an induction on the positive induction branch p + 1 and ending with an induction on the positive induction branch 1. All the other inductions are on two-vertices induction branches as in the previous case. In stage 4p + 2 the tree of relations is the initial one and the half-lengths are l j,4p+2 = y(j, 2p) r j,4p+2 = -x(j, 2p). if we put l j = l j+p,4p and r j = r j+p,4p for j ≤ p, l j = r j-p,4p and r j = l j-p,4p for j > p, we get the required formulas, computing l r from l 1 = y(p + 1, 2p) = y(p, 2p), r 1 = -x(p + 1, 2p).

Case 2n -2i for 1 ≤ i < n 2
This case is roughly symmetric with case 2i. The sequence of inductions has the signs (-+ +) i-1 -+-, where the negative inductions are on three-vertices induction branches, except the first and last ones which are on unions of two (or one)-vertices induction branches, and the positive inductions are on an induction branch which is absorbing more and more vertices on its left during the process. We arrive in stage 3i, where the half-lengths are l j,3i = y(j, 2i -1) r j,3i = -y(j, 2i).

If we put l j = r n-i+1-j,3i and r j = l n-i+1-j,3i for 1 ≤ j ≤ n -i, l j = r 2n-i-j,3i and r j = l 2n-i-j,3i for n -i + 1 ≤ j ≤ n -1, we get the required formulas, computing l r from

l 1 = -y(n -i, 2i), r 1 = y(n -i, 2i -1). Case 2n -2i + 1 for 1 ≤ i < n-1 2
This case is roughly symmetric with case 2i + 1. The sequence of inductions has the signs -+(-++) i-2 -+-, where the negative inductions are on three-vertices induction branches, except the first and last ones which are on unions of two (or one)-vertices induction branches, and the positive inductions are on an induction branch which is absorbing more and more vertices on its left during the process. We arrive in stage 3i -1, where the half-lengths are l j,3i-1 = y(j, 2i -2) r j,3i-1 = -y(j, 2i -1).

If we put l j = l j+n-i,3i-1 and r j = r j+n-i,3i-1 for 1 ≤ j ≤ i -1, l j = l j-i+1,3i-1 and r j = r j-i+1,3i-1 for i ≤ j ≤ n -1, we get the required formulas, computing l r from

l 1 = y(n -i + 1, 2i -2), r 1 = -y(n -i + 1, 2i -1) = -y(n -i, 2i -1). Case 2n -1: λ n-1 2 > l
r > 0 This case is roughly symmetric with case 1: we make only two negative inductions on unions of two (or one)-vertices induction branches; note that when n = 2p we make two inductions on the one-vertex negative induction branch p, in contrast with case 1 where we always make only one induction on the one-vertex positive induction branch 1. At the end the half-lengths are l j,2 = l j r j,2 = -y(j, 1).

If we put l j = l j,2 and r j = r j,2 , we get the required formulas, computing l r from l 1 = l 1 , r 1 = -y(1, 1).

It remains to check that we have to be in one of the Cases 1 to 2n -1. But otherwise, for some integer i, l r = λ i and thus l i = r i , or l r = λ i+ 1 2 and thus l i + l i+1 = r i + r i+1 ; as results of the analysis of every case below, this implies β i = γ i,k at the first or second stage of a self-dual induction, and thus contradicts the i.d.o.c. condition as stated in Proposition 1 above.

The previous analysis is still valid for n = 2, with the obvious modifications needed because this is a degenerate situation, for example in the first case Step 2 is void, and we stop in stage 1. Corollary 8. Under the i.d.o.c. condition (for the interval exchange I), the renormalization process (l, r) → (l , r ) can be iterated infinitely many times. The knowledge of the itinerary under this renormalization, as an infinite sequence of Cases numbered by 1, ... 2n -1, yields a full description of the infinite iteration of a self-dual induction process for I as described in Section 1 above, differing from the one in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] only by the postponing of some modifications by at most 4n -4 stages.

Proof

The i.d.o.c. condition for the initial parameters l i , r i ensures (by Proposition 1) that l r cannot be equal to any of the λ i , thus we can iterate the process, and the same will be true after each iteration thus we can do it infinitely many times.

Let φ k , resp. d k , be the permutation φ, resp. the number d, used for the k-th renormalization, k ≥ 1;

e k = d 1 ...d k with e 0 = +1, g k = g if e k-1 = +1, g k (y) = 1 g( 1 y ) if e k-1 = -1, Φ k = φ k • ...φ 1 , G k = g k • ...g 1 .
Immediately after the k-th renormalization, we arrive in some stage m k of the self-dual induction:

• if e k = +1, the l Φ k (j),m k , r Φ k (j),m k , 1 ≤ j ≤ n -1, are proportional to l (k) cos π n-2j+1 2n cos π 2n , r (k) cos π n-2j
2n , where l (k) r (k) = G k ( l r ). Then, if the conditions defining Case i are satisfied with l replaced by l (k) , r replaced by r (k) , we say that after the k-th renormalization we are in Case i, and get stages m k + 1, ... m k+1 of the variant of the self-dual induction defined in Theorem 7, by following exactly the steps described in the relevant paragraph of the proof of Theorem 7, but after replacing each j by Φ k (j);

• if e k = -1, the l Φ k (j),m k , r Φ k (j),m k , 1 ≤ j ≤ n -1, are proportional to r (k) cos π n-2j+1 2n cos π 2n , l (k) cos π n-2j 2n , where l (k) r (k) = G k ( l r ).
Then, if the conditions defining Case i are satisfied with r replaced by l (k) , l replaced by r (k) , we say that after the k-th renormalization we are in Case i, and get stages m k + 1, ... m k+1 of the variant of the self-dual induction defined in Theorem 7, by following exactly the steps described in the relevant paragraph of the proof of Theorem 7, but after replacing each j by Φ k (j), and exchanging the right and left half-lengths, thus the + and -in the trees of relations.

The difference with the algorithm described in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] is that some modifications of i, which in the algorithm of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] would have been made between the k -1-th and the k-th renormalization, are postponed to after the k-th renormalization; but every i is modified at least once between two renormalizations, thus the postponed modifications will be made before

Dynamical results

The coding of trajectories gives precious informations on the dynamical behaviour of the system, and allows us to consider the problem of weak mixing; We recall that (X, T, µ) is weakly mixing if µ is ergodic and the operator f • T in L 2 (X, IR/Z Z) has no nonzero eigenvalue (denoted additively, f • T = f + ζ). Artur Avila and Giovanni Forni [START_REF] Avila | Giovanni Weak mixing for interval exchange transformations and translation flows[END_REF] have proved that almost every symmetric interval exchange is weakly mixing; the same authors (private communication) can prove that, at least for n = 4, almost every interval exchange in our one-parameter family is weakly mixing. We do not attempt to prove such a result, but shall prove a little more in the (admittedly easier) case n = 3: here every non-periodic I in our family is weakly mixing (for the unique invariant probability), and in an explicit subfamily we have the very strong property of minimal self-joinings: an ergodic system (X, T, µ) has minimal self-joinings if any ergodic measure ν on X × X, invariant under T × T , for which both marginals are µ, is either the product measure µ × µ or a diagonal measure defined by ν(A × B) = µ(A ∩ T i B) for an integer i; we refer the reader to [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF] for every detail on the theory of self-joinings.

Theorem 12. A non-periodic hexagon type 3-interval exchange transformation I is always weakly mixing for its unique invariant probability measure. Whenever in the algorithm of Corollary 8 the lengths of the runs of successive Case 1 and the lengths of the runs of successive Case 5 are bounded, I has minimal self-joinings, and its trajectories are linearly recurrent, i.e. each word of length n occurring in a trajectory occurs in every word of length at least Kn occurring in any trajectory. Otherwise I is rigid, i. e. µ(T sn A∆A) → 0 for any measurable set on a common sequence s n .

Proof

We apply the criteria of [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF] and [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF]. These involve the infinite iteration of a self-dual induction which defines quantities (m k , n k , k+1 ), k ≥ 1. We can retrieve this self-dual induction from the algorithm of Corollary 8, where the three possible trees of relations are 1 -2, 1 =2, 1 +2, and use it to compute the quantities (m k , n k , k+1 ): namely, we notice that we must have the tree of relations 1 =2 infinitely many times, but we cannot have it in two consecutive stages, and look at what happens between the k-th and k + 1-th time we have that tree: if during these stages we have the tree of relations 1 -2, m k , resp. n k , is the number of times 1, resp. 2 takes +, while if during these stages we have the tree of relations 1 +2, m k , resp. n k , is the number of times 1, resp. 2 takes -; k+1 is -1 if, between the k-th and k + 1-th time we have the tree 1 =2, we have the same tree of relations as between the k -1-th and k-th time, k+1 is +1 otherwise. By Theorem 3.1 of [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF], we have weak mixing if m k n k is bounded above and below. This is always the case here as m k and n k are bounded by 4 unless there is a run of Q ≥ 1 consecutive Case 1, and during such a run either we have the tree 1 -2, 1 takes + 2Q times and 2 takes + Q times, or we have the tree 1 +2, 1 takes -2Q times and 2 takes -Q times, or the same with 1 and 2 exchanged; thus, because in the other cases we see 1 =2 at most one step after the beginning and at most one step before the end, m k ∨n k ≤ 2Q+2, m k ∧n k ≥ Q.

The linear recurrence implies minimal self-joinings by Theorem 4.1 of [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF], and its absence implies rigidity by Theorem 5.1 of [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF]; by Proposition 3.1 of [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF] it is equivalent to the boundedness of the m k , n k , and the lengths of runs of consecutive (m k = 1, k+1 = -1) or of consecutive (n k = 1, k+1 = -1). Now, unbounded runs of Case 1 give unbounded m k and n k , unbounded runs of Case 5 give unbounded runs of (m k = n k = 1, k+1 = -1) and thus prevent linear recurrence. Conversely, suppose we have bounded runs of Case 1 and of Case 5: then the m k and n k are bounded as they can grow beyond 4 only with a run of Case 1; as an occurrence of Case 2 or 4 gives an k+1 = +1, and an occurrence of Case 5 gives m k-1 = n k = 2 or n k-1 = m k = 2, the other conditions for linear recurrence are satisfied because the runs of Case 5 are bounded.

Theorem 12 above is just a translation, through Corollary 8 above, of the extensive theory developped in [START_REF] Ferenczi | Structure of three interval exchange transformations. I. An arithmetic study[END_REF][6][7] [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF]. At the root of this theory is a fundmental property of the self-dual induction that we shall use again now: namely, the words M and P defined in Theorem 11 above are not mere auxiliaries for building the bispecial words, they also span the trajectories and thus determine an explicit construction of Rokhlin towers. Definition 5. In (X, T ), a Rokhlin tower of base F is a collection of disjoint measurable sets called levels F , T F , . . . , T h-1 F . If X is equipped with a partition P such that each level T r F is contained in one atom P w(r) , the name of the tower is the word w(0) . . . w(h -1).

We recall that the induced map of any transformation T on a set Y is the map y → T r(y) y where, for y ∈ Y , r(y) is the smallest r ≥ 1 such that T r y. As is noticed in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], p. 300-301, at stage k of a self-dual induction, the induced map of I on E 1,k ∪ ...E n-1,k determines in a standard way 2n -2 disjoint Rokhlin towers (for

I) of bases [β i -l i,k , γ i,k [, 1 ≤ i ≤ n -1, and [γ i,k , β i + r i,k [, 1 ≤ i ≤ n -1,
filling the whole space. As is noticed in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], p. 309, each level I r [γ i,k , β i + r i,k [ is contained in one interval ∆ z(r,i,k) , z(r, i, k) ∈ {1, ...n}; each level I r [β i -l i,k , γ i,k [ is contained in one interval ∆ z (r,i,k) , z (r, i, k) ∈ {1, ...n}.This gives two words z i = z(0, i, k)...z(h i -1, i, k) and z i = z (0, i, k)...z (h i -1, i, k), and the z i , resp. z i , are identified with the words P , resp. M , at the k-th stage of the induction, but read backwards. Thus we can build inductively, for each k, 2n -2 disjoint Rokhlin towers for I -1 , filling the whole space, whose names (for the partition into ∆ i ) are these 2n -2 words M and P . Moreover, the towers at stage k + 1 are made by cutting and stacking following the recursion rules giving their names by concatenating names of towers at stage k. We must warn the reader of a technicality: in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] and the present paper, the words M and P are built in order to extend the bispecial words to the right, and yield Rokhlin towers for I -1 , while in [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF] the words P and M are those in the present paper read backwards, yielding Rokhlin towers for I and extending the bispecial words to the left.

Thus in the present paper we have 2n -2 Rokhlin towers for I -1 ; but this is not optimal: indeed, by a further induction operation, we could use them to build n Rokhlin towers filling all the space, with the further property that the n bases are sub-intervals of a small interval. This further step is carried out for low values of n, for n = 4 in [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF], while for n = 3 it gives in [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF][8] the general results which we have used in Theorem 12.

For general values of n, however, the n Rokhlin towers become very complicated to build explicitly. Thus the following result is quite different from all the results in [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF][8] [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF], as it makes use of the 2n -2 towers M and P , whose bases are not close to one another, to get dynamical results. Moreover, it gives, as far as we know, the first explicit construction (as opposed to existence theorems) of a weakly mixing n-interval exchange transformation for every value of n, the only constructions we have been able to find in the literature being for n = 3 [13][7], n = 4 [10][14], and n = 6 [START_REF] Sinai | Ulcigrai, Corinna Weak mixing in interval exchange transformations of periodic type[END_REF]. The idea of the proof is to kill any possible eigenvalue ζ by the usual Chacon trick, i.e. have both uζ and (u + 1)ζ close to an integer; this is achieved by ensuring first that the heights of two of the towers are coprime, then that these towers are cycled for a large enough number of times to permit using Bezout's relation; we conclude by checking that these two towers appear at least as a fixed proportion of all the towers at a further stage.

Theorem 13. For any n, one can construct recursively two sequences m k and q k such that the 2n-gon type n-interval exchange transformation I for which the algorithm of Corollary 8 is made with successive runs of m k Case 1 and q k Case 2n -1, k ≥ 1, is weakly mixing for its unique invariant probability measure.

Proof

At the beginning of the run of m k Case 1, let M k,i,j be the word M beginning with the letter n -i and ending with the letter j, P k,i,j be the word P beginning with the letter n + 1 -i and ending with the letter j. Then, by Theorem 11, at the beginning of the run of q k Case 2n -1 the words M and P are the M k+1,i,j and P k,i,j , with

M k+1,i,n-i = M k,i,n-i (P k,n-i,i+1 P k,i+1,n-i ) m k for 1 ≤ i ≤ n -2, M k+1,n-1,1 = M k,n-1,1 P m k k,1,1 .
Then after this run we get

P k+1,i,n+1-i = P k,i,n+1-i (M k+1,n+1-i,i-1 M k+1,i-1,n+1-i ) q k for 2 ≤ i ≤ n -1, P k+1,1,1 = P k,1,1 (M k+1,1,n-1 M k+1,n-1,1 ) q k .
Take n = 2p; we make the recursion hypothesis that the word lengths x k = |M k,p,p | and y k = |M k,p-1,p+1 M k,p+1,p-1 | are coprime. The hypothesis is satisfied for k = 1 where x 1 = 1 and y 1 = 2, we suppose now that it is satisfied for k and choose m k such that it will be satisfied for k + 1.

Namely,

x k+1 = x k + m k |P k,p,p+1 P k,p+1,p | = x k + m k X k , y k+1 = y k + m k (|P k,p+1,p P k,p,p+1 | + |P k,p-1,p+2 P k,p+2,p-1 |) = y k + m k Y k . Any common factor of x k+1 and y k+1 has to divide Y k x k+1 -X k y k+1 = Y k x k -X k y k = Z,
k such that m k ≡ X -1 k (u -x k ) modulo d, for any u ≡ 0 modulo d. Similarly if d is in D 1 ,
and therefore does not divide y k , either d does not divide y k+1 for any value of m k , or this can be ensured by a congruence condition modulo d. Thus, by the Chinese remainder theorem, we can find infinitely many values of m k such that no prime number d divides the three numbers Z, x k+1 and y k+1 , and this ensures that x k+1 and y k+1 are coprime. We also ask

that |M k,i,n-i | < k m k (|P k,n-i,i+1 |+|P k,i+1,n-i )| for 1 ≤ i ≤ n-2 and |M k,n-1,1 | < k m k |P k,1,1 |
for some prescribed k . Note that m k depends only on the parameters m 1 , ... m k-1 , q 1 , ... q k-1 .

Thus for any k there exist positive integers

U k and V k such that |U k x k -V k y k | = 1.
As the value of x k+1 and y k+1 depend only on the parameters m 1 , ... m k , q 1 , ... q k-1 , we can then choose q k larger than 2(U k+1 ∨ V k+1 ). We also ask that |P k,i,n+1-i | < k q k (|M k+1,n+1-i,i-1 | + |M k+1,i-1,n+1-i |) for 2 ≤ i ≤ n -1 and |P k,1,1 | < k q k (|M k+1,1,n-1 | + |M k+1,n-1,1 |). We shall now prove that, with this choice of the m k and q k , I is weakly mixing.

We build the Rokhlin towers for I -1 whose names are the words P and M . At stage k, the space is filled by 2n-2 towers, whose names are the M k,i,j and P k,i,j . The towers at stage k+1 are made by cutting and stacking following the recursion rules above, thus in the name of P k,p+1,p we see M For any point ω in τ k , I -x k ω, I -2x k ω,.... I -U k x k ω are in the same level of the tower M k,p,p as ω. Similarly, in the name of P k,p,p+1 we see (M k,p-1,p+1 M k,p+1,p-1 ) q k-1 from level |P k-1,p,p+1 | to level |P k-1,p,p+1 | + q k-1 |M k,p-1,p+1 M k,p+1,p-1 | -1; let τ k be the union of all the levels of P k,p,p+1 from level |P k-1,p,p+1 | to level |P k-1,p,p+1 | + [ q k-1 2 ]|M k,p-1,p+1 M k,p+1,p-1 | -1. For any point ω in τ k , I -y k ω, I -2y k ω,.... I -V k y k ω are in the same level of a tower M k,i,j as ω.

Let µ be the invariant probability for I, f be an eigenfunction for the eigenvalue ζ; the σ-algebras generated by the levels of the k-towers converge to the full σ-algebra when k tends to infinity, thus for each ε > 0 there exists N (ε) such that for all k > N (ε) there exists f k , which satisfies ||f -f k ||dµ < ε and is constant on each level of each k-tower (where ||x|| denotes its distance to the nearest integer).

Thus for µ-almost every ω in τ k , f k (I -U k x k ω) = f k (ω) while f (I -U k x k ω) = -ζU k x k + f (ω); we have

τ k ||f k • I -U k x k + ζU k x k -f k ||dµ = τ k ||ζU k x k ||dµ = ||ζU k x k ||µ(τ k ) and τ k ||f k • I -U k x k + ζU k x k -f k ||dµ ≤ τ k ||f k • I -U k x k -f • I -U k x k ||dµ + τ k ||f k -f ||dµ < 2ε.
Thus µ(τ k )||ζU k x k || < 2ε, and similarly µ(τ k )||ζV k y k || < 2ε; as U k x k -V k y k = ±1, we shall conclude that ζ = 0, and thus get the weak mixing, if we can prove that µ(τ k ) and µ(τ k ) are bounded away from 0.

For this, we need first to check that all the lengths of the M k,i,j , resp. P k,i,j , are comparable for constant k; they are not equal, even approximately, because in one of the recursion formulas there is a lone term P m k k,1,1 where the others have (P k,i,j P k,j,i ) m k . Up to k which is chosen much smaller than all the other parameters: for k ≥ 2 we have, following the tree of relations from left to right, Thus the strings M 2q k-1 k,p,p fill (about) all the length of P k,p+1,p , thus (because of the recursion formulas and the comparability of the lengths of P k,p+1,p and P k,p,p+1 ) at least a fixed proportion c of the lengths of M k+1,p-1,p+1 and M k+1,p,p , thus, in the same way, a proportion at least c 2 of the lengths of P k+1,i,n+1-i for p -1 ≤ i ≤ p + 1, thus a proportion at least c 3 of the lengths of M k+2,i,n+1-i for p -2 ≤ i ≤ p + 1, .... and finally a proportion at least c 2n-1 of the lengths of all the M k+n,i,j and P k+n,i,j , which define 2n -2 Rokhlin towers filling all the space. This implies that µ(τ k ) ≥ 1 2 c 2n-1 , and a similar reasoning works for µ(τ k ).

If n = 2p + 1 we choose succesively the q k such that |P k,p+1,p+1 | and |P k,p,p+2 P k,p+2,p | are coprime, the m k to ensure that these strings are cycled enough times, and make a similar reasoning.

Institut de Mathématiques de Luminy, CNRS -FRE 3529, Case 907, 163 av. de Luminy, F13288 Marseille Cedex 9 (France), and Fédération de Recherche des Unités de Mathématiques de Marseille, CNRS -FR 2291 E-mail address: ferenczi@iml.univ-mrs.fr

  r j and tree of relations made of the main branch 1 -(n-1) +..(i-a) -(n-i+a) +(i-a+1) =(i+a) -(n-i+a-1) =(i+a+1) -(n-i+a-2) =(i+a+2) -... and of the secondary branch

  which is independent of m k . Let D be the set of all prime factors of Z, D 1 the set of those factors which divide also x k , D 2 the set of the other factors. If d is in D 2 and divides X k , any choice of m k ensures that d does not divide x k+1 ; if d is in D 2 and does not divide X k , d does not divide x k+1 for any m

2q k- 1 k

 1 ,p,p , from level |P k-1,p+1,p | to level |P k-1,p+1,p | + 2q k-1 |M k,p,p | -1. Let τ k be the union of all the levels of P k,p+1,p from level |P k-1,p+1,p | to level |P k-1,p+1,p |+q k-1 |M k,p,p |-1.

  |M k,n-1,1 | ≤ |M k,n-2,2 | ≤ ...|M k,p,p |, while |M k,i-1,n-i+1 | = |M k,n-i,i | for 2 ≤ i ≤ p, and |P k,2,n-1 | ≤ |P k,3,n-2 | ≤ ...|P k,p+1,p |, while |P k,n-i+2,i-1 | = |P k,i,n-i+1 | for 3 ≤ i ≤ p, and |P k,1,1 | = |P k,2,n-1 |. Then we check by induction that |M k,n-i,i | ≥ 2 -1 |M k,n-i-1,i+1 | for 1 ≤ i ≤ p -1, and |P k,i,n-i+1 | ≥ 2 -1 |P k,i+1,n-i | for 2 ≤ i ≤ p.

the k + 1-th renormalization, and thus are postponed by at most 4n -4 stages.. Thus, for an n-interval exchange transformation in our one-parameter family, from the itinerary under the renormalization we get its infinite itinerary under the self-dual induction, which is a path in the n-th graph of graphs defined in Definition 2.8 of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] and described in the remark following that definition and in [START_REF] Cassaigne | Combinatorial trees arising in the study of interval exchange transformations[END_REF]. We remark that this path has a quite special form, compared to the possibilities realized by general n-interval exchange transformations; indeed, because of Theorem 7 above and Lemma 7.3 of [START_REF] Cassaigne | Combinatorial trees arising in the study of interval exchange transformations[END_REF] it stays in a subgraph comprising at most 4n 3 trees of relations, while the cardinality of the full graph of graphs is exponential in n by Proposition 7.5 of [START_REF] Cassaigne | Combinatorial trees arising in the study of interval exchange transformations[END_REF]; in particular the trees of relations in this subgraph have at most two branches, while, by [START_REF] Cassaigne | Combinatorial trees arising in the study of interval exchange transformations[END_REF], for n ≥ 7 there are trees of relations with more branches, namely up to [ n-1 2 ] branches. Then, for n ≥ 4 there exist accepted induction branches B with q ≥ 3 vertices, and in general it is possible to make up to q consecutive inductions on B and its successive images before coming back to B, and to iterate that process as in the first family of examples in [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF], while in the present family we can make at most two consecutive inductions on such a branch and its successive images. Even for n = 3, the proof of Theorem 12 below shows that only some particular paths are possible.

When we do not suppose I satisfies the i.d.o.c. condition, the algorithm of Theorem 7 may be undefined because l r = λ i ; these cases are completely characterized by the following result, which makes full use of two heavy machineries, the self-dual induction and the Veech alternative. • all the trajectories of I are periodic,

• the algorithm of Theorem 7 cannot be iterated infinitely many times.

Proof

The equivalence between the first two assertions is a consequence of Proposition 3 above. The equivalence between the first and the third is a consequence of Proposition 1 above.

Note that for n = 3, resp. n = 4, the three conditions of the above proposition are equivalent to tan [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], and this could be reproved by using the renormalization algorithm of Theorem 7, but no such characterization holds for general n, see Remark 6.2.3 of [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF].

When I satisfies the i.d.o.c. condition, or equivalently is non-periodic, we can characterize the possible infinite sequences of Cases: Proposition 10. In the algorithm of Corollary 8, the possible infinite sequences of Cases are all the sequences on {1, ..., 2n -1} which do not take the value 1 ultimately or the value 2n -1 ultimately.

Proof

The condition is necessary because of the form of the map g, as given in Theorem 7 in Case 1, and written r l = r l -1

in Case 2n -1, and because during a run of Case 1 or 2n -1 d is always +1. And when it is satisfied, we can find a corresponding initial l r as an intersection of nested compact sets.

Coding of the trajectories

We are now ready to reap the results of the extensive theory developped in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF].

First, we get a coding of the symbolic trajectories, which is different from the one in [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], and is relatively simple to state even for general values of n. Note that we do not use our renormalization algorithm to get a renormalization of the trajectories, though this could be possible also; we just use Corollary 8 to describe completely the path of the selfdual induction in the graph of graphs of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF]; then, using again the full machinery of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], we generate the trajectories, not by renormalization as in [START_REF] Smillie | Corinna Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF], but by families of words which are built inductively.

Theorem 11. Let I be a non-periodic 2n-gon type interval exchange transformation. We apply to it the algorithm of Corollary 8; let Φ k and e k be as defined in the proof of Corollary 8. We build inductively three families of words, consisting, at each stage of each iteration, of n -1 words w whose first letters are 1, ... n -1, n -1 words M whose first letters are 1, ... n -1 and last letters are 1, ... n -1 (independently) and n -1 words P whose first letters are 2, ... n and last letters are 1, ... n -1 (independently), in the following way:

• at the beginning the words w and the words M are 1,..., n -1, the words P are n1, 2, ... n -1; • at any step between the k-th and k + 1-th renormalization, if e k = +1: for every j which takes +, the word w, resp. the word M , ending with the letter Φ k (j), is replaced by wP , resp. M P , for the word P beginning with the letter n + 1 -Φ k (j); for every j which takes -, the word w, resp. the word P , ending with the letter Φ k (j), is replaced by wM , resp. P M , for the word M beginning with the letter n -Φ k (j); all the other words are left unchanged; • at any step between the k-th and k + 1-th renormalization, if e k = -1: for every j which takes -, the word w, resp. the word M , ending with the letter Φ k (j), is replaced by wP , resp. M P , for the word P beginning with the letter n + 1 -Φ k (j); for every j which takes +, the word w, resp. the word P , ending with the letter Φ k (j), is replaced by wM , resp. P M , for the word M beginning with the letter n -Φ k (j); all the other words are left unchanged.

Then the words w, taken after every step of every iteration, constitute all the bispecial words of the trajectories of I, i.e. the words w such that aw, bw, wc and wd appear also in the trajectories for letters a = b, c = d.

Proof This is a translation, through Corollary 8, of Theorem 2.8 of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF].