Farey codes and languages (Q854840): Difference between revisions

Denoting by \(\pi_w\) the minimal period of a word \(w\), we say that \(w\) is central if \(|w|-\pi_w +2\) is a period of \(w\) coprime with \(\pi_w\). Central words are on a two-letter alphabet \(\{a,b\}\) and the set of such words, known as \(PER\), plays an important role in the combinatorics of Sturmian words. In this very interesting paper, the authors study some new structural properties of \(PER\). First, the authors consider two bijections \(\varphi\) and \(\psi\) from \(\{a,b\}^*\) to \(PER\), called the generating maps. They also consider two bijections from \(PER\) to the set of all positive irreducible fractions: \(\theta\), called the ratio of periods, and \(\eta\), called the rate. Second, the authors consider the so-called prefix central codes which are codes of central words such that no word in the set is a prefix of another word. Such a prefix central code is called maximal if it is not properly contained in a larger one. Of particular interest is the maximal prefix central code \(\Delta_n\) of all central words \(w\) having period \(|w|-\pi_w+2\) and satisfying \(0 < n \leq |w| \leq n + \pi_w -1\). The set \(\Delta_n\) is naturally associated with the set \({\mathcal F}_{n+1}\) of the fractions of the Farey series of order \(n+1\), and is hence referred to as the Farey code of order \(n\). The union of all the \(\Delta_n\)'s for \(n \geq 0\) turns out to be equal to the set \(PER\). Third, setting \(PER_a = PER \cap a\{a,b\}^*\) and letting \(n\) denote a positive integer, the authors introduce the Farey language of order \(n\), \[ L_n = \{w \in PER_a \cup \{\varepsilon\} \mid |w| \leq n + \pi_w -2\}, \] and the dual Farey language of order \(n\), \[ M_n = \{w \in PER_a \cup \{\varepsilon\} \mid |w|_a \leq n\}, \] where \(\varepsilon\) denotes the empty word and \(|w|_a\) the number of occurrences of the letter \(a\) in \(w\). This terminology is motivated by the equalities \(\theta(L_n) = {\mathcal F}_n\) and \(\eta(M_n) = {\mathcal F}_n\) holding. Fourth, the authors show some structural properties of the prefix code \(P_n = \psi^{-1}(\Delta_n)\) called the Farey pre-code of order \(n\) which ends up being a maximal prefix code. Finally, the authors introduce two total orderings of the set \(PER\) naturally defined in terms of \(\theta\) and \(\eta\). For a finite subset \(L\) of \(PER\) and a word \(x\) in \(PER\), the \(\theta\)- and \(\eta\)-orders of \(x\) relative to \(L\) are defined as well as some related quantities, and general results are proved. It is noteworthy that in the case where \(L = L_n\) or \(L = M_n\), the Riemann hypothesis on the Zeta function can be restated as a combinatorial property of these languages.