Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

3.1 Optimal Oracles via Kolmogorov Complexity

By the Point-to-Set Principle (Theorem 2.4.1), every set X⊆RmX \subseteq \mathbb{R}^m has a Hausdorff oracle: that is, an oracle AA with sup⁡x∈Xdim⁡A(x)=dim⁡H⁡(X)\sup_{x \in X} \dim^A(x) = \dim_{\operatorname{H}}(X). Inuitively, this means that a Hausdorff oracle is one which can compute approximations to all points of XX powerfully enough to recuperate the classical dimension of XX.

But Hausdorff oracles are far from unique. Computing with extra oracle power can’t meaningfully increase complexity, so if AA is a Hausdorff oracle for XX, then so is the join of AA with any other oracle BB. As dim⁡H⁡(X)\dim_{\operatorname{H}}(X) is a lower-bound to sup⁡x∈Xdim⁡A,B(x)\sup_{x \in X} \dim^{A, B}(x), this oracle BB cannot lower the effective dimension assigned to most points of XX when joined with AA. In this sense, AA is relatively “optimal” for XX.

But recall that effective Hausdorff dimension is the limit inferior of prefix complexity. It’s still possible that KrA,B(x)K^{A, B}_r(x) could fall significantly below KrA(x)K^A_r(x) at infinitely many precision levels r∈ωr \in \omega and for some x∈Xx \in X.

D. Stull asked for an oracle which rules this possibility out at almost every precision level, for at least one point of nearly full effective Hausdorff dimension against any join on that oracle Stull, 2022. Such an oracle would be even moreso “optimal” for XX. Stull’s motivation was the Marstrand-Mattila Projection Theorem (Theorem A.1): its classical proof needs XX to be analytic, while sets with optimal Hausdorff oracles satisfy its conclusion in the plane without any such assumption (Theorem 3.1.9).

For the remainder of this page, let X⊆RmX \subseteq \mathbb{R}^m and s:=dim⁡H⁡(X)≥0s := \dim_{\operatorname{H}}(X) \geq 0.

3.1.1Optimal Oracles

The following is Stull’s original, algorithmic information theoretic definition for optimal oracles.

Notice that the second condition asks only for a single point whose complexity the additional oracle BB can’t reduce by a linear amount at almost every precision. It turns out that this is equivalent to asking the same for many such points. Let’s collect all the points satisfying this second condition into a set.

We can’t ask much more than this: for no single point can serve every additional oracle in general. For instance, any x∈NX(A,x,ε)x \in N_X(A, x, \varepsilon), would have KrA(x)≤KrA,x(x)+εr≤K(r)+εr+O(1)K^A_r(x) \leq K^{A, x}_r(x) + \varepsilon r \leq K(r) + \varepsilon r + O(1) for all but finitely many rr, so Dim⁡A(x)≤ε\operatorname{Dim}^A(x) \leq \varepsilon. By Point-to-Set Principle for packing dimension (Theorem 2.4.2), dim⁡H⁡(X)≤dim⁡P⁡(X)≤ε\dim_{\operatorname{H}}(X) \leq \dim_{\operatorname{P}}(X) \leq \varepsilon, too.

The proposition excludes dimension zero. That case is trivial.

3.1.2Known Results

The following are results of Stull (2022) related to having optimal oracles. First, closure under natural operations on oracles and sets.

Several (classical) classes of sets are known to have optimal oracles.

But whether every set has optimal oracles actually depends on the axioms of set theory.

The proof combines the analytic case with the theorem of L. Crone, L. Fishman, and S. Jackson that, under AD, every set has a Borel subset of the same Hausdorff dimension Crone et al., 2020. Recall that AD contradicts the Axiom of Choice.

The original motivation for optimal oracles is Marstrand’s projection theorem (Theorem A.1), here in the planar case m=2m = 2, n=1n = 1. For θ∈[0,π]\theta \in [0, \pi], let pθ:R2→Rp_\theta : \mathbb{R}^2 \to \mathbb{R} be the projection pθ(z):=z1cos⁡θ+z2sin⁡θp_\theta(z) := z_1 \cos \theta + z_2 \sin \theta.

By Theorem 3.1.6, this recovers Marstrand’s theorem for analytic sets and the extension of Lutz & Stull (2018) to weakly regular sets. Some hypothesis is needed: assuming AC and CH, for every s∈(0,1)s \in (0, 1) there is a set X⊆R2X \subseteq \mathbb{R}^2 with dim⁡H⁡(X)=1+s\dim_{\operatorname{H}}(X) = 1 + s but dim⁡H⁡(pθX)=s\dim_{\operatorname{H}}(p_\theta X) = s for every θ∈(π/4,3π/4)\theta \in (\pi/4, 3\pi/4) (Theorem 23 of Stull (2022)). Optimal oracles have since been used to construct universal sets of directions for projection theorems Fiedler & Stull, 2024.

3.1.3Witness and Fitness

The two conditions in Definition 3.1.1 play different roles. The first is a witness condition: AA attains the minimum in a point-to-set principle. The second is a fitness condition: AA cannot be improved, at almost every precision, by any additional oracle.

A fit oracle need not be a Hausdorff oracle. For example, let AA be an optimal Hausdorff oracle for some Y⊆RmY \subseteq \mathbb{R}^m with dim⁡H⁡(Y)<m\dim_{\operatorname{H}}(Y) < m, and pick any z∈Rmz \in \mathbb{R}^m sufficiently random relative to AA (so dim⁡A(z)=m\dim^A(z) = m). Then AA is Hausdorff-fit for X:=Y∪{z}X := Y \cup \seq{z}, since the witnesses for YY still serve, but AA is not a Hausdorff oracle for XX.

So, for sets of positive dimension, having optimal Hausdorff oracles amounts to a single condition:

(∃A)(∀B)(∀ε>0)[dim⁡H⁡(NX(A,B,ε))=dim⁡H⁡(X)].\begin{aligned} (\exists A)(\forall B)(\forall \varepsilon > 0) \brk{\dim_{\operatorname{H}}(N_X(A, B, \varepsilon)) = \dim_{\operatorname{H}}(X)}. \end{aligned}
References
  1. Stull, Donald. M. (2022). Optimal Oracles for Point-To-Set Principles. In P. Berenbrink & B. Monmege (Eds.), 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (Vol. 219, p. 57:1-57:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 10.4230/LIPIcs.STACS.2022.57
  2. Crone, L., Fishman, L., & Jackson, S. (2020). Hausdorff Dimension Regularity Properties and Games.
  3. Lutz, N. J., & Stull, D. M. (2018). Projection theorems using effective dimension. In 43rd International Symposium on Mathematical Foundations of Computer Science (Vol. 117, p. Art. No. 71, 15). Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern.
  4. Fiedler, J. B., & Stull, D. M. (2024). Universal Sets for Projections.