# On the invariance of the Kolmogorov complexity of $\beta$-expansions

Valentin Abadie  Helmut Boelcskei

Measuring the complexity of real numbers is of major importance in computer
science, for the purpose of knowing which computations are allowed. Consider a
non-computable real number $s$, i.e. a real number which cannot be stored on a
computer. We can store only an approximation of $x$, for instance by
considering a finite bitstring representing a finite prefix of its binary
expansion. For a fixed approximation error $\epsilon>0$, the size of this
finite bitstring is dependent on the algorithmic complexity of the finite
prefixes of the binary expansion of $s$. The algorithmic complexity of a
binary sequence $x$, often referred to as Kolmogorov complexity, is the length
of the smallest binary sequence $x^{\prime}$, for which there exists an
algorithm, such that when presented with $x^{\prime}$ as input, it outputs
$x$. The algorithmic complexity of the binary expansion of real numbers is
widely studied, but the algorithmic complexity of other ways of representing
real numbers remains poorly reported. However, knowing the algorithmic
complexity of different representations may allow to define new and more
efficient strategies to represent real numbers. To our knowledge, [17] is the
only paper to make a step in this direction: it establishes an equivalence
between the algorithmic complexity of the $q$-ary expansions, with
$q\in\mathbf{N}$, $q\geq 2$, i.e. representations of real numbers in any
integer base. In this paper, we study the algorithmic complexity of the so-
called $\beta$-expansions, which are representations of real numbers in a base
$\beta\in(1,2)$. $\beta$-expansions display very interesting properties, one
of which being redundancy: a given real number $s$ and a fixed
$\beta\in(1,2)$, there can be infinitely many different $\beta$-expansions of
$s$. In [9], this redundancy is used to design robust A/D converters. However,
nothing is known about the algorithmic complexity of the generated sequences,
and they may potentially be way more complex than the binary expansion,
displaying a robutness-complexity trade-off. In this paper, we show that for a
given real number $s$, the binary expansion is a minimizer of algorithmic
complexity, and that for every given $\beta\in(1,2)$, there exists a
$\beta$-expansion of $s$ which achieves the lower bound of algorithmic
complexity displayed by the binary expansion of $s$.

## Notations

$\mathbf{N}$ denotes the set of natural numbers,
$\mathbf{N}_{0}:=\mathbf{N}\cup\\{0\\}$, and
$\mathbf{N}_{2}:=\mathbf{N}\backslash\\{1\\}$. $\mathbf{Q}$ stands for the set
of rational numbers, $\mathbf{R}$ the set of real numbers, $\mathbf{R}_{+}$
the set of nonnegative real numbers, and $\mathbf{C}$ denotes the set of
computable numbers [5, Section 10]. Let $n\in\mathbf{N}$. We let
$\left\llbracket n\right\rrbracket:=\\{1,\ldots,n\\}$. For a set $A$,
$\\#\left(A\right)$ denotes its cardinality. If $\\#\left(A\right)=\infty$, we
may write $\\#\left(A\right)=\aleph_{0}$ if $A$ is countable, and
$\\#\left(A\right)=2^{\aleph_{0}}$ if $A$ is uncountable. Given a set $A$,
$A^{\omega}$ denotes the set of infinite sequences with elements in $A$. Let
$f:X\to X$ be a map from a set $X$ into itself. Then, $f^{0}$ denotes the maps
identity map of $X$, and $f^{1}:=f$, and $f^{n+1}:=f\circ f^{n}$, for
$n\in\mathbf{N}$. Let $f:X\to Y$ be a map from a set $X$ into a set $Y$. For a
given subset $A\subset Y$, we let $f^{-1}(A):=\\{x\in X:f(x)\in A\\}$.

Let $A$ be a set. $A^{\omega}$ denotes the set of infinite sequences with
elements in $A$, and $A^{\ast}$ denotes the set of sequences of finite, but
otherwise arbitrary length, of elements in $A$. $\epsilon$ denotes the empty
sequence. For $x\in A^{\ast}$, $x_{n}$ denotes the $n$-th element of the
sequence $x$, and $x_{n:m}$ stands for the fininte sequence
$x_{n}x_{n+1}\ldots x_{m}$. Similarly, for ${\bf x}\in A^{\ast}$, ${\bf
x}_{n}$ denotes the $n$-th element of the sequence ${\bf x}$, and ${\bf
x}_{n:m}$ stands for the fininte sequence ${\bf x}_{n}{\bf x}_{n+1}\ldots{\bf
x}_{m}$. $\left|x\right|$ refers to the length of $x$, i.e. for $x\in A^{n}$,
we have $\left|x\right|=n$, and by convention, we set $|{\bf x}|=\infty$ for
${\bf x}\in A^{\omega}$. For $x,y\in A^{\ast}$, $xy$ denotes the concatenation
of $x$ and $y$, and same holds for $x{\bf y}$, for $x\in A^{\ast}$ and ${\bf
y}\in A^{\omega}$. For $x^{(1)},\ldots,x^{(n)}\in A^{\ast}$,
$\coprod_{i=1}^{n}x^{(i)}$ stands for the concatenation $x^{(1)}x^{(2)}\ldots
x^{(n)}$. For an infinite family $\left(x^{(i)}\right)_{i\in\mathbf{N}}\in
A^{\ast}$, $\coprod_{i=1}^{\infty}x^{(i)}\in A^{\omega}$ denotes the infinite
concatenation of the elements in $\left(x^{(i)}\right)_{i\in\mathbf{N}}$.
Finally, for $x\in A^{\ast}$, we set $x^{n}:=\coprod_{i=1}^{n}x$, for
$n\in\mathbf{N}$, and $x^{\infty}:=\coprod_{i=1}^{\infty}x$. For instance,
$0^{\infty}$ denotes the infinite sequence containing only zeroes,
$(10)^{5}=1010101010$, and $10^{5}=100000$.

$\\{0,1\\}^{\ast}$ is called the set of finite binary sequences,
$\\{0,1\\}^{\omega}$ is called the set of infinite binary sequences. Following
[13, Chapter 1.4], we map $\\{0,1\\}^{\ast}$ one-to-one onto $\mathbf{N}_{0}$
by indexing each string through the quasi-lexicographical ordering [4, Section
1.1], i.e.

$(\epsilon,0),(0,1),(1,2),(00,3),(01,4),(10,5),(11,6),\ldots.$ (1)

We make the confusion between $x\in\\{0,1\\}^{\ast}$ and its index, and hence
any concept relative to elements of $\\{0,1\\}^{\ast}$ can also be used for
elements of $\mathbf{N}_{0}$. For $x\in\\{0,1\\}^{\ast}$, we define
$\bar{x}:=1^{|x|}0x$. For $x,y\in\\{0,1\\}^{\ast}$, we set $\langle
x,y\rangle:=\bar{x}y$. Note that $|\langle x,y\rangle|=2|x|+|y|+1$. Let
$q\in\mathbf{N}$. $\\{0,\ldots,q-1\\}^{\ast}$ is called the set of finite
$q$-ary sequences, $\\{0,\ldots,q-1\\}^{\omega}$ is called the set of infinite
$q$-ary sequences. For $x,y\in\\{0,\ldots,q-1\\}^{\omega}$, we write $x<_{L}y$
if there exists $j\in\mathbf{N}$ such that $x_{i}=y_{i}$ for all $i<j$, and
$x_{j}<y_{j}$. $<_{L}$ is called lexicographical ordering.

##  1 Introduction and statement of the main result

Representing real numbers in terms of sequences of bits is of major interest
in computer science and electrical engineering. The most common way to effect
such a conversion is the binary expansion. Indeed, a real number $s\in[0,1]$
can be written as a sum of negative powers of $2$. As an example, if $s=0.75$,
one can write

$s=0.75=\frac{1}{2}+\frac{1}{4}=2^{-1}+2^{-2}=1\times 2^{-1}+1\times
2^{-2}+0\times 2^{-3}+0\times 2^{-4}+\ldots$ (2)

Here, the sequence $110^{\infty}$ is called a binary expansion of $s=0.75$. We
conspicuously say “a binary expansion”, rather than “the binary expansion”, as
there are multiple such representations. Indeed, as

$\frac{1}{4}=\frac{\frac{1}{8}}{\frac{1}{2}}=\frac{\frac{1}{8}}{1-\frac{1}{2}}=\sum_{i=3}^{\infty}2^{-i},$
(3)

one has equivalently

$s=0.75=\frac{1}{2}+\frac{1}{4}=2^{-1}+\sum_{i=3}^{\infty}2^{-i}=1\times
2^{-1}+0\times 2^{-2}+\sum_{i=3}^{\infty}1\times 2^{-i},$ (4)

so ${\bf x}=101^{\infty}$ constitutes an alternative binary representation of
$s$ in terms of negative powers of $2$. Generally speaking, for every given
$s\in[0,1]$, there exist either one or two binary expansions. This result is a
common knowledge, and following [17, Section 1][7, Section 2][12, Section 1],
we refer to it as 2-ambiguity of the binary expansion. Following [16, Section
1.5, Problem 44], the real numbers with precisely two binary expansions are
rational. Moreover, one of the two expansions ends with $0^{\infty}$, and the
other expansion ends with $1^{\infty}$. To see this, consider a number $s\neq
0$ whose binary expansion ends with an infinite tail of $0$’s. Then, there
exists a binary sequence $x\in\\{0,1\\}^{\ast}$, of length $|x|=n$, such that
${\bf x}=x10^{\infty}$ is a binary expansion of $s$, i.e.

$s=x_{1}\times 2^{-1}+\ldots+x_{n}\times 2^{-n}+1\times 2^{-(n+1)}+0\times
2^{-(n+2)}+0\times 2^{-(n+3)}+\ldots$ (5)

As $1$ satisfies the following algebraic equation

$1=\sum_{i=1}^{\infty}2^{-i},$ (6)

one can replace last $1$ of the binary expansion of $x$, i.e.

$\displaystyle s$ $\displaystyle=x_{1}\times 2^{-1}+\ldots+x_{n}\times
2^{-n}+\left(\sum_{i=1}^{\infty}2^{-i}\right)\times 2^{-(n+1)}$ (7)
$\displaystyle=x_{1}\times 2^{-1}+\ldots+x_{n}\times
2^{-n}+\sum_{i=n+2}^{\infty}2^{-i}$ (8) $\displaystyle=x_{1}\times
2^{-1}+\ldots+x_{n}\times 2^{-n}+0\times 2^{-(n+1)}+1\times 2^{-(n+2)}+1\times
2^{-(n+3)}+\ldots$ (9)

This proves that ${\bf x}^{\prime}=w01^{\infty}$ is also a binary expansion of
$x$. The lexicographically larger of these two expansions, i.e. ${\bf
x}=w10^{\infty}$, is called the greedy binary expansion of $s$, and is the
lexicographically smaller, i.e. ${\bf x}^{\prime}=w01^{\infty}$, is called the
lazy binary expansion. In case when $s$ has only one expansion, both the
greedy and lazy binary expansion refer to the unique binary expansion of $s$.
Both greedy and lazy binary expansions have an associated algorithm generating
them. We next detail the algorithm generating $n$ first bits of the greedy
binary expansion of $s$, when presented with input $s\in[0,1]$ and
$n\in\mathbf{N}$. In the description, summarized as Algorithm 1, which is a
very classic algorithm following [8, Introduction], the variable $s$ contains
progressively the bits of the greedy binary expansion of $s$. Let us apply
this algorithm to $s=0.75$ with $n=4$:

  1. (1)

$r\leftarrow 0.75$, $x$ is initialized as the empty string $\epsilon$, the for
loop (line 4) is entered, with $i$ initialized to $1$

  2. (2)

$r=0.75\geq 0.5$, so $b\leftarrow 1$, $x\leftarrow\epsilon b=1$, $r\leftarrow
2r-b=2\times 0.75-1=0.5$, the algorithm continues the for loop, with $i=2$.

  3. (3)

$r=0.5\geq 0.5$, so $b\leftarrow 1$, $x\leftarrow 1b=11$, $r\leftarrow
2r-b=2\times 0.5-1=0$, the algorithm continues the for loop, with $i=3$.

  4. (4)

$r=0<0.5$, so $b\leftarrow 0$, $x\leftarrow 11b=110$, $r\leftarrow
2r-b=2\times 0-0=0$, the algorithm continues the for loop, with $i=4$.

  5. (5)

$r=0<0.5$, so $b\leftarrow 0$, $x\leftarrow 110b=1100$, $r\leftarrow
2r-b=2\times 0-0=0$, the algorithm exits the for loop, as $i=4=n$.

  6. (6)

$x=1100$ is returned by the algorithm.

Algorithm 1 is therefore seen to, indeed, generate the first $n=4$ bits of the
greedy binary expansion of $s=0.75$. Following [8, Section 2], to generate the
lazy binary expansion, one only needs to change the condition $r<0.5$ in line
5 of Algorithm 1 to $r\leq 0.5$.

Algorithm 1 Greedy algorithm for binary expansion

1:$s\in[0,1]$, $n\in\mathbf{N}$

2:$r\leftarrow s$

3:Initialize $x$ as the empty string $\epsilon$

4:for $i=1,\ldots,n$ do

5: if $r<0.5$, then $b\leftarrow 0$

6: else $b\leftarrow 1$

7: end if

8: $x\leftarrow xb$

9: $r\leftarrow 2\,r-b$

10:end for

11:return s

Binary expansions are not the only way to represent real numbers as infinite
sequences of bits. One can replace the base 2 in $s=\sum_{i=1}^{\infty}2^{-i}$
by $\beta\in(1,2]$ to get so-called $\beta$-expansions, i.e., representations
of real numbers as sums of negative powers of $\beta$. $\beta$-expansions
exhibit a much richer structure than binary expansions, specifically, the
2-ambiguity can turn into an $\infty$-ambiguity. An example illustrating this
aspect is the $G$-expansion of $s=1$, where $G$ is the golden ratio,
satisfying $G^{2}=G+1$, i.e., $G=\frac{1+\sqrt{5}}{2}$. Indeed, it follows
immediately that

$1=\frac{1}{G}+\frac{1}{G^{2}}=1\times\frac{1}{G}+1\times\frac{1}{G^{2}}+0\times\frac{1}{G^{3}}+0\times\frac{1}{G^{4}}+\cdots$
(10)

and hence ${\bf x}=1100\ldots$ is a $G$-expansion of $s=1$. An alternative
representation of $s=1$ in base $\beta=G$ is obtained by noting that
$\frac{1}{G^{2}}=\frac{1}{G^{3}}+\frac{1}{G^{4}}$, and hence

$1=\frac{1}{G}+\frac{1}{G^{3}}+\frac{1}{G^{4}}=1\times\frac{1}{G}+0\times\frac{1}{G^{2}}+1\times\frac{1}{G^{3}}+1\times\frac{1}{G^{4}}+0\times\frac{1}{G^{5}}+\cdots$
(11)

so that ${\bf x}^{\prime}=101100\ldots$ is also a $G$-expansion of $s=1$. By
iterating this heuristic, one can show that for every $n\geq 0$, the sequence
${\bf x}^{(n)}:=(10)^{n}110^{\infty}$ is a $G$-expansion of $x=1$. There are
hence infinitely many different $G$-expansions of $s=1$. Note that to show the
$\infty$-ambiguity of $1$ in base $G$, we used the fact that $1$ satisfies the
following algebraic equation

$1=\frac{1}{G}+\frac{1}{G^{2}},$ (12)

which is of the same flavour as the algebraic equation (6) used to show the
$2$-ambiguity of the binary expansions, and the fact that for
$n\in\mathbf{N}$, ${\bf x}^{(n)}=(10)^{n}110^{\infty}$ ends with an infinite
tail of zeroes.

We can then generalize this procedure to many bases $\beta$, and many
$s\in[0,1]$ satisfying the following sufficient pair of conditions:

  1. (a)

$\beta$ satisfies an equation of the form

$1=\sum_{i=1}^{N}\beta^{-n_{i}},$ (13)

where $N,n_{1},\ldots,n_{N}\in\mathbf{N}$ and the $n_{i}\neq n_{j}$ for $1\leq
i<j\leq N$,

  2. (b)

there is a $\beta$-expansion of $s$ finishing with an infinite tail of zeros.

If both (a) and (b) are satisfied, then the representation of $s$ in base
$\beta$ is $\infty$-ambiguous.

Regardless, one can define the notion of greedy and lazy expansions for
arbitrary $\beta\in(1,2]$, in the same manner as in the binary case.
Specifically, we define the greedy $\beta$-expansion of $s\in[0,1]$ as the
lexicographically largest $\beta$-expansion, and the lazy $\beta$-expansion as
the lexicographically smallest $\beta$-expansion. Both greedy and lazy
$\beta$-expansions have an associated algorithm generating them. Algorithm 2
below generalizes Algorithm 1 to deliver the $n$ first bits of the greedy
$\beta$-expansion of $x$ for $\beta\in(1,2]$, on input $s\in[0,1]$ and
$n\in\mathbf{N}$. Following [8, Introduction], Algorithm 2 generates the
greedy $\beta$-expansion. Similar considerations apply for the lazy
$\beta$-expansion.

Algorithm 2 Greedy algorithm for $\beta$-expansion

1:$\beta\in(1,2]$, $s\in[0,1]$, $n\in\mathbf{N}$

2:$r\leftarrow s$, initialize $x$ as the empty string $\epsilon$

3:for $i=\\{1,\ldots,n\\}$ do

4: if $r<\frac{1}{\beta}$ then set $b\leftarrow 0$

5: else set $b\leftarrow 1$

6: end if

7: $x\leftarrow xb$

8: $r\leftarrow\beta\,r-b$

9:end for

10:return x

The multiplicity of $\beta$-expansions of a given real number leads to robust
binary representations of real numbers, an insight exploited for example in
A/D conversion. Specifically, it was shown in [10] that $\beta$-expansions can
yield A/D conversion, with arbitrary precision, even when imperfect quantizers
are employed. To illustrate this, consider the problem of encoding $s\in[0,1]$
into a binary sequence, i.e. performing an A/D conversion. One can build a
physical device to perform Algorithm 1 in order to generate the greedy binary
expansion of $s$. However, at line 4 of the algorithm, the operation $r<0.5$
is limiting, as it requires infinite precision, which is impossible to realize
in practice. Any physical device implementing $r<0.5$ will necessarily fail
from time to time. If it fails once during the conversion, then maybe it will
generate the lazy binary expansion of $s$, which is still a valid binary
representation of $s$. However, if it fails twice or more often, then because
of the $2$-ambiguity property the algorithm will necessarily generate a wrong
representation of $s$. Now, as $\beta$-expansions yield potentially infinitely
many binary representations of $s$, a physical device can, in theory, fail
infinitely many often, but still yield a correct result.

It is now natural to ask the following question. We have seen that
$\beta$-expansions lead to robust binary representations. However, these
binary reprensation could be very complex and very long compared to the binary
representation induce by the binary expansions. In this case
$\beta$-expansions to represent real numbers would be of poor interest, as the
binary expansions would much more efficient in terms of storage. Then, for
every $s\in[0,1]$, how does the complexity of its binary expansions relate to
the complexity of its $\beta$-expansions? We study this question by
quantifying algorithmic complexity, also referred to as Kolmogorov complexity,
of finite prefixes of the $\beta$-expansions.

We proceed by defining the algorithmic complexity, which quantifies the
complexity of finite sequences. This notion naturally extends to infinite
sequences by computing the algorithmic complexity of all the finite prefixes
of a given infinite sequence. Let $x$ be a finite binary sequence, and
$U:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ be a universal effective algorithm,
whose precise meaning will be detailed below. We define the algorithmic
complexity $K[x]$ of $x$ to be the length of the shortest finite binary
sequence $x^{\ast}$ satisfying $U(x^{\ast})=x$. An effective algorithm
$\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ is precisely a partial
computable function [13, Definition 1.7.1], which roughly refers to algorithms
which can be run by digital computers. As a counter-example, Algorithm 1 is
not an effective algorithm, as it manipulates a variable “$r$”, which is a
real number, and real numbers can not be processed on digital computers,
simply as they require, in general, infinitely many bits to represent them.
Effective algorithms can manipulate finite binary sequences and perform
operations such as bit shift, copy bits, paste bits which can then be use to
define more complex operations on integers and rationals, such as addition and
multiplication. A universal effective algorithm is an effective algorithm
$U:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ such that for any given effective
algorithm $\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$, there exists a
$p\in\\{0,1\\}^{\ast}$, called program for $\varphi$, such that
$\varphi(\cdot)=U(\langle p,\cdot\rangle)$. The existence of universal
effective algorithms was proven in [18]. Note that above we chose $U$ somewhat
abitrarily. Indeed, the choice of the universal effective algorithm for the
definition of the algorithmic complexity can be arbitrary, as explained below
Theorem 14.2.1 in [6], and will be detailed in the next section. As a special
case of [17, Theorem 2], we show the following very simple lemma.

######  Lemma 1.1.

Let $\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ be an effective algorithm.
Then, there exists a constant $c>0$, such that for all
$x,x^{\prime}\in\\{0,1\\}^{\ast}$ satisfying $x^{\prime}=\varphi(x)$, one has
$K[x^{\prime}]\leq K[x]+c$.

###### Proof.

Let $\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ be an effective algorithm.
$\varphi\circ U$ is also an effective algorithm (the composition of two
effective algorihm is again an effective algorithm [14, Exercise 2.1.2]). As
$U$ is a universal effective algorithm, there exists $p\in\\{0,1\\}^{\ast}$,
such that $U(\langle p,x\rangle)=\varphi\circ U(x)$, for all
$x\in\\{0,1\\}^{\ast}$. Let now $x,x^{\prime}\in\\{0,1\\}^{\ast}$, such that
$\varphi(x)=x^{\prime}$. Let $x^{\ast}\in\\{0,1\\}^{\ast}$ satisfying
$U(x^{\ast})=x$ and $|x^{\ast}|=K[x]$. Then, $U(\langle
p,x^{\ast}\rangle)=\varphi\circ U(x^{\ast})=\varphi(x)=x^{\prime}$. It follows
that $K[x^{\prime}]\leq|\langle p,x^{\ast}\rangle|=2|p|+|x^{\ast}|+1$. We let
$c:=2|p|+1$, and the result follows. ∎

The algorithmic complexity of finite prefixes of binary expansions is very
well understood, namely, the algorithmic complexity of the greedy binary
expansion of a given real number is equal to the algorithmic complexity of its
lazy binary expansion, which follows directly from the fact that one can
generate the lazy binary expansion from the greedy binary expansion by using
the procedure employed in equations (5)-(9), which can be achieved by an
effective algorithm. To the best of our knowledge, there is no literature at
all relating the algorithmic complexity of the $\beta$-expansions to the
algorithmic complexity of the binary expansions, even though their rich
structure suggests interesting relashionships. In particular, for a given
$s\in[0,1]$, its $\beta$-expansions could have a different algorithmic
complexity than its binary expansions.

Indeed, at first glance, $\beta$-expansions could be more complex than their
binary counterparts. To illustrate this, we have compiled the first 50 bits of
the greedy $\beta$-expansion, for various values of $\beta$, in Table 1. The
greedy $\beta$-epansions were generated by the greedy algorithm summarized in
Algorithm 2.

$\beta$ | Greedy $\beta$-expansion of $s=0.75$
---|---
2 | 11000000000000000000000000000000000000000000000000
1.01 | 00000000000000000000000000001000000000000000000000
1.2 | 01000000000000010000000000000000000100000000000000
1.5 | 10000010010010100000000010000001000010000001001001
1.8 | 10100010101000000110101000011000011010011000010000
1.99 | 10111110001001001001010001100011010000100000111010
Table 1: First 50 bits of the $\beta$-expansion of $s=0.75$ generated by the
greedy algorithm for $\beta$-expansions (Algorithm 2), for different values of
$\beta$.

We can make the following observations. Although the binary expansion of
$s=0.75$ exhibits a very simple structure, its greedy $\beta$-expansions in
Table 1 do not seem to exhibit recognizable structural regularities. Such
regularities would be indicators of low algorithmic complexity. The absence of
obvious structural regularities does not, however, necessarily imply large
algorithmic complexity either. We now approach this question in a more
systematic manner by identifying values of $\beta$ for which the
$\beta$-expansion of a given $x\in[0,1]$ is closely related to its binary
expansion. Concretely, let $s=0.75$ and $\beta=\sqrt{2}$. Instead of
generating the greedy $\sqrt{2}$-expansion of $s$, which is
$10000000010010\ldots$ and exhibits no evident structure, we observe that

$\displaystyle s=0.75$
$\displaystyle=\frac{1}{2}+\frac{1}{4}=\frac{1}{(\sqrt{2})^{2}}+\frac{1}{(\sqrt{2})^{4}}=\sqrt{2}^{-2}+\sqrt{2}^{-4}$
(14)
$\displaystyle=0\times\sqrt{2}^{-1}+1\times\sqrt{2}^{-2}+0\times\sqrt{2}^{-3}+1\times\sqrt{2}^{-4}+0\times\sqrt{2}^{-5}+\ldots$
(15)

Hence, ${\bf x}=01010^{\infty}$ is a $\sqrt{2}$-expansion of $s=0.75$, which
displays a very simple structure, namely two 1’s and ending with an infinite
tail of zeros. Recall that the greedy binary expansion of $s=0.75$ is given by
$110^{\infty}$ What is more, owing to the idea underlying the representation
(15), is that we can even establish an effective relationship between the
greedy binary expansion and a $\sqrt{2}$-expansion. Specifically, if ${\bf
x}\in\\{0,1\\}^{\omega}$ is the greedy binary expansion of $s\in[0,1]$, then
the sequence ${\bf x}^{\prime}\in\\{0,1\\}^{\omega}$ defined as

$\begin{array}[]{l}{\bf x}^{\prime}_{2i-1}:=0,\\\ {\bf x}^{\prime}_{2i}:={\bf
x}_{i},\end{array}\ \ \text{for all}\ i\in\mathbf{N},$ (16)

is a $\sqrt{2}$-expansion of $s$. Indeed, as ${\bf x}$ is the greedy binary
expansion of $s$,

$\displaystyle s$ $\displaystyle=\sum_{i=1}^{\infty}{\bf
x}_{i}2^{-i}=\sum_{i=1}^{\infty}{\bf
x}_{i}\sqrt{2}^{-2i}=\sum_{i=1}^{\infty}{\bf
x}_{i}\sqrt{2}^{-2i}+\sum_{i=1}^{\infty}0\times\sqrt{2}^{-(2i-1)}$ (17)
$\displaystyle\overset{(\ref{eq:definition of b_i prime as alternating b_i and
0})}{=}\sum_{i=1}^{\infty}{\bf
x}^{\prime}_{2i}\sqrt{2}^{-2i}+\sum_{i=1}^{\infty}{\bf
x}^{\prime}_{2i-1}\sqrt{2}^{-(2i-1)}=\sum_{i=1}^{\infty}{\bf
x}^{\prime}_{i}\sqrt{2}^{-i}.$ (18)

This idea can be generalized as follows. For $m\in\mathbf{N}$, $m\geq 2$, let
${\bf x}\in\\{0,1\\}^{\omega}$ be the greedy binary expansion of $s\in[0,1]$.
Then, the sequence ${\bf x}^{\prime}\in\\{0,1\\}^{\omega}$ defined as

$\begin{array}[]{l}{\bf x}^{\prime}_{mi-k}:=0,\ k\in\\{1,\ldots,m-1\\}\\\ {\bf
x}^{\prime}_{mi}:={\bf x}_{i},\end{array}\ \ \text{for all}\ i\in\mathbf{N},$
(19)

is a $\sqrt[m]{2}$-expansion of $s$. Indeed, as ${\bf x}$ is the greedy binary
expansion of $s$,

$\displaystyle s$ $\displaystyle=\sum_{i=1}^{\infty}{\bf
x}_{i}2^{-i}=\sum_{i=1}^{\infty}{\bf
x}_{i}\sqrt[m]{2}^{-mi}=\sum_{i=1}^{\infty}{\bf
x}_{i}\sqrt[m]{2}^{-mi}+\sum_{k=1}^{m-1}\sum_{i=1}^{\infty}0\times\sqrt[m]{2}^{-(mi-k)}$
(20) $\displaystyle\overset{(\ref{eq:generation of beta expansions sqrt m
2})}{=}\sum_{i=1}^{\infty}{\bf
x}^{\prime}_{mi}\sqrt[m]{2}^{-mi}+\sum_{k=1}^{m-1}\sum_{i=1}^{\infty}{\bf
x}^{\prime}_{mi-k}\sqrt[m]{2}^{-(mi-k)}=\sum_{i=1}^{\infty}{\bf
x}^{\prime}_{i}\sqrt[m]{2}^{-i}.$ (21)

We shall now cast (19) into an effective algorithm which takes the first
$\lceil k/m\rceil$ bits ${\bf x}_{1:\lceil k/m\rceil}$ of the greedy binary
expansion of $s$ as input and produces the first $k$ bits ${\bf
x}^{\prime}_{1:k}$ of a $\sqrt[m]{2}$-expansion ${\bf x}^{\prime}$. The
procedure is made explicit in Algorithm 3.

Algorithm 3 $\sqrt[m]{2}$-expansion from greedy binary expansion

1:$m\in\mathbf{N}$, $x\in\\{0,1\\}^{\ell}$, $k\in\left\llbracket
m\ell\right\rrbracket$

2:Initialize $y$ as the empty string $\epsilon$

3:for $i=1,\ldots,k$ do

4: if $i$ is divisible by $m$ then

5: $y\leftarrow yx_{i/m}$

6: else

7: $y\leftarrow y0$

8: end if

9:end for

10:return y

All the steps in Algorithm 3 involve only multiplications of integers,
bitshifts and concatenations of binary sequences, which makes it an effective
algorithm. Note that one can find a reciprocal of this algorithm, namely a
procedure that generates the first $\lceil k/m\rceil$ bits of the greedy
binary expansion from the first $k$ of a $\sqrt[m]{2}$-expansion. This
algorithm would be also effective as it would involve very similar operations
as Algorithm 3. As we can generate the first $k$ bits ${\bf x}^{\prime}_{1:k}$
of a $\sqrt[m]{2}$-expansion ${\bf x}^{\prime}$ from the first $\lceil
k/m\rceil$ bits ${\bf x}_{1:\lceil k/m\rceil}$ of the greedy binary expansion
${\bf x}$ through an effective algorithm, and vice-versa, then by Lemma 1.1,
there exists $c>0$ such that

$\left|K\left[{\bf x}^{\prime}_{1:k}\right]-K\left[{\bf x}_{1:\lceil
k/m\rceil}\right]\right|<c,$ (22)

where $c$ is independant of $k$. We then have a concrete relationship between
the greedy binary expansion and a $\sqrt[m]{2}$-expansion.

The main contribution of this paper is to prove that (22) can be generalized
to all computable bases $\beta\in(1,2]$, i.e., all bases whose greedy binary
expansion can be generated by an effective algorithm. The class of computable
numbers is very wide, as it contains all algebraic numbers, and even some
transcendental numbers such as $\pi$ and $e$. The statement we will prove is
the following.

######  Theorem 1.2.

Let $s\in[0,1]$, and $\beta\in(1,2]$ be a computable number. Let ${\bf x}$ be
either the greedy or lazy binary expansion of $s$. Then, there exists a
$\beta$-expansion of $s$, denoted by ${\bf x}^{\prime}$ and $c>0$, satisfying

$\left|K\left[{\bf x}^{\prime}_{1:k}\right]-K\left[{\bf x}_{1:\lceil
k\log_{2}(\beta)\rceil}\right]\right|<c,\ \ \forall k\in\mathbf{N}.$ (23)

Note that setting $\beta=\sqrt[m]{2}$ in (1.2) recovers (22), as a special
case. The multiplicative constant $\log_{2}(\beta)$ can be interpreted as
follows. As the first $n$ bits of a $\beta$-expansion of $s\in[0,1]$
approximate $s$ to within an error of $\beta^{-n}$, the first
$n\log_{2}(\beta)$ of the greedy binary expansion ${\bf x}$ of $s$ suffice to
describe this approximation. Indeed, the first $n\log_{2}(\beta)$ bits of
${\bf x}$ approximate $s$ to within an error of
$2^{-n\log_{2}(\beta)}=\beta^{-n}$.

Theorem 1.2 hence states that there is no increase in algorithmic complexity
when switching from base 2 to any computable $\beta\in(1,2]$. Concretely, for
every $s\in[0,1]$ and fixed approximation error, there exists an approximation
in base $\beta$ that exhibits the same algorithmic complexity as the greedy
binary expansion.

Moreover, we give the explicit formula for the $\beta$-expansion ${\bf
x}^{\prime}$ satisfying (23). We give examples of such $\beta$-expansions in
Table 2. By compparison with Table 1, we note that for $\beta=1,5,1.8$ and
$1.99$, the generated $\beta$-expansion exactly agrees with the greedy
$\beta$-expansion on the first 50 bits, but disagrees fro $\beta=1.01$ and
$1.2$. In fact, we have generated the first $5.10^{6}$ bits of ${\bf
x}^{\prime}$, and for $\beta=1.5,1.8$ and $1.99$, it still agrees with the
greedy $\beta$-expansion. However, we also have tested with less special
values of $s$, such as $s=0.342736$. In this case, we did not find any value
of $\beta$ such that ${\bf x}^{\prime}$ agrees with the greedy
$\beta$-expansion.

$\beta$ |  $\beta$-expansion of $s=0.75$ satisfying (23)
---|---
2 | 11000000000000000000000000000000000000000000000000
1.01 | 00000000000000000000000000000000000000000000000000
1.2 | 00100000010000000000000001000000000001000000000000
1.5 | 10000010010010100000000010000001000010000001001001
1.8 | 10100010101000000110101000011000011010011000010000
1.99 | 10111110001001001001010001100011010000100000111010
Table 2: First 50 bits of the $\beta$-expansion of $s=0.75$ satisyfing (23)

##  2 Technical preliminaries

In this section, we introduce preparatory material on $\beta$-expansions and
algorithmic complexity, and we split Thoerem 1.2 in subcases to be proven in
the remaining sections of the paper.

###  2.1 $\beta$-expansions

Let $\beta\in(1,2]$. Following [15], we say that ${\bf
x}\in\\{0,1\\}^{\omega}$ is a $\beta$-expansion of $s\in
I_{\beta}:=\left[0,\frac{1}{\beta-1}\right]$ if

$s=\delta_{\beta}({\bf x}),$ (24)

where

$\begin{array}[]{lccl}\delta_{\beta}:&\\{0,1\\}^{\omega}&\to&I_{\beta}\\\
&{\bf x}&\mapsto&\displaystyle\sum_{i=1}^{\infty}{\bf
x}_{i}\beta^{-i}.\end{array}$ (25)

To see that $\delta_{\beta}$, indeed, maps to $I_{\beta}$, note that
$\delta_{\beta}(0^{\infty})=0$ and
$\delta_{\beta}(1^{\infty})=\frac{1}{\beta-1}$. As already mentionned in
Section 1, there are, in general, multiple sequences ${\bf
x}\in\\{0,1\\}^{\omega}$ generating a given $x$ according to (24), and we
denote by $\Sigma_{\beta}(s):=\delta_{\beta}^{-1}(\\{s\\})$ the set of all
$\beta$-expansions of $s\in I_{\beta}$. For instance, as explained in Section
1, for $G=\frac{1+\sqrt{5}}{2}$, $\\#\left(\Sigma_{\beta}(1)\right)=\infty$.
Moreover, for $\beta\in(1,G)$, the set of $\beta$-expansions for each $s\in
I_{\beta}$ is uncountable, i.e.,
$\\#\left(\Sigma_{\beta}(s)\right)=2^{\aleph_{0}}$ [11, Theorem 3]. For $s\in
I_{\beta}$, we define the greedy $\beta$-expansion according to ${\bf
g}_{\beta}(s):=\sup_{L}\left(\Sigma_{\beta}(s)\right)$. As mentionned in
Section 1, it is explained in [8, Introduction] that ${\bf g}_{\beta}(s)$ is
computed by Algorithm 2. Specifically, the variable “$r$” in Algorithm 2
realizes the greedy map $G_{\beta}:I_{\beta}\to I_{\beta}$ [1, Section 1]:

$G_{\beta}(r)=\begin{cases}\beta r,\ \ \text{if}\ r<\frac{1}{\beta},\\\ \beta
r-1,\ \ \text{if}\ r\geq\frac{1}{\beta},\end{cases}\ \ \forall r\in
I_{\beta}.$ (26)

Further, the variable “$b$” in Algorithm 2 realizes the computation of the
following function

$d_{\beta,greedy}(r)=\begin{cases}0,\ \ \text{if}\ r<\frac{1}{\beta},\\\ 1,\ \
\text{if}\ r\geq\frac{1}{\beta},\end{cases}\ \ \forall r\in I_{\beta}.$ (27)

Finally, the greedy $\beta$-expansion is shown to be given by

${\bf
g}_{\beta}(s)=\coprod_{i=0}^{\infty}d_{\beta,greedy}\left(G_{\beta}^{i}(s)\right).$
(28)

One can also define the lazy $\beta$-expansion
$\boldsymbol{\ell}_{\beta}(s):=\inf_{L}\left(\Sigma_{\beta}(s)\right)$.
Following [8, Section 2] the lazy $\beta$-expansion can be generated as
follows. Analogously to the greedy map $G_{\beta}$ above, we define the lazy
map according to $L_{\beta}:I_{\beta}\to I_{\beta}$ [1, Section 1]:

$L_{\beta}(r)=\begin{cases}\beta r,\ \ \text{if}\
r\leq\frac{1}{\beta(\beta-1)},\\\ \beta r-1,\ \ \text{if}\
r>\frac{1}{\beta(\beta-1)},\end{cases}\ \ \forall r\in I_{\beta}.$ (29)

The bits of the lazy $\beta$-expansion are then computed by the following
function

$d_{\beta,lazy}(r)=\begin{cases}0,\ \ \text{if}\
r\leq\frac{1}{\beta(\beta-1)},\\\ 1,\ \ \text{if}\
r>\frac{1}{\beta(\beta-1)},\end{cases}\ \ \forall r\in I_{\beta}.$ (30)

Finally, the lazy $\beta$-expansion is shown to be given by

$\boldsymbol{\ell}_{\beta}(s)=\coprod_{i=0}^{\infty}d_{\beta,lazy}\left(L_{\beta}^{i}(s)\right).$
(31)

We end this section with the following note: for $\beta\in(1,2]$, and
$x\in\\{0,1\\}^{\ast}$, we use the shorthand
$\delta_{\beta}(x):=\sum_{i=1}^{|x|}x_{i}\beta^{-i}$ instead of the more
cumbersome $\delta_{\beta}(x0^{\infty})$.

###  2.2 Algorithmic complexity

We now proceed in establishing solid ground for the study of algorithmic
complexity. Recall the notion of universal effective algorithm introduced in
previous section. Following [4, Definition 3.4][6, Chapter 14.2][13,
Definition 2.1.1], the algorithmic complexity of a binary sequence
$x\in\\{0,1\\}^{\ast}$ with respect to a given universal effective algorithm
$U:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ is

$K_{U}[x]:=\min\\{\left|u\right|:u\in\\{0,1\\}^{\ast},U(u)=x\\}.$ (32)

Following [4, Definition 3.4], we say that $x^{\ast}$ is the canonical program
for $x$ with respect to $U$ if

$x^{\ast}:=\min\left\\{u\in\\{0,1\\}^{\ast}:U(u)=x\right\\},$ (33)

where the $\min$ is taken with respect to the quasi-lexicographical order.
Note that $|x^{\ast}|=K_{U}[x]$.

Following [6, Theorem 14.2.1], we now show that the choice of $U$ is somewhat
not important.

######  Lemma 2.1.

Let $V:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ be another universal effective
algorithm. Then, there exists $c>0$ such that for all $x\in\\{0,1\\}^{\ast}$,

$\left|K_{U}[x]-K_{V}[x]\right|\leq c.$ (34)

###### Proof.

As $U$ is a universal effective algorithm, there exists $p\in\\{0,1\\}^{\ast}$
such that

$U(\langle p,x\rangle)=V(x),\text{ for all }x\in\\{0,1\\}^{\ast}.$ (35)

Let $x\in\\{0,1\\}^{\ast}$, and let $x^{\ast}\in\\{0,1\\}^{\ast}$ be the
canonical program for $x$ with respect to $V$. Then, $U(\langle
p,x^{\ast}\rangle)=V(x^{\ast})=x$. It follows that $K_{U}[x]\leq|\langle
p,x^{\ast}\rangle|\leq 2|p|+|x^{\ast}|+1=2|p|+1+K_{V}[x]$. We let
$c_{1}:=2|p|+1$, and then $K_{U}[x]\leq K_{V}[x]+c_{1}$. Likewise, we can show
that there is a constant $c_{2}>0$ such that $K_{V}[x]\leq K_{U}[x]+c_{2}$.
The lemma follows by letting $c=\max(c_{1},c_{2})$. ∎

Then, the definition of algorithmic complexity relatively to a specific
universal effective algorithm is invariant up to a positive additive constant.
From now on, we fix a universal effective algorithm
$\mathcal{U}_{\operatorname{ref}}$, and define the (absolute) algorithmic
complexity of the binary sequences $x$ as

$\begin{array}[]{lccl}K[\cdot]:&\\{0,1\\}^{\ast}&\to&\mathbf{N}\\\
&x&\mapsto&K_{\mathcal{U}_{\operatorname{ref}}}[x].\end{array}$ (36)

In this paper, we are interested in comparing the algorithmic complexity of
binary expansions and $\beta$-expansions. As the expansions are of infinite
length and algorithmic complexity is defined for finite binary sequences only,
we need an adequate extension of algorithmic complexity to infinitely long
sequences. Specifically, following [3, Definition 10.9], we shall consider the
algorithmic complexity of $n$-prefixes ${\bf x}_{1:n}$ of such an infinite
sequence ${\bf x}$. For simplicity of notations, we shall write

$K[{\bf x}|n]:=K[{\bf x}_{1:n}],\ \text{ for all }{\bf
x}\in\\{0,1\\}^{\omega},\ \text{ and all }n\in\mathbf{N}.$ (37)

The above definition allows to study the algorithmic complexity of
$\beta$-expansions.

###  2.3 Algorithmic complexity of $\beta$-expansions

We now investigate the algorithmic complexity of $\beta$-expansions, with the
goal of comparing its behavior to the algorithmic complexity of binary
expansions. This is motivated by the fact that binary expansions are
essentially unique, i.e., unique up to the 2-ambiguity property discussed in
Section 1, whereas $\beta$-expansions are highly non-unique as exemplified in
Section 1. The goal of our analysis is to develop an understanding of how this
nonuniqueness is reflected in terms of algorithmic complexity.

As a first exercise, we start by studying how the 2-ambiguity of binary
expansions is reflected in terms of algorithmic complexity. Specifically, we
make formal the following statement from [2, Section IV]: “In the cases where
$\delta_{2}$ is not injective, either one of the two inverse images can be
selected, since they have essentially (up to a small additive term) the same
Kolmogorov complexity”.

######  Lemma 2.2.

There exists $c>0$ such that, for every given $s\in[0,1]$, its greedy binary
expansion ${\bf g}_{2}(s)$ and its lazy binary expansion
$\boldsymbol{\ell}_{2}(s)$ satisfy the relation

$\left|K[{\bf g}_{2}(s)|n]-K[\boldsymbol{\ell}_{2}(s)|n]\right|\leq c,\
\forall n\in\mathbf{N}.$ (38)

###### Proof.

As explained in Section 1, the greedy and lazy binary expansion of a given
$s\in[0,1]$ differ only when the greedy binary expansion ends with
$0^{\infty}$, and in this case, the lazy expansion ends with $1^{\infty}$. In
this case, $s$ is said to be a “dyadic number”, and we denote by $\mathbf{D}$
the set of all dyadic numbers. On one hand, if $s\notin\mathbf{D}$, one has
$\boldsymbol{\ell}_{2}(s)={\bf g}_{2}(s)$, and (38) holds trivially. On the
other hand, we can create two effective algorithms
$\varphi,\psi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$, such that

$\begin{array}[]{l}\varphi({\bf
g}_{2}(s)_{1:n})=\boldsymbol{\ell}_{2}(s)_{1:n}\\\
\psi(\boldsymbol{\ell}_{2}(s)_{1:n})={\bf g}_{2}(s)_{1:n}\end{array},\ \forall
n\in\mathbf{N},\ \text{and}\ \forall x\in\mathbf{D}.$ (39)

The operations underlying $\varphi$ are summarized in Algorithm 4. We do not
present the operations underlying $\psi$ as they are very similar.

Algorithm 4 Generator of lazy binary expansion from the greedy binary
expansion.

1:$x\in\\{0,1\\}^{\ast}$

2:Find the position $n$ of the last $1$ in $x$

3:$x_{n}\leftarrow 0$

4:for $i=n+1,\ldots,|x|$ do

5: $x_{i}\leftarrow 1$

6:end for

7:return $x$

By application of Lemma 1.1 to (39), there exists two constants
$c_{\varphi},c_{\psi}>0$ such that

$\begin{array}[]{l}K[\boldsymbol{\ell}_{2}(s)|n]\leq K[{\bf
g}_{2}(s)|n]+c_{\varphi},\\\ K[{\bf g}_{2}(s)|n]\leq
K[\boldsymbol{\ell}_{2}(s)|n]+c_{\psi},\end{array}\ \forall n\in\mathbf{N},\
\text{and}\ \forall s\in\mathbf{D}.$ (40)

We set $c:=\max(c_{\varphi},c_{\psi})$, thereby finishing the proof. ∎

Remaining section of the paper will be dedicated to the proof of Theorem 1.2,
which thanks to the simpler notation introduced above and Lemma 2.2, can be
restated as follows. For all $s\in[0,1]$ and all computable $\beta\in(1,2]$,
there exists ${\bf x}\in\Sigma_{\beta}(s)$ and $c>0$ such that

$\left|K[{\bf g}_{2}(s)|n]-K[{\bf x}|\lceil n\log_{2}(\beta)\rceil]\right|\leq
c,\ \ \forall n\in\mathbf{N}.$ (41)

(41) consitutes a vast extension of [17, Theorem 3], which establishes an
equivalent fact for $q$-ary expansions, where $q\in\mathbf{N}_{2}$. More
precisely, for a given $s\in[0,1]$, a $q$-ary expansion of $s$ is an infinite
$q$-ary sequence ${\bf x}\in\\{0,\ldots,q-1\\}^{\mathbf{N}}$ satisfying

$s=\sum_{i=1}^{\infty}{\bf x}_{i}q^{-i}=:\delta_{q}({\bf x}).$ (42)

Following [4, Section 7.2], $q$-expansions also display $2$-ambiguity
property: “If $\delta_{q}({\bf x})$ is irrational, then $\delta_{q}({\bf
x})=\delta_{q}({\bf x}^{\prime})$ implies ${\bf x}={\bf x}^{\prime}$. On the
other hand, for rational numbers there sometimes are two different natural
positional representations”. For a given $s\in[0,1]$, we define its greedy
$q$-ary expansion ${\bf g}_{q}(s)$ to be its lexicographically larger $q$-ary
expansion, and its lazy $q$-ary expansion $\boldsymbol{\ell}_{q}(s)$ to be its
lexicographically smaller $q$-ary expansion. Further, for
$q\in\mathbf{N}_{2}$, one can generalize the algorithmic complexity to finite
$q$-ary sequences as follows. We have defined effective algorithms as a
specific subset of functions $\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$. Following
[17, Section 1], we consider the more general $q$-ary effective algorithms
$\varphi:\\{0,\ldots,q-1\\}^{\ast}\to\\{0,\ldots,q-1\\}^{\ast}$, which roughly
refer to algorithms which can be run on a digital computer allowing
computations on sequence in $\\{0,\ldots,q-1\\}^{\ast}$. $q$-ary universal
effective algorithms are defined accordingly. For $q\in\mathbf{N}_{2}$, we fix
a $q$-ary universal effective algorithm
$U_{q}:\\{0,\ldots,q-1\\}^{\ast}\to\\{0,\ldots,q-1\\}^{\ast}$, and we define
the $q$-ary algorithmic complexity as

$K_{q}[x]:=\min\\{|u|:u\in\\{0,\ldots,q-1\\}^{\ast},U_{q}(\langle|x|,u\rangle)=x\\},\
\ \text{ for }x\in\\{0,\ldots,q-1\\}^{\ast}.$ (43)

[17, Theorem 3] states that for all $q\in\mathbf{N}_{2}$ and all $s\in[0,1]$,
there exists $c>0$ such that

$\left|\log_{2}(q)K_{q}\left[{\bf g}_{q}(s)|n\right]-K_{2}\left[{\bf
g}_{2}(s)|\lceil n\log_{2}(q)\rceil\right]\right|\leq c,\ \ \text{for all}\
n\in\mathbf{N}.$ (44)

Note that in [17], the author uses a different version of Kolmogorov
complexity, but one can easily adapt the proof. The proof proceeds roughly, as
we omit some technical details, as follows. Each symbol $x_{i}$ of a $q$-ary
sequence $x$ can be encoded by a binary sequence $x_{i}^{(2)}$ of length
$\simeq\log_{2}(q)$. Then, $x$ can be encoded by a binary sequence $x^{(2)}$
of length $\simeq|x|\log_{2}(q)$. We call $x^{(2)}$ the binary encoding of
$x$. One can proove quite easily that
$K_{2}\left[x^{(2)}\right]\simeq\log_{2}(q)K_{q}[x]$. Now, using arguments
which deeply rely on the $2$-ambiguity of $q$-ary expansions, we can construct
two effective algorithms $\varphi,\psi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$
such that for all $s\in[0,1]$, one has

$\begin{array}[]{ll}\varphi\left({\bf g}_{2}(s)_{1:\lceil
n\log_{2}(q)\rceil}\right)&=({\bf g}_{q}(s)_{1:n})^{(2)}\\\ \psi\left(({\bf
g}_{q}(s)_{1:n})^{(2)}\right)&={\bf g}_{2}(s)_{1:\lceil
n\log_{2}(q)\rceil}\end{array}\ \text{ for all }n\in\mathbf{N},$ (45)

where $({\bf g}_{q}(s)_{1:n})^{(2)}$ indicates the binary encoding of ${\bf
g}_{q}(s)_{1:n}$. These two algorithm convert between the binary and $q$-ary
representations, and they are proven to be effective algorithms in the details
of the proofs in [17]. By Lemma 1.1, one can conclude that

$\left|K_{2}\left[({\bf g}_{q}(s)_{1:n})^{(2)}\right]-K_{2}\left[{\bf
g}_{2}(s)_{1:\lceil n\log_{2}(q)\rceil}\right]\right|\leq c,\ \ \text{for
all}\ n\in\mathbf{N}.$ (46)

As $K_{2}\left[x^{(2)}\right]\simeq\log_{2}(q)K_{q}[x]$ for all
$b\in\\{0,\ldots,q-1\\}^{\ast}$, (44) follows. As mentioned previously, the
above proof of [17, Theorem 3] hinges critically on the 2-ambiguity of the
$q$-ary expansions. $\beta$-expansions, however, exhibit $\infty$-ambiguity.

One can still use the 2-ambiguity of binary expansions to show a first step
towards the proof of (41), as follows.

######  Lemma 2.3.

For all $s\in[0,1]$ and all computable $\beta\in(1,2]$, there exists $c>0$
such that

$K[{\bf g}_{2}(s)|\lceil n\log_{2}(\beta)\rceil]\leq K[{\bf x}|n]+c,\ \
\forall n\in\mathbf{N},\ \ \forall{\bf x}\in\Sigma_{\beta}(s).$ (47)

The proof is effected in Appendix B. The remainder of this paper is devoted to
developing mathematical tools needed to deal with the $\infty$-ambiguity of
$\beta$-expansions. As a result, we establish the following statement, which,
combined to Lemma 2.3, immediately implies (41).

######  Theorem 2.4.

For all $s\in[0,1]$ and all computable $\beta\in(1,2]$, there exists $\hat{\bf
x}_{\beta}(s)\in\Sigma_{\beta}(s)$ and $c>0$ such that

$K[\hat{\bf x}_{\beta}(s)|n]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+c,\ \ \forall n\in\mathbf{N}.$ (48)

In the next section, we prove Theorem 2.4 for rational $\beta\in(1,2]$ only.
We will start by introducing a new dynamical system which realizes a
$\beta$-expansion whose algorithmic complexity is controlled. The proof for
general computable $\beta\in(1,2]$ relies on very similar arguments, but
require much more complex technical details. We present it in the last
section.

##  3 A new $\beta$-map

Inspired by the dynamical system realization of the greedy map and the lazy
map described in Section 2, we introduce a new dynamical system which
generates chunks of a $\beta$-expansion by reading chunks of the greedy binary
expansion as follows. Let $s\in[0,1]$ and $N\in\mathbf{N}$. This dynamical
system will create an increasing sequence $\Sigma_{i}\in\mathbf{N}$ and we
will convert ${\bf g}_{2}(s)_{1:\Sigma_{i}}$ to ${\bf x}_{\beta}(s)_{1:Ni}$,
for $i\in\mathbf{N}$, where ${\bf x}_{\beta}(s)\in\Sigma_{\beta}(s)$. This is
illustrated on Figure 1.

${\bf
g}_{2}(s)=\overset{}{01001}|\overset{}{0001}|\overset{}{111}|\overset{}{1001}|\overset{}{000}|\overset{}{1101}|\overset{}{010}|\overset{}{0000}|\overset{}{001}|\overset{}{1000}|\overset{}{011}|\ldots$${\bf
x}_{\beta}(s)=\underset{N}{000100}|\underset{N}{101000}|\underset{N}{001000}|\underset{N}{101000}|\underset{N}{100000}|\underset{N}{101000}|\underset{N}{100000}|\underset{N}{100000}|\underset{N}{100000}|\underset{N}{010001}|\underset{N}{000010}|\ldots$
Figure 1: Principle of conversion from the greedy binary expansion ${\bf
g}_{2}(s)$ to a $\beta$-expansion ${\bf x}_{\beta}(s)$ with similar
algorithmic complexity.

The sequence $(M_{i})\in\mathbf{N}$ on Figure 1 denotes the size of the
respective chunks of greedy binary expansion used to generate the
corresponding chunks of size $N\in\mathbf{N}$ of the $\beta$-expansion ${\bf
x}_{\beta}(s)$. Note that we have the relation
$\Sigma_{i}=\sum_{k=0}^{i}M_{k}$, for all $i\in\mathbf{N}_{0}$. We will define
$M_{i}$ such that
$\underset{i\to\infty}{\lim}\frac{\Sigma_{i}}{Ni}=\log_{2}(\beta)$, leading to
(48) for $\beta\in\mathbf{Q}$, because we can explicitely define an effective
algorithm to compute the first $Ni$ bits of ${\bf x}_{\beta}(s)$ on input
${\bf g}_{2}(s)_{1:\Sigma_{i}}$.

Note that this vision of a dynamical system operating on the bits of
$\beta$-expansions is not new. For instance, the greedy map can also be seen
as performing actions on bits. Specifically, for a given $s\in[0,1]$, denote
its greedy expansion by ${\bf x}$. Then, one has

$s^{\prime}=G_{\beta}(s)=G_{\beta}\left(\sum_{i=1}^{\infty}{\bf
x}_{i}\beta^{-i}\right)=\beta\left(\sum_{i=1}^{\infty}{\bf
x}_{i}\beta^{-i}\right)-{\bf x}_{1}=\sum_{i=1}^{\infty}{\bf
x}_{i+1}\beta^{-i}.$ (49)

Therefore, $s^{\prime}$ has exactly the same greedy $\beta$-expansion as $s$,
but shifted of one bit to the left. Moreover, we can also see the greedy map
as a way to extract the first bit of the greedy $\beta$-expansion of $s$, as

$s-\frac{1}{\beta}G_{\beta}(s)=\sum_{i=1}^{\infty}{\bf
x}_{i}\beta^{-i}-\frac{1}{\beta}\sum_{i=1}^{\infty}{\bf
x}_{i+1}\beta^{-i}=\frac{{\bf x}_{1}}{\beta}.$ (50)

Further, iterating $n$ times the greedy map on a given $s$ outputs
$s^{\prime}$, having the same greedy $\beta$-expansion as $s$, but shifted $n$
times to the left, precisely

$s^{\prime}=G^{n}_{\beta}(s)=\sum_{i=1}^{\infty}{\bf x}_{i+n}\beta^{-i}.$ (51)

Finally, we can also see the $n$ first iterates of greedy map as a way to
extract the first $n$ bits of the greedy $\beta$-expansion of $s$, as

$s-\frac{1}{\beta^{n}}G_{\beta}(s)=\sum_{i=1}^{\infty}{\bf
x}_{i}\beta^{-i}-\frac{1}{\beta^{n}}\sum_{i=1}^{\infty}{\bf
x}_{i+n}\beta^{-i}=\sum_{i=1}^{n}{\bf x}_{i}\beta^{-i}=\delta_{\beta}({\bf
x}_{1:n}).$ (52)

In contrast to the greedy map, the new dynamical system we will build is
nonstationary. Specifically, the new map will depend on an extra time
parameter $i\in\mathbf{N}$. We first introduce the dynamical system, then
prove that it produces a valid $\beta$-expansion, and finally study the
algorithmic complexity of the resulting $\beta$-expansions.

###  3.1 The dynamical system

Fix $\beta\in(1,2)$. We start by specifying the evolution equations of the new
system and then explain the underlying ideas. We define the dynamical system
$\mathcal{D}_{\beta}$ as the following pair.

$\mathcal{D}_{\beta}:=\left(N,(\Sigma_{i})_{i\in\mathbf{N}_{0}}\right),$ (53)

where $N,\Sigma_{i}\in\mathbf{N}$, for all $i\in\mathbf{N}$, and
$\Sigma_{0}=0$. For $s\in[0,1]$, the realization of $\mathcal{D}_{\beta}$ on
$s$, denoted by $\mathcal{D}_{\beta}(s)$, is defined as the triplet

$\mathcal{D}_{\beta}(s):=\left(X_{i},S_{i},R_{i}\right)_{i\in\mathbf{N}_{0}}\in\\{0,1\\}^{\ast}\times[0,1]\times
I_{\beta},$ (54)

satisfying

$\begin{cases}(X_{0},S_{0},R_{0})=\left(\epsilon,s,0\right),\\\
(X_{i+1},S_{i+1},R_{i+1})=f_{\beta}(X_{i},S_{i},R_{i},i),\ \ \ \text{for}\
i\in\mathbf{N}_{0},\end{cases}$ (55)

with

$f_{\beta}(X,S,R,i)=\left(X{\bf g}_{\beta}(R^{\prime})_{1:N},\
G_{2}^{M_{i}}(S),\ G_{\beta}^{N}(R^{\prime})\right),$ (56)

where $R^{\prime}:=R+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}$, and
$S^{\prime}:=S-\frac{1}{2^{M_{i}}}G_{2}^{M_{i}}(S)$, and
$(M_{i})_{i\in\mathbf{N}_{0}}\in\mathbf{N}$ satisfies

$M_{i}:=\Sigma_{i+1}-\Sigma_{i},\ \text{for all}\ i\in\mathbf{N}_{0}.$ (57)

We define the auxiliary sequences

$\begin{array}[]{ll}S^{\prime}_{i}&:=S_{i}-\frac{1}{2^{M_{i}}}G_{2}^{M_{i}}(S_{i})\\\
R^{\prime}_{i}&:=R_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i},\end{array}\
\ \ \text{for all}\ i\in\mathbf{N}_{0}.$ (58)

The parameters $N$ and $(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ ensure that the
quantities inside the dynamical system, indeed, stay within the domain of the
system. The desired $\beta$-expansion produced by $\mathcal{D}_{\beta}$ is
obtained from $X_{i}$ according to

${\bf x}_{\beta}(s):=\underset{i\to\infty}{\lim}X_{i},$ (59)

where the limit is defined according to distance $d$ introduced in Definition
A.1.

We turn to the description of the ideas underlying the conception of this
dynamical system.

  1. 1.

$S_{0}=s$, and by (56),
$S_{i}=G_{2}^{\sum_{j=0}^{i-1}M_{j}}(S_{0})=G_{2}^{\Sigma_{i}}(s)$, for all
$i\in\mathbf{N}$. By the interpretation of $G_{2}$ in terms of bitshifts of
the greedy binary expansion exposed in (51), $S_{i}$ encodes the greedy binary
expansion of $x$, to which we have removed the first
$\Sigma_{i}=\sum_{j=0}^{i-1}M_{j}$ bits. On Figure 1, $S_{i}$ acts as a
pointer which points to the beginning of the chunk of size $M_{i}$ of the
greedy binary expansion of $s$.

  2. 2.

By (58), $S^{\prime}_{i}=S_{i}-\frac{1}{2^{M_{i}}}G_{2}^{M_{i}}(S_{i})$. By
the interpretation of the greedy map in terms of bitshifts presented in (52),
$S^{\prime}_{i}$ encodes the first $M_{i}$ bits of the greedy binary expansion
of $S_{i}$. As we have shown above that $S_{i}$ acts as a pointer which points
to the beginning of the chunk of size $M_{i}$ of the greedy binary expansion
of $s$, we deduce that $S^{\prime}_{i}$ encodes the bits of the chunk of size
$M_{i}$, as pointed out on Figure 1.

  3. 3.

$R_{i}$ and $R^{\prime}_{i}$ are to be considered together. $R^{\prime}_{i}$
is a variable which controls the generation of $i$-th chunk of size $N$ of the
$\beta$-expansion. As by (56), $R_{i+1}=G_{\beta}^{N}(R^{\prime}_{i})$, then,
by the interpretation of the greedy map in terms of bitshifts presented in
(51), $R_{i}$ encodes the first $Ni$ bits of the $\beta$-expansion generated
by the dynamical system.
$R^{\prime}_{i}=X_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}$ hence
encodes a combination of the first $Ni$ bits of the $\beta$-expansion and of
the bits in the chunk of size $M_{i}$ of the binary expansion. The term
$\frac{\beta^{Ni}}{2^{\Sigma_{i}}}$ is here to control an error introduced by
the dynamical system, that we need to make converge to zero so to ensure that
the system generates a valid $\beta$-expansion of $s$.

We are now ready to prove that the dynamical system $\mathcal{D}_{\beta}$,
under suitable choices of the parameters $N$ and
$(\Sigma_{i})_{i\in\mathbf{N}_{0}}$, produces a $\beta$-expansion.

###  3.2 $\mathcal{D}_{\beta}$ produces a valid $\beta$-expansion

In this paragraph, we fix a $\beta\in(1,2)$, and we find a set of sufficient
conditions, denoted by $(\mathbf{H})$, under which $\mathcal{D}_{\beta}$ is
well-defined. We then show that under $(\mathbf{H})$, $\mathcal{D}_{\beta}$
indeed generates a valid $\beta$-expansion.

We start by constructing $(\mathbf{H})$. $\mathcal{D}_{\beta}$ is defined if
and only if $R^{\prime}_{i}\in\left[0,\frac{1}{\beta-1}\right]$, for
$i\in\mathbf{N}_{0}$. Indeed, if $R^{\prime}_{i}\notin I_{\beta}$ for a given
$i\in\mathbf{N}_{0}$, then neither ${\bf g}_{\beta}$ nor $G_{\beta}$ are not
defined in $R^{\prime}_{i}$, so the definition of $f_{\beta}$ in (56) makes no
sense. $(\mathbf{H})$ will consist of sufficient conditions on $N$ and
$(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ to ensure that
$R^{\prime}_{i}\in\left[0,\frac{1}{\beta-1}\right]$ for all $i\in\mathbf{N}$.

Specifically, we show that for $0<\delta<2-\beta$, we can tune $N$ and
$(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ so that both $R_{i}\in[0,1]$ and
$R^{\prime}_{i}\in\left[0,\frac{1-\delta}{\beta-1}\right)\subset I_{\beta}$,
for all $i\in\mathbf{N}_{0}$, thereby satisfying the necessary condition
$R^{\prime}_{i}\in I_{\beta}$ stated above. These choices of $N$ and
$(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ are informed by using an induction
principle as follows.

  1. 1.

As a base case, we show that $R_{0}\in[0,1]$.

  2. 2.

As per induction step, we show that $R_{i}\in[0,1]$ implies both
$R^{\prime}_{i}\in\left[0,\frac{1-\delta}{\beta-1}\right)$ and
$R_{i+1}\in[0,1]$.

For the base case, we need to prove that $R_{0}\in[0,1]$, which immediately
follows from $R_{0}\overset{(\ref{eq:definition of the dynamical
system})}{=}0$.

Now, as per induction step, suppose that, for a given $i\in\mathbf{N}_{0}$,
$R_{i}\in[0,1]$. We find sufficient conditions on $N$ and $\Sigma_{i}$ such
that $R^{\prime}_{i}\in\left[0,\frac{1-\delta}{\beta-1}\right)$ and
$R_{i+1}\in[0,1]$.

  1. (a)

We start by finding a condition $\Sigma_{i}$ so that
$R^{\prime}_{i+1}\in\left[0,\frac{1-\delta}{\beta-1}\right)$. First,

$\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\leq
R_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\overset{(\ref{eq:definition
of K beta})}{=}R^{\prime}_{i}\overset{(\ref{eq:definition of K
beta})}{=}R_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\leq
1+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}.$ (60)

Note that

$\displaystyle S^{\prime}_{i}$ $\displaystyle\overset{(\ref{eq:definition of K
beta})}{=}S_{i}-\frac{1}{2^{M_{i}}}G_{2}^{M_{i}}(S_{i})\overset{(\ref{eq:n
iterations of greedy map is same as reading the first n
bits})}{=}\sum_{k=1}^{M_{i}}{\bf g}_{2}(S_{i})_{k}\times 2^{-k}\in[0,1].$ (61)

It follows that

$0\overset{(\ref{eq:encadrement of
[0,1]})}{\leq}\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\overset{(\ref{eq:first
encadrement of Z_i})}{\leq}R^{\prime}_{i}\overset{(\ref{eq:first encadrement
of
Z_i})}{\leq}1+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\overset{(\ref{eq:encadrement
of [0,1]})}{\leq}1+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}\cdot$ (62)

Then, to satisfy $R^{\prime}_{i}\in\left[0,\frac{1-\delta}{\beta-1}\right)$,
it is sufficient so set $\Sigma_{i}$ such that

$1+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}\leq\frac{1-\delta}{\beta-1}\Leftrightarrow\Sigma_{i}\geq
Ni\log_{2}(\beta)-\log_{2}\left(\frac{2-\beta-\delta}{\beta-1}\right).$ (63)

  2. (b)

