# An infinite interval version of the $\alpha$-Kakutani equidistribution
problem

M. Pollicott and B. Sewell Partly supported by ERC-Advanced Grant
833802-Resonances and EPSRC grant EP/T001674/1 University of Warwick

###### Abstract

In this article we extend results of Kakutani, Adler–Flatto, Smilansky and
others on the classical $\alpha$-Kakutani equidistribution result for
sequences arising from finite partitions of the interval. In particular, we
describe a generalization of the equidistribution result to infinite
partitions. In addition, we give discrepancy estimates, extending results of
Drmota–Infusino [8].

##  1 Introduction

Uniform distribution of sequences of numbers $(x_{n})_{n=1}^{\infty}$ in the
unit interval has been an important area of interest for over a century. For
example, it was shown by Weyl [20] that, for any irrational $\alpha$, the
sequence $x_{n}=\alpha n$ (mod $1$) is uniformly distributed and Hardy and
Littlewood showed that, for almost all $\lambda>1$, the sequence
$x_{n}=\lambda^{n}$ (mod $1$) is uniformly distributed [13]. In this note we
consider another simple family of examples based on subdividing intervals.
Before introducing the original motivating example, we first fix our
terminology: a partition $\mathcal{P}$ is a set of closed, positive-length
intervals, which have pairwise disjoint interiors and cover $[0,1]$ up to a
set of Lebesgue measure zero.

###  1.1 The original $\alpha$-Kakutani equidistribution result

In 1973 Araki posed a problem which lead to Kakutani to prove an elegant
equidistribution result. (An interesting historical background is presented in
[1]). For clarity, we give a description of his original partition scheme,
which we generalise in the next section.

######  Definition ($\alpha$-Kakutani scheme).

For a fixed $0<\alpha<1$, the $\alpha$-Kakutani scheme is a sequence of
partitions $(\mathcal{P}_{n})_{n=0}^{\infty}$ defined inductively:

  * •

$\mathcal{P}_{0}=\big{\\{}[0,1]\big{\\}}$ is the trivial partition; and

  * •

$\mathcal{P}_{n+1}$ is obtained from $\mathcal{P}_{n}$ by taking each interval
of maximal length and subdividing it into two smaller intervals in the ratio
$\alpha:1-\alpha$.

######  Example 1.

Figure 1 shows the first seven partitions for the choice $\alpha=1/3$. Notice
that $\mathcal{P}_{5}$ is obtained by splitting two maximal length intervals
in $\mathcal{P}_{4}$ simultaneously (each of length 2/9). By contrast, the
choice $\alpha=1/2$ gives the trivial dyadic splitting.

$\mathcal{P}_{0}$$\mathcal{P}_{1}$$\mathcal{P}_{2}$$\mathcal{P}_{3}$$\mathcal{P}_{4}$$\mathcal{P}_{5}$$\mathcal{P}_{6}$$\mathcal{P}_{7}$$0$$1$$\frac{1}{3}$$\frac{5}{9}$$\frac{19}{27}$$\frac{1}{9}$$\frac{11}{27}$$\frac{5}{27}$$\frac{65}{81}$$\frac{211}{243}$
Figure 1: The first seven partitions $(\mathcal{P}_{n})_{n=0}^{7}$ of the
$\frac{1}{3}$-Kakutani scheme.

Consider the set of endpoints at the $n$th stage of this process,
$E_{n}=\bigcup_{I\in\mathcal{P}_{n}}\partial I$. Kakutani’s result is the
following.

######  Theorem (Kakutani).

For all $\alpha\in(0,1)$, the set $E_{n}$ becomes uniformly distributed as
$n\to\infty$.

###  1.2 Interval substitutions using multiple intervals

A natural generalisation of the $\alpha$-Kakutani scheme, first introduced by
Volčič in [18], is to alter the above process by splitting intervals of
maximal length according to a fixed finite partition consisting of $N\geq 2$
subintervals, say. That is, at each stage, one splits all intervals of maximal
length into $N$ pieces whose lengths have a certain fixed ratio,
$\alpha_{1}:\alpha_{2}:\dots:\alpha_{N}$, where the $\alpha_{i}$ sum to 1.

######  Example 2.

In Figure 2, we have the first seven partitions of the interval substitution
scheme in which one splits maximal intervals according to the partition
$\big{\\{}[0,\frac{1}{2}],[\frac{1}{2},\frac{2}{3}],[\frac{2}{3},1]\big{\\}}$,
i.e., with ratio $\frac{1}{2}:\frac{1}{6}:\frac{1}{3}$. By contrast, the
$\alpha$-Kakutani scheme corresponds to splitting according to the partition
$\big{\\{}[0,\alpha],[\alpha,1]\big{\\}}$.

$0$$1$$\frac{1}{2}$$\frac{2}{3}$$\frac{1}{4}$$\frac{1}{3}$$\frac{5}{6}$$\frac{8}{9}$$\ldots$$\mathcal{P}_{0}$$\mathcal{P}_{1}$$\mathcal{P}_{2}$$\mathcal{P}_{3}$$\mathcal{P}_{4}$$\mathcal{P}_{5}$$\mathcal{P}_{6}$$\mathcal{P}_{7}$
Figure 2: The first seven partitions $(\mathcal{P}_{n})_{n=0}^{7}$ of the
interval substitution scheme where one splits maximal-length intervals
according to the partition
$\mathcal{P}_{1}=\big{\\{}[0,\frac{1}{2}],[\frac{1}{2},\frac{2}{3}],[\frac{2}{3},1]\big{\\}}$.

One particular family of these schemes, that of so-called LS-sequences, which
include the $\phi$-Kakutani scheme for $\phi=\frac{1}{2}(\sqrt{5}-1)$, has
received particular attention in the context of low discrepancy sequences:
see, e.g., [3, 5, 6, 14, 19].

###  1.3 Interval substitutions using infinitely many intervals

In this note, we continue the process and ask in what way the result above
still holds if at every stage we insert an infinite partition $\mathcal{P}$
into each maximal-length subinterval. We denote by $\hat{E}_{n}$ the finite
set of endpoints of those intervals which have been split up to the $(n+1)$-st
stage, i.e.,

$\hat{E}_{n}:=\left\\{\min(I),\;\max(I)\;:\;I\in\bigcup_{i=0}^{n}\mathcal{P}_{i}\,\setminus\,\mathcal{P}_{n+1}\right\\}.$

######  Example 3.

In Figure 3 we depict $\mathcal{P}_{n}$ and $\hat{E}_{n}$ (for $n\leq 7$) for
the infinite substitution scheme generated by
$\mathcal{P}=\big{\\{}[0,\frac{1}{2}]\big{\\}}\cup\big{\\{}[1-\frac{1}{2}\cdot
3^{-n},1-\frac{1}{6}\cdot 3^{-n}]\big{\\}}_{n=0}^{\infty}$.

######  Example 4.

A wilder example: let the intervals in $\mathcal{P}$ be the connected
components of the compliment of the middle third Cantor set.

$\mathcal{P}_{0}$$\hat{E}_{0}$$\mathcal{P}_{1}$$\hat{E}_{1}$$\mathcal{P}_{2}$$\hat{E}_{2}$$\mathcal{P}_{3}$$\hat{E}_{3}$$\mathcal{P}_{4}$$\hat{E}_{4}$$\mathcal{P}_{5}$$\hat{E}_{5}$$\mathcal{P}_{6}$$\hat{E}_{6}$$\mathcal{P}_{7}$$\hat{E}_{7}$
Figure 3: An illustration of $(\mathcal{P}_{n})_{n=0}^{7}$ and
$(\hat{E}_{n})_{n=0}^{7}$ for the example generated by the partition
$\mathcal{P}=\big{\\{}[1,\frac{1}{2}]\big{\\}}\cup\big{\\{}[1-\frac{1}{2}\cdot
3^{-n},1-\frac{1}{6}\cdot 3^{-n}]\big{\\}}_{n=0}^{\infty}$. Here the tick
marks (which accumulate on certain points in the interval) denote the elements
of $E_{n}$ and the suspended yellow circles denote the elements of
$\hat{E}_{n}$.

For simplicity, we restrict our attention to the set of left endpoints, which
we shall denote by $L_{n}$, although we could equally well have chosen the
right endpoints, midpoints, etc.

Our main result is the following generalization of Kakutani’s equidistribution
theorem. Let $\|I\|$ denote the length of an interval $I$.

######  Theorem 1.

Let $\mathcal{P}$ be a countable partition. Then, provided that

$-\displaystyle\sum_{I\in\mathcal{P}}\|I\|\log\|I\|<\infty,$

the set $L_{n}$ becomes uniformly distributed as $n\to\infty$.

A brief outline of this note: In section 2, we give a new dynamical viewpoint
of the problem and in section 3, we apply renewal theory to prove Theorem 1 in
two cases. In section 4 we use a generating function to estimate the
discrepancy in the rank one case. In section 5 we use methods of analytic
number theory to estimate the discrepancy in the higher rank case, with a
generic Diophantine-type assumption.

Our interest in this problem, and the starting point for our analysis, began
with the very elegant work of Smilansky [17].

##  2 Partitions and similarities

Our approach to Theorem 1 is to express the elements of the partition
$\mathcal{P}$ in terms of the images of similarities. The refinements into
finer partitions, $\mathcal{P}_{n}$, can then be expressed in terms of words
formed from the index set of $\mathcal{P}$.

That is, one can write $\mathcal{P}=\\{T_{i}[0,1]\\}_{i\in\mathcal{I}}$, where
each $T_{i}:[0,1]\to[0,1]$ is an orientation preserving similarity with
contraction ratio $\alpha_{i}>0$. We see that $\mathcal{P}$ being a partition
is equivalent to the following:

  * •

$T_{i}[0,1)\cap T_{j}[0,1)=\emptyset$ for $i\neq j$; and

  * •

$\displaystyle\sum_{i\in\mathcal{I}}\alpha_{i}=1$.

######  Example 5.

Given $0=t_{0}<t_{1}<\cdots$ with $(t_{n})\to 1$, the partition
$\\{[t_{n-1},t_{n}]\\}_{n\in\mathbb{N}}$ is equal to
$\\{T_{n}[0,1]\\}_{n\in\mathbb{N}}$, where

$T_{n}(x)=(t_{n}-t_{n-1})x+\sum_{k=0}^{n-1}t_{n}.$

######  Example 6.

Setting $t_{n}=1-\frac{1}{6}\,3^{-n}$ for $n\geq 1$ gives rise to
$\mathcal{P}_{1}$ in Figure 3.

We now explain how this can be used to give an explicit description of the
splitting process.

######  Definition ($(T_{i})$-refinement).

Given a partition $\mathcal{P}=\\{S_{k}[0,1]\\}_{k}$, where the
$\\{S_{k}\\}_{k}$ are orientation preserving similarities, the
$(T_{i})$-refinement of $\mathcal{P}$ is the refinement obtained by taking all
intervals of maximal length in $\mathcal{P}$ and replacing them by
subintervals in the following manner: if $S[0,1]\in\mathcal{P}$ has maximal
length in $\mathcal{P}$, then it is replaced by the elements of the set

$\\{S\circ\,T_{i}[0,1]\;|\;i\in\mathcal{I}\\}.$

######  Definition (Interval substitution scheme).

The interval substitution scheme generated by $\\{T_{i}\\}_{i\in\mathcal{I}}$
is the sequence of partitions $(\mathcal{P}_{n})_{n=0}^{\infty}$ defined as
follows:

  * •

$\mathcal{P}_{0}$ is the trivial partition,
$\mathcal{P}_{0}=\big{\\{}[0,1]\big{\\}}$; and

  * •

$\mathcal{P}_{n+1}$ is the $(T_{i})$-refinement of $\mathcal{P}_{n}$.

