Abstract: 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.

Cite: Avgustinovich S.V. , Frid A.E. , Puzynina S.
Minimal complexity of equidistributed infinite permutations
European Journal of Combinatorics. 2017. V.65. P.24-36. DOI: 10.1016/j.ejc.2017.05.003 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Dec 20, 2016
Accepted:	May 11, 2017

Identifiers:

Web of science:	WOS:000408301100003
Scopus:	2-s2.0-85020262101
Elibrary:	31002012
OpenAlex:	W2962952252

Citing:

DB	Citing
Web of science	2
Scopus	2
Elibrary	2
OpenAlex	2

Altmetrics: