Ergodic Infinite Permutations of Minimal Complexity

Sergey V. Avgustinovich (1) , Anna E. Frid (2) , Svetlana Puzynina (1, 3)

1 Sobolev Institute of Mathematics
2 I2M - Institut de Mathématiques de Marseille
3 MC2 - Modèles de calcul, Complexité, Combinatoire

An infinite permutation can be defined as a linear ordering of the set of natural numbers. Similarly to infinite words, a complexity p(n) of an infinite permutation is defined as a function counting the number of its factors of length n. For infinite words, a classical result of Morse and Hedlind, 1940, states that if the complexity of an infinite word satisfies p(n) ≤ n for some n, then the word is ultimately periodic. Hence minimal complexity of aperiodic words is equal to n + 1, and words with such complexity are called Sturmian. For infinite permutations this does not hold: There exist aperiodic permutations with complexity functions of arbitrarily slow growth, and hence there are no permutations of minimal complexity. In the paper we introduce a new notion of ergodic permutation, i.e., a permutation which can be defined by a sequence of numbers from [0, 1], such that the frequency of its elements in any interval is equal to the length of that interval. We show that the minimal complexity of an ergodic permutation is p(n) = n, and that the class of ergodic permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

Domaines: Mathématique discrète [cs.DM]

Sergey V. Avgustinovich, Anna E. Frid, Svetlana Puzynina. Ergodic Infinite Permutations of Minimal Complexity. DLT 2015, Jul 2015, Liverpool, United Kingdom. pp.71-84, ⟨10.1007/978-3-319-21500-6_5⟩. ⟨hal-01221433⟩