Exact Constructive and Computable Dimensions

Abstract

In this paper we derive several results which generalise the constructive dimension of (sets of) infinite strings to the case of exact dimension. We start with proving a martingale characterisation of exact Hausdorff dimension. Then using semi-computable super-martingales we introduce the notion of exact constructive dimension of (sets of) infinite strings. This allows us to derive several bounds on the complexity functions of infinite strings, that is, functions assigning to every finite prefix its Kolmogorov complexity. In particular, it is shown that the exact Hausdorff dimension of a set of infinite strings lower bounds the maximum complexity function of strings in this set. Furthermore, we show a result bounding the exact Hausdorff dimension of a set of strings having a certain computable complexity function as upper bound. Obviously, the Hausdorff dimension of a set of strings alone without any computability constraints cannot yield upper bounds on the complexity of strings in the set. If we require, however, the set of strings to be Σ₂-definable several results upper bounding the complexity by the exact Hausdorff dimension hold true. First we prove that for a Σ₂-definable set with computable dimension function one can construct a computable – not only semi-computable – martingale succeeding on this set. Then, using this result, a tight upper bound on the prefix complexity function for all strings in the set is obtained.

The paper addresses a problem from Algorithmic Information Theory. In his papers [17, 19] Lutz came up with an effectivisation of Hausdorff dimension, called constructive dimension. Constructive dimension characterises the algorithmic complexity of (sets of) infinite strings as real numbers. It turned out to be equivalent to asymptotic Kolmogorov complexity [44, Theorem 3.4] (see also [19, 22, 33]) and is related to the concept of partial randomness of infinite strings [4, 39]. However, the results of Reimann and Stephan [26] show, unlike the case of random infinite strings, different notions of Kolmogorov complexity (cf. [6, 42, 43]) yield different notions of partial randomness.

To distinguish these types of partial randomness requires a refinement of the complexity scale of (sets of) infinite strings. The present paper shows that an effectivisation of Hausdorff’s original concept of dimension [12], referred to as exact Hausdorff dimension in [11, 20, 21], is possible and leads, similarly to the case of “usual” dimensions (cf. [17, 19, 28, 29, 31, 32]), to close connections between exact Hausdorff dimension and exact constructive dimension. In contrast to the “usual” constructive or Hausdorff dimension an exact dimension of a string or a set of strings is a real function, referred to as dimension function [10, Section 2.5] or gauge function [11]. This makes it more difficult to specify uniquely ‘the’ exact Hausdorff dimension of set of strings.

After introducing some notation and some necessary concepts related to Kolmogorov complexity we proceed in Section 1.3 with Hausdorff’s original approach [12] (see also [27]) and give a definition of what is an exact Hausdorff dimension of a set of infinite words. Then Section 1.4 presents a brief account on some known results relating “classical” Hausdorff dimension and (asymptotic) Kolmogorov complexity.

The subsequent part consisting of four sections generalises the “classical” results mentioned in Section 1.4 to the case of exact Hausdorff dimension and Kolmogorov complexity functions. First, in Section 2 we deal with the martingale characterisation of exact Hausdorff dimension. The following section defines the exact constructive dimension and derives a lower complexity bound by the principle “large sets contain complex elements”, and in Section 4 we use a dilution principle to construct sets of infinite strings having a prescribed computable dimension function.

Upper complexity bounds for Σ₂-definable sets of infinite strings are the subject of Section 5. It should be mentioned here that, as already proved in [32] these bounds cannot be extended to the class of π₂-definable sets.

Finally, in Section 6, we apply our results to the family of functions of the logarithmic scale, which was also considered by Hausdorff [12]. This family on the one hand refines the “usual” scale of asymptotic dimension and is, on the other hand, – in contrast to the general case – linearly ordered. Another refinement of the usual constructive dimension called scaled dimension which uses gauge functions derived from a particular scale has been proved to be useful in the theory of complexity classes [14, 15].

Some of the results of the Sections 2, 3 and 5 are contained in the conference papers [36] and [37].

1 Notation and Preliminaries

1.1 Notation

In this section we introduce the notation used throughout the paper. By $\mathbb {N} = \{ 0,1,2,\ldots \}$ we denote the set of natural numbers and by $\mathbb {Q}$ the set of rational numbers, $\mathbb {R}$ are the real numbers and $\mathbb {R}_{+}$ the non-negative real numbers.

Let X be an alphabet of cardinality |X| = r ≥ 2. By X ^∗ we denote the set of finite words on X, including the empty word e, and X ^ω is the set of infinite strings (ω-words) over X. Subsets of X ^∗ will be referred to as languages and subsets of X ^ω as ω-languages.¹

For w ∈ X ^∗ and η ∈ X ^∗∪ X ^ω let w ⋅ η be their concatenation. This concatenation product extends in an obvious way to subsets W ⊆ X ^∗ and B ⊆ X ^∗∪ X ^ω.

We denote by |w| the length of the word w ∈ X ^∗ and p r e f(B) is the set of all finite prefixes of strings in B ⊆ X ^∗∪ X ^ω. We shall abbreviate w ∈p r e f(η) (η ∈ X ^∗∪ X ^ω) by $w\sqsubseteq \eta$, and $\eta \upharpoonright n$ is the n-length prefix of η provided |η|≥ n. A language W ⊆ X ^∗ is referred to as prefix-free if w,v ∈ W and $w\sqsubseteq v$ imply w = v. If W ⊆ X ^∗ then $\text {Min}_{\sqsubseteq }W:=\{w:w\in W\wedge \forall v(v\in W \to v\not \sqsubset w)\}$ is the (prefix-free) set of minimal w.r.t. $\sqsubseteq$ elements of W.

It is sometimes convenient to regard X ^ω as a topological space (Cantor space). Here open sets in X ^ω are those of the form W ⋅ X ^ω with W ⊆ X ^∗. Closed are sets F ⊆ X ^ω which satisfy the condition F = {ξ : p r e f(ξ) ⊆p r e f(F)}. In this space the following compactness theorem (or König’s lemma) holds.

Compactness Theorem

If F ⊆ X ^ω is closed and F ⊆ W ⋅ X ^ω for some W ⊆ X ^∗ then there is a finite subset W ^′⊆ W such that F ⊆ W ^′⋅ X ^ω.

For a computable domain $\mathcal {D}$, such as $\mathbb {N}$, $\mathbb {Q}$ or X ^∗, we refer to a function $f:\mathcal {D}\rightarrow \mathbb {R}$ as left-computable (or approximable from below) provided the set $\{(d,q): d\in \mathcal {D}\wedge q\in \mathbb {Q}\wedge q< f(d)\}$ is computably enumerable. Accordingly, a function $f:\mathcal {D}\rightarrow \mathbb {R}$ is called right-computable (or approximable from above) if the set $\{(d,q): d\in \mathcal {D}\wedge q\in \mathbb {Q}\wedge q> f(d)\}$ is computably enumerable, and f is computable if f is right and left-computable. Accordingly, a real number $\alpha \in \mathbb {R}$ is left-computable, right computable or computable provided the constant function c _α (t) = α is left-computable, right-computable or computable, respectively.

If we refer to a function $f:\mathcal {D}\rightarrow \mathbb {Q}$ as computable we usually mean that it maps the domain $\mathcal D$ to the domain $\mathbb {Q}$, that is, it returns the exact value $f(d)\in \mathbb {Q}$.

1.2 Semi-Measures and Kolmogorov Complexity

In this part we introduce those variants of Kolmogorov complexity which we will consider in the subsequent parts. The first two of them can be related to left-computable semi-measures on X ^∗. For the third one—monotone complexity—we use the relation based approach (see [41, 43]).

1.2.1 Prefix Complexity

A function $\nu :X^{*}\to \mathbb {R}_{+}$ is referred to as a (discrete)semi-measure provided ${\sum }_{w\in X^{*}}\nu (w)<\infty$. It is well-known ([2, 6, 16]) that there is a universal left-computable discrete semi-measure $\mathbf {m}:X^{*}\to \mathbb {R}_{+}$ such that for every left-computable discrete semi-measure ν there is a constant c _ν > 0 such that m(w) ≥ c _ν ⋅ ν(w) for all w ∈ X ^∗.

Fix a universal left-computable discrete semi-measure $\mathbf {m}:X^{*}\to \mathbb {R}_{+}$ with m(w) ≤ 1 for all w ∈ X ^∗. Then H(w) := ⌈−log |X|ν(w)⌉ is the prefix complexity of the word w ∈ X ^∗.

1.2.2 A Priori Complexity

A continuous (or cylindrical) semi-measure on X ^∗ is a function $\mu :X^{*}\to \mathbb {R}_{+}$ which satisfies μ(e) ≤ 1 and $\mu (w) \geq {\sum }_{x \in X} \mu (wx)$, for w ∈ X ^∗. If there is no danger of confusion, in the sequel we will refer to continuous (semi)-measures simply as (semi)-measures.

If $\mu (w)={\sum }_{x\in X}\mu (wx)$ the function μ is called a measure. A continuous semi-measure μ has the following property.

Proposition 1

If C ⊆ w ⋅ X ^∗ is prefix-free then $\mu (w)\geq {\sum }_{v\in C}\mu (v)$ .

In [44] the existence of a universal left-computable semi-measure M is proved: There is a left-computable semi-measure M which satisfies

$$ \exists c_{m}>0 \, \forall w \in X^{*}: \mu(w)\leq c_{m} \cdot \mathbf{M}(w), $$

(1)

for all left-computable semi-measures μ.

The a priori complexity of a word w ∈ X ^∗ is defined as

$$ \textstyle \text{KA}(w):= \lceil-\log_{|X|} \mathbf{M}(w)\rceil\,. $$

(2)

The properties of the semi-measure M imply KA(w) ≤KA(w ⋅ v) and ${\sum }_{v\in C}|X|^{-\text {KA}(v)}\le \mathbf {M}(e)$ when C ⊆ X ^∗ is prefix-free.

A simple computable continuous measure is μ ₌(w) := |X|^−|w|. Since M is universal, we have M(w) ≥ c ⋅|X|^−|w| for every w ∈ X ^∗. Thus KA(w) ≤|w| + c ^′.

1.2.3 Monotone Complexity

In this section we introduce the monotone complexity along the lines of [41, 43]. To this end let E ⊆ X ^∗× X ^∗ be a description mode (a computably enumerable set) which satisfies the condition.

$$ (\pi,w), (\pi^{\prime},v)\in E\wedge \pi\sqsubseteq \pi^{\prime}\rightarrow w\sqsubseteq v\vee v\sqsubseteq w $$

(3)

Then $K_{E}(w):= \inf \{|\pi |: \exists u(w\sqsubseteq u\wedge (\pi ,u)\in E)\}$ is the monotone complexity of the word w w.r.t. E. In [41, § 3.2] it is shown that there is a description mode $\mathcal {E}$ universal among all description modes, that is, $K_{E}(w)\le K_{\mathcal {E}}(w)+ c_{E}$ for all w ∈ X ^∗ and some constant not depending on w. In the sequel we use the term Km for $K_{\mathcal {E}}$. Since E ₌ := {(w,w) : w ∈ X ^∗} is a description mode satisfying (3) we have Km(w) ≤|w| + O(1).

Finally we mention some relations between the complexities H,KA and Km (see [6, 43]).

$$\begin{array}{@{}rcl@{}} \text{KA}(w)\le \text{Km}(w) + O(1)&,&\text{Km}(w)\le \mathrm{H}(w)+ O(1) \end{array} $$

(4)

$$\begin{array}{@{}rcl@{}} |K_{1}(w)- K_{2}(w)|&\le& O(\log|w|)\text{ for }K_{i}\in \{\mathrm{H}, \text{KA},\text{Km}\} \end{array} $$

