# Effective Continued Fraction Dimension versus Effective Hausdorff Dimension
of Reals

Satyadev Nandakumar  Department of Computer Science and Engineering
Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India.  Akhil S
Department of Computer Science and Engineering
Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India.  Prateek
Vishnoi  Department of Computer Science and Engineering
Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India.

###### Abstract

We establish that constructive continued fraction dimension originally defined
using $s$-gales [23] is robust, but surprisingly, that the effective continued
fraction dimension and effective (base-$b$) Hausdorff dimension of the same
real can be unequal in general.

We initially provide an equivalent characterization of continued fraction
dimension using Kolmogorov complexity. In the process, we construct an optimal
lower semi-computable $s$-gale for continued fractions. We also prove new
bounds on the Lebesgue measure of continued fraction cylinders, which may be
of independent interest.

We apply these bounds to reveal an unexpected behavior of continued fraction
dimension. It is known that feasible dimension is invariant with respect to
base conversion [8]. We also know that Martin-Löf randomness and computable
randomness are invariant not only with respect to base conversion, but also
with respect to the continued fraction representation [23]. In contrast, for
any $0<\varepsilon<0.5$, we prove the existence of a real whose effective
Hausdorff dimension is less than $\varepsilon$, but whose effective continued
fraction dimension is greater than or equal to $0.5$. This phenomenon is
related to the “non-faithfulness” of certain families of covers, investigated
by Peres and Torbin [25] and by Albeverio, Ivanenko, Lebid and Torbin [1].

We also establish that for any real, the constructive Hausdorff dimension is
at most its effective continued fraction dimension.

##  1 Introduction

The concept of an individual random sequence, first defined by Martin-Löf
using constructive measure [18], is well-established and mathematically robust
- very different approaches towards the definition identify precisely the same
sequences as random. These include Kolmogorov incompressibility (Levin [10],
Chaitin [3]) and unpredictability by martingales [27]. While the theory of
Martin-Löf randomness _classifies_ sequences into random and non-random, it
does not _quantify_ the information rate in a non-random sequence. Lutz
effectivized the classical notions of Hausdorff and packing dimensions [15],
surprisingly extending it to individual infinite binary sequences [16],
yielding a notion of information density in sequences. This definition also
has several equivalent definitions in terms of Kolmogorov compression rates
[19], unpredictability by $s$-gales, and using covers [15], [16]. These
definitions have led to a rich variety of applications in various domains of
computability and complexity theory (see for example, Downey and Hirschfeldt
[5], Nies [24]).

Recently, settings more general than the Cantor space of infinite binary (or
in general, infinite sequences from a finite alphabet) have been studied by
Lutz and Mayordomo [17], and Mayordomo [20], [21]. Prominent among them is
Mayordomo’s definition of effective Hausdorff dimension for a very general
class of metric spaces [20], [21]. Nandakumar and Vishnoi [23] and Vishnoi
[31] define the notion of effective dimension of continued fractions, which
involves a countably infinite alphabet, and is thus a setting which cannot be
studied using Mayordomo’s framework. This latter setting is interesting
topologically since the space of continued fractions is non-compact, and
interesting measure-theoretically since the natural shift invariant measure,
the Gauss measure, is a non-product measure.

Nandakumar and Vishnoi [23] use the notion of an $s$-gale on the space of
continued fractions to define effective dimension. Vishnoi [31] introduced the
notion of Kolmogorov complexity of finite continued fraction strings using a
one to one binary encoding. Vishnoi [31] also shows that the notion of
Kolmogorov complexity is invariant under computable 1-1 encodings, upto an
additive constant.

In this work, we first establish the mathematical robustness of the notion of
effective dimension, by proving an equivalent characterization using
Kolmogorov complexity of continued fractions. The characterization achieves
the necessary equivalence by choosing a binary encoding of continued fractions
which has a compelling geometric intuition, and then applying Mayordomo’s
characterization of effective (binary) Hausdorff dimension using Kolmogorov
complexity [19] . In the process, analogous to the notion of an optimal
constructive supergale on the Cantor space defined by Lutz [16], we provide
the construction of a lower semi-computable $s$-gale that is optimal for
continued fractions. We also prove new bounds on the Lebesgue measure of
continued fraction cylinders using the digits of the continued fraction
expansion, a result which may be of independent interest.

The topological and measure-theoretic intricacies involved in this setting
imply that some, but not all, “natural” properties of randomness and dimension
carry over from the binary setting. For example, while Martin-Löf and
computable randomness are invariant with respect to the conversion between the
base-$b$ and continued fraction expansion of the same real [22], [23],
Vandehey [29] and Scheerer [26] show that other notions of randomness like
absolute normality and normality for continued fractions are not identical.

Staiger [28] showed that the Kolmogorov complexity of a base $b$ expansion of
a real $\alpha,0\leq\alpha\leq 1,$ is independent of the chosen base $b$.
Aligning with this, Hitchcock and Mayordomo [8] establish that feasible
dimension of a real is the same when converting between one base to another.
Hitherto, it was unknown whether effective dimension is invariant with respect
to conversion between base-$b$ and continued fraction representations. Since
we can convert between the representations efficiently, it is possible that
these are equal. We show this is true in one direction, that the effective
base $b$ dimension is a lower bound for effective continued fraction
dimension.

However, using the technique of diagonalization against the optimal lower
semicomputable continued fraction $s$-gale and using set covering techniques
used in recent works by Peres and Torbin [25], Albeverio, Ivanenko, Lebid and
Torbin [1] and Albeverio, Kondratiev, Nikiforov and Torbin [2] to show the
“non-faithfulness” of certain families of covers, we show that the reverse
direction does not hold, in general. We prove the following result: for every
$0<\varepsilon<0.5$, there is a real whose effective (binary) Hausdorff
dimension is less than $\varepsilon$ while its effective continued fraction
dimension is at least 0.5. By the result of Hitchcock and Mayordomo [8], this
also implies that the effective base-$b$ dimension of this real is less than
$\varepsilon$ in every base-$b$, $b\geq 2$. Thus, surprisingly, there is a
sharp gap between the effective (base-$b$) dimension of a real and its
effective continued fraction dimension, highlighting another significant
difference in this setting.

##  2 Preliminaries

We denote the binary alphabet by $\Sigma$. The set of strings of a particular
length $n$ is denoted $\Sigma^{n}$. The set of all finite binary strings is
denoted $\Sigma^{*}$ and infinite binary sequences is denoted
$\Sigma^{\infty}$. For a binary string $v\in\Sigma^{n}\setminus\\{0^{n}\cup
1^{n}\\}$, $v-1$ denotes the string occurring just before $v$
lexicographically, and $v+1$ the string occurring just after $v$
lexicographically. We use $\mathbb{N}$ to denote the set of positive integers.
The set of finite continued fractions is denoted $\mathbb{N}^{*}$ and the set
of all infinite continued fractions, as $\mathbb{N}^{\infty}$.

We adopt the notation $[a_{1},a_{2},\dots]$ for the continued fraction

$\displaystyle\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\cdots}}$

and similarly, $[a_{1},a_{2},\dots,a_{n}]$ for finite continued fractions.

If a finite binary string $x$ is a prefix of a finite string $z$ or an
infinite binary sequence $Z$, then we denote this by $x\sqsubseteq z$ or
$x\sqsubseteq Z$ respectively. If $x$ is a proper prefix of a finite string
$z$, we denote it by $x\sqsubset z$. We adopt the same notation for denoting
that a finite continued fraction $v$ is a prefix of another continued
fraction. For a $v\in\mathbb{N}^{*}$, the _cylinder set_ of $v$, denoted
$C_{v}$, is defined by $C_{v}=\\{Y\in\mathbb{N}^{\infty}\mid v\sqsubset Y\\}$.
For a $w\in\Sigma^{*}$, $C_{w}$ is defined similarly. For a continued fraction
string $v=[a_{1}\dots a_{n}]$, $P(v)$ denotes the string $[a_{1},\dots
a_{n-1}]$. $\lambda$ denotes the empty string and we define
$P(\lambda)=\lambda$.

For $v\in\mathbb{N}^{*}$, $\mu(v)$ refers to the Lebesgue measure of the
continued fraction cylinder $C_{v}$. $\gamma(v)$ refers to the Gauss measure
of the continued fraction cylinder $C_{v}$, defined by
$\gamma(v)=\int_{C_{v}}\frac{1}{1+x}~{}dx$. We use the same notation for a
binary cylinder $w\in\Sigma^{*}$. It is well-known that the Gauss measure is
absolutely continuous with respect to the Lebesgue measure, and is invariant
with respect to the left-shift transformation on continued fractions (see for
example, [4], or [6]). Wherever there is no scope for confusion, for a
$v\in\mathbb{N}^{*}$, we use $\mu(v)$ and $\gamma(v)$ to represent
$\mu(C_{v})$ and $\gamma(C_{v})$ respectively. The same holds for a
$v\in\Sigma^{*}$. We also use the notation $\mu^{s}(v)$ and $\gamma^{s}(v)$ to
denote $(\mu(v))^{s}$ and $(\gamma(v))^{s}$ respectively. For a continued
fraction string $v=[a_{1},\dots,a_{n}]$, we call $n$ as the rank of $v$, and
we denote it using $rank(v)$. $[v,i]$ denotes the continued fraction
$[a_{1},\dots a_{n},i]$. For an infinite continued fraction string
$Y=[a_{1},a_{2},\dots]$, $Y\upharpoonleft n$ denotes the continued fraction
string corresponding to the first n entries of $Y$, that is $Y\upharpoonleft
n=[a_{1},a_{2}\dots a_{n}]$. For $k\in\mathbb{N}$, $\mathbb{N}^{\leq k}$
refers to the set of continued fraction strings having rank less than or equal
to $k$. All logarithms in the work have base 2, unless specified otherwise.
For any sets $A$ and $B$, $A\Delta B$ denotes the symmetric set difference
operator, defined by $(A\setminus B)\cup(B\setminus A)$. In this work, for
ease of notation, $Y\in\mathbb{N}^{*}$ denotes an infinite continued fraction
and $X\in\Sigma^{\infty}$ denotes an infinite binary sequence.

