# Lochs-type theorems beyond positive entropy

Valérie Berthé  Université de Paris, CNRS, IRIF, F-75006 Paris, France
<EMAIL_ADDRESS>,  Eda Cesaratto  CONICET and Instituto del Desarrollo Humano,
Universidad Nacional de General Sarmiento, Buenos Aires, Argentina
<EMAIL_ADDRESS>,  Pablo Rotondo  Laboratoire d’Informatique
Gaspard-Monge, Université Gustave Eiffel, Champs-sur-Marne, France
<EMAIL_ADDRESS>and  Martín D. Safe  Departamento de Matemática,
Universidad Nacional del Sur (UNS), Bahía Blanca, Argentina, and INMABB,
Universidad Nacional del Sur (UNS)-CONICET, Bahía Blanca, Argentina
<EMAIL_ADDRESS>
###### Abstract.

Lochs’ theorem and its generalizations are conversion theorems that relate the
number of digits determined in one expansion of a real number as a function of
the number of digits given in some other expansion. In its original version,
Lochs’ theorem related decimal expansions with continued fraction expansions.
Such conversion results can also be stated for sequences of interval
partitions under suitable assumptions, with results holding almost everywhere,
or in measure, involving the entropy. This is the viewpoint we develop here.
In order to deal with sequences of partitions beyond positive entropy, this
paper introduces the notion of log-balanced sequences of partitions, together
with their weight functions. These are sequences of interval partitions such
that the logarithms of the measures of their intervals at each depth are
roughly the same. We then state Lochs-type theorems which work even in the
case of zero entropy, in particular for several important log-balanced
sequences of partitions of a number-theoretic nature.

This work was supported by the Agence Nationale de la Recherche through the
project CODYS (ANR-18-CE40-0007) and STIC AMSUD project 20STIC-06. The authors
are members of LIA SINFIN (ex-INFINIS), Université de Paris-CNRS/Universidad
de Buenos Aires-CONICET. E. Cesaratto was partially supported by Grant UNGS
30/3307. M.D. Safe was partially supported by Grant UNS PGI 24/L115.

Keywords. zero entropy, infinite entropy, Farey and Stern-Brocot sequences,
three-distance theorem, numeration systems, Lochs’ theorem, change of base

2020 MSC. 11K55, 11K50, 11B57, 28D20

##  1\. Introduction

Lochs’ theorem [Loc63] is a probabilistic statement about base changes. This
conversion theorem relates, almost everywhere, the relative speed of
approximation of decimal and regular continued fractions expansions to the
quotient of the entropies of their respective dynamical systems. More
generally, Lochs-type theorems amount to compare the number of digits
determined in one expansion of a real number as a function of the number of
digits given in some other expansion.

Lochs’ theorem and its extensions have given rise to a rich literature. The
original setting of Lochs’ theorem has been considered in [Fai97] where an
error term is provided based on the use of a Perron–Frobenius type operator;
see also [Fai98] for a central limit theorem, [Fai01, Wu06] for the case of
numbers $x$ having a _Lévy’s constant_ $\lim_{n\to\infty}(\log q_{n}(x))/n$
(including the case of quadratic numbers), and [Wu08] for an iterated
logarithm law. Analogous results for the case of the beta-numeration and
continued fractions have been established in [BI08, LW08a, FWL16, FWL19] and
in [LW08b] in the case of the beta-numeration and of the continued fractions
for formal power series with coefficients in a finite field. More general
transformations have then been considered in [DF01, BDK06, DdVJ06] for number
theoretic fibred systems. Most of these results are stated in the case where
both dynamical systems to be compared have positive entropy.

In the present paper we follow the viewpoint developed in [DF01, BDK06] where
Lochs’ theorem is understood as a way to see how decimal intervals fit into
the fundamental intervals provided by the continued fraction expansion. Here
also, and as stressed in [DF01], proofs are based on measure-theoretic
covering arguments and not on the dynamics of specific maps. We introduce the
notion of log-balanced sequences of partitions of the unit interval, inspired
by [DF01] (where the terminology ‘equipartition’ is used). Roughly speaking,
that a sequence $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ of partitions of
the unit interval is log-balanced means that the intervals of each partition
$P_{n}$ have approximately the same measure $e^{-f(n)}$ as $n\to\infty$ (a.e.
or in measure), where $f$ is called a weight function (see Definition 2.1) We
then deal with the Lochs index, a now classical parameter in base changing,
denoted here by $L_{n}$ and defined for two sequences of partitions as
follows. Let $\mathcal{P}^{1}=\\{P^{1}_{n}\\}_{n\in\mathbb{N}}$ and
$\mathcal{P}^{2}=\\{P^{2}_{n}\\}_{n\in\mathbb{N}}$ be two sequences of
partitions of the unit interval. For each $i=1,2$, let $E^{i}$ be the set of
endpoints of all the intervals of the partitions in $\mathcal{P}^{i}$ and, for
each $x\in[0,1]\setminus E^{i}$, let $I^{i}_{n}(x)$ be the interval of
$P_{n}^{i}$ containing $x$. Then, the Lochs index is defined by

(1) $L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}):=\sup\\{\ell\in\mathbb{N}\mid
I^{1}_{n}(x)\subseteq I^{2}_{\ell}(x)\\},$

for each $x\in[0,1]\setminus(E^{1}\cup E^{2})$.(Strictly speaking, we work
with _topological_ partitions, see Section 2.1.)

The behaviour (a.e. or in measure) of Lochs’ index is usually described in the
literature in terms of entropy (we discuss the notion of entropy in Section
2.1 and 4.4). Our work is inspired by the following result, which is Theorem 4
from [DF01]. Let $\lambda$ be a Borel probability measure on $[0,1]$. If
$\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ are sequences of partitions having
positive a.e. entropies $h_{1}$ and $h_{2}$ with respect to $\lambda$, then

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})}{n}=\frac{h_{1}}{h_{2}}\quad
a.e.\ (\lambda).$

As Dajani and Fieldsteel [DF01], we also consider a variant in measure of the
above result.

Our main results, Theorems 2.8 and 2.9, work as follows. Let $\mathcal{P}^{1}$
and $\mathcal{P}^{2}$ be two log-balanced sequences of partitions with weight
functions $f_{1}$ and $f_{2}$, both of which either a.e. or in measure. We
give sufficient conditions in order to ensure that

(2)
$\lim_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}=1$

either a.e. or in measure ($\lambda$), respectively.

Our results extend the results of [DF01], by providing asymptotic relations as
(2) for partitions which may not have positive entropy. The hypotheses of our
main results regard separately the weight functions $f_{1}$ and $f_{2}$.

For an illustration, consider the sequence of partitions given by the binary
numeration, i.e., $\mathcal{P}^{1}=\mathcal{B}=\\{B_{n}\\}_{n\in{\mathbb{N}}}$
with

$B_{n}=\left\\{\left(0,\frac{1}{2^{n}}\right),\left(\frac{1}{2^{n}},\frac{2}{2^{n}}\right),\ldots,\left(\frac{2^{n}-1}{2^{n}},1\right)\right\\},$

and the Farey sequence of partitions
$\mathcal{P}^{2}=\mathcal{F}=\\{F_{n}\\}_{n\in\mathbb{N}}$ (the latter of
which has zero entropy, see Section 4.6), where each $F_{n}$ is determined by
the set $E_{n}^{\mathcal{F}}$ of endpoints of its intervals, given as follows:

$E^{\mathcal{F}}_{n}:=\left\\{\frac{p}{q}:\,p,q\geq 1,\ \gcd(p,q)=1\text{ and
}q\leq n+1\right\\}.$

Our results imply that, with respect to the Lebesgue measure,

$\displaystyle\lim_{n\to\infty}\frac{2\log
L_{n}(x,\mathcal{B},\mathcal{F})}{(\log 2)n}=1\quad\text{ a.e.}$

(where by $\log$ we mean the natural logarithm). Note that a change of scale
is performed on the Loch’s index $L_{n}(x,\mathcal{B},\mathcal{F})$ which
occurs as $\log L_{n}(x,\mathcal{B},\mathcal{F})$ compared to the index $n$.

Our main examples of sequences of partitions (see Section 4) are of an
arithmetic nature. They are associated with numeration systems (see Section
4.2), dynamically, with fibred systems (see Section 4.3), and more
specifically with continued fractions with the Stern-Brocot tree (see Section
4.5), the Farey sequence (see Section 4.6), and a partition related to the
three distance theorem (see Section 4.7).

The study of base changes and of the Lochs index opens a large scope of
potential applications. Indeed, sequences of partitions can model numeration
systems (see Section 4.2), as well as sources for the production of digits; as
an example, consider the dichotomic selection on words for selection
algorithms developed in [ACD+19] and see also Section 7. A further motivation
is the dynamic generation of characteristic Sturmian words of uniform random
parameters (see Section 7 for more on this topic).

##### Plan of the article

The key notion of a log-balanced sequence of partitions is introduced in
Section 2.1 together with the weight functions for our main examples of
sequences of partitions. The definition of the Lochs index is given in Section
2.2 which also presents the main theorems of this paper. Section 3 gives some
basic results on log-balanced sequences of partitions. The examples of
sequences of partitions considered in the present paper are detailed in
Section 4, with in particular the notion of a numeration system given by a
sequence of partitions in Section 4.2 and a discussion on fibred systems in
Section 4.3. For the case of conversions between the Farey and the continued
fractions sequences of partitions, explicit formulas for the corresponding
Lochs indexes are given in Section 5. As a consequence, we derive in
particular a Lochs-type theorem for the conversion from the continued fraction
to the Farey sequences of partitions in law (see Section 5.1). The proofs of
our main general conversion results are given in Section 6. We conclude this
paper with open questions and by developing connections with sources and tries
in Section 7.

##  2\. Log-balancedness and Lochs-type theorems

The aim of this section is to introduce the main notions and state our main
results. In Section 2.1, we define the notions of log-balancedness and weight
function. As far as we know, these notions are introduced in this paper for
the first time in the context of Lochs’ index. We also relate weight functions
to the entropies of sequences of partitions when they are positive. Theorem
2.4 presents our main examples of log-balanced sequences of partitions
together with their weight functions. In Section 2.2, we formally define the
notion of Lochs’ index, following the classical approach of the literature.
Finally, in the same section, we state our main results.

###  2.1. Log-balanced sequences of partitions

We first fix some general notation and definitions. We consider that
$0\in{\mathbb{N}}$. The notation $\overline{A}$ stands for the usual
topological closure of $A$. The Lebesgue measure is denoted by $|\cdot|$.

A _topological partition of $[0,1]$_ is a collection of pairwise disjoint open
nonempty intervals so that the union of their closures equals $[0,1]$. Notice
that such a collection is necessarily at most countable.

By a _sequence of partitions_ $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$, we
mean a sequence of topological partitions of $[0,1]$. We refer to the
intervals in $P_{n}$ as the intervals at depth $n$ of $\mathcal{P}$. We say
that $\mathcal{P}$ is _self-refining_ if, for each $n\in\mathbb{N}$, each
interval of $P_{n+1}$ is contained in (and possibly equal to) an interval of
$P_{n}$. A sequence of partitions $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$
is _strictly self-refining_ if it is self-refining and $P_{n+1}\neq P_{n}$ for
each $n\in\mathbb{N}$; or, equivalently, for each $n\in\mathbb{N}$, there
exists an interval $I_{n}$ in $P_{n}$ which is the union of at least two
different intervals in $P_{n+1}$. We denote by $E^{\mathcal{P}}$ the set of
endpoints of the intervals in the partitions in $\mathcal{P}$.

Given a sequence of partitions $\mathcal{P}$, $n\in\mathbb{N}$, and
$x\in[0,1]\setminus E^{\mathcal{P}}$, we denote by $I_{n}^{\mathcal{P}}(x)$
the unique interval in $P_{n}$ to which $x$ belongs. If there is no risk of
ambiguity, we denote $I_{n}^{\mathcal{P}}(x)$ simply by $I_{n}(x)$ and
$E^{\mathcal{P}}$ simply by $E$.

######  Definition 2.1.

Let $\lambda$ be a Borel probability measure on $[0,1]$. Let $\mathcal{P}$ be
a sequence of partitions. We say that $\mathcal{P}$ is _log-balanced a.e._
(resp.  _in measure_) with respect to $\lambda$ if $\lambda(E)=0$ and there is
some function $f:\mathbb{N}\to\mathbb{R}$ such that $f(n)\to+\infty$ as
$n\to\infty$ and

$\lim_{n\to\infty}\frac{-\log\lambda(I_{n}(x))}{f(n)}=1\quad a.e.\
(\text{resp.\ in measure})\quad(\lambda).$

If so, $f$ is called a _weight function of $\mathcal{P}$ a.e._ (resp.  _in
measure_) with respect to $\lambda$.

The weight function is not unique. If $f$ is a weight function for a sequence
of partitions $\mathcal{P}$ with respect to some measure $\lambda$, any other
function $g:\mathbb{N}\to\mathbb{R}$ so that $f(n)/g(n)\to 1$ as $n\to\infty$
is also a weight function with respect to $\lambda$. In the particular case of
an a.e. log-balanced self-refining system of partitions, the weight function
might be chosen to be nondecreasing. This is proved in Proposition 3.5.

When, in the above definition, the weight $f$ is linear, one recovers the
following notions of entropy, as given in [DF01], which are reminiscent of the
Shannon–McMillan–Breiman theorem (see Theorem 4.4).

######  Definition 2.2.

Let $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ be a sequence of partitions and
$\lambda$ be a Borel probability measure $\lambda$ on the unit interval. We
say $\mathcal{P}$ _has entropy $h$ a.e. (resp. in measure) with respect to
$\lambda$_ if $\lambda(E)=0$ and

(3) $\lim_{n\to\infty}\frac{-\log\lambda(I_{n}(x))}{n}=h\quad\text{a.e.\
(resp.\ in measure)\ }(\lambda).$

######  Remark 2.3.

The assumption $\lambda(E)=0$ is not given in [DF01, Definition 2];
nevertheless, it is implicit in it. The reason is that in that work, the
partitions are made up of semi-open intervals in such a way that for any
$x\in[0,1)$ and each $n\in\mathbb{N}$ there is a well defined $I_{n}(x)$ in
$P_{n}$ such that $x\in I_{n}(x)$. Thus, in that context, (3) implies
$\lambda(\\{x\\})=0$ for every $x\in[0,1)$ (cf. Proposition 3.2 of this work).
Notice also that in [DF01], $\lambda([0,1))=1$.

#### Main examples of weight functions.

Our main examples of sequences of partitions are detailed in Section 4. It
includes number-theoretic fibred systems, especially the sequence of
partitions associated with continued fractions and the binary numeration
system. We also study the Farey sequence of partitions given by the classical
Farey sequence. We are interested in it because of its strong relation with
Sturmian words (see e.g. [Ber96]). In addition, we study the Stern-Brocot
sequence of partitions associated with the Stern-Brocot tree. Finally, we also
study what we call three-distance sequences of partitions parameterized by an
irrational $\alpha\in(0,1)$, associated with the family of Kronecker-Weyl
sequences $n\mapsto\\{n\alpha\\}$. The precise definition of all of these
sequences of partitions are given throughout Section 4. Also throughout that
section, the log-balancedeness of each of these sequences is analyzed, thus
obtaining the results summarized in the following theorem.

######  Theorem 2.4.

The following assertions hold with respect to the Lebesgue measure:

  1. (i)

The binary partition $\mathcal{B}$ is a.e. log-balanced with weight function

$f_{\mathcal{B}}(n)=(\log 2)n.$

  2. (ii)

The continued fractions partition $\mathcal{CF}$ is a.e. log-balanced with
weight function

$f_{\mathcal{CF}}(n)=\frac{\pi^{2}}{6\log 2}n.$

  3. (iii)

More generally, if $\mathcal{H}$ is any sequence of partitions having positive
entropy $h$ a.e. (resp. in measure), then $\mathcal{H}$ is log-balanced a.e.
(resp. in measure) with weight function

$f_{\mathcal{H}}(n)=hn.$

  4. (iv)

The Farey partition $\mathcal{F}$ is a.e. log-balanced with weight function

$f_{\mathcal{F}}(n)=2\log n\quad\text{for each }n\geq 1.$

  5. (v)

The three-distance partition $3\mathcal{D}(\alpha)$ is a.e. log-balanced, for
a.e. $\alpha\in(0,1)$, with weight function

$f_{{3\mathcal{D}}({\alpha})}(n)=\log n\quad\text{for each }n\geq 1.$

However, there is an uncountable set of numbers $\alpha$ for which
${3\mathcal{D}}({\alpha})$ is not even log-balanced in measure.

  6. (vi)

The Stern-Brocot partition $\mathcal{SB}$ is log-balanced in measure with
weight function

$f_{\mathcal{SB}}(n)=\frac{\pi^{2}}{6}\frac{n}{\log n}\quad\text{for each
}n\geq 2.$

Nevertheless, the $\mathcal{SB}$ partition is not log-balanced a.e.

The fact that we work with the logarithm of the measures of the intervals (and
not with the measures themselves) allows for some non-uniformity for the
measures of the intervals. This is illustrated in particular by the case of
the Stern-Brocot sequence of partitions, which is log-balanced in measure (but
not a.e.) with respect to the Lebesgue measure.

###  2.2. Lochs-type theorems

We start by giving a precise definition of Lochs’ index, following the
approach of [BDK06] and [DF01]. If $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ are
sequences of partitions, then, for each $i=1,2$, we denote by $E^{i}$ the set
of endpoints of all the intervals of the partitions in $\mathcal{P}^{i}$ and,
for each $x\in[0,1]\setminus E^{i}$, $I^{i}_{n}(x)$ the interval of
$P_{n}^{i}$ containing $x$.

######  Definition 2.5.

If $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ are sequences of partitions and
$n\in\mathbb{N}$, the Lochs index is defined as

