Optimal Oracles for Point-to-Set Principles

D. M. Stull
Department of Computer Science, Iowa State University
Ames, IA 50011, USA
[email protected]

Abstract

The point-to-set principle [14] characterizes the Hausdorff dimension of a subset $E\subseteq\mathbb{R}^{n}$ by the effective (or algorithmic) dimension of its individual points. This characterization has been used to prove several results in classical, i.e., without any computability requirements, analysis. Recent work has shown that algorithmic techniques can be fruitfully applied to Marstrand’s projection theorem, a fundamental result in fractal geometry.

In this paper, we introduce an extension of point-to-set principle - the notion of optimal oracles for subsets $E\subseteq\mathbb{R}^{n}$ . One of the primary motivations of this definition is that, if $E$ has optimal oracles, then the conclusion of Marstrand’s projection theorem holds for $E$ . We show that every analytic set has optimal oracles. We also prove that if the Hausdorff and packing dimensions of $E$ agree, then $E$ has optimal oracles. Moreover, we show that the existence of sufficiently nice outer measures on $E$ implies the existence of optimal Hausdorff oracles. In particular, the existence of exact gauge functions for a set $E$ is sufficient for the existence of optimal Hausdorff oracles, and is therefore sufficient for Marstrand’s theorem. Thus, the existence of optimal oracles extends the currently known sufficient conditions for Marstrand’s theorem to hold.

Under certain assumptions, every set has optimal oracles. However, assuming the axiom of choice and the continuum hypothesis, we construct sets which do not have optimal oracles. This construction naturally leads to a generalization of Davies theorem on projections.

1 Introduction

Effective, i.e., algorithmic, dimensions were introduced [12, 1] to study the randomness of points in Euclidean space. The effective dimension, $\dim(x)$ and effective strong dimension, $\operatorname{Dim}(x)$ , are real values which measure the asymptotic density of information of an individual point $x$ . The connection between effective dimensions and the classical Hausdorff and packing dimension is given by the point-to-set principle of J. Lutz and N. Lutz [14]: For any $E\subseteq\mathbb{R}^{n}$ ,

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\min\limits_{A\subseteq\mathbb{N}}\sup_{x\in E}\dim^{A}(x),\text{ and}$		(1)
	$\displaystyle\dim_{P}(E)$	$\displaystyle=\min\limits_{A\subseteq\mathbb{N}}\sup_{x\in E}\operatorname{Dim}^{A}(x)\,.$		(2)

Call an oracle $A$ satisfying (1) a Hausdorff oracle for $E$ . Similarly, we call an oracle $A$ satisfying (2) a packing oracle for $E$ . Thus, the point-to-set principle shows that the classical notion of Hausdorff or packing dimension is completely characterized by the effective dimension of its individual points, relative to a Hausdorff or packing oracle, respectively.

Recent work as shown that algorithmic dimensions are not only useful in effective settings, but, via the point-to-set principle, can be used to solve problems in geometric measure theory [15, 17, 18, 29]. It is important to note that the point-to-set principle allows one to use algorithmic techniques to prove theorems whose statements have seemingly nothing to do with computability theory. In this paper, we focus on the connection between algorithmic dimension and Marstrand’s projection theorem.

Marstrand, in his landmark paper [20], was the first to study how the dimension of a set is changed when projected onto a line. He showed that, for any analytic set $E\in\mathbb{R}^{2}$ , for almost every angle $\theta\in[0,\pi)$ ,

\dim_{H}(p_{\theta}\,E)=\min\{\dim_{H}(E),1\},

(3)

where $p_{\theta}(x,y)=x\cos\theta+y\sin\theta$ ¹¹1This result was later generalized to $\mathbb{R}^{n}$ , for arbitrary $n$ , as well as extended to hyperspaces of dimension $m$ , for any $1\leq m\leq n$ (see e.g. [21, 22, 23]).. The study of projections has since become a central theme in fractal geometry (see [8] or [24] for a more detailed survey of this development).

Marstrand’s theorem begs the question of whether the analytic requirement on $E$ can be dropped. It is known that, without further conditions, it cannot. Davies [5] showed that, assuming the axiom of choice and the continuum hypothesis, there are non-analytic sets for which Marstrands conclusion fails. However, the problem of classifying the sets for which Marstrands theorem does hold is still open. Recently, Lutz and Stull [19] used the point-to-set principle to prove that the projection theorem holds for sets for which the Hausdorff and packing dimensions agree²²2Orponen [28] has recently given another proof of Lutz and Stull’s result using more classical tools.. This expanded the reach of Marstrand’s theorem, as this assumption is incomparable with analyticity.

In this paper, we give the broadest known sufficient condition (which makes essential use of computability theory) for Marstrand’s theorem. In particular, we introduce the notion of optimal Hausdorff oracles for a set $E\subseteq\mathbb{R}^{n}$ . We prove that Marstrand’s theorem holds for every set $E$ which has optimal Hausdorff oracles.

An optimal Hausdorff oracle for a set $E$ is a Hausdorff oracle which minimizes the algorithmic complexity of ”most“³³3By most, we mean a subset of $E$ of the same Hausdorff dimension as $E$ points in $E$ . It is not immediately clear that any set $E$ has optimal oracles. Nevertheless, we show that two natural classes of sets $E\subseteq\mathbb{R}^{n}$ do have optimal oracles.

We show that every analytic, and therefore Borel, set has optimal oracles. We also prove that every set whose Hausdorff and packing dimensions agree has optimal Hausdorff oracles. Thus, we show that the existence of optimal oracles encapsulates the known conditions sufficient for Marstrand’s theorem to hold. Moreover, we show that the existence of sufficiently nice outer measures on $E$ implies the existence of optimal Hausdorff oracles. In particular, the existence of exact gauge functions (Section 2.1) for a set $E$ is sufficient for the existence of optimal Hausdorff oracles for $E$ , and is therefore sufficient for Marstrand’s theorem. Thus, the existence of optimal Hausdorff oracles is weaker than the previously known conditions for Marstrand’s theorem to hold.

We also show that the notion of optimal oracles gives insight to sets for which Marstrand’s theorem does not hold. Assuming the axiom of choice and the continuum hypothesis, we construct sets which do not have optimal oracles. This construction, with minor adjustments, proves a generalization of Davies theorem proving the existence of sets for which (3) does not hold. In addition, the inherently algorithmic aspect of the construction might be useful for proving set-theoretic properties of exceptional sets for Marstrand’s theorem.

Finally, we define optimal packing oracles for a set. We show that every analytic set $E$ has optimal packing oracles. We also show that every $E$ whose Hausdorff and packing dimensions agree have optimal packing oracles. Assuming the axiom of choice and the continuum hypothesis, we show that there are sets with optimal packing oracles without optimal Hausdorff oracles (and vice-versa).

The structure of the paper is as follows. In Section 2.1 we review the concepts of measure theory needed, and the (classical) definition of Hausdorff dimension. In Section 2.2 we review algorithmic information theory, including the formal definitions of effective dimensions. We then introduce and study the notion of optimal oracles in Section 3. In particular, we give a general condition for the existence of optimal oracles in Section 3.1. We use this condition to prove that analytic sets have optimal oracles in Section 3.2. We conclude in Section 3.3 with an example, assuming the axiom of choice and the continuum hypothesis, of a set without optimal oracles. The connection between Marstrands projection theorem and optimal oracles is explored in Section 4. In this section, we prove that Marstrands theorem holds for every set with optimal oracles. In Section 4.1, we use the construction of a set without optimal oracles to give a new, algorithmic, proof of Davies theorem. Finally, in Sectino 5, we define and investigate the notion of optimal packing oracles.

2 Preliminaries

2.1 Outer Measures and Classical Dimension

A set function $\mu:\mathcal{P}(\mathbb{R}^{n})\to[0,\infty]$ is called an outer measure on $\mathbb{R}^{n}$ if

1.

$\mu(\emptyset)=0$ ,
2.

if $A\subseteq B$ then $\mu(A)\leq\mu(B)$ , and
3.

for any sequence $A_{1},A_{2},\ldots$ of subsets,

$\mu(\bigcup_{i}A_{i})\leq\sum_{i}\mu(A_{i})$ .

If $\mu$ is an outer measure, we say that a subset $A$ is $\mu$ -measurable if

$\mu(A\cap B)+\mu(B-A)=\mu(B)$ ,

for every subset $B\subseteq\mathbb{R}^{n}$ .

An outer measure $\mu$ is called a metric outer measure if every Borel subset is $\mu$ -measurable and

$\mu(A\cup B)=\mu(A)+\mu(B)$ ,

for every pair of subsets $A,B$ which have positive Hausdorff distance. That is,

$\inf\{\|x-y\|\,|\,x\in A,y\in B\}>0$ .

An important example of a metric outer measure is the $s$ -dimensional Hausdorff measure. For every $E\subseteq[0,1)^{n}$ , define the $s$ -dimensional Hausdorff content at precision $r$ by

$h^{s}_{r}(E)=\inf\left\{\sum_{i}d(Q_{i})^{s}\,|\,\bigcup_{i}Q_{i}\text{ covers }E\text{ and }d(Q_{i})\leq 2^{-r}\right\}$ ,

where $d(Q)$ is the diameter of ball $Q$ . We define the $s$ -dimensional Hausdorff measure of $E$ by

$\mathcal{H}^{s}(E)=\lim\limits_{r\to\infty}h^{s}_{r}(E)$ .

Remark.

It is well-known that $\mathcal{H}^{s}$ is a metric outer measure for every $s$ .

The Hausdorff dimension of a set $E$ is then defined by

$\dim_{H}(E)=\inf\limits_{s}\{\mathcal{H}^{s}(E)=\infty\}=\sup\limits_{s}\{\mathcal{H}^{s}(E)=0\}$ .

Another important metric outer measure, which gives rise to the packing dimension of a set, is the $s$ -dimensional packing measure. For every $E\subseteq[0,1)^{n}$ , define the $s$ -dimensional packing pre-measure by

$p^{s}(E)=\limsup\limits_{\delta\to 0}\left\{\sum\limits_{i\in\mathbb{N}}d(B_{i})^{s}\,|\,\{B_{i}\}\text{ is a set of disjoint balls and }B_{i}\in C(E,\delta)\right\}$ ,

where $C(E,\delta)$ is the set of all closed balls with diameter at most $\delta$ with centers in $E$ . We define the $s$ -dimensional packing measure of $E$ by

$\mathcal{P}^{s}(E)=inf\left\{\sum\limits_{j}p^{s}(E_{j})\,|\,E\subseteq\bigcup E_{j}\right\}$ ,

where the infimum is taken over all countable covers of $E$ . For every $s$ , the $s$ -dimensional packing measure is a metric outer measure.

The packing dimension of a set $E$ is then defined by

$\dim_{P}(E)=\inf\limits_{s}\{\mathcal{P}^{s}(E)=0\}=\sup\limits_{s}\{\mathcal{P}^{s}(E)=\infty\}$ .

In order to prove that every analytic set has optimal oracles, we will make use of the following facts of geometric measure theory (see, e.g., [7], [2]).

Theorem 1.

The following are true.

1.

Suppose $E\subseteq\mathbb{R}^{n}$ is compact and satisfies $\mathcal{H}^{s}(E)>0$ . Then there is a compact subset $F\subseteq E$ such that $0<\mathcal{H}^{s}(F)<\infty$ .
2.

Every analytic set $E\subseteq\mathbb{R}^{n}$ has a $\Sigma^{0}_{2}$ subset $F\subseteq E$ such that $\dim_{H}(F)=\dim_{H}(E)$ .
3.

Suppose $E\subseteq\mathbb{R}^{n}$ is compact and satisfies $\mathcal{P}^{s}(E)>0$ . Then there is a compact subset $F\subseteq E$ such that $0<\mathcal{P}^{s}(F)<\infty$ .
4.

Every analytic set $E\subseteq\mathbb{R}^{n}$ has a $\Sigma^{0}_{2}$ subset $F\subseteq E$ such that $\dim_{P}(F)=\dim_{P}(E)$ .

It is possible to generalize the definition of Hausdorff measure using gauge functions. A function $\phi:[0,\infty)\to[0,\infty)$ is a gauge function if $\phi$ is monotonically increasing, strictly increasing for $t>0$ and continuous. If $\phi$ is a gauge, define the $phi$ -Hausdorff content at precision $r$ by

$h^{\phi}_{r}(E)=\inf\left\{\sum_{i}\phi(d(Q_{i}))\,|\,\bigcup_{i}Q_{i}\text{ covers }E\text{ and }d(Q_{i})\leq 2^{-r}\right\}$ ,

where $d(Q)$ is the diameter of ball $Q$ . We define the $phi$ -Hausdorff measure of $E$ by

$\mathcal{H}^{\phi}(E)=\lim\limits_{r\to\infty}h^{\phi}_{r}(E)$ .

Thus we recover the $s$ -dimensional Hausdorff measure when $\phi(t)=t^{s}$ .

Gauged Hausdorff measures give fine-grained information about the size of a set. There are sets $E$ which Hausdorff dimension $s$ , but $\mathcal{H}^{s}(E)=0$ or $\mathcal{H}^{s}(E)=\infty$ . However, it is sometimes possible to find an appropriate gauge so that $0<\mathcal{H}^{\phi}(E)<\infty$ . When $0<\mathcal{H}^{\phi}(E)<\infty$ , we say that $\phi$ is an exact gauge for $E$ .

Example.

For almost every Brownian path $X$ in $\mathbb{R}^{2}$ , $\mathcal{H}^{2}(X)=0$ , but $0<\mathcal{H}^{\phi}(X)<\infty$ , where $\phi(t)=t^{2}\log\frac{1}{t}\log\log\frac{1}{t}$ .

For two outer measures $\mu$ and $\nu$ , $\mu$ is said to be absolutely continuous with respect to $\nu$ , denoted $\mu\ll\nu$ , if $\mu(A)=0$ for every set $A$ for which $\nu(A)=0$ .

Example.

For every $s$ , let $\phi_{s}(t)=t^{s}\log\frac{1}{t}$ . Then $\mathcal{H}^{s}\ll\mathcal{H}^{\phi_{s}}$ .

Example.

For every $s$ , let $\phi_{s}(t)=\frac{t^{s}}{\log\frac{1}{t}}$ . Then $\mathcal{H}^{\phi_{s}}\ll\mathcal{H}^{s}$ .

2.2 Algorithmic Information Theory

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. An important fact is that the choice of universal machine affects the Kolmogorov complexity by at most an additive constant (which, especially for our purposes, can be safely ignored). See [11, 27, 6] for a more comprehensive overview of Kolmogorov complexity.

We can naturally extend these definitions to Euclidean spaces by introducing “precision” parameters [16, 14]. 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\,|\,q)\,:\,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^{-s}}(y)\cap\mathbb{Q}^{n}\big{\}}\,.

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