###  2.1 Constructive dimension of binary sequences

Lutz [16] defines the notion of effective (equivalently, constructive)
dimension of an individual infinite binary sequence using the notion of the
success of $s$-gales.

######  Definition 1 (Lutz [16]).

For $s\in[0,\infty)$, a binary $s$-gale is a function
$d:\Sigma^{*}\to[0,\infty)$ such that $d(\lambda)<\infty$ and for all
$w\in\Sigma^{*}$,
$d(w)[\mu(C_{w})]^{s}=\sum_{i\in\\{0,1\\}}d(wi)[\mu(C_{wi})]^{s}.$

The _success set_ of $d$ is
$S^{\infty}(d)=\left\\{X\in\mathbb{N}^{\infty}\mid\limsup\limits_{n\to\infty}d(X\upharpoonright
n)=\infty\right\\}$.

For $\mathcal{F}\subseteq[0,1]$, $\mathcal{G}(\mathcal{F})$ denotes the set of
all $s\in[0,\infty)$ such that there exists a lower semicomputable binary
$s$-gale $d$ with $\mathcal{F}\subseteq S^{\infty}(d)$.

The _constructive dimension_ or _effective Hausdorff dimension_ of
$\mathcal{F}\subseteq[0,1]$ is
$\mathrm{cdim}(\mathcal{F})=\inf\mathcal{G}(\mathcal{F})$ and the constructive
dimension of a sequence $X\in\Sigma^{\infty}$ is
$\mathrm{cdim}(X)=\mathrm{cdim}(\\{X\\})$.

##  3 Effective Continued Fraction Dimension using $s$-gales

Nandakumar and Vishnoi [23] formulate the notion of effective dimension of
continued fractions using the notion of lower semicomputable continued
fraction $s$-gales. Whereas a binary $s$-gale bets on the digits of the binary
expansion of a number, a continued fraction $s$-gales places bets on the
digits of its continued fraction expansion.

######  Definition 2 (Nandakumar, Vishnoi [23]).

For $s\in[0,\infty)$, a continued fraction $s$-gale is a function
$d:\mathbb{N}^{*}\to[0,\infty)$ such that $d(\lambda)<\infty$ and for all
$w\in\mathbb{N}^{*}$, the following holds.

$\displaystyle
d(w)[\gamma(C_{w})]^{s}=\sum_{i\in\mathbb{N}}d(wi)[\gamma(C_{wi})]^{s}.$

The _success set_ of $d$ is
$S^{\infty}(d)=\left\\{Y\in\mathbb{N}^{\infty}\mid\limsup\limits_{n\to\infty}d(Y\upharpoonright
n)=\infty\right\\}$.

In this paper, we deal with the notion of effective or equivalently,
constructive dimension. In order to effectivize the notion of $s$-gales, we
require them to be _lower semicomputable_.

######  Definition 3.

A function $d:\mathbb{N^{*}}\longrightarrow[0,\infty)$ is called _lower
semicomputable_ if there exists a total computable function
$\hat{d}:\mathbb{N^{*}}\times\mathbb{N}\longrightarrow\mathbb{Q}\cap[0,\infty)$
such that the following two conditions hold.

  * •

Monotonicity : For all $w\in\mathbb{N^{*}}$ and for all $n\in\mathbb{N}$, we
have $\hat{d}(w,n)\leq\hat{d}(w,n+1)\leq d(w)$.

  * •

Convergence : For all $w\in\mathbb{N^{*}}$,
$\lim\limits_{n\to\infty}\hat{d}(w,n)=d(w)$.

For $\mathcal{F}\subseteq[0,1]$, $\mathcal{G}_{CF}(\mathcal{F})$ denotes the
set of all $s\in[0,\infty)$ such that there exists a lower semicomputable
continued fraction $s$-gale $d$ with $\mathcal{F}\subseteq S^{\infty}(d)$.

######  Definition 4 (Nandakumar, Vishnoi [23]).

The _effective continued fraction dimension_ of $\mathcal{F}\subseteq[0,1]$ is

$\displaystyle\mathrm{cdim}_{CF}(\mathcal{F})=\inf\mathcal{G}_{CF}(\mathcal{F}).$

The _effective continued fraction dimension_ of a sequence
$Y\in\mathbb{N}^{\infty}$ is defined by $\mathrm{cdim}_{CF}(\\{Y\\})$, the
effective continued fraction dimension of the singleton set containing $Y$.

###  3.1 Conversion of binary $s$-gales into continued fraction $s$-gales

In this subsection, from a continued fraction $s^{\prime}$-gale
$d:\mathbb{N}^{*}\to[0,\infty)$, for any $s>s^{\prime}$, we construct a binary
$s$-gale $h:\Sigma^{*}\to[0,\infty)$ which succeeds on all the reals on which
$d$ succeeds. The construction proceeds in multiple steps. We first mention
some technical lemmas which we use in the proof.

The following lemma is an easy consequence of the fact that the Gauss measure
is absolutely continuous with respect to the Lebesgue measure (see for
example, Nandakumar and Vishnoi [23]).

######  Lemma 1.

For any interval $B\subseteq(0,1)$, we have

$\frac{1}{2\ln 2}\mu(B)\leq\gamma(B)\leq\frac{1}{\ln 2}\mu(B).$

In the construction that follows, we formulate betting strategies on binary
cylinders based on continued fraction cylinders. In order to do this
conversion, we require the following bounds on the relationships between the
lengths of continued fraction cylinders and binary cylinders.

######  Lemma 2 (Nandakumar, Vishnoi [23]).

For any $0\leq a<b\leq 1$, let
$\left[\frac{m}{2^{k}},\frac{m+1}{2^{k}}\right)$, where $0\leq m\leq 2^{k}-1$
be one of the largest dyadic intervals which is a subset of $[a,b)$, then
$\frac{1}{2^{k}}\geq\frac{1}{4}(b-a)$.

######  Lemma 3 (Falconer [7]).

For any $0\leq a<b\leq 1$, let
$\left[\frac{m}{2^{k}},\frac{m+1}{2^{k}}\right)$ ,
$\left[\frac{m+1}{2^{k}},\frac{m+2}{2^{k}}\right)$, where $0\leq m\leq
2^{k}-2$, be the smallest consecutive dyadic intervals whose union covers
$[a,b)$. Then $\frac{1}{2^{k}}\leq 2(b-a)$.

###### Proof.

Let $j=\lfloor-\log_{2}(b-a)\rfloor$. Since $(b-a)/2<2^{-j}$, it follows that
at most two dyadic rationals of the form $m/2^{j}$, $0\leq m<2^{j}$ is in
$(a,b)$. Thus, three dyadic intervals of length $\frac{1}{2^{j}}$ cover the
interval $[a,b]$. Hence two dyadic intervals of length $\frac{2}{2^{j}}$ cover
$[a,b]$. Since $2^{-j}\leq(b-a)$, it follows that $\frac{2}{2^{j}}\leq
2(b-a)$. ∎

The following lemma is a generalization of the Kolmogorov inequality for
continued fraction martingales (Vishnoi [30]) to $s$-gales. The lemma states
that an equality holds in the case of decompositions using prefix-free
subcylinder sets upto a finite depth.

######  Lemma 4.

Let $d:\mathbb{N}^{*}\rightarrow[0,\infty)$ be a continued fraction $s$-gale.
Let $v\in\mathbb{N}^{*}$ and for some $k\in\mathbb{N}$, let $A$ be a prefix
free set of elements in $\mathbb{N}^{\leq k}$ such that $\cup_{w\in
A}C_{w}=C_{v}$. Then, we have $d(v)\gamma^{s}(v)=\sum_{w\in
A}d(w)\gamma^{s}(w)$.

###### Proof.

We prove this result by induction on $k$, the maximum rank of an element in
$A$. We first observe that for any $v\in\mathbb{N}^{*}$, if $C_{v}=\cup_{w\in
A}C_{w}$, then for all $w\in A$, $v\sqsubseteq w$. Therefore, we have that
$k\geq rank(v)$.

Let’s consider the case when $k=rank(v)$. In this case, the only possibility
is that $A=\\{v\\}$ and therefore the lemma holds trivially.

Assume that the lemma holds for any $k\in\mathbb{N}$ such that $k\geq
rank(v)$. Let $A$ be a prefix free set of elements in $\mathbb{N}^{\leq k+1}$
such that $\cup_{w\in A}C_{w}=C_{v}$.

Consider the sets, $P=\\{w\in A~{}|~{}rank(w)=k+1\\}$ and
$P^{\prime}=\\{u\in\mathbb{N}^{k}~{}|~{}[u,i]\in P\text{ for some
}i\in\mathbb{N}\\}$.

