Interval exchanges
system:sage


<div class="section" id="demonstration-interval-exchange-transformations">
<span id="demo-interval-exchanges"></span><h1>Demonstration: Interval exchange transformations<a class="headerlink" href="#demonstration-interval-exchange-transformations" title="Permalink to this headline"></a></h1>
<div class="section" id="cut-and-rearrange-the-interval">
<h2>Cut and rearrange the interval<a class="headerlink" href="#cut-and-rearrange-the-interval" title="Permalink to this headline"></a></h2>
<p>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$:</p>
<div align="center" class="align-center"><img alt="data/3iet_definition_example.png" class="align-center" src="data/3iet_definition_example.png"></div>
<div class="highlight-python">

{{{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
}}}

</div>
<p>We are interested in the iteration of such a map $T$, i.e. $x_{n+1} = T(x_n)$:</p>
<div align="center" class="align-center"><img alt="data/3iet_iterations.gif" class="align-center" src="data/3iet_iterations.gif"></div>
<p>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.</p>
<p>Formally,</p>
<p><strong>Definition</strong> Let $\pi \in S_d$  and $\lambda \in \RR^d$. We define</p> $$x_i = \sum_{j \leq i} \lambda_j \qquad \text{and} \qquad y_i = \sum_{j \leq i} \lambda_{\pi^{-1}(j)}$$</p>
</div><p>The <em>interval exchange transformation</em>  with data $(\lambda,\pi)$ is the map from $I = [0;|\lambda|)$ to itself defined by</p>
$$T(x) = x - x_i + y_i \qquad \text{if} x \in [x_i; x_{i+1})$$</p>
</div><p>where $|\lambda| = \lambda_1 + \ldots + \lambda_d$.</p>
<p>There are two useful ways to plot an interval exchange transformation.
Either, a plot showing the domain above the range, the map is specified by
colors.</p>
<div class="highlight-python">

{{{id=1|
T.plot_two_intervals()
///
}}}

</div>
<p>Or the graph of the interval exchange transformation:</p>
<div class="highlight-python">

{{{id=2|
T.plot_function(aspect_ratio=1)
///
}}}

</div>
</div>
<div class="section" id="orbit-and-symbolic-coding">
<h2>Orbit and symbolic coding<a class="headerlink" href="#orbit-and-symbolic-coding" title="Permalink to this headline"></a></h2>
<p>To each point $x \in I$ we associate the label of the subinterval it belongs to.</p>
<div class="highlight-python">

{{{id=3|
T.in_which_interval(0.2)
///
'a'
}}}

{{{id=4|
T.in_which_interval(2)
///
'b'
}}}

</div>
<p>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:</p>
<div class="highlight-python">

{{{id=5|
x = 2
w = []
for i in xrange(17):
       w.append(T.in_which_interval(x))
       x = T(x)
print &#39;&#39;.join(w)
///
bbbcacacacbbbbcac
}}}

</div>
<p>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.</p>
<p>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)$.</p>
<p>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</p>
$$I_w = I_{w_0} \cap T^{-1}(I_{w_1}) \cap \ldots \cap T^{-n}(I_{w_n})$$
</div><p>The partition determined by the subintervals $I_w$ for $w$ of fixed length
corresponds to the map $T^n$.</p>
<div class="highlight-python">

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

</div>
<div class="highlight-python">

