Dimension spectra of lines 1

Abstract

This paper investigates the algorithmic dimension spectra of lines in the Euclidean plane. Given any line L with slope a and vertical intercept b, the dimension spectrum $sp (L)$ is the set of all effective Hausdorff dimensions of individual points on L. We draw on Kolmogorov complexity and geometrical arguments to show that if the effective Hausdorff dimension $dim (a, b)$ is equal to the effective packing dimension $Dim (a, b)$ , then $sp (L)$ contains a unit interval. We also show that, if the dimension $dim (a, b)$ is at least one, then $sp (L)$ is infinite. Together with previous work, this implies that the dimension spectrum of any line is infinite.

Keywords

Effective dimension Kolmogorov complexity

1. Introduction

Algorithmic dimensions refine notions of algorithmic randomness to quantify the density of algorithmic information of individual points in continuous spaces. The most well-studied algorithmic dimensions for a point $x \in R^{n}$ are the effective Hausdorff dimension, $dim (x)$ , and its dual, the effective packing dimension, $Dim (x)$ [2,22]. These dimensions are both algorithmically and geometrically meaningful [10]. In particular, the quantities ${sup}_{x \in E} dim (x)$ and ${sup}_{x \in E} Dim (x)$ are closely related to classical Hausdorff and packing dimensions of a set $E \subseteq R^{n}$ [16,25], and this relationship has been used to prove nontrivial results in classical fractal geometry using algorithmic information theory [25,28,36].

Given the pointwise nature of effective Hausdorff dimension, it is natural to investigate not only the supremum ${sup}_{x \in E} dim (x)$ but the entire (effective Hausdorff) dimension spectrum of a set $E \subseteq R^{n}$ , i.e., the set $\begin{matrix} sp (E) = {dim (x) : x \in E} . \end{matrix}$ The dimension spectra of several classes of sets have been previously investigated. Gu et al. studied the dimension spectra of randomly selected subfractals of self-similar fractals [15]. Dougherty et al. focused on the dimension spectra of random translations of Cantor sets [9]. In the context of symbolic dynamics, Westrick has studied the dimension spectra of subshifts [42].

This work concerns the dimension spectra of lines in the Euclidean plane $R^{2}$ . Given a line $L_{a, b}$ with slope a and vertical intercept b, we ask what $sp (L_{a, b})$ might be. It was shown by Turetsky that, for every $n ⩾ 2$ , the set of all points in $R^{n}$ with effective Hausdorff 1 is connected, guaranteeing that $1 \in sp (L_{a, b})$ . In recent work [28], we showed that the dimension spectrum of a line in $R^{2}$ cannot be a singleton. By proving a general lower bound on $dim (x, a x + b) = dim ((x, a x + b))$ , which is presented as Theorem 8 here, we demonstrated that $\begin{matrix} min {1, dim (a, b)} + 1 \in sp (L_{a, b}) . \end{matrix}$ Together with the fact that $dim (a, b) = dim (a, a^{2} + b) \in sp (L_{a, b})$ and Turetsky’s result, this implies that the dimension spectrum of $L_{a, b}$ contains both endpoints of the interval $[min {1, dim (a, b)}, min {1, dim (a, b)} + 1]$ .

Here we build on that work with two main theorems on the dimension spectrum of a line. Our first theorem gives conditions under which that entire interval must be contained in the spectrum. We refine the techniques of [28] to show in our first main theorem (Theorem 15) that, whenever $dim (a, b) = Dim (a, b)$ , we have $\begin{matrix} [min {1, dim (a, b)}, min {1, dim (a, b)} + 1] \subseteq sp (L_{a, b}) . \end{matrix}$ Given any value $s \in [0, 1]$ , we construct, by padding a random binary sequence, a value $x \in R$ such that $\begin{matrix} dim (x, a x + b) = s + min {dim (a, b), 1} . \end{matrix}$ Our second main theorem states that the dimension spectrum $sp (L_{a, b})$ is infinite whenever $dim (a, b) ⩾ 1$ . Together with Theorem 8, this implies that all lines in $R^{n}$ have infinite dimension spectra.

We begin by reviewing definitions and properties of algorithmic information in Euclidean spaces in Section 2. In Section 3, we sketch our technical approach and prove our main technical lemmas. In Section 4 we prove our main theorems. We conclude in Section 5 with a brief discussion of future directions.

2. Preliminaries

2.1. Kolmogorov complexity in discrete domains

The conditional Kolmogorov complexity of binary string $σ \in {0, 1}^{*}$ given a binary string $τ \in {0, 1}^{*}$ is the length of the shortest program π that will, when concatenated with τ, output σ. Formally, it is $\begin{matrix} K (σ ∣ τ) = min_{π \in {0, 1}^{*}} {ℓ (π) : U (π, τ) = σ}, \end{matrix}$ where $ℓ (π)$ is the length of π and U is a fixed universal Turing machine that is prefix-free in its first input. Any π that achieves this minimum is said to testify to, or be a witness to, the value $K (σ ∣ τ)$ . The Kolmogorov complexity of a binary string σ is $K (σ) = K (σ ∣ λ)$ , where λ is the empty string. These definitions extend naturally to other finite data objects, e.g., vectors in $Q^{n}$ , via standard binary encodings; see [21] for details.

2.2. Kolmogorov complexity in Euclidean spaces

The above definitions can also be extended to Euclidean spaces, as we now describe. The Kolmogorov complexity of a point $x \in R^{m}$ at precision $r \in N$ is the length of the shortest program π that outputs a precision-r estimate for x, i.e., some rational point in a ball of radius $2^{- r}$ about x. Formally, it is $\begin{matrix} K_{r} (x) = min {K (p) : p \in B_{2^{- r}} (x) \cap Q^{m}}, \end{matrix}$ where $B_{ε} (x)$ denotes the open ball of radius ε about x. The conditional Kolmogorov complexity of x at precision $r \in N$ given $y \in R^{n}$ at precision $s \in N$ is $\begin{matrix} K_{r, s} (x ∣ y) = max {min {K_{r} (p ∣ q) : p \in B_{2^{- r}} (x) \cap Q^{m}} : q \in B_{2^{- s}} (y) \cap Q^{n}} . \end{matrix}$ That is, the length of the shortest program that outputs a precision-r estimate p for x when given the “least helpful” precision-s estimate q for y. This maximization step is necessary to ensure that q is not “cheating” by encoding extra information about x.2

²
Some readers may find it intuitively useful to consider these quantities in terms of truncated binary expansions. For any point $x = (x_{1}, \dots, x_{n}) \in R^{n}$ and precision $r \in N$ , let $x ↾ r$ denote the concatenation $x_{1} ↾ r \dots x_{n} ↾ r$ , where $x_{i} ↾ r$ is the binary expansion of $x_{i}$ , truncated r bits to the right of the binary point. It is straightforward to show, for example, that the difference between $K_{r, s} (x ∣ y)$ and $K (x ↾ r ∣ y ↾ s)$ is $O (log r s)$ , which is small enough to be irrelevant for our purposes. See [28] for a full, quantitative accounting of these relationships.

When the precisions r and s are equal, we abbreviate

K_{r, r} (x ∣ y)

K_{r} (x ∣ y)

As the following two lemmas show, these quantities have some convenient properties: They are only linearly sensitive to their precision parameters, and they obey chain rules.

Lemma 1 ([3 ,25]).

Let $x \in R^{m}$ and $y \in R^{n}$ . For all $r, Δ r, s, Δ s \in N$ ,

$K_{r + Δ r} (x) = K_{r} (x) + O (Δ r + log (r + Δ r))$ .

$K_{r + Δ r, s} (x ∣ y) = K_{r, s + Δ s} (x ∣ y) + O (Δ r + Δ s + log (r + Δ r) + log (s + Δ s))$ .

Lemma 1 is an essential tool for the kind of geometric arguments we make in this paper because it lets us accommodate small changes in precision parameters, e.g., when combining two estimates or switching between $ℓ_{1}$ and $ℓ_{2}$ norms. It is most frequently used when $Δ r$ and $Δ s$ are constants, in which case the two statements can be rewritten more simply as $K_{r + Δ r} (x) = K_{r} (x) + O (log r)$ and $K_{r + Δ r, s} (x ∣ y) = K_{r, s + Δ s} (x ∣ y) + O (log r s)$ .

Lemma 2 ([25,28]).

Let $x \in R^{m}$ and $y \in R^{n}$ . For all $r, s \in N$ with $r ⩾ s$ ,

$K_{r} (x, y) = K_{r} (x ∣ y) + K_{r} (y) + O (log r)$ .

$K_{r} (x) = K_{r, s} (x ∣ x) + K_{s} (x) + O (log r)$ .

The first statement of Lemma 2 allows us to decompose the algorithmic information about a point $(x, y) \in R^{m + n}$ coordinate-wise, isolating the information about the final n coordinates in an estimate for $(x, y)$ . The second statement allow us to decompose the algorithmic information about a point $x \in R^{m}$ by precision; given an estimate for x, it isolates the information necessary to obtain a less-precise estimate for x.

2.3. Effective Hausdorff and packing dimensions

J. Lutz initiated the study of algorithmic dimensions by effectivizing Hausdorff dimension using betting strategies called gales, which generalize martingales. Subsequently, Athreya et al. defined effective packing dimension, also using gales [2]. Mayordomo showed that effective Hausdorff dimension can be characterized using Kolmogorov complexity [30], and Mayordomo and J. Lutz showed that effective packing dimension can also be characterized in this way [26]. In this paper, we use these characterizations as definitions. The effective Hausdorff dimension and effective packing dimension of a point $x \in R^{n}$ are $\begin{matrix} dim (x) = \underset{r \to \infty}{lim inf} \frac{K_{r} (x)}{r} and Dim (x) = \underset{r \to \infty}{lim sup} \frac{K_{r} (x)}{r} . \end{matrix}$ Intuitively, these dimensions measure the density of algorithmic information in the point x. Guided by the information-theoretic nature of these characterizations, Lutz and Lutz [25] defined the lower and upper conditional dimension of $x \in R^{m}$ given $y \in R^{n}$ as $\begin{matrix} dim (x ∣ y) = \underset{r \to \infty}{lim inf} \frac{K_{r} (x ∣ y)}{r} and Dim (x ∣ y) = \underset{r \to \infty}{lim sup} \frac{K_{r} (x ∣ y)}{r} \end{matrix}$ and showed that these quantities obey a chain rule: For all $x, y \in R^{n}$ , $\begin{matrix} (1) & dim (x ∣ y) + dim (y) ⩽ dim (x, y) ⩽ Dim (x ∣ y) + dim (y) ⩽ Dim (x, y) ⩽ Dim (x ∣ y) + Dim (y) . \end{matrix}$

2.4. Relative complexity and dimensions

By letting the underlying Turing machine U be a universal oracle machine, we may relativize the definitions in this section to an arbitrary oracle set $A \subseteq N$ . The definitions of $K^{A} (σ ∣ τ)$ , $K^{A} (σ)$ , $K_{r}^{A} (x)$ , $K_{r}^{A} (x ∣ y)$ , ${dim}^{A} (x)$ , ${Dim}^{A} (x)$ ${dim}^{A} (x ∣ y)$ , and ${Dim}^{A} (x ∣ y)$ are then all identical to their unrelativized versions, except that U is given oracle access to A.

In general, because an instruction to ignore the oracle can be encoded in constant length, the presence of any oracle A cannot significantly increase the complexity of a bit string σ: $\begin{matrix} (2) & K^{A} (σ) ⩽ K (σ) + O (1), \end{matrix}$ and therefore ${dim}^{A} (x) ⩽ dim (x)$ for all $A \subseteq N$ and $x \in R^{n}$ .

We will frequently consider the complexity of a point $x \in R^{n}$ relative to a point $y \in R^{m}$ , i.e., relative to a set $A_{y}$ that encodes the binary expansion of y in a standard way. We then write $K_{r}^{y} (x)$ for $K_{r}^{A_{y}} (x)$ . Lutz and Lutz [25] showed that for all $r, t \in N$ , $x \in R^{m}$ , and $y \in R^{n}$ , $\begin{matrix} (3) & K_{r}^{y} (x) ⩽ K_{r, t} (x ∣ y) + K (t) + O (1), \end{matrix}$ and consequently $\begin{matrix} (4) & {dim}^{y} (x) ⩽ dim (x ∣ y) and {Dim}^{y} (x) ⩽ Dim (x ∣ y) . \end{matrix}$

3. Background and approach

In this section we describe the basic ideas behind our investigation of dimension spectra of lines. We briefly discuss some of our earlier work on this subject, and we present two technical lemmas needed for the proof our main theorems.

The dimension of a point on a line in $R^{2}$ has the following trivial upper bound.

Observation 3.
For all $a, b, x \in R$ , $\begin{matrix} (5) & dim (x, a x + b) ⩽ dim (a, b, x) . \end{matrix}$

The idea here is simple: At any given precision, the amount of information needed to describe a point $(x, a x + b)$ cannot be much greater than the amount of information needed to describe the three parameters $(a, b, x)$ . This is an instance of the following general fact, shown by Reimann [36] for Cantor space and subsequently by Case and J. Lutz [3] for Euclidean spaces.
Lemma 4 ([3 ,36]).

If $f : R^{m} \to R^{n}$ is a computable locally Lipschitz function and $z \in R^{m}$ , then $dim (f (z)) ⩽ dim (z)$ .

In this work our approach is to identify, for given a and b, and relative to a carefully chosen oracle, values of x such that equality holds in (5).