Now since $\cup_{w\in A}~{}C_{w}=C_{v}$ and $A$ is prefix free, we have that
for all $u\in P^{\prime}$, and for all $i\in\mathbb{N}$, $[u,i]\in P$.

Since $d$ is a continued fraction $s$-gale, it follows that,

$\sum_{u\in P^{\prime}}d(u)\gamma^{s}(u)=\sum_{w\in P}d(w)\gamma^{s}(w)$

Also, note that since for any $u\in\mathbb{N^{*}}$,
$C_{u}=\cup_{i\in\mathbb{N}}~{}C_{[u,i]}$, we have

$\cup_{u\in P^{\prime}}~{}C_{u}=\cup_{w\in P}~{}C_{w}.$

Construct the $A^{\prime}=P^{\prime}\cup(A-P)$. We have that the elements in
$A^{\prime}$ are prefix free and $\cup_{w\in A^{\prime}}C_{w}=C_{v}$. Since
the maximum rank of an element in $A^{\prime}$ is $k$, we have that,

$d(v)\gamma^{s}(v)=\sum_{w\in A^{\prime}}d(w)\gamma^{s}(w)$

Since $P^{\prime}\cap(A-P)=\phi$, it follows that

$d(v)\gamma^{s}(v)=\sum_{w\in
A-P}d(w)\gamma^{s}(w)+\sum_{\begin{subarray}{c}u\in
P^{\prime}\end{subarray}}d(u)\gamma^{s}(u).$

Using $\sum_{u\in P^{\prime}}d(u)\gamma^{s}(u)=\sum_{w\in
P}d(w)\gamma^{s}(w)$, we have

$d(v)\gamma^{s}(v)=\sum_{w\in
A-P}d(w)\gamma^{s}(w)+\sum_{\begin{subarray}{c}w\in
P\end{subarray}}d(w)\gamma^{s}(w).$

From which we have

$d(v)\gamma^{s}(v)=\sum_{w\in A}d(w)\gamma^{s}(w).$

∎

In the construction of a binary $s$-gale from continued fraction gales, The
first step is the following decomposition of a binary cylinder into a set of
prefix free continued fraction cylinders.

######  Lemma 5 (Vishnoi [30]).

For every $w\in\Sigma^{*}$, there exists a set $I(w)\subseteq\mathbb{N}^{*}$
and a constant $k\in\mathbb{N}$ such that,

  1. 1.

$y\in\mathbb{N}^{\leq k}$ for every $y\in I(w)$.

  2. 2.

$(\cup_{y\in I(w)}C_{y})\Delta C_{w}\subseteq\\{\inf(C_{w}),\sup(C_{w})\\}$

  3. 3.

$I(w0)\cup I(w1)=I(w)$

  4. 4.

$I(w0)\cap I(w1)=\phi$

Moreover, given $w\in\Sigma^{*}$, Vishnoi [30] gives a division algorithm to
compute $I(w)$. It is also clear from the division algorithm that for all
$w\in\Sigma^{*}$, there exists a $u\in I(w)$ such that for all $v\in(I(w0)\cup
I(w1))\setminus I(w)$, we have $u\sqsubset v$. This $u\in I(w)$ is the
continued fraction cylinder for which the mid point of $w$, $m(w)$ is an
interior point in $C_{u}$ and therefore gets divided.

From a continued fraction martingale, Vishnoi [30] uses the decomposition
$I(w)$ to construct a binary martingale that places the same aggregate bets on
an interval. We generalize this construction to the setting of $s$-gales.
Given a continued fraction $s^{\prime}$-gale $d:\mathbb{N}^{*}\to[0,\infty)$,
using the decomposition $I(w)$, we construct a binary $s^{\prime}$-gale
$H_{d}$ from $d$.

######  Definition 5.

Given any continued fraction $s^{\prime}$-gale
$d:\mathbb{N}^{*}\to[0,\infty)$, define the _Proportional binary
$s^{\prime}$-gale_ of $d$, $H_{d}:\Sigma^{*}\to[0,\infty)$ as follows:

$H_{d}(w)=\sum_{{y\in
I(w)}}d(y)\left(\frac{\gamma(y)}{\mu(w)}\right)^{s^{\prime}}.$

For a $w\in\Sigma^{*}$, let $I^{\prime}(w)=I(w0)\cup I(w1)$. Then we have,

$\displaystyle H_{d}(w0)+H_{d}(w1)=2^{s^{\prime}}\sum_{y\in
I^{\prime}(w)}d(y)\Big{(}\frac{\gamma(y)}{\mu(w)}\Big{)}^{s^{\prime}}.$

Let $u\in I(w)$ such that for all $v\in I^{\prime}(w)\setminus I(w)$,
$u\sqsubset v$. Hence, by Lemma 4, it follows that $\sum_{y\in
I^{\prime}(w)}d(y)\gamma^{s^{\prime}}(y)=\sum_{y\in
I(w)}d(y)\gamma^{s^{\prime}}(y)$. Therefore, we have
$H_{d}(w0)+H_{d}(w1)=2^{s^{\prime}}H_{d}(w)$, so $H_{d}$ is an
$s^{\prime}$-gale. Also as $\gamma(\lambda)=1$, we have that
$H_{d}(\lambda)=d(\lambda)$.

As $I(w)$ is computably enumerable, it follows that $H_{d}$ is lower
semicomputable if $d$ is lower semicomputable.

The construction by Vishnoi [30] proceeds using the _savings-account trick_
for martingales. In the setting of $s$-gales, however, the concept of a
savings account does not work directly. Therefore, we require additional
constructions in this setting.

Using ideas from the construction given in Lemma 3.1 in Hitchcock and
Mayordomo [8], we construct a “smoothed” $s$-gale
$H_{h}:\Sigma^{*}\to[0,\infty)$ from the proportional $s^{\prime}$-gale
constructed in Definition 5.

######  Definition 6.

For a $w\in\Sigma^{*}$, and an $n>|w|$, we define

$\displaystyle F_{n}(w)$ $\displaystyle=\\{u\in\\{0^{n}\cup 1^{n}\\}\mid
w\sqsubseteq{u}\\}\;\cup\;\\{u\in\Sigma^{n}\setminus\\{0^{n}\cup 1^{n}\\}\mid
w\sqsubseteq u+1\text{ and }w\sqsubseteq u-1\\},$ $\displaystyle H_{n}(w)$
$\displaystyle=\\{u\in\Sigma^{n}\mid w\sqsubseteq{u}\text{ or }w\sqsubseteq
u+1\text{ or }w\sqsubseteq u-1\\}\setminus F_{n}.$

######  Definition 7.

Given an $s^{\prime}$-gale $h:\Sigma^{*}\to[0,\infty)$, for any $s>s^{\prime}$
and for each $n\in\mathbb{N}$, define:

$\displaystyle h_{n}(w)=\begin{cases}\;\;2^{s|w|}\;\bigg{(}\;\sum\limits_{u\in
H_{n}(w)}\frac{1}{2}\;h(u)\;+\;\sum\limits_{u\in
F_{n}(w)}h(u)\bigg{)}&\text{if }|w|<n\\\ \\\
\;\;{2^{(s-1)(|w|-n+1)}}\;\;h_{n}(w[0\dots n-2])&\text{otherwise.}\end{cases}$

Define $S_{h}:\Sigma^{*}\to[0,\infty)$ by

$S_{h}(w)=\sum\limits_{n=0}^{\infty}2^{-sn}\;h_{n}(w).$

We call $S_{h}$ as the _smoothed $s$-gale of $h$_.

Consider a string $w\in\Sigma^{n}$ other than $0^{n}$ and $1^{n}$. In $h_{n}$,
a factor of half the capital of $w$ gets assigned to it’s immediate parent
$w^{\prime}$. The other half is assigned to the neighbor of $w^{\prime}$ to
which $w$ is adjacent to.

It is straightforward to verify that each $h_{n}$ is an $s$-gale. $S_{h}$ is a
combination of $s$-gales, and hence is a valid $s$-gale. Note that
$h_{n}(\lambda)=\sum_{u\in\Sigma^{n}}h(u)=2^{s^{\prime}n}$. Therefore as
$s>s^{\prime}$, $S_{h}(\lambda)=\sum_{n\in\mathbb{N}}2^{(s^{\prime}-s)n}$ is
finite. If $h$ is lower semicomputable, it follows that $S_{h}$ is lower
semicomputable.

Combining the constructions given in the section, for any $s>s^{\prime}$, we
show the construction of a binary $s$-gale from a continued fraction
$s^{\prime}$-gale, satisfying certain bounds on the capital acquired.

This construction helps to establish a lower bound on effective continued
fraction dimension using effective binary dimension. It is also central in
formulating a Kolmogorov complexity characterization for continued fraction
dimension.

######  Lemma 6.

For $s^{\prime}\in(0,\infty)$, let $d:\mathbb{N}^{*}\to[0,\infty)$ be a
continued fraction $s^{\prime}$\- gale. Then, for any $s>s^{\prime}$, there
exists a binary $s$-gale $h:\Sigma^{*}\to[0,\infty)$ such that for any
$v\in\mathbb{N}^{*}$ and for any $b\in\Sigma^{*}$ such that $C_{b}\cap
C_{v}\neq\phi$ and $\frac{1}{16}\mu(v)\leq\mu(b)\leq 2\mu(v)$, we have

