TY - JOUR

T1 - Minimal complexity of equidistributed infinite permutations

AU - Avgustinovich, S. V.

AU - Frid, A. E.

AU - Puzynina, S.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - An infinite permutation is a linear ordering of the set of natural numbers. An infinite permutation can be defined by a sequence of real numbers where only the order of elements is taken into account; such sequence of reals is called a representative of a permutation. In this paper we consider infinite permutations which possess an equidistributed representative on [0,1] (i.e., such that the prefix frequency of elements from each interval exists and is equal to the length of this interval), and we call such permutations equidistributed. Similarly to infinite words, a complexity p(n) of an infinite permutation is defined as a function counting the number of its subpermutations of length n. We show that, unlike for permutations in general, the minimal complexity of an equidistributed permutation α is pα(n)=n, establishing an analog of Morse and Hedlund theorem. The class of equidistributed permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

AB - An infinite permutation is a linear ordering of the set of natural numbers. An infinite permutation can be defined by a sequence of real numbers where only the order of elements is taken into account; such sequence of reals is called a representative of a permutation. In this paper we consider infinite permutations which possess an equidistributed representative on [0,1] (i.e., such that the prefix frequency of elements from each interval exists and is equal to the length of this interval), and we call such permutations equidistributed. Similarly to infinite words, a complexity p(n) of an infinite permutation is defined as a function counting the number of its subpermutations of length n. We show that, unlike for permutations in general, the minimal complexity of an equidistributed permutation α is pα(n)=n, establishing an analog of Morse and Hedlund theorem. The class of equidistributed permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

UR - http://www.scopus.com/inward/record.url?scp=85020262101&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2017.05.003

DO - 10.1016/j.ejc.2017.05.003

M3 - Article

AN - SCOPUS:85020262101

VL - 65

SP - 24

EP - 36

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -