AIT defines effective dimension under an algorithmic restriction; but in the limit of stronger computational powers, it is intuitive that AIT might recover the classically-defined fractal dimensions. The point-to-set principles formalize this. 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 -dimensional Hausdorff outer measures via algorithmically-restricted quantities.
2.4.1PTS 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 , there exists an oracle which is powerful enough to simulate Hausdorff dimension by ML---tests. Any such oracle is called a Hausdorff oracle for .
An analogous formula holds for classical packing dimension, wapping weak effective dimension for strong dimension :
Likewise, any oracle attaining this minimum is called a packing oracle for .
The main insight used to prove the Point-to-Set Principle involves the ability to build for a fixed set an oracle with knowledge of how intersects with any given dyadic cube from . Arbitrary covers of exhibiting may be approximated using covers comprising dyadic cubes, and so the Hausdorff dimension of is the supremum of the size of the intersection with along nested sequences of dyadic cubes. Suppose that the intersection of a nested sequence intersecting with is the singleton set containing . Then exactly captures how much dimension takes on at .
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 , it is not enough to find a single sufficiently-random element , for any countable number of reals could be coded into an oracle. Instead, one must demonstrate the existence of many highly-complex elements of , 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 -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.
2.4.2PTS by Coding on Balls¶
K. Miyabe observed that the point-to-set principle factors into a purely classical coding theorem, followed by an encoding of countable data into an oracle Miyabe, 2026.
Note that Miyabe writes where we write .
One might view the Hausdorff dimension result above as a Euclidean, ball-based counterpart to B. Ryabko’s coding theorem for combinatorial sources in Ryabko, 1986.
Here, we reproduce the proof of Miyabe’s Hausdorff dimension formula.
The effective version follows by rationalizing a minimizing code and storing it in an oracle.
One can prove the first part by enlargening each ball of the original ball code to a rational closed ball of less than twice its diameter. For the second part: it suffices to encode both the domain and graph of the ball code.
By Proposition 2.1.10, these are exactly and . So Theorem 2.4.7 recovers Theorem 2.4.1 and its packing analogue (Corollary 5.9 of Miyabe (2026)). Conversely, granting the point-to-set principle, the same two lemmas recover the rational-ball case of Theorem 2.4.5.
2.4.3PTS for Hausdorff Measures¶
The original Point-to-Set Principle has recently been refined to the -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.6.2.
By Theorem 1.6.2, is not -finite in dimension if and only if there is a strong Solovay---random element in for every oracle .
Again by Theorem 1.6.2, is not -null if and only if there is an ML---random element in for every oracle .
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 -dimensional Hausdorff outer measures.
On , Miyabe’s ball codes also give a classical characterization of nullity at a fixed exponent.
Effectivizing as in Theorem 2.4.7 gives a Euclidean analogue of the characterization in Corollary 2.4.9.
- 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
- Miyabe, K. (2026). Ball codes: A coding characterization of Hausdorff and packing dimensions.
- Ryabko, B. Ya. (1986). Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity. Problems of Information Transmission, 22(3), 170–179.
- Lutz, P., & Miller, J. S. (2024). Point-to-Set Principles for Hausdorff Measure.