{{{id=7|
T*T
///
Interval exchange transformation of [0, 4/7*pi + sqrt(2) + 7/5[ with
permutation
ac bb bc ca cb
bc ac cb bb ca
}}}

</div>
<div class="highlight-python">

{{{id=8|
T*T*T
///
Interval exchange transformation of [0, 4/7*pi + sqrt(2) + 7/5[ with permutation
aca acb bbb bbc bca cac cbb
bbc cac acb cbb bbb bca aca
}}}

</div>
<p><strong>Proposition:</strong> If $T$ is an interval exchange transformation with $d$
subintervals then the number of subintervals in the partition of the domain of
$T^n$ is smaller than$(d-1)n + 1$.</p>
<p>This proposition proves that the entropy of any interval exchange transformation
is zero as $\lim_{n \to \infty} \frac{\log((d-1)n+1)}{n} = 0$.</p>
<p>This proposition proves that the entropy of any interval exchange transformation
is zero.</p>
<p>Each time you consider one more iteration, the preceding partition is refined
with respect to the preimages of the $x_i$.</p>
<p><strong>Definition:</strong> A <em>connection</em> of an interval exchange transformation, is a
triple $(y,x,n) I \times I \times \{1,2,\ldots\}$ such that $y$ is a singularity
of $T^{-1}$ (one of the $y_i$ in the definition), $x$ is a singularity of $T$
(one of the $x_i$ in the definition) and such that $T^n(y) = x$). The number $n$
is called the length of the connection.</p>
<img alt="data/3iet_connection.png" src="data/3iet_connection.png">
<p><strong>Proposition:</strong> If the interval exchange transformation $T$ on $d$ intervals
has no connection then the number of words of length $n$ which appear as a
coding sequence of an orbit is exactly $(d-1)n+1$.</p>
<p>A connection gives a rational relation on the set of lengths $\lambda_1$,
$\lambda_2, \ldots, \lambda_d$. For example, if the lengths are integers, then
the interval exchange has $d$ saddle connections.</p>
<p><strong>Exercise</strong> Given a list of three positive integers $\lambda =
(\lambda_a,\lambda_b,\lambda_c)$, find the lengths of connections of the
interval exchange transformation with permutation</p>
$$\pi = \left( \begin{array}{lll}a & b & c \\c & b & a\end{array} \right)$$
>/div>
<div class="section" id="rauzy-induction">
<h2>Rauzy induction<a class="headerlink" href="#rauzy-induction" title="Permalink to this headline"></a></h2>
<p>Rauzy introduced in <a class="reference internal" href="#rau79">[Rau79]</a> introduced a renormalization algorithm for
interval exchange transformations. This renormalization generalizes continous
fraction algorithm for rotations.</p>
<p>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)}$ (<em>top induction</em>) or
$\lambda_{\pi_b^{-1}(d)}$ (<em>bottom induction</em>) there are two possibilities for
$\pi'$.</p>
<p>We treat the case of the permutation</p>
$$\left(\begin{array}{ccc}a&b&c\\c&b&a\end{array}\right)$$
<p>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).</p>
<a class="reference internal image-reference" href="../_images/top_rauzy_induction.png"><img alt="data/top_rauzy_induction.png" src="data/top_rauzy_induction.png" style="width: 387.2px; height: 252.8px;"></a>
<a class="reference internal image-reference" href="data/bottom_rauzy_induction.png"><img alt="data/bottom_rauzy_induction.png" src="data/bottom_rauzy_induction.png" style="width: 387.2px; height: 252.8px;"></a>
<p>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</p>
<div class="highlight-python">