(5)

It should be mentioned that the inequalities in (5) cannot be reversed, that is, the differences |Km(w) −KA(w)| and |H(w) −Km(w)| are unbounded.

What concerns transformations with (partially defined) computable mappings we have the following.

Proposition 2

Let φ : X ^∗→ X ^∗ be a prefix-monotone partial computable function and let K ∈{H,KA,Km}. Then there is a constant c _φ such that K(φ(w)) ≤ K(w) + c _φ for all w ∈ X ^∗ .

In the case of prefix complexity H we can drop the requirement that φ be prefix-monotone.

Proof 1

In the case of H define a discrete semi-measure ν(w) := m(φ(w)). Then ν is left-computable and the assertion follows from ν(w) ≤ c _φ ⋅m(w).

For Km define $E_{\varphi }:=\{(\pi ^{\prime },\varphi (w)): \exists \pi (\pi \sqsubseteq \pi ^{\prime }\wedge (\pi ,w)\in \mathcal {E})\}$. Then E _φ is computably enumerable and satisfies (3).

Since $\mathcal {E}$ is a universal description mode satisfying (3), we have $K_{E_{\varphi }}(\varphi (w))\leq K_{\mathcal {E}}(w)+c_{\varphi }$.

The proof for KA is more complicated and can be found in [16, Section 4.2.2] or in a more detailed form in [38]. □

1.2.4 Complexity of Infinite Words

A simple and natural way to extend the complexity of finite words to infinite ones is to consider, for ξ ∈ X ^ω, the Kolmogorov complexity function for infinite words $K(\xi \upharpoonright n)$ where K is a complexity of finite words as mentioned in the preceding part.

In connection with constructive dimension (see e.g. [6, 19]) the following variant of asymptotic complexity plays a major rôle.

$$ \underline{\kappa}(\xi):= {\liminf}_{n\to\infty}\frac{K(\xi\upharpoonright n)}{n} $$

(6)

In view of (5) it is apparent that the actual variant of complexity is not essential here (see also [1]).

1.3 Gauge Functions and Hausdorff’s Original Approach

A function h : (0,∞) → (0,∞) is referred to as a gauge function (or dimension function [10] ) provided h is right continuous and non-decreasing.² If not stated otherwise, we will assume that $\lim _{t\to 0} h(t)=0$.

The h-dimensional outer measure of F on the space X ^ω is given by

$$ {\mathcal H}^{h}(F):= \lim_{n\to\infty}\inf\left\{{\textstyle\sum\limits_{v\in V}}h(r^{-|v|}): V\subseteq X^{*}\wedge F\subseteq V\cdot X^{\omega}\wedge \min_{v\in V}|v| \geq n\right\} \,. $$

(7)

If $\lim _{t\to 0}h(t)> 0$ then $\mathcal {H}^{h}(F)<\infty$ if and only if F is finite.

For $\alpha \in \mathbb {R}_{+}$ the α-dimensional Hausdorff measure ${\mathcal H}^{\alpha }$ is defined by the gauge functions h _α (t) = t ^α,α ∈ [0,1], that is, ${\mathcal H}^{\alpha }={\mathcal H}^{h_{\alpha }}$.

In this case the (also referred to as “classical” in [6, Chapter 13.1]) Hausdorff dimension of a set F ⊆ X ^ω is defined as the change-over point in the plot of Fig. 1.

$$ \dim_{H}F:= \sup\{\alpha: \alpha=0\vee{\mathcal H}^{\alpha}(F) = \infty\}= \inf\{\alpha: \wedge{\mathcal H}^{\alpha}(F)=0\}\,. $$

(8)

Fig. 1

Plot of $\mathcal {H}^{\alpha }(F)$ as a function of α

The following properties of gauge functions h and the related measure ${\mathcal H}^{h}$ are proved in the standard way (see e.g. [7, 10] or [27, Theorem 40]).

Property 1

Let h,h ^′ be gauge functions.

• 1. If c ⋅ h(r ⁻ⁿ) ≤ h ^′(r ⁻ⁿ) for some c > 0, then $c\cdot {\mathcal H}^{h}(F)\le {\mathcal H}^{h^{\prime }}(F)$.

• 2. If $\lim \limits _{n\to \infty } \frac {h(r^{-n})}{h^{\prime }(r^{-n})}=0$ then ${\mathcal H}^{h^{\prime }}(F)<\infty$ implies ${\mathcal H}^{h}(F)=0$, and ${\mathcal H}^{h}(F)>0$ implies ${\mathcal H}^{h^{\prime }}(F)=\infty$.

Here the first property implies a certain equivalence of gauge functions. In fact, if c ⋅ h ≤ h ^′ and c ⋅ h ^′≤ h in the sense of Property 1.1 then for all F ⊆ X ^ω the measures ${\mathcal H}^{h}(F)$ and ${\mathcal H}^{h^{\prime }}(F)$ are both zero, finite or infinite.

As we see from (7) for our purposes the behaviour of gauge functions is of interest only for large values of n, that is, in a small vicinity of 0. Moreover, in many cases we are not interested in the exact value of ${\mathcal H}^{h}(F)$ when $0<{\mathcal H}^{h}(F)<\infty$. Thus we can often make use of scaling a gauge function and altering it in a range (ε,∞) apart from 0.

In the same way the second property gives a partial pre-order of gauge functions (see [27, Chapter 2, § 4]). By analogy to the change-over-point α ₀ = dimH F for ${\mathcal H}^{\alpha }(F)$ this partial pre-order yields a suitable notion of Hausdorff dimension in the range of arbitrary gauge functions.

Definition 1

We refer to a gauge function h as an exact Hausdorff dimension function for F ⊆ X ^ω provided