$h(b)\geq c_{s}d(v),$

where $c_{s}$ is a constant that depends on $s$. Moreover, if $d$ is lower
semicomputable, then $h$ is lower semicomputable.

###### Proof.

Given an $s^{\prime}$-gale $d:\mathbb{N}^{*}\to[0,\infty)$, let
$h^{\prime}=H_{d}$, the proportional binary $s^{\prime}$-gale of $d$ given in
Definition 5.

For a $v\in\mathbb{N}^{*}$, consider the smallest $w_{1},w_{2}\in\Sigma^{*}$
such that $C_{v}\subseteq C_{w_{1}}\cup C_{w_{2}}$. Also we can see that there
exists a $S\subseteq I(w_{1})\cup I(w_{2})$ such that $C_{v}=\cup_{u\in
S}C_{u}$.

Therefore from Lemma 4, we get $h^{\prime}(w_{1})+h^{\prime}(w_{2})\geq
d(v)\frac{\gamma^{s^{\prime}}(v)}{\mu^{s^{\prime}}(w_{1})}$. From Lemma 3, we
get that $\mu(w_{1})=\mu(w_{2})\leq 2\mu(v)$. Also from Lemma 1, we have that
$\gamma(v)\leq(ln2)^{-1}\mu(v)$. Therefore,
$h^{\prime}(w_{1})+h^{\prime}(w_{2})\geq(2ln2)^{-s^{\prime}}d(v)$. Now for any
$s>s^{\prime}$, we have that $h^{\prime}(w_{1})+h^{\prime}(w_{2})\geq
c_{1}.d(v)$, where $c_{1}=1/(2ln2)^{s}$.

Now for any $s>s^{\prime}$, consider the smoothed $s$-gale $h=S_{H_{d}}$ of
the $s^{\prime}$-gale $H_{d}$ given in Definition 6.

Let $|w_{1}|=n$ , and let $W_{1}=P(P(w_{1}))$ be the parent cylinder of parent
of $w_{1}$. Similarly let $W_{2}=P(P(w_{2}))$. We see that for any
$W\in\\{W_{1},W_{2}\\}$, $h_{n}(W)\geq
2^{s(n-2)}\frac{h^{\prime}(w_{1})+h^{\prime}(w_{2})}{2}\geq
c_{2}.2^{sn}.d(v)$, where $c_{2}=2^{-(2s+1)}c_{1}$.

Take any any $b\in\Sigma^{*}$ such that $C_{b}\cap C_{v}\neq\phi$ and
$2.\mu(v)\geq\mu(b)\geq\frac{1}{16}\mu(v)$. Since $\mu(b)\leq 2\mu(v)$ and
$\mu(v)\leq 2.\mu(w_{1})$, it follows that for some $W\in\\{W_{1},W_{2}\\}$,
$W\sqsubseteq b$. Also since $\mu(b)\geq\frac{1}{16}\mu(v)$, we have that,
$\mu(b)\geq\frac{1}{32}\mu(w_{1})$.

Therefore, we have that $h_{n}(b)\geq 2^{5(s-1)}h_{n}(W)\geq
c_{3}.2^{sn}.d(v)$, where $c_{3}=c_{2}.2^{5(s-1)}$.

Since $h(b)\geq 2^{-sn}h_{n}(b)$, we have that $h(b)\geq c_{3}.d(v)$. ∎

##  4 Kolmogorov Complexity characterization of Continued Fraction Dimension

Mayordomo [19] extended the result by Lutz [14] to show that effective
dimension of a binary sequence $X\in\Sigma^{\infty}$ can be characterized in
terms of the Kolmogorov complexity of the finite prefixes of $X$.

######  Theorem 1 (Mayordomo [19] and Lutz [14]).

For every $X\in\Sigma^{\infty}$,

$\mathrm{cdim}(X)=\liminf\limits_{n\rightarrow\infty}\frac{K(X\upharpoonright
n)}{n}.$

We provide a similar characterization for effective continued fraction
dimension. To obtain the Kolmogorov complexity of a continued fraction string,
we use the Kolmogorov complexity of one of its binary encodings.

The idea of encoding a finite continued fraction using a 1-1 binary encoding
is present in Vishnoi [31]. The author presents an invariance theorem stating
that every computable binary 1-1 encoding of continued fractions defines the
same Kolmogorov complexity, up to an additive constant. Hence in this work, we
use a new binary encoding to define Kolmogorov complexity of continued
fractions, which helps us establish the characterization of effective
dimension of continued fractions in a fairly simple manner while having
intuitive geometric meaning.

######  Definition 8 (Many-one binary encoding).

For a continued fraction string $v\in\mathbb{N}^{*}$, let $b_{v}$ be the
leftmost maximal binary cylinder which is enclosed by $C_{v}$. We define
$E(v)=b_{v}$.

######  Lemma 7.

For any $b\in\Sigma^{*}$, there exists at most three $v\in\mathbb{N}^{*}$ such
that $E(v)=b$.

###### Proof.

For $b\in\\{0,1\\}^{*}$ assume there exists distinct
$v_{1},v_{2},v_{3},v_{4}\in\mathbb{N}^{*}$ such that
$E(v_{1})=E(v_{2})=E(v_{3})=E(v_{4})=b$. Since $b$ is enclosed by all of these
continued fraction cylinders, it follows that these continued fraction strings
are extensions of each other. Assume without loss of generality that
$v_{1}\sqsubset v_{2}\sqsubset v_{3}\sqsubset v_{4}$. We can also assume that
these cylinders are one length extensions of each other. From Lemma 11, using
the fact that $s_{n}>0$ and $i\geq 1$, it follows that for any
$v\in\mathbb{N}^{*}$ and $i\in\mathbb{N}$, $\frac{\mu[v,i]}{\mu[v]}\leq 1/2$ .
Therefore we have, $\mu(v_{4})\leq\frac{1}{8}\mu(v_{1})$. But from Lemma 2, we
get $\mu(b)\geq\frac{1}{4}\mu(v_{1})$. Combining these two, we get that
$\mu(b)\geq 2\mu(v_{4})$, which leads to a contradiction, since $b$ is
enclosed by $v_{4}$. ∎

Therefore for any $b\in\Sigma^{*}$, at most three continued fraction
cylinders, say $[v]$, $[v,i]$ and $[v,i,j]$ get mapped to $b$. Therefore we
pad two additional bits of information to $E(v)$, say $b_{1}(v).b_{2}(v)$ to
identify the continued fraction cylinder that $E(v)$ corresponds to.

######  Definition 9 (One-one binary encoding).

For $v\in\mathbb{N}^{*}$, let $\mathcal{E}(v)=E(v).b_{1}(v).b_{2}(v)$. This
forms a one to one binary encoding of $v$.

We define Kolmogorov complexity of continued fraction string
$v\in\mathbb{N}^{*}$ as the Kolmogorov complexity of $\mathcal{E}(v)$.

######  Definition 10 (Kolmogorov complexity of continued fraction strings).

For any $v\in\mathbb{N}^{*}$, define $K_{\mathcal{E}}(v)=K(\mathcal{E}(v))$.

Notation. By the invariance theorem of Vishnoi [31], for any $v\in\Sigma^{*}$,
$K_{\mathcal{E}}$ is at most an additive constant more than the complexity of
$v$ as defined in [31]. Hence, we drop the suffix and denote the above
complexity as $K(v)$.

In the proof of Theorem 1, Mayordomo [19] provides the construction of an
$s$-gale that succeeds on all $X$ for which
$s>s^{\prime}>\liminf_{n\rightarrow\infty}\frac{K(X\upharpoonright n)}{n}$. We
extend the construction to the setting of continued fractions.

Additionally, we take a convex combination of gales to remove the dependence
of the $s$-gale on the parameter $s^{\prime}$. Due to this, we obtain the
notion of an optimal lower semicomputable continued fraction $s$-gale. This
notion is crucial in the proofs we use in the upcoming sections.

######  Definition 11.

Given $0<s^{\prime}<s\leq 1$ let

$\displaystyle G_{s^{\prime}}=\\{w\in\mathbb{N}^{*}\mid
K(w)\leq-s^{\prime}\log(\mu(w))\\}.$

Consider the following function
$d_{s^{\prime}}:\mathbb{N}^{*}\rightarrow[0,\infty)$ defined by

$\displaystyle d_{s^{\prime}}(v)=\frac{1}{\gamma^{s}(v)}\left(\sum_{w\in
G_{s^{\prime}};v\sqsubseteq w}\gamma^{s^{\prime}}(w)+\sum_{w\in
G_{s^{\prime}};w\sqsubset
v}\gamma^{s^{\prime}}(w)\frac{\gamma(v)}{\gamma(w)}\right).$

Now for each $i\in\mathbb{N}$, let $s_{i}=s(1-2^{-i})$. Finally, define
$d^{*}:\mathbb{N}^{*}\to[0,\infty)$ by

$\displaystyle d^{*}(v)=\sum\limits_{i=1}^{\infty}2^{-i}d_{s_{i}}(v).$

We now go on to show that the function $d^{*}$ given in Definition 11 is a
lower semicomputable $s$-gale. Additionally, it succeeds on all continued
fraction sequences $Y$ for which the Kolmogorov complexity of its prefixes,
$K(Y\upharpoonright n)$ dips below $s\times-\log(\mu(Y\upharpoonleft n))$
infinitely often.