$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}):=\sup\\{\ell\in\mathbb{N}\mid
I^{1}_{n}(x)\subseteq I^{2}_{\ell}(x)\\},\quad\text{for each
}x\in[0,1]\setminus(E^{1}\cup E^{2}).$

When both sequences of partitions involved are log-balanced a.e. or in measure
with respect to the same Borel probability measure $\lambda$, the Lochs index
is a.e. finite with respect to $\lambda$. This will be proved in Proposition
3.3.

####  2.2.1. Results for general sequences of partitions

We first recall results from the literature. Let us consider the sequence of
partitions $\mathcal{P}^{1}=\mathcal{D}=\\{D_{n}\\}$ of the decimal numeration
system, i.e.,

$D_{n}=\left\\{\left(0,\frac{1}{10^{n}}\right),\left(\frac{1}{10^{n}},\frac{2}{10^{n}}\right),\ldots,\left(\frac{10^{n}-1}{10^{n}},1\right)\right\\},$

and let $\mathcal{P}^{2}$ be the classical continued fraction sequence of
partitions $\mathcal{CF}$ (as given in Section 4.4.4). The following is the
classical Lochs’ theorem.

######  Theorem 2.6 ([Loc63]).

The following holds with respect to the Lebesgue measure:

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{CF},\mathcal{D})}{n}=\frac{6\log
2\log 10}{\pi^{2}}\quad\text{a.e.}$

Dajani and Fieldsteel [DF01] proved theorems like the above one but in a more
general setting, involving two sequences of partitions $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$, both of positive entropies a.e. or in measure. Their
results are as follows.

######  Theorem 2.7 ([DF01, Theorem 4]).

If $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ are sequences of partitions having
positive a.e. entropies $h_{1}$ and $h_{2}$ with respect to some Borel
probability measure $\lambda$ on $[0,1]$, then

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})}{n}=\frac{h_{1}}{h_{2}}\quad
a.e.\ (\lambda).$

######  Theorem 2.8 ([DF01, Theorem 6]).

If $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ are sequences of partitions having
positive entropies $h_{1}$ and $h_{2}$ in measure with respect to some Borel
probability measure $\lambda$ on $[0,1]$ and $\mathcal{P}^{2}$ is self-
refining, then

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})}{n}=\frac{h_{1}}{h_{2}}\quad\text{in
measure}\ (\lambda).$

We now state our main results which are extensions of the above theorems to
log-balanced sequences of partitions.

theoremmainResultae Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be two a.e.
log-balanced sequences of partitions with weight functions $f_{1}$ and
$f_{2}$, respectively, with respect to some Borel probability measure
$\lambda$ on $[0,1]$ such that all the following assertions hold:

  1. (i)

$\sum_{n=1}^{\infty}e^{-\delta f_{1}(n)}<\infty$ for every $\delta>0$;

  2. (ii)

$f_{2}$ is nondecreasing;

  3. (iii)

$f_{2}(n+1)-f_{2}(n)=o(f_{2}(n))$ as $n\to\infty$.

Then,

$\lim_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}=1\quad\text{a.e.\
}(\lambda).$

######  Remark 2.9.

The assumptions of this theorem can be easily checked in natural instances.

  1. (1)

Assumption (i) above holds for any $f$ satisfying that
$\lim_{n\to\infty}f(n)/\log n=\infty$. In contrast, it does not hold if
$\limsup_{n\to\infty}f(n)/\log n$ is finite.

  2. (2)

If $\mathcal{P}_{2}$ is self-refining, then the weight function $f_{2}$ can be
chosen to be nondecreasing (see Proposition 3.5).

  3. (3)

A weight function $f_{2}$ satisfies assumption (iii) above if and only if
$f_{2}(n+1)/f_{2}(n)\to 1$ as $n\to\infty$ or, equivalently,
$\sqrt[1/n]{|f_{2}(n)|}\to 1$ as $n\to\infty$.

theoremmainResultim Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be two
sequences of partitions that are log-balanced in measure, having respective
weight functions $f_{1}$ and $f_{2}$, with respect to some Borel probability
measure $\lambda$ on $[0,1]$ such that all the following assertions hold:

  1. (i)

$\mathcal{P}^{2}$ is self-refining;

  2. (ii)

$f_{2}$ is nondecreasing;

  3. (iii)

$f_{2}(n+1)-f_{2}(n)=o(f_{2}(n))$ as $n\to\infty$.

Then,

$\lim_{n\to\infty}\frac{f_{2}(L_{n}(x;\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}=1\quad\text{in
measure\ }(\lambda).$

######  Remark 2.10.

In this case, there are no assumptions on $f_{1}$ apart from it being a weight
function of $\mathcal{P}^{1}$ with respect to $\lambda$. Possible assumptions
equivalent to assertion (iii) are given in Remark 2.9 above.

The above theorems are proved in Section 6. To prove them, we deal with the
corresponding superior and inferior limits separately. This gives four
propositions. The conditions in their statements are weaker than those asked
in Theorems 2.8 and 2.9 but, for the propositions regarding the inferior
limits, are also more technical. The first two, Propositions 6.6 and 6.7,
consider a.e. convergence and prove Theorem 2.8. Propositions 6.11 and 6.12
prove the result in measure, namely Theorem 2.9.

####  2.2.2. Positive entropy versus Farey and Stern-Brocot

We focus here on conversion results involving the Farey and the Stern-Brocot
sequences of partitions.

In the case $\mathcal{P}^{2}$ is the Farey sequence of partitions
$\mathcal{F}$ (see Section 4.6) and $\lambda$ is the Lebesgue measure, Theorem
2.8 applies when $\mathcal{P}^{1}$ is any sequence of partitions $\mathcal{H}$
of positive entropy $h$ a.e. and yields the following:

(4) $\lim_{n\to\infty}\frac{\log
L_{n}(x,\mathcal{H},\mathcal{F})}{n}=\frac{h}{2}\quad\text{a.e.},$

with respect to the Lebesgue measure. In particular, if $\mathcal{H}$ is the
binary sequence of partitions $\mathcal{B}$ or the continued fraction sequence
$\mathcal{CF}$, then $h$ is $\log 2$ or $\pi^{2}/(6\log 2)$, respectively.
Note that this result admits a nice interpretation in terms of Sturmian words:
because of the connection between Sturmian words and the Farey sequences (see
Section 4.6.2), the assertion for $\mathcal{H}=\mathcal{B}$ means that the
first $n$ digits in the binary expansion of some $x\in[0,1]$ gives the prefix
of length roughly $2^{n/2}$ of the characteristic Sturmian word associated
with $x$. Concerning the case ${\mathcal{H}}=\mathcal{CF}$, note also that
using classical results about the statistics of continued fractions
expansions, a normal law is even proved in Theorem 5.4 for the Lochs index
$L_{n}(x,\mathcal{CF},\mathcal{F})$.

Notice that assumption (i) of Theorem 2.8 is not satisfied in the case where
$\mathcal{P}^{1}=\mathcal{F}$, because the corresponding weight function is
$f_{\mathcal{F}}(n)=2\log n$ (see Theorem 2.4 and Remark 2.9). In Section 5.6,
we show, by alternative means, that

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{F},\mathcal{CF})}{\log
n}=\frac{12\log 2}{\pi^{2}}\quad\text{a.e.,}$

with respect to the Lebesgue measure. In this case, our general results only
provide convergence in measure. The fact that we may obtain a stronger
convergence is not surprising in such a case: the two partitions, continued
fractions and Farey, are strongly related in their constructions (see e.g.,
Lemma 5.2), while the proofs of the general results are based on the
comparison of the growth of the measures of the intervals.

Lastly, the case of the Stern-Brocot sequence of partitions and positive
entropy is an example of direct application of Theorem 2.9 together with
Theorem 2.4. If $\mathcal{H}$ is any sequence of partitions of positive
entropy $h$ in measure, then

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{SB},\mathcal{H})}{n\log
L_{n}(x,\mathcal{SB},\mathcal{H})}=\frac{6h}{\pi^{2}}\quad\text{in measure}$

and

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{H},\mathcal{SB})}{n/\log
n}=\frac{\pi^{2}}{6h}\quad\text{in measure},$

with respect to the Lebesgue measure.

##  3\. Basic properties of sequences of partitions

This section gathers basic results which describe the behavior of log-balanced
sequences of partitions and of Lochs’ index. The first one, namely Proposition
3.1, shows that the measures of intervals of a log-balanced sequence of
partitions tend to zero as their depths tend to infinity. This has two
consequences: first, points have zero measure (Proposition 3.2); second,
Lochs’ index is a.e. finite (Proposition 3.3). Proposition 3.4 then shows that
if a sequence of partitions is log-balanced with respect to a measure
$\lambda$, so is it with respect to any measure equivalent to $\lambda$. This
property is relevant for the study of number-theoretic fibred systems (see
Section 4.3). Proposition 3.5 shows that any a.e. log-balanced sequence of
partitions admits some nondecreasing weight function. Finally, Proposition 3.6
proves that a sequence of partitions with a sub-exponential number of
intervals at each depth has zero entropy. In particular, if it is log-
balanced, its weight function is in $o(n)$. This is the case for the Farey and
the three-distance sequences of partitions.

The following proposition shows that the norm of the partitions of a log-
balanced sequence tend to zero.

######  Proposition 3.1.

Let $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ be a sequence of partitions. If
$\mathcal{P}$ is log-balanced in measure (or even a.e.) with respect to some
measure $\lambda$, then

$\|P_{n}\|_{\lambda}:=\sup_{I\in P_{n}}\lambda(I)\to 0\quad\text{as
}n\to\infty.$

###### Proof.

Suppose otherwise $\|P_{n}\|_{\lambda}\not\to 0$ as $n\to\infty$. Thus, there
is some $c>0$ and some increasing sequence $\\{n_{k}\\}_{k\in\mathbb{N}}$ such
that $\|P_{n_{k}}\|_{\lambda}\to c$ as $k\to\infty$. Let $J_{k}\in P_{n_{k}}$
such that $\lambda(J_{k})>c/2$, for large enough $k$.

Let $f$ be a weight function of $\mathcal{P}$ in measure (or even a.e.) with
respect to $\lambda$. Since $f(n_{k})\to+\infty$ as $k\to\infty$, we have that
$1+\log(c/2)/f(n_{k})\geq 1/2$ for $k$ large enough. Hence, as for each $x\in
J_{k}$, we have $J_{k}=I_{n_{k}}(x)$, then

$\displaystyle\frac{c}{2}<\lambda(J_{k})$
$\displaystyle\leq\lambda\left(\left\\{x\in[0,1]:\,1+\frac{\log\lambda(I_{n_{k}}(x))}{f(n_{k})}>1+\frac{\log(c/2)}{f(n_{k})}\right\\}\right)$
$\displaystyle\leq\lambda\left(\left\\{x\in[0,1]:\,\left|1+\frac{\log\lambda(I_{n_{k}}(x))}{f(n_{k})}\right|>\frac{1}{2}\right\\}\right),$

for large enough $k$. This shows that $-\log(\lambda(I_{n}(x))/f(n)$ does not
converge towards $1$ as $n\to\infty$ in measure and thus neither does a.e.
This contradicts that $f$ is a weight function of $\mathcal{P}$.∎

The next propositions show that the property of being log-balanced with
respect to $\lambda$ implies that $\lambda$ charges no point and moreover that
the measure of the intervals of the partitions $P_{n}$ tend to $0$ as
$n\to\infty$. Also, equivalent measures yield the same log-balanced sequences
and weight functions.

######  Proposition 3.2.

Let $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ a sequence of partitions. If
$\mathcal{P}$ is log-balanced in measure (or even a.e.) with respect to some
measure $\lambda$, then $\lambda(\\{x\\})=0$ for each $x\in[0,1]$.

###### Proof.

On the one hand, $\lambda(E)=0$ by Definition 2.1. On the other hand, if
$x\in[0,1]\setminus E$ and $n\in\mathbb{N}$, then
$\lambda(\\{x\\})\leq\lambda(I_{n}(x))\leq\|P_{n}\|_{\lambda}$ and thus
$\lambda(\\{x\\})=0$ by Proposition 3.1. ∎

In our setting of log-balanced sequences of partitions, Lochs’ index takes
finite values a.e. such as stated below, where we recall that $E^{i}$ stands
for the set of endpoints of the partition ${\mathcal{P}}^{i}$, $i=1,2$.

######  Proposition 3.3.

Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be sequences of partitions. If
$\mathcal{P}^{2}$ is log-balanced a.e. (or in measure) with respect to some
measure $\lambda$ and $\lambda(E^{1})=0$, then the Lochs index
$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})$ is finite a.e. with respect to
$\lambda$ for each $n\in\mathbb{N}$.

###### Proof.

Let $n\in\mathbb{N}$. Since $\mathcal{P}^{2}$ is log-balanced a.e. (or in
measure), $\lambda(E^{2})=0$. Let $J$ be the union of all the intervals
$I_{n}^{1}$ in $P_{n}^{1}$ such that $\lambda(I_{n})=0$. Clearly,
$\lambda(J)=0$. Hence, it suffices to prove that
$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})$ is finite for every
$x\in[0,1]\setminus(E^{1}\cup E^{2}\cup J)$. For that purpose, let
$x\in[0,1]\setminus(E^{1}\cup E^{2}\cup J)$. By Proposition 3.1,
$\lambda(I_{\ell}^{2}(x))\to 0$ as $\ell\to\infty$. As
$\lambda(I_{n}^{1}(x))>0$, there must be some $\ell\in\mathbb{N}$ such that
$I_{n}^{1}(x)\nsubseteq I_{\ell}^{2}(x)$ and thus
$L_{n}(x,\mathcal{P}_{1},\mathcal{P}^{2})$ is finite. ∎

######  Proposition 3.4.

Let $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ be a sequence of partitions
that is log-balanced a.e. (resp. in measure) with respect to some measure
$\lambda$. If $\mu$ is another Borel probability measure equivalent to
$\lambda$ (i.e., both $d\mu/d\lambda$ and $d\lambda/d\mu$ are bounded), then
$\mathcal{P}$ is also log-balanced a.e. (resp. in measure) with respect to
$\mu$ with the same weight function.

###### Proof.

By Proposition 3.1, $\mu(I_{n}(x))\to 0$ as $n\to\infty$ for every
$x\in[0,1]\setminus E$. Now the proof can be completed along the same lines as
in the proof of [BDK06, Lemma 2.4] in order to prove that
$\lim_{n\to\infty}\frac{\log\lambda(I_{n}(x))}{\log\mu(I_{n}(x))}=1$ a.e. ∎

For the validity of Theorem 2.8, we assume that the weight $f_{2}$ of
$\mathcal{P}^{2}$ is nondecreasing. The following lemma shows that this
assumption does not per se rules out any particular a.e. log-balanced self-
refining sequence $\mathcal{P}^{2}$.

######  Proposition 3.5.

Every self-refining a.e. log-balanced sequence of partitions $\mathcal{P}$
with respect to some measure $\lambda$ admits some nondecreasing a.e. weight
function with respect to $\lambda$.

###### Proof.

Let $f$ be an a.e. weight function of $\mathcal{P}$. Let $x\in[0,1]\setminus
E$ for which $-\log\lambda(I_{n}(x))/f(n)\to 1$ as $n\to\infty$. Let
$g(n)=-\log\lambda(I_{n}(x))$. By construction, $g(n)/f(n)\to 1$ as
$n\to\infty$. Hence, as $f$ is an a.e. weight function of $\mathcal{P}$, so is
$g$. Moreover, since $\mathcal{P}$ is self-refining, the definition of $g$
implies that $g$ is nondecreasing. ∎

The next result shows that a sequence of partitions with polynomially many
intervals at each depth has zero entropy a.e.

######  Proposition 3.6.

Let $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ be a sequence of partitions and
let $\lambda$ be a Borel probability measure on $[0,1]$. Suppose that the
number $\\#(P_{n})$ of intervals at depth $n$ is such that
$\log\\#(P_{n})=o(n)$ as $n\to\infty$. Then, $\mathcal{P}$ has zero entropy
a.e.

###### Proof.

Notice that $\log\\#(P_{n})=o(n)$ implies
$\limsup_{n\to\infty}\\#(P_{n})^{1/n}=1$. Thus, by the root test,
$\sum_{n=0}^{\infty}\\#(P_{n})e^{-\epsilon n}<\infty$ for each $\epsilon>0$.

Let $h_{n}(x):=-\log\lambda(I_{n}(x))/n$. And, for each $\epsilon>0$ and
$n\in\mathbb{N}$, let

$A_{n,\epsilon}=\\{x\in[0,1]\setminus
E:h_{n}(x)\geq\epsilon\\}=\\{x\in[0,1]\setminus E:\lambda(I_{n}(x))\leq
e^{-\epsilon n}\\}\ .$

Therefore,

$\lambda(A_{n,\epsilon})\leq\sum_{I_{n}\in\mathcal{P}_{n}:\,I_{n}\cap
A_{n,\epsilon}\neq\emptyset}\lambda(I_{n})\leq\\#(P_{n})e^{-\epsilon n}\ .$

Since $\sum_{n=0}^{\infty}\\#(P_{n})e^{-\epsilon n}<\infty$, the
Borel–Cantelli Lemma implies

$\lambda(\\{x:\,x\in A_{n,\epsilon}\ \text{i.o.}\\})=0.$

Thus, $x\notin A_{n,\epsilon}$ for $n$ large enough a.e., that is,
$\lim_{n\to\infty}h_{n}(x)=0$ a.e.∎

##  4\. Main examples

In this section, we introduce our main examples of sequences of partitions and
discuss their log-balancedness. Throughout this section we prove Theorem 2.4.

