Keywords:

DIAGONAL CHANGES FOR EVERY INTERVAL EXCHANGE TRANSFORMATION

S ÉBASTIEN FERENCZI ABSTRACT. We give a geometric version of the induction algorithms defined in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] and generalizing the self-dual induction of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF]. For all interval exchanges, whatever the permutation and the disposition of the discontinuities, we define diagonal changes which generalize those of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]: they are exchange of unions of triangles on a set of triangulated polygons, which may be glued to create a translation surface. There are many possible algorithms depending on decisions at each step, and when the decision is fixed each diagonal change is a natural extension of the corresponding induction, which extends the result shown in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] in the particular case of the hyperelliptic Rauzy class. Furthermore, for that class, we can define decisions such that we get an algorithm of diagonal changes which is a natural extension of the underlying algorithm of self-dual induction, and we can thus compute an invariant measure for the normalized induction. The diagonal changes allow us also to realize the self-duality of the induction in the hyperelliptic class, and to prove this does not hold outside that class.

Interval exchanges were originally introduced by Oseledec [START_REF] Oseledec | The spectrum of ergodic automorphisms[END_REF], following an idea of Arnold [START_REF] Arnold | Small denominators and problems of stability of motion in classical and celestial mechanics[END_REF], see also Katok and Stepin [20]; an exchange of k intervals, denoted throughout this paper by I, is given by a probability vector of k lengths together with a permutation π on k letters; the unit interval is partitioned into k subintervals of lengths α 1 , . . . , α k which are rearranged by I according to π. The first tool to study interval exchanges is an algorithm of renormalization called the Rauzy induction [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF], which generalizes the Euclid algorithm of continued fraction approximation, and coincides with it for k = 2.

The Rauzy induction, further developed by Veech [START_REF] Veech | Interval exchange transformations[END_REF], and modified by Zorich [START_REF] Zorich | Finite Gauss measure on the space of interval exchange transformations. Lyapunov exponents[END_REF] and others, had a tremendous success in solving the big problems which made the history of this field, such as unique ergodicity [START_REF] Veech | Gauss measures for transformations on the space of interval exchange maps[END_REF] [START_REF] Masur | Interval exchange transformations and measured foliations[END_REF] or weak mixing [START_REF] Avila | Weak mixing for interval exchange maps and translation flows[END_REF] of almost all interval exchanges. These inductions are also a fundamental tool in the study of the space of moduli of Riemann surfaces, and the various strata of its unit tangent bundle, through the Teichmüller flow on a stratum. Consider the translation surface obtained by gluing opposite parallel sides of a polygon: to study the Teichmüller flow applied to this given surface, the Rauzy induction chooses an initial segment of an horizontal separatrix and follows its vertical separatrix till it intersects this initial segment, in order to obtain an interval exchange as induced map; then it considers shorter and shorter initial segments. But a basic flaw is that we only consider one horizontal separatrix; the da Rocha induction [START_REF] Lopes | Invariant measures for Gauss maps associated with interval exchange maps[END_REF] considers all the horizontal separatrices and one vertical separatrix, and its duality with the Rauzy induction appears in the natural extension of the induction process (this was predicted by Arnoux, an unpublished proof is attributed to Fisher, at last a proof has just been written by Inoue and Nakada [START_REF] Inoue | On the dual of Rauzy induction[END_REF]). The trouble with both procedures is that they destroy the symmetry of the geometrical situation, by giving a special role to one of the separatrices; because of that, each foliation admits several descriptions, and the relative position of the separatrices is not taken into account.

A new induction algorithm for interval exchanges, tentatively giving the same role to each horizontal and vertical separatrix, has been defined and studied in a long series of papers by the author, some of them together with Holton, Zamboni or da Rocha, in successive particular cases in [START_REF] Ferenczi | Structure of three-interval exchange transformations I: an arithmetic study[END_REF] [13] [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF] [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], then in full generality in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF]; in the first papers we called it the self-dual induction as, at least in the case of three intervals, it is self-dual for the duality mentioned above [START_REF] Ferenczi | A self-dual induction for three-interval exchange transformations[END_REF]. This induction has already been used successfully, as it seems to be more suitable than the existing ones to build explicit examples of interval exchanges with prescribed dynamical properties: the author and his collaborators build examples with weak mixing in [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF] [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] [8] [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] (though weak mixing is known to be widely verified, very few actual examples existed), and then the first known examples with eigenvalues, in [START_REF] Ferenczi | Structure of three-interval exchange transformations III: ergodic and spectral properties[END_REF] [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF], or, in [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF] [START_REF] Ferenczi | Eigenvalues and simplicity for interval exchange transformations[END_REF], with the famous property of simplicity defined by Veech [START_REF] Veech | A criterion for a process to be prime[END_REF]. Then it was used by Smillie and Ulcigrai [START_REF] Smillie | Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF] to study some classes of billiards, Delecroix [START_REF] Delecroix | Divergent directions in some periodic wind-tree models[END_REF] for the so-called windtree model, and recently by Bourgain [START_REF] Bourgain | On the correlation of the Moebius function with rank-one systems[END_REF] to build interval exchanges satisfying a famous conjecture of Sarnak, which states that the trajectories of any system with zero topological entropy are orthogonal to the Möbius function; this last result is generalized in [START_REF] Ferenczi | On Veech's question and Sarnak's conjecture for interval exchanges[END_REF], where we build examples satisfying both Sarnak's conjecture and Veech simplicity for any number of intervals and any Rauzy class. The fact that this induction does not privilege any separatrix should also make it the right instrument to solve some long-standing problems such as enumerating and counting the pseudo-Anosov diffeormorphisms in a given stratum.

At each stage we induce I on a disjoint union of k -1 intervals, and as for the other inductions, this generates an infinite path through a set of states. Even in the simpler case of the hyperelliptic Rauzy class, dealt with in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], the self-dual induction is neither unique nor straightforward to implement; as there is no canonical order between the parameters to be changed, there will be decisions to make, as in the problem of induction of a train-track [START_REF] Penner | Combinatorics of train tracks[END_REF], which is not solved in the general case. Thus we propose several algorithms, which create the same induction sub-intervals though at different speeds.

The latest development, after an idea of Smillie, Ulcigrai [START_REF] Smillie | Beyond Sturmian sequences: coding linear trajectories in the regular octagon[END_REF] and Hubert (unpublished) is to define also this induction in a geometric way, with a natural extension defined on a class of translation surfaces; this idea, which is very far from the original authors' minds, is carried out by Delecroix and Ulcigrai [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]; an exchange of triangles, and not rectangles as for the Rauzy induction, called diagonal change, is defined directly on translation surfaces, made with quadrilaterals, in the hyperelliptic component, and it provides, at each step when the decision is known, a natural extension of the self-dual induction for the interval exchanges studied in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], namely those with the symmetric permutation i → k + 1i and with alternate discontinuities, see Definition 1.3 below.

The present paper extends the geometric results of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] to the general algorithm defined in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF]; thus, for every interval exchange, we can define a natural extension (again, at each step when the decision is known, see Theorem 2.1 below) on sets of triangulated polygons (which may then be glued to create a translation surface) by exchanging unions of triangles. This is valid whatever the permutation and the order of the discontinuities for the interval exchange: for the examples of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], the geometric model is just the one of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] translated in the language of interval exchanges, but, in every other case, it is new and does make the combinatorial results of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] much more palatable, particularly in the intricate case where the discontinuities do not alternate (even in the hyperelliptic class, this case could not be treated with the quadrilaterals of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]). The castle forests which were used in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] as states of the induction appear naturally as a description of the polygons and their triangulation.

After making our algorithm work in the most general case, we turn again to the hyperelliptic case, to show some further results extending the work of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF], first for the symmetric permutation and then for all permutations in the hyperelliptic Rauzy class. In that case our induction is indeed self-dual: inverting the natural extension amounts, up to a renumbering of the coordinates, to exchanging the verticals and horizontals; also, we can define a combinatorial algorithm of decisions such that the corresponding algorithm of diagonal changes is actually invertible, thus being a natural extension, in the usual (full) sense, of the corresponding algorithm of self-dual induction, and we can compute the density of an invariant measure for the normalized induction. Outside the hyperelliptic class, however, as far as we can show, the diagonal change is the natural extension of the corresponding induction only when the decision is fixed, while that induction is not self-dual: thus in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] it is called the Ferenczi-Zamboni induction. In the last part of the paper, we investigate the relation between the states of our induction and the existing Rauzy classes, again with a full description in the case of the hyperelliptic class.

The present paper is essentially independent from [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF], as it gives a geometric point of view, and the latter a word combinatorial one; just some proofs of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] are used in Section 1.5 without being duplicated here. It is also independent of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF], as our geometric point of view is unashamedly pedestrian and limited to the study of interval exchanges while [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] deals with more general objects, the only (but fundamental) element we use from [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] is the idea of the definition of polygons and diagonal changes. The author thanks Vincent Delecroix, Pascal Hubert and Corinna Ulcigrai for fruitful discussions about this idea and its consequences.

This research was carried out while the author was in Unité Mixte IMPA-CNRS in Rio de Janeiro. It was also partially supported by the ANR GeoDyn and the ANR DYna3S.

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 ≤ k -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 .
We shall use freely the notation

