Reduced permutations

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 ReducedPermutation

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

Bases: ReducedPermutation, 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 sorted(p.rauzy_diagram()):
....:     print('%s\n********' % q)
-a  b -c
 b -a -c
********
 a -b -c
-b  a -c
********
 a -b  c
 c  a -b
********
 a  b -c
 b -c  a
********
 a -b  c
 c -b  a
********

list(flips=False)

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 iet

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)

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)

Bases: ReducedPermutation, 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)

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)

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)

Bases: FlippedRauzyDiagram, 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

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

Bases: ReducedPermutation, 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()

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)

Cardinality of Rauzy diagram

As proved in [Del13], 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)

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

Returns the relabelization obtained from this move.

EXAMPLES:

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: list(map(s_t, p_t[0])) == list(map(Word, q_t[0]))
True
sage: list(map(s_t, p_t[1])) == list(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: list(map(s_b, q_b[0])) == list(map(Word, p_b[0]))
True
sage: list(map(s_b, q_b[1])) == list(map(Word, p_b[1]))
True

class surface_dynamics.interval_exchanges.reduced.ReducedPermutationLI(intervals=None, alphabet=None, reduced=False, flips=None)

Bases: ReducedPermutation, 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()

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)

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)

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)

Bases: RauzyDiagram

Rauzy diagram of reduced permutations

surface_dynamics.interval_exchanges.reduced.labelize_flip(couple)

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'