$$\mathcal{H}^{h^{\prime}}(F)=\left\{\begin{array}{ll} \infty\,,&\text{ if }\lim\limits_{n\to\infty} \frac{h(r^{-n})}{h^{\prime}(r^{-n})}=0\text{ , and}\\ 0\,,&\text{ if }\lim\limits_{n\to\infty} \frac{h^{\prime}(r^{-n})}{h(r^{-n})}=0\,. \end{array}\right. $$

Hausdorff [12] called a function h dimension of F provided $0<{\mathcal H}^{h}(F)<\infty$. This case is covered by our definition and Property 1.

Partitioning the gauge (or dimension) functions into those for which $\mathcal {H}^{h}(F)$ is finite and those for which $\mathcal {H}^{h}(F)$ is infinite gives a more precise indication to the ‘dimension’ of F than just the number α = dimH F from above.

As in [27, Chapter 2, §4] Definition 1 leads to a partial ordering of gauge functions

$$h\prec h^{\prime}\iff \lim\limits_{n\to\infty} \frac{h^{\prime}(r^{-n})}{h(r^{-n})}=0 $$

by saying that h corresponds to a smaller dimension than h ^′.³ This partial ordering is not as simple as the one of the classical Hausdorff dimension in (8), and it seems to be much more difficult to find the exact borderline, if it exists, between gauge functions with $\mathcal {H}^{h}(F)=0$ and such with $\mathcal {H}^{h}(F)=\infty$. In fact, Eggleston [8, 9] (see also [27, Theorem 42]) proved that there are sets F which have functions $h,\bar h$ both satisfying Definition 1 such that $\limsup _{n\to \infty }\frac {h(r^{-n})}{\bar h(r^{-n})}= \limsup _{n\to \infty }\frac {\bar h(r^{-n})}{h(r^{-n})}=\infty$. This, in particular, implies that one cannot always compare two sets E,F ⊆ X ^ω and say that one or the other of the two must be the smaller from the point of Hausdorff dimension due to the lack of total ordering among the gauge functions.

One easily observes that h ₁(t) := t yields ${\mathcal H}^{h_{1}}(F)\le 1$, thus ${\mathcal H}^{h}(F)=0$ for all h with h ₁ ≺ h. Therefore, we can always assume that a gauge function satisfies h(t) ≥ t, t ∈ (0,1).

1.4 Kolmogorov Complexity and Hausdorff Dimension

In this part we briefly recall known results relating classical Hausdorff dimension and (asymptotic) Kolmogorov complexity. Then in the subsequent sections we generalise them to the case of exact Hausdorff dimension and Kolmogorov complexity functions. For a more detailed account on previous results see the above mentioned books [2, 6, 16] or the survey [34].

1.4.1 Martingales and Hausdorff Dimension

Closely related to the invention of constructive dimension is the notion of martingale. Martingales had already been used successfully to characterise randomness and in conjunction with order functions the order of randomness [30]. A similar approach was pursued when Lutz [18, 19] constructivised Hausdorff dimension using what he called s-(super-)gales, a combination of (super-)martingales and exponential order functions (see [40, Section 4.2]). We follow Schnorr’s approach, because it seems that the combination of (super-)martingales with order functions is more flexible at least in two respects: on the one hand, as in the investigation of Hausdorff dimension, it allows for the use of order functions other than exponential ones. On the other hand, a comparison of Theorem 3 below with Theorem 4.4 of [13] shows that computable martingales may achieve non-computable (exponential) order functions, something which is not possible for s-gales, as computable s-gales exist only for computable reals $s\in \mathbb {R}$.

A super-martingale is a function $\mathcal {V}: X^{*}\to \mathbb {R}_{+}$ which satisfies $\mathcal {V}(e)\le 1$ and the super-martingale inequality

$$ \textstyle r\cdot \mathcal{V}(w)\ge {\sum}_{x\in X} \mathcal{V}(wx) \text{ for all }w\in X^{*}\,. $$

(9)

If (9) is satisfied with equality $\mathcal {V}$ is called a martingale. Closely related with (super-) martingales are continuous (or cylindrical) (semi-)measures μ : X ^∗→ [0,1] where μ(e) ≤ 1 and $\mu (w)\ge \sum \nolimits _{x\in X} \mu (wx)$ for all w ∈ X ^∗.

Indeed, if $\mathcal {V}$ is a super-martingale then μ defined by the key equation

$$ \mu(w):= r^{-|w|}\cdot \mathcal{V}(w) $$

(10)

is a continuous semi-measure, and vice versa. Moreover, from Proposition 1 we obtain

$$ r^{-|w|}\cdot\mathcal{V}(w)\geq {\sum}_{v\in C}r^{-|v|}\cdot\mathcal{V}(v) $$

(11)

if C ⊆ w ⋅ X ^∗ is prefix-free.

Let

$$ S_{c,h}[\mathcal{V}]:= \left\{\xi: \xi\in X^{\omega}\wedge \limsup_{n\to\infty} \frac{\mathcal{V}(\xi\upharpoonright n)}{r^{n}\cdot h(r^{-n})}\ge c\right\}\,, $$

(12)

for a super-martingale $\mathcal {V}: X^{*}\to [0,\infty )$, a gauge function h and a threshold c ∈ (0,∞]. The following relations for gauge functions h,h ^′ and thresholds c,c ^′ are obvious.

Lemma 1

If c ≥ c ^′ then $S_{c,h}[\mathcal {V}]\subseteq S_{c^{\prime },h}[\mathcal {V}]$ , and if h ≺ h ^′ then $S_{c,h}[\mathcal {V}]\subseteq S_{c,h^{\prime }}[\mathcal {V}]$ .

In particular, $S_{\infty ,h}[\mathcal {V}]$ is the set of all ω-words on which the super-martingale $\mathcal {V}$ is successful w.r.t. the order function f(n) = r ⁿ ⋅ h(r ⁻ⁿ) in the sense of Schnorr [30]. $S_{\infty ,h}[\mathcal {V}]$ is also referred to as the success set of the super-martingale $\mathcal {V}$ w.r.t. the order function f(n) = r ⁿ ⋅ h(r ⁻ⁿ).

Schnorr [30] required an order function $f:\mathbb {N}\to \mathbb {N}$ to be non-decreasing, unbounded and computable. For our purposes it is more convenient to consider $f:\mathbb {N}\to \mathbb {R}_{+}$ only as a real-valued non-decreasing function. Nevertheless, this does not guarantee that f(n) = r ⁿ ⋅ h(r ⁻ⁿ) is always an order function whenever h is a gauge function and h(0) = 0. The following gives a sufficient condition. We call a function $h:\mathbb {R}_{+}\to \mathbb {R}_{+}$ upwardly convex if (t ₁ − t ₀) ⋅ h(t ^′) ≥ h(t ₀) + (t ^′− t ₀) ⋅ (h(t ₁) − h(t ₀)) for 0 ≤ t ₀ < t ^′ < t ₁.

Lemma 2

If a gauge function $h:[0,1]\to \mathbb {R}_{+}$ is upwardly convex then f(n) := r ⁿ ⋅ h(r ⁻ⁿ)is an order function.

Proof 2

It suffices to show that h(t)/t is non-increasing.

If h is upwardly convex then (t ₁ − t ₀) ⋅ h(t ^′) ≥ h(t ₀) + (t ^′− t ₀) ⋅ (h(t ₁) − h(t ₀)) when 0 ≤ t ₀ < t ^′ < t ₁ ≤ 1. Thus t ₁ = t and t ₀ = 0 imply t ⋅ h(t ^′) ≥ t ^′⋅ h(t) + (1 − t ^′) ⋅ h(0) ≥ t ^′⋅ h(t). □

The converse of Lemma 2 is not true.

Example 1

Set $h(t):= \left \{\begin {array}{ll} \sqrt {t}&\text { if }0\le t\le 1/4\\ 1/2&\text { if }1/4\le t\le 1/2\text {, and }\\ t&\text { otherwise}\,. \end {array}\right .$

Then $h(t)/t:= \left \{\begin {array}{ll} 1/\sqrt {t}&\text { if }0\le t\le 1/4\\ 1/2t&\text { if }1/4\le t\le 1/2\text {, and }\\ 1&\text { otherwise}\,. \end {array}\right .$

Thus h(t)/t is non-increasing but $\frac {3}{4}\cdot h(1/2)=\frac {3}{8}< h(1/4)+ \frac {1}{4}\cdot (h(1)- h(1/4))=\frac {5}{8}$.

Lutz [18, 19] coined the term s-(super-)gale for the combination $d(w):= \mathcal {V}(w)/(r^{|w|}\cdot r^{-s|w|})$ of a (super-)martingale $\mathcal {V}$ with the gauge function h(t) = t ^s or, alternatively with the order function f(n) = r ^(1−s)⋅n. He then proved the following relation between success sets and classical Hausdorff dimension.

Theorem 1 (18)

Let F ⊆ X ^ω . Then

$$\dim_{H} F<\alpha \ \rightarrow\ \exists\mathcal{V}(F\subseteq S_{\infty,t^{\alpha}}[\mathcal{V}])\ \rightarrow\ \dim_{H} F\leq\alpha\,. $$

1.4.2 Constructive Dimension and Asymptotic Kolmogorov Complexity

In [19] Lutz invented constructive dimension by restricting to success sets of left-computable super-martingales. In this case the condition $\exists \mathcal {V}(F\subseteq S_{\infty ,t^{\alpha }}[\mathcal {V}])$ turns out to be simpler because the results of Levin [44] and Schnorr [30] show that there is an optimal left-computable super-martingale $\mathcal {U}$, that is, every other left-computable super-martingale $\mathcal {V}$ satisfies $\mathcal {V}(w)\le c_{\mathcal {V}}\cdot \mathcal {U}(w)$ for all w ∈ X ^∗ and some constant $c_{\mathcal {V}}>0$ not depending on w.

Thus we may define the constructive dimension of F ⊆ X ^ω as $\inf \{\alpha : F\subseteq S_{\infty ,t^{\alpha }}[\mathcal {U}]\}$. Using our key equation (10) and the definitions of $\underline {\kappa }$ and KA in (6) and (2), respectively, we obtain immediately the coincidence of constructive dimension and asymptotic Kolmogorov complexity (see [22, Theorem 1] and for a more detailed discussion [33]).

Corollary 1

Let F ⊆ X ^ω . Then

$$\sup\{\underline{\kappa}(\xi):\xi\in F\} = \inf \left\{\alpha: F\subseteq S_{\infty,\alpha}[\mathcal{U}]\right\}\,. $$

In [28, 29] Ryabko proved results which related Hausdorff dimension to asymptotic Kolmogorov complexity.

Theorem 2

[28]Let F ⊆ X ^ω . Then

$$\dim_{H}\{\xi: \xi\in X^{\omega}\wedge \underline{\kappa}(\xi)<\alpha\}=\alpha\,. $$

The proof of the inequality ≤ is based on the principle “large sets contain complex elements” (cf. also Theorem 6 below).

Lemma 3

[29] $\dim _{H}F\le \sup \{\underline {\kappa }(\xi ):\xi \in F\}$

The other direction is constructive: for rational α ^′ < α, ω-languages $E\subset \{\xi : \underline {\kappa }(\xi )<\alpha \}$ having dimension dimH E ≥ α ^′ are constructed (cf. Theorem 10 below).

Ryabko’s results, however, give no bounds on the actual Kolmogorov complexity functions $K(\xi \upharpoonright n)$ when ξ ∈ F and dimH F = α. Those results were derived in [3, 23, 31] or for the the particular case of ω-languages definable by finite automata in [31, 35].

1.4.3 Bounds for Σ₂-definable ω-languages

The lower bound given in Lemma 3 might be quite loose depending on the structure of the ω-language F. In [13, 32]) it was shown that this bound is also an upper bound for Σ₂-definable ω-languages. Here, as usual, we refer to an ω-language F ⊆ X ^ω as Σ ₂ -definable provided there is a computable relation $\mathbf {R}\subseteq X^{*}\times \mathbb {N}$ such that $F= \{\xi : \exists i \forall n\left ((\xi \upharpoonright n, i)\in \mathbf {R}\right )\}$. The bound can be actually shown already for computable dimension (see [32, Theorem 11] or [13, Theorem 4.4]).

Lemma 4

If F ⊆ X ^ω is Σ₂ -definable and α > dimH F then there is a computable martingale $\mathcal {V}$ such that $\limsup \limits _{n\to \infty } \frac {\mathcal {V}(\xi \upharpoonright n)}{r^{(1-\alpha )\cdot n}}=\infty$ for all ξ ∈ F .

Since there are only countably many Σ₂-definable ω-languages F ⊆ X ^ω we obtain the following.

Corollary 2 ([13, 32])

If F ⊆ X ^ω is a union of Σ₂ -definable sets then $\dim _{H}F =\sup \{\underline {\kappa }(\xi ):\xi \in F\}$ .

Moreover, the proof of Theorem 11 of [32] yields a slight strengthening of Lemma 4.

Theorem 3

If F ⊆ X ^ω is Σ₂ -definable and α ≥ dimH F is a right-computable real then there is a computable martingale $\mathcal {V}$ such that for all ξ ∈ F there is a constant c _ξ > 0such that $\mathcal {V}(\xi \upharpoonright n)\ge _{i.o.} c_{\xi }\cdot r^{(1-\alpha )\cdot n}$ .

So far the reviewed results concern “classical” Hausdorff dimension. The subsequent sections are devoted to generalisations of these results to the case of exact Hausdorff dimension and gauge functions.

2 Exact Hausdorff Dimension and Martingales

In this section we show the generalisation of Lutz’s theorem (Theorem 1) for arbitrary gauge functions. In view of Property 1 we split the assertion into two parts.

Lemma 5

Let F ⊆ X ^ω and h,h ^′ be gauge functions such that h ≺ h ^′ and $\mathcal {H}^{h}(F)<\infty$ . Then $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {V}]$ for some martingale $\mathcal {V}$ .

Proof 3

First we follow the lines of the proof of Theorem 13.2.3 in [6] and show the assertion for $\mathcal {H}^{h}(F)=0$. Thus there are prefix-free subsets U _i ⊆ X ^∗ such that $F\subseteq \bigcap _{i\in \mathbb {N}} U_{i}\cdot X^{\omega }$ and ${\sum }_{u\in U_{i}} h(r^{-|u|})\le 2^{-i}$.

$$\text{Define}~\mathcal{V}_{i}(w) := \left\{\begin{array}{l} r^{|w|}\cdot {\sum}_{wu\in U_{i}} h(r^{-|wu|}),\text{ if }w\in\mathbf{pref}({U_{i}})\setminus U_{i}\text{ , and}\\ \sup\{r^{|v|}\cdot h(r^{-|v|}): v\sqsubseteq w\wedge v\in U_{i}\},\text{ otherwise.} \end{array}\right. $$

In order to prove that $\mathcal {V}_{i}$ is a martingale we consider three cases:

w ∈p r e f(U _i ) ∖ U _i ::

Since then $U_{i}\cap w\cdot X^{*}= \bigcup _{x\in X}U_{i}\cap wx\cdot X^{*}$, we have $\mathcal {V}_{i}(w) = r^{|w|}\cdot {\sum }_{wu\in U_{i}} h(r^{-|wu|})= r^{-1}\cdot {\sum }_{x\in X} r^{|wx|}{\sum }_{wxu\in U_{i}} h(r^{-|wxu|}) = r^{-1}\cdot {\sum }_{x\in X} \mathcal {V}_{i}(wx)$.

w ∈ U _i ⋅ X ^∗ ::

Let w ∈ v ⋅ X ^∗ where v ∈ U _i . Then $\mathcal {V}_{i}(w)= \mathcal {V}_{i}(wx)= r^{|v|}\cdot h(r^{-|v|})$ whence $\mathcal {V}_{i}(w)=r^{-1}\cdot {\sum }_{x\in X}\mathcal {V}_{i}(wx)$.

w∉p r e f(U _i ) ∪ U _i ⋅ X ^∗ ::

Here $\mathcal {V}_{i}(w)=\mathcal {V}_{i}(wx)=0$.

Now, set $\mathcal {V}(w) :={\sum }_{i\in \mathbb {N}}\mathcal {V}_{i}(w)$.

Then, for $\xi \in \bigcap _{i\in \mathbb {N}} U_{i}\cdot X^{\omega }$ there are $n_{i}\in \mathbb {N}$ such that $\xi \upharpoonright n_{i}\in U_{i}$ and we obtain $\frac {\mathcal {V}(\xi \upharpoonright n_{i})}{r^{n_{i}}\cdot h^{\prime }(r^{-n_{i}})}\geq \frac {\mathcal {V}_{i}(\xi \upharpoonright n_{i})}{r^{n_{i}}\cdot h^{\prime }(r^{-n_{i}})}=\frac {h(r^{-n_{i}})}{h^{\prime }(r^{-n_{i}})}$ which tends to infinity as i tends to infinity.

Now let $\mathcal {H}^{h}(F)<\infty$. Then $h\prec \sqrt {h\cdot h^{\prime }}\prec h^{\prime }$. Thus $\mathcal {H}^{\sqrt {h\cdot h^{\prime }}}(F)=0$ and we can apply the first part of the proof to the functions $\sqrt {h\cdot h^{\prime }}$ and h ^′. □

The next lemma is in some sense a converse to Lemma 5.

Lemma 6

Let h be a gauge function, c ∈ (0,∞]and $\mathcal {V}$ be a super-martingale. Then $\mathcal {H}^{h}(S_{c,h}[\mathcal {V}])\le \frac {\mathcal {V}(e)}{c}$ .

Proof 4

It suffices to prove the assertion for c < ∞.

Define $V_{k}:= \{w: w\in X^{*}\wedge |w|\ge k\wedge \frac {\mathcal {V}(w)}{r^{|w|}\cdot h(r^{-|w|})}\ge c-2^{-k}\}$ and set $U_{k}:= \text {Min}_{\sqsubseteq }V_{k}$. Then $S_{c,h}[\mathcal {V}]\subseteq \bigcap _{k\in \mathbb {N}}U_{k}\cdot X^{\omega }$.

$$\begin{array}{rcl}\textstyle \text{Now }\sum\limits_{w\in U_{k}} h(r^{-|w|})&\le&\textstyle \sum\limits_{w\in U_{k}} h(r^{-|w|})\cdot \frac{\mathcal{V}(w)}{r^{|w|}\cdot h(r^{-|w|})}\cdot \frac{1}{c-2^{-k}}\\{} &=&\textstyle \frac{1}{c-2^{-k}}\cdot \sum\limits_{w\in U_{k}} \frac{\mathcal{V}(w)}{r^{|w|}}\ \le\ \frac{\mathcal{V}(e)}{c- 2^{-k}}\text{ (cf. (11)).} \end{array} $$

Thus $\mathcal {H}^{h}(\bigcap _{k\in \mathbb {N}}U_{k}\cdot X^{\omega })\le \frac {\mathcal {V}(e)}{c}$. □

Lemmata 5 and 6 yield the following martingale characterisation of exact Hausdorff dimension functions.

Theorem 4

Let F ⊆ X ^ω . Then a gauge function h is an exact Hausdorff dimension function for F if and only if

• 1. for all gauge functions h ^′ with h ≺ h ^′ there is a super-martingale $\mathcal {V}$ such that $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {V}]$ , and

• 2. for all gauge functions h ^″ with h ^″≺ h and all super-martingales $\mathcal {V}$ it holds $F\not \subseteq S_{\infty ,h^{\prime \prime }}[\mathcal {V}]$ .

Proof 5

Assume h to be exact for F and h ≺ h ^′. Then $h\prec \sqrt {h\cdot h^{\prime }}\prec h^{\prime }$. Thus $\mathcal {H}^{\sqrt {h\cdot h^{\prime }}}(F)=0$ and applying Lemma 5 to $\sqrt {h\cdot h^{\prime }}$ and h ^′ yields a super-martingale $\mathcal {V}$ such that $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {V}]$.