Specifically, for every (or at least infinitely many) $s \in [0, 1]$ , we want to find a value $x \in R$ such that $\begin{matrix} (6) & dim (a, b, x) = dim (a, b) + s \end{matrix}$ and equality holds in (5). For any triple a, b, x satisfying (6), if we can prove that $\begin{matrix} (7) & dim (a, b, x) ⩽ dim (x, a x + b), \end{matrix}$ then we will have $dim (x, a x + b) = s + dim (a, b)$ .

We note that values satisfying (6) always exist:

Observation 5.
For all $a, b \in R$ and $s \in [0, 1]$ , there is some $x \in R$ such that $\begin{matrix} {dim}^{a, b} (x) = dim (x ∣ a, b) = dim (x) = {Dim}^{a, b} (x) = Dim (x ∣ a, b) = Dim (x) = s, \end{matrix}$ and therefore $dim (a, b, x) = dim (a, b) + s$ .
Proof.
Athreya et al. (Theorem 6.5 of [2]) showed that for all $0 ⩽ α ⩽ β ⩽ 1$ , there exists an $x \in R$ with $dim (x) = α$ and $Dim (x) = β$ . In their proof, this x is constructed using a Martin-Löf random sequence R. That proof relativizes; if we choose R to be Martin-Löf random relative to some oracle A, then it yields ${dim}^{A} (x) = α$ and ${Dim}^{A} (x) = β$ . And since a sequence that is Martin-Löf random relative to an oracle is still Martin-Löf random in the unrelativized sense, the conclusion $dim (x) = α$ and $Dim (x) = β$ is also preserved. Thus, choosing $A = A_{(a, b)}$ (as defined in Section 2.4) and $α = β = s$ , we have ${dim}^{a, b} (x) = Dim (x) = s$ .

Definitions and (4) imply that $\begin{matrix} dim (x ∣ a, b), dim (x), {Dim}^{a, b} (x), Dim (x ∣ a, b) \in [{dim}^{a, b} (x), Dim (x)], \end{matrix}$ so these values are all s, and equation (1) gives $\begin{matrix} dim (a, b) + dim (x ∣ a, b) ⩽ dim (x, a, b) ⩽ dim (a, b) + Dim (x ∣ a, b) . \end{matrix}$ □

Informally, (7) means that, given an approximation of the point $(x, a x + b)$ , we can recover an approximation of the line $L_{a, b}$ on which it lies. It may seem surprising that this is ever possible; after all, $(x, a x + b)$ lies on uncountably many lines. But in the case that $dim (a, b) < {dim}^{a, b} (x)$ – intuitively, when answering Which line? requires less information than answering Which point on that line? – there is some hope for such a recovery. The reason is that in this case, $(a, b)$ has a lower dimension than the slope-intercept pair of any other line that $(x, a x + b)$ lies on:
Observation 6.
Suppose $a x + b = u x + v$ and $u \neq a$ . Then $dim (u, v) ⩾ {dim}^{a, b} (x)$ .
Proof.
It is easy to show that ${dim}^{a, b} (u, v) = {dim}^{a, b} (a, b, u, v)$ ; estimating $(a, b)$ requires little information in the presence of an oracle for $(a, b)$ . Therefore, solving for x and applying Lemma 4, we have $\begin{matrix} dim (u, v) ⩾ {dim}^{a, b} (u, v) = {dim}^{a, b} (a, b, u, v) ⩾ {dim}^{a, b} (\frac{b - v}{u - a}) = {dim}^{a, b} (x) . \end{matrix}$ □

Since $(a, b)$ is, in this case, the lowest-dimensional pair such that $(x, a x + b)$ lies on $L_{a, b}$ , one might naïvely hope to use this fact to derive an estimate of $(x, a, b)$ from an estimate of $(x, a x + b)$ . Unfortunately, the dimension of a point is not even semicomputable, so algorithmically distinguishing $(a, b)$ requires a more refined statement.
3.1. Precursors to technical lemmas

The following lemma, which is essentially geometrical, is such a statement.

Lemma 7 ([28]).

Let $a, b, x \in R$ and $r \in N$ . For all $(u, v) \in R^{2}$ such that $u x + v = a x + b$ and $t = - log ‖ (a, b) - (u, v) ‖ \in (0, r]$ , $\begin{matrix} K_{r} (u, v) ⩾ K_{t} (a, b) + K_{r - t}^{a, b} (x) - O (log r) . \end{matrix}$

Notice that the complexity bound depends on the precision parameter t, which in turn depends on the angle of intersection between $L_{a, b}$ and $L_{u, v}$ at the point $(x, a x + b) = (x, u x + v)$ . An approximation of $(u, v)$ gives more information about $(a, b)$ when t is large, meaning that $L_{u, v}$ and $L_{a, b}$ intersect at a shallow angle. When t is smaller, meaning that $L_{u, v}$ and $L_{a, b}$ intersect at a steep angle, an approximation of $(u, v)$ gives less information about $(a, b)$ , but more about where on $L_{a, b}$ the point of intersection lies.

Roughly, if $dim (a, b) < {dim}^{a, b} (x)$ , then Lemma 7 tells us that $K_{r} (u, v) > K_{r} (a, b)$ unless $(u, v)$ is very close to $(a, b)$ . As $K_{r} (u, v)$ is upper semicomputable, this is algorithmically useful: We can enumerate all pairs $(u, v)$ whose precision-r complexity falls below a certain threshold. If one of these pairs satisfies, approximately, $u x + v = a x + b$ , then we know that $(u, v)$ is close to $(a, b)$ . Thus, an estimate for $(x, a x + b)$ algorithmically yields an estimate for $(a, b, x)$ .

In our previous work [28], we used an argument of this type to prove a general lower bound on the dimension of points on lines in $R^{2}$ :

Theorem 8 ([28]).

For all $a, b, x \in R$ , $\begin{array}{l} dim (x, a x + b) ⩾ dim (x ∣ a, b) + min {dim (a, b), {dim}^{a, b} (x)} . \end{array}$

The proof of that theorem uses carefully constructed oracles to artificially lower $K_{r} (a, b)$ when necessary, essentially forcing $dim (a, b) < {dim}^{a, b} (x)$ . This enables the above argument structure about an estimate for $(x, a x + b)$ yielding an estimate of $(a, b, x)$ to be used. Unfortunately, lowering the complexity of $(a, b)$ also weakens the conclusion, leading to the minimum in Theorem 8.

The following two lemmas from our previous work (stated in slightly different forms here) are precursors to Lemmas 13 and 14. The proof of Lemma 13 is similar to that of Lemma 9, and the proof of Lemma 14 is an induction on Lemma 10.

Lemma 9 (N. Lutz and Stull [28]).

Suppose that $a, b, x \in R$ , $r \in N$ , $δ \in R_{+}$ , and $ε, η \in Q_{+}$ satisfy the following conditions.

$r ⩾ log (2 | a | + | x | + 5) + 1$ .

$K_{r} (a, b) ⩽ (η + ε) r$ .

For every $(u, v) \in R^{2}$ such that $t = - log ‖ (a, b) - (u, v) ‖ \in (0, r]$ and $u x + v = a x + b$ , $\begin{matrix} K_{r} (u, v) ⩾ (η - ε) r + δ \cdot (r - t) . \end{matrix}$

Then for every oracle set

A \subseteq N

\begin{matrix} K_{r}^{A} (x, a x + b) ⩾ K_{r}^{A} (a, b, x) - \frac{4 ε}{δ} r - K (ε) - K (η) - O (log r) . \end{matrix}

Informally, Lemma 9 says that if $(a, b)$ has sufficiently low complexity, and if every other u, v such that $(x, a x + b)$ lies on $L_{u, v}$ has sufficiently high complexity – parameterized the distance between $(u, v)$ and $(a, b)$ , and thus indirectly by the angle of intersection between $L_{a, b}$ and $L_{u, v}$ – then approximating $(a, b, x)$ cannot require much more information than approximating $(x, a x + b)$ .

Lemma 10 (N. Lutz and Stull [28]).

Let $r \in N$ , $z \in R^{n}$ , and $η \in Q \cap [0, dim (z)]$ . There is an oracle $A = A (r, z, η)$ such that

For every $t ⩽ r$ , $K_{t}^{A} (z) = min {η r, K_{t} (z)} + O (log r)$ .

For every $t > r$ , $K_{t}^{A} (z) ⩾ η r + K_{t, r} (z ∣ z) + O (log r)$ .

For every $t \in N$ and $y \in R^{m}$ , $K_{t}^{z, A} (y) = K_{t}^{z} (y) + O (log r)$ .

Lemma 10 is an oracle construction that allows us to fine-tune the complexity of any point z. Given a parameter η, this oracle essentially encodes the information needed to get from a precision- $η r$ estimate of z to a precision-r estimate of z.

3.1.1. Computing a line given a point

For our present purposes, we will need the following corollary to Lemma 9. That lemma gave conditions under which precision-r estimates for $(x, a x + b)$ and $(a, b, x)$ contain similar amounts of information. This corollary shows that, under the same conditions, those two approximations are furthermore nearly “interchangeable,” in the sense that there is a short program which, given a precision-r estimate for $(x, a x + b)$ as input, will output a precision-r estimate for $(a, b, x)$ , and, as we argue in the proof, vice versa.

Corollary 11.
If the conditions of Lemma 9 are satisfied, then $\begin{matrix} K_{r}^{A} (a, b, x ∣ x, a x + b) ⩽ \frac{4 ε}{δ} r + K (ε) + K (η) + O (log r) . \end{matrix}$
Proof.
It is easy to see that $K_{r} (x, a x + b ∣ a, b, x) = O (log r)$ : Consider a constant-length program that, given $(u, v, y) \in Q^{3}$ , outputs $(y, u y + v)$ . If $(u, v, y) \in B_{2^{- r}} (a, b, x)$ , then $(y, u y + v) \in B_{2^{c - r}} (x, a x + b)$ , where c is constant in r, so $K_{r - c, r} (a x + b ∣ a, b, x) = O (1)$ . Thus, by Lemma 1, $\begin{matrix} (8) & K_{r} (a x + b ∣ a, b, x) = O (log r) . \end{matrix}$ Now suppose that the conditions of Lemma 9 are satisfied. Then we have $\begin{array}{l} [Lemma 2 ] & K_{r}^{A} (a, b, x ∣ x, a x + b) & = K_{r}^{A} (a, b, x) - K_{r}^{A} (x, a x + b) + K_{r}^{A} (x, a x + b ∣ a, b, x) + O (log r) \\ [equation (8) ] & = K_{r}^{A} (a, b, x) - K_{r}^{A} (x, a x + b) + O (log r) \\ [Lemma 9 ] & ⩽ \frac{4 ε}{δ} r + K (ε) + K (η) + O (log r) . \end{array}$ □

We will also need the following pair of geometric facts about interactions between estimates of the slope-intercept pair $(a, b)$ and of the point $(x, a x + b)$ .
Observation 12 (N. Lutz and Stull [28]).

Let $a, x, b \in R$ and $r \in N$ . Let $(q_{1}, q_{2}) \in B_{2^{- r}} (x, a x + b)$ .

If $(p_{1}, p_{2}) \in B_{2^{- r}} (a, b)$ , then $| p_{1} q_{1} + p_{2} - q_{2} | < 2^{- r} (| p_{1} | + | q_{1} | + 3)$ .

If $| p_{1} q_{1} + p_{2} - q_{2} | ⩽ 2^{- r} (| p_{1} | + | q_{1} | + 3)$ , then there is some pair $(u, v) \in B_{2^{- r} (2 | a | + | x | + 5)} (p_{1}, p_{2})$ such that $a x + b = u x + v$ .

3.2. Technical lemmas

In the present work, we achieve inequality (7) by controlling the choice of x and placing a condition on $(a, b)$ . To adapt the arguments of [28] to the case where $dim (a, b) > {dim}^{a, b} (x)$ , we will use the following two technical lemmas, which are essentially refinements of Lemma 9 and Lemma 10, respectively.

Compared to Lemma 9, Lemma 13 weakens the conditions needed to compute an estimate of $(x, a, b)$ from an estimate of $(x, a x + b)$ . In particular, the incremental range of t considered in condition (3) will allows us to handle different precision ranges separately.

Lemma 13.
Let $a, b, x \in R$ , $k \in N$ , and $r_{0} = 1$ . Suppose that $r_{1}, \dots, r_{k} \in N$ , $δ \in R_{+}$ , and $ε, η \in Q_{+}$ satisfy the following conditions for every $1 ⩽ i ⩽ k$ .
$r_{i} ⩾ log (2 | a | + | x | + 6) + r_{i - 1}$ .

$K_{r_{i}} (a, b) ⩽ (η + ε) r_{i}$ .

For every $(u, v) \in R^{2}$ such that $t = - log ‖ (a, b) - (u, v) ‖ \in (r_{i - 1}, r_{i}]$ and $u x + v = a x + b$ , $\begin{matrix} K_{r_{i}} (u, v) ⩾ (η - ε) r_{i} + δ \cdot (r_{i} - t) . \end{matrix}$
Then for every oracle set $A \subseteq N$ , $\begin{matrix} K_{r_{k}}^{A} (a, b, x ∣ x, a x + b) ⩽ k (K (ε) + K (η) + \frac{4 ε}{δ} r_{k} + O (log r_{k})) . \end{matrix}$
Proof.
Let $a, b, x \in R$ . We proceed by induction on k. By Corollary 11, the conclusion holds for $k = 1$ . Assume the conclusion holds for all $i < k$ . Let $r_{1}, \dots, r_{k}$ , δ, ε, η, and A be as described in the lemma statement.