We now find a sufficient condition on $N$ only so that $R_{i+1}\in[0,1]$. By
Lemma A.5,

$G_{\beta}^{n}\left(R^{\prime}_{i}\right)\in[0,1]$ (64)

for all

$n\geq-\log_{\beta}\left(\frac{1-(\beta-1)R^{\prime}_{i}}{2-\beta}\right).$
(65)

Then,

$N\geq-\log_{\beta}\left(\frac{1-(\beta-1)R^{\prime}_{i}}{2-\beta}\right)\Rightarrow
R_{i+1}\overset{(\ref{eq:definition of K
beta})}{=}G_{\beta}^{N}\left(R^{\prime}_{i}\right)\in[0,1].$ (66)

As $R^{\prime}_{i}\leq\frac{1-\delta}{\beta-1}$, we deduce a condition on $N$
which does not depend on $i$:

$N\geq-\log_{\beta}\left(\frac{\delta}{2-\beta}\right).$ (67)

As a conclusion, we say that, for $\delta\in(0,2-\beta)$,
$\mathcal{D}_{\beta}$ satisfies $(\mathbf{H}_{\delta})$ if

$\begin{split}N&\overset{(\ref{eq:condition on N induction
step})}{\geq}-\log_{\beta}\left(\frac{\delta}{2-\beta}\right),\\\
\Sigma_{i}&\overset{(\ref{eq:condition on Sigma_i induction
step})}{\geq}Ni\log_{2}(\beta)-\log_{2}\left(\frac{2-\beta-\delta}{\beta-1}\right),\
\text{for all}\ i\in\mathbf{N}.\end{split}$ ($\mathbf{H}_{\delta}$)

We say that $\mathcal{D}_{\beta}$ satisfies $(\mathbf{H})$ if there exists
$\delta\in(0,2-\beta)$ such that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H}_{\delta})$. We summarize the above discussion with the following
Lemma.

######  Lemma 3.1.

Let $\beta\in(1,2)$, and suppose that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H})$. Then,

$R^{\prime}_{i}\in\left[0,\frac{1}{\beta-1}\right],\ \text{and}\
R_{i}\in[0,1],\ \forall i\in\mathbf{N}_{0}.$ (68)

We now prove if $\mathcal{D}_{\beta}$ satisfies $(\mathbf{H})$, it indeed
generates a valid $\beta$-expansion.

######  Theorem 3.2.

Let $\beta\in(1,2)$, and suppose that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H})$. Then,

${\bf x}_{\beta}(s)\in\Sigma_{\beta}(s),\ \text{for all}\ s\in[0,1].$ (69)

###### Proof.

Let $\beta\in(1,2)$, and suppose that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H})$. Let $s\in[0,1]$. To prove that ${\bf
x}_{\beta}(s)\in\Sigma_{\beta}(x)$, we need to show that $\delta_{\beta}({\bf
x}_{\beta}(s))=s$. Consider the sequence $(X_{n})_{n\in\mathbf{N}}$ generated
by $\mathcal{D}_{\beta}$. By (59), $\underset{n\to\infty}{\lim}X_{n}={\bf
x}_{\beta}(s)$, where the limit is defined according to distance $d$
introduced in Definition A.1. As by Lemma A.2, $\delta_{\beta}$ is continuous
as a mapping from $\left(\\{0,1\\}^{\omega},d\right)$ to
$(\mathbf{R},|\cdot|)$, $\left(\delta_{\beta}(X_{n})\right)_{\mathbf{N}_{2}}$
therefore converges to $\delta_{\beta}({\bf x}_{\beta}(x))$. We now show that
$\left(\delta_{\beta}(X_{n})\right)_{\mathbf{N}_{2}}$ converges to $x$, which
allows us to conclude that $s=\delta_{\beta}({\bf x}_{\beta}(s))$, and hence
that $\delta_{\beta}({\bf x}_{\beta}(s))\in\Sigma_{\beta}(s)$. Fix
$n\in\mathbf{N}$. Note that by (56), $X_{n+1}=X_{n}{\bf
g}_{\beta}(R^{\prime}_{n})_{1:N}$. By repeating this argument, one has

$X_{n+1}=X_{0}\coprod_{i=0}^{n}{\bf
g}_{\beta}(R^{\prime}_{i})_{1:N}\overset{(\ref{eq:definition of the dynamical
system})}{=}\coprod_{i=0}^{n}{\bf g}_{\beta}(R^{\prime}_{i})_{1:N}.$ (70)

It follows that

$\displaystyle\delta_{\beta}(X_{n+1})$ $\displaystyle\overset{(\ref{eq:B_n as
concatenation of greedy Z i})}{=}\delta_{\beta}\left(\coprod_{i=0}^{n}{\bf
g}_{\beta}(R^{\prime}_{i})_{1:N}\right)\overset{\ref{lem:factorisation of beta
expansion through concatenation}}{=}\delta_{\beta}\left({\bf
g}_{\beta}(R^{\prime}_{0})_{1:N}\right)+\sum_{i=1}^{n}\beta^{-Ni}\delta_{\beta}\left({\bf
g}_{\beta}(R^{\prime}_{i})_{1:N}\right)$ (71)
$\displaystyle=\sum_{i=0}^{n}\beta^{-Ni}\delta_{\beta}\left({\bf
g}_{\beta}(R^{\prime}_{i})_{1:N}\right)\overset{(\ref{eq:n iterations of
greedy map is same as reading the first n
bits})}{=}\sum_{i=0}^{n}\beta^{-Ni}\left(R^{\prime}_{i}-\frac{1}{\beta^{N}}G_{\beta}^{N}(R^{\prime}_{i})\right)$
(72) $\displaystyle\overset{(\ref{eq:definition of K
beta})}{=}\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}-\frac{1}{\beta^{N}}G_{\beta}^{N}(R^{\prime}_{i})\right)$
(73) $\displaystyle\overset{(\ref{eq:definition of K
beta})}{=}\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}-\frac{1}{\beta^{N}}R_{i+1}\right).$
(74)

Note that

$\displaystyle S^{\prime}_{i}$ $\displaystyle\overset{(\ref{eq:definition
auxiliary sequences})}{=}S_{i}-G_{2}^{M_{i}}(S_{i})\overset{(\ref{eq:n
iterations of greedy map is same as reading the first n
bits})}{=}\delta_{2}\left({\bf
g}_{2}(S_{i})\right)\overset{(\ref{eq:definition of K
beta})}{=}\delta_{2}\left({\bf
g}_{2}\left(G_{2}^{\Sigma_{i}}(S_{0})\right)_{1:M_{i}}\right)$ (75)
$\displaystyle\overset{(\ref{eq:n iterations of greedy map is same as shifting
n bits})}{=}\delta_{2}\left({\bf
g}_{2}(S_{0})_{\Sigma_{i}+1:\Sigma_{i}+M_{i}}\right)\overset{(\ref{eq:definition
of Sigma as the sum of M})}{=}\delta_{2}\left({\bf
g}_{2}(S_{0})_{\Sigma_{i}+1:\Sigma_{i+1}}\right)\overset{(\ref{eq:definition
of the dynamical system})}{=}\delta_{2}\left({\bf
g}_{2}(s)_{\Sigma_{i}+1:\Sigma_{i+1}}\right).$ (76)

Then,

$\displaystyle\delta_{\beta}(X_{n+1})$ $\displaystyle\overset{(\ref{eq:first
simplification of delta
beta})}{=}\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}-\frac{1}{\beta^{N}}R_{i+1}\right)$
(77) $\displaystyle\overset{(\ref{eq:W_i equivalent to delta of greedy
binary})}{=}\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}+\frac{\beta^{Ni}}{2^{\Sigma_{i}}}\delta_{2}\left({\bf
g}_{2}(s)_{\Sigma_{i}+1:\Sigma_{i+1}}\right)-\frac{1}{\beta^{N}}R_{i+1}\right)$
(78)
$\displaystyle=\sum_{i=0}^{n}\beta^{-Ni}\frac{\beta^{Ni}}{2^{\Sigma_{i}}}\delta_{2}\left({\bf
g}_{2}(s)_{\Sigma_{i}+1:\Sigma_{i+1}}\right)+\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}-\frac{1}{\beta^{N}}R_{i+1}\right)$
(79) $\displaystyle=\sum_{i=0}^{n}\frac{1}{2^{\Sigma_{i}}}\delta_{2}\left({\bf
g}_{2}(s)_{\Sigma_{i}+1:\Sigma_{i+1}}\right)+\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}-\frac{1}{\beta^{N}}R_{i+1}\right)$
(80) $\displaystyle=\delta_{2}\left({\bf
g}_{2}(s)_{1:\Sigma_{1}}\right)+\sum_{i=1}^{n}\frac{1}{2^{\Sigma_{i}}}\delta_{2}\left({\bf
g}_{2}(x)_{\Sigma_{i}+1:\Sigma_{i+1}}\right)+\sum_{i=0}^{n}\beta^{-Ni}\left(X_{i}-\frac{1}{\beta^{N}}R_{i+1}\right)$
(81) $\displaystyle\overset{\ref{lem:factorisation of beta expansion through
concatenation}}{=}\delta_{2}({\bf
g}_{2}(s)_{1:\Sigma_{n}})+R_{0}-\beta^{N(n+1)}R_{n+1}$ (82)
$\displaystyle\overset{(\ref{eq:definition of the dynamical
system})}{=}\delta_{2}({\bf g}_{2}(s)_{1:\Sigma_{n}})-\beta^{-N(n+1)}R_{n+1}.$
(83)

$\mathcal{D}_{\beta}$ satisfies $(\mathbf{H})$, so $\Sigma_{n}\geq
Nn\log_{2}(\beta)$, and hence $\underset{n\to\infty}{\lim}\Sigma_{n}=\infty$.
By continuity of $\delta_{2}$,

$\displaystyle\underset{n\to\infty}{\lim}\delta_{2}({\bf
g}_{2}(s)_{1:\Sigma_{n}})$
$\displaystyle=\delta_{2}\left(\underset{n\to\infty}{\lim}{\bf
g}_{2}(s)_{1:\Sigma_{n}}\right)=\delta_{2}({\bf
g}_{2}(s)_{1:\infty})=\delta_{2}({\bf g}_{2}(s))=s.$ (84)

Moreover, as by Lemma 3.1, $R_{i}\in[0,1]$ for all $i\in\mathbf{N}_{0}$, one
has

$\underset{n\to\infty}{\lim}\beta^{-N(n+1)}R_{n+1}=0.$ (85)

By (83), one has

$\underset{n\to\infty}{\lim}\delta_{\beta}(X_{n+1})=\underset{n\to\infty}{\lim}\delta_{2}({\bf
g}_{2}(s)_{1:\Sigma_{n}})+\underset{n\to\infty}{\lim}\beta^{-N(n+1)}R_{n+1}\overset{(\ref{eq:
one term converges to x})(\ref{eq:error converging to 0})}{=}s,$ (86)

thereby finishing the proof. ∎

###  3.3 Algorithmic complexity of the $\beta$-expansion generated by
$\mathcal{D}_{\beta}$

Having established that $\beta\in(1,2)$ and $x\in[0,1]$, ${\bf x}_{\beta}(s)$
constitutes a valid $\beta$-expansion under condition $(\mathbf{H})$, it
remains to show that the algorithmic complexity of the prefixes of ${\bf
x}_{\beta}(s)$ can inferred from the algorithmic complexity of the prefixes of
the greedy expansion ${\bf g}_{2}(s)$. However, the dynamical system
$\mathcal{D}_{\beta}$ allows to establish such a statement for
$\beta\in(1,2)\cap\mathbf{Q}$ only (while the definition of
$\mathcal{D}_{\beta}$ can be effected for any $\beta\in(1,2)$): as $\beta$ is
used explicitely in the formulas underlying $\mathcal{D}_{\beta}$, one cannot
simulate $\mathcal{D}_{\beta}$ with an effective algorithm for general
$\beta\in(1,2)$. Instead, we would need another dynamical system which cope
with approximations of $\beta$ only. We develop this dynamical system in the
next section. In this paragraph, we conclude the proof of Lemma 2.3, which
establishes a relationship between the algorithmic complexity of the
respective prefixes of ${\bf x}_{\beta}(s)$ and ${\bf g}_{2}(s)$,
respectively, for $\beta\in(1,2)\cap\mathbf{Q}$ only.

From now on, we say that $\mathcal{D}_{\beta}$ is effective if there exists an
effective algorithm which can, on input $n$, outputs $\Sigma_{n}$, for all
$n\in\mathbf{N}$.

######  Lemma 3.3.

Let $\beta\in(1,2)\cap\mathbf{Q}$, $s\in[0,1]$, let $\mathcal{D}_{\beta}$ be
effective, and suppose that there exists $\delta\in(0,2-\beta)\cap\mathbf{Q}$
such that $\mathcal{D}_{\beta}$ satisfies ($\mathbf{H}_{\delta}$). Then, there
exists $c_{\beta}>0$ depending only on $\mathcal{D}_{\beta}$, such that

$K[{\bf x}_{\beta}(s)|Nn]\leq K[{\bf g}_{2}(s)|\Sigma_{n}]+c,\ \ \text{for
all}\ n\in\mathbf{N}.$ (87)

###### Proof.

Let $\beta\in(1,2)\cap\mathbf{Q}$, $s\in[0,1]$, let $\mathcal{D}_{\beta}$ be
effective, and suppose that there exists $\delta\in(0,2-\beta)\cap\mathbf{Q}$
such that $\mathcal{D}_{\beta}$ satisfies ($\mathbf{H}_{\delta}$). We design
an effective algorithm $\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$ such that

${\bf x}_{\beta}(s)_{1:Nn}=\varphi({\bf g}_{2}(s)_{1:\Sigma_{n}}),\ \
\text{for all}\ n\in\mathbf{N}_{0}.$ (88)

Let $n\in\mathbf{N}$. Concretely, on input ${\bf g}_{2}(s)_{1:\Sigma_{n}}$,
$\varphi$ first uses $\Sigma_{n}$ to compute $n$ (this operation can be done
because $\mathcal{D}_{\beta}$ is effective). Further, $\varphi$ computes $n$
iterations of the dynamical system $\mathcal{D}_{\beta}$, and records the
successive values $Z_{0},\ldots,Z_{n}$. Finally, it generates ${\bf
x}_{\beta}(s)_{1:Nn}$ through the equation

${\bf x}_{\beta}(s)_{1:Nn}:=\coprod_{i=0}^{n-1}{\bf
g}_{\beta}(R^{\prime}_{i})_{1:N}.$ (89)

Note that as $\beta\in\mathbf{Q}$, all the variables involved in the evolution
of $\mathcal{D}_{\beta}$ are rational numbers, and all the operations
underlying this evolution can be run on a digital computer, as they can be
reduced to additions and multiplications only. So $\varphi$ is indeed an
effective algorithm. By Lemma 1.1, there exists $c>0$, depending only on
$\varphi$ and a fortiori only on $\mathcal{D}_{\beta}$, such that

$K[{\bf x}_{\beta}(s)|Nn]\leq K[{\bf g}_{2}(s)|\Sigma_{n}]+c,\ \ \text{for
all}\ n\in\mathbf{N}.$ (90)

∎

######  Corollary 3.4.

Let $\beta\in(1,2)\cap\mathbf{Q}$, $s\in[0,1]$. Then, there exists $\hat{\bf
x}_{\beta}\in\Sigma_{\beta}(s)$, and $c_{\beta}>0$ depending only on $\beta$,
such that

$K[\hat{\bf x}_{\beta}|n]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+c_{\beta},\ \text{for all}\ n\in\mathbf{N}.$ (91)

###### Proof.

Let $\beta\in(1,2)\cap\mathbf{Q}$, $s\in[0,1]$. Let
$\delta\in(0,2-\beta)\cap\mathbf{Q}$, and let $\mathcal{D}_{\beta}$ be the
dynamical system defined as in (55), such that

$\begin{split}N&=\left\lceil-\log_{\beta}\left(\frac{\delta}{2-\beta}\right)\right\rceil,\\\
\Sigma_{i}&=\left\lceil
Ni\log_{2}(\beta)-\log_{2}\left(\frac{2-\beta-\delta}{\beta-1}\right)\right\rceil,\
\text{for all}\ i\in\mathbf{N}.\end{split}$ (92)

Obviously, $\mathcal{D}_{\beta}$ satisfies ($\mathbf{H}_{\delta}$), where
$\delta\in\mathbf{Q}$, so by Lemma 3.3, there exists $c>0$ such that

$K[{\bf x}_{\beta}(s)|Nn]\leq K[{\bf g}_{2}(s)|\Sigma_{n}]+c,\ \ \text{for
all}\ n\in\mathbf{N}.$ (93)

Note that by (255), there exists $C>0$ such that

$K[{\bf x}_{\beta}(s)|n]\leq K[{\bf g}_{2}(s)|\Sigma_{\lfloor
n/N\rfloor}]+c+C,\ \ \text{for all}\ n\in\mathbf{N}.$ (94)

Moreover, by setting
$M:=1+N\log_{2}(\beta)+\left|\log_{2}\left(\frac{2-\beta-\delta}{\beta-1}\right)\right|$,
(92) yields

$\lceil n\log_{2}(\beta)\rceil-M\leq\Sigma_{\lfloor n/N\rfloor}\leq\lceil
n\log_{2}(\beta)\rceil+M,\ \text{ for all }\ n\in\mathbf{N}.$ (95)

Then, by Lemma C.7, there exists $C^{\prime}>0$ such that

$K[{\bf g}_{2}(s)|\Sigma_{\lfloor n/N\rfloor}]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+C^{\prime},\ \text{for all}\ n\in\mathbf{N}.$ (96)

By combining (94) and (96), one has

$K[{\bf x}_{\beta}(s)|n]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+C^{\prime}+C+c,\ \text{for all}\ n\in\mathbf{N},$ (97)

thereby finishing the proof by letting $\hat{\bf x}_{\beta}={\bf
x}_{\beta}(s)$. ∎

We have proven that for every $s\in[0,1]$, there exists a $\beta$-expansion
which algorithmic complexity of prefixes is upper bounded a very simple manner
by a relation involving the algorithmic complexity of the prefixes of the
binary expansion, for every $\beta\in\mathbf{Q}\cap(1,2)$. In the next
section, we modify slighly the dynamical system $\mathcal{D}_{\beta}$ to come
up with a new relationship, which holds for general $\beta\in(1,2)$.

##  4 Extended $\beta$-map

Inspired from the considerations which applied for the simpler case
$\beta\in\mathbf{Q}\cap(1,2)$, we introduce a another dynamical system which
also generates chunks of a $\beta$-expansion by reading chunks of the greedy
binary expansion as on Figure 1. Although, the link between ${\bf g}_{2}(s)$
and $\hat{\bf x}_{\beta}(s)$ will quite more complex than in previous section.
We will again define $M_{i}$ such that
$\underset{i\to\infty}{\lim}\frac{\Sigma_{i}}{Ni}=\log_{2}(\beta)$, leading to
(48) for $\beta\in(1,2)$. The dynamical system that we introduce in this
section uses approximations of $\beta$ only, to that an effective algorithm
can simulate it, even if $\beta$ is not a rational number. Specifically, we
will manipulate sequences of the following form:

$q_{i}:=1+\delta_{2}({\bf g}_{2}(\beta-1)_{1:L+Ni}),\ \text{for all}\
i\in\mathbf{N}_{0},$ (98)

where $L,N\in\mathbf{N}$ are parameter of the sequence
$(q_{i})_{i\in\mathbf{N}_{0}}$. For a given sequence
$(q_{i})_{i\in\mathbf{N}_{0}}$ of approximations of $\beta$, we also introduce
two other sequences $(\chi_{n})_{n\in\mathbf{N}_{0}}$ and
$(\xi_{n})_{n\in\mathbf{N}_{0}}$ which turn out to be useful, defined
according to

$\displaystyle\chi_{n}$ $\displaystyle:=\prod_{i=0}^{n}q_{i}$ (99)
$\displaystyle\xi_{n}$ $\displaystyle:=\frac{1}{q_{n}^{n+1}}\chi_{n},$ (100)

for all $n\in\mathbf{N}_{0}$.

As in previous section, we first introduce the dynamical system, then prove
that it produces a valid $\beta$-expansion, and finally study the algorithmic
complexity of the resulting $\beta$-expansions.

###  4.1 The dynamical system

Fix $\beta\in(1,2)$. We start by specifying the evolution equations of the new
system and then explain the underlying ideas. We define the dynamical system
$\mathcal{D}_{\beta}$ as the following triplet.

$\mathcal{D}_{\beta}:=\left(L,N,(\Sigma_{i})_{i\in\mathbf{N}_{0}}\right),$
(101)

where $L,N,\Sigma_{i}\in\mathbf{N}$, for all $i\in\mathbf{N}$, and
$\Sigma_{0}=0$. For $s\in[0,1]$, the realization of $\mathcal{D}_{\beta}$ on
$s$, denoted by $\mathcal{D}_{\beta}(s)$, is defined as the triplet