This gives a convenient presentation of the partitions.

######  Example 7.

The $\alpha$-Kakutani scheme is the interval substitution scheme generated by
the pair $T_{1}:x\mapsto\alpha x$ and $T_{2}:x\mapsto(1-\alpha)x+\alpha$.

######  Example 8.

Similarly, the interval substitution scheme generated by the triple
$T_{1}:x\mapsto x/2$, $T_{2}:x\mapsto(x+3)/6$ and $T_{3}:x\mapsto(x+2)/3$
gives the sequence of partitions depicted in Figure 2.

We now associate to the sequence of partitions
$(\mathcal{P}_{n})_{n=0}^{\infty}$ a sequence of families of left endpoints of
split intervals, $(L_{n})_{n=0}^{\infty}$.

######  Definition ($L_{n}$).

Given an interval substitution scheme $(\mathcal{P}_{n})_{n=0}^{\infty}$
generated by similarities $(T_{i})_{i\in\mathcal{I}}$, we define the finite
sets $L_{n}$ ($n\geq 0$) to be

$L_{n}=\bigcup_{k=0}^{n}\
\bigcup_{I\in\mathcal{P}_{k}\setminus\mathcal{P}_{k+1}}\min(I).$

######  Remark.

One can consider a generalisation of the above process by dropping the
assumption that the $(T_{i})_{i}$ have to be affine. We will not consider this
more general setting, but we note it is easy to give superficial examples
where $E_{n}$ (or $L_{n}$) is not uniformly distributed: take, for example,
$T_{1}(x)=\sqrt{x}/2$, $T_{2}(x)=(x+1)/2$.

Considering the interval substitution scheme generated by
$\\{T_{i}\\}_{i\in\mathcal{I}}$, it follows inductively that every interval
appearing in the process is obtained by applying a sequence of maps from
$\\{T_{i}\\}_{i}$ to $[0,1]$, and so each is naturally described by a finite
word in $\mathcal{I}$. It is convenient to introduce the following notation.

######  Definition ($W(\mathcal{I})$, $\ast$, $\alpha_{\boldsymbol{v}}$,
$T_{\boldsymbol{v}}$).

Given a countable set $\mathcal{I}$, the word set $W(\mathcal{I})$ is the
semigroup consisting of all words in $\mathcal{I}$: i.e.

$W(\mathcal{I})=\\{\emptyset\\}\cup\bigcup_{n=1}^{\infty}\mathcal{I}^{n},$

where $\emptyset$ denotes the empty word (unique word of length zero), and the
semigroup operation $\ast:W(\mathcal{I})\times W(\mathcal{I})\to
W(\mathcal{I})$ denotes concatenation of words, for which $\emptyset$ acts as
the identity:

$(n_{1},\ldots,n_{k})\ast(m_{1},\ldots,m_{j})=(n_{1},\ldots,n_{k},m_{1},\ldots,m_{j});\qquad{\boldsymbol{v}}\ast\emptyset=\emptyset\ast{\boldsymbol{v}}={\boldsymbol{v}}.$

Furthermore, for ease of notation, we extend the definitions of $\alpha_{i}$
and $T_{i}$ to the whole of $W(\mathcal{I})$: For the word
${\boldsymbol{v}}=(i_{1},\ldots,i_{k})\in\mathcal{I}^{k}$, define

$\alpha_{\boldsymbol{v}}:=\prod_{j=1}^{k}\alpha_{i_{j}},\qquad
T_{\boldsymbol{v}}:=T_{i_{1}}\circ\ldots\circ T_{i_{k}},$

and also define $\alpha_{\emptyset}=1$ and $T_{\emptyset}=\text{Id}_{[0,1]}$.

That is, given any interval $I$ which appears in the process,
$I=T_{\boldsymbol{v}}[0,1]$ for some word ${\boldsymbol{v}}\in
W(\mathcal{I})$***Similarly, every word ${\boldsymbol{v}}\in\mathcal{I}$ gives
rise to an interval in some $\mathcal{P}_{n}$, and will be split between
$\mathcal{P}_{n}$ and $\mathcal{P}_{n+1}$ (i.e.,
$I\in\mathcal{P}_{n}\setminus\mathcal{P}_{n-1}$) precisely when $n$ satisfies

$\alpha_{\boldsymbol{v}}=\max_{I\in\mathcal{P}_{n}}\big{\\{}\|I\|\big{\\}},$

and consequently its left endpoint $T_{\boldsymbol{v}}(0)$ will appear in
$L_{n}$, if not already present in $L_{n-1}$.

Rather than using $n$ in $\\{L_{n}\\}_{n\geq 1}$ to parametrise this process,
we want to reparameterise this family to reflect the lengths of the maximal
intervals, and rewrite it as $(X_{\lambda})$ as follows.

######  Definition.

For $\lambda>1$, let $X_{\lambda}=\emptyset$, and for $\lambda\in(0,1]$, let

$X_{\lambda}:=L_{n(\lambda)},\quad\text{where}\quad n(\lambda):=\max\\{n\geq
0\,:\,\forall I\in\mathcal{P}_{n},\ \|I\|\geq\lambda\\}.$

I.e., given $\lambda\leq 1$, $P_{n(\lambda)+1}$ is the first partition in the
process for which all intervals have lengths strictly smaller than $\lambda$.
From the previous discussion, one obtains a convenient, dynamical formula for
$X_{\lambda}$:

$X_{\lambda}=\big{\\{}T_{\boldsymbol{v}}(0)\,:\,{\boldsymbol{v}}\in
W(\mathcal{I}),\,\alpha_{\boldsymbol{v}}\geq\lambda\big{\\}}.$

As $\lambda\to 0^{+}$, $n(\lambda)\to\infty$ and so the uniform distribution
of $L_{n}$ as $n\to\infty$ is equivalent to that of $X_{\lambda}$ as
$\lambda\to 0^{+}$. As an aside, this is equivalent to the convergence of the
probablity measure $\mu_{\lambda}$,

$\mu_{\lambda}=\frac{1}{|X_{\lambda}|}\sum_{x\in X_{\lambda}}\delta_{x},$

to the Lebesgue measure (which we will henceforth denote as
$\operatorname{Leb}$), as $\lambda\to 0^{+}$, where $\delta_{x}$ denotes the
Dirac delta measure at $x$, and $|\cdot|$ denotes cardinality (of a finite
set).

##  3 Proof of Theorem 1

This section is devoted to proving the main result, which we can conveniently
rephrase in the following way.

######  Theorem 1.

Provided that $-\sum_{I\in\mathcal{P}}\|I\|\log\|I\|<\infty$, the measures
$\mu_{\lambda}$ converge to the Lebesgue measure $\operatorname{Leb}$ as Borel
measures as $\lambda\to 0^{+}$, i.e., for any interval $J\subset[0,1]$, we
have $\mu_{\lambda}(J)\to\operatorname{Leb}(J)=\|J\|$.

We first prove the convergence for a given interval of the form
$T_{\boldsymbol{v}}[0,1)$. For each of these elementary sets, their
$\mu_{\lambda}$-measure is intimately related to the asymptotics of
$|X_{\lambda}|$ as $\lambda\to 0^{+}$. To proceed, we can relate
$|X_{\lambda}|$ to the set of words $|A_{\lambda}|$, where

$A_{\lambda}:=\\{{\boldsymbol{w}}\in
W(\mathcal{I})\,|\,\alpha_{\boldsymbol{w}}\geq\lambda\\},$

and exploit a natural renewal equation for the quantity
$\lambda|A_{\lambda}|$.

######  Lemma 1.

One of the following two cases hold. Either there is a (unique) symbol in
$1\in\mathcal{I}$, say, such that $T_{1}(0)=0$; in which case, for all
$\lambda>0$,

$|A_{\lambda}|=\sum_{k=0}^{\infty}|X_{\lambda\alpha_{1}^{-k}}|\ \iff\
|X_{\lambda}|=|A_{\lambda}|-|A_{\lambda/\alpha_{1}}|;$ (1)

or no element of $\\{T_{\boldsymbol{w}}\\}_{{\boldsymbol{w}}\in
W(\mathcal{I})}$ fixes 0, and $|X_{\lambda}|=|A_{\lambda}|$ for all
$\lambda>0$.

###### Proof of Lemma 1.

Let ${\boldsymbol{w}},{\boldsymbol{v}}\in A_{\lambda}$ satisfy
$T_{\boldsymbol{w}}(0)=T_{\boldsymbol{v}}(0)$. If
${\boldsymbol{w}}\neq{\boldsymbol{v}}$, the disjointness of $T_{i}[0,1)$ and
the injectivity of the $T_{i}$ imply inductively that one of these words is
obtained from the other by concatenation with a word fixing the identity;
i.e., without loss of generality,
${\boldsymbol{w}}={\boldsymbol{v}}\ast{\boldsymbol{j}}$, where
${\boldsymbol{j}}\in W(\mathcal{I})$ satisfies $T_{\boldsymbol{j}}(0)=0$. We
now have the two cases:

If there is no symbol $i\in\mathcal{I}$ for which $T_{i}(0)=0$, we must have
${\boldsymbol{j}}=\emptyset$; which implies the map ${\boldsymbol{v}}\mapsto
T_{\boldsymbol{v}}(0)$ is a bijection $A_{\lambda}\to X_{\lambda}$.

For the other case, let $1\in\mathcal{I}$ be such that $T_{1}(0)=0$; it is
unique by the disjointness of $T_{i}[0,1)$. Then
${\boldsymbol{j}}\neq\emptyset$ only if
${\boldsymbol{j}}\in\\{1\\}^{k}\subset\mathcal{I}^{k}$ for some
$k\in\mathbb{N}$, i.e., ${\boldsymbol{j}}$ is a tuple of 1’s. It follows that,
for each $y\in X_{\lambda}$, there is a unique word
${\boldsymbol{v}}_{0}(y)\in A_{\lambda}$ satisfying

  * •

$T_{{\boldsymbol{v}}_{0}(y)}(0)=y$; and

  * •

$T_{\boldsymbol{v}}(0)=y\implies{\boldsymbol{v}}={\boldsymbol{v}}_{0}(y)\ast{\boldsymbol{j}}$,
for some ${\boldsymbol{j}}\in\\{\emptyset\\}\cup\\{1\\}^{k}$,
$k\in\mathbb{N}$.

In particular, $T_{\boldsymbol{v}}(0)=y$ implies
$\alpha_{\boldsymbol{v}}=\alpha_{{\boldsymbol{v}}_{0}(y)}\alpha_{1}^{k}$, for
some $k\in\mathbb{N}_{0}$. In other words, there is exactly one element of
$A_{\lambda}\setminus A_{\lambda/\alpha_{1}}$, $n_{0}(y)$, which gets mapped
onto $y$. Therefore, ${\boldsymbol{v}}\mapsto T_{\boldsymbol{v}}(0)$ gives a
bijection $A_{\lambda}\setminus A_{\lambda/\alpha_{1}}\to X_{\lambda}$. The
right hand side of (1) follows, completing the proof. ∎

Now, to continue the proof of the theorem, we combine the previous lemma with
the following, which expresses $\mu_{\lambda}(T_{\boldsymbol{v}}[0,1))$ as a
ratio involving $|X_{\lambda}|$.

######  Lemma 2.

For all ${\boldsymbol{v}}\in W(\mathcal{I})$ and $\lambda\in(0,1]$,

$|T_{\boldsymbol{v}}[0,1)\cap
X_{\lambda\alpha_{\boldsymbol{v}}}|=|X_{\lambda}|.$ (2)

In particular, for all $\lambda\in(0,\alpha_{\boldsymbol{v}}]$,