######  Lemma 8.

For any $0<s\leq 1$, there exists a lower semicomputable continued fraction
$s$-gale $d^{*}:\mathbb{N}^{*}\rightarrow[0,\infty)$ that succeeds on all
$Y\in\mathbb{N}^{\infty}$ such that
$\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}<s$.

###### Proof.

Consider any $s^{\prime}<s\leq 1$. Let
$G_{s^{\prime}}=\\{w\in\mathbb{N}^{*}\mid
K(w)\leq-s^{\prime}.\log(\mu(w))\\}$. Consider the following continued
fraction $s$-gale $d_{s^{\prime}}:\mathbb{N}^{*}\rightarrow[0,\infty)$

$\displaystyle d_{s^{\prime}}(v)=\frac{1}{\gamma^{s}(v)}\;\left(\sum_{w\in
G_{s^{\prime}};v\sqsubseteq w}\gamma^{s^{\prime}}(w)+\sum_{w\in
G_{s^{\prime}};w\sqsubset
v}\gamma^{s^{\prime}}(w)\frac{\gamma(v)}{\gamma(w)}\right).$

We can see that for any $s^{\prime}$, since $G_{s^{\prime}}$ is computably
enumerable, $d_{s^{\prime}}$ is lower semicomputable.

For each $w\in G$, let $\mathcal{E}(w)=b$. By definition $K(w)=K(b)$.
Therefore, $K(b)\leq-s^{\prime}\log(\mu(w))$. From the Definition of
$\mathcal{E}$ and Lemma 2, we see that $\mu(b)\geq\frac{1}{16}\mu(w)$. The
extra factor of $\frac{1}{4}$ comes from the two additional bits that are
padded in $b$. Therefore, we have that $K(b)\leq-s^{\prime}\log(16.\mu(b))\leq
s^{\prime}|b|-4s^{\prime}\leq s^{\prime}|b|$.

Define $B=\\{x\in\\{0,1\\}^{*}$ $~{}|~{}$ $K(x)\leq s^{\prime}|x|\\}$. Hence
if $w\in G$, then $\mathcal{E}(w)\in B$.

Now, $d_{s^{\prime}}(\lambda)=\sum_{w\in G}\gamma^{s^{\prime}}(w)$. Using
Lemma 1, we get that $d_{s^{\prime}}(\lambda)\leq c\sum_{w\in
G}\mu^{s^{\prime}}(w)$ where $c=(\ln 2)^{-s^{\prime}}$. Since $s^{\prime}<1$,
we have that $c<\ln 2$.

From Lemma 2, it follows that
$\mu^{s}(\mathcal{E}(w))\geq\frac{1}{16}.\mu^{s}(w)$. Using the fact that
$\mathcal{E}$ is a one to one encoding, we get that
$d_{s^{\prime}}(\lambda)\leq 16\ln 2\sum_{x\in B}2^{-s^{\prime}|x|}$.

In the proof of the Kolmogorov complexity characterization of constructive
dimension [19], Mayordomo shows that $\sum_{x\in B}2^{-s^{\prime}|x|}\leq
2^{c}$ for some constant $c$. The proof uses the fact that $|B^{=n}|\leq
2^{s^{\prime}n-K(n)+c}$ along with the Kraft inequality
$\sum_{n}2^{-K(n)+c}\leq 2^{c}$. Therefore $d_{s^{\prime}}(\lambda)$ is
finite.

Note that for each $w\in G_{s^{\prime}}$ we see that
$d_{s^{\prime}}(w)\geq(\frac{1}{\gamma(w)})^{s-s^{\prime}}$.

Now for each $i\in\mathbb{N}$, let $s_{i}=s(1-2^{-i})$. Finally, consider the
following continued fraction $s$-gale.

$d^{*}(v)=\sum\limits_{i=1}^{\infty}2^{-i}d_{s_{i}}(v).$

Consider any $Y\in\mathbb{N}^{\infty}$ such that
$\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}<s$. Let $i\in\mathbb{N}$ be the smallest
number such that $\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}<s_{i}$.

For each $w\in G_{s_{i}}$ we see that $d^{*}(w)\geq
2^{-i}(\frac{1}{\gamma(w)})^{s-s_{i}}$. We see that there are infinitely many
prefixes $w$ of $Y$ for which $w\in G_{s_{i}}$. Hence it follows that $d^{*}$
succeeds on Y. ∎

We refer to Downey and Hirschfeldt’s (Theorem 13.3.4 [5]) proof of the lower
bound on constructive dimension using Kolmogorov complexity. The proof
fundamentally uses properties of the universal lower semicomputable super-
martingale.

For any real having continued fraction dimension less than $s$, we obtain a
lower semicomputable binary $s$-gale that succeeds on it from Lemma 6. We use
the success of this binary $s$-gale along with the same properties of the
universal lower semicomputable super-martingale, to prove the following lemma.

######  Lemma 9.

For any $Y\in\mathbb{N}^{\infty}$ and any $s>\mathrm{cdim}_{CF}(Y)$, we have
$\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}\leq s.$

###### Proof.

Given any $s>dim_{CF}(Y)$, take an $s^{\prime}$ such that
$s>s^{\prime}>dim_{CF}(Y)$. By definition, there exists a continued fraction
$s^{\prime}$-gale, say $d:\mathbb{N}^{*}\to[0,\infty)$ that succeeds on $Y$.
For each prefix $v_{i}\sqsubseteq Y$, let $\mathcal{E}(v_{i})=b_{i}$. From the
definition of $\mathcal{E}$ and Lemma 2, we get that
$\mu(v)\geq\mu(b_{i})\geq\frac{1}{16}\mu(v_{i})$. The extra factor of
$\frac{1}{4}$ comes from the two additional bits that gets added in
$\mathcal{E}$.

Using Lemma 6, we get a binary $s$-gale $h:\Sigma^{*}\to[0,\infty)$ such that
forall $i$, $h(b_{i})\geq c_{s}d(v_{i})$ for some constant $c_{s}$. Therefore
$\limsup_{i\rightarrow\infty}h(b_{i})=\infty$.

Let $f$ be the universal lower semicomputable super-martingale [11]. As
$2^{(1-s)|b_{i}|}h(b_{i})$ is a martingale, it follows that $f(b_{i})\geq
c_{h}2^{(1-s)|b_{i}|}h(b_{i})$ for some constant $c_{h}$ that depends only on
$h$. Therefore, we have that
$\limsup_{i\rightarrow\infty}\frac{f(b_{i})}{2^{(1-s)|b_{i}|}}=\infty$.

Let $|b_{i}|=n$. As noted in the proof of Theorem 13.3.4 in [5],
$f(b_{i})=2^{n-KM(b_{i})\pm O(1)}$ where $K(b_{i})\leq KM(b_{i})+O(\log n)$.
Hence it follows that $\limsup_{i\rightarrow\infty}2^{sn-K(b_{i})+O(\log
n)}=\infty$. Therefore for infinitely many $i\in\mathbb{N}$, we have
$K(b_{i})<sn+O(\log n)$.

By definition $K(v_{i})=K(b_{i})$. Also, we have that
$|b_{i}|=-\log(\mu(b_{i}))\leq-\log(\mu(v_{i}))+4$. Therefore for infinitely
many $i\in\mathbb{N}$, we have
$K(v_{i})<-s\log(\mu(v_{i}))+4s+O(\log(-\log(\mu(v_{i}))))$. From this, it
follows that
$\liminf\limits_{i\rightarrow\infty}\frac{K(v_{i})}{-\log(\mu(v_{i}))}\leq s$.
∎

Therefore, we have the following Kolmogorov complexity based characterization
of effective continued fraction dimension.

######  Theorem 2.

For any $Y\in\mathbb{N}^{\infty}$,

$dim_{CF}(Y)=\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}.$

###### Proof.

For any $Y\in\mathbb{N}^{\infty}$, let
$s^{*}=\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}$.

For any $s>s^{*}$, from Lemma 8, it follows that there exists a lower
semicomputable $s$-gale ${\mathcal{D}}$ that succeeds on $Y$. Hence
${\mathrm{dim}}_{CF}(Y)\leq s^{*}$.

For any $s>{\mathrm{dim}}_{CF}(Y)$, from Lemma 9, we have that $s^{*}\leq s$.
Therefore, we have $s^{*}\leq{\mathrm{dim}}_{CF}(Y)$. ∎

###  4.1 Optimal gales and effective continued fraction dimension of a set

Lutz [16] utilizes the notion of the optimal constructive subprobability
supermeasure $\mathbf{M}$ on the Cantor space [32] to provide a notion of an
optimal constructive supergale.

We note that using Theorem 2, the gale that we obtain from Lemma 8 leads to an
analogous notion in the continued fraction setting. We call the continued
fraction $s$-gale $d^{*}$ thus obtained as the _optimal lower semicomputable
continued fraction $s$-gale_.

######  Lemma 10.

For any $s>0$, there exists a lower semicomputable continued fraction $s$-gale
$d^{*}:\mathbb{N}^{*}\rightarrow[0,\infty)$ such that for all
$Y\in\mathbb{N}^{\infty}$ with $\mathrm{cdim}_{CF}(Y)<s$, $d^{*}$ succeeds on
$Y$.

###### Proof.