$\mathcal{D}_{\beta}(s):=\left(X_{i}(s),S_{i}(s),R_{i}(s)\right)_{i\in\mathbf{N}_{0}}\in\\{0,1\\}^{\ast}\times[0,1]\times
I_{\beta},$ (102)

where the values of $X_{i}(s),S_{i}(s),R_{i}(s)$ are to be define below. When
the context is clear, we write $X_{i},S_{i},R_{i}$ instead of the more tedious
$X_{i}(s),S_{i}(s),R_{i}(s)$. For $s\in[0,1]$, we set

$\begin{cases}(X_{0},Y_{0},X_{0})=\left(\epsilon,s,0\right),\\\
(X_{i+1},S_{i+1},R_{i+1})=f_{\beta}(X_{i},S_{i},R_{i},i),\ \ \ \text{for}\
i\in\mathbf{N}_{0},\end{cases}$ (103)

with

$f_{\beta}(X,S,R,i)=\left(X{\bf g}_{q_{i}}(R^{\prime})_{1:N},\
G_{2}^{M_{i}}(S),\
q_{i}^{N}\left(1-\xi_{i}^{N}\right)R+\xi_{i}^{N}G_{q_{i}}^{N}(R^{\prime})\right),$
(104)

where

$\displaystyle S^{\prime}$
$\displaystyle:=S-\frac{1}{2^{M_{i}}}G_{2}^{M_{i}}(S),$ (105) $\displaystyle
R^{\prime}$
$\displaystyle:=R+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}+\begin{cases}0,\hskip
116.65646pt\text{if}\ i=0,\\\
q_{i}^{Ni}\left(\delta_{q_{i-1}}(X)-\delta_{q_{i}}(X)\right),\ \text{if}\
i\neq 0,\end{cases}$ (106) $\displaystyle M_{i}$
$\displaystyle:=\Sigma_{i+1}-\Sigma_{i}$ (107) $\displaystyle q_{i}$
$\displaystyle:=1+\delta_{2}({\bf g}_{2}(\beta-1)_{1:L+Ni}),$ (108)
$\displaystyle\xi_{i}$
$\displaystyle:=\frac{1}{q_{i}^{i+1}}\prod_{j=0}^{i}q_{j},$ (109)

for all $i\in\mathbf{N}_{0}$. For $s\in[0,1]$, we next define the auxiliary
sequences $S^{\prime}_{i}(s),R^{\prime}_{i}(s)$. Owing to the clarity of the
context, we write $S^{\prime}_{i},R^{\prime}_{i}$ instead of
$S^{\prime}_{i}(s),R^{\prime}_{i}(s)$, and we set

$\begin{array}[]{ll}S^{\prime}_{i}&:=S_{i}-\frac{1}{2^{M_{i}}}G_{2}^{M_{i}}(S_{i})\\\
R^{\prime}_{i}&:=R_{i}+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}+\begin{cases}0,\hskip
122.9161pt\text{if}\ i=0,\\\
q_{i}^{Ni}\left(\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})\right),\
\text{if}\ i\neq 0,\end{cases}\end{array}\ \forall i\in\mathbf{N}_{0},$ (110)

where the values of $R_{i}$, $S_{i}$ and $X_{i}$ are understood to be
$R_{i}(s)$, $S_{i}(s)$ and $X_{i}(s)$, respectively.

The parameters $L$, $N$ and $(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ ensure that
the quantities inside the dynamical system, indeed, stay within the domain of
the system. The desired $\beta$-expansion produced by $\mathcal{D}_{\beta}$ on
input $s\in[0,1]$ is obtained from $X_{i}(s)$ according to

${\bf x}_{\beta}(s):=\underset{i\to\infty}{\lim}X_{i}(s),$ (111)

where the limit is defined according to distance $d$ introduced in Definition
A.1.

We turn to the description of the ideas underlying the conception of this
dynamical system.

  1. 1.

$(S_{i}(s))_{i\in\mathbf{N}_{0}}$ and
$(S^{\prime}_{i}(s))_{i\in\mathbf{N}_{0}}$ have the exact same expression as
in Section 3, i.e. $S_{i}$ encodes the greedy binary expansion of $s$, to
which we have removed the first $\Sigma_{i}=\sum_{j=0}^{i-1}M_{j}$ bits, and
$S^{\prime}_{i}$ encodes the first $M_{i}$ bits of the greedy binary expansion
of $S_{i}$.

  2. 2.

$(R_{i}(s))_{i\in\mathbf{N}_{0}}$ and
$(R^{\prime}_{i}(s))_{i\in\mathbf{N}_{0}}$ are to be considered together.
$R^{\prime}_{i}$ is a variable which controls the generation of $i$-th chunk
of size $N$ of the $q_{i}$-expansion. As by (56),
$R_{i+1}=q_{i}^{N}\left(1-\xi_{i}^{N}\right)X+\xi_{i}^{N}G_{q_{i}}^{N}(Z)$,
then, by the interpretation of the greedy map in terms of bitshifts presented
in (51), $R_{i}$ encodes the first $Ni$ bits of the $q_{i}$-expansion
generated by the dynamical system.
$R^{\prime}_{i}=R_{i}+q_{i-1}^{Ni}\left(\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})\right)+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}$
hence encodes a combination of the first $Ni$ bits of the $q_{i}$-expansion
and of the bits in the chunk of size $M_{i}$ of the binary expansion through
$R_{i}+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}$. The terms
$\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}$ and
$q_{i-1}^{Ni}\left(\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})\right)$ are
here to control an error introduced by the dynamical system, that we need to
make converge to zero so to ensure that the system generates a valid
$\beta$-expansion of $s$.

We are now ready to prove that the dynamical system $\mathcal{D}_{\beta}$,
under some conditions on $(q_{i})_{i\in\mathbf{N}_{0}}$ suitable choices of
the parameters $L$, $N$ and $(\Sigma_{i})_{i\in\mathbf{N}_{0}}$, produces a
$\beta$-expansion of $s$, for every input $s\in[0,1]$.

###  4.2 $\mathcal{D}_{\beta}$ produces a valid $\beta$-expansion

In this paragraph, we fix a $\beta\in(1,2)$, and we find a set of sufficient
conditions, denoted by $(\mathbf{H}^{\prime})$, under which
$\mathcal{D}_{\beta}(s)$ is well-defined for all $s\in[0,1]$. We then show
that under $(\mathbf{H}^{\prime})$, ${\bf x}_{\beta}(s)$ is a valid
$\beta$-expansion of $s$.

We start by constructing $(\mathbf{H}^{\prime})$. Fix $s\in[0,1]$.
$\mathcal{D}_{\beta}(s)$ is defined if and only if
$R^{\prime}_{i}\in\left[0,\frac{1}{q_{i}-1}\right]$, for $i\in\mathbf{N}_{0}$.
Indeed, if $R^{\prime}_{i}\notin I_{\beta}$ for a given $i\in\mathbf{N}_{0}$,
then neither ${\bf g}_{\beta}$ nor $G_{\beta}$ are not defined at
$R^{\prime}_{i}$, so the definition of $f_{\beta}$ in (104) makes no sense.
$(\mathbf{H}^{\prime})$ will consist of sufficient conditions on $L$, $N$, and
$(\Sigma_{i})_{i\in\mathbf{N}_{0}}$, to ensure that
$R^{\prime}_{i}\in\left[0,\frac{1}{q_{i}-1}\right]$ for all
$i\in\mathbf{N}_{0}$.

Specifically, we show that for $0<\delta<\frac{2-\beta}{\beta}$, we can tune
$L$, $N$ and $(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ so that
$R_{i}\in[0,1+\delta]$ and
$R^{\prime}_{i}\in\left[0,\frac{1-\delta}{q_{i}-1}\right)\subset\left[0,\frac{1}{q_{i}-1}\right]$,
for all $i\in\mathbf{N}_{0}$, thereby satisfying the necessary condition
$R^{\prime}_{i}\in I_{\beta}$ stated above. These choices of $L$, $N$ and
$(\Sigma_{i})_{i\in\mathbf{N}_{0}}$ are informed by using an induction
principle as follows.

  1. 1.

As a base case, we show that $R_{0}\in[0,1+\delta]$.

  2. 2.

As per induction step, we show that $R_{i}\in[0,1+\delta]$ implies both
$R^{\prime}_{i}\in\left[0,\frac{1-\delta}{\beta-1}\right)$ and
$R_{i+1}\in[0,1+\delta]$.

For the base case, we need to prove that $R_{0}\in[0,1+\delta]$, which
immediately follows from $R_{0}\overset{(\ref{eq:definition of the generalized
dynamical system})}{=}0$.

Now, as per induction step, suppose that, for a given $i\in\mathbf{N}_{0}$,
$R_{i}\in[0,1+\delta]$. We find sufficient conditions on $L$, $N$ and
$\Sigma_{i}$ such that
$R^{\prime}_{i}\in\left[0,\frac{1-\delta}{q_{i}-1}\right)$, and
$R_{i+1}\in[0,1]$.

  1. (a)

We start by finding a sufficient condition $\Sigma_{i}$ and $L$ so that
$R^{\prime}_{i}\in\left[0,\frac{1-\delta}{q_{i}-1}\right)$. First note that
obiously $R^{\prime}_{i}\geq 0$. By (110),

$\displaystyle R^{\prime}_{i}\ $
$\displaystyle=R_{i}+q_{i}^{Ni}\left(\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})\right)+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\leq\frac{1-\delta}{q_{i}-1}$
(112) $\displaystyle\overset{(a)}{\Leftarrow}\ $ $\displaystyle
1+\delta+q_{i}^{Ni}\left(\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})\right)+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\leq\frac{1-\delta}{q_{i}-1}$
(113) $\displaystyle\overset{\ref{lem:delta beta lipschitz}}{\Leftarrow}\ $
$\displaystyle
1+\delta+q_{i}^{Ni}\frac{|X_{i}|(|X_{i}|+1)}{2}|q_{i}-q_{i-1}|+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}\leq\frac{1-\delta}{q_{i}-1}$
(114) $\displaystyle\overset{(\ref{eq:encadrement of [0,1]})}{\Leftarrow}\ $
$\displaystyle
1+\delta+q_{i}^{Ni}\frac{|X_{i}|(|X_{i}|+1)}{2}|q_{i}-q_{i-1}|+\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}\leq\frac{1-\delta}{q_{i}-1}$
(115) $\displaystyle\Leftrightarrow\ $
$\displaystyle\frac{|X_{i}|(|X_{i}|+1)}{2}|q_{i}-q_{i-1}|+\frac{1}{2^{\Sigma_{i}}}\leq\frac{1}{q_{i}^{Ni}}\left(\frac{1-\delta}{q_{i}-1}-1-\delta\right)$
(116) $\displaystyle\overset{(b)}{\Leftarrow}\ $
$\displaystyle\frac{|X_{i}|(|X_{i}|+1)}{2}|q_{i}-q_{i-1}|+\frac{1}{2^{\Sigma_{i}}}\leq\frac{1}{q_{i}^{Ni}}\left(\frac{1-\delta}{\beta-1}-1-\delta\right)$
(117) $\displaystyle\Leftrightarrow\ $
$\displaystyle\underset{=:A_{1}}{\underbrace{\frac{|X_{i}|(|X_{i}|+1)}{2}|q_{i}-q_{i-1}|}}+\underset{=:A_{2}}{\underbrace{\frac{1}{2^{\Sigma_{i}}}}}\leq\frac{1}{q_{i}^{Ni}}\underset{=:2C_{\delta,\beta}}{\underbrace{\frac{2-\beta-\delta\beta}{\beta-1}}},$
(118)

where (a) follows from $R_{i}\leq 1+\delta$, (b) is by $q_{i}\leq\beta$. We
arbitrarily choose to tune $|q_{i}-q_{i-1}|$. For (118) to be satisfied, it is
sufficient to have both $A_{1}\leq\frac{1}{q_{i}^{Ni}}C_{\delta,\beta}$ and
$A_{2}\leq\frac{1}{q_{i}^{Ni}}C_{\delta,\beta}$. By identification of $A_{1}$
and $A_{2}$, we have

$\displaystyle\frac{|X_{i}|(|X_{i}|+1)}{2}|q_{i}-q_{i-1}|$
$\displaystyle\leq\frac{1}{q_{i}^{Ni}}C_{\delta,\beta},$ (119)
$\displaystyle\frac{1}{2^{\Sigma_{i}}}$
$\displaystyle\leq\frac{1}{q_{i}^{Ni}}C_{\delta,\beta}.$ (120)

Note that by (104), we have

$X_{i}=X_{i-1}{\bf
g}_{q_{i-1}}\left(R^{\prime}_{i-1}\right)_{1:N}=X_{0}\coprod_{j=0}^{i-1}{\bf
g}_{q_{j}}\left(R^{\prime}_{j}\right)_{1:N}=\coprod_{j=0}^{i-1}{\bf
g}_{q_{j}}\left(R^{\prime}_{j}\right)_{1:N}.$ (121)

Then, $X_{i}$ is the result of the concatenation of $i$ sequences of length
$N$, so it has length $|X_{i}|=Ni$. By using $|X_{i}|=Ni$, (119) and (120), it
follows that

$\displaystyle|q_{i}-q_{i-1}|$
$\displaystyle\leq\frac{1}{q_{i}^{Ni}}\frac{2}{Ni(Ni+1)}C_{\delta,\beta},$
(122) $\displaystyle\Sigma_{i}$ $\displaystyle\geq
Ni\log_{2}(q_{i})-\log_{2}\left(C_{\delta,\beta}\right).$ (123)

We now turn the condition on $|q_{i}-q_{i-1}|$ can be turn into a condition on
$L$. First note that, as $q_{i}\leq\beta$, and $Ni+1\leq 2Ni$ for all
$i\in\mathbf{N}$, (122) holds if

$|q_{i}-q_{i-1}|\leq\frac{1}{\beta^{Ni}}\frac{1}{N^{2}i^{2}}C_{\delta,\beta},$
(124)

Now, remark that

$q_{i}-q_{i-1}\leq 2^{-L-(i-1)N}$ (125)

We let $L=L_{1}+L_{2}$, with $L_{1},L_{2}\in\mathbf{N}$. A sufficient
condition for (124) is

$\displaystyle
2^{-L_{1}-L_{2}-(i-1)N}\leq\frac{1}{\beta^{Ni}}\frac{1}{N^{2}i^{2}}C_{\delta,\beta}$
(126) $\displaystyle\Leftrightarrow$
$\displaystyle\frac{1}{2^{L_{1}}}\frac{1}{2^{L_{2}}}\frac{1}{2^{(i-1)N}}\leq\frac{1}{2^{N(i-1)}}\left(\frac{2}{\beta}\right)^{N(i-1)}\frac{1}{i^{2}}\frac{C_{\delta,\beta}}{N^{2}\beta^{N}}$
(127) $\displaystyle\Leftarrow$
$\displaystyle\frac{1}{2^{L_{1}}}\leq\left(\frac{2}{\beta}\right)^{N(i-1)}\frac{1}{i^{2}}\
\ \text{and}\ \
\frac{1}{2^{L_{2}}}\leq\frac{C_{\delta,\beta}}{N^{2}\beta^{N}}$ (128)
$\displaystyle\overset{(a)}{\Leftarrow}$ $\displaystyle L_{1}\geq C_{N,\beta}\
\ \text{and}\ \
L_{2}\geq-\log_{2}\left(\frac{C_{\delta,\beta}}{N^{2}\beta^{N}}\right),$ (129)

where
$C_{N,\beta}:=N\log_{2}\left(\frac{2}{\beta}\right)+2-2\log_{2}\left(N\log\left(\frac{2}{\beta}\right)\right)$,
and (a) follows from finding the maximum of the function
$t\mapsto\frac{1}{t^{2}}\left(\frac{2}{\beta}\right)^{N(t-1)}$. Overall, if

$L\geq
C_{N,\delta,\beta}:=C_{N,\beta}-\log_{2}\left(\frac{C_{\delta,\beta}}{N^{2}\beta^{N}}\right),$
(130)

then (122) is satisfied. We conclude that if

$\displaystyle L$ $\displaystyle\geq C_{N,\delta,\beta},$ (131)
$\displaystyle\Sigma_{i}$ $\displaystyle\geq
Ni\log_{2}(q_{i})-\log_{2}\left(C_{\delta,\beta}\right),$ (132)

then $R^{\prime}_{i}\in\left[0,\frac{1-\delta}{q_{i}-1}\right)$.

  2. (b)

We now find a sufficient condition on $N$ and another sufficient condition on
$L$ so that $R_{i+1}\in[0,1+\delta]$. $R_{i+1}\geq 0$ is obvious. Further, as

$R_{i+1}\overset{(\ref{eq:definition of generalized K
beta})}{=}q_{i}^{N}\left(1-\xi_{i}^{N}\right)R_{i}+\xi_{i}^{N}G_{q_{i}}^{N}(R^{\prime}_{i}),$
(133)

we first find a sufficient condition on $N$ so that
$G_{q_{i}}^{N}(R^{\prime}_{i})\leq 1$, and then we find a sufficient condition
on $L$ so that $q_{i}^{N}\left(1-\xi_{i}^{N}\right)R_{i}+\xi_{i}^{N}\leq
1+\delta$. By (133), these two conditions taken together yield $R_{i+1}\leq
1+\delta$. We start by finding the condition on $N$ so that
$G_{q_{i}}^{N}(R^{\prime}_{i})\leq 1$. By Lemma A.5,

$G_{q_{i}}^{n}\left(R^{\prime}_{i}\right)\in[0,1]$ (134)

for all

$n\geq-\log_{q_{i}}\left(\frac{1-(q_{i}-1)R^{\prime}_{i}}{2-q_{i}}\right).$
(135)

Then,

$N\geq-\log_{\beta}\left(\frac{1-(q_{i}-1)R^{\prime}_{i}}{2-q_{i}}\right)\Rightarrow
G_{q_{i}}^{N}\left(R^{\prime}_{i}\right)\in[0,1].$ (136)

As per assumption $R^{\prime}_{i}\leq\frac{1-\delta}{q_{i}-1}$, we deduce a
condition on $N$ which does not depend on $R^{\prime}_{i}$:

$N\geq-\log_{q_{i}}\left(\frac{\delta}{2-{q_{i}}}\right)\overset{(a)}{\geq}-\log_{\beta}\left(\frac{\delta}{2-\beta}\right),$
(137)

where (a) is a consequence of $q_{i}\leq\beta$, and of
$t\mapsto-\log_{t}\left(\frac{\delta}{2-t}\right)$ considered as a function
from $(1,\beta]$ to $\mathbf{R}$ being decreasing (see Lemma C.1).

We now assume that $N$ satisfies (137) and we move to finding the condition on
$L$ so that

$q_{i}^{N}\left(1-\xi_{i}^{N}\right)R_{i}+\xi_{i}^{N}\leq
1+\delta\overset{(a)}{\Leftarrow}q_{i}^{N}\left(1-\xi_{i}^{N}\right)(1+\delta)+\xi_{i}^{N}\leq
1+\delta,$ (138)

where (a) follows from the induction hypothesis $R_{i}\leq 1+\delta$. (138) is
equivalent to

$\xi_{i}\geq\sqrt[N]{\frac{\delta}{q_{i}^{N}(1+\delta)-1}}\overset{(b)}{\Leftarrow}\xi_{i}\geq\sqrt[N]{\frac{\delta}{\beta^{N}(1+\delta)-1}}=:C^{\prime}_{N,\delta,\beta},$
(139)

and (b) is a consequence of $q_{i}$ being nondecreasing and converging to
$\beta$. By Lemma C.3,
$L\geq\frac{1}{2}\log_{2}(-\log(C^{\prime}_{N,\delta,\beta}))$ implies (139).
In summary, we have found the two following sufficient condition on $N$ and
$L$ so that $R_{i+1}\in[0,1+\delta]$:

$\displaystyle N$
$\displaystyle\geq-\log_{\beta}\left(\frac{\delta}{2-\beta}\right),$ (140)
$\displaystyle L$
$\displaystyle\geq\frac{1}{2}\log_{2}\left(-\log\left(C^{\prime}_{N,\delta,\beta}\right)\right)\cdot$
(141)

For $\delta\in\left(0,\frac{2-\beta}{\beta}\right)$, we say that
$\mathcal{D}_{\beta}$ satisfies $(\mathbf{H}_{\delta}^{\prime})$ if

$\displaystyle\begin{split}L&\geq\max\left\\{C_{N,\delta,\beta},\frac{1}{2}\log_{2}\left(-\log\left(C^{\prime}_{N,\delta,\beta}\right)\right)\right\\}\\\
N&\geq-\log_{\beta}\left(\frac{\delta}{2-\beta}\right),\\\ \Sigma_{i}&\geq
Ni\log_{2}(q_{i})-\log_{2}\left(\frac{2-\beta-\delta\beta}{2(\beta-1)}\right),\
\forall i\in\mathbf{N},\end{split}$ ($\mathbf{H}_{\delta}^{\prime}$)

We say that $\mathcal{D}_{\beta}$ satisfies $(\mathbf{H}^{\prime})$ if there
exists $\delta\in\left(0,\frac{2-\beta}{\beta}\right)$ such that
$\mathcal{D}_{\beta}$ satisfies $(\mathbf{H}_{\delta}^{\prime})$. We summarize
the above discussion with the following Lemma.

######  Lemma 4.1.

Let $\beta\in(1,2)$, and suppose that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H}^{\prime})$. Then,

$R^{\prime}_{i}(s)\in\left[0,\frac{1}{q_{i}-1}\right),\ \text{and}\
R_{i}(s)\in\left[0,\frac{2}{\beta}\right),\ \forall i\in\mathbf{N}_{0},\
\forall s\in[0,1],$ (142)

We now prove if $\mathcal{D}_{\beta}$ satisfies $(\mathbf{H}^{\prime})$, it
indeed generates a valid $\beta$-expansion.

######  Theorem 4.2.