If h ^″≺ h then $\mathcal {H}^{h^{\prime \prime }}(F)=\infty$ and according to Lemma 6 $F\not \subseteq S_{\infty ,h^{\prime \prime }}[\mathcal {V}]$ for all super-martingales $\mathcal {V}$.

Conversely, let Conditions 1 and 2 be satisfied. Let h ≺ h ^′, and let $\mathcal {V}$ be a super-martingale such that $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {V}]$. Now Lemma 6 shows $\mathcal {H}^{h^{\prime }}(F)\le \mathcal {H}^{h^{\prime }}(S_{\infty ,h^{\prime }}[\mathcal {V}])=0$.

Finally, suppose h ^″≺ h and $\mathcal {H}^{h^{\prime \prime }}(F)<\infty$. Then $\mathcal {H}^{\sqrt {h\cdot h^{\prime \prime }}}(F)=0$ and Lemma 5 shows that there is a super-martingale $\mathcal {V}$ such that $F\subseteq S_{\infty ,\sqrt {h\cdot h^{\prime \prime }}}[\mathcal {V}]$. This contradicts Condition 2. □

Lemmata 5 and 6 also show that we can likewise formulate Theorem 4 for martingales instead of super-martingales.

3 Constructive Dimension: the Exact Case

Constructive dimension is a variant of dimension defined analogously to Theorem 4 using only left-computable super-martingales. As mentioned above, in this case we can simplify our considerations using an optimal left-computable super-martingale. For definiteness we use $\mathcal {U}(w):= r^{|w|}\cdot \mathbf {M}(w)$ where M is the universal left-computable semi-measure from Section 1.2.2. Thus we may define

Definition 2

Let F ⊆ X ^ω. We refer to $h:\mathbb {R}\to \mathbb {R}$ as an exact constructive dimension function for F provided $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {U}]$ for all h ^′,h ≺ h ^′, and $F\not \subseteq S_{\infty ,h^{\prime \prime }}[\mathcal {U}]$ for all h ^″,h ^″≺ h.

The next theorem follows immediately from the identity $\mathcal {U}(w)= r^{|w|}\cdot \mathbf {M}(w)$ and the inequality M(w) ≥M(w ⋅ v).

Theorem 5

The function h _ξ defined by $h_{\xi }(r^{-n}):= \mathbf {M}(\xi \upharpoonright n)$ is an exact constructive dimension function for the set {ξ}.

In view of (2) also $h^{\prime }_{\xi }(r^{-n}):= r^{-\text {KA}(\xi \upharpoonright n)}$ is an exact constructive dimension function for the set {ξ}. In contrast to the asymptotic case, however, this does not hold for other complexities, like the monotone complexity Km, prefix complexity H or plain complexity. For the latter two this is made apparent by considering computable ω-words or Martin-Löf random ω-words. Corollary 4.5.2 of [6] shows that also Km and KA differ more than by a constant for certain ω-words.

Next we are going to show that the principle “large sets contain complex elements” holds also for exact Hausdorff dimension. We obtain the following bound from [23].

Theorem 6

Let F ⊆ X ^ω , h be a gauge function and $\mathcal {H}^{h}(F)>0$ .

Then for every c > 0with $\mathcal {H}^{h}(F)>c\cdot \mathbf {M}(e)$ there is a ξ ∈ F such that $\text {KA}(\xi \upharpoonright n)\ge _{\text {ae}} -\log _{r} h(r^{-n}) +\log _{r} c$ .

For the sake of completeness we give a short proof. To this end we introduce the δ-limit W ^δ := {ξ : ξ ∈ X ^ω ∧|p r e f(ξ) ∩ W| = ∞} of a language W ⊆ X ^∗.

Proof 6

It is readily seen that the set of infinite words not fulfilling the asserted inequality is the δ-limit of W _c = {w : KA(w) ≤−log r h(r ^−|w|) + log r c}.

Let $V_{m}= \text {Min}_{\sqsubseteq }(W_{c} \cap X^{m}\cdot X^{*})$. Then V _m is prefix-free and $W_{c}^{\delta }\subseteq V_{m}\cdot X^{\omega }$ for all $m\in \mathbb {N}$. Consequently, $\mathcal {H}^{h}(W_{c}^{\delta })\le {\sum }_{v\in V_{m}} h(r^{-|v|})$ and in view of (1) we have ${\sum }_{v\in V_{m}} h(r^{-|v|})\le c\cdot {\sum }_{v\in V_{m}}r^{-\text {KA}(v)}\le c\cdot {\sum }_{v\in V_{m}}\mathbf {M}(v)\le c\cdot \mathbf {M}(e)$ . Now the inequality $\mathcal {H}^{h}(F) > \mathcal {H}^{h}(W_{c}^{\delta })$ shows the assertion $F\not \subseteq W_{c}^{\delta }$. □

This lower bound on the maximum complexity of an infinite string in F yields a set-theoretic lower bound on the success sets $S_{c,h}[\mathcal {U}]$ of $\mathcal {U}$.

Theorem 7

Let $c\in \mathbb {R}$ and let h be a gauge function. Then there is a c ^′ > 0such that

$$\{\xi: \exists^{\infty}n(\text{KA}(\xi\upharpoonright n)\leq -\log_{r} h(r^{-n})+c)\}\subseteq S_{c^{\prime},h}[\mathcal{U}]. $$

Proof 7

If ξ has infinitely many prefixes such that $\text {KA}(\xi \upharpoonright n) \leq -\log _{r}h(r^{-n})+c$ then $\mathbf {M}(\xi \upharpoonright n)\ge r^{-\text {KA}(\xi \upharpoonright n)}\ge h(r^{-n})\cdot r^{-c}$. Since $\mathcal {U}(w)=r^{|w|}\cdot \mathbf {M}(w)$ , we obtain $\limsup \limits _{n\to \infty } \frac {\mathcal {U}(\xi \upharpoonright n)}{r^{n}\cdot h(r^{-n})}= \limsup \limits _{n\to \infty }\frac {\mathbf {M}(\xi \upharpoonright n)}{h(r^{-n})}\ge r^{-c}$. □

Corollary 3

Let h,h ^′ be gauge functions such that h ≺ h ^′ and $c\in \mathbb {R}$ . Then

• 1. $\{\xi :\text {KA}(\xi \upharpoonright n)\leq _{\text {io}}\log _{r} h(r^{-n})+c\}\subseteq S_{\infty ,h^{\prime }}[\mathcal {U}]$ , and

• 2. $\mathcal {H}^{h^{\prime }}\left (\{\xi :\text {KA}(\xi \upharpoonright n)\leq _{\text {io}} -\log _{r} h(r^{-n})+c\}\right )=0$ .

4 Complexity and Dilution

In this section we are going to show that, analogously to Ryabko’s proof for the “usual” dimension, the bound given in Corollary 3 is tight for a large class of (computable) gauge functions. To this end we prove that certain sets of infinite strings diluted according to a gauge function h have positive Hausdorff measure $\mathcal {H}^{h}$.

4.1 A Generalised Dilution Principle

We show that for a large family of gauge functions, a set of finite positive measures can be constructed. Our construction is a generalisation of Hausdorff’s 1918 construction. Instead of his method of cutting out middle thirds in the unit interval we use the idea of dilution functions as presented in [35]. In fact dilution appears much earlier (see e.g. [5, 19, 25, 31])

We consider prefix-monotone mappings, that is, mappings φ : X ^∗→ X ^∗ satisfying $\varphi (w)\sqsubseteq \varphi (v)$ whenever $w\sqsubseteq v$. We call a function $g:\mathbb {N}\rightarrow \mathbb {N}$ a modulus function for φ provided |φ(w)| = g(|w|) for all w ∈ X ^∗. This, in particular, implies that |φ(w)| = |φ(v)| for |w| = |v| whenever φ has a modulus function.

Every prefix-monotone mapping φ : X ^∗→ X ^∗ defines as a limit a partial mapping $\overline {\varphi }:\subseteq X^{\omega }\rightarrow X^{\omega }$ in the following way: $\mathbf {pref}({\overline {\varphi }(\xi )})= \mathbf {pref}({\varphi (\mathbf {pref} (\xi ))})$ whenever φ(p r e f(ξ)) is an infinite set, and $\overline {\varphi }(\xi )$ is undefined when φ(p r e f(ξ)) is finite.

If, for some strictly increasing function $g:\mathbb {N}\to \mathbb {N}$, the mapping φ satisfies the conditions |φ(w)| = g(|w|) and for every v ∈p r e f(φ(X ^∗)) there are w _v ∈ X ^∗ and x _v ∈ X such that

$$ \varphi(w_{v})\sqsubset v\sqsubseteq \varphi(w_{v}\cdot x_{v})\wedge \forall y\left( y\in X \wedge y\ne x_{v}\to v\not\sqsubseteq \varphi(w_{v}\cdot y)\right) $$

(13)

then we call φ a dilution function with modulus g. If φ is a dilution function then $\overline {\varphi }$ is a one-to-one mapping.

