1.12 Point-to-Set Principles - Algorithmic Information Theory

In this context, a point-to-set (PTS) principle will characterize the fractal dimension or measure content of a subset by some local dimension or measure assigned to its elements. We summarize the few PTS principles known for Hausdorff dimension and the $s$ -dimensional Hausdorff outer measures via algorithmically-restricted quantities.

1.12.1 PTS for Hausdorff Dimension¶

Certain fractal dimension notions have pointwise, algorithmic characterizations (over simple spaces such as Cantor space and Euclidean space). This was originally shown for Hausdorff dimension in 2017 by J. Lutz and N. Lutz Lutz & Lutz, 2018.

Notably, this implies that for each subset $X$ , there exists an oracle $B \in 2^{\leq \omega}$ which is powerful enough to simulate Hausdorff dimension by ML- $B$ - $s$ -tests. Any such oracle is called a Hausdorff oracle for $X$ . An analogous formula holds for classical packing dimension (see Theorem 2 of Lutz & Lutz (2018)), swapping weak effective dimension $\dim$ for strong dimension: $\operatorname{Dim}$ .

The main insight used to prove the Point-to-Set Principle involves the ability to build for a fixed set $X \subseteq \mathbb{R}^m$ an oracle $B$ with knowledge of how $X$ intersects with any given dyadic cube from $\mathcal{Q}^m$ . Arbitrary covers of $X$ exhibiting $\dim_{\operatorname{H}} X$ may be approximated using covers comprising dyadic cubes, and so the Hausdorff dimension of $X$ is the supremum of the size of the intersection with $X$ along nested sequences of dyadic cubes. Suppose that the intersection of a nested sequence intersecting with $X$ is the singleton set containing $x \in X$ . Then $\dim^B(x)$ exactly captures how much dimension $X$ takes on at $x$ .

In practice, the power of the Point-to-Set Principle is in proving lower-bounds for Hausdorff dimension. As remarked to me by Ryan Bushling, one might as well consider this a local-to-global principle for the following reason: in order to witness a lower bound on $\dim_{\operatorname{H}}X$ , it is not enough to find a single sufficiently-random element $x \in X$ , for any countable number of reals could be coded into an oracle. Instead, one must demonstrate the existence of many highly-complex elements of $X$ , which requires knowledge of a large portion of the set to do.

The Point-to-Set Principle has found applications across geometric measure theory, including in bounding the Hausdorff dimension of Furstenberg sets Lutz & Stull, 2020Stull, 2018, lineal extensions Bushling & Fiedler, 2025, distance sets Altaf et al., 2023, and pinned-distance sets Stull, 2022; as well as in extending the Marstrand-Mattila Projection Theorem Stull, 2022.

Well before the full Point-to-Set Principle was proved, L. Staiger Staiger, 1989 and B. Ryabko Ryabko, 1993Ryabko, 1994 had already observed versions of the Point-to-Set Principle for simply-definable classes such as $\Sigma^0_2$ -classes. This was slightly generalized by J. Hitchcock in Hitchcock (2005) in what he calls a correspondence principle between constructive dimension and Hausdorff dimension Hitchcock, 2005. The spirit of any correspondence principle is to characterize a classical notion by unrelativized, effective means (i.e., avoiding oracles).

Hitchcock further showed that this correspondence broke down immediately beyond this level of the lightface Borel hierarchy.

1.12.2 PTS for Hausdorff Measures¶

The original Point-to-Set Principle has recently been refined to the $s$ -dimensional Hausdorff outer measures by P. Lutz and J. Miller Lutz & Miller, 2024. These results also expand on the complexity characterizations of various partial randomness notions from Theorem 1.11.2.

By Theorem 1.11.2, $X$ is not $\sigma$ -finite in dimension $s$ if and only if there is a strong Solovay- $B$ - $s$ -random element in $X$ for every oracle $B$ .

Corollary 1.12.4

For every $X \subseteq 2^\omega$ and $s \geq 0$ ,

\begin{aligned} \mathcal{H}^s(X) > 0 & \iff(\forall B \in 2^{\leq \omega})(\exists x \in X)\brk{\liminf_{r \to \infty} \operatorname{\Delta M}_s^B(\restrict{x}{r}) > -\infty}\\ & \iff(\forall B \in 2^{\leq \omega})(\exists x \in X)\brk{\liminf_{r \to \infty} \operatorname{\Delta P}_s^B(\restrict{x}{r}) > -\infty}, \\ \mathcal{H}^s(X) < \infty &\iff (\exists B \in 2^{\leq \omega}) \brk{\sup_{x \in X} \liminf_{r \to \infty} \operatorname{\Delta M}_s^B(\restrict{x}{r}) < \infty}. \end{aligned}

Again by Theorem 1.11.2, $X$ is not $s$ -null if and only if there is an ML- $B$ - $s$ -random element in $X$ for every oracle $B$ .

In effect, these refined point-to-set principles demonstrate the usefulness of a priori complexity–defined by continuous semimeasures–in characterizing not just Hausdorff dimension but also the $s$ -dimensional Hausdorff outer measures.

References¶

Lutz, J. H., & Lutz, N. J. (2018). Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory, 10(2), Art. 7, 22. 10.1145/3201783
Lutz, N. J., & Stull, D. M. (2020). Bounding the dimension of points on a line. Inform. and Comput., 275, 104601, 15. 10.1016/j.ic.2020.104601
Stull, D. M. (2018). Results on the Dimension Spectra of Planar Lines. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (Vol. 117, p. 79:1-79:15). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 10.4230/LIPIcs.MFCS.2018.79
Bushling, R. E. G., & Fiedler, J. B. (2025). Bounds on the dimension of lineal extensions. Journal of Fractal Geometry, 12(1/2), 105–133. 10.4171/JFG/161
Altaf, I., Bushling, R., & Wilson, B. (2023). Distance sets bounds for polyhedral norms via effective dimension.
Stull, D. M. (2022). Pinned Distance Sets Using Effective Dimension. https://arxiv.org/abs/2207.12501
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
Staiger, L. (1989). Kolmogorov complexity and Hausdorff dimension. In J. Csirik, J. Demetrovics, & F. Gécseg (Eds.), Fundamentals of Computation Theory (pp. 434–443). Springer Berlin Heidelberg.
Ryabko, B. Ya. (1993). Algorithmic Approach to the Prediction Problem. Probl. Peredachi Inf., 29(2), 96–103. http://mi.mathnet.ru/ppi180
Ryabko, B. Ya. (1994). The Complexity and Effectiveness of Prediction Algorithms. Journal of Complexity, 10(3), 281–295. https://doi.org/10.1006/jcom.1994.1015
Hitchcock, J. M. (2005). Correspondence principles for effective dimensions. Theory Comput. Syst., 38(5), 559–571. 10.1007/s00224-004-1122-1
Lutz, P., & Miller, J. S. (2024). Point-to-Set Principles for Hausdorff Measure.