Interval exchange transformations

Permutations

Template for permutations of interval exchange transformations

This file define high level operations on permutations (alphabet, the different rauzy moves, …) shared by reduced and labeled permutations.

AUTHORS:

  • Vincent Delecroix (2008-12-20): initial version
  • Vincent Delecroix (2010-02-11): datatype simplification

TODO:

  • disallow access to stratum, stratum component for permutations with flip
  • construct dynamic Rauzy graphs and paths
  • construct coherent _repr_
surface_dynamics.interval_exchanges.template.FlippedPermutation

alias of surface_dynamics.interval_exchanges.template.Permutation

class surface_dynamics.interval_exchanges.template.FlippedPermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.PermutationIET

Template for flipped Abelian permutations.

Warning

Internal class! Do not use directly!

backward_rauzy_move(winner, side=-1)[source]

Returns the permutation before a Rauzy move.

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b c d e','d a b e c', flips='abcd')
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True

Testing the inversion on reduced permutations:

sage: p = iet.Permutation('f a b c d e','d f c b e a', flips='abcd', reduced=True)
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True
rauzy_move(winner, side=-1)[source]

Returns the permutation after a Rauzy move.

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c a b', flips=['b'], reduced=True)
sage: p.rauzy_move('t','r')
 a -b  c
 c -b  a
sage: p.rauzy_move('b','r')
 a -b -c
-b  a -c
sage: p.rauzy_move('t','l')
 a -b  c
 c  a -b
sage: p.rauzy_move('b','l')
-a  b  c
 c  b -a

sage: p = iet.GeneralizedPermutation('a b c d','d a b c',flips='abcd')
sage: p
-a -b -c -d
-d -a -b -c
sage: p.rauzy_move('top','right')
-a -b  c -d
 c -d -a -b
sage: p.rauzy_move('bottom','right')
-a -b  d -c
 d -a -b -c
sage: p.rauzy_move('top','left')
-a -b -c  d
-a  d -b -c
sage: p.rauzy_move('bottom','left')
-b -c -d  a
-d  a -b -c
class surface_dynamics.interval_exchanges.template.FlippedPermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.PermutationLI

Template for flipped quadratic permutations.

Warning

Internal class! Do not use directly!

AUTHORS:

  • Vincent Delecroix (2008-12-20): initial version
backward_rauzy_move(winner, side=-1)[source]

Rauzy move

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b c e b','d c d a e',flips='abcd')
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True

Testing the inversion on reduced permutations:

sage: p = iet.GeneralizedPermutation('a b c e b','d c d a e',flips='abcd',reduced=True)
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True
rauzy_move(winner, side=-1)[source]

Rauzy move

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b c b','d c d a',flips='abcd')
sage: p
-a -b -c -b
-d -c -d -a
sage: p.rauzy_move('top','right')
 a -b  a -c -b
-d -c -d
sage: p.rauzy_move('bottom','right')
 b -a  b -c
-d -c -d -a
sage: p.rauzy_move('top','left')
-a -b -c -b
-c  d -a  d
sage: p.rauzy_move('bottom','left')
-b -c -b
-d -c  a -d  a
class surface_dynamics.interval_exchanges.template.FlippedRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Bases: surface_dynamics.interval_exchanges.template.RauzyDiagram

Template for flipped Rauzy diagrams.

AUTHORS:

  • Vincent Delecroix (2009-09-29): initial version
complete(p, reducible=False)[source]

Completion of the Rauzy diagram

Add all successors of p for defined operations in edge_types. Could be used for generating non (strongly) connected Rauzy diagrams. Sometimes, for flipped permutations, the maximal connected graph in all permutations is not strongly connected. Finding such components needs to call most than once the .complete() method.

INPUT:

  • p - a permutation
  • reducible - put or not reducible permutations

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a',flips='a')
sage: d = p.rauzy_diagram()
sage: d
Rauzy diagram with 3 permutations
sage: p = iet.Permutation('a b c','c b a',flips='b')
sage: d.complete(p)
sage: d
Rauzy diagram with 8 permutations
sage: p = iet.Permutation('a b c','c b a',flips='a')
sage: d.complete(p)
sage: d
Rauzy diagram with 8 permutations
class surface_dynamics.interval_exchanges.template.OrientablePermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.PermutationIET

Template for permutation of Interval Exchange Transformation.

Warning

Internal class! Do not use directly!

AUTHOR:

  • Vincent Delecroix (2008-12-20): initial version
arf_invariant()[source]

Returns the Arf invariant of the permutation.

To a permutation pi is associated a quadratic form on the field with 2 elements. The Arf invariant is the total invariant of linear equivalence class of quadratic form of given rank.

Let V be a vector space on the field with two elements FF_2. V there are two equivalence classes of non degenerate quadratic forms. A complete invariant for quadratic forms is the Arf invariant.

For non zero degenerate quadratic forms there are three equivalence classes. If B denotes the bilinear form associated to q then the three classes are as follows

  • the restriction of q to ker(B) is non zero
  • the restriction of q to ker(B) is zero and the spin parity of q on the quotient V/ker(B) is 0
  • the restriction of q to ker(B) is zero and the spin parity of q on the quotient V/ker(B) is 1

The function returns respectively None, 0 or 1 depending on the three alternatives above.

EXAMPLES:

sage: from surface_dynamics import *

Permutations from the odd and even component of H(2,2,2):

sage: a = range(10)
sage: b1 = [3,2,4,6,5,7,9,8,1,0]
sage: b0 = [6,5,4,3,2,7,9,8,1,0]
sage: p1 = iet.Permutation(a,b1)
sage: p1.arf_invariant()
1
sage: p0 = iet.Permutation(a,b0)
sage: p0.arf_invariant()
0

Permutations from the odd and even component of H(4,4):

sage: a = range(11)
sage: b1 = [3,2,5,4,6,8,7,10,9,1,0]
sage: b0 = [5,4,3,2,6,8,7,10,9,1,0]
sage: p1 = iet.Permutation(a,b1)
sage: p1.arf_invariant()
1
sage: p0 = iet.Permutation(a,b0)
sage: p0.arf_invariant()
0

REFERENCES:

[Jo80] D. Johnson, “Spin structures and quadratic forms on surfaces”, J. London Math. Soc (2), 22, 1980, 365-373

[KoZo03] M. Kontsevich, A. Zorich “Connected components of the moduli spaces of Abelian differentials with prescribed singularities”, Inventiones Mathematicae, 153, 2003, 631-678

attached_in_degree()[source]

Returns the degree of the singularity at the right of the interval.

OUTPUT:

  • a positive integer

EXAMPLES:

sage: from surface_dynamics import *

sage: p1 = iet.Permutation('a b c d e f g','d c g f e b a')
sage: p2 = iet.Permutation('a b c d e f g','e d c g f b a')
sage: p1.attached_in_degree()
1
sage: p2.attached_in_degree()
3
attached_out_degree()[source]

Returns the degree of the singularity at the left of the interval.

OUTPUT:

  • a positive integer

EXAMPLES:

sage: from surface_dynamics import *

sage: p1 = iet.Permutation('a b c d e f g','d c g f e b a')
sage: p2 = iet.Permutation('a b c d e f g','e d c g f b a')
sage: p1.attached_out_degree()
3
sage: p2.attached_out_degree()
1
backward_rauzy_move(winner, side='right', inplace=False)[source]

Returns the permutation before a Rauzy move.

INPUT:

  • winner - ‘top’ or ‘bottom’ interval
  • side - ‘right’ or ‘left’ (defaut: ‘right’) corresponding to the side on which the Rauzy move must be performed.
  • inplace - (default False) whether the Rauzy move is performed inplace (to be used with care since permutations are hashable, set to True if you are sure to know what you are doing)

OUTPUT:

  • a permutation

TESTS:

sage: from surface_dynamics import *

Testing the inversion on labelled permutations:

sage: p = iet.Permutation('a b c d','d c b a')
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True

Testing the inversion on reduced permutations:

sage: p = iet.Permutation('a b c d','d c b a',reduced=True)
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True

Test the inplace option:

sage: p = iet.Permutation('a b c d', 'd c b a')
sage: q = p.backward_rauzy_move('t', inplace=True)
sage: assert q is p
sage: p
a b c d
d b a c
sage: q = p.backward_rauzy_move('t', inplace=True)
sage: q = p.backward_rauzy_move('b', inplace=True)
sage: assert q is p
sage: q = p.rauzy_move('b', inplace=True)
sage: q = p.rauzy_move('t', inplace=True)
sage: q = p.rauzy_move('t', inplace=True)
sage: p
a b c d
d c b a
decompose()[source]

Returns the decomposition as a concatenation of irreducible permutations.

OUTPUT:

a list of permutations

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a').decompose()[0]
sage: p
a b c
c b a
sage: p1,p2,p3 = iet.Permutation('a b c d e','b a c e d').decompose()
sage: p1
a b
b a
sage: p2
c
c
sage: p3
d e
e d
erase_marked_points()[source]

Returns a permutation equivalent to self but without marked points.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: p.erase_marked_points()
a b
b a
sage: p = iet.Permutation('a b1 b2 c d', 'd c b1 b2 a')
sage: p.erase_marked_points()
a b1 c d
d c b1 a
sage: p = iet.Permutation('a0 a1 b0 b1 c0 c1 d0 d1','d0 d1 c0 c1 b0 b1 a0 a1')
sage: p.erase_marked_points()
a0 b0 c0 d0
d0 c0 b0 a0
sage: p = iet.Permutation('a b y0 y1 x0 x1 c d','c x0 x1 a d y0 y1 b')
sage: p.erase_marked_points()
a b c d
c a d b
sage: p = iet.Permutation('a x y z b','b x y z a')
sage: p.erase_marked_points()
a b
b a
sage: p = iet.Permutation("0 1 2 3 4 5 6","6 0 3 2 4 1 5")
sage: p.stratum()
H_3(4, 0)
sage: p.erase_marked_points().stratum()
H_3(4)
genus()[source]

Returns the genus corresponding to any suspension of self.

The genus can be deduced from the profile (see profile()) p = (p_1,ldots,p_k) of self by the formula: 2g-2 = sum_{i=1}^k (p_i-1).

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c b a')
sage: p.genus()
1

sage: p = iet.Permutation('a b c d','d c b a')
sage: p.genus()
2

REFERENCES:

Veech, 1982
intersection_matrix(ring=None)[source]

Returns the intersection matrix.

This d*d antisymmetric matrix is given by the rule :

\[\begin{split}m_{ij} = \begin{cases} 1 & \text{$i < j$ and $\pi(i) > \pi(j)$} \\ -1 & \text{$i > j$ and $\pi(i) < \pi(j)$} \\ 0 & \text{else} \end{cases}\end{split}\]

OUTPUT:

  • a matrix

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d','d c b a')
sage: p.intersection_matrix()
[ 0  1  1  1]
[-1  0  1  1]
[-1 -1  0  1]
[-1 -1 -1  0]
sage: p = iet.Permutation('1 2 3 4 5','5 3 2 4 1')
sage: p.intersection_matrix()
[ 0  1  1  1  1]
[-1  0  1  0  1]
[-1 -1  0  0  1]
[-1  0  0  0  1]
[-1 -1 -1 -1  0]
sage: p = iet.Permutation('a b c d', 'd c b a')
sage: R = p.rauzy_diagram()
sage: g = R.path(p, *'tbt')
sage: m = g.matrix()
sage: q = g.end()
sage: q.intersection_matrix() == m.transpose() * p.intersection_matrix() * m
True
is_cylindric()[source]

Returns True if the permutation is cylindric

A permutation pi is cylindric if pi(1) = n or pi(n) = 1. The name cylindric comes from geometry. A cylindric permutation has a suspension which is a flat surface with a completely periodic horizontal direction which is made of only one cylinder.

EXAMPLES:

sage: from surface_dynamics import *

sage: iet.Permutation('1 2 3','3 2 1').is_cylindric()
True
sage: iet.Permutation('1 2 3','3 1 2').is_cylindric()
True
sage: iet.Permutation('1 2 3 4','3 1 2 4').is_cylindric()
False
is_hyperelliptic()[source]

Returns True if the permutation is in the class of the symmetric permutations (with eventual marked points).

This is equivalent to say that the suspension lives in an hyperelliptic stratum of Abelian differentials H_hyp(2g-2) or H_hyp(g-1, g-1) with some marked points.

EXAMPLES:

sage: from surface_dynamics import *

sage: iet.Permutation('a b c d','d c b a').is_hyperelliptic()
True
sage: iet.Permutation('0 1 2 3 4 5','5 2 1 4 3 0').is_hyperelliptic()
False

REFERENCES:

Gerard Rauzy, “Echanges d’intervalles et transformations induites”, Acta Arith. 34, no. 3, 203-212, 1980

M. Kontsevich, A. Zorich “Connected components of the moduli space of Abelian differentials with prescripebd singularities” Invent. math. 153, 631-678 (2003)

is_identity()[source]

Returns True if self is the identity.

EXAMPLES:

sage: from surface_dynamics import *

sage: iet.Permutation("a b","a b",reduced=False).is_identity()
True
sage: iet.Permutation("a b","a b",reduced=True).is_identity()
True
sage: iet.Permutation("a b","b a",reduced=False).is_identity()
False
sage: iet.Permutation("a b","b a",reduced=True).is_identity()
False
is_standard()[source]

Test if the permutation is standard