Let $\beta\in(1,2)$, and suppose that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H}^{\prime})$. Then,

${\bf x}_{\beta}(s)\in\Sigma_{\beta}(s),\ \forall s\in[0,1].$ (143)

###### Proof.

Let $\beta\in(1,2)$, suppose that $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H}^{\prime})$, and let $s\in[0,1]$. To prove that ${\bf
x}_{\beta}(s)\in\Sigma_{\beta}(s)$, we need to show that $\delta_{\beta}({\bf
x}_{\beta}(s))=s$. Consider the sequence $(X_{n})_{n\in\mathbf{N}}$ generated
by $\mathcal{D}_{\beta}(s)$. By (111), $\underset{n\to\infty}{\lim}X_{n}={\bf
x}_{\beta}(s)$, where the limit is defined according to distance $d$
introduced in Definition A.1. As by Lemma A.2, $\delta_{\beta}$ is continuous
as a mapping from $\left(\\{0,1\\}^{\omega},d\right)$ to
$(\mathbf{R},|\cdot|)$, $\left(\delta_{\beta}(X_{n})\right)_{\mathbf{N}_{2}}$
therefore converges to $\delta_{\beta}({\bf x}_{\beta}(s))$. Further, fix
$n\in\mathbf{N}$ and note that

$\displaystyle|\delta_{\beta}(X_{n})-\delta_{q_{n-1}}(X_{n})|$
$\displaystyle=\left|\sum_{i=1}^{|X_{n}|}[X_{n}]_{i}\left(\beta^{-i}-q_{n-1}^{-i}\right)\right|\leq\left|\sum_{i=1}^{|X_{n}|}\left(\beta^{-i}-q_{n-1}^{-i}\right)\right|$
(144)
$\displaystyle\leq\left|\sum_{i=1}^{\infty}\left(\beta^{-i}-q_{n-1}^{-i}\right)\right|\leq\frac{1}{\beta-1}-\frac{1}{q_{n-1}-1}\underset{n\to\infty}{\to}0.$
(145)

Then,
$\underset{n\to\infty}{\lim}\delta_{\beta}(X_{n})=\underset{n\to\infty}{\lim}\delta_{q_{n-1}}(X_{n})$.
We now show that $\left(\delta_{q_{n-1}}(X_{n})\right)_{\mathbf{N}_{2}}$
converges to $s$, which allows us to conclude that
$s=\underset{n\to\infty}{\lim}\delta_{\beta}(X_{n})=\delta_{\beta}({\bf
x}_{\beta}(s))$, and hence that $\delta_{\beta}({\bf
x}_{\beta}(s))\in\Sigma_{\beta}(s)$. Fix $n\in\mathbf{N}$. First note that by
(104), $X_{n+1}=X_{n}{\bf g}_{q_{n}}(R^{\prime}_{n})_{1:N}$. By repeating this
argument, one has

$X_{n+1}=X_{0}\coprod_{i=0}^{n}{\bf
g}_{q_{i}}(R^{\prime}_{i})_{1:N}\overset{(\ref{eq:definition of the
generalized dynamical system})}{=}\coprod_{i=0}^{n}{\bf
g}_{q_{i}}(R^{\prime}_{i})_{1:N}.$ (146)

Further, for $i\in\\{1,\ldots,n\\}$,

$\displaystyle R_{i+1}-q_{i}^{N}R_{i}$
$\displaystyle\overset{(\ref{eq:definition of generalized K
beta})}{=}q_{i}^{N}(1-\xi_{i}^{N})R_{i}+\xi_{i}^{N}G_{q_{i}}^{N}(R^{\prime}_{i})-q_{i}^{N}R_{i}$
(147) $\displaystyle\overset{(\ref{eq:n iterations of greedy map is same as
reading the first n
bits})}{=}q_{i}^{N}(1-\xi_{i}^{N})R_{i}+\xi_{i}^{N}q_{i}^{N}\left(R^{\prime}_{i}-\delta_{q_{i}}({\bf
g}_{q_{i}}(R^{\prime}_{i}))_{1:N}\right)-q_{i}^{N}R_{i}$ (148)
$\displaystyle\overset{(\ref{eq:generalized definition auxiliary
sequences})}{=}\xi_{i}^{N}q_{i}^{N}\left(\frac{q_{i}^{Ni}}{2^{\Sigma_{i}}}S^{\prime}_{i}+q_{i}^{Ni}\left(\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})\right)-\delta_{q_{i}}({\bf
g}_{q_{i}}(R^{\prime}_{i}))_{1:N}\right)$ (149)
$\displaystyle\overset{(\ref{eq:def of xi
i})}{=}\chi_{i}^{N}\left(\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}(X_{i})-q_{i}^{-Ni}\delta_{q_{i}}({\bf
g}_{q_{i}}(R^{\prime}_{i}))_{1:N}\right)$ (150)
$\displaystyle\overset{(\ref{eq:generalized B_n as concatenation of greedy Z
i})}{=}\chi_{i}^{N}\left(\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}\left(\coprod_{j=0}^{i-1}{\bf
g}_{q_{j}}(R^{\prime}_{j})_{1:N}\right)-q_{i}^{-Ni}\delta_{q_{i}}({\bf
g}_{q_{i}}(R^{\prime}_{i}))_{1:N}\right)$
$\displaystyle\overset{\ref{lem:factorisation of beta expansion through
concatenation}}{=}\chi_{i}^{N}\left(\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}\left(\coprod_{j=0}^{i}{\bf
g}_{q_{j}}(R^{\prime}_{j})_{1:N}\right)\right)$ (151)
$\displaystyle\overset{(\ref{eq:generalized B_n as concatenation of greedy Z
i})}{=}\chi_{i}^{N}\left(\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}\left(X_{i+1}\right)\right),$
(152)

and

$\displaystyle R_{1}-q_{0}^{N}R_{0}$
$\displaystyle\overset{(\ref{eq:definition of generalized K
beta})}{=}q_{0}^{N}(1-\xi_{0}^{N})R_{0}+\xi_{0}^{N}G_{q_{0}}^{N}(R^{\prime}_{0})-q_{0}^{N}R_{0}\overset{(\ref{eq:definition
of the generalized dynamical
system})}{=}\xi_{0}^{N}G_{q_{0}}^{N}(R^{\prime}_{0})\overset{(\ref{eq:def of
xi i})}{=}G_{q_{0}}^{N}(R^{\prime}_{0})$ (153)
$\displaystyle\overset{(\ref{eq:n iterations of greedy map is same as reading
the first n bits})}{=}q_{0}^{N}\left(R^{\prime}_{0}-\delta_{q_{0}}({\bf
g}_{q_{0}}(R^{\prime}_{0})_{1:N})\right)\overset{(\ref{eq:generalized
definition auxiliary sequences}),(\ref{eq:generalized B_n as concatenation of
greedy Z
i})}{=}q_{0}^{N}\left(\frac{1}{2^{\Sigma_{0}}}S^{\prime}_{0}-\delta_{q_{0}}(B_{1})\right).$
(154)

Moreover, note that

$\displaystyle\sum_{i=0}^{n}\left(\prod_{j=i+1}^{n+1}q_{j}^{N}\right)\left(R_{i+1}-q_{i}^{N}R_{i}\right)=\sum_{i=0}^{n}\left(R_{i+1}\prod_{j=i+1}^{n+1}q_{j}^{N}-R_{i}\prod_{j=i}^{n+1}q_{j}^{N}\right)$
(155)
$\displaystyle=\sum_{i=1}^{n+1}\left(R_{i}\prod_{j=i}^{n+1}q_{j}^{N}\right)-\sum_{i=0}^{n}\left(R_{i}\prod_{j=i}^{n+1}q_{j}^{N}\right)=R_{n+1}\prod_{j=n+1}^{n+1}q_{j}^{N}-R_{0}\prod_{j=0}^{n+1}q_{j}^{N}$
(156)
$\displaystyle=R_{n+1}q_{n+1}^{N}-R_{0}\chi_{n+1}\overset{(\ref{eq:definition
of the generalized dynamical system})}{=}R_{n+1}q_{n+1}^{N}.$ (157)

Then,

$\displaystyle R_{n+1}$ $\displaystyle\overset{(\ref{eq:relation X n + 1 with
sum of X n
s})}{=}\frac{1}{q_{n+1}^{N}}\sum_{i=0}^{n}\left(\prod_{j=i+1}^{n+1}q_{j}^{N}\right)\left(R_{i+1}-q_{i}^{N}R_{i}\right)=\sum_{i=0}^{n}\left(\prod_{j=i+1}^{n}q_{j}^{N}\right)\left(R_{i+1}-q_{i}^{N}R_{i}\right)$
(158)
$\displaystyle=\sum_{i=1}^{n}\left(\prod_{j=i+1}^{n}q_{j}^{N}\right)\left(R_{i+1}-q_{i}^{N}R_{i}\right)+\left(\prod_{j=1}^{n}q_{j}^{N}\right)\left(R_{1}-q_{0}^{N}R_{0}\right)$
(159) $\displaystyle\overset{(\ref{eq:X i + 1 X i
relationship})}{=}\sum_{i=1}^{n}\left(\prod_{j=i+1}^{n}q_{j}^{N}\right)\chi_{i}^{N}\left(\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}\left(X_{i+1}\right)\right)+\left(\prod_{j=1}^{n}q_{j}^{N}\right)\left(R_{1}-q_{0}^{N}R_{0}\right)$
$\displaystyle\overset{\begin{subarray}{c}(\ref{eq:def of chi i})\\\
(\ref{eq:X 1 X 0
relationship})\end{subarray}}{=}\sum_{i=1}^{n}\chi_{n}^{N}\left(\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\delta_{q_{i-1}}(X_{i})-\delta_{q_{i}}\left(X_{i+1}\right)\right)+\left(\prod_{j=1}^{n}q_{j}^{N}\right)q_{0}^{N}\left(\frac{1}{2^{\Sigma_{0}}}S^{\prime}_{0}-\delta_{q_{0}}(B_{1})\right)$
$\displaystyle\overset{(\ref{eq:def of chi
i})}{=}\chi_{n}^{N}\left(\sum_{i=0}^{n}\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}+\sum_{i=1}^{n}\delta_{q_{i-1}}(X_{i})-\sum_{i=0}^{n}\delta_{q_{i}}\left(X_{i+1}\right)\right)$
(160)
$\displaystyle=\chi_{n}^{N}\left(\sum_{i=0}^{n}\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}-\delta_{q_{n}}\left(X_{n+1}\right)\right).$
(161)

Remark that, for $i\in\\{0,\ldots,n\\}$,

$\displaystyle S^{\prime}_{i}$ $\displaystyle\overset{(\ref{eq:definition
auxiliary sequences})}{=}S_{i}-G_{2}^{M_{i}}(S_{i})\overset{(\ref{eq:n
iterations of greedy map is same as reading the first n
bits})}{=}\delta_{2}\left({\bf
g}_{2}(S_{i})\right)\overset{(\ref{eq:definition of K
beta})}{=}\delta_{2}\left({\bf
g}_{2}\left(G_{2}^{\Sigma_{i}}(S_{0})\right)_{1:M_{i}}\right)$ (162)
$\displaystyle\overset{(\ref{eq:n iterations of greedy map is same as shifting
n bits})}{=}\delta_{2}\left({\bf
g}_{2}(S_{0})_{\Sigma_{i}+1:\Sigma_{i}+M_{i}}\right)\overset{(\ref{eq:definition
of Sigma as the sum of M})}{=}\delta_{2}\left({\bf
g}_{2}(S_{0})_{\Sigma_{i}+1:\Sigma_{i+1}}\right)\overset{(\ref{eq:definition
of the dynamical system})}{=}\delta_{2}\left({\bf
g}_{2}(s)_{\Sigma_{i}+1:\Sigma_{i+1}}\right).$ (163)

Therefore,

$\sum_{i=0}^{n}\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}\overset{(\ref{eq:generalized
W_i equivalent to delta of greedy
binary})}{=}\sum_{i=0}^{n}\frac{1}{2^{\Sigma_{i}}}\delta_{2}\left({\bf
g}_{2}(s)_{\Sigma_{i}+1:\Sigma_{i+1}}\right)\overset{\begin{subarray}{c}\ref{lem:factorisation
of beta expansion through concatenation}\\\ (\ref{eq:generalized definition of
Sigma as the sum of M})\end{subarray}}{=}\delta_{2}\left({\bf
g}_{2}(s)_{1:\Sigma_{i+1}}\right).$ (164)

Finally,

$\delta_{q_{n}}\left(X_{n+1}\right)\overset{(\ref{eq:intermediate result X n
+1})}{=}\sum_{i=0}^{n}\frac{1}{2^{\Sigma_{i}}}S^{\prime}_{i}-\frac{1}{\chi_{n}^{N}}X_{n+1}\overset{(\ref{eq:sum
W i to make x})}{=}\delta_{2}\left({\bf
g}_{2}(s)_{1:\Sigma_{n+1}}\right)-\frac{1}{\chi_{n}^{N}}R_{n+1}.$ (165)

As $\mathcal{D}_{\beta}$ satisfies $(\mathbf{H}^{\prime})$, by Lemma 4.1,
$0\leq R_{n+1}\leq\frac{2}{\beta}$, and as $\chi_{n}\overset{(\ref{eq:def of
chi i})}{\geq}q_{0}^{n}$, then
$0\leq\underset{n\to\infty}{\lim}\frac{R_{n+1}}{\chi_{n}}\leq\underset{n\to\infty}{\lim}\frac{2}{\beta
q_{0}^{n}}=0$. Moreover, as $\mathcal{D}_{\beta}$ satisfies
$(\mathbf{H}^{\prime})$, then also $\Sigma_{n}\geq Nn\log_{2}(\beta)$, so
$\underset{n\to\infty}{\lim}\Sigma_{n}=\infty$. We deduce that

$\underset{n\to\infty}{\lim}\delta_{q_{n}}(X_{n+1})=\underset{n\to\infty}{\lim}\delta_{2}\left({\bf
g}_{2}(s)_{1:\Sigma_{n+1}}\right)-\underset{n\to\infty}{\lim}\frac{1}{\chi_{n}^{N}}R_{n+1}=\delta_{2}({\bf
g}_{2}(s))=s,$ (166)

thereby finishing the proof.

∎

###  4.3 Algorithmic complexity of the $\beta$-expansion generated by
$\mathcal{D}_{\beta}$

Having established that $\beta\in(1,2)$ and $s\in[0,1]$, ${\bf x}_{\beta}(s)$
constitutes a valid $\beta$-expansion under condition $(\mathbf{H}^{\prime})$,
it remains to show that the algorithmic complexity of the prefixes of ${\bf
x}_{\beta}(s)$ can inferred from the algorithmic complexity of the prefixes of
the greedy expansion ${\bf g}_{2}(s)$. In this section, we say that
$\mathcal{D}_{\beta}$ is effective if there exists an effective algorithm
which can, on input $n$, output $\Sigma_{n}$, for all $n\in\mathbf{N}$. We
start with an intermediate result, and then conclude on the final result as a
corollary.

######  Theorem 4.3.

Let $\beta\in(1,2)$, $s\in[0,1]$, $\mathcal{D}_{\beta}=(L,N,(\Sigma_{n}))$ be
effective, and suppose that there exists
$\delta\in\left(0,\frac{2-\beta}{\beta}\right)\cap\mathbf{Q}$ such that
$\mathcal{D}_{\beta}$ satisfies ($\mathbf{H}_{\delta}^{\prime}$). Then, there
exists $c>0$, depending only on $\mathcal{D}_{\beta}$, such that

$K[{\bf x}_{\beta}(s)|Nn]\leq K[{\bf g}_{2}(s)|\Sigma_{n}]+F(K[{\bf
g}_{2}(\beta-1)|Nn+L])+c,\ \ \text{for all}\ n\in\mathbf{N},$ (167)

where $F:t\mapsto t+2\log_{2}(t)$.

###### Proof.

Let $\beta\in(1,2)$, $s\in[0,1]$, $\mathcal{D}_{\beta}=(L,N,(\Sigma_{n}))$ be
effective and suppose that there exists
$\delta\in\left(0,\frac{2-\beta}{\beta}\right)\cap\mathbf{Q}$ such that
$\mathcal{D}_{\beta}$ satisfies ($\mathbf{H}_{\delta}^{\prime}$).

We design an effective algorithm $\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$
such that

${\bf x}_{\beta}(s)_{1:Nn}=\varphi(\langle{\bf g}_{2}(s)_{1:\Sigma_{n}},{\bf
g}_{2}(\beta-1)_{1:Nn+L}\rangle),\ \ \text{for all}\ n\in\mathbf{N}.$ (168)

Let $n\in\mathbf{N}$. Concretely, on input $\langle{\bf
g}_{2}(\beta-1)_{1:Nn+L},{\bf g}_{2}(s)_{1:\Sigma_{n}}\rangle$, $\varphi$
first separates ${\bf g}_{2}(\beta-1)_{1:Nn+L}$ from ${\bf
g}_{2}(x)_{1:\Sigma_{n}}$. $\varphi$ then computes $n$ through
$n=\frac{Nn+L-L}{N}$. Further, $\varphi$ uses ${\bf g}_{2}(\beta-1)_{1:Nn+L}$
to compute $q_{0},\ldots,q_{n}$, as per $q_{i}=\delta_{2}({\bf
g}_{2}(\beta-1)_{1:Ni+L})$. $\varphi$ then computes $n$ iterations of the
dynamical system $\mathcal{D}_{\beta}$ on input $s$, and records the
successive values $R^{\prime}_{0},\ldots,R^{\prime}_{n}$. Finally, it
generates ${\bf x}_{\beta}(s)_{1:Nn}$ through the equation

${\bf x}_{\beta}(s)_{1:Nn}:=\coprod_{i=0}^{n-1}{\bf
g}_{q_{i}}(R^{\prime}_{i})_{1:N}.$ (169)

Note that as $q_{k}\in\mathbf{Q}$ for all $0\leq k\leq n$, all the variables
involved in the evolution of $\mathcal{D}_{\beta}$ are rational numbers, and
all the operations underlying this evolution can be run on a digital computer,
as they can be reduced to additions and multiplications only. So $\varphi$ is
indeed an effective algorithm. By Lemma 1.1, there exists $C>0$, depending
only on $\varphi$, and a fortirori only on $\mathcal{D}_{\beta}$, such that,
for all $n\in\mathbf{N}$,

$\displaystyle K[{\bf x}_{\beta}(x)|Nn]$ $\displaystyle\leq K[\langle{\bf
g}_{2}(s)_{1:\Sigma_{n}},{\bf g}_{2}(\beta-1)_{1:Nn+L}\rangle]+C$ (170)
$\displaystyle\overset{(\ref{eq:simple inequality on pairing of
sequences})}{\leq}K[{\bf g}_{2}(s)_{1:\Sigma_{n}}]+F(K[{\bf
g}_{2}(\beta-1)_{1:Nn+L}])+C_{+}+C.$ (171)

We set $c:=C+C_{+}$, thereby finishing the proof. ∎

######  Corollary 4.4.

Let $\beta\in(1,2)$, $s\in[0,1]$. Then, there exists $\hat{\bf
x}_{\beta}\in\Sigma_{\beta}(s)$, and $c>0$, depending only on $\beta$, such
that

$K[\hat{\bf x}_{\beta}|n]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+F(K[{\bf g}_{2}(\beta-1)|n])+c,\ \text{for all}\
n\in\mathbf{N}.$ (172)

###### Proof.

Let $\beta\in(1,2)$, $s\in[0,1]$. Let
$\delta\in(0,\frac{2-\beta}{\beta})\cap\mathbf{Q}$, and let
$\mathcal{D}_{\beta}$ be the dynamical system defined as in (55), such that

$\begin{split}L&=\left\lceil\max\left\\{C_{N,\beta}-\log_{2}\left(\frac{C_{\delta,\beta}}{N^{2}\beta^{N}}\right),\frac{1}{2}\log_{2}\left(-\log\left(C^{\prime}_{N,\delta,\beta}\right)\right)\right\\}\right\rceil\\\
N&=-\left\lceil\log_{\beta}\left(\frac{\delta}{2-\beta}\right)\right\rceil,\\\
\Sigma_{i}&=\left\lceil
Ni\log_{2}(q_{i})-\log_{2}\left(C_{\delta,\beta}\right)\right\rceil,\ \forall
i\in\mathbf{N}.\end{split}$ ($\mathbf{H}_{\delta}^{\prime}$)

Obviously, $\mathcal{D}_{\beta}$ satisfies ($\mathbf{H}_{\delta}^{\prime}$),
where $\delta\in\mathbf{Q}$, so by Lemma 4.3, there exists $c>0$ such that

$K[{\bf x}_{\beta}(s)|Nn]\leq K[{\bf g}_{2}(s)|\Sigma_{n}]+F(K[{\bf
g}_{2}(\beta-1)|Nn+L])+c,\ \ \text{for all}\ n\in\mathbf{N}.$ (173)

Note that by (255), there exists $C>0$ such that

$K[{\bf x}_{\beta}(s)|n]\leq K[{\bf g}_{2}(s)|\Sigma_{\lfloor
n/N\rfloor}]+F(K[{\bf g}_{2}(\beta-1)|N\lfloor n/N\rfloor+L])+c+C,\ \
\text{for all}\ n\in\mathbf{N}.$ (174)

Further, remark that

$n-N+L\leq N\lfloor n/N\rfloor+L\leq n+L,\ \text{ for all }\ n\in\mathbf{N}.$
(175)

Then, by Lemma C.7, there exists $C^{\prime}>0$ such that

$\displaystyle K[{\bf g}_{2}(\beta-1)|N\lfloor n/N\rfloor+L]\leq K[{\bf
g}_{2}(\beta-1)|n]+C^{\prime},\ \ \text{for all}\ n\in\mathbf{N},$ (176)
$\displaystyle\overset{(a)}{\Rightarrow}$ $\displaystyle F(K[{\bf
g}_{2}(\beta-1)|N\lfloor n/N\rfloor+L])\leq F(K[{\bf
g}_{2}(\beta-1)|n])+C^{\prime},\ \ \text{for all}\ n\in\mathbf{N},$ (177)