This section is organized as follows. In Section 4.1, we show that one can
give an explicit log-balanced sequence of partitions with weight $f$ for any
given function $f$ that tends to infinity. In Section 4.2, we make explicit
the connection between sequences of partitions and numeration systems. In
Section 4.3, we build log-balanced sequences of partitions from fibred
systems. In Section 4.4, we consider fibred numeration systems with positive
entropy, which includes the sequences of partitions corresponding to the
binary numeration system, the beta-numeration, and continued fraction
expansions. In Section 4.5, we introduce the Stern-Brocot sequence of
partitions, which is induced by a fibred system of zero entropy. In Section
4.6, we present some examples of zero-entropy sequences of partitions not
induced by fibred systems, namely the Farey sequence of partitions. Lastly, in
Section 4.7, we discuss a sequence of partitions associated with the three
distance theorem.

###  4.1. A realization result

Next proposition shows that for any $f:\mathbb{N}\to\mathbb{R}_{\geq 0}$ so
that $f(n)\to\infty$ as $n\to\infty$ there exists a sequence of partitions
with $f$ as an a.e. weight function with respect to the Lebesgue measure.

######  Proposition 4.1.

Let $f:\mathbb{N}\to\mathbb{R}_{\geq 0}$, with $\lim_{n\to\infty}f(n)=\infty$.
Then, there exists an a.e. log-balanced sequence of partitions
$\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ with weight function $f$, with
respect to the Lebesgue measure. Moreover, if $f$ is nondecreasing, then
$\mathcal{P}$ is self-refining. Furthermore, if $n\mapsto\lfloor
e^{f(n)}\rfloor$ is (strictly) increasing, then $\mathcal{P}$ is strictly
self-refining.

###### Proof.

We build $\mathcal{P}$ by giving for each $n\in\mathbb{N}$ the set endpoints
of the intervals of $P_{n}$. For that purpose, we take as a reference the sets
$E_{k}^{\mathcal{B}}=\\{a/2^{k}:\,a\in\mathbb{N}\text{ and }0\leq a\leq
2^{k}\\}$ of endpoints of the binary partition at depth $k$.

Fix $n\in\mathbb{N}$ and consider the only integer $k\geq 0$ so that
$2^{k}\leq e^{f(n)}<2^{k+1}$. These relations allows one to perform a change
of scale between indices of depths $k$ and $n$. Let $P_{n}$ be the topological
partition of $[0,1]$ whose endpoint set is

$E_{n}=E_{k}^{\mathcal{B}}\cup\\{a/2^{k+1}:\,a=2i+1\text{ and }0\leq
i\leq\lfloor e^{f(n)}\rfloor-2^{k}-1,i\in\mathbb{N}\\}.$

Notice that $E_{k}^{\mathcal{B}}\subseteq E_{n}\subsetneq
E_{k+1}^{\mathcal{B}}$ because $E_{n}$ is $E_{k}^{\mathcal{B}}$ together with
the leftmost $\lfloor e^{f(n)}\rfloor-2^{k}$ endpoints of
$E_{k+1}^{\mathcal{B}}$. Hence, if $n\mapsto\lfloor e^{f(n)}\rfloor$ is
nondecreasing, then the sequence of partitions $\\{P_{n}\\}$ is self-refining,
and if $n\mapsto\lfloor e^{f(n)}\rfloor$ is increasing, then $P_{n}\subsetneq
P_{n+1}$.

Let $x\notin E^{\mathcal{B}}:=\bigcup_{k=0}^{\infty}E^{\mathcal{B}}_{k}$.
Then, by construction, $2^{-k-1}\leq|I_{n}(x)|\leq 2^{-k}$, that is,

$\frac{1}{2e^{f(n)}}\leq|I_{n}(x)|<\frac{2}{e^{f(n)}}.$

The fact that $f(n)\to\infty$ as $n\to\infty$ implies that

$\lim_{n\to\infty}\frac{-\log|I_{n}(x)|}{f(n)}=1\quad a.e.\qed$

######  Remark 4.2.

Notice that, in the above proposition, if $f(n)/n\to 0$ (resp.
$f(n)/n\to\infty$) as $n\to\infty$, then the sequence of partitions
$\mathcal{P}$ has $0$ (resp. $\infty$) a.e. entropy with respect to the
Lebesgue measure.

###  4.2. From sequences of partitions to numeration systems

By numeration system given by partitions, we mean a system of representation
of numbers using sequences of labels, and even of digits in most of the cases,
provided by a sequence of partitions
$\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ endowed with labels. This involves
in particular the most classical numerations for real numbers, such as $b$-ary
representations, as well as representations based on continued fractions.

A numeration system by a log-balanced sequence of partitions over the (at most
countable) alphabet $\mathcal{A}$, denoted as
${\mathcal{N}}=({\mathcal{P}},\rho)$, is defined by a strictly self-refining
sequence of partitions $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ with
$P_{0}=\\{(0,1)\\}$, assumed to be log-balanced with respect to the Lebesgue
measure, together with a sequence of labelling functions
$\rho=\\{\rho_{n}\\}_{n\geq 1}$, with $\rho_{n}:P_{n}\to\mathcal{A}$ for all
$n$, that satisfies the following condition.

  1. (H)

For each $I\in\mathcal{\mathcal{missing}}{P}_{n}$ and each distinct
$J,J^{\prime}\in P_{n+1}$ such that $J,J^{\prime}\subset I$,
$\rho_{n+1}(J)\neq\rho_{n+1}(J^{\prime})$. In other words, the restriction of
the labelling map $\rho_{n+1}$ is injective when restricted to the set
$P_{n+1}|_{I}$ of all intervals $J\in P_{n+1}$ contained in $I\in P_{n}$.

In particular, by Proposition 3.1, one has $\|P_{n}\|=\sup\\{|I|:\,I\in
P_{n}\\}$ tends to $0$ as $n\to\infty$. The sequence of partitions is thus
generating (i.e., for a.e. $x,y\in[0,1]$, if $x\neq y$, then there exist
$n\in\mathbb{N}$, $P,Q\in P_{n}$, $P\neq Q$, such that $x\in P$ and $y\in Q$.)

In full generality, according e.g. to the formalism developed in [BBLT06], a
numeration system is a triple $(X,\mathcal{A},\varphi)$, where $X$ is a set
(the set of elements to be represented), $\mathcal{A}$ a finite or countable
set (the alphabet of the representation), and $\varphi$ an injective map
$\varphi\colon X\rightarrow\mathcal{A}^{{\mathbb{N}}}$. Accordingly, given a
sequence of partitions ${\mathcal{P}}$ that satisfies the above conditions, we
want to define a map that associates with every $x$ in $[0,1]$ the sequence of
labels of intervals to which $x$ belongs. Such a map is well-defined on points
that do not belong to the set $E$ of endpoints of the intervals of the
partitions. In any case, the set $E$ is a countable set111Of course, it would
be possible to define (two) finite expansions for the elements in $E$, but we
choose to concentrate just on $[0,1]\setminus E$, the set corresponding to
infinite expansions.. Hence here $X$ is equal to $[0,1]\setminus E$ and this
gives a coding map $\varphi$ that associates with an element of
$[0,1]\setminus{E}$ the sequence of labels of the intervals to which it
belongs:

$\varphi:[0,1]\setminus E\rightarrow\mathcal{A}^{\mathbb{N}},\
x\mapsto\rho_{1}(I_{1}(x))\rho_{2}(I_{2}(x))\ldots\text{ where }x\in
I_{n}(x)\text{ for all }n.$

Let us check that the map $\varphi$ is injective. Let $x,y\in X$ and suppose
$\varphi(x)=\varphi(y)$. Observe that $x$ and $y$ both belong to $[0,1]$. Let
us prove by induction that $x$ and $y$ belong to the same interval $I_{n}\in
P_{n}$ for all $n$. Assume that the induction property holds for some positive
$n$. The points $x,y$ thus belong to the same interval $I_{n}\in P_{n}$, and
by Condition (H), $x,y$ belong to the same $I_{n+1}\in P_{n+1}$, which ends
the induction proof. Thus, $x,y\in\bigcap_{n\geq 1}I_{n}$. Since $\\{I_{n}\\}$
is a nested sequence of intervals whose length tends to $0$, $\bigcap_{n\geq
1}I_{n}$ has only one element. Hence, $x=y$. We thus get a numeration system
as defined above. In other words, by assumption (H), we have for any
$x\in[0,1]\setminus E$ that $\\{x\\}=\bigcap_{n\geq 1}\overline{I_{n}(x)}$ and
the sequence of labels $\\{\rho_{n}(I_{n}(x))\\}_{n\geq 1}$ encodes $x$
univocally. By definition, each interval of depth $n$ in the partition $P_{n}$
gathers all numbers in $[0,1]\setminus E$ whose representations, as sequences
of labels, coincide until depth $n$.

######  Remark 4.3.

Examples of labelled sequences of partitions are given below. When each
interval in $P_{n}$ is divided into proper subintervals in $P_{n+1}$, the
labels $\rho_{n+1}$ usually produce digits that will be used to provide
suitable expansions of the real numbers of the unit interval. This is for
instance the case of the binary numeration (see Section 4.4). For other
sequences of partitions, such as the Farey one in Section 4.6, the labelling
$\rho_{n}$ might seem to be less relevant at first view. However, we will see
that it is connected to the coding of dynamical systems in the context of
characteristic Sturmian words, as developed in Section 4.6.2.

###  4.3. Fibred systems

Often, a sequence of partitions, which allows for the definition of a
numeration system as described in Section 4.2, can be defined in dynamical
terms. A particularly relevant framework in this setting is the one of fibred
systems as introduced in [Sch95], and in [BDK06, DF01] for the notion of a
number-theoretic fibred system.

In this paper, we say that the pair $([0,1],T)$ is a fibred system if the
transformation $T\colon[0,1]\to[0,1]$ is such that there exist a finite or
countable set ${\mathcal{A}}$ and a topological partition
${P}=\\{I_{a}\\}_{{a\in{\mathcal{A}}}}$ of $[0,1]$ for which the restriction
$T_{a}$ of $T$ to $I_{a}$ is injective and continuous, for each
$a\in{\mathcal{A}}$.

We associate with a fibred system $([0,1],T)$ a sequence of partitions in the
usual dynamical way. Let $T^{-1}{P}$ denote the partition
$\\{T^{-1}I_{a}\\}_{a\in\mathcal{A}}$. We define, for any $n\geq 1$, the
partition ${P}_{n}$ as the join partition $\bigvee_{i=0}^{n-1}T^{-j}{P}$ made
up of the sets of the form $\bigcap_{j=0}^{n-1}T^{-j}I_{a_{j}}$, for all
choices of $a_{0},\ldots,a_{n-1}\in\mathcal{A}$, where each
$I_{a_{j}}\in{{P}}$. For $n=0$, we define $P_{0}=\\{(0,1)\\}$. Now, we define
a sequence of labelling maps $\\{\rho_{n}\\}_{n\geq 1}$ as follows:

$\rho_{n}\left(\bigcap_{j=0}^{n-1}T^{-j}I_{a_{j}}\right):=a_{n-1}\quad\text{for
all choices of }a_{0},\ldots,a_{n-1}\in\mathcal{A}.$

Note that $\rho_{n}=\rho_{1}\circ T^{n-1}$ for each $n$. If, moreover,
${\mathcal{P}}=\\{P_{n}\\}_{n\in\mathbb{N}}$ is log-balanced a.e. or in
measure with respect to the Lebesgue measure and it is strictly self-refining,
then $\mathcal{P}$ satisfies the conditions given in Section 4.2 and thus
provides a numeration system $({\mathcal{P}},\rho)$. This numeration system
associated with the map $T$ together with the topological partition $P$ (whose
elements are indexed by the alphabet $\mathcal{A}$) is said to be, here, a
fibred numeration system. The injectivity of the restriction $T_{a}$ of $T$ to
$I_{a}$ is consistent with the injectivity requirement of condition (H).

Fibred systems as above defined are particular cases of the more general
fibred systems developed in [BBLT06]. For a fibred system $([0,1],T)$ as
above, the corresponding set $X$ and the corresponding partition
$\\{X_{a}\\}_{a\in\mathcal{A}}$ of $X$ in the definition of fibred system
given in Definition 2.3 of [BBLT06] are given by:

$X=X(T,P):=\bigcap_{j=0}^{\infty}T^{-j}\bigcup_{a\in\mathcal{A}}I_{a}\quad\text{and}\quad
X_{a}=X\cap I_{a}\ \text{for each }a\in\mathcal{A}.$

Clearly, $T(X)\subseteq X$ and the restriction $T_{a}$ of $T$ on $X_{a}$ is
injective. In our context, the set $X$ equals the set $[0,1]\setminus E$ where
$E$ is the set of endpoints of $\mathcal{P}$.

A fibred system $([0,1],T)$ admits _an invariant and ergodic Borel probability
measure_ $\lambda$ if, for every Borel set $B$, the following assertions hold:
(i) $\lambda(T^{-1}(B))=\lambda(B)$ and (ii) $T^{-1}(B)=B$ implies that $B$ is
a set of measure $0$ or $1$. We then denote it as $([0,1],T,\lambda)$.
According to [BDK06, Definition 2.2], a fibred system is called a number-
theoretic fibred system if $T$ has an ergodic and invariant probability
measure which is equivalent to the Lebesgue measure. A fibred system with an
invariant and ergodic probability measure $\lambda$ has then a well-defined
entropy (see [PY98, Chap. 8]). The following theorem is a consequence of the
Shannon–McMillan–Breiman Theorem (see [PY98, p. 134]).

######  Theorem 4.4.

Let $([0,1],T,\lambda)$ be a fibred number-theoretic system (endowed with an
ergodic invariant measure $\lambda$ of the probability space $[0,1]$). Let
$\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ be the sequence of partitions
associated with this fibred system. If

$H_{1}(\mathcal{P},\lambda)=-\sum_{I\in
P_{1}}\lambda(I)\log\lambda(I)<\infty,$

then for $\lambda$-almost every $x$, the following limits exist and satisfy

$h=\lim_{n\to\infty}-\frac{\log\lambda(I_{n}(x))}{n}=-\lim_{n\to\infty}\frac{1}{n}\sum_{I\in
P_{n}}\lambda(I)\log\lambda(I)\,.$

In particular, the sequence of partitions ${\mathcal{P}}$ is log-balanced a.e.
with respect to $\lambda$ and the map $f:n\mapsto hn$ is a corresponding
weight function.

Under the above assumption, we thus get, from a fibred number-theoretic
system, a log-balanced sequence of partitions, as described in Section 4.2. By
Proposition 3.4, if $\mu$ is another probability measure equivalent to
$\lambda$, then $\mathcal{P}$ is also log-balanced a.e. for $\mu$ with $f$ as
weight function.

###  4.4. Fibred systems with positive entropy

Two classical instances of ergodic measure preserving fibred systems with
positive entropy are the binary numeration system (in general, the beta-
numeration) and the Gauss map producing continued fractions expansions. We
describe them below.

####  4.4.1. The binary numeration system

The binary numeration system is the fibred number-theoretic system associated
with the map $T:x\mapsto 2x\mod 1$ and the partition $P=\\{(0,1/2),(1/2,1)\\}$
with respect to the Lebesgue measure. Its entropy for the Lebesgue measure is
$\log 2$. It associated sequence of partitions is the binary sequence of
partitions defined as $\mathcal{B}=\\{B_{n}\\}_{n\in\mathbb{N}}$, where

$B_{n}=\left\\{\left(0,\frac{1}{2^{n}}\right),\left(\frac{1}{2^{n}},\frac{2}{2^{n}}\right),\ldots,\left(\frac{2^{n}-1}{2^{n}},1\right)\right\\}.$

Hence, the endpoints of the intervals in $B_{n}$ are $E_{n}^{\mathcal{B}}$ are
the points $a/2^{n}$ for $a=0,1,\ldots,2^{n}$. The binary sequence of
partitions $\mathcal{B}$ is a.e. log-balanced with weight function
$f_{\mathcal{B}}(n)=(\log 2)n$ with respect to the Lebesgue measure.

####  4.4.2. The decimal numeration system.

The decimal numeration system is the fibred number-theoretic system associated
with the map $T:x\mapsto 10x\mod 1$ with the partition
$P=\\{(a/10,(a+1)/10)\\}_{a=0,\ldots,9}$ with respect to the Lebesgue measure.
We denote by $\mathcal{D}=\\{D_{n}\\}_{n\in\mathbb{N}}$ the decimal sequence
of partitions associated with this fibred systems. It admits as an a.e. weight
function $f_{\mathcal{D}}(n)=(\log 10)n$ with respect to the Lebesgue measure.

####  4.4.3. Beta-numeration sequence of partitions

The beta-numeration sequence of partitions $\mathcal{BE}$ is the sequence of
partitions associated with the the beta-numeration, i.e., the fibred system
associated with the map $x\mapsto\beta x\mod 1$, where $\beta$ is a given real
number with $\beta>1$. Its entropy for the Lebesgue measure is $\log\beta$. It
is a.e. log-balanced with weight function $f_{\mathcal{B}}(n)=(\log\beta)n$.
This numeration has been introduced in [Rén57]. For more on the length of the
fundamental intervals, see e.g. [FW12]. When $\beta=2$, one recovers the
binary numeration and when $\beta=10$, the decimal one.

####  4.4.4. Continued fraction sequence of partitions

The continued fraction expansions correspond to the fibred system associated
with the Gauss map $T_{G}$ such that

$T_{G}(x)=\\{1/x\\}\quad\text{if }x\neq 0\qquad\text{and}\qquad T_{G}(0)=0,$

where $\\{x\\}$ denotes the fractional part of $x$ and the partition
$\\{(1/(a+1),1/a)\\}_{a\geq 1}$. The corresponding alphabet is the set of the
positive integers. The labelling map $\rho_{1}$ is given by
$\rho_{1}(x)=\lfloor 1/x\rfloor$ and $\rho_{n}(x)=\rho_{1}(T_{G}^{n-1}(x))$.
We denote by $\mathcal{CF}$ the sequence of partitions associated with this
fibred system, called the continued fraction sequence of partitions.

