Flip sequences

Flip sequence of permutation of iet

A concatenation of: - left rauzy moves (top or bottom) - right rauzy moves (top or bottom) - left_right_inverse, top_bottom_inverse, symmetric - relabeled

class surface_dynamics.interval_exchanges.flip_sequence.IETFlipSequence(p, rauzy_moves=None, top_bottom_inverse=False, left_right_inverse=False, relabelling=None)

Bases: SageObject

A flip sequence of interval exchange transformations.

Each step is a Rauzy move either on the left or on the right.

EXAMPLES:

sage: from surface_dynamics import iet

Making substitutions from a flip sequence:

sage: p = iet.Permutation([['a','b','c','d'],['d','c','b','a']])
sage: g = iet.FlipSequence(p, 'ttbtbbtb')
sage: assert g.is_complete()
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

If large powers appear in the path it might be more convenient to use power notations as in the following example:

sage: p = iet.Permutation([['a','b','c','d'],['d','c','b','a']])
sage: fs = iet.FlipSequence(p, 't^5b^3tbt^3b')
sage: fs == iet.FlipSequence(p, 'tttttbbbtbtttb')
True

The minimal dilatations in H(2g-2)^hyp from Boissy-Lanneau:

sage: def gamma(n, k):
....:     p = iet.Permutation(list(range(n)), list(range(n-1,-1,-1)))
....:     for _ in range(k): p.rauzy_move('t', inplace=True)
....:     f = iet.FlipSequence(p, ['b'] * (n-1-k) + ['t'] * (n-1-2*k), True, True)
....:     f.close()
....:     assert f.is_complete()
....:     return f

sage: x = polygen(QQ)
sage: gamma(4, 1).matrix().charpoly()
x^4 - x^3 - x^2 - x + 1
sage: gamma(6, 1).matrix().charpoly()
x^6 - x^5 - x^4 - x^3 - x^2 - x + 1
sage: gamma(6, 2).matrix().charpoly()
x^6 - x^5 - x^4 + x^3 - x^2 - x + 1
sage: gamma(8, 1).matrix().charpoly()
x^8 - x^7 - x^6 - x^5 - x^4 - x^3 - x^2 - x + 1
sage: gamma(8, 2).matrix().charpoly()
x^8 - x^7 - x^6 - x^5 + x^4 - x^3 - x^2 - x + 1
sage: gamma(8, 3).matrix().charpoly()
x^8 - x^7 - x^6 + x^5 - x^4 + x^3 - x^2 - x + 1

The path of non-orientable flipped iet from [BasLop] that gives non-uniquely ergodic examples. Since IETFlipSequence uses labelled permutations, the path needs a relabelling to be closed:

sage: p0 = iet.Permutation([1,2,3,4,5,6,7,8,9,10], [9,10,1,2,3,4,5,6,7,8], flips=[1,2,3,4,5,6,7,10])
sage: fs1 = iet.FlipSequence(p0, 't^7btbbtbtbtb')
sage: p16 = fs1.end()
sage: fs2 = iet.FlipSequence(p16, 'b')
sage: assert fs2.is_closed()
sage: fs3 = iet.FlipSequence(p16, 'tb^2t^3b^4t^5b^5')
sage: p37 = fs3.end()
sage: fs4 = iet.FlipSequence(p37, 't')
sage: assert fs4.is_closed()
sage: fs5 = iet.FlipSequence(p37, 'bt^7btb')
sage: p49 = fs5.end()
sage: assert p49.reduced() == p0.reduced()
sage: fs6 = iet.FlipSequence(p49, [], relabelling=[7,1,2,3,4,5,6,9,8,0])
sage: assert fs6.end() == p0
sage: (fs1 * fs2 * fs3 * fs4 * fs5 * fs6).matrix()
[ 2  2  2  2  2  2  2  2  3  2]
[ 2  4  2  2  2  2  1  0  0  0]
[ 0  0  2  2  2  1  0  0  0  0]
[ 0  0  0  3  2  0  0  0  0  0]
[ 0  0  1  2  2  0  0  0  0  0]
[ 1  2  2  2  2  2  0  0  0  0]
[ 2  3  2  2  2  2  2  0  0  0]
[ 0  0  0  0  0  0  0  1  1  1]
[ 1  1  1  1  1  1  1  1  2  1]
[ 6 10 10 14 13  8  4  2  3  3]

A symbolic matrix (with polynomial coefficients) where powers of the paths fs2 and fs4 are variables can be obtained with the function symbolic_matrix_power:

sage: from surface_dynamics.misc.linalg import symbolic_matrix_power
sage: QQrs = QQ['r,s']
sage: m1 = fs1.matrix()
sage: m2 = symbolic_matrix_power(fs2.matrix(), QQrs.gen(0))
sage: m3 = fs3.matrix()
sage: m4 = symbolic_matrix_power(fs4.matrix(), QQrs.gen(1))
sage: m5 = fs5.matrix()
sage: m6 = fs6.matrix()
sage: print(m1 * m2 * m3 * m4 * m5 * m6)
[      2       2       2       2       2       2       2       2       3       2]
[    2*s 2*s + 2       2       2       2       2       1       0       0       0]
[      0       0       2       2       2       1       0       0       0       0]
[      0       0       0   r + 2   r + 1       0       0       0       0       0]
[      0       0       1       2       2       0       0       0       0       0]
[      s   s + 1       2       2       2       2       0       0       0       0]
[  s + 1   s + 2       2       2       2       2       2       0       0       0]
[      0       0       0       0       0       0       0       1       1       1]
[      1       1       1       1       1       1       1       1       2       1]
[4*s + 2 4*s + 6      10  r + 13  r + 12       8       4       2       3       3]

