Interval exchange transformations¶

Interval Exchange Transformations and Linear Involution

An interval exchange transformation is a map defined on an interval (see help(iet.IntervalExchangeTransformation) for a more complete help.

EXAMPLES:

sage: from surface_dynamics import *

Initialization of a simple iet with integer lengths:

sage: T = iet.IntervalExchangeTransformation(Permutation([3,2,1]), [3,1,2])
sage: T
Interval exchange transformation of [0, 6[ with permutation
1 2 3
3 2 1

Rotation corresponds to iet with two intervals:

sage: p = iet.Permutation('a b', 'b a')
sage: T = iet.IntervalExchangeTransformation(p, [1, (sqrt(5)-1)/2])  # random output due to deprecation warnings in some versions of SageMath
sage: T.in_which_interval(0)
'a'
sage: T.in_which_interval(T(0))
'a'
sage: T.in_which_interval(T(T(0)))
'b'
sage: T.in_which_interval(T(T(T(0))))
'a'

There are two plotting methods for iet:

sage: p = iet.Permutation('a b c','c b a')
sage: T = iet.IntervalExchangeTransformation(p, [1, 2, 3])

class surface_dynamics.interval_exchanges.iet.IntervalExchangeTransformation(permutation=None, lengths=None, base_ring=None)[source]¶

Bases: object

Interval exchange transformation

INPUT:

permutation - a permutation (LabelledPermutationIET)
lengths - the list of lengths

EXAMPLES:

sage: from surface_dynamics import *

Direct initialization:

sage: p = iet.IET(('a b c','c b a'),{'a':1,'b':1,'c':1})
sage: p.permutation()
a b c
c b a
sage: p.lengths()
(1, 1, 1)

Initialization from a iet.Permutation:

sage: perm = iet.Permutation('a b c','c b a')
sage: l = vector([0.5,1,1.2])
sage: t = iet.IET(perm,l)
sage: t.permutation() == perm
True
sage: t.lengths() == l
True

Initialization from a Permutation:

sage: p = Permutation([3,2,1])
sage: iet.IET(p, [1,1,1])
Interval exchange transformation of [0, 3[ with permutation
1 2 3
3 2 1

If it is not possible to convert lengths to real values an error is raised:

sage: iet.IntervalExchangeTransformation(('a b','b a'),['e','f'])
Traceback (most recent call last):
...
TypeError: unable to convert x (='e') into a real number

The value for the lengths must be positive:

sage: iet.IET(('a b','b a'),[-1,-1])
Traceback (most recent call last):
...
ValueError: lengths must be non-negative, got -1.0

backward_rauzy_move(winner, side='right')[source]¶

Return a new interval exchange transformation obtained by performing a backward Rauzy move.

EXAMPLES:

sage: from surface_dynamics import iet
sage: perm = iet.Permutation('a b c d e f', 'f c b e d a')
sage: x = polygen(QQ)
sage: poly = x^3 - x^2 - x - 1
sage: root = AA.polynomial_root(poly, RIF(1.8, 1.9))
sage: K.<a> = NumberField(poly, embedding=root)
sage: T = iet.IntervalExchangeTransformation(perm, [a**2, a-1, a + 2, 3, 2*a - 3, 1])
sage: T
Interval exchange transformation of [0, a^2 + 4*a + 2[ with permutation
a b c d e f
f c b e d a
sage: S = T.backward_rauzy_move(0).backward_rauzy_move(1).backward_rauzy_move(1)
sage: S
Interval exchange transformation of [0, a^2 + 7*a + 4[ with permutation
a b c f d e
f b e d a c
sage: S.rauzy_move(iterations=3) == T
True

base_ring()[source]¶

Return the base ring over which the lengths are defined

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b', 'b a')

sage: T = iet.IntervalExchangeTransformation(p, [3, 12])
sage: T.base_ring()
Integer Ring

sage: T = iet.IntervalExchangeTransformation(p, [3, 12/5])
sage: T.base_ring()
Rational Field

sage: T = iet.IntervalExchangeTransformation(p, [3, AA(12).sqrt()])
sage: T.base_ring()
Algebraic Real Field

sage: sqrt2 = QuadraticField(2).gen()
sage: T = iet.IntervalExchangeTransformation(p, [1, sqrt2])
sage: T.base_ring()
Number Field in a ...

domain_singularities()[source]¶

Returns the list of singularities of T

OUTPUT:

list – positive reals that corresponds to singularities in the top: interval

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IET(("a b","b a"), [1, sqrt(2)])
sage: t.domain_singularities()
[0, 1, sqrt(2) + 1]

erase_marked_points()[source]¶

Remove the marked points.

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation([0,1,2,3,4], [4,2,3,0,1])
sage: T1 = iet.IntervalExchangeTransformation(p, [13,2,4,5,7])
sage: T1.erase_marked_points()
Interval exchange transformation of [0, 40[ with permutation
0 4
4 0

in_which_interval(x, interval=0)[source]¶

Returns the letter for which x is in this interval.

INPUT:

x - a positive number
interval - (default: ‘top’) ‘top’ or ‘bottom’

OUTPUT:

label – a label corresponding to an interval

inverse()[source]¶

Returns the inverse iet.

OUTPUT:

iet – the inverse interval exchange transformation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation("a b","b a")
sage: s = iet.IET(p, [1,sqrt(2)-1])
sage: t = s.inverse()
sage: t.permutation()
b a
a b
sage: t.lengths()
(1, sqrt(2) - 1)
sage: t*s
Interval exchange transformation of [0, sqrt(2)[ with permutation
aa bb
aa bb

We can verify with the method .is_identity():

sage: p = iet.Permutation("a b c d","d a c b")
sage: s = iet.IET(p, [1, sqrt(2), sqrt(3), sqrt(5)])
sage: (s * s.inverse()).is_identity()
True
sage: (s.inverse() * s).is_identity()
True

is_identity()[source]¶

Returns True if self is the identity.

OUTPUT:

boolean – the answer

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation("a b","b a")
sage: q = iet.Permutation("c d","d c")
sage: s = iet.IET(p, [1,5])
sage: t = iet.IET(q, [5,1])
sage: (s*t).is_identity()
True
sage: (t*s).is_identity()
True

length(label=None)[source]¶

Return the length of a subinterval, or if label is None the total length.

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b','b a'), [1,3])
sage: t.length()
4
sage: t.length('a')
1
sage: t.length('b')
3

lengths()[source]¶

Return the list of lengths associated to this iet.

OUTPUT:

vector – the list of lengths of subinterval (the order of the entries: correspond to the alphabet)

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.IntervalExchangeTransformation(('a b','b a'),[1,3])
sage: p.lengths()
(1, 3)

normalize(total=1, inplace=False)[source]¶

Returns a interval exchange transformation of normalized lengths.

The normalization consist in consider a constant homothetic value for each lengths in such way that the sum is given (default is 1).

INPUT:

total - (default: 1) The total length of the interval

OUTPUT:

iet – the normalized iet

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b','b a'), [1,3])
sage: t.length()
4
sage: s = t.normalize(2)
sage: s.length()
2
sage: s.lengths()
(1/2, 3/2)

permutation()[source]¶

Returns the permutation associated to this iet.

OUTPUT:

permutation – the permutation associated to this iet

EXAMPLES:

sage: from surface_dynamics import *

sage: perm = iet.Permutation('a b c','c b a')
sage: p = iet.IntervalExchangeTransformation(perm,(1,2,1))
sage: p.permutation() == perm
True

plot(position=(0, 0), vertical_alignment='center', horizontal_alignment='left', interval_height=0.1, labels_height=0.05, fontsize=14, labels=True, colors=None)¶

Returns a picture of the interval exchange transformation.

INPUT:

position - a 2-uple of the position
horizontal_alignment - left (default), center or right
labels - boolean (default: True)
fontsize - the size of the label

OUTPUT:

2d plot – a plot of the two intervals (domain and range)

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b','b a'),[1,1])
sage: t.plot_two_intervals() # random output due to matplotlib deprecation warnings with SageMath <9.1
Graphics object consisting of 8 graphics primitives

plot_function(**d)[source]¶

Return a plot of the interval exchange transformation as a function.

INPUT:

Any option that is accepted by line2d

OUTPUT:

2d plot – a plot of the iet as a function

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b c d','d a c b'),[1,1,1,1])
sage: t.plot_function(rgbcolor=(0,1,0))    # not tested (problem with matplotlib font cache)
Graphics object consisting of 4 graphics primitives

plot_towers(iterations, position=(0, 0), colors=None)[source]¶

Plot the towers of this interval exchange obtained from Rauzy induction.

INPUT:

nb_iterations – the number of steps of Rauzy induction
colors – (optional) colors for the towers

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('A B', 'B A')
sage: T = iet.IntervalExchangeTransformation(p, [0.41510826, 0.58489174])
sage: T.plot_towers(iterations=5)   # not tested (problem with matplotlib font cache)
Graphics object consisting of 65 graphics primitives

plot_two_intervals(position=(0, 0), vertical_alignment='center', horizontal_alignment='left', interval_height=0.1, labels_height=0.05, fontsize=14, labels=True, colors=None)[source]¶

Returns a picture of the interval exchange transformation.

INPUT:

position - a 2-uple of the position
horizontal_alignment - left (default), center or right
labels - boolean (default: True)
fontsize - the size of the label

OUTPUT:

2d plot – a plot of the two intervals (domain and range)

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b','b a'),[1,1])
sage: t.plot_two_intervals() # random output due to matplotlib deprecation warnings with SageMath <9.1
Graphics object consisting of 8 graphics primitives

range_singularities()[source]¶

Returns the list of singularities of T^{-1}

OUTPUT:

list – real numbers that are singular for T^{-1}

EXAMPLES:

sage: from surface_dynamics import *
sage: t = iet.IET(("a b","b a"), [1, sqrt(2)])
sage: t.range_singularities()
[0, sqrt(2), sqrt(2) + 1]

rauzy_move(side='right', iterations=1, data=False, error_on_saddles=True)[source]¶

Performs a Rauzy move.

INPUT:

side - ‘left’ (or ‘l’ or 0) or ‘right’ (or ‘r’ or 1)
iterations - integer (default :1) the number of iteration of Rauzy
moves to perform
data - whether to return also the paths and composition of towers
error_on_saddles - (default: True) whether to stop when a saddle is encountered

OUTPUT:

iet – the Rauzy move of self
path – (if data=True) a list of ‘t’ and ‘b’
towers – (if data=True) the towers of the Rauzy induction as a word morphism

EXAMPLES:

sage: from surface_dynamics import *

sage: phi = QQbar((sqrt(5)-1)/2)
sage: t1 = iet.IntervalExchangeTransformation(('a b','b a'),[1,phi])
sage: t2 = t1.rauzy_move().normalize(t1.length())
sage: l2 = t2.lengths()
sage: l1 = t1.lengths()
sage: l2[0] == l1[1] and l2[1] == l1[0]
True

sage: tt,path,sub = t1.rauzy_move(iterations=3, data=True)
sage: tt
Interval exchange transformation of [0, 0.3819660112501051?[ with
permutation
a b
b a
sage: path
['b', 't', 'b']
sage: sub
WordMorphism: a->aab, b->aabab

The substitution can also be recovered from the Rauzy diagram:

sage: p = t1.permutation()
sage: p.rauzy_diagram().path(p, *path).substitution() == sub
True

An other examples involving 3 intervals:

sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[1,1,3])
sage: t
Interval exchange transformation of [0, 5[ with permutation
a b c
c b a
sage: t1 = t.rauzy_move()
sage: t1
Interval exchange transformation of [0, 4[ with permutation
a b c
c a b
sage: t2 = t1.rauzy_move()
sage: t2
Interval exchange transformation of [0, 3[ with permutation
a b c
c b a
sage: t2.rauzy_move()
Traceback (most recent call last):
...
ValueError: saddle connection found
sage: t2.rauzy_move(error_on_saddles=False)
Interval exchange transformation of [0, 2[ with permutation
a b
a b

Degenerate cases:

sage: p = iet.Permutation('a b', 'b a')
sage: T = iet.IntervalExchangeTransformation(p, [1,1])
sage: T.rauzy_move(error_on_saddles=False)
Interval exchange transformation of [0, 1[ with permutation
a
a

recoding(n)[source]¶

Recode this interval exchange transformation on the words of length n.

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a d c b', 'b c a d', alphabet='abcd')
sage: T = iet.IntervalExchangeTransformation(p, [119,213,82,33])
sage: T.recoding(2)
Interval exchange transformation of [0, 447[ with permutation
ab db cc cb ba bd bc
ba bd bc cc cb ab db
sage: T.recoding(3)
Interval exchange transformation of [0, 447[ with permutation
aba abd abc dbc ccb cba bab bdb bcc bcb
cba aba abd abc dbc bcc bcb ccb bab bdb

sah_arnoux_fathi_invariant()[source]¶

Return the Sah-Arnoux-Fathi invariant

The interval exchange needs to be defined over a number field. The output is then a vector with rational entries of dimension d (d-1) / 2 where d is the degree of the field.

EXAMPLES:

The golden rotation:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b','b a')
sage: R = p.rauzy_diagram()
sage: g = R.path(p, 't', 'b')
sage: T = g.self_similar_iet()
sage: T.sah_arnoux_fathi_invariant()
(2)

The Sah-Arnoux-Fathi invariant is not changed under Rauzy (or Zorich) induction:

sage: S = T.zorich_move(iterations=100)
sage: S.sah_arnoux_fathi_invariant()
(2)
sage: (T.length().n(), S.length().n())
(2.61803398874989, 0.000000000000000)

An other rotation:

sage: g = R.path(p, 't', 'b', 'b')
sage: T = g.self_similar_iet()
sage: T.sah_arnoux_fathi_invariant()
(1)
sage: T.rauzy_move().sah_arnoux_fathi_invariant()
(1)

Arnoux-Yoccoz in genus 3:

sage: x = polygen(ZZ)
sage: poly = x^3 - x^2 - x - 1
sage: l = max(poly.roots(AA, False))
sage: K.<a> = NumberField(poly, embedding=l)
sage: top = 'A1l A1r A2 B1 B2 C1 C2'
sage: bot = 'A1r B2 B1 C2 C1 A2 A1l'
sage: p = iet.Permutation(top, bot)
sage: lengths = vector((a+1, a**2-a-1, a**2, a, a, 1, 1))
sage: T = iet.IntervalExchangeTransformation(p, lengths)
sage: T.sah_arnoux_fathi_invariant()
(0, 0, 0)

Arnoux-Yoccoz examples in genus 4 (an auto-similar iet):

sage: x = polygen(ZZ)
sage: poly = x^4 - x^3 - x^2 - x - 1
sage: l = max(poly.roots(AA, False))
sage: K.<a> = NumberField(poly, embedding=l)
sage: top = 'A1l A1r A2 B1 B2 C1 C2 D1 D2'
sage: bot = 'A1r B2 B1 C2 C1 D2 D1 A2 A1l'
sage: p = iet.Permutation(top, bot)
sage: lengths = vector((a**4-a**3, 2*a**3-a**4, a**3, a**2, a**2, a, a, 1, 1))
sage: T = iet.IntervalExchangeTransformation(p, lengths)
sage: T.sah_arnoux_fathi_invariant()
(0, 0, 0, 0, 0, 0)
sage: T.zorich_move(iterations=10).sah_arnoux_fathi_invariant()
(0, 0, 0, 0, 0, 0)

A cubic example in genus 4 (H_4(6)^hyp):

sage: p = iet.Permutation([0, 1, 2, 3, 4, 5, 6, 7], [7, 6, 5, 4, 3, 2, 1, 0])
sage: x = polygen(QQ)
sage: poly = x^3 - 6*x^2 + 9*x - 3
sage: emb = AA.polynomial_root(poly, RIF(1.64, 1.66))
sage: K.<A> = NumberField(poly, embedding=emb)
sage: lengths= (-4*A^2 + 4*A + 18, -2*A^2 + 19*A - 25, 168*A^2 - 355*A + 128,
....:           586*A^2 - 1317*A + 576, -725*A^2 + 1626*A - 707,
....:           -11*A^2 - 6*A + 41, -32*A^2 + 100*A - 77, 20*A^2 - 71*A + 63)
sage: S = iet.IntervalExchangeTransformation(p, lengths)
sage: S.permutation().stratum_component()
H_4(6)^hyp
sage: S.sah_arnoux_fathi_invariant()
(0, 0, 0)
sage: S.zorich_move('left', 120).normalize(17) == S
True

A quartic example in genus 4 (H_4(6)^even):

sage: p = iet.Permutation([0, 1, 2, 3, 4, 5, 6, 7], [7, 1, 0, 5, 4, 3, 2, 6])
sage: poly = x^4 - 7*x^3 + 14*x^2 - 8*x + 1
sage: emb = AA.polynomial_root(poly, RIF(0.17, 0.18))
sage: K.<A> = NumberField(poly, embedding=emb)
sage: lengths = (2*A^3 - 18*A^2 + 44*A - 4, -10*A^3 + 55*A^2 - 60*A + 10,
....:    15*A^3 - 90*A^2 + 120*A - 15, -16*A^3 + 94*A^2 - 132*A + 22,
....:    9*A^3 - 56*A^2 + 88*A - 13, 4*A^3 - 16*A^2 + 3*A + 2,
....:    -8*A^3 + 57*A^2 - 101*A + 16, 4*A^3 - 26*A^2 + 38*A - 3)
sage: S = iet.IntervalExchangeTransformation(p, lengths)
sage: S.permutation().stratum_component()
H_4(6)^even
sage: S.sah_arnoux_fathi_invariant()
(0, 0, 0, 0, 0, 0)
sage: S.zorich_move('left', 38).normalize(15) == S
True

show()[source]¶

Shows a picture of the interval exchange transformation

EXAMPLES:

sage: from surface_dynamics import *

sage: phi = QQbar((sqrt(5)-1)/2)
sage: t = iet.IntervalExchangeTransformation(('a b','b a'),[1,phi])
sage: t.show() # not tested (problem with matplotlib font cache)

singularities()[source]¶

The list of singularities of ‘T’ and ‘T^{-1}’.

OUTPUT:

list – two lists of positive numbers which corresponds to extremities: of subintervals

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b','b a'),[1/2,3/2])
sage: t.singularities()
[[0, 1/2, 2], [0, 3/2, 2]]

translations()[source]¶

Return the vector of translations operated on each intervals.

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b c', 'c b a')
sage: T = iet.IntervalExchangeTransformation(p, [5,1,3])
sage: T.translations()
(4, -2, -6)

The order of the entries correspond to the alphabet:

sage: p = iet.Permutation('a c d b', 'b d c a', alphabet='abcd')
sage: T = iet.IntervalExchangeTransformation(p, [1, 1, 1, 1])
sage: T.translations()
(3, -3, 1, -1)

This vector is covariant with respect to the Rauzy matrices:

sage: p = iet.Permutation('a b c d', 'd c b a')
sage: R = p.rauzy_diagram()
sage: g = R.path(p, *'ttbtbtbtbb')
sage: T = g.self_similar_iet()
sage: for i in range(12):
....:     S, code = T.zorich_move(iterations=i, data=True)
....:     gg = R.path(p, *code)
....:     m = gg.matrix()
....:     assert m * S.lengths() == T.lengths()
....:     assert m.transpose() * T.translations() == S.translations()

vector_space()[source]¶

zorich_move(side='right', iterations=1, data=False)[source]¶

Performs a Rauzy move.

INPUT:

side - ‘left’ (or ‘l’ or 0) or ‘right’ (or ‘r’ or 1)
iterations - integer (default :1) the number of iteration of Rauzy
moves to perform
data - whether to return also the path

OUTPUT:

iet – the Rauzy move of self
path – (if data=True) a list of ‘t’ and ‘b’

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c b a')
sage: T = iet.IntervalExchangeTransformation(p, [12, 35, 67])
sage: T.zorich_move()
Interval exchange transformation of [0, 55[ with permutation
a b c
c a b
sage: assert T.permutation() == p and T.lengths() == vector((12,35,67))

A self similar example in genus 2:

sage: p = iet.Permutation('a b c d', 'd a c b')
sage: R = p.rauzy_diagram()
sage: code = 'b'*4 + 't'*1 + 'b'*3 + 't'*1 + 'b'*3 + 't'*1 + 'b'*1 + 't'*1 + 'b'*4 + 't'*1 + 'b'*2 + 't'*7
sage: g = R.path(p, *code)
sage: m = g.matrix()
sage: poly = m.charpoly()
sage: l = max(poly.roots(AA, False))
sage: K.<a> = NumberField(poly, embedding=l)
sage: lengths = (m - a).right_kernel().basis()[0]
sage: T = iet.IntervalExchangeTransformation(p, lengths)
sage: T.normalize(a, inplace=True)
sage: T
Interval exchange transformation of [0, a[ with permutation
a b c d
d a c b
sage: T2, path = T.zorich_move(iterations=12, data=True)
sage: a*T2.lengths() == T.lengths()
True
sage: path == code
True

Saddle connection detection:

sage: p = iet.Permutation('a b c', 'c b a')
sage: T = iet.IntervalExchangeTransformation(p, [41, 22, 135])
sage: T.zorich_move(iterations=100)
Traceback (most recent call last):
...
ValueError: saddle connection found
sage: p = iet.Permutation('a b c d e f', 'f c b e d a')
sage: T = iet.IntervalExchangeTransformation(p, [41, 132, 22, 135, 55, 333])
sage: T.zorich_move(iterations=100)
Traceback (most recent call last):
...
ValueError: saddle connection found

surface_dynamics.interval_exchanges.iet.wedge(u, v)[source]¶: Return the wedge of the vectors u and v