$\mu_{\lambda}(T_{\boldsymbol{v}}[0,1))=\frac{|X_{\lambda/\alpha_{\boldsymbol{v}}}|}{|X_{\lambda}|}.$
(3)

Moreover, if ${\boldsymbol{v}}=\emptyset$, or
${\boldsymbol{v}}={\boldsymbol{w}}\ast i$ with $T_{i}(0)\neq 0$, these hold
for all $\lambda>0$.

###### Proof of Lemma 2.

Fix ${\boldsymbol{v}}\in W(\mathcal{I})$ and consider (2). First let
$\lambda\leq 1$. By induction, using the properties of the $T_{i}$, if
$T_{\boldsymbol{w}}(0)\in T_{\boldsymbol{v}}[0,1)$, then, either
${\boldsymbol{w}}={\boldsymbol{v}}\ast{\boldsymbol{j}}$ or
${\boldsymbol{v}}={\boldsymbol{w}}\ast{\boldsymbol{j}}$, for some
${\boldsymbol{j}}\in W(\mathcal{I})$. Moreover, if ${\boldsymbol{w}}\in
A_{\lambda\alpha_{\boldsymbol{v}}}$, the second option gives a contradiction:
$\alpha_{\boldsymbol{w}}>\alpha_{\boldsymbol{v}}\geq\lambda\alpha_{\boldsymbol{v}}\geq\alpha_{\boldsymbol{w}}$.
Thus, we have

$T_{\boldsymbol{v}}[0,1)\cap
X_{\lambda\alpha_{\boldsymbol{v}}}=\\{T_{{\boldsymbol{v}}\ast{\boldsymbol{j}}}(x)\,:\,{\boldsymbol{j}}\in
A_{\lambda}\\}.$

By injectivity of $T_{\boldsymbol{v}}$, the right hand side bijectively
corresponds to $X_{\lambda}$, giving (2). Applying (2), with
$\lambda/\alpha_{\boldsymbol{v}}$ in place of $\lambda$ and dividing by
$|X_{\lambda}|$ yields (3).

As for the final remark, now let $\lambda>1$. This implies the second option
holds, ${\boldsymbol{v}}={\boldsymbol{w}}\ast{\boldsymbol{j}}$, since the
first is satisfied only if $\lambda\leq 1$, by a similar contradiction
argument. It follows that $T_{\boldsymbol{j}}(0)=0$ and thus, as in the proof
of Lemma 1, ${\boldsymbol{j}}\in\\{1\\}^{k}$ for some $k\in\mathbb{N}$. This
contradicts the assumptions of the remark; thus both the left and the right
hand side of $\eqref{eq - Tn X alfla}$ are empty when $\lambda>1$. The lemma
follows. ∎

The significance of relating $|X_{\lambda}|$ to $|A_{\lambda}|$ will now
become clear from the following renewal equation.

######  Lemma 3.

The following holds for all $\lambda>0$.

$|A_{\lambda}|=\sum_{i\in\mathcal{I}}|A_{\lambda/\alpha_{i}}|+\raisebox{-2.0pt}{\scalebox{1.3}{$\chi$}\vphantom{\big{(}}}_{\\{\lambda\leq
1\\}},$ (4)

where $\chi$ is the indicator function. Equivalently, the following renewal
equation applies, for $Z(t):=e^{-t}|A_{e^{-t}}|$.

$Z(t)=\sum_{i\in\mathcal{I}}\alpha_{i}Z\big{(}t-\log({\alpha_{i}}^{-1})\big{)}+e^{-t}\raisebox{-2.0pt}{\scalebox{1.3}{$\chi$}\vphantom{\big{(}}}_{\\{t\geq
0\\}},\qquad\forall\,t\in\mathbb{R}.$

###### Proof of Lemma 3.

The second equation is a restatement of the first, (4). One can obtain (4) by
partitioning the non-empty words in $A_{\lambda}$ according to their first
symbol. That is, one can write the following disjoint union.

$A_{\lambda}\setminus\\{\emptyset\\}=\bigsqcup_{i\in\mathcal{I}}\underbrace{\\{i\ast{\boldsymbol{v}}\in
W(\mathcal{I})\,|\,\alpha_{\boldsymbol{v}}\leq\lambda/\alpha_{i}\\}}_{\text{in
bijection with }A_{\lambda/\alpha_{i}}}.$

This gives rise to the sum in (4). Accounting for $\emptyset$, $\emptyset\in
A_{\lambda}$ if and only if $\lambda\leq 1$, thus providing the indicator term
in (4), and completing the proof. ∎

To make use of this renewal equation, just as in [2, 8, 17] it is necessary to
consider two cases which behave somewhat differently. These cases correspond
to, for example, the $\alpha$-Kakutani schemes for $\alpha=1/3$ and
$\alpha=1/2$, as described in the introduction.

######  Definition (Rank).

For $n\in\mathbb{N}$ we will say the collection
$\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ is rank $n$ if the smallest additive
subgroup of $\mathbb{R}$ containing the set
$\\{-\log(\alpha_{i})\\}_{i\in\mathcal{I}}$ is isomorphic to $\mathbb{Z}^{n}$.
If $\\{\alpha_{i}\\}_{i}$ is not rank $n$ for any $n\in\mathbb{N}$ we will say
$\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ is infinite rank. Also, whenever
$\\{\alpha_{i}\\}_{i}$ is not rank one, we say it is higher rank.

######  Example 9.

The following examples illustrate the different ranks:

  1. 1.

$\\{1/2^{n}\\}_{n\in\mathbb{N}}$ is rank one;

  2. 2.

$\\{1/2\\}\cup\\{1/3^{n}\\}_{n\in\mathbb{N}}$ is rank two;

  3. 3.

$\\{1/2\\}\cup\\{1/3\\}\cup\\{1/7^{n}\\}_{n\in\mathbb{N}}$ is rank three; and

  4. 4.

$\\{1/n^{s}\\}_{n=2}^{\infty}$ is infinite rank, where $s\approx 1.728$
satisfies $\zeta(s)=2$ (here $\zeta$ denotes the Riemann zeta function).

###  3.1 Uniform distribution in the rank one case

In this subsection, we concentrate on the rank one case, also known as the
arithmetic, rationally-related or commensurable case (see [2, 8, 17]). The
characteristic feature of this case is that the contraction ratios are all
powers of a common number,
$\\{\alpha_{i}\\}_{i\in\mathcal{I}}\subset\\{x^{n}\\}_{n\in\mathbb{N}}$.
Thereby, fixing the minimal such $x>0$, equation (4) defines a discrete
renewal equation on the lattice $-\log(x)\mathbb{Z}$, and one can apply the
Erdős-Feller-Pollard renewal theorem (see [11]) to obtain the following lemma.

######  Lemma 4 (Erdős-Feller-Pollard renewal theorem).

Suppose that $\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ is rank one, that $x>0$ is
the minimal positive number for which
$\\{\alpha_{i}\\}_{i\in\mathcal{I}}\subset\\{x^{n}\\}_{n\in\mathbb{N}}$, and
that $H:=-\sum_{i}\alpha_{i}\log(\alpha_{i})<\infty$, then

$Z\big{(}-n\log(x)\big{)}\to\frac{1}{H}\quad\text{as }n\to\infty,\
n\in\mathbb{N};$

where $Z(\cdot)$ is defined in Lemma 3.

This lemma yields the following corollary, all but completing the proof of the
theorem in this case.

######  Corollary.

For $\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ and $H$ as in the previous lemma, the
following hold as $n\to\infty$, $n\in\mathbb{N}$:

  * •

$|A_{x^{n}}|\sim x^{-n}/H$.

  * •

For all ${\boldsymbol{v}}\in W(\mathcal{I})$,
$\mu_{x^{n}}(T_{\boldsymbol{v}}[0,1))\to\alpha_{\boldsymbol{v}}=\operatorname{Leb}(T_{\boldsymbol{v}}[0,1))$.

###### Proof of Corollary.

The first item is simply a restatement of the conclusion of Lemma 4. The
second item follows with an application of Lemmas 1 and 2. For
$n\in\mathbb{N}$ we have one of the following, according to the two cases of
Lemma 1: Either no $T_{i}$ fixes $0$, and

$\mu_{x^{n}}(T_{\boldsymbol{v}}[0,1))=\frac{|A_{x^{n}\alpha_{\boldsymbol{v}}^{-1}}|}{|A_{x^{n}}|}\sim\frac{\big{(}\alpha_{\boldsymbol{v}}^{-1}x^{n}\big{)}^{-1}/H}{x^{-n}/H}=\alpha_{\boldsymbol{v}};$

or, for $T_{1}(0)=0$ and ${\boldsymbol{v}}_{0}$ the longest subword of
${\boldsymbol{v}}$ not ending in a 1,

$\displaystyle\mu_{x^{n}}(T_{\boldsymbol{v}}[0,1))$
$\displaystyle=\frac{|A_{{x^{n}}\alpha_{\boldsymbol{v}}^{-1}}|-|A_{{x^{n}}(\alpha_{\boldsymbol{v}}\alpha_{1})^{-1}}|+\raisebox{-2.0pt}{\scalebox{1.3}{$\chi$}\vphantom{\big{(}}}_{\\{\alpha_{\boldsymbol{v}}<{x^{n}}\leq\alpha_{{\boldsymbol{v}}_{0}}\\}}}{|A_{{x^{n}}}|-|A_{{x^{n}}\alpha_{1}^{-1}}|}$
$\displaystyle\sim\frac{1-\alpha_{1}}{1-\alpha_{1}}\frac{\alpha_{\boldsymbol{v}}x^{-n}/H}{x^{-n}/H}=\alpha_{\boldsymbol{v}}$

as $n\to\infty$, as required. ∎

The last, easy, step in the proof of Theorem 1 concerns packing intervals of
the form $T_{\boldsymbol{v}}[0,1)$ into a given interval. This will be written
as if in the continuous case. For the rank one case, for $\lambda\to 0^{+}$,
one can read $\lambda=x^{n},$ $n\to\infty$; in fact, it is a trivial matter to
prove they are equivalent.

###### Proof of Theorem 1.

Let $I\subset[0,1]$ be an interval, and let
$\alpha_{\max}=\max_{i\in\mathcal{I}}(\alpha_{i})$. For $n\in\mathbb{N}$, let

$U_{n}:=\\{{\boldsymbol{v}}\in\mathcal{I}^{n}\,:\,T_{\boldsymbol{v}}[0,1)\subset
I\\}.$

We claim the total length of intervals corresponding to $U_{n}$ approximates
the length of $I$, as follows:

$\sum_{{\boldsymbol{v}}\in
U_{n}}\|T_{\boldsymbol{v}}[0,1)\|\geq\|I\|-2\alpha_{\max}^{n}.$ (5)

To prove this, take $x\in I\setminus\bigcup_{{\boldsymbol{v}}\in
U_{n}}T_{\boldsymbol{v}}[0,1)$. Then one of the following hold:

  1. 1.

$x\in
K_{n}:=[0,1]\setminus\bigcup_{{\boldsymbol{v}}\in\mathcal{I}^{n}}T_{\boldsymbol{v}}[0,1)$.
An inductive argument shows, for all $\lambda$ and $n$,
$\mu_{\lambda}(K_{n})=0=\text{Leb}(K_{n})$.

  2. 2.

$x\in T_{\boldsymbol{w}}[0,1)$ for some
${\boldsymbol{w}}\in\mathcal{I}^{n}\setminus U_{n}$. Since
$T_{\boldsymbol{w}}[0,1)\not\subset I$, it is an interval meeting $\partial
I$; thus there are at most two ${\boldsymbol{w}}\in\mathcal{I}^{n}$ with this
property.

In other words, $I\setminus\bigcup_{{\boldsymbol{v}}\in
U_{n}}T_{\boldsymbol{v}}[0,1)\setminus K_{n}$ comprises at most two intervals,
each with length at most $\alpha_{\max{}}^{n}$. (5) follows.

To apply this, let $U$ be a union of a finitely number of intervals in
$U_{n}$, and let $\|U\|$ denote its total length (i.e.,
$\operatorname{Leb}(U)$). Then $\mu_{\lambda}(I)\geq\mu_{\lambda}(U)$ and

$\liminf_{\lambda\to 0^{+}}\mu_{\lambda}(I)\geq\lim_{\lambda\to
0^{+}}\mu_{\lambda}(U)=\|U\|.$

Taking the supremum over all such finite unions $U$ gives

$\liminf_{\lambda\to
0^{+}}\mu_{\lambda}(I)\geq\|S\|\geq\|I\|-2\alpha_{\max}^{n}.$

Repeating the above argument for the 0, 1 or 2 intervals comprising
$[0,1]\setminus I$ yields a converse inequality for $\|I\|$:

$\limsup_{\lambda\to 0^{+}}\mu_{\lambda}(I)\leq\|I\|+2\alpha_{\max}^{n},$

and the proof is completed by taking $n\to\infty$. ∎

###  3.2 Uniform distribution in the higher rank case

In the remaining, generic case, the proof is very similar to the above. It
continues with the following lemma, a convenient application of the Blackwell
renewal theorem (see [4]).

######  Lemma 5 (Blackwell renewal theorem).

Suppose that $\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ is not rank one and that
$H=-\sum_{i}\alpha_{i}\log(\alpha_{i})<\infty$. Then one has the continuous
limit

$Z(t)\to\frac{1}{H}\quad\text{as }t\to\infty,$

where $Z(\cdot)$ is defined in Lemma 3.

This gives the following corollary. The proof is similar to that of the
preceding, with the convergence now taking place as $\lambda\to 0^{+}$.

######  Corollary.

For $\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ as in the previous lemma, the
following hold as $\lambda\to 0^{+}$.

  * •

$|A_{\lambda}|\sim 1\big{/}\lambda H$,

  * •

For all ${\boldsymbol{v}}\in W(\mathcal{I})$,
$\mu_{\lambda}(T_{\boldsymbol{v}}[0,1))\to\alpha_{\boldsymbol{v}}=\operatorname{Leb}(T_{\boldsymbol{v}}[0,1))$.

The conclusion of Theorem 1 in this case is the same as given in the
proceeding case, see p.3.1.

######  Remark.

The same method of proof gives a more general result. Suppose we have a set
$\mathbb{X}$ equipped with a probability measure $\nu$, and there is a
collection $\\{T_{i},\alpha_{i}\\}_{i\in\mathcal{I}}$ such that

  * a)

$T_{i}:\mathbb{X}\to\mathbb{X}$ are injective $\nu$-measurable functions;

  * b)

for all $i,j\in\mathcal{I}$ distinct, $T_{i}(\mathbb{X})\cap
T_{j}(\mathbb{X})=\emptyset$;

  * c)

