Permutations infinies “ergodiques”

Anna Frid
I2M, Aix-Marseille Université
/user/anna.frid/

Date(s) : 18/11/2014   iCal
11 h 05 min - 12 h 00 min

Une permutation infinie est un ordre sur N. Nous pouvons considérer une permutation comme une structure analogue à un mot, et en particulier, étudier son ensemble de facteurs. Comme nous avons montré avec D. Fon-Der-Flaass en 2007, la complexité d’une permutation non périodique peut être majorée par toute fonction croissante non bornée. Cependant, cela n’est plus le cas si on ne considère que les permutations “ergodiques”. Une permutation est “ergodique” si elle correspond à une suite de nombres réels deux à deux distincts entre 0 et 1 telle que la probabilité qu’un nombre soit inférieur à p est p pour tout p.

Nous montrons que la complexité minimale d’une permutation ergodique est n, et que les permutations dont la complexité est n sont exactement les permutations sturmiennes. Nous discutons aussi les représentants canoniques des permutations définies par des mots morphiques et généralisons la construction de Makarov (2009) pour le mot de Thue-Morse.

(En collaboration avec S. V. Avgustinovich, S. A. Puzynina)

Infinite “ergodic” permutations

An infinite permutation is an order on N. We can consider a permutation as a structure analogous to a word, and in particular, study its set of factors. As we showed with D. Fon-Der-Flaass in 2007, the complexity of a non-periodic permutation can be increased by any unbounded increasing function. However, this is no longer the case if one considers only the “ergodic” permutations. A permutation is “ergodic” if it corresponds to a sequence of two by two distinct real numbers between 0 and 1 such that the probability that a number is less than p is p for all p.
We show that the minimal complexity of an ergodic permutation is n, and that the permutations whose complexity is n are exactly the Sturmian permutations. We also discuss the canonical representatives of permutations defined by morphic words and generalize the construction of Makarov (2009) for the Thue-Morse word.
(In collaboration with S. V. Avgustinovich, S. A. Puzynina)

https://hal.archives-ouvertes.fr/hal-01221433/

 

Catégories



Retour en haut