Sturmian sequences and the lexicographic world

Abstract:

In this paper, we give a complete description for the lexicographic world ${\mathcal {L}}=\{(x,y)\in \Sigma \times \Sigma : \Sigma _{xy}\not =\emptyset \} =\{(x,y):y\ge \phi (x)\}$, where $\Sigma =\{0,1\}^{\mathbf {N}}$, $\Sigma _{ab}=\{x\in \Sigma : a\le \sigma ^i(x)\le b,\text {for\ all\ }i\ge 0\}$, $\phi :\Sigma \to \Sigma$ is defined by $\phi (a)=\inf \{b:\Sigma _{ab}\not =\emptyset \}$ and the order $\le$ is the lexicographic order on $\Sigma$. The main result is that $b=\phi (a)$ for some $a=0x$ if and only if $b$ is the Sturmian sequence $b$ such that $\operatorname {Orb}(b)\subset [0x,1x]$ and $\sigma ^i(b)\le b$ for all $i\ge 0$. At the same time, a new description of Sturmian minimal sets is given. A minimal set $M$ is a Sturmian minimal set if and only if, for some $x\in \Sigma$, $M\subset [0x,1x]$. Moreover, for any $x\in \Sigma$, there exists a unique Sturmian minimal set in $[0x,1x]$.