for all ${\boldsymbol{v}}\in W(\mathcal{I})$,
$\nu(T_{\boldsymbol{v}}(\mathbb{X}))=\alpha_{\boldsymbol{v}}$;

  * d)

$\alpha_{i}>0$ for all $i\in\mathcal{I}$ and
$\sum_{i\in\mathcal{I}}\alpha_{i}=1$; and

  * e)

$-\sum_{i\in\mathcal{I}}\alpha_{i}\log(\alpha_{i})<\infty$.

Then, for any
$x\in\mathbb{X}\setminus\bigcup_{i\in\mathcal{I}}T_{i}(\mathbb{X})$, and for
any $\nu$-measurable set $S$ which can be written as

$S=\bigcup_{{\boldsymbol{v}}\in V}T_{\boldsymbol{v}}(\mathbb{X})$

(with $V$ is any subset of $w(\mathcal{I})$), we have, as $\lambda\to 0^{+}$,

$\frac{|S\,\cap\,X_{\lambda}(x)|}{|X_{\lambda}(x)|}\to\nu(S),$

where $X_{\lambda}(x)=\\{T_{\boldsymbol{v}}(x)\,:\;{\boldsymbol{v}}\in
W(\mathcal{I}),\ \alpha_{\boldsymbol{v}}\geq\lambda\\}$.

It is also possible to generalise the method of proof to include substitution
schemes starting from arbitrary partitions, and one recovers results analogous
to those of [2].

These will be discussed in greater depth in the forthcoming doctoral thesis of
the second author.

##  4 Discrepancy estimates

In [18], the author both generalised the method used by Adler and Flatto in
[1] to general finite partitions, and posed questions which inspired various
other papers. Of particular interest is the behaviour of the discrepancy. This
corresponds to estimating the speed of convergence (where the $I$ are
intervals) of

$\sup_{I\subset[0,1]}\big{|}\,\mu_{\lambda}(I)-\|I\|\,\big{|}\to 0\hbox{ as
}\lambda\to 0^{+}.$

The Koksma inequality uses such estimates to give convergence rates for
integrals of bounded-variation functions. Hence, fast-decaying discrepancies
provide potential computationally-efficient numerical integration techniques.
The theory of discrepancies (of equidistributing sets and sequences) has
naturally received a lot of attention (see, e.g., [9] for an overview). There
are also interesting open problems, for example on optimal discrepancy in
higher dimensions.

Regarding interval substitution schemes, in the finite-partition case,
discrepancy estimates are provided by Drmota–Infusino in [8], extending the
application-focused work of Carbone in [5]. We in turn extend this to the
context of infinite partitions. The results obtained here are different,
depending on whether we are in the rank one case or the higher rank case.

###  4.1 Discrepancy estimates in the rank one case

In this final section, we extend the analysis of the rank one case to estimate
the discrepancy between the measure $\mu_{\lambda}$ and the Lebesgue measure.
More precisely, we have the following result.

######  Theorem 2.

Suppose that

  1. 1.

$\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ is rank one;

  2. 2.

$x>0$ is the smallest number for which
$\\{\alpha_{i}\\}_{i\in\mathcal{I}}\subset\\{x^{n}\\}_{n\in\mathbb{N}}$; and

  3. 3.

there is some $\varepsilon>0$ for which
$\sum_{i\in\mathcal{I}}\alpha_{i}^{1-\varepsilon}<\infty$.

Then there is an $R^{\ast}\in(0,1)$, made explicit in Lemma 6 below, such
that, for all $\rho\in(x/R^{\ast},1)$, there is a constant $C>0$ such that,
for all $n\in\mathbb{N}$ and all intervals $I\subset[0,1]$,

$\big{|}\,\mu_{x^{n}}(I)-\|I\|\,\big{|}\leq C\rho^{n}.$

The proof of Theorem 2 begins with the following light lemma, defining
$R^{\ast}$ in terms of a generating function for $|A_{x^{n}}|$.

######  Lemma 6.

Given $\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ as in Theorem 2, the function
formally defined by

$g(z)=(z-x)\sum_{n=0}^{\infty}|A_{x^{n}}|z^{n}$

has a holomorphic extension to the open disk of radius $R^{\ast}$ about 0,
where

$R^{\ast}:=\min\left(\\{x^{1-\varepsilon}\\}\cup\big{\\{}|z|\;:\>z\in\mathbb{C}\setminus\\{x\\},\
\sum_{j\in\mathcal{I}}z^{n_{j}}=1\big{\\}}\right)>x$

and where $n_{i}:=\log_{x}(\alpha_{i})$. Therefore, denoting by $b_{n}$ the
$n$th Taylor coefficient of $g$, given $R<R^{\ast}$, there exists $C>0$ such
that, for all $n\in\mathbb{N}$, $b_{n}\leq CR^{-n}$.

###### Proof of Lemma 6.

From (4), the renewal equation of Lemma 3, one has, for $|z|\leq
x^{1-\varepsilon}$ and $z\neq x$,

$\displaystyle\frac{g(z)}{z-x}=\sum_{n=0}^{\infty}|A_{x^{n}}|z^{n}$
$\displaystyle=\sum_{n=0}^{\infty}\left(\sum_{j\in\mathcal{I}}|A_{x^{n-n_{j}}}|+1\right)z^{n}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{j\in\mathcal{I}}|A_{x^{n-n_{i}}}|z^{n}+\frac{1}{1-z}$
$\displaystyle=\sum_{j\in\mathcal{I}}z^{n_{j}}\sum_{n=0}^{\infty}|A_{x^{n-n_{j}}}|z^{n-n_{i}}+\frac{1}{1-z}$
$\displaystyle=\sum_{j\in\mathcal{I}}z^{n_{j}}\frac{g(z)}{z-x}+\frac{1}{1-z},$

which rearranges to

$g(z)=\frac{z-x}{(z-1)(\sum_{j\in\mathcal{I}}z^{n_{j}}-1)}.$

Therefore, $g$ has a meromorphic expansion on the disk of convergence of

$z\mapsto\sum_{j\in\mathcal{I}}z^{n_{j}};$ (6)

which has radius at least $x^{1-\varepsilon}$, by assumption on the decay of
$\\{\alpha_{i}\\}$.

An elementary argument (see [11, pp.201–2]) shows that $z=x$ is not only a
simple root of (6) with residue $1/H$ (see the statement of Lemmas 4 or 5),
but it is also the only root of (6) in the closed disk $\\{|z|\leq x\\}$.
Therefore, $g$ is holomorphic on the open disk of radius $R^{\ast}>x$, where
$R^{\ast}$ is the absolute value of the next smallest root of (6), or equal
$x^{1-\varepsilon}$ if no other root exists. ∎

######  Example 10.

In certain nice cases, one can say more. For the simplest infinite example,
$\alpha_{n}=2^{-n}$ ($n\in\mathbb{N}$), $g(z)\equiv 1/2$ is constant.

The final stage of the proofs of Theorems 2 and 3 is similar to that of
Theorem 1, but the method of splitting up a general interval needs a little
more care. We will only prove the case that none of the $T_{i}$ fix $0$, since
the other case is similar but tedious.

###### Proof of Theorem 2.

For simplicity, consider the interval $I=[b,1)$, for fixed $b\in(0,1)$, and
assume that no $i\in\mathcal{I}$ satisfies $T_{i}(0)=0$. For $n\in\mathbb{N}$,
let $V_{n}$ denote the elements of $U_{n}$ (where $U_{n}$ is in the proof of
Theorem 1) whose interval is not contained in one from $U_{n^{\prime}}$ for
any $n^{\prime}<n$. More explicitly,

$V_{1}:=\big{\\{}i\in\mathcal{I}\;:\;T_{i}[0,1)\subset I\big{\\}}=U_{1},$

and, for $n\geq 2$,

$\displaystyle V_{n}$ $\displaystyle:=\big{\\{}{\boldsymbol{v}}\ast
i\in\mathcal{I}^{n}\;:\;i\in\mathcal{I},\ T_{{\boldsymbol{v}}\ast
i}[0,1)\subset I\text{ but }T_{{\boldsymbol{v}}}[0,1)\not\subset I\big{\\}}$
$\displaystyle\phantom{:}=U_{n}\setminus U_{n-1}.$

It is simple to show the union over all intervals coming from the $V_{n}$,

$\bigcup_{n=1}^{\infty}\bigcup_{{\boldsymbol{v}}\in
V_{n}}T_{\boldsymbol{v}}[0,1),$

is disjoint, contained in $I$, and differs from $I$ by at most some
exceptional set of points—those contained in at most finitely many
$T_{\boldsymbol{v}}[0,1)$, i.e., a subset of

$K=[0,1]\setminus\bigcup_{N\in\mathbb{N}}\bigcap_{n>N}\bigcup_{{\boldsymbol{v}}\in\mathcal{I}^{n}}T_{\boldsymbol{v}}[0,1).$