The effective Hausdorff dimension and effective packing dimension⁴⁴4Although effective Hausdorff was originally defined by J. Lutz [13] using martingales, it was later shown by Mayordomo [25] that the definition used here is equivalent. For more details on the history of connections between Hausdorff dimension and Kolmogorov complexity, see [6, 26]. 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}\,.

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)$ . We can also join two oracles $A,B\subseteq\mathbb{N}$ using any computable bijection $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ . We denote the join of $A$ and $B$ by $(A,B)$ . We can generalize this procedure to join any countable sequence of oracles.

As mentioned in the introduction, the connection between effective dimensions and the classical Hausdorff and packing dimensions is given by the point-to-set principle introduced by J. Lutz and N. Lutz [14].

Theorem 2 (Point-to-set principle).

Let $n\in\mathbb{N}$ and $E\subseteq\mathbb{R}^{n}$ . Then

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\min\limits_{A\subseteq\mathbb{N}}\sup_{x\in E}\dim^{A}(x),\text{ and}$
	$\displaystyle\dim_{P}(E)$	$\displaystyle=\min\limits_{A\subseteq\mathbb{N}}\sup_{x\in E}\operatorname{Dim}^{A}(x)\,.$

An oracle testifying to the the first equality is called a Hausdorff oracle for E. Similarly, an oracle testifying to the the second equality is called a packing oracle for E.

3 Optimal Hausdorff Oracles

For any set $E$ , there are infinitely many Hausdorff oracles for $E$ . A natural question is whether there is a Hausdorff oracle which minimizes the complexity of every point in $E$ . Unfortunately, it is, in general, not possible for a single oracle to maximally reduce every point. We introduce the notion of optimal Hausdorff oracles by weakening the condition to a single point.

Definition 3.

Let $E\subseteq\mathbb{R}^{n}$ and $A\subseteq\mathbb{N}$ . We say that $A$ is Hausdorff optimal for $E$ if the following conditions are satisfied.

1.

$A$ is a Hausdorff oracle for $E$ .
2.

For every $B\subseteq\mathbb{N}$ and every $\epsilon>0$ there is a point $x\in E$ such that $\dim^{A,B}(x)\geq\dim_{H}(E)-\epsilon$ and for almost every $r\in\mathbb{N}$

$K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r$ .

Note that the second condition only guarantees the existence of one point whose complexity is unaffected by the addtional information in $B$ . However, we can show that this implies the seemingly stronger condition that “most” points are unaffected. For $B\subseteq\mathbb{N}$ , $\epsilon>0$ define the set

$N(A,B,\epsilon)=\{x\in E\,|\,(\forall^{\infty}r)\,K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r\}$

Proposition 4.

Let $E\subseteq\mathbb{R}^{n}$ be a set such that $\dim_{H}(E)>0$ and let $A$ be an oracle. Then $A$ is a Hausdorff optimal oracle for $E$ if and only if $A$ is a Hausdorff oracle and $\dim_{H}(N(A,B,\epsilon))=\dim_{H}(E)$ for every $B\subseteq\mathbb{N}$ and $\epsilon>0$ .

Proof.

For the forward direction, let $A$ be a optimal Hausdorff oracle for $E$ . Then by the first condition of the definition, $A$ is a Hausdorff oracle. Let $B\subseteq\mathbb{N}$ and $\epsilon>0$ . Let $C$ be a Hausdorff oracle for $N(A,B,\epsilon)$ . For the sake of contradiction, suppose that

$\dim_{H}(N(A,B,\epsilon))<\dim_{H}(E)-\gamma$ ,

for some $\gamma>0$ . We will, without loss of generality, assume that $\gamma<\epsilon$ . Then, by the point to set principle, for every $x\in N(A,B,\epsilon)$ ,

	$\displaystyle\dim^{A,(B,C)}(x)$	$\displaystyle\leq\dim^{C}(x)$
		$\displaystyle\leq\dim_{H}(N(A,B,\epsilon))$
		$\displaystyle<\dim_{H}(E)-\gamma.$

Since, $A$ is an optimal Hausdorff oracle for $E$ , there is a point $x\in E$ such that $\dim^{A,(B,C)}(x)\geq\dim_{H}(E)-\gamma$ and for almost every $r\in\mathbb{N}$

$K^{A,(B,C)}_{r}(x)\geq K^{A}_{r}(x)-\gamma r$ .

By our previous discussion, any such point $x$ cannot be in $N(A,B,\epsilon)$ . However, if $x\notin N(A,B,\epsilon)$ , then for infinitely many $r$ ,

$K^{A,(B,C)}_{r}(x)<K^{A}_{r}(x)-\epsilon r$ .

Thus, no such $x$ exists, contradicting the fact that $A$ is Hausdorff optimal.

For the backward direction, let $A$ be an oracle satisfying the hypothesis. Then $A$ is a Hausdorff oracle for $E$ and the first condition of optimal Hausdorff oracles is satisfied. Let $B\subseteq\mathbb{N}$ and $\epsilon>0$ . By our hypothesis and the point-to-set principle,

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\dim_{H}(N(A,B,\epsilon))$
		$\displaystyle\leq\sup\limits_{x\in N(A,B,\epsilon)}\dim^{A,B}(x).$

Therefore, there is certainly a point $x\in E$ such that $\dim^{A,B}(x)\geq\dim_{H}(E)-\epsilon$ and

$K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r$ ,

for almost every $r\in\mathbb{N}$ . ∎

A simple, but useful, result is if $B$ is an oracle obtained by adding additional information to an optimal Hausdorff oracle, then $B$ is also optimal.

Lemma 5.

Let $E\subseteq\mathbb{R}^{n}$ . If $A$ is an optimal Hausdorff oracle for $E$ , then the join $C=(A,B)$ is Hausdorff optimal for $E$ for every oracle $B$ .

Proof.

Let $A$ be an optimal Hausdorff oracle for $E$ . By the point-to-set principle (Theorem 2),

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\sup\limits_{x\in E}\dim^{A}(x)$
		$\displaystyle\geq\sup\limits_{x\in E}\dim^{C}(x)$
		$\displaystyle\geq\dim_{H}(E).$

Hence, the oracle $C=(A,B)$ is a Hausdorff oracle for $E$ .

Let $B^{\prime}\subseteq\mathbb{N}$ be an oracle, and let $\epsilon>0$ . Let $x\in E$ be a point such that

\dim^{A,(B,B^{\prime})}(x)\geq\dim_{H}(E)-\epsilon/2,

(4)

and

K_{r}^{A,(B,B^{\prime})}(x)\geq K^{A}_{r}(x)-\epsilon r/2,

(5)

for almost every precision $r$ . Note that such a point exists since $A$ is optimal for $E$ .

For all sufficiently large $r$ ,

	$\displaystyle K^{(A,B),B^{\prime}}_{r}(x)$	$\displaystyle=K^{A,(B,B^{\prime})}_{r}(x)$
		$\displaystyle\geq K^{A}_{r}(x)-\epsilon r/2$
		$\displaystyle\geq K^{A,B}_{r}(x)-\epsilon r/2$
		$\displaystyle=K^{C}_{r}(x)-\epsilon r/2.$

Therefore, $C=(A,B)$ is optimal for $E$ .

∎

We now give some basic closure properties of the class of sets with optimal Hausdorff oracles.

Observation 6.

Let $F\subseteq E$ . If $\dim_{H}(F)=\dim_{H}(E)$ and $F$ has an optimal Hausdorff oracle, then $E$ has an optimal Hausdorff oracle.

We can also show that having optimal Hausdorff oracles is closed under countable unions.

Proposition 7.

Let $E_{1},E_{2},\ldots$ be a countable sequence of sets and let $E=\cup_{n}E_{n}$ . If every set $E_{n}$ has an optimal Hausdorff oracle, then $E$ has an optimal Hausdorff oracle.

Proof.

We first note that

$\dim_{H}(E)=\sup_{n}\dim_{H}(E_{n})$ .

For each $n$ , let $A_{n}$ be an optimal Hausdorff oracle for $E_{n}$ . Let $A$ be the join of $A_{1},A_{2},\ldots$ . Let $B$ be a Hausdorff oracle for $E$ . Note that, by Lemma 5, for every $n$ , since $A_{n}$ is an optimal Hausdorff oracle for $E_{n}$ , $(A,B)$ is optimal for $E_{n}$ .

We now claim that $(A,B)$ is an optimal Hausdorff oracle for $E$ . Theorem 2 shows that item (1) of the definition of optimal Hausdorff oracles is satisfied. For item (2), let $C\subseteq\mathbb{N}$ be an oracle, and let $\epsilon>0$ . Let $n$ be a number such that $\dim_{H}(E_{n})>\dim_{H}(E)-\epsilon$ . Since $(A,B)$ is Hausdorff optimal for $E_{N}$ , there is a point $x\in E_{n}$ such that

(i)

$\dim^{(A,B),C}(x)\geq\dim_{H}(E_{n})-\epsilon\geq\dim_{H}(E)-\epsilon$ , and
(ii)

for almost every $r$ ,

$K^{(A,B),C}_{r}(x)\geq K^{(A,B)}_{r}(x)-\epsilon r$ .

Therefore, item (2) of the definition of optimal Hausdorff oracles is satisfied, and so $(A,B)$ is Hausdorff optimal for $E$ .

∎

3.1 Outer Measures and Optimal Oracles

In this section we give a sufficient condition for a set to have optimal Hausdorff oracles. Specifically, we prove that if $\dim_{H}(E)=s$ , and there is a metric outer measure, absolutely continuous with respect to $\mathcal{H}^{s}$ , such that $0<\mu(E)<\infty$ , then $E$ has optimal Hausdorff oracles. Although stated in this general form, the main application of this result (in Section 3.2) is for the case $\mu=\mathcal{H}^{s}$ .

For every $r\in\mathbb{N}$ , let $\mathcal{Q}^{n}_{r}$ be the set of all dyadic cubes at precision $r$ , i.e., cubes of the form

$Q=[m_{1}2^{-r},(m_{1}+1)2^{-r})\times\ldots\times[m_{n}2^{-r},(m_{n}+1)2^{-r})$ ,

where $0\leq m_{1},\ldots,m_{n}\leq 2^{r}$ . For each $r$ , we refer to the $2^{nr}$ cubes in $\mathcal{Q}_{r}$ as $Q_{r,1},\ldots,Q_{r,2^{nr}}$ . We can identify each dyadic cube $Q_{r,i}$ with the unique dyadic rational $d_{r,i}$ at the center of $Q_{r,i}$ .

We now associate, to each metric outer measure, a discrete semimeasure on the dyadic rationals $\mathbb{D}$ . Recall that discrete semimeasure on $\mathbb{D}^{n}$ is a function $p:\mathbb{D}^{n}\to[0,1]$ which satisfies $\Sigma_{r,i}p(d_{r,i})<\infty$ .

Let $E\subseteq\mathbb{R}^{n}$ and $\mu$ be a metric outer measure such that $0<\mu(E)<\infty$ . Define the function $p_{\mu}:\mathbb{D}^{n}\rightarrow[0,1]$ by

$p_{\mu,E}(d_{r,i})=\frac{\mu(E\cap Q_{r,i})}{r^{2}\mu(E)}$ .

Observation 8.

Let $\mu$ be a metric outer measure and $E\subseteq\mathbb{R}^{n}$ such that $0<\mu(E)<\infty$ . Then for every $r$ , every dyadic cube $Q\in\mathcal{Q}_{r}$ , and all $r^{\prime}>r$ ,

$\mu(E\cap Q)=\sum\limits_{\begin{subarray}{c}Q^{\prime}\subset Q\\ Q^{\prime}\in\mathcal{Q}_{r^{\prime}}\end{subarray}}\mu(E\cap Q^{\prime})$ .

Proposition 9.

Let $E\subseteq\mathbb{R}^{n}$ and $\mu$ be a metric outer measure such that $0<\mu(E)<\infty$ . Relative to some oracle $A$ , the function $p_{\mu,E}$ is a lower semi-computable discrete semimeasure.

Proof.

We can encode the real numbers $p_{\mu,E}(d)$ into an oracle $A$ , relative to which $p_{\mu,E}$ is clearly computable.

To see that $p_{\mu,E}$ is indeed a discrete semimeasure, by Observation 8,

	$\displaystyle\sum\limits_{r,i}p_{\mu,E}(d_{r,i})$	$\displaystyle=\sum\limits_{r}\sum\limits_{i=1}^{2^{2r}}\frac{\mu(E\cap Q_{r,i})}{r^{2}\mu(E)}$
		$\displaystyle=\sum\limits_{r}\frac{1}{r^{2}\mu(E)}\sum\limits_{i=1}^{2^{2r}}\mu(E\cap Q_{r,i})$
		$\displaystyle=\sum\limits_{r}\frac{\mu(E)}{r^{2}\mu(E)}$
		$\displaystyle<\infty.$

∎

In order to connect the existence of such an outer measure $\mu$ to the existence of optimal oracles, we need to relate the semimeasure $p_{\mu}$ and Kolmogorov complexity. We achieve this using a fundamental result in algorithmic information theory.

Levin’s optimal lower semicomputable subprobability measure, relative to an oracle $A$ , on the dyadic rationals $\mathbb{D}$ is defined by

$\mathbf{m}^{A}(d)=\sum\limits_{\pi\,:\,U^{A}(\pi)=d}2^{-|\pi|}$ .

Lemma 10.

Let $E\subseteq\mathbb{R}^{n}$ and $\mu$ be a metric outer measure such that $0<\mu(E)<\infty$ . Let $A$ be an oracle relative to which $p_{\mu,E}$ is lower semi-computable. Then is a constant $\alpha>0$ such that $\mathbf{m}^{A}(d)\geq\alpha p_{\mu,E}(d)$ , for every $d\in\mathbb{D}^{n}$ .

Proof.

Case and Lutz [3], generalizing Levin’s coding theorem [9, 10], showed that there is a constant $c$ such that

$\mathbf{m}^{A}(d_{r,i})\leq 2^{-K^{A}(d_{r,i})+K^{A}(r)+c}$ ,

for every $r\in\mathbb{N}$ and $d_{r,i}\in\mathbb{D}^{n}$ . The optimality of $\mathbf{m}^{A}$ ensures that, for every lower semicomputable (relative to $A$ ) discrete semimeasure $\nu$ on $\mathbb{D}^{n}$ ,

$\mathbf{m}^{A}(d_{r,i})\geq\alpha\nu(d_{r,i})$ .

∎

The results of this section have dealt with the dyadic rationals. However, we ultimately deal with the Kolmogorov complexity of Euclidean points. A result of Case and Lutz [3] relates the Kolmogorov complexity of Euclidean points with the complexity of dyadic rationals.

Lemma 11 ([3]).

Let $x\in[0,1)^{n}$ , $A\subseteq\mathbb{N}$ , and $r\in\mathbb{N}$ . Let $Q_{r,i}$ be the (unique) dyadic cube at precision $r$ containing $x$ . Then

$K^{A}_{r}(x)=K^{A}(d_{r,i})-O(\log r)$ .

Lemma 12.