For all $Y\in\mathbb{N}^{*}$ such that $\mathrm{cdim}_{CF}(Y)<s$, from Theorem
2, it follows that $\liminf\limits_{n\rightarrow\infty}\frac{K(Y\upharpoonleft
n)}{-\log(\mu(Y\upharpoonleft n))}<s$. Now applying Lemma 8, we see that the
given lemma holds. ∎

Lutz (Theorem 4.1 in [16]) shows that the effective dimension of a set is
precisely the supremum of effective dimensions of individual elements in the
set, that is for all $X\subseteq[0,1]$, $\mathrm{cdim}(X)=\sup_{S\in
X}\mathrm{cdim}(S)$. Using the notion of the optimal lower semicomputable
continued fraction $s$-gale from Lemma 10, we extend this result to continued
fraction dimension.

######  Theorem 3.

For all $\mathcal{F}\subseteq[0,1]$,
$\mathrm{cdim}_{CF}(\mathcal{F})=\sup_{Y\in\mathcal{F}}\mathrm{cdim}_{CF}(Y)$.

###### Proof.

For any $s>\mathrm{cdim}_{CF}(\mathcal{F})$, for all $Y\in\mathcal{F}$ there
exists a lower semicomputable continued fraction $s$-gale that succeeds on
$Y$. Thus we have $\sup_{Y\in\mathcal{F}}\mathrm{cdim}_{CF}(Y)\leq s$.

Take any any $s>\sup_{Y\in\mathcal{F}}\mathrm{cdim}_{CF}(Y)$. It follows that
for all $Y\in\mathcal{F}$, $\mathrm{cdim}_{CF}(Y)<s$. Therefore from Lemma 10,
we have that there exists a lower semicomputable continued fraction $s$-gale
$d^{*}:\mathbb{N}^{*}\rightarrow[0,\infty)$ that succeeds on all
$Y\in\mathcal{F}$. Therefore, $\mathrm{cdim}_{CF}(\mathcal{F})\leq s$. ∎

##  5 Reals with unequal Effective Dimension and Effective Continued Fraction
Dimension

In this section, we show that for any set of reals
$\mathcal{F}\subseteq[0,1]$, the effective Hausdorff effective dimension of
$\mathcal{F}$ cannot exceed its effective continued fraction dimension. We
show that this cannot be improved to an equality. Hence, this inequality is
strict in general. We show this by proving the existence of a real such that
its effective continued fraction dimension is strictly greater its effective
dimension.

###  5.1 Effective Hausdorff dimension is at most the effective continued
fraction dimension

######  Theorem 4.

For any $\mathcal{F}\subseteq[0,1]$,
$\mathrm{cdim}(\mathcal{F})\leq\mathrm{cdim}_{CF}(\mathcal{F})$.

###### Proof.

Let $s>s^{\prime}>\mathrm{cdim}_{CF}(\mathcal{F})$. By definition, there
exists a lower semicomputable continued fraction $s^{\prime}$-gale
$d:\mathbb{N}^{*}\to[0,\infty)$ such that $\mathcal{F}\subseteq
S^{\infty}[d]$.

Take any $Y\in S^{\infty}[d]$. Let $X\in\Sigma^{\infty}$ be the corresponding
binary representation of $Y$. By definition, for any $m\in\mathbb{N}$, there
exists an $n\in\mathbb{N}$ such that $d(Y\upharpoonright n)>m$. Let
$v=Y\upharpoonright n$.

Using Lemma 3, we get two binary cylinders $w_{1}$ and $w_{2}$ such that
$C_{v}\subseteq C_{w_{1}}\cup C_{w_{2}}$ such that $\mu(w_{1})=\mu(w_{2})\leq
2\mu(v)$. We have that since $v\sqsubseteq Y$, $w1\sqsubseteq X$ or
$w2\sqsubseteq X$. Without loss of generality assume that $w_{1}\sqsubseteq
X$.

From Lemma 6, we obtain a lower semicomputable $s$-gale $h$ such that
$h(w_{1})\geq c_{s}.d(v)\geq c_{s}.m$ for some positive constant $c_{s}$.

Since $m$ is arbitrary, we see that $h$ succeeds on $X$. ∎

###  5.2 Reals with unequal effective Hausdorff and effective continued
fraction dimensions

We now provide the main construction of the paper, utilizing the results we
show in previous sections.

We first require some technical lemmas about the estimation of Lebesgue
measure of a continued fraction cylinder in terms of digits of the continued
fraction. Some of the bounds derived in this section may be of independent
interest.

In combinatorial arguments, the Gauss measure is often difficult to deal with
directly, and it is convenient to use the Lebesgue measure, and derive
inequalities.

The following equation, Proposition 1.2.7 in Kraaikamp and Iosifescu [9], is
extremely useful in deriving an estimate for the Lebesgue measure of continued
fraction cylinders. We derive consequences of this Lemma below, and these are
crucial in estimating the dimension of the continued fraction we construct in
Section 5. Note that the bounds for Gauss measure are not simple to derive
directly.

######  Lemma 11 (Kraaikamp, Iosifescu [9]).

For any $v=[a_{1},\dots a_{n}]$ and $i\in\mathbb{N}$,

$\frac{\mu([v,i])}{\mu([v])}=\frac{s_{n}+1}{(s_{n}+i)(s_{n}+i+1)}$

where $s_{n}=[a_{n},\dots a_{1}]$ is the rational corresponding to the reverse
of string $v$.

The lemma given above gives the following bounds on the Lebesgue measure of a
continued fraction cylinder in terms of the digits of the continued fraction.

######  Lemma 12.

For any $v=[a_{1},\dots a_{k}]\in\mathbb{N}^{k}$ we have

$\prod\limits_{i=1}^{k}\frac{1}{(a_{i}+1)(a_{i}+2)}\ \leq\ \mu(v)\ \leq\
\prod\limits_{i=1}^{k}\frac{2}{a_{i}\;(a_{i}+1)}$

###### Proof.

If $k=1$, then $\mu(v)=\frac{1}{a_{1}(a_{1}+1)}$, therefore the lemma holds.
For $k>1$, let $v=[a_{1},\dots a_{k-1}]$ and consider $[v,a_{k}]$. From Lemma
11, it follows that

$\mu([v,a_{k}])=\frac{s_{k-1}+1}{(s_{k-1}+a_{k})(s_{k-1}+a_{k}+1)}\;\;\mu(v),$

where $s_{k-1}=[a_{k-1},\dots a_{1}]$. Since $s_{k-1}\in[0,1]$, it follows
that

$\frac{1}{(a_{k}+1)(a_{k}+2)}\;\mu(v)\leq\mu([v,a_{k}])\leq\frac{2}{(a_{k})(a_{k}+1)}\;\mu(v)$

Therefore, by induction on $k$, the lemma holds. ∎

######  Lemma 13.

Let $v=[a_{1}\dots a_{k}]\in\mathbb{N}^{*}$. Then for any $a,b\in\mathbb{N}$
such that $b>a$,

$\displaystyle\mu\left(\;\bigcup\limits_{i=a}^{b}\;[v,i]\;\right)\leq\frac{2}{a}\;\prod\limits_{i=1}^{k}\frac{2}{a_{i}\;(a_{i}+1)}$

###### Proof.

From Lemma 11, it follows that

$\frac{\mu([v,i])}{\mu(v)}=\frac{s_{k}+1}{(s_{k}+i)(s_{k}+i+1)}$

where $s_{k}\in[0,1]$. Therefore

$\mu\Big{(}\;\bigcup\limits_{i=a}^{b}\;[v,i]\;\Big{)}\leq\sum\limits_{i=a}^{b}\frac{2}{i(i+1)}\mu(v)\leq\frac{2}{a}\;\mu(v).$

From Lemma 12, $\mu(v)\leq\prod\limits_{i=1}^{k}\frac{2}{a_{i}\;(a_{i}+1)}$.
Therefore this lemma holds. ∎

The following lemma is a direct constructive extension of the proof by Lutz
[15]. Using this technique, we convert a set of computably enumerable prefix
free binary covers into a lower semicomputable binary $s$-gale.

######  Lemma 14 (Lutz [15]).

For all $n\in\mathbb{N}$, and $\mathcal{F}\subseteq[0,1]$, if there is a
computably enumerable prefix free binary cover $\\{B^{n}_{i}\\}$ of
$\mathcal{F}$, such that $\sum_{i}|B_{i}^{n}|^{s}<2^{-n}$, then there exists a
lower semicomputable binary $s$-gale that succeeds on $\mathcal{F}$.

###### Proof.

For an $n\in N$, define an $s$-gale $d_{n}:\\{0,1\\}^{*}\rightarrow[0,\infty)$
as follows:

If $\exists\;v\sqsubseteq w$ such that $v\in\\{B^{i}_{n}\\}$, then

$d_{n}(w)=\frac{\mu^{s}(v)}{\mu^{s}(w)}\frac{\mu(w)}{\mu(v)}$

Otherwise,

$d_{n}(w)=\frac{1}{\mu^{s}(w)}{\sum_{v\in A_{r}\;;\;w\sqsubset v}\mu^{s}(v)}$

Finally define

$d(w)=\sum_{n=0}^{\infty}2^{n}d_{2n}(w).$