For the image $\overline {\varphi }(X^{\omega })$ we obtain the following bounds on its Hausdorff measure (cf. the mapping theorem [27, Theorem 29]).

Theorem 8

Let $g: \mathbb {N}\to \mathbb {N}$ be a strictly increasing function, φ a corresponding dilution function and h : (0,∞) → (0,∞)be a gauge function. Then

• 1. $\mathcal {H}^{h}(\overline {\varphi }(X^{\omega }))\le \liminf \limits _{n\to \infty } \frac {h(r^{-g(n)})}{r^{-n}}$

• 2. If c ⋅ r ⁻ⁿ≤_ae h(r ^−g(n))then $c\le {\mathcal H}^{h}(\overline {\varphi }(X^{\omega }))$ .

Proof 8

The first assertion follows from $\overline {\varphi }(X^{\omega })\subseteq \bigcup _{|w|=n} \varphi (w)\cdot X^{\omega }$ and |φ(w)| = g(|w|).

The second assertion is obvious for ${\mathcal H}^{h}(\overline {\varphi }(X^{\omega }))=\infty$. Let the measure ${\mathcal H}^{h}(\overline {\varphi }(X^{\omega }))$ be finite, ε > 0, and $V\cdot X^{\omega } \supseteq \overline {\varphi }(X^{\omega })$ such that ${\sum }_{v\in V}h(r^{-|v|})\le \mathcal {H}^{h}(\overline {\varphi }(X^{\omega }))+\varepsilon$. Without loss of generality we may assume that V ⊆ X ^∗ is prefix-free. Then, since φ is a dilution function, for every v ∈ V there is at most one w _v ⋅ x _v such that $v\sqsubseteq \varphi (w_{v}\cdot x_{v})$.

Now, the set $W_{V}:=\{ w_{v}\cdot x_{v}: \exists v(v\in V\wedge \varphi (w_{v})\sqsubset v\sqsubseteq \varphi (w_{v}\cdot x_{v}))\}$ (see (13)) is prefix-free, and it holds W _V ⋅ X ^ω ⊇ X ^ω. Thus W _V is finite and ${\sum }_{w\in W_{V}} r^{-|w|}=1$.

Assume now min{|v| : v ∈ V } large enough such that c ⋅ r ^−|v|≤ h(r ^−g(|v|)) for all v ∈ V.

$$\begin{array}[t]{rcl}\text{Then }{\sum}_{v\in V}h(r^{-|v|})&\ge& {\sum}_{wx\in W_{V}}h(r^{-|\varphi(wx)|})={\sum}_{wx\in W_{V}}h(r^{-g(|wx|)})\\&\ge& {\sum}_{wx\in W_{V}}c\cdot r^{-|wx|}=c\,.\end{array} $$

As ε > 0 is arbitrary, the assertion follows. □

Corollary 4

If c ⋅ r ⁻ⁿ≤_ae h(r ^−g(n)) ≤ c ^′⋅ r ⁻ⁿ then $c\le {\mathcal H}^{h}(\overline {\varphi }(X^{\omega }))\le c^{\prime }$ .

In connection with Theorem 8 and Corollary 4 it is of interest which gauge functions allow for a construction of a set of positive finite measure via dilution. Hausdorff’s cutting out was demonstrated for upwardly convex gauge functions. We consider the slightly more general case of functions fulfilling the following (cf. also Lemma 2).

Lemma 7

Let $h:[0,1]\to \mathbb {R}_{+}$ be a gauge function h with $\lim _{t\to \infty }h(t)=0$ . If h(t)/t is non-increasing on (0,ε), ε ≤ 1,then there is an $n_{0}\in \mathbb {N}$ such that for all n ≥ n ₀ there is an $m\in \mathbb {N}$ satisfying

$$ r^{-n}< h(r^{-m})\le r^{-n+1}\,. $$

(14)

In particular, (14) implies that the gauge function h does not tend faster to 0 than the identity function $\text {id}: \mathbb {R}\to \mathbb {R}$.

Proof 9

We prove the assertion by induction on m.

Since $\lim _{t\to \infty }h(t)=0$, we may choose n ₀,m ₀ such that $r^{-(n_{0}+1)}< h(r^{-m_{0}})\le r^{-n_{0}}$. Now assume r ⁻⁽ⁿ⁺¹⁾ < h(r ^−m) ≤ r ⁻ⁿ for n ≥ n ₀,m ≥ m ₀.

Then $r^{-(n+2)}< \frac {h(r^{-m})}{r}\le r^{-(n+1)}$. Since $\frac {h(t)}{t}$ is non-increasing, we have r ^m ⋅ h(r ^−m) ≤ r ^(m+1) ⋅ h(r ^−(m+1)), that is, $\frac {h(r^{-m})}{r}\le h(r^{-(m+1)})\le h(r^{-m})$. Consequently, r ⁻⁽ⁿ⁺²⁾ < h(r ^−(m+1)) ≤ h(r ^−m) ≤ r ⁻ⁿ, and we have r ⁻⁽ⁿ⁺²⁾ < h(r ^−(m+1)) ≤ r ⁻⁽ⁿ⁺¹⁾ or r ⁻⁽ⁿ⁺¹⁾ < h(r ^−(m+1)) ≤ r ⁻ⁿ. □

Remark 1

Using the scaling factor $c=r^{n_{0}}$, that is, considering c ⋅ h instead of h and taking h ^′(t) = min{c ⋅ h(t),r} one can always assume that n ₀ = 0 and h ^′(1) > 1. Defining then $g(n):= \max \{m:m\in \mathbb {N}\wedge r^{-n}<h(r^{-m})\}$ we obtain via Property 1 and Corollary 4 that for every gauge function h fulfilling (14) there is a subset $F_{h}=\overline {\varphi }(X^{\omega })$ of X ^ω having finite and positive $\mathcal {H}^{h}$-measure.

As in Lemma 2 the condition of Lemma 7 is not necessary. We provide an example.

Example 2