Let $E\subseteq\mathbb{R}^{n}$ and $\mu$ be a metric outer measure such that $0<\mu(E)<\infty$ . Let $A$ be an oracle relative to which $p_{\mu,E}$ is lower semi-computable. Then, for every oracle $B\subseteq\mathbb{N}$ and every $\epsilon>0$ , the set

$N=\{x\in E\,|\,(\exists^{\infty})\;K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r\}$

has $\mu$ -measure zero.

Proof.

Let $B\subseteq\mathbb{N}$ and $\epsilon>0$ . For every $R\in\mathbb{N}$ , there is a set $\mathcal{C}_{R}$ of dyadic cubes satisfying the following.

•

The cubes in $\mathcal{C}_{R}$ cover $N$ .
•

Every $Q_{r,i}$ in $\mathcal{C}_{R}$ satisfies $r\geq R$ .
•

For every $Q_{r,i}\in\mathcal{C}_{R}$ ,

$K^{A,B}(d_{r,i})<K^{A}(d_{r,i})-\epsilon r+O(\log r)$ .

Note that the last item follows from our definition of $N$ by Lemma 11.

Since the family of cubes in $\mathcal{C}_{R}$ covers $N$ , by the subadditive property of $\mu$ ,

$\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}\mu(E\cap Q_{r,i})\geq\mu(N)$ .

Thus, for every $R$ , by Lemma 10 and Kraft’s inequality,

	$\displaystyle 1$	$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{-K^{A,B}(d_{r,i})}$
		$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{\epsilon r-K^{A}(d_{r,i})}$
		$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{\epsilon r}\mathbf{m}^{A}(d_{r,i})$
		$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{\epsilon r-K^{A}(r)+c}\alpha p_{\mu,E}(d_{r,i})$
		$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{\epsilon r/2}p_{\mu,E}(d_{r,i})$
		$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{\epsilon r/2}\frac{\mu(E\cap Q_{r,i})}{r^{2}\mu(E)}$
		$\displaystyle\geq\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}2^{\epsilon r/4}\frac{\mu(E\cap Q_{r,i})}{r^{2}\mu(E)}$
		$\displaystyle\geq 2^{\epsilon R/4}\sum\limits_{Q_{r,i}\in\mathcal{C}_{R}}\frac{\mu(E\cap Q_{r,i})}{\mu(E)}$
		$\displaystyle\geq 2^{\epsilon R/4}\frac{\mu(N)}{\mu(E)}.$

Since $R$ can be arbitrarily large, and $0<\mu(E)<\infty$ , the conclusion follows. ∎

We now have the machinery in place to prove the main theorem of this section.

Theorem 13.

Let $E\subseteq\mathbb{R}^{n}$ with $\dim_{H}(E)=s$ . Suppose there is a metric outer measure $\mu$ such that

$0<\mu(E)<\infty$ ,

and either

1.

$\mu\ll\mathcal{H}^{s-\delta}$ , for every $\delta>0$ , or
2.

$\mathcal{H}^{s}\ll\mu$ and $\mathcal{H}^{s}(E)>0$ .

Then $E$ has an optimal Hausdorff oracle $A$ .

Proof.

Let $A\subseteq\mathbb{N}$ be a Hausdorff oracle for $E$ such that $p_{\mu,E}$ is computable relative to $A$ . Note that such an oracle exists by the point-to-set principle and routine encoding. We will show that $A$ is optimal for $E$ .

For the sake of contradiction, suppose that there is an oracle $B$ and $\epsilon>0$ such that, for every $x\in E$ either

1.

$\dim^{A,B}(x)<s-\epsilon$ , or
2.

there are infinitely many $r$ such that $K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r$ .

Let $N$ be the set of all $x$ for which the second item holds. By Lemma 12, $\mu(N)=0$ . We also note that, by the point-to-set principle,

$\dim_{H}(E-N)\leq s-\epsilon$ ,

and so $\mathcal{H}^{s}(E-N)=0$ .

To achieve the desired contradiction, we first assume that $\mu\ll\mathcal{H}^{s-\delta}$ , for every $\delta>0$ . Since $\mu\ll\mathcal{H}^{s-\delta}$ , and $\dim_{H}(E-N)<s-\epsilon$ ,

$\mu(E-N)=0$ .

Since $\mu$ is a metric outer measure,

	$\displaystyle 0$	$\displaystyle<\mu(E)$
		$\displaystyle\leq\mu(N)+\mu(E-N)$
		$\displaystyle=0,$

a contradiction.

Now suppose that $\mathcal{H}^{s}\ll\mu$ and $\mathcal{H}^{s}(E)>0$ . Then, since $\mathcal{H}^{s}$ is an outer measure, $\mathcal{H}^{s}(E)>0$ and $\mathcal{H}^{s}(E-N)=0$ we must have $\mathcal{H}^{s}(N)>0$ . However this implies that $\mu(N)>0$ , and we again have the desired contradiction. Thus $A$ is an optimal Hausdorff oracle for $E$ and the proof is complete. ∎

Recall that $E\subseteq[0,1)^{n}$ is called an $s$ -set if

$0<\mathcal{H}^{s}(E)<\infty$ .

Since $\mathcal{H}^{s}$ is a metric outer measure, and trivially absolutely continuous with respect to itself, we have the following corollary.

Corollary 14.

Let $E\subseteq[0,1)^{n}$ be an $s$ -set. Then there is an optimal Hausdorff oracle for $E$ .

3.2 Sets with optimal Hausdorff oracles

We now show that every analytic set has optimal Hausdorff oracles.

Lemma 15.

Every analytic set $E$ has optimal Hausdorff oracles.

Proof.

We begin by assuming that $E$ is compact, and let $s=\dim_{H}(E)$ . Then for every $t<s$ , $\mathcal{H}^{t}(E)>0$ . Thus, by Theorem 1(1), there is a sequence of compact subsets $F_{1},F_{2},\ldots$ of $E$ such that

$\dim_{H}(\bigcup_{n}F_{n})=\dim_{H}(E)$ ,

and, for each $n$ ,

$0<\mathcal{H}^{s_{n}}(F_{n})<\infty$ ,

where $s_{n}=s-1/n$ . Therefore, by Theorem 13, each set $F_{n}$ has optimal Hausdorff oracles. Hence, by Proposition 7, $E$ has optimal Hausdorff oracles and the conclusion follows.

We now show that every $\Sigma^{0}_{2}$ set has optimal Hausdorff oracles. Suppose $E=\cup_{n}F_{n}$ is $\Sigma^{0}_{1}$ , where each $F_{n}$ is compact. As we have just seen, each $F_{n}$ has optimal Hausdorff oracles. Therefore, by Proposition 7, $E$ has optimal Hausdorff oracles and the conclusion follows.

Finally, let $E$ be analytic. By Theorem 1(2), there is a $\Sigma^{0}_{2}$ subset $F$ of the same Hausdorff dimension as $E$ . We have just seen that $F$ must have an optimal Hausdorff oracle. Since $\dim_{H}(F)=\dim_{H}(E)$ , by Observation 6 $E$ has optimal Hausdorff oracles, and the proof is complete ∎

Crone, Fishman and Jackson [4] have recently shown that, assuming the Axiom of Determinacy (AD)⁵⁵5Note that AD is inconsistent with the axiom of choice., every subset $E$ has a Borel subset $F$ such that $\dim_{H}(F)=\dim_{H}(E)$ . This, combined with Lemma 15, yields the following corollary.

Corollary 16.

Assuming AD, every set $E\subseteq\mathbb{R}^{n}$ has optimal Hausdorff oracles.

Lemma 17.

Suppose that $E\subseteq\mathbb{R}^{n}$ satisfies $\dim_{H}(E)=\dim_{P}(E)$ . Then $E$ has an optimal Hausdorff oracle. Moreover, the join $(A,B)$ is an optimal Hausdorff oracle, where $A$ and $B$ are the Hausdorff and packing oracles, respectively, of $E$ .

Proof.

Let $A$ be a Hausdorff oracle for $E$ and let $B$ be a packing oracle for $E$ . We claim that that the join $(A,B)$ is an optimal Hausdorff oracle for $E$ . By the point-to-set principle, and the fact that extra information cannot increase effective dimension,

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\sup\limits_{x\in E}\dim^{A}(x)$
		$\displaystyle\geq\sup\limits_{x\in E}\dim^{A,B}(x)$
		$\displaystyle\geq\dim_{H}(E).$

Therefore

$\dim_{H}(E)=\sup\limits_{x\in E}\dim^{A,B}(x)$ ,

and the first condition of optimal Hausdorff oracles is satisfied.

Let $C\subseteq\mathbb{N}$ be an oracle and $\epsilon>0$ . By the point-to-set principle,

$\dim_{H}(E)\leq\sup\limits_{x\in E}\dim^{A,B,C}(x)$ ,

so there is an $x\in E$ such that

$\dim_{H}(E)-\epsilon/4<\dim^{A,B,C}(x)$ .

Let $r$ be sufficiently large. Then, by our choice of $B$ and the fact that additional information cannot increase the complexity of a point,

	$\displaystyle K^{A,B}_{r}(x)$	$\displaystyle\leq K^{B}_{r}(x)$
		$\displaystyle\leq\dim_{P}(E)r+\epsilon r/4$
		$\displaystyle=\dim_{H}(E)r+\epsilon r/4$
		$\displaystyle<\dim^{A,B,C}(x)r+\epsilon r/2$
		$\displaystyle\leq K_{r}^{A,B,C}(x)+\epsilon r.$

Since the oracle $C$ and $\epsilon$ were arbitrarily, the proof is complete. ∎

3.3 Sets without optimal Hausdorff oracles

In the previous section, we gave general conditions for a set $E$ to have optimal Hausdorff oracles. Indeed, we saw that under the axiom of determinacy, every set has optimal Hausdorff oracles.

However, assuming the axiom of choice (AC) and the continuum hypothesis (CH), we are able to construct sets without optimal Hausdorff oracles.

Lemma 18.

Assume AC and CH. Then, for every $s\in(0,1)$ , there is a subset $E\subseteq\mathbb{R}$ with $\dim_{H}(E)=s$ such that $E$ does not have optimal Hausdorff oracles.

$\lim_{n}a_{n}/b_{n}=s$ .

Using AC and CH, we order the subsets of the natural numbers such that every subset has countably many predecessors. For every countable ordinal $\alpha$ , let $f_{\alpha}:\mathbb{N}\to\{\beta\,|\,\beta<\alpha\}$ be a function such that each ordinal $\beta$ strictly less than $\alpha$ is mapped to by infinitely many $n$ . Note that such a function exists, since the range is countable assuming CH.

We will define real numbers $x_{\alpha}$ , $y_{\alpha}$ via transfinite induction. Let $x_{1}$ be a real which is random relative to $A_{1}$ . Let $y_{1}$ be the real whose binary expansion is given by

\displaystyle y_{1}[r]=\begin{cases}0&\text{ if }a_{n}<r\leq b_{n}\text{ for some }n\in\mathbb{N}\\ x_{1}[r]&\text{ otherwise}\end{cases}

For the induction step, suppose we have defined our points up to $\alpha$ . Let $x_{\alpha}$ be a real number which is random relative to the join of $\bigcup_{\beta<\alpha}(A_{\beta},x_{\beta})$ and $A_{\alpha}$ . This is possible, as we are assuming that this union is countable. Let $y_{\alpha}$ be the point whose binary expansion is given by

\displaystyle y_{\alpha}[r]=\begin{cases}x_{\beta}[r]&\text{ if }a_{n}<r\leq b_{n},\text{ where }f_{\alpha}(n)=\beta\\ x_{\alpha}[r]&\text{ otherwise}\end{cases}

Finally, we define our set $E=\{y_{\alpha}\}$ . We now claim that $\dim_{H}(E)=s$ , and that $E$ does not have an optimal Hausdorff oracle.

Lemma 19.

The Hausdorff dimension of $E$ is $s$ .

Proof.

We first upper bound the dimension. Let $A$ be an oracle encoding $x_{1}$ . From our construction, for every element $y\in E$ , there are infinitely many intervals $[a_{n},b_{n}]$ such that $y[a_{n},b_{n}]=x_{1}[a_{n},b_{n}]$ . Hence, for every $y\in E$ , there are infinitely many $n$ such that

	$\displaystyle K^{A}_{b_{n}}(y)$	$\displaystyle=K^{A}_{a_{n}}(y)+K^{A}_{b_{n},a_{n}}(y)+o(b_{n})$
		$\displaystyle\leq K^{A}_{a_{n}}(y)+o(b_{n})$
		$\displaystyle\leq a_{n}+o(b_{n}).$

Therefore, by the point to set principle,

	$\displaystyle\dim_{H}(E)$	$\displaystyle\leq\sup_{y}\dim^{A}(y)$
		$\displaystyle=\sup_{y}\liminf_{r}\frac{K^{A}_{r}(y)}{r}$
		$\displaystyle\leq\sup_{y}\liminf_{n}\frac{K^{A}_{b_{n}}(y)}{b_{n}}$
		$\displaystyle\leq\sup_{y}\liminf_{n}\frac{a_{n}+o(b_{n})}{b_{n}}$
		$\displaystyle\leq\sup_{y}\liminf_{n}s$
		$\displaystyle=s,$

and the proof that $\dim_{H}(E)\leq s$ is complete.

For the lower bound, let $A$ be a Hausdorff oracle for $E$ , and let $\alpha$ be the ordinal corresponding to $A$ . By our construction of $y_{\alpha}$ , for every $n$ ,

	$\displaystyle K^{A_{\alpha}}_{a_{n}}(y_{\alpha})$	$\displaystyle\geq K^{A_{\alpha}}_{a_{n}}(x_{\alpha})-b_{n-1}$
		$\displaystyle\geq a_{n}-b_{n-1}-o(a_{n})$
		$\displaystyle\geq a_{n}-a_{n}^{\frac{1}{2}}-o(a_{n}).$

Hence, for every $n$ , and every $a_{n}<r\leq b_{n}$ ,

	$\displaystyle K^{A_{\alpha}}_{r}(y_{\alpha})$	$\displaystyle\geq K^{A_{\alpha}}_{a_{n}}(y_{\alpha})$
		$\displaystyle\geq a_{n}-a_{n}^{\frac{1}{2}}-o(a_{n}).$

This implies that

$\frac{K^{A_{\alpha}}_{r}(y_{\alpha})}{r}\geq s-o(1)$ ,

for every $n$ , and every $a_{n}<r\leq b_{n}$ .

We can also conclude that, for every $n$ and every $b_{n}<r\leq a_{n+1}$ ,

	$\displaystyle K^{A_{\alpha}}_{r}(y_{\alpha})$	$\displaystyle=K^{A_{\alpha}}_{b_{n}}(y_{\alpha})+K^{A_{\alpha}}_{r,b_{n}}(y_{\alpha})-o(r)$
		$\displaystyle\geq a_{n}-a_{n}^{\frac{1}{2}}+r-b_{n}-o(r).$

