The Dimension Spectrum Conjecture for Planar Lines

D. M. Stull
Department of Computer Science
Northwestern University
[email protected]

Abstract

Let $L_{a,b}$ be a line in the Euclidean plane with slope $a$ and intercept $b$ . The dimension spectrum $\operatorname{sp}(L_{a,b})$ is the set of all effective dimensions of individual points on $L_{a,b}$ . Jack Lutz, in the early 2000s posed the dimension spectrum conjecture. This conjecture states that, for every line $L_{a,b}$ , the spectrum of $L_{a,b}$ contains a unit interval.

In this paper we prove that the dimension spectrum conjecture is true. Specifically, let $(a,b)$ be a slope-intercept pair, and let $d=\min\{\dim(a,b),1\}$ . For every $s\in[0,1]$ , we construct a point $x$ such that $\dim(x,ax+b)=d+s$ . Thus, we show that $\operatorname{sp}(L_{a,b})$ contains the interval $[d,1+d]$ .

1 Introduction

The effective dimension, $\dim(x)$ , of a point $x\in\mathbb{R}^{n}$ gives a fine-grained measure of the algorithmic randomness of $x$ . Effective dimension was first defined by J. Lutz [5], and was originally used to quantify the sizes of complexity classes. Unsurprisingly, because of its strong connection to (classical) Hausdorff dimension, effective dimension has proven to be geometrically meaningful [3, 15, 1, 9]. Indeed, an exciting line of research has shown that one can prove classical results in geometric measure theory using effective dimension [7, 10, 11, 13]. Importantly, these are not effectivizations of known results, but new results whose proofs rely on effective methods. Thus, it is of considerable interest to investigate the effective dimensions of points of geometric objects such as lines.

Let $L_{a,b}$ be a line in the Euclidean plane with slope $a$ and intercept $b$ . Given the point-wise nature of effective dimension, one can study the dimension spectrum of $L_{a,b}$ . That is, the set

$\operatorname{sp}(L_{a,b})=\{\dim(x,ax+b)\,|x\in\mathbb{R}\}$

of all effective dimensions of points on $L_{a,b}$ . In the early 2000s, Jack Lutz posed the dimension spectrum conjecture for lines. That is, he conjectured that the dimension spectrum of every line in the plane contains a unit interval.

The first progress on this conjecture was made by Turetsky.

Theorem 1 (Turetsky [18]).

The set of points $x\in\mathbb{R}^{n}$ with $\dim(x)=1$ is connected.

This immediately implies that $1\in\operatorname{sp}(L_{a,b})$ for every line $L_{a,b}$ . The next progress on the dimension spectrum conjecture was by Lutz and Stull [11]. They showed that the effective dimension of points on a line is intimately connected to problems in fractal geometry. Among other things, they proved that $1+d\in\operatorname{sp}(L_{a,b})$ for every line $L_{a,b}$ , where $d=\min\{\dim(a,b),1\}$ . Shortly thereafter, Lutz and Stull [12] proved the dimension spectrum conjecture for the special case where the effective dimension and strong dimension of $(a,b)$ agree.

In this paper, we prove that dimension spectrum conjecture is true. For every $s\in(0,1)$ , we construct a point $x$ such that $\dim(x,ax+b)=d+s$ , where $d=\min\{\dim(a,b),1\}$ . This, combined with the results of Lutz and Stull, imply that

$[d,1+d]\subseteq\operatorname{sp}(L_{a,b})$ ,

for every planar line $L_{a,b}$ . The proof of the conjecture builds on the techniques of [11]. The primary difficulty of the conjecture is the case when the dimension of $x$ is less than the difficulty of the line $(a,b)$ . We expand on the nature of this $\dim(x)<\dim(a,b)$ obstacle in Section 3.1. Our main technical contribution is showing how to overcome this difficulty by encoding the information of $a$ into our point $x$ . Further complications arise in the “high-dimensional” case, i.e., when $\dim(a,b)>1$ . In this case, we combine the encoding idea with a non-constructive argument.

Apart from its intrinsic interest, recent work has shown that the effective dimensions of points has deep connections to problems in classical analysis [10, 11, 13, 17, 8]. Lutz and Lutz [7] proved the point-to-set principle, which characterizes the Hausdorff dimension of a set by effective dimension of its individual points. Lutz and Stull [11], using the point-to-set principle, showed that lower bounds on the effective dimensions of points on a line are intimately related to well-known problems of classical geometric measure theory such the Kakeya and Furstenberg conjectures.

The structure of the paper is as follows. In Section 2, we recall the basic definitions and results of Kolmogorov complexity and effective dimension we need. In Section 3, we recall the strategy of Lutz and Stull [11] to give strong lower bounds on the effective dimension of points on a line. In Sections 3 and 3.1 we give intuition about this strategy, and discuss why it is not enough to settle the dimension spectrum conjecture.

In Section 4, we prove the dimension spectrum conjecture for lines with effective dimension at most one. We also give a brief overview of this proof, and how it overcomes the strategy discussed in Section 3. In Section 5, we prove the dimension spectrum conjecture for lines with effective dimension greater than one. We also give intuition of this proof, and how it overcomes the difficulties when the line is high-dimensional.

Finally, in the conclusion, we discuss open questions and avenues for future research.

2 Preliminaries

The conditional Kolmogorov complexity of a binary string $\sigma\in\{0,1\}^{*}$ given binary string $\tau\in\{0,1\}^{*}$ is

K(\sigma|\tau)=\min_{\pi\in\{0,1\}^{*}}\left\{\ell(\pi):U(\pi,\tau)=\sigma\right\}\,,

where $U$ is a fixed universal prefix-free Turing machine and $\ell(\pi)$ is the length of $\pi$ . The Kolmogorov complexity of $\sigma$ is $K(\sigma)=K(\sigma|\lambda)$ , where $\lambda$ is the empty string. Thus, the Kolmogorov complexity of a string $\sigma$ is the minimum length program which, when run on a universal Turing machine, eventually halts and outputs $\sigma$ . We stress that the choice of universal machine effects the Kolmogorov complexity by at most an additive constant (which, especially for our purposes, can be safely ignored). See [4, 16, 2] for a more comprehensive overview of Kolmogorov complexity.

We can extend these definitions to Euclidean spaces by introducing “precision” parameters [9, 7]. Let $x\in\mathbb{R}^{m}$ , and $r,s\in\mathbb{N}$ . The Kolmogorov complexity of $x$ at precision $r$ is

K_{r}(x)=\min\left\{K(p)\,:\,p\in B_{2^{-r}}(x)\cap\mathbb{Q}^{m}\right\}\,.

The conditional Kolmogorov complexity of $x$ at precision $r$ given $q\in\mathbb{Q}^{m}$ is

\hat{K}_{r}(x|q)=\min\left\{K(p)\,:\,p\in B_{2^{-r}}(x)\cap\mathbb{Q}^{m}\right\}\,.

The conditional Kolmogorov complexity of $x$ at precision $r$ given $y\in\mathbb{R}^{n}$ at precision $s$ is

K_{r,s}(x|y)=\max\big{\{}\hat{K}_{r}(x|q)\,:\,q\in B_{2^{-r}}(y)\cap\mathbb{Q}^{n}\big{\}}\,.

We abbreviate $K_{r,r}(x|y)$ by $K_{r}(x|y)$ .

The effective Hausdorff dimension and effective packing dimension¹¹1Although effective Hausdorff was originally defined by J. Lutz [6] using martingales, it was later shown by Mayordomo [14] that the definition used here is equivalent. For more details on the history of connections between Hausdorff dimension and Kolmogorov complexity, see [2, 15]. of a point $x\in\mathbb{R}^{n}$ are

\dim(x)=\liminf_{r\to\infty}\frac{K_{r}(x)}{r}\quad\text{and}\quad\operatorname{Dim}(x)=\limsup_{r\to\infty}\frac{K_{r}(x)}{r}\,.

Intuitively, these dimensions measure the density of algorithmic information in the point $x$ .

By letting the underlying fixed prefix-free Turing machine $U$ be a universal oracle machine, we may relativize the definition in this section to an arbitrary oracle set $A\subseteq\mathbb{N}$ . The definitions of $K^{A}_{r}(x)$ , $\dim^{A}(x)$ , $\operatorname{Dim}^{A}(x)$ , etc. are then all identical to their unrelativized versions, except that $U$ is given oracle access to $A$ . Note that taking oracles as subsets of the naturals is quite general. We can, and frequently do, encode a point $y$ into an oracle, and consider the complexity of a point relative to $y$ . In these cases, we typically forgo explicitly referring to this encoding, and write e.g. $K^{y}_{r}(x)$ .

Among the most used results in algorithmic information theory is the symmetry of information. In Euclidean spaces, this was first proved, in a slightly weaker form in [7], and in the form presented below in [11].

Lemma 2.

For every $m,n\in\mathbb{N}$ , $x\in\mathbb{R}^{m}$ , $y\in\mathbb{R}^{n}$ , and $r,s\in\mathbb{N}$ with $r\geq s$ ,

(i)

$\displaystyle|K_{r}(x|y)+K_{r}(y)-K_{r}(x,y)\big{|}\leq O(\log r)+O(\log\log\|y\|)\,.$
(ii)

$\displaystyle|K_{r,s}(x|x)+K_{s}(x)-K_{r}(x)|\leq O(\log r)+O(\log\log\|x\|)\,.$

2.1 Initial segments versus $K$ -optimizing rationals

For $x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ and a precision $r\in\mathbb{N}$ , let $x{\upharpoonright}r=(x_{1}{\upharpoonright}r,\ldots,x_{n}{\upharpoonright}r)$ , where each

$x_{i}{\upharpoonright}r=2^{-r}\lfloor 2^{r}x_{i}\rfloor$

is the truncation of $x_{i}$ to $r$ bits to the right of the binary point. For $r\in(0,\infty)$ , let $x{\upharpoonright}r=x{\upharpoonright}\lceil r\rceil$ .

We can relate the complexity $K_{r}(x)$ of $x$ at precision $r$ and the initial segment complexity $K(x{\upharpoonright}r)$ of the binary representation of $x$ . Lutz and Stull [11] proved the following lemma, and its corollaries, relating these two quantities. Informally, it shows that, up to a logarithmic error, the two quantities are equivalent.

Lemma 3.

For every $m,n\in\mathbb{N}$ , there is a constant $c$ such that for all $x\in\mathbb{R}^{m}$ , $p\in\mathbb{Q}^{n}$ , and $r\in\mathbb{N}$ ,

|\hat{K}_{r}(x|p)-K(x{\upharpoonright}r\,|\,p)|\leq K(r)+c\,.

This has the following two useful corollaries.

Corollary 4.

For every $m\in\mathbb{N}$ , there is a constant $c$ such that for every $x\in\mathbb{R}^{m}$ and $r\in\mathbb{N}$ ,

