On periodicity and low complexity of infinite permutations

We define an infinite permutation as a sequence of reals taken up to value, or, equivalently, as a linear ordering of NN or of ZZ. We introduce and characterize periodic permutations; surprisingly, for each period tt there is an infinite number of distinct tt-periodic permutations. At last, we study a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is not analogous to that for words and is different for the right infinite and the bi-infinite case.