close()

Close this path with the unique relabelling that identifies its end to its start.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b c d e f', 'f e d c b a')
sage: q = p.rauzy_move('t').rauzy_move('b').rauzy_move('t')
sage: f = iet.FlipSequence(q, ['t', 't', 'b', 'b', 'b', 't', 'b', 't'],
....:                      top_bottom_inverse=True,
....:                      left_right_inverse=True)
sage: f.close()
sage: f
FlipSequence('a b f c d e\nf a e b d c', 'ttbbbtbt', top_bottom_inverse=True, left_right_inverse=True, relabelling=(0,2,1,3)(4,5))

dual_substitution(as_plain_list=False)

Return the substitution of intervals.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: p0 = iet.FlipSequence(p, ['t'])
sage: s0 = p0.interval_substitution()
sage: print(s0)
a->a, b->ba
sage: p1 = iet.FlipSequence(p, ['b'])
sage: s1 = p1.interval_substitution()
sage: print(s1)
a->ab, b->b
sage: (p0 * p1).interval_substitution() == s1 * s0
True
sage: (p1 * p0).interval_substitution() == s0 * s1
True

sage: p = iet.Permutation('a b c d', 'd c b a')
sage: f0 = iet.FlipSequence(p, ['t','b','t'], relabelling="(0,1,2)")
sage: f1 = iet.FlipSequence(f0._end, ['b','t','b'], relabelling="(1,3,2)")
sage: f2 = iet.FlipSequence(f1._end, ['t','b','t'], relabelling="(0,3,1,2)")
sage: f = f0 * f1 * f2
sage: f.interval_substitution()
WordMorphism: a->ba, b->cdbadbadbc, c->dbadbcdbadb, d->adbcba
sage: f.interval_substitution(as_plain_list=True)
[[1, 0],
 [2, 3, 1, 0, 3, 1, 0, 3, 1, 2],
 [3, 1, 0, 3, 1, 2, 3, 1, 0, 3, 1],
 [0, 3, 1, 2, 1, 0]]
sage: s0 = f0.interval_substitution()
sage: s1 = f1.interval_substitution()
sage: s2 = f2.interval_substitution()
sage: f.interval_substitution() == s2 * s1 * s0
True

end()

Return the end of the path.

find_closure()

Return the unique permutation of the labels that allows to make a closed loop out of this path. If no such permutation exists, return None.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b c d e f', 'f e d c b a')
sage: q = p.rauzy_move('t').rauzy_move('b').rauzy_move('t')
sage: f = iet.FlipSequence(q, ['t', 't', 'b', 'b', 'b', 't', 'b', 't'],
....:                      top_bottom_inverse=True,
....:                      left_right_inverse=True)
sage: f.find_closure()
[2, 3, 1, 0, 5, 4]

interval_substitution(as_plain_list=False)

Return the substitution of intervals.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: p0 = iet.FlipSequence(p, ['t'])
sage: s0 = p0.interval_substitution()
sage: print(s0)
a->a, b->ba
sage: p1 = iet.FlipSequence(p, ['b'])
sage: s1 = p1.interval_substitution()
sage: print(s1)
a->ab, b->b
sage: (p0 * p1).interval_substitution() == s1 * s0
True
sage: (p1 * p0).interval_substitution() == s0 * s1
True

sage: p = iet.Permutation('a b c d', 'd c b a')
sage: f0 = iet.FlipSequence(p, ['t','b','t'], relabelling="(0,1,2)")
sage: f1 = iet.FlipSequence(f0._end, ['b','t','b'], relabelling="(1,3,2)")
sage: f2 = iet.FlipSequence(f1._end, ['t','b','t'], relabelling="(0,3,1,2)")
sage: f = f0 * f1 * f2
sage: f.interval_substitution()
WordMorphism: a->ba, b->cdbadbadbc, c->dbadbcdbadb, d->adbcba
sage: f.interval_substitution(as_plain_list=True)
[[1, 0],
 [2, 3, 1, 0, 3, 1, 0, 3, 1, 2],
 [3, 1, 0, 3, 1, 2, 3, 1, 0, 3, 1],
 [0, 3, 1, 2, 1, 0]]
sage: s0 = f0.interval_substitution()
sage: s1 = f1.interval_substitution()
sage: s2 = f2.interval_substitution()
sage: f.interval_substitution() == s2 * s1 * s0
True

is_closed()

Return whether the path is closed, that is whether its start and end coincide.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b c d e f', 'f e d c b a')
sage: iet.FlipSequence(p, 't^5').is_closed()
True
sage: iet.FlipSequence(p, 't^4').is_closed()
False