This implies that

	$\displaystyle\frac{K^{A_{\alpha}}_{r}(y_{\alpha})}{r}$	$\displaystyle=1+\frac{a_{n}}{r}-\frac{b_{n}}{r}-o(1)$
		$\displaystyle=1-\frac{a_{n}(1/s-1)}{r}-o(1)$
		$\displaystyle\geq 1-s(1/s-1)-o(1)$
		$\displaystyle=s-o(1).$

for every $n$ , and every $a_{n}<r\leq b_{n}$ .

Together, these inequalities and the point-to-set principle show that

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\sup_{x}\dim^{A}(x)$
		$\displaystyle\geq\dim^{A}(y_{\alpha})$
		$\displaystyle=\liminf_{r}\frac{K^{A}(y_{\alpha})}{r}$
		$\displaystyle\geq\liminf_{r}s-o(1)$
		$\displaystyle=s,$

and the proof is complete. ∎

Lemma 20.

$E$ does not have optimal Hausdorff oracles.

Proof.

Let $A_{\alpha}\subseteq\mathbb{N}$ be an oracle. It suffices to show that $A_{\alpha}$ is not optimal. With this goal in mind, let $B$ be an oracle encoding $x_{\alpha}$ and the set $\{y_{\beta}\,|\,\beta<\alpha\}$ . Note that we can encode this information since this set is countable.

Let $y_{\beta}\in E$ . First, suppose that $\beta\leq\alpha$ . Then by our choice of $B$ , $\dim^{A_{\alpha},B}(y_{\beta})=0$ . So then suppose that $\beta>\alpha$ . We first note that, since $x_{\beta}$ is random relative to $A_{\alpha}$

	$\displaystyle K^{A_{\alpha}}_{a_{n}}(y_{\beta})$	$\displaystyle\geq K^{A_{\alpha}}(y_{\beta}[b_{n-1}\ldots a_{n}])-O(\log a_{n})$
		$\displaystyle=K^{A_{\alpha}}(x_{\beta}[b_{n-1}\ldots a_{n}])-O(\log a_{n})$
		$\displaystyle\geq a_{n}-b_{n-1}-O(\log a_{n})$
		$\displaystyle\geq a_{n}-o(a_{n}),$

for every $n\in\mathbb{N}$ .

By our construction, there are infinitely many $n$ such that

y_{\beta}[a_{n}\ldots b_{n}]=x_{\alpha}[a_{n}\ldots b_{n}]

(6)

Since $x_{\alpha}$ is random relative to $A_{\alpha}$ , for any $n$ such that (6) holds,

	$\displaystyle K^{A_{\alpha}}_{b_{n}}(y_{\beta})$	$\displaystyle=K^{A_{\alpha}}_{a_{n}}(y_{\beta})+K^{A_{\alpha}}_{b_{n},a_{n}}(y_{\beta})$
		$\displaystyle\geq a_{n}-o(a_{n})+K^{A_{\alpha}}(y_{\beta}[a_{n}\ldots b_{n}])-O(\log b_{n})$
		$\displaystyle=a_{n}-o(a_{n})+K^{A_{\alpha}}(x_{\alpha}[a_{n}\ldots b_{n}])$
		$\displaystyle\geq a_{n}-o(a_{n})+b_{n}-a_{n}-o(b_{n})$
		$\displaystyle=b_{n}-o(b_{n}).$

However, since we can compute $x_{\alpha}$ given $B$ ,

	$\displaystyle K^{A_{\alpha},B}_{b_{n}}(y_{\beta})$	$\displaystyle=K^{A_{\alpha},B}_{a_{n}}(y_{\beta})+K^{A_{\alpha},B}_{b_{n},a_{n}}(y_{\beta})$
		$\displaystyle=K^{A_{\alpha},B}_{a_{n}}(y_{\beta})$
		$\displaystyle\leq a_{n}-o(a_{n})$
		$\displaystyle=sb_{n}-o(a_{n})$
		$\displaystyle=sK^{A_{\alpha}}_{b_{n}}(y_{\beta})-o(a_{n}).$

Therefore $A_{\alpha}$ is not optimal, and the claim follows. ∎

3.3.1 Generalization to $\mathbb{R}^{n}$

In this section, we use Lemma 18 to show that there are sets without optimal Hausdorff oracles in $\mathbb{R}^{n}$ of every possible dimension. We will need the following lemma on giving sufficient conditions for a product set to have optimal Hausdorff oracles. Interestingly, we need the product formula to hold for arbitrary sets, first proven by Lutz [17]. Under the assumption that $F$ is regular, the product formula gives

$\dim_{H}(F\times G)=\dim_{H}(F)+\dim_{H}(G)=\dim_{P}(F)+\dim_{H}(G)$ ,

for every set $G$ .

Lemma 21.

Let $F\subseteq\mathbb{R}^{n}$ be a set such that $\dim_{H}(F)=\dim_{P}(F)$ , let $G\subseteq\mathbb{R}^{m}$ and let $E=F\times G$ . Then $E$ has optimal Hausdorff oracles if and only if $G$ has optimal Hausdorff oracles.

Proof.

Assume that $G$ has an optimal Hausdorff oracle $A_{1}$ . Let $A_{2},A_{3}$ be Hausdorff oracles for $E$ and $F$ , respectively. Let $A\subseteq\mathbb{N}$ be the join of all three oracles. We claim that $A$ is optimal for $E$ . Let $B$ be any oracle and let $\epsilon>0$ . Since $A$ is optimal for $G$ , by Lemma 5, there is a point $z\in G$ such that $\dim^{A,B}(z)\geq\dim_{H}(G)-\epsilon/2$ and

$K^{A,B}_{r}(z)\geq K^{A}_{r}(z)-\epsilon r/2$ ,

for almost every $r$ . By the point-to-set principle, we may choose a $y\in F$ such that

$\dim^{A,B,z}(y)\geq\dim_{H}(F)-\epsilon/2$ .

Let $x=(y,z)\in E$ . Then

	$\displaystyle K^{A,B}_{r}(x)$	$\displaystyle=K^{A,B}_{r}(y,z)$
		$\displaystyle=K^{A,B}_{r}(z)+K^{A,B}_{r}(y\,\|\,z)$
		$\displaystyle\geq K^{A}_{r}(z)-\epsilon r/2+K^{A,B,z}_{r}(y)$
		$\displaystyle\geq K^{A}_{r}(z)-\epsilon r/2+(\dim_{H}(F)-\epsilon/2)r$
		$\displaystyle=K^{A}_{r}(z)-\epsilon r/2+(\dim_{P}(F)-\epsilon/2)r$
		$\displaystyle\geq K^{A}_{r}(z)-\epsilon r/2+K^{A}_{r}(y)-\epsilon r/2$
		$\displaystyle\geq K^{A}_{r}(z)-\epsilon r/2+K^{A}_{r}(y\,\|\,z)-\epsilon r/2$
		$\displaystyle\geq K^{A}_{r}(y,z)-\epsilon r$
		$\displaystyle=K^{A}_{r}(x)-\epsilon r.$

Since $B$ and $\epsilon$ were arbitrary, $A$ is optimal for $E$ .

Suppose that $G$ does not have optimal Hausdorff oracles. Let $A$ be a Hausdorff oracle for $E$ . It suffices to show that $A$ is not optimal for $E$ . Since optimal Hausdorff oracles are closed under the join operation, we may assume that $A$ is a Hausdorff oracle for $F$ and $G$ as well. Since $G$ does not have optimal Hausdorff oracles, there is an oracle $B$ and $\epsilon>0$ such that, for every $z\in G$ , either $\dim^{A,B}(z)<\dim_{H}(G)-\epsilon$ or

$K^{A,B}_{r}(z)<K^{A}_{r}(z)-\epsilon r/2$ ,

for infinitely many $r$ . Let $x\in E$ , such that $\dim^{A,B}(x)\geq\dim_{H}(E)-\epsilon/2$ . Let $x=(y,z)$ for some $y\in F$ and $z\in G$ . Then we have

	$\displaystyle\dim_{H}(F)+\dim_{H}(G)$	$\displaystyle=\dim_{H}(E)$
		$\displaystyle\leq\dim^{A,B}(x)+\epsilon/2$
		$\displaystyle=\dim^{A,B}(y)+\dim^{A,B}(z\,\|\,y)+\epsilon/2$
		$\displaystyle\leq\dim_{H}(F)+\dim^{A,B}(z)+\epsilon/2.$

Hence, $\dim^{A,B}(z)\geq\dim_{H}(G)-\epsilon/2$ .

We conclude that there are infinitely many $r$ such that

	$\displaystyle K^{A,B}_{r}(x)$	$\displaystyle=K^{A,B}_{r}(z)+K^{A,B}_{r}(y\,\|\,z)$
		$\displaystyle<K^{A}_{r}(z)-\epsilon r/2+K^{A,B}_{r}(y\,\|\,z)$
		$\displaystyle\leq K^{A}_{r}(z)-\epsilon r/2+K^{A}_{r}(y\,\|\,z)$
		$\displaystyle=K^{A,B}_{r}(x)-\epsilon r/2.$

Thus $E$ does not have optimal Hausdorff oracles. ∎

Theorem 22.

Assume AC and CH. Then for every $n\in\mathbb{N}$ and $s\in(0,n)$ , there is a subset $E\subseteq\mathbb{R}^{n}$ with $\dim_{H}(E)=s$ such that $E$ does not have optimal Hausdorff oracles.

Proof.

We will show this via induction on $n$ . For $n=1$ , the conclusion follows from Lemma 18.

Suppose the claim holds for all $m<n$ . Let $s\in(0,n)$ . First assume that $s<n-1$ . Then by our induction hypothesis, there is a set $G\subseteq\mathbb{R}^{n-1}$ without optimal Hausdorff oracles such that $\dim_{H}(G)=s$ . Let $E=\{0\}\times G$ . Note that, since $\{0\}$ is a singleton, $\dim_{H}(\{0\})=\dim_{P}(\{0\})=0$ . Therefore, by Lemma 21, $E$ does not have optimal Hausdorff oracles. By the well-known product formula for Hausdorff dimension,

	$\displaystyle\dim_{H}(G)$	$\displaystyle\leq\dim_{H}(\{0\})+\dim_{H}(G)$
		$\displaystyle\leq\dim_{H}(E)$
		$\displaystyle\leq\dim_{P}(\{0\})+\dim_{H}(G)$
		$\displaystyle=\dim_{H}(G),$

and the claim follows.

We now assume that $s\geq n-1$ . Let $d=s-1$ . By our induction hypothesis, there is a set $G\subseteq\mathbb{R}^{n-1}$ without optimal Hausdorff oracles such that $\dim_{H}(G)=d$ . Let $E=[0,1]\times G$ . Note that, since $[0,1]$ has (Lebesgue) measure one, $\dim_{H}([0,1])=\dim_{P}([0,1])=1$ . Thus, by Lemma 21, $E$ is a set without optimal Hausdorff oracles. By the product formula,

	$\displaystyle 1+\dim_{H}(G)$	$\displaystyle\leq\dim_{H}([0,1])+\dim_{H}(G)$
		$\displaystyle\leq\dim_{H}(E)$
		$\displaystyle\leq\dim_{P}([0,1])+\dim_{H}(G)$
		$\displaystyle=1+\dim_{H}(G),$

and the claim follows. ∎

4 Marstrand’s Projection Theorem

The following theorem, due to Lutz and Stull [19], gives sufficient conditions for strong lower bounds on the complexity of projected points.

Theorem 23.

Let $z\in\mathbb{R}^{2}$ , $\theta\in[0,\pi]$ , $C\subseteq\mathbb{N}$ , $\eta\in\mathbb{Q}\cap(0,1)\cap(0,\dim(z))$ , $\varepsilon>0$ , and $r\in\mathbb{N}$ . Assume the following are satisfied.

1.

For every $s\leq r$ , $K_{s}(\theta)\geq s-\log(s)$ .
2.

$K^{C,\theta}_{r}(z)\geq K_{r}(z)-\varepsilon r$ .

Then,

K^{C,\theta}_{r}(p_{\theta}z)\geq\eta r-\varepsilon r-\frac{4\varepsilon}{1-\eta}r-O(\log r)\,.

The second condition of this theorem requires the oracle $(C,\theta)$ to give essentially no information about $z$ . The existence of optimal Hausdorff oracles gives a sufficient condition for this to be true, for all sufficiently large precisions. Thus we are able to show that Marstrands projection theorem holds for any set with optimal Hausdorff oracles.

Theorem 24.

Suppose $E\subseteq\mathbb{R}^{2}$ has an optimal Hausdorff oracle. Then for almost every $\theta\in[0,\pi]$ ,

$\dim_{H}(p_{\theta}E)=\min\{\dim_{H}(E),1\}$ .

Proof.

Let $A$ be an optimal Hausdorff oracle for $E$ . Let $\theta$ be random relative to $A$ . Let $B$ be oracle testifying to the point-to-set principle for $p_{\theta}E$ . It suffices to show that

$\sup\limits_{z\in E}\dim^{A,B}(p_{\theta}z)=\min\{1,\dim_{H}(E)\}$ .

Since $E$ has optimal Hausdorff oracles, for each $n\in\mathbb{N}$ , we may choose a point $z_{n}\in E$ such that

•

$\dim^{A,B,\theta}(z_{n})\geq\dim_{H}(E)-\frac{1}{2n}$ , and
•

$K^{A,B,\theta}_{r}(z_{n})\geq K^{A}_{r}(z_{n})-\frac{r}{2n}$ for almost every $r$ .

Fix a sufficiently large $n$ , and let $\varepsilon=1/2n$ . Let $\eta\in\mathbb{Q}$ be a rational such that

$\min\{1,\dim_{H}(E)\}-5\varepsilon^{1/2}<\eta<1-4\varepsilon^{1/2}$ .

We now show that the conditions of Theorem 23 are satisfied for $\eta,\varepsilon$ , relative to $A$ . By our choice of $\theta$ ,

$K^{A}_{r}(\theta)\geq r-O(\log r)$ ,

for every $r\in\mathbb{N}$ . By our choice of $z_{n}$ and the Hausdorff optimality of $A$ ,

$K^{A,B,\theta}_{r}(z_{n})\geq K_{r}(z_{n})-\varepsilon r$ ,

for all sufficiently large $r$ . We may therefore apply Theorem 23, to see that, for all sufficiently large $r$ ,

K^{A,B,\theta}_{r}(p_{\theta}z_{n})\geq\eta r-\varepsilon r-\frac{4\varepsilon}{1-\eta}r-O(\log r)\,.

Thus,

	$\displaystyle\dim^{A,B}(p_{\theta}z_{n})$	$\displaystyle\geq\dim^{A,B,\theta}(p_{\theta}z_{n})$
		$\displaystyle=\limsup_{r}\frac{K^{A,B,\theta}_{r}(p_{\theta}z_{n})}{r}$
		$\displaystyle\geq\limsup_{r}\frac{\eta r-\varepsilon r-\frac{4\varepsilon}{1-\eta}r-O(\log r)}{r}$
		$\displaystyle=\limsup_{r}\eta-\varepsilon-\frac{4\varepsilon}{1-\eta}-o(1)$
		$\displaystyle>\eta-\varepsilon-\varepsilon^{1/2}-o(1)$
		$\displaystyle>\min\{1,\dim_{H}(E)\}-\varepsilon-6\varepsilon^{1/2}-o(1).$