We use the standard notation for continued fractions

$x=[0;a_{1}(x),a_{2}(x),a_{3}(x),\ldots]=\cfrac{1}{a_{1}(x)+\cfrac{1}{a_{2}(x)+\cfrac{1}{a_{3}(x)+\dotsb}}}$

with the last partial quotient larger than 1 in the case of rationals numbers.
As usual, the numerators and denominators of the $n$-th convergent
$[0;a_{1}(x),a_{2}(x),\ldots,a_{n}(x)]$ are called continuants of the number
$x$. They are denoted by $p_{n}=p_{n}(x)$ and $q_{n}=q_{n}(x)$. For any $n\geq
1$, the following recurrence relations hold

$\displaystyle p_{n}=a_{n}p_{n-1}+p_{n-2},\ p_{0}=0,\ p_{-1}=1,$
$\displaystyle q_{n}=a_{n}q_{n-1}+q_{n-2},\ q_{0}=1,\ q_{-1}=0,$

together with the equality

(5) $q_{n}p_{n-1}-p_{n}q_{n-1}=(-1)^{n}.$

The fundamental interval $I_{n}^{\mathcal{CF}}(x)$ of depth $n$ associated
with $x$ in the continued fraction expansion has as endpoints the fractions
$p_{n}/q_{n}$ and $(p_{n-1}+p_{n})/(q_{n-1}+q_{n})$. More precisely, by
[Khi97, p. 57], one has

(6)
$I_{n}^{\mathcal{CF}}(x)=\begin{cases}\left(\dfrac{p_{n}}{q_{n}},\dfrac{p_{n-1}+p_{n}}{q_{n-1}+q_{n}}\right)&\text{if
$n$ is even}\vskip 12.0pt plus 4.0pt minus 4.0pt\\\
\left(\dfrac{p_{n-1}+p_{n}}{q_{n-1}+q_{n}},\dfrac{p_{n}}{q_{n}}\right)&\text{if
$n$ is odd}.\end{cases}$

In particular,

(7) $\left|I_{n}^{\mathcal{CF}}(x)\right|=\frac{1}{q_{n}(q_{n}+q_{n-1})}.$

Let the _Gauss measure_ be $d\mu=1/((1+x)\log 2)\,dx$. Since $T_{G}$ is an
ergodic measure preserving transformation with respect to the Gauss measure
(see, for instance, [PY98, p. 106]), the dynamical system $([0,1],T_{G},\mu)$
is a fibred number-theoretic system. Moreover, as the Gauss measure is
absolutely continuous with respect to the Lebesgue measure, it can be shown,
by relying on Theorem 4.4, that the entropy of the continued fraction sequence
of partitions $\mathcal{CF}$ is $\pi^{2}/(6\log 2)$, with respect to both its
invariant measure and the Lebesgue measure (see [IK02, Cor. 4.1.28] for a
detailed proof). It follows that the sequence of partitions $\mathcal{CF}$
admits as an a.e. weight function

(8) $f_{\mathcal{CF}}(n)=\frac{\pi^{2}}{6\log 2}n$

with respect to the Lebesgue measure (and the Gauss measure as well).

An alternative derivation of the value of the a.e. entropy of $\mathcal{CF}$
follows from Khinchin–Lévy’s Theorem, which asserts that

(9) $\lim_{n\to\infty}\frac{\log q_{n}(x)}{n}=\frac{\pi^{2}}{12\log
2}\quad\text{ a.e.\ $x$}.$

We also recall the Borel–Bernstein Theorem (see [Bor09, Ber11]).

######  Theorem 4.5 (Borel-Berstein).

The set of real numbers $x$ such that $a_{n}\leq k_{n}$ for infinitely many
$n$, where the $k_{n}$ are positive integers is of zero measure if and only if
$\sum_{n}1/k_{n}=\infty$.

###  4.5. A fibred numeration system with zero entropy: the Stern-Brocot
system

The Stern-Brocot sequence of partitions, denoted as $\mathcal{SB}$, is the
sequence of partitions associated with the Farey fibred system whose map is
the Farey map

$T_{F}=\begin{cases}\dfrac{1}{1-x}-1&=\dfrac{x}{1-x}\quad\text{if
}x\in[0,1/2]\vskip 12.0pt plus 4.0pt minus 4.0pt\\\
\dfrac{1}{x}-1&=\dfrac{1-x}{x}\quad\text{if }x\in[1/2,1]\end{cases}$

and the partition $P=\\{(0,1/2),(1/2,1)\\}$. This sequence has been widely
studied, see e.g. [MZ04a]. Even if the partition is nonuniform, considering
logarithms of lengths allows the balance property in measure.

The standard construction of the sequence
$\mathcal{SB}=\\{\text{\emph{SB}}_{n}\\}_{n\in\mathbb{N}}$ is as follows (see
Figure 1 for an illustration): we start with
$\text{\emph{SB}}_{0}=\\{(0/1,1/1)\\}$, and for each $n\in\mathbb{N}$,
$\text{\emph{SB}}_{n+1}$ arises from $\text{\emph{SB}}_{n}$ by dividing each
interval $(p/q,p^{\prime}/q^{\prime})$ of $\text{\emph{SB}}_{n-1}$ into two
subintervals by its mediant $(p+p^{\prime})/(q+q^{\prime})$.

$\mathcal{SB}_{0}:$$0/1$$1/1$$\mathcal{SB}_{1}:$$1/2$$\mathcal{SB}_{2}:$$1/3$$2/3$$\mathcal{SB}_{3}:$$1/4$$2/5$$3/4$$3/5$$\mathcal{SB}_{4}:$$1/5$$2/7$$3/8$$3/7$$4/7$$5/8$$5/7$$4/5$
Figure 1. The Stern-Brocot sequence of partitions

We denote by $E^{\mathcal{SB}}_{n}$ the set of endpoints of the intervals in
$\text{\emph{SB}}_{n}$.

Let $x\in[0,1]$ be an irrational number and let $\\{p_{m}/q_{m}\\}$ stand for
its sequence of convergents. We recall that the convergents satisfy the
following mediant-construction [Khi97, p. 14–15]: if $m$ is even, then

(10) $\frac{p_{m}}{q_{m}}\leq
x\leq\frac{p_{m+1}}{q_{m+1}}=\frac{a_{m+1}p_{m}+p_{m-1}}{a_{m+1}q_{m}+q_{m-1}}\leq\cdots\leq\frac{p_{m-1}+p_{n}}{q_{m-1}+q_{m}}\leq\frac{p_{m-1}}{q_{m-1}},$

whereas if $m$ is odd, then

(11)
$\frac{p_{m-1}}{q_{m-1}}\leq\frac{p_{m-1}+p_{n}}{q_{m-1}+q_{m}}\leq\cdots\leq\frac{a_{m+1}p_{m}+p_{m-1}}{a_{m+1}q_{m}+q_{m-1}}=\frac{p_{m+1}}{q_{m+1}}\leq
x\leq\frac{p_{m}}{q_{m}}.$

The following result is well known (see [MZ04b, Lemma 1]).

######  Proposition 4.6.

Let $x\in[0,1]$ be an irrational and let $n\in\mathbb{N}$. Then, the interval
in $SB_{n}$ containing $x$ is

$I_{n}^{\mathcal{SB}}(x)=\begin{cases}\left(\dfrac{p_{m}}{q_{m}},\dfrac{(r+1)p_{m}+p_{m-1}}{(r+1)q_{m}+q_{m-1}}\right)&\text{if
$m$ is even}\vskip 12.0pt plus 4.0pt minus 4.0pt\\\
\left(\dfrac{(r+1)p_{m}+p_{m-1}}{(r+1)q_{m}+q_{m-1}},\dfrac{p_{m}}{q_{m}}\right)&\text{if
$m$ is odd,}\end{cases}$

where $m:=m(x,n)$ and $r:=r(x,n)$ are the unique integers such that

$\sum_{i=1}^{m}a_{i}\leq n<\sum_{i=1}^{m+1}a_{i}\quad\text{and}\quad
r=n-\sum_{i=1}^{m}a_{i}.$

As a consequence, one has

$\left|I_{n}^{\mathcal{SB}}(x)\right|=\frac{1}{((r+1)q_{m}+q_{m-1})q_{m}}.$

The next two results show that, with respect to the Lebesgue measure, the
Stern-Brocot sequence of partitions is log-balanced in measure but not a.e.

######  Proposition 4.7.

The Stern-Brocot sequence of partitions admits as weight function in measure
with respect to the Lebesgue measure

$f_{\mathcal{SB}}(n):=\frac{\pi^{2}}{6}\frac{n}{\log n}\quad\text{for each
}n\geq 2.$

###### Proof.

Let $x\in[0,1]$ an irrational number and let $n\in\mathbb{N}$. Let $m$ and $r$
be as in Proposition 4.6, i.e., $\sum_{i=1}^{m}a_{i}\leq
n<\sum_{i=1}^{m+1}a_{i}$ and $r=n-\sum_{i=1}^{m}a_{i}$. Hence,

$\frac{1}{2(r+1)q_{m}^{2}}\leq\left|I_{n}^{\mathcal{SB}}(x)\right|\leq\frac{1}{(r+1)q_{m}^{2}}.$

Therefore, one has

(12) $-\frac{\log|I_{n}^{\mathcal{SB}}(x)|}{n/\log n}=\frac{\log(r+1)}{n/\log
n}+2\frac{\log q_{m}}{n/\log n}+O\left(\frac{\log n}{n}\right)\quad\text{as
}n\to\infty.$

Since $r\leq n$, the first term in the above equation tends to zero when
$n\to\infty$ a.e. We write

(13) $\frac{\log q_{m}}{n/\log n}=\frac{\log q_{m}}{m}\frac{\log n}{\log
m}\frac{m\log m}{n}.$

Notice that, by (9), the first factor $\frac{\log q_{m}}{m}$ on the above
right-hand side tends to $\frac{\pi^{2}}{12\log 2}$ as $m\to\infty$ a.e. Let
us prove that

(14) $\lim_{n\to\infty}\frac{\log n}{\log m}=1\quad\text{a.e.\ }x.$

(We recall that $m$ depends on $x$ and $n$.) By [DV86, Corollary 1], for a.e.
$x$ and large enough $m$ (depending on $x$),

$\sum_{i=1}^{m}a_{i}\leq\frac{1+o(1)}{\log 2}m\log m+\max_{1\leq i\leq
m}a_{i}.$

Fix $\epsilon>0$. By Borel–Bernstein Theorem (see Theorem 4.5), for a.e. $x$
and for $m$ large enough (depending on $x$), one has

$a_{m}\leq m(\log m)^{1+\epsilon}.$

For a.e. $x$ and $n$ large enough (depending on $x$), this yields

$\displaystyle m\leq n<\sum_{i=1}^{m+1}a_{i}$
$\displaystyle\leq\left(\frac{1+o(1)}{\log
2}\log(m+1)+(\log(m+1))^{1+\epsilon}\right)(m+1)$ $\displaystyle=O(m(\log
m)^{1+\epsilon}).$

Hence, $\log n=\log m+O(\log\log m)$ as $n\to\infty$, a.e. $x$. This proves
(14).

In [Khi35, p. 377], Khinchin proved that $\frac{\log 2}{m\log
m}\sum_{i=1}^{m}a_{i}$ tends to $1$ in measure as $m\to\infty$. Since, by
definition, $\sum_{i=1}^{m}a_{i}\leq n<\sum_{i=1}^{m+1}a_{i}$, this implies
that

(15) $\lim_{n\to\infty}\frac{m\log m}{n}=\log 2\quad\text{in measure}.$

With Equation (13), the result follows. ∎

######  Proposition 4.8.

The Stern-Brocot sequence of partitions is not log-balanced a.e. with respect
to the Lebesgue measure.

###### Proof.

If the Stern-Brocot sequence of interval partitions $\mathcal{SB}$ were to
admit an a.e. weight function $f$ with respect to the Lebesgue measure, then,
because of Proposition 4.7, $f(n)/f_{\mathcal{SB}}(n)\to 1$ as $n\to\infty$.
Thus, it suffices to prove that $f_{\mathcal{SB}}$ is not an a.e. weight
function for $\mathcal{SB}$.

Let $S_{m}=S_{m}(x,n):=\sum_{i=1}^{m}a_{i}$. Since $n\geq S_{m}$, by virtue of
[Phi88, Theorem 1] we have that

$\liminf_{n\to\infty}\frac{m\log m}{n}\leq\liminf_{n\to\infty}\dfrac{m\log
m}{S_{m}}=0\quad\text{a.e.\ }x.$

Notice however that (15) holds. As a consequence, $\frac{m\log m}{n}$ does not
converge as $n\to\infty$ a.e. As the first two factors on the right-hand side
of (13) converge as $n\to\infty$ a.e., $\log q_{m}/(n/\log n)$ does not and,
consequently, neither does the left-hand side of (12). This proves that
$f_{\mathcal{SB}}$ is not an a.e. weight function for $\mathcal{SB}$. ∎

The Stern-Brocot sequence of partitions has zero Shannon entropy with respect
to the Lebesgue measure (see [BCP+20]). Moreover, the following also holds.

######  Proposition 4.9.

The Stern-Brocot sequence of partitions has zero entropy a.e. with respect to
the Lebesgue measure.

###### Proof.

Letting $m$ be as in the proof of Proposition 4.7 and combining (12), (13),
and (9), it follows that

$-\frac{\log|I_{n}^{\mathcal{SB}}(x)|}{n}=O\left(\frac{m}{n}\right)\quad\text{as
}n\to\infty,\text{ a.e.\ }x.$

By [DV86, Corollary 1], for a.e. $x$, and for $n$ large enough (depending on
$x$), $n\geq\sum_{i=1}^{m}a_{i}\geq m\log m$. The proposition follows. ∎

###  4.6. The Farey sequence of partitions

In this section, we introduce two zero entropy sequences of partitions, namely
the Farey sequence of partitions and the closely related Sturmian sequence of
partitions. Both are nonfibred examples having zero entropy. The fact that
they are indeed zero entropy follows from Proposition 3.6 because they have
polynomially many intervals at each depth.

####  4.6.1. The Farey sequence of partitions ${\mathcal{F}}$

The _Farey sequence of partitions_ $\mathcal{F}=\\{F_{n}\\}_{n\in\mathbb{N}}$
is defined as follows. Each of the partitions $F_{n}$ is determined by the set
$E_{n}^{\mathcal{F}}$ of endpoints of its intervals, i.e.,

$E^{\mathcal{F}}_{n}:=\left\\{\frac{p}{q}:\,p,q\geq 1,\ \gcd(p,q)=1\text{ and
}q\leq n+1\right\\}.$

The set of endpoints $E^{\mathcal{F}}_{n}$ thus corresponds to the Farey
sequence of order $n+1$ which is the sequence of fractions $h/k$ with
$(h,k)=1$ and $1\leq h\leq k\leq n+1$, arranged in increasing order between 0
and 1, and studied e.g. in [Hal70, KSRSRS82].

Equivalently, $\mathcal{F}$ can be built recursively as follows. Let
$F_{0}=\\{(0/1,1/1)\\}$ and, for each $n\in\mathbb{N}$, let $F_{n+1}$ be the
partition that arises from $F_{n}$ by dividing each of the intervals
$(p/q,p^{\prime}/q^{\prime})$ such that $q+q^{\prime}$ is at most $n+2$ into
two subintervals by its mediant $(p+p^{\prime})/(q+q^{\prime})$, while keeping
all the other intervals of $F_{n}$ unchanged.

The construction of the Farey sequence of partitions closely resembles the
construction of the Stern-Brocot sequence of partitions given in Section 4.5.
In fact, the only difference is that when constructing the sequence of
partitions $\mathcal{SB}$ we divide every interval $(a/c,b/d)$ of
$\text{\emph{SB}}_{n}$ into two subintervals, whereas when constructing
$\mathcal{F}$ only those intervals $(p/q,p^{\prime}/q^{\prime})$ of $F_{n}$
which satisfy $q+q^{\prime}\leq n+2$ are divided. Compare Figures 1 and 2.

$\mathcal{F}_{0}:$$0/1$$1/1$$\mathcal{F}_{1}:$$1/2$$\mathcal{F}_{2}:$$1/3$$2/3$$\mathcal{F}_{3}:$$1/4$$3/4$$\mathcal{F}_{4}:$$1/5$$2/5$$3/5$$4/5$
Figure 2. The Farey sequence of partitions

By the definition of $E_{n}^{\mathcal{F}}$, it is clear that $F_{n}$ consists
of $O(n^{2})$ intervals and thus Proposition 3.6 implies that $\mathcal{F}$
has zero entropy. Notice that, instead, each partition $\text{\emph{SB}}_{n}$
consists of $2^{n}$ intervals.

Let us recall some basic facts regarding the Farey sequence.

######  Theorem 4.10 ([Hal70, HW08]).

Two irreducible fractions $p/q$ and $p^{\prime}/q^{\prime}$ in $[0,1]$ are
consecutive endpoints in $\mathcal{F}_{n}$ if and only if $q\leq n+1$,
$q^{\prime}\leq n+1$, $|p^{\prime}q-pq^{\prime}|=1$ and $q+q^{\prime}>n+1$.

The following result is probably folklore. However, given the lack of a
suitable reference for it, we give a precise statement and a proof for the
sake of completeness.

######  Proposition 4.11.

Let $x\in[0,1]$ be an irrational and let $n\in\mathbb{N}$. Then, the interval
in $F_{n}$ containing $x$ is

$I_{n}^{\mathcal{F}}(x)=\begin{cases}\left(\dfrac{p_{m}}{q_{m}},\dfrac{(r+1)p_{m}+p_{m-1}}{(r+1)q_{m}+q_{m-1}}\right)&\text{if
$m$ is even}\vskip 12.0pt plus 4.0pt minus 4.0pt\\\
\left(\dfrac{(r+1)p_{m}+p_{m-1}}{(r+1)q_{m}+q_{m-1}},\dfrac{p_{m}}{q_{m}}\right)&\text{if
$m$ is odd,}\end{cases}$