is_complete()

Return whether that all winners appear.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b c d e f', 'f e d c b a')
sage: q = p.rauzy_move('t').rauzy_move('b').rauzy_move('t')
sage: f = iet.FlipSequence(q, ['t', 't', 'b', 'b', 'b', 't', 'b', 't'],
....:                      top_bottom_inverse=True,
....:                      left_right_inverse=True)
sage: f.close()
sage: f.is_complete()
True

is_full()

Return whether that all winners appear.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b c d e f', 'f e d c b a')
sage: q = p.rauzy_move('t').rauzy_move('b').rauzy_move('t')
sage: f = iet.FlipSequence(q, ['t', 't', 'b', 'b', 'b', 't', 'b', 't'],
....:                      top_bottom_inverse=True,
....:                      left_right_inverse=True)
sage: f.close()
sage: f.is_complete()
True

is_loop()

Return whether the path is closed, that is whether its start and end coincide.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b c d e f', 'f e d c b a')
sage: iet.FlipSequence(p, 't^5').is_closed()
True
sage: iet.FlipSequence(p, 't^4').is_closed()
False

left_right_inverse()

losers()

Return the list of the loosers along this flip sequence.

EXAMPLES:

sage: from surface_dynamics import iet

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

matrix()

Return the Rauzy matrix of this path.

TESTS:

sage: from surface_dynamics import iet
sage: p = iet.Permutation('a b', 'b a')
sage: iet.FlipSequence(p, '').matrix()
[1 0]
[0 1]

orbit_substitution(as_plain_list=False)

Return the substitution on the orbit.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: g0 = iet.FlipSequence(p, ['t'])
sage: s0 = g0.orbit_substitution()
sage: print(s0)
a->ab, b->b
sage: g1 = iet.FlipSequence(p, ['b'])
sage: s1 = g1.orbit_substitution()
sage: print(s1)
a->a, b->ab
sage: (g0 * g1).orbit_substitution() == s0 * s1
True
sage: (g1 * g0).orbit_substitution() == s1 * s0
True

rauzy_move(winner, side='right', iterations=1)

Add a Rauzy move to this flip sequence.

relabel(p)

Add a relabelling to this flip sequence.

self_similar_iet()

Return the dilatation and the self-similar interval exchange transformation associated to this path.

EXAMPLES:

sage: from surface_dynamics import iet

The golden rotation:

sage: p = iet.Permutation('a b', 'b a')
sage: g = iet.FlipSequence(p, ['t', 'b'])
sage: a, T = g.self_similar_iet()
sage: T.lengths().parent()
Vector space of dimension 2 over Number Field ...
sage: T.lengths().n()
(1.00000000000000, 1.61803398874989)

An example from Do-Schmidt:

sage: code = [1,0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,0]
sage: p = iet.Permutation([0,1,2,3,4,5,6],[6,5,4,3,2,1,0])
sage: g = iet.FlipSequence(p, code)
sage: a, T = g.self_similar_iet()
sage: T.sah_arnoux_fathi_invariant()
(0, 0, 0)

self_similar_interval_exchange_transformation()

Return the dilatation and the self-similar interval exchange transformation associated to this path.

EXAMPLES:

sage: from surface_dynamics import iet

The golden rotation:

sage: p = iet.Permutation('a b', 'b a')
sage: g = iet.FlipSequence(p, ['t', 'b'])
sage: a, T = g.self_similar_iet()
sage: T.lengths().parent()
Vector space of dimension 2 over Number Field ...
sage: T.lengths().n()
(1.00000000000000, 1.61803398874989)

An example from Do-Schmidt:

sage: code = [1,0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,0]
sage: p = iet.Permutation([0,1,2,3,4,5,6],[6,5,4,3,2,1,0])
sage: g = iet.FlipSequence(p, code)
sage: a, T = g.self_similar_iet()
sage: T.sah_arnoux_fathi_invariant()
(0, 0, 0)

start()

Return the start of the path.

substitution(as_plain_list=False)

Return the substitution on the orbit.

EXAMPLES:

sage: from surface_dynamics import *

sage: p = iet.Permutation('a b','b a')
sage: g0 = iet.FlipSequence(p, ['t'])
sage: s0 = g0.orbit_substitution()
sage: print(s0)
a->ab, b->b
sage: g1 = iet.FlipSequence(p, ['b'])
sage: s1 = g1.orbit_substitution()
sage: print(s1)
a->a, b->ab
sage: (g0 * g1).orbit_substitution() == s0 * s1
True
sage: (g1 * g0).orbit_substitution() == s1 * s0
True

top_bottom_inverse()

winners()

Return the list of winners along this flip sequence.

EXAMPLES:

sage: from surface_dynamics import iet

sage: p = iet.Permutation('a b','b a')
sage: iet.FlipSequence(p).winners()
[]
sage: iet.FlipSequence(p, [0]).winners()
['b']
sage: iet.FlipSequence(p, [1]).winners()
['a']

winners_losers()

Return the pair of list of winner letters and list of loser letters along the path.