Hence,

$\lim_{n}\dim^{A,B}(p_{\theta}z_{n})=\min\{1,\dim_{H}(E)\}$ ,

and the proof is complete. ∎

This shows that Marstrand’s theorem holds for every set $E$ with $\dim_{H}(E)=s$ satisfying any of the following:

1.

$E$ is analytic.
2.

$\dim_{H}(E)=\dim_{P}(E)$ .
3.

$\mu\ll\mathcal{H}^{s-\delta}$ , for every $\delta>0$ for some metric outer measure $\mu$ such that $0<\mu(E)<\infty$ .
4.

$\mathcal{H}^{s}\ll\mu$ and $\mathcal{H}^{s}(E)>0$ , for some metric outer measure $\mu$ such that $0<\mu(E)<\infty$ .

For example, the existence of exact gauged Hausdorff measures on $E$ guarantee the existence of optimal Hausdorff oracles.

Example.

Let $E$ be a set with $\dim_{H}(E)=s$ and $\mathcal{H}^{s}(E)=0$ . Suppose that $0<\mathcal{H}^{\phi}(E)<\infty$ , where $\phi(t)=\frac{t^{s}}{\log\frac{1}{t}}$ . Since $\mathcal{H}^{\phi}\ll\mathcal{H}^{s-\delta}$ for every $\delta>0$ , Theorem 13 implies that $E$ has optimal Hausdorff oracles, and thus Marstrand’s theorem holds for $E$ .

Example.

Let $E$ be a set with $\dim_{H}(E)=s$ and $\mathcal{H}^{s}(E)=\infty$ . Suppose that $0<\mathcal{H}^{\phi}(E)<\infty$ , where $\phi(t)=t^{s}\log\frac{1}{t}$ . Since $\mathcal{H}^{s}\ll\mathcal{H}^{\phi}$ , Theorem 13 implies that $E$ has optimal Hausdorff oracles, and thus Marstrand’s theorem holds for $E$ .

4.1 Counterexample to Marstrand’s theorem

In this section we show that there are sets for which Marstrand’s theorem does not hold. While not explicitly mentioning optimal Hausdorff oracles, the construction is very similar to the construction in Section 3.3.

Theorem 25.

Assuming AC and CH, for every $s\in(0,1)$ there is a set $E$ such that $\dim_{H}(E)=1+s$ but

$\dim_{H}(p_{\theta}E)=s$

for every $\theta\in(\pi/4,3\pi/4)$ .

This is a modest generalization of Davies’ theorem to sets with Hausdorff dimension strictly greater than one. In the next section we give a new proof of Davies’ theorem by generalizing this construction to the endpoint $s=0$ .

We will need the following simple observation.

Observation 26.

Let $r\in\mathbb{N}$ , $s\in(0,1)$ , and $\theta\in(\pi/8,3\pi/8)$ . Then for every dyadic rectangle

$R=[d_{x}-2^{-r},d_{x}+2^{-r}]\times[d_{y}-2^{-sr},d_{y}+2^{-sr}]$ ,

there is a point $z\in R$ such that $K^{\theta}_{r}(p_{\theta}z)\leq sr+o(r)$ .

Proof.

Note that $p_{\theta}$ is a Lipschitz function. Thus, for any rectangle

$R=[d_{x}-2^{-r},d_{x}+2^{-r}]\times[d_{y}-2^{-sr},d_{y}+2^{-sr}]$ ,

The length of its projection (which is an interval) is

$|p_{\theta}R|\geq c2^{-sr}$

for some constant $c$ . It is well known that any interval of length $2^{-\ell}$ contains points $x$ such that

$K_{r}(x)\leq\ell r+o(r)$ .

∎

For every $r\in\mathbb{N}$ , $\theta\in(\pi/4,3\pi/4)$ , binary string $x$ of length $r$ and string $y$ of length $sr$ , let $g_{\theta}(x,y)\mapsto z$ be a function such that

$K^{\theta}_{r}(p_{\theta}\,(x,z))\leq sr+o(r)$ .

That is, $g_{\theta}$ , given a rectangle

$R=[d_{x}-2^{-r},d_{x}+2^{-r}]\times[d_{y}-2^{-sr},d_{y}+2^{-sr}]$ ,

outputs a value $z$ such that $K_{r}(p_{\theta}(x,z))$ is small.

Let $s\in(0,1)$ . We begin by defining two sequences of natural numbers, $\{a_{n}\}$ and $\{b_{n}\}$ . Let $a_{1}=2$ , and $b_{1}=\lfloor 2/s\rfloor$ . Inductively define $a_{n+1}=b_{n}^{2}$ and $b_{n+1}=\lfloor a_{n+1}/s\rfloor$ . We will also need, for every ordinal $\alpha$ , a function $f_{\alpha}:\mathbb{N}\to\{\beta\,|\,\beta<\alpha\}$ such that each ordinal $\beta<\alpha$ is mapped to by infinitely many $n$ . Note that such a function exists, since the range is countable assuming CH.

Using AC and CH, we first order the subsets of the natural numbers and we order the angles $\theta\in(\pi/4,3\pi/4)$ so that each has at most countably many predecessors.

We will define real numbers $x_{\alpha}$ , $y_{\alpha}$ and $z_{\alpha}$ inductively. Let $x_{1}$ be a real which is random relative to $A_{1}$ . Let $y_{1}$ be a real which is random relative to $(A_{1},x_{1})$ . Define $z_{1}$ to be the real whose binary expansion is given by

\displaystyle z_{1}[r]=\begin{cases}g_{\theta_{1}}(x_{1},y_{1})[r]&\text{ if }a_{n}<r\leq b_{n}\text{ for some }n\in\mathbb{N}\\ y_{1}[r]&\text{ otherwise}\end{cases}

For the induction step, suppose we have defined our points up to ordinal $\alpha$ . Let $x_{\alpha}$ be a real number which is random relative to the join of $\bigcup_{\beta<\alpha}(A_{\beta},x_{\beta})$ and $A_{\alpha}$ . Let $y_{\alpha}$ be random relative to the join of $\bigcup_{\beta<\alpha}(A_{\beta},x_{\beta})$ , $A_{\alpha}$ and $x_{\alpha}$ . This is possible, as we are assuming CH, and so this union is countable. Let $z_{\alpha}$ be the point whose binary expansion is given by

\displaystyle z_{\alpha}[r]=\begin{cases}g_{\theta_{\beta}}(x_{\alpha},y_{\alpha})[r]&\text{ if }a_{n}<r\leq b_{n},\text{ for }f_{\alpha}(n)=\beta\\ y_{\alpha}[r]&\text{ otherwise}\end{cases}

Finally, we define our set $E=\{(x_{\alpha},z_{\alpha})\}$ .

Lemma 27.

For every $\theta\in(\pi/4,3\pi/4)$ ,

$\dim_{H}(p_{\theta}E)\leq s$

Proof.

Let $\theta\in(\pi/4,3\pi/4)$ and $\alpha$ be its corresponding ordinal. Let $A$ be an oracle encoding $\theta$ and

$\bigcup\limits_{\beta\leq\alpha}(x_{\beta},y_{\beta},z_{\beta})$ .

Note that, since we assumed CH, this is a countable union, and so the oracle is well defined.

Let $z=(x_{\beta},z_{\beta})\in E$ . First assume that $\beta\leq\alpha$ . Then, by our construction of $A$ , all the information of $p_{\theta}z$ is already encoded in our oracle, and so

$K^{A}_{r}(p_{\theta}z)=o(r)$ .

Now assume that $\beta>\alpha$ . Then by our construction of $E$ , there are infinitely many $n$ such that $f_{\beta}(n)=\alpha$ . Therefore there are infinitely many $n$ such that

$z_{\beta}[r]=g_{\theta_{\alpha}}(x_{\beta},y_{\beta})[r]$ ,

for $a_{n}<r\leq b_{n}$ . Recalling the definition of $g_{\theta_{\alpha}}$ , this means that, for each such $n$ ,

$K^{\theta}_{b_{n}}(p_{\theta}z)=sb_{n}+o(r)$ .

Therefore, by the point-to-set principle,

	$\displaystyle\dim_{H}(p_{\theta}E)$	$\displaystyle\leq\sup_{z\in E}\dim^{A}(p_{\theta}z)$
		$\displaystyle\leq\sup_{\beta>\alpha}\liminf_{n}\frac{K^{A}_{b_{n}}(p_{\theta}z)}{b_{n}}$
		$\displaystyle\leq\sup_{\beta>\alpha}\liminf_{n}\frac{sb_{n}}{b_{n}}$
		$\displaystyle=s,$

and the proof is complete. ∎

Lemma 28.

The Hausdorff dimension of $E$ is $1+s$ .

Proof.

We first give an upper bound on the dimension. Let $A$ be an oracle encoding $\theta_{1}$ . Let $z=(x_{\alpha},z_{\alpha})$ . By our construction of $E$ , there are infinitely many $n$ such that $f_{\alpha}(n)=1$ . Therefore there are infinitely many $n$ such that

$z_{\beta}[r]=g_{\theta_{1}}(x_{\beta},y_{\beta})[r]$ ,

for $a_{n}<r\leq b_{n}$ . Recalling the definition of $g_{\theta_{1}}$ , this means that, for each such $n$ ,

$K^{\theta_{1}}_{b_{n}}(p_{\theta_{1}}z)=sb_{n}+o(r)$ .

Moreover,

	$\displaystyle K^{\theta_{1}}_{b_{n}}(x_{\alpha},z_{\alpha})$	$\displaystyle\leq K^{\theta_{1}}_{b_{n}}(x_{\alpha})+K^{\theta_{1}}_{b_{n}}(z_{\alpha}\mid x_{\alpha})+o(r)$
		$\displaystyle\leq b_{n}+K^{\theta_{1}}_{b_{n}}(p_{\theta_{1}}z)+o(r)$
		$\displaystyle\leq b_{n}+sb_{n}+o(b_{n})).$

Therefore, by the point-to-set principle,

	$\displaystyle\dim_{H}(E)$	$\displaystyle\leq\sup_{z\in E}\dim^{A}(z)$
		$\displaystyle\leq\sup_{z\in E}\liminf_{n}\frac{K^{A}_{b_{n}}(z)}{b_{n}}$
		$\displaystyle\leq\sup_{z\in E}\liminf_{n}\frac{(1+s)b_{n}+o(b_{n})}{b_{n}}$
		$\displaystyle=1+s.$

For the upper bound, let $A$ be a Hausdorff oracle for $E$ , and let $\alpha$ be the ordinal corresponding to $A$ . By construction of $z=(x_{\alpha},z_{\alpha})$ ,

$K^{A}_{r}(x_{\alpha})\geq r-o(r)$ ,

for all $r\in\mathbb{N}$ . We also have, for every $n$ ,

	$\displaystyle K^{A}_{a_{n}}(z_{\alpha}\,\|\,x_{\alpha})$	$\displaystyle\geq K^{A}_{a_{n}}(y_{\alpha}\,\|\,x_{\alpha})-b_{n-1}-o(a_{n})$
		$\displaystyle\geq a_{n}-b_{n-1}-o(a_{n})$
		$\displaystyle=a_{n}-a^{\frac{1}{2}}_{n}-o(a_{n}).$

Hence, for every $n$ and every $a_{n}<r\leq b_{n}$ ,

	$\displaystyle K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})$	$\displaystyle\geq K^{A}_{a_{n}}(z_{\alpha}\,\|\,x_{\alpha})$
		$\displaystyle\geq a_{n}-a^{\frac{1}{2}}_{n}-o(a_{n}).$

This implies that

	$\displaystyle\frac{K^{A}_{r}(x_{\alpha},z_{\alpha})}{r}$	$\displaystyle=\frac{K^{A}_{r}(x_{\alpha})+K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})}{r}$
		$\displaystyle\geq\frac{r+a_{n}-a^{\frac{1}{2}}_{n}-o(a_{n})}{r}$
		$\displaystyle=1+s-o(1).$

We can also conclude that, for every $n$ and every $b_{n}<r\leq a_{n+1}$ ,

	$\displaystyle K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})$	$\displaystyle\geq K^{A}_{b_{n}}(z_{\alpha}\,\|\,x_{\alpha})K^{A}_{a_{n},b_{n}}(z_{\alpha}\,\|\,x_{\alpha})-o(r)$
		$\displaystyle\geq a_{n}-a^{\frac{1}{2}}_{n}+r-b_{n}-o(r).$

This implies that

	$\displaystyle\frac{K^{A}_{r}(x_{\alpha},z_{\alpha})}{r}$	$\displaystyle=\frac{K^{A}_{r}(x_{\alpha})+K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})}{r}$
		$\displaystyle\geq\frac{r+a_{n}-a^{\frac{1}{2}}_{n}+r-b_{n}-o(r)}{r}$
		$\displaystyle\geq 1+s-o(1).$

These inequalities, combined with the point-to-set principle show that

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\sup_{z\in E}\dim^{A}(z)$
		$\displaystyle\geq\sup_{z\in E}\liminf_{r}\frac{K^{A}_{r}(z)}{r}$
		$\displaystyle\geq\sup_{z\in E}\liminf_{r}1+s$
		$\displaystyle=1+s,$

and the proof is complete. ∎

4.2 Generalization to the endpoint $s=0$

Theorem 29.

Assuming AC and CH, there is a set $E$ such that $\dim_{H}(E)=1$ but

$\dim_{H}(p_{\theta}E)=0$

for every $\theta\in(\pi/4,3\pi/4)$ .

For every $r\in\mathbb{N}$ , $\theta\in(\pi/4,3\pi/4)$ , binary string $x$ of length $r$ and string $y$ of length $sr$ , let $g^{s}_{\theta}(x,y)\mapsto z$ be a function such that

$K^{\theta}_{r}(p_{\theta}\,(x,z))\leq sr+o(r)$ .

That is, $g^{s}_{\theta}$ , given a rectangle

$R=[d_{x}-2^{-r},d_{x}+2^{-r}]\times[d_{y}-2^{-sr},d_{y}+2^{-sr}]$ ,

outputs a value $z$ such that $K_{r}(p_{\theta}(x,z))$ is small.

We begin by defining two sequences of natural numbers, $\{a_{n}\}$ and $\{b_{n}\}$ . Let $a_{1}=2$ , and $b_{1}=4$ . Inductively define $a_{n+1}=b_{n}^{2}$ and $b_{n+1}=(n+1)\lfloor a_{n+1}\rfloor$ . We will also need, for every ordinal $\alpha$ , a function $f_{\alpha}:\mathbb{N}\to\{\beta\,|\,\beta<\alpha\}$ such that each ordinal $\beta<\alpha$ is mapped to by infinitely many $n$ . Note that such a function exists, since the range is countable assuming CH.

Using AC and CH, we first order the subsets of the natural numbers and we order the angles $\theta\in(\pi/4,3\pi/4)$ so that each has at most countably many predecessors.