where $m:=m(x,n)$ and $r:=r(x,n)$ are the unique integers such that

(16) $(r+1)q_{m}+q_{m-1}\leq n+1<(r+2)q_{m}+q_{m-1},\ m\geq 0,\text{ and
}0\leq r<a_{m+1}.$

As a consequence,

$|I_{n}^{\mathcal{F}}(x)|=\frac{1}{((r+1)q_{m}+q_{m-1})q_{m}}.$

###### Proof.

The uniqueness of $m$ follows from the fact that (16) implies

$q_{m}+q_{m-1}\leq n+1<(a_{m+1}+1)q_{m}+q_{m-1}=q_{m+1}+q_{m}.$

The uniqueness of $m$ in turn implies the uniqueness of $r$.

Notice that (10) or (11) (according to whether $m$ is even or odd) implies
that $x$ belongs to the interval whose endpoints are the quotients
$p_{m}/q_{m}$ and $((r+1)p_{m}+p_{m-1})/((r+1)q_{m}+q_{m-1})$. As we are
assuming that $q_{m}\leq(r+1)q_{m}+q_{m-1}\leq n+1$, both quotients are
endpoints of $F_{n}$. Moreover, Theorem 4.10 implies that these quotients are
consecutive endpoints of $F_{n}$ because
$q_{m}+((r+1)q_{m}+q_{m-1})=(r+2)q_{m}+q_{m-1}>n+1$ and

$\displaystyle((r+1)p_{m}+p_{m-1})q_{m}-((r+1)q_{m}+q_{m-1})p_{m}=p_{m-1}q_{m}-q_{m-1}p_{m}=1$

by (5).∎

######  Remark 4.12.

Notice, by comparing Propositions 4.6 and 4.11, the intervals in the Stern-
Brocot $\mathcal{SB}$ and in the Farey $\mathcal{F}$ sequences of partitions
that contain a given $x$ have the same form, however they might occur at
different indices for their depth.

######  Proposition 4.13.

The Farey sequence of partitions admits as a.e. weight function with respect
to the Lebesgue measure

$f_{\mathcal{F}}(n)=2\log n\quad\text{for each }n\geq 1.$

###### Proof.

Let $x\in[0,1]$ be an irrational number. Let $m\geq 0$ as in Proposition 4.11
(i.e., $(r+1)q_{m}+q_{m-1}\leq n+1<(r+2)q_{m}+q_{m-1}$ where $0\leq
r<a_{m+1}$). Notice that $q_{m}\leq(r+1)q_{m}+q_{m-1}\leq n+1$. Notice also
that $n+1<(r+2)q_{m}+q_{m-1}\leq(r+3)q_{m}$. Similarly,
$n+1<(r+2)q_{m}+q_{m-1}\leq 2((r+1)q_{m}+q_{m-1})$. In this way, we proved
that

$\frac{1}{(n+1)^{2}}\leq\left|I_{n}^{\mathcal{F}}(x)\right|\leq\frac{2(r+3)}{(n+1)^{2}}.$

It is well-known that $m=O(\log n)$ as $n\to\infty$ (since $2^{(m-1)/2}\leq
q_{m}\leq n$). Hence, since Borel–Bernstein Theorem (Theorem 4.5) ensures that
$a_{m}=O(m(\log m)^{2})$ as $m\to\infty$, for a.e., it follows that
$r<a_{m+1}=O(\log n(\log\log n)^{2})$ a.e. As a consequence,

$-\log|I_{n}^{\mathcal{F}}(x)|=2\log(n+1)+O(\log\log n)\quad\text{as
$n\to\infty$,\quad a.e.\ }x,$

where the hidden constants in the $O$-term may depend on $x$. The result
follows.∎

####  4.6.2. The Farey sequence of partitions and Sturmian words

The Farey sequence of partitions has a particular combinatorial meaning in
symbolic dynamics by producing prefixes of so-called characteristic Sturmian
words. Indeed, given an irrational real number $\alpha\in[0,1]$ consider the
Kronecker-Weyl sequence $\\{n\alpha\\}_{n\geq 1}$ (here $\\{x\\}$ is the
fractional part of $x$). Sturmian words are obtained as binary codings of
Kronecker-Weyl sequences, thus providing a numeration system as introduced in
Section 4.2 for irrational numbers with digits in $\\{0,1\\}$. We describe it
below.

Let $\alpha$ be an irrational number in $[0,1]$. Consider the two intervals
$(0,1-\alpha)$ and $(1-\alpha,1)$. We define the sequence
$S(\alpha):=\\{s_{n}(\alpha)\\}_{n\geq 1}$ in $\\{0,1\\}^{\mathbb{N}}$
associated with $\alpha$ as follows:

$s_{n}(\alpha)=\begin{cases}0&\hbox{ if }\\{n\alpha\\}\in(0,1-\alpha)\\\
1&\hbox{ if }\\{n\alpha\\}\in(1-\alpha,1).\end{cases}$

Since $\alpha$ is assumed to be irrational, observe that the sequence
$\\{n\alpha\\}$ never takes the value $0$, nor $1-\alpha$. We will use the
notation $S(\alpha)_{[1,n]}$ for the prefix $s_{1}\cdots s_{n}$ of length $n$
of the sequence $S(\alpha)$ (considered as an infinite word over the alphabet
$\\{0,1\\}$). The sequence $S(\alpha)$ is a so-called characteristic Sturmian
word (see e.g. [Lot02, Chapter 2]). Sturmian words are among the most studied
words in word combinatorics and symbolic dynamics.

By [Ber96, Lemma 5], irrational numbers $\alpha$ that belong to a common
interval of the partition $F_{n}$ have the same prefix of length $n$ for the
characteristic Sturmian word $s_{n}(\alpha)$, while these prefixes differ if
they belong to two distinct intervals of $F_{n}$. Hence, with each interval in
the Farey partition $F_{n}$ of order $n$ is associated the prefix of length
$n$ of some characteristic Sturmain word $S(\alpha)$.

More precisely, according to [Ber96, Mig91], let $\frac{p_{1}}{q_{1}}$ and
$\frac{p_{2}}{q_{2}}$ be the endpoints of an interval in $F_{n}$ with
$\frac{p_{1}}{q_{1}}\neq 0$, $\frac{p_{2}}{q_{2}}\neq 1$ and
$\frac{p_{1}}{q_{1}}<\frac{p_{2}}{q_{2}}$. Let $\alpha$ be an irrational
number in $[\frac{p_{1}}{q_{1}},\frac{p_{2}}{q_{2}}].$ If $\alpha$ belongs to
$[\frac{p_{1}}{q_{1}},\frac{p_{1}+p_{2}}{q_{1}+q_{2}}]$, then
$S(\alpha)_{[1,n+1]}=S(\alpha)_{[1,n]}0$, and if
$\alpha\in[\frac{p_{1}+p_{2}}{q_{1}+q_{2}},\frac{p_{2}}{q_{2}}]$, then
$S(\alpha)_{[1,n+1]}=S(\alpha)_{[1,n]}1$. Moreover, for all irrational
$\alpha$ in $[\frac{p_{1}}{q_{1}},\frac{p_{2}}{q_{2}}]$,
$S(\alpha)]_{[1,n+1]}$ is a palindrome if and only if $q_{1}+q_{2}=n+2$. This
thus allows the definition of a labelling function
$\rho_{n}:F_{n}\to\\{0,1\\}$ such as introduced in Section 4.2 that maps each
interval of $F_{n}$ to the last letter $s_{n+1}$ of the prefix
$S(\alpha)_{[1,n+1]}$ of the characteristic Sturmian word $S(\alpha)$. The
labelling function $\rho=\\{\rho_{n}\\}_{n\geq 1}$ of the Farey sequence of
partitions thus works as follows. We begin with the coding of the unique
interval in $F_{0}$ as the empty word. Then, there are two cases: when the
mediant of an interval of $F_{n}$ can be added as an endpoint of $F_{n+1}$,
then this interval is subdivided and the coding of the two subintervals is
made in the lexicographic order by adding a letter in $\\{0,1\\}$. When the
mediant cannot be added, the interval is not subdivided, and the coding is
extended in a unique way by adding the next letter in its palindromic
completion. This is illustrated in Figure 3.

$F_{0}:$$\varepsilon$$0/1$$1/1$$F_{1}:$$0$$1$$\tfrac{1}{2}$$F_{2}:$$00$$01$$10$$11$$\tfrac{1}{3}$$\tfrac{2}{3}$$F_{3}:$$000$$001$$010$$101$$110$$111$$\tfrac{1}{4}$$\tfrac{3}{4}$
Figure 3. The labelling of the Farey partition $F_{n}$ for $n\leq 3$.

######  Remark 4.14.

Consider the case where we consider two identical sequences of partitions
${\mathcal{P}}={\mathcal{P}}^{1}={\mathcal{P}}^{2}$ in Definition 2.5, with
${\mathcal{P}}$ log-balanced (a.e. or in measure). One can have
$L_{n}(x,{\mathcal{P}},{\mathcal{P}})>n$ if $I_{n}(x)=I_{n+1}(x)$. This is for
instance the case for the Farey partition. The construction of the coding
using the palindromic completion which shows that one might have more digits
in an interval of $F_{n}$ than the $n+1$ letters of a prefix. For instance,
$(1/(n+1),1/n)\in F_{n}$ and $L_{n}(x,\mathcal{F},\mathcal{F})=2n$ for every
$x\in(1/(n+1),1/n)$.

###  4.7. The three-distance sequence of partitions

The three-distance sequence of partitions ${3\mathcal{D}}({\alpha})$ is
defined in terms of the corresponding endpoints of each partition
${3\mathcal{D}}_{n}({\alpha})$. The set $E_{n}^{{3\mathcal{D}}({\alpha})}$ of
endpoints of ${3\mathcal{D}}_{n}({\alpha})$ is given by
$\\{1\\}\cup\\{(i\alpha)\bmod 1:\,0\leq i\leq n\\}$. We remark that, when
$\alpha$ is irrational, these determine exactly $n+1$ intervals.

####  4.7.1. Almost everywhere log-balancedness

It turns out, somewhat surprisingly, see [Sós58, Suŕ58, Sla64] or the survey
[AB98], that the lengths of the intervals in ${3\mathcal{D}}_{n}({\alpha})$
can only take at most three different values. This classical result is known
as the three-distance theorem, which we cite below. We make use of this
theorem to derive the weight function of the three-distance partition for
almost every $\alpha$. See [CV16] for a probabilistic study of the lengths in
the case where there are two distances, [PSZ16] for a study of the
distribution of the lengths when averaging over $\alpha$, and see also [ZA99].

######  Theorem 4.15 (The three-distance theorem).

Let $\alpha\in(0,1)$ an irrational number and $n$ be a positive integer. The
points $\\{1\\}\cup\\{(i\alpha)\bmod 1:\,0\leq i\leq n\\}$ partition the unit
interval $[0,1]$ into $n+1$ intervals, the lengths of which take at most three
values, one being the sum of the other two.

More precisely, let $\\{p_{k}/q_{k}\\}_{k\in\mathbb{N}}$ and
$\\{a_{k}\\}_{k\in\mathbb{N}}$ be the sequences of the convergents and partial
quotients associated with $\alpha$ in its continued fraction expansion. There
exist unique integers $k$, $m$, and $r$ such that

$n=mq_{k}+q_{k-1}+r,\ k\geq 0,\ 1\leq m\leq a_{k+1},\text{ and }0\leq
r<q_{k}.$

Let $\eta_{k}=(-1)^{k}(q_{k}\alpha-p_{k})$ for every $k\in\mathbb{N}$. Then,
the unit interval is divided by the points
$\\{\alpha\\},\\{2\alpha\\},\ldots,\\{n\alpha\\}$ into $n+1$ intervals which
satisfy that:

  * •

$n+1-q_{k}$ of them have length $\eta_{k}$ (which is the smallest of the three
lengths),

  * •

$r+1$ of them have length $\eta_{k-1}-m\eta_{k}$, and

  * •

$q_{k}-(r+1)$ of them have length $\eta_{k-1}-(m-1)\eta_{k}$ (which is the
largest of the three lengths).

There is an interesting connection between this theorem and frequencies of
words that occur in a characteristic Sturmian word (see Section 4.6.2).
Indeed, the lengths of intervals in Theorem 4.15 coincide with the frequencies
of factors of length $n+1$ [Ber96]. We will repeatedly use the following
result.

######  Theorem 4.16 ([Khi97, Theorems 9 and 13]).

Let $\alpha\in(0,1)$ an irrational and $\\{p_{k}/q_{k}\\}_{k\in\mathbb{N}}$
its sequence of convergents. If $k\in\mathbb{N}$ and
$\eta_{k}=(-1)^{k}(q_{k}\alpha-p_{k})$, then

$\frac{1}{q_{k+1}+q_{k}}<\eta_{k}<\frac{1}{q_{k+1}}.$

####  4.7.2. Weight function for most three-distance sequences of partitions
${3\mathcal{D}}({\alpha})$

We will prove that, for almost every $\alpha$, the three-distance sequence of
partitions ${3\mathcal{D}}({\alpha})$ is a.e. log-balanced as a consequence of
the following lemma.

######  Lemma 4.17.

For almost every $\alpha$ in $(0,1)$, the three-distance sequence of
partitions ${3\mathcal{D}}({\alpha})$ satisfies

$-\log|I^{{3\mathcal{D}}({\alpha})}_{n}(x)|=\log n+O(\log\log n)\text{ as
}n\to\infty\,,\quad\text{for every }x\not\in E^{{3\mathcal{D}}({\alpha})},$

where the hidden constant in the $O$-term might depend on $\alpha$, but can be
chosen so that the result holds for every $x\not\in
E^{{3\mathcal{D}}({\alpha})}$. Moreover, the limit
$-\log|I_{n}^{{3\mathcal{D}}({\alpha})}(\alpha)|/\log n\to 1$ as $n\to\infty$
holds for any irrational $\alpha\in(0,1)$ so that $\log a_{k}(\alpha)=o(k)$ as
$k\to\infty$.

###### Proof.

Let $\alpha$ be an irrational in $(0,1)$. We keep the notation introduced in
Theorem 4.15. In particular, $\eta_{k}:=|q_{k}(\alpha)\cdot\alpha-
p_{k}(\alpha)|$ for each $k\in\mathbb{N}$.

Let $n$ be a positive integer and choose $k\in\mathbb{N}$ so that

$q_{k}+q_{k-1}\leq n<q_{k+1}+q_{k}.$

(we recall $q_{0}=1$ and $q_{-1}=0$). Let $x\in[0,1]\setminus
E^{{3\mathcal{D}}({\alpha})}$. By Theorem 4.15,

$\eta_{k}\leq|I^{{3\mathcal{D}}({\alpha})}_{n}(x)|\leq\eta_{k-1}.$

By Theorem 4.16, $\log q_{k+1}<-\log\eta_{k}<\log(q_{k+1}+q_{k})$ and we
obtain

$\log
q_{k}<-\log\eta_{k-1}\leq-\log|I^{{3\mathcal{D}}({\alpha})}_{n}(x)|\leq-\log\eta_{k}<\log(q_{k+1}+q_{k}).$

Since
$q_{k+1}+q_{k}=(a_{k+1}+1)q_{k}+q_{k-1}<(a_{k+1}+2)q_{k}\leq(a_{k+1}+2)n$,

$\displaystyle-\log|I^{{3\mathcal{D}}({\alpha})}_{n}(x)|\leq\log(q_{k+1}+q_{k})<\log
n+\log(a_{k+1}+2).$

But we also obtain $q_{k}>(q_{k+1}+q_{k})/(a_{k+1}+2)>n/(a_{k+1}+2)$, which
implies

$\displaystyle-\log|I^{{3\mathcal{D}}({\alpha})}_{n}(x)|\geq\log q_{k}>\log
n-\log(a_{k+1}+2).$

The Borel–Bernstein Theorem (Theorem 4.5) implies that, for a.e. $\alpha$,
$a_{k+1}\leq k^{2}$ for $k$ large enough. Moreover, $k=O(\log n)$ as
$n\to\infty$ for every irrational $\alpha\in(0,1)$, as $2^{(k-1)/2}\leq
q_{k}(\alpha)\leq n$. Therefore, $\log(a_{k+1}+2)=O(\log\log n)$ as
$n\to\infty$, for a.e. $\alpha$. This proves the first assertion of the lemma.

The second assertion of the lemma follows from the fact that if
$\log(a_{k})=o(k)$ as $k\to\infty$, then $\log(a_{k+1}+2)=o(\log n)$ as
$n\to\infty$.∎

We have the following consequence of Lemma 4.17.

######  Proposition 4.18.

For almost every $\alpha$ in $(0,1)$, the three-distance sequence of
partitions ${3\mathcal{D}}({\alpha})$ is a.e. log-balanced with respect to the
Lebesgue measure with weight function

$f_{{3\mathcal{D}}({\alpha})}(n)=\log n\quad\text{for each }n\geq 1.$

More specifically, it holds for any irrational $\alpha\in(0,1)$ whose
continued fraction expansion satisfies $\log a_{k}(\alpha)=o(k)$ as
$k\to\infty$.

######  Remark 4.19.

The above result holds, for instance, for $\alpha=\phi^{-2}$, where $\phi$
denotes the golden ratio, and for
$\alpha=e-2=[0;\overline{1,2k,1}_{k=1}^{\infty}]$ (see e.g., [Coh06]).

####  4.7.3. Sequences of partitions which are not log-balanced

Next proposition will provide an uncountable family of numbers $\alpha$ for
which the corresponding sequence of partitions ${3\mathcal{D}}({\alpha})$ is
not log-balanced.

######  Proposition 4.20.