Define an oracle Turing machine M that does the following given oracle A and input $π = π_{1} π_{2} π_{3} π_{4} π_{5}$ such that $U^{A} (π_{1}) = (q_{1}, q_{2}) \in Q^{2}$ , $U (π_{2}) = (s_{1}, \dots, s_{k}) \in N^{k}$ , $U (π_{3}) = ζ \in Q$ , $U (π_{4}) = ι \in Q$ and $U^{A} (π_{5} π_{1}) = h \in Q^{2}$ .

For every program $σ \in {0, 1}^{}$ with $ℓ (σ) ⩽ (ι + ζ) s_{k}$ , in parallel, M simulates $U (σ)$ . If one of the simulations halts with some output $(p_{1}, p_{2}) \in Q^{2} \cap B_{2^{- s_{k - 1}}} (h)$ such that $\begin{matrix} | p_{1} q_{1} + p_{2} - q_{2} | < 2^{- s_{2}} (| p_{1} | + | q_{1} | + 3), \end{matrix}$ then M halts with output $(p_{1}, p_{2}, q_{1})$ . Let $c_{M}$ be a constant for the description of M.

Now let $π_{1}$ , $π_{2}$ , $π_{3}$ , and $π_{4}$ , testify to $K_{r_{k}}^{A} (x, a x + b)$ , $K (r_{k - 1}, r_{k})$ , $K (ε)$ , $K (η)$ , and $K_{r_{k - 1}, r_{k}} (a, b ∣ x, a x + b)$ , respectively, and let $π = π_{1} π_{2} π_{3} π_{4} π_{5}$ .

By condition (2), there is some $({\hat{p}}_{1}, {\hat{p}}_{2}) \in B_{2^{- r_{k}}} (a, b)$ such that $K ({\hat{p}}_{1}, {\hat{p}}_{2}) ⩽ (η + ε) r_{k}$ , meaning that there is some $\hat{σ} \in {0, 1}^{}$ with $ℓ (\hat{σ}) ⩽ (η + ε) r_{k}$ and $U (\hat{σ}) = ({\hat{p}}_{1}, {\hat{p}}_{2})$ . By Observation 12(1), $\begin{matrix} | {\hat{p}}_{1} q_{1} + {\hat{p}}_{2} - q_{2} | < 2^{- r_{k}} (| {\hat{p}}_{1} | + | q_{1} | + 3), \end{matrix}$ for every $(q_{1}, q_{2}) \in B_{2^{- r_{k}}} (x, a x + b)$ , so M is guaranteed to halt on input π.

Hence, let $(p_{1}, p_{2}, q_{1}) = M (π)$ . By Observation 12(2), there is some $\begin{matrix} (u, v) \in B_{2^{γ - r_{k}}} (p_{1}, p_{2}) \subseteq B_{2^{- r_{k - 1}}} (a, b) \end{matrix}$ such that $u x + v = a x + b$ , where $γ = log (2 | a | + | x | + 5)$ . Since $\begin{matrix} (9) & ‖ (p_{1}, p_{2}) - (u, v) ‖ < 2^{γ - r_{k}} \end{matrix}$ and $| q_{1} - x | < 2^{- r_{k}}$ , we have $\begin{matrix} (10) & (p_{1}, p_{2}, q_{1}) \in B_{2^{γ + 1 - r_{k}}} (u, v, x) . \end{matrix}$ Thus, $\begin{array}{l} [inequality (2) ] & K_{r_{k} - γ - 1}^{A} (u, v, x) & ⩽ K_{r_{k} - γ - 1} (u, v, x) + O (1) \\ [equation (10) ] & ⩽ K (p_{1}, p_{2}, q_{1}) + O (1) \\ [(p_{1}, p_{2}, q_{1}) = M (π)] & = ℓ (π) + c_{M} + O (1) \\ [definition of π] & = K_{r_{k}}^{A} (x, a x + b) + K (r_{k - 1}, r_{k}) + K (ε) + K (η) + ℓ (π_{5}) + O (1) \\ ⩽ K_{r_{k}}^{A} (x, a x + b) + K (ε) + K (η) + ℓ (π_{5}) + O (log r_{k}) . \end{array}$ Since $γ + 1$ is a constant, it follows that $\begin{array}{l} [Lemma 1 ] & K_{r_{k}}^{A} (u, v, x ∣ x, a x + b) & = K_{r_{k} - γ - 1, r_{k}}^{A} (u, v, x ∣ x, a x + b) + O (log r_{k}) \\ [Lemma 2 ] & ⩽ K_{r_{k} - γ - 1}^{A} (u, v, x) - K_{r_{k}}^{A} (x, a x + b) + O (log r_{k}) \\ (11) & ⩽ K (ε) + K (η) + ℓ (π_{5}) + O (log r_{k}) . \end{array}$

By the induction hypothesis, then, $\begin{array}{l} [definition of π_{5}] & ℓ (π_{5}) & = K_{r_{k - 1}, r_{k}} (a, b ∣ x, a x + b) \\ [B_{2^{- r_{k}}} (x, a x + b) \subseteq B_{2^{- r_{k - 1}}} (x, a x + b)] & ⩽ K_{r_{k - 1}} (a, b ∣ x, a x + b) \\ (12) & ⩽ (k - 1) (K (ε) + K (η) + \frac{4 ε}{δ} r_{k - 1} + O (log r_{k - 1})) . \end{array}$

We now bound $K_{r_{k}}^{A} (a, b, x ∣ u, v, x)$ . If $t > r_{k}$ , then $(u, v, x) \in B_{2^{- r_{k}}} (a, b, x)$ , so any precision- $r_{k}$ approximation of $(u, v, x)$ is also a precision- $(r_{k} - 1)$ approximation of $(a, b, x)$ . Thus, $\begin{matrix} K_{r_{k} - 1, r_{k}} (a, b, x ∣ u, v, x) = O (1), \end{matrix}$ and applying Lemma 1 gives $\begin{matrix} K_{r_{k}}^{A} (a, b, x ∣ u, v, x) = O (log r_{k}) . \end{matrix}$ Now suppose that $t ⩽ r_{k}$ . Since γ is a constant, $\begin{array}{l} [condition (2)] & (η + ε) r_{k} & ⩾ K (p_{1}, p_{2}) \\ [inequality (9) ] & ⩾ K_{r_{k} - γ} (u, v) \\ [Lemma 1 ] & ⩾ K_{r_{k}} (u, v) - O (log r_{k}) . \end{array}$ Combining this with condition (3) in the lemma statement gives $\begin{matrix} (η - ε) r_{k} + δ \cdot (r_{k} - t) ⩽ (η + ε) r_{k} + O (log k), \end{matrix}$ which can be simplified to $\begin{matrix} (13) & r_{k} - t ⩽ \frac{2 ε}{δ} r_{k} + O (log r_{k}) . \end{matrix}$

Since $t ⩽ r_{k}$ and $(u, v) \in B_{2^{- t}} (a, b)$ , any precision- $r_{k}$ approximation of $(u, v)$ is also a precision- $(t - 1)$ approximation of $(a, b)$ : $\begin{matrix} (14) & B_{2^{- r_{k}}} (u, v) \subseteq B_{2^{1 - t}} (a, b) . \end{matrix}$ Therefore we can apply inequality (13) to get $\begin{array}{l} [Lemma 2 ] & K_{r_{k}} (a, b, x ∣ u, v, x) & = K_{r_{k}} (a, b ∣ u, v) + O (log r_{k}) \\ [equation (14) ] & ⩽ K_{r_{k}, t - 1} (a, b ∣ a, b) + O (log r_{k}) \\ [Lemma 1 ] & ⩽ 2 (r_{k} - t) + O (log r_{k}) \\ (15) & ⩽ \frac{4 ε}{δ} r_{k} + O (log r_{k}), \end{array}$ for every $t \in N$ .

Putting the above analysis together, we have $\begin{array}{l} [Lemma 2 ] & K_{r_{k}} (a, b, x ∣ x, a x + b) & ⩽ K_{r_{k}} (u, v, x ∣ x, a x + b) + K_{r_{k}} (a, b, x ∣ u, v, x) + O (log r_{k}) \\ [inequality (15) ] & ⩽ K_{r_{k}} (u, v, x ∣ x, a x + b) + \frac{4 ε}{δ} r_{k} + O (log r_{k}) \\ [inequality (11) ] & ⩽ ℓ (π_{5}) + K (ε) + K (η) + \frac{4 ε}{δ} r_{k} + O (log r_{k}) \\ [inequality (12) ] & ⩽ k (K (ε) + K (η) + \frac{4 ε}{δ} r_{k} + O (log r_{k})) . \end{array}$ □

Lemma 14 strengthens the oracle construction of Lemma 10, allowing us to control a point’s complexity at multiple levels of precision. It essentially uses the construction of Lemma 10, iterated at multiple precisions. Given a point z, precisions $r_{1}, \dots, r_{k}$ , and a target parameter η, the oracle D we construct will aim to reduce the complexity of z at each precision $r_{i}$ to approximately $η r_{i}$ . This goal is captured by property (1) in the lemma statement. Note that in some cases, it may not be possible to achieve $K_{r_{i}}^{D} (z) = η r_{i}$ , even approximately. If the additional information needed to get from a precision- $r_{i - 1}$ approximation of z to a precision- $r_{i}$ approximation of z – i.e., $K_{r_{i}, r_{i - 1}} (z ∣ z)$ – is significantly less than $η \cdot (r_{i} - r_{i - 1})$ , then by the symmetry of information (Lemma 2), it will not be possible to satisfy both $K_{r_{i - 1}}^{D} (z) = η r_{i - 1}$ and $K_{r_{i}}^{D} (z) = η r_{i}$ . This issue is the reason for the minimum in property (1).

Beyond what is needed to achieve property (1), we want this oracle to affect complexities as little as possible, which is captured by the remaining four properties. Property (2) says that for precisions less than $r_{1}$ , D reduces the complexity of z only as much as is necessary to be consistent with monotonicity and $K_{r_{1}}^{D} (z)$ being approximately $η r_{1}$ , and property (3) is the corresponding statement for $i > 1$ . Property (4) says that for precisions beyond $r_{k}$ , D no longer causes any significant reduction in the complexity of z. Property (5) says that D is essentially just a partial description of z, without extraneous information, in the sense that it does not reduce any complexities by more than an oracle for z would.

These five properties necessitate a somewhat unwieldy induction, but the basic role of the oracle D is simple: Given a precision- $r_{i - 1}$ approximation of z, D provides just enough help to make sure that specifying a precision- $r_{i}$ approximation of z will not require much more than $η \cdot (r_{i} - r_{i - 1})$ additional bits. The purpose of properties (2)–(4) is to ensure that D is “well-behaved” while fulfilling this role. Lemma 14.
For all $z \in R^{n}$ , $η \in Q \cap [0, dim (z)]$ , $k \in N$ , and $r_{1} < \dots < r_{k} \in N$ , there is an oracle $D = D (r_{1}, \dots, r_{k}, z, η)$ such that
For every $1 ⩽ i ⩽ k$ , $K_{r_{i}}^{D} (z) = η r_{1} + \sum_{j = 2}^{i} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z)} + O (log r_{k})$ .

For every $t ⩽ r_{1}$ , $K_{t}^{D} (z) = min {η r_{1}, K_{t} (z)} + O (log r_{k})$ .

For every $1 ⩽ i < k$ , and every $r_{i} ⩽ t < r_{i + 1}$ , $K_{t}^{D} (z) ⩾ K_{r_{i}}^{D} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)} + O (log r_{k})$ .

For every $t ⩾ r_{k}$ , $K_{t}^{D} (z) = K_{r_{k}}^{D} (z) + K_{t, r_{k}} (z ∣ z) + O (log r_{k})$ .

For every $t \in N$ and $x \in R$ , $K_{t}^{z, D} (x) = K_{t}^{z} (x) + O (log r_{k})$ .

Proof.
We begin by introducing some notation. Given an oracle $D \subseteq N$ , a precision $r \in N$ , a point $z \in R^{n}$ , and a rational parameter $η \in Q \cap [0, {dim}^{D} (z)]$ , we let $A^{D} (r, z, η)$ denote the oracle guaranteed by applying Lemma 10 relative to D. For oracles $A, B \subseteq N$ , we let $A \oplus B \subseteq N$ denote an oracle that combines A and B by interleaving.