This $K$, similarly to $K_{n}$ in the proof of Theorem 1, has both
$\mu_{\lambda}$ and Lebesgue measure zero.

To say more, it is necessary to give a partial description for $V_{n}$,
involving the itinerary for $b$.

######  Definition (Itinerary, $\operatorname{It}(x)$,
$\operatorname{It}_{n}(x)$).

This definition has two cases. First suppose that $x\in[0,1]$ is such that

  * •

$x$ is a left endpoint, $T_{\boldsymbol{v}}(0)$, for some ${\boldsymbol{v}}\in
W(\mathcal{I})$; or

  * •

$x$ lies in the exceptional set $K$ above.

Then

$n=\min\left\\{k\in\mathbb{N}:x\notin\bigcup_{{\boldsymbol{v}}\in\mathcal{I}^{k}}T_{\boldsymbol{v}}[0,1)\right\\}$

exists; and we call $\operatorname{It}(x)$, the itinerary of $x$, the unique
word in $\mathcal{I}^{n-1}$ such that

$x\in T_{\operatorname{It}(x)}[0,1).$

and we say $x$ has finite itinerary.

Otherwise, we say that $x$ has infinite itinerary, and the itinerary
$\operatorname{It}(x)$ is the sequence

$\operatorname{It}(x):=(i_{n})_{n}\in\mathcal{I}^{\mathbb{N}}$

such that, for each truncation
$\operatorname{It}_{n}(x):=(i_{1},\ldots,i_{n})\in\mathcal{I}^{n}$, $x\in
T_{\operatorname{It}_{n}(x)}[0,1)$.

Returning to the proof: From a similar argument to that in Theorem 1, if
$\operatorname{It}(b)=(i_{1},i_{2},\ldots,i_{n})\in\mathcal{I}^{n}$ has finite
itinerary, then $V_{k}$ is empty for all $k\geq n+2$, and also for all $k\leq
n$, we have

$\displaystyle I_{k}$
$\displaystyle=\\{(i_{1},i_{2},\ldots,i_{k-1},i)\in\mathcal{I}^{k}\ |\
T_{i_{k}}(0)<T_{i}(0)\\}$ (7)
$\displaystyle\subset\\{\operatorname{It}_{k}(b)\\}\times\mathcal{I}\qquad\text{and
similarly,}$ $\displaystyle I_{n+1}$
$\displaystyle\subset\\{\operatorname{It}(b)\\}\times\mathcal{I}.$

Otherwise, if $\operatorname{It}(b)=(i_{n})_{n=1}^{\infty}$ is infinite, (7)
holds for all $k\in\mathbb{N}$ (it is as if $n=\infty$).

Now let $V=\bigcup_{k\in\mathbb{N}}V_{k}$ and $n\in\mathbb{N}$. It follows
from the nullity of $K$ that we can write the following, and we divide the sum
into two, corresponding to intervals which have or haven’t been split at this
$n$th stage:

$\displaystyle\mu_{x^{n}}(I)-\|I\|$ $\displaystyle=\sum_{{\boldsymbol{v}}\in
V}\mu_{x^{n}}(T_{\boldsymbol{v}}[0,1))-\alpha_{\boldsymbol{v}}$
$\displaystyle=\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\alpha_{{\boldsymbol{v}}}\geq
x^{n}\end{subarray}}\frac{|X_{x^{n}/\alpha_{\boldsymbol{v}}}|-\alpha_{{\boldsymbol{v}}}|X_{x^{n}}|}{|X_{x^{n}}|}\quad-\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in
V\\\ \alpha_{{\boldsymbol{v}}}<x^{n}\end{subarray}}\alpha_{\boldsymbol{v}}.$
(8)

We estimate the second sum first, corresponding to intervals which have not
yet been split up to this value of $n$. Firstly, we have

$0\leq\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\alpha_{{\boldsymbol{v}}}<x^{n}\end{subarray}}\alpha_{\boldsymbol{v}}\leq
x^{n(1-\varepsilon)}\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\alpha_{{\boldsymbol{v}}}<x^{n}\end{subarray}}\alpha_{\boldsymbol{v}}^{1-\varepsilon},$

and the sum on the right hand side can be bounded uniformly in $b$, as
follows. Recall that, in the infinite itinerary case, the inclusion in
equation (7) holds for all $n\in\mathbb{N}$, and we may write

$\displaystyle\sum_{{\boldsymbol{v}}\in
V}\alpha_{\boldsymbol{v}}^{1-\varepsilon}=\sum_{k=1}^{\infty}\sum_{{\boldsymbol{v}}\in
V_{k}}\alpha_{\boldsymbol{v}}^{1-\varepsilon}$
$\displaystyle\leq\sum_{k=1}^{\infty}\alpha_{\operatorname{It}_{n-1}(x)}^{1-\varepsilon}$
$\displaystyle\sum_{i\in\mathcal{I}}\alpha_{i}^{1-\varepsilon}$
$\displaystyle\leq\sum_{n=1}^{\infty}(\alpha_{\ast}^{n})^{1-\varepsilon}$
$\displaystyle\sum_{i\in\mathcal{I}}\alpha_{i}^{1-\varepsilon}\qquad\big{(}\alpha_{\ast}=\max_{i\in\mathcal{I}}\\{\alpha_{i}\\}\big{)}$
$\displaystyle=\frac{(\alpha_{\ast})^{1-\varepsilon}}{1-(\alpha_{\ast})^{1-\varepsilon}}$
$\displaystyle\sum_{i\in\mathcal{I}}\alpha_{i}^{1-\varepsilon}\qquad=:C$

which is finite by assumption. The finite itinerary case is similar and we
obtain the same bound, $C$: the only difference is that sum in $k$ is finite.

Therefore, the second sum of (8) is bounded above by $Cx^{n(1-\varepsilon)}$,
and we may turn our attention to the first.

Consider the term of this first sum corresponding to ${\boldsymbol{v}}\in V$.
Write $\alpha_{\boldsymbol{v}}=x^{m}$ for some $m\in\mathbb{N}$, and consider
a generating series for (the numerator of) the corresponding summand, which
relates to the $g$ from Lemma 6:

$\displaystyle\sum_{n=1}^{\infty}\big{(}|X_{x^{n-m}}|-x^{m}|X_{x^{n}}|\big{)}z^{n}$
$\displaystyle=(z^{m}-x^{m})\left(\frac{g(z)}{z-x}\right)$
$\displaystyle=(z^{m-1}+xz^{m-2}+\cdots+x^{m-1})g(z).$

Recalling $b_{n}$ as the $n$th Taylor coefficient of $g$, equating
coefficients on both sides gives, for all $m\geq n$,

$|X_{x^{n-m}}|-x^{m}|X_{x^{n}}|=b_{n-m+1}+xb_{n-m+2}+\cdots+x^{m-1}b_{n}.$

Thus, by Lemma 6, given $\rho\in(x/R^{\ast},1)$, there is some (possibly
updated) constant $C>0$ such that, for all $n\in\mathbb{N}$,
$b_{n}<C(\rho/x)^{n}$. Applying this to the previous equation gives, for all
$n\geq m$,

$|X_{x^{n-m}}|-x^{m}|X_{x^{n}}|\leq
C\frac{\rho^{n-m-1}+\rho^{n-m-2}+\cdots+\rho^{n}}{x^{n-m+1}}=C\left(\frac{\rho}{x}\right)^{n}\frac{(x/\rho)^{m}-x^{m}}{x(1-\rho)},$

and dividing both sides through by $|X_{x^{n}}|=\mathcal{O}(x^{-n})$ gives

$\left|\frac{|X_{x^{n}/\alpha_{\boldsymbol{v}}}|-\alpha_{{\boldsymbol{v}}}|X_{x^{n}}|}{|X_{x^{n}}|}\right|\leq\hat{C}\rho^{n}\left(\left(\frac{x}{\rho}\right)^{\\!\\!m}-x^{m}\right)<\hat{C}\rho^{n}\left(\alpha_{\boldsymbol{v}}^{1-\varepsilon}-\alpha_{\boldsymbol{v}}\right),$

where we have used $x/\rho<(R^{\ast})^{-1}\leq x^{1-\varepsilon}$ in the last
inequality, for some constant $\hat{C}=\hat{C}(x,\rho)>0$. Summing over
${\boldsymbol{v}}\in V$ bounds the first sum of (8):

$\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\alpha_{{\boldsymbol{v}}}\geq
x^{n}\end{subarray}}\left|\frac{|X_{x^{n}/\alpha_{\boldsymbol{v}}}|-\alpha_{{\boldsymbol{v}}}|X_{x^{n}}|}{|X_{x^{n}}|}\right|\leq\left(\hat{C}\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in
V\\\ \alpha_{{\boldsymbol{v}}}\geq
x^{n}\end{subarray}}\alpha_{\boldsymbol{v}}^{1-\varepsilon}-\alpha_{\boldsymbol{v}}\right)\rho^{n}\leq\hat{C}(C+1)\rho^{n}.$

Since $n\in\mathbb{N}$ was arbitrary, we have the required estimate. ∎

###  4.2 Discrepancy estimates in the higher rank case

When the collection $\\{\alpha_{j}\\}_{j\in\mathcal{I}}$ is not rank one, we
require not only a strict decay property on the $\\{\alpha_{j}\\}$—as in
Theorem 2—, but also a kind of Diophantine condition. To proceed, we need the
following definition.

######  Definition ($R$-badly approximable).

For $R\in[2,\infty)$ we say a number $\gamma\in\mathbb{R}$ is $R$-badly
approximable if there exists a $d>0$ such that

$\forall\,(l,k)\in\mathbb{Z}^{2}\ s.t.\ l\neq
0,\quad\left|\gamma-\frac{k}{l}\right|>\frac{d}{|l|^{R}}.$

######  Remark.

Larger values of $R$ correspond to more easily approximable numbers:

  * •

For any $R=2$, the property is equivalent to $\gamma$ having bounded continued
fraction coefficients. (Such $\gamma$ comprise a set of measure 0 containing
all quadratic algebraic numbers.)

  * •

For $R>2$, the property holds Lebesgue almost-everywhere: by Jarnik’s theorem
[12, Thm. 10.3], the Hausdorff dimension of the complementary set is $2/R<1$.

  * •

Certain transcendental numbers (e.g., Liouville numbers) do not satisfy the
property for any $R$ whatsoever.

######  Theorem 3.

Suppose that $\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ is not rank one, that there
is some $\varepsilon>0$ such that $\sum_{i}\alpha_{i}^{1-\varepsilon}<\infty$,
and that there is a pair
$\alpha_{j},\alpha_{k}\in\\{\alpha_{i}\\}_{i\in\mathcal{I}}$ such that
$\log(\alpha_{j})/\log(\alpha_{k})$ is $(2+r)$-badly approximable, for some
$r\in[0,1/2)$. Then, for all $P\in(0,P^{*})$, there exists a constant $C$ such
that, for all intervals $I\subset[0,1]$,

$\left|\,\mu_{\lambda}(I)-\|I\|\,\right|\leq
C\big{(}-\log(\lambda)\big{)}^{-P};$

where

$P^{*}=\frac{1-2r}{8(1+r)}.$

The proof of Theorem 3 requires us to consider the Mellin transform,

$g(z)=\int_{0}^{\infty}t^{-z-1}|A_{1/t}|\ \mathrm{d}t,$

which has the following explicit form, courtesy of the renewal equation for
$|A_{\lambda}|$. Let $\Re$, $\Im$ denote the real and imaginary parts of a
complex number, respectively.

######  Lemma 7.

For $\Re(z)>1$, the Mellin transform $g(z)$ takes the form

$g(z)=\frac{1}{z(\sum_{j\in\mathcal{I}}{\alpha_{j}}^{\\!z}-1)}.$