A permutation pi is standard if ‘pi(n) = 1` and pi(1) = n.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d','d c b a')
sage: p.is_standard()
True
sage: p = p.rauzy_move('top')
sage: p.is_standard()
False
marked_profile()[source]

Returns the marked profile of the permutation

The marked profile of a permutation corresponds to the integer partition associated to the angles of conical singularities in the the suspension together with a data associated to the endpoint called marking.

If the left endpoint and the right endpoint of the interval associated to the permutation, then the marking is of type one and consists in a couple (m,a) such that m is the angle of the conical singularity and a is the angle between the outgoing separatrix associated to the left endpoint and the incoming separatrix associated to the right endpoint. A marking of type one is denoted (m|a).

If the left endpoint and the right endpoint are two different conical singularities in the suspension the the marking is of type two and consists in a couple (m_l,m_r) where m_l (resp. m_r) is the conical angle of the singularity at the left endpoint (resp. right endpoint). A marking of type two is denoted m_l o m_r

EXAMPLES:

sage: from surface_dynamics import *

The irreducible permutation on 1 interval has marked profile of type 2 with data (0,0):

sage: p = iet.Permutation('a','a')
sage: p.marked_profile()
0o0 []

Permutations in H(3,1) with all possible profiles:

sage: p = iet.Permutation('a b c d e f g','b g a c f e d')
sage: p.interval_diagram()
[[('g', 'd'), 'e', 'f', 'g', 'b', 'c', 'a', ('b', 'a')], ['c', 'd', 'e', 'f']]
sage: p.marked_profile()
4|0 [4, 2]

sage: p = iet.Permutation('a b c d e f g','c a g d f b e')
sage: p.interval_diagram()
[['c', 'd', ('g', 'e'), 'f', 'd', 'e', 'b', ('c', 'a')], ['g', 'a', 'b', 'f']]
sage: p.marked_profile()
4|1 [4, 2]

sage: p = iet.Permutation('a b c d e f g','e b d g c a f')
sage: p.interval_diagram()
[['c', 'd', 'b', 'c', ('g', 'f'), 'g', 'd', ('e', 'a')], ['f', 'a', 'b', 'e']]
sage: p.marked_profile()
4|2 [4, 2]

sage: p = iet.Permutation('a b c d e f g', 'e c g b a f d')
sage: p.interval_diagram()
[['b', 'c', 'e', 'f', 'a', 'b', ('g', 'd'), ('e', 'a')], ['c', 'd', 'f', 'g']]
sage: p.marked_profile()
4|3 [4, 2]

sage: p = iet.Permutation('a b c d e f g', 'f d c a g e b')
sage: p.interval_diagram()
[['c', 'd', 'f', 'g', 'a', 'b', 'e', ('f', 'a')], ['d', 'e', ('g', 'b'), 'c']]
sage: p.marked_profile()
4o2 [4, 2]
marking()[source]

Return the marking induced by the two sides of the interval

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d e f','f a e b d c')
sage: p.marking()
5|0
sage: p = iet.Permutation('0 1 2 3 4 5 6','3 2 4 6 5 1 0')
sage: p.marking()
3o3
order_of_rauzy_action(winner, side=None)[source]

Returns the order of the action of a Rauzy move.

INPUT:

  • winner - string 'top' or 'bottom'
  • side - string 'left' or 'right'

OUTPUT:

An integer corresponding to the order of the Rauzy action.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d','d a c b')
sage: p.order_of_rauzy_action('top', 'right')
3
sage: p.order_of_rauzy_action('bottom', 'right')
2
sage: p.order_of_rauzy_action('top', 'left')
1
sage: p.order_of_rauzy_action('bottom', 'left')
3
profile()[source]

Returns the profile of the permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: iet.Permutation('a b c d','d c b a').profile()
[3]
sage: iet.Permutation('a b c d e','e d c b a').profile()
[2, 2]
rauzy_move(winner, side='right', inplace=False)[source]

Returns the permutation after a Rauzy move.

INPUT:

  • winner - ‘top’ or ‘bottom’ interval
  • side - ‘right’ or ‘left’ (defaut: ‘right’) corresponding to the side on which the Rauzy move must be performed.
  • inplace - (default False) whether the Rauzy move is performed inplace (to be used with care since permutations are hashable, set to True if you are sure to know what you are doing)

OUTPUT:

  • a permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: p.rauzy_move(winner='top', side='right') == p
True
sage: p.rauzy_move(winner='bottom', side='right') == p
True
sage: p.rauzy_move(winner='top', side='left') == p
True
sage: p.rauzy_move(winner='bottom', side='left') == p
True

The options winner can be shortened to ‘t’, ‘b’ and ‘r’, ‘l’. As you can see in the following example:

sage: p = iet.Permutation('a b c','c b a')
sage: p.rauzy_move(winner='t', side='r')
a b c
c a b
sage: p.rauzy_move(winner='b', side='r')
a c b
c b a
sage: p.rauzy_move(winner='t', side='l')
a b c
b c a
sage: p.rauzy_move(winner='b', side='l')
b a c
c b a

This works as well for reduced permutations:

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

If Rauzy induction is not well defined, an error is raised:

sage: p = iet.Permutation('a b', 'a b')
sage: p.rauzy_move('t')
Traceback (most recent call last):
...
ValueError: Rauzy induction is not well defined

Test the inplace option:

sage: p = iet.Permutation('a b c d', 'd c b a')
sage: q = p.rauzy_move('t', inplace=True)
sage: assert q is p
sage: p
a b c d
d a c b
sage: q = p.rauzy_move('b', inplace=True)
sage: assert q is p
stratum()[source]

Returns the strata in which any suspension of this permutation lives.

OUTPUT:

  • a stratum of Abelian differentials

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c b a')
sage: p.stratum()
H_1(0^2)

sage: p = iet.Permutation('a b c d', 'd a b c')
sage: p.stratum()
H_1(0^3)

sage: p = iet.Permutation(range(9), [8,5,2,7,4,1,6,3,0])
sage: p.stratum()
H_3(1^4)

sage: a = 'a b c d e f g h i j'
sage: b3 = 'd c g f e j i h b a'
sage: b2 = 'd c e g f j i h b a'
sage: b1 = 'e d c g f h j i b a'
sage: p3 = iet.Permutation(a, b3)
sage: p3.stratum()
H_4(3, 2, 1)
sage: p2 = iet.Permutation(a, b2)
sage: p2.stratum()
H_4(3, 2, 1)
sage: p1 = iet.Permutation(a, b1)
sage: p1.stratum()
H_4(3, 2, 1)

AUTHORS:

  • Vincent Delecroix (2008-12-20)
stratum_component()[source]

Returns a connected components of a stratum.

EXAMPLES:

sage: from surface_dynamics import *

Permutations from the stratum H(6):

sage: a = range(8)
sage: b_hyp = [7,6,5,4,3,2,1,0]
sage: b_odd = [3,2,5,4,7,6,1,0]
sage: b_even = [5,4,3,2,7,6,1,0]
sage: p_hyp = iet.Permutation(a, b_hyp)
sage: p_odd = iet.Permutation(a, b_odd)
sage: p_even = iet.Permutation(a, b_even)
sage: p_hyp.stratum_component()
H_4(6)^hyp
sage: p_odd.stratum_component()
H_4(6)^odd
sage: p_even.stratum_component()
H_4(6)^even

Permutations from the stratum H(4,4):

sage: a = range(11)
sage: b_hyp = [10,9,8,7,6,5,4,3,2,1,0]
sage: b_odd = [3,2,5,4,6,8,7,10,9,1,0]
sage: b_even = [5,4,3,2,6,8,7,10,9,1,0]
sage: p_hyp = iet.Permutation(a,b_hyp)
sage: p_odd = iet.Permutation(a,b_odd)
sage: p_even = iet.Permutation(a,b_even)
sage: p_hyp.stratum() == AbelianStratum(4,4)
True
sage: p_hyp.stratum_component()
H_5(4^2)^hyp
sage: p_odd.stratum() == AbelianStratum(4,4)
True
sage: p_odd.stratum_component()
H_5(4^2)^odd
sage: p_even.stratum() == AbelianStratum(4,4)
True
sage: p_even.stratum_component()
H_5(4^2)^even

As for stratum you can specify that you want to attach the singularity on the left of the interval using the option marked_separatrix:

sage: a = range(1,10)
sage: b_odd = [4,3,6,5,7,9,8,2,1]
sage: b_even = [6,5,4,3,7,9,8,2,1]
sage: p_odd = iet.Permutation(a,b_odd)
sage: p_even = iet.Permutation(a,b_even)
sage: p_odd.stratum_component()
H_4(4, 2)^odd
sage: p_even.stratum_component()
H_4(4, 2)^even
to_cylindric()[source]

Returns a cylindric permutation in the same Rauzy class.

A permutation is cylindric if the first letter in the top interval is also the last letter of the bottom interval or if the last letter of the top interval is the first letter of the bottom interval.

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: p.to_cylindric() == p
True
sage: p = iet.Permutation('a b c d','b d a c')
sage: q = p.to_cylindric()
sage: q[0][0] == q[1][-1] or q[1][0] == q[1][0]
True
to_permutation()[source]

Returns the permutation as an element of the symetric group.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: p.to_permutation()
[3, 2, 1]
sage: p = Permutation([2,4,1,3])
sage: q = iet.Permutation(p)
sage: q.to_permutation() == p
True
to_standard()[source]

Returns a standard permutation in the same Rauzy class.

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: p.to_standard() == p
True
sage: p = iet.Permutation('a b c d','b d a c')
sage: q = p.to_standard()
sage: q[0][0] == q[1][-1]
True
sage: q[1][0] == q[1][0]
True
class surface_dynamics.interval_exchanges.template.OrientablePermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.PermutationLI

Template for quadratic permutation.

Warning

Internal class! Do not use directly!

AUTHOR:

  • Vincent Delecroix (2008-12-20): initial version
backward_rauzy_move(winner, side='top')[source]

Return the permutation before the Rauzy move.

TESTS:

sage: from surface_dynamics import *

Tests the inversion on labelled generalized permutations:

sage: p = iet.GeneralizedPermutation('a a b b','c c d d')
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True

Tests the inversion on reduced generalized permutations:

sage: p = iet.GeneralizedPermutation('a a b b','c c d d',reduced=True)
sage: for pos,side in [('t','r'),('b','r'),('t','l'),('b','l')]:
....:     q = p.rauzy_move(pos,side)
....:     print(q.backward_rauzy_move(pos,side) == p)
....:     q = p.backward_rauzy_move(pos,side)
....:     print(q.rauzy_move(pos,side) == p)
True
True
True
True
True
True
True
True
rauzy_move(winner, side=-1)[source]

Returns the permutation after a Rauzy move.

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True)
sage: p.rauzy_move(0)
a a b
b c c
sage: p.rauzy_move(1)
a a
b b c c
sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True)
sage: p.rauzy_move(0)
a a b
b c c
sage: p.rauzy_move(1)
a a
b b c c
stratum()[source]

Returns the stratum associated to self

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.stratum()
Q_0(-1^4)
class surface_dynamics.interval_exchanges.template.Permutation(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: sage.structure.sage_object.SageObject

Template for all permutations.

Warning

Internal class! Do not use directly!

This class implement generic algorithm (stratum, connected component, …) and unfies all its children.

It has four attributes

  • _alphabet – the alphabet on which the permutation is defined. Be careful, it might have a different cardinality as the size of the permutation!
  • _twin – the permutation
  • _labels – None or the list of labels
  • _flips – None or the list of flips (each flip is either 1 or -1)

The datatype for _twin differs for IET and LI (TODO: unify).

alphabet(data=None)[source]

Manages the alphabet of self.

If there is no argument, the method returns the alphabet used. If the argument could be converted to an alphabet, this alphabet will be used.

INPUT:

  • data - None or something that could be converted to an alphabet

OUTPUT:

  • either None or the current alphabet

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','a b')
sage: p.alphabet([0,1])
sage: p.alphabet() == Alphabet([0,1])
True
sage: p
0 1
0 1
sage: p.alphabet("cd")
sage: p.alphabet() == Alphabet(['c','d'])
True
sage: p
c d
c d
cover(perms, as_tuple=False)[source]

Return a covering of this permutation.

INPUT:

  • perms - a list of permutations that describe the gluings
  • as_tuple - whether permutations need to be considered as 1-based (default) or 0-based.

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b', 'b a')
sage: p.cover(['(1,2)', '(1,3)'])
Covering of degree 3 of the permutation:
a b
b a

sage: p.cover([[1,0,2], [2,1,0]], as_tuple=True)
Covering of degree 3 of the permutation:
a b
b a

sage: p = iet.GeneralizedPermutation('a a b b','c c')
sage: q = p.cover(['(0,1)', [], [2,1,0]], as_tuple=True)
sage: q
Covering of degree 3 of the permutation:
a a b b
c c
sage: q.covering_data('a')
(1,2)
sage: q.covering_data('b')
()
sage: q.covering_data('c')
(1,3)
flips()[source]

Returns the list of flips.

If the permutation is not a flipped permutations then None is returned.

EXAMPLES:

sage: from surface_dynamics import *

sage: iet.Permutation('a b c', 'c b a').flips()
[]
sage: iet.Permutation('a b c', 'c b a', flips='ac').flips()
['a', 'c']
sage: iet.GeneralizedPermutation('a a', 'b b', flips='a').flips()
['a']
sage: iet.GeneralizedPermutation('a a','b b', flips='b', reduced=True).flips()
['b']
horizontal_inverse()

Returns the top-bottom inverse.

You can use also use the shorter .tb_inverse().

There are two other symmetries of permutation which are accessible via the methods Permutation.left_right_inverse() and Permutation.symmetric().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

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

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','a b')
sage: p == p.top_bottom_inverse()
True
sage: p is p.top_bottom_inverse()
False
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True)
sage: p == p.top_bottom_inverse()
True
sage: p is p.top_bottom_inverse()
False
interval_diagram(glue_ends=True, sign=False)[source]

Return the interval diagram of self.

INPUT:

  • glue_ends - bool (default: True)
  • sign - bool (default: False)

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: p.interval_diagram()
[['b', ('c', 'a')], [('c', 'a'), 'b']]

sage: p = iet.Permutation('a b c','c a b')
sage: p.interval_diagram()
[[('c', 'b'), ('c', 'a')], ['b', 'a']]

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

sage: p = iet.GeneralizedPermutation('a a b b','c c')
sage: p.interval_diagram()
[[('b', 'c', 'a')], ['c'], ['b'], ['a']]
sage: p.interval_diagram(sign=True)
[[(('b', 1), ('c', 1), ('a', 1))], [('c', -1)], [('b', -1)], [('a', -1)]]

sage: p = iet.GeneralizedPermutation((0,1,0,2),(3,2,4,1,4,3))
sage: p.interval_diagram()
[[2, 3, 4, (2, 3, 0)], [4, 1, 0, 1]]
sage: p.interval_diagram(sign=True)
[[(2, 1), (3, -1), (4, 1), ((2, -1), (3, 1), (0, 1))],
 [(4, -1), (1, -1), (0, -1), (1, 1)]]

sage: p = iet.GeneralizedPermutation('a b c d b', 'e d f e a f c', flips='bdf')
sage: p.interval_diagram()
[[('e', 'a')], ['d', 'e', 'f', 'c', ('b', 'c'), 'd', 'f', 'a', 'b']]

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('0 1 2 3 2','4 3 4 1 0')
sage: p.interval_diagram(sign=True)
[[('4', -1), ('3', -1), ('2', -1), ('3', 1)],
 [('1', -1), (('2', 1), ('0', -1)), ('1', 1), (('4', 1), ('0', 1))]]

sage: p = iet.Permutation('a b c', 'c b a', flips='a')
sage: p.interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('c', -1), ('b', 1), ('a', -1), ('b', -1), ('c', 1)]]
sage: p.interval_diagram(glue_ends=True, sign=False)
[['b', 'a', 'b', ('c', 'a', 'c')]]

sage: iet.Permutation('a b c', 'c b a', flips='b').interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('b', 1), ('a', -1), ('c', -1), ('b', -1), ('c', 1)]]
sage: iet.Permutation('a b c', 'c b a', flips='c').interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('b', -1), ('c', 1), ('b', 1), ('a', -1), ('c', -1)]]

sage: iet.Permutation('a b c', 'c b a', flips='bc').interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('b', 1), ('a', -1), ('c', -1)], [('c', 1), ('b', -1)]]
sage: iet.Permutation('a b c', 'c b a', flips='ac').interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('c', -1)], [('b', 1), ('c', 1), ('b', -1), ('a', -1)]]
sage: iet.Permutation('a b c', 'c b a', flips='ab').interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('c', -1), ('b', -1), ('c', 1)], [('b', 1), ('a', -1)]]

sage: iet.Permutation('a b c', 'c b a', flips='abc').interval_diagram(glue_ends=False, sign=True)
[[('a', 1), ('c', -1)], [('b', 1), ('a', -1)], [('c', 1), ('b', -1)]]
left_right_inverse()[source]

Returns the left-right inverse.

The left-right inverse of a permutation, is the permutation obtained by reversing the order of the underlying ordering.

You can also use the shorter .lr_inverse()

There are two other symmetries of permutation which are accessible via the methods Permutation.top_bottom_inverse() and Permutation.symmetric().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

For labelled permutations:

sage: p = iet.Permutation('a b c','c a b')
sage: p.left_right_inverse()
c b a
b a c
sage: p = iet.Permutation('a b c d','c d a b')
sage: p.left_right_inverse()
d c b a
b a d c

for reduced permutations:

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

for labelled quadratic permutations:

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

for reduced quadratic permutations:

sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True)
sage: p.left_right_inverse() == p
True
length(interval=None)[source]

Returns the 2-uple of lengths.

p.length() is identical to (p.length_top(), p.length_bottom()) If an interval is specified, it returns the length of the specified interval.

INPUT:

  • interval - None, ‘top’ (or ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)

OUTPUT:

integer or 2-uple of integers – the corresponding lengths

EXAMPLES:

sage: from surface_dynamics import *

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

sage: p = iet.GeneralizedPermutation('a a b','c d c b d',reduced=False)
sage: p.length()
(3, 5)
sage: p = iet.GeneralizedPermutation('a a b','c d c b d',reduced=True)
sage: p.length()
(3, 5)
length_bottom()[source]

Returns the number of intervals in the bottom segment.

OUTPUT:

integer – the length of the bottom segment

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a',reduced=True)
sage: p.length_bottom()
3
sage: p = iet.Permutation('a b c','c b a',reduced=False)
sage: p.length_bottom()
3
sage: p = iet.GeneralizedPermutation('a a b','c d c b d',reduced=True)
sage: p.length_bottom()
5
sage: p = iet.GeneralizedPermutation('a a b','c d c b d',reduced=False)
sage: p.length_bottom()
5
length_top()[source]

Returns the number of intervals in the top segment.

OUTPUT:

integer – the length of the top segment

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a', reduced=True)
sage: p.length_top()
3
sage: p = iet.Permutation('a b c','c b a', reduced=False)
sage: p.length_top()
3
sage: p = iet.GeneralizedPermutation('a a b','c d c b d',reduced=True)
sage: p.length_top()
3
sage: p = iet.GeneralizedPermutation('a a b','c d c d b',reduced=False)
sage: p.length_top()
3
sage: p = iet.GeneralizedPermutation('a b c b d c d', 'e a e',reduced=True)
sage: p.length_top()
7
sage: p = iet.GeneralizedPermutation('a b c d b c d', 'e a e', reduced=False)
sage: p.length_top()
7
letters()[source]

Returns the list of letters of the alphabet used for representation.

The letters used are not necessarily the whole alphabet (for example if the alphabet is infinite).

OUTPUT: a list of labels

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation([1,2],[2,1])
sage: p.alphabet(Alphabet(name="NN"))
sage: p
0 1
1 0
sage: p.letters()
[0, 1]

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.letters()
['a', 'b', 'c']
sage: p.alphabet(range(10))
sage: p.letters()
[0, 1, 2]
sage: p._remove_interval(0, 2)
sage: p.letters()
[0, 2]

sage: p = iet.GeneralizedPermutation('a a b', 'b c c', reduced=True)
sage: p.letters()
['a', 'b', 'c']

For permutations with flips, the letters appear as pairs made of an element of the alphabet and the flip:

sage: p = iet.Permutation('A B C D', 'D C A B', flips='AC')
sage: p.letters()
['A', 'B', 'C',  'D']

sage: p = iet.GeneralizedPermutation('A A B', 'B C C', flips='B')
sage: p.letters()
['A', 'B', 'C']
lr_inverse()

Returns the left-right inverse.

The left-right inverse of a permutation, is the permutation obtained by reversing the order of the underlying ordering.

You can also use the shorter .lr_inverse()

There are two other symmetries of permutation which are accessible via the methods Permutation.top_bottom_inverse() and Permutation.symmetric().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

For labelled permutations:

sage: p = iet.Permutation('a b c','c a b')
sage: p.left_right_inverse()
c b a
b a c
sage: p = iet.Permutation('a b c d','c d a b')
sage: p.left_right_inverse()
d c b a
b a d c

for reduced permutations:

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

for labelled quadratic permutations:

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

for reduced quadratic permutations:

sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True)
sage: p.left_right_inverse() == p
True
str(sep='\n')[source]

A string representation of the generalized permutation.

INPUT:

  • sep - (default: ‘n’) a separator for the two intervals

OUTPUT:

string – the string that represents the permutation

EXAMPLES:

sage: from surface_dynamics import *

For permutations of iet:

sage: p = iet.Permutation('a b c','c b a')
sage: p.str()
'a b c\nc b a'
sage: p.str(sep=' | ')
'a b c | c b a'

The permutation can be rebuilt from the standard string:

sage: p == iet.Permutation(p.str())
True

For permutations of li:

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.str()
'a b b\nc c a'
sage: p.str(sep=' | ')
'a b b | c c a'

Again, the generalized permutation can be rebuilt from the standard string:

sage: p == iet.GeneralizedPermutation(p.str())
True

With flips:

sage: p = iet.GeneralizedPermutation('a a','b b',flips='a')
sage: print(p.str())
-a -a
 b  b
 sage: print(p.str('/'))
 -a -a/ b  b
symmetric()[source]

Returns the symmetric permutation.

The symmetric permutation is the composition of the top-bottom inversion and the left-right inversion (which are geometrically orientation reversing).

There are two other symmetries of permutation which are accessible via the methods Permutation.left_right_inverse() and Permutation.top_bottom_inverse().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a',reduced=True)
sage: p.symmetric() == p
True
sage: p = iet.Permutation('a b c d','c a d b',reduced=True)
sage: q = p.symmetric()
sage: q
a b c d
b d a c
sage: q1 = p.tb_inverse().lr_inverse()
sage: q2 = p.lr_inverse().tb_inverse()
sage: q == q1 and q == q2
True

It works for any type of permutations:

sage: p = iet.GeneralizedPermutation('a b b','c c a',flips='ab')
sage: p
-a -b -b
 c  c -a
sage: p.symmetric()
-a  c  c
-b -b -a

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True)
sage: q = p.symmetric()
sage: q1 = p.tb_inverse().lr_inverse()
sage: q2 = p.lr_inverse().tb_inverse()
sage: q == q1 and q == q2
True
tb_inverse()

Returns the top-bottom inverse.

You can use also use the shorter .tb_inverse().

There are two other symmetries of permutation which are accessible via the methods Permutation.left_right_inverse() and Permutation.symmetric().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

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

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','a b')
sage: p == p.top_bottom_inverse()
True
sage: p is p.top_bottom_inverse()
False
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True)
sage: p == p.top_bottom_inverse()
True
sage: p is p.top_bottom_inverse()
False
top_bottom_inverse()[source]

Returns the top-bottom inverse.

You can use also use the shorter .tb_inverse().

There are two other symmetries of permutation which are accessible via the methods Permutation.left_right_inverse() and Permutation.symmetric().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

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

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','a b')
sage: p == p.top_bottom_inverse()
True
sage: p is p.top_bottom_inverse()
False
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True)
sage: p == p.top_bottom_inverse()
True
sage: p is p.top_bottom_inverse()
False
vertical_inverse()

Returns the left-right inverse.

The left-right inverse of a permutation, is the permutation obtained by reversing the order of the underlying ordering.

You can also use the shorter .lr_inverse()

There are two other symmetries of permutation which are accessible via the methods Permutation.top_bottom_inverse() and Permutation.symmetric().

OUTPUT: a permutation

EXAMPLES:

sage: from surface_dynamics import *

For labelled permutations:

sage: p = iet.Permutation('a b c','c a b')
sage: p.left_right_inverse()
c b a
b a c
sage: p = iet.Permutation('a b c d','c d a b')
sage: p.left_right_inverse()
d c b a
b a d c

for reduced permutations:

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

for labelled quadratic permutations:

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

for reduced quadratic permutations:

sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True)
sage: p.left_right_inverse() == p
True
class surface_dynamics.interval_exchanges.template.PermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.Permutation

has_rauzy_move(winner, side='right')[source]

Test if a Rauzy move can be performed on this permutation.

EXAMPLES:

sage: from surface_dynamics import *

for labelled permutations:

sage: p = iet.Permutation('a b c','a c b',reduced=False)
sage: p.has_rauzy_move(0,'right')
True
sage: p.has_rauzy_move(0,'left')
False
sage: p.has_rauzy_move(1,'right')
True
sage: p.has_rauzy_move(1,'left')
False

for reduced permutations:

sage: p = iet.Permutation('a b c','a c b',reduced=True)
sage: p.has_rauzy_move(0,'right')
True
sage: p.has_rauzy_move(0,'left')
False
sage: p.has_rauzy_move(1,'right')
True
sage: p.has_rauzy_move(1,'left')
False
is_irreducible(return_decomposition=False)[source]

Test irreducibility.

A permutation p = (p0,p1) is reducible if: set(p0[:i]) = set(p1[:i]) for an i < len(p0)

OUTPUT:

  • a boolean

EXAMPLES:

sage: from surface_dynamics import *

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

sage: p = iet.Permutation('a b c', 'b a c')
sage: p.is_irreducible()
False

sage: p = iet.Permutation('a b c', 'c b a', flips=['a'])
sage: p.is_irreducible()
True
twin(i, pos)[source]

Return the twin of the interval in the interval i at position pos.

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b c e d', 'e b d a c')
sage: p.twin(0,0)
(1, 3)
sage: p.twin(0,1)
(1, 1)

sage: twin_top = [p.twin(0,i) for i in range(p.length_top())]
sage: twin_bot = [p.twin(1,i) for i in range(p.length_bottom())]
sage: p.twin_list() == [twin_top, twin_bot]
True
twin_list()[source]

Returns the twin list of self.

The twin list is the involution without fixed point associated to that permutation seen as two lines of symbols. As the domain is two lines, the position are 2-tuples (i,j) where i specifies the line and j the position in the line.

EXAMPLES:

sage: from surface_dynamics import *

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

We may check that it is actually an involution without fixed point:

sage: t = p.twin_list()
sage: all(t[i][j] != (i,j) for i in xrange(2) for j in xrange(len(t[i])))
True
sage: all(t[t[i][j][0]][t[i][j][1]] == (i,j) for i in xrange(2) for j in xrange(len(t[i])))
True
class surface_dynamics.interval_exchanges.template.PermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.Permutation

erase_marked_points()[source]

Return a permutation without marked points.

This method is not implemented for generalized permutations.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.stratum()
Q_0(-1^4)
sage: p.erase_marked_points()
a a b
b c c
sage: p = iet.GeneralizedPermutation('a d d a b','b c c')
sage: p.stratum()
Q_0(0, -1^4)
sage: p.erase_marked_points()
Traceback (most recent call last):
...
NotImplementedError: Not yet implemented! Do it!
genus()[source]

Returns the genus of any suspension of self.

The genus g can be deduced from the profile (see profile()) p=(p_1,ldots,p_k) of self by the formula: 4g-4 = sum_{i=1}^k (p_i - 2).

EXAMPLES:

sage: from surface_dynamics import *

sage: iet.GeneralizedPermutation('a a b','b c c').genus()
0
sage: iet.GeneralizedPermutation((0,1,2,1,3),(4,3,4,2,0)).genus()
2
has_rauzy_move(winner, side='right')[source]

Test of Rauzy movability (with an eventual specified choice of winner)

A quadratic (or generalized) permutation is rauzy_movable type depending on the possible length of the last interval. It’s dependent of the length equation.

INPUT:

  • winner - the integer ‘top’ or ‘bottom’

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a','b b')
sage: p.has_rauzy_move('top','right')
False
sage: p.has_rauzy_move('top','left')
False
sage: p.has_rauzy_move('bottom','right')
False
sage: p.has_rauzy_move('bottom','left')
False
sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.has_rauzy_move('top','right')
True
sage: p.has_rauzy_move('bottom','right')
True
sage: p.has_rauzy_move('top','left')
True
sage: p.has_rauzy_move('bottom','left')
True
sage: p = iet.GeneralizedPermutation('a a','b b c c')
sage: p.has_rauzy_move('top','right')
True
sage: p.has_rauzy_move('bottom','right')
False
sage: p.has_rauzy_move('top','left')
True
sage: p.has_rauzy_move('bottom','left')
False
sage: p = iet.GeneralizedPermutation('a a b b','c c')
sage: p.has_rauzy_move('top','right')
False
sage: p.has_rauzy_move('bottom','right')
True
sage: p.has_rauzy_move('top','left')
False
sage: p.has_rauzy_move('bottom','left')
True
is_cylindric()[source]

Test if the permutation is cylindric

EXAMPLES:

sage: from surface_dynamics import *

sage: q = iet.GeneralizedPermutation('a b b','c c a')
sage: q.is_cylindric()
True
sage: q = iet.GeneralizedPermutation('a a b b','c c')
sage: q.is_cylindric()
False
is_hyperelliptic(verbose=False)[source]

Test if this permutation is in an hyperelliptic connected component.

EXAMPLES:

sage: from surface_dynamics import *

An example of hyperelliptic permutation:

sage: p = iet.GeneralizedPermutation([0,1,2,0,6,5,3,1,2,3],[4,5,6,4])
sage: p.is_hyperelliptic()
True

Check for the corresondance:

sage: q = QuadraticStratum(6,6)
sage: c_hyp, c_reg, c_irr = q.components()

sage: p_hyp = c_hyp.permutation_representative()
sage: p_hyp
0 1 2 3 4 1 5 6 7
7 6 5 8 4 3 2 8 0
sage: p_hyp.is_hyperelliptic()
True

sage: p_reg = c_reg.permutation_representative()
sage: p_reg
0 1 2 3 4 5 2 6 7 5
1 4 6 8 7 8 3 0
sage: p_reg.is_hyperelliptic()
False

sage: p_irr = c_irr.permutation_representative()
sage: p_irr
0 1 2 3 4 3 5 6 7
1 6 8 4 2 7 5 8 0
sage: p_irr.is_hyperelliptic()
False

sage: q = QuadraticStratum(3,3,2)
sage: c_hyp, c_non_hyp = q.components()
sage: p_hyp = c_hyp.permutation_representative()
sage: p_hyp.is_hyperelliptic()
True
sage: p_non_hyp = c_non_hyp.permutation_representative()
sage: p_non_hyp.is_hyperelliptic()
False
sage: q = QuadraticStratum(5,5,2)
sage: c_hyp, c_non_hyp = q.components()
sage: p_hyp = c_hyp.permutation_representative()
sage: p_hyp.is_hyperelliptic()
True
sage: p_non_hyp = c_non_hyp.permutation_representative()
sage: p_non_hyp.is_hyperelliptic()
False
sage: q = QuadraticStratum(3,3,1,1)
sage: c_hyp, c_non_hyp = q.components()
sage: p_hyp = c_hyp.permutation_representative()
sage: p_hyp.is_hyperelliptic()
True
sage: p_non_hyp = c_non_hyp.permutation_representative()
sage: p_non_hyp.is_hyperelliptic()
False
is_irreducible(return_decomposition=False)[source]

Test of reducibility

A quadratic (or generalized) permutation is reducible if there exists a decomposition

\[ \begin{align}\begin{aligned}A1 u B1 | ... | B1 u A2\\A1 u B2 | ... | B2 u A2\end{aligned}\end{align} \]

where no corners is empty, or exactly one corner is empty and it is on the left, or two and they are both on the right or on the left. The definition is due to [BL08] where they prove that the property of being irreducible is stable under Rauzy induction.

INPUT:

  • return_decomposition - boolean (default: False) - if True, and the permutation is reducible, returns also the blocs A1 u B1, B1 u A2, A1 u B2 and B2 u A2 of a decomposition as above.

OUTPUT:

If return_decomposition is True, returns a 2-uple (test,decomposition) where test is the preceding test and decomposition is a 4-uple (A11,A12,A21,A22) where:

A11 = A1 u B1 A12 = B1 u A2 A21 = A1 u B2 A22 = B2 u A2

EXAMPLES:

sage: from surface_dynamics import *

sage: GP = iet.GeneralizedPermutation

sage: GP('a a','b b').is_irreducible()
False
sage: GP('a a b','b c c').is_irreducible()
True
sage: GP('1 2 3 4 5 1','5 6 6 4 3 2').is_irreducible()
True

TESTS:

sage: from surface_dynamics import *

Test reducible permutations with no empty corner:

sage: GP('1 4 1 3','4 2 3 2').is_irreducible(True)
(False, (['1', '4'], ['1', '3'], ['4', '2'], ['3', '2']))

Test reducible permutations with one left corner empty:

sage: GP('1 2 2 3 1','4 4 3').is_irreducible(True)
(False, (['1'], ['3', '1'], [], ['3']))
sage: GP('4 4 3','1 2 2 3 1').is_irreducible(True)
(False, ([], ['3'], ['1'], ['3', '1']))

Test reducible permutations with two left corner empty:

sage: GP('1 1 2 3','4 2 4 3').is_irreducible(True)
(False, ([], ['3'], [], ['3']))

Test reducible permutations with two right corner empty:

sage: GP('1 2 2 3 3','1 4 4').is_irreducible(True)
(False, (['1'], [], ['1'], []))
sage: GP('1 2 2','1 3 3').is_irreducible(True)
(False, (['1'], [], ['1'], []))
sage: GP('1 2 3 3','2 1 4 4 5 5').is_irreducible(True)
(False, (['1', '2'], [], ['2', '1'], []))

A NotImplementedError is raised when there are flips:

sage: p = iet.GeneralizedPermutation('a b c e b','d c d a e', flips='abcd', reduced=True)
sage: p.is_irreducible()
Traceback (most recent call last):
...
NotImplementedError: irreducibility test not implemented for generalized permutations with flips
sage: p = iet.GeneralizedPermutation('a b c e b','d c d a e', flips='abcd', reduced=False)
sage: p.is_irreducible()
Traceback (most recent call last):
...
NotImplementedError: irreducibility test not implemented for generalized permutations with flips
marked_profile()[source]

Returns the marked profile of self.

The marked profile of a generalized permutation is an integer partition and some additional data associated to the angles of conical singularities in the the suspension. The partition, called the profile, is the list of angles divided by 2pi (see profile()). The additional is called the marking and may be of two different types.

If the left endpoint and the right endpoint of the interval associated to the permutation coincides, then the marking is of type 1 and the additional data consists of a couple (m,a) such that m is the angle of the conical singularity and a is the angle between the outgoing separatrix associated to the left endpoint and the incoming separatrix associated to the right endpoint. A marking of type one is denoted m | a.

If the left endpoint and the right endpoint are two different conical singularities in the suspension, then the marking is of type 2 and the data consists in a couple (m_l,m_r) where m_l (resp. m_r) is the conical angle of the singularity at the left endpoint (resp. right endpoint). A marking of type two is denoted m_l circ m_r

EXAMPLES:

sage: from surface_dynamics import *

All possible markings for the profile [1, 1, 1, 1]:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.marked_profile()
1o1 [1, 1, 1, 1]
sage: p = iet.GeneralizedPermutation('a a','b b c c')
sage: p.marked_profile()
1|0 [1, 1, 1, 1]

All possible markings for the profile [4, 4]:

sage: p = iet.GeneralizedPermutation('0 1 2 1 3','3 4 0 4 2')
sage: p.marked_profile()
4o4 [4, 4]

sage: p = iet.GeneralizedPermutation('0 1 2 1 3','4 3 2 0 4')
sage: p.marked_profile()
4|0 [4, 4]

sage: p = iet.GeneralizedPermutation('0 1 0 2 3 2','4 3 4 1')
sage: p.marked_profile()
4|1 [4, 4]

sage: p = iet.GeneralizedPermutation('0 1 2 3 2','4 3 4 1 0')
sage: p.marked_profile()
4|2 [4, 4]

sage: p = iet.GeneralizedPermutation('0 1 0 1','2 3 2 4 3 4')
sage: p.marked_profile()
4|3 [4, 4]
marking()[source]

Return the marking induced by the two sides of the interval

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('0 1 2 3 4 3 5 6 7','1 6 8 4 2 7 5 8 0')
sage: p.marking()
8|7

sage: p = iet.GeneralizedPermutation('0 1 2 3 4 3 5 6 7','1 6 8 4 2 7 8 0 5')
sage: p.marking()
8o8
orientation_cover()[source]

Return the orientation cover of this permutation.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b', 'b c c')
sage: c = p.orientation_cover()
sage: c
Covering of degree 2 of the permutation:
a a b
b c c
sage: c.stratum()
H_1(0^4)

sage: C = QuadraticStratum(3,2,2,1).unique_component()
sage: p = C.permutation_representative()
sage: c = p.orientation_cover()
sage: c.stratum()
H_6(4, 2, 1^4)
profile()[source]

Returns the profile of self.

The profile of a generalized permutation is the list (d_1, ldots, d_k) where (d_1 pi, ldots, d_k pi) is the list of angles of any suspension of that generalized permutation.

See also marked_profile().

EXAMPLES:

sage: from surface_dynamics import *

sage: p1 = iet.GeneralizedPermutation('a a b','b c c')
sage: p1.profile()
[1, 1, 1, 1]
sage: all(p.profile() == [1, 1, 1, 1] for p in p1.rauzy_diagram())
True

sage: p2 = iet.GeneralizedPermutation('0 1 2 1 3','4 3 4 2 0')
sage: p2.profile()
[4, 4]
sage: all(p.profile() == [4,4] for p in p2.rauzy_diagram())
True

sage: p3 = iet.GeneralizedPermutation('0 1 2 3 3','2 1 4 4 0')
sage: p3.profile()
[3, 3, 1, 1]
sage: all(p.profile() == [3, 3, 1, 1] for p in p3.rauzy_diagram())
True
stratum_component()[source]

Return the connected component of stratum in which self belongs to.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.stratum_component()
Q_0(-1^4)^c

Test the exceptionnal strata in genus 3:

sage: Q = QuadraticStratum(9,-1)
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()
Q_3(9, -1)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()
Q_3(9, -1)^irr

sage: Q = QuadraticStratum(6,3,-1)
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()
Q_3(6, 3, -1)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()
Q_3(6, 3, -1)^irr

sage: Q = QuadraticStratum(3,3,3,-1)
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()
Q_3(3^3, -1)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()
Q_3(3^3, -1)^irr

Test the exceptionnal strata in genus 4:

sage: Q = QuadraticStratum(12)
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()
Q_4(12)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()
Q_4(12)^irr

sage: Q = QuadraticStratum(9,3)
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()  # long time - 1.5sec
Q_4(9, 3)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()  # long time - 2sec
Q_4(9, 3)^irr

sage: Q = QuadraticStratum(6,6)
sage: p = Q.hyperelliptic_component().permutation_representative()
sage: p.stratum_component()
Q_4(6^2)^hyp
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()  # long time - 1sec
Q_4(6^2)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()  # long time - 1sec
Q_4(6^2)^irr

sage: Q = QuadraticStratum(6,3,3)
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()  # long time - 3sec
Q_4(6, 3^2)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()  # long time - 3sec
Q_4(6, 3^2)^irr

sage: Q = QuadraticStratum(3,3,3,3)
sage: p = Q.hyperelliptic_component().permutation_representative()
sage: p.stratum_component()
Q_4(3^4)^hyp
sage: p = Q.regular_component().permutation_representative()
sage: p.stratum_component()  # long time - 5sec
Q_4(3^4)^reg
sage: p = Q.irregular_component().permutation_representative()
sage: p.stratum_component()  # long time - 5sec
Q_4(3^4)^irr
to_cylindric()[source]

Return a cylindric permutation in the same extended Rauzy class

A generalized permutation is cylindric if the first letter in the top interval is the same as the last letter in the bottom interval.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b d a c','c e b e d')
sage: p.is_irreducible()
True
sage: p.to_cylindric().is_cylindric()
True

TESTS:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation([[0,1,1],[2,2,0]], reduced=True)
sage: p.to_cylindric()
0 1 1
2 2 0

ALGORITHM:

The algorithm is naive. It computes the extended Rauzy class until it finds a cylindric permutation.

twin(i, pos)[source]

Return the twin of the letter in interval i at position pos

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.GeneralizedPermutation('a a b c', 'c e b e')
sage: p.twin(0,0)
(0, 1)
sage: p.twin(0,1)
(0, 0)

sage: twin_top = [p.twin(0,i) for i in range(p.length_top())]
sage: twin_bot = [p.twin(1,i) for i in range(p.length_bottom())]
sage: p.twin_list() == [twin_top, twin_bot]
True
twin_list()[source]

Returns the twin list of self.

The twin list is the involution without fixed point which defines it. As the domain is naturally split into two lines we use a 2-tuple (i,j) to specify the element at position j in line i.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.twin_list()[0]
[(0, 1), (0, 0), (1, 0)]
sage: p.twin_list()[1]
[(0, 2), (1, 2), (1, 1)]

And we may check that it is actually an involution without fixed point:

sage: t = p.twin_list()
sage: all(t[i][j] != (i,j) for i in xrange(2) for j in xrange(len(t[i])))
True
sage: all(t[t[i][j][0]][t[i][j][1]] == (i,j) for i in xrange(2) for j in xrange(len(t[i])))
True

A slightly more complicated example:

sage: q = iet.GeneralizedPermutation('a b c a','d e f e g c b g d f')
sage: q.twin_list()[0]
[(0, 3), (1, 6), (1, 5), (0, 0)]
sage: q.twin_list()[1]
[(1, 8), (1, 3), (1, 9), (1, 1), (1, 7), (0, 2), (0, 1), (1, 4), (1, 0), (1, 2)]
sage: t = q.twin_list()
sage: all(t[t[i][j][0]][t[i][j][1]] == (i,j) for i in xrange(2) for j in xrange(len(t[i])))
True
class surface_dynamics.interval_exchanges.template.RauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Bases: sage.structure.sage_object.SageObject

Template for Rauzy diagrams.

AUTHORS:

  • Vincent Delecroix (2008-12-20): initial version
Path[source]

alias of RauzyDiagram.Path

alphabet(data=None)[source]

TESTS:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: r.alphabet() == Alphabet(['a','b'])
True
sage: r = iet.RauzyDiagram([0,1],[1,0])
sage: r.alphabet() == Alphabet([0,1])
True
cardinality()[source]

Returns the number of permutations in this Rauzy diagram.

OUTPUT:

  • integer - the number of vertices in the diagram

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: r.cardinality()
1
sage: r = iet.RauzyDiagram('a b c','c b a')
sage: r.cardinality()
3
sage: r = iet.RauzyDiagram('a b c d','d c b a')
sage: r.cardinality()
7
complete(p)[source]

Completion of the Rauzy diagram.

Add to the Rauzy diagram all permutations that are obtained by successive operations defined by edge_types(). The permutation must be of the same type and the same length as the one used for the creation.

INPUT:

  • p - a permutation of Interval exchange transformation

Rauzy diagram is the reunion of all permutations that could be obtained with successive rauzy moves. This function just use the functions __getitem__ and has_rauzy_move and rauzy_move which must be defined for child and their corresponding permutation types.

TEST:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b c','c b a')   #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',left_induction=True) #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',symmetric=True)   #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',lr_inversion=True)   #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',tb_inversion=True)   #indirect doctest
edge_iterator()[source]

Returns an iterator over the edges of the graph.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: r = p.rauzy_diagram()
sage: for e in r.edge_iterator():
....:     print('%s --> %s' %(e[0].str(sep='/'), e[1].str(sep='/')))
a b/b a --> a b/b a
a b/b a --> a b/b a
edge_to_loser(p=None, edge_type=None)[source]

Return the corresponding loser

TEST:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: r.edge_to_loser(None,None)
[]
edge_to_matrix(p=None, edge_type=None)[source]

Return the corresponding matrix

INPUT:

  • p - a permutation
  • edge_type - 0 or 1 corresponding to the type of the edge

OUTPUT:

A matrix

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: d = p.rauzy_diagram()
sage: print(d.edge_to_matrix(p,1))
[1 0 1]
[0 1 0]
[0 0 1]
edge_to_winner(p=None, edge_type=None)[source]

Return the corresponding winner

TESTS:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: r.edge_to_winner(None,None)
[]
edge_types()[source]

Print information about edges.

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b', 'b a')
sage: r.edge_types()
0: rauzy_move(0, -1)
1: rauzy_move(1, -1)
sage: r = iet.RauzyDiagram('a b', 'b a', left_induction=True)
sage: r.edge_types()
0: rauzy_move(0, -1)
1: rauzy_move(1, -1)
2: rauzy_move(0, 0)
3: rauzy_move(1, 0)
sage: r = iet.RauzyDiagram('a b',' b a',symmetric=True)
sage: r.edge_types()
0: rauzy_move(0, -1)
1: rauzy_move(1, -1)
2: symmetric()
edge_types_index(data)[source]

Try to convert the data as an edge type.

INPUT:

  • data - a string

OUTPUT:

integer

EXAMPLES:

sage: from surface_dynamics import *

For a standard Rauzy diagram (only right induction) the 0 index corresponds to the ‘top’ induction and the index 1 corresponds to the ‘bottom’ one:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: r.edge_types_index('top')
0
sage: r[p][0] == p.rauzy_move('top')
True
sage: r.edge_types_index('bottom')
1
sage: r[p][1] == p.rauzy_move('bottom')
True

The special operations (inversion and symmetry) always appears after the different Rauzy inductions:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram(symmetric=True)
sage: r.edge_types_index('symmetric')
2
sage: r[p][2] == p.symmetric()
True

This function always try to resolve conflictuous name. If it’s impossible a ValueError is raised:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram(left_induction=True)
sage: r.edge_types_index('top')
Traceback (most recent call last):
...
ValueError: left and right inductions must be differentiated
sage: r.edge_types_index('top_right')
0
sage: r[p][0] == p.rauzy_move(0)
True
sage: r.edge_types_index('bottom_left')
3
sage: r[p][3] == p.rauzy_move('bottom', 'left')
True
sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram(left_right_inversion=True,top_bottom_inversion=True)
sage: r.edge_types_index('inversion')
Traceback (most recent call last):
...
ValueError: left-right and top-bottom inversions must be differentiated
sage: r.edge_types_index('lr_inverse')
2
sage: p.lr_inverse() == r[p][2]
True
sage: r.edge_types_index('tb_inverse')
3
sage: p.tb_inverse() == r[p][3]
True

Short names are accepted:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram(right_induction='top',top_bottom_inversion=True)
sage: r.edge_types_index('top_rauzy_move')
0
sage: r.edge_types_index('t')
0
sage: r.edge_types_index('tb')
1
sage: r.edge_types_index('inversion')
1
sage: r.edge_types_index('inverse')
1
sage: r.edge_types_index('i')
1
edges(labels=True)[source]

Returns a list of the edges.

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: len(r.edges())
2
graph()[source]

Returns the Rauzy diagram as a Graph object

The graph returned is more precisely a DiGraph (directed graph) with loops and multiedges allowed.

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b c','c b a')
sage: r
Rauzy diagram with 3 permutations
sage: r.graph()
Looped digraph on 3 vertices
letters()[source]

Returns the letters used by the RauzyDiagram.

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: r.alphabet()
{'a', 'b'}
sage: r.letters()
['a', 'b']
sage: r.alphabet('ABCDEF')
sage: r.alphabet()
{'A', 'B', 'C', 'D', 'E', 'F'}
sage: r.letters()
['A', 'B']
path(*data)[source]

Returns a path over this Rauzy diagram.

INPUT:

  • initial_vertex - the initial vertex (starting point of the path)
  • data - a sequence of edges

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: g = r.path(p, 'top', 'bottom')
vertex_iterator()[source]

Returns an iterator over the vertices

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: for p in r.vertex_iterator(): print(p)
a b
b a
sage: r = iet.RauzyDiagram('a b c d','d c b a')
sage: from itertools import ifilter
sage: r_1n = ifilter(lambda x: x.is_standard(), r)
sage: for p in r_1n: print(p)
a b c d
d c b a
vertices()[source]

Returns a list of the vertices.

EXAMPLES:

sage: from surface_dynamics import *

sage: r = iet.RauzyDiagram('a b','b a')
sage: for p in r.vertices(): print(p)
a b
b a
RauzyDiagram.Path[source]

alias of RauzyDiagram.Path

surface_dynamics.interval_exchanges.template.interval_conversion(interval=None)[source]

Converts the argument in 0 or 1.

INPUT:

  • winner - ‘top’ (or ‘t’ or 0) or bottom (or ‘b’ or 1)

OUTPUT:

integer – 0 or 1

TESTS:

sage: from surface_dynamics import *

sage: from surface_dynamics.interval_exchanges.template import interval_conversion
sage: interval_conversion('top')
0
sage: interval_conversion('t')
0
sage: interval_conversion(0)
0
sage: interval_conversion('bottom')
1
sage: interval_conversion('b')
1
sage: interval_conversion(1)
1
surface_dynamics.interval_exchanges.template.labelize_flip(couple)[source]

Returns a string from a 2-uple couple of the form (name, flip).

TESTS:

sage: from surface_dynamics.interval_exchanges.template import labelize_flip
sage: labelize_flip((0,1))
' 0'
sage: labelize_flip((0,-1))
'-0'
surface_dynamics.interval_exchanges.template.side_conversion(side=None)[source]

Converts the argument in 0 or -1.

INPUT:

  • side - either ‘left’ (or ‘l’ or 0) or ‘right’ (or ‘r’ or -1)

OUTPUT:

integer – 0 or -1

TESTS:

sage: from surface_dynamics.interval_exchanges.template import side_conversion
sage: side_conversion('left')
0
sage: side_conversion('l')
0
sage: side_conversion(0)
0
sage: side_conversion('right')
-1
sage: side_conversion('r')
-1
sage: side_conversion(1)
-1
sage: side_conversion(-1)
-1

Reduced permutations

A reduced (generalized) permutation is better suited to study strata of Abelian (or quadratic) holomorphic forms on Riemann surfaces. The Rauzy diagram is an invariant of such a component. Corentin Boissy proved the identification of Rauzy diagrams with connected components of stratas. But the geometry of the diagram and the relation with the strata is not yet totally understood.

AUTHORS:

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

TESTS:

sage: from surface_dynamics.interval_exchanges.reduced import ReducedPermutationIET
sage: ReducedPermutationIET([['a','b'],['b','a']])
a b
b a
sage: ReducedPermutationIET([[1,2,3],[3,1,2]])
1 2 3
3 1 2
sage: from surface_dynamics.interval_exchanges.reduced import ReducedPermutationLI
sage: ReducedPermutationLI([[1,1],[2,2,3,3,4,4]])
1 1
2 2 3 3 4 4
sage: ReducedPermutationLI([['a','a','b','b','c','c'],['d','d']])
a a b b c c
d d
sage: from surface_dynamics.interval_exchanges.reduced import FlippedReducedPermutationIET
sage: FlippedReducedPermutationIET([[1,2,3],[3,2,1]],flips=[1,2])
-1 -2  3
 3 -2 -1
sage: FlippedReducedPermutationIET([['a','b','c'],['b','c','a']],flips='b')
 a -b  c
-b  c  a
sage: from surface_dynamics.interval_exchanges.reduced import FlippedReducedPermutationLI
sage: FlippedReducedPermutationLI([[1,1],[2,2,3,3,4,4]], flips=[1,4])
-1 -1
 2  2  3  3 -4 -4
sage: FlippedReducedPermutationLI([['a','a','b','b'],['c','c']],flips='ac')
-a -a  b  b
-c -c
sage: from surface_dynamics.interval_exchanges.reduced import ReducedRauzyDiagram
sage: p = ReducedPermutationIET([[1,2,3],[3,2,1]])
sage: d = ReducedRauzyDiagram(p)
surface_dynamics.interval_exchanges.reduced.FlippedReducedPermutation

alias of surface_dynamics.interval_exchanges.reduced.ReducedPermutation

class surface_dynamics.interval_exchanges.reduced.FlippedReducedPermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.reduced.ReducedPermutation, surface_dynamics.interval_exchanges.template.FlippedPermutationIET

Flipped Reduced Permutation from iet

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c b a', flips=['a'], reduced=True)
sage: p.rauzy_move(1)
-a -b  c
-a  c -b

TESTS:

sage: p = iet.Permutation('a b','b a',flips=['a'])
sage: p == loads(dumps(p))
True

sage: p = iet.Permutation('a b c', 'c a b', flips=['b'], reduced=True)
sage: for q in p.rauzy_diagram():
....:     print('%s\n********' % q)
 a -b  c
 c  a -b
********
 a -b -c
-b  a -c
********
-a  b -c
 b -a -c
********
 a  b -c
 b -c  a
********
 a -b  c
 c -b  a
********
list(flips=False)[source]

Returns a list representation of self.

INPUT:

  • flips - boolean (default: False) if True the output contains
    2-uple of (label, flip)

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a',reduced=True,flips='b')
sage: p.list(flips=True)
[[('a', 1), ('b', -1)], [('b', -1), ('a', 1)]]
sage: p.list(flips=False)
[['a', 'b'], ['b', 'a']]
sage: p.alphabet([0,1])
sage: p.list(flips=True)
[[(0, 1), (1, -1)], [(1, -1), (0, 1)]]
sage: p.list(flips=False)
[[0, 1], [1, 0]]

One can recover the initial permutation from this list:

sage: p = iet.Permutation('a b','b a',reduced=True,flips='a')
sage: iet.Permutation(p.list(), flips=p.flips(), reduced=True) == p
True
rauzy_diagram(**kargs)[source]

Returns the associated Rauzy diagram.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a',reduced=True,flips='a')
sage: r = p.rauzy_diagram()
sage: p in r
True
class surface_dynamics.interval_exchanges.reduced.FlippedReducedPermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.reduced.ReducedPermutation, surface_dynamics.interval_exchanges.template.FlippedPermutationLI

Flipped Reduced Permutation from li

EXAMPLES:

sage: from surface_dynamics import *

Creation using the GeneralizedPermutation function:

sage: p = iet.GeneralizedPermutation('a a b', 'b c c', reduced=True, flips='a')
list(flips=False)[source]

Returns a list representation of self.

INPUT:

  • flips - boolean (default: False) return the list with flips

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True,flips='a')
sage: p.list(flips=True)
[[('a', -1), ('a', -1)], [('b', 1), ('b', 1)]]
sage: p.list(flips=False)
[['a', 'a'], ['b', 'b']]

sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True,flips='abc')
sage: p.list(flips=True)
[[('a', -1), ('a', -1), ('b', -1)], [('b', -1), ('c', -1), ('c', -1)]]
sage: p.list(flips=False)
[['a', 'a', 'b'], ['b', 'c', 'c']]

one can rebuild the permutation from the list:

sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='a',reduced=True)
sage: iet.GeneralizedPermutation(p.list(),flips=p.flips(),reduced=True) == p
True
rauzy_diagram(**kargs)[source]

Returns the associated Rauzy diagram.

For more explanation and a list of arguments try help(iet.RauzyDiagram)

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b','c c b',reduced=True)
sage: r = p.rauzy_diagram()
sage: p in r
True
class surface_dynamics.interval_exchanges.reduced.FlippedReducedRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Bases: surface_dynamics.interval_exchanges.template.FlippedRauzyDiagram, surface_dynamics.interval_exchanges.reduced.ReducedRauzyDiagram

Rauzy diagram of flipped reduced permutations.

TESTS:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c a b', flips=['b'], reduced=True)
sage: r = p.rauzy_diagram()
sage: r
Rauzy diagram with 5 permutations
sage: p in r
True
sage: p.rauzy_move('t','r') in r
True
sage: p.rauzy_move('b','r') in r
True

sage: p = iet.GeneralizedPermutation('a b b','c c a',flips='a',reduced=True)
sage: r = p.rauzy_diagram()
Traceback (most recent call last):
...
NotImplementedError: irreducibility test not implemented for generalized permutations with flips
class surface_dynamics.interval_exchanges.reduced.ReducedPermutation[source]

Bases: sage.structure.sage_object.SageObject

Template for reduced objects.

Warning

Internal class! Do not use directly!

class surface_dynamics.interval_exchanges.reduced.ReducedPermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.reduced.ReducedPermutation, surface_dynamics.interval_exchanges.template.OrientablePermutationIET

Reduced permutation from iet

Permutation from iet without numerotation of intervals. For initialization, you should use GeneralizedPermutation which is the class factory for all permutation types.

EXAMPLES:

sage: from surface_dynamics import *

Equality testing (no equality of letters but just of ordering):

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

Reducibility testing:

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

Rauzy movability and Rauzy move:

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

Rauzy diagrams:

sage: p = iet.Permutation('a b c d', 'd a b c')
sage: p_red = iet.Permutation('a b c d', 'd a b c', reduced = True)
sage: d = p.rauzy_diagram()
sage: d_red = p_red.rauzy_diagram()
sage: p.rauzy_move(0) in d
True
sage: d.cardinality()
12
sage: d_red.cardinality()
6
list()[source]

Returns a list of two list that represents the permutation.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b','b a',reduced=True)
sage: p.list() == [['a', 'b'], ['b', 'a']]
True
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True)
sage: p.list() == [['a', 'a'], ['b', 'b']]
True
rauzy_class_cardinality(extended=False)[source]

Cardinality of Rauzy diagram

As proved in [Del10], there exists a closed formula for the cardinality of Rauzy diagrams. This function uses the formula without any explicit computation of the rauzy class.

INPUT:

  • extended - boolean (default: False) - return cardinality for extended Rauzy diagrams

EXAMPLES:

sage: from surface_dynamics import *

Examples for permutations such that the suspensions are tori:

sage: p=iet.Permutation('a b','b a',reduced=True)
sage: p.stratum()
H_1(0)
sage: p.rauzy_diagram()
Rauzy diagram with 1 permutation
sage: p.rauzy_class_cardinality()
1

sage: p = iet.Permutation('a 1 b','b 1 a',reduced=True)
sage: p.stratum()
H_1(0^2)
sage: p.rauzy_diagram()
Rauzy diagram with 3 permutations
sage: p.rauzy_class_cardinality()
3

sage: p = iet.Permutation('a 1 2 b','b 1 2 a',reduced=True)
sage: p.stratum()
H_1(0^3)
sage: p.rauzy_diagram()
Rauzy diagram with 6 permutations
sage: p.rauzy_class_cardinality()
6

sage: p = iet.Permutation('a 1 2 3 b','b 1 2 3 a',reduced=True)
sage: p.rauzy_class_cardinality()
10
sage: p = iet.Permutation('a 1 2 3 4 b','b 1 2 3 4 a',reduced=True)
sage: p.rauzy_class_cardinality()
15

You should have recognize the sequence 1, 3, 6, 10, 15… which is the sequence with general term the binomial n(n+1)/2.

An example of extended Rauzy diagram which is different from Rauzy diagram:

sage: p = iet.Permutation('a b c d e f g','g c b f e d a',reduced=True)
sage: p.marked_profile()
2o4 [4, 2]
sage: pp = p.left_right_inverse()
sage: pp.marked_profile()
4o2 [4, 2]
sage: p.rauzy_class_cardinality()
261
sage: pp.rauzy_class_cardinality()
509
sage: p.rauzy_class_cardinality(extended=True)
770
sage: 261 + 509 == 770
True

And one can check that this the algorithm for cardinality is True:

sage: p.rauzy_diagram()
Rauzy diagram with 261 permutations
sage: pp.rauzy_diagram()
Rauzy diagram with 509 permutations
sage: p.rauzy_diagram(extended=True)
Rauzy diagram with 770 permutations

And we end by an example of Rauzy diagram associated to an hyperelliptic component:

sage: p = iet.Permutation('a b c d e 0 f','f e d c b 0 a',reduced=True)
sage: p.rauzy_diagram()
Rauzy diagram with 37 permutations
sage: p.rauzy_class_cardinality()
37
sage: p.rauzy_diagram(extended=True)
Rauzy diagram with 254 permutations
sage: p.rauzy_class_cardinality(extended=True)
254
rauzy_diagram(extended=False, **kwds)[source]

Returns a Rauzy diagram associated to this permutation

INPUT:

  • extended - boolean (default: False) - if True return extended Rauzy diagram

OUTPUT:

A Rauzy diagram

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d', 'd a b c',reduced=True)
sage: d = p.rauzy_diagram()
sage: p.rauzy_move(0) in d
True
sage: p.rauzy_move(1) in d
True

For more information, try help RauzyDiagram

rauzy_move_relabel(winner, side='right')[source]

Returns the relabelization obtained from this move.

EXAMPLE:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d','d c b a')
sage: q = p.reduced()
sage: p_t = p.rauzy_move('t')
sage: q_t = q.rauzy_move('t')
sage: s_t = q.rauzy_move_relabel('t')
sage: print(s_t)
a->a, b->b, c->c, d->d
sage: map(s_t, p_t[0]) == map(Word, q_t[0])
True
sage: map(s_t, p_t[1]) == map(Word, q_t[1])
True
sage: p_b = p.rauzy_move('b')
sage: q_b = q.rauzy_move('b')
sage: s_b = q.rauzy_move_relabel('b')
sage: print(s_b)
a->a, b->d, c->b, d->c
sage: map(s_b, q_b[0]) == map(Word, p_b[0])
True
sage: map(s_b, q_b[1]) == map(Word, p_b[1])
True
class surface_dynamics.interval_exchanges.reduced.ReducedPermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.reduced.ReducedPermutation, surface_dynamics.interval_exchanges.template.OrientablePermutationLI

Reduced quadratic (or generalized) permutation.

EXAMPLES:

sage: from surface_dynamics import *

Reducibility testing:

sage: p = iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
sage: p.is_irreducible()
True
sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c', reduced = True)
sage: p.is_irreducible()
False
sage: test, decomposition = p.is_irreducible(return_decomposition = True)
sage: test
False
sage: decomposition
(['a'], ['c', 'a'], [], ['c'])

Rauzy movavability and Rauzy move:

sage: p = iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
sage: p.has_rauzy_move(0)
True
sage: p.rauzy_move(0)
a a b b
c c
sage: p.rauzy_move(0).has_rauzy_move(0)
False
sage: p.rauzy_move(1)
a b b
c c a

Rauzy diagrams:

sage: p_red = iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
sage: d_red = p_red.rauzy_diagram()
sage: d_red.cardinality()
4
list()[source]

The permutations as a list of two lists.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
sage: list(p)
[['a', 'b', 'b'], ['c', 'c', 'a']]
rauzy_diagram(**kargs)[source]

Returns the associated Rauzy diagram.

The Rauzy diagram of a permutation corresponds to all permutations that we could obtain from this one by Rauzy move. The set obtained is a labelled Graph. The label of vertices being 0 or 1 depending on the type.

OUTPUT:

Rauzy diagram – the graph of permutations obtained by rauzy induction

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d', 'd a b c')
sage: d = p.rauzy_diagram()
surface_dynamics.interval_exchanges.reduced.ReducedPermutationsIET_iterator(nintervals=None, irreducible=True, alphabet=None)[source]

Returns an iterator over reduced permutations

INPUT:

  • nintervals - integer or None
  • irreducible - boolean
  • alphabet - something that should be converted to an alphabet of at least nintervals letters

TESTS:

sage: from surface_dynamics import *

sage: for p in iet.Permutations_iterator(3,reduced=True,alphabet="abc"):
....:     print(p)  #indirect doctest
a b c
b c a
a b c
c a b
a b c
c b a
class surface_dynamics.interval_exchanges.reduced.ReducedRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Bases: surface_dynamics.interval_exchanges.template.RauzyDiagram

Rauzy diagram of reduced permutations

surface_dynamics.interval_exchanges.reduced.labelize_flip(couple)[source]

Returns a string from a 2-uple couple of the form (name, flip).

TESTS:

sage: from surface_dynamics.interval_exchanges.reduced import labelize_flip
sage: labelize_flip((4,1))
' 4'
sage: labelize_flip(('a',-1))
'-a'

Labelled permutations

A labelled (generalized) permutation is better suited to study the dynamic of a translation surface than a reduced one (see the module surface_dynamics.interval_exchanges.reduced). The latter is more adapted to the study of strata. This kind of permutation was introduced by Yoccoz [Yoc05] (see also [MMY03]).

In fact, there is a geometric counterpart of labelled permutations. They correspond to translation surface with marked outgoing separatrices (i.e. we fi a label for each of them).

Remarks that Rauzy diagram of reduced objects are significantly smaller than the one for labelled object (for the permutation a b d b e / e d c a c the labelled Rauzy diagram contains 8760 permutations, and the reduced only 73). But, as it is in geometrical way, the labelled Rauzy diagram is a covering of the reduced Rauzy diagram.

AUTHORS:

  • Vincent Delecroix (2009-09-29) : initial version
  • Vincent Delecroix (2010-02-11) : correction and simplification of datatypes

TESTS:

sage: from surface_dynamics.interval_exchanges.labelled import LabelledPermutationIET
sage: LabelledPermutationIET([['a','b','c'],['c','b','a']])
a b c
c b a
sage: LabelledPermutationIET([[1,2,3,4],[4,1,2,3]])
1 2 3 4
4 1 2 3
sage: from surface_dynamics.interval_exchanges.labelled import LabelledPermutationLI
sage: LabelledPermutationLI([[1,1],[2,2,3,3,4,4]])
1 1
2 2 3 3 4 4
sage: LabelledPermutationLI([['a','a','b','b','c','c'],['d','d']])
a a b b c c
d d
sage: from surface_dynamics.interval_exchanges.labelled import FlippedLabelledPermutationIET
sage: FlippedLabelledPermutationIET([[1,2,3],[3,2,1]],flips=[1,2])
-1 -2  3
 3 -2 -1
sage: FlippedLabelledPermutationIET([['a','b','c'],['b','c','a']],flips='b')
 a -b  c
-b  c  a
sage: from surface_dynamics.interval_exchanges.labelled import FlippedLabelledPermutationLI
sage: FlippedLabelledPermutationLI([[1,1],[2,2,3,3,4,4]], flips=[1,4])
-1 -1
 2  2  3  3 -4 -4
sage: FlippedLabelledPermutationLI([['a','a','b','b'],['c','c']],flips='ac')
-a -a  b  b
-c -c
sage: from surface_dynamics.interval_exchanges.labelled import LabelledRauzyDiagram
sage: p = LabelledPermutationIET([[1,2,3],[3,2,1]])
sage: d1 = LabelledRauzyDiagram(p)
sage: p = LabelledPermutationIET([['a','b'],['b','a']])
sage: d = p.rauzy_diagram()
sage: g1 = d.path(p, 'top', 'bottom')
sage: g1.matrix()
[1 1]
[1 2]
sage: g2 = d.path(p, 'bottom', 'top')
sage: g2.matrix()
[2 1]
[1 1]
sage: p = LabelledPermutationIET([['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: s1 = g.orbit_substitution()
sage: print(s1)
a->adbd, b->adbdbd, c->adccd, d->adcd
sage: s2 = g.interval_substitution()
sage: print(s2)
a->abcd, b->bab, c->cdc, d->dcbababcd
sage: s1.incidence_matrix() == s2.incidence_matrix().transpose()
True

REFERENCES:

[Yoc05]Jean-Cristophe Yoccoz “Echange d’Intervalles”, Cours au college de France
[MMY03]Jean-Cristophe Yoccoz, Stefano Marmi and Pierre Moussa “On the cohomological equation for interval exchange maps”, arXiv:math/0304469v1
class surface_dynamics.interval_exchanges.labelled.FlippedLabelledPermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.FlippedPermutationIET, surface_dynamics.interval_exchanges.labelled.LabelledPermutationIET

Flipped labelled permutation from iet.

EXAMPLES:

sage: from surface_dynamics import *

Reducibility testing (does not depends of flips):

sage: p = iet.Permutation('a b c', 'c b a',flips='a')
sage: p.is_irreducible()
True
sage: q = iet.Permutation('a b c d', 'b a d c', flips='bc')
sage: q.is_irreducible()
False

Rauzy movability and Rauzy move:

sage: p = iet.Permutation('a b c', 'c b a',flips='a')
sage: p
-a  b  c
 c  b -a
sage: p.rauzy_move(1)
-c -a  b
-c  b -a
sage: p.rauzy_move(0)
-a  b  c
 c -a  b

Rauzy diagrams:

sage: d = iet.RauzyDiagram('a b c d','d a b c',flips='a')
rauzy_diagram(**kargs)[source]

Returns the Rauzy diagram associated to this permutation.

For more information, try help(iet.RauzyDiagram)

OUTPUT:

RauzyDiagram – the Rauzy diagram of self

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c b a',flips='a')
sage: p.rauzy_diagram()
Rauzy diagram with 3 permutations
reduced()[source]

The associated reduced permutation.

OUTPUT:

permutation – the associated reduced permutation

EXAMPLE:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a',flips='a')
sage: q = iet.Permutation('a b c','c b a',flips='a',reduced=True)
sage: p.reduced() == q
True
class surface_dynamics.interval_exchanges.labelled.FlippedLabelledPermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.template.FlippedPermutationLI, surface_dynamics.interval_exchanges.labelled.LabelledPermutationLI

Flipped labelled quadratic (or generalized) permutation.

EXAMPLES:

sage: from surface_dynamics import *

Rauzy movability and Rauzy move:

sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d', flips='d')
sage: p.has_rauzy_move(0)
False
sage: p.has_rauzy_move(1)
True
sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c')
sage: p.has_rauzy_move(0)
True
sage: p.has_rauzy_move(1)
True
left_rauzy_move(winner)[source]

Perform a Rauzy move on the left.

INPUT:

  • winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)

OUTPUT:

– a permutation

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.left_rauzy_move(0)
a a b b
c c
sage: p.left_rauzy_move(1)
a a b
b c c
sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.left_rauzy_move(0)
a b b
c c a
sage: p.left_rauzy_move(1)
b b
c c a a
rauzy_diagram(**kargs)[source]

Returns the associated Rauzy diagram.

For more information, try help(RauzyDiagram)

OUTPUT :

– a RauzyDiagram

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b b a', 'c d c d')
sage: d = p.rauzy_diagram()
reduced()[source]

The associated reduced permutation.

OUTPUT:

permutation – the associated reduced permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a','b b c c',flips='a')
sage: q = iet.GeneralizedPermutation('a a','b b c c',flips='a',reduced=True)
sage: p.reduced() == q
True
right_rauzy_move(winner)[source]

Perform a Rauzy move on the right (the standard one).

INPUT:

  • winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)

OUTPUT:

permutation – the Rauzy move of self

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c')
sage: p.right_rauzy_move(0)
 a  a  b
-c  b -c
sage: p.right_rauzy_move(1)
 a  a
-b -c -b -c
sage: p = iet.GeneralizedPermutation('a b b','c c a',flips='ab')
sage: p.right_rauzy_move(0)
 a -b  a -b
 c  c
sage: p.right_rauzy_move(1)
 b -a  b
 c  c -a
class surface_dynamics.interval_exchanges.labelled.FlippedLabelledRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Bases: surface_dynamics.interval_exchanges.template.FlippedRauzyDiagram, surface_dynamics.interval_exchanges.labelled.LabelledRauzyDiagram

Rauzy diagram of flipped labelled permutations

class surface_dynamics.interval_exchanges.labelled.LabelledPermutation[source]

Bases: sage.structure.sage_object.SageObject

General template for labelled objects.

Warning

Internal class! Do not use directly!

list(flips=False)[source]

Returns a list of two lists corresponding to the intervals.

INPUT:

  • flips - boolean (default: False) - if True returns instead of letters use pair of letter and flip.

OUTPUT: two lists of labels (or labels with flips)

EXAMPLES:

sage: from surface_dynamics import *

The list of an permutation from iet:

sage: p1 = iet.Permutation('1 2 3', '3 1 2')
sage: p1.list()
[['1', '2', '3'], ['3', '1', '2']]
sage: p1.alphabet("abc")
sage: p1.list()
[['a', 'b', 'c'], ['c', 'a', 'b']]

Recovering the permutation from this list (and the alphabet):

sage: q1 = iet.Permutation(p1.list(),alphabet=p1.alphabet())
sage: p1 == q1
True

The list of a quadratic permutation:

sage: p2 = iet.GeneralizedPermutation('g o o', 'd d g')
sage: p2.list()
[['g', 'o', 'o'], ['d', 'd', 'g']]

Recovering the permutation:

sage: q2 = iet.GeneralizedPermutation(p2.list(),alphabet=p2.alphabet())
sage: p2 == q2
True

Some non-orientable examples:

sage: p = iet.GeneralizedPermutation('0 0 1 2 2 1', '3 3', flips='1')
sage: p.list(flips=True)
[[('0', 1), ('0', 1), ('1', -1), ('2', 1), ('2', 1), ('1', -1)], [('3', 1), ('3', 1)]]
sage: p.list(flips=False)
[['0', '0', '1', '2', '2', '1'], ['3', '3']]

sage: iet.Permutation('a b c', 'c b a').list(flips=True)
[[('a', 1), ('b', 1), ('c', 1)], [('c', 1), ('b', 1), ('a', 1)]]

The list can be used to reconstruct the permutation:

sage: p = iet.Permutation('a b c','c b a',flips='ab')
sage: p == iet.Permutation(p.list(), flips=p.flips())
True
sage: p = iet.GeneralizedPermutation('a b b c','c d d a',flips='ad')
sage: p == iet.GeneralizedPermutation(p.list(), flips=p.flips())
True
rauzy_move_loser(winner=None, side=None)[source]

Returns the loser of a Rauzy move

INPUT:

  • winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)
  • side - either ‘left’ or ‘right’ (‘l’ or ‘r’ for short)

OUTPUT:

– a label

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d','b d a c')
sage: p.rauzy_move_loser('top','right')
'c'
sage: p.rauzy_move_loser('bottom','right')
'd'
sage: p.rauzy_move_loser('top','left')
'b'
sage: p.rauzy_move_loser('bottom','left')
'a'
rauzy_move_matrix(winner=None, side='right')[source]

Returns the Rauzy move matrix.

This matrix corresponds to the action of a Rauzy move on the vector of lengths. By convention (to get a positive matrix), the matrix is define as the inverse transformation on the length vector.

OUTPUT:

matrix – a square matrix of positive integers

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b','b a')
sage: p.rauzy_move_matrix('t')
[1 0]
[1 1]
sage: p.rauzy_move_matrix('b')
[1 1]
[0 1]
sage: p = iet.Permutation('a b c d','b d a c')
sage: q = p.left_right_inverse()
sage: m0 = p.rauzy_move_matrix(winner='top',side='right')
sage: n0 = q.rauzy_move_matrix(winner='top',side='left')
sage: m0 == n0
True
sage: m1 = p.rauzy_move_matrix(winner='bottom',side='right')
sage: n1 = q.rauzy_move_matrix(winner='bottom',side='left')
sage: m1 == n1
True
rauzy_move_winner(winner=None, side=None)[source]

Returns the winner of a Rauzy move.

INPUT:

  • winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)
  • side - either ‘left’ or ‘right’ (‘l’ or ‘r’ for short)

OUTPUT:

– a label

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c d','b d a c')
sage: p.rauzy_move_winner('top','right')
'd'
sage: p.rauzy_move_winner('bottom','right')
'c'
sage: p.rauzy_move_winner('top','left')
'a'
sage: p.rauzy_move_winner('bottom','left')
'b'
sage: p = iet.GeneralizedPermutation('a b b c','d c a e d e')
sage: p.rauzy_move_winner('top','right')
'c'
sage: p.rauzy_move_winner('bottom','right')
'e'
sage: p.rauzy_move_winner('top','left')
'a'
sage: p.rauzy_move_winner('bottom','left')
'd'
class surface_dynamics.interval_exchanges.labelled.LabelledPermutationIET(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.labelled.LabelledPermutation, surface_dynamics.interval_exchanges.template.OrientablePermutationIET

Labelled permutation for iet

EXAMPLES:

sage: from surface_dynamics import *

Reducibility testing:

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

sage: q = iet.Permutation('a b c d', 'b a d c')
sage: q.is_irreducible()
False

Rauzy movability and Rauzy move:

sage: p = iet.Permutation('a b c', 'c b a')
sage: p.has_rauzy_move('top')
True
sage: p.rauzy_move('bottom')
a c b
c b a
sage: p.has_rauzy_move('top')
True
sage: p.rauzy_move('top')
a b c
c a b

Rauzy diagram:

sage: p = iet.Permutation('a b c', 'c b a')
sage: d = p.rauzy_diagram()
sage: p in d
True
heights_cone(side=None)[source]

Return the cone of heights data.

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b c d', 'd c b a')
sage: C = p.heights_cone()
sage: C
A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex and 5 rays
sage: C.rays_list()
[[0, 0, 1, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

sage: p.heights_cone('top').rays_list()
[[0, 0, 1, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 0, 0]]
sage: p.heights_cone('bot').rays_list()
[[0, 0, 1, 1], [0, 1, 1, 0], [1, 1, 0, 0], [1, 1, 1, 0]]
lyapunov_exponents_approx(nb_vectors=None, nb_experiments=10, nb_iterations=65536, return_speed=False, verbose=False, output_file=None)[source]

Return approximate Lyapunov exponents of the KZ-cocycle.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation([1,2,3],[3,2,1])
sage: p.lyapunov_exponents_approx()  # abs tol .05
[1.000]
rauzy_diagram(**args)[source]

Returns the associated Rauzy diagram.

For more information try help(iet.RauzyDiagram).

OUTPUT:

Rauzy diagram – the Rauzy diagram of the permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c', 'c b a')
sage: d = p.rauzy_diagram()
rauzy_move_interval_substitution(winner=None, side=None)[source]

Returns the interval substitution associated.

INPUT:

  • winner - the winner interval (‘top’ or ‘bottom’)
  • side - (default: ‘right’) the side (‘left’ or ‘right’)

OUTPUT:

WordMorphism – a substitution on the alphabet of the permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: print(p.rauzy_move_interval_substitution('top','right'))
a->a, b->ba
sage: print(p.rauzy_move_interval_substitution('bottom','right'))
a->ab, b->b
sage: print(p.rauzy_move_interval_substitution('top','left'))
a->ba, b->b
sage: print(p.rauzy_move_interval_substitution('bottom','left'))
a->a, b->ab
rauzy_move_orbit_substitution(winner=None, side=None)[source]

Return the action fo the rauzy_move on the orbit.

INPUT:

  • i - integer
  • winner - the winner interval (‘top’ or ‘bottom’)
  • side - (default: ‘right’) the side (‘right’ or ‘left’)

OUTPUT:

WordMorphism – a substitution on the alphabet of self

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: print(p.rauzy_move_orbit_substitution('top','right'))
a->ab, b->b
sage: print(p.rauzy_move_orbit_substitution('bottom','right'))
a->a, b->ab
sage: print(p.rauzy_move_orbit_substitution('top','left'))
a->a, b->ba
sage: print(p.rauzy_move_orbit_substitution('bottom','left'))
a->ba, b->b

TESTS:

sage: p = iet.Permutation('a1 a2', 'a2 a1')
sage: p.rauzy_move_orbit_substitution('top','right').codomain().alphabet()
{'a1', 'a2'}
reduced()[source]

Returns the associated reduced abelian permutation.

OUTPUT:

a reduced permutation – the underlying reduced permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation(“a b c d”,”d c a b”) sage: q = iet.Permutation(“a b c d”,”d c a b”,reduced=True) sage: p.reduced() == q True

suspension_cone(winner=None)[source]

Return the cone of suspension data.

A suspension data tau for a permutation (pi_{top}, pi_{bot}) on the alphabet mathcal{A} is a real vector in RR^mathcal{A} so that

\[\forall 1 \leq k < d,\, \sum_{\beta: \pi_{top}(\beta) \leq k} \tau_\beta > 0 \quad \text{and} \quad \sum_{\beta: \pi_{bot}(\beta) \leq k} \tau_\beta < 0.\]

A suspension data determines half of a zippered rectangle construction. The other half is the length data that is a positive vector in RR^mathcal{A}.

INPUT:

  • winner - (optional) either None, "top" or "bottom". If not None , then return only half of the suspension cone corresponding to data that either comes from a top or bottom Rauzy induction.

See also

heights_cone()

EXAMPLES:

sage: from surface_dynamics import *
sage: p = iet.Permutation('a b c d e f', 'e c b f d a')
sage: H = p.suspension_cone()
sage: H.dimension()
6
sage: rays = [r.vector() for r in H.rays()]
sage: r = sum(randint(1,5)*ray for ray in rays)
sage: r[0]>0 and r[0]+r[1] > 0 and r[0]+r[1]+r[2] > 0
True
sage: r[0]+r[1]+r[2]+r[3]>0
True
sage: r[0]+r[1]+r[2]+r[3]+r[4]>0
True
sage: r[4]<0 and r[4]+r[2]<0 and r[4]+r[2]+r[1] < 0
True
sage: r[4]+r[2]+r[1]+r[5]<0
True
sage: r[4]+r[2]+r[1]+r[5]+r[3]<0
True
class surface_dynamics.interval_exchanges.labelled.LabelledPermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)[source]

Bases: surface_dynamics.interval_exchanges.labelled.LabelledPermutation, surface_dynamics.interval_exchanges.template.OrientablePermutationLI

Labelled quadratic (or generalized) permutation

EXAMPLES:

sage: from surface_dynamics import *

Reducibility testing:

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

Reducibility testing with associated decomposition:

sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c')
sage: p.is_irreducible()
False
sage: test, decomposition = p.is_irreducible(return_decomposition = True)
sage: test
False
sage: decomposition
(['a'], ['c', 'a'], [], ['c'])

Rauzy movability and Rauzy move:

sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d')
sage: p.has_rauzy_move(0)
False
sage: p.has_rauzy_move(1)
True
sage: q = p.rauzy_move(1)
sage: q
a a b b c
c d d
sage: q.has_rauzy_move(0)
True
sage: q.has_rauzy_move(1)
True

Rauzy diagrams:

sage: p = iet.GeneralizedPermutation('0 0 1 1','2 2')
sage: r = p.rauzy_diagram()
sage: p in r
True
has_right_rauzy_move(winner)[source]

Test of Rauzy movability with a specified winner)

A quadratic (or generalized) permutation is rauzy_movable type depending on the possible length of the last interval. It’s dependent of the length equation.

INPUT:

  • winner - ‘top’ (or ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)

OUTPUT:

bool – True if self has a Rauzy move

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a','b b')
sage: p.has_right_rauzy_move('top')
False
sage: p.has_right_rauzy_move('bottom')
False
sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.has_right_rauzy_move('top')
True
sage: p.has_right_rauzy_move('bottom')
True
sage: p = iet.GeneralizedPermutation('a a','b b c c')
sage: p.has_right_rauzy_move('top')
True
sage: p.has_right_rauzy_move('bottom')
False
sage: p = iet.GeneralizedPermutation('a a b b','c c')
sage: p.has_right_rauzy_move('top')
False
sage: p.has_right_rauzy_move('bottom')
True
left_rauzy_move(winner)[source]

Perform a Rauzy move on the left.

INPUT:

  • winner - ‘top’ or ‘bottom’

OUTPUT:

permutation – the Rauzy move of self

EXAMPLES:

sage: from surface_dynamics import *

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

TESTS:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: q = p.top_bottom_inverse()
sage: q = q.left_rauzy_move(0)
sage: q = q.top_bottom_inverse()
sage: q == p.left_rauzy_move(1)
True
sage: q = p.top_bottom_inverse()
sage: q = q.left_rauzy_move(1)
sage: q = q.top_bottom_inverse()
sage: q == p.left_rauzy_move(0)
True
sage: q = p.left_right_inverse()
sage: q = q.right_rauzy_move(0)
sage: q = q.left_right_inverse()
sage: q == p.left_rauzy_move(0)
True
sage: q = p.left_right_inverse()
sage: q = q.right_rauzy_move(1)
sage: q = q.left_right_inverse()
sage: q == p.left_rauzy_move(1)
True
lyapunov_exponents_H_minus(nb_vectors=None, nb_experiments=10, nb_iterations=65536, return_speed=False, verbose=False, output_file=None)[source]

Compute the H^+ Lyapunov exponents of the stratum associated to this permutation.

This method calls a C library. It might be significantly faster if nb_vectors=1 (or if it is not provided but genus is 1).

INPUT:

  • nb_vectors – the number of exponents to compute. The number of vectors must not exceed the dimension of the space!
  • nb_experiments – the number of experiments to perform. It might be around 100 (default value) in order that the estimation of confidence interval is accurate enough.
  • nb_iterations – the number of iteration of the Rauzy-Zorich algorithm to perform for each experiments. The default is 2^15=32768 which is rather small but provide a good compromise between speed and quality of approximation.
  • verbose – if True provide additional informations rather than returning only the Lyapunov exponents (i.e. ellapsed time, confidence intervals, …)
  • output_file – if provided (as a file object or a string) output the additional information in the given file rather than on the standard output.

EXAMPLES:

sage: from surface_dynamics import *
sage: Q = QuadraticStratum([1,1,-1,-1]).unique_component()
sage: p = Q.permutation_representative(reduced=False)
sage: p.lyapunov_exponents_H_minus() # abs tol .05
[1.000, 0.333]

sage: Q_reg = QuadraticStratum([12]).regular_component()
sage: p_reg = Q_reg.permutation_representative(reduced=False)
sage: p_reg.lyapunov_exponents_H_minus() # abs tol .05
[1.000, 0.310, 0.120]
sage: sum(_)  # abs tol .05
1.430

sage: Q_irr = QuadraticStratum([12]).irregular_component()
sage: p_irr = Q_irr.permutation_representative(reduced=False)
sage: p_irr.lyapunov_exponents_H_minus() # abs tol .05
[1.000, 0.444, 0.128]
sage: sum(_) # abs tol .05
1.5725
lyapunov_exponents_H_plus(nb_vectors=None, nb_experiments=10, nb_iterations=65536, return_speed=False, verbose=False, output_file=None)[source]

Compute the H^+ Lyapunov exponents of the stratum associated to this permutation.

This method calls a C library. It might be significantly faster if nb_vectors=1 (or if it is not provided but genus is 1).

INPUT:

  • nb_vectors – the number of exponents to compute. The number of vectors must not exceed the dimension of the space!
  • nb_experiments – the number of experiments to perform. It might be around 100 (default value) in order that the estimation of confidence interval is accurate enough.
  • nb_iterations – the number of iteration of the Rauzy-Zorich algorithm to perform for each experiments. The default is 2^15=32768 which is rather small but provide a good compromise between speed and quality of approximation.
  • verbose – if True provide additional informations rather than returning only the Lyapunov exponents (i.e. ellapsed time, confidence intervals, …)
  • output_file – if provided (as a file object or a string) output the additional information in the given file rather than on the standard output.

EXAMPLES:

sage: from surface_dynamics import *
sage: Q = QuadraticStratum([1,1,-1,-1]).unique_component()
sage: p = Q.permutation_representative(reduced=False)
sage: p.lyapunov_exponents_H_plus() # abs tol .05
[0.6666]

sage: Q_reg = QuadraticStratum([12]).regular_component()
sage: p_reg = Q_reg.permutation_representative(reduced=False)
sage: p_reg.lyapunov_exponents_H_plus() # abs tol .05
[0.662, 0.448, 0.230, 0.087]
sage: sum(_)  # abs tol .05
1.43

sage: Q_irr = QuadraticStratum([12]).irregular_component()
sage: p_irr = Q_irr.permutation_representative(reduced=False)
sage: p_irr.lyapunov_exponents_H_plus() # abs tol .05
[0.747, 0.491, 0.245, 0.090]
sage: sum(_) # abs tol .05
1.5727
rauzy_diagram(**kargs)[source]

Returns the associated RauzyDiagram.

OUTPUT:

Rauzy diagram – the Rauzy diagram of the permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a b c b', 'c d d a')
sage: d = p.rauzy_diagram()
sage: p in d
True

For more information, try help(iet.RauzyDiagram)

reduced()[source]

Returns the associated reduced quadratic permutations.

OUTPUT:

permutation – the underlying reduced permutation

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.GeneralizedPermutation('a a','b b c c')
sage: q = p.reduced()
sage: q
a a
b b c c
sage: p.rauzy_move(0).reduced() == q.rauzy_move(0)
True
right_rauzy_move(winner)[source]

Perform a Rauzy move on the right (the standard one).

INPUT:

  • winner - ‘top’ (or ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)

OUTPUT:

boolean – True if self has a Rauzy move

EXAMPLES:

sage: from surface_dynamics import *

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

TESTS:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: q = p.top_bottom_inverse()
sage: q = q.right_rauzy_move(0)
sage: q = q.top_bottom_inverse()
sage: q == p.right_rauzy_move(1)
True
sage: q = p.top_bottom_inverse()
sage: q = q.right_rauzy_move(1)
sage: q = q.top_bottom_inverse()
sage: q == p.right_rauzy_move(0)
True
sage: p = p.left_right_inverse()
sage: q = q.left_rauzy_move(0)
sage: q = q.left_right_inverse()
sage: q == p.right_rauzy_move(0)
True
sage: q = p.left_right_inverse()
sage: q = q.left_rauzy_move(1)
sage: q = q.left_right_inverse()
sage: q == p.right_rauzy_move(1)
True
surface_dynamics.interval_exchanges.labelled.LabelledPermutationsIET_iterator(nintervals=None, irreducible=True, alphabet=None)[source]

Returns an iterator over labelled permutations.

INPUT:

  • nintervals - integer or None
  • irreducible - boolean (default: True)
  • alphabet - something that should be converted to an alphabet of at least nintervals letters

OUTPUT:

iterator – an iterator over permutations

TESTS:

sage: from surface_dynamics import *

sage: for p in iet.Permutations_iterator(2, alphabet="ab"):
....:     print("%s\n****" % p)  #indirect doctest
a b
b a
****
b a
a b
****
sage: for p in iet.Permutations_iterator(3, alphabet="abc"):
....:     print("%s\n*****" %p)   #indirect doctest
a b c
b c a
*****
a b c
c a b
*****
a b c
c b a
*****
a c b
b a c
*****
a c b
b c a
*****
a c b
c b a
*****
b a c
a c b
*****
b a c
c a b
*****
b a c
c b a
*****
b c a
a b c
*****
b c a
a c b
*****
b c a
c a b
*****
c a b
a b c
*****
c a b
b a c
*****
c a b
b c a
*****
c b a
a b c
*****
c b a
a c b
*****
c b a
b a c
*****
class surface_dynamics.interval_exchanges.labelled.LabelledRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)[source]

Bases: surface_dynamics.interval_exchanges.template.RauzyDiagram

Template for Rauzy diagrams of labelled permutations.

…DO NOT USE…
Path[source]

alias of LabelledRauzyDiagram.Path

edge_to_interval_substitution(p=None, edge_type=None)[source]

Returns the interval substitution associated to an edge

OUTPUT:

WordMorphism – the WordMorphism corresponding to the edge

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: print(r.edge_to_interval_substitution(None,None))
a->a, b->b, c->c
sage: print(r.edge_to_interval_substitution(p,0))
a->a, b->b, c->ca
sage: print(r.edge_to_interval_substitution(p,1))
a->ac, b->b, c->c
edge_to_orbit_substitution(p=None, edge_type=None)[source]

Returns the interval substitution associated to an edge

OUTPUT:

WordMorphism – the word morphism corresponding to the edge

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: print(r.edge_to_orbit_substitution(None,None))
a->a, b->b, c->c
sage: print(r.edge_to_orbit_substitution(p,0))
a->ac, b->b, c->c
sage: print(r.edge_to_orbit_substitution(p,1))
a->a, b->b, c->ac

TESTS:

sage: from surface_dynamics import *

sage: pi0 = iet.Permutation('A1 A2 B', 'B A1 A2')
sage: G = pi0.rauzy_diagram()
sage: s1 = G.edge_to_orbit_substitution(pi0,0)
sage: s1.domain().alphabet()
{'A1', 'A2', 'B'}
sage: s1.codomain().alphabet()
{'A1', 'A2', 'B'}
full_loop_iterator(start=None, max_length=1)[source]

Returns an iterator over all full path starting at start.

INPUT:

  • start - the start point
  • max_length - a limit on the length of the paths

OUTPUT:

iterator – iterator over full loops

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: r = p.rauzy_diagram()
sage: for g in r.full_loop_iterator(p,2):
....:     print("%s\n*****" % g.matrix())
[1 1]
[1 2]
*****
[2 1]
[1 1]
*****
full_nloop_iterator(start=None, length=1)[source]

Returns an iterator over all full loops of given length.

INPUT:

  • start - the initial permutation
  • length - the length to consider

OUTPUT:

iterator – an iterator over the full loops of given length

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: d = p.rauzy_diagram()
sage: for g in d.full_nloop_iterator(p,2):
....:     print("%s\n*****" % g.matrix())
[1 1]
[1 2]
*****
[2 1]
[1 1]
*****
LabelledRauzyDiagram.Path[source]

alias of LabelledRauzyDiagram.Path

Cardinality of Rauzy classes

The following functions implement algorithms relative to article [Del2010] and [Boi2010] where are given formulas for the cardinality of Rauzy classes of permutations.

  • c: number of standard labeled permutations
  • d: spin difference of standard labeled permutations
  • gamma_std: number of standard permutations (with given profile and marking)
  • gamma_irr: number of irreducible permutations (with given profile and marking)
  • delta_std: spin difference for standard permutations (with given profile and marking)
  • delta_irr: spin difference for irreducible permutations (with given profile and marking)

AUTHOR:

Vincent Delecroix

REFERENCES:

[Boi2010]Boissy 2010
[Del2010]Delecroix 2010
[Vee1982]W. Veech, “Gauss measures for transformations on the space of interval exchange maps”, Ann. of Math., vol. 115, no. 2 (1982), pp. 201-242.
surface_dynamics.interval_exchanges.rauzy_class_cardinality.bidecompositions(p)[source]

Iterator through the pair of partitions (q1,q2) such that the union of the parts of q1 and q2 equal p.

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
sage: list(rcc.bidecompositions(Partition([3,1])))
[([], [3, 1]), ([3], [1]), ([1], [3]), ([3, 1], [])]
sage: list(rcc.bidecompositions(Partition([2,1,1])))
[([], [2, 1, 1]),
 ([2], [1, 1]),
 ([1], [2, 1]),
 ([2, 1], [1]),
 ([1, 1], [2]),
 ([2, 1, 1], [])]
surface_dynamics.interval_exchanges.rauzy_class_cardinality.c(p)[source]

Number of labeled standard permutations with given profile

There is an explicit formula for this number

\[c(p) = \frac{2 (n-1)!}{n+1} \left( \sum_{q \subset (p_2,p_3,\ldots,p_k)} (-1)^{s(q)-l(q)} \binom{n}{s(q)}^{-1} \right).\]

Though, for huge partition p this is not very useful. This function implements an induction formula to compute c(p).

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

Partition of length 1:

sage: n = 7
sage: rcc.c([n]) == 2 * factorial(n-1) / (n+1)
True
sage: all(rcc.c([n]) == 2 * factorial(n-1) / (n+1) for n in xrange(11,18,2))
True

Partitions of length 2 with two odd numbers:

sage: p = [5,3]
sage: n = sum(p)
sage: b = binomial(n,p[0])
sage: rcc.c(p) == 2 * factorial(n-1) * (1 + 1 / binomial(n,p[0])) / (n+1)
True

sage: p = [13,5]
sage: n = sum(p)
sage: b = binomial(n,p[0])
sage: rcc.c(p) == 2 * factorial(n-1) * (1 + 1 / binomial(n,p[0])) / (n+1)
True

Partitions of length 2 with even numbers:

sage: p = [4,4]
sage: n = sum(p)
sage: b = binomial(n,p[0])
sage: rcc.c(p) == 2 * factorial(n-1) * (1 - 1 / binomial(n,p[0])) / (n+1)
True

sage: p = [10,2]
sage: n = sum(p)
sage: b = binomial(n,p[0])
sage: rcc.c(p) == 2 * factorial(n-1) * (1 - 1 / binomial(n,p[0])) / (n+1)
True

Add marked points to an integer partition:

sage: p = [3,2,2]
sage: n = sum(p)
sage: all(rcc.c(p + [1]*k) == factorial(n+k-1) / factorial(n-1) * rcc.c(p) for k in xrange(1,6))
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.check_marking(p, marking)[source]

Tiny internal function that checks that marking is compatible with p.

OUTPUT:

A 3-tuple.

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
sage: p = Partition([3,2,2])
sage: rcc.check_marking(p, (1,3,1))
(1, 3, 1)
sage: rcc.check_marking(p, (1,3,2))
(1, 3, 2)
sage: rcc.check_marking(p, (1,3,3))
Traceback (most recent call last):
...
ValueError: marking[2] is not good
sage: rcc.check_marking(p, (1,3,-1))
Traceback (most recent call last):
...
ValueError: marking[2] is not good
sage: rcc.check_marking(p, (2,3,2))
(2, 3, 2)
sage: rcc.check_marking(p, (2,3,3))
Traceback (most recent call last):
...
ValueError: wrong marking type 2
surface_dynamics.interval_exchanges.rauzy_class_cardinality.check_std_marking(p, marking)[source]

Tiny internal function that checks the validity of marking on the partition p.

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
sage: p = Partition([3,2,2])
sage: rcc.check_std_marking(p, (1,3,1))
(1, 3, 1)
sage: rcc.check_std_marking(p, (1,3,0))
Traceback (most recent call last):
...
ValueError: marking[2] is not good
surface_dynamics.interval_exchanges.rauzy_class_cardinality.collapse(p, i, j)[source]

Collapses the i-th term and the j-th term of a permutation

INPUT:

  • p - a partition
  • i,j - two different indices of p

OUTPUT:

  • a partition

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
sage: p = Partition([4,2,1])
sage: rcc.collapse(p, 0, 1)
[5, 1]
sage: rcc.collapse(p, 0, 2)
[4, 2]
sage: rcc.collapse(p, 1, 2)
[4, 2]
surface_dynamics.interval_exchanges.rauzy_class_cardinality.d(p)[source]

Difference between the number of odd spin parity and even spin parity standard labeled permutations with given profile

There is an explicit formula

\[d(p) = \frac{(n-1)!}{2^{(n-k)/2}}\]

where n is the sum of the partition p and k is its length.

EXAMPLES:

   sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
   sage: p = [3,3,1]
   sage: rcc.d([3,3,1]) == factorial(6) / 2**2
   True
   sage: rcc.d([13]) == factorial(12) / 2**6
   True

Adding marked points::

   sage: p = [5,3,3]
   sage: n = sum(p)
   sage: all(rcc.d(p + [1]*k) == factorial(n+k-1) / factorial(n-1) * rcc.d(p) for k in xrange(1,6))
   True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.delta_irr(profile, marking=None)[source]

Spin difference for the given profile and marking

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

The non connecte strata in genus 3:

sage: from surface_dynamics import AbelianStratum

sage: c_odd = AbelianStratum(2,2).odd_component()
sage: c_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 294 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 63 permutations
sage: rcc.delta_irr([3,3]) == 294 - 63
True

sage: c_odd = AbelianStratum(4).odd_component()
sage: c_hyp = AbelianStratum(4).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 134 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 31 permutations
sage: rcc.delta_irr([5]) == 134 - 31
True

A non connected strata in genus 4:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rdc
sage: a = AbelianStratum(6)
sage: c_hyp = a.hyperelliptic_component()
sage: c_odd = a.odd_component()
sage: c_even = a.even_component()
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 127 permutations
sage: c_hyp.rauzy_class_cardinality()
127
sage: c_odd.rauzy_diagram()
Rauzy diagram with 5209 permutations
sage: c_odd.rauzy_class_cardinality()
5209
sage: c_even = a.even_component()
sage: c_even.rauzy_diagram()
Rauzy diagram with 2327 permutations
sage: c_even.rauzy_class_cardinality()
2327
sage: 5209 - 2327 - 127
2755
sage: rdc.delta_irr([7])
2755

An example with a very big Rauzy class:

sage: c = AbelianStratum(6,6).odd_component()
sage: c.rauzy_class_cardinality()
11609364656
surface_dynamics.interval_exchanges.rauzy_class_cardinality.delta_std(profile, marking=None)[source]

Return the difference odd-even in the given stratum

INPUT:

  • p - partition with odd terms
  • marking - a 3-tuple (1, n1, a) or (2, n1, n2)

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

A ValueError is raised if the partition does not fullfill the requirement:

sage: rcc.delta_std([5,2])
Traceback (most recent call last):
...
ValueError: the profile (=[5, 2]) must contain only odd numbers

Non connected strata in genus 3 has two connected components distinguished by their spin parity:

sage: from surface_dynamics import AbelianStratum
sage: cc_odd = AbelianStratum(2,2).odd_component()
sage: cc_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 294 permutations
sage: d_hyp
Rauzy diagram with 63 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd - n_hyp == rcc.delta_std([3,3])
True

sage: cc_odd = AbelianStratum(4).odd_component()
sage: cc_hyp = AbelianStratum(4).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 134 permutations
sage: d_hyp
Rauzy diagram with 31 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd - n_hyp == rcc.delta_std([5])
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.gamma_irr(profile=None, marking=None)[source]

Number of permutations for the given profile and marking

INPUT:

  • profile - an integer partition such that its sum plus its length is congruent to 0 modulo 2
  • markings - None, an element of the profile or a 3-tuple

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

The connected strata in genus 3:

sage: from surface_dynamics import AbelianStratum

sage: c = AbelianStratum(1,1,1,1).unique_component()
sage: c.rauzy_diagram()
Rauzy diagram with 1255 permutations
sage: rcc.gamma_irr([2,2,2,2])
1255

sage: c = AbelianStratum(2,1,1).unique_component()
sage: c.rauzy_diagram()
Rauzy diagram with 2177 permutations
sage: rcc.gamma_irr([3,2,2])
2177

sage: c = AbelianStratum(3,1).unique_component()
sage: c.rauzy_diagram()
Rauzy diagram with 770 permutations
sage: rcc.gamma_irr([4,2])
770

The non connecte strata in genus 3:

sage: c_odd = AbelianStratum(2,2).odd_component()
sage: c_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 294 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 63 permutations
sage: rcc.gamma_irr([3,3]) == 294 + 63
True

sage: c_odd = AbelianStratum(4).odd_component()
sage: c_hyp = AbelianStratum(4).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 134 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 31 permutations
sage: rcc.gamma_irr([5]) == 134 + 31
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.gamma_std(profile, marking=None)[source]

Return the number of standard permutations of given profile

INPUT:

  • profile - an integer partition such that the its sum plus its length is congruent to 0 modulo 2
  • marking - either None, an element of the profile or a 3-tuple (1, n1, a) or (2, n1, n2)

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

A ValueError is raised if the partition does not satisfy the requirement:

sage: rcc.gamma_std([5,2])
Traceback (most recent call last):
...
ValueError: the sum of the profile (=[5, 2]) plus its length must be congruent to 0 modulo 2

The Rauzy classes associated to connected strata in genus 3:

sage: from surface_dynamics import AbelianStratum
sage: cc = AbelianStratum(1,1,1,1).unique_component()
sage: d = cc.rauzy_diagram()
sage: d
Rauzy diagram with 1255 permutations
sage: len(filter(lambda x: x.is_standard(), d)) == rcc.gamma_std([2,2,2,2])
True

sage: cc = AbelianStratum(2,1,1).unique_component()
sage: d = cc.rauzy_diagram()
sage: d
Rauzy diagram with 2177 permutations
sage: len(filter(lambda x: x.is_standard(), d)) == rcc.gamma_std([3,2,2])
True

sage: cc = AbelianStratum(3,1).unique_component()
sage: d = cc.rauzy_diagram()
sage: d
Rauzy diagram with 770 permutations
sage: len(filter(lambda x: x.is_standard(), d)) == rcc.gamma_std([4,2])
True

The non connected strata in genus 3:

sage: cc_odd = AbelianStratum(2,2).odd_component()
sage: cc_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 294 permutations
sage: d_hyp
Rauzy diagram with 63 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd + n_hyp == rcc.gamma_std([3,3])
True

sage: cc_odd = AbelianStratum(4).odd_component()
sage: cc_hyp = AbelianStratum(4).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 134 permutations
sage: d_hyp
Rauzy diagram with 31 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd + n_hyp == rcc.gamma_std([5])
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.marking_iterator(profile, left=None, standard=False)[source]

Returns the marked profile associated to a partition

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
sage: p = Partition([3,2,2])
sage: list(rcc.marking_iterator(p))
[(1, 2, 0),
 (1, 2, 1),
 (1, 3, 0),
 (1, 3, 1),
 (1, 3, 2),
 (2, 2, 2),
 (2, 2, 3),
 (2, 3, 2)]
surface_dynamics.interval_exchanges.rauzy_class_cardinality.number_of_irreducible_permutations(profile=None, marking=None)

Number of permutations for the given profile and marking

INPUT:

  • profile - an integer partition such that its sum plus its length is congruent to 0 modulo 2
  • markings - None, an element of the profile or a 3-tuple

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

The connected strata in genus 3:

sage: from surface_dynamics import AbelianStratum

sage: c = AbelianStratum(1,1,1,1).unique_component()
sage: c.rauzy_diagram()
Rauzy diagram with 1255 permutations
sage: rcc.gamma_irr([2,2,2,2])
1255

sage: c = AbelianStratum(2,1,1).unique_component()
sage: c.rauzy_diagram()
Rauzy diagram with 2177 permutations
sage: rcc.gamma_irr([3,2,2])
2177

sage: c = AbelianStratum(3,1).unique_component()
sage: c.rauzy_diagram()
Rauzy diagram with 770 permutations
sage: rcc.gamma_irr([4,2])
770

The non connecte strata in genus 3:

sage: c_odd = AbelianStratum(2,2).odd_component()
sage: c_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 294 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 63 permutations
sage: rcc.gamma_irr([3,3]) == 294 + 63
True

sage: c_odd = AbelianStratum(4).odd_component()
sage: c_hyp = AbelianStratum(4).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 134 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 31 permutations
sage: rcc.gamma_irr([5]) == 134 + 31
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.number_of_standard_permutations(profile, marking=None)

Return the number of standard permutations of given profile

INPUT:

  • profile - an integer partition such that the its sum plus its length is congruent to 0 modulo 2
  • marking - either None, an element of the profile or a 3-tuple (1, n1, a) or (2, n1, n2)

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

A ValueError is raised if the partition does not satisfy the requirement:

sage: rcc.gamma_std([5,2])
Traceback (most recent call last):
...
ValueError: the sum of the profile (=[5, 2]) plus its length must be congruent to 0 modulo 2

The Rauzy classes associated to connected strata in genus 3:

sage: from surface_dynamics import AbelianStratum
sage: cc = AbelianStratum(1,1,1,1).unique_component()
sage: d = cc.rauzy_diagram()
sage: d
Rauzy diagram with 1255 permutations
sage: len(filter(lambda x: x.is_standard(), d)) == rcc.gamma_std([2,2,2,2])
True

sage: cc = AbelianStratum(2,1,1).unique_component()
sage: d = cc.rauzy_diagram()
sage: d
Rauzy diagram with 2177 permutations
sage: len(filter(lambda x: x.is_standard(), d)) == rcc.gamma_std([3,2,2])
True

sage: cc = AbelianStratum(3,1).unique_component()
sage: d = cc.rauzy_diagram()
sage: d
Rauzy diagram with 770 permutations
sage: len(filter(lambda x: x.is_standard(), d)) == rcc.gamma_std([4,2])
True

The non connected strata in genus 3:

sage: cc_odd = AbelianStratum(2,2).odd_component()
sage: cc_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 294 permutations
sage: d_hyp
Rauzy diagram with 63 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd + n_hyp == rcc.gamma_std([3,3])
True

sage: cc_odd = AbelianStratum(4).odd_component()
sage: cc_hyp = AbelianStratum(4).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 134 permutations
sage: d_hyp
Rauzy diagram with 31 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd + n_hyp == rcc.gamma_std([5])
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.spin_difference_for_irreducible_permutations(profile, marking=None)

Spin difference for the given profile and marking

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

The non connecte strata in genus 3:

sage: from surface_dynamics import AbelianStratum

sage: c_odd = AbelianStratum(2,2).odd_component()
sage: c_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 294 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 63 permutations
sage: rcc.delta_irr([3,3]) == 294 - 63
True

sage: c_odd = AbelianStratum(4).odd_component()
sage: c_hyp = AbelianStratum(4).hyperelliptic_component()
sage: c_odd.rauzy_diagram()
Rauzy diagram with 134 permutations
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 31 permutations
sage: rcc.delta_irr([5]) == 134 - 31
True

A non connected strata in genus 4:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rdc
sage: a = AbelianStratum(6)
sage: c_hyp = a.hyperelliptic_component()
sage: c_odd = a.odd_component()
sage: c_even = a.even_component()
sage: c_hyp.rauzy_diagram()
Rauzy diagram with 127 permutations
sage: c_hyp.rauzy_class_cardinality()
127
sage: c_odd.rauzy_diagram()
Rauzy diagram with 5209 permutations
sage: c_odd.rauzy_class_cardinality()
5209
sage: c_even = a.even_component()
sage: c_even.rauzy_diagram()
Rauzy diagram with 2327 permutations
sage: c_even.rauzy_class_cardinality()
2327
sage: 5209 - 2327 - 127
2755
sage: rdc.delta_irr([7])
2755

An example with a very big Rauzy class:

sage: c = AbelianStratum(6,6).odd_component()
sage: c.rauzy_class_cardinality()
11609364656
surface_dynamics.interval_exchanges.rauzy_class_cardinality.spin_difference_for_standard_permutations(profile, marking=None)

Return the difference odd-even in the given stratum

INPUT:

  • p - partition with odd terms
  • marking - a 3-tuple (1, n1, a) or (2, n1, n2)

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc

A ValueError is raised if the partition does not fullfill the requirement:

sage: rcc.delta_std([5,2])
Traceback (most recent call last):
...
ValueError: the profile (=[5, 2]) must contain only odd numbers

Non connected strata in genus 3 has two connected components distinguished by their spin parity:

sage: from surface_dynamics import AbelianStratum
sage: cc_odd = AbelianStratum(2,2).odd_component()
sage: cc_hyp = AbelianStratum(2,2).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 294 permutations
sage: d_hyp
Rauzy diagram with 63 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd - n_hyp == rcc.delta_std([3,3])
True

sage: cc_odd = AbelianStratum(4).odd_component()
sage: cc_hyp = AbelianStratum(4).hyperelliptic_component()
sage: d_odd = cc_odd.rauzy_diagram()
sage: d_hyp = cc_hyp.rauzy_diagram()
sage: d_odd
Rauzy diagram with 134 permutations
sage: d_hyp
Rauzy diagram with 31 permutations
sage: n_odd = len(filter(lambda x: x.is_standard(), d_odd))
sage: n_hyp = len(filter(lambda x: x.is_standard(), d_hyp))
sage: n_odd - n_hyp == rcc.delta_std([5])
True
surface_dynamics.interval_exchanges.rauzy_class_cardinality.split(p, k, i=0)[source]

Splits the i-th term of p into two parts of size k and n-k-1

There is a symmetry split(p, k, i) = split(p, p[i]-k-1, i)

INPUT:

  • p - a partition
  • k - an integer between 2 and p[i]
  • i - integer - the index of the element to split

OUTPUT: a partition

EXAMPLES:

sage: import surface_dynamics.interval_exchanges.rauzy_class_cardinality as rcc
sage: p = Partition([5,1])
sage: rcc.split(p,1,0)
[3, 1, 1]
sage: rcc.split(p,2,0)
[2, 2, 1]
sage: rcc.split(p,3,0)
[3, 1, 1]

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 iet.RauzyGraph()) 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 defaut, 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

REFERENCES:

[BL08](1, 2) Corentin Boissy and Erwan Lanneau, “Dynamics and geometry of the Rauzy-Veech induction for quadratic differentials” (arxiv:0710.5614) to appear in Ergodic Theory and Dynamical Systems
[DN90]Claude Danthony and Arnaldo Nogueira “Measured foliations on nonorientable surfaces”, Annales scientifiques de l’Ecole Normale Superieure, Ser. 4, 23, no. 3 (1990) p 469-494
[N85]Arnaldo Nogueira, “Almost all Interval Exchange Transformations with Flips are Nonergodic” (Ergod. Th. & Dyn. Systems, Vol 5., (1985), 257-271
[R79](1, 2) Gerard Rauzy, “Echanges d’intervalles et transformations induites”, Acta Arith. 34, no. 3, 203-212, 1980
[V78]William Veech, “Interval exchange transformations”, J. Analyse Math. 33, 222-272
[Z]Anton Zorich, “Generalized Permutation software” (http://perso.univ-rennes1.fr/anton.zorich)

AUTHORS:

  • Vincent Delecroix (2009-09-29): initial version
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 [DN90]. The full combinatoric study and precise links with strata of quadratic differentials was achieved few years later by Boissy-Lanneau [BL08].

INPUT:

  • intervals - strings, list, tuples
  • reduced - boolean (defaut: 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

TESTS:

sage: type(iet.GeneralizedPermutation('a b b', 'c c a', reduced=True))
<class 'surface_dynamics.interval_exchanges.reduced.ReducedPermutationLI'>
sage: type(iet.GeneralizedPermutation('a b b', 'c c a', reduced=False))
<class 'surface_dynamics.interval_exchanges.labelled.LabelledPermutationLI'>
sage: type(iet.GeneralizedPermutation('a b b', 'c c a', reduced=True, flips=['a','b']))
<class 'surface_dynamics.interval_exchanges.reduced.FlippedReducedPermutationLI'>
sage: type(iet.GeneralizedPermutation('a b b', 'c c a', reduced=False, flips=['a','b']))
<class 'surface_dynamics.interval_exchanges.labelled.FlippedLabelledPermutationLI'>
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 datas. 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 dictionnary 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 datas. 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 dictionnary 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 [R79] and William Veech [V78].

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 strata)

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 different:

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
False
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

TESTS:

sage: type(iet.Permutation('a b c', 'c b a', reduced=True))
<class 'surface_dynamics.interval_exchanges.reduced.ReducedPermutationIET'>
sage: type(iet.Permutation('a b c', 'c b a', reduced=False))
<class 'surface_dynamics.interval_exchanges.labelled.LabelledPermutationIET'>
sage: type(iet.Permutation('a b c', 'c b a', reduced=True, flips=['a','b']))
<class 'surface_dynamics.interval_exchanges.reduced.FlippedReducedPermutationIET'>
sage: type(iet.Permutation('a b c', 'c b a', reduced=False, flips=['a','b']))
<class 'surface_dynamics.interval_exchanges.labelled.FlippedLabelledPermutationIET'>

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

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

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

sage: p = iet.Permutation('a b c','c b a',reduced=True)
sage: iet.Permutation(p) == p
True
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 strata 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(*args, **kwds)[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 [R79].

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

Interval exchange transformations

Interval Exchange Transformations and Linear Involution

An interval exchage 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])
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 positive
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 with defining polynomial x^2 - 2
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]
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

TESTS:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[1,1,1])
sage: t.in_which_interval(0)
'a'
sage: t.in_which_interval(0.3)
'a'
sage: t.in_which_interval(1)
'b'
sage: t.in_which_interval(1.9)
'b'
sage: t.in_which_interval(2)
'c'
sage: t.in_which_interval(2.1)
'c'
sage: t.in_which_interval(3)
Traceback (most recent call last):
...
ValueError: your value does not lie in [0; 3[
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()[source]

Returns the total length of the interval.

OUTPUT:

real – the length of the interval

EXAMPLES:

sage: from surface_dynamics import *

sage: t = iet.IntervalExchangeTransformation(('a b','b a'),[1,1])
sage: t.length()
2
lengths()[source]

Returns 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 (defaut), center or right
  • labels - boolean (defaut: 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()  # not tested (problem with matplotlib font cache)
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 (defaut), center or right
  • labels - boolean (defaut: 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()  # not tested (problem with matplotlib font cache)
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:

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)
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