Combinatorial structure of symmetric $k$-interval exchange transformations

Sébastien Ferenczi

Institut Mathématique de Luminy, CNRS, Marseille, France

Coauthor(s): Luca Q. Zamboni

We describe a combinatorial and arithmetic algorithm for generating the symbolic sequences which code the orbits of points under an interval exchange transformation on $k$ intervals, using the ``symmetric" permutation $i \mapsto k-i+1$; this algorithm is based on a new induction, described by two classes of graphs. As a consequence we obtain a complete characterization of those sequences of subword complexity $(k-1)n+1$ which are natural codings of orbits of $k$-interval exchange transformations in the Rauzy class of symmetrics, thereby answering an old question of Rauzy. We also give an S-adic presentation of these systems, and improve a bound of Boshernitzan in a generalization of the three-distances theorem for rotations.