\displaystyle z_{1}[r]=\begin{cases}g^{1}_{\theta_{1}}(x_{1},y_{1})[r]&\text{ if }a_{n}<r\leq b_{n}\text{ for some }n\in\mathbb{N}\\ y_{1}[r]&\text{ otherwise}\end{cases}

\displaystyle z_{\alpha}[r]=\begin{cases}g^{1/n}_{\theta_{\beta}}(x_{\alpha},y_{\alpha})[r]&\text{ if }a_{n}<r\leq b_{n},\text{ for }f_{\alpha}(n)=\beta\\ y_{\alpha}[r]&\text{ otherwise}\end{cases}

Finally, we define our set $E=\{(x_{\alpha},z_{\alpha})\}$ .

Lemma 30.

For every $\theta\in(\pi/4,3\pi/4)$ ,

$\dim_{H}(p_{\theta}E)=0$ .

Proof.

Let $\theta\in(\pi/4,3\pi/4)$ and $\alpha$ be its corresponding ordinal. Let $A$ be an oracle encoding $\theta$ and

$\bigcup\limits_{\beta\leq\alpha}(x_{\beta},y_{\beta},z_{\beta})$ .

Note that, since we assumed CH, this is a countable union, and so the oracle is well defined.

Let $z=(x_{\beta},z_{\beta})\in E$ . First assume that $\beta\leq\alpha$ . Then, by our construction of $A$ , all the information of $p_{\theta}z$ is already encoded in our oracle, and so

$K^{A}_{r}(p_{\theta}z)=o(r)$ .

Now assume that $\beta>\alpha$ . Then by our construction of $E$ , there are infinitely many $n$ such that $f_{\beta}(n)=\alpha$ . Therefore there are infinitely many $n$ such that

$z_{\beta}[r]=g^{1/n}_{\theta_{\alpha}}(x_{\beta},y_{\beta})[r]$ ,

for $a_{n}<r\leq b_{n}$ . Recalling the definition of $g^{1/n}_{\theta_{\alpha}}$ , this means that, for each such $n$ ,

$K^{\theta}_{b_{n}}(p_{\theta}z)=\frac{b_{n}}{n}+o(r)$ .

Therefore, by the point-to-set principle,

	$\displaystyle\dim_{H}(p_{\theta}E)$	$\displaystyle\leq\sup_{z\in E}\dim^{A}(p_{\theta}z)$
		$\displaystyle\leq\sup_{\beta>\alpha}\liminf_{n}\frac{K^{A}_{b_{n}}(p_{\theta}z)}{b_{n}}$
		$\displaystyle\leq\sup_{\beta>\alpha}\liminf_{n}\frac{\frac{b_{n}}{n}}{b_{n}}$
		$\displaystyle=\frac{1}{n},$

and the proof is complete. ∎

Lemma 31.

The Hausdorff dimension of $E$ is $1$ .

Proof.

$z_{\beta}[r]=g^{1/n}_{\theta_{1}}(x_{\beta},y_{\beta})[r]$ ,

for $a_{n}<r\leq b_{n}$ . Recalling the definition of $g^{1/n}_{\theta_{1}}$ , this means that, for each such $n$ ,

$K^{\theta_{1}}_{b_{n}}(p_{\theta_{1}}z)=\frac{b_{n}}{n}+o(r)$ .

Moreover,

	$\displaystyle K^{\theta_{1}}_{b_{n}}(x_{\alpha},z_{\alpha})$	$\displaystyle\leq K^{\theta_{1}}_{b_{n}}(x_{\alpha})+K^{\theta_{1}}_{b_{n}}(z_{\alpha}\mid x_{\alpha})+o(r)$
		$\displaystyle\leq b_{n}+K^{\theta_{1}}_{b_{n}}(p_{\theta_{1}}z)+o(r)$
		$\displaystyle\leq b_{n}+\frac{b_{n}}{n}+o(b_{n})).$

Therefore, by the point-to-set principle,

	$\displaystyle\dim_{H}(E)$	$\displaystyle\leq\sup_{z\in E}\dim^{A}(z)$
		$\displaystyle\leq\sup_{z\in E}\liminf_{n}\frac{K^{A}_{b_{n}}(z)}{b_{n}}$
		$\displaystyle\leq\sup_{z\in E}\liminf_{n}\frac{(b_{n}+b_{n}/n+o(b_{n})}{b_{n}}$
		$\displaystyle=1.$

For the upper bound, let $A$ be a Hausdorff oracle for $E$ , and let $\alpha$ be the ordinal corresponding to $A$ . By construction of $z=(x_{\alpha},z_{\alpha})$ ,

$K^{A}_{r}(x_{\alpha})\geq r-o(r)$ ,

for all $r\in\mathbb{N}$ . We also have, for every $n$ ,

	$\displaystyle K^{A}_{a_{n}}(z_{\alpha}\,\|\,x_{\alpha})$	$\displaystyle\geq K^{A}_{a_{n}}(y_{\alpha}\,\|\,x_{\alpha})-b_{n-1}-o(a_{n})$
		$\displaystyle\geq a_{n}-b_{n-1}-o(a_{n})$
		$\displaystyle=a_{n}-a^{\frac{1}{2}}_{n}-o(a_{n}).$

Hence, for every $n$ and every $a_{n}<r\leq b_{n}$ ,

	$\displaystyle K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})$	$\displaystyle\geq K^{A}_{a_{n}}(z_{\alpha}\,\|\,x_{\alpha})$
		$\displaystyle\geq a_{n}-a^{\frac{1}{2}}_{n}-o(a_{n}).$

This implies that

	$\displaystyle\frac{K^{A}_{r}(x_{\alpha},z_{\alpha})}{r}$	$\displaystyle=\frac{K^{A}_{r}(x_{\alpha})+K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})}{r}$
		$\displaystyle\geq\frac{r+a_{n}-a^{\frac{1}{2}}_{n}-o(a_{n})}{r}$
		$\displaystyle=1-o(1).$

We can also conclude that, for every $n$ and every $b_{n}<r\leq a_{n+1}$ ,

	$\displaystyle K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})$	$\displaystyle\geq K^{A}_{b_{n}}(z_{\alpha}\,\|\,x_{\alpha})+K^{A}_{a_{n},b_{n}}(z_{\alpha}\,\|\,x_{\alpha})-o(r)$
		$\displaystyle\geq a_{n}-a^{\frac{1}{2}}_{n}+r-b_{n}-o(r).$

This implies that

	$\displaystyle\frac{K^{A}_{r}(x_{\alpha},z_{\alpha})}{r}$	$\displaystyle=\frac{K^{A}_{r}(x_{\alpha})+K^{A}_{r}(z_{\alpha}\,\|\,x_{\alpha})}{r}$
		$\displaystyle\geq\frac{r+a_{n}-a^{\frac{1}{2}}_{n}+r-b_{n}-o(r)}{r}$
		$\displaystyle\geq 1-o(1).$

These inequalities, combined with the point-to-set principle show that

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\sup_{z\in E}\dim^{A}(z)$
		$\displaystyle\geq\sup_{z\in E}\liminf_{r}\frac{K^{A}_{r}(z)}{r}$
		$\displaystyle\geq\sup_{z\in E}1$
		$\displaystyle=1,$

and the proof is complete. ∎

5 Optimal Packing Oracles

Similarly, we can define optimal packing oracles for a set.

Definition 32.

Let $E\subseteq\mathbb{R}^{n}$ and $A\subseteq\mathbb{N}$ . We say that $A$ is an optimal packing oracle (or packing optimal) for $E$ if the following conditions are satisfied.

1.

$A$ is a packing oracle for $E$ .
2.

For every $B\subseteq\mathbb{N}$ and every $\epsilon>0$ there is a point $x\in E$ such that $\operatorname{Dim}^{A,B}(x)\geq\dim_{P}(E)-\epsilon$ and for almost every $r\in\mathbb{N}$

$K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r$ .

Let $E\subseteq\mathbb{R}^{n}$ and $A\subseteq\mathbb{N}$ . For $B\subseteq\mathbb{N}$ , $\epsilon>0$ define the set

$N(A,B,\epsilon)=\{x\in E\,|\,(\forall^{\infty}r)\,K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r\}$

Proposition 33.

Let $E\subseteq\mathbb{R}^{n}$ be a set such that $\dim_{P}(E)>0$ and let $A$ be an oracle. Then $A$ is packing optimal for $E$ if and only if $A$ is a packing oracle and for every $B\subseteq\mathbb{N}$ and $\epsilon>0$ , $\dim_{P}(N(A,B,\epsilon))=\dim_{P}(E)$ .

Proof.

For the forward direction, let $A$ be an optimal packing oracle for $E$ . Then by the first condition of the definition, $A$ is a packing oracle. Let $B\subseteq\mathbb{N}$ and $\epsilon>0$ . Let $C$ be a packing oracle for $N(A,B,\epsilon)$ . For the sake of contradiction, suppose that

$\dim_{P}(N(A,B,\epsilon))<\dim_{P}(E)-\gamma$ ,

for some $\gamma>0$ . We will, without loss of generality, assume that $\gamma<\epsilon$ . Then, by the point to set principle, for every $x\in N(A,B,\epsilon)$ ,

	$\displaystyle\operatorname{Dim}^{A,(B,C)}(x)$	$\displaystyle\leq\operatorname{Dim}^{C}(x)$
		$\displaystyle\leq\dim_{P}(N(A,B,\epsilon))$
		$\displaystyle<\dim_{P}(E)-\gamma.$

Since, $A$ is an optimal packing oracle for $E$ , there is a point $x\in E$ such that $\operatorname{Dim}^{A,(B,C)}(x)\geq\dim_{P}(E)-\gamma$ and for almost every $r\in\mathbb{N}$

$K^{A,(B,C)}_{r}(x)\geq K^{A}_{r}(x)-\gamma r$ .

By our previous discussion, any such point $x$ cannot be in $N(A,B,\epsilon)$ . However, if $x\notin N(A,B,\epsilon)$ , then for infinitely many $r$ ,

$K^{A,(B,C)}_{r}(x)<K^{A}_{r}(x)-\epsilon r$ .

Thus, no such $x$ exists, contradicting the fact that $A$ is packing optimal.

	$\displaystyle\dim_{H}(E)$	$\displaystyle=\dim_{H}(N(A,B,\epsilon))$
		$\displaystyle\leq\sup\limits_{x\in N(A,B,\epsilon)}\dim^{A,B}(x).$

Therefore, there is certainly a point $x\in E$ such that $\dim^{A,B}(x)\geq\dim_{H}(E)-\epsilon$ and

$K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r$ ,

for almost every $r\in\mathbb{N}$ . ∎

Lemma 34.

Let $E\subseteq\mathbb{R}^{n}$ . If $A$ is packing optimal for $E$ , then the join $C=(A,B)$ is packing optimal for $E$ for every oracle $B$ .

Proof.

Let $A$ be an optimal packing oracle for $E$ , let $B$ be an oracle and let $C=(A,B)$ . By the point-to-set principle (Theorem 2),

	$\displaystyle\dim_{P}(E)$	$\displaystyle=\sup\limits_{x\in E}\operatorname{Dim}^{A}(x)$
		$\displaystyle\geq\sup\limits_{x\in E}\operatorname{Dim}^{C}(x)$
		$\displaystyle\geq\dim_{P}(E).$

Hence, the oracle $C=(A,B)$ is a packing oracle for $E$ .

Let $B^{\prime}\subseteq\mathbb{N}$ be an oracle, and let $\epsilon>0$ . Let $x\in E$ be a point such that

\operatorname{Dim}^{A,(B,B^{\prime})}(x)\geq\dim_{P}(E)-\epsilon/2,

(7)

and

K_{r}^{A,(B,B^{\prime})}(x)\geq K^{A}_{r}(x)-\epsilon r/2,

(8)

for almost every precision $r$ . Note that such a point exists since $A$ is packing optimal for $E$ .

For all sufficiently large $r$ ,

	$\displaystyle K^{(A,B),B^{\prime}}_{r}(x)$	$\displaystyle=K^{A,(B,B^{\prime})}_{r}(x)$
		$\displaystyle\geq K^{A}_{r}(x)-\epsilon r/2$
		$\displaystyle\geq K^{A,B}_{r}(x)-\epsilon r/2$
		$\displaystyle=K^{C}_{r}(x)-\epsilon r/2.$

Therefore, $C=(A,B)$ is packing optimal for $E$ . ∎

We now give some basic closure properties of the class of sets with optimal packing oracles.

Observation 35.

Let $F\subseteq E$ . If $\dim_{P}(F)=\dim_{P}(E)$ and $F$ has an optimal packing oracle, then $E$ has an optimal packing oracle.

We can also show that having optimal packing oracles is closed under countable unions.

Lemma 36.

Let $E_{1},E_{2},\ldots$ be a countable sequence of sets and let $E=\cup_{n}E_{n}$ . If every set $E_{n}$ has an optimal packing oracle, then $E$ has an optimal Hausdorff oracle.

Proof.

We first note that

$\dim_{P}(E)=\sup_{n}\dim_{P}(E_{n})$ .

For each $n$ , let $A_{n}$ be an optimal packing oracle for $E_{n}$ . Let $A$ be the join of $A_{1},A_{2},\ldots$ . Let $B$ be an oracle guaranteed by Theorem 2 such that

$\sup_{x}\operatorname{Dim}^{B}(x)=\sup_{n}\dim_{P}(E_{n})$ .

Note that, by Lemma 5, for every $n$ , $(A,B)$ is packing optimal for $E_{n}$ .

We now claim that $(A,B)$ is an optimal packing oracle for $E$ . Theorem 2 shows that item (1) of the definition of optimal packing oracles is satisfied. For item (2), let $C\subseteq\mathbb{N}$ be an oracle, and let $\epsilon>0$ . Let $n$ be a number such that $\dim_{P}(E_{n})>\dim_{P}(E)-\epsilon$ . Since $(A,B)$ is packing optimal for $E_{N}$ , there is a point $x\in E_{n}$ such that

(i)

$\dim^{(A,B),C}(x)\geq\dim_{P}(E_{n})-\epsilon\geq\dim_{P}(E)-\epsilon$ , and
(ii)

for almost every $r$ ,

$K^{(A,B),C}_{r}(x)\geq K^{(A,B)}_{r}(x)-\epsilon r$ .

Therefore, item (2) of the definition of optimal packing oracles is satisfied, and so $(A,B)$ is Hausdorff optimal for $E$ . ∎

For every $0\leq\alpha<\beta\leq 1$ define the set

$D_{\alpha,\beta}=\{x\in(0,1)\,|\,\dim(x)=\alpha\text{ and }\operatorname{Dim}(x)=\beta\}$ .

Lemma 37.

For every $0\leq\alpha<\beta\leq 1$ , $D_{\alpha,\beta}$ has optimal Hausdorff and optimal packing oracles and

	$\displaystyle\dim_{H}(D_{\alpha,\beta})=\alpha$
	$\displaystyle\dim_{P}(D_{\alpha,\beta})=\beta.$

Proof.