where (a) is a consequence of $F$ being increasing and subadditive. It follows
that

$K[{\bf x}_{\beta}(s)|n]\leq K[{\bf g}_{2}(s)|\Sigma_{\lfloor
n/N\rfloor}]+F(K[{\bf g}_{2}(\beta-1)|n])+C^{\prime}+c+C,\ \ \text{for all}\
n\in\mathbf{N}.$ (178)

Finally, note that

$\displaystyle\left|\lceil n\log_{2}(\beta)\rceil-\Sigma_{\lfloor
n/N\rfloor}\right|$ $\displaystyle\leq
2+\left|n\log_{2}(\beta)-N\left\lfloor\frac{n}{N}\right\rfloor\log_{2}(q_{\lfloor
n/N\rfloor})-\log_{2}\left(C_{\delta,\beta}\right)\right|$ (179)
$\displaystyle\leq 2+N+\left|n\log_{2}(\beta)-n\log_{2}(q_{\lfloor
n/N\rfloor})-\log_{2}\left(C_{\delta,\beta}\right)\right|$ (180)
$\displaystyle\overset{(a)}{\leq}2+N+\left|n\frac{1}{\log(2)}(\beta-q_{\lfloor
n/N\rfloor})-\log_{2}\left(C_{\delta,\beta}\right)\right|$ (181)
$\displaystyle\leq 2+N+\left|n\frac{1}{\log(2)}2^{-L-N{\lfloor
n/N\rfloor}}-\log_{2}\left(C_{\delta,\beta}\right)\right|$ (182)
$\displaystyle\leq
2+N+\left|\frac{2}{\log(2)}2^{-L}n2^{-n}-\log_{2}\left(C_{\delta,\beta}\right)\right|$
(183)
$\displaystyle\overset{(b)}{\leq}2+N+\left|\frac{2}{\log(2)}2^{-L}-\log_{2}\left(C_{\delta,\beta}\right)\right|=:M$
(184)

where (a) follows from $\log:[1,\infty]\to\mathbf{R}$ being 1-Lipschitz, and
(b) is by $n2^{-n}\leq 1$ for all $n\in\mathbf{N}$. Then, $\left|\lceil
n\log_{2}(\beta)\rceil-\Sigma_{\lfloor n/N\rfloor}\right|\leq M$ for all
$n\in\mathbf{N}$, so by Lemma by Lemma C.7, there exists $C^{\prime\prime}>0$
such that

$K[{\bf g}_{2}(s)|\Sigma_{\lfloor n/N\rfloor}]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+C^{\prime\prime},\ \text{for all}\ n\in\mathbf{N}.$
(186)

By combining (94) and (96), one has

$K[{\bf x}_{\beta}(s)|n]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+F(K[{\bf
g}_{2}(\beta-1)|n])+C^{\prime\prime}+C^{\prime}+C+c,\ \text{for all}\
n\in\mathbf{N},$

thereby finishing the proof by letting $\hat{\bf x}_{\beta}:={\bf
x}_{\beta}(s)$. ∎

We have proven that for every $s\in[0,1]$, there exists a $\beta$-expansion of
$s$ which algorithmic complexity of prefixes is upper bounded a very simple
manner by a relation involving the algorithmic complexity of the prefixes of
the binary expansion of $s$ and the binary expansion of $\beta$, for every
$\beta\in(1,2)$. A direct consequence is the following corollary, when $\beta$
is a computable number.

######  Corollary 4.5.

Let $\beta\in(1,2)$ be a computable number, and $s\in[0,1]$. Then, there
exists $\hat{\bf x}_{\beta}\in\Sigma_{\beta}(s)$, and $c>0$, depending only on
$\beta$, such that

$K[\hat{\bf x}_{\beta}|n]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta)\rceil]+c,\ \text{for all}\ n\in\mathbf{N}.$ (187)

This achieves the proof of Theorem 2.4.

##  Appendix A Basic concepts related to $q$-ary and $\beta$-expansions

In this Appendix, we review some facts about $\beta$-expansions. Let
$\beta\in(1,2]$, $\delta_{\beta}$ be defined according to $(\ref{eq:definition
of delta beta})$. Throughout the paper, we make use of the fact that
$\delta_{\beta}$ is continuous on $\\{0,1\\}^{\omega}$, with respect to a
specific distance $d$, that we introduce next.

######  Definition A.1.

We define

$\begin{array}[]{lccl}d:&\left(\\{0,1\\}^{\omega}\right)^{2}&\to&\mathbf{R}\\\
&{\bf x},{\bf y}&\mapsto&\displaystyle\frac{1}{\min\\{i\in\mathbf{N}\,:\,{\bf
x}_{i}\neq{\bf y}_{i}\\}}.\end{array}$ (188)

######  Lemma A.1.

$d$ is a metric.

###### Proof.

Let ${\bf x},{\bf y}\in\\{0,1\\}^{\omega}$, and note that $d({\bf x},{\bf
y})\geq 0$, $d({\bf x},{\bf y})=d({\bf y},{\bf x})$, and $d({\bf x},{\bf
y})=0\Leftrightarrow{\bf x}={\bf y}$. Let ${\bf x},{\bf y},{\bf
z}\in\\{0,1\\}^{\omega}$. Then,

  1. (a)

if $d({\bf x},{\bf y})\leq d({\bf x},{\bf z})$, then trivially $d({\bf x},{\bf
y})\leq d({\bf x},{\bf z})+d({\bf z},{\bf y})$,

  2. (b)

if $d({\bf x},{\bf y})>d({\bf x},{\bf z})$, then $d({\bf y},{\bf z})=d({\bf
x},{\bf y})$, so $d({\bf x},{\bf y})\leq d({\bf x},{\bf z})+d({\bf y},{\bf
z})$.

In all cases, we have $d({\bf x},{\bf y})\leq d({\bf x},{\bf z})+d({\bf
z},{\bf y})$. Therefore, $d$ is symmetric, positive separable, and satisfies
the triangular inequality on $\mathbf{N}$, so $d$ is a metric. ∎

######  Lemma A.2.

Let $\beta\in(1,2]$. $\delta_{\beta}$ as a mapping from $\\{0,1\\}^{\omega}$
to $I_{\beta}$ is continuous.

###### Proof.

Fix $\beta\in(1,2]$, $\varepsilon>0$, and ${\bf x},{\bf
y}\in\\{0,1\\}^{\omega}$ such that $d({\bf x},{\bf y})\leq 1/j$, for some
$j\in\mathbf{N}$. Then,

$\displaystyle\left|\delta_{\beta}\left({\bf
x}\right)-\delta_{\beta}\left({\bf y}\right)\right|$
$\displaystyle=\left|\sum_{i=1}^{\infty}({\bf x}-{\bf
y}_{i})\beta^{-i}\right|\leq\sum_{i=j+1}^{\infty}\left|{\bf x}-{\bf
y}_{i}\right|\beta^{-i}\leq
2\left|\sum_{i=j+1}^{\infty}\beta^{-i}\right|\leq\frac{2}{\beta-1}\beta^{-j}.$
(189)

Therefore, a sufficient condition for $\left|\delta_{\beta}\left({\bf
x}\right)-\delta_{\beta}\left({\bf y}\right)\right|\leq\varepsilon$ to hold is

$d({\bf x},{\bf
y})=\frac{1}{j}\leq\frac{1}{\log_{\beta}\left(\frac{2}{\varepsilon(\beta-1)}\right)}.$
(190)

In summary, for all ${\bf x},{\bf y}\in\\{0,1\\}^{\omega}$ satisfying $d({\bf
x},{\bf
y})\leq\delta:=\frac{1}{\log_{\beta}\left(\frac{2(\lceil\beta\rceil-1)}{\varepsilon(\beta-1)}\right)}$,
one has $\left|\delta_{\beta}({\bf x})-\delta_{\beta}({\bf
y})\right|\leq\varepsilon$, which establishes the continuity of
$\delta_{\beta}$. ∎

The two following results are on computing $\delta_{\beta}$ when the input is
made up of blocks, which turns out to be useful.

######  Lemma A.3.

Let $n\in\mathbf{N}$, $(\ell_{i})_{i\in\left\llbracket 0,n\right\rrbracket}$,
and $(x_{i})_{i\in\left\llbracket 0,n\right\rrbracket}\in\\{0,1\\}^{m}$ be a
family of $n+1$ binary sequences of respective length $\ell_{i}$. We define
$L_{i}:=\sum_{j=0}^{i}\ell_{j}$, for $i\in\left\llbracket
0,n\right\rrbracket$. Then, for all $\beta\in(1,2]$, it holds that

$\delta_{\beta}\left(\coprod_{i=0}^{n}x_{i}\right)=\delta_{\beta}(x_{0})+\sum_{i=1}^{n}\beta^{-L_{i-1}}\delta_{\beta}(x_{i}).$
(191)

###### Proof.

The proof follows by the chain of arguments

$\displaystyle\delta_{\beta}\left(\coprod_{i=0}^{n}x_{i}\right)$
$\displaystyle=\sum_{j=1}^{L_{n}}\beta^{-j}\left[\coprod_{i=0}^{n}x_{i}\right]_{j}=\sum_{j=1}^{L_{0}}\beta^{-j}\left[\coprod_{i=0}^{n}x_{i}\right]_{j}+\sum_{j=L_{0}+1}^{L_{n}}\beta^{-j}\left[\coprod_{i=0}^{n}x_{i}\right]_{j}$
(192)
$\displaystyle=\sum_{j=1}^{\ell_{0}}\beta^{-j}\left[\coprod_{i=0}^{n}x_{0}\right]_{j}+\sum_{j=1}^{n}\sum_{k=L_{j-1}+1}^{L_{j}}\beta^{-k}\left[\coprod_{i=0}^{n}x_{i}\right]_{k}$
(193)
$\displaystyle=\sum_{j=1}^{\ell_{0}}\beta^{-j}x_{0}+\sum_{j=1}^{n}\sum_{k=1}^{L_{j}-L_{j-1}}\beta^{-k-L_{j-1}}\left[\coprod_{i=0}^{n}x_{i}\right]_{k+L_{j-1}}$
(194)
$\displaystyle=\delta_{\beta}(x_{0})+\sum_{j=1}^{n}\beta^{-L_{j-1}}\sum_{k=1}^{\ell_{j}}\beta^{-k}\left[x_{j}\right]_{k}$
(195)
$\displaystyle=\delta_{\beta}(x_{0})+\sum_{i=1}^{n}\beta^{-L_{i-1}}\delta_{\beta}(x_{i}).$
(196)

∎

######  Lemma A.4.

Let $x\in\\{0,1\\}^{\ast}$ and ${\bf x}\in\\{0,1\\}^{\omega}$. Then, for all
$\beta\in(1,2]$, it holds that

$\delta_{\beta}\left(x{\bf
x}\right)=\delta_{\beta}(x)+\beta^{-|x|}\delta_{\beta}({\bf x}).$ (197)

###### Proof.

The proof follows by the chain of arguments

$\displaystyle\delta_{\beta}\left(x{\bf x}\right)$
$\displaystyle=\sum_{i=1}^{\infty}[x{\bf
x}]_{i}\beta^{-i}=\sum_{i=1}^{|x|}[x{\bf
x}]_{i}\beta^{-i}+\sum_{i=|x|+1}^{\infty}[x{\bf x}]_{i}\beta^{-i}$ (198)
$\displaystyle=\sum_{i=1}^{|x|}x_{i}\beta^{-i}+\sum_{i=1}^{\infty}[x{\bf
x}]_{i+|x|}\beta^{-(i+|x|)}=\delta_{\beta}(x)+\beta^{-|x|}\sum_{i=1}^{\infty}{\bf
x}_{i}\beta^{-i}$ (199)
$\displaystyle=\delta_{\beta}(x)+\beta^{-|x|}\delta_{\beta}({\bf x}).$ (200)

∎

Following [8, Section 1], we close this section with a technical result
involving the convergence behavior of $G_{\beta}$, which will turn out to be
useful.

######  Lemma A.5.

Let $\beta\in(1,2)$, $r\in\left[0,\frac{1}{\beta-1}\right]$, and set
$N_{\beta}(r)=-\log_{\beta}\left(\frac{1-(\beta-1)r}{2-\beta}\right)$. Then,
for $n\in\mathbf{N}$, it holds that $n>N_{\beta}(s)$ if and only if

$G^{n}_{\beta}(r)\in[0,1).$ (201)

###### Proof.

Fix $\beta\in(1,2)$. The proof is divided two regimes for
$r\in\left[0,\frac{1}{\beta-1}\right]$. First, note that if $r\in[0,1)$, then

$G_{\beta}(r)=\begin{cases}\beta r,\ \text{if}\ r<\frac{1}{\beta},\\\ \beta
r-1,\ \text{if}\ r\geq\frac{1}{\beta},\end{cases}<\begin{cases}1,\ \text{if}\
r<\frac{1}{\beta},\\\ \beta-1,\ \text{if}\
r\geq\frac{1}{\beta},\end{cases}\leq 1.$ (202)

Therefore, $G_{\beta}([0,1))\subseteq[0,1)$. Now, fix
$x\in\left[1,\frac{1}{\beta-1}\right]$, and take $m\in\mathbf{N}$ to satisfy
$G^{m}_{\beta}(r)\geq 1$. As $G_{\beta}([0,1))\subseteq[0,1)$, we must have
for all $i\leq m$, that $G^{i}_{\beta}(r)\geq 1\geq\frac{1}{\beta}$. Then, one
gets

$\displaystyle 1\leq G^{m}_{\beta}(r)$ $\displaystyle=(t\mapsto\beta
t-1)^{m}(r)=\beta^{m}x-\sum_{i=0}^{m-1}\beta^{i}=\beta^{m}r-\frac{\beta^{m}-1}{\beta-1}.$
(203)

This is satisfied if and only if

$m\leq-\log_{\beta}\left(\frac{1-(\beta-1)r}{2-\beta}\right).$ (204)

∎

##  Appendix B A simple relation for algorithmic complexity of binary and
$\beta$-expansions

In this appendix, we establish, for every $\beta\in(1,2)\cap\mathbf{Q}$ and
$s\in[0,1]$, a relation between the algorithmic complexity of the prefixes of
the greedy binary expansion of $s$ and the prefixes of the $\beta$-expansions
of $s$.

######  Lemma B.1.

Let $\beta\in(1,2]$, and $s\in\left[0,\frac{1}{\beta-1}\right]$. Then, for all
$x\in\\{0,1\\}^{\ast}$, $x$ is a prefix of a $\beta$-expansion if and only if
$s\in\delta_{\beta}(x)+\beta^{-|x|}\left[0,\frac{1}{\beta-1}\right]$.

###### Proof.

Let $\beta\in(1,2]$, and $s\in\left[0,\frac{1}{\beta-1}\right]$. Suppose
$s\in\delta_{\beta}(x)+\beta^{-|x|}\left[0,\frac{1}{\beta-1}\right]$. Then,
there exists ${\bf x}\in\\{0,1\\}^{\omega}$ such that

$s=\delta_{\beta}(x)+\beta^{-|x|}\delta_{\beta}({\bf
x})\overset{\ref{lem:factorisation of beta expansion through concatenation
two}}{=}\delta_{\beta}(x{\bf x}),$ (205)

so $x$ is a prefix of the $\beta$-expansion $x{\bf x}$. Conversely, suppose
that $x$ is a prefix of a $\beta$-expansion of $s$. Then, there exists ${\bf
x}\in\\{0,1\\}^{\omega}$ such that $x{\bf x}$ is a $\beta$-expansion of $s$,
i.e.

$s=\delta_{\beta}(x{\bf x})\overset{\ref{lem:factorisation of beta expansion
through concatenation
two}}{=}\delta_{\beta}(x)+\beta^{-|x|}\delta_{\beta}({\bf
x})\in\delta_{\beta}(x)+\beta^{-|x|}\left[0,\frac{1}{\beta-1}\right].$ (206)

∎

######  Lemma B.2.

Let $\beta_{1},\beta_{2}\in(1,2),\ \beta_{1}<\beta_{2}$, $n\in\mathbf{N}$ and
$x\in\\{0,1\\}^{n}$. We denote by $A(x)$ the set of $\lceil
n\log_{2}(\beta_{1})\rceil$-prefixes of the greedy expansions of all real
numbers for which there exists $\beta\in(\beta_{1},\beta_{2})$ such that one
of the $\beta$-expansions has $n$-prefix $x$. Then,

$\\#\left(A(x)\right)\leq\frac{2}{\beta_{1}-1}+n(n+1)(\beta_{2}-\beta_{1})\beta_{1}^{n}+2.$
(207)

###### Proof.

Let $\beta_{1},\beta_{2}\in(1,2],\ \beta_{1}<\beta_{2}$, $n\in\mathbf{N}$ and
$x\in\\{0,1\\}^{n}$. Let $X(x)\subseteq\left[0,\frac{1}{\beta_{1}-1}\right)$
be the set of real numbers for which there exists
$\beta\in(\beta_{1},\beta_{2})$ such that one of the $\beta$-expansions has
prefix $x$. By Lemma B.1,

$S(x)=\bigcup_{\beta\in[\beta_{1},\beta_{2}]}\left(\delta_{\beta}(x)+\beta^{-n}\left[0,\frac{1}{\beta-1}\right]\right).$
(208)

Note that $t\mapsto\delta_{t}(b)$, as a function from $(1,2]$ to $\mathbf{R}$,
is continuous and decreasing, so $S(x)$ is a closed interval whose lower bound
is $\delta_{\beta_{2}}(x)$ and
$\delta_{\beta_{1}}(x)+\frac{\beta_{1}^{-n}}{\beta_{1}-1}$ is the upper bound,
i.e.

$S(x)=\left[\delta_{\beta_{2}}(x),\delta_{\beta_{1}}(x)+\frac{\beta_{1}^{-n}}{\beta_{1}-1}\right].$
(209)

Let $w\in\\{0,1\\}^{\lceil n\log_{2}(\beta_{2})\rceil}$. One has that $y\in
A(x)$ $\Leftrightarrow$ there exists a $s\in S(x)$ such that $y$ is a prefix
of ${\bf g}_{2}(s)$ $\overset{\ref{lem:condition prefix beta expansion of
x}}{\Rightarrow}$ there exists $s\in X(x)$ such that
$s\in\delta_{2}(y)+2^{-|y|}\left[0,1\right]$ $\Leftrightarrow$ there exists
$s\in S(x)$ such that $\delta_{2}(y)\in x+2^{-|y|}\left[-1,0\right]$
$\Leftrightarrow$ $\delta_{2}(y)\in
S(x)+2^{-|y|}\left[-1,0\right]=\left[\delta_{\beta_{2}}(x)-2^{-|y|},\delta_{\beta_{1}}(x)+\frac{\beta_{1}^{-n}}{\beta_{1}-1}\right]$.
Therefore,

$A(x)\subseteq\delta_{2}\left(\\{0,1\\}^{\lceil
n\log_{2}(\beta_{1})\rceil}\right)\cap\underset{=:R(x)}{\underbrace{\left[\delta_{\beta_{2}}(x)-2^{-|y|},\delta_{\beta_{1}}(x)+\frac{\beta_{1}^{-n}}{\beta_{1}-1}\right]}}.$
(210)

As for any two different elements of
$s,s^{\prime}\in\delta_{2}\left(\\{0,1\\}^{\lceil
n\log_{2}(\beta_{1})\rceil}\right)$, $|s-s^{\prime}|\geq d:=2^{-\lceil
n\log_{2}(\beta_{1})\rceil}$, one has

$\displaystyle\\#(A(x))$
$\displaystyle\leq\left\lceil\frac{|R(x)|}{d}\right\rceil\leq\frac{\left[\delta_{\beta_{2}}(x)-2^{-\lceil
n\log_{2}(\beta_{1})\rceil},\delta_{\beta_{1}}(x)+\frac{\beta_{1}^{-n}}{\beta_{1}-1}\right]}{2^{-\lceil
n\log_{2}(\beta_{1})\rceil}}+1$ (211) $\displaystyle=\frac{2^{-\lceil
n\log_{2}(\beta_{1})\rceil}+\frac{\beta_{1}^{-n}}{\beta_{1}-1}+\delta_{\beta_{1}}(x)-\delta_{\beta_{2}}(x)}{2^{-\lceil
n\log_{2}(\beta_{1})\rceil}}+1$ (212) $\displaystyle=\frac{2^{-\lceil
n\log_{2}(\beta_{1})\rceil}\beta_{1}^{-n}}{\beta_{1}-1}+2^{-\lceil
n\log_{2}(\beta_{1})\rceil}\left(\delta_{\beta_{1}}(x)-\delta_{\beta_{2}}(x)\right)+2$
(213)
$\displaystyle\leq\frac{2^{-n\log_{2}(\beta_{1})+1}\beta_{1}^{-n}}{\beta_{1}-1}+2^{-n\log_{2}(\beta_{1})+1}\left(\delta_{\beta_{1}}(x)-\delta_{\beta_{2}}(x)\right)+2$
(214)
$\displaystyle\leq\frac{2}{\beta_{1}-1}+2\beta_{1}^{n}\left(\delta_{\beta_{1}}(x)-\delta_{\beta_{2}}(x)\right)+2$
(215) $\displaystyle\overset{\ref{lem:delta beta
lipschitz}}{\leq}\frac{2}{\beta_{1}-1}+2\beta_{1}^{n}\frac{n(n+1)}{2}(\beta_{2}-\beta_{1})+2$
(216)
$\displaystyle=\frac{2}{\beta_{1}-1}+\beta_{1}^{n}n(n+1)(\beta_{2}-\beta_{1})+2.$
(217)

∎

######  Theorem B.3.

For all $s\in[0,1]$ and all $\beta\in(1,2)$, there exists $c>0$ such that

$K[{\bf g}_{2}(s)|\lceil n\log_{2}(\beta)\rceil]\leq K[{\bf
x}|n]+F(K[u_{n}])+c,\ \ \forall n\in\mathbf{N},\ \ \forall{\bf
x}\in\Sigma_{\beta}(s),$ (218)

