Interval exchange constructors

Interval exchange transformations

This library is designed for the usage and manipulation of interval exchange transformations and linear involutions. It defines specialized types of permutation (constructed using Permutation()) some associated graph (constructed using ?) and some maps of intervals (constructed using IntervalExchangeTransformation()).

EXAMPLES:

sage: from surface_dynamics import *

Creation of an interval exchange transformation (iet):

sage: T = iet.IntervalExchangeTransformation(('a b','b a'),(sqrt(2),1))
sage: T
Interval exchange transformation of [0, sqrt(2) + 1[ with permutation
a b
b a

It can also be initialized using permutation (group theoritic ones):

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

As the iet’s are functions, you can compose and invert them:

sage: T = iet.IntervalExchangeTransformation(('a b','b a'),(sqrt(2),1))
sage: T*T
Interval exchange transformation of [0, sqrt(2) + 1[ with permutation
aa ab ba
ab ba aa
sage: S = T.inverse()
sage: S
Interval exchange transformation of [0, sqrt(2) + 1[ with permutation
b a
a b
sage: S * T
Interval exchange transformation of [0, sqrt(2) + 1[ with permutation
aa bb
aa bb
sage: (S * T).is_identity()
True
sage: T * S
Interval exchange transformation of [0, sqrt(2) + 1[ with permutation
bb aa
bb aa
sage: (T * S).is_identity()
True

For the manipulation of permutations of iet, there are special types provided by this module. All of them can be constructed using the constructor iet.Permutation. For the creation of labelled permutations of interval exchange transformation:

sage: p1 =  iet.Permutation('a b c', 'c b a')
sage: p1
a b c
c b a

They can be used for initialization of an iet:

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

You can also, create labelled permutations of linear involutions:

sage: p = iet.GeneralizedPermutation('a a b', 'b c c')
sage: p
a a b
b c c

By default, the permutations are labelled (it means that the labels are important and (a b / b a) differs from (b a / a b)). It sometimes useful to deal with reduced permutations for which the order does not import:

sage: p = iet.Permutation('a b c', 'c b a', reduced = True)
sage: p
a b c
c b a

Permutations with flips:

sage: p1 = iet.Permutation('a b c', 'c b a', flips = ['a','c'])
sage: p1
-a  b -c
-c  b -a

Creation of Rauzy diagrams:

sage: r = iet.RauzyDiagram('a b c', 'c b a')

Reduced Rauzy diagrams are constructed using the same arguments than for permutations:

sage: r = iet.RauzyDiagram('a b b','c c a')
sage: r_red = iet.RauzyDiagram('a b b','c c a',reduced=True)
sage: r.cardinality()
12
sage: r_red.cardinality()
4

By default, Rauzy diagram are generated by induction on the right. You can use several options to enlarge (or restrict) the diagram (try help(iet.RauzyDiagram) for more precisions):

sage: r1 = iet.RauzyDiagram('a b c','c b a',right_induction=True)
sage: r2 = iet.RauzyDiagram('a b c','c b a',left_right_inversion=True)

You can consider self similar iet using path in Rauzy diagrams and eigenvectors of the corresponding matrix:

sage: p = iet.Permutation("a b c d", "d c b a")
sage: d = p.rauzy_diagram()
sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b')
sage: g
Path of length 8 in a Rauzy diagram
sage: g.is_loop()
True
sage: g.is_full()
True
sage: m = g.matrix()
sage: v = m.eigenvectors_right()[-1][1][0]
sage: T1 = iet.IntervalExchangeTransformation(p, v)
sage: T2 = T1.rauzy_move(iterations=8)
sage: T1.normalize(1) == T2.normalize(1)
True

AUTHORS:

  • Vincent Delecroix (2009-09-29): initial version

surface_dynamics.interval_exchanges.constructors.FlipSequence(*args, **kwds)[source]

Build a flip sequence corresponding to a path in a Rauzy diagram.

A flip sequence is built from an initial permutation (built from Permutation() or GeneralizedPermutation()) and a sequence of Rauzy inductions that could be of the following form:

  • a letter 't' or 'b' for top right and bottom right induction respectively

  • a pair of letters 'tr', 'br', 'tl' or 'bl' for top right, bottom right, top left and bottom left induction respectively

For all available options, see IETFlipSequence.

EXAMPLES:

sage: from surface_dynamics import iet
sage: p = iet.Permutation('a b', 'b a')
sage: f = iet.FlipSequence(p, ['t', 'b'])
sage: f.substitution()
WordMorphism: a->ab, b->abb

sage: f = iet.FlipSequence(p, ['tr', 'bl'])
sage: f.substitution()
WordMorphism: a->bab, b->b
surface_dynamics.interval_exchanges.constructors.GeneralizedPermutation(arg1, arg2=None, reduced=None, flips=None, alphabet=None)[source]

Returns a permutation of an interval exchange transformation.

Those permutations are the combinatoric part of linear involutions and were introduced by Danthony-Nogueira [DanNog90] (the flipped version is also considered in [Nog89]). The full combinatoric study and precise links with strata of quadratic differentials was achieved few years later by Boissy-Lanneau [BoiLan09].

INPUT:

  • intervals - strings, list, tuples

  • reduced - boolean (default: False) specifies reduction. False means labelled permutation and True means reduced permutation.

  • flips - iterable (default: None) the letters which correspond to flipped intervals.

OUTPUT:

generalized permutation – the output type depends on the data.

EXAMPLES:

sage: from surface_dynamics import *

Creation of labelled generalized permutations:

sage: iet.GeneralizedPermutation('a b b','c c a')
a b b
c c a
sage: iet.GeneralizedPermutation('a a','b b c c')
a a
b b c c
sage: iet.GeneralizedPermutation([[0,1,2,3,1],[4,2,5,3,5,4,0]])
0 1 2 3 1
4 2 5 3 5 4 0

Creation of reduced generalized permutations:

sage: iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
a b b
c c a
sage: iet.GeneralizedPermutation('a a b b', 'c c d d', reduced = True)
a a b b
c c d d

Creation of flipped generalized permutations:

sage: iet.GeneralizedPermutation('a b c a', 'd c d b', flips = ['a','b'])
-a -b  c -a
 d  c  d -b
surface_dynamics.interval_exchanges.constructors.IET(permutation=None, lengths=None)

Constructs an Interval exchange transformation.

An interval exchange transformation (or iet) is a map from an interval to itself. It is defined on the interval except at a finite number of points (the singularities) and is a translation on each connected component of the complement of the singularities. Moreover it is a bijection on its image (or it is injective).

An interval exchange transformation is encoded by two data. A permutation (that corresponds to the way we echange the intervals) and a vector of positive reals (that corresponds to the lengths of the complement of the singularities).

INPUT:

  • permutation - a permutation

  • lengths - a list or a dictionary of lengths

OUTPUT:

interval exchange transformation – an map of an interval

EXAMPLES:

sage: from surface_dynamics import *

Two initialization methods, the first using a iet.Permutation:

sage: p = iet.Permutation('a b c','c b a')
sage: t = iet.IntervalExchangeTransformation(p, {'a':1,'b':0.4523,'c':2.8})

The second is more direct:

sage: t = iet.IntervalExchangeTransformation(('a b','b a'),{'a':1,'b':4})

It’s also possible to initialize the lengths only with a list:

sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,0.4,2])

The two fundamental operations are Rauzy move and normalization:

sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,0.4,2])
sage: s = t.rauzy_move()
sage: s_n = s.normalize(t.length())
sage: s_n.length() == t.length()
True

A not too simple example of a self similar interval exchange transformation:

sage: p = iet.Permutation('a b c d','d c b a')
sage: d = p.rauzy_diagram()
sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b')
sage: m = g.matrix()
sage: v = m.eigenvectors_right()[-1][1][0]
sage: t = iet.IntervalExchangeTransformation(p,v)
sage: s = t.rauzy_move(iterations=8)
sage: s.normalize() == t.normalize()
True
surface_dynamics.interval_exchanges.constructors.IETFamily(*args)

Return a linear family of interval exchange transformations

INPUT: either an interval exchange transformation or a pair consisting of a permutation and a cone

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation([0,1,2,3,4,5],[5,4,3,2,1,0])
sage: rays = [[5, 1, 0, 0, 3, 8], [2, 1, 0, 3, 0, 5], [1, 0, 1, 2, 0, 3], [3, 0, 1, 0, 2, 5]]
sage: F = iet.IETFamily(p, rays)    # optional: pplpy
surface_dynamics.interval_exchanges.constructors.IntervalExchangeTransformation(permutation=None, lengths=None)[source]

Constructs an Interval exchange transformation.

An interval exchange transformation (or iet) is a map from an interval to itself. It is defined on the interval except at a finite number of points (the singularities) and is a translation on each connected component of the complement of the singularities. Moreover it is a bijection on its image (or it is injective).

An interval exchange transformation is encoded by two data. A permutation (that corresponds to the way we echange the intervals) and a vector of positive reals (that corresponds to the lengths of the complement of the singularities).

INPUT:

  • permutation - a permutation

  • lengths - a list or a dictionary of lengths

OUTPUT:

interval exchange transformation – an map of an interval

EXAMPLES:

sage: from surface_dynamics import *

Two initialization methods, the first using a iet.Permutation:

sage: p = iet.Permutation('a b c','c b a')
sage: t = iet.IntervalExchangeTransformation(p, {'a':1,'b':0.4523,'c':2.8})

The second is more direct:

sage: t = iet.IntervalExchangeTransformation(('a b','b a'),{'a':1,'b':4})

It’s also possible to initialize the lengths only with a list:

sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,0.4,2])

The two fundamental operations are Rauzy move and normalization:

sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,0.4,2])
sage: s = t.rauzy_move()
sage: s_n = s.normalize(t.length())
sage: s_n.length() == t.length()
True

A not too simple example of a self similar interval exchange transformation:

sage: p = iet.Permutation('a b c d','d c b a')
sage: d = p.rauzy_diagram()
sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b')
sage: m = g.matrix()
sage: v = m.eigenvectors_right()[-1][1][0]
sage: t = iet.IntervalExchangeTransformation(p,v)
sage: s = t.rauzy_move(iterations=8)
sage: s.normalize() == t.normalize()
True
surface_dynamics.interval_exchanges.constructors.IntervalExchangeTransformationFamily(*args)[source]

Return a linear family of interval exchange transformations

INPUT: either an interval exchange transformation or a pair consisting of a permutation and a cone

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation([0,1,2,3,4,5],[5,4,3,2,1,0])
sage: rays = [[5, 1, 0, 0, 3, 8], [2, 1, 0, 3, 0, 5], [1, 0, 1, 2, 0, 3], [3, 0, 1, 0, 2, 5]]
sage: F = iet.IETFamily(p, rays)    # optional: pplpy
surface_dynamics.interval_exchanges.constructors.Permutation(arg1, arg2=None, reduced=None, flips=None, alphabet=None)[source]

Returns a permutation of an interval exchange transformation.

Those permutations are the combinatoric part of an interval exchange transformation (IET). The combinatorial study of those objects starts with Gerard Rauzy [Rau80] and William Veech [Vee78].

The combinatoric part of interval exchange transformation can be taken independently from its dynamical origin. It has an important link with strata of Abelian differential (see ?)

INPUT:

  • intervals - string, two strings, list, tuples that can be converted to two lists

  • reduced - boolean (default: False) specifies reduction. False means labelled permutation and True means reduced permutation.

  • flips - iterable (default: None) the letters which correspond to flipped intervals.

  • alphabet - (optional)

OUTPUT:

permutation – the output type depends of the data.

EXAMPLES:

sage: from surface_dynamics import *

Creation of labelled permutations

sage: iet.Permutation('a b c d','d c b a')
a b c d
d c b a
sage: iet.Permutation([[0,1,2,3],[2,1,3,0]])
0 1 2 3
2 1 3 0
sage: iet.Permutation([0, 'A', 'B', 1], ['B', 0, 1, 'A'])
0 A B 1
B 0 1 A

Creation of reduced permutations:

sage: iet.Permutation('a b c', 'c b a', reduced = True)
a b c
c b a
sage: iet.Permutation([0, 1, 2, 3], [1, 3, 0, 2], reduced=True)
0 1 2 3
1 3 0 2
sage: iet.Permutation([2,1], reduced=True)
1 2
2 1

Managing the alphabet: two labelled permutations with different (ordered) alphabet but with the same labels are equal:

sage: p = iet.Permutation('a b','b a', alphabet='ab')
sage: q = iet.Permutation('a b','b a', alphabet='ba')
sage: str(p) == str(q)
True
sage: p == q
True
sage: p.rauzy_move_matrix('top')
[1 0]
[1 1]
sage: q.rauzy_move_matrix('top')
[1 1]
[0 1]

For reduced permutations, the alphabet does not play any role excepted for printing the object:

sage: p = iet.Permutation('a b c','c b a', reduced=True)
sage: q = iet.Permutation([0,1,2],[2,1,0], reduced=True)
sage: p == q
True

Creation of flipped permutations:

sage: iet.Permutation('a b c', 'c b a', flips=['a','b'])
-a -b  c
 c -b -a
sage: iet.Permutation('a b c', 'c b a', flips='ab', reduced=True)
-a -b  c
 c -b -a
surface_dynamics.interval_exchanges.constructors.Permutations_iterator(nintervals=None, irreducible=True, reduced=False, alphabet=None)[source]

Returns an iterator over permutations.

This iterator allows you to iterate over permutations with given constraints. If you want to iterate over permutations coming from a given stratum you have to use the module ? and generate Rauzy diagrams from connected components.

INPUT:

  • nintervals - non negative integer

  • irreducible - boolean (default: True)

  • reduced - boolean (default: False)

  • alphabet - alphabet (default: None)

OUTPUT:

iterator – an iterator over permutations

EXAMPLES:

sage: from surface_dynamics import *

Generates all reduced permutations with given number of intervals:

sage: P = iet.Permutations_iterator(nintervals=2,alphabet="ab",reduced=True)
sage: for p in P: print("%s\n* *" % p)
a b
b a
* *
sage: P = iet.Permutations_iterator(nintervals=3,alphabet="abc",reduced=True)
sage: for p in P: print("%s\n* * *" % p)
a b c
b c a
* * *
a b c
c a b
* * *
a b c
c b a
* * *
surface_dynamics.interval_exchanges.constructors.RauzyDiagram(arg1, arg2=None, reduced=False, flips=None, alphabet=None, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Return an object coding a Rauzy diagram.

The Rauzy diagram is an oriented graph with labelled edges. The set of vertices corresponds to the permutations obtained by different operations (mainly the .rauzy_move() operations that corresponds to an induction of interval exchange transformation). The edges correspond to the action of the different operations considered.

It first appeard in the original article of Rauzy [Rau80].

INPUT:

  • intervals - lists, or strings, or tuples

  • reduced - boolean (default: False) to precise reduction

  • flips - list (default: []) for flipped permutations

  • right_induction - boolean (default: True) consideration of left induction in the diagram

  • left_induction - boolean (default: False) consideration of right induction in the diagram

  • left_right_inversion - boolean (default: False) consideration of inversion

  • top_bottom_inversion - boolean (default: False) consideration of reversion

  • symmetric - boolean (default: False) consideration of the symmetric operation

OUTPUT:

Rauzy diagram – the Rauzy diagram that corresponds to your request

EXAMPLES:

sage: from surface_dynamics import *

Standard Rauzy diagrams:

sage: iet.RauzyDiagram('a b c d', 'd b c a')
Rauzy diagram with 12 permutations
sage: iet.RauzyDiagram('a b c d', 'd b c a', reduced = True)
Rauzy diagram with 6 permutations

Extended Rauzy diagrams:

sage: iet.RauzyDiagram('a b c d', 'd b c a', symmetric=True)
Rauzy diagram with 144 permutations

Using Rauzy diagrams and path in Rauzy diagrams:

sage: r = iet.RauzyDiagram('a b c', 'c b a')
sage: r
Rauzy diagram with 3 permutations
sage: p = iet.Permutation('a b c','c b a')
sage: p in r
True
sage: g0 = r.path(p, 'top', 'bottom','top')
sage: g1 = r.path(p, 'bottom', 'top', 'bottom')
sage: g0.is_loop()
True
sage: g1.is_loop()
True
sage: g0.is_full()
False
sage: g1.is_full()
False
sage: g = g0 + g1
sage: g
Path of length 6 in a Rauzy diagram
sage: g.is_loop()
True
sage: g.is_full()
True
sage: m = g.matrix()
sage: m
[1 1 1]
[2 4 1]
[2 3 2]
sage: s = g.orbit_substitution()
sage: print(s)
a->acbbc, b->acbbcbbc, c->acbc
sage: s.incidence_matrix() == m
True

We can then create the corresponding interval exchange transformation and comparing the orbit of 0 to the fixed point of the orbit substitution:

sage: v = m.eigenvectors_right()[-1][1][0]
sage: T = iet.IntervalExchangeTransformation(p, v).normalize()
sage: print(T)
Interval exchange transformation of [0, 1[ with permutation
a b c
c b a
sage: w1 = []
sage: x = 0
sage: for i in range(20):
....:  w1.append(T.in_which_interval(x))
....:  x = T(x)
sage: w1 = Word(w1)
sage: w1
word: acbbcacbcacbbcbbcacb
sage: w2 = s.fixed_point('a')
sage: w2[:20]
word: acbbcacbcacbbcbbcacb
sage: w2[:20] == w1
True