We begin by noting that $D_{\alpha,\beta}$ is Borel. Therefore, by Theorems 13 and 39, $D_{\alpha,\beta}$ has optimal Hausdorff and optimal packing oracles. Thus, it suffices to show prove the dimension equalities.

Define the increasing sequence of natural numbers $\{h_{j}\}$ inductively as follows. Let $h_{1}=2$ , and let $h_{j+1}=2^{h_{j}}$ . For every oracle $A$ let $z_{A}$ be a point such that, for every $\delta>0$ and all sufficiently large $r$ ,

$K^{A}_{(1+\delta)r,r}(z_{A}\,|\,z_{A})=\alpha\delta r=K_{(1+\delta)r,r}(z_{A}\,|\,z_{A})$ .

Let $y_{A}$ be random relative to $A$ and $z_{A}$ .

Let $x_{A}$ be the point whose binary expansion is given by

\displaystyle x_{A}[r]=\begin{cases}z_{A}[r]&\text{ if }h_{j}<r\leq\frac{1-\beta}{1-\alpha}h_{j+1}\text{ for some }j\in\mathbb{N}\\ y_{A}[r]&\text{ otherwise}\end{cases}

Let $A$ be an oracle, and consider the point $x_{A}$ . Let $r\in\mathbb{N}$ be sufficiently large and let $j\in\mathbb{N}$ such that $h_{j}<r\leq h_{j+1}$ . We first suppose that $r\leq\frac{1-\beta}{1-\alpha}h_{j+1}$ . Then

$\displaystyle K_{r}(x_{A})$	$\displaystyle\geq K^{A}_{r}(x_{A})$	$\displaystyle=K^{A}_{h_{j}}(x_{A})+K^{A}_{r,h_{j}}(x_{A}\,\|\,x_{A})$
	$\displaystyle=O(\log r)+K^{A}_{r,h_{j-1}}(z_{A}\,\|\,z_{A})$
	$\displaystyle=\alpha r+O(\log r)$
	$\displaystyle\geq K_{r}(x_{A}).$

Now suppose that $r>\frac{1-\beta}{1-\alpha}h_{j+1}$ . Let $t=\frac{1-\beta}{1-\alpha}h_{j+1}$ . Then

	$\displaystyle K_{r}(x_{A})$	$\displaystyle\geq K^{A}_{r}(x_{A})$
		$\displaystyle=K^{A}_{t}(x_{A})+K^{A}_{r,t}(x_{A}\,\|\,x_{A})+O(\log r)$
		$\displaystyle=\alpha t+K^{A}_{r,t}(x_{A}\,\|\,x_{A})+O(\log r)$
		$\displaystyle=\alpha t+r-t+O(\log r)$
		$\displaystyle=r-t(1-\alpha)+O(\log r)$
		$\displaystyle=r-(1-\beta)h_{j+1}+O(\log r)$
		$\displaystyle\geq K_{r}(x_{A}).$

In particular, $K^{A}_{r}(x_{A})\geq\alpha r$ for every $h_{j}<r\leq h_{j+1}$ . Hence for every oracle $A$ ,

$\dim^{A}(x_{A})=\alpha=\dim(x_{A})$ .

For all sufficiently large $j$ ,

	$\displaystyle K_{h_{j}}(x_{A})$	$\displaystyle=K^{A}_{r}(x_{A})$
		$\displaystyle=h_{j}-(1-\beta)h_{j}+O(\log r)$
		$\displaystyle=\beta h_{j}+O(\log r),$

and so

$\operatorname{Dim}^{A}(x_{A})=\beta=\operatorname{Dim}(x_{A})$ .

Therefore, for every $A$ , $x_{A}\in D_{\alpha,\beta}$ .

Finally, by the above bounds,

	$\displaystyle\dim_{H}(D_{\alpha,\beta})=\alpha$
	$\displaystyle\dim_{P}(D_{\alpha,\beta})=\beta.$

∎

5.1 Sufficient conditions for optimal packing oracles

Lemma 38.

Let $E\subseteq\mathbb{R}^{n}$ be a set such that $\dim_{H}(E)=\dim_{P}(E)=s$ . Then $E$ has optimal Hausdorff and optimal packing oracles.

Proof.

Lemma 17 shows that $E$ has optimal Hausdorff oracles. Let $A_{1}$ be an optimal Hausdorff oracle for $E$ . Let $A_{2}$ be a packing oracle for $E$ . Let $A=(A_{1},A_{2})$ . By Lemma 5, $A$ is an optimal Hausdorff oracle for $E$ . We now show that $A$ is an optimal packing oracle for $E$ .

It is clear that $A$ is a packing oracle for $E$ . Let $B\subseteq\mathbb{N}$ and $\epsilon>0$ . Since $A$ is Hausdorff optimal for $E$ , there is a point $x\in E$ such that $\dim^{A,B}(x)\geq s-\epsilon$ and

$K^{A,B}_{r}(x)\geq K^{A}_{r}(x)-\epsilon r$

for almost every $r$ . Therefore

	$\displaystyle\operatorname{Dim}^{A,B}(x)$	$\displaystyle\geq\dim^{A,B}(x)$
		$\displaystyle\geq s-\epsilon$
		$\displaystyle=\dim_{P}(E)-\epsilon.$

Therefore $x$ satisfies the second condition of optimal packing oracles, and the conclusion follows. ∎

Theorem 39.

Let $E\subseteq\mathbb{R}^{n}$ with $\dim_{P}(E)=s$ . Suppose there is a metric outer measure $\mu$ such that

$0<\mu(E)<\infty$ ,

and either

1.

$\mu\ll\mathcal{P}^{s}$ , or
2.

$\mathcal{P}^{s}\ll\mu$ and $\mathcal{P}^{s}(E)>0$ .

Then $E$ has an optimal packing oracle $A$ .

Proof.

Let $A\subseteq\mathbb{N}$ be a packing oracle for $E$ such that $p_{\mu,E}$ is computable relative to $A$ . Note that such an oracle exists by the point-to-set principle and routine encoding. We will show that $A$ is packing optimal for $E$ .

For the sake of contradiction, suppose that there is an oracle $B$ and $\epsilon>0$ such that, for every $x\in E$ either

1.

$\operatorname{Dim}^{A,B}(x)<s-\epsilon$ , or
2.

there are infinitely many $r$ such that $K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r$ .

Let $N$ be the set of all $x$ for which the second item holds. By Lemma 12, $\mu(N)=0$ . We also note that, by the point-to-set principle,

$\operatorname{Dim}_{H}(E-N)\leq s-\epsilon$ ,

and so $\mathcal{P}^{s}(E-N)=0$ .

To achieve the desired contradiction, we first assume that $\mu\ll\mathcal{P}^{s}$ . In this case, it suffices to show that $\mu(E-N)>0$ . Since $\mu\ll\mathcal{P}^{s}$ ,

$\mu(E-N)=0$ .

Since $\mu$ is a metric outer measure,

	$\displaystyle 0$	$\displaystyle<\mu(E)$
		$\displaystyle\leq\mu(N)+\mu(E-N)$
		$\displaystyle=0,$

a contradiction.

Now suppose that $\mathcal{P}^{s}\ll\mu$ and $\mathcal{P}^{s}(E)>0$ . Then, since $\mathcal{P}^{s}$ is an outer measure, $\mathcal{P}^{s}(E)>0$ and $\mathcal{P}^{s}(E-N)=0$ we must have $\mathcal{P}^{s}(N)>0$ . However this implies that $\mu(N)>0$ , and we again have the desired contradiction. Thus $A$ is an optimal packing oracle for $E$ and the proof is complete. ∎

We now show that every analytic set has optimal packing oracles.

Lemma 40.

Every analytic set $E$ has optimal packing oracles.

Proof.

A set $E\subseteq\mathbb{R}^{n}$ is called an packing $s$ -set if

$0<\mathcal{P}^{s}(E)<\infty$ .

Since $\mathcal{P}^{s}$ is a metric outer measure, and trivially absolutely continuous with respect to itself, Theorem 39 shows that if $E$ is a packing $s$ -set then there is an optimal packing oracle for $E$ .

Now assume that $E$ is compact, and let $s=\dim_{H}(E)$ . Then for every $t<s$ , $\mathcal{H}^{t}(E)>0$ . Thus, by Theorem 1, there is a sequence of compact subsets $F_{1},F_{2},\ldots$ of $E$ such that

$\dim_{P}(\bigcup_{n}F_{n})=\dim_{P}(E)$ ,

and, for each $n$ ,

$0<\mathcal{P}^{s_{n}}(F_{n})<\infty$ ,

where $s_{n}=s-1/n$ . Therefore, each set $F_{n}$ has optimal packing oracles. Hence, by Lemma 36, $E$ has optimal packing oracles and the conclusion follows.

We now show that every $\Sigma^{0}_{2}$ set has optimal packing oracles. Suppose $E=\cup_{n}F_{n}$ is $\Sigma^{0}_{1}$ , where each $F_{n}$ is compact. As we have just seen, each $F_{n}$ has optimal packing oracles. Therefore, by Lemma 36, $E$ has optimal packing oracles and the conclusion follows.

Finally, let $E$ be analytic. By Theorem 1, there is a $\Sigma^{0}_{2}$ subset $F$ of the same packing dimension as $E$ . We have just seen that $F$ must have an optimal packing oracle. Since $\dim_{P}(F)=\dim_{P}(E)$ , by Observation 35 $E$ has optimal packing oracles, and the proof is complete ∎

5.2 Sets without optimal oracles

Theorem 41.

Assuming CH and AC, for every $0<s_{1}<s_{2}\leq 1$ there is a set $E\subseteq\mathbb{R}$ which does not have Hausdorff optimal nor packing optimal oracles such that

$\dim_{H}(E)=s_{1}$ and $\dim_{P}(E)=s_{2}$ .

Proof.

Let $\delta=s_{2}-s_{1}$ . We begin by defining two sequences of natural numbers, $\{a_{n}\}$ and $\{b_{n}\}$ . Let $a_{1}=2$ , and $b_{1}=4$ . Inductively define $a_{n+1}=2^{b_{n}}$ and $b_{n+1}=2^{a_{n+1}}$ .

We will define real numbers $w_{\alpha}$ , $x_{\alpha}$ , $y_{\alpha}$ and $z_{\alpha}$ via transfinite induction. Let $x_{1}$ be a real such that, for every $\gamma>0$ and all sufficiently large $r$ ,

$K^{A_{1}}_{(1+\gamma)r,r}(w_{1}\,|\,w_{1})=s_{1}\gamma r=K_{(1+\gamma)r,r}(w_{1}\,|\,w_{1})$ .

Let $x_{1}$ be random relative to $A_{1}$ and $w_{1}$ . Let $y_{1}$ be a real such that, for every $\gamma>0$ and all sufficiently large $r$ ,

$K^{A_{1}}_{(1+\gamma)r,r}(y_{1}\,|\,y_{1})=(s_{1}+\frac{\delta}{2})\gamma r=K_{(1+\gamma)r,r}(y_{1}\,|\,y_{1})$ .

Let $z_{1}$ be the real whose binary expansion is given by

\displaystyle z_{1}[r]=\begin{cases}w_{1}[r]&\text{ if }a_{n}<r\leq\frac{1-s_{2}}{1-s_{1}}b_{n}\text{ for some }n\in\mathbb{N}\\ x_{1}[r]&\text{ if }\frac{1-s_{2}}{1-s_{1}}b_{n}<r\leq b_{n}\text{ for some }n\in\mathbb{N}\\ y_{1}[r]&\text{ if }b_{n}<r\leq(1-\delta)a_{n+1}<\text{ for some }n\in\mathbb{N}\\ 0&\text{ if }(1-\delta)a_{n+1}<r\leq(1+\delta)a_{n+1}<\text{ for some }n\in\mathbb{N}\\ \end{cases}

For the induction step, suppose we have defined our points up to $\alpha$ . Let $A$ be the join of $\bigcup_{\beta<\alpha}(A_{\beta},w_{\beta}.x_{\beta},y_{\beta},z_{\beta})$ and $A_{\alpha}$ . Let $x_{\alpha}$ be a real such that, for every $\gamma>0$ and all sufficiently large $r$ ,

$K^{A}_{(1+\gamma)r,r}(w_{\alpha}\,|\,w_{\alpha})=s_{1}\gamma r=K_{(1+\gamma)r,r}(w_{\alpha}\,|\,w_{\alpha})$ .

Let $x_{\alpha}$ be random relative to $A$ and $w_{\alpha}$ . Let $y_{\alpha}$ be a real such that, for every $\gamma>0$ and all sufficiently large $r$ ,

$K^{A,w_{\alpha},x_{\alpha}}_{(1+\gamma)r,r}(y_{\alpha}\,|\,y_{\alpha})=(s_{1}+\frac{\delta}{2})\gamma r=K_{(1+\gamma)r,r}(y_{\alpha}\,|\,y_{\alpha})$ .

Let $z_{\alpha}$ be the real whose binary expansion is given by

\displaystyle z_{\alpha}[r]=\begin{cases}w_{\alpha}[r]&\text{ if }a_{n}<r\leq\frac{1-s_{2}}{1-s_{1}}b_{n}\text{ for some }n\in\mathbb{N}\\ x_{\alpha}[r]&\text{ if }\frac{1-s_{2}}{1-s_{1}}b_{n}<r\leq b_{n}\text{ for some }n\in\mathbb{N}\\ y_{\alpha}[r]&\text{ if }b_{n}<r\leq(1-\delta)a_{n+1}<\text{ for some }n\in\mathbb{N}\\ x_{\beta}&\text{ if }(1-s_{1}\delta/2)a_{n+1}<r\leq a_{n+1}<\text{ where }f(\beta)=n\\ \end{cases}

Finally, we define our set $E=\{z_{\alpha}\}$ .

We begin by collecting relevant aspects of our construction. Let $\alpha$ be an ordinal, let $A=A_{\alpha}$ be the corresponding oracle in the order, and let $z=z_{\alpha}$ be the point constructed at ordinal $\alpha$ .

Let $n$ be sufficiently large. Let $a_{n}<r\leq\frac{1-s_{2}}{1-s_{1}}b_{n}$ ,

	$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{a_{n}}(z)+K^{A}_{r,a_{n}}(w_{\alpha}\,\|\,z)$
		$\displaystyle=K^{A}_{a_{n}}(z)+(r-a_{n})s_{1}+O(\log r).$		(9)

Let $t=\frac{1-s_{2}}{1-s_{1}}b_{n}<r\leq b_{n}$ ,

$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{t}(z)+K^{A}_{r,t}(x_{\alpha}\,\|\,z)$
	$\displaystyle=K^{A}_{t}(z)+(r-t)+O(\log r)$
	$\displaystyle=(t-a_{n})s_{1}+(r-t)+O(\log r)$
	$\displaystyle=ts_{1}+r-t+O(\log r)$
	$\displaystyle=r-(1-s_{1})t+O(\log r)$
	$\displaystyle=r-(1-s_{2})b_{n}+O(\log r).$	(10)