|K_{r}(x)-K(x{\upharpoonright}r)|\leq K(r)+c\,.

Corollary 5.

For every $m,n\in\mathbb{N}$ , there is a constant $c$ such that for all $x\in\mathbb{R}^{m}$ , $y\in\mathbb{R}^{n}$ , and $r,s\in\mathbb{N}$ ,

|K_{r,s}(x|y)-K(x{\upharpoonright}r\,|\,y{\upharpoonright}s)|\leq K(r)+K(s)+c\,.

3 Previous Work

The proof of our main theorem will use the tools and techniques introduced by Lutz and Stull [11]. In this section we will state the main lemmas needed for this paper. We will devote some time giving intuition about each lemma. In Subsection 3.1, we give an informal discussion on how to combine these lemmas to give bounds on the effective dimensions of points on a line. We will also discuss where these tools break down, motivating the techniques introduced in this paper.

The first lemma, informally, states the following. Suppose that $L_{a,b}$ intersects $(x,ax+b)$ and the complexity of $(a,b)$ is low (item (i)). Further assume that (item (ii)), if $L_{u,v}$ is any other line intersecting $(x,ax+b)$ such that $\|(a,b)-(u,v)\|<2^{-m}$ then either

1.

$u,v$ is of high complexity, or
2.

$u,v$ is very close to $a,b$ .

Then it is possible to compute an approximation of $(a,b)$ given an approximation of $(x,ax+b)$ and first $m$ bits of $(a,b)$ . Indeed, we can simply enumerate over all low complexity lines, since we know that the only candidate is essentially $(a,b)$ .

Lemma 6 (Lutz and Stull [11]).

Suppose that $A\subseteq\mathbb{N}$ , $a,b,x\in\mathbb{R}$ , $m,r\in\mathbb{N}$ , $\delta\in\mathbb{R}_{+}$ , and $\varepsilon,\eta\in\mathbb{Q}_{+}$ satisfy $r\geq\log(2|a|+|x|+5)+1$ and the following conditions.

(i)

$K^{A}_{r}(a,b)\leq\left(\eta+\varepsilon\right)r$ .
(ii)

For every $(u,v)\in B_{2^{-m}}(a,b)$ such that $ux+v=ax+b$ ,

$K^{A}_{r}(u,v)\geq\left(\eta-\varepsilon\right)r+\delta\cdot(r-t)\,,$

whenever $t=-\log\|(a,b)-(u,v)\|\in(0,r]$ .

Then,

K_{r}^{A}(a,b,x)\leq K_{r}(x,ax+b)+K_{m,r}(a,b\,|\,x,ax+b)+\frac{4\varepsilon}{\delta}r+K(\varepsilon,\eta)+O(\log r)\,.

The second lemma which will be important in proving our main theorem is the following. It is essentially the approximation version of the simple geometric fact that any two lines intersect at a single point. In other words, if $ax+b=ux+v$ and you are given an approximation of $(a,b)$ and an approximation of $(u,v)$ , then you can compute an approximation of $x$ . Moreover, the quality of the approximation of $x$ depends linearly on the distance between $(u,v)$ and $(a,b)$ .

Lemma 7 ([11]).

Let $a,b,x\in\mathbb{R}$ . For all $u,v\in B_{1}(a,b)$ such that $ux+v=ax+b$ , and for all $r\geq t:=-\log\|(a,b)-(u,v)\|$ ,

K_{r}(u,v)\geq K_{t}(a,b)+K_{r-t,r}(x|a,b)-O(\log r)\,.

The primary function of this lemma is to give a lower bound on the complexity of any line intersecting $(x,ax+b)$ , i.e., ensuring condition (ii) of the previous lemma.

Finally, we also need the following oracle construction of Lutz and Stull. The purpose of this lemma is to show that we can lower the complexity of our line $(a,b)$ , thus ensuring item (i) of Lemma 6. Crucially, we can lower this complexity using only the information contained in $(a,b)$ .

Lemma 8 ([11]).

Let $r\in\mathbb{N}$ , $z\in\mathbb{R}^{2}$ , and $\eta\in\mathbb{Q}\cap[0,\dim(z)]$ . Then there is an oracle $D=D(r,z,\eta)$ satisfying

(i)

For every $t\leq r$ , $K^{D}_{t}(z)=\min\{\eta r,K_{t}(z)\}+O(\log r)$ .
(ii)

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

3.1 Combining the lemmas

We now briefly discuss the strategy of [11] which combines the above lemmas to give non-trivial bounds on the effective dimension of points on a line. Suppose $(a,b)$ is a line with $\dim(a,b)=d$ , and $x$ is a point with $\dim^{a,b}(x)=s$ . We will also make the crucial assumption that $d\leq s$ . Roughly, Lutz and Stull showed that, for sufficiently large $r$

$K_{r}(x,ax+b)\geq(s+d)r$ .

The strategy is as follows. Note that to simplify the exposition, all inequalities in this discussion will be approximate. Using Lemma 8, we find an oracle $D$ which reduces the complexity of $(a,b)$ to some $\eta\leq dr$ , i.e., $K^{D}_{r}(a,b)=\eta r$ . Combining this with Lemma 7, we get a lower bound on every line $(u,v)$ intersecting $(x,ax+b)$ . That is, we show for any such line,

K^{D}_{r}(u,v)\geq\eta t+s(r-t)-O(\log r)

By our choice of $\eta$ , we can simplify this inequality to get

K^{D}_{r}(u,v)\geq sr-O(\log r)

In particular, relative to $D$ , both conditions of Lemma 6 are satisfied and we have the sufficient lower bound.

In the previous sketch, it was crucial that the dimension of $(a,b)$ was less than $s$ , in order for the lower bound from Lemma 7 to be useful. In the case where $\dim(a,b)$ is much larger than $\dim(x)$ , this strategy breaks down, and further techniques are required.

We also note that this seems to be a very deep issue. As discussed in the Introduction, the point-to-set principle of J. Lutz and N. Lutz [7] allows us to translate problems from (classical) geometric measure theory into problems of effective dimension. The same issue discussed in this section occurs when attacking the notorious Kakeya and Furstenberg set conjectures using the point-to-set principle. While resolving this obstacle in full generality is still elusive, we are able to get around it in the context of the Dimension Spectrum Conjecture.

4 Low-Dimensional Lines

In this section, we prove the spectrum conjecture for lines with $\dim(a,b)\leq 1$ .

Theorem 9.

Let $(a,b)\in\mathbb{R}^{2}$ be a slope-intercept pair with $\dim(a,b)\leq 1$ .. Then for every $s\in[0,1]$ , there is a point $x\in\mathbb{R}$ such that

$\dim(x,ax+b)=s+\dim(a,b)$ .

We begin by giving an intuitive overview of the proof.

4.1 Overview of the proof

As mentioned in Section 3.1, the main obstacle of the Dimension Spectrum Conjecture occurs when the dimension of $x$ is lower than the dimension of the line $(a,b)$ . As mentioned in Section 3.1, in general, this issue is still formidable. However, in the Dimension Spectrum Conjecture, we are given the freedom to specifically construct the point $x$ , allowing us overcome this obstacle.

The most natural way to construct a sequence $x$ with $\dim^{a,b}(x)=s$ is to start with a random sequence, and pad it with long strings of zeros. This simple construction, unfortunately, does not seem to work.

We are able to overcome the obstacle by padding the random sequence with the bits of $a$ , instead of with zeros. Thus, given an approximation $(x,ax+b)$ we trivially have a decent approximation of $a$ (formalized iin Lemma 10). This allows us, using Lemma 6, to restrict our search for $(a,b)$ to a smaller set of candidate lines.

4.2 Proof for low-dimensional lines

Fix a slope-intercept pair $(a,b)$ , and let $d=\dim(a,b)$ . Let $s\in(0,d)$ . Let $y\in\mathbb{R}$ be random relative to $(a,b)$ . Thus, for every $r\in\mathbb{N}$ ,

$K^{a,b}_{r}(y)\geq r-O(\log r)$ .

Define the sequence of natural numbers $\{h_{j}\}_{j\in\mathbb{N}}$ inductively as follows. Define $h_{0}=1$ . For every $j>0$ , let

h_{j}=\min\left\{h\geq 2^{h_{j-1}}:K_{h}(a,b)\leq\left(d+\frac{1}{j}\right)h\right\}.

Note that $h_{j}$ always exists. For every $r\in\mathbb{N}$ , let

\displaystyle x[r]=\begin{cases}a[r-\lfloor sh_{j}\rfloor]&\text{ if }r\in(\lfloor sh_{j}\rfloor,h_{j}]\text{ for some }j\in\mathbb{N}\\ y[r]&\text{ otherwise}\end{cases}

where $x[r]$ is the $r$ th bit of $x$ . Define $x\in\mathbb{R}$ to be the real number with this binary expansion.

One of the most important aspects of our construction is that we encode (a subset of) the information of $a$ into our point $x$ . This is formalized in the following lemma.

Lemma 10.

For every $j\in\mathbb{N}$ , and every $r$ such that $sh_{j}<r\leq h_{j}$ ,

$K_{r-sh_{j},r}(a,b\,|\,x,ax+b)\leq O(\log h_{j})$ .

Proof.

By definition, the last $r-sh_{j}$ bits of $x$ are equal to the first $r-sh_{j}$ bits of $a$ . That is,

	$\displaystyle x[sh_{j}]\,x[sh_{j}+1]\,\ldots x[r]$	$\displaystyle=a[0]\,a[1]\,\ldots a[r-sh_{j}]$
		$\displaystyle=a{\upharpoonright}(r-sh_{j}).$

Therefore, since additional information cannot increase Kolmogorov complexity,

	$\displaystyle K_{r-sh_{j},r}(a\,\|\,x,ax+b)$	$\displaystyle\leq K_{r-sh_{j},r}(a\,\|\,x)$
		$\displaystyle\leq O(\log h_{j}).$

Note that, given $2^{-(r-sh_{j})}$ -approximations of $a$ , $x$ , and $ax+b$ , it is possible to compute an approximation of $b$ . That is,

$K_{r-sh_{j}}(b\,|\,a,x,ax+b)\leq O(\log h_{j})$ .

Therefore, by Lemma 2 and the two above inequalities,

	$\displaystyle K_{r-sh_{j},r}(a,b\,\|\,x,ax+b)$	$\displaystyle=K_{r-sh_{j},r}(a\,\|\,x,ax+b)$
		$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+K_{r-sh_{j},r}(b\,\|\,a,x,ax+b)+O(\log r)$
		$\displaystyle\leq O(\log h_{j})+K_{r-sh_{j},r}(b\,\|\,a,x,ax+b)+O(\log r)$
		$\displaystyle\leq O(\log h_{j}).$

∎

The other important property of our construction is that $(a,b)$ gives no information about $x$ , beyond the information specifically encoded into $x$ .

Lemma 11.