Now fix $z \in R^{n}$ and $η \in Q \cap [0, dim (z)]$ , and let $r_{1} < r_{2} < \dots$ be an increasing sequence of natural numbers. We define a sequence of oracles recursively. Let $D_{1} = A (r_{1}, z, η)$ , as defined in Lemma 10, and for every $i > 1$ , let $\begin{matrix} (16) & D_{i} = \{\begin{matrix} D_{i - 1} & if K_{r_{i}, r_{i - 1}}^{D_{i - 1}} (z ∣ z) < η \cdot (r_{i} - r_{i - 1}) \\ D_{i - 1} \oplus A^{D_{i - 1}} (r_{i}, z, η_{i}) & otherwise, \end{matrix} \end{matrix}$ where $η_{i}$ is defined to be $\begin{matrix} (17) & η_{i} = \frac{K_{r_{i - 1}}^{D_{i - 1}} (z) + η \cdot (r_{i} - r_{i - 1})}{r_{i}} . \end{matrix}$ Notice that each $D_{i}$ is a finite oracle, so ${dim}^{D_{i}} (z) = dim (z)$ holds for all i.

We now show by induction on k that for all $k \in N$ , the oracle $D_{k}$ satisfies the four properties in the lemma statement. For $k = 1$ , Lemma 10 shows that $D_{1}$ satisfies these four properties.

For the inductive step, fix some $ℓ > 1$ , and assume that the oracle $D_{ℓ - 1}$ satisfies the four properties for $k = ℓ - 1$ .

To see that the oracle $D_{ℓ}$ satisfies property (1) for $k = ℓ$ , first consider the case that $1 ⩽ i < ℓ$ . In this case, if $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) < η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then $\begin{array}{l} [equation (16) ] & K_{r_{i}}^{D_{ℓ}} (z) & = K_{r_{i}}^{D_{ℓ - 1}} (z) \\ [induction hypothesis] & = η r_{1} + \sum_{j = 2}^{i} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z)} + O (log r_{ℓ - 1}) . \end{array}$ Otherwise, if $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) ⩾ η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then since $r_{i} ⩽ r_{ℓ - 1}$ in this case, $\begin{array}{l} [equation (16) ] & K_{r_{i}}^{D_{ℓ}} (z) & = K_{r_{i}}^{D_{ℓ - 1} \oplus A^{D_{ℓ - 1}} (r_{ℓ}, z, η_{ℓ})} (z) \\ [Lemma 10 (1), relative to D_{ℓ - 1}] & = min {η_{ℓ} r_{ℓ}, K_{r_{i}}^{D_{ℓ - 1}} (z)} + O (log r_{ℓ}) . \end{array}$ By the definition of $η_{ℓ}$ , equation (17), $\begin{array}{l} η_{ℓ} r_{ℓ} & = K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + η \cdot (r_{ℓ} - r_{ℓ - 1}) \\ ⩾ K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) . \end{array}$ Therefore, $\begin{array}{l} K_{r_{i}}^{D_{ℓ}} (z) & = K_{r_{i}}^{D_{ℓ - 1}} (z) + O (log r_{ℓ}) \\ [induction hypothesis] & = η r_{1} + \sum_{j = 2}^{i} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z) + O (log r_{ℓ}) . \end{array}$ The other case to consider is that $i = ℓ$ . If $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) < η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then $\begin{array}{l} [equation (16) ] & K_{r_{ℓ}}^{D_{ℓ}} (z) = & K_{r_{ℓ}}^{D_{ℓ - 1}} (z) \\ [induction hypothesis] & = & K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + min {η \cdot (r_{ℓ} - r_{ℓ - 1}), K_{r_{ℓ}, r_{ℓ - 1}} (z ∣ z)} + O (log r_{k}) \\ = & η r_{1} + \sum_{j = 2}^{ℓ - 1} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z)} \\ [induction hypothesis] & + K_{r_{ℓ}, r_{ℓ - 1}} (z ∣ z) + O (log r_{ℓ}) \\ assumption & = & η r_{1} + \sum_{j = 2}^{i} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z)} + O (log r_{j}) . \end{array}$ If instead $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) ⩾ η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then $\begin{array}{l} [equation (16) ] & K_{r_{ℓ}}^{D_{ℓ}} (z) & = K_{r_{ℓ}}^{D_{ℓ - 1} \oplus A^{D_{ℓ - 1}} (r_{ℓ}, z, η_{ℓ})} (z) \\ [Lemma 10 (1), relative to D_{ℓ - 1}] & = min {η_{ℓ} r_{ℓ}, K_{r_{ℓ}}^{D_{ℓ - 1}} (z)} + O (log r_{ℓ}) \\ ⩽ η_{ℓ} r_{ℓ} + O (log r_{ℓ}), \end{array}$ and $\begin{array}{l} [equation (17) ] & η_{ℓ} r_{ℓ} & = K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + η \cdot (r_{ℓ} - r_{ℓ - 1}) \\ [assumption] & ⩽ K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) \\ [Lemma 2 ] & = K_{r_{ℓ}}^{D_{ℓ}} (z) + O (log r_{ℓ}) . \end{array}$ Therefore, $\begin{array}{l} K_{r_{ℓ}}^{D_{ℓ}} (z) = & η_{ℓ} r_{ℓ} + O (log r_{ℓ}) \\ [equation (17) ] & = & K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + η \cdot (r_{ℓ} - r_{ℓ - 1}) \\ = & η r_{1} + \sum_{j = 2}^{ℓ - 1} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z) + η \cdot (r_{ℓ} - r_{ℓ - 1})} \\ [induction hypothesis] & + O (log r_{ℓ}) \\ [assumption] & = & η r_{1} + \sum_{j = 2}^{ℓ} min {η \cdot (r_{j} - r_{j - 1}), K_{r_{j}, r_{j - 1}} (z ∣ z)} + O (log r_{ℓ}) . \end{array}$ Thus, property (1) is satisfied for $k = ℓ$ .

To see that the oracle $D_{ℓ}$ satisfies property (2) for $k = ℓ$ , let $t ⩽ r_{1}$ . If $K_{r_{i}, r_{i - 1}}^{D_{i - 1}} (z ∣ z) < η \cdot (r_{i} - r_{i - 1})$ , then $\begin{array}{l} [equation (16) ] & K_{t}^{D_{ℓ}} (z) & = K_{t}^{D_{ℓ - 1}} (z) \\ [induction hypothesis] & = min {η r_{1}, K_{t} (z)} + O (log r_{ℓ}) . \end{array}$ Otherwise, $\begin{array}{l} [equation (16) ] & K_{t}^{D_{ℓ}} (z) & = K_{t}^{D_{ℓ - 1} \oplus A^{D_{ℓ - 1}} (r_{ℓ}, z, η_{ℓ})} (z) \\ [Lemma 10 (1), relative to D_{ℓ - 1}] & = min {η_{ℓ} r_{ℓ}, K_{t}^{D_{ℓ - 1}} (z)} + O (log r_{ℓ}) \\ [induction hypothesis] & = min {η_{ℓ} r_{ℓ}, min {η r_{1}, K_{t} (z)} + O (log r_{ℓ - 1})} + O (log r_{ℓ}) \\ [equation (17) ] & = min {K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + η \cdot (r_{ℓ} - r_{ℓ - 1}), min {η r_{1}, K_{t} (z)} + O (log r_{ℓ - 1})} + O (log r_{ℓ}) . \end{array}$ Since $\begin{matrix} K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + η \cdot (r_{ℓ} - r_{ℓ - 1}) ⩾ η r_{1}, \end{matrix}$ by our induction hypothesis, $\begin{array}{l} K_{t}^{D_{ℓ}} (z) & = min {η r_{1}, min {η r_{1}, K_{t} (z)} + O (log r_{ℓ - 1})} + O (log r_{ℓ}) \\ [r_{1} ⩽ r_{ℓ - 1} < r_{ℓ}] & = min {η r_{1}, K_{t} (z)} + O (log r_{ℓ}) . \end{array}$ Therefore, in both cases, property (2) holds.

We now show that property (3) is satisfied for $k = ℓ$ . Let $1 ⩽ i < ℓ$ , and let $r_{i} ⩽ t < r_{i + 1}$ . In this case, if $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) < η \cdot (r_{ℓ} - r_{ℓ - 1})$ . $\begin{array}{l} [equation (16) ] & K_{t}^{D_{ℓ}} (z) & = K_{t}^{D_{ℓ - 1}} (z) \\ [induction hypothesis] & ⩾ K_{r_{i}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)} + O (log r_{k}) \\ [equation (16) ] & = K_{r_{i}}^{D_{ℓ}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)} + O (log r_{k}) . \end{array}$ Otherwise, if $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) ⩾ η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then since $r_{i} ⩽ r_{ℓ - 1}$ in this case, $\begin{array}{l} [equation (16) ] & K_{t}^{D_{ℓ}} (z) & = K_{t}^{D_{ℓ - 1} \oplus A^{D_{ℓ - 1}} (r_{ℓ}, z, η_{ℓ})} (z) \\ [Lemma 10 (1), relative to D_{ℓ - 1}] & = min {η_{ℓ} r_{ℓ}, K_{t}^{D_{ℓ - 1}} (z)} + O (log r_{ℓ}) . \end{array}$ If $i = ℓ - 1$ , then we have $\begin{array}{l} [induction hypothesis] & K_{t}^{D_{ℓ}} (z) ⩾ & min {η_{ℓ} r_{ℓ}, K_{r_{i}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)}} + O (log r_{k}) \\ = & min {K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + η \cdot (r_{ℓ} - r_{ℓ - 1}), K_{r_{i}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)}} \\ [equation (17) ] & + O (log r_{k}) \\ [i = ℓ - 1] & = & K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + min {η \cdot (r_{ℓ} - r_{ℓ - 1}), min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)}} + O (log r_{k}) \\ [t < r_{ℓ}] & = & K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)} + O (log r_{k}) . \end{array}$ If $i < ℓ - 1$ , then $\begin{array}{l} [Lemma 2 ] & K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) & = K_{t}^{D_{ℓ - 1}} (z) + K_{r_{ℓ - 1}, t}^{D_{ℓ - 1}} (z) \\ [induction hypothesis] & = K_{r_{i}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)} + K_{r_{ℓ - 1}, t}^{D_{ℓ - 1}} (z) \\ ⩾ K_{r_{i}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)} . \end{array}$ Therefore $η_{ℓ} r_{ℓ} ⩾ K_{t}^{D_{ℓ - 1}} (z)$ , so $\begin{matrix} K_{t}^{D_{ℓ}} (z) = K_{r_{i}}^{D_{ℓ - 1}} (z) + min {η \cdot (t - r_{i}), K_{t, r_{i}} (z ∣ z)}, \end{matrix}$ and property (3) is satisfied.

To see that property (4) is satisfied for $k = ℓ$ , let $t ⩾ r_{ℓ}$ . If $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) < η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then $\begin{array}{l} [equation (16) ] & K_{t}^{D_{ℓ}} (z) & = K_{t}^{D_{ℓ - 1}} (z) \\ [induction hypothesis] & = K_{r_{ℓ}}^{D_{ℓ - 1}} (z) + K_{t, r_{ℓ}} (z ∣ z) + O (log r_{k}) \\ = K_{r_{ℓ}}^{D_{ℓ}} (z) + K_{t, r_{ℓ}} (z ∣ z) + O (log r_{k}) . \end{array}$ If instead $K_{r_{ℓ}, r_{ℓ - 1}}^{D_{ℓ - 1}} (z ∣ z) ⩾ η \cdot (r_{ℓ} - r_{ℓ - 1})$ , then $\begin{array}{l} [equation (16) ] & K_{t}^{D_{ℓ}} (z) & = K_{t}^{D_{ℓ - 1} \oplus A^{D_{ℓ - 1}} (r_{ℓ}, z, η_{ℓ})} (z) \\ [Lemma 10 (2), relative to D_{ℓ - 1}] & = K_{r_{ℓ}}^{D_{ℓ}} (z) + K_{t, r_{ℓ}}^{D_{ℓ - 1}} (z ∣ z) + O (log r_{ℓ}) \\ [Lemma 2 ] & = K_{r_{ℓ}}^{D_{ℓ}} (z) + K_{t}^{D_{ℓ - 1}} (z) - K_{r_{ℓ}}^{D_{ℓ - 1}} (z) + O (log r_{ℓ}) \\ [induction hypothesis] & = K_{r_{ℓ}}^{D_{ℓ}} (z) + K_{r_{ℓ - 1}}^{D_{ℓ - 1}} (z) + K_{t, r_{ℓ - 1}} (z) - K_{r_{ℓ}}^{D_{ℓ - 1}} (z) + O (log r_{ℓ}) \\ = K_{r_{ℓ}}^{D_{ℓ}} (z) + K_{t, r_{ℓ - 1}} (z) . \end{array}$ and the proof of property (4) is complete.

Finally, we show that property (5) is satisfied for $k = ℓ$ . Let $t \in N$ and $y \in R^{m}$ . If $K_{r_{ℓ}}^{D_{ℓ - 1}} (z) < η r_{ℓ}$ , then $\begin{array}{l} [equation (16) ] & K_{t}^{z, D_{ℓ}} (y) & = K_{t}^{z, D_{ℓ - 1}} (y) \\ [induction hypothesis] & = K_{t}^{z} (y) + O (log r_{ℓ}) . \end{array}$ Otherwise, if $K_{r_{ℓ}}^{D_{ℓ - 1}} (z) ⩾ η r_{ℓ}$ , then $\begin{array}{l} [equation (16) ] & K_{t}^{z, D_{j}} (y) & = K_{t}^{z, D_{j - 1} \oplus A^{D_{ℓ - 1}} (r_{ℓ}, z, η)} (y) \\ [Lemma 10 (3), relative to D_{j - 1}] & = K_{t}^{z, D_{j - 1}} (y) + O (log r_{ℓ}) \\ [induction hypothesis] & = K_{t}^{z} (y) + O (log r_{ℓ}) . \end{array}$ This shows that property (5) is satisfied. This concludes the induction, proving the lemma. □

4. Main theorems

In this section we prove our two main theorems, concerning the dimension spectrum of a line $L_{a, b}$ in the cases that $dim (a, b) = Dim (a, b)$ and that $dim (a, b) ⩾ 1$ , respectively. In both cases, given such a slope-intercept pair $(a, b)$ , we will construct a value $x \in R$ whose information density fluctuates across precisions in a way that allows us to place bounds on $dim (x, a x + b)$ .