Fix any real number $s>0$. We define $\alpha=\alpha(s)\in(0,1)$ as the number
whose continued fraction expansion satisfies the following recurrence relation

$a_{1}(\alpha)=1\quad\text{and}\quad a_{k+1}(\alpha)=\lceil
q_{k}^{s}(\alpha)\rceil\quad\text{for each }k\geq 1.$

Then, the corresponding ${3\mathcal{D}}({\alpha})$ sequence of partitions is
not log-balanced in measure (thus, neither a.e. log-balanced) with respect to
the Lebesgue measure.

###### Proof.

We will prove that

$\displaystyle\frac{-\log|I^{{3\mathcal{D}}({\alpha})}_{n}(x)|}{\log n}$

does not converge in measure with respect to the Lebesgue measure as
$n\to\infty$. For this purpose, let us define $\\{{n}_{k}\\}_{k\in\mathbb{N}}$
as follows: for each $k\in\mathbb{N}$,

${n}_{k}=m_{k}q_{k}+q_{k-1}+r_{k},\quad\text{with}\quad
m_{k}=\left\lceil\frac{a_{k+1}}{2}\right\rceil\quad\text{and}\quad
r_{k}=q_{k}-1.$

According to the three-distance theorem, there are only two different lengths
among the intervals in ${3\mathcal{D}}_{n_{k}}({\alpha})$. More precisely,
these $n_{k}+1$ intervals can be partitioned into two types:

  * •

$n_{k}+1-q_{k}$ intervals of length $\eta_{k}$ and

  * •

$r_{k}+1=q_{k}$ intervals of length $\Delta_{k}:=\eta_{k-1}-m_{k}\eta_{k}$.

On the basis of this remark, we will prove that for our choice of
$\\{n_{k}\\}_{k\in\mathbb{N}}$ and for each $x\in[0,1]\setminus
E^{{3\mathcal{D}}({\alpha})}$, one has:

(17) $\frac{-\log|I^{{3\mathcal{D}}({\alpha})}_{n_{k}}(x)|}{\log
n_{k}}=g(x,k)+O\left(\frac{1}{k}\right)\quad\text{as }k\to\infty,$

where

$\displaystyle g(x,k):=\begin{cases}1&\text{if
}|I^{{3\mathcal{D}}({\alpha})}_{n_{k}}(x)|=\eta_{k},\vskip 3.0pt plus 1.0pt
minus 1.0pt\\\ \dfrac{1}{s+1}&\text{if
}|I^{{3\mathcal{D}}({\alpha})}_{n_{k}}(x)|=\Delta_{k},\end{cases}$

and the constant hidden in the $O$-term does not depend on $x$.

In order to estimate the three quantities $n_{k}$, $\eta_{k}$, and
$\Delta_{k}$ by a convenient power of $q_{k}$, we will bound $m_{k}$ as
follows:

(18) $\frac{1}{2}q_{k}^{s}\leq\frac{a_{k+1}}{2}\leq
m_{k}<\frac{a_{k+1}}{2}+1<\frac{1}{2}(q_{k}^{s}+1)+1=\frac{1}{2}q_{k}^{s}\left(1+\frac{3}{q_{k}^{s}}\right).$

Hence, each depth $n_{k}$ satisfies

(19) $\frac{1}{2}q_{k}^{s+1}\leq
n_{k}<m_{k}q_{k}+2q_{k}=\frac{1}{2}q_{k}^{s+1}\left(1+\frac{7}{q_{k}^{s}}\right).$

Now, we bound the distance $\eta_{k}$. Since $q_{k}^{s}\leq
a_{k+1}<q_{k}^{s}+1$, the continuant $q_{k+1}$ satisfies

$\displaystyle q_{k+1}$
$\displaystyle<(q_{k}^{s}+1)q_{k}+q_{k-1}<(q_{k}^{s}+1)q_{k}+q_{k}=q_{k}^{s+1}\left(1+\frac{2}{q_{k}^{s}}\right)\quad\text{and}$
$\displaystyle q_{k+1}$ $\displaystyle>q_{k}^{s+1}.$

Thus, by Theorem 4.16, each length $\eta_{k}$ satisfies

(20)
$\frac{q_{k}^{-(s+1)}}{1+{3}/{q_{k}^{s}}}\leq\frac{1}{q_{k+1}+q_{k}}<\eta_{k}<\frac{1}{q_{k+1}}\leq{q_{k}^{-(s+1)}}.$

Inequalities (19) and (20) prove that $\log n_{k}=(s+1)\log q_{k}+O(1)$ and
also $-\log\eta_{k}=(s+1)\log q_{k}+O(1)$ as $k\to\infty$. Since
$q_{k}=q_{k}(\alpha)$ has, at least, exponential growth with respect to $k$,
then

(21) $\frac{-\log\eta_{k}}{\log
n_{k}}=1+O\left(\frac{1}{k}\right)\quad\text{as }k\to\infty.$

In order to bound the length $\Delta_{k}$, we remark that the above upper
bound on $\eta_{k}$ and the upper bound on $m_{k}$ given in (18) yield

(22) $m_{k}\eta_{k}<\frac{q_{k}^{-1}}{2}\left(1+\frac{3}{q_{k}^{s}}\right).$

By construction, the sequence of partial quotients $\\{a_{k}\\}$ tends to
infinity as $k$ does. Hence, it is possible to choose a large enough
$k_{0}\in\mathbb{N}$ so that $q_{k-1}/q_{k}\leq 1/3$. Without loss of
generality, we assume $k_{0}$ is large enough so that $3/q_{k}^{s}\leq 1/4$
for any $k\geq k_{0}$. For such a $k$, it follows by Theorem 4.16 that

$\displaystyle\Delta_{k}$
$\displaystyle=\eta_{k-1}-m_{k}\eta_{k}<q_{k}^{-1}\quad\text{and}$
$\displaystyle\Delta_{k}$ $\displaystyle\geq
q_{k}^{-1}\left(\frac{1}{1+\dfrac{q_{k-1}}{q_{k}}}\right)-\frac{q_{k}^{-1}}{2}\left(1+\frac{3}{q_{k}^{s}}\right)\geq\frac{1}{8}q_{k}^{-1}.$

These inequalities prove that $-\log\Delta_{k}=\log q_{k}+O(1)$ but, according
to (19), $-\log n_{k}=(s+1)\log q_{k}+O(1)$, as $k\to\infty$. Thus, as the
continuants $q_{k}$ grow at least exponentially with $k$, this yields

(23) $\frac{-\log\Delta_{k}}{\log
n_{k}}=\frac{1}{s+1}+O\left(\frac{1}{k}\right)\quad\text{as }k\to\infty.$

Equation (17) now follows from (21) and (23). Notice that (17) implies that
there are three possibilities for the sequence
${-\log|I_{n_{k}}^{{3\mathcal{D}}({\alpha})}(x)|}/{\log n_{k}}$ depending on
$x\in[0,1]\setminus E^{{3\mathcal{D}}({\alpha})}$: (i) it has a limit equal to
1; (ii) it has a limit equal to $1/(s+1)$; or (iii) it has no limit. To end
the proof of this proposition, we now show that there exists $\epsilon>0$ so
that the measures of the sets

$F_{k,\epsilon}=\left\\{x\in[0,1]\setminus
E^{{3\mathcal{D}}({\alpha})}:\,\left|\frac{-\log|I_{n_{k}}^{{3\mathcal{D}}({\alpha})}(x)|}{\log
n_{k}}-1\right|<\varepsilon\right\\}$

belong to $\left[\frac{1}{4},\frac{3}{4}\right]$ for $k$ large enough.
Consider any $\epsilon$ with $0<\epsilon<{1}/{(2(s+1))}$. Because of (17),
there is a $k_{1}\in\mathbb{N}$ so that, for each $k\geq k_{1}$, the set
$F_{k,\epsilon}$ coincides with the set $G_{k}$ given by

$G_{k}=\left\\{x\in[0,1]\setminus
E^{{3\mathcal{D}}({\alpha})}:\,|I^{{3\mathcal{D}}({\alpha})}_{n_{k}}(x)|=\eta_{k}\right\\}.$

The number of intervals of length $\eta_{k}$ is $n_{k}+1-q_{k}$. Thus, one has

$|G_{k}|=(n_{k}+1-q_{k})\eta_{k}=(m_{k}q_{k}+q_{k-1})\eta_{k}.$

The bounds on $m_{k}\eta_{k}$ and $\eta_{k}$ in (22) and (20) yield, for $k$
large enough so that $5/q_{k}^{s}\leq 1/2$,

$\displaystyle|G_{k}|$
$\displaystyle\leq(m_{k}+1)\eta_{k}q_{k}\leq\frac{1}{2}q_{k}^{-1}\left(1+\frac{5}{q_{k}^{s}}\right)q_{k}\leq\frac{3}{4}\quad\text{and}$
$\displaystyle|G_{k}|$ $\displaystyle\geq
m_{k}q_{k}\eta_{k}\geq\frac{1}{2}q_{k}^{s+1}\left(\frac{q_{k}^{-s-1}}{1+3/q_{k}^{s}}\right)\geq\frac{1}{4}.$

Finally, we have proved that, for each $\epsilon$ with
$0<\varepsilon<{1}/{(2(s+1))}$ and sufficiently large $k$, the following holds
$\left|F_{k,\epsilon}\right|=|G_{k}|\in[1/4,3/4]$. Then, the sequence
$-\log|I_{n_{k}}^{{3\mathcal{D}}({\alpha})}(x)|/{\log n_{k}}$ cannot converge
in measure as $k\to\infty$, and thus the proof of the proposition is complete.
∎

##  5\. On the Farey and continued fraction sequences of partitions: an
explicit case

In this section, we look at the relationship between the Farey and the
continued fraction sequences of partitions. Both cases are of particular
interest as the Lochs indexes in both conversion directions can be computed
explicitly, as demonstrated with Proposition 5.3 and 5.5, which moreover
provide direct proofs of the Lochs-type theorems for these cases. We also show
stronger results, when compared to our general theorems, including a
probabilistic version of the error term in the case of the Lochs index from
continued fraction to Farey.

More precisely, for the probabilistic error term when going from continued
fractions to Farey, namely Theorem 5.4, we apply a strong result regarding the
asymptotic distribution of the logarithm of the continuants $\log q_{n}$ as
$n\to\infty$. This result is a refinement over the classical Khinchin–Lévy’s
Theorem (see (9)), which tells us that $(1/n)\log q_{n}\to\pi^{2}/(12\log 2)$
as $n\to\infty$. The refinement comes in the form of an extra term, of
probabilistic nature: the random variable $\log q_{n}$ is asymptotically
Gaussian (see, e.g., [FV98, Thm. 1] and [Ibr61]), as recalled below.

######  Theorem 5.1.

Let $h=\pi^{2}/(6\log 2)$ be the entropy of the continued fraction sequence of
partitions. Then, there exists a positive constant $B$ so that the sequence

(24) $Z_{n}(x)=\frac{\log q_{n}(x)-\frac{h}{2}n}{B\sqrt{n}}$

is asymptotically Gaussian; i.e., for every $t\in\mathbb{R}$,

$\left|\\{x\in[0,1]:\,Z_{n}(x)<t\\}\right|=\frac{1}{\sqrt{2\pi}}\int_{0}^{t}e^{-w^{2}/2}dw+O\Big{(}\frac{1}{\sqrt{n}}\Big{)}$

as $n\to\infty$. (We recall that $|\cdot|$ stands for the Lebesgue measure.)

###  5.1. From continued fractions to the Farey sequence of partitions

We begin by describing the Lochs index for the conversion from the continued
fraction sequence of partitions to the Farey one.

######  Lemma 5.2.

For each irrational $x\in(0,1)$ and each $n\in\mathbb{N}$, one has

(25) $I_{n}^{\mathcal{CF}}(x)=I_{k}^{\mathcal{F}}(x),\quad\text{where
}k=q_{n}+q_{n-1}-1.$

###### Proof.

On the one hand, the interval $I_{n}^{\mathcal{CF}}(x)$ of the continued
fraction sequence of partitions is simply, up to reordering the endpoints
depending on the parity of $n$,

(26)
$I_{n}^{\mathcal{CF}}(x)=\left(\frac{p_{n}}{q_{n}},\frac{p_{n}+p_{n-1}}{q_{n}+q_{n-1}}\right)\,.$

On the one hand, by Proposition 4.11, the Farey interval of depth $k$
containing $x$, up to reordering of the endpoints depending on the parity of
$m$, is given by

(27)
$I_{k}^{\mathcal{F}}(x)=\Big{(}\frac{p_{m}}{q_{m}},\frac{(r+1)p_{m}+p_{m-1}}{(r+1)q_{m}+q_{m-1}}\Big{)}\,,$

where $m$ and $r$ are the only integers such that

$(r+1)q_{m}+q_{m-1}\leq k+1<(r+2)q_{m}+q_{m-1},\ m\geq 0,\text{ and }0\leq
r<a_{m+1}.$

Notice that if $k=q_{n}+q_{n-1}$, then $r=0$ and $m=n$, which shows that
$I_{k}^{\mathcal{F}}(x)=I_{n}^{\mathcal{CF}}(x)$. ∎

######  Proposition 5.3.

For any irrational number $x\in(0,1)$ and any integer $n\geq 1$, one has

$L_{n}(x,\mathcal{CF},\mathcal{F})=2q_{n}(x)+q_{n-1}(x)-2.$

###### Proof.

By Lemma 5.2, $I_{n}^{\mathcal{CF}}(x)=I_{k}^{\mathcal{F}}(x)$, where
$k=q_{n}+q_{n-1}-1$. This interval will split into two subintervals in the
Farey sequence of partitions for the first time at depth $2q_{n}+q_{n-1}-1$
(for this is the denominator of the mediant of its endpoints). Hence, the
proposition follows.∎

Theorem 5.1, together with the above result, yields the following theorem
which gives a Lochs-type theorem for the conversion from the continued
fraction sequence of partitions to the Farey one with an error term satisfying
an asymptotically Gaussian law.

######  Theorem 5.4.

If $Z_{n}$ and $B$ are as in Theorem 5.1 and $x$ is an irrational in $(0,1)$,
then

(28) $\frac{\log L_{n}(x,\mathcal{CF},\mathcal{F})}{n}=\frac{\pi^{2}}{12\log
2}+\frac{B}{\sqrt{n}}Z_{n}(x)+O\left(\frac{1}{n}\right),\quad\text{as
}n\to\infty,$

with $Z_{n}$ asymptotically Gaussian. In particular,

$\lim_{n\to\infty}\frac{\log
L_{n}(x,\mathcal{CF},\mathcal{F})}{n}=\frac{\pi^{2}}{12\log
2}\quad\text{a.e.},$

with respect to the Lebesgue measure.

###### Proof.

Let $x\in(0,1)$ an irrational. Observe that, by Proposition 5.3 and each
positive integer $n$,

$\log L_{n}(x,\mathcal{CF},\mathcal{F})=\log(2q_{n}+q_{n-1}-2)=\log
q_{n}+\log\left(2+\tfrac{q_{n-1}-2}{q_{n}}\right).$

As the term $\log\left(2+\tfrac{q_{n-1}-2}{q_{n}}\right)$ is upper bounded by
$\log 3$, then

$\displaystyle\frac{\log L_{n}(x,\mathcal{CF},\mathcal{F})}{n}=\frac{\log
q_{n}}{n}+O\left(\frac{1}{n}\right)=\frac{\pi^{2}}{12\log
2}+\frac{B}{\sqrt{n}}Z_{n}(x)+O\left(\frac{1}{n}\right)$

as $n\to\infty$ by Theorem 5.1. ∎

###  5.2. Coming back: from Farey to continued fractions

In the case of the conversion from the Farey sequence of partitions to the
continued fraction one, the Lochs-type result we obtain comes directly from
the expression of the Lochs index from Proposition 5.6 below. This is an
almost everywhere result that is not covered by our more generally applicable
Theorem 2.8. Indeed, the difficulty in applying Theorem 2.8 in this case stems
from the fact that assertion (i) does not hold; this is because the weight
function $f_{1}$ of the Farey sequence of partitions is slowly-increasing.
Nevertheless, our general result in measure (Theorem 2.9) does apply in this
case, which is enough to ensure that the limit (30) holds but only in measure.

######  Proposition 5.5.

Let $x\in(0,1)$ be an irrational number and let $n$ be a positive integer. If
$k=k(x,n)$ is the only positive integer such that

(29) $q_{k}(x)+q_{k-1}(x)\leq n+1<q_{k+1}(x)+q_{k}(x)\,,$

then

$L_{n}(x,\mathcal{F},\mathcal{CF})=k.$

###### Proof.

By Lemma 5.2, $I_{k}^{\mathcal{CF}}(x)=I_{n^{\prime}}^{\mathcal{F}}(x)$ and
$I_{k+1}^{\mathcal{CF}}(x)=I_{n^{\prime\prime}}^{\mathcal{F}}(x)$ where
$n^{\prime}=q_{k}+q_{k-1}-1$ and $n^{\prime\prime}=q_{k+1}+q_{k}-1$. By
assumption, $n^{\prime}\leq n<n^{\prime\prime}$. Thus,

$I_{k+1}^{\mathcal{CF}}(x)=I_{n^{\prime\prime}}^{\mathcal{F}}(x)\subseteq
I_{n}^{\mathcal{F}}(x)\subseteq
I_{n^{\prime}}^{\mathcal{F}}(x)=I_{k}^{\mathcal{CF}}(x).$

Notice that one of the endpoints of $I_{k+1}^{\mathcal{CF}}(x)$ is
$\frac{p_{k+1}+p_{k}}{q_{k+1}+q_{k}}$, which does not belong to $F_{n}$
(because $q_{k+1}+q_{k}>n+1)$. Hence, $I_{k+1}^{\mathcal{CF}}(x)\subsetneq
I_{n}^{\mathcal{F}}(x)$ and, in particular, $I_{n}^{\mathcal{F}}(x)\nsubseteq
I_{k+1}^{\mathcal{CF}}(x)$. We conclude that $k$ is the largest integer
$k^{\prime}$ such that $I_{n}^{\mathcal{F}}(x)\subseteq
I_{k^{\prime}}^{\mathcal{CF}}(x)$, i.e.,
$k=L_{n}(x,\mathcal{F},\mathcal{CF})$.∎