For every $j\in\mathbb{N}$ , the following hold.

1.

$K^{a,b}_{t}(x)\geq t-O(\log h_{j})$ , for all $t\leq sh_{j}$ .
2.

$K^{a,b}_{r}(x)\geq sh_{j}+r-h_{j}-O(\log h_{j})$ , for all $h_{j}\leq r\leq sh_{j+1}$ .

Proof.

We first prove item (1). Let $t\leq sh_{j}$ . Then, by our construction of $x$ , and choice of $y$ ,

	$\displaystyle K^{a,b}_{t}(x)$	$\displaystyle\geq K^{a,b}_{t}(y)-h_{j-1}-O(\log t)$
		$\displaystyle\geq t-O(\log t)-\log h_{j}-O(\log t)$
		$\displaystyle\geq t-O(\log h_{j}).$

For item (2), let $h_{j}\leq r\leq sh_{j+1}$ . Then, by item (1), Lemma 2 and our construction of $x$ ,

$\displaystyle K^{a,b}_{r}(x)$	$\displaystyle=K^{a,b}_{h_{j}}(x)+K^{a,b}_{r,h_{j}}(x)-O(\log r)$	[Lemma 2]
	$\displaystyle\geq sh_{j}+K^{a,b}_{r,h_{j}}(x)-O(\log r)$	[Item (1)]
	$\displaystyle\geq sh_{j}+K^{a,b}_{r,h_{j}}(y)-O(\log r)$
	$\displaystyle\geq sh_{j}+r-h_{j}-O(\log r),$

and the proof is complete.

∎

We now prove bounds on the complexity of our constructed point. We break the proof into two parts.

In the first, we give lower bounds on $K_{r}(x,ax+b)$ at precisions $sh_{j}<r\leq h_{j}$ . Intuitively, the proof proceeds as follows. Since $r>sh_{j}$ , given $(x,ax+b)$ to precision $r$ immediately gives a $2^{-r+sh_{j}}$ approximation of $(a,b)$ . Thus, we only have to search for candidate lines $(u,v)$ which satisfy $t=\|(a,b)-(u,v)\|<2^{-r+sh_{j}}$ . Then, because of the lower bound on $t$ , the complexity $K_{r-t}(x)$ is maximal. In other words, we are essentially in the case that the complexity of $x$ is high. Thus, we are able to use the method described in Section 3.1. We now formalize this intuition.

Lemma 12.

For every $\gamma>0$ and all sufficiently large $j\in\mathbb{N}$ ,

$K_{r}(x,ax+b)\geq(s+d)r-\gamma r$ ,

for every $r\in(sh_{j},h_{j}]$ .

Proof.

Let $\eta\in\mathbb{Q}$ such that

$d-\gamma/4<\eta<d-\gamma^{2}$ .

Let $\varepsilon\in\mathbb{Q}$ such that

$\varepsilon<\gamma(d-\eta)/16$ .

Note that

$\frac{4\varepsilon}{1-\eta}\leq\frac{\gamma}{4}$

We also note that, since $\eta$ and $\varepsilon$ are constant,

$K(\eta,\varepsilon)=O(1)$ .

Let $D=D(r,(a,b),\eta)$ be the oracle of Lemma 8 and let $\delta=1-\eta$ .

