Infinite permutations of lowest maximal pattern complexity (Q544872)

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\).