Set $h(r^{-n}):= \left \{ \begin {array}{ll} r^{-n/2}&\text { if } n \text { is even, and}\\ r^{-(n+3)/2}+ r^{-n}&\text { if }n\text { is odd.}\end {array}\right .$ and extend h to a continuous non-decreasing function. Then h(r ⁻²ⁿ) = r ⁻ⁿ, h(r ^−(2n+1)) = r ⁻⁽ⁿ⁺²⁾ + r ^−(2n+1) and, consequently, r ⁻ⁿ ≥ h(r ⁻²ⁿ) > r ⁻⁽ⁿ⁺¹⁾ ≥ h(r ^−(2n+1)) > r ⁻⁽ⁿ⁺²⁾, if n ≥ 1.

On the other hand, $\frac {h(r^{-2n})}{r^{-2n}}= r^{n}> \frac {h(r^{-(2n+1)})}{r^{-(2n+1)}}=r^{(n-1)}+1$.

4.2 Computable Gauge Functions

The aim of this section is to show that the modulus function g and thus the dilution function φ can be chosen computable if the gauge function h fulfilling (14) is computable.

Lemma 8

Let $h:\mathbb {Q}\to \mathbb {R}$ be a computable gauge function satisfying the conditions 1 < h(1) < r and for every $n\in \mathbb {N}$ there is an $m\in \mathbb {N}$ such that r ⁻ⁿ < h(r ^−m) ≤ r ⁻ⁿ⁺¹ . Then there is a computable strictly increasing function $g:\mathbb {N}\to \mathbb {N}$ such that r ⁻ⁿ < h(r ^−g(n)) < r ⁻ⁿ⁺² .

Proof 10

We define g inductively. To this end we compute for every n ≥ 1 a closed interval I _n such that h(r ^−g(n)) ∈ I _n ⊂ (r ⁻⁽ⁿ⁻¹⁾,minI _n−1)

We start with g(0) := 0 and I ₋₁ = [r,r + 1] and estimate I ₀ as an sufficiently small approximating interval of h(r ^−g(0)) > 1 satisfying I ₀ ⊆ (1,r).

Assume now that for n the value g(n) and the interval I _n satisfying h(r ^−g(n)) ∈ I _n ⊂ (r ⁻ⁿ,minI _n−1) are computed.

We search for an m and an approximating interval I(m), h(r ^−m) ∈ I(m), such that I(m) ⊂ (r ⁻ⁿ⁻¹,minI _n ). Since $\liminf \limits _{m\to \infty }h(r^{-m})=0$ and ∃m(r ⁻ⁿ⁻¹ < h(r ^−m) ≤ r ⁻ⁿ) and r ⁻ⁿ < minI _n this search will eventually be successful. Define g(n + 1) as the first such m found by our procedure and set I _n+1 := I(m).

Finally, the monotonicity of h implies g(n + 1) > g(n). □

With Corollary 4 we obtain the following.

Corollary 5

Under the hypotheses of Lemma 8 there is a computable dilution function φ : X ^∗→ X ^∗ such that $r^{-2}\le \mathcal {H}^{h}(\overline {\varphi }(X^{\omega }))\le 1$ .

4.3 Complexity of Diluted Infinite Strings

In the final part of this section we show that, for a large class of computable gauge functions, sets like $\{\xi :\text {KA}(\xi \upharpoonright n)\leq _{\text {io}} -\log _{r} h(r^{-n})+c\}$ (see Corollary 3) have the function h as an exact dimension function, that is, a converse to Corollary 3.2.

We use the following estimate on the monotone complexity of a diluted string analogous to Theorem 3.1 of [35].

Theorem 9

Let φ : X ^∗→ X ^∗ be a one-to-one prefix-monotone computable function satisfying(13) with strictly increasing modulus function g. Then

$$\left|\text{Km}\left( \overline{\varphi}(\xi)[0..g(n)]\right)- \text{Km}\left( \xi\upharpoonright n \right)\right|\leq O(1)\text{ for all }\xi\in X^{\omega}\ . $$

Proof 11

The function φ has a prefix monotone computable partial inverse. Then the proof follows from Proposition 2. □

This auxiliary result yields that certain sets of non-complex strings have non-null h-dimensional Hausdorff measure.

Theorem 10

If $h: \mathbb {Q}\to \mathbb {R}$ is a computable gauge function satisfying(14) then there is a $c\in \mathbb {N}$ such that

$$\mathcal{H}^{h}(\{\zeta: \text{Km}(\zeta\upharpoonright n)\le_{\text{ae}} -\log_{r} h(r^{-n})+c\})>0. $$

Proof 12

From the gauge function h we construct a computable dilution function φ with modulus function g such that r ^{−(l + k)} < h(r ^−g(l)) < r ^{−(l + k−2)} for a suitable constant k (cf. Lemma 8 and Remark 1). Then, according to Corollary 5, $\mathcal {H}^{h}(\overline {\varphi }(X^{\omega }))>0$.

Using Theorem 9 we obtain $\text {Km}\left (\overline {\varphi }(\xi )\upharpoonright g(l)\right )\le \text {Km}\left (\xi \upharpoonright l \right )+c_{1}\le l+c_{2}$ for suitable constants $c_{1},c_{2}\in \mathbb {N}$ . Let $n\in \mathbb {N}$ satisfy g(l) < n ≤ g(n + 1). Then $\text {Km}\left (\overline {\varphi }(\xi )\upharpoonright n \right )\le \text {Km}\left (\overline {\varphi }(\xi )\upharpoonright g(l+1)\right )\le l+1+ c_{2}$.

Now from l + k − 1 < −log r h(r ^−g(l)) ≤−log r h(r ⁻ⁿ) we obtain the assertion $\text {Km}\left (\overline {\varphi }(\xi )\upharpoonright n \right )\le -\log _{r}h(r^{-n}) - k + c_{2}+ 2$. □

Now Corollary 3.2 and Theorem 6 prove the following analogue to Ryabko’s [28] result.

Lemma 9

If $h: \mathbb {Q}\to \mathbb {R}$ is a computable gauge function satisfying(14) then there is a $c\in \mathbb {N}$ such that h is an exact Hausdorff dimension for the sets $\{\xi :\text {KA}(\xi \upharpoonright n)\leq _{\text {io}} -\log _{r} h(r^{-n})+c\}$ and $\{\zeta : \text {Km}(\zeta \upharpoonright \ell )\le _{\text {ae}} -\log _{r} h(r^{-\ell })+c\}$ .

Despite the fact that there are ω-words on which KA and Km differ by more that an additive constant Lemma 9 seems to indicate that the set of those ω-words is not too big even in the sense of exact Hausdorff dimension.

5 Exact Dimensions for Σ₂-definable ω-languages

In this section we generalise the results of Section 1.4.3 to the case of exact dimension. The proofs follow closely the line of the corresponding proofs in [32]. It is remarkable that the upper complexity bound holds for prefix complexity.

5.1 Constructive Dimension

We start with an auxiliary lemma characterising subsets F ⊆ X ^ω having null measure via the δ-limit of languages V ^δ.

Lemma 10 (25)

Let F ⊆ X ^ω and h be a gauge function. Then $\mathcal {H}^{h}(F)=0$ if and only if there is a language V ⊆ X ^∗ such that F ⊆ V ^δ and ${\sum }_{v\in V}h(r^{-|v|})< \infty$ .

The following theorem gives a constructive version of Lemma 10.

Theorem 11

If F ⊆ X ^ω is a Σ₂ -definable ω -language and h,h(1) ≤ 1,is a right-computable gauge function such that $\mathcal {H}^{h}(F)=0$ then there are a computable non-decreasing function $\bar h:\{r^{-i}:i\in \mathbb {N}\}\to \mathbb {Q}$ and a computable language V ⊆ X ^∗ satisfying

• 1. $\bar h(r^{-n})\ge h(r^{-n})$ for all $n\in \mathbb {N}$ ,

• 2. F ⊆ V ^δ and ${\sum }_{v\in V}\bar h(r^{-|v|})<\infty$ .

Proof 13

Let $h_{n}:\{r^{-\ell }:\ell \in \mathbb {N}\}\to \mathbb {Q}\ ,n\in \mathbb {N},$ be computable approximations of h such that h _n (t) ≥ h _n+1(t) ≥ h(t) and $\lim _{n\to \infty }h_{n}(t)=h(t)$ for $t\in \{r^{-\ell }:\ell \in \mathbb {N}\}$. The functions h _n are assumed to be non-decreasing on the set $\{r^{-\ell }:\ell \in \mathbb {N}\}$. As h(t) ≥ t we have also h(r ⁻ⁿ) ≥ r ⁻ⁿ.

Furthermore, let $(U_{j})_{j\in \mathbb {N}}$ be an effective enumeration of all finite prefix codes over X such that sup{|v| : v ∈ U _j }≤ sup{|v| : v ∈ U _j+1}, and let F ∈Σ₂, as described in Section 1 of [32] be given by $F= \bigcup _{k\in \mathbb {N}} X^{\omega }\setminus L_{k}\cdot X^{\omega }$ where M _F := {(w,k) : w ∈ L _k } is a computable set and the family of languages $(L_{k})_{k\in \mathbb {N}}$ satisfies $L_{k}:= \bigcap _{i=0}^{k} L_{i}\cdot X^{*}$.

Define the predicate

$$\mathbf{test}(k,j,n) :\Leftrightarrow \left( \left( U_{j} \cup (L_{k}\cap X^{n})\right)\cdot X^{\omega} = X^{\omega}\ \wedge\ \sum\limits_{v\in U_{j}} h_{n}(r^{-|v|}) < r^{-k}\right)\ . $$

Observe that t e s t(k,j,n) is computable and if t e s t(k,j,n) is true then the conditions F ⊆ U _j ⋅ X ^ω and ∀v(v ∈ U _j → k < |v|) are satisfied.

The first condition follows from L _k ⋅ X ^ω ∩ F = ∅ and the second one from h _n (r ^−|v|) > r ^−|v|.

Now the following algorithm, when given M _F , computes a finite prefix code C _k and a value m _k satisfying the conditions F ⊆ C _k ⋅ X ^ω and ${\sum }_{v\in C_{k}} h_{m_{k}}(r^{-|v|}) < r^{-k}$:

By construction we have k < |v|≤ m _k for v ∈ C _k .

Informally, for every n ≥ 0 our algorithm successively searches for a U _j satisfying the condition t e s t(k,j,n), more precisely, it searches until such a U _j is found or else all U _j having sup{|v| : v ∈ U _j }≤ n fail to satisfy t e s t(k,j,n).

In the latter case the value of n is increased (thus allowing for a larger maximum codeword length, a larger complementary ω-language (L _k ∩ X ⁿ) ⋅ X ^ω and a closer approximation h _n+1 of the gauge function h) and the search starts anew. Consequently, the algorithm terminates if and only if there is a finite prefix code U such that ${\sum }_{v\in U} h_{n}(r^{-|v|})< r^{-k}$ and U ⋅ X ^ω ∪ (L _k ∩ X ⁿ) ⋅ X ^ω = X ^ω for some $n\in \mathbb {N}$.

First we show that our algorithm always terminates. Observe that for every ε > 0 there is a W ⊆ X ^∗ such that F ⊆ W ⋅ X ^ω and ${\sum }_{w\in W} h(r^{-|w|}) < \frac {\varepsilon }{2}$.

Since X ^ω ∖ L _k ⋅ X ^ω is a closed subset of F, for ε ≤ r ^−k we find a finite subset W ^′⊆ W such that X ^ω ∖ L _k ⋅ X ^ω ⊆ W ^′⋅ X ^ω. Then ${\sum }_{w\in W} h(r^{-|w|}) < \frac {\varepsilon }{2}$ implies that ${\sum }_{w\in W^{\prime }} h_{n}(r^{-|w|}) < \varepsilon$ for n ≥ n _ε,k , say.

Consequently, there is a finite prefix code U _j ⊆ W ^′ satisfying (U _j ∪ L _k ) ⋅ X ^ω = X ^ω and thus (U _j ∪ (L _k ∩ X ⁿ)) ⋅ X ^ω = X ^ω for $n\ge n^{\prime }_{j,k}$. This shows that the predicate t e s t(k,j,n) is satisfied whenever $n\ge \max \{n_{r^{-k},k},n^{\prime }_{j,k}\}$.

Now we define $V := \bigcup _{i\in \mathbb {N}} C_{i}$ and show that V meets the requirements of the theorem. We have w ∈ V if and only if ∃i(i < |w|∧ w ∈ C _i ). This predicate is computable, since i < |w| bounds the quantifier ∃i from above. Thus the language V is computable.

Next we show that F ⊆ V ^δ. If ξ ∈ F there is an i _ξ such that ξ ∈ X ^ω ∖ L _i ⋅ X ^ω for all i ≥ i _ξ . Hence, for every i ≥ i _ξ the ω-word ξ has a prefix w _i ∈ C _i . As it was observed above, |w _i | > i. Consequently, ξ has infinitely many prefixes in $V = \bigcup _{i\in \mathbb {N}} C_{i}$.

Finally, in order to define the function $\bar h$ we let ℓ _i := max{m _k : k < i}. Clearly, the value ℓ _i can be computed from i. Define $\bar h(r^{-i}):= h_{\ell _{i}}(r^{-i})$. Then $h_{m_{k}}(t)\ge h(t)$ implies $\bar h(r^{-i})\ge h(r^{-i})$ and ℓ _i ≤ ℓ _i+1 shows that $\bar h(r^{-i})\ge \bar h(r^{-(i+1)})$.

It remains to show that ${\sum }_{v\in V}\bar h(r^{-|v|})<\infty$. Taking into account that k < |v|≤ m _k , for v ∈ C _k , we have $\bar h(r^{-|v|})= h_{\ell _{|v|}}(r^{-|v|})\le h_{m_{k}}(r^{-|v|})$ for v ∈ C _k and thus

$$\begin{array}{@{}rcl@{}} {\sum}_{v\in V}\bar h(r^{-|v|}) &\le& {\sum}_{k\in \mathbb{N}}{\sum}_{v\in C_{k}}h_{m_{k}}(r^{-|v|})\\ &\le& {\sum}_{k\in \mathbb{N}} r^{-k}<\infty\ . \end{array} $$

□

Interpolating the computable function $\bar h$ we obtain the following consequence.

Corollary 6

If F ⊆ X ^ω is a Σ₂ -definable ω -language and h is a right-computable gauge function such that $\mathcal {H}^{h}(F)=0$ then there is a computable non-decreasing function $\bar h:\mathbb {Q}\to \mathbb {Q}$ satisfying $\mathcal {H}^{\bar h}(F)=0$ and $\bar h(t)\ge h(t)$ for $t\in \mathbb {Q}\cap (0,1)$ .

This result corresponds in some sense to a result by Besicovitch [27, Theorem 41] which states that for every E ⊆ X ^ω with $\mathcal {H}^{h}(E)=0$ there is a h ^″ such that $\mathcal {H}^{h^{\prime \prime }}(E)=0$ and $\liminf _{n\to \infty } \frac {h(r^{-n})}{h^{\prime \prime }(r^{-n})}=0$.

Our Theorem 11 yields the required upper bound for the prefix complexity H, and hence also for the monotone and a priori complexities Km and KA, of an ω-word in F.

If V ⊆ X ^∗ is computably enumerable and $\bar h: \{r^{-n}>n\in \mathbb {N}\}\to \mathbb R$ is a left-computable function such that ${\sum }_{v\in V}\bar h(r^{-|v|})<\infty$ then

$$ \nu(w):= \left\{ \begin{array}{ll} \bar h(r^{-|w|}),&\text{ if } w\in V\text{ , and}\\ 0,&\text{ otherwise} \end{array}\right. $$

(15)

defines a left-computable discrete semi-measure. Thus Theorem 11 implies the following upper bound on the complexity functions of ω-words.

Lemma 11

If F ⊆ X ^ω is a Σ₂ -definable ω -language and h is a right-computable gauge function such that $\mathcal {H}^{h}(F)=0$ then

$$\mathrm{H}(\xi\upharpoonright n)\le_{\mathrm{i.o.}} {-}{\log_{r}} h(r^{-n})+ O(1) \text{ for all } \xi\in F. $$

Proof 14

We use the computable subset V ⊆ X ^∗ and the computable function $\bar h$ defined in the proof of Theorem 11 and define the discrete semi-measure ν via (15). Then ν(w) ≤ c ⋅m(w), for all w ∈ X ^∗ and, consequently $\mathrm {H}(w)\le {-}{\log _{r}}\bar h(r^{-|w|})\le {-}{\log _{r}}h(r^{-|w|})$, for w ∈ V. The assertion follows from F ⊆ V ^δ. □

Finally, Lemma 11 and Corollary 3 prove the following.

Theorem 12

If F ⊆ X ^ω is a union of Σ₂ -definable sets and h is a right-computable gauge function such that $\mathcal {H}^{h}(F)=0$ then $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {U}]$ for every gauge function h ^′ such that $\lim _{t\to 0}\frac {h^{\prime }(t)}{h(t)}=0$ .

5.2 Computable Dimension

Computable dimension is based on computable super-martingales as constructive dimension was based on left-computable super-martingales. In contrast to the latter, for the former there is no universal computable super-martingale (cf. [6, 30]). Thus we define analogously to Theorem 4

Definition 3

We refer to a gauge function h as an exact computable dimension function for F ⊆ X ^ω provided

• 1. for all gauge functions h ^′ with $\lim \limits _{n\to \infty } \frac {h^{\prime }(r^{-n})}{h(r^{-n})}=0$ there is a computable super-martingale $\mathcal {V}$ such that $F\subseteq S_{\infty ,h^{\prime }}[\mathcal {V}]$, and

• 2. for all gauge functions h ^″ with $\lim \limits _{n\to \infty } \frac {h(r^{-n})}{h^{\prime \prime }(r^{-n})}=0$ and all computable super-martingales $\mathcal {V}$ it holds $F\not \subseteq S_{\infty ,h^{\prime \prime }}[\mathcal {V}]$.

As for the constructive case the second item is fulfilled provided $\mathcal {H}^{h}(F)>0$. For Item 1 we prove that for computable gauge functions h and ${{\Sigma }_{2}^{0}}$-definable sets F ⊆ X ^ω with $\mathcal {H}^{h}(F)=0$ there is a computable martingale $\mathcal {V}$ such that $F\subseteq \bigcup _{c>0}S_{c,h}[\mathcal {V}]$.

In order to achieve our goal we introduce families of covering codes as in [32]. For a prefix code C ⊆ X ^∗ we define its minimal complementary code as

$$\widehat{C} := (X \cup \mathbf{pref} (C) \cdot X)\setminus\mathbf{pref} (C)\ . $$

If C = ∅ we have ${\widehat {C}} =X$, and if C≠∅ the set ${\widehat {C}}$ consists of all words w ⋅ x∉p r e f(C) where w ∈p r e f(C) and x ∈ X. It is readily seen that $C\cup {\widehat {C}}$ is a maximal prefix code, $C\cap {\widehat {C}}=\emptyset$, and $\mathbf {pref}({C\cup {\widehat {C}}})=\{e\}\cup \mathbf {pref} (C)\cup {\widehat {C}}$.

We call ${\mathfrak C} := (C_{w})_{w\in X^{*}}$ a family of covering codes provided each C _w is a finite prefix code. Since then the set $C_{w}\cup {\widehat {C}}_{w}$ is a finite maximal prefix code, every word u ∈ X ^∗ has a uniquely specified ${\mathfrak C}$-factorisation u = u ₁⋯u _n ⋅ u ^′ where $u_{i+1}\in C_{u_{1}{\cdots } u_{i}}\cup {\widehat {C}}_{u_{1}{\cdots } u_{i}}$ for i = 0,…,n − 1 (u ₁⋯u _i = e, if i = 0) and $u^{\prime }\in \mathbf {pref}({C_{u_1{\cdots } u_n}\cup {\widehat {C}}_{u_1{\cdots } u_n}}$). Analogously, every ξ ∈ X ^ω has a uniquely specified ${{\mathfrak C} }$-factorisation ξ = u ₁⋯u _i ⋯ where $u_{i+1}\in C_{u_{1}{\cdots } u_{i}}\cup {\widehat {C}}_{u_{1}{\cdots } u_{i}}$ for i = 1,… .

In what follows we use martingales derived from prefix codes in the following manner.

Lemma 12

Let $h:\mathbb {R}\to \mathbb {R}$ a gauge function and ∅≠C ⊆ X ^∗ be a prefix code satisfying ${\sum }_{v\in C}h(r^{-|v|}) <\infty$ . Then there is a martingale ${\mathcal V}_{C}^{(h)} : X^{*} \to [0,\infty )$ such that

$$ {\mathcal V}_{C}^{(h)} (w) = \left\{{\begin{array}{l@{\quad,\ }l} {\displaystyle \frac{r^{{|w|}}\cdot h(r^{(-|w|)}}{{\sum}_{v\in C}h(r^{(-|v|})+{\sum}_{u\in{\widehat{C}}}r^{-|u|}} }&\text{for }w\in C\,\text{, and}\\ {\displaystyle \frac{1}{{\sum}_{v\in C}h(r^{(-|v|})+{\sum}_{u\in{\widehat{C}}}r^{-|u|}}} &\text{for }w\in {\widehat{C}}\,. \end{array}}\right. $$

(16)

Proof 15

Set ${\Gamma }:= {{\sum }_{v\in C}h(r^{-|v|})+{\sum }_{u\in {\widehat {C}}}r^{-|u|}}$, and define for $u\in \mathbf {pref}({C)\cup {\widehat {C}}}$ and $w\in C\cup {\widehat {C}}\ , v\in X^{*}$

$${\begin{array}{rcl} {\mathcal V}_{C}^{(h)} (u) &:=& {\displaystyle\frac{r^{|u|}}{\Gamma}}\cdot \left( \sum\limits_{u\cdot w\in C} h(r^{-|u\cdot w|}) + \sum\limits_{u\cdot w\in {\widehat{C}}} r^{-|u\cdot w|}\right)\\ {\mathcal V}_{C}^{(h)} (w\cdot v) &:=& {\mathcal V}_{C}^{(h)}(w)\ . \end{array} } $$

Then ${\mathcal V}_{C}^{(h)}$ fulfils (16). We still have to show the property ${\mathcal V}_{C}^{(h)}(u) = \frac {1}{r}{\sum }_{x\in X}{\mathcal V}_{C}^{(h)}(ux)$. This identity is obvious if $u \in (C\cup \widehat {C})\cdot X^{*}$.

Now, let $u\notin (C\cup \widehat {C})\cdot X^{*}$, that is, $u \in \mathbf {pref}({C\cup \widehat {C}})\setminus (C\cup \widehat {C})$. Then

$$\begin{array}{@{}rcl@{}} \sum\limits_{x\in X}\frac{{\mathcal V}_{C}^{(h)}(ux)}{r}& = & \sum\limits_{x\in X}\frac{r^{|ux|}}{r\cdot{\Gamma}}\cdot\left( \sum\limits_{uxw\in C} h(r^{-|uxw|})+\sum\limits_{uxw\in {\widehat{C}}} r^{-|uxw|}\right) \\ & = & \frac{r^{|u|}}{\Gamma}\cdot \sum\limits_{x\in X}\left( \sum\limits_{uxw\in C}h(r^{-|uxw|}) + \sum\limits_{uxw\in {\widehat{C}}} r^{-|uxw| }\right)\ , \end{array} $$

because for $u\in \mathbf {pref}({C\cup {\widehat {C}}}) \setminus (C\cup {\widehat {C}})$ the set $\{w:w\in C\cup {\widehat {C}}\land u \sqsubseteq w\}$ partitions into the sets $\{w:w\in C\cup {\widehat {C}}\land ux \sqsubseteq w\}\ (x\in X)$, and the required equation follows. □

Remark 2

If C is a finite prefix code and $h:\mathbb {Q}\to \mathbb {Q}$ is computable then ${\mathcal V}_{C}^{(h)}$ is a computable martingale.

For a gauge function $h:\mathbb {R}\rightarrow \mathbb {R}$ let $h_{w}(t):= \frac {h(r^{-|w|}\cdot t)}{h(r^{-|w|})}$ and let ${\mathfrak C}:= (C_{w})_{w\in X^{*}}$ be a family of covering codes.

Using the martingales ${\mathcal V}_{C_{w}}^{(h_{w})}$ we define a new martingale ${\mathcal V}_{\mathfrak C}$ as follows:

For u ∈ X ^∗ consider the ${\mathfrak C}$-factorisation u ₁⋯u _n ⋅ u ^′, and put

$${\mathcal V}^{(h)}_{\mathfrak C}(u):= \left( {\prod}_{i=0}^{n-1}{\mathcal V}_{C_{u_{1}{\cdots} u_{i}}}^{(h_{u_{1}{\cdots} u_{i}})}(u_{i+1})\right)\cdot{\mathcal V}_{C_{u_{1}{\cdots} u_{n}}}^{(h_{u_{1}{\cdots} u_{n}})}(u^{\prime})\ , $$

that is, ${\mathcal V}^{(h)}_{\mathfrak C}$ is in some sense the concatenation of the martingales ${\mathcal V}^{(h_{w})}_{C_{w}}$. Observe that ${\mathcal V}^{(h)}_{\mathfrak C}$ is computable if only $h:\mathbb {R}\to \mathbb {R}$ is a computable function, the codes C _w are finite and the function which assigns to every w the corresponding code C _w is computable.

We have the following.

Lemma 13

Let $h:\mathbb {N}\rightarrow \mathbb {Q}$ be a gauge function and let ${{\mathfrak C} }= (C_{w})_{w\in X^{*}}$ be a family of covering codes such that ${\sum }_{v\in C_{w}} \frac {h(r^{-|wv|})}{h(r^{-|v|})}\le r^{-|w|}$ for all w ∈ X ^∗ .

If the ω -word ξ ∈ X ^ω has a $\mathfrak C$ -factorisation ξ = u ₁⋯u _i ⋯such that for some $n_{\xi }\in \mathbb {N}$ and all i ≥ n _ξ the factors u _i+1 belong to $C_{u_{1}{\cdots } u_{i}}$ . Then there is a constant c _ξ > 0not depending on i for which

$${\mathcal V}_{{\mathfrak C} }(u_{1}{\cdots} u_{i})\geq c_{\xi}\cdot r^{|u_{1}{\cdots} u_{i}|}\cdot h(r^{-|u_{1}{\cdots} u_{i}|})\ . $$

Proof 16

Since ${\widehat {C}}_{w}$ is a code, we have ${\sum }_{v\in {\widehat {C}}_{w}} r^{-|v|}\leq 1$, and from the assumption and the definition of the function h _w we obtain

$${\sum}_{v\in C_{w}} h_{w}(r^{-|v|}) + {\sum}_{v\in {\widehat{C}}_{w}} r^{-|v|}\leq r^{-|w|}+1\ . $$

Now |u _j |≥ 1 implies |u ₁⋯u _i |≥ i, and the above (16) yields for w = u ₁⋯u _i

$$ {\mathcal V}_{C_{u_{1}{\cdots} u_{i}}}^{(h_{w})}(u_{i+1})\geq\left\{\begin{array}{l@{\ ,\ }l} \displaystyle\frac{1}{r^{-i}+1}= \frac{r^{i}}{1+r^{i}}& \text{ if }i\leq n_{\xi}\text{ , \ and}\\ \displaystyle\frac{r^{|u_{i+1}|}\cdot h_{w}(r^{-|u_{i+1}|})}{r^{-i}+1}& \text{ if } i> n_{\xi}\ . \end{array}\right. $$

(17)

Put

$$c_{\xi} := {\prod}_{i=0}^{\infty} \frac{r^{i}}{1+r^{i}}\cdot {\prod}_{i=0}^{n_{\xi}} r^{|u_{i+1}|}\cdot h_{w}(r^{-|u_{i+1}|})= r^{|u_{1}{\cdots} u_{n_{\xi}}|}\cdot h(r^{-|u_{1}{\cdots} u_{n_{\xi}}|})\cdot{\prod}_{i=0}^{\infty} \frac{r^{i}}{1+r^{i}}\ . $$

Clearly, c _ξ > 0, and using (17) by induction on i the assertion is easily verified. □

Now we derive the announced result.

Theorem 13

For every Σ₂ -definable ω -language F ⊆ X ^ω and every right-computable gauge function $h:\mathbb {Q}\to \mathbb {R}$ such that $\mathcal {H}^{h}(F)=0$ there is a computable martingale ${\mathcal V}$ such that $F\subseteq \bigcup _{c>0}S_{c,h}[\mathcal {V}]$ .

Proof 17

In view of Corollary 6 it suffices to prove the theorem for computable functions $h:\mathbb {Q}\to \mathbb {R}$.

We use computable approximations $h_{n}:\mathbb {Q}\to \mathbb {Q}$ of h such that h _n (t) ≤ h _n+1(t) and h _n (t) ≤ h(t) ≤ (1 + r ⁻ⁿ) ⋅ h _n (t) for $t\in (0,1)\cap \mathbb {Q}$.

By virtue of Lemma 13 it suffices to construct a computable family of covering codes $\mathfrak {C} = (C_{w})_{w \in X^{*}}$ such that the function which assigns to every w the corresponding finite prefix code C _w is computable.

To this end we modify the predicate t e s t introduced in the proof of Theorem 11 as follows:

$$\begin{array}{@{}rcl@{}} \mathbf{test^{\prime}}(w,j,n) &:\Leftrightarrow& \left( n\ge|w|\wedge \left( w \cdot U_{j}\cup (L_{|w|}\cap X^{|w|+n})\right)\cdot X^{\omega} \supseteq w \cdot X^{\omega}\right.\\ && \left.\wedge \sum\limits_{v\in U_{j}} \frac{(1+r^{-n})\cdot h_{n}(r^{-|wv|})}{h_{n}(r^{-|w|})}< r^{-|w|}\right)\ . \end{array} $$

In the same way we modify the algorithm presented there.

Similar to the proof of Theorem 11 this algorithm computes a prefix code C _w with ${\sum }_{v\in C_{w}} \frac {h(r^{-|wv|})}{h(r^{-|w|})} < r^{-|w|}$ and w ⋅ C _w ⋅ X ^ω ⊇ w ⋅ X ^ω ∖ L _|w|⋅ X ^ω.

Next we show that under the hypotheses of the theorem the algorithm always terminates. We have $\mathcal {H}^{h}(F\cap w\cdot X^{\omega })=0$ for all w ∈ X ^∗. Thus for w ∈ X ^∗ and every ε > 0 there is a prefix-free language W ⊆ X ^∗ such that F ∩ w ⋅ X ^ω ⊆ W ⋅ X ^ω and ${\sum }_{v\in W}h(r^{-|v|})< r^{-|w|}\cdot \frac {h_{0}(r^{-|w|})}{1+ r}$. As in the proof of Theorem 11, in view of F ⊇ X ^ω ∖ L _|w|⋅ X ^ω, there is a finite subset W ^′⊆ W ∩ w ⋅ X ^∗ such that w ⋅ X ^ω ∖ L _|w|⋅ X ^ω ⊆ W ^′⋅ X ^ω. Consequently, if w ⋅ U _j ⋅ X ^ω ⊇ W ^′⋅ X ^ω and n is large enough the condition t e s t ^′(w,j,n) will be satisfied.

It remains to show that every ξ ∈ F has a ${\mathfrak C}$-factorisation ξ = u ₁⋯u _i ⋯ such that almost all factors u _i+1 belong to the corresponding codes $C_{u_{1}{\cdots } u_{i}}$.

Let ξ ∈ F. Then there is a $k \in \mathbb {N}$ such that ξ ∈ X ^ω ∖ L _i ⋅ X ^ω for all i ≥ k. Consequently, w ∈p r e f(ξ) implies w∉L _k = L _k ⋅ X ^∗, and according to the definition of ${\mathfrak C}$ there is a u ∈ C _w such that w ⋅ u ∈p r e f(ξ) whenever |w|≥ k. □

6 Functions of the Logarithmic Scale

As we have seen in Section 1.3 the set of gauge functions is not ordered which makes it difficult to assign a Hausdorff dimension to that set. On the other hand, the scale of the “classical” Hausdorff dimension is sometimes to coarse to distinguish sets.

In this part we consider a generalisation of the “usual” dimension which is finer than the “classical” Hausdorff dimension but is linearly ordered.

Another linear ordering of a family of functions larger than the exponential ones h _α (t) = t ^α is the scaling defined in [14, 15] mentioned in the Introduction. Here $h_{\alpha }(t)= r^{-g(-\log _{r}t,\alpha )}$ where the scale $g:\mathbb {R}\times \mathbb {R}_{+}\to \mathbb {R}$ is suitably defined (see [15, Section 3]). This yields a variety of scaled dimensions (depending on the scale g) which gave new insights into dimensions of complexity classes.

Here we consider the family of functions of the logarithmic scale which is also considered in Hausdorff’s original paper [12]. This family is, similarly to the family h _α (t) = t ^α, also linearly ordered and, thus, allows for more specific versions of Corollary 3.2 and Theorem 6.

A function of the form where the first non-zero exponent satisfies p _i > 0

$$ \textstyle h_{(p_{0},\dots,p_{k})}(t) = t^{p_{0}}\cdot {\prod}_{i=1}^{k}\left( \frac{1}{{\log_{r}^{i}}{\frac{1}{t}}}\right)^{p_{i}} $$

(18)

is referred to as a function of the logarithmic scale. Here we have the convention that ${\log _{r}^{i}}\frac {1}{t} = \max \{\underbrace {\log _{r} {\dots } \log _{r}}_{i\ \text {times}}\,\frac {1}{t}\ ,1\}$, that is, ${\log _{r}^{i}}\frac {1}{t}= \underbrace {\log _{r} {\dots } \log _{r}}_{i\ \text {times}}\,\frac {1}{t}$ if t is sufficiently small.

One observes that the lexicographic order on the tuples (p ₀,…,p _k ) yields an order of the functions $h_{(p_{0},\dots ,p_{k})}$ in the sense that (p ₀,…,p _k ) > _lex(q ₀,…,q _k ) if and only if $h_{(q_{0},\dots ,q_{k})}(t)\prec h_{(p_{0},\dots ,p_{k})}(t)$.

This gives rise to a generalisation of the “usual” Hausdorff dimension as follows.

$$ \begin{array}{rrl}\textstyle \dim^{(k)}_{\mathrm H} F &:=& \sup \{(p_{0},\dots,p_{k}): {\mathcal H}^{h_{(p_{0},\dots,p_{k})}}(F)=\infty\}\\&=&\inf \{(p_{0},\dots,p_{k}): {\mathcal H}^{h_{(p_{0},\dots,p_{k})}}(F)=0\} \end{array} $$

(19)

When taking supremum or infimum we admit also values −∞ and ∞ for the last parameter p _k although we did not define the corresponding functions of the logarithmic scale. E.g. $\dim ^{(1)}_{\mathrm {H}} F= (0,\infty )$ means that $\mathcal {H}^{h_{(0,\gamma )}}(F)=\infty$ but $\mathcal {H}^{h_{(\alpha ,-\gamma )}}(F)=0$ for all γ ∈ (0,∞) and all α > 0.

The following theorems generalise Theorem 2 of the set of strings having asymptotic Kolmogorov complexity $\underline {\kappa }(\xi )\le p_{0}$.

Let $h_{(p_{0},\dots ,p_{k})}$ be a function of the logarithmic scale. We define its first logarithmic truncation as $\beta _{h}(t):= -\log _{r}h_{(p_{0},\dots ,p_{k-1})}$. Observe that $\beta _{h}(r^{-n})= p_{0}\cdot n + \sum \nolimits _{i=1}^{k-1}p_{i}\cdot {\log _{r}^{i}} n$ and $-\log _{r} h_{(p_{0},\dots ,p_{k})}(r^{-n})= \beta _{h}(r^{-n}) + p_{k}\cdot {\log _{r}^{k}} n$ , for sufficiently large $n\in \mathbb {N}$.

Then from Corollary 3.2 we obtain the following result.

Theorem 14 (24)

Let k > 0, (p ₀,…,p _k )be a (k + 1)-tuple and $h_{(p_{0},\dots ,p_{k})}$ be a function of the logarithmic scale. Then

$$\dim^{(k)}_{\mathrm H} \left\{\xi: \xi\in X^{\omega}\wedge \liminf_{n\to\infty}\frac{\text{KA}(\xi\upharpoonright n)-\beta_{h}(2^{-n})}{{\log_{r}^{k}} n}< p_{k}\right\}\leq (p_{0},\dots,p_{k})\,. $$

Proof 18

From $\liminf _{n\to \infty }\frac {\text {KA}(\xi \upharpoonright n)-\beta _{h}(2^{-n})}{{\log _{r}^{k}} n}< p_{k}$ follows $\text {KA}(\xi \upharpoonright n)\le \beta _{h}(2^{-n}) +p^{\prime }_{k}\cdot {\log _{r}^{k}} n+O(1)$ for some $p^{\prime }_{k}<p_{k}$. Thus $h_{(p_{0},\dots ,p^{\prime }_{k})}\prec h_{(p_{0},\dots ,p_{k})}$ and the assertion follows from Corollary 3.2. □

Using Theorem 6 we obtain a partial converse to Theorem 14 slightly refining Satz 4.11 of [24].

Theorem 15

Let k > 0, (p ₀,…,p _k )be a (k + 1)-tuple where p ₀ > 0and p ₀,…,p _k−1 are computable numbers. Then for the function $h_{(p_{0},\dots ,p_{k})}$ it holds

$$\dim^{(k)}_{\mathrm H} \left\{\xi: \xi\in X^{\omega}\wedge \limsup_{n\to\infty}\frac{\text{KA}(\xi\upharpoonright n)-\beta_{h}(2^{-n})}{{\log_{r}^{k}} n}\le p_{k}\right\}= (p_{0},\dots,p_{k})\,. $$

Proof 19

Let $p^{\prime }_{k}<p_{k}$ be a computable number. Then $h_{(p_{0},\dots ,p^{\prime }_{k})}$ is a computable gauge function, $h_{(p_{0},\dots ,p^{\prime }_{k})}\prec h_{(p_{0},\dots ,p_{k})}$ and $\mathcal {H}^{h}(\{\xi :\text {KA}(\xi \upharpoonright n)\le -\log _{r}h(r^{-n})+c_{h}\})>0$ for $h=h_{(p_{0},\dots ,p^{\prime }_{k})}$ and some constant c _h . Moreover the relation $\text {KA}(\xi \upharpoonright n)\le -\log _{r}h(r^{-n})+c_{h}$ implies $\limsup \limits _{n\to \infty } \frac {\text {KA}(\xi \upharpoonright n)-\beta _{h}(2^{-n})}{{\log _{r}^{k}} n}\le p_{k}$.

Thus $\dim ^{(k)}_{\mathrm H} \left \{\xi : \xi \in X^{\omega }\wedge \limsup \limits _{n\to \infty } \frac {\text {KA}(\xi \upharpoonright n)-\beta _{h}(2^{-n})}{{\log _{r}^{k}} n}\le p_{k}\right \}\ge (p_{0},\dots ,p^{\prime }_{k})$.

As $p^{\prime }_{k}$ can be made arbitrarily close to p _k the assertion follows. □

It would be desirable to prove Theorem 6 for arbitrary gauge functions or Theorem 15 for arbitrary (k + 1)-tuples. One obstacle is that, in contrast to the case of real number dimension where the computable numbers are dense in the reals, already the computable pairs (p ₀,p ₁) are not dense in the above mentioned lexicographical order of pairs. This can be verified by the following fact.

Remark 3

Let p ₀ ∈ (0,1). If $r^{-p_{0}\cdot n}\le h(r^{-n})\le n\cdot r^{-p_{0}\cdot n}$ for a computable function $h:\mathbb {Q}\to \mathbb {R}$ and sufficiently large $n\in \mathbb {N}$. Then p ₀ is a computable real. Thus, if p ₀ is not a computable number, the interval between $h_{(p_{0},0)}$ and $h_{(p_{0},1)}$ does not contain a computable gauge function.