######  Proposition 5.6.

The following holds with respect to the Lebesgue measure:

(30) $\lim_{n\to\infty}\frac{L_{n}(x;{\mathcal{F}},{\mathcal{CF}})}{\log
n}=\frac{12\log 2}{\pi^{2}}\quad\text{a.e.}$

###### Proof.

Let $x\in(0,1)$ an irrational and $n$ be a positive integer. By Proposition
5.5, if $k=k(x,n)$ is the only positive integer satisfying (29), then
$L_{n}(x,\mathcal{F},\mathcal{CF})=k(x,n)$ and the following inequalities hold

$2q_{k(x,n)-1}(x)\leq n\leq 2q_{k(x,n)+1}(x).$

As $k(x,n)\to\infty$ as $n\to\infty$, Khinchin–Lévy’s Theorem (see (9)) yields
$\log q_{k(x,n)+1}/\log q_{k(x,n)-1}\to 1$ as $n\to\infty$ a.e. Hence, $\log
n/\log q_{k(x,n)}\to 1$ as $n\to\infty$ a.e. Therefore, again by
Khinchin–Lévy’s Theorem, we have that

$\lim_{n\to\infty}\frac{L_{n}(x,\mathcal{F},\mathcal{CF})}{\log
n}=\lim_{n\to\infty}\frac{k(x,n)}{\log n}=\lim_{n\to\infty}\frac{k(x,n)}{\log
q_{k(x,n)}}=\frac{12\log 2}{\pi^{2}}\quad\text{a.e.}\qed$

It would be interesting to characterize

$\frac{L_{n}(x,\mathcal{F},\mathcal{CF})-\tfrac{\pi^{2}}{12\log 2}\log
n}{\sqrt{\log n}}$

in law. The objective would be to obtain an analog to Theorem 5.4 but going
from Farey to continued fractions.

##  6\. Lochs-type theorems for log-balanced sequences of partitions

In this section, we give the proofs of our general Lochs-type theorems:
Theorems 2.8 and 2.9. The structure of this section is as follows. In Section
6.1, we introduce some auxiliary notions which are useful for the proofs
throughout this section. In Sections 6.2 and 6.3, we prove our main result
a.e. and in measure, respectively.

###  6.1. Preliminaries

We follow here the notion of $\epsilon$-goodness introduced in [DF01].

######  Definition 6.1.

Let $\mathcal{P}=\\{P_{n}\\}_{n\in\mathbb{N}}$ be a sequence of partitions and
let $f:\mathbb{N}\to\mathbb{R}$. If $x\in[0,1]\setminus E$, $n\in\mathbb{N}$,
and $\epsilon>0$, we say that $I_{n}(x)\in P_{n}$ is _$\epsilon$ -good for
$\mathcal{P}$ and $f$_ if

$(1-\epsilon)f(n)<-\log\lambda(I_{n}(x))<(1+\epsilon)f(n)$

or, equivalently,

$e^{-(1+\epsilon)f(n)}<\lambda(I_{n}(x))<e^{-(1-\epsilon)f(n)}.$

######  Notation 6.2.

In the proofs given in this section, for each $i=1,2$, we say that
$I_{n}^{i}(x)$ is _$\epsilon$ -good_ if $I_{n}^{i}(x)$ is $\epsilon$-good for
$\mathcal{P}^{i}$ and $f_{i}$.

######  Definition 6.3.

If $f:\mathbb{N}\to\mathbb{R}$ is a nondecreasing function such that $f(n)$
tends to $+\infty$ as $n\to\infty$, we denote by $f^{[-1]}$ the function
$f^{[-1]}:\mathbb{R}\to\mathbb{N}$ defined as
$f^{[-1]}(y)=\min\\{n\in\mathbb{N}:\,f(n)\geq y\\}$.

######  Remark 6.4.

All the following assertions are immediate consequences of the definition:

  1. (i)

$f^{[-1]}$ is nondecreasing;

  2. (ii)

$f^{[-1]}(y)\to\infty$ as $y\to+\infty$;

  3. (iii)

for each $y\in\mathbb{R}$, $f(f^{[-1]}(y))\geq y$;

  4. (iv)

if $n\in\mathbb{N}$ and $y\in\mathbb{R}$ are such that $n<f^{[-1]}(y)$, then
$f(n)<y$; and

  5. (v)

if $f$ is strictly increasing and $\tilde{f}:[0,+\infty)\to\mathbb{R}$ is any
strictly increasing function such that $\tilde{f}(n)=f(n)$ for each
$n\in\mathbb{N}$, then $f^{[-1]}(y)=\lceil\tilde{f}^{-1}(y)\rceil$ for every
$y\in\mathbb{R}$.

The following lemma tells us that, if $f$ is not allowed to grow too fast, we
can reverse $f^{[-1]}$ by $f$ asymptotically.

######  Lemma 6.5.

Let $f\colon\mathbb{N}\to\mathbb{R}$ be a nondecreasing function tending to
infinity. If $f(n+1)-f(n)=o(f(n))$ as $n\to\infty$, then $f(f^{[-1]}(y))/y\to
1$ as $y\to+\infty$ (over $y\in\mathbb{R}$).

###### Proof.

By Remark 6.4 (ii), $f^{[-1]}(y)\to\infty$ as $y\to+\infty$. Thus, the fact
that $f(n+1)-f(n)=o(f(n))$ as $n\to\infty$ implies
$f(f^{[-1]}(y))/f(f^{[-1]}(y)-1)\to 1$ as $y\to+\infty$. Moreover, by items
(iii) and (iv) of Remark 6.4, $f(f^{[-1]}(y)-1)<y\leq f(f^{[-1]}(y))$.
Therefore, dividing through by $f(f^{[-1]}(y))$ implies the result, as both
extremes tend to $1$ as $y\to+\infty$. ∎

###  6.2. Lochs-type theorem a.e.

In this section, we prove our general Lochs-type theorem a.e., namely Theorem
2.8. This result is a consequence of Propositions 6.6 and 6.7.

######  Proposition 6.6.

Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be two a.e. log-balanced sequences
of partitions with weight functions $f_{1}$ and $f_{2}$, respectively, with
respect to a measure $\lambda$. If $f_{2}$ is nondecreasing, then

$\displaystyle\limsup_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}\leq
1\quad\text{a.e. }(\lambda).$

###### Proof.

Let $\epsilon\in(0,1)$. For each $n\in\mathbb{N}$, let
$m(n):=f_{2}^{[-1]}\bigl{(}\frac{1+\epsilon}{1-\epsilon}f_{1}(n)\bigr{)}$. Let
$m\in\mathbb{N}$ such that $m\geq m(n)$. Since $f_{2}$ is nondecreasing,
$f_{2}(m)\geq f_{2}(m(n))\geq\frac{1+\epsilon}{1-\epsilon}f_{1}(n)$, by Remark
6.4 (iii). Thus, $e^{-(1+\epsilon)f_{1}(n)}\geq e^{-(1-\epsilon)f_{2}(m)}$ for
all $n\in\mathbb{N}$. Hence, for each $x\in[0,1]\setminus(E^{1}\cup E^{2})$,
each $n\in\mathbb{N}$, and each $m\in\mathbb{N}$ such that $m\geq m(n)$, if
$I^{1}_{n}(x)$ and $I^{2}_{m}(x)$ are $\epsilon$-good, then

$\displaystyle\lambda(I^{1}_{n}(x))>e^{-(1+\epsilon)f_{1}(n)}\geq
e^{-(1-\epsilon)f_{2}(m)}>\lambda(I^{2}_{m}(x))$

and, in particular, $I_{n}^{1}(x)\nsubseteq I^{2}_{m}(x)$. Therefore, for each
$x\in[0,1]\setminus(E^{1}\cup E^{2})$ and each $n\in\mathbb{N}$ such that both
$I_{n}^{1}(x)$ is $\epsilon$-good and $I_{m}^{2}(x)$ is $\epsilon$-good for
each $m\geq m(n)$, we have that
$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})<m(n)$.

Since $-\log\lambda(I_{n}^{1}(x))/f_{1}(n)\to 1$ as $n\to\infty$ a.e., we have
that $I^{1}_{n}(x)$ is $\epsilon$-good for $n$ large enough a.e. Notice that,
since $f_{1}(n)\to+\infty$ as $n\to\infty$, Remark 6.4 (ii) implies
$m(n)\to\infty$ as $n\to\infty$. Thus, the fact that
$-\log\lambda(I_{m}^{2}(x))/f_{2}(m)\to 1$ as $m\to\infty$ a.e. implies that
for a.e. $x$, for $n$ large enough (depending on $x$), $I_{m}^{2}(x)$ is
$\epsilon$-good for each $m\in\mathbb{N}$ such that $m\geq m(n)$. Hence,
$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})<m(n)$ for $n$ large enough a.e.
Therefore, by Remark 6.4 (iv),
$f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))<\frac{1+\epsilon}{1-\epsilon}f_{1}(n)$
for $n$ large enough a.e. Taking $\epsilon\to 0$ gives the result. ∎

######  Proposition 6.7.

Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be two a.e. log-balanced sequences
of partitions with weight functions $f_{1}$ and $f_{2}$, respectively, with
respect to a measure $\lambda$ such that the following assertions hold:

  1. (i)

$f_{2}$ is nondecreasing;

  2. (ii)

for each $\eta\in(0,1)$, there exists $\epsilon>0$ such that

$\displaystyle\sum_{n=1}^{\infty}e^{-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))}<+\infty,\quad\text{where
}m(n):=f_{2}^{[-1]}\left((1-\eta)f_{1}(n)\right).$

Then,

$\displaystyle\liminf_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}\geq
1\quad\text{a.e.\ }(\lambda).$

###### Proof.

Let $\eta\in(0,1)$. For each $n\in\mathbb{N}$, let $\mathcal{J}_{n}$ be the
set of ordered pairs $(I^{1}_{n}(x),I^{2}_{m(n)}(x))$ such that
$I^{1}_{n}(x)\nsubseteq I^{2}_{m(n)}(x)$. Let
$(I^{1}_{n}(x),I^{2}_{m(n)}(x))\in\mathcal{J}_{n}$. Since $I^{1}_{n}(x)$ and
$I^{2}_{m(n)}(x)$ share the point $x$, necessarily $I^{1}_{n}(x)$ contains at
least one of the endpoints of $I^{2}_{m(n)}(x)$. Thus, there are no three
ordered pairs in $\mathcal{J}_{n}$ having the same second entry.

Suppose $\epsilon>0$ (we will choose $\epsilon$ later). Let
$\mathcal{J}_{n,\epsilon}$ be the set of ordered pairs in $\mathcal{J}_{n}$
whose entries are both $\epsilon$-good. Notice that, if
$(I^{1}_{n}(x),I^{2}_{m(n)}(x))\in\mathcal{J}_{n,\epsilon}$, then

$\displaystyle\lambda(I^{1}_{n}(x))<e^{-(1-\epsilon)f_{1}(n)}\quad\text{and}\quad
e^{-(1+\epsilon)f_{2}(m(n))}<\lambda(I^{2}_{m(n)}(x))$

and, consequently,

$\displaystyle\lambda(I^{1}_{n}(x))<e^{-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))}{\lambda(I^{2}_{m(n)}(x))}.$

Let
$D_{n,\epsilon}:=\\{x:\,\bigl{(}I^{1}_{n}(x),I^{2}_{m(n)}(x)\bigr{)}\in\mathcal{J}_{n,\epsilon}\\}=\bigcup_{(I^{1}_{n}(x),I^{2}_{\bar{m}(n)}(x))\in\mathcal{J}_{n,\epsilon}}(I^{1}_{n}(x)\cap
I^{2}_{m(n)}(x))$. Hence, this gives

$\displaystyle\lambda(D_{n,\epsilon})$
$\displaystyle=\sum_{(I^{1}_{n}(x),I^{2}_{m(n)}(x))\in\mathcal{J}_{n,\epsilon}}\lambda(I^{1}_{n}(x)\cap
I^{2}_{m(n)}(x))\leq\sum_{(I^{1}_{n}(x),I^{2}_{m(n)}(x))\in\mathcal{J}_{n,\epsilon}}\lambda(I^{1}_{n}(x))$
$\displaystyle\leq
e^{-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))}\sum_{(I^{1}_{n}(x),I^{2}_{m(n)}(x))\in\mathcal{J}_{n,\epsilon}}\lambda(I^{2}_{m(n)}(x))$
$\displaystyle\leq 2e^{-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))}.$

(Recall that there are no three ordered pairs in $\mathcal{J}_{n}$ having the
same second entry.)

Let $\epsilon$ be as in assertion (ii). Hence, by the Borel–Cantelli Lemma we
have that

$\displaystyle\lambda(\\{x:\,x\in D_{n,\epsilon}\text{ i.o.}\\})=0.$

Thus, $x\notin D_{n,\epsilon}$ for $n$ large enough a.e. Since
$f_{1}(n)\to+\infty$ as $n\to\infty$, Remark 6.4 (ii) ensures that
$m(n)\to\infty$ as $n\to\infty$. Thus, since $f_{1}$ and $f_{2}$ are a.e.
weight functions of $\mathcal{P}_{1}$ and $\mathcal{P}^{2}$, $I^{1}_{n}(x)$
and $I^{2}_{m(n)}(x)$ are $\epsilon$-good for $n$ large enough a.e. By the
definition of $D_{n,\epsilon}$, necessarily $I^{1}_{n}(x)\subseteq
I^{2}_{m(n)}(x)$ for $n$ large enough a.e. In particular,
$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})\geq m(n)$ for $n$ large enough a.e.
By assertion (i), the fact that $f_{2}(n)\to+\infty$ as $n\to\infty$, and
Remark 6.4 (iii), one has

$f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))\geq
f_{2}(m(n))\geq(1-\eta)f_{1}(n)\quad\text{for $n$ large enough a.e.}$

Taking $\eta\to 0$ gives the result.∎

Now we are ready to prove our main result a.e.

###### Proof.

By Propositions 6.6 and 6.7, it suffices to check that, for each
$\eta\in(0,1)$, there exists $\epsilon>0$ so that

(31)
$\sum_{n=1}^{\infty}e^{-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))}<+\infty,\quad\text{where
}m(n):=f_{2}^{[-1]}\left((1-\eta)f_{1}(n)\right).$

Let $\eta>0$. We show that $\epsilon=\eta/2$ satisfies the condition. By
assertion (iii), we can apply Lemma 6.5 to $f=f_{2}$ and $y=(1-\eta)f_{1}(n)$
in order to obtain $f_{2}(m(n))/((1-\eta)f_{1}(n))\to 1$ as $n\to\infty$.

Hence, since $\epsilon=\eta/2$, for $n$ large enough one has

$-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))=\left(-\frac{\eta^{2}}{2}+o(1)\right)f_{1}(n)\leq-\frac{\eta^{2}}{4}f_{1}(n).$

It follows from assertion (i) that (31) holds. This proves the theorem.∎

######  Remark 6.8.

The assumptions of the above result are sufficient conditions. These
assumptions are however not always necessary. The next result shows that, for
instance, the conclusion of Theorem 2.8 still holds in the case where
$\mathcal{P}^{1}=\mathcal{P}^{2}=\mathcal{F}$ even if the weight function
$f_{\mathcal{F}}(n)=2\log n$ does not satisfy assumption (i) of the theorem.

######  Proposition 6.9.

Let $\mathcal{P}$ be an a.e. log-balanced sequence of partitions with weight
function $f$ with respect to a measure $\lambda$. If $f$ is nondecreasing,
then

$\displaystyle\frac{f(L_{n}(x,\mathcal{P},\mathcal{P}))}{f(n)}\quad\text{as
}n\to\infty,\quad\text{a.e.}\ (\lambda).$

###### Proof.

Notice that, by definition of Lochs’ index,
$L_{n}(x,\mathcal{P},\mathcal{P})\geq n$ for each $n\in\mathbb{N}$. Moreover,
since $f$ is nondecreasing, $f(L_{n}(x,\mathcal{P},\mathcal{P}))\geq f(n)$ for
every $n\in\mathbb{N}$. Thus,
$\liminf_{n\to\infty}f(L_{n}(x,\mathcal{P},\mathcal{P}))/f(n)\geq 1$.
Therefore, by Proposition 6.6, the proof is complete. ∎

######  Remark 6.10.

It is unclear whether assumption (ii) in Proposition 6.7 is necessary.
Consider in particular the case where $\mathcal{P}^{2}$ is a slight
perturbation of $\mathcal{P}^{1}$ so that $f_{1}=f_{2}$. A natural question is
whether it is possible, in this case, to have
$\liminf_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}<1$
a.e. or that this limit does not even exist. If possible, this situation could
be regarded as revealing an intrinsic difficulty, in the sense that
considering only the lengths of the intervals does not provide enough
information for proving Lochs’ conversion results.

###  6.3. Lochs-type theorem in measure

In this section, we prove our general Lochs-type theorem in measure, namely
Theorem 2.9. This result is a consequence of Propositions 6.11 and 6.12.

######  Proposition 6.11.

Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be two sequences of partitions
that are log-balanced in measure with weight functions $f_{1}$ and $f_{2}$,
respectively, with respect to $\lambda$, such that the following assertions
hold:

  1. (i)

$\mathcal{P}^{2}$ is self-refining;

  2. (ii)

$f_{2}$ is nondecreasing.

Then,

$\limsup_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}\leq
1\quad\text{in measure }(\lambda).$

###### Proof.

