Infinite permutations of lowest maximal pattern complexity

Abstract: An infinite permutation is a linear ordering of the set of non-negative integers. Generally, the properties of infinite permutations analogous to those of infinite words show some resemblances and some differences between permutations and words. In this paper, we define maximal pattern complexity for infinite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic. Then we characterize the non-periodic permutations of minimal complexity (equal to n) and find that they all are constructed with the use of Sturmian words.

Review text

An \(\mathbb{N}\)-permutation is a linear ordering of \(\mathbb{N}\) represented by \ a sequence of pairwise distinct real numbers \(\alpha=\left\{ \alpha _{i}\right\} _{i=1}^{\infty}\).\ The ordering may be encoded using the symbols \(\gamma_{ij}\in\left\{ <,>\right\} \), where \(\gamma_{ij}=\,<\) if \(\alpha _{i}<\alpha_{j}\), and \(\gamma_{ij}=\,>\) otherwise. The sequence \(\alpha\) is [ultimately] periodic if, for some \(t\geq1,\) \(\gamma_{ij}=\gamma_{i+tj+t}\) for all \(i,j\) (starting from some \(n_{0}\)). A \(T\)-pattern in \(\alpha\), where \(T=\left\{ 0<m_{1}<\cdots<m_{n-1}\right\} \), is the \(n\)-permutation corresponding to a finite subsequence \(\alpha_{k}\alpha_{m_{1}+k}\cdots \alpha_{m_{n-1}+k}\), \(k\geq0\). The number of distinct \(T\)-patterns in \(\alpha\) is denoted as \(p_{\alpha}\left( T\right) \). A \(\left\{ 0,1,\ldots,n-1\right\} \)-pattern\ in \(\alpha\) is called an \(n\)-factor of \(\alpha\). A characterization of (ultimate) periodicity of \(\mathbb{N}\)-permutations based on the number \(f_{\alpha}\left( n\right) \) of distinct factors of \(\alpha\) of length \(n\) is known and just partially corresponds to the similar characterization for infinite words. In the current paper the authors consider the maximal pattern complexity \(p_{\alpha}^{\ast}\left( n\right) =\max_{\left| T\right| =n}p_{\alpha}\left( T\right).\) Their main result states that an infinite word is ultimately periodic if and only if \(p_{\alpha}^{\ast}\left( n\right) \geq n\). This is an analogue of a similar fact known for infinite words (where the right-hand side is to be replaced by \(2n\)). Moreover, they prove that equality holds exactly for those \(\mathbb{N}\)-permutations that are Sturmian. An \(\mathbb{N}\)-permutation \(\alpha\) is said to be Sturmian if it can be described using some Sturmian word \(w=w_{0}w_{1}\cdots\) and fixed real numbers \(\alpha_{0},x,y\) by the formula \(\alpha_{i+1}=\alpha_{i}+x\) if \(w_{i}=0\) and \(\alpha_{i+1}=\alpha_{i}-y\) if \(w_{i}=1\).

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Infinite permutations of lowest maximal pattern complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q544872)