Demonstration: Interval exchange transformations

Cut and rearrange the interval

Take an interval, cut it into $n$ pieces of lengths $\lambda_1, \lambda_2,\ldots, \lambda_d$ and rearrange the pieces according to some permutation $\pi$:

{{{id=0| T = iet.IntervalExchangeTransformation((a b c,c b a), [7/5, sqrt(2), 4*pi/7]) T /// Interval exchange transformation of [0, 4/7*pi + sqrt(2) + 7/5[ with permutation a b c c b a }}}

We are interested in the iteration of such a map $T$, i.e. $x_{n+1} = T(x_n)$:

Interval exchange transformations generalize rotations which correspond to the case of $2$ intervals. The dynamics of general interval exchange transformations is richer and still an active research area.

Formally,

Definition Let $\pi \in S_d$ and $\lambda \in \RR^d$. We define

$$x_i = \sum_{j \leq i} \lambda_j \qquad \text{and} \qquad y_i = \sum_{j \leq i} \lambda_{\pi^{-1}(j)}$$

The interval exchange transformation with data $(\lambda,\pi)$ is the map from $I = [0;|\lambda|)$ to itself defined by

Orbit and symbolic coding

To each point $x \in I$ we associate the label of the subinterval it belongs to.

The approach of symbolic dynamics is to associate to the orbit $x_0$, $x_1 = T(x_0)$, ..., $x_n = T(x_{n-1})$, ... of $x$ the sequence of labels corresponding to the visited subintervals. In our example, the sequence associated to the orbit of $x_0 = 2$ is $bbbacabbacabbba\ldots$. It can be computed in Sage as follows:

Note that the sequence associated to $T(x)$ is the shifted of the one associated to $x$. This conjugacy establishes a dictionnary between dynamical properties and combinatorial ones.

The set of points in $x \in I$ such that the symbolic coding of its orbit start with a given word correspond to a subinterval. Setting the first letter, fix the subinterval. Fixing two letters, fix the subinterval of $x$ and the subinterval of its image $T(x)$.

Let $w = w_0 w_1 \ldots w_n$ be a word, then the set of points such that the symbolic coding of the orbit starts with $w$ is the intersection

Rauzy induction

Rauzy introduced in [Rau79] introduced a renormalization algorithm for interval exchange transformations. This renormalization generalizes continous fraction algorithm for rotations.

Let $T = T(\lambda,\pi)$ be an interval exchange transformation with $d$ letters. Let $a = max(\lambda_{\pi_t^{-1}(d)},\lambda_{\pi_b^{-1}(d)})$ be the maximum length between the right subinterval in the domain and the right subinterval in the range. The first return map of $T$ onto $[0,|\lambda|-a)$ is an interval exchange $R(T) = T(\lambda',\pi')$ on the same number of intervals. Depending on the fact that $a$ is $\lambda_{\pi_t^{-1}(d)}$ (top induction) or $\lambda_{\pi_b^{-1}(d)}$ (bottom induction) there are two possibilities for $\pi'$.

We treat the case of the permutation

In the below pictures, you can see two choices of vector-lengths $\lambda$ that lead to a top induction (left picture) and bottom induction (right picture).

The Rauzy induction can be iterated, and we get a sequence of interval exchange transformations on the same number of intervals $T^{(0)} = T(\lambda,\pi)$, $T^{(1)} = T(\lambda^{(1)},\pi^{(1)})$, ..., $T^{(n)} = (\lambda^{(n)},\pi^{(n)}) = R(T^{(n-1)})$, ... For our example we get the following for the first eight Rauzy inductions

We can get successive plot of the interval exchange transformations on the same picture

Rauzy classes of permutations

During a step of Rauzy induction, the operation on permutations can be expressed without any reference to the lengths $\lambda$. We have two operations $R_t$ (top move) and $R_b$ (bottom move).

The set of permutations obtained by top and bottom inductions is called the Rauzy class of $\pi$. The action of top and bottom induction on the the Rauzy classes gives can be seen as edges of a graph which is called a Rauzy diagram.

Definition: A permutation $\pi \in S_d$ is called irreducible if there is no $1 \leq k < d$ such that $\pi(\{1,\ldots,k\}) = \{1,\ldots,k\}$.

The number of irreducible permutations is easily computed from factorial as follows:

From the definition, you can see that the property of being irreducible for a permutation is invariant under Rauzy moves. Hence, the irreducible permutations on $n$ letters split in a certain number of Rauzy classes. On $2$ and $3$ letters there are only one Rauzy classes

On four letters there are two Rauzy diagrams

The classification of Rauzy classes follow from a correspondance between Rauzy classes and connected components of moduli spaces.

Reference

Exercises

Sage commands used to provide the animated outputs

The following gives an animation for seeing the orbit of a point, iterations is the number of points and x0 is the initial point. On the left you see a point of period 2 while on the right a point of period $6$.

Here is the function that plots the above animations.

As you can see, the interval exchanges above are periodic and the period is given by the sum of the lengths: $1+1+1=3$ in the first case and $2+1+3=6$ in the second one.