In particular, if $\ \sum_{j}{\alpha_{j}}^{\\!1-\varepsilon}<\infty$, $g$ has
a meromorphic extension to the half-plane $\\{\Re(z)>1-\varepsilon\\}$.

###### Proof of Lemma 7.

The formula follows from standard properties of the Mellin transform, namely
$g(\alpha_{j}z)=\alpha_{j}^{z}g(z)$, and the renewal equation of Lemma 3. ∎

As is well-known, one can obtain asymptotic information about a function from
the distribution of poles of its Mellin transform.

In particular, this depends on the zeros of the almost-periodic function

$f(z)=\sum_{j\in\mathcal{I}}{\alpha_{j}}^{\\!z}-1.$

There is a lot we can say straight away. From our assumptions on
$\\{\alpha_{j}\\}_{j}$, we have that $z=1$ is a simple zero of $f$, and by the
triangle inequality, there are no zeros of $f$ for $\\{\Re(z)>1\\}$. Moreover,
if there were another zero of $f$ on the line $\\{\Re(z)=1\\}$, it would
follow that $\\{\alpha_{j}\\}_{j}$ is rank one, a contradiction.

The role of the poles of the Mellin transform is illustrated in the proof of
the following result.

######  Proposition 1.

For any given collection of positive numbers
$\\{\alpha_{j}\\}_{j\in\mathcal{I}}$ which sum to 1 such that
$H=-\sum_{j}\alpha_{j}\log(\alpha_{j})<\infty$, there is no $\varepsilon>0$
for which

$|A_{\lambda}|=\frac{1}{H\lambda}+\mathcal{O}(\lambda^{1-\varepsilon})$ (9)

as $\lambda\to 0^{+}$.

###### Proof of Proposition 1.

Fix a collection $\\{\alpha_{j}\\}_{j\in\mathcal{I}}$ as above and assume for
contradiction that there is an $\varepsilon>0$ for which (9) holds. Taking the
Mellin transform of this equation yields that

$\frac{1}{zf(z)}=\frac{1}{H(z-1)}+\int_{1}^{\infty}t^{-z-\varepsilon}\mathcal{O}(1)\
\mathrm{d}t.$

Since this second integral converges absolutely for all $z$ with
$\Re(z)>1-\varepsilon$, we see that the left hand side has a meromorphic
extension to the half plane $\\{z\in\mathbb{C}\;:\;\Re(z)>1-\varepsilon\\}$,
with only one pole at $z=1$. To obtain a contradiction, we provide a sequence
of zeros $z_{n}=u_{n}+iv_{n}$ with $u_{n}\to 1$, $v_{n}\to\infty$, using the
theory of almost-periodic functions. In particular, we follow the proof of the
corollary to [7, Theorem 3.6].

It can quickly be seen that $f$ is almost-periodic, by [7, Cor. to Thm. 3.12],
and is bounded on $\\{\Re(z)\geq 1-\varepsilon/2\\}$ since, in this half-
plane,

$|f(z)|\leq 1+\sum_{i\in\mathcal{I}}\alpha^{1-\,\varepsilon/2}.$

Also, since $f(1)=0$, the definition of almost-periodicity provides a sequence
of positive numbers $(y_{n})_{n=1}^{\infty}$ for which $f(1+iy_{n})\to 0$ as
$n\to\infty$. In other words, the holomorphic functions

$f_{n}(z)=f(z+iy_{n})$

are bounded on the same half-plane, and $f_{n}(1)\to 0$.

Furthermore, fixing any index $j\in\mathcal{I}$, for
$L:=-2\pi/\log(\alpha_{j})$, we see that $\sup_{|v|\leq L}|f_{n}(1+iv)|$ is
bounded away from zero uniformly, since every interval of length $L$ contains
a $v$ such that

$\alpha_{j}^{1+iv}=-\alpha_{j}\quad\therefore\quad\left|f\left(1+iv\right)\right|\geq
1+\alpha_{j}-\sum_{k\in\mathcal{I}\setminus\\{j\\}}\alpha_{k}=2\alpha_{j}.$

Therefore, on the rectangle $(1-\varepsilon,1+\varepsilon)+i(-l,l)$, an
application of Montel’s theorem shows that $f_{n}$ uniformly converges
(passing to a subsequence if necessary) to some analytic function
$f_{\infty}$. From the last two considerations, $f_{\infty}(1)=0$ and
$f_{\infty}$ is not identically zero.

Now, taking a circle about 1 small enough that $f_{\infty}$ has no zeros on
it, by Hurwitz’s theorem, for all $n$ sufficiently large, $f_{n}$ has a zero
$\hat{z}_{n}$ inside this circle, such that $\hat{z}_{n}\to 1$ as
$n\to\infty$.

This thus provides us with a sequence of zeros of $f$ accumulating on the line
as required, contradicting the statement that $f$ has only one zero in the
above-mentioned half-plane. ∎

Considering now the proof of Theorem 3, the following lemma uses the
$(2+r)$-badly approximable hypothesis, following [8]. For simplicity in the
following two proofs, we write $\alpha=\max(\alpha_{j},\alpha_{k})$ and
$\beta=\min(\alpha_{j},\alpha_{k})$.

######  Lemma 8.

Suppose that $(\alpha_{j})_{j\in\mathcal{I}}$ satisfies the conditions of
Theorem 3. Then there exists $C>0$ such that, whenever
$z=1-u+iv\in\mathbb{C}\setminus\\{1\\}$ satisfies both $f(z)=0$ and
$u<\varepsilon$, then $u>0$ and

$|v|^{2+2r}\geq\frac{C}{u}.$

###### Proof of Lemma 8.

The fact that $u>0$ follows from the discussion preceding the previous
proposition. We first show, if $f(z)=0$, the argument of $\alpha^{z}$ in
$(-\pi,\pi]$ is $\mathcal{O}(\sqrt{u})$ as $u\to 0^{+}$. That is, the quantity
$\eta_{\alpha}\in(-\pi,\pi]$, satisfying

$e^{i\eta_{\alpha}}=\frac{\alpha^{z}}{|\alpha^{z}|}=\frac{\alpha^{z}}{\alpha^{1-u}},$

is $\mathcal{O}(\sqrt{u})$. This uses the triangle inequality and a small
amount of trigonometry, as we now detail. We have that

$|\alpha^{z}-1|\leq 1-\alpha+H(u),$

where

$H(u):=\sum_{n\in\mathcal{I}}\alpha_{n}^{1-u}-\alpha^{1-u}-1+\alpha.$

In particular, $H(u)=\mathcal{O}(u)$ as $u\to 0^{+}$, by the mean value
theorem. Therefore, for $u$ sufficiently small, $H(u)<\alpha$, which gives
rise to the picture in Figure 4(i). Consequently, $|\eta_{\alpha}|<\theta$,
where $\theta$ is as in 4(ii) and satisfies the following equation.

$\sum_{i}\alpha_{i}^{1-u}$$H(u)+1-\alpha$$\alpha^{1-u}$$0$$1$

$1$$H(u)+1-\alpha$$\alpha^{1-u}$$\theta$

Figure 4: (i) The region in which $\alpha^{z}$ must lie for $f(z)=0$—the bold
arc in the shaded circle; (ii) the triangle defining $\theta(u)$, the maximum
possible value of $|\eta_{\alpha}|$.

$\cos(\theta)=\frac{1+\alpha^{2-2u}-(1-\alpha+H(u))^{2}}{2\alpha^{1-u}}=1-\mathcal{O}(u)\quad(u\to
0),$

where the constant now depends on the value of $\alpha$. Using, for example,
that

$\lim_{y\to
0^{+}}\frac{\arccos(1-y)}{\sqrt{y}}=\sqrt{2},\qquad\arccos:[-1,1]\to[0,\pi],$

it is clear that $\theta=\mathcal{O}(\sqrt{u})$ as $u\to 0^{+}$, hence the
same applies to $\eta_{\alpha}$.

We can repeat this argument with $\beta$ in place of $\alpha$ to bound the
analogously defined $\eta_{\beta}$—i.e., $\eta_{\beta}=\mathcal{O}(\sqrt{u})$.

Write $v\log(\alpha)=2\pi k+\eta_{\alpha}$ and $v\log(\beta)=2\pi
l+\eta_{\beta}$, supposing $|v|\geq 2\pi/\log(\beta)$ so that $k$ and $l$ are
non-zero. Substituting into the definition of $(2+r)$-badly approximable gives

$\frac{d}{|l|^{2+r}}\leq\left|\frac{\log(\alpha)}{\log(\beta)}-\frac{k}{l}\right|=\left|\frac{2\pi
k+\eta_{\alpha}}{2\pi
l+\eta_{\beta}}-\frac{k}{l}\right|=\left|\frac{\eta_{\alpha}}{2\pi
l+\eta_{\beta}}-\eta_{\beta}\frac{2\pi k+\eta_{\alpha}}{(2\pi
l+\lambda)^{2}}\right|,$

where $\lambda\in\mathbb{R}$ is a constant, provided by the mean value
theorem, satisfying $0<|\lambda|<|\eta_{\beta}|\leq\pi$. Using the triangle
inequality on the right hand side, multiplying through by $(2\pi
l+\lambda)^{2}\,|l|^{r}$ and using that $|\eta_{\alpha}|\leq\pi$, one obtains

$\displaystyle\pi^{2}d\leq 4\pi^{2}\left(1-\frac{\lambda}{l}\right)^{2}d$
$\displaystyle\leq 2\pi\left(|\eta_{\alpha}|\frac{\left(1-\lambda/2\pi
l\right)^{2}}{|1+\eta_{\beta}/2\pi
l|}+|\eta_{\beta}|\left|\frac{k}{l}-\frac{\eta_{\alpha}}{2\pi}\right|\right)|l|^{1+r}$
$\displaystyle\leq
2\pi\left(9|\eta_{\alpha}|+|\eta_{\beta}|\left(\left|\frac{k}{l}\right|+\frac{1}{2}\right)\right)|l|^{1+r}$
$\displaystyle\leq
2\pi\left(9|\eta_{\alpha}|+|\eta_{\beta}|\left(\frac{3}{2}+2\frac{\log(\alpha)}{\log(\beta)}\right)\right)|l|^{1+r},$

where the last inequality uses that $|v|>-2\pi/\log(\beta)$. We can divide
through by the large bracket on the right hand side and, recalling the
$\sqrt{u}$ asymptotic for $\eta_{\alpha}$ and $\eta_{\beta}$, obtain the
required inequality for some constant $C$, for $u$ sufficiently small and
$|v|$ sufficiently large.

That the inequality holds in the whole of the specified region (with a
possibly different $C$) follows simply from the fact that zeros of $f$ can
only accumulate on the vertical boundary $\\{z=1-\varepsilon+iv:v\neq 0\\}$,
and so there is an open neighbourhood of $[1-\varepsilon,1]$ containing only
one zero of $f$, at 1. Since there are finitely many zeros of $f$ to cater for
(at most), we can adapt $C$ accordingly. ∎

The next lemma is a variant on the last and allows us to estimate decay of the
Mellin inverse integral inside the zero-free region.

######  Lemma 9.

Suppose $(\alpha_{j})_{j\in\mathcal{I}}$ is a collection of positive numbers
as given in Theorem 3. Then there exists $C>0$ such that, whenever
$z=1-u+iv\in\mathbb{C}$ with $u\geq 0$ and $\sigma>0$ sufficiently small,

$\left|f(z)\right|<\sigma$ (10)

implies one of the following holds: either

$|v|\leq 2\pi/\log(\beta)$

or

$|v|^{2+2r}>\frac{C}{\max(u,\sigma)}.$

###### Proof of Lemma 9.