4.1. First main theorem

Our first main theorem states that if the effective Hausdorff and packing dimensions of the slope-intercept pair $(a, b)$ are equal – i.e., if the limit ${lim}_{r \to \infty} K_{r} (a, b) / r$ exists – then the dimension spectrum of the line $L_{a, b}$ contains an interval of length 1.

Theorem 15.
Let $a, b \in R$ satisfy $dim (a, b) = Dim (a, b)$ . Then for every $s \in [0, 1]$ there is a value $x \in R$ such that $dim (x, a x + b) = s + min {dim (a, b), 1}$ .

We begin with an overview of our proof. For each value of s, we will construct a real number x whose information density $K_{r} (x) / r$ fluctuates, roughly, between s and 1, in a way that is independent of the information in $(a, b)$ . We will construct x by having its binary expansion alternate between long strings of zeros and long strings of bits that are random relative to $(a, b)$ . In this way, x will approach its minimum information density s at the precisions where it switches from zeros to random bits, which will occur at each of a doubly exponential sequence of precisions ${h_{j}}_{j \in N}$ .

We will first show the upper bound $dim (x, a x + b) ⩽ s + min {dim (a, b), 1}$ , which is a straightforward and unsurprising calculation given our construction of x: At each precision $h_{j}$ , the complexity $K_{h_{j}} (x)$ is approximately $s h_{j}$ , the complexity $K_{h_{j}} (x, a x + b)$ cannot be much greater than $K_{h_{j}} (x) + K_{h_{j}} (a x + b ∣ x)$ by the symmetry of information, and it is easy to see that $K_{h_{j}} (a x + b ∣ x)$ cannot be much greater than either $K_{h_{j}} (a x + b)$ or $K_{h_{j}} (a, b)$ .

The lower bound $dim (x, a x + b) ⩾ s + min {dim (a, b), 1}$ is more difficult. We will show that, for all sufficiently large precisions r, the complexity $K_{r} (x, a x + b)$ cannot be much less than $K_{r} (x) + min {K_{r} (a, b), r}$ . Our approach is to show that a precision-r approximation for the point $(x, a x + b)$ can be used (with some small amount of auxiliary information) to compute a precision-r approximation of $(a, b)$ . We consider precisions r in each range $[s h_{j}, s h_{j + 1})$ , for sufficiently large j, and we split each such range into two parts: $[s h_{j}, m h_{j})$ , and $[m h_{j}, s h_{j + 1})$ , where $m > 1$ is a carefully chosen constant.

For precisions $r \in [s h_{j}, m h_{j})$ , we compute the precision-r approximation of $(a, b)$ using the strategy indicated by Lemma 13. That is, we compute approximations of $(a, b)$ iteratively, at an increasing sequence of precisions. We cannot, due to the accumulation of additive errors, continue like this indefinitely. However, because the information density of x grows throughout the precision range $[h_{j}, s h_{j + 1})$ as random bits are appended, it eventually reaches an information density that is sufficiently large to be amenable to the non-iterative approach of [28]. We choose m according to this threshold, cut off the iterative procedure at precision $m h_{j}$ , and thereafter revert to the strategy of [28]. Proof.
Every line in $R^{2}$ contains a point of effective Hausdorff dimension 1 [40], and by the preservation of effective dimensions under computable bi-Lipschitz functions, $dim (a, a^{2} + b) = dim (a, b)$ , so the theorem holds for $s = 0$ .