{{{id=9|
TT=T
alphabet = T.permutation().alphabet()
for i in xrange(8):
       TT = TT.rauzy_move()
       perm = TT.permutation()
       lengths = TT.lengths()
       pp = TT.permutation()
       print pp
       print lambda_a = %s&quot; %(lengths[alphabet.rank('a')])
       print lambda_b = %s&quot; %(lengths[alphabet.rank('b')])
       print lambda_c = %s&quot; %(lengths[alphabet.rank('c')])
       print "\n--------------------"
///
a b c
c a b
  lambda_a = 7/5
  lambda_b = sqrt(2)
  lambda_c = 4/7*pi - 7/5
--------------------
a b c
c a b
  lambda_a = 7/5
  lambda_b = -4/7*pi + sqrt(2) + 7/5
  lambda_c = 4/7*pi - 7/5
--------------------
a b c
c a b
  lambda_a = 7/5
  lambda_b = -8/7*pi + sqrt(2) + 14/5
  lambda_c = 4/7*pi - 7/5
--------------------
a b c
c a b
  lambda_a = 7/5
  lambda_b = -12/7*pi + sqrt(2) + 21/5
  lambda_c = 4/7*pi - 7/5
--------------------
a b c
c b a
  lambda_a = 7/5
  lambda_b = -12/7*pi + sqrt(2) + 21/5
  lambda_c = 16/7*pi - sqrt(2) - 28/5
--------------------
a c b
c b a
  lambda_a = -16/7*pi + sqrt(2) + 7
  lambda_b = -12/7*pi + sqrt(2) + 21/5
  lambda_c = 16/7*pi - sqrt(2) - 28/5
--------------------
a b c
c b a
  lambda_a = -4/7*pi + 14/5
  lambda_b = -12/7*pi + sqrt(2) + 21/5
  lambda_c = 16/7*pi - sqrt(2) - 28/5
--------------------
a c b
c b a
  lambda_a = -20/7*pi + sqrt(2) + 42/5
  lambda_b = -12/7*pi + sqrt(2) + 21/5
  lambda_c = 16/7*pi - sqrt(2) - 28/5
--------------------
}}}

</div>
<p>We can get successive plot of the interval exchange transformations on the same
picture</p>
<div align="center" class="align-center"><img alt="data/rauzy_inductions.gif" class="align-center" src="data/rauzy_inductions.gif"></div>
</div>
<div class="section" id="rauzy-classes-of-permutations">
<h2>Rauzy classes of permutations<a class="headerlink" href="#rauzy-classes-of-permutations" title="Permalink to this headline"></a></h2>
<p>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$
(<em>top move</em>) and $R_b$ (<em>bottom move</em>).</p>
<div class="highlight-python">

{{{id=10|
p = T.permutation()
p
///
a b c
c b a
}}}

{{{id=11|
p.rauzy_move('top')
///
a b c
c a b
}}}

{{{id=12|
p.rauzy_move('bottom')
///
a c b
c b a
}}}

</div>
<p>The set of permutations obtained by top and bottom inductions is called the
<em>Rauzy class</em> 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 <em>Rauzy diagram</em>.</p>
<div class="highlight-python">

{{{id=13|
p.rauzy_diagram()
///
Rauzy diagram with 3 permutations
}}}

</div>
<p><strong>Definition:</strong> 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\}$.</p>
<p>The number of irreducible permutations is easily computed from factorial as
follows:</p>
<div class="highlight-python">

{{{id=14|
@cached_function
 def number_of_irreducible_permutations(n):
     return factorial(n) - sum(factorial(k)*number_of_irreducible_permutations(n-k) for k in xrange(1,n))
///
}}}

</div>
<div class="highlight-python">

{{{id=15|
[number_of_irreducible_permutations(i) for i in xrange(1,10)]
///
[1, 1, 3, 13, 71, 461, 3447, 29093, 273343]
}}}

</div>
<p>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</p>
<div class="highlight-python">

{{{id=16|
number_of_irreducible_permutations(2)
///
1
}}}

{{{id=17|
p2a = iet.Permutation('a b','b a',reduced=True)
p2a.rauzy_diagram()
///
Rauzy diagram with 1 permutation
}}}

</div>
<div class="highlight-python">

{{{id=18|
number_of_irreducible_permutations(3)
///
3
}}}

{{{id=19|
p3a = iet.Permutation('a b c','c b a',reduced=True)
p3a.rauzy_diagram()
///
Rauzy diagram with 3 permutations
}}}

</div>
<p>On four letters there are two Rauzy diagrams</p>
<div class="highlight-python">

{{{id=20|
number_of_irreducible_permutations(4)
///
13
}}}

{{{id=21|
p4a = iet.Permutation('a b c d','d b c a',reduced=True)
p4a.rauzy_diagram()
///
Rauzy diagram with 6 permutations
}}}