β 0 = γ 0 = 0, β k = γ k = 1; then ∆ i is the interval [γ i-1 , γ i [.
Warning: roughly half the texts on interval exchanges re-order the subintervals by π -1 ; the present definition corresponds to the following ordering of the I∆ i : from left to right, I∆ π(1) , ...I∆ π(k) . Figure 1 shows a 3-interval exchange with πi = 3i. Definition 1.2. I satisfies the infinite distinct orbit condition or i.d.o.c. of Keane [START_REF] Keane | Interval exchange transformations[END_REF]

if the k -1 negative orbits {I -n γ i } n≥0 ,1 ≤ i ≤ k -1, of the discontinuities of I are infinite disjoint sets. 0 β 1 γ 1 γ 2 0 1 1 β 2 I∆ 3 I∆ 2 I∆ 1 ∆ 1 ∆ 2 ∆ 3 FIGURE 1
As is proved in [START_REF] Keane | Interval exchange transformations[END_REF], the i.d.o.c. condition implies that I has no periodic orbit and is minimal: every orbit is dense. If π is primitive, that is π({1, ...j}) = {1, ...j} for every 1 ≤ j ≤ k -1, the i.d.o.c. condition is (strictly) weaker than the total irrationality, where the only rational relation satisfied by

α i , 1 ≤ i ≤ k and 1 is k i=1 α i = 1. Definition 1.3. Let I be a k-interval exchange; it has alternate discontinuities if β 1 < γ 1 < ...., β k-1 < γ k-1 , opposite alternate discontinuities if γ 1 < β 1 < ...., γ k-1 < β k-1 .
Definition 1.4. The induced map of a map 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 is in Y (in all cases considered in this paper, r(y) is finite).

We recall that the Rauzy induction consists in inducing I on the interval [0, β k-1 ∨ γ k-1 [, which gives an interval exchange with a new permutation (∨ and ∧ denote the supremum and infimum). The Rauzy induction partitions the set of interval exchanges, or equivalently the set of (primitive) permutations, into equivalence classes called Rauzy classes; the two-sided Rauzy induction allows us to induce also on [β 1 ∧ γ 1 , 1[ and creates extended Rauzy classes. Their link with connected components of strata in the moduli space of abelian differentials is described in [START_REF] Kontsevich | Connected components of the moduli spaces of Abelian differentials with prescribed singularities[END_REF]. Among the Rauzy classes of permutations on {1, . . . , k}, a particular one is the hyperelliptic class which contains the symmetric permutation i → k + 1i, 1 ≤ i ≤ k, and is also an extended Rauzy class; each hyperelliptic Rauzy class corresponds to a so-called hyperelliptic component in the above strata.

The induction(s).

Starting from an interval exchange, and with a word-combinatorial motivation detailed in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] (namely, we want to know all the bispecial words of the associated language), we aim to build the points where the negative orbits of the discontinuities of I approximate the discontinuities of I -1 . By approximating the discontinuities of I -1 from the right and the left, we build small intervals around them. We suppose first I has alternate discontinuities, as this makes things much easier at the initial stages; the opposite condition works similarly, the only difference being in the initial state, see Section 2.2 below.

Thus we want to build

k -1 nested families of subintervals E i,n = [β i -l i,n , β i + r i,n [ 1 ≤ i ≤ k -1, so that E i,0 = ∆ i ,
and the E i,n are the intervals containing β i , and whose endpoints are the successive (where

I -m ′ γ j ′ is after I -m γ j if m ′ > m) I -m γ j which fall closest to β i .
The number n of the stage will be omitted whenever it is not absolutely necessary: when we go from one stage to the next, E i,n will be E i and E i,n+1 will be E ′ i .

Proposition 1.1. Given any subinterval E of ∆ i containing β i , there is a minimal m < 0 and unique j such that I -m γ j is in the interior of E; this point I -m γ j is different from β i .

Proof As I is minimal, there exist some points I -m γ j in the interior Ẽ of E. We take a minimal m; then I m is continuous on Ẽ; if there exist two different points I -m γ j 1 and I -m γ j 2 , j 1 < j 2 , in Ẽ, then I m Ẽ contains the interval [γ j 1 , γ j 2 ] and thus, because of the alternate discontinuities, the point β j 1 +1 , which implies that I m-1 Ẽ contains some γ l , and this is a contradiction. The point I -m γ j is different from all points β i , 1 ≤ i ≤ k -1, because of the i.d.o.c. condition. Definition 1.5. γ(E) is the unique point I -m γ j defined in Proposition 1.1. φ(E) is the one of the two subintervals of E with endpoints γ(E) which contains β i .

Thus, for a given

E i ⊂ ∆ i , γ(E i ) is indeed the first element I -m γ j , m > 0, 1 ≤ j ≤ k -1, to
fall in the interior of E i . Then we could tentatively define E ′ i to be φ(E i ). However, it may very well happen that, for example, γ(E 1 ) = I -5 γ 1 while γ(E 2 ) = I -2 γ 1 and γ(E ′

2 ) = I -3 γ 1 , which creates a desynchronization between the tentatives E ′

1 and E ′ 2 ; then it seems natural to wait before cutting E 1 , that is to put E ′ 1 = E 1 . Thus, for each i, at each stage, we make a decision, either to put

E ′ i = E i or to define E ′ i = φ(E i ), the subinterval [γ(E i ), β i +r i [ or [β i -l i , γ(E i )[ which contains β i .
Thus, in the case of alternate discontinuities, we can define formally our induction as follows.

Definition 1.6. For an interval exchange I, given a disjoint union of intervals

E i = [β i -l i , β i + r i [⊂ ∆ i , 1 ≤ i ≤ k -1
, and a nonempty subset F of {1, ...k -1}, an induction with decision F creates the intervals E ′ i where

• if i is in F , E ′ i = φ(E i ); • if i is not in F , E ′ i = E i .
This formal definition applies to any nonempty subset F of {1, k -1}. Concretely, we shall use it in the course of an induction process, where we have intervals E i,n at stage n; then the set F will depend on n, and at each stage we shall restrict ourselves to some particular sets F , explicited in Definition 1.9 below, for which we shall be able to identify the new intervals. This still leaves many different possible decisions at each stage, and thus different induction processes; however, as is shown in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF], all sequences of decisions for which, for every 1 ≤ i ≤ k -1, E ′ i = E i at infinitely many stages yield the same sequences of different intervals, though not numbered in the same way. To define sequences of decisions which makes the induction work is non-trivial: it is done in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] for some permutations, in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] for all permutations. These are indeed induction algorithms because the intervals E ′ i are built from the E i by using S where throughout this paper, S denotes the induced map of I on the set ∪ k-1 i=1 E i .

1.3. Examples on three intervals. We consider the three-interval exchange of Figure 1 above, with the symmetric permutation 1 → 3, 2 → 2, 3 → 1, and alternate discontinuities, as in Section 2.2 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF]. S is always the induced map of

I on E 1 ∪ E 2 .
At the initial stage,

E 1 = [0, α 1 [, E 2 = [α 1 , α 1 + α 2 [. By the induced map S, each E i is partitioned into two arrival intervals [β i -l i , β i [ and [β i , β i + r i [, and two departure intervals [β i - l i , γ(E i )[ and [γ(E i ), β i + r i [, with γ(E 1 ) = I -1 γ 2 , γ(E 2 ) = I -1 γ 1 .
S sends by a translation the two departure intervals of E 1 onto the arrival intervals of length r 2 and l 1 , the two departure intervals of E 2 onto the arrival intervals of length r 1 and l 2 .

β 1 A 1 B 1 C 1 β 2 A 2 B 2 C 2 -→ l 1 -→ r 1 -→ r 2 -→ l 1 -→ l 2 -→ r 2 -→ r 1 -→ l 2 FIGURE 2
This implies the train-track equalities

l 1 + r 1 = r 2 + l 1 , l 2 + r 2 = r 1 + l 2 , which in turn imply r 1 = r 2 .
We go now from intervals to polygons, by adding heights L i > 0 and R i > 0, such that the vectors -→ l i = (l i , -L i ) and -→ r i = (r i , R i ) satisfy the same train-track equalities as their first components, namely

-→ l 1 + -→ r 1 = -→ r 2 + -→ l 1 , -→ l 2 + -→ r 2 = -→ r 1 + -→ l 2 .
We draw quadrilaterals as in Definition 1.11 below, such that S will appear as a section of the linear flow on the translation surface defined by glueing them by their opposite equal sides: we have

-→ l 1 , -→ r 1 , -→ l 2 , -→ r 2 as lower sides, -→ r 2 , -→ l 1 , -→ r 1 ,
-→ l 2 as upper sides, and we can glue the upper -→ l 1 to the lower -→ l 1 , etc The projections, on the horizontal containing the β i , of the lower, resp. upper, sides give the arrival, resp. departure, intervals of S. We get two parallelograms (Figure 2), and call polygon i the one with lowest point β i ; they have a natural triangulation by the triangles

β 1 A 1 B 1 and A 1 B 1 C 1 , resp. β 2 A 2 B 2 and A 2 B 2 C 2 ,
which we call pasting triangles. Note that in the pictures we have exaggerated the distance from β 1 to β 2 so that the initial intervals E 1 and E 2 do not appear as adjacent, as this adjacency is irrelevant.

The tentative new E i (if i is in F ) is one of the two subintervals [γ(E i ), β i + r i [ or [β i -l i , γ(E i ),
according to the respective positions of β i and γ(E i ). These are given by the signs of the quantities l ir 2-i = l ir i , which are nonzero by the i.d.o.c. condition.

First step. We suppose that l 2 < r 2 = r 1 < l 1 . This means that the vertical of β 1 in the polygon 1 intersects the subpolygon which lies to the right of the diagonal β 1 C 1 (this is a triangle, β 1 B 1 C 1 , though this will not be always the case in more general situations, but not a pasting triangle), the vertical of β 2 in the polygon 2 intersects the subpolygon

β 2 A 2 C 2 .
First possible decision: F = {1}: then we keep in the new polygon 1 the subpolygon which intersects the vertical of β 1 , namely β 1 C 1 B 1 , and this becomes the new lower pasting triangle

β 1 A ′ 1 B ′ 1 -→ r ′ 1 -→ l ′ 1 -→ l 1 -→ l 1 -→ r 2 -→ l ′ 1 FIGURE 3 β 1 A ′ 1 B ′ 1 C ′ 1 -→ r ′ 1 -→ l ′ 1 -→ l 1 -→ r ′ 2 = -→ r 2 -→ l ′ 1 FIGURE 4
β 1 A ′ 1 B ′ 1 .
The other subpolygon, β 1 A 1 C 1 , is cut (Figure 3) and pasted by its lower side, which has vector -→ l 1 , to the available upper side with vector 4), the triangle A ′ 1 B ′ 1 C ′ 1 which has been added on the polygon 1 becomes a pasting triangle, which explains the terminology. We get two parallelograms again, the parallelogram 2 remaining as in Figure 2.

-→ l 1 , which is C 1 B 1 = A ′ 1 B ′ 1 (Figure
β 2 A ′ 2 B ′ 2 -→ l ′ 2 -→ r ′ 2 -→ r 1 -→ r ′ 2 -→ l 2 -→ r 2 FIGURE 5 β 1 A ′ 1 B ′ 1 C ′ 1 D ′ 1 β 2 B ′ 2 A ′ 2 -→ r ′ 1 -→ l ′ 1 -→ l 1 -→ r 2 -→ l ′ 1 -→ r ′ 2 -→ l ′ 2 = -→ l 2 -→ l ′ 2 -→ r ′ 2 -→ r ′ 1 = -→ r 1 FIGURE 6
Up to this point, we have only translated in the context of interval exchanges the diagonal changes of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]; but in the present case they would allow only the decision F = {1}. We begin now to diverge from [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] by allowing other decisions.

β 1 A ′′ 1 B ′′ 1 = C ′ 1 C ′′ 1 = D ′ 1 -→ r ′′ 1 -→ l ′′ 1 -→ r ′ 2 -→ l ′ 2 -→ r ′ 1 -→ r ′′ 1 -→ l ′ 1 FIGURE 7
Second possible decision: F = {1, 2}. Then the subpolygon β 1 A 1 C 1 , is cut and pasted by its lower side, with vector -→ l 1 , to the available upper side with vector -→ l 1 , as in Figure 3, but also the subpolygon β 2 B 2 C 2 , is cut from the polygon 2 (Figure 5) and pasted by its lower side, with vector -→ r 2 , to the available upper side with vector -→ r 2 . The two pastings can be made in any order, and in the end we get Figure 6 with a pentagon 1 and triangle 2, and pasting triangles

β 1 A ′ 1 B ′ 1 , A ′ 1 B ′ 1 C ′ 1 , A ′ 1 C ′ 1 D ′ 1 , and β 2 A ′ 2 C ′ 2 .
Then, in view of the next step, the triangle 2 cannot be cut, while there are a priori two possible diagonals to cut the pentagon, namely β 1 C ′ 1 and β 1 D ′ 1 ; going back to the interval exchange, we see that the projections of D ′ 1 and C ′ 1 on the horizontal of β 1 correspond to two points on the negative orbits of discontinuities, and cut the interval 1 into three subintervals of lengths r ′ 2 , l ′ 2 and l ′ 1 . The way the pentagon has been constructed implies that the projection of C ′ 1 is before the projection of D ′ 1 (they are I -m γ and I -m ′ γ ′ for m < m ′ ). This information is given in the picture by the pasting triangles, which are

A ′ 1 B ′ 1 C ′ 1 and A ′ 1 C ′ 1 D ′ 1 , but not A ′ ! D ′ 1 B ′ 1 or B ′ 1 C ′ 1 D ′ 1 : C ′ 1 is above the diagonal A ′ 1 B ′ 1 , which indicates that the projection of C ′ 1 is after the projections of A ′ 1 and B ′ 1 , and D ′ 1 is above the diagonal A ′ 1 C ′ 1 , which indicates that the projection of D ′ 1 is after the projections of A ′
1 and C ′ 1 ; alternatively, we can write the parenthesized train-track equalities

-→ l ′ 1 + -→ r ′ 1 = ( -→ r ′ 2 + -→ l ′ 2 ) + -→ l ′ 1 , -→ l ′ 2 + -→ r ′ 2 = -→ r ′ 1 .
Either one of these properties implies that, at the next

β 1 A ′′ 1 B ′′ 1 = C ′ 1 C ′′ 1 = D ′ 1 β 2 B ′′ 2 A ′′ 2 C ′′ 2 -→ r ′′ 1 -→ l ′′ 1 -→ r ′′ 2 -→ l ′′ 2 -→ l ′′ 2 -→ r ′′ 2 -→ r ′′ 1 -→ l ′′ 1 -→ r ′ 1 FIGURE 8
step, we shall cut the pentagon by the diagonal

β 1 C ′ 1 . r 2 l 1 r 1 l 2 FIGURE 9
Second step. We suppose furthermore that 2r 1 > l 1 . If, at the first step, we have taken the second decision, the triangle 2 cannot be cut; if now we take any decision containing 2, the new interval E 2 , though it is uniquely defined, cannot be identified from the data we have; thus we take the decision F = {1}. As we have seen above, the pentagon 1 is divided into the subpolygons 7); we keep in the new polygon 1 the subpolygon which intersects the vertical, namely the quadrilateral

β 1 A ′ 1 D ′ 1 C ′ 1 and β 1 C ′ 1 B ′ 1 (Figure
β 1 A ′ 1 D ′ 1 C ′ 1 while the triangle β 1 C ′ 1 B ′
1 is pasted, by its lower side with vector -→ r ′ 1 , to the available upper side, with vector -→ r ′ 1 , which is on the triangle 2. We get Figure 8, with two quadrilaterals which are not parallelograms, but related by a rotation of angle π.

If, at the first step, we have taken the first decision, and then, at the second step, take F = {1, 2}, then, as in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF], the triangle 4 is cut, and pasted on the parallelogram 2 along the side with vector 2 is cut as in Figure 5, and pasted on the parallelogram 1 along the side with vector

β 1 B ′ 1 C ′ 1 of Figure
-→ r ′ 1 , while the triangle β 2 B 2 C 2 of Figure
-→ r ′ 2 = -→ r 2 ,
and what we get is again Figure 8.

1.4. Castle polygons and diagonal changes. The plane is oriented; when a given segment is said to correspond to some vector, the vector goes from left to right (there will be no vertical segment).

Definition 1.7. A set of castle polygons is a set of k -1 polygons, each one equipped with a triangulation by pasting triangles such that (1) the lowest vertex in the polygon i is denoted by β i , and no other vertex is on the vertical of β i , (2) the lower sides in the polygon i correspond to vectors

-→ l i = (l i , -L i ), going from A i to β i and -→ r i = (r i , R i ), going from β i to B i , with l i > 0, r i > 0, L i > 0, R i > 0, 1 ≤ i ≤ k -1, (3) the upper sides of the polygons i, 1 ≤ i ≤ k -1, form a partition of the set { -→ l 1 , - → r 1 , ..., --→ l k-1 , --→ r k-1 }, (4) β i A i B i
is a pasting triangle; every pasting triangle except the β i A i B i has one lower side with finite nonzero slope, one left upper side with finite positive slope, one right upper side with finite negative slope, (5) every pasting triangle except the β i A i B i is pasted by its lower side onto an upper side of another pasting triangle, (6) there is no strict subset J of {1, ...k -1} such that all the upper sides of the polygons i, i ∈ J correspond to vectors -→ l j or -→ r j for j ∈ J.

In a set of castle polygons, the vectors must satisfy train-track equalities; for

1 ≤ i ≤ k -1, -→ l i + -→ r i
is the sum of the vectors of the upper sides of the polygon i; furthermore, we get parenthesized train-track equalities by putting, in the second members of the equalities, a set of parentheses around each sum of vectors corresponding to a pasting triangle (we can omit the outer set of parentheses corresponding to

β i A i B i ).
In [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] the induction is used to generate the names (for the natural coding) of the bispecial intervals: they appear as labels of edges in some trees, constituting forests which can be naturally associated with castle polygons:

Definition 1.8. The castle forest of a set of k -1 castle polygons is a set of k -1 castle trees defined by
• there is one vertex on each upper side of each pasting triangle, labeled l i , resp. r i when it is also an upper side -→ l i , resp. -→ r i of a polygon, • from every vertex which is also on the lower side of a pasting triangle, there is an edge, oriented upwards and going to the left, resp. right, to the vertex corresponding to the upper left, resp. right, side, of this pasting triangle, • for the i such that the polygon i is a triangle, there is a vertex at the lowest point of this triangle, and a single edge, oriented upwards, from this vertex to the one corresponding to the upper side of the triangle.

The tree structure of the castle forest is exactly the one described by the parenthesized traintrack equalities. Also, for each polygon i, there is a tree defined naturally by its triangulation into pasting triangles: we put a vertex in each triangle, for example on its lowest side (or lowest point if it is a β i A i B i ) and an edge between two triangles which have a common side. Then the castle tree of the polygon i is obtained from that tree by orienting it, deleting the lower edge when there is one, and adding edges going to the upper sides of the polygon.

For the examples of Section 1.3, Figure 9 gives the castle forest embedded in the polygons of Figure 2, which is the one in Figure 2.6 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] (minus the edge and root labels).

l 1 r 2 l 2 r 1 FIGURE 10
In Figure 10 we show both the castle forest embedded in the polygons of Figure 6 (Figure 2.8 or 2.9 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] minus the edge and root labels), and the trees describing the triangulation of Figure 6, made with two edges in the pentagon, and no edge in the triangle. Note that the above-mentioned names which label the edges in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] can be seen here as labels of the upper sides of the pasting triangles.

We define now two operations on castle polygons. Definition 1.9. A forward diagonal change on a set of castle polygons is defined as follows: let H be the set of i such that the polygon i is not a triangle. Let F be a nonempty subset of H, called a (forward) decision. For each i in F , let C i be the upper vertex of the pasting triangle with lower side A i B i ; then we cut the polygon i into two subpolygons by the diagonal β i C i , keep in the new polygon i the subpolygon which contains the vertical of β i , and paste the other one by its lower side onto the one upper side of a castle polygon which corresponds to the same vector ( -→ l i or -→ r i ). The cuttings and pastings for different i in F can be made in any order. The pasting triangles of the new set of castle polygons are deduced from the ones in the original set by deleting the diagonals A i B i , i ∈ F , and adding all the former sides along which a pasting has just been done.

Lemma 1.2. The image of a set of castle polygons by a forward diagonal change satisfies all the properties of a set of castle polygons, except that some β i C i may be vertical.

Proof

The non-trivial point to check is that any subpolygon which has been cut is pasted to one of the new castle polygons; as we can cut the polygons successively, it suffices to check that the part we cut from the polygon i does not have to be pasted on itself; but in that case, if -→ z i is the lower side of the subpolygon which has been cut from the polygon i, -→ z i is an upper side of the subpolygon which has been cut from the polygon i; if z i is the first coordinate of -→ z i , and zi is the horizontal distance from C i to the one of the points A i or B i which is in the subpolygon which has been cut from the polygon i, we must have zi < z i < zi , impossible. Also, by definition each one of the new lower side vectors -→ l i or -→ r i is also an upper side of a subpolygon which has been cut, and thus a new upper side vector, hence the conclusion of the lemma.

Definition 1.10. A backward diagonal change on a set of castle polygons is defined as follows: let H -be the set of i such that

• either R i > L i , the unique upper side in the set of castle polygons with vector -→ r i is not the only upper side of its polygon, and the lower side of the pasting triangle containing it has positive slope, • or L i > R i , the unique upper side in the set of castle polygons with vector -→ l i is not the only upper side of its polygon, and the lower side of the pasting triangle containing it has negative slope, Let F be a nonempty subset of H -, called a (backward) decision. Then for each i in F , let ζ i be the lower side of the pasting triangle containing the upper side used in the definition of H -; then we cut the relevant polygon j in two parts by the diagonal ζ i , keep the lower part in the new polygon j and paste the upper part, by the upper side used in the definition of H -, onto the lower side in the set of castle polygons with the same vector -→ r i or -→ l i . The cuttings and pastings for different i in F can be made in any order. The pasting triangles of the new set of castle polygons are deduced from the ones in the original set by adding the diagonals A i B i of the new polygons for i ∈ F , and deleting the former diagonals ζ i for i in F . Lemma 1.3. The image of a set of castle polygons by a backward diagonal change satisfies all the properties of a set of castle polygons, except that some A i B i may be horizontal.

Proof

The proof follows immediately from the definitions.

We check first that our definitions are nonempty, as independent as they can be of the decisions, and that the backward and forward changes are locally inverse to each other: Lemma 1.4. For any set of castle polygons

• H and H -are nonempty;

• two forward diagonal change with decisions F 1 and F 2 give the same new vectors -→ r i and -→ l i for any i ∈ F 1 ∩ F 2 ; • two backward diagonal changes with decisions F 1 and F 2 give the same new vectors -→ r i and -→ l i for any i ∈ F 1 ∩ F 2 ; • the composition of a a forward and backward, resp. backward and forward, diagonal change with the same decision is the identity.

Proof H is nonempty as there are 4k -4 sides for k -1 polygons, thus not every polygon is a triangle. Suppose H -is empty. We take an i such that R i > L i , and look at the upper side in the set of castle polygons with vector -→ r i . If it is the only upper side of a polygon j, then -→ r i = -→ l j + -→ r j and thus R j > R i > L i . Otherwise, the lower side of the pasting triangle containing it has negative slope, and, if ζ i,1 is the right upper side of that triangle and L i,1 the length of its vertical projection, then L i,1 > R i ; if ζ i,1 is not an upper side of a polygon, then it is the lower side of a pasting triangle, whose right upper side is ζ i,2 , with a vertical projection of length L i,2 , and L i,2 > L i,1 ; and so on until some ζ i,s is an upper side of a polygon, thus corresponds to some vector -→ l j , and

L j = L i,s > ... > L i,1 > R i > L i . Similarly, if L i > R i , we find some j such that R j > L i > R i or L j > L i > R i ,
and for every i we have found a j such that L j ∨ R j > L i ∨ R i , which is impossible.

It follows from the definitions that, for a given i and forward change, the new vectors -→ l i . and -→ r i depend only on the subpolygon which is cut from the polygon i, and this is the same for all the decisions F such that i is in F .

For a given i and backward change, the new vectors -→ l i . and -→ r i are determined by the subpolygon which is pasted on the polygon i; in general, this is a union of (before the change) pasting triangles, and -→ l i and -→ r i depend only on the lower one, which is the same for all the decisions F such that i is in F .

The last assertion comes from the definition, and the important fact that after a forward change has cut a left part of the polygon i, then the new L i is bigger than both the old L i and R i , and thus than the new R i which is the same as the old one, and similarly R i > L i after a forward move has cut a right part of the polygon i.

Note that if i is not in F the vectors -→ l i and -→ r i are never changed. When i is in F , the subpolygon which is pasted on the polygon i by a backward change may depend on other elements of F ; for example if we make a backward change from Figure 6 and 1 is in F , the subpolygon to be pasted on the polygon 1 may be either the triangle

A ′ 1 B ′ 1 C ′ 1 , if A ′ 1 C ′ 1 D 1 is pasted on 2 because 2 is in F , or the quadrilateral A ′ 1 B ′ 1 C ′ 1 D ′ 1 otherwise
. This contrasts with the polygon which is cut from the polygon i by a forward change, which depends only on whether i is in F .

We look now at infinite iterations of diagonal changes, which supposes we are always in sets of castle polygons. To ensure that infinitely many successive forward diagonal changes are possible from a given set of castle polygons, a sufficient condition is that this set is obtained by a finite number of successive forward diagonal changes from the initial set of an interval exchange satisfying the i.d.o.c. condition, see Proposition 1.7 below; another sufficient condition is that the l i and r i have no rational relations except those generated by the train-track equalities. In an infinite sequence of forward changes, the vectors -→ l i and -→ r i become more and more vertical, their future values being vectors of upper sides of pasting triangles.

To ensure that infinitely many successive backward diagonal changes are possible from a given set of castle polygons, a sufficient condition is that the L i and R i have no rational relations except those generated by the train-track equalities. In an infinite sequence of backward changes, the vectors -→ l i and -→ r i become more and more horizontal, their future values being vectors of lower sides of pasting triangles.

We prove now in the general setting a fundamental result which in the case of forward changes coming from an i.d.o.c. interval exchange is just a consequence of minimality.

Theorem 1.5. If we make infinitely many successive diagonal changes from a given set of castle polygons

• forward, then for each i, l i,n and r i,n tend to zero, L i,n and R i,n tend to infinity, when n tends to infinity; • backward, then for each i, L i,n and R i,n tend to zero, l i,n and r i,n tend to infinity, when n tends to infinity; • in both cases the sequences of successive (different) values of -→ r i and -→ l i is the same, whatever the sequence of decisions.

Proof

We look first at forward changes.

Suppose that l i,n → 0 but the polygon i has a part cut from the left infinitely many times; then L i,n is increased infinitely many times by some positive quantity which is the length of the vertical projection of some side of a pasting triangle, and thus at least the length of the vertical projection of some side of a pasting triangle at stage 0, as these quantities are increasing, thus L i,n → +∞. The total area of the set of castle polygons at stage n is constant, and is at least the area of the lower pasting triangle of the polygon i, which is 1 2 (l i,n R i,n + r i,n L i,n ). If r i,n → 0, the polygon i has a part cut from the right infinitely many times, and by the above reasoning R i,n , and thus l i,n R i,n , tend to infinity. If r i,n → 0, r i,n L i,n tends to infinity. In both cases, we have a contradiction. And the same reasoning leads to a contradiction if r i,n → 0 but the polygon i has a part cut from the right infinitely many times.

Suppose that l i,n + r i,n → 0, but the polygon i is cut infinitely often. We take N large enough, so that all the l j,n and r j,n which do not tend to zero will not be changed further, while the others are small. Let --→

x j,N , x = l or x = r, be the vector of the upper side of the polygon i at stage N which contains the vertical of β i . By the definition of the forward changes, after finitely many stages the diagonal A i B i will have vector --→

x j,N . Thus x j,N ′ = l i,N ′ + r i,N ′ , hence x j,n cannot tend to zero, and thus x j,n = x j,N for all n ≥ N. But nothing can ever be pasted on the diagonal A i B i as this would create an x j,n+1 < x j,n . Thus the polygon i cannot be cut ultimately, contradiction.

Let now J be the set of i such that the polygon i is cut infinitely many times; J is nonempty as in infinitely many forward changes at least one polygon i is cut infinitely many times. An i is in J if and only if l i,n and r i,n tend to zero. Because of the train-track equalities, for n large enough the upper sides of polygons i for i in J can only have vectors -→ x j , x = l or x = r, j ∈ J, hence all the -→ x j , x = l or x = r, j ∈ J must be vectors of upper sides of polygons i, i ∈ J; thus J = {1, ...k -1} by (6) of Definition 1.7.

We look now at backward changes. Suppose that L i,n → 0 but the polygon i has a part pasted to the left infinitely many times; then we make the same reasoning using the areas as above, mutatis mutandis (l and L, r and R exchanged, "cut from" replaced by "pasted to", "vertical projection" replaced by "projection") and get a contradiction. And similarly if R i,n → 0 but the polygon i has a part pasted to the right infinitely many times.

Suppose that L i,n + R i,n → 0, but the polygon i is pasted infinitely often; then for example L i,n → 0 and R i,n → 0. Then for n large enough L i,n < R i,n , and by the definition of the forward changes the polygon i cannot ever have a part pasted to the left, contradiction.

Let now J be the set of i such that the polygon i is pasted infinitely many times; J is nonempty as in infinitely many backward changes at least one polygon i is pasted infinitely many times. An i is in J if and only if l i,n and r i,n tend to infinity. Because of the train-track equalities, for n large enough the upper sides of polygons i for i in J c can only have vectors -→ x j , x = l or x = r, j ∈ J c , hence all the -→ x j , x = l or x = r, j ∈ J c must be vectors of upper sides of polygons i, i ∈ J c ; thus J = {1, ...k -1} by (6) of Definition 1.7.

The last assertion comes from the fact that any infinite sequence of decisions creates the same pasting triangles: they depend only on the initial values of the -→ l i and -→ r i ; the stages during which any given pasting triangle exists may vary, but as every sequence of decisions changes each polygon to the left and to the right infinitely often, every pasting triangle created by one sequence will be created by any other sequence. 1.5. Diagonal changes project on inductions. The algorithms of induction described in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] use states defined by castle forests, or parenthesized train-track equalities involving the r i and l i ; in a given state, we know the γ(E i ) of Definition 1.5 for i in some set H, and an induction is defined by some inequalities involving the l i and r i , and a decision F ⊂ H, and creates new parameters l i and r i in a new state.

To each of these states correspond sets of castle polygons, with suitable L i and R i , and the same parenthesized train-track equalities but involving the -→ r i and -→ l i , we define H as in Definition 1.9 and we take a decision F ⊂ H: it follows from the definitions and the theory in Section 2 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] that the two sets H coincide, the inequalities involving the l i and r i are exactly those determining whether the diagonal β i C i is left or right of the vertical of β i , and the forward diagonal change defined by F and projected on the parameters l i , r i is just the induction defined by F in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF].

We define here the initial set of castle polygons when I has alternate discontinuities; in that case the initial intervals are

E i = [γ i-1 , γ i [.
• l i is the distance from γ i-1 to β i , 1 ≤ i ≤ k -1; • r i is the distance from β i to γ i , 1 ≤ i ≤ k -1; • if π -1 k = 1: the upper sides of the polygon 1 are --→ r k-1 and -→ l 1 , the upper sides of the polygon πi = 1 are --→ r i-1 and -→ l i ; • if π -1 k = j = 1, the upper sides of the polygon πi, 2 ≤ i ≤ k -1, i = j, are --→ r i-1
and -→ l i ; the only upper side of the polygon π1 is -→ l 1 ; the upper sides of the polygon πk are --→ r k-1 , --→ r j-1 , -→ l j ; • the L i > 0 and R i > 0 have no rational relations except those generated by the train-track equalities, and satisfy R j-1 < L j if π -1 k = j = 1; • the polygons are equipped with the unique triangulation compatible with Definition 1.7.

The triangulation is defined trivially for the triangle and the quadrilaterals, and for the pentagon --→ r j-1 and -→ l j are the upper sides of the same triangle.

Suppose now we start from an initial set of castle polygons defined by an i.d.o.c interval exchange I with alternate discontinuities; then, by the definitions, at any given stage the diagonal A i B i projects (on the horizontal of β i ) on the interval E i . Thus we can translate Proposition 2.3 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF]; the proof is not repeated here, but comes directly from the definitions. Lemma 1.6. At any given stage, each vertex of the polygon i, except β i , projects (on the horizontal of β i ) on a point I -s γ t in the interior of E i ; if a vertex X is (strictly) above a side Y Z of a pasting triangle, the projection of X is (strictly) after (i.e. corresponds to a larger s) than the projections of Y and Z.

If an upper side of the polygon i has vector -→ l j , resp. -→ r j , then its horizontal projection is an interval of continuity of S, sent by S onto [β jl j , β j [, resp. [β j , β j + r j [.

The following result translates Proposition 2.25 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF], or can be recovered from Theorem 1.5 and the remark that the i.d.o.c. condition prevents the existence of vertical β i C i .

Proposition 1.7. An i.d.o.c interval exchange I with alternate discontinuities, through any sequence of decisions F n , generates an infinite sequence of forward diagonal changes, such that each polygon has a part cut from the left, resp. right, for infinitely many n.

A converse of Proposition 1.7 is Theorem 2.28 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF]; this is the key to the construction of examples which is the main use of this induction. Here we just quote it as it will not be used in the present paper, and its non-trivial proof is based on word combinatorial techniques, for which we do mot know any ready geometric translation. This uses formal diagonal changes where the actual values of the -→ l i and -→ r i are not involved, just the description of what is cut and pasted; for a given description of the set of castle polygons, not every formal diagonal changes is possible, as the positions of the verticals may satisfy some symmetry conditions; for example in Figure 7, whatever the actual value of the parameters, the polygons 1 and 2 cannot be cut from different sides. These allowed formal changes are defined in Corollary 2.16 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF], as those for which the resulting train-track equalities do have solutions in the positive cone.

Proposition 1.8. Any infinite sequence of allowed formal forward diagonal changes, starting from an initial set as in Definition 1.11, and such that each polygon has a part cut from the left, resp. right, for infinitely many n, defines at least one k-interval exchange with permutation π and alternate discontinuities, satisfying the i.d.o.c. condition, which generates it as in Proposition 1.7.

INTERVAL EXCHANGES WITHOUT ALTERNATE DISCONTINUITIES

Without the condition of alternate discontinuities, or the opposite condition, our induction has to deal with a finite number of transient states at the beginning, and diagonal changes loose a part of their interest as in these states there are no satisfying backward changes. Still, the presentation of the new induction through forward diagonal changes is more elegant than the one in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF], and will be used in Section 4.

We give a general definition for the induction, taking into account that an interval E i may now contain several points β i , or several I -m γ i for the same m; this definition applies always, while the simpler Definition 1.6 applies at every stage when I has alternate discontinuities, and a modified version (taking into account that E i is not always a subinterval of ∆ i ) applies for opposite alternate discontinuities, and after a finite number of initial stages for general I. Of course, when both definitions apply, they are equivalent. Definition 2.1. For an interval exchange I, we start from a disjoint union of intervals E i = [β il i , β i+z i + r i [ for i in a subset K of {1, ...k -1} and z i ≥ 0. For a given i, let m be such that at least one (but possibly several) I -m γ r is in the interior of E i and no I -s γ t , is in the interior of E i for s < m. Then, if i is in F , the induction with decision F creates all possible subintervals E ′ of E i such that

• E ′ contains at least one β i ,

• each endpoint of E ′ is either an endpoint of E i or an I -m γ r ,

• the interior of E ′ contains no I -m γ t .

The E ′ are then numbered so that

E ′ j = [β j -l ′ j , β j+z ′ j + r ′ j [ for j in K ′ . If i is not in F , E ′ i = E i . 2.1.
Examples on four intervals. We take first the example in Figure 11, with permutation

1 → 4, 2 → 3, 3 → 2, 4 → 1, and γ 1 < γ 2 < β 1 < γ 3 < β 2 < β 3 .
We have two intervals [γ i , γ i+1 [ which contain points β i , and thus the parameters of our induction are l 1 , the distance from γ 2 to β 1 ; r 1 , the distance from β 1 to γ 3 ; l 2 , the distance from γ 3 to β 2 ; u 2 , the distance from β 2 to β 3 ; r 2 , the distance from β 3 to 1; we add the auxiliary quantities v 1 , the distance from 0 to γ 1 , and v 2 , the distance from γ 1 to γ 2 , which will be used later, and remark that by definition of the transformation we have v 1 = r 2 , v 2 = u 2 . We define vectors -→ l i = (l i , -L i ), -→ r i = (r i , R i ), -→ u 2 = (u 2 , 0). The train-track equalities imply l 1 = l 2 ; we suppose r 1 < l 1 = l 2 and

r 2 < l 1 = l 2 . 0 β 1 γ 1 γ 2 γ 3 0 1 1 β 2 β 3 l 1 r 1 l 2 u 2 r 2 v 1 v 2 FIGURE 11 β 1 A 1 B 1 C 1 β 2 β 3 A 2 B 2 C 21 C 22 -→ l 1 -→ r 1 -→ r 1 -→ l 2 -→ l 2 -→ r 2 -→ r 2 -→ l 1 -→ u 2 -→ u 2 FIGURE 12
The generalized castle polygons corresponding to this situation are drawn in Figure 12; note that in the hexagon there is no diagonal A 2 C 22 or B 2 C 21 , which reflects the fact that the projection (on the horizontal of the β i ) of C 21 and C 22 are I -n γ 1 and I -n γ 2 for the same n.

Then at the next stage, if F = {1, 2}, the triangles β 1 A 1 C 1 and β 2 A 2 C 21 are cut and pasted in the usual way, respectively on the upper side with vector -→ l 1 and -→ l 2 , but also the lower triangle β 2 β 3 C 22 is cut, and pasted by its lower side with vector -→ u 2 onto the available upper side C 21 C 22 . The hexagon is replaced by two quadrilaterals, thus a polygon 3 is created and some vectors are renumbered accordingly. The three quadrilaterals we get in Figure 13 form a generalized set of castle polygons, but not a set of castle polygons because of the horizontal new A 2 B 2 .

We take now the permutation

1 → 4, 2 → 3, 3 → 1, 4 → 2, again with γ 1 < γ 2 < β 1 < γ 3 < β 2 < β 3 .
The parameters of the induction are again l 1 , r 1 , l 2 , u 2 , r 2 , and with l 1 < r 1 , r 2 < l 2 < u 2 we get the initial set of generalized castle polygons in Figure 14.

If F = {1, 2}, the triangle β 1 B 1 C 1 is cut and pasted on the quadrilateral 1, and the quadrilateral β 2 C 21 C 22 β 3 is cut and pasted by its lower side with vector -→ u 2 onto the available upper side A 2 C 21 . Thus the hexagon is replaced by a pentagon and a triangle, a polygon 3 is created and some vectors are renumbered accordingly. In the generalized set of three castle polygons we get in Figure 15, the pentagon 2 has again an horizontal A 2 B 2 , and no other pasting diagonal.

β 1 A 1 B 1 C 1 β 2 β 3 A 2 B 2 C 2 A 3 B 3 C 3 -→ l 1 -→ r 1 -→ r 3 -→ l 2 -→ l 2 -→ r 2 -→ r 2 -→ l 3 -→ l 3 -→ r 3 -→ r 1 -→ l 1 FIGURE 13
β 1 A 1 B 1 C 1 β 2 β 3 A 2 B 2 C 21 C 22 -→ l 1 -→ r 1 -→ r 1 -→ l 2 -→ l 2 -→ r 2 -→ u 2 -→ l 1 -→ u 2 -→ r 2 FIGURE 14 β 1 A 1 B 1 C 1 β 2 β 3 A 2 B 2 D 2 C 2 A 3 B 3 -→ l 1 -→ r 1 -→ r 1 -→ l 2 -→ l 2 -→ r 2 -→ r 2 -→ l 3 -→ r 3 -→ l 3 -→ r 3 -→ l 1 FIGURE 15
2.2. The general case. The above examples suggest that it might be possible to define backward changes, even in the case of horizontal A i B i as these indicate that former sides -→ u s have been pasted; but iterating them would be somehow meaningless except in the case of alternate discontinuities or the opposite case, as unchangeable vectors -→ u s would co-exist with long vectors -→ l i and -→ r i ; thus we shall not attempt to define backward diagonal changes.

For a general interval exchange I, satisfying the i.d.o.c. condition, the initial set of generalized castle polygons will be defined in several steps. It involves vectors -→ l i and -→ r i as before, though they will be defined only for those i for which we have an E i , which are defined below, and form a smaller set than before as one E i may contain several β j ; but we have also to use vectors -→ u s , which join two points β s and β s+1 when they do not have a γ j between them, these are horizontal as we want the two points β s and β s+1 to be in the polygon; the opposite situation is the case when two points γ j-1 and γ j do not have a β i between them: as can be seen in the examples of Section 2.1, these do not create sides in the initial polygons, as the corresponding (auxiliary) vectors -→ v j are pasted at a preliminary stage. The full process of building the initial polygons is as follows.

The interval E i is the unique interval [γ j-1 , γ j [ which is of the form [β i -l i , β i+z i +r i [ for z i ≥ 0; such i form a subset K of {1, ...k -1} and for i in K we define l i to be the distance from γ j-1 to β i , r i to be the distance from β i+z i to γ j , while u s is the distance, if it exists, from β s to β s+1 for i ≤ s ≤ i + z i -1. We shall use the auxiliary quantities v j , the distance from γ j-1 to γ j when [γ j-1 , γ j [ contains no β i , which may happen for j in a (possibly empty) set K 1 ; note that if also I[γ j-1 , γ j [ contains no γ t , which may happen for j in a (possibly empty) set K 2 , then v j is either l 1 , r k-1 or a u s ; to understand these notations, look at Figure 11 above, where

E 1 is [γ 2 , γ 3 [, E 2 is [γ 3 , 1[; then K 1 = {1, 2}
, and we define v 1 and v 2 as in Section 2.1, but as

I[0, γ 2 [ contains no γ t , K 2 = {1, 2} with v 1 = r 2 , v 2 = u 2 .
We define vectors -→ l i = (l i , -L i ), -→ r i = (r i , R i ), -→ u s = (u s , 0), and auxiliary ones -→ v j = (v j .V j ) for j in K 1 \ K 2 . The V j can have any value satisfying the corresponding train-track equalities, except that, if they exist, we take V 1 > 0 and V k < 0.

Then for i in K, the provisional polygon i has lower sides, from left to right, -→ l i from A i to β i , -→ u s (if they exist) from β s to β s+1 for i ≤ s ≤ i + z i -1, -→ r i from β i+z i to B i . To get its upper sides, we look at IE i , which is an interval [β t , β t+1 [, and partition it by all the γ s inside it; this gives, from left to right, subintervals of lengths r t ′ (for some t ′ ≤ t), v s , s 1 ≤ s ≤ s 2 , l t+1 , and then the upper sides of the provisional polygon i will be, from left to right,

-→ r t ′ , -→ v ′ s , s 1 ≤ s ≤ s 2 , -→ l t+1 , where -→ v ′ s = -→ v s when s is in K 1 \ K 2 , and, when s is in K 2 , -→ v ′ s is -→ l 1 , --→ r k-1 or -→ u s ′ if v s is l 1 , r k-1 or u s ′ . The provisional polygon i, if it is not a triangle, has A i B i as a pasting diagonal.
Also, for each j in K 1 \ K 2 , we add an auxiliary unnumbered polygon with lower side -→ v j , and whose upper sides correspond to the partition of I[γ j-1 , γ j [ by all the γ s inside it, as in the previous paragraph. Then we paste each auxiliary polygon, by its lower side with vector -→ v j , onto the available upper side with vector -→ v j ; the pasted sides with vector -→ v j are kept as pasting diagonals. The pastings can be made in any order, and at the end we get polygons i for i in K, together with some pasting diagonals, but generalized castle polygons are not necessarily triangulated, see Figures 12 and14 above; indeed, a triangulation will be built by forward diagonal changes in successive further steps, as in Figure 13.

The signs of the V j are not important (they could also be 0) as in general we do not define backward changes, except for V 1 and V k which may exist when there are no -→ u i , and V k < 0 ensures that in the case of alternate discontinuities we get the initial set of castle polygons in Definition 1.11 and can define backward changes, while V 1 > 0 ensures an equivalent construction in the opposite case, with E i = [γ i , γ i+1 [ in the initial state.

The forward diagonal change corresponding to the induction in Definition 2.1 is the following: we start from a set of generalized castle polygons, where the polygon i, i in K, has lower sides -→ l i from A i to β i , -→ u s (if they exist) from β s to β s+1 for i ≤ s ≤ i + z i -1, -→ r i from β i+z i to B i , and the upper sides of the polygons i, i in K, correspond to a partition of the set { -→

l i , i ∈ K, - → r i , i ∈ K, - → u s , i ∈ K, i ≤ s ≤ i + z i -1}.
Because of the i.d.o.c. condition, no vertex except β i is on the vertical of β i . We take a nonempty decision F ⊂ K, such that for all i in F the polygon i is not a triangle. The polygons i such that i is not in F will not be cut. Then, for i ∈ F let C i,j , 1 ≤ j ≤ y i , be the vertices of the polygon i other than A i , B i , and the β s . As in Figures 12 and14, we draw the cutting diagonals from β s , i ≤ s ≤ i + z i to

• if s > i, the rightmost (if such exist) C i,j which is between the verticals of β s-1 and β s ,

• if s = i, the rightmost (if such exist) C i,j which is between the verticals of β il i and β i , • if s < i + z i , the leftmost (if such exist) C i,j which is between the verticals of β s and β s+1 ,

• if s = i + z i , the leftmost (if such exist) C i,j which is between the verticals of β i+z i and

β i+z i + r i .
The polygon i is partitioned into subpolygons by the cutting diagonals. If a subpolygon contains the vertical of at least one β s , then it contains the verticals of β s for j ≤ s ≤ j + z ′ j ; the subpolygon is not moved, and becomes a part of the new polygon j. Any other subpolygon is cut, and pasted by its lower side -→ l i , -→ r i , or -→ u s , onto the available upper side -→ l i , -→ r i , or -→ u s . The new lower sides are then renumbered so that each new polygon j has lower sides -→ l j from the (possibly new) A j to β j , -→ u s (if they exist) from β s to β s+1 for j ≤ s ≤ j + z ′ j -1, -→ r j from β j+z ′ j to the (possibly new) B j ; the new upper sides are numbered accordingly, each lower side which has been created (and not just changed) appearing as an upper side of a subpolygon with a lower side -→ u s which has been cut, while the rightmost lower side and its corresponding upper side, which were -→ r i , are renumbered -→ r j , whether they are changed or not, where j is the highest number of the new polygons issued from the polygon i.

Because of minimality, after a finite number of forward changes, we get a set of castle polygons, satisfying all the properties of Definition 1.7; but, whenever I does not have alternate or opposite alternate discontinuities, if we make backward changes from those polygons, at some stage they show that there was at least one vector -→ u s in the initial set of castle polygons, by the presence of an horizontal side of a pasting triangle, and we cannot make infinitely many backward changes.

Natural extension and algorithms.

From the conclusions of Section 1.5, which generalize to the diagonal changes of Section 2.2, we get immediately the following theorem, which extends the results of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] to interval exchanges with every permutation and every disposition of the discontinuities.

Theorem 2.1. For any interval exchange I satisfying the i.d.o.c. condition, the forward diagonal changes defined in Section 2 by a decision F gives a natural extension of the induction defined in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] by the decision F . At any stage, if we build a translation surface through gluing the castle polygons by their opposite equal sides, the induced map S of I on ∪ k-1 i=1 E i is a Poincaré section of the linear flow on the surface.

there is in general a big obstacle described in the remark just after Lemma 1.4: in a given polygon, two different pasting triangles may have been pasted at the same stage or at two different stages, depending on the decision, and the value of the parameters in a given set of polygons do not seem to allow us to distinguish between these two situations; the only way we know to overcome this problem is to ensure that all polygons are quadrilaterals, and this is impossible in the general case, see Section 3.1 below. But this is possible in the hyperelliptic case, and a (new and non-trivial) invertible algorithm is described in Section 3.3 below. We mention another property, which is defined for surfaces and called best approximation in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]; it is still satisfied in the general case, even outside the hyperelliptic class, we state it here in our framework, though we give references instead of duplicating proofs. Proposition 2.2. In an infinite sequence of forward diagonal changes starting from an initial set of castle polygons defined by an i.d.o.c interval exchange, for any poluygon i in any set of castle polygons, in the rectangle whose diagonal is the lower side -→ l i , resp. -→ r i , starting from β i there is no vector from the lattice generated by the -→ l i and -→ r i , except -→ l i , resp. -→ r i . Moreover, all the possible vectors -→ l i , resp. -→ r i , having this property appear at some stage in the process.

Proof By Lemma 4.7 of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF], this property is equivalent to the fact that the induction generates all the bispecial factors of the associated language, and that fact is proved in Proposition 2.27 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF].

SYMMETRIC INTERVAL EXCHANGES

When I is in the hyperelliptic Rauzy class, the new induction, called the self-dual induction, has been studied from the word-combinatorial point of view in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], and the diagonal changes in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]. In the present section, we continue the study of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] with some new results. These results are written here for symmetric interval exchanges, i.e. when the permutation is πi = k + 1i, 1 ≤ i ≤ k -1, and with alternate discontinuities; they will be extended to the whole hyperelliptic Rauzy class by Theorem 4.3 below.

3.1.

Trees of relations. In this case, the induction and diagonal changes are defined as usual, but there are privileged decisions which allow us to have only quadrilaterals as castle polygons; this means that we can always find decisions such that, whenever we cut a part, for example from the left, of a quadrilateral, another part, coming from another quadrilateral, is pasted on its left, and vice-versa (these sets of quadrilaterals are called staircases in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF]). The existence of these decisions is not trivial: it was proved in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] using some combinatorial objects called trees of relations, and re-proved geometrically in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF], where the fundamental part played by the hyperelliptic involution is explained, and trees of relations are identified as triangulation trees of the sphere; it results from Section 2.8 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] or Section 3.4 of [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] that, outside the hyperelliptic class, it is not possible in general to find such decisions. Algorithms using trees of relations are described extensively in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], [START_REF] Ferenczi | Billiards in regular 2n-gons and the self-dual induction[END_REF] and [START_REF] Delecroix | Divergent directions in some periodic wind-tree models[END_REF]. We give here a summary of the results we need, which are either results of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] or their translations in the terminology of diagonal changes.

A tree of relations (not to be confused with a castle tree) is a non-oriented and non-rooted tree with k -1 vertices labeled i, 1 ≤ i ≤ k -1, and edges labelled +, -, or =, such that two adjacent edges never have the same label. Such a tree can be represented by a picture like Figure 16 (nonoriented), but by convention, in the text a +, resp. -, resp. =, edge between a and b is denoted by writing a +b, resp. a -b, resp. a =b; thus the tree in Figure 16 is also represented for example by 2 -1 +3 -4, 3 =5, or else 4 -3 =5, 3 +1 -2; the hats are there to avoid writing dubious assertions like 3 = 5. A tree of relations G defines three bijections s, p m, by • s(i) is the only j such that there is a = edge between i and j, or s(i) = i if there is no such edge, • p(i) is the only j such that there is a + edge between s(i) and j, or p(i) = s(i) if there is no such edge, • m(i) is the only j such that there is aedge between s(i) and j, or m(i) = s(i) if there is no such edge. Thus G defines a combinatorial class of sets of castle polygons, by the train-track equalities

-→ l i + -→ r i = --→ r m(i) + -→ l p(i) , 1 ≤ ≤ k -1:
any set of vectors as in Definition 1.7 satisfying them defines a set of castle polygons (quadrilaterals, indeed), associated with G, and always denoted by G.

For example the castle polygons in Figure 2, resp. 8, are associated with the tree of relations 1 -2, resp. 1 =2, while with the tree of relations in Figure 16 are associated sets of five castle polygons, whose upper sides are respectively -→ r 2 and -→ l 3 , -→ r 1 and -→ l 2 , -→ r 5 and -→ l 5 , -→ r 3 and -→ l 4 , -→ r 4 and -→ l 1 .

When a set of castle polygons is associated to a tree of relations, all the polygon are quadrilaterals; the train-track equalities, which do not need parentheses, can be simplified into a set of relations which have given their names to the trees, namely -→

l i = --→ l ps(i) , -→ r i = ---→ r ms(i) . -→ l i + -→ r i = -→ l s(i) + --→
r s(i) for all i, which gives only k -2 different nontrivial relations. This implies that the set of castle polygons is invariant by the rotation of angle π, which corresponds to the hyperelliptic involution, see [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF].

In a tree of relations, a positive, resp. negative induction branch is a maximal connected subtree withoutedges, resp. without + edges; the tree in Figure 16 defines the positive induction branches 2, 4, and 1 +3 =5, the negative induction branches 2 -1, 4 -3 =5. When a set of castle polygons is associated to a tree of relations, a positive, resp. negative, induction branch is accepted if for all its vertices i we have l i > r s(i) , resp. r i > l s(i) ; a positive, resp. negative, induction branch is backward accepted if for all its vertices i we have L i > R i , resp. R i > L i (note that the quantities l ir s(i) and L i -R i are invariant by s).

It is shown in Proposition 2.4 of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] that, if at one stage of an induction process the set of castle polygons, or equivalently the parenthesized train-track equalities, are associated to a tree of relations, and if the decision is made with the vertices of a disjoint union of accepted induction branches, then at the next stage the set of castle polygons is associated to a new tree of relations. Moreover, if I is a symmetric i.d.o.c. interval exchange with alternate discontinuities, the initial set of castle polygons is associated to the tree of relations 1 -(k -1) +2 -(k -2) +..., and if up to stage n -1 all the decisions have been made with the vertices of disjoint unions of accepted induction branches, then at stage n there exists at least one nonempty such decision. This translates in the usual way for forward diagonal changes on sets of castle polygons for a symmetric i.d.o.c. interval exchange with alternate discontinuities.

In the example of Section 1.3, at the beginning we have the tree of relations 1 -2 and if l 2 < r 2 = r 1 < l 1 , the only accepted induction branch is the positive branch 1; if l 1 < 2r 1 , at the second stage, after the change with decision F = {1}, the negative branch 1 -2 is accepted; thus, taking F = {1} in the first step and F = {1, 2} in the second step is a way, and indeed here the only way, to keep a set of quadrilaterals; taking F = {1, 2} in the first step, which obliges F = {1} in the second step, is a less subtle way to proceed, but for non-hyperelliptic interval exchanges such decisions creating polygons which are not quadrilaterals are unavoidable.

The same reasoning works also for backward diagonal changes, using backward decisions made with the vertices of disjoint unions of backward accepted induction branches.

From the definitions, we get that if we make a forward diagonal change with decision F , then for all i in F , the new vectors are given by -→

l ′ i = -→ l i ---→ r m(i) , -→ r ′ i = -→ r i whenever i is a vertex of a positive accepted induction branch, -→ l ′ i = -→ l i , -→ r ′ i = -→ r i - -→ l p(i)
whenever i is a vertex of a negative accepted induction branch. If we make a backward diagonal change with backward decision F , then for all i in F , the new vectors are given by

-→ l ′′ p(i) = -→ p(i) ---→ r m(i) , -→ r ′′ i = -→ r i whenever i is a vertex of a positive backward accepted induction branch, -→ l ′′ i = -→ l i , --→ r ′′ m(i) = --→ r m(i) - -→ l p(i)
whenever i is a vertex of a negative backward accepted induction branch.

3.2. Self-duality. The self-duality claimed in the name of our induction in the symmetric case [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] means that a backward change should be equivalent to a forward change after exchanging the horizontals and verticals; this equivalence does not hold in the general case, but, when we can use trees of relations, there is indeed such an equivalence, up to a permutation of the coordinates. An analogous result is stated and proved independently in [START_REF] Delecroix | Diagonal changes for surfaces in hyperelliptic components, to appear in Geometriae Dedicata[END_REF] in the setting of quadrangulations of hyperelliptic surfaces, while earlier a similar result has been proved in [START_REF] Ferenczi | A self-dual induction for three-interval exchange transformations[END_REF] for three intervals and a slightly different natural extension. Theorem 3.1. Let G0 be a set of castle polygons associated with the tree of relations 1 -(k -1) +2 -(k -2) +.... We suppose that, starting from the vectors -→ l i,0 , -→ r i,0 in G0 , we arrive to vectors -→ l i,n , -→ r i,n , by a sequence of forward diagonal changes with decisions F n made with the vertices of disjoint unions of accepted induction branches. Let --→ l i,0,d = (L i,0 , -l i,0 ), --→ r i,0,d = (R i,0 , r i,0 ); then there exist backward decisions F n,d made with the vertices of disjoint unions of backward accepted induction branches and two permutations σ n and τ n of {1, ...k -1}, such that, if starting from the vectors --→ l i,0,d , --→ r i,0,d we arrive to vectors --→ l i,n,d , --→ r i,n,d , by a sequence of backward diagonal changes with decisions F n,d , then L i,n,d = l σn(i),n , R i,n,d = r τn(i),n , l i,n,d = L σn(i),n , r i,n,d = R τn(i),n .

Proof

At stage n the vectors -→ l i,n , -→ r i,n are in a set of castle polygons associated to a tree of relations G n , with bijections s n , p n , m n ; the vectors --→ l i,n,d , --→ r i,n,d are in a set of castle polygons associated to a tree of relations G n,d , with bijections s n,d , p n,d , m n,d . The claimed result comes from the fact that the castle polygons in Gn,d are obtained from those in Gn by first replacing each -→ l j by ---→ l σ -1 n (j) , and each -→ r j by ---→ r τ -1 n (j) , then rotating each polygon by π 2 to the right and making a left to right symmetry; thus the polygon τ -1 n j in Gn,d has lower sides -------→ l σ -1 n pn(j),n,d , -----→ r τ -1 n (j),n,d , upper sides -------→ r τ -1 n mn(j),n,d , -----→ l σ -1 n (j),n,d . This translates into the conclusion of the proposition plus the three equalities

σ n = p n • τ n , m n • τ n = τ n • m n,d , p -1 n • σ n = σ n • p n,d
, and we take all this as our induction hypothesis.

For n = 0 it is satisfied with τ 0 = Id, σ 0 = p 0 . We suppose it is satisfied up to stage n. Then we take F n,d = τ -1 n F n ; if F n,+ , resp. F n,-is the subset of F n made with vertices of positive, resp. negative, accepted induction branches, we notice that, as τ -1

n = σ -1 n • p n and F n,+ is stable by p n , F n,d is also τ -1 n F n,-∪ σ -1 n F n,+ . Then we put τ n+1 = τ -1 n • m n • τ n , σ n+1 = σ n on F n,-, σ n+1 = σ -1 n • p -1 n • σ n , τ n+1 = τ n on F n,+ , τ n+1 = τ n , σ n+1 = σ n on F c n .
The induction hypothesis is satisfied at stage n + 1, as a straightforward application of the formulas giving the new parameters and train-track equalities. Note that the above permutations are not unique; we could start with σ 0 = Id, τ 0 = m 0 , and make similar constructions where the polygons are rotated to the left, with different equalities.

Outside the hyperelliptic class the induction does not seem to deserve being called self-dual: Proposition 3.2. Theorem 3.1 is not valid for the non-hyperelliptic (or rotations) Rauzy class on four intervals.

Proof

Let G be a set of castle polygons satisfying the parenthesized train-track equalities

-→ l 1 + -→ r 1 = -→ r 3 + ( -→ r 2 + -→ l 3 ), -→ l 2 + -→ r 2 = -→ l 1 , -→ l 3 + -→ r 3 = -→ r 1 + -→ l 2
. This is an initial set of castle polygons for the permutation 1 → 2, 2 → 3, 3 → 4, 4 → 1. but it is also shown in Section 2.8 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF] that these equalities define a recurrent state for every permutation in this Rauzy class.

To begin proving an analogous of Theorem 3.1, we need to find two permutations σ and τ and a dual state G d such that the train-track equalities of G d projected on the L i and R i are the same as the train-track equalities of G projected on the l i and the r i after applying σ to the l i and τ to the r i ; equalities on L i and R i must be of the form L i + X = R i + Y and, after trying all thirty-six pairs of permutations, we get six possible states, which are the same up to the permutations of {1, 2, 3}. We take for example G d to be the state where the train-track equalities of G d projected on the L i and the

R i are L 2 + R 1 = (R 3 + R 2 ) + L 1 , L 3 + R 2 = L 2 , L 1 + R 3 = R 1 + L 3 ,
then σ is a circular permutation and τ is the identity; thus G d is defined by the train-track equalities

-→ l 1 + -→ r 1 = -→ r 3 + ( -→ r 2 + -→ l 2 ), -→ l 2 + -→ r 2 = -→ l 3 , -→ l 3 + -→ r 3 = -→ r 1 + -→ l 1
. Now, if we want to go forward from G, only the polygons 1 and 3 can be cut, the positions of the diagonals are given by the signs of l 1r 3 and l 3r 1 , and the train-track equalities for G imply that l 1r 3 = l 2 + r 2l 3 > l 2r 3 = l 3r 1 , thus three pairs of signs are possible, (-, -), (+, +), and (+, -); with the decision F = {1, 3}, the three different pairs of forward diagonal changes from G are indeed possible, and lead to three different formal sets of castle polygons. However, if we go backwards from G d , the relation L 1 + R 3 = R 1 + L 3 and the rules of the backward diagonal changes imply that with the decision F d = {1, 3} only two possible pairs of backward changes (decreasing both L 1 and L 3 or both R 1 and R 3 ) are possible; the other possible backward decisions being F d = {1} and F d = {3}, there is no way to get the self-duality at the next stage. Note that the above proof points out another (see also the remark after Lemma 1.4) interesting dissymetry between forward and backward diagonal changes.

3.

3. An invertible algorithm. We tackle now the problem of inverting an algorithm of induction, starting from where we have left it in Section 2.3. For example, let us take the greedy-hyperelliptic algorithm as described in [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] (and named in [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF]), where at each stage the decision is made with the vertices of all accepted induction branches; for a three-interval exchange and the initial set of castle polygons associated to the tree of relations 1 -2, when m 1 r 1 < l 1 < (m 1 + 1)r 1 and m 2 r 2 < l 2 < (m 2 + 1)r 2 , with m 1 < m 2 , this implies taking m 1 times the decision F = {1, 2} then m 2m 1 times the decision F = {2}. If we want to inverse this sequence of changes, we have to begin with F = {2}, thus wait until pasting on 1, though 1 is a backward accepted induction branch. How long we have to wait until pasting on vertices of a blocked backward accepted induction branch is not always from the parameters in the arrival set of castle polygons: it depends on the forward algorithm we want to invert, and we are not able to determine it in the general case.

In the case of three-interval exchanges the greedy-hyperelliptic algorithm is invertible; this is proved in [START_REF] Ferenczi | A self-dual induction for three-interval exchange transformations[END_REF], with a different but equivalent natural extension, because the set of castle polygons associated to 1 =2 acts as a regulator. Namely, every sequence of consecutive sets of castle polygons associated to 1 -2 comes after one set associated to 1 =2, and in the first set associated to 1 -2 we have R 1 > L 1 and R 2 > L 2 ; then after m decisions made with the vertex 1 and n decisions made with the vertex 2 we have mR 1 < L 1 < (m + 1)R 1 , nR 2 < L 2 < (n + 1)R 2 ; thus at each stage we can retrieve the number of decisions made with the vertex 1, resp. 2, which have just been taken, and, knowing we have followed the greedy-hyperelliptic algorithm, invert the process; the same reasoning, mutatis mutandis, is valid for sets of castle polygons associated with 1 +2, and in the remaining case with 1 =2 there is only one possible decision, thus no problem of invertibility.

For more than three intervals, we do not know whether the greedy-hyperelliptic algorithm is invertible.

In this section, we propose an invertible algorithm which uses only one accepted induction branch at a time; the choice of this branch uses the tree structure of the trees of relations, which will be rooted and oriented for this purpose (though they are still not to be confused with the castle trees).

Namely, in any tree of relations we particularize the vertex 1 to be the root, and the edges are oriented away from the root; thus the tree of relations in Figure 16 can be seen as oriented from left to right (to stress the difference with the castle trees which are oriented upwards).

Let G be a set of castle polygons associated to the tree of relations G, oriented as above. The orientation defines a partial order on the vertices; we extend it now to a total order between disjoint induction branches of G depending on the horizontal coordinates l i and r i of the sides of the polygons in G; namely, if B and B ′ are two disjoint induction branches of G, B is before B ′ in any of the following cases:

• B has a common vertex with the path from the root to B ′ , • a is the last common vertex in the oriented paths from the root to B and B ′ , and the first edge in the path from a to B is labelled =, • a is the last common vertex in the oriented paths from the root to B and B ′ , the first edge in the path from a to B is labelled +, the first edge in the path from a to B ′ is labelled -, and l a > r s(a) , • a is the last common vertex in the oriented paths from the root to B and B ′ , the first edge in the path from a to B is labelled -, the first edge in the path from a to B ′ is labelled +, and r a > l s(a) .

Theorem 3.3. A set G of castle polygons is canonical if it is associated to a tree of relations G and no accepted induction branch is before any backward accepted induction branch; we define the canonical decision F to be the union of the vertices of the first accepted induction branch, the canonical backward decision F -to be the union of the vertices of the last backward accepted induction branch. Any forward diagonal change from G with canonical decision leads to another canonical set of castle polygons, from which a backward change with canonical backward decision is the inverse of the previous forward change.

Any backward diagonal change from G with canonical backward decision leads to another canonical set of castle polygons, from which a forward change with canonical decision is the inverse of the previous backward change.

Proof

We take a forward change from G, where the decision F is made with the vertices of an accepted induction branch B. In the new tree G ′ , this creates a backward accepted induction branch with the same vertices as B, deletes B as an accepted induction branch, and possibly creates new accepted induction branches using vertices of B; this also changes the order between disjoint induction branches, but only beyond B for the partial order of the orientation.

G′ could be non canonical only if a new accepted induction branch is before an existing backward accepted induction branch. The only non-trivial possibility is when B is on one of the two far sides of a node (or the root) and, after the change, some vertices of B become part of a new accepted induction branch B ′ touching the node (or root): for example, starting from Figure 14, the induction branch 2 could be accepted and, after the change, create a new accepted induction branch B ′ , the branch 1 -2; then we have to check that B ′ is not before a backward accepted union branch on the other far side of the node (or root), such as 4 in Figure 14; but this is just what is avoided by the last three items in the definition of the order, which ensure that, before the change, B was before any branch on the other far side, and thus there can be no backward accepted induction branch on that side.

Similarly, after a backward change from G, the new G′′ could be non canonical only if a new backward accepted branch, created in the new tree G ′′ by the change, is after an existing accepted induction branch. This is not possible as an extending of a branch as above can only move it towards the root.

All the sets being canonical, it is immediate that the changes with canonical decisions are inverse to each other.

We check that in the initial state defined by G 0 = 1 -(k -1) +2 -(k -2) +..., for any possible parameters l i , r i given by an interval exchange, we can choose the L i and R i such that the initial set of castle polygons G0 is canonical. Indeed, the worst case is when l 1 > r 1 , as then 1 is a positive accepted induction branch; then the induction branches (k -1) +2, 2 -(k -2), and so on as far as the negative branch p if k = 2p, or the positive branch p + 1 if k = 2p + 1, cannot be backward accepted. This is ensured, if k = 2p, by taking L p > R p , R p+1 > L p+1 , L p-1 > R p-1 , and so on until L 2 > R 2 and R k-1 > L k-1 , and similarly starting from R p+1 > L p+1 if k = 2p + 1.

Thus, for a symmetric i.d.o.c. interval exchange with alternate discontinuities, the algorithm of self-dual induction using the canonical decisions is invertible.

3.4. Invariant measure. We can now define the maps ψ and Ψ of Section 2.3 for the algorithm described above: Ψ is defined on a subset of IR 2k-2 , and ψ as its projection on IR k-1 (after normalization). Namely, let G be the set of all trees of relations with vertices 1, 2,... k -1 such that pms(i) = i + 1 for 1 ≤ i ≤ k -2, pms(k -1) = 1; it is shown in Corollary 6.3 of [START_REF] Cassaigne | Combinatorial trees arising in the study of interval exchange transformations[END_REF] (allowing for slightly different definitions of s, m, p) that these are exactly the trees of relations which can be reached from the initial 1 -(k -1) +2 -(k -2) +... by a finite sequence of inductions using decisions made with the vertices of accepted induction branches.

For any G ∈ G, we define D G as the set of (l i , r i , L i , R i ) in IR 4k-4 which satisfy

• the 2k -4 nontrivial relations defined by G, namely l i = l ps(i) , r i = r ms(i) . l i + r i = l s(i) + r s(i) L i = L ps(i) , R i = R ms(i) . L i + R s(i) = L s(i) + R i for all i; • S = 1, where S is the total area of the castle polygons associated to G, namely, because of the relations and the symmetries they imply, S = k-1 i=1 (l i R i + r i L i ); • the signs of l ir s(i) and L i -R i , 1 ≤ i ≤ k -1, are all the possible 2k -2-uples compatible with the invariance by s, and such that in G no accepted induction branch is before any backward accepted induction branch for the order defined in Section 3.3.

Then we define Ψ(l i , r i , L i , R i , 1 ≤ i ≤ k -1) = (l ′ i , r ′ i , L ′ i , R ′ i , 1 ≤ i ≤ k -1), the new parameters after the forward diagonal change with canonical decision, leading from G to G′ for some G ′ ∈ G. Then, by Theorem 3.3, after deleting a finite union of rational hyperplanes, Ψ is a bijection from D G to D G ′ , which projects on the self-dual induction ψ(l i , r i , 1 ≤ i ≤ k -1). As we want to iterate Ψ or ψ, it will be convenient to delete a countable invariant union of rational hyperplanes, which will be always understated.

We can then write Ψ on independent variables on each D G , by using first the relations to drop k -2 pairs of variables (l i , L i ) or (r i , R i ); the remaining variables are denoted by x i and X i , 1 ≤ i ≤ k; then we drop x k and X k , and add x 0 = k-1 j=1 (l j + r j ), and X 0 = S. We still call D G the resulting domain and Ψ the resulting map from D G to D G ′ . Theorem 3.4. Let y 0 = log x 0 , y

i = x i X 1 , 1 ≤ i ≤ k -1, Y 0 = X 0 , Y i = x 0 X i , 1 ≤ i ≤ k -1.
Let J(x i , X i , 1 ≤ i ≤ k -1) be the Jacobian such that k-1 j=1 (dy j dY j ) = J k-1 j=1 (dx j dX j ); let J ′ (x i , X i , 1 ≤ i ≤ k -1) be the Jacobian such that k-1 j=0 (dy j dY j ) = J ′ k-1 j=0 (dx j dX j ) taken for x 0 = X 0 = 1. Then the self-dual induction map ψ, on the coordinates x i , normalized by k-1 j=1 (l j + r j ) = 1, admits an invariant measure whose density with respect to the Lebesgue measure on D G is D G (x 1 ,...,x k-1 ) J J ′ dX 1 ...dX k-1 , where D G (x 1 , ...x k-1 ) = {(X 1 , ..., X k-1 ); (x 0 = 1, X 0 = 1, x 1 , X 1 , ..., x k-1 , X k-1 ) ∈ D G }.

As it is shown in [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF] that any i.d.o.c. interval exchange in the hyperelliptic class is obtained from a symmetric i.d.o.c. interval exchange by a finite number of Rauzy inductions (this is nontrivial and has no known equivalent in other Rauzy classes), this yields the result. By Proposition 6.2 of [START_REF] Cassaigne | Combinatorial trees arising in the study of interval exchange transformations[END_REF], for k intervals trees of relations form (k -1)! disjoint sets of possible states, characterized by a circular order determined by the map pms of Section 3.4, thus we have only one possible set of states up to a renumbering of the intervals. If we want to know the set itself with the numbering defined in Definition 2.1: under the condition of alternate discontinuities, we get the set containing the initial state 1 -(k -1) +2 -(k -2) + . . ., coresponding to the circular order (1, 2, 3, . . . , k -1, 1); under the opposite condition, we get the set containing the initial state (k -1) -1 +(k -2) -2 + . . ., coresponding to the circular order (1, k -1, k -2, . . . , 2, 1). A closer look at Section 3.1 of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] (where a different numbering system is used) would prove that only these two possibilities exist.

1 .

 1 INTERVAL EXCHANGES WITH ALTERNATE DISCONTINUITIES 1.1. Definitions. For any question about interval exchanges, we refer the reader to the surveys [32] [33] [9]. Our intervals are always semi-open, as [a, b[. Definition 1.1. A k-interval exchange I with probability vector (α 1 , α 2 , . . . , α k ), and permutation π is defined by

  FIGURE 16

  Other cases, including the case of opposite alternate discontinuities, are studied in Section 2.2 below. Definition 1.11. An initial set of castle polygons defined by an i.d.o.c interval exchange I with permutation π and alternate discontinuities is such that • the β i of Definition 1.7 are identified with those of Definition 1.1;

Proof

We just use the recipe given in [START_REF] Arnoux | Mesures de Gauss pour des algorithmes de fractions continues multidimensionnelles, (French) [Gauss measures for multidimensional continued fraction algorithms[END_REF]. Ψ commutes with the flow ρ t (x i , X i ) = (x i e -t , X i e t ), and in the (y i , Y i ) coordinates this flow is just a translation on the first coordinate, and preserves the Lebesgue measure; the first return map of ρ t on the surface s = 1 preserves the Lebesgue measure k-1 j=1 (dy j dY j ), and after integrating on each fibre we get an invariant measure for the normalized projection of Ψ.

RAUZY CLASSES

The Rauzy classes partition the states of the Rauzy induction; thus one can wonder if the formal states of our induction, namely the description of the castle polygons, or castle trees, or parenthesized train-track equalities, without the actual values of the parameters, are partitioned in an equivalent way. Here the geometric theory comes into its own, as it gives an immediate answer in one direction.

Proof

Then two induced maps from the respective interval exchanges appear as sections of the linear flows on two surfaces in the same stratum, and this yields the result.

In the other direction, it is not so clear that, through our inductions, we can get from any surface to any other one in the same connected component of any stratum; we can show only partial results, using the combinatorics of the induction, with the additional inconvenience that the states we can reach depend on the decisions. In Section 2.8 of [START_REF] Ferenczi | A generalization of the self-dual induction to every interval exchange transformation[END_REF], we compute all the possible formal states for four intervals, with a particular algorithm for choosing a decision, and show that, for this algorithm, two interval exchanges with alternate discontinuities give the same possible formal states, up to a renumbering of the intervals 1 to k (see the discussion at the end of this section), if they are in the same Rauzy class, except for some transient states in the early stages. Here we give two results in the direction of a more general statement.

Note that Lemma 4.2 concerns actual, not only formal, states; it is a result on the induction, though it is stated and proved more easily in the language of diagonal changes, and it is valid also if γ 1 < β 1 and we induce on (Rauzy) induced map on [0, γ k-1 [. Then, for any infinite sequence S of forward diagonal changes, starting from the initial set of castle polygons for I and with decisions F n , there exists a finite sequence of forward diagonal changes, starting from the initial set of castle polygons for I ′ and with decisions F ′ n , leading to the same set of castle polygons as an initial subsequence of S.

Proof

The effect of the Rauzy induction is to cut the interval

subintervals, provisionally numbered j 1 and j 2 , by the point γ ′ = I -1 γ k-1 ; then the intervals (1, ..j 1 , j 2 , ...k-1) are re-ordered by I ′ in the order π(1), ...π(k) modified by replacing k by j 2 and π(k) = j by j 1 ; then the intervals are renumbered 1 to k.

In the initial set of castle polygons of I the side corresponding to [γ k-1 , 1[ has already been pasted somewhere.

Suppose first that the interval [γ j-1 , γ j [ is one of the initial E i ; then it contains some β s , in which case it is numbered E i 1 , and γ ′ is the horizontal projection of a vertex C 1 of the polygon i 1 (for I). Then, if we make what amounts to a partial forward diagonal change, namely cutting the polygon i 1 by the diagonal β i 1 C 1 and pasting one part according to the usual rules, we get a new set of castle polygons for I which is exactly the initial set of castle polygons for I ′ , except that the pasted part may create a vertex C 2 , projecting on some I -m γ ′ , while the adjacent vertices are other I -m γ t ; as γ ′ is a discontinuity of I ′ , while for I it is the pre-image of a discontinuity, this implies that C 2 is above a pasting diagonal for I, while this pasting diagonal does not exist for I ′ . The change we have made may replace the polygon i 1 in the initial set of I by two polygons, numbered i 1 and i 2 , both in the new set for I and in the initial set of I ′ ; all the other polygons and their sides are numbered in the same way in the two initial states, as the discontinuities β i are the same, even if the intervals are numbered differently.

If [γ j-1 , γ j [ is not one of the initial E i , then some I -m γ ′ is the horizontal projection of a vertex C 2 of some polygon i 3 in the initial set of I. Then the two initial sets are the same, except that again a pasting diagonal below C 2 may be present for I and not for I ′ . Now, given decisions F n for I, we take F n = F ′ n except possibly for two modifications: first, if i 1 exists and F n 1 is the first decision containing i 1 (it exists by minimality), we build F ′ n 1 from F n 1 by adding i 2 if it exists and the polygon i 2 is not a triangle, and deleting i 1 if the polygon i 1 in the initial state of I ′ is a triangle. In this way, after n 1 decisions at most, we have the same castle polygons for I and I ′ except possibly for a pasting diagonal which may be present in the former and absent in the latter; in that case, one polygon for I will be cut more slowly (by one step) than the same polygon for I ′ , and this is compensated by deleting its number from some F n 2 to get F ′ n 2 , at some stage after the pasting diagonal is cut and each polygon contains only one β i (again, this will happen by minimality); thus we get the claimed result.

In general the induction in Lemma 4.2 does not preserve the condition of alternate discontinuities. Thus the problem is to know whether two different formal initial states for interval exchanges with the same permutation lead ultimately to the same formal states; this seems to be true experimentally, but difficult to prove in the general case; however, it is proved in the important particular case of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF], using the relatively heavy machinery of composite trees of relations. Theorem 4.3. Let I be an interval exchange in the hyperelliptic Rauzy class, satisfying the i.d.o.c. condition; then there exists an algorithm of self-dual induction such that all the possible sets of castle polygons are associated with trees of relations, except for some transient states in the early stages.

Proof

This algorithm is described in Section 3.1 of [START_REF] Ferenczi | Structure of K-interval exchange transformations: induction, trajectories, and distance theorems[END_REF] where it is proved that, if we make self-dual inductions from any initial state of a symmetric i.d.o.c. interval exchange, we can make decisions which lead us, after a finite number of initial stages, to states associated with trees of relations. Now, starting from the initial state of an interval exchange which is the Rauzy induced map on [0, γ k-1 [ of a symmetric i.d.o.c. interval exchange, by Lemma 4.2 we can go to states associated with trees of relations. The same result is true for the Rauzy induced map on [0, β k-1 [ of a symmetric i.d.o.c. interval exchange by using the inverse maps I -1 and (I ′ ) -1 , as, when an induced map is described by a state corresponding to a tree of relations, its inverse is also.