Now let $s \in (0, 1]$ , and assume that $d = dim (a, b) = Dim (a, b)$ . Let $y = (y [0], y [1], y [2], \dots)$ be an infinite binary sequence that is random relative to $(a, b)$ . That is, there is some constant $c \in N$ such that for all $r \in N$ , $K^{a, b} (y ↾ r) ⩾ r - c$ . Define sequence of natural numbers ${h_{j}}_{j \in N}$ inductively as follows. Define $h_{0} = 1$ . For every $j > 0$ , define $\begin{matrix} h_{j} = min {h ⩾ 2^{h_{j - 1}} : K_{h} (a, b) ⩽ (d + \frac{1}{j}) h} . \end{matrix}$ Note that $h_{j}$ always exists. For every $r \in N$ , let $\begin{matrix} (18) & x [r] = \{\begin{matrix} 0 & if r \in [s h_{j}, h_{j}) for some j \in N \\ y [r] & otherwise \end{matrix} \end{matrix}$ Define $x \in [0, 1]$ to be the real number with this binary expansion. Observe that, for every $j \in N$ , $\begin{matrix} x [h_{j - 1}], \dots, x [⌊ s h_{j} ⌋ - 1] = y [h_{j - 1}], \dots, y [⌊ s h_{j} ⌋ - 1], \end{matrix}$ and $h_{j - 1} ⩽ log h_{j}$ , so all but $O (log h_{j})$ of the first $s h_{j}$ bits of x are almost all from y, meaning that for all $r ⩽ s h_{j}$ , $\begin{matrix} (19) & K_{r} (x) = K_{r}^{a, b} (x) + O (log h_{j}) = r + O (log h_{j}) . \end{matrix}$ Thus, since the bits of x not due to y are all 0, ${dim}^{a, b} (x) = dim (x)$ . Furthermore, at every precision r, at least $s r - O (log r)$ of x’s bits are from y, and at precisions $h_{j}$ , $s h_{j} - O (log h_{j})$ of x’s bits are from y, so we have $\begin{matrix} (20) & {dim}^{a, b} (x) = s . \end{matrix}$

We now show our upper bound, that $dim (x, a x + b) ⩽ s + min {d, 1}$ . For every $j \in N$ , $\begin{array}{l} [Lemma 2 ] & K_{h_{j}} (x, a x + b) & = K_{h_{j}} (x) + K_{h_{j}} (a x + b ∣ x) + O (log h_{j}) \\ [equation (18) ] & ⩽ K_{s h_{j}} (x) + K (0^{h_{j} - s h_{j}}) + K_{h_{j}} (a x + b ∣ x) + O (log h_{j}) \\ [K (0^{h_{j} - s h_{j}}) = O (log h_{j})] & = K_{s h_{j}} (x) + K_{h_{j}} (a x + b ∣ x) + O (log h_{j}) \\ [equation (19) ] & = s h_{j} + K_{h_{j}} (a x + b ∣ x) + O (log h_{j}) \\ [Lemma 2 ] & ⩽ s h_{j} + min {K_{h_{j}} (a, b), K_{h_{j}} (a x + b)} + O (log h_{j}) \\ [definition of Dim] & ⩽ s h_{j} + min {Dim (a, b) \cdot h_{j}, Dim (a x + b) \cdot h_{j}} + o (h_{j}) \\ (21) & ⩽ s h_{j} + min {d, 1} \cdot h_{j} + o (h_{j}) . \end{array}$ Therefore, $\begin{array}{l} [definition of dim] & dim (x, a x + b) & = \underset{r \to \infty}{lim inf} \frac{K_{r} (x, a x + b)}{r} \\ [definition of lim inf] & ⩽ \underset{j \to \infty}{lim inf} \frac{K_{h_{j}} (x, a x + b)}{h_{j}} \\ [inequality (21) ] & ⩽ \underset{j \to \infty}{lim inf} \frac{s h_{j} + min {d, 1} h_{j} + o (h_{j})}{h_{j}} \\ = s + min {d, 1} . \end{array}$

For the lower bound, first consider the case that $1 ⩾ s ⩾ d$ . In this case, $\begin{array}{l} [Theorem 8 ] & dim (x, a x + b) & ⩾ dim (x ∣ a, b) + min {{dim}^{a, b} (x), dim (a, b)} \\ [inequality (4) ] & ⩾ {dim}^{a, b} (x) + min {{dim}^{a, b} (x), dim (a, b)} \\ [dim (a, b) = d, equation (20) ] & = s + min {s, d} \\ [1 ⩾ s ⩾ d] & = s + min {1, d} . \end{array}$

Hence, we assume that $s < d$ . Let $η \in Q \cap (s, min {d, 1})$ and $ε \in Q_{+}$ . We will show that $\begin{matrix} dim (x, a x + b) ⩾ s + η - α ε, \end{matrix}$ where α is some constant independent of η and ε.

Let $m = \frac{s - 1}{η - 1}$ , and let $j \in N$ be sufficiently large. We first consider the case where $r \in (s h_{j}, m h_{j}]$ . We will use Lemma 13 to show that $\begin{matrix} (22) & K_{r} (x, a x + b) ⩾ K_{r} (x) + η r - c \frac{ε}{δ} r - o (r), \end{matrix}$ where $δ = 1 - η > 0$ .

For all $1 ⩽ i ⩽ k$ , define $r_{i} = ⌈ i s h_{j} ⌉$ . Let $D = D (r_{1}, \dots, r_{k}, (a, b), η)$ be the oracle defined in Lemma 14. Note that, since $dim (a, b)$ and $Dim (a, b)$ are assumed to be equal, $\begin{array}{l} [Lemma 2 ] & K_{r_{i}, r_{i - 1}} (a, b ∣ a, b) = & K_{r_{i}} (a, b) - K_{r_{i - 1}} (a, b) - O (log r_{i}) \\ ⩾ & dim (a, b) r_{i} - o (r_{i}) - Dim (a, b) r_{i - 1} \\ [definition of dim and Dim] & - o (r_{i - 1}) - O (log r_{i}) \\ [dim (a, b) = Dim (a, b)] & = & dim (a, b) r_{i} - o (r_{i}) - dim (a, b) r_{i - 1} - o (r_{i - 1}) - O (log r_{i}) \\ [η < dim (a, b)] & ⩾ & η \cdot (r_{i} - r_{i - 1}) - o (r_{i}) . \end{array}$ Hence, by property (2) of Lemma 14, for every $1 ⩽ i ⩽ k$ , $\begin{matrix} (23) & | K_{r_{i}}^{D} (a, b) - η r_{i} | ⩽ o (r_{k}) . \end{matrix}$

We now show that the conditions of Lemma 13 are satisfied. Condition (1) is satisfied by all sufficiently large precisions r, so it will be satisfied by letting j be large. By inequality (23), for every $1 ⩽ i ⩽ k$ , $\begin{matrix} K_{r_{i}}^{D} (a, b) ⩽ η r_{i} + o (r_{k}), \end{matrix}$ and so $K_{r_{i}}^{D} (a, b) ⩽ (η + ε) r_{i}$ , for sufficiently large j. Thus condition (2) of Lemma 13 is satisfied.

To see that condition (3) of Lemma 13 is satisfied, first consider the case where $i = 1$ , and recall that $r_{1} = ⌈ s h_{j} ⌉$ . Let $(u, v) \in B_{r_{i - 1}} (a, b)$ such that $u x + v = a x + b$ and $t = - log ‖ (a, b) - (u, v) ‖ ⩽ r_{1}$ . Then $\begin{array}{l} [Lemma 7 ] & K_{r_{i}}^{D} (u, v) & ⩾ K_{t}^{D} (a, b) + K_{r_{1} - t, r_{1}}^{D} (x ∣ a, b) - O (log r_{1}) \\ [Lemma 14 (1)] & = min {η r_{1}, K_{t} (a, b)} + K_{r_{1} - t, r_{1}}^{D} (x ∣ a, b) - O (log r_{k}) \\ [inequality (3) ] & ⩾ min {η r_{1}, K_{t} (a, b)} + K_{r_{1} - t}^{D, a, b} (x) - O (log r_{k}) \\ [Lemma 14 (5)] & = min {η r_{1}, K_{t} (a, b)} + K_{r_{1} - t}^{a, b} (x) - O (log r_{k}) \\ [equation (19) ] & = min {η r_{1}, K_{t} (a, b)} + (r_{1} - t) - O (log r_{k}) \\ [definition of dim] & = min {η r_{1}, dim (a, b) t - o (t)} + (r_{1} - t) - O (log r_{k}) \\ [dim (a, b) = d, t ⩽ r_{k}] & = min {η r_{1}, d t} + (r_{1} - t) - o (r_{k}) \\ [δ = 1 - η] & = min {η r_{1}, d t} + (η + δ) (r_{1} - t) - o (r_{k}) \\ [η < d] & ⩾ min {η r_{1}, η t} + (η + δ) (r_{1} - t) - o (r_{k}) \\ [t ⩽ r_{1}] & = η r_{1} + δ (r_{1} - t) - o (r_{k}) . \end{array}$ The other case is that $1 < i ⩽ k$ . In this case, let $(u, v) \in B_{r_{i - 1}} (a, b)$ such that $u x + v = a x + b$ and $t = - log ‖ (a, b) - (u, v) ‖ ⩽ r_{i}$ . Then $t > r_{i - 1}$ , so by the definition of $r_{i}$ , $\begin{array}{l} r_{i} - t & < r_{i} - r_{i - 1} \\ = ⌈ i s h_{j} ⌉ - ⌈ (i - 1) s h_{j} ⌉ \\ ⩽ s h_{j} + 1 \\ ⩽ r_{1} + 1 . \end{array}$ Since $r_{i}$ and $r_{1}$ are both integers, this implies that $r_{i} - t ⩽ r_{1}$ . Therefore, $\begin{array}{l} [Lemma 7 ] & K_{r_{i}}^{D} (u, v) ⩾ & K_{t}^{D} (a, b) + K_{r_{i} - t, r_{i}}^{D} (x ∣ a, b) - O (log r_{1}) \\ = & K_{r_{i - 1}}^{D} (a, b) + min {η \cdot (t - r_{i - 1}), K_{t, r_{i - 1}} (a, b ∣ a, b)} \\ [Lemma 14 (4)] & + K_{r_{i} - t, r_{i}}^{D} (x ∣ a, b) - O (log r_{1}) \\ = & η \cdot (r_{i - 1}) + min {η \cdot (t - r_{i - 1}), K_{t, r_{i - 1}} (a, b ∣ a, b)} \\ [equation (23) ] & + K_{r_{i} - t, r_{i}}^{D} (x ∣ a, b) - O (log r_{1}) \\ = & η \cdot (r_{i - 1}) + min {η \cdot (t - r_{i - 1}), dim (a, b) (t - r_{i - 1}) - o (t)} \\ [equation (23) ] & + K_{r_{i} - t, r_{i}}^{D} (x ∣ a, b) - O (log r_{1}) \\ [η < dim (a, b)] & = & η \cdot (r_{i - 1}) + η \cdot (t - r_{i - 1}) - o (t) + K_{r_{i} - t, r_{i}}^{D} (x ∣ a, b) - O (log r_{1}) \\ = & η t - o (t) + K_{r_{i} - t, r_{i}}^{D} (x ∣ a, b) - O (log r_{1}) \\ [inequality (3) ] & ⩾ & η t - o (t) + K_{r_{i} - t}^{D, a, b} (x) - O (log r_{k}) \\ [Lemma 14 (5)] & = & η t - o (t) + K_{r_{i} - t}^{a, b} (x) - O (log r_{k}) \\ [equation (19) ] & = & η t - o (t) + (r_{i} - t) - O (log r_{k}) \\ [δ = 1 - η] & = & η t - o (t) + (η + δ) (r_{i} - t) - o (r_{k}) \\ [t ⩽ r_{i}] & = & η r_{i} + δ (r_{i} - t) - o (r_{k}) . \end{array}$ We conclude that $K_{r_{i}}^{D} (u, v) ⩾ (η - ε) r_{i} + δ (r_{i} - t)$ holds for all $1 ⩽ i ⩽ k$ whenever each $r_{i} = ⌈ i s h_{j} ⌉$ is large enough, i.e., for all sufficiently large j.

We have shown that all three conditions of Lemma 13 are satisfied, so we may apply it to get that, for all $r \in (s h_{j}, m h_{j}]$ , $\begin{array}{l} [inequality (2) ] & K_{r} (x, a x + b) & ⩾ K_{r}^{D} (x, a x + b) - O (1) \\ [Lemma 13 ] & ⩾ K_{r}^{D} (a, b, x) - k (K (ε) + K (η) + \frac{4 ε}{δ} r) - O (log r) \\ [ε and η are constants] & ⩾ K_{r}^{D} (a, b, x) - \frac{4 ε k}{δ} r - O (log r) \\ [Lemma 2 ] & = K_{r}^{D} (a, b) + K_{r}^{D} (x ∣ a, b) - \frac{4 k ε}{δ} r - O (log r) \\ [equation (3) ] & ⩾ K_{r}^{D} (a, b) + K_{r}^{D, a, b} (x) - \frac{4 k ε}{δ} r - O (log r) \\ [Lemma 14 (5)] & = K_{r}^{D} (a, b) + K_{r}^{a, b} (x) - \frac{4 k ε}{δ} r - O (log r) \\ [definition of dim] & ⩾ dim (a, b) r + {dim}^{a, b} (x) r - \frac{4 k ε}{δ} r - o (r) . \end{array}$ Since we chose $η < dim (a, b)$ and equation (20) tells us that ${dim}^{a, b} (x) = s$ , we have shown, for all sufficiently large j and all $r \in (s h_{j}, m h_{j}]$ , that $\begin{matrix} (24) & K_{r} (x, a x + b) ⩾ η r + s r - \frac{4 k ε}{δ} r - o (r) . \end{matrix}$

To complete the proof, we consider the case where $r \in [m h_{j}, s h_{j + 1})$ . For this case, we directly apply a technique from [28] to give a lower bound on $K_{r} (x, a x + b)$ . Equation (18) says that $x [r] = y [r]$ for all $r \in [m h_{j}, s h_{j + 1}) \subseteq [h_{j}, s h_{j})$ , so for all r in this range, $\begin{matrix} (25) & K_{r, h_{j}}^{a, b} (x ∣ x) = r - h_{j} + o (r) . \end{matrix}$ Thus, $\begin{array}{l} [Lemma 2 ] & K_{r}^{a, b} (x) & = K_{r, h_{j}}^{a, b} (x ∣ x) + K_{h_{j}} (x) + o (r) \\ [equation (25) ] & = r - h_{j} + K_{h_{j}}^{a, b} (x) + o (r) \\ [definition of dim] & ⩾ r - h_{j} + {dim}^{a, b} (x) h_{j} - o (r) \\ [equation (20) ] & = r - h_{j} + s h_{j} - o (r) . \end{array}$ Now, $r ⩾ m h_{j} = \frac{s - 1}{η - 1} h_{j}$ implies that $r - h_{j} - s h_{j} ⩾ η r$ , so for all $r \in [m h_{j}, s h_{j + 1})$ , we have $\begin{matrix} (26) & K_{r}^{a, b} (x) ⩾ η r - o (r) . \end{matrix}$

Let $η^{'} \in Q \cap [0, s)$ , $δ^{'} = s - η^{'}$ , and $ε^{'} > 0$ . Using Lemma 10, construct the oracle $A = A (r, (a, b), η^{'})$ . We now show that the conditions of Lemma 9 are satisfied. Condition (1) holds for all sufficiently large r. Condition (2) holds by the construction of Lemma 10.

To see that condition (3) holds, let $(u, v) \in B_{1} (a, b) ∖ B_{2^{- r}} (a, b)$ and $t = - log ‖ (a, b) - (u, v) ‖ \in (0, r]$ . Then, $\begin{array}{l} [Lemma 7 , relative to A] & K_{r}^{A} (u, v) & ⩾ K_{t}^{A} (a, b) + K_{r - t}^{A, a, b} (x) - O (log r) \\ [Lemma 10 (1)] & ⩾ min {η^{'} r, K_{t} (a, b)} + K_{r - t}^{A, a, b} (x) - O (log r) \\ [Lemma 10 (3)] & ⩾ min {η^{'} r, K_{t} (a, b)} + K_{r - t}^{a, b} (x) - O (log r) \\ [definition of dim] & ⩾ min {η^{'} r, K_{t} (a, b)} + {dim}^{a, b} (x) (r - t) - o (r) \\ [equation (20) ] & = min {η^{'} r, K_{t} (a, b)} + s \cdot (r - t) - o (r) \\ [δ^{'} = s - η^{'}] & = min {η^{'} r, K_{t} (a, b)} + (η^{'} + δ^{'}) (r - t) - o (r) \\ [η < dim (a, b)] & ⩾ min {η^{'} r, η^{'} t - o (t)} + (η^{'} + δ^{'}) (r - t) - O (log r) \\ [t ⩽ r] & = η^{'} t + (η^{'} + δ^{'}) (r - t) - o (r) \\ = (η^{'} - ε^{'}) r + δ^{'} (r - t), \end{array}$ for all sufficiently large r.

Therefore we can apply Lemma 9, which yields $\begin{array}{l} [inequality (2) ] & K_{r} (x, a x + b) & ⩾ K_{r}^{A} (x, a x + b) - O (1) \\ [Lemma 9 ] & ⩾ K_{r}^{A} (a, b, x) - \frac{4 ε^{'}}{δ^{'}} r - K (ε^{'}) - K (η^{'}) - O (log r) \\ [ε^{'} and η^{'} are constants] & ⩾ K_{r}^{A} (a, b, x) - \frac{4 ε^{'}}{δ^{'}} r - O (log r) \\ [Lemma 2 ] & = K_{r}^{A} (a, b) + K_{r}^{A} (x ∣ a, b) - \frac{4 ε^{'}}{δ^{'}} r - O (log r) \\ [Lemma 2 ] & = K_{r}^{A} (a, b) + K_{r}^{A} (x ∣ a, b) - \frac{4 ε^{'}}{δ^{'}} r - O (log r) \\ [inequality (3) ] & ⩾ K_{r}^{A} (a, b) + K_{r}^{A, a, b} (x) - \frac{4 ε^{'}}{δ^{'}} r - O (log r) \\ [Lemma 10 (3)] & ⩾ K_{r}^{A} (a, b) + K_{r}^{a, b} (x) - \frac{4 ε^{'}}{δ^{'}} r - O (log r) \\ [inequality (26) ] & ⩾ K_{r}^{A} (a, b) + η r - \frac{4 ε^{'}}{δ^{'}} r - o (r) \\ [Lemma 10 (1)] & ⩾ η^{'} r + η r - \frac{4 ε^{'}}{δ^{'}} r - o (r) \\ [δ^{'} = s - η^{'}] & = η^{'} r + η r - \frac{4 ε^{'}}{s - η^{'}} r - o (r) . \end{array}$ Since $η^{'}$ and $ε^{'}$ may be chosen arbitrarily close to s and 0, respectively, we conclude that, for all sufficiently large j and every $r \in [m h_{j}, s h_{j + 1})$ , $\begin{matrix} K_{r} (x, a x + b) ⩾ s r + η r - ε r - o (r) . \end{matrix}$ Combining this with inequality (24), we have, for all sufficiently large j and every $r \in [s h_{j}, s h_{j + 1})$ , $\begin{matrix} (27) & K_{r} (x, a x + b) ⩾ s r + η r - \frac{4 k ε}{δ} r - o (r), \end{matrix}$ Therefore, $\begin{array}{l} [definition of dim] & dim (x, a x + b) & = \underset{r \to \infty}{lim inf} \frac{K_{r} (x, a x + b)}{r} \\ [inequality (27) ] & ⩾ \underset{r \to \infty}{lim inf} \frac{s r + η r - \frac{4 k ε}{δ} r - o (r)}{r} \\ = s + η - \frac{4 k ε}{δ} . \end{array}$ Since η and ε can be chosen arbitrarily close to 0, the conclusion follows. □

4.2. Second main theorem

Our second main theorem concerts the case where $dim (a, b) ⩾ 1$ . In this case, where the limit ${lim}_{r \to \infty} K_{r} (a, b) / r$ might not exist, we place bounds on the effective Hausdorff dimension of our constructed point instead of determining its exact value.

Theorem 16.
Let $a, b \in R$ such that $dim (a, b) ⩾ 1$ . Then for every $s \in [\frac{1}{2}, 1]$ there is a point $x \in R$ such that $dim (x, a x + b) \in [\frac{3}{2} + s - \frac{1}{2 s}, s + 1]$ .

For the remainder of this section, fix a slope-intercept pair $(a, b) \in R$ such that $dim (a, b) ⩾ 1$ and a value $s \in [\frac{1}{2}, 1]$ .

We now construct a value $x \in R$ such that the conclusion of Theorem 16 holds for $(x, a x + b)$ . As in the proof of Theorem 15, let $y = (y [0], y [1], y [2], \dots)$ be random relative to $(a, b)$ , and define the sequence ${h_{j}}_{j \in N}$ of natural numbers by $h_{0} = 1$ and, for every $j > 0$ , $\begin{matrix} (28) & h_{j} = min {h ⩾ 2^{h_{j - 1}} : K_{h} (a, b) ⩽ (dim (a, b) + \frac{1}{j}) h} . \end{matrix}$ For every $r \in N$ , let $\begin{array}{l} x [r] = \{\begin{matrix} 0 & if r \in (h_{j}, h_{j} / s] for some j \in N \\ y [r] & otherwise. \end{matrix} \end{array}$ Define $x \in [0, 1]$ to be the real number with this binary expansion. Note that we defined x so that its information density is essentially maximal when the information density of $(a, b)$ is minimal. That is, $\begin{matrix} K_{h_{j}} (x) = h_{j} + O (log h_{j}), \end{matrix}$ where $h_{j}$ is a precision such that $K_{h_{j}} (a, b)$ is approximately $dim (a, b) h_{j}$ . Furthermore, for any fixed j, all but $O (log h_{j})$ bits of x prior to precision $h_{j}$ are bits from y that are random relative to $(a, b)$ . Thus, for all $r ⩽ h_{j}$ , $\begin{matrix} (29) & K_{r}^{a, b} (x) = r - O (log h_{j}) . \end{matrix}$ Observe also that even when $r ⩾ h_{j}$ , the binary expansion of x up to precision r consists of $h_{j}$ bits, all but $O (log h_{j})$ of which are from y, followed by at most $h_{j} / s - h_{j}$ zeros, and then possibly more bits from y. Thus, at least $r - h_{j} \cdot (1 / s - 1) - O (log r)$ bits of x up to precision r are from y. This implies that for all $r \in N$ and all j such that $r ⩾ h_{j}$ , $\begin{matrix} (30) & K_{r}^{a, b} (x) ⩾ r - h_{j} \cdot (1 / s - 1) - O (log r) ⩾ s r - O (log r) . \end{matrix}$

To prove Theorem 16, it will suffice to show that, for every $ε > 0$ , $\begin{matrix} (\frac{3}{2} + s - \frac{1}{2 s}) r - ε r - o (r) ⩽ K_{r} (x, a x + b) ⩽ (1 + s) r + o (r) . \end{matrix}$ The proof of this naturally splits into three parts. The first, Lemma 17 below, controls the upper bound. In order to control the lower bound, we consider the cases that $r \in (h_{j}, 2 h_{j}]$ and $(2 h_{j}, h_{j + 1}]$ separately, in Lemmas 18 and 19.

The key to the proof of Lemma 18 is our choice of the precision parameters $h_{j}$ . Since $(a, b)$ is approximately minimal at $h_{j}$ and $dim (a, b) ⩾ 1$ , it must require a relatively large amount of information to get from a precision- $h_{j}$ approximation of $(a, b)$ to a precision-r approximation of $(a, b)$ , for $h_{j} < r ⩽ 2 h_{j}$ . In other words, the conditional complexity $K_{r, h_{j}} (a, b ∣ a, b)$ cannot be much smaller than $r - h_{j}$ when $r \in (h_{j}, 2 h_{j}]$ . This implies that the oracle described by Lemma 14 is able to decrease the complexity of $(a, b)$ at precisions $h_{j}$ and r in a useful way: Given a parameter η, we can construct an oracle that will cause the information density of $(a, b)$ to be approximately η, both at precision $h_{j}$ and at precision $r \in (h_{j}, 2 h_{j}]$ . This will allow us to invoke Lemma 13, relative to this oracle D.

Lemma 19, which concerns the case where $r \in (2 h_{j}, h_{j + 1}]$ , essentially follows the proof of the main theorem of [28]. In this case, we rely on the fact that the bits of x’s binary expansion are random after precision $h_{j} / s$ . We construct the oracle D given by Lemma 10 to decrease the complexity of $(a, b)$ to $s r$ , then appeal to Lemma 9.
Lemma 17.
For this construction of x, $dim (x, a x + b) ⩽ 1 + s$ .
Proof.
For every $j \in N$ , $\begin{array}{l} [Lemma 2 ] & K_{h_{j} / s} (x, a x + b) & = K_{h_{j} / s} (x) + K_{h_{j} / s} (a x + b ∣ x) + O (log (h_{j} / s)) \\ [definition of x] & = K_{h_{j}} (x) + K_{h_{j} / s} (a x + b ∣ x) + O (log h_{j}) \\ (31) & ⩽ h_{j} + h_{j} / s + O (log h_{j}), \end{array}$ since the complexity of any real number at precision $r \in N$ is at most $r + O (log r)$ . Therefore, $\begin{array}{l} [definition of dim] & dim (x, a x + b) & = \underset{r \to \infty}{lim inf} \frac{K_{r} (x, a x + b)}{r} \\ [definition of lim inf] & ⩽ \underset{j \to \infty}{lim inf} \frac{K_{h_{j} / s} (x, a x + b)}{h_{j} / s} \\ [inequality (31) ] & ⩽ \underset{j \to \infty}{lim inf} \frac{h_{j} + h_{j} / s + O (log h_{j})}{h_{j} / s} \\ = s + 1 . \end{array}$ □
Lemma 18.
For all $ε > 0$ , all sufficiently large j, and all $r \in (h_{j}, 2 h_{j}]$ , $\begin{matrix} K_{r} (x, a x + b) ⩾ (1 + s) r - ε r - o (r) . \end{matrix}$
Proof.
Let $η, δ, ζ \in Q$ such that $η \in [1 - ε / 2, 1)$ , $δ = 1 - η > 0$ , and $ζ \in (0, δ ε / 16)$ . Let $j, r \in N$ be such that j is sufficiently large and $r \in (h_{j}, 2 h_{j}]$ , where $h_{j}$ is defined as in (28).

Let $D = D (h_{j}, r, (a, b), η)$ be the oracle defined in Lemma 14. Recall that the purpose of this oracle is to potentially reduce the complexity of $(a, b)$ at precisions $h_{j}$ and r.

From the choice of precision parameter $h_{j}$ , we have $\begin{array}{l} [Lemma 2 ] & K_{r, h_{j}} (a, b ∣ a, b) & = K_{r} (a, b) - K_{h_{j}} (a, b) + O (log r) \\ [equation (28) ] & ⩾ K_{r} (a, b) - dim (a, b) h_{j} - h_{j} / j - O (log r) \\ [h_{j} / j = o (r)] & = K_{r} (a, b) - dim (a, b) h_{j} - o (r) \\ [definition of dim] & ⩾ dim (a, b) r - dim (a, b) h_{j} - o (r) \\ [η < 1 ⩽ dim (a, b)] & ⩾ η \cdot (r - h_{j}) - o (r) . \end{array}$ Property (1) of Lemma 14 gives $\begin{matrix} K_{r}^{D} (a, b) = η h_{j} + min {η \cdot (r - h_{j}), K_{r, h_{j}} (a, b ∣ a, b)} + O (log r), \end{matrix}$ which, combined with the inequality above, yields $\begin{matrix} (32) & K_{r}^{D} (a, b) = η r + o (r) . \end{matrix}$

We now show that the conditions of Lemma 13 are satisfied, for $k = 2$ , $r_{1} = h_{j}$ , and $r_{2} = r$ . Condition (1) holds for all sufficiently large j.

Property (2) of Lemma 14 gives $\begin{matrix} K_{h_{j}}^{D} (a, b) ⩽ η h_{j} + O (log r) = η h_{j} + O (log h_{j}), \end{matrix}$ since $r \in (h_{j}, 2 h_{j}]$ . This implies that condition (2) of Lemma 13 holds for $i = 1$ whenever the $O (log h_{j})$ term is dominated by $ε h_{j}$ , i.e., for all sufficiently large j. Similarly, (32) shows that condition (2) holds for $i = 2$ and all sufficiently large j.

To see that condition (3) of Lemma 13 is satisfied, we first consider the $i = 1$ case, for $r_{1} = h_{j}$ . Let $(u, v) \in B_{1} (a, b)$ such that $u x + v = a x + b$ and $t = - log ‖ (a, b) - (u, v) ‖ ⩽ h_{j}$ . Then by our construction of x, $\begin{array}{l} [Lemma 7 ] & K_{h_{j}}^{D} (u, v) & ⩾ K_{t}^{D} (a, b) + K_{h_{j} - t, h_{j}}^{D} (x ∣ a, b) - O (log h_{j}) \\ [Lemma 14 (2)] & = min {η h_{j}, K_{t} (a, b)} + K_{h_{j} - t, h_{j}}^{D} (x ∣ a, b) - O (log r) \\ [inequality (3) ] & ⩾ min {η h_{j}, K_{t} (a, b)} + K_{h_{j} - t}^{D, a, b} (x) - O (log r) \\ [Lemma 14 (5)] & = min {η h_{j}, K_{t} (a, b)} + K_{h_{j} - t}^{a, b} (x) - O (log r) \\ [inequality (29) ] & ⩾ min {η h_{j}, K_{t} (a, b)} + (h_{j} - t) - O (log r) \\ [definition of dim] & = min {η h_{j}, dim (a, b) t - o (t)} + (h_{j} - t) - O (log r) \\ [η < 1 ⩽ dim (a, b)] & ⩾ min {η h_{j}, η t - o (t)} + (h_{j} - t) - O (log r) \\ [t ⩽ h_{j}] & ⩾ η t - o (t) + (h_{j} - t) - O (log r) \\ [δ = 1 - η] & = η h_{j} + δ \cdot (h_{j} - t) - o (r) . \end{array}$ We now consider the $i = 2$ case, for $r_{2} = r$ . Let $(u, v) \in B_{h_{j}} (a, b)$ such that $u x + v = a x + b$ and $t = - log ‖ (a, b) - (u, v) ‖ ⩽ r$ . Observe that since $t ⩾ h_{j}$ and $r \in (h_{j}, 2 h_{j}]$ , we have $r - t ⩽ h_{j}$ . Therefore, $\begin{array}{l} [Lemma 7 ] & K_{r}^{D} (u, v) ⩾ & K_{t}^{D} (a, b) + K_{r - t, r}^{D} (x ∣ a, b) - O (log r) \\ ⩾ & K_{h_{j}}^{D} (a, b) + min {η \cdot (t - h_{j}), K_{t, h_{j}} (a, b ∣ a, b)} \\ [Lemma 14 (3)] & + K_{r - t, r}^{D} (x ∣ a, b) - O (log h_{j}) \\ [Lemma 14 (1)] & = & η h_{j} + min {η \cdot (t - h_{j}), K_{t, h_{j}} (a, b ∣ a, b)} + K_{r - t, r}^{D} (x ∣ a, b) - O (log h_{j}) \\ [Lemma 2 ] & = & η h_{j} + min {η \cdot (t - h_{j}), K_{t} (a, b) - K_{h_{j}} (a, b)} + K_{r - t, r}^{D} (x ∣ a, b) - O (log h_{j}) \\ ⩾ & η h_{j} + min {η \cdot (t - h_{j}), dim (a, b) t - o (t) - K_{h_{j}} (a, b)} \\ [definition of dim] & + K_{r - t, r}^{D} (x ∣ a, b) - O (log h_{j}) \\ ⩾ & η h_{j} + min {η \cdot (t - h_{j}), dim (a, b) t - o (t) - (dim (a, b) - 1 / j) h_{j}} \\ [equation (28) ] & + K_{r - t, r}^{D} (x ∣ a, b) - O (log h_{j}) \\ [t ⩾ h_{j}] & ⩾ & η h_{j} + min {η \cdot (t - h_{j}), dim (a, b) (t - h_{j})} + K_{r - t, r}^{D} (x ∣ a, b) - o (t) \\ [η < 1 ⩽ dim (a, b)] & ⩾ & η h_{j} + η \cdot (t - h_{j}) + K_{r - t, r}^{D} (x ∣ a, b) - o (t) \\ [inequality (3) , t ⩽ r] & ⩾ & η t + K_{r - t}^{D, a, b} (x) - o (r) \\ [Lemma 14 (5)] & = & η t + K_{r - t}^{a, b} (x) - o (r) \\ [inequality (29) ] & ⩾ & η t + (r - t) - o (r) \\ [δ = 1 - η] & = & η t + (η + δ) (r - t) - o (r) \\ = & η r + δ \cdot (r - t) - o (r) . \end{array}$ Since $ζ > 0$ , we have for both $i = 1$ and $i = 2$ that $\begin{matrix} K_{r_{i}}^{D} (u, v) ⩾ (η - ζ) r_{i} + δ \cdot (r_{i} - t) \end{matrix}$ for all sufficiently large j, so condition (3) is satisfied.

As all three conditions of Lemma 13 are satisfied, we can apply it. Thus, for all $r \in (h_{j}, 2 h_{j}]$ , $\begin{array}{l} [inequality (2) ] & K_{r} (x, a x + b) & ⩾ K_{r}^{D} (x, a x + b) - O (1) \\ [Lemma 13 ] & ⩾ K_{r}^{D} (a, b, x) - 2 (K (ε) + K (η) + \frac{4 ζ}{δ} r + O (log r)) - O (1) \\ [ε and η are constants] & ⩾ K_{r}^{D} (a, b, x) - \frac{8 ζ}{δ} r - O (log r) \\ [Lemma 2 ] & = K_{r}^{D} (a, b) + K_{r}^{D} (x ∣ a, b) - \frac{8 ζ}{δ} r - O (log r) \\ [equation (32) ] & = η r + K_{r}^{D} (x ∣ a, b) - \frac{8 ζ}{δ} r - o (r) \\ [inequality (3) ] & = η r + K_{r}^{D, a, b} (x) - \frac{8 ζ}{δ} r - o (r) \\ [Lemma 14 (5)] & = η r + K_{r}^{a, b} (x) - \frac{8 ζ}{δ} r - o (r) \\ [inequality (30) ] & ⩾ η r + s r - \frac{8 ζ}{δ} r - o (r) \\ [ζ < δ ε / 16] & ⩾ η r + s r - \frac{ε}{2} r - o (r) \\ [η < 1 - ε / 2] & = (1 + s) r - ε r - o (r), \end{array}$ and the proof is complete. □

To complete the proof of Theorem 16, we must lower bound the complexity of $(x, a x + b)$ for precisions in the range $(2 h_{j}, h_{j + 1}]$ .
Lemma 19.
For every $ε > 0$ and all sufficiently large j, $\begin{matrix} K_{r} (x, a x + b) ⩾ (\frac{3}{2} + s - \frac{1}{2 s} - ε) r - O (log r), \end{matrix}$ for every $r \in (2 h_{j}, h_{j + 1}]$ .
Proof.
Let $η, δ, ζ \in Q$ be such that $η \in [s - ε / 2, s)$ , $δ = s - η$ , and $ζ \in (0, δ ε / 8)$ . Let $j, r \in N$ be such that j is sufficiently large and $r \in (2 h_{j}, h_{j + 1}]$ , where $h_{j}$ is defined as in (28).

Let $D = D (r, (a, b), η)$ be the oracle defined in Lemma 10. We now show that the conditions of Lemma 9 are satisfied. Condition (1) of Lemma 9 holds for sufficiently large j. By Lemma 10, $\begin{matrix} K_{r}^{D} (a, b) ⩽ η r + O (log r), \end{matrix}$ and therefore the condition (2) of Lemma 9 is satisfied.

To see that condition (3) of Lemma 9 is satisfied, let $(u, v) \in B_{1} (a, b)$ such that $u x + v = a x + b$ and $t = - log ‖ (a, b) - (u, v) ‖ ⩽ r$ . Then, by Lemmas 7 and 10 and our construction of x, $\begin{array}{l} [Lemma 7 ] & K_{r}^{D} (u, v) & ⩾ K_{t}^{D} (a, b) + K_{r - t, r}^{D} (x ∣ a, b) - O (log r) \\ [Lemma 10 (1)] & = min {η r, K_{t} (a, b)} + K_{r - t}^{D} (x ∣ a, b) - O (log r) \\ [inequality (3) ] & ⩾ min {η r, K_{t} (a, b)} + K_{r - t}^{D, a, b} (x) - O (log r) \\ [Lemma 10 (3)] & = min {η r, K_{t} (a, b)} + K_{r - t}^{a, b} (x) - O (log r) \\ [inequality (30) ] & ⩾ min {η r, K_{t} (a, b)} + s \cdot (r - t) - o (r) \\ [definition of dim] & ⩾ min {η r, dim (a, b) t - o (t)} + s \cdot (r - t) - o (r) \\ [η < 1 ⩽ dim (a, b)] & ⩾ min {η r, η t - o (t)} + s \cdot (r - t) - o (r) \\ [t ⩽ r] & ⩾ η t - s \cdot (r - t) - o (r) \\ [δ = s - η] & = η t - (η + δ) (r - t) - o (r) \\ [ζ > 0] & ⩾ (η - ζ) r + δ (r - t), \end{array}$ for all sufficiently large j. Thus we may apply Lemma 9, which shows that $\begin{array}{l} [inequality (2) ] & K_{r} (x, a x + b) & ⩾ K_{r}^{D} (x, a x + b) - O (1) \\ [Lemma 9 ] & ⩾ K_{r}^{D} (a, b, x) - \frac{4 ζ}{δ} r - K (ζ) - K (η) - O (log r) \\ [ζ and η are constants] & ⩾ K_{r}^{D} (a, b, x) - \frac{4 ζ}{δ} r - O (log r) \\ [Lemma 2 ] & = K_{r}^{D} (a, b) + K_{r}^{D} (x ∣ a, b) - \frac{4 ζ}{δ} r - O (log r) \\ [Lemma 10 (1)] & = η r + K_{r}^{D} (x ∣ a, b) - \frac{4 ζ}{δ} r - O (log r) \\ [inequality (3) ] & ⩾ η r + K_{r}^{D, a, b} (x) - \frac{4 ζ}{δ} r - O (log r) \\ [Lemma 10 (3)] & = η r + K_{r}^{a, b} (x) - \frac{4 ζ}{δ} r - O (log r) \\ [inequality (30) ] & ⩾ η r + r - h_{j} \cdot (\frac{1}{s} - 1) - \frac{4 ζ}{δ} r - O (log r) \\ [ζ < δ ε / 8] & ⩾ η r + r - h_{j} \cdot (\frac{1}{s} - 1) - \frac{ε}{2} r - O (log r) \\ [η ⩾ s - ε / 2, r ⩽ 2 h_{j}] & ⩾ (s - \frac{ε}{2}) r + r - \frac{r}{2} \cdot (\frac{1}{s} - 1) - \frac{ε}{2} r - O (log r) \\ = (s + \frac{3}{2} - \frac{1}{2 s} - ε) r - O (log r), \end{array}$ and the proof is complete. □

The conclusion of Theorem 16 follows immediately from Lemmas 17, 18, and 19. Corollary 20.
Let $L_{a, b}$ be any line in $R^{2}$ . Then the dimension spectrum $sp (L_{a, b})$ is infinite.
Proof.
Let $(a, b) \in R^{2}$ . We first consider the case that $dim (a, b) < 1$ . For each $s \in [dim (a, b), 1]$ , select an $x \in R$ according to Observation 5. Then $Dim (x ∣ a, b) = dim (x ∣ a, b) = {dim}^{a, b} (x) = s ⩾ dim (a, b)$ , so by Theorem 8, $\begin{matrix} dim (x, a x + b) ⩾ dim (x ∣ a, b) + dim (a, b) = s + dim (a, b), \end{matrix}$ and by (5) and (1), $\begin{matrix} dim (x, a x + b) ⩽ dim (a, b, x) ⩽ Dim (x ∣ a, b) + dim (a, b) = s + dim (a, b) . \end{matrix}$ Since $s \in (dim (a, b), 1]$ was arbitrary, this implies that $[2 dim (a, b), dim (a, b) + 1] \subseteq sp (L_{a, b})$ .

Otherwise, $dim (a, b) ⩾ 1$ . Then by Theorem 16, for every $s \in [\frac{1}{2}, 1]$ , there is a point x such that $\begin{matrix} dim (x, a x + b) \in [\frac{3}{2} + s - \frac{1}{2 s}, s + 1] . \end{matrix}$ For each positive integer k, define $s_{k} = 1 - 2^{- k} \in [\frac{1}{2}, 1]$ . Then $s_{k} + 1 < \frac{3}{2} + s_{k + 1} - \frac{1}{2 s_{k + 1}}$ , so $\begin{matrix} {[\frac{3}{2} + s_{k} - \frac{1}{2 s_{k}}, s_{k} + 1] : k ⩾ 1} \end{matrix}$ is a infinite collection of disjoint intervals, and the dimension spectrum $sp (L_{a, b})$ contains a value in each of these intervals. □

5. Future directions

We have made progress in the broader program of describing the dimension spectra of lines in Euclidean spaces. We highlight three specific directions for further progress. First, it is natural to ask whether the condition on $(a, b)$ may be dropped from the statement our main theorem: Does Theorem 15 hold for arbitrary $a, b \in R$ ?

Second, the dimension spectrum of a line $L_{a, b} \subseteq R^{2}$ may properly contain the length-1 interval described in our main theorem, even when $dim (a, b) = Dim (a, b)$ . If $a \in R$ is random and $b = 0$ , for example, then $sp (L_{a, b}) = {0} \cup [1, 2]$ . It is less clear whether this set of “exceptional values” in $sp (L_{a, b})$ might itself contain an interval, or even be infinite. How large (in the sense of cardinality, dimension, or measure) may $sp (L_{a, b}) \cap [0, min {1, dim (a, b)})$ be?

Finally, any non-trivial statement about the dimension spectra of lines in higher-dimensional Euclidean spaces would be very interesting. Indeed, an n-dimensional version of Theorem 8 (i.e., one in which $a, b \in R^{n - 1}$ , for all $n ⩾ 2$ ) would, via the point-to-set principle for Hausdorff dimension [25], affirm the famous Kakeya conjecture and is therefore likely difficult. The additional hypothesis of Theorem 15 might make it more conducive to such an extension.

References

47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21–24 October 2006, Berkeley, California, USA, Proceedings, in: FOCS, IEEE Computer Society, 2006. ISBN 0-7695-2720-5.

K.B.

Athreya,

J.M.

Hitchcock,

J.H.

Lutz and

Mayordomo, Effective strong dimension in algorithmic information and computational complexity, SIAM J. Comput. 37(3) (2007), 671–705. doi:10.1137/S0097539703446912.

Case and

J.H.

Lutz, Mutual dimension, ACM Transactions on Computation Theory 7(3) (2015), 12. doi:10.1145/2786566.

Case and

J.H.

Lutz, Mutual dimension and random sequences, in: Mathematical Foundations of Computer Science 2015 – 40th International Symposium, MFCS 2015, Proceedings, Part II, Milan, Italy, August 24–28, 2015,

G.F.

Italiano,

Pighizzini and

Sannella, eds, Lecture Notes in Computer Science, Vol. 9235, Springer, 2015, pp. 199–210.

G.J.

Chaitin, On the length of programs for computing finite binary sequences, J. ACM 13(4) (1966), 547–569. doi:10.1145/321356.321363.

G.J.

Chaitin, On the length of programs for computing finite binary sequences: Statistical considerations, J. ACM 16(1) (1969), 145–159. doi:10.1145/321495.321506.

T.R.

Cover and

J.A.

Thomas, Elements of Information Theory, 2nd edn, Wiley, 2006.

R.O.

Davies, Some remarks on the Kakeya problem, Proceedings of the Cambridge Philosophical Society 69 (1971), 417–421. doi:10.1017/S0305004100046867.

Dougherty,

Lutz,

R.D.

Mauldin and

Teutsch, Translating the Cantor set by a random real, Transactions of the American Mathematical Society 366(6) (2014), 3027–3041. doi:10.1090/S0002-9947-2014-05912-6.

10.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010. ISBN 0387955674.

11.

Falconer, Fractal Geometry: Mathematical Foundations and Applications, 3rd edn, Wiley, 2014.

12.

K.J.

Falconer, The Geometry of Fractal Sets, Cambridge University Press, 1985.

13.

Gács, On the symmetry of algorithmic information, Soviet Mathematics Doklady 15 (1974), 1477–1480.

14.

Gu,

J.H.

Lutz and

Mayordomo, Points on Computable Curves, CoRR abs/cs/0512042, 2005.

15.

Gu,

J.H.

Lutz,

Mayordomo and

Moser, Dimension spectra of random subfractals of self-similar fractals, Ann. Pure Appl. Logic 165(11) (2014), 1707–1726. doi:10.1016/j.apal.2014.07.001.

16.

J.M.

Hitchcock, Correspondence principles for effective dimensions, Theory of Computing Systems 38(5) (2005), 559–571. doi:10.1007/s00224-004-1122-1.

17.

G.F.

Italiano,

Pighizzini and

Sannella (eds), Mathematical Foundations of Computer Science 2015 – 40th International Symposium, Proceedings, Part II, MFCS 2015, Milan, Italy, August 24–28, 2015, Lecture Notes in Computer Science, Vol. 9235, Springer, 2015.

18.

Katz and

Tao, Recent progress on the Kakeya conjecture, in: Proceedings of the 6th International Conference on Harmonic Analysis and Partial Differential Equations, Publicacions Matematiques, 2002, pp. 161–180.

19.

N.H.

Katz and

Tao, Some connections between Falconer’s distance set conjecture and sets of Furstenburg type, New York J. Math 7 (2001), 149–187.

20.

L.A.

Levin, On the notion of a random sequence, Soviet Math Dokl. 14(5) (1973), 1413–1416.

21.

Li and

P.M.B.

Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Springer, 2008, 9780387339986. ISBN 0387339981.

22.

J.H.

Lutz, The dimensions of individual strings and sequences, Inf. Comput. 187(1) (2003), 49–79. doi:10.1016/S0890-5401(03)00187-1.

23.

J.H.

Lutz, Dimension in complexity classes, SIAM J. Comput. 32(5) (2003), 1236–1259. doi:10.1137/S0097539701417723.

24.

J.H.

Lutz and

Lutz, Lines missing every random point, Computability 4(2) (2015), 85–102. doi:10.3233/COM-150038.

25.

J.H.

Lutz and

Lutz, Algorithmic information, plane Kakeya sets, and conditional dimension, ACM Trans. Comput. Theory 10(2) (2018), 7:1–7:22. doi:10.1145/3201783.

26.

J.H.

Lutz and

Mayordomo, Dimensions of points in self-similar fractals, SIAM J. Comput. 38(3) (2008), 1080–1112. doi:10.1137/070684689.

27.

J.H.

Lutz and

Weihrauch, Connectivity properties of dimension level sets, Mathematical Logic Quarterly 54 (2008), 483–491. doi:10.1002/malq.200710060.

28.

Lutz and

D.M.

Stull, Bounding the Dimension of Points on a Line, Information and Computation 275 (2020).

29.

Mattila, Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability, Cambridge University Press, 1999.

30.

Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inf. Process. Lett. 84(1) (2002), 1–3. doi:10.1016/S0020-0190(02)00343-5.

31.

Mayordomo, Effective fractal dimension in algorithmic information theory, in: New Computational Paradigms: Changing Conceptions of What Is Computable,

S.B.

Cooper,

Löwe and

Sorbi, eds, Springer, New York, 2008, pp. 259–285. doi:10.1007/978-0-387-68546-5_12.

32.

Mayordomo, Effective dimension in some general metric spaces, in: Proceedings 8th International Workshop on Developments in Computational Models, DCM 2012, Cambridge, United Kingdom, 17 June 2012, 2012, pp. 67–75.

33.

J.S.

Miller, “Open Questions” section of personal webpage, Retrieved October 30 (2016).

34.

Molter and

Rela, Furstenberg sets for a fractal set of directions, Proc. Amer. Math. Soc. 140 (2012), 2753–2765. doi:10.1090/S0002-9939-2011-11111-0.

35.

Nies, Computability and Randomness, Oxford University Press, Inc., New York, NY, USA, 2009, 9780199230761. ISBN 0199230765.

36.

Reimann, Effectively closed classes of measures and randomness, Annals of Pure and Applied Logic 156(1) (2008). doi:10.1016/j.apal.2008.06.015.

37.

Rela, Refined size estimates for Furstenberg sets via Hausdorff measures: A survey of some recent results, in: Concrete Operators, Spectral Theory, Operators in Harmonic Analysis and Approximation, Springer, 2014, pp. 421–454. doi:10.1007/978-3-0348-0648-0_27.

38.

R.J.

Solomonoff, A formal theory of inductive inference, Information and Control 7(1–2) (1964), 1–22, 224–254. doi:10.1016/S0019-9958(64)90131-7.

39.

Tao, From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE, Notices Amer. Math. Soc 48 (2000), 294–303.

40.

Turetsky, Connectedness properties of dimension level sets, Theor. Comput. Sci. 412(29) (2011), 3598–3603. doi:10.1016/j.tcs.2011.03.006.

41.

Weihrauch, Computable Analysis: An Introduction, Springer, 2000.

42.

L.B.

Westrick, Computability in Ordinal Ranks and Symbolic Dynamics, PhD thesis, University of California, Berkeley, 2014.

43.

Wolff, Recent work connected with the Kakeya problem, Prospects in Mathematics (1999), 129–162.