{{{id=22|
p4b = iet.Permutation(&#39;a b c d&#39;,&#39;d c b a&#39;,reduced=True)
p4b.rauzy_diagram()
///
Rauzy diagram with 7 permutations
}}}

</div>
<p>The classification of Rauzy classes follow from a correspondance between Rauzy
classes and connected components of moduli spaces.</p>
<div class="highlight-python">

{{{id=23|
number_of_irreducible_permutations(6)
///
461
}}}

{{{id=24|
N = 0
for a in AbelianStrata(nintervals=6,marked_separatrix=&#39;out&#39;):
       for cc in a.connected_components():
           n = cc.rauzy_diagram().cardinality()
           N += n
           print &quot;%3d perms in %s&quot; %(n ,str(cc))
///
 31 perms in H_hyp^out(4)
134 perms in H_odd^out(4)
 66 perms in H_hyp^out(0, 2, 0)
105 perms in H_hyp^out(2, 0, 0)
 20 perms in H_hyp^out(0, 1, 1)
 90 perms in H_hyp^out(1, 1, 0)
 15 perms in H_hyp^out(0, 0, 0, 0, 0)
}}}

{{{id=25|
print &quot;total perms = %d&quot; %N
///
total perms = 461
}}}

</div>
</div>
<div class="section" id="reference">
<h2>Reference<a class="headerlink" href="#reference" title="Permalink to this headline"></a></h2>
<table class="docutils citation" frame="void" id="rau79" rules="none">
<colgroup><col class="label"><col></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id1">[Rau79]</a></td><td>G. Rauzy, <em>Echanges d&#8217;intervalles et transformations induites</em>, Acta
Arith., p. 315-328 (1979)</td></tr>
</tbody>
</table>
</div>
<div class="section" id="exercises">
<h2>Exercises<a class="headerlink" href="#exercises" title="Permalink to this headline"></a></h2>
</div>
<div class="section" id="sage-commands-used-to-provide-the-animated-outputs">
<h2>Sage commands used to provide the animated outputs<a class="headerlink" href="#sage-commands-used-to-provide-the-animated-outputs" title="Permalink to this headline"></a></h2>
<p>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$.</p>
<p>Here is the function that plots the above animations.</p>
<div class="highlight-python">

{{{id=26|
def animate_iet(T, iterations=8, x0=0):
       colors = rainbow(len(T.permutation()),&#39;rgbtuple&#39;)
       alphabet = T.permutation().alphabet()
       x = x0
       G = T.plot_two_intervals(colors=colors)
       l = []
       for i in xrange(iterations):
           G += point((float(x),0.1))
           G += text(&#39;$x_%d$&#39; %i, (x,0.115),color=&#39;black&#39;,fontsize=11)
           l.append(copy(G))
           xx = x
           aa = T.in_which_interval(xx)
           ii = alphabet.rank(aa)
           x = T(x)
           a = T.in_which_interval(x)
           i = alphabet.rank(a)
           G += line([(float(xx),0.1),(float(x),-0.1)],linestyle=&#39;dashed&#39;,color=colors[ii])
           l.append(copy(G))
           G += line([(float(x),-0.1),(float(x),0.1)],linestyle=&#39;dotted&#39;,color=(0.3,0.3,0.3))
       l.append(copy(G))
       return animate(l)
///
}}}

</div>
<div class="highlight-python">

{{{id=27|
p = iet.Permutation(&#39;a b c&#39;,&#39;c b a&#39;)
///
}}}

</div>
<div class="highlight-python">

{{{id=28|
T = iet.IntervalExchangeTransformation(p,[1,1,1])
animate_iet(T,iterations=2, x0=0.3).show(delay=50)
///
}}}

</div>
<div class="highlight-python">

{{{id=29|
T = iet.IntervalExchangeTransformation(p,[2,1,3])
animate_iet(T,iterations=6,x0=0.3).show(delay=50)
///
}}}

</div>
<p>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.</p>
</div>
</div>

{{{id=52|

///
}}}