where $u_{n}:={\bf g}_{2}(\beta-1)_{1:n}$, and $F:t\mapsto t+2\log_{2}(t)$.

###### Proof.

The main arguments of this proof follow closely that of [17, Theorem 3]. Let
$s\in[0,1]$, $\beta\in(1,2)$, ${\bf x}\in\Sigma_{\beta}(s)$ and
$n\in\mathbf{N}$, large enough to ensure that $u_{n}:={\bf
g}_{2}(\beta-1)_{1:n}$ is not made only of $0$’s. Let
$\beta_{1}-1\in(0,1)\cap\mathbf{Q}$ to be the real number having the same
greedy binary expansion as $\beta-1$, but truncated after $\lceil
n\log_{2}(\beta)\rceil$ bits, i.e. $\beta_{1}-1:=\delta_{2}(u_{n})$. We also
define $\beta_{2}:=\beta_{1}+2^{-\lceil\log_{2}(\beta)\rceil}$. By Lemma B.1,

$1\overset{(a)}{<}\beta_{1}\leq\beta\leq\beta_{2}\leq 2.$ (219)

where (a) follows from the fact that $u_{n}$ is not made only of $0$’s.

By Lemma B.2, the sole knowledge of ${\bf x}_{1:n}$ allows to immediatly
conclude that ${\bf g}_{2}(s)_{1:\lceil n\log_{2}(\beta)\rceil}$ belongs to a
set $A({\bf x}_{1:n})\subseteq\\{0,1\\}^{\lceil n\log_{2}(\beta_{1})\rceil}$,
which cardinality is bounded above by
$\frac{2}{\beta_{1}-1}+n(n+1)(\beta_{2}-\beta_{1})\beta_{1}^{n}+2$, and which
can be computed by using $u_{n}$ only. As defined above,
$\beta_{2}-\beta_{1}=2^{-\lceil\log_{2}(\beta)\rceil}\leq\beta^{-n}$, hence
$n(n+1)(\beta_{2}-\beta_{1})\beta_{1}^{n}\leq n(n+1)(\beta_{1}/\beta)^{n}$. As
$\beta_{1}/\beta<1$,
$\left(n(n+1)(\beta_{1}/\beta)^{n}\right)_{n\in\mathbf{N}}$ is a bounded
sequence. Overall, there exists a constant $N>0$, independant of $n$, such
that $\\#(A({\bf x}_{1:n}))\leq N$.

Let $z_{n}\in\mathbf{N}$ be the index of ${\bf g}_{2}(s)_{1:\lceil
n\log_{2}(\beta)\rceil}$ in the lexicographical enumeration of $A({\bf
x}_{1:n})$. Then, one can build an effective algorithm
$\varphi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$, such that on input
$\langle\langle{\bf x}_{1:n},u_{n}\rangle,z_{n}\rangle$, $\varphi$ computes
$A({\bf x}_{1:n})$, finds the $z_{n}$-th element $y$ of $A({\bf x}_{1:n})$ and
outputs $y$. By the preceding discussion, it is clear that
$\varphi(\langle\langle{\bf x}_{1:n},u_{n}\rangle,z_{n}\rangle)={\bf
g}_{2}(s)_{1:\lceil n\log_{2}(\beta)\rceil}$. By Lemma 1.1, there exists
$C,C^{\prime}>0$ such that

$\displaystyle K[y]$ $\displaystyle\overset{\ref{lem:if two sequences are
connected through an algorithm, they have same kolmogorov
complexity}}{\leq}K[\langle\langle{\bf x}_{1:n},z_{n}\rangle,u_{n}\rangle]+C$
(220) $\displaystyle\overset{(\ref{eq:simple inequality on concatenation of
sequences})}{\leq}K[\langle{\bf
x}_{1:n},z_{n}\rangle]+F\left(K[u_{n}]\right)+C_{+}+C$ (221)
$\displaystyle\overset{(\ref{eq:simple inequality on concatenation of
sequences})}{\leq}K[{\bf
x}_{1:n}]+F\left(K[z_{n}]\right)+F\left(K[u_{n}]\right)+2C_{+}+C$ (222)
$\displaystyle\overset{(\ref{eq:algorithmic complexity is bounded by the
length})}{\leq}K[{\bf
x}_{1:n}]+F\left(|z_{n}|+C_{||}\right)+F\left(K[u_{n}]\right)+2C_{+}+C$ (223)
$\displaystyle\overset{\ref{lem:if two sequences are connected through an
algorithm, they have same kolmogorov complexity}}{\leq}K[{\bf
x}_{1:n}]+F\left(|z_{n}|+C_{||}\right)+F\left(K[u_{n}]+C^{\prime}\right)+2C_{+}+C$
(224) $\displaystyle\overset{(a)}{\leq}K[{\bf
x}_{1:n}]+F\left(|z_{n}|\right)+F\left(K[u_{n}]\right)+C_{||}+2C_{+}+C+C^{\prime},$
(225)

where $(a)$ is by $F$ being subadditive. Recall from above that $\\#(A({\bf
x}_{1:n}))\leq N$. As $z_{n}$ is an index for $A({\bf x}_{1:n})$, then
$z_{n}\leq N$, and we set $C_{0}:=F(N)$, so that

$K[y]\overset{(\ref{eq:ineq algorithmic complexity w appendix})}{\leq}K[{\bf
x}_{1:n}]+F\left(K[u_{n}]\right)+C_{||}+2C_{+}+C+C^{\prime}+C_{0}.$ (226)

We set $c:=C_{||}+2C_{+}+C+C^{\prime}+C_{0}$. By identification of $y$ with
${\bf g}_{2}(s)_{1:\lceil n\log_{2}(\beta_{1})\rceil}$, one has

$K[{\bf g}_{2}(s)|\lceil n\log_{2}(\beta_{1})\rceil]\leq K[{\bf
x}|n]+F(K[u_{n}])+c.$ (227)

Note that as $\beta_{1}:=\delta_{2}(u_{n})$, $|\beta-\beta_{1}|\leq 2^{-\lceil
n\log_{2}(\beta)\rceil}\leq\beta^{-n}$, so

$\displaystyle\left|\lceil n\log_{2}(\beta)\rceil-\lceil
n\log_{2}(\beta_{1})\rceil\right|$ $\displaystyle\leq
n(\log_{2}(\beta)-\log_{2}(\beta_{1}))+2$ (228)
$\displaystyle=n(\log_{2}(\beta_{1}+\beta^{-n})-\log_{2}(\beta_{1}))+2$ (229)
$\displaystyle=n(\log_{2}(1+\beta_{1}^{-1}\beta^{-n}))+2$ (230)
$\displaystyle\leq n\beta_{1}^{-1}\beta^{-n}+2$ (231)
$\displaystyle\overset{(a)}{\leq}\frac{\beta_{1}^{-1}}{\log(\beta)}\beta^{-\frac{1}{\log(\beta)}}+2=:D,$
(232)

where is a consequence of a study of the maximum of the functiono $t\mapsto
t\beta^{-t}$. By application of Lemma C.7, there exists $D^{\prime}>0$ such
that

$K[{\bf g}_{2}(s)|\lceil n\log_{2}(\beta)\rceil]\leq K[{\bf g}_{2}(s)|\lceil
n\log_{2}(\beta_{1})\rceil]+D^{\prime}.$ (233)

By (227) and (233), one gets

$K[{\bf g}_{2}(s)|\lceil n\log_{2}(\beta)\rceil]\leq K[{\bf
x}|n]+F(K[u_{n}])+c+D^{\prime},$ (234)

thereby finishing the proof. ∎

Previous theorem is the general form of Lemma 2.3, and one can immediately
infer it as a corollary.

######  Corollary B.4.

For all $s\in[0,1]$ and all computable $\beta\in(1,2)$, there exists $c>0$
such that

$K[{\bf g}_{2}(s)|\lceil n\log_{2}(\beta)\rceil]\leq K[{\bf x}|n]+c,\ \
\forall n\in\mathbf{N},\ \ \forall{\bf x}\in\Sigma_{\beta}(s).$ (235)

###### Proof.

Let $s\in[0,1]$ and a computable $\beta\in(1,2)$. As $\beta$ is computable, so
does $\beta-1$, and hence there exists $C>0$ such that $K[{\bf
g}_{2}(\beta-1)|n]\leq C$, for all $n\in\mathbf{N}$. The result follows
immediatly by application of Theorem B.3. ∎

##  Appendix C Miscellaneous results

######  Lemma C.1.

Let $\beta\in(1,2)$, and $\delta\in\left(0,\frac{2-\beta}{\beta}\right)$.
Then,

$\begin{array}[]{lrcl}g:&(1,\beta]&\to&\mathbf{R}\\\
&t&\mapsto&-\log_{t}\left(\frac{\delta}{2-t}\right)\end{array}$ (236)

is decreasing.

###### Proof.

Let $t\in(1,\beta]$. Then,

$\displaystyle g^{\prime}(t)$
$\displaystyle=\frac{\log(\delta)}{t\log(t)^{2}}-\frac{\frac{1}{2-t}\log(t)-\frac{1}{t}\log(2-t)}{\log(t)^{2}}$
(237)
$\displaystyle=\frac{1}{\log(t)^{2}}\left(\frac{-1}{2-t}+\frac{1}{t}(\log(\delta)-\log(2-t))\right).$
(238)

As $\delta\leq\frac{2-\beta}{\beta}<2-\beta\leq 2-t$, one has
$\log(\delta)-\log(2-t)<0$. From (238), it follows that

$g^{\prime}(t)<0,$ (239)

thereby finishing the proof. ∎

######  Lemma C.2.

For $\beta\in(1,2]$ $\delta_{\beta}$ be defined according to (25). Let
$x\in\\{0,1\\}^{\ast}$. Then,

$\begin{array}[]{lrcl}h:&(1,2]&\to&\mathbf{R}\\\
&\beta&\mapsto&\delta_{\beta}(x)\end{array}$ (240)

is $\frac{|x|(|x|+1)}{2}$-Lipschitz.

###### Proof.

Let $\beta_{1},\beta_{2}\in(1,2)$, and $x\in\\{0,1\\}^{\ast}$. Without loss of
generality, we assume that $\beta_{1}<\beta_{2}$.

$\displaystyle|\delta_{\beta_{1}}(x)-\delta_{\beta_{2}}(x)|=\left|\sum_{i=1}^{|x|}x_{i}\beta_{1}^{-i}-\sum_{i=1}^{|x|}x_{i}\beta_{2}^{-i}\right|=\left|\sum_{i=1}^{|x|}x_{i}\left(\beta_{1}^{-i}-\beta_{2}^{-i}\right)\right|\overset{(a)}{\leq}\sum_{i=1}^{|x|}\left|\beta_{1}^{-i}-\beta_{2}^{-i}\right|,$
(241)

where (a) is by $x_{i}\leq 1$. Note that for all $\beta\in(1,2)$,
$\left|\frac{\partial\beta^{-i}}{\partial\beta}\right|=\left|-i\beta^{-(i+1)}\right|\leq
i$. Then, by using the mean value theorem, one gets
$\left|\beta_{1}^{-i}-\beta_{2}^{-i}\right|\leq i|\beta_{1}-\beta_{2}|$. By
(241),

$|\delta_{\beta_{1}}(x)-\delta_{\beta_{2}}(x)|\leq\sum_{i=1}^{|x|}i|\beta_{1}-\beta_{2}|=\frac{|x|(|x|+1)}{2}|\beta_{1}-\beta_{2}|,$
(242)

thereby finishing the proof. ∎

######  Lemma C.3.

Let $\beta\in(1,2)$, $C\in(0,1)$, $L,N\in\mathbf{N}$,
$q_{i}:=1+\delta_{2}({\bf g}_{2}(\beta-1)_{1:L+Ni})$, and
$\xi_{i}:=\frac{1}{q_{i}^{i+1}}\prod_{j=0}^{i}q_{j}$, for all
$i\in\mathbf{N}_{0}$. If

$L\geq\frac{1}{2}\log_{2}(-\log(C)),$ (243)

then

$\xi_{i}\geq C,\ \text{for all}\ i\in\mathbf{N}_{0}.$ (244)

###### Proof.

Let $\beta\in(1,2)$, $L,N\in\mathbf{N}$, $q_{i}:=1+\delta_{2}({\bf
g}_{2}(\beta-1)_{1:L+Ni})$, and
$\xi_{i}:=\frac{1}{q_{i}^{i}}\prod_{j=0}^{i-1}q_{j}$, for all
$i\in\mathbf{N}_{0}$. Note that

$\log(\xi_{i})=\log\left(\frac{1}{q_{i}^{i+1}}\prod_{j=0}^{i}q_{j}\right)=\sum_{j=0}^{i}\log\left(\frac{q_{j}}{q_{i}}\right).$
(245)

We will show that if $n_{0}$ satisfies (243), then $\log(\xi_{i})\geq\log(C)$
for all $i\in\mathbf{N}$. A numerical approximation allows to show that

$\log(1+t)\geq 2t,\ \text{for all}\ t\in[-0.75,0].$ (246)

Now, let ${\bf x}:={\bf g}_{2}(\beta-1)_{L+1:\infty}$. Note that by Lemma A.3,

$\displaystyle q_{j}$ $\displaystyle=1+\delta_{2}({\bf
g}_{2}(\beta-1)_{1:L+Nj}=1+\delta_{2}({\bf
g}_{2}(\beta-1)_{1:L})+2^{-L}\delta_{2}({\bf x}_{1:Nj})$ (247)
$\displaystyle=q_{0}+2^{-L}\delta_{2}({\bf x}_{1:Nj}),$ (248)

for all $j\in\mathbf{N}$. Fix $i\in\mathbf{N}$.

$\displaystyle\log(\xi_{i})$
$\displaystyle=\sum_{j=0}^{i}\log\left(\frac{q_{j}}{q_{i}}\right)=\sum_{j=0}^{i}\log\left(\frac{q_{0}+2^{-L}\delta_{2}({\bf
x}_{1:Nj})}{q_{0}+2^{-L}\delta_{2}({\bf x}_{1:Ni})}\right)$ (249)
$\displaystyle=\sum_{j=0}^{i}\log\left(\frac{1+\frac{1}{2^{L}q_{0}}\delta_{2}({\bf
x}_{1:Nj})}{1+\frac{1}{2^{L}q_{0}}\delta_{2}({\bf x}_{1:Ni})}\right)$ (250)
$\displaystyle=\sum_{j=0}^{i}\log\left(\frac{1+\frac{1}{2^{L}q_{0}}(\delta_{2}({\bf
x}_{1:Nj})-\delta_{2}({\bf x}_{1:Ni})+\delta_{2}({\bf
x}_{1:Ni}))}{1+\frac{1}{2^{L}q_{0}}\delta_{2}({\bf x}_{1:Ni})}\right)$ (251)
$\displaystyle=\sum_{j=0}^{i}\log\left(1+\frac{\delta_{2}({\bf
x}_{1:j})-\delta_{2}({\bf
x}_{1:Ni})}{2^{L}q_{0}\left(1+\frac{1}{2^{L}q_{0}}\delta_{2}({\bf
x}_{1:Ni})\right)}\right)$ (252)
$\displaystyle=\sum_{j=0}^{i}\log\left(1+\frac{\delta_{2}({\bf
x}_{1:Nj})-\delta_{2}({\bf x}_{1:Ni})}{2^{L}q_{0}+\delta_{2}({\bf
x}_{1:Ni})}\right).$ (253)

Note that, for all $i,j\in\mathbf{N}$, $j\leq i$ implies that

$0\geq\frac{\delta_{2}({\bf x}_{1:Nj})-\delta_{2}({\bf
x}_{1:i})}{2^{L}q_{0}+\delta_{2}({\bf
x}_{1:Ni})}\geq\frac{-2^{-L-Nj}}{2^{L}q_{0}+\delta_{2}({\bf
x}_{1:Ni})}\overset{(a)}{\geq}-\frac{2^{-L-Nj}}{2^{L}q_{0}}\overset{(b)}{\geq}-\frac{1}{2^{2L}}\overset{(c)}{\geq}-0.75,$
(254)

where (a) is by $\delta_{2}({\bf x}_{1:Ni})\geq 0$, (b) follows from
$q_{0}\geq 1$ and $2^{-Nj}\leq 1$, and (c) is a consequence of $L\geq 1$.
Therefore,

$\displaystyle\log(\xi_{i})$ $\displaystyle\overset{(\ref{eq:other form xi
i})}{=}\sum_{j=0}^{i}\log\left(1+\frac{\delta_{2}({\bf
x}_{1:Nj})-\delta_{2}({\bf x}_{1:Ni})}{2^{L}q_{0}+\delta_{2}({\bf
x}_{1:Li})}\right)\overset{(\ref{eq:minoration de log 1 +
x})}{\geq}2\sum_{j=0}^{i}\frac{\delta_{2}({\bf x}_{1:Nj})-\delta_{2}({\bf
x}_{1:Ni})}{2^{L}q_{0}+\delta_{2}({\bf
x}_{1:Ni})}\overset{(\ref{eq:simplification of the xi i
terms})}{\geq}-2^{-2L}.$

It immediately follows that $L\geq\frac{1}{2}\log_{2}(-\log(C))$ implies
$\xi_{i}\geq C$. ∎

######  Lemma C.4.

[13, Example 2.1.5] There exists $C_{+}>0$, such that

$\displaystyle K[xx^{\prime}]$ $\displaystyle\leq
K[x]+F(K[x^{\prime}])+C_{+},\ \ \text{for all}\
x,x^{\prime}\in\\{0,1\\}^{\ast},$ (255)

and

$\displaystyle K[\langle x,x^{\prime}\rangle]$ $\displaystyle\leq
K[x]+F(K[x^{\prime}])+C_{+},\ \ \text{for all}\
x,x^{\prime}\in\\{0,1\\}^{\ast},$ (256)

where $F:t\mapsto t+2\log_{2}(t)$.

######  Lemma C.5.

[13, Theorem 2.1.2] There exists $C_{||}>0$, such that

$K[x]\leq|x|+C_{||},\ \ \text{for all}\ x\in\\{0,1\\}^{\ast}.$ (257)

######  Lemma C.6.

Let $N\in\mathbf{N}$, ${\bf x}\in\\{0,1\\}^{\omega}$,
$(u_{n})_{n\in\mathbf{N}}$ a sequence of integers. Then,

$K[{\bf x}|Nn]\leq u_{n},\ \forall n\in\mathbf{N}\Rightarrow\exists C>0\ s.t.\
K[{\bf x}|n]\leq u_{\lfloor n/N\rfloor}+C,\ \forall n\in\mathbf{N}.$ (258)

###### Proof.

Let $N\in\mathbf{N}$, ${\bf x}\in\\{0,1\\}^{\omega}$,
$(u_{n})_{n\in\mathbf{N}}$ a sequence of integers, and suppose that $K[{\bf
x}|Nn]\leq u_{n},\ \forall n\in\mathbf{N}$. Fix $n\in\mathbf{N}$. Then,
$k:=\lfloor n/N\rfloor$ satisfies $n=kN+(n-kN)$, where $n-kN\leq N$. Then,

$\displaystyle K[{\bf x}|n]$ $\displaystyle=K[{\bf x}_{1:n}]=K[{\bf
x}_{1:kN}{\bf x}_{1:(n-kN)}]$ (259) $\displaystyle\overset{(\ref{eq:simple
inequality on concatenation of sequences})}{\leq}K[{\bf x}_{1:kN}]+K[{\bf
x}_{1:(n-kN)}]+2\log_{2}(K[{\bf x}_{1:(n-kN)}])+C_{+}$ (260)
$\displaystyle\overset{(a)}{\leq}K[{\bf
x}_{1:kN}]+N+C_{||}+2\log_{2}(N+C_{||})+C_{+}$ (261)
$\displaystyle\overset{(b)}{\leq}u_{k}+N+C_{||}+2\log_{2}(N+C_{||})+C_{+}$
(262) $\displaystyle=u_{\lfloor
n/N\rfloor}+N+C_{||}+2\log_{2}(N+C_{||})+C_{+},$ (263)

where (a) follows from (257) and $n-kN\leq N$, and (b) is by $K[{\bf
x}|Nk]\leq u_{k}$. We set $C:=N+C_{||}+2\log_{2}(N+C_{||})+C_{+}$, thereby
finishing the proof. ∎

######  Lemma C.7.

Let ${\bf x}\in\\{0,1\\}^{\omega}$, $(i_{n})_{n\in\mathbf{N}}$ and $(j_{n})$
be two increasing sequences of natural numbers. Suppose that there exists
$M>0$ such that $|i_{n}-j_{n}|\leq M$, for all $n\in\mathbf{N}$. Then, there
exists $C>0$, such that

$K[{\bf x}|i_{n}]\leq K[{\bf x}|j_{n}]+C,\ \text{for all}\ n\in\mathbf{N}.$
(264)

###### Proof.

Let ${\bf x}\in\\{0,1\\}^{\omega}$, $(i_{n})_{n\in\mathbf{N}}$ and $(j_{n})$
be two increasing sequences of natural numbers. Suppose that there exists
$M>0$ such that $|i_{n}-j_{n}|\leq M$, for all $n\in\mathbf{N}$. Fix
$n\in\mathbf{N}$, and let $x:=10^{j_{n}+M-i_{n}}$. Then, one can build an
effective algorithm $\phi:\\{0,1\\}^{\ast}\to\\{0,1\\}^{\ast}$, which on input
${\bf x}_{1:j_{n}+M}x$, which uses $x$ to delete the $j_{n}+M-i_{n}$ last bits
of ${\bf x}_{1:j_{n}+M}$, and outputs the resulting sequence. Then, $\phi({\bf
x}_{1:j_{n}+M}x)=\phi({\bf x}_{1:i_{n}})$. By Lemma 1.1, there exists
$c_{\phi}>0$ such that

$\displaystyle K[{\bf x}|i_{n}]$ $\displaystyle=K[{\bf x}_{1:i_{n}}]\leq