Let $(u,v)$ be a line such that $t:=\|(a,b)-(u,v)\|\geq r-sh_{j}$ , and $ux+v=ax+b$ . Note that $r-t\leq sh_{j}$ . Then, by Lemma 7, Lemma 8 and Lemma 11(1),

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K^{D}_{t}(a,b)+K^{D}_{r-t,r}(x\,\|\,a,b)-O(\log r)$	[Lemma 7]
	$\displaystyle\geq K^{D}_{t}(a,b)+K_{r-t,r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle\geq K^{D}_{t}(a,b)+r-t-O(\log r).$	[Lemma 11(1)]

There are two cases by Lemma 8. For the first, assume that $K^{D}_{t}(a,b)=\eta r$ . Then

	$\displaystyle\geq\eta r+r-t-O(\log r)$		[Definition of $\dim$ ]
	$\displaystyle=(\eta-\varepsilon)r+r-t$		[ $r$ is large]
	$\displaystyle\geq(\eta-\varepsilon)r+(1-\eta)(r-t)$

For the second, assume that $K^{D}_{t}(a,b)=K_{t}(a,b)$ . Then

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K_{t}(a,b)+r-t-O(\log r)$
	$\displaystyle\geq dt-o(t)+r-t-O(\log r)$	[Definition of $\dim$ ]
	$\displaystyle=\eta r+(1-\eta)r-t(1-d)-\varepsilon r$	[ $r$ is large]
	$\displaystyle\geq\eta r-\varepsilon r+(1-\eta)(r-t)$	[ $d>\eta$ ]
	$\displaystyle\geq(\eta-\varepsilon)r+(1-\eta)(r-t).$	(1)

Therefore, in either case, we may apply Lemma 6,

$\displaystyle K_{r}(x,ax+b)$	$\displaystyle\geq K_{r}^{D}(a,b,x)-K_{r-sh_{j},r}(a,b\,\|,x,ax+b)$	[Lemma 6]
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\frac{4\varepsilon}{1-\eta}r-K(\eta,\varepsilon)-O(\log r)$
	$\displaystyle\geq K_{r}^{D}(a,b,x)-K_{r-sh_{j},r}(a,b\,\|\,x,ax+b)-\frac{\gamma}{4}r-\frac{\gamma}{8}r$
	$\displaystyle=K_{r}^{D}(a,b,x)-K_{r-sh_{j},r}(a,b\,\|\,x,ax+b)-\frac{3\gamma}{8}r.$	(2)

By Lemma 11(1), our construction of oracle $D$ , and the symmetry of information,

$\displaystyle K_{r}^{D}(a,b,x)$	$\displaystyle=K_{r}^{D}(a,b)+K_{r}^{D}(x\,\|\,a,b)-O(\log r)$	[Lemma 2]
	$\displaystyle=K_{r}^{D}(a,b)+K_{r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8(ii)]
	$\displaystyle\geq\eta r+K_{r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8(i)]
	$\displaystyle\geq\eta r+sh_{j}-O(\log r)$	[Lemma 11(1)]
	$\displaystyle\geq\eta r+sh_{j}-\frac{\gamma}{4}r.$	(3)

Finally, by Lemma 10,

K_{r-sh_{j},r}(a,b\mid x,ax+b)\leq\frac{\gamma}{8}r.

(4)

Together, inequalities (2), (3) and (4) imply that

	$\displaystyle K_{r}(x,ax+b)$	$\displaystyle\geq K_{r}^{D}(a,b,x)-K_{r-sh_{j},r}(a,b\,\|,x,ax+b)-\frac{3\gamma}{8}r$
		$\displaystyle\geq\eta r+sh_{j}-\frac{\gamma}{4}r-\frac{\gamma}{8}r-\frac{3\gamma}{8}r$
		$\displaystyle\geq dr-\frac{\gamma}{4}r+sh_{j}-\frac{3\gamma}{4}r$
		$\displaystyle\geq dr+sh_{j}-\gamma r$
		$\displaystyle\geq(s+d)r-\gamma r,$

and the proof is complete. ∎

We now give lower bounds on the complexity of our point, $K_{r}(x,ax+b)$ , when $h_{j}<r\leq sh_{j+1}$ . Intuitively, the proof proeeds as follows. Using the previous lemma, we can, given a $2^{-h_{j}}$ -approximation of $(x,ax+b)$ , compute a $2^{-h_{j}}$ -approximation of $(a,b)$ . Thus, we only have to compute the last $r-h_{j}$ bits of $(a,b)$ . Importantly, since $r>h_{j}$ , the last $r-h_{j}$ bits of $x$ are maximal. Hence, we can simply lower the complexity of the last $r-h_{j}$ bits of $(a,b)$ to roughly $s(r-h_{j})$ . Thus, we are again, essentially, in the case where $\dim(x)\geq\dim(a,b)$ and the techniques of Section 3.1 work. We now formalize this intuition.

Lemma 13.

For every $\gamma>0$ and all sufficiently large $j\in\mathbb{N}$ ,

$K_{r}(x,ax+b)\geq(s+d)r-\gamma r$ ,

for every $r\in(h_{j},sh_{j+1}]$ .

Proof.

Recall that we are assuming that $s<d$ . Let $\hat{s}\in\mathbb{Q}\cap(0,s)$ be a dyadic rational such that

$\gamma/8<s-\hat{s}<\gamma/4$ .

Let $\hat{d}\in\mathbb{Q}\cap(0,\dim(a,b))$ be a dyadic rational such that

$\gamma/8<\dim(a,b)-\hat{d}<\gamma/4$ .

Define

$\alpha=\frac{s(r-h_{j})+\dim(a,b)h_{j}}{r}$ ,

and $\eta\in\mathbb{Q}\cap(0,\alpha)$ by

$\eta=\frac{\hat{s}(r-h_{j})+\hat{d}h_{j}}{r}$ .

Finally, let $\varepsilon=\gamma^{2}/64$ . Note that

$\displaystyle\alpha-\eta$	$\displaystyle=\frac{s(r-h_{j})+dh_{j}-\hat{s}(r-h_{j})-\hat{d}h_{j}}{r}$
	$\displaystyle=\frac{(s-\hat{s})(r-h_{j})+(d-\hat{d})h_{j}}{r}$
	$\displaystyle\leq\frac{\frac{\gamma}{4}(r-h_{j})+\frac{\gamma}{4}h_{j}}{r}$
	$\displaystyle=\frac{\gamma}{4}$	(5)

Similarly,

$\displaystyle\alpha-\eta$	$\displaystyle=\frac{s(r-h_{j})+\dim(a,b)h_{j}-\hat{s}(r-h_{j})-\hat{d}h_{j-1}}{r}$
	$\displaystyle=\frac{(s-\hat{s})(r-h_{j})+(\dim(a,b)-\hat{d})h_{j}}{r}$
	$\displaystyle>\frac{\frac{\gamma}{8}(r-h_{j})+\frac{\gamma}{8}h_{j}}{r}$
	$\displaystyle=\frac{\gamma}{8}$	(6)

In particular,

\frac{4\varepsilon}{\alpha-\eta}\leq\gamma/4.

(7)

We also note that

K(\varepsilon,\eta)\leq K(\gamma,\hat{s},\hat{d},r,h_{j})\leq O(\log r),

(8)

since $j$ was chosen to be sufficiently large and $\gamma$ is constant.

Finally, let $D=D(r,(a,b),\eta)$ be the oracle of Lemma 8. Note that we chose $D$ so that, roughly, $D$ lowers the complexity of the last $r-h_{j}$ bits of $(a,b)$ to $s(r-h_{j})$ .

Let $(u,v)$ be a line such that $t:=\|(a,b)-(u,v)\|\geq h_{j}$ , and $ux+v=ax+b$ . Then, by Lemmas 7, 8 and 11,

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K^{D}_{t}(a,b)+K^{D}_{r-t,r}(x\,\|\,a,b)-O(\log r)$	[Lemma 7]
	$\displaystyle\geq K^{D}_{t}(a,b)+K_{r-t,r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle\geq K^{D}_{t}(a,b)+s(r-t)-O(\log r).$	[Lemma 11(1)]

There are two cases. In the first, $K^{D}_{t}(a,b)=\eta r$ . Then,

	$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq\eta r+s(r-t)-O(\log r)$
		$\displaystyle\geq(\eta-\varepsilon)r+s(r-t)$
		$\displaystyle\geq(\eta-\varepsilon)r+(\alpha-\eta)(r-t).$

In the other case, $K^{D}_{t}(a,b)=K_{t}(a,b)$ . Then,

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K_{t}(a,b)+s(r-t)-O(\log r)$
	$\displaystyle\geq dt-o(t)+s(r-t)-O(\log r)$	[Definition of $\dim$ ]
	$\displaystyle=dh_{j}+d(t-h_{j})+s(r-t)-o(r)$
	$\displaystyle=dh_{j}+d(t-h_{j})+s(r-h_{j})-s(t-h_{j})-o(r)$
	$\displaystyle=\alpha r+(d-s)(t-h_{j})-o(r)$
	$\displaystyle=\eta r+(\alpha-\eta)r+(d-s)(t-h_{j})-o(r)$
	$\displaystyle\geq\eta r+(\alpha-\eta)(r-t)-o(r)$
	$\displaystyle\geq(\eta-\varepsilon)r+(\alpha-\eta)(r-t).$

Therefore we may apply Lemma 6, which yields

$\displaystyle K^{D}_{r}(a,b,x)$	$\displaystyle\leq K_{r}(x,ax+b)+K^{D}_{h_{j},r}(a,b,x\,\|\,x,ax+b)$	[Lemma 6]
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;+\frac{4\varepsilon}{\alpha-\eta}r+K(\varepsilon,\eta)+O(\log r)$
	$\displaystyle\leq K_{r}(x,ax+b)+K^{D}_{h_{j},r}(a,b,x\,\|\,x,ax+b)$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+\frac{\gamma}{4}r+\frac{\gamma}{8}r$	[Choice of $\eta,\varepsilon$ ]
	$\displaystyle=K_{r}(x,ax+b)+K^{D}_{h_{j},r}(a,b,x\,\|\,x,ax+b)+\frac{3\gamma}{8}r.$	(9)

By Lemma 11, and our construction of oracle $D$ ,

$\displaystyle K_{r}^{D}(a,b,x)$	$\displaystyle=K_{r}^{D}(a,b)+K_{r}^{D}(x\,\|\,a,b)-O(\log r)$	[Lemma 2]
	$\displaystyle=\eta r+K_{r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle\geq\eta r+sh_{j}+r-h_{j}-O(\log r)$	[Lemma 11(2)]
	$\displaystyle\geq\alpha r-\frac{\gamma}{4}r+sh_{j}+r-h_{j}-O(\log r)$
	$\displaystyle\geq s(r-h_{j})+dh_{j}-\frac{\gamma}{4}r+sh_{j}+r-h_{j}-O(\log r)$
	$\displaystyle\geq(1+s)r-(1-d)h_{j}-\frac{\gamma}{4}r.$	(10)

By Lemmas 12, and 2, and the fact that additional information cannot increase Kolmogorov complexity

$\displaystyle K_{h_{j},r}(a,b,x\,\|\,x,ax+b)$	$\displaystyle\leq K_{h_{j},h_{j}}(a,b,x\,\|\,x,ax+b)$
	$\displaystyle=K_{h_{j}}(a,b,x)-K_{h_{j}}(x,ax+b)$	[Lemma 2]
	$\displaystyle=K_{h_{j}}(a,b)+K_{h_{j}}(x\mid a,b)$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-K_{h_{j}}(x,ax+b)$	[Lemma 2]
	$\displaystyle=K_{h_{j}}(a,b)+sh_{j}-K_{h_{j}}(x,ax+b)$	[Lemma 11]
	$\displaystyle\leq K_{h_{j}}(a,b)+sh_{j}-(s+d)h_{j}+\frac{\gamma}{16}h_{j}$	[Lemma 12]
	$\displaystyle\leq dh_{j}+h_{j}/j-dh_{j}+\frac{\gamma}{16}r$	[Definition of $h_{j}$ ]
	$\displaystyle\leq\frac{\gamma}{8}r$	(11)

Combining inequalities (9), (10) and (11) , we see that

	$\displaystyle K_{r}(x,ax+b)$	$\displaystyle\geq K_{r}^{D}(a,b,x)-\frac{\gamma}{8}r-\frac{3\gamma}{8}r$
		$\displaystyle\geq(1+s)r-(1-d)h_{j}-\frac{\gamma}{4}r-\frac{\gamma}{4}r$
		$\displaystyle\geq(1+s)r-(1-d)h_{j}-\gamma r.$

Note that, since $d\leq 1$ , and $h_{j}\leq r$ ,

	$\displaystyle(1+s)r-h_{j}(1-d)-(s+d)r$	$\displaystyle=r(1-d)-h_{j}(1-d)$
		$\displaystyle=(r-h_{j})(1-d)$
		$\displaystyle\geq 0.$

Thus,

	$\displaystyle K_{r}(x,ax+b)$	$\displaystyle\geq(1+s)r-h_{j}(1-d)-\gamma r$
		$\displaystyle\geq(s+d)r-\gamma r,$

and the proof is complete for the case $s<\dim(a,b)$ .

∎

We are now able to prove our main theorem.

Proof of Theorem 9.

Let $(a,b)\in\mathbb{R}^{2}$ be a slope-intercept pair with

$d=\dim(a,b)\leq 1$ .

Let $s\in[0,1]$ . If $s=0$ , then

	$\displaystyle K_{r}(a,a^{2}+b)$	$\displaystyle=K_{r}(a)+K_{r}(a^{2}+b\,\|\,a)+O(\log r)$
		$\displaystyle=K_{r}(a)+K_{r}(b\,\|\,a)+O(\log r)$
		$\displaystyle=K_{r}(a,b)+O(\log r),$

and so the conclusion holds.

If $s=1$ , then by [11], for any point $x$ which is random relative to $(a,b)$ ,

$\dim(x,ax+b)=1+d$ ,

and the claim follows.

If $s\geq d$ , then Lutz and Stull [11] showed that for any $x$ such that

$\dim^{a,b}(x)=\dim(x)=s$ ,

we have $\dim(x,ax+b)=s+d$ .

Therefore, we may assume that $s\in(0,1)$ and $s<d$ . Let $x$ be the point constructed in this section. Let $\gamma>0$ . Let $j$ be large enough so that the conclusions of Lemmas 12 and 13 hold for these choices of $(a,b)$ , $x$ , $s$ and $\gamma$ . Then, by Lemmas 12 and 13,

	$\displaystyle\dim(x,ax+b)$	$\displaystyle=\liminf_{r\rightarrow\infty}\frac{K_{r}(x,ax+b)}{r}$
		$\displaystyle\geq\liminf_{r\rightarrow\infty}\frac{(s+d)r-\gamma r}{r}$
		$\displaystyle=s+d-\gamma.$

Since we chose $\gamma$ arbitrarily, we see that

$\dim(x,ax+b)\geq s+d$ .

For the upper bound, let $j\in\mathbb{N}$ be sufficiently large. Then

	$\displaystyle K_{h_{j}}(x,ax+b)$	$\displaystyle\leq K_{h_{j}}(x,a,b)$
		$\displaystyle=K_{h_{j}}(a,b)+K_{h_{j}}(x\,\|\,a,b)$
		$\displaystyle\leq dh_{j}+sh_{j}$
		$\displaystyle=(d+s)h_{j}.$

Therefore,

$\dim(x,ax+b)\leq s+d$ ,

and the proof is complete. ∎

5 High-Dimensional Lines

In this section we show that the Dimension Spectrum Conjecture holds for lines of high dimension, i.e., for lines $L_{a,b}$ such that $\dim(a,b)>1$ . That is, we will prove the following theorem.

Theorem 14.

Let $(a,b)\in\mathbb{R}^{2}$ be a slope-intercept pair with $\dim(a,b)>1$ .. Then for every $s\in[0,1]$ , there is a point $x\in\mathbb{R}$ such that

$\dim(x,ax+b)=1+s$ .

5.1 Overview of proof

In this case, we again apply essential insight of the proof for low-dimensional lines, namely, encoding (a subset of) the information of $a$ into $x$ . However, when $\dim(a,b)>1$ constructing $x$ as before potentially causes a problem. Specifically, in this case, the previous construction might cause $\dim(x,ax+b)$ to become too large.

The overcome this, we rely on a non-constructive argument. More specifically, we begin as in the construction of $x$ in the low-dimensional case. However at stage $j$ of our construction, we do not add all $h_{j}-sh_{j}$ bits of $a$ to $x$ . Instead we consider the $m=h_{j}-sh_{j}$ strings $\mathbf{x_{0}},\ldots,\mathbf{x_{m}}$ , where

\displaystyle\mathbf{x_{n}}[i]=\begin{cases}0&\text{ if }0\leq i<m-n\\ \frac{1}{a}[i-(m-n)]&\text{ if }m-n\leq i\leq m\end{cases}

(*)

and look at the extension of $x$ with the bits of $\mathbf{x_{n}}$ .

Using a discrete, approximate, version of the mean value theorem, we are able to conclude that there is some extension $x^{\prime}=x\mathbf{x_{n}}$ such that

$\min\limits_{sh_{j}\leq r\leq h_{j}}|K_{r}(x^{\prime},ax^{\prime}+b)-(1+s)r|$

is sufficiently small. We then carry on with the argument of the low-dimensional lines until $sh_{j+1}$ .

5.2 Proof for high-dimensional lines

In order to prove Theorem 14, we will, given any slope-intercept pair $(a,b)$ and $s\in(0,1)$ , construct a point $x\in[0,1]$ such that $\dim(x,ax+b)=1+s$ .

Our construction is best phrased as constructing an infinite binary sequence $\mathbf{x}$ , and then taking $x$ to be the unique real number whose binary expansion is $\mathbf{x}$ . We now recall terminology needed in the construction. We will use bold variables to denote binary strings and (infinite) binary sequences. If $\mathbf{x}$ is a (finite) binary string and $\mathbf{y}$ is a binary string or sequence, we write $\mathbf{x}\prec\mathbf{y}$ if $\mathbf{x}$ is a prefix of $\mathbf{y}$ .

Let $(a,b)$ be a slope intercept pair and let $d=\dim(a,b)$ . Define the sequence of natural numbers $\{h_{j}\}_{j\in\mathbb{N}}$ inductively as follows. Define $h_{0}=2$ . For every $j>0$ , let

h_{j}=\min\left\{h\geq 2^{h_{j-1}}:K_{h}(a,b)\leq\left(d+2^{-j}\right)h\right\}.

We define our sequence $\mathbf{x}$ inductively. Let $\mathbf{y}$ be a random, relative to $(a,b)$ , binary sequence. That is, there is some constant $c$ such that

K^{a,b}(y{\upharpoonright}r)\geq r-c,

(12)

for every $r\in\mathbb{N}$ . We begin our inductive definition by setting $\mathbf{x}[0\ldots 2]=\mathbf{y}[0\ldots 2]$ . Suppose we have defined $\mathbf{x}$ up to $h_{j-1}$ . We then set

$\mathbf{x}[r]=\mathbf{y}[r]$ , for all $h_{j-1}<r\leq sh_{j}$ .

To specify the next $h_{j}-sh_{j}$ bits of $\mathbf{x}$ , we use the following lemma, which we will prove in the next section.

Lemma 15.

For every sufficiently large $j$ , there is a binary string $\mathbf{z}$ of length $h_{j}-sh_{j}$ such that

\min\limits_{sh_{j}<r\leq h_{j}}\left|K_{r}(x,ax+b)-(1+s)r\right|<\frac{r}{j},

where $x$ is any real such that $\mathbf{x}\mathbf{z}\prec x$ . Moreover, $\mathbf{z}$ is of the form (*) of Section 5.1.

For now, we assume the truth of this lemma. If the current $j$ is not sufficiently large, take $\mathbf{z}$ to be the string of all zeros. Otherwise, if $j$ is sufficiently large, we let $\mathbf{z}$ be such a binary string. We then set

$\mathbf{x}[r]=\mathbf{z}[r-sh_{j}]$ , for all $sh_{j}<r\leq h_{j}$ ,

completing the inductive step. Finally, we let $x_{a,b,s}$ be the real number with binary expansion $\mathbf{x}$ .

Proposition 16.

Let $x=x_{a,b,s}$ be the real we just constructed. Then for every $j$ ,

1.

$K^{a,b}_{sh_{j}}(x)\geq sh_{j}-O(\log h_{j})$ , and
2.

$K_{r}(x\mid a,b)\geq sh_{j}+r-h_{j}$ , for every $h_{j}\leq r<sh_{j+1}$ .

Proof.

To see (1), by our construction, $\mathbf{x}[h_{j-1}\ldots sh_{j}]=\mathbf{y}[h_{j-1}\ldots sh_{j}]$ . Thus, by Corollary 4,

	$\displaystyle K^{a,b}_{sh_{j}}(x)$	$\displaystyle=K^{a,b}(\mathbf{x})-O(\log h_{j})$
		$\displaystyle\geq K^{a,b}(\mathbf{y})-h_{j-1}-O(\log h_{j})$
		$\displaystyle\geq sh_{j}-h_{j-1}-O(\log h_{j})$
		$\displaystyle\geq sh_{j}-O(\log h_{j}).$

For item (2), by our construction $\mathbf{x}[h_{j}\ldots r]=\mathbf{y}[h_{j}\ldots r]$ . Therefore, by Corollary 4 and our construction of $x$ ,

$\displaystyle K_{r}(x\mid a,b)$	$\displaystyle\geq K^{a,b}_{r}(x)$
	$\displaystyle=K^{a,b}(\mathbf{x})-O(\log h_{j})$
	$\displaystyle\geq K^{a,b}(\mathbf{y}[0\ldots sh_{j}]\mathbf{z}\mathbf{y}[h_{j}\ldots r])-h_{j-1}-O(\log h_{j})$
	$\displaystyle\geq K^{a,b}(\mathbf{y}[0\ldots sh_{j}]\mathbf{y}[h_{j}\ldots r])$
	$\displaystyle\;\;\;\;\;\;\;\;\;-h_{j-1}-O(\log h_{j})$	[ $\mathbf{z}$ computable from $a$ ]
	$\displaystyle\geq sh_{j}+r-h_{j}-O(\log h_{j})$	[Definition of $\mathbf{y}$ ]

∎

We now show, again assuming Lemma 15, that $\dim(x,ax+b)=1+s$ , where $x=x_{a,b,s}$ is the point we have just constructed.

We begin by proving an upper bound on $\dim(x,ax+b)$ . Note that this essentially follows from our choice of $\mathbf{z}$ .

Proposition 17.

Let $(a,b)$ be a slope intercept pair, $s\in(0,1)$ and $\gamma\in\mathbb{Q}$ be positive. Let $x=x_{a,b,s}$ be the point we have just constructed. Then

$\dim(x,ax+b)\leq(1+s)+\gamma$ .

Proof.

Let $j$ be sufficiently large. By our construction of $x$ ,

\min\limits_{sh_{j}<r\leq h_{j}}\left|K_{r}(x,ax+b)-(1+s)r\right|<\frac{\gamma r}{4}

(13)

Therefore,

	$\displaystyle\dim(x,ax+b)$	$\displaystyle=\liminf\limits_{r}\frac{K_{r}(x,ax+b)}{r}$
		$\displaystyle\leq\liminf\limits_{j}\min\limits_{sh_{j}<r\leq h_{j}}\frac{K_{r}(x,ax+b)}{r}$
		$\displaystyle\leq\liminf\limits_{j}\min\limits_{sh_{j}<r\leq h_{j}}\frac{(1+s)r+\gamma r/4}{r}$
		$\displaystyle=\liminf\limits_{j}\min\limits_{sh_{j}<r\leq h_{j}}1+s+\gamma/4$
		$\displaystyle=1+s+\frac{\gamma}{4}.$

∎

We break the proof of the lower bound on $\dim(x,ax+b)$ into two parts. In the first, we give lower bounds on $K_{r}(x,ax+b)$ on the interval $r\in(sh_{j},h_{j}]$ . Note that this essentially follows from inequality (13).

Proposition 18.

Let $(a,b)$ be a slope intercept pair, $s\in(0,1)$ , $\gamma\in\mathbb{Q}$ be positive and $j$ be sufficiently large. Let $x=x_{a,b,s}$ be the point we have just constructed. Then

$K_{r}(x,ax+b)\geq(1+s-\gamma)r$

for all $sh_{j}<r\leq h_{j}$

Proof.

Let $j$ be sufficiently large and $sh_{j}<r\leq h_{j}$ . Then, by (13),

$K_{r}(x,ax+b)\geq(1+s)r-\gamma r$ .

∎

We now give lower bounds on $K_{r}(x,ax+b)$ on the interval $r\in(h_{j-1},sh_{j}]$ . The proof of this lemma is very similar to the analogous lemma for low-dimensional lines (Lemma 13). Intuitively, the proof is as follows. Using the previous lemma, we can, given a $2^{-h_{j}}$ -approximation of $(x,ax+b)$ , compute a $2^{-h_{j}}$ -approximation of $(a,b)$ with a small amount of extra bits. Having done so, we have to compute the last $r-h_{j}$ bits of $(a,b)$ . Importantly, since $r>h_{j}$ , the last $r-h_{j}$ bits of $x$ are maximal. Thus, we can simply lower the complexity of the last $r-h_{j}$ bits of $(a,b)$ so that the complexity of these bits is roughly $s(r-h_{j})$ . Thus, we are again, morally, in the case where $\dim(x)\geq\dim(a,b)$ and the techniques of Section 3.1 work. We now formalize this intuition.

Lemma 19.

Let $(a,b)$ be a slope intercept pair, $s\in(0,1)$ , $\gamma\in\mathbb{Q}$ be positive and $j$ be sufficiently large. Let $x=x_{a,b,s}$ be the point we have just constructed. Then

$K_{r}(x,ax+b)\geq(1+s-\gamma)r$

for all $h_{j-1}<r\leq sh_{j}$

Proof.

Intuitively, we will use the approximation of $(x,ax+b)$ at precision $h_{j-1}$ to compute $(a,b)$ at precision $h_{j-1}$ . Then we will only search for candidate lines within $2^{-h_{j-1}}$ of $(a,b)$ . Formally, the argument proceeds as follows.

We first show that we can compute $(a,b)$ to within $2^{-h_{j-1}}$ with an approximation of $(x,ax+b)$ , with few additional bits of information. By Lemma 2 and inequality (13)

$\displaystyle K_{h_{j-1},r}(a,b,x\,\|\,x,ax+b)$	$\displaystyle\leq K_{h_{j-1},h_{j-1}}(a,b,x\,\|\,x,ax+b)+O(\log h_{j}))$
	$\displaystyle=K_{h_{j-1}}(a,b,x)-K_{h_{j-1}}(x,ax+b)$	[Lemma 2]
	$\displaystyle\leq K_{h_{j-1}}(a,b,x)-(1+s)h_{j-1}+\frac{\gamma}{4}h_{j-1}$	[(13)]
	$\displaystyle=K_{h_{j-1}}(a,b)+K_{h_{j-1}}(x\mid a,b)$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-(1+s)h_{j-1}+\frac{\gamma}{4}h_{j-1}$	[Lemma 2]
	$\displaystyle\leq dh_{j-1}+h_{j}2^{-j}+K_{h_{j-1}}(x\mid a,b)$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-(1+s)h_{j-1}+\frac{\gamma h_{j-1}}{4}$	[Definition $h_{j}$ ]
	$\displaystyle\leq dh_{j-1}+h_{j}2^{-j}+sh_{j-1}$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-(1+s)h_{j-1}+\frac{\gamma h_{j-1}}{4}$	[Proposition 16]
	$\displaystyle\leq dh_{j}+sh_{j-1}$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;-(1+s)h_{j-1}+\frac{\gamma h_{j-1}}{2}$	[ $j$ large]
	$\displaystyle\leq dh_{j}-h_{j}+\frac{\gamma h_{j-1}}{2}.$	(14)

Thus, we can, given a $2^{-r}$ approximation of $(x,ax+b)$ , compute a $2^{-h_{j-1}}$ -approximation of $(a,b)$ with

$(d-1)h_{j}+\frac{\gamma h_{j-1}}{2}$

additional bits of information. Knowing $(a,b)$ to precision $h_{j-1}$ allows us to search for candidate lines within $2^{-h_{j-1}}$ of $(a,b)$ , i.e., using Lemma 6 with $m=h_{j-1}$ .

Let $\hat{s}\in\mathbb{Q}\cap(0,s)$ be a dyadic rational such that

$\gamma/8<s-\hat{s}<\gamma/4$ .

Let $\hat{d}\in\mathbb{Q}\cap(0,\dim(a,b))$ be a dyadic rational such that

$\gamma/8<\dim(a,b)-\hat{d}<\gamma/4$ .

Define

$\alpha=\frac{s(r-h_{j-1})+dh_{j-1}}{r}$ .

Define

$\eta=\frac{\hat{s}(r-h_{j-1})+\hat{d}h_{j-1}}{r}$ .

Finally, let $\varepsilon=\gamma^{2}/64$ . Note that

$\displaystyle\alpha-\eta$	$\displaystyle=\frac{s(r-h_{j-1})+dh_{j-1}-\hat{s}(r-h_{j-1})-\hat{d}h_{j-1}}{r}$
	$\displaystyle=\frac{(s-\hat{s})(r-h_{j-1})+(d-\hat{d})h_{j-1}}{r}$
	$\displaystyle\leq\frac{\frac{\gamma}{4}(r-h_{j-1})+\frac{\gamma}{4}h_{j-1}}{r}$
	$\displaystyle=\frac{\gamma}{4}$	(15)

Similarly,

$\displaystyle\alpha-\eta$	$\displaystyle=\frac{s(r-h_{j-1})+dh_{j-1}-\hat{s}(r-h_{j-1})-\hat{d}h_{j-1}}{r}$
	$\displaystyle=\frac{(s-\hat{s})(r-h_{j-1})+(d-\hat{d})h_{j-1}}{r}$
	$\displaystyle>\frac{\frac{\gamma}{8}(r-h_{j-1})+\frac{\gamma}{4}h_{j-1}}{r}$
	$\displaystyle=\frac{\gamma}{8}$	(16)

In particular,

\frac{4\varepsilon}{\alpha-\eta}\leq\gamma/4.

(17)

We also note that

K(\varepsilon,\eta)\leq K(\gamma,\hat{s},\hat{d},r,h_{j-1})\leq O(\log r),

(18)

since $j$ was chosen to be sufficiently large and $\gamma$ is constant.

Let $D=D(r,(a,b),\eta)$ be the oracle of Lemma 8. We now show that the conditions of Lemma 6 are satisfied for these choices $a,b,\eta,\varepsilon,r$ and $\delta=\alpha-\eta$ , $m=h_{j-1}$ and $A=D$ .

Let $(u,v)$ be a line such that $t:=\|(a,b)-(u,v)\|\geq h_{j-1}$ , and $ux+v=ax+b$ . Then, by Lemmas 7, 8, and Proposition 16,

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K^{D}_{t}(a,b)+K^{D}_{r-t,r}(x\,\|\,a,b)-O(\log r)$	[Lemma 7]
	$\displaystyle\geq K^{D}_{t}(a,b)+K_{r-t,r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle\geq K^{D}_{t}(a,b)+s(r-t)-O(\log r).$	[Proposition 16]

By Lemma 8, there are two cases. In the first, $K^{D}_{t}(a,b)=\eta r$ , and so

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K^{D}_{t}(a,b)+s(r-t)-O(\log r)$
	$\displaystyle=\eta r+s(r-t)-O(\log r)$
	$\displaystyle\geq(\eta-\varepsilon)r+s(r-t)$	[ $j$ is large]
	$\displaystyle\geq(\eta-\varepsilon)r+\delta(r-t)$	[ $\gamma$ is small]

In the second case, $K^{D}_{t}(a,b)=K_{t}(a,b)$ , and so

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K^{D}_{t}(a,b)+s(r-t)-O(\log r)$
	$\displaystyle\geq dt-o(t)+s(r-t)-O(\log r)$	[Definition of $\dim$ ]
	$\displaystyle=dh_{j-1}+d(t-h_{j-1})+s(r-t)-o(r)$
	$\displaystyle=dh_{j-1}+d(t-h_{j-1})+s(r-h_{j-1})-s(t-h_{j-1})-o(r)$
	$\displaystyle=\alpha r+d(t-h_{j-1})-s(t-h_{j-1})-o(r)$	[Definition of $\alpha$ ]
	$\displaystyle=\eta r+(\alpha-\eta)r+(d-s)(t-h_{j-1})-o(r)$
	$\displaystyle\geq\eta r+(\alpha-\eta)r-o(r)$	[ $d>1$ , $t>h_{j-1}$ ]
	$\displaystyle\geq\eta r+(\alpha-\eta)(r-t)-o(r)$	[ $\alpha>\eta$ ]
	$\displaystyle\geq(\eta-\varepsilon)r+\delta(r-t)$	[ $j$ is large]

Therefore, in either case, we may apply Lemma 6, relative to $D$ which yields

$\displaystyle K^{D}_{r}(a,b,x)$	$\displaystyle\leq K_{r}(x,ax+b)+K_{h_{j},r}(a,b,x\,\|\,x,ax+b)$
	$\displaystyle\;\;\;\;\;\;\;+\frac{4\varepsilon}{\alpha-\eta}r+K(\varepsilon,\eta)+O(\log r)$	[Lemma 6]
	$\displaystyle\leq K_{r}(x,ax+b)+dh_{j}-h_{j}+\frac{\gamma h_{j-1}}{2}$
	$\displaystyle\;\;\;\;\;\;\;+\frac{4\varepsilon}{\alpha-\eta}r+K(\varepsilon,\eta)+O(\log r)$	[(14)]
	$\displaystyle\leq K_{r}(x,ax+b)+dh_{j}-h_{j}+\frac{\gamma h_{j-1}}{2}$
	$\displaystyle\;\;\;\;\;\;\;+\frac{4\varepsilon}{\alpha-\eta}r+O(\log r)$	[(18)]
	$\displaystyle\leq K_{r}(x,ax+b)+dh_{j}-h_{j}+\frac{\gamma h_{j-1}}{2}$
	$\displaystyle\;\;\;\;\;\;\;+\frac{\gamma r}{4}+O(\log r)$	[(17)]
	$\displaystyle\leq K_{r}(x,ax+b)+dh_{j}-h_{j}+\frac{3\gamma r}{4}+O(\log r)$	(20)

By Lemma 11, and our construction of oracle $D$ ,

$\displaystyle K_{r}^{D}(a,b,x)$	$\displaystyle=K_{r}^{D}(a,b)+K_{r}^{D}(x\,\|\,a,b)-O(\log r)$	[Lemma 2]
	$\displaystyle=\eta r+K_{r}(x\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle\geq\eta r+sh_{j}+r-h_{j}-O(\log r)$	[Lemma 11(2)]
	$\displaystyle\geq\alpha r-\frac{\gamma}{4}r+sh_{j}+r-h_{j}-O(\log r)$
	$\displaystyle\geq s(r-h_{j})+dh_{j}-\frac{\gamma}{4}r+sh_{j}+r-h_{j}-O(\log r)$
	$\displaystyle\geq(1+s)r-(1-d)h_{j}-\frac{\gamma}{4}r.$	(21)

Rearranging (20) and combining this with (21), we see that

$\displaystyle K_{r}(x,ax+b)$	$\displaystyle\geq K^{D}_{r}(a,b,x)-dh_{j}+h_{j}-\frac{3\gamma r}{4}-O(\log r)$	[(20)]
	$\displaystyle\geq(1+s)r-(1-d)h_{j}-\frac{\gamma}{4}r$
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-dh_{j}+h_{j}-\frac{3\gamma r}{4}-O(\log r)$	[(21)]
	$\displaystyle=(1+s)r-\gamma r-O(\log r)$

∎

We are now able to prove that the Dimension Spectrum Conjecture holds for high dimensional lines.

Proof of Theorem 14.

Let $(a,b)\in\mathbb{R}^{2}$ be a slope-intercept pair with

$d=\dim(a,b)>1$ .

Let $s\in[0,1]$ . In the case where $s=0$ , Turetsky showed (Theorem 1) that $1\in\operatorname{sp}(L_{a,b})$ , i.e., there is a point $x$ such that $\dim(x,ax+b)=1$ . In the case where $s=1$ , Lutz and Stull [11] showed than any point $x$ which is random relative to $(a,b)$ satisfies

$\dim(x,ax+b)=2$ .

Therefore, we may assume that $s\in(0,1)$ . Let $x=x_{a,b,s}$ be the point constructed in this section. By Propositions 17 and 18 and Lemma 19, for every $\gamma$ ,

$|\dim(x,ax+b)-(1+s)|<\gamma$ .

Thus, by the definition of effective dimension,

$\dim(x,ax+b)=1+s$ ,

and the proof is complete. ∎

5.3 Proof of Lemma 15

To complete the proof of the main theorem of this section, we now prove Lemma 15. Recall that this states that, for every $j$ , after setting $\mathbf{x}[h_{j-1}\ldots sh_{j}]=\mathbf{y}[h_{j-1}\ldots sh_{j}]$ , the following holds.

Lemma 15. For every sufficiently large $j$ there is a binary string $\mathbf{z}$ of length $h_{j}-sh_{j}$ such that

\min\limits_{sh_{j}<r\leq h_{j}}\left|K_{r}(x,ax+b)-(1+s)r\right|<\frac{r}{j},

where $x$ is any real such that $\mathbf{x}\mathbf{z}\prec x$ . Moreover, $\mathbf{z}$ is of the form (*) of Section 5.1.

Let $m=h_{j}-sh_{j}$ . For each $0\leq n\leq m$ , define the binary string $\mathbf{x_{n}}$ of length $m$ by

\displaystyle\mathbf{x_{n}}[i]=\begin{cases}0&\text{ if }0\leq i<m-n\\ \frac{1}{a}[i-(m-n)]&\text{ if }m-n\leq i\leq m\end{cases}

Thus, for example $\mathbf{x_{0}}$ is the binary string of $m$ zeros, while $\mathbf{x_{m}}$ is the binary string containing the $m$ -bit prefix of $\frac{1}{a}$ .

Let $x$ be the real number such that $\mathbf{x}\mathbf{x_{0}}\prec x$ , and whose binary expansion contains only zeros after $sh_{j}$ . For each $1\leq n\leq m$ , let $x_{n}$ be the real number defined by

$x_{n}=x+2^{-h_{j}+n}/a$ .

Therefore, for every $n$ ,

$(x_{n},ax_{n}+b)=(x_{n},ax+b+2^{-h_{j}+n})$ .

Since the binary expansion of $x$ satisfies $x[r]=0$ for all $r\geq sh_{j}$ , we have, for every $n$ ,

\mathbf{x}\mathbf{x_{n}}\prec x_{n}

(22)

In other words, the binary expansion of $x_{n}$ up to index $h_{j}$ is just the concatenation of $\mathbf{x}$ and $\mathbf{x_{n}}$ .

We now collect a few facts about our points $x_{n}$ .

Lemma 20.

For every $n,r$ such that $0\leq n\leq m$ and $sh_{j}\leq r\leq h_{j}$ the following hold.

1.

$K_{n,h_{j}}(a\,|\,x_{n})\leq O(\log h_{j})$ .
2.

For every $n$ and $n^{\prime}>n$ ,

$|K_{r}(x_{n^{\prime}},ax_{n^{\prime}}+b)-K_{r}(x_{n},ax_{n}+b)|<n^{\prime}-n+\log(r)$ .
3.

$K_{r-sh_{j},r}(a,b\mid x_{m},ax_{m}+b)\leq O(\log r)$ .

Note that the constants implied by the big oh notation depend only on $a$ .

Proof.

From the definition of $\mathbf{x_{n}}$ ,

$\mathbf{x_{n}}[(m-n)\ldots m]=\frac{1}{a}[0\ldots n]$ .

Since the map $a\mapsto\frac{1}{a}$ is bi-Lipschitz on an interval, there some constant $c$ depending only on $a$ , such that we can compute a $2^{-n+c}$ -approximation of $a$ given the first $n$ bits of $1/a$ . Thus, by Corollary 5,

$\displaystyle K_{n,h_{j}}(a\mid x_{n})$	$\displaystyle=K(a{\upharpoonright}n\mid x_{n}{\upharpoonright}h_{j})+O(\log h_{j})$	[Corollary 5]
	$\displaystyle=K(a{\upharpoonright}n\mid\mathbf{x}\mathbf{x_{n}})+O(\log h_{j})$	[(22)]
	$\displaystyle\leq K(a{\upharpoonright}n\mid\mathbf{x_{n}})+O(\log h_{j})$
	$\displaystyle\leq O(\log h_{j}).$

For item (2), let $n^{\prime}>n$ . We first assume that $r<h_{j}-n^{\prime}$ . Then

	$\displaystyle\|x_{n^{\prime}}-x_{n}\|$	$\displaystyle=x+2^{-h_{j}+n^{\prime}}/a-(x+2^{-h_{j}+n}/a)$
		$\displaystyle=2^{-h_{j}}(2^{n^{\prime}}-2^{n})/a)$
		$\displaystyle=2^{-h_{j}+n^{\prime}}(1-2^{n-n^{\prime}})/a$
		$\displaystyle\leq 2^{-h_{j}+n^{\prime}}/2a$
		$\displaystyle\leq O(2^{-h_{j}+n^{\prime}}).$

Thus,

	$\displaystyle\\|(x_{n^{\prime}},ax_{n^{\prime}}+b)-(x_{n},ax_{n}+b)\\|$	$\displaystyle=\\|(x_{n^{\prime}},ax+b+2^{-h_{j}+n^{\prime}})$
		$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;-(x_{n},ax+b+2^{-h_{j}+n^{\prime}})\\|$
		$\displaystyle\leq O(2^{-h_{j}+n^{\prime}}).$

Therefore, under our assumption that $r<h_{j}-n^{\prime}$ ,

$K_{r}(x_{n^{\prime}},ax_{n^{\prime}}+b)=K_{r}(x_{n},ax_{n}+b)-O(1)$ ,

and the claim follows. Now assume that $r\geq h_{j}-n^{\prime}$ . By Corollary 4,

	$\displaystyle K_{r}(x_{n^{\prime}},ax_{n^{\prime}}+b)$	$\displaystyle=K_{r}(x_{n^{\prime}},ax+b+2^{-h_{j}+n^{\prime}})$
		$\displaystyle=K_{r}(\mathbf{x}\mathbf{x_{n^{\prime}}},ax+b+2^{-h_{j}+n^{\prime}}).$

Similarly,

	$\displaystyle K_{r}(x_{n},ax_{n}+b)$	$\displaystyle=K_{r}(x_{n},ax+b+2^{-h_{j}+n})$
		$\displaystyle=K_{r}(\mathbf{x}\mathbf{x_{n}},ax+b+2^{-h_{j}+n}).$

By our definition of $\mathbf{x_{n}}$ and $\mathbf{x_{n^{\prime}}}$ , $\mathbf{x_{n^{\prime}}}$ contains all the bits of $\frac{1}{a}$ that $\mathbf{x_{n}}$ has. Thus,

$K(\mathbf{x_{n}}{\upharpoonright}r\mid\mathbf{x_{n^{\prime}}}{\upharpoonright}r)=O(\log n^{\prime})$ .

Given the first $r$ bits of $\mathbf{x_{n}}$ , we can compute the first $r$ bits of $\mathbf{x_{n^{\prime}}}$ by simply giving the $n^{\prime}-n$ bits of $\frac{1}{a}$ that $\mathbf{x_{n^{\prime}}}$ contains but $\mathbf{x_{n}}$ does not. Thus,

$K(\mathbf{x_{n^{\prime}}}{\upharpoonright}r\mid\mathbf{x_{n}}{\upharpoonright}r)\leq n^{\prime}-n+O(\log n^{\prime})$ .

Similarly, since $ax_{n}+b$ and $ax_{n^{\prime}}+b$ are translates of each other, to compute one given the other, we just need to give the logarithm of their distance. Therefore,

	$\displaystyle K_{r}(ax+b+2^{-h_{j}+n^{\prime}}\,\|\,ax+b+2^{-h_{j}+n})$	$\displaystyle\leq O(\log h_{j}+\log n^{\prime})$
	$\displaystyle K_{r}(ax+b+2^{-h_{j}+n}\,\|\,ax+b+2^{-h_{j}+n^{\prime}})$	$\displaystyle\leq O(\log h_{j}+\log n^{\prime})$

Taken together, these four inequalities show that

	$\displaystyle K_{r}(x_{n},ax_{n}+b\mid x_{n^{\prime}},ax_{n^{\prime}}+b)$	$\displaystyle=K_{r}(x_{n}\mid x_{n^{\prime}},ax_{n^{\prime}}+b)$
		$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+K_{r}(ax_{n}+b\mid x_{n^{\prime}},ax_{n^{\prime}}+b)$
		$\displaystyle\leq O(\log n^{\prime})+O(\log h_{j}+\log n^{\prime}).$

Similarly,

	$\displaystyle K_{r}(x_{n^{\prime}},ax_{n^{\prime}}+b\mid x_{n},ax_{n}+b)$	$\displaystyle=K_{r}(x_{n^{\prime}}\mid x_{n},ax_{n}+b)$
		$\displaystyle\;\;\;\;\;\;\;\;\;\;\;+K_{r}(ax_{n^{\prime}}+b\mid x_{n},ax_{n}+b)$
		$\displaystyle\leq n^{\prime}-n+O(\log n^{\prime})+O(\log h_{j}+\log n^{\prime}),$

and the proof of the second item is complete.

For item (3), note that the first $r$ bits of $x_{m}$ ,

$x_{m}{\upharpoonright}r=\mathbf{x}\mathbf{x_{m}}[0\ldots(r-sh_{j})]$ .

By definition, $\mathbf{x_{m}}[0\ldots(r-sh_{j})]=\frac{1}{a}[0\ldots(r-sh_{j})]$ . Thus, given a $2^{-r}$ approximation of $x_{m}$ , we can compute a $2^{-r+sh_{j}+c}$ -approximation of $a$ . Finally, given a $2^{-r+sh_{j}+c}$ -approximation of $x_{m}$ , $a$ and $ax_{m}+b$ , we can compute a $2^{-r+sh_{j}+c}$ -approximation of $b$ . ∎

Poof of Lemma 15.

The proof of this lemma is essentially (a discrete, approximate, version of) the mean value theorem. In particular, we will show that $x_{0}$ satisfies

$K_{r}(x_{0},ax_{0}+b)\leq(1+s)r$ ,

for every $r\in[sh_{j},h_{j}]$ , and $x_{m}$ satisfies

$K_{r}(x_{m},ax_{m}+b)\geq(1+s)r$ ,

for every $r\in[sh_{j},h_{j}]$ . By Lemma 20, the map $n\mapsto K_{r}(x_{n},ax_{n}+b)$ is “continuous”, and therefore there must be a point $x_{n}$ which satisfies

$\min\limits_{sh_{j}<r\leq h_{j}}\left|K_{r}(x,ax+b)-(1+s)r\right|<\frac{r}{j}$ .

We now formalize this intuition. For each $n$ , define

$M_{n}=\min\{\frac{K_{r}(x_{n},ax_{n}+b)}{r}\,|\,sh_{j}\leq r\leq h_{j}\}$ .

To prove our theorem, it suffices to show that there is an $n$ such that

1+s-\frac{1}{j}\leq M_{n}\leq 1+s+\frac{1}{j}.

To begin, note, by our construction of $h_{j}$ , $j<\log h_{j}$ . We also note that $K_{h_{j}}(x_{0})\leq sh_{j}$ , since the bits of $x_{0}$ after $sh_{j}$ are all zero. Therefore,

$\displaystyle K_{h_{j}}(x_{0},ax_{0}+b)$	$\displaystyle=K_{h_{j}}(x_{0})+K_{h_{j}}(ax_{0}+b\mid x_{0})+O(\log h_{j})$	[Lemma 2]
	$\displaystyle\leq sh_{j}+K_{h_{j}}(ax_{0}+b\mid x_{0})+O(\log h_{j})$
	$\displaystyle\leq sh_{j}+K_{h_{j}}(ax_{0}+b)+O(\log h_{j})$
	$\displaystyle\leq sh_{j}+h_{j}+O(\log h_{j})$

where the constant of the $O(\log h_{j})$ term is independent of $x_{0}$ . Thus, $M_{0}<1+s+\frac{1}{j}$ , for all $j$ such that $\frac{h_{j}}{j}>O(\log h_{j})$ .

We now show that

$K_{r}(x_{m},ax_{m}+b)\geq(1+s)r-\frac{r}{j}$ ,

for all sufficiently large $j$ , and for every $sh_{j}\leq r\leq h_{j}$ .

Let $sh_{j}\leq r\leq h_{j}$ , $\eta=1-\frac{1}{2j}$ and let $D=D(r,(a,b),\eta$ . Let $\epsilon=\frac{1}{32j^{2}}$ and $\delta=1-\eta$ . We now show that the conditions of Lemma 6 are satisfied.

Let $(u,v)$ be a line such that $t:=\|(a,b)-(u,v)\|\geq r-sh_{j}$ , and $ux_{m}+v=ax_{m}+b$ . Note that $r-t\leq sh_{j}$ . Then, by Lemma 7, Lemma 8 and Lemma 11(1),

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K^{D}_{t}(a,b)+K^{D}_{r-t,r}(x_{m}\,\|\,a,b)-O(\log r)$	[Lemma 7]
	$\displaystyle\geq K^{D}_{t}(a,b)+K_{r-t,r}(x_{m}\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle=\min\{\eta r,K_{t}(a,b)\}+K_{r-t,r}(x_{m}\,\|\,a,b)-O(\log r)$	[Lemma 8]
	$\displaystyle=\min\{\eta r,K_{t}(a,b)\}+r-t-O(\log r).$	[construction of $x$ ]

There are two cases guaranteed by Lemma 8. If $\eta r\leq K_{t}(a,b)$ , then

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq\eta r+r-t-O(\log r)$
	$\displaystyle\geq(\eta-\epsilon)r+r-t$	[ $j$ is large]
	$\displaystyle\geq(\eta-\epsilon)r+\delta(r-t),$	[ $\delta<1$ ]

since $\varepsilon r\geq O(\log r)$ . Hence, we may apply Lemma 6 in this case. Otherwise, $K^{D}_{t}(a,b)=K_{t}(a,b)$ . Then

$\displaystyle K^{D}_{r}(u,v)$	$\displaystyle\geq K_{t}(a,b)+r-t-O(\log r)$
	$\displaystyle\geq(d-2^{-j})t+r-t-O(\log r)$	[Definition of $h_{j}$ ]
	$\displaystyle=\eta r+(1-\eta)r-t(1+2^{-j}-d)-O(\log r)$
	$\displaystyle\geq\eta r+(1-\eta)r-t(1-\eta)-O(\log r)$
	$\displaystyle=\eta r+\delta(r-t)-O(\log r)$
	$\displaystyle\geq(\eta-\varepsilon)r+\delta(r-t).$

Therefore we may apply Lemma 6.

$\displaystyle K_{r}(x_{m},ax_{m}+b)$	$\displaystyle\geq K_{r}^{D}(a,b,x_{m})-K_{r-sh_{j},r}(a,b\,\|,x_{m},ax_{m}+b)$	[Lemma 6]
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\frac{4\varepsilon}{1-\eta}r-K(\epsilon,\eta)-O(\log r)$
	$\displaystyle=K_{r}^{D}(a,b,x_{m})-O(\log r)$	[Lemma 20(3)]
	$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\frac{4\varepsilon}{1-\eta}r-K(\epsilon,\eta)-O(\log r)$
	$\displaystyle=K_{r}^{D}(a,b,x_{m})-O(\log r)-\frac{1/8j^{2}}{1/2j}r-K(\epsilon,\eta)-O(\log r)$
	$\displaystyle=K_{r}^{D}(a,b,x_{m})-O(\log r)-\frac{r}{4j}-K(\epsilon,\eta)-O(\log r)$
	$\displaystyle=K_{r}^{D}(a,b,x_{m})-O(\log r)-\frac{r}{4j}-K(j)-O(\log r)$
	$\displaystyle=K_{r}^{D}(a,b,x_{m})-\frac{r}{4j}-O(\log r)$
	$\displaystyle=K_{r}^{D}(a,b,x_{m})-\frac{r}{2j}.$

By our construction of oracle $D$ , and the symmetry of information,

$\displaystyle K_{r}^{D}(a,b,x_{m})$	$\displaystyle=K_{r}^{D}(a,b)+K_{r}^{D}(x_{m}\,\|\,a,b)-O(\log r)$	[Lemma 2]
	$\displaystyle=K_{r}^{D}(a,b)+K_{r}(x_{m}\,\|\,a,b)-O(\log r)$	[Lemma 8(ii)]
	$\displaystyle\geq\eta r+K_{r}(x_{m}\,\|\,a,b)-O(\log r)$	[Lemma 8(i)]
	$\displaystyle\geq\eta r+sh_{j}-O(\log r).$	(23)

Therefore, we have

	$\displaystyle K_{r}(x_{m},ax_{m}+b)$	$\displaystyle\geq\eta r+sh_{j}-O(\log r)-\frac{r}{2j}$
		$\displaystyle\geq(1+s)r-\frac{r}{2j}-\frac{r}{2j}$
		$\displaystyle>(1+s)r-\frac{r}{j}.$

Thus we have shown that

$K_{r}(x_{m},ax_{m}+b)>(1+s)r-\frac{r}{j}$ ,

for every $sh_{j}\leq r\leq h_{j}$ .

If either

•

$M_{m}\leq(1+s)+\frac{1}{j}$ , or
•

$M_{0}\geq(1+s)-\frac{1}{j}$

our claim would follow. We will therefore assume that

$M_{0}<1+s-\frac{1}{j}$ , and $1+s+\frac{1}{j}<M_{m}$ .

Define

	$\displaystyle L$	$\displaystyle=\{n\,\|\,M_{n}<1+s-\frac{1}{j}\}$
	$\displaystyle G$	$\displaystyle=\{n\,\|\,M_{n}>1+s+\frac{1}{j}\}.$

By our assumption, $L$ and $G$ are non-empty. Suppose that $L$ and $G$ partition $\{0,\ldots,m\}$ . Then there is a $n$ such that $n\in L$ and $n+1\in G$ . However, by Lemma 20,

$|K_{r}(x_{n+1},ax_{n+1}+b)-K_{r}(x_{n},ax_{n}+b)|\leq 1+O(\log r)$ ,

for every $r$ . Let $r$ be a precision testifying to $x_{n}\in L$ . Then

	$\displaystyle(1+s-\frac{1}{j})r$	$\displaystyle>K_{r}(x_{n},ax_{n}+b)$
		$\displaystyle>K_{r}(x_{n+1},ax_{n+1}+b)-1-O(\log r).$

That is,

	$\displaystyle\frac{K_{r}(x_{n+1},ax_{n+1}+b)}{r}$	$\displaystyle<1+s-\frac{1}{j}+\frac{1}{r}+\frac{O(\log r)}{r}$
		$\displaystyle<1+s+\frac{1}{j},$

which contradicts our assumption that $x_{n+1}\in G$ and the proof is complete. ∎

6 Conclusion and Future Directions

The behavior of the effective dimension of points on a line is not only interesting from the algorithmic randomness viewpoint, but also because of its deep connections to geometric measure theory. There are many avenues for future research in this area.

The results of this paper show that, for any line $L_{a,b}$ , the dimension spectrum $\operatorname{sp}(L_{a,b})$ contains a unit interval. However, this is not, in general, a tight bound. It would be very interesting to have a more thorough understanding of the “low end” of the dimension spectrum. Stull [17] showed that the Hausdorff dimension of points $x$ such that

$\dim(x,ax+b)\leq\alpha+\frac{\dim(a,b)}{2}$

is at most $\alpha$ . Further investigation of the low-end of the spectrum is needed.

It seems plausible that, for certain lines, the dimension spectrum contains an interval of length greater than one. For example, are there lines in the plane such that $\operatorname{sp}(L)$ contains an interval of length strictly greater than $1$ ?

Another interesting direction is to study the dimension spectrum of particular classes of lines. One natural class is the lines $L_{a,b}$ whose slope and intercept are both in the Cantor set. By restricting the lines to the Cantor set, or, more generally, self-similar fractals, might give enough structure to prove tight bounds not possible in the general case.

Additionally, the focus has been on the effective (Hausdorff) dimension of points. Very little is known about the effective strong dimension of points on a line. The known techniques do not seem to apply to this question. New ideas are needed to understand the strong dimension spectrum of planar lines.

Finally, it would be interesting to broaden this direction by considering the dimension spectra of other geometric objects. For example, can anything be said about the dimension spectrum of a polynomial?

References

[1] Randall Dougherty, Jack Lutz, R Daniel Mauldin, and Jason Teutsch. Translating the Cantor set by a random real. Transactions of the American Mathematical Society, 366(6):3027–3041, 2014.
[2] Rod Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010.
[3] Xiaoyang Gu, Jack H Lutz, Elvira Mayordomo, and Philippe Moser. Dimension spectra of random subfractals of self-similar fractals. Annals of Pure and Applied Logic, 165(11):1707–1726, 2014.
[4] Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008.
[5] Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236–1259, 2003.
[6] Jack H. Lutz. The dimensions of individual strings and sequences. Inf. Comput., 187(1):49–79, 2003.
[7] Jack H. Lutz and Neil Lutz. Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory, 10(2):Art. 7, 22, 2018.
[8] Jack H Lutz and Neil Lutz. Who asked us? how the theory of computing answers questions about analysis. In Complexity and Approximation, pages 48–56. Springer, 2020.
[9] Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM J. Comput., 38(3):1080–1112, 2008.
[10] Neil Lutz. Fractal intersections and products via algorithmic dimension. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 2017.
[11] Neil Lutz and D. M. Stull. Bounding the dimension of points on a line. In Theory and applications of models of computation, volume 10185 of Lecture Notes in Comput. Sci., pages 425–439. Springer, Cham, 2017.
[12] Neil Lutz and D. M. Stull. Dimension spectra of lines. In Unveiling dynamics and complexity, volume 10307 of Lecture Notes in Comput. Sci., pages 304–314. Springer, Cham, 2017.
[13] Neil Lutz and D. M. Stull. Projection theorems using effective dimension. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 2018.
[14] Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett., 84(1):1–3, 2002.
[15] Elvira Mayordomo. Effective fractal dimension in algorithmic information theory. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 259–285. Springer New York, 2008.
[16] Andre Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009.
[17] D. M. Stull. Results on the dimension spectra of planar lines. In 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 79, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
[18] Daniel Turetsky. Connectedness properties of dimension level sets. Theor. Comput. Sci., 412(29):3598–3603, 2011.

	$\displaystyle K_{r-sh_{j},r}(a,b\,\|\,x,ax+b)$	$\displaystyle=K_{r-sh_{j},r}(a\,\|\,x,ax+b)$
		$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+K_{r-sh_{j},r}(b\,\|\,a,x,ax+b)+O(\log r)$
		$\displaystyle\leq O(\log h_{j})+K_{r-sh_{j},r}(b\,\|\,a,x,ax+b)+O(\log r)$
		$\displaystyle\leq O(\log h_{j}).$

	$\displaystyle\\|(x_{n^{\prime}},ax_{n^{\prime}}+b)-(x_{n},ax_{n}+b)\\|$	$\displaystyle=\\|(x_{n^{\prime}},ax+b+2^{-h_{j}+n^{\prime}})$
		$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;-(x_{n},ax+b+2^{-h_{j}+n^{\prime}})\\|$
		$\displaystyle\leq O(2^{-h_{j}+n^{\prime}}).$

The Dimension Spectrum Conjecture for Planar Lines

Abstract

1 Introduction

Theorem 1 (Turetsky [18]).

2 Preliminaries

Lemma 2.

2.1 Initial segments versus KK-optimizing rationals

Lemma 3.

Corollary 4.

Corollary 5.

3 Previous Work

Lemma 6 (Lutz and Stull [11]).

Lemma 7 ([11]).

Lemma 8 ([11]).

3.1 Combining the lemmas

4 Low-Dimensional Lines

Theorem 9.

4.1 Overview of the proof

4.2 Proof for low-dimensional lines

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof.

Lemma 13.

Proof.

Proof of Theorem 9.

5 High-Dimensional Lines

Theorem 14.

5.1 Overview of proof

5.2 Proof for high-dimensional lines

Lemma 15.

Proposition 16.

Proof.

Proposition 17.

Proof.

Proposition 18.

Proof.

Lemma 19.

Proof.

Proof of Theorem 14.

5.3 Proof of Lemma 15

Lemma 20.

Proof.

Poof of Lemma 15.

6 Conclusion and Future Directions

References

2.1 Initial segments versus $K$ -optimizing rationals