The proof is an adaptation of that for Lemma 8. This time, the radius of the
circle depicted in Figure 4 is $H(u)+1-\alpha+\sigma$ and correspondingly,

$\cos(\theta)=\frac{1}{2}\frac{1+\alpha^{2-2u}-(1-\alpha+H(u)+\sigma)^{2}}{\alpha^{1-u}}=1-\mathcal{O}(\max(u,\sigma))$

as $\max(u,\sigma)\to 0$, which gives, for $\max(u,\sigma)$ is sufficiently
small),

$|\theta|\leq\frac{\pi}{2}\sqrt{1-\cos(\theta)}=\mathcal{O}(\sqrt{\max(u,\sigma)})$

and the proof continues as before. ∎

The next crucial lemma is the analogue to Lemma 6 in the higher rank case.

######  Lemma 10.

Under the assumptions of Theorem 3,

$|A_{\lambda}|=\frac{1}{H\lambda}+\mathcal{O}\big{(}\lambda^{-1}(-\log(\lambda))^{-P}\big{)}\qquad\lambda\in(0,1],$

where $P\in(0,P^{*})$ is as given in Theorem 3.

###### Proof of Lemma 10.

The proof uses simple complex analysis to estimate the integral

$F(t):=\frac{1}{2\pi
i}\int_{2-i\infty}^{2+i\infty}\frac{t^{z+3}}{z(z+1)(z+2)(z+3)f(z)}\mathrm{d}z,\hbox{
for }t>1.$ (11)

We first relate $F(t)$ to $|A_{1/t}|$. On the line $\\{\Re(z)=2\\}$, we see
that $f$ is uniformly bounded away from zero,

$|f(z)|\geq 1-\sum_{j\in\mathcal{I}}\alpha_{j}^{2}>0,$

so $F(t)$ absolutely converges, for all $t$. Therefore, by the Mellin
inversion theorem, the Mellin transform of $t\mapsto F(t)/t^{3}$ is the
denominator of the integrand of $F$:

$F^{\ast}(z):=\int_{0}^{\infty}t^{-z-1}F(t)\
\mathrm{d}t=\frac{1}{z(z+1)(z+2)(z+3)f(z)}.$

Therefore, using integration by parts, one has $F^{(3)}(t)=|A_{1/t}|$ Lebesgue
almost-everywhere.

We now relate the integral in (11) to that over the contour $\Gamma$,
parametrised by

$\gamma:\mathbb{R}\to\mathbb{C},\qquad\gamma(v)=1+iv-D\min(1,|v|^{-2-r})$

(see Figure 5), where $D>0$ is chosen sufficiently small so that the previous
two lemmas apply as follows: firstly, the only zero of $f$ which lies on or to
the right of $\Gamma$ is at $1$, and secondly, whenever $z$ lies on or to the
right of $\Gamma$ and $|\Im(z)|\geq-2\pi(\log(\beta))^{-1}$, one has

$|f(z)|\geq D|\Im(z)|^{-2-2r}.$ (12)

Consider, for $T\geq 1$, the contour $\Gamma_{T}$ depicted in Figure 5.

$\gamma(-T)$$\gamma(T)$$2+iT$$2-iT$$\times$$1$$\Gamma_{T}\ $$U_{T}\ $$L_{T}\ $
Figure 5: The contour $\Gamma_{t}$ used in the proof of Lemma 10.

Cauchy’s residue theorem gives

$\int_{2-iT}^{2+iT}F^{\ast}(z)\;\mathrm{d}z={2\pi
i}\frac{t^{4}}{24H}+\int_{\Gamma_{T}}F^{\ast}(z)\,\mathrm{d}z+\int_{U_{T}}F^{\ast}(z)\,\mathrm{d}z+\int_{L_{T}}F^{\ast}(z)\,\mathrm{d}z.$

Since $U_{T}$ and $L_{T}$ have bounded length, a simple application of
$\eqref{eq - vertical decay of f z}$ shows that the corresponding last two
integrals are $\mathcal{O}(|T|^{-2+2r})$ as $T\to\infty$; therefore, taking
the limit, one has

$F(t)=\frac{t^{4}}{24H}+\frac{1}{2\pi
i}\int_{\Gamma}F^{\ast}(z)t^{-z-3}\;\mathrm{d}z.$ (13)

From this point, the proof follows along the lines of [10, Theorem 4.6,
pp.133–4]. Since $t\mapsto|A_{1/t}|$ is non-decreasing on the real line, so
too are the functions $F$, $F^{\prime}$ and $F^{\prime\prime}$. Using this,
together with repeated applications of the mean value theorem, gives that, for
any $t\in\mathbb{R}$ and $h>0$, both

$\displaystyle\frac{F(t-3h)-3F(t-2h)+3F(t-h)-F(t)}{-h^{3}}\leq|A_{1/t}|$ and
$\displaystyle|A_{1/t}|\leq\frac{F(t+3h)-3F(t+2h)+3F(t+h)-F(t)}{h^{3}}$ hold.

Substituting (13) into these expressions yields

$\displaystyle\frac{F(t\pm 3h)-3F(t\pm 2h)+3F(t\pm h)-F(t)}{\pm
h^{3}}=\qquad\qquad\qquad$ $\displaystyle t\pm\frac{3}{2}h+\frac{1}{2\pi
i}\int_{\Gamma}\frac{(t\pm 3h)^{z+3}-3(t\pm 2h)^{z+3}+3(t\pm
h)^{z+3}-t^{z+3}}{\pm h^{3}}$ $\displaystyle F^{\ast}(z)\mathrm{d}z.$

Thus, we have the estimate

$\displaystyle|A_{1/t}|$ $\displaystyle=\;t+\mathcal{O}(h)\,+$
$\displaystyle\;\mathcal{O}$
$\displaystyle\left(\int_{\Gamma}\left|\frac{(t\pm 3h)^{z+3}-3(t\pm
2h)^{z+3}+3(t\pm h)^{z+3}-t^{z+3}}{\pm
h^{3}(z+1)(z+2)(z+3)}\right|\left|\frac{1}{zf(z)}\right|\;|\mathrm{d}z|\right).$

From now on, let $h=h(t)\in(0,t)$ be a function of $t$ to be determined later.
To begin to estimate the integral, consider $|\Delta_{\pm}(t,h,z)|$ for $t>1$
and $z\in\Gamma$, where

$\Delta_{\pm}(t,h,z):=\frac{(t\pm 3h)^{z}-3(t\pm 2h)^{z}+3(t\pm
h)^{z}-t^{z}}{\pm h^{3}(z+1)(z+2)(z+3)}.$

We estimate $|\Delta_{\pm}|$ in two different ways. For the first, we express
$|\Delta_{\pm}|$ as a series of nested integrals:

$\displaystyle\left|\Delta_{\pm}(t,h,z)\right|=\left|\frac{1}{\pm
h}\int_{t}^{t\pm h}\frac{1}{\pm h}\int_{\hat{t}}^{\hat{t}\pm h}\frac{1}{\pm
h}\int_{\hat{\vphantom{\rule{1.0pt}{4.81111pt}}\smash{\hat{t}}}}^{\hat{\vphantom{\rule{1.0pt}{4.81111pt}}\smash{\hat{t}}}\pm
h}\hat{\vphantom{\rule{1.0pt}{5.93056pt}}\smash{\hat{\vphantom{\rule{1.0pt}{5.93056pt}}\smash{\hat{t}}}}}^{z}\
\mathrm{d}\hat{\vphantom{\rule{1.0pt}{5.93056pt}}\smash{\hat{\vphantom{\rule{1.0pt}{5.93056pt}}\smash{\hat{t}}}}}\
\mathrm{d}\hat{\vphantom{\rule{1.0pt}{5.93056pt}}\smash{\hat{t}}}\
\mathrm{d}\hat{t}\right|$ $\displaystyle\leq(t+3h)^{\Re(z)}$
$\displaystyle\leq 4t^{\Re(z)}.$

For the first inequality, we have taken the absolute value signs inside the
integral and applied the mean value theorem three times, noting that
$t\mapsto|t^{z}|=t^{\Re(z)}$ is increasing on $[0,\infty)$, since $\Re(z)>0$
for $z\in\Gamma$. (The second follows simply from $h<t$ and $\Re(z)<1$.)

The triangle inequality gives us another estimate: for $t\geq 1$,

$\displaystyle\left|\Delta_{\pm}(t,h,z)\right|$
$\displaystyle\leq\frac{(4t)^{Re(z)+3}+3(3t)^{Re(z)+3}+3(2t)^{Re(z)}+t^{Re(z)+3}}{h^{3}|z+1||z+2||z+3|}$
$\displaystyle\leq\frac{548t^{\Re(z)+3}h^{-3}}{|z+1||z+2||z+3|}.$

From the Bernoulli inequality it follows that, for $z=\gamma(v)\in\Gamma$, the
three quantities $|\gamma(v)+1|,|\gamma(v)+2|,|\gamma(v)+3|$ are all greater
than or equal to $(1+|v|)/2$, so altogether we have the following.

$|\Delta_{\pm}\big{(}t,h,\gamma(v)\big{)}|\leq\min\left(4t^{\Re(\gamma(v))},\frac{4384\,t^{\Re(\gamma(v))+3}}{h^{3}\,(1+|v|)^{3}}\right).$

From (12), one can easily deduce that
$\big{|}\gamma(v)f\big{(}\gamma(v)\big{)}\big{|}^{-1}=\mathcal{O}((1+|v|)^{1+2r})$,
for all $v\in\mathbb{R}$. Combining the previous three inequalities and using
the boundedness of $|\gamma^{\prime}(v)|$ gives the following.

$|A_{1/t}|=\frac{t}{H}+\mathcal{O}(h)+\mathcal{O}\left(\int_{-\infty}^{\infty}(1+|v|)^{1+2r}\min\left(t^{\Re(\gamma(v))},\frac{t^{\Re(\gamma(v))+3}}{(1+|v|)^{3}}\right)\mathrm{d}v\right).$

Because the integral is symmetric in $v$, it suffices to estimate the integral
from 0 to $\infty$, as we now do. Writing $\Re(\gamma(v))=1-\kappa(v)$, where
$\kappa(v)=D\min(1,|v|^{-2-2r})$, the previous equation simplifies to the
following.

$\displaystyle\frac{|A_{1/t}|}{t}-\frac{1}{H}$
$\displaystyle=\mathcal{O}\left(\frac{h}{t}\right)+\mathcal{O}\left(\int_{0}^{\infty}(1+v)^{1+2r}t^{-\kappa(v)}\min\left(1,\frac{(t/h)^{3}}{(1+v)^{3}}\right)\mathrm{d}v\right)$
$\displaystyle=\mathcal{O}\left(\frac{h}{t}\right)+\mathcal{O}\left(\int_{0}^{\infty}(1+v)^{-2+2r}t^{-\kappa(v)}\min\left((1+v)^{3},\left(\frac{t}{h}\right)^{\\!\\!3}\right)\mathrm{d}v\right)$
$\displaystyle=\mathcal{O}\left(\frac{h}{t}\right)+\mathcal{O}\left(\int_{1}^{\infty}v^{-2+2r}t^{-\kappa(v-1)}\min\left(v^{3},\left(\frac{t}{h}\right)^{\\!\\!3}\right)\mathrm{d}v\right).$

Now let $\delta\in(0,1-2r)$. For $v,t\geq 1$, we have, since $\kappa$ is
decreasing on $[0,\infty)$,

