Farey codes and languages

A word ww is central if it has a minimal period πwπw such that |w|−πw+2|w|−πw+2 is a period of ww coprime with πwπw. Central words are in a two-letter alphabet AA and play an essential role in combinatorics of Sturmian words. We study some new structural properties of the set PER   of central words which are based on the existence of two basic bijections ψψ and φφ of A∗A∗ in PER  , related to two different methods of generation, and two natural bijections θθ (the ratio of periods) and ηη (the rate) of PER   in the set of all positive irreducible fractions. In this paper we are mainly interested in sets of central words which are codes. In particular, for any positive integer nn we consider the set ΔnΔn of all central words ww such that the period |w|−πw+2|w|−πw+2 is not larger than n+1n+1 and |w|≥n|w|≥n. In a previous paper we proved that for each nn, ΔnΔn is a maximal prefix central code called the Farey code of order nn since it is naturally associated with the Farey series of order n+1n+1. New structural properties of Farey codes are given as well as of their pre-codes PnPn. In particular one has PER=∪n≥0Δn. Moreover, for each nn two languages of central words LnLn and MnMn are introduced. The language LnLn (resp., MnMn) is called the Farey (resp., dual Farey) language of order nn. The name is motivated by the fact that LnLn and MnMn give faithful representations of the set of Farey’s fractions of order nn. Finally, two total orderings of PER   are naturally defined in terms of maps θθ and ηη. The notion of order of a central word relative to a language of central words is given and some general results are proved. In the case of Farey’s languages one has that the Riemann hypothesis on the Zeta function can be restated in terms of a combinatorial property of these languages.