It is straightforward to verify that $d_{n}$ is an $s$-gale. It follows that
$d_{n}(\lambda)\leq 2^{-n}$, hence $d(\lambda)\leq 1$. Since $\\{B^{i}_{n}\\}$
is computably enumerable, $d$ is lower semicomputable. Now, for all $X\in F$
and $n\in\mathbb{N}$, there exists a prefix $w\sqsubseteq X$ such that
$w\in\\{B^{i}_{n}\\}$. From the definition of $d$, we can see that $\forall
w\in\\{B^{i}_{n}\\}$, $d_{n}(w)=1$. Therefore, $d(w)\geq
2^{n}d_{2n}(w)=2^{n}.$ Since $n$ is arbitrary, the $s$-gale d succeeds on $F$.
∎

We now proceed to show the construction of the set $\mathcal{F}$. The
definition uses a parameter $\mathbf{s}$. We later go on to show that for all
such $\mathcal{F}$, there exists an element $Y\in\mathcal{F}$ such that the
effective continued fraction dimension of $Y$ is greater than $0.5$. We also
go on to show that $cdim(F)\leq\mathbf{s}$.

We first provide the stage-wise construction of a set
$\mathcal{F}_{k}\subseteq[0,1]$, such that for each $k\in\mathbb{N}$
$\mathcal{F}_{k+1}\subseteq\mathcal{F}_{k}$. We then define the set
$\mathcal{F}$ using an infinite intersection of the sets $\mathcal{F}_{k}$.

######  Definition 12.

Let $0<\mathbf{s}<0.5$. Define $a_{1}=1$. For any $k\in\mathbb{N}$, such that
$k>1$, define $a_{k}$ inductively as:

$a_{k}=2\bigg{(}k\prod\limits_{i=1}^{k-1}100a_{i}\bigg{)}^{1/\mathbf{s}}.$

For any $k\in\mathbb{N}$, define $b_{k}=50.a_{k}$. Take
$\mathcal{F}_{0}=\lambda$.

Let $\mathcal{F}_{k}=\\{[v_{1}\dots v_{k}]\in\mathbb{N}^{k}\text{ such that
}v_{i}\in[a_{i},b_{i}]\text{ for }i\in 1\text{ to }k\\}$. Finally define

$\mathcal{F}=\bigcap\limits_{k=1}^{\infty}\mathcal{F}_{k}.$

We use the bounds obtained from Lemma 11, along with basic properties of
harmonic numbers to prove the following property of measures of continued
fraction sub cylinders.

######  Lemma 15.

For any $x\in\mathbb{N}^{*}$ , $s\leq 0.5$ and $a_{k},b_{k}\in N$ such that
$b_{k}=50.a_{k}$,
$\sum\limits_{i=a_{k}}^{b_{k}}\gamma^{s}([x,i])>c\gamma^{s}([x])$ for some
$c>1$.

###### Proof.

From Lemma 11, it follows that

$\displaystyle\sum\limits_{a_{n}}^{b_{k}}\frac{\mu^{s}([x,i])}{\mu^{s}([x])}$
$\displaystyle=\sum\limits_{a_{n}}^{b_{k}}\bigg{(}\frac{s_{k}+1}{(s_{k}+i)(s_{k}+i+1)}\bigg{)}^{s}$
$\displaystyle\geq\sum\limits_{a_{k}}^{b_{k}}\bigg{(}\frac{1}{(i+1)(i+2)}\bigg{)}^{s}$

The second inequality follows from the fact that $s_{k}\in[0,1]$.

Using Lemma 1, we get that

$\displaystyle\sum\limits_{a_{n}}^{b_{k}}\frac{\gamma^{s}([x,i])}{\gamma^{s}([x])}$
$\displaystyle\geq\sum\limits_{a_{k}}^{b_{k}}\bigg{(}\frac{1}{2(i+1)(i+2)}\bigg{)}^{s}$

Putting $b_{k}=50a_{k}$ and $s\leq 0.5$, we get

$\displaystyle\sum\limits_{a_{n}}^{b_{k}}\frac{\gamma^{s}([x,i])}{\gamma^{s}([x])}$
$\displaystyle\geq\frac{1}{2}\sum_{a_{k}}^{50a_{k}}\frac{1}{i+2}$
$\displaystyle=0.5(H(50a_{k}+2)-H(a_{k}+1)).$

where $H_{n}$ is the $n^{th}$ Harmonic number. From the fact that $\ln n\leq
H_{n}\leq\ln n+1$, we have

$\displaystyle H(50a_{k}+2)-H(a_{k}+1)$
$\displaystyle\geq\ln(50.a_{k})-\ln(2.a_{k})-1$ $\displaystyle=\ln(25)-1.$

The lemma holds as $0.5(\ln 25-1)$ is greater than $1$. ∎

Using the bound derived above, we show that for $s=0.5$, the optimal $s$-gale
$d^{*}$ formulated in Section 4.1 does not succeed on some sequence in
$Y\in\mathcal{F}$. Using this we establish that $\mathrm{cdim}_{CF}(Y)\geq
0.5$.

######  Lemma 16.

There exists a $Y\in\mathcal{F}$ such that $\mathrm{cdim}_{CF}(Y)\geq 0.5$.

###### Proof.

Let $s=0.5$. Consider the continued fraction $s$-gale $d^{*}$ from Lemma 10.
It follows that for all $Y\in\mathbb{N}^{*}$, if $d^{*}$ does not succeed on
any $Y\in\mathbb{N}^{*}$, then $\mathrm{cdim}_{CF}(Y)\geq s$.

Consider any $v\in\mathbb{N}^{*}$, let $rank(v)=k$. From lemma 15, we have
that for some $c>1$,
$\sum\limits_{i=a_{k}}^{b_{k}}\gamma^{s}([v,i])>c.\gamma^{s}([v]).$

Now if $\forall i\in[a_{k},b_{k}]$, $d^{*}([v,i])\geq\frac{1}{c}.d^{*}(v)$,
from the $s$-gale condition it follows that
$d^{*}(v)\gamma^{s}(v)\geq\frac{d^{*}(v)}{c}\sum\limits_{i=a_{k}}^{b_{k}}\gamma^{s}([v,i])>d^{*}(v)\gamma^{s}(v)$,
which is a contradiction.

Therefore, it follows that for all $v\in\mathbb{N}^{*}$, there exists some
$n_{v}\in[a_{k},b_{k}]$ such that $d^{*}([v,i])<\frac{1}{c}.d^{*}([v])$.

Let $v_{0}=\lambda$, for each $i\in\mathbb{N}$, we define
$v_{i}=[v_{i-1},n_{v_{i-1}}]$. Take $Y=\cap_{i=1}^{\infty}C_{v_{i}}$, it
follows that $Y\in F$. Taking $d^{*}(\lambda)=k$ we get
$d^{*}(Y\upharpoonright n)<\frac{k}{c^{n}}$. Therefore the continued fraction
$s$-gale $d^{*}$ does not succeed on $Y$. Hence $\mathrm{cdim}_{CF}(Y)\geq
0.5$. ∎

From this, it follows that the constructive dimension of the entire set
$\mathcal{F}$ is also greater than or equal to 0.5.

######  Lemma 17.

$\mathrm{cdim}_{CF}(\mathcal{F})\geq 0.5$.

###### Proof.

From Theorem 3, we get that
$\mathrm{cdim}_{CF}(\mathcal{F})=\sup_{Y\in\mathcal{F}}\mathrm{cdim}_{CF}(Y)$.
From Lemma 16, it follows that there exists a $Y\in F$ such that
$\mathrm{cdim}_{CF}(Y)\geq 0.5$. Combining these two, we get that
$\mathrm{cdim}_{CF}(\mathcal{F})\geq 0.5$. ∎

Now we show that the effective Hausdorff dimension of all points in the set
$\mathcal{F}$ is less than $\mathbf{s}$. Using ideas from [2], we devise a set
of covers $S_{k}$ for $\mathcal{F}$, by combining adjacent continued fraction
cylinders into a single cover.

Using the bounds derived on Lebesgue measure of continued fraction cylinders,
we show that for the set of covers $S_{k}$ for $\mathcal{F}$, the
$\mathbf{s}$-dimensional Hausdorff measure shrinks arbitrarily small.

######  Lemma 18.

For $k\in\mathbb{N}$, let $S_{k}=\\{\
\bigcup\limits_{i=a_{k}}^{b_{k}}\;[v,i]\text{ for }v\in\mathcal{F}_{k-1}\\}$.
Then, $\sum\limits_{S\in S_{k}}\mu^{\mathbf{s}}(S)\leq 1/k$.

###### Proof.

