By the Point-to-Set Principle (Theorem 2.4.1), every set X⊆Rm has a Hausdorff oracle: that is, an oracle A with supx∈XdimA(x)=dimH(X). Inuitively, this means that a Hausdorff oracle is one which can compute approximations to all points of X powerfully enough to recuperate the classical dimension of X.
But Hausdorff oracles are far from unique. Computing with extra oracle power can’t meaningfully increase complexity, so if A is a Hausdorff oracle for X, then so is the join of A with any other oracle B. As dimH(X) is a lower-bound to supx∈XdimA,B(x), this oracle B cannot lower the effective dimension assigned to most points of X when joined with A. In this sense, A is relatively “optimal” for X.
But recall that effective Hausdorff dimension is the limit inferior of prefix complexity. It’s still possible that KrA,B(x) could fall significantly below KrA(x) at infinitely many precision levels r∈ω and for some x∈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 X. Stull’s motivation was the Marstrand-Mattila Projection Theorem (Theorem A.1): its classical proof needs X 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⊆Rm and s:=dimH(X)≥0.
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 B 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,ε), would have KrA(x)≤KrA,x(x)+εr≤K(r)+εr+O(1) for all but finitely many r, so DimA(x)≤ε. By Point-to-Set Principle for packing dimension (Theorem 2.4.2), dimH(X)≤dimP(X)≤ε, too.
The proposition excludes dimension zero. That case is trivial.
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=2, n=1. For θ∈[0,π], let pθ:R2→R be the projection pθ(z):=z1cosθ+z2sinθ.
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) there is a set X⊆R2 with dimH(X)=1+s but dimH(pθX)=s for every θ∈(π/4,3π/4) (Theorem 23 of Stull (2022)). Optimal oracles have since been used to construct universal sets of directions for projection theorems Fiedler & Stull, 2024.
The two conditions in Definition 3.1.1 play different roles. The first is a witness condition: A attains the minimum in a point-to-set principle. The second is a fitness condition: A cannot be improved, at almost every precision, by any additional oracle.
A fit oracle need not be a Hausdorff oracle. For example, let A be an optimal Hausdorff oracle for some Y⊆Rm with dimH(Y)<m, and pick any z∈Rm sufficiently random relative to A (so dimA(z)=m). Then A is Hausdorff-fit for X:=Y∪{z}, since the witnesses for Y still serve, but A is not a Hausdorff oracle for X.
So, for sets of positive dimension, having optimal Hausdorff oracles amounts to a single condition:
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
Crone, L., Fishman, L., & Jackson, S. (2020). Hausdorff Dimension Regularity Properties and Games.
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.
Fiedler, J. B., & Stull, D. M. (2024). Universal Sets for Projections.