Let $\epsilon\in(0,1)$ and let
$m(n):=f_{2}^{[-1]}\bigl{(}\frac{1+\epsilon}{1-\epsilon}f_{1}(n)\bigr{)}$.
Arguing as in the proof of Proposition 6.6, $e^{-(1+\epsilon)f_{1}(n)}\geq
e^{-(1-\epsilon)f_{2}(m(n))}$ for all $n\in\mathbb{N}$. Hence, for each
$x\in[0,1]\setminus(E^{1}\cup E^{2})$ and each $n\in\mathbb{N}$, if
$I^{1}_{n}(x)$ and $I^{2}_{m(n)}(x)$ are $\epsilon$-good, then

$\displaystyle\lambda(I^{1}_{n}(x))>e^{-(1+\epsilon)f_{1}(n)}\geq
e^{-(1-\epsilon)f_{2}(m(n))}>\lambda(I^{2}_{m(n)}(x))$

and, in particular, $I_{n}^{1}(x)\nsubseteq I^{2}_{m(n)}(x)$. Moreover, as we
are assuming that $\mathcal{P}^{2}$ is self-refining, it follows that
$I_{n}^{1}(x)\nsubseteq I_{m}^{2}(x)$ for each $m\geq m(n)$. Therefore,
$L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})<m(n)$. Hence,

$\displaystyle C_{n}$
$\displaystyle:=\\{x:\,L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})\geq m(n)\\}$
$\displaystyle\subseteq\\{x:\,I_{n}^{1}(x)\text{ is not
$\epsilon$-good}\\}\cup\\{x:\,I^{2}_{m(n)}(x)\text{ is not
$\epsilon$-good}\\}.$

By Remark 6.4 (ii), $m(n)\to\infty$ as $n\to\infty$. Thus, the fact that
$f_{1}$ and $f_{2}$ are weight functions in measure implies that, for $n$
large enough,

$\lambda(\\{x:I^{1}_{n}(x)\text{ is
$\epsilon$-good}\\})>1-\epsilon\quad\text{and}\quad\lambda(\\{x:I^{2}_{m(n)}(x)\text{
is $\epsilon$-good}\\})>1-\epsilon.$

Hence, $\lambda(C_{n})\leq 2\epsilon$ for $n$ large enough. Moreover, by
Remark 6.4 (iv), if $x\in[0,1]\setminus C_{n}$, then

$f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))<\frac{1+\epsilon}{1-\epsilon}f_{1}(n)=\left(1+\frac{2\epsilon}{1-\epsilon}\right)f_{1}(n).$

Taking $\epsilon\to 0$ gives the result.∎

######  Proposition 6.12.

Let $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$ be two sequences of partitions
that are log-balanced in measure with weight functions $f_{1}$ and $f_{2}$,
respectively, with respect to a measure $\lambda$, such that the following
assertions hold:

  1. (i)

$f_{2}$ is nondecreasing;

  2. (ii)

for each $\eta\in(0,1)$, there exists some $\epsilon>0$ such that

$\lim_{n\to\infty}\,(1-\epsilon)f_{1}(n)-(1+\epsilon)f_{2}(m(n))=+\infty,\text{where
}m(n):=f_{2}^{[-1]}\left((1-\eta)f_{1}(n)\right).$

Then,

$\displaystyle\liminf_{n\to\infty}\frac{f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))}{f_{1}(n)}\geq
1\quad\text{in measure }(\lambda).$

###### Proof.

Let $\eta\in(0,1)$ and let $\epsilon$ be as in (ii). Let $D_{n,\epsilon}$ be
defined as in the proof of Theorem 6.7. As argued in that proof,
$\lambda(D_{n,\epsilon})\leq
2e^{-(1-\epsilon)f_{1}(n)+(1+\epsilon)f_{2}(m(n))}$. Because of the choice of
$\epsilon$, $\lambda(D_{n,\epsilon})<\eta$ for $n$ large enough. Notice that,
since $f_{1}(n)\to+\infty$ as $n\to\infty$, Remark 6.4 (ii) ensures that
$m(n)\to\infty$ as $n\to\infty$. As $f_{1}$ and $f_{2}$ are weight functions
in measure for $\mathcal{P}^{1}$ and $\mathcal{P}^{2}$, then, for $n$ large
enough,

$\lambda(\\{x:\,I^{1}_{n}(x)\text{ is
$\epsilon$-good}\\})>1-\eta\quad\text{and}\quad\lambda(\\{x:\,I^{2}_{m(n)}(x)\text{
is $\epsilon$-good}\\})>1-\eta.$

Hence, since

$\displaystyle B_{n}$
$\displaystyle:=\\{x:\,L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2})<m(n)\\}$
$\displaystyle\subseteq\\{x:\,I^{1}_{n}(x)\nsubseteq I^{2}_{m(n)}(x)\\}$
$\displaystyle\subseteq D_{n,\epsilon}\cup\\{x:\,I^{1}_{n}(x)\text{ is not
$\epsilon$-good}\\}\cup\\{x:\,I^{2}_{m(n)}(x)\text{ is not
$\epsilon$-good}\\},$

we have that $\lambda(B_{n})<3\eta$ for $n$ large enough. Moreover, by
assertion (i), the fact that $f_{2}(n)\to+\infty$ as $n\to\infty$, and Remark
6.4 (iii), if $x\in[0,1]\setminus B_{n}$, then

$f_{2}(L_{n}(x,\mathcal{P}^{1},\mathcal{P}^{2}))\geq
f_{2}(m(n))\geq(1-\eta)f_{1}(n)$

for $n$ large enough. Taking $\eta\to 0$ gives the result.∎

###### Proof.

Arguing as in the proof of Theorem 2.8, for each $\eta>0$, if
$\epsilon=\eta/2$, then
$(1-\epsilon)f_{1}(n)-(1+\epsilon)f_{2}(m(n))\geq\frac{\eta^{2}}{4}f_{1}(n)$
for $n$ large enough. As $f_{1}(n)\to+\infty$ as $n\to\infty$, the theorem
follows by Propositions 6.11 and 6.12. ∎

######  Remark 6.13.

A situation analogous to that pointed out in Remark 6.8 holds also in
connection with the above theorem, that is, the assumptions in Theorem 2.9 are
sufficient but not always necessary. Indeed, reasoning as in the proof of
Proposition 6.9, one can prove that if $\mathcal{P}$ is log-balanced in
measure and self-refining, then $L_{n}(x,\mathcal{P},\mathcal{P})/n\to 1$ in
measure as $n\to\infty$.

##  7\. Final remarks and open questions

Theorem 2.8 and 2.9 provide asymptotic results for Lochs’ indexes for log-
balanced sequences of partitions. While the assumption of log-balancedness
could be regarded as relatively mild, it is crucial for our results. A natural
question is whether we can express sufficient conditions for log-balancedness,
for instance in dynamical terms in the case of fibred systems.

We have proved Lochs-type statements a.e. and in measure. Further studies
concerning these Lochs-type results could be conducted, such as a multifractal
analysis in the spirit of [BI08], or probabilistic estimates (central limit
theorems) such as in [Fai01, Wu06].

One motivation for the present work comes from the experimental simulation of
sources determined by sequences of partitions. (Here, by a source we mean the
usual notion in information theory.) Lochs-type results come up naturally when
we wonder how many of the initial digits in the binary expansion (which is
computationally natural) of a random number are needed in order to deduce a
prefix of a given length expressed in a different numeration system. Let us
first illustrate this with the following question: how many binary digits of a
random number do we need in order to generate the prefix of length $n$ of the
characteristic Sturmian word (see Section 4.6.2 for the definition)? We gave
an answer to this question in Section 2.2.2.

Our work is also related to the probabilistic study of the behavior of data
structures which are of fundamental importance in computer science. One such
structure is the so-called _trie_. A trie is a tree-like data-structure that
mimics the natural strategy to search a word in a dictionary by comparing
words via their prefixes. Thus, the depth of a trie built from a set of words
is related to “coincidences” between the words, that is, to the difficulty in
distinguishing these words. For positive entropy, Clément, Flajolet and Vallée
[CFV01] show that, when one builds a trie by picking $N$ random words produced
by a reasonably well-made source with entropy $h>0$, its average depth has
expectation asymptotically equal to $(1/h)\log N$. Furthermore, Cesaratto and
Vallée [CV15] have shown that its distribution is asymptotically Gaussian. In
[BCP+20] the authors consider the average depth of the tries produced by
random words produced by a source also as a mean to compare zero entropy
sources.

We conjecture that there should be some relation between the weight function
$f$, when it exists, and the average depth of the trie. We observe that the
average depth of a trie is related to the inverse of the weight function, for
instance, in the case of positive entropy and for the Farey sequence. Note
that $f^{-1}(\log N)=(1/h)\log N$, in the case of positive entropy $h$, as
then we have the weight function $f(n)=hn$. For the case of the Farey sequence
of partitions, $f(n)=2\log n$ and so $f^{-1}(\log N)=\sqrt{N}$. This coincides
with the asymptotics for the expected value of the average depth of the Farey
trie given in [BCP+20] up to a constant factor. However, this kind of
connection does not hold for Stern-Brocot.

Acknowledgements. We would like to thank Loïck Lhote for discussions on the
subject and Brigitte Vallée for comments on earlier versions of this paper.

## References

  * [AB98] P. Alessandri and V. Berthé, _Three distance theorems and combinatorics on words_ , Enseign. Math. (2) 44 (1998), no. 1-2, 103–132.
  * [ACD+19] A. Akhavi, J. Clément, D. Darthenay, L. Lhote, and B. Vallée, _Dichotomic selection on words: a probabilistic analysis_ , 30th Annual Symposium on Combinatorial Pattern Matching, vol. 128, LIPIcs. Leibniz Int. Proc. Inform., no. 19, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.
  * [BBLT06] G. Barat, V. Berthé, P. Liardet, and J. Thuswaldner, _Dynamical directions in numeration_ , Ann. Inst. Fourier (Grenoble) 56 (2006), no. 7, 1987–2092.
  * [BCP+20] V. Berthé, E. Cesaratto, F. Paccaut, P. Rotondo, M. D. Safe, and B. Vallée, _Two arithmetical sources and their associated tries_ , Proceedings of AoFa, 31st International Conference on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms, 2020.
  * [BDK06] W. Bosma, K. Dajani, and C. Kraaikamp, _Entropy quotients and correct digits in number-theoretic expansions_ , Dynamics & stochastics, IMS Lecture Notes Monogr. Ser., vol. 48, Inst. Math. Statist., Beachwood, OH, 2006, pp. 176–188.
  * [Ber11] F. Bernstein, _Über eine Anwendung der Mengenlehre auf ein aus der Theorie der säkularen Störungen herrührendes Problem_ , Math. Ann. 71 (1911), no. 3, 417–439.
  * [Ber96] V. Berthé, _Fréquences des facteurs des suites sturmiennes_ , Theoret. Comput. Sci. 165 (1996), no. 2, 295–309.
  * [BI08] L. Barreira and G. Iommi, _Partial quotients of continued fractions and $\beta$-expansions_, Nonlinearity 21 (2008), no. 10, 2211–2219.
  * [Bor09] E. Borel, _Les probabilités denombrables et leurs applications arithmétiques._ , Rend. Circ. Mat. Palermo 27 (1909), 247–271 (French).
  * [CFV01] J. Clément, P. Flajolet, and B. Vallée, _Dynamical sources in information theory: A general analysis of trie structures_ , Algorithmica 29 (2001), no. 1, 307–369.
  * [Coh06] H. Cohn, _A short proof of the simple continued fraction expansion of $e$_, Amer. Math. Monthly 113 (2006), no. 1, 57–62.
  * [CV15] E. Cesaratto and B. Vallée, _Gaussian distribution of trie depth for strongly tame sources_ , Combin. Probab. Comput. 24 (2015), no. 1, 54–103.
  * [CV16] by same author, _Pseudo-randomness of a random Kronecker sequence. An instance of dynamical analysis_ , Combinatorics, words and symbolic dynamics, Encyclopedia Math. Appl., vol. 159, Cambridge Univ. Press, Cambridge, 2016, pp. 401–442.
  * [DdVJ06] K. Dajani, M. de Vries, and A. S. A. Johnson, _The relative growth of information in two-dimensional partitions_ , Real Anal. Exchange 31 (2005/06), no. 2, 397–408.
  * [DF01] K. Dajani and A. Fieldsteel, _Equipartition of interval partitions and an application to number theory_ , Proc. Amer. Math. Soc. 129 (2001), no. 12, 3453–3460.
  * [DV86] H. G. Diamond and J. D. Vaaler, _Estimates for partial sums of continued fraction partial quotients_ , Pacific J. Math. 122 (1986), no. 1, 73–82.
  * [Fai97] C. Faivre, _On decimal and continued fraction expansions of a real number_ , Acta Arith. 82 (1997), no. 2, 119–128.
  * [Fai98] by same author, _A central limit theorem related to decimal and continued fraction expansion_ , Arch. Math. (Basel) 70 (1998), no. 6, 455–463.
  * [Fai01] by same author, _On calculating a continued fraction expansion from a decimal expansion_ , Acta Sci. Math. (Szeged) 67 (2001), no. 3-4, 505–519.
  * [FV98] P. Flajolet and B. Vallée, _Continued fraction algorithms, functional operators, and structure constants_ , Theoret. Comput. Sci. 194 (1998), no. 1-2, 1–34.
  * [FW12] A.-H. Fan and B.-W. Wang, _On the lengths of basic intervals in beta expansions_ , Nonlinearity 25 (2012), no. 5, 1329–1343.
  * [FWL16] L. Fang, M. Wu, and B. Li, _Limit theorems related to beta-expansion and continued fraction expansion_ , J. Number Theory 163 (2016), 385–405.
  * [FWL19] by same author, _Beta-expansion and continued fraction expansion of real numbers_ , Acta Arith. 187 (2019), no. 3, 233–253.
  * [Hal70] R. R. Hall, _A note on Farey series_ , J. London Math. Soc. (2) 2 (1970), 139–148.
  * [HW08] G. H. Hardy and E. M. Wright, _An introduction to the theory of numbers_ , sixth ed., Oxford University Press, Oxford, 2008.
  * [Ibr61] I. A. Ibragimov, _A theorem from the metric theory of continued fractions_ , Vestnik Leningrad. Univ. 16 (1961), no. 1, 13–24.
  * [IK02] M. Iosifescu and C. KraainKamp, _Metrical theory of continued fractions_ , Mathematics and Its Applications, Kluwer Academic Publisher, 2002.
  * [Khi35] A. Khintchine, _Metrische kettenbruchprobleme_ , Compositio Mathematica 1 (1935), 361–382.
  * [Khi97] A. Ya. Khinchin, _Continued fractions_ , russian ed., Dover Publications, Inc., Mineola, NY, 1997, Reprint of the 1964 translation.
  * [KSRSRS82] S. Kanemitsu, R. Sitaramachandra Rao, and A. Siva Rama Sarma, _Some sums involving Farey fractions. I_ , J. Math. Soc. Japan 34 (1982), no. 1, 125–142.
  * [Loc63] G. Lochs, _Die ersten $968$ Kettenbruchnenner von $\pi$_, Monatsh. Math. 67 (1963), 311–316.
  * [Lot02] M. Lothaire, _Algebraic combinatorics on words_ , Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002, Ed. by J. Berstel and D. Perrin.
  * [LW08a] B. Li and J. Wu, _Beta-expansion and continued fraction expansion_ , J. Math. Anal. Appl. 339 (2008), no. 2, 1322–1331.
  * [LW08b] by same author, _Beta-expansion and continued fraction expansion over formal Laurent series_ , Finite Fields Appl. 14 (2008), no. 3, 635–647.
  * [Mig91] F. Mignosi, _On the number of factors of Sturmian words_ , Theoret. Comput. Sci. 82 (1991), no. 1, Algorithms Automat. Complexity Games, 71–84.
  * [MZ04a] N. Moshchevitin and A. Zhigljavsky, _Entropies of the partitions of the unit interval generated by the Farey tree_ , Acta Arith. 115 (2004), no. 1, 47–58.
  * [MZ04b] by same author, _Entropies of the partitions of the unit interval generated by the Farey tree_ , Acta Arithmetica 115 (2004), 47–58.
  * [Phi88] W. Philipp, _Limit theorems for sums of partial quotients of continued fractions_ , Monatsh. Math. 105 (1988), no. 3, 195–206.
  * [PSZ16] G. Polanco, D. Schultz, and A. Zaharescu, _Continuous distributions arising from the three gap theorem_ , Int. J. Number Theory 12 (2016), no. 7, 1743–1764.
  * [PY98] M. Pollicott and M. Yuri, _Dynamical systems and ergodic theory_ , London Mathematical Society Student Texts, Cambridge University Press, 1998.
  * [Rén57] A. Rényi, _Representations for real numbers and their ergodic properties_ , Acta Math. Acad. Sci. Hungar. 8 (1957), 477–493.
  * [Sch95] F. Schweiger, _Ergodic theory of fibred systems and metric number theory_ , Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1995.
  * [Sla64] N. B. Slater, _Distribution problems and physical applications_ , Compositio Math. 16 (1964), 176–183 (1964).
  * [Sós58] V. T. Sós, _On the distribution mod 1 of the sequence $n\alpha$._, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 1 (1958), 127–134.
  * [Suŕ58] J. Suŕanyi, _Über die Anordnung der Vielfachen einer reellen Zahl mod 1._ , Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 1 (1958), 107–111 (German).
  * [Wu06] J. Wu, _Continued fraction and decimal expansions of an irrational number_ , Adv. Math. 206 (2006), 684–694.
  * [Wu08] by same author, _An iterated logarithm law related to decimal and continued fraction expansions_ , Monatsh. Math. 153 (2008), no. 1, 83–87.
  * [ZA99] A. Zhigljavsky and I. Aliev, _Weyl sequences: asymptotic distributions of the partition lengths_ , Acta Arith. 88 (1999), no. 4, 351–361.