$\displaystyle v^{-2+2r}t^{-\kappa(v-1)}$ $\displaystyle\leq
v^{-2+2r}t^{-\kappa(v)}$ $\displaystyle=v^{-2+2r}\exp(-\kappa(v)\log(t))$
$\displaystyle=v^{-2+2r+\delta}\exp(-\kappa(v)\log(t)-\delta\log(v))$
$\displaystyle=v^{-2+2r+\delta}\exp\left(-Dv^{-2-2r}\log(t)-\delta\log(v))\right)$
$\displaystyle=v^{-2+2r+\delta}\exp(-\xi_{\delta}(t)),$

where

$\displaystyle\xi_{\delta}(t)$ $\displaystyle:=\inf_{v\geq
1}\left(Dv^{-2-2r}\log(t)+\delta\log(v)\right)$
$\displaystyle=\frac{\delta}{2+2r}\left(1+\log\left(\frac{D(2+2r)\log(t)}{\delta}\right)\right).$

This last equality holds for all $t$ sufficiently large, by elementary
calculus. Hence

$\frac{|A_{1/t}|}{t}-\frac{1}{H}=\mathcal{O}\left(\frac{h}{t}\right)+\mathcal{O}\left(e^{-\xi_{\delta}(t)}\int_{1}^{\infty}v^{-2+2r+\delta}\min\left(v^{3},\left(\frac{t}{h}\right)^{3}\right)\mathrm{d}v\right).$

Now, writing $\omega=vh/t$ and substituting, the integral becomes

$\left(\frac{t}{h}\right)^{2+2r+\delta}\int_{h/t}^{\infty}\omega^{-2+2r+\delta}\min(\omega^{3},1)\;\mathrm{d}\omega,$

and this can be split into two parts,

$\int_{h/t}^{1}\omega^{1+2r+\delta}\;\mathrm{d}\omega+\int_{1}^{\infty}\omega^{-2+2r+\delta}\;\mathrm{d}\omega,$

both of which are finite, since $2r+\delta\in(0,1)$. Therefore, for all $t\geq
1$,

$\frac{|A_{1/t}|}{t}-\frac{1}{H}=\mathcal{O}\left(\frac{h}{t}\right)+\mathcal{O}\left(e^{-\xi_{\delta}(t)}\left(\frac{t}{h}\right)^{2+2r+\delta}\right).$

Finally, choosing $h(t)=t\exp(\frac{-\xi_{\delta}(t)}{3+2r+\delta})$ ensures
both terms have the same order of magnitude, and the previous equation
simplifies to the required expression:

$|A_{1/t}|=\frac{t}{H}+\mathcal{O}\left(t\log(t)^{-P}\right),$

where

$P=P(r,\delta)=\frac{\delta}{(2+2r)(3+2r+\delta)}\in\left(0,\frac{1-2r}{8(1+r)}\right).\qquad\qed$

The concluding stages of the proof of Theorem 3 are similar to those of
Theorem 2; but with some notable differences.

###### Proof of Theorem 3.

For simplicity of writing, we again consider only the case that none of the
$T_{i}$ fix 0. Let $\lambda\in(0,1)$ and recall $I=[b,1)$, $V_{k}$ and $V$
from the proof of Theorem 2 (p.6 onwards).

Similarly to that proof, we may write the discrepancy in terms of three sums,

$\displaystyle\mu_{\lambda}(I)-\|I\|$
$\displaystyle=\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\hphantom{\lambda\leq\alpha_{{\boldsymbol{v}}}<\lambda/\alpha_{\max}}\end{subarray}}\mu_{\lambda}(T_{\boldsymbol{v}}[0,1))-\alpha_{\boldsymbol{v}}$
$\displaystyle=\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\alpha_{\boldsymbol{v}}\geq\lambda/\alpha_{\max}\\\
\hphantom{\lambda\leq\alpha_{{\boldsymbol{v}}}<\lambda/\alpha_{\max}}\end{subarray}}\frac{|X_{\lambda/\alpha_{\boldsymbol{v}}}|}{|X_{\lambda}|}-\alpha_{\boldsymbol{v}}$
$\displaystyle+\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in V\\\
\lambda\leq\alpha_{{\boldsymbol{v}}}<\lambda/\alpha_{\max}\end{subarray}}\frac{|X_{\lambda/\alpha_{\boldsymbol{v}}}|}{|X_{\lambda}|}\quad-\sum_{\begin{subarray}{c}{\boldsymbol{v}}\in
V\\\
\alpha_{{\boldsymbol{v}}}<\lambda/\alpha_{\max}\end{subarray}}\alpha_{\boldsymbol{v}},$
(14)

where $\alpha_{\max}=\max_{i\in\mathcal{I}}(\alpha_{i})$.

The second and third sum of (14) decay much faster than the first, which can
be deduced from the summability of $\alpha_{\boldsymbol{v}}^{1-\varepsilon}$
alone. For the third sum, the argument from Theorem 2 (p.4.1) applies to bound
it by a multiple of $\lambda^{1-\varepsilon}$. The second sum of (14)
corresponds to newly split intervals: if
$\alpha_{\boldsymbol{v}}<\lambda/\alpha_{\max}$, then
$\alpha_{\boldsymbol{v}}\alpha_{i}<\lambda$ for any $i\in\mathcal{I}$, so no
proper subinterval of $T_{\boldsymbol{v}}[0,1)$ has been split for this value
of $\lambda$, and $|X_{\lambda/\alpha_{\boldsymbol{v}}}|=1$. Therefore,
assuming $b$ has an infinite itinerary,

$\displaystyle\sum_{\begin{subarray}{c}v\in V\\\
\lambda\leq\alpha_{\boldsymbol{v}}<\lambda/\alpha_{\max}\end{subarray}}{|X_{\lambda/\alpha_{\boldsymbol{v}}}|}$
$\displaystyle=\phantom{\sum_{n\in\mathbb{N}}}\big{|}\\{{\boldsymbol{v}}\in
V:\lambda\leq\alpha_{\boldsymbol{v}}<\lambda/\alpha_{\max}\\}\big{|}$
$\displaystyle=\sum_{n\in\mathbb{N}}\big{|}\\{{\boldsymbol{v}}\in
V_{n}:\lambda\leq\alpha_{\boldsymbol{v}}<\lambda/\alpha_{\max}\\}\big{|}$
$\displaystyle\leq\sum_{n\in\mathbb{N}}\big{|}\\{i\in\mathcal{I}:\lambda\leq\alpha_{\operatorname{It}_{n-1}(b)}\alpha_{i}<\lambda/\alpha_{\max}\\}\big{|}$
$\displaystyle=\sum_{n\in\mathbb{N}}\big{|}\\{i\in\mathcal{I}:\lambda/\alpha_{\operatorname{It}_{n-1}(b)}\leq\alpha_{i}<\lambda/(\alpha_{\max}\alpha_{\operatorname{It}_{n-1}(b)})\\}\big{|}$
$\displaystyle\leq\sum_{n\in\mathbb{N}}\big{|}\\{i\in\mathcal{I}:\lambda/\alpha_{\operatorname{It}_{n-1}(b)}\leq\alpha_{i}<\lambda/\alpha_{\operatorname{It}_{n}(b)}\\}\big{|}$
$\displaystyle=\phantom{\sum_{n\in\mathbb{N}}}\big{|}\\{i\in\mathcal{I}:\lambda\leq\alpha_{i}\\}\big{|}$
$\displaystyle\leq\sum_{i\in\mathcal{I}}\alpha_{i}^{1-\varepsilon}\;\lambda^{\varepsilon-1}.$

Thus, the second sum of (14) is bounded by a multiple of
$\lambda^{\varepsilon}$. The finite itinerary case is similar, involving a
finite sum in $n$.

It remains to bound the first sum of (14), using the asymptotics for
$|A_{\lambda/\alpha_{\boldsymbol{v}}}|$ provided by the previous lemma. One
finds that there exists $C,C^{\prime}$ such that, for all ${\boldsymbol{v}}\in
V$ with $\alpha_{\boldsymbol{v}}\geq\lambda/\alpha_{\max}$,

$\left|\frac{|X_{\lambda/\alpha_{\boldsymbol{v}}}|}{|X_{\lambda}|}-\alpha_{\boldsymbol{v}}\right|\leq
C\alpha_{\boldsymbol{v}}\left((-\log(\lambda/\alpha_{\boldsymbol{v}}))^{-P}\right)\leq
C^{\prime}\alpha_{\boldsymbol{v}}\left((-\log(\lambda))^{-P}\right),$

the last inequality following from the fact that
$x\mapsto\log(\lambda)/\log(\lambda/x)$ is uniformly bounded on
$[\alpha_{\max},\infty)$. Summing over ${\boldsymbol{v}}$ gives the required
estimate. ∎

## References

  * [1] Adler, R. L., Flatto, L. (1977). Uniform distribution of Kakutani’s interval splitting procedure. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 38, no. 4, 253–259.
  * [2] Aistleitner, C., Hofer, M. (2013). Uniform distribution of generalized Kakutani’s sequences of partitions. Ann. Mat. Pura Appl. (4) 192, no. 4, 529–538.
  * [3] Aistleitner, C., Hofer, M., Ziegler, V. (2014). On the uniform distribution modulo 1 of multidimensional LS-sequences. Ann. Mat. Pura Appl. (4) 193, no. 5, 1329–1344.
  * [4] Blackwell, D. (1948). A renewal theorem. Duke Math. J. 15, 145–150.
  * [5] Carbone, I. (2012). Discrepancy of LS-sequences of partitions and points. Ann. Mat. Pura Appl. (4) 191, no. 4, 819–844.
  * [6] Carbone, I., Iacò, M. R., Volčič, A. (2014). A dynamical system approach to the Kakutani-Fibonacci sequence. Ergodic Theory Dynam. Systems  34, no. 6, 1794–1806.
  * [7] Corduneanu, C. (1961). Almost Periodic Functions. Interscience Tracts in Pure and App. Math. 22. Wiley Interscience: London.
  * [8] Drmota, M., Infusino, M. (2012). On the discrepancy of some generalized Kakutani’s sequences of partitions. Unif. Distrib. Theory 7, no. 1, 75–104.
  * [9] Drmota, M., Tichy, R. (1997). Sequences, Discrepancies and Applications. Lecture notes in math. 1651. Springer: Berlin.
  * [10] Ellison, F., Ellison, W. (1985). Prime Numbers. Wiley Interscience: London.
  * [11] Erdős, P., Feller, W., Pollard, H. (1949). A property of power series with positive coefficients. Bull. Amer. Math. Soc. 55, 201–204.
  * [12] Falconer, K. (2014). Fractal geometry: Mathematical foundations and applications. Third edition. John Wiley & Sons, Ltd.: Chichester.
  * [13] Hardy, G. H., Littlewood, J. E. (1914) Some problems of diophantine approximation II. Acta Math. 37, no. 1, 193–239.
  * [14] Hofer, M. Iacò, M. R., Tichy, R. (2015). Ergodic properties of $\beta$-adic Halton sequences. Ergodic Theory Dynam. Systems 35, no. 3, 895–909.
  * [15] Iacò, M. R., Ziegler, V. (2017). Discrepancy of generalized LS-sequences. Unif. Distrib. Theory 12, no. 2, 37–63.
  * [16] Kakutani, S. (1976). A problem of equidistribution on the unit interval $[0,1]$. Measure theory (Proc. Conf., Oberwolfach, 1975). Lecture Notes in Math. 541. Springer: Berlin. 369–375.
  * [17] Smilansky, Y. (2020). Uniform Distribution of Kakutani Partitions Generated By Substitution Schemes, Israel J. Math., 240, 667–710
  * [18] Volčič, A. (2011) A generalization of Kakutani’s splitting procedure. Ann. Mat. Pura Appl. (4) 190, no. 1, 45–54.
  * [19] Weiss, C. (2018). On the classification of LS-sequences. Unif. Distrib. Theory 13, no. 2, 83–92.
  * [20] Weyl, H. (1916). Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann. 77, no. 3, 313–352.