The largest element in $S_{k}$ is $I=[(a_{1}\dots a_{k-1},a_{k}),[(a_{1}\dots
a_{k-1},b_{k})]$. The number of elements in $S_{k}$ equals
$\prod_{i=1}^{k-1}(b_{i}-a_{i})$. Additionally, we have $b_{i}=50a_{i}$ for
all $i\in\mathbb{N}$. Therefore,

$\sum\limits_{S\in
S_{k}}\mu^{\mathbf{s}}(S)\leq\mu^{\mathbf{s}}(I)\prod\limits_{i=1}^{k-1}50a_{i}.$

From Lemma 13, it follows that
$\mu(I)\leq\frac{2}{a_{k}}\;\prod\limits_{i=1}^{k-1}\frac{2}{a_{i}\;(a_{i}+1)}$.
Therefore,

$\displaystyle\sum\limits_{S\in S_{k}}\mu^{\mathbf{s}}(S)$
$\displaystyle\leq\Big{(}\frac{2}{a_{k}}\;\prod\limits_{i=1}^{k-1}\frac{2}{a_{i}^{2}\;}\Big{)}^{\mathbf{s}}\;\;\prod\limits_{i=1}^{k-1}(50a_{i})$
$\displaystyle\leq\frac{2^{\mathbf{s}}}{a_{k}^{\mathbf{s}}}\;\;\prod\limits_{i=1}^{k-1}100a_{i}$

Since $a_{k}=2(k\prod\limits_{i=1}^{k-1}100a_{i})^{1/{\mathbf{s}}}$, this
value is less than $1/k$. ∎

To show that the constructive dimension of $\mathcal{F}$ is less than
$\mathbf{s}$, we construct a lower semicomputable binary $\mathbf{s}$-gale
that succeeds on $\mathcal{F}$. Using standard techniques, we first convert
the covers obtained in Lemma 18 to a set of binary covers of $\mathcal{F}$.
Finally applying Lemma 14, we convert the binary covers into a semicomputable
$\mathbf{s}$-gale that succeeds on $\mathcal{F}$.

######  Lemma 19.

$\mathrm{cdim}(\mathcal{F})\leq\mathbf{s}.$

###### Proof.

Given $k\in\mathbb{N}$, from Lemma 18, we have that for $S_{k}=\\{\
\bigcup_{i=a_{k}}^{b_{k}}\;[v,i]\text{ for }v\in\mathcal{F}_{k-1}\\}$,
$\sum_{S\in S_{k}}\mu^{\mathbf{s}}(S)\leq 1/k$. For each $S\in S_{k}$, using
Lemma 3, we get that for the two smallest consecutive binary cylinders say
$b_{1}(S)$ and $b_{2}(S)$ that cover $S$, we have that
$\mu(b_{1})=\mu(b_{2})\leq 2\mu(C)$.

Hence the set $B_{k}=\\{\\{b_{1}(S)\\}\cup\\{b_{2}(S)\\}\text{ such that }S\in
S_{k}\\}$ forms a binary cover of $S_{k}$. Also from Lemma 3, we have that
$\sum_{b\in B_{k}}\mu^{\mathbf{s}}(b)\leq 2^{1+{\mathbf{s}}}\sum_{S\in
S_{k}}\mu^{\mathbf{s}}(S)\leq 2^{1+{\mathbf{s}}}/k$.

Note that the set $S_{k}$ is computable as $a_{k}$ and $b_{k}$ are computable
for all $k$. Given any interval $S$, $b_{1}(S)$ and $b_{2}(S)$ are also
computable. Hence the set $B_{k}$ is computable.

Since $B_{k}$ is a finite set, we can remove all $v\in B_{k}$ such that
$u\sqsubset v$ for some $u\in B_{k}$, to make $B_{k}$ prefix free.

For an $n\in\mathbb{N}$, taking $k=\lceil 2^{1+\mathbf{s}}.2^{n}\rceil$, the
set $B_{k}$ forms a computably enumerable prefix free binary cover of
$\mathcal{F}$ such that $\sum_{b\in B_{k}}\mu^{\mathbf{s}}(b)\leq 2^{-n}$.

Applying Lemma 14, we get that there exists a lower semicomputable
$\mathbf{s}$-gale that succeeds on $\mathcal{F}$. Hence the lemma holds. ∎

We sum up the results from Lemma 16 and Lemma 19 into the following theorem.

######  Theorem 5.

Given any $0<\varepsilon<0.5$, there exists a $Y\in\mathbb{N}^{\infty}$ such
that $\mathrm{cdim}_{CF}(Y)\geq 0.5$ and $\mathrm{cdim}(Y)\leq\varepsilon$.

###### Proof.

Given $0<\varepsilon<0.5$, taking $\mathbf{s}=\varepsilon$, construct the set
$\mathcal{F}$ given in Definition 12.

From Lemma 16, it follows that there exists a $Y\in\mathcal{F}$ such that
$\mathrm{cdim}_{CF}(Y)\geq 0.5$.

From Lemma 19, it follows that for all $X\in\mathcal{F}$,
$cdim(X)\leq\varepsilon$. Hence $cdim(Y)\leq\varepsilon$.

∎

## References

  * [1] S. Albeverio, Ganna Ivanenko, Mykola Lebid, and Grygoriy Torbin.  On the Hausdorff dimension faithfulness and the Cantor series expansion.  Methods of Functional Analysis and Topology, 26(4):298–310, 2020\.
  * [2] Sergio Albeverio, Yuri Kondratiev, Roman Nikiforov, and Grygoriy Torbin.  On new fractal phenomena connected with infinite linear IFS.  Math. Nachr., 290(8-9):1163–1176, 2017.
  * [3] G. J. Chaitin.  A theory of program size formally identical to information theory.  Journal of the Association for Computing Machinery, 22:329–340, 1975.
  * [4] Karma Dajani and Cor Kraaikamp.  Ergodic Theory of Numbers.  The Mathematical Association of America, 2002.
  * [5] Rodney G. Downey and Denis R. Hirschfeldt.  Algorithmic randomness and complexity.  Theory and Applications of Computability. Springer, New York, 2010.
  * [6] M. Einsiedler and T. Ward.  Ergodic Theory: with a view towards Number Theory.  Graduate Texts in Mathematics. Springer London, 2010.
  * [7] Kenneth Falconer.  Fractal geometry.  John Wiley & Sons, Inc., Hoboken, NJ, second edition, 2003.  Mathematical foundations and applications.
  * [8] John M. Hitchcock and Elvira Mayordomo.  Base invariance of feasible dimension.  Inform. Process. Lett., 113(14-16):546–551, 2013.
  * [9] Marius Iosifescu and Cor Kraaikamp.  Metrical theory of continued fractions, volume 547 of Mathematics and its Applications.  Kluwer Academic Publishers, Dordrecht, 2002.
  * [10] L. A. Levin.  On the notion of a random sequence.  Soviet Mathematics Doklady, 14:1413–1416, 1973.
  * [11] Ming Li and Paul Vitányi.  An introduction to Kolmogorov complexity and its applications.  Texts in Computer Science. Springer, New York, third edition, 2008.
  * [12] J. H. Lutz.  Dimension in complexity classes.  In Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity, pages 158–169, 2000.
  * [13] J. H. Lutz.  The dimensions of individual strings and sequences.  Information and Computation, 2003.
  * [14] Jack H. Lutz.  Gales and the constructive dimension of individual sequences.  In Automata, languages and programming (Geneva, 2000), volume 1853 of Lecture Notes in Comput. Sci., pages 902–913. Springer, Berlin, 2000.
  * [15] Jack H. Lutz.  Dimension in complexity classes.  SIAM J. Comput., 32(5):1236–1259, 2003.
  * [16] Jack H. Lutz.  The dimensions of individual strings and sequences.  Inform. and Comput., 187(1):49–79, 2003.
  * [17] Jack H. Lutz and Elvira Mayordomo.  Dimensions of points in self-similar fractals.  SIAM Journal on Computing, 38:1080–1112, 2008.
  * [18] P. Martin-Löf.  The definition of random sequences.  Information and Control, 9(6):602–619, 1966.
  * [19] Elvira Mayordomo.  A Kolmogorov complexity characterization of constructive Hausdorff dimension.  Inform. Process. Lett., 84(1):1–3, 2002.
  * [20] Elvira Mayordomo.  Effective dimension in some general metric spaces.  In Benedikt Löwe and Glynn Winskel, editors, Proceedings 8th International Workshop on Developments in Computational Models, DCM 2012, Cambridge, United Kingdom, 17 June 2012, volume 143 of EPTCS, pages 67–75, 2012.
  * [21] Elvira Mayordomo.  Effective Hausdorff dimension in general metric spaces.  Theory Comput. Syst., 62(7):1620–1636, 2018.
  * [22] S. Nandakumar.  An effective ergodic theorem and some applications.  In Proceedings of the 40th Annual Symposium on the Theory of Computing, pages 39–44, 2008.
  * [23] Satyadev Nandakumar and Prateek Vishnoi.  On continued fraction randomness and normality.  Inform. and Comput., 285(part B):Paper No. 104876, 17, 2022.
  * [24] André Nies.  Computability and randomness, volume 51.  OUP Oxford, 2009.
  * [25] Yuval Peres and Gyorgiy Torbin.  Continued fractions and dimensional gaps.  In preparation.
  * [26] Adrian-Maria Scheerer.  On the continued fraction expansion of absolutely normal numbers, 2017\.
  * [27] C. P. Schnorr.  Zufälligkeit und Wahrscheinlichkeit.  Springer-Verlag, Berlin, 1971.
  * [28] Ludwig Staiger.  The Kolmogorov complexity of real numbers.  Theor. Comput. Sci., 284(2):455–466, 2002.
  * [29] Joseph Vandehey.  Absolutely abnormal and continued fraction normal numbers.  Bulletin of the Australian Mathematical Society, 94(2):217–223, 2016.
  * [30] Prateek Vishnoi.  Algorithmic Information Theory & Continued Fractions.  PhD thesis, Indian Institute of Technology Kanpur, 2023.
  * [31] Prateek Vishnoi.  Normality, randomness and Kolmogorov complexity of continued fractions.  In Theory and Applications of Models of Computation: 17th Annual Conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, pages 382–392. Springer, 2023.
  * [32] A. K. Zvonkin and L. A. Levin.  The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms.  Russ. Math. Surv., 25(6):83–124, 1970.