Let $b_{n}<r\leq(1-s_{1}\delta/2)a_{n+1}$ . Then,

$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{b_{n}}(z)+K^{A}_{r,b_{n}}(y_{\alpha}\,\|\,z)$
	$\displaystyle=b_{n}-(1-s_{2})b_{n}+K^{A}_{r,b_{n}}(y_{\alpha}\,\|\,z)$
	$\displaystyle=s_{2}b_{n}+K^{A}_{r,b_{n}}(y_{\alpha}\,\|\,z)$
	$\displaystyle=s_{2}b_{n}+(s_{1}+\frac{\delta}{2})(r-b_{n}).$	(11)

Finally, let $t=(1-s_{1}\delta/2)a_{n+1}<r\leq a_{n+1}$ and let $\beta<\alpha$ be the ordinal such that $f(\beta)=n$ . Then,

$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{t}(z)+K^{A}_{r,t}(x_{\beta}\,\|\,z)$
	$\displaystyle=s_{2}b_{n}+(s_{1}+\frac{\delta}{2})(t-b_{n})+K^{A}_{r,t}(x_{\beta}\,\|\,z)$
	$\displaystyle=(s_{1}+\frac{\delta}{2})t+K^{A}_{r,t}(x_{\beta}\,\|\,z)$	(12)

In particular,

$\displaystyle s_{1}r$	$\displaystyle\leq K^{A}_{r}(z)$
	$\displaystyle=(s_{1}+\frac{\delta}{2})t+K^{A}_{r,t}(x_{\beta}\,\|\,z)$
	$\displaystyle\leq(s_{1}+\frac{\delta}{2})r+r-t$
	$\displaystyle\leq(s_{1}+\frac{\delta}{2})r+\frac{\delta r}{2}$
	$\displaystyle=s_{2}r$	(13)

Let $a_{n}<r\leq a_{n+1}$ . The above inequalities show that, if $r>\frac{1-s_{2}}{1-s_{1}}b_{n}$ , then

$K^{A}_{r}(z)\geq s_{1}r$ .

When $r\leq\frac{1-s_{2}}{1-s_{1}}b_{n}$ , by combining equality (9) and inequality (13),

	$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{a_{n}}(z)+(r-a_{n})s_{1}+O(\log r)$
		$\displaystyle\geq s_{1}a_{n}+(r-a_{n})s_{1}+O(\log r)$
		$\displaystyle=s_{1}r+O(\log r).$

Therefore, $K^{A}_{r}(z)\geq s_{1}r$ . for all $r$ . For the lower bound, let $r=\frac{1-s_{2}}{1-s_{1}}b_{n}$ . Then,

	$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{a_{n}}(z)+(r-a_{n})s_{1}+O(\log r)$
		$\displaystyle\leq a_{n}++(r-a_{n})s_{1}+O(\log r)$
		$\displaystyle\leq s_{1}r+O(\log r),$

and so $\dim^{A}(z)=s_{1}$ .

Similarly, the above inequalities show that $K^{A}_{r}(z)\leq s_{2}r$ . To prove the lower bound, let $r=b_{n}$ . Then

	$\displaystyle K^{A}_{r}(z)$	$\displaystyle=r-(1-s_{2})b_{n}+O(\log r)$
		$\displaystyle=s_{2}r+O(\log r),$

and so $\operatorname{Dim}^{A}(z)=s_{2}$ .

To complete the proof, we must show that $E$ does not have an optimal Hausdorff oracle, nor an optimal packing oracle. Let $A=A_{\alpha}$ be any Hausdorff oracle for $E$ . Let $B$ be an oracle encoding the set $\{w_{\beta},x_{\beta},y_{\beta}\,|\,\beta\leq\alpha\}$ . Note that we can encode this information since this set is countable.

Let $z_{\beta}\in E$ . First, suppose that $\beta\leq\alpha$ . Then by our choice of $B$ , $\dim^{A_{\alpha},B}(z_{\beta})=0$ . So then suppose that $\beta>\alpha$ . Let $n$ be a sufficiently large natural such that $f(\alpha)=n$ . Then, since $x_{\alpha}$ is random relative to $A_{\alpha}$

	$\displaystyle K^{A_{\alpha}}_{a_{n+1}}(z_{\beta})$	$\displaystyle=(s_{1}+\frac{\delta}{2})t+K^{A}_{a_{n+1},t}(x_{\alpha}\,\|\,z)$
		$\displaystyle\geq(s_{1}+\frac{\delta}{2})t+a_{n+1}-t,$

where $t=(1-s_{1}\delta/2)a_{n+1}$ . However, by our construction on $B$ ,

	$\displaystyle K^{A_{\alpha},B}_{a_{n+1}}(z_{\beta})$	$\displaystyle=(s_{1}+\frac{\delta}{2})t+K^{A,B}_{r,t}(x_{\alpha}\,\|\,z)$
		$\displaystyle\geq(s_{1}+\frac{\delta}{2})t+O(1).$

Therefore,

	$\displaystyle K^{A_{\alpha}}_{a_{n+1}}(z_{\beta})-K^{A_{\alpha},B}_{a_{n+1}}(z_{\beta})$	$\displaystyle=a_{n+1}-t$
		$\displaystyle=\frac{s_{1}\delta a_{n+1}}{2}.$

Since $z_{\beta}$ was arbitrary, it follows that $B$ reduces the complexity of every point $z\in E$ infinitely often. Since $A_{\alpha}$ was arbitrary, we conclude that $E$ does not have optimal Hausdorff nor optimal packing oracles. ∎

Corollary 42.

Assuming CH and AC, for every $0<s_{1}<s_{2}\leq 1$ there is a set $E\subseteq\mathbb{R}$ which has optimal Hausdorff oracles but does not have optimal packing oracles such that

$\dim_{H}(E)=s_{1}$ and $\dim_{P}(E)=s_{2}$ .

Proof.

Let $F$ be a set such that $\dim_{H}(F)=\dim_{P}(F)=s_{1}$ . Then, by Lemma 17, $F$ has optimal Hausdorff oracles. Let $G$ be a set, guaranteed by Theorem 41, with $\dim_{H}(G)<s_{1}$ , $\dim_{P}(G)=s_{2}$ such that $G$ does not have optimal Hausdorff nor optimal packing oracles.

Let $E=F\cup G$ . Then $\dim_{H}(E)=s_{1}$ and $\dim_{P}(E)=s_{2}$ by the union formula for Hausdorff and packing dimension. By Observation 6, $E$ has optimal Hausdorff oracles.

We now prove that $E$ does not have optimal packing oracles. Let $A$ be a packing oracle for $E$ . By possibly joining $A$ with a packing oracle for $G$ , we may assume that $A$ is a packing oracle for $G$ as well. Since $G$ does not have optimal packing oracles, there is an oracle $B\subseteq\mathbb{N}$ and $\epsilon>s_{2}-s_{1}$ such that, for every $x\in G$ where $\operatorname{Dim}^{A,B}(x)\geq s_{2}-\epsilon$ ,

$K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r$

for infinitely many $r$ . Let $x\in E$ such that $\operatorname{Dim}^{A,B}(x)\geq s_{2}-\epsilon$ . Then, by our choice of $F$ , $x$ must be in $G$ . Therefore

$K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r$

for infinitely many $r$ , and so $A$ is not an optimal packing oracle for $E$ . Since $A$ was arbitrary, the conclusion follows.

∎

Theorem 43.

Assuming CH and AC, for every $0<s_{1}<s_{2}\leq 1$ there is a set $E\subseteq\mathbb{R}$ which has optimal packing oracles but does not have optimal Hausdorff oracles such that

$\dim_{H}(E)=s_{1}$ and $\dim_{P}(E)=s_{2}$ .

Proof.

Let

$F=\{x\in(0,1)\,|\,\dim(x)=0\text{ and }\operatorname{Dim}(x)=s_{2}\}$ .

By Lemma 37, $\dim_{H}(F)=0$ , $\dim_{P}(F)=s_{2}$ and $F$ has optimal packing oracles. Let $G$ be a set, guaranteed by Theorem 41, with $\dim_{H}(G)=s_{1}$ , $\dim_{P}(G)=s_{2}$ such that $G$ does not have optimal Hausdorff nor optimal packing oracles. Let $E=F\cup G$ . Then $\dim_{H}(E)=s_{1}$ and $\dim_{P}(E)=s_{2}$ by the union formula for Hausdorff and packing dimension. By Observation 35, $E$ has optimal packing oracles.

We now prove that $E$ does not have optimal Hausdorff oracles. Let $A$ be a Hausdorff oracle for $E$ . By possibly joining $A$ with a Hausdorff oracle for $G$ , we may assume that $A$ is a Hausdorff oracle for $G$ as well. Since $G$ does not have optimal Hausdorff oracles, there is an oracle $B\subseteq\mathbb{N}$ and $\epsilon>s_{1}$ such that, for every $x\in G$ where $\dim^{A,B}(x)\geq s_{1}-\epsilon$ ,

$K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r$

for infinitely many $r$ . Let $x\in E$ such that $\dim^{A,B}(x)\geq s_{1}-\epsilon$ . Then, since $\dim_{H}(F)=0$ , $x$ must be in $G$ . Therefore

$K^{A,B}_{r}(x)<K^{A}_{r}(x)-\epsilon r$

for infinitely many $r$ , and so $A$ is not an optimal Hausdorff oracle for $E$ . Since $A$ was arbitrary, the conclusion follows. ∎

6 Acknowledgments

I would like to thank Denis Hirschfeldt, Jack Lutz and Chris Porter for very valuable discussions and suggestions. I would also like to thank the participants of the recent AIM workshop on Algorithmic Randomness.

References

[1] Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM J. Comput., 37(3):671–705, 2007.
[2] Christopher J. Bishop and Yuval Peres. Fractals in probability and analysis, volume 162 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2017.
[3] Adam Case and Jack H. Lutz. Mutual dimension. ACM Transactions on Computation Theory, 7(3):12, 2015.
[4] Logan Crone, Lior Fishman, and Stephen Jackson. Hausdorff dimension regularity properties and games. arXiv preprint arXiv:2003.11578, 2020.
[5] Roy O. Davies. Two counterexamples concerning Hausdorff dimensions of projections. Colloq. Math., 42:53–58, 1979.
[6] Rod Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010.
[7] Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, third edition, 2014.
[8] Kenneth Falconer, Jonathan Fraser, and Xiong Jin. Sixty years of fractal projections. In Fractal geometry and stochastics V, pages 3–25. Springer, 2015.
[9] Leonid A. Levin. On the notion of a random sequence. Soviet Math Dokl., 14(5):1413–1416, 1973.
[10] Leonid Anatolevich Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30–35, 1974.
[11] Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008.
[12] Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236–1259, 2003.
[13] Jack H. Lutz. The dimensions of individual strings and sequences. Inf. Comput., 187(1):49–79, 2003.
[14] Jack H. Lutz and Neil Lutz. Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory, 10(2):Art. 7, 22, 2018.
[15] 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.
[16] Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM J. Comput., 38(3):1080–1112, 2008.
[17] Neil Lutz. Fractal intersections and products via algorithmic dimension. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 2017.
[18] 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.
[19] Neil Lutz and D. M. Stull. Projection theorems using effective dimension. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 2018.
[20] J. M. Marstrand. Some fundamental geometrical properties of plane sets of fractional dimensions. Proc. London Math. Soc. (3), 4:257–302, 1954.
[21] Pertti Mattila. Hausdorff dimension, orthogonal projections and intersections with planes. Ann. Acad. Sci. Fenn. Ser. AI Math, 1(2):227–244, 1975.
[22] Pertti Mattila. Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Cambridge University Press, 1999.
[23] Pertti Mattila. Hausdorff dimension, projections, and the fourier transform. Publicacions matematiques, pages 3–48, 2004.
[24] Pertti Mattila. Hausdorff dimension, projections, intersections, and besicovitch sets. In New Trends in Applied Harmonic Analysis, Volume 2, pages 129–157. Springer, 2019.
[25] Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett., 84(1):1–3, 2002.
[26] 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.
[27] Andre Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009.
[28] Tuomas Orponen. Combinatorial proofs of two theorems of Lutz and Stull. arXiv preprint arXiv:2002.01743, 2020.
[29] 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.

	$\displaystyle K^{A,B}_{r}(x)$	$\displaystyle=K^{A,B}_{r}(z)+K^{A,B}_{r}(y\,\|\,z)$
		$\displaystyle<K^{A}_{r}(z)-\epsilon r/2+K^{A,B}_{r}(y\,\|\,z)$
		$\displaystyle\leq K^{A}_{r}(z)-\epsilon r/2+K^{A}_{r}(y\,\|\,z)$
		$\displaystyle=K^{A,B}_{r}(x)-\epsilon r/2.$

$\displaystyle K^{A}_{r}(z)$	$\displaystyle=K^{A}_{t}(z)+K^{A}_{r,t}(x_{\beta}\,\|\,z)$
	$\displaystyle=s_{2}b_{n}+(s_{1}+\frac{\delta}{2})(t-b_{n})+K^{A}_{r,t}(x_{\beta}\,\|\,z)$
	$\displaystyle=(s_{1}+\frac{\delta}{2})t+K^{A}_{r,t}(x_{\beta}\,\|\,z)$	(12)

Optimal Oracles for Point-to-Set Principles

Abstract

1 Introduction

2 Preliminaries

2.1 Outer Measures and Classical Dimension

Remark.

Theorem 1.

Example.

Example.

Example.

2.2 Algorithmic Information Theory

Theorem 2 (Point-to-set principle).

3 Optimal Hausdorff Oracles

Definition 3.

Proposition 4.

Proof.

Lemma 5.

Proof.

Observation 6.

Proposition 7.

Proof.

3.1 Outer Measures and Optimal Oracles

Observation 8.

Proposition 9.

Proof.

Lemma 10.

Proof.

Lemma 11 ([3]).

Lemma 12.

Proof.

Theorem 13.

Proof.

Corollary 14.

3.2 Sets with optimal Hausdorff oracles

Lemma 15.

Proof.

Corollary 16.

Lemma 17.

Proof.

3.3 Sets without optimal Hausdorff oracles

Lemma 18.

Lemma 19.

Proof.

Lemma 20.

Proof.

3.3.1 Generalization to ℝn\mathbb{R}^{n}

Lemma 21.

Proof.

Theorem 22.

Proof.

4 Marstrand’s Projection Theorem

Theorem 23.

Theorem 24.

Proof.

Example.

Example.

4.1 Counterexample to Marstrand’s theorem

Theorem 25.

Observation 26.

Proof.

Lemma 27.

Proof.

Lemma 28.

Proof.

4.2 Generalization to the endpoint s=0s=0

Theorem 29.

Lemma 30.

Proof.

Lemma 31.

Proof.

5 Optimal Packing Oracles

Definition 32.

Proposition 33.

Proof.

Lemma 34.

Proof.

Observation 35.

Lemma 36.

Proof.

Lemma 37.

3.3.1 Generalization to $\mathbb{R}^{n}$

4.2 Generalization to the endpoint $s=0$